Latent Space Representations of Neural Algorithmic Reasoners

Vladimir V Mirjanic, Razvan Pascanu, Petar Veličković
Proceedings of the Second Learning on Graphs Conference, PMLR 231:10:1-10:24, 2024.

Abstract

Neural Algorithmic Reasoning (NAR) is a research area focused on designing neural architectures that can reliably capture classical computation, usually by learning to execute algorithms. A typical approach is to rely on Graph Neural Network (GNN) architectures, which encode inputs in high-dimensional latent spaces that are repeatedly transformed during the execution of the algorithm. In this work we perform a detailed analysis of the structure of the latent space induced by the GNN when executing algorithms. We identify two possible failure modes: (i) loss of resolution, making it hard to distinguish similar values; (ii) inability to deal with values outside the range observed during training. We propose to solve the first issue by relying on a softmax aggregator, and propose to decay the latent space in order to deal with out-of-range values. We show that these changes lead to improvements on the majority of algorithms in the standard CLRS-30 benchmark when using the state-of-the-art Triplet-GMPNN processor.

Cite this Paper

BibTeX
@InProceedings{pmlr-v231-mirjanic24a, title = {Latent Space Representations of Neural Algorithmic Reasoners}, author = {Mirjanic, Vladimir V and Pascanu, Razvan and Veli{\v c}kovi{\' c}, Petar}, booktitle = {Proceedings of the Second Learning on Graphs Conference}, pages = {10:1--10:24}, 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/mirjanic24a/mirjanic24a.pdf}, url = {https://proceedings.mlr.press/v231/mirjanic24a.html}, abstract = {Neural Algorithmic Reasoning (NAR) is a research area focused on designing neural architectures that can reliably capture classical computation, usually by learning to execute algorithms. A typical approach is to rely on Graph Neural Network (GNN) architectures, which encode inputs in high-dimensional latent spaces that are repeatedly transformed during the execution of the algorithm. In this work we perform a detailed analysis of the structure of the latent space induced by the GNN when executing algorithms. We identify two possible failure modes: (i) loss of resolution, making it hard to distinguish similar values; (ii) inability to deal with values outside the range observed during training. We propose to solve the first issue by relying on a softmax aggregator, and propose to decay the latent space in order to deal with out-of-range values. We show that these changes lead to improvements on the majority of algorithms in the standard CLRS-30 benchmark when using the state-of-the-art Triplet-GMPNN processor.} }
Endnote
%0 Conference Paper %T Latent Space Representations of Neural Algorithmic Reasoners %A Vladimir V Mirjanic %A Razvan Pascanu %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-mirjanic24a %I PMLR %P 10:1--10:24 %U https://proceedings.mlr.press/v231/mirjanic24a.html %V 231 %X Neural Algorithmic Reasoning (NAR) is a research area focused on designing neural architectures that can reliably capture classical computation, usually by learning to execute algorithms. A typical approach is to rely on Graph Neural Network (GNN) architectures, which encode inputs in high-dimensional latent spaces that are repeatedly transformed during the execution of the algorithm. In this work we perform a detailed analysis of the structure of the latent space induced by the GNN when executing algorithms. We identify two possible failure modes: (i) loss of resolution, making it hard to distinguish similar values; (ii) inability to deal with values outside the range observed during training. We propose to solve the first issue by relying on a softmax aggregator, and propose to decay the latent space in order to deal with out-of-range values. We show that these changes lead to improvements on the majority of algorithms in the standard CLRS-30 benchmark when using the state-of-the-art Triplet-GMPNN processor.
APA
Mirjanic, V.V., Pascanu, R. & Veličković, P.. (2024). Latent Space Representations of Neural Algorithmic Reasoners. Proceedings of the Second Learning on Graphs Conference, in Proceedings of Machine Learning Research 231:10:1-10:24 Available from https://proceedings.mlr.press/v231/mirjanic24a.html.

Related Material