DeepSTE: Deep Spectral Temporal Embeddings for Dynamic Graph Representation Learning

Abstract

Temporal embeddings play a crucial role in dynamic graph neural networks (DGNNs) by capturing the temporal dynamics of interactions. However, existing Random Fourier Feature (RFF)-based methods in DGNNs directly sample Fourier frequencies from a fixed, data-independent distribution $p(\omega)$, neglecting the temporal characteristics of dynamic graphs and thereby limiting representational capacity. We propose DeepSTE, a deep spectral temporal embedding framework for dynamic graphs. DeepSTE learns RFF representations via Monte Carlo importance sampling with a tractable proposal distribution $q(\omega)$ (e.g., \texttt{Gaussian}) to approximate the feature map of a shift-invariant or positive-definite kernel whose latent spectral density is analytically intractable. DeepSTE adopts a data-dependent scale parameter $\eta$, estimated from interaction intervals, to construct the frequency proposal distribution $q(\omega)$ reflecting time–frequency uncertainty. The frequency DNN $f_{\boldsymbol{\omega}}$ and the importance-weighting DNN $g_{\mathbf{w}}$, initialized from $q(\omega)$, are jointly optimized to model the importance-sampled spectral representation and learn adaptive temporal features. Experiments indicate the effectiveness of DeepSTE with average improvements of 2.32\% and 1.32\% on the tasks of dynamic link prediction and node classification, respectively, and reveal insights such as temporal embedding decay and accelerated convergence.