通过噪声遮掩实现可扩展的深度图神经网络

Yuxuan Liang, Wentao Zhang, Zeang Sheng, Ling Yang, Quanqing Xu, Jiawei Jiang, Yunhai Tong, Bin Cui

论文链接：https://arxiv.org/abs/2412.14602

背景和挑战：

图神经网络 (GNN) 在图表示学习方面取得了巨大成功。但由于训练期间重复特征传播的计算和存储成本很高，因此将其扩展到大型图具有挑战性。

为了解决可扩展性问题，模型简化GNN作为可扩展性能的一个有前途的方向，最近引起了人们的极大兴趣。最具代表性的工作是SGC，并以此衍生一系列模型简化GNN比如SIGN，S2GC, GBP, GAMLP等。

尽管现有的模型简化 GNN 具有较好的可扩展性和预测性能，但它们仍然面临以下两个限制：（1）带有噪声信息的传播；（2）具有高预处理开销的传播。这两个限制阻碍了模型简化 GNN进一步加深。

研究动机：

在本节中，我们将深入分析模型简化 GNN 中存在的两个局限性，然后提供我们的见解来帮助我们设计 RMask 的架构。

图1. 实验观察和见解

（1）带有噪声信息的传播：

我们在Cora数据集上随机选择 10 个节点，并通过 L2 归一化P传播观察每跳的平均权重。

如图1a所示，权重较高的节点经常在较低的跳数内被捕获，而有价值信息的较高跳数的节点表现出相当低的权重。这种现象阻碍了对高跳信息的捕获。

为了进一步解释，我们从目标节点开始进行 2 跳传播。如图1c所示，2跳捕获的信息不仅包括当前跳，还包括2跳冗余信息，由于这些信息在1跳内已经可以捕获，我们将其称为噪声信息。随着传播深度的增加，高跳捕获的节点包含大量低跳噪声信息，难以区分高跳和低跳信息，加剧了过平滑问题。为了进一步研究噪声信息对过平滑的影响，我们增加跳数，并使用SIGN模型测量噪声信息和图平滑度GSL的比例。如图1b所示，随着跳数的增加，GSL呈爆炸式增长，噪声信息也不断增长。7跳后捕获的信息完全是冗余的。

基于此，我们重新实现了带噪声掩蔽的SIGN。如图1d所示，节点不仅可以捕获高跳的有效信息，还可以消除过度平滑问题，如图1e所示。随着跳数的增加，准确率和平滑度趋于平稳。

(2) 具有高预处理开销的传播:

此外，这种传播方法会导致显著的预处理开销。图1f 的上部说明了当前模型简化 GNN 采用的统一预处理过程。首先，预处理的时间复杂度与边的数量线性相关。每一跳都会从所有先前的跳数中捕获大量的图结构信息，从而产生高密集计算开销。其次，这种方法依赖于不同跳跃之间信息的相互依赖性，只能串行执行。与昂贵的预处理开销相比，模型简化 GNN 通常使用简单的模型进行快速训练。由于上述原因，预处理开销构成了端到端训练时间的大部分。如图1f下半部分所示，为了减少预处理的高开销，我们需要一种稀疏和并行的方法来有效地捕获每一跳的重要信息。

方法：

图2. Rmask架构

RMask执行流程：

给定指定的跳跃数和图结构，我们首先根据图结构对每个节点执行带有屏蔽机制的随机游走。然后聚合捕获的图结构信息和特征以获得不同跳跃的结果。

此外，通过这种方式得到的特征传播结果可以直接替代其他模型简化GNN（如 S2GC、GBP、SIGN、GAMLP 等）中的P操作。同时，我们保留了现有模型简化 GNN 在特征组合和模型选择方面的优势。

噪声掩码机制：

噪声掩码机制由两个部分组成：噪声信息识别和邻居节点重要性分配。

第一个组件识别每一跳中的噪声信息，并使用随机游走有效地捕获非冗余的图结构信息。第二个组件为每个邻居节点分配重要性权重，以帮助随机游走捕获更重要的信息。

（1）噪声信息识别:

考虑到噪声的影响，高跳数通常包含来自低跳数的冗余信息。因此，我们需要遍历整个图来识别每一跳的噪声信息。基于对高hop噪声信息的观察，我们使用去噪矩阵来记录噪声信息：

采用去噪矩阵使我们能够在确保低过平滑度级别的同时，从每一跳中提取有用信息。然后，对于每一跳，我们使用随机游走函数（RW）来捕获当前跳的图结构信息，然后结合去噪矩阵从每一跳中提取有用的信息：

其中T是随机游走的次数。通过控制T，我们在准确性和效率之间取得了良好的平衡，使其可以支持大规模图的处理。

（2）邻居节点重要性分配:

为了进一步提升预测精度，我们采用基于相邻节点重要性的偏置随机游走。使用PageRank来获取相邻节点重要性：

其中S是重要性矩阵。通过为图中的每个边分配重要性权重，可以引导随机游动的方向，从而捕获更重要的去噪信息。具体算法如表1所示：

表1. Rmask算法概述

实验效果：

实验主要包含以下四个方面：(1)与最先进的模型简化方法进行端到端比较 ；(2)分析更深层架构的能力 ；(3)分析效率和准确性之间的权衡 ；(4)分析效率。

（1）与最先进的模型简化方法进行端到端比较：如表2所示，集成RMask 后，SIGN、S2GC、GBP 和 GAMLP 在所有六个数据集上均实现了比其各自原始版本更好的性能。

表2. 节点分类预测任务的实验结果

（2）更深层架构的能力：如图3所示，集成Rmask的模型简化方法可以更有效地利用深层信息，从而提高准确性。

图3. 随着跳数增加，性能变化的趋势

（3）分析效率和准确性之间的权衡：如图4（a）所示，使用 RMaska 插件模块可以在效率和准确性之间进行良好的权衡。

（4）效率实验：如图4（b）(c)所示，在所有数据集中，我们的方法成功地减少了端到端训练中预处理开销的比例，并且获得了2.9X以上的提速。

图4. （a）ogbn-product上效率和准确性之间的权衡。（b）时间开销分析。（c）加速分析。

总结：

本文介绍了 RMask，这是一个即插即用的模块，旨在增强现有的模型简化 GNN 在更高速度下探索更深层次的图形结构的能力。作为插件方法， RMask可以与大多数模型简化GNN无缝集成。实验结果表明，RMask有效地提高了模型简化GNN的准确性和效率。

实验室简介

北京大学数据与智能实验室（Data And Intelligence Research Lab at Peking Univeristy，PKU-DAIR实验室）由北京大学计算机学院崔斌教授领导，长期从事数据库系统、大数据管理与分析、人工智能等领域的前沿研究，在理论和技术创新以及系统研发上取得多项成果，已在国际顶级学术会议和期刊发表学术论文100余篇，发布多个开源项目。课题组同学曾数十次获得包括CCF优博、ACM中国优博、北大优博、微软学者、苹果奖学金、谷歌奖学金等荣誉。PKU-DAIR实验室持续与工业界展开卓有成效的合作，与腾讯、阿里巴巴、苹果、微软、百度、快手、中兴通讯等多家知名企业开展项目合作和前沿探索，解决实际问题，进行科研成果的转化落地。