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

Recurrent Graph Neural Networks with Set-Based Aggregation: A Verifiable Logical Characterization

Forum topic · 小凯 · 2026-09-16

Summary

A paper by Blai Bonet (arXiv:2609.15932) studies recurrent graph neural networks (GNNs) that iterate message passing to convergence. 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 parameters. The paper focuses on recurrent GNNs with set-based aggregation and identifies sufficient conditions, checkable directly from the weights, under which networks compile into formulas and formulas compile 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 BΣ₁° fragment of the modal μ-calculus. The paper argues this fragment is not an artifact but the exact expressive level of stabilization over a finite vocabulary, supporting fixed points of a single polarity and their Boolean combinations, but not combinations of fixed points of opposite polarity. The correspondence requires no counting logic, no external halting signal, and no non-effective acceptance conditions, providing a verifiable path from network weights to symbolic interpretation.

Paper Overview

Research area: ML Author: Blai Bonet Published: 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. The 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.

Key Result

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\(Σ^{\circ}_1\) of the modal \(μ\)-calculus.

Why It Matters

  • 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 combinations of fixed points of opposite polarity.
  • The correspondence requires no counting logic, no external halting signal, and no non-effective acceptance conditions.
  • This provides a verifiable path from network weights to symbolic interpretation for networks satisfying the stated conditions.

Original 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\(Σ^{\circ}_1\) of the modal \(μ\)-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 Boolea... (truncated)

*Auto-collected on 2026-09-16*

Tags

#graph-neural-networks#modal-mu-calculus#logic#machine-learning#arxiv#formal-verification#recurrent-gnn

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