arXiv:2604.25551cs.LGcs.AI2026-04

比较了循环图神经网络的三种停止机制,揭示其表达能力差异。

On Halting vs Converging in Recurrent Graph Neural Networks

  • 提出三种停止策略:全局收敛、输出收敛与逐顶点停机。
  • 证明收敛型RGNN可表达μGML逻辑,与停机型等价。
  • 设计交通灯协议解决异步停机带来的同步难题,适合理论研究者。

循环图神经网络(RGNN)通过迭代消息传递直到满足停止条件来扩展标准GNN。本文研究三类模型:要求所有顶点表示稳定的收敛型RGNN;仅要求输出分类稳定的输出收敛型RGNN;以及由每个顶点独立判断是否停机的停机型RGNN。在无向图上,收敛型RGNN与分级双仿真不变的停机型RGNN表达力相当,输出收敛型至少具有相同表达力。结合先前关于停机型RGNN的结果,表明收敛型RGNN恰好能表达单阶二阶逻辑(MSO)中的分级模态μ-演算(μGML),输出收敛型至少可表达μGML。这些结论在使用ReLU网络与求和聚合时依然成立。主要技术挑战在于用收敛型模拟停机型:缺乏全局停机判断时,顶点可能异步停机导致不同步。为此提出‘交通灯’协议,实现顶点在异步情况下的协调。结果回答了Bollen等(2025)提出的开放问题,并证明Pflueger等(2024)的RGNN模型在保证收敛时仍保有完整μGML表达力。

原文摘要 · Abstract (English)

Recurrent Graph Neural Networks (RGNNs) extend standard GNNs by iterating message-passing until some stopping condition is met. Various RGNN models have been proposed in the literature. In this paper, we study three such models: converging RGNNs, where all vertex representations must stabilise; output-converging RGNNs, where only the output classifications must stabilise; and halting RGNNs, where a per-vertex halting classifier determines when to stop. We establish expressiveness relationships between these models: over undirected graphs, converging RGNNs are equally expressive as graded-bisimulation-invariant halting RGNNs, while output-converging RGNNs are at least as expressive. Combined with prior results on halting RGNNs, this shows that, relative to the classifiers expressible in monadic second-order logic (MSO), converging RGNNs express exactly the graded modal $μ$-calculus ($μ$GML), and output-converging RGNNs express at least $μ$GML. These results hold even when restricting to ReLU networks with sum aggregation. The main technical challenge is simulating halting RGNNs by converging ones: without a global halting classifier, vertices may locally decide to halt at different times, causing desynchronisation. We develop a "traffic-light" protocol that enables vertices to coordinate despite this asynchrony. Our results answer an open question from Bollen et al. (2025) and show that the RGNN model of Pflueger et al. (2024) retains full $μ$GML expressiveness even when convergence is guaranteed.

图神经网络表达能力逻辑推理收敛性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。