拓展器图传播

来自今天的爱可可AI前沿推介

[LG] Expander Graph Propagation

A Deac, M Lackenby, P Veličković [Mila & University of Oxford & DeepMind]

拓展器图传播

要点：
1. GNN架构需要线性时间和空间复杂度并避免病态行为；
2. 提出一种基于在扩展器图上传播信息的方法，并进一步提出EGP模型，以解决上述问题；
3. 无瓶颈可扩展的消息传递需要负曲率的边。

摘要：
众所周知，在全图分类或回归任务中部署图神经网络(GNN)是一个挑战：通常需要计算节点特征，这些特征既要考虑其邻域的局部交互，又要考虑图结构的整体上下文。在该空间中漫游的GNN架构需要避免病态行为，如瓶颈和过冲，同时最好有线性的时间和空间复杂性要求。本文提出一种基于在扩展器图上传播信息的优雅方法，提供了一种有效的方法来构建给定大小的扩展器图，并利用该洞察提出了EGP模型。我们表明EGP能够解决上述所有的问题，同时只需要最小的努力来建立，并提供证据证明其在相关数据集和Open Graph Benchmark的基线上的经验效用。重要的是，使用扩展器图作为消息传递的模板，必然会产生负的曲率。虽然从最近关于过冲的相关工作来看，这似乎是反直觉的，但本文从理论上证明，要获得没有瓶颈的可扩展的消息传递，可能需要负弯曲的边缘。

Deploying graph neural networks (GNNs) on whole-graph classification or regression tasks is known to be challenging: it often requires computing node features that are mindful of both local interactions in their neighbourhood and the global context of the graph structure. GNN architectures that navigate this space need to avoid pathological behaviours, such as bottlenecks and oversquashing, while ideally having linear time and space complexity requirements. In this work, we propose an elegant approach based on propagating information over expander graphs. We provide an efficient method for constructing expander graphs of a given size, and use this insight to propose the EGP model. We show that EGP is able to address all of the above concerns, while requiring minimal effort to set up, and provide evidence of its empirical utility on relevant datasets and baselines in the Open Graph Benchmark. Importantly, using expander graphs as a template for message passing necessarily gives rise to negative curvature. While this appears to be counterintuitive in light of recent related work on oversquashing, we theoretically demonstrate that negatively curved edges are likely to be required to obtain scalable message passing without bottlenecks. To the best of our knowledge, this is a previously unstudied result in the context of graph representation learning, and we believe our analysis paves the way to a novel class of scalable methods to counter oversquashing in GNNs.

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

内容中包含的图片若涉及版权问题，请及时与我们联系删除