acceptodds
Under review as a conference paper at ICLR 2027

DAG-MAMBA: Structure-aware selectivity for directed acyclic graphs State space model

Abstract

The directed acyclic graph (DAG) induces a partial order, but does not induce a unique node sequence, which causes a structural mismatch between it and the order-sensitive state space model (SSM). Arbitrary topological serialization may make the loop model depend on the relative order of incomparable nodes, even if the order is not part of the graph. We study how to align order-sensitive sequence models with DAGs without committing to an arbitrary linear extension. We propose \method, a sequential robust structural interface, which separates the node-level dependency information from the coarse-grained depth sequence. The local and bounded reachability branches retain the direct relationship and the predecessor-follower relationship, and the nodes with the same longest path depth are pooled into a norm-front token sequence ; we then use Mamba as a learned cross-frontier mixer. The frontier represents that the node index and the selected topology order remain unchanged, but is intentionally designed to be non-injective, so it complements rather than replaces the graph structure. On the code, reference, and neural architecture DAG, complete instantiation is significantly superior to sequential naive Mamba on several tasks and remains competitive with strong graph/DAG baselines. A diagnostic ablation further demonstrated that replacing the learned Mamba transfer with an identical leading-edge mixer on three ablation tasks could match or exceed the complete model. This distinguishes two confusing effects : sequential robustness is provided by the DAG interface, and the marginal value of the learned cross-frontier loop depends on the task. Therefore, we position \method as a Mamba instantiation of a sequential robust DAG interface, rather than as evidence that selective scanning is generally necessary for DAG learning. The simulation code can be obtained in https://github.com/zongjin130/DAG-MAMBA.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
DAG-MAMBA, Selective State Space Model, Directed Acyclic Graph (DAG), Structure-aware Representation, Long-range Dependency Modeling, Graph Representation Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ALwmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces DAG-Mamba, an order-robust structural interface bridging the partial-order structure of directed acyclic graphs (DAGs) and order-sensitive state space models. The framework separates node-level dependency information from a coarse-grained depth sequence. Experiments show that this interface outperforms vanilla Mamba across multiple DAG tasks.

Critical strengths

The structural interface is thoughtfully tailored to the core challenge. By using permutation-invariant depth frontiers to form a global sequence while leaning on local-edge and bounded-reachability branches for node-level dependencies, the design strikes a smart balance between order robustness and structural preservation.

The theoretical analysis provides a clear picture of what the frontier representation can and cannot do, while proving that this compression doesn't uniquely determine the original graph highlights precisely why those extra node-level structural branches are necessary.

Critical weaknesses

The independent contribution of the Mamba transformation is not well supported. Table 5 shows that an identity mixer matching the structural interface performs as well as or better than the full model across all tasks, meaning the experiments do not establish Mamba as a necessary source of performance gains.

The efficiency advantage of the full model remains unverified. Although frontier mixing scales linearly, the reachability component can reach quadratic worst-case complexity, and the paper lacks a direct runtime comparison against strong baselines under matched conditions.

Questions for authors

In Table 5, the identity mixer manages to match or even outperform the full model. Could the authors shed some light on why the learned Mamba transformation doesn't seem to deliver consistent performance gains?

Under node relabeling, does the full model preserve the exact same graph-level output while ensuring that the node-level outputs shift accordingly? Also, when using different valid topological orderings, do both the graph-level output and the node-level outputs (aligned back to original node identities) remain completely invariant?

1 comment
AuthorsOpenReview ↗

Response to Reviewer ALwm

We thank the reviewer for pointing out that this ablation should be explained more precisely. Table 5 compares the full model with the identity-mixer variant, which retains the structural interface but removes the learned cross-depth mixing. Averaged over multiple seeds, the identity variant performs better on the listed metrics: on Code2, validation/test F1 is 0.1855/0.2034, versus 0.1813/0.2020 for the full model; on NA, RMSE/Pearson is 0.2521/0.9667, versus 0.2689/0.9617 for the full model; on self-citation, AP/AUC is 0.6598/0.8369, versus 0.6402/0.8302 for the full model.

These results indicate that the structural interface alone can work effectively; the incremental effect of the learned cross-depth mixing is task-dependent and is not consistently positive across all tasks. Our contribution is the structural interface that organizes DAG information into depth frontiers while preserving node-level structural pathways; Mamba is the learnable cross-depth transformation within this interface, and its scope will be more precisely defined in the revised manuscript. We will explicitly distinguish the contribution of the structural interface from the task-dependent effects of the Mamba transformation, and report the relevant results as multi-seed mean ± standard deviation.

Major weakness 2: The scope of the efficiency advantage claim needs to be clarified.

Response: We agree that complexity analysis and measured runtime are claims at different levels. The efficiency discussion in this paper is positioned as a per-component complexity analysis, rather than an end-to-end measured runtime or memory comparison. Frontier mixing operates on depth-frontier sequences; reachability computation may require quadratic work or storage in the worst case, i.e., O(n^2).

We will clearly state the worst-case cost of reachability in the revised manuscript and limit the efficiency discussion to component-level complexity characterization. End-to-end runtime, throughput, and peak memory comparisons will be part of follow-up experimental work, and we will not make empirical speedup claims in this paper. This will align the efficiency claims with what the analysis establishes.

Question 1: Why does the learned Mamba transformation not yield consistent gains?

Response: The multi-seed results for identity-mixer indicate that the structural representation and node-level structural pathways already provide useful information for these tasks; the incremental benefit of the learned cross-depth transformation varies by task. A reasonable explanation is that, once local information and reachability information are available, some tasks benefit less from additional cross-depth mixing. The current multi-seed results support that this effect is task-dependent; the mechanistic explanation is still offered as a hypothesis. The revised manuscript will make clear that Mamba is a learnable component in the architecture, and its benefits need to be evaluated in light of the specific task structure.

Question 2: Are graph-level and node-level outputs invariant under node relabeling and different valid topological orderings?

Response: These properties should be distinguished. Under consistent node relabeling, graph-level invariance means that graph predictions remain unchanged; node-level equivariance means that node predictions are permuted in the same way and, after alignment to the original node identities, match the original predictions.

Our depth-frontier construction uses set-based pooling, so the frontier representation is insensitive to the order of nodes within a frontier; the frontier sequence is then organized by depth. This is a concrete source of order robustness at the representation level. The end-to-end ordering properties of the full model need to be defined in light of the specific implementation; the revised manuscript will limit the statement to the properties supported by the frontier interface: the frontier interface eliminates dependence on arbitrary within-frontier order, and this will be distinguished from statements about the end-to-end properties of the full model.

Reviewer_FcDROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper groups nodes in a directed acyclic graph (DAG) by depth, pools each group into a token, and applies Mamba to the resulting sequence. Local and reachability aggregation provide additional graph structure. The goal is to avoid dependence on arbitrary topological ordering.

Critical strengths
  1. The motivation makes sense. A DAG can have several valid topological orders, and grouping nodes by depth gives the sequence model a consistent input. The paper also explains the assumptions needed for this invariance.

  2. The three branches have clear roles. The frontier branch provides context across depth levels, while the local and reachability branches process more detailed node relationships. This is a sensible design given the structural information lost through pooling.

  3. The experiments cover several types of tasks and include useful ablations. Replacing Mamba with an identity mapping helps separate the effect of depth pooling from sequence mixing. The authors are also upfront about the cases where Mamba does not help.

Critical weaknesses
  1. The ablations leave the added value of the frontier branch unclear. Identity matches or beats Mamba, and removing the branch remains competitive on two tasks. I would like to see which kinds of graphs actually benefit from frontier pooling or mixing across depth levels.

  2. The experiments do not directly test the ordering issue that motivates the paper. Running the same graph under several valid topological orders would show how much this affects the baselines. The ordering used by the plain Mamba baseline also needs to be explained.

  3. Some reported numbers need clarification. All nine “±” values in Table 6 match the earlier DAG-Transformer paper despite different means, and the full-model results differ between the main tables and the ablations. The authors should explain these numbers and provide the training settings, run counts, and individual-run results.

Questions for authors
  1. Given the identity and no-frontier results, when does frontier pooling help, and what does Mamba add beyond it? Can you explain whether these benefits depend on graph depth or frontier width?

  2. Which topological ordering is used for the plain Mamba baseline? How much do its predictions and performance change when the same graph is presented in different valid orders?

  3. Why do all nine uncertainty values in Table 6 match the earlier DAG-Transformer results? Please clarify what “±” represents and provide the individual-run results. Also, what configuration differences explain the full-model results across the main and ablation tables?

1 comment
AuthorsOpenReview ↗

Response to Reviewer FcDR

We thank the reviewer for the detailed and constructive feedback. These comments identify places where our description could be more complete and where the reporting conventions in the ablation table need to be unified. We agree that the scope of the relevant claims needs to be defined more precisely. We already have multi-seed run results; this response is based on re-checking and unifying the statistical reporting against the existing multi-seed records, and no new experiments are added.

  1. Interpretation of frontier and component ablations

We agree that the original discussion of the role of frontier scanning could be more precise. DAG-MAMBA combines direct-edge local aggregation, reachability propagation conditioned on hop distance and direction, and depth-frontier state propagation with node-conditioned readout. The identity_scan ablation retains frontier packing and readout but replaces selective scanning, so its intent is to isolate the contribution of scanning under this representation. Our multi-seed ablation results show that this effect is task-dependent; accordingly, we will limit the conclusion to task-dependent component evidence and report the number of seeds, mean, and standard deviation for each entry in the revision, without making claims of general necessity.

  1. Topological ordering in the vanilla Mamba baseline

We agree that the original manuscript’s description of the node ordering used by the vanilla Mamba baseline could be more complete. In the revision, we will add a description of the ordering setting for this baseline and clarify how it differs from the longest-path depth ordering used in the DAGGraphMamba implementation. Comparisons across topological orderings will be limited to the controlled scope currently supported; the order-sensitivity analysis will be treated as a follow-up extension, and the applicable scope of the current comparison will be stated explicitly in the text.

  1. Consistency of the reported standard deviations with the full-model row

We thank the reviewer for pointing out this issue. We have checked the multi-seed run records: some ± entries did not correspond item by item to the multi-seed run records for DAG-MAMBA and have been corrected according to the run records. For k-sweep or ablation entries that can be matched to existing multi-seed run records, we will report the number of seeds, mean, and standard deviation; all statistics are summarized from multi-seed run records, and standard deviations are not inferred from means or from other papers.

We have also unified the full-model entries in the main table and the ablation table. The NA entry is unified to the retained multi-seed summary values 0.2689 / 0.9617; the full-model rows for Code2 and self-citation have also been aligned with the retained multi-seed run records. The revised tables will explicitly state the number of seeds and the aggregation method, so that the reporting conventions of the main table and the ablation table are consistent.

We agree that these corrections make the statistical reporting clearer. The revised manuscript will report our results as multi-seed mean ± standard deviation and will state the component ablation conclusions according to the strength of the evidence.

Reviewer_5i3wOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper groups DAG nodes by longest-path depth and pools each group into a frontier token. Mamba processes the resulting sequence, while local and reachability branches retain node-level structure. The method improves over plain Mamba on several tasks. However, the identity-mixer variant achieves better mean results in the reported ablations.

Critical strengths
  1. The motivation is clear. Different valid topological orderings can affect sequence models. The frontier construction removes this arbitrary ordering dependence.
  2. The authors acknowledge the information lost through frontier pooling. They also provide informative ablations and openly discuss the limited benefits of Mamba.
Critical weaknesses
  1. Limited methodological novelty. The theoretical results largely follow from depth grouping and invariant pooling. The added value over existing depth- and reachability-aware DAG encoders remains unclear.

  2. Limited support for sequence modeling. In Table 5, the identity mixer achieves better mean results than the full model across all reported metrics. These results support same-depth aggregation more directly than learned cross-depth recurrence. The authors acknowledge this limitation, but the broader value of the sequence interface remains unclear.

  3. Insufficient implementation details. The aggregation, pooling, fusion, and training settings are not fully specified. The full model’s NA RMSE is 0.313 in Table 4 and 0.2689 in Table 5. The settings behind these results need clarification.

  4. The paper may violate the double-blind policy, as its GitHub link appears to reveal author-identifying information.

Questions for authors
  1. Given the identity-mixer results, how do the authors distinguish the benefits of same-depth aggregation from those of cross-depth sequence modeling?
  2. Which settings differ between the main experiments and the ablations? What accounts for the difference in NA results?
  3. What specific operators implement LocalAgg, ReachAgg, Pool, and Fuse? Which implementation choices and hyperparameters remain fixed across tasks and ablations?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 5i3w

  1. Methodological contribution and relation to existing DAG encoders

We agree that depth grouping, permutation-invariant pooling, and reachability have foundations in prior work. Our contribution is organizing them into a structural interface for order-sensitive sequence models. Local and reachability branches operate at node granularity, while invariant pooling constructs a depth-indexed sequence for the global mixer. This sequence does not depend on the arbitrary ordering among incomparable nodes in a valid topological serialization. The frontier representation is deliberately non-injective: it is a coarse summary rather than a complete encoding, motivating the retention of node-level branches. We will strengthen this distinction and present our theoretical results as a characterization of invariance and information loss, not as evidence of a completely new representation or generally stronger expressive power.

  1. Same-depth aggregation and cross-depth modeling—response to Question 1

We agree with your reading of Table 5. Multi-seed averages of the identity mixer are better than the full Mamba mixer, not supporting consistent gains from the learned cross-depth recurrence. The identity control retains frontier construction, pooling, node-level branches, and fusion, removing only the learned cross-depth transition. Thus, full-vs-identity tests the Mamba transformation, while identity-vs-no-frontier examines the pooled frontier pathway.

On Code2, identity achieves F1 0.2034, no-frontier 0.1993, and full Mamba 0.2020. This supports the frontier pathway but not its dependence on Mamba. On NA, identity and no-frontier get RMSE 0.2521 and 0.2518, better than full (0.2689). We will report mean ± standard deviation and interpret cautiously. We narrow our conclusion: results support the structural interface more than the learned recurrence; Mamba’s benefit is task-dependent. Optimization explanations remain hypotheses.

  1. NA discrepancy, experimental setup, and operator definitions—response to Questions 2 and 3

Thank you for noting the NA inconsistency. The final implementation reports RMSE 0.2689 and Pearson 0.9617. The 0.313 / 0.947 values were from an earlier, unfinalized implementation on another machine. We will remove the early value from final comparisons and update the text. Main and ablation tables will report identical final model results, avoiding comparisons across implementation versions. Code is in the supplement.

Abstract operator names are insufficient. In the current Code2 implementation:

LocalAgg: edge-type embeddings and GINE-style messages, aggregation, MLP, dropout, and layer normalization.

ReachAgg: gated messages conditioned on source/target features, hop distance, and direction (aggregated separately), followed by MLP.

Pool: permutation-invariant within-depth pooling (1-4 slots: all-node mean/max, attributed-node mean, sink mean).

Fuse: combines updates via learned branch scales, residuals, and layer normalization; node-conditioned weights handle multiple frontier slots.

We will clarify configurations to distinguish shared architecture from task adapters and training settings. We will document all controlled ablation settings and reconcile "one token per frontier" with the configurable pooling.

  1. Repository link containing author-identifying information

Thank you. We have removed the author-identifying URL and checked the supplement. Code for anonymous review will use an anonymized version. We understand removal does not eliminate prior exposure; the previous link was an anonymized entry point without author-identifying information.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.