Unbiased Stochastic Proximal Solver for Graph Neural Networks with Equilibrium States
Authors: Mingjie Li
Yifei Wang
Yisen Wang
Zhouchen Lin
Venue: ICLR 2023 poster (2023)

Abstract: Graph Neural Networks (GNNs) are widely used deep learning models that can extract meaningful representations from graph datasets and achieve great success in many machine learning tasks. Among them, graph neural networks with iterative iterations like unfolded GNNs and implicit GNNs can effectively capture long-range dependencies in graphs and demonstrate superior performance on large graphs since they can mathematically ensure its convergence to some nontrivial solution after lots of aggregations. However, the aggregation time for such models costs a lot as they need to aggregate the full graph in each update. Such weakness limits the scalability of the implicit graph models. To tackle such limitations, we propose two unbiased stochastic proximal solvers inspired by the stochastic proximal gradient descent method and its variance reduction variant called USP and USP-VR solvers. From the point of stochastic optimization, we theoretically prove that our solvers are unbiased, which can converge to the same solution as the original solvers for unfolded GNNs and implicit GNNs. Furthermore, the computation complexities for unfolded GNNs and implicit GNNs with our proposed solvers are significantly less than their vanilla versions. Experiments on various large graph datasets show that our proposed solvers are more efficient and can achieve state-of-the-art performance.

Published as a conference paper at ICLR 2023
UNBIASED STOCHASTIC PROXIMAL SOLVER FOR GRAPH NEURAL NETWORKS WITH EQUILIBRIUM STATES
Mingjie Li², Yifei Wang", Yisen Wang1.3, Zhouchen Lin
National Key Lab of General Artificial Intelligence,
School of Intelligence Science and Technology, Peking University
School of Mathematical Sciences, Peking University
Institute for Artificial Intelligence, Peking University
Peng Cheng Laboratory
ABSTRACT
Graph Neural Networks (GNNs) are widely used deep learning models that can extract meaningful representations from graph datasets and achieve great success in many machine learning tasks. Among them, graph neural networks with iterative iterations like unfolded GNNs and implicit GNNs effectively capture long- range dependencies in graphs and demonstrate superior performance on large graphs since they can mathematically ensure its convergence to some nontrivial solution after lots of aggregations. However, the aggregation time for such models costs a lot as they need aggregate the full graph in each update. Such weakness limits the scalability of the implicit graph models. To tackle such limitations, we propose two unbiased stochastic proximal solvers inspired by the stochastic proximal gradient descent method and its variance reduction variant called USP and USP-VR solvers. From the point of stochastic optimization, we theoretically prove that our solvers are unbiased, which can converge to the same solution as the original solvers for unfolded GNNs and implicit GNNs. Furthermore, the computation complexities for unfolded GNNs and implicit GNNs with our proposed solvers are significantly less than their vanilla versions. Experiments on various large graph datasets show that proposed solvers more efficient and can achieve state-of-te ofte--of-the-ar performance.
INTRODUCTION
Graph Neural Networks (GNNs) Zhou et al. 2020 Wu et al. 2020) can effectively aggregate information from its neighbors and then encode graph information into meaningful representations and have been widely used extract meaningful representations of nodes in graph-structured data recently. Furthermore, Graph Convolution Networks (KiNs)(Kipf* & Welling 2016) involve the convolution structure in the GNNs and drastically improve the performance
wide range of tasks like computer vision (Xu et al., 2020b), recommendation systems (He et al. 2020 Zhang al. 2020b) and biochemical researches (Mincheva & Roussel [0077] Wan al.) 2019). Due to these results, GCN models have attracted a lot of attention and various techniques have be proposed recently, including graph attention (Veličković al. 2017). normalization (Zhao & Akoglu 2019).
linearization (Wu et al. 2019 Li et al. 2022) and others (Klicpera et al. 2018 Rong et al.) 2020).
Current GNN models usually capture topological information of Thpps by performing T iterations graph aggregation. However, T cannot be large. Otherwise, their outputs may degenerate to some trivial points and such a phenomenon called over-smoothing (Yang al. 2020 Li et al. 2019). Therefore, traditional GNNs cannot discover the dependency with longer ranges. To tackle these prob- lems, researchers have proposed some graph neural networks with iterative update algorithms (Yang
al. 2021a a b). The implicit graph neural networks (IGNNs) (Gu et al., 2020) is another type of such
"Corresponding author

---

Published as a conference paper at ICLR 2023
model. Since these models will finally converge equilibrium state (stationary points fixed points), we call these models Graph Equilibrium Models for convenience the following paper.
Above graph equilibrium models enjoy superior advantages in capturing the oongerange information because they implicitly finish the "huge hop" aggregation via its forward procedure. However, graph equilibrium models have to recursively aggregate the neighborhoods of graph nodes since solving their equilibrium state needs iteratively aggregating the full graph. Therefore, it needs expensive computation costs deal with large graphs especially when they dense. Although many works (Chen el al. 2018 8 Hamilton et al. 2017) propose different aggregation methods through the sampling nodes in traditional graph models, there are no guarantees for their convergence and unbiased approximation when applying them to the graph equilibrium models.
For the above reasons, how efficiently obtain the outputs for these graph equilibrium models an interesting problem worth exploring. Inspired by Yang et al. (2021b); Zhu et al. (2021); (Zang et al. (2020a)'s 's works which reveal the connections between the implicit and the unfolded graph neural networks' architecture and learnable graph denoising problems, are trying study the efficiency of the above models from the optimization view. Then we propose two stochastic solvers for these graph equilibrium models with convergence guarantees inspired by the stochastic proximal gradient descent algorithms. Since our forward procedure only needs to aggregate subgraphs, the proposed solvers much more efficient than vanilla deterministic solvers gradient descent fixed-pol point iterations. Furthermore, we can theoretically prove that our solvers can obtain the unbiased output as the vanilla deterministic solvers do.
Our Contributions. We summarize the contributions of our methods as follows:
By splitting the graph denoising optimization for the graph equilibrium models as several sub-optimization problems, we treat their forward procedure as solving the proper finite-sum optimization problem. Then we propose two stochastic solvers for graph equilibrium models: Unbiased Stochastic Proximal Solver (USP solver) and its variant with variance reduction USP-VR solver.
Compared with the vanilla deterministic solvers which aggregate the full graph for graph equilibrium models' forward procedure, our USP solver and its variant only need aggregate subgraphs to reach the equilibrium. Therefore, graph equilibrium models can be more efficient than before with our stochastic solvers.
We theoretically prove that USP solvers can converge to the same outputs obtained by the vanilla deterministic forward procedure in expectation. Furthermore, we empirically demonstrate our proposed method's 's advantages with various experiments.
RELATED WORKS
2.1 GRAPH NEURAL NETWORKS
Most GNNs Kipf & Welling 2016 Velicković et al. 2017 Xu et al. 2018 Li et al. 2022) aggregate
the graph information for finite times due to the over-smoothing problem. Thereby, they can hardly capture very long-range dependency. Contrary to these models, implicit graph models (Liu et al.) 2021a
Gu et al. 2020 Park al., 2021) aggregate the graph information for lot of iterations or "infinite iterations with theoretically non-trivial equilibrium outputs.
Moreover, recent works tries to explore the connections between the graph neural models and the graph denoising optimization problem. Some works (Zhu et al. 2021 Zhang et al. (020a) recover different graph models to various graph denoising problems. Furthermore, Zhhu et al. (202T) also proposed two types of models by reformulating graph denoising problems from spectral filters per- spective. Some researchers focus on interpreting existing graph models from the view redesigning the correlated graph denoising models (Yang et al. 2021a Ma et al. 2021 Yang et al. 2021b)
Researchers also pay attention to GNNs from different perspective. For example, robust graph neural networks (Jin et al.) 2020: Luo et al. 2021), )), pretraining graph neural networks (Hu et al. 2019b; Qiu et al.) 2020), explanations for graph networks (Ying et al., 2019 Yuan et al.] (2000) and
connections to differential systems (Xu et al. 2020a Chamberlain et al. 2021 Wang et al.) 2021
2

---

Published as a conference paper at ICLR 2023
2.2 GRAPH EQUILIBRIUM MODELS AND IMPLICIT MODELS
Since the implicit graph models (Gu et al. 2020 Chen et al. 2022) and unfolded graph Yang et al. (202Ta); Liu et al. (02]c);; Klicpera al.
2018)'s forward procedure will converge to the equilibrium state of the corresponding optimization problem and Yang et al. (2021b) has already shown their relationships, we call these models the graph equilibrium models in the following. Yang et al.] (2021a) briefly discusses the deterministic proximal gradient descent method's implementation for explicit graph models. Different regularizers' impacts on graph models' robustness have also been explored in Liu et al. (202 lb by adding them and reformulating their correlated optimization problems. Implicit graph models(El Ghaoui et al. 2021) are new types of graph neural architectures inspired by the deep equilibrium models (Bai et al. 2019 Li et al. 2021 in deep learning whose outputs are determined implicitly by the designation of fixed- point equations with graph aggregation. Since these models' forward procedures are all trying to reach the equilibrium points by iteratively aggregating on graphs, these models can capture the long-range information of graphs. Therefore, the graph equilibrium models can perform well various large-scale graphs. However, these models need aggregating whole graphs lots of times for the outputs, the computation complexity is large when dealing with large and dense graphs we use the original solvers for graph equilibrium models.
2.3
GRAPH NEURAL NETWORKS FOR LARGE GRAPHS
Aggregating through large or dense graphs needs huge computation complexity. Different training or inference strategy have been proposed to reduce the computation cost for training and testing procedures. GraphSAINT (Zeng
al. 2019) and Cluster-GCN (Chiang al. 2019) propose subgraph sampling and restrict the back- propagation within the subgraphs to reduce the complexity of training. VR-GCN (Chen et al. (017)) uses the variance elimination method for training to improve the training performance. Narayanan et al. (202I) uses lazy update for weight parameters' training. GraphS AGE (Hamilton et 2017) updates a sub-sampled neighhorhood of node during training and inferencing to speed up GNNs.
3. GRAPH EQUILIBRIUM MODELS USING THE UNBIASED STOCHASTIC SOLVER
3.1 PRELIMINARIES AND SETTINGS
Implicit graph neural networks and other unfolded graph neural networks' forward procedure get the output features after n iterations (nn) for given input can be formulated as follows:
(n)
(-
B 7ÄZWWT).
(1)
with A I- D 1-22 A/2AAD-11 1/2 denotes the Laplacian matrix, A is the adjacent matrix, input injection
B AXWa n as former works (Gu et al. 2020 Park al. 2022) and is the activation function. It can be viewed as the implicit graph neural networks when = I and otherwise it can be regarded as other unfolded graph neural networks. The above equation can also be regarded as solving the following graph denoising problems by deterministic gradient descent with step size Y.
min G(Z) = min g (Z) + f(Z) = min (1 1 2
1 tr ( Á ((W))) + +f(Z), (2) 2
2
B
F
where f is the proximal function that tries to constrain the output features and can induce the widely used activation functions by different choices. For example, if we choose to constrain the output features to be non-negative by setting I as the positíve indicator function, then the corresponding graph equilibrium models will use ReI.U activation functions. Furthermore, the above formulation is the general formulation for different models. For example, IRLS (Yang et al.) 2021a) sets W = I, APPNP (Klicpera et al., 2018)) needs weight W and activation all be identity. Although our formulation Eqn 1 restricts the symmetric weight structure WW our optimization problem's 's weight parameter in Eqn 22 is not be constrained. Therefore, it won't have many impacts on the representative ability of the hidden problem and the graph equilibrium models, which are also illustrated in Hu al, (2019a)'s 's work. To solve the above problem get the equilibrium state,
3

---

Published as a conference paper at ICLR 2023
most works apply the deterministic gradient descent method like Equ (I. However, such solver is consuuinn,,, especially when aggregating large graphs in each update. Therefore, we are going to propose new solvers for the above graph equilibrium models to make them more efficient. Before that, we are going to make some assumptions for the convenience of our analysis.
Firstly, we assume WW l2 S |/ which can easily achieved by weight normalization (Sali mans Kingmal 2016) following Gu al. 2020)'s setting. As shown in former works (Bai et al. 2020; Li et al. (021). such a technique will not influence the performance much. Furthermore, assume the derivative of (Z) are Lipschitz continuous with Lipschitz constant I. satisfying
1 < L < 2. which can also be achieved by weight normalization. G(Z) is strongly convex with u 1, which can easily be achieved for many activation functions including ReLU. And our work,
we mainly focus on the graph equilibrium models without attention.
3.2 SOLVE GRAPH EQUILIBRIUM MODELS VIA UNBIASED STOCHASTIC SOLVER
In order obtain the solutions in stochastic way, we first reformulate the graph optimization from the view of edges as follows:
problem 2
min GZZ) min (Z) + f(2) z
min Z
B
B
+ 2
Σ (iJ)EE
-,
2, + IZ)),
Z
2
where & is the full edges set of the graph, (1,j) E E means an edge between node and j exist in the edge set ε, z, is the output feature vector for the i-th node and Aij denotes (ith) element of original Laplacian A. Viewing graph edges as samples of the dataset, the original algorithm can be viewed as using the global proximal gradient descent method for the problem (3). However, acquiring the global gradient in each iteration is expensive as we demonstrate above. To make them more efficient, we convert the deterministic solvers for graph equilibrium models to the stochastic scheme.
First, we separate the global graph denoising objective g into m sub-objectives:
98.
Z
Z
B
Σ
A.j A W 2y W 1
2
2
(L,))&&
where & C E is the k-th subset of edges which are randomly split into m sets from the full graph set and each contains around | edges. Then the original optimization problem can be regarded as finite optimization problem: G(Z)
1 m Ex G8, (Z) + S(Z).
Then we can use the stochastic proximal gradient method by randomly choosing ls E {1, m} with the same probability and calculate the stochastic gradient for updating as follows:
v(t)_ = ( + +mm. Z WWW - B,
(5)
( (z Vi())
where 7) = 1/2 is the step size and Ag s is the laplacian matrix for I8, with mErAAg = A and its (k), k2) element defined as:
Einoer Abii
if ki th=ha = k2,
Åg (ki, k2)
Aki
if (k), E E
0.
otherwise.
We call the graph equilibrium models "A" using our solvers are Eqn (6) as the "A w. USP" in the following. "A w. USP" can converge to the equilibrium state Zt as the following proposition states: Proposition 1. With the assumptions in Section 3.7 the expectations of our uniformly sampled stochustic grudient defined in Eqn 5) is the sume the g(Z)'s gradient, i.e. Eg Vz 95. (Z)
(Z) Furthermore, converge to the solution of the global objective Eqn (3) in expectation with the sub-linear convergent
conclude that with our USP solver Eqn (6) and nu }. the result will
rate, i.e., (We use Z" to denote the minimizer of Eqn (3)
1
E (t)
Z
= 0
-
F
4

---

Published as a conference paper at ICLR 2023
Proofs can be found in the Appendix. The above proposition indicates that iteratively forwarding the stochastic proximal gradient descent step Eqn (6) can finally get the solution for the problem Eqn (3, which means that our proposed stochastic solver is unbiased. Since the inner iterations Eqn (5) and (6) only need subgraphs instead the full graph, our stochastic proximal solver can be much more efficient than the original solvers for graph equilibrium models in practice. However, the USP solver's s forward procedure can only provide sub-linear convergence. Thereby, the outputs of our proposed solver will be less accurate than the vanilla deterministic models when their propagation times are limited during the forward procedure in practice and may influence performance. To solve such a problem, we propose another stochastic solver with the linear convergent rate in the following.
3.3 SOLVE GRAPH EQUILIBRIUM MODELS VIA UNBIASED STOCHASTIC SOLVER WITH VARIANCE REDUCTION
Although using the stochastic proximal gradient defined Eqn. (5) is unbiased, the large variance of the stochastic gradient still hinders our stochastic solver's s convergence speed. A straightforward way to reduce the variance is utilizzig the full gradient to correct the gradient every m2 iteration. For example, next m2 iterations of graph equilibrium models' forwarding are initialized with ( Z.
then for the k-th iteration with A: 2 1, we can use the modified gradient (*k) to replace the original (k) in Eqn
(k)
E (Z Vgg,, ( + Vg (Z),
(8)
with & sampled randomly from to m with the same probability. Moreover, we can easily conclude that the modified direction Va is unbiased and have smaller variance than ((k) in Eqn
(K)
Vg(Z(k-1)
2 Vg(Z
E
(
Vg
Replacing the original stochastic gradient with this modified version in the USP solver, obtain our Unbiased Stochastic Proximal Solver with Variance Reduction (USP- VR) which is inspired by the variance reduction algorithm proposed in Xiao & Zhang (2014). The procedure for USP-VE solver is listed in Alogrithm
Algorithm 1 USP-VR solver's s procedure for the equilibrium state.
Input: Input graph Laplacian A, input injection B, initial state žo. step size maximum iteration number m1, 1, maximum inner iteration number m2, W. depend on the choices of different graph equilibrium models.
Output: output Z.
1: Randomly split the whole edge set & into m subsets {E,,... Em and generate the subgraph's laplacian matrix. {Åg, "... .., }-
2: while <. my and (() not satisfies stop condition do
3: Ż (Z)
4:
V #-A2 B.
5: ( = Z.
6:
for k to m2 do
7:
Randomly pick E (1,... mm with the same probability. (A)) (Z (k-1) ) Z) + mÂg (Z ww V.
8:
9:
(k) (((-1) (k)
10:
end for
We mm [(k) i i= 11
7
12:
13:
end while
Since the global optimization problem G(Z) is strongly convex, the USP-VR solver's multi-stage procedure can progressively reduce the variance of the stochastic gradient Vş and both 2, (k) will finally converge to Z with proper step size 7).
5

---

Published as a conference paper at ICLR 2023
Proposition 2. With the same settings and assumptions in Proposition 1 can conclude that our proposed USP- VR solver can converge to the equilibrium state with step size n < 8Lmax and sufficiently large m2 so that
8Immax (m2 11 1)
(17 - m m
where Lmax max; L98g where L; are the Lipschitz constants for 9g, 's derivatives. The output (0 after i iterations will converge to the optimal solution Z linearly in expectation as follows:
E Z
z
S p'
0 -
As the above proposition shows, our USP-VR solver enjoys a linear convergent rate like the vanilla deterministic solvers. Therefore, USP-VE VR solver can achieve the solution which more near to optimal compared with the USP-VR solver with limited propagation times in the forward procedure. Moreover, our US solver is still much faster than the original deterministic solvers since only use the full graph for every m2 iteration.
3.4 BACKPROPAGATION WHEN USING OUR SOLVERS
Assuming all the graph equilibrium models have achieved the equilibrium Z' during its iterative forward pass, we use the one-step gradient by feeding Z to one deterministic iteration update (Eqn (T)) inspired by former works (Geng et al. 2021 Guo 2013 Fung et al. 2022). Using h to represent the deterministic iteration update (Eqn (T) for convenience, the output for down-stream tasks is Z 1(',, A, X). Since we can regard the whole structure as only propagating once from near-optimal initialization point, we can only backward the final iteration get the gradients. Gradients for learnable parameters in our methods can be written as follows:
aL(Z") az
I 0h X)
dh A,
08
OZ
where denotes the learnable parameters for the graph equilibrium models h. The one-step gradient can be regarded as the first-order Neumann approximation of the original gradients with a more efficient memory cost. We adopt this approximated gradient in all our experiments.
EXPERIMENTS
In this section, we demonstrate the efficiency of our proposed USP and USP-VR solver compared with the traditional implicit models large graph datasets with better performance both node classification and graph classification tasks. Specifically, we test graph equilibrium models using our solvers against their vanilla version and other models on 6 popular node classification datasets (Flickr, Reddit, Yelp, PPI (Zitnik& & Leskovec 2017). OGBN (Hu et al.] 2020) (Arxiv and Products)) and graph classification datasets. These datasets are challenging for not only graph equilibrium models but also vanilla graph neural networks due to their sizes. We conduct the experiments on Torch (Paszke) et al. 2019) with Torch-Geometric (Fey & Lenssen] 2019) and DGL (Wang al.] (019). All the
experiments are finished on an RTX-3090 GPU. The hyper-parameter settings and other details for the experiments are listed in the Appendix.
4.1 NUMERICAL EVALUATION
We first conduct an experiment to explore whether our proposed method can converge equilibrium as our analysis shows. As we cannot obtain the closed-form solution for Problem (2). we use the gradient of g( ZZ) in Eqn (3) the evaluation of the convergence. This is because V Zz (Z) 0 also
demonstrates satisfies the first-order condition of Problem ( Z is obtained by our methods.
In this part, we use Reddit to draw the convergence curve for one layer IGNN, IGNN w. USP, and IGNN w. USP-VR layer with 128 output feature size for each node. We set m = 20 for our proposed solvers and m2 10 for IGNN USP-VR. Then draw the convergence curve of the relative gradient concerning the equivalent subgraph aggregation times (Each IGNN's iteration through the full graph is equivalent to times subgraph aggregation) Figure T shows.

---

Published as a conference paper at ICLR 2023
x 10
IGNN
IGNN+USP
2.5
IGNN+USP-VR
hmmd
1.5
1.2
0
50
100
150
200
Equivalent raph Aggregation Times
Figure 1: The convergence curve of each model's equilibrium state on Reddit Dataset.
The convergence curve is consistent with our analysis: IGNN w. USP can quickly converge compared with IGNN and IGNN w. USP-VR in the beginning while IGNN w. USP-VR will finally converge to a better solution compared with the other two models.
4.2 NODE CLASSIFICATION
Comparison on popular large-scale graphs. In this section, first evaluate the performance of our methods on popular large-scale benchmark node classification graph datasets with the benchmark model APPNP and IGNN. The statistics of the four datasets are listed in Table We compare the performance of the above models with their vanilla and our USP solvers. Apart from that, we also report the vanilla GCN and its sampling variants as baselines. All models share the uniform hidden dimensions of 256, Appendix. Furthermore, all models are trained without subgraph training except the results for the ClusterGCN and GraphSAINT. The results are listed in Table 2
20 for our stochastic solvers, and other training details can be found in the
Table 1: Data Statistic ('m" stands for multi-labed classification, and "s" for single-label).
Dataset
Nodes
Edges
Degree
Classes
Training/Validationn//e
Flickr
89, 250
899, 756
10
7(s)
0.50/0.25/0.25
Reddit
232,965
114, 615, 892
50
41(s)
0.66/0.10/0.24
Yelp
716, 847
13, 954, 819
10
100(m)
0.75/0.10/0.15
PPI (Multi Graph)
14, 755
225, 270
14
121
0.79/0.11/0.10
OGBN-Arxiv
169, 169,343
166, 243
7
40(s)
0.54/0.18/0.18
OGBN-Product
2, 029
61, 859, 140
25
47(s)
0.90/0.02/0.08
From the table, one can see that our methods can outperform other vanilla models with notable advan- tages on most datasets, which means that our USP solvers can also capture long-range information such as APPNP and IGNN with their vanilla models. Moreover, the USP-V VR solver is slightly better than USP solver because USP-VR can obtain outputs that are nearer to the optimal.
In addition to evaluating the prediction performance, we also draw the testing and training time for different models F to demonstrate the efficiency of our proposed solvers. From the figures, one can see that USP solvers can accelerate APPNP and IGNN for more than 2x. Moreover, USP solvers are more than 10x faster than the vanilla solver on Reddit because its scale is larger than the other three datasets. Our USP-VR solver is slightly slower with better results than USP solver since they need additional full graph aggregation in the forward procedure.
Comparison OGBN dataset. Apart from the above datasets, also conduct experiments for different models with their vanilla solvers and our USP solver on OGBN datasets listed Table From the table,
that our USP solvers can still return comparable results OGBN datasets
7

---

Published as a conference paper at ICLR 2023
Table Comparison of test set Test Accuracy/FI-micro score with different methods. "OOT" here denotes that the time cost is more than 10x longer than using USP solvers.
Model
Flickr
Reddit
Yelp
PPI
GCN Kipf & Welling 2016
49.2 + 0.3%
93.3 + 0.1%
37.8 + 0.1%
51.2 0.3%
GraphSAGE Hamilton et 2017
50.1 + 1.3%
95.3 0.1%
63.4
63.4
FastGCN (Chen et al.
50.1 1.3%
0.1%
03.4:0.6%
51.3
ASGCN (Huang cf al.
2018
50.1 1.3%
95.3
63.4 0.6%
68.7 1.2%
ClusterGCN (Chiang ct al. 2019
48.1 + 0.5%
95.4+0.19
+0.9+0059
87.3 + 0.4%
GraphSAINT ZZng et al 2019
51.5 -: 0.1%
96.7
64.5 64.5 +: 0.3%
98.0 + 0.2%
APPNP (Kliepera al.
2018)
51.2 0.22
95.9 0.2%%
6.22%
98.1 + 0.2%
APPNP w. USP
52.4 0.1%
96.2 1 0.2%
0.3%
97.9 1 0.2%
APPNP w. USP-VR
52.3 1 0.2%
96.4 0.3%
63.7 1: 0.1%
98.2 1 0.3%
IGNN (Gu al. 2020
53.0 - 0.2%
OOT
65.8 + 0.2%
97.8 + 0.1%
IGNNN USP
54.1 + 0.2%
96.7 T 0.3%
66.2 1 0.2%
98.3 1 0.2%
IGNN w. USP-VR
54.3 0.1%
96.8 0.2%
66.1 + 0.2%
0.2%
102
IGNN w. USP
APPNP USP
IGNN w. USP-VR
APPNP USP-VR
IGNN
APPNP
10
100
10
Flickr
PPI
Yelp
Reddit
Flickr
PPI
Yelp
Reddit
(a) Epoch time for IGNN.
(h) Epoch time for APPNP.
Figure 2: Comparison the training time per epoch and test time through the full graph of IGNN
and APPNP with and without proposed solvers for different node classification datasets.
with much faster speed. From the above results, we can conclude that our proposed solvers can effectively improve the efficiency of various graph equilibrium models, especially on large graphs with comparable or even better performance on the node classification tasks.
IGNN
IRLS
APPNP
DAGNN
JKNet
Accuracy
70.1 0.8%
71.1 + 0.3%
71.1 0.2%
71.1 0.1%
71.0 = 0.2% 71.5 1 0.4%
Arxiv
w. USP Accuracy
72.7 72.7 0.2%
71.6 - 0.2%
71.4
71.3 0.1%
USP Speedup
3.5x
2x
2.5x
2.3x
2.4x
Accuracy
0.8%
73.8 + 0.2%
74.2 0.6%
73.7 0.6%
75.4 0.3%
Product
USP Accuracy
73.6 :: 0.3%
73.8 + 0.3%
74.6 + 0.5%
73.5 : 0.7%
75.2 = 0.4%
USP Speedup
5x
3x
6x
6.2x
4.5x
Table The empirical results for different Graph Equilibrium Models with their vanilla solver and our proposed USP solvers OGBN datasets.
4.3 GRAPH CLASSIFICATION
Aside from the node classification, we also conduct experiments on graph classification datasets to see whether methods can show consistent advantages graph classification tasks. We use D&D (Dosson & Doig 2003) (Bioinformatics Graphs) and COLLAB (Yanardag Vishwanathan 2015) (Social Graphs) for experiments and use CGS and IGNNs as baselines. Training details can be found in the Appendix. Results are listed Table Ba and test time for IGNN and our methods drawn in Figure 3b From the results, our proposed solvers also perform well.
8

---

Published as a conference paper at ICLR 2023
2
IGNN+USP
IGNN+USP-NE
1.5
IGNN
datasel
D&D
COLLAB
# Graphs
1178
5000
Test
Avg # Edges
716
2458
1
CGS-1
76.75 2.9%
3.5%
CGS-4
0OM
77.5 3.1%%
IGNN
16.588.1%
78.5 135+1.60 1.6%
0.5
IGNN USP
78.1 6.2%
78.4 1.2%
IGNN USP-VR
81.8 2.1%
78.1 + 1.5%
(a) Graph classification accuracy.
COLLAB
DD
(b) Test time for IGNN and IGNN with pro- posed solvers.
Figure 3: Graph classification accuracy and test time. Accuracies are averaged (and std are computed) on the outer 10 folds. CGS-k denotes the CGS model with heads. "OOM" denotes outtof-memor.
IGNN with proposed solvers is also faster than its origin in the experiment, 3x COLLAB and 1.5x on D&D as the figure shows. We notice that our efficiency advantages are less significant than using methods in the node classification tasks. The reason is that the scale of single graph is much smaller in the graph classification task and the time cost of graph aggregations is not too large compared with others like linear layers' propagation data processing. Furthermore, conclude that our stochastic solvers can perform more efficiently as the graph scale goes larger as our experiments show because the time cost of graph aggregation can gradually dominate the total cost of the implicit models as the graph gets larger.
can
4.4 ABLATION STUDY: COMPARISON WITH FORMER SAMPLING METHODS.
First, we use the "SAGE" aggregator to directly replace APPNP's graph aggregation to conduct the experiments OGBN-Arxiv. The results shown in Table 4a). From the table, one that the original sage aggregator is not stable when applying them on APPNP because they cannot ensure convergence like our USP solvers.
Vanilla
GraphSAINT
GrapKSAINT w. USP
Acc
71.1 + 0.2%
71.4 1:4:000 0.2%
5.7% 3.1s
Ace Epoch Time
6.2
65.2
0.3%
Epoch Time
4.1s
1.7s
14s
9.5a
(a) APPNP variants with full-graph training.
(b) IGNN with sub-graph training Yelp.
Figure Comparison of different accelerating methods.
Furthermore, we conduct experiments using GraphSAINT on IGNN with and without our USP solvers in Table (4b) Yelp. From the table, one that our USP solver can also accelerate the models when training them with the sub-graph techniques.
CONCLUSIONS
In our work, we first propose two stochastic solvers for the graph equilibrium models from the view of their relationship the graph denoising optimization problem. Our proposed solvers can be applied to different graph equilibrium models such as APPNP and IGNN. Since our proposed solvers only need to propagate uub-graphs in each aggregation, methods much faster than the original fixed point iterative or gradient descent solvers used for implicit graph models and unfolded graph models, especially large and dense graphs. Furthermore, unbiased and can finally output the same equilibrium state as the vanilla equilibrium models. The empirical results also demonstrate the advantages of different models with our proposed solvers for large-scale graphs.
also theoretically prove that solvers

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Zhouchen Lin and Yisen Wang were supported by National Key R&D Program of China (2022DD1100022, the major key project of PCL, China (No. PCL2021A12), the NSF China (No. 62276004, 62006153), Open Research Projects of Zhejiang Lab (No. 2022RC0AB05), Huawei Technologies Inc., Qualcomm, and Project 2020BD006 supported by PKU-Baidu Fund.
REFERENCES
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In NeurIPS, 2019.
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. In NeurIPS, 2020.
Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusioo.. In ICML, 2021.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In arXiv preprint arXiv: 10568, 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. In arXiv preprint arXiv: 1801. 10247, 2018.
Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Optimization-induced graph implicit nonlinear diffusion. In ICML, 2022.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-GCN, In SIGKDD, 2019.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. In Inproceedings of Molecular Biology, 2003.
Laurent EI Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit deep learning. SIMODS, 2021.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Samy Wu Fung, Howard Heaton, Qiuwei Li, Daniel McKenzie, Stanley Osher, and Wotao Yin. Jfb: Jacobian-free backpropagation for implicit networks. In AAAI, 2022.
Zhengyang Geng, Xin- Yu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. In NeurlPS, 2021.
Fangda Gu, Heng Chang, Wenwu Zhu, Somaych Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. In NeurlPS, 2020.
Jiang Guo. Backpropagation through time. In Unpubl. ms. Harbin Institute of Technologg, 2013.
William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs In arXiv preprini 1rXiv:1706.02216. 2017.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In SIGIR, 2020.
Shell Xu Hu, Sergey Zagoruyko, and Nikos Komodakis. Exploring weight symmetry in deep neural networks. In CVIU, 2019a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In arXiv preprint arXiv: /905. /2265, 2019b.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In arXiv preprint arXiv:2005.000 006877 2020.
10

---

Published as a conference paper at ICLR 2023
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In NewrIPS, 2018.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In SIGKDD, 2020.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In arXiv preprint Tefi::66000299000 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph
neural networks meet personalized pagerank. In arXiv preprint arXiv:1810.0599) 2018.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In ICCV, 2019.
Mingjie Li, Yisen Wang. Xingyu Xie, and Zhouchen Lin. equilibrium models. In ICLR, 2021.
Optimization inspired multi-branch
Mingjie Li, Xiaojun Guo, Yifei Wang, Yisen Wang, and Zhouchen Lin. GPen: Graph gaussian convolution networks with concentrated graph filters. In ICML, 2022.
Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and Xiaokui Xiao. Eignn: Efficient infinite-depth graph neural networks. In NeurIPS, 2021a.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. In NeurIPS, 2021b.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In ICML, 2021c.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong. Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In WSDM, 2021.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view graph neural networks as graph signal denoising. In CIKM, 2021.
Maya Mincheva and Marc R Roussel. Graph-theoretic methods for the analysis of chemical and biochemical networks. ii oscillations networks with delays. In Inproceedings of Mathematical Biology, Springer, 2007.
S Deepak Narayanan, Aditya Sinha, Prateek Jain, Purushottam Kar, and Sundararajan Sellamanickam. Iglu: Efficient gen training via lazy updates. In arXiv preprint arXiv:2 13995, 2021.
Junyoung Park, Jinhyun Choo, and Jinkyoo Park. Convergent graph solvers. In arXiv preprint arXiv:2106.00 0100006800000 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, 2019.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In SIGKDD, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In NewrlPS, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In arXiv preprint arXiv: 10903, 2017.

---

Published as a conference paper at ICLR 2023
Fangping Wan, Lixiang Hong, An Xiao, Tao Jiang, and Jianyang Zeng. Neodti: neural integration of neighbor information from heterogeneous network for discovering new drug target interactions. In Bioinformatics, 2019.
Minjie Wang, Da Zheng. Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph- preprint ar 1191:199,. 2019.
package for graph neural networks. In arXiv
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. In NeurlPS, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Simplify- ing graph convolutional networks. In ICML, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. In IEEE TNNLS, 2020.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. In SIAM, 2014.
Binghing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. In arXiv preprint arXiv:2007. 2020a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Qiangeng Xu, Xudong Sun, Cho-Ying Wu, Panqu Wang, and UIrich Neumann. Grid-gen for fast and scalable point cloud learning. In CVPR, 2020b.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In SIGKDD, 2015.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek F. Abdelzaher. Revisiting "over-smoothing" in deep gens. arXiv preprint arXiv:2003./3663, 2020.
Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. In ICML, 2021a.
Yongyi Yang, Yangkun Wang. Zengfeng Huang, and David Wipf. Implicit vs unfolded graph neural networks. In arXiv preprint arXiv:2 2021b.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In NeurlPS, 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In SIGKDD, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint 2019.
Hongwei Zhang, Tijin Yan, Zenjun Xie, Yuanqing Xia, and Yuan Zhang. Revisiting graph convolu- tional network semi-supervised node classification from an optimization perspective. In arXiv preprint arXiv:2009. 1469, 2020a.
Shijie Zhang, Hongzhi Yin. Tong Chen, Quoe Viet Nguyen Hung, Zi Huang, and Lizhen Cui. Gen- based user representation learning for unifying robust recommendation and fraudster detection. In SIGIR, 2020b.
Lingxiao Zhao and Leman Akoglu. Pairorm: Tackling oversmoothing in gnns. arXiv preprint arXiv:/909) /2223, 2019.
12

---

Published as a conference paper at ICLR 2023
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. In Al Open, Elsevier, 2020.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Web Conference, 2021.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. In Bioinformatics 2017.
13


Reviews:
[{"review_id": "rbo-tlLXvJi", "reviewer": "Reviewer_1NkB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\n\n# Post-rebuttal comments\n\nThe responses by the authors solved my questions. Therefore, I want to keep my score, leaning to accept.", "strength_and_weaknesses": "Strengths\n- The proposed methods have guarantees for convergence.\n- Numerical experiments demonstrated the usefulness of the proposed methods on large graph datasets.\n\nWeaknesses\n- Novelty in methodology is somewhat limited because randomization and variance reduction are relatively standard approaches to improve optimization algorithms.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cdOJu91Iq5", "reviewer": "Reviewer_ejih", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\nIt 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.\nFurthermore, the presentation of the paper could be improved.", "strength_and_weaknesses": "Strengths:\n+ A simple, computationally less expensive to optimize graph equilibrium models is proposed.\n+ The authors provide convergence guarantees of the average proposed sampling method and derive its convergence rate (O(1/t))\n+ They also propose a simple variance reduction scheme that enjoys a linear convergent rate like the vanilla deterministic solvers.\n\nWeaknesses and open questions:\n- The claimed performance improvements in Table 2 are often not significant.\n- How does the run time (in Figure 2) compare to explicit methods (which often do not perform much worse).\n- 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.\n- 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?\n- 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).\n- A complexity analysis of the proposed algorithm would strengthen the claim of computational advantages.\n\nPoints of minor critique and open questions:\n- Examples for f on page 3 would be appreciated.\n- Table 3 does not report any significance intervals.\n- 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...)\n- In contrast to what the authors claim the weight normalisation will influence the training dynamics.\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OUSQjQrKK-", "reviewer": "Reviewer_S8SB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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.", "strength_and_weaknesses": "Strength:\n1. The authors propose a method to accelerate the IGNN.\n\nWeakness:\n1. 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?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3LeComfWffl", "reviewer": "Reviewer_XXk2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\n\n## After rebuttal\n\nThe revision improves the paper. I am happy to increase my score. ", "strength_and_weaknesses": "# Strength:\n\nThe 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. \n\n# Weakness\n\nThe 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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster