最新消息：「几何深度学习」从古希腊到AlphaFold，「图神经网络」起源于物理与化学

转自 | 新智元

编辑 |LRS

【导读】 最近大火的「几何深度学习」到底是怎么出现的？创始人Michael Bronstein发布系列长文，带你从头开始回忆。

2016年，牛津大学教授、Twitter的图机器学习研究负责人Michael Bronstein发布了一篇论文，首次引入几何深度学习（Geometric Deep Learning, GDL）一词，试图从对称性和不变性的视角出发，从几何上统一CNNs、GNNs、LSTMs、Transformers等典型架构的方法。

(资料图)

论文链接： https://arxiv.org/pdf/1611.08097.pdf

比如传统网络认为E和3是不同的，但是具有镜像对称性（或π键旋转）的网络却会认为它们是一致的，而CNN则可以利用平移不变性等将右上角的3和中心的3视为等价，也就增强了泛化性。

最近，Michael Bronstein发起了四篇专栏文章，从古希腊几何到物理、化学，再到现代图神经网络，详细介绍了几何深度学习（GDL）背后的思想是如何出现的。

第一篇主要讨论对称性的概念如何促进理论物理学的发展，第二篇为神经网络的早期历史和第一个「AI寒冬」，第三篇主要研究第一个「几何」架构，第四篇讨论了1960年代化学领域中GNN的早期原型，下面是对第三、四篇的专栏文章翻译。

第一个几何架构

第一个新「几何」类型的神经网络架构的灵感来自于神经科学。

在一系列后来成为经典并夺得诺贝尔医学奖的实验中，哈佛大学的神经生理学家David Hubel和Torsten Wiesel共同揭开了大脑中负责模式识别的一部分，即视觉皮层的结构和功能。

通过向一只猫展示不断变化的光线图案并测量其脑细胞（神经元）的反应，结果表明视觉皮层中的神经元具有多层结构，具有局部空间连通性：一个细胞只有在其附近的细胞，即感受野被激活时才会产生反应。

此外，该组织似乎具有层次结构，其中对局部原始导向的阶梯状刺激作出反应的「简单细胞」被「复杂细胞」聚合，产生对更复杂模式的反应。

有人假设，视觉皮层深层的细胞会对由较简单的图案组成的越来越复杂的图案作出反应，并半开玩笑地提出存在一个「祖母细胞」，它只在显示一个人的祖母的脸时作出反应。

对视觉皮层结构的理解在计算机视觉和模式识别的研究早期产生了深远的影响，福岛邦彦（Kunihiko Fukushima），当时是日本广播公司的研究员，开发了一个新的神经网络架构，类似于Hubel和Wiesel提出的视觉神经系统的层次模型，并将其命名为neocognitron。

neocognitron系统由交错的S层和C层神经元组成，这一命名习惯也反映了其在生物视觉皮层中的灵感；每层的神经元按照输入图像的结构（视网膜）排列成二维阵列，每层有多个「细胞面」（现代术语叫做feature map）。

S层被设计成平移对称的，使用共享的可学习权重聚集来自局部感受野的输入，导致单个细胞面的细胞具有相同功能的感受野，但处于不同的位置，其原理是为了吸收可能出现在输入中任何地方的模式。

C层是固定的，并进行局部聚集（加权平均），对模式的具体位置不敏感，如果其输入中的任何一个神经元被激活，该C神经元就被激活。

由于neocognitron的主要应用是字符识别，因此平移不变性是至关重要的。这一特性与早期的神经网络（如Rosenblatt的感知器）有着根本的区别：为了可靠地使用感知器，必须先使输入模式的位置正常化，而在neocognitron中，对模式位置的不敏感性已被吸收入架构中。

通过将平移变化的局部特征提取层与池化交织在一起，形成一个多尺度的表征来实现neocognitron。

计算实验表明，福岛的架构即使在有噪音和几何扭曲的情况下也能够成功地识别复杂的图案，如字母或数字。

从该领域四十年来的进展来看，人们发现neocognitron已经具有现代深度学习架构的许多特征：深度（福岛在他的论文中模拟了一个七层网络）、局部感受野、共享权重和池化。它甚至使用了ReLU激活函数，通常被认为是在近期的深度学习架构中引入的。

与现代系统的主要区别在于网络的训练方式：neocognitron是一个以无监督方式训练的 「自组织」架构，因为反向传播在当时的神经网络界仍未被广泛使用。

卷积神经网络

Yann LeCun进一步发展了福岛的设计，他刚从巴黎大学毕业，博士论文是关于使用反向传播来训练神经网络。

他在AT&T贝尔实验室的第一个博士后职位上，LeCun和同事们建立了一个系统来识别信封上的手写数字，以使美国邮政服务能够自动发送邮件。

在一篇经典的论文中，LeCun等人描述了第一个三层卷积神经网络（CNN），与neocognitron类似，LeCun的CNN也使用了共享权重和池化的局部连接。但他放弃了福岛更复杂的非线性滤波（抑制性连接），而选择了简单的线性滤波，可以通过数字信号处理器（DSP）上的乘法和累加操作有效地实现卷积。

这一设计选择，背离了神经科学的灵感和术语，进入了信号处理的领域，将在随后的深度学习的成功中发挥关键作用。

CNN的另一个关键创新是使用反向传播进行训练。

LeCun的研究成果展示了基于梯度的方法在复杂模式识别任务中的威力，是最早的基于深度学习的计算机视觉系统之一。这个架构的演变中，一个有五层的CNN被命名为LeNet-5，作为对作者名字的双关语，被美国银行用来阅读手写支票。

但当时计算机视觉研究界的绝大多数人都没有选择神经网络，走上了一条不同的道路。

在新千年的第一个十年里，视觉识别系统的典型架构是一个精心制作的特征提取器，通常是检测图像中有趣的点，并以一种对视角转换和对比度变化具有鲁棒性的方式提供它们的局部描述，然后是一个简单的分类器，一般都是使用支持向量机SVM，少部分情况会使用一个小型神经网络。

深度学习的胜利

由于计算能力和可用的标注视觉数据量的快速增长，技术的天平被彻底打破，使得实现越来越大、越来越复杂的CNN成为可能，也使得解决越来越具有挑战性的视觉模式识别任务成为可能。

由美籍华人研究员李飞飞在2009年建立的ImageNet数据集，并随之举办的大规模视觉识别挑战赛在当时的计算机视觉领域掀起深度学习浪潮，其中包括数以百万计的人类标记的图像，参赛模型需要将其分为1000个不同类别。

Krizhevsky、Sutskever和Hinton在多伦多大学开发的一个CNN架构成功地以极大的优势击败了所有的竞争方法，如基于该领域几十年研究的智能工程特征检测器。AlexNet（为了纪念它的开发者Alex Krizhevsky）在参数和层数方面比它的前辈LeNet-5大得多，但从概念上来说是一样的。关键的区别在于使用图形处理器（GPU）进行训练。

ImageNet上CNN的成功成为深度学习的转折点，并在接下来的十年中预示了其广泛的应用前景，并衍生出了数十亿美元的行业，从Apple iPhone的语音识别到特斯拉自动驾驶汽车的商业系统中，深度学习无处不在。

当图神经网络遇上化学

如果说对称性的历史与物理学紧密地交织在一起，那么图形神经网络的历史，即几何深度学习的典型应用代表则植根于自然科学的另一个分支：化学。

化学在历史上一直是，现在也是数据最密集的学术学科之一，现代化学在十八世纪的出现导致了已知化合物的快速增长和对其组织的早期需求。

自19世纪中期以来，化学家们已经建立了一种能够普遍被接收的理解方式，通过结构式来指代化合物，表明化合物的原子、它们之间的键，甚至它们的三维几何形状，但这样的结构并不便于检索。

在20世纪上半叶，随着新发现的化合物及其商业用途的快速增长，组织、搜索和比较分子的问题变得至关重要：例如，当一家制药公司试图为一种新药申请专利时，专利局必须核实以前是否有类似的化合物被存入。

为了应对这一挑战，20世纪40年代引入了几个分子索引系统，为后来被称为化学信息学的新学科奠定了基础。其中一个系统以作者Gordon、Kendall和Davison的名字命名为「GKD化学密码」，由英国轮胎公司Dunlop开发，用于早期基于打卡的计算机。从本质上讲，GKD密码是一种将分子结构解析为一个字符串的算法，可以更容易地被人类或计算机查询。

但GKD密码和其他相关方法远远不能令人满意。在化合物中，类似的结构往往会导致类似的属性，化学家们被训练成具有发现这种相似性的直觉，并在比较化合物时寻找它们。

例如，苯环与气味特性的联系是19世纪「芳香族化合物」这一化学类别命名的原因。

另一方面，当一个分子被表示为一个字符串时（如在GKD密码中），单一化学结构的成分可能被映射到密码的不同位置。因此，两个含有类似子结构的分子（因此可能具有类似的性质）可能以非常不同的方式被编码。

这种认识促进了「拓扑密码」的发展，研究者试图拆解分子的结构。这方面的第一项工作是在陶氏化学公司和美国专利局完成的，它们都是化学数据库的大用户。

其中一个最有名的描述符，被称为「摩根指纹」，是由Harry Morgan在化学文摘社开发的，并一直使用到今天。

出生于罗马尼亚的苏联研究员George Vlăduţ在开发早期的「结构化」方法搜索化学数据库方面发挥了关键作用。

他是一名化学家，于1952年在莫斯科门捷列夫学院通过了有机化学的博士论文答辩，在大一的时候，他经历了一次与巨大的Beilstein手册的惨痛交锋，使得他的研究兴趣转向化学信息学，并在这一领域工作了一辈子。

Vlăduţ被认为是使用图论对化合物的结构和反应进行建模的先驱者之一。从某种意义上说，这并不令人惊讶：图论在历史上一直与化学联系在一起，甚至「图」这个词（指一组节点和边，而不是一个函数图）也是由数学家James Sylvester在1878年提出的，作为化学分子的一个数学抽象。

而且Vlăduţ主张将分子结构比较表述为图的同构问题；他最著名的工作是将化学反应分类为反应物和产物分子的部分同构（最大公共子图）。

Vlăduţ的工作启发了一对年轻的研究人员，Boris Weisfeiler（代数几何学家）和Andrey Lehman（自称是程序员）。

在一篇经典的合作论文中，两人介绍了一种迭代算法，用于测试一对图形是否同构（即，在节点重新排序之前，图形具有相同的结构），也被称为Weisfeiler-Lehman（WL）测试。虽然两人在学生时代就相识，但他们的文章发表后不久就分道扬镳了，各自在不同的领域都有了成就。

Weisfeiler和Lehman最初的猜想，即他们的算法解决了图的同构问题（而且是在多项式时间内解决）是不正确的：虽然Lehman在计算上证明了最多有九个节点的图，但一年后发现了一个更大的反例，事实上，一个未能通过WL测试的强规则图被称为Shrinkhande图，甚至更早之前就已经被发现了。

Weisfeiler和Lehman的论文已经成为理解图同构性的基础。要从历史的角度来看待他们的工作，我们应该记住，在20世纪60年代，复杂性理论仍处于萌芽状态，算法图理论也只是迈出了第一步。

他们的成果激发了许多后续工作，包括高维图同构测试。在图神经网络领域，Weisfeiler和Lehman已经成为非常著名的人物，证明了他们的图同构测试与消息传递的等价性。

早期的图神经网络

尽管化学家使用类似GNN的算法已经有几十年了，但他们关于分子表征的工作很可能在机器学习界仍然几乎无人知晓。我们发现很难准确地指出图神经网络的概念是什么时候开始出现的：可能是因为大多数早期的工作并没有把图作为「一等公民」，图神经网络在2010年代末才开始实用，也可能是因为这个领域是从几个相邻的研究领域的汇合处出现的。

图神经网络的早期形式至少可以追溯到20世纪90年代，包括Alessandro Sperduti的Labeling RAAM, Christoph Goller和Andreas Küchler的「通过结构的反向传播」，以及数据结构的自适应处理。

虽然这些作品主要关注对「结构」（通常是树或有向无环图）的操作，但其架构中保留的许多不变性让人想起今天更常用的GNNs。

对通用图结构处理的第一次处理，以及「图神经网络」这一术语的创造，发生在2000年以后，由Marco Gori和Franco Scarselli领导的锡耶纳大学团队提出了第一个GNN。他们依靠递归机制，要求神经网络参数指定收缩映射，从而通过搜索固定点来计算节点表征，这本身就需要一种特殊形式的反向传播，而且完全不依赖节点特征。

上述所有问题都被Yujia Li的Gated GNN（GGNN）模型所纠正，包括许多现代RNN的机制，如门控机制和通过时间的反向传播。

Alessio Micheli在同一时期提出的图的神经网络（NN4G）[37]使用了前馈而非递归的架构，事实上更类似于现代的GNNs。

另一类重要的图神经网络，通常被称之为谱（spectral），是由Joan Bruna和合作者利用图傅里叶变换的概念而产生的。这种构造的根源在于信号处理和计算谐波分析，在2000年代末和2010年代初，处理非欧几里得信号已经成为新趋势。

来自Pierre Vandergheynst和José Moura小组的有影响力的论文普及了图信号处理（GSP）的概念和基于图邻接和拉普拉斯矩阵特征向量的傅里叶变换的概括。

Michaël Defferrard和Thomas Kipf和Max Welling的图卷积神经网络依赖于频谱滤波器，是该领域中被引用最多的。

回归化学原点

有点讽刺的是，现代GNN被David Duvenaud作为手工制作的摩根分子指纹的替代品，以及Justin Gilmer以相当于Weisfeiler-Lehman测试的消息传递神经网络的形式，成功地重新引入了它们所起源的化学领域，五十年后，这个圈子终于又闭环了。

图谱神经网络现在是化学领域的一个标准工具，并且已经在药物发现和设计管道中看到使用。2020年，基于GNN的新型抗生素化合物的发现成为划时代的成果。

DeepMind的AlphaFold 2使用了等值注意（GNN的一种形式，考虑了原子坐标的连续对称性），以解决结构生物学的明珠——蛋白质折叠问题。

1999年，Andrey Lehman在给一位数学家同事的信中说，他很高兴得知Weisfeiler-Leman被人所知，并且仍然能够吸引人们的研究兴趣。

他没有活着看到基于他五十年前的工作GNNs的崛起，George Vlăduţ也没有看到他的想法的实现，其中许多想法在他的一生中仍然停留在纸上。

我们相信，他们一定会为站在这个新的激动人心的领域的源头而感到自豪。