Technical Summary: Hierarchical Partial-Order Models for Ranking

Problem Statement

Rank aggregation aims to combine ordered lists from diverse sources into a consensus structure. Classical parametric models, such as Mallows and Plackett–Luce, assume that preferences concentrate around one or more complete consensus rankings (total orders). However, in many applications, the assumption that the true preference structure is a total order is unjustified; assessors may regard certain items as incomparable. Furthermore, preference data often exhibit group structures (e.g., different assessors, distinct scenarios, or time-series segments) that existing models struggle to accommodate while preserving partial-order structures.

While recent work has relaxed the total-order assumption to allow for partial orders (posets), and other work has introduced hierarchical extensions for total orders, there is a lack of a unified framework that combines hierarchical grouping with partial-order consensus. Existing hierarchical models for partial orders (e.g., Arcagni et al., 2022) rely on loss-based point estimates rather than generative Bayesian inference.

Methodology

The paper introduces Hierarchical Partial-Order (HPO) models and their unsupervised clustering extension (HCPO).

1. The HPO Framework

The HPO model is designed for rank-order data coming in labeled groups (e.g., $A$ assessors). It is structured as a tree with a root node representing a "global" partial order and leaf nodes representing assessor-specific partial orders.

• Latent Variable Construction: The model parameterizes partial orders using continuous latent variables. For each item $j$ in the universe of choices, there is a vector of preference weights $U_j \in \mathbb{R}^K$. A partial order is formed by the intersection of $K$ complete orders derived from these weights.
• Generative Process:
  • Global Level: A global latent weight matrix $U^{(0)}$ is drawn from a multivariate normal distribution with a correlation structure controlled by $\rho$.
  • Local Level: For each assessor $a$, latent weights $U^{(a)}$ are drawn conditionally on $U^{(0)}$ via a multivariate normal distribution with correlation parameter $\tau$. This parameter $\tau \in (0, 1]$ controls the "shrinkage" of assessor-specific posets toward the global poset.
  • Mapping to Posets: The latent weights are transformed via a Gumbel construction (using the inverse CDF of the Gumbel distribution applied to the normal CDF) to generate preference scores $\eta$. The partial order $h^{(a)}$ is defined by the intersection of orders derived from these scores.
• Observation Models: The paper proposes three likelihoods for observing a ranking $y$ given a poset $h$:
  1. Noise-free: Uniform sampling from linear extensions (computationally expensive for large $M$).
  2. Queue-jumping: A repeated selection model where, with probability $p$, an item is chosen randomly (noise), and otherwise chosen based on the poset constraints.
  3. Weighted Queue-jumping: An extension where random choices are biased by the latent scores $\eta$, making errors less likely for items with large preference gaps.
  4. Frontier-softmax: A utility-based model where items are chosen from the "frontier" (maximal elements) of the remaining suborder, weighted by the number of items they dominate. This is computationally efficient ($O(M)$ per step) and suitable for large datasets.

2. The HCPO Framework

When group labels are unknown, the paper extends HPO to Hierarchical Clustering Partial-Order (HCPO) models.

• Clustering: A Pitman-Yor process prior is placed on the partition of lists (or assessors) into $G$ latent groups.
• Inference: The number of groups $G$ and the cluster assignments are inferred jointly with the poset hierarchy using Markov Chain Monte Carlo (MCMC).
• Assessor vs. List Clustering: The model can cluster individual lists or entire assessors (moving all lists from an assessor together).

3. Bayesian Inference

Inference is performed using MCMC. The posterior distribution is over the correlation parameters ($\rho, \tau$), the latent weight matrices ($U$), the regression coefficients ($\beta$), and the partition ($C$). The dimension of the latent space $K$ can also be inferred using reversible jump MCMC.

Key Contributions

1. HPO and HCPO Models: The introduction of a generative Bayesian framework for grouped rank data that explicitly models partial-order consensus structures, extending the Plackett–Luce model to the poset domain.
2. Theoretical Properties:
   • Proof that Plackett–Luce models and their hierarchical variants are special cases of HPO (when $K=1$).
   • Demonstration that the model is marginally consistent, ensuring that the prior on sub-orders is consistent with the prior on the full universe.
   • Proof that the model can represent any hierarchy of posets provided $K \ge \lfloor M/2 \rfloor$.
3. Novel Observation Models: The development of Weighted Queue-jumping and Frontier-softmax likelihoods, which allow for noise and computational efficiency while maintaining a generative interpretation.
4. Unsupervised Clustering: The extension to HCPO for discovering latent group structures in unlabeled rank data.

Experimental Results

The paper evaluates the models on synthetic and real-world datasets:

• Synthetic Data (HPO): In settings with labeled groups, HPO successfully recovers the latent hierarchy of posets. Recovery accuracy is driven primarily by the length of the observed lists (choice set size) and the coupling strength ($\tau$). The Frontier-softmax likelihood offers significant computational speedups (scaling linearly with list length) compared to exact linear-extension methods, which time out for $M \ge 50$.
• Synthetic Data (HCPO): In unlabeled settings, HCPO accurately recovers both the latent clustering structure and the cluster-specific posets. The benefit of clustering is most pronounced when the coupling between groups is weak (high heterogeneity).
• Cloud Provisioning Traces (LLM Agents): Applied to execution traces from LLM agents (Aliyun Cloud-IaC-6). The HPO model, treating different scenarios as groups, outperformed independent single-poset baselines in recovering the underlying dependency graphs (workflow structures). Hierarchical pooling improved the recovery of precedence constraints, particularly in scenarios with sparse data.
• Human Preference Data (3D Sound): Applied to pairwise acoustic preference data where listeners exhibited cyclic patterns (violating total orders). The HCPO model significantly outperformed total-order baselines (Plackett–Luce and Mallows mixtures) in predictive fit (WAIC). Crucially, the HCPO summaries revealed interpretable structures where clusters contained broad "top layers" of incomparable items, a feature total-order models could not represent without forcing arbitrary strict rankings.

Significance and Claims

The paper claims that the proposed HPO and HCPO frameworks provide a principled way to handle grouped rank data where preferences may be incomplete or incomparable.

• Structural Interpretability: The models allow for the recovery of partial-order structures that reflect genuine incomparabilities, avoiding the artifacts introduced by forcing data into total orders.
• Information Sharing: The hierarchical structure enables principled information sharing (shrinkage) across groups, improving estimation in low-data regimes while preserving group-specific nuances.
• Computational Feasibility: The Frontier-softmax likelihood enables the application of these models to larger item sets where exact linear-extension counting is intractable.
• Generality: The framework subsumes existing hierarchical Plackett–Luce models and extends them to the partial-order domain, offering a unified approach for both labeled and unlabeled grouped ranking data.

The authors emphasize that their approach is superior to existing loss-based methods for partial orders by providing a full Bayesian posterior, allowing for uncertainty quantification and principled model comparison via WAIC.