What Can Neural Networks Reason About?

Abstract

Neural networks have succeeded in many reasoning tasks. Empirically, these tasks require specialized network structures, e.g., Graph Neural Networks (GNNs) perform well on many such tasks, but less structured networks fail. Theoretically, there is limited understanding of why and when a network structure generalizes better than others, although they have equal expressive power. In this paper, we develop a framework to characterize which reasoning tasks a network can learn well, by studying how well its computation structure aligns with the algorithmic structure of the relevant reasoning process. We formally define this algorithmic alignment and derive a sample complexity bound that decreases with better alignment. This framework offers an explanation for the empirical success of popular reasoning models, and suggests their limitations. As an example, we unify seemingly different reasoning tasks, such as intuitive physics, visual question answering, and shortest paths, via the lens of a powerful algorithmic paradigm, dynamic programming (DP). We show that GNNs align with DP and thus are expected to solve these tasks. On several reasoning tasks, our theory is supported by empirical results.

References in corpus (12)

• Neural Message Passing for Quantum Chemistry
• Representation Learning on Graphs with Jumping Knowledge Networks
• Interaction Networks for Learning about Objects, Relations and Physics
• Learning Particle Dynamics for Manipulating Rigid Bodies, Deformable Objects, and Fluids
• A Compositional Object-Based Approach to Learning Physical Dynamics
• Flexible Neural Representation for Physics Prediction
• Measuring abstract reasoning in neural networks
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Norm-Based Capacity Control in Neural Networks
• On the Turing Completeness of Modern Neural Network Architectures
• Automatically Composing Representation Transformations as a Means for Generalization
• On the Limitations of Representing Functions on Sets

Cited by in corpus (31)

• Discovering Symbolic Models from Deep Learning with Inductive Biases
• Graph Neural Networks: Taxonomy, Advances and Trends
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Algorithmically-Consistent Deep Learning Frameworks for Structural Topology Optimization
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Directed Acyclic Graph Neural Networks
• Building powerful and equivariant graph neural networks with structural message-passing
• On Provable Benefits of Depth in Training Graph Convolutional Networks
• Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization
• Normalized Attention Without Probability Cage
• LIME: Learning Inductive Bias for Primitives of Mathematical Reasoning
• Information Obfuscation of Graph Neural Networks
• Neural Bipartite Matching
• Graph Neural Reasoning May Fail in Certifying Boolean Unsatisfiability
• Supervising the Transfer of Reasoning Patterns in VQA
• DeepPeep: Exploiting Design Ramifications to Decipher the Architecture of Compact DNNs
• Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks
• Discovering Dynamic Salient Regions for Spatio-Temporal Graph Neural Networks
• Cross-Node Federated Graph Neural Network for Spatio-Temporal Data Modeling
• Neural Trees for Learning on Graphs
• Can Graph Neural Networks Learn to Solve MaxSAT Problem?
• Decentralized Statistical Inference with Unrolled Graph Neural Networks
• Neural Subgraph Isomorphism Counting
• Plant 'n' Seek: Can You Find the Winning Ticket?
• Towards Sample Efficient Agents through Algorithmic Alignment
• Neural PathSim for Inductive Similarity Search in Heterogeneous Information Networks
• Unsupervised Abstract Reasoning for Raven's Problem Matrices