递归图神经网络可达到消息传递理论极限，突破传统GNN表达力瓶颈。
Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit
- 通过循环结构+有限精度参数设计，实现对图算法的精确表达
- 在连通图上，随机初始化后可模拟任意多项式时间图算法
- 首次证明递归GNN能完全匹配颜色精炼算法的表达力边界
我们精确刻画了可计算的递归图神经网络（recurrent GNNs）的表达能力。证明在有限精度参数、求和聚合和ReLU激活函数条件下，递归GNN能够计算所有满足由颜色精炼（Weisfeiler-Leman）算法诱导的消息传递不变性的图算法。尽管已有研究指出图神经网络的表达力受限于该不变性，但本文首次确立递归GNN可实际达到此上限。相比之下，非递归GNN仅以极弱的“非均匀”方式具备类似能力，需为每种图规模配置不同模型。本方法引入的时空开销仅为多项式级。此外，通过引入随机初始化，递归GNN在连通图上可表达任意图算法，任何多项式时间图算法均可在多项式时间内被带随机初始化的递归GNN模拟。
原文摘要 · Abstract (English)
We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggregation, and ReLU activation, can compute any graph algorithm that respects the natural message-passing invariance induced by the Color Refinement (or Weisfeiler-Leman) algorithm. While it is well known that the expressive power of GNNs is limited by this invariance [Morris et al., AAAI 2019; Xu et al., ICLR 2019], we establish that recurrent GNNs can actually match this limit. This is in contrast to non-recurrent GNNs, which have the power of Weisfeiler-Leman only in a very weak, "non-uniform", sense where each graph size requires a different GNN to compute with. Our construction introduces only a polynomial overhead in both time and space. Furthermore, we show that by incorporating random initialization, for connected graphs recurrent GNNs can express all graph algorithms. In particular, any polynomial-time graph algorithm can be emulated on connected graphs in polynomial time by a recurrent GNN with random initialization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。