Streaming Graph Embeddings via Incremental Neighborhood Sketching

Streaming Graph Embeddings via Incremental Neighborhood Sketching

Yang, Dingqi (University of Macau)
Qu, Bingqing (United International College)
Yang, J. (TU Delft Web Information Systems)
Wang, Liang (Northwestern Polytechnical University)
Cudre-Mauroux, Philipe (University of Fribourg)

2022

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.

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

http://resolver.tudelft.nl/uuid:525da5ef-29bb-4982-91c3-397fc50bbcf5

https://doi.org/10.1109/TKDE.2022.3149999

2023-05-01

1041-4347

IEEE Transactions on Knowledge & Data Engineering, 35 (5), 5296-5310

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.

Institutional Repository

journal article

© 2022 Dingqi Yang, Bingqing Qu, J. Yang, Liang Wang, Philipe Cudre-Mauroux