Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a method for learning how to predict the properties of graphs. These properties are fixed points (e.g. the PageRank vector or Equilibrium Values of a Diffusion Process).Wrt existing methods (SSE and IGNN), CGS learn multiple transition matrices instead of using a unique one. The underlying idea is to: (a) learn several linear operators whose iterations lead to a fixed point, (b) aggregate/combine the fixed points and (c) make the final prediction. With these elements to hand it is possible to find fixed points for several tasks. The proposed approach is tested in PHYSICAL DIFFUSION, GRAPH VALUE ITERATION and GRAPH CLASSIFICATION. The results show that CGSs are competitive with the state of the art and sometimes generalize better. 
main_review: STRONG POINTS: There is a principled theory regarding contractive linear maps as well as the existence of inverses. Experiments are well explained (sometimes is interesting to explain again what is the readout for the classification). Supplementary material is often used by this reviewer just to better understand the statements and experiments, but they are very well structured and provide the necessary evidence. 

WEAK POINTS: I get the point of using SSE or IGNN for computing global descriptors of the graphs instead of node embedding, which is not scalable for real-world graphs (large number of nodes). However, the approach presented here is limited exactly for the same reason. Consider for instance the problem of learning many linear mappings for a very large graph. Gradient descent is difficult to compute (need either matrix inversion or solving a linear system) and this is not practical. This is why most of the experiments are done with small graphs. 

RECOMMENDATION and ARGUMENTS: My recommendation is weak acceptance. Since the WEAK POINT is evident, the theoretical contribution is very interesting and inspires additional tasks (widely applicable). 

QUESTIONS AND ADDITIONAL EVIDENCE. Please clarify the following paragraph: "From the results, we can conclude that learning to generate transition matrices A(G) from the data is more effective than using the fixed transition matrix, as in SSE and IGNN, to achieve a model with better generalizability" and contextualize with respect to the mechanism used by SSE. It there any trade-off between less mappings to learn and better generalization? 
summary_of_the_review: The paper is theoretically interesting but the results are limited to small graphs.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper constructed a linear map on graph that is guaranteed to converge to a fixed point, by embeding such linear map into a graph neural network, it can be used to solve nonlinear problems on graphs. Experiments show that the proposed methods have good performance in various methods. 
main_review: The key idea from the observation that the diffusion on a graph often converges to a fixed point. Thus the authors proposed a linear map that is used to mimic this procedure. I did not check all the derivations and proofs of the paper, but I believe the correctness of Theorem 1 is quite obvious. 

Currently overall the paper is ok but there are three problem. 

(1) The result of Theorem 1 can be further improved. In the paper the authors only consider linear maps, but the Banach fixed point theorem is strong enough to handle nonlinear maps. I guess we can easily add non-linear functions such as ReLU, sigmoid or tanh to (6) to get a nonlinear convergent map.

(2) In linear case, it might not be a good way to compute the fixed point by matrix inverse. The inverse of matrix might be expensive. Meanwhile, by using fast matrix multiplication we can use O(log n) matrix  multiplication to get an approximate fixed point very fast. 

(3) In graph value iteration, the authors only considered deterministic transition case, while in practice the transition are often with uncertainty. The authors may consider to extend this part to probabilistic cases.
summary_of_the_review: The motivation and the theory of the paper is clear and correct. But there are some space for the authors to further improve the quality of the paper, also the value iteration part of the paper is to restrictive and it need to be extended.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces the equilibrium GNN-based model with a linear transition map. The transition map is made contracting to ensure that the fixed point exists and is unique. The paper provides the extensive comparisons and ablation studies for the proposed model.

main_review: **Strong points:**

The paper is well-written and motivates the choice of the linear transition map from theoretical prospective. The fact that the transition map should depend on the input graph is Interesting and has not been explored by the previous works.

The paper also provides extensive ablation studies on their modelling choices as well as the snippet of the code for the model.

**Weak points:**

It is a bit odd to compare the CGS across the number of heads, while GNN results are provided for a different number of message-passing layers. This particularly makes the figure 3 to be misleading. CGS and GNN will have a similar number of parameters if they have the same number of layers and output heads, if I understand correctly. I see that CGS results for different layers are provided in the supplement, but it will be handy to put them into the same table and compare CGS and GNN across the same parameters.

The similar issue is with SSE and IGNN models, especially since the architecture is slightly different across experiments. It would be handy to mark which CGS(m) is the most direct comparison to SSE and IGNN in terms of number of layers and heads.

**Additional questions:**

It is intriguing that implicit GNN models can handle long-range interactions without increasing the depth of the GNN. Do you have a hypothesis why?

It is odd that more output heads result in better performance. The Implicit Layers tutorial by Zico Kolter (http://implicit-layers-tutorial.org/deep_equilibrium_models/, section “One (implicit) layer is all you need”) demonstrates that a single equilibrium layer is equivalent to modelling a “stack” of several equilibrium layers (or multiple GNN heads). Can it be that the increased performance is simply due to higher output dimensionality?

Minor: I would be interested to see the runtime comparison between the GNN models and CGS, as CGS requires up to 50 iterations to converge (according to the code snippet).


summary_of_the_review: The paper uses fixed-point iteration to find the equilibrium point of the graph network and constructs the transition map to be contracting and input-dependent to ensure a unique fixed point. The paper provides extensive comparisons with other equilibrium models and on different types of graphs. It is a clear accept for me.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a graph neural network termed "Convergent Graph Solvers" that computes the stationary distribution of stochastic matrices. This is achieved by an implicit definition of a linear system and by computing the fixed point of that system. The paper shows on a range of problems that the proposed approach works well and that it is particularly fast for smaller graphs.
main_review: The proposed approach is technically sound and empirically evaluated on a range of experiments. The paper is generally well-written, easy to follow, and contains enough technical details to understand the underlying principles. I found that I had to look at the appendix a couple of times for important details. This includes for example the experimental details or the discussion on the runtime comparison of direct inversion and iterative methods. I think that it would have been beneficial to briefly summarize those details in the main paper.

The paper proposes a three-step procedure that is guaranteed to converge by construction. This approach is well motivated and seems promising. At first, one might wonder whether the constructed maps are expressive enough. Various experiments suggest that this is often the case. The ablation studies in the appendix corroborate the claim regarding computational complexity and suggest that the proposed method performs particularly well for problems with a large number of samples.
summary_of_the_review: The paper is well written, clearly explains the underlying assumptions and limitations, and shows promising results on a range of experiments.
review_title: null

Meta-review: The paper got four accepts (after the reviewers changed their scores), all with high confidences. The theories are complete and the experiments are solid. The AC found no reason to overturn reviewers' recommendations. However, the AC deemed that all the pieces are just routine, thus only recommended poster.
Decision: Accept (Poster)