On Local Aggregation in Heterophilic Graphs
arXiv:2106.03213
Abstract
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.
References in corpus (15)
- Adam: A Method for Stochastic Optimization
- Inductive Representation Learning on Large Graphs
- Mixing patterns in networks
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
- Pitfalls of Graph Neural Network Evaluation
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
- How Powerful are Graph Neural Networks?
- Link Prediction Based on Graph Neural Networks
- On Mutual Information Maximization for Representation Learning
- DeeperGCN: All You Need to Train Deeper GCNs
- Principal Neighbourhood Aggregation for Graph Nets
- Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
- Non-Local Graph Neural Networks
- Permutohedral-GCN: Graph Convolutional Networks with Global Attention