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 provides a new perspective
for understanding the learning behavior of GNNs, and can be used as an analytic
tool for dissecting various GNN-related research problems including
expressivity, generalization, over-smoothing and heterophily. As an initial
step to analyze PMLP, we show its essential difference to MLP at infinite-width
limit lies in the NTK feature map in the post-training stage. Moreover, through
extrapolation analysis (i.e., generalization under distribution shifts), we
find that though most GNNs and their PMLP counterparts cannot extrapolate
non-linear functions for extreme out-of-distribution data, they have greater
potential to generalize to testing data near the training data support as
natural advantages of the GNN architecture used for inference.

本文通过引入中间模型 PMLP，揭示了 GNN 的性能提升主要源于其本质上的泛化能力，而非原理层面上的增强表现力。同时，本文发现 PMLP 表现与 GNN 相当，但训练效率更高。该发现为解析 GNN 相关问题提供了新的视角。