GRAND++: Graph Neural Diffusion with A Source Term
Authors: Matthew Thorpe
Tan Minh Nguyen
Hedi Xia
Thomas Strohmer
Andrea Bertozzi
Stanley Osher
Bao Wang
Venue: ICLR 2022 Poster (2022)
Keywords: graph deep learning
low-labeling rates
diffusion on graphs
random walk

Abstract: We propose GRAph Neural Diffusion with a source term (GRAND++) for graph deep learning with a limited number of labeled nodes, i.e., low-labeling rate. GRAND++ is a class of continuous-depth graph deep learning architectures whose theoretical underpinning is the diffusion process on graphs with a source term. The source term guarantees two interesting theoretical properties of GRAND++: (i) the representation of graph nodes, under the dynamics of GRAND++, will not converge to a constant vector over all nodes even as the time goes to infinity, which mitigates the over-smoothing issue of graph neural networks and enables graph learning in very deep architectures. (ii) GRAND++ can provide accurate classification even when the model is trained with a very limited number of labeled training data. We experimentally verify the above two advantages on various graph deep learning benchmark tasks, showing a significant improvement over many existing graph neural networks.

Published as a conference paper at ICLR 2022
GRAND++: GRAPH NEURAL DIFFUSION WITH A SOURCE TERM
Matthew Thorpe*! Hedi Xia*? Tan Nguyen* Thomas Strohmer
Andrea L. Bertozzi", Stanley J. Osher & Bao Wang*
l 'Department of Mathematics, University of Manchester, Manchester M13 9PI., UK 2 DDparrment of Mathematics, UCLA, Los Angeles, CA, 90095, USA
3 "Department of Mathematics, UC Davis, Davis, CA 95616, USA
*Department of Mathematies and Scientific Computing and Imaging (SCT) Institute University of Utah, Salt Lake City, UT. 84102, USA
ABSTRACT
We propose GRAph Neural Diffusion with a souree term (GRAND++) for graph deep learning with limited number of labeled nodes, i.e. low-labeling rate. GRAND+ is a class of continuous-depth graph deep learning architectures whose theoretical underpinning is the diffusion process graphs with source term. The source term guarantees two interesting theoretical properties of GRAND++: (i) the representation of graph nodes, under the dynamics of GRAND++, will not converge to a constant vector over all nodes even as the time goes to infinity, which mitigates the over-smoothing issue of graph neural networks and enables graph learning in very deep architectures. (ii) GRAND++ can provide accurate classification even when the model is trained with a very limited number of la- beled training data. We experimentally verify the above two advantages on vari- ous graph deep learning benchmark tasks, showing a significant improvement over many existing graph neural networks.
INTRODUCTION
Graph neural networks (GNNs) are the backbone for deep learning on graphs. Recent GNN ar- chitectures include graph convolutional networks (GCNs) [30), ChebyNet [16). GraphSAGE (29), neural graph fingerprints (20. message passing neural networks 28 and graph attention networks (GATs) [54] These graph deep networks have achieved success in many applications. including
computational physics and computational chemistry [20 28 3 recommender systems [41 62 and
social networks [63] 47 Hyperbolic GNNs have also been proposed to enable certain kinds of
data embedding with much smaller distortion
I|I 37
See 6 for some recent advances of GNN
algorithm development and applications.
A well-known problem of GNNs is that increasing the depth of GNNs often results in a significant drop in performance various graph learning tasks. This performance degradation has been widely interpreted as the overssmoothng issue of GNNs [35 12] Intuitively, GNN layers update the node representation by taking weighted average of its neighbors' features, making representations for neighboring nodes to be similar. As the GNN architecture gets deeper, all nodes' representa- tion will become indistinguishable resulting in over-smoothing. In Sec. 2 we briefly show that certain GNNs have a diffusive nature which makes over-smoothing inevitable. Another interesting interpretation of the GNN performance degradation is via a bottleneck M. since a GNN tends to represent exponentially growing information from neighbors with fixed-size vectors. Several algo- rithms have been proposed to mitigate the over-smoothing of GNNs, including skip connection and dilated convolution [33 Jumping Knowledge [60] DropEdge [49.. PairNorm [64], graph neural
diffusion (GRAND) [10), and wave equation motivated GNNs 221. Nevertheless, developing deep
GNN architectures is still in its infancy compared to the development of other deep networks.
Besides suffering from over-smoothing, we notice that the accuracy of existing GNNs drops severely when they are trained with limited labeled data. As illustrated in Fig. T the test accuracy of several
Codd to wangbaon sangbaonj@gmai com or matthew. watthee.thhrpeeeee... www..toooooeeeeeeeeeeee 2emanchsstmn...er...... ac.uk

---

Published as a conference paper at ICLR 2022
celebrated GNN architectures, including GCN, GAT, and GraphSage, drops rapidly when they trained with fewer labeled data. Morcover, the variance of classification accuracy grows significantly number of labeled nodes drops. Indeed, semi-supervised graph learning with very low-labeling rates has been studied in the Laplace learning and graph deep learning settings, see, e.g., [66] 9 (33;; one question is can develop new GNN architectures improve the performance of graph deep learning in low-labeling rate regimes?
60
10
50
15
55
40
GCN
GA1
Sage
30 GraphSage
GmapiSage
5
15
10
15 dLabeled Nodes class
#Labeled Modes C
Por cless
CORA
CitcSoor
PubMod
Figure 1: Test accuracy GCN, GAT, and GraphSage vs. the number of labeled nodes per class. All networks have layers, and each experiment run with 100 splits and 20 random seeds following [10]. The accuracy drops rapidly with fewer labeled data for training. CORA. CiteSeer, and PubMed have 2485, 2120, and 19717 nodes in total respectively. Results on more benchmark GNN architectures in Appendix D.4
1.1
OUR CONTRIBUTION
With the above GNN problems in mind, we focus on developing new continuous-depth GNNs to overcome over-smoothing and boost the accuracy of GNNs with a limited number of labeled data. We first present a random walk interpretation of the GRAND model [TO], revealing a potentially in- evitable over-smoothing phenomenon when GRAND is implicitly very deep. Based on the random walk viewpoint of GRAND, we then propose graph neural diffusion with a source term (GRAND++) that corrects the bias arising from the diffusion process, see Sec. [ details. GRAND++ theoret- ically guarantees that: (i) under GRAND+ dynamics, the graph node features do not converge to a constant vector over all nodes even as the time goes to infinity, and (ii) GRAND++ can provide accurate prediction even when it is trained with a limited number of labeled nodes. Moreover, these theoretical results resonate with the practical advantages of GRAND++. We summarize the major practical advantages of GRAND++ below.
GRAND++ can effectively overcome the over-smoothing issue; it is remarkably more accurate than existing GNNs when the architecture is very deep.
GRAND++ is suitable for graph deep learning when only a few nodes are labeled as training data. Moreover, in the low-labeling rates, GRAND++
be more accurate when the network is deeper. GRAND++ inherits the continuous-depth merit from GRAND, which defines the network depth implicitly and enables memory- training by using the adjoint method.
1.2 RELATED WORK
Diffusion on graphs and continuous-depth graph neural networks. Diffusion has been defined on graphs, see, e.g., (25] 24), and used in various applications, including data clustering and di- mension reduction 15 image processing (27 22 17 38). and semi-supervised graph nodes classification 67 65 From the numerical viewpoint, fast algorithms have been proposed for using diffusion graphs solve penalized graph cut problems [26). The connection between GNNs and diffusion on graphs has been studied substantially. For instance, GNN has been interpreted as a diffusion process on graphs, which performs low-pass filtering the input features [43). Moreover, insights from the diffusion process on graphs have been used to improve the performance of GNNs,
see, c.g., 2 36 31 57].
Leveraging neural ordinary differential equations (ODEs) 13 continuous-depth GNNs have been proposed, see, e.g., 44
which parameterizes the diffusion equation on graphs with a neural network. See Sec. 3 for a brief review of GRAND.
58 68 One recent work GRAND
Neural ODEs. Neural ODEs [3] are a class of continuous-depth neural networks whose depth is defined implicitly. Training neural ODEs using the adjoint method [46) is more memory efficient than training other neural networks using backpropagation. We provide a brief review of neural ODEs and the adjoint method in Appendix C tial equations (PDEs) on graphs that can also be considered as a coupled system of neural ODEs. Furthermore, GRANDs also trained by using the adjoint method.
GRANDs [10] are class of neural partial differen-
2

---

Published as a conference paper at ICLR 2022
data 65 [6] image processing 7 (2]. etc. Direct application of Laplace learning with Gaussian weights [ or locally linear embedding weights [50] for the above tasks may cause inference inconsistency when only a limited number of graph nodes are labeled, resulting in poor performance. Several algorithms address the inference inconsistency low labeling rate. They include up-weighting the weights of the labeled data (52) and the p-Laplacian [8 48 [66] In [9], the authors have proposed Poisson learning for improving Laplace learning at extremely low-labeling rate regimes. Poisson learning augments Laplace learning with Green's 's function at each labeled data, enabling accurate node classification when only few labeled data are available. Compared to Laplace learning, Poisson learning adds Green's 's function to the label of each labeled node and then performs label propagation to predict the label for unlabeled graph nodes. GRAND and GRAND++ both learn graph node representations and perform prediction by activating the node representations, which are fundamentally different from Laplace and Poisson learning.
Laplace learning and Poisson learning. Laplace learning has been used for
classification [67
1.3 NOTATION
We denote scalars by lower- or upper-case letters and vectors and matrices by lower- and upper-case boldface letters, respectively. For a matrix A, we denote its transpose as A and its Hadamard product with another matrix B as A @ B, i.e., the entrywise multiplication
A and B. We write the set {1, 2, .... ... as [n]. We denote the probability and expectation of given random variable æ as ((x) and E(ær). respectively. The meaning other notations can be inferred from the context.
1.4 ORGANIZATION
The paper organized as follows: In Sec. 2 we review diffusion equation on graphs and its con- nection to GNNs. In Secs. and 4 we briefly review GRAND and present random walk inter- pretation of GRAND, respectively. Leveraging the random walk viewpoint of GRAND, we propose GRAND++ for deep graph learning with theoretical guarantees in Sec. We verify the efficacy of GRAND++ in Sec. Technical proofs and more validations are provided in the appendix.
BACKGROUND
Diffusion equation on graphs. Let G (X, W) represent an undirected graph with n nodes, where X ( (ix()) [T) E Raxd with each row x(()) Rd feature vector and W := (w,)) n x n matrix with Wiy representing the similarity (edge weight) between the 7th and jth feature vectors, and we assume Wi, = Wj.. Consider the following diffusion process that evolves the feature matrix X on the graph (see Appendix AopendixAAfor. a brief review of calculus graphs):
(x())
div ())(GG((())..... (t). O VX())).
Ōt
(T) E Rax with x (0) = (+)) V and div are the gradient and divergence operators, respectively. The matrix G(X (t), t) is chosen such that W 3 G right-stochase stochastcc, i.e., each row of W G summing to In the machine learning setting, we can parameterize G with Icarnable parameters @ which we denote by G(X(t). (t).t, 0). The initial features
where (t) = (())
are evolved under the diffusion dynamics ① from / = 0 to learn the final representation X for further machine learning tasks.
In the simplest case when (t), only dependent on the initial node features X, i.e., G is time-independent, right-stochasticity implies E, WinGi 1 for all i, and so we focus on the particular case when G. 1/d, with d, = ΣØ= Wij. In this case the right-hand side of (I) reduces to the negative of the random-walk Laplacian applied to (1) and ① becomes
(x(() div div(G( v = Lxx(t)..
(2)
Øt
where L - I W = I A(A := ((A==((AX))) is the random walk Laplacian and D is diagonal with Dù d,. See 14
25| 24 for more about random walk Laplacian and diffusion graphs.
Graph neural networks. Applying forward Euler discretization, with step size 5, < 1, of gives X (ko.)) X X((k 1)6+) 8 L.L ((k- 1)5.) = ix(( 1)6t), for k 1,2, K, (3)
3

---

Published as a conference paper at ICLR 2022
T Ko, and x X. Note that the matrix L is the discretization of the diffusion operator, which is a special low-pass filter. Equation (3) a prototype for motivating GNNs; by introducing weights W(k) E RRdxd and a nonlinearity a, e.g. ReLUU, into we have
x(k+ + 1)6.) of (k6.)
The model in 4 is similar to the well-established GCN architecture proposed in [30]. The diffusive nature of the GNN architecture in (4) further explains the over-smoothing issue of training deep GNNs; the deeper the network architecture is, the more the node features diffuse. Eventually, all nodes share similar features and become indistinguishable. See Sec. for detailed analysis.
3 A BRIEF REVIEW OF GRAND
GRAND is new continuous- depth GNN proposed in [TO] It integrates a learnable encoder function & and a learnable decoder function v with the neural network parameterized graph diffusion process, resulting in the prediction Y
vb (X (T)), where X X(T) is computed
(t) de, with (() - ((X),
( (() +
(5)
aL
where (1)/al Bt is given by the graph diffusion equation can perform forward propagation of GRAND, i.e., we solve using numerical ODE solvers.
2 From the neural ODE perspective, we
In the simplest case, when is only dependent on the initial node features, we can rewrite ①
as
Ox at. (A(X) -)
(6)
GRAND models the diffusivity A in (6) by the multi-head self-attention mechanism; potential
choices of the attention function include the ones proposed in [53 54 More precisely, in GRAND
A(X) E A' (X) with h being the number of heads and the attention matrix A'(X) = (x, xz) )). for = 1, .... h, computed as follows:
exp (LeakyReLUU(d w<'l")
al [z, x,) Σ EREN, exp (LeakyReLU(a") [W'x, [Wwx))
(7)
where W and a' are learned, is the concatenation operator, and N is the index set of the nodes that are connected to the jth node in the graph. GRAND with the attention in 7 is called GRAND-I, that is, GRAND-I is a special case of GRAND when the diffusivity is dependent only the initial graph node features. Time-dependers attention and graph rewiring can be integrated into GRAND, resulting in GRAND-nl and GRAND-nl-rw, respectively [10]. From the ODE viewpoint, GRAND and its variants are a class of coupled neural ODEs defined on an unweighted graph. Their merits include continuous-depth and memory-effiiieet training using the adjoint method 46
RANDOM WALK VIEWPOINT OF GRAND
In this section, we present random walk interpretation of GRAND. The connection between graph random walks and the diffusion equation has been extensively studied, but we recap the key idea here to motivate the new GRAND with a source term architecture. Let (k)))) be the random walk on (x()) (0)) defined by, for ó E [0. 1].
B B(O (0) x. (0 (0) { - de if
(8)
We d
if +
where d, E W5 (assume We for all f). Proposition below is well-known, see 66 We provide the proof of P all the subsequent theoretical results in Appendix
Proposition 1 Let X solve 3 and ( be the random walk determined by where & E 10, 1].
Then
a ((,k)) ((B(0
4

---

Published as a conference paper at ICLR 2022
Proposition below gives the stationary distribution of the random walk
Proposition 2 Assume the graph G (X, W) is connected. Then, the stationary distribution of (k) is
di
dn Σラ= dg
).)
(9)
E5=1 d
which is independent of the starting position ((.))
Furthermore, have the following theoretical result on the asymptotic behavior of graph node features under the GRAND dynamics given by
Proposition 3 Assume the graph (x, W) is connected. Then for all -, n, we have
x: 10 (kob)) - E. = Σ x (0) as k + 00.
Hence, for the case of (3) i.e., GRAND-I, expect the output to be approximately independent of the input, due to over-smoothing. Of course, once we reintroduce the (() dependence back into G longer hold. Nevertheless,
in ( and (2) or into the operator A in (6) then the above arguments the GRAND architectures are built on principle that is ill-suited to deep networks. In the next section we introduce source term and perform similar random walk analysis that illustrates how the new architecture can be better suited for deep GNN architectures.
5 GRAND++: GRAPH NEURAL DIFFUSION WITH A SOURCE TERM
5.1 ALGORITHM AND FORMULATION
At core of GRAND+ is the introduction source term into GRAND, leveraging the random walk viewpoint of the diffusion process. We take small subset of feature vectors, indexed by
I [n], believed to be "trustworthy" for use as a source term. In particular, we use the features of labeled data. The GRAND++ dynamics are defined by diffusion equation with a source term (we use the variable z for relae++rreltted dynamics and x for GRAND dynamics)
(z) div (G(((())))))) OZZ))) Ot
E JEI
(10)
where Cj the source feature vector of node j. Below we motivate particular choice of Cj.
The key idea to first characterise the bias that arises from the diffusion and use that to propose correction via the choice of source terms Cy- Following the simplifications in (). diffusion equation (without the source term) follows the approximate dynamics when t >
ix)) (t) - [LX())
Wi (0) m
For E I, transpires that choosing C, (8) a (where á is defined below) gives rise to random walk interpretation that allows us to prove that the oversmoothing seen in the GRAND model avoided.
One can in fact choose h with certain degree of freedom. If we initialise X X then we obtain ã = =ー ( (as is usual in the GRAND model). However, as the similarities are encoded in the graph weights, and the diffusion dynamics will drive it towards non-trivial state, we can choose different initialization than X(0) X. Through connections with random walks we, in the next subsection, motivate an alternative initialisation
(0 + where +
(0)
Σ (1)
(11)
dj
ieT
5

---

Published as a conference paper at ICLR 2022
with the dynamics
Oz (z)
div (t(Z(t), VZ()) + Σ
- (x)
(12)
Ot
JEI
For example, we could choose
20
t.
(x
+)
if E otherwise,
or z () = (f)
265 where c 1-=1 x Ejez d, is chosen such that 111 holds. We do not believe that the
constant c (that shifts by constant) is particularly important but it is included to provide a random walk interpretation which helps to understand the deep architecture (when T is big) behaviour of the model GRAND++. The justification for this choice will be made Sec. To summarize, the GRAND++ model in (2), with initial condition satisfying (II), simply adds source term the original GRAND model and uses a different initial condition. Therefore, the nonlinear diffusivity and graph rewiring tricks used by GRAND can be easily integrated into GRAND++. In terms of implementation, since GRAND++ merely changes the right-hand side of GRAND, which again can be regarded as a system of coupled first-order neural ODEs; we can leverage neural ODE training, testing, and inference for GRAND++ similar to GRAND.
In the next subsection we explore the random walk connection of the above model, suggesting that building graph neural network based on the diffusion with source model does not suffer from the same degeneracy as we observed in Sec. and therefore better suited to build deep GNNs. In particular, we can write the diffusion with source model as the short time expected behaviour of random walk and therefore we do not have the issue of reaching the stationary state (in other words passing the mixing time). Our experiments in Sec. suggest the formal motivation holds and able to design deep GNNs.
5.2 THE RANDOM WALK PERSPECTIVE OF GRAND++
Let us continue to consider the simplified model in the previous subsection, i.e., assume the dynam- ics are governed by
d2 (t) - (Z) +
Σ Dij
(1) +t
(13)
at
JEZ
where the initial condition satisfies ics we have
Using the forward Euler discretisation of the above dynam-
(Bckk = 200) (5. - 1)) 5, [LZ (5, 1))1 + 5e Σ Rij (z - #t)
(14)
JEI
for k = K where again T K Kå.-
We use the same random walk as that introduced Sec. i.e. the random walk defined by 8 but we will now only consider random walks that are initialised on the nodes indexed by I.
Proposition 4 Let Z solve [4) with the initial condition satisfying (11, and let B be the random walk determined by (8). Then,
100
EE
(0))
-60)+}) x)) 11))))))) m00) +0 as k - oc.
de
jEI
Remark In the limit - oo the term
E
(1) (
JEI
is formally a function of the random walk at all times. Whilst if la very large (i.e. in comparison to the mixing time) we still have that
E
Σ
x U7.
(K)=
1 x
( (k) = (3)
T Σ
(15)
d
di
d
JCI
JEZ
jET

---

Published as a conference paper at ICLR 2022
and the other hand
Ty T
E
Σ jEZ
x
(1)
(b) - x())
(16)
d:
di
d;
JEI
From the definition of Φi see that 15 and 16 are approximately equal, And therefore we can understand 2 Ejer #1 (R) m ] as the long time behaviour of Blz Ejez x (k) Very formally we can see that subtracting the long-time behaviour from the all-time behaviour leaves with the short time behaviour. This provides
explanation as why do not expect the deep layers to determined by the stationary state of the random walk (at which point there is little dependence on the initial layers, causing the deep layers be approximately constant).
Remark The random walk interpretation
k
E
Σ
(1) -2) Σ JEZ
1 BBO mx)()
(17)
can be considered to be dual to the random walk interpretation in Sec. 4 in Sec. 4 we released the random walker from the node interest, whilst now we release the random walkers from nodes indexed by I and see how many of them hit the node of interest. We note also that we do not require a lower bound on the size of the set Indeed, if [Z] is fixed whilst one takes the number of feature vectors + Do we still expect many properties of GRAND++, in particular Proposition Deriitiooonboooyy below, to asymptotic well-posedness of the dual random walk in low labeling rates (9].
hold. This is due
Proposition 3 reveals that in the simple setting of (2). GRAND converges to constant when its depth goes infinity. However, this is not true for GRAND++ since the graph node features will not converge to a constant vector driven by the GRAND++ as shown in Proposition below.
Proposition 5 Assume the graph G = (X, W) is connected. Then z (kōtt that was defined in
14 does converge to constant vector function of - That is, the node features will not become the same across graph nodes under the GRAND++ dynamics.
Remark 3 Proposition 3 guarrantess GRAND++ is less likely to suffer from merrsmoothing than GRAND, and in particular it shows that we have a non-constant deep layer limit, i.e. as t Analysing the limit is beyond the scope of the paper but have seen characterisation in Proposition 4 By construction we have (z()(()) (t) (t) ze 0 for i E I so one should expect that the deep layer limit (close to) smooth interpolation of the feature vectors labeled by I.
The continuous time model 10
is, in the special case (1)). 3 the mean field limit of the probabilistic formulation (17). Our proposed algorithm is formulated from the mean mean-field limit.
EXPERIMENTS
In this section, we compare the performance of GRAND++ with GRAND and several other popu- lar GNNs various graph node classification tasks. We aim show the practical advantages of GRAND++ in learning with limited labeled data and using deep architectures. Without mentioning clearly, we use the same hyperparameters that that used for GRAND in [0 for GRAND++. We provide detailed descriptions of experimental settings and datasets that are omitted in the main text Appendix [D.] For all experiments, we run 100 splits for each dataset with 20 random seeds for server with four NVIDIA RTX 3090 graphics cards.
each split, which are conducted
We compare the performance GRAND++ and its nonlinear and graph rewiring variants with sev- eral popular GNNs various graph node classification benchmarks. Except for the integration time, which measures the implicit depth of GRAND and GRAND++, we adopt the experimental settings of GRAND in [10] for GRAND++ include numerical differential equation solvers. Following [10), we study seven graph node classification datasets, namely CORA, CiteSeer, PubMed, CoauthorCS, Computer, Photo, and ogbn-arxiv; we describe these datasets in Appendix D.1

---

Published as a conference paper at ICLR 2022
6.1 GRAND++ MORE RESILIENT TO DEEP ARCHITECTURES
We first show that our introduced source term in (12 can improve the accuracy of GRAND-I when the architecture is deep, i.e., the integration time 7 in 5 big. We denote GRAND-J with the source term as GRAND++11 For each node classification task, we train all models using the same number of labeled nodes as in [T]] Figure 2 contrasts the performance of GRAND-I and GRAND++-1 with different depths, or T. on CORA, CiteSeer, Computer, and Photo datasets. We provide the detailed results on PubMed and CoauthorCS, together with more comparisons of GRAND++-1 with GRAND-I and several other celebrated GNNs include GCN, GAT, and GraphSage in Table [ in Appendix D.2 The results Fig. 2 and Appendix [ confirm that GRAND-I suffers less from over-smoothing compared to GCN, GAT, and GraphSage. Moreover, GRAND++-1 performs on par with GRAND-I when the depth (T) of the network is small, but GRAND++1 significantly outperforms GRAND-I when T is large. As 'T' increases, the margin becomes wider, indicating that GRAND+ can overcome over-smoothing much more effectively than GRAND-I Note that did not uniform depth for GRAND-I and GRAND++-I on all datasets because the adaptive step-size ODE solver fails when T is large for some tasks.
93
92
72
GRAND GLARD
89
128
256
Depth IT)
Desth (T)
Depts m
CORA
CiteSeer
Computer
Photo
Figure 2: Test accuracy vs. the "'deth" (T' in 5 of GRAND-1 and GRAND++1 on the four graph node classification tasks. We that GRAND++1 is much more resilient to deep architectures than GRAND-L. These results show that GRAND++ better suited for learning with a very deep architecture than GRAND.
Next, we compare GRAND-I and GRAND++1 on the ogbn-arxiv node classification task, which a large-scale benchmark. We train two models using labeling rates of 3.0% and 5.0%, re- spectively; the corresponding test accuracy for GRAND-IGRANDt++ are 65.26%/66.644 64% and 67. 07.42% respectively. GRAND++11 outperforms GRAND-I in both labeling rates. We fur- ther compare GRAND and GRAND++ with different depth on the ogbn-arxiv task in Appendix D.6
6.2 GRAND++ MORE ACCURATE WITH LIMITED LABELED TRAINING DATA
Besides helping to overcome over-smoothing, our theory shows that the source term can boost the accuracy of GRAND-I with low- labeling rates. Table [ compares the accuracy of GRAND++-1 with GRAND-I, GCN, GAT, GraphSage, and MoNet, trained with different numbers of labeled data. Here, slightly tune T for GRAND++ based on the optimal value for GRAND, see Table 4 in the Appendix for their values. We see that with few labeled data, in most tasks GRAND++1Iis is significantly more accurate than the other GNNs include GRAND- I. confirming our theoretical insight. For Coau- thorCS task, both GRAND-I and GRAND++11 are worse than GCN and GraphSage. Moreover, increasing the depth of GRAND+++I can improve the classification accuracy with limited training data, but this is not the case for GRAND-I, see Fig. 3 We perform the t-test in Appendix D.5 to confirm the statistical significance of the aceuracy gain of GRAND++ over GRAND in Table I
30
40
GRAND=+-I GRAND-1
GRAND++
GRAND-1
64 Deach IT
128
L4
Depch
CORA
CieSeer
Figure 3: Accuracy of GRAND++11 and GRAND- for CORA and CiteSeer, where both models, with different depth (I'). are train with labeled node per class. These results show that GR GRAND++ is more effective in learn- ing with low-labeling rates than GRAND.
6.3 TTME-DEPENDENT ATTENTION AND GRAPH REWIRING
The previous experimental results show that GRAND++- enhances the accuracy of GRAND-I in the cases when the labeled training data is limited and when the network is deep. Here, we explore the same strategy for GRAND-nl and GRAND-nl-rw; we name the corresponding models with the new source term GRAND+++1 and GRAND++-nl-rw, respectively. Table compares GRANDDnl and
8

---

Published as a conference paper at ICLR 2022
Model
Aper class
CORA
CiteSeer
PubMed
CoanthorCS
Computer
Photo
54,94 + 16.09
58.95 + 9.59
65.94 + 4.87
60 + 1.50
67.65 + 0.37
83.12 + 0.78
66.92
10.04
64.98
8,31
69,31
+ 4,87
76.53
1.85
76.47
1.48
83.71
+ 0.90
GRAND++1
77.80
4.46
3,63
71.99
84.83
82.64
0.56
88.33
1.21
(ours)
80.86
2.99
2,42
75.13
82.99
0.81
1.19
20
82.95
1.37
73.53
3.31
79.16 + 1.37
90.80 - 0.34
85.73
0.50
93.55
0.38
52.53
16.40
50.06 + 17.98
48.67
1.66
2.50
64,82
11.16
59.55 + 10.89
69,00
73.83
5.58
74.17
1.85
82.13
3.27
GRAND-]
76.07
5.08
68.37
5.00
73.98
5.08
85.29
2.19
80.72
1.09
88.27
1.94
10
10
80.25 = 3:40
71.90 + 7.66
76.33 + 3.41
87.81 + 1.36
82:42
1,10
90.98 + 0.93
20
82.86 2.39
73.02
5.89
78.76
1.69
91.03 0.47
84.54
0.90
93.53 1. 0.47
47.72
15.33
48.94 + 10.24
58.61 + 12.83
65.22
2.25
49 46
1.65
82,94 2.17
2
60.85
14,01
58.06
+ 9.76
60.45 + 16.20
83.61
+ 1.49
76.90
1.49
83.61 + 0.71
GCN 80
73.86
7.97
67.24
4.19
68.69
+ 7.93
86.66
0.43
82.47
0.97
88.86
+ 1.56
10
78.82
5.38
72.18
3.47
1.19 76.89
72.59
88
0,50
82.53
0.74
90.1
0.35
2.90
47.86 + 15.38
50.31 + 14.27
58.84
12.81
51.13 + 5.24
37.14
7.81
73.58 + 8.15
+
8.86
4.89
71.04
5.08
71.65
71,43
7.34
10
76.31
4.87
71.35 4.92
72.44
3.50
74.71
3.35
0.35 80,05
76.04
87,42 2.38
20
79.92 2.28
73.22 + 2.90
75.55 + 4.11
79.95
2.88
1.81
89.38 + 2.48
43.04 14.01
48.81 11.45
55.53 12.71
61.35
1.35
27.65
2.39
45.36 7.13
53.96 - 12.18
$4,39 +: 11.37
$8.97 + 12:65
76.51
1.31
42.63
4.29
$1.93 + 4:21
GraphSage 29
68.14 = 6.95
64.79
+ 5.16
66.07
+ 6.16
89.06
+ 0.69
64.83
1.62
78.26 + 1.93
10
75.04 5.05
68.90
5.08
70.74 + 3.11
89.68
0.39
74,66
1.29 79.98
84.38
1.75
20
80.04
2.54
72.02
2.82
74.55 3: 3.09
91.33 0.36
0.96
91,29 1 0.67
47.7
15.53
$9.13 11.37
$6.47 + 4.67
58 $8.99
5.17
23.78
7.57
34.72 8.18
MoNet
60.85
14.01
48.52
61,03 - 6.93
76.57
4.06
38.19
3.72
43.03 + 8.22
40
73.86
7.97
67.92
71.24
3.17
20
82.07
2.03
71.52
4.11
76.49 = L.75
90.31
0.41
73,66
2.87
88.61
1.18
Table 1: Classification accuracy of different GNNs trained with different number of labeled data per class
(fiee class) on six benchmark graph node classification tasks. The highest accuracy is highlighted in bold for each number of labeled data per class. These results show that GRAND++ is more effective in learning with low-labeling rates than GRAND. (Unit: %)
GRAND-nl-rw with the corresponding model with a source term. We see that overall GRAND++nn (GRAND+--nl-yg outperforms GRAND-nl (GRAND-nl-rw) when the network is deep, i.e., T is big. We further study the www-labeling rate regimes in Appendix D.3
Depth (T)
GRANT>al 10
GRAND>al-rw
GRAND++-al (ours)
GRAND (ours)
CORA
3.05
79.24 1:
82.31
0.91
82.47
1.32
82.64
82.23
1.14
16
82.11
1.42
82.05
1.31
83.24
0.20
81.48
1.07
32
79:42
0.64
81.01
0.81
81.21 - 0.37
82.20 + 1.15
CiteSeer
1
71.84
2.98
71.84
2.66
70.45
2.12
71.74
1.37
16
72.65
2.42
73.06
2.98
12.48
+ 1.10
73.29 1: 1.37
64
70.29
2.58
69.65
2,50
72.64 + 0.93
73.38 0.95
128
65.19
6.77
65:45
7.18
74.24
0.70
74.23 + 0.70
PubMed
1
77.93
1.27
77.93
1.26
78.01
0.68
78.01 0.68
4
77.95
1.28
78.02
1.14
78.41
+ 0,88
77.
0.93
16
76.51
2.73
76.88
2.57
78.43 1 0.78
78.12
0.87
Table 2: Classification accuracy of ANA and GRAND++ variants of different depth trained 20 labeled data per class. The highest accuracy highlighted in bold for each of the depths T 1, 1,4, 16, 32, 64, and 128. We test 7 only up to 16 for PehMed and up to 32 for 32 since the neural ODE solver failed for larger T. (Unit: %)
7 CONCLUDING REMARKS
We propose GRAND++, which augments graph neural diffusion with a source term. We present some theory that connects the model to random walk formulation on graphs. GRAND+ out- performs many existing GNNs for graph deep learning with very deep architectures and when the number of labeled data is limited. GRAND++ can be regarded each ODE has an external force term. As such, it is natural to consider if advanced techniques in accelerating training, test, and inference of neural ODEs can be leveraged improve the efficiency and accuracy of GRAND++, in particular high-order neural ODEs [19 6 42 [5] and noise injec- tion (55). It is interesting to note that the second-order neural ODE can be connected the wave equation in the graph setting, which can automatically bypass over-smoothing. We leave studying the second-order neural ODE on graphs as future work.
coupled ODE system in which
9

---

Published as a conference paper at ICLR 2022
8 ACKNOWLEDGEMENT
This material is based on research sponsored by NSF grants DMS-1924935, DMS- 1952339, DMS- 2027248 and NSF CCF-193456B DOE grant DE-SC0021 142. and ONR grant N00014-18-1-2577 and the MURI grant N00014-20-1-2781 MT would like to thank the Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programme Mathematics of Deep Learning when work on this paper was undertaken (EPSRC grant number EP/RO1 EP/R014604/1) and ac- knowledge support from the European Union Horizon 2020 research and innovation programmes under the Marie Sklodowska-Cume grant agreement No. 777826 (NoMADS). MT also holds Tur- ing Fellowship at the Alan Turing Institute.
REFERENCES
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical impli- cations. In International Conference on Learning Representations, 2021.
[2] James Atwood and Don Towsley. Diffusion-convolutionn neural networks. In Advances in neural information processing systems, pages 1993-2001, 2016.
[3] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems, pages 1502-4510, 2016.
[4] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Compulation, 15(6): 2003.
[5] Mikhail Belkin and Partha Niyogi. Semi-supervised learning on Riemannian manifolds. Ma- chine learning, 56(1-3):209-233 2004.
[6] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learn- ing: Grids, groups, graphs, geodesics, and gauges. arXiv preprint 1rX1v:2104.13478, 2021.
[7] Antoni Buades, Bartomeu Coll, and Jean M. Morel. Neighborhood filters and PDE's. Nu- merische Mathematik, 105(1):1-34, 2006.
[8] Jeff Calder. The game theoretic p-Laplacian and semi-supervised learning with few labels. Nonlinearity, 32(1), 2018.
[9] Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepcev. Poisson learning: Graph hased semi-supervised learning at very low label rates. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1306-1316. PMLR, 13-18 Jul 2020.
[10] Ben Chamberlain, James Rowbottom, Maria Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: Graph neural diffusion. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1407-1418. PMLR, 18-24 Jul 2021.
[11] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32:4868-488 2019.
[12] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring 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, pages 3438-3445, 2020.
[13] Ricky T. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In S. Bengio, Wallach, H. Larochelle. K. Grauman, N. Cesa-Biande and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018
[14] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Math- ematical Soc., 1997.
10

---

Published as a conference paper at ICLR 2022
[15] Ronald R Coifiman, Stephane Lafon, Ann B Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker. Geometric diffusions as a tool for harmonic analysis and struc- ture definition of data: Diffusion maps. Proceedings of the National Academy of Sciences, 102/211:7426-7441, 2005.
[16] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-3852, 2016.
[17] Xavier Desquesnes, Abderrahim Elmoataz, and Lézoray, Olivier. Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing. Journal of Mathematical Imaging and Vision, 46(2):238-257, 2013.
[18] John R Dormand and Peter Prince. A family of embedded Runge-Kutta formulae. Journal of Computationaal and Applied Mathematics, 6(1):19-26, 1980.
[19] Emilien Dupont, Arnaud Doucet, and Yee Whye Teh. Augmented neural odes. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[20] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. Lawrence, Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[21] Moshe Eliasof, Eldad Haber, and Eran Treister. PDE-GCN: Novel architectures for graph neural networks motivated by partial differential equations. arXiv preprint arXiv:2108.0190 2021.
[22] Abderrahim Elmoataz, Olivier Lezoray, and Sébastien Bougleux. Nonlocal discrete regulariza- tion on weighted graphs: A framework for image and manifold processing. IEEE Transactions on Image Prucessing, 1777):1047-1000, 2008
[23] Francesco Farina and Emma Slade. Data efficiency in graph networks through equivariance. arXiv preprint arXiv:2 13786, 2021.
[24] Mark Freidlin and Shuenn-Jyi Sheu. Diffusion processes on graphs: stochastic differential equations, large deviation principle. Probability theory and related fiels, 116(2):881 2000.
[25] Mark I. Freidlin and Alexander D. Wentzell. Diffusion Processes on Graphs and the Averaging Principle. The Annals of Probability, 21(4):2215 2245, 1993.
[26] Cristina Gareia-Cardona Ekaterina Merkurjev, Andrea Bertozzi, Arjuna Flenner, and Al- lon G. Percus. Multiclass data segmentation using diffuse interface methods graphs. IEEE Transactions on Puttern Analysis and Machine Intelligence, 3608):1600-1613, 2014.
[27] Guy Gilboa and Stanley Osher. Nonlocal operators with applications to image processing. Multiscale Modeling & Simulation, 103):1005-1028, 2008
[28] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. Doina Precup and Yee Whye Teh, edi- tors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 06-11 Aug 2017.
[29] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[30] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In Proceedings of the 3th International Conference on Learning Representationss ICLR '17, 2017.
11

---

Published as a conference paper at ICLR 2022
[31] Johannes Klicpera, Stefan Weißenbbeggrr, and Stephan Günnemann. Diffusion improves graph learning. Advances in Neural Information Processing Systems,
2019.
[32] Guohao Li, Matthias Müller, Bermard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. arXiv preprint XXi:22066.07476, 2021.
[33] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9267-9276, 2019.
[34] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprini arXiv:2006.07733 2020..
[35] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional net- works for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelli- gence, 2018.
[36] Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In International Conference on Learning Representations, 2019.
[37] Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. Advances in Neural Information Processing Systems, 32:8230-8244 2019.
[38] François Lozes, Abderrahim Elmoataz, and Olivier Lézoray. Partial difference operators on weighted graphs for image processing on surfaces and point clouds. IEEE Transactions on Image Processing, 23(9):3896-3909 2014.
[39] Stefano Massaroli, Michael Poli, Jinkyoo Park, Atsushi Yamashita, and Hajime Asama. Dis- secting neural odes. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 3952-3963. Curran Associates, Inc., 2020.
[40] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5425-5434, Los Alamitos, CA, USA, jul 2017. IEEE Computer Society.
[41] Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. In Proceedings of the 31st st International Conference Neural Information Processing Systems, pages 3700-3710, 2017.
[42] Alexander Norcliffe, Cristian Bodnar, Ben Day, Nikola Simidjievski, and Pietro Lió. On sec- ond order behaviour in augmented neural odes. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5911-550 1-521. Curran Associates, Inc., 2020.
[43] Hoang Nt and Takanori Machara. Revisiting graph neural networks: All have is low-pass filters. arXiv preprint 19X5::1905.095555 2019.
[44] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
[45] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations. arXiv preprint arX1v:1911.07522, 2019.
[46] Lev Semenovich Pontryagin. Mathematical theory of optimal processes. CRC press, 1987.
[47] Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 21 101021199 19, 2018.
12

---

Published as a conference paper at ICLR 2022
[48] Mauricio Flores Rios, Jeff Calder, and Gilad Lerman. Algorithms for ip-based semi- semi-supervised learning on graphs. arXiv preprint
2019.
[49] Yu Rong. Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
[50] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(55000;2323-22222 2000.
[51] Yulia Rubanova, Ricky T. Q. Chen, and David K Duvenaud. Latent ordinary differential equations for iregularly--sampler time series. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[52] Zuoqiang Shi, Stanley J. Osher, and Wei. Zhu. Weighted nonlocal Laplacian on interpolation from sparse data, Journal of Scientific Computing, 73(2-3):1144 161-114--111 1177, 2017.
[53] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[54] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Rep- resentations, 2018.
[55] Bao Wang, Binjie Yuan, Zuoqiang Shi, and Stanley Osher. Resnets ensemble via the Feynman- Kac formalism to improve natural and robust accuracies. In Advances in Neural Information Processing Systems, pages 1655-1665, 2019.
[56] Fei Wang, Changshui Zhang, Helen C Shen, and Jingdong Wang. Semi-supervised classifica- tion using linear neighborhood propagation. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), (06), volume 1, pages 160-167. IEEE, 2006.
[57] Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process linear graph convolutional networks. arXiv preprint 1rXiv:2102.10739, 2021.
[58] Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10432- 10441. PMLR, 13-18 Jul 2020.
[59] Hedi Xia, Vai Suliafu, Hangjie Ji, Tan Minh Nguyen, Andrea Bertozzi, Stanley Osher, and Bao Wang. Heavy ball neural ordinary differential equations. In A. Beygelzimer, Y. Dauphin, Liang, and Wortman Vaughan, editors, Advances Neural Information Processing Sys- tems, 2021.
[60] 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 on Machine Learning, pages 5453-5462. PMLR, 2018
[61] Cagatay Yildiz, Markus Heinonen, and Harri Lahdesmaki. ODE2VAE: deep generative second order odes with Bayesian neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, Alcché-Buc,, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[62] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Pro- ceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 983, 2018.
13

---

Published as a conference paper at ICLR 2022
[63] Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Proceed- ings of the 32nd International Conference on Neural Information Processing Systems, pages 5171-5181, 2018.
[64] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in GNNs. In Interna- lional Conference on Learning Representations, 2020.
[65] Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in neural information processing systems, pages 321-328, 2004.
[66]
Dengyong Zhou and Bernhard Schölkopf. Regularization discrete spaces. In 27th DAGM Conference on Pattern Recognition, pages 361-368, 2005.
[67] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using Gaus- sian fields and harmonic functionn. In Proceedings of the 20th International Conference on Machine learning, pages 912-919, 2003.
[68] Juntang Zhuang, Nicha Dvornek, Xiaoxiao Li, and James S. Duncan. Ordinary differential equations on graph networks.
2020.
14

---

Published as a conference paper at ICLR 2022
A BACKGROUND ON GRAPH DIFFERENTIAL OPERATORS
Let (X, W) represent graph where X (.(, E Raxd is the matrix where each row a:()) E TRd a feature vector and W (W,)).== is n n matrix with Wi representing the similarity (edge weight) between the ith and jth feature vector. We assume that we are dealing with an undirected graph, i.c., Wij Wji. A valuee function on the nodes of the graph can be represented as a matrix U E Ruxk: by = (1 .......ud (u..,(((()]]) ) and we define the inner product
UU V) = Σ u v(())
Similarly, valuue function on the edges can be represented third-order tensor U Raxnxka which we write
40.1
40.m)
u
u(n.))
u(n
and (1(5)) E 12,, On edge functions we use the inner product
(u, V)
Σ
Wozl((1.)) p(a))
4J=1
Multiplication between matrix and an edge function is usually defined pointwise and we use the notation [A @ (( = Ai2(((1)) E RR, for matrix A E Raxx and an edge function U E Raxxxka, to make this clear. Similarly, pointwise multiplication between two matrices A, B E Rax= is defined by [A B)g By R. When matrix is acting as a linear operator on node function we use the usual matrix-vectee notation and write (AU]() Σi= Aiy e R
for matrix A E R and node function U ([u(U]T [m(n)] E Banks In the sequel we will have bj = k2
The gradient of a node-function U (1 TT E Raxd is defined the edge- function VU E Baxxxd with (VU)6)) = 00) m E IRd The divergence div) ([div)](U]T.... ...., (T Rixd of an edge-function V E Raxaxd is defined as
( =
Σ W W(s)
for all i = 1.... n. For anti-symmetric edge functions, i.c. V(i)) = -V61.) for all i, we have that the divergence the negative adjoint to the gradient, i..
(divV, U) (V, VU).
B TECHNICAL PROOFS
[Proof of Proposition Clearly
Proof:
For notational convenience let us assume that (0) (0)
E B (0) ( (0)
for all 1,-.., n. Assume that
B (k) (6.k))
15

---

Published as a conference paper at ICLR 2022
for all i 1,....n. Then,
E B (I: + 1)]
n
x P
( (A: +1= = 2 =x("))
j=1
x p PP (k) 2 ( (1) = =(1)) P (1) = xl1))
(1- -ii lime
We
P (1) =
=x(()) x!())
di
t=1
-11 - 6:) Σ
x pp B (1) = =l11)
Σ
Wie Σ x Up ( (1) xl1)
dj t=1
j=l
+ 5c
(1 61) (k))
Σ
Wiek
B
di
1=1
de +
(1 (0
Σ
( (8ck)
d
(8,k) + 8,
Σ
Wee (x(0) (8ck))
di
t=1
(5,k)) 5, LX (5x))))
(b. 1)),
as required.
Proof: [Proof of Proposition
Let P = (Pij) Ruxx be the probability transition kernel,
if =
Pi =
W.Wo
di if
We have
di
2
(1 - أe11imp +
Σn k= dj
d;
2=
i=1
d 0.)
6e Σラ i- Wij
+
Σ k= dx
k== dr
d,
Ekmi de
Jjj
as required.
Proof: [Proof of Proposition The proof follows from simple application of Propositions Namely, for any E nn.
and
x (1)) (k6,) E B 1 (B)]
Σ
(B)
=x(0) - Σ x (i) (0)= =
1=1
==1
as l + 00.
Proof: [Proof of Proposition 4 Let
(k) = E
21)) - ② 1 1))
d
==0
jEI
16

---

Published as a conference paper at ICLR 2022
Notice that
E
1 B (1) 10
0=0 0
Σ P (s) = =
k
P (B) = x11)
+ Σ
P (8) (8)= xx)())
==1
n
P (s) 10 (B))B 1) -1]= =00 P (B 1) )0(())
6ij
t=1
4 n
(1 8,)0g1= + 5.Wii
= 6z +
P
(B -1) = xz!1)
de
f=1
k
= d, + (1 5,)
P
(s 1) = x0())
+ 5,
W &
P
- -1) = -1)= (s1)-
=)==(())
s=1
t=1
8=1
k-1
n
k-1
-oi + (1 8t)
Σ
P
(B)
(s) = 20)
+ 6z
PP
(s) = )0)
de
--
n
Wi
= 6ig + (1 T.
(z)==
+ 82
E
(+)=
de
t=1
From the definition of Y and the above recursive relationship we have
y
(k)) =
1
Σ
(
B (s)=
d2 JET.
1
20
2 8.g + (1
-8)
1
x10)
+
(()
d JET
d:
JEI
8
WH
(x((0) at) E
+
d t=1
dj
(s)
JEI
1
Σ
266 +) 8.j + (1 -8:)) (0) (k- (1)
6e
Σ
n
Why (o 1)
di jET
d, t=1
= ( (k: 1) + di
Σ
(0() - x 6is - 8, LY (A: 1)1(0
IEZ
Now we let
(b) di (2)))))))) ())
so that W satisfies
2 (1) (k) ((k) = ((( (k: - 1) - 8, [LW (k: 1 1))( = (PW - 1)1(0.
Hence, (4) = Pd ((). Since the stationary distribution of the random walk with transition
kernel is n, we have lim pk = T_T. Hence, as k + 0o, (k) + Ey= ()) = since u) (0) 0 by the choice in the initialisation of Z.
17

---

Published as a conference paper at ICLR 2022
Proof: [Proof of Proposition 5 We prove the result by contradiction. Assume that there exists such that (kóe)) + for all = ...... n2 as k + co. Then L (kō;) - O. Since we can write
(k:b.) - (ko,)) = z ((: - 1)6+) - -= ((k - 1)6z)
[LZ - 1)6,){(0 [
1alk--1000 1)6:))
5, Σ
(51((x(0)) - ②)) - -55e(x00) - -z))
RET
then taking the limit k implies
Σ
)ee
2
Σ -d -z)
EEI
FEI
for all i.j which clearly not true.
C NEURAL ODES AND TRAINING NEURAL ODES WITH ADJOINT METHOD
Neural ODEs 13
class of continuous-depth (-time) neural networks that particu- larly suitable for learning complex dynamics from irregularly sampled sequential data, see, e.g.
19 39 42. Mathematically, neural ODE is the first-order ODE:
dh(tt) (h(t),,,,) dt
(18)
where fh((t) t, Rd is specified by neural network parameterised by 8, e.g., two-layer feed- forward neural network. Starting from the input (0), neural ODEs learn the representation and perform prediction by solving (T8) from / = 0 to T using numerical integrator with given error tolerance, often with an adaptive step size solver (or adaptive solver for short) [18] Solving (18)
from 0 to 1 in single pass with an adaptive solver requires evaluating f (h((t, t, 0) at various
timesteps, with computational complexity counted by the number of forward function evaluations (forward NFEs) 13
The adjoint sensitivity method (or adjoint method) [46, is a memory efficceent method for training neural ODEs. We regard the output h(T) I as the prediction and denote the loss between ((T)) and the ground truth as L. Let at)) = aL/ah(() be the adjoint state, then we have (see [3 details)
46 for
dC
db L' a(1) @f(h(t)) t, dl,
(19)
00
with a()) satisfying the following adjoint ODE
da(t) a(t)
0h ah f(h(t),t,))
(20)
dt which is solved numerically from = to and also requires the evaluation of the right-hand side of 20 at various timestamps, and the backward NEEs measure the computational complexity.
D EXPERIMENTAL DETAILS AND MORE EXPERIMENTAL RESULTS
D.1 DATASETS AND EXPERIMENTAL SETTINGS
Graph node classification dataset. Following I0 we consider the largest connected component of seven graph node classification datasets, including CORA, CiteSeer, PubMed, coauthor graph CoauthorCS, and Amazon co-purchasing graphs Computer and Photo, and a large scale ogbn-arxiv dataset. For completeness, we list the number of classes, the number of features, and the number of
nodes and edges of each dataset Table 3 More detailed information can be found in [10]
Depth of GRAND and GRAND++ for the results in Table 1 Table 4 lists the fine-tuned T for the results in Table T Due to the limited time, we only search around the value of optimal for GRAND with grid spacing 0.1.
18

---

Published as a conference paper at ICLR 2022
Daraset
Classes
Features
#Nodes
#Edges
CORA
1433
2485
5069
CincSoer
3703
3679
PubMed
500
19717
44324
ConuthorC'S
15
6805
18335
81894
Computer
10
767
1338
245778
119043
ogba-arxiv
128
169343
1166243
Table Summary of graph node classification datasets.
CORA
CiteSeer
PubMed
CoauthorCS
Computer
Photo
GRAND++1
8.0
GRAND41
18.2948
12,9423
Table The value of fine-tuned depth the continuous- GNNs, GRAND and GRAND++ in learning with different labeling results, and the corresponding accuracy are reported in Table ! o for GRAND++ are adopted from the paper [10].
The values
D.2 CLASSIFICATION ACCURACY OF GNNS WITH DIFFERENT DEPTHS
In this subsection, provide detailed numbers that correspond to Fig. 1. We further compare GRAND++-1 with several other GNN architectures, including GCN, GAT, and GraphSage, with different depths few benchmark datasets. Table lists the classification accuracy of GRAND++, GRAND, and three benchmark GNNs with different depths on six graph node classification tasks. Again, we that GRAND+ is better than the other GNN models when the networks deep.
Model
depth
CORA
CiteSeer
PubMed
CoauthorCS
Computer
Photo
77 + 1.43
71.23
3.47
78.11 + 1.47
90.42 + 0.76
84.11 + 0.51
92,93 + 0.84
81.98
1 1.42
72.58
3.79
79.20
0.74
90.89
0.36
84.19
1 0.93
93.54
0.38
1.37
73.84
2.66
79.49
0.84
90.24 NA
0.30
78.97
2.33
92.69
0.61
GRAND++-1
32
82.48 + 0.71
73.29
1.29
79.81
L.11
76.01
+ 1.33
92.94 NA
0.90
(ours)
64
80.99
+ 1.76
72.81
2.18 NA
NA
NA
NA
80.29
1.98
NA
256
79.04
82.80
1.62
73.87
2.12
78.71
1.19
90.94
0.21
84,23
1 1.05
92.47
0.53
16
82.75
+ 1.17
72.61
2.42
78.79
+ 0.93
87.66 + L.70
77.67
+ 1.94
92.37
0.27
GRAND-I
32
82.19
1.73
3.15 72,65
78.70
1.08
NA
69.56
J. 2.20
89.61
1.33
80.87
128
77.22
+ 2,88
NA
NA
NA
NA
NA
256
67.79
1: 3,10
NA
NA
NA
NA
NA
76.92 + 0.56
72.80
1,69
72.78 + 1.80
91.53 + 0.45
81 + 0.24
91.31 0.19
GCN
4
81.35 + 1.27
70.54
6.61
77.15
+ 3.00
87.84 + 0.96
75.73 + 1.02
90.1 + 0.66
A0
1.77
1.76
21.80 21.86-2 = 6.09
1,65
40.06
1.86
12.14 1.64
21.15
- 0.73
0.37
GAT
80.95
1. 2.28
72.31
2.82
77.37
1: 1.32
78.05
1.10
76.67
1: 2.79
87.95
1.76
S
16
29.14
1: 1,02
24,84
1.45
39.21
1 0.43
24.20
1 2.22
37.07
1: 2.99
29,97
3.68
32
29.75
+ 1.57
24.83
1.45
39.02
0.12
22.73 2.08
32.53
3.09
25.57
4.03
73.47 + 1.98
71.94
1.45
72.42 + 0.61
91.74 + 0.26
75.95 + 0.70
88.10 + 0.87
GraphSage 20
79.83
2.43
50.00
14.27
76.01
2.35
87.94
0.23
75.62
90.68
2.11
16
25.5 22.52-1
6.45
24.84
1.45
37.55
3.92
10.12
2.21
22.79
10.77
25.57 3,31
32
29.14 + 1.02
28.38
2.54
39.21
4.39
7.91
3.15
37.07 + 13:22
20.09 + 5.67
Table 5: Classification accuracy of different GNN models with different depths on six benchmark graph node
classification tasks. NA: neural ODE solver failed. These results show that GRAND++ is better suited for learning with very deep architecture than GRAND. (Unit: %)
D.3 MORE RESULTS ON TIME-DEPENDENT ATTENTION AND GRAPH REWIRING
We further explore the effects of the source term for GRAND-nl and GRAND-nI-rw in the low- labeling rate regimes. Table 6 compares GRAND-nl and GRAND-nl-rw with the corresponding model with source term. We that GRAND-nl and GRAND-nl-rw are almost always worse than the vanilla GRAND-I, consistent with the results reported [10]. GRAND++-nl and GRAND++- nl-rw cannot help learning at low labeling rates anymore. However, when the labeling rates not low, GRAND++-nl or GRAND++ can outperform GRAND-nl and GRAND ml-rw, even outperform GRAND++.
19

---

Published as a conference paper at ICLR 2022
Model
#per class
GRAND-ol [0
GRAND-sI-ww 10
GRAND++-al (ours)
GRAND+ (ours)
50.55 + 15.68
50.63 + 17.71
48.89
11.51
47.94 + 11.06
65.06 + 9.35
61.24
16.19
59.96
58.25 - 11.97
CORA
76.93 1: 3.10
76.50
3.91
74.01
1.73
74.25 1: 1,99
10
79.60 + 2.69
79.38 + 3.25
80.14 = 0.69
80.18 : 0.40
20
82.22 + 1.93
82.14 + 2.49
83.24 = 0.20
81,48 1,07
50.25 + 17.66
50.20 + 17.90
49.65
5.45
53.10 5.51
59.87 10.89
59.95 + 10.48
59.16 8.13
60.26 5.10
CiteSeer
5.48
10
88 + 6.94
71.92 + 7.34
68.84
2.84
71.45 1.64
20
72.84 1 6.61
72.72 1 6.85
72.52
1.24
73.87
1,35
66.97 1. 10.07
67.69 1: 7.89
63.85
4.86
67.45
3.88
69.17 1: 2.46
69.42 2.13
66.98
5.30
69.11
1: 1.80
PubMed
2.52
10
76.03 1. 3.73
75.32
3.45
74.94
2.15
75.09
2.88
20
78.55 1: 1.59
78.30 +
1.43
78.41 :: 0.99
79.44 1 0.56
Table 6: Classification accuracy of the variants of GRAND and GRAND++ models trained with diffcrent numbers of labeled data per class (#pper class) on graph node classification lasks. (Unit: %)
D.4 CLASSIFICATION ACCURACY OF GNNS WITH PEWER NUMBER OF TRAINING DATA
Besides the results shown in Fig. we further test the classification accuracy of more benchmark GNN architectures trained with fewer numbers of labeled data per class. Tables 7 list the classi- fication accuracy, on the test set, of different benchmark GNN models when they are trained with different numbers of labeled nodes per class.
#laboled nodes per class
5
10
20
GCN
30
47.72
15.53
60.85 + 14.01
73.86
+ 7.97
78.82
5.38
82.07 + 2.03
GAT 54
47.86
15.38
$8.30 + 13.55
71.04
5.74
76.31
4.87
79.92 - 2.28
GraphSage
MoNet H0
47.72
15.53
60.85
14.01
73.86
7.97
78.82
5.38
82.07
2.03
Lanzzos 36
47.41
11.82
60.94
4.00
74.28
1.07
76.12
0.93
79.85
1.82
Adalzanczos 56
48.23
11.82
61.46 1 4.96
74.24
3.25
77.61
1.36
81.03
1.56
GCNN
GRAND
[10
$2.53
16.40
64.82
11.16
76.07
5.08
80.25
3.40
82.85
GRAND-al 10
40.97
14.87
50.59
1: 13.25
65.13
9.14
72.55
1 6.65
77.76
4.21
GRAND-al-ww (gde)
10
52.68
12.48
65.54 + 10.01
74.94
7.04
80.64
6.19
82.47
1.93
GRAND (two (two-hop)
11.88
Table 7: Classification accuracy of different GNNs trained with different numbers of labeled nodes per class.
Dataset: CORA.
Plabeled nodes per class
10
20
1:
3.47
GAT S4
50.31 +: 14:27
55.55 + 9.19
67.37
+ 5.08
71.35
+ 4.92
73.22
2.90
GrahSaage 20
48.81 +: 11.45
54.39 + 11.37
64.79
4 5.16
68.90
1 5.08
72.02
+ 2.82
MoNet 40
39.13 1. 11.37
48.52 1. 9.52
61.66
6.61
68.08
6.29
71.52
1 4.11
Lanczos
49. 3663
57.65 7.60
71.01
72.14 2.00
Adal ancrns
50.32
7.42
58.35
7.97
67.39
1 8.20
72.15
74.33 1 2,83
GCNN [58]
40.58 1. 15.32
51.71 1 13.87
63.16
12.26
67.06
1. 5.65
69.84
1 1.77
GRAND-I [0]
50.06 + 17.98
59.55
10.89
68.37
5.00
71.90
7.66
73.02
5.89
GRAND-al
6.94
6.61
GRAND nl rw
(gio)
10
50.35 1. 17.74
59.98
1 10.32
68.39
5.81
71.33
7.26
72.81
6.94
GRAND-ol-rw (two-hop)
50.20 + 17.90
59.95
+ 10.48
68.05
5.49
71.92 + 7.34
72.72
+ 6.85
Table 8: Classification accuracy of different GNNs trained with different numbers of labeled nodes class.
Dataset: CiteSeer.
D.S T-TEST OF THE ACCURACY IMPROVEMENT OF GRAND++ OVER GRAND
To confirm the statistical significance of the accuracy improvement of GRAND++ over GRAND in T in this subsection, we conduct t-test experiments at 0.95 confidence to compare GRAND and GRAND++ on six different benchmark graph node classification tasks. We first perform unpaired t-tests to show the improvement of GRAND++ over GRAND on low labeled datasets using the following t-score
MGRAND++ JAGRAND
t-score
(21)
GRANDIL
GRAND
n1
76
20

---

Published as a conference paper at ICLR 2022
#labeled nodes per class
2
5
10
20
GCN
50
58.61 +: 12.83
60.45
+ 16.20
68.69
7.33
72.59
+ 3.19
76.89
3.27
58.84 +: 12.81
60.24
14.44
5.75
72.44
3.50
75.55
4.11
GraphSage 29
55.53 1: 12.71
58.97
1: 12.65
66.07
6.16
70.74
3.11
74.55
3.09
MoNett H0
56.47 = 4.67
61.03
6.93
67.92
= 2.50
71.24
+ 1.54
76.49
+ 1.75
Lanczos
30
60.12 6.37
63.65 11655000 6.97
70.61
= 4.50
73.01
3.27
78.35
+ 1.84
AdaLanccos
GCNN
338
60.78 + 20.64
65.14 19.45
72.72
1082
76.47
6.03
79.24
3.45
GRAND 10
62.11 1: 10.58
69.00
7.55
73.98
5.08
76.33
1. 3.41
78.76
1.69
GRAND-nl 10
61.75 1 11.12
69.16
8.46
72.35
5.35
76.03
3.72
78.55
1.59
GRAND-nl-rw (gdo)
8.21
GRAND rw (two hop)
10
61.65 1 12.09
68.49 8.99
72.68
5.92
75.72
3.50
78.77
1.88
Table Classification accuracy of different GNNs trained with different numbers of labeled nodes per class. Dataset: PubMed.
where μ and 2² the mean and variance of the performances of each model, and n is the number of runs for each model. The t-test score are shown in Table I0
#per class
CORA
CiteSeer
PabMed
CounthorCS
Computer
Photo
4.36
3,28
1,55
111.60
45.33
1.39
3.96
0.34
4.59
7.18
4.65
2.55
2,68
-3.67
-1.96
15.67
0.26
Table 10: Unpaired t-test scores of GRAND++ v.s. GRAND on six different benchmark graph node classifica- tion tasks. With 100, over 0.95 confidence is equivalent to exceed roughly 1.66 t-test scores. Highlighted the passing the test.
For some entries To are not significant enough, we further conduct paired t-test between GRAND++ and GRAND on these specific datasets shown in Table II Since large portion of variance comes from splitting of the datasets, we pair up tests of GRAND and GRAND+ with the same splitting in this experiment. In this case, sample of difference of size is computed, and t-test score can be computed using the equation
/diff
t-score
(22)
dant vn
#per Accuracy Difference
splits
p-score
CORA
+ 6.24
100
1.80
0.044
Table 11: Paired scores of GRAND+ GRAND datasets where unpaired t-test scores are significant enough.
D.6 TASKS FOR FURTHER EVALUATING DEEP GRAND AND GRAND++
Open graph benchmark with paper citation network (ogbn-arxiv). Ogbn-arxiv consists of 169, 343 nodes and 166, 243 directed edges. Each node an arxiv paper represented by 128- dimensional features and each directed edge indicates the citation direction. This dataset is used for node property prediction and has been a popular benchmark to test the advantage of deep graph neural networks shallow graph neural networks 34] 32 Compared to the GRAND model used in [10], we reduce the hidden dimension from 162 to 81 to fit the model into the GPU in our lab.
Model
depth (T)
GRAND-I 10
GRAND++J (ours)
Improvement from GRAND++-1 (ours)
68.50 + 0.76
68.79 :: 0..5
0.29
69.46
1 0.43
69.71
0.24
0.25
8
69.44
1 0.30
69.61
0.28
0.17
OGBN-aXiv
32
67.44
+ 0.59
69.41
0.53
1.97
96
55.95
1.24
67.26
0.61
11.31
Table 12: Classification accuracy of the lincar GRAND and GRAND++ models trained with different depth on the OGBN-arXiv graph node classification task. Compared to the GRAND model used in [00] we reduce the hidden dimension from 162 to 81 to fit the model into the GPU in our lab. (Unit: %)
21


Reviews:
[{"review_id": "q0xlJ5HAumT", "reviewer": "Reviewer_zJ38", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\nThe authors provide comprehensive background knowledge for the different parts of their algorithem.\n\nThey theoretically show that the source term helps alleviate the over-smoothing problem.\n\nThe experiment regarding limited label data is interesting.\n\nCons and concerns:\n\nOne of my main concerns is the empirical results reported in the paper. Specifically, I would be grateful if the authors could elaborate on why there is a mismatch between the results reported for the \"GRAND\" method (when for each label, 20 samples were used) in the original paper and the numbers reported in the current submission. For instance, on CORA dataset, the GRAND paper reported 83.6 ± 1.0 while the submission reported GRAND test accuracy as 82.86 ± 2.39. This is important because the test accuracy of GRAN++ is 82.95 ± 1.37.\n\n\n\n\nTo actually show that GRAND++ is empirically better than other methods, the authors need to do a t-test. That is because std. of the reported test accuracy is too high (16 percent for CORA) when the number of observed samples for each label is less than 20. Note, this is different from having a small improvement; the t-test has to be done to show whether there is actually an improvement or not.\n\n\n\nLack of experiments on datasets that needs larger depth NN. Authors motivate their method by mentioning that they avoid over-smoothing; however, there must be an empirical need to develop such methods.  I suggest authors to experiment on a dataset that needs large depth to show the importance of their contribution.\n\n\n", "summary_of_the_paper": "This paper studies neural-based diffusion models for graph data. It considers deep learning on graphs as a continuous diffusion process and treats GNNs as discretizations of an underlying PDE. The authors build upon an existing work (GRAND) by adding a source term to the objective function. The source term is designed to alleviate the over-smoothing problem of GNN, a well-known phenomenon that deeper GNN learns similar representation for each node. They theoretically show the effectiveness of the source term in mitigation over-smoothing problem. Furthermore, they empirically assess their method's effectiveness in learning with limited labeled data and using deep architectures on several benchmark datasets.", "summary_of_the_review": "Please look at the comments provided above.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jglDeSz_aQs", "reviewer": "Reviewer_qrMB", "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": "Strengths: The problem faced by the paper is interesting and timely and the proposed approach seems reasonable. The article is well written, the method is clearly described, and the overall quality is good. The authors also provide the source code to facilitate experimental replication.\n\nWeakness: \n1. This paper is more like an external version of GRAND. The author spends a lot of time on background knowledge and GRAND's work, which may undermine the contribution of this paper.\n2. The assumption of Proposition 2 and 3 seems a little bit strong. We cannot guarantee how the graph data will look like, nor can we guarantee that the graph is connected. \n3. I have some doubts about the 5.2 experiment, why use a setting where each class has only one label. In the above experiment, the authors used 20 labels per class, while in this experiment just 1 label was used. I would like to have some intermediate stage of experiments, like 5/10 labels per class.\n", "summary_of_the_paper": "In this paper, the authors propose a graph deep learning method called GRAND++. This framework based on GRAND and can work with a limited number of labeled nodes. Experiments are also conducted to demonstrate the effectiveness of the method.", "summary_of_the_review": "The overall quality of the paper is good, with a clear narrative. The problems addressed are also much needed. The methodology is straightforward and clear, and there is also theoretical guarantee. So I recommend it for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "cg5IxwOH8WL", "reviewer": "Reviewer_durM", "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": "Strengths:\n1) Overall, I feel this is a well-organized paper and I enjoy reading it. This paper describes clearly the motivations of their model design. It also provides complete theoretical results and examples to explain the claimed issue (over-smoothing) and how the proposed method could solve it. \n2) The proposed model is simple and neat. By simply adding the constant source term to the original diffusion equation and adjusting the initial conditions, this model is able to prevent the over-smoothing issue of diffusive GNN models. Moreover, this model could reuse the design and implementations of its source-term free version (GRAND). \n3) The ablation study plots suggest that this model is able to effectively alleviate the important problem of over-smoothing issue of GNN models and benefits from adding more depth to the network. \n\nWeakness:\n1) The accuracy gains are not stable. The proposed method has worse classification accuracy than GNN and GCN significantly in the CoauthorCS dataset. The causes remain unexplained. Also, on CORA and CiteSeer the added source-term are worse than the baseline GRAND model. \n2) This paper uses the classification with low-labeling rate as the prediction task to validate the effectiveness of preventing over-smoothing. However, over-smoothing could happen even without low-labelling rate. It is not clear whether the proposed method could practically solves the over-smoothing problems. ", "summary_of_the_paper": "This paper proposes a novel graph diffusion model with a source term in order to solve the over-smoothing issue of GRAND model and GNNs with diffusive property when the depth of the GNNs is large. This design also leads to a class of more accurate GNN based classification models when the labeling rate in the graph is low. ", "summary_of_the_review": "In general, this is a solid paper which proposes a novel idea to solve the over-smoothing problem the GNN models using a special form of graph diffusion equation. Solid theoretical and experimental results are provided in the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "b2d0tAd9M_", "reviewer": "Reviewer_y1z1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n\nPros:\n- The problem is, in my opinion, both interesting and relevant for the research community\n- The model seems to perform particularly well when there are very, very few labeled data points\n\nCons:\n- A few parts are introduced without much context or references in the text, e.g. Laplace and Poisson learning are cited as related work but the connection to the present one is not clear enough IMO (except for the problem of inference inconsistency at low labeling rate)\n\n- Formulation is not always clear, e.g.:\n  - in Eq (3), $\\tilde L$ is introduced as a shorthand for $(I-\\delta_{t}L)$. Does this matrix have any particular interpretation? \n  - in page 4, between (6) and (7), $h$ is used both as an index for layers and as the max value (something like $\\sum_{l=1..h} A^{l}(X)$ or even just using $l$ would make it more readable)\n  - the random walk definition in (8) did not convince me (perhaps because it was introduced with no further explanation). How is the step size $\\delta_t$ defined? To me it should not be possible to use it as in $1 - \\delta_{t}$ to define a probability value, as there was no definition of $T$ thus it can take any value greater than zero. \n  - in Eq (10.5), $\\pi_{j}=: \\tilde{x}$ shouldn't this be $\\bar{x}$ instead?\n\n- experimental results are, in my opinion, not convincing:\n  - related to the claim of performing better with fewer labeled data, while there are some datasets in which the method actually does well there also many cases (CoauthorCS, most of Computer, and Photo) in which it is worse or comparable to simpler approaches (learning the reasons why this happens, though, would be interesting per se)\n  - still related to numbers, the noise of low-labels dataset is such (and the variance is so high) that even results out of 2000 experiments are not statistically very significant: some of them (e.g. CORA-20, PubMed-2, Photo-20) have a p-value > 0.1.\n  - it is not clear why depth should be such a useful treat when both GRAND and GRAND++ have deteriorating performances when it grows (e.g. in Figure 2, 1-3 from left). In these cases GRAND seems to perform better or comparably most of the times (with the advantage of being simpler). Plots with small amount of labeled samples, instead, look more convincing in my opinion (i.e. they clearly show a use case in which GRAND++ would be preferable)\n", "summary_of_the_paper": "The paper introduces GRAND++, GRAph Neural Diffusion with a source term. As its predecessor GRAND, this method is focused on the development of a new continuous-depth GNN to tackle the over-smoothing and the bottleneck issues which are typical of deep GNNs.\nThe authors introduce a random-walk interpretation of GRAND, which shows that when the network is very deep it is still prone to over-smoothing. To address this problem they add a source term to the problem formulation, which is shown to provide better results in very deep models and in classification tasks which are characterised by a low amount of labeled data.", "summary_of_the_review": "I think the paper tackles an interesting problem and provides evidence that, in some extreme cases such as incredibly low amount of labels per class, it can outperform other approaches.\n\nHowever, of its two main claims (avoiding over-smoothing and working well with few labels), I think the former is a bit harder to defend (GRAND++ is always better than GRAND when depth is very large but not always otherwise, in addition it is does not always exhibit the same behavior and it not clear why that happens). For the low-label case, I think there are more chances to convince about the improvement brought by the model but I think it would be important to better understand the reasons for it. Intuitively, a strong bias is introduced by the insertion of the source term that definitely helps by providing useful signal for the classification. This should be, in my opinion, discussed more in detail and verified with more examples.\n\nFor the above reasons, I consider the paper still not mature enough for publication but I think a more in-depth analysis could bring valuable results.\n\n----\n\nThe authors' replies addressed my concerns and after reading their answers to other reviewers and the updates to their manuscript I decided to increase my rating. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G4JnTP3q20f", "reviewer": "Reviewer_p1wb", "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": "The paper addresses an important issue which affects neural ODEs and deep NN on graphs. In particular, concerning the GRAND differential equation, I think that adding a source term is an important idea essential to obtain a non-trivial long term behaviour of the dynamical system. This is clear when looking at linear dynamics (as done in the paper) as it is well known that the system converges to the dominant eigenmodes in that case. In fact, the addition of a source term is typical of most diffusion models on graphs, including standard Label Spreading/Label Propagation and their variants. \n\nWeaknesses:\nThe paper is sometimes poorly written with several typos affecting the mathematics. I list below some of the major points that require improvement to my opinion:  \n- In the notation, the Hadamard product should be explicitly defined (or maybe just say that this is entrywise multiplication)\n- Eq (1) uses notations that are not mentioned in the main paper such as $\\nabla$ or $\\mathrm{div}$ operators (they are in the supp material). I believe it would be very helpful to recall what this operators are in the main text. \n- Right after eq (1): you consider the simplest case where $G$ is only dependent on the initial $X=X(0)$. However, this is not clear. This is a particular choice of $G$ that does not change in time, it is not the only one. Also, your choice seems to have no dependence on $X$ but rather on $W$ (the graph structure). So this seems to be the case of a $G$ that does not depend on $t$ NOR on $X$. In fact, soon afterwards at the beginning of $\\S 3$ you consider another case where there is no dependence on $t$ but there is dependence on $X$ via the attention matrix $A(X)$. Also, what do you mean by \"so we pick $G_{ij} = 1/d_i$? When do you pick this? Overall, I find this paragraph very confusing \n- Why does the step size in Euler depend on $t$? It seems to me this is just a constant in your subsequent derivations\n- Before eq (6) you quote eq (2) while I think you should refer to eq (1)\n- You define GRAND-l after eq (7) but this definition is not clear to me. Right before you say that GRAND is based on the solution of (5) via ODE solvers. But then, when you define GRAND-l you refer to the attention matrix $A(X)$, which may not appear in (5). As you will use GRAND-l often in the rest of the paper, I believe this deserves a more clear definition here\n- In the definition of the random walk (8), is $x^{(i)}=x^{(i)}(0)$? Also, this is quite unusual definition: typically the state space of a random walk on a graph are the nodes not on the their feature embedding. What is the advantage of defining the RW on the features?\n- Again, the notation in Proposition 3 is not clear: what is $x^{(j)}$? \n- Equation (1): what does \"the source at feature vector of node $j$\" mean?\n- Starting from section 4 you move from $X(t)$ to $Z(t)$ in a way that is to my opinion inconsistent and not clear.\n- In the centred equation after (10) there are several typos: I think $x$ should be $z$ or maybe you should use $x$ in (10) rather than $z$? $\\tilde x$ was $\\bar x$ in prop 3; I think your approximate dynamics should be $-x^{(i)}(t) + A\\bar x$ rather than $-x^{(i)}(t) + \\tilde x$, or could you clarify why this is not the case?\n- Right after that equation you state: \"for $i\\in I$ we choose $c$ so that $z'(t)\\approx 0$. This is not clear to me. What is $c$? What does $z'(t)\\approx 0$ mean?\n- The statement of Proposition 5 is quite sloppy. First, it is not clear what $z(k\\delta_t)$ is? Is this the one from (14)? Second, mathematically, \"it does not converge to a constant vector\" makes not much sense? For example, if constant means that the limit does not depend on $t_0$, then this is probably not true. If it means that it has all constant entries, than still this might no be true as it would depend on the initial feature space. A much more precise statement to my opinion would say what the sequence converges to, rather than what it does not. \n- Concerning this convergence questions, overall I do not really understand why you are considering the convergence of the sequence obtained via Euler integration, rather than the real dynamical system. Since you are anyway considering the simplest case of a linear dynamical system, why don't you consider the exact solution and study its behaviour? The fact that Euler converges to something might not mean that any numerical integrator would\n- As stated above, in the experiments you mention GRAND-l and GRAND++-l but it is not clear to me what exactly are those\n\n", "summary_of_the_paper": "The paper proposes a modification of the continuous-time graph neural network architecture GRAND where a source term is added to the differential equation in order to (a) avoid convergence of the dynamics towards constant vectors and thus mitigate the over-smoothing effect which affects the long time behaviour of the original dynamical system and graph neural networks with many layers in general and (b) increase classification performance under limited number of training points. ", "summary_of_the_review": "I like very much the idea of modifying the Laplacian diffusion equation div-grad used in GRAND adding a source term. The theoretical analysis proposed in the paper deals mostly with the simplest case of a linear diffusion operator, which is certainly useful to gain intuition. However, no attempt to transfer the results to more general nonlinear settings are discussed. Moreover, the mathematics contains many typos and a number of statements that are vague or not clear.", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: The paper presents a continuous framework for GNNs based on neural diffusion PDE and is an evolution of a previous method (GRAND). The main novelty appears to be the additional source term, which the author show to be beneficial in reducing the oversmoothing effect typical in deep GNNs. While novelty is somewhat limited, the paper provided detailed theoretical and experimental assessment of the idea. Overall, the reviewers liked the approach and expressed some questions/concerns that were satisfactorily addressed in the rebuttal. We recommend acceptance.
Decision: Accept (Poster)