DynG2G: An Efficient Stochastic Graph Embedding Method for Temporal Graphs

Abstract

Dynamic graph embedding has gained great attention recently due to its capability of learning low-dimensional and meaningful graph representations for complex temporal graphs with high accuracy. However, recent advances mostly focus on learning node embeddings as deterministic "vectors" for static graphs, hence disregarding the key graph temporal dynamics and the evolving uncertainties associated with node embedding in the latent space. In this work, we propose an efficient stochastic dynamic graph embedding method (DynG2G) that applies an inductive feedforward encoder trained with node triplet energy-based ranking loss. Every node per timestamp is encoded as a time-dependent probabilistic multivariate Gaussian distribution in the latent space, and, hence, we are able to quantify the node embedding uncertainty on-the-fly. We have considered eight different benchmarks that represent diversity in size (from 96 nodes to 87 626 and from 13 398 edges to 4 870 863) as well as diversity in dynamics, from slowly changing temporal evolution to rapidly varying multirate dynamics. We demonstrate through extensive experiments based on these eight dynamic graph benchmarks that DynG2G achieves new state-of-the-art performance in capturing the underlying temporal node embeddings. We also demonstrate that DynG2G can simultaneously predict the evolving node embedding uncertainty, which plays a crucial role in quantifying the intrinsic dimensionality of the dynamical system over time. In particular, we obtain a "universal" relation of the optimal embedding dimension, L_o , versus the effective dimensionality of uncertainty, D_u , and infer that L_o=D_u for all cases. This, in turn, implies that the uncertainty quantification approach we employ in the DynG2G algorithm correctly captures the intrinsic dimensionality of the dynamics of such evolving graphs despite the diverse nature and composition of the graphs at each timestamp. In addition, this L₀ - D_u correlation provides a clear path to selecting adaptively the optimum embedding size at each timestamp by setting L ≥ D_u .