Source-linked AI summary
NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Chi Wang, Kuansan Wang, Jie Tang
TL;DR
Large-scale network embedding needs effective representations without explicitly constructing and factorizing the dense matrix underlying methods such as DeepWalk. NetSMF sparsifies that matrix using spectral techniques and randomized factorization, achieving strong effectiveness with substantially improved scalability and bounded approximation error.
Problem
The dense matrix underlying explicit network embedding factorization is prohibitively expensive to construct and factorize for large networks.
Method
NetSMF uses spectral sparsification to create a sparse matrix spectrally close to NetMF, then applies randomized singular value decomposition to obtain embeddings.
Results
NetSMF outperforms DeepWalk and node2vec by up to 34% and LINE by up to 100% on multi-label vertex classification while embedding a 67-million-vertex network in 24 hours.
Takeaways & Limitations
NetSMF combines the representation power of dense matrix factorization with efficiency suitable for very large-scale network embedding.
Takeaways & Limitations
The current single-machine implementation limits the number of samples for large networks, motivating a future multi-machine solution.
Abstract
from arXiv · showhide
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).
1 INTRODUCTION
Network embedding learns latent representations for network objects, but explicit factorization can be prohibitively expensive at scale. NetSMF sparsifies the dense NetMF matrix, combines efficiency with theoretical guarantees, and preserves strong embedding effectiveness.
- DeepWalk and LINE can be viewed as implicitly factorizing a closed-form matrix, while NetMF explicitly factorizes it for more effective embeddings.
- The dense NetMF matrix has O(n^2) non-zeros in small-world networks, making exact construction and factorization impractical for large networks.
- NetSMF sparsifies the dense NetMF matrix, then factorizes the sparse approximation to reduce construction and factorization costs.
- NetSMF achieves orders-of-magnitude speedups over NetMF on million-scale or larger networks while maintaining competitive vertex-classification performance.
- NetSMF embeds a 67-million-vertex, 895-million-edge academic network on one server in 24 hours, whereas DeepWalk and node2vec would take months and NetMF is infeasible.
- NetSMF maintains the dense solution’s representation power, outperforming DeepWalk and node2vec by up to 34% and LINE by up to 100% on multi-label vertex classification.
- The sparse matrix is spectrally close to the exact NetMF matrix, with theoretically bounded approximation error.
2 PRELIMINARIES
Network embedding maps vertices to low-dimensional vectors that capture structural properties for downstream tasks. DeepWalk motivates NetMF through an implicit matrix factorization, but the resulting matrix is dense and difficult to scale.
- Network embedding maps each vertex to a d-dimensional vector that captures structural properties such as community structure.
- DeepWalk generates random-walk vertex sequences and applies skip-gram to learn latent representations.
- A theoretical study shows that DeepWalk implicitly and asymptotically factorizes a matrix derived from the random-walk process.
- NetMF explicitly factorizes this matrix and yields higher vertex-classification accuracy than DeepWalk and LINE.
- Because most nearby vertex pairs are reachable in small-world networks, the NetMF matrix becomes dense with O(n^2) non-zeros and is impractical to construct and factorize at scale.
3 NETWORK EMBEDDING AS SPARSE MATRIX FACTORIZATION (NetSMF)
NetSMF approximates the dense NetMF matrix through random-walk matrix-polynomial sparsification. It constructs a sparse, spectrally close matrix and efficiently factorizes it to produce network embeddings.
- NetSMF uses random-walk matrix-polynomial sparsification to construct and factorize a sparse approximation of the dense NetMF matrix.
- Spectral similarity bounds the quadratic forms of two network Laplacians within factors of 1 − ϵ and 1 + ϵ.
- The sparsification theorem constructs a (1 + ϵ)-spectral sparsifier with O(n lognϵ^-2) non-zeros in O(T^2mϵ^-2 log^2 n) time.
- NetSMF replaces the matrix’s Laplacian component with its sparsifier, producing a sparse matrix with the same order of magnitude of non-zeros.
- The algorithm comprises random-walk sparsification, NetMF sparsifier construction, and truncated singular value decomposition.
7 end
NetSMF replaces the dense NetMF factorization with a sparse, spectrally close approximation and randomized SVD. Its design targets lower construction and factorization costs while preserving theoretical approximation guarantees and enabling parallel execution.
- Sparse matrix construction: NetSMF samples paths to construct a sparse graph and then derives a NetMF matrix sparsifier without changing its order of magnitude of non-zeros.The sparsifier has O(M) non-zeros after merging sampled edges and computing the graph Laplacian.
- Truncated singular value decomposition: Randomized SVD factorizes the sparse matrix by projecting it into a low-dimensional space and applying traditional SVD to a d × d matrix.This avoids exact SVD on the full sparsifier and can help select embedding dimensionality from singular values.
- Connection to NetMF: NetSMF approximates NetMF with a sparse matrix, whereas NetMF uses a dense matrix that creates additional space and computation challenges.The sparse approximation is designed to retain spectral closeness while reducing construction and factorization costs.
- Example: 1.4 × 10^11 non-zeros is an upper bound for the example sparsifier, whose density is approximately 14%, compared with 10^12 non-zeros for dense NetMF.Increasing the approximation factor can further reduce NetSMF sparsity, unlike NetMF.
- Approximation error analysis: The approximation analysis assumes ϵ < 0.5 and provides bounds without assumptions on the input network.Tighter bounds may be possible under assumptions such as bounded minimum degree or a specified random graph model.
- Parallelization: Independent path sampling allows NetSMF steps to be parallelized, supporting scaling to very large networks.Multiple workers can process subsets of samples, provided they can access the network data efficiently.
4 EXPERIMENTS
Experiments evaluate NetSMF on five networks spanning small social, biological, and large academic graphs, comparing predictive performance, efficiency, and scalability. NetSMF provides competitive or superior classification performance while substantially reducing runtime for large networks.
- Datasets: Experiments evaluate multi-label vertex classification on five networks, including four widely used smaller datasets and the 67-million-vertex OAG co-authorship network.The datasets cover BlogCatalog, PPI, Flickr, YouTube, and OAG.
- Predictive performance: NetSMF and NetMF consistently achieve the best prediction results among the compared methods, with NetSMF sometimes outperforming NetMF.On Flickr, NetSMF exceeds NetMF by 3.6% Macro-F1 and 5.3% Micro-F1 on average.
- Efficiency and scalability: NetSMF requires 24 hours on OAG, while DeepWalk and node2vec may require months and NetMF cannot complete because of excessive resource demands.The OAG network contains 67,768,244 authors and 895,368,962 collaboration edges.
- Predictive performance: NetSMF outperforms DeepWalk by 7–34% in Micro-F1 and 5–25% in Macro-F1 on BlogCatalog, PPI, and Flickr.It achieves comparable results to DeepWalk on YouTube.
- Efficiency and scalability: NetSMF is the only compared method reported to achieve both high efficiency and effectiveness for billion-scale networks, including OAG with 0.9 billion edges.LINE is efficient but has the worst prediction performance, while NetMF has high effectiveness but substantially greater time and space costs.
- Parameter analysis: Increasing the number of non-zeros improves prediction performance, while increasing threads reduces Flickr runtime from 12 hours to 48 minutes with 30 threads.The reported parallel speedup is 15×, compared with an ideal 30×.
5 RELATED WORK
Related work spans skip-gram, deep-learning, and matrix-factorization approaches, alongside efforts to scale embedding computation. NetSMF applies spectral graph sparsification to approximate the dense NetMF matrix efficiently.
- Network embedding research includes skip-gram, deep-learning, and matrix-factorization methods for learning representations used in downstream applications.
- Distributed Skip-Gram Model: Distributed skip-gram approaches accelerate training by replicating or partitioning embedding parameters across workers.
- Efficient Matrix Factorization: NetMF-related factorization methods face high computation costs from dense matrices and difficulty approximating element-wise logarithms.
- Spectral Graph Sparsification: Spectral graph sparsification approximates dense graphs with sparse ones for use in scientific computing, machine learning, and data mining.
- Spectral Graph Sparsification: NetSMF incorporates spectral sparsification into network embedding to approximate and analyze the random-walk matrix-polynomial in NetMF.
6 CONCLUSION
The paper presents NetSMF as a sparse matrix-factorization approach for efficient large-scale network embedding. It combines scalable construction with spectral approximation guarantees and reports strong effectiveness across benchmark comparisons.
- NetSMF sparsifies the dense NetMF matrix so both construction and factorization become practical for very large networks.The paper reports embedding the Open Academic Graph in 24 hours, whereas dense NetMF is computationally intractable.
- The sparsified matrix is theoretically spectrally close to the original NetMF matrix with a bounded approximation error.
- NetSMF embeddings are reported as effective as NetMF embeddings and superior to DeepWalk, LINE, and node2vec.
- Future Work: The current implementation is single-machine, limiting the number of samples available for large networks and motivating a future multi-machine solution.
- Future Work: Future work includes embeddings for large-scale directed, dynamic, and heterogeneous networks and connections between matrix factorization and graph convolutional methods.
APPENDIX
The appendix establishes theoretical tools for analyzing NetSMF’s sparsifier and its approximation of the NetMF matrix. It also gives bounds for singular-value errors and explains path-sampling weights used in sparsifier construction.
- For symmetric matrices, singular values equal the absolute values of eigenvalues, supporting the appendix’s spectral analysis.
- Courant–Fisher characterizes ordered eigenvalues of a symmetric matrix through a min–max variational expression.
- The normalized sparsifier and original Laplacian differ in singular values by a bound smaller than 4ϵ.
- The normalized Laplacian has eigenvalues in [0, 2), while its spectral sparsifier satisfies a quadratic-form approximation bound.
- Theorem 2 bounds each singular value of the NetMF-matrix approximation error by 4ϵ√(d_i d_min).
- After sampling a length-r path, NetSMF adds an edge to the sparsifier with weight 2r^m M/Z(p).