图同构下等变,计算高效,韦灵思团队提出\"自然图网络\"消息传递方法

近日，韦灵思团队的一项研究通过研究图的局部对称性，提出了一种新的算法。该算法在不同的边上使用不同的核，从而使网络在局部与全局的图同构体上是等变的，也更易于表达。

通常来说，常规神经消息传递算法在消息排列下是不变的，因此会忘记信息流如何在网络中传递。

近日，阿姆斯特丹大学 ML 教授、高通技术副总裁韦灵思（Max Welling）团队通过研究图的局部对称性，提出了一种通用性更强的算法。该算法在不同的边上使用不同的核，从而使得网络在局部图和全局图同构上呈现等变化，也因而更易于表达。

论文地址：https://arxiv.org/abs/2007.08349v1

具体而言，研究者使用了初级范畴论，将许多显式等变神经网络形式化为自然图网络（Natural Graph Network, NGN），并表明它们的核正是两个函子（functor）之间的自然转换。

他们还提供了一个自然网络的图实例，该网络使用等变消息网络参数化，在多个基准上实现了良好的性能。

接下来我们来看这篇论文的具体内容。

自然图网络

在图上构建神经网络有一种完全不同的策略，即使用图卷积神经网络或消息传递网络（Kipf 和 Welling, 2016；Gilmer 等人, 2017）。研究者将这类方法称为局部图网络（local graph network, LIGN）。

以最简单的形式，这些每个节点上具有特征 v_p 的转换图信号 v，使用单个共享线性变换 W 在图的边上传递消息，如下公式 2 所示：

其中 E 是图的边集。这类卷积架构通常比全局方法具有更高的计算效率，这是因为计算线性变换的计算成本与边的数量呈线性比例关系。

为了克服现有消息传递网络的局限性，同时又保持更高的计算效率，研究者提出了一种新型的消息传递网络，其中的权重是由图结构决定的。

也就是说，研究者对公式 2 做了改进，得到以下公式 3：

其中线性核在每个图每条边上都是不同的。显然，并非所有此类核都会导致等变网络。接下来研究者详细介绍了如何定义核空间。

全局和局部图对称性

研究者用整数数组表示图 G 中的节点 N_G，即

，然后图中的边用整数对表示，边的集合是ε(G)，则边(p,q)∈ε(G)。

如果图是带有 p→q 这样箭头符号的有向图，那么图 G 和 G’是相似或同构的。换句话说，图同构将节点映射到节点，边映射到边。一种特殊的同构是自同构，只是节点的排列顺序有所变化，边集保持不变。根据定义，一个组中的自同构，称为自同构组。

特征

为了使等变神经网络具有可表达的核，必须将节点 p 处的特征向量 v_p 进行变换，因为节点 p 通过某种全局对称性映射到 p’，而不是像固定消息传递网络中那样保持不变。研究者重新定义了特征向量在局部节点对称性下的变换规则。

局部等变性

边 (p,q) 上的核是 p 点的向量空间 V_p 到 q 点的向量空间 V_q 的映射。核的局部等变性意味着，如果有局部同构的边的空集

，则这样做和以下两种情况的结果一样：

将信号从 p 传递到 p’，然后再申请内核 K^(G’)_p’q’；

先申请内核 K^G_pq，然后将 q 转换成 q’。

具体如下图 6 所示：

因此需要以下公式 4：

图神经网络的消息参数化

等变性只需要在具有同构邻域的边之间共享权重，因此在定理中，我们可以将分类参数用于每个同构类的边邻域，以参数化等变核的空间。

实际上，像社交图（social graph）这类图的异构性很强，很少有边是同构的，并且很少需要共享权重，因而学习和泛化也是很困难的。

这一点可以通过以下方式解决：将 p 到 q 的消息

重新解释为函数

，其中 G_pq 是边邻域，v_p 是 p 点的特征值，在 v_p 中可能被泛化为非线性的，K 是基于消息网络的神经网络。

下图 7 所示为作为图卷积的消息传递过程：

范畴论

全局对称性的等变约束，比如机器学习中广泛使用的公式 1 最近已经被扩展到局部对称性或规范对称性中。

但是，这些形式不包括图的动态局部对称性，并且需要一种通用性更强的语言。

基于此，研究者使用了范畴论，该理论最初是从代数拓扑发展而来的，近来也被用作更多问题的建模工具。范畴论的结构为建立等变消息传递网络（称为自然网络）提供了一个良好的框架，研究者称为「自然网络（Natural Network）」。

实验

二十面体（Icosahedral）的 MNIST

为了在实验中验证该方法与全局对称的等变性，并增强在不变消息传递网络（GCN）上的可表达性，研究者对投影到二十面体的 MNIST 进行了分类。

下表 1 第一列显示了在一个固定（fixed）投影上进行训练和测试的准确率。在第二列中，研究者在通过随机二十面体对称性变换的投影上测试了相同的模型。

结果表明，NGN 的性能优于 GCN，并且准确率相等表明该模型是完全等变的。

图分类

在 Yanardag 和 Vishwanathan 于 2015 年提出的 8 个标准图分类基准集上（包括 5 个生物学数据集和 3 个社交图），研究者使用 GCN 消息参数化评估了该模型。