Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
Updated 2 h ago · first seen 11 Sept 2026
paper_01M294GMMGHXNW7RE5WF9614GQ
- Published
- 11 Sept 2026
- T1 · 2 h ago
- arXiv
- 2609.09698
- T1 · 2 h ago
- Category
- cs.LG
- T1 · 2 h ago
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
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
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 · Abstract
Abstractabstract1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| 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. | → 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 →
- 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
| 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.