2011 DiversityinRankingviaResistiveG

• (Dubey et al., 2011) ⇒ Avinava Dubey, Soumen Chakrabarti, and Chiranjib Bhattacharyya. (2011). “Diversity in Ranking via Resistive Graph Centers.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020428

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Diversity+in+Ranking+via+Resistive+Graph+Centers
• http://dl.acm.org/citation.cfm?id=2020408.2020428&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; conductance; diversity; graph; information search and retrieval; performance; ranking

Abstract

Users can rarely reveal their information need in full detail to a search engine within 1 - 2 words, so search engines need to "hedge their bets" and present diverse results within the precious 10 response slots. Diversity in ranking is of much recent interest. Most existing solutions estimate the marginal utility of an item given a set of items already in the response, and then use variants of greedy set cover. Others design graphs with the items as nodes and choose diverse items based on visit rates (PageRank). Here we introduce a radically new and natural formulation of diversity as finding centers in resistive graphs. Unlike in PageRank, we do not specify the edge resistances (equivalently, conductances) and ask for node visit rates. Instead, we look for a sparse set of center nodes so that the effective conductance from the center to the rest of the graph has maximum entropy. We give a cogent semantic justification for turning PageRank thus on its head. In marked deviation from prior work, our edge resistances are learnt from training data. Inference and learning are NP-hard, but we give practical solutions. In extensive experiments with subtopic retrieval, social network search, and document summarization, our approach convincingly surpasses recently-published diversity algorithms like subtopic cover, max-marginal relevance (MMR), Grasshopper, DivRank, and SVMdiv.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 DiversityinRankingviaResistiveG	Soumen Chakrabarti Avinava Dubey Chiranjib Bhattacharyya			Diversity in Ranking via Resistive Graph Centers				10.1145/2020408.2020428		2011