Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors connect GNN and DP by using integral transforms as a common form to represent the operations used in GNN and DP. The common form allows studying GNN and GP in unified framework and authors use the connection to design GNN architecture that better align with the underlying DP algorithm to achieve better empirical performance on benchmark.
strengths_and_weaknesses: **originality:** On the question being asked, this work is similar to Xu et al. 2019 ICLR but this work is original in that this study connect GNN and DP in a more formal way.

**quality & clarity:** Introduction and background sections are clearly written and motivate this study well. And that dynamic programming (e.g., Bellman-Ford) and GNN be represented in the same framework is well demonstrated. I do not have the expertise on examining all the methods details in section 4 so i defer this to other reviewers. I find the quality of empirical results (section 7) can be improved (see below). 

**significance:** this study is important on progress to connect classical DP and GNN and may be used to better understand and propose new type of GNN. However, presentation on methods and empirical results can be improved to strengthen the impact of this paper to broader audience.
questions: 1. I find it difficult to fully grasp details for polynomial span diagram of GNNs. One way this paper can be strengthened is to provide more details on how Diagram (7) and (10) are implemented in practices and what does these abstract operations correspond to in GNN operations (perhaps a side-by-side figure with left being the integral transform diagram, and right being the things like pseudocode)
2. The experiments part can be improved by adding negative examples where V^3 network does not improve over V^2 network for those non-edge-centric CLRS benchmarks, or as authors stated in Line 46-47, by showcasing examples that certain classes of GNN fit certain classes of DP, rather than showing V^3 outperforms V^2 throughout.
3. Can authors explain more on the consistently low performance even for Dijkstra problem (~70%) even though it seems the GNN architecture well matches the DP problem structure here (also for results of other benchmarks with performance as low as ~10%). Can authors provide insights on in what directions performance can be boosted, e.g., for Find Maximum Subarray (currently with only ~10% performance)? The baseline I am mainly referring to are the empirical results in Xu et al. 2019 ICLR. It is hard to persuaded by the title “Graph Neural Networks are Dynamic Programmers” with the these underwhelming experiment performance. Is it because of the limited training data? Perhaps authors can consider downplaying their paper title.
4. Information about experiments setup (including data sample size, hyperparameter tuning steps, etc. that can be replicate the experiments) should be added in line (rather than being put into checklist)
limitations: See above in "Questions" section
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes an approach to interpret the operations of both DP and GNNs from the perspective of category theory and abstract algebra. They derive the GNN-DP connection by a diagrammatic abstraction in the computations and recast the algorithmic alignment to align the diagrams of GNNs to some specific algorithm classes. Some experiments on six edge-centric tasks from CLRS Algorithmic Reasoning Benchmark demonstrate the effectiveness of the proposed derive.
strengths_and_weaknesses: Strengths:
- This paper theoretically proposes the integral transform to connect GNNs and DP. Furthermore, they provide sufficient theoretical proof to prove the correctness. The theoretical part seems solid to me. 
- This paper is good at writing, the target problem is demonstrated clear and the proposed solution is well-discussed. 

Weakness:
- The evaluation part is not sufficient and in this paper, only six algorithms are evaluated with different dimension lengths from in-domain and out-of-domain datasets.

questions: - One major question is that in the evaluation part why use a two-layer MLP with different dimensional sizes, It seems GNNs are discussed in this paper, however, using MLP for evaluation is unclear to me. I am not very familiar with this topic, so please clarify it.
- Furthermore, why choose in-domain and out-of-domain for evaluation, and what is the rationality behind it.
limitations: The evaluation part is not sufficient.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors describe the connection between GNNs and dynamic programming via the category theory, specifically, the integral transform. It shows that both GNNs and DPs can be described as a polynomial span diagram and people can improve GNNs' edge updates from the perspective of the polynomial span diagram. 

With the analysis from the polynomial span, the authors show that we can use order-3 edge updates to improve the performance of GNNs for edge-centric problems in the CLRS Algorithmic Reasoning Benchmark. 

strengths_and_weaknesses: Strengths:

This is an interesting and intriguing paper for connecting GNNs with DP as well as elevating the understanding of GNNs. The paper builds the connection between GNNs and DP via the polynomial span diagram from category theory. It also demonstrates a bit the empirical usage of this analysis via the improved edge updates, tested on the CLRS Algorithmic Reasoning Benchmark.

Weakness:

I admit that I'm not an expert in category theory, so I expect a more clear/intuitive explanation of the "integral transform" and the "polynomial span diagram". 
The experimental results on the CLRS algorithm reasoning benchmark are done via a very small-scale GNN (hidden size of 8/16), which could not fully demonstrate the practical impact of the order-3 updates. Hence, it doesn't surprise me that higher-order updates improve the small GNN models. 
questions: Can the authors demonstrate the improvement of the order-3 updates with larger GNNs? For example, a 128-dimension embedding and 256-dimension hidden layer?  

How's the improved the GNNs compare to the state-of-the-art on the CLRS benchmark? Or, can you improve the state-of-the-art models via the order-3 updates?
limitations: Though it is an interesting theoretical analysis work for GNNs and DP, the experimental results/settings are not satisfactory enough. (As stated in the weakness.)
review_title: null

Meta-review: metareview: All the reviewers and the AC believe this paper makes solid contributions to GNN and its connection with DP. Therefore, the AC recommends acceptance. 
confidence: Certain
Decision: Accept