Graph Neural Networks are Dynamic Programmers
  Recent advances in neural algorithmic reasoning with graph neural networks
(GNNs) are propped up by the notion of algorithmic alignment. Broadly, a neural
network will be better at learning to execute a reasoning task (in terms of
sample complexity) if its individual components align well with the target
algorithm. Specifically, GNNs are claimed to align with dynamic programming
(DP), a general problem-solving strategy which expresses many polynomial-time
algorithms. However, has this alignment truly been demonstrated and
theoretically quantified? Here we show, using methods from category theory and
abstract algebra, that there exists an intricate connection between GNNs and
DP, going well beyond the initial observations over individual algorithms such
as Bellman-Ford. Exposing this connection, we easily verify several prior
findings in the literature, produce better-grounded GNN architectures for
edge-centric tasks, and demonstrate empirical results on the CLRS algorithmic
reasoning benchmark. We hope our exposition will serve as a foundation for
building stronger algorithmically aligned GNNs.
