- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies how to adapt selective state-space models to combinatorial complexes, where cells do not have a natural ordering. It proposes CCMamba with two variants: CCMamba-S uses bidirectional Mamba scans over an imposed rank-wise ordering and therefore remains order-sensitive, while CCMamba-K replaces the scan with incidence-based structural kernel mixing, making it permutation equivariant. The paper provides theoretical results on order sensitivity, equivariance, and a conditional connection to 1-CCWL, and evaluates the models across graph and higher-order benchmarks with several ablation and efficiency studies.
Critical strengths
- The permutation experiments are a clear strength. They directly test the main distinction between the two variants: CCMamba-S remains sensitive to the imposed ordering, while CCMamba-K is permutation equivariant up to numerical precision.
- The experimental evaluation is broad and includes useful ablations. The paper covers graphs, hypergraphs, simplicial and cellular complexes, as well as native higher-order datasets. The matched-mixer ablation is particularly useful because it compares CCMamba-K with message-passing and attention-based alternatives under a controlled setup.
Critical weaknesses
- My main concern is the novelty relative to closely related work. The ordering problem in Graph Mamba is already well known. For example, Behrouz and Hashemi (2024) already use graph-dependent ordering together with bidirectional state-space processing. TopoMamba (Montagna et al., 2025) also applies Mamba-style state-space modeling to simplicial complexes. More importantly, Huang, Miao, and Li (2024) already study the lack of a canonical ordering for graphs and propose permutation-equivariant aggregation based on factorized graph kernels. In this context, CCMamba-S seems mainly to extend existing Graph Mamba ideas to a rank-aware combinatorial-complex setting. CCMamba-K is more distinctive because of the combination of multi-rank incidence support, structural gating, and factorized kernel interactions, but I think the paper should explain much more clearly how this differs from the approach of Huang et al. and from generalized combinatorial-complex architectures such as TopoTune (Papillon et al., 2025).
The most relevant references are:
- Ali Behrouz and Farnoosh Hashemi. “Graph Mamba: Towards Learning on Graphs with State Space Models.” Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 119–130, 2024.
- Yinan Huang, Siqi Miao, and Pan Li. “What Can We Learn from State Space Models for Machine Learning on Graphs?” arXiv preprint arXiv:2406.05815, 2024.
- Marco Montagna, Simone Scardapane, and Lev Telyatnikov. “Topological Deep Learning with State-Space Models: A Mamba Approach for Simplicial Complexes.” 2025 International Joint Conference on Neural Networks (IJCNN), pp. 1–8, IEEE, 2025.
- Mathilde Papillon, Guillermo Bernardez, Claudio Battiloro, and Nina Miolane. “TopoTune: A Framework for Generalized Combinatorial Complex Neural Networks.” International Conference on Machine Learning, 2025.
- I am also not fully convinced by the long-range/state-space framing of CCMamba-K. The K variant is not a selective SSM block, and its neighborhood is restricted to immediate incidence relations, so longer-range information still requires stacking multiple layers. I therefore think the paper should be more precise about which advantages associated with state-space models are actually retained by CCMamba-K. The 1-CCWL result is also proved for an idealized version of the model under several assumptions, including injective mappings and a simplified aggregation setting, so I think its implications for the practical architecture should be stated more carefully.
- The battery of experiments is vast, but the gains are overall incremental, on mostly saturated benchmarks, excluding Mantra.
Questions for authors
- The main point I would like clarified is the relation between CCMamba-K and GSSC (Huang, Miao, and Li, 2024). Both approaches address the lack of a canonical ordering by moving away from purely sequential processing and using factorized, permutation-equivariant interactions. What is the main methodological difference between CCMamba-K and a GSSC-style kernel mixer applied over combinatorial-complex incidence relations? In particular, what does CCMamba-K enable that could not be obtained by combining the GSSC idea with an existing combinatorial-complex architecture?
- What exactly is meant by long-range modeling in CCMamba-K? As I understand it, the K variant only mixes over immediate incidence neighborhoods, so information from more distant cells is obtained by stacking layers. If this is correct, I think the distinction between the long-range behavior of CCMamba-S and the local mixing of CCMamba-K should be made clearer. If CCMamba-K has a different mechanism for capturing non-local information, could the authors clarify it?
- Could the authors clarify the scope of the 1-CCWL result for the practical CCMamba-K model? The theoretical result is proved under an idealized setting with assumptions such as simplified structural coefficients and injective mappings. Moreover, the correlation between WL expressivity and downstream performance seems to be fundamentally refuted by recent literature. How directly should this result be interpreted as a statement about the learned model used in the experiments?
- Could the authors clarify the experimental protocol? In the appendix, different seed sets seem to be reported in different places, and some of the default lifting choices do not appear to match exactly the corresponding results in the main tables and lifting ablations. Which seeds and lifting configurations were used for the final reported numbers? C.1 reports seeds {0,3,5,7,9}, whereas C.4 reports {1,3,5,7,9}; moreover, C.4 specifies KHop and Clique as the default hypergraph/simplex lifts, but the corresponding values in Table D.2 do not match the main Table 1 values.
- Tables 2 and 3 are clearly not adhering to the correct paper format.
Overall, given the idea, this paper is well written and tested. However, the idea per se is simple, partly incremental and the battery of experiments is exhaustive but not particularly insightful or modern in terms of employed benchmarks.
5 comments
Part 2/3
W2/Q2:What exactly is meant by long-range modeling in CCMamba-K?...,the distinction between the long-range behavior of CCMamba-S and the local mixing of CCMamba-K should be made clearer.
We thank the reviewer for highlighting the need to clarify how information propagates in the two variants.
(1)Distinction between CCMamba-S and CCMamba-K. CCMamba-S retains genuine bidirectional selective SSM recurrence and efficient fused scanning, enabling information propagation across rank-specific cell sequences within a single scan block, although its representations remain order-sensitive. In contrast, CCMamba-K does not retain selective SSM recurrence, fused scanning, or single-layer global propagation. Instead, it employs permutation-equivariant, incidence-supported factorized kernel mixing. Its computational efficiency arises from sparse structural aggregation rather than state-space recurrence.
(2)What does long-range modeling mean in CCMamba-K? We agree that CCMamba-K directly mixes information only within immediate adjacent-rank incidence neighborhoods: $ \mathcal N(\sigma)= \mathcal N_{k-1\rightarrow k}(\sigma) \cup \mathcal N_{k+1\rightarrow k}(\sigma)$. Stacking layers allows information from more distant cells to reach . Higher-order lifting can also shorten paths by introducing additional incidence relations. A single kernel mixer remains local to its incidence neighborhood. Our depth-sensitivity study evaluates 2–64 layers across graph, hypergraph, simplicial, and cellular representations (Appendix E.6, Fig. E.1). The table shows CCMamba-K test accuracy (%) on CiteSeer.
| Topology | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|
| Graph | 72.89 | 73.13 | 72.56 | 71.57 | 71.04 | 71.40 |
| Hypergraph | 70.54 | 69.84 | 70.18 | 70.20 | 70.95 | 70.83 |
| Simplex | 74.29 | 73.33 | 72.82 | 73.83 | 73.83 | 73.83 |
| Cellular | 74.86 | 75.37 | 74.43 | 74.17 | 74.07 | 73.21 |
We have explicitly clarified this distinction in the revised Related Work (Appendix B, Table B.1 and the accompanying discussion) and reiterated it in Section 6. CCMamba-S provides rank-wise sequence-global selective scanning, whereas CCMamba-K performs incidence-local structural mixing with depth-dependent multi-hop propagation.
W2/Q3:Could the authors clarify the scope of the 1-CCWL result for the practical CCMamba-K model?..., the correlation between WL expressivity and downstream performance seems to be fundamentally refuted by recent literature. How directly should this result be interpreted as a statement about the learned model used in the experiments?
We thank the reviewer for highlighting the distinction between idealized theoretical expressivity and the realized expressive power of the practical CCMamba-K model.
(1)Scope of the 1-CCWL result. Conventional Mamba relies on order-dependent selective scans, which do not guarantee permutation equivariance and do not directly admit a standard WL-style multiset analysis. CCMamba-K aggregates over unordered incidence neighborhoods. Its index-free, permutation-equivariant updates permit a multiset-based analysis. Theorem 1 establishes that an idealized CCMamba-K specialization matches the distinguishing power of 1-CCWL under the stated assumptions, including the following.
| Property | Idealized CCMamba-K | Practical CCMamba-K |
|---|---|---|
| Structural coefficients(Theorem 1) | Learned structural gating | |
| Kernel representation(Lemma 5, Fig. E.2) | Injective multiset embedding | Finite-dimensional feature mapping |
| Aggregation (Table E.9) | Unnormalized retained | Structural aggregation with learned coefficients |
| Update, Readout(Theorem 1) | Assumed injective | Learned MLP, injectivity not guaranteed |
| Expressivity(Appendix C.4) | Conditional 1-CCWL matching | No unconditional matching guarantee |
Importantly, permutation equivariance enables the structural multiset analysis but does not guarantee 1-CCWL matching, which additionally requires injectivity and specific aggregation assumptions. We have clarified these limitations in Section 4 and Appendix C.4.
(2) Relationship Between WL Expressivity and Downstream Performance. Appendix E.4 evaluates downstream accuracy and structural discrimination separately. Table E.7 compares CCMamba with 12 expressive GNN baselines across ten graph benchmarks. In Table E.8, CCMamba-K separates 6.25% of BREC pairs and 9.20% of SR25 pairs, compared with 0% on both for the evaluated GIN baseline. On CSL, it achieves 11.60% classification accuracy, close to the 10% chance level. These results show a modest discrimination advantage over GIN on the two pair-separation benchmarks.
We agree that stronger WL distinguishability does not necessarily imply better downstream predictive performance or generalization (Franks et al., 2024; Maskey et al., 2026). We distinguish theoretical structural discrimination from empirical predictive utility. Line2039 reports these experiment is the evidence for the benefit of incidence-aware higher-order representation rather than stronger expressive power.
Part 3/3
W3: The battery of experiments is vast, but the gains are overall incremental, on mostly saturated benchmarks, excluding Mantra.
We thank the reviewer for this fair assessment, and we agree with part of it. On mature, near-saturated benchmarks (e.g., PubMed, Minesweeper, Roman-Empire), differences between CCMamba and the strongest baselines are small relative to seed variance, and we do not claim otherwise. We address this concern in two respects.
(1)Statistical Significance. We have strengthened the evaluation with paired statistical tests and Holm correction for multiple comparisons(Appendix E.8, Tables E.10–E.11) Significant differences are marked with , and for adjusted (p<0.05), (p<0.01), and (p<0.001), respectively, while non-significant comparisons are explicitly identified.
For example, the supplementary comparisons provide statistical support for CCMamba-S on 20NewsW100 and IMDB-B.
| Domain/Dataset | Baseline | CCMamba | Gain (pp) | Adjusted p | Sig. |
|---|---|---|---|---|---|
| Hypergraph/20NewsW100 | HJRL: 80.88±0.22 | CCMamba-S: 81.47±0.31 | +0.59 | 0.0022 | ** ↑ |
| Hypergraph/20NewsW100 | HJRL: 80.88±0.22 | CCMamba-K: 82.09±0.63 | +1.21 | 0.0198 | * ↑ |
| Graph/IMDB-B | GraphGPS: 72.35±2.60 | CCMamba-S: 73.20±3.56 | +0.85 | 0.0340 | * ↑ |
Interpretation of Incremental Gains. These results confirm that performance differences are dataset-dependent: some modest improvements receive statistical support, while others are not significant, and certain comparisons favor the baselines. We therefore do not claim consistent or substantial improvements across saturated benchmarks.
(2)Scope of claims. We do not claim consistent accuracy gains on saturated benchmarks. Our contributions are the order-sensitivity analysis of causal scans, a permutation-equivariant incidence-supported mixer with conditional expressivity analysis, and favorable memory/runtime scaling. We have revised Section 5 to state that gains on saturated benchmarks are within variance and to foreground the MANTRA, hypergraph, and efficiency results. Larger native combinatorial-complex benchmarks remain needed (Section 6, Appendix F).
Q4: Could the authors clarify the experimental protocol? In the appendix, different seed sets appear to be reported in different places, and some of the default lifting choices do not appear to match exactly the corresponding results in the main tables and lifting ablations...
We thank the reviewer for identifying these inconsistencies. We have standardized the training seeds to {1, 3, 5, 7, 9} throughout the manuscript and clarified the distinction between training seeds and data-split seeds. For graph-origin benchmarks, all methods use matched data partitions, with training randomness controlled by the five reported seeds. Native hypergraph benchmarks follow their dataset-specific splitting protocols, with the same partitions shared across the compared methods.
We also clarify that the default graph-to-complex lifting configurations are KHop for hypergraphs, Clique for simplicial complexes, and Cycle for cellular complexes. We have corrected the default-lifting entries in Appendix E.2 (Table E.5) to match the corresponding CCMamba-S results in Table 1 across all ten graph-origin benchmarks.
Q5: Tables 2 and 3 are clearly not adhering to the correct paper format.
We thank the reviewer for pointing out the formatting issues. We have reformatted Tables 2 and 3 to comply with the ICLR guidelines and improve readability. We reorganized Table 2 by moving selected benchmarks to the appendix and adjusted the layout, spacing, and alignment of both tables while preserving the original results.
We hope this response addresses your concerns. If our clarifications address your question, we would sincerely appreciate your reconsideration of the score. Otherwise, we remain happy to discuss further.
Part 1/3
We thank the reviewer for highlighting these connections. We address this concern in four respects.
(1)Methodological novelty and relation to prior work. Graph Mamba (Behrouz and Hashemi, 2024) combines graph-dependent tokenization and ordering with bidirectional selective SSMs. TopoMamba (Montagna et al., 2025) constructs node-specific sequences from rank-wise summaries of incident simplices. GSSC (Huang et al., 2024) achieves global, permutation-equivariant graph aggregation through factorized spectral kernels. TopoTune (Papillon et al., 2025) provides a general framework for combining configurable CC neighborhoods with neural network backbones.
CCMamba-S extends selective recurrence to multi-rank cell representations through incidence lifting and rank-specific scans. CCMamba-K uses incidence relations directly in the mixing weights, as detailed below. Appendix B (Table B.1) summarizes these distinctions.
(2) What distinguishes CCMamba-K from GSSC and GSSC-TopoTune?
In GSSC, Laplacian-derived representations zu and zv determine the structural kernel for global graph aggregation. Its update can be written schematically as:
hu=v∈V∑spectral structural kernel⟨zuWQ,zvWK⟩d⊙WOxv+Self(u).GSSC-TopoTune incorporates the GSSC mixer into TopoTune's relational framework.
In contrast, CCMamba-K defines interactions directly over typed adjacent-rank incidence neighborhoods. Its value-weighted mixing matrix is
MCCMamba−K=LCC(X)⊙(ΨQΨK⊤),
and its cell-wise update is:
h_\sigma = \left[ \sum_{\tau\in\mathcal N(\sigma)} a_{\sigma\tau} \psi(q_\sigma)^\top\psi(k_\tau)v_\tau \\;\middle\\|\\; z_\sigma \right].Here, LCC(X) encodes typed adjacent-rank incidence support and learned structural coefficients, while ΨQΨK⊤ represents factorized content-dependent kernel interactions. The second output block zσ retains the uncontracted neighborhood key aggregate.
(3) Direct empirical comparison with GSSC-TopoTune. We implemented GSSC-TopoTune by incorporating the GSSC mixer into TopoTune and evaluated it alongside the methods below. We report accuracy(%) for classification and PM25CC (MAE↓). Here, “—” indicates that the model cannot be directly applied to this structure.
CCMamba-K achieves higher mean accuracy than GSSC-TopoTune with absolute improvements of 10.10, 9.65, and 20.79 percentage points on House, Citation-Cora, and MANTRA Genus, respectively. However, GSSC-TopoTune performs better on PROTEINS.
(4)Matched Mixer Ablation. To control for differences in lifting and relational inputs, we also compared the mixers under shared incidence support and experimental settings. In this comparison, CCMamba-K achieved higher mean accuracy than Incidence-GSSC on all four datasets, with gains of 3.05–4.25 percentage points. We moved this ablation to the main text (Table 4).