Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors try to use reinforcement learning to investigate large sparse linear systems of equations. Meanwhile, they introduce the graph model here. 
main_review: Using reinforcement learning to solve large sparse linear systems of equations is a very interesting problem. The authors introduce the graph and GNN as the tools to investigate them. However, the quality is not enough and the content is not clear. The experiments look very good, but the theories are not very clear. If the authors can show strong theories, I would like to change my grade. Furthermore, the authors still need to show the significance of their work to the readers. 
limitations_and_societal_impact: Theories related to their experiments still need to improve.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose using RL agent via a TAGCOnv network in DQN to select coarse points in the procedure of coarsening algebraic grids. Theoretical results are established for the integration of the RL into a convergent scheme, and the complexity of the algorithm is at O(n) via a Lloyd based aggregation to constrain the coarsening to an O(n) selection.
main_review: Overall the paper clearly proposes a useful improvement of the AMG algorithm. The novelty here is in combining RL other AMG technique which Im not familiar with in prior work. The authors give sufficient empirical validation to the advantage of the suggested combination. The results are clearly of interest to practitioners who use AMG solvers in a variety of settings from solving pdes to other general systems in 2D grids. The authros clearly (and honestly) state that the generalization to other problems is still unknown.
There are still some details missing that I would be grateful if the authors could address in the rebuttal:
1.	I assume that the Lloyd based aggregation is a k-means essentially, hence the question is how to determine K so that the partition will still be O(n) but the size of each cluster will be approximately similar to that of the other clusters to allow faithful sampling from each.
2.	In this context, For example, I would expect the family of Aspect ratio to be fairly challenging. For some reason (could be a typo) the blue points for that family are not given in Fig. 3-right. Can you please elaborate on what type of grids, (and most importantly why) the Lloyd could be a limiting factor? and please report the aspect ration location in Fig 3-right.
3.	For fig 1 what is the greedy dominance factor?
4.	In fig 2 can we also see the greedy baseline?

limitations_and_societal_impact: no
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: An AMG coarsening algorithm is proposed based on reinforcement learning on graph neural networks. The coarsening is determined from the diagonal dominance criterium for AMG as proposed by MacLachlan and Saad. Numerical experiments on a wide variety of 2D meshes (structured and unstructured) for the Poisson problem show excellent performance compared to the simple greedy algorithm proposed by MacLachlan and Saad. Theoretical results are fairly limited but the approach is very promising algorithmically. However, more meshes (3D), elliptic operators (smooth and discontinuous coefficients), and better comparison to the state-of-the art should have been tried to truly assess the novelty and viability of the proposed algorithm.
main_review: Questions / remarks:
1) Can the proposed Reinforcement Learning (RL) solution be used as starting value for the NP hard problem (4) when solved as an integer programming? This would also allow to deduce how far from optimality the RL solution is.

2) How is an optimal agent defined in Thm 1? As minimising the number of actions? It is worth point out that in practice one does not find an optimal agent.

3) Sec 4.2 - line 204: Please give more details (in the appendix) about the "random convex triangular mesh" and its FEM discretisation. How is the mesh generated? Which FEM discretisation (order of elements)?

4) Please explain briefly (in the appendix) how Lloyd aggregation works and why it would result in an $O(n)$ cost.

5) Fig 3: Add other metrics like AMG grid complexity and convergence factor. Effective convergence factor combines, which is nice, but could be difficult to interpret.

6) Fig 2: add the type of mesh in the legend.

7) While I find the results of Poisson on unstructured meshes very impressive, more experiments should be done truly assess the novelty and viability of the proposed ideas: 
 - 3D (un)structured 
 - Variable coefficients (smooth and discontinuous) elliptic on 2D/3D
 - Helmholtz problems
 - Compare to state-of-the-art and not only to the greedy approach: standard AMG with heuristic coarsening and other ML optimized MG.
 - Maybe not needed but nice: actually solve the PDE and compare time, cost.

It is probably not feasible to perform all these tests, but I find doing at least a few of them necessary to make the submission acceptable for Neurips. It is recommended to put much more experiments in the appendix.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The authors in the article have made a contribution to Algebraic Multigrid Coarsening. The AMG method is used to solve sparse linear systems. They proposed to replace heuristic approach used in the coarsening process by an Reinforcement Learning scheme. They have used Duel Double DQN with TAGCN to implement the RL based scheme. The paper describes in detail the problem formulation in terms of RL and presents results of the proposed algorithms. There are some important issues of concern regarding the submission.
main_review:  - The presented algorithm is only tested on 2D Poisson problem and they admit that they do not know how the algorithm will behave on other systems. This is a big hurdle in the acceptance of the paper. The contributions in the abstract and in section 1 are not formulated to support the view described earlier. A normal reader is prone to believe that the algorithm "...can coarsen arbitrary unstructured grids, including those much larger than the training grid" or is able to "...learn to perform graph coarsening on small training graphs and then be applied to unstructured large graphs"
- It is assumed that the structural bias learned by RL during the training will not allow it to be used in different scenarios. So the algorithm may have shown good result for one set of problems, but it may need to be trained from scratch for any other type of problem. 
- Although, the authors claim that the algorithm is faster than any other technique, but there is no performance comparison present in the article. 
- The code provided by the authors is not useful. It is hard to know the dependencies and even after that effort one comes to know that there are missing files in the code.
- For example, this line produces error in "from DuelingNet2 import Net as Net_MPNN" in MG_Agent.py
- I do not agree with the authors that the complexity of Algorithm 2 is O(n). The Complexity of Algorithm 2 depends on the structure of matrix A. Finding arg max could itself have a complexity of O(n) in normal circumstances. So the whole algorithm may have the complexity of O(n^2).
- It is not mentioned how the accuracy of the result is affected after grid coarsening. More coarse graph may also lead to bad results.
limitations_and_societal_impact: NA
review_title: null

Meta-review: ## Original AC meta-review

This paper proposes a systematic way of computing optimal coarsening for algebraic multigrid (AMG) algorithms by using a) connection of this problem to graph algorithm b) formulation of the optimal selection as a game c) solution of the RL problem using graph neural networks. The resulting algorithm is compared against classical greedy algorithm and beats it on a wide range of meshes. One of the important contributions is the usage of LLoyd aggregation that allows the learned coarsening to be computed in linear complexity. Most of the reviewers agree that the approach is interesting algorithmically and promising in practice. Some concern was raised about theoretical contribution, but it is not so clear to me where this should go: the equivalence to RL task is shown, and how good the RL algorithms solves problem is quite difficult to show.

For the experiments, as it was noted in the reviews, the resulting convergence is only shown for 2D Laplace problem, which can be considered as a minus for the paper. However, the framework that are proposed do not depend on the type of the PDE, so this would have been a nice addition, but not change the main message of the paper.

To summarize, this is one of the first works where RL approach seems to provide a practical tool for constructing AMG precondition and can be important for the field.

## SAC meta-review (the AC's recommendation was borderline)

This paper had quite opposite recommendations from the reviewers so I had to check more carefully how to calibrate them with respect to the ones on other accepted / rejected papers. I also read the paper. While I agree that this paper presents an interesting line of research that should be presented to the machine learning community, the current submission did not appear ready yet for publication at NeurIPS. In particular, as mentioned by some reviewers, the authors should make their paper more self-contained in terms of many non-standard topics in the machine learning community (like Lloyd's aggregation, which is not described at all even in an appendix). The work should also be better related to the current machine learning literature: for example, RL has already been used to solve several combinatorial algorithms (see [A],[B] e.g.), how does their approach to solve (4) fit and compare with this literature? (this was not mentioned at all in the current submission) Finally, comparing only with the greedy algorithm of [17] appears limited for such a niche area, especially since the authors already mentioned that their approach should be more effective than simulated annealing [18] in lines 147-148, but yet do not demonstrate this at all empirically or theoretically. Including such a comparison would improve the significance of the work.

I encourage the authors to take these comments in consideration for a resubmission.

[A] Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290(2), 405-421. (on arXiv since 2018)
[B] Mazyavkina, N., Sviridov, S., Ivanov, S., & Burnaev, E. (2021). Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 105400. (on arXiv since 2020)
Decision: Accept (Poster)