mlsanityData to 14 Oct 2026

What Can Neural Networks Reason About?

arXiv 1905.13211 ↗First posted 30 May 2019cs.LG cs.AI cs.CVcited by 159

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 159 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 30; 2022: 32; 2023: 31; 2024: 32; 2025: 18; 2026: 16.

159 papers.

Sort:

By area:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  2. 2021QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answeringcited by 388
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  4. 2021Identity-aware Graph Neural Networkscited by 198
  5. 2025When More is Less: Understanding Chain-of-Thought Length in LLMscited by 183
  6. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  7. 2022Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphscited by 144
  8. 2023EvoPrompting: Language Models for Code-Level Neural Architecture Searchcited by 131
  9. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  10. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 112
  11. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 106
  12. 2022On the Paradox of Learning to Reason from Datacited by 93
38 more
  1. 2024Position: Graph Foundation Models are Already Herecited by 86
  2. 2022Sparse Mixture-of-Experts are Domain Generalizable Learnerscited by 85
  3. 2021Object-Region Video Transformerscited by 73
  4. 2021Directed Acyclic Graph Neural Networkscited by 70
  5. 2021Cross-Node Federated Graph Neural Network for Spatio-Temporal Data Modelingcited by 69
  6. 2022When Physics Meets Machine Learning: A Survey of Physics-Informed Machine Learningcited by 65
  7. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  8. 2022A Generalist Neural Algorithmic Learnercited by 59
  9. 2024Graph Neural Networks for Learning Equivariant Representations of Neural Networkscited by 59
  10. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  11. 2022Provably expressive temporal graph networkscited by 56
  12. 2023Relational Deep Learning: Graph Representation Learning on Relational Databasescited by 56
  13. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  14. 2022Graph Neural Networks are Dynamic Programmerscited by 55
  15. 2021LIME: Learning Inductive Bias for Primitives of Mathematical Reasoningcited by 46
  16. 2022Graph Neural Networks for Wireless Communications: From Theory to Practicecited by 46
  17. 2024Softmax is not Enough (for Sharp Size Generalisation)cited by 46
  18. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 43
  19. 2022Relational Attention: Generalizing Transformers for Graph-Structured Taskscited by 41
  20. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  21. 2021Sampling methods for efficient training of graph convolutional networks: A surveycited by 40
  22. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 40
  23. 2021VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantizationcited by 39
  24. 2023Incorporating Structured Representations into Pretrained Vision & Language Models Using Scene Graphscited by 39
  25. 2024Learning Iterative Reasoning through Energy Diffusioncited by 36
  26. 2024Position: Categorical Deep Learning is an Algebraic Theory of All Architecturescited by 32
  27. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 31
  28. 2024Simulation of Graph Algorithms with Looped Transformerscited by 30
  29. 2023Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalizationcited by 29
  30. 2024The CLRS-Text Algorithmic Reasoning Language Benchmarkcited by 28
  31. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  32. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  33. 2021How to transfer algorithmic reasoning knowledge to learn new algorithms?cited by 22
  34. 2023Dual Algorithmic Reasoningcited by 21
  35. 2022PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphscited by 20
  36. 2023Neural Algorithmic Reasoning for Combinatorial Optimisationcited by 19
  37. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 18
  38. 2021Ego-GNNs: Exploiting Ego Structures in Graph Neural Networkscited by 17

50 most cited of 159 All 159 (JSON)