What Can Neural Networks Reason About?
  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.
