Recursive Algorithmic Reasoning

Jonas Jürß, Dulhan Hansaja Jayalath, Petar Veličković
Proceedings of the Second Learning on Graphs Conference, PMLR 231:5:1-5:14, 2024.

Abstract

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 sampling intermediate algorithm trajectories that improves 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).

Cite this Paper

BibTeX
@InProceedings{pmlr-v231-jurss24a, title = {Recursive Algorithmic Reasoning}, author = {J{\"u}r{\ss}, Jonas and Jayalath, Dulhan Hansaja and Veli{\v c}kovi{\' c}, Petar}, booktitle = {Proceedings of the Second Learning on Graphs Conference}, pages = {5:1--5:14}, year = {2024}, editor = {Villar, Soledad and Chamberlain, Benjamin}, volume = {231}, series = {Proceedings of Machine Learning Research}, month = {27--30 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v231/jurss24a/jurss24a.pdf}, url = {https://proceedings.mlr.press/v231/jurss24a.html}, abstract = {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 sampling intermediate algorithm trajectories that improves 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).} }
Endnote
%0 Conference Paper %T Recursive Algorithmic Reasoning %A Jonas Jürß %A Dulhan Hansaja Jayalath %A Petar Veličković %B Proceedings of the Second Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2024 %E Soledad Villar %E Benjamin Chamberlain %F pmlr-v231-jurss24a %I PMLR %P 5:1--5:14 %U https://proceedings.mlr.press/v231/jurss24a.html %V 231 %X 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 sampling intermediate algorithm trajectories that improves 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).
APA
Jürß, J., Jayalath, D.H. & Veličković, P.. (2024). Recursive Algorithmic Reasoning. Proceedings of the Second Learning on Graphs Conference, in Proceedings of Machine Learning Research 231:5:1-5:14 Available from https://proceedings.mlr.press/v231/jurss24a.html.

Related Material