# PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 50 references that are in the map.
- First posted on arXiv 5 Aug 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [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)
- [Generative Adversarial Networks: An Overview](https://mlsanity.com/paper/1710.07035/) (2017)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [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)
- [Anonymous Walk Embeddings](https://mlsanity.com/paper/1805.11921/) (2018)
- [Adversarial Training Methods for Network Embedding](https://mlsanity.com/paper/1908.11514/) (2019)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [Scalable Graph Embeddings via Sparse Transpose Proximities](https://mlsanity.com/paper/1905.07245/) (2019)
- [FREDE: Anytime Graph Embeddings](https://mlsanity.com/paper/2006.04746/) (2020)
- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Spectral Sparsification of Random-Walk Matrix Polynomials](https://mlsanity.com/paper/1502.03496/) (2015)
- [SketchNE: Embedding Billion-Scale Networks Accurately in One Hour](https://mlsanity.com/paper/2110.12782/) (2021)
- [Scalable and Effective Conductance-based Graph Clustering](https://mlsanity.com/paper/2211.12511/) (2022)

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

- [CoATA: Effective Co-Augmentation of Topology and Attribute for Graph Neural Networks](https://mlsanity.com/paper/2506.22299/) (2025)

## Abstract (arXiv)

Network embedding has numerous practical applications and has received extensive attention in graph learning, which aims at mapping vertices into a low-dimensional and continuous dense vector space by preserving the underlying structural properties of the graph. Many network embedding methods have been proposed, among which factorization of the Personalized PageRank (PPR for short) matrix has been empirically and theoretically well supported recently. However, several fundamental issues cannot be addressed. (1) Existing methods invoke a seminal Local Push subroutine to approximate textita single row or column of the PPR matrix. Thus, they have to execute n (n is the number of nodes) Local Push subroutines to obtain a provable PPR matrix, resulting in prohibitively high computational costs for large n. (2) The PPR matrix has limited power in capturing the structural similarity between vertices, leading to performance degradation. To overcome these dilemmas, we propose PSNE, an efficient spectral sParsification method for Scaling Network Embedding, which can fast obtain the embedding vectors that retain strong structural similarities. Specifically, PSNE first designs a matrix polynomial sparser to accelerate the calculation of the PPR matrix, which has a theoretical guarantee in terms of the Frobenius norm. Subsequently, PSNE proposes a simple but effective multiple-perspective strategy to enhance further the representation power of the obtained approximate PPR matrix. Finally, PSNE applies a randomized singular value decomposition algorithm on the sparse and multiple-perspective PPR matrix to get the target embedding vectors. Experimental evaluation of real-world and synthetic datasets shows that our solutions are indeed more efficient, effective, and scalable compared with ten competitors.