Gradient Gating for Deep Multi-Rate Learning on Graphs
Authors: T. Konstantin Rusch
Benjamin Paul Chamberlain
Michael W. Mahoney
Michael M. Bronstein
Siddhartha Mishra
Venue: ICLR 2023 poster (2023)
Keywords: GNNs
message-passing
oversmoothing
heterophilic graphs
multi-rate learning
gating
large graphs

Abstract: We present Gradient Gating (G$^2$), a novel framework for improving the performance of Graph Neural Networks (GNNs). Our framework is based on gating the output of GNN layers with a mechanism for multi-rate flow of message passing information across nodes of the underlying graph. Local gradients are harnessed to further modulate message passing updates. Our framework flexibly allows one to use any basic GNN layer as a wrapper around which the multi-rate gradient gating mechanism is built. We rigorously prove that G$^2$ alleviates the oversmoothing problem and allows the design of deep GNNs. Empirical results are presented to demonstrate that the proposed framework achieves state-of-the-art performance on a variety of graph learning tasks, including on large-scale heterophilic graphs.

Published as a conference paper at ICLR 2023
GRADIENT GATING FOR DEEP MULTI-RATE LEARNING ON GRAPHS
T. Konstantin Rusch
Benjamin P. Chamberlain
ETH Zürich, ICSI and UC Berkeley konstantin, rusch@san math ethz. ch
Charm Therapeutics
Michael W. Mahoney ICSL, LBNL, and UC Berkeley
Michael M. Bronstein University of Oxford
Siddhartha Mishra ETH Zürich
ABSTRACT
We present Gradient Gating (G²), a novel framework for improving the perfor- mance of Graph Neural Networks (GNNs). Our framework is based on gating the output of GNN layers with a mechanism for multi-rate flow of message passing information across nodes of the underlying graph. Local gradients are harnessed to further modulate message passing updates. Our framework flexibly allows one to use any basic GNN layer as wrapper around which the multi-rate gradient gating mechanism is built. We rigorously prove that G2 alleviates the oversmoothing problem and allows the design of deep GNNs. Empirical results are presented demonstrate that the proposed framework achieves state-of-the-arr performance on variety of graph learning tasks, including large-scale heterophilic graphs.
INTRODUCTION
Learning tasks involving graph structured data arise in a wide variety of problems in science and
engineering. Graph Neural Networks (GNNs) (Sperduti) 1994 Goller & Kuchler 1996 Sperduti
& Starita 1997
Frasconi et al. 1998 Gori et al. 2005 Scarselli et al.]| Bruna et al. 2014]
Defferrard et al. 2016 Kipf & Welling 2017 Monti al. 2017 Gilmer al. 2017) are a popular
deep learning architecture for graph-structured and relational data. GNNs have been successfully applied in domains including computer vision and graphics (Monti et al. 2017), recommender
systems (Ying et al.) 2018), transportation (Derrow-Pinion et 2021), computational chemistry (Gilmer et al., 2017). drug discovery (Gaudelet et al. 2021), particle physics (Shlomi et al. 2020) and social networks. See Zhou et al. (2019); Bronstein et al. (202I) for extensive reviews.
Despite the widespread success of GNNs and plethora of different architectures, several fundamental problems still impede their efficiency realistic learning tasks. These include the bottleneck AAln
Yahav/ (222)) oversquashing (Topping et al., (222)), and oversmoothing (Nt & Machara, 2019
Oono & Suzuki 2020) phenomena. Oversmoothing refers the observation that all node features in a deep (multi-layen GNN converge to the same constant value as the number of layers is increased.
Thus, and in contrast to standard machine learning frameworks, oversmoothing inhibits the use of very deep GNNs for learning tasks. These phenomena are likely responsible for the unsatisfactory empirical performance of traditional GNN architectures heterophilic datasets, where the features or labels of node tend to be different from those of its neighbors (Zhu et al. 2020).
Given this context, our main goal present novel framework that alleviates the oversmoothing problem and allows one to implement very deep multi-layer GNNs that can significantly improve performance the setting of heterophilic graphs. Our starting point is the observation that in standard Message-Pa Passing GNN architectures (MPNNs), such as GCN (Kipf & Welling, (017) or GAT /Velickovic et al., 2018), each node gets updated at exactly the same rate within every hidden layer. Yet, realistic learning tasks might benefit from having different rates of propagation (flow) of information on the underlying graph. This insight leads to a novel multi-rate message passing scheme capable of learning these underlying rates. Moreover, we also propose a novel procedure that harnesses graph gradients to ameliorate the oversmoothing problem. Combining these elements leads new architecture described in this paper, which term Gradient Gating (G2).

---

Published as a conference paper at ICLR 2023
Main Contributions. We will demonstrate the following advantages of the proposed approach:
G2 is a flexible framework wherein any standard peassage-passingg layer (such as GAT, GCN, GIN, GraphSAGE) can be used as the coupling function. Thus, it should be thought of framework into which one can plug existing GNN components. The use of multiple rates and gradient gating facilitates the implementation of deep GNNs and generally improves performance.
G² can be interpreted as a discretization of dynamical system govemnd by nonlinear differential equations. By investigating the stability of Rero-Dirichlet energy steady states of this system, we rigorously prove that our gradient gating mechanism prevents oversmoothing. To complement this, we also prove a partial converse, that the lack of gradient gating can lead to oversmoothing.
We provide extensive empirical evidence demonstrating that G² achieves state-of-the-art perfor- mance on a variety of graph learning tasks, including on large heterophilic graph datasets.
2 GRADIENT GATING
Let (V. be an undirected graph with V = o nodes and |8| = e edges (unordered pairs of nodes {i.j} denoted i j). The 1-neighborhood of node i is denoted NN = {i E V:io j). Furthermore, each node is endowed with an m-dimensional feature vector X;; the node features arranged into
matrix X (Xi)) with l....: e and k = =, m..
typical residual Pesssae-PPassing GNN (MPNN) updates the node features by performing several iterations of the form,
X" X + (Fo( 99)),
where Fg is learnable function with parameters 8, and is an element-wiss non-lineed activation function. Here n 2 1 denotes the n-th hidden layer with n = 0 being the input.
One interpret I as a discrete dynamical system in which F plays the role of coupling function determining the interaction between different nodes of the graph. In particular, we consider local (I-neighborhood) coupling of the form Y, (X, 9)); F(,,, |[ {()jeN:B B) operating on the multiset of I-neighbors of each node. Examples of such functions used in the graph machine learning literature (Bronstein et al. 2021) are graph convolutions Y, EyEN, C, (GCN, Kipf & Welling
2017 and gruph atlention Y, =EEEN a(X;, X,,,,, (GAT, (Velickovic et al. 2018))
We observe that in [ each hidden layer, every node and every feature channel gets updated with exactly the same rate. However, it is reasonable to expect that in realistic graph learning tasks one can encounter multiple rates for the flow of information (node updates) on the graph. Based on this observation, we propose multi-rate (MR) generalization of ( allowing updates to each node of the graph and feature channel with different rates,
X (1 - 7)) @ x @ a
where T denotes a V X m matrix of rates with elements TiA [0. 1]. Rather than fixing T prior to training, we aim learn the different update rates based on the node data and the local structure of the underlying graph G, as follows
"(X""1 () 7"X"-1,99
where Fg is another learnable 1-neighborhood coupling function, and ō is a sigmoidal logistic activation function constrain the rates lie within [0, 1]. Since the multi-rate message-passing scheme 2 using () does not necessarily prevent oversmoothing (for any choice of the coupling function), we need to further constrain the rate matrix T". To this end, we note that the graph
gradient of scalar node features y on the underlying graph G is defined as (Vy);j y; -yyyyyy y; at the edge i ~ [Lim 2015). Next, we will use graph gradients obtain the proposed Gradient Gating (G2) framework given by
4"h = [Fo((X" ,9)),
+ tanh
(4)
3k
JEN,
X (1 -1
3 X n- + (o(Fo(X
2

---

Published as a conference paper at ICLR 2023
where 7jz F (V+*k) by denotes the graph-gradient and +% is the k-th column of the rate matrix 4" and p O. Since Σjex, 17 + P 2 for all E it follows that T" E [0, 1 1 for all n, retaining its interpretation as a matrix of rates. The sum over the neighborhood A, in (4) can be replaced by any permutation-invaaiian aggregation function (e.g., mean or max). Moreover, any standard message-passingg procedure can be used to define the coupling functions F and (and, in particular, one can set F F). As an illustration, Fig. shows schematic diagram of the layer-wise update of the proposed G² architecture.
X
GNN
VII
tanh
GNN
Figure 1: Schematic diagram of G² 4 showing the layer- wise update of the latent node features X (at layer n). The norm of the graph-gradien (i.e., sum in second equation in denoted as [
4
The intuitive idea behind gradient gating in (4 is the following: If for any node V local oversmoothing occurs, i.e., lim LjEN; [ -XpIl
[|||= = O, then G2 ensures that the corresponding rate T," goes to zero (at a faster rate), such that the underlying hidden node feature X; is no longer updated. This prevents oversmoothing by early-stopping of the message passing procedure.
PROPERTIES OF G2-GNN
G2 is a flexible framework. An important aspect of G2 4 is that can be considered as a "wrapper" around any specific MPNN architecture. In particular, the hidden layer update for any form of message passing (e.g., GCN (Kipf & Welling 2017). GAT (Velickovic et al. 2018). GIN (Xu et al.
2018) or GraphSAGE (Hamilton et al. setting I, reduces
2017 can be used as the coupling functions F, F in (4). By
X = (F,(X~11g))
(5)
standard (non-uesidual) MPNN. As we will show in the following, the use of non-trivial gradient- gated learnable rate matrix allows implementing very deep architectures that avoid oversmoothing.
Maximum Principle for node features. Node features produced by G² satisfy the following Maximum Principle.
Proposition 3.1. Let X be the node feature matrix generated by iteration formula (4) Then, the features are bounded as follows:
min (-1,g) < X S max (1,7), V1 $ n,
(6)
where the scalar activation function is bounded by S (z)))= S O for all R.
The proof follows readily from writing component-wise and using the fact that 0 < T < for all < i v, < k: < and 1
Continuous limit of G It has recently been shown (see Avelar et al. (2019):
: Poli et al.
2019
Zhuang et al. (2020); Xhonneux et al.] (2020); Chamberrlin et al. (2021a); Elhasof et al. 202 )
Chamberlain et al. (2021b); Topping et al. (2021) Rusch et al. (2022a) and references therein)
3

---

Published as a conference paper at ICLR 2023
that interesting properties of GNNs (with residual connections) can be understood by taking the continuous (infmite-depth)) limit and analyzing the resulting differential equations.
In this context, derive continuous version of (4 by introducing small-scale 0 < At < 1 and rescaling the rate matrix T" to Att" leading to
X
Atr x"
Att od (Fo(X"-1,g))
Rearranging the terms in
we obtain
X X
=
( -x--))
At
Interpreting X ((ntt) (("),, i.e. marching in time, corresponds increasing the number
of hidden layers. Letting Al + O, one obtains the following system of graph-coupled ordinary differential equations (ODEs):
(1
T (t) o (F((((1).)) - X(t)), A1 #20 0,
dt
(t) tanh
Σ (t) (x)(
(9)
EEAL
+t) a (( 9)). .9))
We observe that the iteration formula (4) acts as forward Euler discretization of the ODE system ( Hence, one can follow Chamberlain et al. (2021a) and design more general (e.g., higher-order, adaptive, or implicit) discretizations of the ODE system (9) All these can be considered as design extensions of
Oversmoothing. Using the interpretation of 4 discretization of the ODE system (9. can adapt the mathematical framework recently proposed in Rusch et al. (2022a) to study the oversmoothing problem. In order to formally define oversmoothing, introduce the Dirichlet energy defined on the node features X of an undirected graph 9 as
E(X) -
X - X,112
(10)
SEV JEM;
Following Rusch et al. (2022a), say that the scheme p oversmoothes if the Dirichlet energy decays exponentially fast,
((X(t)) S Cie
0,
(1I)
for some C1.2 > O. In particular, the discrete version of 1II implies that oversmoothing happens
when the Dirichlet energy, decays exponentially fast as the number hidden layers increases (Rusch al. 2022a) Definition 3.2).
Next, one can prove the following proposition further characterizing oversmoothing with the standard terminology of dynamical systems (Wiggins 2003).
Proposition 3.2. The oversmoothing problem occurs for the ODES (9) iff the hidden states X for all i are exponentially stable steady states (fixed points) of the ODE for some c IR...
In other words, for the oversmoothing problem occur for this system, all the trajectories of the ODE (9) that start within the corresponding basin attraction have to converge exponentially fast in time (according (Th) to the corresponding steady state c. Note that the basins of attraction will be different for different values of c. The proof of this Proposition is a straightforward adaptation of the proof of Proposition 3.3 of Rusch al. (2022a).
Given this precise formulation of oversmoothing, we will investigate whether and how gradient gating 9 can prevent oversmoothing. For simplicity, we set m to consider only scalar node features (extension to vector node features is straightforward). Moreover, we assume coupling functions of the form F A expressed element-wing as (see also Chamberlain al. (2021a); Rusch
et al. 22022a))
(F(X)); Σ A(X,, JEV.
(12)
4

---

Published as a conference paper at ICLR 2023
Here, (X) is matrix-valued function whose form covers many commonly used coupling functions stemming from the graph attention (GAT, where Aúj A x)) is learnable) or convolution operators (GCN, where A, is fixed). Furthermore, the matrices right stochastic, i.e., the entries satisfy
0 OSA, S1, ΣA, =1.
(13)
JEN;
Finally, as the multi-rate feature of (9) has no direct bearing on the oversmoothing problem, we focus on the contribution of the gradient feedback term. To this end, we deactivate the multi-rate aspects and assume that f: = X, for all i E V, leading to the following form of (9):
dt.(t)
(t)
o Σ
X -x((0)
vt 2 0,
dt
JEN;
(14)
(t) = tanh
Σ JEN.
xX, - x.(PP))) -x,00)-((0)))))
Lack of G2 can lead to oversmoothing. We first consider the case where the Gradient Gating is switched off by setting p 0 in (14). This yields standard GNN in which node features are evolved through message passing between neighboring nodes, without any explicit information about graph gradients. We further assume that the activation function is ReLU i..., (x) max(x,, 0). Given this setting, we have the following proposition on oversmoothing:
Proposition 3.3. Assume the underlying graph G is connected. For any 2 O, let X; = c, for all i E V be a Diirichet energy) steady state of the ODEs 14). Moreover, assume no Gradient Gating (p = 0 in (4)) and
(15) with 0 a S and that there exists at least one node denoted w.L.o.g. with index such that (t) for all 2 0. Then, the steady state X; for all i V, of (14) is exponentially stable.
Anlcc,, and Au(c,c)2a, isijse,
can lead oversmoothing. The proof, presented in SM C.I relies on analyzing the time-evolution of small perturbations around the steady state c and showing that these perturbations decay exponentially fast in time (see (20).
Proposition 3.2 implies that without gradient gating (G²). (9)
G2 prevents oversmoothing. We next investigate the effect of Gradient Gating in the same setting of Proposition 3.3 The following Proposition shows that gradient gating prevents oversmoothing: Proposition 3.4. Assume the underlying graph G is connected. For any 2 0 and for all i e V, let X; = c be a kero--iriichler energy) steady state of the ODEs (4). Moreover, assume Gradient Gating (p > 0) and that the matrix A in denoted w.l.o.g. with index such that X (t) = c, for all tllt Then, the steady state X; for all i E V is not exponentially stable.
(14 satisfies (15) and that there exists at least one node
The proof, presented in SM C.2 clearly elucidates the role of gradient gating by showing that the energy associated with the -inaii--ieerizeed evolution equations (SM Eqn. (21) is balanced by two terms (SM Eqn. (3)), both resulting from the introduction of gradient gating by setting p > 0 in (14). One of them is of indefinite sign and can even cause growth of perturbations around steady state c. The other decays initial perturbations. However, the rate of this decay is at most polynomial (SM Eqn. (28)). For instance, the decay is merely linear for
2 and slower for higher values of p. Thus, the steady state e cannot be exponentially stable and oversmoothing is prevented. This justifies the intuition behind gradient gating, namely, if oversmoothing occurs around node i, i.e., lim,,+oo ΣjEN; ||X,- - I = O, then the corresponding rate т;" goes to zero (at a faster rate), such that the underlying hidden node feature X, stops getting updated.
EXPERIMENTAL RESULTS
In this section, present experimental study of G on both synthetic and real datasets. We use G with three different coupling functions: GCN (Kipf & Welling 2017). GAT /Velickovic et al. 2018) and GraphSAGE (Hamilton al. 2017).
5

---

Published as a conference paper at ICLR 2023
Effect of G2 on Dirichlet energy. Given that oversmoothing relates to the decay of Dirichlet energy (II). we follow the experimental setup proposed by Rusch et al. (202aa) to probe the dynamics of the Dirichlet energy of Gradient-Gate GNNss defined 2-dimensional 10 x 10 regular grid with 4-neighbor connectivity. The node features X are randomly sampled from 2/[[0, 1]) and then propagated through 1000-layer GNN with random weights. We compare GAT, GCN and their gradient-gated versions -GT and G²-GCN) in this experiment. Fig. 2 depicts on log-log scale the Dirichlet energy of each layer's output with respect to the layer number. We clearly observe that GAT and GCN oversmooth as the underlying Dirichlet energy converges exponentially fast to practice, the Dirichlet energy
zero, resulting in the node features becoming indistiguuisable. for these architectures is R 0 after just ten hidden layers. On the other hand, and as suggested by the theoretical results of the previous section, adding G2 decisively prevents this behavior and the Dirichlet energy remains (near) constant, even for very deep architectures (up to 1000 layers).
Tex sccuracy 7
10-1
60
GN-GCN
GR-GNN
10-11
GCN
GCN dropEdge
10
GAG
80
GCN-GrophCON
GAT
res. ren-GCN
10
100
1000
16
32
64
128
Lager 10
Number of layers
) of laser-wise node features X propagated through GAT, GCN and their gradient gated versions GGT, G²-GCN).
Figure 2: Dirichlet energy (X")
Figure 3: Test accuracies of GCN with gradient gating (G2-GCN) as well as plain GCN and GCN combined with other methods on the Cora dataset for increasing number of layers.
G for very deep GNNs. Oversmoothing inhibits the use of large number of GNN layers. As G² is designed to alleviate oversmoothing, it should allow very deep architectures. To test this assumption, reproduce the experiment considered in Chamberlain al. (2221a: node-level classification task on the Cora dataset using increasingly deeper GCN architectures. In addition to G², we also compare with two recently proposed mechanisms alleviate oversmoothing. DropEdge (Rong et al.) 2020) and GraphCON (Rusch et al. 2022a). The results are presented in Fig. 3 where we plot the test accuracy for all the models with the number of layers ranging from 2 to 128. While a plain GCN seems to suffer the most from oversmoothing (with the performance rapidly deteriorating after 8 layers), GCN+DropEdge as well as OCN+GraphCON are able to mitigate this behavior to some extent, although the performance eventually starts dropping (after 16 and 64 layers, respectively). In contrast, G CCCN exhibits small but noticeable increase performance for increasing number of layers, reaching its peak performance for 128 layers. This experiment suggests that G can indeed be used conjunction with deep GNNs, potentially allowing performance gains due to depth.
G for multi-scale node-level regression. We test the multi-rate nature of G2 on node-level regression tasks, where the target node values exhibit multiple scales. Due to a lack of widely available node-level regression tasks, we propose regression experiments based on the Wikipedia article networks Chameleon and Squirrel, (Rozemberczki al., 202II. While Chameleon and Squirrel are already widely used as heterophilic node-level classification tasks, the original datasets consist of continuous node targets (average monthly web-page traffic). We normalize the provided webpage traffic values for every node between 0 and I and note that the resulting node values exhibit values on a wide range of different scales ranging between 10 and 1 (see Fig. 4h. Table I shows the test normalized mean-square error (mean and standard deviation based on the ten pre-defined splits in Pei et al. (2020)) for standard GNN architectures (GCN and GAT) with and without G2. We observe from
Table Normalized test MSE on multi- scale node-level regression tasks.
Chameleon
Squirrel
#Nodes #Edges
2,277
5,201
31,421
198,493
GCNII
0.170 : 0.034
0.093 0.031
PuirNorm
0.207 0.038
0.140 0.010
GCN
0.207 = 0.039
0.143 +: 0.039
GAT
0.207 1: 0.038
0.143 0.039
GCN
0.137 : 0 033
0.070 -: 0.028
GA-
0.136 0.029
0.069 0.029

---

Published as a conference paper at ICLR 2023
Table 1 that adding G to the baselines significantly reduces the error, demonstrating the advantage of using multiple update rates.
squirrel
chameleon
Text sccurssy in 3
80
100
(3
GC
GCN
50
GAT
GAT
30
Node
Homophily lovel
Figure 4: Histogram of the target node values of the Chameleon and Squirrel node-level regres- sion tasks.
Figure 5: Test accuracy of GCN and GAT with / without gradient gating (G²) on synthetic Cora with varying level of true label homophily.
G for varying homophily (Synthetic Cora). We test G2 on a node-level classification task with varying levels of homophily on the synthetic Cora dataset Zhu et al. (2020). Standard GNN models are known to perform poorly in heterophilic settings. This can be seen in Fig. S where we present the classification accuracy of GCN and GAT the synthetic-Coue -orr dataset with level of homophily varying between O and 0.99. While these models succeed in the homophilic case (reaching nearly perfect accuracy), their performance drops to 20% when the level of homophily approaches Adding G to GCN or GAT mitigates this phenomenon: the resulting models reach a test accuracy of over 80%, even in the most heterophilic setting, thus leading four-fold increase in the accuracy of the underlying GCN or GAT models. Furthermore, we notice an increase in performance even in the homophilic setting. Moreover, we compare with state-of-the model GGCN (Yan al. 202Ip, which has been recently proposed to explicitly deal with heterophilic graphs. From Fig. 5 we observe that G2 performs on par and slightly better than GGCN strongly heterophilic settings.
Table 2: Results on heterophilic graphs. The three best performing methods are highlighted in red (First), blue (Second), and violet (Third).
Texas
Wisconsin
Film
Squirrel
Chameleon
Cornell 0.30
Hom level
0.11
0.21
0.22
0.22
0.23
#Nodes
251
7,600
5,201
2,277
183
#Edges
295
466
26,752 5
198,493 5
31,421
280
#Classes
5
GGCN
84.86 +: 4.55
86.86 + 3.29
37.54 + 1.56
55.17 1,58
71.14
1.84
85.68 6.63
GPRGNN
78.38 + 4.36
82.94 + 4.21
34.63 = 1.22
31.61 + 1.24
46.58
1.71
80.27 + 8.11
H2GCN
84.86 + + 7.23
87.65 + 4.98
35.70 + 1.00
36.48
1.86
60.11
2.15
82.70 + 5.28
FAGCN
82.43 1 6.89
82.94 1: 7.95
34.87 1 1.25
42.59
1: 0.79
55.22
3.19
79.19 9.79
FGAT
82.70 - 5.95
87.06 4.13
36.65 + 1.13
47.32 2.43
67.81 + 2.05
83.51 6.70
MixHop
77.84 7.73
32.22
43.80
2.53 60.50
73.51 6.34
GCNII
77.57 - 3.83
80.39 3.40
37.44 1.30
38.17 1.58
77.86 3.79
Geom-GCN
66.76 2.72
+.66
31.59 = 1.15
38.15 0.92
60.00
60.54 + 3.67
PairNorm
60.27 + 4.34
48.43 6.14
27.40 + 1.24
50.44 2.04
6.874
58.92 + 3.15
LINKX
74.60 + 8.37
75.49 +: 5.72
36.10 + 1.55
61.81 + 1.80
68.42 1.38
77.84 5.81
GloGNN
84.32 1
87.06
3.53
37.35 1
57.54 1.39
69.78 2.42
83.51
4.26
GraphSAGE
82.43 6.14
81.18 5.56
34.23
41.61 0.74
38.73 1.68
75.95
5.01
ResGateddGCN
80.00 + 5.57
81.57
5.35
36.02 + 1.19
37.60 1.80
49.82
2.71
73.51 4.95
GCN
55.14 5.16
51.76 1. 3.06
27.32 1 1.10
31.52 1. 0.71
38.44 1.92
60.54 5.30
GAT
52.16 1 6.63
49.41 + 4.09
27.44 0.80
36.77 1.68
48.36 11666110 1.58
61. 80 + 5.05
MLP
80.81 = 4.75
85.29 + 3.31
36.53 0.70
1.56 28.77
46.21 2.99
81.89 6.40
G2-GAT
84.59 1 5.55
87, 65
4.64
37.30 1 0.87
46.48
1.41
64.12 1.96
$7.30 4.84
G2-GCN
84.86 + 3.24
87.06
3.19
37.09 + 1.16
39.62 2.91
55.83 2.88
86. 36.49 5.27
Gd GraphAAA
87.57 + 3.86
87.84 3.49
37.14 1.01
64.26 2.38
71.40 2.38
86.22 4.90
Heterophilic datasets. In Table erophilic graphs (with a homophily level of < 0.30) (Pei et al. |020; Rozemberezki et al., (02T]) and benchmark it against baseline models GraphSAGE (Hamilton et al. 2017). GCN (Kipf Welling
test the proposed framework several real-world het-
7

---

Published as a conference paper at ICLR 2023
2017). GAT VVelickviic al. 2018) and MLP (Goodfellow et al. 2016), well as recent state-of-
the-art models on heterophilic graph datasets, i.c. GGCN (Yan et al. (022). GPRGNN (Chien et al.)
2020), H2GCN Zhu et al. 2020), FAGCN (Bo et al. 2021), F'GAT (Wei et al. 2022 MixHop (Abu-EI-Haija et al. 2019), GCNII (Chen et al. 2020b), Geom-GCN (Pei et al. 2020), PairNorm
(Zhao & Akoglu 2019 We can observe that GD added to GCN, GAT or GraphSAGE outperforms all
other methods (in particular recent methods such as GGCN, GPRGNN, H2GCN that were explicitly designed solve heterophilic tasks). Moreover, adding G2 the underlying base GNN model improves the results on average by 45.75% for GAT, 45.4% for GCN and 18.6% for GraphSAGE.
Large-scale graphs. Given the exceptional performance of G
Table 3: Results on large-scale datasets.
snap-patents 0.07 2,923,922 13,975,788 5
arXiv-year
genius
GraphSAGE on small and medium sized heterophilic graphs, test the proposed G² (applied to GraphSAGE, i.e., GrG)
Hom level
0.22 169,343
0.61
#Nodes
421.961
#Edges
1,166,243 5
984.979 2
large-scale datasets. To this end, we consider three different experiments based on large graphs from Lim et al. (2021), which range from highly heterophilic (homophily level of 0.07) to fairly homophilic (homophily level of 0.61). The sizes range from large graphs with ~ 170K nodes and 1MM edges to a very large graph with ~3M nodes and ~ ~14M edges.
#Classes
MLP
31.34 1 0.05
36.70 0.21
86.68 0.09
GCN
45.63 + 0,04
46.02 0.26
87.42 + 0.37
GAT
45.37 + 0.44
46.05 + 0.51
55.80 +: 0.87
Mix
52.16
1..11
90.58 1 0.16
LINKX
6
56.00 1.34
90.77 = 0.27
LINK
60.39 0.07
53.97 0.118
73.56 0.14
GCNII
37.88 0.66
47:21 1
90.24 1.441000 0.09
APPNP
1.01
38.15 0.26
85.36 0.62
GloGNN
62.09+022 0.27
54.68
0.34
90.66 0.11
GPR-GNN
40.19 1199100 0.03
45.07 0.221
90.05 1 0.31
ACM-GCN
55.14
47.37
0.59
80.33 4 3.91
GGGGaASAG
69.50 + 0.39
63.30 = 1.84
90.85 0.64
Table 3 shows the results of G
GraphSAGE together with other standard GNNs, as well as recent state-of-the-ar art models, i.e.,
MLP(Goodfellow et al., (2116) GCN (Kipf & Welling 2017). GAT (Velickovic al. (018). Mix- Hop (Abu-Ei-Haija et al. 2019), LINK(X) (Lim et al. 2021). GCNII (Chen et al. 2020b)) APPNP Klicpera et al. 20118), GloGNN (Li et al. 2022), GPR-GNN (Chien et al.) 2020) and ACM-GCN Luan et al. 2021). We can see that G Gr-GraphSAGE significantly outperforms current state-of-the- art (by up to 13%) on the two heterophilic graphs (i.e., snap-patents and arXiv-year). Moreover, GraphSpSAGEE is on-par with the current state-of-the on the homophilic graph dataset genius.
We conclude that the proposed gradient gating method can successfully be scaled up large graphs, reaching state-of-the- performance, in particular on heterophilic graph datasets.
5 RELATED WORK
Gating. Gating is a key component of our proposed framework. The use of gating (i.e., the modulation between 0 and 1) of hidden layer outputs has long pedigree in neural networks and sequence modeling. In particular, classical recurrent neural network (RNN) architectures such as LSTM (Hochreiter Schmidhuber] 1997) and GRU (Cho et al., 2014) rely on gates to modulate information propagation in the RNN. Given the connections between RNNs and early versions of GNNs (Zhou et al. 2019)), it is not surprising that the idea of gating has been used in designing GNNs Bresson & Laurent (017); Li et al. (2016): Zhang al. (2018). However, to the best of our knowledge, the use of local graph-gradient to further modulate gating in order to alleviate the oversmoothing problem is novel, and is its theoretical analysis.
Multi-scale methods. The multi-rate gating procedure used in G2 is a particular example of multi- scale mechanisms. The use of multi-scale neural network architectures has long history. An early example is Hinton & Plaut (1987), who proposed neural network with each connection having fast changing weight for temporary memory and slow changing weight for long-term learning. The classical convolutional neural networks (CNNs, LeCun et al. (1989) can be viewed as multi-scale architectures for processing multiple spatial scales in images (Bai et al.) 2020). Moreover, there is close connection between multi-rate mechanism (4) and the use of multiple time scales in recently proposed sequence models such as UnICORNN (Rusch & Mishra 202T) and long expressive memory (LEM) (Rusch et al. 2022b).
8

---

Published as a conference paper at ICLR 2023
Neural differential equations. Ordinary and partial differential equations (ODEs and PDEs) are playing an increasingly important role in designing. interpreting. and analyzing novel graph machine learning architectures (Avelar et al. (2019); Poli et al. (2019); [huang et al. (2020) Xhonneux
et al. (020). Chamberlain et al. (2021a) a designed attentional GNNs by discretizing parabolic diffusion-typpe PDEs. Di Giovanni et al. (2022) interpreted GCNs as gradient flows minimizing
generalized version of the Dirichlet energy. Chamberlain et al. (2021b) applied non-Euclidean diffusion equation ("Beltrami flow") yielding a scheme with adaptive spatial derivatives ("graph rewiring"), ), and Topping et al. (2021) studied a discrete geometric PDE similar to Ricci flow to improve information propagation in GNNs. [Eliasof et al. (202T) proposed a GNN framework arising from mixture of parabolic (diffusion) and hyperbolic (wave) PDEs on graphs with convolutional coupling operators, which describe dissipative wave propagation. Finally, |Ruch et al. (2022a) used systems of nonlinear oscillators coupled through the associated graph structure to rigorously overcome the oversmoothing problem. In line with these works, one contribution of our paper is a continuous version of G (2) which we used for rigorous analysis of the oversmoothing problem. Understanding whether this system of ODEs has an interpretation as a known physical model is a topic for future research.
DISCUSSION
We have proposed a novel framework, termed G2, for efficient learning on graphs. GD builds on standard MPNNs, but seeks overcome their limitations. In partieular, we focus on the fact that for standard MPNNs such as GCN or GAT, cach node (in every hidden layer) is updated at the same rate. This might inhibit efficient learning of tasks where different node features would need to be updated at different rates. Hence, we equip a standard MPNN with gates that amount to a multi-rate modulation for the hidden layer output 4 This enables multiple rates (or scales) of flow of information across graph. Moreover, we leverage local (graph) gradients to further constrain the gates. This done to alleviate oversmoothing where node features become indistinguishable as the number of layers is increased.
By combining these ingredients, we present a very flexible framework (dubbed G2) for graph machine learning wherein any existing MPNN hidden layer can be employed the coupling function and the multi-rate gradient gating mechanism can be built on top of it. Moreover, we also show that G corresponds to time-discred dineersctetiiiioonn of system of ODEs (9. By studying the (in)-stability of the corresponding zero- arr--Diichlle energy steady states we rigorously prove that gradient gating can mitigate the oversmoothing problem, paving the way for the of very deep GNNs within the G² framework. In contrast, the lack of gradient gating is shown to lead to oversmoothing.
We also present extensive empirical evaluation illustrate different aspects of the proposed G2 framework. Starting with synthetic, small-scale experiments, we demonstrate that i) G2 can prevent oversmoothing by keeping the Dirichlet energy constant, even for a very large number of hidden layers, ii) this feature allows us to deploy very deep architectures and to observe that the accuracy of classification tasks can increase with increasing number of hidden layers, iii) the multi- rate mechanism significantly improves performance on node regression tasks when the node features are distributed over a range of scales, and iv) G² is very accurate at classification on heterophilic datasets, witnessing an increasing gain in performance with increasing heterophily.
This last feature was more extensively investigated, and we observed that G2 can significantly outperform basclines as well as recently proposed methods on both benchmark medium-scall and large-scale heterophilic datasets, achieving state-of-the-arr performance. Thus, by a combination of theory and experiments, we demonstrate that the -f-frmeeoork is a promising approach for learning on graphs.
Future work. As future work, we would like to better understand the continuous limit of G2, i.c., the ODEs (9), especially in the zero spatial-resolution limit and investigate if the resulting continuous equations have interesting geometric and analytical properties. Moreover, we would like to use G2 for solving scientific problems, such as in computational chemistry the numerical solutions of PDEs. Finally, the promising results for G2 on large-scale graphs encourage us to use it for even larger industrial-scale applications.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The research of TKR and SM was performed under a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant Agreement No. 770880). MWM would like to acknowledge the IARPA (contract I91 NSF, and ONR for providing partial support of this work. MB is supported in part by ERC Grant No. 724228 (LEMAN). The authors thank Emmanuel de Bézenac (ETH) for his constructive suggestions.
REFERENCES
Sami Abu-El-Haa 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. international conference on machine learning, pp. 21-29. PMLR, 2019.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICML, 2021.
H. C. Avelar, A. R. Tavares, M. Gori, and L. C. Lamb. Discrete and continuous deep residual learning over graphs. arXiv preprint, 2019.
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 770-778, 2020.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond now-frequency information in graph con- volutional networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 3950-3957, 2021.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv:1711.07553 2017.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv:2104. 13478, 2021.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In 2nd International Conference Learning Representations, ICLR 2014, 2014.
Ben Chamberlain, James Rowbottom, Maria I. Gorinova, Michael M. Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: graph neural diffusion. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 1407-1418. PMLR, 2021a.
Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusion graphs. In NeurIPS, 2021b.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3438-3445, 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie, Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988. 2020.
Kyunghyun Cho, B van Merrienboer, Caglar Gulcehre, F Bougares, H Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Conference Empirical Methods in Natural Language Processing (EMNLP 2014), 2014.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-385 3852, 2016.
10

---

Published as a conference paper at ICLR 2023
Austin
Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Peter W Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalee Yujia Li, and Petar Veličković. Traffic Prediction with Graph Neural Networks in Google Maps. 2021.
Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows. (tt1:2200.109991,, 2022.
Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen:
Novel architectures for graph neural networks motivated by partial differential equations. In NeurlPS, 2021.
Lawrence C Evans. Partial differential equations, volume 19. American Mathematical Soc., 2010.
Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing of data structures. IEEE Trans. Neural Nenworks, 9()):768-786 1998.
Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, et al. Utilizing graph machine learning within drug discovery and development. Briefings in Bioinformatics, 22(6), 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Christoph Goller and Andreas Kuchler. Learning task lask-dependent distributed representations by backpropagation through structure. In ICNN, 1996.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In IJCNN, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
G.E. Hinton and D.C. Plaut. Using fast weights to deblur old memories. In Proceedings of the ninth annual conference of the cognitive science society, pp. 177-186, 1987.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1780, 1997.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprins 1rX1v:1810.05599,, 2018.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4):541-551) 1989.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily, arXiv preprint arXiv:2205.07308, 2022.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua Bengio and Yann LeCun (eds.), ICLR, 2016.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang. Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Lek-Heng Lim. Hodge laplacians graphs. arXiv preprint arXiv: 1507.05577 2015.
11

---

Published as a conference paper at ICLR 2023
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint
2021.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning graphs and manifolds using mixture model cnns. In CVPR, 2017.
H Nt and T Maehara. Revisiting graph neural networks: all we have is low pass filters. arXiv: (882..82.4444 2019.
K Oono and T Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo
Park. Graph neural ordinary differential equations. pp. 6571-6583, 2019.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Towards deep graph convolutional networks on node classification. In ICLR, 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnab011, 2021.
T. Konstantin Rusch and Siddhartha Mishra. Unicornn: A recurrent model for learning very long time dependencies. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9168-9178. PMLR, 2021.
T. Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bron- stein. Graph-coupled oscillator networks. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 18888-18909. PMLR, 2022a.
Konstantin Rusch, Siddhartha Mishra, N. Benjamin Erichson, and Michael. Mahoney, Long ex- pressive memory for sequence modeling. In International Conference Learning Representations, 2022b.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20( 20(1):61-80, 2008
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2)x021001, 2020.
Alessandro Sperduti. Encoding labeled graphs by labeling RAAM. In NIPS, 1994.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Trans. Neural Networks, 8(3):714-735, 1997.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature.
arXiv:2111.14522. 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR, 2018
Lanning Wei, Huan Zhao, and Zhiqiang He. Designing the topology of graph neural networks: A novel feature fusion perspective. In Proceedings of the ACM Web Conference 2022, pp. 1381-1391, 2022.
S. Wiggins. Introduction nonlinear dynamical systems and chaos. Springer, 2003.
12

---

Published as a conference paper at ICLR 2023
Louis- A C Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In ICML, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint (XXiv:202200662. 2021.
Rex Ying, Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Yan Yeung. Gaan: Gated atten- tion networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07290 2018.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns, arXiv preprint arXiv:1909 12223, 2019.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang,, Changcheng Li, and Maosong Sun. Graph neural networks: a review of methods and applications. 1.X.:18812.0843444,, 2019.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
Zhuang, N. Dvornek, X. Li, and J. S. Duncan. Ordinary differential equations on graph networks. Technical Report, 2020.
13

---

Published as a conference paper at ICLR 2023
Supplementary Material for: Gradient Gating for Deep Multi-Rate Learning on Graphs
A ADDITIONAL EXPERIMENTS
In this section, we describe additional empirical results complement those in the main text.
On the multi-rate effect of G Here, we analyze the performance of G on the multi-scale node-level regression task of the main text. As we see in the main text, G2 applied to GCN or GAT outperforms their plain counterparts (GCN and GAT) on the multi-scale node-level regression task by more than 50% on Chameleon and more than 100% on Squirrel. The question therefore arises whether this better performance can be explained by the multi-rate nature of gradient gating.
To empirically analyse this, we begin by adding control parameter a to G as follows, mm-1,,
X - (T")") O X= + (T")² ④ (F G)))
Clearly, setting a = 1 recovers the original gradient gating message-passing update,
X (1 r") x + o (F ,)).
while setting 0 disables any explicit multi-rate behavior and plain message-passing scheme is recovered,
X (F (9)=
Note that by continuously changing from 0 to controls the level of multi-rate behavior in the proposed gradient gating method.
In Fig- 6 we plot the test NMSE of the best performing G2-GCN and G2-GAT on the Chameleon multi-scale node-level regression task for increasing values of a E [10-3, see that the test NMSE monotonically decreases (lower error means better performance) for both
log-scale. We can
G2-GCN and G2 -AT for increasing values of a, i.e., increasing level of multi-rate behavior. We can conclude that the multi-rate behavior of G2 is instrumental in successfully learning multi-scale regression tasks.
0.18
G'-GCN
GAT
90
Tex NASE
Test accuracy
70
0.14
60
50
Texas
Scuirrel
Film
0.10
G exponent
Figure 6: Test NMSE on the multi-scale chameleon node-level regression task of G GCN and G²-GAT for continuously decreasing level of multi-rate behavior.
Figure 7: Test accuracies of Gr-GraphSAGE on Texas, Squirrel, Film, Wisconsin and Chameleon graph datasets for varying values of p in (4)
On the sensitivity of performance of G2 to the hyperparameter p. The proposed gradient gating model implicitly depends on the hyperparameter p, which defines the multiple rates т, i.e.,
7" 8 (F n-1 .9)),
T tanh
Σ JEN.
AT
AT 5k!
SA
While any value > 0 can be used in practice, standard hyperparameter tuning procedure (see for the training details) on p has been applied in every experiment included in this paper. Thus,
14

---

Published as a conference paper at ICLR 2023
it is natural to ask how sensitive the performance of G² is with respect to different values of the hyperparameter
To answer this question, trained different C2-GraphSAGE models variety of different graph datasets (i.c., Texas, Squirrel, Film, Wisconsin and Chameleon) for different values of E [1. 5]. Fig. shows the resulting performance of G2-GraphSAGE. We can see that different values of do not significantly change the performance of the model. However, including the hyperparameter p to the hyperparameter fine-tuning procedure will further improve the overall performance of Ga.
On the sensitivity of performance of G² to the number of parameters. All results of G² provided in the main paper are obtained using standard hyperparameter tuning (i.e., random search). Those hyperparameters include the number hidden channels for each hidden node of the graph, which directly correlates with the total number of parameters used in G It is thus natural to ask how G² performs compared to its plain counter-version (e.g. G2-GCN to GCN) for the exact same number of total parameters of the underlying model. To this end, Fig. 8 shows the accuracies of G2-GCN and GCN for increasing number of total parameters in its corresponding model. We can see that first, using more parameters has only slight effect on the overall performance of both models. Second, and most importantly, G2-GCN constantly reaches significantly higher test accuracies for the exact same number of total parameters. We can thus rule out that the better performance of G2 compared to its plain counter- vennton-vession is explained by the usage of more parameters.
accracy
G' CC-GCN
GEN
paramoters
Figure 8: Test accuracies of plain GCN and G2-GCN on Texas for varying number of total parameters in the GNN.
Ablation of Fg in G². In its most general form G² (4) uses additional GNN F, to construct the multiple rates T" Is this additional GNN needed To answer this question, Table shows in which of the provided experiments (using G GGGGhSaahSAAE) we actually used an additional GNN F (as suggested by our hyperparameter tuning protocol). We can see that on small-scale experiments having an additional GNN is not needed. However, on the considered medium and large-scale graph datasets it is beneficial to use Motivated by this, Table shows the results for G² Gr-GraphSAGG AGE on the three medium-scale graph datasets (Film, Squirrel and Chameleon) without using an additional GNN in (i.e., F, Fo) well as with using an additional GNN (i.e., the results provided in the main paper). We can that while G²-GraphAAGE without additional GNN (i.e., w/o Fg) yields competitive results, using an additional GNN is needed in order to obtain state-of-the-art results on these three datasets.
Table 4: Usage of F9 in G2 4 for each result with G G--GraphS AGE presented the main paper (YES indicates the usage of Fs, while NO indicates that no additional GNN is used to construct the multiple rates, i.c., F9 = Fe)
Texas
Wisconsin
Film
Squirrel
Chamelcon
Cornell
snap-patents
arXiv-ycar
genius
NO
NO
YES
YES
YES
NO
YES
YES
YES
15

---

Published as a conference paper at ICLR 2023
Table 5: Test accuracies of GG--GrapSAAGG with and without additional GNN (i.e., w/ Fg and w/o Fo in (4 Film, Squirrel and Chameleon graph dataset.
Film
Squirrel
Chameleon
G GraphSG w/ Fø 37.14 + 1.01
64.26 + 2.38 71.40 + 2.38
GD GraahSSSG w/o F,,
36.83 + 1.26
55.78 + 1.61
65.04 + 2.27
Ablation of multi-rate channels in G2. The corner stone of the proposed G2 the multi-rate matrix 7 in (4), which automatically solves the oversmoothing issue for any given GNN (Proposition 3.3). This multi-rate matrix learns different rates for every node but also for every channel of every node. It is thus natural ask if the multi-rate property for the channels is necessary, if having multiple rates for the different nodes is sufficient, i.e., having multi-rate vector T R A direct construction of such multi-rate vector (derived from our proposed G²) is:
4" = oFFo
T." tanh
Σ JENr
||
+:- l1p
(16)
X" " + OF(FF(X ,9))
Note that the only difference to our proposed G2 in the second equation of (16), where we sum the node-wise p-norms of the differences of adjacent nodes. This way, compute single scalar T for every node E V.
6 the results of our proposed Gr-GraaSSAGE well the single-rate channels ablation of GD (eq. (16)) on the Film, Squirrel and Chameleon graph datasets. As a baseline, we also include the results of plain GraphSAGE. We can see that while G2 with single-scale ehannels outperforms the base GraphSAGE model, our proposed G with multi-rate channels vastly outperforms the single-rate channels version of G².
Table 6: Test accuracies of plain GraphSAGE, G2-GraphSAGE with multi-rate channels for each node (i.e., standard G as well as with only a single rate for every channel on Film, Squirrel and Chameleon.
Film
Squirrel
Chameleon
GraphSAGE
34.23 + 0.99
41.61 + 0.74
58.73 = 1.68
D'-GrapSSAGE w/ multi-rate channels 2
37.14 + 1.01
64.26 + 2.38
71.40 + 2.38
G GraphhSSAGGE w/ single-rate channels 2
16
36.67 + 0.56
44.03 + 1.01
60.29 + 3.45
Alternative measures of oversmoothing. The proof of Proposition 3.2 and Proposition 3.3 as well as the first experiment in the main paper is based on the definition of oversmoothing using the Dirichlet energy, which was proposed in Rusch et (2022a). However, there exist alternative measures to describe the oversmoothing phenomenon in deep GNNs. One such measure is the mean average distance (MAD), which was proposed in Chen al. (2020a). In order to check our proposed G mitigates oversmoothing defined through the MAD measure repeat the first experiment in the main paper and plot the MAD instead the Dirichlet energy for increasing number of layers in Fig. We can see that while the MAD of plain GCN and GAT converges exponentially with increasing number of layers, remains constant for G². G2-GCN and G2-GAT. We can thus conclude that G2 mitigates oversmoothing defined through the MAD measure.
16

---

Published as a conference paper at ICLR 2023
10
10-
MAD
G'GGON
GCN
12
G1-GAT
10" GAT
100
Layer
Figure 9: Mean average distance (MAD) of layer- wise node features X propagated through GAT, GCN and their gradient gated versions (G²-GAT, G²-GCN).
B TRAINING DETAILS
All small and medium-see scale experiments have been run on NVIDIA GeForce RTX 2080 Ti, GeForce RTX 3090, TITAN RTX and Quadro RTX 6000 GPUs. The large-scale experiments have been run on Nvidia Tesla A100 (40GiB) GPUs.
tuned using random search. Table shows the ranges of each hyperparam- eter as well as the random distribution used to randomly sample from it. Moreover, Table 8 shows the rounded hyperparameter p G² of each best performing network.
All hyperparameters
Table Hyperparameter ranges.
range
rand. distribution
learning rate
[10 11044,0 10-21
log uniform disc. uniform uniform uniform
hidden size
{32, 64, 128, 256, 512)
dropout input
[0, 0.9]
dropout output weight decay G d"-exponent p
[0, 0.9
10-8810-9)
log uniform uniform
[1,5]
Usage Fg in
(YES, NO]
disc. uniform
Table 8: Rounded hyperparameter p in G2 of each best performing network.
Texas
Wisconsin
Film
Squirrel
Chameleon
Cornell
snap-patents
arXiv-yeur
genius
G'-GAT
3.06
1.68
1.23
3.48
3.54
3.54
GD-GCN
3,93
2.92
3.79
1.99
1.08
3,87
/
GG-GrahSAGE
4.47
1.14
2.89
3.04
2.00
3,27
1.60
3,40
4,40
C MATHEMATICAL DETAILS
In this section, provide proofs for Propositions 3.3 and 3.4 in the main text. We start with the following technical result which is necessary in the subsequent proofs.
Poincare Inequality on Connected Graphs. Poincare inequalities for functions (Evans 2010) bound function values in terms of their gradients. Similar bounds node values in terms of graph-gradients can be derived and a particular instance is given below,
17

---

Published as a conference paper at ICLR 2023
Proposition C.1. Let (V,&) be connected graph and the corresponding (scalar) node features are denoted by Y: E R. for all E V. Let y1 = 0. Then, the following bound holds,
Σ dA SdAS E E
ly, ys13,
(17)
iEV
iEV
where d = max deg(i) and A is the eccentricity of the node 1.
VEV
Proof. Fix a node i E V. By assumption, the graph is connected. Hence, there exists a path connecting i and the node 1. Denote the shortest path Pii 1). This path can be expressed in terms of the nodes f with 0 < l < ö, where 0,,1 = 1 and 6,, = i. For any L, we require 4,1 ~ (e+ 1)..1 Moreover, 6,,1 is the graph distance between the nodes and 1 and A
max d4, is the eccentricity ieV
of the node 1.
Given the node feature yı. we can rewrite it as,
6-1 y(41)., - -V41
Y1 -1 y1 vet.. - Y4.1
Σ t=
t=0
assumption y1 0.
Using Cauchy-Schwartz inequality on the previous identity yields,
y (C+1)) - -YG,)
Summing the above inequality over i V and using the fact that l,1 ~ (e+ + 1)x,1, we obtain the desired Poincare inequality (17).
C.1 PROOF PROPOSITION 3.3 OF MAIN TEXT
Proof. By the definition of exponential stability, we consider a small perturbation around the steady state e and study whether this perturbation grows decays time. To this end, define the perturba- tion as.
= isise.
(18)
tedious but straightforward calculation shows that these perturbations evolve by the following linearized system of ODEs,
dxx (t)
A,,,,)) (X,,,.),
Vt, ViE..
(19)
dt
JEN;
Multiplying x; both sides of (9) yields,
xx,(t)
Σ A (x, -x.).
dl
JEN:
(x?(1)
Σ An -x-=
E ( x.)²
dt JEN,
JEN;
18

---

Published as a conference paper at ICLR 2023
Summing the above identity over all nodes i V yields,
x1)) = Σ Σ dl LEV
A,y(c,)
{3 1 x2)
Σ E
Asj(a,) (2, -x,
iEV JEN,
iEV JEN;
ΣΣ
(c,((, cs))(c,)))
X3 x2
(Aig(c, cz)(e,c))
X, -x))
2 iEV JEN;
iEV JEN =2A,g
Σ
Σ
A.j((,) (x, -X))
EEV JEN,
Σ
Σ
{ -xx) (by 15
iEV JEN.
x
dAi
Here, the last inequality comes from applying the Poincare inequality 17 and from the fact that by assumption X₁ =1=00 O.
for the perturbations
X
Applying Grönwall's inequality yields.
Ex(0s S
Σ
(20)
NV
Thus, the initial perturbations around the steady steady state e is exponentially stable implying that this architecture will lead to oversmoothing. O
damped down exponentially fast and the
C.2 PROOF OF PROPOSITION 3.4 OF MAIN TEXT
Proof. As in the proof of Proposition 3.3 we consider small perturbations of form 18] of the steady state and investigate how these perturbations evolve in time. Assuming that the initial perturbations are small, i.e., that there exists an 0 < e << such that max [x, S e, we perform a
iEV straightforward calculation to obtain that the perturbations (for short time) evolve with the following quasi-linearized system of ODEs,
(t) dt
T((t)
Σ (g(a, (x, (x,- vi ViEV,
JEN.
(21)
+,(
Σ
x() X.(P),, ViEV.
JEM
Note that we have used the fact that o o'(x) and tanh' (0) 1 in obtaining from 14
Next, we multiply &; to both sides of 21 to obtain,
(t)
x
Σ
A,((,.))F.8 (x, 1 -X.).
dl
JEN,
(22)
(1?(1)
Σ A (x3-X?)
x2) Σ Aig(c (x, - JEN,
dt
JEN;
Trivially,
X X, T., Vj N₁, Vi.
Applying this inequality to the last line of the identity 22 we obtain,
ix?(1)
< Angee)) (8)
x?
Σ
(e, (e(cec) -x,"" pt2
dt
JEN:
JEN;
19

---

Published as a conference paper at ICLR 2023
Summing the above inequality over E V leads to,
d
xtt(
- Σ Σ
A,)(C.TT (x--X;) -
ΣΣ E Aty(c,c) X, -x, x1/ pr2
dt LEV
iEV JEM;
iEV JEA;
- 2 Σ
Σ
Au(ac) -T,) (x) - x²) (Ay = And)
KEV JEN;
Σ
Σ
X,
X,
pt2
(from 15
KEV JEN;
Therefore, we have the following inequality.
d
(t) Ti - T2,
dt iEV
1 Σ Σ (g(ac)
(T: (x) x?)
Ti 2
(23)
VEV JEM
p+2
T2 Σ
Σ
X,
JEN,
We analyze the differential inequality (23 by starting with the term Ti in (3 We observe that this
term does not have a definite sign and can be either positive or negative. However, we can upper bound this term in the following manner. Given that the right-hand side of the ODE system (2T) is Lipschitz continuous, the well-known Sauchy-Lipschhe continuously on the initial data. Given that max (X)) S << 1 and the bounds on the hidden 'EV
theorem states that the solutions & depend
states I there exists a time > such that
max KEV
1, E [0,7).
Using the definitions of 7 and the right stochasticity of the matrix A, easily obtain the following bound
|T - 2
(24)
where d = max deg(i..
VEV
On the other hand, the term T2 in (33 is clearly positive. Hence, the solutions of resulting ODE,
d
Σ 5
(25)
dt iEV
will clearly decay in time. The key question is whether not the decay is exponentially fast. We answer this question below.
To this end, we have the following calculation using the Hölder's inequality,
ΣΣ
X, X; s (dv) 630
ΣΣ
X; x,
LEV JEN,
NEV VEVJENS
242
ΣΣ SEV JEN.
x
-x
x
12
ΣΣ
X,
X p+2
& (dv)
NEV
JEN,
Observing that x 0 by assumption, applying the Poincare inequality 17 inequality to further obtain.
in the above
4+
X P+2
Σ EXXP
ΣΣΣ
X,
7
0 A
PT
NEV
TEY JEA;
20

---

Published as a conference paper at ICLR 2023
Hence, from the definition of T2
23 have,
4/2
T2
Σxx;P
Σ
12,
(26)
d 02 A
LEV
Therefore, the differential inequality 25
now reduces to,
d
Σ
(27)
dt iEV
A
P-2
VEV
The differential inequality
27 can be explicitly solved to obtain,
Ex KEV
2+
Σx LEV
Σ x9(0). SEV
(28)
d 0 A
From (8). we see that the initial perturbations decay but only algebraically at rate of 2 in time. For instance, the decay is only linear in time for 2 and even slower for higher value of
Combining the analysis of the terms T2,2 in the differential inequality 23 we see that the one of the terms can lead to a growth in the initial perturbations whereas the second term only leads to polynomial decay. Even if the contribution the term Ti = 0, the decay of initial perturbations only polynomial. Thus, the steady state c is not exponentially stable.
Remark C.2. We note that the Proposition 3.4 assumes certain structure of the matrix A in (14). A careful perusal of the proof presented above reveal that this assumptions can be further relaxed. To start with, if the matrix ( c) is not symmetric, then there will be an additional term in the inequality (33. which would be proportional to Aij - Ajt This term will be of indefinite sign and can cause further growth the perturbations of the steady state c. any case, can only further destabilize the quasi-linearized system. The assumption that the entries of A are uniformly positive amounts to assuming positivity of the weights of the underlying GNN layer. This can be replaced by requiring that the corresponding eigenvalues are uniformly positive. If some eigenvalues are negative, this will cause further instability and only strengthen the conclusion of lack of (exponential) stability. Finally, the assumption that one node is not perturbed during the quasi- linearization is required for the Poincare inequality (17). If this not true, an additional term, of indefinite sign, is added to the inequality (3). This term can cause further growth of the perturbations and will only add instability to the system. Hence, all the assumptions in Proposition 3.4 can be relaxed and the conclusion of lack of exponential stability of the zero- -rrr-hirihhlet energy steady state still holds.
21


Reviews:
[{"review_id": "iZ6NSsOFSuB", "reviewer": "Reviewer_xxu8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel GNN architecture based on a gradient gating module. The module is proved to alleviate oversmoothing through theoretical analysis and simulations, and shows good experimental results on the benchmarks. ", "summary_of_the_review": "Overall I like the method proposed in the paper and the experimental results shows good improvements, therefore I lean towards accepting the paper. It would be even better if my concerns are addressed.", "strength_and_weaknesses": "Strength: The proposed operator is backed by theory to alleviate the oversmoothing issue, and demonstrates good results in practice.\n\nWeakness: It introduces another hyperparameter $p$ which requires additional tuning efforts. It is not discussed whether the performances still match when number of trainable parameters or computations are the same. \n\nCould the authors provide some additional results to show:\n\n1. Is there a good $p$ that transfers well across different tasks? Or is there some principle to make tuning $p$ easier?\n\n2. How do the results compare in the parameter or compute match settings?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "cbeivQD51Oq", "reviewer": "Reviewer_WoCb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a graph gating method for advancing the capacity of overcoming over-smoothing problem of GNN models. Theoretical proof and analysis are provided to demonstrate its superiority on dealing with over-smoothing issue with the help of ordinal differential equation (ODE). Experimental results look impressive on graph heterogeneity problem. The presentation and writing are overall good for catching up with the main idea.", "summary_of_the_review": "Overall it's a good work along with both methodology and theoretical analysis. But it still has certain space for further improvement.", "strength_and_weaknesses": "Strength:\n1. A multi-rate update schema implemented as graph gating operation is designed as a wrapper for GNN layers.\n2. Theoretical analysis on the properties of  the proposed method is provided.\n3. Extensive experimental results on classification and regression tasks demonstrate the superiority of the proposed method.\n\nWeakness:\n1. Employing gating method to control the message passing flow is not a new idea. The difference of this work is the employment of graph gradient method. The idea of graph gradient seems to be directly from previous work (Hodge laplacians on graphs, 2015). However, it's lack of critical details about how to get the gradient of node features as the difference of node features of end points in single edge, and how to adapt to the gradient gating module for the graph gating method. \n\n2. From the main content, it's still difficult to conclude a strong connection between over-smoothing problem and the gradient gating method. Before dividing into the theoretical analysis,  the gradient gating can adaptively control the message passing flow with information gathering from the difference of node features between central node and its neighbors. While, it's not easy to draw the conclusion because dynamic changes of the aggregation weight over the neighbors is a common property of many GNN methods. Until the theoretical part, some clues induced from the theoretical upper bound of Dirichlet energy state give an alternative way to help dig more insights about the proposed gating method. Maybe authors should consider to move some conclusions from the theoretical analysis ahead to the main content (Section 2).\n\n3. The experimental analysis mainly focuses on the classification performance. It misses important experiments to show the capacity of overcoming over-smoothing problem. I strongly suggest authors to show the performance of the proposed method along with the increasing number of GNN layers, and the employ the metrics from pioneering work [1] to validate the proposed method. Besides, it should consider more baseline which also applies gating mechanism to the GNN layers, such as but limited to GaGN [2] etc. \n\nReferences:\n1. Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View, AAAI 2020.\n2. GaAN: gated attention networks for learning on large and spatiotemporal graphs, UAI 2018.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "biGmeMOtXit", "reviewer": "Reviewer_8MQJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes gradient gating ($G^2$), which assigns different trainable weights for different nodes and representation channels in each layer of GNN. The proposed method can be easily combined with different GNN, e.g., GCN or GAT. Theoretical results prove that $G^2$ can help alleviate the over-smoothing problem in GNN, and empirical results demonstrate that the proposed framework achieves state-of-the-art performance on node classification with different heterophilic graphs, both standard and large-scale. ", "summary_of_the_review": "While this paper proposes a novel method and empirical results show some improvements, more explanations can be added to make the proposed method more clear, and some baseline methods are also missing in comparison. As such, I think current version is still marginally below the acceptance bar. ", "strength_and_weaknesses": "Strength:\n- This paper proposes a novel mechanism for GNN to alleviate the over-smoothing problem\n- Empirical results against several existing baseline methods show state-of-the-art performance of the proposed method\n\nWeakness:\n- Some parts on the proposed method may need more explanations:\n  - I am a bit curious on how $G^2$ can reduce back to standard GNN with residual connection.  Equation (5) in section 3 shows its connection with standard GNN when $\\tau^n=0$. And from (2), I suppose setting $\\tau^n=1/2$ will only differ in a constant with (1). Nevertheless, it is a bit confusing why there is a difference in constant. The authors may need to add some explanations on that. \n  - It is a bit unclear why there is an additional hyper-parameter $p$ on computing $\\tau$, considering the expressive power of GNN. The sensitivity analysis in appendix A seems to show that we need a large enough $p$ to ensure good performance. Are there some explanations on that behavior?\n  - Also, since $\\tau \\in [0,1]$, why tanh activation function is used for $\\tau$? I suppose the output of tanh function lies in $[-1,1]$? \n  - Moreover, it is a bit confusing how the proposed method is connected to gradient, as the method name \"gradient gating\" indicates. I suppose it is more appropriate to call it \"channel weighting\" as $\\tau$ is directly multiplied on each channel of node representations. \n- Empirical results:\n  - I think a very relevant paper [1] is missing in current version. The authors may consider adding some discussions or empirical comparisons with it. \n  - Also, why are GloGNN and LINKX missing in Table 2? Are there any special reasons not to compare with them?\n  - It may be also good to show some visualization results on $\\tau^n$, and see how it changes with layer $n$. I wonder if there will be some interesting patterns, e.g., only few channels receive large weights while other channels have near-zero weight. \n- Minor issue: some references seem to be duplicated. Please double-check. \n\n[1] Designing the Topology of Graph Neural Networks: A Novel Feature Fusion Perspective. WWW 2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FzWw7e7VuR", "reviewer": "Reviewer_uYz6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method for gating the updates in message passing graph neural networks. The key idea is to measure the similarity of a node's representation with its neighbors, and to reduce the update magnitude when they become very similar (i.e., oversmoothing happens). The authors present theoretical and experimental evidence of the effectiveness of their approach to tackle the oversmoothing problem in GNNs. ", "summary_of_the_review": "Overall, I think the method is interesting and promising enough to warrant publication if my concerns from the detailed comments are adequately addressed. Currently, the evaluation is not rigorous enough to support all of the authors' claims about their method.\n", "strength_and_weaknesses": "Strengths:\n* The method achieves strong experimental results on a variety of tasks and datasets.\n* The method is generally well-motivated and clearly explained.\n* The authors present theoretical justification of their method.\n\nWeaknesses (more details in the next section):\n* Some of the experiments do not convincingly evaluate the described properties.\n* There is relatively little ablation analysis of the proposed model.\n* There is a plethora of methods claiming to solve the oversmoothing problem. The authors do not explain why their method should be better than existing ones.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1sfMA3trze", "reviewer": "Reviewer_f9D8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a general module that alleviates the over-smoothing problem and allows the design of deep GNNs. The theoretical results are useful.", "summary_of_the_review": "Overall, the paper proposes a GRU-like module for alleviating the over-smoothing problem for GNN. The proposed idea lacks sufficient motivation. Although the paper provides reasonable theoretical results, the proposed method is not convincingly evaluated. ", "strength_and_weaknesses": "Strength:\n- The paper proposes reasonably theoretical results.\n\nWeakness:\n- The proposed method is not well motivated. The paper shows that \"However, it is reasonable to expect that in realistic graph learning tasks one can encounter multiple rates for the flow of information (node updates) on the graph\". I hope the paper can include any example showing that multi-rate learning is necessary.\n- The proposed idea, shown in Figure 1, reminds me of the GRU layer. I hope the authors can clearly point out the similarity of ideas in the paper, and discuss why the proposed idea is different/novel.\n- The paper does not provide a sufficient description of the methods. There is no description of the number of layers, hidden dim size, number of trainable parameters, etc. of the proposed and baseline methods, making the experimental results hardly convincing.\n- I hope the paper can at least include experiments on some ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster