## 3 Route Planning Scheme Based on Scatter-GNN
### Problem Definition
Among them, the attention coefficient \(e_{ij}\) can be defined as:

\[e_{ij}=F\Big{(}W\overrightarrow{v}_{i},W\overrightarrow{v}_{j}\Big{)} \tag{21}\]

It represents the importance of site \(j\) to site \(i\), regardless of graph structure information, and \(F\) is a self-defined function. In order to make the attention coefficient easy to understand and easy to compare, this paper introduces a softmax function to regularize all adjacent sites \(j\) of site \(i\):

\[\alpha_{ij}=softmax_{j}\big{(}e_{ij}\big{)}=\frac{\exp\big{(}e_{ij}\big{)}}{ \sum_{k\in N_{i}}\exp(e_{ik})} \tag{22}\]

After adding the LeakyRelu function and substituting it into formula (21), the complete attention mechanism is expressed as follows:

\[\alpha_{ij}=\frac{\exp(\text{LeakyRelu}\big{(}\overrightarrow{F}\Big{[}W \overrightarrow{v}_{i}||W\overrightarrow{v}_{j}\Big{]}\big{)})}{\sum_{k\in N _{i}}\exp(\text{LeakyRelu}\big{(}\overrightarrow{F}\Big{[}W\overrightarrow {v}_{i}||W\overrightarrow{v}_{k}\Big{]}\big{)})} \tag{23}\]

where \(\alpha_{ij}\) is called the normalized attention coefficient. The vector representation of site \(i\) changes from the original \(\overrightarrow{v}_{i}\) to \(\overrightarrow{v}_{i}^{\rightarrow}\) after passing through the attention layer, and then uses the multi-head attention mechanism to repeat the process \(K\) times to obtain the following formula:

\[\overrightarrow{v}_{i}^{\prime}=\bigparallel\limits_{k=1}^{K}\sigma\Bigg{(} \sum_{j\in N_{i}}\alpha_{ij}^{k}W\overrightarrow{v}_{j}\Bigg{)} \tag{24}\]

where \(K\) represents the stacking layers of the attention layer, \(\mid\mid\) represents the row vector splicing operation, and \(N_{i}\) is the first-order neighbor set of the site \(i\in V\). The \(K\)th attention mechanism in the multi-head attention mechanism is \(\alpha^{k}\), and \(W^{k}\) is the linear transformation weight matrix of the input features under the \(K\)th attention mechanism. The focus of multi-head attention is different, which makes the model compatibility better. Finally, in order to make the prediction effect of the model more stable, the splicing vector is K-averaged to obtain the final feature of each site \(\overrightarrow{v}_{i}^{\prime}\), \(\overrightarrow{v}_{i}^{\prime}\) indicates that the output feature of each site is related to all its adjacent features, which is obtained after activation of their linear and nonlinear functions. \[\overrightarrow{v}_{i}^{\prime}=\sigma\Bigg{(}\frac{1}{K}\sum_{k=1}^{K}\sum _{j\in N_{i}}\alpha_{ij}^{k}W\overrightarrow{v}_{j}\Bigg{)} \tag{25}\]

Finally, the new vector representation for each pair of sites is:

\[\overrightarrow{v}^{\prime}=\Big{\{}\overrightarrow{v}_{1}^{\prime}, \overrightarrow{v}_{2}^{\prime},\overrightarrow{v}_{3}^{\prime},\ldots, \overrightarrow{v}_{n}^{\prime}\Big{\}},\overrightarrow{v}_{i}^{\prime}\in R ^{F^{\prime}} \tag{26}\]

After the aggregation operation of the K-layer graph attention mechanism, each pair of site vectors is represented by the Hadamard product. Taking sites \(i\) and \(j\) as an example, the route is expressed as follows:

\[\overrightarrow{e_{ij}}=\overrightarrow{v}_{i}^{\prime}\odot\overrightarrow{ v}_{j}^{\prime} \tag{27}\]

Finally, the probability of the existence of a route between two stations can be calculated by activating by the following formula:

\[P_{ij}=Softmax\Big{(}W\overrightarrow{e_{ij}}+b\Big{)} \tag{28}\]A binary cross-entropy loss function is used as supervised training:

\[\overrightarrow{v}_{i}^{\prime}=\sigma\left(\sum_{j\in N_{i}}\alpha_{ij}W \overrightarrow{v}_{j}\right) \tag{20}\]0

where \(|\mathcal{P}\cup\mathcal{N}|\) represents the sum of the number of positive samples and the number of negative samples in the sample space; if there is a route between stations \(i\) and \(j\), then \(e_{ij}=1\), otherwise \(e_{ij}=0\); \(P_{ij=1}\) represents the probability that the route \(e_{ij}\) exists in the line, \(P_{ij=0}\) represents the probability that the route \(e_{ij}\) does not exist in the line.