Hodge Decomposition

Hodge decomposition of pairwise comparison data.

Any skew-symmetric matrix of log-odds (or edge flows on the tournament graph) can be orthogonally decomposed into:

Y = grad(s) + curl(C) + harmonic

where:

• grad(s) is the transitive component: there exists a potential s_i for each node such that Y_ij ~ s_i - s_j. This is the part that can be calibrated via a standard Bradley-Terry model.

• curl(C) is the cyclic component: it captures rock-paper-scissors structure that is irreducible to any linear ranking.

• harmonic captures global topological structure (zero for complete tournaments).

The decomposition is computed via least-squares on the combinatorial Laplacian, following Jiang et al. (2011) “Statistical ranking and combinatorial Hodge theory”.

Calibration strategy

1. Compute the Hodge decomposition of the empirical log-odds.

2. Use the gradient component s as BT strengths giving transitive calibrated win probabilities: P_trans(i > j) = sigmoid(s_i - s_j).

3. Report ||curl||^2 / ||Y||^2 as the fraction of variance due to non-transitive structure, the part your calibration ignores.

class winference.hodge.HodgeResult(potential, gradient_flow, curl_flow, harmonic_flow, transitive_variance, cyclic_variance, harmonic_variance)

Bases: NamedTuple

Result of a Hodge decomposition.

Parameters:

• potential (NDArray[float64])

• gradient_flow (NDArray[float64])

• curl_flow (NDArray[float64])

• harmonic_flow (NDArray[float64])

• transitive_variance (float)

• cyclic_variance (float)

• harmonic_variance (float)

potential: NDArray[float64]

Alias for field number 0

gradient_flow: NDArray[float64]

Alias for field number 1

curl_flow: NDArray[float64]

Alias for field number 2

harmonic_flow: NDArray[float64]

Alias for field number 3

transitive_variance: float

Alias for field number 4

cyclic_variance: float

Alias for field number 5

harmonic_variance: float

Alias for field number 6

class winference.hodge.HodgeDecomposition(models)

Bases: object

Hodge decomposition of a pairwise comparison matrix.

Examples

>>> import numpy as np
>>> from winference import HodgeDecomposition
>>> rps = np.array([[0.5, 0.9, 0.1], [0.1, 0.5, 0.9], [0.9, 0.1, 0.5]])
>>> hd = HodgeDecomposition(["A", "B", "C"])
>>> result = hd.fit(rps)
>>> result.cyclic_variance  # rock-paper-scissors is pure curl
1.0
>>> hd.transitive_win_probability("A", "B")  # no transitive signal left
0.5

Parameters:

models (list[str])

result: HodgeResult | None

fit(W, weights=None)

Decompose a win-rate matrix.

Parameters:

• W (NDArray[float64]) – Win rate matrix of shape (n, n) where W[i,j] = P(i beats j). Should satisfy W[i,j] + W[j,i] ~ 1.

• weights (NDArray[float64] | None) – Number of comparisons per pair of shape (n, n), used for weighted least squares. Default: uniform weights.

Returns:

HodgeResult containing decomposition components.

Return type:

HodgeResult

transitive_win_probability(model_a, model_b)

P(a beats b) using only the gradient (transitive) component.

This is the win probability that can be calibrated to a scalar ranking. The cyclic component is dropped.

Parameters:

• model_a (str)

• model_b (str)

Return type:

float

transitive_win_matrix()

Full NxN transitive win probability matrix.

Return type:

NDArray[float64]

transitive_strengths()

Hodge potential (transitive strength) per model.

Return type:

dict[str, float]

curl_magnitude_per_pair()

NxN matrix of curl magnitude: each pair’s deviation from transitivity.

Return type:

NDArray[float64]

worst_pairs(k=10)

Top-k pairs with largest cyclic residual.

Parameters:

k (int)

Return type:

list[tuple[str, str, float]]

summary()

Quick summary of the decomposition.

Return type:

dict[str, float | int]