# Understanding Structural Vulnerability in Graph Convolutional Networks

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 29 references that are in the map.
- First posted on arXiv 13 Aug 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (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)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Node Similarity Preserving Graph Convolutional Networks](https://mlsanity.com/paper/2011.09643/) (2020)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [Reliable Graph Neural Networks via Robust Aggregation](https://mlsanity.com/paper/2010.15651/) (2020)
- [Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies](https://mlsanity.com/paper/2003.00653/) (2020)
- [A Survey of Adversarial Learning on Graphs](https://mlsanity.com/paper/2003.05730/) (2020)
- [Invariance-Preserving Localized Activation Functions for Graph Neural Networks](https://mlsanity.com/paper/1903.12575/) (2019)
- [Median activation functions for graph neural networks](https://mlsanity.com/paper/1810.12165/) (2018)

## Built on by (most cited first, 30 of 37)

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [What's Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoders](https://mlsanity.com/paper/2205.10053/) (2022)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN](https://mlsanity.com/paper/2207.00012/) (2022)
- [Scaling Up Dynamic Graph Representation Learning via Spiking Neural Networks](https://mlsanity.com/paper/2208.10364/) (2022)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Defending Graph Convolutional Networks against Dynamic Graph Perturbations via Bayesian Self-supervision](https://mlsanity.com/paper/2203.03762/) (2022)
- [A Unified Framework of Graph Information Bottleneck for Robustness and Membership Privacy](https://mlsanity.com/paper/2306.08604/) (2023)
- [Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation](https://mlsanity.com/paper/2208.09779/) (2022)
- [Spectral Adversarial Training for Robust Graph Neural Network](https://mlsanity.com/paper/2211.10896/) (2022)
- [Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attack](https://mlsanity.com/paper/2202.07114/) (2022)
- [GANI: Global Attacks on Graph Neural Networks via Imperceptible Node Injections](https://mlsanity.com/paper/2210.12598/) (2022)
- [Simple and Efficient Partial Graph Adversarial Attack: A New Perspective](https://mlsanity.com/paper/2308.07834/) (2023)
- [FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classification](https://mlsanity.com/paper/2210.13815/) (2022)
- [AGNN: Alternating Graph-Regularized Neural Networks to Alleviate Over-Smoothing](https://mlsanity.com/paper/2304.07014/) (2023)
- [Less Can Be More: Unsupervised Graph Pruning for Large-scale Dynamic Graphs](https://mlsanity.com/paper/2305.10673/) (2023)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)
- [Robust Graph Representation Learning via Predictive Coding](https://mlsanity.com/paper/2212.04656/) (2022)
- [Robust Graph Learning Against Adversarial Evasion Attacks via Prior-Free Diffusion-Based Structure Purification](https://mlsanity.com/paper/2502.05000/) (2025)
- [GUARD: Graph Universal Adversarial Defense](https://mlsanity.com/paper/2204.09803/) (2022)
- [Attributed Multi-order Graph Convolutional Network for Heterogeneous Graphs](https://mlsanity.com/paper/2304.06336/) (2023)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Detecting Topology Attacks against Graph Neural Networks](https://mlsanity.com/paper/2204.10072/) (2022)
- [Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification](https://mlsanity.com/paper/2212.01749/) (2022)
- [Understanding the Robustness of Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2406.13920/) (2024)
- [On Measuring Unnoticeability of Graph Adversarial Attacks: Observations, New Measure, and Applications](https://mlsanity.com/paper/2501.05015/) (2025)
- [Single-Node Trigger Backdoor Attacks in Graph-Based Recommendation Systems](https://mlsanity.com/paper/2506.08401/) (2025)

## Abstract (arXiv)

Recent studies have shown that Graph Convolutional Networks (GCNs) are vulnerable to adversarial attacks on the graph structure. Although multiple works have been proposed to improve their robustness against such structural adversarial attacks, the reasons for the success of the attacks remain unclear. In this work, we theoretically and empirically demonstrate that structural adversarial examples can be attributed to the non-robust aggregation scheme (i.e., the weighted mean) of GCNs. Specifically, our analysis takes advantage of the breakdown point which can quantitatively measure the robustness of aggregation schemes. The key insight is that weighted mean, as the basic design of GCNs, has a low breakdown point and its output can be dramatically changed by injecting a single edge. We show that adopting the aggregation scheme with a high breakdown point (e.g., median or trimmed mean) could significantly enhance the robustness of GCNs against structural attacks. Extensive experiments on four real-world datasets demonstrate that such a simple but effective method achieves the best robustness performance compared to state-of-the-art models.