- 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
- This paper analyzes the phenomenon that the aggregate accuracy alone is not enough for GNN robustness evaluation and provides an intuitive Break/Repair decomposition.
- The empirical study covers multiple datasets, architectures, and perturbation settings, and the authors are reasonably careful about the scope of their claims.
- The margin-crossing interpretation provides a simple and interpretable explanation of prediction transitions.
Critical weaknesses
- Motivation is not clear; why the author focuses on this problem, and which problem they want to solve is also not clear.
- The Cora-GCN example is used in multiple places and seems redundant.
- 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.
- 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.
- 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
- What is the motivation for this paper? Why do we need this study?
- What is the novelty and superiority compared to existing related work?
2 comments
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.
-
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.
-
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.
-
Although the margin is mathematically defined, the theoretical foundation of the proposed formulation remains insufficiently developed.
-
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.
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.