How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks — part 1/11

Cleaned-text code points [0, 15904). Bibliography omitted here; source.md includes it.

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

###### Abstract

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.

## 1 Introduction

Humans extrapolate well in many tasks. For example, we can apply arithmetics to arbitrarily large numbers. One may wonder whether a neural network can do the same and generalize to examples arbitrarily far from the training data ( Lake et al., 2017 ) . Curiously, previous works report mixed extrapolation results with neural networks. Early works demonstrate feedforward neural networks, a.k.a. multilayer perceptrons (MLPs), fail to extrapolate well when learning simple polynomial functions ( Barnard & Wessels, 1992 ; Haley & Soloway, 1992 ) . However, recent works show Graph Neural Networks (GNNs) ( Scarselli et al., 2009 ) , a class of structured networks with MLP building blocks, can generalize to graphs much larger than training graphs in challenging algorithmic tasks, such as predicting the time evolution of physical systems ( Battaglia et al., 2016 ) , learning graph algorithms ( Velickovic et al., 2020 ) , and solving mathematical equations ( Lample & Charton, 2020 ) .

To explain this puzzle, we formally study how neural networks trained by gradient descent (GD) extrapolate, i.e., what they learn outside the support of training distribution. We say a neural network extrapolates well if it learns a task outside the training distribution. At first glance, it may seem that neural networks can behave arbitrarily outside the training distribution since they have high capacity ( Zhang et al., 2017 ) and are universal approximators ( Cybenko, 1989 ; Funahashi, 1989 ; Hornik et al., 1989 ; Kurkova, 1992 ) . However, neural networks are constrained by gradient descent training ( Hardt et al., 2016 ; Soudry et al., 2018 ) . In our analysis, we explicitly consider such implicit bias through the analogy of the training dynamics of over-parameterized neural networks and kernel regression via the neural tangent kernel (NTK) ( Jacot et al., 2018 ) .

Starting with feedforward networks, the simplest neural networks and building blocks of more complex architectures such as GNNs, we establish that the predictions of over-parameterized MLPs with ReLU activation trained by GD converge to linear functions along any direction from the origin. We prove a convergence rate for two-layer networks and empirically observe that convergence often occurs close to the training data (Figure 1 ), which suggests ReLU MLPs cannot extrapolate well for most nonlinear tasks. We emphasize that our results do not follow from the fact that ReLU networks have finitely many linear regions ( Arora et al., 2018 ; Hanin & Rolnick, 2019 ; Hein et al., 2019 ) . While having finitely many linear regions implies ReLU MLPs eventually become linear, it does not say whether MLPs will learn the correct target function close to the training distribution. In contrast, our results are non-asymptotic and quantify what kind of functions MLPs will learn close to the training distribution. Second, we identify a condition when MLPs extrapolate well: the task is linear and the geometry of the training distribution is sufficiently “diverse”. To our knowledge, our results are the first extrapolation results of this kind for feedforward neural networks.

We then relate our insights into feedforward neural networks to GNNs, to explain why GNNs extrapolate well in some algorithmic tasks. Prior works report successful extrapolation for tasks that can be solved by dynamic programming (DP) ( Bellman, 1966 ) , which has a computation structure aligned with GNNs ( Xu et al., 2020 ) . DP updates can often be decomposed into nonlinear and linear steps. Hence, we hypothesize that GNNs trained by GD can extrapolate well in a DP task, if we encode appropriate non-linearities in the architecture and input representation (Figure 2 ). Importantly, encoding non-linearities may be unnecessary for GNNs to interpolate , because the MLP modules can easily learn many nonlinear functions inside the training distribution ( Cybenko, 1989 ; Hornik et al., 1989 ; Xu et al., 2020 ) , but it is crucial for GNNs to extrapolate correctly. We prove this hypothesis for a simplified case using Graph NTK ( Du et al., 2019b ) . Empirically, we validate the hypothesis on three DP tasks: max degree, shortest paths, and n n -body problem. We show GNNs with appropriate architecture, input representation, and training distribution can predict well on graphs with unseen sizes, structures, edge weights, and node features. Our theory explains the empirical success in previous works and suggests their limitations: successful extrapolation relies on encoding task-specific non-linearities, which requires domain knowledge or extensive model search. From a broader standpoint, our insights go beyond GNNs and apply broadly to other neural networks.

To summarize, we study how neural networks extrapolate. First, ReLU MLPs trained by GD converge to linear functions along directions from the origin with a rate of O ⁡ ( 1 / t ) O(1/t) . Second, to explain why GNNs extrapolate well in some algorithmic tasks, we prove that ReLU MLPs can extrapolate well in linear tasks, leading to a hypothesis: a neural network can extrapolate well when appropriate non-linearities are encoded into the architecture and features. We prove this hypothesis for a simplified case and provide empirical support for more general settings.

### 1.1 Related work

Early works show example tasks where MLPs do not extrapolate well, e.g. learning simple polynomials ( Barnard & Wessels, 1992 ; Haley & Soloway, 1992 ) . We instead show a general pattern of how ReLU MLPs extrapolate and identify conditions for MLPs to extrapolate well. More recent works study the implicit biases induced on MLPs by gradient descent, for both the NTK and mean field regimes ( Bietti & Mairal, 2019 ; Chizat & Bach, 2018 ; Song et al., 2018 ) . Related to our results, some works show MLP predictions converge to “simple” piecewise linear functions, e.g., with few linear regions ( Hanin & Rolnick, 2019 ; Maennel et al., 2018 ; Savarese et al., 2019 ; Williams et al., 2019 ) . Our work differs in that none of these works explicitly studies extrapolation, and some focus only on one-dimensional inputs. Recent works also show that in high-dimensional settings of the NTK regime, MLP is asymptotically at most a linear predictor in certain scaling limits ( Ba et al., 2020 ; Ghorbani et al., 2019 ) . We study a different setting (extrapolation), and our analysis is non-asymptotic in nature and does not rely on random matrix theory.

Prior works explore GNN extrapolation by testing on larger graphs ( Battaglia et al., 2018 ; Santoro et al., 2018 ; Saxton et al., 2019 ; Velickovic et al., 2020 ) . We are the first to theoretically study GNN extrapolation, and we complete the notion of extrapolation to include unseen features and structures.

## 2 Preliminaries

We begin by introducing our setting. Let 𝒳 \mathcal{X} be the domain of interest, e.g., vectors or graphs. The task is to learn an underlying function g : 𝒳 → ℝ g:\mathcal{X}\rightarrow\mathbb{R} with a training set { ( 𝒙 i , y i ) } i = 1 n ⊂ 𝒟 \{(\bm{x}_{i},y_{i})\}_{i=1}^{n}\subset\mathcal{D} , where y i = g ⁡ ( 𝒙 i ) y_{i}=g(\bm{x}_{i}) and 𝒟 \mathcal{D} is the support of training distribution. Previous works have extensively studied in-distribution generalization where the training and the test distributions are identical ( Valiant, 1984 ; Vapnik, 2013 ) ; i.e., 𝒟 = 𝒳 \mathcal{D}=\mathcal{X} . In contrast, extrapolation addresses predictions on a domain 𝒳 \mathcal{X} that is larger than the support of the training distribution 𝒟 \mathcal{D} . We will say a model extrapolates well if it has a small extrapolation error .

###### Definition 1 .

(Extrapolation error). Let f : 𝒳 → ℝ f:\mathcal{X}\rightarrow\mathbb{R} be a model trained on { ( 𝒙 i , y i ) } i = 1 n ⊂ 𝒟 \{(\bm{x}_{i},y_{i})\}_{i=1}^{n}\subset\mathcal{D} with underlying function g : 𝒳 → ℝ g:\mathcal{X}\rightarrow\mathbb{R} . Let 𝒫 \mathcal{P} be a distribution over 𝒳 ∖ 𝒟 \mathcal{X}\setminus\mathcal{D} and let ℓ : ℝ × ℝ → ℝ \ell:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R} be a loss function. We define the extrapolation error of f f as 𝔼 𝒙 ∼ 𝒫 ​ [ ℓ ⁡ ( f ⁡ ( 𝒙 ) , g ⁡ ( 𝒙 ) ) ] \mathbb{E}_{\bm{x}\sim\mathcal{P}}[\ell(f(\bm{x}),g(\bm{x}))] .

We focus on neural networks trained by gradient descent (GD) or its variants with squared loss . We study two network architectures: feedforward and graph neural networks.

Graph Neural Networks. GNNs are structured networks operating on graphs with MLP modules ( Battaglia et al., 2018 ; Xu et al., 2019 ) . Let G = ( V , E ) G=(V,E) be a graph. Each node u ∈ V u\in V has a feature vector 𝒙 u \bm{x}_{u} , and each edge ( u , v ) ∈ E (u,v)\in E has a feature vector 𝒘 ( u , v ) \bm{w}_{(u,v)} . GNNs recursively compute node representations 𝒉 u ( k ) \bm{h}_{u}^{(k)} at iteration k k ( Gilmer et al., 2017 ; Xu et al., 2018 ) . Initially, 𝒉 u ( 0 ) = 𝒙 u \bm{h}_{u}^{(0)}=\bm{x}_{u} . For k = 1 . . K k=1..K , GNNs update 𝒉 u ( k ) \bm{h}_{u}^{(k)} by aggregating the neighbor representations. We can optionally compute a graph representation 𝒉 G \bm{h}_{G} by aggregating the final node representations. That is, 𝒉 u ( k ) = ∑ v ∈ 𝒩 ⁡ ( u ) MLP ( k ) ​ ( 𝒉 u ( k − 1 ) , 𝒉 v ( k − 1 ) , 𝒘 ( v , u ) ) , 𝒉 G = MLP ( K + 1 ) ​ ( ∑ u ∈ G 𝒉 u ( K ) ) . \displaystyle\bm{h}_{u}^{(k)}=\sum\limits_{v\in\mathcal{N}(u)}\text{MLP}^{(k)}\Big(\bm{h}_{u}^{(k-1)},\bm{h}_{v}^{(k-1)},\bm{w}_{(v,u)}\Big),\quad\bm{h}_{G}=\text{MLP}^{(K+1)}\Big(\sum_{u\in G}\bm{h}_{u}^{(K)}\Big). (1) The final output is the graph representation 𝒉 G \bm{h}_{G} or final node representations 𝒉 u ( K ) \bm{h}_{u}^{(K)} depending on the task. We refer to the neighbor aggregation step for 𝒉 u ( k ) \bm{h}_{u}^{(k)} as aggregation and the pooling step in 𝒉 G \bm{h}_{G} as readout . Previous works typically use sum-aggregation and sum-readout ( Battaglia et al., 2018 ) . Our results indicate why replacing them may help extrapolation (Section 4 ).

## 3 How Feedforward Neural Networks Extrapolate

Feedforward networks are the simplest neural networks and building blocks of more complex architectures such as GNNs, so we first study how they extrapolate when trained by GD. Throughout the paper, we assume ReLU activation. Section 3.3 contains preliminary results for other activations.

### 3.1 Linear Extrapolation Behavior of ReLU MLPs

By architecture, ReLU networks learn piecewise linear functions, but what do these regions precisely look like outside the support of the training data? Figure 1 illustrates examples of how ReLU MLPs extrapolate when trained by GD on various nonlinear functions. These examples suggest that outside the training support, the predictions quickly become linear along directions from the origin. We systematically verify this pattern by linear regression on MLPs’ predictions: the coefficient of determination ( R 2 R^{2} ) is always greater than 0.99 (Appendix C.2 ). That is, ReLU MLPs “linearize” almost immediately outside the training data range.

We formalize this observation using the implicit biases of neural networks trained by GD via the neural tangent kernel (NTK) : optimization trajectories of over-parameterized networks trained by GD are equivalent to those of kernel regression with a specific neural tangent kernel, under a set of assumptions called the “NTK regime” ( Jacot et al., 2018 ) . We provide an informal definition here; for further details, we refer the readers to Jacot et al. (2018) and Appendix A .

###### Definition 2 .

(Informal) A neural network trained in the NTK regime is infinitely wide, randomly initialized with certain scaling, and trained by GD with infinitesimal steps.

Prior works analyze optimization and in-distribution generalization of over-parameterized neural networks via NTK ( Allen-Zhu et al., 2019a ; Allen-Zhu et al., 2019b ; Arora et al., 2019a ; Arora et al., 2019b ; Cao & Gu, 2019 ; Du et al., 2019c ; Du et al., 2019a ; Li & Liang, 2018 ; Nitanda & Suzuki, 2021 ) . We instead analyze extrapolation.

Theorem 1 formalizes our observation from Figure 1 : outside the training data range, along any direction t ​ 𝒗 t{\bm{v}} from the origin, the prediction of a two-layer ReLU MLP quickly converges to a linear function with rate O ⁡ ( 1 t ) O(\frac{1}{t}) . The linear coefficients 𝜷 𝒗 \bm{\beta_{{\bm{v}}}} and the constant terms in the convergence rate depend on the training data and direction 𝒗 {\bm{v}} . The proof is in Appendix B.1 .

###### Theorem 1 .

(Linear extrapolation). Suppose we train a two-layer ReLU MLP f : ℝ d → ℝ f:\mathbb{R}^{d}\rightarrow\mathbb{R} with squared loss in the NTK regime. For any direction 𝐯 ∈ ℝ d {\bm{v}}\in\mathbb{R}^{d} , let 𝐱 0 = t ​ 𝐯 \bm{x}_{0}=t{\bm{v}} . As t → ∞ t\rightarrow\infty , f ⁡ ( 𝐱 0 + h ​ 𝐯 ) − f ⁡ ( 𝐱 0 ) → β 𝐯 ⋅ h f(\bm{x}_{0}+h{\bm{v}})-f(\bm{x}_{0})\rightarrow\beta_{{\bm{v}}}\cdot h for any h > 0 h>0 , where β 𝐯 \beta_{{\bm{v}}} is a constant linear coefficient. Moreover, given ϵ > 0 \epsilon>0 , for t = O ⁡ ( 1 ϵ ) t=O(\frac{1}{\epsilon}) , we have | f ⁡ ( 𝐱 0 + h ​ 𝐯 ) − f ⁡ ( 𝐱 0 ) h − β 𝐯 | < ϵ |\frac{f(\bm{x}_{0}+h{\bm{v}})-f(\bm{x}_{0})}{h}-\beta_{{\bm{v}}}|<\epsilon .

ReLU networks have finitely many linear regions ( Arora et al., 2018 ; Hanin & Rolnick, 2019 ) , hence their predictions eventually become linear. In contrast, Theorem 1 is a more fine-grained analysis of how MLPs extrapolate and provides a convergence rate. While Theorem 1 assumes two-layer networks in the NTK regime, experiments confirm that the linear extrapolation behavior happens across networks with different depths, widths, learning rates, and batch sizes (Appendix C.1 and C.2 ). Our proof technique potentially also extends to deeper networks.

Theorem 1 implies which target functions a ReLU MLP may be able to match outside the training data: only functions that are almost-linear along the directions away from the origin. Indeed, Figure 4(a) shows ReLU MLPs do not extrapolate target functions such as 𝒙 ⊤ ​ A ​ 𝒙 \bm{x}^{\top}A\bm{x} (quadratic), ∑ i = 1 d cos ⁡ ( 2 ​ π ⋅ 𝒙 ( i ) ) \sum_{i=1}^{d}\cos(2\pi\cdot\bm{x}^{(i)}) (cos), and ∑ i = 1 d 𝒙 ( i ) \sum_{i=1}^{d}\sqrt{\bm{x}^{(i)}} (sqrt), where 𝒙 ( i ) \bm{x}^{(i)} is the i i -th dimension of 𝒙 \bm{x} . With suitable hyperparameters, MLPs extrapolate the L1 norm correctly, which satisfies the directional linearity condition.