Learning to rank networked entities

Agarwal, Alekh ; Chakrabarti, Soumen ; Aggarwal, Sunny (2006) Learning to rank networked entities In: KDD '06 Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 20-23, Philadelphia, Pennsylvania, USA.

PDF - Other

Official URL: http://dl.acm.org/citation.cfm?id=1150409


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.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to KDD '06 Proceedings of the 12th ACM SIGKDD International Conference.
Keywords:Pagerank; Conductance; Network Flow; Maximum Entropy
ID Code:100081
Deposited On:12 Feb 2018 12:27
Last Modified:12 Feb 2018 12:27

Repository Staff Only: item control page