Neural algorithmic reasoners are parallel processors. Teaching them
sequential algorithms contradicts this nature, rendering a significant share of
their computations redundant. Parallel algorithms however may exploit their
full computational power, therefore requiring fewer layers to be executed. This
drastically reduces training times, as we observe when comparing parallel
implementations of searching, sorting and finding strongly connected components
to their sequential counterparts on the CLRS framework. Additionally, parallel
versions achieve strongly superior predictive performance in most cases.

神经算法推理器是并行处理器，教给它们顺序算法与其本质相悖，导致他们的大部分计算无效。与之相对，平行算法可以充分利用它们的计算能力，因此执行所需的层数较少。这大大减少了训练时间，比较了在 CLRS 框架上搜索、排序和查找强连通分量的平行实现与顺序实现，观察到这一点。此外，平行版本在大多数情况下实现了明显更好的预测性能。

并行算法与神经执行对齐

Parallel Algorithms Align with Neural Execution

State-of-the-art neural algorithmic reasoners make use of message passing in
graph neural networks (GNNs). But typical GNNs blur the distinction between the
definition and invocation of the message function, forcing a node to send
messages to its neighbours at every layer, synchronously. When applying GNNs to
learn to execute dynamic programming algorithms, however, on most steps only a
handful of the nodes would have meaningful updates to send. One, hence, runs
the risk of inefficiencies by sending too much irrelevant data across the graph
-- with many intermediate GNN steps having to learn identity functions. In this
work, we explicitly separate the concepts of node state update and message
function invocation. With this separation, we obtain a mathematical formulation
that allows us to reason about asynchronous computation in both algorithms and
neural networks.

本文中，我们分离了节点状态更新和消息函数调用的概念，并得到了一个数学公式，以此来推导算法和神经网络中异步计算的过程。