# Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec

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

## Key facts

- Cited by 198 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2017.

## Built on by (most cited first, 30 of 198)

- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs](https://mlsanity.com/paper/2107.01495/) (2021)
- [Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning](https://mlsanity.com/paper/2111.04314/) (2021)
- [Simple and Asymmetric Graph Contrastive Learning without Augmentations](https://mlsanity.com/paper/2310.18884/) (2023)
- [Link Prediction with Persistent Homology: An Interactive View](https://mlsanity.com/paper/2102.10255/) (2021)
- [Graph Domain Adaptation: A Generative View](https://mlsanity.com/paper/2106.07482/) (2021)
- [Graph Auto-Encoder Via Neighborhood Wasserstein Reconstruction](https://mlsanity.com/paper/2202.09025/) (2022)
- [Learning Conjoint Attentions for Graph Neural Nets](https://mlsanity.com/paper/2102.03147/) (2021)
- [A Survey on Spectral Graph Neural Networks](https://mlsanity.com/paper/2302.05631/) (2023)
- [GRAND+: Scalable Graph Random Neural Networks](https://mlsanity.com/paper/2203.06389/) (2022)
- [Self-Supervised Temporal Graph learning with Temporal and Structural Intensity Alignment](https://mlsanity.com/paper/2302.07491/) (2023)
- [Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning](https://mlsanity.com/paper/2104.09856/) (2021)
- [Privacy-Preserving Representation Learning on Graphs: A Mutual Information Perspective](https://mlsanity.com/paper/2107.01475/) (2021)
- [Edgeformers: Graph-Empowered Transformers for Representation Learning on Textual-Edge Networks](https://mlsanity.com/paper/2302.11050/) (2023)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [Joint Embedding of Structural and Functional Brain Networks with Graph Neural Networks for Mental Illness Diagnosis](https://mlsanity.com/paper/2107.03220/) (2021)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [Network Representation Learning: From Preprocessing, Feature Extraction to Node Embedding](https://mlsanity.com/paper/2110.07582/) (2021)
- [Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs](https://mlsanity.com/paper/2103.14187/) (2021)
- [Social Recommendation with Self-Supervised Metagraph Informax Network](https://mlsanity.com/paper/2110.03958/) (2021)
- [DPPIN: A Biological Repository of Dynamic Protein-Protein Interaction Network Data](https://mlsanity.com/paper/2107.02168/) (2021)
- [Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction](https://mlsanity.com/paper/2111.05941/) (2021)
- [Affinity-Aware Graph Networks](https://mlsanity.com/paper/2206.11941/) (2022)

## Abstract (arXiv)

Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of the aforementioned models with negative sampling can be unified into the matrix factorization framework with closed forms. Our analysis and proofs reveal that: (1) DeepWalk empirically produces a low-rank transformation of a network's normalized Laplacian matrix; (2) LINE, in theory, is a special case of DeepWalk when the size of vertices' context is set to one; (3) As an extension of LINE, PTE can be viewed as the joint factorization of multiple networks' Laplacians; (4) node2vec is factorizing a matrix related to the stationary distribution and transition probability tensor of a 2nd-order random walk. We further provide the theoretical connections between skip-gram based network embedding algorithms and the theory of graph Laplacian. Finally, we present the NetMF method as well as its approximation algorithm for computing network embedding. Our method offers significant improvements over DeepWalk and LINE for conventional network mining tasks. This work lays the theoretical foundation for skip-gram based network embedding methods, leading to a better understanding of latent network representation learning.