Bayesian Inference for Vertex-Series-Parallel Partial Orders

Chuxuan Jiang, Geoff Keith Nicholls, Kate LeeUAI 2023 · OpenReview

Introduction

When analyzing rank-order data—ranging from historical witness lists to modern sports results—researchers often assume an underlying hierarchy. Traditional models typically rely on total orders, where every element is strictly ranked against every other. However, real-world social and competitive structures are frequently partial orders: while some relationships are clear (e.g., a King outranks a Duke), others are incomparable (e.g., two Earls of equal standing).

The primary barrier to using Bayesian partial order models has been computational. Performing inference requires counting "linear extensions"—the set of all total rankings consistent with a given partial order. For general partial orders, this is an #P-complete problem, making it intractable for datasets with more than a few dozen actors. This paper introduces a framework focusing on Vertex-Series-Parallel (VSP) partial orders, a subclass that allows for efficient $O(n)$ counting while remaining flexible enough to model complex hierarchies.

A partial order (left) and its corresponding linear extensions (right), illustrating the complexity of counting valid total rankings.

Technical Framework

The authors contribute three major technical components to enable scalable Bayesian inference:

1. A Marginally Consistent Prior

A critical property for any robust statistical model is "projectivity" or marginal consistency. In this context, it means the perceived relationship between two individuals should not change simply because a third individual is added to the dataset. The authors derive a prior distribution over VSPs that satisfies this property, utilizing Binary Decomposition Trees (BDTs) and Catalan numbers to provide a closed-form expression.

2. Recursive VSP Construction

VSPs are defined by their recursive structure, built using two fundamental operations: Series (S), where one set of nodes is placed strictly above another, and Parallel (P), where two sets of nodes are considered incomparable. This structure is what allows the model to bypass the exponential complexity of general partial orders.

Recursive construction of a Vertex-Series-Parallel (VSP) partial order using series (S) and parallel (P) composition operations.

3. Bi-Directional Queue-Jumping (QJ-B) Model

To account for noise in real-world observations—such as a lower-ranking official appearing higher on a list due to proximity or clerical error—the authors developed the QJ-B model. Unlike previous "queue-jumping" models that only allowed displacement in one direction, the QJ-B model allows actors to "jump" both forward and backward in a list, providing a more realistic representation of observational noise.

Key Results and Applications

The model's performance was validated using two distinct datasets: 11th and 12th-century English Royal Acta (witness lists) and 2021 Formula 1 race results.

  • Scalability: While general partial order methods fail as they approach 30 nodes, the VSP framework easily handles over 200 nodes due to its linear-time counting algorithm.
  • Historical Insights: When applied to the Royal Acta, the model successfully reconstructed known medieval hierarchies (e.g., King > Queen > Archbishop). More importantly, it quantified previously unmeasured relationships between lower-ranking officials, offering new evidence for historical analysis.
  • Model Fit: The VSP model provided a significantly better fit for the witness list data than traditional alternatives like Mallows or Plackett-Luce mixtures, which often struggle to represent the inherent incomparability found in social strata.

Conclusion and Future Directions

By restricting the model space to VSPs, the authors have unlocked the ability to perform rigorous Bayesian inference on large-scale partial orders. While VSPs cannot represent every possible relationship (they exclude certain "N-shaped" subgraphs), they prove highly effective for social and competitive hierarchies. Future work may involve optimizing the QJ-B likelihood evaluation to handle even larger subsets of noisy data and exploring more efficient MCMC moves to navigate the space of decomposition trees.

Summary updated

Abstract

Partial orders are a natural model for the social hierarchies that may constrain ``queue-like'' rank-order data. However, the computational cost of counting the linear extensions of a general partial order on a ground set with more than a few tens of elements is prohibitive. Vertex-series-parallel partial orders (VSPs) are a subclass of partial orders which admit rapid counting and represent the sorts of relations we expect to see in a social hierarchy. However, no Bayesian analysis of VSPs has been given to date. We construct a marginally consistent family of priors over VSPs with a parameter controlling the prior distribution over VSP depth. The prior for VSPs is given in closed form. We extend an existing observation model for queue-like rank-order data to represent noise in our data and carry out Bayesian inference on ``Royal Acta'' data and Formula 1 race data. Model comparison shows our model is a better fit to the data than Plackett-Luce mixtures, Mallows mixtures, and ``bucket order'' models and competitive with more complex models fitting general partial orders.
BibTeX
@inproceedings{jiang2023bayesian,
  author = {Chuxuan Jiang and Geoff Keith Nicholls and Kate Lee},
  title = {{Bayesian Inference for Vertex-Series-Parallel Partial Orders}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=K5WX50tp2ZV},
}
Figure