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

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.