英文标题：Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks
作者：Yaning Jia, Shenyang Deng, Yaoqing Yang, Chiyu Ma, Wenxuan Xu, Soroush Vosoughi
arXiv ID：2609.09698 | 分类：cs.LG | 发表：2026-09-09
许可：CC-BY
摘要。 图神经网络（GNN）在各类应用中取得了显著成功，但仍极易受到恶意扰动图结构的对抗攻击。现有防御方法往往缺乏严格的理论基础，依赖针对特定攻击的启发式策略，或需要诸如对抗训练之类代价高昂的重训练过程。为解决这些局限，我们提出核复杂度边净化（KCES），一个免训练且模型无关的框架，用于防御结构攻击。KCES 建立在图核复杂度（GKC）之上，后者是一种源自图 Gram 矩阵的原则性度量，出现在 GNN 测试误差的泛化上界中。基于该上界，我们定义了一种边特定的 KC 分数，通过其引起的 GKC 变化来量化每条边的结构影响。随后，KCES 识别并剪除高 KC 边——在结构攻击下这些边在经验上富集了
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.
查看完整双语翻译 →
正在跳转到翻译阅读页… 如果没有自动跳转，请点击这里。