Latent Space Representations of Neural Algorithmic Reasoners
This work addresses reliability issues in neural networks that execute classical algorithms, which is incremental for improving robustness in algorithmic reasoning tasks.
The paper tackled the problem of latent space failures in neural algorithmic reasoners, specifically loss of resolution and inability to handle out-of-range values, and showed that proposed modifications like a softmax aggregator and decay mechanism improved performance on most algorithms in the CLRS-30 benchmark.
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. Our code is available at https://github.com/mirjanic/nar-latent-spaces