mlsanityData to 13 Oct 2026

Understanding Structural Vulnerability in Graph Convolutional Networks

arXiv 2108.06280 ↗First posted 13 Aug 2021cs.LG cs.CRcited by 37

Not on the map. Why?

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.

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

Builds on

19 of 29 references.

References · 19

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,093
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
  3. 2017Graph Attention Networkscited by 8,888
  4. 2018How Powerful are Graph Neural Networks?cited by 4,373
  5. 2019Graph Neural Networks for Social Recommendationcited by 714
  6. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 396
  7. 2018Adversarial Attack on Graph Structured Datacited by 301
  8. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  9. 2020A Semi-supervised Graph Attentive Network for Financial Fraud Detectioncited by 150
  10. 2020Node Similarity Preserving Graph Convolutional Networkscited by 112
  11. 2018Adversarial Attacks on Node Embeddings via Graph Poisoningcited by 109
  12. 2019Certifiable Robustness to Graph Perturbationscited by 62
7 more
  1. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  2. 2019Transferring Robustness for Graph Neural Network Against Poisoning Attackscited by 58
  3. 2020Reliable Graph Neural Networks via Robust Aggregationcited by 43
  4. 2020Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studiescited by 42
  5. 2020A Survey of Adversarial Learning on Graphscited by 42
  6. 2019Invariance-Preserving Localized Activation Functions for Graph Neural Networkscited by 14
  7. 2018Median activation functions for graph neural networkscited by 1

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 1; 2022: 17; 2023: 7; 2024: 5; 2025: 6; 2026: 1.

37 papers.

Sort:

By area:

  1. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  2. 2021Robustness of Graph Neural Networks at Scalecited by 100
  3. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  4. 2022What's Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoderscited by 82
  5. 2023Are Defenses for Graph Neural Networks Robust?cited by 38
  6. 2022Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNNcited by 34
  7. 2022Scaling Up Dynamic Graph Representation Learning via Spiking Neural Networkscited by 24
  8. 2022A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protectioncited by 20
  9. 2022Defending Graph Convolutional Networks against Dynamic Graph Perturbations via Bayesian Self-supervisioncited by 16
  10. 2023A Unified Framework of Graph Information Bottleneck for Robustness and Membership Privacycited by 14
  11. 2022Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagationcited by 12
  12. 2022Spectral Adversarial Training for Robust Graph Neural Networkcited by 12
25 more
  1. 2022Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attackcited by 10
  2. 2022GANI: Global Attacks on Graph Neural Networks via Imperceptible Node Injectionscited by 10
  3. 2023Simple and Efficient Partial Graph Adversarial Attack: A New Perspectivecited by 8
  4. 2022FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classificationcited by 7
  5. 2023AGNN: Alternating Graph-Regularized Neural Networks to Alleviate Over-Smoothingcited by 7
  6. 2023Less Can Be More: Unsupervised Graph Pruning for Large-scale Dynamic Graphscited by 7
  7. 2024Minimum Topology Attacks for Graph Neural Networkscited by 6
  8. 2022Robust Graph Representation Learning via Predictive Codingcited by 5
  9. 2025Robust Graph Learning Against Adversarial Evasion Attacks via Prior-Free Diffusion-Based Structure Purificationcited by 3
  10. 2022GUARD: Graph Universal Adversarial Defensecited by 2
  11. 2023Attributed Multi-order Graph Convolutional Network for Heterogeneous Graphscited by 2
  12. 2024Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attackcited by 2
  13. 2025AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothingcited by 2
  14. 2022Detecting Topology Attacks against Graph Neural Networkscited by 1
  15. 2022Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classificationcited by 1
  16. 2024Understanding the Robustness of Graph Neural Networks against Adversarial Attackscited by 1
  17. 2025On Measuring Unnoticeability of Graph Adversarial Attacks: Observations, New Measure, and Applicationscited by 1
  18. 2022Global quantitative robustness of regression feed-forward neural networkscited by 0
  19. 2023Spatial-Temporal DAG Convolutional Networks for End-to-End Joint Effective Connectivity Learning and Resting-State fMRI Classificationcited by 0
  20. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  21. 2024On the Adversarial Robustness of Graph Neural Networks with Graph Reductioncited by 0
  22. 2025Single-Node Trigger Backdoor Attacks in Graph-Based Recommendation Systemscited by 0
  23. 2025Ralts: Robust Aggregation for Enhancing Graph Neural Network Resilience on Bit-flip Errorscited by 0
  24. 2025Backdoor or Manipulation? Graph Mixture of Experts Can Defend Against Various Graph Adversarial Attackscited by 0
  25. 2026Adversarial Graph Neural Network Benchmarks: Towards Practical and Fair Evaluationcited by 0