KCES: Training-Free Defense for Robust Graph Neural Networks via Kernel Complexity
This addresses the problem of securing GNNs against adversarial perturbations for applications in graph-based tasks, offering a principled and efficient solution, though it is incremental as it builds on existing defense strategies.
The paper tackles the vulnerability of Graph Neural Networks (GNNs) to adversarial attacks by proposing KCES, a training-free defense framework that prunes edges based on a novel kernel complexity metric, resulting in enhanced robustness and outperforming state-of-the-art baselines in experiments.
Graph Neural Networks (GNNs) have achieved impressive success across a wide range of graph-based tasks, yet they remain highly vulnerable to small, imperceptible perturbations and adversarial attacks. Although numerous defense methods have been proposed to address these vulnerabilities, many rely on heuristic metrics, overfit to specific attack patterns, and suffer from high computational complexity. In this paper, we propose Kernel Complexity-Based Edge Sanitization (KCES), a training-free, model-agnostic defense framework. KCES leverages Graph Kernel Complexity (GKC), a novel metric derived from the graph's Gram matrix that characterizes GNN generalization via its test error bound. Building on GKC, we define a KC score for each edge, measuring the change in GKC when the edge is removed. Edges with high KC scores, typically introduced by adversarial perturbations, are pruned to mitigate their harmful effects, thereby enhancing GNNs' robustness. KCES can also be seamlessly integrated with existing defense strategies as a plug-and-play module without requiring training. Theoretical analysis and extensive experiments demonstrate that KCES consistently enhances GNN robustness, outperforms state-of-the-art baselines, and amplifies the effectiveness of existing defenses, offering a principled and efficient solution for securing GNNs.