ICLR 2023 | ACMP: 具有引力斥力机制的Allen-Cahn消息传递

科技

2023-02-16 05:02

©PaperWeekly 原创 · 作者 | 王悦琳

单位 | 上海交通大学

研究方向 | 几何深度学习、图神经网络

论文标题：

ACMP: Allen-Cahn Message Passing with Attractive and Repulsive Forces for Graph Neural Networks

论文链接：

https://arxiv.org/abs/2206.05437

今天介绍的论文是接收于 ICLR 2023（spotlight）的论文。此文将粒子系统动力学理论与图神经网络中传统的消息传递机制相结合，在交互粒子系统框架下分析了图神经扩散模型（GRAND [1]）的动力学特点，提出了兼具引力-斥力的消息扩散模型（ACMP）。

在引力-斥力的共同作用下，ACMP 可以避免图神经网络中常见的过度平滑（over-smoothing）问题，保持 Dirichlet 能量的严格正下界，进而加深网络。在恰当的排斥力作用下，ACMP 因可以产生类似于 Allen-Cahn 相变模型的双集簇现象而得名。

背景介绍

1.1 图神经网络中的消息传递

近年来，图形神经网络（Graph neural networks，GNN）以其在图结构数据上强大的学习和表达能力，成为深度学习的一大热点。神经消息传递（message passing）是一种聚合邻接节点信息来更新中心节点信息的范式，因简洁高效而被广泛应用。对于无向图 G 其更新范式如下：

其中，表示结点在第（k-1）层的特征；表示从结点到结点的边特征；表示一个可微、具有 (结点) 置换不变性的函数，和表示可微函数，表示结点的一阶邻域（one-hop neighbors）。该范式是 ACMP 模型依赖的基本框架。

1.2 交互粒子系统

交互粒子系统可以被认为是自然界和人类社会消息递送行为的另一种数学模型。该模型将个体抽象为粒子，将群体中的信息交互抽象为相互作用力，来模拟虫群或人类社会的集体行动。粒子方程有多种构造方式，根据需要，可以设计相应的粒子系统使得演化结果展现多簇或一致性。

这启发文章为图神经网络设计一个基于粒子系统的神经信息传递传播器，将结点特征看做粒子，边特征看做粒子之间的相互作用。而网络中的每个结点都与其邻居进行交互，使得整个网络成为一个系统，该系统的动力学过程构成网络中的信息传递。

1.3 GNN模块面临的问题

过度平滑：

过度平滑（oversmoothing）是近年来 GNN 领域广为关注的问题之一。受过度平滑效应的影响，经典的 GNN 模块如 GCN，GAT 的表现随着网络加深变得不在理想。简单地说，过度平滑是指，在 GNN 模块的多次迭代之后，随着不同结点的接收域变得越来越相似图中所有结点的表示变得非常相似，结点特征变得“过度平滑”，影响认为效果。这造成 GNN 的层数难以加深。

Rusch 等人通过 Dirichlet 能量给出了过度平滑问题的数学刻画 [2]：关于图 G 的Dirichlet 能量定义为

而过度平滑现象来自 Dirichlet 能量随着层数的指数衰减。换言之，随着层数的增加，图的 Dirichlet 能量迅速衰减，最后降低到不足以支撑深层网络学习的地步，不同结点特征无法有效区分。

异质图：

改善异质图上 GNN 模块的表现是另一个人们关注的问题。异质图是指，图中的结点更多地与不同种类的结点建立边连接关系的图。对于一个图数据集，异种结点相连地越多，同种结点相连地越少，就意味着数据集的异质性越强。经典的消息聚合模块正向地接收所有邻居结点的信息（尽管权重可能不同），这暗含一种同质化的倾向，即认为邻居结点会展现更高的相似性。因此，尽管这些模块在同质性强的数据集上表现优异，在异质性强的数据集上却往往表现不佳。

粒子系统背景下的解释：

针对上述问题，文章从交互粒子系统的角度给出了新颖的解释。假设略去激活函数和参数矩阵的作用（就是说，取单位矩阵），仅从动力系统的角度考虑，Chamberlain 等人提出的图神经扩散方程（GRAND [1]）是一个反应动力学特征，且能够概括 GCN，GAT 模型的例子。GRAND 的标量形式可以写作：

这时，如果将结点特征视为单独的粒子，很容易发现特征的演化趋势：若，则的速度方向朝向。也就是说，被吸引。而相似度是一个非负函数，因此，结点间的相似度可以看作和之间的吸引力。这表明图中连通分支中的所有节点特征相互吸引。如果权重矩阵是正随机的，可以证明特征的凸包不会随时间膨胀。若图中只有一个连通分支，则所有特征不断趋同，最后难以区分。

然而，只有吸引力的相互作用机制显然是不完整的。正如消息传播过程不只是采纳整合邻居的意见，有时候，消息传递是伴随着否定和对立的。负面信息在相反层面上具有价值。例如，在二分图的节点分类任务中，由于相邻的节点属于不同的类，可以把相邻消息称之为为负面信息，这种信息同样可以帮助分类。这种作用机制恰好和排斥过程吻合。因此，文章设计了可以同时表现正面信息和负面信息的消息传递网络 ACMP，能够容纳完整的引力-斥力交互作用。

模型架构

ACMP 的模型结构如下图所示：

首先，ACMP 模块的网络更新由一个时间步长的积分方程决定，方程的一步演化，意味着 message passing 的一次更新。ACMP 的动力学方程由两部分组成：刻画相互作用力的引力-斥力机制，和刻画势能作用的势能项。

在引力-斥力结构下，不同种类的特征粒子倾向于相互排斥，而相似的特征粒子倾向于相互吸引。在消息传递的意义下，也就是说，特征信息的同种/异种性质得到增强，从而增强网络的信息处理能力，避免过度平滑问题，灵活适应同质图和异质图这两种不同的数据结构。

势能项的主要作用是防止粒子系统空间的无限膨胀。因为系统中存在排斥力，相互排斥的粒子如果始终保持排斥状态，随着时间推进，粒子直接会不断远离。从网络层面上说，特征向量的值会随着网络的加深不断增大，最后超出需要的范围。因此，引入一个井状的势能场，也就是说，在系统边缘的区域施加一个强位势，在系统中心施加弱位势，对维持系统的稳定方面可以起到积极的作用。

这个势能场的选择，在“井”状轮廓之外，可以是自由的。在文章中，简单起见，采用了双势能井“W”形结构：一方面，两侧的高位势保持了系统的稳定性，另一方面，中间的“W”形低位势在容许交互作用力为主导作用的状态下，对异种粒子的分离起到促进作用。

ACMP 的更新方程如下所示：

这里，表示第 i 个结点的特征向量；表示结点之间的边特征，根据需要，可以选择诸如 GCN 系数，GAT 系数或任何表示结点间相似度的系数。是可学习参数，表示超参数，哈达玛积（Hadamard product）表示所有运算是在 channel-wise 意义下执行的。和用来平衡和调节这两项的作用强度。右边的第一项对应相互作用力，第二项对应势能项，由双井形势能的梯度流得到。