How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

By Keyulu Xu, Jingling Li, Mozhi Zhang, Simon Shaolei Du, Ken-ichi Kawarabayashi, Stefanie Sabrina Jegelka. 2020

370 citations recorded by the source corpus.

We study how neural networks trained by gradient descent extrapolate, i.e., what they learn outside the support of the training distribution. Previous works report mixed empirical results when extrapolating with neural networks: while multilayer perceptrons (MLPs) do not extrapolate well in certain simple tasks, Graph Neural Network (GNN), a structured network with MLP modules, has shown some success in more complex tasks. Working towards a theoretical explanation, we identify conditions under which MLPs and GNNs extrapolate well. First, we quantify the observation that ReLU MLPs quickly converge to linear functions along any direction from the origin, which implies that ReLU MLPs do not extrapolate most non-linear functions. But, they can provably learn a linear target function when the training distribution is sufficiently "diverse". Second, in connection to analyzing successes and limitations of GNNs, these results suggest a hypothesis for which we provide theoretical and empirical evidence: the success of GNNs in extrapolating algorithmic tasks to new data (e.g., larger graphs or edge weights) relies on encoding task-specific non-linearities in the architecture or features.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhiyuan Liu
2. Minlie Huang
3. Sergey Levine
4. Tao A. Xiang
5. Maosong Sun
6. Yu Qiao
7. Xipeng Qiu
8. Jie Tang

Citations in the corpus

• Pre-Trained Models: Past, Present and Future (2021, background): “Since deep neural networks usually have a large number of parameters, they are thus easy to overfit and have poor generalization ability (Belkin et al., 2019; Xu et al., 2021) without sufficient training data.”
• Implicit Behavioral Cloning (2021, background): “Recent work [22] has shown that explicit models tend to perform linear extrapolation, but the analysis assumes the ground truth function is continuous.”
• Domain Generalization with MixStyle (2021, background): “A recent work by Xu et al. (2021) also emphasizes the”
• Subspace Diffusion Generative Models (2022, background): “Due to the curse of dimensionality, much of this support may never be visited during training, and the accuracy of the score model in these regions is called into question by the uncertain extrapolation abilities of neural networks [23].”
• The Risks of Invariant Risk Minimization (2020, background): “Xu et al. (2021) show that an infinitely wide two-layer network extrapolates linear functions when the training data is sufficiently diverse.”
• LIFT: Language-Interfaced Fine-Tuning for Non-Language Machine Learning Tasks (2022, methodology): “[40] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka.”