Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Two unbiased stochastic proximal solvers for learning graph equilibrium models are proposed. They are inspired by the stochastic proximal gradient descent method and its variance reduction variant (called USP and USP-VR solver). Both provide considerable computational speed-ups in comparison with the original solvers.

strength_and_weaknesses: Strengths:
+ A simple, computationally less expensive to optimize graph equilibrium models is proposed.
+ The authors provide convergence guarantees of the average proposed sampling method and derive its convergence rate (O(1/t))
+ They also propose a simple variance reduction scheme that enjoys a linear convergent rate like the vanilla deterministic solvers.

Weaknesses and open questions:
- The claimed performance improvements in Table 2 are often not significant.
- How does the run time (in Figure 2) compare to explicit methods (which often do not perform much worse).
- The equilibrium solution $Z^*$ needs to be defined precisely. Currently, the formulation of Proposition 1 suggests that $Z^*$ might be unique, which is not the case in general. Also the experiments confirm this, since the IGNN variants do not seem to converge to the same solutions.
- How is the proposal different from (Chen et al., 2018; Hamilton et al., 2017) for "traditional graph models" and why should these not transfer to graph equilibrium models?
- The convergence results in expectation seem trivial as, in expectation, the procedure is not different from optimising the full model. The real challenge would lie in the analysis of the error that is introduced by the sampling scheme (or the average number of additional SGD steps to reach an equilibrium that are required for the actual sampling scheme and not its average).
- A complexity analysis of the proposed algorithm would strengthen the claim of computational advantages.

Points of minor critique and open questions:
- Examples for f on page 3 would be appreciated.
- Table 3 does not report any significance intervals.
- The formulation is restricted to symmetric weight structure $WW^T$ but the authors claim that this has no effect on the performance of the model. (It should impact its expressive power though...)
- In contrast to what the authors claim the weight normalisation will influence the training dynamics.
- page 5/6: `Therefore, our USP-VR solver can achieve a more accurate solution compared with the USP-VR solver with limited propagation times in the forward procedure.' does not seem to make sense.
clarity,_quality,_novelty_and_reproducibility: The paper does not make a very polished impression and is for that reason hard to follow from time to time.
It should be discussed more concretely why previous cannot be transferred to the setting of equilibrium because this does not seem to be apparent.
The proposed scheme seems relatively trivial but this can also be a feature.
summary_of_the_review: A strength of the paper is that the methodological proposals achieve performance speed-ups that are backed up by theoretical investigations.
It is not sufficiently clear to me, however, whether the contribution is sufficiently novel in comparison with similar schemes that have been developed for "non-equilibrium" models.
Furthermore, the presentation of the paper could be improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper revisits the implicit and optimization perspective of designing graph neural networks. Based on this perspective, the paper adopts two existing algorithms such as stochastic proximal gradient descent and its variance-reduced version to accelerate the forward computation with sampling. The backward computation is simply replaced by a one-step backward on the equilibrium point. Experiments demonstrate the effectiveness and efficiency of the proposed algorithm.

strength_and_weaknesses: # Strength:

The motivation and background of the studied problem have been clearly demonstrated, and the paper is well written. The paper revisits the implicit and optimization perspective of designing GNNs. The finite-sum reformulation draws a natural connection with stochastic proximal gradient algorithm and the variance-reduced variant. The idea is simple but effective and efficient as demonstrated in the experiments. 

# Weakness

The forward computation of the solver is natural, simple, and well-justified. However, the backward computation is simply replaced by a one-step backward on the equilibrium point. This seems surprising if it can work well in practice. It would be great if the author can provide solid theoretical justification as well as the empirical study on the gradient approximation error due to this approximation. Moreover, the idea of sampling is standard in stochastic optimization. Therefore, the contribution and novelty are a bit weak.


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written with good quality. The idea is simple but effective.
summary_of_the_review: The paper provides a simple but effective approach for the training of large-scale implicit GNNs. The effectiveness and efficiency are clearly demonstrated. Solid theoretical and empirical justification of the backward computation can further improve the paper.

## After rebuttal

The revision improves the paper. I am happy to increase my score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work introduces the sampling way in the GNNs from optimization perspective. And thus it alleviates the computation cost on graph diffusion in different iterations. Furthermore, Variance Reduction (VR) is introduced for improving the performance. 
strength_and_weaknesses: Strength:
1. The authors propose a method to accelerate the IGNN.

Weakness:
1. This work is incremental it only works for some specific frameworks (here is IGNN). However, there are so many GNNs like ODE and PDE GNN. If this type of incremental work makes it into the ICLR, we should have many for different GNNs in future. But does it inspire any member in this community? Is this really necessary?
clarity,_quality,_novelty_and_reproducibility: The whole paper is good, both in terms of clarity and quality. But the novelty is trivial in my opinion. 
summary_of_the_review: According to my comments above, I am personally inclined to reject this paper. Of course I am happy to see other different opinions before making a decision.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed an efficient way to compute Graph Equilibrium models. The computation of the Graph Equilibrium model is an optimization problem of a graph denoising problem, and its naive solution is computationally expensive due to the use of an entire graph. This paper introduced the Unbiased Stochastic Proximal Solver (USP-solver) and its variance-reduction version USP-VR. They compute the Graph Equilibrium model by sampling the edges of the underlying graph. It was shown that USP converges to the equilibrium state at a sub-linear rate and USP-VR at a linear rate. Numerical experiments were conducted on node prediction and graph prediction problems to verify the practical usefulness of the proposed methods.
strength_and_weaknesses: Strengths
- The proposed methods have guarantees for convergence.
- Numerical experiments demonstrated the usefulness of the proposed methods on large graph datasets.

Weaknesses
- Novelty in methodology is somewhat limited because randomization and variance reduction are relatively standard approaches to improve optimization algorithms.
clarity,_quality,_novelty_and_reproducibility: Clarity

It took me some time to understand the method on first reading because (1) looks like one layer of an ordinal GNN, although the main interest of this paper is implicit GNNs. Therefore, I would suggest briefly writing the formulation of implicit GNNs, and how (1) is derived.
Nevertheless, overall, the paper is well-written.


Quality

The proposed methods are justified from both theoretical and empirical points of view. First, Propositions 1 and 2 ensure that the proposed methods converge to an equilibrium state, demonstrating their theoretical soundness. Regarding the empirical evaluations, I want to clarify what the authors meant by computational complexity (e.g., in the abstract). Figure 2, Table 3, and Figure 3 certainly provide evidence for the improvement of numerical improvements in computational speed. They have also shown that there is no degradation in prediction performance. If the authors also intended space complexity, it would be desirable to evaluate memory usage quantitatively. That said, memory efficiency is implicitly evaluated, although I am not sure the authors intended this. For example, in Table 2, when using the Reddit dataset, the vanilla IGNNs caused OOM, while IGNN+USP and IGNN+USP-VR did not. 

Novelty

If my understanding is correct, randomization is a relatively standard approach to reduce the computational complexity of optimization algorithms in expectation or with high probability. Also, variance reduction is a standard technique. In this sense, the method proposed in this paper is a natural improvement of the algorithm.

Reproducibility

The Appendix described the hyperparameters of the prediction model. Although this paper did not describe every full detail of dataset preparations, this is not a problem because references and dataset specifications are available. Since code is not provided, there is no guarantee of perfect reproduction. However, I think we can implement the code to reproduce the experiments to some degree.

Minor Comments

- P3 (1): $Z^{(n)}$, $Z^{(n+1)}$, $Z$ are undefined.
- P4 $\|WW^\top\| \leq 1/\tilde{A}$: this formula is invalid because the left hand side is scaler-valued, while the right hand side is vector-valued.
- P4 (3): $g(Z) + f(Z)$ -> $\min_{Z} g(Z) + f(Z)$
- P6 last equation: $\sum_{(k1, j) \in \tilde{\mathcal{E}}_k}$ -> $\sum_{(k_11, j) \in \tilde{\mathcal{E}}_k}$
summary_of_the_review: Although randomization and variance reduction are relatively standard approaches, as far as I know, these approaches have no application to implicit GNNs. In addition, the method is sound in that it has theoretical guarantees, and numerical experiments have shown its practical usefulness.

# Post-rebuttal comments

The responses by the authors solved my questions. Therefore, I want to keep my score, leaning to accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work proposed an efficient way to compute Graph Equilibrium models from optimization perspective, which for example reduce the computation cost on graph diffusion in different iterations. The computation of the Graph Equilibrium model is an optimization problem of a graph denoising problem, and its naive solution is computationally expensive due to the use of an entire graph. This paper introduced the Unbiased Stochastic Proximal Solver (USP-solver) and its variance-reduction version USP-VR. They compute the Graph Equilibrium model by sampling the edges of the underlying graph. Both provide considerable computational speed-ups in comparison with the original solvers. It was shown that USP converges to the equilibrium state at a sub-linear rate and USP-VR at a linear rate. Numerical experiments were conducted on node prediction and graph prediction problems to verify the practical usefulness of the proposed methods. Reviewers pointed out issues including relatively modest novelty, theoretical justification (e.g., on backward step) and limited applicability. The authors did a good job of response and pointed out that the model not only improves various graph equilibrium models' efficiency but also is unbiased and has the convergence guarantee. In addition, the authors provided suggested theoretical justification and showed broad applications with added experiments. Overall, the reviewers have more positive assessment after author responses. 
justification_for_why_not_higher_score: Novelty is somewhat incremental. 
justification_for_why_not_lower_score: Reviewers pointed out issues including relatively modest novelty, theoretical justification (e.g., on backward step) and limited applicability. The authors did a good job of response and pointed out that the model not only improves various graph equilibrium models' efficiency but also is unbiased and has the convergence guarantee. In addition, the authors provided suggested theoretical justification and showed broad applications with added experiments. Overall, the reviewers have more positive assessment after author responses.
Decision: Accept: poster