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

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

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [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)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [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)

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

- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Graph Neural Convection-Diffusion with Heterophily](https://mlsanity.com/paper/2305.16780/) (2023)
- [Homophily-oriented Heterogeneous Graph Rewiring](https://mlsanity.com/paper/2302.06299/) (2023)
- [Robust Mid-Pass Filtering Graph Convolutional Networks](https://mlsanity.com/paper/2302.08048/) (2023)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning](https://mlsanity.com/paper/2409.17386/) (2024)
- [Intruding with Words: Towards Understanding Graph Injection Attacks at the Text Level](https://mlsanity.com/paper/2405.16405/) (2024)
- [Learn from Heterophily: Heterophilous Information-enhanced Graph Neural Network](https://mlsanity.com/paper/2403.17351/) (2024)
- [What Does the Gradient Tell When Attacking the Graph Structure](https://mlsanity.com/paper/2208.12815/) (2022)
- [Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning](https://mlsanity.com/paper/2405.19919/) (2024)
- [Understanding the Robustness of Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2406.13920/) (2024)
- [MADE: Graph Backdoor Defense with Masked Unlearning](https://mlsanity.com/paper/2411.18648/) (2024)
- [Robust Graph Contrastive Learning with Information Restoration](https://mlsanity.com/paper/2307.12555/) (2023)
- [Guarding Graph Neural Networks for Unsupervised Graph Anomaly Detection](https://mlsanity.com/paper/2404.16366/) (2024)
- [β-GNN: A Robust Ensemble Approach Against Graph Structure Perturbation](https://mlsanity.com/paper/2503.20630/) (2025)
- [Heterophily-informed Message Passing](https://mlsanity.com/paper/2504.19785/) (2025)
- [Navigating the Black Box: Leveraging LLMs for Effective Text-Level Graph Injection Attacks](https://mlsanity.com/paper/2506.13276/) (2025)
- [Fixed-point graph convolutional networks against adversarial attacks](https://mlsanity.com/paper/2511.00083/) (2025)
- [Robust Learning on Heterogeneous Graphs with Heterophily: A Graph Structure Learning Approach](https://mlsanity.com/paper/2604.27387/) (2026)
- [Adversarial Graph Neural Network Benchmarks: Towards Practical and Fair Evaluation](https://mlsanity.com/paper/2605.05534/) (2026)

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