Graph Neural Networks are Dynamic Programmers
This work provides a foundational theoretical framework for enhancing GNNs in algorithmic reasoning tasks, potentially benefiting researchers in machine learning and graph-based AI.
The paper investigates the connection between graph neural networks (GNNs) and dynamic programming (DP), using category theory and abstract algebra to theoretically quantify this alignment beyond prior observations, and demonstrates empirical improvements on the CLRS benchmark.
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.