research-article

Efficient ad-hoc search for personalized PageRank

Authors:

Yasuhiro Fujiwara,

Makoto Nakatsuji,

Hiroaki Shiokawa,

Takeshi Mishima,

Makoto OnizukaAuthors Info & Claims

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Pages 445 - 456

https://doi.org/10.1145/2463676.2463717

Published: 22 June 2013 Publication History

Abstract

Personalized 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 interactive actions, interactive similarity search supports users to enhance the efficacy of applications. Unfortunately, if the graph is large, interactive similarity search is infeasible due to its high computation cost. Previous PPR approaches cannot effectively handle interactive similarity search since they need precomputation or approximate computation of similarities. The goal of this paper is to efficiently find the top-k nodes with exact node ranking so as to effectively support interactive similarity search based on PPR. Our solution is Castanet. The key Castanet operations are (1) estimate upper/lower bounding similarities iteratively, and (2) prune unnecessary nodes dynamically to obtain top-k nodes in each iteration. Experiments show that our approach is much faster than existing approaches.

References

[1]

E. Agirre and A. Soroa. Personalizing PageRank for Word Sense Disambiguation. In EACL, pages 33--41, 2009.

Digital Library

[2]

K. Avrachenkov, N. Litvak, D. Nemirovsky, E. Smirnova, and M. Sokol. Quick Detection of Top-k Personalized PageRank Lists. In WAW, pages 50--61, 2011.

Digital Library

[3]

B. Bahmani, K. Chakrabarti, and D. Xin. Fast Personalized PageRank on MapReduce. In SIGMOD Conference, pages 973--984, 2011.

Digital Library

[4]

B. Bahmani, A. Chowdhury, and A. Goel. Fast Incremental and Personalized PageRank. PVLDB, 4(3):173--184, 2010.

Digital Library

[5]

A. Balmin, V. Hristidis, and Y. Papakonstantinou. ObjectRank: Authority-based Deyword Search in Databases. In VLDB, pages 564--575, 2004.

Digital Library

[6]

S. M. Beitzel, E. C. Jensen, A. Chowdhury, D. A. Grossman, and O. Frieder. Hourly Analysis of a Very Sarge Topically Categorized Web Query Log. In SIGIR, pages 321--328, 2004.

Digital Library

[7]

B. Carterette, J. Allan, and R. K. Sitaraman. Minimal Test Collections for Retrieval Evaluation. In SIGIR, pages 268--275, 2006.

Digital Library

[8]

S. Chakrabarti, A. Pathak, and M. Gupta. Index Design and Query Processing for Graph Conductance Search. VLDB J., 20(3):445--470, 2011.

Digital Library

[9]

J. Cho and U. Schonfeld. RankMass Crawler: A Crawler with High PageRank Coverage Guarantee. In VLDB, pages 375--386, 2007.

Digital Library

[10]

J. Domènech, J. A. Gil, J. Sahuquillo, and A. Pont. Using Current Web Page Structure to Improve Prefetching Performance. Computer Networks, 54(9):1404--1417, 2010.

Digital Library

[11]

M. Eirinaki and M. Vazirgiannis. Usage-based PageRank for Web Personalization. In ICDM, pages 130--137, 2005.

Digital Library

[12]

D. Fogaras, B. Rácz, K. Csalogány, and T. Sarlós. Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments. Internet Mathematics, 2(3), 2005.

[13]

Y. Fujiwara, G. Irie, and T. Kitahara. Fast Algorithm for Affinity Propagation. In IJCAI, pages 2238--2243, 2011.

Digital Library

[14]

Y. Fujiwara, M. Nakatsuji, M. Onizuka, and M. Kitsuregawa. Fast and Exact Top-k Search for Random Walk With Restart. PVLDB, 5(5):442--453, 2012.

Digital Library

[15]

Y. Fujiwara, M. Nakatsuji, H. Shiokawa, and M. Onizuka. Efficient Search Algorithm for SimRank. In ICDE, 2013.

Digital Library

[16]

Y. Fujiwara, M. Nakatsuji, T. Yamamuro, H. Shiokawa, and M. Onizuka. Efficient Personalized PageRank with Accuracy Assurance. In KDD, 2012.

Digital Library

[17]

Y. Z. Guo, K. Ramamohanarao, and L. A. F. Park. Personalized PageRank for Web Page Prediction Based on Access Time-length and Frequency. In Web Intelligence, pages 687--690, 2007.

Digital Library

[18]

M. S. Gupta, A. Pathak, and S. Chakrabarti. Fast Algorithms for Top-k Personalized PageRank Queries. In WWW, pages 1225--1226, 2008.

Digital Library

[19]

D. A. Harville. Matrix Algebra From a Statistician's Perspective. Springer, 2008.

[20]

G. Jeh and J. Widom. Scaling Ppersonalized Web Search. In WWW, pages 271--279, 2003.

Digital Library

[21]

R. Jin, N. Ruan, S. Dey, and J. X. Yu. SCARAB: Scaling Reachability Computation on Large Graphs. In SIGMOD Conference, pages 169--180, 2012.

Digital Library

[22]

U. Kang, D. H. Chau, and C. Faloutsos. Mining Large Graphs: Algorithms, Inference, and Discoveries. In ICDE, pages 243--254, 2011.

Digital Library

[23]

A. N. Langville and C. D. Meyer. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.

Digital Library

[24]

J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. In KDD, pages 177--187, 2005.

Digital Library

[25]

R. Mihalcea. Unsupervised Large-vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling. In HLT/EMNLP, 2005.

Digital Library

[26]

M. Nakatsuji, Y. Fujiwara, T. Uchiyama, and K. Fujimura. User Similarity from Linked Taxonomies: Subjective Assessments of Items. In IJCAI, pages 2305--2311, 2011.

Digital Library

[27]

M. Nakatsuji, Y. Fujiwara, T. Uchiyama, and H. Toda. Collaborative Filtering by Analyzing Dynamic User Interests Modeled by Taxonomy. In ISWC, pages 361--377, 2012.

Digital Library

[28]

R. Navigli. Word Sense Disambiguation: A Survey. ACM Comput. Surv., 41(2), 2009.

Digital Library

[29]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999--66, Stanford InfoLab, November 1999.

[30]

J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu. Automatic Multimedia Cross-modal Correlation Discovery. In KDD, pages 653--658, 2004.

Digital Library

[31]

B. C. Russell, A. Torralba, K. P. Murphy, and W. T. Freeman. LabelMe: A Database and Web-based Tool for Image Annotation. International Journal of Computer Vision, 77(1-3):157--173, 2008.

Digital Library

[32]

H. Shiokawa, Y. Fujiwara, and M. Onizuka. Fast Algorithm for Modularity-based Graph Clustering. In AAAI, 2013.

Digital Library

[33]

H. Tong, C. Faloutsos, and J.-Y. Pan. Fast Random Walk with Restart and Its Applications. In ICDM, pages 613--622, 2006.

Digital Library

[34]

D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. Learning with Local and Global Consistency. In NIPS, 2003.

Digital Library

Cited By

Yang MWang HWei ZWang SWen J(2024)Efficient Algorithms for Personalized PageRank Computation: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.337600036:9(4582-4602)Online publication date: Sep-2024
https://doi.org/10.1109/TKDE.2024.3376000
Li YShen YChen LYuan M(2023)Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRankProceedings of the VLDB Endowment10.14778/3583140.358315016:6(1332-1345)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583150
Li YZhao XChen AYang GSong W(2023)GERWkNN: GPU-accelerated Exact Random Walk-based kNN Query in Large GraphsProceedings of the 2023 5th International Conference on Big Data Engineering10.1145/3640872.3640880(47-54)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3640872.3640880
Show More Cited By

Index Terms

Efficient ad-hoc search for personalized PageRank
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Personalized PageRank to a Target Node, Revisited
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

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 ...
Personalized PageRank Estimation and Search: A Bidirectional Approach
WSDM '16: Proceedings of the Ninth ACM International Conference on Web Search and Data Mining

We 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 personalized pagerank with accuracy assurance
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining

Personalize PageRank (PPR) is an effective relevance (proximity) measure in graph mining. The goal of this paper is to efficiently compute single node relevance and top-k/highly relevant nodes without iteratively computing the relevances of all nodes. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

June 2013

1322 pages

ISBN:9781450320375

DOI:10.1145/2463676

General Chairs:
Kenneth Ross
Columbia University
,
Divesh Srivastava
AT&T Research
,
Program Chair:
Dimitris Papadias
HKUST

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

SIGMOD '13 Paper Acceptance Rate 76 of 372 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
1,009
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang MWang HWei ZWang SWen J(2024)Efficient Algorithms for Personalized PageRank Computation: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.337600036:9(4582-4602)Online publication date: Sep-2024
https://doi.org/10.1109/TKDE.2024.3376000
Li YShen YChen LYuan M(2023)Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRankProceedings of the VLDB Endowment10.14778/3583140.358315016:6(1332-1345)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583150
Li YZhao XChen AYang GSong W(2023)GERWkNN: GPU-accelerated Exact Random Walk-based kNN Query in Large GraphsProceedings of the 2023 5th International Conference on Big Data Engineering10.1145/3640872.3640880(47-54)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3640872.3640880
Liao MLi RDai QChen HQin HWang G(2023)Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo ApproachesProceedings of the ACM on Management of Data10.1145/35893051:2(1-26)Online publication date: 20-Jun-2023
https://doi.org/10.1145/3589305
Hou GGuo QZhang FWang SWei Z(2023)Personalized PageRank on Evolving Graphs with an Incremental Index-Update SchemeProceedings of the ACM on Management of Data10.1145/35887051:1(1-26)Online publication date: 30-May-2023
https://doi.org/10.1145/3588705
Lin DWei VWong R(2023)Effective and Scalable Manifold Ranking-Based Image Retrieval with Output BoundACM Transactions on Knowledge Discovery from Data10.1145/356557417:5(1-31)Online publication date: 7-Apr-2023
https://dl.acm.org/doi/10.1145/3565574
Chen LGao YHuang XJensen CZheng B(2022)Efficient Distributed Clustering Algorithms on Star-Schema Heterogeneous GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304763134:10(4781-4796)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TKDE.2020.3047631
Hou GChen XWang SWei Z(2021)Massively parallel algorithms for personalized pagerankProceedings of the VLDB Endowment10.14778/3461535.346155414:9(1668-1680)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.14778/3461535.3461554
Deng XSun HLees AWu YYu C(2021)TURLProceedings of the VLDB Endowment10.14778/3430915.343092114:3(307-319)Online publication date: 9-Dec-2021
https://dl.acm.org/doi/10.14778/3430915.3430921
Ami AKafle KMoran KNadkarni APoshyvanyk D(2021)Systematic Mutation-Based Evaluation of the Soundness of Security-Focused Android Static Analysis TechniquesACM Transactions on Privacy and Security10.1145/343980224:3(1-37)Online publication date: 9-Feb-2021
https://dl.acm.org/doi/10.1145/3439802
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents