Contribution
A method for ranking from incomplete, imbalanced, cardinal pairwise data, HodgeRank, with a built-in diagnostic of whether the data admit a global ranking at all. Its authors call their “elementary treatment a minor expository contribution” on the mathematics’ side (p. 5). The new part is its application to ranking.
Key insight
A ranking is a potential and the comparisons are its gradient. Data consistent with a ranking form a gradient flow. What is left after the best gradient fit is a cyclic flow. Cycles are not noise to be discarded: “cyclic inconsistencies are not necessarily due to error or noise in the data but may very well be an inherent characteristic of the data” (p. 3). “Even a single individual making his own preference judgements could face such dilemma — if he uses multiple criteria to rank the alternatives” (p. 3).
Assumptions
- Cardinal comparisons. “We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data” (abstract). Curl-freeness, X_ij + X_jk + X_ki = 0, is a cardinal condition (p. 30).
- A pre-processed flow Ȳ. Raw data must first be turned into one of four averages (§2.2.1, p. 10): mean score difference, log score ratio, binary comparison, or log odds. The result depends on which is chosen.
- Weights. w_ij defaults to the number of comparisons of the pair (eq. 8). “This choice of W is not intended to be rigid. One could for example define W to incorporate prior knowledge of the relative importance of the paired comparisons as judged by the voters” (p. 9).
- l2 geometry. Orthogonality and the least-squares solution use the weighted inner product on edge flows (§5.1). l1 variants are treated in §6 and lose orthogonality.
Key results
- Definition 2.3, p. 12. X is globally consistent if X = grad s for some score function s, and locally consistent if it is curl-free on every triangle of the comparison graph.
- Theorem 4.7 (Hodge Decomposition Theorem), p. 18. For a simplicial complex K, C^k(K, ℝ) = im(δ_{k−1}) ⊕ ker(Δ_k) ⊕ im(δ_k*), orthogonally, with ker(Δ_k) = ker(δ_k) ∩ ker(δ_{k−1}*). A proof is included (pp. 18–19).
- Theorem 4.8 (Helmholtz Decomposition Theorem), p. 19. “Let G = (V, E) be an undirected, unweighted graph and KG be its clique complex.” Then C¹(K_G, ℝ) = im(grad) ⊕ ker(Δ₁) ⊕ im(curl*), and ker(Δ₁) = ker(curl) ∩ ker(div). “The equation (21) says that an edge flow is harmonic iff it is both curl-free and divergence-free.”
- Theorem 5.1, pp. 21–22. (i) Solutions of (7) satisfy ∆₀s = −div Ȳ, and the minimum-norm solution is s* = −∆₀† div Ȳ. (ii) The residual R* = Ȳ − δ₀s* “is divergence-free, i.e. div R∗ = 0”, and splits orthogonally into proj_im(curl*) Ȳ, which “is a local cyclic ranking accounting for local inconsistencies”, and proj_ker(Δ₁) Ȳ, which “is a harmonic ranking accounting for global inconsistencies”. On a complete graph with unweighted inner product, s* is “the well-known Borda count” (p. 22).
- Theorem 5.2, p. 24. If the 3-clique complex has no 1-loops (β₁ = 0), “every locally consistent pairwise ranking is also globally consistent”. There is no ordinal analogue: “If we instead have “triangular transitivity” in the ordinal sense”, “then there is no result analogous to Theorem 5.2.”
- Theorem 7.1, pp. 31–32. For binary Y ∈ {±1}, least squares over the Kemeny class, a linear programme over the convex hull of permutations, weighted l1 projection onto the transitive region, and minimum feedback arc set are equivalent. “It is known that the minimum feedback arc set problem in (iv) is NP-hard, and therefore, so are the other three” (p. 32).
- Inconsistency indices, p. 35. The “cyclicity ratio, is a measure of global inconsistency given by” C_p = ‖R*‖²_{2,w} / ‖Ȳ‖²_{2,w}. Relative curl compares a triangle’s curl with the gradient on one of its edges. On the Netflix example the binary-comparison flow “has the smallest cyclicity ratio, 0.30” (p. 36).
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | Any pairwise-ranking flow decomposes orthogonally into gradient, curl and harmonic parts | strong | Theorems 4.7–4.8, proved |
| C2 | The least-squares ranking is the gradient part; the residual is the cyclic part | strong | Theorem 5.1 |
| C3 | On complete, balanced, binary data it is the Borda count | strong | eq. (26), §7.1 |
| C4 | A small residual certifies a global ranking; a large one says no ranking explains the data | moderate | interpretive; the l2 share is a convention |
| C5 | Harmonic components are rare on realistic comparison graphs | weak | Kahle’s random-graph result, applied by analogy (§5.2) |
Concepts
- gradient / curl / harmonic flow — globally acyclic, locally cyclic, and locally acyclic but globally cyclic pairwise rankings.
- cyclicity ratio — the residual’s share of the flow’s squared weighted norm.
- certificate of reliability — the authors’ name for the residual’s magnitude.
Connections
Candogan et al. (LIT-1442) cite this paper and apply the same decomposition to games, where curl vanishes. Sen’s liberal paradox (THEORY-027) is the ordinal intransitivity this paper sets beside its cardinal inconsistency (p. 30). Kendall and Smith’s circular triads, the ordinal index, are the binary case of its curl (p. 12).
Bearing on the record
It fits the conflict record directly. QUESTION-268’s first measure is an organization’s decisions on the pairs where its perspectives disagree. HodgeRank takes exactly such data: alternatives as nodes, contested pairs as edges, and the direction of each decision as a binary comparison averaged over occasions, Ȳ_ij = Pr(j chosen over i) − Pr(i over j) (p. 10). Two flows must be kept apart.
- The decision flow, built from what the system did. Its gradient share says whether the system’s contested decisions admit a global ordering. That is TERM-076’s common currency: whether the negotiation has a potential at all.
- The perspectives’ flows, one per perspective, built from what each would have chosen. Aggregating them with HodgeRank gives a Borda-like collective ranking. That is a choice rule applied to the perspectives, not the outcome of their negotiation, and it must not be mistaken for it.
Which ordering prevails is then a comparison between the two. One candidate, the record’s and not the paper’s, is the weighted correlation ⟨grad s*, Y^v⟩_w / (‖grad s*‖_w ‖Y^v‖_w) between the decision flow’s gradient and perspective v’s flow, on the contested pairs. Edges should be restricted to contested pairs. Otherwise pairs on which every perspective agrees inflate the gradient share, and CLAIM-440’s first consequence fails: with no frustration there is nothing to prevail over.
Can a binary conflict record be fed to it? Yes, but its cyclic share is then not ambivalence. The record’s check: a perfectly transitive binary record, the complete tournament in which the higher-ranked option always wins, has cyclicity ratio (n − 2)/3n. That is 1/9 at n = 3, 1/6 at n = 4 and 0.27 at n = 10, rising toward 1/3. It was computed for n = 3 to 10 and matches the formula at each. The least-squares ranking recovers the order exactly. The residual is not intransitivity. It is the mismatch between ±1 data and any gradient, since equal-magnitude wins cannot be differences of scores. The authors flag the general point: their inconsistency is cardinal and the impossibility theorems are ordinal (p. 30), and curl-freeness has no ordinal counterpart (p. 24). So “ambivalence = cyclic share” fails on binary data unless:
- the share is read against the transitive baseline for the same graph, or
- the ordinal index is used, circular triads, |curl| = 3 on a binary triangle (p. 12), counted among contested triples.
The second is the honest measure of ambivalence on a who-won record. The first is a calibration of the cardinal share.
What it assumes. Three choices fix the share before any data are seen:
- an aggregation into Ȳ, binary or score difference or log ratio, which give different rankings and ratios in the paper’s own example (Table 1, p. 37);
- a weighting w, which by default counts how often a pair was contested, so frequently contested pairs dominate whatever their stakes; and
- the l2 inner product.
An intensity read from it is a property of the system plus these choices. CLAIM-436’s warning that an ordering need not be a currency applies here too. The measure turns the ordering into a currency by fiat.
Gradient share as intensity. On the decision flow, the gradient share measures how coherent the contested decisions are, not how strongly a given ranking overrides the others. A system whose decisions follow a stable compromise among its perspectives scores as high as one in which a single perspective dictates. Intensity in TERM-076’s sense, how much of what the others would decide the prevailing ranking overrides, needs the alignment term above, weighted by how far the overridden perspectives’ flows were from it. The gradient share alone cannot supply it.
Local and global inconsistency. On a complete comparison graph the harmonic term “is always zero” (p. 35). A conflict record is sparse, holding only the pairs that happened to be contested. Harmonic inconsistency there may be an artefact of which pairs were contested rather than a fact about the system. Curl, which is local, is the more robust indicator. The paper’s food example (p. 4), coarse consensus with local cycles, is a natural picture of split ascendancy within a group of nearby options.
A lexicographic override. On a binary record, a lexicographic override and a compensatory trade-off that rank the options faced in the same order produce the same transitive tournament and the same shares. The distinction CLAIM-440’s fifth consequence and CLAIM-435 rely on is invisible to a who-won record. Telling them apart needs magnitudes, such as how much of one dimension was traded for another, which is the cardinal data this method is built for. A threshold override with a discrimination threshold, a lexicographic semiorder (CLAIM-436 part 3b), does show up. Its choices cycle, and the cycle appears as circular triads or a non-zero curl on the relevant triangles.
Persistence and resumption. HodgeRank is static. Applied over successive windows, the gradient share and the alignment term become time series, which is where QUESTION-268’s attractor-strength and hysteresis tools would act. The paper does none of this.
An anomaly in the arXiv text. Theorem 5.1 makes R* orthogonal to the gradient part under the same weighted inner product, so ‖R*‖² ≤ ‖Ȳ‖² and C_p ≤ 1. Yet Table 1 (p. 37) reports a cyclicity ratio of 1.15 for the score-ratio flow. Either the table uses a different normalization or it has an error. The published version was not checked. The record should not take the paper’s C_p values as calibration without recomputing them.
Limitations
The l2 choice is a convention, and §6 shows that l1 alternatives change the solution. Harmonic components are argued to be rare by analogy with Erdős–Rényi graphs, which the authors do not defend as models of real comparison graphs. Ties are excluded from the binary case “to keep the discussion simple” (§7).
Open questions
Whether an ordinal decomposition exists with the gradient/cyclic geometry, one invariant to monotone transformation of the data. If not, whether the circular-triad count, normalized by the number of contested triples, is the best ordinal index of ambivalence the record can have.