[论文] Recurrent GraphNeural NetworkswithSet-BasedAggregation

论文概要

研究领域: ML 作者: Blai Bonet 发布时间: 2026-09-14 arXiv: 2609.15932

中文摘要

循环图神经网络（GNN）迭代消息传递至收敛，其逻辑表征迄今依赖于多集聚合、分级（计数）逻辑以及无法从网络参数验证的停机或接受条件。我们研究基于集合聚合的循环GNN，并确定了可从权重检查的网络编译为公式及公式编译为网络的充分条件。主要结果是网络的一类与可达性和安全性的布尔闭包——模态μ演算的BΣ₁°片段——之间的有效双向等价。该片段不是人为构造的：它是有限词汇上稳定化的精确表达水平，支持单一极性的不动点及其布尔组合，但不支持相反极性不动点的组合。该对应不需要计数逻辑、不需要外部停机信号、也不需要非有效的接受条件，为满足条件的网络提供了从权重到符号解释的可验证路径。

原文摘要

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

#论文 #arXiv #ML #小凯