###### Abstract  
One of the important tasks in a graph is to compute the _similarity_ between two nodes; link-based similarity measures (in short, similarity measures) are well-known and conventional techniques for this task that exploit the relations between nodes (i.e., links) in the graph. Graph embedding methods (in short, embedding methods) convert nodes in a graph into vectors in a low-dimensional space by _preserving_ social relations among nodes in the original graph. Instead of applying a similarity measure to the graph to compute the similarity between nodes \(a\) and \(b\), we can consider the _proximity_ between corresponding vectors of \(a\) and \(b\) obtained by an embedding method as the similarity between \(a\) and \(b\). Although embedding methods have been analyzed in a wide range of machine learning tasks such as link prediction and node classification, they are _not_ investigated in terms of similarity computation of nodes. In this paper, we investigate _both_ effectiveness and efficiency of embedding methods in the task of similarity computation of nodes by comparing them with those of similarity measures. To the best of our knowledge, this is the first work that examines the application of embedding methods in this special task. Based on the results of our _extensive_ experiments with five well-known and publicly available datasets, we found the following observations for embedding methods: (1) with all datasets, they show _less_ effectiveness than similarity measures except for one dataset, (2) they _underperform_ similarity measures with all datasets in terms of efficiency except for one dataset, (3) they have more parameters than similarity measures, thereby leading to a _time-consuming_ parameter tuning process, (4) increasing the number of dimensions does _not_ necessarily improve their effectiveness in computing the similarity of nodes. graph embedding; feature representation learning; link-based similarity measures; node-pairs similarity +
Footnote †: journal: Applied  
1
Footnote 1: institutetext: _Applied_  
22 December 2020  
2020220202  
similar objects\"_[11]. In the literature, significant efforts have been devoted to improve the effectiveness of SimRank in similarity computation by proposing different variants such as SimRank++ [15], PSimRank [16], JacSim [1], JPRank [17], RoleSim [18], MatchSim [19], C-Rank [20], SimRank* [9], SimRank# [12], and PRank [21]. Among the aforementioned SimRank variants, JacSim, SimRank*, and JPRank are the state-of-the-art ones; JacSim solves the _pairwise normalization problem_[1, 16, 20], SimRank* solves the _level-wise computation problem_[9], and JPRank remedies both the pairwise normalization and _in-links consideration_ problems [17, 21] in the original SimRank. In addition, other variants such as GSimRank [14] and HowSim [8] have been proposed to compute the similarity of nodes in _heterogeneous_ graphs where nodes have different types and links represent different types of relationships among nodes (However, in this paper, we only focus on the homogeneous graphs where nodes and links have a single type such as a citation graph where nodes represent papers and links to the citation relationship among them). Graph embedding methods (in short, embedding methods), also known as feature representation learning methods, exploit the graph structure to represent each node in the graph as a _low-dimensional vector_ in which neighborhood similarity, semantic information, and community structure among nodes in the graph are captured [22, 23, 24, 25]. The obtained vector representations can be utilized by a wide range of tasks such as link prediction [22, 24, 26, 27, 28], node classification [22, 23, 25, 26, 27, 28, 29, 30], recommendations [27], word analogy detection [25], and document classification [25].