Abstract
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 https://github.com/Chillee/CorrectAndSmooth.
Introduction
In recent years, Graph Neural Networks (GNNs) have become the undisputed kings of graph-based machine learning. The research community has been locked in an "arms race" to develop increasingly complex architectures (like GATs, GCNII, and UniMP) to capture intricate relational data. However, these models come with a heavy "complexity tax": they are difficult to tune, expensive to train, and hard to scale to massive datasets. This work asks a fundamental question: Are these complex architectures actually necessary for good performance? We suggest that the field may be over-engineering solutions while ignoring simpler, more direct ways to utilize graph structure—specifically, the labels themselves.
The Correct and Smooth (C&S) Pipeline
The proposed Correct and Smooth (C&S) pipeline decouples the learning of node features from the graph structure. This method consists of three distinct stages:
- Simple Base Predictor: Instead of a GNN, the process begins with a simple model (such as a shallow MLP) that makes predictions based only on node features, completely ignoring the graph edges during training.
- The "Correct" Step (Residual Correlation): This step assumes that errors in the base prediction are positively correlated across the graph. Known residuals from the training data are "spread" across the graph using label propagation to correct the initial predictions for unlabeled nodes.
- The "Smooth" Step (Prediction Correlation): Finally, the corrected predictions undergo another round of label propagation to smooth the results. This leverages the principle of homophily, where adjacent nodes are likely to share the same label.
Key Results and Efficiency
The results demonstrate that simplicity can be remarkably powerful. On the OGB-Products dataset, C&S achieved higher accuracy than the best GNNs on the leaderboard while using 137 times fewer parameters and training 100 times faster.
When incorporating validation labels, C&S outperformed state-of-the-art (SOTA) models on 7 out of 9 datasets. Even a "Plain Linear" model combined with C&S was sufficient to outperform standard Graph Convolutional Networks (GCNs) in many cases. Furthermore, when C&S was applied as a post-processing step to existing SOTA GNNs, it still provided modest gains, indicating that even complex models were not fully capturing label correlations.
Key Insights
- Labels are High-Signal: Traditional GNNs often use labels only for the loss function. C&S treats labels as a primary source of information to be propagated directly through the graph, which proves to be incredibly effective.
- GNNs as Implicit Smoothers: Much of a GNN's success likely comes from its ability to smooth predictions over the graph. C&S makes this smoothing explicit and separates it from feature learning.
- Decoupling for Scalability: By training the base predictor without graph structure, the model avoids the "neighborhood explosion" problem, allowing it to scale easily to massive graphs.
Conclusion
The performance of C&S highlights how directly incorporating label information into the learning algorithm yields substantial performance gains with minimal complexity. By explicitly modeling label correlations through simple post-processing, we can achieve state-of-the-art results with much simpler and more efficient models. This suggests that for many node classification tasks, the current trend toward increasingly complex GNN architectures may be unnecessary.
Summary updated