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.

References in corpus (28)

• Distributed Representations of Words and Phrases and their Compositionality
• Neural Message Passing for Quantum Chemistry
• Exploiting Similarities among Languages for Machine Translation
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Interaction Networks for Learning about Objects, Relations and Physics
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Domain Adaptation: Learning Bounds and Algorithms
• On Exact Computation with an Infinitely Wide Neural Net
• Invariant Risk Minimization
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• On Lazy Training in Differentiable Programming
• Strategies for Pre-training Graph Neural Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Invariant Models for Causal Transfer Learning
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Measuring abstract reasoning in neural networks
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• What Can Neural Networks Reason About?
• The Risks of Invariant Risk Minimization
• Neural Arithmetic Logic Units
• Complexity of Linear Regions in Deep Networks
• Domain Generalization with MixStyle
• Gradient Descent Quantizes ReLU Network Features
• Neural Arithmetic Units
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Learning Representations that Support Extrapolation

Cited by in corpus (19)

• Reliable extrapolation of deep neural operators informed by physics or sparse observations
• Differentiable sampling of molecular geometries with uncertainty-based adversarial attacks
• Deep Learning Collective Variables from Transition Path Ensemble
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning
• Machine learning applications for weather and climate need greater focus on extremes
• Physics-Guided Neural Networks for Feedforward Control: An Orthogonal Projection-Based Approach
• An extrapolation-driven network architecture for physics-informed deep learning
• Deep Extrapolation for Attribute-Enhanced Generation
• From Local Structures to Size Generalization in Graph Neural Networks
• Enhanced sampling of robust molecular datasets with uncertainty-based collective variables
• Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
• On the equivalence of molecular graph convolution and molecular wave function with poor basis set
• Neural Status Registers
• A Priori Uncertainty Quantification of Reacting Turbulence Closure Models using Bayesian Neural Networks
• Persistent Message Passing
• Implicit Behavioral Cloning
• A Feature-based Generalizable Prediction Model for Both Perceptual and Abstract Reasoning
• SLIDE: A machine-learning based method for forced dynamic response estimation of multibody systems