CCMamba: 조합론적 복합체에서의 고차 그래프 학습을 위한 선택적 상태 공간 모델

CCMamba: Selective State-Space Models for Higher-Order Graph Learning on Combinatorial Complexes

토폴로지 기반 딥러닝은 표준 그래프 신경망이 포착하지 못하는 쌍대 상호 작용을 넘어선 고차 관계 구조를 모델링하는 데 등장했습니다. 조합론적 복합체는 통일된 토폴로지 프레임워크를 제공하지만, 대부분의 기존 토폴로지 기반 딥러닝 방법은 어텐션 메커니즘을 통한 로컬 메시지 전달에 의존하며, 이는 2차 복잡도를 초래하고 저차원 정보를 유지하여 고차 복합체에서의 확장성과 랭크 정보를 고려한 정보 집계를 제한합니다. 우리는 조합론적 복합체 학습을 위한 최초의 통일된 Mamba 기반 신경망 프레임워크인 Combinatorial Complex Mamba (CCMamba)를 제안합니다. CCMamba는 멀티 랭크의 상관 관계를 구조화된 시퀀스로 구성하여, 랭크 정보를 고려한 상태 공간 모델에 의해 처리되는 선택적 상태 공간 모델링 문제로 메시지 전달을 재구성합니다. 이를 통해 자기 어텐션 없이 선형 시간 내에 적응적이고 방향성 있는 장거리 정보 전파가 가능합니다. 또한, CCMamba 메시지 전달의 표현력 상한이 1-Weisfeiler-Lehman 테스트와 같다는 이론적 분석을 제시합니다. 그래프, 하이퍼그래프, 심플렉스 벤치마크 실험 결과, CCMamba는 기존 방법보다 일관되게 우수한 성능을 보이며, 확장성과 깊이에 대한 강건성도 향상되었습니다.

Topological deep learning has emerged for modeling higher-order relational structures beyond pairwise interactions that standard graph neural networks fail to capture. Although combinatorial complexes offer a unified topological framework, most existing topological deep learning methods rely on local message passing via attention mechanisms, which incur quadratic complexity and remain low-dimensional, limiting scalability and rank-aware information aggregation in higher-order complexes.We propose Combinatorial Complex Mamba (CCMamba), the first unified mamba-based neural framework for learning on combinatorial complexes. 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. This enables adaptive, directional, and long range information propagation in linear time without self attention. We further establish the theoretical analysis that the expressive power upper-bound of CCMamba message passing is the 1-Weisfeiler-Lehman test. Experiments on graph, hypergraph, and simplicial benchmarks demonstrate that CCMamba consistently outperforms existing methods while exhibiting improved scalability and robustness to depth.