Summary
This paper explores a novel approach to NAR using GNNs. Traditional NAR models typically use a recurrent architecture where each iteration of the GNN corresponds to an iteration of the algorithm being learned. Instead, this paper proposes that since many algorithms reach an equilibrium state where further iterations do not alter the outcome, it is possible to directly solve for this equilibrium. By training neural networks to find the equilibrium point, the authors aim to improve the alignment between GNNs and classical algorithms, potentially enhancing both the accuracy and speed of NAR models. Empirical evidence from the CLRS-30 benchmark supports the viability of this equilibrium-based approach.
Weaknesses
1. The transition from denotational semantics to the proposed architecture could be further clarified to improve the overall understanding of the method. (Question 1)
2. It is not entirely clear whether the comparison with the baseline is accurate, and further justification or explanation may be needed. (Question 2)
3. The authors might consider revising the presentation of their contributions to more effectively convey the significance and novelty of the paper to the audience. (Question 3)
4. Including real-world experiments in the paper could substantially strengthen the contributions and further demonstrate the practical applicability of the proposed method. (Question 4, 5)
Questions
1. From reviewer's understanding, denotational semantics primarily motivate the equilibrium methods.
- The connection between the proposed architecture (PGN with gating) and denotational semantics is not clear.
- The motivation for equilibrium methods does not seem to require denotational semantics, as graph algorithms such as Bellman-Ford inherently have equilibrium points.
Could the authors provide further clarification on this aspect?
2. It appears that the data for the experiments was generated by the authors rather than from CLRS-30, as they mention "For each algorithm, we generate" in Line 219. However, the baseline scores are identical to those reported in previous papers. To ensure a fair comparison, the authors should consider re-running the baselines on their own dataset.
3. From the reviewer's personal perspective, the introduction and contributions sections may not be well-suited for an academic paper in their current form. The investigated problem could benefit from better motivation, and the contributions might not fully capture the paper's key theoretical and empirical results.
4. The training and test graph sizes used in the experiments seem to be relatively small, although consistent with CLRS-30. The reviewer recommends training on larger graphs (e.g., 50 nodes) and testing on even larger graphs (e.g., 300 nodes) to better demonstrate the performance gains of the proposed methods.
5. The experiments presented in the paper are limited to synthetic graph datasets. The reviewer suggests that demonstrating the performance gains on real tasks (e.g., physical systems [1] or mathematical problems [2]) would enhance the contributions of this paper.
6. The authors mention that DEQ models can be difficult to train, which might be due to the instability of DEQ's gradient. The reviewer recommends considering the use of [3] for training the models, as it provides a more stable approach.
[1] Battaglia, Peter, et al. "Interaction networks for learning about objects, relations and physics." NeurIPS 2016.
[2] Lample, Guillaume, and François Charton. "Deep learning for symbolic mathematics." ICLR 2020.
[3] Fung, Samy Wu, et al. "Jfb: Jacobian-free backpropagation for implicit networks." AAAI 2022.