# NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2019.

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

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Multiplex Heterogeneous Graph Convolutional Network](https://mlsanity.com/paper/2208.06129/) (2022)
- [A Broader Picture of Random-walk Based Graph Embedding](https://mlsanity.com/paper/2110.12344/) (2021)
- [OAG-Bench: A Human-Curated Benchmark for Academic Graph Mining](https://mlsanity.com/paper/2402.15810/) (2024)
- [CogDL: A Comprehensive Library for Graph Deep Learning](https://mlsanity.com/paper/2103.00959/) (2021)
- [REFINE: Random RangE FInder for Network Embedding](https://mlsanity.com/paper/2108.10703/) (2021)
- [A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations](https://mlsanity.com/paper/2204.05885/) (2022)
- [Recommender systems based on graph embedding techniques: A comprehensive review](https://mlsanity.com/paper/2109.09587/) (2021)
- [Collaborative Graph Neural Networks for Attributed Network Embedding](https://mlsanity.com/paper/2307.11981/) (2023)
- [PST-Bench: Tracing and Benchmarking the Source of Publications](https://mlsanity.com/paper/2402.16009/) (2024)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)
- [Large-Scale Network Embedding in Apache Spark](https://mlsanity.com/paper/2106.10620/) (2021)
- [A Framework for Large Scale Synthetic Graph Dataset Generation](https://mlsanity.com/paper/2210.01944/) (2022)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report](https://mlsanity.com/paper/2501.04570/) (2025)
- [Low-Rank Subspaces for Unsupervised Entity Linking](https://mlsanity.com/paper/2104.08737/) (2021)
- [A Survey on Role-Oriented Network Embedding](https://mlsanity.com/paper/2107.08379/) (2021)
- [Finding MNEMON: Reviving Memories of Node Embeddings](https://mlsanity.com/paper/2204.06963/) (2022)
- [Continuous-time Graph Representation with Sequential Survival Process](https://mlsanity.com/paper/2312.13068/) (2023)
- [Multiple Kernel Representation Learning on Networks](https://mlsanity.com/paper/2106.05057/) (2021)
- [Network representation learning: A macro and micro view](https://mlsanity.com/paper/2111.10772/) (2021)
- [Privacy-Preserving Graph Embedding based on Local Differential Privacy](https://mlsanity.com/paper/2310.11060/) (2023)
- [Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling](https://mlsanity.com/paper/2105.09182/) (2021)
- [Leveraging semantically similar queries for ranking via combining representations](https://mlsanity.com/paper/2106.12621/) (2021)
- [Towards Improving Embedding Based Models of Social Network Alignment via Pseudo Anchors](https://mlsanity.com/paper/2111.11335/) (2021)
- [Distributed Graph Embedding with Information-Oriented Random Walks](https://mlsanity.com/paper/2303.15702/) (2023)
- [Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation](https://mlsanity.com/paper/2505.20992/) (2025)
- [Self-Supervised Deep Graph Embedding with High-Order Information Fusion for Community Discovery](https://mlsanity.com/paper/2102.03302/) (2021)
- [Inferential SIR-GN: Scalable Graph Representation Learning](https://mlsanity.com/paper/2111.04826/) (2021)
- [Digraphwave: Scalable Extraction of Structural Node Embeddings via Diffusion on Directed Graphs](https://mlsanity.com/paper/2207.10149/) (2022)

## Abstract (arXiv)

We study the problem of large-scale network embedding, which aims to learn latent representations for network mining applications. Previous research shows that 1) popular network embedding benchmarks, such as DeepWalk, are in essence implicitly factorizing a matrix with a closed form, and 2)the explicit factorization of such matrix generates more powerful embeddings than existing methods. However, directly constructing and factorizing this matrix---which is dense---is prohibitively expensive in terms of both time and space, making it not scalable for large networks. In this work, we present the algorithm of large-scale network embedding as sparse matrix factorization (NetSMF). NetSMF leverages theories from spectral sparsification to efficiently sparsify the aforementioned dense matrix, enabling significantly improved efficiency in embedding learning. The sparsified matrix is spectrally close to the original dense one with a theoretically bounded approximation error, which helps maintain the representation power of the learned embeddings. We conduct experiments on networks of various scales and types. Results show that among both popular benchmarks and factorization based methods, NetSMF is the only method that achieves both high efficiency and effectiveness. We show that NetSMF requires only 24 hours to generate effective embeddings for a large-scale academic collaboration network with tens of millions of nodes, while it would cost DeepWalk months and is computationally infeasible for the dense matrix factorization solution. The source code of NetSMF is publicly available (https://github.com/xptree/NetSMF).