acceptodds
Under review as a conference paper at ICLR 2027

GraphSieve: Graph Purification via Attack-Agnostic Calibration across Perturbation Severities

Abstract

Structural poisoning attacks degrade node classification in graph neural networks by editing edges before training. Purification defenses respond by editing the observed graph, and their test accuracy depends on both the editing rule and the procedure that selects its hyperparameters. We study that selection when it must be made without access to the evaluation attack instances. We introduce GraphSieve, a purification defense for homophilous graphs that prunes low-similarity edges and adds high-similarity absent edges. Its attack-agnostic calibration selects configurations by mean validation accuracy over a trusted clean graph and label-blind random perturbations at prespecified severities. The same procedure calibrates GraphSieve and the purification baselines, separating calibration from graph editing. A prespecified evaluation on three citation graphs identifies gains in attacked-graph test accuracy over the undefended GCN, RGCN, and GCN-SVD, with no statistically significant loss to RGCN or GCN-SVD. An attack that adapts to the published editing criterion leaves GraphSieve ahead of the undefended GCN in 20 of 36 cells, with no loss. Against equally calibrated GCN-Jaccard, which applies the pruning rule alone, the evaluation finds both gains and losses. In exploratory ablations, calibration also lifts the baselines, raising GCN-Jaccard's mean attacked-graph accuracy over clean-only tuning by +0.44 and +4.18 percentage points on the fresh and reproduction profiles, and the benefit extends to GCN-SVD and GraphSieve. Single-severity comparisons show that a selection rule must be reported with its severity distribution. A follow-up replication, run after the prespecified evaluation with new attack graphs and model seeds, reproduces the augmentation gains in the Cora deletion-Metattack conditions, where calibration disables pruning. The gains are +1.21 and +0.93 percentage points over calibrated GCN-Jaccard at deletion budgets of 15 and 25 percent, respectively. These gains identify a replicated use case for augmentation rather than a general benefit from edge addition. Recovery diagnostics show that most added edges had never been deleted. These results motivate a common calibration protocol for purification defenses and distinguish predictive augmentation from reconstruction of the original topology.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, adversarial robustness, structural poisoning attacks, graph purification, calibration, hyperparameter selection, attack-agnostic defense, homophily, pre-registered study, node classification

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_3XfxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

GraphSieve combines similarity-based edge pruning with optional addition of high-similarity absent edges. The paper focuses on selecting defense hyperparameters using validation accuracy on a trusted clean graph and random perturbations at several severities. Applying this calibration to both GraphSieve and existing purification methods helps separate tuning gains from changes to the editing method. Experiments on three citation graphs show improvements over several baselines, but mixed results against equally calibrated GCN-Jaccard. A follow-up reproduces small gains from edge addition in two Cora deletion-Metattack conditions, while recovery diagnostics show that most added edges were never part of the original graph.

Critical strengths
  1. Calibrating the baselines under the same information-access assumptions is a useful contribution. GCN-Jaccard improves by +0.44 and +4.18 percentage points over clean-only tuning on the two profiles (Table 1). This demonstrates why comparing a tuned new method against a default baseline can give a misleading impression of progress.

  2. The diagnostics make the results easier to understand. The paper varies insertion/deletion composition, includes a structure-free baseline, reports clean-accuracy costs, and distinguishes candidate coverage from actual edge recovery. In particular, Table A19 supports the authors' decision to describe the added edges as predictive augmentation rather than successful reconstruction.

  3. The follow-up experiment is a useful check on the favorable Cora result. New attack graphs and model seeds reproduce gains of +1.21 and +0.93 points at the two deletion budgets (Table A16). The authors appropriately state that this is conditional on the original split and configurations and does not establish a general benefit from edge addition.

Critical weaknesses
  1. The improvement over a properly calibrated pruning baseline is limited. GraphSieve has 4 wins and 6 losses against GCN-Jaccard in 130 fresh-profile cells, and one win in 18 reproduction cells (Table 2). Against its own pruning-only ablation, it has 3 wins and 9 losses on the fresh profile. Addition is disabled throughout PubMed, and the positive replication concerns two selected Cora conditions. These are useful findings, but they leave the case for the new editing method rather weak. The ladder also loses on average to clean-plus-100%-severity tuning on the reproduction profile (Tables A13 and A15), so its advantage over simpler selection policies is not consistent either.

  2. The clean-graph assumption limits the practical motivation. Calibration uses a trusted clean copy of the same graph, which could simply be used for training, as the authors acknowledge. It is unclear when a defender would have that graph for calibration but still need to train on its poisoned counterpart. Evidence of transfer across separate trusted graphs or snapshots would help; without it, the contribution is mainly a controlled evaluation study.

  3. The adaptive attack does not adapt to the complete deployed defense. It knows the similarity rule but not the frozen thresholds or trained model, and its deletion heuristic does not test attacks that exploit the addition stage or insert high-similarity edges. I would like to know whether the gains survive an attack that uses the actual frozen configuration and optimizes against purification and training together. The current results support a narrower robustness claim.

  4. The registered E1/E2 decision rule treats cells as independent despite shared datasets, seeds, and calibrations. Appendix A's sensitivity analysis is helpful, but the six fresh-profile losses for E1 reach both dependence-aware bounds even though E1 “holds” under the registered rule. The substantive conclusion should follow that qualification. Reporting aggregate paired effects with uncertainty that preserves this dependence would be more informative than relying on counts of significant cells.

Questions for authors

See weaknesses 1–4.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 3Xfx

Thank you for taking the time to review our paper and for the constructive feedback.

  • W1. Improvement over the calibrated pruning baseline. Each number you quote is correct.

    1. 4 gains and 6 losses (fresh), 1 gain (reproduction). The four fresh gains (+0.72 to +0.89 pp) are all under pure deletion, edits that pruning cannot act on. A follow-up with new attack graphs and model seeds reproduces the two under deletion Metattack on Cora, at +1.21 [+0.77, +1.65] and +0.93 [+0.26, +1.60] pp. The six losses (at most 0.65 pp) are all on fresh-profile Cora at the two smaller budgets, with none on reproduction; four are at deletion shares of at least 0.50, so composition alone does not predict a benefit (Section 5.2; Tables A24 and A25).
    2. 3 gains and 9 losses against Prune-only. On fresh-profile Cora, calibration turns pruning off, so Prune-only and calibrated GCN-Jaccard both coincide with the undefended GCN, and six of the nine losses are the six Cora cells above. As Section 5.4 states, the nine losses exceed E2's registered bound, in a direction its clause does not cover; neither profile's aggregate difference excludes zero (W4).
    3. Addition disabled throughout PubMed. Calibration keeps addition only where it raises validation accuracy on the ladder. On PubMed the best configuration with addition scores below the best without it in every replicate, by a mean of 1.27 pp (fresh) and 1.03 pp (reproduction; post hoc, Appendix C). Calibration therefore declines it, and GraphSieve and calibrated GCN-Jaccard are the same method there: they build the same graph in every cell.
    4. The ladder against clean-plus-100-percent tuning. On citation-reproduction the ladder trails that control by 1.39 pp for GCN-Jaccard and 1.44 pp for GraphSieve, with 4 and 3 significant losses, all on Cora; on citation-fresh it leads by +0.33 and +0.15 pp (Section 5.1, Appendix C).

    Overall, GraphSieve does not improve on calibrated GCN-Jaccard, and the protocol you found useful is what makes that baseline strong (+0.77 and +4.26 pp over its library default). A better addition rule is left to future work: under generalized DICE on Cora and CiteSeer, the candidate set contains most deleted edges, but similarity ranking recovers few (Section 5.4).

  • W2. The clean-graph assumption and transfer. We use the trusted copy once, before any attack, only to choose the defense's settings. Training on that copy instead would work only if the graph never changed; once it changes, the defender must work with the changed graph and cannot tell which edits are attacks. Each replicate's frozen configuration is therefore applied unchanged to every attacked version of its graph, with no recalibration and no clean copy (Section 3.2). We also ran the transfer test you suggest, between graphs, and its result is negative: applying each citation graph's frozen configuration to the attacked cells of the other two (exploratory, fresh profile; Appendix C, Table A17), the transferred GraphSieve records more significant losses than gains against the undefended GCN in five of the six pairs. We therefore claim no transfer between different graphs.

  • W3. Adaptation to the complete deployed defense. The registered attack read the similarity signal but not the frozen thresholds, so we added two better-informed attackers (exploratory; Section 5.5, Table A20), holding the defense at its frozen configurations. L2 deletes only edges that the defense neither prunes nor re-admits, reading the registered pruning grid; L3 does the same reading each replicate's frozen threshold. Against the undefended GCN over 36 cells, GraphSieve records gains/NS/losses of 20/16/0 under the registered attack, 14/22/0 at L2, and 13/20/3 at L3, with the three losses on PubMed, and the abstract is revised accordingly. Both attackers adapt deletions and keep the DICE insertions, and no attacker evaluated optimizes through purification and training jointly. These results therefore measure sensitivity to better-informed deletions; they do not establish robustness and do not amount to adaptation to the complete defense.

  • W4. Dependence among cells. The registered bound does treat cells as independent (Section 4.3). We computed the estimator you describe, with the replicate as the unit and a 95 percent interval over 10 replicates (exploratory; Appendix A, paragraph "Aggregate paired effects", Table A1). The gains over the undefended GCN (+0.82 and +6.73 pp, fresh and reproduction), RGCN (+4.38 and +8.18), GCN-SVD (+6.34 and +2.71), and the feature-only baseline exclude zero. The differences from calibrated GCN-Jaccard, +0.01 [-0.15, +0.17] and +0.14 [-0.06, +0.35] pp, and from Prune-only, -0.06 [-0.12, +0.00] and +0.07 [-0.08, +0.22] pp, do not.

We rewrote many parts of the paper for clarity and welcome any further comments that would strengthen it.

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

This paper proposes GraphSieve, a graph purification method against structural poisoning attacks on GNNs. It combines similarity-based edge pruning and addition to improve graph robustness. The authors introduce a severity-ladder calibration strategy that selects hyperparameters without accessing evaluation attacks. Experiments on three citation datasets demonstrate improvements over GCN-SVD and RGCN. However, the gains over equally calibrated GCN-Jaccard are limited. Additional analyses highlight the benefits of calibration and distinguish predictive edge augmentation from topology reconstruction.

Critical strengths
  1. The paper evaluates multiple attack settings and baselines under a unified calibration protocol, providing fair comparisons and detailed statistical analyses.
  2. The ablation studies and replication experiments demonstrate the value of calibration and clarify the limited effectiveness of edge addition for topology recovery.
Critical weaknesses
  1. While the severity-ladder calibration strategy is useful, GraphSieve provides only limited improvements over equally calibrated GCN-Jaccard, raising concerns about the independent effectiveness of the added edge restoration stage.
  2. The method requires access to a trusted clean graph and validation labels, which limits its practical applicability in realistic poisoning scenarios.
Questions for authors

Q1. What realistic poisoning scenario allows the defender to access a trusted clean graph for calibration but still requires purification of the poisoned graph? Could the authors clarify the practical motivation for this assumption?

Q2. Although edge addition shows benefits in specific Cora settings, its overall improvements over calibrated GCN-Jaccard remain limited. Could the authors clarify under what conditions the additional edge restoration stage is consistently beneficial?

1 comment
AuthorsOpenReview ↗

Response to Reviewer XGC7

Thank you for the time you gave to reviewing the paper and for the constructive feedback.

  • W1. Limited improvement over calibrated GCN-Jaccard. The addition stage is effective where it can act, and this comparison shows where that is (Q2); overall the two methods do not differ significantly. On citation-fresh (130 cells) the exploratory aggregate difference is +0.01 [-0.15, +0.17] pp, with 4 significant gains and 6 losses cell by cell; on citation-reproduction (18 cells) it is +0.14 [-0.06, +0.35] pp, with 1 gain and no loss. Neither interval excludes zero (Section 5.2, Table A1). This contrast measures the addition stage: calibrated GCN-Jaccard has GraphSieve's pruning stage and no addition stage. The ladder selects the same pruning threshold for both methods in 27 of 30 fresh and 25 of 30 reproduction calibrations, so in most replicates the contrast isolates that stage. The baseline is this strong because the protocol calibrated it, and the protocol is a contribution in its own right. On the two profiles, the ladder raises GCN-Jaccard's mean attacked-graph accuracy by +0.77 and +4.26 pp over its library default (Table 1). Against GCN-Jaccard at that default, GraphSieve's mean advantage is +0.78 and +4.41 pp (Section 5.1; both exploratory). GraphSieve's significant gains over the other methods are in item 1 of the general response.

  • W2. Trusted clean graph and validation labels. We use the trusted copy once, before any attack, only to choose the defense's settings. Training on that copy instead would work only if the graph never changed. Once it changes, the defender must work with the changed graph and cannot tell which edits are attacks, so the defense needs settings chosen in advance. The protocol provides them: each replicate's frozen configuration is applied unchanged to every attacked version of its graph, with no recalibration, no clean copy, and no evaluation attack instance (Section 3.2). The validation labels are those of each profile's split, and every calibrated method receives the same ones. Clean-only tuning (Ngo et al., 2026) makes the same assumption, and at that equal access the ladder adds +0.44 and +4.18 pp for GCN-Jaccard and +0.49 and +3.92 pp for GraphSieve (Table 1).

  • Q1. A realistic scenario for the clean-graph assumption. Any graph that keeps changing after it was last verified, such as a citation or social graph that receives edges from untrusted sources. The verified copy no longer matches the graph in use, the defender cannot tell which new edges are attacks, and verifying every new version is the cost that one frozen configuration avoids (W2). Our benchmark tests this with graphs changed by four families of edits, from random to adaptive (Section 4.1).

  • Q2. Conditions under which the addition stage is beneficial. GCN-Jaccard can only remove edges, so addition is the one stage that can act where an attacker deletes them, and every significant gain over calibrated GCN-Jaccard falls where deletions make up at least half of the attack budget. The gain is reproduced in one setting; beyond it the evidence does not show a consistent benefit across datasets or attacks, and we do not claim one.

    • Where the gains fall (post hoc). There are five, +0.51 to +0.89 pp, on Cora or CiteSeer, and the four on the fresh profile are all under pure deletion (Section 5.2, Table A24).
    • Where the gain is reproduced. Under deletion Metattack on Cora, calibration disables pruning for both methods, so the contrast is addition alone: +0.89 [+0.33, +1.45] and +0.74 [+0.19, +1.29] pp at the 15 and 25 percent budgets. Because these cells were singled out after the outcome, a follow-up with a design fixed in advance, new attack graphs, and new model seeds retested them, and it reproduces both gains, at +1.21 [+0.77, +1.65] and +0.93 [+0.26, +1.60] pp (Section 5.4, Table A19).
    • Where addition is not used. On PubMed, addition lowers validation accuracy on the ladder in every replicate of both profiles, by a mean of 1.27 and 1.03 pp (post hoc, Appendix C). Calibration therefore declines it, and GraphSieve and calibrated GCN-Jaccard are the same method there, building the same graph in all 42 fresh and 6 reproduction PubMed cells.
    • Where a high deletion share is not sufficient. All six significant losses are on fresh-profile Cora, where GraphSieve runs addition alone, at the 5 and 15 percent budgets, so each is a cell in which addition cost accuracy. None exceeds 0.65 pp, and four of the six sit at deletion shares of 0.50 or more (Table A25), so composition alone does not predict a benefit.
    • What limits the present rule. Under generalized DICE on Cora and CiteSeer, the candidate set contains most deleted edges, but similarity ranking recovers few (Section 5.4), so a better addition rule is the next step.

We rewrote many parts of the paper for clarity, and we welcome any further comments that would strengthen it.

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

This paper focuses on structural poisoning in graph data and proposes a defense called GraphSieve. This is a purification defense for homophilous graphs that prunes low-similarity edges and adds high-similarity missing edges. The parameters of the defense are chosen based on a calibration procedure using mean validation accuracy over a trusted clean graph. Experiments show this calibration also improves existing purification defenses. GraphSieve offers limited improvement over equally calibrated GCN Jaccard.

Critical strengths
  1. The structural poisoning problem is important and using attack agnostic calibration is novel.
  2. The experimental evaluation is thoughtful and informative.
Critical weaknesses
  1. The main weakness is the use of a trusted clean graph for calibration, which substantially limits practical applicability.
  2. The developed purification defense works only for homophilous graphs.
  3. The benefit of GraphSieve is less evident. Compared to calibrated GCN Jaccard and Prune-only, the gains are minimal (Table 2).
  4. The adaptive attack is not measuring the true robustness since it deletes the lowest similarity edges within the same class without considering the frozen thresholds or optimizing the defended loss. This means, when pruning is active, some of the edges that would be removed by the defense can also be the edges that were added by the attack. The current attack does not establish robustness against an attacker targeting the edges that survive pruning.
Questions for authors
  1. What practical setting provides a trusted clean copy of a graph for calibration while preventing direct training on that same copy?
  2. How does the adaptive attack perform when restricted to deleting edges that survive the frozen pruning rule? Can the attacker use the actual thresholds and evaluate damage after purification?
1 comment
AuthorsOpenReview ↗

Response to Reviewer TbBk

Thank you for taking the time to review our paper and for the constructive feedback.

  • W1. Trusted clean graph. We use the trusted copy once, before any attack, only to choose the defense's settings. Training on that copy instead would work only if the graph never changed. Once it changes, the defender must work with the changed graph and cannot tell which edits are attacks, so the defense needs settings chosen in advance. The protocol provides them: each replicate's frozen configuration is applied unchanged to every attacked version of its graph, with no recalibration, no clean copy, and no evaluation attack instance (Section 3.2). It holds up: GraphSieve gains significantly over the undefended GCN in 52 of 130 and 13 of 18 cells, with 6 and 0 losses (Table 2). Clean-only tuning (Ngo et al., 2026) makes the same assumption, and at that equal access the ladder adds +0.44 and +4.18 pp for GCN-Jaccard.

  • W2. Homophilous graphs only. Yes, by design: similarity-based editing presumes that informative edges join feature-similar nodes, and the evaluated graphs have edge homophily of 0.736 to 0.810. The limitations state that the evidence does not extend to heterophilous graphs.

  • W3. Benefit over calibrated GCN-Jaccard and Prune-only. GraphSieve improves significantly on GCN-SVD, RGCN, and the undefended GCN, and it can act where pruning cannot. Against calibrated GCN-Jaccard (+0.01 [-0.15, +0.17] and +0.14 [-0.06, +0.35] pp) and Prune-only (-0.06 [-0.12, +0.00] and +0.07 [-0.08, +0.22] pp; Table A1; 3/118/9 and 1/17/0 gains/NS/losses, Table 2) the overall difference is not significant. In detail:

    • GraphSieve gains significantly over GCN-SVD and RGCN (reference settings) in most cells and over the undefended GCN on CiteSeer and PubMed (Section 5.2).
    • GCN-Jaccard is a strong baseline because our protocol, a contribution in its own right, calibrated it: the ladder raises its mean attacked-graph accuracy by +0.77 and +4.26 pp over its library default, and also over clean-only tuning (Section 5.1).
    • GraphSieve can add edges, so it can act where an attacker deletes them, which pruning cannot. Its five significant gains over GCN-Jaccard all occur where at least half of the budget deletes edges, and the two under deletion Metattack on Cora were reproduced with new attack graphs and model seeds (+1.21 and +0.93 pp). Its six losses are all on Cora, none above 0.65 pp.
    • On PubMed, addition lowers validation accuracy on the ladder, so calibration declines it, and GraphSieve, GCN-Jaccard, and Prune-only are the same method there (Table 2).
    • A better addition rule is left to future work: under generalized DICE on Cora and CiteSeer, the candidate set contains most deleted edges, but similarity ranking recovers few (Section 5.4).
  • W4. The adaptive attack. As you note, the registered attack (L1) reads the similarity signal only, not the frozen thresholds. The revision adds two better-informed attackers as exploratory follow-ups, holding the defense at its frozen configurations and measuring accuracy after purification and training.

    • L2 deletes only edges that survive pruning and that addition does not re-admit, using the registered pruning grid; L3 does the same with each replicate's frozen threshold.
    • Against the undefended GCN over the family's 36 citation-fresh cells, GraphSieve records 20/16/0 at L1, 14/22/0 at L2, and 13/20/3 at L3 (gains/NS/losses; Section 5.5, Table A20).
    • Attackers that adapt only their deletions erode the gains without removing them, and the revised abstract replaces the submitted sentence on this attack, which reported no loss.
    • L2 and L3 keep the DICE insertions, and no attacker evaluated optimizes through purification and training jointly, so these results measure sensitivity to better-informed deletions and do not establish robustness (Sections 5.5 and 6).
  • Q1. A practical setting. Any graph that keeps changing after it was last verified, such as a citation or social graph that receives edges from untrusted sources. The verified copy no longer matches the graph in use, the defender cannot tell which new edges are attacks, and verifying every new version is the cost that one frozen configuration avoids (W1). Our benchmark tests this with graphs changed by four families of edits, from random to adaptive.

  • Q2. The attacker restricted to surviving edges. We ran this attacker: it is L3 under W4 (13/20/3), which uses each replicate's actual frozen threshold, with accuracy measured after purification and training and compared with the undefended GCN in the same cells. By dataset it gives 0/12/0 on Cora, 6/6/0 on CiteSeer, and 7/2/3 on PubMed, against 0/12/0, 8/4/0, and 12/0/0 under the registered attack; the three losses are the PubMed cells whose budget is spent entirely on deletions, and none exceeds 0.95 pp (Section 5.5 and Appendix D).

We rewrote many parts of the paper for clarity and welcome any further comments that would strengthen it.

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

In this paper, the authors look at the problem in how the different graph-purification defenses are evaluated. The reported benefit of a new "editing rule" (which edges to cut or add) often gets tangled up with the benefit of simply tuning its hyperparameters well. To separate the two, they propose a calibration procedure which picks a defense's hyperparameters using only a clean graph and some randomly perturbed versions of it, never the actual attack, and then applies this same procedure to every method so the comparison is fair. Their own defense, GraphSieve, combines the familiar similarity-based edge pruning of GCN-Jaccard with an edge-addition step that inserts high-similarity missing edges. They evaluate on Cora, Citeseer, and PubMed dataset.

Critical strengths
  1. The evaluation methodology is rigorous.
  2. The reporting is honest and reports where its method does and does not help.
Critical weaknesses
  1. The paper is not well written and is hard to follow.
  2. Novelty is limited.
  3. The proposed defense is not a clear advance even on its own terms.
  4. The setup rests on a premise the authors themselves flag as unrealistic. Their calibration assumes access to a trusted, clean copy of the graph, but as they note, a defender who actually possessed such a graph could simply train on it directly rather than defend a poisoned one.
Questions for authors
  1. How does GraphSieve differ from some prior arts like -- "Unveiling Adversarially Robust Graph Lottery Tickets" (TMLR)?
  2. What does the proposed calibration add over the equal-tuning protocol already used by Are Defenses for Graph Neural Networks Robust? (NeuRIPS 2022)
  3. Given that calibration requires a trusted clean graph, and you note a defender could train on it directly, what realistic deployment scenario makes attack-agnostic calibration preferable to using the clean graph?
1 comment
AuthorsOpenReview ↗

Response to Reviewer RL1M

Thank you for taking the time to review our paper and for the constructive feedback. Paired numbers give the fresh and reproduction profiles, in that order; a cell is one dataset under one attack setting.

  • W1. Writing. We accept this and revised the text as follows.
    • The abstract and introduction present the protocol first, and severity-ladder calibration is defined at its first mention.
    • Section 3.1 lists the two addition rules, and Section 5.2 gives calibrated GCN-Jaccard its own paragraph.
    • The main text uses one name for each method and stage (Section 3.1).
  • W2. Novelty. The pruning stage is GCN-Jaccard's rule. The novelty lies in the calibration protocol and the addition stage, which reuses the pruning score to add absent edges.
    • The protocol is a contribution in its own right. It selects the hyperparameters of every evaluated purification method by one rule, using no evaluation attack instance. A close precedent, G-RNA, scores architectures at a fixed budget; we select defense hyperparameters across several severities (Section 2).
    • The protocol is also what makes GCN-Jaccard a strong baseline. It raises its mean attacked-graph accuracy by +0.77 and +4.26 pp over its library default and by +0.44 and +4.18 pp over clean-only tuning (Table 1).
  • W3. Not a clear advance. GraphSieve improves significantly on three of the four methods it is compared with, and it adds a capability the fourth lacks. Against that fourth, calibrated GCN-Jaccard, the aggregate difference is +0.01 [-0.15, +0.17] and +0.14 [-0.06, +0.35] pp, and neither interval excludes zero (Section 5.2).
    • GraphSieve gains significantly over GCN-SVD in 117 of 130 and 14 of 18 cells, over RGCN at its reference settings in 94 and 17, and over the undefended GCN in 50 of the 86 fresh-profile CiteSeer and PubMed cells, with no significant loss in these comparisons.
    • GraphSieve can add edges, so it can act where an attacker deletes them, which pruning-only GCN-Jaccard cannot. Every significant gain over calibrated GCN-Jaccard falls where at least half of the attack budget deletes edges. A follow-up with new attack graphs and model seeds reproduced the two gains under deletion Metattack on Cora (+1.21 and +0.93 pp). The six significant losses are all on Cora, and none exceeds 0.65 pp.
    • The next step is a better addition rule: under generalized DICE on Cora and CiteSeer, the candidate set contains most deleted edges, but similarity ranking recovers few (Section 5.4).
  • W4. The trusted clean graph. We use the trusted copy once, before any attack, only to choose the defense's settings. Training on that copy instead would work only if the graph never changed. Once it changes, the defender must work with the changed graph and cannot tell which edits are attacks, so the defense needs settings chosen in advance. The protocol provides them: each replicate's frozen configuration is applied unchanged to every attacked version of its graph, with no recalibration, no clean copy, and no evaluation attack instance (Section 3.2). It holds up: GraphSieve gains significantly over the undefended GCN in 52 of 130 and 13 of 18 cells, with 6 and 0 losses (Table 2). Clean-only tuning (Ngo et al., 2026) makes the same assumption, and at equal access our protocol gives higher accuracy (W2).
  • Q1. Difference from "Unveiling Adversarially Robust Graph Lottery Tickets" (ARGS). Both works share the homophily premise. ARGS seeks sparse graph lottery tickets: it iteratively prunes the adjacency matrix together with the GNN weights by optimizing a loss that encodes homophily and uses training labels and test pseudo-labels. GraphSieve edits the graph once, by a rule with two frozen thresholds, before a standard GCN is trained. It can also add edges, and its configuration is fixed before the attacked graph is seen. We did not evaluate ARGS; Section 2 now cites it and states the difference.
  • Q2. What calibration adds over Mujkanovic et al. (NeurIPS 2022). Mujkanovic et al. tune each defense so that clean accuracy is kept while robustness to their adaptive attacks improves, which uses attack outcomes at selection time, and they vary the attacker's knowledge. We give selection no evaluation attack instance, apply one rule to all purification methods, and vary the rule. Table 1 and Appendix C give the comparisons, including where the protocol trails.
  • Q3. A realistic deployment scenario. Any graph that keeps changing after it was last verified, such as a citation or social graph that receives edges from untrusted sources. The verified copy no longer matches the graph in use, the defender cannot tell which new edges are attacks, and verifying every new version is the cost that one frozen configuration avoids (W4). Our benchmark tests this with graphs changed by four families of edits, from random to adaptive (Section 4.1).

We rewrote many parts of the paper for clarity, and we welcome any further comments that would strengthen it.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the four reviewers for their time and constructive feedback. Three concerns recur: what GraphSieve adds beyond calibrated GCN-Jaccard, the trusted clean graph, and the adaptive attack. Analyses run after the registered study are labeled exploratory or post hoc.

Our position. The paper contributes a calibration protocol and a defense.

  • Protocol. Severity-ladder calibration is a contribution in its own right, and it is what makes GCN-Jaccard a strong baseline: in exploratory ablations it raises GCN-Jaccard's mean attacked-graph accuracy by +0.77 and +4.26 pp over its library default and by +0.44 and +4.18 pp over clean-only tuning (citation-fresh and citation-reproduction; Section 5.1).
  • Calibrated GCN-Jaccard. GraphSieve does not improve on it overall (last row of the table). Its mean advantage is +0.78 and +4.41 pp over GCN-Jaccard at its library default and +0.01 and +0.14 pp under equal calibration, so nearly all of the first margin is calibration's.
  • What addition can do. GCN-Jaccard only prunes, so it has no response where an attacker deletes edges. GraphSieve can add edges, and all five of its significant gains over calibrated GCN-Jaccard occur where at least half of the attack budget deletes edges. A follow-up with new attack graphs and model seeds reproduces the two under deletion Metattack on Cora (Section 5.4). On PubMed, calibration declines addition and the two are the same method.
  • Next step. A better addition rule is left to future work. Under generalized DICE on Cora and CiteSeer, the candidate set contains 52 to 82 percent of the deleted edges, but similarity ranking with the true deletion count recovers only 0.5 to 4.2 percent (Section 5.4).

1. GraphSieve against the other methods. Each entry gives the aggregate paired effect that Reviewer 3Xfx requested (exploratory; 95 percent interval over 10 replicates; Table A1), then the registered W/NS/L counts of Table 2.

GraphSieve minusCitation-fresh (130 cells)Citation-reproduction (18 cells)
Undefended GCN+0.82 [+0.64, +1.01]; 52/72/6+6.73 [+6.01, +7.45]; 13/5/0
RGCN (reference settings)+4.38 [+3.87, +4.88]; 94/36/0+8.18 [+7.52, +8.83]; 17/1/0
GCN-SVD+6.34 [+5.90, +6.78]; 117/13/0+2.71 [+1.92, +3.50]; 14/4/0
Calibrated GCN-Jaccard+0.01 [-0.15, +0.17]; 4/120/6+0.14 [-0.06, +0.35]; 1/17/0

2. The trusted clean graph (all reviewers). We use the trusted copy once, before any attack, only to choose the defense's settings. Training on that copy instead would work only if the graph never changed. Once it changes, the defender must work with the changed graph and cannot tell which edits are attacks, so the defense needs settings chosen in advance. The protocol provides them: each replicate's frozen configuration is applied unchanged to every attacked version of its graph, with no recalibration, no clean copy, and no evaluation attack instance (Section 3.2). The table above shows that it holds up. Clean-only tuning (Ngo et al., 2026) makes the same assumption, and at that equal access the ladder gives higher mean attacked-graph accuracy. Sharing one trusted copy also makes the comparison controlled, since every method receives the same information.

3. The adaptive attack (Reviewers TbBk and 3Xfx). The registered attack read the similarity signal but not the frozen thresholds. The revision adds two better-informed attackers as exploratory follow-ups, with the defense held at its frozen configurations.

AttackerGraphSieve vs. undefended GCN, W/NS/L (36 citation-fresh cells)
L1, registered: reads the similarity signal20/16/0
L2: deletes only edges the defense neither prunes nor re-admits, reading the registered pruning grid14/22/0
L3: the same, reading each replicate's frozen threshold13/20/3

Attackers that adapt only their deletions erode the gains without removing them. The three L3 losses are PubMed cells whose budget is spent entirely on deletions, and none exceeds 0.95 pp (Section 5.5, Appendix D). No evaluated attacker optimizes through purification and training jointly, so these results measure sensitivity to better-informed deletions and do not establish robustness.

4. Changes in the revised PDF. The main text is 10 pages, with new text in blue; section order and main-text tables and figures are as submitted. Severity-ladder calibration is defined where it is first named (abstract, Section 1, Section 3.2). Section 3.1 lists the two addition rules; the main text uses one name per concept. Section 5.2 has a new paragraph that locates every significant gain and loss against calibrated GCN-Jaccard. Appendix Tables A1, A17, A18, and A20 are new, so the other appendix tables are renumbered.

We rewrote many parts of the paper for clarity, and we welcome any further comments that would strengthen it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.