Scalable and Effective Implicit Graph Neural Networks on Large Graphs
Authors: Juncheng Liu
Bryan Hooi
Kenji Kawaguchi
Yiwei Wang
Chaosheng Dong
Xiaokui Xiao
Venue: ICLR 2024 poster (2024)
Keywords: graph neural networks
implicit graph neural networks
implicit models
graph learning
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) have become the de facto standard for modeling graph-structured data in various applications. Among them, implicit GNNs have shown a superior ability to effectively capture long-range dependencies in underlying graphs. However, implicit GNNs tend to be computationally expensive and have high memory usage, due to 1) their use of full-batch training; and 2) they require a large number of iterations to solve a fixed-point equation. These compromise the scalability and efficiency of implicit GNNs especially on large graphs. In this paper, we aim to answer the question: how can we efficiently train implicit GNNs to provide effective predictions on large graphs? We propose a new scalable and effective implicit GNN (SEIGNN) with a mini-batch training method and a stochastic solver, which can be trained efficiently on large graphs. Specifically, SEIGNN can more effectively incorporate global and long-range information by introducing coarse-level nodes in the mini-batch training method. It also achieves reduced training time by obtaining unbiased approximate solutions with fewer iterations in the proposed solver. Comprehensive experiments on various large graphs demonstrate that SEIGNN outperforms baselines and achieves higher accuracy with less training time compared with existing implicit GNNs.

Published as a conference paper at ICLR 2024
SCALABLE AND EFFECTIVE IMPLICIT GRAPH NEURAL NETWORKS ON LARGE GRAPHS
Juncheng Liu Bryan Hooi Kenji Kawaguchi Yiwei Wang! Chaosheng Dong! Xiaokui Xiao
National University of Singapore juncheng. liudu. nus edu
!University of Californi, Los Angeles 'Amazon.com Inc.
ABSTRACT
Graph Neural Networks (GNNs) have become the de facto standard for model- ing traph-structured data in various applications. Among them, implicit GNNs have shown a superior ability to effectively capture long-range dependencies underlying graphs. However, implicit GNNs tend to be computationally expensive and have high memory usage, due to 1) their use of full-batch training; and 2) they require large number of iterations solve fixed-point equation. These compromise the scalability and efficiency of implicit GNNs especially on large graphs. In this paper, we aim answer the question: how can we efficiently train implicit GNNs to provide effective predictions on large graphs? We propose a new scalable and effective implicit GNN (SEIGNN) with a mini-batch training method and a stochastic solver, which can be trained efficiently on large graphs. Specifically, SEIGNN can more effectively incorporate global and long-range infor- mation by introducing coarse-level nodes in the mini-batch training method. It also achieves reduced training time by obtaining unbiased approximate solutions with fewer iterations in the proposed solver. Comprehensive experiments various large graphs demonstrate that SEIGNN outperforms baselines and achieves higher accuracy with less training time compared with existing implicit GNNs.
INTRODUCTION
Recently, Graph Neural Networks (GNNs) have been widely used for modeling graph-structured data in the real world and achieved great success in numerous applications (Wu al., (020)) including computer vision (Shi and Rajkumar 2020), recommendation systems (Zhang et al. 2020). and drug discovery (Wan et al. 2019). In general, to utilize both graph topology and node attributes for generating meaningful node representations, modern GNNs iteratively aggregate representations of neighbors of each node with its own representation to update representations, which termed as the "message passing" mechanism (Gilmer al. 2017).
Despite the success achieved by these GNNs on different tasks, they lack the ability to capture long-range dependencies in graphs. The reason is that traditional GNN models only capture information up to 7 --hops away with T layers. T cannot be large because a large causes the over-smoothing problem (Li et al. (2018). To mitigate this limitation of traditional GNNs, another type of GNNs, called implicit GNNs, has been proposed to capture long-range dependencies (Gu al. 2020 Liu al. 2022 Li al. 2023). Implicit GNNs define implicit layer using fixed- point equation for aggregation and generate the equilibrium as node representations by solving the fixed-point equation. These implicit GNNs have superiority in capturing long-range information as they can be treated as a GNN with many layers defined implicitly to aggregate the information from distant nodes in the forward pass. Meanwhile, they enjoy constant memory complexity through implicit differentiation when computing gradients in the backward pass (Bai al. 2019).
In spite of the advantages of implicit GNNs in capturing long-range information, they suffer from scalability issues on large graphs. The first limitation is is their reliance on full-batch training, which involves iteratively aggregating an entire graph to solve the fixed-point equation. This approach incurs significant computational costs and it is sometimes not massive memory may be required to load a whole graph into GPU during training. For example, MGNNI runs out of GPU memory the ogbn-products dataset as shown Table 2
feasible on large graphs since

---

Published as a conference paper at ICLR 2024
Although there several sampling-based methods proposed to enable mini-batch training for traditional GNN models (Hamilton et al. 2017] Zeng et al.] 2021 Chiang et al. 2019), it is infeasible to directly apply these methods to implicit GNNs without sacrficing their effectiveness/ [ The reason is that these methods split an entire graph into several subgraphs as mini-batches, which prohibits information propagation between different mini-batches. Therefore, directly employing existing mini-batch methods may be harmful to the ability of implicit GNNs to capture long-range information. Besides the limitation of using full-batch training, the second limitation is that implicit GNNs are computationally expensive to train, as they usually require a large number of iterations to iteratively solve fixed-poi fixed-point equation. This issue can be exacerbated on large graphs.
Motivated by the aforementioned limitations of previous implicit GNNs, in this paper, we aim to answer the question: how to efficiently train implicit GNNs to provide effective predictions on large graphs? To achieve this, we propose a scalable and effective implicit GNN (SEIGNN) with mini-batch training method. Specifically, following previous sampling-bas -aased methods, our designed mini-batch training method also samples subgraphs, but adds coarse-level nodes representing different graph partitions, while new edges are included considering both coarse nodes and original nodes. In this way, mini-bated training method avoids full-batch training and encourages information propagation between nodes within different mini-batches, which cannot be achieved by previous implicit GNNs or by directly applying existing mini-batch methods implicit GNNs. Therefore, with this mini-batch training, SEIGNN can scale up to large graphs without sacrificing the ability to capture global or long-range information.
Moreover, to reduce the extensive training time of previous implicit GNNs caused by a large number of iterations for obtaining equilibrium, in SEIGNN, we also propose a new stochastic unbiased solver that can solve the fixed-point equation with fewer iterations to obtain approximated equilibrium.
Our contributions We summarize the contributions of this work follows:
We first point the scalability and efficiency limitations of previous implicit GNNs, which caused by full-batch training and their large number of iterations used for getting equilibrium.
To mitigate the limitations, we propose SEIGNN, a scalable and effective implicit GNN, which incorporates our designed mini-batch training methods with coarse nodes to capture global infor- mation; and a new stochastic solver that achieves unbiased estimates of equilibriums. Through these, SEIGNN can be efficiently trained large graphs while maintaining the ability to capture long-range information.
Comprehensive experiments on 6 datasets show that SEIGNN achieves better accuracies with less training time on large graphs. Additionally, the detailed ablation studies further demonstrate the effectiveness of our methods.
RELATED WORK
2.1
GRAPH NEURAL NETWORKS
GNNs have been widely used for modeling graph data in different tasks. Modern GNNs (Kipf and Welling 2016 Hamilton al. 2017) usually follow the "message passing" mechanism where information is aggregated from the neighbor nodes for each node. Different GNN models have been proposed utilize skip connection (Xu et al. 2018 Chen et al. 2020), attention mechanism (Veličković et al., 2018), and simplified activation (Wu et al. 2019). However, these models usually only involve finite aggregation layers due to the ovor-smoothing problem (Li et al. 2018), which makes them hardly capture long-range dependencies graphs.
2.2 IMPLICIT MODELS AND IMPLICIT GRAPH NEURAL NETWORKS
Implicit models/ deep equilibrium models (Bai et al. 2019) generally define an equilibrium equation implicit hidden layers generate outputs by solving the equation. These models have attracted much attention recently as they can avoid storing hidden states and achieve constant memory con- sumption by using implicit differentiation. For example, Bai al. (0019) and Bai al. 2002
Table empirically shows that directly using these methods with implicit GNNs performs poorly.
2

---

Published as a conference paper at ICLR 2024
propose the deep equilibrium model (DEQ) and its multiscale variant demonstrating the ability of implicit models in image and text related tasks. Some theoretical works (Kawaguchi] (021) and (Geng et al. 202T) also explore the convergence analysis and provide a gradient estimate for implicit models to avoid exact gradient computation, respectively.
Inspired by implicit models, several implicit GNN models have been proposed, such IGNN (Gu et al. 2020). EIGNN (Liu et al. 2021), MGNNI (Liu et al. 2022). CGS (Park et al. 2022). Since these models iteratively aggregate information from neighbors obtain the fixed-point solution of the equilibrium equation, they can capture long-range information on graphs. However, as these implicit GNNs use full-batch training that iteratively aggregates a full graph get outputs, they cost lot of training time and need massive memory for storing whole graph and the representation of each node in GPU memory. To reduce the computation complexities, a recent work USP (Li et al. 2023) proposes to use mini-batch training as aggregating information on randomly sampled subgraphs with proposed proximal solvers. However, randomly sampling subgraphs as mini-batch might affect the ability of implicit GNNs to capture long-range information.
2.3 GRAPH NEURAL NETWORKS FOR LARGE GRAPHS
To avoid huge computation costs incurred in training GNNs on large graphs, several mini-batch training methods for traditional GNNs have been proposed scale up GNNs. Cluster-GCN (Chiang
ct al. 2019). GraphSAINT ZZng et al.) (020). and Shadow-GNN ZZng et al. 2021 sample subgraphs as minibatches and train GNNs within different subgraphs to reduce the computation cost. Specifically,
UCN relies on graph clustering method to generate subgraphs while Shadow-GN GNN uses Personalized Pangenlk scores select important nodes form subgraph for each target node. GraphS AGE (Hamilton et al.) (017) proposes to use a sampled neighborhood of node for message aggregation to efficiently generate node representations.
PRELIMINARIES
An undirected graph can be represented as G = E) which consists of the node set V with n nodes and the edge set ε. Each node v has a length-d feature T.. The adjacency matrix A E B2xx and the node feature matrix X E IR [gd are taken as the input for graph neural networks. Considering unweighted adjacency matrix A, if node and] j are connected, Aij 1, otherwise Arj = 0.
Traditional GNNs and Implicit GNNs
Traditional GNNs (Kipf and Welling 2016 Chen et al.
2020, Hamilton et al. 2017) have learnable aggregation process that iteratively propagates informa- tion from each node to its neighbor nodes. For each layer 1, the aggregation step can be defined as follows:
z = (( 20 +
(1)
where ( is the hidden states in layer I, is the normalized adjacency matrix; W(O and ( trainable weight matrices.
Similar to traditional GNNs, implicit GNNs (Gu et al. 2020 Liu et al. 2021 2022 Park et al. 2022)
also have an aggregation process but with tied wight matrices W and at each iteration step. The
aggregation process in implicit GNNs is generally defined as z(+1) d(W 2 (2X) at step I. Given such aggregation step, implicit GNNs solve the fixed-point equation Z 2'WZ' ΩX)
and obtain the equilibrium Z as node representations. To obtain the equilibrium, implicit GNNs usually require a large number of iterations of the equation until convergence, which may demand significant amount of time. For example, MGNNI (Liu et al. 2022) ensure the convergence by using damping factor y [0, 1) and define the aggregation follows:
((++) (0 f(X,9).
(2)
where s(W) projects the weight W into Frobenius norm ball of radius < 1 and ((X,9) is parameterized transformation. In contrast, IGNN (Gu et al. (020) enforces || S <p)p. with the Perron-Frobeius (PF) eigenvalue Aps (Berman and Plemmons 1994).
Mini-batch sampling for GNNs In general, batc- methods for GNNs need to compute the predictions for target nodes in each mini-batch. Previous mini-batch sampling methods for GNNs
3

---

Published as a conference paper at ICLR 2024
generally either sample auxiliary nodes of target nodes to form mini- (Hamilton al. 2017
Zeng et al.] (021) or directly sample subgraphs from the whole graph and use a subgraph as a mini-batch Chiang et al. 2019). For example, given a set of target nodes Vout. Shadow-GN (Zeng et al. 2021 constructs a set of auxiliary nodes Vauz by selecting nodes with top-k personalized PageRank (PPR) scores for each target node u Vegt- To obtain mini-batch, it forms subgraph
G. with node set V.- = Vege Vaue and train GNNs on this subgraph as if it is the full graph.
4 SCALABLE AND EFFECTIVE IMPLICIT GNNS
As mentioned in See ! previous implicit GNNs (Gu et al. 2020 Liu al. 2022 Park al. 2022)
usually use bath- training with an entire graph which involves recursively aggregating neighbors calculate fixed-point solutions for nodes. needs massive GPU memory and is not feasible for large graphs (e.g., with millions nodes) since full-batch training requires storing a whole graph and representations of all nodes. Moreover, these works usually cost lot of time for model training as they require a large number of iterations to solve a fixed-point equation.
Motivated by these limitations, we propose an implicit graph model SEIGNN which enables mini- batch training for implicit GNNs without harming the ability to capture long-range information and accelerates model training with new unbiased stochastic solver.
4.1 MINI-BATCH TRAINING
For traditional GNNs, there are several sampling techniques proposed to improve training efficiency such as Hamilton et al. (2017 Zeng et al. (202T); Chiang et al. (2019). However, these techniques cannot be directly used to train implicit GNNs without sacrificing the accuracy, since these sampling methods enforce implicit GNNs to lose long range dependency. To explain, these sampling- based mini-batch methods either sample neighbor nodes or a subgraph to form a training mini-batch. In this these methods inevitably prohibit information propagation between nodes of the current subgraph and nodes outside the subgraph. Therefore, directly using these methods can affect the advantage of implicit GNNs in capturing long-range dependencies. This is the reason why we cannot trivially use previous methods for implicit GNNs.
way, given
Graph with coarse nodes by graph paussniigg/parttioniie we propose use additional Subgraph coarse nodes representing different partitions to facilitate long- range information propagation for implicit GNNs with mini- batch training. First, we conduct graph partitioning to obtain partitions/subgraphs Ge, ..... which can represent the coarse information on the graph. For each partition, we create new coarse node Ve, to represent the partition 9s;- We construct two types of edges as follows:
To solve the above issue, inspired
Message passing via coarse nodes
Subgruph
Coarse-original edges: if node on the original graph E G also belongs the i-th partition, i... v Gs., an edge e (v, Ve,) connecting v and ve, is constructed.
Coarse-coarse edges: considering two different partitions G.. and G.,. if there exists at least one edge e E & connecting two different nodes a coarse-coarse edge connecting two corresponding coarse nodes Us. and Usy as (Va,, ).
Gs and Uj Gay. we construct
Coarse Node
Coarse-original Edge
Original Node
Coarse-coarse Edge
Figure 1: Illustrations of adding coarse nodes.
With coarse-original edges, coarse node can act summary of nodes in its partitions as all original nodes in this partition are its 1-hop neighbors. This can be treated as local information within each partition. Coarse coaree edges propagate the inter-partition information by passing the message contained in coarse node to another coarse node, which can facilitate long gaange information propagation between nodes from different partitions. In addition, coarse-coans edges also provide coarse-level graph connectivity information global information of the whole graph.
4

---

Published as a conference paper at ICLR 2024
Mini-batch training After constructing new graph with additional coarse nodes, existing mini- bini-batch sampling methods, such as Shadow-GNN (Zeg et al. 2021) or GraphSAGE (Hamilton et al. 2017), to construct mini-batches for training on subgraphs. To construct a mini-batch, we first randomly sample target nodes from the node set V, which means that we exclude coarse nodes from being target nodes. After that, to generate the prediction of each target node v, choose some nodes which are more relevant or important as auxiliary nodes. As in Zeng et al. (2021), we rely on Personalized PageRank (PPR) score, graph-strruttur-bbases metric, to determine the relevant/importan nodes with respect to a target node u. Specifically, we select the nodes with top-k PPR scores as auxiliary nodes of the current target node v. Combining all target nodes and their auxiliary nodes as a node set V., we obtain the subgraph Gsub with the corresponding edges connecting any two nodes in this node set.
In mini-batch with the subgraph Gsub, modifying the aggregation step in Eq 2 the fixed-point equation of our implicit GNNs can be re-written as:
Zgu :p( Zub X99) Zwu + s(X Isub);
where Sub and Xud are the adjacency matrix and node feature matrix with only nodes in Guub-
4.2 ACCELERATE TRAINING WITH NEW SOLVERS
To get the equilibrium of a fixed-point equation node representations, previous implicit GNNs usually use an original iterative solver which simply iterates the equation (Gu et al., 2020: Liu et al., get the equilibrium,
2022 Park et al.) 2022). However, it requires large number of iterations which costs massive time for training. In this section, we aim to reduce the training time by reducing the number of iterations with new solvers to approximate the equilibrium of the forward pass.
Neumann solver First, we show that we can approximate the equilibrium with the Neumann series As proven in Liu et al. 2021), the equilibrium of Eq can be obtained as follows:
lim vec (2)) = vec = (1 - 7/S @ g(W))) vec[f(X, (1000
(4)
Using the fact of the Neumann series (1 - T[S @ (()))) = Ex=o 1ST @ (()] and vectorization property, we can have:
vec [Z"]
* [St @ 9(W)]* (X)] = Σ x vec (o)
(5)
Then, removing the vectorization from both sides, the equilibrium can be obtained form of infinite sum:
z" y *d ((W)))(
(6)
To get the simplest approximation of the equilibrium, we can directly truncate the Neumann series at a certain step t and define ((t) as the approximation of the equilibrium:
(
r * (l(WW & Z
K=U
Stochastic solver However, directly truncating the Neumann series to get the approximated equi- librium with Eq 7 will incur errors that are not going to vanish as the forward pass biased. Therefore, we further propose new stochastic solver to get the approximated equilibrium 2*, We first truncate the series at step f as in Eq 7 and set the approximation Ž = v(t), At each following step é > f, sample Bernoulli random variable b, Bernoulli(a)), which means P(b: = 1) and P(b:- 0) 1 If b. 1, update the current approximation 2 with amplifying factor ato- as follows:
2 = (6-1)) (W)
(8)
Note that omit the subscript "sub" in equations hereafter for better clarity since the equations are applicable for both subgraph and whole graph.
5

---

obtain the unbiased approximation of the equilibrium as shown in Published as a conference paper at ICLR 2024
Algorithm I: The stochastic solver's procedure for the equilibrium.
Input: The subgraph G, the normalized adjacency matrix S, and the node features X. Output: The approximated equilibrium z
v Ex=o7 (Xx)))
20 = V(";
Define Bernoulli distribution Pa where Pall 1] and Pa lb 0] 0z i=t; L;;
Sample b; ~ Pai
while b, =116 do
i
2 2 + "
Sample by Pai
10 2 2();
return 2%
Otherwise if b, O, cease the process and obtain the final approximation ~ 2(,, The procedure our stochastic solver is illustrated in Algorithm [
Using the stochastic solver, the following proposition.
The proposed stochastic solver is an unbiased estimator of the equilibrium Z of the forward pass, i.e., the expectation of the approximated equilibrium 2- is the same as that of the true equilibrium Z*: [[ Z* (( under the condition that Exe Ex-+1> ((W)" f(X.)) a exists
Proposition 1.
Our stochastic solver is an unbiased stochastic solver which can have the same error with fewer iterations in expectation compared with our Neumann solver and the original iterative solver (Gu et al. 2020) used in existing implicit GNNs.
We provide the proof of this proposition in Appendix A.1
4.3 TRAINING OF SEIGNN
For model training, with subgraph in a mini-batch, we use our unbiased stochastic solver with Eq (8) to obtain the approximated equilibrium 2 for the forward pass. For backward pass, as shown in Liu et al. (2022) and Bai et al. (2019), implicit differentiation is used compute the gradients by directly differentiating through the equilibrium as:
ac = az-
Oi
(1-))(2²) -1 0,(2",X,99
0(-)
0(.)
where 2- = = x( is the fixed-point equation and J 0p(2",X.0) 82.
To avoid expensive
computation of calculating (I ((-))
we adopt a recently proposed phantom gradient esti- mation (Geng al. 2021) which has the advantages efficient computation and stable training dynamics. Therefore, with our unbiased stochastic solver and phantom gradient estimation, we can enjoy efficient computation for both forward and backward passes.
EXPERIMENTS
In this section, demonstrate the effeetiveness and efficiency of SEIGNN compared with both implicit GNNs and representative traditional GNNs on large graph datasets for the node classification task. Specifically, we conduct experiments commonly used datasets for node classification (i.e., Flickr, Yelp, Reddit, PPI, ogbn-arxiv, and ogbn- -gbnuutod We provide the descriptions and details of datasets in Appendix B.I
We discuss the case when this condition does hold in Appendix A.1

---

Published as a conference paper at ICLR 2024
Table I: Comparison on test accuracy micro Fl score on large graph datasets.
Model
Flickr
Reddit
Yelp
PPI
GCN Kipf and Welling 2016
49.2 + 0.3
93.
37.8 = 0.1
51.2
GraphSAGE (Hamilton et al. 2017
50.1 1.3
9.1
63.4 0.6
6..7
FastGCN (Chen et al.
2018
50,4
9.14
5.3
51.
ASGCN (Huang et al.
2018)
5..4
63.4 9.1
68.7 1.2
ClusterGCN Chiang et al. 2019
48.1
0.1
60,9 0.5
89.5 0.4
GraphSAINT (Zeng et
2020)
51.5
96.7
64.5 - 0.3
98.0 0.2
IGNN Gu et al.
2020)
$3.0
97.0
65.8 + 0.2
97.8 + 0.1
MGNNI Liu et
2022)
33.5
96.2 + 0.2
56.6 + 0.1
98.6 + 0.1
USP Li ct al.
2023)
54.3
96.8 + 0.2
66.1 = 0.2
98.5 = 0.2
SEIGNN
55.8 + 0.1
97.8 0.1
66.9 0.2
98.8 + 0.2
Table 2: Test Accuracy on OGBN datasets.
Table 3: Training time per epoch (second).
Model
oghn-arxiv
ogbn-produce
Model
Flickr
Reddit
ogbn-arxiv
IGNN
70.4 + 0.8
69.7 + 0.8
IGNN
7.68
141.12
8.51
MGNNI
71.2 0.4
OOM
MGNNI
9.29
60.95
4.04
USP
72.7 + 0.2
73.6 +: 0.3
USP
3.13
52.78
7.05
SEIGNN
77.9 + 0.2
76.4 + 0.2
SEIGNN
4.36
6.21
3.79
5.1 NODE CLASSIFICATION
Comparison popular large graphs We first use the various graph datasets with relatively large sizes (i.e., Flickr, Reddit, Yelp, PPI). Their scenarios vary from predicting communities of online posts (Reddit) to classifying protein functions (PPI).
The results are shown Table [ We can see that SEIGNN generally outperforms all other representa- tive baselines including both implicit GNNs and traditional GNNs on these four datasets. Compared with USP (Li et al.) 2023) which uses mini-batch training. SEIGNN achieves better performance by up to 1.5% absolute improvement. This can be attributed to the better ability of SEIGNN to capture global and long-range information by adding coarse nodes during training. IGNN and MGNNI, two implicit GNNs with full-batch training, generally perform worse than USP and SEIGNN, indicating that mini-batch training is more effective on large graphs in terms of performance. In addition, as MGNNI shares similar aggregation step SEIGNN, the worse performance of MGNNI compared with SEIGNN verifies the effectiveness of our designs of mini-batch training with the stochastic solver and coarse nodes.
Comparison on OGBN datasets Apart from four large graph datasets, to better examine scalability and effectiveness, also conduct experiments with two popular OGBN datasets (ogbn-arxiv and ogbn-products). Specifically, ogbn- gebnuuroducts is the largest dataset used in this paper, which contains around 2.5 million nodes and 61 million edges.
Table 2 shows the comparison of accuracies between SEIGNN and other implicit GNNs on OGBN datasets. SEIGNN still outperform other implicit GNNs by large margin. Specifically, SEIGNN achieves 5.1 % and 2.7% absolute accuracy improvements on ogbn-arxiv and ogbn-products re- spectively. In addition, we observe that MGNNI would face the out-of-memory (OOM) issue on ogbn-products as MGNNI has to load all nodes into GPU memory for full-batch training. This verifies again the limitation of using full-batch training in previous implicit GNNs.
Efficiency Comparison In addition to evaluating prediction accuracy, we also provide experimental results regarding the training efficiency of different implicit GNN models. Table aableBddemosstrate the comparison training time per epoch among different models. We can see that our model SEIGNN generally has less training time per epoch compared with existing implicit GNNs. Especially,
7

---

Published as a conference paper at ICLR 2024
2.3
230
2340
1568
HCRM
MCNM
MCNM
U57
D57
057
22g
2000
1200y
3050 193
Training (Seceda))
Tranding (Sacona))
Trshing Gacmng
(a) ogbn-arxin -axiv
(b) Flickr
(c) Reddit
Figure 2: Efficiency Comparison: Accuracy vs Training Time.
Table 4: Accuracy comparison: the effectiveness of using coarse nodes and the unbiased stochastic solver.
Table 5: Accuracy of different mini- batch methods.
Model
Reddit
Yelp
ogbn-arxiv
Method
ogbn-arxiv
SEIGNN (full version)
97.85
66.85
77.94
ClusterGCN
71.31
w/o coarse nodes
96.34
63.70
71.40
GraphSAGE
68.84
remove stochastic solver
97.51
66.65
77.24
SEIGNN
77.94
Reddit, SEIGNN only needs 6.21s for epoch, which is around 8x less compared with USP. Note that, although USP spends the least time training an epoch on Flickr which is relatively small, requires more time compared with SEIGNN other large datasets. This may indicate that USP is not efficient enough for relatively large and dense datasets (e.g., Reddit).
Moreover, for a more holistic view efficiency comparison, Figure we show how accuracy would change as training progresses for different models. First of all, our model SEIGNN achieves better eventual accuracies with less total training time compared with other implicit GNNs. Additionally, the accuracy of SEIGNN also increases much faster. These observations confirm the effectiveness and efficiency of our model on large graphs.
Besides the efficiency comparison, we also provide the comparison of memory usage in Table 9 of Appendix B33] showing that SEIGNN has significantly less GPU memory usage compared with other implicit GNNs. Lower memory usage leads to higher scalability of model.
5.2 ABLATION STUDY AND FURTHER EXPERIMENTAL INVESTIGATION
Besides the overall performance and efficiency comparison the above section, we also conduct detailed ablation studies and further investigations about the effectiveness of two key components in SEIGNN (i.c., mini-batch training with coarse nodes and the unbiased stochastic solver).
Effectiveness of using coarse nodes and the proposed solver Table 4 demonstrates the results of removing coarse nodes our designed mini-batch method and replacing the unbiased stochastic solver with the naive Neumann solver. It shows that, without adding coarse nodes in mini-batch training, the accuracies drop significantly, especially on Yelp and ogbn-arxiv. This confirms that adding coarse nodes is helpful for better global information propagation. By replacing unbiased stochastic solver with the naive Neumann solver, the performance also slightly decreases, which indicates the effectiveness of the unbiased stochastic solver.
Ineffectiveness of directly applying existing mini-batch methods In Section and 4.1 explain the reason that directly applying existing mini-batch methods for implicit GNNs may affect the performance. Table 5 empirically verifies the ineffectiveness of using existing mini-batch methods by illustrating that trivially using those methods (i.c., ClusterGCN (Chiang et al. 2019) and GraphSAGE with neighbor sampling (Hamilton al., 2017)) for implicit GNNs provides much worse performances compared to our mini- batch training method with coarse nodes.
8

---

Published as a conference paper at ICLR 2024
Table 6: Compatibility: using coarse nodes can improve other existing mini-batch methods.
Table Accuracy and Total Time (second) of dif- ferent solvers with different numbers of maximum iterations on ogbn-arxiv.
Method
Variant
Accuracy
our solver
original solver
w/o coarse nodes
71.31
ClusterGCN
Max iter.
3
5
10
50
w/ coarse nodes
76.21
Accuracy
77.94 7891
77.19
77.53
77.79
w/o coarse nodes
68.84
GraphSAGE
Total Time
15399
21748
45775
w/ coarse nodes
73.89
The improvements are higher for low-degree nodes. As the sig- nificant improvement by using coarse nodes is shown in Table 4 try provide more insights by further investigating how coarse nodes may specifically improve the performance. Considering nodes with different levels of degrees, we evenly split nodes into groups according to their degrees (Ist group contains nodes with the high- est level of degrees while the 5th group contains the lowest-degree nodes). Figure 3a shows the average accuracies of different degree groups by comparing the variants using/not using coarse nodes, and Figure 3b demonsttaates the relative improvement of degree groups through adding coarse nodes. We can see that I) nodes with lower degrees tend to have low accuracies for both two variants, and 2) accuracy improvements on nodes with lower degrees are more ob- vious compared with nodes with higher degrees. These observations suggest that our proposed mini- batch training with coarse nodes is more helpful on nodes with lower degrees. The reason might be that, by enhancing global/long-rang information propagation via coarse nodes, lew-degree nodes can receive sufficient information compared with the variant not adding coarse nodes.
0.85
coarse maDes
WDD coarse nodes
0.80
Accuracy
0.70
Degroa Group Index
(a) Accuracy comparison for
different degree groups.
7.0
65
Percentage
35
Degres Group
(b) Relative Improvement.
Additionally, we also investigate the compatibility of using coarse nodes for applying other sampling- based mini batch methods to SEIGNN. Table[]]shows that, on ogbn-arxiv, adding coarse nodes can also improve the performance of two existing mini-bated methods (i.e., ClusterGCN and GraphSAGE with neighbor sampling).
The effect of using coarse nodes for nodes with different levels of degrees on ogbn-arxiv.
Figure 3:
Efficiency comparison for different solvers Moreover, to verify the effectiveness of our stochastic solver, in Table 7 provide experimental comparison of accuracy and total time between solver and the original solver used in (Liu et al., 2022 Gu et al., 2020). We use different maximum for our solver with the continue probability a = 0.5. The results show that our solver can generally achieve better accuracy compared with the original solver while spending much less time. We also observe that the original solver needs more iterations (i.e., 50) to achieve a comparable accuracy as our solver, which leads to excessive time consumption.
iterations for the original solvers and set maximum iterations
6 CONCLUSION
In this paper, we propose a scalable and effective implicit GNN model (SEIGNN) that can be efficiently trained on large graphs. Specifically, SEIGNN contains mini-batch training method with added coarse nodes and an unbiased stochastic solver to scale up the model to large graphs without losing the ability to capture long-range information. The experiments on several large-graph datasets demonstrate that SEIGNN can achieve superior performance using less training time compared with existing implicit GNNs. Furthermore, the results of ablation studies verify the effectiveness of our mini-batch training method and the unbiased stochastic solver. We also try to provide a deeper analysis of why using coarse nodes in our mini-batch training can improve performance.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This research is supported by the Ministry of Education, Singapore, under its MOE AcRF TIER 3 Grant (NOE-MOET33002-001)) Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of the Ministry of Education, Singapore.
REFERENCES
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, 2019.
Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale deep equilibrium models. In Advances in Neural Information Processing Systems, 2020.
Abraham Berman and Robert Plemmons. Nonnegative matrices in the mathematical sciences. SIAM, 1994.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018. URL http:://peeeeeeeeeeeeeeoooovll/s
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, In International Conference on Machine Learning, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 257-266, 2019.
Zhengyang Geng, Xin- Yu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. In Advances in Neural Information Processing Systems, 2021.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. In Advances in Neural Information Processing Systems, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
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. Advances in neural information processing systems, 33:22115 222133,, 2020.
Wenbing Huang, Tong Zhang. Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph
representation learning, Advances neural information processing systems, 31, 2018.
Kenji Kawaguchi. On the theory of implicit deep learning: Global convergence with implicit layers. In International Conference on Learning Representations (ICLR), 2021.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International
Conference on Learning Representations (ICLR), 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
Mingjie Li, Yifei Wang, Yisen Wang, and Zhouchen Lin. Unbiased stochastic proximal solver for graph neural networks with equilibrium states. The Eleventh International Conference on Learning Representations, 2023. URL http::///oooecevwweeo/oooo/r/ass
10

---

Published as a conference paper at ICLR 2024
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and Xiaokui Xiao. Eignn: Efficient infinite-depth graph neural networks. In Advances in Neural Information Processing Systems, 2021.
Juncheng Liu, Bryan Hooi, Kenji Kawaguchi, and Xiaokui Xiao. Mgnni: networks with implicit layers. Advances in Neural Information Processing Systems, 35:21358- 21370, 2022.
Multiscale graph neural
Junyoung Park, Jinhyun Choo, and Jinkyoo Park. Convergent graph solvers. In International Conference on Learning Representations, 2022.
Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection in a point cloud. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pages 1711-1719, 2020.
Aravind Subramanian, Pablo Tamayo. Vamsi K Mootha, Sayan Mukherjee, Benjamin L Ebert, Michael A Gillette, Amanda Paulovich, Scott Pomeroy, Todd R Golub, Eric S Lander, et al. Gene set enrichment analysis: knowledge-baid approach for interpreting gedo expression profiles. Proceedings of the National Academy of Sciences, 2005.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
Fangping Wan, Lixiang Hong, An Xiao, Tao Jiang, and Jianyang Zeng. Neodti: neural integration of neighbor information from heterogeneous network for discovering new drug- targettrgett interactions. Bioinformatics, 35(1):104-111, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020. URL
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34: 19665-999777, 2021.
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 Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pages 688, 2020.
11

---

Published as a conference paper at ICLR 2024
Appendices
A PROOFS
A.1 PROOF OF PROPOSITION 1
Proof. We first define S, {0, 1} random variable, indicating whether sample the i-th term or not. By the property of probability, we can decompose the marginal P(S, = 1| by
P(S: 1) P(S: 1|5 1] P[S 1] + P(S: 1| = 0] P(S.. 0]. Here, P[S: 1|5 0] in our algorithm because we terminate the iteration if S 0. Thus,
P(S: 1| P(S: 1|5;-1 P[S, = 1].
Moreover, as the random variable S; is sampled from a Bernoulli distribution Bernoulli(a). we have P(S: 1|5 1] our algorithm. Plugging this into the above.
P[s: = 1] = aP(S:-1 = 1].
Recursively applying this equation,
P[S: = a' PPSS 1].
Since P(S; 1] = 1 for all i 5 in our algorithm, we have
P[S 1] a
Considering the possibility of reaching step i, the forward pass of our algorithm can be written as:
20
200
7*t 1( = 1]
(()) ((x 9)x,
a(k-t)
k=t+1
where 1(S 1} take the value when Sp 1 (i.e., the algorithm reaches step k), otherwise takes the value 0.
As we continue the algorithm until the termination (i.e., S. 0). we can write the approximated equilibrium as follows:
k 11 =
-01
a(k-1) x
k=
By taking the expectation of the second term, with the definition A, -' and the
condition that > 2k As A exists, we have the following:
T00
LIS 13
11SA = 1] A
a(k-t) ( = E
ak-t
Lk=++1
1=H+1
11Sx = 13 ab-t
A&E
k=
P(Sk =
A
k-t
k=1+1
Σ
A
Σ
* (()
k=t+1
k=t+1
12

---

Published as a conference paper at ICLR 2024
Combining the above expectation of the second term with the deterministic term 2 Ei=o (9(W)" g) get obtain the expectation E[ follows:
1(xx = axk-t)
E|2^| 200 E
9(W)xx5*
R=1+1
Σ k=1+1
(9(W)"((X,9)
*9(W)* = Z"
This indicates that our proposed stochastic solver is an unbiased estimator of the equilibrium 2
In the above proof, we have an assumption that Ex A& a exists. In the case where E A - does not exist, we define fn to be the output of a modified version of the Al- gorithm Thheee we replace the while-loop with the for-loop up step: i.c., we forceful terminate the while-loop if takes more than steps. Then, by using the same proof steps except that we replace the infinite sum with the finite sum upto n terms, we conclude that for any n, E[fn] = Ex Ak- This implies that our proposed stochastic solver is still an unbiased estimator of the equilibrium Z" of the forward pass up to the error Ex.n Ag- For any desired error value machine precision), there exists a sufficiently large n such that Σkzn A S c. Thus, the statement in Proposition still holds true up the machine precision without the condition that _k= Ak ク exists. The output of our algorithm is equivalent to fn with = co. Thus, it is ensured to be unbiased.
0 (including
B
MORE ON EXPERIMENTS
B. DATASET STATISTICS AND DESCRIPTIONS
The dataset statistics are provided in Table 8 ogbn-products is the largest dataset used in our paper, which contains around 25 million nodes and million edges. Reddit is the densest dataset here with the average node degrees as 50. We follow Li et al. (2023) to use six datasets in our experiments. We provide a detailed description of each dataset as follows:
Flickr is single-label multi-class classification dataset. The task is to categorize types of images based on the descriptions and common properties of online images. We are using the Flickr dataset provided in Zeng et al. (2020). Flickr data collected in the SNAP website P from different sources. Flickr contains an undirected graph and a node in the graph represents an image on Flickr. An edge is connected between two nodes properties (e.g., the same gallery, comments from the same user, etc.). The node features are the 500-dimensional bag-of-word representations of the images. For labels, each image belongs to one of the 7 classes.
corresponding images share some common
Reddit is a single-label multi-clan class classification dataset. The task is to predict different com- munities of online posts. We use the Reddit dataset from Hamilton et al. (2017) in Li al.) (2023). The nodes are online posts and an edge is connected between two posts if the same user comments on both. Word features in posts are 300-dimensional word vectors. Node features concatenated using 1) the average embedding of the post title, 2) the average embedding of all the post's comments, 3) the post's 's score, the number of comments on the post.
Yelp is multi-label multi-class classification dataset. The task is categorize types of businesses based on users and friendships. We use the Yelp dataset provided in Zeng et al. (2020). Yelp contains single graph. The nodes users who provide reviews. If two users friends, edge between them connected. The features of each node are added and normalized using several 300-dimensional vectors representing a review word provided by the user.
13

---

Published as a conference paper at ICLR 2024
Table Dataset statisties.
Dataset
Nodes
Edges
Avg. Degree
Classes
Features
Train/Val/
Flickr
89,250
899,756
10
500
0.50/0.25/0.22
Reddit
232,965
11,606,919
50
41
602
0.66/0. 10/0.24
Yelp 716,847
6,977,410
10
100
300
0.75/0. 10/0.
PPI 14,755
225,270
14
121
50
0.79/0. 1/0.10
ogbn-arxiv 169,343
1,166,243
40
128
0.54/0. 18/0.9
2,449.029
61,859,140
25
100
47
0.10/0.02/0.88
PPI is single-lahel multi-class classification dataset that contains multiple graphs. The task is to classify protein functions based on the interactions of human tissues. PPI dataset has 24 graphs in total and each graph represents a different human tissue. In graph, nodes represent proteins and edges indicate interactions between proteins. Each node can have up to 121 labels, which are originally collected from Molecular Signatures dataset (Subramanian
al.] (0055 by Hamilton et al. (2017). The dataset splits used in paper are the same as in Hamilton et al. (201)) i.e., 20 graphs for training, graphs for validation, and graphs for testing.
ogbn-arxiv is single-label classification dataset that contains directed graph. The task is to predict the 40 subject areas of arXiv CS papers, such as cs.Al, cs.LG, and cs.OS, which are manually labeled by the authors of the paper and the moderators. each node is arXiv paper and each directed edge indicates that one paper cites another one. The node feature of each node is 228-dimensional vector obtained by averaging the embeddings of words the title and abstract. We download ogbn-arxiv arxiv dataset from the OGB website The detailed descriptions can be found Hu al. (2020).
oghn- products is single-label multi-class classification dataset which contains undirected and unweighted graph. Nodes represent products sold on Amazon, and edges between two products indicate that these two products are purchased together. Node features are generated by extracting bag-of-worde features from the description of the product followed by Principal Component Analysis to reduce the dimension to 100. We download website E
dataset from the OGB The detailed descriptions can be found in Hu et al. (2020).
B.2 EXPERIMENTAL SETTING
For experimental setup, mainly follow Li et al. 2023). As use the same experimental setting on some datasets, we reuse the results of some baselines from Li et al. (202)) and Zeng et al. (2020). We compare SEIGNN with implicit GNNs (i.e., USP (Li et al.) 2023), MGNNI (Liu et al. 2022), and IGNN (Gu et al.] (2020) and 6 explicit/radiiionaa GNNs (GCN (Kipf and Welling 2016 GraphSAGE (Hamilton al. 2017), FastGCN (Chen et al., 2018). ASGCN (Huang et al., 2018). ClusterGCN (Chiang et al. 2019), and GraphSAINT (Zeng al. 2020)). The experiments are run with different trials. The averaged accuracy and standard deviation are reported. We mainly run the experiments RTX-A5000 GPU with 24GB GPU memory.
Model Architecture and Hyperparameters For SEIGNN, we use the same structure with a few implicit graph layers and the same number of linear layers in MGNNI (Liu et al. 2022) and USP (Li et al. 2023). We select the number implicit graph layers from (2, 3, 4). We also conduct a hyperparameter search learning rate (0.01, 0.005. 0.001) and dropout rate (0.0, 0.2, 0.5). The number of deterministic steps in our stochastic solver is chosen from (3, 5) and the continuation probability
0.5. The hyperparameter y used an implicit graph layer set to 0.8. The Adam optimizer (Kingma and Ba, 2015) is used for optimization. The number of partitions for adding coarse nodes our mini-batch training method is selected from (50, 100, 200). The number of target nodes in mini-batch is configured as follows: 8192 for Flickr and PPI, 10240 for ogbn-arxiv, Yelp. and Reddit, and 16384 for aebnn-poddcct
14

---

Published as a conference paper at ICLR 2024
Table 9: GPU Memory Usage (GB) of different models. OOM indicates Out-of-Memory.
2-layer MGNNI
3-layer MGNNI
SEIGNN
IGNN
SEIGNN
IGNN
Reddit
7.23
23.77
18.67
8.41
OOM
22.21
Yelp
5.82
15.96
13.65
7.27
20.72
17.34
ogbn-products
9.21
OOM
OOM
9.78
OOM
OOM
B.3 ADDITIONAL EXPERIMENTAL RESULTS
Besides the overall comparison of accuracy and efficiency, also investigate the memory usage of different implicit GNNs. Table 9 shows that SEIGNN requires significantly less GPU memory compared with IGNN and MGNNI. In particular, SEIGNN only uses 37% of the memory as IGNN with 3 implicit layers Reddit. Moreover, we can see that SEIGNN cost less than 10GB GPU memory on oghn- agbn-productt while MGNNI and IGNN face the out-of-memory issue using a GPU with 24GB memory.
15


Reviews:
[{"review_id": "yBib9UDh8F", "reviewer": "Reviewer_Jpev", "summary": "The authors identify 2 problems with mini-batching implicit GNNs:\n\n1) The traditional minibatches formed for GNN training is often done through sampling which ignores long-range dependency nodes.\n\n2) Implicit GNNs take a long time to converge, hurting scalability.\n\nThe authors propose 2 solutions to said problems.\n\n1) The authors propose adding coarse nodes between minibatch subgraphs to facilitate long-range message propagation during training (when combined with standard techniques like GraphSAGE)\n\n2) The authors extend Neumann series, a implicit GNN solver proposed in [1], by making it a unbiased stochastic solver.\n\nThe authors provide experiments and ablations to show their minibatch sampling method is superior to existing works.\n\n[1] Eignn: Efficient infinite-depth graph neural networks", "questions": "In addition to the weaknesses section, I have a few more questions:\n\n- Have you considered adding multiple coarse nodes in between mini-batch subgraphs? What would be the effect of this?\n\n- What would be the effect of removing/keeping the coarse nodes post-training?\n\n- Why is the stochastic solver slightly better in performance than the Neumann solver in Table 4 of the ablation studies? Is the Neumann solver a truncated version here?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors provide a compelling argument that their augmentations to mini-batch sampling and implicit GNN solving can improve the scalability of implicit GNNs. \n\n- The authors identified a compelling issue with existing mini-batch approaches.\n\n- The solutions the authors provide are simple, yet intuitive. \n\n- The paper is written clearly and is easy to follow.\n\n- The authors provide timing experiments to empirically verify SEIGNN's scalability.\n\n- The authors try various different minibatch methods with the coarse nodes.\n\n- The method is targeted towards implicit GNNs, which is a subset of all possible GNNs (though the authors demonstrate the method generalizes to other GNNs)", "weaknesses": "To be fully convinced, I have a few more questions regarding the approach:\n\n- [important] On datasets where full-batch training is available, what is the performance trade-off of using SEIGNN over the full implicit GNN and a naive subsampling of the full-batch?\n\n- How does modifying the sizes of the minibatch subgraphs affect the efficacy of SEIGNN's coarse nodes?\n\n- How important is using PPR for the coarse node idea? Could SEIGNN generalize to other importance metrics?\n\n- The method is targeted towards implicit GNNs, which is a subset of all possible GNNs (though the authors demonstrate the method generalizes to other GNNs)", "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": "", "extra_scores": {}}, {"review_id": "jGKKqItFHf", "reviewer": "Reviewer_4DC8", "summary": "This paper proposes a scalable and effective implicit GNN (SEIGNN) with a mini-batch training method. Experiments demonstrate SEIGNN outperforms the state-of-the-art implicit GNNs on various large graphs.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. SEIGNN is fast and memory-efficient.\n2. The accuracy of SEIGNN on the large datasets is significantly higher than the state-of-the-art implicit GNNs.", "weaknesses": "My major concern is the reproducibility of this paper.\n\n1. Table 4 shows that the improvement of SEIGNN is due to the coarse nodes. However, the authors do not analyze why the coarse nodes improve the prediction performance.\n2. The authors do not provide the codes for reproducibility.", "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": "", "extra_scores": {}}, {"review_id": "Rb8xWTSEU3", "reviewer": "Reviewer_K2Aq", "summary": "The paper proposes a scalable and effective implicit graph neural network (GNN) model, called SEIGNN, that can handle large graph data. Implicit GNNs are models that can capture long-range dependencies in graphs by solving a fixed-point equation. However, they are computationally expensive and memory-intensive, due to their use of full-batch training and a large number of iterations. SEIGNN addresses these limitations by using a mini-batch training method with coarse nodes and a stochastic solver. The coarse nodes are added to the mini-batch to incorporate global information from the graph, and the stochastic solver is used to obtain unbiased approximate solutions with fewer iterations. SEIGNN can be integrated with any existing implicit GNN model to improve its performance. The paper evaluates SEIGNN on six datasets and shows that it achieves better accuracy with less training time than existing implicit GNNs.", "questions": "Please kindly refer to the Weaknesses.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper tackles a novel and important problem of scaling up implicit GNNs to large graphs, which has applications in real-world massive graphs.\n* The authors introduce a mini-batch sampling strategy that can preserve the global and long-range information of the graph by using coarse nodes and can achieve reduced training time by using a stochastic solver.\n* Extensive experiments and analysis are conducted to demonstrate the advantages of the proposed framework in mini-batch training.", "weaknesses": "* The paper fails to position itself with recent related works. More SOTA papers in mini-batch training strategy should be included for discussion, such as [1-3]. The idea of introducing coarse nodes during the process of mini-batching is relatively straightforward and appears in existing literature such as [3]. Therefore, it hurts the novelty of this work regarding the first contribution without a thorough comparison with the current mini-batching GNN methods that also include coarse nodes. Meanwhile, there is a very relevant and similar work that should be added for comparison [4].\n\n* For the second contribution of accelerated training with the Neumann solver, it is unclear how the authors constrain $n$ to be sufficiently large during experiments. In other words, does the performance of SEIGNN be affected even if the proposed stochastic solver is not an unbiased estimator? Could the authors elaborate more on this? \n\n* The setting of the experiments could be improved to better reflect the contributions. Do the results for all implicit GNNs come from full-batch training on all benchmarks? What would performance be if we incorporated different mini-batching sampling strategies for the baseline implicit GNNs? Meanwhile, more recent baselines of scalable GNN should be added for comparison such as [5-6].\n\n* This manuscript aims to scale implicit GNNs to large graphs, but the benchmarks have nearly become standard for even some GNNs that are not specifically designed for scalability. Therefore, large graphs such as ogbn-papers100M should be evaluated for the scalability aim. Note that even the largest dataset (ogbn-products) used in this manuscript is marked as medium in OGB benchmarks.\n\n[1] VQ-GNN: A Universal Framework to Scale-up Graph Neural Networks using Vector Quantization, NeurIPS 2021\n\n[2] Influence-Based Mini-Batching for Graph Neural Networks, LoG 2022\n\n[3] SMGRL: Scalable Multi-resolution Graph Representation Learning, arXiv 2022\n\n[4] Efficient and Scalable Implicit Graph Neural Networks with Virtual Equilibrium, Big Data 2022\n\n[5] Decoupling the Depth and Scope of Graph Neural Networks, NeurIPS 2021\n\n[6] Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity, NeurIPS 2022", "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": "", "extra_scores": {}}, {"review_id": "SDQVdDMMZw", "reviewer": "Reviewer_m8F2", "summary": "This work aims to address the scalability and efficiency challenges associated with implicit Graph Neural Networks (GNNs), which are designed to capture long-range dependencies in graph-structured data. It first points out that the implicit GNNs are suffering from the computational burden brought by (1) full-batch training and (2) a large number of iterations to solve fixed-point equations, limiting their applicability to large graphs. This work proposes a scalable and effective SEIGNN model that employs mini-batch training with coarse-level nodes to encourage information propagation between subgraphs. Extensive experiments are conducted to justify the power of SEIGNN in terms of both efficiency and efficacy.", "questions": "1. I agree that subgraph-wise sampling (ClusterGCN) and node-wise sampling (GraphSage) indeed lead to a loss of long-range dependencies. However, how about layer-wise sampling, such as the approaches like LADIES[1] and fastGCN[2]? \n\n2. I want to confirm my understanding. In subgraph sampling, the coarse nodes are excluded from being the target nodes but will be included in the sampled subgraph through the top-k Personalized PageRank (PPR) selection step, is that correct?\n\n3. Given that the purpose of introducing the coarse nodes is to maintain long-term dependencies in mini-batch training, can SEIGNN ensure that coarse nodes are included in each mini-batch? Or is there a way to encourage the sampled subgraph to include more coarse nodes?\n\n\n[1] https://arxiv.org/abs/1911.07323\n[2] https://arxiv.org/abs/1801.10247", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This work is clearly motivated, addressing the scalability issue of IGNN is an important problem.\n\n2. Good performance and comprehensive ablation study.\n\n3. Writing is clear and easy to follow.", "weaknesses": "Please refer to ``Questions``.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)