Neural Algorithmic Reasoning with Causal Regularisation

Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, Petar Veličković
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2272-2288, 2023.

Abstract

Recent work on neural algorithmic reasoning has investigated the reasoning capabilities of neural networks, effectively demonstrating they can learn to execute classical algorithms on unseen data coming from the train distribution. However, the performance of existing neural reasoners significantly degrades on out-of-distribution (OOD) test data, where inputs have larger sizes. In this work, we make an important observation: there are many different inputs for which an algorithm will perform certain intermediate computations identically. This insight allows us to develop data augmentation procedures that, given an algorithm’s intermediate trajectory, produce inputs for which the target algorithm would have exactly the same next trajectory step. We ensure invariance in the next-step prediction across such inputs, by employing a self-supervised objective derived by our observation, formalised in a causal graph. We prove that the resulting method, which we call Hint-ReLIC, improves the OOD generalisation capabilities of the reasoner. We evaluate our method on the CLRS algorithmic reasoning benchmark, where we show up to 3x improvements on the OOD test data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-bevilacqua23a, title = {Neural Algorithmic Reasoning with Causal Regularisation}, author = {Bevilacqua, Beatrice and Nikiforou, Kyriacos and Ibarz, Borja and Bica, Ioana and Paganini, Michela and Blundell, Charles and Mitrovic, Jovana and Veli\v{c}kovi\'{c}, Petar}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {2272--2288}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/bevilacqua23a/bevilacqua23a.pdf}, url = {https://proceedings.mlr.press/v202/bevilacqua23a.html}, abstract = {Recent work on neural algorithmic reasoning has investigated the reasoning capabilities of neural networks, effectively demonstrating they can learn to execute classical algorithms on unseen data coming from the train distribution. However, the performance of existing neural reasoners significantly degrades on out-of-distribution (OOD) test data, where inputs have larger sizes. In this work, we make an important observation: there are many different inputs for which an algorithm will perform certain intermediate computations identically. This insight allows us to develop data augmentation procedures that, given an algorithm’s intermediate trajectory, produce inputs for which the target algorithm would have exactly the same next trajectory step. We ensure invariance in the next-step prediction across such inputs, by employing a self-supervised objective derived by our observation, formalised in a causal graph. We prove that the resulting method, which we call Hint-ReLIC, improves the OOD generalisation capabilities of the reasoner. We evaluate our method on the CLRS algorithmic reasoning benchmark, where we show up to 3x improvements on the OOD test data.} }
Endnote
%0 Conference Paper %T Neural Algorithmic Reasoning with Causal Regularisation %A Beatrice Bevilacqua %A Kyriacos Nikiforou %A Borja Ibarz %A Ioana Bica %A Michela Paganini %A Charles Blundell %A Jovana Mitrovic %A Petar Veličković %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-bevilacqua23a %I PMLR %P 2272--2288 %U https://proceedings.mlr.press/v202/bevilacqua23a.html %V 202 %X Recent work on neural algorithmic reasoning has investigated the reasoning capabilities of neural networks, effectively demonstrating they can learn to execute classical algorithms on unseen data coming from the train distribution. However, the performance of existing neural reasoners significantly degrades on out-of-distribution (OOD) test data, where inputs have larger sizes. In this work, we make an important observation: there are many different inputs for which an algorithm will perform certain intermediate computations identically. This insight allows us to develop data augmentation procedures that, given an algorithm’s intermediate trajectory, produce inputs for which the target algorithm would have exactly the same next trajectory step. We ensure invariance in the next-step prediction across such inputs, by employing a self-supervised objective derived by our observation, formalised in a causal graph. We prove that the resulting method, which we call Hint-ReLIC, improves the OOD generalisation capabilities of the reasoner. We evaluate our method on the CLRS algorithmic reasoning benchmark, where we show up to 3x improvements on the OOD test data.
APA
Bevilacqua, B., Nikiforou, K., Ibarz, B., Bica, I., Paganini, M., Blundell, C., Mitrovic, J. & Veličković, P.. (2023). Neural Algorithmic Reasoning with Causal Regularisation. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:2272-2288 Available from https://proceedings.mlr.press/v202/bevilacqua23a.html.

Related Material