The Problem with Complex GNNs
In recent years, the field of graph machine learning has been dominated by increasingly complex Graph Neural Network (GNN) architectures, such as GCN, GraphSAGE, and GAT. While these models are undeniably powerful, they often function as "black boxes" that are difficult to scale to massive datasets and computationally expensive to train.
This raises a fundamental question: Do we actually need these complex architectures to achieve high performance on graph data?
The authors of this paper suggest that much of the "magic" in graph learning actually stems from simple correlations in labels among neighboring nodes (a concept known as homophily). They argue that this correlation can be captured much more efficiently than through deep, end-to-end neural message passing.
The "Correct and Smooth" (C&S) Pipeline
To prove this, the authors propose a remarkably simple three-part pipeline called Correct and Smooth (C&S). This approach completely decouples feature learning from the graph topology during the training phase.
The C&S pipeline consists of three distinct steps:
- Simple Base Predictor: First, a shallow model—like a Multi-Layer Perceptron (MLP) or even a linear model—is trained to predict node labels using only node features. The graph structure is completely ignored during this step.
- Correction Step (Error Correlation): Because the base model ignores the graph, it likely makes errors. However, since neighboring nodes are often similar, their errors are likely correlated. C&S "spreads" the residual errors from the training data across the graph using label propagation. This step "corrects" the base predictions for unlabeled nodes based on the known errors of their neighbors.
- Smoothing Step (Prediction Correlation): Finally, the model performs another round of label propagation to smooth the final predictions across the graph. This ensures that adjacent nodes have similar predicted label distributions.
Crucially, the graph structure is only used as a post-processing mechanism.
Key Insights
- Labels are Powerful Features: Traditional GNNs typically use labels only as training targets. The C&S pipeline demonstrates that directly incorporating known label information into the inference process (via propagation) provides massive performance gains for very little computational cost.
- Decoupling is Efficient: By ignoring the graph during the initial MLP training, the model avoids the "neighbor explosion" problem that makes scaling deep GNNs notoriously difficult. An MLP can be trained on a single GPU in seconds, after which the post-processing steps are applied rapidly.
- Error Correlation Matters: Propagating uncertainty and residuals (the Correction step) is a novel insight that proves just as important as smoothing the final labels.
- Spectral Embeddings as a "Cheat Code": The authors found that adding simple spectral embeddings (eigenvectors of the graph Laplacian) as input features to the MLP often gave the simple model enough "graph awareness" to rival deep GNNs.
Key Results
The researchers evaluated C&S on nine diverse transductive node classification benchmarks, including the Open Graph Benchmark (OGB), citation networks, and social/geographic datasets. The results serve as a wake-up call for the GNN community.
- Massive Efficiency Gains: On the large-scale
ogbn-productsdataset, C&S achieved a higher accuracy than the best-known GNN at the time, despite having 137 times fewer parameters and training 100 times faster. - State-of-the-Art Performance: Across the board, C&S outperformed or matched state-of-the-art (SOTA) models on 7 out of the 9 evaluated datasets.
- GNN Enhancement: C&S isn't just a replacement for GNNs; it can also be used to boost them. The authors demonstrated that adding C&S post-processing to existing top-tier models (like GAT on
ogbn-arxiv) pushed them even higher up the leaderboards.
Limitations and Future Work
While highly effective, the C&S approach has limitations. The paper focuses primarily on transductive learning, where the entire graph structure is known at training time. Applying these simple propagation techniques to inductive settings (where new, unseen nodes arrive later) is more challenging.
Furthermore, C&S relies heavily on the assumption of homophily. On "heterophilous" graphs—where neighbors tend to have different labels—simple label propagation might struggle. Finally, while C&S excels when features and labels provide strong signals, massive GNNs may still hold an advantage in niche cases requiring the capture of highly complex, non-linear interactions between node features and graph topology.
Summary updated