How Many Pairwise Preferences Do We Need to Rank A Graph Consistently?

We consider the problem of optimal recovery of true ranking of n items from a randomly chosen subset of their pairwise preferences. It is well known that without any further assumption, one requires a sample size of Omega(n2) for the purpose. We analyze the problem with an additional structure of relational graph G([n],E) over the n items added with an assumption of locality: Neighboring items are similar in their rankings. Noting the preferential nature of the data, we choose to embed not the graph, but, its strong product to capture the pairwise node relationships. Furthermore, unlike existing literature that uses Laplacian embedding for graph based learning problems, we use a richer class of graph embeddings---orthonormal representations---that includes (normalized) Laplacian as its special case. Our proposed algorithm, it Pref-Rank, predicts the underlying ranking using an SVM based approach over the chosen embedding of the product graph, and is the first to provide statistical consistency on two ranking losses: Kendall's tau and Spearman's footrule, with a required sample complexity of O(n2 chi(barG))^frac23 pairs, chi(barG) being the chromatic number of the complement graph barG. Clearly, our sample complexity is smaller for dense graphs, with chi(bar G) characterizing the degree of node connectivity, which is also intuitive due to the locality assumption e.g. O(n^frac43) for union of k-cliques, or O(n^frac53) for random and power law graphs etc.---a quantity much smaller than the fundamental limit of Omega(n2) for large n. This, for the first time, relates ranking complexity to structural properties of the graph. We also report experimental evaluations on different synthetic and real datasets, where our algorithm is shown to outperform the state-of-the-art methods.