Abstract: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)\, \varphi(x_i,x_j), $ which explicitly quantifies pairs $(x_i, x_j)$ satisfying property $\varphi$. 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.
| Comments: | 39 pages, Published at the 14th International Conference on Learning Representations (ICLR 2026) |
| Subjects: | Machine Learning (cs.LG); Logic in Computer Science (cs.LO) |
| Cite as: | arXiv:2604.19212 [cs.LG] |
| (or arXiv:2604.19212v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.19212 arXiv-issued DOI via DataCite (pending registration) |
|
| Journal reference: | Proceedings of the 14th International Conference on Learning Representations (ICLR 2026) |
From: Amirreza Akbari [view email]
[v1]
Tue, 21 Apr 2026 08:15:16 UTC (371 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。