Graph embedding methods are effective techniques for representing nodes and their relations in a continuous space. Several studies try to embed graphs in constant curvature manifolds such as Euclidean, hyperbolic, and spherical space. It is critical how to select the best space for the graph embedding, as well as its dimensionality. In this study, we focus on the aforementioned constant curvature manifolds and aim at the dimensionality and curvature selection from the viewpoint of statistical model selection for latent variable models. Thereafter, we introduce universal latent variables models using wrapped normal distributions, which are the extension of Gaussian distribution for Riemannian manifolds. We then propose a novel methodology using decomposed normalized maximum likelihood code-length, which is based on the minimum description length principle. We empirically demonstrated the effectiveness of our method using both artificial and real-world datasets.

Abstract Graph embedding methods are effective techniques for representing nodes and their relations in a continuous space. Specifically, the hyperbolic space is more effective than the Euclidean space for embedding graphs with tree-like structures. Thus, it is critical how to select the best dimensionality for the hyperbolic space in which a graph is embedded. This is because we cannot distinguish nodes well with dimensionality that is considerably low, whereas the embedded relations are affected by irregularities in data with excessively high dimensionality. We consider this problem from the viewpoint of statistical model selection for latent variable models. Thereafter, we propose a novel methodology for dimensionality selection based on the minimum description length principle. We aim to introduce a latent variable modeling of hyperbolic embeddings and apply the decomposed normalized maximum likelihood code-length to latent variable model selection. We empirically demonstrated the effectiveness of our method using both synthetic and real-world datasets.

Graph embedding methods are effective techniques for representing nodes and their relations in a continuous space. Specifically, hyperbolic space is more effective for embedding graphs with tree-like structures than Euclidean one. Then it is critical how to select the best dimensionality of the hyperbolic space where a graph is embedded. This is because we cannot distinguish nodes well with too low a dimensionality, whereas the embedded relations are affected by irregularities of data with too high a dimensionality. We consider this problem from the view of statistical model selection for latent variable models. We then propose a novel methodology for dimensionality selection on the basis of the minimum description length principle. The key idea is to make the latent variable model of hyperbolic embeddings and to employ the decomposed normalized maximum likelihood code-length as an evaluation criterion. We empirically demonstrate the effectiveness of our method through synthetic and real datasets.