Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks

• URL: http://arxiv.org/abs/2609.09698v1
• Date: Wed, 09 Sep 2026 04:33:09 GMT
• Title: Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
• Abstract summary: Graph Neural Networks (GNNs) have achieved remarkable success across diverse applications, yet they remain highly vulnerable to adversarial perturb structure attacks.<n>Existing defenses often lack rigorous theoretical grounding, rely on attack-specific Kernels, or require costly retraining procedures such as adversarial training.<n>We propose Kernel-Complexity Edge Sanitization (KCES), a training-free and model-agnostic framework for defending against structural attacks.
• Score: 35.52484692340263
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Defending against Model Extraction for GNNs with Model Reprogramming [57.82196268649236]
  Graph Neural Networks (GNNs) serve as the backbone for high-stakes applications in Machine-Learning-as-a-Service (ML)<n>Still, their black-box deployment exposes them to Model Extraction (ME) attacks.<n>Existing defenses suffer from a critical ''Euclidean bias''<n>We propose GraphRP, a proactive defense framework that repurposes Model Reprogramming for security.
  arXiv  Detail & Related papers  (2026-08-11T23:20:15Z)
• Leaking Circuit Secrets: Gradient Leakage Attacks on Graph Neural Networks [6.1625231866179595]
  We present the first comprehensive evaluation of gradient leakage attacks (GLAs) on graph neural networks (GNNs)<n>GLAs can expose sensitive information, such as gate types and distinctive properties of hardware Trojans.<n>We evaluate several SOTA defense techniques, including differential privacy, gradient clipping, secure aggregation, model compression with quantization, and adversarial training.
  arXiv  Detail & Related papers  (2026-06-24T08:59:28Z)
• SEA: Spectral Edge Attacks on Graph Neural Networks [1.066048003460524]
  We propose a new family of adversarial attacks that leverage spectral robustness evaluation to guide perturbations.<n>We introduce two complementary attack variants: (i) a Spade-guided deletion attack that removes the most spectrally robust edges, and (ii) a Spade-guided addition attack that inserts edges between nodes that are maximally incompatible in the fragile spectral space.
  arXiv  Detail & Related papers  (2025-11-30T01:40:15Z)
• KCES: Training-Free Defense for Robust Graph Neural Networks via Kernel Complexity [24.925490936301184]
  Graph Neural Networks (GNNs) are highly vulnerable to small, imperceptible perturbations and adversarial attacks.<n>We propose Kernel Complexity-Based Edge Sanitization (KCES), a training-free, model-agnostic defense framework.<n>KCES consistently enhances GNN robustness, outperforms state-of-the-art baselines, and amplifies the effectiveness of existing defenses.
  arXiv  Detail & Related papers  (2025-06-13T09:33:41Z)
• Grimm: A Plug-and-Play Perturbation Rectifier for Graph Neural Networks Defending against Poisoning Attacks [53.972077392749185]
  Recent studies have revealed the vulnerability of graph neural networks (GNNs) to adversarial poisoning attacks on node classification tasks.<n>Here we introduce Grimm, the first plug-and-play defense model.
  arXiv  Detail & Related papers  (2024-12-11T17:17:02Z)
• Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks [50.87615167799367]
  We certify Graph Neural Networks (GNNs) against poisoning attacks, including backdoors, targeting the node features of a given graph.<n>Our framework provides fundamental insights into the role of graph structure and its connectivity on the worst-case behavior of convolution-based and PageRank-based GNNs.
  arXiv  Detail & Related papers  (2024-07-15T16:12:51Z)
• Self-Guided Robust Graph Structure Refinement [37.235898707554284]
  We propose a self-guided graph structure refinement (GSR) framework to defend GNNs against adversarial attacks. In this paper, we demonstrate the effectiveness of SG-GSR under various scenarios including non-targeted attacks, targeted attacks, feature attacks, e-commerce fraud, and noisy node labels.
  arXiv  Detail & Related papers  (2024-02-19T05:00:07Z)
• Everything Perturbed All at Once: Enabling Differentiable Graph Attacks [61.61327182050706]
  Graph neural networks (GNNs) have been shown to be vulnerable to adversarial attacks. We propose a novel attack method called Differentiable Graph Attack (DGA) to efficiently generate effective attacks. Compared to the state-of-the-art, DGA achieves nearly equivalent attack performance with 6 times less training time and 11 times smaller GPU memory footprint.
  arXiv  Detail & Related papers  (2023-08-29T20:14:42Z)
• Doubly Robust Instance-Reweighted Adversarial Training [107.40683655362285]
  We propose a novel doubly-robust instance reweighted adversarial framework. Our importance weights are obtained by optimizing the KL-divergence regularized loss function. Our proposed approach outperforms related state-of-the-art baseline methods in terms of average robust performance.
  arXiv  Detail & Related papers  (2023-08-01T06:16:18Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Understanding Structural Vulnerability in Graph Convolutional Networks [27.602802961213236]
  Graph Convolutional Networks (GCNs) are vulnerable to adversarial attacks on the graph structure. We show that structural adversarial examples can be attributed to the non-robust aggregation scheme of GCNs. We show that adopting the aggregation scheme with a high breakdown point could significantly enhance the robustness of GCNs against structural attacks.
  arXiv  Detail & Related papers  (2021-08-13T15:07:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.