# Distributed Detection of Large-Scale Internet of Things Botnets Based on Graph Partitioning
## 4 Proposed Method
### Feature Learning  
Define the communication graph of the botnet as \(G=(V,A)\), where \(V\) is a set consisting of \(n\) nodes \(\{v_{1},v_{2},\ldots,v_{n}\}\). The adjacency matrix of the graph \(G\) is denoted by \(A\in\mathbb{R}^{n\times n}\), which is typically symmetric. In the matrix \(A\in\mathbb{R}^{n\times n}\), \(a_{ij}=1\) represents the edge between nodes \(v_{i}\) and \(v_{j}\), indicating direct communication between nodes \(v_{i}\) and \(v_{j}\), while a value of 0 indicates no direct communication. The node degree matrix is represented by \(D=diag(d_{1},d_{2},\ldots,d_{n})\), where \(d_{i}=\sum_{j=1}^{n}a_{ij}\). It is important to note that \(A\) and \(DS\) represent the fixed graph structure throughout the entire learning process. We utilize the Cluster-GCN model [18] to learn the topology of the botnet network and the preprocessing technique to modify the embedding representations of nodes and perform end-to-end detection. The working principle of Cluster-GCN is as follows: we first use the METIS algorithm to process the large graph and partition it into a specified number of dense subgraphs. Then, we sample the node blocks that are related to the subgraph and restrict the neighborhood search within that subgraph. This simple and effective strategy significantly improves memory and computational efficiency while achieving comparable testing accuracy to previous algorithms. To address the issue of low computational performance of IoT devices, we adopted a random multiple clustering approach proposed by Cluster-GCN to merge inter-cluster edges and reduce discrepancies between batches. Initially, we partitioned the graph into \(c\) clusters \(\mathcal{V}_{1},\mathcal{V}_{2},\ldots,\mathcal{V}_{c}\), where \(c\) takes a relatively large value. When constructing batches \(B\) for SGD updates, instead of using just one cluster, we randomly selected \(q\) clusters,  
Figure 5: Overview of our method. denoted as \(t_{1},\ldots,t_{q}\), and included their nodes \(\{\mathcal{V}_{t_{1}}\cup\cdots\cup\mathcal{V}_{t_{q}}\}\) in the batch. Additionally, the edges between the selected clusters \(\{A_{ij}|i,j\in t_{1},\ldots,t_{q}\}\) were also reintroduced. This recombination of edges between clusters minimized differences between batches. Experimental results demonstrated that using multiple clusters as a batch improved convergence. The final Cluster-GCN algorithm is presented in Algorithm 1. ```
1:Input: Graph A, feature X, label Y
2:Output: Node representation \(\bar{X}\)
3:Partition graph nodes \(\mathcal{V}\) into \(c\) clusters \(\{\mathcal{V}_{1},\mathcal{V}_{2},\ldots,\mathcal{V}_{m}\}\) by METIS, such that \(|\mathcal{V}_{i}|=k\) for \(i=1,2,\ldots,c\)
4:for each epoch \(t=1,2,\ldots,T\)do
5: Randomly choose \(q\) clusters, \(t_{1},t_{2},\ldots,t_{q}\) from \(V\) without replacement;
6: Form the subgraph \(\bar{G}\) with nodes \(\bar{\mathcal{V}}=[V_{t_{1}},V_{t_{2}},\ldots,V_{t_{q}}]\) and links \(A_{\bar{\mathcal{V}},\bar{\mathcal{V}}}\);
7: Compute \(g\leftarrow\
abla\mathcal{L}_{A_{\mathcal{V},\bar{\mathcal{V}}}}\) (loss on the subgraph \(A_{\bar{\mathcal{V}},\bar{\mathcal{V}}}\));
8: Conduct Adam update using gradient estimator \(g\)
9:endfor
10:Output \(\{W_{t}\}_{t=1}^{L}\)
```  
**Algorithm 1** Cluster-GCN  
In our approach, we utilize the METIS algorithm to partition n nodes into m groups, \(V=[V_{1},V_{2},\ldots,V_{m}]\). Let \(V_{i}\) represent the nodes in the i-th group. Based on this, we obtain m subgraphs as follows:  
\[\widetilde{G}=[G_{1},G_{2},\ldots,G_{m}]=[\{V_{1},E_{1}\},\{V_{2},E_{2}\}, \ldots,\{V_{m},E_{m}\}] \tag{4}\]  
Each \(E_{i}\) only consists of the links between nodes in \(V_{i}\). Similarly, after reorganizing the nodes, the adjacency matrix is also partitioned into \(m^{2}\) sub-matrices:  
\[A=\overline{A}+\Delta= \begin{bmatrix}A_{11}&\cdots&A_{1m}\\ \vdots&\ddots&\vdots\\ A_{m1}&\cdots&A_{mm}\end{bmatrix}  \tag{5}\]  
and:  
\[\overline{A}= \begin{bmatrix}A_{11}&\cdots&0\\ \vdots&\ddots&\vdots\\ 0&\cdots&A_{mm}\end{bmatrix}  \tag{6}\]  
\[\Delta=