揭示拓扑神经网络的逻辑表达能力,明确其能识别哪些图结构分类。
The Logical Expressiveness of Topological Neural Networks
- 提出k-CCWL同构测试与新型配对计数逻辑TCₖ
- 证明TNNs逻辑表达力等价于(k+2)-pebble游戏
- 为拓扑神经网络可表示的分类器提供理论边界
图神经网络(GNN)是图学习的标准方法,但其表达能力受限,常以Weisfeiler-Leman(WL)层次或一阶逻辑框架描述。近年来,拓扑神经网络(TNN)作为图表示学习的替代方案兴起,通过将高阶关系结构引入消息传递机制,展现出超越传统GNN的表征能力。然而,一个基本问题仍悬而未决:TNNs的逻辑表达力究竟如何?本研究通过分析源自通用TNN机制的同构测试,提出并研究了基于组合复形的k-CCWL测试。同时引入拓扑计数逻辑TCₖ,扩展标准计数逻辑,新增显式对变量计数的量化算子∃ᴺ(xᵢ,xⱼ) φ(xᵢ,xⱼ)。严格证明了三者等价:k-CCWL ≡ TCₖ₊₂ ≡ Topological (k+2)-pebble game。该结果建立了TNNs的逻辑表达力理论体系。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are the standard for learning on graphs, yet they have limited expressive power, often expressed in terms of the Weisfeiler-Leman (WL) hierarchy or within the framework of first-order logic. In this context, topological neural networks (TNNs) have recently emerged as a promising alternative for graph representation learning. By incorporating higher-order relational structures into message-passing schemes, TNNs offer higher representational power than traditional GNNs. However, a fundamental question remains open: what is the logical expressiveness of TNNs? Answering this allows us to characterize precisely which binary classifiers TNNs can represent. In this paper, we address this question by analyzing isomorphism tests derived from the underlying mechanisms of general TNNs. We introduce and investigate the power of higher-order variants of WL-based tests for combinatorial complexes, called $k$-CCWL test. In addition, we introduce the topological counting logic (TC$_k$), an extension of standard counting logic featuring a novel pairwise counting quantifier $ \exists^{N}(x_i,x_j)\, φ(x_i,x_j), $ which explicitly quantifies pairs $(x_i, x_j)$ satisfying property $φ$. We rigorously prove the exact equivalence: $ \text{k-CCWL} \equiv \text{TC}_{k{+}2} \equiv \text{Topological }(k{+}2)\text{-pebble game}.$ These results establish a logical expressiveness theory for TNNs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。