- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper studies neural algorithmic reasoning, which aims to train a graph neural network to simulate the execution of a classical algorithm step by step. The well-known benchmark in this area is CLRS-30, which contains 30 classical algorithms, including sorting algorithms and graph algorithms. For each algorithm in the benchmark, CLRS-30 provides intermediate states produced at each iteration of the algorithm (e.g., the current state of the array), called hints, and expects the trained neural network to predict the corresponding hint at each step. The authors observe that the operations between some hints do not match well with those of standard GNNs or graph transformers, but instead match the TMU operation mentioned in the literature; therefore, they propose replacing the node update function in the GNN with TMU. In the paper, the authors propose a mixture-of-experts neural network, where each expert corresponds to a way of updating GNN nodes (including TMU), and at the beginning of each inference step, a router network decides which expert to use for the GNN update at that step. The paper validates the effectiveness of the proposed method through experiments.
Critical strengths
The paper is overall clean and easy to follow. Although some similar ideas have already appeared in Triplet-GMPNN, using the TMU operation to update the GNN in NAR can be regarded as a novel point, and it may provide a GNN operator option for the future development of NAR.
Critical weaknesses
The main concern is the experimental section. The paper does not compare the results of the proposed network architecture with methods from the literature; instead, it compares several methods designed by the authors against one another within their own framework. The main comparison tables in the experimental section do not follow the setting used in prior literature, where at test time each step takes as input the hint predicted by the GNN at the previous step. The authors use ground-truth hints as input. The authors provide results without teacher forcing in the appendix, but the reported performance is far below that of some methods in the literature. Additionally, the paper only tests a few graph algorithm tasks in CLRS, but the proposed framework can also be applied to other types of algorithms in CLRS. These weaknesses make the experiments not that convincing.
Questions for authors
Could you compare the proposed method with existing methods under the same test setting (either both using teacher forcing at test time or both not using teacher forcing)? Such a comparison would help convince that the proposed method indeed has advantages.
3 comments
Response to Reviewer Xb68 (2)
Neither uses teacher forcing
The own-prediction retrainings do not establish a general advantage over the tested literature processors.
Submitted models evaluated on their own predictions. Every processor of the submitted paper falls below 0.19 on Dijkstra and Floyd–Warshall and below 0.29 on Bellman–Ford at N ≥ 32 (Appendix N). The two ported processors are above PSAR on Dijkstra and Bellman–Ford (MPNN-max 0.213 and 0.389, the triplet port 0.295 and 0.467, PSAR 0.068 and 0.280 at N=32); on Floyd–Warshall PSAR is above both (0.187 against 0.108 and 0.081). As the reviewer notes, these are far below published results obtained without teacher forcing. These models never saw their own predictions in training, and the main harness differs from the reference CLRS implementation in two disclosed ways (Appendix N): edge-level quantities are decoded without a per-edge term, and padded steps are not masked. The retrainings below use reference-form decoders, mask lengths where trajectories vary (three smaller differences remain and are listed in Appendix S), and train, select and evaluate every model on its own predictions.
Floyd–Warshall retrained (Appendix Q). Accuracy at N=32 / 64 is 0.472 / 0.197 for PSAR, 0.430 / 0.228 for MPNN-max, 0.406 / 0.168 for Triplet-GMPNN and 0.561 / 0.213 for a wider TMU. PSAR is not separable from MPNN-max or Triplet-GMPNN and is below the wider TMU at N=32 and 48 (−9.0 [−16.0, −4.2] and −9.3 [−18.8, −3.8] pp) and a parameter-matched TMU (−8.0 [−14.0, −4.0] and −4.3 [−7.5, −0.8]).
Dijkstra and Bellman–Ford retrained (Appendix S). Accuracy at N=32 / 64:
| Task | PSAR | MPNN-max | Triplet-GMPNN | Wider TMU |
|---|---|---|---|---|
| Dijkstra | 0.795 / 0.584 | 0.944 / 0.901 | 0.947 / 0.865 | 0.829 / 0.594 |
| Bellman–Ford | 0.885 / 0.768 | 0.929 / 0.875 | 0.944 / 0.907 | 0.873 / 0.624 |
Both message-passing processors are above PSAR at every size: on Dijkstra by 14.8 [10.9, 18.4] and 31.7 [26.3, 36.6] pp (MPNN-max, N=32 and 64), on Bellman–Ford by 5.9 [4.5, 7.4] and 14.0 [11.7, 16.1] pp (Triplet-GMPNN). PSAR is above the wider TMU on Bellman–Ford at N=48 and 64 (+7.4 [+5.0, +9.7] and +14.4 [+11.0, +17.9]). On neither task is PSAR above all four of its own experts, with or without teacher forcing (computed after the other contrasts).
What the paper claims
The paper compares processors and routing controls under explicitly specified configurations. Standalone TMU accounts numerically for most of the gain over single-step attention on Floyd–Warshall under teacher forcing. The routed pool exceeds a parameter-matched TMU on Floyd–Warshall in the main teacher-forced harness (+7.2 and +8.1 pp at N=48 and 64), and this ordering reverses when both are trained and evaluated on their own predictions (−5.8 and −3.4 pp; §8, Table 4). §9 states that we do not contest the benchmark-wide state of the art on CLRS-30.
The new comparisons bound these claims, as stated in §6, Limitations and Appendices P, Q and S: max-aggregation message passing is either higher than PSAR or not statistically distinguishable from it on Dijkstra and Floyd–Warshall in the main teacher-forced harness, at a fraction of its cost; and the Floyd–Warshall margin over a single pair-state expert is not reproduced with upstream-form edge decoders. PSAR's favourable same-setting comparisons are against Relational Attention on Dijkstra, the triplet processor on Floyd–Warshall under both read-outs, and the unwidened MPNN-max on Bellman–Ford at N=32 under teacher forcing (23.4 pp in the main harness; 1.9 pp in Appendix S). §2 no longer says that Triplet-GMPNN was not run in our harness; the Edge Transformer and FloydNet remain untested.
Scope of tasks
The three tasks share shortest-path semantics but differ in update structure: greedy vertex selection, repeated edge relaxation and pivot-indexed pair updates. Appendix J.1 (Table 23) extends PSAR and the four single experts to seven CLRS-30 tasks under teacher forcing on the checkpoint-selection split, four outside shortest paths. PSAR's largest shortfall to the per-task best single expert is 6.6 pp, against 17.7 to 35.2 pp for any one expert used on all seven; it exceeds every single expert only on Floyd–Warshall and BFS. Appendix R adds their self-rollout (SCC retains ground-truth color). These tests do not establish a routing benefit. The literature processors and routing controls were run on the three shortest-path tasks only.
These additions provide the established-method comparisons requested in your review under both hint contracts. We would appreciate your reassessment of the concern arising from their original absence, and of the empirical support for the contribution within its stated scope.
Thanks for the additional experiments and clarifications. The new comparisons address my concern about the lack of evaluation against established methods under matched settings. However, I still remain concerned about the added value of routing and performance without teacher forcing, so I will maintain my original rating.
Response to Reviewer Xb68 (1)
Thank you for identifying the missing comparisons with established processors under a common setting. We have added MPNN-max and Triplet-GMPNN-based comparisons under both hint contracts, followed by retraining with reference-form decoders and length masking where applicable.
Response in brief. Within each comparison, the evaluation instances and hint contract are shared, and model-specific training schedules are disclosed. This directly addresses the missing-comparison concern. The results support a scoped conclusion: standalone TMU accounts numerically for most of the original Floyd–Warshall gain over attention, while the additional routing advantage depends on the configuration and comparator. This boundary now appears in the contribution statement. Table numbers refer to the revised PDF; changes are marked in blue.
Both use teacher forcing
Three literature processors replace our processor in the same harness: Relational Attention (Diao & Loynd; Table 35, already in the submission), the CLRS max-aggregation MPNN and Triplet-GMPNN (both new, not tuned; Appendix P). The comparisons share data, evaluation instances, hint contract and decoder design within each harness. PSAR retains its staged training; the baselines use the disclosed single-expert recipe. Four seeds each, on the held-out instances of Table 1. PSAR minus each processor, in pp (95% paired-bootstrap intervals for the two new processors, not corrected for multiplicity; N=32 / 48 / 64, or N=32 / 64 for Relational Attention):
Reference-form decoders. The main harness differs from the reference CLRS implementation in its read-outs and in not masking padded steps (Appendix N), and our triplet port pools the edge representation into the nodes, so it is not a faithful Triplet-GMPNN. We therefore retrained all models with decoders in the reference form (four seeds, 64 new instances per size).
Floyd–Warshall (Appendix Q). PSAR minus each model at N=48 / 64, trained and evaluated with ground-truth hints, with checkpoints selected on autonomous or teacher-forced accuracy:
PSAR stays above Triplet-GMPNN and is not separable from MPNN-max under either rule. Against a single wider TMU it is below at N=32 under both rules (−25.8 [−47.3, −8.1] and −9.4 [−13.8, −4.1]) and at N=48 under teacher-forced selection, the rule of the submission. Against a parameter-matched TMU it is below at N=32 under both rules (−28.1 [−47.9, −9.6], −9.8 [−13.4, −5.2]); at N=48 and 64 the intervals include zero.
Dijkstra and Bellman–Ford (Appendix S, with length masking). Every model is above 0.89 at every size. PSAR is not separable from MPNN-max, Triplet-GMPNN or a wider TMU at N=48 and 64 on either task; at N=32 it is above MPNN-max on Bellman–Ford (+1.9 [+1.1, +2.8] pp) and below the wider TMU on Dijkstra (−0.3 [−0.6, −0.1]). On Dijkstra every trained model is below the baseline that copies the last fed hint (1.000 at N ≥ 32).