# GraphSAGE-Based Multi-Path Reliable Routing Algorithm for Wireless Mesh Networks
## 3 Multi-Path Routing Algorithm Based on the Improved Breadth First Search
### Multipath Output
The process of neighbor nodes aggregation is as follows: \[h^{k}_{N(v)}\gets Mean(\left\{h^{k-1}_{u},u\in N(v)\right\})\] (11) where \(N(v)\) denotes the set of neighbor nodes of node \(v\); \(h^{k-1}_{u}\) donates the feature representation of the neighbor node \(u\) at layer \(k-1\); \(h^{k}_{N(v)}\) donates the aggregated features of neighbor nodes of node \(v\) at layer \(k\). The process of node \(v\) at layer \(k\) to generate vector representations is as follows: \[u_{ij}=\frac{1}{\sum\limits_{k=1}^{c}{\left(\frac{d_{ij}}{d_{k}}\right)^{\frac{ 2}{m-1}}}} \tag{4}\]0 (12) where \(CONCAT\) uses the residual concatenation to linearly superimpose each feature vector; \(W^{k}\) is the weight matrix to be learned; \(\sigma\) is a nonlinear activation function; \(\left\{h^{k}_{v},k=1,2,\cdots,K\right\}\) represents the vector representation of node \(v\) at layer \(k\). When \(k=0\), the vector representation of node \(v\), is defined as the input feature of node \(v\), i.e., \(h^{0}_{v}=x_{v}\). 3. Embedding generation: The vector representation of each node in layer \(K\) in the graph structure is obtained as the final vector representation \(z_{v}\) for the following node classification task. The process is as follows: \[u_{ij}=\frac{1}{\sum\limits_{k=1}^{c}{\left(\frac{d_{ij}}{d_{k}}\right)^{\frac{ 2}{m-1}}}} \tag{4}\]1 (13) GraphSAGE embedding generation algorithm describes the process of GraphSAGE to generate node vector representations, which is as follows (Algorithm 2). \[u_{ij}=\frac{1}{\sum\limits_{k=1}^{c}{\left(\frac{d_{ij}}{d_{k}}\right)^{\frac{ 2}{m-1}}}} \tag{4}\]2 The process of GraphSAGE to generate node vector representations. After obtaining the vector representations of nodes, it is also necessary to learn the parameters of the GraphSAGE model. Weight matrix \(W^{k}\) is the core of GraphSAGE, which contains the mapping relationship of the aggregated features of neighbor nodes to the vector representations of the target node. Therefore, the main process of parameter learning is to train a good weight matrix. And the network labels generated in Section 4.1 allow for supervised learning of the parameters. The cross-entropy function is used as the loss function for the node classification task [24]. The loss function is as follows:

\[u_{ij}=\frac{1}{\sum\limits_{k=1}^{c}{\left(\frac{d_{ij}}{d_{k}}\right)^{\frac{ 2}{m-1}}}} \tag{4}\]3

where \(y_{Label}\) represents the set of nodes with labels; \(y_{vi}\) represents the network labels after One-Hot encoding; \(l\) represents the number of network labels classes. The vector representation \(z_{vi}\) of node \(v\) is obtained through forward propagation, and then the gradient descent method is used to perform backpropagation to update \(W^{k}\) and parameters in the aggregation function until the loss value does not change. At this point, the model has converged and can correspond well to the nodes in the network topology to the network performance. The trained GraphSAGE model can directly follow Algorithm 2 to complete feature aggregation in the face of new topologies and node features, yielding the results of network performance classification of nodes. Assume that the multiple shortest paths iterated by the multi-path routing algorithm are \(Path=\{p_{1},p_{2},\cdots,p_{m}\}\), and each path consists of several nodes. The class of each node in the network topology can be obtained by inputting the network topology and node feature information into the trained GraphSAGE model. After knowing the class to which the node belongs, the corresponding network performance value of the node can also be known. The network performance of each shortest path can be defined as the sum of the network performance of each node in the path, then the network performance of the shortest path \(i\) can be written as:

\[u_{ij}=\frac{1}{\sum\limits_{k=1}^{c}{\left(\frac{d_{ij}}{d_{k}}\right)^{\frac{ 2}{m-1}}}} \tag{4}\]4

where \(performance_{v}\) represents the network performance of node \(v\); \(v\) is a node in the path \(p_{i}\).