Capturing Graphs with Hypo-Elliptic Diffusions
Authors: Csaba Toth
Darrick Lee
Celia Hacker
Harald Oberhauser
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Diffusion
Random Walks
Hypo-Elliptic Laplacian
Graph Tensor Networks
Graph Classification

Abstract: Convolutional layers within graph neural networks operate by aggregating information about local neighbourhood structures; one common way to encode such substructures is through random walks. The distribution of these random walks evolves according to a diffusion equation defined using the graph Laplacian. We extend this approach by leveraging classic mathematical results about hypo-elliptic diffusions. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We provide theoretical guarantees and efficient low-rank approximation algorithms. In particular, this gives a structured approach to capture long-range dependencies on graphs that is robust to pooling. Besides the attractive theoretical properties, our experiments show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges as opposed to quadratically in nodes.

Capturing Graphs with Hypo-Elliptic Diffusions
Csaba Toth"
Darrick Lee" Mathematical Institute University of Oxford Leed@maths ox. ac
Mathematical Institute University of Oxford toth@maths.om ox. ac
Celia Hacker
Harald Oberhauser
Department of Mathematics
Mathematical Institute University of Oxford oberhauserrmathhe ox. uk
EPFL celia. haakahakeeee@@effecceeee
Abstract
Convolutional layers within graph neural networks operate by aggregating infor- mation about local neighbourhood structures; one common way to encode such substructures is through random walks. The distribution of these random walks evolves according to diffusion equation defined using the graph Laplacian. We extend this approach by leveraging classic mathematical results about hypo-elliptic diffusions. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We provide theoretical guarantees and efficient low-rank approximation algorithms. In particular, this gives a structured approach capture long-range dependencies on graphs that is robust to pooling. Besides the attractive theoretical properties, our experiments show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges as opposed to quadratically in nodes.
1 Introduction
Obtaining latent description of the Euclldean structure of graph is central many applications. One common approach is to construct a set of features for each node that represents the local neighborhood of this node; pooling these node features then provides latent description of the whole graph. A classic way to arrive at such node features is by random walks: at the given node one starts random walk, and extracts a summary the local neighbourhood from its sample trajectories. We revisit this random walk construction and are inspired by two classical mathematical results:
Hypo-elliptic Laplacian. the Euclidean case of Brownian motion B (Bt)s2 evolving in R" the quantity u(t, x) (B,) Bo 2] solves the heat equation d,u Au [0, oc) R". u(0,z) x) = fzx) Seminal work of Gaveau 23 in the 1970s shows that if one replaces f(B.) in the expectation by functional of the whole trajectory. F(B,
[0, f)), then path- dependent heat equation can be derived where the classical Laplacian is replaced by the hypo-elliptic Laplacian.
Free Algebras. A simple way capture sequence for sequence of nodes visited by random walk on a graph is to associate with each sequence element an element in an algebra and multiply these algebra elements together. If the algebra multiplication is commutative,
Equaal contribution; order determined by random coin flip.
An algebra is vector space where one can multiply elements; e.g. the set of n X matrices with matrix multiplication. This multiplication can be non-commutative; e.g. A B B A for general matrices A, B.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the sequential structure is lost but if it is commutaate,,v this captures the order in the sequence. In fact, by using the free associative algebra, this can be done faithfully and linear functionals of this algebra correspond to functionals on the space of sequences.
We leverage these ideas from the Euclidean case of Rd the non-Euclidean case of graphs. In particular, we construct features for a given node by sampling from a random walk started at this node, but instead of averaging over the end points, we average over path-dependent functions. Put informally, instead of asking random walker that started at node, "What do you see now?" after k steps, we ask "What have you seen along your way?". The above notions from mathematics about the hypo-elliptic Laplacian and the free algebra allow us to formalize this in the form of a generalized graph diffusion equation and we develop algorithms that make this a scalable method.
Related Work. From the ML literature, 49 27 popularized the combination of deep learning
architectures capture random walk histories. Such ideas have been incorporated, sometimes implic- itly, into graph neural networks (GNN) (53
29 5 33 that in turn build on convolutional well their combination with attention or message passing [5 24
y
54
18]
approaches 77
27
[S] that provide and improve on theoretical guarantees. Another classic approach are graph kernels, see 7 for recent survey; in particular, the seminal paper [36] explored the connection between diffusion equations and random walkers in kernel learning context. More recently, [4] proposed sequence kernels to capture the random walk history. Furthermore, [I7 uses the signature kernel maximum mean discrepancy (MMD) [6 as metric for trees which implicitly relies on the algebra of tensors that we use, and 48 aggregates random
and more recent improvements
772
46
43
walk histories to derive kernel for graphs. Moreover, the concept of network motifs 44 55 relates to similar ideas that deseribe graph by node sequences. Further, the Bethe Hessian (52) has been successfully used in spectral clustering and shares the same goal of capturing pathdependence via a "deformed Laplacians", although the mathematical approach is very different to ours. Directly related to our approach is the topic of learning diffusion models 35
20 | on graphs. While 50
similar ideas on random walks and diffusion for graph learning have been developed by different communities, our proposed method leverages these perspectives by capturing random walk histories through a novel diffusion operation.
Our main mathematical influence is the seminal work of Gaveau 23 from the 1970s that shows how Brownian motion can be lifted into a Markov process evolving free algebra to capture path-dependence. This leads to a heat equation governed by the hypo-elliptic Laplacian. These insights had a large influence in PDE theory, see [T. but seems that their discrete counterpart on graphs has received no attention despite the dele-deel literature on random walks graphs and general non- Euclidean objects, [68 19 is handling the computational complexity. To do we build on ideas from 622 to design effective algorithms for the hypo-elliptic graph diffusion.
26
631 A key challenge to go from theory to application
Contribution and Outline. We introduce the hypo-elliptic graph Laplacian which allows to effec- tively capture random walk histories through a generalized diffusion model.
In Section S we introduce the hypo-elliptic variants of standard graph matrices such as the adjacency matrix and (normalized) graph Laplacians. These hypo-elliptic variants formulated in terms of censor-valued matrices rather than scalar-valued matrices, and can be manipulated using linear algebra in the same manner as the classical setting.
The hypo-elliptic Laplacian leads to a corresponding diffusion model, and in Theorem we show that the solution to this generalized diffusion equation summarizes the microscopic picture of the entire history of random walks and not just their location after k steps.
This solution provides a rich description of the local neighbourhood about a node, which can either be used directly node features or be pooled over the graph to obtain latent description of the graph. Theorem 2 shows that these node features characterize random walks the graph, and we provide analogous statement for graph features in Appendix
One can solve the hypo-elliptic graph diffusion equation directly with linear algebra, but this is computationally prohibitive and Theorem 3 provides an efficient low-rank approximation.
Finally, Section 5 provides experiments and benchmarks. A particular focus is to test the ability of our model to capture long-range interactions between nodes and the robustness of pooling operations which makes it less susceptible to the "over-squashing" phenomenon [2]
2

---

2 Sequence Features by Non-Commutative Multiplication.
define the space of sequences in IR4 by
(eq(R)) U (Rd)h+1
where elements sequences denoted by (Io ,,,...,, Ik) E (R4)k+1, Assume given injective map, which we call the algebra lifting, Rd H.
from Rd into algebra H. We can use this to define sequence feature map
G Seq(R") - H, (xx)) = p()(x) ... =(
(I)
where dyx = To and 6,x == x; -;-1 for 2 are used to denote the increments of a sequence (zo...., ).) This map associates to any sequence Seq(R") element of the algebra H. If the multiplication in H commutative, then the map T would have no information about the order of increments, i.c. ((6gx) ... (((xx)))))))))))))))))))) (()) (((+(()))) for any permutation и of (O....,k) k). However, the multiplication in H is "non-commutative enough" we expect ç to be injective.
Free Construction. Many choices for H are possible, but intuitively it makes sense to use the "most general object" for H. The mathematically rigorous approach is to use the free algebra over Rd and we give summary Appendix B. Despite this abstract motivation, the algebra H has concrete form: it is realized as a sequence of tensors in Id of increasing degree, and is defined by
= (v (vo: V1, V2,...) .): Vm E (Rd) @m m E N, || < oo).
where by convention (Rd)@u R, and we describe the norm ||v|| in the paragraph below. For example, if v (vm m20 E H, then Vn is scalar, is vector, V2 (Rd))8 is d x d matrix, and so on. The vector space structure H given by addition and scalar multiplication according to
V w == (vm + Wm)m20 E and Av = (Avm))20 E
for À E IR, and the algebra structure is given by
V. =
Σ vi 2 Wm-i
E H.
(2)
m20
An Inner Product. If ed a basis of Rdd, then every tensor Vm E (Rd)@m can be written as
Gr X X elm.
15 Sd
This allows to define an inner product (,, ) on (Rd) jm by extending
(c 1 pm e elm)
1
1 : ji.....
......, im Jun
0 otherwise.
to (Rd) by linearity. This gives us inner product on H,
(v. w) = Σ (Vm. Wm)m
m20
such that is Hilbert space; particular we get norm || ==
v). To sum up, the space H has a rich structure: it has a vector space structure, it has an algebra structure (a noncommutative product), and is Hilbert space (an inner product between elements of H gives scalar).
There variants of this sequence feature map, which discussed in Appendix

---

Characterizing Random Walks, From Equation I we have constructed a map ğ that maps sequence x E (R*(R") of arbitrary length into the space H (see Appendix Coor further details). Our aim is to apply this to the sequence of node attributes corresponding to random walks on a graph. Therefore, the expectation of Φ should be able to characterize the distribution of the random walk. Formally the map Ø is characteristic if the map l + Ex~u [x~x(((x)] from the space of probability measures (eq(1) into H is injective. Indeed, if the chosen lifting sp satisfies some mild conditions this holds for (o; see Appendix and [6 62].
Linear Functionals. The quantity Ex~p (x) characterizes the probability measure but is valued in the
Hilbert space Using the inner product, we can instead consider
(L, Ex~nulpr (((x)) for l (Lo, f,.,,,,,,, 0,.0,...)) E H and M 2 1
(4)
which is equivalent to knowing [xx]]; i.c. the set 4 characterizes μr. This is analogous to how one can either the moment generating function of real-valued random variable its sequence
of moments to characterize its distribution; the former is one infinit-diimensinall object (a function),
the latter is infinite sequence of scalars. We extend key insight from [62] in Section 4 linear
functional (e, [+()) can be efficiently approximated without directly computing E Ex~x [x) or storing large tensors.
The Tensor Exponential. While we will continue to keep arbitrary for our main results (see 62
and Appendix G for other choices), we will use the tensor exponential exps. Rdd H, defined by
200m
expx (x)
(5)
m!!
m20
as the primary example throughout this paper and the experiments in Section 5 With this choice, the induced sequence feature map is the discretized version of a classical object analysis, called the path signature, see Appendix
3 Hypo-Elliptic Diffusions
Throughout this section, fix labelled graph EV, that is V is of nodes Rd is the set of continuous node attributes which
== {1....,,1] n2), & denotes edges and f map each node to an element in the vector space Rd. Two nodes i, E V are adjacent if (i,j) & is an edge, and we denote this by ~ j. The adjacency matrix of graph defined by Ai, = 1, whenever i ~ j. and 0 otherwise. We denote by deg(i) the number nodes that are adjacent to node i.
Random Walks on Graphs. Let (Bx)220 be the simple random walk on the nodes of G, where the initial node is chosen uniformly at random. The transition matrix of this time-homogeneous Markov chain is
dog(s) :i~j
P.j = P(Bx = -B
= i)
: otherwise.
Denote by (Lx)k20 the random walk lifted to the node attributes in Rd, that is
L = (Bxx)
(6)
Recall that the normalized graph Laplacian for random walks is defined as L - - D-1A, where D is diagonal degree matrix; in particular, the entry-wise definition is
j j
deg(() (8)
Cij
otherwise.
The discrete graph diffusion equation for Us RRuxd is given by
Uk - Uk-1 -
u = f(i)
'The labels given by the labelled graph called autributes, while the computed updates called features.

---

where the initial condition Uo E Raxd is specified by the node attributes interpretation of the solution this diffusion equation is classical and given as
The probabilistic
U = (F( Be = -)== P
(8)
This allows us to compute the solution uk using the transition matrix P P= P
Random Walks on Algebras. the quantity
We now incorporate the history of a random walker by considering
(L) B. - -- (((.L))))(.-((LL)) Bo -
where L (Too ................................ ]. Since き captures the whole history of the random walk Lg node attributes, we expect this expectation to provide a much richer summary of the neighborhood of node i than [[Lx] BB ij. The price is however, the computational complexity, since 2 is H-valued. We first show, that analogous to 7. the quantity D satisfies a diffusion equation that can be computed with linear algebra. To do so, we develop a graph analogue of the hypo-elliptic Laplacian and replace the scalar entries of the matrices with entries from the algebra H.
Matrix Rings over Algebras. We first revisit the adjacency matrix A E R and replace it by the tensor adjacency matrix Ā = (A)s.) E H that is A is a matrix but instead of scalar entries its entries are elements in the algebra H. The matrix A has an entry at i, if nodes and j are connected; A replaces the i entry with an element of И that tells us how the node attributes of i and differ,
A : (((()) f())) :inj
(10)
otherwise.
Matrix multiplication works for elements of H by replacing scalar multiplication by multiplication
in H, that is (B CC) Ek_1 Bi Ck.i for B, C E = and B., Ck. denotes multiplication For the classical adjacency matrix A, the k-th power counts the number of
in H as in Equation length & walks in the graph, so that (A*)s )a, is the number walks of length & from node i to node j.
We can take powers of A in the same way as in the classical case, where
(A')ss Σ p((1x) ... (6(xx)
where the sum is taken over all length i walks x (f(i),.. f( f()) from node to node (full details provided in Appendix D). Since ((x) characterizes each walk the entry At can be interpreted as a summary of all walks which connect nodes i and j.
Hypo-elliptic Graph Diffusion. Similar to the tensor adjacency matrix, we define the hypo-elliptic graph Laplacian as the n X n matrix
T- H=x"
where D is the degree matrix embedded into H at tensor degree 0. The entry-wise definition is
-(())) f())
Daj
deg())
(11)
otherwise.
We now formulate the hypo-elliptiee graph diffusion equation for VA H
Vk-1 - 0 = (i)))..
(i)
(12)
Analogous to the classic graph diffusion (8). the hypo-elliptic graph diffusion 12 has a probabilistic interpretation in terms of as shown in Theorem (the proof is given in Appendix D.
Theorem 1. Let I. L (Lu,..., .., Lb) be the lifted random walk from ( and P Σ be
the tensor adjacency matrix. The solution to the hypo-elliptic graph diffusion equation
12 is
Vk (E(
(p Lx) Bo = = p*
Furthermore, if E H is the diagonal matrix with F,, = (i)) then
Fv, = (E(G(L,)) By = i 'The attributes over all nodes are given by d matrix; particular U.(0) is the 1thh row of the matrix.
5

---

In the classical diffusion equation, Uj captures the concentration of the random walkers after & time steps over the nodes. In the hypo-elliptic diffusion equation, V& captures summaries of random walk histories after & time steps over the nodes since ((Lx) summarizes the whole trajectory Lg = (Io....; I&x) and not only the endpoint L.z-
Node Features and Graph Features. Theorem 1 can then be used to compute features +(t) H for individual nodes as well as feature (g) for the entire graph. The former is given by i-th component Viz
(8) of the solution (v i=...... E H of Equation 12
(i)
= (L.) B. = (FP* (1) H.
since the random walk B chooses the starting node Bu = uniformly at random. The latter can be computed by mean pooling the node features, which also has probabilistic interpretation as
(G)) = Σ = E[G(L:)) - n ((hPP''' E H,
(13)
where 1/ = (1H,... 1x) E H the all-ones vector in H and 18 denotes the unit in H.
Characterizing Graphs with Random Walks. The graph and node features obtained through the hypo-elliptic diffuusion equation are highly descriptive: they characterize the entire history of the random walk process if one also includes the time parametrization, as described in Appendix [
Theorem 2. Suppose is the graph feature map from Equation (33) induced by the tensor ex- ponential algebra lifting including time parametrization. Let G and G' be two labelled graphs, and L (Lo...., Lb) and Lig (Lig...,Li, L1) be the k-step lifted random walk as defined in Equation 6 Then, (G) (G') if and only if the distributions of Lg and L2g are equal.
It is instructive to contrast this result with the classical diffusion case; the latter only uses the marginal distribution of La capture the graph structure, which at least intuitively has much less expressive power. Indeed, in Appendix D we show that for elementary graphs. this already leads to big differences expressive power. Further, an analogous result holds for the node features, and we prove both results in Appendix E While we use the tensor exponential in this article, many other choices of T are possible and result in graph and node features with such properties: under mild conditions, if the algebra lifting y IR + H characterizes measures on Rd the resulting node feature map & characterizes the random walk, see 62) which in turn implies the above results. Possible variations are discussed in Appendix
General (Hypo-elliptic) Diffussios and Attention. One can consider more general diffusion operators, such as the normalized Laplacian K. of a weighted graph. We define its lifted operator K. E _=x= analogous to Equation (II) resulting in generalization of Theorem I with K. replacing L. In the flavour of convolutional GNNs [8) consider weighted adjacency matrix A E R
Ca.y :ing otherwise,
Aij
O
for C.j > O. The corresponding normalized Laplacian K. is given by I D-1 where D is diagonal matrix with D,,, EjeN(e) Ctj-- A common way to learn the coefficients is by introducing parameter sharing across graphs by modelling them as q.j attention mechanism, a Rd Rd R
using a local (55 our implementation, we use additive attention given by (i), f()) = LeakyRe Ruy u (i) + W.f())), where W., W. RIxd are linear transformations for the source and target nodes, but different attention mechanisms can also be used; e.g. scaled dot-product attention [64]. Then, the corresponding transition matrix P. = D-1 A is defined as P.j = softmax (a(f()) ((k))) The lifted transition matrix defined as
())(a((())
P p= {
(a,(((()) (()) : :i~j otherwise.
The statements of Theorem immediately generalize to this variation by replacing the expectation with respect to non-uniform random walk. Hence, this case the use of attention can interpreted as learning the transition probabilities of a random walk on the graph.

---

4 Efficient Algorithms for Deep Learning
The previous sections show that the node feature 4(t) provides structured description of the neighborhood of node i and it is instructive to think of a linear functional (e, (()) as answering specific question about the node neighbourhood, see Appendix E for examples. The naive computation of (e. (a)) by first computing (() and taking the inner product is too expensive, especially when (Lu. .......... .., .M....... O....) E for large M. To address this we revisit two observations from [62] first, for rank-1 functional & H, the computation of (L, (())) is computationally cheap. Second, restriction to small M limits the expressive power can be counteracted by composition: any choice of d different functionals e² e....., L E H gives a label update f(i) + ( ((e), ((1))))=I...d E Id for the graph. Repeating such label update a few times with low-degree M and rank- I functionals turns out to be as powerful as computing one update for general functionals with arbitrary high M. The first observation should not be too surprising given the popularity of low rank approximations: the second observation is reminiscent to constructing a high-degree polynomial by composing low-degree polynomial or the width-vs-depe phenomenon in neural nets and we give more details below.
Computing Rank-1 Functionals. First, we focus on rank-1 linear functional & E Н given as Ł= (fm))m22 with Pm UM-m+1
uM and e. for m M,
(14)
where um E ERd for m = l....,.M .M for fixed M 2 1. Theorem shows that for such the compu- tation of (e, (()), where ((i) the node feature without the basepoint, can be done (a) efficiently by factoring this low-rank structure into the recursive computation, and (b) simultaneously for all nodes E in parallel. This can then be used to compute rank- functionals for R > 1, and for (e, (())); see Appendix F where we also provide a pseudocode implementation.
Theorem 3. Let be as in 140 and define Jk.m E R for m 1,...,M. M as
1 m!!
f.mm
(Po CmM--mmin
3 C
where 1T = (1..... 1) E Rn is the all-ones vector; and for 2 < k and 1 S m S M recursively as
1 (P CHM---1 C... CuM-mmtr) 1k--,m-- (15)
fk.m P. 5k-1,m
where the matrix C (Ct,) Rax is defined as
Cgiy {
(() :i~j. otherwise.
Here o denotes element-wise multiplication, while denotes matrix multiplication. Then, it holds for E random walk length Z_, and tensor degree m I,..., M, that
fk.m = (em, (1))))
where &x (1) F(p(())))) ... (0x Lx)1
Bo = i).
Overall, Eq. 15 computes fk.m (i) for all V, h = 1,..., K, m =, M, in O(K - -2. NF + M - Ng d) operations, where NE IN denotes the number of edges; see App. In particular, one does not need to compute (ii) E directly or store large tensors.
Graph Labelling Layers. Fixing d rank I-functionals e! e'. E H induces a label update f(i) + ((e', ( E Rdd. Theorem allows us to compute this update in parallel for all nodes in V. Such label update is similar to hidden layer in NN and we stack such updates, see Figure 3 in App. H.I As NN, the functionals each "graph labelling layer" are optimized by gradient descent. Finally, note that rank R functional is the sum of R rank- functionals can immediately carry out the same construction with rank- R functionals by adding a mixing layer.
For example,
1 + xx² composed with 1 2 yields the degree polynomial 1 1+ (1 (1+ 2x +(1 217)2)
1 27
5
6
5
12]
For example
3
4
④
7
8
21
32
7

---

To sum up, graph labelling layer is determined by the random walk length k, the maximal tensor degree M, maximal tensor rank R. and the functionals are then found by optimization.
Using a single layer of low-rank functionals limits the expressiveness but stacking layers allows in practice approximate general, high-degree M functionals. Some theoretical results can be found in [22; however, here we simply appeal to the analogy with NN where stacking simple transformations provides a flexible functional class with good inductive bias.
5 Experiments
We implemented the above approach and call the resulting model Graph2Tens Networks since it represents the neighbourhood of node sequence of tensors, which is further pushed through a low-tensor-ramt constrained linear mapping, similarly to how neural networks linearly transform their inputs pre-activation. conceptual difference is that in our case the non-linearity is applied first and the projection secondly, albeit the computation is coupled between these steps. We provide further experiments and ablation studies of models in Appendix
Experimental Setup. The aim of our main experiment is to test the following key properties of model: (1) ability to capture long-range interactions between nodes in graph, (2) robustness to pooling operations, hence making it less susceptible to the "over-squashing" phenomenon (2]. We do this by following the experiments in 70. In particular, we show that our model is competitive with previous approaches for retaining long-range context in graph-level learning tasks but without computing all pairwise interactions between nodes, thus keeping the influence distribution localized 773. We further give a detailed ablation study to show the robustness of our model to various architectural choices in Appendix H.22] As a second experiment, we follow the previous applications of diffusion approaches to graphs that have mostly considered inductive learning tasks, e.g. on the citation datasets [13 60 M... Our experimentation on these datasets are available in Appendix HH.3 where the model performs on par with short-range GNN models, but does not seem to benefit from added long-range information a-priori. However, when labels are dropped in a k-hop sanitized way as in 150,, the performance decrease is less pronounced.
Datasets. We two biological graph classification datasets (NCI1 and NC1109), that contain around 4000 biochemical compounds represented as graphs with ~03 nodes on average [67 M. The task is predict whether a compound contains lit--uunn-ccncer activity. The dataset split in a ratio of 80% - 10% 10% for training, validation and testing. Previous work (2) has found that GNNs that only summarize local structural information can be greatly outperformed by models that are able to account for global contextual relationships through the use of fully-adjaces layers. This was further improved on by 77, where a local neighbourhood encoder consisting of GNN stack was upgraded with a Transformer submodule 64 for learning global interactions.
Model Details. We build a GNN architecture primarily motivated by the GraphTrans (small) model from 170, and only fine-tune the pre- and postprocessing layers(s), random walk length, functional degree and optimization settings. In detail, a preprocessing MLP layer with 128 hidden units is followed by a stack of 4 G2TN layers each with RW length-5, max rank-128, max tensor degree-2, all equipped with JK-connections [73] and a max aggregator. Afterwards, the node features are combined into a graph-level representation using gated attention pooling [11. The pooled features are transformed using a final MLP layer with 256 hidden units, and then fed into softmax classification layer. The pre- and postprocessing MLP layers employ skip-connections 60). Both MLP and G2TN layers are followed by layer normalization 3 where GTN layers normalize their rank-1 functionals independently across different tensor degrees, which corresponds to particular realization of group normalization 69). We randomly drop 10% of the features for all hidden layers during training [58]. The attentional variant, G2T NA)N also randomly drops 10% of its edges and uses 8 attention heads 665. Training is performed by minimizing the categorical cross- conospy loss with an l2 regularization penalty of 10 For optimization, Adam ? is used with a batch size of 128 and an inital learning rate of 10 that is decayed via a cosine annealing schedule 42 over 200 epochs. Further intuition about the model and architectural choices are available in Appendix
Baselines. We compare against (1) the baseline models reported in 70 (2) variations of Graph- Trans, (3) other recently proposed hierarchical approaches for long-range graph tasks [50]. Groups
8

---

Table I: Comparison of classification accuracies on NCT biological datasets, where we report mean and standard deviation over 10 random seeds for our models.
Model
GNN Type
GNN Count
NC11 (%)
NC1109 (%)
Set2Set
40
6N
GCN
3
68.6 + 1.9
69.8 + 1.2
SortPool
40
75
GCN
3
73.8 = 1.0
74.0 1.2
SAGPool
40
GCN
3
67.5 = 1.1
67.9
SAGPool
40
GCN
74.2 = 1.2
0.1
GIN [2T
GIN
80.0 1.4
GCN VN
24]
GCN
71.5
HGNet-FddePool
14
54
GCN+RGCN
3 3+2
77.1
HGNet-l.ouvain
14
54
GCN+RGCN
3+2
75.1
GIN FA
GIN
81.5 = 1.2
GraphTrans (small)
70
64
GCN
3
81.3 = 1.9
79.2 2.2
GraphTram Trans (large)
70
64
GCN
4
82.6 + 1.2
82.3 2.6
( (ours)
(2)
4
81.9 + 1.2
2
G2TN (ours)
G2TN
4
80.7 = 2.5
78.9
2.5
of models in Table | are separated by dashed lines if they were reported in separate papers, and the first citation after the name is where the result first appeared. The number of GNN layers in HGNet not discussed by [50).. and report it as implied by their code. We organize the models into three groups divided by solid lines: (a) baselines that only apply neighbourhood aggregations, and hierarchical global pooling schemes, (b) baselines that first employ a local neighbourhood encoder, and afterwards fully densify the graph in one way or another so that all nodes interact with each other directly, (c) our models that emphasize thematically belong to (a)
In Table over 10 different seeds. Overall, both our models improve over all baselines in group (a) on both datasets, maximally by 1.9% on NCI1 and by 4.8% on NCI109. In group (b) G2T (A) N solely outperformed by GraphTrans (large) on NCI1 by only 0.7%. Interestingly, the attention free variation, G2TN, performs better on NC1109, where it performs very slightly worse than Graph (small).
Results.
report the mean and standard deviation of classification accuracy computed
Discussion. The previous experiments demonstrate that our approach performs very favourably on long-range reasoning tasks compared to GNN-based alternatives without global pairwise node interactions. Several of the works compare against have focused on extending GNNs to larger neighbourhoods by specifically designed graph coarsening and pooling operations, and we emphasize two important points: (1) our approach can efficiently capture large neighbourhoods without any need for coarsening, (2) it already performs well with simple mean-pooling as justified by Theorem 2 and experimentally supported by the ablation studies Appendix H.2 Although the Transformer- based GraphTrans slightly outperforms our model potentially due to its ability to learn global interactions, it is not entirely clear how much of the global graph structure is able infer from interactions of short-range neighbourhood summaries. Finally, Transformer models can be bottlenecked by their quadratic complexity in nodes, while our approach only scales with edges, and hence, it can be more favourable for large sparse graphs in terms of computations.
Conclusion
Inspired by classical results from analysis 23.. we introduce the hypo-elliptic graph Laplacian. This yields diffusion equation and also generalizes its classical probabilistic interpretation via random walks but now taking history into account. addition to several attractive theoretical guarantees, we provide scalable algorithms. Our experiments show that this can lead to largely improved baselines for long-range reasoning tasks. A promising future research theme is to develop improvements for the classical Laplacian in this hypo-elliptic context; including lazy random walks [71]: nonlinear diffusions 12 and source/sink terms 300 Another theme could be to extend the geometric study [61] of over-squashing to this hypo-elliptic point of view which is naturally tied to sub- Riemannian geometry [59]. limitation our theoretical results is that for the iterations of low-rank approximations only partial results exist and expanding this is interesting aigebra-heavy. topic.

---

Acknowledgments and Disclosure of Funding
Csaba Toth was supported by a Mathematical Institute Award from the University of Oxford. Celia Hacker and Darrick Lee were supported by NCCR-Synapp Phase-3 SNSF grant number S1NF40- 185897. Darrick Lee and Harald Oberhauser were supported by the Hong Kong Innovation and Technology Commission (InnoHK Project CIMDA). Harald Oberhauser was also supported by the DataSig Program (EP/S026347/1) and the Oxford-Man Institute.
References
[1] Pubchem. https://pubchem. hww.occhhem.nc..... Lm. nww. gov/
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton, Layer normalization. arXiv preprint VrXiv:1607.064550 2016.
[4] Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
[5] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
[6] Patric Bonnier, Chong Liu, and Harald Oberhauser. Adapted topologies and higher rank signatures. arXiv preprint arXiv:2005. 08897, 2020.
[7] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O' Bray, and Bastian Rieck. Graph kernels: State-of-the-art and future challenges. arXiv preprint 20X1:20011.0884 2020.
[8] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning Grids, Groups, Graphs, Geodesies, and Gauges, arXiv:2104.13478 [cs, stat), May 2021.
[9] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv:1312.62000 2013.
[10] J. Douglas Carroll and Jih-Jie Chang- Analysis of individual differences in multidimen- sional scaling via an n-way generalization of "Eckart- "Eckart-Young" decomposition. Psychometrika, 35(3):283-319, September 1970.
[11] Benjamin Paul Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael M. Bronstein, Beltrami flow and neural diffusion on graphs. CoRR, abs/21 10.09443, 2021.
[12] Benjamin Paul Chamberlain, James Rowbottom, Maria I. Gorinova, Stefan D. Webb, Emanuele Rossi, and Michael M. Bronstein. GRAND: Graph Neural Diffusion. In The Symbiosis of Deep Learning and Differential Equations, September 2021.
[13] Benjamin Paul Chamberlain, James R. Rowbottom, Maria I. Gorinova, Stefan Webb, Emanuele Rossi, and Michael M. Bronstein. Grand: Graph neural diffusion. In ICML, 2021.
[14] Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph- structured data. In International Conference on Machine Learning, pages 1576-1586. PMLR, 2020.
[15] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[16] Ilya Chevyrev and Harald Oberhauser. Signature moments to characterize laws of stochastic processes. arXiv:1810.1099 10971 [math, stat], 2018.
10

---

[17] Thomas Cochrane, Peter Foster, Varun Chhabra, Maud Lemercier, Terry Lyons, and Cristopher Salvi. Sk-tree: a systematic malware detection algorithm on streaming trees via the signature kernel. In 2021 IEEF International Conference on Cyber Security and Resilience (CSR), pages 35-40. IEEE, 2021.
[18] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[19] Persi Diaconis. Group representations in probability and statistics. Lecture notes-monograph series, 11:i-192, 1988.
[20] Ahmed A. A. Elhag, Gabriele Corso, Hannes Stärk, and Michael M. Bronstein. Graph anisotropic diffusion, 2022.
[21] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference Learning Representations, 2019.
[22] Michel Fliess. Fonctionnelles causales non linéaires et indéterminées non commutatives. Bulletin de la société mathématique de France, 109:3-40, 1981.
[23] Bernard Gaveau. Principe de moindre action, propagation de la chaleur et estimees sous elliptiques sur certains groupes nilpotents. Acta Mathematica, 139(none):55-153, January 1977.
[24] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning. pages 2263-1272. PMLR, 2017.
[25] Daniele Grattarola and Cesare Alippi. Graph neural networks in tensorflow and keras with spektral [application notes]. IEEE Computational Intelligence Magazine, 16(1):99-106, 2021.
[26] Alexander Grigoryan. Heat kernel and analysis on manifolds, volume 47. American Mathemat- ical Soc., 2009.
[27] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[28] Ben Hambly and Terry Lyons. Uniqueness for the signature of path of bounded variation and the reduced path group. Ann. of Math., 171(1):109-167, 2010. 2010.
[29] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016
[31] Lars Hörmander. Hypoelliptic second order differential equations. 119:147-171, 1967.
Acta Mathematica,
[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[33] Thomas Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations, 2017.
[34] Franz J. Kiraly and Harald Oberhauser. Kernels for sequentially ordered data. J. Mach. Learn. Res., 20(31):1-45, 2019.
[35] Johannes Klicpera, Stefan Weissenberger, and Stephan Günnemann. Diffusion improves graph learning, ArXiv, abs/191 1.05485, 2019.
[36] Risi Kondor. Diffusion kernels graphs and other discrete structures. In ICML 2002, 2002.
11

---

[37] Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images. speech, and time series. The handbook of brain theory and neural networks, 3361((0):1995, 1995.
[38] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1
1998.
[39] Darrick Lee and Robert Ghrist. Path Signatures on Lie Groups. arXiv:2007.06633 [cs, math, stat], 2020.
[40] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International conference on machine learning, pages 3734-3743. PMLR, 2019.
[41] Yujia Li, Richard Zemel, Mare Brockschmidt, and Daniel Tarlow. Gated graph sequence neural networks. Proceedings of ICLR' 16, 2016.
[42] Iyy Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. In ICLR, 2017.
[43] Haggai Maron, Heli graph networks. Advances in neural information processing systems, 32, 2019.
Hadar Serviansky, and Yaron Lipman. Provably powerful
[44] Ron Milo, Shai Chen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri B. Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298 5594:824-7, 2002.
[45] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017.
[46] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gau- rav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher- Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):4602-4600 July 2019.
[47] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8. page 1, 2012.
[48] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. Advances in Neural Information Processing Systems, 33:16211-16223 2020.
[49] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[50] Ladislav Rampášek and Guy Wolf. Hierarchical graph neural nets can capture long-range interactions. In 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing (MLSP), pages 1-6. IEEE, 2021.
[51] Linda Preiss Rothschild and Elias M. Stein. Hypoelliptic differential operators and nilpotent groups. Acta Mathematica, 137:247-320, 1976.
[52] Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. In NIPS, 2014.
[53] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
[54] Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018
[55] Alice Schwarze and Mason Porter. Motifs for processes on networks. SIAM Journal on Applied Dynamical Systems, 20(4):2516-2557 2021.
12

---

[56] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. magazine, 29(3):93-99, 93, 2008.
[57] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneeman. Pitfalls of graph neural network evaluation. arXiv preprim arXiv: 18058668 2018.
[58] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-1958, 2014.
[59] Robert Strichartz. Sub-ricmannian geometrr Journal of Differential Geometry, 2242)221-622 1986.
[60] Matthew Thorpe, Tan Minh Nguyen, Hedi Xia, Thomas Strohmer, Andrea Bertozzi, Stanley Osher, and Bao Wang. GRAND++: Graph neural diffusion with a source term. In International Conference on Learning Representations, 2022.
[61] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature, 2021.
[62] Csaba Toth, Patric Bonnier, and Harald Oberhauser. Seq2Tens: An Efficient Representation of Sequences by Low-Rank Tensor Projections. In International Conference on Learning Representations, 2021.
[63] N Th Varopoulos. Analysis and geometry on groups. Cambridge Tracts in Math., 100, 1992.
[64] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[65] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[66] Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. ICLR, 2016.
[67] Nikil Wale, Ian A. Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, March 2008.
[68] Wolfgang Woess. Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathe- matics. Cambridge University Press, Cambridge, 2000.
[69] Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3-19, 2018.
[70] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems,
2021.
[71] Louis-Pascal A. C. Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In Proceedings of the 37th International Conference on Machine Learning, ICML'20, pages 10432-10441. JMLR.org, July 2020.
[72] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[73] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462. PMLR, 2018.
13

---

[74] Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren. William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling, In Pro- ceedings of the 32nd International Conference Neural Information Processing Systems, NIPS'18, 18, pages 1805-4815, Red Hook, NY, USA, December 2018. Curran Associates Inc.
[75] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In seioly AAAI conference on artificial intelligence, 2018.
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] While our approach is less susceptible the "over-squashing" phenomenon and empirically performs well on learning long-range interactions, we find that our methods are less beneficial for inductive learning tasks. This is stated explicitly in Section with experiments shown in Appendix H.33
(c) Did you discuss any potential negative societal impacts of your work? [No] This article introduce a method which can improve the performance on graph neural networks. We don't t think there are any foreseeable negative societal impacts beyond generic points that apply to any graph learning method.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [es]]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All theorem statements contain the full set of assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs all of our theoretical results are contained in the appendix, with specific references to sections within the main text.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes]. see Appendix
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they chosen)? [Yes] This is detailed in Section with further discussion Appendix H.2 (c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Ye]] All experiments standard deviation over these seeds is provided.
run using multiple seeds, and the
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix H
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] We include it in our code.
(c) Did you include any assets either in the supplemental material
URL.? [Yes]
We include code as part of supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're 'r
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "xxARTBOw3G", "reviewer": "Reviewer_f1qr", "summary": "In this work the authors present a formalism where a tensor valued version of the graph laplacian, which they call the hypo-elliptic graph laplacian, is used to model the distribution of node attribute propagation via random walks as a diffusion process. They show how the solutions for the state of the resulting system after length k walks can be computed via low rank approximation algorithms and compare a concrete realization of their method to other common architectures for graph modeling. They argue that their method excels in representing long range dependencies while scaling more favorably than other approaches in the size of the graph.", "questions": "1. Is there a reason why $m$ and $k$ are not used a bit more interchangeably? It seems like that dimension of cross product space and the sequence lengths we are lifting are practically the same? \n2. Can you describe the meaningful difference if any of thinking of elements of H as the m-dimensional cross of the node attributes along the path, rather than each sequence element individually as lifted to $(\\mathbb{R}^{d})^{\\otimes m}\\$? (I think no, this is part of the elegance of the setup?)", "limitations": "1. Somewhat duplicated from above, I am concerned about the $m=2$ restriction of the implementation results presented. It seems like this may take the power out of the method in some sense by barely maintaining the added depth/tensorial nature beyond the classical diffusion equation using the normal graph laplacian. Further, and this is _just a conjecture_, but it is possible that this limitation on $m$, plus the rank-1 approximation scheme is responsible for the shakeout of the results wrt the GraphTrans competitive baseline. Interested to hear the authors discuss this further.\n\n2. The scalability of the approach may be problematic given that the complexity analysis already relies on the Rank-1 approximation and also contains an $M^2$ term suggesting that the small M setting may be a requirement for practical implementations. Without demonstration on graphs of realistic scales (well beyond 30 nodes), as well as the resultant larger graph diameters and path lengths, it's unclear whether the approach has to always be nearly reduced to the classical setting in order to applied to graphs of non-trivial sizes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "###  Strengths\n\n**Quality/Clarity**: Sections 1-3 (along with the relevant appendices) are very well written, and do a remarkable job at providing an understanding of the background machinery required to understand the proposed method. In particular, the punchline results through Eq. 11 and 12 about the theoretical expressivity in node and graph representation extractable from the solution to the hypo-elliptic graph diffusion equation are exciting. \n\n**Originality**: Benefit of the doubt is granted on the overall presentation of the formalism being novel (reviewer is not a theorist), though I assume novelty is mostly concentrated on the tensor valued version of the diffusion equation, Eq 11.\n\n### Weaknesses\n\n**Clarity**: The work is remarkably readable, but there are a couple points:\n- At the moment one reads line 105, it _is not_ immediately clear that we have built the map between $Seq(\\mathbb{R}^d)$ and $H$, rather it should cite Appendix lines 612-618 as these are sort of the final step of that construction.\n- The section on the low rank approximation of the functionals and the \"Building Neural Networks\" section is much harder to understand than the sections that precede it.\n\n**Significance**: Despite the theoretical expressivity of the proposed model class, the particular setting evaluated only explores a max tensor degree of 2. This seems like a severely restricted realization of the model based on my understanding that $m$ sort of represents the dimension of the \"summary capturing\" capacity of the lifted form of the diffusion solution. The method only performs _competitively_ with GraphTrans. Ideally, since it's being proposed as an alternative to the family of available GNNs, the implementation results will be more developed in future work to more convincingly demonstrate the benefits in practice that the framework argues that it offers in theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XiMD1VvG6z5", "reviewer": "Reviewer_foUs", "summary": "In graph neural networks, convolutional layers operate by aggregating information about local neighborhood structures. This paper extends to hypo-elliptic diffusions and the derived tensor valued graph operator. \n\nIn short, this paper builds the operators by using random walks but instead of taking only the endpoints of random walks, takes averages over path-dependent functions. Here the ordering of vertices visited in a random walk matters. Using random walks to build feature vectors for graphs is a classical idea (e.g., Deepwalk), which has also been extended to other local graph features such as breadth-first trees etc (e.g., Node2Vec). This paper uses the entire path rather than the endpoint and build an algebraic operator. \n\n\n", "questions": "There are a few issues that the authors can possibly address/discuss:\n\n\t1. About descriptive power, is there theoretical understanding that the hypo-elliptic diffusion is strictly more powerful than just using regular heat diffusion on graphs? \n\t2. There seems to be a tradeoff between computational cost vs results of the model via parameters such as k, the length of random walks, and R the rank of the functionals. Could the authors discuss the influence of these parameters in model performance?\n\t3. The results are comparable to earlier work that uses a Transformer model with graph neural networks (GraphTrans), which captures long-term interactions. The discussion at the end of section 5 regarding the performance comparison of this method and Transformer is a bit wishful. Can the authors provide more solid results backing up the discussion here (e.g., the summaries in this paper can also help Transformer submodule)? \n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The approach of extension from using only endpoint of a random walk to the entire path of the random walk is natural. The paper presented a theorem (Theorem 2) which says that two labelled graphs are the same if and only if the distribution of k-step random walks of the two graphs are the same. The authors use diffusion over tensor transition matrix and introduce an attention mechanism. The paper explained how to efficiently calculate the operator on a graph.  \n\nWeaknesses: see next box on questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I3B1CpfLDMG", "reviewer": "Reviewer_zTgE", "summary": "The paper introduces hypo-elliptic graph Laplacians -- a generalization of classical graph Laplacians to higher order tensors -- that are capable of storing the entire history of a given random-walk. This is studied in the context of attributed graphs where each node is equipped with vector information. Theoretical analysis is carried over to demonstrate that 1) the analogous tensor-like diffusion process retains the probabilistic interpretation of standard scalar random walks and 2) graph feature maps can be defined on these processes w/o losing expressive power. A low-rank approximation is provided to make the approach scalable and experiments are conducted on datasets that present long-range dependencies. ", "questions": "- While the problem is relevant, the solution is somewhat not surprising. If we store more information directly via tensors, then this will avoid aggregating information from distant nodes along the 1-hops only hence alleviating the over-squashing phenomenon. A perhaps more interesting analysis should entail what this higher-order approach is effectively accomplishing. Is it `just' a matter of storing higher-order (i.e. non-local) information? Do we actually need random walks exactly or a higher-order approach that store information without leveraging the algebra representation is going to accomplish similar results? What does such method give us when compared to more standard MPNNs like, say GIN, when augmented with JK connections for example? I don't expect a specific answer here but some speculation might improve the message.\n- In the proof of Theorem 3 I believe there is a typo in the proof of the case for $f_{1,m}$ where we should have $\\frac{1}{d_{i}m!}\\prod_{r= M - m +1}^{M}\\langle u_{r},f(j)-f(i)\\rangle$.\n- Some analysis of the number of parameters might be relevant here. How do you compare to baselines?\n-  A clock experiment comparing running time of GT2N/GT2(A)N with baselines would also be important here. \n- The size of the random walk is chosen to be 5 on the molecular datasets: how would that compare to the average diameter of the graphs? Is in fact this quite a `global' approach already?\n- Why in the experiment section you only compare with [64] on some of the datasets used in [64] and not all of them? A comparison with Table 2 in [64] would appear meaningful here.\n\n\nConclusions: The paper is novel and the idea of relying on the algebra representations to memorize the full history of the attributed random walk is an elegant formalization of an idea that has entered existing `tricks' one way or another. Of relevance the proposed approximation in Theorem 3. There are a few questions partly left-unanswered. As mentioned above, how the questions are addressed may affect the final score (in both ways). ", "limitations": "Societal impact is not reported. Limitations are partly addressed in the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Contribution and novelty: To my knowledge -- I am not an expert in the field of hypo-elliptic operators on non-Euclidean domains -- the contribution of the paper is original. This applies to both the theoretical analysis in Theorem 1,2 and the low-rank approximation in Theorem 3 that builds on previous work in [56].\n\nPresentation: The paper is very well-presented and the organisation does not require main modifications. On a minor side, some of the paper is quite technical and potentially obscure to a significant part of the community.\n\nStrengths (in random order):\n\n- The exposition is clear.\n- The problem at hand is of interest, given that standard MPNNs are known to struggle on tasks with long-range dependencies, mainly due to the problem of over-squashing.\n- The theoretical analysis in Theorem 3 is of relevance in the context of the tools and techniques introduced, given that it provides a scalable approach.\n- The implementation/experiment section has detailed explanation with sufficient ablation studies that strengthen the message and indeed highlight the robustness of the method.\n\n\nWeaknesses (in random order) -- I reserve some unanswered points to the Questions paragraph below; depending on the rebuttal such points could be solved or become weaknesses with consequent adjusting of the score.\n\n- Theorem 3 inevitably leads to a loss in expressive power and it is not entirely clear how the loss would depend on M, and R (minor point).\n- The proposed method is not (significantly) better than faster/standard GNN methods on task like node-classification where long-range dependencies may not be crucial. This is somewhat expected but it limits the impact of the approach. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "86-SCCzqNjo", "reviewer": "Reviewer_sq7T", "summary": "The authors present a novel version of the graph Laplacian which instead of capture information focused on start/end of a path, it emphasizes information along paths. This is inspired on previous notions of the hypo-elliptic Laplacian. Moreover, since the hypo-elliptic graph laplacian is a tensor-valued graph operator, the authors provide low-rank approximations which allow numerical computations, is it scales linearly with the number of edges, contrary to the standard case which grows quadratically with the number of nodes.\n\nTogether with the Hypo-elliptic Laplacian another key ingredient is the perspective of free algebras, which is relevant since the order in which nodes visited in a path is relevant, and free algebras induce algebra multiplication that are non-commutative.\n\n", "questions": "I understand that the proposed numerical scheme is presented in Theorem 3, but I would suggest to introduce a pseudo code. In general that would allow the readers to have a specific module where one can focus on explicit programatic steps, rather than having to follow non-programmatic terminology that naturally corresponds to a theorem.\n\nFurther, the authors describe the complexity to be O(K · M^2 · N_E + M · N_E · d) where $M$ is the maximum tensor degree, $N_E$ is the number of edges, $d$ is the dimension of node attributes. Given all these terms in complexity, would it be possible for the authors to report the execution time? I think this would be relevant for the reader, as for instance, the number of edges in the datasets ($N_E$) is not reported in the paper. Further, it is not that straight forward to track the values for the remaining parameters involved in the algorithm complexity. Providing the parameter values of the algorithm complexity, potentially in the supplementary material,  per dataset and model would be of great benefit.", "limitations": "It seems the authors do not provide potential negative societal impacts.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper does a great job to briefly introduce the basic notions related to the hypo-elliptic graph and the corresponding free algebra notions that are required to grasp the basic intuitions of the concepts here considered. Further, supporting material is presented in the supplementary material that helps to grasp basic concepts related to this paper.\n\nThe presents an interesting modeling approach by showing/motivating that the proposed Laplacian indeed has certain properties that might be appealing in the context of learning long dependencies for GNNs. The analysis of the path, and not only relying on where it starts and where it ends has already been suggested, for instance (in a different context) by the non-back tracking operator (or the corresponding Bethe Hessian), even in the context of spectral clustering, where the graph Laplacian plays a crucial role [A].\n\nBibliography\n[A]. Saade, Alaa, Florent Krzakala, and Lenka Zdeborová. \"Spectral clustering of graphs with the bethe hessian.\" Advances in Neural Information Processing Systems 27 (2014).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept