Recursive Algorithmic Reasoning
This addresses a key problem in deep learning for researchers and practitioners by enabling better out-of-distribution generalization, though it is incremental as it builds on prior work on algorithmic reasoning.
The authors tackled the problem of neural networks' inability to execute recursive algorithms due to memory limitations, by augmenting graph neural networks with a stack and improving algorithmic alignment, resulting in significant improvements in generalization to larger input graphs for depth-first search.
Learning models that execute algorithms can enable us to address a key problem in deep learning: generalizing to out-of-distribution data. However, neural networks are currently unable to execute recursive algorithms because they do not have arbitrarily large memory to store and recall state. To address this, we (1) propose a way to augment graph neural networks (GNNs) with a stack, and (2) develop an approach for capturing intermediate algorithm trajectories that improves algorithmic alignment with recursive algorithms over previous methods. The stack allows the network to learn to store and recall a portion of the state of the network at a particular time, analogous to the action of a call stack in a recursive algorithm. This augmentation permits the network to reason recursively. We empirically demonstrate that our proposals significantly improve generalization to larger input graphs over prior work on depth-first search (DFS).