document: Fast dynamic reranking in large graphs 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 .
doc_bio_tags: O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O