Abstract

Several algorithms have been proposed to learn to rank entities modeled as feature vectors, based on relevance feedback. However, these algorithms do not model network connections or relations between entities. Meanwhile, Pagerank and variants find the stationary distribution of a reasonable but arbitrary Markov walk over a network, but do not learn from relevance feedback. We present a framework for ranking networked entities based on Markov walks with parameterized conductance values associated with the network edges. We propose two flavors of conductance learning problems in our framework. In the first setting, relevance feedback comparing node-pairs hints that the user has one or more hidden preferred communities with large edge conductance, and the algorithm must discover these communities. We present a constrained maximum entropy network flow formulation whose dual can be solved efficiently using a cutting-plane approach and a quasi-Newton optimizer. In the second setting, edges have types, and relevance feedback hints that each edge type has a potentially different conductance, but this is fixed across the whole network. Our algorithm learns the conductances using an approximate Newton method.

Keywords

Computer sciencePageRankLearning to rankRelevance (law)Theoretical computer scienceMarkov chainRanking (information retrieval)Parameterized complexityEnhanced Data Rates for GSM EvolutionFeature (linguistics)AlgorithmArtificial intelligenceMachine learning

Affiliated Institutions

Related Publications

Publication Info

Year
2006
Type
article
Pages
14-23
Citations
102
Access
Closed

External Links

Social Impact

Altmetric

Social media, news, blog, policy document mentions

Citation Metrics

102
OpenAlex

Cite This

Alekh Agarwal, Soumen Chakrabarti, Sunny Aggarwal (2006). Learning to rank networked entities. , 14-23. https://doi.org/10.1145/1150402.1150409

Identifiers

DOI
10.1145/1150402.1150409