## 4 Graph-Based Classification with Human Engagement
### Graph Embedding  
Graph embedding converts nodes to latent vectors on the latent feature space according to its graph topology. Thereby, relative distances between the nodes in the graph are also reflected to the latent space. We employed two well-known graph embedding methods: DeepWalk [25] and large-scale information network embedding (LINE) [26]. DeepWalk performs multiple random walks, say \(K\), from each node to collect a set of \(K\) paths with sequences of nodes that has a predefined length (say \(L\)). Then, it learns the embeddings of the nodes by using the collected random walks as \"context\" data, based on the assumption that adjacent nodes are likely to have similar paths with similar embeddings. The objective function is:  
\[\max(\log Pr(\{v_{i-w},\ldots v_{i+w}\}\backslash v_{i}|\Phi(v_{i})), \tag{5}\]  
where \(Pr(|)\) shows the co-occurrence probability between malware around to target malware \(v_{i}\) within the window size of \(w\). Additionally, \(\Phi\) is a mapping function that sets the target malware to the latent space, eventually setting topologically similar malware in the shared latent space after the training.  
LINE is another embedding method based on edges rather than nodes, unlike DeepWalk. LINE uses two similarities for conversion: first order and second order. The first order proximity (\(O_{1}\)) between two nodes is computed through the weight of the edges linked to each other, while the second order proximity (\(O_{2}\)) uses similar neighbor nodes. LINE is then trained by concatenating these two proximities for each node. Each proximity objective function for edges \((i,j)\) between nodes \(v_{i}\) and \(v_{2}\) in the set of \(V\) nodes can be written as follows:  
\[p_{1}(v_{i},v_{j})=\frac{1}{1+\exp(-\vec{u}_{i}^{T}\cdot\vec{u}_{j})}, \tag{6}\]  
\[p_{2}(v_{j}|v_{i})=\frac{exp(-\vec{u}_{i}^{T}\cdot\vec{u}_{j})}{\sum_{k=1}^{|V |}\exp(-\vec{u}_{i}^{T}\cdot\vec{u}_{j})}, \tag{7}\]  
\[O_{1}=-\sum_{(i,j)\in E}w_{ij}\log p_{1}(v_{i},v_{j}), \tag{8}\]  
\[O_{2}=-\sum_{(i,j)\in E}w_{ij}\log p_{1}(v_{j}|v_{i}), \tag{9}\]  
where \(\vec{u}_{i}\in R^{z}\) is the \(z\)-dimensional vector of node \(v_{i}\). Further, \(p_{1}\) is the joint probability of node \(v_{j}\) in the space \(V\times V\), and \(p_{2}\) is a conditional distribution of \(v_{i}\) in the entire set of nodes. With \(w_{ij}\), which is the weight of the edge \((i,j)\), the embeddings (i.e., \(\{\vec{u}_{i}\}_{i=1\dots\{V\}}\)) can be obtained by optimizing the objective functions \(O_{1}\) and \(O_{2}\).  
Both DeepWalk and LINE can be used for embedding malware nodes, and we used DeepWalk for this task because it provided better results in our evaluation. With the embeddings, each malware is now converted to a feature vector, which is a proper format for classification, such as KNN classification. The KNN classifier labels the target sample by finding the majority of the top-k nearest neighbor labels. Our framework borrowed this classifier. In practice, we find the top-1 nearest neighbor for the target malware and then confirm the author group of the chosen neighbor as the target malware's author group. We also tried various \(k\) values, such as 2 or 3, but setting \(k\) as 1 provided the best results.