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.

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

References in corpus (21)

• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Geometric deep learning: going beyond Euclidean data
• Adversarial Attacks on Neural Networks for Graph Data
• Representation Learning on Graphs with Jumping Knowledge Networks
• Social Structure of Facebook Networks
• Certified Adversarial Robustness via Randomized Smoothing
• Adversarial Attacks on Graph Neural Networks via Meta Learning
• 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
• Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers
• 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