poster

Diversified ranking on large graphs: an optimization viewpoint

Authors:

Ching-Yung LinAuthors Info & Claims

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 1028 - 1036

https://doi.org/10.1145/2020408.2020573

Published: 21 August 2011 Publication History

Abstract

Diversified ranking on graphs is a fundamental mining task and has a variety of high-impact applications. There are two important open questions here. The first challenge is the measure - how to quantify the goodness of a given top-k ranking list that captures both the relevance and the diversity? The second challenge lies in the algorithmic aspect - how to find an optimal, or near-optimal, top-k ranking list that maximizes the measure we defined in a scalable way? In this paper, we address these challenges from an optimization point of view. Firstly, we propose a goodness measure for a given top-k ranking list. The proposed goodness measure intuitively captures both (a) the relevance between each individual node in the ranking list and the query; and (b) the diversity among different nodes in the ranking list. Moreover, we propose a scalable algorithm (linear wrt the size of the graph) that generates a provably near-optimal solution. The experimental evaluations on real graphs demonstrate its effectiveness and efficiency.

References

[1]

C. L. 0001, F. Guo, and C. Faloutsos. Bbm: bayesian browsing model from petabyte-scale data. In KDD, pages 537--546, 2009.

Digital Library

[2]

D. Agarwal, A. Z. Broder, D. Chakrabarti, D. Diklic, V. Josifovski, and M. Sayyadian. Estimating rates of rare events at multiple resolutions. In KDD, pages 16--25, 2007.

Digital Library

[3]

A. Angel, S. Chaudhuri, G. Das, and N. Koudas. Ranking objects based on relationships and fixed associations. In EDBT'09, pages 910--921, 2009.

Digital Library

[4]

L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks. In WSDM, pages 635--644, 2011.

Digital Library

[5]

A. Broder, R. Kumar, F. Maghoul1, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web: experiments and models. In WWW Conf., 2000.

Digital Library

[6]

J. G. Carbonell and J. Goldstein. The use of mmr, diversity-based reranking for reordering documents and producing summaries. In SIGIR, pages 335--336, 1998.

Digital Library

[7]

K. El-Arini, G. Veda, D. Shahaf, and C. Guestrin. Turning down the noise in the blogosphere. In KDD, pages 289--298, 2009.

Digital Library

[8]

Y. Ge, H. Xiong, A. Tuzhilin, K. Xiao, M. Gruteser, and M. J. Pazzani. An energy-efficient mobile recommender system. In KDD, pages 899--908, 2010.

Digital Library

[9]

F. Geerts, H. Mannila, and E. Terzi. Relational link-based ranking. In VLDB, pages 552--563, 2004.

Digital Library

[10]

G. H. Golub and C. F. V. Loan. Matrix Perturbation Theory. The Johns Hopkins University Press, 1996.

[11]

T. H. Haveliwala. Topic-sensitive pagerank. WWW, pages 517--526, 2002.

Digital Library

[12]

D. Heckerman, D. M. Chickering, C. Meek, R. Rounthwaite, and C. M. Kadie. Dependency networks for collaborative filtering and data visualization. In UAI, pages 264--273, 2000.

Digital Library

[13]

U. Kang, C. E. Tsourakakis, and C. Faloutsos. Pegasus: A peta-scale graph mining system. In ICDM, pages 229--238, 2009.

Digital Library

[14]

G. Karypis and V. Kumar. Multilevel -way hypergraph partitioning. In DAC, pages 343--348, 1999.

Digital Library

[15]

J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632, 1999.

Digital Library

[16]

Y. Koren. Collaborative filtering with temporal dynamics. In KDD, pages 447--456, 2009.

Digital Library

[17]

Y. Koren, S. C. North, and C. Volinsky. Measuring and extracting proximity in networks. In KDD, pages 245--255, 2006.

Digital Library

[18]

A. Krause and C. Guestrin. Beyond convexity - submodularity in machine learning. In ICML, 2008.

[19]

T. Lappas, K. Liu, and E. Terzi. Finding a team of experts in social networks. In KDD, pages 467--476, 2009.

Digital Library

[20]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007.

Digital Library

[21]

L. Li, K. Zhou, G.-R. Xue, H. Zha, and Y. Yu. Enhancing diversity, coverage and balance for summarization through structure learning. In WWW, pages 71--80, 2009.

Digital Library

[22]

P. Li, H. Liu, J. X. Yu, J. He, and X. Du. Fast single-pair simrank computation. In SDM, pages 571--582, 2010.

[23]

D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proc. CIKM, 2003.

Digital Library

[24]

R. Lichtenwalter, J. T. Lussier, and N. V. Chawla. New perspectives and methods in link prediction. In KDD, pages 243--252, 2010.

Digital Library

[25]

A. S. Maiya and T. Y. Berger-Wolf. Sampling community structure. In WWW, pages 701--710, 2010.

Digital Library

[26]

H. Maserrat and J. Pei. Neighbor query friendly compression of social networks. In KDD, pages 533--542, 2010.

Digital Library

[27]

Q. Mei, J. Guo, and D. R. Radev. Divrank: the interplay of prestige and diversity in information networks. In KDD, pages 1009--1018, 2010.

Digital Library

[28]

J. Neville, B. Gallagher, and T. Eliassi-Rad. Evaluating statistical tests for within-network classifiers of relational data. In ICDM, pages 397--406, 2009.

Digital Library

[29]

C. C. Noble and D. J. Cook. Graph-based anomaly detection. In KDD, pages 631--636, 2003.

Digital Library

[30]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998. Paper SIDL-WP-1999-0120 (version of 11/11/1999).

[31]

R. Pemantle. Vertex reinforced random walk. Prob. Th. and Rel. Fields, pages 117--136, 1992.

[32]

F. Radlinski, P. N. Bennett, B. Carterette, and T. Joachims. Redundancy, diversity and interdependent document relevance. SIGIR Forum, 43(2):46--52, 2009.

Digital Library

[33]

P. Sarkar and A. W. Moore. Fast nearest-neighbor search in disk-resident graphs. In KDD, pages 513--522, 2010.

Digital Library

[34]

V. Satuluri and S. Parthasarathy. Scalable graph clustering using stochastic flows: applications to community discovery. In KDD, pages 737--746, 2009.

Digital Library

[35]

H. Shan and A. Banerjee. Generalized probabilistic matrix factorizations for collaborative filtering. In ICDM, pages 1025--1030, 2010.

Digital Library

[36]

C. Tan, J. Tang, J. Sun, Q. Lin, and F. Wang. Social action tracking via noise tolerant time-varying factor graphs. In KDD, pages 1049--1058, 2010.

Digital Library

[37]

H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random walk with restart and its applications. In ICDM, pages 613--622, 2006.

Digital Library

[38]

L. Wu. Social network effects on performance and layoffs: Evidence from the adoption of a social networking tool. Job Market Paper, 2011.

[39]

D. Xin, J. Han, X. Yan, and H. Cheng. Mining compressed frequent-pattern sets. In VLDB, pages 709--720, 2005.

Digital Library

[40]

X. Yin, J. Han, and P. S. Yu. Cross-relational clustering with user guidance. In KDD, pages 344--353, 2005.

Digital Library

[41]

Y. Yue and T. Joachims. Predicting diverse subsets using structural svms. In ICML, pages 1224--1231, 2008.

Digital Library

[42]

X. Zhu, A. B. Goldberg, J. V. Gael, and D. Andrzejewski. Improving diversity in ranking using absorbing random walks. In HLT-NAACL, pages 97--104, 2007.

[43]

C.-N. Ziegler, S. M. McNee, J. A. Konstan, and G. Lausen. Improving recommendation lists through topic diversification. In WWW, pages 22--32, 2005.

Digital Library

Cited By

Ordozgoiti BMahadevan AMatakos AGionis A(2022)Provable randomized rounding for minimum-similarity diversificationData Mining and Knowledge Discovery10.1007/s10618-021-00811-236:2(709-738)Online publication date: 4-Jan-2022
https://doi.org/10.1007/s10618-021-00811-2
Ge XChrysanthis PPelechrinis KZeinalipour-Yazti DSharaf M(2020)Serendipity-based Points-of-Interest NavigationACM Transactions on Internet Technology10.1145/339119720:4(1-32)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1145/3391197
Morales PTabourier LFournier-S'niehotta RAlhajj R(2020)Testing the impact of semantics and structure on recommendation accuracy and diversityProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381334(250-257)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381334
Show More Cited By

Index Terms

Diversified ranking on large graphs: an optimization viewpoint
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Scalable Diversified Ranking on Large Graphs

Enhancing diversity in ranking on graphs has been identified as an important retrieval and mining task. Nevertheless, many existing diversified ranking algorithms either cannot be scalable to large graphs due to the time or memory requirements, or lack ...
Re-ranking search results using query logs
CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management

This work addresses two common problems in search, frequently occurring with underspecified user queries: the top-ranked results for such queries may not contain documents relevant to the user's search intent, and fresh and relevant pages may not get ...
Coverage, relevance, and ranking: The impact of query operators on Web search engine results

Research has reported that about 10% of Web searchers utilize advanced query operators, with the other 90% using extremely simple queries. It is often assumed that the use of query operators, such as Boolean operators and phrase searching, improves the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2011

1446 pages

ISBN:9781450308137

DOI:10.1145/2020408

General Chair:
Chid Apte
IBM Research
,
Program Chairs:
Joydeep Ghosh
UT Austin
,
Padhraic Smyth
UC Irvine

Copyright © 2011 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

KDD '11

Sponsor:

KDD '11: The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2011

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
566
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ordozgoiti BMahadevan AMatakos AGionis A(2022)Provable randomized rounding for minimum-similarity diversificationData Mining and Knowledge Discovery10.1007/s10618-021-00811-236:2(709-738)Online publication date: 4-Jan-2022
https://doi.org/10.1007/s10618-021-00811-2
Ge XChrysanthis PPelechrinis KZeinalipour-Yazti DSharaf M(2020)Serendipity-based Points-of-Interest NavigationACM Transactions on Internet Technology10.1145/339119720:4(1-32)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1145/3391197
Morales PTabourier LFournier-S'niehotta RAlhajj R(2020)Testing the impact of semantics and structure on recommendation accuracy and diversityProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381334(250-257)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381334
Wu ZZhou KLiu YZhang MMa S(2019)Does Diversity Affect User Satisfaction in Image SearchACM Transactions on Information Systems10.1145/332011837:3(1-30)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.1145/3320118
Zhang JGuo BLi ZLiu YYu ZHan Q(2019)CrowdTravel: Leveraging Cross-Modal CrowdSourced Data for Fine-Grained and Context-Based Travel Route Recommendation2019 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI)10.1109/SmartWorld-UIC-ATC-SCALCOM-IOP-SCI.2019.00175(851-858)Online publication date: Aug-2019
https://doi.org/10.1109/SmartWorld-UIC-ATC-SCALCOM-IOP-SCI.2019.00175
Zhou XQin DLu XChen LZhang Y(2019)Online Social Media Recommendation Over Streams2019 IEEE 35th International Conference on Data Engineering (ICDE)10.1109/ICDE.2019.00088(938-949)Online publication date: Apr-2019
https://doi.org/10.1109/ICDE.2019.00088
Zhou YRen JWu SDou DJin RZhang ZWang P(2019)Semi-supervised Classification-based Local Vertex Ranking via Dual Generative Adversarial Nets2019 IEEE International Conference on Big Data (Big Data)10.1109/BigData47090.2019.9005595(1267-1273)Online publication date: Dec-2019
https://doi.org/10.1109/BigData47090.2019.9005595
Gong ZZhong PHu W(2019)Diversity in Machine LearningIEEE Access10.1109/ACCESS.2019.29176207(64323-64350)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2917620
Nandanwar SMoroney AMurty MChang YZhai CLiu YMaarek Y(2018)Fusing Diversity in Recommendations in Heterogeneous Information NetworksProceedings of the Eleventh ACM International Conference on Web Search and Data Mining10.1145/3159652.3159720(414-422)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.1145/3159652.3159720
Bandyopadhyay SNandanwar SDeshmukh RMusti N(2018)DivGroup: A Diversified Approach to Divide Collection of Patterns into Uniform Groups2018 24th International Conference on Pattern Recognition (ICPR)10.1109/ICPR.2018.8546203(964-969)Online publication date: Aug-2018
https://doi.org/10.1109/ICPR.2018.8546203
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