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

By Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, Austin R. Benson. International Conference on Learning Representations, 2020

328 citations recorded by the source corpus.

Graph Neural Networks (GNNs) are the predominant technique for learning over graphs. However, there is relatively little understanding of why GNNs are successful in practice and whether they are necessary for good performance. Here, we show that for many standard transductive node classification benchmarks, we can exceed or match the performance of state-of-the-art GNNs by combining shallow models that ignore the graph structure with two simple post-processing steps that exploit correlation in the label structure: (i) an "error correlation" that spreads residual errors in training data to correct errors in test data and (ii) a "prediction correlation" that smooths the predictions on the test data. We call this overall procedure Correct and Smooth (C&S), and the post-processing steps are implemented via simple modifications to standard label propagation techniques from early graph-based semi-supervised learning methods. Our approach exceeds or nearly matches the performance of state-of-the-art GNNs on a wide variety of benchmarks, with just a small fraction of the parameters and orders of magnitude faster runtime. For instance, we exceed the best known GNN performance on the OGB-Products dataset with 137 times fewer parameters and greater than 100 times less 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. We can also incorporate our techniques into big GNN models, providing modest gains. Our code for the OGB results is at this https URL.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f1e5e65941617604923225cc4bf464e370fcae67

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Uri Alon
2. Eran Yahav
3. Jure Leskovec
4. Matthias Fey
5. Yuxiao Dong
6. Weihua Hu
7. Hongyu Ren
8. Shaked Brody

In Computer Vision and Pattern Recognition

1. Yuxiao Dong
2. Uri Alon
3. Eran Yahav
4. Jure Leskovec
5. Hongyu Ren
6. Weihua Hu
7. Shaked Brody
8. Thomas Liao

In Statistical and Nonlinear Physics

1. Matthias Fey
2. Yuxiao Dong
3. Jure Leskovec
4. Eran Yahav
5. Uri Alon
6. Weihua Hu
7. Hongyu Ren
8. Thomas Liao

Citations in the corpus

• Are We Learning Yet? A Meta Review of Evaluation Failures Across Machine Learning (2021, background): “…to smaller details and thorough feature engineering can often make a huge difference for these simple baselines: • In graph learning, logistic regression combined with simple feature engineering provided comparable performance to neural networks while being orders of magnitude faster [67, 162].”
• Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, unknown): “Also, we include SGC [71] and C&S [32] as simple, scalable methods that perform well on homophilic datasets.”
• A Metaverse: Taxonomy, Components, Applications, and Open Challenges (2022, unknown): “Huang et al. [284] implemented a post-processing step with simple modifications to the standard label propagation technique in the initial graph-based semi-supervised learning method.”
• How Attentive are Graph Attention Networks? (2021, background): “…2021; Rong et al., 2020a; Hassani and Khasahmadi, 2020), graph regularization methods (Wang et al., 2019a; Zhao and Akoglu, 2020; Rong et al., 2020b), and other tricks (Wang, 2021; Huang et al., 2021) are orthogonal to the contribution of the GNN layer itself, and might further improve all GNNs.”
• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs (2021, methodology): “More recently, researchers improve the model scalability by significantly simplifying GNNs (Wu et al., 2019; Rossi et al., 2020; Huang et al., 2020), which inevitably limits their expressive power.”