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. How to collect the nodes' correlation on graphs fast and precisely? Inspired by convolutional neural networks(CNNs), 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 on random walk diffusion based feature engineering to extract and exploit the useful features of the input data. Recent works show random walk based methods can represent graph-structured data on the spatial vertex domain. For example, Li et al. (2017) use bidirectional random walks on the graph to capture the spatial dependency and Perozzi et al. (2014) present a scalable learning algorithm for latent representations of vertices in a network using random walks. Except for the spatial domain, many researchers focus on approximating filters using spectral graph theory method, for example, Bruna et al. (2013) construct a convolutional architecture based on the spectrum of the graph Laplacian; Defferrard et al. (2016) use high order polynomials of Laplacian matrix to learn the graphs in a NN structure model. The ballistic walk algorithm consists of two parts, a walker in the position space H spatial and a coin in the coin space H c . Thus the walker is described using states in Hibert space H spatial ⌦ H c . Let the walker initially be at the state | i 0 = |i, ji p ⌦ s 0 , where s 0 is normally symmetric state in H c . In analogy to the classical random walk, the next state of the walker can be expressed by In this paper, we consider the ballistic walk on a regular two-dimensional graph. The coin space H c consists of four states: |#i, |"i, | i, |!i , represents move up, down, left and right for the next step. The spatial space H spatial consists N states representing the walker's position, where N is the number of nodes. The notation |ni denotes an orthonormal basis for H spatial and hn| is the Hermitian conjugate of the state. For a finite-dimensional vector space, the inner product hn 0 |ni is nn 0 and the outer product |n 0 i hn| equals to a matrix in R N ⇥N . The probability stay on the node |i, ji is Pseudo-code of our method is given in Algorithm 1. Algorithm 1: Ballistic walk on 2D regular graph Result: The walker's state after K steps start from (i, j) We want our filters have a diffusion distance in a reasonable region(a < Distance < b). However, the ballistic filters' distances increase with steps. The filters are not capable to dense sampling some specific regions. By selecting different randomness and steps, we can generate filters localized in a bounded area. The noisy Hadamard can be written as Table 2 : Diffusion rate with different randomness Table 3 shows the accuracy with different perturbed filters(↵ = 0, 0.05, 0.10, 0.15, 0.20). = 2 ⇥ R ⇥ ⇡↵ denotes the randomness in the coin space, R is a random number between 0 and 1. The corresponding transportation speed is shown in table 2 and Figure 12 . As the ↵ increases to 0.20, the speed drops to 0.323. ↵ is a controller of the diffusion speed, as ↵ becomes larger, the ballistic tranportation will finally evolve to the classical diffusive couterpart. In this paper, we introduced a generalization of graph neural network: ballistic graph neural network. We started from the speed problem of 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, we showed that the efficiency of the ballistic filters could be improved by controlling transportation behaviour. Compared to the random walk method, we used two operators: the coin operator and shift operator to control the walker, and thus controlled the information the walker gathers. Our pipeline provides a new perspective for efficient extracting the graphical information using diffusion-related 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 are limited to 5 layers, and we use traditional average pooling. More layers can be added to improve particular accuracy, and more sophisticated pooling methods can be introducedDefferrard et al. (2016) . Other techniques like dropout can also be employed to improve accuracy. The Ballistic Filter. De-coherence can also be introduced into the shift operator. In other words, we can use perturbed shifted operator, and thus we introduce randomness in the spatial domain. We can also try different unitary operators in the coin space or 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. The ballistic filters are inspired by two-dimensional quantum walk. The quantum coherence effect guarantees fast ballistic transportation. The different states in the coin space can be 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 a conjecture from the perspective of signal processing using one-dimensional condition. The classical diffusion in the one-dimensional case has the shape of: and the frequency part can be written as:ĝ The g(x) can be regarded as a gaussian low pass filter. For a gaussian high-pass filter, the spatial distribution is: Makandar & Halalli (2015) hg The long time probability distribution of ballistic walk is: Luo & Xue (2015) P (x) = P 0 + ae (12) Figure 15 shows the distribution of gaussian high pass filter and the cumulative distribution of 24th and 25step of ballistic diffusion. These two distributions have a similar shape while the ballistic distribution has steeper edges resulted from fast transportation. The ballistic filters' capability to collect the long-time probability means it can act as a high-pass filter with different sizes. The size of the filters depends on the walking steps. Figure 16 shows the ballistic diffusion with a pulse signal from t = ⌧ to t = ⌧ . The orange dashed line is an approximated shape of ballistic transportation of the leftmost signal(t = ⌧ ), and the blue dashed line corresponds to t = ⌧ . 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 t = ⌧ to t = ⌧ have a gaussian shape since it is sum of gaussian distribution with centers range from t = ⌧ to t = ⌧ . The classical diffusion acts like a blur filter(low pass filter). For ballistic diffusion, the shape of the pulse signal from t = ⌧ to t = ⌧ evolves to a 'valley' shape and thus, the ballistic diffusion is similar to a high pass filter.
A new perspective on how to collect the correlation between nodes based on diffusion properties. A new diffusion operation for graph neural networks that does not require eigenvalue calculation and can propagate exponentially faster compared to traditional graph neural networks. The paper proposes to cope with the speed of diffusion problem by introducing ballistic walk.