{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:52Z","timestamp":1778807872024,"version":"3.51.4"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,9,22]]},"abstract":"<jats:p>\n            Personalized PageRank (PPR) is a fundamental graph proximity measure with a wide range of applications. The single-source Personalized PageRank (SSPPR) query aims to compute the PPR values for all nodes from a given source node. Due to the high computational cost of exact SSPPR computation, most existing solutions focus on approximate queries with accuracy guarantees. The state-of-the-art approaches for approximate SSPPR queries are index-based and are typically designed for a single, fixed value of \u03b1. However, real-world applications often require handling multiple values of \u03b1, and current index-based methods struggle to adapt to varying values of \u03b1 without rebuilding the index. To address this limitation, we propose a novel and efficient index approach for SSPPR queries that supports all values of \u03b1. A striking feature of our approach is that it stores only a single index for all possible values of \u03b1. This is achieved by leveraging the loop-erased \u03b1-random walk interpretation of PPR and constructing a stack-style\n            <jats:italic toggle=\"yes\">meta-index<\/jats:italic>\n            with a sufficiently large damping factor \u0101, denoted as StackIndex. Then, we develop a novel technique to efficiently transform StackIndex into a\n            <jats:italic toggle=\"yes\">new index<\/jats:italic>\n            for any specified damping factor \u03b1, without the need to rebuild the index. We show that our index construction algorithm requires around\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\u03c9\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            ) time and\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\u03c9\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            ) space to ensure approximation quality, where \u03c9 and\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            represent the sample size and the number of nodes in the graph, respectively. We also develop an index maintenance technique to update our StackIndex when handling dynamic graphs with edge insertions and deletions. Extensive experiments on 5 large real-world graphs demonstrate that StackIndex offers substantial speedups over previous index-based methods for PPR queries with different \u03b1 while maintaining the same accuracy guarantee.\n          <\/jats:p>","DOI":"10.1145\/3749176","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-0303-4902","authenticated-orcid":false,"given":"Junjie","family":"Zhou","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5808-3131","authenticated-orcid":false,"given":"Meihao","family":"Liao","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2194-8146","authenticated-orcid":false,"given":"Longlong","family":"Lin","sequence":"additional","affiliation":[{"name":"Southwest University, Chongqing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"150","article-title":"Local computation of pagerank contributions","author":"Andersen Reid","year":"2007","unstructured":"Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcraft, Vahab S Mirrokni, and Shang-Hua Teng. 2007. Local computation of pagerank contributions. In WAW. 150-165.","journal-title":"WAW."},{"key":"e_1_2_1_2_1","first-page":"475","article-title":"Local graph partitioning using pagerank vectors","author":"Andersen Reid","year":"2006","unstructured":"Reid Andersen, Fan Chung, and Kevin Lang. 2006. Local graph partitioning using pagerank vectors. In FOCS. 475-486.","journal-title":"FOCS."},{"key":"e_1_2_1_3_1","volume-title":"Monte Carlo methods in PageRank computation: When one iteration is sufficient","author":"Avrachenkov Konstantin","year":"2007","unstructured":"Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, and Natalia Osipova. 2007b. Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM, Vol. 45, 2 (2007), 890-904."},{"key":"e_1_2_1_4_1","first-page":"16","article-title":"Distribution of PageRank mass among principle components of the web","author":"Avrachenkov Konstantin","year":"2007","unstructured":"Konstantin Avrachenkov, Nelly Litvak, and Kim Son Pham. 2007a. Distribution of PageRank mass among principle components of the web. In WAW. 16-28.","journal-title":"WAW."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129300"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135955"},{"key":"e_1_2_1_7_1","first-page":"2464","article-title":"Scaling graph neural networks with approximate pagerank","author":"Bojchevski Aleksandar","year":"2020","unstructured":"Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek R\u00f3zemberczki, Michal Lukasik, and Stephan G\u00fcnnemann. 2020. Scaling graph neural networks with approximate pagerank. In KDD. 2464-2473.","journal-title":"KDD."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi Massimo Santini and Sebastiano Vigna. 2005. PageRank as a Function of the Damping Factor. In WWW. 557.","DOI":"10.1145\/1060745.1060827"},{"key":"e_1_2_1_9_1","unstructured":"Paolo Boldi Massimo Santini and Sebastiano Vigna. 2007. A Deeper Investigation of PageRank as a Function of the Damping Factor. (2007) 19 pages 408817 bytes."},{"key":"e_1_2_1_10_1","unstructured":"Eli Chien Jianhao Peng Pan Li and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In ICLR."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/asmb.656"},{"key":"e_1_2_1_12_1","first-page":"15","article-title":"Efficient Personalized Pagerank with Accuracy Assurance","author":"Fujiwara Yasuhiro","year":"2012","unstructured":"Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro, Hiroaki Shiokawa, and Makoto Onizuka. 2012. Efficient Personalized Pagerank with Accuracy Assurance. In KDD. 15-23.","journal-title":"KDD."},{"key":"e_1_2_1_13_1","first-page":"381","article-title":"Tracking the random surfer: empirically measured teleportation parameters in PageRank","author":"Gleich David F","year":"2010","unstructured":"David F Gleich, Paul G Constantine, Abraham D Flaxman, and Asela Gunawardana. 2010. Tracking the random surfer: empirically measured teleportation parameters in PageRank. In WWW. 381-390.","journal-title":"WWW."},{"key":"e_1_2_1_14_1","first-page":"576","article-title":"Combating web spam with trustrank","author":"Gy\u00f6ngyi Zolt\u00e1n","year":"2004","unstructured":"Zolt\u00e1n Gy\u00f6ngyi, Hector Garcia-Molina, and Jan Pedersen. 2004. Combating web spam with trustrank. In VLDB. 576-587.","journal-title":"VLDB."},{"key":"e_1_2_1_15_1","volume-title":"PageRank Algorithm Based on Dynamic Damping Factor. In 2023 International Conference on Cyber-Physical Social Intelligence (ICCSI). 381-386","author":"HaoLin Zheng","year":"2023","unstructured":"Zheng HaoLin, Hu Jin, and Li WeiKai. 2023. PageRank Algorithm Based on Dynamic Damping Factor. In 2023 International Conference on Cyber-Physical Social Intelligence (ICCSI). 381-386."},{"key":"e_1_2_1_16_1","first-page":"784","article-title":"Topic-Sensitive PageRank","volume":"15","author":"Haveliwala Taher H.","year":"2003","unstructured":"Taher H. Haveliwala. 2003. Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search. TKDE, Vol. 15, 4 (2003), 784-796.","journal-title":"A Context-Sensitive Ranking Algorithm for Web Search. TKDE"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i8.28693"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588705"},{"key":"e_1_2_1_19_1","first-page":"271","article-title":"Scaling personalized web search","author":"Jeh Glen","year":"2003","unstructured":"Glen Jeh and Jennifer Widom. 2003. Scaling personalized web search. In WWW. 271-279.","journal-title":"WWW."},{"key":"e_1_2_1_20_1","first-page":"789","article-title":"BePI","author":"Jung Jinhong","year":"2017","unstructured":"Jinhong Jung, Namyong Park, Sael Lee, and U Kang. 2017. BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart. In SIGMOD. 789-804.","journal-title":"In SIGMOD."},{"key":"e_1_2_1_21_1","unstructured":"Johannes Klicpera Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2019a. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In ICLR."},{"key":"e_1_2_1_22_1","volume-title":"7th International Conference on Learning Representations, ICLR 2019","author":"Klicpera Johannes","year":"2019","unstructured":"Johannes Klicpera, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2019b. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. https:\/\/openreview.net\/forum?id=H1gL-2A9Ym"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589305"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589305"},{"key":"e_1_2_1_26_1","first-page":"2048","article-title":"Efficient personalized pagerank computation: A spanning forests sampling based approach","author":"Liao Meihao","year":"2022","unstructured":"Meihao Liao, Rong-Hua Li, Qiangqiang Dai, and Guoren Wang. 2022. Efficient personalized pagerank computation: A spanning forests sampling based approach. In SIGMOD. 2048-2061.","journal-title":"SIGMOD."},{"key":"e_1_2_1_27_1","first-page":"913","article-title":"Index-free approach with theoretical guarantee for efficient random walk with restart query","author":"Lin Dandan","year":"2020","unstructured":"Dandan Lin, Raymond Chi-Wing Wong, Min Xie, and Victor Junqiu Wei. 2020. Index-free approach with theoretical guarantee for efficient random walk with restart query. In ICDE. 913-924.","journal-title":"ICDE."},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"Damping Effect on Pagerank Distribution","author":"Liu Tiancheng","year":"2018","unstructured":"Tiancheng Liu, Yuchen Qian, Xi Chen, and Xiaobai Sun. 2018. Damping Effect on Pagerank Distribution. In HPEC. 1-11.","journal-title":"HPEC."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732978"},{"key":"e_1_2_1_31_1","first-page":"875","article-title":"Efficient pagerank tracking in evolving networks","author":"Ohsaka Naoto","year":"2015","unstructured":"Naoto Ohsaka, Takanori Maehara, and Ken ichi Kawarabayashi. 2015. Efficient pagerank tracking in evolving networks. In KDD. 875-884.","journal-title":"KDD."},{"key":"e_1_2_1_32_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1998. The pagerank citation ranking: Bring order to the web. In WWW."},{"key":"e_1_2_1_33_1","first-page":"1633","article-title":"Google Pagerank Algorithm","volume":"28","author":"Saber Ali Ali","year":"2022","unstructured":"Ali Ali Saber, Aso Kamaran Omer, and Noor Kaylan Hamid. 2022. Google Pagerank Algorithm: Using Efficient Damping Factor. Vol. 28, 3 (2022), 1633-1639.","journal-title":"Using Efficient Damping Factor."},{"key":"e_1_2_1_34_1","first-page":"1571","article-title":"BEAR","author":"Shin Kijung","year":"2015","unstructured":"Kijung Shin, Jinhong Jung, Sael Lee, and U. Kang. 2015. BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs. In SIGMOD. 1571-1585.","journal-title":"In SIGMOD."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994522"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Atul Kumar Srivastava Rakhi Garg and P. K. Mishra. 2017. Discussion on Damping Factor Value in PageRank Computation. Vol. 9 9 (2017) 19.","DOI":"10.5815\/ijisa.2017.09.03"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2013.07.021"},{"key":"e_1_2_1_38_1","first-page":"657","article-title":"Personalized pagerank to a target node, revisited","author":"Wang Hanzhi","year":"2020","unstructured":"Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, and Zengfeng Huang. 2020. Personalized pagerank to a target node, revisited. In KDD. 657-667.","journal-title":"KDD."},{"key":"e_1_2_1_39_1","first-page":"911","article-title":"Revisiting Local Computation of PageRank","author":"Wang Hanzhi","year":"2024","unstructured":"Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, and Mingji Yang. 2024. Revisiting Local Computation of PageRank: Simple and Optimal. In STOC. 911-922.","journal-title":"Simple and Optimal. In STOC."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_1_41_1","first-page":"505","article-title":"FORA: simple and effective approximate single-source personalized pagerank","author":"Wang Sibo","year":"2017","unstructured":"Sibo Wang, Renchi Yang, Xiaokui Xiao, Zhewei Wei, and Yin Yang. 2017. FORA: simple and effective approximate single-source personalized pagerank. In KDD. 505-514.","journal-title":"KDD."},{"key":"e_1_2_1_42_1","first-page":"1","article-title":"Approximating Single-Source Personalized PageRank with Absolute Error Guarantees","volume":"290","author":"Wei Zhewei","year":"2024","unstructured":"Zhewei Wei, Ji-Rong Wen, and Mingji Yang. 2024. Approximating Single-Source Personalized PageRank with Absolute Error Guarantees. In ICDT, Vol. 290. 9:1-9:19.","journal-title":"ICDT"},{"key":"e_1_2_1_43_1","first-page":"296","article-title":"Generating random spanning trees more quickly than the cover time","author":"Wilson David Bruce","year":"1996","unstructured":"David Bruce Wilson. 1996. Generating random spanning trees more quickly than the cover time. In STOC. 296-303.","journal-title":"STOC."},{"key":"e_1_2_1_44_1","first-page":"1996","article-title":"Unifying the global and local approaches: An efficient power iteration with forward push","author":"Wu Hao","year":"2021","unstructured":"Hao Wu, Junhao Gan, Zhewei Wei, and Rui Zhang. 2021. Unifying the global and local approaches: An efficient power iteration with forward push. In SIGMOD. 1996-2008.","journal-title":"SIGMOD."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3376000"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319886"},{"key":"e_1_2_1_47_1","first-page":"64","article-title":"GSD-GNN","author":"Yu Yunfeng","year":"2024","unstructured":"Yunfeng Yu, Longlong Lin, Qiyu Liu, Zeli Wang, Xi Ou, and Tao Jia. 2024. GSD-GNN: Generalizable and Scalable Algorithms for Decoupled Graph Neural Networks. In ICMR. 64-72.","journal-title":"In ICMR."},{"key":"e_1_2_1_48_1","first-page":"1315","article-title":"Approximate personalized pagerank on dynamic graphs","author":"Zhang Hongyang","year":"2016","unstructured":"Hongyang Zhang, Peter Lofgren, and Ashish Goel. 2016. Approximate personalized pagerank on dynamic graphs. In KDD. 1315-1324.","journal-title":"KDD."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645637"},{"key":"e_1_2_1_50_1","volume-title":"One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor. Full version: https:\/\/github.com\/zjjyyyk\/stackindex","author":"Zhou Junjie","year":"2026","unstructured":"Junjie Zhou, Meihao Liao, Rong-Hua Li, and Guoren Wang. 2026. One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor. Full version: https:\/\/github.com\/zjjyyyk\/stackindex (2026)."},{"key":"e_1_2_1_51_1","volume-title":"Kevin Chen-Chuan Chang, and Jing Ying","author":"Zhu Fanwei","year":"2013","unstructured":"Fanwei Zhu, Yuan Fang, Kevin Chen-Chuan Chang, and Jing Ying. 2013. Incremental and Accuracy-Aware Personalized Pagerank through Scheduled Approximation. (2013)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T16:21:02Z","timestamp":1758903662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749176"],"URL":"https:\/\/doi.org\/10.1145\/3749176","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}