Graph Neural Networks with Heterophily

By Jiong Zhu, Ryan A. Rossi, Anup B. Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, Danai Koutra. AAAI Conference on Artificial Intelligence, 2020

406 citations recorded by the source corpus.

Graph Neural Networks (GNNs) have proven to be useful for many different practical applications. However, many existing GNN models have implicitly assumed homophily among the nodes connected in the graph, and therefore have largely overlooked the important setting of heterophily, where most connected nodes are from different classes. In this work, we propose a novel framework called CPGNN that generalizes GNNs for graphs with either homophily or heterophily. The proposed framework incorporates an interpretable compatibility matrix for modeling the heterophily or homophily level in the graph, which can be learned in an end-to-end fashion, enabling it to go beyond the assumption of strong homophily. Theoretically, we show that replacing the compatibility matrix in our framework with the identity (which represents pure homophily) reduces to GCN. Our extensive experiments demonstrate the effectiveness of our approach in more realistic and challenging experimental settings with significantly less training data compared to previous works: CPGNN variants achieve state-of-the-art results in heterophily settings with or without contextual node features, while maintaining comparable performance in homophily settings.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/33b75e9094968c060238d54f1026dbc3c8ab66f7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Is Homophily a Necessity for Graph Neural Networks? (2021, methodology): “Due to this neighborhood aggregation mechanism, existing literature posits that strong homophily of the underlying graph is a necessity for GNNs to achieve good performance on SSNC [1, 41, 40, 4, 22, 12, 14, 35].”
Finding Global Homophily in Graph Neural Networks When Meeting Heterophily (2022, methodology): “As a representative model, H2GCN (Zhu et al., 2020b) presents three designs to improve the performance of GNNs under heterophily: ego and neighbor embedding separation, higher-order neighborhood utilization and intermediate representation combination.”
Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, background): “Various GNNs have been proposed to achieve higher performance in low-homophily settings [82, 44, 81, 17, 15, 73, 36, 35].”
Revisiting Heterophily For Graph Neural Networks (2022, methodology): “Heterophily has received lots of attention recently and an increasing number of models have been put forward to address this problem [46, 29, 32, 8, 45, 44, 33, 16, 24].”
Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs (2020, methodology): “Moreover, the recent CPGNN model [43] integrates the compatibility matrix as a set of learnable parameters into GNN, which it initializes with an estimated class compatibility matrix.”
A critical look at the evaluation of GNNs under heterophily: are we really making progress? (2023, methodology): “Heterophily-speciﬁc models We use eight models designed for node classiﬁcation under het-erophily: H 2 GCN (Zhu et al., 2020), CPGNN (Zhu et al., 2021), GPR-GNN (Chien et al., 2021), FSGNN (Maurya et al., 2022), GloGNN (Li et al., 2022), FAGCN (Bo et al., 2021), GBK-8 GNN (Du et al., 2022), and Jaco”
Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks (2021, background): “[12] identified a set of effective designs that allow GCNs to generalize to heterophilous data and handle adversarial attacks [27], and [28] introduced a new GCN model that leverages ideas from belief propagation.”