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. Recently, there have been many advances in building neural networks that can learn to reason. Reasoning spans a variety of tasks, for instance, visual and text-based question answering (Johnson et al., 2017a; Weston et al., 2015; Hu et al., 2017; Fleuret et al., 2011; Antol et al., 2015) , intuitive physics, i.e., predicting the time evolution of physical objects (Battaglia et al., 2016; Watters et al., 2017; Fragkiadaki et al., 2016; Chang et al., 2017) , mathematical reasoning (Saxton et al., 2019; Chang et al., 2019) and visual IQ tests Zhang et al., 2019) . Curiously, neural networks that perform well in reasoning tasks usually possess specific structures (Santoro et al., 2017) . Many successful models follow the Graph Neural Network (GNN) framework Palm et al., 2018; Mrowca et al., 2018; Janner et al., 2019) . These networks explicitly model pairwise relations and recursively update each object's representation by aggregating its relations with other objects. Other computational structures, e.g., neural symbolic programs (Yi et al., 2018; Mao et al., 2019; Johnson et al., 2017b) and Deep Sets (Zaheer et al., 2017) , are effective on specific tasks. However, there is limited understanding of the relation between the generalization ability and network structure for reasoning. What tasks can a neural network (sample efficiently) learn to reason about? Answering this question is crucial for understanding the empirical success and limitations of existing models, and for designing better models for new reasoning tasks. This paper is an initial work towards answering this fundamental question. We develop a theoretical framework to characterize what tasks a neural network can reason about. We build on a simple observation that reasoning procedures resemble algorithms. Hence, we study how well a reasoning algorithm aligns with the computation graph of the network. Intuitively, if they align well, the network only needs to learn simple algorithm steps to simulate the reasoning procedure, which leads to better sample efficiency. We formalize this intuition with a numeric measure of algorithmic alignment, This paper is an initial step towards formally understanding how neural networks can learn to reason. We introduce an algorithmic alignment perspective that may inspire neural network design and opens up theoretical avenues. An interesting future direction is to design, e.g. via algorithmic alignment, neural networks that can learn other general algorithmic paradigms, and to explore the neural architecture search space of algorithmic structures. Zaheer et al. (2017) prove the universal approximation of Deep Sets under the restriction that the set size is fixed and the hidden dimension is equal to the set size plus one. Wagstaff et al. (2019) extend the universal approximation result for Deep Sets by showing that the set size does not have to be fixed and the hidden dimension is only required to be at least as large as the set size. The results for our purposes can be summarized as follows.
We develop a theoretical framework to characterize which reasoning tasks a neural network can learn well. The paper proposes a measure of classes of algorithmic alignment that measure how "close" neural networks are to known algorithms, proving the link between several classes of known algorithms and neural network architectures.