acceptodds
Under review as a conference paper at ICLR 2027

Curvature Finds the Poison: One-Shot Adversarially Robust Graph Lottery Tickets

Abstract

Graph lottery tickets, a sparse adjacency matrix paired with a sparse graph neural network, deliver the inference and memory savings of pruning at little cost to clean accuracy. Their robustness, however, is brittle. When an adversary flips a small number of edges before training, such a ticket loses a large amount of accuracy. The only existing remedy restores robustness, but only by pruning and retraining many times, by assuming that neighbours share a label, and by relying on pseudo-labels. We show that a single second-order measurement of the loss on the observed graph is enough. Curvature-Aware Adversarial Winning Tickets (CA-AWT) estimates the Hessian diagonal once after a short warm-up and derives both masks from it. Weights whose removal would raise the loss are kept and edges with high curvature are removed, because an injected adversarial edge is precisely one along which the loss is fragile, so the edge ranking acts as an attack detector. This is what a learned mask cannot see. Averaged over three poisoning attacks and four perturbation rates, curvature recovers 88% of the injected edges and over 98% at high sparsity, while a mask learned by standard sparsification recovers 30%, below random pruning. A teacher distilled from the curvature-cleaned graph, a global cross-layer budget and a budget schedule on the fixed ranking complete the recipe. The resulting sparse subnetwork carries Lipschitz, complexity and PAC-Bayes generalization guarantees that hold regardless of how the mask is chosen. Across citation graphs of increasing scale, one-shot CA-AWT beats the standard graph lottery ticket in 98% of cells and matches the only robust method, which prunes and retrains many times, while assuming nothing about homophily. The detector transfers unchanged to a strongly heterophilous graph.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Lottery Tickets, Adversarial Attack, Robustness, Prunning

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 3 reviews, above 27% of the others.
Reviewer_faSSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes CA-AWT, a one-shot way to find sparse graph lottery tickets that stay robust when the graph has been poisoned. It computes the loss curvature once after a short warm-up and uses it for both masks: weights with high curvature are kept, and edges with high curvature are removed, on the idea that injected edges are where the loss is most sensitive. A teacher trained on the cleaned graph is then distilled into the sparse ticket. On citation graphs under several poisoning attacks, the method beats UGS almost everywhere and roughly matches the iterative ARGS method, removing about 88% of injected edges compared with about 30% for a learned mask.

Critical strengths
  1. A simple, cheap, and empirically strong edge-ranking signal with a clear contrast to learned masks.

  2. The coverage analysis is correct and verified empirically. The paper also reports where the method fails. The ablations are per-component and per-budget, and the hyper-parameter sensitivity is reported.

Critical weaknesses

1. The edge detector is not shown to detect adversarial edges, and its theoretical justification does not hold.

The curvature score is non-zero only on entries within L−1L-1 hops of a labelled node (Prop. 1), and the paper itself notes that DeepRobust attacks concentrate there and that high curvature means "influential, not malicious" (A.5). At r≥13r\ge13 the cut removes 49–62% of edges against roughly 70% coverage, so near-perfect recall (e.g., 100% in Table 9) is close to what any label-proximity ranking would achieve. Yet the paper omits structural controls (distance to training nodes, degree, Jaccard/feature dissimilarity) and threshold-free metrics (AUROC/AUPR, precision at a cut equal to the injected share). The mechanism is also unsupported. Prop. 2 discards the first-order term and the absolute values by appealing to a converged minimum, but aa is never optimized, so a=1a=\mathbf 1 is not stationary in aa. Moreover, a unit removal is not a small perturbation. Finally, no adaptive attacker is evaluated, although by Prop. 1 perturbations placed outside the coverage set are invisible to the detector by construction.

2. Parity with ARGS rests mainly on an expensive distillation component.

Without the teacher, CA-AWT reaches 73.4 / 74.8 / 70.3 on Cora at r=5/13/19r=5/13/19 (Table 11), several points below ARGS (about 79.9 / 76.8 / 72.8 from Table 1). The gap is closed by a dense teacher selected from up to 20 dense trainings on validation, a component ARGS does not receive. The "one-shot, fraction of the cost" claim lacks wall-clock or FLOP evidence, and the paper does not report ARGS or UGS with the same cleaned teacher. It is also unclear whether the baseline numbers were re-run on identical poisoned graphs, splits, and seeds. The unusually large teacher gain at r=1r=1 (+14 points) further suggests that the no-teacher pipeline may be undertrained. On the theory side, Theorem 1's proof applies the e−αte^{-\alpha t} decay only to pruned coordinates, while kept coordinates keep a non-decaying 2ηL/n2\eta L/n term, so the TT-independent bound does not follow. Prop. 3 bounds by ∏∥Wio∥F\prod\|W^o_i\|_F rather than the dense model's Lipschitz constant, so "the certificate never shrinks" is not established.

Questions for authors
  1. Please report the recall (and AUROC/AUPR) of simple structural rankings at the same budgets: (i) distance to or incidence on training nodes; (ii) endpoint-degree-based ranking; (iii) Jaccard or cosine feature dissimilarity.

  2. Please also report the recall of the curvature score restricted to the covered set, compared with a random ranking within the covered set. If curvature does not clearly beat these, the core claim needs to be reframed.

  3. Precision at small budgets. What is the precision or recall of the curvature ranking at a cut equal to the injected share, for each attack? Baseline provenance. Were UGS and ARGS re-run on exactly the same poisoned graphs, splits and seeds, or copied from the ARGS paper? If copied, how were the MetaAttack and Meta-PGD graphs matched?

  4. What accuracy do ARGS (and UGS) reach when given the same curvature-cleaned dense teacher? What does a dense GCN trained on the curvature-cleaned graph alone reach, with no sparsity? Please also give end-to-end wall-clock and FLOPs for CA-AWT (including all 20 teacher candidates) against ARGS.

  5. Why is the teacher gain about +14 points at r=1r=1? What is the accuracy of the no-teacher ticket at r=1r=1 compared with a dense GCN on A′A'?

  6. For Theorem 1, please address the issue with the kept coordinates. As I read the proof, the decaying factor applies only to pruned coordinates.

  7. Is CA-AWT robust to an adaptive attack, for example perturbations placed outside the coverage set, or a curvature-regularized PGD? ARGS reports results under an adaptive attacker.

6 comments

Thank you for a review that found two errors in our proofs and named the right control for our main claim. We ran what you asked for. All numbers are measured.

The coverage argument. You are right. The score is nonzero only for edges within one hop of a labelled node. On our 24 poisoned graphs (Cora and Citeseer, three attacks, four rates) this coverage holds 76% of the edges (67.5 to 84.8 by attack; the 70% in the paper is Cora under PGD only) and 99.6% of the attacker's edges. A random ranking of the covered edges removes qmin⁡(1,pe/c)q\min(1,p_e/c) of the attacker's edges, which is 29.8%, 64.1% and 82.1% at r=5r = 5, 13 and 19. Measured, a random ranking of the covered edges removes 29.7%, 64.4% and 82.4%. The curvature ranking removes 84.6%, 97.3% and 98.9% of the covered attacker edges at the same budgets. So the near-perfect recall at r=13r = 13 and r=19r = 19 is indeed mostly a coverage effect, and we will stop presenting it as evidence of detection. The informative test is a tight cut.

The controls section. Fourteen rankings on the same 72 poisoned graphs, same warm-up, same aggregation over the two directions of each edge. P@k is the precision when we remove exactly as many edges as the attacker added (random gives 9.8). Recall and FPR, the share of clean edges removed, are at r=5r = 5, where the cut is 22.6%.

RankingAUROCAUROC on covered edgesAUPRP@kRecall at r=5FPR at r=5
Curvature (ours)0.9120.8880.49850.884.316.2
First-order, ∣guv∣\lvert g_{uv}\rvert0.8960.8660.46748.279.916.7
Learned mask, largest values first0.5380.5480.34540.948.920.0
Distance to training nodes, nearest first0.8950.8630.39240.587.915.8
Incident on a training node0.8920.8630.39140.587.915.8
Endpoint degree, high first0.4150.3450.0853.29.523.8
Endpoint degree, low first0.5850.6550.1127.425.222.8
Jaccard dissimilarity0.8550.8510.34638.769.717.5
Cosine dissimilarity0.8550.8520.34738.769.617.5
Random within the covered set0.6310.5010.12812.529.721.9
Random0.5040.5040.1019.922.922.6

What this shows. Curvature is first on every threshold-free metric and at the tight cut. It is far above random within the covered set (0.631 AUROC, and 0.501 on the covered edges themselves, as it must be), so the coverage alone does not produce the ranking. Against your label-proximity control the result is mixed and we say so. Curvature is ahead by 10.3 points of precision at the tight cut (56 of 72 graphs) and by 0.106 AUPR, but only by 0.017 AUROC (52 of 72), and at r=5r = 5 the proximity rule removes slightly more attack edges (87.9 against 84.3) at a slightly lower false-positive rate. So at the budgets of our main experiments, a proximity rule reaches the recall we reported. Curvature's advantage is at tight cuts. By attack, curvature leads proximity under PGD (0.954 against 0.921 on Cora) and MetaAttack (0.936 against 0.910) and is behind or level under Meta-PGD (0.842 against 0.863 on Cora, 0.856 against 0.856 on Citeseer).

Precision at a cut equal to the injected share, per attack. Random equals the injected share, 7.5 to 10.9%.

5%10%15%20%
Cora, PGD55.053.959.059.4
Cora, MetaAttack51.057.959.459.7
Cora, Meta-PGD23.840.345.645.0
Citeseer, PGD48.655.963.459.0
Citeseer, MetaAttack49.252.761.361.3
Citeseer, Meta-PGD26.639.742.948.8

What we change. "Attack detector" leaves the abstract. The paper will say that the ranking removes injected edges with precision well above every structural control at tight cuts, that at the lattice budgets its recall is matched by a proximity rule, and that recall at wide cuts is not evidence of detection on its own.

Does the parity rest on the teacher, and what does ARGS reach with the same teacher

You asked the decisive question, and the answer is yes. We ran ARGS and UGS with our curvature-cleaned teacher, and we report a dense GCN on the cleaned graph with no sparsity.

Setting. Mean over attacks and rates, three seeds, ± standard deviation over seeds. "Alone" is the published curve on the same basis. The teacher is the dense GCN trained on the graph cleaned at the budget our validation selects; all three students distil from the same one. The teacher's soft labels are distilled into ARGS and UGS the same way they are into our own student, with the baselines' other settings left at their released defaults; the full configuration will be given in the appendix.

DatasetrARGS aloneARGS + our teacherUGS aloneUGS + our teacherour ticketthe teacher itself
Cora579.879.7 ± 0.0567.574.6 ± 1.0380.377.1
Cora1376.977.9 ± 1.0163.871.2 ± 0.8776.877.1
Cora1973.075.5 ± 0.8161.667.4 ± 0.9574.277.1
Citeseer574.374.9 ± 0.92––72.672.0
Citeseer1373.074.1 ± 1.2662.168.4 ± 1.4372.172.0
Citeseer1971.773.2 ± 0.50––72.072.0
PubMed1384.082.4 ± 0.0953.172.3 ± 0.9881.783.1

Three things follow, and the paper will say all three.

  1. With the same teacher, ARGS is ahead of our ticket. By 1.2 to 1.3 points on Cora at r=13r = 13 and 19, by 1.2 to 2.3 on Citeseer, by 0.7 on PubMed, and behind only by 0.6 at Cora r=5r = 5. Our Table 1 compares a ticket with a teacher against ARGS without one. Given the teacher, the iterative method wins on accuracy. Our advantage is that we reach the same neighbourhood with one scoring pass and one teacher instead of twenty prune-and-retrain rounds. We will state the comparison this way.

  2. The teacher's gain follows how far the student sits below the teacher. On Cora, ARGS gains −0.1, +1.0 and +2.5 at r=5r = 5, 13 and 19 as it falls further below the 77.1 teacher. UGS, far below it, gains 5.8 to 7.4 points on Cora and Citeseer and 19.2 on PubMed. Our own ticket without the teacher gains 6.4 at r=5r = 5 and 2.1 at r=13r = 13. One rule covers all three methods. As a check, our learned-magnitude arm, which is a UGS-style mask inside our pipeline, reaches 63.9 on Cora at r=13r = 13 against 63.8 for the published UGS curve.

  3. The cleaning is worth two separate increments, and both come from the curvature ranking. On Cora at r=13r = 13: a UGS-style student on the poisoned graph with a teacher also trained on the poisoned graph reaches 63.9. The same student with the teacher trained on the cleaned graph reaches 71.2. A student whose own graph is also cleaned reaches 76.8. Cleaning the teacher's graph is worth about 7 points and cleaning the student's graph about 6 more. UGS with our teacher stays 3.7 to 9.4 points below our ticket on every graph. That gap is the direct contribution of the edge criterion.

The dense model against the ticket. Our sweep already records the teacher at every cell, so this needs no new run. Over all 1,800 runs the ticket is 0.14 points above the dense cleaned-graph model. By budget, the ticket is ahead of it up to r=11r = 11 (91% of the weights removed, +0.53), behind by 0.46 at r=13r = 13 (94.5%) and by 2.15 at r=19r = 19 (98.6%). So the cleaning carries the robustness, and the sparsity is free up to about 91% of the weights and costs accuracy beyond that. This is the claim the paper should have made, and will make.

What does the whole procedure cost, and why the teacher gain is +14 at r = 1

What is one-shot. The scoring step. We estimate the Hessian diagonal once and read both masks from the two fixed rankings. The full procedure also trains up to twenty dense teachers to choose the cleaning budget. The paper will say this plainly, and the sentence that the search costs "no more than a teacher retrained at every budget" is replaced by the numbers below.

Cost, measured. Cora, PGD 5%, GCN with 512 hidden units, budget r=13r = 13, same CPU. One supervised epoch of this backbone on this graph takes 0.092 s. ARGS, from its released code, runs 300 mask-learning epochs plus 300 retraining epochs per budget and reaches budget 13 only through rounds 1 to 13; its code needs CUDA, so its wall clock below is its epoch count times the measured epoch time. FLOPs are a fixed multiple of epochs for one model on one graph, so we report epochs.

Methodwall clockepochsaccuracy at r=13, Cora
ARGS, rounds 1 to 13719 s7,80076.9
ARGS + our teacher (ARGS + scoring + teacher search)about 1,260 sabout 11,80077.9
UGS + our teacher––71.2
dense GCN on the cleaned graph (the teacher)27 s20077.1
ours, scoring pass alone6.2 s––
ours, one ticket, teacher budget already chosen99 s53076.8
ours, one ticket including all 20 teacher candidates635 s4,53076.8
ours, one ticket with the early-stopped searchabout 430 sabout 3,00076.8
ours, whole lattice of 20 budgets2,513 s14,600–
ARGS, whole lattice of 20 budgets1,106 s12,000–

The scoring pass is 6.2% of one ticket. One ticket at a chosen sparsity is 7.3 times cheaper than reaching it iteratively. With the full teacher search included, the two are level. Over the whole lattice we are 2.3 times slower, because ARGS obtains every budget on the way to the last one. The efficiency claim is restricted to this and the "fraction of the cost" wording is removed. The early-stop rule, stop after five budgets without a validation gain, re-derived from the 90 stored candidate tables, keeps the same budget in 81 of 90 cases at 62% of the cost. Searching only the first ten budgets costs 0.22 points of teacher accuracy.

The +14 gain at r = 1. Our stored no-teacher sweep answers this without a new run. Cora, mean over three attacks, four rates and three seeds:

modelaccuracy
dense GCN on the poisoned graph A′A'64.6
our ticket at r=1r = 1 without the teacher66.5
the teacher, a dense GCN on the graph cleaned at the selected budget77.1
our ticket at r=1r = 1 with the teacher80.2

The no-teacher ticket is 1.9 points above the dense poisoned model, so it is trained, not undertrained. The gain is a cleaning gap. At r=1r = 1 the student's own graph has lost only 5% of its edges, while the teacher's graph has lost a median of 34% (the selected rtr_t has median 8), and distillation carries that difference across. At r=13r = 13 the student's own cut, 48.7%, is larger than the teacher's, and the gain shrinks to 2.1 points (76.8 against 74.7). Citeseer behaves the same way: 53.5, 56.4, 72.0 and 72.4 at r=1r = 1. We will replace the "U-shaped" description with this explanation.

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

The paper tries to find doubly-sparse graph lottery tickets (sparse graph + sparse weights) that survive structure poisoning, in one shot. CA-AWT runs a short warm-up and then estimates the Hessian diagonal once with Hutchinson probes. It keeps weights with high OBD saliency and drops edges with high summed directed curvature. On top of that, it adds a global cross-layer weight budget, an annealed mask with a budget ramp, and distillation from a dense teacher trained on the cleaned graph.

Critical strengths
  • The research question is important. Asking whether a robust GLT can be found in one shot makes sense, and dropping ARGS's homophily prior and pseudo-labels is a worthwhile goal.
  • The proposed method is simple and cheap. A single Hessian-diagonal estimate ranks both weights and edges, so each pass costs little.
Critical weaknesses
  • The mechanism is a heuristic, and the paper partly undercuts it. The authors say attackers pick the flips that raise training loss most, so the loss should be fragile along injected edges. But Metattack, PGD and Meta-PGD optimise bilevel or self-training objectives, mostly on unlabeled nodes. They don't target the defender's loss curvature.
  • Simple baselines are missing, and the comparator is weak. The only edge-scoring comparator is a learned mask that prunes the smallest values. The paper itself argues that injected edges get large mask values. So "prune the largest mask values" or "prune the largest $| {\partial L} / {\partial a} | $" are obvious first-order detectors. Neither is tested.
Questions for authors
  • Please report precision, recall and AUROC against inverted first-order scores, distance to labelled nodes, degree and Jaccard. If curvature doesn't clearly win, the core claim changes.
  • Can you test an adaptive attacker, such as PGD with a curvature penalty or perturbations outside the coverage set?
  • Please clarify Prop. 2's assumptions, given that a isn't at a stationary point.
  • Were ARGS and UGS re-run with the same splits and seeds? Please add their variances and paired significance tests.
4 comments

Reply to the mechanism, the missing simple baselines, and whether curvature clearly wins

Thank you for the review. You asked for specific baselines and a specific condition. We ran the baselines, and we report the condition as it came out.

Point 2.1, the mechanism. You are right. The sentence "the attacker picks the flips that raise the training loss most" describes PGD, which maximises a training objective, but not MetaAttack or Meta-PGD, which follow meta-gradients of a self-training objective on unlabelled nodes. We remove it. The paper will state the sharpness of injected edges as a hypothesis and test it. The test comes out along the line you draw. The AUROC of our ranking against the attacker's edges is 0.954 under PGD, 0.936 under MetaAttack and 0.842 under Meta-PGD on Cora (0.950, 0.933, 0.856 on Citeseer). Detection gets worse in the same order in which the attacker's objective moves away from the defender's training loss.

Points 2.2 and 2.3, the controls. Fourteen rankings on the same 72 poisoned graphs (Cora and Citeseer, three attacks, four rates, three seeds), same warm-up, same aggregation over the two directions of each edge. Only the score changes. P@k is the precision when we remove exactly as many edges as the attacker added (random gives 9.8). Recall and FPR, the share of clean edges removed, are at r=5r = 5, where the cut is 22.6% (random gives 22.6 for both).

RankingAUROCAUROC on covered edgesAUPRP@kRecall at r=5FPR at r=5
Curvature (ours)0.9120.8880.49850.884.316.2
Curvature + first-order term0.9040.8770.48349.982.216.4
First-order, ∣guv∣\lvert g_{uv}\rvert largest first0.8960.8660.46748.279.916.7
First-order, most helpful gradient first0.7480.7280.37543.768.417.8
Learned mask, largest values first0.5380.5480.34540.948.920.0
Learned mask, smallest first (UGS rule)0.4620.4520.18525.842.320.3
Distance to labelled nodes, nearest first0.8950.8630.39240.587.915.8
Incident on a labelled node0.8920.8630.39140.587.915.8
Endpoint degree, high first0.4150.3450.0853.29.523.8
Endpoint degree, low first0.5850.6550.1127.425.222.8
Jaccard dissimilarity0.8550.8510.34638.769.717.5
Cosine dissimilarity0.8550.8520.34738.769.617.5
Random within the covered set0.6310.5010.12812.529.721.9
Random0.5040.5040.1019.922.922.6

Your two first-order detectors. Neither matches curvature. Pruning the largest learned-mask values gives AUROC 0.538. Pruning the most helpful gradient gives 0.748. The inverted mask does beat the UGS rule (0.462), which supports our reading of why the magnitude rule fails, and on Cora under PGD it reaches 0.790, so the effect in our Figure 1 is real there but does not hold across attacks. We will soften that caption. The size of the gradient, ∣guv∣\lvert g_{uv}\rvert, is a strong detector at 0.896, and curvature improves on it in 69 of 72 graphs. Keeping both terms together is slightly worse than curvature alone.

Does curvature clearly win. Against degree, Jaccard, cosine, both first-order detectors and random within the covered set, yes. Against distance to labelled nodes, partly. Curvature is ahead by 10.3 points of precision at the tight cut (56 of 72 graphs) and by 0.106 AUPR, but only by 0.017 AUROC (52 of 72), and at the budget r=5r = 5 the distance rule removes slightly more attack edges (87.9 against 84.3). We accept your condition and change the claim to what the numbers show. The ranking removes injected edges with precision well above every simple rule at tight cuts. At the lattice budgets its recall is matched by a proximity rule. "Attack detector" leaves the abstract.

Reply to the adaptive attackers

We ran both attackers you suggest, and one more that was needed to interpret them.

Setting. Cora, budget 10% of the clean edge count, which is 507 flips. Every graph is generated with our own PGD implementation (Xu et al. 2019, DeepRobust conventions) and defended with the paper's exact protocol: the teacher's cleaning budget is chosen on validation over rt=1r_t = 1 to 20, one teacher, tickets at r=5r = 5 and r=13r = 13, seed 0. "Dense" is a GCN with 512 hidden units trained on the poisoned graph with no defence. Recall is the share of the attacker's edges our ranking removes.

Two facts frame the results. First, the three published attacks place 99.6% of their edges inside the coverage, the set of edges within one hop of a labelled node. Second, an attacker restricted to the outside of the coverage cannot use the training loss at all, because every allowed flip has zero training-loss gradient (our Proposition 1). It must use a self-training objective on the unlabelled nodes. We give it that, and we also run the same self-training attacker without the restriction, so the effect of the restriction can be read off.

The curvature penalty is λ∑se\lambda\sum s_e over the flipped pairs. The curvature field is the Hessian diagonal of a GCN-512 after a 30-epoch warm-up on the current graph, refreshed every 25 attack steps. λ\lambda is set so the penalty gradient on a typical covered pair is κ\kappa times the 90th percentile of the attack gradient at step 0.

Attackinjecteddense, no defencechosen rtr_trecall at r=5ours at r=5recall at r=13ours at r=13
none, clean graph082.651–84.21–80.99
PGD, training-loss objective44064.991479.383.2099.176.66
PGD + curvature penalty, κ=0.5\kappa = 0.542961.37481.383.0598.177.67
PGD + curvature penalty, κ=2\kappa = 242460.761285.883.4599.176.06
PGD, self-training objective, any pair43978.37121.279.2336.276.46
PGD, self-training, outside the coverage only45677.9710.078.770.075.80

Three answers.

  1. Penalising curvature does not help the attacker. Recall stays at 81 to 86% at r=5r = 5 and 98 to 99% at r=13r = 13, the same as without the penalty, and the defended ticket recovers to 83 from an undefended 61. The reason is that the flips which raise the training loss most are the ones along which the loss is sharpest. The attacker cannot have one without the other.

  2. An attacker that bypasses the training loss evades the detector. With the self-training objective, recall falls to 21%, below random, and validation picks rt=1r_t = 1, so the defence does nothing it would not do on a clean graph. But this attacker is also four times weaker. It costs an undefended GCN 4.3 points, against 17.7 for the training-loss attacker, and the defended ticket loses 5.0 points relative to the clean ticket.

  3. Outside the coverage the detector is blind, as Proposition 1 says. Recall is exactly zero. The attack costs an undefended GCN 4.7 points and the defended ticket 5.4 points at r=5r = 5 and 5.2 at r=13r = 13.

What we conclude. We will state the exposure as a bound. An attacker that stays away from the labelled neighbourhoods gives up about three quarters of its damage, and what remains is not defended. The published MetaAttack and Meta-PGD graphs are detected at AUROC 0.93 and 0.85 because their meta-gradient flows through training on the labelled nodes. The simple self-training attacker above does not have that coupling, and it is the case our method does not cover. We will say this in the limitations.

Point 2.5. You are right. The first-order term does not vanish, and our proof borrowed an argument that only holds for trained weights. The revised Proposition 2 makes no stationarity assumption. It gives the exact second-order prediction for removing an edge, −guv+12(Hu→v,u→v+Hv→u,v→u)+Hu→v,v→u-g_{uv} + \tfrac12(H_{u\to v,u\to v} + H_{v\to u,v\to u}) + H_{u\to v,v\to u}, and states that our score equals twice this only when the gradient term and the cross term vanish and both curvatures are nonnegative. In general the score is a ranking proxy, and the paper will call it that. We also measured the effect of the dropped term. Adding it to the score changes AUROC from 0.912 to 0.904, so it changes the ranking very little. And in a direct deletion test on 18 Cora graphs, the score has rank correlation 0.935 with the size of the measured loss change after removing an edge, while the exact prediction has 0.992 with the signed change. So the score tracks deletion cost, but the exact prediction tracks it better, and we will say so.

Point 2.6, the baselines. ARGS's released code, run on the same poisoned graphs at its reported operating point on eight Cora and Citeseer graphs, reproduces its published accuracy within +0.13 to +1.15 points, so the ARGS values we compare against are if anything conservative toward ARGS. For PGD on Cora and Citeseer the poisoned graphs are the files shipped with ARGS, so graphs and splits are identical.

Point 2.6, variance and paired tests. The mean difference to ARGS over the lattice is 0.4 points in our favour. Our own standard deviation over seeds is 1.05 points on average (median 0.76, maximum 3.70), so a 0.4-point mean gap is well inside one seed spread. We therefore read the comparison with ARGS as parity and not as an advantage, as the paper says, and the revision will keep that wording. The comparison with UGS is a different matter. Paired cell by cell over all 400 cells of the lattice, three seeds averaged per cell, with a 95% bootstrap interval over cells and seeds and a two-sided Wilcoxon signed-rank test:

Comparisoncellsmean difference95% intervalp
ours minus UGS, all cells400+12.87[+12.14, +13.60]4.9e−67

We are ahead of UGS in 392 of 400 cells.

Thank you for your detailed responses and additional experiments. I have carefully gone through all of the responses and the new results, and have re-evaluated the paper on that basis. I will keep my original score for now, since the curvature cannot clearly win against distance to labelled nodes.

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

This paper introduces Curvature-Aware Adversarial Winning Tickets (CA-AWT), a framework for jointly extracting a sparse graph and sparse graph neural network from a structurally poisoned graph. It asks whether a single curvature-scoring pass can extract robust graph lottery tickets without the iterative pruning, pseudo-labeling, and homophily assumptions of prior approaches. The paper identifies how standard sparsification can preserve poisoned edges and motivates a unified curvature score for graph and model sparsity. The empirical ranking heuristic and broad evaluation are promising, but several advertised theoretical guarantees are unsupported as written, and the evaluation does not establish robustness to the full flip threat model, adaptive attacks, or the claimed end-to-end efficiency.

The paper states three main contributions: 1.A curvature criterion uses one Hessian-diagonal estimate after a short warm-up to score both masks. 2.A ticket-extraction framework combines a global cross-layer sparsity budget and a schedule over fixed rankings with distillation from a dense teacher trained on the curvature-cleaned graph. 3.The evaluation covers citation graphs of three scales under three poisoning attacks and four perturbation rates, and reports 88% average injected-edge recall, results tracking ARGS, and gains over UGS in 98% of evaluated cells.

Critical strengths

Problem significance. This paper addresses an important problem in graph learning: whether a robust graph lottery ticket can preserve the computational benefits of jointly sparsifying a graph and its GNN without retaining adversarially introduced structure. Efficiency and structural robustness are often studied separately, even though a sparse model may still inherit harmful edges from a poisoned graph. By bringing these goals together, the paper offers a useful direction for research on graph-learning systems that are both computationally efficient and reliable under structural threats.

Methodology novelty. The proposed method is innovative in using a single estimate of the Hessian diagonal to rank both weight and observed-edge masks under opposite rules: retain weights with high Optimal Brain Damage saliency and remove edges with high curvature. It turns this shared score into a concrete pipeline through a global cross-layer sparsity budget, an annealed schedule over fixed rankings, and distillation from a dense teacher trained on the curvature-cleaned graph. The joint procedure connects graph cleaning, model sparsification, and teacher-guided training. This is a meaningful design choice, although the stronger claim that curvature acts as an attack detector remains insufficiently established.

Evaluation. The experimental design is broad and systematic. It covers citation graphs of different scales, OGBN-ArXiv, and the heterophilous Chameleon dataset, and tests multiple poisoning attacks and perturbation rates. Component ablations isolate the contribution of key design choices, while comparisons with ARGS and UGS provide relevant baselines. Together, these complementary evaluations provide strong empirical support for the paper's reported edge-recall and accuracy results across the tested settings.

Writing. The paper is generally clear and easy to follow. Its progression from motivation to method and evaluation is coherent.

Critical weaknesses

Attack detection is partly supported. The main-text results provide real but limited support for the abstract claim. Section 6.2 reports 88% average recall of injected edges and more than 98% at high sparsity, compared with 30% for the learned mask. This shows that CA-AWT removes many known injected edges under the tested attacks. However, Section 6.5 reports that on Chameleon, removing high-curvature edges does not consistently improve accuracy, suggesting that the ranking can also remove useful edges. Because the paper reports injected-edge recall but not false positives on clean edges, it does not show that the score distinguishes malicious edges from benign but influential ones.

The deletion-cost interpretation is unverified. Section 3, Eq. (6), calls the summed curvature score the predicted cost of deleting an edge. But the paper presents no comparison between this prediction and the actual loss change after an edge is deleted. The ranking may be useful in the reported experiments, but the paper has not established that it measures deletion cost rather than serving as an empirical heuristic.

Writing clarity. Some sentences in the Introduction are unclear. On p. 1, the authors write: "Graph neural networks (GNNs) are the standard model for relational data (Kipf & Welling, 2017; Veličković et al., 2018; Hamilton et al., 2017), and as graphs grow to millions of nodes and edges, however, dense GNNs incur a heavy cost in memory, inference latency, and energy, which motivates a growing body of work on sparsification." The sentence is difficult to follow because the relation between its clauses is unclear. On p. 2, the authors write: "for an injected edge the two point in opposite directions." The phrase "the two" has no clear referent, and "opposite directions" is undefined. These wording problems obscure the motivation for the curvature score and reduce the precision of the discussion.

Questions for authors

Attack detection claim. Section 6.2 reports 88% average injected-edge recall and more than 98% at high sparsity, but Section 6.5 notes that removing high-curvature edges on Chameleon does not consistently improve accuracy. What evidence in the main text shows that the score distinguishes injected edges from benign but influential edges? Without a clean-edge false-positive rate, why should injected-edge recall be read as attack detection rather than influence-based pruning?

Edge-deletion cost. Section 3, Eq. (6), calls the summed curvature score the predicted cost of deleting an edge. What result shows that this ranking tracks the actual loss change after an edge is removed, rather than serving as an empirical heuristic?

One-shot cost and baseline evidence. Section 4.3 says that the curvature ranking is computed once, but the method selects its teacher-cleaning budget by training dense teachers at 20 candidate sparsity levels. What exactly is one-shot: the curvature-scoring step, or the complete end-to-end procedure? Since the candidate sweep requires additional teacher training, how is that cost counted in the claimed efficiency advantage over iterative ARGS? Separately, Section 6.1 reports a 0.4-point mean accuracy advantage over ARGS, while the table gives variability for CA-AWT but not for ARGS or UGS. Without corresponding baseline variance or paired uncertainty estimates, what evidence shows that this small mean gap reflects a reliable advantage rather than run-to-run variation?

3 comments

Thank you for the careful review. You are right that recall alone does not answer this. We have now run the missing controls. All numbers below are measured.

Why recall at high sparsity is not enough. The score is nonzero only for edges within one hop of a labelled node. We call this set the coverage. On our 24 poisoned graphs (Cora and Citeseer, three attacks, four rates) the coverage holds 76% of all edges and 99.6% of the attacker's edges. So at the budgets r=13r = 13 and r=19r = 19, where we cut 49% and 62% of the edges, even a random ranking of the covered edges removes 64% and 82% of the attacker's edges. Recall above 98% there is partly a coverage effect. The informative test is a tight cut, and a comparison against simple rules.

The controls. Fourteen rankings, same 72 poisoned graphs, same warm-up, same aggregation over the two directions of an edge. Only the score changes. P@k is the precision when we remove exactly as many edges as the attacker added (random gives 9.8). FPR is the share of clean edges removed at r=5r = 5, where the cut is 22.6% (random gives 22.6 for both recall and FPR).

RankingAUROCAUROC on covered edgesAUPRP@kRecall at r=5FPR at r=5
Curvature (ours)0.9120.8880.49850.884.316.2
First-order, ∣guv∣\lvert g_{uv}\rvert0.8960.8660.46748.279.916.7
First-order, most helpful gradient0.7480.7280.37543.768.417.8
Learned mask, largest values first0.5380.5480.34540.948.920.0
Learned mask, smallest first (UGS rule)0.4620.4520.18525.842.320.3
Closeness to labelled nodes0.8950.8630.39240.587.915.8
Endpoint degree, high first0.4150.3450.0853.29.523.8
Jaccard feature dissimilarity0.8550.8510.34638.769.717.5
Random within the covered set0.6310.5010.12812.529.721.9
Random0.5040.5040.1019.922.922.6

What this shows. Curvature is the best ranking on every threshold-free metric and at the tight cut. It is far above random within the covered set (0.912 against 0.631 AUROC, 50.8 against 12.5 precision), so the coverage alone does not explain the result. At the tight cut half of the removed edges are the attacker's. The honest part is the comparison with closeness to labelled nodes. Curvature wins by 10 points of precision at the tight cut and by 0.106 AUPR, but only by 0.017 AUROC, and at the budget r=5r = 5 the closeness rule removes slightly more attack edges (87.9 against 84.3) with a slightly lower false-positive rate. So at the budgets of our main experiments, a simple proximity rule reaches the same recall we reported. The advantage of curvature is at tight cuts, where precision matters.

Chameleon. Here the ranking has AUROC 0.834, precision 23.5% at the tight cut, and a false-positive rate of 22.7% at r=5r = 5, which is the cut itself. So on this graph the ranking still puts attack edges at the top, but at the main budgets it removes clean edges at the random rate. This is exactly the behaviour you describe, and we now give the number for it.

This would be an explanation about the "attack detector" term. The paper will say that the ranking removes injected edges with precision well above every simple rule at tight cuts, and that at the lattice budgets a proximity rule matches its recall. Every recall number will have the clean-edge false-positive rate next to it.

Is the score the cost of deleting an edge?

You are right, and we withdraw that claim. We also tested what the score actually tracks.

Why the claim was wrong. Our Proposition 2 dropped the first-order term because, at a converged model, the gradient is small. That holds for the weights, which are trained. It does not hold for the edge weights, which are fixed at one and never trained, so their gradient is not zero. Removing an edge is also a unit step, not a small change. The revised Proposition 2 gives the exact second-order prediction for removing an edge, including the gradient term and the cross term, and says plainly that our score equals it only when those two terms vanish. Eq. (6) will be called a ranking score, not a predicted cost.

The test. Cora, three attacks, 5% and 20%, three seeds, so 18 poisoned graphs. On each graph we sample 200 edges spread evenly over the deciles of our score. We delete each edge and measure the change in training loss at the warm-up weights. On three graphs we also fine-tune for 20 epochs after the deletion and compare with 20 epochs on the full graph. We report the Spearman rank correlation between each predictor and the measured change.

Predictorsigned change, fixed weightsabsolute change, fixed weightssigned, after fine-tuningabsolute, after fine-tuning
our curvature score0.5800.9350.2570.808
exact second-order prediction0.9920.6650.2280.465
absolute first-order term ∣guv∣\lvert g_{uv}\rvert0.6200.9850.2720.830
endpoint degree−0.0520.0470.0330.070

What this shows. The score ranks edges like the size of the measured loss change does, with correlation 0.935 at fixed weights (0.957 under PGD, 0.935 under MetaAttack, 0.913 under Meta-PGD) and 0.808 after fine-tuning. So it is not an arbitrary heuristic. But we must also say two things. The exact second-order prediction tracks the signed change almost perfectly (0.992). And the first-order term alone tracks the size of the change slightly better than our score (0.985 against 0.935). So the curvature score is not needed to predict deletion cost. Its value is as a detector, where it is ahead of the first-order term (0.912 against 0.896 AUROC, comment 1). Removing an attack edge raises the training loss on average, and removing a clean edge leaves it unchanged. That is the sign pattern of edges that help fit poisoned labels.

What is one-shot, what does it cost, and is the 0.4-point gap real?

Point 1.3. Both sentences are rewritten. The introduction now reads: "Graph neural networks are the standard model for relational data. As graphs grow to millions of nodes and edges, dense GNNs become costly in memory, inference latency and energy, which motivates a growing body of work on sparsification." The second sentence now reads: "A learned mask follows the first derivative, so an edge whose weight lowers the training loss receives a large mask value and is kept. Curvature asks a different question, how sharply the loss changes along the edge, and ranks such an edge for removal." The phrase "the two point in opposite directions" is gone.

What is one-shot. The scoring step. We estimate the Hessian diagonal once and read both masks from the two fixed rankings. The full procedure also trains up to twenty dense teachers to choose the cleaning budget. The paper will say this clearly, and the sentence that the search costs "no more than a teacher retrained at every budget" is replaced by the measured numbers below.

Cost, measured. Cora, PGD 5%, GCN with 512 hidden units, budget r=13r = 13, same CPU. ARGS runs 300 mask-learning epochs plus 300 retraining epochs per budget and reaches budget 13 only through rounds 1 to 13. Its wall clock is its epoch count times the measured time of one epoch of the same backbone on the same graph (0.092 s), because its code needs CUDA.

Whatwall clockepochs
ARGS, rounds 1 to 13719 s7,800
our scoring pass alone6.2 s–
our ticket, teacher budget already chosen99 s530
our ticket including all 20 teacher candidates635 s4,530
our whole lattice of 20 budgets2,513 s14,600
ARGS, whole lattice of 20 budgets1,106 s12,000

So one ticket at a chosen sparsity is 7.3 times cheaper than reaching it iteratively. With the full teacher search included the two are level. Over the whole lattice we are 2.3 times slower, because ARGS gets every budget on the way to the last one. The efficiency claim is restricted to this. Stopping the search after five budgets without a validation gain keeps the same choice in 81 of 90 cases at 62% of the cost.

Is the 0.4-point gap real. The mean difference to ARGS over the lattice is 0.4 points in our favour. Our own standard deviation over seeds is 1.05 points on average (median 0.76, maximum 3.70), so a 0.4-point mean gap is well inside one seed spread. We therefore read the comparison with ARGS as parity and not as an advantage, as the paper says, and the revision will keep that wording. The comparison with UGS is a different matter. Paired cell by cell over all 400 cells of the lattice, three seeds averaged per cell, with a 95% bootstrap interval over cells and seeds and a two-sided Wilcoxon signed-rank test:

Comparisoncellsmean difference95% intervalp
ours minus UGS, all cells400+12.87[+12.14, +13.60]4.9e−67

We are ahead of UGS in 392 of 400 cells.

Comments on the paper

1 comment

Hi Reviewers,

We are now near the end of the rebuttal period. If you haven't done so yet, please review the authors' responses and post a reply addressing whether their clarifications or new results resolve your concerns. Even if your score or recommendation remains unchanged, a brief note confirming what did or didn't shift your assessment—and why—is essential for the discussion and final decision. Thank you for your time and engagement.

Best regards,

Area Chair

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.