Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank

Summary: NRP converts personalized PageRank into scalable homogeneous embeddings via iterative degree-based reweighting, correcting PPR’s source-centric bias. It achieves O(m log n) time and O(m) space, outperforming 18 methods while scaling to billion-edge graphs on one CPU. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: ha0b6c99059b6118f
Venue: VLDB
Year: 2020
Pagerank: 9.512431e-05
Overall Rank: 1,843 | 87.65%
DOI: 10.14778/3377369.3377376
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Renchi Yang (Nanyang Technological University)
2. Jieming Shi (National University of Singapore)
3. Xiaokui Xiao (National University of Singapore)
4. Yin Yang (Hamad Bin Khalifa University)
5. Sourav S. Bhowmick (Nanyang Technological University)

BibTeX Citation

@article{yang_vldb20,
        title = {{Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank}},
        author = {Yang, Renchi and Shi, Jieming and Xiao, Xiaokui and Yang, Yin and Bhowmick, Sourav S.},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {5},
        pages = {670--683},
        doi = {10.14778/3377369.3377376},
        url = {https://doi.org/10.14778/3377369.3377376},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,105	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.6278115e-05
3,910	FREDE: Anytime Graph Embeddings	2021	VLDB	6.9119982e-05
3,926	Scaling Attributed Network Embedding to Massive Graphs	2021	VLDB	6.9030847e-05
3,988	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.8626164e-05
4,654	LightNE: A Lightweight Graph Processing System for Network Embedding	2021	SIGMOD	6.4694415e-05
5,579	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	6.0611875e-05
5,741	Efficient Tree-SVD for Subset Node Embedding over Large Dynamic Graphs	2023	SIGMOD	5.9939789e-05
6,097	On Graph Representation for Attributed Hypergraph Clustering	2025	SIGMOD	5.8699655e-05
6,339	EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs	2023	SIGMOD	5.7918126e-05
8,041	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB	5.385603e-05
8,440	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.3148581e-05
10,295	Efficient High-Quality Clustering for Large Bipartite Graphs	2024	SIGMOD	5.031399e-05
10,456	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	4.9605343e-05
10,897	FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism	2026	VLDB	4.9605343e-05
10,906	Sankofa: Online Query-adaptive Dynamic Graph Summaries	2026	VLDB	4.9605343e-05
11,419	Effective and Efficient Attributed Hypergraph Embedding on Nodes and Hyperedges	2025	VLDB	4.9605343e-05
11,516	Efficient Graph Embedding Generation and Update for Large-Scale Temporal Graph	2025	VLDB	4.9605343e-05
11,757	Effective and Efficient PageRank-based Positioning for Graph Visualization	2023	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,188	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.8879472e-05
3,657	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	7.1105244e-05
4,097	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.7946571e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,404	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
2	8,041	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB
3	4,097	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD
4	5,244	Edge-based Local Push for Personalized PageRank	2022	VLDB
5	2,382	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
6	3,657	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB
7	4,630	On the Embeddability of Random Walk Distances	2013	VLDB
8	1,303	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
9	5,579	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD
10	3,926	Scaling Attributed Network Embedding to Massive Graphs	2021	VLDB