Abstract: Graph neural networks (GNNs), as the de-facto model class for representation learning on graphs, are built upon the multi-layer perceptrons (MLP) architecture with additional message passing layers to allow features to flow across nodes. While conventional wisdom commonly attributes the success of GNNs to their advanced expressivity, we conjecture that this is not the main cause of GNNs' superiority in node-level prediction tasks. This paper pinpoints the major source of GNNs' performance gain to their intrinsic generalization capability, by introducing an intermediate model class dubbed as P(ropagational)MLP, which is identical to standard MLP in training, but then adopts GNN's architecture in testing. Intriguingly, we observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training. This finding sheds new insights into understanding the learning behavior of GNNs, and can be used as an analytic tool for dissecting various GNN-related research problems. As an initial step to analyze the inherent generalizability of GNNs, we show the essential difference between MLP and PMLP at infinite-width limit lies in the NTK feature map in the post-training stage. Moreover, by examining their extrapolation behavior, we find that though many GNNs and their PMLP counterparts cannot extrapolate non-linear functions for extremely out-of-distribution samples, they have greater potential to generalize to testing samples near the training data range as natural advantages of GNN architectures.
TL;DR
This paper reveals that the success of Graph Neural Networks (GNNs) stems more from their inherent generalization capability at inference time than their training-time expressivity. By introducing the Propagational MLP (PMLP)—a model trained as a standard MLP but tested with GNN-style message passing—the authors show you can match GNN performance while training up to 17x faster.
What Problem Does This Paper Address?
In graph representation learning, GNNs consistently outperform Multi-Layer Perceptrons (MLPs). Conventional wisdom suggests this is because GNNs are more "expressive"—their message-passing layers allow them to learn complex relational patterns that a simple MLP, which treats nodes as independent points, cannot see.
However, the authors ask a provocative question: Is the graph structure actually necessary during training? They aim to decouple the benefits of "representation power" (what the model can learn) from "generalization power" (how the model applies what it learned to new data). By bridging the gap between MLPs and GNNs, they seek to pinpoint exactly where the "GNN magic" happens.
Methods
The authors introduce a clever intermediate model class called Propagational MLPs (PMLPs).
- Training Phase: The PMLP is identical to a standard MLP. It ignores the graph structure entirely and learns weights based solely on individual node features.
- Inference Phase: During testing, non-parametric message-passing (MP) layers are "plugged in" to the trained MLP architecture to align it with a specific GNN counterpart (like GCN, SGC, or APPNP).
Essentially, a PMLP is an MLP that "pretends" to be a GNN only when it's time to make predictions.
To explain why this works, the authors use Neural Tangent Kernel (NTK) theory to analyze models at the "infinite-width limit," comparing how their feature maps evolve and how they behave when "extrapolating" to data points far outside the training range.
Datasets
The study utilizes 16 benchmark datasets across various categories, including Citation Networks (Cora, Citeseer, Pubmed), Product/Co-occurrence (Amazon-Photo, Amazon-Computer), Co-authorship (CS, Physics), Large-scale (OGBN-Arxiv, OGBN-Products, Flickr), and Heterophily datasets (Chameleon, Squirrel, Film, etc.).
Key Insights and Ideas
- The "Inherent" Advantage: PMLPs perform nearly as well as standard GNNs. This suggests message-passing acts as a powerful post-training regularizer that encourages better generalization, regardless of whether it was present during weight learning.
- Training vs. Inference: GNNs often achieve lower training loss, but the "generalization gap" is much smaller for PMLPs and GNNs compared to MLPs.
- Smoother Extrapolation: Standard MLPs collapse into simple linear functions quickly when faced with Out-of-Distribution (OoD) samples. GNN architectures (and PMLPs) converge to these limits much more slowly, allowing them to handle samples near the training boundary more effectively.
- Robustness to Noise: Because PMLPs don't see the graph during training, they are more robust to "noisy" or "fake" edges. A standard GNN might overfit to a bad graph structure, whereas a PMLP only uses the graph as a hint during inference.
Key Results
- Performance: On datasets like Cora, PMLP improved upon the base MLP's accuracy by over 37%, reaching parity with GCN.
- Efficiency: PMLPs are significantly faster to train by avoiding recursive neighborhood aggregation in the training loop. On large datasets, PMLPs were 5x to 17x faster than GNNs. For deep architectures (100+ layers), the speedup reached 65x.
- Scalability: Standard MLP training is trivial to implement with mini-batching, making PMLP highly suitable for massive graphs where standard GNN training hits memory bottlenecks.
Limitations and Future Work
- The Expressivity Gap: On extremely large and complex datasets (like OGBN-Products), standard GNNs still hold a slight edge, suggesting that seeing the graph during training is sometimes necessary for the most informative features.
- Transductive Learning: The default PMLP doesn't leverage unlabeled nodes during training. While extensions like label propagation are possible, they weren't the primary focus of this theoretical analysis.
- Regression vs. Classification: The NTK analysis assumes a regression task with squared loss. While empirical evidence carries over to classification, a formal theoretical bridge for cross-entropy loss remains an open area.
In summary, this paper provides a compelling argument that we might be over-complicating GNN training. For many tasks, a fast MLP training session followed by a "graph-aware" inference step is all you need.
Summary updated