From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyond
Authors: Andi Han
Dai Shi
Lequan Lin
Junbin Gao
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) have demonstrated significant promise in modelling relational data and have been widely applied in various fields of interest. The key mechanism behind GNNs is the so-called message passing where information is being iteratively aggregated to central nodes from their neighbourhood. Such a scheme has been found to be intrinsically linked to a physical process known as heat diffusion, where the propagation of GNNs naturally corresponds to the evolution of heat density. Analogizing the process of message passing to the heat dynamics allows to fundamentally understand the power and pitfalls of GNNs and consequently informs better model design. Recently, there emerges a plethora of works that proposes GNNs inspired from the continuous dynamics formulation, in an attempt to mitigate the known limitations of GNNs, such as oversmoothing and oversquashing. In this survey, we provide the first systematic and comprehensive review of studies that leverage the continuous perspective of GNNs. To this end, we introduce foundational ingredients for adapting continuous dynamics to GNNs, along with a general framework for the design of graph neural dynamics. We then review and categorize existing works based on their driven mechanisms and underlying dynamics. We also summarize how the limitations of classic GNNs can be addressed under the continuous framework. We conclude by identifying multiple open research directions.

Published in Transactions on Machine Learning Research (02/2024)
From Continuous Dynamics to Graph Neural Networks: Neural Diffusion and Beyond
Andi Han University of Sydney
andi. @sydney. Mannnnenyeeedd.oo edu.
Dai Shi
dai.shi@lsydneey.c eduu
University of Sydney
Lequan Lin University of Sydney
lequan. lin @sydneyy.deeee edu.
Junbin Gao University of Sydney
junbin. gao @sydney. edu.eu on
Reviewed on OpenReview: https: // openreview. net/ forum? id- fPQSzjga2
Abstract
Graph neural networks (GNNs) have demonstrated significant promise in modelling relational data and have been widely applied various fields of interest. The key mechanism behind GNNs is the so-called message passing where information is being iteratively aggregated to central nodes from their neighbourhood. Such scheme has been found to be intrinsically linked to a physical process known heat diff'usion, where the propagation of GNNs naturally corresponds to the evolution of heat density. Analogizing the process of message passing to the heat dynamics allows to fundamentally understand the power and pitfalls of GNNs and consequently informs better model design. Recently, there emerges plethora of works that proposes GNNs inspired from the continuous dynamics formulation, in an attempt to mitigate the known limitations of GNNs, such oversmoothing and oversquashing, In this survey, we provide the first comprehensive review of studies that leverage the continuous perspective of GNNs. To this end, introduce foundational ingredients for adapting continuous dynamics to GNNs, along with a general framework for the design of graph neural dynamics. We then review and categorize existing works based on their driven mechanisms and underlying dynamics. We also summarize how the limitations of classic GNNs can be addressed under the continuous framework. We conclude by identifying multiple open research directions.
1 Introduction
Graph neural networks (GNNs) Kipf & Welling 2017 Veličković et al.] 2018 Gilmer et al. 2017) have emerged as one of the most popular choices for processing and analyzing relational data. The main goal of GNNs to acquire expressive representations at node, edge or graph level, primarily for tasks including but not limited to node classification, link prediction and graph property prediction. Such a learning process requires not only utilizing the node features but also the underlying graph topology. GNNs have been successful in various fields of application where relational structures are critical for learning quality, including recommendation systems [Fan et al. 2019), transportation networks (Jiang & Luo 2022), particle system SShooi el al. 2020), molecule and protein designs (Hoogeboom et al. 2022 Watson el. al. 2023), neuroscience
Bessadok et al. 2022) and material science Xie Grossman 2018 among many others.
The effectiveness of GNNs primarily roots the message passing paradigm, in which information is iteratively aggregated among the neighbouring nodes to update representation of the center node. One prominent.

---

Published in Transactions on Machine Learning Research (02/2024)
example is the graph convolution network (GCN) Kipf & Welling 2017 where each layer updates node representation by laking a degree- average of its neighbours" representation. Although being effective in capturing dependencies among the nodes, the number of layers of message passing requires to be carefully chosen so as to avoid performance degradation. This is unlike the classic (foedforward) neural networks where increasing depth generally leads to improved predictive performance. In particular, due to the nature of message passing, deeper GNNs have a tendency to over-smooth the features, lcading to un-informative node representations (Rusch al. 2023a). On the other hand, shallow GNNs are likely suffer from information bottleneck where signals from distant nodes (with regards to graph topology) exert little influence the centered node (Topping et al. 2022: Di Giovanni et al. 2023)
In order to analyze and address the aforementioned issues, many recent works have cast GNNs as discretization of certain contimuuus dynamical systems, by analogizing propagation through the layers to time evolution of dynamics. Indeed, the idea of viewing neural networks in the continuous limits is not new and has been
explored for classic noural networks (E) 2017 Haber & Ruthotto 2017 Liu & Thoodorou, 2019 Li ct al.) 2022 Ruthotto & Haber 2020). The continuous formulation provides unified framework for understanding and designing the propagation of neural networks, leveraging various mathematical tools from control theory and differential equations. One seminal work (Chen et al. 2018) proposes neural ordinary differential equation (Neural ODE), which can be viewed as a contimtous-depte depth residual network (He et al. 2016). Another work explores the connections between the convolutional networks with partial differential equations (PDEs)
[Ruthotto & Haber 2020
In GNNs, in particular, the message passing mechanism can be viewed as realization of class of PDEs, namely the heat diffusion equation (Chamberlain al. 2021a). Such a novel perspective allows to better dissect the behaviours of GNNs. As an example, because heat diffusion is known to dissipate energy and converge to a steady state of heat equilibrium, the phenomenon of oversmoothing corresponds to the equilibrium state of diffusion where heat distributes uniformly across spatial locations. Apart from offering theoretical insights into the evolution of GNNs, the continuons dynamics perspective also allows casy integration of structural raints and desired properties into the dynamical system, such as energy conservation, riversiiii, and boundary conditions. Meanwhile advanced numerical integrators, like high-order and implicit schemes, can be employed to enhance the efficiency and stability of discretization (Butcher] 2016). Finally, the variety of continuous dynamics grounded with physical substance inform better designs of GNNs to enhance the
representation power and overcome the performance limitations (Chamberlain et al.
2021a
Thorpe et al.
2022
Eliasof et al. 2021 Rusch et al.] 2022 Maskey et al. 2023 Zhao et al. 2023b Choi et al.
2023 Eliasof
ct al.
2023 Gruber et al. 2023 Kang et al. 2023
The theory of ial equations and dynamical systems is well-developed with a long-standing history /Verhulst 2006 Perko| 2013), while graph neural network is a comparatively nascent field, garnering attention within the past decade. This offers great potential in harnessing the rich foundations of the dynamical system theory for enhancing the understanding and functionality of GNNs. In this work, provide comprehensive review of existing developments in continuous dynamics inspired GNNs, which we collectively refer to as graph neural dynamics. To the best of our knowledge, this is the first survey on the connections between continuous dynamical systems and graph neural networks. Nevertheless, we would like to highlight a related line of research that utilizes deep learning to solve differential equations (Huang et al.] 2022 Gupta et al., Kumar & Yadav 2023 Kovachki et al.] 2023). In particular, graph neural operators (Anandkumar
2023
el al. 2020 Li et al., 2020) employ GNNs to solve PDEs by discretizing the domains and constructing graph
structure based spatial proximity. In contrast, the idealization that we focus in this work is the reverse where PDEs inform the designs of graph neural networks.
Organization. We organize the rest of the paper as follows. In Section 2 we introduce diffusion equations from first principles and then review discrete operators on graphs such as gradient and divergence, which are crucial for formulations of continuous GNNs. This section concludes with the connection between diffusion equation with the famous graph convolutional network. Section 3 then presents the framework for designing GNNs from continuous dynamics and summarizes the existing works based on the underlying physical processcs. In Section we explain how the various dynamics help to tackle the shortcomings of existing GNNs, in terms of oversmoothing, oversquashing, poor performance heterophilic graphs (where
2

---

Published in Transactions on Machine Learning Research (02/2024)
neighbouring nodes do not share similar information), as well adversarial robustness and training stability. We then in Section 5 discuss the various numerical schemes for propagating and learning the continuous GNN dynamics. In Section G we summarize and compare the computational complexities of the dynamics discussed in this work and section 7 discusses empirical benchmarks for evaluating graph neural dynamics. We then conclude the survey by outlining several open research questions and challenges in Section
2 From diffusion equations to graph neural networks
A fundamental building block of graph neural networks is message passing where information flows between neighbouring nodes. Message passing has natural connection to diffusion equations, which describe how certain quantitics of interest, such as mass or heat disperse spatially, as a function of time.
Diffusion equation in continuous domains. The two laws governing any diffusion equation are Fick's 's low and mass conservation law. The former states the diffusion happens from the regions of higher concentration to regions of lower concentration and the rate of diffusion is proportional to the mass difference (the gradient). The latter states the mass cannot be created nor destroyed through the process of diffusion. Formally, let V: Q x R - RR represent the mass distribution, i.e., s(u, 1) over the spatial locations u E Ω and time / E R. 8e
Denote Væ == du as the gradient of mass across the space. Fick's law states that a flux J (quantifying the direction and magnitude of mass movement) points towards lower mass concentrated regions, i.c., DDVr, where D is the diffusivity coefficient that potentially depends on both space and time. When C Fd we can Oz dz and D E Raxd and J corresponds to flux in d directions. The mass conservation write Vx lay: :ua law then leads to the following continuity equation de = div.J where div is the divergence operator that computes the mass changes at certain location and time. Combining the two equations yields the fundamental (heat) diffusion equation
dr = div(DVz).
(1)
at
The diffusion process is called homogeneous when the diffusivity coefficient. D is space independent, and is called isotropic when D depends only on the location, and called anisotropic when D depends on both the location and the direction of the gradient. In the case homogeneous diffusson, we can write the diffusion equation in terms of the Laplacian operator A = div V, ie., Be
Di DÅW.
Graphs and discrete differential operators. In order to properly characterize diffusion dynamics over graphs, it is necessary to generalize the concepts from differential geometry to the discrete space, such gradient and divergence.
A graph can be represented by a tuple g = EV,E) where V, E denote the set of nodes and odges respectively. In this work, we focus on the undirected graphs, i..., if (i, E E, then (j.t) E E. Leveraging tools from differential geometry, let T.2(V) and (E) be Hilbert spaces for real-valued functions on V and & respectively with the inner product given by
(fg) = Σ fig. NEV
(F,G) = En
(1,)EE
for f.g:V. V- + IR and F R. This allows to generalize the definitions of gradient and divergence to graph domains (Bronstein et al., 2017p. Formally, graph gradient is defined as V (2))) + L²(() such that (V = /4 ft. Here we assume the edges are anti-symmetric, namely (V.)iz - (VV( Graph divergence div (2(E) - L2()), is defined as the converse of graph gradient such that (divF), = Enisee Fij.
By the discrete nature, graphs and functions/signals on a graph can be compactly represented via vectors and matrices. In a graph with n nodes (|VI = n), each f E L²(V) can be written as n-dimensional vector f and F E (E) can be written as a matrix F of size n x n (with nonzero i, j- entry F,,, only when (i, E E) An adjacency matrix is E {0, 1)mxm such that As,j = 1 if (i, E and 0 otherwise. The degree matrix is diagonal degree matrix with i-th diagonal entry D deg, = E, Aij- Graph Laplacian is then defined
3

---

Published in Transactions on Machine Learning Research (02/2024)
Table 1: List of commonly used notations
Notations
Explanations
G (V)
Graph 9 with node set V and edge set &
12(V), (E)
Hilbert space for functions on V.E
X KENE
Node signal matrix
A, E RNXN
Graph adjacency, normalized adjacency matrix
L E RNXN
Normalized Laplacian matrix
( E RNN
Graph atlention matrix computed on X
deg,
Degree of node
div, V
Divergence and gradient operator
Edit
Dirichlet energy.
X 8'x OF
First-order and second-order time derivative of node signal
X
clementwise product/ elementwise product (broadcast across channels)/ tensor product
as L = D and one can verify
div(Vf)= = - (1))))= -f.
HUJEEE
Further, graph gradient can be represented with the incidence matrix G E Rex", Specifically Gk. 1 if edge k enters node i, -1 if edge k leaves node and 0 otherwise. Graph divergence is thus given by -G which is the negative adjoint of the gradient. The edge direction in G can be arbitrarily chosen for undirected graphs because the Laplacian is indifferent to the choice of direction as L = G
Graph diffusion and graph neural networks. In this work, we consider x V:V+ R as multi-channel signal (or feature) over the node set. We denote x; E RC the signal over node and let X Rxxe collects the signals over all the nodes. The previously defined discrete gradient and divergence operators lead to the following graph diffusion process, which can be seen a discrete version of heat diffuusion equation in (
Ox = =div(DVX), = Σ xx,,,, - x,), 0t
where the diffusivity D(x,, x) is often scalar-valued and positive, which applies channel-wise. In the special case of homogencous diffusion, i.e., D(x,, = 1, the diffusion process can be written as 0x: St div( - -LLX); This process is known the Laplacian smoothing where the signals become progressively smooth by wittinn-negghbourhood averaging. The solution to the diffusion equation is given by the heat kernel, ie., (() (())), In fact, the graph heat equation can also be derived as the gradient flow of the so-called Dirichlet energy, which measures the local variations: Edit (X) = ((d)es ||x xx,xxx,11 x21 tr(X LX).
The graph diffusion process is related to the famous graph convolutional network (GCN) (Kipl & Welling 2017 where the latter can be viewed as taking the Euler discretization of the former with unit stepsize. In addition, GCN defines diffusion with (symmetrically) normalized adjacency À D-1/2AD 11/2 and Laplacian L A-A. The use of normalized Laplacian L in place of the combinatorial Laplacian L switches the dynamics from being homogencous to isotropic (where diffusion is weighted by node degrees). More precisely, the discretized dynamics gives the update X x -xx = Äx'. It can be readily verified that GCN corresponds to the gradient flow of normalized Dirichlet energy E (X) = EE ||x// /deg, x,/ /deg, I tr(X (Tx Additional channel mixing W and nonlinear activation (-)) added, leading to a single GCN layer, X o (Ax'
In the more general setup with anisotropic diffusion coefficients xx,,,x,t) the diffusion process relates to the general form of message passing neural network (MPNN) Gilmer et. al. 2017). Taking the Fuler
4

---

Published in Transactions on Machine Learning Research (02/2024)
discretization of the diffusion equation with stepsize T, can rewrite the process
ft x T
E x(xf,x)) xx) = (x4 (-(d)E
E M (x(.x))) (((d)EE
where xy) Dxx;, xx)(x} x,) represents the message passing between two nodes i, and U(x; m,) Xi + 7m; represents the message aggregation within the neighbourhood of node i. The channel-mixing matrix and nonlinear activation can be added for both the message passing and aggregation steps.
We finally remark that there cxist GNNs that cannot be casily interpreted within the continuous diffusion framework. This includes MPNNs where the updale involves operalions such as concatenation (Kearnes et al., 2016), gated recurrett unit (Li et al. 2015). In addition, spectral GNNs, such ChebGCN (Defferrard et al, 2016,, also do not have natural correspondence in the physical process. Hence exclude such GNNs from the discussion of this work.
3 A general framework of continuous dynamics informed GNNs beyond diffusion
Diffussin dynamics has been shown to underpin the design of message passing and graph convolutional networks. While showing promise in many applications, vanilla diffusion dynamics may suffer from performance degradation due to the following four types of causes:
Ouersmoothing: signals become increasingly similar as the propagation of GNN.
Oversquashing: message cannot be easily communicated
Heterophily: neighbouring nodes do not share similar features
Instability: Sensitivity to adversarial perturbation and vanishing or exploding gradients when increasing depth.
This has motivated the consideration of alternative dynamics other than isotropic diffusion, including anisotropic diffusion, diffusion with source term, geometric diffusion, oscillation, convection, advection and reaction. Many of them are dircctly adapted from the existing physical processos (as we discuss in this work).
This section summarizes existing developments on graph neural dynamics under general framework and categories the literature by the underlying contimuous system. We follow the same notations in Section 2 where a graph is represented as g (V,E) with | n and |1| = The graph signals or features are encoded in a matrix X, which is in general time-dependent. Unless mentioned of herwise, we omit. the time dependence and treat X as X(t) for notation clarity. We also denote x x(0) as the initial conditions for the system.
The general framework for designing continuous graph dynamics given follows, which relates the time derivatives of the signals with spatial derivatives on graphs.
Xx aL 012
8x
= FX(
(2)
where Fg is spatial coupling function that is usually parameterized by neural networks. The initial condition of the system is generally the input graph signals (after an encoder). We have summarized and compared existing works discussed in the survey in Table 2 in terms of the driving mechanisms and problems addressed. As we shall see, most of the existing works consider the first-order time derivative while some works explore the second-order time derivative to encode oscillatory systems.
As a summary, anisolropic diffusion provides more flexibility in adapting to different graph types by allowing different diffusivity coefficients, which may depend on the current state of graph signals. This can be achieved by explicitly factoring out the edge indicators or implicitly modelled driving mechanism is the diffusion with learnable coefficients, i.c., 0x div(A(X).... VX), for some learnable diffusion coefficients. Oscillatory processes model the acceleration through second-order differential equations,
attention mechanism. The main
Øt
5

---

Published in Transactions on Machine Learning Research (02/2024)
i.c. 0'X =o VX). The energy conservation of such processes help to avoid converging to trivial solutions 013 of constants and thus circumvent oversmoothing. This also prevents energy from exploding, which helps stabilize the training, Non-local dynamics allows information exchange at a longer distance, and thus have a wider receptive field at each step. This is in contrast to diffusion based dynamics where communications happen locally. This can be beneficial for tasks where long-range dependencies are crucial, such as node classification for heterophilic graphs. External forces can be further injected to modulate the direction, magnitude and even the nature of information flow on graph, which leads to ex ät Fai (X) + Fext (X), for some diffusion dynamics Faur and some mechanisms governed by external forces Fext. When equipping graphs with additional geometric structures, the resulting geometry- wnnpetrry-ddeepiinneddee dynamics offers brand- new perspective in controlling the behaviours of GNNs by modifying the underlying geometries. That is, ex - (X) where the dynamics rely on the additional geometry MM imposed on the graph. Furthermore, अt dynamics can often be interpreted as inherently minimizing some energy functional and thus can be seen as its gradient flow. This suggests directly modifying the energy rather than the dynamics to achieve desired properties. At last, multi-scale diffusion separates the diffusion dynamics for low- low-pass and high-pass filters, and thus achieve greater control for learning different frequency components.
3.1 Anisotropic diffusion
The first class of dynamics, anisotropic diffusion, generalizes the isotropic diffusion in GCN, offering great flexibility in controlling the local diffusivity patterns. In image processing, anisotropic diffussin has been extensively applied for low-level tasks, such as image denoising, restoration and segmentation (Weickerl et al. 1998). In particular, the Perona-Malik model (Perona & Malik 1990) sets the diffusivity coefficient. D x Vx which is often called the edge indicator as it preserves the sharpness of signals by slowing down diffusion in regions of high variations.
The idea of using anisotropic diffusion to define continuous GNN dynamics has been firstly considered by Poli ltt al.] (2019) and formalized by Chamberlain et al. (2021a), where a class of graph neural diffusion (GRAND) dynamics is proposed. The anisotropic diffusion process is formally given by
OX GRAND: : a div(A((X) -X)))
where AX) E Rax= encodes the anisotropic diffusivity along the edges. Here VX E Ruxxxe collects the gradient along edges and we use to represent the elementwise multiplication of diffusivity coefficients broadcast across the channel dimension. The coefficient is determined by the feature similarity, i.e., A(X) = la(x;, X(),)ee where x,) (Wxx,, Wax, computes the dot product attention with learnable parameters W WQ. Softmax normalization is performed on A(X) to ensure it is right-stochastic (row sums up to one). Notably, the explicit-Euun Euler discretization of GRAND corresponds to the propagation of graph attention network (GAT) (Veličković et al. 2018). Scveral versions of GRAND are proposed to render the dynamics more adaptable compared to the discretized version in (Veličković et al. 2018). In particular, the diffusivity matrix AX) can be fixed as A(X") that only depends on the initial features. This leads to a GAT propagation with shared attention weights. In addition, AX)) can vary according rewired edge set based the attention score, i.e., E (i..)) (i,j) E E, x(x,,),)) > p} for some threshold p 0. Instructively, this interprets the graph structure as discrete realization of certain underlying domains where graph rewiring dynamically changes the spatial discrctization.
a dynamically
Building on the formulation of GRAND, BLEND CChamberlain et al. 2021b) further augments the input signals x, with position coordinates u, for each node. The diffusion process then becomes
aXx div(A([X, UJ) v[X. UJ). Ōt
BLEND:
The joint diflusion over both positions and signals is motivated by diffussin on Riemannian manifolds with the Beltramil operator, in which the gradient, diffusivity and divergence all depend on the Riemannian metric (that varies according to the position). In a similar vein, augmenting the position information while diffusing on graphs produces joint evolution of features as well as topology, which further allows graph rewiring to improve the information flow. In particular, based on the evolved positional information, the
6

---

Published in Transactions on Machine Learning Research (02/2024)
Table Summary of continuous dynamics informed graph neural networks, including the driving mechanism and the problems addressed, including oversmoothing (OSM), oversquashing (OSQ), graph heterophily (HETERO), and stability (STAB) with respect perturbation or with training, such as gradient vanishing explosion associated with increased depth. Note show the problems addressed either theorctically empirically in the paper (unless proven otherwise in subsequent literature). More detailed discussions are in Section
Problems Tacklod
Mothods
Mcchanism
OSM OSQ HETERO STAB
GRAND
Chamberlain et
2021a
Attention diffusivity rewiring
BLEND
Chamberlain al.
2021b
Position augmentation
Mean Curvature
Song et m.
2022
Non-smooth edge indicators
Beltrami
Song et al. 2022
Anisotropic
LLaplacian
Fu et al. 2022
p-Laplacian regularization
S SJJ
diffusion
DIF DirFor
Wu et al
2023b
Full graph transformer
DIGNN Fu et al.
2023)
Parameterized Laplacian
GRAND
Thorpe et al.
2022
Source term
PDE-GCNp
[ilaaoo al.
2021
Nonlinear diffusion
GIND Chen et 2022
Implicit nonlinear diffusion
Oscillation
PDE-GCN# [Bliasof et al CraphCON
2021
Wave equation
J
(Rusch al.
2022
Damped coupled oscillation
د>
FLODE (aakeey et
2023
Fractional Laplacian
Non-local
QDC
Markovich
2023
Quantur diffusion
dynamics
TIDE
Behmanesh
et a
2023
Learnable heat kernel
G2TN
Toth et al.
2022
Hypo-elliptic diffusion
CDE Zhao
2023b
Convection diffusion Reaction diffusion
GREAD Chor al 2023
Allen-Chan retraction with negative diffusivity
ACMP Wang al. 2023
Diffusion
with external
ODNet
Lv et al. 2023
Diffusion with confidence
forces
ADR-GNN Ellasot et al.
2023
Advection reaction diffusion
G²
(Rusch et al. 20236
Diffusion gating
MHKG (Shao et al
2023
Reverse diffusion
A-DGN Cravina aJ.
2023
Anti-symmetric weight
NSD Bodnar et
2022
Sheaf diffusion Bracket dynamics with higher-order cliques
Geometry
Hamiloniaag, etc.
Gruber
2023
underpinned
dynamics
Kang et al.
2023
HamGNN
Learnable Hamiltonian dynamics
Zhao et al.
2023a
Gradient flow
GRAAF (Giovanni et 2023
Parameterized gradient flow
Multi-scale diffusion
Separated diffusion for low-pass and high-pass different scales
GradFUFG (Han et al.
2022
"The ability of the methods to mitigate oversquashing is through graph rewiring. fp-Laplacian and DIGNN avoids oversmoothing provided the input dependent regularization (i.c., soure term) is added.
graph is dynamically rewired as E [(i,)) de(u,, Uy) <r) or by k-nearest neighbour graph. The positional information can be pre-computed by personalized PageRank (Gasteiger et al. 2019). deepwalk (Perozzi et al. 2014) or even Iearned hyperbolic embeddings CChami et al. 2019).
In BLEND, the diffusivity is given by the aliention score over both the positional features and signals, which is in fact the core idea of transformers (Vaswani et al.] 2017) that augments samples with positional encoding. Wu al. (2023b) develop transformer-based diffusion process (called DIFFormer) where attention diffusivity coefficients computed on fully connected graph V x V. The input graph (represented via input adjacency matrix A) serves a geometric prior that augments the learned attention matrix.
0x
FIFFormer:
= divvxv((A) A(X)) vx),
Ōt
7

---

Published in Transactions on Machine Learning Research (02/2024)
where (F), = Ejey Fi, denotes the divergence operator on the complete graph and A(X) computes the diffusivity by transformer block (Vaswani et al. 2017), different to the ones used by GRAND and BLEND. A recent work (Wu et al. 2023a has shown the evolution via both local message passing through A and global attention diffusion through A(X) improves the generalization under topological distribution shift, Le., when training and lest. graph topology differs.
Apart from its connection to censformer-based dynamics, BLEND is in fact motivated by a geometric evolution known as Beltrami flow where the diffusion over non-Euclidean domains also depends the varying metric. In (Song et al., 2022), the Beltrami flow, along with mean-curvaurre flow (a geometric flow where the movement is governed by the mcan curvature at cach point on the surface), is generalized to graph domains by explicitly factorizing out the edge indicator ||xx;|| == v Eyonee ||x; - x;|1?. Formally, let Sme (X), Sbel(X) (X) be the diffusivity coefficients of mean curvature and Beltrami diffusion, with their elements and [S)ei(X]] = Tox. + [6x, |xx, The diffusion processes Song
defined as (X))ks = [xxx]] Txxy
et al. 2022 propose are
0x
Mean Curvature: :
div ((A(X) @ Sin(()) VX).
ōt
Beltrami: 0X div div( @ (be) -V)).
Ōt
where A (X) is computed from the dot product attention following the previous works (Chamberlain et al., 2021a b). For both dynamics, non-smooth signals are preserved by slowing down diffusion where signal abruptly changes. As commented by the paper, positional information can be added in similar way as BLEND (Chamberlain et al. 2021b). It should be noticed that although BLEND originates from the Beltrami flow, the dynamics turns out to be the same as GRAND, augmented with positional embeddings. In contrast, Song et al. (2022) explicitly separates the edge indicator out from the attention matrix A(X).
A more general p-Laplacian based graph neural network is proposed by Fu et al. 2022 where the diffusion is derived from y-Taplacian regularization framework.
Ox = div (IIVX| Vx) - -M(x S), S),
paaaplacian: at
with S as a source term and f > controlling the regularization strength. The diffusivity |VX |--2 is an n x n matrix with elements [|[ = | - if (i.j) E E. The injection of source information the heat exchange from the system to the outside. In the paper the source
can be understood physically term is simply the imput feature matrix, i.c., S X When p = 2, the diffusion reduces to the heat diffusion with classic Laplacian. When p p=1, 1, the dynamics recovers the mean curvature flow (although the definition slightly differs from the one in (Song et al. 2022 ). As a result, with properly selected p. the process is flexible in adapting to different types of graphs and able to perverse the boundarics without oversmoothing the signals. It is worth mentioning that unlike previous works that use discretization to update X, the paper directly solves for the equilibrium state by setting ät 0, which leads to an implicit graph diffusion layer given by p-Laplacian message passing.
ax
The p-Laplacian diffusion corresponds to the gradient flow of a p-Dirichlet energy, defined by E (X) Eiiee ||x x,1l" given with a regularization term |X - S||2. A similar idea has been considered in (Dan et al. 2023) where the Dirichlet energy is replaced with the total variation on graph gradients, which leverages the Li norm (which is different to the case of p 1 in the p-Laplacian diffusion (Song et al. 2022 A dual-optimization scheme is introduced due to the non-difeornniaablit of the objective at zero.
A recent paper Fuu et al. 2023) parameterizes the graph gradient and divergence instead of the diffusivity coefficients as in previous works, and defines a parameterized graph Laplacian for diffusson process. In particular, Fu et al. (2023) consider weightod inner products for both the I.²(V) and L²(EE,, i.c., (f. (f.g) = Evev X1fe and (7, L) F.,FF. The graph gradient. is defined (VeJ)s == Vee St), which Fja), where Xx, Di Vi.5 are strictly positive real-valued functions on nodes and edges respectively. Here we denote Ve, dive to emphasize that the gradient and divergence operators are parameterized. Because the graph gradient is parameterized
- ΣjEN, Vi.,) also leads to a notion of graph divergence (dive = 2x.
8

---

Published in Transactions on Machine Learning Research (02/2024)
and may not be anti-symmetric, i..., (Vef)s -(Vef) the divergence encodes directional information. The paper also parameterizes the weighting functions to be node-dependent, i.e., Xi = xx(),), Pt.j = وi, (X,, xj) and dh.j = which involves learnable parameters. The diffusion process the paper considers is thus
aX = dive - --X
DIGNN:
Ot
where a regularization term X S| added similarly as in (Fu et al. 2022).
The idea of adding an energy source has also been considered in GRAND ++ (horpe et al. 2022 based
the framework of anisotropic diffusion of GRAND:
ax Ōt = div(A(X) VX) +
GRAND++:
where S E Ruxe source term. The paper proposes random walk viewpoint to show that, without the source term, the dynamics reduces to GRAND and is guaranteed to converge to stationary distribution independent of the initial conditions X Each row of the source term S is defined as s; = Ejez (x)(x] x²) with I _ selected node subset used as the source term and x ये. Ejez x2 is the average signal. 6, denotes the initial transition probability from node j to i. By construction, the limiting signal distribution is close to an interpolation the source signals in the selected subset I. Similar idea of source term injection has also been considered in earlier work (Xhonneux et al.) 2020), which can be seen as the homogeneous diffusion with both source term and residual term. The proposed model (called CGNN) follows the dynamics ax - XW + XX, for some learnable channel mixing matrix W.
Anisotropic diffusion is generally nonlinear in the sense that diffusivity depends nonlinearly on the mass along the evolution. This is the case in edge-preserving dynamics as the diffusivity explicitly depends nonlinearly on the gradient. GRAND-based dynamics is also nonlinear as long as the attention coefficients is computed for each timestep. (Fliasol et al., 2021] Chen et al., 2022). additional nonlinearity further incorporated by factoring the diffusivity as the composition of linear operator K. and its adjoint K*, i.e., K*K. Then pointwise nonlincarity function o() is added, leading to
0x Ōt
In the case when a is the identity map, the dynamies recovers the anisotropic diffusion. Such a nonlinear system has been firstly proposed by Ruthotto & Haber (2020) for defining convolutional residual networks for images. In (Eliasof et al. 2021). the idea is generalized to graphs by defining K. as learnable pointwise convolution. Specifically, the dynamics, called PDE-GCND, can be written in terms of the gradient and divergence operator as follows.
PDE-GCND 0x - KTGKTTTKGGN
where K a learnable parameter and G is the gradient operator defined Section 2 It can be readily observed that when a identity and K I, the dynamics reduces to the heat diffusion implemented by GCN.
In the follow-up work (Chen et al. 2022 the linear operator IC (parameterized by K) is applied over the channel space instead of the edge space, i.e.,
OX
GIND
-G TGXKK K.
0t
Motivated by Gu et al. (2020). Chen et al. -G oo (G + (X")) ) ")K, where by(-) is an affine transformation with paramcter Ω. The model corresponds to a refinement process for the flux Z and the output is given by a decoder over Z + X It has convex objective function provided the nonlincarity monotone and Lipschitz and K & G upper bounded norm. This result guarantees the convergence of the dynamics and allows structural constraints be embedded to the dynamics by explicitly modifying the objective.
2022 consider implicit propagation of GIND Z
been shown the equilibrium state of the implicit diffusion corresponds to the minimizer
9

---

Published in Transactions on Machine Learning Research (02/2024)
3.2 Oscillations
The phenomenon of oscillation has been widely found in physics, which primarily features the repetitive motion. Unlike diffusion that dissipates energy, oscillatory system often preserves energy and is thus reversible. Oscillatory processes are often modelled as second-order urdinary/partiag differential equations. One simple example of oscillatory process is characterized by the wave equation Ø cÂæ, which is hyperbolic PDE. The wave equation has been considered in (Eliasof et al. 2021 for defining dynamics on graphs, which follows the nonlinear formalism in (Ruthotto & Haber 2020):
0x = div div(KC - -K
PDE-GCN#
ōt
In addition, GraphCON RRuch et al. 2022 considers more general oscillatory dynamics which combines a damped oscillating process with coupling function. That is,
0X (Fo(X)) 7X a Ōt GraphCON: : 0+2
0x
where Fx(X); = Fx, (eA)) the coupling function, a 2 and o(.) some nonlinear activation. When (Fg (X)) 0, a = 0, the system reduces to the classic harmonic oscillation for cach node independently. Adding the damping term _0x de mimics the frictional force that diminishes the oscillation. Finally, due to the presence of interdependence between the nodes, the coupling function is required to model the interactions between the nodes. The paper mainly considers two choices of coupling function, with isotropic and anisotropic diffusion (which leads to GCN and GAT respectively). Formally, (X); = =E Eist,ee AXX),xx represents the message passing with normalized adjacency or learned attention scores. When = 1, is identily, the GraphCON can be rewritten as DE div(A(X) VX) a ax "F' which is effectively the wave equation with a damping term. GraphCON is flexible in that the coupling term can accommodate arbitrary message passing scheme. In addition, it possesses greater expressive power by showing the GNN induced by the coupling function approaches the steady state of GraphCON, while the latter explores the entire trajectory.
a'
3.3 Non-local dynamics
We have so far focused on local dynamics, in the sense that the diffusion or oscillation happens locally within the neighbourhood. Thus it usually requires sufficiently large timestep for one node's influence to reach a distant node (with respect to graph topology). Graph rewiring employed in GRAND and BLEND can be utilized to enable long-range diffusion by modifying the graph topology. This section explores various sraamics-based formulations that transcend the local community when propagating information, resulting in non-localized dynamics.
Fractional Laplacian. Fractional Laplacian (Pozrikidis) 2018 Lischke al. 2020 has been effective to represent complex anomalous processes, such as fluids dynamics in porous medium Caffarelli & Vazquez 2011). A recent work (Maskey al. 2023) utilizes the fractional graph Laplacian/adjacenge matrix -A" (for some R) in order to define non-local diffusion process as
OX Ōt
FLODE:
-
where A is the symmetric normalized adjacency matrix. A critical difference compared to p-Laplacian in terms of the order is that here Laplacian is often denso, and thus the corresponding diffusion is non-local where long-range interactions are captured. When coupled with a symmet ric channel mixing matrix W, i.e., 8x = - X the flexibility at in the choice a allows dynamics to accommodate both smoothing and sharpening effects, which avoids oversmoothing and suited for heterophilic graphs. The work also extends the formulation to directed graphs and correspondingly defines the notions of oversmoothing and Dirichlet energy with the asymmetric Laplacian. On directed graphs, the fractional Laplacian defined through singular value decomposition, i.e.,
be fractional, instead of being restricted to integers. The fractional
10

---

Published in Transactions on Machine Learning Research (02/2024)
A= -UE'V" where U,V E C are unitary singular vectors and Σ R contains singular values the diagonal. Similar idea of using SVD for directed graph processing has been explored in (Zo et al. 2023
Finally, the paper also considers Schrödinger equation based diffusion as 2x 0E i where i
represents the imaginary unit.
Quantum diffusion kernel. The Schrödinger's equation i (b(u.)) = Hub t) has also been considered in [Markovich] 2023), where H is the Hamiltonian operator (composed of kinetic and potential energy operator). (2, t) denotes the (complex-valued) quantun wave function at position u at time t, and the square modulus of the wave function t)), indicates the probability density of a particle. With the quantum system defined by (u, t), a quantum state (xb(t) refers to the superposition of all the states, ie., (+)) = J (u, (),,t) lu)ddu, where (u) is the position state (a basis vector for representing the quantum state). One can recover the components of the quantum state by the inner product between quantum state vector (t))t) and position vector (u), i.e, (u, t) (ulp((t). In a simple quantum system where the Hamiltonian H. is time-independent, the solution to the Schrödinger's equation can be written in terms of quantum state as (+))) = = --*+)1(0)).
On a graph with n nodes, (t)) E C can be interpreted as the state vector particles across all nodes, and the position state refers to the node set. In a system without a potential and thus the potential energy term is zero, the Hamiltonian reduces to the negative Laplacian, and the Schrödingor's equation reduces to - = - (t)) The eigenvectors of L, denoted as {1 provides a complete orthogonal basis, which can be treated as the position basis so that one can express the solution as [ε{(t) Σn_ Cge ( where A is the k-th eigenvalue and C2 = (v²()) Instead of working with the solution which involves the complex unit. Markovich] (2023) define a kernel that models the average overlap between any two nodes i, as the inner product between (x((t) and [b(t)),, which is Σi.=1 Galo)) ()); To engineer observation operators as spectral filter, the paper further leverages Gaussian filter P P= Ei=r (hx--))//22 which leads to the proposed quantum diffusion kernel (QDC) Q E Raxx, where
n QDC: Qu, Q,,=
Σ e (Ae () (
k=1
The kernel matrix Q is interpreted the transition matrix between the nodes and hence can be supplemented for any message-passing passing-based graph neural networks. Hence the resulting quantum diffusion corresponds to the anisotropic diffusion where the diffusivity is given by the quantum diffusion kernel. The kernel matrix can be further sparsified either using threshold or KNN. The kernel allows non-local message passing due to the quantum interference across all the position states (i.e., Q is computed with all the states). Further a multi-scalc variant of quantum diffusion is proposed that combines the propagation from quantum diffusion and standard graph diffusion.
Time dcrivative diffusion. Another work (Bchmanesh et al. 2023 introduces a non-local message passing heat kernel. Recall the heat diffusion 3t = - LX, where its solution is given by the heat kernel as ((t) = exp(- - ((). One can generalize the heat kernel to capture the transition between any two states in time, i.e., X(t) = exp(-(t (f-sft()))))) xs)). Instead of setting a pre-defined s, the paper parameterizes the heat kernel as exp(-tgL) where to is the learnable timestep in order to adapt the diffusion range to different types of dataset. Further, to simultancously account for local message passing, the paper combines the adjacency matrix A with learned heat kernel, which leads to the proposed dynamics as X(1) A exp((<oo))(ss). This corresponds to the following continuous dynamics (up to some normalizing constants):
scheme by combining local message passing with learnable-timess
follows ax
OX = exp((Axxp-ttt) exp(-teL) VX).
TIDE: : Ōt
It is clear that when lg = 0, the model reduces to the classic GCN. The learnability of lo ensures the model is flexible to capture both local and multi-hop communication.
Hypo-elliptic diffusion. In Toth et al. 2022), non-local and higher-order information is captured via the so-called hypo-elliptic diffusion, which based on a tensor-valued Laplacian that aggregates the entire
11

---

Published in Transactions on Machine Learning Research (02/2024)
trajectories of random walks on graphs. The sequential nature of the path can be characterized with the free (associative) algebra, which lifts the sequence injectively to a vector space with non-commutative multiplication (i.e., an algebra). More formally, an algebra H over Re can be realized as a sequence of tensors with increasing order, i.c., H == {v = (v", v', v'.v2....) v E (R2)8m) where (R²)00 denotes the space of m-order lensors. For example, (RR))0= = RR, (Ro)1 = RR. The scalar multiplication and vector addition of H is defined according to λv (AvT) mz0 for A R and v + w == (vm + w=") The algebra multiplication of H is given by w (Li=o vk wm- m20' H can be further made into a Hilbert space with the chosen inner product (v, w) == E Emzu(v" (v", wm) where (, denotes the classic inner product on the tensor space (Re)sm.
With the properly defined algebra, one can lift a sequence to such space, thus summarizing the full details of its trajectory. Specifically, denote the space of sequences in R as SRq(R") = UK-o (RC) where (R+)++1 denotes the k + 1-product space of R. A sequence, denoted as x = =x"; ,.,,,. x*) E (RR))*+ an element. of the sequence space (E Let i : R + H be an algebra lifting, which allows define sequence
feature map (xx) = +xx") xp(x -x)) ... pxx x
E H. One example of such injective map is the tensor
exponential given by (p)) = expe (u) = ml
6m
for u E IR", where nmmm == x 80 x. 0 x. Such a feature
m20
map is able to summarize the entire sequence path up to step k.
On a graph, let x E R denote the signals at node i E V at diffusion step k 2 0. Instead of focusing on the signals at a particular timestep k, the paper leverages the sequence map to capture the entire past trajectory of the diffusion process through (xx;) E H where x; = (x,, ,..,, x,). The corresponding diffusion process
requires a tensor adjacency matrix, A E H= with the entries A,, = x(x) x)) E H if (i.j) E & and 0 otherwise. The associated Laplacian L can be defined accordingly. For example, the random walk Laplacian has entries L,, and L, 1 -xx x!) if (i, E & and 0 otherwise. The classic graph heat diffusion is generalized to hypo-elliptic graph diffusion as
deg, xxx]
0x(X) = LX())
G2TN:
Ot
where we let == = (x(1), ((,x.) E H The multiplication of L and (XX) is defined over the space of algebra H (similarly as how classic matrix multiplication works). In the case of random walk Laplacian, the paper verifies that the solution of the hypo-elliptic diffusion summarizes the entire random walk histories of each node, in contrast to the snapshot state at each timestep given by the classic diffusion equation. Notice here instead of working with node signals x directly, the diffusion concerns all the node signals along the trajectory, Le., xxx). Thus (xx) is more expressive compared to x. The paper further adapts the attention mechanism to define a weighted hypo-clliptic adjacency as A = a(x². xx)) -x)), which correspondingly defines an anisotropic hypo-clliptic diffusion.
3.4 Diffusion with external forces
Most of the aforementioned processes are only controlled by a single mechanism, either diffusion oscillation. This section discusses systems that impart external forces to the diffusion dynamics, such as convection, aduection, and reaction. In particular, convection and advection are widely known in physical sciences that describe how the mass transports as result of the movement of the underlying fluid, Such a process is characterized by dz Br = -viv where v represents the velocity field of the fluid motion. Reaction process is more general and often found in chemistry where chemical substance interacts with each other and leads to a change of mass and substance, i.c., òz = rx)), for some reaction function r(-). Other mechanisms such as at gating, reverse diffusion and anti-symmetry have also been exploited in literalure to modulate and control the diffusion dynamics.
Convection-diifusiion. Convection-diffuse dynamics combines the convection with diffusion process in which mass not only transports but also disperse in space. Zhao et al. (2023b) generalize the convection- diffusion equation (CDE) to graphs as
OX
CDE: :
div(A(X)).. VX) + (iv(Va X)
Øt
12

---

Published in Transactions on Machine Learning Research (02/2024)
where V denotes velocity field and (V o X)1, = V. @x, with @ representing the clementwise product. In particular, Zhao et al. (2023b) define Va, (W(x - x,)) RC for some nonlinear activation a(-) and learnable matrix W. Such a choice is motivated from the heterophilic graphs where neighbouring nodes exhibit diverse features. Hence Vay captures the dissimilarity between the nodes, which ultimately guides the diffusion process, Accordingly, div(V o X), = =Ejadee Vi, 3 x, measures the flow of densily al node in the direction of V1.. The nonlinear paramcterization of the gradient further enhances the dynamics adapt to different graphs with varying homophily levels.
Reaction-diffusion. A more general reaction-diffusion process is considered in (Choi al., 2023
0X div(A(X) VX) + R(X), Öt
GREAD:
where R(X) is the reaction term, and proper choice of R(.) recovers many existing works as special cases. For example, the Fisher reaction (Fisher| 1937) is given by R(X) = xX @ (1-X), which can be used to model the spread of biological populations where represents the intrinsic growth rate. Other reaction processes include Allen-Cahn (Allen & Cahn 1979) R(X)= = X @ (1 (1-X X @ X) and Zeldovich (Gilding &
Kersner 2004 R(X) = X o (X - X & X). Apart from the physics informed choices of reaction term, Choi et al. (2023) also consider R(X)= = X", which follows GRAND++, CGNN to incorporate a source term, and also proposes several high-pass reaction term based on graph structure, aiming to induce a sharpening effect. For example, the Nlurring-sharpeningg reaction is defined as R(X) = (A(X) - A(X)))x, which corresponds to performing a low-pass filter A - followed by a high-pass filter I A(X). The paper also considers two learnable coefficients a to control the emphasis on diffussin and reaction terms respectively, i.e.
a di)) VX) + 3R(X).
A closely related work (Wang et al. 2023) adopts the Allen-Cahn reaction term for the reaction-diffusion process. Further, the paper allows negative diffusson coefficients, which is able to induce a repulsive force between the nodes:
OX = div - B) VX) + X a
ACMP:
where B >>0 O is bias term controlling the strength and direction of message passing. This allows A(X) - B to model the interactive forces and can become negative. Further, the first term of ACMP corresponds to the gradient flow of a pseudo Dirichlet energy given by Ei.eee (Ai,j - Br,))[x; - xj12² where we ignore the dependence of A on X for the time being. This suggests, when Aijj - B > 0, node is attracted by node j by minimizing the difference between x; and Xj and when A, B < O, node is repelled by node j. It is noticed that the presence of negative weights can cause the energy to be unbounded and thus the dynamics may not be convergent. To resolve the issuc, the paper considers external potential, namely the well potential (8/4) Eiev(1 - ||x, 12))2 ACMP is indeed derived as the gradient flow of the pseudo Dirichlet energy combined with the double-well potential. Theoretically, the Dirichlet energy Edir of ACMP evolution is upper bounded due to the Allen-Cahn reaction term as well as lower bounded due to the repulsive forces. Hence, the system remains stable while avoiding oversmoothing. For practical implementation, ACMP sets B,, = B > 0, a tunable hyperparameter for simplicity of optimization. Two channel-wise coefficient. vectors are added to balance the diffusion and reaction similarly in (Choi et al. 2023). Unlike in ACMP WWann et al. 2023) where the repulsive components Bij are treated hyperparameters, a recent work (Shi et al. 2024 proposes more principled strategy for incorporating negative weights through augmented nodes with label information.
In addition, the idea of incorporating repulsive force in the message passing has also been explored in (L et al. 2023). The work proposes to view the message passing mechanism on graphs in the framework of opinion dynamics. The work explores the notion of bounded confidence from the Hogselmann-Krause (HK) model (Hegselmann & Krause 2002) where only similar opinions (up to some cut-off threshold) are exchanged. This motivates the following dynamics on graphs that separates messages according to the similarity level of graph signals:
0x
ODNet: : 0t
= -divxx( VX) + R(X),
13

---

Published in Transactions on Machine Learning Research (02/2024)
where divyxy defines message aggregation over the complete graph. ((A(X)) is an elementwise scalar- function (called influence function) on diffusivity and is required to be non-decreasing. In (Lv et al. 2023) (-) is chosen to be piecewise linear as follows.
i 22 e S $ E2,
(() = 8,
u(1 8),
otherwise
where μ 0 and are hyperparameters. In addition, (1, defines the inffuence regions (which resembles bounded confidence in HK model). Because can be negalive, it is able to induce repulsive forces by separating the node representations. Empirically, the work chooses v == 0 for homophilic graphs and < 0 for heterophilic graphs. It is noticed that when v < O, the message can propagate even for unconnected nodes in the case of v < O.
Addeetion-diiftsioon-eeeae
ADR-GNN Elliasof et al. 2023 further adds explicit advection term top of the reaction-diffusion process considered in CCho et al. 2023).
ADR-GNN: ax div(A(X): VX) div(V x)+ R(X).
The work considers homogeneous diffusion with channel scaling, i.e., div(A(X) VX - -LXdiag (0), where 0 E R is the channel-wise scaling factor. In contrast to CDE (Zhao et al. 2023b), the advection term concerns two directional velocity fields Viji Vjá E R which measures both in-flow and out-flow of density, with (V X)),, = Vya x Vi, @ X By further ensuring channel-wise row stochasticity of both Vú, and V,,r, Vi,j ④ x, interpreted as the mass of node j to be transported to node Thus the advection term, given by div(V X); Ej(CEEE V,, O x, - Xi, quantifies the net flow of density node The reaction term R() is parameterized by additive and multiplicative MLPs with a source term, R(X)= = o (XW, tXnh(XW,) O X X') Different to previous works, the paper considers operator splitting for discretizing the continuous dynamics, i.e., by separating the propagation of the three processes. Such scheme allows separate treatment and analysis of each process. Particularly, Eliasof et al. (0023) demonstrate the mass preserving property and stability of the advection operator. Empirically, ADR-GNI has shown promising performance for modelling not only the static graphs but also spatial temporal graphs where addeetion-diiffssonn-
process has been successful (Fiedler & Scheel 2003).
Gating. It has been shown that controlling the speed of diffusion through convection/adveclle term is able to counteract the smoothing process. Rusch et al. (2023b) adopt different strategy by explicitly modelling gating function on the diffusion:
OX Ōt
G2
T(X) 3 div(A(X). VX)
where T(X) E [0, 1]axe collects the rate of speed for each node and across each channel. Specifically, the rates depend the graph gradient T(X) tanh(E |8 X, P)), O where &; ==ENN, À A(X)(xx and ((X) is another message aggregation. Conceptually, the gating rates T(X),, for node i depend on the channel-wise graph gradients to all its neighbours. The use of tanh(-) ensures when ΣSEN, E X & 0, the rate T(X)ia vanishes faster rate. This correspondingly shuts down the update for node i and thus avoid oversmoothing, The paper also considers more general choices of coupling functions in place of div(A(X) VX) where nonlincarity is added.
The idea of gating has been similarly explored in DeepGRAND Nguuen et al. 2023 which utilizes a channel-wise scaling factor (X)" e 3xd place of T(X) where (XXx = X P '1, The dynamics also incorporates a perturbation to the diffusivity as A(X) (1 + c)I. The scaling factor and perturbation help regulate the convergence of node features so that the node features neither explodes nor converges too fast the steady state.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Reverse diffusion. Similar to the idea in (Choi al. 2023 that simultaneously accounts for low-pass and high-pass filters, (haa et al. (2023) introduce a reverse diffusion process based on the heat kernel. When coupled with heat diffusion, it leads to a process that accommodates both smoothing and sharpening effects:
ox
MHKG: : öt = (diag(()) + diag(02) cxp(g(L) x)X,
where 0,, 02 are learnable filters and f.g are scalar-valued functions defined over the eigenvalues of É, e.g., f(L)= Uf(A)UT where f(A) diag([f(>)]]==)) with A being the diagonal matrix collecting the cigenvalues and U collecting the cigenvectors of the normalized Laplacian L. In particular, f.9 are assumed to be opposite in terms of monotonicity, In the simplest case, suppose f(L) = - and g()) L, then the two terms in MHKG correspond to the heat kernel and its reverse. The filtering coefficients Q1, 02 controls the relative dominance of the two terms, where the former smooths while the latter sharpens the signals.
Anti-symmetry. In (Gravina et al. 2023). a stable and non-dissipative system is proposed by imposing the additional anti-symmetric structure for channel mixing matrix as
0X ŌL
A-DGN:
- WT) + FX(),,
where we omit the nonlinearity and a bias term to show only the driving factors. Here, (X( is a coupling function similar as in (Rusch al. 2022). such as a simple homogeneous message passing Fx(X); = ESEN, Vx, for some weight matrix V or the one with attention mechanism (Veličković et al. 2018). The incorporation of anti-symmetry constraint for the channel mixing renders the system to be stable and non-dissipative, both due to the fact that the Jacobian of dynamics has pure imaginary eigenvalues, i.e., all real parts of the eigenvalues are zero. This suggests the solutions to the system remain bounded under perturbation of initial conditions, which concludes the stability of the evolution. In addition, the zero real part of the eigenvalues suggests the sensitivity of the node signals to its initial values, i.e., the magnitude of (x:(t) vi, t stays constant throughout the dynamics. This result infers that oversmoothing in the limit does not occur the final state still depends on the initial conditions as lim (x,
ax,(0)
(1) * O. Further, this also suggests
the magnitude of aLines remains unchanged over time and hence gradient vanishing explosion is avoided (0) during backpropagation. This allows the dynamics to be propagating to the limit and capture long-range
interactions without facing the issue of oversmoothing or training instability.
3.5 ueodeerr--uddeppnnned dynamics
Previous sections have viewed graphs from its trivial topology, and standard dynamics on graphs amounts to propagating information from node to edge space and back, only utilizing the connectivity between nodes. In fact, graphs can often be viewed as discrete approximations of more general topological spaces such as Riemannian manifolds, which possess complex cont inuous geometries. In this section, we show how dynamics on graphs can be underpinned with additional geometric structure, such as sheaves and stalks in (Bodnar ct al. 2022), and cliques and cochains in (rruber et al. 2023).
Sheaf diffusion. Hansen & Gebhart 2020)); Barbero et al. 2022a) and Bodnar et al. (2022) leverage cellular sheave theory to endow a geometric structure for graphs. Specifically, cach node i E V and edge Bgy [i.î} E & (undirected) is equipped with a vector space structure F(i), with a linear map Ficmy F()) + Flei)) (called restriction map) that connects the node to edge spaces. Its adjoint operator Flae,, : :(ee)) + F()) does the reverse. The direct sum of all vector spaces of nodes is called the space of 0-cochains, denoted by (G: = Diey F(i). Suppose, without loss of generality, that all vector spaces F(es)) are d-dimensional, we can represent Fiaes as a d x d matrix. Further, suppose x E (G; then each X; E Rdd and x E Rnd by stacking the feature vectors across all nodes.
Under the construction of voctor spaces on nodes and edges, the concepts of graph gradient and divergence require to utilize the restriction maps because the vector spaces are not directly comparable. That is, the graph gradient (also known as the co-boundary map) is defined (Vxx)a == Fjec, X; -Ficeyy X where
15

---

Published in Transactions on Machine Learning Research (02/2024)
the restriction maps transport the signals to a common disclosure space. The graph divergence is thus similarly defined as (div= EjEN, F iees Gagz for Ges E F(ei)) This leads to the definition of sheaf Laplacian as L=(x); = dVvx(V = EJEN, Fide, (Frany Faan, xz). The sheaf Laplacian is an nd nd block positive semi-definite matrix, with the diagonal blocks (Lf) = EEEN; Flan,, and off-diagonal blocks (Iy) = --F Ftaee,Fjeen A symmetrically normalized sheaf Laplacian can be similarly computed by D L 1/2 with D is the block diagonal of Lz. The corresponding sheaf diffussin process is
0X = -iv>> = -L,X
Øt
where here X E ((nd)xe, where e is the feature channels and divy, Vy, Ly are applied channel-wise. The Sheaf diffusion turns out to be the gradient flow of the sheaf Dirichlet energy Lr(XLyxX) which measures the smoothness of signals in the disclosure space, For practical settings where sheaf structure is unavailable, one can construct such feature through imput embedding. It is worth highlighting that, when d = 1, the sheaf Laplacian reduces to the classic graph Laplacian and the sheaf diffusion becomes the heat diffusion. In Bodnar et al. 2022), variety of restriction maps are constructed, which leads to dynamics flexible enough to handle different types of graphs and avoid oversmoothing, The paper also develops a general framework for learning the sheaf Laplacian from the features and include channel mixing and nonlinearity to increase the expressive power:
OX = -L (I W1)XW2)
NSD:
ŌL where Wi E Rdxd transforms the feature vectors and W2 E Bexe' mixes the channels and @ denotes the Kronecker product. LF(x) is parameterized via a matrix-valued function on the current feature values.
In (Bodnar et al. 2022), the sheaf Laplacian is paramctorized by Fidey = (V[x where -|I- denotes concalenation. A Tollow-up work (Barbero et al. 20226) devises a sheaf attention mechanism further enhance the diffusson process. Let A(X) = be matrix of learnable attention coefficients (the same in GAT (Veličković et al., 2018)), and let A (X)) @ Laxd that assigns uniform attention coefficients for each feature dimension within vector space. The atlentive sheaf diffusion (ShealAN) is introduced (A(X) @ As(x) - I)X, where (Ar(x))ss = Fiaesy Fa is the sheaf adjacency matrix with self-loop, i.c., 6ú E E. A second-order sheaf PDE (NSP) proposed in (Suk et al., 2022) using the wave equation as 8x 8
ax
dr
xVxX.
Bracket dynamics. Gruber al. (2023) propose to use geometrie brackels that implicitly parameterize dynamics on graphs that satisfy certain properties while equipping graphs with higher-order structures. The formulation requires concepts from structure presuuriireeeeringggg bracket-based dynamics and exterior calculus. In general, for state variable z, its dynamics can be given by some combination of reversible and irreversible brackets. The reversible bracket (also known as Poisson bracket) is denoted by (4, F) == dzz I. for some skew-symmetric operator L and some inner product ), The reversibility is result of energy conservation. The irreversible bracket is defined by [A, = (āz M MOE) ) for some (either positive negative) semi-definite operator M. The irreversibility describes the loss of energy from the system due to friction or dissipation.
(AA
(04
dE
The double bracket [A, = 0A i ag)) is an irreversible bracket.
2z
For simplicity, the paper considers A = x and one simplify the brackets as E| M de and E) = i 0E The paper considers four different types of dynamics leveraging both reversible and irreversible brackets:
Hamiltonian
ag {2, E);
at
Gradient:
ax
- [ar, E];
De da
(3)
Double bracket:
{x,, E} + {(x, E}};
DE Ba
Metriplectic:
{x,, E} + [}
OF
where E(x) is referred to as the energy of the state and 5(z) is the entropy. The dynamics of cach process captures fundamentally different systems and has natural substance in physics. The Hamiltonian dynamics
' Here, in order not be confused with the Laplacian L used in previous discussions, we T.
16

---

Published in Transactions on Machine Learning Research (02/2024)
leads to complete, isolated system in the sense that no energy is lost to the external environment. In contrast, both the gradient and double bracket dynamics are incomplete where the energy is lost through the process. Metriplectic dynamics is complete by further requiring the degeneracy conditions L 05 M 8E
= 0.
Bm
de = 0 and the entropy inequality, i.e., de These conditions ensure the conservation of energy, Le., at isolated system.
as
0 in an
In order to properly generalize the dynamics to discrete domains like graphs, one requires to identify the state variable, an inner product structure as well as energy and entropy. Rather than only considering node features as the state variable, Gruber et al. (2023) extend the framework to higher-order clique cochains, including edges and cycles. Formally, let S2 be the set of k-cliques on graph G, which contains ordered, complete, subgraphs generated by (k 1)-nodes. For example, nodes, edges and triangles, correspond to the 0-clique, I-clique and 2-clique respectively. The exterior derivative operator is denoted as da ((04) + 3(5++1) where B(22) represents function space over the domain Ω. The specific structure of 3 depends on the chosen inner product (,,-). The dual derivative dz 3(Q++1) - ((Qx)) is given as the adjoint of the d2 that salisfies (affG))++ = (f, G for any f ( G E ((2x+1). One common choice of & is the L' space, where one can derive dž- = dg. For example, do, the graph gradient on nodes and dō becomes the graph divergence on edges. The classic graph Laplacian can be computed as didu- = dg do G G we have shown in Section
Instead, the paper pursues inner product parameterized by positive definite matrices Ao, A A up to k-cliques. For example on node space Ωo. where the L space has inner product fl g for f. E 3(2a), the generalized inner product is given by f Aog. Under such choice, one can show d' = A dx ARt1-
The state variable is set to a node-edge feature pairs, denoted by x = (q, which can be treated as the position and momentum of phase space. Further, the following operators are utilized to extend the dynamics in graphs,
db -6)) i= do 0 )
G = (fo
dgdo
0 did + docs): and M M- = A
It can be verified that L is miemssymmctric and G, M are symmetric positive definite with respect to the block-diagonal inner product parameterized by A diag(An A1). Furthermore, let X (Q. P) denote the tuple of node and edge feature matrices, the energy considered is the total kinetic energy on both node and edge spaces, i.c., E(X) = _ (Il 12 + [[P|13). The gradient with respect to the generalized inner product (called A-gradient) can be computed as V F(X) [A, dynamics, it is in general non-trivial to identify entropy such that the degeneracy conditions hold. Hence the paper constructs a scparate energy and entropy function pair as (X) = fx(Q) + (d P) and Sm (X) (d) d),), for some node function fø and edge functions 9E, Is applied channel-wil wise. The A-gradient is derived as
BE 3q A ap ] [AJ AP]T For the Metriplectic
A 1 (Q) [od]] 1 & VAgE P)
0 VASM = A AA d11 ( Vags(did P
V Fm X)=
Importantly, the degeneracy conditions LVAS = MVAE- = 0 are satisfied by construction.
Finally the generalized dynamics from
3 to graphs are
0X
Hamiltoniang
Dt EXX))
OX -G(X)VAL(X);
Gradiento
JI
OX
Double bracket.
DI -
OX L( E.,. (X) M,
Metrplecticg
where the operators L(X), G(X), M(X) are state-dependent through attention mechanism to construct the metric tensor Ag, A1, which thus parameterizes the exterior derivative operators.
17

---

Published in Transactions on Machine Learning Research (02/2024)
Remark 1 (Connection to GCN and GAT/ GRANGR GCN can be seen the Gradiente dynamics with Ao, 11 parameterized by node degrees. Setting Ao a diagonal matrix (on nodes) with diagonal entries 00 = deg, and A as the identity matrix (over edges), we can verify (didAA, Q); = =iee, (q:/deg, - 9i/ / /deg, = (IQ); In this case, Gradiente; recovers the heat equation (with normalized Laplacian) when = and thus leads to GCN under discretization.
Similarly, GAT can be seen as the same Gradient dynamics while learning a metric structure Ao, A1. That q₁)). (;))) Let the atlention coefficient be o(q:9;) = - ,ny ao,ss Then one can show Gradiente dynamics with P = O corresponds to a (symmetrically) normalized version of GRAND.
is, choose 40,u v EyEN, exp(alin(q;, (()) and di,es exp(atin(q;:
This result demonstrates the irreversible nature of GCN or GAT/ /GRAND dynamics where energy dissipates, while other dynamics are either conservative or partially dissipative.
Hamiltonian mechanics. The Hamiltonian mechanics has also been considered in (Kang et al. 2023) where instead of using the edge features as the momentum, the work parameterizes the momentum with a neural network from the node features. This leads to distinction compared to the previous works in the cvolution of the node fcatures, which is docoupled from the graph structure. Let Q denote the node leat and the momentum is compuled as P = MLPe (Q). The Hamiltonian mechanics is determined by a Hamiltonian function H(Q,P), P), which characterizes the total energy of the system. The dynamics is governed by the Hamiltonian equation
aQ 0H
OP
OH
Ot
ap ōt
aQ
The paper motivates a varicty of paramcterization for the Hamiltonian H. One specific choice of Hamiltonian is H(Q, = ((Q)) where M(Q) represents the inverse metric tensor al Q (also learnable in the local neighbourhood). Its solution Q(t) recovers the geodesic (a locally shortest curve) on the manifold with metric parameterized by M at Q. Hence, nodes are effectively embedded a (implicit) manifold space where the metric is learnable. Unlike previous methods, where the dynamics of the features depend coupling function regulated by the graph topology, here the evolution of Q is independent across the nodes. To further incorporate the graph structure, message passing by neighbourhood aggregation is performed after the feature evolution via Hamiltonian equation. Multiple layers of Hamiltonian dynamics and message passing are stacked to model complex geometries and node embeddings.
A follow-up work (Zhao et al., 2023a) extends the formulation by considering general graph-coupled Hamilto- nian function (Q, For example, the paper considers Hamiltonian function defined the norm of the output from a two-layer GCN, where dieg 8Ng are computed from auto-differentiatiin. Further, the "Q
paper studies various notions of stability on graphs from the theory of dynamical system, including BIBO, Lyapunov, structural and conservative stability. The work conducts a systematic analysis and comparison of proposed Hamiltonian-based dynamics with existing graph neural dynamics, such as GRAND, BLEND, Mean Curvature and Beltrami. It is found that the conservative Hamiltonian dynamics has shown improved robustness against adversarial attacks.
3.6 Dynamics as gradient flow
Most of the aforementioned designs of GNNs are inspired by evolution of some underlying dynamics. The learnable parameters, such as channel mixing, are usually added after discretization to increase the expressive power. In (Giovanni et al. 2202)) the dynamics is instead given as the gradient flow of some learnable energy. The framework is general and includes many of the existing works as special cases (as long as the channel mixing matrix is symmetric] [ The parameterized energy takes the following form:
1 ux( XQ) ur AXW) + (X, (x) = -
Althouggh many existing works can he written as gradient flow of some energy, their motivation comes mostly from the dynamics, not from the energy.
18

---

Published in Transactions on Machine Learning Research (02/2024)
where A is the (normalized) adjacency matrix and St W R are assumed to be symmetridf The first term determines the external forces exerted upon the system and the second term reflects the pairwise interactions while the last term quantifies the energy preserved by the source term X Although & can be general, the paper considers a form xx)X = tr x"W). The gradient flow of Ex( yields the dynamics of the following general form,
0X_ dt
GRAFF:
VEg(X) XQ --- AXW W.
This formulation includes many of the existing dynamics-motivated GNNs. When Ω = W, W corresponds to the evolution of (residual) GCN or GAT/GRAND (Cammeelain et al. 2021a if A is constructed by attention mechanism. If W + 0, this corresponds to the GRAND++ Thorpe el al. 2022) and thus also the CGNN (Xhonneux al. 2020). The decrease of the general energy does not necessarily lead decrease in the Dirichlet energy (which is special case of Ex( with Ω W = II, 0). This is mainly due to the occurrence of both attractive and repulsive elfects along the positive and negalive eigen-directions
0, this
+ - - and rewrite the energy (without Φ²) as of W. More formally, one decompose W = +
(X) 2
Σ xx (S W)x, + 4 LEV
Σ (K.)EE
[VX),
1 Σ (V- (K.)EE
2
It has been shown that the gradient flow minimizes the gradient along the positive eigen -igen-directions (which leads to smoothing effect) while maximizing the gradient along the negative eigen-directions (which leads to sharpening effect). In contrast, minimizing the Dirichlet energy always induces smoothing effect because W I with only positive cigen-directions. This allows GRAFF to avoid oversmoothing and produce sharpening effects as long as the W has sufficiently large negative spectrum.
3.7 Multi-scale diffusion
Previous sections have mostly focused on dynamics with local diffusion. In other words, the signal/densin at certain node changes depending on its immediate neighbourhood. The communication with distant nodes only happens when diffusion time is sulficiently large. Section 3.3 discusses dynamics that. leverages non-local diffusion, but nonetheless mostly restricted to single scale at each diffusion step, e.g.. single a in fractional diffusion [Maskey et al. 2023) and to for time derivative diffusion (Behmancsh et al. 2023). Multi-scale graph neural nelworks, such as ChebyNet (Delferrard el al.] 2016), LauczosNet (Liao et al. 2018) and Framelet GNN [Zeng et al., 2021b) are capable of capturing multi-scale graph properties through spectral filtering on the graph Laplacian. The eigen-pairs of graph Laplacian encode structural information different levels of gramularity and separate processing of each resolution provides insights into both local and global patterns.
Several recent works have adapted the continuous dynamics formulation to multi-scale GNN. Han et al. (2022) introduce a multi-scale diffusion process via graph framelet. Apart from the multi-scale properties shared with other spectral GNNs, graph framelet further separates the low-pass from high-pass filters. Let Wo.J E aR denote the low-pass framelet. transform and W.j E RRaxn r ===1, 1..., .,. R. j 1,....J denote the high-pass framelet transforms, where R the number of high-pass filter banks and J is the scale level. For a multi-channel graph signal X E Raxe, Wo,XX and Wry r 1, 1..,, R, high-pass framelet coefficients. For notation clarity let I {00, u [(r, ()sersIsss) be the framelet index set. Due to the reconstruction property of framelets, it satisfies that Eireee W Wry
1,.., represent low-pass and
The spatial framelet diffusion proposed in (Han et al. 2022 is given as
0x
GradFUFG:
Σ
(W. W. X. - W.J.A.W, Aw.. XW..),
Øt
(nJ)ez
where Org, Wny njj are symmetric channel mixing matrices. When Prg = Wr, I, by the tightness of framelet transform, GradFUFG reduces to the heat equation as dt
ax = -Xx The spatial-basod framelet diffusion
ITe symmetric assumption not required except for the purpose of simplification for the gradient derivation and analysis.
19

---

Published in Transactions on Machine Learning Research (02/2024)
can be considered by GRAFF (Giovanni et al., 2023) as special case. It can be seen that, due to the separate modelling of low-pass and high-pass as well as different scale levels, the dynamics can adapt to datasets of different homophily levels as well as has the potential of avoiding oversmoothing.
seen gradient flow of generalized Dirichlet energy, which also inchudes the parameterized energy
4 On oversmoothing, oversquashing, heterophily and robustness of GNN dynamics
As we have briefly mentioned, the main hurdles for successful designs of GNN include oversmoothing, oversquashing, graph heterophily and adversarial perturbations. The framework of continuous GNNs allows principled analysis and treatment for the issues identified. In fact, many of the previously introduced dynamics are motivated to overcome the limitations of existing GNN designs. Nonetheless, there exist possible trade-offs such as between oversmoothing and oversquashing (Giraldo et al.] 2022 Shao et al. 2023). which makes it. challenging for GNN dynamies to avoid both phenomenon at the same time. Conceptually, common strategies for mitigating oversquashing relies on graph rewiring (Topping et al.
2022) that increases propagation strength, which likely enhances the smoothing effects. Apart from the trade-off, new problems may emerge result of resolving the existing ones. One example is the training difficulty (from gradient vanishing or explosion) associated with complex and long-range dynamics.
This section provides a holistic overview on these undesired behaviours GNNs through the lens of continuous dynamics, along with a discussion on how existing approaches address the issucs.
Oversmoothing. Oversmoothing refers a phenomenon that node signals become progressively similar as result of message passing, and converge a state independent of the input signals. Although there are many different characterizations for oversmoothing, most if not all rely the (normalized) Dirichlet energy that measures node similarity. Recall from Section 2 the Dirichlet energy is defined as (X) tr(X ΣX), where L is the symmetrically normalized Laplacian. Because oversmoothing claims loss of distinguishability across the nodes, a natural quantification of oversmoothing is (X()) + 0 as t state, nodes with same degree collapse into a single representation. A stronger notion of oversmoothing has been considered in RRusch et al. 2022 2023a) requiring an exponential decay of the Dirichlet energy for oversmoothing to occur, i.e., Edi ((t)) S C2t ,t > 0 and for some constants C₁, C2 > O. This is equivalent to claiming that the system has a node-wise constant, exponentially stable equilibrium state. In this work, we focus on a notion of oversmoothing called low-frequency dominance (LFD) put forward by Giovanni et al. (2023). A dynamics is said to be low-frequency dominant if Eair (Xt)()/IXX( - O. It can be readily verifies that when Edir (())) + 0, then Eair (x()(((()) - O, while the reverse argument is false (see Appendix B.2 of Giovanni et al. (0023) more discussions). The normalization by ||X(t)|l reveals the dependence of asymptotic behaviour to the dominant spectrum of the dynamics, where low-frequency is related to the smoothing effect.
1 Eusyes /dg, X /dg,,
From the definition of the Dirichlet energy, in the limiting
In the sense of LFD, it can be shown that the dynamics relying on (anisotropic) diffusion would incur oversmoothing in the limit, such as the linear versions of GRAND (Chamberlain al. 2021a), BLEND [Chamberlain et al. 2021b), and DIFFormer (Wu et al.) 2023b). See for example (Giovanni et al., 2023
Theorem B.4) for formal proof. Dynamics that involves (non-smooth) edge indicators, like Mean Curvature, Beltrami flows (Song et al. 2022), p-Laplacian (Fu et al. 2022) and DIGNN (Fu et al. 2023) also correspond to LFD dynamics although the convergence is slower compared to (smooth) diffusion dynamics. Such a statement has been formalized in (Fu et al. 2023).
We summarize existing remedics for oversmoothing as follows.
(1) Source term: One remedy that steers the dynamics away from the low-frequency dominance is to include a source term. For example, in p-Laplacian (Fu et al.) 2022) and DIGNN (Fu et al.) 2023), the source term is implicitly added in terms of input dependent regularization, while GRAND++ (Thorpe et al. (022) and CGNN [Xhonneux et al. 2020) explicitly inject the source information to the dynamics. The presence of a source term ensures the Dirichlet energy is lower bounded above zero where the limiting state is non-constant.
20

---

Published in Transactions on Machine Learning Research (02/2024)
(2) Non-smoothing dynamics: Choosing non-smoothing dynamics can help avoid oversmoothing, such as oscillatory process as in PDF-GCNH (Eliasof et al. 2021 and GraphCON (Rusch et al. 2022p. Oscillatory system usually conserves rather than dissipates energy. In particular, it has been proved that the constant equilibrium state of the dynamics is not exponentially stable because any perturbation remains due to the energy conservation. The reversible dynamics, such as Hamiltonian and metriplectic in (Gruber et al. 2023 also non-smoothing by construction.
(3) Diffusion modulators: Imposing external forces to counteract or modulate the diffusion mechanism is beneficial for mitigating oversmoothing. Examples include the high-pass filters in GREAD (Choi
et. al.
2023) and GradFUFG (Han et al.
2022)
repulsive diffuusion coefficients in ACMP Wang
et al.
2023 and ODNet (Lv et al.) 2023
negative spectrum in GRAFF (Giovanni et al.
2023 0,
reverse heat kernel in MHKG (Shao et al. diffusion gating in G (Rusch al.) 2023b and DeepGRAND (Nguyen et al.) 2023). In essence,
2023
anti-symmetry in A-DGN (Gravina et al. 2023
oversmoothing can be avoided in the above dynamics by diminishing smoothing effects in the limit of evolution.
(4) Higher-order geometries: Bodnar et al. (2022) demonstrate the cause of oversmoothing from the perspective of choosing a trivial geometry. In contrast, by enriching the graph with a higher-order sheaf topology, the asymptotic behaviour of the diffusion process can be better controlled. Indeed, the sheaf Dirichlet energy can be increased with a suitable choice of non-symmetric sheaf structure Proposition 17).
on graphs, thus avoiding oversmoothing under this regime (Bodnar al. 2022
Heterophily. Unlike homophilic graphs where neighbouring nodes tend to share similar features and labels, nodes in heterophilic graphs usually exhibit dissimilar patterns compared to the neighbours. GNN that is dominated by smoothing effect generally less preferred for such graphs. Following (Giovanni et al. 2023). the ability of a dynamics to adapt for heterophilic graphs is measured in terms of high-frequency dominance (HFD). A dynamics is said to be high- high-frequency dominant if Eair (X(())))) the largest eigenvalue of L. Intuitively, HFD dynamics is dominated by sharpening effect and eventually converge to the breeueeey eigenvectors of the Laplacian where node information gets separated. In this work, equate the ability of dynamics handling heterophily with its ability to become dominated by the highest frequency. Although HFD dynamics is also undesired due to information loss related to the low frequencies, here we focus on the ability, meaning that a system should have the flexibility to converge to the eigenspace associated with the highest. frequency, which allows separability of bipartite graphs. Under such notion, dynamics that is purely smoothing cannot be HFD. The incorporation of a source term and (positive) graph re- weighting alone are not sufficient to turn a smoothing dynamics into sharpening one even though empirically these strategies boost performance on heterophilic datasets. This is because the driving mechanism of the resulting system is still diffusion.
PL. where PL S is
Existing dynamics that provably accommodates separating effects can be classified as follows.
(1) Sharpening induced forces: One scheme for system to be HFD is to explicitly introduce sharpening induced forces. Most of the diffusion modulators identified for tackling oversmoothing amounts incorporate such anti-smoothing forces, including GREAD (Choi et al. 2023). GradFUFG HHan)
et al. 2022), ACMP Wang el al. 2023 ODNet (Lv el al. 2023), GRAFF (Giovanni el. al. 2023
and MHKG (hao et al.) 2023). Conceptually, the dynamics is dominated by the high frequency if the magnitude of the sharpening effect surpasses the smoothing effect.
(2) Higher-order geometries: Once the graph is equipped with a shcaf topology, Bodnar et al. (2022) have shown that choosing a higher-dinensionaal stalks and non-symmetric restriction maps allows sheaf diffusion to gain linear separability in the limit for heterophilic graphs.
We highlight that other schemes, such as oscillatory dynamics in GraphCON (Rusch et al. 2022) and convection/advectioo process in (Zhao et al. 2023b Eliasof et al. (003) also demonstrate empirical success under heterophilic settings. Nevertheless, theoretical guarantee for theses schemes in adapting heterophilic graphs is currently unavailable.
21

---

Published in Transactions on Machine Learning Research (02/2024)
Oversquashing. The phenomenon of oversquashing has firstly been empirically observed by Alon & Yahav (2021) and later formally studied by [Topping et al.] (2022); Di Giovanni et al. (2023) Such a phenomenon has been identified as a key factor hindering expressive power of GNNs (Di Giovanni et al. 2023). Oversquashing concerns a scenario where long-range communication between distant nodes matters for the downstream tasks whereas message passing squashes information due to the exponentially growing size of the receptive field. A closely related concept under-reaching, which refers to shallow GNN not being able to fully explore long-range interactions (Barceló et al., 2020). A critical difference between under-reaching and oversquashing is that the former can often be alleviated by increasing the depth of GNN while the latter can occur even with deep GNNs. One major cause of such a phenomenon is the local diffusion process according to the given graph structure, where messages are exchanged only within the neighbourhood. This can be formally characterized by the sensitivily across nodes, measured through the Jacobian. More formally, consider a (discretized) dynamics X = Ag(x'), where Ag is a coupling function that aggregates information based on input graph g. The scnsitivity between nodes i.j E V after itcrations of updates can be computed as ex 2 where smaller value indicates lower sensitivity and thus higher degree of oversquashing. In the
dx ll2 S (A'A))), where A denotes the f-th matrix power of A and e > 0 is a Lipschitz constant that depends on the activation function and W. It can be readily noticed that the graph structure encoded in A critically determines the severity of oversquashing.
simple case of isotropic diffusion Ag (Xt) (AX one can show ||
Below are strategies employed in GNN system that avoids oversquashing.
(1) Graph topology modification: One natural strategy in addressing the oversquashing is to enhance communications by rewiring the graph structure. GRAND (Chamberlain et al. 2021a) and BLEND (Chamberlain et al.) 2021b) dynamically modify the connectivity according to the updated node features, which amounts to changing the spatial discretization over time. DIFFormer (Wu al.)
2023b), on the other hand, adopts a fully connected graph and thus avoids oversquashing by allowing message passing between all pairs of nodes.
(2) Non-local dynamics: Alternatively, non-local dynamics constructs dense graph communication function and thus mitigates oversquashing by design. This can be achieved for example by taking the fractional power of mossage passing matrix as in FLODE (Maskey et al.) 2023), leveraging the dense quantum diffusion kernel in QDC (Markovich] 2023), learning the timestep of heat kernel in TIDE (Behmanesh et al. 2023), and capturing the entire path of diffusion as in G2TN (Toth et al. 2022
(3) Mulli-scale and spectral fillering: Multi-scale diffusion in GradF (Han el al. 2022) has the poten- tial to mitigate oversquashing by simultaneously accounting for information at different frequencies. Further, properly controlling the magnitude of high-pass versus low-pass filtering coefficients as in MHKG (Shao et al. 2023) (in the HFD setting) can provably improve the upper bound of the node sensitivity and thus oversquashing is alleviated.
Despite the success of aforementioned techniques in addressing oversquashing, polential downside is the increased complexity of propagating information at each update, which is often associated with the more dense message passing matrix. We also remark that some methods, including GIND (Chen et al. 2022) and A-DGN (Gravina et al. 2023) are able to capture long-range dependencies without suffering from oversmoothing. In particular, the driving mechanisms for such purpose are the implicit. diffuusion GIND and anti-symmetric weight in A-DGN where the former can be viewed as an infinite-depth GNN and the latter allows to build deep GNNs with constant sensitivity to avoid oversmoothing.
Stability, gradient vanishing and explosion. Lastly, we highlight several other potential pitfalls of GNN dynamics, that are often less explored in the literature compared to the previous issues, such as robustness and stability, and gradient vanishing and exploding during training.
Stability and robustness against adversarial attacks critical factor in assessing the performance of GNNs. For continuous dynamics, [Song et al.] (2022) verify that the graph neural diffusion, like GRAND (Chamberlain) et al. 2021ab and BLEND (Chamberlain et al. 2021b), are empirically more stable to graph topology
22

---

Published in Transactions on Machine Learning Research (02/2024)
perturbation compared to other discrete variants, which follows from the derived theoretical results based heat. kernel. Song et al. (2022) also prove that, due to the row-stochastic normalization of the diffusivity matrix in graph neural diffusion, the stability against node perturbation is guaranteed. In (Gravina et al.) 2023). the robustness to the change in initial conditions is explicitly enforcod with the required anti-symmetry
(due to the zero real parts of the Jacobian eigenvalues). In (Zhao el al. 2023a), the conservative stability offered by Hamiltonian dynamics has shown enhanced robustness to adversarial attacks. In addition, Wu jet al. (2023a) improve the generalization ability of GNNs with respect to topological distribution shifts, via local diffusion and global attention.
Another plight of deep neural networks are vanishing and exploding gradients, which refers to the situation when gradient exponentially converges to zero or infinity as a result of increasing depth. Because classic graph neural networks are often designed to be shallow as in GCN (Kipf & Welling, 2017) and GAT (Veličković et al. 2018), in order to avoid oversmoothing, gradient vanishing or explosion have received less attention in the GNN community. However, in the continuous regimes, espocially when depth increases, these problems can emerge and severely escalate the training difficully. In (Rusch et. al.) 2022), has been verified that GraphCON is able to mitigate the vanishing and exploding gradient problems because the gradient of GraphCON is upper bounded at most quadratically in depth and is shown to be independent of the depth in terms of decaying behaviour. Due to the anti-symmetric channel mixing in A-DGN (Gravina et al. 2023 ), the magnitude of the gradient stays constant during backpropation and hence avoids the problem.
5
On training graph neural dynamics
Most of the works based on contimuous GNN dynamics consider the following architecture, which is firstly introduced in GRAND (Chamberlain et al. 2021a).
X(T) = X(0) /'' T Ox(1)
(0)= EEEbb
dl,
Y = (X()))
(4)
Ot
where ox(()
S1 [X, VX) are the graph coupled, parameterized, differential equation introduced in Section E are respectively the imput embodding and output decoding functions, which are usually learnable. The formulation in | provides a general framework for various learning tasks on graphs, from node-level to graph-level, from transductive to inductive (see more discussions in Section 7 Similar to classic GNNs, the training for graph neural dynamics consists of forward and backward propagation. The forward propagation solves the graph differential equation via numerical integrators, while backward propagation consists of solving an adjoint differential equation to compute the gradient.
3
Forward propagation. There exist variety of numerical solvers for differential equations, once the continuous dynamics is formulated on graphs. In fact, with the discrete differential operators defined on graphs, the PDE reduces to an ODE, which can be solved with standard numerical integrators. One natural strategy for discretizing a continuous dynamics is through finite differences. Particularly, the forward Euler and leapfrog methods are commonly employed for first-order and second-order ODE respectively. For a first-order ODE given by ax öe = F(X, t), the forward Euler discretization leverages forward finite time difference, which gives the update X(t + 1) = X(t) + +F(X(t), for some stepsize > 0. The forward Euler is an explicit method in that X(t + 1) depends on X(t) explicitly. In contrast, backward Euler method is implicit by discretization X(t+ 1) X(t) + +F(((t++ 1), + 1), which involves solving (nonlinear) system of equations to obtain X(! + 1).
For a second-order ODE a²x FXX t), the leapfrog method that leverages centered finite differences yields 05 the update X(t + 1) = (x - X(t 1) + 72 F((((tt) t), which has been considered for PDE-GCN, (Eliasof et al. p021p. The leapfrog method can be equivalently derived by rewriting the second-order ODE into system of first-order ODEs (concerning both the position and velocity) and then use forward Euler method to alternatively update the two. In GraphCON (Rusch et al. 2022), a similar idea has been applied for the more complex second-order dynamics.
For second-order dynamics like in PDE-GCNg and GraphCON, the same formulation applies if the second-arder ODE is rewritten as a system of first-order ODEs.
23

---

Published in Transactions on Machine Learning Research (02/2024)
Higher-order methods employ high-order approximations for solving both first- second-order ODEs and can be either explicit or implicit. Common choices include Kunge-Kutta, which is a class of single-step methods that requires evaluating F' at multiple extrapolated state. One popular variant of Runge-Kurt Kutta method is Runge- Kutta 4 that balances the accuracy and efficiency. It computes x(+++) X+ T (K + + 2K, + K2) where K2 = ((X + -K1/2,1+7/22 K3 =
k = F(X)())) ()) Multi-step methods, such as Adams- Bashford, store multiple previous steps in order to approximate high-order derivatives. More advanced solvers set the adaptive stepsize based on the error estimated at each iteration. Dormand- Prince is Runge- Kutta method with step-size control and has been widely adopted as the default solver for ODEs (Dormand] 1996).
K, = + + +)).
Backward propagation To compute the gradient, it is generally memory-consuming to differentiate directly through the numerical integrators used in the forward pass. Instead, Chen et al. (2018) considered the adjoinl sensilivily melhod (Pontryagin) 2018), which requires to solve an adjoint differential equation, which is more memory-effiiiet and accurate by explicitly controlling the numerical error. Such a scheme allows to decouple the forward and backward pass where the numerical solvers can be chosen differently. This is unlike the classic GNNs, where the complexity of the backward pass highly depends on the forward pass.
The forward and backward propagation schemes can be implemented through torchdiffeq package (Chen 2018). Choosing suitable integration schemes depends on the trade-off between efficiency, accuracy and stability. From the comparisons in (Chamberlain et al.] 2021a (b), it is shown that explicit, solvers, like forward Euler is more efficient, at the cost of being less accurate and stable regarding the choice of step size. On the other hand, implicit method requires less steps to reach a desired accuracy but requiring high computational cost per step. We refer to httpes//gtthubb.mmm//ttttteeer wwtp:///oo//otttttttteeeee Bacha//ggppppaa taapph-nuurllppee for typical implementation of continuous GNNs.
6 Complexity and scalability of graph neural dynamics
In this section, we compare the computational complexity of introduced graph neural dynamics in this work. We assume the implementation follows (4) and hence only compares the cost for evaluating ax Here we denote X E Raxe where n is the number of nodes and e as the number of channels after embedding. We also let d be the dimension of attention transformation matrix.
dr
Most dynamics of anisotropic diffusion, such GRAND (Chamberlain et al. 2021a): require time complexity of O((E(c) without attention (((E)e)). For BLEND, is further augmented by the dimension of positional embedding, i.e., O(EE(c+ Cpoe)) Although DIFFormer (Wu et al. 2023b) requires to compute attention over the fully connected graph, a linear attention scheme is employed to lower the complexity to O(ned + n²c) instcad of O(n2cd) For oscillatory processes, including PDE-GCNH (Eliasof et al. 2021) and GraphCON (Rusch et al. 2022), the complexity is on the same order as O((E)ed) by rewriting the propagation into a system of first-order dynamics.
Non-local dynamics generally demands higher complexity by propagation information on denser graph, such as QDC (Markovich 2023), with complexity O((E' (c) where |E') is the edge set corresponding to a denser graph. For the spectral-based based propagation, like FLODE (Maskey et al. 2023). TIDE (Behmanesh et al. )023), the cost scales with O(n'c) (after pre-computing eigendecomppositinn at a cost of O(n))). For G2TN (oth et al.] 2022) that requires to capture a long path of information with higher-order tensors, the complexity depends on the order of tensor m and the number of propagation step L, i.c., O(EEm²L, {mmc).
For diffusion dynamics with external forces, the complexity depends on whether the added forces dominate the computation of diffusion. For CDE (Zhao et al.) 2023b), GREAD (Choi et al.) 2023). ACMP WWang 2023), ODNet (Hegselmann & Krause, 2002) and G² (Rusch et al. 2023b), A-DGN (Gravina et al. the complexity is still dominated by the diffusion term ((E (or ((E For ADR-GNN (Elasso 2023) that requires to compute the edge weights further increases the complexity to O((n + El))²).
ct al.
2023
et al.
Lastly, MHKG (Shao et al. 2023) operates ove the spectral domain and hence costs O(n²c).
For Chomeery-underpinne dynamics, diffusion based on sheaf structure (Bodnar et al., 2022) requires at least ((8)fc) (using diagonal maps) where is the stalk dimension. The bracket dynamics (Gruber et al. 2023
24

---

Published in Transactions on Machine Learning Research (02/2024)
Table 3: Summary of experiments conducted for graph neural dynamics. Homo and Hetero refers to experiments for node classification with homophilic and heterophilic graphs. Inductive refers experiments validating generalization to unseen graphs. Scalability refers experiments on large-scale graph benchmarks. OSM OSQ refers to experiments validating the oversmoothing and oversquashing issues. STAB refers to experiments showing robustness and stability against perlurbations.
Homo Hetero Inductive Scalability Craph-level OSM OSQ STAB
Others experiments
GRAND BLEND
Mean Curvature
Beltrami
p- p-Laplacian*
Image/text classification, Spatial-temporal prediction
DIFFormer
DIGNN6
GRAND++7
Varying label rate Dense shape correspondence
PDE-GON
GIND
GraphCON10
FLODE
Directed graphs
QDC
TIDEL3
Geometric graphs
G2TN14
C
GREAD 16
ACMP!7
Hypergraph diffusion,
18
Network simplification Spatial-temporal prediction Node regression
1
G
2
A-GCN22
Treo- Proo-NeighboosMatchh
2SD
Hamiltoniang etc.24
Trajectory prediction
Link prediction, Mixed-geometry graphs
25
HamGNN26 GRAFF47
Chamberlain et al.
2021
Chamberlain et al.
202
(Song ct al.
2022
Fu et al.
2022
Wu et al.
2023h
Fu al.
2023
Thorpe al.
2022
Eliasof et al.
2021
Chen et al.
2022
10
Rusch ot al.
2022
Maskey et al.
2023).
12 Markovich
2023
Behmanesh et al
2023
Toth et
2022
Zhao
2023b
Choi et
2023
17 Wang et
2023
al
Eliasof
Rusch
2023b
Shao
2023
Gravina
2023
Boduar
2022
Gruber
al.
2023
Kang ct al.
2023
Zhao et al.
2023a
Giovanni al.
2023
scales linearly with the k-cliques and hence if only nodes and edges are considered as in the classic GNNs, the complexity is O(EEeed), matching the diffusion dynamics with attention. Finally, GRAFF (Giovanni et al. 2023) requires a complexity of O(n"c (&|c) and GradFUFG Han et al. 2022 has a complexity of O( due to the framelet transform.
In summary, the complexiyy/scalablity of graph neural dynamics mainly determined by the design of graph differential equations, which matches the discrete counterparts. In fact, using Euler discretization for solving the differential equations reduces the contimuous dynamics into the classic discrete versions, such as GCN and GAT.
7 Empirical benchmarks and evaluations of graph neural dynamics
This section summarizes empirical experimental procodures for evaluating the performance of different graph neural dynamics. Because graph neural dynamics can be viewed as generalization of GNNs via continuous formulation, classic benchmarks for evaluating discrete GNNs still applicable for the continuous GNNs.
25

---

Published in Transactions on Machine Learning Research (02/2024)
Node-level classification The most widely considered task is node classification, which aims to classify test nodes in a graph under semi-supervised setting (Kipf & Welling 2017]. For this task, the out Y in is passed through a linear layer for predicting the probabilities for each class. Common benchmark datasets include citation networks, Cora (McCallum et al. 2000 Citeseer (Sen ct al. 2008), y Pubmed (Namata et al.) 2012), co-authorship graphs, including CoauthorCSs CoauthorPhysies (Shchur el al. 2018), co-purchase graphs, including Computer, and Photo (McAuley et al., (2015). These graph datasets are known to be homophilic in the sense that neighbours tend to share similar features and labels. To verify whether a dynamics can adapt to heterophilic graphs, benchmarks including web-page link graphs, Cornell, Texas, Wisconsin (Pei et al. 2019), actor co-occurrence network (Tang et al. 2009). Wikipedia networks, including Chameleon and Squirrel (Rozemberrckii et al. 2021). Previous datasets are only used for transductive learning, i.e., classifying nodes in the same graph that. is used for training. For inductive learning setup, models are trained only on training graphs and are expected to predict node labels for test graphs. One popular dataset is PPI (Hamilton et al. 2017). where cach graph corresponds to a different human tissue documenting protein-protein interactions.
Graph-level classification Apart from the major experiments on node classification, some works consider graph-level prediction for evaluating the dynamics in extracting graph-level information. For this purpose, the output Y is passed through some pooling layer for aggregating the information across nodes for before final prediction. Commonly considered datasets, include MUTAG (Debnath et al., 1991). PTC (Helma et al. 2001), , COX2 (Sutherland et al.) 2003). NCI1 (Wale et al. 2008) which collect molecules or chemical compounds where each node represents an atom and edges represent chemical bonds; PROTEINS (Borgwardt) (et al. 2005), which collects proteins where each node represents amino acids and edges are constructed based on the spatial proximity. The task to predict the properties at molecule, compound or protein level.
Evaluation for oversmoothing and oversquashing. To evaluate whether a dynamics can potentially mitigate or even avoid oversmoothing, it is common to show node classification performance as the number of layers (or equivalently the integration time) increases. Alternatively, showing the evolution of Dirichlet. energy in terms of depth is equally indicative of oversmoothing, On the other hand, it is generally difficult to explicitly measure the level of oversquashing. Nevertheless, many synthetic experiments have been designed to test whether a graph dynamics is able to capture long range dependencies. For example in (Gu et al.) 2020: Chen et al.; 2022 Di Giovanni ct al.] 2023), data is created to test the ability of classifying nodes in a given distance away. It is expected that a dynamics that mitigates oversquashing will sulfer less from the performance degradation as the distance increases. For real applications, datasets that are known to exhibit strong long-range dependencies are often used for implicitly quantifying the degree of oversquashing for GNNs, including PascalVOC-SP, COCO-SP, PCQM-Contact, Peptides-func and Peptidees-truct (Dwivedi et al. 2022
Evaluation for scalability and stability. GNNs are known to suffers from poor scalability to large graphs because the message passing scheme requires to input the entire graph each step. Common large-scale graph benchmarks include OGB-arxiv, OGB-proteins and OGB-products (Hu et al., 2020) where the number of nodes ranges from 13k to 2500k. It thus becomes critical to report the runtime and memory consumption of graph neural dynamics on such large-scale datasets. In addition to scalability, stability and robustness against, adversarial perturbation is another important spectrum of benchmarking different dynamics. In general, various adversarial attacks, such as udding/removing nodes, injecting noise to node features, modifying graph topology, can be implemented through Graph Robustness Benchmark (GRB) (Zheng et al. 2021a A dynamics that is robust to such attacks is generally preferred.
Other experiments. Apart from the aforementioned benchmark experiments, some works consider tailored experiments showing the exclusive benefits of the proposed dynamics. This includes experiments on classifying images and texts where graphs are constructed based on feature similarities (Wu et al. 2023b), predicting node labels for spatial temporal graphs (Wu et al. 2023b Eliasof et al.) 2023), and processing geometric graphs (Eliasof et al., 2021 Bchmanesh et al.] 2023). Some works have generalized the dynamics to other graph types, including directed graphs (Maskey et al. 2023) and hypergraphs (Lv et al. 2023) and thus experiments for such graph types are considered.
26

---

Published in Transactions on Machine Learning Research (02/2024)
We have summarized in Table Ball the experiments performed for each dynamics introduced in Section
8 Open research questions
The recent success of graph neural dynamics has presented numerous opportunities for future explorations. This section summarizes several exciting research directions that remain open.
Systematic empirical comparisons of graph neural dynamics. From the summary in Section many dynamics share similar characteristics, especially the ones within the same categories. Moreover, the components of different dynamics can be combined together to form new dynamics. For example, the oscillatory process can be coupled with external forces like reaction and convection, and the augmentation of positional encoding is universal for all dynamics. Conducting controlled experiments that systematically compare the variety of graph neural dynamics through ablation and combination is an important future work for better undorstanding the utility of different components. This would provide principled guidelines for designing tailored dynamics for specific settings.
Interpretation of spectral GNNs from the perspective of continuous dynamics. We have summarized the dynamics mostly under the paradigm of spatial GNNs due to the nice interpretation of message passing as a form of diffusion. Spectral GNNs on the other hand, usually transforms the graph signals into coefficients weighted by eigenvectors of graph Laplacian (a process known as graph Fourier transform). Then filters are designed and learned to alter the frequency components of graph signals for downstream tasks. Although some existing works like (Han et al. 2022) have made preliminary attempts in formulating spectral GNNs through continuous dynamics, is generally unknown whether there exists a unified framework for designing continuous dynamics on the spectral domain. Such a framework could be beneficial in bridging the gap between spatial and spectral methods and could further motivate designs of dynamics that take advantage of both paradigns.
Dynamics with high-order graph structures and spatial derivatives. Most existing continuous GNNs are limited to evolution over nodes, except for (Gruber et al. 2023) that considers higher-order cliques. Meanwhile graphs often encode more intricate topology where higher-order substructures, such as paths, triangles and cycles are crucial for downstream tasks (Thiede al. 2021). For example, aromatic rings are cycle structures commonly appearing in molecule, which determines various chemical properties, such solubility and acidity. Thus designing a dynamics aware of such local substructures is beneficial. In addition, current dynamics often rely on coupling function that involves only the first-order spatial derivative (i.e., the gradient). It is thus interesting to investigate how to properly define higher-order spatial derivatives (e.g.. the Hessian) and incorporate into the dynamics formulation.
Explore the potential of graph neural dynamics for other applications. Existing studies proposing continuous GNNs mostly focus on the node-level prediction tasks while the continuous formalism presents a general framework for modelling not limited to the evolution of nodes, but also edges, communities and even the entire graph. It is thus rewarding to adapt graph neural dynamics for other types of applications, such as link and graph-level prediction, anomaly detection, time series forecasting. For example, Elhag et al. 2022 leverage both lincar and anisotropic diffusion for molecule property prediction: Bhaskar et al. (0023 utilize
graph heat and wave equation for graph topology recovery; Eliasof et al. (023 demonstrate the promise of using advection process for spatial temporal graph learning.
Expressivity of graph neural dynamics. The umprecedented success of GNNs have propelled researchers to study their expressive power in distinguishing non-isomorphic graphs (Xu et al. 2019 Morris et al. 2019). counting subgraph structures (Chen et al. 2020), etc. While the continuous formalism present framework for interpreting and designing GNNs, there have been few works that characterize the expressivily of graph neural dynamics, especially on graph and subgraph levels. There also lacks theoretical understanding on how the choice of numerical integrators affects the performance of the neural dynamics. In addition, an equally fruitful direction is to explore whether the theory of dynamical systems, such as energy conservation and reversibility can be leveraged to design theoretically more powerful graph neural networks.
27

---

Published in Transactions on Machine Learning Research (02/2024)
Continuous formulation for other graph types. Most of the continuous GNNs focus primarily dynamics over static, undirected, homogeneous graphs. Nevertheless, other graph types have also witnessed wide applicability, including signed or directed gruphs (where edges can be negative or directed) (Derr et al., Tong et al. 2020). heterogeneous graphs (where nodes and edges have multiple types) (Wang et al. 2019 Ji el al. 2021| geometric graphs (where nodes or edges respect. geometric constraints) [Brosteein et al. 30 spatial-temporyy graphs (where graph topology also evolves time) (Jin al. 2023b ap. The continuous formulation of GNNs for these more complex graph types could be beneficial for both enhancing the understanding and representation power of existing GNNs. However, such generalization requires nontrivial efforts. For example, the dynamics should preserve symmetries for geometric graphs and account for both evolution of graph topology and signals for spatial-temporal graphs.
2018 Huang et al.
2019 Monti et al. 2018
9 Conclusion
In this work, we conduct a comprchensive review of recent developments on continuous dynamics informed GNNs, an increasingly growing field that marries the theory of dynamical system and differential equation with graph representation learning. In particular, we provide mathematical formulations for a diverse range of graph neural dynamics, and show how the common plights of GNNs can be alleviated through the continuous formulation. We highlight several open challenges and fruitful research directions that warrant further exploration. We hope this survey brings attention to the potential of the continuous formalism of GNNs, and severs as a starting point for future endeavors in harnessing classic theories of continuous dynamics for enhancing the explainability and expressivity of GNN designs.
References
Samuel M Allen and John W Cahn. A microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening. Acta metallurgica, 27(6):1085- 1095, 1979.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Anima Anandkumar, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Nikola Kovachki, Zongyi Li, Burigede Liu, and Andrew Stuart. Neural operator: Graph kernel network for partial differential equations. In ICLR Workshop on Integration of Deep Neural Models and Differential Equations, 2020.
Federico Barbero, Cristian Bodnar, Haitz Sáez de Ocáriz Borde, Michael Bronstein, Petar Veličkovié, and Pietro Lio. Sheaf neural networks with connection Laplacians. In ICML Topological, Algebraic and Geometric Learning Workshops, pp. 28-36. PMLR, 2022a.
Federico Barbero, Cristian Bodnar, Haitz Sáez de Ocáriz Borde, and Pietro Lio. Sheal attention networks. In NeurIPS Workshop on Symmetry and Geometry in Newral Representations, 2022b.
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020.
Maysam Behmanesh, Maximilian Krahn, and Maks Ovsjanikov. TIDE: Time derivative diffusion for deep learning on graphs. In International Conference on Machine Learning, pp. 2015-2030. PMLR, 2023.
Alaa Bessadok, Mohamed Ali Mahjoub, and Islem Rekik. Graph neural networks in network neuroscience. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):5833 5848, 2022.
Dhananjay Bhaskar, Yanlei Zhang, Charles Xu, Xingzhi Sun, Oluwadamilola Fasina, Guy Wolf, Maximilian Nickel, Michael Perlmutter, and Smita Krishnaswamy. Graph topological property recovery with heat and wave dynamics-based features on graphsd. orXiv:2309.0990 2023.
Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pictro Liò, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. In Advances in Neural Information Processing Systems, 2022.
28

---

Published in Transactions on Machine Learning Research (02/2024)
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönaner, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(supl__] 1::47-156, 2005.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.. Geometric 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ć. Geometrie deep learning: Grids, groups, graphs, geodesies, and gauges. arXiv:2104.14477 2021.
John Charles Butcher. Numerical methods for ordinary differential equations. John Wiley & Sons, 2016.
Luis Caffarelli and Juan Vazquez. Nonlinear porous medium flow with fractional potential pressure. Archive for Rational Mechanics & Analysis, 202(2), 2011.
Ben Chamberlain, James Rowbottom, Maria T Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: Graph neural diffusion. In International Conference Machine Learning, pp. 1407 1418. PMLR, 2021a.
Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusson on graphs. Advances in Neural Information Processing Systems, 34:1594 1609, 2021b.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in Newral Information Processing Systems, 32, 2019.
Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Optimization-induued graph implicit nonlinear diffusion. In International Conference on Machine Leorning, pp. 3648-3661. PMLR, 2022.
Ricky T. Q Chen. torchdiffeq, 2018. URL http:s///gtth...coom//rgcaaaaaar
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in Neural Information Processing Systems, 31, 2018.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems, 33:10383 10395, 2020.
Jeongwhan Choi, Seoyoung Hong, Noseong Park, and Sung- Bae Cho. GREAD: Graph neural reaction-diffusion equations. In International Conference Machine Learning. PMLR, 2023.
Tingting Dan, Jiaqi Ding, Ziquan Wei, Shahar Z Kovalsky, Minjeong Kim, Won Hwa Kim, and Guorong Wu. Ro-think and re-design graph noural networks in spaces of continuous graph diffusion functionals. Xiw:2307.00022 2023.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-797, 1991.
Michaöl Defferrard, Xavier Bresson, and Picrre Vanderghoynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances Neural Information Processing Systems, 29, 2016.
Tyler Derr, Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In IEEE International Conference Data Mining (TCDM), pp.
IEFF, 2018.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pp. 7863-7885. PMLR, 2023.
John R Dormand. Numerical methods for differential equations: a computational approach, volume 3. CRC press, 1996.
29

---

Published in Transactions on Machine Learning Research (02/2024)
Vijay Prakash Dwivedi, Ladislav Rampášck, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35: 22326 22340, 2022.
Weinan E. A proposal on machine learning via dynamical systems. Communications in Mathematics and Statistics, 5:1-11, 2017.
Ahmed AA Elhag, Gabriele Corso, Hannes Stärk, and Michael M Bronstein. Graph anisotropic diffusion for molecules. In ICLR Machine Learning for Drug Discovery, 2022.
Moshe Eliasof, Eldad Haber, and Eran Treister. PDE-GCN: Novel architectures for graph neural networks motivated by partial differential equations. Advances in Newral Information Processing Systems, 34: 2021.
Moshe Eliasof, Eldad Haber, and Eran Treister. ADR-GNN: Adveetion-diffusoorrreeatt graph neural networks. arXiv preprint XxXc:2207.16000 2023.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417 426, 2019.
Bernold Fiedler and Arnd Scheel. Spatio-temporal dynamics of reaction-diffusion patterns. Trends in nonlinear analysis, pp. 23 152, 2003.
Ronald Aylmer Fisher. The wave of advance of advantageous genes. Annals of Eugeniis, 7(4):355 369, 1937.
Guoji Fu, Peilin Zhao, and Yatao Bian. p-laplacian based graph neural networks. In International Conference on Machine Learning, pp.
PMLR, 2022.
Guoji Fu, Mohammed Haroon Dupty, Yanfei Dong, and Lee Wee Sun. Implicit graph neural diffusion based constrained Dirichlet energy minimization. arXi::208.00380 2023.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in Newral Information Processing Systems, 32, 2019.
Brian H Gilding and Robert Kersner. Travelling waves in nonlinear diffusion-convection reaction, volume 60. Springer Science & Business Media, 2004.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263-122 1272. PMLR, 2017.
Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M. Bronstein. Understanding convolution on graphs via energies. Trasactions on Machine Learning Research, 2023. ISSN 2835-8856.
Jhony H Giraldo, Fragkiskos D Malliaros, and Thierry Bouwmans. Understanding the relationship between over-smoothing and over-squashing in graph neural networks. w.Xiv:2212.00 02374, 2022.
Alessio Gravina, Davide Bacciu, and Clandio Gallicchio. Anti-symmetric DGN: stable architecture for deep graph networks. In International Conference on Learning Representations, 2023.
Anthony Gruber, Kookjin Lee, and Nathaniel Trask. Reversible and irreversible bracket-based dynamics for deep graph neural networks. arXiv.2305.16611 2023.
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Newral Information Processing Systems, 33:11984-11995, 2020.
Jayant Gupta, Bharat Jayaprakash, Matthew Eagon, Harish Panneer Sclvam, Carl Molnar, William Northrop, Shashi Shekhar, et al. A survey on solving and discovering differential equations using deep neural networks. ar arXiv:2304.11 13807, 2023.
30

---

Published in Transactions on Machine Learning Research (02/2024)
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse problems, 34(1): 014004, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Andi Han, Dai Shi, Zhiqi Shao, and Junbin Gao. Generalized energy and gradient flow via graph framelets. or arXiv:2210.04 124, 2022.
Jakob Hansen and Thomas Gebhart. Sheaf neural networks. In NewrIPS Topological Data Analysis ond Beyond Workshop, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pottern Recognition, pp. 770-778, 2016.
Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confidence: models, analysis and simulation, Journal of Artifical Societies and Social Simulation (JASSS) vol, 5(3), 2002.
Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 17(1):107-108, 2001.
Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling, Equivariant diffusion for molecule generation in 3d. In International Conference on Machine Learning, pp. 8867-8887. PMLR, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in Newral Information Processing Systems, 33:22118 221333, 2020.
Junjie Huang, Huawei Shen, Liang Hou, and Xueqi Cheng, Signed graph attention networks. In Artificial Newral Networks and Machine Learning-CCANN 2019: Workshop and Special Sessions: 28th International Conference on Artificial Neural Networks, pp. 566-577. Springer, 2019.
Shudong Huang, Wentao Feng, Chenwei Tang, and Jiancheng Lv. Partial differential equations meet deep neural networks: A survey, orXiv:2211005567, 2022.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, (2)4)44945514, 2021.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey, Expert Systems with Applications, 207:117921, 2022.
Guangyin Jin, Yuxuan Liang, Yuchen Fang, Jincai Huang, Junbo Zhang, and Yu Zheng. graph neural networks for predictive learning in urban computing: A survey. arXi::2303.144: 2023a.
Ming Jin, Huan Yee Koh, Qingsong Wen, Daniele Zambon, Cesare Alippi, Geoffrey Webb, Irwin King, and Shirui Pan. A survey on graph neural networks for time series: Forecasting, classification, imputation, and anomaly detection. arXin:2307.03769 2023b.
Qiyu Kang, Kai Zhao, Yang Song, Sijic Wang, and Wee Peng Tay. Node embedding from neural Hamiltonian orbits in graph neural networks. In International Conference on Machine Learning, 2023.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer-Aided Molecular Design, 30:595-608, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
31

---

Published in Transactions on Machine Learning Research (02/2024)
Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Neural operator: Learning maps between function spaces with applications to pdes. Journal of Machine Learning Research, 24(89):1 97, 2023. URL http:://jjil..oog/pppprrs//////
111-552..hrr html
Harender Kumar and Ncha. Yadav. Deep learning algorithms for solving differential equations: survey. Journal of Experimental & Theorelical Arlificial Intelligence, pp. 1 1-46, 2023.
Qianxiao Li, Ting Lin, and Zuowei Shen. Deep learning via dynamical systems: An approximation perspoctive. Journal of the European Mathemalical Sociely, 25(5):1671-1709) 2022.
Yujia Li, Daniel Tarlow, Mare Brockschmidl, and Richard Zemel. Gated graph sequence neural networks. arXivv1511.05..00 2015.
Zongyi Li, Nikola Kovachki, Kamyar Aziwzaeneshelli Burigede Liu, Andrew Stuart, Kaushik Bhattacharya, and Anima Anandkumar. Multipole graph neural operator for parametric partial differential equations. Advances in Neural Information Processing Systems, 33:6755 6766, 2020.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. LanczosNet: Multi-scale deep graph convolutional networks. In International Conference Learning Representations, 2018.
Anna Lischke, Guofei Pang, Mamikon Gulian, Fangying Song, Christian Glusa, Xiaoning Zheng, Zhiping Mao, Wei Cai, Mark M Meerschaert, Mark Ainsworth, et al. What is the fractional laplacian? a comparative review with new results. Journal of Computational Physics, 404:109009, 2020.
Guan-Horng Liu and Evangelos A Theodoron. Deep learning theory review: An optimal control and dynamical systems perspective. 1rXiv:190. 2019.
Outongyi Lv, Bingxin Zhou, Jing Wang, Xiang Xiao, Weishu Zhao, and Lirong Zheng, A unified view on neural message passing with opinion dynamics for social networks. arXiv:231000122, 2023.
Thomas Markovich. QDC: Quantum diffusion convolution kernels on graphs arXiv:2307.1123 2023.
Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 2023.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In International ACM SIGIR Conference on Reseorch and Development in Information Retrieval, pp. 43 43-52, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163 2000.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228. IEEE, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go ncural: Higher-order graph noural networks. In AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Galileo Namala, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In International Workshop on Mining and Learning with Graphs, volume 8, pp. 1, 2012.
Khang Nguyen, Nong Minh Hien, Tan Minh Nguyen, Nguyen Duy Khuong, and Vinh Duc NGUYEN. DeepGRAND: Deep graph neural diffusion, 2023. URL http:s///ppaeeeeeeeeee///rrrr/rs CHPX
Hongbin Pei, Bingzhe Wei, Kevin Chen- Chaan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geometric graph convolutional networks. In International Conference on Learning Representations, 2019.
32

---

Published in Transactions on Machine Learning Research (02/2024)
Lawrence Perko. Differential equations and dynamical systems, volume 7. Springer Science & Business Media, 2013.
Pietro Perona and Jitendra. Malik. Scale-space and edge detection using anisotropic diffusion. IEEF Transactions on Pattern Analysis and Machine Intelligence, 12(7):629 639, 1990.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of ACM SIGKDD International Conference Knowledge Discovery and Dato Mining, pp- 701-710, 2014.
Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations. arXie:1911.07532, 2019.
Lev Semenovich Pontryagin. Mathematical theory of optimal processes. Routledge, 2018.
Constantine Pozrikidis. The fractional laplacion. CRC Press, 2018.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complez Networks, :2)xcn1,,,,, 2021.
T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein.
Graph-coupled oscillator networks. Tn International Conference on Machine Learning, pp. 18888-18909. PMLR, 2022.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXie:2303.1090) 2023a.
T Konstantin Rusch, Benjamin Paul Chamberlain, Michael W Mahoney, Michael M Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. In International Conference on Learning Representations, 2023b.
Lars Ruthotto and Eldad Haber. Deep neural networks motivated by partial differential equations. Journal of Mathematical Imaging and Vision, 62:352 364, 2020.
Prithviraj Sen, Galileo Namala, Mustala Bilgie, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data, AI Magazine, (9): 93, 2008.
Zhiqi Shao, Dai Shi, Andi Han, Yi Guo, Qibin Zhao, and Junbin Gao. Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond. wxXiu:230000266. 2023.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv:1811.05866 2018.
Dai Shi, Andi Han, Lequan Lin, Yi Guo, Zhiyong Wang, and Junbin Gao. Design your universe: A physics-informed agnostic method for enhancing graph neural networks. arXi::2401.14580, 2024.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics.
Machine Learning: Science and Technology, 2(2):021001, 2020.
Yang Song, Qiyu Kang, Sijie Wang, Kai Zhao, and Wee Peng Tay. On the robustness of graph neural diffusion topology perturbations. Advances in Neural Information Processing Systems, 35:6384-683 6396, 2022.
Julian Suk, Lorenzo Giusti, Tamir Hemo, Miguel Lopez, Konstantinos Barmpas, and Cristian Bodnar. Surfing on the neural sheaf. In NewrlPS Workshop on Symmetry and Geometry in Newral Representations, 2022.
Jeffrey Sutherland, Lee A O'brien, and Donald F Wcaver. Splino-fitting with genetic algorithm: A method for developing classification structure- activity relationships. Journal of Chemical Information and Computer Sciences, 43(6))1900-199)) 1915, 2003.
33

---

Published in Transactions on Machine Learning Research (02/2024)
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social inftuence analysis in large-scale networks. In ACM SIGKDD International Conference on Knowledge Discovery and Dala Mining, pp. 807-816, 2009.
Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahm: Autonorphism-based graph neural nets. Advances in Neural Information Processing Systems, 34:29922-29988 2021.
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 Conference on Learning Representations, 2022.
Zekun Tong, Yuxuan Liang, Changsheng Sun, David $ Rosenblum, and Andrew Lim. Directed graph convolutional network. ar WrXv:2004.13970 2020.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understauding over-squahhin and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
Csaba Toth, Darrick Lee, Celia Hacker, and Harald Oberhauser. Capturing graphs with hypo-elliptic diffusions. Advances Neural Information Processing Systems, 35:38803- 38817, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Iilia Polosukhin. Attention is all you need. Advances in Newral Information Processing Systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Ferdinand Verhulst. Nonlinear differential equations and dynamical systems. Springer Science & Business Media, 2006.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14:347 375, 2008.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip Yu. Heterogeneous graph attention network. In The World Wide Web Conference, pp. 2022-2030 2019.
Yuelin Wang, Kai Yi, Xinliang Liu, Yu Guang Wang, and Shi Jin. ACMP: Allen-Cahn message passing with attractive and repulsive forces for graph neural networks. In International Conference on Learning Representations, 2023.
Joseph L Watson David Juergens, Nathaniel Bennelt, Brian L Trippe, Jason Yim, Helen E Eisenach, Woody Ahern, Andrew J Borst, Robert Ragotte, Lukas F Milles, et al. De novo design of protein structure and function with REdiffusion. Nature, pp. 3, 2023.
Joachim Weickert et al. Anisotropic diffusion in image processing, volume Teubner Stuttgart, 1998.
Qitian Wu, Chenxiao Yang, Kaipeng Zeng, Fan Nie, Michael Bronstein, and Junchi Yan. Advective diffusion transformers for topological generalization in graph learning. arXiv:2310.06. 2023a.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. In International Conference on Learning Representations, 2023b.
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In International Conference on Machine Learning, pp. 10432-10441) PMLR, 2020.
Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for accurate and interpretable prediction of material properties. Physical Review Letters, 120(14):145301, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
34

---

Published in Transactions on Machine Learning Research (02/2024)
Kai Zhao, Qiyu Kang, Yang Song, Rui She, Sijie Wang, and Wee Peng Tay. Adversarial robustness in graph neural networks: A Hamiltonian approach. Advances in Neural Information Processing Systems, 2023a.
Kai Zhao, Qiyu Kang, Yang Song, Rui She, Sijie Wang, and Wee Peng Tay. Graph neural convection-diffusion with heterophily. In International Joint Conference Artificial Intelligence, 2023b.
Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang. Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning. In Newral Information Processing Systems Datasets and Benchmarks Track, 2021a.
Xuebin Zheng, Bingxin Zhou, Junbin Gao, Yuguang Wang, Pietro Lió, Ming Li, and Guido Montufar. How framelets enhance graph neural networks. In International Conference on Machine Learning, pp- 12761-12771. PMLR, 2021b.
Chunya Zou, Andi Han, Lequan Lin, Ming Li, and Junbin Gao. A simple yet effective Framelet-based graph neural network for directed graphs. IEEE Transactions on Artificial Intelligence, 2023.
35


Reviews:
[{"review_id": "egL7zF85Tc", "reviewer": "Reviewer_GiRx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n\n1. Overall, I found this to be a thorough survey for the stated goal and scope (GNN papers using a continuous dynamics lense). Am am not immediately aware of important missing papers\n2. The authors do a very good job summarizing the framework and each papers contributions. As a study guide, a launch-off point for a researcher wanting to find a footing or for a hypothetical student I would want to familarize with the topic, I would probably hand recommend this work. As far as I can tell, the summaries are also *correct*.\n3. I want to highlight the \"it is worth highlighting\" snippets and explanations of concepts like sheafs or brackets which make it possible to read the paper without being deeply familiar with concepts from continuous dynamics. In terms of exposition and flow, this paper does a  really good job that is worth stressing\n\nWeaknesses:\n\n1. It is difficult to motivate \"why should I care\" from the studied examples alone if not already familiar with the literature. This could be alleviated by discussing empirical results where available\n2. This is a personal trigger and borders on nitpicking, but the authors use the phrase \"systematic and comprehensive\" review. While I agree on the comprehensive, \"systematic\" has a meaning in science and would mean something checking at least *some* of e.g. the https://prisma-statement.org/ checklist. \n3. There are some *minor* english flaws (superflous the) but nothing that is more than a nitpick and can't be dealt with using a judciously applied LLM or a native lector (I can't downlplay this enough, but it's worth fixing for nicety)\n4. Finally, it *IS* a review, there is nothing new here, but it is sufficiently high quality that I find it valuable on its own", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper is a survey paper covering papers studying the evolution of features in various GNN architectures the lens of viewing the architectures as the discretization of  a specific set of continuous dynamics.\n  \n  It opens by introducing concepts from the analysis of continuous dynamics like Fick's law, mass conservation, divergence, Laplace operator etc. and then relate the layerwise feature dynamics of GCN to the Euler discretization of the graph-diffusion version of the heat diffusion kernel (using graph definitions of divergence and gradient) with parametrization and non-linearities added after the discretization as an opening example.  \n  \n  It then summarizes around 30 recent GNN papers which can explicitly made reference or can be analyized within the framework of  \n\n$\\left[ \\frac{\\delta X}{\\delta t},\\frac{\\delta^2 X}{\\delta t^2} \\right]\\coloneqq \\mathcal{F}_{\\mathcal{G}}\\left(X,\\nabla X\\right)$\n\nwith\n\n$\\mathcal{F}_{\\mathcal{G}}$\n\n being a spatial coupling function implied by parametrization of neural networks, $$\\frac{\\delta X}{\\delta t}$$ being the feature evolution throughout the network process (with layers being implied discretizations) and $$\\nabla X$$ being the graph gradient of features $$(\\nabla X)_{ij}\\coloneqq x_i -x_j$$ , which are taken to be functions belonging to Hilbert spaces $$L^2 \\left(\\mathcal{V}\\right),L^2 \\left(\\mathcal{E}\\right)$$ on vertices and nodes respectively.  \n  \n  Over 14 pages, the authors state the dynamics of each discussed paper and summarize the main innovation, implication or consideration that lead to the dynamic, as well as discussing the impact of parametrization and the discretization that converts the dynamics into a layerwise implementable neural network architecture (if not using NODEs).  \n  \n  The final 4 pages are then spent summarizing insights on Oversmoothing, Oversquashing, the expressive power of the dynamics in the face of heterophily and training stability, as well as discussing open research questions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please try to add a section showing the empirical (benchmark) impact of the different dynamics, where possible. I.e., it is worth adding a table summarizing what (if any) empirical evaluation was done (standard benchmark, custom experiments etc), discussing which papers are comparible to which others and then discussing those empirical insights to another.E.g., GRAFF compares against Sheaf,GRAND,GCN and others on relatively standard benchmarks as well as their custom experiment, and discussing their results together with other papers would make it easier for practitioners to decide which analysis line of research is worth digging deeper for them.\n2. Similarly, the computational and parameter impact of the different dynamics can be discussed in the same section, as well as that of the different backprop and training methods. I understand that this is partially a paper about understanding, but the practical impact and trainability of each method is worthwhile additional context.\n3. The other major change I'd request is checking at least some of the checkboxes of a systematic review, i.e.\n    - state the explicit sources of consideration, search strategy etc\n     - state the inclusion or exclusion criteria\n    - include a list of papers considered and excluded/included according to these criteria\n    - any other systematic review checklist item which makes sense\n\nSystematic reviews come from studies of intervention, and this paper focuses on theoretical insights of ML models, so one shouldn't go crazy on this. However, the 4 steps above and maybe more from the general systematic review field would be value-adds in my opinion, both for future work which seeks to extend it and to explain the authors perspective further (and serve as a jump off list for other researchers). If it can be automated, making all the excluded papers doi-links could be a boon for readers as well.", "broader_impact_concerns": "Review paper, none that I can see.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3zpVB0uD3M", "reviewer": "Reviewer_uQos", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Table 1 provides a nice and useful overview and well outlines the foundation for the structure of section 3 describing the listed methods in general in a nice and coherent manner.\n* The survey appears very comprehensive in terms of methodologies covered.\n* The survey is in general well-structured and written.\n\n\nWeaknesses:\n* Some parts of the survey reads somewhat mechanically as paper A did this, then paper B this, then paper C did this etc. which makes section 3 rather monotone in some places to read. Would it be possible to restructure parts of these sections and for instance provide all the diffusion formulations within a given framework in terms of their mathematical specifications and then discuss their strengths and limitations explicitly highlighting the different formulations and contrasting them to each other within the different dynamics formulations? \n\n* I was a bit disappointed reading section 6 which is rather short and given the otherwise comprehensive survey I would have liked to see this section expanded and further elaborated. I.e., could there also be future directions of research for instance in scaling these methodologies to large systems, enhance their reliability of the learned parameters, issues of explainability in how these modeling approaches work, methodologies for systematically benchmarking procedures and investigating what is the most adequate parameterization of graph neural dynamics? Overall, I feel this section is very short where I would here expect a much more elaborate discussion and further pointers to important open and future research directions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This comprehensive survey overviews the recent studies considering modeling GNN using continuous dynamics, i.e. neural diffusion and related approaches. In particular, the survey provides an introduction to the use of continuous dynamics in the context of GNN, a taxonomy of approaches and how continuous dynamics can address existing challenges in GNN in regards to oversmoothing, oversquashing, and heterophily. The survey ends up with future directions of research in the domain coined graph neural dynamics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(Optional, if possible) I suggest revising section 3 to within each methodological framework restructure each section and provide all the diffusion formulations within a given framework and then discuss their strengths and limitations explicitly highlighting the different formulations and contrasting them to each other within the different dynamics formulations where possible.\n\nProvide a table explaining all notations used in the paper to help the reader.\n\nI would suggest include in the manuscript illustrative examples throughout the exposition. This could be an example illustrating the effect using different diffusion specifications (highlighting key different methodologies in section 3), illustrating the merits and limitations of ODE solvers (section 4), Exemplifying oversmoothing, oversquashing and heterophily (section 5) and how these effects are addressed by adequate specifications as discussed. This could be accompanied by code and some illustrative synthetic reproducible examples that would be very helpful to the reader.\n\nMinor comments:\nThe paper is in need of a bit of proof reading, i.e.\n\nPage 4 top: \n“which applies channel wise” – it is unclear what channel wise refers to. Isn’t the elements of D scalar valued and positive in general and not just channel wise?\n“can be also derived” -> “can also be derived”\n\nPage 4 middle:\n“Many of them are directly adapted from the existing physical processes.” – what existing physical processes are here specifically referred to in particular in context of oscillations and geometric diffusion? Perhaps this sentence can be removed. Perhaps rephrase to:\n“Many of them are directly adapted from the existing physical processes as we will discuss below.”\n\nPage 5:\n“Blend further (Chamberlain et al., 2021b)” -> “Blend (Chamberlain et al., 2021b) further” \n\nPage 7 middle:\n“Similar in (Fu et al., 2022)” -> “Similar to (Fu et al., 2022)”\n\nPage 9 bottom:\n“that models the the average” -> “that models the average”\n\nPage 16 bottom:\n“Hence, node is effectively” -> “Hence, nodes are effectively”/ “Hence, each node is effectively”\n\nPage 18 middle:\n“the dynamics can adapt to datasets” -> “that the dynamics can adapt to datasets”\n\nPage 18 bottom:\n“by rewriting the the second-order” ->“by rewriting the second-order”\n\nPage 19 top:\n“similar idea has” -> “a similar idea has”/ “similar ideas have”\n\nPage 22 middle:\n“is gradient vanishing and exploding” -> “are vanishing and exploding gradients”", "broader_impact_concerns": "I see no concerns in regards to ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8BeC76C9HS", "reviewer": "Reviewer_1KdX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n*S1:* The survey is informative and covers a large number of different approaches and perspectives inspired by continuous dynamics. (I'm not an expert in this subarea, however, and was not previously familiar with most of the papers discussed here, so it's possible I'm unaware of additional relevant work, and my assessment might not be very reliable.)\n\n*S2:* The introduction is clear and gives useful context for the continuous-dynamics perspective. The methods are grouped based on their central ideas, and most of the specific methods discussed seem to be explained well.\n\n**Weaknesses:**\n\n*W1:* The paper makes some broad statements about GNNs and message passing being connected to continuous dynamics as a general. However, there are also many GNNs that don't seem to have a natural continuous dynamics interpretation. I think the paper could be a bit more careful about its claims here.\n\n*W2:* Some parts of Section 3 were still quite difficult for me to follow and seem to expect the reader to have a substantial background in continuous dynamics. I noticed multiple terms that were used without definitions or context. It also wasn't clear to me what the significance of each work was or how the method actually solves the problems it was motivated by. (Someone more familiar with the area might not have this problem, though.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission gives a survey of existing works that take a continuous-dynamics perspective on graph neural networks. The authors start by introducing continuous diffusion processes and graph convolutional networks, and discuss how GCNs can be viewed as discretizations of a particular continuous diffusion process. They then discuss a large number of existing works that extend this interpretation, most of which involve defining a more complex continuous dynamical system over graphs and then discretizing it to obtain a graph neural network method. They also briefly discuss numerical solution method, and a set of problems for GNN methods that some of the earlier methods address. Finally, they conclude with some open problems for continuous-dynamics GNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Qualify somewhat overbroad claims about GNNs\n\nThe paper currently frames all message-passing GNNs as being based on continuous diffusion, and has a number of broad statements about GNNs and message-passing, e.g. that message passing is \"intrinsically linked to a physical process known as heat diffusion\" (in the abstract) and \"Diffusion dynamics has been shown to underpin the design of message passing and graph convolutional networks\" (Section 3). This seems a bit overly simplistic to me. I agree many existing GNN architectures are related to heat diffusion (as discussed by Chamberlain et al., 2021) but it seems like a stretch to say that the message-passing technique is fundamentally linked to diffusion dynamics in general. For instance, it seems like some of the architectures in the [Message Passing Neural Networks framework (Gilmer et al. 2017)](https://proceedings.mlr.press/v70/gilmer17a) are not directly linked to any physical diffusion process.\n\nAlthough these other GNN architectures aren't the main focus of this survey, I think this work should avoid implying that every GNN is fundamentally based on diffusion ideas. I'd like to see this addressed before recommending acceptance.\n\n### Add context and definitions for some terms\n\nSection 3 seems to assume that the reader is already familiar with some terms that aren't directly defined. I think the survey would be more accessible if it acknowledged that readers may not know these terms, and either summarized their definitions or explicitly referred to an existing definition. (This isn't the case for all terms; there are other terms the paper does give a good definition or summary of.)\n\nSpecific examples I noticed:\n\n- \"Oversmoothing\" is referenced on page 2 and throughout section 3, but not actually defined or cited until Section 5. (More generally, I think it would be useful to give a brief description of the four types of problem referred to in Table 1 before the main content of section 3, instead of waiting until section 5.)\n- On page 3, it's not clear what \"a flux\" is or what it means for it to exist.\n- Page 6 doesn't explain what a \"mean-curvature flow\" is.\n- Page 7 says that p-Laplacian diffusion corresponds to a \"p-Dirichlet energy\" but doesn't explain what that is.\n- The \"Quantum diffusion kernel\" has a few terms like this:\n  - What is a \"system without a potential\"? What kind of potential are we talking about?\n  - What does it mean to be \"equally delocalized\"?\n  - I also didn't understand how quantum interference occurs or how it leads to non-local message passing.\n- The hypo-elliptic diffusion section uses some undefined algebraic terms like \"an algebra lifting\" and the $\\mathbf{u}^{\\otimes m}$ notation without explaining what they mean.\n\nGiven the breadth of the different methods covered, it's likely difficult to fully explain all of the terms used, but I think that at least in these cases readers could benefit from more context.\n\n### Other minor specific suggestions for improvement\n\n- The second paragraph of the introduction makes a number of statements about GNN performance degradation without citing any examples or analyses of this degradation.\n- On page 3, shouldn't it just be \"Fick's law\" and not \"the Fick's law\"?\n- I was a bit confused by the Beltrami flow discussion \"Anisotropic diffusion\" section on page 6. Does the Song et al Beltrami flow build on the BLEND flow or are they independent uses of Beltrami flows?\n- On page 14, I didn't follow the claim \"graphs usually possess more intricate geometries and viewed as discrete realization of general topological spaces\". What does this mean?\n- On page 15: Should the \"over the domain $\\omega$\" be a capital $\\Omega$?\n- On page 20: Typo, \"converses\" instead of \"conserves\"\n- On page 22: \"Such\" should not be capitalized", "broader_impact_concerns": "I don't have any broader impact concerns for this submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers were of the opinion that for the scope of the paper, the survey was thorough. All reviewers indicated they would recommend the paper to newcomers in the field. Therefore the recommendation is to extend the survey certification for this paper.
Decision: Accept (poster)