Statistical ranking and combinatorial Hodge theory

By Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, Yinyu Ye. Mathematical programming, 2008

424 citations recorded by the source corpus.

We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian, which is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We shall study the graph Helmholtzian using combinatorial Hodge theory, which provides a way to unravel ranking information from edge flows. In particular, we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the l2-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained—if this is large, then it indicates that the data does not have a good global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency in the ranking data arises locally or globally. When applied to statistical ranking problems, Hodge decomposition sheds light on whether a given dataset may be globally ranked in a meaningful way or if the data is inherently inconsistent and thus could not have any reasonable global ranking; in the latter case it provides information on the nature of the inconsistencies. An obvious advantage over the NP-hardness of Kemeny optimization is that HodgeRank may be easily computed via a linear least squares regression. We also discuss connections with well-known ordinal ranking techniques such as Kemeny optimization and Borda count from social choice theory.

Subfields: Computational Theory and Mathematics, Economics and Econometrics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/b1cda064decc073881941c6d4f4ef3d6a3daafb4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Economics and Econometrics

In Signal Processing

Citations in the corpus

Analysis and Approximation of Nonlocal Diffusion Problems with Volume Constraints (2012, background): “3] and [10, 37, 36] for some recent work and citations to the literature.”
Massive Online Crowdsourced Study of Subjective and Objective Picture Quality (2015, methodology): “…al. [33], [34] introduced the HodgeRank on Random Graphs (HRRG) test, where random sampling methods based on Erd¨os-R´enyi random graphs were used to sample pairs and the HodgeRank [35] was used to recover the underlying quality scores from the incomplete and imbalanced set of paired comparisons.”
Re-evaluating evaluation (2018, methodology): “Theorem (Hodge decomposition, [48]) .”
What are higher-order networks? (2021, background): “aggregating rankings in a consistent way [154] or for smoothing and filtering flows and trajectories on networks and simplicial complexes [20,21,153,248,250].”
Hodge Laplacians on graphs (2015, methodology): “Less well-known is the graph Helmholtzian [38], the operator ∆1 : L 2 ∧(E)→ L(2)∧(E) defined by ∆1 = − grad div + curl∗ curl, which is a graph-theoretic analogue of the vector Laplacian.”
Group MAD Competition? A New Methodology to Compare Objective Image Quality Models (2016, methodology): “Since every pair of images in the gMAD competition are associated with two IQA models, we first compare these models in pairs and then aggregate the pairwise comparisons into a global ranking using mature rank aggregation tools such as maximum likelihood for multiple options [28], hodgeRank [10] and”
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, neutral): “Additionally, the work Jiang et al. (2011); Xu et al. (2012) proposed a least-squares type method, called HodgeRank, to estimate the full ranking, which generalizes the simple Borda count algorithm (Borda, 1784; Ammar and Shah, 2011; Rajkumar and Agarwal, 2014).”
Classifying Actions and Measuring Action Similarity by Modeling the Mutual Context of Objects and Human Poses (2011, methodology): “We then use the edge flow method (Jiang et al., 2011) to convert these pairwise rankings to a similarity vector s = {s(Iref , Ii)}120 i=1, where s(I , I) denotes the ground truth similarity between I and I.”
Open-ended Learning in Symmetric Zero-sum Games (2019, background): “We generalize some results from combinatorial Hodge theory (Jiang et al., 2011; Candogan et al., 2011; Balduzzi et al., 2018b) to the setting where ﬂows are antisymmetric functions instead of antisymmetric matrices .”
Visual Persuasion: Inferring Communicative Intents of Images (2014, methodology): “Since each response only provides a pair-wise order, we aggregate all responses to construct the global ranking order using HodgeRank [11] which arranges the entire image set in one sequential order.”
Differentiable Game Mechanics (2019, methodology): “The definition is adapted from Letcher et al. (2019), where conditions on the Jacobian hold at the fixed point; in contrast, Balduzzi et al.”
Interestingness Prediction by Robust Learning to Rank (2014, background): “uk/~yf300/ranking/ 6 Recent statistical theories [37,20] show that the dense human annotations collected in [16] and [21] can give a reasonable approximation of ground truth for interestingness.”
Automated Facial Trait Judgment and Election Outcome Prediction: Social Dimensions of Face (2015, methodology): “From these pairwise ratings, we retrieve the global ranking orders of all examples by HodgeRank [15] to resolve loopy orderings.”
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (2020, result): “This is exactly what is done in (Beaver, 1977; Hendrickx et al. , 2019) and broadly similar to the approach taken earlier in (Jiang et al. , 2011).”
Graph Resistance and Learning from Pairwise Comparisons (2019, methodology): “Our approach to the problem very closely parallels the approach of (Jiang et al., 2011), where a collection of potentially inconsistent rankings is optimally reconciled by solving an optimization problem over the comparison graph.”
Fine-Grained Visual Comparisons with Local Learning (2014, neutral): “While the HodgeRank algorithm [19] also takes a global ranking approach, it estimates how much it suffers from cyclic inconsistencies, which is valuable to know how much to trust the final ranking function.”
Post Classification Label Refinement Using Implicit Ordering Constraint Among Data Instances (2015, methodology): “Hence, methods that use pairwise preference relationships can be potentially used to estimate total ordering [11], [8], [9], [12], [13], [14].”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, background): “The 0- and 1-simplices are given by the graph [72,85].”