Beyond Classical Diffusion: Ballistic Graph Neural Network
Authors: Yimeng Min
Venue:  (2020)
Keywords: Graph Convolutional Network
Diffusion
Transportation
Machine Learning

Abstract: This paper presents the ballistic graph neural network. Ballistic graph neural network tackles the weight distribution from a transportation perspective and has many different properties comparing to the traditional graph neural network pipeline. The ballistic graph neural network does not require to calculate any eigenvalue. The filters propagate exponentially faster($\sigma^2 \sim T^2$) comparing to traditional graph neural network($\sigma^2 \sim T$). We use a perturbed coin operator to perturb and optimize the diffusion rate. Our results show that by selecting the diffusion speed, the network can reach a similar accuracy with fewer parameters. We also show the perturbed filters act as better representations comparing to pure ballistic ones. We provide a new perspective of training graph neural network, by adjusting the diffusion rate, the neural network's performance can be improved.

Under review as a conference paper at ICLR 2020
BEYOND CLASSICAL DIFFUSION: BALLISTIC GRAPH NEURAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents the ballistic graph neural network. Ballistic graph neural ner- work tackles the weight distribution from a transportation perspective and has many different properties comparing the traditional graph neural network pipeline. The filters propagate exponentially faster(o² ~ 72) comparing to traditional graph neu- ral network(a? T). We a perturbed coin operator to perturb and optimize the diffusion rate. Our results show that by selecting the diffusion speed, the network can reach a similar accuracy with fewer parameters. We also show the perturbed filters act as better representations comparing to pure ballistic ones. We provide a new perspective of training graph neural network, by adjusting the diffusion rate, the neural network's 's performance can be improved.
INTRODUCTION
How to collect the nodes' correlation on graphs fast and precisely? Inspired by convolutional neural networks(CNNss, graph convolutional networks(GCNs) can be applied to many graph-based structures like images, chemical molecules and learning systems. Kipf & Welling (2016) Similar to neural networks, GCNs rely random walk diffusion based feature engineering to extract and exploit the useful features of the input data.
Recent works show random walk based methods represent graph-structured data the spatial vertex domain. For example, Li et al. (2017) use bidirectional random walks on the graph to capture the spatial dependency and Perozzi al. 2014) present scalable learning algorithm for latent representations of vertices in a network using random walks. Except for the spatial domain, many researchers focus approximating filters using spectral graph theory method, for example Bruna BBuna et al. (2013) construct a convolutional architecture based on the spectrum of the graph Laplacian; Defterrard et al. (2016) use high order polynomials of Laplacian matrix learn the graphs a NN structure model.
1.1 BACKGROUND AND RELATED WORK
1.1.1 LAZY RANDOM WALK
Consider a undirected graph G(V, E), for random walk start from vertex v E ( pı(u) denotes the probability vertex at time we have En (u)) = 1. At time = t + 1, the probability at vertex e will be:
(v)
Σ
P.(u)
(1)
d(u)
(L,))EE(G)
where d(u) is degree on vertex u. The normalized walk matrix is defined as D-1/2AD-1/2 where E(G) denotes the edges on G. Matrix notation as follows:
1 = AD-
Consider lazy random walk with 1/2 probability staying current nodes. AD-1 becomes
] (AD-- + 7) and the lazy normalized lazy walk is + D- ADD where A is the adjancy matrix and D is the degree matrix. For regular graph, AD-122AD-1/2 AD-1- D-1

---

Under review as a conference paper at ICLR 2020
1.1.2 GRAPH CONVOLUTIONAL NETWORK
Graph convolutional neC) powerful tools for learning graph representatior Kipi & Welling (016). For traditional GCN, the structure is shown in Figure | Akin to neural net- Works(NNs), promising improvements have been achieved by defining the random walk diffusion- based filters and using them in multi-layer NN. However, the depth of layers grows, over-
Feature Extraction
Feature Extraction
Manifold
Wo
W
Output
Figure 1: Structure of GCN.
smoothing appears common issue faced by GCNs Li et al. (0188. The over-smooth be
attributed to the stacking of random walk diffusion based feature extraction, resulting in the similarty of node representations.
In Kipf & Welling (0166), the convolution I AD-12 In practice, the first part can be regarded as adding self-loops to the node and then the latter part can be regarded as a walk based diffusion. For k step lazy random no biased walk, the final probability distribution of the random walk will converge applying 1 on the initial state. The distance from the start point of simple random walk will converge CVK, where C, & is the constant and the number of total steps respectively.
1.2
THE OVER-SMOOTH PROBLEM
1.2.1 THE LOW PASS FILTER
The random walk based method can be regarded as a low pass filter on the graph. The normalized It is easy to prove that Inormalized has an eigenvalue 0 with a eigenvector d2/2, where is the degree vector. Lnormalized has eigenvalues: Ào S >; A 2 with normalized orthonormal eigenvectors di do ||a_/|||
graph Laplacian is Lnormatized = 1 --- - where L = D D-1/2AD-323
d
Fourier transformation for a signal ग. on graph with basis di is f(T)): = म. di. denotes the time steps. @ and A corresponds the lowest frequency part and the larger X correponds to higher frequency components.
Consider the operator Lrw = AD-1 Lyw has n eigenvectors 6o"h D1/2 1/ and eigenvalues 7 = - 2, The X has a range between 0 and 1. The largest eigenvalue is dp with the eigenvector ob The normalized distribution at / = 0 is noNor D D-1/2 where is the spatial distribution
The normalized distribution after steps is: का mm the Fourier transform reads:
n-1
f(
Nor)
Σ f( (o
Nor (17")) OF f(r) Nor ( " %
Σ f( Nor
Yo""
(3)
Since AD = 1, thus the diffusion operator (brw)' preserves the zero-frequency component of and suppress the high frequency part. In this case, the depth of GCN increase, the high-frequency information is lost, resulting in the over-smooth problem.
1.2.2 THE SPATIAL DOMAIN
In this section, we analyze the long-time random walk behaviour from the spatial domain. Figure (a) and (b) show the short time and long-time behaviour respectively, for short time random walk,
there are many discussions about random walk asymptotic behaviour, for example, please httpa wwww... mit http://aaaaaaaaaaaaee//p/aataaaa
/
random. htm hatp::/mattwwezll..oLLzaaa http://owrrrrrr.cnnneeeeennneooe
and
http: /www/ math. caltech.eduu httteeechh...a////00///////////a http:///eaaaaaiaaoo////aaaaaaaat
Tew has similar matrices, share properties of represented linear operator 7,
2

---

Under review as a conference paper at ICLR 2020
neighbourhood information is captured and learned; the time steps become larger, the probability distribution on the nodes becomes indistinguisaalle and increases the error in the classification task. The distribution of ballistic walk proposed in this paper is shown in Figure 2 (c), being different from the random walk method, the distribution puts more weight on the more distant nodes as time steps increase.
Relationship between distribution and distance
The definition of distance is:
probablity on xleast nember of hoppings belween start point and node Dislance Σ
(4) Figure (b) and (c) show the distribution the same number of steps start from the same point. As ballistic walk puts more weight on the farther nodes: the indistinguishable problem is circumvented, and the distance is increased. The shape of the ballistic distribution is more oscillated, thus higher frequency information is preserved. Since the distance within the same time steps is larger, we regard the ballistic walk is faster transportation method comparing to the random (alg(Figr))[dd) Note the faster term does not mean the ballistic walk goes to farther nodes, both the random walk and ballistic walk reach the k-th hopping nodes in time step k, the ballistic walk has different weight distribution on more distant nodes.
(a)
(b)
(c)
Probability
Indettinuiehablle
Start Point
Start Point
Start Point
t ta
(d)
(c)
Distance
t= to
Time
t 4
Figure 2: (a) Schematic weight distribution of random walk/Lapplaian operator after short time steps. (b) Schematic weight distribution of random walk/Laplacial operator after long time steps. (c) Schematic weight distribution of ballistic walk after same time steps as (b). (d) The distance of (a),(b)(c) with their time steps respectively. (c) has a larger distance comparing to (b) at t = é,, thus (c)-the ballistic walk is considered as faster transportation.
1.3 BALLISITC WALK IS ABLE TO COLLECT CORRLEATION BETTER
In traditional GCN, The random walk/L.aplacian matrix collects the correlated information over a graph. Here we consider two-dimensional condition, taking the start point (0,0) and the correlated point is (i.j), the distance is denoted as dıy. As discussed, the distance walk travels is CVT,, in this case, though a di step walker can reach (i.j), the probability distribution on the correlated point is relatively low since the walk's 's average distance is C- k. In order to fully capture the correlation between the two vertices(in other words, increase the weight between (0,0) and (i-)),, two main methods are used:
1. take steps d, steps, in Defferrard et al. (0166). in analogy 5x5 filter, the authors Laplacian polynomial order up to 25 to achieve similar accuracy, the number of steps is far larger than the filter's size in CNNs.
3

---

Under review as a conference paper at ICLR 2020
Distance
10
15
20
25
Time step
Figure Classical diffusion
2. Pooling: the distance of two vertices is shortened after pooling operation. dy will reduce to /ig/21 / after a 2 x2 pooling. c.g. Henaff et al. (2015) and Bruna et al. (2013) use max pooling, Defferrard al. (2016) efficient pooling and Tran et al. 2018) sort pooling.
Figure B shows the relation between the distance and number of steps for the random walk/Laplacian matrix. As the steps increases, the walk diffuses with the distance ~ Cvk, where k is the number of steps, resulting in the inefficiency in collecting information. Suggested by Haammod et al. (201 1). the filter on most common graph convolutional network is:
(5) (A = Σk-1 0gA* and 0 RK is a vector of polynomial coefficients, where U RNNN comprises orthonormal eigenvectors and A diag(Ai, ..., An) ). is diagonal matrix of eigenvalues, which is approximated by k-th order polynomials of L. Wu et al. (219) Since the number of steps corresponds to the polynomial order of the Laplacian, as the polynomial order grows, the distance walker travelled changes slower and slower(the distribution becomes smooth), resulting in low efficiency and duplicated filters.
9o go(UAU*) -Ug(()U"
In the section, will introduce the ballistic walk method that, instead of walking classical diffusion speed, the walker is able to reach an average distance ~ Clk steps walking. Different from classical diffusive transportation, this method enables to collect correlation faster.
Contributions We summarize our contributions as fourfold. (1) We discuss the smooh of traditional GCN and propose the ballistic graph neural network. (2) We show the ballistic walk is faster transportation comparing to classical random walk based methods. (3) We use the ballistic walk as feature extraction, and ballistic graph neural network achieves promising performance using fewer parameters comparing to random walk based feature extraction. (4) We introduce noise to the coin space during ballistic transportation. The perturbed ballistic walk transports slower and is able to collect correlation within reasonable distance region. Thus the perturbed ballistic walk is better representation comparing to pure ballistic filters.
BALLISTIC WALK ON GRAPH
In the following, we will focus on the regular graph to demonstrate the ballistic graph neural network, where image, video and speech data represented.
2.1 INTRODUCTION TO BALLISTIC WALK
The ballistic walk algorithm consists of two parts, a walker in the position space Hapatial and coin in the coin space Hg. Thus the walker is described using states in Hibert space H Hapatial @ He- Let the walker initially be at the state 1 j. @ So, where so is normally symmetric state in Ho. In analogy to the classical random walk, the next state of the walker can be expressed by [V = ú | where Ō consists two operations, flip operation Oznin in the coin space and shift operation S the spatial space.
In this paper, consider the ballistic walk regular dio--immniiinll graph. The coin space H., consists of four states: [4), It). |+), |++, represents move up, down, left and right for the next step. The spatial space H. Hspatiat consists N states representing the walker's position, where N is
4

---

Under review as a conference paper at ICLR 2020
the number of nodes. The notation In) denotes orthonormal basis for Mapatial and (nl is the Hermitian conjugate of the state. For a dimen--iimeniinal vector space, the inner product (n' [n) is onn' and the outer product (n') (n] equals to matrix in RNN,, The probability stay the node
(i,5) - ( ( & |s) 2 Pseudo-code of our method given in Algorithm
Algorithm 1: Ballistic walk on 2D regular graph
Result: The walker's state after K steps start from (1,j)
1 [.,))
I/ The start point
so [4]+b --)+
ba, C; |all + +1] +||e|l +|dd|
3 Eng 1
@ [+]+ Li [XXU|+
Eis (,j++ 1).0,) - Eis 1 @ |-X-|
4 Ocoin = H
IIH is usually the Hadamard matrix
5 Vo) = =po 2 80
6 W1) = =S(po & sn)
7 for: 2; i K; i do
,,,) = 5(0 coin \
8
end
2.2 EXPERIMENTS
Methods In the last section, we introduce the ballistic walk on 2D regular graph. Next, we use ballistic walk as feature extraction layer and learn graph representations. The experiment
00000000
Ballistic Walk
2000000
time=0
Fully connected
Fully connected
Input image
Every non-zero pixel as start point
...0000000
Number of class for Classification
Ballistic Feature Layer
Number of hidden units
Figure 4: Schematic layout: Take every non-zero pixels start points, the feature layer is the stack of ballistic distributions.
constructed as follows. Taking MNIST classification example. First, take the non-zero pixels as the start points the ballistic walk. The ballistic distributions at different time steps of digital are shown in Figure 5 The stacked ballistic feature layer is then fully connected to set of hidden units with relu activation. The final layer's width is the number of classes(for MNIST 10) with softmax activation for class prediction(shown in Figure 4h.
1
Results
The Hadamard matrix 76 is
-1 and the initial state is V, = 1j/2 + 1/22
v2
1 -)). Figure 5 and show the difference in diffusion between the random walk 28 28 grid starting from the center. Comparing to
based diffuuson and the ballistic diffusion the classical random walk, the ballistic walk shows cohesive behaviour and transports faster. The comparison between the speed is shown in Figure g
The diffusive classical walk's 'ss distances at time = 15 and time = 20 center around the same range. The ballistic walk's 's differences more significant, which means collecting different information. Comparing to classical random walk, the ballistic walk has a speed of C.. This linear transportation behaviour enables the filters collect correlation the graph more efficiently.
5

---

Under review as a conference paper at ICLR 2020
o
o
(a) Step:1
(b) Step:2
(c) Step:3
(d) Step:4
(e) Step:5
(f) Step:6
(g) Step:7
(h) Step:8
(1) Step:9
(i) Step: 10
Figure The ballistic distributions on digital at different time steps.
S.D.
2.0
044
630
1311
0.01
Step:1
Step:5
Step:
Step:
(e) Step:20
Figure 6: The classical diffusion at different (starts from point)
639
1055
E30
3039
1000
64:
3650
00
39
3080
(a) Step:1
Step:5
Step:10
(d) Step:15
(e) Step:20
Figure 7: The ballistic diffusion at different (starts from point)
As shown in Figure 8 the distance for diffusive walk at Lime 25 is around taking an 8-step ballistic walk. Defferrard et al. (0016) considers 25 steps diffusive filters to approximate 5 x kernel with 10 feature maps( 10 hidden units). For comparison, the same number of feature maps. The feature maps are then fully connected to 10/32 units and then connected to 10 units for classification. The notations denoted Ball10 and Ball32. Table [ summarizes the capabilities of our model compared to other recent modeling approaches.
take 8-step-ballistic kernel with
Structure Ballió
Ball32
GCIO(Non-
GCIO(Spline) 97.26(K=25)
GCI0(Cheb)
Accuracy
97.21(K=8)
97.38(K=8)
95.75(K=25)
97.48(K=25)
Structure
ManiReg 94.62
DeepWalk
GCN
GAT
GLCN
Accuracy
95.34
91.01
92.81
95.46
Table 1: Results on MNIST dataset using Ballistic filters with K 8 compared with traditional ceffusionbbased graph convolutional network with K = 25 in Defferrard et al. (016)
Baselines
We compare approaches with the following baselines:

---

Under review as a conference paper at ICLR 2020
15
Distance
Diffusive Hallistic
10
0
10
15
20
25
Time step
Figure 8: The diffusion behaviour of ballistic and diffusive walk.(start from a point)
0.30
0.25
Ball10
0.20
Ball32
Loss
0.15
0.10
0.05
0.00
5000
10000
15000
20000
lterations
Figure Results of one layer Ballistic graph network with 10 and 32 hidden units on MNIST dataset. The feature layer include 8 ballistic filters.
(2014) uses local information obtained from truncated random walks. For iterating over all the vertices of the graph, the authors generate random walk [W, for every node, and then use it to update representations.
Walk:alk: Perozzi et al.
Graph Attention Networks (GAT); Veličkovćć et al. (017) assigns different weights different nodes neighbourhood. The graph attentional layer changes the weight distribution on the neighbourhood nodes.
Manifold Regularization (ManiReg): Belkin al. (2006) brings together ideas from the theory of regularization in reproducing kernel Hilbert spaces, manifold learning and spectral methods. In the paper, their propose data-dependent geometric regularization method based on graph Laplacian.
Graph Convolutional Network (GCN): Kipf Welling (2016) conducts the following wise propagation in hidden layers using random walk based method((
o
AD- (p) Doftmax(D-1/2, AD- 1/2 (x))))((()))
The final perceptron layer for classication is defines as: Z
Graph Learning-Convoluttonn Convolutional Networks(GLCN)) Jiang et al. (201)) contains one graph learn- ing layer, several graph convolution layers and one final perceptron layer. The layer-wise propaga-
tion rule is: (k+1) oDD, 1/2 - (4)
REVISITING THE SPEED PROBLEM
In the last section, we introduce the ballistic walk, which transports faster than the diffusive classical walk. By selecting the ballistic filters up K= 8, we reach 97% and use 1/3 parameters comparing to spline method using classical diffusive filters. This suggests ballistie filters are able collect correlation more efficiently comparing to random walk based Laplacian filters.
Figure shows the transportation behaviour of different kinds filters. There exists two phases: 'trapped to diffusive" phase and 'diffusive to ballistic' phase. The laplacian-based filters can be regarded as the up-bound filters the trapped to diffusive phase(the orange points) and obey the /steps law. As the steps grow, the filters inefficient. As shown in the Figure 10. the filters repeatedly sampling the region with distance<< 10 as the steps grow up to 70 steps, this means the filtered information be very similar, leading invalid feature layer. The ballistic filters lie the
7

---

Under review as a conference paper at ICLR 2020
40
20
Go the boundary
Dilisere
15-
Ballone
10:
30
5:
Distance
Localize near the start point
15
25
35
20
Diffusive to Ballistic phase
10
Trapped Diffusive phase
0
0
10
20
30
40
50
60
70
Time step
Figure 10: Comparison between diffusive and ballistic transportation. Classical diffusive walk transports slower and localizes near the start point, and ballistic walk moves beyond the boundary as steps grow. We are interested in learning the information with in the 28 x 28 gird.
up-bound of the 'diffusive to ballistic' phase(the blue points), the linear propagation ensures gathering the long correlation information in relatively small number of steps. However, linear transportation also brings drawbacks:
Sparse sampling at the mid-distance region: as shown in Figure 10 (figure in the figure), for 35-steps walk, the points from distance 6 to distance = 13 enables the ballistic filters better interpret the long correlation. However, the distance intervals between the ballistic filters are relatively sparse, and this can result in the missing of correlation.
Beyond the boundary: the linear ballistic transportation makes the walker go beyond the boundary (for our case the distance is 14). With the same number the steps, the ballistic walk travels the boundary line(shown in Figure
Is there way generate filters that collect the correlation within distance 14 while circumventing cumbersome classical diffusion? In other words, we are interested in generating filters with a transportation speed between ballistic and classical diffusion. By controlling the speed of the filters, we circumvent going beyond the boundary and make all our filters localized between the regions with restricted distance the diffusive to ballistic phase in Figure TO
(c)
Figure 11: Comparison between ballistic and classical transportation. (a) Classical diffusion started
from a line; (b) Classical diffusion started from a point; (c) Ballistic diffusion started from a line; (d) Ballistic diffusion started from point. The ballistic filters have the exceeding boundary problem.
8

---

Under review as a conference paper at ICLR 2020
4 DE-COHERENCE
In the ballistic diffusion, we use Hadamard transformation on the coin space, The Hadamard operator (SU(2)) helps spilt the state in the coin space and finally leads linear ballistic transportation. However, mentioned in the last section, we are interested in generating filters lines between ballistic and classical phase that we can eireumvent the boundary and transppototta problem. In this section, we introduce the de-coherence scheme to perturb ballistic transportation by adding noise term to the Hadamard operation at every step. This noisy perturbation results in the de-coherence of ballistic filters and thus slows down the transportation.
4.1 THE INTRODUCTION TO DECOHERENCE
We want our filters have diffusion distance in a reasonable region(a < Dislance < b). However, the ballistic filters' distances increase with steps. The filters not capable to dense sampling some specific regions, By selecting different randomness and steps, we generate filters localized in bounded area. The noisy Hadamard can be written as
1 = e 18
e4
(3
(6)
-1
Table 5 shows the accuracy with different perturbed filters(a
Randomness
= 0
0.01
0.05
0.1
0, 0.10, 0.15, 0.20). 8 = 2 x R x denotes the randomness in the coin space, Rt is random num- ber between 0 and 1. The correspond- ing transportation speed is shown in table 2 and Figure [2] As the a in- creases to 0.20, the speed drops to 0.323. a controller of the diffusion speed, as a becomes larger, the ballistic tranportation will finally evolve to the classical diffusive couterpart.
Speed
0.612
0.608
0.586
0.516
Randomness
Q 0.15
a 0.20
a 0.25
0.30
Speed
0.414
0.323
0.268
0.240
Table 2: Diffusion rate with different randomness
Diffusive
20
a=0.01
a=0.55
15
0=0.10
Distance
0=0.15
0.20
Q=0.25
Q=0.30
5
0
0
5
10
15
20
25
30
Time step
Figure 12: Comparison between diffusive and hallistic transportation with different random Hadamard operator.
4.2 SUMMARY OF THE SPEED WITH RANDOMNESS
After taking randomized operations, the accuracy can be improved. In other words, by using filters from the perturbed ballistic walk, avoid the shallow sampling and slow transportation problem by selecting the step and the randomness of the ballistic walk. The 'meaningful regions' denoted blue and yellow Figure T0 (figure in
now able dense sample the 'meaningful regions' and

---

Under review as a conference paper at ICLR 2020
Canv 2x22 Sinde 2
Fillra
28
28
512
Figure 13: The model architecture with 25 filters as feature maps
the figure). In model, fix the first eight filters the pure ballistic filters without perturbation. We then select different filters from perturbed filters. The model architecture is shown in Figure [3 The input signals first passed 25 different feature maps using the selected filters. We then apply the convolutional operation and average pooling on the feature maps. After a fully connected layer with 512 hidden units, the network is connected select our filters up to the distance<14 regions(~ 25 steps for ballistic duffusion), and this ensures the filters gather the correlation information within reasonable regions. For pure ballistic filters,
10 units for the classification task. We
Filter Index
Ballistic(a
0.1
a 0.15
0.05
a 0.20
Accuracy
99.11 0.13
1-25
0
0
99.14=0.17
1-8
9,10
24,25
10-23
99.32 0.09
1-8
3-10
4-10
8,9
0
99.35 0.07
1-8
1-8
1-8
0
99.23 0.13
1-8
2,4,6,8,10,12
3.6,9.12.15.18
2,4.6,8,10
99.32 0.06
1-8
3,6,9,12
3,6,9.12
3,6,9,12
3,6.9,12.15
99.39 0.09
1-8
3,6,9,12
3,6,9,12
9,12,15,18
12,15,18,21
Table Accuracy with different randomized Hadamard operations. We use 25 filters with different steps and randomness for each case.
the classification accuracy is around 99.11%, when we keep the first eight ballistic filters and use different filters with different randomness, the accuracy increases to 99.39%. Our results show that the classification accuracy can be improved using mixture of perturbed filters.
4.3 COIN OPERATOR
The ballistic walk filters can also be generalized to different coin operators. Except using Hadamard and noisy Hadamard coin operator, we can also use discrete Fourier operator(DFO) or Grover operator, the discrete Fourier operator is written:
1
wd-1
1
w
w
DFO
d1/2
1
2
w
w6
I
wd-1
()d--1)
1)
wld (d--1)) 1)d-1)
w
w9
where = 2xi/d is the dth root of unity, d is the degree of regular graph, and the Grover operator is:
b b b
-1
1
a b
b
1
1
G
(8)
..
...
2
1
-1
b
b
1
-1
where (2/d) - and b = 2/d. The results are shown in Table Note that usually select unitary operation the coin space to keep the probability as a constant. However, not every unitary operator results in ballistic transportation, the Grover operator will localize near the start point the steps gshow in Figure [4p. however, they all have a speed-up effect comparing to the classical diffusive filters. The DFO and Grover operator have transportation speed between the ballistic
10

---

Under review as a conference paper at ICLR 2020
Structure DFOTO
DFO32 97.58
Grover10 97.26
Grover32
Accuracy
97.32
97.39
Table 4: Performance using Grover and DFO filters using NN structure in Figure
(a)
Difusive
10
DRO
Grover
8
Ballsti
Distance
2
10
Time step (c)
(b)
Viraaion Intere
12
25
15
20
30
20 25 25 25
Figure 14: Comparison between DFO and Grover operator at 15 steps. (a) The transportation speed. (b) The walk's distribution after 15 steps using DFO. (c) The walk's distribution after 15 steps using Grover operator.
filters and diffusive filters, thus can be regarded as special forms of randomized filters. The general Hadamard coin is balanced. DFO retains the balanced properties in coin space is obtained with equal probability. The Grover operator helps retain the symmetry of the signal and is permutation symmetric. The Grover operator is not balanced coin because the probability( weight our case) does not change its propagating directions(p = (1 - 2/d)²).
general graph. Every state
5 CONCLUSION AND FUTURE WORK
In this paper, we introduced generalization of graph neural network: ballistic graph neural network. We started from the speed problem the traditional diffusive kernel and tackle this problem from the perspective of transportation behaviour. We showed the linear transportation behaviour of ballistic filters and introduced the de-coherence scheme to adjust the filters' speed. Compared with diffusive filters, the ballistic filters achieve similar accuracy using fewer of the parameters. Besides, showed that the efficiency of the ballistic filters could be improved by controlling transportation behaviour. Compared the random walk method, used two operators: the coin operator and shift operator control the walker, and thus controlled the information the walker gathers. Our pipeline provides new perspective for efficient extracting the graphical information using diffusion-relann models.
Future work can investigate these two directions:
The Network Structure. In this paper, we use simplified architecture to demonstrate the concept of the ballistic walk, the layers limited 5 layers, and traditional average pooling. More layers can be added to improve particular accuracy, and more sophisticated pooling methods can be IntroduceDeeffenee et (2016). Other techniques like dropout can also be employed improve accuracy.
The Ballistic Filter. De-coherence can also be introduced into the shift operator. In other words, can perturbed shifted operator, and thus introduce randomness in the spatial domain. We

---

Under review as a conference paper at ICLR 2020
also try different unitary operators in the coin space change the initial state of the walker. The extension to general graphs can be generalized by adding self-loops to the nodes and thus make the graph regular.
DISCUSSION: BALLISTIC FILTER IN ONE DIMENSIONAL CONDITION
The ballistic filters inspired by two-dimensional quantum walk. The quantum coherence effect guarantees fast ballistic transportation. The different states the coin space can regarded as the independent state from spatial behaviour, for example, the spin of fermions or the polarization of light. More information about the quantum walk can be found at Childs et al. (2003).
Why introducing ballistic filters results in better performance? We here offer conjecture from the perspective of signal processing using one-dimensional condition.
The classical diffusion in the one-dimensional case has the shape of:
(
ex²
(9)
and the frequency part can be written as:
=34²
î(f)
(10)
The (()) can be regarded as gaussian low pass filter. For a gaussian high-pass filter, the spatial distribution is Makandar & Halalli (2015)
- x2
hg(#) C(1 - 2
(1I)
The long time probability distribution of ballistic walk is Luo Xue 2015
(8)
(0)
0.08
0.04
0.33
0.04
0.02
0.02
0.11
0.00
0.3
Figure 15: Different distributions. (a) cumulative distribution of 24th and 25step of ballistic diffusion. (b) Gaussian high pass filter.
P(x) = Po + ae
(12)
Figure 13 shows the distribution of gaussian high pass filter and the cumulative distribution 24th and 25step of ballistic diffusion. These two distributions have similar shape while the ballistic distribution has steeper edges resulted from fast transportation.
1.0
0.8
0.6
0.4
0.2
0.0
16
-10
-5
5
10
Position
Figure 16: Ballistic diffusion with pulse signal.
The ballistic filters' capability to collect the long-time time probability means it can act as a high-pass filter with different sizes. The size of the filters depends the walking steps. Figure shoss the ballistic
12

---

Under review as a conference paper at ICLR 2020
diffusion with pulse signal from f =- to The orange dashed line is approximated shape of ballistic transportation of the leftmost signal(t = -T), and the blue dashed line corresponds to т. The width of the approximated shape is related to the walking steps. For random walk based diffusive transportation after certain steps of diffusion, the region from / - to / = have a gaussian shape since it is sum of gaussian distribution with centers range from f - to = The classical diffusion acts like blur filter(low pass filter). For ballistic diffusion, the shape of the pulse signal from t -7 to & т evolves 'valley' shape and thus, the ballistic diffusion is similar to a high pass filter.
(a) 0.25
(b) 0:5
(0)
0.15
0.15
Charsec
0.06
0.06
Postlon
Poatton
-10
Figure 17: Schematic diagram of different filters and their Fourier transformation.
Figure 17 (a) and (b) shows approximate shape of the one dimensional ballistic and classical filtering result with pulse signal from -3 to f 3, respectively. Figure 17 shows the Fourier transformations. With faster transportation, the filters are capable of collecting more high frequency compared to localized diffusive filters.
Acknowledgement
We thank Nvidia for donating NVIDIA DGX-1 used for this research
REFERENCES
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (Nov):2399-244) 2006.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 2013.
Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by quantum walk. In Proceedings of the thirty-fifth annual ACM symposium Theory of computing, pp. 59-68. ACM, 2003.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.00 556..5 05.o..0566... 163, 2015.
Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang. and Bin Luo. Semi-supervised learning with graph learning-convolutions networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11313-11320 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. 2016.
arXiv preprint arXiv:
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusson convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint 1707.07707.11266 2017.
13

---

Under review as a conference paper at ICLR 2020
Hao Luo and Peng Xue. Properties of long quantum walks in and two dimensions. Quantum Information Processing. 14(12):43614333 2015.
Aziz Makandar and Bhagirathi Halalli. Image enhancement techniques using highpass and lowpass filters. International Journal of Computer Applications, 109(14):12-15, 2015.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 701-710. ACM, 2014.
Dinh Tran, Nicolò Navarin, and Alessandro Sperduti. On filter size in graph convolutional networks. In 2018 IEEE Symposium Series Computational Intelligence (SSCI), pp- 1534-1541. IEEE, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903 2017.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: 1902.0713, 2019.
14

---

Responses to Reviewers
on Paper Beyond Classical Diffusion: Ballistic Graph Neural Network
Referee #3 and #2:
More experiments to demonstrate the power of ballistic comparing to classical ones. Classification on different DATASETs (accuracy %)
Name of dataset
Classical Diffusion
Classical Diffusion
Ballistic (this paper)
based (LI)
based ((2))
CIFAR-10
93.65
93.49
94.73
CIFAR-100
60.30
59.51
61.24
STL-10
55.28
58.87
63.32
[ Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv
preprint (.XXv:16699029000 2016.
[2] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Referee #1:
the contribution is only a new kind of random walk on graph, ICLR the good targeted venue?
Response: Answer: Yes, random walk on graph is a very important problem. In GCN, random walk is the way you collect the information. The traditional pipeline is show attached.
Feature Extraction
Feature Extraction
Manifold
Wo
W
Output
The Feature Extraction lies as the cornerstone of the GCN problem:
For almost all previous papers, the methods used are based on a random walk (Laplacian matrix), resulting in the over-smooth problem as Referee #3 mentioned. The method we propose in this paper is inspired by quantum diffusion and is completely different from the previous one. Our method also achieves better performance.

---

Referee #1 and #2:
The proposed algorithm is not clear.
Response: In light of the reviewer's recommendation, we now present the algorithm in one- dimensional condition for better understanding and ballistic concept.
The ballistic concept is not introduced at all in section Referee #1
The ballistic concept is taken from Condensed Matter physics. (please see the introduction in this link http://asdn.met//sdneeeeeeee mntttasctteeeccroonsssstrprppppp For Electron Transport in Semiconductors. There three types of transportation behaviour: Diffusive, quasi- Ballistic and Ballistic. Please see the attached figure. The 'Ballistic' means transportation is exponentially accelerated.
Response:
Diffusive
ly
Quasi ballistic
(b)
Ballistic
(4)
W
Lec1
The proposed algorithm.
Response: Here we demonstrate the algorithm in one-dimensional case, this algorithm is also called quantum walk, for one-dimensional case, please see here: Section
Discrete Time Quantum Walks https:://n. wwtp://wwwiiiiiiaraa/iiiiiaaaaaa walk There are two operators, "coin flip" operator and conditional shift operator, which are applied repeatedly.
1. First, the distribution one-dimensional line (9 nodes: = -4 to 4) is:

---

10,000000111000000000
The state on the middle node (x= V2 (lleft) + |right)). The left state means go left and the right state means go right, the state is in the coin Hilbert space. |left) corresponds to 2) and |left) corresponds to ())
2. (Coin space operation) Then we apply the coin operator, in one-dimensional case the coin operator is the Hadamard Gate. H operator on the state
1 2 1 apply coin
V2 1
V2 (lleft) + (right)) - H (3)== V2
1+i = 2 +
H
((1 + 1lleft) + (1
1 1-1
1) bright)
(Spatial space operation) Now the line is 1,0,0,00,,0,,,000,,iii a state
(1 + +illeft) + (1 (1-i) (1)rgghtt)) on x = 0. For every node, move the Ileft) state amplitude to left node and |right) to right node.
Now the line is {0,0,0, (1 + 0,,
0, 2 (1 - i), 0,0,0) with pure state Ileft) on state amplitude: the distribution on a line becomes:
x = -1 and pure state Iright) on x = =
The probability is the norm (multiply the conjugate complex number) of the
10,0,0,
1 - 0, 0,0,0) 0,0,0)
with pure state |left) on x = -1 and pure state |right) on x = 1.
3. Coin space operation: the amplitude distribution on line last moment: (0,0,0, (1 (1+1) 1), (1+
(1 (1,
Using coin operator :H (1+1)
() = 1+1 1
on = -1 and H (1-1)
2/2
1-1 1 }.. For x = -1, 1+1 1
= 1+1
lleft) + 1+1 Iright), moves the 2
3/
v2 1
2v2
lle deft) state amplitude to left node and |right) to right node. Same as For x 1.
(patiall space operation) the amplitude on the line becomes 1+1 10,0, 2/2 |left),0,
1+1
1-t
2v lright,, 0, 1-1 2 |right), 0,0)
2vž lleft) +
1t1 0, //2 0, 0,0) 10,0, 2/2
1-1
2V2'
With |left) at x -2, 1 ((1 + i)lleft) + +1 - --)-rrgtthh)) at x = 0 and
|right) at x 2.
The probability is the norm (multiply the conjugate complex number) 1 2
(0,0, 4' 2' 4'
,, 0,0}
Repeat the two operation again and again.
Here we plot Probability (not amplitude) evolution on line with 21 nodes.

---

-00
-388
t=0
t=1
t=2
9.7
076
020
0.20
000
600
t=3
t=4
t=5
0200
0375
0.1
t=8
Referee #3 the over smooth problem:
The smooth problem means after apply traditional Laplacian-based matrix on manifold; the distribution will become more and more 'flat' on the spatial domain, as shown in the figure below:

---

small steps
The nodes within this region are indistinguishable Because of the flat distribution result from the classical
diffusion
large steps
But the ballistic diffusion avoids this problem, see the attached figure:
The nodes within this region are distinguishable Because the ballistic distribution
Spatial Domain

---

Ballistic diffusion MNIST dataset: (step 0 to 10)
2
2
2
2
2
8
2
2
7
28
20

---

3
3
3
3
7
>
>
88
4
4
4
5
5
S
5
8

---

6
6
6
<
7
7
7
7
1
8
8
8

---

9
9
9
9
28
Classical diffusion on MNIST dataset (equal to low pass filter discussed in the paper):
(only step 10)
6
8
1
5
4
3
2


Reviews:
[{"review_id": "rkePgdaptB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "The paper \"Beyond Classical Diffusion: Ballistic Graph Neural Network\" tackles the problem of graph vertices representation. While most existing works rely on classical random walks on the graph, the paper proposes to cope with the \"speed of diffusion\" problem by introducing ballistic walk.\n\nI noticed the comment of the authors that gives a correction for the introduction. But even with it the paper remains very cryptic, with very few pointers to help the reader in understanding the contribution. The introduction (even corrected) is very abrupt and it is very difficult to understand the problem that the authors propose to attack. The problem is that authors start with mathematical discussions before presenting the manipulated concepts and formalizing the adressed problem. I only understood the adressed problem after seing which are the baselines the proposal is compared with in section 4.2. Also, the introduction does not introduce the proposal at all. \n\nA symptomatic example of the lack of paper positioning is the Related Works section which does not even give a single reference !  A related work section with no related works in it appears to have a limited interest to me...  This section should at least introduce other works in the field of graph embedding, such as those reported as baselines. It would also greatly help to understand the contribution of the paper. Also, the ballistic concept is not introduced at all in section 4. Where does this term comes from ? The proposed approach is completely cryptic, with clearly not enough definition of the notations the algorithm deals with. A global view of the approach, from the input graph to the final representation, would also be required to help the reader to understand the proposal. If the contribution is only a new kind of random walk on a graph, is ICLR the good targeted venue ? If authors think so, they should present their contribution in a representation learning perspective, which would highlight the importance of this new walk for the graph representation learning process. \n\n\nFrom my point of view, without a full re-writting of the paper, this work cannot be published in a conference like ICLR.   ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJxnbHqiFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposed a new diffusion operation for the graph neural network. Specifically, the ballistic graph neural network does not require to calculate any eigenvalue and can propagate exponentially faster comparing to traditional graph neural network. Extensive experiments have been conducted to verify the performance of the proposed method.\n\n1. The motivation of this method is to accelerate the diffusion speed in a graph. However, as we know, a very severe issue of graph neural network is the over-smoothness issue. The reason is that, in the high layer, the node feature is diffused to far neighbours.  When using the proposed ballistic filter, node features diffuse much faster than the regular GNN. Thus, the over-smoothness will appear in the shallow layer very fast. As a result, we cannot use many layers so that the non-linearity of deep neural networks cannot be fully utilized. Thus, is it necessary to accelerate the diffusion speed for graph neural network?\n\n2. There is only one dataset for  the comparison of the performance of different graph neural networks. More datasets are needed to thoroughly verify the performance of the proposed ballistic graph neural network.\n\n3. Is it possible to slow down the diffusion speed with the proposed ballistic filter?\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJxcTdsmcH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 was extremely hard to read or comprehend. It’s riddled with typos, inaccurate notations and undefined variables (see below for a sampling). The authors will need to significantly polish and improve the presentation of the paper. \n\nAfter a few forward and backward passes through the paper, I was able to gather the following high level ideas about the paper:\n(1) This paper is somewhat related to the Defferard et. al, 2016 in that the authors want to define a propagation filter for graph neural networks.\n2) This proposed filter known as “ballistic filter” should have the property of allowing fast diffusion through the network. \n(3) The authors claim that the ballistic kernel diffuses @ O(k) as compared to O(\\sqrt k) when compared to traditional GCNs, where k is the number of propagation steps.\n(4) The authors additionally claim that their approach needs one-third the number of parameters.\n(5) The authors provide some plots to visualize the linear diffusion rate of their proposed filter.\n\n--- Issues and clarifications ---\n- Sec 3, Eq 1 seems to have been taken from Eq 1 in Defferard et. al, however there’s no reference to it and the terms g, U, etc. are not defined.\n - Sec 4, Algo 1 contains the main core of the proposed algorithm, but it’s only defined for the 2D grid case. The notation therein is extremely unclear. What is H_space, H_c? How does one sample \\hat{O}_coin.? The net result is that algorithm is undefined. Without a clear definition of the algorithm, it’s completely unclear what the proposed method does.\n - Sec 4.2 is completely unparseable. What is problem setting? What is the metric? How have the baselines been implemented? How has data been split for training/testing?\n - Section 5 mentions that one-third params are used to get 97% but no details are provided as to how less params are consumed.\n - How is figure 7 generated?\n - Sec 8, feel totally unrelated to the paper. There are a whole bunch of random, unmotivated diffusion equations  Eq 6, mentions “.. \\hat{g}(f) decreases as f increases and thus can be seen as a low pass filter…” . This is not true from the formula.\n \n\n --- A sampling of typos ---\nSec 4.1, .. consisits …\nSec 5 “REVISIT” -> “REVISITING”\nFigure 6, text, “cassical”\nSec 6.2 title, “SUMMAY”\nSec 8  “aggreated”\nSec 8  t=\\-tau to -\\tau\nSeveral typos with Hardmard, Hadmard instead of Hadamard.\n\nOverall, the major criticisms of this paper:\n - The proposed algorithm is not clear. \n - The authors need much more experimentation to bolster their claims in the paper. It’s completely unclear if fast diffusion even if it were possible will help GNNs perform better on a diverse set of tasks.\n - The paper needs a lot more polish and proof reading to make this paper presentable.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission has been assessed by three reviewers who scored it 3/1/3, and they have remained unconvinced after the rebuttal. The main issues voiced are the difficult readability of the paper, cryptic at times due to a mix of physical and DL notations, and a lack of sufficient experimentation to support all claims. The reviewers acknowledge the authors' efforts to resolve the main issues but find these efforts insufficient. Thus, this paper cannot be accepted to ICLR2020.
Decision: Reject