Fast dynamic reranking in large graphs

ABSTRACT

In this paper we consider the problem of re-ranking search results by incorporating user feedback. We present a graph theoretic measure for discriminating irrelevant results from relevant results using a few labeled examples provided by the user. The key intuition is that nodes relatively closer (in graph topology) to the relevant nodes than the irrelevant nodes are more likely to be relevant. We present a simple sampling algorithm to evaluate this measure at specific nodes of interest, and an efficient branch and bound algorithm to compute the top k nodes from the entire graph under this measure. On quantifiable prediction tasks the introduced measure outperforms other diffusion-based proximity measures which take only the positive relevance feedback into account. On the Entity-Relation graph built from the authors and papers of the entire DBLP citation corpus (1.4 million nodes and 2.2 million edges) our branch and bound algorithm takes about 1.5 seconds to retrieve the top 10 nodes w.r.t. this measure with 10 labeled nodes.

REFERENCES

• 1: Jacob Abernethy , Olivier Chapelle , Carlos Castillo, Web spam identification through content and hyperlinks, Proceedings of the 4th international workshop on Adversarial information retrieval on the web, April 22-22, 2008, Beijing, China [doi>10.1145/1451983.1451994]
• 2: D. Aldous and J. A. Fill. Reversible Markov Chains. 2001.
• 3: Andrey Balmin , Vagelis Hristidis , Yannis Papakonstantinou, Objectrank: authority-based keyword search in databases, Proceedings of the Thirtieth international conference on Very large data bases, p.564-575, August 31-September 03, 2004, Toronto, Canada
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: Soumen Chakrabarti, Dynamic personalized pagerank in entity-relation graphs, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242650]
• 6: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 7: Leo Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.11, p.1768-1783, November 2006 [doi>10.1109/TPAMI.2006.233]
• 8: Zoltán Gyöngyi , Hector Garcia-Molina , Jan Pedersen, Combating web spam with trustrank, Proceedings of the Thirtieth international conference on Very large data bases, p.576-587, August 31-September 03, 2004, Toronto, Canada
• 9: G. Jeh and J. Widom. Scaling personalized web search. In Stanford University Technical Report, 2002.
• 10: Rong Jin , Hamed Valizadegan , Hang Li, Ranking refinement and its application to information retrieval, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367552]
• 11: Amruta Joshi , Ravi Kumar , Benjamin Reed , Andrew Tomkins, Anchor-based proximity measures, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242730]
• 12: Ioannis Koutis , Gary L. Miller, A linear work, O(n^1/6) time, parallel algorithm for solving planar Laplacians, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1002-1011, January 07-09, 2007, New Orleans, Louisiana
• 13: Anat Levin , Dani Lischinski , Yair Weiss, Colorization using optimization, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 14: Alexandros Ntoulas , Marc Najork , Mark Manasse , Dennis Fetterly, Detecting spam web pages through content analysis, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135794]
• 15: P. Sarkar and A. Moore. A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In Proc. UAI, 2007.
• 16: Purnamrita Sarkar , Andrew W. Moore , Amit Prakash, Fast incremental proximity search in large graphs, Proceedings of the 25th international conference on Machine learning, p.896-903, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390269]
• 17: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 18: Z. Xu, R. Akella, and Y. Zhang. Incorporating diversity and density in active learning for relevance feedback. In ECIR, 2007.
• 19: X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, volume 20, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback

General Terms:
Algorithms, Experimentation

Keywords:
harmonic function, random walk, search, semi-supervised learning