# A Novel Algorithm for Local Network Alignment Based on Network Embedding
## 1 Introduction  
Nowadays, networks are used to model and study several applications in many real scenarios. In molecular biology, networks are used to model associations among genes or proteins in a unified formalism known as Protein Interaction Networks (PINs) [1]. Networks are also used to model association among drugs and diseases, to model protein structures [2, 3, 4, 5, 6, 7, 8, 9], or to study multilayer applications [10]. In social sciences, network-based models are used to represent relations among users of social networks [11, 12]. It has been demonstrated that valuable information can be obtained by analyzing single networks as well as by comparing two or more networks. Comparison between networks is also associated with Network Alignment (NA) algorithms [1, 13]. NA algorithms fall into two major classes: local (LNA, for Local Network Alignment) and global (GNA, for Global Network Alignment). LNA algorithms usually find (relatively small) regions of similarity between two or more networks and are also used to compare small regions extracted from two or more input networks. GNA algorithms aim to find a global mapping among nodes, discarding local regional similarity. It has been demonstrated that GNA algorithms are the best choice to transfer knowledge from a well-studied network to other networks [14], LNA algorithms usually perform well in finding corresponding substructures representing, for instance, protein complexes [2, 13, 15, 16, 17, 18]. In brain sciences, NA has been used to reconstruct connectomes from images without the use of any atlas [19, 20]. In this paper, we focus on LNA algorithms to study biological networks [1]. We also focus on embedding techniques to improve LNA. LNA uses as input two (or more) networks and a set of initial mapped nodes (known as _seed nodes_) to build the alignment. Such information is usually derived from biological considerations, which, in principle, may cause a circularity problem or bias [16, 19]. Consequently, many different works have tried to improve existing LNAalgorithms by using topological information as input [21]. The rationale behind these approaches is that topological information can quantify the structural similarity among nodes. Similarly, network embedding methods aim to encode structural information about networks. The latter methods are usually referred to as _graph embedding_ or _graph representation learning_[22]. The goal of each algorithm is to map each node of a given undirected and unweighted graph \(G=(V,E)\) into points of a low-dimensional vector space, i.e., into a vector \(z\in\mathbb{R}^{d}\) where \(d<|V|\), with \(d<n\), and \(n\) being the dimension of the graph adjacency matrix [22]. We are interested in node-based embeddings; thus, all these methods calculate a mapping among nodes and points of the embedding space so that geometric relationships among embedded objects reflect the structure of the original graph. For instance, Figure 1 represents an example of LNA and embedding. Let \(G(V,E)\) be a graph with \(\|E\|\) edges and \(\|V\|\) nodes. The desired behavior of an embedding algorithm is that, given two nodes \(v_{i}\in V\) and \(v_{j}\in V\) the similarity between the embeddings of \(v_{i}\) and \(v_{j}\) should reflect the similarity between the original nodes, i.e., minimizing loss \(l\), a measure to quantify the noise introduced by mapping nodes into a new space (e.g., two adjacent nodes are not necessarily mapped into close points in the new space, called latent (or embedding) space). More formally, given two nodes \(v_{i}\) and \(v_{j}\) in \(V\), let \(emb_{v_{i}}\) and \(emb_{v_{j}}\) be their embeddings and let \(l\) be the loss value between the similarity among nodes and their embeddings. Then, the embedding algorithm should be geared in such a way that its parameters will minimize the overall loss function \(\mathcal{L}=\sum_{v_{i},v_{j}\in V}l(v_{i},v_{j}),(emb_{v_{i}},emb_{v_{j}})\).