# Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 57 references that are in the map.
- First posted on arXiv 30 May 2024.

## Builds on (most cited first, 30 of 31)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (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)
- [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)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [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)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks](https://mlsanity.com/paper/1508.00200/) (2015)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [Bipartite Graph Embedding via Mutual Information Maximization](https://mlsanity.com/paper/2012.05442/) (2020)
- [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)
- [InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity](https://mlsanity.com/paper/2006.00094/) (2020)
- [Personalized PageRank to a Target Node, Revisited](https://mlsanity.com/paper/2006.11876/) (2020)
- [On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximation](https://mlsanity.com/paper/2306.09104/) (2023)
- [Scalable Graph Embeddings via Sparse Transpose Proximities](https://mlsanity.com/paper/1905.07245/) (2019)
- [Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push](https://mlsanity.com/paper/2101.03652/) (2021)
- [Personalized PageRank Estimation and Search: A Bidirectional Approach](https://mlsanity.com/paper/1507.05999/) (2015)
- [DeepWalking Backwards: From Embeddings Back to Graphs](https://mlsanity.com/paper/2102.08532/) (2021)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Finding MNEMON: Reviving Memories of Node Embeddings](https://mlsanity.com/paper/2204.06963/) (2022)
- [Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries](https://mlsanity.com/paper/1908.10583/) (2019)

## Abstract (arXiv)

Node embedding learns low-dimensional vectors for nodes in the graph. Recent state-of-the-art embedding approaches take Personalized PageRank (PPR) as the proximity measure and factorize the PPR matrix or its adaptation to generate embeddings. However, little previous work analyzes what information is encoded by these approaches, and how the information correlates with their superb performance in downstream tasks. In this work, we first show that state-of-the-art embedding approaches that factorize a PPR-related matrix can be unified into a closed-form framework. Then, we study whether the embeddings generated by this strategy can be inverted to better recover the graph topology information than random-walk based embeddings. To achieve this, we propose two methods for recovering graph topology via PPR-based embeddings, including the analytical method and the optimization method. Extensive experimental results demonstrate that the embeddings generated by factorizing a PPR-related matrix maintain more topological information, such as common edges and community structures, than that generated by random walks, paving a new way to systematically comprehend why PPR-based node embedding approaches outperform random walk-based alternatives in various downstream tasks. To the best of our knowledge, this is the first work that focuses on the interpretability of PPR-based node embedding approaches.