ICML 2024丨多轨图卷积网络：解决过平滑与过碾压的新思路

图神经网络（Graph Neural Networks）是强大的图（关系与交互系统）分析工具，已成功应用在推荐系统、金融风控、知识工程、分子动力学模拟、芯片设计等诸多领域。绝大多数GNNs利用消息传递（Message Passing）框架实现拓扑感知及信息融合，该框架的核心是消息聚合与转换模块。然而，相较于计算机视觉与自然语言处理领域的大模型，当前GNNs模型层数较浅，未能充分发掘出模型的表达潜力。

过平滑（Oversmoothing）和过碾压（Oversquashing）问题使得难以通过堆叠多层的方式构建深层的GNNs。过平滑是指随着消息聚合次数的增加，节点表示变得无法相互区分；过碾压是指在来自远端节点的信息被过度压缩在有限长度的表示向量中，这阻碍了对图中长程依赖关系的捕获。

现有解决过平滑与过碾压的工作大多基于以下3类策略。（1）图重写（Graph rewiring）策略通过删边[1][2]或增边[3][4]的方式优化图的拓扑结构。Graph transformer模型也可以看做是一种基于attention的增边方式。（2）正则项策略通过约束节点表示[5]或者信息流[6]的方式，避免上述问题。（3）残差链接对解决平滑和过碾压也有不错的效果[7]。尽管已有许多努力，该问题尚未被很好解决。

西安交通大学网络空间安全学院的研究团队近期提出了一种新颖的多轨道消息传递方案（Multi-Track Message Passing，MTMP），能有效解决过平滑和过碾压问题。该工作被机器学习顶级学术会议ICML 2024录用并入选亮点论文（Spotlight Paper）。论文题目是“Multi-Track Message Passing: Tackling Oversmoothing and Oversquashing in Graph Learning via Preventing Heterophily Mixing”。该工作的主要贡献包括，

1. 提出了一种新颖的多轨道消息传递方案MTMP，通过避免异质混合（Heterophily Mixing）有效解决了过度平滑和过碾压问题。

2. 从图学习和半监督学习的角度阐明了MTMP设计的合理性；

3. 将MTMP实现为多轨道图卷积网络MTGCN，并在多个基准图数据集上进行了广泛的比较、验证与分析。

此外，MTGCN还成功应用在KDD CUP 2024 Task 2挑战赛并获得铜牌。展示了MTGCN在文本图数据上的强大分析能力。

论文地址（包含代码）：https://openreview.net/forum?id=1sRuv4cnuZ&noteId=EhTT19WQG0

KDD Cup地址：https://www.biendata.xyz/competition/aqa_kdd_2024

核心观点：异质混合导致了过平滑和过碾压，限制了深层GNNs的表达能力

图1 异质性混合导致了过平滑和过碾压

异质混合现象发生在GNN模型的消息聚合中，指的是不同语义的消息混合。异质混合会致使不同类型的信息丢失，造成过平滑和过碾压问题。具体地，如图1中A1所示，在一次L1层的聚合后，节点2和3的表示变得难以区分。而在L2层聚合后，节点1也变得不可区分。如图1中B1所示，由于异质混合，9号节点难以接收到来自远距离同类节点1和2的信息，造成过碾压。

一、多轨道图卷积网络MTGCN架构

该工作的基本思路是：依据消息的类别语义将消息分配在不同轨道中传递与聚合，避免质性混合的发生，保障消息所含语义的纯洁性，从而解决过平滑和过碾压问题。基于该思路，该文提出了多轨道消息传递方案，MTMP，如图2所示。核心步骤主要包括以下3个步骤：

图2 MTGCN核心步骤

步骤一：消息加载。将节点特征加载到相应的轨道上作为初始消息。节点依据其类别语义关联至相应轨道，由节点-轨道关联矩阵F确定。

步骤二：多轨消息传递。在多条轨道上独立进行消息传递和聚合，不断更新消息向量。

步骤三：消息拾取。依据节点-轨道关联矩阵F，节点拾取相应轨道中更新后的消息构建节点表示Z。

MTGCN计算流程

图3 MTGCN计算流程

在MTGCN的计算流程如图3所示。其中节点-轨道关联矩阵F的构建是关键模块，决定了节点与轨道间的关联关系。具体包括，

1.训练辅助模型 ：使用训练集和伪标签训练一个简单的2层GCN得到辅助节点表示

3.利用attention机制计算节点-轨道关联矩阵F

此外，该工作为MTGCN设计了多阶段的训练流程，每个阶段的MTGCN都会使用前一阶段的有用信息来更新辅助模型Ψ、节点-轨道关联矩阵F和轨道原型P，有助于MTGCN跳出局部最优解。

二、为什么多轨道消息传递方案MTMP有效？

MTMP能带来图学习性能提升的主要原因主要有以下3个方面：

1. 防止异质混合：首要且最重要的优势在于避免了异质混合。如前所述，异质混合是过平滑和过碾压的根本原因。MTMP仅允许相同语义消息进行交互，既实现了拓扑感知，同时充分保留了消息的语义信息。

2. 促进长距离信息流：由于过碾压问题，传统消息传递方案无法实现长距离信息传递。MTMP将消息传递与节点表示解耦，使消息能够流经任何节点，不会在任何节点被阻断。

3. 增强分离条件：分离条件（Separation condition）是半监督学习的关键假设之一[8]。实验表明MTMP方案增强了分离条件，表明其可学到更鲁棒的决策边界。

三、实验验证

1.节点分类任务

在基于经典数据划分的半监督节点分类任务中，MTGCN在多个图数据集上表现出优越的性能。特别是多阶段训练策略训练下的MTGCN-s3和MTGCN-s4展现出了最佳性能，展示了MTGCN在多阶段中的自我进化能力。此外，MTGCN在异质图上同样取得了出色的性能。这归功于MTGCN在消息传递中避免了异质混合，捕获了长距离依赖。

2.MTGCN解决过平滑问题

实验表明，MTGCN无论网络深度如何，都能保持稳定的分类准确率。这与传统的图神经网络形成了鲜明对比，后者在层数增加时出现了显著的性能下降。该工作引入了组距离比（Rg）来衡量过平滑程度，较低的Rg表明严重的过平滑。实验表明，MTGCN保持了最优的Rg。

3.MTGCN解决过碾压问题

该工作实验利用合成基准测试Tree-NeighborsMatch [9]评估图神经网络模型处理过碾压问题的能力。如图4所示，该任务的目标是识别根节点的类别，根节点的类别由叶节点确定，该例中根节点的类别是C。树的中间节点全部为噪声节点。

图4 Tree-NeighborsMatch示例

图5 Tree-NeighborsMatch实验结果

如图5所示， MTGCN在这个任务上达到了非常高的准确率，展示有效捕获长距离依赖关系的能力。MTGCN准确率在树超过6层时有轻微下降，可能是由MTGCN的高空间复杂性导致。

AI科技评论长期围绕AI与机器人领域的前沿研究进行盘点和报道，过去数年，我们接收和报道了上千篇报道，覆盖全球各大高校与企业的顶级实验室。如果您有优秀的论文或研究工作想要分享，也欢迎投稿（邮箱：cenfeng@leiphone.com，微信：8019788）或者联系报道。

[1] Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., and Sun, X. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence, 2020.

[2] Yan, Y., Hashemi, M., Swersky, K., Yang, Y., and Koutra, D. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), 2022.

[3] Devriendt, K. and Lambiotte, R. Discrete curvature on graphs from the effective resistance. Journal of Physics: Complexity, 3(2):025008, 2022.

[4] Banerjee, P. K., Karhadkar, K., Wang, Y. G., Alon, U., and Mont´ufar, G. Oversquashing in gnns through the lens of information contraction and graph expansion. In Annual Allerton Conference on Communication, Control, and Computing, 2022.

[5] Zhou, K., Dong, Y., Wang, K., Lee, W. S., Hooi, B., Xu, H., and Feng, J. Understanding and resolving performance degradation in deep graph convolutional networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021.

[6] Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., Markovich, T., and Bronstein, M. M. Graph neural networks as gradient flows. arXiv preprint arXiv:2206.10991, 2022.

[7] Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.

[8] Wei, C., Shen, K., Chen, Y., and Ma, T. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2020.

[9] Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021

更多内容，点击下方关注：