@article{Saha_Shivanna_Bhattacharyya_2019, title={How Many Pairwise Preferences Do We Need to Rank a Graph Consistently?}, volume={33}, url={https://ojs.aaai.org/index.php/AAAI/article/view/5182}, DOI={10.1609/aaai.v33i01.33014830}, abstractNote={<p>We consider the problem of optimal recovery of true ranking of <em>n</em> 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 Ω(<em>n</em><sup>2</sup>) for the purpose. We analyze the problem with an additional structure of relational graph <em>G</em>([<em>n</em>]<em>,E</em>) over the <em>n</em> items added with an assumption of <em>locality</em>: Neighboring items are similar in their rankings. Noting the preferential nature of the data, we choose to embed not the graph, but, its <em>strong product</em> 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—<em>orthonormal representations</em>—that includes (normalized) Laplacian as its special case. Our proposed algorithm, <em>Pref-Rank</em>, predicts the underlying ranking using an SVM based approach using the chosen embedding of the product graph, and is the first to provide <em>statistical consistency</em> on two ranking losses: <em>Kendall’s tau</em> and <em>Spearman’s footrule</em>, with a required <em>sample complexity</em> of <em>O</em>(<em>n</em><sup>2</sup>χ(G<sup>¯</sup>))⅔ pairs, χ(G<sup>¯</sup>) being the <em>chromatic number</em> of the complement graph G<sup>¯</sup>. Clearly, our sample complexity is smaller for dense graphs, with χ(G<sup>¯</sup>) characterizing the degree of node connectivity, which is also intuitive due to the <em>locality</em> assumption e.g. <em>O</em>(<em>n</em>4/3) for union of <em>k</em>-cliques, or <em>O</em>(<em>n</em>5/3) for random and power law graphs etc.—a quantity much smaller than the fundamental limit of Ω(n<sup>2</sup>) for large <em>n</em>. This, for the first time, relates ranking complexity to structural properties of the graph. We also report experimental evaluations on different synthetic and real-world datasets, where our algorithm is shown to outperform the state of the art methods.</p>}, number={01}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Saha, Aadirupa and Shivanna, Rakesh and Bhattacharyya, Chiranjib}, year={2019}, month={Jul.}, pages={4830-4837} }