- 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
-
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.
-
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
-
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.
-
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.
-
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
-
What is the main graph-specific theoretical contribution of Proposition 1 beyond established surrogate-calibration and identifiability principles?
-
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?
-
How would the proposed guardrail behave if the warmup graph were inaccurate or if the true graph underwent significant edge additions and removals?
-
What advantage does the proposed guardrail offer over conventional adjacency regularization, early stopping, or periodically freezing graph parameters under comparable adaptation budgets?
2 comments
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.
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 k edges, where the target also has k edges. Among graphs that replace exactly q target edges, the minimum residual sum is obtained by keeping the k−q lowest-residual target edges and adding the q lowest-residual non-target edges. Let r(i)+ and r(j)− denote the target and non-target residuals in ascending order. For replacement fraction at least ϵ, the exact curve is given by
Cq=∑i=1k−qr(i)++∑j=1qr(j)−,C∗=minqCq,ΨZ(ϵ)=kminq≥⌈kϵ⌉Cq−C∗.
Both minima range over feasible replacement counts.
The curve agrees with exhaustive enumeration to 1.1×10−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.
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-k 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.