The Logical Expressiveness of Topological Neural Networks

arXiv:2604.19212v1 Announce Type: new 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), arphi(x_i,x_j), which explicitly quantifies pairs (x_i, x_j) satisfying property arphi. We rigorously prove the exact equivalence: ext{k-CCWL} equiv ext{TC}_{k{+}2} equiv ext{Topological }(k{+}2)ext{-pebble game}. These results establish a logical expressiveness theory for TNNs.

Related

• Beyond the Laplacian: Doubly Stochastic Matrices for Graph Neural Networks
• Persistence-Augmented Neural Networks
• Subgraph Concept Networks: Concept Levels in Graph Classification
• Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning

Source: arXiv cs.LG | 2026-04-22