Novel Graph Embedding Methods based on Listwise Learning-To-Rank

Abstract

Nowadays, graphs are widely used to encode relational structures in many domains where nodes represent objects and links do their relationships in the domain. Graph embedding methods exploit the graph structure to map nodes in the graph into latent vectors in a low-dimensional embedding space where semantic information in the graph is preserved. The obtained latent vectors can be utilized by various downstream machine learning tasks. In this thesis, we focus on embedding methods that exploit only the topological information of the graph structure in the embedding process. This thesis contains two parts: in the first part, we discuss the similarity-based embedding methods that employ the similarity scores of nodes in the embedding process. Although it has been shown that similarity-based embedding methods are more effective than the conventional ones in graph embedding, we point out their three drawbacks as follows: inaccurate similarity computation, conflicting optimization goal, and impairing in/out-degree distributions. Motivated by these drawbacks, we propose GELTOR, an effective similarity-based embedding method that employs the concept of learning-to-rank in the embedding process. In the second part, we discuss the graph embedding methods to preserve the asymmetric information in directed graphs. Single-vector embedding methods (i.e., providing as a single latent vector per node in a directed graph) cannot well preserve the asymmetric information. To alleviate this problem double-vector embedding methods provide two latent vectors, source and target, per node. Although double-vector embedding methods are known to be superior to the single-vector ones, we point out their three drawbacks as inability to preserve asymmetry on NU-paths, inability to preserve global nodes similarity, and impairing in/out-degree distributions. We propose ELTRA, an effective double-vector embedding method to preserve asymmetric information in directed graphs.