Recurrent GraphNeural NetworkswithSet-BasedAggregation
Paper proves two-directional equivalence between recurrent GNNs with set-based aggregation and Boolean closure of reachability/safety properties in modal mu-calculus, checkable from weights.
The authors study recurrent graph neural networks with set-based aggregation and identify sufficient conditions, checkable directly from network weights, for compiling networks into logical formulas and formulas into networks. They establish an effective two-directional equivalence with the Boolean closure of reachability and safety properties, the fragment BΣ°1 of the modal μ-calculus, shown to be the exact expressive level of stabilization over finite vocabulary. The correspondence needs no counting logic, external halting signal, or non-effective acceptance condition, yielding a verifiable path from weights to symbolic explanations.