P. Sarkar, and A. Moore. Proceedings of the 18th international conference on World wide web, page 31--40. New York, NY, USA, ACM, (2009)
DOI: 10.1145/1526709.1526715
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.
%0 Conference Paper
%1 citeulike:4375062
%A Sarkar, Purnamrita
%A Moore, Andrew W.
%B Proceedings of the 18th international conference on World wide web
%C New York, NY, USA
%D 2009
%I ACM
%K dlpaws dppaws japaws recommender relevance-feedback spread-activation
%P 31--40
%R 10.1145/1526709.1526715
%T Fast dynamic reranking in large graphs
%U http://dx.doi.org/10.1145/1526709.1526715
%X 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.
%@ 978-1-60558-487-4
@inproceedings{citeulike:4375062,
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.}},
added-at = {2018-03-19T12:24:51.000+0100},
address = {New York, NY, USA},
author = {Sarkar, Purnamrita and Moore, Andrew W.},
biburl = {https://www.bibsonomy.org/bibtex/26dec1d7dc98a620506abfe7f6030ab6e/aho},
booktitle = {Proceedings of the 18th international conference on World wide web},
citeulike-article-id = {4375062},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1526709.1526715},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/1526709.1526715},
doi = {10.1145/1526709.1526715},
interhash = {2dfb95457971c30026fc2935fe850300},
intrahash = {6dec1d7dc98a620506abfe7f6030ab6e},
isbn = {978-1-60558-487-4},
keywords = {dlpaws dppaws japaws recommender relevance-feedback spread-activation},
location = {Madrid, Spain},
pages = {31--40},
posted-at = {2010-04-19 19:00:25},
priority = {3},
publisher = {ACM},
series = {WWW '09},
timestamp = {2018-03-19T12:24:51.000+0100},
title = {{Fast dynamic reranking in large graphs}},
url = {http://dx.doi.org/10.1145/1526709.1526715},
year = 2009
}