Xu Mengjia, Singh Apoorva Vikram, Karniadakis George Em
IEEE Trans Neural Netw Learn Syst. 2022 Jun 10;PP. doi: 10.1109/TNNLS.2022.3178706.
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 , versus the effective dimensionality of uncertainty, D , and infer that L=D 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 correlation provides a clear path to selecting adaptively the optimum embedding size at each timestamp by setting L ≥ D .
动态图嵌入由于能够为复杂的时态图高精度地学习低维且有意义的图表示，近来受到了广泛关注。然而，近期的进展大多集中于为静态图学习作为确定性“向量”的节点嵌入，从而忽略了关键的图时间动态以及与潜在空间中节点嵌入相关的不断演变的不确定性。在这项工作中，我们提出了一种高效的随机动态图嵌入方法（DynG2G），该方法应用基于节点三元组能量排序损失训练的归纳前馈编码器。每个时间戳的每个节点在潜在空间中被编码为一个随时间变化的概率多元高斯分布，因此，我们能够实时量化节点嵌入的不确定性。我们考虑了八个不同的基准，这些基准在大小（从96个节点到87626个节点，从13398条边到4870863条边）以及动态方面具有多样性，涵盖了从缓慢变化的时间演变到快速变化的多速率动态。我们通过基于这八个动态图基准的大量实验表明，DynG2G在捕获潜在的时间节点嵌入方面取得了新的最优性能。我们还表明，DynG2G能够同时预测不断演变的节点嵌入不确定性，这在量化随时间变化的动态系统的固有维度方面起着关键作用。特别地，我们得到了最优嵌入维度(L)与不确定性有效维度(D)的“通用”关系，并推断在所有情况下(L = D)。这反过来意味着，尽管每个时间戳的图具有不同的性质和组成，但我们在DynG2G算法中采用的不确定性量化方法正确地捕获了此类演变图动态的固有维度。此外，这种(L - D)相关性为通过设置(L \geq D)在每个时间戳自适应地选择最优嵌入大小提供了一条清晰的途径。
