Time-varying Graph Representation Learning via Higher-Order Skip-Gram with Negative Sampling
This work addresses the challenge of modeling dynamic networks for applications such as social interaction analysis and epidemic forecasting, representing an incremental improvement over existing graph representation techniques.
The paper tackles the problem of learning representations for time-varying graphs by extending skip-gram embedding to perform implicit tensor factorization, resulting in a method that outperforms state-of-the-art approaches in tasks like network reconstruction and disease spreading prediction.
Representation learning models for graphs are a successful family of techniques that project nodes into feature spaces that can be exploited by other machine learning algorithms. Since many real-world networks are inherently dynamic, with interactions among nodes changing over time, these techniques can be defined both for static and for time-varying graphs. Here, we build upon the fact that the skip-gram embedding approach implicitly performs a matrix factorization, and we extend it to perform implicit tensor factorization on different tensor representations of time-varying graphs. We show that higher-order skip-gram with negative sampling (HOSGNS) is able to disentangle the role of nodes and time, with a small fraction of the number of parameters needed by other approaches. We empirically evaluate our approach using time-resolved face-to-face proximity data, showing that the learned time-varying graph representations outperform state-of-the-art methods when used to solve downstream tasks such as network reconstruction, and to predict the outcome of dynamical processes such as disease spreading. The source code and data are publicly available at https://github.com/simonepiaggesi/hosgns.