Fast Dynamic Reranking in Large Graphs (2009)

Purnamrita Sarkar, Andrew W. Moore

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 irrele-
vant nodes are more likely to be relevant. We present a
simple sampling algorithm to evaluate this measure at spe-
cic nodes of interest, and an ecient branch and bound
algorithm to compute the top k nodes from the entire graph
under this measure. On quantiable prediction tasks the
introduced measure outperforms other diusion-based prox-
imity measures which take only the positive relevance feed-
back 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.

Full text

Download (application/pdf, 974.2 kB)

Approximate BibTeX Entry

@inproceedings{sarkar_moore_www09,
    Year = {2009},
    Booktitle = {International World Wide Web Conference},
    Title = {Fast Dynamic Reranking in Large Graphs}
}