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

The authors argue that we need to enable graph neural nets to model graphs beyond homophily, which is reasonable and great. However, the three corresponding designs that are introduced to address this issue lack of technical novelty and depth. All of the three designs have been proposed and well utilized (in a separated way) in existing graph neural nets. The proposed H2GNN model puts all three design together without clear discussions about their original sources during the authors' arguments (though table 2 is used in related work). Furthermore, the goal of the three designs is to model heterophily in graphs or networks.

The paper presents three GNN architectural guidelines for combating this, which can lead to improved predictions, particularly on networks exhibiting heterophilous structure (i.e., non-homophilous labels). The design choices are motivated theoretically and intuitively and then combined into a single model that can provide better predictions on networks with heterophilous structure, as demonstrated by synthetic and real-world data experiments. The paper provides a number of interesting insights into why certain GNN architectural choices can help predictions in the case of low network homophily. Although not mentioned in their paper, a similar idea to higher-order neighborhoods (Section 3.1.2) I believe that these ideas provide further motivation for the design choices appearing in this paper and including them will strengthen some of the intuition.

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