SEA: Spectral Edge Attacks on Graph Neural Networks

• URL: http://arxiv.org/abs/2512.08964v1
• Date: Sun, 30 Nov 2025 01:40:15 GMT
• Title: SEA: Spectral Edge Attacks on Graph Neural Networks
• Authors: Yongyu Wang,
• Abstract summary: 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.
• Score: 1.066048003460524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) achieve strong performance on graph-structured data, but are notoriously vulnerable to small, carefully crafted perturbations of the graph structure. Most existing structure-based attacks rely on gradient-based heuristics or local connectivity patterns, and treat edges as equally important candidates for manipulation. In this paper, we propose Spectral Edge Attacks (SEA), a new family of adversarial attacks that explicitly leverage spectral robustness evaluation to guide structural perturbations. Our key idea is to compute a spectral embedding that captures the most fragile directions of the input manifold and to use it to assign a robustness score to each edge or non-edge. Based on these scores, 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. Both attacks operate at the graph level, are model-aware but conceptually simple, and can be plugged into existing GNN architectures without requiring gradients. We describe the spectral formulation, the attack algorithms, and experiments on benchmarks.

Related papers

• Relaxing Graph Transformers for Adversarial Attacks [49.450581960551276]
  Graph Transformers (GTs) surpassed Message-Passing GNNs on several benchmarks, their adversarial robustness properties are unexplored. We overcome these challenges by targeting three representative architectures based on (1) random-walk PEs, (2) pair-wise-short-paths, and (3) spectral perturbations. Our evaluation reveals that they can be catastrophically fragile and underlines our work's importance and the necessity for adaptive attacks.
  arXiv  Detail & Related papers  (2024-07-16T14:24:58Z)
• AGSOA:Graph Neural Network Targeted Attack Based on Average Gradient and Structure Optimization [16.681157857248436]
  Graph Neural Networks (GNNs) are vulnerable to adversarial attack that cause performance degradation by adding small perturbations to the graph. This paper proposes an attack on GNNs, called AGSOA, which consists of an average gradient calculation and a structre optimization module.
  arXiv  Detail & Related papers  (2024-06-19T05:29:20Z)
• 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)
• EDoG: Adversarial Edge Detection For Graph Neural Networks [17.969573886307906]
  Graph Neural Networks (GNNs) have been widely applied to different tasks such as bioinformatics, drug design, and social networks. Recent studies have shown that GNNs are vulnerable to adversarial attacks which aim to mislead the node or subgraph classification prediction by adding subtle perturbations. We propose a general adversarial edge detection pipeline EDoG without requiring knowledge of the attack strategies based on graph generation.
  arXiv  Detail & Related papers  (2022-12-27T20:42:36Z)
• Model Inversion Attacks against Graph Neural Networks [65.35955643325038]
  We study model inversion attacks against Graph Neural Networks (GNNs) In this paper, we present GraphMI to infer the private training graph data. Our experimental results show that such defenses are not sufficiently effective and call for more advanced defenses against privacy attacks.
  arXiv  Detail & Related papers  (2022-09-16T09:13:43Z)
• What Does the Gradient Tell When Attacking the Graph Structure [44.44204591087092]
  We present a theoretical demonstration revealing that attackers tend to increase inter-class edges due to the message passing mechanism of GNNs. By connecting dissimilar nodes, attackers can more effectively corrupt node features, making such attacks more advantageous. We propose an innovative attack loss that balances attack effectiveness and imperceptibility, sacrificing some attack effectiveness to attain greater imperceptibility.
  arXiv  Detail & Related papers  (2022-08-26T15:45:20Z)
• Discriminator-Free Generative Adversarial Attack [87.71852388383242]
  Agenerative-based adversarial attacks can get rid of this limitation. ASymmetric Saliency-based Auto-Encoder (SSAE) generates the perturbations. The adversarial examples generated by SSAE not only make thewidely-used models collapse, but also achieves good visual quality.
  arXiv  Detail & Related papers  (2021-07-20T01:55:21Z)
• BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detection [20.666171188140503]
  Graph-based Anomaly Detection (GAD) is becoming prevalent due to the powerful representation abilities of graphs. These GAD tools expose a new attacking surface, ironically due to their unique advantage of being able to exploit the relations among data. In this paper, we exploit this vulnerability by designing a new type of targeted structural poisoning attacks to a representative regression-based GAD system OddBall.
  arXiv  Detail & Related papers  (2021-06-18T08:20:23Z)
• Graph Backdoor [53.70971502299977]
  We present GTA, the first backdoor attack on graph neural networks (GNNs) GTA departs in significant ways: it defines triggers as specific subgraphs, including both topological structures and descriptive features. It can be instantiated for both transductive (e.g., node classification) and inductive (e.g., graph classification) tasks.
  arXiv  Detail & Related papers  (2020-06-21T19:45:30Z)
• Graph Structure Learning for Robust Graph Neural Networks [63.04935468644495]
  Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. Recent studies show that GNNs are vulnerable to carefully-crafted perturbations, called adversarial attacks. We propose a general framework Pro-GNN, which can jointly learn a structural graph and a robust graph neural network model.
  arXiv  Detail & Related papers  (2020-05-20T17:07:05Z)

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.