Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks
Pith reviewed 2026-05-09 19:17 UTC · model grok-4.3
The pith
Upper and lower neighborhoods suffice to achieve the full expressive power of the Combinatorial Complex Weisfeiler-Lehman test.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The Combinatorial Complex Weisfeiler-Lehman (CCWL) test extends the classical WL procedure by formalizing topological message passing through four types of neighborhood relation on combinatorial complexes. The central discovery is that the upper and lower neighborhoods alone are sufficient to reach the expressivity of the full CCWL framework across all topological structures of combinatorial complexes.
What carries the argument
The CCWL test, which encodes four neighborhood relations (upper, lower, and the remaining two) to perform topological message passing and to test isomorphism of combinatorial complexes.
If this is right
- Topological neural networks can be analyzed for expressive power under one unified CCWL measure.
- Architectures such as CCIN can be built using only upper and lower neighborhoods while retaining full distinguishing power.
- The same sufficiency result holds uniformly for set-based structures like hypergraphs and part-whole structures like simplicial complexes.
- Empirical evaluations show CCIN outperforming existing topological baselines on synthetic isomorphism tasks and real-world data.
Where Pith is reading between the lines
- Implementations of topological networks could reduce computation by tracking only upper and lower adjacencies without loss of theoretical power.
- The result supplies a concrete test for whether a new higher-order architecture matches the distinguishing capability of CCWL.
- Existing simplicial or cellular complex networks can be re-examined to determine which already operate at the reduced upper-lower level.
Load-bearing premise
The four neighborhood relations defined in the combinatorial complex framework are exhaustive and the axiomatic WL extension preserves all relevant topological distinctions without additional constraints.
What would settle it
A pair of non-isomorphic combinatorial complexes that the full four-neighborhood CCWL distinguishes but the upper-and-lower version does not.
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Combinatorial Complex Weisfeiler-Lehman (CCWL) test as an axiomatic extension of the classical WL test to combinatorial complexes, formalizing topological message passing via four neighborhood relations. It proves that the upper and lower neighborhoods alone suffice to achieve the full distinguishing power of the CCWL test across arbitrary combinatorial complexes. Building on this, the authors propose the Combinatorial Complex Isomorphism Network (CCIN) and report that it outperforms existing baselines on both synthetic and real-world benchmarks.
Significance. If the central sufficiency proof holds without hidden restrictions on the complexes, the work supplies a unified theoretical lens for the expressive power of topological neural networks that subsumes graphs, hypergraphs, simplicial complexes, and cellular complexes. The reduction to only two neighborhood types would also yield a concrete efficiency gain for higher-order message passing. The experimental section provides initial evidence that the resulting CCIN architecture is competitive, though the strength of this evidence depends on the completeness of the benchmark suite and ablation controls.
major comments (2)
- [Section 4.2, Theorem 1] Section 4.2, Theorem 1 (sufficiency of upper/lower neighborhoods): the proof sketch asserts that distinctions arising from the two omitted neighborhood relations are recoverable from upper/lower message passing, yet the argument does not exhibit an explicit reduction or enumerate the higher-order incidence cases (e.g., a 2-cell incident to two 1-cells that are not adjacent via the retained relations) where the omitted relations could separate non-isomorphic complexes. Without such a case analysis or counter-example search, the claim that the result holds “across topological structures of combinatorial complexes” remains open to counter-examples.
- [Definition 3.1] Definition 3.1 and the subsequent axiomatic extension: the four neighborhood relations are introduced as exhaustive, but the manuscript does not prove that every combinatorial complex satisfies the incidence axioms needed for the WL iteration to be well-defined when only upper and lower neighborhoods are retained; a short counter-example complex violating one of the implicit incidence conditions would falsify the reduction.
minor comments (2)
- [Figure 2] Figure 2 (CCWL iteration diagram) uses inconsistent arrow styles for the four neighborhood types; clarifying the legend would improve readability.
- [Section 5] The experimental section reports aggregate accuracy but omits per-dataset standard deviations and the exact hyper-parameter search protocol; adding these details would strengthen reproducibility.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, providing clarifications on the proofs and indicating where revisions will be made to strengthen the presentation.
read point-by-point responses
-
Referee: [Section 4.2, Theorem 1] Section 4.2, Theorem 1 (sufficiency of upper/lower neighborhoods): the proof sketch asserts that distinctions arising from the two omitted neighborhood relations are recoverable from upper/lower message passing, yet the argument does not exhibit an explicit reduction or enumerate the higher-order incidence cases (e.g., a 2-cell incident to two 1-cells that are not adjacent via the retained relations) where the omitted relations could separate non-isomorphic complexes. Without such a case analysis or counter-example search, the claim that the result holds “across topological structures of combinatorial complexes” remains open to counter-examples.
Authors: We appreciate the referee highlighting the desirability of greater explicitness in the proof of Theorem 1. The appendix contains the complete argument, which proceeds by showing that any color refinement step using the omitted neighborhoods can be simulated exactly by a finite number of iterations over upper and lower neighborhoods alone, using the rank-ordered incidence poset structure of combinatorial complexes. For the concrete case of a 2-cell incident to two non-adjacent 1-cells, the distinction is first encoded in the 1-cell color multisets after a single lower-neighborhood aggregation and is then propagated to the 2-cell via its upper neighborhood; this equivalence holds because the omitted relations are compositions of the retained ones under the partial order. We will revise Section 4.2 to include this explicit reduction together with a short case analysis for higher-rank incidences and a small illustrative example, thereby removing any ambiguity about potential counter-examples. revision: yes
-
Referee: [Definition 3.1] Definition 3.1 and the subsequent axiomatic extension: the four neighborhood relations are introduced as exhaustive, but the manuscript does not prove that every combinatorial complex satisfies the incidence axioms needed for the WL iteration to be well-defined when only upper and lower neighborhoods are retained; a short counter-example complex violating one of the implicit incidence conditions would falsify the reduction.
Authors: The four neighborhood relations are derived directly from the incidence poset that defines every combinatorial complex (Definition 2.1). Upper and lower neighborhoods correspond precisely to the covering relations of higher and lower rank, which are part of the standard axioms of a combinatorial complex and therefore hold for every such structure by definition. Consequently, the message-passing iteration remains well-defined when restricted to these two relations; no additional incidence axioms are imposed. We will add a brief clarifying paragraph immediately after Definition 3.1 that recalls the poset axioms and states that the reduction inherits well-definedness from the underlying combinatorial complex, thereby addressing the concern. revision: yes
Circularity Check
No circularity: CCWL is an independent axiomatic extension with a claimed proof of neighborhood sufficiency.
full rationale
The paper introduces CCWL as a new axiomatic-style extension of the classical WL test to combinatorial complexes, defining four neighborhood relations and then proving that upper and lower neighborhoods suffice for full expressivity. No equations or steps reduce a claimed result to a fitted parameter, self-definition, or load-bearing self-citation chain; the framework is presented as a fresh unification rather than a renaming or tautological restatement of prior inputs. The sufficiency claim is a mathematical assertion whose validity is independent of circularity analysis.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.