###### Abstract
Embedding methods, which are effective for extracting features from graph structured data, have broadly attracted significant attention in the literature and different embedding methods such as DeepWalk [23], Line [25], node2 vec [26], graphGAN [27], NetMF [29], ATP [24], BoostNE [30], DWNS [22], and NERD [28] have been proposed for homogeneous graphs. In addition, some embedding methods have been proposed that target the heterogeneous graphs such as HeGAN [31], RTN [32], and HAN [33]. Some methods such as SIDE [34], CSNE [35], and nSNE [36] perform feature representation learning in _signed_ graphs where there are two types of links (i.e., positive and negative) (In this paper, we focus only on the unsigned homogeneous graphs and the related embedding methods). All of the aforementioned embedding methods encode the social relations among nodes into vectors in a continuous low-dimensional space where each dimension in this space can be interpreted as a _latent feature_[22, 23, 24, 26]. In order to compute the similarity score of a pair of nodes in a given graph, we can apply Cosine [37] to their corresponding vector representations, similar to the strategy observed in the word analogy detection [25, 38]. In other words, a link-based similarity measure computes the similarity between nodes by _directly_ exploiting the graph structure, while an embedding method _converts_ a node in the graph into a vector representation composed of a set of latent features by exploiting the graph structure, then these latent features preserving the graph structure properties can be used to compute the similarity between nodes. Although a lot of efforts have been devoted to propose powerful embedding methods in the literature by analyzing them in a wide range of machine learning tasks, they are _not_ comprehensively analyzed in terms of similarity computation of nodes in graphs. In this paper, we investigate and analyze _both_ the effectiveness (i.e., accuracy) and efficiency (i.e., execution time) of embedding methods (i.e., DeepWalk, Line, node2 vec, graphGAN, NetMF, ATP, BoostNE, DWNS, and NERD) in similarity computation of nodes and compare them with those of similarity measures (i.e., SimRank, JacSim, JPRank, and SimRank*). To the best of our knowledge, this is the first work that examines the application of embedding methods in computing the similarity of nodes. We conduct extensive experiments with five _well-known_ and _publicly_ available datasets as BlogCatalog [23, 27, 29], Cora [39, 40], DBLP [1, 17, 41], TREC [1, 17], and Wikipedia [26, 27, 29], which are widely used in the literature. Our experimental results demonstrate that similarity measures are _better_ than embedding methods to compute the similarity of nodes; we found the following observations for embedding methods: (1) with all datasets, they show _less_ effectiveness than similarity measures except for the BlogCatalog dataset; however, they show less efficiency than similarity measures with this dataset, (2) they _underperform_ similarity measures with all datasets in terms of efficiency except for the Wikipedia dataset; however, with this dataset, they show less effectiveness than similarity measures, (3) they have more parameters than similarity measures, thereby leading to a _difficult_ and _time-consuming_ parameter tuning process, and (4) increasing the number of dimensions (i.e., latent features) does _not_ necessarily improve their effectiveness in computing the similarity of nodes. In addition, we observe that, among embedding methods, DeepWalk and its variants (i.e., Line and NetMF) show better effectiveness. The contributions of this paper are summarized as follows:  
* Although embedding methods have been analyzed in a wide range of machine learning tasks, they are _not_ investigated in terms of similarity computation of nodes. We investigate and analyze _both_ the effectiveness and efficiency of embedding methods in the task of similarity computation of nodes in graphs.