Recurrent Aggregators in Neural Algorithmic Reasoning
This work addresses a problem in neural algorithmic reasoning for researchers and practitioners by offering a novel approach that improves performance on specific algorithmic tasks, though it is incremental in modifying existing methods.
The paper tackled the challenge of designing neural networks that mimic classical algorithms by replacing the equivariant aggregation function in graph neural networks with a recurrent neural network, achieving a state-of-the-art mean micro-F1 score of 87% on the Quickselect task.
Neural algorithmic reasoning (NAR) is an emerging field that seeks to design neural networks that mimic classical algorithmic computations. Today, graph neural networks (GNNs) are widely used in neural algorithmic reasoners due to their message passing framework and permutation equivariance. In this extended abstract, we challenge this design choice, and replace the equivariant aggregation function with a recurrent neural network. While seemingly counter-intuitive, this approach has appropriate grounding when nodes have a natural ordering -- and this is the case frequently in established reasoning benchmarks like CLRS-30. Indeed, our recurrent NAR (RNAR) model performs very strongly on such tasks, while handling many others gracefully. A notable achievement of RNAR is its decisive state-of-the-art result on the Heapsort and Quickselect tasks, both deemed as a significant challenge for contemporary neural algorithmic reasoners -- especially the latter, where RNAR achieves a mean micro-F1 score of 87%.