Time-capturing Dynamic Graph Embedding for Temporal Linkage Evolution

Yu Yang, Jiannong Cao, Milos Stojmenovic, Senzhang Wang, Yiran Cheng, Chun Lum, Zhetao Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Dynamic graph embedding learns representation vectors for vertices and edges in a graph that evolves over time. We aim to capture and embed the evolution of vertices' temporal connectivity. Existing work studies the vertices' dynamic connection changes but neglects the time it takes for edges to evolve, failing to embed temporal linkage information into the evolution of the graph. To capture vertices' temporal linkage evolution, we model dynamic graphs as a sequence of snapshot graphs, appending the respective timespans of edges (ToE). We co-train a linear regressor to embed ToE while inferring a common latent space for all snapshot graphs by a matrix-factorization-based model to embed vertices' dynamic connection changes. Vertices' temporal linkage evolution is captured as their moving trajectories within the common latent representation space. Our embedding algorithm converges quickly with our proposed training methods, which is very time efficient and scalable. Extensive evaluations on several datasets show that our model can achieve significant performance improvements, i.e. 22.98% on average across all datasets, over the state-of-the-art baselines in the tasks of vertex classification, static and time-aware link prediction, and ToE prediction
Original languageEnglish
Pages (from-to)1-14
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Publication statusPublished - Jun 2021

Keywords

  • Dynamic graph embedding
  • Graph evolution
  • Edge timespan
  • Graph mining
  • Heuristic algorithms
  • Couplings
  • Evolution (biology)
  • Prediction algorithms
  • Trajectory
  • Task analysis
  • Social networking (online)

Cite this