Ccmamba Achieves Scalable Higher-Order Graph Learning on Combinatorial Complexes with Quadratic Complexity

Researchers are tackling the limitations of current graph neural networks by exploring how to better model complex relationships beyond simple pairwise interactions. Jiawen Chen, Qi Shao, and Mingtong Zhou, from the School of Mathematics at Southeast University, alongside Duxin Chen and Wenwu Yu, present a novel approach in their paper, ‘CCMamba: Selective State-Space Models for Higher-Order Graph Learning on Combinatorial Complexes’. They introduce Combinatorial Complex Mamba (CCMamba), a groundbreaking framework that leverages state-space models to efficiently learn from combinatorial complexes , a unified topological structure , overcoming the quadratic complexity and limited dimensionality of existing attention-based methods. This innovation not only improves scalability and robustness in higher-order complexes but also demonstrates expressive power comparable to the powerful 1-Weisfeiler-Lehman test, marking a significant step forward in topological machine learning.

CCMamba learns from complex relational structures and generalizes

This breakthrough addresses limitations in existing methods that struggle to model higher-order relational structures beyond simple pairwise interactions, a common challenge in analysing complex systems. CCMamba’s core innovation lies in its ability to efficiently process the intricate topology of combinatorial complexes, which generalise graphs, hypergraphs, and higher-order complexes into a unified structure. By treating topological relations as structured sequences, the researchers have unlocked the potential of state-space models to achieve global, context-aware propagation, overcoming the locality constraints of previous topological deep learning approaches. Furthermore, the study establishes a theoretical foundation for CCMamba’s expressive power, proving that its message passing capabilities are upper-bounded by the 1-Weisfeiler, Lehman test, a crucial benchmark in graph learning.
This theoretical analysis solidifies the framework’s potential for capturing complex relationships within data. The work opens new avenues for applying topological deep learning to real-world problems, including biomolecular interaction networks, traffic dynamics, and image analysis. This research establishes a new paradigm for higher-order graph learning, moving beyond low-dimensional message passing and quadratic complexity limitations. By integrating selective state-space models, CCMamba provides a scalable and expressive framework for capturing intricate relational patterns in complex data.

Measurements confirm that CCMamba achieves this efficiency without compromising expressive power; theoretical analysis establishes that the upper bound of its message passing capability is equivalent to the 1-Weisfeiler-Lehman test. Results demonstrate CCMamba’s ability to process complex data with significantly reduced computational demands. Specifically, the framework linearizes neighborhood sequences and models long-range propagation, offering a substantial improvement over traditional methods. The study meticulously defines a lifting operation to translate graph data into higher-order combinatorial complexes, enabling the representation of intricate relationships beyond simple pairwise interactions.
This allows for a more nuanced understanding of the underlying structure of the data. Tests prove that CCMamba’s rank-structured selective state-space mechanism effectively captures dependencies within and between cells of different topological ranks. The researchers defined four key neighborhood types, Node-Edge, Edge-Node, Edges-Face, and Face-Edge, to govern message propagation across dimensions, ensuring comprehensive information flow. Data shows that the framework accurately models these relationships, leading to superior performance on node and graph classification tasks. The expressive power of CCs-based Mamba message passing is bounded above by the 1-dimensional combinatorial complex Weisfeiler, Lehman test, confirming its theoretical capabilities.

Furthermore, the work establishes a formal definition of a combinatorial complex as a triple (S, C, rk), where S is a finite set of vertices, C is a collection of cells, and rk is an order-preserving rank function. This rigorous mathematical foundation underpins the framework’s ability to generalize across various data types, including graphs, hypergraphs, and simplicial complexes. The breakthrough delivers a scalable and robust solution for learning on complex data, opening new avenues for applications in diverse fields such as materials science, social network analysis, and drug discovery.

CCMamba learns on complex structures efficiently and quickly

This research reformulates message passing, a key process in neural networks, as a selective state-modeling problem, enabling efficient information processing. The significance of this work lies in its ability to generalise across various complex data types, including graphs, hypergraphs, simplicial complexes, and cellular complexes, while maintaining expressive power comparable to the 1-Weisfeiler-Lehman test, a measure of a model’s ability to distinguish between different network structures. The authors acknowledge a limitation in that the current implementation focuses on node classification tasks, and further investigation is needed to explore its performance on other tasks. Future research directions include extending CCMamba to handle dynamic combinatorial complexes and exploring its application to more complex real-world datasets, potentially unlocking new capabilities in areas such as materials discovery and drug design.