마수드/정창엽/조성운/오정석’s paper has been accepted in
Title: Simple is Better: A Simple yet Effective Graph Embedding Method Based on Similarity Computation and Learning-to-Rank
Author: Masoud Reyhani Hamedani, Chang Yeop Jung, Seong Un Cho, Jeong Seok Oh, Seong Soo Oh, and Sang Wook Kim
Abstract
We first identify four drawbacks of existing graph embedding methods. Inspired by them, we then propose LINOW, a recursive link-based similarity measure by utilizing nodes’ weights. Then, we provide a matrix form that dramatically accelerates LINOW’s computation, and two inherently parallelizable variants, LINOW-sn and LINOW-bn, to enhance LINOW’s scalability by computing similarity scores w.r.t. a single node and a batch of nodes, respectively. To improve its effectiveness, we propose LINOW* that considers both in- and out-neighbors in similarity computation, while preserving the link directions. Finally, we propose SIGEM, a self-supervised and contrastive-free graph embedding method that employs LINOW-bn to compute similarity scores of nodes, thereby ranking them. Then, it tries to preserve the ranks of nodes within their corresponding vectors in the embedding space. Moreover, we propose SIGEM* that employs LINOW* in the embedding process, while inheriting all the properties of SIGEM. The results of our extensive experiments demonstrate that (1) LINOW and LINOW* are beneficial to similarity-based graph embedding, (2) SIGEM consistently achieves the highest accuracy in both graph reconstruction and node classification tasks compared to other methods, while it outperforms them in most cases of the link prediction task, and (3) SIGEM* improves the effectiveness of SIGEM.