MGNNI: Multiscale Graph Neural Networks with Implicit Layers
Authors: Juncheng Liu
Bryan Hooi
Kenji Kawaguchi
Xiaokui Xiao
Venue: NeurIPS 2022 Accept (2022)
Keywords: implicit graph neural networks
graph neural networks
implicit models
equilibrium models
graph representation learning

Abstract: Recently, implicit graph neural networks (GNNs) have been proposed to capture long-range dependencies in underlying graphs. In this paper, we introduce and justify two weaknesses of implicit GNNs: the constrained expressiveness due to their limited effective range for capturing long-range dependencies, and their lack of ability to capture multiscale information on graphs at multiple resolutions. To show the limited effective range of previous implicit GNNs, we first provide a theoretical analysis and point out the intrinsic relationship between the effective range and the convergence of iterative equations used in these models. To mitigate the mentioned weaknesses, we propose a multiscale graph neural network with implicit layers (MGNNI) which is able to model multiscale structures on graphs and has an expanded effective range for capturing long-range dependencies. We conduct comprehensive experiments for both node classification and graph classification to show that MGNNI outperforms representative baselines and has a better ability for multiscale modeling and capturing of long-range dependencies.

MGNNI: Multiscale Graph Neural Networks with Implicit Layers
Juncheng Liu
Bryan Hooi
Kenji Kawaguchi Xiaokui Xiao
National University of Singapore (juncheng, , xiaoxk)@compp....... nus. edu.
Abstract
Recently, implicit graph neural networks (GNNs) have been proposed to capture long-range dependencies in underlying graphs. In this paper, we introduce and justify two weaknesses of implicit GNNs: the constrained expressiveness due to their limited effective range for capturing long-range dependencies, and their lack of ability to capture multiscale information on graphs at multiple resolutions. To show the limited effective range of previous implicit GNNs, first provide theoretical analysis and point out the intrinsic relationship between the effective range and the convergence of iterative equations used in these models. To mitigate the mentioned weaknesses, we propose a multiscale graph neural network with implicit layers (MGNNI) which able model multiscale structures on graphs and has an expanded effective range for capturing long-range dependencies. We conduct comprehensive experiments for both node classification and graph classification show that MGNNI outperforms representative baselines and has better ability for dependencies.
multiscale modeling and capturing of
Introduction
In recent years, graph neural networks (GNNs) have been widely adopted on graph-related tasks, such as node classification, link prediction, and graph classification [29]. In general, GNNs utilize both node attributes and graph topology to produce meaningful node representations for downstream applications. To achieve this, most modern GNNs follow "message passing" mechanism: at each iteration, they iteratively aggregate representations of neighboring nodes of each node with its own representation to generate new representations. During this process, each iteration is typically parameterized as a single-layer neural network with learnable weights. Many GNN models have been proposed by adopting different aggregations techniques (e.g., GCN with renormalization 177, GAT with attentive aggregations on neighbors 27 and SGC (2 using aggregations without non-linear activation). In spite of the effectiveness achieved by the aforementioned GNNs on different tasks, they fail to effectively capture long-range information on graphs, since a GNN with layers can only capture information up to T hops away.
To overcome this deficiency of previous GNNs, recent work has proposed implicit graph neural networks 13 20 21 to effectively capture long-range dependencies. These implicit graph neural networks generally define a fixed- point equation as an implicit layer for aggregation and generate the equilibrium Z* as the node representations. To get the equilibrium, they either use an iterative solver to solve the equation or directly obtain a closed-form solution with guaranteed convergence. Meanwhile, they utilize implicit differentiation to achieve O(1) memory complexity when computing the gradients during the iterations. As mentioned in Gu et al. [K]] . Liu al. (20,, these models can be treated graph neural network with infinite layers which has the same transformation and shared weights in each layer. This makes them able to effectively capture long-range dependencies without excessive memory requirements as compared with previous GNNs.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Despite the superiority of implicit GNNs shown in several applications requiring long-range informa- tion, an important question what the farthest range these models can capture information from has not been studied. Although these models are usually claimed as GNNs with infinite depth this paper, we first point out the effectivv range of these models (i.e., the maximum hops they can effectively capture dependencies for each node) is actually bounded by certain value. We provide analyses on the intrinsic relationship between the effective range and the convergence of the iterative equation used in implicit GNNs. Specifically, these models usually use a contraction factor Y to ensure the convergence of the iterative map 20 20. which indeed exponentially decays the distant information during the aggregation at the same time. This design inherently limits the effective range of propagation and hinders their ability to capture long-range dependencies.
13 20
Besides the limited effective range. implicit GNNs also cannot effectively capture multiscale informa- tion on graphs, i.e., graph features at various scales. In contrast, several GNNs without implicit layers 3C
2 1 g have been proposed to utilize multiscale information to improve the model capacity. For example, Xu et connections and adaptive aggregations of hidden representations at different layers. MixHop III learns neighborhood mixing relationships by mixing hidden representations at various distances. These explicit GNN models demonstrate the effectiveness of utilizing multiscale information from neighbors at various scales. However, it is still not clear how to utilize multiscale information with implicit GNNs since there are different "layers" in implicit GNNs that can be used for capturing multiscale information at different scales.
$10 proposes JKNet which leverages different neighborhood ranges by skip
Motivated by the above limitations of previous implicit GNNs, we propose our multiscale graph neural network with implicit layers (MGNNI) which brings multiscale modeling into implicit GNNs and expands their effective range for capturing long-range dependencies. We summarize the contributions of this work as follows:
We introduce the concept of effective range for implicit GNNs, and provide theoretical analyses on the effective range that previous implicit GNNs can capture distant information from. We then point out that their effective range is limited although previous models are generally regarded as GNNs with infinite layers.
We propose MGNNI as a new implicit GNN model with multiscale propagation to expand the effective range and capture underlying graph information at various scales.
We conduct comprehensive experiments with synthetic datasets and real-world datasets on both node classification and graph classification demonstrate that MGNNI has better performance and better ability to capture both long-range range and multiscale information compared with other baselines.
2 Related work
Implicit Models Implicit neural networks use implicit hidden layers which are implicitly defined: the outputs are determined by the solutions of some underlying equations. A notable advantage of these implicit models is that they generally backpropagate through the fixed-point solution using implicit differentiation to achieve constant memory complexity regardless of the "depth" of the network. There is emerging interest in implicit layers in recent years [
3 [1I. To name few, Bai et al. 4 propose the deep equilibrium model (DEQ) demonstrating the ability of implicit models in sequence modeling; Multiscale DEQ (MDEQ) 5 brings multiscale modeling into implicit deep networks for image classification and semantic segmentation. Kawaguchi [5 analyses the global convergence of deep linear implicit models and Geng et for implicit models to avoid the costly exact gradient computation.
provide gradient estimate
Graph Neural Networks GNNs have been widely used in different tasks for graph-structured
data. Even with different aggregation schemes (e.g., skip connection 30 g and attention (27). convolutional GNNs [17 30 generally involve finite aggregation layers (usually less than 20 layers) with different learnable weights, which makes them unable to effectively capture fong-range dependencies. Although RevGNN [9] is proposed with 1000 layers, it has to use deep reversible architectures [12], which requires excessive amount of time for training. Inspired by implicit models 5 on image and text data, implicit graph neural networks
[K]
20 21 have been proposed to
capture long-range range information with constant memory complexity. Implicit GNNs generally define an

---

aggregation equation and obtain the fixedpooin solution of the equation as the outputs. In particular, Gu al. T3 propose IGNN where they ensure the well- pellepssessss and use iterative solvers to obtain fixed-point solutions. Liu et al. [20] propose EIGNN as a linear implicit GNNs where closed-form solution derived. Park et al. [21] construct an input-dependent linear iterative map for predicting the properties of a graph system. However, these implicit GNNs cannot model multiscale information in underlying graphs. In contrast, several explicit GNNs, such as JKNet 60), MixHop M. and N-GCN 221. have shown that multiscale information is helpful to improve the model capability. To fill the gap, our model MGNNI brings multiscale modeling to implicit GNNs.
3 Preliminaries
A graph is represented as G = (V,E) which contains the node set V with n nodes and the edge set E. In practice, graph neural networks take the adjacency matrix A Æ=x* and the node feature matrix X E Rm of G as input data. For simplicity, considering unweighted adjacency matrix A, then A., if (i.j) E, for any two nodes i.j E V; otherwise A., = O. Given input graph data (G. X), depending on different classification tasks, graph neural networks are required to provide a prediction ý for a node or a graph to match the true label y-
Aggregations in GNNs GNNs typically employ a trainable aggregation process that iteratively pass the information from each node its adjacent nodes, followed by non-linear activation. Without loss of generality, a typical aggregation step at layer can be written as follows:
z(+1) <(W (1) 2 + X))
(I)
where ( Rlix xn is the hidden states in the layer I which stacks the state vectors of every nodes denoted 2() E R²;;; S R=xn is the normalized adjacency matrix; W(I) R X and 2 E Rh441xm are the matrices of trainable weight parameters; & denotes a non-linear activation function. Recently proposed GNN models use different forms of this graph aggregation process. For example, simplified graph convolution
[S removes the non-linear activation, use only one weight matrix W, and sets 2 = X and Ω O.
In addition to GNNs with explicitly defined layers, GNNs with implicit layers 13
20 21
also follow
a similar aggregation form, but with tied weight matrices W and f2 at each iteration step. For these
implicit GNNs, the aggregation step is generally changed to (1+ = o ( 5 22X). Given such an aggregation step, implicit GNNs of times until convergences. To ensure the convergence, IGNN [T3] enforces |[ | S K 1
be seen iterating the aggregation step an infinite number
with K E [0, 1), where An is the Froron-Frobeiu (PF) eigenvalue 77 EIGNN 20 and CGS 21
instead achieve this by introducing a contraction factor in the aggregation step.
Using EIGNN as an example, it defines the aggregation as an iterative mapping with contraction factor y as follows:
z(+1) = 7g (F) S X,
where y E [0, 1) and gW) is a bounded mapping that projects the trainable weight matrix F into a Frobenius norm ball of radius 1. Given the iterative mapping, implicit GNNs obtain the equilibrium states 2" = o(W z + (2X) as the final representations by using either root-finding approaches or closed-form solutions.
4 Effective range of previous implicit GNNs
Implicit deep learning is considered as a method to increase the effective depth of deep neural Previous works on implicit GNNs (including IGNN [3 and EIGNN 20) claim that these models can be viewed as an infinite-layer GNN. However, in this section, we point out that the effective range within which previous implicit GNNs can capture the long-range information is actually bounded. In other words, their abilities for capturing long-range dependencies are still restricted. We provide analyses revealing the intrinsic relationship between the effective range and the convergence of the iterative equation in implicit GNNs. In addition, we also provide empirical results to support our analyses.
networks 4 2
To investigate the effective range, we first provide an analysis on sensitivity, i.e., how changes in node features of node p affect the equilibrium of distant node q.
3

---

Theorem 1. Given two nodes p and q that are h-hops apart, using Equation 2 for propagation, if we perturb node features X of node p by AX..p R.", the L2 norm of the change in node q equilibrium | is upper bounded as follows:
7h A o - --7 110 (F)AX
(3)
The complete proof can be found in Appendix A.1
At first glance, the norm of the change in equilibrium A.", would not be zero no matter how large the distance between node p and However, Theorem shows that || |AZ |l decays exponentially with distance along the graph. Therefore, in practice, this change will fairly quickly fall below the roundoff error in floating-point numbers or the stopping criterion in the iterative solver used to obtain the fixed-point solution, then the change AX., on node p cannot affect the equilibrium of node q. This is the intuition about what we call the effective range. To formalize it, we provide the definition of 0-effective range as follows:
Definition 1. For any given error parameter 0 > O, the O-effective range h is the maximum integer such that exists some pairs of nodes p and q that are h-hop apart, when node features X; of node p are perturbed by AX.,p the L.2 norm of the change node q's equilibrium || > 0.
By Definition we know that, given any h > h, for all pairs of node p and q that are ht- ho-hop apart. the L2 norm of the change || | S 6, which means the equilibrium of node cannot be affected in practice. To analyse the O-effective range, we can derive the corollary Theorem !
Corollary 1. With Equation range upper bounded:
2 for propagation, given any error constant 0 >> O, the O-effective In(8(117)), Therefore, if node features X. of node p are perturbed, In
the perturbation can only affect the equilibrium of nodes which are up to ln(6(1-71)) -hop away from p. In
The complete proof can be found in Appendix A.2 Note that the above analysis is directly applicable
to two recent Implicit GNN models with a contraction factor i.e., EIGNN (20 and CGS [21]
Asides from the above analysis. we further verify the theoretical analysis with synthetic experiments on the same chain dataset as in EIGNN 20 and IGNN [33, where the task requires simply passing information from one end to the other of chain graph. See Appendix C. for detailed settings. We use the basic form of EIGNN (20) with iterative methods (i.c., iterating Equation 2 to find the cquilibrium) the model. We follow the same experimental setup EIGNN and then perturb node features by masking the features of the starting node to all zeros. To support our theoretical analysis, we investigate how the change of node q's equilibrium (i.e., AZ behaves as q gets farther away from p. In Figure L we show that AZ decays as node q gets further from p in terms of the distance. For example, with 7 0.5, A :.g becomes numerically 0 when q and p are around 25 hops apart, which indicates that node can no longer receive any information from node p at this distance.
The above theoretical analysis and empirical evidences show how different values of 7 can constrain the expres- siveness of implicit GNNs, i.e., the range within which they effective capture long-range dependencies. In short, smaller y results in a shorter effective range of im- plicit GNNs. A straightforward strategy to expand the ef- fective range is to increase (c.g., to close to I). However, large y can cause instability and difficulty for the con- vergence of iterative mapping, which would empirically compromise the efficiency of iterative solvers as found in our experiments. We provides the empirical evidences for this in Appendix B This raises the question: how can we capture longer range dependencies while ensuring the convergence of the iterative mapping? Our multiscale MGNNI approach aims to answer this question.
055
Norm change: .01
0.4
y= 0.55
0.-
Distance
Figure 1: The norm of the change of equilibrium | decays as node becomes further from p.

---

Multiscale implicit graph neural networks
propagate the information from 1-hop neighbors while applying a decay with the contraction factor r in each iterative step (e.g.. using Equation 2 As analysed in Section 4 this design inherently limits the effective range of propagation since the information decays exponentially as the range grows linearly. Besides the limited effective range, previous implicit GNNs also cannot capture multiscale information on graphs similarly to explicit GNNs, such as JKNet B0 and MixHop MI which combine information at different scales of the graph.
Previous implicit GNNs 13
20
2
Motivated by these limitations, we propose multiscale graph neural networks with implicit layers (MGNNI) which can first expand the effective range to capture long-range dependencies and then capture information from neighbors at various distances. MGNNI contains multiple propagation components with different scales and learns a trainable aggregation mechanism for mixing latent information various scales.
5.1 The MGNNI model
single m-scale propagation module in MGNNI model is defined as the following iterative mapping:
g ( 5Th ((X,)),
(4)
where 7 E [0, 1) and denotes hyperparameter for the graph scale (i.c., the power of adjacency matrix). f(X,)) is a parameterized transformation on input features and graphs, and g(F) is normalized weight matrix defined as:
g F F FTF
(5)
with arbitrary small EF > O. Note that in multiscale propagation, at each iterative step, the model can capture the information along with a m-step path, while previous implicit GNNs only consider 1 hhhop neighbors. In this way, MGNNI is able capture dependencies within longer range over iterations. Now we provide the analysis to show that the iterative mapping in MGNNI (i.e., Equation converges to unique equilibrium Z"
lim (h) = s.t. =" "g(' + f(X,9).
Theorem 2. Given the bounded damping factor [0, 1), the proposed iterative map for propagation (i.e., Equation 4 is a contraction mapping and the unique fixed-point solution Zt can be obtained
by iterating Equation
This can be proved by using the properties of matrix vectorization and the Kronecker product with the Banach fixed Point Theorem. The complete proof is given in Appendiex A.3
Multiscale propagation With set of multiple scales M (m1,..., mm/m: * mjVi, j.. we can have multiple propagation modules and obtain equilibriums with different scales Given those equilibriums, we propose a scale-aggregation mechanism uti- lizing learnable attentions, as to learn the contributions of different scales for each node automatically through the learning objective. For each node i, z
{ Z=2 ? k=
*t denotes (-th equilibrium in Z and the attention
value 8 is defined as follows:
= g"anhtt WWaz," + ba),
where y is the parameterized attention weight vector, Wa and b, are the weight matrix and the bias vector, respectively. Given attention values for different scales ","",..,') normalized by softmax function:
}. the final weights are
exp(3!)
softmax (0)
Σラ= " exp(3))
Larger at indicates that the corresponding scale is more important for node i. The final embeddings Z' are obtained by aggregating the equilibriums at different scales with corresponding weights:
af
(9)
y = (Z'),
(10)
5

---

where the predictions Y are generated by a -ebecfi- decoding function fo-
5.2 Expanded range via multiscale propagation
In multiscale propagation, nodes receive information from further m-hop neighbors rather than only immediate neighbors, which enlarges the effective range of message passing. It is similar with larger receptive field in convolutional neural networks. We prove that the effective range for receiving distant information is enlarged by using multiscale propagation.
Theorem 3. Given two nodes p and q are h-hop apart, using propagation with m-hop neighbors (i.e.,
Equation A J. if we perturb node features X.p pp of node p by A E Rm, the L2 norm of the change in node s equilibrium (Z is upper bounded as follows:
| S 7
L. (F)AX p.qll
(11)
The complete proof is provided in Appendix A.5
Similar to Corollary we analyse the effective range of multiscale propagation by considering when the change in the equilibrium of node q becomes smaller than certain numerical error.
Corollary 2. Using propagation with m-hop neighbors (i.e., Equation given any small error constant 0, the --effective range h < p can affect the equilibrium of nodes which are located up to In
mmnn8((1>]) Hence, the perturbation on node features of node m ml((01117))
In
-hop away from p.
This is the corollary of Theorem 3 the effective range is expanded by using multiscale propagation to consider m-hop neighbors in a propagation step.
The proof is given in Appendix A.5 Under the condition,
5.3 Training MGNNI
To train MGNNI, we can simply iterate Equation until it converges the equilibrium Z for the forward pass. We do not use closed-form solutions as in Liu et al. 20 since it would slow the training with large graphs and a large number of node features. For backward pass, given loss f, we can use implicit differentiation to compute the gradients of trainable parameters by directly differentiating through the equilibrium z" by:
de 0())
Ol (I - (z()))) 0x(Z".X,9) -
(12)
97.
0(.)
where 7' = ",",, 7g( () 7m
9X and Jz(Z") xx.9)
07 We provide the
complete derivation in Appendix A.6 One of advantages of directly differentiating through Z" is that the memory consumption only one layer regardless the number of iterative steps in forward pass. In contrast, differentiating over iterative steps requires large memory to store intermediate variables.
Note that ( (Z"))""))" in Equation 12 is expensive to compute due to the computation of the Jacobian (z*) and the inverse. However, we solve linear equation with a Vector-Jacobe product (VJP) achieve cheaper computation of 82 (I -z())))
de
u T== = Jo" + 07
(13)
Note that, the VJP aT Jz(Z") can be efficiently computed by automatic differentiation packages (e.g.. PyTorch (2 without forming the Jacobian. Subsequently, the gradients a(-)
øt can be obtained.
5.4 Discussion and comparison with previous implicit GNNs
In general, compared to previous implicit GNNs (i.e., IGNN IR EIGNN 20 and CGS 2 our model MGNNI brings multiscale modeling implicit GNNs, which allows the model capture graph information of different granularities. The multiscale idea has shown its effectiveness on explicit GNN models, such as N-GCN 22) JKNet 30,, and MixHop M. However, to our knowledge, there is no previous implicit GNNs able to capture graph information at various scales. Specifically, MGNNT essentially has multiple implicit layers with different focuses on various scales coexisting side by side.

---

Computational complexity MGNNI has similar time complexity with IGNN and CGS as they all use iterative methods to iterate Equation + until convergence. The asymptotic time complexity is O(K + hn²)) where h is the number of hidden units after the input transformation f(X, 9) and K is the number of iterations in an iterative method. In contrast, EIGNN costs O(n²) to conduct eigendecomposition for the adjacency S, which is costly and prohibitive for large graphs. Additionally, for training, it requires O + hīn)) to get the closed-form solution and O(h)) to conduct eigendecomposition for the weights, where h; is the number of input features. Comparing MGNNI and EIGNN, MGNNI is more efficient on large graphs as it utilizes iterative solvers for exed-point solutions, whereas EIGNN requires eigendecomposition to get closed-fore solutions.
The above analysis of computational complexity mainly considers the process of propagation. Here, we discuss the time complexity of some additional operations in these implicit GNNs, e.g., the attention mechanism in MGNNI and the projection on the weight matrix in IGNN, which generally cost much less time compared with the main propagation process. The attention mechanism used in MGNNI has the time complexity O hn + hn) (according to Equation D. where h is the number of hidden units in the attention module. Similarly, IGNN also has some additional operations, e.g., it requires a projection of the weight matrix W in each training iteration to ensure the well-posedness condition [WI] <
It needs Onn²) to get and modify the maximum row sum of W (i.e., () Overall, MGNNI has the same level of time complexity compared with IGNN and CGS.
6 Experiments
In this section, we show that MGNNI can effectively capture long-range dependencies and mixed graph information at various scales. Therefore, MGNNI provides better performance on both node classification and graph classification compared with representative baselines. Specifically, we conduct the experiment on 7 datasets for node classification (including synthetic and real-world datasets: Color-counting, Cornell, Texas, Wisconsin, Chamelcon, Squirrel, PPI) and 6 datasets (MUTAG, PTC, PROTEINS, NCII, IMDB-Binary, (MDB-Mult) for graph classification. As we follow the same experimental settings on some datasets, we reuse the results of some baselines from literatures. Descriptions of datasets and experimental settings are detailed in Appendix C
6.1 Experiments with synthetic datasets
Color-counting dataset We construct the synthetic dataset for node classification. The graph contains sev- eral chains and some nodes on each chain have different colors. The color information is encoded in node fea- tures. The nodes on the same chain share the same la- bel which is the majority color appeared on this chain.
MGNNI (M=(1))
(M.(1.4.8))
EIGNN
IGNI
Accurcy
CGS
The model is supposed to predict the majority color on chain, which requires the model able to capture the long-range dependencies and also count the occurrence of each color. In Figure 2 compare MGNNI with different scales against previous implicit GNN models (i.e., IGNN, FIGNN, and CGS). MGNNI (M=(1, (M)))) de- notes that three scales with m=1, m-4, and m=8 are used, MGNNI with higher exponents (i.e., M= M=(1.4.8) generally performs better than IGNN and CGS, which indicates that multiscale propagation with higher-hop neighbors can effectively expand the effective range for long-range dependencies. Note that MGNNI (M=(1)) can be regarded as MGNNI with only single scale. It is outperformed by MGNNI (M= 1.4,8)). which again shows the effectiveness of multiscale propagation. MGNNI (=(1)), I), IGNN and CGS are all outperformed by EIGNN, suggesting that implicit GNNs with iterative solvers may still suffer from approximation error issues. We also provide the comparison between MGNNI and representative explicit GNNs in Appendix C.I (See Figure
0.6
50
1000
125
350
175
200
Length of chain
Figure 2: Averaged accuracies on color- counting dataset.
5). It further demonstrates the superiority of MGNNI over explicit GNNs in terms the ability of capturing long-range dependencies.
'The implementation can be found https://gituub.oom/iijjeeee
7

---

Table Results on heterophilic graph datasets: mean accuracy (%) stdev over different data splits.
Cornell
Texas
Wisconsin
Chameleon
Squirrel
Nodes
183
183
251
2,277
5,201
# Edges
280
295
466
31,421
198,493
# Classes
5
5
5
5
Geom GCN 26
60.81
67.57
64.12
60.90
38.14 14
SGC
58.91 3.15
58.92 + 4.32
59.41 + 6.39
40.63 2.35
28.4 1.43
GCN
59.19 = 3.51
64.05 + 5.28
61.17 + 4.71
42.34 + 2.77
29.0 + 1.10
GAT
59.46 = 6.94
61.62 5.77
60.78 8.27
46.03 2.51
30.51 1.28
APPNP 18
63.78 = 5.43
64.32
3.331
43.85 + 2.43
30.67 + 1.06
JKNet 30
58.18 = 3.87
63.78:666
60.98 2.97
44.45 3.17
30.83 - 1.65
GCNII R
76.75 = 5.95
78.82 5.74
48.59 + 1.88
32.20 + 1.06
H2GCN
82.22 = 5.67
84.76 + 5.57
85.88 + 4.58
2.31 60.30
40.75 + 1.44
IGNN KK
61.35 = 4.84
58.37 + 5.82
53.53 + 6.49
41.38 + 2.53
24.99 + 2.11
EIGNN 20
85.13 = 5.57
84.60 + 5.41
86.86 + 5.54
62.92 1.59
46.37 = 1.39
CGS 21
68.11 = 9.41
62.97 + 9.23
63.53 9.81
40.57 + 1.61
31.78 + 0.89
MGNNI
85.95 6.10
84.86 + 5.91
86.67 + 4.31
63.93 + 2.21
54.50 + 2.10
Besides the experiments on Color-counting dataset, following Liu et al. 20. we also conduct synthetic experiments on Chains dataset. MGNNI and EIGNN both maintain 100% test accuracy, demonstrating the advantages of capturing long-range dependencies. The results and detailed analyses can be found in Appendix C.T and Figure
6.2 Experiments with real-world datasets
Node classification Apart from the synthetic experiments, following Pei al. 2 experiments on 5 heterophilic datasets (Cornell, Texas, Wisconsin, Chameleon, and Squirrel) for node classification. On heterophilic graphs, the nodes with different class labels tend be connected, which requires models to aggregation information from distant nodes. These graph datasets are web-page graphs of the corresponding universities or the corresponding Wikipedia pages. We use the standard train/test/val splits as in Pei et al. 23 See the detailed setting in Appendix C22
we also conduct
The results are shown in Table T MGNNI generally achieves the best performance most datasets. Comparing MGNNI and EIGNN, MGNNI provides better results, especially on Chameleon and Squirrel, which indicates that MGNNI has the superior ability of capturing long-range dependencies and multiscale information. Among implicit GNN baselines, EIGNN outperforms IGNN and CGS, which might attributed to the less approximation error the closed-form solution of EIGNN. Among explicit GNN baselines, H2GCN and GCNII are usually better than others, suggesting that the aggregation design in H2GCN and deeper models with residual connections are helpful on heterophilic graphs.
In addition, we also evaluate MGNNI on Pootein-Protein Inter- action (PPI) dataset which have multiple graphs. On each graph, proteins are presented nodes and edges are formed there is an interaction between two proteins. The task is to predict node labels multi-label multi-graph inductive setting. The same train/val/test split are used as in Hamilton et al. 14]. Table reports the micro-Fl scores of MGNNI against other baseline models. Compared to IGNN and EIGNN, MGNNI achieves 1.1% and 0.7% absolute improvement respectively by effec- tively capturing underlying multiscale information and long- range dependencies between proteins. Unlike IGNN having implicit layers sequentially stacked, on PPI dataset, MGNNI re- sorts to parallel equilibrium layers with different scales, which makes MGNNI more efficient than IGNN. We report the effi- ciency comparison between MGNNI and other implicit GNNs in Appendix 4
Table 2: Multi-lahel node classifi- cation on PPI: Micro-FI (%).
Method
Micro-F1
GCN 17
59.2
GraphSAGE 14
78.6
SSE
83.6
GAT
27
97.3
JKNet 30
97.6
IGNN
13
97.6
EIGNN 20
98.0
MGNNI
98.7

---

Table 3: Mean accuracy (%) stdev over 10 folds on real-world datasets for graph classification.
MUTAG
PTC
PROTEINS
NCI1
IMDB-B
IMDB-M
# Graphs
188
344
1113
4110
1000
1500
Avg # Nodes
17.9
25.5
39.1
29.8
19.8
13.0
# Classes
2
2
2
3
GCN
177
85.6 = 5.8
64.2 + 4.3
76,0 = 3.2
80.2 + 2.0
GIN
89.0 6.0
63.7 + 8.2
75.9 + 3.8
82.7 1.6
75.1 + 5.1
52.3 + 2.8
DGCNN
33
85.8
58.6
75.5
74.4
70.0
47.8
FDGNN
88.5 + 3.8
63.4 + 5.4
76.8 +2.9
77.8 1.6
72.4 + 3.6
50.0 + 1.3
IGNN 13
89.3 + 6.7
70.1 + 5.6
77.7 + 3.4
80.5 + 1.9
EIGNN 20
88.9 = 1.1
69.8 5.3
75.9 - 6.4
77.5 2.2
72.3 - 4.3
52.1 + 2.9
CGS A
89.4 + 5.6
64.7 + 6.4
76.3 + 6.3
77.2 + 2.0
73.1 + 3.3
51.1 + 2.2
MGNNI
91.9 = 5.5
72.1 + 2.8
79.2 + 2.9
78.9 + 2.1
75.8 + 3,4
53.5 + 2.8
Graph classification Besides node classification, we conduct experiments on graph classification tasks, using four bioinformatics datasets (MUTAG, PTC, PROTEINS, NCI) 32 and two social- network datasets (IMDB-Binary and IMDB-Multi). 10-fold Cross-validation is conducted as Ki and the averaged accuracies with standard deviations are reported in Table B The results of baselines are borrowed from Gu et al. [S] and Park et al. (2T]. In general, compared with other implicit and explicit baseline models, MGNNI achieves the best performance on 3 out of 4 bioinformatics datasets and both two social-network datasets. This shows that the ability to capture long-range dependencies and multiscale information is helpful for graph classification and can be generalized to test graphs in the inductive setting.
6.3 Ablation Study
To further investigate the effectiveness of multiscale mod- cling and the contributions different scales, we conduct the ablation study using different MGNNI variants with various scale combinations. As shown in Table 4 com- pared to variants with single scale (i.e., (1), (2) and (3)), multiscale variants generally achieve better performance on all three datasets. This verifies that multiscale model-
Table 4: Performance different scales.
Scales
PPI
Chameleon
Texas
[1]
98.35
61.46
81.35
(2)
94.62
58.24
82.97
(3)
88.56
56.07
83.78
ing is effective and plays an important role in capturing
(1,2)
98.67
63.93
83.24
graph information at various scales. Comparing variants
[1,2,3)
98.74
63.75
84.86
with single scale, the variant utilizing 1-hop propagation performs best on PPI and Chameleon, whereas the variant with only 3-hop propagation obtains the best performance on Texas. This demonstrates that informa- tion a certain scale can be more important than others on graphs with different properties. Merely considering 1 I-hop propagation as in previous implicit GNNs might lead to sub-optimal performance.
Besides the overall performance of different vari- ants, in Figure g we also demonstrate the at- tention values of 100 randomly sampled nodes using MGNNI with scales {1, 3} on PPI and Chameleon. Most of the nodes chameleon tend to have high attention weights on the first scale and rarely have attentions on the third scale, whereas some nodes on PPI have relatively higher atten- tion values on the third scale than the first scale. Moreover, compared to Chameleon, there are more nodes on PPI prefer the second and the third scale. These phenomena verify the effectiveness of the at- tention module MGNNI, and show that different nodes might prefer information at different scales according to the graph property. Additionally, we also conduct the ablation study on the effect the attention mechanism in MGNNI (see Appendix C.5
scales
P9
scates
Chameleon
Figure 3: Attention weights of nodes at different scales on PPI and Chameleon.

---

7 Conclusion
In this paper, we provide theoretical analyses on the constrained expressiveness of previous implicit GNNs due to the limited effective range for capturing distant information. We propose MGNNI which has an expanded effective range and the ability to learn mixing graph information at various scales. With synthetic experiments, we show that MGNNI with a large effective range has a better capacity to capture long-range dependencies. On various real-world datasets for both node classification and graph classification, MGNNI demonstrates superior performances compared with representative baselines, showing the effectiveness of multiscale modeling. Furthermore, the ablation study also shows that MGNNI allows different nodes to have different scale preferences, which plays an important role in adaptively capturing graph information at various scales.
Although MGNNI has the advantages of capturing multiscale graph information, MGNNI also has the limitation on potential approximation errors introduced in the iterative method as IGNN and CGS. EIGNN gets rid of these errors by using a closed-form solution with cigendecomposition which prohibits its usage on large graphs. How to mitigate approximation errors while ensuring the scalability on large graphs could be an interesting topic for future work.
Acknowledgments and Disclosure of Funding
We would like to gratefully thank the insightful feedback and suggestions from the anonymous reviewers. We also appreciate their engagement during the discussion period. This work was supported by Proximate Beta (Grant No. A A-8000117-00-00) 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] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Conference Machine Learning. 2019.
[2] Sami Abu-El-Haija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-gen: Multi-scale graph convolution for semi-supervised node classification. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, 2020.
[3] Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as layer in neural networks. International Conference on Machine Learning, 2017.
[4] Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, 2019.
[5] Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale deep equilibrium models. In Advances Neural Information Processing Systems, 2020.
[6] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzaez- Vinicius Zambaldi. Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1rXivv1806.01261 2018.
[7] Abraham Berman and Robert. J Plemmons. Nonnegative matrices in the mathematical sciences. SIAM, 1994.
[8] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.
[9] Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alex Smola, and Le Song. Learning steady-states of iterative algorithms over graphs. In Proceedings of the 35th International Conference Machine Learning, 2018
[10] Claudio Gallicchio and Alessio Micheli, Fast and deep graph neural networks. Proceedings of the AAAI conference artificial intelligence, 2020.
10

---

[11] Zhengyang Geng, Xin-Yi Yu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. In Advances in Neural Information Processing Systems. 2021.
[12] Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible residual network: Backpropagation without storing activations. 2017.
[13] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems, 2020.
[14] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, 2017.
[15] Kenji Kawaguchi. On the theory of implicit deep learning: Global convergence with implicit layers. In International Conference Learning Representations (ICLR), 2021.
[16] Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), 2015.
[17] Thomas N Kipf and Max Welling. Seni-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2016.
[18] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
[19] Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, 2021.
[20] 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.
[21] Junyoung Park, Jinhyun Choo, and Jinkyoo Park. Convergent graph solvers. In International Conference on Learning Representations, 2022.
[22] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
[23] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations, 2020.
[24] Zaccharie Ramzi, Florian Mannel, Shaojie Bai, Jean-Luc Starck, Philippe Ciuciu, and Thomas Moreau. SHINE: SHaring the INverse estimate from the forward pass for bi-level optimization and implicit models. In International Conference on Learning Representations, 2022.
[25] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 2021.
[26] Aravind Subramanian, Pablo Tamayo, Vamsi K Mootha, Sayan Mukherjee, Benjamin L Ebert, Michael A Gillette, Amanda Paulovich, Scott L Pomeroy, Todd R Golub, Eric S Lander, et al. Gene set enrichment analysis: a Enowledge-based approach for interpreting gede expression profiles. Proceedings of the National Academy of Sciences. 2005.
[27] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations, 2018.
[28] Felix WU, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, 2019.

---

[29] 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.
[30] 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.
[31] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[32] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, 2015.
[33] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thiirty-second AAAI conference on artificial intelligence,
2018.
[34] 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 Neural Information Processing Systems, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss the limitations our
conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] They are included in Appendix
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or as a URL)? [Yes] Appendix C
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In Appendix C
(c) Did you report eтror bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] We report standard deviations.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C
you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] We only use public datasets and code.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We include our code in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applica-
ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vmXK8y0cpan", "reviewer": "Reviewer_Ap6e", "summary": "In this paper, the authors propose implicit GNN with an effective range concept.\n\nWhile previous implicit GNNs can be treated as neural networks with infinite layers sharing the same weights, MGNNI can exploit long-range dependencies capturing multi-scale information.\n\nThe $\\gamma$ control can constrain the expressiveness of GNNs via effective range.\n\nFor multi-scale information, they exploit a set of scales $M$ and corresponding equilibriums $Z$.\n\nThe model is optimized in an iterative manner, not a closed-form solution because of the slow training speed over large graphs or a large number of node features.\n\nMGNNI has comparable time complexity with IGNN and CGS because of the iterative method for convergence but it is more efficient than EIGNN which exploits eigendecomposition.", "questions": "-", "limitations": "The authors adequately addressed the limitations. While MGNNI can capture multi-scale information, there is a limitation from potential approximation error as other iteration-based methods such as IGNN and CGS.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Implicit GNNs are getting more and more attention as one of the ways to complement the existing message-passing paradigm.\n\nHowever, the researches for implicit GNNs are not plentiful that much compared to other explicit architectures.\n\nThe concept of effective range and the corresponding set of multiple scales with equilibriums might be akin to multi-hop aggregation of existing message passing GNNs such as ChebNet and SGC.\n\nUsing multiple propagation modules for multi-scale information may seem a bit naive, but I think it's well worth a try.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lF3Wn6zVBI-", "reviewer": "Reviewer_apvj", "summary": "In this paper, the authors analyze the \"infinite effect\" in implicit GNNs, and give the theoretical bound of the \"effective range\". Additionally, the authors extend the implicit GNNs with multi-scale ability plus the \"effective range\" analysis. The whole paper is complete, and the experiment results are promising.", "questions": "1. For the first question, please refer to the first bullet point in the Limitations section.\n\n2. In experiments, when a single scale is executed in MGNNI, is the attention mechanism in Eq. (7) - (10) still applied?", "limitations": "1. The definition of multi-scale is not clear and needs to be specified. In the current version, from lines 48 to 57, the authors listed four related works and illustrated two of them. Just describing them could not lead to a clear understanding of multi-scale, and more especially, why [8] is a multi-scale method? A more straightforward question here can be like: does stacking GNN layers qualify as a multi-scale method? Or the scale of each node feature aggregation needs to be personalized could qualify as a multi-scale method?\n\n2. Authors may want to be more careful about the statements from lines 38 to 47. A suggestion here is to highlight and well-define the term \"effective\". Because of the Theorem 1 and its proof, the effect still exists even though it is bounded by a small value, and the threshold $\\theta$ is hand-crafted.\n\n3. I am wondering about the role of the attention mechanism in outstanding experimental performance. The ablation studies could better consider removing the attention part.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The flow of the paper is clear and well-written.\n2. This paper gives a solid analysis of the implicit GNNs for their effective range. For dealing with the multi-scale problem for implicit GNNs, this paper proposes the MGNNI model with theoretical analysis.\n3. The experiments are extensive.\n\nWeaknesses\n1. Some parts of paper can be reconsidered like the definition, derivation, and the experiments. For details and improvement suggestions, please refer to the following \"Limitations\" section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "crcSROoX_E", "reviewer": "Reviewer_wdFc", "summary": "The paper points out a main draw back of existing implicit graph neural network — its limited effective range. Although implicit graph neural network has implicitly infinite depth and infinite large reception field, the influence between two nodes decays exponentially with distance along the graph, so it still cannot capture long range information well. The paper propose to alleviate the problem by multi-scale propagation, which utilize adjacency matrix with different powers to propagate info, and finally fuse propagation results of different scales by attention mechanism.  ", "questions": "## About theorem 3:\n1. eq. (11) has nothing to do with function $f(X, \\mathcal{G})$ in eq. (4), which is strange. If I am correct, only when $f(X, \\mathcal{G})=X$, theorem 3 holds.\n2. If we replace $S$ in Theorem 1 by $S^m$, we can get following upper bound: \n$$\\lVert\\Delta Z^*_{:,q}\\rVert \\le \\frac{\\gamma^h}{1-\\gamma}\\lVert g^h(F)\\Delta X_{:,P} S^{hm}_{p,q}\\rVert$$ \n- It seems to be a tighter bound than theorem 3 (I am not sure), because $\\gamma, g(F)$ and $S_{p,q}$ are less than 1, above formula has higher power on them, and thus the upper bound is tighter.\n- If above upper bound is tighter, then Corollary 2 will become same as Corollary 1, and thus the effective range remains unchanged even with multi-scale propagation. If am wrong, please correct me.\n\n## About motivation:\n\nDo we really need so called \"long range information\" in real world applications? \n- In my opinion, locality is is not a drawback of Graph Neural Networks, or more generally, it is not a drawback of convolutional neural networks, including both CNN in image domain and GCN in graph domain. Instead, it is the key why CNN outperforms MLP and why GCN works. Nearby neighbourhood always has much more importance than nodes/pixels far away, because they are the nodes that closely related to the centre nodes/pixels. \n- Even if someone take it as a drawback, their methods still assign more importance to nearby neighbourhood. Nobody tries to give more importance to nodes far away than nearby ones, because that is not reasonable. Take the proposed method as an example, the influence between two nodes still decays exponentially with distance. \n- Experimental results also favours my opinion. In real word dataset, the proposed method performs similar as EIGNN, which does not consider multi-scale propagation. Only in handcrafted dataset designed for long range information, the proposed method outperforms EIGNN by a large margin.\n\nThis part about motivation is not a question, but a discussion. It is OK for you not to response. ", "limitations": "No special negative societal impact. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. the paper is well motivated, well written and easy to follow. \n2. The drawback of IGNN is demonstrated by both theoretical analysis and experimental proofs.\n3. The effectiveness of proposed method is also demonstrated by both theoretical analysis and experimental proofs.\n\nWeakness:\n1. The modification does not thoroughly overcome the drawback, but just alleviate it instead. Although effective range becomes $m$ times larger, the influence between two nodes still decays exponentially with distance along the graph in the proposed method. \n2. The proposed methods outperforms EIGNN by a large margin only in synthesized data, and behaves similarly as EIGNN in real world dataset.\n3. I doubt the correctness and meaningfulness of some theorem, and expect explanations from authors. See my questions below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "AWuSsrVIDaI", "reviewer": "Reviewer_Ctvi", "summary": "This paper proposes a new variant of implicit graph neural network MGNNI, which is a new type of graph neural networks that captures the long-range dependencies in underlying graphs. The authors first conduct theoretical analysis on the two weaknesses of previous implicit graph neural networks, namely limited effective range for capturing distant information and constrained ability of capturing multiscale information. They then show that MGNNI with multiscale propagation could expand the effective range and capture various-scale graph information. Experiments on both synthetic dataset and real-world graphs demonstrate the effectiveness of MGNNI.", "questions": "- Could IGNN/EIGNN/CGS with jumping knowledge connection effectively capture multiscale information on graphs? This is a interesting baseline to further demonstrate the effectiveness of the design of MGNNI.\n- How do implicit graph neural networks such as IGNN that don’t rely on contraction factor \\gamma to ensure convergence be included in the theoretical analysis framework?\n- How do the multiscale propagation and attention mechanism used in MGNNI affects its computational analysis?\n- Does MGNNI face the over-smoothing problem?\n- How does MGNNI perform on massive graphs and other types of graphs such as social networks?\n", "limitations": "Limitations are addressed in the Conclusion, but the assumption that used in theoretical analysis should be also highlighted.\n\nNo potential negative societal impact is discussed, which is fair for a methodological contribution to a well-studied problem.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is easy to follow with a clear motivation and closely related to the NeurIPS community with comprehensive experimental and theoretical analysis.\n- Theoretical analysis comparison on the effective range of previous implicit GNNs and MGNNI are important and sufficient.\n- The current paper might have certain impact as it further explores a mild trend in the literature, which investigates the theoretical analysis of implicit graph neural networks.\n\nWeakness:\n- The theoretical analysis has the assumption that a contraction factor \\gamma is used to ensure convergence in the aggregation step, which is not used in all implicit graph neural networks. This should be highlight in limitations. \n- The computational complexity for IGNN and CGS should be included for clearer comparison. How the multiscale propagation and attention mechanism used in MGNNI affects its computational analysis is missed.\n- While the implicit graph neural networks are also known for effectively alleviate the over-smoothing problem for many GNNs, how MGNNI handles this over-smoothing problem should be discussed.\n- For experiments, I noticed that the benchmarks used for evaluation are relatively small graphs with nodes less than 10K. While the efficiency of MGNNI is claimed as an advantage over many other SOTA implicit graph neural networks, I am curious about how the performance is on larger datasets such as OGB.\n- Only four small-scale bioinformatics datasets are used in the graph classification evaluation and it is a known problem with those small and noisy datasets. It is encouraged to include other types of graphs such as social networks for more convincing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept