mlsanityData to 7 Oct 2026

How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications

arXiv 2106.07767 ↗First posted 14 Jun 2021cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We bridge two research directions on graph neural networks (GNNs), by formalizing the relation between heterophily of node labels (i.e., connected nodes tend to have dissimilar labels) and the robustness of GNNs to adversarial attacks. Our theoretical and empirical analyses show that for homophilous graph data, impactful structural attacks always lead to reduced homophily, while for heterophilous graph data the change in the homophily level depends on the node degrees. These insights have practical implications for defending against attacks on real-world graphs: we deduce that separate aggregators for ego- and neighbor-embeddings, a design principle which has been identified to significantly improve prediction for heterophilous graph data, can also offer increased robustness to GNNs. Our comprehensive experiments show that GNNs merely adopting this design achieve improved empirical and certifiable robustness compared to the best-performing unvaccinated model. Additionally, combining this design with explicit defense mechanisms against adversarial attacks leads to an improved robustness with up to 18.33% performance increase under attacks compared to the best-performing vaccinated model.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 37 of its 55 references that are in the map. First posted on arXiv 14 Jun 2021.

Builds on

37 of 55 references.

References · 37

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  5. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  6. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  7. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  9. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  10. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  11. 2019Diffusion Improves Graph Learningcited by 414
  12. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
25 more
  1. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 368
  2. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  3. 2018Adversarial Attack on Graph Structured Datacited by 300
  4. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  5. 2020Graph Neural Networks with Heterophilycited by 202
  6. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  7. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  8. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  9. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  10. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 166
  11. 2018Adversarial Attacks on Node Embeddings via Graph Poisoningcited by 109
  12. 2020Non-Local Graph Neural Networkscited by 91
  13. 2020DeepRobust: A PyTorch Library for Adversarial Attacks and Defensescited by 78
  14. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  15. 2019A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Modelscited by 68
  16. 2019Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifierscited by 65
  17. 2019Certifiable Robustness to Graph Perturbationscited by 62
  18. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  19. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  20. 2020Reliable Graph Neural Networks via Robust Aggregationcited by 43
  21. 2021AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filtercited by 43
  22. 2020Adversarial Attack on Community Detection by Hiding Individualscited by 20
  23. 2021Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphscited by 18
  24. 2020Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networkscited by 16
  25. 2016Graph-based semi-supervised learning for relational networkscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 8; 2025: 4; 2026: 2.

21 papers.

Sort:

  1. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
  2. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  3. 2023Graph Neural Convection-Diffusion with Heterophilycited by 26
  4. 2023Homophily-oriented Heterogeneous Graph Rewiringcited by 18
  5. 2023Robust Mid-Pass Filtering Graph Convolutional Networkscited by 17
  6. 2024A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directionscited by 13
  7. 2024Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learningcited by 12
  8. 2024Intruding with Words: Towards Understanding Graph Injection Attacks at the Text Levelcited by 9
  9. 2024Learn from Heterophily: Heterophilous Information-enhanced Graph Neural Networkcited by 3
  10. 2022What Does the Gradient Tell When Attacking the Graph Structurecited by 2
  11. 2024Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learningcited by 2
  12. 2024Understanding the Robustness of Graph Neural Networks against Adversarial Attackscited by 1
9 more
  1. 2024MADE: Graph Backdoor Defense with Masked Unlearningcited by 1
  2. 2023Robust Graph Contrastive Learning with Information Restorationcited by 0
  3. 2024Guarding Graph Neural Networks for Unsupervised Graph Anomaly Detectioncited by 0
  4. 2025β-GNN: A Robust Ensemble Approach Against Graph Structure Perturbationcited by 0
  5. 2025Heterophily-informed Message Passingcited by 0
  6. 2025Navigating the Black Box: Leveraging LLMs for Effective Text-Level Graph Injection Attackscited by 0
  7. 2025Fixed-point graph convolutional networks against adversarial attackscited by 0
  8. 2026Robust Learning on Heterogeneous Graphs with Heterophily: A Graph Structure Learning Approachcited by 0
  9. 2026Adversarial Graph Neural Network Benchmarks: Towards Practical and Fair Evaluationcited by 0