The Logical Expressiveness of Topological Neural Networks
Authors: Amirreza Akbari
Amauri H Souza
Vikas K Garg
Venue: ICLR 2026 Poster (2026)
Keywords: topological neural networks
message-passing networks
expressive power
first-order logic
Primary area: learning on graphs and other geometries & topologies

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.

Published as a conference paper at ICLR 2026
THE LOGICAL EXPRESSIVENESS OF TOPOLOGICAL NEURAL NETWORKS
Amirreza Akbari
Amauri H. Souza
Aalto University
Federal Institute of Ceará, 26 Al amaur Amauriholle www.aooalaadee foe. edu, br
amirreza. albaraaaaaaaaaiiaaaaaaa
Vikas Garg
Aalto University and Yai Ltd vgargecsail. wwm.mieeee..
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. this context, topo- logical neural networks (TNNs) have recently emerged as a promising alternative for graph representation learning. By incorporating higher-order relational struc- tures into sassage-passingg schemes, TNNs offer higher representational power than traditional GNNs. However, a fundamental question remains is the logical expressiveness of TNNs? Answering this allows open: what character- ize precisely which binary classifiers TNNs can represent. In this paper, we address this question by analyzing isomorphism tests derived from the underly- ing mechanisms of general TNNs. We introduce and investigate the power of higher-order variants of WL-bbaed tests combinatorial complexes, called k- CCWL. test. In addition, we introduce the topological counting logic (TCs), an extension of standard counting logic featuring a novel pairwise counting quan- tifier 3 (Iz, z2)) xz); which explicitly quantifies pairs (z) satisfying property sp We rigorously prove the exact equivalence: k-CCWL TC Topological (A++2)-pebbll game. These results establish logical expressiveness theory for TNNs.
INTRODUCTION
Graph neural networks (GNNs) (Scarselli et al.) 2009 Bruna al. 2014: Gilmer et al. 2017 Hamil-
data, driving progress in several applications such as drug repurposing (Stokes et al., 2020). simulation of physical systems (Znnalez-Gonzalez al. 2020), algorithmie reasoning (Jurss et al. 2023). and recommender systems (Ying et al. 2018). Nonetheless, most GNNs are at most as powerful as the W-Weisfeiler-Lehman (I-WL) test the color refinement algorithm) (Weisfeiler & Leman 1968) in distinguishing non-isomorphic graphs (Xu et al. 2019 Morris et al. 2019). Consequently. GNNs fail to capture fundamental structural information (e.g.. cycles connected components) and de- cide basic graph properties (Loukas) 2020; Garg et al. 2020 Chen et al.) 2020). Importantly, this limitation has also been examined through the lens of first-order logic. which provides precise characterization of the node-level binary classifiers that GNNs can express (Barceló et al. 2020).
ton et al.) 2017) have become the de facto paradigm for predictive tasks graph-structune
Naturally, this limited expressivity has propelled the development more expressive GNNs (Sato
et al. 202 Wang et al. 2022 Horn et al. [022 Verma et al. [024 Immonen et al. 2023). Among
these, topological neural networks (TNNs) (Hajij et al. 2023 Bodnar et al. 202 la Papillon et al,
2025) have recently emerged as the new frontier for relational learning (Papamarkou et al. 2024
Akin to GNNs, typical TNNs employ message- pressage-passing layers where each element of the input (c.g., nodes cells) updates its representation (or features) based those of its topological neighbors.
These TNNs operate on the so-called (uniform) combinatorial complexes (Hajij et al.) 2023):: a
flexible relational notion that accommodates both non-hierarchical domains (e.g.. hypergraphs)

---

Published as a conference paper at ICLR 2026
and hierarchical ones (e.g., cell complexes). Unraveling the representation capabilities of TNNs is imperative to understanding their strengths and pitfalls, and designing better, more nuanced models that are theoretically well-grounded. However, although the logical expressivity of GNNs, and even their higher-order variants (Morris et al.) 2019 2024), is well understood within the framework of first-order logic (Barceló al. 2020 Geerts & Reutter 2022), the logical characterization of TNNS remains largely uncharted.
To address this gap. this paper investigates the logical expressiveness of general framework for topological neural networks and their higher-order variants, here denoted as k-TNNs. As a first step, we introduce extensions of the classical color refinement algorithm tailored to TNNs: the combi- natorial complex WL (CCWL) test and its higher-order counterpart, k-CCWL. These refinements are not just abstract gadgets: they capture the expressive power of broad class of existing TNN architectures. In particular, 1-CCWL. subsumes the expressivity of most message-passing TNNs on cell complexes, including CW Networks (e.g.. Cell Isomorphism Networks, CIN) (Bodnar et al.) 2021a), message-passinngg simplicial networks (Bodnar et al. 2021 and higher-order GNNs such as UniGCN and UniGIN (Huang & Yang 2021), among many others summarized in (Papillon et al.) )024). More generally, any model with invariant update functions under the k-CCWL refinement cannot distinguish ACCs that L-CCWL cannot separate. For k = 1, this reduces to standard message passing on combinatorial complexes; for k >> the architecture operates on k-tuples of cells and updates labels via the same mechanism as k-CCWL. Notably, (I-)CCCI can be used as a standard tool for analyzing the expressivity of TNNs, and leads to strict hierarchy k grows.
To formally analyze the expressive power of TNNs, we introduce a new fragment of first-order logic, the topological counting logic (TCx), which is inspired by classical counting logic (Ebbinghaus & Flum 1999 | Libkin 2004: Immerman] 1998). The standard counting quantifier can only count single-variable instantiations; however, TC2 extends this by introducing pairwise counting quantifier 3 (z,, .ry) (p(z), zz) that allows reasoning about pairs of cells in topological structure. Intuitively, unlike in graphs, where edges directly connect two vertices, many relations between cells are mediated by other cells (e.g., two edges are adjacent because they share a vertex, or they both lie in the same face). Many interesting patterns also come from how a cell's boundary (its faces) and coboundary (its cofaces) interact, which is naturally described by counting pairs of cells that meet in some shared neighbor. This extension is motivated by the setting of TNNs aggregation: When updating cell's label through its upper and lower neighborhoods, the update necessarily involves information from intermediary face and co-face cells, which means that TNNs aggregate pairs of relational signals rather than single neighbors. The pairwise quantifier thus provides the correct logical abstraction for capturing these higher-order interactions.
In parallel, we define the topological k-pebble game, which generalizes the classical pebble games of Immerman (1822): [Imermma & Lander (1990) and the earlier work Ehrenfeuchh (1961); Fraisse (1944), and serves as the game-theoretic counterpart of TC2. Unlike the classical version, however, the topological game must be designed to capture the semantics of the new pairwise counting quan- rifier: Instead of only reasoning about single-variable placements, the game needs to account for pairs of pebbled elements and their topological relations. The main challenge lies in extending the rules so that duplicator-spoiler interactions reflect the ability of TC,, to distinguish structures based on the number of cell pairs satisfying a given property; therefore, we need to precisely align the expressive power of the game with the expressive power of the logic.
These tools create a unified analysis of k-TNNs from three sides: algorithmic (A-CCWL), logical (TC+), and same-theoretic (the topological pebble game). Our main contribution shows that these three characterizations are equivalent, in direct analogy the classical k-WL / counting logic / pebble games correspondence (Cai et al., 1992). which provides the first logic-gama --o---ameeaaaae algorrihh triad for k-TNNs and precise description of how their expressive power scales with k.
1.1 CONTRIBUTIONS
In this paper, we extend the classic triad "k-WL ++ Ck+1 counting logic ++ (k+1))-ebble game from graphs to attributed combinatorial complexes (ACCs), and use it to analyze the expressive power of topological neural networks (TNNs):
Section 3 Algorithm. We introduce k-CCWL, a WL-style refinement on ACCs that respects bound- ary, coboundary, lower and upper adjacencies. On uniform ACCs, simple broadcast-
2

---

Published as a conference paper at ICLR 2026
anchor gadget gives an edentical-vs-disjoine global color property (Proposition 3.1) and for every E N. we provide non-isomorphic ACCs that are distinguished by k-CCWL but not by (k-1)-CCWI (Theorem 3.2). We also show k-CCWL has the same pressive power as k-WL in terms of distinguishing non-isomorphic 1-dimensional ACCs (heorem D.2).
Section 4
topological counting logic TC2 with pairwise counting quanti- fier, 3 (z) p( Tz), which can capture the aggregation patterns of TNNS. We show that TCx+2 refines k- k-CCWL in distinguishing non-isomorphic ACCs (Theorem 4.1).
Logic. We define
Section 5
Game. We introduce topological k-pebble game, whose winning strategies for Player characterize TCu-equivalence (Theorem 5.1). As the final piece of the triad, we then show that --CCCW-indistiguussabblii implies winning strategy for Player II Theorem 5.2). All together, we have our main result Corollary 5.3
k-CCWL = TC = topological 2p-bb-e game,
so the hierarchy is strict.
(A: 1)-pebble counting game
Graphs
k- WL
Ca-1
ACCs
pairwise quantifier
topological (k+2) game
ACCs
k-CCWL
TCx+2
BACKGROUND
This section overviews combinatorial complexes, message-passing topological neural networks, and the logical expressivity of GNNs.
Combinatorial Complexes, Hajij et 2023) introduced combinatorial complexes as relational structure to accommodate both hierarchical topological domains (c.g.. simplicial complexes) and non-hierarchical ones (e.g., hypergraphs). Formally, combinatorial complex (CC) is triple (S, X, rk) consisting of set of vertices S, set of cells X' C P(S) \ (0). and a rank function rk: X - Zzo such that Vs E S. {s) E X'; and Va, E X, x C y = rk(x)) S rk(y). The set of k-cells of combinatorial complex, denoted X (k), consists of all cells with rank exactly k.
We can exploit rank functions to specify local neighbors for each cell. Analogously to Bodnar et al. a2 we define four neighborhood structures:
Boundary adjacency: (x(x)) = {y C w r(()) = rk(x) -
Co-boundary adjacency: No(x) = {y
rk(y) = rk(x) 1}
Upper adjacency: (x)x) = {y 38 such that æ C d,y c and rk(6) - 1= rk(y)=
Lower adjacency: Ni(x) {y 38 such that 5 x,
and rk(ō) + rk(y)=
We are interested in attributed combinatorial complexes. An attributed combinatorial complex (ACC) is tuple (S, X, rk, c) where X E assigns label c(z) from domain Σ to each cell x. The order of an ACC is max max(rk(x)= x E X).. Moreover, we call an ACC uniform if for every cell of rank > 0 there exists finite sequence of cells .0, -...., . such that da is cell of rank 0 and, for every 0 < i < t, there exists NG E (NB with
24 (.
In other words, from any cell, there is a finite sequence of cells to a cell of rank 0 by following the neighborhood structures. Further, assume binary features, i.e., Σ {0, 13 for some constant L.
CC-Isomorphism. Papillon et al. (025) introduced the notion of CC- CC-issomopphimm Let D1 = (Vi, C1 rk1, c1) and 12 (V2, C2. rk2, 02) be combinatorial complexes equipped with neighbor- hood structures Mi and N₁, respectively. A CC-isomorphism induced by (N1,N) is a bijective function f C C2 such that
In 1, we show 1-CCWL has the same expressive power as guarded fragment of TC3.
3

---

Published as a conference paper at ICLR 2026
1. For all o, if i Mi(o) then f(r) e N2(f(())
2. The inverse f- is also a CC-homomorphiss induced by (N2,,W1, and
3. ci) (7), then (2( c2(f(r))-
Topological neural networks (TNNs) (Bodnar et al., 2021a Papillon et al, 2025 2024) em- ploy passing layers to obtain cell-level representations. In particular, let Nall
NN, be the set of neighborhood structures. In its general form, starting from h2 = c(x) for all cells z, message- message-passing TNNs recursively compute:
h++1
h NENN
Agg, (MKx.))
(I)
where in is the embedding of æ at layer l. X and Agg, are inter- and intra-neighborhood aggrega- tion functions, respectively, jo is an update function (e.g., MLP), and M denotes multiset of messages. Let define (z, y) (2) (y) and Nn y) (2(x) (W) In the
literature, two main variants of message computation have been introduced:
(n((,, if = N Hourth he h E (a)), &
My.. ( be h() y E N(2), e () if Nr CoENiiy kC) (x)) otherwise.
Similar to the equivalence between 1-WL and GNNs, we can define corresponding isomorphism tests for TNNs. The key idea consists of adopting injective (or hash) functions for the maps é, X Agg, & in Equations (1) (2)
The W- Algorithm. The k-dimensional Weisfeiler- algorithm (k- WL. extends the classi- cal color refinement to k-tuples of vertices (Grohe & Otto 2015
Grohe 2017 Cai et al. 1992). Let E V the atomic rype atpc, (v) encodes the equality pattern among coordinates, the adjacency relations (vi, U2) E, and the initial colors o(u)). Initialization is given by
G , E, c) be vertex-colored graph. For v (Ui,..., . 2k
(v) == (v).
(3)
At iteration + 1, the label of refined using substitutions by all u E
w/ (((++1) (v) : (= {{ (atpe+r (v, wi (viu/Il),... ..., [ : : =Ev (4)
Here v [u/i] denotes the k-tuple obtained by replacing with u. The process stabilizes after finitely many steps, yielding the stable coloring wl(o)) Two graphs G, H are distinguished by k-WL if their multisets of stable colors differ.
Morris al. 2019)
slightly different method WL To avoid confusion, we follow the method used in Cai et al. 1992) as k-W and recall the latter method as oblivious k-WL, or k-OWL.
Logical expressivity and counting logic. The k k-variable counting logic CG is the fragment of first- order logic restricted to variables { 2x) and extended with counting quantifiers. For any N N, formulas are generated by
b = (,,=,,)) (x().) F(F,,,,) I - | (wh 4/22 3 x, v.
where P. (for E [(] are unary predicates encoding node attributes, and E is the adjacency relation.
Semantics is defined over a vertex-colored graph G = Eg. Eg.cG) Let C, {1 E Vo (ca(t)), 1} be the set of vertices that their s-th bit of attribute 1. For (partial) valuation μ: (21...., . VG. the satisfaction relation G, }= 6 is defined as follows:
..l......44.
G (a():) u(xx)) E C..
G. 1 = E(a,, iff (u(a;), e Ec. G. - iff G. vb
G (z; (x:=;;) x,) iff u(xx)) u(x;).
G (wh (b)) iff G. F ii and G. F= t22
G,p PY go iff there exist at least N distinct elements Va such that G, n|n; c) th
4

---

Published as a conference paper at ICLR 2026
A key result Cai al. (1992) shows that Ck+1 has exactly the same distinguishing power the k-dimensional Weisfeiler Lemann algorithm (k-WL). Moreover, two graphs can be distinguished by k-WL if and only if they can be separated by some Ck+1 formulas. Therefore, the iterative refinement of k-WI. captures precisely those properties which can be defined with k+1 variables and counting quantifiers. This explains why increasing k strictly increases expressivity, and why the power of GNNs and their higher-order variants can be analyzed by counting logic. Pebble Game The Cx-pebble game, introduced by [mmerrman & Lander (1990), gives game-theoretic view of CR. The game is played between two players on two graphs A and B with & pairs of pebbles (a1, bi)..... (ax, bk). At any moment, the current pebble placements define partial mapping from vertices of A to vertices of B. In each round, Player selects subset X C B: Player II must respond with a subset Y S A of equal size. Then, Player chooses an element Y place pebble a; there, and Player II must place the matching by on an element of X. Player wins immediately the partial mapping defined by the pebbles is not a partial isomorphism (i.c., fails to preserve adjacency relations or equality).
Player II has a winning strategy for rounds she can always maintain a partial isomrrphism for that many rounds. In this case, A and B satisfy the same Ce-sentences of quantifier depth at most q. Indeed, the following are equivalent: and agree on all formulas in C5; A and B are indistinguishable by k-WL; and Player II has winning strategy in the k-pebble game A and B,
HIGHER-ORDER TOPOLOGICAL ISOMORPHISM TESTS
This section introduces higher-order isomorphism tests associated with TNNS (using injective ag- gregate and update functions). In other words, naturally extend the tuple-based procedure of k-WL to combinatorial complexes.
The construction mirrors equality, ranks, colors, and the four topological adjacencies; we then iteratively refine by "probing" all possible substitutions and aggregating the resulting colors. The key novelty is the double shift sequence, which simultaneously tracks two substitutions per position; this is exactly what will force a (k++2 2) -varribble requirement on the logic side in /eccionn 4
k-WL on graphs: we start from an atomic type for k-tuples that encodes
k-CCWL isomorphism test (k: 2)
Let r (k, c) be an ACC, and let x (#1;...,, .x) E X be k-tuple of cells. The rank sequence of x is defined as rank(x) = (rk(z)),.... (.....,,((xxx)) rk(x))). The atomic type of k-tuple x, denoted atp, (x). encodes structural and attribute-level information about the tuple. It consists of the rank sequence of x, the initial colors c(z,) for = 1,...,k, k. and five binary vectors that describe pairwise relations among components boundary adjacency, coboundary adjacency, lower adjacency, and upper adjacency. Each relation vector shows if the corresponding pair of cells satisfies the relation.
x: equality,
1. Initialization: For each X** define the initial label: Xie (x) atp; (x).
2. Update: For 2 1, the label of each x x updated as: X (x)
HASH(X (x) (x)),, where D(0((x (x) is multiset of refinement contexts, which is defined as follows:
D( ( (xtP)42(x0.),, A (x;,,))) a, C.SBEX
Here, A (t-1) (x; ax; 9) denotes the double shift sequence:
/ (1-1) (xla//)) 1 - [x: (x: 3)
(x13/1)) (
1=1
3. Termination: The process continues until convergence:
X
(t+ (t+1) (x) X (x) for all
x E A The final stable labeling is denoted x (x).
(x).
5

---

Published as a conference paper at ICLR 2026
In both CCWL and k-CCWL, after each refinement step, aggregate the tuple labels to form global label for the complex. For an ACC =
and iteration t, this is defined as
(t) X
{
(1) (xx X xEX"
Given two ACCs A = (SA, rkA, ea) and B = (Sn, Xn, rkn, CB), the k-CCWI, procedure distinguishes and B if their stable global signatures differ, i.e.,
(00) * Xt,B
XK,A
Complexity. Let n = | Since we work with finite ACCs, the refinement process induced by k-CCWL stabilizes after finitely many iterations (at most n² 1), so the stable coloring well- defined (see Lemma B. Additionally, ranks, and attributes. Updating the colors of all k-tuples can be done in h+2). Thus, the time complexity of k k-CCWL is (n.2++2).
use (mz space encode all adjacencies,
For isomorphism testing, we augment each complex by introducing a fresh O--ell connected to every existing O-cell via new 1-cells, all initialized with distinct new color. We then run the k-CCWL refinement on these augmented complexes and compare their stable global signatures. Intuitively. the fresh O-cell acts broadcast anchor: any local color difference between the complexes is propagated through this anchor to all other cells during the refinement process. Importantly, adding cells does not change whether the original complexes are CC-isomorphic:
the broadcast-anche only mark the anchor and its incident l-cells as new elements by choosing distinct colors from the rest of the complex. As consequence, once stabilization reached, the global signatures of the two augmented complexes cannot partially overlap: they are either exactly the same or completely disjoint.
(SA, KA, rk,, and B (SB, XB, rkg, CB) be two uniform ACCs, and let k 2 1. Suppose the k-CCWL algorithm applied to both A and B. Then exactly one of the following holds:
Proposition 3.1 (Identical-vs-diinn vs-djsjoin). Let A =
(0c) XE.A = X
(00)
(00)
(00)
XR,A
Kk.B
The proof of [Proposition 3.1 is provided in Section of Appendix. Our next result shows that k-CCWL. not less expressive than (I--))-CCWI.
Theorem 3.2. For any N. there exist pairs of non-isomorphic ACCs that are distinguishable by k-CCWI but not by (k-1)- 1))CCCC
The proof of Theorem 3.2 is provided in (Section of Appendix.
TOPOLOGICAL COUNTING LOGIC
In what follows, we consider ACCs of the form - (S, where c: : {0, 1] assigns binary attribute vectors and rk X' + 1.......,pp) /}} assigns a rank to each cell. We define the k-variable fragment TC; of first-order logic extended with a pairwise counting quantifier. Formulas & TC₁ are built over the variable set (II,..., and follow the grammar:
:: (z, = x,) (x,))) Px(x,) E (x,, | 11 A 2h2 - 1 (2),
(5) e)
where i,j E (1....,k, k) are distinct. The symbols R, for {0, 1,...,p) p}} and P. for E (1,..., are unary predicates encoding rank and bitwise color attributes, respectively. The binary predicate E,,, for N (N, NC,,,, captures boundary, coboundary, lower, and upper adjacency relations.
The set of free variables in a formula ø E TC2, denoted free(Ø). determines the variables that are not bound by quantifiers and is defined inductively as follows:
1. free(x; = xz) = free(E (N,, = {a,, x,}
free R2 (xx) = (roo(P.(zz)) = {x;}
3. free(1) A (2) = freo((1) U free((2))
4. free(-0) free(()
5. free(3 (II, Φ) free(Ø) (I,, K,}

---

Published as a conference paper at ICLR 2026
Coruanmarry Adbucenc
Color ge elanent
h
w
Upper Aduuoms
Equality
g
(c,e)
Initialization
000 01
Houndtary Adjacmic
Lowez Adjucnes
Color of dkmoot
Rank tequenos
Update
Ot
B
Refinement context for each pair (a, ()
st, ((x"=)) (a, (- (a, e)) (x (c a),x (c, a))}
a
at ((x (a, x). (b. e)) (c, ( bi])
a
a
a.,, (a (c, e)) (x a},x x xー (c et))
Figure 1: Example of one refinement round in the 2-CCWL on ACC where all vertices share the same color, all edges share the same color, and there is a single 2-cell (the triangular face). The chosen tuple ec, consisting of a vertex and edge e, is first assigned its atomic rype, which includes pairwise equality, adjacency relations, colors, and the rank sequence. During the update step, all substitutions (a,, 3) of cells into the tuple considered, and for each pair the refinement context is formed from the extended atomic type and the double shift sequence. The resulting collection of contexts is then hashed with the initial label to produce the updated label at round I.
A partial function μ .xk X' has domain dom,, S {a 24 on which each E dom,, maps to exactly one cell of I. The semantics of formulas in TC, is defined in terms of interpretations relative to a given ACC T and a partial valuation μ.. This interpretation determines whether formula & is satisfied by a given ACC P and a partial valuation with free(Ø) C &oom,, denoted as I, fa }= Φ. To be more precise, we define:
T, k = R, (2::) if and only if rk(p(x:))
T, f = Pa and only if the s-th bit of c(u(x;;) 1.
T = E (I)) if and only if p(xx) E (N(((())))
1 = (x; = x;)) and only u(x;) = u(zz).
I (6 A v if and only if -= o and I2 u - v.
F, = - if and only if a H s.
T, = AN (z., v/ if and only (()),02) E 22 T, 1
b 2 N.
In the last case, 14xx; C1, Ij c2] denotes the partial valuation obtained by extending μ to include the assignments x; to ei and xy to c2. Moreover, when free(Ø) = 0. we simply write I - Φ
instead of I, n F Φ, since the choice of valuation μ is then immaterial.
Limitations. Note that TC2 is still finite-variall, counting logic and it inherits the usual locality restrictions of C.. Many global graph/topological properties need unbounded and cannot be ex- pressed by TC2 for any fixed k, e.g.: (1) classic global graph properties that k-WL cannot capture for fixed k such as connectivity, existence Hamiltonian path or perfect matching. (2) topological invariants that depend the overall pattern of "holes" and voids across the entire complex, where the difference between two complexes may only appear in very large cycles that cannot be detected from any fixed-radius local neighborhood. Note that Eitan et al. 2025) shows that higher-order
7

---

Published as a conference paper at ICLR 2026
message passing on CCs has "blindspots" (e.g., for diameter, orientability, planarity, homology). Indeed, our hierarchy is complementary: many such blindspots correspond to properties requiring unbounded quantification and thus lie outside TC
The k-CCWL procedure refines tuple colors step by step, and each update depends on how many pairs of cells (a. (3) yield given atomic type for the extended tuple and produce specific color pattern. On the logic side, TC can describe exactly this situation: with variables for the tuple and two extra variables, it can state, "there are at least N such pairs (a, () making the extension satisfy property v²" Thus, each refinement step in k-CCWL can be seen as the logical counterpart of adding one more layer of quantifiers in TC++2. Formally, we have
Theorem 4.1. Let A= (SA, XA. IKA, CA) and B (Sp, XB, rkg, CB) be two ACCs, and let u, E XI uB E B be k-tuples of cells from A and B, respectively. for every formula @ E TC we have
AA F Φ = B, B, =6.
then the k-CCWL colorings agree:
(20) XK. (UA) = Xk.B (uB).
(20)
Proof sketch. The proof proceeds by induction on the number of refinement steps t. For the base case (t = 0), we use the agreement on all quantifier-free formulas to show that the initial atomic types, and therefore, the initial colors, the same. For the inductive step. we assume the claim holds up to step - 1. If a difference appears at step nt, we have two cases: (1) It happened at step 1 (contradicting the induction hypothesis) or (2) comes from the neighborhood aggregation. In the latter case, we can construct formula of quantifier depth n in TC that separates the two structures, which again contradicts the assumption. Therefore, the colors must agree at every step. The full proof of Theorem 4.1 is provided in Section C.4 Appendix.
TOPOLOGICAL PEBBLE GAME
Let (S,, and B = (Sp, XB, rkp, cn) be two ACCs, and let uı, uB : {zi,..., [Ik XA.NB be partial valuations such that dom(ua) dum(up). We say that (A, UA) and (B, uB) are k-dimensionally structurally similar, which is written as (A, UA) ~o (B,uB). for every pair of variables I; 2z E dom(ua), the following conditions hold:
1. ua(x,)) = =x((z)) = up(x)) uz(xz)
2. rka(ua(z:)) = rkn(un(I:))
3. (a(ua(z))) cc((u((;))
4. ua(x;) (A(), = un(x;) un())))(z;) for all A NN,,
Note that the above conditions show a local CC-isomorphism between the subcomplexes of and B, which is induced by u and ug. In particular, (A, uA) ~ (B, confirms that the map- ping uA(x;) + un(x;) preserves equalities between cells, their ranks, their labels, and all of their neighborhood relations. In other words, it satisfies exactly the requirements of a labeled CC- isomorphism restricted to the cells in the domain of the (partial) valuations. Therefore, we can take k-dimensional structural similarity as local form of CC-isomorphism, defined by partial valua- tions. Here, (A,, denotes the neighborhood of cell in the combinatorial complex A, making explicit which complex the neighborhood is taken with respect to.
The topological Intuitively, the pairwise counting quantifier in the logic is reflected by the game rule where Player I selects a set of cell pairs in one complex and Player II must answer with set of the same size in the other. To keep winning, Player II must choose the responses so that all ranks, colors, and neighborhood relations remain consistent between the two structures. This means that if Player II can survive for t rounds without losing, then the two structures cannot be distinguished by any TC, formula with quantifier depth at most l.
pebble game in Box below is designed to match exactly the semantics of TC.-
8

---

Published as a conference paper at ICLR 2026
Box I: Topological Pebble Game TC₁
The topologiaal pebble game two-player combinatorial game played between Player I (the Spoiler) and Player II (the Duplicator) on two ACCs A = (SA, AA, rk,, (A,,CA) and B (SB, rkB, CB). The state the game described by a pair of partial valuations MA.MB { - - XA NB. which assign up to k variables to cells in A and B, respectively. Each round of the game proceeds as follows:
Step 1: Player chooses one of the complexes (say A) and selects a finite set of ordered pairs PA S X3.
Step 2: Player Il must respond with a set P3 S X2 such that |Pal PPal-
Step 3: Player chooses a pair (an, TB) E Pn and updates the valuation Pa by placing pebbles: |n + an: Ij + TBl for some distinct i,
Step 4: Player II must choose a pair (0 TA) E 2% and update MA(Z, + oA 2 + TAL-
After r rounds, we obtain valuations ( H²B), which show all pebble placements so far. Player wins the r-round game if they preserve k-dimensional structural similarity,
(1) ~ (B,r for all i S (A, A
Player II has a winning strategy if this similarity is preserved in every r-round game. Player I wins if Player II fails preserve structural similarity any round.
and B = (Sp, XB, rkg, CB) be two ACCs, and let UA E P uB E X be k-tuples of cells from A and B. respectively, If Player Il has a winning strategy in the topological (k)--eeblle game on (A) and (B) with initial configuration (u un), then for every formula & E TC2,
Theorem 5.1. Let A =
U. F + BB 1
Proof sketch. The proof proceeds by induction the number of moves & in the game. For the base case (t = 0), we prove that if Player II has a winning strategy, then A, uA and B, ug agree on all quantifier-free formulas. For the inductive step, we assume the claim holds up to t
1. At I == n. the only important case we need to handle is when the formula is of the form 3N (I. (1r, y)- If Player selects set of candidate pairs in one structure, then Player must respond with set of equal size in the other. If no such response were possible, Player II would fail to maintain winning strategy, which contradicts the assumption. Therefore, the result also holds for t n. The full proof of Theorem is provided in Section C.5 of Appendix.
The next step is to connect k-CCWL with the topological pebble game. Intuitively, if two tuples receive the same color at every step of k- k-CCWL, then Player II can always mirror Player I's moves in the (k+bb)-eebble game without losing. To give more intuition, one can recall that in the classical Weisfeiler-Leman correspondence, where k-WI. matches with the (k+1 ---bblee game: the extra pebble serves as a cursor to resample one coordinate, while the other pebbles keep the rest of the tuple fixed. In our setting, however, each refinement step inspects pairs of extensions (a, () via the double-shift sequence, and the logic quantifies over such pairs. As a result, we need two spare pebbles for (a., B), which leads to (k++2) pebbles rather than (k++) pebbles. This correspondence formalized in the following theorem.
(A,, IKA, Ca) and B (SB, XB, rkB, CB) be two ACCs, and let u E X uB E X be k-tuples cells from A and B, respectively. If the k-CCWL colorings of u (0o) and uB agree, i.e, Xk.A (uΛ) = Xk.B (uB). then Player II has winning strategy in the topological game on (A) and (B) with initial configuration (u wn).
Theorem 5.2. Let
(co)
(8) sketch The proof shows that if Xk.A (uA) = Xe.B (uB). then Player II has winning strategy for the t-move TC game. The proof is by induction on f. For the base case (t = 0), equality of k-CCWL colors implies identical atomic types for UA and ug, which satisfies the conditions needed for Player II to win the O-move game. In the inductive step, assume the result holds for all t < n. For = n. Player I's strongest move is to modify an unmodified pair (#x+2, xx+1). ). Player II responds by selecting matching valuations in the other structure, preserving atomic types and color

---

Published as a conference paper at ICLR 2026
shifts. By the induction hypothesis, Player II can then continue maintain winning strategy for the remainder the game. The full proof Theorem is provided in Section C.5 of Appendix.
Combining Theorems 4.1 5.1 and yields our three-way way equivalence: equality of stable k-CCWL colors, Duplicator's s winning strategy with k+2 pebbles, and agreement on all TC formulas. Corollary 5.3. Let A = (A, IKA, CA) and B = (Sp, XB, rkg, CB) be two ACCs, and let WA X uB A be k-tuples of cells. Then the following statements are equivalent:
(00) 1. XE.A (uA) = Xk,B (un)
(00)
2. Player has a winning strategy in the topological (k++2)-pebbe game on (A, UA) vs. (B, UB)
3. For every formula & E TC++2, we have: A, U = = B, uB F
Restricting the above corollary to the case of uniform ACCs, and using Proposition 3.1 we have: Theorem 5.4. The k-CCWL procedure and TCx+2 are equivalent in expressive power for distin- guishing non-ison -oniisomopphic uniform ACCs.
The proof of Theorem 5.4 provided in Section C.5
B
A
c
22
UG
E
61
1/2
E3
6G
Up
E8
U/
Ua
U6
33
V
e2
U3
C1
eT
17
Two non-isomorphic simplicial complexes. If all vertices and edges are given the same initial color, then running SWL or 1-CCWL gives the final coloring shown above.
Figure 2:
Example 5.5. Figure 2 is an example of two non-isomorphic simplicial complexes from Verma et al. 2024). In this example, we want
both logical and game point of view for k 2 to show that (1) TC₁ can distinguish these two ACCs, and (2) Player has a winning strategy in TC, game.
Logic: Consider formula o E TC₁ as follows:
= 33 x2) (Ia, I4) CYCLE( 32, T3,
where CYCLE( Zy. 33, = N 22) A E EM D3)) A E. (2s, xs) E. x1) A (E,, A A (x2,, 24) A (z) F3 T3) A A
24). In the ACC A. we have two copies of C4 connected by an edge, and each C4 gives us eight 4-tuples n.a = (u1, 122 us) that uy connected consecutively. Therefore, A - Φ, however, we do not have such tuples in ACC B, therefore, B H Φ.
Game: Player first chooses, each copy C4 in A. all 16 pairs of adjacent edges as PA- For any reply Pg. there is pair not containing e's Player I picks such pair and modifies u.. W.l.o.g., assume now Player modifies the valuation U such that (Z1) = e and u (x22 62. In the next round, Player sets PA {(e3, e4)). Whatever Player II chooses, they lose, since A, the edges G1 62, C3 and 64 are consecutively in each other's lower neighborhood.
CONCLUSION
We introduced the k-dimensional combinatorial complex Weisfeiler- test (k-CCWL.) together with a Topological Counting Logic (TC,) equipped with a pairwise counting quantifier and matched them with topological (k+2)- game. Together, these yield the first aeti--aam-allgorthe triad for higher-order message passing on combinatorial complexes. Our main equivalence is
k-CCWI. TC Topological (k++2)-pebbl game.
follows that k-CCWL and TC have identical separation power, which strictly increases with k. This pins down exactly which binary classifiers higher-order architectures realize and, via the pairvise-counting view, explains when moving to higher dimensions yields provable gains over standard message passing graphs.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This work advances our understanding of the foundations of topological neural networks by estab- lishing their logical expressivity. While it might pave way for design of more powerful topological models, we do not foresee any specific ethical concerns stemming from this work.
ACKNOWLEDGMENTS
This work was supported by the Quantum Doctoral Programme (QDOC) the Finnish Quantum Flagship. VG also acknowledges Saab-Wa WASP, Research Council of Finland, and the Jane and Aatos Erkko Foundation for their support. AS acknowledges the support by the Conselho Nacional de Desenvolvimento Científico Tecnológico (CNPq) (408974/2025-7, 312068/2005-5).
REFERENCES
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in neural infor- mation processing systems, 34:2625-2640, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F. Montúfar, Pietro Lió, and Michael M. Bronstein. Weisfeiler and lehman go topological: Message passing simpli- cial networks. In Marina Meila and Tong Zhang (eds.), Proceedings the 38th Interna- tional Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, vol- 139 of Proceedings of Machine Learning Research, pp. 1026-1037, PMLR, 2021b. URL
mllr press / 139 htt99//onnana http///onarrr11. html
J. Bruna, W. Zaremba, A. Szlam, and Y. Lecun Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations (ICLR). 2014.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count
substructures? In NeurlPS, 2020.
H.D. Ebbinghaus and J. Flum. Finite Model Theory. Perspectives Mathematical Logic. Springer Berlin Heidelberg, 1999. ISBN 9783540657583.
Andrzej Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math, 49(129-141):133 1961.
Yam Eitan, Yoav Gelberg, Guy Bar-Shalom, Fabrizio Frasca, Michael M. Bronstein, and Haggai Maron. Topological blindspots: Understanding and extending topological deep learning through the lens of expressivity. In NewrIPS 2024 Workshop on Symmetry and Geometry in Neural Rep- resentations, 2025. URL http:ttsss///pe.eee.eaaee wwtp://wwwwweewtwe/e//ee 2ttp://foouumm02226666666
Roland Fraïssé. Sur quelques classifications des systemes de relations. Universite d' Alger, 1954.
V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), 2020.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural net- works. In International Conference on Learning Representations (ICLR 2022), pp. 1-43, 2022.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neu- ral message passing for quantum chemistry. In International Conference on Machine Learning (ICML., 2017.

---

Published as a conference paper at ICLR 2026
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, vol- ume 47. Cambridge University Press, 2017.
Martin Grohe. The logic of graph neural networks. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-17. IEEE, 2021.
Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80(3):797-844 2015.
Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenz, Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal Dey, Soham Mukherjee, Shreyas Sam- aga, Neal Livesay, Robin Walters, Paul Rosen, and Michael Schaub. Topological deep learning: Going beyond graph data. 04 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borg- wardt. Topological graph neural networks. In International Conference on Learning Representa- tions, 2022. URL
net/ http://ooonnnxxxxeeeeeeeeeeeeeee
Jing Huang and Jie Yang. Unignn: a unified framework for graph and hypergraph neural networks. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI-21, pp. 2563-2569. International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 0..24963/jccai22222/333 URL https://doi org./0.2/9910000
ijcai. 20a1/2202/353 Main Track.
Neil Immerman. Upper and lower bounds for first order expressibility. Journal of Computer and System Sciences, 25(1):76-98, 1982.
Neil Immerman. Descriptive complexity. Springer Science & Business Media, 1998.
Neil Immerman and Eric Lander. Describing graphs: first-order approach to graph canonization. Springer, 1990.
Johanna Immonen, Amauri Souza, and Vikas Garg. Going beyond persistent homology using per- sistent homology. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 63150-63177 Cur- ran Associates, Inc., 2023.
Jonas Jurss, Dulhan Hansaja Jayalath, and Petar Velickovic. Recursive algorithmic reasoning, In The Second Learning on Graphs Conference, 2023.
Leonid Libkin. Elements of finte model theory, volume 41. Springer, 2004.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- ference Learning Representations, 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602 6602-4609,20 2019.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: the story so far. J. Mach. Learn. Res., 24(1), mar 2024. ISSN 1532-4435.
Martin Otto. Bounded variable logics and counting, volume 9. Cambridge University Press, 2017.
Theodore Papamarkou, Tolga Birdal, Michael M. Bronstein, Gunnar E. Carlsson, Justin Curry, Yue Gao, Mustafa Hajij. Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, Vasileios Maroulas, Nina Mi- olane, Farzana Nasrin, Karthikeyan Natesan Ramamurthy, Bastian Rieck, Simone Scardapane, Michael T Schaub, Petar Veličković, Bei Wang, Yusu Wang, Guowei Wei, and Ghada Zamzmi. Position: Topological deep learning is the new frontier for relational learning. Ruslan Salakhut- dinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix
12

---

Published as a conference paper at ICLR 2026
Berkenkamp (eds.), Proceedings of the 41st International Conference Machine Learning, vol- ume 235 of Proceedings of Machine Learning Research, pp. 39529-395355 39555. PMLR, 21-27 Jul 2024.
http://///2///pppaaaaaooaaaaaaa html
Mathilde Papillon, Sophia Sanborn, Mustafa Hajij, and Nina Miolane. Architectures of topolog- ical deep learning: A survey of message-passing topological neural networks. arXiv preprint arXiv:2304. 10031, 2024.
Mathilde Papillon, Guillermo Bernardez, Claudio Battiloro, and Nina Miolane. Topotune: A frame- work for generalized combinatorial complex neural networks. In Forty-second International Conference on Machine Learning. 2025. URL https:/ /tlEp::///penreviww new forumiid S5n. fo
A. Sanzhez-Gonzalez, J. Godwin, T. Pfaff, R. Ying, J. Leskovec, and P. Battaglia. In International Conference on Machine Learning (ICML), 2020.
R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In SIAM International Conference Data Mining (SDM), 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Jonathan M Stokes, Kevin Yang. Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann et al. A deep learning approach to antibiotic discovery. Cell, 188(4)668--722 2020.
Yogesh Verma, Amauri H Souza, and Vikas Garg. Topological neural networks go persistent, equiv- ariant, and continuous. International Conference Machine Learning (ICML), 2024.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representa- tions (ICLR), 2022.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9): 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Leurning Representations, 2019. URL https: //open
A5Km A55mm
R. Ying. R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolutional neural networks for web-scale recommender systems. In International Conference on Knowledge Discovery & Data Mining (KDD), 2018.
APPENDIX OVERVIEW
The appendix complements the main text by providing formal definitions, detailed proofs, and aux- iliary results that underpin our theoretical contributions. We present complete proofs for the main results stated in the paper, including the vdentical-vs-disjinnt property (Proposition 3.T and the cquivalence theorems connecting k-CCWL, TC and the topological pebble game.
A GENERAL NOTATION
The set of real numbers is denoted by R. the set of integers is denoted by Σ, and the set of natural
numbers denoted by N. Furthermore, we denote [n] := {1, 2, ...... ...,.. Moreover, for any set of numbers S, the following notations are defined: the union of 5 and (0) is denoted by Sp == SU (0), and for any m E S, the subset 52m == fx E S x 2 m) contains all elements S greater than or equal
In general, for functions f.g: 3::... X +Y, is said to refine g (denoted by f 9) if for all x I' e X, whenever (x) f(x'), it follows that g(x) = g(x'). Functions f and g considered equivalent
13

---

Published as a conference paper at ICLR 2026
(denoted by f 9) if 3 9 and 3 f. meaning that f and assign the same values to related elements in X. Moreover, consider a subset Ç X, the restriction of f to A, denoted by fla. the function flx A Y defined by
f
for all A.
A partial function f from A to B is relation f A B such that for every E A, there is at most one y & with (x. E f. In other words, a partial function a function that may be defined for all elements of its domain A. this paper, we use the arrow notation f A B to show partial function f. The domain of f, denoted by domy, indicates the set of all I E for which fxx is defined.
B CCWL AND k-CCWL
First, we give the formal definition of the combinatorial complex Weisfeiler-LLeman (CCWL.) algo- rithm.
Conbinatorial complex Weisfeiler-Leman (CCWL). Let r (S, X, rk, c) be attributed combinatorial complex. The CCWL, algoriin iteratively computes the labeling of cells in the com- binatorial complex. The process is defined as follows:
1. Initialize the cell labeling: for each cell æ E X, set x2) - (c(xx),k(11)
2. For each iteration / 2 1, update the cell labels using:
(x)
(c), (1)))
where
( (000=((B.00))) (c),0 (c), cli(1) (x)) (x)
The colors of the boundary cells are denoted by (B.()())) the colors of the co-boundary cells are denoted by (x)))) colors of the lower cells are denoted by (x)) and the colors of the upper cells are denoted by ct.(0) (x:). These sets are defined as follows:
(1) = {
(t- (
y N=))()) }.
Xi
(x) = { {xi x (v) (cN)) }.
(x) {x1 (xf-"((w)
(v) (e-1)
(z) (2)
2 and e
a (x) (xI--" (t-1)
Here, for the sake simplifying the notation, we write (B ny y) instead NB(x)) N (y), and similarly (z O y) instead of (c)x) n (e Moreover, whenever we work with two ACCs A and B in the same argument, we make the complexes explicit in the notation: for example, MV x)
denotes the neighborhood of x in A, and Xi.A denotes the 1-CCWL coloring on A at round t. In addition, after each iteration, collect all cell labels to form global label for the combinatorial complex:
x = (x) (x)
The stable labeling is reached at iteration t when, for each a e X, Xi xx)
x²) The stable (60)
labeling denoted by xi
(no) (z). The set of stable labels for all cells is denoted Xi.r
Convergence. Before proceeding, we start with a simple termination result for k-CCWL for k: 2 2, and the termination of CCWL. (k: can be proved similarly.
14

---

Published as a conference paper at ICLR 2026
Lemma B.1 (Termination of k-CCWL). Ler XS, let 2 1. Consider the k-CCWL refinement sequence
X rk, c) be an ACC with finite cell set X, and
(xk x* >
defined in /Section 3 Then this sequence stabilizes after finitely many iterations. In particular, there exists E Ro such that
Xk
(T+1 (xx = Xx (x)
for all E X²,
(00) well-defined.
so the stable labeling X
Proof of Lemma B.I Since X' is finite, say | = n < oc, the set of k--uppes == X is also finite
with [U| n². For each iteration t No. the labeling
X
U E
induces equivalence relation ~e U via
(1) (x) (x) Xk (0) (y): (x))
X
and hence partition P. of U into color classes. By the k-CCWL update rule (see the definition in Section 3), we have
(++1) (x) HXSH(XE
(x), (x
(x)), (x)),
X
where (x) is the multiset of refinement contexts
D (x) H{ (atP ! B)) a, x
By assumption, HASH is injective its arguments (cf. the discussion preceding the CCWL and k-CCWL definition, so
(x) = Xk (y) = (x), (X (y), D (y)).
(++1)(y)
X
In particular,
(1-1 (x) X ((+1)
(y)
(x) Xk (8)
(y):
Xk
which means that any two tpples that are merged at round ++ must already have been in the same color class at round f. Equivalently, each color class of P.+1 is contained in some color class of Pt, so Po+1 a refinement of Pt.
If Pt+1 A Pt. then at least one color class of P, is split into two more classes in Pr+1, and hence
P |Pal-
On the other hand, each P; is partition of the finite set U,
pdl < 10 = h
for all E No-
Therefore, the sequence partitions Po. P1. P2.... can strictly increase in size at most n²
times. It follows that there exists some T nº 1 with
Pr+1 Pr5
which is equivalent
(T+1) (x)
Xx (T)
(x)
for all x E U x*
For all f T, the refinement stationary, the stable labeling
(2))
is well-defined, and the k-CCWL procedure converges on T.
15

---

Published as a conference paper at ICLR 2026
Complexity of k-CCWL. To complete understanding of l- k-CCWL algorithm, Let |X] denote the number of cells in the ACC (S, X, c, rk) and let p denote its order (maximum rank). In each k- k-CCWL iteration,
refine labels all k-tuples of cells and for each tuple aggregate over all pairs (ax, B) E X via the refinement context ( (x)). From definition Section 3 and Lemma B.1
obtain the following bounds:
The number of tuples is | = n.
For fixed k-tuple æ. in order compute D (z), we require scan all pairs (a, 3) e X² and, for each such pair,
1. Compute the (k + -attmmi type a 2 and (4) Read the previously computed colors X (xla//t) and Xk (x[B/i)) for i 1,..., to compute the double-shift sequence A (8)
(1)
(z; a 8).
For fixed & and p. if we store adjacency, ranks, and attributes in precomputed data structures, both store adjacencies
operations can be implemented in time O(1) per pair (a, 3). In practice, in memory of On??), whose entries show the topological adjacency relation between each pair of cells. In addition,
store ranks and attributes in arrays of size (n). Therefore:
Per-iteration cost: One²) tuples times O(n²) pairs per tuple.
Number of iterations: according to Lemma B.I] the refinement process terminates after at most T < n iterations, since each iteration strictly refines partition of X and there are only = tuples.
Therefore, obtain worst-case bound
(IME()-CCWL) s OOTTT''' x2) S ((22+2)).
with space complexity (2x,(k))))) to store tuple colors. addition, we need the space for
ACC itself (adjacencies, ranks, attributes), which is at most quadratic in n for fixed rank. Therefore, the overall space complexity is m2x(22))) for fixed k.
Note that for the case k each cell is still in On²)):
again store the ACC in O(n²) space, and the per-iteration cost for
1. We need to aggregate colors from boundary and coboundary cells, which can be done (n))
2. We need to aggregate at most (n²²) color pairs for corresponding lower and upper multisets in the refinement process.
We know that the refinement process terminates after at most T S 1, therefore, TIME(1-CCWL) < OT nn) C O(n)),
B. BROADCAST-ANCHON CELL
first analyze the alentical-vs-disjoin construction for uniform ACCs, then we establish the disjoint-or-identin property (Proposition 3.1), and finally we prove the equiv- alence results in Theorem 4.1 Theorem 5.1 and Theorem 5.2, Our aim is to make explieit all intermediate arguments, ensuring that the rigorous.
We proceed follows:
game-aggo correspondence is completely
For two uniform ACCs A = &A, CΛ) and B = (Sp, X'. rkp, cp), the k-CCWL algo- rithm distinguishes the uniform ACCs A and B, if their stable global labels are different. In other words, k-CCWL distinguishes A and B, if
(00) XA. + X
(00)
This can also be interpreted as the existence of color C such that
Ku x (2) (w) (w)= =
foe x
(00) (v) (v) = cc
X
16

---

Published as a conference paper at ICLR 2026
To perform k-CCWL test on these two uniform ACCs via k-CCWL, first add fresh cell with rank 0 to each uniform ACC and then connect this fresh cell to all O-ranked cells via 1-ranked cells. Then, we apply k-CCWL these two modified uniform ACCs and check if their stable global labels are different. Formally, let a" and b" be the fresh O-ranked cells, and define the two new uniform ACCs A and B" as follows:
A" = KA,
(8)
where
SA- fa')
(9)
X'A- Ufaa x1) x E Xa(0)) fa'),
(10)
(rka(1),
if Nr, if x a', if x = fa", x'), ) E (x))
r (x)
0,
(11)
1,
(a(#), a fresh color,
if XA.
ca-
if = a" if x = {at ,'), x' E (A())
(12)
a fresh color,
Similarly, for B":
B" (S rkg.
(13)
where
SB- SB (bb),
(14)
Xg- = XB U ffb"
axE E ((0))U(b")))
(15)
(k)()),
i E Xn, if b4, if (br ,'), E (n()))
(x)-(x)
0,
(16)
1,
CB(Z), fresh color,
if E XB,
Cn- (x)
if = b"
(17)
a fresh color, i = (b x }, x' E X0(
Next, we compare XA* and XB-.& to determine whether A-CCWL can distinguish A and B. Note
(c0)
(co)
that the fresh O-ranked and 1-ranked cells are initially colored with a new fresh color, so they can be distinguished from the original cells in and B. We need also to mention when during CC isomorphism test, the only way to define mapping between A and B is to map the fresh O-ranked cell in A to the fresh O-ranked cell in B", and similarly for the fresh l-ranked cells. Therefore, we have the following result:
Remark B.2. There a CC-isomorphism between A and 8 if and only if there CC- isomorphism between A and B; in particular, adding broadcast-anchar cells does not affect whether A and are CC-isomorphic.
For simplicity and to avoid redundancy, we use A and to refer to these new uniform ACCs, previously denoted by A' and 3" respectively.
Intuitively, these fresh cells act as broadcast agents to help distinguish A and B. We show that there is difference in the global stable coloring of these two uniform ACCs, the fresh cells will propagate this difference to all other cells in A and B.
Base path. In a uniform ACC I (S, X, rk, c), the base distance defined as follows: the base path of a cell x E X, is sequence of cells x T1........ Et, such that
Ft is a non non-fresh O-ranked cell,
for every 0 < i < t, xr E (1(+;11) for some Nr E NN,, and the path has minimal possible length and we define drase (2) -
17

---

Published as a conference paper at ICLR 2026
We denote base path for by (2)).
The goal of the following lemma is to prove that if 1-CCWL test is performed on A and B, and the stable coloring of the fresh cells in two uniform ACCs is different, then the set of stable colors of all cells in A and B are disjoint. In other words, if the stable coloring of the fresh cells in A and B differs, this difference will be broadcast to all other cells in A and B.
Lemma B.3. If A = AA,ANA CAA and B = (SB, XB, r are two uniform attributed combinatorial cell complexes, and 1-CCWL is performed on these two uniform ACCs. Let a" and (oc) b' be the fresh O-ranked cells in XA \ NA and Xg- \ (B, respectively. If X1,A (a*) # X1,B (b"), then
(x)
{ 100) XI,A
(xA) DA E KaI n (00) X (xB) UB E XB 0.
L (S, 2' rk, c) be uniform ACC. In the 1 1-CCWL algorithm, each cell X' is initially colored with the pair of rc()), Therefore, the stable 1-CCWL coloring state, the cells of the same color have the same rank. To extend this, in the stable coloring state, if a cell A E X'A has X1.A (a C. then only cells TB E X'B with (x can have color C as their stable color. This is because if the base distances of two cells xA and a are different, then one cell receives messages from a O-ranked cell earlier than the other cell during the 1 1-CCWL iterations, which leads different stable colors for these two cells. Let Dbsse be the maximum base distance over both ACCs, which is defined as
Proof of Lemma B.3
(
D Dasse max max de (x.), max d c (FE)
(18)
AAAEAA
#gENe
Hence, the following statements equivalent:
The multisets of colors of cells with base distance are disjoint in A and B, for all t S Dasee
The multisets of colors of all cells are disjoint in A and B.
For E [Drase Jo. define the multisets of stable colors at base distance by
(o0) (L) == { Xi,A (x)
VA E XA, diase (x = 1
(19)
(t()) = { X1,8
(00) (x)
xB E XB, d = t }.
(20)
Then the first statement can be formalized as
(C =
for all t E [Dbaselo-
(21)
Furthermore, the stable coloring state, the color of a cell remains fixed and still dependent on the colors of its neighbors. Since the stable coloring has been reached in both uniform attributed combinatorial complexes A and B, if for two cells x E XA and Tg E XB. there exists a cell the boundary neighborhood of cell T with completely different color from any cell in the boundary neighborhood of cell TB. it implies that the stable coloring of & and JB are different. Therefore, for any two cells IA XA. and FB X', if there exist a cell ya E NN((A, such that for (oo)
(oo) all yB E NB [B RB) X1.4 (yA) # X1,B (yB). it follows that XI.A (cA) + X1,8 (#g). The same argument also applies to the coboundary. lower, and upper neighborhoods. To prove Lemma B.3 show Equation (21) using induction f, which will imply the lemma.
(c0)
1. Initial Step:
We prove the equality in Equation h2I)holds for = 0. The cells with base distance O, are exactly the O-ranked cells in the uniform ACCs A and B. The fresh cells a" and b* are connected to all O-ranked cells in their respective uniform ACCs. By assumption, Xi.A (a*) +
(xc)
X1,B (b*), which implies that their adjacent O-ranked cells do not have any common color. Thus,
(oc)
(0) (() = 0.
Inductive Step: Assume that the equality in Equation holds for = i 1, then
Ca(i 1) Cp 1) 0.
(22)
18

---

Published as a conference paper at ICLR 2026
We prove that the equality EEquation (21) holds for t i. Consider the multisets of colors of cells with base distance in and B. Since and B are uniform, each i-ranked cell has at least one adjacent cell with base distance cells with base distance - are disjoint in and B. Consequently, the multisets of colors of cells with base distance i must also be disjoint in A and B. Hence, the equality in [Equation (21) holds for = i, and
1. By the inductive hypothesis, the multisets of colors of
Ca(i) n (i) =0
(23)
By induction, Equation h2lds for all Dbsse- Therefore, the lemma is proved.
We now show that if there is a difference in the global stable coloring of other cells, the fresh cells will capture these differences. Formally, we state the following lemma:
Lemma B.4. Let = = (SA,AA, rkA, CA) and = (SB, XB, rkg, CB) be two uniform attributed combinatorial cell complexes, and 1-CCWL performed on these uniform ACCs. there exists a color C' such that
H XA X1,4 (xx) (xx)= -c c} * f ex X' Xi. (2n) - c
(00) then X1,A (a*) + X1.B (b*).
(00)
Proof of Lemma B.4 We proceed with the same idea as in the proof of Lemma B.3 which that cells of the same color have the same rank, because each cell is initially colored with the pair of its attribute and its rank. Therefore, it is sufficient to prove that if there of color C' with base distance in A and B, then the stable coloring of the fresh cells a" and b* in A and B, respectively, are also different. Let D Dasse be the maximum base distance over both ACCs, which is defined as
different number of cells
d (EA), max B (EE)
D bass == max
max EAEAA
(24)
Hence, we can conclude that the following two statements are equivalent:
1. There exists color such that the number of cells with stable color and base distance is different in A and B, for some t E Dosselo.
2. There exists color C such that the number of cells with stable color C is different in and B.
For E [Dbase lo, define the multisets stable colors at base distance by
Ca(C, = { xA X'
(00) XI.A (#a) C, d ( (I =
(25)
CB(C,t) = f XB
( (#B) C, af (x (xB)=
= =1
(26)
The first statement can be formalized as follows: There exists a color such that
CC(C,, * (C, t)], for some E [Dbseelu
(27)
Instead of directly proving Lemma B.4
we now prove the following lemma:
Lemma B.5. Let = (SA, XA, rk cA) and (S XB, rk CB) two uniform attributed combinatorial cell complexes, and 1- 1-CCWL is performed on these two uniform ACCs. If there exists a color C. such that
(C)
for some E [Dbaselo-
(80) then XI.A (a*) X1.B (b*).
(20)
Next, prove Lemma B.5 by using induction on
19

---

Published as a conference paper at ICLR 2026
1. Initial Step: We prove Lemma B.5 holds for t 0. The fresh cells a* and b are connected to all O-ranked cells in their respective uniform ACCs. Therefore, if there is a different number of cells of color C' with base distance t 0 in A and B, then a" and b will have different colors. Formally, if for any color C, holds that
[Cx(C,0] + [CB(C,0),
then it implies that
(00) X1.A
(a") # Xi.B (b").
((c)
2. Inductive Step: Assume Lemma B.3 holds for / i. We must prove that if there exists color C' such that
CA(C,, * (C)(C,
(28)
x(o)) (a") X1.B (b*). By the induction hypothesis, for any color C. the number of cells with stable color C and base distance i 1 in A and must be the same. this not the case, the lemma has already been proved. Thus, it is known that for all C, it holds that
then
(00)
[C, - 1) = (C, 1)].
Since the number of cells with base distance i is equal, but the number of i-ranked cells with stable color C' differs, there is inconsistency in the adjacency relations between cells of base distance i with color C' and cells of base distance í. Therefore, the lemma is proved for Formally, without loss of generality, assume there is a color C' such that:
[C,(C, > (C,(C,
In uniform ACC, each cell of base distance i must be adjacent to at least one cell of base distance i Assume that a cell of base distance i with color connected cell of base distance i - 1 with color C", Since the stable coloring has been reached in both uniform ACCs, the number of adjacency relations between cells of base distance with color C and cells of base distance - 1 with color C' should be the same in A and B. Formally, if we define
MA VAEN(A, for some N E NNN (xi, (5x) xi.A (WA)) (C,C") ( doasee (UA) +1=i
(x = (FA.BA)
UB E NoW (IB), for some N E (00) (IB), X1.B (yB) = (C,C), (xL.
WB(1)= =
(B yB)
(XB) d (yB) +1=i
it means that we must have ( [WB (i)). the stable state, this implies that each cell of base distance with color C must have the same number of adjacent cells of base distance i - with color C'. Since there are more cells of base distance with color C in A, the pigeonhole principle ensures that at least a cell of base distance i with color C in A has fewer adjacent with color C' than required. This contradicts the assumption that
cells of base distance stable coloring has been reached. Thus, (C, A (CB(C, Hence, the lemma is proved for = i.
Since
Lemma B.5 holds for all E [DbaseJu- we conclude that Lemma B.4 is proved.
Lemma B.6. Let A (SA, KA, CA) and B (SB, XB. rkg, CB) be two attributed combi- (xc) natorial complexes, and let k- 4-CCWL (k 2 2) be performed on these two ACCs. Let Xk.A (xA) =
X (xx) for some XA E X' and xB E X Then,
(oo)
{ (atpe)((xaAaa)) ( as, ea
= =f (alpa=2(xRapan) A A (xn; an, an)) an OnExN]]
20

---

Published as a conference paper at ICLR 2026
Proof of Lemma B.6 For any SA E NA and og NB, if
(atp:-2(xAaABa) A (x aA BA)
= =xatpu=((xpagas)
( (xB; (B,0B) kn
(00)
then a = AA. This follows from the fact that the atomic type of a k-tuple encodes the equality of the cells in the tuple. Furthermore, for any an, 3B,38 An and as XA, if
(atp== A (00) K. (xAi (A,
=(atpH=2(xaagág) A (0c) ( (xg: ag.
(00) then an = Sn. Since XE,1 (x,) = Xx.B (xn), it follows that (00) (x1) = D (00)
(00)
KB (xn). Therefore,
{ (ttp) (00) (xA: aw. aA. E EXa
= (
M (xn: an 3n) an: Br Xn
By the above observations, restrict the left-hand side a = BA. and the right-hand side to = BB, the equality still holds. This completes the proof.
Combining Lemmas B.3 and B.4 we conclude that when the CC isomorphism test is performed on A and B via k-CCWL, the stable global labels of these two UACCs are either entirely disjoint, or identical. This result is formalized the following theorem:
Proposition B.7 (Identical-ve eleetticl-vs-disjonn vs-disjoint,. Let A = (SA, NA. rka,Ca) and B = (S XB. rkg, CB) be two attributed combinatorial cell complexes, and CCWL is performed on these two uniform ACCs. Then, only one of the following two cases can occur:
Xiid (xx)
xA E SaExt
(20) (xB)
XB E X 11
XR.B
. Xxhod (xx)
XA E EaEx
(00) Xr (xB)
XB E N } 4.
Proof of Proposition B.7 We prove if there exist two k-tuples us E X and us X such that (00)
100)
Xk.4 (ux) = Xk.B (un), then
{ xA 2
(00) Xk. (x1)= = cc (0c) X (xB) = c.|. for all color C.
(29)
= {xB= X3
Note that [Equation holds if and only if the multisets of stable colors of k-tuples in A and B are the same, which is the first case in Proposition B.7
If k: 1 and there exists color C such that (0o)
{ E XA
(z,) = c} * #1{00
(00) (zn) = (zn)= cc
E X'
then by using Lemma B.4 it follows that the stable coloring of the fresh cells a* and b" in A and B are different. Furthermore, by Lemma B.3] be concluded that
{ Xi, (ra) sA E 2x
(00) (wn) xn XB 0.
Xi,B
However, this contradicts the assumption that X1,A (WA) holds for k 1.
(oc)
(co) X1.8 (uB). Therefore, Equation (29)
If l: 1, then for T (A, B} and any color C, define
Ff (x,
x
X (v) C, diff v) = =P] for any x X and PC [k]. (no)
This is the set of all k-tuples in X that have color and differ from x precisely in the positions indexed by P. The proof proceeds by induction on [P| to show that for any color C', holds that
|F (us, P)] F (un, P)1, for all P C [k].
(30)
21

---

Published as a conference paper at ICLR 2026
1. Initial step: We prove the equality in Enquatiio (30) holds for P with cardinality at most It is known that Xa,4 (uA) Xx,8 (uB), implying the equality in Equation (30) Let P (i)
(oc)
for some i [k]. Since X (uA) = X2,B (uB), it follows that D (UA) = ( (ug), and by Lemma B.6
(co)
(00) (u)) xa 1n E 2 (aIDAA-2(MAAAA A And
{ at
4 (20) (uB: 2B.28)) 2B E Xz}
Thus, (u (2}) (un, {i}).
2. Inductive step: Assume that the equality in Equation holds for P with cardinality at most n 1. We must show that it also holds for P with cardinality n. By the induction hypothesis, for any color C²:
FF (u,, P') IFg (UB, P'),,
where p' = P) {m for some P. Then, for any color C:
Fu P)1
Σ
E
FX
C²
WAEFA (Ma)(m))
Σ
Σ
IF
BBEFR (uadm))
F (un, P)].
Thus, the equality in Equation (30) holds for P with cardinality n, which completes the proof.
Algorithmic benefits of Proposition 3.1. The Proposition 3.1 states that when performing k- CCWL on two uniform ACCs, the stable colorings of these two ACCs are either identical or disjoint. This property can help to improve the performance of comparing global stable color of two ACCs. Formally, without this property, to compare the global stable color of these two uniform ACCs, we need compare each color in the first ACC with each color in the second ACC. This requires O(I.Xa (aa*)) comparisons. However, by using the identical identical-vs-disjoinn property, we can reduce the number of comparisons to O(min (1x% (x which is significantly more efficient.
Uniformity requirement in Proposition 3.1 As it can be observed from the proofs Lemma B.3 and Lemma B.4 the uniformity is sufficient maintain flow of information from fresh cells to other cells, and vice versa. As a result, the ddentical-vs-diste the following example, show that the uniformity is also necessary for the identical-vs-disjon property to hold.
property holds. Now, by giving
Example B.8 (Non-unifee uniform ACCs breaking conntica-vvs-isjoone Let A = (SA. rk CA) and B Xn, Cp) be two attributed combinatorial cell complexes. The ACC A is defined as follows:
SA (ai, 02 03, a4, as, (6)
xx(0)= {ai), (a2), fas), {as), {as), {as)].
. X1(1) fai, a2) faz, ast, fai, as
x2(2) = { far, as, }
XA (0) U Xx) and
the attribute function с assigns the same attribute to all cells in XA-
22

---

Published as a conference paper at ICLR 2026
Then, the ACC B is defined follows:
SB = {br b2, b3, by, bs, b6}
(0( = { {b1). {b2}. (bs), {bi), 1bs {b9}
Xb(1) (b1,b2) b23. (02, (b2, b.s]
Xb(2)
(6r,b6, bo, bol).
XB XB UBB())) (2),), and
the attribute function og assigns the same attribute all cells in XB.
It can be seen that both ACCs are non-uniform, since in both of ACCs there are 2-ranked cells that are not adjacent any 1-ranked cells or any other 2-ranked cells. Therefore, these 2-ranked cells cannot receive any information from other cells in their respective ACCs, and they are already reached to their stable state. The same argument applies to the cells {a4). {as}. and {as} in ACC A and the cells {64). {65}. {bg} in ACC B. However, in A, the 1-ranked cells form a triangle, while in B, they form a path, and thus, the stable colors of 1-ranked cells A and B are different. Therefore, the stable coloring of these two ACCs are neither identical nor disjoint, which shows that the uniformity is necessary for Proposition 3.1 to hold.
03
b
by
ba
be
{ba bn. bu)
b4
04; as; 06
0.4
Figure 3: Non-uniform ACCs from Example B.8 Blue edges denote 1-cells; red shaded triangles denote 2-cells whose 1-faces are not in the complex (dashed edges), so the 2-cells have empty boundary.
C LOGIC
In this section, we first familiarize the reader with the basic concepts of logic, including syntax, semantics, and satisfiability. We also give the concepts Topological Counting Logic TC2, which are extensions of First-Order Logic.
Definition C.1 (Language). Let Σ
symbols called the alphabet. The set L is called language if T. C Σx The elements of I. are called strings.
Example C.2. Let Σ = {0, 1}. The set I Σ a language of all binary strings. To familiarize the reader further, consider the English language. The alphabet Σ' consists of all the letters in the English language, both uppercase and lowercase, as well as punctuation marks and spaces. An example of language L with alphabet I' is the set of all valid English sentences. This language includes every possible combination words and punctuation that form valid English sentences.
C.I FIRST-ORDER LOGIC
A first-order logical language I. is defined by the following symbols:
23

---

Published as a conference paper at ICLR 2026
Variables: Varg
{21, 22,1,2,220 23....}
Predicates and functions: The predicate symbols Pl, P2, Ps...., ......,,....... ,, the binary equality symbol and the function symbols fI, f2, fa....,
Logical connectives: A,
Quantifier: (there exists)
Parentheses and commas: (,)
Note that the O-ary function symbols called constants. It is possible for logical language to not contain any function symbols or any predicate symbols other than equality.
Syntax
The terms of the language are defined as follows:
Each variable is term.
If (2..2..... In are terms and is n-ary function symbol, then [(1,, 12...., ,......,))))))) (n) is term.
The formulas of the logical language are defined as follows:
f2......... in are terms and P is an n-ary predicate symbol, then P(t1, .2.....,.... (n) is formula.
If l and l2 are terms, then (41 = 12) is formula.
If á and db are formulas, then ø A & is a formula.
If á a formula, then - formula.
If á is a formula and x is variable, then Ezo is a formula.
The formulas built from the first two rules called atomic formulas.
Definition C.3. Let ø be formula. The set of all variables in á is denoted by Var(ø), which includes variables that appear in o. The sets of bound variables, denoted by Bound( (), and free variables, denoted by Free(o), are defined recursively follows:
1. If Φ is an atomic formula:
Bound (Φ) = 0, (ree(() = Var( (Ø).
2. If ④b mbb
Bound ()) Bound( (r)e = Free(1))
3. If U1 4/2:
Bound ()) (ound( (ound( Free(e) Free(1)1 U Free(U)).
4. If 6 = Qua where Q is a quantifier:
Bound () BBound (b) (z), Free(Ø) Free(v) \ {x).
Let V C Varz. The sub-language L(V) is the language that syntactically restricts the variables to V. using only variables from V.
Semanties
mathematical structure S is (D, PS,...,
where:
D is a non-empty set called the universe of S.
S.. C n for r E [i] are interpretations of P, in S, where n is the arity of P,.. 1 : D D for [j]] interpretations of in S, where is the arity of fr.
mapping f Var, - D is called a partial valuation. The term-mapping μ assigns each term t L(dom,,) to element in D as follows:
If is a variable, then (t()) = ((t).
If f(1,, -2.--.,,.... .n),, then pat)= 1 ... (((n)) for bi].
24

---

Published as a conference paper at ICLR 2026
Let S be structure and μ Varg - D partial valuation for L. For any formula E L with Free(() - domp, the satisfaction relation S. μ & (or S. satisfies Φ) is defined as follows:
If Φ = (.(t1, ,2,,..,, ,t),,,,,),, then S, - Φ iff (T((t),,T ..... ((bt)) ((n))) P.S.
If Φ (41 = 12). then S, F Φ iff p(() = (112).
If Φ = 1i A 1/2, then S F iff S, 1 and S, 1/2. 1/2.
If Φ - then S, F Φ iff s
If Φ 1/ then 5, 14 = Φ iff there exists E such that S, 11 - c) F
Here, fu(;; > cl denotes the partial valuation that maps to and agrees with all other variables. The all first-order logical languages is denoted by FOL. We use the notation FOL; denotes the set of languages containing at most & variables.
C.2 TOPOLOGICAL COUNTING LOGIC
Intuitively, we introduce a new variant of first-order logic capable counting the number of pairs of elements satisfying given property. To do this, we define over pairs of variables. This new quantifier is called the pairwise counting quantifier and it written 3dth for any N E No. Although this symbol is the same the standard counting quantifier, its syntax and semantics differ. This pairwise counting quantifier 3 (Iz; counts pairs of elements the universal set. Formally, if Φ = EN (xt, 4t, then S, 1 F= Φ if and only if there exist at least N pairs of elements (c1, 02) D such that
counting quantifier that counts
S, c1. 2. c2] F db
Here, plaa + C1, + 02] is the partial valuation that maps I, to c1 and to c22 and agrees with all other variables. The pairwise counting quantifier be recursively defined in terms of standard quantifiers as follows:
1. (x,, 2y is equivalent T.
2. 3N+ (x1, 2 is equivalent to
Er,32, (v 33 (v. (-(( -zz 2) 01y/21,2/211)
Here, Vly/2,, x/2,] is the formula obtained from & by replacing all occurrences of x; with y and all occurrences of 2j with Although it is possible to recursively define the pairwise counting quantifier, it needs extra variables and is inefficient. Hence, the new quantifier introduced to increase the expressive power of the logic.
The language TC2, finite topological counting logic with variables, is defined by the following symbols:
Variables: Vartc, = (x1, T2,
Unary predicate symbols: R1, R2, Rg.... ., Rp and PI, P2, Pa...... P
Binary predicate symbols: E.,n, ENc, EN, ENG and
Logical connectives: A,
Counting quantifier: EN for N N
Parentheses and commas: (.)
Syntax
Since the only terms in the language TC2 are variables, the formulas of the language are defined as follows:
If .; a variable, then (x;x) is atomic formula for [plo.
If Jy is a variable, then Ps(x)) is an atomic formula for E [2].
If wy and iy are variables, then E 24,) Noo (;), E. (11, and ENG (xi, 2ry) atomic formulas.
"The notation S. p. # indicates that y do satisfy the formula tb.
25

---

Published as a conference paper at ICLR 2026
If zy and 2y are variables, then (2; 22) is atomic formula.
If Φi and de are formulas, then Φ1 A d2 is formula.
If Φi is a formula, then - is formula.
If Φi a formula and x; and xy are distinct variables, then 3 (xx, #5) ) a formula.
In terms of free and bound variables, the rules are similar to those of first-order logic, except that if
Φ 3 (ry, RTy) 1 then:
(o) ( U (2i,ay) Free( = Free(1) \ (1:,2y)
Semantics
Let r &,, be attributed combinatorial complex. Consider the following structure:
(X, Ro...... ......,,p... Rp, CI....,,c,,. EV ENVO ET 1
(31)
where R, = (r) for any E ploo and
1} for all s [e]. For any valuation μ f mk} + X with Free(Ø) C domp, the satisfaction relation I' F defined as follows:
C, = fi X (c(z)),
If Φ = (x;), then r, 14 F o iff u(z;)= E R..
If P. (z.), then F ó iff u(z;) C..
If N (z), ky), then r, ト iff (p(=)), ((z;)) E E
If Φ = Ne (z), ., then r, iff (u(2,), p(z,)) E NNc.
If 6 E (z4, 4;), then
(p(z.), ((z))) E
(u(zz), ((x;)) ET If' 6 (z; 2,). then I, = 0 iff =(x,) p(zz).
If Φ = Æ. (z,, ) then r,
If Φ = (t/1 3 then F = iff , th1 and r, |= 1/2.
If +6. then 1 Φ iff / vb.
If Φ I (z) v/ then r = iff there exist at least pairs of elements (c1,02) E X2 such that I" 12, C1, c2] wb.
Therefore, r = (S, X. rk, e) can represent a structure in the language TC₁. For simplicity, instead of using the structure 31 we use r itself as structure.
Guarded logic GTC3. The guarded logic GTC3 is fragment of TC3, which only allows to have formulas of the form x; zy, rank and attribute predicates, and formula of the following form:
Φ m
Ø (I()) A v2(x),,
Ø (M(,,=) = (,,(,,))) A
6 = (E (,,a) E E (2. v) vi(() A (e(())
where A' (NB,No). (2) E {[N, Nc) and Φ vh, 1b are again GTC3 formu- las. The semantics are inherited from TC3-
C.3 GENERAL NOTATION FOR LOGICAL LANGUAGES
Let L be language with at least variables, S be structure with universe D, and μ be partial valuation for L. For any formula o L, when it is said that S, }= or S, j o. it necessarily means that Free(e) C dom,, Otherwise, the satisfaction relation is not defined. In cases where dom,, 0, instead of writing S. μ + ó S. μ é. it is said that S F & S Y é. respectively. Each μ = (WI.... Mk) D can represent partial valuation such that u(x;)) = 14 for all e [k]] Additionally, when we have that Si, μl and S2, U2 agree on a formula o E L, it means that both St, fn and S2, pa either satisfy & do not satisfy Φb
26

---

Published as a conference paper at ICLR 2026
Definition C.4 (L-Equivalence). Let 1₁ and S2 be two structures for language L, and let μl and H2 be partial valuations corresponding to S1 and S2, respectively. The following statements are equivalent, and say St, Yn and S2, H2 are L-equivalent:
S1, P1 and S2, #2 agree on all formulas @ L.
2. S1, 52. M2-
3. 51 and S2, μ22 are not L-distinguishable.
These statements are equivalent to the following conditions:
dompn = dompa
. For all Φ E I., it holds that SI. j41 += Φ if and only if S2, Φ.
In terms of TC2. defining the length and depth of logical formulas can bring an inductive approach solving the problems. For formula ø, len(ø) is defined recursively follows:
1. If Φ is an atomic formula, then len( (e) = 1.
2. If á is of the form mys then (en(Φ) (Ø) 1 len(v))
3. If ại is of the form 4/ A 1/2, then len( = + (en( + len (1/2)))..
4. If s is of the form 3 axp or 3N (Ix y) then len(d) = 1 + len()))
The quantifter depth refers to the maximum nesting level of quantifiers within formula, indicating how deeply quantifiers are embedded. For a formula o, depth(o) defined recursively as follows:
1. If Φ is an atomic formula, then depth(d) 0.
2. If Φ is of the form mbb then depth(o) Φ) = depth(w)..
3. If Φ is of the form d/ A 1/2, then depth(o) max(depthi (th)), (e))
4. If 6 is of the form IN xu or NN (I, v)v, then de = + depth(v)).
The notations TCk,, denote the of formulas in TC2 with quantifier depth most respectively.
C.4 RELATION OF LOGIC TC₁ AND k-CCWL
In this section, explore the expressive power of k-CCWL in terms of logic. Intuitively, the following lemma shows that there exists a logical formula capable of characterizing k-tuples with the same atomic type value.
Lemma C.5. Let r (S,X, Krr, c) be combinatorial cell complex and let be atomic type value. Assume the representation of a is as follows:
o where for all Ty F, X,
NB 21.22
No N. 11.3
axi.
Nr
o ... E. : 2
Tna,, encodes the equality information between x; and Vy
Ni an NNe aziay, awia; encode the boundary, coboundary, lower, and upper adjacency relations between I; and Zj respectively,
a',, encodes the information about ce(x:), and
atk encodes the rank information of Tz-
Then, there exists formula in TC2 that characterizes k-tuples having the atomic type value a. Specifically, there exists a formula &n in TC2 such that for all x E X*, f holds that:
T,x da if and only if alPp (x) =a.
Proof of Lemma C.S lows:
To prove this lemma, we construct the formula &a in TC₁, iteratively as fol-
27

---

Published as a conference paper at ICLR 2026
1. Initialization: Let 0. ()-
2. Equality: For each 1 S i < j S k; if axy,ay = 1, then Oa = da A (ai = Iz); otherwise,
da da A (xx; xz))
3. Adjacencies: For each N E
Ny,, if and Ca then 0a Da F> (z;, zy): otherwise, &a = Qa A -BN T.))
4. Color: For each 8 [4], oz.. = 1, then da = Φa Pa (z:); otherwise, da = 0a A -Po (P:(.
5. Rank: For each E [p]o. if a 1, then Oa = da A R2 (z:); otherwise, d. d, A A
Now, we prove that the following holds:
1 da
(t) =a for all x E x
We prove this in two directions:
1. If atpr, (2) a, then r F Pa: By construction, Pa is built to match the atomic structure
a. Thus, Paalpr (x) = a, directly follows that r, x }= da.
2. If d.. then atpr, (x) a: Assume, for contradiction, that I' x - 6 and atpr, (x) b o a. This implies that r x += db- Therefore, r, F= da A Φb. which leads to r, F= 1. This contradicts the fact that T is non-trivial and valid combinatorial complex.
The next lemma shows that if the initial coloring of two ACCs A and B differs during the execution of k-CCWL, then there exists a quantifier-free logical formula in TCg that can distinguish these two ACCs.
Lemma C.6. Let A (SA, Ik, and B = (SB, XB, rkB, CB) be two attributed combi- natorial complexes. Let uA X and up E X If A, and B, ug agree on all quantifier-fre formulas in TC,, then it implies:
(0) XR. (u^) = Xx,B (un)
Proof of Lemma C.6 Since A, u and B, un agree all quantifier-free formulas, A, Us and B, un agree on (I,), (x,) for all i E [k] and E [plo- Consequently, we conclude
(kA(uA( = (kn(4 for all i E [k]]
Similarly, A, us and B, up agree on (P, (2:),, PP. (x:) for all E [k] and & E [4] Therefore, we conclude
ca(uA(ε:)) cz(() for all [k].
Moreover, A, a and B, up agree on = = Zy, -2; x,,} for all i, E [k], which implies:
(A(x,) uA(x,) + "g( up up (r,)) for all i, [k]
Furthermore, A, uA and B, ug agree on {E (æ,, xy), (N..Nc.NN,.W.) Therefore, we conclude for all i.j (k), and E Nc.
EE (2,, x1)} for i e [k] and M
ua(z;) E EV(A (x(x))) + up( E E uB(x,))
Thus, we conclude that A, B, ug, and consequently, (t = atp (UB). There- fore, Xk,A (uA) = X (uB). For lo = 1, having (ua(z)) = cp (us(z)) and IKA (ua(a)) rkg (un(x)) is sufficient to obtain the desired result.
The following two lemmas show that if two ACCs A and B are distinguished by k-CCWL, then they can also be distinguished by TC,-2. Furthermore, there exists logical formula in TC on which these two ACCs do not agree
28

---

Published as a conference paper at ICLR 2026
Lemma C.7. Let A (SA, Ikg, CA) and B = (Sp, IB, (BB be attributed combina- torial complexes. Let U E XA and up E XB. If A, u, and B, ug are not AiCygiistinguishaall then
(20) (UA) = X1.B (uB).
Proof of Lemma C.7
We prove
A, U.4 CTC3,1
uB uB =
(0) XI.A (UA) = x1.1 (uB), for all t No.
(32)
by induction on L.
Initial step: We prove that Eqquttinn holds for 1. 0. According Lemma C.6 if A, U.A. (0) and B, agree on all quantifier-free formulas, then X1.4 (uA) = X1,B (uB). Thus, the result holds for / = 0.
[0)
2. Inductive step: Assume that Equation (32) holds for all f [n 1oo- We must show that it also holds for / = n. For contradiction, assume xi, (ua) # Xi.8 (un). Then, there are two cases to consider:
If xi,A (n-1) (wx) * X1.B (un): By the induction hypothesis, there exists a formula e E GT C GTC3,n such that A, u. and B, un do not agree. This contradicts the assumption.
(n-1)
If ( (uA) * M (uB): This case only needs to be analyzed if the aggregated values of either the boundary neighborhood or the lower adjacency neighborhood. The reasoning for other types of neighborhoods is similar. Suppose cB.(n) (A, UA) + c..(m) (B, uB). Then, there exists a color C such that:
Has E NNBA, xi.A"" (aa) (ca)=cH * KaB= (B((B uB)
(n-1) XI, (aB)
o)
Let N be the cardinality of the larger set. Since cells have the same color in iteration n - 1 if they agree on all formulas in GTC3,n-1. Let the be the conjunction of the formulas in GTC3,n-1, which characterizes color C on iteration 1. Formally, for any color C:
(n-1) I, = Dh + Xir
(#r) C, for all I [), and ær E X.
Now consider the formula:
3= ( (5(()2) A (N (x2 = =33) )
It follows that A, ua and B, un will not agree on the formula & E GTC and con- tradicts with the fact that A, and B, uB agree on all formulas in GTC Moreover, if cl.(a) ua) + ctil)) wB), then there exist colors Ö and Ć such that
a E (A, uA), BA E (A,uanaa) naa)s (n-1)
ag E E uB),
BB EN uB naB),
BA)
XL.A (ax) =Ō;
#
3B)
(n-1) (an) = Ō
X1,8
X1,A (8x)= ò
(n-1)
X1,8 (3n) ò
(n-1)
Let N be the cardinality of the larger set. Consider the formula:
NN 2s) (22) (53))))) (N, EN (I3, E.V (23, 222) )
Again, A, ua and B, uB do not agree on the formula & E GTC3,,, which contradicts the (n) assumption. Therefore, XI.A (M^) = X1.8 (ug).
(n)
Hence, the lemma holds for all E No. and we conclude
A, U = BBuB = (20) (uA) = X (uB).
GTC,,
29

---

Published as a conference paper at ICLR 2026
Theorem C.8. Let A (Sa, NA. rkA. and B (Sp, Ng. rkg, cB) be two attributed com- binatorial complexes and let uA E Xy and ug E B.. Then if A, UA and B, ug are not TC*42" distinguishable, then:
(00) (UA) Xk.B (u
(00)
Xk.A
Proof of Theorem C.8
We prove
(t) Xk.A (uA) = Xk.B (uB), for all & No,
A, U 1C
B
(33)
by induction on L.
Initial step: We prove that Equation (33) holds for /. 0. According Lemma C.6 if A, MA (0) and B, agree on all quantifier-free frre formulas, then Xk.4 (uA) = X (uB). Thus, the result holds for t = 0.
(0)
2. Inductive step: Assume that Equattin (33) holds for all f [n 1Jo. We must show that also holds for / = n. For contradiction, assume XR.A (uA) # Xx.B (ug). Then, there are two cases to consider:
[m]
(n-1) If Xk. (ua) # XK.B (ug): By the induction hypothesis, there exists formula ø TC++2.-11 C TC+22, such that A, ua and B, ug do not agree. This contradicts the
assumption.
If D (ux) (())
D (n)
B (un): there exists k-tuple of pairs of colors C
Ck
and an atomic type value of size + 2, such that:
K(os, EX (atPE)((()CιянA) A " (uxi (A = (a,
* (a BB) x3 (atp:42(uaaBBs) k
(n=-") (uz; aB, aB, (a, O)
Let N be the cardinality of the larger set. Cells have the same color in iteration n if they agree all formulas in TC++2nn Let the be the conjunction of the formulas TC which characterize color C' in itcration 1. Formally, for any color C:
P. F th
(a-1) (ØT) = C, for all r {A, B), and ær X. XR.
According to Lemma C.5 let da TCx42 be the logical formula that characterizes the atomic type value a. Formally:
T F do atPr,4+( =a, for all r E (4, B). and ær E X.
Now, consider the following formula:
& 3 (#1+1, @a (0a (G(())....TTtt))) IR+2) A
(A (Vc de, [m (2//0x+2l)) ))
h
follows that A, U. and B, ug do not agree on the formula & E TC which contra- dicts the assumption that A, u, and B, ug agree on all formulas in TC Therefore, Xi, (ux) = X (up).
(n)
Hence, Equation holds for all t No. and we conclude:
A, UA
B, uB =
Xk.A (uA) =
(00)
(00) =2, (ug)
10
30

---

Published as a conference paper at ICLR 2026
C.5 RELATION BETWEEN GAME, LOGIC, AND l: C-CCCL
In this section, we show the correspondence between TC k-CCWL and the topological (k+22)- pebble game. Recall that 1-CCWL refines the color of a single cell by aggregating over its boundary, coboundary, lower, and upper neighborhood, and in Lemma C.7 we show that GTC3 refines 1- CCWL. Intuitively, For the base case 1, we slightly restrict TC3 to a guarded fragment GTC3 so that counting quantifiers only range over the same neighborhoods that I-CCWL sees. In order to maintain the precise correspondence, we introduce the GTC; game, as follows:
If no pebble is currently placed on either side, Player I may choose any set PA S XA x XA of pairs A, as in the standard game.
Otherwise, suppose for example that the first pebble is placed on cell in A (i.e. u. (21)
a). Then Player must choose PA consisting only of pairs (b, c) such that one of the following holds:
bbcc
-bE and c (B
-be (a) and E NNal n6).
(The same condition holds symmetrically on PB using the current position of the corresponding pebble in B.)
Lemma C.9. Let A and B be two altributed combinatorial complexes, and let (xI,,..,, Ibk A and up : (x1.....,Tg - XB be two partial functions. If Player has a winning strategy for the O-move TCk game A and B with initial configuration (UA, uB), then A, U, and B, uB agree on all quantifier-fut formulas in TCk.
Proof of Lemma C.9 We prove this lemma by induction on the length of the quantifier-free formula A E TC20, as follows:
1. Initial step: We prove that if Player II has a winning strategy for the O-move TC2 game, then A, 4 and B, ug agree on all atomic formulas A E TCR. We analyze each possible case for the atomic formula separately:
If x=== (a; x.)) for all i,j E [k]] Since Player has a winning strategy in the 0- move game, it means that ua(x)) = (xxz) implies un(x;) = un(x,) and vice versa. Therefore, A, U and B, ug agree on the formula X.
x (x, for some r E [plo and for all i E [k]: Since Player II has a winning strategy (ug(() for all [k]. Therefore,
in the O-move game, it means
(xx)) A, u. and B, u agree on the formula X.
If À (x;) for some E [4] and for all i E [k]: Since Player II has a winning strategy in the 0-move game, it means CA (x:)) = (=.((())) for all E [4]. Therefore, A, U.A. and B, ug agree on the formula A.
If A E (x;, for some N E NN. and for all i,j E [k]: Since Player has winning strategy in the O-move game, it means that if u E NA, u (xz)), then uz (a;;) E (B, un((x)))))) (Iz)), and vice versa. Therefore, A, U. and B, uy agree on the formula A.
Therefore, we conclude that A, UY and B, ug agree on the quantifier-free free formula with len(A)= 1.
2. Inductive step: Assume that if Player has a winning strategy for the 0-move TC2 game, then A, us and B, ug agree all formulas À TC, with len(A) m. We must show that it also holds for all formulas À E TC, with len(A) (A) = m. For contradiction, assume that A, U. F but B, un K X. Each case for is analyzed separately:
If A is of the form ww:
A, uA A - A,
uu | w,
B, # o = u F w.
Thus, A, u. and B, up do not agree on w. which has len(w) < m. This contradicts the induction hypothesis. Hence, A, us and B, un agree on X.
31

---

Published as a conference paper at ICLR 2026
If is of the form w1 wy: Without loss of generality, B, v of w1. In this case, u and B, ug do not agree on w1, where len(wr) < m. This again contradicts the induction hypothesis. Hence, A, U and B, un agree on A.
assume A, u F= w1 but
Therefore, we have proved that if Player II has a winning strategy for the O-move TC₁ game, then A, ua and B, ug agree all quantifier-free formulas À TCk.
Theorem C.10. Let A 1SA,NA, IkA, CA) and B (Sn, XB, Ck be two attributed combi- natorial complexes and let uA (Ii,-.., ,T, XA and up {I1,..., .Tk] - XB be the partial functions. If Player II has a winning strategy for TC2 game with initial configuration [uA, uB), then:
A, UA = B TCk
Proof of Theorem C.10 We prove this theorem by induction on the quantifier depth of the formula À TC2. Specifically, we show that if Player II has winning strategy for the l-move TC2 game, then A, uA and B, ug agree on all formulas
TC We prove this by induction on t.
1. Initial step: We prove that if Player II has a winning strategy for the O-move TC& game, then A, U and B, ug agree on all quantifier-fre formulas À E TC2. We prove this in Lemma C.9
2. Inductive step: Assume that if Player II has winning strategy for the t-move TC2 game for all t E [n - 1/a. then A, U and B, ug agree on all formulas À E TC We must show this also holds for t n. For contradiction, assume that A, uA + À but B, uB H X. The only case to consider is when À is of the form N (Iz, Iz )w for some i E [k]. We define the following set:
PA = (ar,, BA) E x2 A.uAl + O.A, BAl F w)
By assumption:
IPAL N > (((B,)))) E X3 - + 3ol J w||
If Player selects PA. then Player II must respond with a set PB. Regardless of which set PB Player II selects, there exists at least pair of cells (0B, BB) E X3 such that
B, B,u aB Bal | w.
On the other hand, for all (aA,34) 3A) PA. it holds that
A. A, + QA, + BAl F Fw.
If Player I modifies the partial function uy = up [ - aB - 3R), then Player II can- not have winning strategy for the remainder of the game. By the induction assumption, A, U [T + a,A, xk-1 + 3A] and B, up up( + a,, Tx-1 + BB] must agree on w, where (en( < n. This contradicts the assumption that Player II has a winning strategy. Therefore, A, u and B, u agree on the formula X with len n.
Thus, if Player has a winning strategy for the TC₁ game, then A, U. and B, ub agree on all formulas X TCR-
Remark C.11. By the same approach used in the proofs of Lemma C.9 and Theorem C.10 one can show that if Player has winning strategy the GTC, game with initial configuration ( un), then we have
A, u. = B,uB GTC,
Theorem C.12. Let A = KA, and B = (SB. XB. rkg, be two attributed combi-
natorial complexes. Let us E X and up X If winning strategy for TC+42 game with initial configuration (uA, uB).
(00) (00 (ux) XR.B (un), then Player Il has
(8) Proof of Theorem C.12 We prove that for all L 2 0, X (ua) X (un). then Player II has winning strategy for the t-move TC game. We prove this by induction on f.
(t)
32

---

Published as a conference paper at ICLR 2026
1. Initial step: We prove that if (4)
Xk,A (ua) (8)
K (un). then Player II has winning strategy
for the O-move TC++2 game. Since Xk.A (uA) X (uB). it follows that atp (uA)) aLpB,A (uB). This implies the following conditions hold:
(6)
(0)
uA(a;) = u.(x)) = uB(x;) = (2;))), for all i,j E [R]] tk)(un(z,)) = rkn(un(z)), for all d E [k].
ca(ua(m)) = cz(u)(z)) for all i e [k:], and
us(a,) E A(A, (x,)) + un(ss) (((B (x(r))) for all N (N.,NN., ind E [R].
Therefore, Player II has a winning strategy for the O-move game.
2. Inductive step: Assume that if (0)
Xk.1 (ua) - X (wn), then Player II has a winning strategy We must show that this also holds for t= Note that Player I's strongest move is to modify an unmodified pair of variables. Without loss of generality, assume Player I modifies the pair (IR+2; Tx+1). The game proceeds follows:
(t)
for the t-move TC game for all 1
Player selects N pairs of cells, denoted as PA-
For each atomic type value and k-tuple of pairs of colors C, let No.C be the number of pairs (oA,BA) E PA such that
(ttpA)e((uaaAa))) (m-1) (ua: aA. "Ma (a.C)
Since Xk.1 (ua) Xk,n (un), it means that there Na.0 pairs of cells (an, (B) E X
(1)
(t)
for all atomic type a and k-tuple of pairs of colors C, such that
(UDBA4z(UBaBB0) (n-1)) k (uB; a (a)B (a,
Player II includes all these No.c pairs in PB. for all atomic types and k-tuples of pairs of
colors C.
Player modifies un un| an, 2x+1 + Bn] for some pair (an,Bn) Pn- Player Il modifies u. [xk+2 + a,1, aA, +++1 - 3A] for (a,, 3A) PA such that
(at):+2(AAQAAA)) A (m-1) (ua: (A) = (atpe+2 (ugag A
(n= (uB: (B.88))
The remaining valuations un Ma(xxt2 0A, - 3^] and un 12/2222 0B, 3g].
Player II has not lost the game. In the next move, Player I modifies valuation for pair 2y). By the induction assumption, Player II has winning strategy for the remainder of the game.
(t) Thus, we have shown that for all 2 0, X (MA) = Xk.B (uB), then Player II has a winning strategy for the t-move TC++2 game.
Remark C.13. One can use the similar approach as in the proof of Theorem C.12 and show that if (oc)
X1.A (WA) X1.B (ug), then Player II has winning strategy for GTC; game with initial configu- ration (uA, uB).
(00)
Theorem C.14. The k: b-CC procedure and TC are equivalent in expressive power for distin- guishing non-isomorphic uniform ACCs.
Proof. Let = (A,, ca) and = (SB, XB. rkg, CB) be two uniform ACCs. Recall that the k-CCWL procedure A and B is defined by: augmenting each complex with identical-vs- disjoint (a fresh O-cell connected to all O-cells via freshly colored 1 1-cells), running k-CCWL, and
then comparing the stable global signatures X and Xk,B The procedure distinguishes A and B
(oo) (xo)
iff XE.A # Xk.B
(20) (20)
33

---

Published as a conference paper at ICLR 2026
TC++2
GTC₂
Theorem C.10
Theorem C.8
Remark C.I1]
Lemma C.7
TC game
k-CCWL
GTCs game
1-CCWL
heorem C.12
Remark C.I3
Figure 4: Left: correspondence between k-CCWL, TC and the TC Right: the case k with guarded logic GTC; and the GT GTC3 game.
By Proposition 3.1 applied to uniform ACCs with the identical-vs-disjinn,, exactly one of the fol- lowing holds:
(20)
(00) or X
(00)
X
B
O X
We show that these two cases are equivalent to agreement vs. disagreement on all sentences of TC
Case 1: XK.A Xk.B* Then the multisets of stable k-CCWL colors on X and X coincide. In particular, for every color C' the number of k-tuples of color C is the same in A and B. Hence we can fix color-preservin bijection
(00) (00)
f X
(20) x with X = Xk, (00) (f(u)) for all u. E X
By Corollary 5.3
equality of stable k-CCWL colors for tuples is equivalent indistinguishabiiity in TC++2. Concretely, for every X X
Xk.A (UA) = X
X (uB)
Ve E TC
A,uA + Buu F
Applying this to each pair (UA, f(uA)) we obtain
AuA E X Vp E TC442
A,u + B,f(ua) F
Now let vp be any sentence of TC&+2 (no free variables). Since the truth of v does not depend on the chosen valuation, for any UA we have A }= vo A, us = v. and similarly for B. Taking any U E X and ug = f(uA), we get
A
A
B,un
B B
Thus A and B satisfy exactly the same TC sentences, so TC cannot distinguish them when- ever the k-CCWL procedure cannot.
(oc) Case 2: Xk.A * XR,B- By Proposition 3.1, this implics Xk.A n X = 0. i.c., no stable color
(20)
(cc)
occurs in both A and B. Hence there exists stable color C and k-tuple U. E 2 such that
X L (uA) = C and X (un) + C for all un E x
Let =TCk1a be the equivalence relation on k-tuples taken from A and B defined by
U TC UB
Vi TC A, UA } x >
B, ug ト s.
for UA E X and ug E X By Corollary 5.3 this equivalence coincides exactly with equality of stable k-CCWL colors: for all UA E 2'H up E x
(ux) = xk. (un)
(0c)
UA TTC, UB-
34

---

Published as a conference paper at ICLR 2026
Fix stable color C' that occurs in A but not in B, and choose us Consider the
2 with Xa. (un)(us) C.
[uA] = aea E X' (va) = =} u {un E X (t.) C
By assumption, tuple in B has color C, the second set empty and
[uA] = {UA E X
CJ.
By the previous paragraph, all tuples in [uA] are mutually ETC -equvvllet, and tuple in B is equivalent to them. Thus [ux] is single ETC.-a eequivalence class among the tuples of A and B.
By standard finite- siite-model-theoreee 2C442-formula with & free variables. Hence, there exists formula (C( E TC such that, for every D E (A, B) and every Xb
arguments, each +2 eeuivalence class is definable by some
D, F PC
[MA]
(v) C. (t)
In particular, there exists 4n E 2' with A, us F pc. while for all ug E 23 we have B, uB * p0 because no tuple in has color C.
Consider now the seeeenneee
3ø ... Exg po(1......
By construction,
A A 1= le ... Box (o but 1 lz ... Des ( 2x),
80 TC distinguishes A and B whenever the k-CCWL p-CCcd..rocedure does.
k-CCWL < (k- 1)-CCWL. Now, we know that k-CCWL has the same expressive power as TC and (x--))CCWL has the same expressive power as TC It also known that TC C TC therefore, k-CCWL is at least as expressive as (k- 11-CCWL. Now, in the next section, we want show that k-CCWL is strietly more expressive than (k- 1)-CCW) in terms of distinguishing non-isomorphic ACCs.
D CCWL ON GRAPHS AND ITS RELATION TO WEISFEILER-
In the following, we want to show that 2-CCWL has strictly more expressive power than 1-CCWL. In the proof of [emma D.I] instead of running 2-CCWL on the pair of ACC, we use the result from [Teoremm C.14] and its corresponding logic to make the proof simpler, which provides great example useful tool terms of distinguishing ACCs.
Lemma D.1 (1-CCWL 2-CCWL). There a pair of ACCs such that 1- 1-CCWL cannot distinguish them, but 2-CCWL can distinguish them.
Proof of Lemma D.I We use the standard example from the graph setting: the 6-cycle C. and the disjoint union of two triangles C3 C3, which 1-WL fails distinguish, e.g. Grohe 2021
We now view these graphs as 1-dimensional ACCs:
On the left, the ACC A obtained from the 6-cycle Cs. with 6 cells of rank 0 (the vertices) and cells of rank (the edges);
On the right, the ACC obtained from C3 again with cells of rank 0 and 6 cells of rank 1.
In both cases, there are no cells of rank 2 2.
Intuitively, these ACCs, 1-CCWL behaves exactly like 1-WL the underlying graphs. In both ACCs, each O-cell v. aggregates colors exactly from two O-rank cells and two 1-rank cells. Since initially all O-cells share the same color and all 1-cells share the same color, every O-cell sees the
35

---

Published as a conference paper at ICLR 2026
Figure 5: Left: the ACC associated with the 6-cycle Cg. Right: the ACC associated with the disjoint union C3 Li C3. Both have six O-cells, but only the right-hand side contains 3-cycle (triangle).
same multiset of colors. Dually, each 1-cell e has two O-rank cells in its boundary and two 1-rank cells in its lower neighborhood, all 1-cells also see the same multiset. Hence refinement step already yields a stable coloring that is identical on the two ACCs, and 1-CCWL cannot distinguish them.
As result, after one refinement step the coloring on both ACCs is already stable and identical, and 1-CCWL cannot distinguish them. Let us also note that adding the broadcast-anchor cell used in our TNN constructions does not affect this argument. If we attach the same anchor cell to A and B in the same way, then all cells in A and B gain the same additional neighbor of the same color. Hence the symmetry of the refinement process is preserved, and 1-CCWL still cannot distinguish the two ACCs.
However, consider the following formula @ E TC₁:
Φ 3'1 R1 (x1) A (x2) E (21,
24) R1 (I4) EN (I3, EN (11, A x2 za)).
Informally, this formula expresses the existence of three rank-1 cells (edges) that are pairwise ad- jacent via their lower neighborhoods, i.e., the presence of triangle. In the ACC B (two trian- gles), this property holds. In the ACC A (6-cycle), there is no triangle at all, so no such quadruple (11, 32, 2z, v4) exists and A //= 6. Moreover, we can make an adjustment to ø and create new formula o' that expresses the existence of at least two such triangles:
o' =21, (R1
A (1 A EN
3' sTa) (Ri (ma) R (x4) (Na, A E- (x), A 02 =xa))
One might worry that adding the identical-vs-dijoinn vs-disjoint cell to could create triangles. However, as discussed before, the anchor cell and all edges involving it are added with fresh color, they easily recognizable. In particular, we can use the predicate P.(.) to restrict attention to non-fresh edges and thus ignore any triangles that use the anchor. Therefore, & still separates A and B even in the presence of the identical-ve sesecall-s--ijjeen vs-disjoint cell.
Thus, A and B disagree Hence, 1-CCWL cannot distinguish them, this proves that 1-CCWL is strictly less expressive than 2-CCWL.
Sey-eentnce.
Therefore, 2-CCWL is able distinguish A and B.
36

---

Published as a conference paper at ICLR 2026
Given the above lemma, it seems that k- WL and k-CCWL have similar behavior in terms of dis- tinguishability of pairs of graphs, if we only consider nodes as O-rank cells and edges as 1-rank cells. To formalize this assumption, Let G (Va. Eg co) be vertex-colored simple graph. We associate to a 1-dimensional uniform ACC
A GC == (SA. XA tkA, CA)
as follows:
SA Vo:
Xx(0)= ((o) :
Xx(1) ((u,0) (u, E Ea).
XA == ( and rka(fv)) 0, rka((u, =
ca(lo)) = cc(o), and all 1-cells receive the same fresh color Gedge-
Theorem D.2. Let G, be vertex-colored graphs, and let A == GOC and B HCC be their
associated I-dimensional ACCs. Then, for fix k 2 1, we have
wi (0 (va) va E V = { (o (vn) un E V
(34)
if and only if
{ (Ell(Es): :A E
an e x x - (x.l((n))
(35)
Proof of Theorem D.2 We follow the following steps to prove the theorem.
Step 1: Let A (SA, NA, rka, ca) be the associated 1-dimensional ACC of the graph G. We define the incidence graph ine of as follows:
Vine == Va Ü Eg. We consider new vertex type vf for each edge e = {u, v) E Eg.
E Aine == EG {fu, e} e fu, v} Ec, E e).
Vertex colors: each v E Vg keeps its original color but is tagged as "vertex"; each e E Eg
receives fresh color tagged "edge", vertex- and edge-nodes distinguishable.
We define Bine in the same way.
Step 2: We claim that for every O, we have
{
wl (1) Ri (
VR Aim } = { w1 (icl (u) : Bine
: =f x
We prove this by induction on
1. Initial step: We prove that the theorem holds for 0. The k-WL atomic type atpe, (v) records:
the equality pattern among the v,'s,
which pairs (o,, 0y) are adjacent in ine and the initial vertex colors Caine (1)).
The k-CCWL atomic type al.ps, (ar) records:
- the equality pattern among the xz's,
the truth values Ng,Ne,,N between F,, Ky, and
the initial cell colors ca (2:4).
Moreover, we know that x; E N (Iz) if and only if foi, E Eg. Therefore, we can
define a bijective function F X U X + gine U UVk
Bine such that for all xA E X we Ue if x; {p.g) E Eg and u; p
have F( (V1,-.., where vi
37

---

Published as a conference paper at ICLR 2026
if 2, {p} E Vg. Same also holds for all aB E Xz.. Therefore, for all IA E 24 and By E X let = F(TrA) and u = F(BB), we have
(m)) (v) = w1. B. (u)
= aine. (v) = atpk, Bine (u)
= atPa,a (FAA atpx, (IBB)
= (EA) X1. (In)
Therefore, we have
{ {xbA()): E { {
(0)
(0) (k,B(() v x3} }
if and only if
{ w1 Aine (v) : E Vk Aine }
{{
w1 p (u) u E Vk }
Bine
2. Inductive step: Assume the statement holds at round t-1. We compare the refinement multisets used by k-WL and k-CCWL incidence graphs and 1-ACCs.
For k-WL, the refinement of u at round is hash of wh (v) together with the multiset
Ml0 k,Aine (w) == {l (atPp+11A (Tlu: + w)); (wi(--t) Kiu (5(m) & u)))==)) a e Vane B.
For k-CCWL on A, the refinement of round t is hash of (t-1) (x) and the multiset XR.A
a, 8, E XA B. Same as the base of induction, for all FA X and VB E X let e F(xA) and u F(BB), we have
( (a) == | (atP*+2. (xxA. ( (f(a/))) (-) (a
(t) K, (v) = (((()
Bine (u) (+A) = (t) (EB)
(EA((T)) (Z
(0)
Therefore, by the induction hypothesis, we have
(x {f (x yE x
if and only if
{ wi Amm : v E V
Aine } f- (ln a E V 7
Step 3: We now show that k- G and on Alne have the same distinguishing power. In- tuitively, Aine is obtained from G by adding a vertex per edge, connecting to its endpoint and coloring the new edge-vertices by a fresh color. Conversely, G can be recovered uniquely from giue by restricting to the "vertex-type" nodes.
Step 4: Combining Step 2 and Step 3, we obtain for all t 12 0:
(wolo(a) : vo E v& { (V uu E v/ }
Aine } { (xn) (2') e V }
( x4 { (xxl((n) en x
which is exactly the statement of Theorem D.2
'The 1 be handled similarly; therefore, we only consider k
38

---

Published as a conference paper at ICLR 2026
In the following, want generalize the result in Lemma D.I and prove Theorem D.3 (lk-1)-CCWL < k-CCWL). For any k 2 1, there is pair of ACCs such that (k 1)-CCWL cannot distinguish them, but k-CCWL can distinguish them.
Proof of Theorem D.3 We use the result that is found in Cai al. 19922
Theorem D.4 (Cai et al. (1992)). For any k 2 1, there is a pair of graphs Gk and Hş such that k-WL can distinguish them, but (k 1)-WL cannot distinguish them.
Now, as a direct result of Theorem D.4 and Theorem D.2, we can conclude that for any 2 2, there is pair of ACCs G and H such that k-CCWL can distinguish them, but (k: 1)-CCWL
cannot distinguish them.
39


Reviews:
[{"review_id": "votWNI2i6q", "reviewer": "Reviewer_wsPE", "summary": "The paper develops a rigorous theory of the logical expressiveness of topological neural networks (TNNs) operating on attributed combinatorial complexes (ACCs). It introduces:\n\n- k-CCWL: a higher-order Weisfeiler–Leman-style test for combinatorial complexes that refines colors on k-tuples via a “double shift sequence,” aligning with message passing that aggregates via pairs across upper/lower neighborhoods.\n\n- TCk: a new finite first-order logic fragment endowed with a pairwise counting quantifier designed to capture the pairwise aggregation semantics inherent to TNNs.\n\n- Topological pebble game: a game-theoretic characterization mirroring TCk, but with rules adapted to pairwise placements/relations in complexes.\n\nThe central theoretical result is the exact equivalence among these three viewpoints.\nThis yields a clean expressiveness characterization akin to the classical WL–counting logic–pebble game triad for GNNs, and explains why expressivity increases with k for higher-order TNNs. The paper also proves a “broadcast anchor” property for uniform ACCs, establishing an identical-vs-disjoint global signature phenomenon that strengthens the isomorphism testing narrative.", "questions": "1.  Why do you need the broadcast-anchor? Does the isomophism test work without it? \n\n2. Is k-CCWL guaranteed to converge? I couldn't find relevant info in the proof.\n\n1. Beyond uniform ACCs: Which parts of the equivalence hinge critically on uniformity? Can the broadcast-anchor identical-vs-disjoint result be generalized with weaker conditions (e.g., local facet constraints)? If not, can you provide counterexamples?\n\n\n2. Tightness of the k+2 overhead: The need for k+2 variables/pebbles arises from the double shift sequence. Is k+2 provably tight, or could specific subclasses of ACCs/TNNs be captured by TCk+1? A formal lower bound on variables needed would be informative.\n\n3. Complexity bounds: What are the computational costs of k-CCWL (and its stabilization) on ACCs of order ρ and size |X|? Are there known polynomial bounds in k, ρ, and |X|? Can you propose practical approximations that preserve the expressiveness class for typical TNN architectures?\n\n4. Design guidance for practitioners: Given the pairwise quantifier motivation, which concrete TNN aggregation patterns (e.g., pairwise interactions via NB/NC intersections) are minimally necessary to realize the TCk+2 power? Could you sketch an architecture template that is complete for TCk+2 under injective maps?\n\n5. Illustrative case studies: Could you add small synthetic examples where k-CCWL separates complexes that 1-WL or even k-WL on graphs cannot? For instance, hypergraph configurations or simplicial complexes where upper vs. lower adjacencies are crucial.\n\n6. Relations to sheaf/CW networks: How does k-CCWL/TCk+2 apply to CW networks (Bodnar et al., 2021) and cellular sheaf-based models? Are there natural adaptations of the atomic type to encode sheaf morphisms/twists, and would the pairwise counting extend?\n\n7. Limits and blind spots: Are there graph/topological properties you can prove are still not definable in TCk+2 for fixed k (i.e., requiring unbounded k)? A short “limitations” subsection would sharpen the theoretical picture.\n\n8. Anchors and robustness: The broadcast-anchor gadget is central. How robust is this construction to noise or attribute perturbations? If attributes are continuous and then discretized, does the identical-vs-disjoint property survive?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality: The paper introduces a novel pairwise counting quantifier and a tailored topological pebble game, both tailored to the unique mechanics of TNN message passing over combinatorial complexes. This goes beyond standard graph WL/FOC frameworks to a topological domain with upper/lower adjacency and boundary/co-boundary relations. The “double shift” construction and the logic–game–algorithm triad for TNNs are original and conceptually unifying.\n\n- Quality: The theoretical development is systematic, starting from ACCs and neighbourhood systems, building k-CCWL from atomic types and multiset refinement contexts, and then matching these to TCk+2 and the pebble game through careful equivalence arguments. The appendices provide detailed proofs, and the broadcast anchor gadget for uniform ACCs is a nice technical device that clarifies the isomorphism testing behaviour.\n\n- Clarity: The paper clearly distinguishes the four adjacency types and motivates why pairwise aggregation in TNNs necessitates pairwise counting in the logic. The stepwise definitions for atomic types, initialisation, refinement, and stabilisation are well structured, and the use of quantifier depth and alignment of refinement depth with logic/game rounds help readability.\n\n- Significance: Establishing a precise logical expressiveness theory for TNNs is timely and valuable. It puts TNNs on similar theoretical footing to GNNs and higher-order WL variants, enabling principled reasoning about what architectures can or cannot decide. The equivalence result is likely to become a reference point for future work in topological deep learning and higher-order message passing.", "weaknesses": "- Scope restriction to uniform ACCs: Several key claims and the broadcast-anchor property depend on uniform ACCs. While understandable for technical control, it would strengthen the discussion of how results extend to non-uniform complexes and the minimal conditions needed.\n\n- Complexity and practicality: The theoretical expressiveness results are strong, but practical guidance is limited. There’s little discussion of the computational complexity of k-CCWL on ACCs, its scaling with k and complex order, or efficient approximation methods. Concrete implications for designing more powerful TNN layers, such as beneficial pairwise aggregations or architectural motifs, could be elaborated. TNNs are often criticised for practicality due to complexity, so the increased complexity on higher orders may hinder the impact of the theoretical results.\n\n- Empirical or constructive exemplars: Even small, instructive examples demonstrating where k-CCWL/TCk+2 distinguish structures that standard WL/GNNs can’t, especially in real TNN use-cases (e.g., hypergraphs, simplicial complexes in molecules), would increase accessibility and impact.\n\n- Contextualisation vs. related theory: The connection to prior works on higher-order WL, counting logic, and pebble games is noted, but a more granular comparison to existing expressiveness results for cellular/cellular sheaf networks or recent “topological blind spots” analyses would better position the novelty. Making explicit how the new pairwise quantifier relates to prior graded/counting logics would help readers from finite model theory.\n\n- Notation density: Some sections (e.g., Definition and refinement contexts with `D(t)_k(x)` and the double shift sequence) are notation-heavy. Additional figures or worked examples could reduce cognitive load.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3T0hfrykK3", "reviewer": "Reviewer_qRd9", "summary": "In this paper, the authors study the so-called logical expressiveness of topological neural networks. They first define the k-combinatorial complex WL test (k-CCWL) on Page 5, via adapting the k-WL test for graphs to topological networks. Next, they show that for uniform attributed combinatorial complexes (ACCs), the output representations of two objects via an instance k-CCWL are either completely disjoint sets or completely equal sets. \nHere, 'uniformity' allows us to define some notion similar to neighborhoods in graphs, and thus one can then extend message passing to such neural networks. \n\n\nNext, they define topological counting logic TC-k, as well as topological k-pebble games, where the latter is a game defined to mimic the definition of topological logic. \n\nHere are the main results: In Theorems 4.1, they prove that if for every formula in topological logic TC-(k+2), two given ACCs are consistent, then the k-CCWL coloring of them will also be the same. Next, together in Theorem 5.1 and Theorem 5.2, they show that having a winning strategy for a particular player in (k+2)-pebble game is equivalent to the topological logic TC-(k+2) assumption, completing the equivalence of different notions of expressiveness. This is given in Corollary 5.3 and Theorem 5.4. See also Eq. 6 that summarizes the main contributions of the paper.", "questions": "I completely read the main body of this work and found that it is a great paper. It contains solid mathematical contributions characterizing the expressive power of topological neural networks via different approaches: (1) methods similar to k-WL for graphs, (2) the introduced notion of pebble games, (3) the definition of the topological logic classes of order k. This contributed to the theory side of geometry and topology in neural networks. \n\n\n\nUnfortunately, this paper, while having great contributions, has a major problem. It is less accessible to the community. As ICLR and even the geometry community within AI have different backgrounds, it is necessary to make sure that a paper with that level of great math contributions is accessible. The author should make sure that a reader, even if they barely know geometry and topology, could understand the main contribution and the message. The first few pages of the paper have to deliver the message to people who do not have much background in theory, yet they want to know what the contributions of the paper are. For instance, for a practitioner, the paper is absolutely difficult to read and follow.\n\n\nI suggest that the author extensively reconsider the first few pages of this paper and rewrite them so that it is more accessible. That way, the paper will get more audience and will have more impact, given its great contributions to the math of AI. As a result of this, for the current version of the paper, I recommend rejection. \n\n\n\n- Typo, Line 91: There is nothing called 'Theorem 3.1' in the paper, which is cited multiple times in the paper. Probably the authors meant 'Proposition 3.1.' Please make sure to correct all such typos in the paper.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- contributions to the theory of topological neural networks, which is of potential interest to this part of the community\n\n- Nice and clean theoretical results, solid paper at the intersection of math and AI", "weaknesses": "- This paper, while having great contributions, is less accessible to the community. It is hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aqwsoewGSh", "reviewer": "Reviewer_bQiY", "summary": "The paper presents new expressiveness characterisations in the realm of topological deep learning, a recent field dealing with the design of  neural network architectures for higher-order relational data. The main result is an equivalence triad which mirrors results in the expressive power of machine learning on graphs. This results connects isomorphism testing, a fragment of FOL, and pebble games.\n\nIn particular, the authors introduce a novel: (i) variant of the k-WL test adapted to combinatorial complexes (CCs); (ii) \"topological\" fragment of FOL with k-variables and counting quantifiers; (iii) \"topological pebble game\".\n\n(i) The authors introduce the k-CCWL test hierarchy to distinguish non-isomorphic combinatorial complexes. The main novelty wrt to the standard k-WL test, consists in simultaneously tracking two cell substitution per tuple position. The authors formalise this aspect trying to link it to the main feature of typical upper- and lower- neighbourhoods in topological neural networks, which introduce the feature of the boundary or co-boundary cells shared between two adjacent ones.\n\n(ii) The authors introduce a \"topological counting logic\" which resembles the one studied in graphs, but with the main difference being that counting quantifiers are pairwise. The authors show an equivalence between the k-CCWL  and this fragment with k+2 variables.\n\n(iii) The authors introduce a variant of the pebble game over combinatorial complexes, where the main difference w.r.t. the \"standard\" pebble games is that players select and mark couples of cells (instead of nodes). The authors show the equivalence between the k-variable topological counting logic and the topological k-pebble game in terms of the duplicator winning strategies.\n\nFinally the authors show the equivalence between the k-CCWL test and the (k+2)-pebble game.", "questions": "[Q1] Lines 251 -- 257: Can the authors please explain the idea of the broadcast anchor? this paragraph appears rather detached from the rest of the paper and, to the best of my knowledge, this is also something different w.r.t. the standard k-WL test.\n\n[Q2] Can the authors explain why the atps are injected in multisets in every refinement step, even in standard k-WL? This is not something standard, to the best of my knowledge (see, e.g., Eq. 4).\n\nAlso see other weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "[S1] The work is relevant and timely. It contributes a set of insights and tools which, going forward, will support better and more informed quantifications of expressive power for topological neural network architectures.\n\n[S2] The paper is presented in a precise way, the authors give sufficient background to grasp the relevance of the contribution and the existing, base results in the realm of graphs.\n\n[S3] The way the fundamental expressiveness characterisations are extended is intriguing and interesting, that is, the \"shift\" to the pairwise paradigm in counting quantifiers, pebbles, tuple variable substitutions.", "weaknesses": "[W1] The main results are relevant, but remain rather abstract.\n- [W1.1] The authors does not provide evidence of how they can, for example, help characterise the expressiveness of existing architectures. Do these tools already support some, even preliminary, architectural stratification?\n- [W1.2] Does the new counting logic allow to grasp some intuition on what kind of topological structural properties methods can or cannot capture?\n- [W1.3] Other than completing the \"triad\", what kind of interesting intuition can we draw from the newly introduced pebble game?\n\n[W2] Related to W1.1 – The paper does not connect to the learning aspect at all. Generally speaking this is not an easy endeavour, and even in the graph literature, this connection is rather unexplored. A precise characterisation is clearly out of scope, but considering the current venue scope ... _experimentally_, are expressiveness insights minimally reflected in practice, even in some synthetic benchmark?\n\n[W3] A recent paper explores expressiveness limits of topological neural networks: Eitan et al, 2025 (https://arxiv.org/pdf/2408.05486). It would be extremely interesting, other than expected, to discuss at least some links between the two works. The authors does not seem to do that.\n\n[W4] Generally speaking, the paper could appear not to be accessible to all readers, being rather theory heavy. I believe something that could significantly improve the quality of the paper is to provide more intuitions and illustrations.\n- [W4.1] This \"shift\" to the pairwise paradigm that marks a difference w.r.t. standard expressiveness characterisation is only intuitively justified in lines 63 through 67, but I believe this is one of the most important aspects behind the contribution. The authors should give it more emphasis and illustrate it better to ground the following contributions.\n- [W4.2] Lines 251 -- 257 – This paragraph is rather unclear; what is the intuition behind the broadcast anchors?\n\n[W5] Minor – some references are not up to date and still report preprints instead of publication venues.\n\nOverall, with the caveat that I have not checked the math in the proofs reported in appendix, I lean towards recommending acceptance, but addressing the above weaknesses would positively strengthen my evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xMbXzkCnIR", "reviewer": "Reviewer_6rEA", "summary": "This paper develops the first formal theory describing how expressive Topological Neural Networks (TNNs) are. It introduces the Combinatorial Complex Weisfeiler–Leman (k-CCWL) test, the Topological Counting Logic ($TC_k$) with a new pairwise counting quantifier, and a Topological Pebble Game. The main result proves that $(k-)$CCWL $\\equiv$ TC$_{k+2}$​ $\\equiv$ Topological $(k+2)$-Pebble Game, creating a unified logic–game–algorithm framework that precisely characterizes the expressive power of TNNs and shows how it extends beyond classical graph neural networks.", "questions": "1. **Why the \"+2 variables\" gap is tight:** You prove $k$-CCWL $\\equiv$ $TC_{k+2}$ $\\equiv$ topological $(k+2)$-pebble game. Please provide a separation example showing $TC_{k+1}$ ​ is insufficient - i.e., a pair of ACCs indistinguishable by $TC_{k+1}$ ​but separated by $k-CCWL/TC_{k+2}$. This would make the +2 blow-up not just sufficient but necessary (currently this is motivated by the \"double shift\" and pairwise counting intuition.)\n2. **Scope: which TNN families are covered exactly?** Equivalences are stated for \"general message-passing TNNs\" with injective aggregators and the four adjacencies $N_B ​ ,N_C ​ ,N_{\\uparrow} ​, N_{\\downarrow}$. Please clarify which concrete architectures (i.e., CWN, TopoTune variants, sheaf-style updates, etc.) are exactly simulated by $k$-CCWL, and which require extra assumptions (i.e., uniformity, binary labels, injectivity). A small coverage table would help practitioners map models to the theory.\n3. **Uniform ACC assumption in Prop./Thm. 3.1:** The \"broadcast anchor\" gadget yields the identical-vs-disjoint global signature property for uniform ACCs. Is uniformity essential? Please give a counterexample without uniformity or relax the condition (i.e., \"every non-0 cell has $\\ge$ 1 facet\") and state the minimal requirement.\n4. **Complexity and convergence of $k$-CCWL:** (1) What is the per-iteration complexity in $|X|, k$, and the maximum rank $\\rho$, given the \"double shift\" considers all $(\\alpha, \\beta) ⁣ \\in ⁣ X^2$?; (2) Do you prove a polynomial stabilization bound (as for $k$-WL on graphs) for ACCs? If so, please state it; if not, clarify whether only finite convergence is established.\n5. **Game rules vs. pairwise quantification:** In the topological pebble game, Spoiler picks sets of pairs $P \\subseteq X^2$ . Please add a short completeness sketch that shows every $TC_k$ ​formula with a pairwise quantifier translates to a finite-round Spoiler strategy with $k$ pebbles (and conversely), making the alignment fully explicit (beyond the proof sketch).\n6. **Expressiveness vs. standard $k$-WL baselines:** Since $C_{k+1} ​\\equiv $k$-WL$ on graphs, the $+2$ variable shift for ACCs is intuitive. Please add a diagram/table contrasting: $k-WL \\leftrightarrow C_{k+1}$​ (graphs) vs. $k-CCWL \\leftrightarrow TC_{k+2}$ ​(ACCs), plus a simple ACC \"witness\" where $k-CCWL$ strictly dominates $k-WL$.\n7. **Worked micro-examples:** The running example in Fig. 1 (2-CCWL on a triangle with ranks/colors) is helpful - please add 1-2 non-trivial pairs of ACCs separated by 2-CCWL but not by 1-CCWL, with the corresponding $TC_3$ ​formulas and two-pebble strategies spelled out.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The introduction of $TC_k$ ​ with a pairwise counting quantifier  $\\exists^{\\geq N}(x_i, x_j)$ tailored to the upper/lower adjacency flows in TNNs is novel and well-motivated by message passing that aggregates over intermediary face/co-face pairs. This is a clean, logic-first abstraction of a topological operation.\n2. Establishing expressiveness bounds for TNNs on combinatorial complexes is timely and important: it clarifies when and why TNNs can surpass GNNs and gives a yardstick for future TNN variants (i.e., with persistence, sheaves, or equivariance). The \"pairwise-counting view\" should inform model design and benchmarking going forward.", "weaknesses": "1. **Tightness of $TC_{k+2}$:** The $+2$ variable overhead is plausible but not yet proved tight. Add a lower-bound separation ($TC_{k+1}$ ​ vs. $TC_{k+2}$) or, minimally, a conjecture plus partial evidence (i.e., a candidate pair indistinguishable by $TC_{k+1}$).\n2. The broadcast-anchor argument and \"identical-vs-disjoint\" global signatures rely on uniform ACCs. Please either: (1) show the theorem under weaker conditions, or (2) give a counterexample and make the limitation prominent (incl. a discussion of how non-uniform ACCs appear in practice).\n3. **Algorithmic complexity \\& stabilization bounds:** Provide explicit bounds for: (1) Per-round cost of $k-CCWL$ with the double-shift ($O(|X|^{k+2}$)?); (2) Number of rounds to stabilization in terms of $|X|, \\rho, k$.\n4. Can you please provide 1 or 2 toy ACC pairs and explicit $TC_{k+2}$ ​ formulas that $k$-CCWL detects but $k$-WL on graphs cannot. This would concretely demonstrate the step from vertex-adjacency to topological relations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)