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.

本文开发了一个框架来描述神经网络适用于哪些推理任务，并利用算法结构与相关推理过程的匹配程度推导了样本复杂度的界限，以解释一些模型在实践中的成功以及他们的局限性。