Search papers, labs, and topics across Lattice.
To bypass the heavy computational overhead and heuristic nature of adversarial GNN training, this work derives an edge-level Kernel Complexity score from a Gram matrix-based generalization error bound to identify and prune structurally malicious edges. By targeting edges that disproportionately inflate graph kernel complexity, the method purges adversarial perturbations as a training-free, model-agnostic preprocessing step. Across diverse attack settings and large-scale graphs, this sanitization technique consistently outperforms standard robust baselines without requiring model retraining.
Structural attacks on GNNs can be systematically neutralized without retraining simply by pruning the specific edges that disproportionately inflate the graph's kernel complexity.
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.
