DeepGRAND: Deep Graph Neural Diffusion
Authors: Khang Nguyen
Nong Minh Hieu
Tan Minh Nguyen
Nguyen Duy Khuong
Vinh Duc NGUYEN
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph neural diffusion
graph neural networks
oversmoothing

Abstract: We propose the Deep Graph Neural Diffusion (DeepGRAND), a class of continuous-depth graph neural networks based on the diffusion process on graphs. DeepGRAND leverages a data-dependent scaling term and a perturbation to the graph diffusivity to make the real part of all eigenvalues of the diffusivity matrix become negative, which ensures two favorable theoretical properties: (i) the node representation does not exponentially converge to a constant vector as the model depth increases, thus alleviating the over-smoothing issue; (ii) the stability of the model is guaranteed by controlling the norm of the node representation. Compared to the baseline GRAND, DeepGRAND mitigates the accuracy drop-off with increasing depth and improves the overall accuracy of the model. We empirically corroborate the advantage of DeepGRAND over many existing graph neural networks on various graph deep learning benchmark tasks.

Under review as a conference paper at ICLR 2023
DEEPGRAND: DEEP GRAPH NEURAL DIFFUSION
Anonymous authors
Paper under double-blind review
ABSTRACT
We propose the Deep Graph Neural Diffusion (DeepGRAND), class of continuous-depth graph neural networks based on the diffusion process on graphs. DeepGRAND leverages a data-dependent scaling term and a perturbation to the graph diffusivity to make the real part of all eigenvalues of the diffusivity ma- trix become negative, which ensures two favorable theoretical properties: (i) the node representation does not exponentially converge model depth increases, thus alleviating the over-smoothing issue; (ii) the stabil- ity of the model is guaranteed by controlling the norm of the node representation. Compared to the baseline GRAND, DeepGRAN AND mitigates the accuracy drop-off with increasing depth and improves the overall accuracy of the model. We empiri- cally corroborate the ad advantage of DeepGRAND over many existing graph neural networks on various graph deep learning benchmark tasks.
constant vector the
INTRODUCTION
Graph neural networks (GNNs) and machine learning on graphs (Bronstein al.) 2017: Scarselli
et al. 2008) have been successfully applied in wide range of applications including physical model-
ing Duvenaud al.] 2015 Gilmer et al. 2017 Battaglia al. 2016). recommender systems (Monti et al. 2017 Ying et al. 20118), and social networks (Zhang & Chen] Qiu et al. 2018). Recently, more advanced GNNs have been developed to further improve the performance of the models and extend their application beyond machine learning, which include the graph convolutional networks (GCNs) (Kipf Welling 2017), ChebyNet (Defferrard et al.) 2016), GraphSAGE (Hamilton et al.) 2017). neural graph finger prints (Duvenaud 2015). message passing neural network (Gilmer et al. 2017), graph attention networks (GATs) (Veličković et al. 2018), and hyperbolic GNNs (Liu al. 2019). A well-known problem of GNNs is that the performance of the model decreases sig- nificantly with increasing depth. This phenomena is common plight of most GNN architectures
and referred as the oversmoothing issue of GNNs (Li al. 2018 Oono & Suzuki 2020 Chen
et al. 2020).
1.1
MAIN CONTRIBUTIONS AND OUTLINE
In this paper, we propose Deep Graph Neural Diffusion (DeepGRAND), a class of continuous- depth graph neural networks based on the diffusion process on graphs that improves on various aspects of the baseline Graph Neural Diffusion (GRAND) (Chamberlain et al. 2021b). At its core, DeepGRAND introduces data-dependent scaling term and perturbation the diffusion dynamic. With this design, DeepGRAND attains the following advantages:
1. DeepGRAND inherits the diffusive characteristic of GRAND while significantly mitigates the over-smoothing issue.
2. DeepGRAND achieves remarkably greater performance than existing GNNs and other GRAND variants when fewer nodes are labelled as training data, meriting its use in low- labelling rates situations.
3. Feature representation under the dynamic of DeepGRAND is guaranteed remain bounded, ensuring numerical stability.
Organization. In Section 2 we give a concise description the over-smoothing issue of general graph neural networks and the GRAND architecture. A rigorous treatment and further discussions

---

Under review as a conference paper at ICLR 2023
showing the inherent over-smoothing issue in GRAND is given in Section The formulation for DeepGRAND is given in Section where we also provide theoretical guarantees on the stabil- ity and ability to mitigate over-smoothing of DeepGRAND. Finally, demonstrate the practical advantages of DeepGRAND in Section [. showing reduced accuracy drop-off at higher depth and improved overall accuracy when compared to variants of GRAND and other popular GNNs.
1.2 RELATED WORK
Neural ODEs. Chen al. (2018) introduced Neural ODEs, class of continuous-depth neural
networks with inherent residual connections. Follow-up works extended this framework through techniques such as augmentation (Dupont et al., 2019), regularization (Finlay et al. 2020), momen- tum (Xia et al. )021). Continuous depth GNN was first proposed by Xhonneux et al. (2020).
Over-smoothing. The over-smoothing issue GNNs was first recognized by et al. (2018). Many recent works have attempted to address this problem (Oono & Suzuki 2020; Cai & Wang 2020
Zhao & Akoglu 2020). connection between the over-smoothing issuc and the homophily property of graphs was also recognized by Yan et al. (02TT.
PDE-inspired graph neural networks. Partial differential equations (PDEs) are ubiquitous mod- mathematics, arising naturally in both pure and applied mathematical research. A number of recent works in graph machine learning has taken inspiration from classical PDEs, including: diffu- sion equation (Chamberlain et al. 2021b Thorpe et al. 2022), wave equation (Eliasof al. (021), Beltrami flow (Chamberlain et al. (2222222 Ia), etc. Such approaches have led to interpretable architec- tures, and provide new solutions to traditional problems in GNNs such over-smoothing (Rusch) et al. 2022) and over-squashing (Topping et al. (022)..
BACKGROUND
Notation. Let (V.8) E) denote graph, where V is the vertex set with | n and & is the edge set with [3 For vertex u in V, denote Nu the set of vertices neighbor to u E G. We the features, i.e, number of features for each node. Following
denote d as the dimensionality the convention of Goodfellow et al. (2016), we denote scalars by lower- or upper- case letters and vectors and matrices by lower- and upper-case boldface letters, respectively.
2.1 GRAPH NEURAL NETWORKS AND THE OVER-SMOOTHING ISSUE
As noted by Bronstein et al. 2021). ). the vast majority of the literature on graph neural networks can be derived from just three basic flavours: convolutional, attentional and message-passinng The cornerstone architectures for these flavours are GCN (Kipf & Welling (017). GAT (Veličković et al.) 2018 and MPNN (Gilmer et al. 2017). the last of which forms overarching design over the other two. An update rule for all message passing neural networks can be written in the form
H. = X.. θ M(X,, X.) vEN.
where a is learnable message function, + is permutation-ivvariant aggregate function, and is the update function. In the case of GCN or GAT, this can be further simplified to
H. =
Σ (EN.U(M)
awo
where a either given by the normalized augmented adjacency matrix (GCN) or the attention mech- anism (GAT), y is linear transformation, and a is activation function.
The learning mechanism behind GCN was first analyzed by Li et al. (018). who showed that graph convolution is essentially type of Laplacian smoothing. It was also noted that deeper layers stacked, the architecture risks suffering from over-smoothing. This issue makes features indistin- guishable and hurts the classification accuracy, which goes against the common understanding that
2

---

Under review as a conference paper at ICLR 2023
the deeper the model, the better its learning capacity will be. Furthermore, it prevents the stacking of many layers and impair the ability to model long range dependencies.
Over the past few years, over-smoothing has been observed in many traditional GNNs, prompting flurry of research into understanding (Oono & Suzuki 2020 Cai & Wang 2020 Yan et al. 2021
and alleviating (Luan et al. 2019 Zhao & Akoglu 2020 Rusch et al. 2022 the issue.
2.2 GRAPH NEURAL DIFFUSION
GRAND is a continuous-depth architecture for deep learning on graph proposed by Chamberlain et al. 2021b). It drew inspiration from the heat diffusion process in mathematical physics, and
follows the same vein as other PDE-inspired neural networks (Rusch et al. [002]] Eliasof et al.j
2021 Chamberlain al. 2021a). Central to the formulation of GRAND is the diffusion equation
on graph
(x div div(G((X())
0L
is an e diagonal matrix giving the diffusivity between connected vertices, which describes the thermal conductance property of the graph, The architecture utilises the encoder-decoder design given by Y ((()))) where (TT E Rexd is computed as
where G diag (a(X, X, ()) (f),,
X(T) = x()) + /-' 0x
Ot (t)dt, with (() 6(X).
In the simplest case when G is only dependent the initial node features, the differential in equa- tion simplifies to
ax ai (t) = (A(x) - (t),
(4)
where A(X) = [(a(X.(t), X,, (1), an n n matrix with the same structure the adjacency matrix of the graph. From now on, we omit the term X when writing A A(X). The entries of A are exactly those in G. and thus determines the diffusivity, Furthermore, A can be informally thought of as the attention weight between vertices. Building upon this heuristic, GRAND models the attention matrix A equation 4 by the multi-head self-attention mechanism, where
- h
=
A (X)
(5)
with h being the number heads and the attention matrix A'(X) = (a'(X, (xx,,x)), X,)), forl 1, 1,...,A With this specific implemennation, which is called GRAND-I, we obtain matrix with positive entries.
....,, h
right-stochastic
As has been pointed out by Chamberlain al. 2021bb Thorpe et al. 2022 many GNN architec- tures, including GAT and GCN, can be formalised as discretisation scheme of equation 2 if no non-linearity is used between the layers. The intuition behind the connection can readily be seen from equation [ where each subsequent node data is computed similar or equal to weighted aver- age of the neighboring node features. This gives rise the diffusive nature of these architectures, resonating with the work of Gasteiger et al. (2019), which asserts that diffusion improves graph learning.
The choice of using a time-independent attention function amounts to all the layers sharing the same parameters, making the model lightweight and less prone to over-fitting. The original authors claimed that this implementation solves the ovor-snoothing problem and performs well with many layers. However, our analysis shows that this is not the case.
3 DOES GRAND SUFFER FROM OVER-SMOOTHING?
Various works OOno & Suzuki 2020
Cai & Wang 2020 Rusch al. 2022 have attributed the
occurrence of the over-smoothing issue to the exponential convergence of node representations. We formally define this phenomenon for continuous depth graph neural networks.
3

---

Under review as a conference paper at ICLR 2023
Definition 1. Let (t) Ruxd denote the feature representation time t 2 0. X is said to
experience over-smoothing if there exists a vector v E E and constants C1, C2 > O such that for V = (v, 20
X Vi S C1t
This definition is similar in spirit to the one given by Rusch et al. (022). We will show that the GRAND architecture suffers from over-smoothing.
Proposition 1. Given a positive right-stochastic matrix A E [Rxx, there exists an invertible matrix P E C such that
0
0
J
0
P P- (A-I)E I)P
Jm/
where each J; is Jordan block associated with some eigenvalue Be of A with Re Br < 0, and P can be chosen such that its first column is the vector (1, l,.,, 1)
The Jordan decomposition of allows to study the long term behaviour of GRAND through its matrix spectrum. The fact that the real part of all eigenvalues of A - I is equal or lesser than 0 will be essential our analysis.
Proposition 2. With the dynamic given by equation over-smoothing.
equation 4 and equation 3
X experiences
Remark 1. random walk viewpoint of GRAND was given by Thorpe et al. (2022). Using this, the authors were able to show node representations in the forward Euler discretization of the GRAND dynamic given by
((k,,) ((
6, ()X - 1)6.). for = = K and o < <1,
converges in distribution to stationary state. Our spectral method can be adapted this discretized setting (see Appendix D). We note that our analysis is strictly stronger through both the use of the co-norm and the exact exponential rate of convergence.
Proposition 2 conclusively shows that GRAND-I still suffers from over-smoothing. Of course, if consider more general variants GRAND, the above arguments no longer hold. Although we can rigorously assert that over-smoothing affect all implementations of GRAND, it can be argued that the occurrence of this phenomenon in GRAND intuitively makes sense since diffusion have the tendency to 'even out' distribution over time (further discussion can be found Appendix B) Hence, a purely diffusion based model like GRAND is inherently ill-suited for deep networks.
4 DEEPGRAND: DEEPER GRAPH NEURAL DIFFUSION
4.1 MODEL FORMCLATION
We propose DeepGRAND, new class of continuous-depth graph neural networks based on GRAND that retains the advantage of diffusion and is capable of learning much higher depth. leverages a perturbation to the graph diffusivity - (1 + E) and a scaling factor (X) to make the model both more stable and more resilient to the over-smoothing issue.
Denote the i-th column of by X,, and the usual 2-norm by the column-wiss norm matrix (X (t)) guxd
||. For constant a > 0, we define
X,
X2 a
X X
X1 a
Xg
(X(t))==
(8)
||
||
||x2||
X
The dynamic of DeepGRAND is given by equation
3 with 0x
given by
Øt 0x (t) = (A (1 x))))))((() (x))))
(9)
4

---

Under review as a conference paper at ICLR 2023
where is the Hadamard product. Our proposed model thus represents alteration the central GRAND dynamics given by equation With such modifications, DeepGRAND no longer has the form of pure diffusion process like GRAND, while still retaining its diffusive characteristics: at every infinitesimal instance, the information from graph nodes are aggregated for use in updating feature representation.
4.2 THEORETICAL ADVANTAGES OF DEEPGRAND
To explain the theoretical motivation behind DeepGRAND, we first note that the convergence prop- crty of all nodes to a pre-determined feature vector is not necessarily an undesirable trait. guar- antees the model will remain bounded and not 'explode'. Our perturbation by serves to slightly strengthen this behaviour. Its purpose to reduce the real part of all eigenvalues to negative values, making all node representations converge to 0 as the integration limit T tends to infinity.
We observe that is in fact the rate of convergence that is the chief factor in determining the range of effective depth. If the model converges very slowly, it is clear ever having to worry about over-smoothing. As such, if we can control the convergence rate, we would be able alleviate the over-smoothing issue. The addition of the term (X (1)) Raxd serves this purpose. As the node representations come close to their limits, this term acts as scaling factor to slow down the convergent process.
train it at high depth without
An exact bound for the convergent rate of our model is presented in Proposition 3
Proposition 3. Assuming A is a right-stochastic and radial matrix. With the dynamic given in equation 9 have the bound for each column X;
((2 (2++)aT (0)l S (|,(T)) (eaT 11(0)199
(10)
The equation 10 shows that each column X; is bounded both sides by polynomial-like terms. Hence, it can no longer converge at exponential speed. The over-smoothing problem is thus alle- viated. Note also that the right hand side of equation [0 converges ensures node representation will not explode in the long run and helps with numerical stability.
T goes infinity. This
5 EMPIRICAL ANALYSIS
In this section, we conduct experiments to compare the performance of our proposed method Deep- GRAND and the baseline GRAND. We aim to point out that DeepGRAND is able achieve better accuracy when trained with higher depth and limitted number of labelled nodes per class. We also compare our results with those of GRAND++ (Thorpe et 2022) and popular GNNs architectures such GCN, GAT and GraphSage.
5.1 EXPERIMENTS
5.1.1 DATA
Cora McCallum et al. 2000 A citation network consisting of more than 2700 publications with more than 5000 connections and classes. Each node a vector Os and Is indicating the presence absence of the corresponding words in corpus of 1433 words.
Citeseer Giles et al. 1998) Similar to Cora, the Citeseer dataset is network of 3312 scientific publications with 4732 connections and each publication is classified into 6 classes. The node vectors consist of Os and is indicating the presence absence of corresponding words in a library of 3703 words.
Pubmed (Sen et al. 2008 Contains 19717 scientific publications related to diabetes from the Pubmed database separated into classes. The network consists of 44338 connections and each node vector is the TF/IDF representation from corpus of 500 unique words.
CoauthorCS (Monti et al., 2016): Co-authorship graph of authors with publications in computer science fields. The nodes of the network represent the authors and two authors are connected if they share co-publish. Each node represents each author's papers keywords and the classes represents
5

---

Under review as a conference paper at ICLR 2023
the authors' most notable research fields studies. This graph consists of 18333 nodes and 163788 edges with 15 different classes.
Computers (McAuley et al. 2015): A co-purchase graph extracted from Amazon where each node represents a product and the edges represent the co-purchased relations. The node features are bag- of-words vectors extracted from the product reviews. The dataset consists of 13752 nodes with 491722 edges. All the nodes are classified into 10 different product categories.
Photo (McAuley al., 2013): Similar to Computers, the node features in the Photo dataset repre- sents the bag-of-words vectors derived from the product review and nodes (products) are connected if frequently co-purchased. The dataset consists of 7487 nodes with 119043 edges. The nodes classified into 8 classes representing 8 product categories.
5.1.2 SETUP
Experiment setup For most of the experiments, we used the same set of hyperparameters as GRAND and only changed some settings for the ablation studies specified in sections 5.2, 5.3 and 5.4. Similar to GRAND-I, we denote the specific implimentation of DeepGRAND when is only dependent the initial node features DeepGRAND-I. The experiments are conducted on the common benchmarks for node classification tasks : Cora, Citeseer, Pubmed, Computers, Photo and CoauthorCS using our NVIDIA RTX 3090 graphies card.
One thing to note is that we have made slight adjustments to the original implementation of GRAND. Firstly, in the original work. the authors of GRAND included learnable scaling term in front of equation 4 Secondly, they also added the value of X X() scaled by a learnable scalar & to the equa- tion. The final GRAND dynamics used in the original implementation is indicated in equation 11
0x a [) 3x
(11)
Øt The initial value X() is treated as a source term added to the overall dynamics before each evalua- tion step of the ODE solver. This modification is task specific. For fair comparison of GRAND and DeepGRAND, we have removed this from the original implementation and all of our experiments.
5.1.3 EVALUATION
We aim to demonstrate the advantages of DeepGRAND by evaluating our proposed method using the following experiments:
Ablation study with different depths (5.2): For this experiment, we trained variants of GRAND and DeepGRAND using the same integration limits T across a wide range of values and compare the respective test accuracies.
For Cora, Citeseer and Pubmed We used the default planetoid splitting method avail- able for Cora, Citeseer and Pubmed. For each T value, we trained GRAND-I, GRAND-nl and DeepGRAND-I with 10 random seeds (weights initializations) per method then calcu- lated mean and standard deviation of the test accuracies across the random seeds.
For Computers, Photo and CoauthorCS We used random splitting for the 3 remaining benchmarks. For each T value, we trained all methods with 10 random seeds and calculated mean and standard deviation of the test accuracies across the random seeds.
Ablation study with different label rates (5.3) : For of the benchmarks, we used random splitting and trained GRAND-I, GRAND-nl and DeepGRANDA with different number of labelled nodes per class. For each experiment, we ran with 10 random seeds per method and calculated mean and standard deviation of the test accuracies across the seeds.
Ablation study effect of a (5.4) For this section we aimed to study the effect of the exponential on the ODE solver's ability to integrate. For each value, trained DeepGRAND-1 with 10 random seeds and calculated the mean and standard deviation of the test accuracies across the seeds.
Note For dypem-parameters tuning of DeepGRAND-I, reused most of the settings tuned for GRAND and only tuned the papereparaeetess that are specific to DeepGRAND the a and e values specified in equation g

---

Under review as a conference paper at ICLR 2023
Summary: For both experiment sets presented in Table I and Table observed that our pro- posed dynamics achieved a substantially higher test accuracies than the baseline method and is less prone to performance decay effect when trained with deep architectures (large depth T). Further- more, the results in Table 3 reveals that DeepGRANDD- also more robust when the number of labelled nodes per class is low.
5.2
DEEPGRAND IS MORE ADAPTABLE TO DEEP ARCHITECTURES
Cora
Cheseer
Pubmed
0.70
0.8
0.85
0.4
0.75
0.60
Mean/tt accuracies
DeepGRAND-1
0.33
DeepGRAND-1
0.2
DeepGRAND-1
0.50
100
Computers
Photo
CoauthorCS
0.9
0.6
0.6
0.7
0.6
0.2
DeepGRAND-1
0.4
DeepGRAND-I
0.5
DeepGRAND-1
GRAND-1
GRAND-4
0.4
GRAND-1
Deptr
Figure 1: Effect of depth T on the performance of DeepGRAND-I and GRAND-I on Cora, Citeseer, Pubmed, Computers, Photo and CoauthorCS benchmarks. For the first three benchmarks, used the default planctoid split to conduct our experiments. For the later three, we used random split.
Table 1: The means and standard deviations of test accuracies of DeepGRAND-I and variants of GRAND experimented with different depths on Cora, Citeseer and Pubmed under the default Plane- toid split. NA: ODE solver failed. (Note: The results for GRAND++11 were imported from (Thoree)
et al.
2022
Dataset
Depth (T)
GRAND-I
GRAND-nl
GRAND+++1
(oer
4
83.49 + 0.40
83.31 + 0.27
81.98 + 1.42
84.69 + 0.23
16
83.51 + 0.51
$2.53 0.35
82,49 + 1.37
84.45 = 0.29
Cora
32
81.76 0.47
81.66 0.25 0.25
82.48 + 0.71
84.26 0.44
64
76.45 = 0.63
78.70 = 1.08
80.99 = 1.76
82.13 0.67
128
68.55 0.38
74.60 0.51
80.29 1.98
76.35 0.89
4
68.45 = 1.66
69.01 1.52
72.58 = 3.79
75.39 0.59
16
40
60.65 1.78
73.84 + 2.66
74.97 0.57
Citeseer
32
60.06
58.77 1.55
73.29 + 1.29
74.42 1.06
64
55.06
55.71 + 2.28
72.81 + 2.18
71.00 + 1.08
128
50.45 2.56
52.90 = 1.80
NA
67.93 = 0.78
4
77.78 00100
77.50 = 0.34
79.20 + 0.74
79.61 = 0.98
16
77.93 + 0.36
77.76 0.15
79.49 0.84
79.52 + 0.56
Pubmed
32
76.65 + 0.26
78.41
0.37
79.81
1.61 NA
79.26 0.35
64
74.68 = 0.52
73.31 1.23
79.08 0.59
128
NA
NA
NA
78.74 0.46
We provide empirical evidence for argument that the dynamics of DeepGRAND is more silient to deeper architectures. Specifically, we compared the change in performance of both GRAND and DeepGRAND the integration limit T increases. In Table T for each T value in (4, 16, 32, 64, 128). we trained both methods for Cora, Citeseer and Pubmed datasets using the default planetoid splitting method with 10 random initializations. For the other benchmarks: Com-

---

Under review as a conference paper at ICLR 2023
Table 2: The means and standard deviations of test accuracies of DeepGRAND-] and variants of GRAND experimented with different depths on the Computers, Photo and CoauthorCS datasets under random split. NA: ODE solver failed. (Note: The results for GRAND++-1 was imported from
(Thorpe et al. 2022
Dataset
Depth (T)
GRAND-1
GRAND-nl
GRAND++-1
DeepGRAND-I (ours)
85.32 1 0.62
85.67 0.14
84.11 0.51
85.87 0.30
85.57 + 2.89
+
84.34 + 0.71
85.78 0.28
85,36 + 0.49
=
84.19 0.93
85.54 = 0.49
Computers
55.94 = 0.32
52.14
80.45 = 1.24
85.12 0.32
16
40.40 1 1.02
42.11
78.97 2.33
78.71 2.23
32
4.18 4.10
8.19
76.01 + 1.33
48.89 + 0.28
93.55 0.20
93.35
92.93 +
93.86 0.30
93.65 0.24
93.28
93.89 = 0.22
93.80 0.28
-.41
93.54 + 0.38
93.76 0.22
Photo
92.57
9
93.01 = 0.52
93.46 0.42
16
83.58 1.67
93.29
92.69 1 0.61
93.29 0.36
32
25.45 5.63
45.23 = 7.32
92.94 + 0.90
91.13 0.95
90.31 1.11
91.12 0.44
90.42 + 0.76
91.36 0.16
2
90.31 0.86
90.79 + 0.14
90.53 + 0.54
91.17 + 0.65
90.37 0.74
89.90 0.75
90.89 = 0.36
90.85 0.62
CoauthorCS
85.13 1 1.77
87.18 1 1.04
90.18 1 0.47
90.74 0.65
16
65.16 + 14.53
77.68 + 3.74
90.24 + 0.30
88.37 + 1.11
47.96 + 8.86
49.71 + 12.08
79.73 2.35
puters, Photo and CoauthorCS, we splitted the datasets randomly and trained with 10 random ini- tializations for each integration limit 7 in {1, 2, 4, 8, 16, 32} and recorded the results in Table 2 For each initialization, we used the default label rate 20 labelled nodes per class as indicated in the original GRAND implementation On all benchmarks,
observe that proposed dynamics performed substantially better for larger values of T, indicating less performance degradation under the effect of over-smoothing.
5.3 DEEPGRAND IS MORE RESILIENT UNDER LIMITED LABELLED TRAINING DATA
In previous experiments, we showed that DeepGRAND outperforms the baseline GRAND when trained with high integration limit. In the following experiments, we aim demonstrate that Deep- GRAND also achieves superior results with limited number of labelled nodes per class. For all of the benchmarks: Cora, Citeseer, Pubmed, Computers, Photo and CoauthorCS, we used grid search to find the optimal T' values and evaluate the performance under different numbers of labelled nodes per class. For each dataset, we experimented with 1, 2, 5, 10, 20 labelled nodes per class and com- pared the test accuracies between GRAND, GRAND++ and DeepGRAND-I. On top of GRAND variants, our results recorded Table also show that DeepGRAND outperforms some of the com- GNN architectures like GCN, GAT and GraphSage. More experiment results where identical values of T as those used in GRAND can be found in Appendix E Even without using optimal 7 values, DeepGRAND is still the top performing design more often than not.
used
5.4 EFFECT OF a ON THE DYNAMICS OF DEEPGRAND
The exponential a defined in our DeepGRAND dynamics directly influences the ability to integrate of the ODE solver. Specifically, high a value (from 0.5 1.5) will likely cause the ODE solver to receive the MaxNFE error (Max Number of Function Evaluations exceeded). Hence, harming the overall performance.
In the following experiment, for each exponential value in {0.0001, 0.001, 0.1,, 0.5). trained with 10 random weights initializations and increased the integration depth from to 128 to observe the behavior the test accuracies. The results in Figure 2 suggest the performance of DeepGRAND under smaller a values are quite stable. This gives us a rough idea of what range of values when perform papereparameter tuning for DeepGRAND.
8

---

Under review as a conference paper at ICLR 2023
The means and standard deviations of test accuracies of DeepGRAND-I, variants of GRAND, and other common GNNs experimented with different number of labelled nodes per class. Best results are written bold (note: The results for GRAND++-I, GCN, GAT and GraphSage were
Table 3:
imported from Thorpe et al. (0022).
labelled
GraphSage
DeepGR.NDD-
20
82.86 1 1.12
82.721245
82995 1: 1.37
82,07 1: 2,03
79.92 2.28
80.04
2.54
84.30
0.71
2.19
2.99
5.38
76.31
75.04
0.78
Com
77.09
3.05
77.68 2.85
77,80 4.46
73,86
7.97
1:.04:::50
5:74
68.14 6.95
1.08
74.23 + 5.58
60.44 4.27
66.92
10.04
60.85
14.01
58. 30-00- 13:55
53.96 + 12.18
76.49 1.97
16.09
47,72
15.35
47,96=
20
71.74 1: 2.54
73.36 3.00
13.53 3.31
74.21 2.90
73:22 = 2.90
72,02
2.82
74.07 0.75
Cheseee
69,00
3.74
66:00
4.62
70.03 + 3.63
67.24 + 4.1.9
67.37 5.0.8
64.79
5.16
71.97 1.03
58.35
8.98
56.35 5.54
64.98 1. 8.31
58.06 9.76
55.55
511399
11.37
69.74 2.97
49.65 8.67
6.66
58,95 9.59
48.94 10.24
50.31
14.27
48.81
11.45
58.35 2.51
78.42 0:46
75.19 + 1.77
79.16 + 1.37
76.89 3.27
75.55 4.11
74.55
3.09
79,50 0.64
Pubened
71.05 +: 1.87
72.07 1: 2.15
71.99 1: 1.91
68.69 1: 7.93
5.75 68.54
66.07 6.16
77.09 1.12
62.41 A: 7.59
63.47 4: 5.47
65.94 1: 4.87
12.83 58.61
58.84
12.81
55.53 4: 12.71
70.03 1.84
84,04 0.38
K3.28 +: 1.34
85.73 0.30
82.944 1.54
80.08
79.98
0.45
87.34 2.18
81.27
3.02
0.81
K2.53 0.74
76.04 0.35
74.66
1.29
1.11
Comguters
78.69 0:79
79.65 + 2.02
82.64 + 0.56
82.47 + 0.97
71.43 7.34
64.83 1.62
82.42 0.33
19,80 1 14.97
47.26 11.23
67.65 1 0.37
49.46 1 1.65
37.14 7.81
27.65 2.39
69.33 2.71
90.80 1.37
89.02 + 2.54
90.65 + 1.19
90.41 + 0.35
87.42 2.38
84.38 1.75
91.29 0.42
Photo
88.06 2.54
88.31 1: 1.63
88.33 1: 1,21
88.86 1,56
83.01
76.26
1,93
90.45 0.99
2.96
83.71 0.90
83.61
76,89
0.33
75,05 + 5.44
76.33 + 4.79
83.12 + 0.78
$2.94 2.17
73.58
45.36 7.13
83.27 1.88
79.55
10
89,00 1. 2,08
89.95 1 0.68
86,91 1 0.46
88.60 0.50
74.71 3.35
89.68 0.39
89.80 0.70
CoumtorC'S
0.84
U.4
88.24 0.68
75.19 3.84
76.66 6.85
76.53 1. 1.85
83.61 1.49
63.12
6.09
76.51 1.31
82.08 3.39
56.58 8:44
66.44 8.17
60,30 +: 1,50
65.22 2.25
51.13
5:24
61.35 :: 1.35
71.14 1.66
0.75
Reeenttd tes: accurettes
0.70
0.6
0.60
1.008-04
1.008-05 05
1.086 02
5.066 01
1.06 01
0.59
320
300
Depth (T)
Figure 2: The change in test accuracies of DeepGRAND- as depth value T increases under different values. Left effect a on the accuracies of Cora, Right effect of on the accuracies of Citeseer. Each value is trained on 10 random seeds for both benchmarks.
CONCLUSION
We propose DeepGRAND, a class of continuous -epth graph neural networks that leverage a novel data-dependent scaling term and perturbation to the graph diffusivity to decrease the saturation rate of the underlying diffusion process, thus alleviating proposed method stabilize the learning of the model by controlling the norm of the node representa- tion. We theoretically and empirically showed its advantage over GRAND and other popular GNNs in term of resiliency to over-smoothing and overall performance. DeepGRAND is first-order sys- tem of ODEs. is natural to explore an extension of DeepGRAND to a second-order system of ODEs and study the dynamics of this system. It is also interesting leverage advanced methods in improving the Neural ODEs (Chen et al. 2018) to further develop DeepGRAND.
over-smoothing issue. We also prove that the

---

Under review as a conference paper at ICLR 2023
REFERENCES
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Piere Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep leam- ing: Grids, groups, graphs, geodesics, and gauges, 2021. URL httpp:://aaxi..org////a/a//////e 2104. 13478
Chen Cai and Yusu Wang- A note on over-smoothing for graph neural networks, 2020. URL fictps://erxxr wttpariwv..rggaaaaeeee wbwpgg//bb///...//////// 13318
Benjamin Paul Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael M. Bronstein. Beltrami flow and neural diffusion on graphs. In A. Beygelz- imer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Pro- cessing Systems, 2021a. URL http:pp::///peeee.e......ttttt wttp:///www..eeee/oteteee.e.. 2ataad-41122hxxxx..
Benjamin Paul Chamberlain, James Rowbottom, Maria Gorinova, Stefan Webb, Emanuele Rossi, and Michael M. Bronstein. GRAND: Graph neural diffusion. In The Symbiosis of Deep Learning and Differential Equations, 2021b. URL https://openreview net/ forum? id= lfllluucppp cjsaR
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 Artificial Intelligence, volume 34, pp. 3438-3445, 2020.
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud, Neural ordinary dif- ferential equations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018 URL http:tttpss/pppcccii....... nwwrpps.......ppp............... http://ccei.....eeriiscc.//ppppd
Papee pdf
Yongqiang Chen, Han Yang, Yonggang Zhang, MA KAILI, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability, In International Conference on Learning Representations 2022. URL PpLlhtttpp::/peerevviee
peet/Eorum:3 www.eiidwwwwdM@cc...
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16. pp. 3854-3852, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
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 (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL htt.a//ee224111.eeeeeeeeeeee pdf 21be9a4bd4 2dt.:ea444..11544111121222444442
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Gure and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Moshe Eliasof, Eldad Haber, and Eran Treister. PDE-GCN: Novel architectures for graph neural networks motivated by partial differential equations. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), ), Advances Neural Information Processing Systems, 2021. URL https://openrev net wtt.:/oommmmmitkkkkkem
10

---

Under review as a conference paper at ICLR 2023
Chris Finlay, Jörn förn-Henrik Jacobsen, Levon Nurbekyan, and Adam M. Oberman. How to train your neural ode: the world of jacobian and kinetic regularization. ICML, pp. 3154 3164, 2020. URL URRphttp://ppcceeiiimm
m /ttp:///........eeee/////////aaa
html
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Conference Neural Information Processing Systems (NeurIPS), 2019.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. CiteSeer. In Proceedings of the third ACM conference on Digital libraries DL '98. ACM Press, 1998. doi: 10. 10.1145/76665.2276665 URL
https://daa wrg.orrgg/...oo...oo 0111//00.11141715511111 276665555577
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http: 7/www. deepleazningbook. org
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Thomas N. Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Net- works. In Proceedings of the 5th International Conference on Learning Representations, ICLR "17 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning, 2018. URL otgp:/uwww..iettteeooooooaaaaaaa
07606
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https:://proceedigg...o wttpe/wips...pppppeeeeeepepe cctpppper/219//Eiie/ 01230305667311117701133330
Paper. pdf
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc. E. Fox, and Garnett (eds.), Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Is heterophily real nightmare for graph neural networks on performing node classification?, 2022. URL
LBv-JtAnm4P
Yao Ma. Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference Learning Representations, 2022. URL https:
//openzeview. wttp://weee//ootre///e//a httt///oounnPduucAAPEEEE.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based rec-
ommendations on styles and substitutes, 2015. URL /tttp:://axxiv.org//bbbb
04757
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Informationn Re- Irieval, 3(2) 2000. doi: 10.1023/a:10099555 1190999933998..... 01033//:109953814333
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns, 2016. URL htt.httts://ee wtt./oor//////o.///o
08402

---

Under review as a conference paper at ICLR 2023
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with current multi-graph neural networks. Advances in neural information processing systems, 30, 2017.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference Learning Representations, 2020. URL https:
//openreview. hwtp://nn//oormmmmmmmmmmm htt:://rrmdddd1111121
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 on knowledge discovery & data mining, pp. 2110-2119, 2018.
Konstantin Rusch, Benjamin Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M. Bronstein. Graph-coupled oscillator networks, 2022. URL https://arxiv.
hogg/bb/2202/ 02296
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-83) 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93, September 2008, doi: 10. wttp:/aamaa..29..215555 URL htt.s::::: //w http:///oooorgg//.///// 609/ mmgg. 02..3...... 2157
Matthew Thorpe, Tan Minh Nguyen, Hedi Xia, Thomas Strohmer, Andrea Bertozzi, Stanley Osher, and Bao Wang. GRAND++: Graph neural diffusion with source term. In International Confer- ence on Learning Representations, 2022. URL https::////.... /tttps://opezzeview. net www.eeee/oooommoooom
EMxu-dzvJk
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- tional Conference on Learning Representations, 2022. URL
net/
Forum? 3orum?1d==7mm332222
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. /RR/ittpp://openeeelee wttp:e/ee//rrruttdddoooppppppp.
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks, In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learn- ing, volume 119 of Proceedings of Machine Learning Research, pp. 10432-10441, PMLR, 13-18 html
Jul 2020. URL StKLLttts///ppcceed.ie marpgssmllr.... wtt.ggsssmr..p.r.e..e press /ttp//l119///// wwwonewxooa...cc.. https///w111////ouuuuuaaaaaaaaa
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, P. Liang, and J. Wortman Vaughan (eds.), ), Advances in Neural Information Processing Systems, 2021. URL https://cpenreviiee
net feet/forume worumordddooooo Sezuumiid=YLLLsyyttt
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. CoRR, abs/2102.06462, 2021. URL
http:///ww.....//////////.... 05462
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974 983. 2018
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
Lingxiao Zhao and Leman Akoglu. Pairnorm Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020. URL httptttppp//pepeeeeee...... hwtp//pppnreee.oeeeeeoe net/ forum?
id=rkec] 1
12

---

Under review as a conference paper at ICLR 2023
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily graph neural networks: Current limitations and effective designs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7793-7804. Curran Asso- ciates, Inc., 2020. URL /ttppsss//pprrrceedingg. neuriss wtteerips..cppppppe///eeeeeeeeee ppspccc/ppperr/2222/11ll 58ae23d878a 03022228000010011311188842888100 Pap.000-ppppppppp.. pdf
13

---

we can Under review as a conference paper at ICLR 2023
Appendix for "DeepGRAND: Deeper Graph Neural Diffusion"
A TECHNICAL PROOFS
Consider the dynamic given by equation 3 and equation 4 We say that matrix is postitive if and only if all of entries are positive. Clearly, is a postive right-stochastic matrix. We recall the
well-known Perron-Firobenius theorem
Theorem 1 (Perron Frobeniis........ Let M be a positive matrix. There is a positive real number r, called the Perron-Frobenide Frobenius eigenvalue, such that r is an eigenvalue of M and any other eigenvalue (possibly complex) absolute value is strictly smaller than v, [2] v. This eigenvalue is simple and its eigenspace is meedimensional.
Proof of Proposition 1 Since A right-stochase its Perron-Frobenius eigenvalue is aj = Its Suppose (a1, 02,, ,0k is the complex spectrum of A. That is, they are all complex eigenvalues of A. The matrix A has eigenvalues 3 02 for all = k, so 31 = and Re 3 < 0 for all é = k. There exists a basis containing 41 of C comprising of generalized eigenvectors of A. By rearranging the vectors if needed, the transition matrix P from the standard basis to this basis satisfies
eigenspace has the basis u, {1, 1, ...... 1}.
0
0
J
(A
J Jm
where each J; is Jordan block associated with some eigenvalue 3i.
Proof of Proposition
2 Let
= P-1PPr and Z(t) = P- P-1X(t) as Proposition
rewrite equation
4 as
az
(t) = (Z()),
Øt
The solution to this matrix differential equation
Z(t) exp(tJ)
where
exp(tJi)
exp(tJ)=
exp((J2)
ctp()
Let Z be the matrix with the same size as Z(0) obtained by setting every entry in all but the first row of Z Z0) be equal to O. We have
0
0
exp(t.J1)
0
0 0
z(1-Z Z(1)-
Z
exp(tJ2)
Z
exp(t.J.m.)
14

---

Under review as a conference paper at ICLR 2023
Denote the size of each Jordan block J, as n4, have well-known equality
t
2
(R- I]]
1
exp(lJi) = Aie
t
Hence, every non-zero entry of (t) - Z has the form e Ptt) for some 3; < 0 and polynomial P. Each entry can thus be bounded above in norm by exponential term of the form cie for some C1,02 > O. A simple calculation shows that || (t) P 80 || (Z) Z) would also be bounded by an exponential term. That is, there exists some Ci, C2 > 0 such that
(t) PZ 20 S C2e C2t
(12)
Recall that the first column of P is u (1, 1,.1,........ ,,,,,,,,))) 1)T, so that
1
2(0)122
z(0)
2(0),11 2(0)
1(0)
PZ
Z(0)11
z(0)
Let = (()
a() and V = (v, U, v).
v)
We can rewrite equation 12
(t) Vl S Cie C2t
(13)
The claim that v E Rd follows from the fact that it is the limit of real-valued vectors with regards to the || oo norm.
Proof of Proposition
Let (it)) = (1)) we have
((( (X)
(1XX0))))(( X,00))
x (1), 40)))((0)))+++))))(
Since A is right-stochastic and radial matrix, have
(Ax,(t), x.())) & AIIII = 11X,
and
(AX,(()) X. & ||II 1|,,0)1 (1)X < (AX, x,()) $ 11,01
so that
Hence, we deduce that
4 X (t)l 1+a (-2 6) b) S (1()) < (100
(14)
Multiply both sides of equation 14 with - ((I (t) 4 -ta and by noting that
-YYY -1-411 (Y; a/4y, we have
(2++)) 2 (Y; a/4y > ae.
Integrate from to and rearranging the appropriate terms, we get
(2 + e)aT + (:(0) > (TT) 2 EaT + Y.(0) o/4
Finally, by noting that Y, -a
| -a casily get the bound equation 10
(22 + ()o + |X,(0) S x S (caT + (1x((0))
15

---

Under review as a conference paper at ICLR 2023
B PHYSICAL INTERPRETATION OF GRAND
Informally, diffusion describes the process by which diffusing material transported from a region of higher to lower density through random microscopic motions. A natural example is the process of heat diffusion, which occurs when a hot object touches a cold object. Heat will diffuse between them until both objects are of the same temperature.
GRAND approaches deep learning on graphs as a continuous diffusion process and treat GNNs as discretisations of an underlying PDE. In doing so, the dynamic in GRAND is the same that in (heat) diffusion problems. We use this viewpoint to consider the over-smoothing issue.
Consider each node in given graph point in space containing some amount of thermal energy. Each pair of points is connected through a heat pipe. The thermal conductivity (also known as the diffusivity) of each pipe is specific each pair of points. A thermal conductivity of represents two points that are not connected in the graph. The exact formulation of graph diffusion up to equation represents a closed system. That is, the total amount of energy in all nodes is invariant of time.
In node classification problems, nodes within the same class are often hypothesized as sharing strong connection with each other. This is known as the homophily assumption, i.c. 'like attracts like'. For example, friends are more likely to share an interest, and papers from the same research area tends to cite each other. Homophily key principle of many world networks, and its effect on GNNs
has gained traction research direction (Zhu et al. 2020 Yan et al. [202 Chen et al. 2022 al. 2022 Ma al. 2022).
Luan
In the context of GRAND, can assume nodes within the same class as sharing highly conductive heat pipe. As such, thermal energy is transferred effectively between them, quickly bridging any gap in temperature. This allows for rapid clustering of nodes into classes of different thermal energy levels, which can then be passed into fully connected layer to perform classification.
This interpretation gives surprising intuitive explanation to the occurrence of the over-smoothing issue in GRAND. If the dynamic carries on for too long, the energy level of every node will exponen- tially converge the average thermal energy, given that the graph is sufficiently connected. Hence, we argue that GRAND (and more generally, any GNN based purely on diffusion) inherently prone suffer from over-smoothing.
C ON NEURAL ODES
Traditional neural networks such as residual neural networks, normalizing flows, eecurent-nnurrle networks (RNNs) learn complicated mappings via the composition of multiple transformations the hidden states. For example, the residual network updates the future hidden state using the following equation:
h:+1 h; + f(1e,, t,
(15)
Where E (1....,77 T} is the layer index of the neural network and h, is the hidden state at layer I. This iterative update rule can be seen as the Euler discretisation continuous transformation.
Neural ODEs (Chen et al. 2018) are class of continuous-depth (or continuous- (atinuous-timm) neural net- works where the transformation step infinitesimally small. Specifically, the hidden state h; is parameterized using a continuous dynamics with respect to time t:
dh. dt fh,,t,,
(16)
Where f(hr, L. 0) is specified by neural network parameterized by 0. Starting from the initial state h()), Neural ODEs learn the final representation h(T) by solving 16 uuing numerical integrator (often with adaptive step-size solver or an adaptive solver for short) given Integrating 16 0 to T a single forward pass requires the adaptive solver to evaluate f(h,, t, 0) multiple time-steps. The computational complexity of the forward pass is determined by the number function evaluations.
tolerance.
The only problem with updating the hidden state by solving 16 numerically is that the black-box ODE solver is not a differentiable operation. Therefore, the usual back-propagen method for optimizing traditional neural networks does work for Neural ODEs.
16

---

Under review as a conference paper at ICLR 2023
The adjoint sensitivity method (or adjoint method) is memory-eeffcient alternative of the traditional back-pne pock-propggttion method for training Neural ODEs. We denote h(T) as the prediction of Neural ODEs and the loss between (TT) and the ground truth is L. Then, we define the adjoint state as a(t) = ac/Oh(t), we have:
= dC
dB = -f" a(t) (f(h(t),t,))
(17)
00
Where the adjoint state (t)) satisfies the following dynamics:
da(t) al1) o (f(h(t),t, t. dt
(18)
Oh(t)
Since the adjoint state in c8 solved numerically using an ODE solver, the gradient of the loss function C with respect in [7 can be evaluated. The computational complexity of the backward pass is determined by the number of function evaluations used by the ODE solver to solve for the adjoint state.
D EULER DISCRETIZATTOON GRAND ALSS SUFFERS FROM WVER-MOOTTHING
Recall that the forward Euler discretization of the GRAND dynamic was given by (Thorpe et al. 2022) as
((k,)) x x ( 1)6+)= + 6,(A - ()k - 1)6,),
(19)
where > 61 > O is the fixed step size, k = 1.2..... K denotes the layers from 1 to K and X₃ X (k0{) is the node feature at the k-th layer.
We mirror our analysis as in Section 3 almost completely. Some calculations will be omitted for clarity. First, we give an analogous delinitio to for discrete GNNs.
Definition 2. Let Xx E Raxd denote the feature representation at the k-th layer of some discrete GNN dynamic. (X&) said experience over-smoothing there exists a vector e IRd and
constants Cj C2 > such that for V = (V, v. U)
|x V Cie-
(20)
we can show that Utilising Proposition] D
Proposition With the dynamic given by equation and equation 19
(Xx)
experiences over-
smoothing.
Proof. Let p-1 AP and Z p- Xx as in Proposition we can rewrite equation 19 as
Z = 3,=Z,-1 + 6.(J 1) Z ((1 8, 8.J) Z ((1 6,) 8,J)* * Zo
(21)
where
('
((1- (11-8,) 8,)1 8.J1)
((1 (1--8) (1- (1,6))+66,)+++
((1 8 J)
Let Z be the matrix with the same size as Zo obtained by setting every entry in all but the first row of Zo be equal We have
0
((1 8.)1 +.,J)*
Z₁ -
Zo.
((1 5,) + 8 J)
17

---

Under review as a conference paper at ICLR 2023
Each block (1- has spectral radius lesser than 1. Hence, every non-zero entry of Z Z can be bounded above in norm by an exponential term of the form eie nat for some c1, C2 > 0. We can deduce that there exists some C₁, C2 > 0 such that
|X PZ 0 S Cie Csk
(22)
Recall that the first column of P is u. rewrite equation 22
= (I,1,...,,)) Set v to be the first row of Zo. We can
| V S Cie
The claim that Fd follows from the fact that it is the limit of real-valued vectors with regards to the || co norm.
E DEEPGRAND PERFORMANCE ON DIFFERENT NUMBERS OF LABELLED NODES PER CLASS
In this section, we provide additional experiment results to complement Table 3 Apart from the test accuracies of DeepGRAND ran on optimal T values, we add an additional column showing used in the GRAND paper CChmmeerlain et al.] (202Tb)). The experiments suggest that with the same T values, DeepGRAND already outperforms GRAND on most of the benchmarks with limited number of labeled nodes. We observe that with optimal T values, DeepGRAND has much less test accuracy variances compared all other designs.
DeepGRAND's results when trained with identical T values
Table The means and standard deviations of test accuracies of DeepGRAND-I and other variants of GRAND experimented with different number of labelled nodes per class. Best results are written in bold (Note: The results for GRAND+++1 were imported from Thorpe et al. 2022
Dataset
# Habblled
GRAND-1
GRAND-Bl
GRAND++-1
DeepGRAND4 (GREANADD+GGAAND setting)
DeepGRAND4 (optimal T)
N2.22:2.5
$387
84,20
10
80.67 + 2.19
80.51 + 1.11
80.86 + 2.99
82.47 + 1.11
82.88
0.78
Cora
77.09 +: 3.05
77.68 2.85
77,80
4:46
79.00 1: 1.87
80.85 1.08
74.23 a: 5.58
69.44 4.27
66.92 : 10.04
67.57 1 8.02
76,49 1.97
$7.934: 8.09
55.86 1: 10.04
54.94 :: 16.09
63.79 1: 7.14
70.15 3.25
2.94
73.53 3.31
73.64 1.73
10
66.26 1: 4.19
67,84 1: 3.96
72.34 2.42
72.87 1: 2:29
73.45 0.84
66.90
70.84 3.04
58 8.98
56.35 5.54
64.98 + 8.31
63.26 + 3.89
69.74 2.97
49 + 8.67
47,32 6.66
58.95
$3.06 1: 8.49
58.5 35 :: 2.51
78.42 0.46
75.19
1.77
79,16 1.37
79.23 1: 1.23
79.50 0.64
74.10 +: 1.88
78
1.99
75. 3.88
76.95 4: 3.24
78.93 1.48
Pubmed
71.05 1.87
72.07
2.1.5
73.37 2.26
77.00
71 +: 3.85
65.50 9.49
69.31 2: 4.87
70.75 4: 3.86
72.32 1.82
7.59
84.04 = 0,98
83.28 1.24
85.73 4: 0.50
87.27 +: 1.45
87.12 0.45
82.34 :: 2.18
81.27
1: 3.02
82.99
83.79 1: 1.45
85.73 1.11
Computers
78.69 1: 0.79
79.65
2.02
82.64
0.56
$2.06 1. 2.02
82.42 0.33
66.21
11.26
65.11
8.31
76.17 1.48
75.26 1: 2.20
76.57 1.44
49,80
14.97
11.23 47,26
67.65 4 0.37
65.35 1. 6.65
69.33 2.71
20
93 =: 0.44
91.76 1,51
93.55 1 0.38
93.52 1: 0.41
93.16 0.66
2:27
Photo
88.06 +: 2.59
$8.31
1.63
88.33 + 1.21
87.75 4: 1.59
90.45 0.99
82 2.96
80:61 4.43
84.59 +
75.05 = 5,44
76.33
4.79
83,12 2: 0.78
73,50 1: 5.06
83.27 1.88
90.99 1: 0.56
90.59 0.97
90.80 1: 0.34
91.53 1: 0.33
91.66 0.59
89.00 2.08
89.95 0.68
86.94 0.46
89.39 4: 0.89
80 0.70
CoautherSS
84. 3.59
87.01
1.97
84.33 01.84
86.05 + 4.64
28.24 0.68
75. 3.84
76.66
3.89
3.39
56.58 1: 8.44
66.44 1: 8.17
60.30 1: 1,50
65.15 1: 6.34
71.14 1: 1.66
Table 5: T values of DeepGRAND used for different benchmarks.
Cora
Citeseer
Pubmed
CoauthorCS
Computers
Photo
DeepGRAND (GRAND setting)
18.29
7.87
12.94
3.12
3.24
3.58
DeepGRAND (optimal T)
20.29
9.87
14.94
6.58
6.25
8.58
18


Reviews:
[{"review_id": "KCn2wwZktg", "reviewer": "Reviewer_spFT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "It is somehow incremental work based on GRAND. An objective of diffusion is quite simple, whether continuous or discrete. This paper states that it can alleviate over-smoothing, but there is not enough evidence to show the alleviating.", "summary_of_the_review": "It is somehow incremental work based on GRAND. ", "strength_and_weaknesses": "### Strength \n- This paper gives an excellent theoretical analysis\n- The language is relatively standard\n- The experimental results are relatively high\n\n### Weaknesses\n- The method is not original enough.\n- They didn't fully explain the difference with Grand", "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": "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": "Jq_LNsq_bpb", "reviewer": "Reviewer_3KbW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose the Deep Graph Neural Diffusion method, which ensures the over-smoothing issue and guarantees stability of the model in theoretical. The experimental results also show the improvement of the proposed method compared with the baseline methods. ", "summary_of_the_review": "This paper provides convincible theoretical analysis on the diffusion process, the over-smoothing, and the bound of the feature. However, the reviewer still has some concerns, listed below.\n1.\tLack of the explanation about the importance and the necessity to design deep GNN models . In this paper, the author tries to address the issue of over-smoothing and build deeper GNN models. However, there is no explanation about why should we build a deep GNN model. For CNN, it could be built for thousands of layers with significant improvement of the performance. While for GNN, the performance decreases with the increase of the depth (shown in Figure 1). Since the deeper GNN model does not show the significant improvement and consumes more computational resource, the reviewer wonders the explanation of the importance and the necessity to design deep models.\n2.\tThe experimental results are not significantly improved compared with GRAND. For example, GRAND++-l on Cora with T=128 in Table 1, on Computers with T=16,32 in Table 2. Since the author claims that GRAND suffers from the over-smoothing issue while DeepGRAND significantly mitigates such issue, how to explain the differences between the theoretical and practical results, why GRAND performs better when T is larger? Besides, in Table 3, DeepGRAND could not achieve the best performance with 1/2 labeled on Citeseer, Pubmed, Computers and CoauthorCS dataset, which could not support the argument that DeepGRAND is more resilient under limited labeled training data.\n3.\tInsufficient ablation study on \\alpha. \\alpha is only set to 1e-4, 1e-1, 5e-1 in section 5.4 with a large gap between 1e-4 and 1e-1. The author is recommended to provide more values of \\alpha, at least 1e-2 and 1e-3, etc.\n4.\tMinor issue. The x label of Figure 2, Depth (T) rather than Time (T).", "strength_and_weaknesses": "Strength:\n1.\tConvincible theoretical analysis on the diffusion process, the over-smoothing, and the bound of the feature.\n2.\tFully designed experiments show the performance of the proposed method systematically.\n3.\tWell organized paper and logical writing. \n\nWeaknesses:\n1.\tLack of the explanation about the importance and the necessity to design deep GNN models . In this paper, the author tries to address the issue of over-smoothing and build deeper GNN models. However, there is no explanation about why should we build a deep GNN model. For CNN, it could be built for thousands of layers with significant improvement of the performance. While for GNN, the performance decreases with the increase of the depth (shown in Figure 1). Since the deeper GNN model does not show the significant improvement and consumes more computational resource, the reviewer wonders the explanation of the importance and the necessity to design deep models.\n2.\tThe experimental results are not significantly improved compared with GRAND. For example, GRAND++-l on Cora with T=128 in Table 1, on Computers with T=16,32 in Table 2. Since the author claims that GRAND suffers from the over-smoothing issue while DeepGRAND significantly mitigates such issue, how to explain the differences between the theoretical and practical results, why GRAND performs better when T is larger? Besides, in Table 3, DeepGRAND could not achieve the best performance with 1/2 labeled on Citeseer, Pubmed, Computers and CoauthorCS dataset, which could not support the argument that DeepGRAND is more resilient under limited labeled training data.\n3.\tInsufficient ablation study on \\alpha. \\alpha is only set to 1e-4, 1e-1, 5e-1 in section 5.4 with a large gap between 1e-4 and 1e-1. The author is recommended to provide more values of \\alpha, at least 1e-2 and 1e-3.\n4.\tMinor issues. The x label of Figure 2, Depth (T) rather than Time (T).\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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "84RFXpEKj-", "reviewer": "Reviewer_UGaV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "In this paper, a continuous depth map neural network based on the diffusion process on the graph, DeepGRAND neural network, is proposed. It makes use of the scale term dependent on data and the disturbance to the diffusion rate of the graph, so that the real part of all the eigenvalues of the diffusion rate Marcus becomes negative, thereby alleviating the problem of over smoothing and ensuring the stability of the model. This paper empirically proves that DeepGRAND is superior to many existing graph neural networks in various graph depth learning benchmark tasks.", "summary_of_the_review": "My research field is not related to this manuscript and I am not very familiar with the research content.", "strength_and_weaknesses": "In this paper, a continuous depth map neural network based on the diffusion process on the graph。", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject