- 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?
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.