Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes the expressiveness of three variants of Recurrent Graph Neural Networks (RGNNs): converging, output-converging, and halting RGNNs. It establishes that converging RGNNs are equally expressive as graded-bisimulation-invariant halting RGNNs over undirected graphs, while output-converging RGNNs are at least as expressive. The key technical contribution is a "traffic-light" protocol that enables vertices in converging RGNNs to coordinate halting decisions despite local asynchrony, thereby simulating halting RGNNs.
RGNNs that provably converge are just as expressive as those that can halt at any time, settling an open question about the trade-off between expressiveness and convergence guarantees.
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.