Graph neural networks defended from attacks by pruning risky edges
Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
Machine LearningArtificial Intelligence
Summary
Graph neural networks can be tricked by attackers who change the connections between data points. The authors propose a way to find and remove the most suspicious connections without needing to retrain the model. They use a new scoring method that measures how much each edge changes the network’s complexity and score. Removing edges with high scores helps protect the network from attacks, is fast to do, and works well on large datasets.
What this means in practice
- •For network security teams: Reduce risks of tampered graph data in network analysis by removing suspicious edges identified before model use.
- •For social media platform engineers: Improve robustness of graph models used to detect fake accounts or misinformation by preprocessing graph connections without retraining.
Authors
Yaning Jia, Shenyang Deng, Yaoqing Yang, Chiyu Ma, Wenxuan Xu, Soroush Vosoughi
Abstract
Graph Neural Networks (GNNs) have achieved remarkable success across diverse applications, yet they remain highly vulnerable to adversarial attacks that maliciously perturb graph structure. Existing defenses often lack rigorous theoretical grounding, rely on attack-specific heuristics, or require costly retraining procedures such as adversarial training. To address these limitations, we propose Kernel-Complexity Edge Sanitization (KCES), a training-free and model-agnostic framework for defending against structural attacks. KCES is built upon Graph Kernel Complexity (GKC), a principled metric derived from the graph Gram matrix that appears in a generalization upper bound on the GNN test error. From this bound, we define an edge-specific KC score that quantifies each edge's structural influence via its induced change in GKC. KCES then identifies and prunes high-KC edges, which are empirically enriched with adversarial perturbations under structural attacks, to mitigate their harmful impact. Computationally efficient and scalable, KCES operates as a lightweight preprocessing step without retraining and can be seamlessly integrated with existing defenses. Extensive experiments demonstrate that KCES consistently outperforms representative robust baselines across diverse attack settings and scales effectively to large graphs. Supported by theoretical analysis and extensive empirical validation, KCES provides a principled and efficient framework for securing GNNs. Our code is available at https://github.com/karpning/KCScore.