TY - JOUR
AU - Saha, Aadirupa
AU - Shivanna, Rakesh
AU - Bhattacharyya, Chiranjib
PY - 2019/07/17
Y2 - 2023/09/27
TI - How Many Pairwise Preferences Do We Need to Rank a Graph Consistently?
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 33
IS - 01
SE - AAAI Technical Track: Machine Learning
DO - 10.1609/aaai.v33i01.33014830
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5182
SP - 4830-4837
AB - <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>
ER -