Streaming Graph Embeddings via Incremental Neighborhood Sketching

Dingqi Yang, Bingqing Qu, Jie Yang, Liang Wang, Philipe Cudre-Mauroux

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
25 Downloads (Pure)

Abstract

Graph embeddings have become a key paradigm to learn node representations and facilitate downstream graph analysis tasks. Many real-world scenarios such as online social networks and communication networks involve streaming graphs, where edges connecting nodes are continuously received in a streaming manner, making the underlying graph structures evolve over time. Such a streaming graph raises great challenges for graph embedding techniques not only in capturing the structural dynamics of the graph, but also in efficiently accommodating high-speed edge streams. Against this background, we propose SGSketch, a highly-efficient streaming graph embedding technique via incremental neighborhood sketching. SGSketch cannot only generate high-quality node embeddings from a streaming graph by gradually forgetting outdated streaming edges, but also efficiently update the generated node embeddings via an incremental embedding updating mechanism. Our extensive evaluation compares SGSketch against a sizable collection of state-of-the-art techniques using both synthetic and real-world streaming graphs. The results show that SGSketch achieves superior performance on different graph analysis tasks, showing 31.9% and 21.9% improvement on average over the best-performing static and dynamic graph embedding baselines, respectively. Moreover, SGSketch is significantly more efficient in both embedding learning and incremental embedding updating processes, showing 54x-1813x and 118x-1955x speedup over the baseline techniques, respectively.

Original languageEnglish
Pages (from-to)5296-5310
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume35
Issue number5
DOIs
Publication statusPublished - 2022

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • Approximation error
  • Communication networks
  • Computational modeling
  • Concept drift
  • Consistent weighted sampling
  • Data sketching
  • Dynamic graph embedding
  • Faces
  • Graph neural networks
  • Social networking (online)
  • Streaming graph
  • Task analysis

Fingerprint

Dive into the research topics of 'Streaming Graph Embeddings via Incremental Neighborhood Sketching'. Together they form a unique fingerprint.

Cite this