提出基于边和三角形的消息传递框架，显著提升GNN表达能力且保持高效。
Message Passing on the Edge: Towards Scalable and Expressive GNNs
- 在边和三角形上进行消息传递，突破传统顶点传播局限
- 理论证明比1WL更强大，且计算复杂度接近线性
- 实验显示效率高、通用性强，适合大规模图学习任务
图神经网络（GNN）广泛用于图学习，多数架构通过顶点间传递消息。本文转向边上的消息传递，提出基于边的1-维沃尔德测试（EB-1WL）及对应架构EB-GNN。EB-GNN受Chiba和Nishizeki三角计数算法启发，在边和三角形上进行消息传递。理论层面，我们证明EB-1WL远比1WL更具表达力，给出了其在一阶逻辑中的完整刻画，并通过同态计数实现区分性结果。据我们所知，EB-GNN是现有文献中表达力最强的边基消息传递GNN。计算方面，尽管表达力强，但其时间与内存开销在实际图学习任务中接近线性。实验表明，EB-GNN作为通用架构，显著优于简单MPNN，且在计算成本更低的前提下，仍可媲美特定任务的前沿GNN模型。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attention to GNNs that perform message passing on edges and introduce EB-1WL, an edge-based color-refinement test, and a corresponding architecture, EB-GNN. Our EB-GNN architecture is inspired by the classic triangle-counting algorithm of Chiba and Nishizeki and passes messages along edges and triangles. Our contributions are as follows: (1) Theoretically, we show that EB-1WL is significantly more expressive than 1WL. We provide a complete logical characterization of EB-1WL in first-order logic, along with distinguishability results via homomorphism counting. To the best of our knowledge, EB-GNN has the strongest theoretical expressivity guarantees among edge-based message-passing GNNs in the literature. (2) Unlike many GNN architectures that are more expressive than 1WL, we prove that EB-1WL and EB-GNN admit near-linear time and memory usage on practical graph learning workloads. (3) We show in experiments that EB-GNN is a highly efficient general-purpose architecture: it substantially outperforms simple MPNNs and remains competitive with task-specialized state-of-the-art GNNs at substantially lower computational cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。