DynG2G: An Efficient Stochastic Graph Embedding Method for Temporal Graphs.

Area of Science:

• Machine Learning
• Graph Theory
• Data Science

Background:

• Dynamic graph embedding methods often overlook temporal dynamics and embedding uncertainties in latent spaces.
• Existing approaches typically represent node embeddings as deterministic vectors, failing to capture evolving graph properties.

Purpose of the Study:

• To propose an efficient stochastic dynamic graph embedding method (DynG2G) that addresses limitations of deterministic vector-based embeddings.
• To quantify node embedding uncertainty on-the-fly by encoding nodes as time-dependent probabilistic Gaussian distributions.
• To establish a universal relationship between optimal embedding dimension and uncertainty dimensionality for dynamic graphs.

Main Methods:

• Developed an inductive feedforward encoder trained with a node triplet energy-based ranking loss.
• Encoded each node at each timestamp as a time-dependent probabilistic multivariate Gaussian distribution.
• Evaluated the method on eight diverse benchmark datasets varying in size and temporal dynamics.

Main Results:

• DynG2G achieved state-of-the-art performance in capturing temporal node embeddings across diverse benchmarks.
• The method successfully predicted evolving node embedding uncertainty, crucial for quantifying system dimensionality.
• A universal correlation (L_o = D_u) was identified between optimal embedding dimension and uncertainty dimensionality.

Conclusions:

• DynG2G effectively captures intrinsic dimensionality of evolving graphs through its uncertainty quantification.
• The discovered L_o - D_u correlation offers a method for adaptively selecting optimal embedding dimensions.
• The stochastic approach provides a more accurate representation of dynamic graph structures and their inherent uncertainties.