## 3 Route Planning Scheme Based on Scatter-GNN
### Problem Definition
### Completion of Edge Site Neighbors

In this paper, the graph attention mechanism is used to predict the link between each edge site and their corresponding potential neighbors, and then a new line network is generated. The completion process of edge site neighbors is shown in Figure 3 below:

In this paper, the Node2 vec algorithm is used to generate the eigenvectors of each station in the railway network. The specific description is as follows:

Given the current site \(v\), the probability of visiting the next site \(x\) is:

\[P(c_{i}=x|c_{i-1}=v)=\left\{ \begin{array}{cl}\frac{x_{v}}{Z},&if(v,x)\in E\\ 0,&otherwise\end{array} \right. \tag{16}\]

Figure 3: Edge site neighbor completion process. Figure 2: An example of potential neighbors of a site in the edge graph. where \(\pi_{vx}\) is the unnormalized transition probability between site \(v\) and site \(x\). \(Z\) is a normalization constant. Node2 vec introduces two hyperparameters \(p\) and \(q\) to control the strategy of random walk, assuming that the current random walk reaches site \(v\) after passing edge \((t,\ v)\). Let \(\pi_{vx}\) be the weight of the edge between site \(v\) and \(x\):

\[\pi_{vx}=\alpha_{pq}(t,x)\cdot w_{vx} \tag{17}\]

\[\alpha_{pq}(t,x)= \begin{cases}\frac{1}{p},\ \text{if}\ d_{tx}=0\\ 1,\ \text{if}\ d_{tx}=1\\ \frac{1}{q},\ \text{if}\ d_{tx}=2\end{cases}  \tag{18}\]

where \(d_{tx}\) is the shortest path distance between site \(t\) and site \(x\). The effect of hyperparameters \(p\) and \(q\) on the walk policy is discussed below. The parameter \(p\) controls the probability of repeatedly visiting the site just visited. If the value of \(p\) is larger, the probability of visiting the site just visited becomes smaller, and vice versa. \(q\) controls whether the walk goes outward or inward. If \(q>1\), the random walk tends to visit sites close to \(t\) (biasing BFS); if \(q<1\), the random walk tends to visit sites far from \(t\) (biasing DFS). After the sequence sampling is completed, the algorithm learns the vector representation of each site according to Word2 vec. The essence of Word2 vec is to use contextual information to train neural networks. It mainly has two implementation methods, namely continuous bag of words (CBOWs) and Skip-grams. CBOW trains the neural network by predicting a word from contextual information, while Skip-grams trains the neural network by predicting the context given a word. Analogy in the graph structure, its site vector learning process is described as the Algorithm 2:
```
Require:  Graph \(G=(V,E,W)\), Dimensions d, Walks per node r. Walk length l, Context size k, Return p, In-out q \(\pi=\) PreprocessModifiedWeights (G, p, q) \(G^{\prime}=(V,E,\pi)\)  Initialize walks to Empty Ensure: 1. For iter = 1 to r do 2. for all nodes u \(\in\) V do 3. walk = node2 vecWalk(\(G^{\prime}\), u, l) 4. Append walk to walks 5. f = StochasticGradientDescent(k, d, walks) 6. Return f
```
**Algorithm 2**Learning Vector Representation. Secondly, all routes in the network are added to the sample space as positive samples, and the same number of station pairs without routes are randomly selected and added to the sample space as negative samples; then, station pairs and their site vector representation is sent to the attention layer, and the input of each pair of sites is represented by a vector as:

\[\overrightarrow{v}=\left\{\overrightarrow{v}_{1},\overrightarrow{v}_{2}, \overrightarrow{v}_{3},\ldots,\overrightarrow{v}_{n}\right\},\ \overrightarrow{v}_{i}\in R^{F} \tag{19}\]

A new vector representation is obtained by aggregating the neighbor site information of each site:

\[\overrightarrow{v}_{i}^{\prime}=\sigma\left(\sum_{j\in N_{i}}\alpha_{ij}W \overrightarrow{v}_{j}\right) \tag{20}\]where \(W\) is the training weight, and site \(j\) is the first-order neighbor of site \(i\). \(\alpha_{ij}\) represents the ratio of the attention coefficient [10] of site \(j\) to site \(i\) to the attention coefficients of all neighbors of site \(i\) to site \(i\).