On Local Aggregation in Heterophilic Graphs
  Many recent works have studied the performance of Graph Neural Networks
(GNNs) in the context of graph homophily - a label-dependent measure of
connectivity. Traditional GNNs generate node embeddings by aggregating
information from a node's neighbors in the graph. Recent results in node
classification tasks show that this local aggregation approach performs poorly
in graphs with low homophily (heterophilic graphs). Several mechanisms have
been proposed to improve the accuracy of GNNs on such graphs by increasing the
aggregation range of a GNN layer, either through multi-hop aggregation, or
through long-range aggregation from distant nodes. In this paper, we show that
properly tuned classical GNNs and multi-layer perceptrons match or exceed the
accuracy of recent long-range aggregation methods on heterophilic graphs. Thus,
our results highlight the need for alternative datasets to benchmark long-range
GNN aggregation mechanisms. We also show that homophily is a poor measure of
the information in a node's local neighborhood and propose the Neighborhood
Information Content(NIC) metric, which is a novel information-theoretic graph
metric. We argue that NIC is more relevant for local aggregation methods as
used by GNNs. We show that, empirically, it correlates better with GNN accuracy
in node classification tasks than homophily.
