mlsanityData to 7 Oct 2026

Graph Structural Attack by Perturbing Spectral Distance

arXiv 2111.00684 ↗First posted 1 Nov 2021cs.LG cs.AI cs.CRcited by 16

Not on the map. Why?

Abstract (arXiv)

Graph Convolutional Networks (GCNs) have fueled a surge of research interest due to their encouraging performance on graph learning tasks, but they are also shown vulnerability to adversarial attacks. In this paper, an effective graph structural attack is investigated to disrupt graph spectral filters in the Fourier domain, which are the theoretical foundation of GCNs. We define the notion of spectral distance based on the eigenvalues of graph Laplacian to measure the disruption of spectral filters. We realize the attack by maximizing the spectral distance and propose an efficient approximation to reduce the time complexity brought by eigen-decomposition. The experiments demonstrate the remarkable effectiveness of the proposed attack in both black-box and white-box settings for both test-time evasion attacks and training-time poisoning attacks. Our qualitative analysis suggests the connection between the imposed spectral changes in the Fourier domain and the attack behavior in the spatial domain, which provides empirical evidence that maximizing spectral distance is an effective way to change the graph structural property and thus disturb the frequency components for graph filters to affect the learning of GCNs.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 28 of its 51 references that are in the map. First posted on arXiv 1 Nov 2021.

Builds on

28 of 51 references.

References · 28

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  4. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  7. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  8. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  9. 2018Adversarial Attack on Graph Structured Datacited by 300
  10. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  11. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  12. 2018Constructing Unrestricted Adversarial Examples with Generative Modelscited by 135
16 more
  1. 2018Adversarial Attacks on Node Embeddings via Graph Poisoningcited by 109
  2. 2017Learning Structural Node Embeddings Via Diffusion Waveletscited by 97
  3. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  4. 2020DeepRobust: A PyTorch Library for Adversarial Attacks and Defensescited by 78
  5. 2016Hiding Individuals and Communities in a Social Networkcited by 77
  6. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  7. 2020Graph signal processing for machine learning: A review and new perspectivescited by 73
  8. 2019A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Modelscited by 68
  9. 2018Fast Gradient Attack on Network Embeddingcited by 65
  10. 2019Attacking Graph-based Classification via Manipulating the Graph Structurecited by 53
  11. 2020Adversarial Attack on Large Scale Graphcited by 39
  12. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  13. 2019On the Transferability of Spectral Graph Filterscited by 27
  14. 2020Spectral Graph Attention Network with Fast Eigen-approximationcited by 18
  15. 2021Universal Spectral Adversarial Attacks for Deformable Shapescited by 14
  16. 2020Learning to Deceive Knowledge Graph Augmented Models via Targeted Perturbationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 7; 2024: 5; 2025: 0; 2026: 2.

16 papers.

Sort:

  1. 2023A semantic backdoor attack against Graph Convolutional Networkscited by 8
  2. 2023Deceptive Fairness Attacks on Graphs via Meta Learningcited by 6
  3. 2023Adversarial Attacks on Fairness of Graph Neural Networkscited by 4
  4. 2024Community-Invariant Graph Contrastive Learningcited by 4
  5. 2023Globally Interpretable Graph Learning via Distribution Matchingcited by 3
  6. 2023Coupled-Space Attacks against Random-Walk-based Anomaly Detectioncited by 2
  7. 2024Debiased Graph Poisoning Attack via Contrastive Surrogate Objectivecited by 2
  8. 2022Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Modelcited by 1
  9. 2023Momentum Gradient-based Untargeted Attack on Hypergraph Neural Networkscited by 1
  10. 2024Adversarial Robustness of Graph Transformerscited by 1
  11. 2022A Systematic Evaluation of Node Embedding Robustnesscited by 0
  12. 2023Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networkscited by 0
4 more
  1. 2024Graph Adversarial Diffusion Convolutioncited by 0
  2. 2024Unveiling the Threat of Fraud Gangs to Graph Neural Networks: Multi-Target Graph Injection Attacks Against GNN-Based Fraud Detectorscited by 0
  3. 2026Generalized Robust Adaptive-Bandwidth Multi-View Manifold Learning in High Dimensions with Noisecited by 0
  4. 2026ASPECT: Node-Level Adaptive Spectral Fusion for Graph Contrastive Learningcited by 0