Source-linked AI summary
DynGEM: Deep Embedding Method for Dynamic Graphs
Palash Goyal, Nitin Kamra, Xinran He, Yan Liu
TL;DR
Dynamic graph embedding must handle evolving links and nodes without sacrificing stability or efficiency. DynGEM incrementally trains a deep autoencoder from prior embeddings and expands its architecture for growing graphs. Experiments report comparable or better accuracy more efficiently than static approaches, with applicability to visualization and anomaly detection.
Problem
Dynamic graphs evolve through changing links and node membership, while independently embedding each snapshot can be unstable, inefficient, and unable to handle growing graphs.
Method
DynGEM incrementally trains a deep autoencoder from the previous snapshot’s embedding and uses PropSize to expand the network for growing graphs.
Results
Experiments on synthetic and real-world datasets achieve similar or better graph reconstruction and link prediction accuracy more efficiently than static approaches, while supporting visualization and anomaly detection.
Takeaways & Limitations
DynGEM provides stable dynamic embeddings across time and remains applicable to growing graphs and multiple evaluation tasks.
Takeaways & Limitations
The method’s stability is ensured through previous-step weight initialization, and the authors identify explicit stability integration, theoretical insight, and performance bounds as future work.
Abstract
from arXiv · showhide
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.
1 Introduction
Dynamic graphs evolve through changing links and node membership, making snapshot-by-snapshot static embedding inadequate. DynGEM addresses stability, growth, and efficiency with incremental deep autoencoder training and achieves competitive results across several tasks.
- Dynamic graphs evolve through changing links, disappearing edges, and newly introduced nodes, commonly represented as time-indexed snapshots.
- Independent static embeddings can be unstable, with consecutive representations differing substantially even when the underlying graphs change little.
- Existing approaches assume a fixed node count, preventing them from handling graphs that grow as new nodes join and connect to existing nodes.
- Training a separate embedding for every snapshot yields running time linear in the number of snapshots and limits scalability.
- DynGEM incrementally initializes each snapshot from the previous embedding, using a deep autoencoder and expanding its network with PropSize for growing graphs.
- Experiments on synthetic and real-world datasets show similar or better graph reconstruction and link prediction accuracy more efficiently than static approaches, while supporting visualization and anomaly detection.
2 Definitions and Preliminaries
The paper formalizes graph and dynamic graph embeddings as low-dimensional mappings over time-indexed snapshots, including growing-graph assumptions. It also defines stability measures that compare embedding changes with graph changes.
- A weighted graph G(V, E) consists of vertices and edges, with adjacency matrix S storing positive edge weights and zeroes for absent edges.
- A graph embedding maps each node v to a d-dimensional vector while preserving graph proximity, with d much smaller than the number of nodes.
- A dynamic graph is represented as snapshots G = {G1, · · · , GT}, with growing node sets Vt ⊆ Vt+1 and edges that may appear or disappear between snapshots.
- A dynamic graph embedding is a time-series of mappings, one graph embedding for each snapshot that preserves the snapshot’s proximity measure.
- Stability requires consecutive embeddings to change only modestly when their underlying graphs change little.
- Absolute stability is the ratio of embedding change to adjacency-matrix change, while relative stability removes dependence on matrix size.
- The stability constant KS(F) summarizes stability, with smaller values indicating more stable dynamic embeddings and serving as an experimental comparison metric.
3 DynGEM: Dynamic Graph Embedding Model
DynGEM uses a deep autoencoder that incrementally updates embeddings across snapshots and expands its architecture as graphs grow. Its objectives preserve local and global graph structure while regularization and ReLU-based training support scalable learning.
- Model and objectives: DynGEM maps node neighborhoods through a deep autoencoder to produce low-dimensional embeddings and reconstruct those neighborhoods.The encoder outputs d-dimensional representations, while the decoder reconstructs the input neighborhoods.
- Handling growing graphs: PropSize expands layer widths or inserts layers while keeping the embedding dimension fixed as new nodes are added.The heuristic keeps consecutive layer sizes within a chosen factor and is applied to both encoder and decoder architectures.
- Handling growing graphs: Net2WiderNet and Net2DeeperNet widen or deepen the autoencoder while approximately preserving its learned function.Net2DeeperNet inserts an identity-like intermediate layer for ReLU activations, enabling architectural growth across time steps.
- Model and objectives: The model combines first-order proximity, second-order proximity, and regularization objectives when learning each snapshot.First-order proximity captures local structure; second-order proximity preserves global neighborhoods through reconstruction, while regularizers encourage sparse weights and reduce overfitting.
- Incremental training: DynGEM initializes each subsequent snapshot from the previous model parameters, transferring structural knowledge and keeping embeddings close across time.The first snapshot is trained with random initialization; later snapshots reuse the preceding parameters before training.
- Training choices: ReLU activations support weighted graphs, accelerate training, and allow gradients from both proximity objectives to propagate effectively.The method also uses Nesterov momentum and combined L1 and L2 regularization, which the authors report improved performance across tasks.
4 Experiments
DynGEM is evaluated on synthetic and real-world dynamic graphs using graph reconstruction, link prediction, embedding stability, and anomaly detection. The experiments compare it with independently trained and temporally initialized static embedding baselines under specified dataset and training settings.
- Datasets: The evaluation uses synthetic and real-world dynamic graphs, including SYN, HEP-TH, Autonomous Systems, and ENRON.SYN models changing communities; HEP-TH contains 60 monthly graphs with nodes increasing from 1,424 to 7,980.
- Compared methods: The comparison includes independently applied SDNE, aligned SDNE or GF embeddings, GF initialized from the previous snapshot, and DynGEM.Embedding dimensions are set to 20 for ENRON and 100 for the other datasets.
- Experimental settings: The SDNE baselines replace sigmoid activations with ReLU activations to improve scalability and training speed.Other neural-network structures and optimization parameters are selected through informal architecture search, grid search, and cross-validation.
- Tasks and metrics: The experiments measure graph reconstruction, link prediction, embedding stability, and anomaly detection.MAP is used for graph reconstruction and link prediction, while stability is measured with the constant KS(F).
5 Results and Analysis
DynGEM performs well across graph reconstruction, link prediction, stability, visualization, anomaly detection, and scalability evaluations. Its incremental dynamic embedding supports accurate adaptation to structural changes while preserving unaffected node embeddings and reducing computation time.
- Graph Reconstruction: DynGEM outperforms Graph Factorization baselines on graph reconstruction, except on HEP-TH where performance is comparable.Graph reconstruction is evaluated using averaged MAP over snapshots.
- Link Prediction: DynGEM predicts missing edges better than the baselines on all datasets.The evaluation hides 15% of network edges and reports prediction accuracy averaged over time.
- Stability of Embedding Methods: DynGEM substantially outperforms other models on embedding stability while maintaining better graph reconstruction performance.Stability is evaluated using stability constants on four datasets.
- Visualization: DynGEM follows community changes accurately without disturbing other node embeddings, even when 30% of nodes change communities.Figure 2 visualizes 100-dimensional embeddings in two dimensions, with colors indicating communities and point sizes indicating changed nodes.
- Anomaly Detection: Anomaly-score spikes around weeks 45, 55, and 94 correspond to major Enron events, while week 94 shows compact embeddings associated with increased communication.The anomaly score is defined as the embedding change between consecutive time steps and can be thresholded for detection.
- Scalability: DynGEM achieves consistent 2-3X speed up across a variety of different networks.Its observed speedup approaches the expected speedup as the number of snapshots increases, because fixed overheads become less important.
6 Conclusion
DynGEM constructs stable, efficient embeddings for dynamic graphs and remains competitive across several evaluation tasks. The authors identify explicit stability modeling, theoretical analysis, and performance bounds as future work.
- DynGEM constructs fast, efficient, stable embeddings for dynamic graphs and remains competitive on graph reconstruction, link prediction, and visualization.It also successfully detects anomalies, extending dynamic graph embedding to this application.
- DynGEM preserves community structures accurately even when approximately 30% of nodes change communities between time steps.
- The authors plan to incorporate the stability metric explicitly while maintaining satisfactory anomaly-detection performance.
- Future work also includes developing theoretical insight into DynGEM and obtaining bounds on performance.