EIGNN: Efficient Infinite-Depth Graph Neural Networks
Authors: Juncheng Liu
Kenji Kawaguchi
Bryan Hooi
Yiwei Wang
Xiaokui Xiao
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
long-range dependencies
graph representation learning
implicit model
implicit deep learning

Abstract: Graph neural networks (GNNs) are widely used for modelling graph-structured data in numerous applications. However, with their inherently finite aggregation layers, existing GNN models may not be able to effectively capture long-range dependencies in the underlying graphs. Motivated by this limitation, we propose a GNN model with infinite depth, which we call Efficient Infinite-Depth Graph Neural Networks (EIGNN), to efficiently capture very long-range dependencies. We theoretically derive a closed-form solution of EIGNN which makes training an infinite-depth GNN model tractable. We then further show that we can achieve more efficient computation for training EIGNN by using eigendecomposition. The empirical results of comprehensive experiments on synthetic and real-world datasets show that EIGNN has a better ability to capture long-range dependencies than recent baselines, and consistently achieves state-of-the-art performance. Furthermore, we show that our model is also more robust against both noise and adversarial perturbations on node features.

EIGNN: Efficient Infinite-eppth Graph Neural Networks
Juncheng Liu Kenji Kawaguchi Bryan Hooi Yiwei Wang
Xiaokui Xiao
National University of Singapore (juncheng, kenji, bhooi] @comp nus edu. 8g Sannyw_seuufee oxmail. com, xkxiaoθnus, edu.
Abstract
Graph neural networks (GNNs) are widely used for modelling graph-structure data numerous applications. However, with their inherently finite aggregation layers, existing GNN models may not be able to effectively capture long-range dependencies the underlying graphs. Motivated by this limitation, we propose GNN model with infinite depth, which we call Efficient Infinite-Depth Graph Neural Networks (EIGNN), to efficiently capture very long-range dependencies. We theoretically derive a closed-fom solution of EIGNN which makes training an infinite-depth GNN model tractable. We then further show that we can achieve more efficient computation for training EIGNN by using eigendecomposition. The empirical results of comprehensive experiments on synthetic and real-world datasets show that EIGNN has better ability capture long range dependen- cies than recent baselines, and consistently achieves state-of- the-art performance. Furthermore, show that model is also more robust against both noise and adversarial perturbations on node features.
Introduction
Graph-structured data ubiquitous in the real world. To model and learn from such data, graph rep- resentation learning aims to produce meaningful node representations by simultaneously considering the graph topology and node attributes. It has attracted growing interest in recent years, as well as numerous real-world applications
[32
widely used approach for node, edge, and graph prediction tasks. Recently, many GNN models have been proposed (e.g., graph convolutional network [14, graph attention network 126), simple graph convolution 30]). Most modern GNN models follow 'message passing" scheme: they iteratively aggregate the hidden representations of every node with those of the adjacent nodes generate hidden representations, where each iteration is parameterized as a neural network layer with learnable weights.
In particular, graph neural networks (GNNs)
Despite the success existing GNN models achieve many different scenarios, they lack the ability to capture long-range dependencies. Specifically, for predefined number of layers T, these models cannot capture dependencies with range longer than Thhops away from any given node. A straightforward strategy to capture long-range dependencies is to stack a large number of GNN layers for receiving "messages" from distant nodes. However, existing work has observed poor empirical performance when stacking more than a few layers [6]. which has been referred to as oversmoothing This has been attributed to various reasons, including node representations becoming indistinguishable as depth increases. Besides oversmoothing. GNN models with numerous layers require excessive computational cost in practice since they need to repeatedly propagate representations across many layers. For these two reasons, simply stacking many layers for GNNs is not a suitable way to capture long-range dependencies.
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

Recently, instead of stacking many layers, several works have been proposed to capture long-range dependencies in graphs. Pei et al. |21 propose global graph method Geom-GCN which builds structural neighborhoods based on the graph and the embedding space, and uses a bi-level aggregation to capture long-range dependencies. However, as Geom-GCY still only has finite layers, still fails to capture very long range dependencies.
To model longer range dependencies, Gu al. T0 propose the implicit graph neural network (IGNN), which can be considered as a GNN model with infinite layers. Thus, IGNN does not suffer from any a priori limitation on the range of information it can capture. To achieve this, IGNN generates predictions as the solution to fixed-point equilibrium equation. Specifically, the solution is obtained by an iterative solver. Moreover, they require additional conditions to ensure rell-posedness of the model and use projected gradient descent method to train the model. However, the practical limitations of iterative solvers are widely recognized: they can lack robustness; the generated solution is approximated; and the number of iterations cannot be known in advance [23]. In our experiments,
we found that IGNN sometimes experiences non-convergence in its iterative solver. Besides the non-convergence issue, the iterative solver of IGNN can be inefficient as IGNN needs to run it once per forward or backward pass.
Motivated by these limitations, we propose our Efficient Infinite-Depth Graph Neural Network (EIGNN) approach, which can effectively capture very long range dependencies in graphs. Instead of relying on iterative solvers to generate the solution like in IGNN [10], we derive a closed-fom solution for EIGNN without additional conditions, avoiding the need for projected gradient descent to train the model. Furthermore, we propose to use eigendecompposiion to improve the efficiency of EIGNN, without affecting its accuracy.
The contributions of this work are summarized as follows:
To capture long-range dependencies, we propose our infinite-depth EIGNN model. To do this, we first define our model as the limit of an infinite sequence of graph convolutions, and theoretically prove its convergence. Then, we derive tractable forward and backward computations for EIGNN.
We then further derive an eigendecomppsstion--aaad approach to improve the computa- tional/memory complexity of our approach, without affecting accuracy.
We empirically compare our model recent baseline GNN models on synthetic and real-world graph datasets. The results show that EIGNN has better ability to capture very long range dependencies and provides better performance compared with other baselines. Moreover, the empirical results of noise sensitivity experiments demonstrate that EIGNN is more robust against both noise and adversarial perturbations.
Paper outline In Section 2 we provide an overview GNNs, implicit models, and the oversmooth- ing problem. Section SatiionBnittten introduces the background and major mathematics symbols used in this paper. In Section we first present the EIGNN model and discuss how to train this infinitely deep model in practice. In addition, we show that with eigendecomposition we can reduce the complexity and achieve more efficient computation for EIGNN. In Section we empirically compare EIGNN with other representative GNN methods.
2 Related work
Graph neural network models GNN models have been successfully used various graph related
tasks 2
27 28. Pioneered by Graph Convolutional Networks (GCNs) [4], many convolutional
GNN models attention 2 skip connection 33 They only have a finite number of aggregation layers, which makes them unable to capture long-range dependencies. Recurrent GNN models [24] 17
20
use different aggregation schemes and components (c.g..
generally share the same parameters in each aggregation step and potentially allow infinite steps until convergence. However, as pointed out in Gu et al. [TO, their sophisticated training process and conservative convergence conditions limit the use of these previous methods in practice. Recently, Gu et al. [TO proposes an implicit graph neural network (IGNN) with infinite depth. IGNN uses an iterative solver for forward and backward computations, and requires additional conditions to ensure the convergence of the iterative method. With infinite depth, they aim to capture very long range dependencies on graphs. Another global method Geom-GCN 21 is also proposed for capturing

---

long-range dependencies using structural neighborhoods based on the graph and the embedding space. However, as Geom-GCN only has finite layers, fails to capture very long range dependencies.
Implicit models Implicit networks use implicit hidden layers which are defined through equilib- rium point an infinite sequence of computation. This makes an implicit network equivalent to feedforward network with infinite depth. Several works [ 12555 7 show the potential advantages of implicit models on many applications, e.g., language modeling, image classification, and semantic segmentation. Besides practical upplications, Kawaguchi [ provides theoretical analysis on the global convergence deep implicit linear models.
Oversmoothing For capturing long-range dependencies, straightforward method is stack more GCN layers. However, Li et al. [16] found that stacking many layers make the learned node representations indistinguishable, which is named the oversmoothing phenomenon. To mitigate oversmoothing and allow for deeper GNN models. several empirical and theoretical works [16 [5 4 35 IV have been proposed. However, these models still cannot effectively capture long-range dependencies, as shown in our empirical experiments (see Section
3 Preliminaries
Let G = (V,E) be an undirected graph with node set V and edge set E, where the number of nodes = n In practice, a graph 9 can represented as its adjacency matrix A E _g=x and its node feature matrix X E _@mx where the feature vector of node is x; E RT In node classification task, given graph data (g, X), graph models are required produce the prediction yi for node i match the true label y/-
Simple graph convolution
The Simple Graph Convolution (SGC) was recently proposed by Wu et al. 30 The pre-softmax output of SGC of depth H can be written as:
Tsac(X, W) W S ",
where X E Rexx is the node feature matrix, S = II S E R is the product of H normalized adjacency matrix with added self-loops S E " and W E Im weight parameters. After the graph convolution, the softmax operation applied obtain the prediction ý.
xm is the matrix of the trainable
Notation We use @ to represent Kronecker product. o is used to represent element- wise product between two matrices with the same shape. For a matrix V E H by stacking all columns, can get vec[V] E Ray as the vectorized form V. The Frobenius norm of denoted as denotes the 2-norm. We use I,, represent the identity matrix with size n X
||V|| |[V]2
4 Efficient Infinite-Depth Graph Neural Networks
To capture long-range dependencies, propose Efficient Infinite-Depth Graph Neural Networks (EIGNN), The pre-softmax output of EIGNN is defined as:
f(X,F,B) = lim Z X.F
(2)
11-000
where F E mm and B E R represent the trainable weight parameters, and z the output of the Hith hidden layer:
(H))
7 ())
(3)
where we are given an arbitrary 7 E (0, 1] and
1
g(F) | F F
FTF
with arbitrary small eF > 0.
3

---

Note that g(F) is constrained by Equation to lie within Frobenius norm ball of radius < 1, which prevents divergence of the infinite sequence. EIGNN extends SGC an infinite depth model with learnable propagation while additionally adding skip connections. By the designs, EIGNN have several helpful properties: 1) residual connection, which also used in finite-depth GNN models (e.g., APPNP 15 and GCNII 4 and has shown its importance in graph learning: 2) learnable weights for propagation on graphs (i.c., g(F)). In contrast, APPNP 15I only directly propagates information without learnable weights.
As EIGNN is model with infinite depth, how to conduct forward and backward computation for training is not obvious. In the rest of this section, we first show how to perform forward and backward computation for EIGNN. Then we propose to use eigendecomposition to improve the efficiency of this computation.
4.1 Forward and backward computation
At first glance, it may seem that cannot compute the infinite sequence of (Z()), without iterative solvers in practice. However, in Proposition 1 we show that the infinite sequence of (2()), is guaranteed to converge and computable without iterative solvers.
Proposition 1. Given any matrix X, F and normalized symmetric adjacency matrix S, the infinite ) is convergent and the limit of the sequence can be written as follows:
sequence of (Z()))
lim vec| [+) = (I - --s @ g(F))) vec[X]. H
(5)
This can be proved by using the triangle inequality of norm and some properties of the Kronecker product. The complete proof can be found in Appendix B.T
Computing F(X, B) After getting the limit of the sequence, we can conduct forward compu- tation without iterative solvers as shown in Proposition 2 contrast, IGNN [TO] heavily relies on iterative solvers for both forward and backward computation. The motivation to avoid iterative solvers that iterative solvers suffer from some commonly known issues, e.g., approximated solutions and sensitive convergence criteria 23
Proposition 2. Given any matrices X, F and normalized symmetric adjacency matrix S, with an
can be obtained arbitrary y E (0, 1] and an arbitrary small eF > 0, f(X, F, B) of Equation (
without iterative solvers:
vecl vecl[(X, F, B)] vec B lim (1
x = [Tn s B] (I - > s (F))) vec[X].
(6)
Proof. Combining Equation 5 with the property of the vectorization (i.e., vec[AB] = (J x A) vec|BB), Equation O can be obtained.
Computing Allim -oo vecl2 I.
In Proposition we show that backward computation can be done without iterative solvers as well. Without iterative solvers in both forward and backward computation, avoid the issue that the solution of iterative methods is not exact. Specifically, in IGNN [TC. the forward computation can yield an error through the iterative solver and the backward pass with the iterative solver can amplify the error from the forward computation. The approximation errors can lead to degradation performance, which we can avoid in our method.
d Fl
Proposition 3. Given any matrices X, F and normalized symmetric adjacency matrix S, assuming
an arbitrary & E (0, and an arbitrary small & > 0, the gradient a(lim -oo vecl2 (. computed without iterative solver:
can be
[vec[F]
A(lim vecl iz x.Fl)
-U-1
s
lim
X 1m
i veelgl veolg(F))
[ve[[F] where U = -11-7888 g(F) and the limit can be computed by
11-000
a vec[[
lim veel veclz X.P. = U-1 vec[X].
#1500
The proof of Proposition is strongly related to the implicit function theorem. See Appendix B.2 for the complete proof.

---

Computing the gradients of objective functions With the gradients of the infinite sequence, the gradients objective functions can be obtained. Define the objective function be minimized by:
L(B,F) F) F,,
Here, ey is an arbitrary differentiable function; for example, it can be set to the cross-entropy loss or square loss with the label matrix Y """"" Let fx,F,8 F, and Zx,r r
l x Then using the chain rule with Equation we have
FL(B,F)
(fx,F))).B) [I & BBU [SZX,F & Im] vec vevcffx [x,F,B)
θ vvelg((F))
a [ec =
ô vec F]
and
@L F)
Jly (fx,F,
X X Lmyh
i vec [ ① vec vec[[xxFF.n]
where Zx.F= (I 7[S @ g (F)))) vec[X]. The full derivation of Equation and
9 can be found
in Appendix B33
4.2 More efficient computation via eigendecomposition
In the previous subsection, we show that even with the infinite depth of EIGNN, forward and backward computations can be conducted without iterative solvers. However, this requires us to >[S
calculate and store the matrix U I @ ( of memory consumption. For example, when m = 100, 1000, the memory requirement of U becomes around 40 GB which usually cannot be handled by a commodity GPU. this subsection, we show that we can achieve more efficient computation via eigendecompoostton. We avoid the matrix U by using eigendecomposition of much smaller matrices g = QrArQF E mm and Q E Raxx separately. Therefore, we reduce the memory complexity from an mn X mn matrix to two matrices with sizes m X m and n X respectively. We first define G' E mxxx where G; 1/(1 (ApAA)))) The output of EIGNN and the gradient with respect F can be computed as follows:
m which can be expensive in terms
f(X,F,B) = BQr(Go (Q]x0))))
(10)
(
(Occl((F)) @ve[[F]
vec QF (Go QTBBBT Oly (fx,F.B) Qs)
(EE Qs)
vocc| (B,F) =2
Q
SZx,F
Ofx.F.B
(11)
where Zx.F Qr(G o (QTx E Rmxx, The complete derivations of Equation I0 and are presented Appendix B.4
Further improvements via avoiding 0 (er As shown Equation TO and vec[F
we can avoid
8 [e) vee in
the mn X mn matrix, but this still requires us to deal with the mm x mm matrix
Equation We show that we can further avoid this as well. Therefore, the memory complexity for the computation of the gradient with respect to F reduces from (m to O(n²) if > m, or O(m²) otherwise.
2 2 F, FT
V LFL(B.F)
Y
F (R+RT)
FTF
E mmm
FT FILE C
OF
FT
F
F
(12)
where
Go (OT.ET (by(fx.EB) Qs)
R= == QF (Go
Q QJSZK, E mm
0xx
Appendix B.5 shows the full derivation of Equation calculated by modern autograd frameworks (c.g.. PyTorch 20 For the gradient V (BL(B, F), can be directly obtained by applying chain rule with 06y (fx.F.mm since B is not within the infinite sequence. Thus, we omit the formula here.
Note that 0fy (fx.Fx.F.)) F.x can be easily
61x,F.
5

---

4.3 Comparison with other GNNs with infinite depth
Comparing with IGNN I0 our model EIGNN can directly obtain a closed-form solution rather than relying on an iterative solver. Thus, we avoid some common issues of iterative solvers [23] e.g.. approximated solutions and sensitivity to typer-parametery, IGNN requires additional conditions to ensure convergence, whereas EIGNN also an infinite-depth GNN model but avoids such conditions. Without restrictions the weight matrix, even a linear model, EIGNN achieves better performance than IGNN as shown the empirical experiments. Previous work also shows that a linear GNN can achieve comparable performance compared with GCNs predictions from the propagation scheme where PPNP can be treated as considering infinitely many aggregation layers well via the personalized pagerank matrix. However, the propagation of APPNP and PPNP is not learnable. This is completely different from IGNN and EIGNN, and limits the model's representation power. Besides that, PPNP requires performing costly matrix inverse operation for a dense n x n matrix during training.
30) APPNP and PPNP [5] separate
Time complexity analysis Besides the aforementioned advantages of EIGNN over IGNN, using eigendecomposition also has an efficiency advantage using iterative solvers (like in IGNN). If we were to use iterative methods in EIGNN, we could iterate Equation B until convergence. Each computation of gradients has theoretical computational complexity of OK (m2n + mn?)) where K is the number of iterations of an iterative method. With eigendecomposition, the time complexity of computing the limit of the infinite sequence is O( + m²n). During training. the eigendeconposition of g (F) requires the cost of (mm²). Thus, the complexity is O(m3 + m²n) n) in total. In practice, for large real-works graph settings, the number of nodes n. is generally larger than the number of feature dimensions m, which makes m² < mn? Therefore, using eigendecomposition for training is more efficient than using iterative methods for infinite-depth GNNs.
In the above analysis, we omit the time complexity of the eigendeccoppoition of S since it is a one-time preprocessing operation for each graph. Specifically, after obtaining the result of eigende- composition S, it can always be reused for training and inference. The time complexity of plain full eigendecomposition of S is (nn²). In some cases where the complexity of the preprocessing of importance, we can consider using truncated eigendecomposition or graph coarsening [12] to mitigate the cost. Regarding this, we provide more discussions in Appendix
Experiments
In this section, we demonstrate that EIGNN can effectively learn representations which have the ability to capture long-range dependencies in graphs. Therefore, EIGNN achieves state-of-the-ar performance for node classification task on both synthetic and world datasets. Specifically, conduct experiments] to compare EIGNN with representative baselines on seven graph datasets (Chains, Chameleon, Squirrel, Cornell, Texas, Wisconsin, and PPT), where Chains is a synthetic dataset used in Gu et al. [T.. Chameleon, Squirrel, Cornell, Texas, and Wisconsin are real-world datasets with a single graph each (21] while PPI is real-world dataset with multiple graphs [[]]. Detailed descriptions of datasets and settings about experiments can be found in Appendix
5.1 Evaluation on synthetic graphs
Synthetic experiments & setup In order directly test existing GNN models' abilities for capturing long-range dependencies of graphs, like in Gu et al. [10, we use the Chains dataset, in which the model is supposed classify nodes the graph constructed by several chains. The label information is only encoded in the starting end node of each chain. Suppose we have e classes, n. chains for each class, and nodes in each chain, then the graph has X n. I nodes in total. For split, we consider 5%/10%/855 which is similar with the semi-supervised node classification setting [14 We select several representative baselines to compare (i.e., IGNN
vaining/validationn//
[00. GCN [1]. SGC 30) GAT (20), JKNet [3 APPNP 15). GCNII 4 and H2GCN (36]). The
syper-parameter setting and details about baselines' implementation can be found in Appendix C.2
'The implementation can be found

---

0.9
GCN
GCN
0.9
SGC
0.8
GAT
GAT
EIGNN
Accuracy
0.7
EIGNN
0.6
0.7
APPNP
GENII
0.5
APPNP
GCNII
0.4
HZGCN
HZGCN
0.3
0.5
0.2
25
75
100
125
150
175
200
50
100
125
150
175
200
Length of chain
Length chain
(a) Results of binary classification
(b) Results multiclass classification
Figure 1: Averaged accuracies with respect the length of chains.
Results and analysis We first consider binary classification (c - 2) with 20 chains of each class as in Gu et al. [TO]. We conduct experiments on graphs with chains different lengths (10 to 200 with the interval 10). The averaged accuracies with respect to the length of chains are illustrated in Figure la In general, EIGNN and IGNN always outperform the other baselines. GCN, SGC and GAT provide similarly poor performances, which indicates that these three classic GNN models cannot effectively capture long-range dependencies. H2GCN has an even worse performance than GAT, SGC, GCN, which is caused by its ego- and neighbor-embedding separation focusing more on ego-embedding rather than distant information. APPNP, JKNet, GCNII are either designed consider different range of neighbors outperform GCN, SGC and GAT, they still perform worse than implicit models with infinitely deep layers (i.e., EIGNN and IGNN) since finite layers for aggregations cannot effectively capture underlying dependencies along extremely long chains (e.g.. with length > 30). Intuitively, increasing the number layers should improve the model's ability to capture long-range dependencies. However, stacking layers requires excessive computational cost and causes oversmoothing which degrades the performance. Appendix C.5 shows the results of APPNP. JKNet and GCNII with increased number of layers, which illustrates that simply stacking layers cannot effectively help to capture long-rang dependencies. Comparing EIGNN and IGNN, they both perfectly capture the long-range dependency when the length is less than 30, while the performance of IGNN generally decreases when the length increases.
to mitigate oversmoothing [T6 R3 Despite that they
In addition to binary classification used in Gu et al. 10,, we also conduct experiments on multi-class classification 5) evaluate the ability of capturing long-range dependencies generalized setting. Figure 16 shows that EIGNN still easily maintains 100% test accuracy on multi-class classification. contrast, all other baselines experience performance drops compared to binary classification. On multi-class classification, EIGNN and IGNN consistently outperform the other baselines, verifying that models with infinitely deep layers have advantages for capturing long-range dependencies.
On both classification and multiclass classification settings, as shown in Figure D IGNN cannot always achieve 100% test ac- curacy, especially when the length is longer than 30. However, IGNN is supposed to capture dependencies on infinite-length chains as it is implicit model with infinite depth. We con- jecture that the reason for the inferior performance is that the iterative solver in IGNN cannot easily capture all dependencies on extremely long chains.
2.00
2.05
8.40
2.33
6.20
2.5
0.42
Finite-depth IGNN v.s. Infinite-depth IGNN To verify the hypothesis mentioned above, we conduct an additional experiment considering two kinds IGNN, i.e., finite-depth IGNN and infinite-depth IGNN (the version proposed in Gu al. (0]). a dataset with chain length for dinite-depth IGNN, use hidden layers which makes it able to capture
100
chail
Figure 2: Mean accuracies compar- ison between the finite-depth and infinite-depth IGNN.
7

---

Table Results on real-world datasets: mean accuracy (%) stdev over different data splits. **. denotes that the results are obtained from 21]
Cornell
Texas
Wisconsin
Chameleon
Squirrel
#Nodes
183
183
251
2,277
5,201
#Edges
280
295
466
31,421
198,493
#Classes
5
EIGNN
85.1
84.60+-5.41
86.86
62.92+1.559
46.37-+1.39
IGNN 10
61.35-+4.84
58.37+
53.53+6.49
41.38+22.53
24.99+22.11
Geom-GCN
60.81
67.57
64.12
60.90
38.14
SGC B0
33.91
58.92:+4.2
59.41=6.39
40.63+2.35
18,4
GCN 14
19.15=3.51
64.05=5.28
61.17=4.71
42.34+2.77
19.0=
GAT 26
59,46=6.94
61.62+5.77
60.78+8.27
46.03+2.51
30.51+1.28
APPNP 115
63.78=5.43
64.32+7.03
61.57=3.31
43.85++243
30.67+1.06
JKNet 33
58.1813.87
63.78:16.00
60.9812.97
44.45.1.117
30.8311.65
GCNII 4
76.75:15.95
73.5119.95
78.82:15.74
48.5911.88
32.2011.066
H2GCN
36
82.22:15.67
84.7611.557
85.8814.58
60.3012.31
40.75
dependencies with up to I-hops. As shown in Figure 2 IGNN-finite always outperforms IGNN when the length of chains becomes longer. This confirms that the iterative solver used in infinite- depth IGNN is unable to capture all dependencies in longer chains. Note that we use the official implementation of IGNN and follow the exact same setting (e.g., hyperparameters) in Gu et al. [TC] This can be caused by the approximated solutions generated by iterative solvers and the sensitivity hyper-parameters of iterative solvers (e.g., convergence criteria). To further support this hypothesis, we illustrate train/test loss trajectories of IGNN-finite and IGNN in Appendix C,3
Efficiency comparison Besides the performance comparison, on Table [T] we also report the train- ing time per epoch of different models (i.e., EIGNN, IGNN, and (GNN-finite) on datasets with varying length and the number of chains Re- On datasets with different chain length I, we set the number of hidden layers to for IGNN-finite as mentioned in the last paragraph. FIGNN requires less training time
Table 1: Training time per epoch with respect to different and ne
(l. TL.)
EIGNN
IGNN
IGNN-finite
(100, 20)
4.05ms
27.36ms
74.61ms
(200, 20)
8.03ms
29.88ms
145.78ms
(100, 30)
6.03ms
64.94ms
76.3
than IGNN and CGNN-finite. IGNN-finite with many hidden layers (i.c., >100) spends much more training time than implicit models (i.e., IGNN and EIGNN),
(200, 30)
16.0ms
6
146.60ms
which shows the efficiency advantage of implicit models when capturing long-range dependencies desired. Note that EIGNN requires precomputation for eigendecomposition on adjacency matrix. After that, the results can be saved to the disk for further use. Thus, this operation is only conducted once for each dataset, which is tractable and generally requires less than 30 seconds in the experiment.
5.2 Evaluation on real-world datasets
Real-world datasets & setup Besides the experiments on synthetic graphs, following Pei et al. [21] we also conduct experiments on several real-world heterophilic graphs to evaluate the model's ability to capture long-range dependencies. As nodes with the same class are far away from each other in heterophilic graphs, this requires models to aggregate information from distant nodes. Cornell, Texas, and Wisconsin are web-page graphs of the corresponding universities while Chameleon and Squirrel are web-page graphs of Wikipedia of the corresponding topic.
In addition, to show that EIGNN applicable multi-label multi-graph inductive learning, we also evaluate FIGNN on commonly used dataset Protein- Protein-Protein Interation (PPI). PPI contains multiple graphs where nodes are proteins and edges are interactions between proteins. We follow the train/validation/ee split used in GraphSAGE

---

Results and analysis As shown in Table 2 in general, EIGNN outperforms other baselines on most datasets. On Texas, EIGNN provides a similar mean accuracy compared with H2GCN which generally provides the second best performance on other real-world datasets. H2GCN focuses more on different designs about aggregations 3d. In contrast, EIGNN performs well through different approach (i.e., capturing long-range dependencies). In terms of capturing long-range dependencies, H2GCN lacks this ability as demonstrated in our synthetic experiments (see Figure Geom-GCN outperforms several baselines (i.e., SGC, GCN, GAT, APPNP and JKNet), which is attributed to its ability to capture long-range dependencies. However, GCNII provides better mean accuracies than Geom-GCN, GCNII with many aggregation layers stacked is designed for mitigating the oversmoothing issue. Thus, this result suggests that alleviating the oversmooth- ing issue can also improve the model's ability to capture long mangrange dependencies. Note that Geom-GCM and IGNN are both significantly outperformed by EIGNN. Therefore, it indicates that they are still not effective enough in capturing long-range dependencies on heterophilic graphs.
Table 3: Multi-label node classifi- cation on PPI: Micro-F1 (%).
Table 3 reports the micro-averaged Fl scores of EIGNN and other popular baseline methods on PPI dataset. As we fol- low the exactly same setting used in Gu et al. [10,, the results
of baselines are obtained from Gu et al. [ From Table 3
Method
Micro-F1
EIGNN achieves better performance compared with other base- lines, which can be attributed to the ability of EIGNN to capture long-range dependencies between proteins PPI dataset. Ad- ditionally, we also conduct the efficiency comparison between EIGNN and IGNN. On average, for training an epoch, EIGNN requires 2.23 seconds, whereas IGNN spends 35.03 seconds. As suggested in IGNN [TO, the training generally requires more than 1000 epochs. Besides the training time, EIGNN needs one-time preprocessing for eigendecomposition on S which costs 40.59 seconds. Therefore, considering both preprocessing and training, EIGNN still requires less time compared with IGNN.
Multi-Layer Perceptron
46.2
GCN 14
59.2
GraphSAGE ||I
78.6
SSE 6
83.6
GAT 26
97.3
IGNN 10
97.6
EIGNN
98.0
5.3 Noise sensitivity
shows that GNNs are vulnerable to perturbations, and El Ghaoui et al. analyze the potential robustness properties of an implicit model. Thus, in this subsection, we empirically examine the potential benefit of EIGNN on robustness against noise. For simplicity, we add perturbations only to node features. Experiments on synthetic datasets and real-world datasets are both conducted.
Recent research
61 37
Synthetic experiments On synthetic chain datasets, we add random perturbations node features in Wu et al. [31.
Specifically, we add uniform noise e ~ U(-a;, (:) to each node's 's features for constructing noisy datasets. Figure 3 shows that across different noise levels, EIGNN consistently outper- forms IGNN. This indicates that EIGNN less vulnerable to noisy features.
FIGNN (a 6.91)
EICNN (am0.3)
IGNM towbi03) o3)
0.65
0:63
Real-world experiments On real-world datasets, we use two
0.55
classic adversarial attacks (i.e., FGSM о and PGD [18] to
Longth of chain
add perturbations on node features. See the detailed setting in Appendix
C We compare three models (i.c., EIGNN, H2GCN, IGNN) on Cornell, Texas, and Wisconsin under dif- ferent level perturbations. As we can observe from Table
Figure 3: Accuracy datasets
with different feature noise.
EIGNN consistently achieves the best performance under different perturbation rates on all three outperform higher. Under FGSM with a perturbation rate larger than 0.001, H2GCN is even outperformed by IGNN which has worse performance under 0.0001 perturbation rate.
datasets. Specifically, EIGNN outperforms H2GCN by larger margin when the perturbation rate is
In summary, the above results show that EIGNN is generally more robust against perturbations com- pared with H2GCN. The intuitive reason is that EIGNN is not/less sensitive to local neighborhoods,

---

Table Accuracy (%)
under attacks with different perturbations.
Attack
FGSM
PGD
Perturbation
0.0001
0.001
0.01
0.0001
0.001
0.01
EIGNN
85.13:5..57
84.05:15.59
6.570-16.56
85.131:.557
84.05
73.24:16.45
Corn.
H2GCN
59.4
26.49+8.62
2.16-+2.336
82.97+-5227
13.9.00
28.68
IGNN
61.08++3.66
60.54++4.22
57.30++5.51
61.07++3.66
60.54
57.8445.116
EIGNN
84.33
83.79115.26
74.59:14.05
84.3315.77
83.791:5.27
75.14114.32
Texas
H2GCN
6..25:16.22
39.79-19.05
7.30:17.74
84.86:15.57
6..54:16.89
36.22:17.57
IGNN
57.84=5.116
57.28+5.64
53.51+5.10
57.84+:..16
57.30+5.64
53.51+5.10
EIGNN
86.67=66.19
84,90-66.45
70,00+
86.67--6.19
85.10+6.34
71.96+66.66
Wisc.
H2GCN
83.53.14.04
17.84
4.12.13.66
84.9011..62
17.2514.13
38.0411..52
IGNN
53.53.14.39
53.14.14.06
47.26.13.77
53.53.14.39
53.14.1..06
47.84.3..53
while finite-depth GNNs (e.g., H2GCN) could be very sensitive to local neighborhoods. Finite-depth GNNs usually only have a few layers and the node representations would be changed a lot when aggregating from perturbed node features. In contrast, EIGNN, infinite-depth GNN model, can consider more about global information and become less sensitive to perturbations from local neighborhoods.
6 Conclusion
In this paper, we address an important limitation of existing GNNs: their lack of ability to capture Long-range dependencies. We propose EIGNN, GNN model with implicit infinite layers. Instead of using iterative solvers like in previous work, we derive a closed-fome solution of EIGNN with rigorous proofs, which makes training tractable. We further achieve more efficient computation for training our model by using eigendecomposition. On synthetic experiments, we demonstrate that EIGNN has better ability capture long-range dependencies. In addition, also provides state-of-the-an performance on real-world datasets. Moreover, our model is less susceptible to perturbations on node features compared with other models. One of the potential limitations of our work that EIGNN can be slow when the number of feature dimensions is very large (c.g., million), which is rare in practical GNN settings. Future work could propose new model which allows for efficient training even with large feature dimension.
Acknowledgments and Disclosure of Funding
We would like thank Keke Huang and Tianyuan Jin for helpful discussions. We also gratefully acknowledge the insightful feedback and suggestions from the anonymous reviewers. This paper is supported by the Ministry of Education, Singapore (Grant No: MOE2018-T2-2-0911 The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, 2019.
[2] Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale deep equilibrium models. In Advances in Neural Information Processing Systems, 2020.
[3] Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. In International Conference Learning Representations, 2021.
[4] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.
[5] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In Advances in Neural Information Processing Systems, 2018.
10

---

[6] Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alex Smola, and Le Song, Learning steady-states of iterative algorithms over graphs. International Conference on Machine Learning, 2018.
[7] Laurent EI Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Y Tsai. Implicit deep learning. arXiv preprint arXiv: 01109098800.... 2, 2019.
[8] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
[9] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. IEEE, 2005.
[10] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems, 2020.
[11] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
[12] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2021.
[13] Kenji Kawaguchi. On the theory of implicit deep learning: Global convergence with implicit layers. In International Conference on Learning Representations (ICLR), 2021.
[14] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2016.
[15] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
[16] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
[17] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
[18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations, 2018
[19] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2020.
[20] 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 Detito, 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 Advances in Neural Information Processing Systems. 2019.
[21] Hongbin Pei, Bingzhe Wei, Kevin Chennn Chang, Yu Lei, and Bo Yang. Geom-gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations, 2020.
[22] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
[23] Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
[24] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 2008.

---

[25] Aravind Subramanian, Pablo Tamayo, Vamsi K Mootha, Sayan Mukherjee, Benjamin L Ebert, Michael A Gillette, Amanda Paulovich, Scott L Pomeroy, Todd Golub, Eric S Lander, et al. Gene set enrichment analysis: a knowledge-basee approach for interpreting genome-wide expression profiles. Proceedings of the National Academy of Sciences, 102(43):15545-1555 2005.
[26] Petar Veličković, Guillem Cucurull, Aramtxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations, 2018.
[27] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
[28] Yiwei Wang. Yujun Cai, Yuxuan Liang, Henghui Ding, Changhu Wang, Siddharth Bhatia, and Bryan Hooi. Adaptive data augmentation on temporal graphs. In Advances in Neural Information Processing Systems, 2021.
[29] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference, 2021.
[30] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning, 2019.
[3]] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovee. Graph information bottleneck. In Advances in Neural Information Processing Systems, 2020.
(32) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chenggi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[33] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning. 2018.
[34] Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey, IEEE Transactions on Knowledge and Data Engineering, 2020.
[35] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in [gnn]s. In Interna- tional Conference on Learning Representations, 2020.
[36] Jiong Zhu, Yujun Yan, Lingxiao Zhao Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
[37] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2018.
12


Reviews:
[{"review_id": "OdB6wGuEut", "reviewer": "Reviewer_9hrH", "summary": "This paper proposes an efficient method for infinite-depth GNN model that allows learnable transformations in each layer. A more efficient computation (eigen-decomposition) of the close-form solution is discussed and proved in the paper. In the experiments, EIGNN shows superior performance on both synthetic and real datasets which requires long-range dependencies capture. The robustness of the method is evaluated by perturbation of node features as well.", "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": "Overall, the paper is clear and easy to follow. The result presented in the paper is both significant and efficient, which aligns well with the original claims made in the paper.\n\nWeakness and Questions:\n1. Some of the interesting work at long-range dependencies are neglected in both related work and experiments. For example, the author mentions APPNP/PPNP in the experiment, while I think this one is quite related with the main contribution of the paper and author should discuss this one in related work. Also, another work called \"Continuous Graph Neural Networks\" [1] is worth discussing in the paper. In its 4.2, it also applies learnable parameters in an infinite-layer GNNs and conduct solution. The author should consider discuss and compare with this method as well.\n2. The dataset selected might be biased towards to the long-range dependencies on node classification. I notice the proposed method yield a large margin to the selected dataset. However, these datasets are both small and not well-known for node classification (see OGB for large benchmarks). Why not you do graph classification instead like the original IGNN paper? \n3. The scalability of the method. As far as I understand, although eigen-decomposition is way more efficient than inverse computation. But in a large network with millions nodes, can you still handle it via eigen-decomposition?\n\n[1] Xhonneux, Louis-Pascal, Meng Qu, and Jian Tang. \"Continuous graph neural networks.\" International Conference on Machine Learning. PMLR, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "AAjLRmjRyQ", "reviewer": "Reviewer_emSJ", "summary": "The authors propose a linear infinite-depth GNN, whose forward pass is a convergent series whose limit can be written in closed-form. Since the series involves the powers of the normalised adjacency matrix, the resulting model captures interactions between all pairs of connected nodes. At the same time, the existence of a closed-form expression makes the gradients easy to compute and provides an easy way to train the model. The authors show how the computational complexity of the model can be improved by diagonalising some of the matrices involved in the computation. The paper validates the hypothesis that the model can capture long-range interactions better than existent models in a synthetic setting and also on small real-world heterophilic graphs. ", "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": "## Strong points\n\n- The authors introduce a model that has many attractive properties: (1) It has residual connections, which have been shown to play an important role in a graph setting, (2) it involves powers of the adjacency matrix which in the limit allows all connected pairs of nodes to interact (3) The series has a nice closed-form expression in the limit that allows the model to be easily trained, (3) the model does not require solvers, which are generally slow or suffer from instabilities.\n-  The only inconvenience of the model is that the complexity of computing the closed-form expression is not practical. The authors also offer a (partial) solution for this by proposing various approximations based on the eigendecomposition of certain matrices. \n- The chain dataset is a great synthetic setting for testing the theoretically justified ability of the model to capture long-range interactions and the authors compare the model carefully against IGNNs in this setting. They also perform a reasonably convincing ablation for IGNN to better understand its limitations. \n- The authors also consider a real-world setting formed of heterophilic graphs, which is indeed an appropriate class of graphs for testing to some extent the long-range interactions that the model can capture. \n\n## Improvements and Questions\n\n- Some of the motivations behind the work are slightly incorrectly stated and do injustice to classic GNNs. Therefore, these could be rephrased: \n  - In the abstract (and other places) the authors claim that \"finite layers\" -> \"unable to capture long-range interactions\". This is not correct. For all practical purposes, the long-range interactions that can be found in practice are bounded by some constant $L$ and a GNN with $L$ layers will be able to capture them. \n  - In line 34 \"GNN models with numerous layers require excessive computational cost in practice\". The complexity of a message passing GNN with $k$ layers in a graph with $E$ edges is $\\mathcal{O}(kE)$. Even assuming that $k ~ \\mathcal{O}(V)$ (the number of vertices), this is still $\\mathcal{O}(VE)$, which I would not call \"excessive\". Note that for the eigendecomposition of $S$ in line 176, the complexity is $\\mathcal{O}(V^3)$, which is worse when the graph is sparse (I also have a question about this below). \n  - In line 30: \"... poor empirical performance when stacking more than a few layers, which has been referred to as oversmoothing\". Oversmoothing is only one of the causes of why Deep GNNs often have problems and it is more common among convolutional models (https://arxiv.org/abs/1905.10947). There is also over squashing (https://arxiv.org/abs/2006.05205) and it is also likely related to optimisation issues as well. \n- Regarding the complexity of the method, the $\\mathcal{O}(V^3)$ eigendecomposition of $S$ from line 176 does not seem to be included in the reported computational complexity. Why is that the case? That is very problematic for many applications where the number of nodes is well beyond $1$ million. Is this why the authors evaluate only on extremely small graphs (see my next point)? The authors might argue that the eigendecomposition of $S$ is not such a big problem because it is a one-time pre-processing step, but this could still limit its applicability in a real-world setting where the graph is often changing in time. \n- As mentioned above, the real-world benchmarks used by the authors are extremely small. While including small-sized graphs is totally justified, I would expect to see at least some medium-sized graphs in the evaluation as well (e.g. from https://ogb.stanford.edu/ or https://arxiv.org/abs/2003.00982).  Based on this and my point above, I have doubts about the scalability of the model in a practical setting. \n- Another limitation that is not mentioned is that using the eigendecomposition of $S$ in the model makes the model inapplicable to multiple graphs because the eigenbasis changes from one graph to another and even for isomorphic graphs, it is not uniquely defined (for more details see e.g. https://arxiv.org/abs/1611.08097). This can be a problem for many practical settings where we want to classify nodes from multiple graphs or maybe we want to perform pre-training on another graph. \n- The limitations of the model have not been properly addressed. The authors have included only a sentence in the conclusion on this. For instance, my point on the $\\mathcal{O}(V^3)$ complexity or the transferability across different graphs could have been mentioned. Are there any other limitations that the authors could mention?   \n- All the figures in the experimental section are missing standard deviations. All experiments should be run over multiple weight initialisations for all the models. Without error bars around the curves in the figures, the reported results could just be lucky runs. \n- While I appreciate the experiments on noise robustness, they only show results on a synthetic graph where the proposed model was already performing better in the first place. At the same time, no justification is offered as to why the proposed model would be more robust to noise. An intuitive justification (if not theoretical) should be presented and validated at least. \n- The paper does not comment at all on the closed-form expression from Proposition 1 to provide a deeper understanding. The expression looks very interesting and the authors could attempt to provide an intuition about what it actually does. For instance, how is the information from different hops around a source node weighted by this expression? \n- A Question: What is the purpose of Proposition 3 and Equation (9)? Since the forward pass has a trivial closed-form expression, the gradient can be trivially computed by an automatic differentiation package. Furthermore, the authors do not seem to use the gradient in their follow-up analysis and, therefore, it could be simply added to the appendix since it does not seem to provide any essential information to the reader. Or is the computation of the derived gradient more efficient than what automatic differentiation would compute? I do not believe that is the case, but if it is, then it should be proven. \n\nEDIT: After the rebuttal, I have increased my score from 5 to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not addressed this in sufficient detail. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3dGxtewqhNF", "reviewer": "Reviewer_mzDR", "summary": "The paper proposes an infinite-depth GNN which captures long-range dependencies in the graph while avoiding iterative solvers by deriving a closed-form solution. The eigendecomposition method is introduced to further improve efficiency. Experiments on several datasets shows improved performance.\n\n", "questions": "", "limitations": "", "rating": 5, "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": "1. The paper proposes the EIGNN in Section 4. The model is formulated in Equations (2), (3), and (4) but didn't provide any explanation for this model itself. Therefore, the motivation of the model is unclear. \n\n2. Instead, Section 4 focuses on introducing the forward and backward computation. In section 4.1, it is clear that the computation and memory cost is not acceptable because it requires dealing with the inverse of a very large matrix and the inversed matrix is dense. \n\n3. In section 4.2, an eigendecomposition method is introduced to improve efficiency. However, it still requires the eigendecomposition on the matrix $S$ whose size is the number of nodes. This is still very expensive for a reasonably large graph, and the result of the decomposition are dense matrices that require significantly large memory and costly computation.\n\n4. The paper tries to avoid iterative solvers that cause approximation errors. However, there is no convincing evidence to show how the approximation error impacts the performance. Therefore, the advantages of using a closed-form solution are unclear while the drawbacks are obvious. More ablation study would be helpful.\n\n5. The datasets in the experiments are very small graphs, it is unclear how the model performs in large graphs in terms of both efficiency and effectiveness. The efficiency comparison with iterative solvers will be helpful.\n\n6. In the experiments on the synthetic chain data, there is a huge performance gap between EIGNN and IGNN. Considering that IGNN is able to capture long-range dependencies, it is unclear where the improvements of EIGNN come from. In the experiments on real-world data, the performance gap between EIGNN and H2GCN is very small while the gap between EIGNN and IGNN is huge. It is a bit confusing and again raises the concern -- where do the improvements of EIGNN come from.\n\n7. While it is possible to verify the benefits of capturing long-range dependencies in the synthetic graph, it is unclear whether this property helps in real-world graphs and how to confirm it. \n\nOverall, this paper proposes an infinite-depth GNN with a closed-form solution. However, the computation and memory cost is still very high. Moreover, without an explanation for the model, the reason for the performance improvement is unclear.\n\n--------------------------\nDuring the discussion, I have raised my rating from 3 to 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation of EIGNN should be discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1m0VGY3Rdk", "reviewer": "Reviewer_GtHW", "summary": "This paper presents an interesting idea on designing a novel graph neural network to capture the long-range dependency, which is the lack of ability of most existing works. A linear model that extends SGC with implicit infinite layers, EIGNN, is proposed to mitigate this issue. A closed form of the infinite sequences is used to define the layer-wise update rule and eigendecomposition is combined to achieve more efficient training. Experimental results on both synthetic and real-world datasets demonstrate the effectiveness of the proposed EIGNN for capturing the long-range dependency.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths:\n\nS1: It is important for the GNN models to obtain the ability for capturing the long-range dependency.\nS2: The idea to extend the linear model SGC into infinite layers is interesting, since it could help the community rethink the representational ability of linear models on graphs. The theoretical analysis on convergence and training of the model has merits. \nS3: The paper is easy to follow with a clear motivation and comprehensive experimental analysis.\n\nWeaknesses:\n\nW1: The design of extending SGC (from Equation 1) to EIGNN (from Equation 3) is somehow implicit and ad-hoc without clear justifications. The authors should explain this more in details for better understanding by general audiences that not very familiar with implicit models.\n\nW2: During the time complexity analysis, only the complexity of training is analyzed, but it seems like the computation of eigendecomposition of S, the normalized adjacency matrix with self-loops, (Line 176) is not added, which usually requires the cost of $\\mathcal{O}(n^{3})$. If this is true, a full eigendecomposition of a large sparse S could make EIGNN an impractical approach for prohibiting the scalability in terms of large number of nodes $n$ for huge real-world graphs.\n\nW3: Several concerns upon experiments include:\n1)\tThe discussion on arbitrary hyperparameter $\\gamma$ is missing, including how to set it in practice for a given graph and analyzing on the sensitivity of this hyperparameter， otherwise it will be hard for the researchers to follow.\n2)\tAs the weakness on the analysis of complexity, why the author chooses not to evaluate the long-range dependency on the standard dataset Amazon Co-purchase as used in IGNN. Amazon Co-purchase dataset has another benefit that it can also reflect the scalability of proposed method since it is a large dataset with ~33k nodes, while the experiments on real-world dataset are all conducted on graphs that less than 10k.\n3)\tFor the evaluation on over-smoothing, it would be interesting to see how the EIGNN performs with respect to over-smoothing under standard setting on real-world datasets, especially in comparison with variants focusing on dealing with over-smoothing, such as the setting used in GCNII.\n4)\tThe evaluation on robustness is not very convincing since structural attack is known to be more powerful and appreciative when we attack on graph-structured data. Thus, the authors are suggested to defend their proposed model against several popular structural attack methods such as Nettack for better demonstration rather than attacks on features used in experiments.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have discussed in the conclusion part. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~5h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 3 of 4 ratings were "accept". The lowest rating (a 5) was most concerned about insufficient experimental evaluation of speed/accuracy tradeoffs, which was echoed by other reviewers as well.

Through the rebuttal/discussion period the authors were very responsive and caused several reviewers to raise their ratings. My view is that the original submission was somewhat confusing and incomplete in a few ways, but that the core of the method and results are solid, and through the discussion period the authors have improved the paper enough to warrant publication. The confusion could also stem from the fairly high technical complexity in the work, which I'd encourage the authors to explain as clearly as possible in the final text.

I do agree with the concern about speed/accuracy analysis, and I'd encourage the authors to do anything they can to address this for camera-ready (if the paper is accepted), however I don't anticipate any surprises.

Decision: Accept (Poster)