Source-linked AI summary
Dynamic Network Embedding Survey
Guotong Xue, Ming Zhong, Jianxin Li, Jia Chen, Chengshuai Zhai, Ruochen Kong
TL;DR
Dynamic network embedding must represent both structural relationships and temporal evolution in networks whose nodes, edges, and attributes change. This survey synthesizes the field through formal data models, a taxonomy of learning approaches, comparisons, resources, applications, and challenges. It identifies discrete and continuous models alongside structural-first and temporal-first methodologies, while noting unresolved issues including general structure changes and scalability.
Problem
Dynamic networks change in attributes and topology, creating a need for embeddings that preserve structure while describing temporal evolution.
Method
The survey defines discrete and continuous data models and organizes existing methods into structural-first and temporal-first categories refined by learning models.
Results
The survey presents and compares dynamic network embedding methods, and summarizes datasets, evaluation tasks, applications, and recurring research challenges.
Takeaways & Limitations
The taxonomy links common data models with high-level methodologies and provides a structured reference for understanding current dynamic network embedding research.
Takeaways & Limitations
Existing work often omits node or edge deletion, while increasing network scale makes reducing model complexity and using accumulated history an open direction.
Abstract
from arXiv · showhide
Since many real world networks are evolving over time, such as social networks and user-item networks, there are increasing research efforts on dynamic network embedding in recent years. They learn node representations from a sequence of evolving graphs but not only the latest network, for preserving both structural and temporal information from the dynamic networks. Due to the lack of comprehensive investigation of them, we give a survey of dynamic network embedding in this paper. Our survey inspects the data model, representation learning technique, evaluation and application of current related works and derives common patterns from them. Specifically, we present two basic data models, namely, discrete model and continuous model for dynamic networks. Correspondingly, we summarize two major categories of dynamic network embedding techniques, namely, structural-first and temporal-first that are adopted by most related works. Then we build a taxonomy that refines the category hierarchy by typical learning models. The popular experimental data sets and applications are also summarized. Lastly, we have a discussion of several distinct research topics in dynamic network embedding.
1. Introduction
Dynamic network embedding addresses evolving node, edge, attribute, and topology information that static methods cannot adequately represent. This survey organizes existing approaches through data models, learning methodologies, comparisons, challenges, resources, and applications.
- Motivation: Real-world networks evolve through changes in node and edge attributes, as well as the creation or removal of nodes and edges.
- Examples: User-item, payment, and social networks exhibit time-dependent interaction patterns relevant to recommendation, fraud detection, link prediction, and community detection.
- Motivation: Dynamic embeddings aim to preserve structural relationships while describing topological changes over time.
- Motivation: Dynamic methods can update representations at fine-grained times and often avoid the costly retraining required by static methods.
- Survey scope: The survey reviews state-of-the-art approaches, compares them across multiple perspectives, and derives common patterns for future research.
- Contributions: Its contributions include two common data models, a hierarchical taxonomy, reviews of datasets and applications, and discussion of critical challenges.
2. Dynamic Network Models
The survey distinguishes dynamic-network data models by how graph updates occur: discrete snapshots or continuous timestamped streams. These definitions shape which embedding techniques are appropriate, while implementations vary in attribute handling and support for node deletion.
- Data-model overview: Dynamic networks update nodes, edges, and attributes over time through either discrete intervals or continuous streams.
- Discrete Model: Discrete snapshots usually differ only slightly between adjacent times, with some nodes and edges created or removed.
- Discrete Model: The discrete model represents a dynamic network as a sequence of snapshots, each a complete static graph recorded at a particular time.
- Continuous Model: The continuous model represents network edges and nodes with timestamps, allowing interactions and property changes to arrive in a stream.
- Model variations: Existing methods differ in whether they model attributes, raw networks, node additions, or node deletions.
3. Taxonomy of Embedding Techniques
The taxonomy organizes dynamic network embedding methods around preserving network structure and temporal evolution. It separates structural-first, temporal-first, and other approaches, then refines them by their underlying learning models.
- Fundamental challenges: Dynamic embeddings must preserve both structural relationships, including high-order proximity, and network evolution over time.
- Structural-first: Structural-first methods add temporal features to structure-preserving models such as Skip-gram, autoencoders, and GNNs.
- Temporal-first: Temporal-first methods add structural or property features to temporal models such as RNNs and LSTMs.
- Taxonomy: The taxonomy contains three broad categories—structural-first, temporal-first, and others—with learning-model subcategories within them.
3.1. Structural-first model
Structural-first methods learn dynamic network embeddings by first extracting structural information and then incorporating temporal changes through model-specific updates. The survey organizes these methods by learning model, including matrix factorization, autoencoder, Skip-gram, and GNN approaches.
- Matrix factorization based model: DANE combines topology and attribute embeddings by maximizing their correlation, then uses eigenvalue and eigenvector perturbations to capture dynamics.Its construction addresses incomplete and noisy topology or attribute representations.
- Matrix factorization based model: Matrix factorization methods represent evolving networks as changing matrices and update embeddings through generalized SVD and matrix perturbation.They can handle node and edge increases or decreases, but are most suitable for subtle changes and require accelerated perturbation solutions to reduce computational complexity.
- Autoencoder based model: Autoencoder methods learn node representations by mapping inputs into latent features and reconstructing the original samples.DynGEM incrementally initializes each snapshot from the previous embedding, while other models use longer histories, LSTM, GraphSAGE, or RNN components for different change patterns.
- Autoencoder based model: NetWalk uses sparse autoencoding on random-walk vertex lists and updates reservoir-stored walks when continuous edge changes occur.The model then continues training with the updated walk set in a warm-start fashion.
- Skip-gram based model: Skip-gram methods commonly sample random walks to update node context information as the network evolves.They update only subsets of nodes and therefore perform better when network structure changes little; continuous-time variants constrain walks to edges with increasing timestamps.
- GNN based model: GNN-based DySAT separates structural and temporal attention blocks, enabling fine-grained node-level temporal dependencies in general dynamic networks.DyHAN extends this approach with hierarchical attention, and experiments report the efficacy of modeling structural heterogeneity.
3.2. Temporal-first model
Temporal-first methods begin with models for sequential data and incorporate network structure to update embeddings as dynamic interactions occur. They are especially suited to continuous-time updates and are commonly applied to recommendation systems.
- RNN based model: RNN-based methods use sequential models to encode temporal information in dynamic network embeddings.GRU and LSTM process variable-length input sequences using internal states as memory.
- RNN based model: DGNN updates source and endpoint embeddings when new interactions occur and propagates their influence to first-order neighbors.Its design extends LSTM to capture both global effects of new edges and local effects on connected nodes.
- RNN based model: DyRep models continuous network evolution through separate association and communication processes.Association changes long-lasting topology, whereas communication propagates information briefly among adjacent nodes.
- RNN based model: JODIE uses coupled RNNs and attention for user-item networks, updating user and item embeddings at every interaction.Its formulation combines previous embeddings, static features, and elapsed time since the user's previous interaction.
- RNN based model: DyHATR and related models extend temporal-first learning to heterogeneous dynamic graphs with multiple edge types and evolutionary attention.DyHATR combines hierarchical attention for heterogeneity with temporal attentive GRU/LSTM components.
- RNN based model: RNN-based continuous methods update node and edge changes more timely and are usually used in recommendation systems.Their designs differ according to the specific network structure, such as a user-item bipartite network.
3.3. Others
Other dynamic embedding methods address inductive inference, triadic closure, temporal heterogeneity, and network dynamics across multiple temporal scales. Their mechanisms are tailored to particular prediction or structural modeling needs.
- Others: DepthLGP combines a high-order Laplacian Gaussian process with a deep neural network to infer embeddings for out-of-sample nodes.Its nonparametric probabilistic modeling supports scalable inference at high speed.
- Others: DynamicTriad learns embeddings by modeling the probability that an open triad evolves into a closed triad.It uses a semi-supervised objective with a sampling strategy based on embeddings of the three nodes.
- Others: MMDNE separates micro-dynamics of edge establishment from macro-dynamics of network-scale evolution.It uses a temporal point process for micro-dynamics and hierarchical temporal attention for node representations.
- Others: TGAT produces inductive representations using functional time encoding based on Bochner’s theorem and self-attention for neighborhood aggregation.The method combines temporal encoding with attention-based structural information.
4. Discussion
The discussion organizes dynamic network embedding around long-term feature preservation, inductive embedding for new nodes, and prediction of future representations. These topics connect modeling choices with practical update and forecasting requirements.
- Long-term Features Preservation: Long-term network patterns such as communities, hubs, and repeated interactions are important features to preserve during evolution.A forming hub may signal illegal transactions, while repeated user-item interactions can indicate enduring product preferences.
- Long-term Features Preservation: Matrix-factorization methods often use matrix perturbation, while deep models reuse previous parameters to retain dynamic information.Parameter reuse does not explicitly focus on preserving long-term features.
- Out-of-sample Node Embedding: Dynamic embedding methods can infer representations for out-of-sample nodes because newly added nodes are treated as part of the network at the next time step.Inductive dynamic methods can additionally exploit temporal features.
- Out-of-sample Node Embedding: Incremental training is accelerated by generating walks only for changed nodes, using t-Batch, or learning unseen-node representations directly.These strategies are associated with dynnode2vec, NetWalk, JODIE, DyRep, and TGAT.
- Prediction for Future Embedding: Future-embedding prediction supports applications such as product recommendation and fraud detection.dyngraph2vec uses an autoencoder to predict node embeddings for the next snapshot, while JODIE predicts evolving user interests without fresh interactions.
5. Data Sets, Evaluation and Applications
The survey summarizes datasets, evaluation tasks, and applications for dynamic network embedding. It covers node and link prediction alongside recommendation, anomaly detection, and traffic forecasting.
- Data Sets: The survey compiles commonly used dynamic-network datasets together with their size and temporal granularity.These datasets are summarized in Table 2.
- Evaluation: Evaluation includes node classification, which assigns labels to nodes using learned features when labels are unavailable for many nodes.Examples include research fields in citation networks and user interests in e-commerce.
- Evaluation: Link prediction targets missing links or edges that may form in the future by estimating whether two nodes will connect.The task can be formulated as binary classification.
- Practical applications: Anomaly detection uses temporal transaction patterns to identify malicious behavior and support early fraud detection.The survey highlights financial networks, where a deceiver’s timeline of transactions may differ from normal users.
- Practical applications: Dynamic embedding supports recommender systems by extracting temporal user and item features for importance scoring.User-item recommendation can be treated as a link-prediction problem.
- Practical applications: Dynamic embedding methods are also applied to traffic forecasting, including traffic-flow prediction, diffusion modeling, and ride-hailing demand forecasting.Traffic flow is modeled as a directed network.
- Practical applications: The survey provides links to open-source implementations of dynamic network embedding methods.The code links are collected in Table 3.
6. Conclusion and Future Direction
The survey organizes dynamic network embedding methods, datasets, applications, and challenges, then identifies future directions including heterogeneous networks, broader structural changes, scalability, and task-oriented models.
- The survey defines discrete and continuous dynamic-network data models and proposes a taxonomy organizing embedding methods by data models and methodologies.It also presents brief comparisons of current methods.
- Future work includes learning embeddings for heterogeneous dynamic networks with multiple node and edge types.Research on heterogeneous dynamic graphs is described as just getting started.
- Many existing works omit node or edge deletion, motivating methods that represent more general structural changes.The survey connects structural changes with information such as special subgraph formation.
- Scalable models are needed as evolving networks grow and accumulate snapshots or timestamps.Future work should reduce model complexity while exploiting historical records.
- Task-oriented dynamic embeddings remain an open direction for applications such as community detection beyond node classification and link prediction.The survey identifies specialized network-data-mining tasks as worthy of further study.