acceptodds
Under review as a conference paper at ICLR 2027

Robustness by Cancellation: Break, Repair, and Signed Structural Responses in Graph Neural Networks

Abstract

A graph neural network can appear structurally robust even when many predictions change correctness. Topology perturbations can Break initially correct predictions and Repair initially incorrect ones, while aggregate accuracy records only their net difference. We show that both transitions follow a common margin-crossing account: clean margin sets the crossing threshold, structural response provides the signed displacement, and clean-state opportunity weights conditional susceptibility into population-level flow. On the development graphs, an independently measured response signal improves held-out Break/Repair susceptibility AUC beyond clean margin by \(0.058\)-\(0.113\). On external graphs, the boundary-distance relation remains stable under perturbation-bank resampling, whereas response predictiveness is setting-dependent, including a Repair case at chance. Across competence-filtered datasets and targeted changes in architecture, perturbation operator, and graph scale, Break and Repair recur despite variation in magnitude and net direction. Aggregate accuracy therefore does not, by itself, establish prediction stability.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Structural Robustness, Graph Perturbations, Node Classification, Prediction Stability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_QMCkOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the prediction-level robustness of GNNs under test-time topology perturbations. It decomposes accuracy changes into Break (correct-to-wrong) and Repair (wrong-to-correct) transitions and analyzes them through margin crossing and signed structural responses, arguing that aggregate accuracy can hide substantial prediction-level instability.

Critical strengths
  1. This paper analyzes the phenomenon that the aggregate accuracy alone is not enough for GNN robustness evaluation and provides an intuitive Break/Repair decomposition.
  2. The empirical study covers multiple datasets, architectures, and perturbation settings, and the authors are reasonably careful about the scope of their claims.
  3. The margin-crossing interpretation provides a simple and interpretable explanation of prediction transitions.
Critical weaknesses
  1. Motivation is not clear; why the author focuses on this problem, and which problem they want to solve is also not clear.
  2. The Cora-GCN example is used in multiple places and seems redundant.
  3. Section 3.4, as an experimental setting, should not be put inside Section 3, and after Section 3, the following sections are mixed with method formulation and experiments; they need to be rearranged. The paper's organization is chaotic and needs careful reframing.
  4. The overall paper is an empirical study, not a deeper analysis and comparison to other related C-B methods; it needs further discussion and comparison to other existing methods.
  5. Since the problem in this paper is not clearly defined, it is not clear what the meaning of this paper is; at least add future or following potential applications.
Questions for authors
  1. What is the motivation for this paper? Why do we need this study?
  2. What is the novelty and superiority compared to existing related work?
2 comments
AuthorsOpenReview ↗

Response to Reviewer QMCk

We thank the reviewer for the careful reading. We address each concern below.

1. Motivation and problem.
The paper studies a concrete ambiguity in structural robustness evaluation: a small aggregate accuracy change may reflect genuine prediction stability, or substantial correct-to-wrong and wrong-to-correct transitions that cancel. These cases differ materially, yet accuracy alone cannot distinguish them. Our goal is therefore diagnostic: under a fixed trained GNN and test-time topology perturbation, we ask when apparent robustness reflects genuine stability, when it reflects cancellation between Break and Repair, and what determines whether a prediction changes correctness.
Revision: We now state this objective explicitly in the Introduction.

2. Role of the Cora/GCN example.
Cora/GCN is intentionally used as one canonical running example, not as repeated independent evidence. The Introduction motivates the gap between net accuracy change and prediction-level turnover; Section 3.3 reuses the same numbers after Break, Repair, and total turnover are defined, tying the formal decomposition to the motivating example. The empirical evidence itself spans Roman-empire, PubMed, Minesweeper, ogbn-arxiv, additional breadth datasets and multiple stress tests.
Revision: We retain the example for continuity and added a roadmap clarifying the later analyses.

3. Organization.
We respectfully disagree that the scientific structure is chaotic. Section 3 defines the structural correctness-response setting and shared protocol. Sections 4-6 then follow one progression: boundary geometry, topology-induced signed response, and population-level opportunity. Section 7 tests falsifiable consequences on external graphs, and Section 8 examines breadth and scope.
Revision: We added an explicit roadmap at the end of the Introduction.

4. Analytical depth and relation to prior work.
We respectfully disagree that the paper is only an empirical study. It establishes an exact accounting identity between aggregate accuracy change and the difference between Repair and Break rates, exact margin-crossing conditions, an exact population factorization separating clean-state opportunity from conditional susceptibility, a closed-form cancellation boundary, and an exact binary-versus-multiclass distinction for Repair directionality.

These are not merely post-hoc bookkeeping relations. They generate testable consequences: boundary distance predicts susceptibility; independently measured signed response should add information beyond boundary geometry; clean-state opportunity controls how conditional susceptibility contributes to aggregate direction; and binary versus multiclass prediction yields an exact difference in wrong-state directionality. Sections 4-7 test these consequences separately.

The distinction from prior churn and Break/Repair work is specific: prior model-update settings change the predictor, whereas our setting keeps the trained predictor fixed and changes only graph topology. This isolates topology-induced response and enables realization-disjoint evaluation. After clean margin and degree are included, Bank-A response still adds held-out AUC gains of +0.058, +0.053, +0.087, and +0.062; gains remain positive under a stronger five-feature static baseline and for every training seed.
Revision: We clarified this distinction in Section 2.3 and added the controlled analysis in Section 5.2 and Appendix E.1.

5. Practical relevance.
The framework can distinguish genuine stability from vulnerability hidden by cancellation and prioritize susceptible nodes. On Roman-empire, adding signed response raises the held-out Break rate among the top 5% ranked nodes from 0.46 to 0.72 and top-20% high-risk recall from 0.48 to 0.91. Ten Bank-A trials retain 78%-91% of the 50-trial incremental gain, while 20 trials retain 91%-97%; Break and Repair are already present at perturbation rate 0.05.
Revision: These results are summarized in Section 9 and detailed in Appendix E3.

6. Novelty and added value.
The novelty is not the existence of correct-to-wrong and wrong-to-correct transitions themselves. It is the combination of a fixed-model topology intervention, a micro-to-macro account linking clean boundary state, topology-induced signed displacement, and clean-state opportunity, and a realization-disjoint protocol testing whether response measured under one perturbation bank predicts susceptibility under unseen perturbations.

Because this is a diagnostic framework rather than a competing defense algorithm, task-accuracy superiority is not the relevant comparison. The relevant question is whether structural response reveals information that aggregate robustness and static boundary features do not retain; the controlled and held-out experiments directly test this.
Revision: We strengthened this distinction in the Introduction, Section 2.3, Section 5.2, Section 7.1, and Appendix E.

Thank you for the detailed rebuttal and additional experiments. After re-reading the paper, I acknowledge the improvements and am reconsidering my initial rating. However, I still have the following concerns.

  1. The paper begins with GNN robustness but mainly focuses on node-level Break/Repair transitions. While aggregate accuracy can conceal these transitions, why should they indicate insufficient robustness if overall accuracy remains acceptable? The authors should better explain when and why these transitions provide more meaningful robustness information than aggregate accuracy.

  2. The margin-crossing analysis explains when Break/Repair occurs, but its implications remain unclear. It is intuitive that nodes farther from the decision boundary are generally less susceptible to perturbations. However, changing the graph structure to improve one node's margin may also affect other nodes' margins, potentially making them more vulnerable. How can this analysis guide improvements in overall GNN robustness rather than simply shifting vulnerability between nodes? The current results do not sufficiently address this question.

  3. Although the margin is mathematically defined, the theoretical foundation of the proposed formulation remains insufficiently developed.

  4. Beyond predicting susceptible nodes, how can this understanding improve robustness evaluation, guide graph modifications, or improve model performance? The current results do not sufficiently demonstrate the practical value of these findings.

I appreciate the authors' additional experiments and clarifications. While I acknowledge the improvements, I still believe the paper falls below the acceptance bar for ICLR, primarily due to my remaining concerns.

Reviewer_KCRAOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates a phenomenon termed robustness by cancellation in GNNs. It argues that aggregate accuracy changes can conceal substantial prediction-level correctness transitions, including Break (correct-to-wrong) and Repair (wrong-to-correct). The authors develop a unified explanation based on clean true-class margins, signed structural responses, and clean-state opportunity. They further examine whether structural responses measured using one perturbation bank can predict Break or Repair susceptibility under an independent bank. Experiments cover numerous node-classification datasets, including development, external-validation, and broader competence-aware evaluations. The reported findings indicate that opposing correctness transitions frequently coexist, although their magnitudes and the predictive value of structural responses vary across settings.

Critical strengths
  1. The paper highlights a meaningful limitation of accuracy-based robustness evaluation. The distinction between net accuracy change and correctness turnover is intuitive and practically relevant.

  2. The margin-based formulation gives a coherent explanation for Break and Repair within a common mathematical framework. The distinction between the initial boundary distance and the signed perturbation-induced displacement makes the discussion easier to follow.

  3. The experimental scope and reporting of limitations are substantial.

Critical weaknesses
  1. The paper provides a useful diagnostic perspective, but does not demonstrate how the proposed analysis can improve robustness evaluation decisions, identify nodes requiring protection, or guide structural interventions. Furthermore, estimating Bank-A response involves repeatedly perturbing the graph and running the fixed GNN, which introduces a potentially substantial computational cost. An analysis of diagnostic efficiency or a small case study showing how the framework informs robustness decisions would strengthen its practical contribution.

  2. Most analyses use random edge deletion at nominal r=0.20r=0.20, corresponding to approximately 40% of canonical undirected edge pairs under the manuscript’s budget convention. Addition and rewiring are included in targeted stress tests, but the analysis does not systematically characterize how Break/Repair behavior changes from very mild to severe perturbations across datasets. This may matter because the relative balance of Break and Repair could vary substantially with perturbation intensity.

Questions for authors

Please response to my mentioned weaknesses. Overall, this is a very interesting paper and I would tend to accept the paper if problems can be addressed.

1 comment
AuthorsOpenReview ↗

Response to Reviewer KCRA

We thank the reviewer for the positive assessment and constructive suggestions. We added targeted analyses addressing each practical concern raised in the review.

1. Robustness Evaluation Decisions and High-Risk Node Identification

We agree that a diagnostic is more useful if it can inform which predictions deserve closer robustness inspection. We therefore added a held-out vulnerability-triage case study. On Roman-empire, adding signed structural response increases the held-out Break rate among the top 5% ranked nodes from 0.46 to 0.72. For the top 20% ranked nodes, high-risk recall increases from 0.48 to 0.91.

This shows that the response signal can support a concrete evaluation decision: prioritizing nodes that are more susceptible to unseen perturbations from the same perturbation family, rather than treating all nodes equally when aggregate accuracy appears stable.

Revision: This practical diagnostic use is summarized in Section 9 and reported in Appendix E.3.

2. Diagnostic Efficiency and Bank-A Computational Cost

We also directly evaluated the cost concern by reducing the number of Bank-A perturbation trials. Relative to the original 50-trial setting, 10 trials retain 78%-91% of the incremental susceptibility gain across the four Cora/Roman-empire Break/Repair settings, while 20 trials retain 91%-97%.

Thus, the full 50-trial Bank-A budget is not required to preserve most of the diagnostic value. This quantifies how much diagnostic value is retained under a substantially smaller sampling budget and directly addresses the repeated-inference cost raised in the review.

Revision: The sampling-efficiency audit is summarized in Section 9 and detailed in Appendix E.3.

3. Scope Regarding Structural Intervention Guidance

The new triage analysis supports identifying and prioritizing vulnerable nodes, but we do not claim that the present framework learns an optimal structural intervention or protection policy. That would require an additional decision layer specifying which edges or nodes should be modified after vulnerability is identified.

We therefore keep the practical claim deliberately scoped: the current framework informs robustness auditing and vulnerability prioritization, while intervention-policy design is a natural downstream extension rather than a claim of this paper.

Revision: Section 9 now frames the practical use in terms of diagnostic prioritization rather than intervention optimality.

4. Mild-to-Severe Perturbation Behavior

We added a systematic deletion-severity audit on both development graphs at perturbation rates 0.05, 0.10, 0.15, and 0.20. Break and Repair are already present at the mildest setting and persist throughout the tested range.

On Cora, Break increases from 0.0164 to 0.0563 and Repair from 0.0100 to 0.0267 as severity increases. On Roman-empire, Break increases from 0.0317 to 0.0838 and Repair from 0.0415 to 0.1083. Their relative balance remains graph-dependent: Cora is Break-dominant throughout the tested range, whereas Roman-empire is consistently Repair-dominant.

These results show that the bidirectional response is not specific to the nominal 0.20 setting: it is already present under mild perturbation, while its magnitude increases with severity and its balance remains setting-dependent. We perform this severity sweep on the two development graphs rather than every external and breadth dataset; the broader experiments separately test recurrence across datasets, architectures, and perturbation operators. Together with the existing deletion, addition, and rewiring stress tests, the revised evaluation therefore examines complementary variation in both perturbation intensity and perturbation type.

Revision: The severity analysis is summarized in Section 9 and reported in full in Appendix E.3.

Taken together, the revision adds both elements suggested in the review: an evaluated practical case study for vulnerability prioritization and an explicit diagnostic-efficiency analysis, together with a systematic mild-to-severe perturbation audit. These additions directly address the practical-use, diagnostic-efficiency, and perturbation-severity concerns raised in the review.

Reviewer_oZiDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper argues that aggregate accuracy under test-time topology perturbation conceals a bidirectional response, decomposing ΔAcc = P(C→W) ("Break") − P(W→C) ("Repair"). Both are recast as margin-crossing events in true-class logit-margin space: the clean margin sets the threshold, the signed structural displacement supplies motion, and clean-state opportunity weights conditional susceptibility, giving a cancellation boundary A* = R_cond/(B_cond+R_cond). Empirically, on Cora and Roman-empire, Break/Repair susceptibility decays with clean boundary distance, and a mean signed margin response measured on a disjoint perturbation bank (Bank A) improves held-out Break/Repair AUC over clean margin alone by 0.058–0.113. External tests on PubMed, Minesweeper and ogbn-arxiv probe three predictions (P1 boundary geometry, P2 response persistence, P3 repair directionality). A competence-filtered breadth study and targeted stress tests show both Break and Repair recur, while magnitude, balance and net direction vary, including sign reversals of ΔAcc.

Critical strengths
  1. The disjoint-bank design is a genuine methodological contribution and makes the predictive claim non-circular: Bank A measures the structural response while a realization-disjoint Bank B defines the Break/Repair target, so the predictor is never evaluated on the realizations used to construct it. The protocol is clearly specified (App. A.3, B.3) and per-seed gains (Table 7) are positive in all 12 cells. This is the element I expect to be reused, and why I read the negative results as credible.
  2. The claims are scoped carefully, including results that weaken the paper's own case: it excludes Tolokers from positive evidence (no candidate passes a frozen competence audit), reports the synthetic audit where Repair collapses to ~0.0005 (2/108 replicates exactly zero), and reports Minesweeper as weak for Break (0.526±0.008) and at chance for Repair (0.498±0.025, range 0.476–0.533)
Critical weaknesses
  1. The contribution beyond the churn literature is unclear and the evidence supports a narrower claim than the framing. Separating the claims into (i) coexistence of Break/Repair under test-time topology perturbation, (ii) the margin-crossing and population accounting linking clean margin, signed displacement, and clean-state opportunity, and (iii) the topology-specific signed response ΔM_i plus the disjoint-bank protocol: (i) is close to prior churn observations, (ii) is a useful but primarily organizational synthesis, and (iii) is the clearest source of distinction — yet its evidence is narrow: four dataset-transition cells on two development graphs, an external probe that is informative on PubMed/ogbn-arxiv but weak/chance on Minesweeper, and only modest gains where they survive. The paper establishes a scoped empirical regularity in GNN topology, not a general mechanism. The most distinctive ingredient has the least stable support.
  2. The sole substantive empirical claim rests on a narrow evidence base and is not consistent under external validation. The structural-response gain (Table 1) relies on a two-feature logistic probe (clean margin + Bank-A mean displacement) improving AUC by 0.058–0.113 on Cora and Roman-empire, for a target defined as "crossed the boundary at least once in 50 Bank-B trials". The gain with degree in the baseline is reported as positive but not sized; the paper does not report the increment over a degree-only probe, nor compare with the second-best-class gap or the clean margin. Since AUC is a rank statistic, any correlate of boundary proximity improves it, so the increment size matters. External tests collapse to chance on Minesweeper (Break 0.526±0.008, Repair 0.498±0.025) — the one external graph that is binary, dense and low-dimensional — and the paper does not test whether the regime or the checkpoint causes the failure, leaving the explanation descriptive. This is the only experiment supporting the incremental-prediction claim; the empirical case for a general structural-response mechanism remains thin.
Questions for authors
  1. Ishimoto et al. (2025) studies Break/Repair under model updates; this paper freezes the model and perturbs topology at test time. Beyond applying the decomposition to a new perturbation source, what is the precise incremental contribution? What does the topology-perturbation setting enable that the model-update setting cannot? Is the primary novel claim the signed displacement, the disjoint-bank protocol, the cancellation boundary, or the persistence of the response? What is the evidence for its added value over the model-update setting?
  2. The Bank-A gain with node degree in the baseline is reported as positive but not sized. What is the ΔAUC of a probe with clean margin + degree + Bank-A response, relative to the same probe without the Bank-A response? And the corresponding ΔAUC when the clean margin is added, again comparing with and without the Bank-A response? If either increment is small relative to 0.058–0.113, what evidence shows Bank A carries structural-dynamics information rather than another correlate of boundary proximity?
  3. All external analyses fix the seed-0 checkpoint; reported standard deviations quantify perturbation-bank, not training-seed, variability. How large is the training-seed variability of the ΔAcc and P2 AUCs? In particular, is the chance-level Minesweeper P2 result stable across retrained checkpoints and across a second binary, dense, low-dimensional graph, or is it a checkpoint/regime artifact? This determines whether the negative result is a scope boundary or a mechanism failure.
1 comment
AuthorsOpenReview ↗

Response to Reviewer oZiD

We thank the reviewer for the careful and technically specific review, and for recognizing the realization-disjoint Bank-A/Bank-B design as a genuine methodological contribution. We address the main concerns below.

1. Contribution Beyond Prior Churn Work

We do not claim novelty for correct-to-wrong or wrong-to-correct transitions themselves. The primary incremental contribution is the topology-specific signed-response analysis under a fixed predictor, together with a realization-disjoint protocol for testing held-out susceptibility.

This intervention differs from model-update settings: the trained predictor is fixed and only relational structure changes. This isolates topology-induced response from parameter change and enables controlled structural operators and budgets, node-level signed margin displacement, and separate perturbation realizations for measuring response and defining susceptibility. The margin-crossing and opportunity decomposition connects this response to Break/Repair and aggregate accuracy; we do not present the cancellation boundary alone as the primary novelty or claim universal response persistence.

Revision: Section 2.3 now makes this fixed-model topology distinction explicit, and the Introduction clarifies the realization-disjoint evaluation.

2. Incremental Value Beyond Static Proxies

We directly tested whether Bank-A response is merely another correlate of boundary proximity or degree. With clean margin and degree already in the baseline, adding Bank-A response gives held-out AUC gains of +0.058, +0.053, +0.087, and +0.062 for Cora Break, Cora Repair, Roman-empire Break, and Roman-empire Repair; every training seed is positive.

We also use a stronger five-feature static baseline containing clean margin, degree, top-1/top-2 logit gap, maximum probability, and predictive entropy. Bank-A response still adds +0.049 to +0.059 across all four settings, and its absolute Spearman correlation with clean margin is at most 0.20.

We did not use degree-only as the decisive control because it omits clean margin, the central boundary-proximity variable. The stricter test is whether response adds value after clean margin and degree are both present; the five-feature baseline further strengthens this test. Thus, the gain is not explained by the tested static boundary/confidence features. We keep the claim scoped to incremental susceptibility information, not optimal ranking.

Revision: Section 5.2 reports these controlled gains; full results are in Appendix E.1.

3. Training-Seed Stability and Minesweeper

We repeated the external analysis across independently trained checkpoints from seeds 0, 1, and 2. Across the audited Minesweeper seed-bank evaluations, Break AUC ranges from 0.514 to 0.566 and Repair AUC from 0.429 to 0.548. Adding response to clean margin changes AUC by only -0.008 to +0.001, while boundary geometry remains stable. Aggregate accuracy change is also stable across checkpoints: -0.040, -0.044, and -0.043. PubMed and ogbn-arxiv retain informative response predictiveness across seeds.

Therefore, the weak Minesweeper result is not specific to the original seed-0 checkpoint. We did not add a second matched binary, dense, low-dimensional graph, so we do not attribute the behavior to binarity, density, or feature dimensionality. We make only the supported conclusion: Minesweeper is a setting-specific scope boundary, not evidence for a general binary-regime failure.

Revision: Section 7.1 now separates bank variability from training-seed variability; Appendix E.2 reports the full audit.

4. Strength and Scope of the Structural-Response Evidence

The held-out response claim is intentionally within-graph and realization-disjoint; it is not a claim of cross-dataset predictor transfer or a universal mechanism. The new experiments strengthen exactly the two axes identified as unresolved in the review: alternative static explanations and independently trained checkpoints. The development gains survive stronger static controls and every training seed, while the Minesweeper negative result persists across retrained checkpoints rather than disappearing as a seed artifact.

We therefore retain the negative result and make the scope explicit: boundary geometry is comparatively stable, whereas predictive persistence of signed structural response is setting-dependent.

Revision: Section 5.2 now frames signed response as an incremental explanatory component, while Section 7.1 and Appendix E make the scope and seed stability explicit.

In summary, the revised evidence strengthens precisely the part of the paper identified in the review as most distinctive: topology-specific signed response under a fixed predictor and its non-circular, realization-disjoint evaluation.

Comments on the paper

1 comment

Thank you for the clarifications.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.