「几何深度学习」从古希腊到AlphaFold，「图神经网络」起源于物理与化学(8)
扫一扫
分享文章到微信
扫一扫
关注99科技网微信公众号
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。
99科技网：http://www.99it.com.cn
推荐资讯
