# How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

arXiv: https://arxiv.org/abs/2009.11848 · HTML: https://mlsanity.com/paper/2009.11848/

## Key facts

- Cited by 222 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2020.

## Built on by (most cited first, 30 of 222)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Domain Generalization: A Survey](https://mlsanity.com/paper/2103.02503/) (2021)
- [Domain Generalization with MixStyle](https://mlsanity.com/paper/2104.02008/) (2021)
- [Implicit Behavioral Cloning](https://mlsanity.com/paper/2109.00137/) (2021)
- [Pre-Trained Models: Past, Present and Future](https://mlsanity.com/paper/2106.07139/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [How Far is Video Generation from World Model: A Physical Law Perspective](https://mlsanity.com/paper/2411.02385/) (2024)
- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [LIFT: Language-Interfaced Fine-Tuning for Non-Language Machine Learning Tasks](https://mlsanity.com/paper/2206.06565/) (2022)
- [Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs](https://mlsanity.com/paper/2202.05441/) (2022)
- [Local Texture Estimator for Implicit Representation Function](https://mlsanity.com/paper/2111.08918/) (2021)
- [Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2101.05265/) (2021)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [NICO++: Towards Better Benchmarking for Domain Generalization](https://mlsanity.com/paper/2204.08040/) (2022)
- [Sparse Mixture-of-Experts are Domain Generalizable Learners](https://mlsanity.com/paper/2206.04046/) (2022)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [OOD-GNN: Out-of-Distribution Generalized Graph Neural Network](https://mlsanity.com/paper/2112.03806/) (2021)
- [Subspace Diffusion Generative Models](https://mlsanity.com/paper/2205.01490/) (2022)
- [Robust Scheduling with GFlowNets](https://mlsanity.com/paper/2302.05446/) (2023)
- [Reliable extrapolation of deep neural operators informed by physics or sparse observations](https://mlsanity.com/paper/2212.06347/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2204.07321/) (2022)

## Abstract (arXiv)

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 feedforward neural networks, a.k.a. multilayer perceptrons (MLPs), do not extrapolate well in certain simple tasks, Graph Neural Networks (GNNs) -- structured networks with MLP modules -- have 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 nonlinear functions. But, they can provably learn a linear target function when the training distribution is sufficiently "diverse". Second, in connection to analyzing the 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. Our theoretical analysis builds on a connection of over-parameterized networks to the neural tangent kernel. Empirically, our theory holds across different training settings.