Structure-aware divergences for comparing probability distributions

1. Problem Statement

Many natural and social science systems are modeled using probability distributions over elements that possess inherent relationships (e.g., occupations with shared skills, species with similar traits). Standard information-theoretic tools, such as Shannon entropy and Kullback-Leibler (KL) divergence, treat these elements as interchangeable and blind to the underlying similarity structure.

While "structure-aware" entropy measures exist (e.g., Rao's quadratic entropy, Leinster-Cobbold diversity indices), there is a lack of corresponding divergence measures to compare two such distributions. Existing alternatives, such as Optimal Transport (OT) distances (e.g., Wasserstein metric), can incorporate structure but suffer from high computational costs due to the need to solve complex optimization problems. The authors aim to fill this gap by introducing a family of divergences that are sensitive to domain geometry while retaining the computational efficiency and analytical convenience of standard information theory.

2. Methodology

A. Structure-Aware Entropy

The authors build upon the Havrda-Charvát (HC) entropies (generalized by Tsallis) and Ricotta and Szeidl's structure-aware generalizations.

• Definition: For a probability distribution $p$ over $n$ elements and a similarity matrix $Z$ (where $Z_{ij} \in [0,1]$, symmetric, $Z_{ii}=1$), the structure-aware entropy of order $\alpha$ is defined as:
  $$H^Z_\alpha(p) = \begin{cases} \frac{1}{\alpha-1}(1 - p^\top(Zp)^{\alpha-1}) & \alpha \neq 1 \\ -p^\top \ln(Zp) & \alpha = 1 \end{cases}$$
  Here, $(Zp)_i$ represents the "ordinariness" of element $i$ (its expected similarity to a random element drawn from $p$).
• Properties: The authors prove that for $\alpha \ge 2$ and a positive definite similarity matrix ($Z \succ 0$), $H^Z_\alpha$ is strictly concave on the interior of the probability simplex. This concavity is crucial for the subsequent construction of divergences.

B. Structure-Aware Divergence

Leveraging the geometric connection between KL divergence and Shannon entropy (where KL is the Bregman divergence induced by negative entropy), the authors define the Structure-Aware Divergence as the Bregman divergence induced by the negative structure-aware entropy.

• Definition: For $\alpha \ge 2$ and $Z \succ 0$, the divergence $d^Z_\alpha(p || q)$ is:
  $$d^Z_\alpha(p || q) = \frac{1}{\alpha-1}p^\top((Zp)^{\alpha-1} - (Zq)^{\alpha-1}) - q^\top \text{diag}((Zq)^{\alpha-2}) Z (p-q)$$
• Key Properties:
  • Non-negativity: $d^Z_\alpha(p || q) \ge 0$, with equality iff $p=q$.
  • Convexity: Convex in the first argument ($p$).
  • Mean-Minimizer: The mean of a set of distributions minimizes the sum of divergences to that set (a property essential for clustering).
  • Special Case: For $\alpha=2$, this reduces to the squared Mahalanobis distance with metric $Z$: $d^Z_2(p || q) = (p-q)^\top Z (p-q)$.

C. Bregman Information

To facilitate clustering, the authors utilize Bregman Information, defined as the expected divergence from the mean. This serves as a structure-aware analogue to variance and mutual information, allowing for the decomposition of total dispersion into within-cluster and between-cluster components.

D. Constructing Similarity Matrices

The framework requires $Z$ to be positive definite. The authors provide methods to ensure this:

• Metric Spaces: If $d$ is a metric of "negative type" (e.g., Euclidean distance, tree distances, effective resistance), then $Z_{ij} = \exp(-\tau d_{ij})$ is guaranteed to be positive definite.
• Optimization: If a similarity matrix is not positive definite, it can be projected onto the nearest positive definite matrix via convex optimization.

3. Key Contributions

1. Novel Divergence Family: Introduction of a closed-form, structure-aware divergence derived from Bregman geometry, bridging the gap between structure-aware entropies and distribution comparison.
2. Theoretical Foundation: Proof of strict concavity for structure-aware entropies under specific conditions, enabling the rigorous definition of the associated Bregman divergences.
3. Computational Efficiency: Demonstration that these divergences have closed-form expressions, making them orders of magnitude faster to compute than Optimal Transport distances (which require solving linear programming problems).
4. Clustering Framework: Adaptation of the divergence for clustering tasks using Bregman information, showing superior ability to recover planted structures compared to structure-blind methods.

4. Results

A. Synthetic Experiments

• Pattern Recovery: In a clustering task with 60 elements grouped into three clusters, structure-aware divergence successfully recovered the ground-truth clusters even when distributions were sparsely sampled (low $m$) and had no overlapping elements. Structure-blind methods (using $Z=I$) failed to distinguish groups without overlap.
• Runtime: The proposed Jensen-Bregman Divergence (J-BD) was ~10x faster than the Wasserstein-1 distance (OT) for pairwise dissimilarity calculations. Vectorized implementations were even faster, scaling better with input size.

B. Application: Economic Geography (England & Wales)

• Data: 2021 Census data for 318 Local Authorities (LAs), focusing on 41 "tradable" occupations.
• Similarity Definitions: Compared "No Similarity," "Skill Similarity" (based on ONET skills), and "Co-location Similarity" (based on regional specialization).
• Findings:
  • Different similarity definitions led to qualitatively different regionalizations.
  • Co-location similarity revealed sector-specialized regions (e.g., a distinct agricultural region spanning Yorkshire, Cornwall, and Wales).
  • Skill similarity grouped regions based on workforce transferability, merging industrial and agricultural areas where blue-collar skills overlapped.
  • Structure-aware methods significantly altered the ranking of regions by diversity and representativeness compared to standard methods.

C. Application: Ecology (Rutor Glacier)

• Data: Vegetation abundance and functional traits (6 traits) across 59 plots in three successional stages (early, mid, late).
• Goal: Measure functional $\beta$-diversity (turnover in functional composition).
• Findings:
  • The structure-aware method reproduced established insights from Optimal Transport studies: mid and late successional stages had significantly lower functional $\beta$-diversity than the early stage, despite similar taxonomic turnover.
  • This confirmed that while species changed, their functional roles remained stable in later stages.
  • The method achieved these results with significantly lower computational cost than the OT-based approach.

5. Significance and Impact

• Bridging Theory and Practice: The work provides a mathematically rigorous yet computationally tractable framework for comparing distributions in structured domains, overcoming the "blindness" of standard information theory.
• Scalability: By replacing expensive optimization (OT) with closed-form algebraic operations, the method enables the analysis of large-scale datasets (e.g., high-resolution geographic data, large species trait databases) that were previously computationally prohibitive.
• Interpretability: The results in economic geography and ecology demonstrate that the choice of similarity structure is not merely a technical detail but fundamentally alters the interpretation of system dynamics (e.g., regional specialization, ecological succession).
• Flexibility: The framework is agnostic to how similarity is defined, allowing researchers to tailor the "structure" to specific domain questions (e.g., skills vs. location, traits vs. taxonomy).

In conclusion, the paper establishes Structure-Aware Divergences as a powerful, efficient, and flexible tool for analyzing complex systems where the relationships between elements are as important as the elements themselves.