DynGEM: Deep Embedding Method for Dynamic Graphs

By Palash Goyal, Nitin Kamra, Xinran He, Yan Liu. arXiv.org, 2018

423 citations recorded by the source corpus.

Embedding large graphs in low dimensional spaces has recently attracted significant interest due to its wide applications such as graph visualization, link prediction and node classification. Existing methods focus on computing the embedding for static graphs. However, many graphs in practical applications are dynamic and evolve constantly over time. Naively applying existing embedding algorithms to each snapshot of dynamic graphs independently usually leads to unsatisfactory performance in terms of stability, flexibility and efficiency. In this work, we present an efficient algorithm DynGEM based on recent advances in deep autoencoders for graph embeddings, to address this problem. The major advantages of DynGEM include: (1) the embedding is stable over time, (2) it can handle growing dynamic graphs, and (3) it has better running time than using static embedding methods on each snapshot of a dynamic graph. We test DynGEM on a variety of tasks including graph visualization, graph reconstruction, link prediction and anomaly detection (on both synthetic and real datasets). Experimental results demonstrate the superior stability and scalability of our approach.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Transportation

View Paper: https://www.semanticscholar.org/paper/1d49c0dd13911f44418d46ec5fac128d6c4bbf59

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Transportation

Citations in the corpus

Incremental Training of Graph Neural Networks on Temporal Graphs under Distribution Shift (2020, methodology): “DynGEM [9] uses deep autoencoders to jointly minimize reconstruction loss between t and t +1 and embedding distance between connected vertices.”
Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks (2019, methodology): “hm, DynamicTriad [50] learns dynamic embeddings but does not work on bipartite interaction networks as it requires the presence of triads. Other recent algorithms such as DDNE [29], DANE [28], DynGem [15], Zhu et al. [51], and Rahman et al. [38] learn embeddings from a sequence of graph snapshots, w”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “The approach of Goyal et al. [81] uses the information within previous snapshots of a DTDG to enable learning an autoencoder for the current snapshot faster.”
dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning (2018, methodology): “DynGEM [26] uses the learned embedding from previous time step graphs to initialize the current time step embedding.”
Representation Learning for Dynamic Graphs: A Survey (2019, methodology): “This approach is used mainly in graph autoencoders (see, e.g., Wang et al. (2016); Cao et al. (2016); Tran (2018); Goyal et al. (2017); Chen et al. (2018a)) and is used for both directed and undirected graphs.”
Inductive Representation Learning on Temporal Graphs (2020, methodology): “…to the temporal domain, several attempts have been done by cropping the temporal graph into a sequence of graph snapshots (Li et al., 2018; Goyal et al., 2018; Rahman et al., 2018; Xu et al., 2019b), and some others work with temporally persistent node (edges) (Trivedi et al., 2018; Ma et…”
Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs (2019, methodology): “There are attempts on predicting future links on homogeneous graphs (Pareja et al., 2020; Goyal et al., 2018, 2019; Zhou et al., 2018; Singer et al., 2019).”
Temporal Graph Networks for Deep Learning on Dynamic Graphs (2020, methodology): “In the latter case, the embeddings are either aggregated by taking a weighted sum [67, 74], ﬁt to time series models [30, 24, 11, 44], used as components in RNNs [55, 45, 41, 69, 8, 54, 48], or learned by imposing a smoothness constraint over time [33, 25, 67, 75, 73, 57, 22, 17, 50].”