Directional graph networks
Authors: Dominique Beaini
Saro Passaro
Vincent Letourneau
William L. Hamilton
Gabriele Corso
Pietro Liò
Venue:  (2021)
Keywords: graph
neural networks
deep learning
spectral theory
directional aggregation
over-smoothing

Abstract: In order to overcome the expressive limitations of graph neural networks (GNNs), we propose the first method that exploits vector flows over graphs to develop globally consistent directional and asymmetric aggregation functions. 
We show that our directional graph networks (DGNs) generalize convolutional neural networks (CNNs) when applied on a grid. Whereas recent theoretical works focus on understanding local neighbourhoods, local structures and local isomorphism with no global information flow, our novel theoretical framework allows directional convolutional kernels in any graph.
First, by defining a vector field in the graph, we develop a method of applying directional derivatives and smoothing by projecting node-specific messages into the field. 
Then we propose the use of the Laplacian eigenvectors as such vector field, and we show that the method generalizes CNNs on an $n$-dimensional grid, and is provably more discriminative than standard GNNs regarding the Weisfeiler-Lehman 1-WL test.
Finally, we bring the power of CNN data augmentation to graphs by providing a means of doing reflection, rotation and distortion on the underlying directional field. We evaluate our method on different standard benchmarks and see a relative error reduction of 8% on the CIFAR10 graph dataset and 11% to 32% on the molecular ZINC dataset. An important outcome of this work is that it enables to translate any physical or biological problems with intrinsic directional axes into a graph network formalism with an embedded directional field. 

Under review as a conference paper at ICLR 2021
DIRECTIONAL GRAPH NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In order to overcome the expressive limitations of graph neural networks (GNNs), we propose the first method that exploits vector flows over graphs develop glob- ally consistent directional and asymmetric aggregation functions. We show that our directional graph networks (DGNs) generalize convolutional neural networks (CNNs) when applied on grid. Whereas recent theoretical works focus on un- derstanding local neighbourhoods, local structures and local isomorphism with no global information flow, our novel theoretical framework allows directional con- volutional kernels any graph. First, by defining vector field in the graph, we develop method of applying directional derivatives and smoothing by projecting node-specific messages into the field. Then we propose the use of the Lapla- cian cigenvectors such vector field, and we show that the method generalizes CNNs on an n-dimensional grid, and is provably more discriminative than stan- dard GNNs regarding the Ceisfeiler-Lehman 1-WL test. Finally, we bring the power of CNN data augmentation to graphs by providing a means of doing reflec- tion, rotation and distortion on the underlying directional field. We evaluate our method on different standard benchmarks and see a relative error reduction of 8% on the CIFARIO graph dataset and 11% 32% on the molecular ZINC dataset. An important outcome of this work is that it enables to translate any physical or biological problems with intrinsic directional axes into a graph network formalism with an embedded directional field.
INTRODUCTION
One of the most important distinctions between convolutional neural networks (CNNs) and graph neural networks (GNNs) is that CNNs allow for any convolutional kernel, while most GNN methods are limited to symmetric kernels (also called isotropic kernels in the literature) (Kipf & Welling 2016 Xu al. 2018a Gilmer et 2017). There
implementation of asymmetric kernels using gated mechanisms (Bresson & Laurent 2017, Veličković et al., 2017), motif attention (Peng al. 2019), edge features (Gilmer et al.] 2017) or by using the 3D structure of molecules for
message passing (Klicpera et al. 2019).
However, to the best of our knowledge, there are currently methods that allow asymmetric graph kernels that are dependent on the full graph structure or directional flows. They either depend on local structures or local features. This is in opposition images which exhibit canonical directions: the horizontal and vertical axes. The absence of an analogous concept in graphs makes it difficult define directional message passing and to produce an analogue of the directional frequency filters (or Gabor filters) widely present in image processing (Olah et al. 2020).
We propose novel idea for GNNs: use vector fields in the graph define directions for the prop- agation of information, with an overview of the paper presented in [ Hence, the aggregation or message passing will be projected onto these directions so that the contribution of each neighbour- ing node n. will be weighted by its alignment with the vector fields at the receiving node nu. This enables our method to propagate information via directional derivatives or smoothing of the features.
We also explore using the gradients of the low-frequency eigenvectors of the Laplacian of the graph Φr. since they exhibit interesting properties (Bronstein et al. 2017 Chung et al. 1997). In particular, they can be used to define optimal partitions of the nodes in graph, to give natural ordering (Levy) 2006), and to find the dominant directions of the graph diffusion process (Chung & Yau 2000). Further, we show that they generalize the horizontal and vertical directional flows in a grid (see

---

Under review as a conference paper at ICLR 2021
computmd steps ((FF)
Graph neural network steps Olk? + RN)
Irput graphs
Computa Trat noll-
trtuial
Compute the gradien
Create the aparapaiion
Inpul graph
ghoccuiin features
Agarogaiian
MIP
agrmpriion
orporeay roaris
and sottd
fuartoe of adges
romralleed by
addo frouuecci
lranned paraintess
We computa
give us unitpu,
theigh har the owan non-
por eqgeooals und du
18, 6, 9, Bithernis..
mett) uuch
apprgattor mattic
dive X8 the
netaninants the
to the dig antiiuutss of
the about
lased on GDM anhedd
agging otion
This tepii the nost
crectera snartingmadr
ONN leye
yours festerss
modis
in the wamiirr of
and ara
coepaato lisist rigneoriees with compllutty 004)
experato zompusatinaly
Nade coloroop
thtt pwwppphhhecccaeene dirccton, enosced re wisi sn sing Fi
Field matrly coformap
(RL)) das
the denctional deviotio nattle
namber todke)
2 ht nove 20w
eamber lepat
mwwoppraation
takes Jrie
foau aecree
the ageragrtcn ma
acteandyy masie jetth
posa regariv we artts
Other nar dinectional
with
yelo
compleiity (MRg.
uet number heutures
the
skkn from
the manie Adprngrtiss
Thers
compuuee stacs
o "aag",,
Graph
rasr sing marti yr the rppreputions the comppie loats digur)) wittl or 0rtig rhe eggnnget enn are leciod
has g2t - 33%
(o la aahi
(4g. 201y
x MAR(000)
Noat GNN
2- 2-4. gil Vift pell
Figure I: Overview of the steps required to aggregate messages in the direction of the eigenvectors.
figure 2). allowing them to guide the aggregation and mimic the asymmetric and directional kernels present in computer vision. In fact, we demonstrate mathematically that our work generalizes CNNs by reproducing all convolutional kernels of radius in an n-dimensional grid, while also bringing the powerful data augmentation capabilities of reflection, rotation or distortion of the directions.
We further show that our directional graph network (DGN) model theoretically and empirically allows for efficient message passing across distant communities, which reduces the well-known problem of over-smoothing, and aligns well with the need of independent aggregation rules (Corso
al. 2020). Alternative methods reduce the impact of over-smoothing by using skip connections (Luan et al., 2019). global pooling (Alon & Yahav) 2020), or randomly dropping edges during training time Rong al. 2020)), but without solving the underlying problem. In fact, we also prove that DGN is more discriminative than standard GNNs in regards to the Weisfeiler-Lehman 1-WL test, showing that the reduction of over-smoo accompanied by an increase of expressiveness.
Our method distinguishes itself from other spectral GNNs since the literature usually uses the low frequencies estimate local Fourier transforms in the graph (Levie et al., 2018, Xu et al. 2019). Instead, we do not try to approximate the Fourier transform, but only to define directional flow at each node and guide the aggregation.
2 THEORETICAL DEVELOPMENT
2.1 INTUITIVE OVERVIEW
One of the biggest limitations of current GNN methods compared to CNNs the inability to do message passing in a specific direction such as the horizontal one in a grid graph. In fact, it is difficult to define directions or coordinates based solely on the shape of the graph.
The lack of directions strongly limits the discriminative abilities of GNNs to understand local struc- tures and simple feature transformations. Most GNNs are invariant to the permutation of the neigh- bours' features, the nodes' received signal is not influenced by swapping the features of neigh- bours. Therefore, several layers in a deep network will be employed to understand these simple changes instead of being used for higher level features, thus over-squashing the message sent be- tween 2 distant nodes (Alon & Yahay 2020).
In this work, one of the main contributions is the realisation that low-frequency eigenveetors of the Laplacian can overcome this limitation by providing a variety of intuitive directional flows. As a first N
example, taking grid-shaped graph of size N M with Y < M < N, we find that the eigenvector
2

---

Under review as a conference paper at ICLR 2021
associated to the smallest non-zero eigenvalue increases in the direction of the width N and the second one increases in the direction of the height M. This property generalizes to n-dimensional grids and motivated the use of gradients of cigenvectors preferred directions for general graphs.
We validated this intuition by looking at the flow of the gradient of the cigenvectors for vari- ety of graphs, as shown in figure 2 For example, in the Minnesota map, the first 3 non-constant eigenvectors produce logical directions, namely South/North, suburb/city, and West/East.
Another important contribution also noted in figure is the ability to define any kind of direction based on prior knowledge of the problem. Hence, instead of relying on eigenvectors to find direc- tions in map, we can simply use the cardinal directions the rush-hour traffic flow.
Examples of eigenvector based directions
Exemples inductive bias based directions
acos d
2c0s
[a] Non-dlagonal ard graph 5)
Mode
Edge
propapelicn change defect the cryatal
vilcss
gnddant
Drus iccapraa lntie,
duppoul glaand)
(b] graph
Dirccion out the global centroal
(cl
vania carlic mar rngirter andtle
ewery
Mirnwuste road map
Figure 2: Possible directional flows different types of graphs. The node coloring potential map and the edges represent the gradient of the potential with the arrows in the direction of the flow. The first 3 columns present the arcosine of the normalized eigenvectors (acos Φ) node coloring, and their gradients represented as edge intensity. The last column presents examples of inductive bias introduced in the choice of direction. (a) The eigenvectors 1 and 2 are the horizontal and vertical flows of the grid. (b) The eigenvectors and are the flow in the longest and second- longest directions. (c) The eigenvectors 1, 2 and flow respectively in the South-North, suburbs to the city center and West-East directions. We ignore do since it is constant and has no direction.
2.2 VECTOR FIELDS IN A GRAPII
Based on a recent review from Bronstein et al. (017)), this section presents the ideas of differential geometry applied to graphs, with the goal of finding proper definitions of scalar products, gradients and directional derivatives.
Let G (V, F)) be graph with V the of vertices and F V V the set of edges. The graph undirected meaning that (i. E E iff (j. i) E E. Define the vector spaces (V) and T.2 as the set of maps V IR and E R with y (VV and F, H E I. (F) and scalar products
(x, LP(V) = Σ a.yk
(F,H)LA(E) = Σ Fus)
SEV
(LE))
Think of E the "tangent space" to V and of (2(E) the set of "vector fields" on the space V with each row F., representing a vector at the i-th node. Define the pointwise scalar product as the map T,2 (F) x (FE) ~ T.2 (V) taking vector fields and returning their inner product each point of V, at the node is defined by equation 2
H
E Fig Hig
In equation we define the gradient V mapping (VV (E) and the divergence div mapping L LE) + (V),,, thus leading to an analogue of the directional derivative in equation
(V = xxi) =x(i)
(div F) = Σ F(s)
JOJEE
3

---

Under review as a conference paper at ICLR 2021
Definition 1. The directional derivative of the function the graph G in the direction of the vector field F where each vector is of unit-norm
(iz( = (Vx. F);
Σ (=(1) xx())
(4)
j((5))E
| will denote the absolute value F and |1 the norm of the i-th row of F. We also define the forward/backwant directions as the positive/negative parts of the field F#.
2.3 DIRECTIONAL SMOOTHING AND DERIVATIVES
Next, we show how the vector field F used to guide the graph aggregation by projecting incoming messages. Specifically, we define the weighted aggregation matrices Buv and B that allow to compute the directional smoothing and directional derivative of the node features.
The directional average matrix Bav is the weighted aggregation matrix such that all weights positives and all rows have an -norm equal to 1, as shown in equation 5 and theorem 2.1 with a proof in the appendix C.I C.I
F.
(5) The variable is an arbitrarily small positive number used to avoid noating-point errors. The T,-- norm denominator is local row-wise normalization. The aggregator works by assigning large weight to the elements in the forward or backward direction the field, while assigning a small weight to the other elements, with total weight of 1.
Bay (F).: P.ollz +
Theorem 2.1 (Directional smoothing). The operation = Ba the directional average of x, in the sense that yu is the mean of wv weighted by the direction and amplitude of F.
The directional derivative matrix Baz defined in (6) and theorem 2.2 with the proof in ap- pendix C.2 Again, the denominator is local row-wise normalization but can be replaced by global normalization. diag(a) (a) is a square, diagonal matrix with diagonal entries given by a. The aggregator works by subtracting the projected forward message by the backward message (similar to center derivative), with an additional diagonal term to balance both directions.
F.
B (F) F... diag Σ
F,, [ +
(6)
Theorem 2.2 (Directional derivative). Suppose have rows of unit Lt- norm. The operation =
B F) is the centered directional derivative of x in the direction of F, in the sense of equation L.e.
y = D (F-diay,
Σ F.s))
These aggregators are directional, interpretable and complementary. making them ideal choices for GNNs. We discuss the choice of aggregators in more details in appendix [A] while also provid- ing alternative aggregation matrices such as the center-balanced smoothing. the forward-copy. the phantom zero-paddie eeto-padding. and the hardening of the aggregators using softmax/argnan further provide a visual interpretation of the Bav and B& aggregators in figure 3 Interestingly, we also note in appendix that Bav and Baz yield respectively the mean and Laplacian aggregations when is vector field such that all entries are constant Fij = +C.
the field. We
Graph features focused the neighbourhood nt Directional smoothing agpregation (F)x f
Directional derivative aggregation By (F)x
FALL
Fra, 18, + |Faay Xu, Fox, Xux
Fax. Fx,, - xx) Fau. (Nu,- Xu.) + Fou X.y)
Fau. + Fox, + |Fuud
Pan, + F Frny)
recekingg Ne ghiporounggg rade
Absulute weighted sum
demisthv
with
5, Feottur ot node
Sum of the absolute weights
Sum the absollute weightts
Fu.
Figure 3: Illustration of how the directional aggregation works at a node n,, with the arrows repre- senting the direction and intensity of the field F.
4

---

Under review as a conference paper at ICLR 2021
2.4 GRADIENT OF THE EIGENVECTORS INTERPRETABLE VECTOR FIELDS
In this section we give theoretical support for the choice of gradients of the eigenfunctions of the Laplacian sensible vectors along which to do directional message passing since they inter- pretable and allow to reduce the over-smoothing.
As usual the combinatorial, degree-normalized and symmetric normalized Laplacian are defined
- Lnorm D-
Laym
LD-
The problems of over-smoothing and over-squashing are critical issues in GNNs Alon & Yahav, 2020 [ammlloon 2020). In most GNN models, node representations become over-smoothed after several rounds of message passing (i.e., convolutions), as the representations tend to reach mean- field equilibrium equivalent to the stationary distribution of a random walk (Hamilton 2020). Over- smoothing is also related the problem of werrssqushhng, which reflects the inability for GNNs to propagate informative signals between distant nodes (Alon & Yahav (020) and is major bottleneck to training deep GNN models (Xu et al. 2019). Both problems are related to the fact that the influence of one node's input on the final representation of another node in a GNN is determined by the likelihood of the nodes co-occurring on truncated random walk (Xu et al. 2018b).
We show in theorem 2.3 (proved in appendix C.3) that by passing information in the direction of Φi, the eigenvector associated the lowest non-trivial frequency of Lnomn DGNs efficiently share information between the farthest nodes of the graph, when using the K-walk distance to measure the difficulty of passing information. Thus, DGNs provide natural way address both the over- smoothing and over-squashing problems: they can efficiently propagate messages between distant nodes and in a direction that counteracts over-smoothing.
Definition 2 (K-walk distance). The K-walk distance dx (v,, of times vú is hit in a K step random walk starting from V/-
graph is the average number
Theorem 2.3 (K- IK-Gradient of the low-frequency eigenvectors). Let X and Φs be the eigen- values and eigenvectors of the normalized Laplacian of a connected graph Lnorm and let (v;, U,)] be the nodes that have highest K-walk distance. Let m = a, b = arg max (d arg (01); and M arg mani (81);s then dg (Ums Uss) (Va vo) has order 0(1-A2)
As another point of view into the problem of oversmoothing, consider the hitting time Q(a, y) defined as the expected number of steps random walk starting from node x ending in node y with the probability transition P(x, y) J. In appendix C.4 we give informal argument supporting the following conjecture.
Definition (Gradient step). Suppose the two neighboring nodes x and are such that ((=) ((x) maximal among the neighbors of x, then we will say z is obtained from x by taking a step in the direction of the gradient VΦ.
Conjecture 2.4 (Gradient steps reduce expected hitting time), Suppose that x, are uniformly dis- tributed random nodes such that Φi(z) < <2)))) Let be the node obtained from x by taking one step in the direction of V db. then the expected hitting time is decreased proportionally to X; and
Ez, (2, v)1 S [2,, v)l
The next two corollaries follow from theorem 2.3 (and also conjecture 2.4 if is true).
Corollary 2.5 (Reduces over-squashing). Following the direction of V is an efficient way of passing information between the farthest nodes of the graph (in terms of the K-walk distance).
Corollary 2.6 (Reduces smoothin) Following the direction of V allows the irfluence dis- tribution between node representations to be decorrelated from random-war walk hitting times (assuming the definition of influence introduced in Xu et al. (2018b)).
Our method also aligns perfectly with a recent proof that multiple independent aggregators are needed to distinguish neighbourhoods of nodes with continuous features (Corso et al. 2020).
When using eigenvectors of the Laplacian o; to define directions in a graph, we need to keep in mind that there is never single eigenvector associated to an eigenvalue, but whole eigenspace.
5

---

Under review as a conference paper at ICLR 2021
For instance, pair of eigenvalues can have multiplicity of meaning that they be generated by different pairs of orthogonal eigenvectors. For an eigenvalue of multiplicity 1, there are always two unit norm eigenvectors of opposite sign, which poses problem during the directional aggregation. We can make a choice of sign and later take the absolute value (i.e. Bad in equation 5 An alterna- tive is to take sample of orthonormal basis of the eigenspace and use each choice augment the training (see section 2.8 Although multiplicities higher than one do happen for low-frequencies (square grids have multiplicity 2 for A1) this is not common in "real-world graphs" we found no a multiplicity greater than on the ZINC and PATTERN datasets (see appendix [B.4). Further, although all Φ are orthogonal, their gradients, used define directions, are not always locally or- thogonal (e.g. there are many horizontal flows in the grid). This last concern is left to be addressed future work.
2.5 GENERALIZATION OF THE CONVOLUTION ON GRID
In this section we show that our method generalizes CNNs by allowing to define any radius- R convolutional kernels in grid-shaped graphs. The radius- R kernel at node u is a convolutional kernel that takes the weighted sum of all nodes at a distance d(u, v) S R.
Consider the lattice graph P of size N1 x N₂ x ... N, where each vertices are connected to their direct non-diagonal neighbour. We know from Lemma [. that, for each dimension, there is an eigenvector that is only a function of this specific dimension. For example, the lowest frequency eigenvector Φ always flows in the direction of the longest length. Hence, the Laplacian eigenvectors of the grid can play a role analogous to the axes in Euclidean space, as shown in figure 2
With this knowledge, we show in theorem 2.7 (proven in C.7) that tional kernels in an n-dimensional grid. This is a strong result since it demonstrates that our DGN framework generalizes CNNs when applied grid, thus closing the gap between GNNs and the highly successful CNNs on image tasks.
generalize all convolu-
Theorem 2.7 (Generalization radius-R convolutional kernel in a lattice), For n-dimensional lattice any convolutional kernel of radius R can be realized by a linear combination of directional aggregation matrices and their compositions.
As an example, figure shows how linear combination of the first and m-th aggregators ( Φ1m))) realize a kernel on an N x M grid, where m = [N/M] and N > M.
(w/l- 2w; B y
Graph aggregation
y= 28
y = 2B
y 28
y = 28
+ww, Bm + 2w: Bitl
CNN equivalent on image Jysue N > M
1y = 44
l
Wy
M2
N%6
+.00
Figure 4: Realization of a radius-1 convolution using the proposed aggregators. I is the input feature map, the convolutional operator, Ly the convolution result, and B = B(V).)
2.6 EXTENDING THE RADIUS OF THE AGGREGATION KERNEL
Having aggregation kernels for neighbours of distance 2 or 3 is important to improve the expres- siveness of GNNs, their ability to understand patterns, and to reduce the number of layers required. However, the lack of directions in GNNs strongly limits the radius of the kernels since, given graph of regular degree d, mean/sum aggregation at a radius- R will result in a heavy over-squashing of d messages. Using the directional fields, we can enumerate different paths, thus assigning a differ- ent weight for different R-distant neighbours. This method, proposed in appendix A.7 avoids the over-sguashing, but empirical results are left for future work.
2.7 COMPARISON WITH WEISFEILER-LEHNE (WL) TEST
We also compare the expressiveness of the Directional Graph Networks with the classical WL graph isomorphism test which is often used to classify the expressivity of graph neural networks (Xu et al.) 2018a). In theorem 2.8 (proven in appendix (C3) we prove that DGNs are capable of distinguishing pairs of graphs that the 1-WL. test (and ordinary GNNs) cannot differentiate.

---

Under review as a conference paper at ICLR 2021
Theorem 2.8 (Comparison with 1-WL test). DGNs using the mean aggregator, any directional aggregator of the first eigenvector and injective degree-scalers are strictly more powerful than the 1-WL test.
2.8 DATA AUGMENTATION
Another important result is that the directions in the graph allow to replicate some of the most common data augmentation techniques used in computer vision, namely reflection, rotation and distortion. The main difference is that, instead of modifying the image (such as a 5 rotation), the proposed transformation is applied on the vector field defining the aggregation kernel (thus rotating the kernel by -5" without changing the image). This offers the advantage of avoiding to pre-process the data since the augmentation is done directly on the kernel each iteration of the training.
The simplest augmentation is the vector field flipping, which is done changing the sign of the field F, as stated in definition 4 This changes the sign of Bad, but leaves Bav unchanged. Definition 4 (Reflection of the vector field). For vector field F, the reflected field is F.
Let F1, F2 be vector fields in a graph, with Fi and F2 being the field normalized such that each row has unitary norm. Define the angle vector by ((F1)s.: (F2)..) cos(a;). The vector field FL is the normalized component of F3 perpendieular Fi. The equation below defines F2. The next equation defines the angle
(F2 (Fi, F2) Ft).
FF k;: 11(P2 (Fi, F2) )..e
Notice that we then have the decomposition (F2)..: cos(a,)) (Fi)s, + sinaa)) )..-
Definition 5 (Rotation of the vector fields). For Fi and F2 non-colinear vector fields with each vector of unitary length. their rotation by the angle 0 in the plane formed by (F1, F2)
F Fi diag 0) + F Fy- diag(sin
Fe F; diagg(coos + F F +a)) (8)
Finally, the following augmentation has similar effect Definition (Random distortion the vector field). For vector field F and anti anti-symmetric random
distortion applied images.
noise matrix R, its randomly distorted field is F' F Ro A.
3 IMPLEMENTATION
We implemented the models using the DGL and PyTorch libraries and we provide the code at the address https://aoonymous.ooo.....cc www.eenncccincccc//a522eee..
We test our method on standard benchmarks from Dwivedi et al. (2020) and Hu et al. (2020), namely ZINC, CIFAR1O, PATTERN and MolHIV with more details on the datasets and how we enforce a fair comparison in appendix B.I
For the empirical experiments we inserted our proposed aggregation method two dif- ferent type of message passing architecture used in the literature: simple one simi- lar to the one present GCN (equation (9a] (Kipf & Welling (016) and more com- plex and general one typical of MPNN (9b) GGimmrr
al. 2017) with without edge features Ezt. Hence, the time complexity O(Em) is identical to the PNA (Corso et al. 2020), where E is the number of edges and the number of aggregators, with an ad- ditional O(Ek) to pre-compute the k-first eigenvectors, as explained the appendix B.2
x (1+1)
+ xx²0) (iE)EE
(9a)
X (1+1)
(())
+ M (GA)E
(x
x
(9b)
optional
where ④ is an operator which concatenates the results of multiple aggregators, X the node fea- tures, M is linear transformation and U multiple layer perceptron.

---

Under review as a conference paper at ICLR 2021
take the We tested the directional aggregators across the datasets using the gradient of the first & eigenvectors V as the underlying vector fields. Here, is a hyperparameter, usually or 2, but could be bigger for -igh-dimensional graphs. To deal with the arbitrary sign of the eigenvectors, absolute value of the result of equation 6 making it invariant to reflection of the field. In case of a disconnected graph, Ø; is the i-th eigenvector of each connected component. Despite the numerous aggregators proposed in appendix [A] only Baz and Bav are tested empirically.
4 RESULTS AND DISCUSSION
Directional aggregation Using the benchmarks introduced in section 3 fair comparison of various aggregation strategies using the same parameter budget and hyperparam- eters. We consistent boost in the performance for simple, complex and complex with edges models using directional aggregators compared to the mean- ggenn-gggregtoo baseline.
present in figure 5|
CIFAR10
Simple
Complex
Complex-E MAE
Simple
Complex
Simple
Complex
Simple
Aggregators
MAE
MAE
% acc
% acc
acc
% RUC
Best
mean
0.316
0.353
0.262
80.77
83.34
55.9
62.8
75.1
mean pos,
0.349
0.332
0.297
80.76
83.74
75.8
mean pos, pos,
0.344
0.330
0.284
84.51
61.25
76.1
mean dk,
0.296
0.233
0.191
84.22
83.44
78.0
mean
0.271
mean
0.317
0.332
83.21
mean
0.367
0.332
0.260
85.12
85.38
60.6
65.1
77.1
mean dx,
0,290
0.245
0.192
85.17
86.68
79.0
Figure 5: Test set results using a parameter budget of ~ 100k, with the same hyperparameters as Corso al. (2020). The low-frequency Laplacian eigenvectors are used define the directions, except for CIFARIO that uses the coordinates of the image. For brevity, we denote dx; and av; as the directional derivative Bi and smoothing B aggregators of the i-th direction. We also denote pos; as the i-th eigenvector used as positional encoding for the mean aggregator.
In particular, we see a significant improvement ZINC and MolHIV using the directional aggrega- tors. We believe this is due to the capacity to move efficiently messages across opposite parts of the molecule and to better understand the role of atom pairs. Further, the thesis that DGNs can bridge the gap between CNNs and GNNs is supported by the clear improvements CIFAR1O baselines. This contrasts with the positional encoding which showed no clear improvement.
the
With our theoretical analysis in mind, we expected perform well on PATTERN since the flow of the first cigenvectors are meaningful directions in a stochastic block model and passing messages using those directions allows the network to efficiently detect the two communities. The results match our expectations, outperforming all the previous models.
Comparison to the literature In order to compare our model with the literature, we fine-tuned it on the various datasets and we report its performance in figure [ We observe that DGN provides significant improvement across all benchmarks, highlighting the importance of anisotropic kernels. In the work by [Dwivedi et al.) (2020), they proposed the use of positional encoding of the eigen- vectors in node features, but these bring significant improvement when many eigenvectors and high network depths are used. Our results outperform them with fewer parameters, less depth, and only 1-2 eigenvectors, further motivating their use directional flows instead of positional encoding.
Data augmentation To evaluate the effectiveness of the proposed augmentation, we trained the models on reduced version of the CIFAR 10 dataset. The results figure show clearly higher expressive power of the dx aggregator, enabling it to fit well the training data. For small dataset, this comes at the cost of overfitting and a reduced test-set performance, but we observe that randomly rotating distorting the kernels counteracts the overfitting and improves the generalization.
As expected, the performance decreases when the rotation or distortion is too high since the aug- mented graph changes too much. In computer vision images similar CIFAR10 are usually rotated by less than 30 (Shorten & Khoshgoftaar Ga'a McGuinness) 2019). Further, due to the con- stant number of parameters across models, less parameters attributed the mean aggregation in
8

---

Rotation Under review as a conference paper at ICLR 2021
ZINC
PATTERN
CIFAR10
MolHIV
No edge
Fdgg features
edge features, No edge features
Edge features
No edge Seaturen
Model
MAE
MAE
% acc
% acc
% acc
% ROC-AUC
GCN
u.
65.880
54.4Gia3s
0.408st.ce
590
33.58
75.58c1
GraphSage
0.410ss.006
50.516mea0
66.08
GAT
0.463 oo0
75 75.824x1mm 123
65. 15.48
MoNet
0.407st.oov
85 48.28002
53,42ar44
GatedGCN
0,422 coe
0.363
84,480 1>>
69. 99.19
69.37
PNA
0.320et.oa
0.188sa.00 004
86 56.567777
70.46m.44
70.47:0.72
79.05
DGN
0.219
0.168
86.680
72.70
72.84
79.70
Figure 6: Fine-tuned results of the DGN model against models from Dwivedi et al. (2020) and Hu ct al. (2020); GCN (Kipf & Welling 2016), GraphSage (Hamilton et al. 2017). GIN (Xu et al, 201 Sa), GAT (Veličković et al. [201), MoNet (Monti et 2017), GatedGCN (Bresson & Laurent, 2017) and PNA (Corso et al., 2020). All the models use ~ 100k parameters, except those with who use 300k to 1.9M. In ZINC the DGN aggregators are (mean, dx1, max, min), in PATTERN (mean, dx,, avi }. in CIFARIO {mean, dx,, dx2, max), in MolHIV {mean, dx,, (v), max, minj.
the directional models, thus it cannot fit well the data when the rotation/distortion is too strong since the directions are less informative. We expect large models to perform better at high angles.
Rotation Training
Rotation
Distortion Training
Distortion
0.52
Accunsy
3v
0.50
0.48
dx
0.48
dx
0"
2
5"
10"
20
45"
0"
5" 10" 20
45"
0%
18
5%
10%
205
40%
0%
1%
5%
10% 20' 40%
Rotation angle
Pertentage distortion
Pertentage distortion
Figure 7: Accuracy of the various models using data augmentation with a complex architecture of ~ 100k parameters and trained on 10% of the CIFARIO training set (4.5k images). An angle of x corresponds to rotation of the kernel by random angle sampled uniformly in (-2", xx) using definition 5 with Fi,2 being the gradient of the horizontal/vertical coordinates. noise of 100x% corresponds to distortion of each eigenvector with a random noise uniformly sampled in (-x - m - m) where m the average absolute value of the eigenvector's components. The mean baseline model is not affected by the augmentation since it does not use the underlining vector field.
5 CONCLUSION
The proposed DGN method allows to solve many problems of GNNs, including the lack of anisotropy, the low expressiveness, the over-smoothing and over-squashing. For the first time in graph networks, we generalize the directional properties of CNNs and their data augmentation ca- pabilities. Based an intuitive idea and backed by of strong theoretical and empirical results, we believe this work will give rise to a new family of directional GNNs. Future work can focus on the implementation of radius-Ae R kernels and improving the choice of multiple orthogonal directions.
Broader Impact This work will extend the usability of graph networks to all problems with phys- ically defined directions, thus making GNN a new laboratory for physics, material science and biol- ogy. In fact, the anisotropy present in wide variety of systems could be expressed vector fields (spinor, tensor) compatible with the DGN framework. without the need of cigenvectors. One exam- ple is magnetic anisotropicity in metals, alloys and also in molecules such benzene ring, alkene, carbonyl, alkyne that are easier or harder to magnetise depending on the directions or which way the object rotated. Other examples are the response of materials (e.g. to study material responses at terahertz frequency); all kind of field propagation in crystals lattices (vibrations, heat, shear and frictional force, young modulus, light refraction, birefringence): modti-body or liquid motion; traffic modelling: and design of novel materials and constrained struc- tures. This also enables GNNs be used for virtual prototyping systems since the added directional constraints could improve the analysis of product's 's functionality, manufacturing and behavior.
high electromagnetic fields

---

Under review as a conference paper at ICLR 2021
AUTHOR CONTRIBUTIONS
Anonymous
ACKNOWLEDGMENNS
Anonymous
REFERENCES
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. 2020. URRpttt://arat wwwpxiv..rrg../g
05205
Xavier Bresson and Thomas Laurent. Residual
gated
graph
convnets.
arXiv preprint
arXiv:1711.0755,, 2017.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. 34(4):18 42, 2017. ISSN 1053-5888, 1558-0792. doi: 10099/MSP..217.266444.
08097
Fan Chung and Y.T.Yau. Discrete green's i functions, 2000.
Fan Chung and S. Yau. Discrete green's functions. 91(1):111214, 2000. ISSN 0097- 3165. doi: 10. 2000:///c...00..300000 URL/tttp: http://wwwwweiiieeetttttt wwwpscience/ii///oeoccccmc
F.R.K. Chung, F.C. Graham, CBMS Conference on Recent Advances in Spectral Graph Theory,
National Science Foundation (U.S.), American Mathematical Society, and Conference Board of the Mathematical Sciences. Spectral Graph Theory. CBMS Regional Conference Se- ries. Conference Board of the mathematical sciences, 1997. ISBN 9780821803158. URL
https::/books. httpss////ookksssgggeee.ooo www.://booooooo-.ooooaooeee
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.05. 057/8, 2020.
Vishwaraj Doshi and Do Young Eun. Fiedler vector approximation via interacting random walks. 2000. doi: 10.1 145/3379487 URL http:tttp://arxi..rr/////./
00283
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint 2rXiv:2003.00982 2020.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23:298- 305, 01 1973. doi: 10.21 1311CMM.. 101
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine
Volume 70, pp. 1263-1272. JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances neural information processing systems, pp. 1034,1034, 2017.
William L. Hamilton. Graph Representation Learning. Morgan and Claypool, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
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 preprint arXiv:2005.00M6 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 1502::550220316 2015.
10

---

Under review as a conference paper at ICLR 2021
Md Amirul Islam, Sen Jia, and Neil D. B. Bruce. How much position information do convolutional neural networks encode? 2020. httpttttp://i....////// abs//001.... 08248
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. 2018.
04364
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: wetp:09909.00 2016.
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molec- ular graphs. 2019. UtL/httts://ppeereeia
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, pp. 4204 4214, 2019.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint orXiv:1801.0211 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
Comelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differ- ential and integral operators. United States Governm. Press Office Los Angeles, CA, 1950.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. CayleyNets: Graph convolutional neural networks with complex rational spectral filters. 2018. URL http:
B. Levy. bellacc-beltrami eigenfunctions towards algorithm that "understands" geometry. In IEEE International Conference on Shape Modeling and Applications 2006 (SMI '06), pp. 13-13, 2006. doi: 10. 10905M...220..........
Sitao Luan, Mingde Zhao, Xiao Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 10943-10953, 2019.
Haggai Maron, Heli networks. arXiv preprint arXiv:1812.09902 2018
Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph
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, pp. 5115- 5124, 2017.
Sarah O' Gara and Kevin McGuinness, Comparing data augmentation strattrss for deep image clas- sification. 2019. doi: http://bb..og10021142///1888 ar75. URL httttttt//rroo.... tudublir. 1e/ te/impstww//?
Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter: An overview of early vision in InceptionV1. 5(4):000024.002, 2020. ISSN 2476- 0757. doi: 2229911/ditiill.00222..00 early-vision
Hao Peng. Jianxin Li, Qiran Gong, Senzhang Wang, Yuanxing Ning, and Philip S. Yu. Graph convolutional neural networks via motif-based attention. 2019. URL httt:://axxi..o///
abs/1811. 08270)
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropFige: Towards deep graph convolutional networks on node classification. pp. 17, 2020.
Connor Shorten and Taghi M. Khoshgoftaar. A survey image data augmentation for deep learn ing. 6(1):60. ISSN 1115- doi: 10.1 10.11166/40537001--0000 URL htLhttps: :/doii..:///....// org/ 00.1186//40337-11---11111

---

Under review as a conference paper at ICLR 2021
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. 2019. URL htttt:tp//aaae wwtp:/orggaaaaaaaaaaaaao 0377/
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? arXiv preprint arXiv: 18X0:00800000820 201 8a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462, 2018b.
A APPENDIX CHOICES OF DIRECTIONAL. AGGREGATORE
This appendix helps understand the choice of Bad and Baz in section 2.3 and presents different directional aggregators that can be used an alternative to the ones proposed.
A simple alternative to the directional smoothing and directional derivative operator is to simply take the forward/backward values according to the underlying positive/negative parts of the field F, since it can effectively replicate them. However, there are many advantage of using Bav.d-- First, one can decide to use either of them and still have an interpretable aggregation with half the parameters. Then, also notice that Bav,dr regularize the parameter by forcing the network to take both forward and backward neighbours into account at each time, and avoids one of the neighbours becoming too important. Lastly, they robust change of sign of the eigenvectors since Buv is sign invariant and B& will only change the sign of the results, which is not the case for forward/backward aggregations.
A.1 RETRIEVING THE MRAN AND LAPLACIAN AGGREGATIONS
is interesting note that we can recover simple aggregators from the aggregation matrices
Ba (F) and Ba ()). Let F be vector field such that all edges are equally weighted F,, = +C
for edges (i,]). Then, the aggregator Bav is equivalent to a mean aggregation:
Bad F D-1 Ax
Under the condition Fij C, the differential aggregator is equivalent to Laplacian operator L normalized using the degree D
D D)æ -D LL
A.2 GLOBAL FIELD NORMALIZATION
The proposed aggregators are defined with a row-wise normalized field
F..
F.
F..llr.
meaning that all the vectors are of unit-norm and the aggregation//mesage passing is done only according to the direction the vectors, not their amplitude. However, also possible do global normalization of the field F by taking matrix-norm instead of a vector-norm. Doing so will modulate the aggregation by the amplitude the field at each node. One needs to be careful since global normalization might be very sensitive to the number of nodes in the graph.
A.3 CENTER BALENEED AGGREGATORS
A problem arises in the aggregators Bur and Bav proposed in equations 5 and when there is an imbalance between the positive and negative terms of F+. In that case, one of the directions overtakes the other in terms of associated weights
12

---

Under review as a conference paper at ICLR 2021
An alternative is also to normalize the forward and backward directions separately, to avoid having either the backward or forward direction dominating the message.
F..
F.
B center F):
F
(10)
ra +c
The same idea can be applied to the derivative aggregator equation where the positive and nega- tive parts of the field F are normalized separately to allow to project both the forward and back- ward messages into vector field of unit-norm. F+ is the out-going field at each node and is used for the forward direction, while F- is the in-going field used for the backward direction. By aver- aging the forward and backward derivatives, the proposed matrix de-ecenter represents the centered derivative matrix.
Bax-center (F),; =. diag EF'
1 2
(11)
+
+
forward field
backward field
A.4 HARDENING THE AGGREGATORS
The aggregation matrices that we proposed, mainly B and Bav depend on a smooth vector field F. At any given node, the aggregation will take weighted sum of the neighbours in relation the direction of F. Hence, if the field F, at a node is diagonal in the sense that it gives non-zero weight to many neighbours, then the aggregator will compute weighted average the neighbours.
Although there are clearly good reasons to have this weighted- average behaviour, it is not necessarily desired in every problem. For example, behaviour will smooth the node at every step. Instead, we propose below to soften and harden the aggregations by forcing the field making a decision on the direction it takes.
want to move single node across the graph, this
Soft hardening the aggregation is possible by using softmax with temperature T on each row obtain the field Foothard-
(Fanhhan): ). sign( F;.: Jsofmax Ft.l)
(12)
Hardening the aggregation is possible by using an infinite temperature, which changes the soft- max functions into argmax. In this specific case, the node with the highest component of the field will be copied, while all other nodes will be ignored.
(Fiar)i,: sign( F... Jargmax F.,l)
(13)
An alternative to the aggregators above take the softmin/argmin of the negative part and the seftmax/argmax of the positive part.
A.5 FORWARD AND BACKWARD COPY
The aggregation matrices Bay and Bár have the nice property that if the field is flipped (change of sign), the aggregation gives the same result, except for the sign of Ba However, there cases where we want to propagate information in the forward direction of the field, without smoothing with the backward direction. In this case, fields below, and use them directly with the aggregation matrices.
define the strictly forward and strictly backward
Fiorward
Frackwand
(14)
Further, we can use the hardened fields order to define a forward copy and backward copy, which will simply copy the node in the direction of the highest field component.
Frorward copy
F+
F Fauckward copy
hard
(15)
13

---

Under review as a conference paper at ICLR 2021
A.6 PHANTOM ZERO-PARE PERO-PA
Some recent work in computer vision has shown the importance of zero-padding to improve CNNs by allowing the network to understand it's position relative the border (Islam al. 2020). In contrast, using boundary conditions or reflection padding makes the network completely blind to positional information. In this section, we show that we can mimic the cero-padding in the direction of the field F for both aggregation matrices Bay and Bdz.
Starting with the Bas matrix, in the case of missing neighbour in the forward/backward direction, the matrix will compensate by adding more weights to the other direction, due to the denominator which performs a normalization. Instead, we would need the matrix to consider both directions separately so that missing direction would result in zero padding. Hence, define B Bav.0pod below, where either the F+ or F will be O on boundary with strictly in-going/out-gon field.
(B (Baw.ppad)i: =
(16)
tE 1F +
Following the same argument, we define Bdx, below, where either the forward or backward term ignored. The diagonal term also removed at the boundary so that the result is center derivative equal to the subtraction of the forward term with the O-term on the back (or vice-versa). instead of forward derivative.
if = if otherwise
F
-dz-d ())
FC + F ).))
F
F.
diag
(17)
F.: | te
F +E
F
A.7 EXTENDING THE RADIUS OF THE AGGREGATION KERNEL.
We aim at providing a general radius- R kernel Ba that assigns different weights to different subsets of nodes n, at distance R from the center node ny.
First, we decompose the matrix ((F) into positive and negative parts B B=FF) representing the forward and backward steps aggregation the field F.
B = B (
(18)
Thus, defining (F,( le we can find different aggregation matrices by using different
combinations of walks of radius R. First demonstrated for a grid in theorem 2.7 we generalize it in equation 19 for any graph G.
Definition 7 (General radius R n-directional kernel), Let Sp be the group of permutations over elements with a set of directional fields F,,
N
BR =
Σ
av
B egn(vo)))
(Fo (FoG))))oosn)
(19)
V (1) (2.. JEN" SI RSO.SR
DES
optional Any choice of walk V with at most R steps permalations using all combinations
Aggregator the steps V., permuted by S..
In this equation, is the number of directional fields and R is the desired radius. V represents all the choices of walk {2), U2 ... 3 in the direction of the fields {Fi, F2,, Fa). For example, V V= (3, 1, -2} has radius R = 6, with steps forward of F1, step forward of Fz, and 2 steps backward of F.. The sign of each B is dependant to the sign of ()()), and the power (v) is the
14

---

Under review as a conference paper at ICLR 2021
number of aggregation steps in the directional field Fot))- The full equation is thus the combination of all possible choices of paths across the set of fields F, with all possible permutations. Note that are restricting the 2 having only a possible sign; although matrices don't commute, avoid choosing different signs since will likely self-intersect a lower radius walk. The permutations required since, for example, the path up left is different (in general graph) than the path left + up.
2n-1 parameters, with high redundancy since some permutations might be very similar, e.g. for grid graph we have that up - left is identical to left + up. Hence, we can replace the permutation S. by a reverse ordering. mean- ing that II, B, = B,. Doing so does not perfectly generalize the radius- R kernel for all graphs. but it generalizes it on a grid and significantly reduces the number of parameters to min((,.) 2" (1) (i-)). 11=1
This matrix BR has a total of E (2))
(2n)
B APPENDIX IMPLEMENTATION DETAILS
B.I BENCHMARKS AND DATASETS
We use variety of benchmarks proposed by Dwivedi et al. (2020) and Hu et al. (2020) to test the empirical performance of our proposed methods. In particular, to have wide variety of graphs and tasks we chose:
1. ZINC, a graph regression dataset from molecular chemistry. The task is to predict a score that is a subtraction of computed properties log SA, with log being the computed octanol-water partition coefficient, and SA being the synthetic accessibility score (Jin et al. 2018).
2. CIFAR10, graph classification dataset from computer vision (Krizhevsky 2009) The task is to classify the images into 10 different classes, with a total of 5000 training image per class and 1000 test image per class. Each image has 32 32 pixels, but the pixels have been clustered into graph of ~ 100 super-pixels. Each super-pixel becomes a node in almost grid-shaped graph, with 8 edges per node. The clustering uses the code from Knyazev et al. (2019), and results in a different number of super-pixels per graph.
3. PATTERN, a node classification synthetic benchmark generated with Stochastic Block Models, which are widely used model communities in social networks. The task is to classify the nodes into communities and it tests the fundamental ability of recognizing specific predetermined subgraphs.
4. MolHIV, a graph classification benchmark from molecular chemistry. The task is to predict whether molecule inhibits HIV virus replication or not. The molecules in the training, val- idation and test sets are divided using a scaffold splitting procedure that splits the molecules based on their two-dimensional structural frameworks.
Our goal is to provide a fair comparison to demonstrate the capacity of our proposed aggregators. Therefore, we compare the various methods on both types of architectures using the same hyper- parameters tuned in previous works (Corso et al., 2020) for similar networks. The models vary exclusively in the aggregation method and the width of the architectures keep a set parameter budget.
In CIFAR10 is impossible to numerically compute a deterministic vector field with eigenvectors due to the multiplicity of êι being greater than 1. This is caused by the symmetry of the square image, and is extremely rare real-world graphs. Therefore, we used as underlying vector field the gradient of the coordinates of the image. Note that these directions are provided in the nodes' features in the dataset and available to all models, that they are co-linear to the eigenvectors of the grid as per lemma C.I and that they mimic the inductive bias in CNNs.
B.2 IMPLEMENTATION AND COMPUTATIONAL COMPLEXITY
Unlike several more expressive graph networks (Kondor et al. 2018 Maron et al. 2018), our method does not require computational complexity superlinear with the size of the graph. The calculation
15

---

Under review as a conference paper at ICLR 2021
of the first & eigenvectors during pretraining, done using Lanezos method (anczoo 1950) and the sparse module of Seipy, has a time complexity of O(Ek) where is the number of edges. During training the complexity is equivalent aggregation and () ) for the MLP.
m-aggregator GNN O(Em) (Corso et al. 2020 for the
To all the architectures added residual connections (He al. 2016), batch normalization (loffe & Szegedy] 2015) and graph size normalization (Dwivedi et al. 2020).
For all the datasets with non-regular graphs, combine the various aggregators with logarithmic degree-scalers as in Corso et al. 2020).
An important thing to note is that, for dynamic graphs, the eigenvectors need be re-computed dynamically with the changing edges. Fortunately, there are random walk based algorithms that can estimate Φ quickly, especially for small changes the graph (Doshi Eun 2000). In the current empirical results, we do not work with dynamic graphs.
B.3 RUNNING TIME
The precomputation of the first four eigenvectors for all the graphs in the datasets takes 38s for ZINC, 96s for PATTERN and 120s for MolHIV on CPU. Table I shows the average running time on GPU for all the various model from figure On average, the epoch running time is 16% slower for the DGN compared to the mean aggregation, but faster convergence for DGN means that the total training time on average 8% faster for DGN.
Each entry represents average time per epoch / average total training time. Each these models has a parameter budget 100% and was run on a Tesla T4 (15GB GPU). The avg increase row is the average of the relative running time of all rows compared to the mean row, with negative value meaning a faster running time.
Table I: Average running time for the non oone tuned models from figure 5
ZINC
PATTERN
Aggregators
Simple
Complex
Complex-E
Simple
Complex
3.29s/1505s
3.58s/1584s
3.56s/1654s
117.8s/9031s 153.1s/10154
mean dxj
1.86s/1122,
3.77s/1278s
4.22s/1371s
144.9s/8 109s
127.2s/8417s
mean dx, dx2
4.23s/1360s
4.55s/1560s
4.63s/1680s
153.3</8057s
167 167.9s/9326s
mean av1
3.68s/1297s
3.84s/1398s
3.92s/1272s
128.0s/8680s
88. 1s/74666
mean a aV2 3.95s/1432s
4.03s/1596s
4.07s/1721s
134.2s/81 15s
170.4s/11114 1144s
mean dx av1 3.89s/1079s
4.09s/1242s
4.58s/1510s
118.6s/6221s
144.2s/91 12s
avg increase
+19%
+13%/-11%
+20%//9%
-11%
+18%/+1%
CIFARTO
MolHIV
Aggregators
Simple
Complex
Simple
mean
83.6s/10526s
78.7s/10900s
11.4s/2189s
mean dx1
12.6s/2348s
mean dx, dx2
98.4s/8405s
100.9s/5191s
14.1s/2345s
mean av1
12.2s/2177s
mean av1 av2
117.1s/12834s
89.5s/14481s
13.9s/2150s
mean dx1 a
14.0s/2070s
avg increase
+29%/+1%
+21%
+17%/41%%
B.4 EIGENVECTOR MULTIPLICITY
The possibility to define equivariant directions using the low-frequency Laplacian eigenvectors is subject to the uniqueness of those vectors. When the dimension of the eigenspaces associated with the lowest eigenvalues propose the use of unit vector normalization and absolute value to eliminate the scale and sign ambiguity. When the dimension of those eigenspaces greater than 1, is not possible to define equivariant directions using the eigenvectors.
1, the eigenvectors are defined up to a constant factor. section 2.4 we
16

---

Under review as a conference paper at ICLR 2021
Fortunately, it is very for the Laplacian matrix to have repeated eigenvalues in real-world datasets. We validate this claim by looking at ZINC and PATTERN datasets where we found no graphs with repeated Fiedler vector and only one graph out of 26k with multiplicity of the second eigenvector greater than
When facing graph that presents repeated Laplacian eigenvalues, we propose randomly shuffle, during training time, different eigenvectors randomly sampled in the eigenspace. This technique will act as a data augmentation of the graph during training time allowing the network to train with multiple directions at the same time.
C APPENDIX -MTHEMATICAL PROOFS
C.I PROOF FOR THEOREM 2.1
DIRECTIONAL SMOOTHING
The operation y B is the directional average of æ; in the sense that yu is the mean of æes weighted by the direction and amplitude of F.
Proof. This should be simple proof, that if we want weighted average of our neighbours, we simply need to multiply the weights by each neighbour, and divide by the sum the weights. Of course, the weights should be positive.
C.2 PROOF FOR THEOREM 2.2 DIRECTIONAL DERIVATIVE
Suppose F have rows of unit L' norm. The operation y Baz (F)xz the centered directional
derivative of æ in the direction of F. in the sense of equation 4 i.c.
(F diag Σ Fi.)
y D D2x
Proof. Since F rows have unit L norm,
= F. The i-th coordinate of the vector
F - diag E, F.s)) x is
Fx diag ΣF F x = F(so(()) - [ Fis x(1)
Σ (a(j) xx(i) Fi.
DF x(i)
C.3 PROOF FOR THEOREM 2.3 KK <GGRADIENT OF THE LOW-FREQUENCY EIGENVECTORS
Let X; and Φ be the eigenvalues and eigenvectors of the normalized Laplacian of a connected graph Lnorm and let a, arg max maxisijj {dx (1;, 0ý)} be the nodes that have highest K-walk distance. Let arg mini (Φ1); and M arg ma (Ø1)s, then dx (Um, Uns) dx (Vay Ub) has order O(1 X2).
the indices i O,.... (N 1), sorted such that A S A4+1- Hence, An = 0 and \ is the first non-trivial eigenvalue.
Proof. For this theorem,
First need the following proposition:
17

---

Under review as a conference paper at ICLR 2021
Proposition 1 (K-walk distance matrix), The K-walk distance matrix P associated with a graph is the matrix such that (P)i.) dx (Vi, can be written Σ WP, where W DD1A is the random walk matrix.
Let's define W D A the random walk matrix of the graph.
First, we are going to show that W is jointly diagonalizable with Lnom and we are going to relate its eigenvectors 0 and its eigenvalues X with the ones of W.
Indeed, Lym is a symmetric real matrix which is semi comiitosiiive definite diagonalizable by the spectral theorem. Since the matrix Loomn is similar to D Lnoem D = D LD- Loym and the matrix of similarity is D*, positive definite matrix, murm diagonalizable and semi coni-positive definite.
By
Dorm= =
W
the random walk matrix is jointly diagonalizable with the random walk Laplacian. Also their eigen- values and eigenvectors are related each other by Φ: 1 and X = An-1-i
Moreover, the constant cigenvector associated with eigenvalue 0 of the Random walk Laplacian, the eigenvector associated with the highest eigenvalue of the Random walk matrix and by the formula obtained, Xn = λo =1
Now, we are going to approximate the K-walk distance matrix using the eigenvectors of the Random walk matrix associated with the highest eigenvalues.
By Proposition we have that P
WP, which can be written as
(X))
H (X))
i=0
by eigen- dggendeecomposition
Since An-1-i 1 X and A2 > Å1. we have that X₂-2 > Xn-3 hence approximate
K
K
P
o (
~
Σ
Σ
(1))))
p=1 ==0
p=1
K
P. (1 (1) 0 A2) Σ
(000) (1)))( X2)
p=1
= =Koop + k of 0(1 - X2)
where K Exn A1 is positive constant.
Now we are going to show that the farthest nodes with respect to the K-walk distance are the ones associated with the highest and lowest value of Φ1.
Indeed if we want to choose i to be at the farthest distance we need to minimise
K no (1) (7)
(P) = (K + x<)I
n
which is minimum when Φ (1) (j) is minimum.
We are going to show that exist p, q such that (p) < 0. Φ1 (g) > Since the eigenvector non- zero, without loss of generality assume Φ (0) * 0. Since Φ and Φi are eigenvectors associated with different eigenvalues of real symmetric matrix, they are orthogonal:
Σ (o(1) 01 (1) =
18

---

Under review as a conference paper at ICLR 2021
and since @u is constant the previous equation leads to
Σ = 21 2 -0
such p, y didn't exist then we would get that Vi, (1(1)) (i) 2 0, hence multiplying both sides of the previous equation by (0) we get
20) 01)0 01 Φ1 (0)² 0
Which is contradiction since by assumption (1 > 0; hence exist p. q such that Φ1 (p) < 0, Φ1 (q) > 0.
Since Φ1 attains both positive and negative values, the quantity Φ (1) (j) is minimised when has negative sign and highest absolute value, hence when i,j are associated with the negative and positive values with the highest absolute value: the lowest and the highest value of Φ1. Hence, dx (UM, Um) dx (Vay vb) O(1 X2)
C.4 INFORMAL ARGUMENT IN SUPPORT OF CONJECTURE 2.4 (RADIENT STEPS REDUCE EXPECTED HITTING TIME
Suppose that y are uniformly distributed random nodes such that (x) < (,(y). Let be the node obtained from æ by taking one step in the direction Vø, then the expected hitting time is decreased proportionally to X; and
Eg Q(2, v)1 Ba,y/Q(a (Q(2. v)]
As reminder, the definition of gradient step is given in the definition 3 copied below.
Suppose the two neighboring nodes and are such that (02)
Φ(x) maximal among the
neighbors of x, then we will say 2 is obtained from x by taking step in the direction of the gradient VΦ.
In Chung & S.T. Yau 2000), it is shown the hitting time Qxx, v) is given by the equation
Q(x, v) vol (G(,.))
G(z.
dy
d.
With d and Φb being the k-th eigenvalues and eigenvectors of the symmetric normalized Laplacian Taym. vol the sum of the degrees of all nodes, d, the degree of node x and G Green's function for the graph
G(
d dj
(x(T)))(1))
A30
Since the sign of the eigenvector is not deterministie, the choice (x(x)) < (1(1) is used simplify the argument without having to consider the change in sign.
Supposing A A2, the first term of the sum of G has much With z obtained from x by taking a step in the direction of the gradient of Φi we have
weight than the following terms.
Φ (2)) Φ (x)
We want to show that the following inequality holds
Eg.y (Q(2, 3)) (Q(x,
this is equivalent the following inequality
Ex, (2,.))) Eu. (x(,
19

---

Under review as a conference paper at ICLR 2021
X2, we can approximate G(r,y) dē x (z)))(((1)
By the hypothesis A1 inequality is equivalent to
<
so the last
Exyy
di dyj X
x1(2))((1)
> Ex,y
de dy A
+1(+))((1))
Removing all equal terms from both sides, the inequality equivalent
En.y
d3 Φ (z)
Earyy
d3 (x))
But showing this last inequality is not easy. We know that Φi (2) Φ1 (2) and from the choice of being a step in the direction of VΦ,, we know is less likely to be on the border of the graph so we believe B(dz) 2 E(dz). Thus also believe that the conjecture should hold in general.
We believe this should be true even without the assumption on λ and X2 and for more eigenvectors than 11
C.5 PROOF LEMMA C.I (COSINE EIGENVECTORS
Consider the lattice graph I' of size N1 N2 Nn. that has vertices II {1. the vertices (x: (d:))=1.....r and (yi):=1..... are connected by an edge iff la, yel for one index and 0 for all other indices. Note that there no diagonal edges in the lattice. The eigenvector of the Laplacian of the grid L(I') are given by Φj.
No and
Lemma C.1 (Cosine eigenvectors). The Laplacian I has an eigenvalue 2 cos associated eigenvector 3; that depends only the variable in the i-th dimension and is constant in all others, with oi 1N, 1 @ LN,N, @ N and 11N, (j) CO8 [
with the
N.
Proof. First, recall the well known result that the path graph on N vertices Py has eigenvalues
Tk: n
A 2 cos
with associated eigenvector æę with i-th coordinate
Tki
ok
(
C08
+
2n
The Cartesian product of two graphs G = (Va, EG) and H = (VH, Eω) is defined as G x H = (VGxH, EGxH) with Vax h VG x Vи and ((u), u2), (11, U2)) EGx iff either ii 0j and (uz, 02) E Eg or (I1, U1) VG and U2 = U2. It is shown in (Fiedler 1973) that if (=,... and (Ay)j=1..... are the eigenvalues of G and H respectively, then the eigenvalues of the Cartesian product graph G x H are A for all possible eigenvalues μı and '5. Also, the eigenvectors asso- ciated to the eigenvalue μi; + X are u, @ by with u; an eigenvector of the Laplacian of G associated to the eigenvalue μ4 and vy eigenvector of the Laplacian of H associated to the eigenvalue Ay.
Finally, noticing that a lattice of shape N1 X N2 X x Nn really the Cartesian product of path graphs of length N₁ up N,, conclude that there eigenvalues 2 2 cos
N; Denoting
by 1N, the vector in R,,, with only ones as coordinates, then the eigenvector associated to the eigenvalue 2 cos N,, is
1N, IN, ... LL,N ... 1N.
where VI,N, is the eigenvector of the Laplacian of PN; associated to its first non-zero eigenvalue.
2 - 2 cos
N.
20

---

Under review as a conference paper at ICLR 2021
C.6 RADIUS CONVOLUTION KERNELS IN GRID
In this section we show any radius convolution kernel can be obtained as a linear combination of the B V and B. (V..)) matrices for the right choice of Laplacian eigenvectors Φ;. First show this can be done for 1-d convolution kernels.
Theorem C.2. On a path graph, any 1D convolution kernel of size 3 le is linear combination of the aggregators Bav: Bdd and the identity I.
Proof. Recall from the previous proof that the first non zero eigenvalue of the path graph Pv has associated eigenvector (t) = cos(
mi N
2N Since this is a monotone decreasing function in
the i-th row of VΦL will be
(0,.... O, 8; 0, 0,,,,,,,,,,,,,, .,..,,
with 8;-1 and 8,-1 > We are trying to solve
Ba + bB cId) (0, (O...., 0, 2r 2, ....
with y, 2, in positions i 1 and + 1. This simplifies solving
[s] b 1 s + c(0, 1, = [x,
with s = (8:-1, - 11+1). which always has solution because 8;-1, Si+1 > 0.
Theorem C.3 (Generalization radius-1 convolutional kernel in a grid). Let I be the n-dimensional lattice as above and let Φj be the eigenvectors of the Laplacian of the lattice as in theorem C.I Then any radius! 1 kernel on I't is a linear combination of the aggregators Buo(d:), Bdx(d ( and
Proof. This is direct consequence of C.2 obtained by adding 1-dimensional kernels, with each kernel being in different axis of the gnid as Lemma C.I See figure 4 for a visual example in 2D.
C.7 PROOF FOR THEOREM 2.7 GENERALIZZTION RADIUS- CONVOLUTIONAL KERNEL IN LATTICE
For n--imensional lattice, any convolutional kernel of radius R can be realized by a linear com- bination of directional aggregation matrices and their compositions.
Proof. For clarity, we first do the dimensional case for a radius 2, then extended the general case. Let & be the radius kernel grid represented by the matrix
0
Q-2.0
0
0
0
a-1,11
0-1.0
0-1,1
05x5
ag, -2
2
ag, -1
40.0
G0.1
40,2
0
01
01,0
@1,1
0
02,0
()
0
since we supposed the N1 x N₂ grid was such that N1 >
N2. by theorem
C.1
we have that Φ is
depending only the first variable i1 and is monotone 21 Recall from that
Φ1 (1) = cos
+ 2N
Ni
The vector Ni V arccos (r)))s(())) will be denoted by F in the rest. Notice all entries of F, are 0 or +1.
Denote by F2 the gradient vector Na V arccos( where Φy is the eigenvector given by theorem म that is depending only in the second variable and is monotone in x; and recall
(x (i) = cos
π
N₂
2N
21

---

Under review as a conference paper at ICLR 2021
For matrix B, let B the positive/negative parts of B, ie matrices with positive entries such that
B = B= -B _ Let Br1 matrix representing the radius kernel with weights
1.0
0
03x3 =
d0.-1
00,0
0g.1
01,0
0
The matrix B, be obtained by theorem C.3
Then the radius 2 kernel is defined by all the possible combinations of 2 positive/negative steps, plus the initial radius-1 kernel.
B22
Σ 22
B all possible single-steps
Any combination steps
with sgn the sign function sgn(i) = + if i 2 and - if < 0. The matrix B,2 then realises the kernel asx5-
We can further extend the above construction to N dimension grids and radius R kernels k
Σ
II (F
Qv
V= Ca... UN JEN"
RS0ER
Aggregator following sleps detined
Any choice of walk with at most Resteps
with F, arccos Φ; ,o; the eigenvector with lowest eigenvalue only dependent on the j-th variable and given in theorem walk (v), U2 U2,..., Un } in the direction the fields (Fi, F2,..., F.)) J. For example, = 1, 0, 2} has radius R 6, with 3 steps forward of F,, step forward of Fz, and 2 steps backward of F4
II is the matrix multiplication. V represents all the choices of
C.8 PROOF FOR THEOREM 2.8 [COMPARISON WITH W- TEST
DGNs using the mean aggregator, any directional aggregator of the first eigenvector and injective degree-scalers strictly more powerful than the I-WL test.
Proof. We will show that (1) DGNs are at least as powerful as the 1-WL test and (2) there is a pair of graphs which are not distinguishable the 1-WL test which DGNs can discriminate.
Since the DGNs include the mean aggregator combined with at least an injective degree-scaler, Corso et al. (2020) show that the resulting architecture is least powerful as the 1-WL. test.
22

---

Under review as a conference paper at ICLR 2021
Graph
Graph
b
Aggregation matrix
Graph 1
Graph
1a + 1b b
1a + 1b
2b a
1a +
|1a 1b| b
|1a 1bl b
B1x
0 + a
|0.44b - 0.44a| + a
1a -
1a + b 0.44b + 0.56a
B1
1b
Figure 8: Illustration of example pair of graphs which the 1-WL test cannot distinguish but DGNs can. The table shows the node feature updates done at every layer. MPNN with mean/sum aggregators and the 1-WL test only use the updates in the first and therefore cannot distinguish between the nodes in the two graphs. DGNs also use directional aggregators that, with the vector field given by the first eigenvector of the Laplacian matrix, provides different updates to the nodes in the two graphs.
Then, to show that the DGNs are strictly more powerful than the 1-WL test it suffices to provide an example pair of graphs that DGNs can differentiate and 1-WL cannot. Such a pair of graphs is illustrated in figure
The 1-WL test any MPNN with, for example, sum aggregator) will always have the same features for all the nodes labelled with and for all the nodes labelled with b and, therefore, will classify graphs as isomorphic. DGNs, via the directional smoothing or directional derivative aggregators based the first eigenvector of the Laplacian matrix, will update the features of the nodes dif- ferently the two graphs (figure 8 presents also the aggregation functions) and will, therefore, be capable of distinguishing them.
23


Reviews:
[{"review_id": "wH5qmWlxrY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a theoretical framework that allows to directional convolutional kernels in any graph, e.g., generalize CNNs on an n-dimensional grid. In the framework, gradients of the eigenvectors of the graph Laplacian are used to define “directions” on the graph.\n\nThe proposed method is well-motivated and seems to be theoretically justified (I did not fully understand the details and check the proofs). My main concerns are:\n\n1.\tThe theoretical development is difficult to follow. The proposed method is not clearly described. It is hard for readers to find in the paper what are the steps of the proposed algorithm and understand how it works. It would be better to describe the algorithm step by step.\n\n2.\tI have some doubts about the practical value of the proposed method because it requires eigen-decomposition of the Laplacian matrices. Though the authors provide complexity analysis in the appendices, it would be more informative to provide a runtime comparison with SOTA methods such as the vanilla GCN. \n\n================ Post Rebuttal =============================================================\n\nThank the authors for the updates.\n\nIn the latest version, the algorithm flow is clearly stated in Figure 1, and now I can understand how the algorithm works. The authors also reported additional results on running time in the latest version, which are informative. \n\nHere is what I think after reading the paper again.\n\n1.\tThis paper proposes a novel idea. Defining directions on graphs is not a well-addressed problem in current GNN models, and using the gradients of the low-frequency eigenvectors of the Laplacian to define directions seems novel and interesting to me.  \n\n2.\tThe insight and analysis are not clear. Section 2.4 is still difficult to follow after the updates. More importantly, I am not sure about the correctness of the theorems and corollaries. \n\n       The K-walk distance is supposed to reflect the difficulty of passing information between two nodes, and a larger distance means more difficulty. In the paper the K-walk distance is defined as the average number of times that a K-step random walk from one node to hit another (formal definition given in Page 18), which really puzzles me, because frequent visits indicate ease of message passing. Did the authors confuse hitting probabilities with hitting times? \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "tV9FbTtMp56", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work considers the limitation of graph neural networks that cannot consider the directions. It proposed directional graph networks to overcome this limitation. The concerns for this work are as below:\n\n1.\tI do not quite understand the motivation of this work. In section 2.1, the authors explain that a big limitation of current GNN methods is that they cannot process directions. This is not case. In most message passing GNNs, they can rely on the adjacency matrix during message passing process. If a specific direction is desired, it is feasible to modify or design the adjacency matrix accordingly. This fact is also true on the grid graphs. Thus, I don’t quite buy the motivation of this work. The authors need to clarify this motivation and illustrate why the direction limitation is not resolvable by manipulating the adjacency matrix. \n2.\tThe data augmentation is proposed in Section 2.7. The authors claimed that the advantage of the proposed method is that it does not influence the data but applied on kernels. However, there may be some issues here for changing kernels. In this work, the kernel is acting as a kind of message passing directions on the graph. The message passing patterns are an important part of the graph. If the patterns or connections are changed, the graph will change consequently. From this perspective, if the proposed method changes the kernel and modify graph connections, this cannot be considered as a strict data augmentation since the modified graphs can have totally different properties as the original ones. Thus, I would like the authors to provide a clarification on this point.\n3.\tThe number of datasets used in the experimental parts is quite limited. These datasets are not commonly used in the community. The authors may want to clarify this and add more datasets for comprehensive evaluations. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "r14dnjXKR2T", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors propose a convolution as a message passing of node features over edges where messages are aggregated weighted by a \"direction\" edge field. Furthermore, the authors propose to use the gradients of Laplace eigenfunctions as direction fields. Presumably, the aggregation is done with different direction fields derived from the Laplace eigenfunctions with lowest eigenvalues, which are then linearly combined with learnable parameters. Doing so allows their graph network to behave more like a conventional CNN, in which the kernels have different parameters for signals from different directions. The authors achieve good results on several benchmarks. Furthermore, the authors prove that their method reduces to a conventional CNN on a rectangular grid and have theoretical results that suggest that their method suffers less from the \"over-smoothing\" and \"over-squashing\" problems.\n\nStrong points:\nThe proposal is highly novel. It is a simple and scalable modification to conventional graph nets that shows a strong performance increase in the benchmarks. The paper is mostly clearly written. The theoretical analyses contribute to the understanding of the work.\n\nWeak points:\n- It is unclear how parameters are used in their model. I presume that they apply the directional derivative with several edge fields and then linearly combine with learnable parameters, but this is not stated explicitly. Furthermore, for different graphs with different spectra, how are the parameter shared? Simply by their order?\n- As the authors note at the end of Sec 2.4, the Laplace eigenvectors can not uniquely be identified, only the eigenspace of a certain eigenvalue. For example, this means that when Lanczos’ method is applied to two isomorphic graphs in different orderings, different eigenvectors can be returned. The authors propose to overcome the arbitrary-ness of the sign by taking the absolute value after each dictional derivative. Still, when an eigenvector is used from a degenerate eigenspace, the method appears not equivariant to node re-orderings. The authors state that in their datasets, the first non-trivial eigenvector is always non-degenerate, but the experiments also use higher eigenvectors. Are these also non-degenerate? Or is that model not equivariant? This also means that when using the proposed method on a square grid, which the authors do on CIFAR10, the method is not equivariant to node re-orderings.\n\nRecommendation:\nI recommend to accept this paper, as it proposes a simple to use method to build more powerful graph nets. In spite of my concerns about equivariance, it appears to perform well in relevant benchmarks.\n\nOpportunities for improvement:\n- The paper could be improved by more directly addressing the concerns about equivariance. Are some of the proposed models indeed not equivariant on certain graphs? Do we care that the model is not always equivariant? \n- It would be interesting to see if the authors could prove that the resulting model is more expressive than a conventional graph networks, for example by comparing theoretically or experimentally to the expressiveness of Weisfeiler-Lehman tests.\n\n### Post rebuttal\nMy previous rating still applies. If accepted, I encourage the authors to more clearly state in the final version that their method is not applicable (without additional - and arguably inelegant - random augmentation) to graphs with degenerate eigenvalues and in particular symmetric graphs. The necessity of taking the absolute value to ensure invariance to the sign of the eigenvector should also be more clearly stated.\nI share reviewer #1's concerns about corollaries 2.5 and 2.6. These should be clarified or removed from the final version. Nevertheless, I think the novelty of the approach justifies acceptance. It is a simple modification that may bring the expressive power of graph networks closer to that of pixel CNNs.", "extra_scores": {}, "extra_text": {}}, {"review_id": "j7q6psu5uxI", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Revision History**\n- Oct. 27th 2020: Submit the initial comment.\n- Nov. 20th, 2020: Fix the \"Correctness\" part for better readability.\n\n\n**Review summary**\n\nThe use of vector fields on a graph to define directed convolution is an interesting idea. In addition, the proposed GNN is theoretically sound in that it is an extension of CNNs on a grid graph in a certain sense (Theorem 2.7). Empirically, the proposed GNN performs better than existing methods. Nevertheless, I am not confident that the proposed method effectively reduces the over-smoothing and over-squashing problems theoretically or empirically. Regarding the data augmentation, although the proposed augmentation method works empirically, I am not sure the soundness of the method.\n\n**Summary of the paper**\n\nThis paper proposed DGN (directional graph neural network), which employs directional aggregations using a vector field on a graph. Specifically, it proposed two types of aggregations: Directional averaging and Directional derivative matrix, which use eigenvectors associated with a graph Laplacian. DGN generalized a CNN when the underlying graph is a grid graph. Also, it proposed a data augmentation method using vector fields. This paper claimed that the proposed methods reduce the over-smoothing and over-squashing problem and perform well compared to existing methods.\n\n**Claim**\n\nIf I understand correctly, the main claims of this paper are as follows. I assume them and evaluate the paper based on whether it supports them.\n- Claim 1: The lack of propagation directions in existing GNNs limits the discriminative power of GNNs (Section 2.1, Paragraph 2)\n- Claim 2: Existing GNNs that used asymmetric graph kernels do not use the graph topology and directional flow (Section 1, Paragraph 2). \n- Claim 3: DGN generalizes CNNs on a grid (Section 1, Paragraph 4) and existing aggregation (Section A.1).\n- Claim 4: DGN works as a countermeasure of over-smoothing and over-squashing problems (Section 2 Corollary2.5, Corollary 2.6). In particular, DGN theoretically and empirically allows message passing across distance layers (Section 1, Paragraph 5).\n- Claim 5: Proposed data augmentation method using a vector field on a graph is effective.\n\n**Soundness of the claims**\n\nCan theory support the claims?\n- Regarding Claim 1 and 2, this paper did not compare (at least directly) with existing methods theoretically.\n- Claim 3 is supported by Theorem 2.7.\n- Claim 4 is supported by Corollary 2.5, 2.6. (But I am not entirely sure their correctness. See \"Correctness\" section.)\n- Claim 5 is not theoretically supported. But I am uncertain whether this paper argues that this claim has theoretical justifications.\n\nCan empirical evaluation support the claims?\n- Claim 1 is empirically supported by comparing GCN, GraphSage, GIN, and MoNet in the experiment in Figure 5.\n- Claim 2 is empirically supported by the comparison with GAT and GatedGCN in the experiment in Figure 5.\n- Claim 3 is theoretical. So, it is OK that no experiments correspond to it.\n- Claim 4 is validated indirectly by comparing the proposed model with existing ones known to be suffered from the over-smoothing and over-squashing problem. If I do not miss any information, this paper did not compare the proposed method with anti-over-smoothing methods such as DropEdge [Rong et al., 20].\n- Claim 5 seems to have some support from the empirical assessment (Figure 6). But I am not perfectly certain of their correctness. (See \"Correctness\" section.)\n\n[Rong et al., 20] Rong, Y., Huang, W., Xu, T., & Huang, J. DropEdge: Towards deep graph convolutional networks on node classification. ICLR 2020.\n\n**Significance and novelty**\n\nNovelty\n- The idea of using a vector field for directional message passing is novel, to the best of my knowledge.\n\nRelation to previous work\n- The authors mentioned existing GNNs that employed asymmetric kernels (such as GAT or DimeNet). Although they discussed the difference of the proposed model from them in detail, I think is these models are based on different design principles. (of course, it would be great if this paper discusses the difference in more details)\n- As I wrote previously, this paper did not compare the proposed method with existing anti-over-smoothing methods.\n\n**Correctness**\n\nIs the theory correct?\n\n- Theorem 2.3: I think the statement of Theorem2.3 is informal. I would recommend to write the formal statement somewhere, at least in the appendix.\n- Section 2.4: This paper wrote that \"These results from theorem 2.3 and conjecture 2.4 have the following immediate corollaries\" (the sentence after Conjecture 2.4). This sentence is not appropriate, as it reads that this paper derives corollaries from a conjecture, which is not proven yet. Considering that, it looks that Corollary 2.4 and 2.5 are not proven theoretically.\n- Conjecture 2.4: I could not understand what \"one step direction of $\\nabla \\phi_i$\" meant.  I understand it when a vector field in a Euclidean space. However, since $\\nabla \\phi_i$ is a function on the set of edges on a graph, this analogy does not hold. I want this paper to clarify it.\n- Theorem 2.7: The proof seems correct. The idea is to pick eigenvectors $\\phi_1, \\ldots, \\phi_D$ that only change along each axis and take vector fields $\\nabla \\arccos(\\phi_d)$ as basic components.\n- Definition 4: Regarding the data augmentation (Definition 4), I understand the intuition that we \"rotate\" a vector field in the reverse direction instead of rotating an image. However, I could not understand whether the definition is sound.  Specifically, if I understand correctly, I expect that $F'_1 = F_1$ and $F'_2=F_2$ when $\\theta = 0$. However, the latter one does not hold in general. Let us decompose $F_2$ into directions that is parallel and perpendicular to $F_1$ as $F_2 = F_2^{\\parallel} + kF_2^{\\perp}$ ($k=\\|F_2-F_2^\\parallel\\|$). Then, it holds $F_2'|_{\\theta=0}=F_1\\cos \\alpha+F_2^\\perp\\sin \\alpha=F_2^{\\parallel}+F_2^\\perp\\sin \\alpha$. This does not equal $F_2$ in general.\n\nIs the experimental evaluation correct?\n- In Section 2.7, this paper proposed the random distortion of a vector field as Definition 5. However, if I do not miss anything, it only defined the concept and did not discuss its theoretical nor empirical properties. Therefore, I do not think the proposed augmentation method is justified.\n- In Figure 6, when the maximum rotation angle is $45^\\circ$,, the training and test accuracy of the dx method is worse than the baseline. I want this paper to discuss the behavior.\n\nIs the experiment reproducible?\n- Yes\n\n**Clarity**\n\nCan I understand the main point of the paper easily?\n- Yes. The background of the proposed method is explained in Section 2.2. The proposed method is explained in Section 2.3. Proofs are easy to understand. The explanations are easy to understand.\n\nIs the organization of paper well?\n- Yes. I did not find any problem regarding the organization of the paper.\n\nAre figures and tables appropriately made?\n- Yes\n\n**Additional feedback**\n\n- Section 2.3, Figure 2: Should we replace $u_i$ with $x_{u_i}$, as $u_i$ is a label for the node itself?\n- Section 2.4, Theorem 2.3: There seems to be inconsistency of ranges the index $i$ runs in different places. Specifically, they assume that indices of $\\lambda_i$ and $\\lambda_i'$ run through $i=0, ..., n-1$ in one place and $i=1, ..., n$ in another place. Also, it should be explicitly written that $\\lambda_i$'s are sorted (either in ascending or descending order) because otherwise $\\lambda_1$ and $\\lambda_2$ are undefined. \n- Section 2.5, page 5, last line: figure 2.5 → figure 3\n- Section 3, page 7, paragraph 3: How can we determine $k$?\n- Section 4, page 7, paragraph 1: What does $i$ in $B^i_{dx}$ and $B^i_{av}$ indicate? (index of the eigenvector?）\n- Section C.3, page 15, Make $D^{-1/2}$ bold\n- Figure 4 referred to $B_{av}$ as av, while Figure 5 referred as smooth. I would recommend to make them consistent.\n- In Equation (8), they normalized the length of the vector field to 1 in the definition of the perpendicular component of a vector field. However, I think we usually refer to the unnormalized vector field (i.e., denominator of (8)) as a perpendicular component.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main merit of the paper is to try to address some important issues about GNN, e.g. expressivity power and data augmentation, from a novel perspective and using well grounded mathematical tools. Unfortunately, however, this novel perspective is also introducing some confusion about its meaning in the context of graphs. In fact, it is not clear how, in the general case, direction as introduced in the paper makes sense, especially when considering the data augmentation approach. Moreover, although well grounded mathematical tools are used, proofs of theorems, as well as justification of related corollaries, are not sufficiently clear to guarantee their correctness.

In summary, a potentially interesting contribution that needs more work to better clarify motivations, grounding to common graph concepts, better presentation of the theoretical results.
Decision: Reject