提出可识别有限环图的子图GNN，突破传统GNN表达力瓶颈。
On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles
- 通过聚合距离k内的子图结构信息增强表达能力
- 理论证明在无长于2k+1环的图上可逼近任意置换不变函数
- 实验验证了聚合距离与环长限制的理论关系
图神经网络（GNN）广泛应用于图相关任务，但其分离能力等价于Weisfeiler-Lehman（WL）测试，无法区分所有非同构图，严重限制表达力。本文研究了$ k $-跳子图GNN，该模型聚合距离不超过$ k $的邻居信息并引入子图结构。在合理假设下，证明$ k $-跳子图GNN可在任意误差容限内逼近所有无长度大于$ 2k+1 $环的图上的置换不变/等变连续函数。同时，也扩展至不包含子图结构的$ k $-跳GNN。在经典基准和新架构上的数值实验验证了信息聚合距离与环大小之间的理论关系。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) have been widely used in graph-related contexts. It is known that the separation power of GNNs is equivalent to that of the Weisfeiler-Lehman (WL) test; hence, GNNs are imperfect at identifying all non-isomorphic graphs, which severely limits their expressive power. This work investigates $k$-hop subgraph GNNs that aggregate information from neighbors with distances up to $k$ and incorporate the subgraph structure. We prove that under appropriate assumptions, the $k$-hop subgraph GNNs can approximate any permutation-invariant/equivariant continuous function over graphs without cycles of length greater than $2k+1$ within any error tolerance. We also provide an extension to $k$-hop GNNs without incorporating the subgraph structure. Our numerical experiments on established benchmarks and novel architectures validate our theory on the relationship between the information aggregation distance and the cycle size.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。