# Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank

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

## Key facts

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

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

- [Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection](https://mlsanity.com/paper/2212.12488/) (2022)
- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [Collaborative Graph Neural Networks for Attributed Network Embedding](https://mlsanity.com/paper/2307.11981/) (2023)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)
- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Non-Euclidean Mixture Model for Social Network Embedding](https://mlsanity.com/paper/2411.04876/) (2024)
- [Effective Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs](https://mlsanity.com/paper/2406.13369/) (2024)
- [Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling](https://mlsanity.com/paper/2105.09182/) (2021)
- [Distributed Graph Embedding with Information-Oriented Random Walks](https://mlsanity.com/paper/2303.15702/) (2023)
- [PGB: A PubMed Graph Benchmark for Heterogeneous Network Representation Learning](https://mlsanity.com/paper/2305.02691/) (2023)
- [Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds](https://mlsanity.com/paper/2306.08967/) (2023)
- [HUGE: Huge Unsupervised Graph Embeddings with TPUs](https://mlsanity.com/paper/2307.14490/) (2023)
- [PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding](https://mlsanity.com/paper/2408.02705/) (2024)
- [Learning Peer Influence Probabilities with Linear Contextual Bandits](https://mlsanity.com/paper/2510.19119/) (2025)
- [Boosting Graph Embedding on a Single GPU](https://mlsanity.com/paper/2110.10049/) (2021)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)
- [Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs](https://mlsanity.com/paper/2209.14825/) (2022)
- [Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework](https://mlsanity.com/paper/2211.02883/) (2022)
- [Understanding and Guiding Weakly Supervised Entity Alignment with Potential Isomorphism Propagation](https://mlsanity.com/paper/2402.03025/) (2024)
- [Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective](https://mlsanity.com/paper/2405.19649/) (2024)
- [Mitigating Structural Overfitting: A Distribution-Aware Rectification Framework for Missing Feature Imputation](https://mlsanity.com/paper/2512.06356/) (2025)
- [FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism](https://mlsanity.com/paper/2606.22180/) (2026)
- [Topology-induced Operators Reveal Complementary Graph Representations without Training](https://mlsanity.com/paper/2609.08152/) (2026)

## Abstract (arXiv)

Given an input graph G and a node v in G, homogeneous network embedding (HNE) maps the graph structure in the vicinity of v to a compact, fixed-dimensional feature vector. This paper focuses on HNE for massive graphs, e.g., with billions of edges. On this scale, most existing approaches fail, as they incur either prohibitively high costs, or severely compromised result utility. Our proposed solution, called Node-Reweighted PageRank (NRP), is based on a classic idea of deriving embedding vectors from pairwise personalized PageRank (PPR) values. Our contributions are twofold: first, we design a simple and efficient baseline HNE method based on PPR that is capable of handling billion-edge graphs on commodity hardware; second and more importantly, we identify an inherent drawback of vanilla PPR, and address it in our main proposal NRP. Specifically, PPR was designed for a very different purpose, i.e., ranking nodes in G based on their relative importance from a source node's perspective. In contrast, HNE aims to build node embeddings considering the whole graph. Consequently, node embeddings derived directly from PPR are of suboptimal utility. The proposed NRP approach overcomes the above deficiency through an effective and efficient node reweighting algorithm, which augments PPR values with node degree information, and iteratively adjusts embedding vectors accordingly. Overall, NRP takes O(mlogn) time and O(m) space to compute all node embeddings for a graph with m edges and n nodes. Our extensive experiments that compare NRP against 18 existing solutions over 7 real graphs demonstrate that NRP achieves higher result utility than all the solutions for link prediction, graph reconstruction and node classification, while being up to orders of magnitude faster. In particular, on a billion-edge Twitter graph, NRP terminates within 4 hours, using a single CPU core.