揭示均值聚合GNN的逻辑表达能力边界，发现连续性假设会显著降低其表达力。
Logical Characterizations of GNNs with Mean Aggregation
- 通过模态逻辑刻画均值聚合GNN的表达能力，区分非均匀与均匀设置。
- 在连续性和阈值假设下，表达力退化为无交替的模态逻辑。
- 揭示均值聚合受实际约束影响大，适合关注理论边界的研究者。
研究采用均值聚合函数的图神经网络（GNNs）的表达能力。在非均匀设置下，这类GNN的表达能力与比值模态逻辑完全等价，后者允许用模态算子表示‘至少一定比例的后继顶点满足某性质’。在均匀设置下，其相对于一阶多步逻辑（MSO）的表达能力等同于普通模态逻辑，因此与最大值聚合的GNN表达力相同。但该证明依赖的构造不具实用性。为此引入自然假设：组合函数连续，分类函数为阈值函数。在此条件下，均值聚合GNN的表达力显著下降：在均匀设置下，其相对于MSO的表达力等同于无交替模态逻辑。这与最大值和求和聚合的GNN不同，后两者不受此类假设影响。
原文摘要 · Abstract (English)
We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function, with the following results. In the non-uniform setting, such GNNs have exactly the same expressive power as ratio modal logic, which has modal operators expressing that at least a certain ratio of the successors of a vertex satisfies a specified property. In the uniform setting, the expressive power relative to MSO is exactly that of modal logic, and thus identical to the (absolute) expressive power of GNNs with max aggregation. The proof, however, depends on constructions that are not satisfactory from a practical perspective. This leads us to making the natural assumptions that combination functions are continuous and classification functions are thresholds. The resulting class of GNNs with mean aggregation turns out to be much less expressive: relative to MSO and in the uniform setting, it has the same expressive power as alternation-free modal logic. This is in contrast to the expressive power of GNNs with max and sum aggregation, which is not affected by these assumptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。