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

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.

References in corpus (14)

• Near linear time algorithm to detect community structures in large-scale networks
• Mixing patterns in networks
• Fast Graph Representation Learning with PyTorch Geometric
• Simplifying Graph Convolutional Networks
• Social Structure of Facebook Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Simple and Deep Graph Convolutional Networks
• Scaling Graph Neural Networks with Approximate PageRank
• SIGN: Scalable Inception Graph Neural Networks
• GMNN: Graph Markov Neural Networks
• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• Unifying Graph Convolutional Neural Networks and Label Propagation
• Residual Correlation in Graph Neural Network Regression

Cited by in corpus (42)

• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
• Graph Attention Multi-Layer Perceptron
• On Representation Knowledge Distillation for Graph Neural Networks
• Label Information Enhanced Fraud Detection against Low Homophily in Graphs
• How Attentive are Graph Attention Networks?
• Differentially Private Graph Classification with GNNs
• Bag of Tricks for Node Classification with Graph Neural Networks
• New Benchmarks for Learning on Non-Homophilous Graphs
• Understanding and Resolving Performance Degradation in Graph Convolutional Networks
• CLDG: Contrastive Learning on Dynamic Graphs
• Graph Condensation for Graph Neural Networks
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• Graph-based Label Propagation for Semi-Supervised Speaker Identification
• Residual Network and Embedding Usage: New Tricks of Node Classification with Graph Convolutional Networks
• Large-scale graph representation learning with very deep GNNs and self-supervision
• p2pGNN: A Decentralized Graph Neural Network for Node Classification in Peer-to-Peer Networks
• Node Injection Attack Based on Label Propagation Against Graph Neural Network
• Revisiting Neighborhood-based Link Prediction for Collaborative Filtering
• On the Equivalence of Decoupled Graph Convolution Network and Label Propagation
• Residual Correction in Real-Time Traffic Forecasting
• Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation
• Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
• Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
• On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs
• How Framelets Enhance Graph Neural Networks
• Network In Graph Neural Network
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
• Deep Attention-guided Graph Clustering with Dual Self-supervision
• Why Propagate Alone? Parallel Use of Labels and Features on Graphs
• $p$-Laplacian Based Graph Neural Networks
• Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks
• Implicit SVD for Graph Representation Learning
• Should Graph Neural Networks Use Features, Edges, Or Both?
• ${\ell }_2$-norm Flow Diffusion in Near-Linear Time
• Prior Signal Editing for Graph Filter Posterior Fairness Constraints
• Scalable Consistency Training for Graph Neural Networks via Self-Ensemble Self-Distillation
• Scaffold-Induced Molecular Graph (SIMG): Effective Graph Sampling Methods for High-Throughput Computational Drug Discovery
• Deep Fraud Detection on Non-attributed Graph
• Does your graph need a confidence boost? Convergent boosted smoothing on graphs with tabular node features
• Sequential Aggregation and Rematerialization: Distributed Full-batch Training of Graph Neural Networks on Large Graphs
• A nonlinear diffusion method for semi-supervised learning on hypergraphs
• SAS: A Simple, Accurate and Scalable Node Classification Algorithm