Recurrent Graph Neural Networks with Set-Based Aggregation
TL;DR
This work studies recurrent GNNs with set-based aggregation and identifies sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks, yielding an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties.
Abstract
Recurrent GNNs iterate message passing to convergence, and their logical characterizations to date rely on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. We study recurrent GNNs with set-based aggregation and identify sufficient conditions checkable from the weights for networks to compile into formulas and formulas into networks. The main result is an effective, two-directional equivalence between a class of networks and the Boolean closure of reachability and safety properties, the fragment B$\Sigma^{\circ}_1$ of the modal $\mu$-calculus. The fragment is not an artifact: it is the exact expressive level of stabilization over finite vocabulary, which supports fixed points of a single polarity and Boolean combinations thereof, but not the composition of fixed points of opposite polarities. The correspondence needs no counting logic, no external halting signal, and no non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations for networks meeting the conditions.
