acceptodds
Under review as a conference paper at ICLR 2027

Successful Constraint Optimization Need Not Certify Structural Fidelity: A Verification Gap in Graph Structure Learning

Abstract

Graph structure learning methods often adapt graph structure from data while incorporating predefined graphs, structural priors, or constraint-based objectives. When a learned graph is claimed to realize a specific external structural target, however, optimization success raises a separate verification question: do the optimized and reported quantities actually certify fidelity to that target? We study this question in a controlled declared-target setting. An external graph \(A^*\) guides a warmup phase; thereafter, the main non-oracle training arms continue without allowing \(A^*\) to influence graph updates, while \(A^*\) is retained for structural audit. Within the Hinge runs on the primary traffic networks, the residual proxy decreases by more than 98% from the warmup boundary and approaches zero. At the final epoch, paired Hinge–ReLU task-error differences remain small, whereas evaluation-only structural audits show lower target fidelity under Hinge than under ReLU. This lower-target-fidelity pattern replicates across four amortized graph learners and multiple traffic networks. We further characterize when surrogate near-optimality can certify proximity to the declared target and isolate two distinct failure points: the constraint interface may lack sufficient target-discriminating information, or the realized graph updates may move in a structurally unfavorable direction. An \(A^*\)-dependent oracle gradient intervention consistently improves local structural quantities but does not reliably restore global edge ranking. This recovery boundary motivates limiting post-warmup deviation from a high-fidelity warmup anchor without requiring \(A^*\) for subsequent non-oracle updates. The resulting guardrail substantially limits structural drift relative to unconstrained continued training; under a controlled fixed-support shift, it retains more structural fidelity than unconstrained adaptation while adapting better than freezing. Thus, task-side behavior and successful surrogate optimization do not, by themselves, certify fidelity to a declared external target. Such claims require direct structural evidence or a demonstrated certificate linking the reported quantities to that target.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph structure learning, structural verification, constraint-guided learning, neuro-symbolic learning, 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 4 reviews, above 27% of the others.
Reviewer_xuqbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper examines whether successful constraint optimization in graph structure learning guarantees that the learned graph remains faithful to a predefined structural target. The authors distinguish between constraint satisfaction, predictive performance, and structural fidelity, arguing that improvements in the first two do not necessarily establish the third. It introduces a diagnostic framework based on Calibration and Route, identifying insufficient target-discriminating information and unfavorable optimization directions as potential causes of structural degradation. It also proposes a warmup-anchor guardrail to limit structural drift during training. Experiments across traffic networks and controlled synthetic settings demonstrate a mismatch between optimization success and structural fidelity. Although the proposed guardrail improves structural preservation, the results also reveal limitations in practical graph dependence and adaptation.

Critical strengths
  1. The paper raises a meaningful concern regarding the interpretation of learned graph structures. I appreciate the clear separation between surrogate optimization, predictive accuracy, and structural fidelity. The Calibration and Route framework provides a useful way to organize the potential sources of failure, and the controlled interventions help illustrate these mechanisms.

  2. The authors conduct paired-seed comparisons across multiple graph parameterizations and traffic networks. Figure 1 provides convincing evidence that the Hinge constraint proxy can decrease substantially while structural fidelity deteriorates relative to the ReLU alternative.

Critical weaknesses
  1. My primary concern is that the main conclusion that minimizing a surrogate objective does not guarantee recovery of an external structural target is a fairly general consequence of optimizing an objective that does not uniquely identify that target. Proposition 1 formalizes structural calibration, but its characterization follows directly from the definition of the calibration margin. Similarly, the interface-equivalence result is an intuitive identifiability limitation. Moreover, the Hinge objective is explicitly described as a residual-based surrogate rather than a direct adjacency-fidelity objective. Therefore, its failure to recover the external road graph is not entirely surprising. The paper would benefit from identifying a stronger graph-specific theoretical result that goes beyond this general observation.

  2. The evaluation measures structural properties against predefined graphs, particularly physical road-network adjacencies. However, the graph that best supports prediction need not coincide with the physical connectivity graph. This distinction becomes especially important because the paper's own graph-dependence controls provide limited support for the necessity of exact reference-edge identities. In Appendix F.12, the Graph-On model does not consistently outperform the degree preserving graph identity control, and the corresponding real data experiment is explicitly blocked. Similarly, the paper reports weak graph dependence in the METR-LA setting.

  3. The warmup-anchor guardrail is a reasonable preservation strategy, but its main mechanism is to restrict graph updates around a previously learned structure. This is conceptually close to standard anchoring or trust-region regularization. The results also suggest that much of the structural benefit comes from limiting adaptation rather than solving the underlying verification problem. Furthermore, the method assumes that the warmup graph is already high quality. If the initial graph is inaccurate or the true structure changes substantially, preserving the warmup anchor could become undesirable. The experiments do not sufficiently establish how the method behaves under such conditions.

Questions for authors
  1. What is the main graph-specific theoretical contribution of Proposition 1 beyond established surrogate-calibration and identifiability principles?

  2. Given that the graph-identity control does not establish the necessity of exact road-network edges for prediction, what evidence supports treating higher Graph AUPRC as a practically important outcome in these experiments?

  3. How would the proposed guardrail behave if the warmup graph were inaccurate or if the true graph underwent significant edge additions and removals?

  4. What advantage does the proposed guardrail offer over conventional adjacency regularization, early stopping, or periodically freezing graph parameters under comparable adaptation budgets?

2 comments

We thank the reviewer for a careful assessment and for recognizing the value of separating predictive accuracy, constraint satisfaction, and structural fidelity. Your questions about the role of the road graph and the adaptation budget sharpened our analysis. We address them below with a graph-specific calculation and additional experimental comparisons.

Q1. What is graph-specific beyond Proposition 1?

Proposition 1 gives the general calibration criterion. The new result computes the minimum excess proxy loss required to replace at least a given fraction of target edges. Fix the node states and consider binary graphs with kk edges, where the target also has kk edges. Among graphs that replace exactly qq target edges, the minimum residual sum is obtained by keeping the k−qk-q lowest-residual target edges and adding the qq lowest-residual non-target edges. Let r(i)+r_{(i)}^{+} and r(j)−r_{(j)}^{-} denote the target and non-target residuals in ascending order. For replacement fraction at least ϵ\epsilon, the exact curve is given by

Cq=∑i=1k−qr(i)++∑j=1qr(j)−,C∗=min⁡qCq,ΨZ(ϵ)=min⁡q≥⌈kϵ⌉Cq−C∗k.C_q=\sum_{i=1}^{k-q}r_{(i)}^{+}+\sum_{j=1}^{q}r_{(j)}^{-},\qquad C_{\ast}=\min_q C_q,\qquad \Psi_Z(\epsilon)=\frac{\min_{q\ge\lceil k\epsilon\rceil}C_q-C_{\ast}}{k}.

Both minima range over feasible replacement counts.

The curve agrees with exhaustive enumeration to 1.1×10−161.1\times10^{-16}. At the audited states, the largest fraction replaceable at zero excess is 1.0 on EdNet and approximately 0.963 on METR-LA. On EdNet, this means there exists a proxy-optimal graph containing no target edges. For soft adjacency, the companion curve has zero slope at all 20 audited final states. That curve is exact for the fixed-state proxy normalized by total edge weight, not for the implemented Hinge training loss with its denominator stabilizer.

Q2. What does higher Graph AUPRC tell us about a road graph?

If a learned graph is presented as a map of road connectivity, Graph AUPRC evaluates whether it ranks reference road edges ahead of non-reference edges. Prediction error cannot validate that interpretation. In PEMS-BAY Block-ST, Graph-On had lower RMSE than Graph-Off in 5/5 seeds, but lower RMSE than the edge-identity control in only 1/5. The preregistered R0 gate therefore blocked the R1 follow-up. METR-LA likewise showed weak graph dependence. These results distinguish the value of propagation for prediction from evidence that the learned edges represent the specified roads.

Q3. What happens with a poor anchor or a change in topology?

Trust penalizes drift from the warmup graph; it does not consult the target after warmup. In the METR-LA Stage A reruns, shortening warmup from 20 to 5 epochs increased the mean drift allowance from 0.003751 to 0.137637, while Trust's mean final Graph AUPRC across five seeds was 0.964 with 20 warmup epochs and 0.222 with 5. The first quantity is the controller's budget; the second measures the structural fidelity actually retained.

Stage C replaced 25% of the target edges. With the same old graph retained, freezing only the graph and continuing to update the other parameters yielded lower RMSE than stopping the entire model in 5/5 seeds. This tests adaptation with a fixed graph; whether Trust tracks a changed topology remains untested.

Q4. How does Trust compare with simpler retention methods?

The Stage B frontier holds training time fixed (5 warmup and 60 post-warmup epochs). Realized drift varies, so we report it alongside both outcomes.

Stage B methodMean actual driftGraph AUPRCIndependent-evaluation RMSE
Trust0.07040.28790.1802
Fixed penalty, μ=0.30.10500.29920.1755
Fixed penalty, μ=0.50.08230.29730.1781
Fixed penalty, μ=0.70.06520.29320.1807

At μ=0.3 and 0.5, each fixed penalty achieved higher AUPRC and lower independent-evaluation RMSE than Trust in 5/5 seeds, with greater mean drift. At μ=0.7, mean drift was closer to Trust's: the fixed penalty retained higher mean AUPRC, while Trust had slightly lower mean RMSE. On Stage B protocol validation, Trust had lower RMSE than Frozen (0.1785 vs. 0.1853) but higher RMSE than Original (0.1731). In the separate METR-LA Stage A rerun, periodic freezing yielded AUPRC 0.183 versus 0.199 for Original and 0.964 for Trust. Trust is thus a deployable way to limit drift, without a general advantage over fixed penalties.

In the revised manuscript, we will add the fixed-kk curve and proof, state which soft-adjacency objective the result covers, and report training budgets, realized drift, fidelity, and prediction error together. We hope these analyses address your concerns about what the certificate establishes and when the guardrail is useful.

Thank you for the detailed response and the additional experiments. I appreciate the authors' efforts to clarify their contributions and address my questions.

The new analysis is helpful, but I still have a few concerns. In particular, the practical value of recovering the exact reference graph remains unclear. The proposed guardrail also seems sensitive to the quality of the warmup graph, and the new results show that simpler fixed-penalty methods can perform just as well or better in some settings. It is also unclear how well the approach would work when the underlying graph structure changes significantly.

Overall, I appreciate the efforts, but I feel that my main concerns about novelty and practical usefulness have not been fully addressed. I will retain my original score.

Reviewer_naMFOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses a potential discrepancy in graph structure learning: the gap between the effectiveness of constrained optimization and the actual recovery of the true underlying structure. Specifically, it investigates whether minimizing a constraint loss can guarantee that the learned graph structure remains consistent with a predefined target graph. Through experiments on traffic network and knowledge tracing datasets, the authors demonstrate that even when the constraint loss decreases significantly and performance on downstream tasks remains relatively stable, the consistency between the learned graph and the target graph can still decline markedly. The authors analyze the causes of this phenomenon from the perspectives of constraint calibration and optimization trajectories, proposing relevant theoretical conditions and a diagnostic method based on structural gradient directions.

Critical strengths
  1. The research problem is significant. This paper addresses the discrepancy between the optimization objective and structural fidelity in graph structure learning—an issue of notable value for interpretable graph learning and the assessment of structural trustworthiness.

  2. The analytical framework is systematic. The paper attributes the decline in structural fidelity to two factors: inadequate constraint calibration and deviation in the optimization trajectory. It explores the impact of these factors through both theoretical analysis and gradient-direction diagnostics.

  3. The experimental design is rigorous. The core phenomenon is validated across various traffic networks and different parameterization methods for graph structure learning. Furthermore, the paper provides a compelling analysis of the underlying causes through experiments involving structural perturbations, interventions in gradient trajectories, and extended training durations.

Critical weaknesses
  1. The importance of graph structure fidelity in real-world tasks has not been sufficiently validated. The paper primarily uses Graph AUPRC to measure the alignment between the learned graph structure and a predefined reference graph. However, in real-world traffic networks, the actual road connectivity does not necessarily correspond to the dependencies most beneficial for a given prediction task. Furthermore, some of the paper’s experiments show that significant changes in the graph structure result in only minor fluctuations in predictive performance; additionally, the tests on graph structure dependency provided in the appendix fail to demonstrate that the specific edges in the reference graph are indispensable for the prediction task. Consequently, the authors need to provide further justification for why recovering a predefined reference graph should be a key objective of graph structure learning, and what practical benefits higher structural fidelity actually yields.

  2. The innovation of the core research findings is relatively limited. The discrepancy between predictive performance and the quality of structural recovery in graph structure learning has already received considerable attention. Related works cited in the paper—such as Zügner et al. (2021), Ozen et al. (2025), and Manenti et al. (2025)—have all discussed, from various perspectives, how predictive efficacy does not equate to the recovery of the true underlying structure. While this paper further highlights the gap between constrained optimization and structural fidelity, its central conclusions are quite similar to existing research. The authors should more clearly articulate the fundamental differences between their work and existing studies, as well as their specific theoretical or methodological contributions.

  3. The theoretical analysis lacks sufficient depth and practical utility. The proposed "Constraint-to-Structure Calibration" characterizes the conditions for structural recoverability primarily through the gap between the constraint loss and the structural risk; in essence, these theoretical results are, to some extent, a reformulation of existing concepts regarding surrogate loss calibration.

  4. The proposed structural preservation strategy lacks sufficient evidence of its advantages. The "Warmup-Anchored Structural Guardrail" essentially prevents structural drift by limiting the distance between the learned graph and the graph obtained during a warm-up phase—an approach that is quite similar to conventional parameter regularization or proximity-based constraints. More importantly, in the METR-LA experiments, simply freezing the graph structure yielded a higher Graph AUPRC (0.9959) compared to 0.9640 for the proposed Trust method; furthermore, the prediction error of Trust did not outperform that of the unconstrained "Original" method. It is advisable to further verify the necessity of this strategy and its advantages over simpler alternatives.

Questions for authors

Please see the weaknesses.

1 comment

We sincerely thank the reviewer for recognizing the importance of our research question, our systematic two-factor analytical framework, and our rigorous experimental design across multiple traffic networks and parameterizations. Below we directly address your four questions with conclusions, new evidence, and concrete revision plans.

Q1. What is graph-specific beyond Proposition 1?

Proposition 1 gives a general calibration characterization. For graphs with exactly k=∣E∗∣k=|E^{\ast}| binary edges and fixed states, we additionally derive an exact, computable curve. Let qq target edges be replaced, and let r(i)+r_{(i)}^{+} and r(j)−r_{(j)}^{-} be the target- and non-target-edge residuals in ascending order. For feasible 0≤q≤min⁡(k,m)0\le q\le\min(k,m), with mm non-target edges,

Cq=∑i=1k−qr(i)++∑j=1qr(j)−C_q=\sum_{i=1}^{k-q}r_{(i)}^{+}+\sum_{j=1}^{q}r_{(j)}^{-} and C∗=min⁡qCqC_{\ast}=\min_q C_q.

ΨZ(ϵ)=min⁡q≥⌈kϵ⌉Cq−C∗k.\Psi_Z(\epsilon)=\frac{\min_{q\ge\lceil k\epsilon\rceil}C_q-C_{\ast}}{k}.

The curve agrees with exhaustive enumeration to 1.1×10−161.1\times10^{-16}. At the audited states, the zero-excess compatibility radius is 1.0 on EdNet and approximately 0.963 on METR-LA. At radius 1.0, there exists a zero-excess graph with no target edges. This is a fixed-state result for binary graphs, not a certificate for the training loss.

We also analyze normalized soft edge mass. If uu and vv are the minimum residuals on target and non-target edges, its curve is Ψsoft(ϵ)=ϵmax⁡(0,v−u)\Psi_{\mathrm{soft}}(\epsilon)=\epsilon\max(0,v-u). In all 20 audited final-state runs v≤uv\le u, giving zero slope. This fixed-state curve is exact for the normalized surrogate, not for the stabilized Hinge training loss.

Q2. Why measure Graph AUPRC if road-edge identity is not necessary for prediction?

Graph AUPRC measures how learned edge scores rank the declared target edges; it does not test exact equality of weighted adjacencies. When fidelity to A∗A^{\ast} is the claim, task RMSE does not answer that structural question. In PEMS-BAY Block-ST, Graph-On beats Graph-Off in 5/5 seeds but the edge-identity control in only 1/5. The preregistered R0 gate therefore blocked the R1 follow-up. METR-LA likewise shows weak task dependence on exact graph identity. These controls establish the distinction: predictive utility can persist while fidelity to the declared target is lost. Our question is whether success at the constraint interface can certify that fidelity, beyond the known prediction–structure mismatch.

Q3. What if the warmup anchor is poor or the topology changes?

Trust limits the learned graph's displacement from its warmup anchor. With warmup shortened from 20 to 5 epochs, the mean allowed drift radius ρs\rho_s, fixed from warmup snapshots, rises from 0.003751 to 0.137637 (36.69×), and Trust's Graph AUPRC declines. The radius specifies the controller's allowance; the AUPRC separately records structural quality. In Stage C, 25% of the support is replaced. Whole-model early stopping and graph-only freezing retain the same old graph, but early stopping has higher RMSE in 5/5 seeds. Stage C tests that control comparison; it does not evaluate Trust against both old and new targets. This identifies anchor quality as the determinant of what the guardrail preserves.

Q4. How does Trust compare with simpler retention methods?

Trust is one deployable drift-control implementation: it continues training without access to A∗A^{\ast} after warmup. The matched comparisons show its position:

SettingEvaluationResult
Stage A, METR-LAProtocol validationGraph AUPRC: Original 0.213, Trust 0.964, Frozen 0.996; RMSE: Original 0.4216, Trust 0.4230
Stage B, 5-epoch warmupProtocol validationRMSE: Original 0.1731, Trust 0.1785, Frozen 0.1853; Trust−Frozen AUPRC −0.0018
Stage B fixed-penalty frontierIndependent evaluationAUPRC/RMSE: μ=0.3\mu=0.3 0.2992/0.1755; μ=0.5\mu=0.5 0.2973/0.1781; Trust 0.2879/0.1802
Stage C, 25% support replacementProtocol validationEarly stopping and graph-only freezing retain the same graph; early stopping has higher RMSE in 5/5 seeds

Stage A shows structural retention relative to Original, not recovery along a single trajectory; Frozen retains still more. In the tested Stage B setting, Trust improves RMSE over Frozen but not Original. The fixed-μ\mu penalties outperform Trust on both AUPRC and independently evaluated RMSE in 5/5 seeds. The Stage B protocol-validation and independent-evaluation RMSE columns are reported separately.

In a subsequent revision, we will add the fixed-kk curve and proof alongside its soft-mass analysis, with the assumptions stated at each result. We will report the Stage B fixed-penalty frontier and Stage C control with their respective evaluation protocols, clarify Graph AUPRC's claim-relative role and the anchor-quality boundary, and place the Trust-versus-freezing and fixed-penalty comparisons beside the guardrail result.

Reviewer_KobvOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors propose an audit method for graph structure learning models where they measure the "task behavior", "surrogate success" and "target fidelity" to discover and diagnose failures, and propose a technique that can be used to "limit structural drift".

Critical strengths
  • The idea of auditing graph structure learning methods might be interesting.
  • The related work seems relatively well discussed.
Critical weaknesses

I want to preface this section by mentioning that, while I have some experience with graph structure learning and have published a few papers in the field, I am not familiar with the literature regarding the certification of machine learning models.

The main and fundamental problem is that the paper is extremely poorly written and almost impossible to comprehend. Because of this, it is also very hard for me to verify the technical novelty and scientific contributions of the work.

  • In the abstract, the authors fail to convey what the paper aims to show or discuss.
  • The introduction then repeats various points from the abstract without properly expanding on them --- for instance, I do not understand what a "declared-target training contract" is, and the authors do not introduce what objects such as the "external graph A*" are before discussing them. After reading the abstract and introduction a few times, I still do not understand the paper's main claims and research questions.
  • The problem setup section also doesn't clarify what exactly the setup is; my only understanding is that the overall scenario is training a model with a task loss and two additional penalty terms: a "constraint" term that gets "activated" after some "warmup" steps that have their own penalty. Moreover, once again, terms are used without properly being introduced: "Hinge", "ReLU-zscore", "A*", "non-oracle contract" etc.
  • The D1/D2/D3 characterizations and experiments are also poorly written. Some definitions and lemmas are introduced, but it is unclear how they are used. The experiments discussions are also poor, and it is unclear to me what hypotheses they are testing and discussing.
  • The overall language used in the paper is vacuous.

The whole paper also includes some very common LLM idiosyncrasies: "training arms", "oracle controls", weird formulations like "prediction-useful graphs", "loss-form interface", "preregistered verdict" and so on. My suspicion is that the paper was drafted by a LLM, and the authors did not sufficiently proofread and refine the paper.

I personally do not believe that using LLMs and LLM agents should disqualify papers from publication --- on the contrary, they can be excellent tools to be used in various parts of the research process, including writing. However, in this case, it seems to me that the authors made very little effort in drafting the final manuscript that was submitted.

I recommend that the paper be rejected, and I urge the authors to significantly revamp their manuscript and send it to a few rounds of internal (human) review before submitting it to other venues.

Questions for authors

Was the paper proofread by humans before being submitted to ICLR?

2 comments

We thank the reviewer for reading the paper section by section and for rigorously identifying specific problems from the perspective of a graph structure learning (GSL) reader. We acknowledge the central issue directly: if a reader with experience in GSL cannot follow the paper, the problem lies in our exposition, not in the reader’s background. Your detailed account of the readability barriers across the manuscript is precise and well targeted. In this response, we first clarify the paper’s central question, exact formulations, and terminology, and then address the human verification process and our concrete revision plan.

  1. Research question We declare an external graph A^ (e.g., road adjacency) as the structural target. It guides graph learning during warmup. After warmup, ordinary training conditions no longer access A^, which is retained for structural audit.

We ask whether good task performance and a low optimized constraint-proxy value certify that the learned graph remains faithful to A^. Our results show they do not. We therefore distinguish three quantities: task behavior (validation RMSE), surrogate success (optimized violation proxy), and structural fidelity (Graph AUPRC against A^). The first two can improve while the third deteriorates. 2. Experimental setup We use a two-stage protocol. For the Hinge implementation, the training objective is:

\mathbf{1}[t\geq T_w]\lambda L_c+ \mathbf{1}[t<T_w]\lambda_{w,t}L_{\mathrm{warm}}.$$ Warmup and post-warmup constraints are not applied simultaneously. The post-warmup constraint interface has two implementations: Hinge (additive loss): $$L_{\mathrm{hinge}}= \frac{ \sum_{b=1}^{B}\sum_{i\neq j} A^s_{ij}\max(0,Z_{bj}-Z_{bi}+\epsilon) }{ B\sum_{i\neq j}A^s_{ij}+10^{-8} }.$$ This penalizes order violations on learned-edge-weighted pairs, normalized by total edge weight and batch size. ReLU-zscore (logit offset, not a loss): $$\mathrm{SMR}{ij}= \frac{1}{B}\sum_b \mathbf{1}[Z{bj}>Z_{bi}+\epsilon],$$ $$s_{ij}=\max\left(0,\frac{\mathrm{SMR}{ij}-\mu}{\sigma}\right), \qquad \mathrm{logit}{ij}\leftarrow \mathrm{logit}{ij}-\beta s{ij}.$$ Here, $\mu$ and $\sigma$ denote the off-diagonal mean and stabilized standard deviation ($+10^{-6}$). The offset is applied before constructing $A^s$; no additional loss is introduced. 3. What D1/D2/D3 establish D1 — Dissociation. On METR-LA, PEMS-BAY, and PEMS08, the Hinge proxy decreases by more than 98% from the warmup boundary, while paired task-error differences remain small and Graph AUPRC deteriorates. The pattern is replicated across four amortized graph parameterizations and two 500-epoch runs. EdNet provides an order-domain stress test. A synthetic 2×2 positive control achieves true-graph AUPRC of 1.0, confirming that the audit detects success as well as failure. D2 — Mechanism. Calibration tests whether the constraint interface distinguishes $A^*$ from residual-equivalent alternatives. The exact fixed-$k$ certificate curve matches exhaustive enumeration to $1.1\times10^{-16}$, with zero-excess radii of 1.0 on EdNet and 0.963 on METR-LA. Route examines whether graph updates move toward the target; the constraint-gradient direction is adverse in 5/5 seeds. These identify two distinct failure points. D3 — Recovery boundary. Oracle directional correction improves local structural quantities but improves Graph AUPRC in only 3/5 seeds. Thus, local directional correction does not guarantee global structural recovery. Trust is a preventive drift guardrail, not a new optimization method, and operates without $A^*$ during ordinary post-warmup updates. The results use frozen, checksummed artifacts. 4. Changes in the later revision. In a later revision of the manuscript, we will reorganize the paper so that A*, the two-stage protocol, and the three measured quantities are stated in plain language on page 1. We will make the presentation more accessible and more complete: define each term at first use, replace internal labels with standard terms, state the question behind each definition and lemma, and present each experiment as question, control, result, and scope. We will explain the protocols and comparisons explicitly, including the evaluation sets, the fixed-k certificate, and the guardrail comparisons.

Thank you for your rebuttal response and for acknowledging the clarity issues with of the paper.

While I will not change my recommendation, I want to wish you good luck with future revisions of the work. I believe that the feedback gained during the rebuttal will help with making the paper solid in the future.

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

This paper investigates a fundamental question in graph structure learning, do favorable task performance and a low constraint loss necessarily certify fidelity to a declared structural target? The authors observe that even when an external graph guides an initial warmup phase after which it is withheld from ordinary graph updates. The paper further analyzes constraint-to-structure calibration and structural route alignment, proposing a warmup anchor guardrail that limits post warmup deviation from the warmup anchor to mitigate structural drift.

Critical strengths

1.The research problem is important, and the motivation is clear. The experiments distinguish task performance from structural fidelity, and the pattern is replicated across multiple traffic networks and graph parameterizations.
2.Starting from a shared warmup checkpoint, the authors independently gate the task-to-graph and constraint-to-graph paths. They also introduce a magnitude-matched control in the oracle structural-route correction experiment. These design choices help analyze the effects of update routes and gradient direction on structural fidelity.

Critical weaknesses

Both the task-to-graph and constraint-to-graph paths can reduce structural fidelity. However, removing the adverse component of the constraint gradient is not equivalent to actively promoting structural recovery. The explanation for why the oracle correction does not reliably restore global edge ranking remains limited.

Questions for authors

1.During oracle structural-route correction, does the task-to-graph path remain active when the constraint gradient is projected? 2.Since the warmup-anchor guardrail depends on the quality of the warmup anchor, does Trust retain higher structural fidelity than Original and lower RMSE than Frozen in the fixed-support shift experiment when the warmup duration is shortened?

1 comment

We sincerely thank the reviewer for the thoughtful evaluation and for recognizing the clear motivation of our problem, the cross-network validation separating task performance from structural fidelity, and the analytical value of our pathway and magnitude-matched controls. Your two perceptive questions directly helped us sharpen the local-to-global recovery boundary and verify the robustness of the warmup anchor. Below, we first clarify the Oracle update pathway, then report a new edge-ranking decomposition and short-warmup experiment prompted by your feedback.

Q1. Is the task-to-graph pathway active during Oracle projection?

Yes. Oracle projection modifies only the constraint-gradient component on the graph parameters. The task gradient is added unchanged before the optimizer step, and both graph and task-model parameters continue to update.

The Magnitude-matched control preserves the original constraint-gradient direction while matching its norm to the projected gradient. Projected versus Magnitude-matched therefore evaluates the directional intervention under a matched constraint-gradient norm.

Why does Oracle correction not reliably recover global edge ranking as measured by AP?

Removing a locally adverse component is not equivalent to actively promoting recovery. Projected is a directional mechanism test: it asks whether removing the diagnosed adverse component improves structural ranking.

The new ranking decomposition identifies where recovery breaks down. Projected improves aggregate positive-negative pair ordering in all five seeds. Each seed contains 62,307,405 candidate pairs, and the correction yields approximately 0.55-8.58 million additional correctly ordered pairs. However, the top-kk contribution to average precision (AP) improves in only 3/5 seeds. In the two seeds where AP decreases, top-kk contributions change by -0.0843 and -0.0537, outweighing middle-rank gains of +0.0470 and +0.0257; lower-rank contributions are also negative. Thus, aggregate pair ordering improves in 5/5 seeds, whereas the AP-sensitive high-ranking target-edge region and AP improve in only 3/5.

Our fixed-state, fixed-edge-budget certificate analysis provides complementary evidence. The surrogate's zero-excess optimal set admits graphs far from the declared target: the measured zero-excess compatibility radius is 1.0 on EdNet and approximately 0.963 on METR-LA. Together, these results establish a local-to-global recovery boundary: neither surrogate optimality nor local directional correction alone determines global target-edge ranking.

Q2. Do the requested comparisons hold with a shorter warmup?

Yes, both hold in the tested Stage B setting. This controlled comparison requires a known target support A∗A^* that remains fixed across the shift and observable post-shift ground-truth propagation weights. Although the real-traffic datasets provide external road-reference graphs, they do not provide the latter after a controlled distribution shift. We therefore shorten warmup to 5 epochs in synthetic Stage B using 50 nodes and five paired seeds. Within each paired seed, all arms share the same warmup checkpoint and subsequent RNG stream.

Comparison (Metric)Mean diff. (Trust - Ref.)Paired seeds
Trust vs. Original: Graph AUPRC (↑\uparrow)+0.1081Trust > Original in 5/5
Trust vs. Frozen: validation RMSE (↓\downarrow)-0.0068Trust < Frozen in 5/5
Trust vs. Frozen: Graph AUPRC (↑\uparrow)-0.0018Trust > Frozen in 1/5

With a 5-epoch warmup, Trust therefore retains more structural fidelity than Original while achieving lower validation RMSE than Frozen. Frozen provides slightly stronger structural retention, whereas Trust preserves adaptation to the fixed-support weight shift. The METR-LA Stage A drift-mitigation experiment, the METR-LA graded-correction audit in Appendix F.10, and the PEMS-BAY Block-ST graph-identity audit in Appendix F.14 provide complementary real-domain evidence and controls.

Summary

We thank the reviewer for the two insightful questions, which prompted us to further clarify our empirical findings and conceptual boundaries. First, Oracle correction improves aggregate pair ordering in every seed, but this improvement does not consistently reach the AP-sensitive top-ranked region; the large zero-excess compatibility radii further show that surrogate optimality does not identify the declared target. Second, under short warmup in the tested Stage B setting, the guardrail retains more structural fidelity than unconstrained training (+0.1081 mean Graph AUPRC, 5/5 seeds in the same direction) while preserving greater task adaptation than freezing (-0.0068 mean validation RMSE, 5/5 seeds in the same direction). We will incorporate both the edge-ranking decomposition and the short-warmup evaluation into the revised manuscript, and we hope these clarifications fully resolve your concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.