# Graph Structural Attack by Perturbing Spectral Distance

arXiv: https://arxiv.org/abs/2111.00684 · HTML: https://mlsanity.com/paper/2111.00684/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Constructing Unrestricted Adversarial Examples with Generative Models](https://mlsanity.com/paper/1805.07894/) (2018)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [Adversarial Attack on Large Scale Graph](https://mlsanity.com/paper/2009.03488/) (2020)
- [On the Transferability of Spectral Graph Filters](https://mlsanity.com/paper/1901.10524/) (2019)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [Spectral Graph Attention Network with Fast Eigen-approximation](https://mlsanity.com/paper/2003.07450/) (2020)
- [Universal Spectral Adversarial Attacks for Deformable Shapes](https://mlsanity.com/paper/2104.03356/) (2021)
- [Learning to Deceive Knowledge Graph Augmented Models via Targeted Perturbation](https://mlsanity.com/paper/2010.12872/) (2020)

## Built on by (most cited first, 16 of 16)

- [A semantic backdoor attack against Graph Convolutional Networks](https://mlsanity.com/paper/2302.14353/) (2023)
- [Deceptive Fairness Attacks on Graphs via Meta Learning](https://mlsanity.com/paper/2310.15653/) (2023)
- [Adversarial Attacks on Fairness of Graph Neural Networks](https://mlsanity.com/paper/2310.13822/) (2023)
- [Community-Invariant Graph Contrastive Learning](https://mlsanity.com/paper/2405.01350/) (2024)
- [Globally Interpretable Graph Learning via Distribution Matching](https://mlsanity.com/paper/2306.10447/) (2023)
- [Coupled-Space Attacks against Random-Walk-based Anomaly Detection](https://mlsanity.com/paper/2307.14387/) (2023)
- [Debiased Graph Poisoning Attack via Contrastive Surrogate Objective](https://mlsanity.com/paper/2407.19155/) (2024)
- [Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model](https://mlsanity.com/paper/2203.07831/) (2022)
- [Momentum Gradient-based Untargeted Attack on Hypergraph Neural Networks](https://mlsanity.com/paper/2310.15656/) (2023)
- [Adversarial Robustness of Graph Transformers](https://mlsanity.com/paper/2407.11764/) (2024)
- [A Systematic Evaluation of Node Embedding Robustness](https://mlsanity.com/paper/2209.08064/) (2022)
- [Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks](https://mlsanity.com/paper/2312.01342/) (2023)
- [Graph Adversarial Diffusion Convolution](https://mlsanity.com/paper/2406.02059/) (2024)
- [Unveiling the Threat of Fraud Gangs to Graph Neural Networks: Multi-Target Graph Injection Attacks Against GNN-Based Fraud Detectors](https://mlsanity.com/paper/2412.18370/) (2024)
- [Generalized Robust Adaptive-Bandwidth Multi-View Manifold Learning in High Dimensions with Noise](https://mlsanity.com/paper/2602.10530/) (2026)
- [ASPECT: Node-Level Adaptive Spectral Fusion for Graph Contrastive Learning](https://mlsanity.com/paper/2604.01878/) (2026)

## 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.