# A Novel Algorithm for Local Network Alignment Based on Network Embedding
## 2 Related Work  
The study, definition and development of new methods for encoding structural information in order to improve graph analysis is a novel topic recently attracting researchers. Currently, many algorithms and many classification attempts have been described in surveys [11, 22, 25, 26, 27, 28, 29, 30]. These methods are usually referred to as _graph representation learning_ or _graph embedding_[22]. Here, we focus on node-based embeddings, i.e., on methods that build mappings between graph nodes and points in the embedding space so that geometric relationships among embedded objects reflect the structure of the original graph. As for the relevant literature, we follow the classification proposed by [PERSON] et al. [22], which presents an overview and a discussion of some related methods, in particular the preprocessing methods being used by the approach presented here to improve network embeddings and alignments. All of the embedding algorithms may be represented by using two functions: an encoder (\(Enc:\ V\to R^{d}\)), which maps each node to the embedding, and a decoder \(Dec\), which decodes structural information about the graph from the embeddings. It is possible to define a similarity among nodes of the \(G\) graph, and a loss function that measures the difference (i.e., the loss) of similarity of two original nodes and their embeddings \(l(v_{i},v_{j}),(emb_{v_{i}},emb_{v_{j}})\). The simplest similarity function is the adjacency matrix, according to which similarity equals 1 for adjacent nodes and 0 otherwise. A common similarity function among node embeddings is the dot product (i.e., the cosine angle) between the embedding vectors. Embedding algorithms are usually based on the minimization of the loss function \(l\) in the embedding space (see Section 1). Embedding approaches can also be also based on _shallow embedding_, which consists of encoding each node of the graph into a  
Figure 2: Workflow of the proposed approach. single vector through the use of a simple encoding function. The main objective is always to map nodes into embedding space. Methods differ in the use of different loss functions and similarity measures. Some representative methods are GraRep [31] and Hope [32]. One main drawback of these methods is that the similarity measure considered only takes into account the presence of edges of nodes, since they only consider nodes in the first-order neighborhood. Conversely, two nodes can be structurally similar even when they are far from each other in the network. Moreover, the encoding must be entirely recalculated when new nodes or edges are deleted or inserted. Consequently, a set of methods to investigate higher-order neighborhoods has been introduced. The higher-order neighborhood of each node is usually explored through Random Walks, which are short random paths that consist of a succession of random steps over the network. The key idea is to derive the similarity between two nodes on the basis of the co-occurrence of nodes in the respective random walks, by observing that two similar nodes have a greater chance to have similar random walks. As reported in [22], the literature reports many strategies that differ on the strategy used to calculate similarity, e.g., the way to simulate random walks. Thus, each method depends on the adopted random walk strategy. e.g., **DeepWalk** employs an unbiased random walk of fixed-length starting from each node [33]. **Node2 Vec**, instead, uses random walks of different lengths, defined as biased random walks [34]. **struct2 vec** employs biased random walks generated and propagated in a modified version of the network, in which nodes are structurally similar to the original network and close to the starting node. **LINE**[35] combines first- and second-order proximity to take into account both the local and the global network structures. First-order proximity is evaluated by considering the pairwise proximity between pair of nodes, while second-order proximity is evaluated on the basis of the neighbors of the nodes.