Ordering Stochastic Block Models via prior transitivity

Technical Summary: Ordering Stochastic Block Models via Prior Transitivity

Problem Statement
Directed networks often exhibit two simultaneous structural features: community structure (nodes forming groups with similar interaction patterns) and hierarchical structure (groups interacting in an ordered manner, where edges predominantly flow from higher-ranked to lower-ranked groups). Existing methodologies typically address these features in isolation. Standard Stochastic Block Models (SBMs) recover groups but do not enforce a coherent block order, while ranking models order individual nodes but fail to identify structurally equivalent groups. This separation risks enforcing strict node-level orderings where only group-level hierarchies exist, or failing to detect hierarchical patterns within clustered data. The paper addresses the need for a unified framework that jointly infers ordered blocks and assesses whether a transitive block structure is supported by the data.

Methodology: The Transitive Stochastic Block Model (TSBM)
The authors introduce the Transitive Stochastic Block Model (TSBM), a Bayesian model for directed weighted networks. The methodology rests on five key pillars:

1. Volume/Direction Decomposition: The model decomposes directed edge counts into two components:

   • Volume: The total undirected interaction volume between nodes, modeled via a symmetric intensity matrix and node-specific degree propensities (following the Degree-Corrected SBM framework).
   • Direction: The probability of interaction direction conditional on an interaction occurring. This separation allows the model to impose hierarchy on directional imbalance rather than interaction frequency.

2. Transitivity-Inducing Priors: The model imposes order on blocks through priors on the directional log-odds ($\psi$). Two specifications are proposed:

   • Weak Stochastic Transitivity (WST): A flexible prior that excludes cyclic dominance patterns (e.g., $A \succ B \succ C \succ A$) by ensuring that if block $k$ dominates $\ell$ and $\ell$ dominates $m$, then $k$ dominates $m$. This is achieved via independent truncated Gaussian priors on the upper-triangular log-odds.
   • Strong Stochastic Transitivity (SST): A more restrictive prior, specifically a Toeplitz SST version. It assumes that directional advantage increases with rank separation (i.e., the advantage of a high-ranked block over a low-ranked block is greater than its advantage over a mid-ranked block). This is modeled by assuming log-odds depend only on the distance between blocks, with monotonic increments enforced via a cumulative sum of positive increments.

3. Ordered Partition Prior: Since ordered block labels are not exchangeable (permuting labels changes the hierarchy and thus the likelihood), standard exchangeable partition priors are unsuitable. The authors employ an age-ordered partition prior (Donnelly and Tavaré, 1986; Donnelly and Joyce, 1991). This prior, originally from population genetics, treats blocks as appearing sequentially in time (or age), allowing for the joint inference of the number of blocks and node allocation without requiring reversible-jump MCMC.

4. Posterior Inference: Inference is performed via a partially collapsed Gibbs sampler. To handle the non-conjugacy between the logistic likelihood of directional probabilities and Gaussian priors, the authors utilize Pólya-Gamma data augmentation. This enables tractable conditional updates for the directional parameters, volume parameters, and node allocations.

5. Model Selection: The framework uses Leave-One-Out Cross-Validation (LOO-CV) via Pareto-smoothed importance sampling to compare the TSBM variants against the standard Degree-Corrected SBM (DC-SBM).

Key Contributions

• Novel Model Formulation: The TSBM is the first Bayesian model to jointly infer stochastic equivalence and stochastic ordering in directed networks using transitivity constraints on block-level probabilities.
• Computational Tractability: By combining Pólya-Gamma augmentation with age-ordered partition priors, the authors derive a full Gibbs sampler that avoids computationally expensive trans-dimensional methods (like reversible-jump) for estimating the number of ordered blocks.
• Flexible Transitivity: The introduction of both WST and Toeplitz SST allows the model to adapt to different levels of hierarchical strictness, from simple acyclicity to rank-dependent dominance.
• Diagnostic Capability: The framework explicitly identifies scenarios where imposing order is detrimental (e.g., non-transitive citation networks), providing a probabilistic mechanism to assess the validity of the transitivity assumption.

Results

• Simulation Studies: In sparse networks with weak directional signals, the TSBM (both WST and SST variants) significantly outperforms the standard DC-SBM in both predictive accuracy (LOOIC) and partition recovery (Variation of Information). In dense networks with strong signals, all models perform similarly. Crucially, in misspecified scenarios where data contains cycles (non-transitive), the DC-SBM outperforms the TSBM, demonstrating the model's ability to detect when the transitivity assumption is inappropriate.
• Empirical Applications: The model was applied to six directed weighted networks (animal dominance, journal citations, and school friendships):
  • Animal Dominance: In bighorn sheep, mountain goats, and spotted hyenas networks, the TSBM generally improved predictive performance and yielded partitions with clearer, more coherent hierarchical structures (fewer backward edges) compared to the DC-SBM.
  • Citations: In the statistics journal citation network, the DC-SBM performed better. The authors note that while prestige gradients exist, the citation patterns are not strictly transitive; thus, the ordered prior constrained the model unnecessarily.
  • Macaques: In the macaque dominance network, the hierarchy was already nearly perfect (almost a strict node-level ordering). Here, the DC-SBM slightly outperformed the TSBM, as the prior's regularization offered little benefit over the strong signal already present in the data.
  • Friendships: In the high school friendship network, the TSBM recovered a block-level ordering consistent with a global hierarchy, whereas the DC-SBM produced a partition reflecting community structure rather than hierarchy.

Significance and Claims
The paper claims that the TSBM provides a probabilistic framework for estimating ordered groups and, importantly, for assessing when a transitive block structure is supported by the data. The authors emphasize that the value of the model lies not just in enforcing order, but in the joint modeling of grouping and hierarchy, which can improve inference and prediction specifically when the directional signal is weak or the network is sparse. The work also contributes to Bayesian nonparametrics by demonstrating the utility of age-ordered partition priors in latent block models with non-exchangeable labels, a combination not previously utilized in this context. The authors modestly note that the model's performance is contingent on the data; in cases where the underlying structure is non-transitive or the hierarchy is already extremely sharp, the unconstrained DC-SBM may remain preferable.