CCMamba: Topologically-Informed Selective State-Space Networks on Combinatorial Complexes for Higher-Order Graph Learning

This paper introduces CCMamba, the first Mamba-based framework for combinatorial complexes that reformulates higher-order message passing as selective state-space modeling to achieve linear-time, long-range dependency learning while outperforming existing topological deep learning methods in scalability and robustness.

The Gist

The Big Picture: Why Do We Need This?

Imagine you are trying to understand a complex system, like a city's traffic, a social network, or a chemical molecule.

• Old Way (Standard Graphs): Traditional AI models look at these systems like a map of roads. They only see how one point connects to another (Point A $\to$ Point B). It's like knowing who your direct neighbors are, but not understanding the whole neighborhood.
• The Problem: Real life is messier. Sometimes, three people form a group chat, or a chemical reaction involves a whole cluster of atoms at once. Standard models miss these "group dynamics" (called higher-order interactions).
• The Current Fix (Topological Deep Learning): Scientists invented a new way to look at data called Combinatorial Complexes (CCs). Think of this as upgrading from a flat road map to a 3D hologram that includes not just roads, but also intersections, city blocks, and entire districts.
• The New Problem: While this 3D hologram is more accurate, analyzing it is incredibly slow and computationally expensive. The current tools (based on "Attention Mechanisms" like Transformers) try to look at every single connection at once. It's like trying to read every book in a library simultaneously to find one sentence—it causes a traffic jam in the computer's brain.

The Solution: Enter CCMamba

The authors propose CCMamba, a new AI framework that solves the speed problem while keeping the 3D accuracy.

1. The Analogy: The "Selective State-Space" (Mamba)

Imagine you are a tour guide in a massive, ancient library (the Combinatorial Complex).

• The Old Way (Attention/Transformers): The guide tries to memorize every single book on every single shelf at the same time to understand the story. As the library grows, the guide's brain explodes. It's slow and inefficient.
• The CCMamba Way: The guide uses a smart, selective memory. Instead of trying to remember everything at once, they walk down the aisles (the sequence), deciding in the moment what information is important to keep and what to forget. They carry a "backpack" (the State Space) that updates as they walk.
  • If they see a book that connects to the story, they put it in the backpack.
  • If they see a book that's irrelevant, they leave it on the shelf.
  • Result: They can walk through a library the size of a city without getting tired, and they still remember the key plot points perfectly. This is linear time complexity—it scales easily.

2. The "Rank-Aware" Magic

In a Combinatorial Complex, data has different "levels" or ranks:

• Rank 0: Individual points (Nodes/People).
• Rank 1: Connections (Edges/Friends).
• Rank 2: Groups (Faces/Triangles/Clubs).

Most AI models treat these levels as a messy pile. CCMamba is special because it is Rank-Aware.

• Analogy: Imagine a construction site.
  • Standard models just see "bricks."
  • CCMamba knows the difference between a single brick (Rank 0), a wall made of bricks (Rank 1), and a room made of walls (Rank 2).
  • It knows that information flows differently: A brick supports a wall, and a wall supports a room. CCMamba respects these rules, allowing information to flow up and down the hierarchy efficiently without getting confused.

3. Solving the "Over-Smoothing" Problem

In deep neural networks, if you stack too many layers, the data often gets "muddy."

• Analogy: Imagine passing a message down a line of 100 people. By the time it reaches the end, everyone has forgotten the original message and just says "Hello." This is called over-smoothing.
• CCMamba's Fix: Because CCMamba uses a "selective" memory (it chooses what to keep), it doesn't just blur everything together. It acts like a filter. Even in a very deep network (100 layers), it can still distinguish the original message from the noise. This allows the AI to be much "deeper" and smarter without losing its mind.

What Did They Prove?

1. It's Fast: It runs in linear time. If you double the size of the data, it takes roughly double the time (not four times or ten times like the old methods).
2. It's Smart: They proved mathematically that CCMamba is as smart as the best possible test for distinguishing complex shapes (called the 1-CCWL test). It can tell the difference between two complex structures that other models would think are identical.
3. It Works Everywhere: They tested it on:
   • Chemical Molecules: Predicting if a drug works.
   • Social Networks: Understanding group dynamics.
   • Citation Networks: Figuring out how research papers relate.
   • Result: CCMamba beat almost every other model, especially on large, complex datasets where the old models crashed or slowed down.

Summary in One Sentence

CCMamba is a super-efficient, "smart-filter" AI that can understand complex, multi-level group relationships (like cliques and teams) without getting overwhelmed, allowing it to learn faster and deeper than previous methods.

It's like upgrading from a magnifying glass that only sees two dots connected by a line, to a high-speed drone that can instantly map out entire cities, neighborhoods, and buildings, all while remembering exactly what matters.

Technical Summary

1. Problem Statement

Standard Graph Neural Networks (GNNs) are limited to modeling pairwise interactions, failing to capture the complex, multi-way, and hierarchical dependencies found in real-world systems (e.g., biomolecular interactions, traffic dynamics). While Topological Deep Learning (TDL) using structures like hypergraphs, simplicial complexes, and Combinatorial Complexes (CCs) addresses this, existing methods face critical bottlenecks:

• Quadratic Complexity: Most TDL methods rely on attention mechanisms or iterative message passing that scale quadratically ($O(n^2)$) with the number of nodes/cells, making them infeasible for large-scale graphs.
• Local Constraints: Traditional message passing is inherently local and isotropic, struggling to model long-range dependencies and directional flows across different topological ranks (e.g., node-to-edge-to-face).
• Lack of Unified Framework: Existing models often target specific complex types (e.g., only simplicial or only hypergraphs) and fail to preserve rank-aware information across a unified structure.

2. Methodology: CCMamba

The authors propose CCMamba, the first unified neural framework based on Selective State-Space Models (SSMs), specifically the Mamba architecture, designed for learning on Combinatorial Complexes.

Core Architecture

CCMamba reformulates higher-order message passing as a selective state-space modeling problem. Instead of treating topological neighborhoods as static graphs for attention, it linearizes multi-rank incidence relations into structured sequences processed by Mamba layers.

The framework operates in three stages:

1. Intra-neighborhood Selective SSM Filtering:

   • Linearization: Higher-order structures are converted into 1D sequences based on incidence relations (e.g., node-to-edge, edge-to-face).
   • Bidirectional Mamba (BiMamba): Since topological neighborhoods lack a canonical causal order, CCMamba employs bidirectional SSMs. This allows the model to capture structural dependencies from both forward and reverse directions simultaneously, preserving geometric fidelity.
   • Rank-Awareness: The model processes features for different ranks (0-cells/nodes, 1-cells/edges, 2-cells/faces) separately but coupled, using input-dependent state transitions to filter information dynamically.

2. Inter-neighborhood Rank-Level Aggregation:

   • Information is fused across different topological dimensions (e.g., aggregating signals from incident edges and faces into a node representation).
   • This stage uses specific fusion operators ($\phi_1, \phi_2, \phi_3$) to integrate cross-rank contextual signals while maintaining the hierarchical geometry of the CC.

3. Deep Representation Refinement:

   • The architecture incorporates residual connections, layer normalization, and Feed-Forward Networks (FFN) to stabilize training and prevent over-smoothing in deep architectures.

Theoretical Expressivity

The paper establishes a theoretical upper bound on the expressive power of CCMamba. It proves that CCMamba's ability to distinguish non-isomorphic combinatorial complexes is bounded by the 1-dimensional Combinatorial Complex Weisfeiler-Lehman (1-CCWL) test. This confirms that CCMamba is at least as powerful as the standard 1-WL test for graphs but extends this capability to higher-order topological structures.

3. Key Contributions

• First Unified Mamba-based TDL Framework: Introduces CCMamba, a novel architecture that unifies message passing for graphs, hypergraphs, simplicial complexes, and cellular complexes under the Combinatorial Complex formalism.
• Linear-Time Scalability: Replaces quadratic attention mechanisms with linear-time selective state-space models ($O(n)$), enabling the processing of large-scale higher-order structures without the memory bottlenecks of Transformers.
• Rank-Aware Directional Propagation: Develops a bidirectional state-space module that explicitly models directional flows and long-range dependencies across different topological ranks, overcoming the limitations of local, isotropic aggregation.
• Theoretical Guarantees: Provides a formal proof linking CCMamba's expressivity to the 1-CCWL test, establishing its theoretical limits and capabilities.
• Robustness to Depth: Demonstrates that the selective gating mechanism effectively mitigates the over-smoothing problem common in deep GNNs, allowing for stable training in very deep networks (up to 64 layers).

4. Experimental Results

The authors evaluated CCMamba on extensive benchmarks including graph classification (MUTAG, PROTEINS, IMDB), node classification (Cora, CiteSeer, PubMed), and heterophilic graphs.

• Performance: CCMamba (specifically the "rank-cell" variant) achieved State-of-the-Art (SOTA) or competitive results across almost all datasets.
  • On MUTAG, it outperformed the best cellular baseline (CWN) by +2.64% and the graph-based GAT by +5.86%.
  • On Cora, it reached 89.22% accuracy, surpassing attention-based CCCN.
• Comparison with Attention: In direct comparisons with GAT and MultiGAT, Mamba-based models consistently outperformed attention-based counterparts, particularly on higher-order structures (simplicial and cellular), showing gains of up to +37.7% on specific hypergraph tasks.
• Scalability & Efficiency:
  • Memory: CCMamba reduced GPU memory consumption by up to 85.8% compared to Multi-head GAT on large datasets (e.g., PROTEINS).
  • Time: Training time was reduced by up to 87.9% compared to attention-based baselines.
• Depth Robustness: While standard GNNs (GCN, HyperGCN) suffered severe performance degradation (over-smoothing) as depth increased to 64 layers, CCMamba maintained high accuracy, demonstrating superior stability.
• Parameter Sensitivity: The model showed robustness to hyperparameters, with optimal performance typically found at a state dimension of 16 and specific cell length limits depending on the dataset topology.

5. Significance

CCMamba represents a paradigm shift in Topological Deep Learning by successfully integrating Selective State-Space Models with Combinatorial Complexes. Its significance lies in:

1. Scalability: It solves the computational bottleneck of attention-based TDL, making higher-order learning feasible for large-scale real-world networks.
2. Unified Theory: It provides a single framework capable of generalizing across diverse topological domains (graphs, hypergraphs, simplicial, cellular), reducing the need for specialized architectures for each structure type.
3. Long-Range Modeling: By leveraging the SSM mechanism, it effectively captures long-range and directional dependencies that traditional local message passing misses, offering a more powerful tool for modeling complex systems like biological networks and social dynamics.

In conclusion, CCMamba establishes a scalable, expressive, and theoretically grounded foundation for the next generation of higher-order graph learning.