Combining Label Propagation and Simple Models out-performs Graph Neural Networks

Graph Neural Networks (GNNs) are now a predominant technique for learning over graphs. However, there is relatively little understanding of why GNNs are successful and whether they are necessary for good performance. Here, we show that for many standard transductive node classification benchmarks, we can ex-ceed or match the performance of state-of-the-art GNNs by combining shallow multilayer perceptrons models (that ignore the graph structure entirely) with two simple postprocessings for correlation in the label structure: (i) an “error correlation” that spreads residual errors in training data to correct errors in test data and(ii) an “prediction correlation” that smooths the predictions on the test data. These correlations are implemented via simple modifications to standard label propagation techniques developed in early graph-based semi-supervised learning methods. Our approach achieves state-of-the-art performance across a wide variety of benchmarks, with just a small fraction of the parameters and orders of magnitude faster runtime compared to highly-parameterized GNNs (for instance, we exceed the best known GNN performance on the OGB-Products dataset with >100x fewer parameters and >100x faster training time). The performance of our methods highlights how directly incorporating label information into the learning algorithm (as was done in traditional techniques) yields easy and substantial performance gains, and we argue that GNNs have been approximating this idea, albeit implicitly. We also incorporate label correlation into SOTA GNN models, providing modest gains.