In the literature, various graph embedding methods have been proposed. Although they have pioneered notable techniques in the field, we point out their four drawbacks as follows: (1) inability to consider global graph structure(2) undermining learning quality(3) impairing in/out-degree distributions in directed graphs, and (4) limited applicability. Inspired by these drawbacks, we first propose LINOW, a recursive LI nk-based similarity measure for graphs by utilizing NO des' Weights, which is applicable to both directed and undirected graphs. Then, we provide a matrix form that dramatically accelerates LINOW's computation without approximation. Furthermore, to enhance its scalability, we provide two variants, LINOW-sn and LINOW-bn, to compute similarity scores w.r.t. a single node and a batch of nodes, respectively. Finally, we propose SIGEM, a simple yet effective self-supervised and contrastive-free SI milarity based Graph EM bedding method that employs LINOW-bn to compute similarity scores of nodes in the graph, thereby ranking them. Then, it tries to preserve the original ranks of nodes in the graph within their corresponding vectors in the embedding space, by employing a single-layer neural network. The results of our extensive experiments with eight real-world datasets and thirteen state-of-the-art and conventional embedding methods demonstrate that (1) LINOW-sn and LINOW-bn successfully improve the scalability of naive LINOW(2) LINOW is beneficial to similarity based graph embedding, and (3) SIGEM consistently achieves the highest accuracy in both graph reconstruction and node classification tasks compared to other methods, while it significantly outperforms them in most cases of the link prediction task.

Double-vector embedding methods capture the asymmetric information in directed graphs first, and then preserve them in the embedding space by providingtwo latent vectors, i.e., source and target, per node. Although these methods are known to besuperior to the single-vector ones (i.e., providing asingle latent vector per node), wepoint out their three drawbacks as inability to preserve asymmetry on NU-paths, inability to preserve global nodes similarity, and impairing in/out-degree distributions. To address these, we first proposeCRW, anovel similarity measure for graphs that considers contributions ofboth in-links and out-links in similarity computation,without ignoring their directions. Then, we proposeELTRA, aneffective double-vector embedding method to preserve asymmetric information in directed graphs. ELTRA computesasymmetry preserving proximity scores (AP-scores) by employing CRW in which the contribution of out-links and in-links in similarity computation isupgraded anddowngraded, respectively. Then, for every node u, ELTRA selects its top-tclosest nodes based on AP-scores andconforms theranks of their corresponding target vectors w.r.t u's source vector in the embedding space to theiroriginal ranks. Our extensive experimental results withseven real-world datasets andsixteen embedding methods show that (1) CRWsignificantly outperforms Katz and RWR in computing nodes similarity in graphs, (2) ELTRAoutperforms the existing state-of-the-art methods in graph reconstruction, link prediction, and node classification tasks.

Similarity-based embedding methods have introduced a new perspective on graph embedding by conforming the similarity distribution of latent vectors in the embedding space to that of nodes in the graph; they show significant effectiveness over conventional embedding methods in various machine learning tasks. In this paper, we first point out the three drawbacks of existing similarity-based embedding methods: inaccurate similarity computation, conflicting optimization goal, and impairing in/out-degree distributions. Then, motivated by these drawbacks, we propose AdaSim*, a novel similarity measure for graphs that is conducive to the similarity-based graph embedding. We finally propose GELTOR, an effective embedding method that employs AdaSim* as a node similarity measure and the concept of learning-to-rank in the embedding process. Contrary to existing methods, GELTOR does not learn the similarity scores distribution; instead, for any target node, GELTOR conforms the ranks of its top-t similar nodes in the embedding space to their original ranks based on AdaSim* scores. We conduct extensive experiments with six real-world datasets to evaluate the effectiveness of GELTOR in graph reconstruction, link prediction, and node classification tasks. Our experimental results show that (1) AdaSim* outperforms AdaSim, RWR, and MCT in computing nodes similarity in graphs, (2) our GETLOR outperforms existing state-of-the-arts and conventional embedding methods in most cases of the above machine learning tasks, thereby implying that learning-to-rank is beneficial to graph embedding.

In the literature, various link-based similarity measures such as Adamic/Adar (in short Ada), SimRank, and random walk with restart (RWR) have been proposed. Contrary to SimRank and RWR, Ada is a non-recursive measure, which exploits the local graph structure in similarity computation. Motivated by Ada's promising results in various graph-related tasks, along with the fact that SimRank is a recursive generalization of the co -citation measure, in this paper, we propose AdaSim, a recursive similarity measure based on the Ada philosophy. Our AdaSim provides identical accuracy to that of Ada on the first iteration and it is applicable to both directed and undirected graphs. To accelerate our iterative form, we also propose a matrix form that is dramatically faster while providing the exact AdaSim scores. We conduct extensive experiments with five real-world datasets to evaluate both the effectiveness and efficiency of our AdaSim in comparison with those of existing similarity measures and graph embedding methods in the task of similarity computation of nodes. Our experimental results show that 1) AdaSim significantly improves the effectiveness of Ada and outperforms other competitors, 2) its efficiency is comparable to that of SimRank* while being better than the others, 3) AdaSim is not sensitive to the parameter tuning, and 4) similarity measures are better than embedding methods to compute similarity of nodes.

Android application (app) stores contain ahugenumber of apps, which aremanuallyclassified based on the apps’ descriptions into various categories. However, the predefined categories or apps descriptions are usuallynotvery accurate to reflect the real functionalities of apps, thereby leading tomisclassifythe apps, which may cause serioussecurity issuesandunreliabilityproblem in the app store. Therefore, the automatic app classification is animportantdemand to construct asecure,reliable,integrated, andeasy to navigateapp store. In this paper, we propose an effective method calledAndroClasstoautomaticallyclassify apps based on theirrealfunctionalities by usingrichandcomprehensivefeatures representing theactualfunctionalities of the apps. AndroClass performsthreesteps offeature extraction,feature refinement, andclassification. In the feature extraction step, we extract 14 various features for each app by utilizing aunified tool suite. In the feature refinement step, we applyRandom Forestalgorithm to refine the features. In the classification step, we combine refined features into asingleone and AndroClass is equipped with K‐Nearest Neighbor, Naive Bayes, Support Vector Machine, and Deep Neural Network to classify apps. On the contrary to the existing methods, all the utilized features in AndroClass arestableandclearlyrepresent the actual functionalities of the app, AndroClass doesnotpose any issues to theuser privacy, and our method can be applied to classifyunreleasedornewly releasedapps. The results ofextensiveexperiments with tworeal-worlddatasets and a dataset constructed byhuman expertsdemonstrate the effectiveness of AndroClass where the classification accuracy of AndroClass with the latter dataset is 83.5%.

In this paper, we propose SimCC-AT (similarity based on content and citations with automatic parameter tuning) to compute the similarity of scientific papers. As in SimCC, the state-of-the-art method, we exploit a notion of a contribution score in similarity computation. SimCC-AT utilizes an automatic weighting scheme based on SVMrank and thus requires only a smaller number of experiments for parameter tuning than SimCC. Furthermore, our experimental results with a real-world dataset show that the accuracy of SimCC-AT is dramatically higher than that of other existing methods and is comparable to that of SimCC.

In computing the similarity of scientific papers, previous text-based and link-based similarity measures look at only a single side of the content and citations. In this paper, we propose a novel approach called SimCC that effectively combines the content and citation information to accurately compute the similarity of scientific papers. Unlike previous approaches, SimCC effectively represents both authority and context of a scientific paper simultaneously in computing similarities. Also, we propose SimCC+A to consider recently-published papers. The effectiveness of our proposed method is demonstrated via extensive experiments on a real-world dataset of scientific papers, with more than 100% improvement in accuracy compared with previous methods.