Conceptio › Archive › arXiv CS

arXiv CSopen access

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Jiawen Chen 1 Qi Shao 1 Duxin Chen 1 Wenwu Yu 1

arXiv:2605.00725v1 [cs.LG] 1 May 2026

Abstract

2025), and cell complexes (Bodnar et al., 2021a; Eitan et al., 2025) have been widely adopted as expressive representations of multi-way, hierarchical, and geometric structures arising in physical simulations, biological networks, and geometric modeling (Papamarkou et al., 2024b; Millán et al., 2025). CCs have become the unified higher-order topological frameworks in topological deep learning.

Combinatorial complexes have unified set-based (e.g., graphs, hypergraphs) and part-whole (e.g., simplicial, cellular complexes) structures into a common topological framework. Existing topological neural networks and Weisfeiler-Lehman variants remain fragmented, lacking a unified theoretical foundation for topological deep learning. In this work, we introduce the Combinatorial Complex Weisfeiler-Lehman (CCWL) test, an axiomatic-style extension of the WL test to combinatorial complexes. CCWL formalizes topological message passing through four types of neighborhood relation and provides a unified perspective on the expressive power of higher-order variants. We further prove that upper and lower neighborhoods are sufficient among the four adjacent WL tests to reach the expressivity of the full CCWL framework across topological structures of combinatorial complexes. Building on this framework, we also propose the Combinatorial Complex Isomorphism Network (CCIN) and evaluate it on synthetic and real-world benchmarks. Experimental results indicate CCIN outperforms baseline methods and offers a generalized expressive framework for topological deep learning.

Prior neural architectures for combinatorial complexes have demonstrated the potential of learning over rich higher-order topological structures. Existing higher-order neural networks are typically designed for specific structures, including hypergraph neural networks (Huang & Yang, 2021), simplicial neural networks, and cell complex networks (Taha et al., 2025; Huang et al., 2024; Battiloro et al., 2024). These models rely on incompatible neighborhood definitions and message-passing mechanisms, reflecting different ways of generalizing graphs through set-based expansions or hierarchical refinements (Millán et al., 2025). To address this, TopoTune (Papillon et al., 2025) studies combinatorial complex neural networks, but simplifies as three neighborhood types and disrupts the higher-order information propagation. However, these models fail to faithfully preserve the topological neighborhood of combinatorial complexes and limits the expressive ability (Hajij et al., 2023; Papillon et al., 2023; Besta et al., 2025). This highlights the need for a principled and expressive framework that preserves the higher-order neighborhoods and topological message passing inherent to combinatorial complexes.

1. Introduction

Weisfeiler-Lehman (WL) has established theoretical foundation for characterizing the expressive power of graph neural networks (GNNs) (Weisfeiler & Leman, 1968). For graphs, the 1-WL test characterizes the expressiveness of messagepassing GNNs (Maron et al., 2018; Xu et al., 2018; Feng et al., 2022; Puny et al., 2023). In parallel, recent works explore substructure-aware GNNs (Zhang et al., 2024a; 2023b; Thiede et al., 2021; Zhang et al., 2023a; 2024b; Bevilacqua et al., 2022; Bouritsas et al., 2022), studying expressive subgraphs and paths from a structural and permutation perspective. When extending beyond graphs to higher-order topological structures, including Hypergraph WL for hypergraphs that focus on node-hyperedges (Zhang et al., 2025b; Feng et al., 2024), MPSN employs on bound-

Combinatorial complexes (CCs) have recently emerged as a unifying topological formalism that simultaneously encodes set-type relations, such as those in graphs and hypergraphs, and part-whole hierarchical relations, as found in simplicial and cellular complexes (Hajij et al., 2022; 2023). Many scientific and relational datasets naturally exhibit interactions that go beyond pairwise graphs. To capture such higherorder dependencies, hypergraphs (Feng et al., 2024), simplicial complexes (Gurugubelli & Chepuri, 2023; Taha et al., *

Equal contribution 1 School of Mathematics, Southeast University, Nanjing, Jiangsu, China. Correspondence to: Wenwu Yu <[email protected]>, Duxin Chen <[email protected]>.

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

• (Theoretical) We formally define the CCWL refinement and prove that the upper and lower adjacency refinements are sufficient for the full CCWL (Theorem 4.8). We extend CCWL results on four structures, analyzing the upper bound (Lemma 4.9) and generalized variants (Theorem 4.11) for higher-order domains.

ary and coboundary of simplicial complexes (Bodnar et al., 2021b), and Cellular WL operates on different dimensional cell of cellular complexes (Bodnar et al., 2021a). However, existing WL variants are designed for domain-specific and mutually incomparable. There remains the absence of a common theoretical foundation (Papp & Wattenhofer, 2022; Papamarkou et al., 2024a), which limits the understanding of expressive power on combinatorial complexes.

• (Empirical) We evaluate CCWL on both synthetic and real-world datasets spanning graphs, hypergraphs, and higher-order topological structures. CCWL consistently achieves superior performance on graph and complex-level classification tasks, demonstrating its practical advantages and strong generalization across heterogeneous topological structures.

Combinatorial complexes naturally admit multiple types of neighborhood relations, including upper and lower adjacencies as well as boundary and co-boundary relations (Hajij et al., 2022; Eitan et al., 2025), which together provide a complete description of higher-order interactions. However, all four relations are incorporated into message passing often results in redundant and repetitive information propagation. To reduce this redundancy, existing higher-order neural architectures typically restrict message passing to a subset of neighborhood relations. For instance, simplicial networks such as MPSN focus on boundary and co-boundary interactions (Bodnar et al., 2021a; Eijkelboom et al., 2023; Wu et al., 2023), while cellular networks propagate information along incident and adjacent cell relations (Morris et al., 2023). Similarly, hypergraph WL tests and neural models rely on node-hyperedge relations (Zhang et al., 2025b; Feng et al., 2024), but it ignores the interactions between hyperedges. However, such simplifications inevitably overlook certain higher-order dependencies (Taha et al., 2025; Chen et al., 2026). More broadly, the absence of a WeisfeilerLehman refinement defined on combinatorial complexes prevents a unified theoretical framework across higher-order topological domains. A critical challenge is to demonstrate the minimal neighborhood function refinement rule that preserves the upper bound of expressive power.

2. Related Works Topological Neural Networks for Higher-order Graph. Motivated by the limitations of pairwise graphs, a wide range of higher-order neural networks has been developed to model topological relational structures (Pham et al., 2025; Verma et al., 2024; Chen et al., 2021) in Topological Deep Learning (TDL). Hypergraph neural networks extend GNNs via node-hyperedge incidence relations (Feng et al., 2019; Huang & Yang, 2021; Xie et al., 2025). Simplicial and cellular neural networks exploit boundary, co-boundary, and adjacency operators to propagate information across cells of different dimensions (Ebli et al., 2020; Bodnar et al., 2021a; Eijkelboom et al., 2023; Wu et al., 2023; Liu et al., 2024; Hajij et al., 2020). More recent works incorporate equivalence or attention mechanisms to enhance geometric modeling capacity (Battiloro et al., 2025; Ballester et al., 2024). While these architectures successfully capture structure-specific higherorder interactions, their message-passing mechanisms are limited by being tied to a fixed subset of neighborhood relations (Taha et al., 2025; Eitan et al., 2025). In practice, our formulation is characterized through a novel model like combinatorial complex to simplify the rich neighborhood structure of higher-order domains.

The benefits of combinatorial complexes generalize set-type and part-whole topological structures. A generalization of Weisfeiler-Lehman to combinatorial complexes fills the gap the unified framework of topological message passing and expressive power on combinatorial complexes. The conceptual framework and theoretical results developed in this paper directly address the open problems and challenges (e.g., research directions 7 and 9) highlighted in the position literature (Papamarkou et al., 2024a;b), including topological message passing generalization, and the expressivity power proofs of topological invariance in TDL models.

Expressive Power of Topological Deep Learning. Weisfeiler-Lehman framework provides a principled foundation for the expressive power of topological deep learning. Recent methods have been proposed on low-order structures. On graphs, the 1-WL test captures the discriminative power of message-passing GNNs, while higher-order variants such as k-WL, sparse WL, and loopy WL offer increased expressivity at the cost of higher computational complexity (Weisfeiler & Leman, 1968; Maron et al., 2018; Xu et al., 2018; Morris et al., 2020b; Paolino et al., 2024; Papp & Wattenhofer, 2022; Zhang et al., 2025a). Beyond graphs, a growing body of work studies expressivity through substructureaware or equivariant extensions, including subgraph-WL architectures (Zhang et al., 2024a; 2023b; Thiede et al.,

Contributions: Our main contributions are summarized as:

• (Axiomatic): We introduce an unified framework of Combinatorial Complex Weisfeiler-Lehman test (CCWL) and their message passing through the four neighbor function refinement. CCWL enables the principled modeling of graph, hypergraph, simplicial complex, and cellular complex structures. 2

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

2021; Zhang et al., 2023a; 2024b; Bevilacqua et al., 2022; Bouritsas et al., 2022). Several WL extensions have also been proposed for higher-order domains. Hypergraph WL tests refine node and hyperedge representations through bipartite incidence relations (Zhang et al., 2025b; Feng et al., 2024). For simplicial complexes, message-passing simplicial networks induce a WL-type refinement via boundary and co-boundary operators (Bodnar et al., 2021b; Eitan et al., 2025). Similarly, cellular WL defines refinement rules over cells of different dimensions (Bodnar et al., 2021a; Chen et al., 2022; Truong & Chin, 2024; Papillon et al., 2025). However, these WL variants are domain-specific with different neighborhood systems and refinement rules. Their expressive powers are not directly comparable to characterize expressivity across higher-order topological domains (Papamarkou et al., 2024a). Our work operates on combinatorial complexes and preserves the inherent neighbors function to unify message passage on higher-order graph structures.

Table 1. Overview of expressive power methods and their corresponding structure domains. Supports (✓) or does not support (✗). Model GIN (Xu et al., 2018) rMPNN (Paolino et al., 2024) HomoGNN (Zhang et al., 2024a) KGWL (Zhang et al., 2025b) ED-HNN (Wang et al., 2023a) IMPSN (Eijkelboom et al., 2023) RePHINE (Immonen et al., 2023) EMPSN (Eijkelboom et al., 2023) MPSN (Bodnar et al., 2021b) CWN (Bodnar et al., 2021a) TopNets (Verma et al., 2024) ETNNs (Battiloro et al., 2025) SMCN (Eitan et al., 2025) CCIN (ours)

Graph

Hypergraph

Simplex

Cellular

✓ ✓ ✓ ✓ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓

✗ ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✗ ✗ ✗ ✗ ✗ ✓

✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✓ ✓ ✓

✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✓ ✗ ✗ ✓

cells), CC (1) contains the nodes and edges (0- and 1-cells), CC (2) contains the full 2-skeleton including nodes, edges, and faces(2-cells). The combinatorial structure of CC can be compactly described by an incidence relation called the boundary relation, denoted σ ≺ τ , indicating that cell σ lies on the boundary of a higher-dimensional cell τ . The reflexive and transitive closure of this relation induces a partial order over the set of cells as σ ⪯ σ, and if σ ≺ τ and τ ≺ ρ, then σ ≺ ρ. such as the boundary relation σ ≺ τ , iff σ ≺ τ and there is no cell δ such that σ ≺ δ ≺ τ .

Combinatorial Complexes Studies. Combinatorial complexes emerge to model the general topological relations (Hajij et al., 2022; 2023). Several frameworks leverage CCs to design flexible neural networks, including TopoTune (Papillon et al., 2025), SMCN (Eitan et al., 2025), topological neural networks (Battiloro et al., 2025), CCMamba (Chen et al., 2026) and modular toolkits for learning on generalized topological domains (Telyatnikov et al., 2024; Hajij et al., 2024; Anonymous, 2026). Table 1 shows previous studies mainly focus on specific high-order modeling, and still lack a unified model for the four structures. Our research is dedicated to establishing the framework of expressive power from WL test on combinatorial complexes.

Now we introduce the four neighborhood incidence relation. Definition 3.2 (Cell Adjacencies). For cell complex CC and a cell σ ∈ P (S), we define four type adjacencies as 1. Boundary adjacent B(σ) = {τ |τ ≺ σ}. 2. Co-boundary adjacent C(σ) = {τ |σ ≺ τ }. 3. Lower adjacent N↓ (σ) = {τ |∃δ,s.t. δ ≺ σ and δ ≺ τ }.

3. Preliminaries

4. Upper adjacent N↑ (σ) = {τ |∃δ,s.t. σ ≺ δ and τ ≺ δ}.

Combinatorial complexes is a frontier generalization structure that combines features of cellular complexes and hypergraphs. Here, cellular complexes are a generalization of simple complexes (regular faces, tetrahedrons), and hypergraphs generalize graphs whose element hyperedges can connect any set of pairwise or several nodes.

Importantly, the message passing mechanism usually considers multi-hop neighborhood relationships in CC. A cell span multiple ranks and propagate from 0-cell to 2-cell, e.g., messages pass from node to face. In this work, we assume that all incidences of cell elements are rank-adjacent, and the complex contains no free faces.

We define combinatorial complexes as follows. Definition 3.1 (Combinatorial Complex). A combinatorial complex (CC) is a triple (S, C, rk) consisting of a set S, a subset C of P (S), and a function rk : C → Z≥0 such that for all v ∈ S, {v} ∈ C and rk({v}) = 0. The function rk is order-preserving, if σ, τ ∈ C satisfy σ ⊆ τ , then rk(σ) ≤ rk(τ ). If rank of a cell σ ∈ C is k, then we denote it as a k−cell. The dimension of CC is defined as the maximal rank among its cell: dim(CC) := max rk(σ).

Based on the neighborhood function, we introduce the Weisfeiler-Lehman test on combinatorial complex CC in Figure 1. The coloring function c at the t-th iteration is c(t) : C → N, where the color values represent the labels of topological structure. The multisets {{·}} generalizes the sets that allow multiple instances of each element.

This definition is useful for referring to specific structural levels of the complex. i.e., CC (0) contains only the nodes (0-

Definition 4.1. Let c be a coloring of the cells in a complex X with cσ denoting the color assigned to cell σ ∈ PX . Define B(σ, τ ) := B(σ)∩B(τ ) and C(σ, τ ) := C(σ)∩C(τ ).

4. Combinatorial Complex Weisfeiler Lehman

σ∈CC

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

�1

�12 �13

:node

�2

�23

�3

:edge

�24

�4

�34

�� : �2 , �1 , �3 , �4 , �12 , �23 , �24

�� : �12 , �1 , �2 , �13 , �24 , �34 , �1

�� : �13 , �1 , �3 , �12 , �23 , �34 , �1

�� : �24 , �2 , �4 , �12 , �23 , �34 , �2

�� : �4 , �2 , �3 , �24 , �34

�� : �34 , �3 , �4 , �13 , �23 , �24 , �2

�� : �23 , �2 , �3 , �12 , �13 , �24 , �34 , �1 , �2 �� : �1 , �12 , �13 , �23 , �2

�� : �2 , �23 , �24 , �34 , �1

�12

�1

�23

�1

�13

:face

�� : �1 , �2 , �3 , �12 , �13

�� : �3 , �1 , �2 , �4 , �13 , �23 , �34

�1

Colour Initialization Combinatorial Complex �2

�12 �1

�13

(a) Multisets Update Rules of CCWL Test

�3 �2

�23

�3

�24

�2

Upper and Lower Adjacency Cell Aggregation

�4

�34

�1 , �4 :

�2 , �3 :

, ,

�12 , �13 , �24 , �34 : �23 :

�1 , �2 :

, , ,

, ,

, , ,

Update Cell Representation �

�

� � �

, , ,

, ,

, , ,

(b) First iteration of Combinatorial Complex Weisfeiler–Lehman Test �24 �2

�34

�4

�1 , �4 :

�2 , �3 :

, ,

�12 , �13 , �24 , �34 : �23 :

�1 , �2 :

, ,

, , ,

, , , ,

, , ,

�

� � �

, , ,

, ,

, , ,

stabled ,

Figure 1. Illustration of Combinatorial Complex Weisfeiler-Lehman Test . CCWL test conducts a combinatorial complex, which consists of four nodes v1 , v2 , v3 , v4 , five edges e12 , e13 , e23 , e24 , e34 and two faces f123 = {e12 , e13 , e23 }, f234 = {e23 , e24 , e34 }. At the (0) (0) (0) initialization, 0-cells (nodes) c0 = {•}, 1-cells (edges) c1 = {•}, 2-cells (faces) c2 = {•}. CCWL test stables at iteration t = 2.

We define the following multisets of colors for cell σ: 1. The boundary colors: cB (σ) = {{cτ |τ ∈ B(σ)}}.

combinatorial complex in Figure 1(a), and Figure 1(b)(c) show that the CCWL test stops and reaches a stable state c(1) = c(2) after two iterations. Two combinatorial complexes are considered non-isomorphic if their relabeled colors are different. Otherwise, the test is inconclusive. Then we define the combinatorial complex isomorphism as

2. The co-boundary colors: cC (σ) = {{cτ |τ ∈ C(σ)}}. 3. The lower adjacent colors: cN↓ (σ) = {{(cτ , cδ )|τ ∈ N↓ (σ) and δ ∈ B(σ, τ )}}.

Definition 4.3 (Combinatorial Complex Isomorphism). Given two combinatorial complexes CC 1 = (S1 , C1 , rk1 ) and CC 2 = (S2 , C2 , rk2 ), the object is to demonstrate the isomorphism as CC 1 ∼ = CC 2 if there exists a bijective function A : CC 1 → CC 2 . The mapping A holds that

4. The upper adjacent colors: cN↑ (σ) = {{(cτ , cδ )|τ ∈ N↑ (σ) and δ ∈ C(σ, τ )}}. Building on the four neighborhood coloring multisets, we define the update rule for cell σ ∈ CC as c(t+1) (σ) = (t) (t) (t) (t) HASH(c(t) (σ), cB (σ), cC (σ), cN↓ (σ), cN↑ (σ)), where HASH is an injective multiset hashing function. The details of coloring process can be found in Appendix A.

(ci , cj ) ∈ CC 1 ⇒ (A(ci ), A(cj )) ∈ CC 2 .

(1)

However, unlike the isomorphism function in the graph structure, the labeling information process between nodes and the relabeling process of different rank structures (e.g., nodes, edges and faces) in the combinatorial complex make the injective transfer have information redundancy. Beyond individual cell comparisons, we can also relate colorings at different levels. We formalize the refinement relationships between colorings can propagate across complexes.

To distinguish non-isomorphic combinatorial complexes, we generalize the WL test on the combinatorial complexes, and introduce the iterative color refinement algorithm CCWL. Definition 4.2 (CCWL Test). Let CC 1 = (S1 , C1 , rk1 ) and CC 2 = (S2 , C2 , rk2 ) be two CC, and a coloring function c on cells. Given initial features {hσ | σ ∈ C1 ∪ C2 } and neighborhood orders k ⊆ Z+ (default: k = {1}), the CCWL iteration proceeds as follows:

Lemma 4.4. Let CC 1 and CC 2 be two combinatorial complexes. If CC 1 ∼ = CC 2 , then for all iterations t ≥ 0, the following (t) equality of multisets holds c (σ) : σ ∈ CC 1 = c(t) (τ ) : τ ∈ CC 2 .

1. All the cell of the same rank σ ∈ CC 1 , τ ∈ CC 2 are initialized with the same color, defined as c(0) (σ), c(0) (τ ) .

Lemma 4.5. Let CC 1 , CC 2 be any regular CC with A ⊆ PCC 1 , B ⊆ PCC 2 . Consider two combinatorial colorings CC 2 1 c, d such that c ⊑ d. If {{dCC σ |σ ∈ A}} ̸= {{dτ |τ ∈ CC 1 CC 2 B}}, then {{cσ |σ ∈ A}} ̸= {{cτ |τ ∈ B}}.

2. Given the color c(t) of cell at iteration t, we update the color of next iteration as c(t+1) by injective mapping the multisets of colors belonging to the adjacent cells of σ by HASH function: c(t+1) = (t) (t) (t) (t) HASH(c(t) , cB , cC , cN↓ , cN↑ ),

Remark. Two coloring functions c and d satisfying the relation c ⊑ d indicate that the coloring function d has a stronger ability to distinguish non-isomorphic structures compared to the coloring function c.

3. It stops when a stable coloring is reached. For example, we provide the rules for the WL test on the 4

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Theorem 4.11. Let G, H, S, C be a graph, hypergraph, simplicial complex and cellular complex, respectively. There exists a mapping from each of these structures into a combinatorial complex CC, the CCWL test can simulate the 1-WL, hypergraph WL, simplicial-WL and cellular-WL tests.

This Lemma further yields a corollary, showing that differences in the coloring function emerge at a refined level. Corollary 4.6. Consider two colorings functions c, d such that c ⊑ d. For all combinatorial complexes CC 1 , CC 2 , if dCC 1 ̸= dCC 2 , then cCC 1 ̸= cCC 2 .

We discussed some non-isomorphic structural pairs as counterexamples that cannot be distinguished by these WL tests, but can be distinguished by the CCWL test in Appendix B.2.

Recent works have proved the upper bound of the expressive power of GNNs (Xu et al., 2018), and hypergraph isomorphism computation on HGNNs (Feng et al., 2024). Similarly, the expressive power of part-whole relations neural networks are also explored (Bodnar et al., 2021a;b). We observe that the two-stage operations on hypergraph (Zhang (t) (t−1) (t−1) et al., 2025b) as ce = HASH(ce , {{cu ,u ∈ (t) (t−1) (t−1) Nv (e)}}), cv =HASH(cv , {{cu , u ∈ Ne (v)}}) are structurally equivalent to upper adjacent colors. Moreover, (t) (t) the WL on cellular update follows HASH(c(t) , cB , cN↑ ). However, in hypergraphs, the use of boundary proximity information during downpropagation does not take into account lower adjacency. The WL test can be generalized to combinatorial complexes with four adjacencies. In practice, we observe that upper adjacent colorings subsume boundary colorings, i.e., cB ⊑ cN↑ , and downward adjacent colorings subsume co-boundary colorings, i.e., cC ⊑ cN↓ . Based on Corollary 4.6, we further derive the neighborhood refinements for the topological message update process.

5. Combinatorial Complex Neural Networks We begin with the message passing of Combinatorial Complex Neural Networks (CCNN) (Hajij et al., 2022). Suppose CC be a combinatorial complex, NC be a collection of four neighborhood functions. The l-th layer of CCNN updates l the embedding hlσ ∈ RF of cell σ can be written as ! O hl+1 = ϕ hlσ , AGG MN (σ) (hlσ , hlτ ) , (2) σ N ∈NC

N where h0σ := hσ are the initial features, is an intraneighborhood aggregator, AGG represents the aggregation function, M(·) denotes as messing information of different neighborhood, and the update function ϕ are learnable functions. To clarify the higher-order message passing on a CC, we introduce the message passing operations of a combinatorial complex with four adjacent types from Definition 3.2. For a cell σ ∈ C, we define four message passing rules as

Lemma 4.7. CCWL with HASH(ctσ , ctB (σ), ctN↓ (σ), ctN↑ (σ)) is as powerful as CCWL with the generalized update rule HASH(ctσ , ctB (σ), ctC (σ), ctN↓ (σ), ctN↑ (σ)) . (t)

(t)

τ ∈N (σ)

t t mt+1 , B (σ) = AGG MB hσ , hτ τ ∈B(σ) t t mt+1 , C (σ) = AGG MC hσ , hτ τ ∈C(σ) (t+1) (t) (t) mN↓ (σ) = AGG MN↓ (h(t) σ , hτ , hδ ) ,

(t)

Theorem 4.8. CCWL with HASH(cσ , cN↓ (σ), cN↑ (σ)) is as powerful as CCWL with the generalized update rule (t) (t) (t) (t) HASH c(t) (σ), cB (σ), cC (σ), cN↓ (σ), cN↑ (σ) .

(3)

τ ∈N↓ ,δ∈B(σ,τ )

Building on this, we can derive this lemma as

(t+1) mN↑ (σ) =

Lemma 4.9. CCWL is at least as powerful as 1-WL in distinguishing of non-isomorphic combinatorial complexes.

AGG

τ ∈N↑ ,δ∈C(σ,τ )

(t) (t) MN↑ (h(t) σ , h τ , hδ ) .

Within the Theorem 4.8, we have proved that CCWL without boundary and co-boundary has the same expressive power in distinguishing non-isomorphic combinatorial complexes as CCWL with the complete set of adjacencies. Therefore, the cells in combinatorial complex neural networks receive two types of messages, then update operation takes into account these two types of incoming messages and updates the features of the cells: (t+1) (t+1) h(t+1) = Update h(t) (4) σ σ , mN↓ (σ), mN↑ (σ) .

The details of the proof are in Appendix B.1. We establish the CCWL test generalizes and strengthens existing WL variants on graphs, simplicial complexes, and cellular complexes through lifting into the combinatorial complex. Definition 4.10 (Combinatorial Lifting Map). A combinatorial lifting map is a function f : G → CC be mapping a graph to a regular combinatorial complex such that G1 ∼ = G2 ⇐⇒ f (G1 ) ∼ = f (G2 ). Example (Clique Complex Lifting to CC): Let f (G) be the clique-based combinatorial complex, where each node in G maps to a 0-cell, each edge maps to a 1-cell, each (k + 1)-clique maps to a k-dimensional cell with rank k. The incidence structure is preserved in the complexes, the CCW L(f (G)) ≻ W L(G) in expressive power, i.e. it can distinguish regular graphs with different triangle counts.

To obtain a global embedding from a d-dimension combinatorial complex CC of a CCNN with L layers, the readout function takes as input the sets of features corresponding to all dimensions of the combinatorial complex (L) hCC = READOUT({{h(L) σ }}dim=0 , . . . , {{hσ }}dim=d ), (5)

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

As before, CCWL has developed the sufficient conditions for the powerful CCNN over multi-rank structures. we further propose the Combinatorial Complex Isomorphism Network (CCIN), which leverages summation-based aggregation and rank-adaptive update functions to achieve high expressiveness on topological neural networks. Similar to the Equation 2, the CCIN layer can be defined as X X (l) (l) h(l+1) =ϕ(l) (1 + ϵ(l) )h(l) ψN (h(l) σ σ + σ , hτ ) , N ∈NC τ ∈N (σ)

and 3-WL baseline models on SR families (in Appendix Table D.7, a larger k value achieves better performance). CCIN effectively distinguishes regular graphs, confirming its expressive power on the higher-order structures. 3-WL

10 0

Failure Rate (log scale)

where READOUT can be a permutation invariant function, such as sum, mean, or max pooling function, resulting in the process differentiable computational operations.

CCIN

10 -2 10 -4 10 -6 10 -8 0 6

sr2

(6) (l) where ϵ is a learnable parameter, and ψN (·, ·) represents a learning function for neighborhood massage. Here these function can also employ summation, max and mean aggregation function. Following the Theorem.4.11, we conclude that combinatorial complexes neural networks (t) (t) (t) Update(hσ , hN↓ (σ), hN↑ (σ)) exhibit the CCWL test’s ability to distinguish non-isomorphic combinatorial complexes through sufficient number of layers and injectivity of local aggregation functions.

MPSN

GIN

sr1

sr2

4 sr2

7 sr3

sr3

4 22

sr4

Figure 2. Failure rate on SR families(ring num k = 4).

6.2. Real-World Datasets TUDataset. We also evaluate CCIN with recent baselines on several real-world datasets from the TUDataset(Morris et al., 2020a) consists of bioinformatics and social networks, where graphs are lifted into cell complexes to model higherorder interactions. MUTAG (Kazius et al., 2005), PTC, PROTEINS(Borgwardt et al., 2005; Dobson & Doig, 2003) consist of graphs where nodes represent atoms and edges are chemical bonds. NCI1 and NCI109 (Wale et al., 2008) contain the chemical compounds screened for activity against various cancer cell lines. IMDB-B, IMDB-M, REDDITB and REDDIT-M (Yanardag & Vishwanathan, 2015; Hu et al., 2020) are preprocessed movie collaboration and Reddit networks, where graphs represent interactions between actors or users, and the tasks involve graph classification. The details of datasets can be found in Appendix D.1.

Lemma 5.1. CCIN is as powerful as CCWL when we employ an injective neighborhood aggregators and a sufficient number of MLP layers. The details and proofs are in Appendix C.1.

6. Experimental Analysis we validate the theoretical and empirical properties of our proposed message passing scheme in synthetic and realworld graph classification tasks. The lack of combinatorial complex benchmarks has been recognized as a challenge in TDL (Papamarkou et al., 2024a;b). To address this, we employ the lifting methods (Telyatnikov et al., 2024; Bodnar et al., 2021a) to infer the higher-order structure by applying cyclic lifting on real-world graph benchmarks in these graph data, which evaluates the ability of CCIN and other benchmark methods to capture topological properties. We provide additional information about experiments in Appendix D.

Table 2 reports the graph classification performance of CCIN on the TUDataset benchmark dataset, where CCIN achieved excellent results over baseline methods. Compared to traditional message-passing graph neural networks, CCIN demonstrates a clear advantage on most datasets. On MUTAG and IMDB-B, CCIN achieves improvements of 7.82% and 4.09% respectively compared to GIN, and 8.90% gains (83.2 vs. 76.4) compared to the GraphSNN model on NCI1, and 2.69% benefits (76.1 vs. 74.1) compared to PROTEINs. These results indicate that GNNs, which rely on node-level message passing, have limitations in modeling high-order structures. Furthermore, compared to higher-order topological neural networks, CCIN also demonstrates competitive or even superior performance. Compared to CWN, CCIN achieves a 7.11% improvement on MUTAG (96.4 vs. 90.0) and a 6.53% improvement on IMDB-B (78.3 vs. 73.5). Compared to TopNets and TopoTune topological methods, CCIN maintains the notable improvement on the MUTAG and IMDB datasets. These results indicate CCIN achieves

6.1. Synthetic Datasets Strongly Regular Graphs. To study the expressivity of CCIN, we employ strongly regular graphs within the same family as indistinguishable non-isomorphic graphs. For the strongly regular graph families, since any two graphs within the same family cannot be distinguished by the 3-WL test (Bouritsas et al., 2022). We build an untrained model with a complex size of k = 4 for each graph. Figure 2 shows the percentage of failure rates. The failure rates indicate that CCIN achieves the superior performance over GIN, MSPN 6

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks Table 2. Graph classification accuracy (Mean±Std) of our CCIN and the baselines on the datasets from TUDataset collection. Best performance is highlighted in bold. N/A means not available. MUTAG

PTC

PROTEINS

NCI1

NCI109

IMDB-B

IMDB-M

RWK (Gärtner et al., 2003) GK(k = 3) (Shervashidze et al., 2009) WL kernel (Shervashidze et al., 2011)

79.2±2.1 81.4±1.9 90.4±5.7

55.8±0.6 55.4±0.4 59.9±4.3

59.6±0.3 71.4±1.5 75.0±3.1

N/A 62.5±0.3 86.0±1.8

N/A 64.9±1.0 73.8±3.9

N/A 50.9±3.8 N/A

N/A N/A N/A

DGCNN (Zhang et al., 2018a), IGN (Cai & Wang, 2022) GIN (Xu et al., 2018) PPGNs (Maron et al., 2018) Natural GN (de Haan et al., 2020) GSN (Bouritsas et al., 2022) MSPN (Bodnar et al., 2021b) GTR (Huang et al., 2023b) CWN (Bodnar et al., 2021a) GraphSNN (Wijesinghe & Wang, 2022) RePHINE (Immonen et al., 2023) WLHN (Nikolentzos et al., 2023) G3N (Wang et al., 2023b) HTML (Li et al., 2024) PathNN (Michel et al., 2023) TopNets (Verma et al., 2024) TopoTune (Papillon et al., 2025) KGWL (Zhang et al., 2025b) CCIN

85.8±1.8 83.9±13.0 89.4±5.6 90.6±8.7 89.4±1.6 92.2±7.5 88.3±10.7 86.6±1.4 90.0±7.4 87.3±3.1 87.4±6.3 86.3±7.4 89.9±8.0 88.9±1.8 90.2±4.7 92.7±1.9 86.4±6.5 82.5±5.7 96.4±2.1

58.6±2.5 58.5±6.9 64.6±7.0 66.2±6.6 66.8±1.7 67.2±7.2 62.6±9.3 65.2±4.6 62.1±9.3 61.6±2.8 64.9±3.7 65.1±2.4 60.0±4.8 66.9±4.2 65.8±2.7 65.7±3.6 67.2±4.8 66.2±3.5 67.6±10.1

75.5±0.9 76.6±5.5 76.2±2.8 77.2±4.7 71.7±1.0 75.6±5.0 62.6±9.3 75.3±0.8 73.4±4.4 74.1±3.2 72.3±1.9 75.9±1.9 75.9±2.8 74.9±0.3 75.2±3.9 73.8±1.5 72.5±3.1 72.8±2.6 76.1±2.5

74.4±0.5 74.3±2.7 82.7±1.7 83.2±1.1 82.4±1.3 83.0±2.0 80.4±1.2 N/A 84.7±1.7 76.4±1.7 80.9±1.9 79.2±2.1 78.6±1.9 78.7±0.7 77.5±1.6 79.1±1.2 77.6±1.1 74.9±3.5 83.2±1.6

N/A 72.8±1.5 N/A 80.2±1.4 N/A N/A 79.1±1.6 N/A 80.3±1.9 N/A 79.2±1.7 N/A 79.2±1.3 78.8±0.6 78.1±2.1 78.4±0.7 77.2±0.2 78.5±1.4 81.1±2.0

70.0±0.9 72.0±5.5 75.1±5.1 73.0±5.8 74.8±2.0 73.36 73.7±4.0 73.1±0.8 73.5±4.5 74.8±3.5 69.4±3.8 73.4±3.7 71.0±2.2 71.7±0.4 72.6±3.3 73.1±1.8 76.3±2.7 74.4±1.9 78.3±4.5

47.8±0.9 48.7±3.4 52.0±2.8 50.5±3.6 51.3±1.5 51.5 52.1±3.9 79.4±0.3 51.0±3.1 N/A N/A 49.7±3.6 45.2±2.8 N/A 50.8±4.5 N/A N/A 51.6±3.1 54.7±3.1

competitive and unifies higher-order graph message passing architectures, suggesting that its combinatorial interaction modeling effectively balances expressiveness and stability.

Table 3. Performance on on graph regression and classification tasks. Results are reported over 9 runs with seed 1-9. (Mean±Std) Method

REDDIT-B REDDIT-M MOLHIV (Accuracy)

WLkernel(Shervashidze et al., 2011) 81.0±3.1 GIN(Xu et al., 2018) 91.1±1.8 RetGK(Zhang et al., 2018b) 90.8±0.2 HGCN(Chami et al., 2019) 86.3±1.6 GSN (Bouritsas et al., 2022) 91.1±1.8 MSPN(Bodnar et al., 2021b) 92.7±0.9 CWN (Bodnar et al., 2021a) 93.1±1.0 G3N(Wang et al., 2023b) 89.4±2.1 MGNN(Kanatsoulis & Ribeiro, 2024) 92.0±1.8 WLHN (Nikolentzos et al., 2023) 90.7±1.9 GraphSNN (Wijesinghe & Wang, 2022) 92.7±2.0 HTML(Li et al., 2024) 90.7±0.6 CCIN 93.4±1.1

Large-Scale Social and Molecular Benchmarks. Table 3 presents the performance of CCIN on large-scale social networks and molecular graph benchmarks. CCIN also demonstrates excellent results in multi-classification tasks. On REDDIT-B, CCIN achieves 93.4 accuracy and outperforms all competitors, representing a 2.30% improvement over the classic message-passing model GIN. On the REDDIT-M dataset, CCIN maintains competitive performance compared to the baseline. On the large-scale molecular property prediction benchmark MOLHIV, CCIN achieves a ROC-AUC of 80.45, a 1.87% improvement over CWN. These results indicate that CCIN can effectively capture key information across long structural distances.

(ROC-AUC)

52.5±2.1 56.2±1.8 54.2±0.3 52.7±2.0 56.2±1.8 57.0±2.0 48.2±6.6 N/A 56.1±1.6 55.2±1.2 57.5±1.5 55.9±0.4 57.3±1.7

N/A 77.07±1.49 N/A 75.91±1.48 77.99±1.00 78.25±0.31 78.58±0.57 79.00±1.34 N/A 78.41±0.31 78.51±1.72 78.68±0.61 80.45±1.38

Peptides Benchmarks. Table 4 summarizes results on Peptides-func and Peptides-struct, which are designed to test long-range interaction (LRI) reasoning. CCIN achieves a competitive average accuracy (AP) of 0.6493 on PEPIDESFUNC, which notably outperforms GIN (0.5498,+18.09%) and CWN (0.6237, +4.11%), and maintains high competitiveness with advanced baselines GPS and Subgraphormer. These results indicate that CCIN exhibits stable and excellent performance on molecules with large-scale graphs, long information propagation distances, and higher-order structural and topological dependencies.

Table 4. Performance on on graph regression and classification tasks. Results are reported over 9 runs with seed 1-9. (Mean±Std) Model GIN (Xu et al., 2018) GatedGCN (Dwivedi et al., 2022a) SAN+LapPE(Kreuzer et al., 2021) SAN+EdgeRWSE(Dwivedi et al., 2022a) GraphFP (Luong & Singh, 2023) 2-DRFWL (Zhou et al., 2023) GPS (Rampášek et al., 2022) CWN (Bodnar et al., 2021a) GTR (Huang et al., 2023b) PathNN (Michel et al., 2023) EMPSN (Eijkelboom et al., 2023) Subgraphormer(Bar-Shalom et al., 2024) CCIN

PEPTIDES-FUNC PEPTIDES-STRUCT (AP) ↑

(MAE) ↓

0.5498±0.0079 0.5498±0.0079 0.6384±0.0121 0.6002±0.0048 0.6267±0.0073 0.5953±0.0048 0.6435±0.0041 0.6237±0.0038 0.6351±0.0079 0.6384±0.0052 0.6156±0.0080 0.6415±0.0052 0.6493±0.0262

0.3547±0.0045 0.3547±0.0045 0.2683±0.0043 0.2679±0.0015 0.3137±0.0019 0.2594±0.0038 0.2547±0.0005 0.2537±0.0042 0.2568±0.0019 0.2540±0.0046 0.2539±0.0015 0.2529±0.0020 0.2501±0.0073

ZINC. We next evaluate CCIN on the large-scale molecular regression benchmark ZINC, including ZINC-small (12K) and ZINC-FULL (250K). These datasets are widely 7

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

adopted to assess a model’s ability to capture fine-grained chemical structures and long-range dependencies, with performance measured by mean absolute error (MAE), where lower is better. Table 5 shows that CCIN displays performance comparable to classical message-passing models. On ZINC-small without edge features, CCIN surpasses classic message-passing models such as GIN and PNA, which achieves performance comparable to recent TNNs methods as TopoTune and MGNN. When with edge features, CCIN further improves its performance and remains competitive with advanced cellular and higher-order models. On the ZINC-FULL, CCIN achieves the best reported performance among all baselines. This suggests that the proposed model enables more effective propagation of higher-order structural information across deep and wide molecular graphs.

the neighborhood aggregation. With the gradual introduction of higher-order structural information, the model shows notable performance improvements on multiple datasets. When input with 1-dim structure improves performance by 10.05%, 10.76%, and 16.83% on the NCI1, NCI109, and RDT-B datasets, respectively, indicating that 1-cell structural information benefits in discriminating structures in molecular graphs and social networks. Further CCIN introduces two-dimensional information can bring relatively mild improvements. These results indicate that the appropriate introduction of higher-order information can achieve superior performance. Table 6. Performance comparison of CCIN on different neighborhood function ablation. (Mean±Std)

Table 5. Mean Absolute Error (Mean±Std) of different methods on ZINC(12K), ZINC-FULL(250K). Model

ZINC-small

w/o-B w/o-C w/o-N↑ w/o-N↓ CCIN-Full CCIN

ZINC-FULL

w/o edge feats w/i edge feats GIN (Xu et al., 2018) PNA (Corso et al., 2020) HIMP (Fey et al., 2020) GSN (Bouritsas et al., 2022) GSN (Bouritsas et al., 2022) MPSN (Bodnar et al., 2021a) G3N (Wang et al., 2023b) I2 -GNN(Huang et al., 2023a) TopoTune (Papillon et al., 2025) MGNN (Kanatsoulis & Ribeiro, 2024) CCIN

0.387±0.015 0.320±0.032 N/A 0.139±0.007 0.139±0.007 0.137±0.008 0.165±0.018 N/A 0.247±0.005 0.140±0.004 0.125±0.003

0.252±0.014 N/A 0.188±0.004 N/A 0.151±0.006 0.036±0.002 0.108±0.018 N/A 0.115±0.012 0.108±0.018 0.094±0.004 0.044±0.003 0.128±0.015 N/A 0.095±0.007 0.083±0.003 0.191±0.003 0.103±0.016 0.110±0.005 0.041±0.001 0.082±0.009 0.033±0.004

PROTEINS

NCI1

NCI109

RDT-B

RDT-M

75.40±4.94 74.14±3.84 75.41±4.15 72.88±4.21 74.95±5.43 76.14±2.53

79.46±2.23 79.44±1.87 72.95±3.17 78.37±1.66 79.56±1.63 80.69±1.22

77.56±2.11 77.91±1.96 71.78±1.35 77.45±1.71 78.54±1.42 79.71±2.05

91.43±2.43 91.95±2.35 85.53±3.17 91.65±1.13 89.15±3.61 93.43±1.15

54.26±2.35 54.89±1.57 54.98±3.73 55.46±2.41 55.49±1.54 57.30±1.78

Table 7. Performance of CCIN on input dimension with 9 runs with seed 1-9. (Mean±Std)

7. Ablation Study

max dim

PROTEINS

NCI1

NCI109

RDT-B

0 1 2

74.77±4.59 74.47±5.01 75.12±3.06

70.40±3.36 80.45±1.59 80.70±1.20

70.15±2.77 80.91±1.78 81.02±2.35

75.50±1.35 92.33±0.85 89.83±8.27

8. Conclusion

Ablation of Neighbor Functions To validate the contribution of different neighborhoods, Table 6 ablates different modules and compares the results of CCIN framework. There is some redundancy between different neighborhoods; removing some neighborhoods actually brings benefits on certain datasets. For example, on RDT-B, removing C (w/oC) achieves 91.95, improving 2.80% compared to the full version, indicating that some neighborhoods may introduce redundancy under specific data distributions, interfering with the information in the aggregation process. In contrast, CCIN achieves excellent performance using only upper and lower neighborhoods, improving performance by +4.28% and +1.17% on RDT-B and RDT-M, respectively. These results show that upper and lower neighborhoods can effectively reduce neighborhood redundancy while maintaining considerable expressive power in message aggregation, thus bringing stable and better performance.

We proposed CCWL framework and investigated the expressive power on combinatorial complexes through the Weisfeiler-Lehman test refinement in different neighborhood function. Specially, combinatorial complexes unify graph, hypergraph, simplicial complex and cellular complex, we proved that the upper and lower adjacencies are sufficient to achieve the expressive power of full CCWL framework. This theoretical insight not only resolves redundancy in existing architectures but also establishes complete refinement rules for distinguishing non-isomorphic combinatorial complexes. Building on CCWL, we propose combinatorial complex isomorphism network model that instantiates the CCWL principles. Extensive experiments on synthetic and real-world benchmarks exhibit that CCIN achieves superior performance over traditional GNNs and specialized higherorder models across diverse topological domains, validating both its expressivity and generalization capability.

Ablation of Maximum Dimension Table 7 shows the classification performance of CCIN under different maximum dimensions. The maximum dimension represents the highest-order structural level that the model can encode in 8

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Impact Statement

Bodnar, C., Frasca, F., Wang, Y., Otter, N., Montufar, G. F., Lio, P., and Bronstein, M. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026–1037. PMLR, 2021b.

This work proposes a general framework for topological deep learning via the Combinatorial Complex WeisfeilerLehman test and its neural instantiation. It lays the groundwork for learning algorithms that reason over complex relational and geometric structures. Potential applications include biological modeling, neural simulation, physical dynamics, and social networks. The model’s expressiveness may enhance prediction and structural understanding.

Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_1): i47–i56, 2005. Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657– 668, 2022.

References Anonymous, I. The logical expressiveness of topological neural networks. In The Fourteenth International Conference on Learning Representations (under review), 2026. URL https://openreview.net/forum? id=8w8jzJXjhj. Under review.

Cai, C. and Wang, Y. Convergence of invariant graph networks. In International Conference on Machine Learning, pp. 2457–2484. PMLR, 2022.

Ballester, R., Hernández-García, P., Papillon, M., Battiloro, C., Miolane, N., Birdal, T., Casacuberta, C., Escalera, S., and Hajij, M. Attending to topological spaces: The cellular transformer. arXiv preprint arXiv:2405.14094, 2024.

Chami, I., Ying, Z., Ré, C., and Leskovec, J. Hyperbolic graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.

Bar-Shalom, G., Bevilacqua, B., and Maron, H. Subgraphormer: unifying subgraph gnns and graph transformers via graph products. In Proceedings of the 41st International Conference on Machine Learning, pp. 2959–2989, 2024.

Chen, J., He, Y., Chen, D., and Yu, W. Investigating hypernode classification of complex systems based on highorder graph neural networks. Guidance, Navigation and Control, 5(01):57–69, 2025. Chen, J., Shao, Q., Zhou, M., Chen, D., and Yu, W. Ccmamba: Selective state-space models for higher-order graph learning on combinatorial complexes. arXiv preprint arXiv:2601.20518, 2026.

Battiloro, C., Spinelli, I., Telyatnikov, L., Bronstein, M., Scardapane, S., Di Lorenzo, P., et al. From latent graph to latent topology inference: differentiable cell complex module. In International conference on learning representations, 2024.

Chen, Y., Coskunuzer, B., and Gel, Y. Topological relational learning on graphs. Advances in Neural Information Processing Systems, 34:27029–27042, 2021.

Battiloro, C., Karaismailoglu, E., Tec, M., Dasoulas, G., Audirac, M., and Dominici, F. E (n) equivariant topological neural networks. In The Thirteenth International Conference on Learning Representations, 2025.

Chen, Y., Gel, Y. R., and Poor, H. V. Bscnets: Block simplicial complex neural networks. In Proceedings of the AAAI conference on Artificial Intelligence, volume 36, pp. 6333–6341, 2022.

Besta, M., Scheidl, F., Gianinazzi, L., Kwasniewski, G., Klaiman, S., Müller, J., and Hoefler, T. Demystifying higher-order graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025.

Corso, G., Cavalleri, L., Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33: 13260–13271, 2020.

Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.

de Haan, P., Cohen, T. S., and Welling, M. Natural graph networks. Advances in Neural Information Processing Systems, 33:3636–3646, 2020.

Bodnar, C., Frasca, F., Otter, N., Wang, Y., Lio, P., Montufar, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625–2640, 2021a.

Dobson, P. D. and Doig, A. J. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771–783, 2003. 9

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022a.

Hajij, M., Zamzmi, G., Papamarkou, T., Miolane, N., Guzmán-Sáenz, A., Ramamurthy, K. N., Birdal, T., Dey, T. K., Mukherjee, S., Samaga, S. N., et al. Topological deep learning: Going beyond graph data. arXiv preprint arXiv:2206.00606, 2022.

Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326–22340, 2022b.

Hajij, M., Zamzmi, G., Papamarkou, T., Guzman-Saenz, A., Birdal, T., and Schaub, M. T. Combinatorial complexes: Bridging the gap between cell complexes and hypergraphs. In 2023 57th Asilomar Conference on Signals, Systems, and Computers, pp. 799–803. IEEE, 2023.

Ebli, S., Defferrard, M., and Spreemann, G. Simplicial neural networks. arXiv preprint arXiv:2010.03633, 2020.

Hajij, M., Papillon, M., Frantzen, F., Agerberg, J., AlJabea, I., Ballester, R., Battiloro, C., Bernárdez, G., Birdal, T., Brent, A., et al. Topox: a suite of python packages for machine learning on topological domains. Journal of Machine Learning Research, 25(374):1–8, 2024.

Eijkelboom, F., Hesselink, R., and Bekkers, E. J. E (n) equivariant message passing simplicial networks. In International Conference on Machine Learning, pp. 9071–9081. PMLR, 2023.

Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33:22118– 22133, 2020.

Eitan, Y., Gelberg, Y., Bar-Shalom, G., Frasca, F., Bronstein, M. M., and Maron, H. Topological blindspots: Understanding and extending topological deep learning through the lens of expressivity. In The Thirteenth International Conference on Learning Representations, 2025. Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M. How powerful are k-hop message passing graph neural networks. Advances in Neural Information Processing Systems, 35:4776–4790, 2022.

Huang, J. and Yang, J. Unignn: a unified framework for graph and hypergraph neural networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2021.

Feng, Y., You, H., Zhang, Z., Ji, R., and Gao, Y. Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 3558–3565, 2019.

Huang, Y., Peng, X., Ma, J., and Zhang, M. Boosting the cycle counting power of graph neural networks with i2-gnns. In The Eleventh International Conference on Learning Representations, 2023a.

Feng, Y., Han, J., Ying, S., and Gao, Y. Hypergraph isomorphism computation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(5):3880–3896, 2024.

Huang, Y., Zeng, Y., Wu, Q., and Lü, L. Higher-order graph convolutional network with flower-petals laplacians on simplicial complexes. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pp. 12653–12661, 2024.

Fey, M., Yuen, J.-G., and Weichert, F. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.

Huang, Z., Wang, Y., Li, C., and He, H. Growing like a tree: Finding trunks from graph skeleton trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(5):2838–2851, 2023b.

Gärtner, T., Flach, P., and Wrobel, S. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines: 16th annual conference on learning theory and 7th kernel workshop, pp. 129–143. Springer, 2003.

Immonen, J., Souza, A., and Garg, V. Going beyond persistent homology using persistent homology. Advances in Neural Information Processing Systems, 36:63150– 63173, 2023. Kanatsoulis, C. and Ribeiro, A. Counting graph substructures with graph neural networks. In The Twelfth International Conference on Learning Representations, 2024.

Gurugubelli, S. and Chepuri, S. P. Sann: Simple yet powerful simplicial-aware neural networks. In The twelfth International Conference on Learning Representations, 2023.

Kazius, J., McGuire, R., and Bursi, R. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312–320, 2005.

Hajij, M., Istvan, K., and Zamzmi, G. Cell complex neural networks. In TDA & Beyond, 2020. 10

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618–21629, 2021.

Paolino, R., Maskey, S., Welke, P., and Kutyniok, G. Weisfeiler and leman go loopy: A new hierarchy for graph representational learning. Advances in Neural Information Processing Systems, 37:120780–120831, 2024.

Li, J., Jin, Y., Gao, H., Qiang, W., Zheng, C., and Sun, F. Hierarchical topology isomorphism expertise embedded graph contrastive learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 13518–13527, 2024.

Papamarkou, T., Birdal, T., Bronstein, M., Carlsson, G., Curry, J., Gao, Y., Hajij, M., Kwitt, R., Liò, P., Di Lorenzo, P., et al. Position paper: Challenges and opportunities in topological deep learning. arXiv preprint arXiv:2402.08871, 24:25, 2024a.

Liu, C., Ruhe, D., Eijkelboom, F., and Forré, P. Clifford group equivariant simplicial message passing networks. In The Twelfth International Conference on Learning Representations, 2024.

Papamarkou, T., Birdal, T., Bronstein, M. M., Carlsson, G. E., Curry, J., Gao, Y., Hajij, M., Kwitt, R., Lio, P., Di Lorenzo, P., Maroulas, V., Miolane, N., Nasrin, F., Natesan Ramamurthy, K., Rieck, B., Scardapane, S., Schaub, M. T., Veličković, P., Wang, B., Wang, Y., Wei, G., and Zamzmi, G. Position: Topological deep learning is the new frontier for relational learning. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 39529–39555. PMLR, 2024b.

Luong, K.-D. and Singh, A. K. Fragment-based pretraining and finetuning on molecular graphs. Advances in Neural Information Processing Systems, 36:17584– 17601, 2023. Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.

Papillon, M., Sanborn, S., Hajij, M., and Miolane, N. Architectures of topological deep learning: A survey of message-passing topological neural networks. arXiv preprint arXiv:2304.10031, 2023.

Michel, G., Nikolentzos, G., Lutzeyer, J. F., and Vazirgiannis, M. Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, pp. 24737–24755. PMLR, 2023.

Papillon, M., Bernardez, G., Battiloro, C., and Miolane, N. Topotune: A framework for generalized combinatorial complex neural networks. In Forty-second International Conference on Machine Learning, 2025.

Millán, A. P., Sun, H., Giambagli, L., Muolo, R., Carletti, T., Torres, J. J., Radicchi, F., Kurths, J., and Bianconi, G. Topology shapes dynamics of higher-order networks. Nature Physics, pp. 1–9, 2025.

Papp, P. A. and Wattenhofer, R. A theoretical comparison of graph neural network extensions. In International Conference on Machine Learning, pp. 17323–17345. PMLR, 2022.

Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020a.

Pham, P., Bui, Q.-T., Nguyen, N. T., Kozma, R., Yu, P. S., and Vo, B. Topological data analysis in graph neural networks: Surveys and perspectives. IEEE Transactions on Neural Networks and Learning Systems, 2025.

Morris, C., Rattan, G., and Mutzel, P. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824–21840, 2020b.

Puny, O., Lim, D., Kiani, B., Maron, H., and Lipman, Y. Equivariant polynomials for graph neural networks. In International Conference on Machine Learning, pp. 28191–28222. PMLR, 2023.

Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1–59, 2023.

Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501–14515, 2022.

Nikolentzos, G., Chatzianastasis, M., and Vazirgiannis, M. Weisfeiler and leman go hyperbolic: Learning distance preserving node representations. In International Conference on Artificial Intelligence and Statistics, pp. 1037–1054. PMLR, 2023.

Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., and Borgwardt, K. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp. 488–495. PMLR, 2009. 11

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.

Wen, W. and Yu, T. Hyperplr: Hypergraph generation through projection, learning, and reconstruction. In The Thirteenth International Conference on Learning Representations, 2025.

Singh, S., Chaudhary, K., Dhanda, S. K., Bhalla, S., Usmani, S. S., Gautam, A., Tuknait, A., Agrawal, P., Mathur, D., and Raghava, G. P. Satpdb: a database of structurally annotated therapeutic peptides. Nucleic acids research, 44(D1):D1119–D1126, 2016.

Wijesinghe, A. and Wang, Q. A new perspective on" how graph neural networks go beyond weisfeiler-lehman?". In International conference on learning representations, 2022. Wu, H., Yip, A., Long, J., Zhang, J., and Ng, M. K. Simplicial complex neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(1):561– 575, 2023.

Taha, D., Chapman, J., Eidi, M., Devriendt, K., and Montufar, G. Demystifying topological message-passing with relational structures: A case study on oversquashing in simplicial message-passing. In The Thirteenth International Conference on Learning Representations, 2025.

Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513–530, 2018.

Telyatnikov, L., Bernardez, G., Montagna, M., Vasylenko, P., Zamzmi, G., Hajij, M., Schaub, M. T., Miolane, N., Scardapane, S., and Papamarkou, T. Topobenchmarkx: A framework for benchmarking topological deep learning. arXiv preprint arXiv:2406.06642, 2024.

Xie, L., Gao, S., Liu, J., Yin, M., and Jin, T. K-hop hypergraph neural network: A comprehensive aggregation approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 21679–21687, 2025.

Thiede, E., Zhou, W., and Kondor, R. Autobahn: Automorphism-based graph neural nets. Advances in Neural Information Processing Systems, 34:29922– 29934, 2021.

Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.

Truong, Q. and Chin, P. Weisfeiler and lehman go paths: Learning topological features via path complexes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15382–15391, 2024.

Yanardag, P. and Vishwanathan, S. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365–1374, 2015.

Verma, Y., Souza, A. H., and Garg, V. Topological neural networks go persistent, equivariant, and continuous. In International Conference on Machine Learning, pp. 49388–49407. PMLR, 2024.

Zhang, B., Feng, G., Du, Y., He, D., and Wang, L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Conference on Machine Learning, pp. 41019–41077. PMLR, 2023a.

Wale, N., Watson, I. A., and Karypis, G. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14 (3):347–375, 2008.

Zhang, B., Luo, S., Wang, L., and He, D. Rethinking the expressive power of gnns via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023b.

Wang, P., Yang, S., Liu, Y., Wang, Z., and Li, P. Equivariant hypergraph diffusion neural operators. In The Eleventh International Conference on Learning Representations, 2023a.

Zhang, B., Gai, J., Du, Y., Ye, Q., He, D., and Wang, L. Beyond weisfeiler-lehman: A quantitative framework for gnn expressiveness. In The Twelfth International Conference on Learning Representations, 2024a.

Wang, Q., Chen, D. Z., Wijesinghe, A., Li, S., and Farhan, M. N-wl: A new hierarchy of expressivity for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b.

Zhang, B., Fan, C., Liu, S., Huang, K., Zhao, X., Huang, J., and Liu, Z. The expressive power of graph neural networks: A survey. IEEE Transactions on Knowledge and Data Engineering, 37(3):1455–1474, 2025a.

Weisfeiler, B. and Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12–16, 1968.

Zhang, D., Zhang, C., Rao, Y., Qing, L., and Zhu, C. Improved expressivity of hypergraph neural networks 12

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

through high-dimensional generalized weisfeiler-leman algorithms. In International Conference on Machine Learning, 2025b. Zhang, M., Cui, Z., Neumann, M., and Chen, Y. An endto-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018a. Zhang, Q., Xu, R., and Kondor, R. Schur nets: exploiting local structure for equivariance in higher order graph neural networks. Advances in Neural Information Processing Systems, 37:5528–5551, 2024b. Zhang, Z., Wang, M., Xiang, Y., Huang, Y., and Nehorai, A. Retgk: Graph kernels based on return probabilities of random walks. Advances in Neural Information Processing Systems, 31, 2018b. Zhou, J., Feng, J., Wang, X., and Zhang, M. Distancerestricted folklore weisfeiler-leman gnns with provable cycle counting power. Advances in Neural Information Processing Systems, 36:14293–14337, 2023.

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

A. Weisfeiler Lehman on Combinatorial Complexes A.1. Weisfeiler Lehman to Neighborhood Function Neighborhood functions define the transitive relationships of various neighborhood relations messages on combinatorial complexes. As the Definition 3.1, for combinatorial complex CC and a cell σ, rk(σ) = k, Four adjacencies as followed • Boundary adjacent B(σ) = {τ |τ ≺ σ}. These are the set of lower-rank connected cells (rk(τ ) = k − 1) on their boundary., with the neighborhood specified by the boundary matrix Br , i.e. the vectors connected with edges τ . • Co-boundary adjacent C(σ) = {τ |σ ≺ τ }. These are the higher-dimensional cells (rk(τ ) = k + 1) with on their boundary. specified by the boundary matrix BrT , i.e. the co-boundary cells of a node are the edges it is part of. • Lower adjacent N↓ (σ) = {τ |∃δ, s.t.δ ≺ σ and δ ≺ τ }. These are the cells of the same dimension as that share a lower dimensional cell (rk(τ ) = k − 1) on their boundary. • Upper adjacent N↑ (σ) = {τ |∃δ, s.t.σ ≺ δ and τ ≺ δ}. These are the cells of the same dimension as that are on co-boundary of the same higher-dimensional cell (rk(τ ) = k + 1). To clarify the visualization process of the four neighborhoods, Figure A.1 (a) shows the WL test for the boundary neighborhood, where the WL test multisets aggregate information from the (k − 1) cells to the k-cells; Figure A.1 (b) shows the WL test for the coboundary neighborhood, where the WL test multisets aggregate information from the k-cells to the (k − 1)-cells; Figure A.1 (c) shows the WL test for the lower adjacency neighborhood, where the WL test multisets of k-cell aggregate information from the k-cells from the adjacent (k − 1)-cells; and Figure A.1 (d) shows the WL test for the upper adjacency neighborhood, where the WL test multisets of k-cell aggregate information from the (k − 1) cells from the adjacent k-cells. We formally define these as follows:

, ,

(a) Boundary Wisfeiler Lehman

, ,

(b) Coboundary Wisfeiler Lehman

, ，

, , ,

(d) Upper-Adjacency Wisfeiler Lehman

Figure A.1. Illustration of Weisfeiler-Lehman tests on four neighborhood function.

Definition A.1 (Wisfeiler Lehman on Boundary ). Given a cell σ ∈ C, the boundary-based WL update is defined as (t+1) cB (σ) = HASH c(t) (σ), c(t) (τ ) | τ ∈ B(σ) , e.g., node • to edge •; edge • to face • (see Figure A.1 (a)). (t+1)

Definition A.2 (Wisfeiler Lehman on Co-boundary). The co-boundary-based WL update is defined as cC HASH c(t) (σ), c(t) (τ ) | τ ∈ C(σ) . e.g., edge • to node •; face • to edge • (see Figure A.1 (b)). 14

(σ) =

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Definition A.3 (Wisfeiler Lehman on Lower-Adjacency). The WL update based on lower adjacent cells is defined as (t+1) cN↓ (σ) = HASH c(t) (σ), (c(t) (τ ), c(t) (δ)) . where τ ∈ N↓ (σ), δ ∈ B(σ, τ ), e.g., edge • to edge • with the bridge node •; face • to face • with the bridge edge • (see Figure A.1 (c)). Definition A.4 (Wisfeiler Lehman on Upper-Adjacency). The WL update based on upper adjacent cells is defined as (t+1) cN↑ (σ) = HASH c(t) (σ), (c(t) (τ ), c(t) (δ)) | . where τ ∈ N↑ (σ), δ ∈ C(σ, τ ), e.g., node • to node • with the bridge edge •; edge • to edge • with the bridge face • (see Figure A.1 (d)). A.2. Set Type Relations: Graph and Hypergraph A graph models pairwise relations via nodes and edges, while a hypergraph generalizes this notion by allowing hyperedges to connect multiple nodes; when a hyperedge has size two, it degenerates to a standard graph edge. Hypergraph neural networks typically employ a two-stage message passing scheme: node-to-hyperedge, and hyperedge-to-node, which is analogous to information propagation in graph neural networks. Recent work interprets this mechanism from a k-hop neighborhood perspective. For example, (Feng et al., 2022) studied kernel-based message passing, (Xie et al., 2025) proposed KHGNN to capture long-range interactions, and (Paolino et al., 2024) introduced an r-loopy Weisfeiler-Leman framework. These approaches aggregate information along multi-hop paths, and under certain conditions, message passing in graphs and hypergraphs can be shown to be equivalent (Chen et al., 2025). (Zhang et al., 2025b) introduced the two-stage update operations in hypergraph neural networks as (t−1) c(t) , {{c(t−1) , u ∈ Nv (e)}}), e = HASH(ce u

(t−1) c(t) , {{c(t−1) , u ∈ Ne (v)}}), v = HASH(cv u

(7)

According to definition 3.2, we can conclude that the message passing as source nodes v up to the hyperedges e, then back to target nodes v, which are structurally equivalent to the upper adjacent N↑ . However, the hypergraph only considers message passing between the source node and the target node during the message passing process, and does not fully consider the message passing process between edges. Inspired by this equivalence, we propose a unified two-stage message passing framework that incorporates four types of neighborhood relations on graph and hypergraph. In case of the scale of hyperedges degrading to 2, the hypergraphs can be generalized into graphs. Therefore, we consider unified concepts from the Hypergraph-Weisfeiler-Leman test. In particular, a node’s neighborhood N (v) can be interpreted through upper-adjacency relations, nodes-to-edge and edge-to-node propagation can be formalized as n o c(t+1) = HASH c(t) v, c(t) τ | τ ∈ N (v) ⇒ v

n o (t+1) cN ↑(v) = HASH c(t) (v), (c(t) (τ ), c(t) (δ)) ,

(8)

where τ denotes a hyperedge incident to node v ,τ ∈ N ↑(v), δ ∈ C(v, τ ), and δ refers to a neighboring node. Similarly, hyperedges-to-hyperedges propagation via hyperedges-to-node and nodes-to-hyperedges steps can be expressed as: n o c(t+1) = HASH c(t) e, c(t) τ | τ ∈ E(e) ⇒ e

n o (t+1) cN ↓(e) = HASH c(t) (e), (c(t) (τ ), c(t) (δ)) ,

(9)

where τ ∈ N ↓(e), δ ∈ B(e, τ ), E(e) denotes the set of hyperedges adjacent to e via a shared node, which offers a view of information propagation in graphs and hypergraphs. We summarize these neighborhood relations in Table A.1. Table A.1. Neighborhood relations for nodes and hyperedges in a hypergraph. Boundary

Co-Boundary

Lower Adjacency

Upper Adjacency

Nodes v N/A Hyperedges e incident to node v N/A Nodes sharing hyperedges incident to v Hyperedges e Nodes v incident to hyperedge e N/A Hyperedges sharing nodes incident to e N/A

Case 1: Let G be a graph and let e12 = {v1 , v2 } be a 1-cell (an edge). Specifically, the boundary of e by ∂(e12 ) = {v1 , v2 }, and the co-boundary of a node v1 by δ(v1 ) = {e′ ∈ H | e′ ∈ {e12 , e14 }}, node v2 by δ(v2 ) = {e′ ∈ H | e′ ∈ {e12 , e24 , e23 }}. we consider the boundary and co-boundary as special cases of adjacency-WL, as followed, (t+1) (i) For a node v1 , the co-boundary update cC (v1 ) = HASH c(t) (v1 ), {{c(t) (e′ ) | e′ ∈ δ(v) = {e12 , e14 }}} aggregates exactly the colors of 1-cells that are pairwise lower adjacent via the boundary bridge v1 . (t+1) (ii) For an edge e12 = {v1 , v2 }, the boundary update cB (e12 ) = HASH c(t) (e12 ), {{c(t) (u) | u ∈ ∂(e12 ) = {v1 , v2 }}} aggregates exactly the colors of the two 0-cells that are upper adjacent witnessed by the co-boundary e12 . 15

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Figure A.2. Illustration of message aggregation on graph, hypergraph.

Proof. As illustrated in Figure A.2, in both graphs and hypergraphs, message passing from a node to hyperedge and back to its connected node corresponds to propagation within the upper neighborhood, whereas message passing from a hyperedge to a node and back to its connected hyperedge corresponds to propagation within the lower neighborhood. For instance, the edge e12 = {v1 , v2 }, we can obtain that, (i) By definition of co-boundary, δ(v1 ) is the set of incident edges e′ with v1 ∈ ∂(e′ ). Hence two edges e12 , e14 ∈ δ(v1 ) satisfy v1 ∈ ∂(e12 ) ∩ ∂(e14 ), i.e., e12 ∈ N↓ (e14 ) with boundary bridge v1 ∈ B(e12 , e14 ). Therefore the multiset {{c(t) (e′ ) | e′ ∈ δ(v1 )}} coincides with the multiset of colors of lower-adjacent 1-cells connected through the bridge v1 . (ii) For e12 = {v1 , v2 }, ∂(e12 ) = {v1 , v2 } by the definition of Moreover v1 and v2 are upper adjacent since {v1 , v2 } ⊆ ∂(e12 ), and e ∈ C(v1 , v2 ). Thus the multiset boundary. c(t) (v1 ), c(t) (v2 ) is exactly the multiset of node colors that is coupled by upper adjacency witnessed by the e12 . Case 2. Let H = (V, E) be a hypergraph. Consider a hyperedge e = {v1 , v2 , . . . , vk } ∈ E with k ≥ 2. We view e as a generalized 1-cell whose boundary is the node set ∂(e) = {v1 , . . . , vk }. For any node v ∈ V , its co-boundary is defined as δ(v) = {e′ ∈ E | v ∈ e′ }. Under the standard projection (or clique expansion) of a hypergraph G ′ = Proj(H) (Wen & Yu, 2025), each hyperedge e = {v1 , . . . , vk } is mapped to a set of pairwise connections {(vi , vj ) | 1 ≤ i < j ≤ k}, i.e., every pair of nodes in the hyperedge is connected by an edge in the projected graph G ′ . Therefore, the projected graph G ′ reduces all hyperedges to edges of cardinality 2. Consequently, Case 1 applies to G ′ , where the induced incidence adjacencies align precisely with the upper- and lower-adjacency relations defined earlier. More generally, in the original hypergraph, a hyperedge e = {v1 , . . . , vk } extends this construction. Its boundary ∂(e) induces upper adjacency among all node pairs contained in e, and aggregating over these nodes recovers the boundary-type update. Similarly, the co-boundary of a node v (the set of hyperedges containing v), which induces lower adjacency among hyperedges that intersect at v. Therefore, these cases on graph and hypergraph illustrate a broader condition: boundary and co-boundary aggregations can be expressed as same-dimensional upper- and lower-adjacency aggregations, without altering the multisets used in the hash functions. This observation justifies the set-type substructure of combinatorial complex weisfeiler-leman update process. A.3. Part-type Relations: Simplicial and Cellular Complex Simplicial and cellular complexes naturally admit boundary and co-boundary operators, which encode cross-dimensional incidence relations between cells. Accordingly, message passing on such complexes has traditionally been formulated in terms of downward (boundary) and upward (co-boundary) maps. An alternative but closely related viewpoint is to describe these incidence relations via adjacency relations among cells of the same dimension. Two k-cells are said to be lower-adjacent if they share a common (k −1)-cell, and upper-adjacent if they share a common (k +1)-cell. In details, boundary- and co-boundary-based information can be encoded through same-dimensional lower and upper adjacency relations augmented with appropriate bridge cells. From the perspective of Weisfeiler-Leman refinement, prior works (Michel et al., 2023; Bodnar et al., 2021a;b) have shown that, for simplicial and cellular complexes, restricting the update rule to boundary information and upper-adjacency neighborhoods already suffices to match the expressive power of more (t) (t) (t) (t) (t) general WL schemes. Specifically, the refinement rule HASH c (σ), cB (σ), cC (σ), cN↓ (σ), cN↑ (σ) in distinguishing non-isomorphic simplicial or cellular complexes. However, boundary and shared-boundary relations are cross-dimensional. For instance, in a graph viewed as a 1-dimensional complex, the boundary of an edge is a pair of nodes, and in a simplicial complex, the boundary of a face consists of edges. In both cases, the boundary operator maps a k-cell to a collection of (k − 1)-cells. Even shared-boundary relations between two k-cells (e.g., two faces sharing an edge) are mediated by a 16

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

lower-dimensional bridge cell. In contrast, the Weisfeiler-Leman refinement operates within a fixed dimension, updating and relabeling cells of the same type (nodes with nodes, edges with edges, faces with faces) at each iteration. Moreover, the lower- and upper-adjacency color multisets heave encoded the cross-dimensional incidence information. From lower adjacent , for each lower-adjacent cell τ ∈ N↓ (σ), the bridge cell δ ∈ B(σ, τ ) = ∂(σ) ∩ ∂(τ ) is a shared boundary cell of σ and τ . Thus, each element (cτ , cδ ) explicitly contains the color of a boundary cell of σ. Similarly, from the upper adjacent, for each upper-adjacent cell τ ∈ N↑ (σ), the bridge cell δ ∈ C(σ, τ ) = δ(σ) ∩ δ(τ ) is a shared co-face of σ and τ , and the token (cτ , cδ ) explicitly contains the color of a co-boundary cell of σ. the boundary-type multiset {c(ζ) | ζ ∈ ∂(σ)} can be functionally recovered from cN↓ (σ) by projecting onto the second component of the tokens, and the co-boundary-type multiset {c(γ) | γ ∈ δ(σ)} can be recovered from cN↑ (σ). Therefore, lower- and upper-adjacency WL updates do not discard boundary or co-boundary information; instead, they encode such cross-dimensional incidence relations within same-dimensional neighborhoods. This observation motivates our design choice: using upper and lower adjacency yields a unified, same-dimensional CCWL scheme that faithfully captures boundary and co-boundary aggregations while avoiding explicit cross-dimensional message passing. As a result, the resulting refinement procedure is conceptually simpler and more readily extensible to hypergraphs and general combinatorial complexes.

Figure A.3. Illustration of message aggregation on simplicial complex, cellular complex.

Case 3. Consider two adjacent 2-simplices (faces) f1 = {v1 , v2 , v3 }, f2 = {v2 , v3 , v4 }, which share the common edge e23 = {v2 , v3 }. The edge sets are ∂(f1 ) = {e12 , e23 , e13 }, ∂(f2 ) = {e23 , e24 , e34 }, where e12 = {v1 , v2 }, e13 = {v1 , v3 }, e24 = {v2 , v4 }, and e34 = {v3 , v4 }. Its four neighborhood relations are followed as • Boundary: ∂(f1 ) = {e12 , e23 , e13 }, ∂(f2 ) = {e23 , e24 , e34 }, ∂(eij ) = {vi , vj }, • Co-boundary: δ(e12 ) = δ(e13 ) = {f1 }, δ(e24 ) = δ(e34 ) = {f2 }, δ(e23 ) = {f1 , f2 }. • Lower adjacency: Two k-cells σ, τ are lower-adjacent if they share a common boundary (k−1)-cell, i.e., ∂(σ)∩∂(τ ) ̸= ∅. In this example: (1) Nodes (0-cells) have no lower adjacency since they have no boundary. (2) Edges (1-cells) are lower-adjacent if they share a node, e.g., e12 ∈ N↓ (e23 ) (share v2 ), e23 ∈ N↓ (e34 ) (share v3 ). (3) Faces (2-cells) are lower-adjacent since ∂(f1 ) ∩ ∂(f2 ) = {e23 } ̸= ∅, hence f1 ∈ N↓ (f2 ), with bridge cell e23 . • Upper adjacency. Two k-cells σ, τ are upper-adjacent if they share a common co-boundary (k+1)-cell, i.e., δ(σ)∩δ(τ ) ̸= ∅. In this example: (1) Nodes (0-cells) are upper-adjacent if they belong to a common edge, e.g., v2 ∈ N↑ (v3 ) (common co-face e23 ), v1 ∈ N↑ (v2 ) (common co-face e12 ). (2) Edges (1-cells) are upper-adjacent if they belong to a common face, e.g., e12 ∈ N↑ (e13 ) (co-face f1 ), e23 ∈ N↑ (e24 ) (co-face f2 ). (3) Faces (2-cells) have no upper adjacency since there is no 3-cell. Proof. By definition, boundary B(σ, τ ) := ∂(σ) ∩ ∂(τ ) and co-boundary C(σ, τ ) := δ(σ) ∩ δ(τ ) relations are crossdimensional: the operator ∂ maps k-cells to (k−1)-cells, while operator δ maps k-cells to (k+1)-cells. Lower and upper adjacency, in contrast, relate cells of the same dimension and are witnessed by shared boundary or co-boundary cells. As illustrated in Figure. A.3, we observe that the shared edge e23 serves as the bridge cell witnessing both the lower adjacency between f1 and f2 and the co-boundary relations δ(e23 ) = {f1 , f2 }. we conclude that: 17

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

(1) The boundary of the shared edge is ∂(e23 ) = {v2 , v3 }. Its lower-adjacent edges include, e12 , e24 (sharing v2 ) and e13 , e34 (sharing v3 ). Here, B(e23 , e12 ) = {v2 }, B(e23 , e24 ) = {v2 }, B(e23 , e13 ) = {v3 }, B(e23 , e34 ) = {v3 }, and therefore [ B(e23 , τ ) = {v2 , v3 } = ∂(e23 ). (10) τ ∈N↓ (e23 )

(2) The co-boundary of the shared edge is δ(e23 ) = {f1 , f2 }, where e23 is upper-adjacent to e12 and e13 via the coface f1 , and to e24 and e34 via the common co-face f2 . C(e23 , e12 ) = {f1 }, C(e23 , e13 ) = {f1 }, C(e23 , e24 ) = {f2 }, C(e23 , e34 ) = {f2 }. Thus, [ C(e23 , τ ) = {f1 , f2 } = δ(e23 ). (11) τ ∈N↑ (e23 )

(3) For two faces f1 , f2 , their adjacency exposes shared boundary information. The faces satisfy ∂(f1 ) ∩ ∂(f2 ) = {e23 }, so f1 ∼↓ f2 with bridge cell e23 , i.e., B(f1 , f2 ) = {e23 }. Therefore, lower adjacency between faces captures their shared boundary. Note that in this example ∂(f1 ) = {e12 , e23 , e13 } contains edges that are not shared with any other 2-cell (namely e12 , e13 ), so they cannot be recovered from B(f1 , τ ) over τ ∈ N↓ (f1 ); rather, they are exposed by the cross-dimensional boundary operator itself (e.g., this condition holds in a tetrahedron). This case shows that boundary and co-boundary are cross-dimensional incidence relations, whereas lower and upper adjacency relate same-dimensional cells and expose incidence information via bridge cells B(σ, τ ) and C(σ, τ ). In particular, for the shared edge e23 , the equalities [ [ ∂(e23 ) = B(e23 , τ ), δ(e23 ) = C(e23 , τ ) (12) τ ∈N↓ (e23 )

τ ∈N↑ (e23 )

hold exactly, demonstrating how same-dimensional adjacency (augmented with bridge cells) can faithfully encode crossdimensional neighborhoods used in WL refinement.

Case 4. Consider the 3-simplex (tetrahedron) σ = {v1 , v2 , v3 , v4 }. Its 2-faces are f1 = {v1 , v2 , v3 }, f2 = {v1 , v2 , v4 }, f3 = {v1 , v3 , v4 }, f4 = {v2 , v3 , v4 }. The 1-cells (edges) are e12 , e13 , e14 , e23 , e24 , e34 , and the 0-cells are v1 , v2 , v3 , v4 . • Boundary operator satisfies ∂(σ) = {f1 , f2 , f3 , f4 }, ∂(f1 ) = {e12 , e13 , e23 },∂(f2 ) = {e12 , e14 , e24 }, ∂(f3 ) = {e13 , e14 , e34 }, ∂(f4 ) = {e23 , e24 , e34 }, ∂(eij ) = {vi , vj }. • Co-boundary includes the nodes: δ(v1 ) = {e12 , e13 , e14 }, δ(v2 ) = {e12 , e23 , e24 }, δ(v3 ) = {e13 , e23 , e34 }, δ(v4 ) = {e14 , e24 , e34 }, and edges eij : δ(eij ) = {fi , fj }, but when i = 1, 2, 3, 4, δ(fi ) = {σ} δ(σ) = ∅. Proof. For same-dimensional cells η, ζ, define bridge sets, boundary B(η, ζ) := ∂(η) ∩ ∂(ζ), and co-boundary C(η, ζ) := δ(η) ∩ δ(ζ), so that ζ ∈ N↓ (η) iff B(η, ζ) ̸= ∅, and ζ ∈ N↑ (η) iff C(η, ζ) ̸= ∅. Here, we need to prove that for every cell η of dimension k ∈ {1, 2}, the following equalities hold: [ [ ∂(η) = B(η, ζ), δ(η) = C(η, ζ). (13) ζ∈N↓ (η)

ζ∈N↑ (η)

(1) Edges (k = 1). For an edge η = eij , ei j = ∂fi ∩ ∂fj . Similar to Equation 12 in Case 3, eij , we can conclude that • For the boundary ∂(eij ) = {vi , vj }, each node has degree 3 in a tetrahedron, there exists an edge ζ = eiℓ ̸= eij sharing vi , hence S B(eij , eiℓ ) = {vi }, and similarly an edge ζ ′ = ejm ̸= eij sharing vj , hence B(eij , ejm ) = {vj }. Therefore ∂(eij ) ⊆ ζ∈N↓ (eij ) B(eij , ζ), while the reverse inclusion holds trivially because every bridge is a boundary node of eij . This proves the boundary equality for all edges. • For the co-boundary, each edge eij lies in exactly two faces; for example δ(e12 ) = {f1 , f2 }. Choose ζ to be another edge in f1 (e.g. e13 ), then C(e12 , e13 ) = {f1 }, and choose ζ ′ to be another edge in f2 (e.g. e14 ), then C(e12 , e14 ) = {f2 }. Thus both incident faces of e12 appear in the union over C-bridges. The same argument applies to any edge, proving the co-boundary equality for all edges. 18

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

(2) Faces (k = 2). For instance, the face η = f1 = {v1 , v2 , v3 }, we can obtain that • Its boundary edges are ∂(f1 ) = {e12 , e13 , e23 }. Each boundary edge is shared with exactly one other face:B(f1 , f2 ) = S {e12 }, B(f1 , f3 ) = {e13 }, B(f1 , f4 ) = {e23 }. Hence ζ∈N↓ (f1 ) B(f1 , ζ) = {e12 , e13 , e23 } = ∂(f1 ). The same holds for any face by symmetry. σ, i.e. δ(fi ) = {σ}. Moreover, for any distinct faces fi ̸= fj , we • For the co-boundary, each face has the unique co-face S have C(fi , fj ) = {σ}, hence fj ∈ N↑ (fi ) and ζ∈N↑ (fi ) C(fi , ζ) = {σ} = δ(fi ).

Table A.2. Neighborhood relations in a 3-cell complex (here 0,1,2,3-cells represent nodes,edges,faces,tetrahedra, respectively). Cell σ Nodes (0-cells) v Edges (1-cells) e Faces (2-cells) f Tetrahedral (3-cells) t

Boundary ∂(σ)

Co-Boundary δ(σ)

Lower Adjacency N↓ (σ)

Upper Adjacency N↑ (σ)

N/A nodes (nodes) of e Boundary edges of f Boundary faces of t

Edges incident to v Faces incident to e Tetrahedral incident to f N/A

N/A Edges sharing a node with e Faces sharing an edge with f Tetrahedral sharing a face with t

Nodes sharing an edge with v Edges sharing a face with e Faces sharing a tetrahedron with f N/A

Remark Lower and upper adjacency expose exactly the shared incidence structure among same-dimensional cells; they are not intended to enumerate private boundary elements of isolated or top-dimensional cells. We summarize the neighborhood relation in Table A.2. There are two special cases in which the boundary equality in (13) does not apply. First, nodes have no boundary, the boundary equality is vacuous for k = 0. Second, although the co-boundary equality holds trivially for the unique top-dimensional cell σ since δ(σ) = ∅, the S boundary equality fails in this case. Indeed, because σ is the only 3-cell in the complex, N↓ (σ) = ∅, and consequently ζ∈N↓ (σ) B(σ, ζ) = ∅ ̸= ∂(σ). Therefore, the boundary equality for the top-dimensional cell holds only when additional 3-cells sharing boundary faces with σ are present. • Nodes (0-cells). Nodes have no boundary by definition as ∂(v) = ∅ and the boundary recovery identity is vacuous for k = 0. In contrast, the co-boundary recovery identity holds exactly. Indeed, for a node vi , its co-boundary is δ(vi ) = {eij | j ̸= i}. For any neighbor vj ∈ N↑ (vi ), the bridge set satisfies C(vi , vj ) = δ(vi ) ∩ δ(vj ) = {eij }. Each edge eij ∈ δ(vi ) appears in exactly one bridge set with some upper-adjacent node vj , and we obtain δ(vi ) = S vj ∈N↑ (vi ) C(vi , vj ). For 0-cells, the co-boundary can be recovered from upper adjacency together with bridge cells. • Tetrahedral (3-cell). For the tetrahedron σ, there is no higher-dimensional cell, and thus δ(σ) = ∅ , N↑ (σ) = ∅, so the co-boundary recovery identity holds trivially. However, σ is the unique 3-cell in the complex, and consequently N↓ (σ) = ∅. Although the boundary of σ is nonempty, ∂(σ) = {f1 , f2 , f3 , f4 }, none of these boundary faces is shared S with another 3-cell. Hence, ζ∈N↓ (σ) B(σ, ζ) = ∅ ̸= ∂(σ). Thus, the boundary recovery identity does not hold for the unique top-dimensional cell unless additional 3-cells are present that share boundary faces with σ.

Existing research has only focused on geometric structural relationships within two dimensions (faces), due to the lack of three-dimensional volumetric datasets. This direction requires further investigation. Case 5 (Combinatorial complex). Let CC = (S, C, rk) be a combinatorial complex as in Definition X, and let σ ∈ C be a k-cell, i.e., rk(σ) = k. We define the boundary and co-boundary operators purely in terms of rank: ∂(σ) := {η ∈ C | η ⊂ σ, rk(η) = k − 1}, δ(σ) := {γ ∈ C | σ ⊂ γ, rk(γ) = k + 1}. For the Same-dimensional adjacencies and bridge sets, such as the two k-cells σ, τ ∈ C, define the bridge sets as B(σ, τ ) := ∂(σ) ∩ ∂(τ ), C(σ, τ ) := δ(σ) ∩ δ(τ ). The lower- and upper-adjacency neighborhoods of σ are N↓ (σ) := {τ ∈ C | rk(τ ) = k, τ ̸= σ, B(σ, τ ) ̸= ∅}, N↑ (σ) := {τ ∈ C | rk(τ ) = k, τ ̸= σ, C(σ, τ ) ̸= ∅}. Coverage condition We define that σ is boundary-covered if every boundary cell of σ is shared with some other kcell: ∀η ∈ ∂(σ), ∃τ ∈ C : rk(τ ) = k, τ ̸= σ, η ∈ ∂(σ) ∩ ∂(τ ). For example, for a face f1 , there exists a face f2 (e.g., rk(f1 ) = rk(f2 )) such that e23 ∈ ∂(f1 ) ∩ ∂(f2 ). Similarly, σ is co-boundary-covered if every co-boundary cell of σ is shared with some other k-cell: ∀γ ∈ δ(σ) ∃τ ∈ C : rk(τ ) = k, τ ̸= σ, γ ∈ δ(σ) ∩ δ(τ ). From the bridge sets in CC, let σ be a k-cell in a combinatorial complex. If σ is boundary-covered, then ∂(σ) = S S B(σ, τ ). If σ is co-boundary-covered, then δ(σ) = τ ∈N↓ (σ) τ ∈N↑ (σ) C(σ, τ ). 19

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Proof. We prove the boundary statement (⊆) Let η ∈ ∂(σ). Since σ is boundary-covered, thereSexists a k-cell τ ̸= σ such that η ∈ ∂(σ) ∩ ∂(τ ) = B(σ, τ ). Hence B(σ, τ ) ̸= ∅, so by definition τ ∈ N↓ (σ), and thus η ∈ τ ∈N↓ (σ) B(σ, τ ). (⊇) For any τ ∈ N↓ (σ), we have B(σ, S τ ) = ∂(σ) ∩ ∂(τ ) ⊆ ∂(σ), hence the union of such sets is contained in ∂(σ). Combining the two inclusions yields ∂(σ) = τ ∈N↓ (σ) B(σ, τ ). The co-boundary follows the same argument with δ and C(·, ·).

B. Proof Theorem B.1. Combinatorial Complex Weisfeiler Lehman Definition B.1. A coloring is a rule that assigns to every cell σ of a combinatorial complex CC a color chosen from a fixed palette. For a given complex CC and a cell σ ∈ CC , we write cCC σ for the color assigned to σ by the coloring c . Definition B.2. Let CC 1 , CC 2 be two combinatorial complexes and c be a coloring function. We denote CC 1 , CC 2 are c-similar, denoted by cCC 1 , cCC 2 , if the number of cells in CC 1 colored with a given color equals the number of cells in CC 2 with the same color. Otherwise, we have cCC 1 ̸= cCC 2 . Definition B.3. A combinatorial coloring c refines a combinatorial coloring d, denoted by c ⊑ d, if for all cell complexes X 1 2 1 2 and Y and all σ ∈ CC 1 and τ ∈ CC 2 , cCC = cCC implies dCC = dCC . Additionally, if d ⊑ c, we say the two colorings σ τ σ τ are equivalent and we represent it by c ≡ d. Lemma B.4. Let ct and dt be the CCWL colorings using full and reduced schemes, respectively. Then for all t, we have: ct ⊑ dt+1 , dt+1 ⊑ ct ⇒ ct ≡ dt+1 . Proof. Assume that for a fixed t ≥ 0, the following two refinement relations hold: (1) ct ⊑ dt+1 , (2) dt+1 ⊑ ct . By the definition of refinement, condition (1) means that for any two combinatorial complexes CC 1 , CC 2 and any cells σ ∈ CC, 1 ,t 1 ,t+1 2 ,t 1 ,t+1 2 ,t+1 2 ,t+1 1 ,t τ ∈ CC 2 , cCC = cCC =⇒ dCC = dCC . Similarly, condition (2) implies:dCC = dCC =⇒ cCC = σ τ σ τ σ τ σ CC 2 ,t CC 1 ,t CC 2 ,t CC 1 ,t+1 CC 2 ,t+1 . Combining both implications, we can obtain: cσ ⇐⇒ dσ = dτ . This means that the cτ = cτ colorings ct and dt+1 induce the same partition on the set of all cells across all combinatorial complexes. By Definition 3, we conclude that ct ≡ dt+1 . Since this holds under the given assumptions for arbitrary t, the lemma is proved.

Proof of Lemma 4.4. Suppose CC 1 and CC 2 are isomorphic, there is a bijection φ : C1 → C2 that respects both cell ranks and all the neighborhood relations CCWL uses: B, C, N↓ , and N↑ . We prove corresponding cells always get the same color. From the Definition 4.2 at t = 0, initialization of cells are the same, and φ preserves it, so σ and φ(σ) start identically colored. We suppose that it holds at step t. To compute c(t+1) (σ), CCWL hashes a tuple of c(t) (σ) and the color multisets from its four neighborhoods. But φ maps those neighborhoods exactly to those of φ(σ), and by the induction hypothesis, all neighbors already share colors. In the case of the HASH is injective function and two input tuples are identified, then final colorings are the same as c(t+1) (σ) = c(t+1) (φ(σ)). The argument repeats cleanly for every t. And since φ is a bijection function, the color multisets over the two complexes remain identical at every iteration. Proof for Lemma 4.5. Assume that c ⊑ d, i.e., for any combinatorial complexes CC 1 (S1 , C1 , rk 1 ), CC 2 (S2 , C2 , rk 2 ) and CC 2 CC 2 CC CC 2 cells σ ∈ CC 1 , τ ∈ CC 2 , cCC =⇒ dCC the contrapositive holds: =⇒ cCC σ = cτ σ = dτ . Equivalently, σ ̸= dτ σ ̸= CC d CC 2 CC 2 1 cτ . Suppose for contradiction that the multisets of c-colors are cσ | σ ∈ P (S1 ) = cτ | τ ∈ P (S2 ) . This 2 1 means there exists a bijection ϕ : P (S1 ) → P (S2 ) such that for all σ ∈ P (S∞ ), cCC = cCC σ ϕ(σ) . Since c ⊑ d, we have: 2 2 2 1 1 cCC = cCC dCC 1 = dCC for all σ ∈ A, dCC = dCC multisets of d-colors σ σ ϕ(σ) =⇒ ϕ(σ) . Therefore, ϕ(σ) , which implies that the CCσ CC CC 1 1 2 are also equal: dσ | σ ∈ A = dτ | τ ∈ B . But this contradicts assumption that the CCdσ | σ ∈ A ̸= CC 2 CC 1 2 dτ | τ ∈ B . Hence, our supposition must be false, and we conclude: cσ | σ ∈ A ̸= cτ | τ ∈ B .

Proof for Corollary 4.6. Assume that c ⊑ d, i.e., for any combinatorial complexes CC 1 (S1 , C1 , rk1 ), CC 2 (S2 , C2 , rk2 ) and CC 1 1 2 1 2 2 cells σ ∈ CC 1 , τ ∈ CC 2 , cCC = cCC =⇒ dCC = dCC ̸= dCC =⇒ σ τ σ τ . Equivalently, the contrapositive holds: dσ τ CC 1 CC 2 CC 1 CC 2 cσ ̸= cτ . Now, suppose for contradiction that c = c , meaning the multisets of c-colors over the entire cell sets are CC 2 1 equal: cCC | σ ∈ C = c | τ ∈ C . This implies there exists a bijection ϕ : C → C such that for all σ ∈ C1 , 1 2 1 2 σ τ CC 2 CC 2 CC 2 CC 2 CC 1 CC 1 CC 1 CC 1 cσ = cϕ(σ) . Since c ⊑ d, we have: cσ = cϕ(σ) =⇒ dσ = dϕ(σ) . Therefore, for all σ ∈ C1 , dσ = dϕ(σ) , which 1 2 implies that the multisets of d-colors are also equal: dCC | σ ∈ C1 = dCC | τ ∈ C2 , i.e., dCC 1 = dCC 2 . But this σ τ CC 1 CC 2 contradicts the assumption that d ̸= d . Hence, the supposition must be false, then conclude: cCC 1 ̸= cCC 2 . 20

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Remark The regularity conditions stated in Lemma 4.7 are sufficient for common combinatorial structures, but not necessary. For graphs, hypergraphs, simplicial complexes, and cell complexes, only information transfer with rank differences of 0 or 1 is handled, and the pattern of associations between ranks is more strictly restricted: upper and lower adjacencies already encode all boundary and co-boundary relationships. Theorem 4.8 provides the generalized update rule to demonstrate the expressive power of the two schemes is the same, i.e., they distinguish the same set of non-isomorphic CC. Proof for Lemma 4.7. Consider two combinatorial complexes CC 1 = (S1 , C1 , rk1 ) and CC 2 = (S2 , C2 , rk2 ). Let at denote the colorings of the generalized rules HASH(ctσ , ctB (σ), ctC (σ), ctN↓ (σ), ctN·,↑ (σ)) and bt denote the colorings restricted rules HASH(ctσ , ctB (σ), ctN↓ (σ), ctN↑ (σ)) at iteration t. Since the generalized rule incorporates the additional co-boundary colors ctC (σ), it is straightforward that at ⊑ bt (Definition B.3). By induction, if bt ⊑ at holds, then at ≡ bt . The base step holds trivially in the case of all cells are initialized with identical colors. Assume σ ∈ CC 1 and τ ∈ CC 2 are t t cells of the same rank such that bt+1 = bt+1 σ τ . Then the arguments of the hash function must coincide. Suppose bσ = bτ , t t t t t t t t b↓ (σ) = b↓ (τ ), b↑ (σ) = b↑ (τ ), bB (σ) = bB (τ ) hold. To demonstrate that these equalities imply bC (σ) = bC (τ ) of the generalized rules. By the definition of the upper adjacencies N↑ (σ) (cN↑ (σ) = {{(cτ , cδ )|τ ∈ N↑ (σ) and δ ∈ C(σ, τ )}}.), it holds bt↑ (σ) = bt↑ (τ ) that ensures that {{btδσ | (·, btδσ ) ∈ bt↑ (σ)}} = {{btδτ | (·, btδτ ) ∈ bt↑ (τ )}}.

(14)

Each coface δσ ∈ N↑ (σ) (and analogously for τ ) contributes exactly rk(σ) + 1 tuples to its upward multisets. After removing repeated entries corresponding to these cofaces, we obtain {{btδσ | δσ ∈ N↑ (σ)}} = {{btδτ | δτ ∈ N↑ (τ )}},

(15)

which directly implies btC (σ) = btC (τ ). By the induction hypothesis, we further have atσ = atτ , at↓ (σ) = at↓ (τ ), at↑ (σ) = at↑ (τ ), atB (σ) = atB (τ ), and atC (σ) = atC (τ ). Therefore, at+1 = at+1 σ τ , concluding the proof.

Proof of Theorem 4.8. Let at denote the coloring obtained from the full generalized rule as the mapping func (t) (t) (t) (t) tion HASH c(t) (σ), cB (σ), cC (σ), cN↓ (σ), cN↑ (σ) , and bt denote the coloring from the restricted rule as (t)

(t)

(t+1)

(σ) = bB

HASH(cσ , cN↓ (σ), cN↑ (σ)). Since at includes more structural information, we have at ⊑ bt . By induction, we further prove that b(t+1) ⊑ at , which implies at ≡ bt . we initial colors are determined by c(0) (σ) = HASH0 (rk(σ), |B(σ)|, |C(σ)|). Since |B(σ)| and |C(σ)| are determined by the neighborhood degrees, a0 ≡ b0 . Suppose bt+2 = bt+2 for any two cells σ σ τ (t+1) (t+1) and τ from combinatorial complexes CC 1 , CC 2 , respectively. By definition of the update rule, we obtain that bσ = bτ , (t+1) (t+1) (t+1) (t+1) bN↑ (σ) = bN↑ (τ ), bN↓ (σ) = bN↓ (τ ). The next step aims to clarify that the boundary B and co-boundary C also hold as bB

(t+1)

(τ ) and bC

(t+1)

(σ) = bC

(t+1)

(τ ). Given bN↑ (σ) = bN↑ (τ ), by definition nn oo nn oo (t+1) (t+1) (t+1) (t+1) (t+1) (t+1) bδσ |(·, bδσ ) ∈ bN↑ (σ) = bδτ |(·, bδτ ) ∈ bN↑ (τ ) ,

(16)

Note that the upper adjacent cells N↑ (σ) = {τ |∃δ, s.t.σ ≺ δ and τ ≺ δ}. we know that the co-boundary adjacent cells C(σ) = {δ|σ ≺ δ}. From the definition that upper adjacent colors σ is cN↑ (σ) = {{(cτ , cδ )|τ ∈ N↑ (σ) and δ ∈ C(σ, τ )}}, co-boundary adjacent cC (σ) = {{cτ |τ ∈ C(σ)}}, nn oo nn oo (t+1) (t+1) (bδσ , b(t+1) )|δ ∈ N↑ (σ), γ ∈ C(σ, δ) = (bδτ , b(t+1) )|δ ∈ N↑ (σ), γ ∈ C(σ, δ) , γσ γτ

(17)

This multiset includes all upper adjacent cells δ that contain σ in their boundary, along with colors of their co-boundary neighbors γ. According to the iteration of WL test, cells with different boundary sizes have different colors. Therefore, we can partition these two multi-sets by the size of the cell boundaries, while preserving the equality between these sub-multisets. Since σ is a boundary cell of δ, the tuple (δ, σ) appears with multiplicity |B(δ)| − 1. For each n ∈ N, we rewrite nn oo nn oo (t+1) (t+1) (t+1) (t+1) (t+1) (t+1) bδσ |(·, bδσ ) ∈ bN↑ (σ) and |B(δσ )| = n = bδτ |(·, bδτ ) ∈ bN↑ (τ ) and |B(δτ )| = n ,

(18)

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Then for cell γ ∈ C(γ), γ exchanges messages with all the other boundary cells of γσ , γτ . Thus, the value of |B(δ)| is (t+1) encoded in bδ , can partition the multiset by boundary size. Each co-boundary cell δ with |B(δ)| = n sends n − 1 repeated messages. Removing multiplicities accordingly reconstructs the true multiset: nn oo nn oo (t+1) (t+1) bδ | δ ∈ C(σ) = bδ | δ ∈ C(τ ) .

(19) (t+1)

(t+1)

we infer that the multisets of colors of co-boundary cells C(σ) and C(τ ) are identical. That is, bC (σ) = bC (τ ). If (t+2) (t+2) (t+1) (t+1) (t+1) t t bσ = bτ , we conclude aσ = aτ , hence b ⊑ a by the induction hypothesis that a already refines all colorings. Thus b(t+1) ⊑ a(t+1) , completing the inductive step. Therefore, at ≡ bt for all t, and both schemes are equally (t+1) (t+1) expressive. Given bN↓ (σ) = bN↓ (τ ), by definition nn oo nn oo (t+1) (t+1) (t+1) (t+1) (t+1) (t+1) bδσ |(·, bδσ ) ∈ bN↓ (σ) = bδτ |(·, bδτ ) ∈ bN↓ (τ ) ,

(20)

The lower adjacent cells N↓ (σ) = {τ |∃δ, s.t.δ ≺ σ and δ ≺ τ }. we nn know that the boundary adjacent cell B(σ)oo = {θ ≺ σ}. (t)

(t)

From the definition, the lower adjacent colors of σ are: cN↓ (σ) = (cθ , cω ) | θ ∈ B(σ), ω ∈ C(θ) \ {σ} , and the nn oo (t) (t) boundary colors of σ are: cB (σ) = cθ | θ ∈ B(σ) . This neighborhood representation includes all boundary cells θ of σ and their other cofaces ω. Since each such pair (θ, ω) occurs |C(θ)| − 1 times, we can group the elements by the value of |C(θ)| to remove neighborhood redundancy, as follows nn oo nn oo (t+1) (t+1) (bθσ , b(t+1) ) | θ ∈ B(σ), ω ∈ C(θ) \ {σ} = (bθτ , b(t+1) ) | θ ∈ B(τ ), ω ∈ C(θ) \ {τ } , ωσ ωτ

(21)

This multiset includes all boundary cells θ that belong to σ, together with their co-boundary neighbors ω. The cells with different co-boundary sizes |C(θ)| must have different colors. Therefore, we can partition these multisets by the boundary size of θ, preserving the equality of the sub-multisets. Since θ is a face of σ, and each θ appears |C(θ)| − 1 times in the neighborhood, we group by boundary degree n and obtain: nn oo nn oo (t+1) (t+1) (t+1) (t+1) (t+1) (t+1) bθσ | (·, bθσ ) ∈ bN↓ (σ), |C(θσ )| = n = bθ τ | (·, bθτ ) ∈ bN↓ (τ ), |C(θτ )| = n .

(22)

Thus, we can recover the true multiplicity-free multiset of boundary cell colors by grouping and deduplicating. That is: nn

(t+1)

which means: bB (t+2)

(t+1)

(σ) = bB

(t+1)

bθ

oo nn oo (t+1) | θ ∈ B(σ) = bθ | θ ∈ B(τ ) , (t)

(23)

(t)

(τ ). Therefore, we can reconstruct cB (σ) from cN↓ (σ), and the same holds for τ . If

(t+2)

(t+1)

bσ = bτ , then the input sets to the full rule at iteration t + 1 are equal. Hence: aσ = aτ , and we conclude that:b(t+1) ⊑ a(t+1) , completing the inductive step. Therefore, by induction on t, we have at ≡ bt for all t, and both schemes are equally expressive. Proof for Lemma 4.9. Let CC 1 and CC 2 be two combinatorial complexes. Let c denote the stable coloring produced by a WL-style test (e.g., a restricted version operating only on 0-cells or using fewer aggregation rules), and let d denote the stable coloring produced by CCWL. Since CCWL aggregates over more structural information. Specifically, it considers both lower neighbourhoods N↓ , upper neighbourhoods N↑ , boundary and coface relations, its coloring d distinguishes more cells than c. Therefore, the partition induced by c is coarser than that induced by d, i.e., c ⊑ d. Suppose that the WL test distinguishes CC 1 and CC 2 . That is, cCC 1 ̸= cCC 2 , which means the multiset of colors differs between the two complexes. By Corollary 4.6, since c ⊑ d, we have: If cCC 1 ̸= cCC 2 , then dCC 1 ̸= dCC 2 . Therefore, CCWL also distinguishes CC 1 and CC 2 . This holds for any pair distinguishable by the WL test. Hence, CCWL is at least as powerful as the WL test in distinguishing non-isomorphic combinatorial complexes.

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Remark Co-boundary relations are encoded in upper neighborhood. Let CC be a combinatorial complex with a rank-aware coloring function c(t) : C → A at iteration t. For any cell σ ∈ C, denote by C(σ) = {δ ∈ C : δ ≻ σ} and N↑ (σ) = {τ ∈ (t) C : ∃ δ ∈ C(σ) with τ ≺ δ}. The coboundary color multiset of σ is defined as cC (σ) = {{ c(t) (δ) : δ ∈ C(σ) }}, and the (t) upper neighborhood color multiset as cN↑ (σ) = {{ (c(t) (τ ), c(t) (δ)) : τ ∈ N↑ (σ), δ ∈ C(σ), τ ≺ δ }}. Then the upper (t)

(t)

neighborhood multiset refines the coboundary multiset in the sense of multiset projection:cC (σ) ⊑ cN↑ (σ), there exists a (t) (t) (t) (t) surjective projection π : cN↑ (σ) → cC (σ) defined by π(cτ , cδ ) = cδ such that π cN↑ (σ) = cC (σ). For every δ ∈ C(σ), there exists at least one τ ∈ δ \ {σ} satisfying τ ≺ δ and τ ∈ N↑ (σ) by the local incidence property of the complex. Hence (t) (t) (c(t) (τ ), c(t) (δ)) ∈ cN↑ (σ) and π((cτ , cδ )) = cδ . Therefore π is surjective, implying that cC (σ) can be recovered from (t)

cN↑ (σ) by projection, which establishes the refinement relation. Remark Boundary relations are encoded in the lower neighborhood. Let CC be a combinatorial complex with a rankaware coloring c(t) : C → A at iteration t. For σ ∈ C set B(σ) = {δ ∈ C : δ ≺ σ}. Define the boundary color (t) (t) multiset cB (σ) = {{ c(t) (δ) : δ ∈ B(σ) }}. Define the extended lower neighborhood color multiset by cNe (σ) = ·,↓

{{ (c(t) (τ ), c(t) (δ)) : δ ∈ B(σ), τ ∈ C, δ ≺ τ }}, i.e., pairs of a co-incident same-rank cell τ and a boundary face (t) (t) (t) (t) δ, allowing τ = σ. Then cNe (σ) refines cB (σ) in the multiset-projection sense: cB (σ) ⊑ cNe (σ), namely, the ·,↓ ·,↓ (t) (t) projection π(cτ , cδ ) = cδ is surjective and satisfies π cNe (σ) = cB (σ). For every δ ∈ B(σ) we have δ ≺ σ, hence ·,↓

(t)

(c(t) (σ), c(t) (δ)) ∈ cNe (σ). Thus the projection π(cτ , cδ ) = cδ hits c(t) (δ) for each boundary face δ. ·,↓

B.2. Lifting Mapping A combinatorial complex lifting map is a function f : G → CC from the space of graphs G to the space of regular combinatorial complexes CC with the property that two graphs G1 , G2 are isomorphic iff the combinatorial complexes f (G1 ), f (G2 ) are isomorphic. To prove the Theorem 4.11, we provide the propositions as follows: Proposition B.5. Let f : G → CC be a lifting function from graph to combinatorial complexes. Then there exists a lifting f such that CCWL over f (G) is strictly more powerful than the classical Weisfeiler-Lehman (1-WL) test on graphs.

�1

�2

Input Graph

Neighbors Aggregation

�1

�� : � 1 , � 2 , � 3 , � 5

�3

�4

�5

�� : � 2 , � 1 , � 3 , � 6 �� : � 3 , � 1 , � 2 , � 4 �� : � 4 , � 3 , � 5 , � 6

�6

�� : � 5 , � 1 , � 2 , � 3 �� : � 6 , � 2 , � 4 , � 5

Update Embeddings Labels

�� : �� : �� : �� : �� : �� :

, , , , , ,

, , , , ,

�1

, ,

�2

�3

�4

, ,

�2

Neighbors Aggregation

Input Graph

�5 �6

�� : �1 , �2 , �3 , �5 �� : �2 , �1 , �4 , �6 �� : �3 , �1 , �3 , �6 �� : �4 , �2 , �3 , �5 �� : �5 , �1 , �4 , �6 �� : �6 , �2 , �3 , �5

Update Embeddings Labels

�� :

�� : �� : �� : �� :

, , , ,

Figure B.1. Two non-isomorphic graphs, 1-WL and hypergraph-WL cannot distinguish them.

Proof. Let G = (V, E) be a finite simple graph. We define a lifting f : G → CC by mapping G to a combinatorial complex X = f (G) as follows. Each node v ∈ V is represented by a 0-cell v 0 . Each edge e = (u, v) ∈ E corresponds to a 1-cell e1 with boundary ∂e1 = {u0 , v 0 }. For every edge e ∈ E, we attach a 2-cell Pe2 (a parity gadget) whose boundary forms a cycle of 1-cells containing e1 and a set of auxiliary 1-cells introduced solely for this construction. The internal structure of Pe2 is chosen from two non-isomorphic configurations, selected according to a global parity bit in the style of the Cai-Fürer-Immerman (CFI) construction. While the parity is fixed uniformly across all edges within a single graph, distinct graphs may adopt different parity assignments. This lifting is faithful: for any pair of graphs G1 and G2 , we have G1 ∼ = G2 if and only if f (G1 ) ∼ = f (G2 ). To compare the expressive power of CCWL on {f (G)} and the classical 1-WL test on G, observe that CCWL subsumes 1-WL. Specifically, the color update for a 0-cell v 0 in X = f (G) aggregates over the multiset of colors of incident 1-cells {e1 | v 0 ∈ ∂e1 }, each of which corresponds bijectively to an edge (v, u) ∈ E. Since the adjacent 0-cells of these 1-cells are the neighbors of v in G, the resulting aggregation encodes the same neighborhood multiset that governs the 1-WL 23

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

refinement at v. Consequently, the sequence of color partitions produced by 1-WL on G is recoverable from the restriction of CCWL’s coloring to the 0-skeleton of f (G). Thus, CCWL is at least as expressive as 1-WL. To establish strict separation, consider a pair of non-isomorphic Cai-Fürer-Immerman (CFI) graphs (G1 , G2 ) that are indistinguishable by 1-WL; their color refinement sequences and the resulting color multisets that coincide at every iteration. We instantiate the lifting f by assigning one parity configuration to all gadgets {Pe2 } in f (G1 ), and the opposite (non-isomorphic) configuration to those in f (G2 ), as prescribed by the CFI construction. Although G1 and G2 are 1-WL-equivalent, the resulting complexes f (G1 ) and f (G2 ) differ in the combinatorial structure of their 2-cells and associated coboundaries. For certain 1-cells e1 , the multiset of cofaces i.e., the 2-cells incident to e1 , which differs between the two lifted complexes due to the global parity constraint. Because CCWL incorporates coboundary information during refinement, the affected 1-cells acquire distinct colors, and this distinction may further influence neighboring 0-cells. Then the final color multisets over f (G1 ) and f (G2 ) diverge. Hence, while 1-WL cannot distinguish G1 from G2 , CCWL distinguishes f (G1 ) from f (G2 ). This demonstrates the existence of a lifting f for which CCWL on f (G) is strictly more expressive than 1-WL on G.

Proposition B.6. There exists a lifting f : H → CC from hypergraphs to combinatorial complexes such that CCWL applied to f (H) is strictly more expressive than the hypergraph Weisfeiler-Lehman (HWL) test. Case 5 (1-WL ≺ CCWL) Figure B.1 shows the 1-WL and Hypergraph WL tests fail to distinguish the two non-isomorphic regular graphs: their iterative color refinement procedures, which operating solely on nodes and (hyper)edges yields identical stable colorings. In contrast, when these graphs are lifted to combinatorial complexes CC 1 and CC 2 via the lifting mapping function, the CCWL test successfully distinguishes them. Specifically, Figure B.2 displays the variant of CCWL that aggre (t) (t) gates over lower and upper neighbors, i.e., HASH c(t) (σ), cN↓ (σ), cN↑ (σ) , which is already sufficient to separate CC 1 and CC 2 . This demonstrates that even a restricted form of CCWL, which omits explicit boundary ( B ) and coboundary ( C ) aggre (t) (t) (t) (t) gation, attains the full distinguishing power of the general update rule HASH c(t) (σ), cB (σ), cC (σ), cN↓ (σ), cN↑ (σ) , on this class of instances. The success of the lifting-based approach thus highlights its ability to resolve structural ambiguities that are inherently invisible to classical WL tests operating on flat graph or hypergraph representations. Proposition B.7. There exists a lifting f : S → CC from simplicial complexes to combinatorial complexes such that CCWL applied to f (S) is strictly more expressive than the Simplicial Weisfeiler-Lehman (SWL) test. Case 5 (SWL ≺ CCWL) Figure B.3 example (a) considers two 1-dimensional simplicial complexes S1 and S2 . The 1-skeleton of S1 is the cycle graph C8 , while S2 consists of two disjoint 4-cycles, i.e., C4 ⊔ C4 . Both complexes have eight nodes and eight edges, and without any 2-simplices. For every 1-simplex, the co-boundary (upper) neighborhood is empty. SWL updates colors by aggregating information from boundary and co-boundary neighborhoods. In the case of no 2-simplices are present here, SWL refinement coincides with the standard 1-WL refinement. we find that both S1 and S2 are 2-regular, each node is incident to exactly two edges, and each edge is bounded by two distinct nodes. At the initialization, all nodes in both complexes are the same multisets of neighboring colors, two identical colors coming from their incident edges. Similarly, every edge observes the same colors. The process stabilizes with one node color and one edge color for both S1 and S2 . Hence, the stable colorings produced by SWL are the same on the S1 and S2 , and SWL cannot distinguish them:SWL(S1 ) ≡ SWL(S2 ). CCWL introduces higher-dimensional structures (faces), and the refinement process divides nodes or edges into multiple color categories, enabling the differentiation between two structures in Figure B.4. Case 5 (SWL ≺ CCWL) Figure B.3 example (b) also considers two 1-dimensional simplicial complexes S1 and S2 . S1 repents C6 ∪ C6 : two 6-cycles glued along an edge(e16 ), and S2 denotes C5 ∪ C5 : two 5-cycles connected by a bridge edge(e16 ). Specifically, nodes aggregate colors from their incident edges, while edges aggregate colors from their two endpoint nodes, since no 2-simplices are present, the upper neighborhoods of all edges are empty. When restricted to 1-dimensional simplicial complexes, SWL test degenerates to the classical 1-dimensional Weisfeiler-Lehman (1-WL) color refinement on graphs. With a uniform initialization, all nodes and all edges share the same color, the first refinement round reveals only degree information. In both graphs considered here, exactly two nodes have degree three and the remaining eight nodes have degree two, leading to an identical partition of nodes into degree-3 and degree-2 color classes. In subsequent iterations, each degree-3 node has an identical local neighborhood structure, consisting of two degree-2 neighbors and one degree-3 neighbor, and the neighborhoods of all degree-2 nodes are likewise locally indistinguishable as color information propagates along the cycle structures. The process stabilizes after the second iteration, producing identical node and edge color distributions for both graphs, and the SWL test fails to distinguish two simplicial complexes. If we lift two simplicial complexes to combinatorial complexes f (S1 ), f (S2 ), as Figure B.5 shows CCWL can distinguish them. 24

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks Combinatorial Complex �(�� )

�1

�13 �2 �3

�1

�12

�15

�34

�23 �3

�2

�4

�45

�4

�46

�26

�13

�3

�1

�12

�4

�24

�15

�34

�2

�45 �36

�26

�2

�3

�� : �13 , �1 , �3 , �12 , �23 , �15 , �34 , �1 , �2

�� : �45 , �4 , �5 , �34 , �15 , �46 , �56 , �2 , �4

�� : �56 , �5 , �6 , �15 , �26 , �45 , �46 , �4

�� : �26 , �2 , �6 , �12 , �23 , �46 , �56 , �3

�� : �46 , �4 , �6 , �34 , �26 , �45 , �56 , �3 , �4 �� : �2 , �13 , �15 , �34 , �45 , �1 , �4

�� : �23 , �2 , �3 , �12 , �13 , �26 , �34 , �1 , �3 �� : �34 , �3 , �4 , �13 , �23 , �45 , �46 , �2 , �3 �� : �1 , �12 , �13 , �23 , �2 , �3

�� : �1 , �2 , �3 , �5 , �12 , �13 , �15

�� : �2 , �1 , �4 , �6 , �12 , �24 , �26

�� : �4 , �2 , �3 , �5 , �24 , �34 , �45

�� : �12 , �1 , �2 , �13 , �24 , �15 , �26 , �1

�56

�� : �6 , �2 , �3 , �5 , �26 , �36 , �56

�� : �13 , �1 , �3 , �12 , �15 , �34 , �36 , �1 , �2

�� : �15 , �1 , �5 , �12 , �13 , �45 , �56 , �2

�� : �24 , �2 , �6 , �12 , �13 , �26 , �34 , �1 , �3

�� : �46 , �4 , �6 , �13 , �34 , �26 , �56 , �2

�� : �45 , �4 , �5 , �15 , �24 , �45 , �56 , �3

�� : �26 , �2 , �6 , �12 , �24 , �36 , �56 , �3

�6

�� : �3 , �1 , �4 , �6 , �13 , �34 , �36

�� : �5 , �1 , �4 , �6 , �15 , �45 , �56

�� : �34 , �3 , �4 , �13 , �24 , �45 , �36 , �1

�� : �56 , �5 , �6 , �15 , �26 , �45 , �36 , �2 , �3 �� : �2 , �13 , �15 , �36 , �56 , �1 , �3

�� : �1 , �12 , �13 , �24 , �34 , �2 , �3

�� : �3 , �24 , �26 , �45 , �56 , �1 , �2

(b) Combinatorial Complex Weisfeiler–Lehman Test on Lifting Graph �(�� )

�12 , �15 , �26 , �56 :

�13 , �23 , �34 , �45 , �46 : �1 , �4 :

�2 , �3 :

, ,

, , ,

, ,

Update

�3 , �4 :

�12 , �56 :

, ,

�13 , �45 , �46 : �23 , �34 : �2 , �3 :

�15 , �26 :

�1 , �4 : ,

Second iteration of CCWL

�1 , �2 , �5 , �6 :

�12 , �15 , �26 , �36 , �34 , �45 , : �1 , �2 , �3 :

�1 , �2 , �3 , �4 , �5 , �6 : �13 , �24 , �56 :

�� : �2 , �45 , �46 , �56 , �2 , �3

�� : �3 , �23 , �26 , �34 , �46 , �1 , �4

(a) Combinatorial Complex Weisfeiler–Lehman Test on Lifting Graph �(�� )

�1 , �2 , �3 , �4 , �5 , �6 :

�(�2 )

�� : �6 , �2 , �4 , �5 , �26 , �46 , �56

�� : �12 , �1 , �2 , �13 , �23 , �15 , �26 , �1

First iteration of CCWL

�(�1 )

�� : �3 , �1 , �2 , �4 , �13 , �23 , �34

�� : �5 , �1 , �2 , �3 , �15 , �45 , �56

�� : �15 , �1 , �5 , �12 , �13 , �45 , �56 , �2

�6

�5

�� : �2 , �1 , �3 , �6 , �12 , �23 , �26

�� : �4 , �3 , �5 , �6 , �34 , �45 , �46

�56

Combinatorial Complex �(�� )

�1

�� : �1 , �2 , �3 , �5 , �12 , �13 , �15

�5

, ,

, , ,

�1 , �2 , �3 , �4 , �5 , �6 :

, ,

�12 , �15 , �26 , �36 , �34 , �45 , :

�13 , �56 : �24 :

�1 , �2 , �3 :

, , ,

, ,

, , ,

, ,

（c）Update Label of Combinatorial Complex Weisfeiler–Lehman Test on Lifting Graph

Figure B.2. Combinatorial complex Weisfeiler-Lehman can distinguish the lifting combinatorial complexes f (G1 ), f (G2 ). Example (a)

�2

�3

�1

�4

�8

�5

Cycle Graph ��

�7 �6

�1

�4 �5

�8

�2

�3 �6

�7

�5 �4

�3

�6 �1

�7

�2 �10 Cycle Graph �� ∪ ��

Cycle Graph �� ∪ ��

Example (b)

�8 �9

�4

�3

�5

�2

�1

�6

�7

�10

�8 �9

Cycle Graph �� ∪ ��

Figure B.3. Regular simplicial complexes are non-isomorphic (Simplicial Weisfeiler-Lehman cannot distinguish them). Example (a) C8 : the cycle graph on 8 nodes, C4 ∪ C4 : the disjoint union of two 4-cycle graphs. Example (b) C6 ∪ C6 : two 6-cycles glued along an edge(e16 ), C5 ∪ C5 : two 5-cycles connected by a bridge edge(e16 ). Note: The boundary of a hollow quadrilateral is a 1-dimensional simple complex, while a solid quadrilateral (as a 2-dimensional region) cannot be directly treated as a simplex; it can be transformed into a 2-dimensional simple complex through triangulation.

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

�12

�1

�23 �34

�1

�2

�1

�4

�18

�8

�1

�78

�45

�23

�4

�56

�5

�2

�56 �34

�3

�6

�58

�(�2 )

�6

�� : �6 , �5 , �7 , �56 , �67

�� : �3 , �2 , �4 , �23 , �34

�� : �7 , �6 , �8 , �67 , �68

�� : �12 , �1 , �2 , �18 , �23 , �1

�� : �23 , �2 , �3 , �12 , �34 , �1

�� : �78 , �7 , �8 , �67 , �18 , �1

�� : �18 , �· , �8 , �12 , �78 , �1

�� : �56 , �5 , �6 , �45 , �67 , �1

�� : �45 , �4 , �5 , �34 , �56 , �1

�� : �4 , �3 , �5 , �34 , �45 �� : �8 , �1 , �7 , �18 , �78

�� : �34 , �3 , �4 , �23 , �45 , �1

�� : �67 , �6 , �7 , �56 , �78 , �1

�� : �1 , �12 , �23 , �34 , �45 , �56 , �67 , �78 , �18

（b）Combinatorial Complex Weisfeiler–Lehman Test on Lifting Simplicial Complexes �(�2 )

�� : �1 , �2 , �4 , �12 , �14

�� : �2 , �1 , �3 , �12 , �23

�� : �5 , �4 , �6 , �45 , �56

�78

�� : �6 , �5 , �7 , �56 , �67

�� : �14 , �4 , �1 , �12 , �34 , �1 �� : �78 , �7 , �8 , �67 , �58 , �2 �� : �1 , �12 , �23 , �34 , �14

�� : �3 , �2 , �4 , �23 , �34 �� : �7 , �6 , �8 , �67 , �68

�� : �23 , �2 , �3 , �12 , �34 , �1

�� : �12 , �1 , �2 , �14 , �23 , �1

�7

�67

�� : �2 , �1 , �3 , �12 , �23

�� : �5 , �4 , �6 , �45 , �56

�8

Cycle Graph �� ∪ ��

�(�1 )

�� : �1 , �2 , �8 , �12 , �18

�7

�67

Cycle Graph ��

�14

（a）Combinatorial Complex Weisfeiler–Lehman Test on Lifting Simplicial Complexes �(�1 )

�� : �56 , �5 , �6 , �45 , �67 , �2

�� : �58 , �5 , �8 , �56 , �78 , �2

�� : �4 , �3 , �1 , �34 , �14 �� : �8 , �5 , �7 , �58 , �78

�� : �34 , �3 , �4 , �23 , �14 , �1

�� : �67 , �6 , �7 , �56 , �78 , �2

�� : �2 , �56 , �67 , �78 , �58

（c）Update Label of Combinatorial Complex Weisfeiler–Lehman Test on Lifting Simplicial Complexes �� , �� , �� , �� , �� , �� , �� , �� : , , , , �� , �� , �� , �� , �� , �� , �� , �� : �� :

�� , �� , �� , �� , �� , �� , �� , �� :

�� , �� , �� , �� , �� , �� , �� , �� : �� , �� :

��(�(�� )) ≠ ��(�(�� ))

Lifting simple complexes �(�1 ), �(�2 ) are non-isomorphic

Figure B.4. Two simplicial complexes (C8 : the cycle graph on 8 nodes, C4 ∪ C4 : the disjoint union of two 4-cycle graphs.) are non-isomorphic. Simplicial Weisfeiler-Lehman cannot distinguish them, but Combinatorial complex Weisfeiler-Lehman can distinguish the lifting combinatorial complexes f (S1 ), f (S2 ).

Proposition B.8. There exists a lifting f : C → CC from cellular complexes to combinatorial complexes such that CCWL applied to f (C) is strictly more expressive than the Cellular Weisfeiler-Lehman (CWL) test. Proof. Similar to the proof of Proposition B.5, we can also prove Proposition B.6, Proposition B.7 and Proposition B.8. Case 5 (CWL ≺ CCWL) Cellular WL operates on a quotient representation of a cellular complex, in which lowerdimensional cells and the types of incidence relations are collapsed into an untyped adjacency graph, boundary multiplicities and rank-specific interactions are irreversibly lost prior to refinement. There exist two 2-dimensional combinatorial complexes CC 1 and CC 2 . they share the same nodes set as V = {v1 , v2 , v3 , v4 , v5 , v6 }. we consider the common edges set as e12 , e13 , e23 , e14 , e15 , e45 , e26 , e36 , e46 , e56 , here each node with four connections,and each edge appears in two 2-cells. Given two combinatorial complexes have 4 triangular 2-cells as • CC 1 = f1 = {v1 , v2 , v3 }, f2 = {v1 , v4 , v5 }, f3 = {v2 , v3 , v6 }, f4 = {v4 , v5 , v6 } , here f1 ∩ f2 = {v1 }, f1 ∩ f3 = {v2 , v3 },f1 ∩ f2 = ∅,f2 ∩ f3 = ∅, f2 ∩ f4 = {v4 , v5 }, f3 ∩ f4 = {v6 }, • CC 1 = g1 = {v1 , v2 , v3 }, g2 = {v1 , v4 , v5 }, g3 = {v2 , v4 , v6 }, g4 = {v3 , v5 , v6 } , here g1 ∩ g2 = {v1 }, g1 ∩ g3 = {v2 ]},g1 ∩ g4 = {v3 },g2 ∩ g3 = {v4 }, g2 ∩ g4 = {v5 }, g3 ∩ g4 = {v6 }, (0)

(0)

According to the CWL test, we suppose the initial colors: all 0-cells c0 = {•}, all 1-cells c1 = {•} and c2 = {•}. CWL updates colors with the rules 1-cells aggregate upper neighbors (incident 2-cells), and 2-cells aggregate lower neighbors (boundary 1-cells). Because of every edge appears in exactly two 2-cells in CC 1 and CC 2 , all edges receive the same updated (1) (1) color as c1 = HASH(•, {•, •}) and each 2-cell aggregates three boundary edges, c2 = HASH(•, {•, •, •}). Followed (t) (t) with CWL update rules, all 2-cells get identical colors c2 (CC 1 ) = c2 (CC 2 ) at any iteration t, and fails to distinguish them. 26

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

�5

�4 �3

�2

（a）Combinatorial Complex Weisfeiler–Lehman Test on Lifting Simplicial Complexes �(�1 )

�6

�3

�� : �7 , �6 , �8 , �67 , �68

�� : �10 , �1 , �10 , �1,10 , �9,10

�� : �23 , �2 , �3 , �12 , �34 , �1

�� : �45 , �4 , �5 , �34 , �56 , �1

�� : �56 , �5 , �6 , �16 , �45 , �67 , �1

�� : �78 , �7 , �8 , �67 , �18 , �2

��,�� : �1,10 , �1 , �10 , �12 , �16 , �9,10 , �2 �� : �1 , �12 , �23 , �34 , �45 , �56 , �16 , �2

�� : �89 , �8 , �9 , �78 , �9,10 , �2

�� : �4 , �3 , �5 , �34 , �45

�� : �8 , �1 , �7 , �18 , �78

�� : �34 , �3 , �4 , �23 , �45 , �1

�� : �67 , �6 , �7 , �16 , �56 , �78 , �2

��,�� : �9,10 , �9 , �10 , �89 , �1,10 , �2

�� : �16 , �1 , �6 , �12 , �1,10 , �56 , �67 , �1 ，�2

�� : �2 , �67 , �78 , �89 , �9,10 , �1,10 , �16 , �1

（b）Combinatorial Complex Weisfeiler–Lehman Test on Lifting Simplicial Complexes �(�2 ) �� : �1 , �2 , �5 , �6 , �12 , �16 , �56 �� : �2 , �1 , �3 , �12 , �23 �� : �3 , �2 , �4 , �23 , �34 �� : �4 , �3 , �5 , �34 , �45

�7

�� : �5 , �4 , �6 , �45 , �56

�8 �� : �9 , �8 , �10 , �89 , �9,10

�6

�� : �6 , �1 , �5 , �10 , �16 , �67 , �6,10 �� : �10 , �6 , �10 , �6,10 , �9,10

�� : �12 , �1 , �2 , �16 , �15 , �23 , �1

�� : �7 , �6 , �8 , �67 , �68

�� : �23 , �2 , �3 , �12 , �34 , �1

�� : �45 , �4 , �5 , �34 , �15 , �1

�� : �56 , �5 , �6 , �16 , �45 , �67 , �1

�� : �1 , �12 , �23 , �34 , �45 , �56

�� : �2 , �67 , �78 , �89 , �9,10 , �6,10

�9 � : � , � , � , � , � , � �� 78 7 8 67 89 2

�� : �16 , �1 , �6 , �12 , �15 , �67 , �6,10

�10

Cycle Graph �� ∪ ��

�� : �3 , �2 , �4 , �23 , �34

�� : �6 , �1 , �5 , �7 , �16 , �56 , �57

�� : �12 , �1 , �2 , �16 , �1,10 , �23 , �1

�10

Cycle Graph �� ∪ ��

�1

�2

�� : �9 , �8 , �10 , �89 , �9,10

�8

�5 �4

�� : �5 , �4 , �6 , �45 , �56

�9

�1

�� : �2 , �1 , �3 , �12 , �23

�� : �1 , �2 , �6 , �7 , �12 , �16 , �1,10

�7

�� : �89 , �8 , �9 , �78 , �9,10 , �2

�� : �8 , �1 , �7 , �18 , �78

�� : �34 , �3 , �4 , �23 , �45 , �1

�� : �67 , �6 , �7 , �16 , �6,10 , �78 , �2 ��,�� : �9,10 , �9 , �10 , �89 , �6,10 , �2

��,�� : �6,10 , �6 , �10 , �16 , �67 , �9,10 , �2

（c）Update Label of Combinatorial Complex Weisfeiler–Lehman Test on Lifting Simplicial Complexes �� , �� :

�(�1 )

�� , ��,�� , �� , �� :

�� , �� , �� , �� , �� , ��,�� : �� :

�� , �� :

�� , �� : �(�2 )

�� , �� , �� , �� , �� , �� , �� , �� : ,

�� , �� , �� , �� , �� , �� , �� , �� : �� , �� , �� , ��,�� : �� :

�� , �� , �� , �� , �� , ��,�� :

�� , �� :

, ,

��(�(�� )) ≠ ��(�(�� ))

Lifting simple complexes �(�1 ), �(�2 ) are non-isomorphic

, ,

Figure B.5. Two simplicial complexes are non-isomorphic (C6 ∪ C6 : two 6-cycles glued along an edge(e16 ), C5 ∪ C5 : two 5-cycles connected by a bridge edge(e16 )). Simplicial Weisfeiler-Lehman cannot distinguish them, but Combinatorial complex Weisfeiler-Lehman can distinguish the lifting combinatorial complexes f (S1 ), f (S2 ).

In contrast, CCWL operates directly on the full incidence structure of the combinatorial complex, allowing higherdimensional cells to exchange messages based on arbitrary non-empty intersections, regardless of the underlying skeleton. (0) (0) (0) we also suppose the initial colors: all 0-cells c0 = {•}, all 1-cells c1 = {•} and c2 = {•}. At iteration t = 1, each 2-cell σ updates its color by aggregating information from all other 2-cells τ ̸= σ(σ ∩ τ ̸= ∅). Importantly, CCWL preserves the size of the intersection σ ∩ τ as part of the message as (1) c2 (σ) = HASH •, (|σ ∩ τ |, •)|τ ∈ CC, τ ̸= σ, σ ̸= τ ̸= ∅ (24) In the combinatorial complexes CC 1 , the 2-cell f1 intersects f2 with node v1 , f2 with edges v2 , v3 , f4 with ∅, then its (1) neighbor multiset is c2 (f1 ) = •, {•, •}, {•, •}, {•} , but the combinatorial complexes CC 2 , the 2-cell f1 intersects (1) f2 with node v1 , f2 with edges v2 , f4 with v3 , then its neighbor multiset is c2 (g1 ) = •, {•, •}, {•, •}, {•, •} . From (t) (t) the multisets, we obtain c2 (CC 1 ) ̸= c2 (CC 2 ). Hence, CCWL can distinguish CC 1 and CC 2 at the first iteration. Proof for Theorem 4.11. Let G, H, S, and C denote the classes of graphs, hypergraphs, simplicial complexes, and cellular complexes, respectively. We prove this theorem by combining the Propositions B.5, Propositions B.6, Propositions B.7 and Propositions B.8. There exist faithful liftings from each of these structures into combinatorial complexes CC such that the Combinatorial Complex Weisfeiler Lehman test simulates the corresponding classical WL tests, namely, 1-WL, Hypergraph WL, Simplicial WL and Cellular WL, which is strictly more expressive in each case. For each discrete structure, we define a faithful lifting map f into the category of combinatorial complexes CC: For graphs G, Proposition B.5 constructs fG : G → CC preserving incidence via 0- and 1-cells, showing that CCWL on fG (G) simulates 27

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

1-WL by matching node neighbourhood aggregation through 0-cell updates. For hypergraphs H, Proposition B.6 constructs fH : H → CC preserving incidence via 0- and 1-cells, showing that CCWL on fH (H) simulates 1-WL by matching node neighbourhood aggregation through 0-cell updates. For simplicial complexes K, Proposition B.7 gives fK : K → CC that preserves simplex-cell correspondence and face incidences. The CCWL update rules on k-cells directly simulate the lower and upper coface aggregation of SWL. Proposition B.8. For cellular complexes C, the construction in the previous proposition defines fC : C → CC preserving all boundary maps. Since CWL refines cells based on boundary and coboundary multisets, and CCWL aggregates over exactly these incidence relations, the simulation follows immediately. For hypergraphs H, a similar lifting fH : H → CC can be defined: map each node to a 0-cell, each hyperedge of size k + 1 to a k-cell with boundary consisting of the corresponding 0-cells. Standard results show that this embedding allows CCWL to simulate Hypergraph WL (which refines nodes based on hyperedge memberships and vice versa) via appropriate aggregation over 0-cells and their incident higher-cells. In all cases, the lifting f is faithful (A ∼ = B ⇐⇒ f (A) ∼ = f (B)), and the local aggregation rules of CCWL generalize those of the respective WL variants when restricted to the base cell types. Each classical WL test is limited by its local update rule. The 1-WL test cannot distinguish non-isomorphic regular graphs with identical local neighborhoods—most famously, Cai-Fürer-Immerman (CFI) graph pairs. Similarly, Hypergraph WL fails on high-uniformity hypergraphs where symmetries persist across all local refinements. For simplicial and cellular complexes, SWL and CWL are blind to global topological invariants: they treat as equivalent any two structures that share the same local incidence patterns but differ in global parity or higher-order connectivity, as demonstrated by CFI-style constructions lifted to these domains. The liftings described above circumvent these limitations by embedding each structure into a combinatorial complex enriched with CFI-style gadgets. Specifically, we attach (k+1)-cells—such as twisted or suspended configurations—whose internal combinatorial structure encodes a global invariant like total parity. Crucially, these gadgets do not modify the original object’s local neighborhood structure; hence, classical WL tests remain oblivious to them. In the lifted complex, however, the coface multisets of certain k-cells differ between non-isomorphic instances. Since CCWL aggregates over both boundary and coboundary relations, it detects these discrepancies and assigns distinct colors during refinement. Consequently, for each domain there exists a pair (A, B) such that A ̸∼ = B, the corresponding classical WL test fails to distinguish A and B, yet CCWL distinguishes f (A) and f (B). This establishes that, under appropriate liftings, CCWL is strictly more expressive than 1-WL, Hypergraph WL, SWL, and CWL. Corollary B.9. The Combinatorial Complex Weisfeiler-Lehman (CCWL) test is strictly more expressive than Graph-WL(1WL), Hypergraph-WL(HWL), Simplicial WL (SWL), and Cellular WL (CWL). That is, 1-WL ≺ CCWL,

HWL ≺ CCWL,

SWL ≺ CCWL,

CWL ≺ CCWL.

Consequently, there exist pairs of non-isomorphic structures indistinguishable by each classical test but distinguished by CCWL under an appropriate faithful lifting into combinatorial complexes. Proof. Building on Proposition B.5, Proposition B.6, Proposition B.7 and Proposition B.8, this Corollary holds.

C. Building Powerful Combinatorial Complex Neural Networks. C.1. Bridge between CCWL test and CCNNs Building Powerful Combinatorial Complex Isomorphic Networks. The expressive capacity of Combinatorial Complex Neural Networks (CCNNs) can be characterized through a generalized Weisfeiler-Lehman (WL) refinement process defined over combinatorial complexes. Let N = {B, C, N↑ , N↓ } be a set of neighborhood functions defined on CC. Then we propose Combinatorial Complex Isomorphic Networks(CCIN) At each iteration, the color of a cell σ is updated based on its current state and the colors of its neighbors across all neighborhood types: [ c(t+1) (σ) = HASH(c(t) (σ), {(N , {{c(t) (τ ) : τ ∈ N (σ)}})}), (25) N

where {{·}} denotes a multiset, and N represents a labeled union across distinct neighborhood types. This iterative refinement continues until color stabilization, as defined in Condition 4.9. Two combinatorial complexes CC 1 and CC 2 are considered non-isomorphic if there exists an iteration t such that nn oo nn oo c(t) (σ) : σ ∈ CC 1 ̸= c(t) (σ) : σ ∈ CC 2 . (26) 28

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

The continuous formulation of CCNNs can be viewed as a differentiable fuction T of this discrete refinement scheme. Specifically, we replace the injective hash operation with learnable, and permutation-invariant transformations, as follows: ! M (t+1) (t) (t) h (σ) = ϕ h (σ), h (τ ) : τ ∈ N (σ) ) , (27) N

where and denote permutation-invariant aggregation and fusion operators, respectively, and ϕ, ψN are learnable, injective mappings ensuring the expressive equivalence to the underlying CCWL refinement. Therefore, Eq. (27) establishes a one-to-one correspondence between the discrete color refinement of CCWL and the continuous feature propagation in CCNNs, implying that the network attains at least the same discriminative power as the CCWL test. Based on the theoretical validity of the CCWL test, we can establish a neural network to learn the feature transfer of combinatorial complexes from the coloring problem in the WL test. This relabeling process is learned through a mapping function, where the input label of (t) (t) the cell is cσ , and the output feature is hσ . The following bridge is established between the CCWL test and CCIN: (t)

(t)

Lemma C.1. Suppose an injective function T : CC 1 → CC 2 , and let the labels cσ , and features of nn hσ o o node, nn edge and oo (k) (k) face in combinatorial complex CC at iteration t, respectively. If the conditions hold for k ≤ t, cCC 1 ,σ1 = cCC 2 ,σ2 , (k)

(k)

(t)

and k ≤ t − 1, hCC 1 ,σ1 = hCC 2 ,σ2 holds, it follows that hCC 1 ,σ1 = hCC 2 ,σ2 at iterations k . Proof. At iteration k = 0, all the initial colors are consistent, the condition holds. nn oo nn oo (k) (k) (k) (k) By induction, it follows that for all k ≤ t − 1, cCC 1 ,σ1 = cCC 2 ,σ2 , which implies hCC 1 ,σ1 = hCC 2 ,σ2 . At iteration t, nn oo nn oo (t) (t) it also holds that cCC 1 ,σ1 = cCC 2 ,σ2 , we can conclude: ((

!)) (t) cCC 1 ,σ1 ,

[

(t) {(N , {{cCC 1 ,τ : τ ∈ N (σ1 )}})}

((

!)) (t) cCC 2 ,σ2 ,

[

(t) {(N , {{cCC 2 ,τ : τ ∈ N (σ2 )}})}

(28)

By the inductive hypothesis and mapping function T is injective, we obtain: ((

!)) (t) hCC 1 ,σ1 ,

M (t) h (τ ) : τ ∈ N (σ1 )

(( =

!)) (t) hCC 2 ,σ2 ,

M (t) h (τ ) : τ ∈ N (σ2 )

(29)

(t)

resulting in the CCIN function’s aggregation function generates the same output hCC 1 ,σ1 = hCC 2 ,σ2 . Proposition C.2. Given two non-isomorphic combinatorial complexes CC 1 and CC 2 , if CCIN layer T can distinguish them by T (CC 1 ) ̸= T (CC 2 ), then 1-CCWL test also decides CC 1 ̸= CC 2 . Proof. Suppose there exists k ≥ 0 such that after k iterations, we have T (CC1 ) ̸= T (CC2 ) , Due to the features (k) (k) (k) (k) hCC = T (CC), hCC1 ̸= hCC2 , but the CCWL test cannot distinguish non-isomorphic CC1 and CC2 , i.e., cCC1 = cCC2 . (0)

(0)

We now prove this Proposition by induction. At the initiation k = 0 , then cCC1 = cCC2 implies the initial features (0) (0) hCC1 = hCC2 . This means that both the WL test and T start with the same labels and features, which contradicts our (k−1) (k−1) (k−1) (k−1) (k) (k) assumption. For k ≥ 0 , then cCC1 = cCC2 and hCC1 = hCC2 . Given that cH1 = cH2 , by Lemma C.1, we obtain (k) (k) (k) (k) (k) (k) cCC1 ,σ1 = cCC2 ,σ2 ,hCC1 ,σ1 = hCC2 ,σ2 , which implies there exists a mapping function R holds that R(cCC,σ ) → hCC,σ . (k) (k) Because cCC1 ,σ1 = cCC2 ,σ2 , we can obtain the condition

(k) cCC1 ,σ1

(k) hCC1 ,σ1

σ1 ∈CC 1

With the mapping function R, we can conclude that (k) (k) (k) hCC1 ,σ1 σ1 ∈CC 1 = R(cCC1 ,σ1 ) σ1 ∈CC 1 = R(cCC2 ,σ2 )

σ2 ∈CC 2

σ1 ∈CC 1

(k) cCC2 ,σ2

σ2 ∈CC 2

s.t.

(k) hCC2 ,σ2

σ2 ∈CC 2

(k) hCC2 ,σ2

σ2 ∈CC 2

However, this conclusion contradicts the assumption T (CC1 ) ̸= T (CC2 ), the proposition has been proved. 29

(30)

(31)

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks (k)

(k)

Proof of Theorem 5.1. Suppose there exists a injective mapping R(k) such that R(k) (cCC,σ ) → hCC,σ . For k = 0 , R(0) is (0) (0) the identity mapping in the case of cCC,σ and hCC,σ are the same. For k ≥ 0 , assuming the injective mapping R(k) exists, L (t+1) we show that it holds at iterations k + 1 based on Equation 27, hCC,σ = ϕ h(t) (σ), N h(t) (τ ) : τ ∈ N (σ) ) ,

L Since the composition of injective functions ϕ and N are the injective function, we can rewrite this as, (t) (t) (t) (t+1) (t) (t) hCC,σ = φ h(t) σ , hτ : τ ∈ N (σ) N (σ)∈N = φ R (cσ ), R (cτ ) : τ ∈ N (σ) N (σ)∈N (t) (k+1) (t+1) = R(t) c(t) cτ = R c σ , σ τ ∈N (σ)

(32)

(k+1) is also the injective function. By N , and R (k) (k) (k) (k) cCC,σ → hCC,σ . If at iterations k , cCC 1 ̸= cCC 2 , then

where φ is the injective function due to it can be induced with ϕ and

induction, there also exists a injective mapping R(k) such that R(k) nn oo nn oo (k) (k) (k) (k) cCC 1 ,σ1 ̸= cCC 2 ,σ2 . By the injectivity assumption, we can derive hCC 1 ̸= hCC 2 , then combine σ1 ∈CC 1

σ2 ∈CC 2

with Proposition C.2. CCIN is as powerful as CCWL when we employ an injective neighborhood aggregators.

C.2. Generalization of Combinatorial Complexes Message Passing To clarify the higher-order message passing on a CC, we discuss the combinatorial complexes message passing in this section. For a cell σ, we instantiate the above general rule into four specific message computations, corresponding to the neighborhood types, the embeddings from the four types are integrated as (t+1) (t+1) (t+1) (t+1) h(t+1) = Update h(t) , mC , mN↓ , mN↑ , σ σ , mB

(33)

where Update is a learnable fusion function, e.g., concatenation followed by a linear transformation (Multilayer Perceptron layer). In details, boundary message aggregates information from lower-dimensional constituents (e.g., edges of a face). The co-boundary message propagates from higher-dimensional cells enclosing σ. The lower adjacency message models lateral interactions through shared boundaries. The upper adjacency message captures relations through shared co-boundaries. We introduce the interpretation of isomorphic networks on four neighborhood functions. Let CC be a combinatorial complex, we consider the following general message-passing update rule for a cell σ ∈ CC of rank k = rk(σ) at layer l + 1: (l)

(l)

h(l+1) =ϕk ((1 + ϵk )h(l) σ σ +

(l)

γN ,k

N ∈NC

(l)

(l) ψN ,k (h(l) σ , hτ )),

(34)

τ ∈N (σ)

l+1

where h0σ = hσ represent the initial features, hl+1 ∈ RF , NC is a collection of neighborhood functions. The functions σ l l+1 ψN ,rk(·) : RF → RF and the update function ϕ are learnable functions, which are typically homogeneous across all neighborhoods and ranks. and ψN ,k (hσ , hτ ) = ηN ,τ · (WN ,k · [hσ ∥hτ ]). According to the Theorem 4.8, we further simplify these four neighborhood relations to upper and lower neighborhood functions, and obtain the following. Let C be a combinatorial complex equipped with a collection of neighborhood functions NC . We consider the following general message-passing update rule for a cell σ ∈ C of rank k = rk(σ) at layer l + 1: (l)

h(l+1) = ϕ(l) ((1 + ϵ(l) )h(l) v σ + γN↓

(l)

(l) ψN↓ (h(l) σ , hτ ) + γN↑

τ ∈N↓ (σ)

X τ ∈N↑ (σ)

(l)

(l) ψN↑ (h(l) σ , hτ )),

(35)

where ϵ(l) ∈ R and γN (·) ∈ R are learnable scalars, ψN (·) is a neighborhoodand rank-specific message MLP, (2) (1) ψN ,k (hσ , hτ ) = MLPN ,k [hσ ∥hτ ] , MLPN ,k (x) = WN ,k ReLU WN ,k x , and ϕrk(σ) is a shared rank-wise update. The update uses Summation, Max and Mean aggregation function, guaranteeing permutation invariance within each neighborhood and preserving asymmetries across ranks and relation types. By refining the neighborhood function NC appropriately, the ability of CCIN can generalize on graph, hypergraph, simplxical and cellular, which imply the same separation guarantees for these variants. Moreover, rank-aware parameter shared with aggregation function ψ and ϕ enables modeling of multi-rank interactions beyond standard GIN. Corollary C.3. CCIN layers are cell permutation equivariant. 30

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

D. Experiments D.1. Datasets Details Strongly Regular Graphs We benchmark it on a synthetic dataset consisting of nine families of strongly regular (SR) graphs (Bodnar et al., 2021a;b). Strongly regular graphs represent "hard" instances of graph isomorphism, as their pairs cannot be distinguished by the 3-WL test. Two graphs are considered isomorphic if the Euclidean distance between their representations is below a fixed threshold ϵ. Each graph is lifted to a d-dimensional complex whose size is (d + 1) the size of the largest clique in the family to which it belongs. Details of SR families are illustrated in Table D.1. Table D.1. Details of Strongly Regular Families Familty Graphs Number

(16,6,2,2) 2

(25,12,5,6) 15

(26,10,3,4) 10

(28,12,6,4) 4

(29,14,6,7) 41

(35,16,6,8) 3854

(35,18,9,9) 227

(36,14,4,6) 180

(40,12,2,4) 28

TUDataset TUDataset(Morris et al., 2020a) consists of bioinformatics and social networks. MUTAG (Kazius et al., 2005), PTC, PROTEINS(Borgwardt et al., 2005; Dobson & Doig, 2003) consist of graphs where nodes represent atoms and edges are chemical bonds. They are labeled according to biochemical properties. NCI1 and NCI109 (Wale et al., 2008) derived from the National Cancer Institute, these datasets contain chemical compounds screened for activity against various cancer cell lines. IMDB-B, IMDB-M, RDT-B and RDT-M are preprocessed movie collaboration and Reddit networks (Yanardag & Vishwanathan, 2015; Hu et al., 2020), where graphs represent interactions between actors or users, and the tasks involve classifying the network type or community structure. Peptides-func and Peptides-struct SATPdb (Dwivedi et al., 2022b; Singh et al., 2016) are derived from 15,535 peptides with a total of 2.3 million nodes. Both datasets use the same set of graphs but differ in their prediction tasks. These graphs are constructed in such a way that requires long-range interactions (LRI) reasoning to achieve strong performance in a given task. In concrete terms, they are larger graphs: on average 150.94 nodes per graph, and on average 56.99 graph diameter. Table D.2. Overview of the graph learning datasets. Dataset

Graphs Avg. nodes Avg. edges

Prediction task

Class

Metric

MUTAG PTC NCI1 NCI109 PROTEINS IMDB-B IMDB-M RDT-B RDT-M

188 344 4110 4127 1113 1000 1 500 2000 5000

17.93 25.56 29.87 29.68 39.06 19.77 13.0 429.6 508.5

19.79 25.96 32.30 32.13 72.82 96.53 65.9 497.8

Classification Classification Classification Classification Classification Classification Classification Classification Classification

2 2 2 2 2 2 3 2 5

Accuracy Accuracy Accuracy Accuracy Accuracy Accuracy Accuracy Accuracy Accuracy

ZINK-Small ZINC-FULL

12,000 249,456

23.2 23.2

24.9 49.8

Regression Regression

12 12

Mean Absolute Error Mean Absolute Error

OGBG-MOLHIV 41,127 OGBG-MOLBACE 1513 OGBG-MOLBBP 2,039 OGBG-MOLESOL 19,717 ogbg-moltox21 7,831 OGBG-MOLTOXCAST 8,576 OGBG-MOLPCBA 437,929 OGBG-PPA 158,100

25.5 34.1 24.1 13.3 18.6 18.8 26.0 243.4

27.5 36.9 51.9 13.7 19.3 19.3 28.1 2,266.1

Binary Classification Binary Classification Binary Classification Regression Regression Regression Regression Regression

2 2 2

PEPTIDES-FUNC PEPTIDES-STRUCT

150.9 150.9

307.3 307.3

Multi-task Classification Multi-task Regression

15,535 15,535

AUROC AUROC AUROC Root Mean Square Error 12 Root Mean Square Error 617 Root Mean Square Error 128 Root Mean Square Error 1 Root Mean Square Error 10 11

Root Mean Square Error Avg. Precision

Open Graph Benchmark (OGB) The Open Graph Benchmark (OGB) is a collection of large-scale and realistic graph datasets (Wu et al., 2018; Hu et al., 2020) designed to facilitate reproducible and rigorous evaluation of graph machine learning methods. Among its offerings, the molecular property prediction suite, which commonly refers to as the OGB-LSC and OGB-Mol datasets, which comprises twelve standardized benchmarks: MOLHIV, MOLTOX21, MOLTOXCAST, MOLBACE, MOLBBBP, MOLCLINTOX, MOLSIDER, MOLESOL, MOLFREESOLV, and MOLLIPO. These datasets are derived from real-world chemical and biomedical applications, where each graph represents a molecule (with atoms as nodes and bonds as edges), and the task is to predict properties such as toxicity (MOLTOX21, MOLTOXCAST, 31

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

MOLCLINTOX), bioactivity (MOLHIV, MOLBACE, MOLBBBP), side effects (MOLSIDER), or physical solubility characteristics (MOLESOL, MOLFREESOLV, MOLLIPO). All datasets follow standardized train/validation/test splits based on molecular scaffolds, ensuring meaningful generalization assessment and enabling fair comparison across methods.

Table D.3. Hyper-parameter configurations on benchmark datasets. Dataset

Batch size Layers Num Embed Dim

Epochs Dropout

Readout

Max dim Max Ring Size

MUTAG PTC NCI1 NCI109 PROTEINS IMDB-B IMDB-M RDT-B RDT-M

32 32 32 32 32 32 32 32 32

4 4 4 4 4 4 4 4 4

64 64 64 64 64 64 64 64 64

0.001 0.001 0.001 0.001 0.001 0.001 0.001 0.001 0.001

300 300 300 300 300 300 300 300 300

0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0

mean / sum / sum mean / sum / sum mean / sum / sum mean / sum / sum mean / sum / sum mean / sum / sum mean / sum / sum mean / sum / sum mean / sum / sum

2 2 2 2 2 2 2 2 2

6 6 6 6 6 6 6 6 6

ZINK-Small ZINC-FULL OGBG-MOLHIV

128 128 128

3 3 2

48 128 48

0.003 0.003 0.0001

1000 1000 200

0.0 0.1 0.5

mean / sum / sum mean / sum / sum mean / sum / sum

2 2 2

18 18 6

PEPTIDES-FUNC PEPTIDES-STRUCT

32 32

3 3

128 128

0.003 0.003

1000 1000

0.15 0.15

sum / sum / sum sum / sum / sum

2 2

8 8

D.2. Experiments Setup All experiments are conducted on a Linux system equipped with two NVIDIA RTX A6000 GPUs (48 GB memory each). For all tasks, we adopt the experimental parameters and model configurations in Table D.3. Other hyperparameters set follow the settings established in the following baselines: GIN (Xu et al., 2018)1 , CWN (Bodnar et al., 2021a)2 , PathGNN (Michel et al., 2023)3 , and SMCN (Ebli et al., 2020)4 . The hidden dimension size and the number of model parameters are listed as follows. All models are trained using the Adam optimizer. The hidden dimension size and the total number of model parameters are reported accordingly. All models are trained using the Adam optimizer with a StepLR learning rate scheduler, which reduces the learning rate by a factor of 0.5 every 50 epochs. D.3. Experimental Results Open Graph Benchmark Table D.4 reports the performance of CCIN on the OGB molecular property prediction benchmark, covering both molecular classification and regression tasks. Overall, CCIN achieves best or near-best results on most datasets, demonstrating stable and consistent performance advantages. On the molecular classification tasks MOLBACE and MOLBBBP, CCIN achieves ROC-AUC of 80.47 and 69.81, respectively, outperforming baseline methods such as GIN and CWN, indicating its stronger discriminative ability in predicting biological activity and molecular permeability. For molecular regression and multi-task prediction tasks, CCIN achieves the lowest RMSE on datasets such as MOLESOL, MOLLIPO, MOLTOX21, and MOLTOXCAST, and maintains competitive performance on MOLCLINTOX and MOLSIDER. These results suggest that CCIN is effective at leveraging structural information in molecular graphs and achieves robust performance across both classification and regression tasks.

Table D.4. Classification tasks are evaluated using ROC-AUC, while regression and multi-task datasets are evaluated using RMSE. ROC-AUC% ( ↑ )

RMSE( ↓ )

MOLBACE MOLBBBP MOLCLINTOX GIN(Xu et al., 2018) 76.73±1.53 67.08±1.35 HGIN (Zhang et al., 2025b) 76.68±3.36 67.69±1.00 MSPN(Bodnar et al., 2021b) 78.64±1.43 66.35±2.78 CWN (Bodnar et al., 2021a) 77.05±2.26 65.46±1.00 CCIN 80.47±1.89 69.81±1.46

0.2627±0.016 0.2594±0.002 0.2458±0.004 0.2557±0.032 0.2514±0.078

MOLESOL

MOLFREESOLV

1.5265±0.173 1.7783±0.012 1.6371±0.046 1.5870±0.157 1.4051±0.293

2.1612±0.16 3.7672±0.15 2.3683±0.07 3.8344±0.11 3.7678±0.28

https://github.com/weihua916/powerful-gnns https://github.com/twitter-research/cwn 3 https://github.com/gasmichel/PathNNs_expressive 4 https://github.com/yoavgelberg/SMCN 2

MOLLIPO

MOLSIDER

MOLTOX21 MOLTOXCAST

1.8118±0.252 0.4935±0.011 0.3364±0.014 1.0416±0.008 0.4740±0.002 0.3348±0.033 1.1458±0.094 0.4829±0.035 0.3524±0.035 1.0602±0.008 0.4702±0.072 0.3349±0.002 1.0332±0.083 0.4601±0.069 0.3186±.0257

0.4337±0.013 0.4019±0.002 0.3905±0.014 0.3879±0.008 0.3599±0.012

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Four Neighborhoods Table D.5 further quantitatively validates the impact of different neighborhood designs on model performance. It can be observed that CCIN, using only upper and lower neighborhoods, significantly outperforms the full model on multiple datasets, especially on large-scale molecular graphs and social network graphs. For example, on the NCI1 and NCI109 datasets, CCIN improves performance by approximately 1.13% (80.69 vs. 79.56) and 1.17% (79.71 vs. 78.54) compared to Full, respectively; the improvement is even more significant on the social network datasets RDT-B and RDT-M, reaching 4.28% (93.43 vs. 89.15) and 1.81% (57.30 vs. 55.49), respectively. This result demonstrates that the multi-scale structural information provided by upper and lower neighborhoods is sufficient to effectively characterize the core discriminative features of a graph, while introducing additional finer-grained neighborhood modules may lead to information redundancy or noise accumulation on some datasets. Meanwhile, ablation experiments show that removing N ↑ causes the most significant performance degradation, for example, a decrease of 6.61% and 6.76% on NCI1 and NCI109, respectively, validating the crucial role of upper-layer neighborhoods in capturing global structural information. Conversely, removing B or N ↓ actually improves performance on some datasets (e.g., on MUTAG, w/o-B improves performance by approximately 1.5% compared to Full), indicating that certain neighborhood modules may introduce mismatched information under specific graph structures.These results demonstrate that the upper and lower neighborhoods constitute the core of topological neural network relationship modeling. While other neighborhood modules can supplement information in specific scenarios, they may also introduce unnecessary complexity, thereby affecting the model’s generalization performance on different datasets. Table D.5. Predictive performance on graph classification.(Mean±Std) w/o-B w/o-C w/o-N↑ w/o-N↓ CCIN-Full CCIN

MUTAG

PTC

PROTEINS

NCI1

NCI109

IMDB-B

IMDB-M

RDT-B

RDT-M

90.62±7.16 90.55±8.32 87.77±9.22 89.75±7.1 89.14±7.72 96.30±5.24

62.64±8.87 62.35±8.48 62.05±6.49 61.17±8.42 61.47±8.37 62.65±10.12

75.40±4.94 74.14±3.84 75.41±4.15 72.88±4.21 74.95±5.43 76.14±2.53

79.46±2.23 79.44±1.87 72.95±3.17 78.37±1.66 79.56±1.63 80.69±1.22

77.56±2.11 77.91±1.96 71.78±1.35 77.45±1.71 78.54±1.42 79.71±2.05

74.73±4.73 74.32±4.51 73.93±2.74 74.41±4.93 75.70±4.29 74.34±4.58

51.93±3.73 52.29±4.66 51.98±3.62 52.79±3.61 52.00±3.47 52.71±3.17

91.43±2.43 91.95±2.35 85.50±3.17 91.65±1.13 89.15±3.61 93.43±1.15

54.26±2.35 54.89±1.57 54.98±3.73 55.46±2.41 55.49±1.54 57.30±1.78

Ring Size The maximum ring size controls the order of the same-dimensional combinatorial expansion induced by the bridging cell. Figure D.1 shows when the ring size increases, the edges number of face are involved with more information.

�1 �2

�3

Cycle Graph ��

�1

�4

�2

�3

Cycle Graph ��

�5

�1 �2

�4

�3

�6

�1

�2

Cycle Graph ��

�3

�5

�4

�2

�3

Cycle Graph ��

�1

�4

�8

�5

�7 �6

Cycle Graph ��

Figure D.1. Regular simplicial complexes are non-isomorphic (Simplicial Weisfeiler-Lehman cannot distinguish them).

Table D.6. Comparison of maximum ring performance on CCIN model. Maximum ring size is set 4 to 14 (≥ 3). Ring Size

MUTAG

PTC

PROTEINS

NCI1

NCI109

4 5 6 7 8 9 10 11 12 13 14

96.30±5.24 94.44±7.86 92.59±6.93 94.44±7.86 96.30±5.24 96.29±5.23 96.32±5.23 96.29±5.23 94.45±7.86 96.29±5.23 96.29±2.61

62.75±6.04 60.78±5.00 61.76±2.40 62.75±5.00 61.76±2.40 61.76±4.81 61.82±2.78 59.80±11.34 59.80±6.04 60.78±3.67 61.76±2.41

76.58±6.02 74.17±0.85 74.17±2.58 74.17±4.49 75.38±1.85 73.87±1.47 74.77±4.41 74.77±5.56 73.87±6.74 74.17±5.57 75.07±4.73

79.40±1.85 80.45±1.44 81.02±1.24 82.24±0.69 81.75±0.72 82.40±0.57 82.18±2.32 82.56±1.69 81.26±0.52 82.72±0.79 82.48±2.15

79.94±3.88 80.26±0.64 80.42±2.12 80.26±2.00 80.34±1.21 81.63±0.45 81.20±2.10 80.09±1.29 81.23±0.81 80.51±0.46 79.93±1.19

To evaluate the impact of the maximum ring size hyperparameter, we progressively increased the ring size from 4 to 14 and reported classification performance on multiple biomolecular graph datasets. Table D.6 shows that moderately increasing the ring size generally helps improve the model’s ability to represent local closed structures (rings/loops). For example, on 33

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

NCI1, with the ring size increasing from 4 to 7 improved the accuracy from 79.40 to 82.24 (an improvement of 3.58%), and then gradually improved the accuracy at 9, 11, and 13, indicating that a longer range of closed structure information can supplement the local structural cues of the molecular graph; NCI109 also achieved the highest accuracy of 81.63 at Ring size=9, an improvement of 2.11% compared to 79.94 at Ring size=4. In contrast, the optimal value for the small molecule dataset MUTAG appears at smaller or medium ring lengths (e.g., approximately 96.29 for Ring size = 4, 8, 10, and 14), but drops to 92.59 at Ring size = 6. This indicates that when the dataset size is small or the statistical instability of higher-order closed structures is high, excessively increasing the ring length may introduce redundant and noisy structures. We also calculated the failure rate at different Ring sizes on the Strongly Regular Graphs benchmark. Table D.7 shows that when the Ring Num is small, some baseline models still exhibit non-zero failure rates on certain SRG instances; however, as the Ring Num increases, the failure rate of CCIN approaches 0 on most SRG instances, demonstrating that more comprehensive closure combination information helps enhance structure discriminative ability. The ring length controls the "closed information coverage" of the same-dimensional combination expansion. Appropriately increasing the Ring size characterizes the local ring structure and improve the distinguishing ability, but an excessively large ring length may lead to statistical instability and redundant closed patterns on some datasets. Table D.7. Failure rates (%) on Strongly Regular Graphs (Rings: 4,5,6,7,8). (Mean±Std). Model

sr251256

sr16622

sr261034

GIN HGIN 4 MPSN CIN CCIN

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

7.83e-02±0.0 4.44e-02±0.0 6.67e-02±0.0 4.44e-02±0.0 4.44e-02±0.0

0.00±0.00 7.15e-03±0.0 7.03e-06±3.52e-07 3.64e-04±0.0 2.61e-02±0.0 5.71e-02±0.0 0.00±0.00 0.00±0.00 3.02e-06±2.1e-07 7.79e-06±3.1e-06 1.82e-02±6.1e-06 1.82e-02±0.0 0.00±0.00 6.15e-04±6.1e-05 3.02e-04±2.7e-06 0.00±0.00 8.16e-02±0.0 8.16e-02±0.0 0.00±0.00 0.00±0.00 3.52e-06±2.09e-07 7.79e-06±3.1e-06 1.92e-02±7.0e-05 1.92e-02±0.0 0.00±0.00 4.88e-04±1.2e-04 4.88e-06±3.02e-06 7.79e-06±3.1e-06 1.91e-02±8.1e-05 1.85e-02±0.0

sr281264

sr291467

sr351668

sr351899

sr361446

sr401224

GIN HGIN 5 MPSN CIN CCIN

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

6.67e-02±0.0 4.44e-02±0.0 6.67e-02±0.0 4.44e-02±0.0 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

6.10e-04±0.0 0.00±0.00 6.1e-04±6.1e-05 0.00±0.00 0.00±0.00

6.43e-03±0.0 0.00±0.00 3.02e-04±2.7e-06 3.5e-06±2.1e-07 0.00±0.00

GIN HGIN 6 MPSN CIN CCIN

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 6.67e-02±0.0 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 6.67e-02±0.0 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 6.1e-04±0.0 0.00±0.00 6.1e-04±6.1e-05 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 3.02e-04±2.7e-06 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 8.16e-02±0.0 0.00±0.00 8.16e-02±0.0 0.00±0.00

GIN HGIN 7 MPSN CIN CCIN

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 6.67e-02±0.0 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

6.1e-04±0.0 0.00±0.00 6.1e-04±6.1e-05 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 3.1e-04±2.7e-06 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 8.16e-02±0.0 0.00±0.00 0.00±0.00

GIN HGIN 8 MPSN CIN CCIN

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 1.67e-06±0.0 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

2.3e-06±0.0 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 5.71e-03±0.0 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

4.52e-06±0.0 0.00±0.00 0.0 0.00±0.00 1.85e-02±7.0e-05 1.85e-02±0.0 0.00±0.00 8.16e-02±0.0 8.16e-02±0.0 7.79e-06±3.1e-06 1.92e-02±7.0e-05 1.85e-02±0.0 0.00±0.00 0.00±0.00 5.3e-03±0.0

Max Dim Table D.8 shows the performance variation of CCIN under different maximum dimensionality (max dim) input features, indicating that high-order structural information has a notable impact on on model performance. Table D.8. Performance of CCIN model with different maximum dimension features max dim

MUTAG

PTC

PROTEINS

NCI1

NCI109

IMDB-B

IMDB-M

RDT-B

0 1 2

75.93±6.93 96.30±5.24 94.44±7.86

59.80±6.04 60.78±2.77 64.71±2.40

74.77±4.59 74.47±5.01 75.12±3.06

70.40±3.36 80.45±1.59 80.70±1.20

70.15±2.77 80.91±1.78 81.02±2.35

75.67±2.62 76.67±3.09 78.00±5.72

52.44±1.91 54.22±4.91 53.33±7.1

75.50±1.78 92.33±0.85 89.83±8.27

When the maximum dimension is 0 (containing only 0-cell node information), the model’s performance is limited on multiple datasets. For instance, the classification accuracy on MUTAG, NCI1, and RDT-B is 75.93, 70.40, and 75.50, respectively. After introducing 1-dimensional structural information by incorporating 1-cell (edge-level) features, the model performance improves substantially. Specifically, the accuracy on MUTAG increases from 75.93 to 96.30, corresponding to a relative improvement of approximately 26.8%; on NCI1, it increases from 70.40 to 80.45 (a 14.3% relative improvement); and on RDT-B, it rises from 75.50 to 92.33, achieving a 22.3% relative improvement. Building upon this, further incorporating 34

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

2-dimensional structural information by adding 2-cell features leads to continued performance gains on some datasets. For example, on PTC, the accuracy improves from 60.78 to 64.71 yielding a relative improvement of 6.5%. On NCI1 and NCI109, smaller relative improvements of 0.3% and 0.1% are observed, suggesting that higher-order topological structures can further complement complex relational patterns. However, on datasets such as MUTAG and RDT-B, the performance exhibits slight fluctuations after introducing 2-dimensional information, implying that in scenarios with fewer higher-order structures, excessively high-dimensional representations may introduce redundant information. Layer Number To analyze the impact of network depth on model performance, we increased the number of layers in CCIN from 1 to 8 and evaluated it on the molecular graph dataset and the Strongly Regular Graphs benchmark. Table D.9 shows that in molecular graph classification tasks, the model is generally stable with varying layer counts, and optimal performance typically occurs in shallower structures (1-3 layers). For example, on MUTAG, a 1-layer model achieves a peak accuracy of 98.15%, while performance significantly decreases with 7 and 8 layers, indicating that excessively deep networks may cause oversmoothing problem on small datasets. For large-scale datasets such as NCI1 and NCI109, the performance difference between different layer counts is smaller, with 2-3 layers achieving comparable results to deeper networks. On the SR family benchmarks (Table D.10), network depth has a more significant impact on structural discriminative ability. As the number of layers increases from 1 to 3-4, the failure rate of the model on most SRG instances drops rapidly and approaches 0, indicating that moderately increasing the depth helps to aggregate higher-order structural information, when the number of layers increases further, the performance improvement tends to stable. Table D.9. Classification accuracy of CCIN model with different layers. Layer number is set 1 to 8. layer num

MUTAG

PTC

PROTEINS

NCI1

NCI109

1 2 3 4 5 6 7 8

98.15±2.62 94.44±7.86 96.30±2.62 92.59±6.93 94.44±4.54 94.44±4.54 83.33±9.07 72.22±9.07

62.75±5.00 63.73±5.00 61.76±4.80 61.76±2.40 63.73±3.67 59.80±6.04 60.78±3.67 63.72±1.39

75.98±3.32 76.28±4.90 74.47±3.32 74.17±2.58 75.98±2.36 73.87±3.68 75.98±2.12 73.27±2.97

81.43±1.65 81.83±1.79 81.02±0.79 81.02±1.24 81.02±0.40 80.94±0.64 81.83±0.61 81.51±1.82

79.85±2.09 79.61±0.52 80.58±1.05 80.42±2.12 80.74±1.60 80.26±1.69 81.31±1.24 80.17±1.49

Table D.10. Failure rates (%) on Strongly Regular Graphs (Rings: 4,5,6,7). (Mean±Std). Model

sr251256

sr16622

sr261034

sr281264

sr291467

sr351668

sr351899

sr361446

sr401224

1 2 3 4 5 6 7 8

9.52±0.00 5.71±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

6.67±0.0 6.22±0.17 4.44±0.00 4.44±0.00 3.56±0.00 2.67±0.17 2.22±0.00 2.22±0.00

0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

67.81±2.07 4.12±0.21 4.87e-4±1.19e-04 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

3.11±0.13 0.08±2.79e-05 4.90e-06±2.21e-06 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

2.51±0.17 0.12±9.28e-05 7.79e-06±3.12e-06 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00 0.00±0.00

8.09±0.02 5.62±0.14 1.94±8.08e-05 1.12±0.09 0.98±0.09 0.92±7.39e-05 0.81±1.15e-04 0.70±4.87e-05

8.20±0.0 7.83±0.12 1.85±0.00 1.74±0.01 1.27±0.05 1.01±0.02 0.89±0.02 0.79±0.00

Injective Function Design. To analyze the impact of different neighborhood aggregation functions on model performance, we conducted ablation experiments on commonly used aggregation functions, including sum, mean, and max, in Init Readout, Intermediate Readout, and Final Readout. Table D.11 shows that, while keeping the intermediate and final readout functions both as sum, a comparison of the initial readout functions reveals that different aggregation methods have similar overall performance across various datasets. For example, on the MUTAG dataset, mean and sum have similar performance (96.30 vs. 96.29), while max is slightly lower. On PTC and RDT-B, mean aggregation achieves better results of 65.69 and 78.67, respectively, indicating that mean aggregation is more effective in integrating local structural information. Table D.11. Ablation study on init readout function. Readout: sum, Final readout: sum.

Init Method

sum max mean

MUTAG

PTC

PROTEINS

NCI1

NCI109

IMDB-B

IMDB-M

RDT-B

96.29±5.26 94.44±2.47 96.30±5.24

61.76±6.35 63.73±6.04 65.69±5.00

74.17±2.78 74.17±2.97 75.08±1.12

81.51±0.91 81.35±1.52 80.86±1.32

79.45±2.48 79.37±2.72 80.74±2.52

76.67±2.05 76.00±1.41 76.00±2.94

53.33±6.79 53.33±3.31 53.56±5.14

76.50±3.89 77.19±3.94 78.67±2.66

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

Table D.12 shows that the three aggregation functions show little difference in performance on most datasets, but exhibit different advantages on individual datasets. For example, on NCI1 and NCI109, sum and mean aggregations achieve similar performance, while on PTC, max aggregation achieves a relatively high accuracy (64.71). Table D.12. Ablation study on intermediate layer readout function. Initial Method: mean, Final readout: sum.

Intermediate Readout

mean sum max

MUTAG

PTC

PROTEINS

NCI1

NCI109

IMDB-B

IMDB-M

RDT-B

96.30±2.62 94.44±7.86 94.44±7.86

61.76±7.21 61.76±2.40 64.71±2.40

73.57±1.85 73.87±5.15 74.47±3.06

81.18±0.64 81.51±1.43 80.70±1.20

79.69±2.45 79.94±1.41 80.02±2.35

76.33±3.09 77.33±2.62 76.00±5.72

53.56±3.62 53.33±7.12 52.44±5.37

79.50±5.31 71.83±8.27 78.67±2.09

Table D.13 observes that the final readout function has a more direct impact on model performance. For example, on the MUTAG dataset, using mean as the final readout function can improve the accuracy to 98.15, which is about 1.9% and 3.9% higher than sum and max, respectively. These results indicate that the choice of specific aggregation function is relatively stable for the initial and intermediate layers, while the final readout layer has a more significant impact on performance. Table D.13. Ablation study on final readout function. Initial Method: mean, Readout: sum.

Final Readout

mean sum max

MUTAG

PTC

PROTEINS

NCI1

NCI109

IMDB-B

IMDB-M

RDT-B

98.15±2.63 96.30±2.62 94.44±7.86

62.75±4.99 60.78±3.67 61.34±5.27

74.17±2.25 75.08±3.32 75.68±2.65

81.83±0.11 81.43±1.44 80.32±4.39

81.07±1.55 80.83±0.52 80.66±2.10

77.32±3.74 78.33±4.03 75.67±0.47

53.11±4.23 54.28±5.36 54.00±6.28

79.83±1.84 76.45±2.64 77.27±1.69

E. Time and Computational Complexity We analyze the computational and memory complexity of the proposed combinatorial complex Weisfeiler-Lehman test and its neural instantiation CCIN. In a combinatorial complex, the degree of a cell is defined as follows: for any k-cell with σ, the boundary size |B(σ)| is the number of its neighboring (k − 1)-cells, and the co-boundary size |C(σ)| is the number of its (k + 1)-cells. The neighborhood degree |N↓ (σ)| is the number of other k-cells sharing a given (k − 1)-cell, and the set of k-cells of the coboundary corresponding to each (k − 1)-cell τ is defined as Sk (τ ). The neighborhood degree |N↑ (σ)| is the number of other k-cells sharing a given (k + 1)-cell, and the set of k-cells of the boundary to each k + 1-cell τ is defined as Sk (η). The computational complexity of the four neighborhood functions is shown in Table E.1. Table E.1. Time complexity of four neighborhood function on combinatorial complexes Neighborhood Function O(

Time complexity

Boundary (✗) P σ∈X |B(σ)|) k

Co-Boundary (✗) P O( σ∈X |C(σ)|) k

Lower Adjacency (✓) P |Sk (τ )|2 ) τ ∈X

k−1

Upper Adjacency (✓) P |Sk+1 (η)|2 ) η∈X k+1

As before, Lemma 4.7 and Theorem 4.8 have simplified the update rules for combinatorial complexes, namely, retaining only the upper and lower neighborhoods , reducing the multisets of boundary and coboundary that need to be constructed and participate round without losing discriminative power. Specifically, The algorithmic complexity of P in the hash in eachP CCIN is O( τ ∈Xk−1 |Sk (τ )|2 + η∈Xk+1 |Sk+1 (η)|2 ), which is comparable to the expressive power of full higher-order message passing framework on combinatorial complexes. We compared the single-epoch training time (seconds/epoch) of CCIN with its full version CCIN-Full (with four neighborhood) in Table E.2. Specifically, training time is reduced by an average of approximately 6.6%, with the most speedup of 18.1% on NCI109 dataset, and a 24.8% speedup on ZINK-Small dataset. This indicates that by theoretically simplifying and removing redundant boundary, co-boundary calculations, runtime efficiency is improved while maintaining expressive power. Table E.2. Train time (seconds per epoch) PROTEINS

NCI1

NCI109

ZINK-Small

ZINC-FULL

MOLHIV

CCIN-Full 5.16 15.20 13.28 21.85 290.61 84.22 CCIN 4.24 (-17.83%) 13.97 (-8.09%) 10.87 (-18.15%) 16.42 (-24.85%) 280.85 (-3.36%) 77.19 (-8.35%)

PEPTIDES-FUNC PEPTIDES-STRUCT 52.81 46.90 (-11.19%)

75.36 69.48 (-7.80%)

Avg. 69.56 64.99 (-6.57%)

Record · ID 151729 · SHA-256 43f69840f121cd68
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.