# The Logical Expressiveness of Topological Neural Networks

arXiv: https://arxiv.org/abs/2604.19212 · HTML: https://mlsanity.com/paper/2604.19212/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 21 Apr 2026.

## Builds on (most cited first, 24 of 24)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Topological Deep Learning: Going Beyond Graph Data](https://mlsanity.com/paper/2206.00606/) (2022)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Position: Topological Deep Learning is the New Frontier for Relational Learning](https://mlsanity.com/paper/2402.08871/) (2024)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Going beyond persistent homology using persistent homology](https://mlsanity.com/paper/2311.06152/) (2023)
- [TopoTune : A Framework for Generalized Combinatorial Complex Neural Networks](https://mlsanity.com/paper/2410.06530/) (2024)
- [Topological Neural Networks go Persistent, Equivariant, and Continuous](https://mlsanity.com/paper/2406.03164/) (2024)
- [Recursive Algorithmic Reasoning](https://mlsanity.com/paper/2307.00337/) (2023)

## Built on by (most cited first, 2 of 2)

- [Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks](https://mlsanity.com/paper/2605.00725/) (2026)
- [Geometry-Aware Simplicial Message Passing](https://mlsanity.com/paper/2605.06061/) (2026)

## Abstract (arXiv)

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 (TCk), an extension of standard counting logic featuring a novel pairwise counting quantifier  existsN(xi,xj), varphi(xi,xj),  which explicitly quantifies pairs (xi, xj) satisfying property varphi. We rigorously prove the exact equivalence:  k-CCWL equiv TC_k+2 equiv Topological (k+2)-pebble game. These results establish a logical expressiveness theory for TNNs.