## 4 Experimental Evaluation
### Graph Embedding Methods  
For embedding methods, the execution time is regarded as the _summation_ of a _learning time_ (i.e., elapsed time to construct low-dimensional representation vectors) and a _similarity computation time_ (i.e., elapsed time to compute the similarity scores of all pairs of representation vectors by employing Cosine). With each dataset, the learning time of an embedding method is regarded as the _average_ run time over the five executions of the method. We implemented Cosine based on a matrix/vector multiplication technique, which is significantly (i.e., almost 30 times) faster than its conventional implementation. In the case of similarity computation time, we consider only the elapsed time to compute the similarity scores by applying Cosine; the required time to store the results in a file or a database is not considered as we did for similarity measures. Table 16 represents the learning time (minutes) of all embedding methods for different values of \(d\) with all datasets where _bold face_ numbers indicate the best efficiency with each value of \(d\) in a dataset. As observed in the table, NetMF shows the _best_ efficiency among _all_ embedding methods with the BlogCatalog and Wikipedia datasets _regardless_ of the value of \(d\), node2 vec shows the _best_ efficiency among all methods with Cora, DBLP, and TREC datasets _regardless_ of the value of \(d\), BoostNE, and ATP almost have better efficiency after NetMF and node2 vec with all datasets, and graphGAN shows the _worst_ efficiency among all embedding methods with all datasets regardless of the value of \(d\). Table 17 shows the similarity computation time (minutes) based on different vector sizes (i.e., \(d=64,128,256,512\)) with our five datasets. Note that the similarity computation time for a dataset depends on the _number of node-pairs_ and the representation vector's _size_ (i.e., the value of \(d\)); for example, with the BlogCatalog dataset, the required time to compute Cosine for all node-pairs with vector size 64 obtained by _any_ embedding methods (except APT and NERD) is 4.07. In the case of ATP and NERD with any value of \(d\), the similarity computation time in Table 17 is multiplied by _two_ since these methods construct two vectors for each node (i.e., target and source vectors) where we apply Cosine to the corresponding target vectors and source vectors of a node-pair separately; finally, the highest score is regarded as the final similarity score of the node-pair. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **JacSim** & **JPRank** & **SimRank\({}^{\star}\)** & **SimRank** \\ \hline BlogCatalog & 457.24 & - & 2.02 & 4.38 \\ Cora & 3.54 & 8.22 & 0.21 & 0.32 \\ DBLP & 3.85 & 8.41 & 0.51 & 0.70 \\ TREC & 39.80 & 91.17 & 1.45 & 5.10 \\ Wikipedia & 55.29 & - & 0.28 & 0.53 \\ \hline \hline \end{tabular}
\end{table} 
Table 15: Execution time (minutes) of all similarity measures with our datasets. In order to easily compare the efficiency of all embedding methods at a glance, Figure 11 illustrates their execution times (i.e., the summation of the learning time and the similarity computation time) with all datasets; we excluded graphGAN since its execution time value is quite larger than other embedding methods. For example, with the BlogCatalog dataset when \(d=64\), the execution time of ATP is \(11.83\) as the summation of \(3.69\) (i.e., the learning time from Table 16) and \(2\ \times\ 4.07\) (As explained before, for _simplicity_, we regard the similarity computation time as twice that in Table 17; for ATP with BlogCatalog when \(d=64\) the _real_ Cosine calculation time is \(8.33\) (\(\simeq 2\times 4.07\)).) (i.e., twice the similarity computation time from Table 17); in addition, the execution time by DeepWalk is \(45.32\) as the summation of \(41.25\) (i.e., the learning time) and \(4.07\) (i.e., the similarity computation time).