Dynamic Node Embeddings From Edge Streams
- 24 August 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Emerging Topics in Computational Intelligence
- Vol. PP (6) , 1-16
Abstract
Networks evolve continuously over time with the addition, deletion, and changing of links and nodes. Such temporal networks (or edge streams) consist of a sequence of timestamped edges and are seemingly ubiquitous. Despite the importance of accurately modeling the temporal information, most embedding methods ignore it entirely or approximate the temporal network using a sequence of static snapshot graphs. In this work, we propose using the notion of temporal walks for learning dynamic embeddings from temporal networks. Temporal walks capture the temporally valid interactions (e.g., flow of information, spread of disease) in the dynamic network in a lossless fashion. Based on the notion of temporal walks, we describe a general class of embeddings called continuous-time dynamic network embeddings (CTDNEs) that completely avoid the issues and problems that arise when approximating the temporal network as a sequence of static snapshot graphs. Unlike previous work, CTDNEs learn dynamic node embeddings directly from the temporal network at the finest temporal granularity and thus use only temporally valid information. As such CTDNEs naturally support online learning of the node embeddings in a streaming real-time fashion. Finally, the experiments demonstrate the effectiveness of this class of embedding methods that leverage temporal walks as it achieves an average gain in AUC of $11.9\%$ across all methods and graphs.
Keywords
All Related Versions
This publication has 67 references indexed in Scilit:
- Temporal networksPhysics Reports, 2012
- Temporal Link Prediction Using Matrix and Tensor FactorizationsACM Transactions on Knowledge Discovery From Data, 2011
- Spread of (mis)information in social networksGames and Economic Behavior, 2010
- Link prediction based on local random walkEurophysics Letters, 2010
- Random walks and local cuts in graphsLinear Algebra and its Applications, 2007
- Online Gradient Descent Learning AlgorithmsFoundations of Computational Mathematics, 2007
- Prediction and ranking algorithms for event-based network dataACM SIGKDD Explorations Newsletter, 2005
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKSInternational Journal of Foundations of Computer Science, 2003
- Temporal shortest paths: Parallel computing implementationsParallel Computing, 2001