- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies when graph repair should use reweighting versus rewiring. The authors construct an edge flow from frozen classifier predictions and use Hodge decomposition to separate gradient and cycle components. They prove that positive reweighting on a fixed support cannot eliminate a nonzero cycle component, and propose the Hodge Router, which uses the normalized cycle residual to choose between reweighting and rewiring. The rewiring branch further combines link scores, cycle contributions, and a bounded LLM-based arbiter. Experiments across random corruption, Metattack, and PRBCD show that the proposed diagnostic predicts which operation is preferable and that the router achieves strong robustness results.
Critical strengths
1.The paper asks a clear and relatively underexplored question: not how to repair a graph, but when reweighting is fundamentally insufficient and structural editing is preferable.
2.The theoretical formulation is elegant. The Hodge decomposition gives a clean interpretation of prediction inconsistency, and the reweighting result provides a principled connection between cycle residuals and support changes.
3.The experimental evaluation is extensive, covering multiple datasets, corruption mechanisms, adversarial attacks, competing diagnostics, graph-repair baselines, backbone transfer, sensitivity analysis, and computational cost.
4.The controlled comparison between reweighting and rewiring is a particular strength. Both operations use the same candidate support, backbone, and edit budget, making the routing analysis more interpretable.
Critical weaknesses
1.The theoretical certificate concerns fitting a fixed prediction flow, whereas the practical goal is downstream classification after retraining on the repaired graph. Since predictions can change substantially after repair, the connection between the theorem and the final learning objective remains indirect.
2.The impossibility result for exact fitting is somewhat narrow. Whether belongs to the gradient subspace is support-dependent regardless of weighting, so the more practically relevant contribution is the bounded-residual argument and its empirical predictive value rather than the exact-fit statement itself.
3.The diagnostic depends on the choice of the antisymmetric comparison matrix . The default class-frequency ordering is somewhat heuristic, and although alternative choices are evaluated, a stronger justification for why this construction should reflect graph corruption would improve the method.
4.The repair experiments assume an edit budget tied to the known perturbation rate. This is convenient for controlled comparison but may overestimate practical applicability when the amount of graph corruption is unknown.
5.The predictive relationship between the diagnostic and the preferred operation is meaningful but moderate rather than strong. A partial Spearman correlation of 0.38 suggests that substantial instance-level variation remains unexplained.
Questions for authors
1.Can the authors clarify the theoretical connection between fitting the frozen prediction flow and improving the classifier after retraining, where the prediction flow itself may change?
2.How sensitive is the routing decision to the choice of comparison matrix , and what principle motivates class-frequency ordering beyond its ability to generate non-gradient flows?
3.How would the Hodge Router determine the edit budget in a realistic setting where the perturbation or corruption rate is unknown?
4.The partial correlation between and the operation gap is 0.38. What are the dominant failure cases where the diagnostic routes an instance to the wrong operation?
5.To what extent does the performance gain of the full Hodge Router come from operation routing versus improved cycle-aware rewiring and semantic arbitration?
3 comments
The rebuttal addresses most of my concerns and provides useful clarification on the scope of the theoretical certificate, the role and sensitivity of , edit-budget robustness, and the relative contributions of routing, cycle-aware rewiring, and arbitration. In particular, the additional discussion of oracle regret and the weak/strong diagnostic regimes improves my confidence in the empirical relevance of the proposed certificate. Some limitations remain, especially that the theoretical guarantee applies to a fixed prediction flow rather than directly to the retrained classifier. Overall, the response strengthens the paper, and I maintain my original rating.
Follow-up response to Reviewer 9uHn
Thank you for the supportive assessment. We are glad the clarifications were useful. Below we address the remaining point.
Some limitations remain, especially that the theoretical guarantee applies to a fixed prediction flow rather than directly to the retrained classifier.
Response. The guarantee is stated on a fixed flow because the router chooses the operation before either repair is trained. Its structural part also applies to the retrained flow (E1). The link to classification accuracy is measured empirically, with results supporting the decision across the evaluated backbones and flow constructions (E2–E4).
E1. What carries over after retraining. The flows that node potentials can fit form , which is fixed by the candidate edge set , not by the classifier or weights. Reweight keeps , so retraining does not enlarge this subspace. Theorem 1 applies to every flow on , including the retrained flow: weights of spread keep its residual share between and , where is that retrained flow's own unweighted share.
The theorem does not determine this new or classification accuracy. The frozen flow supplies a diagnostic available before repair; Sec. 4.2 states its link to classification as the hypothesis tested experimentally.
E2. Prediction of outcomes after retraining. The Sec. 5.3 operation gap is the Macro-F1 of the classifier retrained after Rewire minus that after Reweight. Across 370 instances, the partial Spearman correlation of with this gap is 0.38, with CI [0.21, 0.52]; no non-Hodge deployable diagnostic in Table 1 reaches 0.10. The gate is within 0.09 points of the per-instance oracle, which sees both retrained classifiers.
E3. Transfer across retrained backbones (Table 19). The flow, gate, and edits are computed once from the frozen GCN. Four backbones are trained from scratch on the resulting graphs under Metattack at 15%, pooled over Cora, CiteSeer, and PubMed. The policy ordering is the same for all four. GAT and GraphSAGE ignore edge weights, so their Always-Reweight results use the unweighted candidate support.
| Backbone | Observed graph | Always-Reweight | Always-Rewire | Hodge Router |
|---|---|---|---|---|
| GCN | 70.80 | 73.06 | 78.81 | 80.00 |
| GAT | 70.87 | 71.62 | 78.05 | 79.13 |
| APPNP | 71.93 | 73.84 | 79.37 | 80.46 |
| GraphSAGE | 69.64 | 71.02 | 77.24 | 78.31 |
E4. A flow without a trained classifier (Table 20). Replacing the frozen classifier with soft assignments to feature centroids removes the trained classifier from flow construction. Under random corruption, the residual gate matches or exceeds the better fixed policy on all four datasets and exceeds the random gate that rewires the same share of instances.
| Macro-F1 | Cora | CiteSeer | PubMed | DBLP |
|---|---|---|---|---|
| Always-Reweight | 80.26 | 60.95 | 83.26 | 72.81 |
| Always-Rewire | 79.82 | 60.42 | 83.81 | 71.31 |
| Random gate | 80.05 | 60.73 | 83.60 | 72.55 |
| Residual gate | 80.46 | 61.15 | 83.85 | 72.90 |
Summary. The theorem characterizes what positive weighting can fit on a fixed candidate support, for both frozen and retrained flows. Whether the diagnostic predicts classification performance after retraining is an empirical question, tested in E2–E4 rather than guaranteed by the theorem.
Revision. The updated PDF is now uploaded. Blue text after Corollary 1 in Sec. 4.2 (page 5) clarifies that retraining on does not enlarge the gradient subspace and that the theorem applies to the retrained flow. “Reading the certificate” in App. B.1 (page 18) explains why the gate reads the frozen flow, what carries over after retraining, and how Sec. 5.3 and Tables 19–20 evaluate downstream accuracy.
Thank you again for the constructive discussion and your support.
Response to Reviewer 9uHn
Thank you for the thoughtful review. References below are to the proposed revised manuscript.
W1 / Q1: The link to a retrained classifier. The certificate concerns a specified flow on a fixed support; retraining may change that flow. We therefore use it to motivate a diagnostic, not to equate potential-fitting error with classification loss. The classification link is tested directly: kappa_diag has partial Spearman correlation 0.38 with the Rewire–Reweight gap, with 95% CI [0.21,0.52] (Table 1). The resulting gate matches or exceeds the better fixed policy on every dataset and has average oracle regret of 0.09 Macro-F1 points (Table 2). Table 5 verifies the fixed-flow bound using random weightings; it does not measure changes to the flow after retraining.
W2: Why emphasize the two-sided bound? The exact-fit condition is indeed membership in the gradient subspace fixed by the support. The quantitative contribution is rho_0/gamma <= R_W/||y||_W^2 <= gamma*rho_0: weights with bounded spread cannot reduce fixed-flow inconsistency arbitrarily. The bound becomes weaker as the permitted spread grows. The revision therefore foregrounds this quantitative statement and presents exact-fit impossibility as its corollary, with its scope separated from the empirical routing result.
W3 / Q2: Motivation and sensitivity of K. Proposition 1 requires K not to be a difference of class scores. The sign comparison is a simple order-based construction with that property; frequency ordering provides a training-data-based convention rather than relying on arbitrary label indices. Changes in frequencies that preserve the order leave the construction unchanged.
For one-hot predictions, nonzero circulation requires cycles involving at least three predicted classes. Figure 2 illustrates how a cross-class shortcut creates such a residual. This is a mechanism, not an assertion that every multi-class cycle is wrong. The evidence for relevance comes from the predictive and routing experiments.
For C=3, admissible K choices yield proportional cycle components up to sign on fixed predictions and support, preserving squared contribution rankings. This does not imply invariance of the normalized diagnostic or every routing decision. Table 16 directly tests alternatives: average accuracy changes are -0.15/-0.26/-0.93 points for prototype-cosine/native-order/random antisymmetric K under Metattack 15%. The evaluated alternatives thus remain within one point of the default.
W4 / Q3: Unknown corruption and the edit budget. The gate never reads the corruption rate. A budget is required only after an instance is routed to Rewire. Table 21 tests substantial misspecification under Metattack 15%: doubling the budget costs 0.54/0.53/0.37 points on Cora/CiteSeer/PubMed; halving it costs 1.82/1.47/1.45. At double budget the router still exceeds the strongest competing baseline on each graph. This establishes budget tolerance in that regime, rather than a general estimator of an unknown corruption rate.
W5 / Q4: Moderate correlation and weak regimes. The diagnostic is not a perfect instance-level predictor; the decision-level result is that it recovers most of the available routing benefit. Its average oracle regret is 0.09 points, versus 0.16 for uncalibrated rho and 0.30–0.49 for the other diagnostics (Table 1). Both kappa_diag and rho have partial-correlation intervals excluding zero; the other deployable diagnostics do not.
Table 7 locates the weakest association in betweenness deletion on Cora/CiteSeer (0.29/0.26, nonsignificant after Holm correction). At 15% deletion on Cora, Reweight scores 82.24 versus 79.74 for Rewire. Under Metattack, the correlations rise to 0.55/0.60/0.52 and are all significant. These strata characterize where the diagnostic is more or less informative without claiming an unmeasured breakdown of all individual misrouting errors. Under PRBCD, the gate correctly favors Reweight on 58/60 Cora/CiteSeer instances.
Q5: Which component contributes what?
These conditional comparisons distinguish operation selection from improvements within rewiring; they are not additive.