PaperlayerView exact revision on arXiv

Source-linked AI summary

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:2609.09698v1cs.LGcs.AI

TL;DR

GNNs are vulnerable to structural attacks, while existing defenses may lack generalization-grounded criteria or require costly, attack-specific training. The paper proposes KCES, which uses GKC-based edge influence scores to prune high-KC edges without retraining; experiments report consistent robustness gains, including 58.62% robustness on Ogbn-Arxiv and successful scaling where ProGNN runs out of memory. KCES is scoped to structural perturbations and may be less effective on heterophilous graphs or highly structured attacks.

  • Problem

    Existing GNN defenses may rely on local heuristics, costly optimization, or attack-specific training rather than criteria tied explicitly to generalization, motivating a robust and scalable alternative.

  • Method

    KCES uses GKC from a graph Gram matrix to define edge KC scores, then prunes high-KC edges as a training-free, model-agnostic preprocessing step.

  • Results

    KCES consistently improves structural robustness across attacks and scales, achieving 58.62% robustness on Ogbn-Arxiv while ProGNN fails under memory constraints.

  • Takeaways & Limitations

    KCES provides a lightweight preprocessing module that is compatible with diverse GNN architectures, existing defenses, and large-scale graphs without retraining.

  • Takeaways & Limitations

    KCES directly targets structural perturbations; its benefits may be less pronounced on heterophilous graphs and it may discard useful information under highly structured perturbations.

Abstract

from arXiv · show

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.

1 Introduction

GNNs are highly vulnerable to structural attacks, while existing defenses can rely on heuristics, costly optimization, or attack-specific training. KCES addresses these limitations with a theoretically grounded, training-free, model-agnostic edge-pruning framework.

  • Structural attacks can severely degrade GNN performance by adding or removing only a few edges that corrupt message aggregation.
  • Existing defenses include graph purification, adversarial training, and architecture- or reconstruction-based approaches.
  • Many defenses lack pruning criteria explicitly tied to generalization, while optimization and training requirements limit scalability or cross-attack applicability.
  • KCES uses Graph Kernel Complexity and edge-specific KC scores to guide structural sanitization without retraining or architectural modification.
  • KCES removes high-KC edges because structural attacks empirically enrich harmful perturbations in this region, improving robustness across diverse architectures and defense pipelines.

2 Preliminaries

The paper formulates GNNs on graphs with normalized adjacency-based feature aggregation and introduces a graph Gram matrix that captures structure-feature interactions. GKC is then defined from this matrix to characterize the GNN test-error bound, using pseudo-labels for KCES computation.

  • Graphs are represented by node features, a self-looped adjacency matrix, its degree matrix, and node labels, with a training subgraph used for learning.
  • The aggregated feature matrix is Z = D̃^-1/2 ÃD̃^-1/2X, and row-normalized features are used in the GNN and Gram-matrix construction.
  • The analyzed GNN uses a first-layer weight matrix, a second-layer weight vector, and an activation function such as ReLU.
  • The graph Gram matrix characterizes pairwise node interactions induced by graph structure and node features, forming the basis for GKC.
  • GKC is defined from the Gram matrix and bounded labels to characterize the GNN test-error bound and reflect generalization capacity.
  • KCES replaces theoretical ground-truth labels with bounded pseudo-labels obtained from unsupervised clustering assignments.

3 GKC-based Generalization Analysis

The analysis links GNN training dynamics and test-error generalization to the graph Gram matrix and GKC. Training error decays with gradient updates, while smaller GKC yields a tighter test-error bound under the stated assumptions.

  • The section establishes training and test-error bounds for the analyzed GNN using the graph Gram matrix and GKC.
  • Theorem 3.1 characterizes training-error dynamics after t gradient-descent updates with step size η under Assumption B.1.
  • Training error decays exponentially with gradient steps, with the decay rate governed by the Gram matrix H∞ and an error term ε = Õ(m^-1/2).
  • Theorem 3.2 gives a high-probability test-error bound for sufficiently large hidden-layer width and iteration count.
  • The bound is primarily influenced by GKC(H∞, y), and smaller GKC produces a tighter bound indicating improved generalization under standard GNN training.

4 Kernel-Complexity Edge Sanitization for Structural Robustness

KCES uses pseudo-label-based Graph Kernel Complexity to score each edge by its structural influence and prune high-influence edges as a training-free defense. The framework connects edge-specific KC scores to a test-error bound while offering model-agnostic, scalable preprocessing.

  • Pseudo-Label Generation: KCES generates pseudo-labels with K-Means over row-normalized aggregated features to preserve its training-free and unsupervised operation.The pseudo-labels target structural smoothness rather than exact ground-truth semantics.
  • Edge KC Score Estimation: The KC score measures the magnitude of the change in GKC caused by removing an edge, capturing its influence on graph-induced kernel complexity.Because it uses an absolute difference, the score is directionagnostic.
  • Theoretical Basis: Corollary 4.1 connects an edge’s KC score to the expected test error of the graph formed by deleting that edge under the theorem’s assumptions.The bound uses sufficiently large hidden width and iteration count and holds with probability at least 1 − δ.
  • Kernel-Complexity Edge Sanitization: KCES sanitizes attacked graphs by sorting edges by KC and removing the top-k high-influence edges.The procedure is described as a preprocessing step that operates without adversarial training or iterative graph optimization.
  • Applicability and Complexity: The framework is model-agnostic because GKC computation is independent of specific GNN parameters and can support diverse architectures and existing defense pipelines.Its practical implementation uses sparse operations, local h-hop subgraphs, incremental inverse updates, and parallel edge-wise computations.

5 Experiments

Experiments evaluate KCES across attack mechanisms, graph scales, computational costs, pseudo-label settings, and compatibility with existing defenses. Results show that high-KC pruning improves attacked-graph performance, scales to massive graphs, remains stable across pseudo-label choices, and complements other defenses.

  • Mechanism of KC Scores: Metattack shifts KC scores toward a heavier high-KC tail, while pruning high-KC edges moves the distribution toward clean-graph behavior.This supports the claim that harmful perturbations are enriched among high-KC edges under attack.
  • Mechanism of KC Scores: High-KC pruning outperforms random and low-KC pruning, which respectively produce intermediate and substantially worse accuracy on Metattack graphs.The reported ordering is High-KC > Random > Low-KC.
  • Defense against Structural Attacks: KCES consistently outperforms representative baselines under most adversarial settings and often restores accuracy close to or above clean-graph performance.On Flickr, KCES achieves higher accuracy than on the original clean topology.
  • Scalability and Efficiency Analysis: On Ogbn-Arxiv, KCES scales successfully to over 1M edges and reaches 58.62% robustness, while ProGNN fails from memory constraints.KCES also incurs minimal overhead compared with iterative optimization methods; ProGNN takes over 7,000 seconds.
  • Plug-and-Play Compatibility: Applying KCES before GAT, RGCN, ProGNN, GNN-SVD, GCN-Jaccard, and GNNGuard consistently improves or maintains performance on clean and attacked graphs.The strongest improvements appear under Nettack, MINMAX, and Metattack, supporting KCES as complementary to existing defenses.

6 Related Works

Structural attacks threaten message-passing GNNs by modifying topology, while existing defenses span purification, robust architectures, and kernel-based analyses. KCES adds a data-centric, model-independent kernel-complexity perspective with plug-and-play sanitization.

  • Robustness to Structural Attacks in GNNs: Structural attacks modify graph topology and can corrupt the aggregated information used by message-passing GNNs.
  • Robustness to Structural Attacks in GNNs: Existing defenses include graph purification, robust architecture design, and reconstruction-based approaches.
  • Kernel-view GNN Theory: Kernel-based GNN analyses largely characterize specific architectures rather than providing a direct data-centric measure of graph complexity.
  • Kernel-view GNN Theory: GKC is a computable graph-feature-pseudo-label metric independent of specific GNN parameters and appearing in a GNN test-error bound.
  • Kernel-view GNN Theory: KCES applies this kernel-complexity perspective through training-free, plug-and-play edge sanitization that complements existing defenses.

7 Conclusion

The paper concludes that KCES uses graph-induced kernel complexity and KC scores to improve structural robustness through lightweight, training-free preprocessing. Its scope is constrained by attack type, graph homophily, and possible information loss from pruning.

  • 7 Conclusion: KCES connects graph-induced kernel complexity with generalization to guide targeted edge sanitization for structural robustness.
  • 7 Conclusion: KCES is presented as computationally efficient, scalable, compatible with diverse GNN architectures, and largely preservative of clean accuracy.
  • Limitations: KCES is designed for structural perturbations and is not a direct defense against node- or feature-level attacks.
  • Limitations: Benefits may be less pronounced on heterophilous graphs, and pruning may discard useful information under highly structured perturbations.

Ethics and Privacy Statement

The experiments use publicly available benchmark datasets and models without human subjects, private information, or sensitive user data. The paper reports no direct privacy or ethical concerns associated with the experiments.

  • Ethics and Privacy Statement: The work uses only publicly available benchmark datasets and models.
  • Ethics and Privacy Statement: The experiments involve no human subjects, private information, or sensitive user data.
  • Ethics and Privacy Statement: The authors do not identify direct privacy or ethical concerns associated with the experiments.

A Experimental Setup

The experimental setup uses standardized DeepRobust implementations, fixed training settings, and dedicated multi-GPU hardware. Dataset-specific hyperparameters are summarized separately in Table 6.

  • Experimental Setup: Attack and defense baselines are implemented using the DeepRobust library.
  • Experimental Setup: Unless otherwise specified, models train for 200 epochs with ReLU, Adam, a 0.01 learning rate, and 1 × 10^-5 weight decay.
  • Experimental Setup: Experiments run on a dedicated server with eight NVIDIA RTX A6000 GPUs, each providing 48GB memory.
  • Experimental Setup: Dataset-specific hyperparameters are summarized in Table 6.

B Theoretical Analysis of the Graph Kernel Model

This section establishes the formal framework for deriving graph-kernel training, test, and edge-specific error bounds. The analysis adapts a two-layer ReLU kernel generalization framework to graph-aggregated node features.

  • B Theoretical Analysis of the Graph Kernel Model: The analysis instantiates a two-layer ReLU kernel generalization framework on graph-aggregated node features.It derives training, test, and edge-specific bounds within this graph-kernel setting.
  • B Theoretical Analysis of the Graph Kernel Model: The formal development proceeds from the graph-kernel setup and assumptions to reference kernel results and graph-specific bounds.
  • B Theoretical Analysis of the Graph Kernel Model: The resulting framework provides the theoretical basis for the KCES edge-specific analysis.

B.1 Graph Kernel Setup

The graph-kernel analysis models GNNs as two-layer ReLU networks over normalized graph-aggregated features, defines GKC from the infinite-width Gram matrix, and derives training, test, and edge-specific bounds under explicit assumptions.

  • Graph Kernel Model: Graph aggregation transforms node features using the normalized adjacency structure before applying the two-layer ReLU graph-kernel model.The model uses first-layer weights, fixed second-layer coefficients, and ReLU activation.
  • Graph Kernel Model: The framework defines an infinite-width graph kernel Gram matrix and Graph Kernel Complexity from that matrix.These quantities support the subsequent generalization analysis.
  • Assumptions: The assumptions require normalized aggregated features, bounded labels, non-degenerate graph kernels, Gaussian initialization, fixed second-layer coefficients, and gradient descent.The non-degeneracy conditions apply to both the original and edge-deleted graphs considered by KCES.
  • Connection to Reference Kernel Theory: The graph model satisfies the reference kernel theory because it is a two-layer ReLU model applied to graph-aggregated inputs under the stated assumptions.This correspondence allows the reference training and test results to yield graph-specific bounds.
  • Training and Test Bounds: Theorem B.4 provides training-error dynamics under Assumption B.1 with probability at least 1 − 𝛿 over initialization for all t ≥ 0.The dynamics are expressed using the eigenvalues and eigenvectors of the graph kernel Gram matrix.
  • Training and Test Bounds: Theorem B.5 gives a graph-specific test-error bound, while KCES assigns each edge a KC score from the change induced by deleting that edge.The edge-specific analysis applies the same framework to the corresponding edge-deleted graph.
Loading 2609.09698v1…