WHAT CAN NEURAL NETWORKS REASON ABOUT?

Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken Ichi Kawarabayashi, Stefanie Jegelka

Research output: Contribution to conferencePaperpeer-review

91 Scopus citations

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.

Original languageEnglish
StatePublished - 2020
Externally publishedYes
Event8th International Conference on Learning Representations, ICLR 2020 - Addis Ababa, Ethiopia
Duration: 30 Apr 2020 → …

Conference

Conference8th International Conference on Learning Representations, ICLR 2020
Country/TerritoryEthiopia
CityAddis Ababa
Period30/04/20 → …

Fingerprint

Dive into the research topics of 'WHAT CAN NEURAL NETWORKS REASON ABOUT?'. Together they form a unique fingerprint.

Cite this