Graph Neural Networks with Heterophily

Authors

  • Jiong Zhu University of Michigan
  • Ryan A. Rossi Adobe Research
  • Anup Rao Adobe Research
  • Tung Mai Adobe Research
  • Nedim Lipka Adobe Research
  • Nesreen K. Ahmed Intel Labs
  • Danai Koutra University of Michigan

Keywords:

Relational Learning, Graph-based Machine Learning, Graph Mining, Social Network Analysis & Community

Abstract

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.

Downloads

Published

2021-05-18

How to Cite

Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., & Koutra, D. (2021). Graph Neural Networks with Heterophily. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 11168-11176. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17332

Issue

Section

AAAI Technical Track on Machine Learning V