We propose a modal logic in which counting modalities appear in linear
inequalities. We show that each formula can be transformed into an equivalent
graph neural network (GNN). We also show that a broad class of GNNs can be
transformed efficiently into a formula, thus significantly improving upon the
literature about the logical expressiveness of GNNs. We also show that the
satisfiability problem is PSPACE-complete. These results bring together the
promise of using standard logical methods for reasoning about GNNs and their
properties, particularly in applications such as GNN querying, equivalence
checking, etc. We prove that such natural problems can be solved in polynomial
space.

提出了一种模态逻辑，在其中计数模态出现在线性不等式中。将每个公式转换为等价的图神经网络（GNN）。证明了广泛类别的 GNN 可以高效地转换为公式，从而明显改进了关于 GNN 的逻辑表达能力的文献。证明了可满足性问题的 PSPACE 完备性。这些结果将常规逻辑方法和 GNN 及其属性的推理前景结合起来，尤其适用于 GNN 查询、等价性检查等应用。证明了这种自然问题可以在多项式空间内解决。

关于聚合组合图神经网络推理的逻辑

A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

In this paper, we propose a modal logic in which counting modalities appear
in linear inequalities. We show that each formula can be transformed into an
equivalent graph neural network (GNN). We also show that each GNN can be
transformed into a formula. We show that the satisfiability problem is
decidable. We also discuss some variants that are in PSPACE.

该论文提出了一种包含线性不等式中计数模态的模态逻辑，证明了每个公式可以转化为等价的图神经网络（GNN），也证明了每个 GNN 可以转化为公式，说明可满足性问题是可判定的，并讨论了一些 PSPACE 内的变种。