Beltrami Flow and Neural Diffusion on Graphs
Authors: Benjamin Paul Chamberlain
James Rowbottom
Davide Eynard
Francesco Di Giovanni
Xiaowen Dong
Michael M. Bronstein
Venue: NeurIPS 2021 Poster (2021)
Keywords: Geometric Deep Learning
Graph Neural Network
Diffusion

Abstract: We propose a novel class of graph neural networks based on the discretized Beltrami flow, a non-Euclidean diffusion PDE. 
In our model, node features are supplemented with  positional encodings derived from the graph topology and jointly evolved by the Beltrami flow,  producing simultaneously continuous feature learning, topology evolution. 
The resulting model generalizes many popular graph neural networks and achieves state-of-the-art results on several benchmarks. 

Beltrami Flow and Neural Diffusion on Graphs
Benjamin P. Chamberlain'
James Rowbottom Twitter Inc.
Davide Eynard Twitter Inc.
Twitter Inc. bchamberlain @twitter.com
Francesco Di Giovanni Twitter Inc.
Xiaowen Dong University of Oxford
Michael M. Bronstein Twitter Inc. and Imperial College London
Abstract
We propose a novel class of graph neural networks based on the discretised Beltrami flow, non-Euclidean diffusion PDE. In our model, node features are supplemented with positional encodings derived from the graph topology and jointly evolved by the Beltrami flow, producing simultancously continuous feature learning and topology evolution. The resulting model generalises many popular graph neural networks and achieves state-of of-the-at results on several benchmarks.
Introduction
The majority of graph neural networks (GNNs) are based on the message passing paradigm [30]. wherein node features are learned by means of a non-linear propagation on the graph. Multiple recent works have pointed the limitations of the message passing approach. These include; limited expressive power 80 95
9 77 the related oversmoothing problem [60, 62] and the bottleneck
phenomena 1 93 which render such approaches inefficient, especially deep GNNs. Multiple alternatives have been proposed, among which are higher-order methods [54] 7 and decoupling
the propagation and input graphs by modifying the topology, often referred to as graph rewiring. Topological modifications can take different forms such as graph sampling [2), KNN 43,, using
the complete graph [86, [] latent graph learning [89 36), or multi-hop filters 92 73 However,
there is no agreement in the literature when and how to modify the graph, and single principled framework for doing so.
A somewhat underappreciated fact is that GNNs are intimately related to diffusion equations [6] a connection that was exploited in the early work of Scarselli et al. (76). Diffusion PDEs have been historically important in computer graphics [83] [1 [1 (64), computer vision [13 18 6 and
image processing (65] 82 90
85 26 [2], where they created an entire trend of variational and
PDE-based approaches. In machine learning and data science, diffusion equations underpin such popular manifold learning methods as eigenmaps (5) and diffusion maps [20), as well as the family of
PageRank algorithms 663
14. In deep learning, differential equations used models of neural
networks [6
25
94
98
and for physics-informee informed learning 72
81 47).
Main contributions In this paper, we propose a novel class of GNNs based on the discretised non-Euclidean diffusion PDE in joint positional and feature space, inspired by the Beltrami flow [82 used two decades ago in the image processing literature for lagge-preserving image denoising. We show that the discretisation of the spatial component of the Beltrami flow offers principled view on positional encoding and graph rewiring, whereas the discretisation of the temporal component can replace GNN layers with more flexible adaptive numerical schemes. Based on this model, we introduce Beltrami Neural Diffusson (BLEND) that generalises a broad range of GNN architectures and shows thtte- performance many popular benchmarks. In broader perspective, our
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

When dealing with images, the evolution of the first two components of (æ1, 22) = u is a nuisance amounting the reparamctrisation of the manifold and can be ignored. For grayscale images (the approach explores new tools from PDEs and differential geometry that are less well known in the graph ML community.
Background
Beltrami flow Kimmel et al. [40 82 (39 considered images as 2-manifolds (parametric surfaces)
(,.g) embedded in some larger ambient space z(u) (u, ax(u)) S I2+2 where 2 0 is a scaling factor, u = -uu, u2) are the 2D positional coordinates of the pixels, and x are the dimensional colour feature coordinates (with d 1 or 3 for grayscale or RGB images, or d = k² when using k x patches as features [12). In these works, the image is evolved along the gradient flow of a functional Siz.g g] called the Polyakov action 168), which roughly measures the smoothness of the embedding] For images embedded Euclidean space with the functional minimised with respect both the embedding and the metric g. one obtains the following PDE:
Ūz(u, 1) Ac
z(u, 0) z(u), 2 0,
(1)
aL
and boundary conditions appropriate. Here ÅG is the Laplace- Laplace-Beitramtt operator. the Laplacian operator induced on Σ by the Euclidean space we embed the image into. Namely, the embedding of the manifold allows to pull-back the Euclidean distance structure the image: the distance between two nearby points u and u + du is givenby
de = du G(u)du duî + dup + a Σ dz
where G I I+ (Vxx()() Vv, is a 2 x 2 matrix called the Riemannian metric. The fact that the distance is combination of the positional component (distance between pixels in the plane, I|u - u'll) and the colour component (distance between the colours of the pixels, ||x(u) x(u')l)) is crucial as allows sige-preeerving image diffusion.
case when d and z = (w1, U2, r)), this is done by projection along the dimension 23, in which case the Beltrami flow takes the form of an inhomogeneous diffusion equation of xr
0x(utt)
div Vo(u,t)
t t 0.
(3)
Ot
/detG(u,t)
VdetG(u.tt)
The diffusivity
(4)
delG
determining the speed of difffusion at each point, can be interpreted as an edge indicator: diffusion weak across edges where Vz|| > 1. The result is an adap- tive diffusion (65) popular in image processing due to its ability to denoise images while preserving their edges. For cases with d > 1 (multiple colour channels), equa- tion (3) is applied each channel separately: however, the metric G couples the channels, which results in their gradients becoming aligned (38
Special cases In the limit case = 0, equation (3) becomes the simple homogeneous isotropic diffusion 8 á = div(Vx) = Ax, where A = au?
Figure 1: Two interpretations of the Bel- trami flow: position-dependeee bilateral kernel (top) and a Gaussian passed on the manifold (bottom).
8²
8²
is the
Dug
standard Euclidean Laplacian operator. The solution is
'Epplictll, by minimising the functional with respect to the embedding one finds Euler-Lagrape (EL) equations that can be used to dictate the evolution process of the embedding itself.

---

given in closed form as the convolution of the initial image and a Gaussian kernel with time -ime-dependent variance,
x x(u, t) xuu, 0)
1 -lull
Ilull//4
(5)
(ATl)d/2
and be considered simple linear low-pass filtering. In the limit co, the image becomes constant and equal to the average colour
Another interpretation of the Beltrami flow is passing Gaussian on the manifold (see Figure bottom), which can locally be expressed as non-linear filtering with the bilateral kernel [85 dependent on the joint positional and colour distance (Figure top).
<u 1) (ATt)d/2 JRa
x(v, 0)e -u-v [2AM |x x(vv00) dv.
(6)
For 0, the bilateral filter
6 reduces simple convolution with time-dependent Gaussian.
Discrete Beltrami flow on graphs
We now develop the analogy of Beltrami flow for graphs. We consider a graph to discretisation of continuous structure (manifold), and show that the evolution of the feature coordinates in time amounts to message passing layers in GNNs, whereas the evolution of the positional coordinates amounts to graph rewiring, which is used in some GNN architectures.
3.1 Graph Beltrami flow
Let G (V = n., E) be an undirected graph, where V and & denote node and edge sets, respectively. We further assume node-wise d-dimensional features x; E RRd for i = 1,.... n. Denote by z, (u, ox,) the embedding of the graph in a joint space C x Rd. where C is -immensiia space with a metric de representing the node coordinates (for simplicity, we will assume unless otherwise stated). We refer to u, and z; as the positional, feature and joint coordinates of node respectively, and arrange them into the matrices U, X, and Z, of sizes n x d', n and x (d' + d).
Rd
For images, Beltrami flow amounts evolving the embedding along div(a(z) Vz). with a diffusivity map
B Thus, we consider the graph Beltrami flow to be the discrete diffusion equation
(t, = a() - (t)
(0) = 2;; i == 1. n; t t 0.
Öt J'(.))E
We motivate definition follows: gij Zj and d: Eya.ne Bij are the discrete analogies of the gradient Vz and divergence div(g), both with respect to a graph (V, E') that can be interpreted as the numerical stencil for the discretisation of the continuous Saplace-Beltrami operator in 3 Note that E' can be different from the input (referred to as 'rewiring'). As discussed in rewiring). Alternatively, the positional coordinates of the nodes can be used to define a new graph topology either with E(U) (i,,j) de du(u., uy) < r}. for some radius r > O, or using k nearest neighbours. This new rewiring is precomputed using the input positional coordinates (i.e., = {((())) or updated throughout the diffusion (i.e., (t) {(U(t))) Therefore, (7) can be compactly rewritten
Section 3.3 most GNNs use E' = E (input graph is used for diffusion,
Öz div Vz(
The function a is the diffusivity controlling the diffusion strength between nodes and j and is assumed to be normalised: Ejt,hee a(z;, 2,) 1. The dependence of the diffusivity the
2 Asssumnng appropriate boundary conditions.
'Note that in equation (3) the diffusivity function coincides with (det(Gi(u -1, Similarly to 82 Section 4.2] we have neglected the extra term 1/a appearing B

---

embedding matches the smooth PDE analysed in g.g. 82 Section 4.2] and is consistent with the form of attention mechanism used in e.g. 88 [6]. matrix-form, we can also rewrite 7
U(),, 8 8 (() = (A) (()) - 1) (U(t).
(8)
U()) = U: (()) aX; t t 0,
where we emphasise the evolution of both the positional and feature components, coupled through the matrix-valued function A
a.y(t) a( ((),())x((0))
xx)))) (i. E E(U()))
else.
representing the diffusivity. The graph Beltrami flow produces an evolution of the joint positional and feature coordinates, ((t) = (t)),, X()). In Section 3.3 we will show how the evolution of the feature coordinates (t) results in feature diffusion or message passing on the graph, the core of GNNs. As noted in Section 2 in the smooth case the Beltrami flow obtained as gradient flow of an energy functional when minimised with respect to both the embedding and the metric on the surface (an image). When the embedding takes values in the Euclidean space, this leads equations of the form 3) with no channel-mixing and an exact form of the diffusivity determined by the pull-back G of the Euclidean metric. To further motivate our approach, it tempting to investigate whether similar conclusion can be attained here. Although in the discrete case the operation of pull-back is not well-defined, we are able to derive that the gradient flow of a modified graph Dirichlet energy gives rise to an equation of the form (7). We note though that the gradient flow does not recover the exact form of the diffusivity implemented in this paper. This not a limitation of the theory and should be expected: by requiring the gradient flow to avoid thannel-mixing and imitate the image analogy in [82] and by inducing a discrete pull-back condition, we are imposing constraints on the problem. We leave the theoretical implications for future work and refer to the Supplementary Materials for more thorough discussion, including definitions and proofs.
Theorem 1. Under structural assumptions on the diffusivity, graph Beltrami flow is the gradient flow of the discrete Polyakov functional..
3.2 Numerical solvers
Explicit vs implicit schemes by replacing the continuous time derivative with forward time difference:
Equation 7 is solved numerically, which in the simplest case is done
(k++) 1) (k)
Σ
2 (k)
(M)
(K)
2 (R)
T
Here A denotes the discrete time index (iteration) and 7 is the time step (discretisation parameter). Rewriting (9) compactly in matrix -vector form with T = 1 leads to the explicit Euler scheme:
Z (k+1) = (A - I)Z(k) (k) = Q (())
(10)
(R) where di =azz (k) (k) and the matrix (8) (diffusion operator) is given by
au
(k)
i i=j
(R)
B(GD)E
(i.j) E ((U())
ig
otherwise
The solution to the diffusion equation is computed by applying scheme TOp multiple times in sequence, starting from some initial (0)) It is 'explicit' because the update Z z(++) is done directly by the application of the diffusion operator Q(k) on ( (as opposed to implicit schemes of the form (k) Q ( arising from backward time differences that require inversion of the diffusion operator (91))
Multi-step and adaptive schemes Higher-order approximation of temporal derivatives amount to using intermediate fractional steps, which are then linearly combined. Runge-Kutte (RK) [74] [4], ubiquitously used in numerical analysis, is classical family of explicit numerical schemes, including Fuler as particular case. The Farmand-Prinee (DOPRI) 24 is an RK method based on fifth and fourth-order approximations, the difference between which is used as an error estimate guiding the time step size [78).

---

Adaptive spatial discretisation and rewiring Many numerical PDE solvers also employ adaptive spatial discretisation. The choice of the stencil (mesh) for spatial derivatives is done based on the character of the solution at these points; in the simulation of phenomena such as shock waves it is often desired use denser sampling in the respective regions of the domain, which can change in time. A class of techniques for adaptive rewiring of the spatial derivatives are known as Moving Mesh (MM) methods [33]. Interpreting the graph E in (7) as the numerical stencil for the discretisation of the continuous Laplace-Beltrane operator in 3 can regard rewiring form of MM.
3.3 Relation to graph neural networks
Equation (9) has the structure of many GNN architectures of the "attentional" type [10.. where the discrete time index & corresponds to a (convolutional or attentional) layer of the GNN and multiple diffusion iterations amount to deep GNN, In the diffusion formalism, the time parameter acts as a continuous analogy of the layers, in the spirit of neural differential equations [19]. Typical GNNs amount to explicit single-step (Euler) discretisation schemes, whereas our continuous interpretation can exploit more efficient numerical schemes.
GNNs as instances of graph Beltrami flow The graph Beltrami framework leads to family of graph neural networks that generalise many popular architectures (see Table I For example, GAT [88] can be obtained as a particular setting of our framework where the input graph is fixed (E' E) and only the feature coordinates X are evolved. Equation (TO) in this case becomes
(++1)
(k)
+ T
=a j.(K,)EEE
X
(1)
(x) (k)
(8)
(11)
and corresponds to the update formula of GAT with a residual connection and the assumption of no non-linearity between the layers. The role of the diffusivity is played by a learnable parametric attention function, which is generally time-dependent: alz,") 3 (k) k). This results in separate attention parameters per layer k which can be learned independently. Our intentionally simplistic choice of a fime-independent attention function amounts to parameter sharing across layers. We will show in Section 5. this leads a smaller model that less likely overfit.
Another popular architecture MoNet [57] uses linear diffusion of the features with weights dependent on the structure of the graph expressed as "pseudo-coordiaate which can be cast as attention of the form a( u, uy), Transformers [87] can be interpreted as feature diffusion on a fixed complete graph with E V x y [1O]. Positional encoding (used in Transformers well in several recent GNN architectures 9 (27) amounts to attention dependent on both X and U, which allows the diffusion to adapt the local structure of the graph; importantly, the positional coordinates U are precomputed. Similarly, DeepSets 997 and PointNet [70] architectures can be interpreted as GNNs applied on a graph with no edges (E' 0). where each node is treated independently of the others [10. DIGL [43] performs graph rewiring as a pre-processing step using personalised page rank as positional coordinates, which are then fixed and not evolved. In the point cloud methods, DGCNN [89] and
DGM [36]. the graph is constructed based on the feature coordinates X and rewired adaptively (in our notation, 8 (t))..)
Method
Evolution
Diffusivity
Graph (Y,,²)
Discretisation
ChebNet
Features X
Fixed azy
Fixed E
Explicit lixed step Explicit fixed step Explicit fixed step Explicit fixed step Explicit fixed step Explicit fixed step Explicit fixed step
GAT
Features X
a(x,, Xy
Fixed
MoNet
Features X
a(u,, Uz)
Fixed
Transformer
Features X
a((u: xx). x:). (u),x;)
Fixed x
DeepSet/PointNet
Features X
a(x,)
Fixed 0
DIGL'
Features X
a(x,,
Xy)
Fixed E(U)
DGCNN/DGM"
Features X
X+)
Adaptive {(X)
Beltrami
Positions U
al(n, X.), (n),
Adaptive {(U)
Explicit adaptive step/ Implicit
+Features X
Table 1: GNN architectures interpreted particular instances of our framework. AAttentional variant.
Graph rewiring Multiple authors have recently argued in favor of decoupling the input graph from the graph used for diffusion. Such rewiring can take the form of graph sampling (22 to address scalability issues, data denoising 43), removal of information bottlenecks (1. or larger multi-hop filters 733. The graph construction can also be made differentiable and task-specific rewiring can
5

---

be learned [89 36]. The statement of Klicpera et al. [43] that 'diffusion improves graph learning', leading to the eponymous paradigm (DIGL), can be understood as form of diffusion on the graph connectivity independent of the features. Specifically, the authors used as node positional encoding the Personalised PageRank (PPR), which can be interpreted as the steady-state a diffusion process
UPPR -1-3333
A RW (1 (1 3ARW)"1, 0 < 3 < 1,
(12)
120
where ARW is the random walk graph Laplacian and 3 E (0,1) is parameter such that 1 represents the restart probability. The resulting positional encoding dimension = n can be used to rewire the graph by KNN sampling, which corresponds using E E(UPPR) in our framework.
Numerical schemes All the aforementioned GNN architectures can be seen as an explicit discreti- sation of equation 7 with fixed step size. On the other hand, our continuous diffusion framework offers an additional advantage of employing more efficient numerical schemes with adaptive step size. Graph rewiring of the form E" E()()) can be interpreted as adaptive spatial discretisation (moving mesh method).
X
3.4 Extensions
d
Non-Euu En--Edullddn geometry There are multiple theoreti- cal and empirical arguments (52 17 in favor of using hy- perbolic spaces to represent real-life 'small-world" graphs (in particular, scale-free networks can be obtained ANN graphs in such spaces [8). Our framework allows using
feature space
non-Eude -un-Euclidean metric de for the positional coordinates U (Figure2), 2). In Section we show that hyperbolic positional encodings allow for significant reduction in model size with only a marginal degradation of performance.
du
hyperbolic space
Time-dependent diffusivity The diffusivity function a which we assumed time-independent and which lead to parameter sharing across layers (i.e.. updates of the form (k++1 ((Z(k) (k) can be made time-dependent of the form ( Q(Z(*,, g (k), where 0 and ((k) denote shared and layer-depender parameters, respectively.
Figure 2: Graph Beltrami flow with hy- perbolic positional coordinates.
Onsager diffusion we noted, the Beltrami flow diffuses each channel separately. more general variant of diffusion allowing for feature mixing is the Onsager diffussin [61] of the form
dR Zt) = (()))))()t)())))))))))))) where the matrix-valued function W acts across the channels. GCN can be regarded particular setting thereof, with update of the form ( (x
42
MPNNs Finally, we note that the Beltrami flow amounts to linear aggregation with non-linear coefficients, or the 'attentional" flavor of GNNs [0O. The more general message passing flavor (30 is possible using a generic non-linear equation of the form de Z(t) ve (Z())..
8
4 BLEND: Beltrami Neural Diffusion
Beltrami Neural Diffusion (BLEND) is novel class of graph neural network architectures derived from the graph Beltrami framework. We assume an input graph G = (V,E) with n nodes and matrix X We further assume d' d'-dimeesionnl
d-dimensional node-wise features represented positional encoding Un of the graph nodes. BLEND architectures implement a learnable joint diffusion process of U and X and runs it for time T, to produce an output node embeddings Y.
Z(T) Z(0) + /
OZ(t) Ot dt
Z(0) (m(U,,, (X..))
Y =ZT()T))
where 9, 1/ are learnable positional and feature encoders and { is a learnable decoder (possibly changing the output dimensions). Here the in Equations 2 and (8) is absorbed by vo and made

---

learnable. 2210) is given by the graph Beltrami flow equation 8 where the diffusivity function o (attention) a is also learnable. The choice of attention function depends on the geometry of the positional encoding and for Euclidean encodings we find the scaled dot product attention [86 performs well, in which case
(Waz,) Wozz
alz Zz) = softmax
(13)
du
where Wx k and We are learned matrices, and da hyperparameter.
5 Experimental results
In this section, we compare the proposed Beltrami framework to popular GNN architectures on standard node classification benchmarks and provide detailed study of the choice of the posi- tional encoding space. Additional experiments and implementation details, including runtimes and hyperparameter tuning given in the Supplementary Materials. The code is available https: //ttt/b............ www/twwtttteeeeeeeeeeeccocw res.ttteeerrreeeeeeeeeee perrphhneuura-- neural-pus
Datasets In our experiments,
the following datasets: Cora [56). Citeseer 777,, Pubmed (58).
CoauthorCS [79], Amazon, Computer, and Photo [55]. and DGB-arxiv [35] Since many works using
the first three datasets rely on the Planetoid splits [96), we included them Table
2 together with
more robust evaluation on 100 random splits with 20 random initialisations
79
Baselines compare to following GNN architectures: GCN
GAT
88
MoNet
and GraphSAGE [32] and recent ODE-based GNN models: CGNN 194
GDE
67
GODE
98
and two versions of LanczosNet [49). We use two variants of our method: using fixed input graph (BLEND) and using kNN graph in the positional coordinates (BLEND-Knn)
5.1 Node Classification
Method GCN
CORA
CiteSeer
PubMed
81.9:00.8
69,510.9
79.0=
In these experiments, we followed the method- ology of [79] using 20 random weight initialisa- tions for datasets with fixed Planctoid splits and 100 random splits otherwise. Where available, results from [79] are reported. Hyperparameters with the highest validation accuracy were cho- sen and results are reported on a test set that is used only once. Hyperparameter search used Ray Tune (50) with a thousand random trials us- ing an asynchronous hyperband scheduler with a grace period and half life of ten epochs. The code to reproduce our results is included with the submission and will be released publicly fol- lowing the review process. Experiments ran on AWS p2.8xlarge machines, each with Tesla V100-SXM2 GPUs.
GAT
82.81005
71.0+0.6
77.0=11.3
MoNer
82.2+0.7
70.0
77.7-0.6
GS-maxpool
77.41100
67.011.0
76.6-0.8
Lanczos
79.5+1..
66.211.9
78.3=003
AdaLanczos
80.4+1.1
68.7+1.0
78.1=0.4
CGNN
81.7+00.7
68.1+1.2
80.2-0.3
GDE
83.8+0055
72.5++0.5
79.9=0.3
GODE
83.3-0.33
72.410.6
80.1
BLEND
84,2+0.6
74.4+0.7
80.7+ 0.7
BLEND-ENN
83.1+-0.8
73.3++0.9
81.5=005
Table 2: Performance (test accuracy=sstd) of dif- ferent GNN models using Planetoid splits.
Implementation details For datasets excepting ogb-arxiv, adaptive explicit Dormand-Prince scheme was used as the numerical solver; for ogb-arxiv, we used the Runge-Kutt Kutta method. For the two smallest datasets (Cora and Citeseer) we performed direct backpropagation through each step of the numerical integrator. For the larger datasets, to reduce memory complexity, we Pontryagin's 's maximum principle to propagate gradients backwards time [69]. For the larger datasets, kinetic energy and Jacobian regularisation [28] 37 was employed. The regularisation ensures the learned dynamics is well-conditioned and easily solvable by a numeric solver, which reduced training time. We constant initialisation for the attention weights, Wx. W training starts from a well-conditioned system that induces small regularisation penalty terms (28.
The space complexity of BLEND is dominated by evaluating attention 13 over edges and is (( d')) where E' is the edge set following rewiring and d is dimension of features and d' the dimension of positional encoding. The runtime complexity is O(E' +dd))) d')) + Ey), split
7

---

Method
CORA
CiteSeer
PubMed
Coauthor CS
Computer
Photo
ogb-arxiv
GCN
11.
71.9 11.9
77.8
91.1
82.6=2.4
91.2=1122
71.74=0.29
GAT
81.
71.4119
78.742.3
90.5:1.66
78.0#19
85.74:20
73.01=0.19"
GAT-ppr
81.6+00.3
68.5+0.2
76.7=0.3
91.3+0.1
85,4=0.3
90.9=0.3
MoNet
11.3
71.2:1.00
78.612..3
90.810.6
83,512.2
91.2:12.3
GS-mean
79.217.7
71.6119
77.412.2
91.312.8
82.4
91.4111.
71.49-0.27
GS-maxpool
76.6119
67.5
76.142.3
85.0+1.1
90.411..
CGNN
81.411.6
66.9+188
66,614444
92.3+0022
80.3+2.0
91.4=115
58.70=2.50
GDE
78.7+22.2
71.8+1.1
73.943.7
91.6++011
82,9=0.6
92.4+2.0
56.66=10.9
BLEND 84,810099
75.9113
79.51114
92,910.2
8.69
92.910.6
72.5610.1
BLEND-RNN
82.510.99
73.40..5
80.910.77
92.310.1
86.71006
93.5:10.3
Table 3: Performance (test accuracy of different GNN models using random splits. *OGB GAT reference has 1.5M parameters
70K. BLEND-KNN pre-processes the graph using the DIGL methodology [43 (Section 3.3). which constructs an n-dimensional representation of each node (an n-by-n matrix), then sparsifies into a KNN graph. The ogb-arxiv datasct has >150K nodes and goes OOM. This is not a limitation of BLEND, but that of DIGL. Other forms of initial rewiring are possible, but we chose to compare with DIGL (arguably the most popular graph rewiring) and so this result is missing
between the forward and backward pass and can be dominated by either depending on the number of function evaluations (E,, Ey).
Tables summarise the results of our experiments. BLEND outperforms other GNNs in most of the experiments, showing oate-of-tthearr results on some datasets. Another important point to note is that compared GNNs use different sets of parameters per layer, whereas in BLEND, due to choice of time-independent attention, parameters are shared. This results in significantly fewer parameters: for comparison, the OGB versions of GCN, SAGE and GAT used in the ogb-arxiv experiment require 143K, 219K and 1.63M parameters respectively, compared to only 70K in BLEND.
100
5.2 Positional encoding
w. POS
BLEND positional
In the second experiment, we in- vestigated the impact of the posi- tional encodings and vary the di- mensionality and underlying ge-
95
92.962.9
92. 32.3
90.3
90
86.9
Accuracy
ometry, in order to showcase the flexibility of our framework.
64.8
83.7
85
B2.6
Figure B shows that for all datasets BLEND is superior to a Euclidean model where posi- tional encodings are not used, which corresponds to Z (BLEND w/o positional in Fig- ure 3) and a version of GAT where attention over concate- nation of the same positional en- codings used in BLEND and the features. The only exception is
79.5
78.8
75.9
76.8
75
70
Cora
CiteSeer
PubMed
Coauthor C5 Computer
Photo
Datasets
Figure 3: An ablation study showing BLEND with and without positional encodings as well as GAT, the most similar conventional GNN with positional encodings added CoathorCS, where the performance without positional encodings is unchanged.
We experimented with three forms positional encoding: DIGL PPR embeddings of dimension n 43 DeepWalk embeddings [66] of dimensions 16-256, and hyperbolic embeddings in the Poincare
ball [1] 59] of dimension 2-16. Positional encodings are calculated as a preprocessing step and input the U coordinates to BLEND. We caleulated DeepWalk node embeddings using Py Torch Geometric's Node2Vec implementation with parameters = 1, q = 1, context size 20, and 16 walks per node. We trained with walk length ranging between 40 and 120 and took the embeddings with the highest accuracy for the link prediction task. Shallow hyperbolic embeddings were generated using the HGCN [77 implementation with the default parameters provided by the authors.
Figure (left) compares the performance of the best model using DIGL n-dimensional positional encodings against the best performing di d-dimensional hyperbolic positional encodings with d tuned over the range 2-16. The average performance with DIGL positional encodings is 85.48, compared to 85.28 for hyperbolic encodings. Only in one case the DIGL encodings outperform the best hyperbolic

---

100
0.95
92.5
0.90
90
86.9
0.55
84. 984.2
0.50
70579.6
0.75
75.975.9
75
Citeseer
Photo
Cora
CteSeer
PubMed
Coauthor Computer
Photo
HYP2
HYPE HYP15 Di664 DWL25DW256 GDC Postional ombodding typc and siss
Dataset
Figure 4: Left: performance comparison between Euclidean and hyperbolic positional embeddings. Right: results of positional embeddings ablation. Hyperbolic or Euclidean embeddings with d' 16 allow to obtain performances comparable to euclidean embeddings with d' = 16.
encodings. Figure 1 (right) show the change in performance with the dimension d' of the positional encoding using fixed hyperparameter configuration. As expected, observe monotonic increase in performance as function of d'. Importantly most of the performance is captured by either 16 dimensional hyperbolic or positional encodings, with small additional margin gained for going up to d' n, which is impractical for larger graphs.
5.3 Additional ablations
In addition to studying the affect of posi- tional encodings we performed ablation studies on the step size used in the integra- tor as well as different forms of attention.
60
In Figure 5 we studied the affect of chang- ing the step size of the integrator using the explicit Euler method with fixed terminal time set to be the optimal terminal time. The left hand side of the figure shows the performance using the adaptive stepsize Dopri5 for comparison. Dopri5 gives the most consistent performance and is best if three the six datasets. Details of addi- tional attention functions and their relative performance can be found in the Supplementary Material.
30
40
30
CoautharCS
Citeseer
Computers
20
Dopri5
0.25
0.5
Stepsize
Figure 5: step size against accurcy for explicit Fuler compared to the adaptive dopri5.
Related work
Image processing, computer vision, and graphics. Following the Perona-Malik scheme [65]. PDE-based approaches flourished in the 1990s with multiple versions of anisotropic (90] and non- Euclidean [82] diffusion used primarily for image denoising. The realisation of these ideas in the form of nonlinear filters [85] [2] was adopted in the industry. PDE-based methods were also used for low-level vision tasks including inpainting
[6] and image segmentation [33 18]. In computer graphics, fundamental solutions (theat kernels') ) of diffusion equations were used shape descriptors 83]. The closed-form expression of such solutions using the Laplace- Beltrami operator served as inspiration for some of the early approaches for GNNs 34
45
Neural differential equations The interpretation of neural networks as discretised differential equations ('neural ODEs") 19 was an influential recent result with multiple follow-up works 25
53 46 In deep learning on graphs, this mindset has been applied to GNN architectures and continuous message passing (94). Continuous GNNs were also explored in [31 who, similarly to (76), addressed the solutions of fixed point equations. Ordinary Differential Equations
28

---

on Graph Networks (GODE) approach the problem using the technique of invertible ResNets.
Finally, 75 used graph-based ODEs to generate physies simulations.
Physics-inspired learning Solving PDEs with deep learning has been explored by 722 Neural networks appeared in [47] to accelerate PDE solvers with applications in the physical sciences. These have been applied to problems where the PDE can be described on graph [48]. []] consider the problem of predicting fluid flow and use a PDE inside a GNN. These approaches differ from ours in that they solve a given PDE, whereas we use the notion of discretising PDEs principle to understand and design GNNs.
Neural ODEs graphs The most similar work to this is GRAND [16] of which BLEND can be considered a non-Euclidean extension. In addition there are several other works that apply the neural ODE framework to graphs. In GDE [67], GODE [98] and CGNN (94), the goal is to adapt neural ordinary differential equations to graphs. In contrast, we consider non- -ue-Eucli partial differential equations and regard GNNs as particular instances of their discretisation (both spatial and temporal). We can naturally use spaces with any metric, in particular, extending recent works on hyperbolic graph embeddings. None of the previous techniques explore the link differential geometry. More specifically, GDE, GODE, and CGNN consider Neural ODEs of the canonical form de f(z, t, 0) where f is a graph neural network (GODE), the message passing component of a GNN (CGNN), or restricting f to be layers of bijective functions graphs (GDE). Furthermore, in CGNN only ODEs with closed form solutions are considered. [75] on the other hand is quite distinct as they are not concerned with GNN design and instead use graph-based ODEs to generate physics simulations.
7 Conclusion
We developed a new class of graph neural networks based on the discretisation of a -unluulidenn diffusion PDE called Beltrami flow. We represent the graph structure and node features as manifold in joint continuous space, whose evolution by a parametric diffusion PDE (driven by the downstream learning task) gives rise to feature learning, positional encoding, and possibly also graph rewiring. Our experimental results show very good performance on popular benchmarks with a small fraction of parameters used by other GNN models. Perhaps most importantly, our framework establishes important links between GNNs, differential geometry, and PDEs fields with rich history and profound results that in our opinion are still insufficiently explored in the graph ML community.
Future directions While show that our framework generalises many popular GNN architectures we seck to use the graph as a numerical representation of an underlying continuous space. This view of the graph as approximation of continuous latent structure common paradigm of manifold learning 84 5 20 and network geometry []. If adopted in graph ML, this mindset offers rigorous mathematical framework for formalising and generalising some of the recent trends in the field, including the departure from the input graph as the basis for message passing [. latent [ message passing (which can be expressed as anisotropic diffusion arising from additional structure of the underlying continuous space and different discretisation of the PDEs e.g. based on finite elements), and exploiting efficient numerical PDE solvers
graph inference [41 89 29, (36] higher-order [7] [54] and directional
19] We leave these exciting directions for future research.
Societal impact GNNs have recently become increasingly utilized industrial applications e.g. in recommender systems and social networks, and hence could potentially lead to a negative societal impact if used improperly. We would like to emphasize that our paper does not study such potential negative applications and the mathematical framework we develop could help to interpret and understand existing GNN models. We believe that better understanding of ML models is key to managing their potential societal implications and preventing their negative impact.
The assumption that the graph can be modelled as discretisation of some continuous space makes our framework applicable only to cases where the edge and node features are continuous nature. Applications e.g. to knowledge graphs with categorical attributes could only addressed by first embedding such attributes in a continuous space. Finally, the structural result presented in Theorem [ that link our model to the Polyakov action have not been implemented. This will be addressed in future works.
Limitations

---

8 Acknowledgements
We thank Nils Hammerla and Gabriele Corso for feedback on early version of this manuscript. MB and JR are supported in part by ERC Consolidator grant no 724228 (LEMAN).
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
[2] Pedro H. C. Avelar, Anderson R. Tavares, Marco Gori, and Luis C. Lamb. Discrete and continuous deep residual learning over graphs. 1.0554 2019.
[3] Dominique Beaini, Saro Passaro, Vincent Létourneau, William L Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. arXiv:2010.02863, 2020.
[4] Filipe de Avila Belbute-Peres, Thomas Economon, and Zico Kolter. Combining differentiable pde solvers and graph neural networks for fluid flow prediction. In ICML, 2020.
[5] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, (3(3):1373-1396 2003.
[6] Marcelo Bertalmio, Guillermo Sapiro, Vincent Caselles, and Coloma Ballester. Image inpainting.
In PACMCGIT, 2000.
[7] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Liò, and Michael Bronstein. Weisfeiler and lchman go topological: Message passing simplicial networks. arXivv2103.03212 2021.
[8] Marian Boguna, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and
M Ángeles Serrano. Network geometry. Nature Reviews Physics, pages 1-22, 2021.
[9] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv:2006.09252, 2020.
[10] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. 2ttt:21044134775 2021.
[11] Michael M Bronstein and lasonas Kokkinos. Scale-invariant heat kernel signatures for non-rigid shape recognition. CVPR, 2010.
[12] Antoni Buades, Bartomeu Coll, and J-M Morel. A non-local algorithm for image denoising. In ICCV, 2005.
[13] Vicent Caselles, Ron Kimmel, and Guillermo Sapiro. Geodesic active contours. IJV, 22(1):61-79, 1997.
[14] Soumen Chakrabarti. Dynamic personalized pagerank in entity-relation graphs. In WWW, 2007.
[15] Benjamin P. Chamberlain, James Clough, and Marc Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv: 10359, 2017.
[16] Benjamin P. Chamberlain, James Rowbottom, Maria Gorinova, Michael M. Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: graph neural diffusion. ICML 2021, pages 1407-1418, 2021.
[17] Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In NeurIPS, 2019.
[18] Tony F Chan and Luminita Vese. Active contours without edges. Processing, 10(2):66-211 2222266--77,22 2001.
IEEE Trans. Image

---

[19] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In NewrIPS, pages 6571-6583, 2018.
[20] Ronald Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
[21] Miles Cranmer, Sam Greydanus, Stephan Hoyer, Peter Battaglia, David Spergel, and Shirley Ho. Lagrangian neural networks. 2020.
[22] Miles Cranmer, Rui Xu, Peter Battaglia, and Shirley Ho. Learning symbolic physics with graph networks. arXiv:1909.0580 2019.
[23] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. NeurIPS, 2016.
[24] John R Dormand and Peter Prince. A family of embedded Runge-Kutte Kutte formulae. Journal of Computational and Applied Mathematics, 6(1):19-26, 1980.
[25] Emilien Dupont, Arnaud Doucet, and Yee Whye Teh. Augmented neural ODEs. In NeurIPS, pages 3134-3144 2019.
[26] Frédo Durand and Julie Dorsey. Fast bilateral filtering for the display of high-dynamic-rangg images. In Proc Computer Graphics and Interactive Techniques, 2002.
[27] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv:2012.09699 2020.
[28] Chris Finlay, Jörn- Henrik Jacobsen, Levon Nurbekyan, and Adam M Oberman. How to train your neural ode: The world of Jacobian and kinetic regularization. In ICML, 2020.
[29] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML,, 2019.
[30] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In /CML, 2017.
[31] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. NeurlPS, 2020.
[32] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
[33] DF Hawken, JJ Gottlieb, and JS Hansen. Review of some adaptive node-movement techniques in finite-element and finite-difference solutions of partial differential equations. Journal of Computational Physics, 95(2):254-302 1991.
[34] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph-structurel data. arXiv:1506.05 2015.
[35] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs arXiv:2005.00687, 2020.
[36] Anees Kazi, Luca Cosmo, Nassir Navab, and Michael Bronstein. Differentiable graph module (DGN) graph convolutional networks. 2xXiv:2002.04999 2020.
[37] Jacob Kelly, Jesse Bettencourt, Matthew James Johnson, and David Duvenaud. Learning differential equations that are easy to solve. In NeurlPS, 2020.
[38] Ron Kimmel. Numerical geometry of images: Theory, algorithms, and applications. Springer, 2012.
[39] Ron Kimmel, Ravi Malladi, and Nir Sochen, Images as embedded maps and minimal surfaces: movies, color, texture, and volumetric medical images. IJCV, 39(2):111-129 2000.

---

[40] Ron Kimmel, Nir Sochen, and Ravi Malladi. From high energy physics to low level vision. pages 236-247. Springer, 1997.
[41] Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In ICML, 2018.
[42] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[43] Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In NeurIPS, volume 32, 2019.
[44] Wilhelm Kutta. Beitrag zur naherungsweisen integration totaler differeentalgleichunnen. Math. Phys., 46:435 453, 1901.
[45] Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Trans. Signal Processing. 2017.
[46] Xuechen Li, Ricky Tian Qi Chen, Ting-Kam Leonard Wong, and David Duvenaud. Scalable gradients for stochastic differential equations. In Artificial Intelligence and Statistics, 2020.
[47] Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differen- tial equations. 2020.
[48] Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli. Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Multipole graph neural operator for parametric partial differential equations. In NeurIPS, 2020.
[49] Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard $ Zemel. Lanczosnet: Multi-scale deep graph convo-lutional networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
[50] Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E. Gonzalez, and Ion Stoica. Tune: A research platform for distributed model selection and training. arXiv: 1807,05118 2018.
[51] Roce Litman and Alexander M Bronstein. Learning spectral descriptors for deformable shape correspondence. PAMI, 36(1):171-180, 2013.
[52] Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. arXiv preprint 1910 /2892, 2019.
[53] Xuanqing Liu, Tesi Xiao, Si Si, Qin Cao, Sanjiv Kumar, and Cho-Jui Hsich. Neural SDE: Stabilizing neural ODE networks with stochastic noise. (2), 2019.
[54] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, pages 2153-2164, 2019.
[55] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. image-based recommendations on styles and substitutes. Proceedings Information Retrieval, 2015.
[56] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
[57] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolå, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In CVPR, 2017.
[58] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In Proceedings Mining and Learning with Graphs, 2012.

---

[59] Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference on Machine Learning. pages 3779-3788. PMLR, 2018.
[60] Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. 2019.
[61] Lars Onsager. Reciprocal relations in irreversible processes. i. Physical Review, 37(4):405, 1931.
[62] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. ICLR, 2020.
[63] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, 1999.
[64] Giuseppe Patané. Laplacian spectral kernels and distances for geometry processing and shape analysis. Computer Graphics Forum, 35(2):599-6244 2016.
[65] Pietro Perona and Jitendra Malik. Scale-space and edge detection using anisotropic diffusion. PAMI, 12(7))629-632) 2322,9963,..1 1990.
[66] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[67] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations. pages 6571-6583, 2019.
[68] Alexander M Polyakov. Quantum geometry of bosonic strings. Physics Letters B,
103(3):207-210, 1981.
[69] Lev Semenovich Pontryagin. Mathematical theory of optimal processes. Routledge, 2018.
[70] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In CVPR, 2017.
[71] Alejandro F. Queinuga, N. Benjamin Erichson, Dane Taylor, and Michael W. Mahoney. Continuous-in-depth neural networks. CoRR, 2020.
[72] Maziar Raissi, Paris Perdikaris, and George Em Karniadakis. Physics informed deep learning (Part II): Data-driven discovery of nonlinear partial differential equations. CoRR, (Part II), 2017.
[73] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. arXiv:2004. 11 2020.
[74] Carl Runge. Über die numerische auflösung von diffcrentialgleichungen. Mathematische Annalen, 46(2):167-178, 1895.
[75] Alvaro
Victor Bapst, Kyle Cranmer, and Peter Battaglia. Hamiltonian graph networks with ODE integrators. 2019.
[76] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 27(8):61-80 2009.
[77] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93-9)) 93, 2008
[78] Lawrence F Shampine, Some practical Runge-Kutta formulas. Mathematics of Computation, 46(173):135-150, 1986.
[79] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation.
2018.
[80] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lchman graph kernels. JMLR, 22:2599-2561, 201

---

[81] Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
[82] Nir Sochen, Ron Kimmel, and Ravi Malladi. general framework for low level vision. JEEE Truns. Image Processing, 7(3):310-316 1998.
[83] Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. A concise and provably informative multi- scale signature based on heat diffusion. Computer Graphics Forum, 28(5):1333-1392) 2009.
[84] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. Dcience, 29065500):231--2223 2000.
[85] Carlo Tomasi and Roberto Manduchi. Bilateral filtering for gray and color images. In ICCV, 1998.
[86] Ashish Vaswani, Noam Shazeer, Niki Parmar, Akob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. NeurIPS, pages 5998-6008, 2017.
[87] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. 2017.
[88] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[89] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph CNN for learning on point clouds. ACM Trans. Graphics, 38 2019.
[90] Joachim Weickert. Anisotropic diffusion in image processing. Teubner Stuttgart, 1998.
[91] Joachim Weickert, Bart M. Ter Haar Romeny, and Max A. Viergever. Efficient and reliable schemes for nonlinear diffusion filtering. IEEE Trans. Image Processing, 7(3):398-44) 1998.
[92] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML. PMLR, 2019.
[93] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. NeurIPS, 2020.
[94] Louis-pascal A C Xhoonnex, Meng Qu, and Jian Tang. Continuous graph neural networks. In ICML, 2020.
[95] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[96] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[97] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In NeurlPS, 2017.
[98] Juntang Zhuang, Nicha Dvornek, Xiaoxiao Li, and James S. Dunean, Ordinary differential equations graph networks. Technical Report 1, 2020.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In limitations (S6) and an
extensions (S3.4)
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? Theorem is dealt with in the supplementary material [Yes] Supplementary Material
(b) Did you include complete proofs of all theoretical results? [Yes] Supplementary Material
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] In supplemen-
tary material
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] hyperparameters are included in Supplementary Material and splits are addressed in section 5
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Results in Section include error bars
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] AWS, details the end of 5.1 and supplementary material
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] papers have been cited for the most relevant OS libraries
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "xi87pAv-d3a", "reviewer": "Reviewer_3zke", "summary": "The paper proposes a new graph neural network based on a continuous time flow. Each node is given a pre-processed position from an off-line node embedding method, then both the position and a vector of node features (together called Z) are changed during the flow. The flow changes Z by the average difference of Z of adjacent nodes, weighted by a scaled dot product attention. Additionally, a node-wise initial encoder and final decoder is used. The flow is computed via explicit adaptive or fixed integration and the backward pass via the adjoint method. The authors propose various extensions, including having dynamic adjacency via kNN and using hyperbolic positional space. The authors claim their method is motivated as a discrete analogue of a Beltrami flow.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths:\n- The method performs well on smaller data sets with a small number of parameters.\n- The method explores some interesting new ideas for graph neural networks.\n\n### Weaknesses:\n- I am not quite convinced by the motivation of the proposed method as a discrete analogue of the continuous Beltrami flow. The “structural assumptions on the diffusivity” $a$ seem to not be satisfied scaled dot product attention in BLEND. What is the point of all the theoretical motivation if the actual construction violates the assumptions of the theory?\n- Currently, I find it unclear which aspect of the proposed method makes it perform well. Is it the position that is added as a pre-processing step, the continuousness of the flow, the particular integrator, or the particular flow equation (6)? The ablation analysis in the appendix only partially answers this question. Further experiments could include: augmenting GAT with positional encodings; using BLEND with Euler steps; using GAT with continuous integration.\n- The method does not seem to get state-of-the-art results on larger sized data sets. The GAT baseline uses more parameters, but would BLEND improve if it used as many? I expect that BLEND has much higher training and inference time than GAT, even with the smaller model, because of the continuous integration. Concrete run-times are not given, so I can’t say for sure.\n\n### Further suggestions for improvement:\n- I’d be very interested in the performance of including channel mixing in the flow, referred to as Onsager diffusion, as currently, the fact that the channels only interact via the attention seems limiting. The same holds for time-dependent diffusivity.\n- Include (some idea of) the structural assumptions in thm 1 in the main paper.\n- Include results on BLEND-kNN on ogb-arxiv or explain why this result is missing.\n- Include some actual run-times of BLEND(-kNN) vs other methods.\n- In the appendix clarify why (9, suppl mat) is the obvious discrete analogue of (6, suppl mat). I see some notational similarity between (10, suppl mat) and (6, suppl mat), but that looks rather superficial, besides it being one possible generalization of the classic Dirichlet energy. In fact, the paper doesn’t seem to be using this additional generality and only shows the classic example in which $\\tilde\\psi$ is constant. What does this additional $\\psi$ generality add?\n- Could the authors clarify the step from (8, suppl mat) to (1)? Where does the time come from?\n\n### Typos:\n-\tEqn 4, $x(x,0)$ should be $x(v, 0)$\n-\tIn Table 3, the score for GCN on CiteSeer is bold.\n-\tThe colouring in Table 3 seems incorrect. The BLEND-kNN performs on par with CGNN.\n-\tThe eqn under line 48 in the suppl mat would be clearer if parenthesis would be added to indicate that the partial derivative only applies to Z.\n-\tLine 153, missing reference\n\n\n### Conclusion:\n- Originality: The work is original. It tries to connect differential geometry to continuous flows in graphs in a way I hadn’t seen before.\n- Quality: I have doubts about the correctness, as I question whether the presented theory applies to the proposed model. Additionally, important ablations are missing.\n- Clarity: The paper is clearly written.\n- Significance: The paper can be significant to all people researching graph neural nets and open exploration into continuous flows on this domain.\n- Score: 5, marginally below acceptance threshold. If the authors can convince me the theory does apply to their model, I will increase my score.\n- Confidence: 4. I read the paper in detail.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The fact that their theory does not seem to be applicable to the used model, is not honestly mentioned in the limitations. To the contrary, the vagueness of unspecified 'structural assumptions', that are only given in the appendix, makes this theoretical limitation hard to find.\n\nI think the authors underestimate the current use of graph neural networks in industry. They are used widely. As such, some more elaboration on potential negative societal impact of graph neural networks in general could be given.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "tCBAXwDxRn", "reviewer": "Reviewer_RFfM", "summary": "** score updated 6->7 after rebuttal**\n\nThe paper proposes an interpretation of various GNN related architectures as Beltrami flows on a 2-manifold of position and feature embeddings, using this perspective to formulate a GNN architecture which uses feature encoders to create starting points in the 2-manifold and learned attention kernels (in their experiments, shared across time/layers) to give the update of the embeddings. The authors propose that this unifies various architectures as well as graph-rewiring techniques developed in the literature, evalaute against GCN,GAT,GAT-ppr,MoNet,GS-{mean/maxpool},CGNN and G(O)DE on cora,citeseer,pubmed,coauthor-CS,computer,photo and ogb-arxiv, showing their method matches or outperforms all other methods when taking into account parameter efficiency.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors follow the NODE approach of viewing residual layers as ODE steps, allowing a continuous depth when training with differential equation solvers and parametrizing an implicit layer. \n\nThe paper is well written (except for some typos, see below) and the perspective of graph rewiring through a continuous  process is intriguing. However, I have some questions before I can give  a higher rating\n\n-  you present various extensions in 3.4, what would be the expressive power hierarchy? I assume it goes deepsets \\subset Beltrami with time independent attention(w.t.i.a)  \\subset Onsager w.t.i.a \\subset Onsager Onsager w.t.d.a \\subset onsager with generic time dependent nonlinear equation == full attention network with enough layers?\n- how does this work compare with e.g.  https://arxiv.org/abs/1909.12790 and  G(O)DE/CGNN specifically? I think it's worth highlighting commonalities and differences, especially since G(O)DE/CGNN seem competetive with your method in table2  and 3 \n-  since you are using attention on the node embeddings, this means this method will be quadratic in cost w.r.t to number of nodes? as opposed to the sparsity amortization afforded by e.g. MPGNN?\n- you highlight the expressive power in the abstract, but if I undertand correctly, your method can only ever be equivalent to MPGNNs with rewiring techniques/full attention right? Or do you have a proof/example that says otherwise?\n- did you perform tuning with raytune for *all* methods not taken from the Pitfalls of GNN paper? It might be worth marking which is taken from the paper with a cross or something, and state explicitly whether the others were tunes fairly\n- following up on the complexity question, I think adding training curves or some details about training costs and parameter counts to the appendix would be beneficial to putting the work in context. in general, NODEs offer a tradeoff, not a free lunch\n- did you apply the jacobian/kinetic regularisation to G(O)D/CGNN as well? how does your method perform without the regularisation? \n\nTypos:\nI assume in the equation between 212 and 213 Y is meant to be decoded with \\xi, not with \\psi, which is referred to as encoder in 213?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors are understating the negative effect  social network analysis can have in terms of surveillance and manipulation, as well as understating the benefit that can come from better architectures for relational tasks expressible as graphs.  VLSI,logic programming etc. can all benefit from this, as can the design of automated propaganda techniques, LAWs and police states. \n\nAs for limitations, as I said, computational expense should be discussed in the paper as well, or noted as a bottleneck. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "eKuVL_mApqy", "reviewer": "Reviewer_eTTt", "summary": "I have read the authors' responses, comments from the other reviewers, and the discussion here. The authors have answered my questions satisfactorily. Hence, I am increasing my score to 7.\n\n\nThis paper derives a new class of GNN using ideas from differential geometry. It proposes discretization of the PDE associated with the Beltrami flow for the design of the GNN. Although the explicit discrete approximation of the Beltrami flow on a graph has many interesting similarities to existing attention mechanisms, this framework can be more general with the use of sophisticated differential equation solvers, as presented by the authors. The paper also brings out interesting connections between their model and existing GNN architectures, which in itself, is a nice contribution of this work.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is generally well written except for some typos (possibly), for example,\n\n1) In eq. 4, should there be a $(4\\pi t)^{-d/2}$ in the RHS? Without it, if $\\alpha \\rightarrow 0$, eq.4 does not become the convolution in line 74.\n\n2) In the same equation, should $x(\\mathbf{x}, 0) \\rightarrow x(v, 0)$, and $x(u), x(v) \\rightarrow x(u, 0), x(v, 0)$?\n\n3) In eq. 6, should $U(0)= \\alpha U$ be $U(0)= U$ based on the description in section 2? \n\n4) In section 4, should $Y = \\psi(Z(T))$ be $Y = \\zeta(Z(T))$ based on the subsequent discussion?\n\n5) In eq. 8, $Q^{(k)} \\neq A^{(k)} - I$, it's actually $Q^{(k)} = \\tau A^{(k)} - (\\tau -1) I$. However, the definition of $q_{ij}^{(k)}$ is correct.\n\n6) In line 153, \\ref to a section is not working.\n\nOther questions/ comments:\n\n1) Is $\\alpha$ learned or treated as a hyperparameter? If it is learned, how is the criterion $\\alpha \\geq 0$ satisfied? If it is a hyperparameter, what is its effect on the classification accuracy?\n\n2) Can the authors compare the explicit scheme in sec. 3.2 with their implementation using numerical solver? This will allow the readers to understand the actual source of the performance improvements.\n\n3) Can the authors discuss the novelty in this work in comparison to existing ODE-based GNN models (reference 69, 96, 100). I appreciate that they conduct experimental comparisons with these related works, but some comments about the methodology as well would be welcome.\n\n4) In the supplementary material, the authors discuss several choices for the diffusivity function modeling but do not report any experimental comparisons. \n\nOverall, my impression is that this work has some novelty in terms of methodology and strong numerical results. But the writing could be significantly improved and the current version is not entirely satisfactory to be published.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations and societal impacts adequately.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel class of GNNs based on non-Euclidean diffusion PDEs, i.e., Beltrami flows on 2-manifolds of position and feature embeddings, and can be seen to generalize various existing GNN architectures. The paper is well written and relevant to the NeurIPS community. All reviewers and the AC support acceptance for its contributions, especially due to the novel and interesting ideas that provide a new perspective for graph learning methods as well as the promising empirical results. The authors' rebuttal, including additional experiments, further increased the confidence of reviewers and resolved concerns related to the empirical analysis. When preparing the camera ready version, please incorporate the overall feedback of reviewers into the new revision (e.g., motivation, theoretical discussion of Thm 1 and limitation, ablation).
Decision: Accept (Poster)