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

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.

Authors 6

Yaning Jia, Shenyang Deng, Yaoqing Yang, Chiyu Ma, Wenxuan Xu, Soroush Vosoughi

Specification

Official page: arxiv.org/abs/2609.09698
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
Arxiv announce type: cross
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
arXiv id: 2609.09698
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
Categories: cs.LG, cs.AI
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
DOI: 10.1145/3799682.3841029
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
PDF: arxiv.org/pdf/2609.09698
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
Primary category: cs.LG
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
Published: 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance

Attributed facts

10

Source tiers

T110

Freshest observation

2 h ago

Conflicts

None

No models linked to this paper yet.

Authors: Yaning Jia, Shenyang Deng, Yaoqing Yang

As of

Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.

Claim history · DOI

1 claims · 1 propertiesShow all properties

DOIdoi1

Claim history for DOI
Value	Valid from → to	Status	Source	Confidence	Extractor
10.1145/3799682.3841029	11 Sept 2026 21:03 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →

11 Sept 2026
New paperPaperKernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
New paper: Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
arxiv
rss.arxiv.org

Full timeline →

Source documents
Source	Document	Type	Tier	Last observed	Snapshots
arXiv (Atom API + RSS)	rss.arxiv.org/rss/cs.AI	feed	T1· Official	2 h ago	1

Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.