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

• URL: http://arxiv.org/abs/2605.00725v1
• Date: Fri, 01 May 2026 15:19:40 GMT
• Title: Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks
• Abstract summary: We introduce the Combinatorial Complex Weisfeiler-Lehman (CCWL) test, an axiomatic-style extension of the WL test to complexes.<n>CCWL provides a unified perspective on the expressive power of higher-order variants.<n>We also propose the Combinatorial Complex Isomorphism Network (CCIN) and evaluate it on synthetic and real-world benchmarks.
• Score: 17.8391516367819
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• On the Topology of Neural Network Superlevel Sets [1.827510863075184]
  We show that neural networks with activations satisfying a Riccati-type ordinary differential equation condition, produce Pfaffian outputs on analytic domains with format controlled only by the architecture.
  arXiv  Detail & Related papers  (2026-03-03T13:30:06Z)
• CCMamba: Selective State-Space Models for Higher-Order Graph Learning on Combinatorial Complexes [16.627877999057436]
  Topological deep learning has emerged for modeling higher-order structures beyond pairwise interactions.<n>We propose Combinatorial Complex Mamba, the first unified mamba-based neural framework for learning on relational complexes.<n> CCMamba reformulates message passing as a selective state-space modeling problem by organizing multi-rank incidence relations into structured sequences processed by rank-aware state-space models.
  arXiv  Detail & Related papers  (2026-01-28T11:52:13Z)
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
  Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models.<n>We present the first sample of $mathcalO(epsilon)$ in continuous state-action complexity.<n>Our analysis also extends complexity improving upon existing bounds of $mathcalO(epsilon)$.
  arXiv  Detail & Related papers  (2025-03-22T04:22:04Z)
• Inducing Systematicity in Transformers by Attending to Structurally Quantized Embeddings [60.698130703909804]
  Transformers generalize to novel compositions of structures and entities after being trained on a complex dataset. We propose SQ-Transformer that explicitly encourages systematicity in the embeddings and attention layers. We show that SQ-Transformer achieves stronger compositional generalization than the vanilla Transformer on multiple low-complexity semantic parsing and machine translation datasets.
  arXiv  Detail & Related papers  (2024-02-09T15:53:15Z)
• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  We first show that a three-layer neural network can be designed to approximate an indicator function over a compact set. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. We prove the universal approximation property of three-layer ReLU networks using our topological approach.
  arXiv  Detail & Related papers  (2023-05-25T14:17:15Z)
• Topological Learning in Multi-Class Data Sets [0.3050152425444477]
  We study the impact of topological complexity on learning in feedforward deep neural networks (DNNs) We evaluate our topological classification algorithm on multiple constructed and open source data sets.
  arXiv  Detail & Related papers  (2023-01-23T21:54:25Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• Topological Deep Learning: Going Beyond Graph Data [26.325857542512047]
  We present a unifying deep learning framework built upon a richer data structure that includes widely adopted topological domains. Specifically, we first introduce complexes, a novel type of topological domain. We develop a class of message-passing complex neural networks (CCNNs) focusing primarily on attention-based CCNNs.
  arXiv  Detail & Related papers  (2022-06-01T16:21:28Z)
• Local and global topological complexity measures OF ReLU neural network functions [0.0]
  We apply a piecewise-linear (PL) version of Morse theory due to Grunert-Kuhnel-Rote to define and study new local and global notions of topological complexity. We show how to construct, for each such F, a canonical polytopal complex K(F) and a deformation retract of the domain onto K(F), yielding a convenient compact model for performing calculations.
  arXiv  Detail & Related papers  (2022-04-12T19:49:13Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.