WWW 2023 | 自适应长程信息建模的图神经网络
基本信息
收录会议：
论文地址：
代码链接：
合作机会：
引言
图分类任务有大量的应用场景，比如图 1 中所示的化学/蛋白质分子性质预测，社交网络分析，文档分类等。图神经网络（Graph Neural Network, GNN）已成为目前任务的 SOTA 方案。
▲ 图1：图分类的应用场景示例
捕获远距离节点的信息交互，即长程信息依赖（Long-Range Dependency）对图分类任务的学习至为重要 [1,2]。纵观现有的技术方案，基于堆叠的图神经网络（stacking-based GNN）通过加深模型来扩大节点感受野，进而获取更远端的节点的信息。然而考虑到过平滑（over-smoothing）问题，两至三个聚合操作是常用的配置 [7,8]，这限制了模型对于长程信息的获取。
我们在理论和实验上验证了过平滑对图分类任务的影响相比较于节点分类任务更小，并基于堆叠 GNN 提出了一种用于捕获长程信息依赖的自动化图神经网络设计方案 LRGNN（Long-Range Graph Neural Network）。
本文点明了捕获长程信息依赖过程中的两个要素，即足够深的 GNN 模型和自适应的跳跃连接设计（skip-connection scheme）。基于这两个关键点，我们将模型深度和跳跃连接整合为层间连接的方式，基于神经网络结构搜索（Neural Architecture Search，NAS）的方法来设计 GNN。基于此，设计出来的GNN具有自适应的深度和跳跃连接，可以自适应的捕获图中的长程信息依赖。
现有图分类解决方案中，池化操作（pooling operation）可以利用新增的边来加快图上信息传播进而加速长程信息提取，比如 DiffPool [3]；整合高阶邻居（higher-order neighbors）信息可以直接获取图中的远距离节点间的交互信息，比如基于 virtual node 的方案 [4]，全连接图（fully connected graph）的 [5]，和基于 Global-attention 的方案 [6]。
但是这类方案会修改图结构， 造成信息丢失和模型判别能力的下降（参见论文附录A.4）。和此类方案相比，LRGNN 这种基于堆叠 GNN 的方案能够更好的保有图中的结构信息。
核心思想
本文拟用堆叠的 GNN 捕获长程依赖。首先,我们在 PROPOSITION 1 中从理论上证明了 over-smoothing 问题对图分类任务上相较于节点分类任务更小的影响（参见文章附录A.1），验证了堆叠的 GNN 方案的可行性。
其次，GNN 深度和跳跃连接方式会影响对长距离邻居的利用。前者决定着一个节点可以访问的最远距离，而后者关系着不同范围邻居的信息混合。因此本文在设计堆叠 GNN 时充分考虑了这两个需求，以有效捕获长程依赖。
3.1 足够深的堆叠模型
深层 GNN 可以结合来自更远邻居的交互作用来提升模型的表达力。如图 2 所示，对于同分异构体分子，两层的堆叠 GNN 无法区分两个图，因为它在两个分子图中得到了相同的计算图，并且基于此将获得相同的图表征。但是对于四层堆叠 GNN 而言，G2 中节点 2 计算图同时包含 S1 和 S3 计算图，而在 G1 中无法实现，因此四层 GNN 可以区分这两个图。
结合 1-WL 测试，深层 GNN 比浅层 GNN 更具表现力（PROPOSITION 2），因此，我们需要足够深的模型来捕获图分类中的长距离依赖关系。
▲ 图2：（a）分子同分异构体。（b）基于两层堆叠 GNN 的节点计算图展示。所有节点的计算图共有四种类型，两个分子具有相同的计算图分布。（c）基于四层堆叠 GNN 的 G2 节点 2 的计算图展示。
3.2 自动设计的跳跃连接
基于 PROPOSITION 2，不同的图对在 1-WL 检验中可能有不同的模型深度，因此在处理不同图时，仅使用一种变体与远距离邻居合并是不合理的。在 GNN 中设计跳跃连接方案可以弥补这种缺陷，因为不同范围邻居提取的信息可以通过跳跃连接融合，在此基础上可以丰富提取的信息。
如图 3 中所示，我们对 GNN 中不同的跳跃连接设计做了对比，我们观察到：（a）总体而言，越深的 GNN 性能越好，这说明了足够的网络层数在图分类任务中的重要性；（b）不同的跳跃连接方案在每个数据集有不同的性质和排名。因此，有必要针对数据进行特定的跳跃连接设计。
▲ 图3: 六种不同的GNN模型在三个不同的数据集上表现各异
方案设计
通过设计层间连接方案，可以统一模型深度和跳跃连接方案两类需求，层间连接分别对应于连续层间连接和不连续层间连接。本文采用 NAS 技术设计 GNN 的层间连接，在此基础上自适应地获得 GNN 深度和跳跃连接方案。
4.1 基于新框架构建的搜索空间（search space）
4.2 搜索算法（search algorithm）
本文采用了 NAS 中常用的可微搜索算法（differentiable search algorithm），采用 Gumbel-Softmax 来使搜索空间变得松弛，优化过程详见文章附录 A.5。训练完成后，通过保留权重最大的操作来获取搜索到的 GNN。
实验结果
5.1 整体实验效果
如图5所示，方案 LRGNN 和其他 baseline 对比具有更高的排名，这证明了通过设计 GNN 中的层间连接以适应性地利用长程依赖关系的 LRGNN 方法的有效性。此外，对于在这些数据集上取得最佳结果的方法（用灰色突出显示的结果），我们观察到这些方法中的模型深度非常接近于图半径（直径/2）。考虑到不同数据集的分布差异，这一观察结果凸显了 GNN 中足够的模型深度的重要性。
▲ 图5：实验效果对比。背景色表示每个数据集中最好的结果，下划线表示当前分组中最好的结果。排名前三的方案高亮显示。BICJ 表示方案的不同变种，详见论文章节 4.3。表中“[L5]”表示模型最终的有效深度为 5，以此类推。
5.2 基于堆叠的GNN的可行性验证
本文使用平均节点对距离来进行衡量 over-smoothing 的程度，即 。如图 6 所示，随着模型加深，在两个数据集上观察到的平均特征距离值越来越低，表明两类任务中都存在过平滑问题。然而，在 NC1 数据集上模型性能有明显的上升趋势，而在 Cora 数据集上则相反。因此与节点分类任务相比，过平滑问题对图分类任务的影响较小，通过堆叠足够的层数来获得长程依赖关系是一种可行的方法。
5.3 自适应层间连接设计的必要性验证
本文在两个真实的数据集上对层间连接进行了实证评估。如图 7 所示，具有不同跳跃连接方案的 GNN 在每个数据集上具有不同的性能，这说明不同的数据集对不同的跳跃连接和模型深度有不同的偏好， 这些结果证明了自适应的层间连接设计的必要性。
未来工作
本文证明了过平滑问题对图分类任务的影响较小，以此来唤醒图分类任务中基于堆叠的 GNN 的重要性，并提出了一种新的方法 LRGNN，通过自动设计其层间连接来实现模型深度和跳跃连接的自适应，进而自动化捕获图分类任务中的长程依赖关系。
在未来的工作中，我们会进一步讨论图中基于堆叠的 GNN 和基于池化（pooling）的 GNN 方案在长程信息获取过程中的对比，并研究不同任务下图中长程信息获取的必要性和技术手段的选择合理性。
参考文献
[1] Long Range Graph Benchmark.
[2] Representing Long-Range Context for Graph Neural Networks with Global Attention. NeurIPS 2021
[3] Hierarchical graph representation learning with differentiable pooling. NeurIPS 2018
[4] Graph clas- sification via deep learning with virtual nodes.
[5] On the bottleneck of graph neural networks and its practical implications. ICLR 2021
[6] Attention is all you need. NeurIPS 2017
[7] How powerful are graph neural networks? ICLR 2019
[8] An end-to-end deep learning architecture for graph classification. AAAI 2018
合作机会
本文探索了NAS在图分类任务中的长程信息获取，除此之外，本组还有以下新工作：
1. Understanding and Simplifying Architecture Search in Spatio-Temporal Graph Neural Networks. Transaction of Machine Learning Research (TMLR). 2023
2. ColdNAS: Search to Modulate for User Cold-Start Recommendation. The Web Conference (WebConf). 2023
3. Neural Architecture Search for GNN-based Graph Classification. ACM Transactions on Information Systems (TOIS). 2023
4. Searching a High Performance Feature Extractor for Text Recognition Network. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). 2022
5. Bilinear Scoring Function Search for Knowledge Graph Learning. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). 2022
6. Designing the topology of graph neural networks: A novel feature fusion perspective. The Web Conference (WebConf). 2022
7. Searching to Sparsify Tensor Decomposition for N-ary relational data. The Web Conference (WebConf). 2021
8. Search to aggregate neighborhood for graph neural network. International Conference on Data Engineering (ICDE). 2021
9. DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). 2021
10. Pooling architecture search for graph classification. ACM International Conference on Information and Knowledge Management (CIKM). 2021
11. TabGNN: Multiplex Graph Neural Network for Tabular Data Prediction. 4th Workshop on Deep Learning Practice and Theory for High-Dimensional Sparse and Imbalanced Data with KDD (KDD-DLP). 2021
12. AutoSF: Searching scoring functions for knowledge graph embedding. International Conference on Data Engineering (ICDE) 2020.
13. Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding. 34th Conference on Neural Information Processing Systems (NeurIPS). 2020
14. Simplifying Architecture Search for Graph Neural Network. COMBINING SYMBOLIC AND SUB-SYMBOLIC METHODS AND THEIR APPLICATIONS (CIKM-CSSA). 2020
欢迎对以上论文感兴趣的同学们联系我们。欢迎邮件以下合作导师。
姚权铭，清华大学电子工程系，助理教授（博士生导师）：于香港科技大学计算机系取得博士学位，之后加入第四范式担任高级科学家，创建和领导公司的机器学习研究组，为国内最早一批从事自动化机器学习和图学习的研究团队。已在发表 CCF-A 类会议和期刊论文 70 余篇，Google Scholar 总引用 5800 余次。常任 ICML、NeurIPS 和 ICLR 领域主席（Area Chair）。获得过 Google 全球博士奖研金、香港科技大学优秀博士论文奖、吴文俊人工智能学会优秀青年奖、福布斯 30Under30 精英榜（中国区）、香港科学会优秀青年科学家、全球华人 Top-100 人工智能青年学者。
科研助理、博士后招聘：
邮箱：qyaoaa@tsinghua.edu.cn
主页：https://lars-group.github.io/
赵欢，第四范式科学技术部，资深研究员：负责自动化图神经网络（AutoGraph）相关方向的研究与落地工作，过去 4 年围绕 AutoGraph 方向发表 10+ 篇学术论文以及在 KDD/AAAI/IJCAI 等国际顶会上做讲习报告，并在国际图学习基准 OGB 的图分类任务 2 个赛道拿到冠军。除此之外，他推动图学习算法在推荐系统，生物医学，事件图谱，智能制造等业务方向的落地。
实习生招聘：
邮箱：zhaohuan@4paradigm.com
主页：https://hzhaoaf.github.io/
张永祺，第四范式科学技术部，资深研究员：负责自动化知识图谱（AutoKGE）相关方向的研究工作，以第一作者身份在 TPAMI, VLDB Journal，NeurIPS, WWW, ACL 等人工智能领域顶级会议期刊发表论文近 10 篇，在链接预测、实体对齐等任务基线上达到国际领先水平，取得大规模生物知识图谱预测任务 ogbl-biokg 第一名的成绩，并在药物作用预测、时序事件推理、个性化推荐等任务场景上取得突破。在国际顶级会议 KDD/AAAI/IJCAI 上做 AutoKGE 相关讲习报告，并在国内知名论坛 DataFun、将门 TechBeat 上多次做技术分享。
实习生招聘：
邮箱：zhangyongqi@4paradigm.com
主页：https://yzhangee.github.io/
更多阅读
#投 稿 通 道#
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。
📝 稿件基本要求：
• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注
• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题
• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算
📬 投稿通道：
• 投稿邮箱：hr@paperweekly.site
• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿
△长按添加PaperWeekly小编
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧