江苏龙网

  1. 首页 > 人文 > >

技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验


你是否觉得在图上进行深度学习是一堆有时可以起作用的启发式方法 ， 但是没人知道为什么吗？在本文中 ， 我将讨论图同构问题 ， 用于图同构测试的Weisfeiler-Lehman启发式方法 ， 以及如何将其用于分析图神经网络的表达能力 。
技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验
本文插图
传统前馈网络（多层感知器）是通用近似器：它们可以将任何平滑函数近似为任何所需的精度 。 对于最近出现的图神经网络 ， 人们对表示特性的了解较少 。 在实验中经常会发现 ， 图神经网络在某些数据集上表现出色 ， 而在其他数据集上却表现令人失望 。 为了了解这种行为的根源 ， 必须回答一个问题：图神经网络的功能有多强大？
挑战之一是 ， 应用程序中遇到的图形是连续和离散结构（分别是节点和边缘特征以及连通性）的组合 ， 因此可以用不同的方式提出这个问题 。 一种可能的表述是图神经网络是否可以区分不同类型的图结构 。 这是图论中的经典问题 ， 称为图同构问题 ， 旨在确定两个图在拓扑上是否等效 。 两个同构图具有相同的连通性 ， 并且仅因其节点的排列而不同 。
令人惊讶的是 ， 图同构问题的确切复杂度类别是未知的 。 不知道它在多项式时间内是可解的 ， 也不是NP完全的 ， 有时归因于特殊的“ GI类” 。
Weisfeiler-Lehman检验 。
【技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验】1968年Boris Weisfeiler和 Andrey Lehman的开创性论文提出了一种有效的启发式方法 ， 现在称为Weisfeiler-Lehman（WL）测试 ， 最初被认为是图同构问题的多项式时间解 。 一年后发现了一个反例；但是 ， 从概率的角度来看 ， WL测试似乎适用于几乎所有图形 。
技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验
本文插图
在两个同构图上执行Weisfeiler-Lehman检验的示例 。 弯括号表示多组 。 着色不变后 ， 算法停止并产生输出（颜色的直方图） 。 两个图的相等输出表明它们可能是同构的 。
WL测试基于迭代图形重新着色（图形理论中的"颜色"是指离散的节点标签） ， 并从所有颜色相同的节点开始 。 在每个步骤中 ， 该算法将节点及其邻域的颜色汇总为多集 ， 并将汇总的颜色多集散列为唯一的新颜色 。 该算法在达到稳定的着色时停止 。 如果此时两个图的颜色不同 ， 则认为这些图是非同构的 。 但是 ， 如果颜色相同 ， 则这些图可能（但不一定）是同构的 。 换句话说 ， WL测试是图同构的必要但不充分的条件 。
存在一些非同构图 ， 其中WL测试会产生相同的着色 ， 因此将它们视为"可能同构" 。 据说在这种情况下测试失败 。 下图显示了一个这样的示例：
技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验
本文插图
从其产生的相同颜色可以明显看出 ， 两个WL图同构测试失败的非同构图 。 在化学上 ， 这些图代表两种不同化合物的分子结构 ， 十氢化萘（左）和双环戊基（右） 。
图同构网络Keyulu Xu 和Christopher Morris 注意到 WL测试与通过神经网络的图消息传递图形非常相似 ， 这是进行卷积的一种方法 。
就像对图形的操作一样 。 在消息传递层中 ， 通过汇总邻居的特征来更新每个节点的特征 。 聚合和更新操作的选择至关重要：只有多集内射函数使其等效于WL算法 。 有些文献中使用的一些流行的聚合器选择（例如 ， 最大值或均值）实际上不如WL强大 ， 并且无法区分非常简单的图结构：
技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验
本文插图
无法通过最大值进行区分但可以通过均值聚合器（第一和第二）进行区分 ， 以及既不能通过最大值 ， 也不能通过均值（第一和第三）进行区分的图结构示例 。 原因是从黑节点的邻居以这种方式聚合的特征将是相同的 。


推荐阅读


上一篇：互联网「庆余年先发制人」被判违约：模式本身是对的，吃相不能太难看

下一篇：茂哥|梦幻西游：茂哥暑期物价走势预测 教师节海马和百岁会涨价