# Properties of Vector Embeddings in Social Networks
## 3 Related Work  
### Graph Embedding Techniques  
Recently, methods that use distributed representation learning techniques in an NLP domain, like the Skip-Gram algorithm, have gained attention from the research community. These NLP methods have been adapted to calculate graph embeddings that preserve first and second order proximities. For obtaining the embeddings, these methods create symbolic sequences comparable to natural language text by conducting random-walks over the graph. The methods yield lower time complexity compared to eigenvalue decomposition methods [26]. Moreover, they are able to map the nonlinear structure of the network into the embedding space. They are especially useful when one can either only partially observe the graph, or the graph is too large. In this section, we quickly review the different random-walk based embedding techniques:  
* **DeepWalk**[12]: This approach learns d-dimensional feature representations by simulating uniform random walks over the graph. It preserves higher-order proximities by maximizing the probability of observing the last \(c\) nodes and the next \(c\) nodes in the random walk centered at \(v_{i}\). More formally, DeepWalk maximizes: \[\log Pr(v_{i-c},\cdots,v_{i-1},v_{i+1},\cdots,v_{i+c}|Y_{i}),\] where \(Y_{i}\) is the embedding vector of the node \(v_{i}\) and \(c\) is the context size. We denote the mapping function for this method DeepWalk: \(V\rightarrow\mathbb{R}^{d}\), where \(d\) is the embedding size. Therefore, the DeepWalk embedding of the node \(v\) is denoted by DeepWalk\((v)\). * **node2 vec**[10]: Inspired by DeepWalk, node2 vec preserves higher-order proximities by maximizing the probability of occurrence of subsequent nodes in fixed length random walks. The crucial difference from DeepWalk is that node2 vec employs biased-random walks that provide a trade-off between BFS and DFS graph searches, and hence produces higher-quality and more informative embeddings than DeepWalk. More specifically, there are two key hyper-parameters \(p\in\mathbb{R}^{+}\) and \(q\in\mathbb{R}^{+}\) that control the random walk. Parameter \(p\) controls the likelihood of immediately revisiting a node in the walk. Parameter \(q\) controls the traverse behavior to approximate BFS or DFS. For \(p=q=1\), node2 vec is identical to DeepWalk. We denote the node2 vec embedding by node2 vec: \(V\rightarrow\mathbb{R}^{d}\), where \(d\) is the embedding size. Therefore, the node2 vec embedding of the node \(v\) is shown by node2 vec\((v)\). * **loc**[15]: This approach limits random walks to the neighborhood around egos to make artificial paragraphs. ParagraphVector [16] is properly applied to learn local embeddings for egos by optimizing the likelihood objective using stochastic gradient descent with negative sampling [27]. Formally, given an artificial paragraph \(v_{1},v_{2},v_{3},\ldots,v_{t},\ldots,v_{l}\) for ego \(u_{i}\), the goal is to update representations in order to maximize the average log probability: \[\sum_{t=1}^{l}\log Pr(u_{i},v_{t+c},\ldots,v_{t-c}|Y_{i}),\] where \(Y_{i}\) is the embedding vector of the ego \(u_{i}\), \(l\) is the length of the artificial paragraph, and \(c\) is the context size. Therefore, there is a mapping function \(\mathrm{loc}\colon U\rightarrow\mathbb{R}^{d}\), where \(d\) is the embedding size. We denote the \(\mathrm{loc}\) embedding of the ego \(u\) by \(\mathrm{loc}(u)\). * **LINE**[14]: It learns two embedding vectors for each node by preserving the first-order and second-order proximity of the network in two phases. In the first phase, it learns \(d/2\) dimensions by BFS-style simulations over immediate neighbors of nodes. In the second phase, it learns the next \(d/2\) dimensions by sampling nodes strictly at a 2-hop distance from the source nodes. Then, the embedding vectors are concatenated as the final representation for a node. Indeed, LINE defines two joint probability distributions for each pair of nodes, one using adjacency matrix and the other using the embedding.