# Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds

arXiv: https://arxiv.org/abs/2306.08967 · HTML: https://mlsanity.com/paper/2306.08967/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 57 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 28 of 28)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Heterogeneous Information Network Embedding for Recommendation](https://mlsanity.com/paper/1711.10730/) (2017)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [DynGEM: Deep Embedding Method for Dynamic Graphs](https://mlsanity.com/paper/1805.11273/) (2018)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [Node Embedding over Temporal Graphs](https://mlsanity.com/paper/1903.08889/) (2019)
- [Attributed Network Embedding for Learning in a Dynamic Environment](https://mlsanity.com/paper/1706.01860/) (2017)
- [dynnode2vec: Scalable Dynamic Network Embedding](https://mlsanity.com/paper/1812.02356/) (2018)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [TIMERS: Error-Bounded SVD Restart on Dynamic Networks](https://mlsanity.com/paper/1711.09541/) (2017)
- [A Survey of Knowledge Graph Embedding and Their Applications](https://mlsanity.com/paper/2107.07842/) (2021)
- [Instant Graph Neural Networks for Dynamic Graphs](https://mlsanity.com/paper/2206.01379/) (2022)
- [Scalable Graph Embeddings via Sparse Transpose Proximities](https://mlsanity.com/paper/1905.07245/) (2019)
- [Approximate Personalized PageRank on Dynamic Graphs](https://mlsanity.com/paper/1603.07796/) (2016)
- [GloDyNE: Global Topology Preserving Dynamic Network Embedding](https://mlsanity.com/paper/2008.01935/) (2020)
- [Network Embedding: An Overview](https://mlsanity.com/paper/1911.11726/) (2019)

## Built on by (most cited first, 1 of 1)

- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)

## Abstract (arXiv)

Network embedding, a graph representation learning method illustrating network topology by mapping nodes into lower-dimension vectors, is challenging to accommodate the ever-changing dynamic graphs in practice. Existing research is mainly based on node-by-node embedding modifications, which falls into the dilemma of efficient calculation and accuracy. Observing that the embedding dimensions are usually much smaller than the number of nodes, we break this dilemma with a novel dynamic network embedding paradigm that rotates and scales the axes of embedding space instead of a node-by-node update. Specifically, we propose the Dynamic Adjacency Matrix Factorization (DAMF) algorithm, which achieves an efficient and accurate dynamic network embedding by rotating and scaling the coordinate system where the network embedding resides with no more than the number of edge modifications changes of node embeddings. Moreover, a dynamic Personalized PageRank is applied to the obtained network embeddings to enhance node embeddings and capture higher-order neighbor information dynamically. Experiments of node classification, link prediction, and graph reconstruction on different-sized dynamic graphs suggest that DAMF advances dynamic network embedding. Further, we unprecedentedly expand dynamic network embedding experiments to billion-edge graphs, where DAMF updates billion-level parameters in less than 10ms.