Hanzhi Wang
ABSTRACT
Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node s and a target node t, the PPR value π(s,t) represents the probability that a random walk from s terminates at t, and thus indicates the bidirectional importance between s and t. The majority of the existing work focuses on the single-source queries, which asks for the PPR value of a given source node s and every node t ∈ V. However, the single-source query only reflects the importance of each node t with respect to s. In this paper, we consider the single-target PPR query, which measures the opposite direction of importance for PPR. Given a target node t, the single-target PPR query asks for the PPR value of every node $s\in V$ to a given target node t. We propose RBS, a novel algorithm that answers approximate single-target queries with optimal computational complexity. We show that RBS improves three concrete applications: heavy hitters PPR query, single-source SimRank computation, and scalable graph neural networks. We conduct experiments to demonstrate that RBS outperforms the state-of-the-art algorithms in terms of both efficiency and precision on real-world benchmark datasets.
Supplemental Material
- http://arxiv.org/abs/2006.11876.Google Scholar
- http://snap.stanford.edu/data.Google Scholar
- http://law.di.unimi.it/datasets.php.Google Scholar
- Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcroft, Kamal Jain, Vahab Mirrokni, and Shanghua Teng. Robust pagerank and locally computable spam detection features. In Proceedings of the 4th international workshop on Adversarial information retrieval on the web, pages 69--76, 2008.Google ScholarDigital Library
- Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mirrokni, and Shang-Hua Teng. Local computation of pagerank contributions. In WAW, pages 150--165, 2007.Google ScholarDigital Library
- Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. Local graph partitioning using pagerank vectors. In FOCS, pages 475--486, 2006.Google ScholarDigital Library
- Lars Backstrom and Jure Leskovec. Supervised random walks: predicting and recommending links in social networks. In WSDM, pages 635--644, 2011.Google ScholarDigital Library
- Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. Fast personalized pagerank on mapreduce. In SIGMOD, pages 973--984, 2011.Google ScholarDigital Library
- Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast incremental and personalized pagerank. VLDB, 4(3):173--184, 2010.Google ScholarDigital Library
- Marco Bressan, Enoch Peserico, and Luca Pretto. Sublinear algorithms for local graph centrality estimation. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 709--718. IEEE, 2018.Google ScholarCross Ref
- Soumen Chakrabarti. Dynamic personalized pagerank in entity-relation graphs. In WWW, pages 571--580, 2007.Google ScholarDigital Library
- Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In ICALP, pages 693--703. Springer, 2002.Google ScholarDigital Library
- Mustafa Coskun, Ananth Grama, and Mehmet Koyuturk. Efficient processing of network proximity queries via chebyshev acceleration. In KDD, pages 1515--1524, 2016.Google ScholarDigital Library
- Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3):333--358, 2005.Google ScholarCross Ref
- Yasuhiro Fujiwara, Makoto Nakatsuji, Makoto Onizuka, and Masaru Kitsuregawa. Fast and exact top-k search for random walk with restart. PVLDB, 5(5):442--453, 2012.Google ScholarDigital Library
- Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, Takeshi Mishima, and Makoto Onizuka. Efficient ad-hoc search for personalized pagerank. In SIGMOD, pages 445--456, 2013.Google ScholarDigital Library
- Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, Takeshi Mishima, and Makoto Onizuka. Fast and exact top-k algorithm for pagerank. In AAAI, 2013.Google ScholarDigital Library
- Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro, Hiroaki Shiokawa, and Makoto Onizuka. Efficient personalized pagerank with accuracy assurance. In KDD, pages 15--23, 2012.Google ScholarDigital Library
- Tao Guo, Xin Cao, Gao Cong, Jiaheng Lu, and Xuemin Lin. Distributed algorithms on exact personalized pagerank. In SIGMOD, pages 479--494, 2017.Google ScholarDigital Library
- Manish S. Gupta, Amit Pathak, and Soumen Chakrabarti. Fast algorithms for top-k personalized pagerank queries. In WWW, pages 1225--1226, 2008.Google ScholarDigital Library
- Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. Wtf: The who to follow service at twitter. In WWW, pages 505--514, 2013.Google Scholar
- Glen Jeh and Jennifer Widom. Simrank: a measure of structural-context similarity. In SIGKDD, pages 538--543, 2002.Google ScholarDigital Library
- Glen Jeh and Jennifer Widom. Scaling personalized web search. In WWW, pages 271--279, 2003.Google ScholarDigital Library
- Minhao Jiang, Ada Wai-Chee Fu, and Raymond Chi-Wing Wong. Reads: a random walk approach for efficient and accurate dynamic simrank. PPVLDB, 10(9):937--948, 2017.Google ScholarDigital Library
- Ruoming Jin, Victor E Lee, and Hui Hong. Axiomatic ranking of network role similarity. In KDD, pages 922--930, 2011.Google ScholarDigital Library
- Jinhong Jung, Namyong Park, Sael Lee, and U Kang. Bepi: Fast and memory-efficient method for billion-scale random walk with restart. In SIGMOD, pages 789--804, 2017.Google ScholarDigital Library
- Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.Google Scholar
- Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Personalized embedding propagation: Combining neural networks on graphs with personalized pagerank. CoRR, abs/1810.05997, 2018.Google Scholar
- Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning, 2019.Google Scholar
- Mitsuru Kusumoto, Takanori Maehara, and Ken-ichi Kawarabayashi. Scalable similarity search for simrank. In SIGMOD, pages 325--336, 2014.Google ScholarDigital Library
- Pei Lee, Laks V. S. Lakshmanan, and Jeffrey Xu Yu. On top-k structural similarity search. In ICDE, pages 774--785, 2012.Google ScholarDigital Library
- Lina Li, Cuiping Li, Chen Hong, and Xiaoyong Du. Mapreduce-based simrank computation and its application in social recommender system. In Big Data (BigData Congress), 2013 IEEE International Congress on, 2013.Google ScholarDigital Library
- Zhenguo Li, Yixiang Fang, Qin Liu, Jiefeng Cheng, Reynold Cheng, and John Lui. Walking in the cloud: Parallel simrank at scale. PVLDB, 9(1):24--35, 2015.Google ScholarDigital Library
- David Liben-Nowell and Jon M. Kleinberg. The link prediction problem for social networks. In CIKM, pages 556--559, 2003.Google ScholarDigital Library
- Yu Liu, Bolong Zheng, Xiaodong He, Zhewei Wei, Xiaokui Xiao, Kai Zheng, and Jiaheng Lu. Probesim: scalable single-source and top-k simrank computations on dynamic graphs. PVLDB, 11(1):14--26, 2017.Google ScholarDigital Library
- Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional pagerank estimation: From average-case to worst-case. In WAW, pages 164--176, 2015.Google ScholarDigital Library
- Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Personalized pagerank estimation and search: A bidirectional approach. In WSDM, pages 163--172, 2016.Google ScholarDigital Library
- Peter Lofgren and Ashish Goel. Personalized pagerank to a target node. arXiv preprint arXiv:1304.4658, 2013.Google Scholar
- Peter A. Lofgren, Siddhartha Banerjee, Ashish Goel, and C. Seshadhri. Fast-ppr: Scaling personalized pagerank estimation for large graphs. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pages 1436--1445, New York, NY, USA, 2014. ACM.Google ScholarDigital Library
- Peter A Lofgren, Siddhartha Banerjee, Ashish Goel, and C Seshadhri. Fast-ppr: Scaling personalized pagerank estimation for large graphs. In KDD, pages 1436--1445, 2014.Google ScholarDigital Library
- Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6):1150--1170, 2011.Google Scholar
- Takanori Maehara, Takuya Akiba, Yoichi Iwata, and Ken-ichi Kawarabayashi. Computing personalized pagerank quickly by exploiting graph structures. PVLDB, 7(12):1023--1034, 2014.Google ScholarDigital Library
- Takanori Maehara, Mitsuru Kusumoto, and Ken-ichi Kawarabayashi. Efficient simrank computation via linearization. CoRR, abs/1411.7228, 2014.Google Scholar
- Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. Efficient pagerank tracking in evolving networks. In KDD, pages 875--884, 2015.Google ScholarDigital Library
- Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In SIGKDD, pages 1105--1114. ACM, 2016.Google ScholarDigital Library
- Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: bringing order to the web. 1999.Google Scholar
- Hannu Reittu, Ilkka Norros, Tomi R"aty, Marianna Bolla, and Fülöp Bazsó. Regular decomposition of large graphs: Foundation of a sampling approach to stochastic block model fitting. Data Science and Engineering, 4(1):44--60, 2019.Google ScholarCross Ref
- CH Ren, Luyi Mo, CM Kao, CK Cheng, and DWL Cheung. Clude: An efficient algorithm for lu decomposition over a sequence of evolving graphs. In EDBT, 2014.Google Scholar
- Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, and Eli Upfal. Fast distributed pagerank computation. Theoretical Computer Science, 561:113--121, 2015.Google ScholarDigital Library
- Yingxia Shao, Bin Cui, Lei Chen, Mingming Liu, and Xing Xie. An efficient similarity search framework for simrank over large dynamic graphs. PVLDB, 8(8):838--849, 2015.Google ScholarDigital Library
- Kijung Shin, Jinhong Jung, Lee Sael, and U. Kang. BEAR: block elimination approach for random walk with restart on large graphs. In SIGMOD, pages 1571--1585, 2015.Google ScholarDigital Library
- Nikita Spirin and Jiawei Han. Survey on web spam detection: principles and algorithms. SIGKDD Explorations, 13(2):50--64, 2011.Google ScholarDigital Library
- Boyu Tian and Xiaokui Xiao. SLING: A near-optimal index structure for simrank. In SIGMOD, pages 1859--1874, 2016.Google ScholarDigital Library
- Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In WWW, pages 539--548. International World Wide Web Conferences Steering Committee, 2018.Google Scholar
- Petar Veli?kovi?c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2017.Google Scholar
- Sibo Wang, Youze Tang, Xiaokui Xiao, Yin Yang, and Zengxiang Li. Hubppr: Effective indexing for approximate personalized pagerank. PVLDB, 10(3):205--216, 2016.Google ScholarDigital Library
- Sibo Wang, Youze Tang, Xiaokui Xiao, Yang Yin, and Zengxiang Li. Hubppr: Effective indexing for approximate personalized pagerank. In PVLDB, 2016.Google Scholar
- Sibo Wang and Yufei Tao. Efficient algorithms for finding approximate heavy hitters in personalized pageranks. In Proceedings of the 2018 International Conference on Management of Data, pages 1113--1127, 2018.Google ScholarDigital Library
- Sibo Wang, Renchi Yang, Xiaokui Xiao, Zhewei Wei, and Yin Yang. FORA: simple and effective approximate single-source personalized pagerank. In KDD, pages 505--514, 2017.Google ScholarDigital Library
- Zhewei Wei, Xiaodong He, Xiaokui Xiao, Sibo Wang, Yu Liu, Xiaoyong Du, and Ji-Rong Wen. Prsim: Sublinear time simrank computation on large power-law graphs. In Proceedings of the 2019 International Conference on Management of Data, pages 1042--1059, 2019.Google ScholarDigital Library
- Zhewei Wei, Xiaodong He, Xiaokui Xiao, Sibo Wang, Shuo Shang, and Ji-Rong Wen. Topppr: top-k personalized pagerank queries with precision guarantees on large graphs. In SIGMOD, pages 441--456. ACM, 2018.Google ScholarDigital Library
- Yubao Wu, Ruoming Jin, and Xiang Zhang. Fast and unified local search for random walk based k-nearest-neighbor query in large graphs. In SIGMOD 2014, pages 1139--1150, 2014.Google ScholarDigital Library
- Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. CoRR, abs/1806.03536, 2018.Google Scholar
- Yuan Yin and Zhewei Wei. Scalable graph embeddings via sparse transpose proximities. CoRR, abs/1905.07245, 2019.Google Scholar
- Weiren Yu and Xuemin Lin. IRWR: incremental random walk with restart. In SIGIR, pages 1017--1020, 2013.Google ScholarDigital Library
- Weiren Yu and Julie A. McCann. Efficient partial-pairs simrank search on large networks. Proceedings of the Vldb Endowment, 8(5):569--580.Google ScholarDigital Library
- Weiren Yu and Julie A. McCann. Random walk with restart over dynamic graphs. In ICDM, pages 589--598, 2016.Google ScholarCross Ref
- Hongyang Zhang, Peter Lofgren, and Ashish Goel. Approximate personalized pagerank on dynamic graphs. In KDD, pages 1315--1324, 2016.Google ScholarDigital Library
- Fanwei Zhu, Yuan Fang, Kevin Chen-Chuan Chang, and Jing Ying. Incremental and accuracy-aware personalized pagerank through scheduled approximation. PVLDB, 6(6):481--492, 2013.Google ScholarDigital Library
Index Terms
- Personalized PageRank to a Target Node, Revisited
Recommendations
TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs
SIGMOD '18: Proceedings of the 2018 International Conference on Management of DataPersonalized PageRank (PPR) is a classic metric that measures the relevance of graph nodes with respect to a source node. Given a graph G, a source node s, and a parameter k, a top-k PPR query returns a set of k nodes with the highest PPR values with ...
Personalized PageRank Estimation and Search: A Bidirectional Approach
WSDM '16: Proceedings of the Ninth ACM International Conference on Web Search and Data MiningWe present new algorithms for Personalized PageRank estimation and Personalized PageRank search. First, for the problem of estimating Personalized PageRank (PPR) from a source distribution to a target node, we present a new bidirectional estimator with ...
Efficient ad-hoc search for personalized PageRank
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of DataPersonalized PageRank (PPR) has been successfully applied to various applications. In real applications, it is important to set PPR parameters in an ad-hoc manner when finding similar nodes because of dynamically changing nature of graphs. Through ...
Comments