Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

We investigate the representation power of graph neural networks in the\nsemi-supervised node classification task under heterophily or low homophily,\ni.e., in networks where connected nodes may have different class labels and\ndissimilar features. Many popular GNNs fail to generalize to this setting, and\nare even outperformed by models that ignore the graph structure (e.g.,\nmultilayer perceptrons). Motivated by this limitation, we identify a set of key\ndesigns -- ego- and neighbor-embedding separation, higher-order neighborhoods,\nand combination of intermediate representations -- that boost learning from the\ngraph structure under heterophily. We combine them into a graph neural network,\nH2GCN, which we use as the base method to empirically evaluate the\neffectiveness of the identified designs. Going beyond the traditional\nbenchmarks with strong homophily, our empirical analysis shows that the\nidentified designs increase the accuracy of GNNs by up to 40% and 27% over\nmodels without them on synthetic and real networks with heterophily,\nrespectively, and yield competitive performance under homophily.\n