# Distributed Detection of Large-Scale Internet of Things Botnets Based on Graph Partitioning
## 4 Proposed Method
### Feature Learning
\begin{bmatrix}0&\cdots&A_{1m}\\ \vdots&\ddots&\vdots\\ A_{m1}&\cdots&0\end{bmatrix}  \tag{7}\]  
where \(A_{ii}\) represents the adjacency matrix corresponding to the subgraph \(G_{i}=\{V_{i},E_{i}\}\), \(\Delta\) denotes the interconnections between subgraphs, consisting of all off-diagonal blocks of matrix \(A\), and \(A_{ij}(i\
eq j)\) represents the links between subgraphs \(G_{i}\) and \(G_{j}\). Similarly, we can partition the feature matrix \(X\) and training labels \(Y\) into subsets \([X_{1},X_{2},\ldots,X_{m}]\) and \([Y_{1},Y_{2},\ldots,Y_{m}]\), respectively, based on the partition \([V_{1},V_{2},\ldots,V_{m}]\), where \(X_{i}\) and \(Y_{i}\) are formed by the features and labels of nodes in subgraph \(V_{i}\), respectively. The purpose of this partitioning is to leverage the limited computational resources of IoT devices by assigning different subgraphs to different distributed devices for training. Only one subgraph needs to be loaded into the GPU memory. As a result, the objective function for training GCN is also decomposed into different clusters. Let \(\bar{A^{\prime}}\) represent the normalized version of \(\bar{A}\), and the final embedding matrix becomes:\[Z^{(L)} =\bar{A}^{\prime}\sigma\Big{(}\bar{A}^{\prime}\sigma\Big{(}\cdots \sigma\Big{(}\bar{A}^{\prime}XW^{(0)}\Big{)}W^{(1)}\Big{)}\cdots\Big{)}W^{(L-1)}\] \[= \begin{bmatrix}\bar{A}^{\prime}_{11}\sigma\Big{(}\bar{A}^{\prime }_{11}\sigma\Big{(}\cdots\sigma\Big{(}\bar{A}^{\prime}_{11}XW^{(0)}\Big{)}W^{( 1)}\Big{)}\cdots\Big{)}W^{(L-1)}\\ \vdots\\ \bar{A}^{\prime}_{mm}\sigma\Big{(}\bar{A}^{\prime}_{mm}\sigma\Big{(}\cdots \sigma\Big{(}\bar{A}^{\prime}_{mm}XW^{(0)}\Big{)}W^{(1)}\Big{)}\cdots\Big{)}W ^{(L-1)}\end{bmatrix}  \tag{8}\]  
In Equation (5), due to the reorganization of the adjacency matrix \(A\) into the form \(\bar{A}+\Delta\), where the original graph is partitioned into \(m\) clusters and inter-cluster edges, during the training phase, it is only necessary to compute the cross-entropy loss on the nodes selected within the clusters. The loss function can be decomposed into:  
\[L_{\bar{A}^{\prime}}=\sum_{t}\frac{|V_{t}|}{N}L_{\bar{A}^{\prime}_{tt}} \tag{9}\]  
\[L_{\bar{A}^{\prime}_{tt}}=\frac{1}{|V_{t}|}\sum_{i\in V_{t}}loss\Big{(}y_{t},z ^{(L)}_{i}\Big{)} \tag{10}\]  
The method is then based on the decomposition form in (8)-(10). At each step, we sample a cluster \(V_{t}\) and perform stochastic gradient descent (SGD) to update the weights based on the gradient of the loss function. This process only requires the subgraph \(A_{tt}\), the \(X_{t}\), \(Y_{t}\) on the current batch, and the current model parameters \(\left\{W^{l}\right\}_{l=1}^{L}\). The implementation involves simple forward and backward propagation of matrix products, which is easier to implement compared to the neighborhood search procedure used in previous SGD-based training methods. Since each node in \(V_{t}\) is only connected to nodes within its own subgraph, there is no need for each node to perform a neighborhood search outside of its own subgraph. To avoid the potential impact on performance caused by the removal of certain links after graph partitioning and the issue of potential differences between the clustering distribution of METIS and the original dataset, we approximate the overall dataset distribution by using multiple random combinations. The approach is as follows:  
We begin by partitioning the graph into \(p\) clusters, denoted \(\left[V_{1},V_{2},\ldots,V_{p}\right]\), where \(p\) is relatively large. When creating a batch \(B\) for an SGD update, instead of considering a single cluster, we randomly select \(q\) clusters as a batch, represented as \(\left[t_{1},t_{2},\ldots,t_{q}\right]\), and include their nodes \(\left\{V_{t_{1}}\cup\cdots\cup V_{t_{q}}\right\}\) in the batch. Additionally, we reintroduce the links between the selected clusters to ensure connectivity.