## 3 Graph Embedding Methods  
In this section, we briefly describe the concept of graph embedding and explain some of the state-of-the-art graph embedding methods (in short, embedding methods) in the literature; their corresponding objective functions are represented in Appendix A.2, in detail. For a given graph \(G=(V,E)\), graph embedding aims to learn a function \(f:V\to R^{d}\) that maps each node \(v\) in the graph into a vector in the \(d\)-dimensional space where \(d\ll|V|\)[23; 24; 25; 29]. The embedding methods exploit the graph structure to represent nodes as a low-dimensional vectors that _encode_ the neighborhood similarity, semantic information, and community structure among nodes in the graph [22; 23; 24; 25]. In the low-dimensional space, each dimension of the vectors can be interpreted as a _latent feature_[22; 23; 24; 26]. Figure 2a illustrates the Zachary's Karate graph [42] where the clusters found by modularity maximization are shown in different colors. We applied DeepWalk on this graph to obtain its two-dimensional representation, which is shown in Figure 2b; as an example, nodes 1 and 2 in the graph are represented as \(<\)-1.18, 1.15\(>\) and \(<\)-0.30, 1.10\(>\) vectors, respectively. As observed in the figure, there is a _commonality_ between clusters in the original graph and its representation since they encode the social relations and community structure in the graph. Therefore, in order to compute the similarity score of node-pair \((a,b)\) in a given graph, we can calculate the _proximity_ of the corresponding vector representations of \(a\) and \(b\), similar to the strategy observed in the word analogy detection [25; 38]. Figure 1: A sample graph and similarity scores of some node-pairs. **DeepWalk**[23]: inspired by the remarkable achievements in the representation learning for natural language processing such as Skip-gram [38], it exploits a stream of short random walks to extract information from a graph where these short random walks can be regarded as a _neighborhood_ for a target node \(v_{i}\) consisting of \(n\) nodes before and after \(v_{i}\) (i.e., window size \(W=2n\)). DeepWalk tries to learn a model to maximize the probability of any node appearing in the \(v_{i}\)'s neighborhood without the knowledge of its offset from \(v_{i}\). **Line**[25]: it considers the _first-order_ proximity (i.e., direct neighbors of a node) and the _second-order_ proximity to capture the nodes' neighborhoods; the second-order proximity follows the _sociology_ and _linguistics_ theories where two nodes sharing similar neighbors tend to be similar. These proximities are preserved by utilizing two distinct objective functions where two different models for them are trained _separately_ and their results are concatenated as the final result. **node2 vec**[26]: by following the _homophily_ and _structural equivalence_ hypotheses, it considers the community of a node and its structural roles in the graph, respectively, to capture the node neighborhood. node2 vec utilizes a _biased_ random walk controlled by two parameters \(p\) (return parameter) and \(q\) (in-out parameter). Suppose a random walk by using link \((u,v)\) in a graph; to decide the next walk from node \(v\), parameter \(p\) controls the probability of revisiting previous node in the walk (i.e., \(u\)) and parameter \(q\) controls the probability of visiting a node close to \(v\) or visiting a node that is far from \(v\). **graphGAN**[27]: it considers _two_ models, generator \(\mathbb{G}\) and discriminator \(\mathbb{D}\), involving in a _minimax_ game as follows. For a target node \(v\), the generator tries to generate relevant nodes to the \(v\)'s neighborhood (i.e., found by BFS search rooted in \(v\)) and produces fabricated samples to deceive the discriminator, while the discriminator tries to detect whether a node actually belongs to \(v\)'s neighborhood or it is fabricated by the generator. In graphGAN, the objective is to train two models as a two-play minimax game.