International Conference on Learning Representations · 2020 · 55 citations · 31 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceMachine LearningAutomated ReasoningDeep LearningGraph-based LearningNeural NetworksQuestion AnsweringVisual Question AnsweringGraph Neural NetworksReasoning ModelsSample ComplexitySample Complexity AnalysisShortest PathsVisual Reasoning
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, while less structured networks fail. Theoretically, there is limited understanding of why and when a network structure generalizes better than other equally expressive ones. We develop a framework to characterize which reasoning tasks a network can learn well, by studying how well its structure aligns with the algorithmic structure of the relevant reasoning procedure. We formally define algorithmic alignment and derive a sample complexity bound that decreases with better alignment. This framework explains the empirical success of popular reasoning models and suggests their limitations. 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 can learn DP and thus solve these tasks. On several reasoning tasks, our theory aligns with empirical results.
31
Sepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 98.1K citations
The Graph Neural Network Model
Franco Scarselli, M. Gori, Ah Chung Tsoi et al. · IEEE Transactions on Neural Networks · 2008 · 9.3K citations · Full text
VQA: Visual Question Answering
Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu et al. · 2015 · 4.3K citations
Leslie G. Valiant · 1984 · 4.2K citations