{"id":"552ca261-c422-4dc6-851e-a0a8cb8fa370","arxiv_id":"2412.08160","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"DG-Mamba combines Mamba state space models, kernelized attention, and a Principle of Relevant Information regularizer to learn robust dynamic graph structures in linear time.","lead":"A new framework, DG-Mamba, learns the hidden structure of time-varying graphs in linear time instead of quadratic time. It combines Mamba-style state space models with kernelized attention and an information-theoretic regularizer to keep link prediction accurate on noisy or attacked graphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(T(|V|+|E|)) headline claim rests on an unanalyzed inter-graph structure query: Appendix B.1 constructs cross-snapshot edges by pairwise cosine similarity and top-k selection, an O(T N^2) step unless an unspecified approximation is used.","rationale":"The reader's PRI concern is legitimate: Proposition 2's equivalence proof relies on Eq. (B.18), where log sums are asserted to vanish without justification, and the KL divergence over non-edges is not well-defined for binary adjacency with zero entries. That flaw undermines the information-theoretic framing of the regularizer, though the ablation still shows the regularizer is empirically beneficial. I consider the complexity concern more load-bearing because it attacks the paper's most distinctive quantitative claim ('first trial in which the spatio-temporal computational complexity of DGSL has been simultaneously reduced to linear') and is directly checkable from the released code. The empirical scaling curves in Figures 3-4 report per-epoch training time and peak GPU usage, so they may not include the one-time inter-graph preprocessing and do not settle the asymptotic claim as written. The central architecture and experiments remain plausible, and the reported near-linear per-epoch scaling suggests the issue is localized to a specific step that could be fixed or explicitly scoped; therefore the existing CONDITIONAL verdict is appropriate, with revision required on the complexity statement.","tokens_in":31517,"tokens_out":9380,"duration_ms":101688,"concrete_test":"Open the released repository (https://github.com/RingBDStack/DG-Mamba), locate the inter-graph structure initialization code, and instrument it to count node-pair dot products or measure wall-clock time while scaling node count N on Yelp or ACT. If the operation count or runtime grows approximately quadratically with N (e.g., roughly 4x when N doubles from 13k to 26k), the O(T(|V|+|E|)) complexity claim in Eq. (24) is not supported as written. If the code instead uses an approximate-nearest-neighbor or data-dependent sparsifier, the missing description should be added and its complexity analyzed; if the pairwise pass is one-time preprocessing, the paper should state that Eq. (24) covers per-epoch cost only.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Eq. (24) claims overall complexity O(T(|V|+|E|)). The load-bearing step is the inter-graph structure query described in Appendix B.1 ('Efficient Structure Query'). The paper states that because no original cross-snapshot edges exist, they 'initialize the cross-graph structures by calculating the cosine similarity between graphs with the initialized node embeddings before training and select the top-k edges where k equals |E|,' then assert this consumes O(T(|V|+|E|)). This inference is not justified. Eq. (10) defines A^t_inter as an N x N matrix over u in V_t and v in V_{t-1}; computing pairwise cosine similarity between consecutive snapshots requires Theta(T N^2 D) operations, and selecting top-k from N^2 scores costs at least Theta(T N^2). No approximate-nearest-neighbor, random-feature, or other subquadratic construction is described for this initialization. Appendix G lists limitations but does not flag this missing complexity analysis. Unless this step is replaced by a genuinely subquadratic construction or explicitly excluded from the complexity statement, the paper's central claim of simultaneous linear spatio-temporal DGSL is unsupported. A secondary internal inconsistency is that Section 4.4 says kernelized message-passing is O(T|V|) while Appendix A says O(2LT(|V|+|E|)D0); that can be reconciled under O(T(|V|+|E|)), but the inter-graph query cannot.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DG-Mamba, a dynamic graph structure learning framework that combines a kernelized message-passing operator with selective state space models and a self-supervised Principle of Relevant Information (PRI) regularizer. The headline claim is that the spatio-temporal complexity of DGSL is reduced to O(T(|V|+|E|)) (Eq. 24) while improving robustness against adversarial attacks. The evaluation covers future link prediction on COLLAB, Yelp, and ACT under non-targeted and targeted attacks, with 12 baselines, ablations, scaling experiments, and a publicly listed repository.","tokens_in":31762,"tokens_out":3856,"duration_ms":42962,"significance":"If the central complexity and robustness claims are correct, this is a useful contribution to dynamic graph structure learning: simultaneous linear scaling in both the spatial and temporal dimensions is stated as a first for DGSL, and the experimental suite is extensive, including clean and attacked settings, sensitivity analyses, and scaling studies. The paper also provides implementation detail and reproducibility artifacts. However, the theoretical appendix contains errors that directly affect the claimed guarantees, so the contribution is not yet established as written.","major_comments":[{"comment":"The overall linear complexity claim is not supported by the described inter-graph structure query. The appendix states that cross-graph structures are initialized by computing cosine similarity between graphs with the initialized node embeddings and selecting the top-k edges where k equals |E|. Computing pairwise cosine similarity between consecutive snapshots requires Θ(T N^2 D) operations, and selecting the top-k from N^2 scores costs at least Ω(T N^2). No subquadratic construction (e.g., random features, locality-sensitive hashing, or approximate nearest neighbors) is described for this step, so the inference that this consumes O(T(|V|+|E|)) is unjustified. The authors must either supply a genuinely subquadratic algorithm for this initialization or explicitly exclude it from the complexity statement; otherwise Eq. (24) is unsupported.","section":"§4.4, Eq. (24); Appendix B.1, “Efficient Structure Query”"},{"comment":"The loss-equivalence proof for the PRI regularizer is invalid. The proof assumes log Σ_{k,l} α^t_{kl} = log Σ_{k,l} α̂^t_{kl} = 0, which requires both adjacency sums to equal 1. In the manuscript, α^t is the original binary adjacency (sum = |E^t|) and α̂^t is a learned attention weight matrix whose total sum is generally not 1 either. Moreover, the conclusion that minimizing the KL divergence is equivalent to maximizing α̂^t_{uv} does not follow from Eq. (B.19) when α̂^t_{uv} ∈ [0,1] and α^t_{uv} ∈ {0,1}, because the quotient α̂^t_{uv}/α^t_{uv} equals 1 only in the boundary case. The claim that L_edge is equivalent to the divergence term is therefore unproven, and the information-theoretic interpretation of PRI should be either corrected or replaced by a direct statement that Eq. (21) is a heuristic likelihood-based regularizer.","section":"Appendix B.2, Proposition 2, Eq. (B.18)"},{"comment":"The empirical analysis of the approximation error bound is mathematically incorrect. The text claims that as ϵ and τ simultaneously approach 0, the fraction exp(6r/τ)/(mϵ²) approaches 0 and hence P(Δ < ϵ) approaches 1. In fact, as τ → 0 the exponential term grows without bound, and as ϵ → 0 the denominator shrinks, so the fraction diverges rather than approaching 0. The displayed inequality in Eq. (B.11) therefore provides no support for the claim that the Gumbel-Softmax kernel approximation error vanishes with high probability. This section must be corrected or removed.","section":"Appendix B.1, “Empirical Analysis” after Eq. (B.11)"}],"minor_comments":[{"comment":"The complexity accounting is internally inconsistent: §4.4 states the kernelized message-passing is O(T|V|) and the structure query is O(T|E|), while Appendix A lists O(2LT(|V|+|E|)D0) for the kernelized message-passing layer and O(2T(|V|+|E|)) for regularizing. These can be reconciled under O(T(|V|+|E|)) after treating dimensions and layer count as constants, but the discrepancy should be addressed so the two accounts agree.","section":"§4.4 vs. Appendix A"},{"comment":"There are numerous typos and spelling errors, including “Lamma 1” (Appendix B.1), “Equivalance” (Appendix B.2 title), “sensitvity” (§5.6), “stuking” (§5.4), “secutive” (Appendix C.3), “gound-truth” (§4.3), and “res cross” (Figure 3 caption). These should be corrected.","section":"Throughout"},{"comment":"The input list in Algorithm 1 names hyperparameters β1, β1, γ, λ, and µ, but the running text and experiments describe β1, β2, λ, and µ; γ is not defined or used elsewhere.","section":"Algorithm 1"},{"comment":"Figure 2 is very dense and the label “HBMSRAM” is unclear; the relationship between the hardware-aware scan and the discretized SSM parameters would be easier to follow with a cleaner diagram or a more explicit caption.","section":"Figure 2"},{"comment":"The equation contains stray “xxxx” padding characters that should be removed.","section":"Appendix B.2, Eq. (B.15)"}],"recommendation":"major_revision","confidential_remarks":"The headline contribution is the linear-complexity claim, and the missing subquadratic analysis for the inter-graph structure query is the most serious issue. The theoretical appendix also contains two demonstrable errors that should be fixed rather than merely annotated. I do not see this as a reject: the empirical study is broad and the framework is plausible, but the central claim cannot be accepted without either a corrected complexity analysis or an amended claim. The authors should be asked to address these points in a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid empirical paper with a shaky theoretical wrapper. The DG-Mamba architecture is a sensible combination of kernelized attention, Mamba-style selective SSM, and an information-bottleneck-like regularizer, and the experiments are extensive. But the headline linear-complexity claim (Eq. 24) does not survive a close read, and two appendix proofs are wrong.\n\nWhat's genuinely new: using the learned inter-graph adjacency to discretize the SSM parameters (A, B, Delta) is a neat idea, and the PRI regularizer, even if it isn't exactly what the proof says, is a reasonable self-supervised regularizer for structure learning. The empirical work is a real strength: 12 baselines, three real datasets, non-targeted and targeted attacks, scaling analysis, ablations, hyperparameter sensitivity. The robustness improvements over DGIB and WinGNN are consistent, and the ablation honestly reports that removing KMP helps clean performance, which is a useful trade-off to know.\n\nWhere it falls down: the complexity claim. Appendix B.1 says the inter-graph structure query initializes cross-snapshot edges by pairwise cosine similarity and top-k selection. That is O(T N^2) per step unless some approximate nearest-neighbor or random-feature method is silently assumed; the paper provides none. The O(T(|V|+|E|)) assertion for this step is unsupported, so the central 'linear DGSL' contribution is not actually established. The empirical scaling results look near-linear, which suggests the implementation may do something smarter, but the paper doesn't say what.\n\nThe theoretical appendix has two further errors. The approximation-error bound claims the RHS of Eq. (B.11) goes to 0 as epsilon and tau both go to 0; but exp(6r/tau) blows up as tau decreases, so the bound is vacuous in the relevant limit. The loss-equivalence proof in B.2 sets log(sum(alpha)) = log(sum(hat alpha)) = 0, which only holds if the adjacency matrices sum to 1; for binary adjacency matrices that is false, so the KL-to-L_edge equivalence is unproven.\n\nNone of this makes the method worthless — the empirical results stand on their own, and the PRI regularizer may be fine as an ad hoc loss. But the paper overclaims on theory and on the linear-complexity guarantee. Both are fixable: either describe a subquadratic inter-graph query or weaken Eq. 24, and correct or remove the flawed proofs.\n\nThis is a paper for people working on DGSL or SSMs on graphs. I'd send it to a serious referee — it is not a desk reject — but I'd expect the authors to tighten the complexity analysis and the appendix before acceptance.","headline":"Good empirical paper with a shaky complexity claim and two broken appendix proofs; the linear-time headline needs a real fix.","tokens_in":32369,"tokens_out":4478,"would_cite":true,"duration_ms":45398,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DG-Mamba claims to reduce dynamic graph structure learning from quadratic to linear time, O(T(|V|+|E|)), while improving robustness against adversarial attacks.","keywords":["dynamic graph structure learning","state space models","Mamba","kernelized attention","positive random features","adversarial robustness","linear complexity","future link prediction"],"falsifier":"Compute the actual KL divergence D(Ĝ||G) on a real dataset (e.g., COLLAB) before and after training with L_edge minimized, and check whether minimizing L_edge actually reduces the true KL divergence; if it does not, the equivalence in Proposition 2 collapses. Alternatively, measure empirical training-time scaling on a dense graph where |E| ≈ |V|^2: if time grows quadratically, the linear-complexity claim fails.","tokens_in":31250,"feed_emoji":"⚡","tokens_out":9573,"duration_ms":77551,"temperature":0.7,"pith_summary":"This paper claims that dynamic graph structure learning — refining the connectivity of a time series of graphs for downstream prediction — can be made both linear-time and more robust to adversarial perturbation. It proposes DG-Mamba, which replaces the quadratic pairwise attention of existing DGSL models with a kernelized message-passing operator that reuses two global sums, and it models the whole dynamic graph as a selective state-space system whose parameters are discretized by the learned cross-snapshot edges. Beyond efficiency, a self-supervised 'Principle of Relevant Information' regularizer is added to maximize the informativeness of the refined structures while minimizing redundancy, which the paper argues is what confers robustness. If the claims hold, DGSL becomes practical for long, large dynamic graphs and a stronger defensive baseline for link prediction under attack.","feed_headline":"DG-Mamba cuts dynamic graph learning to linear time, resists attacks","feed_subtitle":"A kernelized message-passing and selective state-space scan cut quadratic cost and block noise.","key_machinery":"The central object is the kernelized dynamic message-passing operator, built on Positive Random Features (PRF). The softmax attention weight between nodes u and v is replaced by an inner product of random feature maps φ(x) = (1/√m) Σ_i exp(ω_i^T x - ||x||^2/2), which by Mercer's theorem is an unbiased estimator of exp(x^T y). Because the aggregation becomes φ(Wz_u)^T Σ_v φ(Wz_v) Wz_v divided by φ(Wz_u)^T Σ_m φ(Wz_m), the two sums are computed once per node, eliminating the quadratic pairwise cost; the same kernel is queried to extract explicit intra- and inter-graph edge weights for structure refinement. The second piece is the Dynamic Graph Selective Scan, a selective state space model whose discrete parameters A = exp(ΔA), B = (ΔA)^{-1}(A-I)ΔB, and C are functions of the input and of the inter-graph adjacency, so that long-range dependencies are captured with a linear recurrent scan. The third piece is the PRI regularizer, L_PRI = H(Ĝ) + β D(Ĝ||G), decomposed into intra-graph entropy plus edge-level maximum-likelihood loss and inter-graph KL between the state-space output and the message-passing embedding.","core_discovery":"The central discovery is that the quadratic spatio-temporal cost of dynamic graph structure learning — O(T|V|^2) from softmax edge weighting and O($T^{2}$) from step-pair attention — can be collapsed into a linear O(T(|V|+|E|)) pipeline without losing the ability to capture long-range dependencies. DG-Mamba achieves this with (1) a positive-random-feature kernel that approximates the softmax attention so that node-wise sums are computed once and reused, (2) a selective state-space scan where the transition, input, and step-size matrices are functions of the current input and the learned inter-graph adjacency, and (3) an information-theoretic regularizer that balances entropy and KL divergence to filter redundancy. The paper further demonstrates through experiments against 12 baselines that this linear model not only matches but often exceeds the accuracy of quadratic DGSL methods on future link prediction, and retains higher accuracy under both random structure/feature attacks and targeted evasion/poisoning attacks.","pith_inferences":["The ablation shows that removing the kernelized operator slightly improves clean AUC, so there is a tunable trade-off: raising the projection dimension m of the random features approaches full attention at still-subquadratic cost.","If the PRI equivalence proof fails, the regularizer may still be useful as an empirical denoiser, but it should then be reinterpreted as a heuristic penalty rather than an information-theoretic bound; a properly normalized variational bound might restore the theory.","The same discretization trick — parameterizing a state-space model with a learned structure matrix — could transfer to other structured sequence problems, such as traffic forecasting or continuous-time graphs, where edge timings provide another natural discretization.","The paper reports empirical robustness but no guarantees, so a natural next test is certified robustness, e.g., randomized smoothing or a Lipschitz certificate for the learned dynamic structures."],"forward_implications":["DGSL can be applied to large-scale, long-sequence dynamic graphs that previously caused out-of-memory errors in quadratic baselines; the paper shows near-linear scaling up to 8× sequence length.","Long-range temporal dependencies can be captured with a linear recurrent scan instead of pairwise temporal attention, so the model is not limited by the local Markov assumption.","The PRI regularizer provides a self-supervised way to denoise structures, reducing the average relative AUC drop under targeted attacks compared to all 12 baselines.","The kernelized operator makes the learned edge weights explicitly queryable, so intra- and inter-graph structures can be visualized and inspected."],"supporting_citations":[{"why":"Supplies the selective state-space scan and hardware-aware algorithm that give the linear temporal scan.","marker":"Gu and Dao 2023"},{"why":"Provides the Positive Random Features (PRF) used to approximate the softmax kernel and its error bound.","marker":"Choromanski et al. 2020"},{"why":"Contributes the kernelized graph structure learning, Gumbel-Softmax reparameterization, and the efficient structure query used in the message-passing operator.","marker":"Wu et al. 2022"},{"why":"Mercer's theorem guarantees the existence of the feature map φ on which the kernel approximation rests.","marker":"Mercer 1909"},{"why":"Provides the Gumbel-Softmax trick for differentiable discrete structure sampling.","marker":"Jang, Gu, and Poole 2022"},{"why":"Introduces the Principle of Relevant Information that the proposed regularizer is based on.","marker":"Principe 2010"},{"why":"Provides the targeted attack library used to evaluate evasion and poisoning robustness.","marker":"Z¨ugner, Akbarnejad, and G¨unnemann 2018"},{"why":"DGIB is the strongest robust baseline to beat and supplies the information-bottleneck comparison.","marker":"Yuan et al. 2024"}],"fun_headline_variants":["Linear-time dynamic graph learning that resists attacks","DG-Mamba: quadratic to linear in graph learning, stays robust","Attack-resistant graph learning at linear speed","State-space Mamba makes dynamic graph learning linear and robust","DG-Mamba: robust graph learning, no quadratic blowup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that the PRI regularizer equals an edge-level maximum-likelihood loss assumes that the learned and original adjacency matrices each sum to 1, but in practice they do not, so the information-theoretic grounding of the robustness mechanism is unproven.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time dynamic graph learning that resists attacks","DG-Mamba: quadratic to linear in graph learning, stays robust","Attack-resistant graph learning at linear speed","State-space Mamba makes dynamic graph learning linear and robust","DG-Mamba: robust graph learning, no quadratic blowup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1507,"prompt_tokens":1002,"completion_tokens":505,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":427}},"tokens_in":618,"tokens_out":505,"duration_ms":5161,"temperature":1.0,"reasoning_tokens":427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:08:15.106990+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the actual KL divergence D(Ĝ||G) on a real dataset (e.g., COLLAB) before and after training with L_edge minimized, and check whether minimizing L_edge actually reduces the true KL divergence; if it does not, the equivalence in Proposition 2 collapses. Alternatively, measure empirical training-time scaling on a dense graph where |E| ≈ |V|^2: if time grows quadratically, the linear-complexity claim fails.","supporting_citations":[{"cited_title":"M.; Likhosherstov, V.; Dohan, D.; Song, X.; Gane, A.; Sarlos, T.; Hawkins, P.; Davis, J","cited_arxiv_id":null,"evidence_quote":"Provides the Positive Random Features (PRF) used to approximate the softmax kernel and its error bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Gumbel-Softmax trick for differentiable discrete structure sampling."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Principle of Relevant Information that the proposed regularizer is based on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"DGIB is the strongest robust baseline to beat and supplies the information-bottleneck comparison."}],"review_version":1}