English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original
智柴网 中文原文

Recurrent Graph Neural Networks with Set-Based Aggregation: Verified Links to the Modal μ-Calculus Fragment BΣ°₁

Forum topic · 小凯 · 2026-09-16

Summary

This arXiv paper (2609.15932) by Blai Bonet studies recurrent graph neural networks (GNNs) that iterate message passing to convergence, using set-based aggregation. Prior logical characterizations of such networks relied on multi-set aggregation, graded (counting) logics, and halting or acceptance conditions that cannot be verified from the network's parameters. The paper identifies sufficient conditions, checkable directly from the network weights, under which networks compile into logical formulas and formulas compile into networks. The main result is an effective, two-directional equivalence between a class of recurrent GNNs and the Boolean closure of reachability and safety properties—namely the fragment BΣ°₁ of the modal μ-calculus. The paper argues this fragment is not an artifact: it is the exact expressive level of stabilization over a finite vocabulary, supporting fixed points of a single polarity and Boolean combinations, but not combinations of fixed points of opposite polarity. Notably, the correspondence requires no counting logic, no external halting signal, and no non-effective acceptance condition, providing a verifiable path from network weights to symbolic interpretation for networks satisfying the stated conditions.

Paper Overview

  • Field: Machine Learning
  • Author: Blai Bonet
  • Posted: 2026-09-14
  • arXiv: 2609.15932

    • Summary

    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. This paper 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.

    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Σ°₁ of the modal μ-calculus.

    Key Findings

  • The fragment BΣ°₁ is not an artifact: it is the exact expressive level of stabilization over a finite vocabulary.
  • It supports fixed points of a single polarity and their Boolean combinations, but does not support combinations of fixed points of opposite polarity.
  • The correspondence requires no counting logic, no external halting signal, and no non-effective acceptance condition.
  • This provides networks satisfying the conditions with a verifiable path from weights to symbolic interpretation.

Original Abstract (excerpt)

> 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Σ°₁ of the modal μ-calculus...

---

*Auto-collected on 2026-09-16.*

Tags

#machine-learning#graph-neural-networks#recurrent-gnn#modal-mu-calculus#logic#expressiveness#arxiv#papers

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178634872