How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications
It addresses robustness issues in GNNs for real-world graph data, offering practical defense improvements, though it builds on existing design principles.
The paper investigates how heterophily affects the robustness of graph neural networks to adversarial attacks, showing that separate aggregators for ego- and neighbor-embeddings improve robustness, with up to 18.33% performance increase under attacks when combined with explicit defenses.
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.