Understanding Graph Embedding Methods and Their Applications

Research output: Contribution to journalArticlepeer-review

69 Scopus citations

Abstract

Graph analytics can lead to better quantitative understanding and control of complex networks, but traditional methods suffer from the high computational cost and excessive memory requirements associated with the high-dimensionality and heterogeneous characteristics of industrial size networks. Graph embedding techniques can be effective in converting high-dimensional sparse graphs into low-dimensional, dense, and continuous vector spaces, preserving maximally the graph structure properties. Another type of emerging graph embedding employs Gaussian distribution-based graph embedding with important uncertainty estimation. The main goal of graph embedding methods is to pack every node's properties into a vector with a smaller dimension; hence, node similarity in the original complex irregular spaces can be easily quantified in the embedded vector spaces using standard metrics. The nonlinear and highly informative graph embeddings generated in the latent space can be conveniently used to address different downstream graph analytics tasks (e.g., node classification, link prediction, community detection, visualization, etc.). In this review, we present some fundamental concepts in graph analytics and graph embedding methods, focusing in particular on random walk-based and neural network-based methods. We also discuss the emerging deep learning-based dynamic graph embedding methods. We highlight the distinct advantages of graph embedding methods in four diverse applications, and we present implementation details and references to open-source software as well as available databases in the supplementary material to help interested readers start their exploration into graph analytics.

Original languageEnglish (US)
Pages (from-to)825-853
Number of pages29
JournalSIAM Review
Volume63
Issue number4
DOIs
StatePublished - 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Mathematics
  • Applied Mathematics

Keywords

  • deep neural networks
  • graph embedding at scale
  • high-dimensionality
  • intrinsic dimension
  • latent space
  • similarity
  • uncertainty quantification

Fingerprint

Dive into the research topics of 'Understanding Graph Embedding Methods and Their Applications'. Together they form a unique fingerprint.

Cite this