PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2010.13993v2cs.LGcs.SI

TL;DR

The paper examines whether complex GNNs are necessary for strong transductive node-classification performance. It combines shallow feature-based predictors with label-propagation correction and smoothing, and reports performance matching or exceeding state-of-the-art GNNs at much lower computational cost.

  • Problem

    The paper addresses limited understanding of why GNNs work well and whether they are necessary for strong transductive node-classification performance.

  • Method

    Correct and Smooth combines a graph-agnostic base predictor with label-propagation steps for error correction and final prediction smoothing.

  • Results

    Across several node-classification tasks, C&S achieves state-of-the-art performance with orders of magnitude fewer parameters and training time than large GNN models.

  • Takeaways & Limitations

    Directly incorporating labels through simple label-propagation post-processing provides substantial performance gains, while the approach can also yield modest gains when combined with GNNs.

  • Takeaways & Limitations

    For the classification problems considered, smoothed errors may not be correctly calibrated in scale, so the error-correction procedure requires adjustment.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper asks whether complex GNNs are necessary for transductive node classification and proposes a simpler alternative: feature-based predictions followed by label-propagation correction and smoothing. This approach matches or exceeds strong GNN performance while using far fewer parameters and substantially less training time.

  • GNNs have achieved strong results, but their increasing complexity makes performance gains difficult to understand and large-dataset training difficult.
  • Correct and Smooth combines graph-agnostic base predictions with error correction and prediction smoothing through label propagation.The base model can be an MLP or linear model; the graph is used during post-processing rather than parameter learning.
  • The correction step propagates training-data errors across the graph, while smoothing spreads the corrected predictions over connected nodes.
  • The method repurposes classical graph-based semi-supervised learning techniques, especially label propagation, to incorporate label information directly.The paper relates this design to earlier diffusion-based methods and to positive correlations among neighboring nodes.
  • C&S achieves state-of-the-art performance on several node-classification tasks with orders of magnitude fewer parameters and training time than large GNN models.The approach can also be combined with state-of-the-art GNNs, producing modest additional gains.

2 CORRECT AND SMOOTH MODEL

Correct and Smooth combines a graph-agnostic base predictor with two post-processing label-propagation steps: error correction and prediction smoothing. The pipeline uses graph structure only after base prediction, keeping training simple while exploiting correlated errors and neighboring labels.

  • Base predictor: C&S starts with a linear model or shallow MLP that predicts from node features without learning over the graph.The base predictor produces probability distributions for all nodes; graph information may be used only for optional feature augmentation.
  • Error correction: The correction step propagates residual errors observed on training nodes, then adds the smoothed errors to the base predictions.The error matrix contains training residuals and zeros elsewhere, while label spreading estimates correlated errors across the graph.
  • Error correction: Because propagated classification errors may have the wrong scale, C&S adjusts residual magnitude using scaling based on training-node errors.The paper introduces autoscaling from the average training error and a fixed-diffusion variant with a learned scale.
  • Prediction smoothing: The smoothing step resets training nodes to their true labels and propagates corrected score vectors so neighboring nodes receive smoother label distributions.Final node labels are selected by the largest component of the converged smoothed prediction.
  • Pipeline properties: C&S decouples both label-propagation steps from training, unlike APPNP, which integrates smoothing end to end and does not incorporate labels at inference.The resulting pipeline uses a cheap feature-only predictor followed by error propagation and prediction smoothing.

3 EXPERIMENTS ON TRANSDUCTIVE NODE CLASSIFICATION

Across nine transductive node-classification datasets, C&S combines simple base predictors with label-propagation post-processing and often matches or exceeds GNN performance while using fewer parameters and less training time.

  • Datasets and setup: Nine datasets span benchmark, citation, web, social-network, and county classification tasks with text- or attribute-derived node features.The evaluation uses benchmark-provided or random train/validation/test splits, with typically less than 1% standard deviation across splits.
  • Models and baselines: C&S uses Linear or MLP base predictors, while comparisons include LP, GCN, SGC, APPNP, and dataset-specific state-of-the-art baselines.The base predictors use raw node features and spectral embeddings; Plain Linear uses only raw features, whereas LP uses only labels.
  • First results: 84%: on Products, LP post-processing raises the MLP base prediction from 63% to 84%.Plain Linear with C&S can also outperform plain GCNs in many cases, while LP alone is often competitive with GCNs.
  • First results: C&S model variants outperform state-of-the-art on Products, Cora, Email, Rice31, and US County, while showing little difference from the best baseline on other datasets.The first comparison uses only training labels; validation labels provide further improvements.
  • Using more labels: Seven of nine datasets: using validation labels, the best C&S model outperforms state-of-the-art, often by substantial margins.Validation labels are used for C&S post-processing and hyperparameter selection, not to update the base prediction model.
  • Efficiency and scale: 137 times fewer parameters and over 100 times faster training: a linear C&S model exceeds the Products state-of-the-art comparison.On papers100M, Linear+C&S reaches 65.33% versus 63.29% for the state of the art reported on October 1, 2020, although exhaustive GNN benchmarking was computationally infeasible.

4 DISCUSSION

The discussion argues that increasingly expressive GNNs should be complemented by simpler techniques, especially label propagation and feature augmentation, which can improve predictions while reducing training costs.

  • Label propagation and feature augmentation are proposed as simpler alternatives for improving graph-learning performance.The paper characterizes label propagation as a longstanding and powerful idea.
  • These techniques can provide both better predictions and faster training.

A MODEL DETAILS

The experiments use standard optimization and benchmark configurations, with dataset-specific MLP architectures and selected state-of-the-art baselines implemented in PyTorch and PyTorch Geometric.

  • All models use Adam, tuned learning rates, OGB and wikiCS configurations, and validation-based hyperparameter tuning.Some hyperparameters are manually tuned for potential better performance.
  • MLPs apply batch normalization, ReLU activation, and 0.5 dropout after every linear layer.
  • MLP configurations: OGB MLPs use 3 layers, 256 hidden channels, and learning rate 0.01.
  • MLP configurations: Cora, Citeseer, Pubmed, and Email MLPs use 3 layers, 64 hidden channels, and learning rate 0.01.
  • MLP configurations: wikiCS MLPs use 3 layers, 256 hidden channels, and learning rate 0.005, while US County and Rice31 use 5 layers, 256 hidden channels, and learning rate 0.005.
  • Baselines: SOTA baselines include UniMP for Arxiv and Products, reused top scores for Cora, Citeseer, and Pubmed, GCNII for Email and US County, GCN with spectral and node2vec embeddings for Rice31, and APPNP for wikiCS.
  • All models were implemented with PyTorch and PyTorch Geometric.

B PERFORMANCE RESULTS WITH ONLY RESIDUAL CORRELATION

The residual-correlation correction step alone improves predictions, but the results indicate that both label-propagation steps contribute significantly to the final C&S gains.

  • Both residual correction and final prediction smoothing matter significantly for the final C&S improvements.Table 6 evaluates residual correlation without smoothing, isolating the correction step.

C ADDITIONAL VISUALIZATION

Additional visualizations compare ground-truth labels, linear base predictions, and GCN predictions for US County and Rice31, while Table 6 isolates C&S error correction without final smoothing.

  • Visualization method: Rice31 is visualized by projecting its 128-dimensional spectral embedding into two dimensions with UMAP.
  • Residual correlation: Table 6 reports C&S performance with error correction but without final prediction smoothing, using only ground-truth training labels.
  • US County: US County visualizations include ground-truth labels, the C&S linear base prediction, and GCN predictions.
  • Rice31: Rice31 visualizations include ground-truth labels, the C&S linear base predictor, and GCN predictions.
Loading 2010.13993v2…