{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:16:04Z","timestamp":1780766164696,"version":"3.54.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>\n            Personalized PageRank (PPR) is a popular node proximity metric in graph mining and network research. A single-source PPR (SSPPR) query asks for the PPR value of each node on the graph. Due to its importance and wide applications, decades of efforts have been devoted to the efficient processing of SSPPR queries. Among existing algorithms,\n            <jats:italic>LocalPush<\/jats:italic>\n            is a fundamental method for SSPPR queries and serves as a cornerstone for subsequent algorithms. In\n            <jats:italic>LocalPush<\/jats:italic>\n            , a\n            <jats:italic>push<\/jats:italic>\n            operation is a crucial primitive operation, which distributes the probability at a node\n            <jats:italic>u<\/jats:italic>\n            to ALL\n            <jats:italic>u<\/jats:italic>\n            's neighbors via the corresponding edges. Although this\n            <jats:italic>push<\/jats:italic>\n            operation works well on\n            <jats:italic>unweighted<\/jats:italic>\n            graphs, unfortunately, it can be rather inefficient on\n            <jats:italic>weighted<\/jats:italic>\n            graphs. In particular, on\n            <jats:italic>unbalanced<\/jats:italic>\n            weighted graphs where only a few of these edges take the majority of the total weight among them, the\n            <jats:italic>push<\/jats:italic>\n            operation would have to distribute \"insignificant\" probabilities along those edges which just take the minor weights, resulting in expensive overhead.\n          <\/jats:p>\n          <jats:p>\n            To resolve this issue, in this paper, we propose the\n            <jats:italic>EdgePush<\/jats:italic>\n            algorithm, a novel method for computing SSPPR queries on weighted graphs.\n            <jats:italic>EdgePush<\/jats:italic>\n            decomposes the aforementioned push operations in\n            <jats:italic>edge-based push<\/jats:italic>\n            , allowing the algorithm to operate at the edge level granularity. As a result, it can flexibly distribute the probabilities according to edge weights. Furthermore, our\n            <jats:italic>EdgePush<\/jats:italic>\n            allows a fine-grained termination threshold for each individual edge, leading to a superior complexity over\n            <jats:italic>LocalPush.<\/jats:italic>\n            Notably, we prove that\n            <jats:italic>EdgePush<\/jats:italic>\n            improves the theoretical query cost of\n            <jats:italic>LocalPush<\/jats:italic>\n            by an order of up to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) when the graph's weights are\n            <jats:italic>unbalanced.<\/jats:italic>\n            Our experimental results demonstrate that\n            <jats:italic>EdgePush<\/jats:italic>\n            significantly outperforms state-of-the-art baselines in terms of query efficiency on large motif-based and real-world weighted graphs.\n          <\/jats:p>","DOI":"10.14778\/3523210.3523216","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:21Z","timestamp":1655936601000},"page":"1376-1389","source":"Crossref","is-referenced-by-count":11,"title":["Edge-based local push for personalized PageRank"],"prefix":"10.14778","volume":"15","author":[{"given":"Hanzhi","family":"Wang","sequence":"first","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Junhao","family":"Gan","sequence":"additional","affiliation":[{"name":"University of Melbourne, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji-Rong","family":"Wen","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. https:\/\/arxiv.org\/pdf\/2203.07937.pdf.  [n.d.]. https:\/\/arxiv.org\/pdf\/2203.07937.pdf."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. https:\/\/blockchair.com.  [n.d.]. https:\/\/blockchair.com."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. http:\/\/snap.stanford.edu\/data.  [n.d.]. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. http:\/\/law.di.unimi.it\/datasets.php.  [n.d.]. http:\/\/law.di.unimi.it\/datasets.php."},{"key":"e_1_2_1_5_1","unstructured":"[n.d.]. http:\/\/www.cs.cornell.edu\/~arb\/data\/.  [n.d.]. http:\/\/www.cs.cornell.edu\/~arb\/data\/."},{"key":"e_1_2_1_6_1","unstructured":"[n.d.]. https:\/\/gz.blockchair.com\/bitcoin-cash\/transactions\/.  [n.d.]. https:\/\/gz.blockchair.com\/bitcoin-cash\/transactions\/."},{"key":"e_1_2_1_7_1","unstructured":"[n.d.]. http:\/\/snap.stanford.edu\/mappr\/code.html.  [n.d.]. http:\/\/snap.stanford.edu\/mappr\/code.html."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77004-6_12"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1451983.1452000"},{"key":"e_1_2_1_10_1","volume-title":"Lang","author":"Andersen Reid","year":"2006","unstructured":"Reid Andersen , Fan R. K. Chung , and Kevin J . Lang . 2006 . Local Graph Partitioning using PageRank Vectors. In FOCS. 475--486. Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. 2006. Local Graph Partitioning using PageRank Vectors. In FOCS. 475--486."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935914"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403296"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_17_1","volume-title":"Scalable Graph Neural Networks via Bidirectional Propagation. arXiv preprint arXiv.2010.15421","author":"Chen Ming","year":"2020","unstructured":"Ming Chen , Zhewei Wei , Bolin Ding , Yaliang Li , Ye Yuan , Xiaoyong Du , and Ji-Rong Wen . 2020. Scalable Graph Neural Networks via Bidirectional Propagation. arXiv preprint arXiv.2010.15421 ( 2020 ). Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. 2020. Scalable Graph Neural Networks via Bidirectional Propagation. arXiv preprint arXiv.2010.15421 (2020)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26784-5_14"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.07.013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339729"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1214-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339538"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020430"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3099023.3099066"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461554"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_30_1","unstructured":"Johannes Klicpera Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2019. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In ICLR.  Johannes Klicpera Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2019. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In ICLR."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623706"},{"key":"e_1_2_1_32_1","volume-title":"The Art of computer programming,Volume3: Sorting and searching","author":"Knuth Donald E","year":"1973","unstructured":"Donald E Knuth . 1998. The Art of computer programming,Volume3: Sorting and searching ( 1973 ). Google Scholar Google Scholar Digital Library Digital Library ( 1998). Donald E Knuth. 1998. The Art of computer programming,Volume3: Sorting and searching (1973). Google Scholar Google Scholar Digital Library Digital Library (1998)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371823"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110044"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_36_1","volume-title":"Index-Free Approach with Theoretical Guarantee for Efficient Random Walk with Restart Query. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 913--924","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 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 913--924 . 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 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 913--924."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313555"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26784-5_13"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_1_41_1","volume-title":"Personalized pagerank to a target node. arXiv preprint arXiv 1304.4658","author":"Lofgren Peter","year":"2013","unstructured":"Peter Lofgren and Ashish Goel . 2013. Personalized pagerank to a target node. arXiv preprint arXiv 1304.4658 ( 2013 ). Peter Lofgren and Ashish Goel. 2013. Personalized pagerank to a target node. arXiv preprint arXiv 1304.4658 (2013)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623745"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014496"},{"key":"e_1_2_1_44_1","unstructured":"Andrew Y Ng Michael I Jordan and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems. 849--856.  Andrew Y Ng Michael I Jordan and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems. 849--856."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783297"},{"key":"e_1_2_1_46_1","unstructured":"Lawrence Page Sergey Bring Rajeev Motwani and Terry Wino grad. 1999. The PageRank citation ranking: bringing order to the web. (1999).  Lawrence Page Sergey Bring Rajeev Motwani and Terry Wino grad. 1999. The PageRank citation ranking: bringing order to the web. (1999)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35668-1_2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Daniel A Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning graph sparsification and solving linear systems. In STOC. 81--90.  Daniel A Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning graph sparsification and solving linear systems. In STOC. 81--90.","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_49_1","volume-title":"The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities","author":"Steele J Michael","unstructured":"J Michael Steele . 2004. The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities . Cambridge University Press . J Michael Steele. 2004. The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities. Cambridge University Press."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.00827"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403108"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196920"},{"key":"e_1_2_1_56_1","volume-title":"Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push. arXiv preprint arXiv:2101.03652","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. arXiv preprint arXiv:2101.03652 ( 2021 ). Hao Wu, Junhao Gan, Zhewei Wei, and Rui Zhang. 2021. Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push. arXiv preprint arXiv:2101.03652 (2021)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783278"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/DNSR.2004.1344743"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-020-01986-9"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975673.39"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00240"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319886"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3044696"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0070"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939804"},{"key":"e_1_2_1_68_1","volume-title":"Jason Weston, and Bernhard Sch\u00f6lkopf.","author":"Zhou Dengyong","year":"2004","unstructured":"Dengyong Zhou , Olivier Bousquet , Thomas Navin Lal , Jason Weston, and Bernhard Sch\u00f6lkopf. 2004 . Learning with local and global consistency. Advances in neural information processing systems 16, 16 (2004), 321--328. Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Sch\u00f6lkopf. 2004. Learning with local and global consistency. Advances in neural information processing systems 16, 16 (2004), 321--328."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.188"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099705"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3523210.3523216","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:50:02Z","timestamp":1672224602000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3523210.3523216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":68,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.14778\/3523210.3523216"],"URL":"https:\/\/doi.org\/10.14778\/3523210.3523216","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}