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

Abstract

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.

KDD 2022 camera ready version + full appendix; 20 pages, 2 figures

References in corpus (14)

• Semi-Supervised Classification with Graph Convolutional Networks
• Certified Adversarial Robustness via Randomized Smoothing
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• GNNGuard: Defending Graph Neural Networks against Adversarial Attacks
• Certifiable Robustness and Robust Training for Graph Convolutional Networks
• Adversarial Examples on Graph Data: Deep Insights into Attack and Defense
• Adaptive Universal Generalized PageRank Graph Neural Network
• Adversarial Attack on Community Detection by Hiding Individuals
• Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
• Certifiable Robustness to Graph Perturbations
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• Reliable Graph Neural Networks via Robust Aggregation
• Towards More Practical Adversarial Attacks on Graph Neural Networks
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More

Cited by in corpus (4)

• Robust Mid-Pass Filtering Graph Convolutional Networks
• Homophily-oriented Heterogeneous Graph Rewiring
• A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions
• $\beta$-GNN: A Robust Ensemble Approach Against Graph Structure Perturbation