A Survey on Dynamic Network Embedding

Yu Xie, Chunyi Li, Bin Yu, Chen Zhang, Zhouhua TangarXiv 2020 · arXiv · OpenReview

TL;DR

This paper provides a comprehensive survey of dynamic network embedding techniques, addressing the limitations of static approaches by considering evolving network structures. It introduces a novel taxonomy to categorize existing methods and highlights key challenges and future research directions in this rapidly advancing field.

What Problem Does This Paper Address?

Real-world networks, from social interactions to biological systems, are inherently dynamic, with entities and their connections constantly changing. Traditional network embedding methods often treat these networks as static snapshots, failing to capture crucial temporal information. This oversight limits their effectiveness in tasks that rely on understanding evolving network behavior. The paper addresses this gap by surveying methods that specifically aim to embed dynamic networks, preserving both structural and temporal dynamics for improved downstream machine learning applications.

Methods

The authors propose a novel taxonomy for dynamic network embedding, categorizing existing techniques into five main groups:

  • Matrix Factorization Based: These methods leverage techniques like Singular Value Decomposition (SVD) to reduce dimensionality and capture network structure. They are extended to dynamic settings by updating matrices based on temporal changes.
  • Skip-Gram Based: Inspired by Word2Vec, these methods adapt random walk sequences to represent network structures. For dynamic networks, they incorporate temporal information by constraining random walks to follow edge timestamps or by initializing embeddings with previous temporal information.
  • Auto-encoder Based: These unsupervised learning models learn compressed representations of networks. In dynamic settings, they often retain and adapt embeddings from previous time steps to capture evolving structures.
  • Neural Networks Based: This category includes more advanced deep learning architectures, such as Recurrent Neural Networks (RNNs) and Graph Convolutional Networks (GCNs), designed to handle sequential and structural data, respectively. They are adapted to dynamic networks by incorporating temporal dependencies and attention mechanisms.
  • Other Embedding Methods: This catch-all category includes approaches that don't fit neatly into the above, such as those focusing on specific network phenomena like triangular closure or streaming graph neural networks.

The paper also discusses preprocessing steps, which typically involve transforming network data into uniform linear arrays and generating normalized matrices for dynamic network evolution.

Datasets

The paper lists several commonly used datasets for dynamic network embedding research, including:

  • Academic: A coauthorship network.
  • Autonomous Systems (AS): A communication network.
  • CollegeMsg: Private messages from an online social network.
  • DBLP: An academic publication network.
  • Email-Eu-core: An email communication network.
  • Enron: Emails among employees.
  • Epinions: A goods review website with trust relationships.
  • F2f-Resistance: A weighted, directed, and temporal network.
  • HEP-TH: A collaboration network of authors.
  • Infectious: Visitor interactions in an exhibition.
  • Internet: A network of internet autonomous systems.
  • Loan: Call records from a mobile dataset.
  • Mobile: A mobile network.
  • Synthetic Data (SYD): Dynamically generated graphs.
  • Twitter: User interactions and blog information.
  • Wikipedia: Communication between users.

Key Insights and Ideas

  • The critical need for dynamic embedding: Static network embedding is insufficient for understanding evolving networks, leading to increased computational costs and missed temporal insights.
  • A unified taxonomy: The paper introduces a novel categorization of dynamic network embedding methods, providing a structured way to understand the diverse landscape of existing techniques.
  • Snapshot vs. Continuous-Time: Dynamic networks can be modeled as discrete snapshots or continuous-time streams, each with its own advantages and challenges for embedding.
  • Challenges in dynamic embedding: Existing methods face hurdles in handling large-scale networks, heterogeneous structures, attributed data, and task-specific optimizations.
  • Future research is crucial: The field is still nascent, with significant opportunities for developing more efficient, adaptable, and comprehensive dynamic network embedding models.

Key Results

The paper is a survey, so it doesn't present new experimental results. Instead, it synthesizes the state-of-the-art by:

  • Systematically categorizing existing dynamic network embedding techniques.
  • Summarizing common datasets and downstream tasks that benefit from dynamic embedding.
  • Identifying key challenges faced by current algorithms.
  • Outlining promising future research directions to guide the field.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Dynamic Embedding Models: There's a need for models that can effectively update embeddings in real-time as network structures change (e.g., edge additions/removals), rather than requiring reprocessing of the entire network.
  • Large-scale Dynamic Networks: Existing methods struggle with the complexity of large-scale dynamic networks, necessitating more efficient evolution handling or improved embedding models.
  • Heterogeneous Dynamic Networks: Many real-world networks are heterogeneous (multiple node/edge types). Dynamic embedding needs to account for these diverse types and their evolution.
  • Dynamic Attributed Networks: Capturing information from both evolving network structures and dynamic node attributes remains a challenge.
  • Task-oriented Dynamic Network Embedding: While static networks have task-specific embedding methods, this area is underdeveloped for dynamic networks.
  • More Embedding Spaces: Exploring embedding networks into multiple spaces could unlock richer representations and preserve more complex structures, though this increases computational complexity.

Summary updated

Abstract

Real-world networks are composed of diverse interacting and evolving entities, while most of existing researches simply characterize them as particular static networks, without consideration of the evolution trend in dynamic networks. Recently, significant progresses in tracking the properties of dynamic networks have been made, which exploit changes of entities and links in the network to devise network embedding techniques. Compared to widely proposed static network embedding methods, dynamic network embedding endeavors to encode nodes as low-dimensional dense representations that effectively preserve the network structures and the temporal dynamics, which is beneficial to multifarious downstream machine learning tasks. In this paper, we conduct a systematical survey on dynamic network embedding. In specific, basic concepts of dynamic network embedding are described, notably, we propose a novel taxonomy of existing dynamic network embedding techniques for the first time, including matrix factorization based, Skip-Gram based, autoencoder based, neural networks based and other embedding methods. Additionally, we carefully summarize the commonly used datasets and a wide variety of subsequent tasks that dynamic network embedding can benefit. Afterwards and primarily, we suggest several challenges that the existing algorithms faced and outline possible directions to facilitate the future research, such as dynamic embedding models, large-scale dynamic networks, heterogeneous dynamic networks, dynamic attributed networks, task-oriented dynamic network embedding and more embedding spaces.
BibTeX
@misc{xie2020survey,
  author = {Yu Xie and Chunyi Li and Bin Yu and Chen Zhang and Zhouhua Tang},
  title = {{A Survey on Dynamic Network Embedding}},
  year = {2020},
  eprint = {2006.08093},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.08093},
}
Figure