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

Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, Austin R. Benson

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 Correct and Smooth (C&S) pipeline.

The C&S pipeline consists of three distinct steps:

  1. 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.
  2. 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.
  3. 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.

Accuracy vs. Parameter count on the ogbn-products dataset.
  • Massive Efficiency Gains: On the large-scale ogbn-products dataset, 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

Abstract

Graph Neural Networks (GNNs) are a 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 that have long been used in graph-based semi-supervised learning. 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 is common in traditional methods) yields easy and substantial performance gains. We can also incorporate our techniques into big GNN models, providing modest gains in some cases.
BibTeX
@inproceedings{huang2021combining,
  author = {Qian Huang and Horace He and Abhay Singh and Ser-Nam Lim and Austin R. Benson},
  title = {{Combining Label Propagation and Simple Models out-performs Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=Hbw8hZQH_q},
}
Figure