How Much Topological Structure Is Preserved by Graph Embeddings?

Xin Liu1, Chenyi Zhuang1, Tsuyoshi Murata2, Kyoung-Sook Kim1 and Natthawut Kertkeidkachorn1

  1. Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology
    AIST Waterfront ANNEX, 2-4-7 Aomi, Koto-ku, Tokyo 135-0064 Japan
    {xin.liu, zhuang.chenyi, ks.kim, n.kertkeidkachorn}@aist.go.jp
  2. Department of Computer Science, Tokyo Institute of Technology
    2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552 Japan
    murata@c.titech.ac.jp

Abstract

Graph embedding aims at learning representations of nodes in a low dimensional vector space. Good embeddings should preserve the graph topological structure. To study how much such structure can be preserved, we propose evaluation methods from four aspects: 1) How well the graph can be reconstructed based on the embeddings, 2) The divergence of the original link distribution and the embedding-derived distribution, 3) The consistency of communities discovered from the graph and embeddings, and 4) To what extent we can employ embeddings to facilitate link prediction. We find that it is insufficient to rely on the embeddings to reconstruct the original graph, to discover communities, and to predict links at a high precision. Thus, the embeddings by the state-of-the-art approaches can only preserve part of the topological structure.

Key words

graph embedding, network representation learning, graph reconstruction, dimension reduction, graph mining

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS123456789X

Publication information

Volume 16, Issue 2 (June 2019)
Year of Publication: 2019
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Liu, X., Zhuang, C., Murata, T., Kim, K., Kertkeidkachorn, N.: How Much Topological Structure Is Preserved by Graph Embeddings?. Computer Science and Information Systems, Vol. 16, No. 2, 597-614. (2019), https://doi.org/10.2298/CSIS123456789X