Spectral Methods for Ranking with Scarce Data
This addresses ranking tasks with limited data, such as consumer preferences, but is incremental as it builds on an existing method.
The paper tackles the problem of ranking items from scarce pairwise comparisons by modifying RankCentrality to incorporate feature information, achieving improved sample complexity and outperforming state-of-the-art methods in practice.
Given a number of pairwise preferences of items, a common task is to rank all the items. Examples include pairwise movie ratings, New Yorker cartoon caption contests, and many other consumer preferences tasks. What these settings have in common is two-fold: a scarcity of data (it may be costly to get comparisons for all the pairs of items) and additional feature information about the items (e.g., movie genre, director, and cast). In this paper we modify a popular and well studied method, RankCentrality for rank aggregation to account for few comparisons and that incorporates additional feature information. This method returns meaningful rankings even under scarce comparisons. Using diffusion based methods, we incorporate feature information that outperforms state-of-the-art methods in practice. We also provide improved sample complexity for RankCentrality in a variety of sampling schemes.