Halting Recurrent GNNs and the Graded mu-Calculus

Jeroen Bollen, Jan Van den Bussche, Stijn Vansummeren, Jonni Virtema2025 · DOI

TL;DR

Recurrent Graph Neural Networks (GNNs) often lack a formal way to know when to stop iterating without being told the graph's size upfront. This paper introduces a "halting" mechanism for recurrent GNNs and proves that these models can express any node classification task definable in the graded $\mu$-calculus—a powerful logic for describing recursive properties in graphs.

What Problem Does This Paper Address?

Standard GNNs usually operate with a fixed number of layers (fixed depth), which limits their ability to capture long-range dependencies or recursive structures. Recurrent GNNs solve this by applying the same layer repeatedly, but they face a major hurdle: termination.

Most current recurrent GNNs either assume the model is told the graph size ($N$) so it knows how many times to loop, or they simply run indefinitely without a guarantee of reaching a stable answer. This is a problem for both theoretical completeness and practical deployment. The authors set out to bridge the gap between deep learning and formal logic by creating a GNN that can decide for itself when it has finished computing a recursive property, all without knowing the total number of nodes in the graph.

Methods

The authors approach this through the lens of formal logic, specifically the graded $\mu$-calculus ($\mu$GML). This logic allows for "graded" counting (e.g., "this node has at least $k$ neighbors where property $X$ holds") and recursion (using least and greatest fixpoints).

To prove that a GNN can handle this logic, they developed several novel components:

  1. Halting Recurrent GNNs: A model architecture that includes a boolean-valued "halting function" and a "readout function." The GNN iterates until every node's halting bit is true.
  2. Approximate Semantics: They created a way to approximate the $\mu$-calculus that iterates fixpoints a specific number of times ($k$) and defined a notion of "stability." If an approximation is stable, it is guaranteed to match the true logical result.
  3. The Counting Algorithm: They designed a model-checking algorithm that tracks these approximations and their stability. Crucially, this algorithm is "oblivious" to graph size.
  4. GNN Simulation: Finally, they proved that a "simple" GNN—using standard ReLU activation functions and sum-based aggregation—can simulate this counting algorithm step-by-step.

Datasets

This is a theoretical paper focused on formal proofs of expressivity. Consequently, no empirical datasets or benchmarks were used for training or evaluation. The "results" are mathematical theorems rather than accuracy scores on specific datasets.

Key Insights and Ideas

  • Stability over Size: The most significant "aha moment" is that a GNN doesn't need to know the graph size $N$ to compute recursive properties. It only needs to detect stability—the point at which further iterations no longer change the result.
  • Polynomial Halting: The authors prove that their constructed GNN will reach this global halting condition in a number of iterations that is polynomial relative to the graph size.
  • The Power of "Simple" GNNs: The proof shows that you don't need complex, custom architectures to capture recursive logic. Standard "plain-vanilla" GNNs (ReLU + Sum) are sufficient, provided they have the right halting mechanism.
  • Approximate Semantics: The new semantics for $\mu$GML developed here are of independent interest to logicians, as they provide a way to evaluate recursive formulas without knowing the bounds of the structure beforehand.

Key Results

  • Theorem 5.1 (The Main Result): Every node classifier definable by a $\mu$GML sentence is also definable by a simple halting recurrent GNN.
  • Invariance: The authors established that these halting GNNs are invariant under "total surjective graded bisimulation." In plain English, this means the GNN respects the fundamental structural symmetries of the graph.
  • Undecidability of General Halting: While the authors provide a way to construct a halting GNN for a specific logic, they also prove that determining if an arbitrary recurrent GNN will ever halt is undecidable (a classic "Halting Problem" result applied to GNNs).

Limitations and Future Work

  • The Converse Question: While the paper proves that $\mu$GML $\subseteq$ Halting GNNs, it remains an open question whether the reverse is true. Do all halting recurrent GNNs fall within the bounds of $\mu$GML?
  • Convergence vs. Halting: The current model uses a specific halting bit. The authors suggest future research could explore "fully convergent" models where the entire feature vector stabilizes, rather than just a single bit.
  • Infinite Graphs: The proofs currently assume finite graphs. Extending these results to infinite structures (like graphons) is a promising but difficult next step.
  • Practical Training: This paper is a proof of existence (showing a GNN can represent these functions). It does not address how easily these parameters can be learned from data using gradient descent, which remains a challenge for recursive architectures.

Summary updated

Abstract

Graph Neural Networks (GNNs) are a class of machine-learning models that operate on graph-structured data. Their expressive power is intimately related to logics that are invariant under graded bisimilarity. Current proposals for recurrent GNNs either assume that the graph size is given to the model, or suffer from a lack of termination guarantees. In this paper, we propose a halting mechanism for recurrent GNNs. We prove that our halting model can express all node classifiers definable in graded modal mu-calculus, even for the standard GNN variant that is oblivious to the graph size. To prove our main result, we develop a new approximate semantics for graded mu-calculus, which we believe to be of independent interest. We leverage this new semantics into a new model-checking algorithm, called the counting algorithm, which is oblivious to the graph size. In a final step we show that the counting algorithm can be implemented on a halting recurrent GNN.
BibTeX
@misc{bollen2025halting,
  author = {Jeroen Bollen and Jan Van den Bussche and Stijn Vansummeren and Jonni Virtema},
  title = {{Halting Recurrent GNNs and the Graded mu-Calculus}},
  year = {2025},
  doi = {10.24963/kr.2025/18},
}
Figure