Abstract
In many real-world applications, data is organized into hierarchical structures, such as words within documents or tags within image collections. We introduce Multilevel Composite Transportation (MCT), a scalable framework for joint local and global clustering. By utilizing a specialized Optimal Transport formulation based on Kullback-Leibler (KL) divergence, MCT provides a robust optimization-based alternative to complex Bayesian nonparametric models, suitable for both continuous and discrete data regimes.
Introduction
In many datasets, observations are organized into groups, necessitating a multilevel approach to clustering. For instance, in a large-scale text corpus, words form topics within individual documents (local level), while documents themselves cluster into broader themes or genres (global level). Standard methods like K-means assume data independence and fail to capture these hierarchical dependencies. While Bayesian nonparametric models like the Hierarchical Dirichlet Process (HDP) address this, they often rely on computationally intensive Markov Chain Monte Carlo (MCMC) sampling, which limits their scalability.
Methodology: Multilevel Composite Transportation
The proposed MCT framework leverages the geometric properties of Optimal Transport to align hierarchical structures. The core innovation lies in the Composite Transportation Distance.
Distribution-Aware Metrics
Traditional Wasserstein distance typically employs Euclidean cost, which is often inappropriate for discrete data like word counts. MCT replaces this with KL divergence. This choice allows the model to naturally accommodate any data following an exponential family distribution, making it "distribution-aware."
Joint Optimization and Barycenters
MCT treats each group of data as a local mixture model. Global clustering is then achieved by finding the Wasserstein barycenter—the geometric average—of these local mixtures. Unlike two-stage approaches that cluster locally and then globally, MCT solves a joint optimization problem, allowing the model to "borrow strength" across groups. This is particularly beneficial for groups with sparse data.
To ensure computational efficiency, the authors employ entropic regularization and a coordinate descent algorithm, transforming the inference task into a series of fast iterative matrix operations.
Experimental Evaluation
The effectiveness of MCT was evaluated across synthetic and real-world datasets, spanning both continuous and discrete domains.
Synthetic Data
On synthetic discrete data consisting of "bar topics," MCT demonstrated a high degree of fidelity in rediscovering the underlying generative structures. As shown in the visual comparison of generated versus rediscovered data, the model accurately captures the latent topic distributions.
Real-World Performance
MCT was tested on the LabelMe dataset (continuous GIST features) and the NUS-WIDE dataset (discrete image tags).
- LabelMe: MCT achieved a Normalized Mutual Information (NMI) of 0.485, significantly outperforming K-means (0.37) and Wasserstein-means (0.423).
- NUS-WIDE: The advantage was more pronounced in the discrete domain, with MCT reaching an NMI of 0.423 compared to 0.356 for the nearest baseline.
Qualitative analysis of the NUS-WIDE results reveals that MCT successfully identifies semantically coherent clusters. For example, a "pet" cluster emerged containing tags such as bunny, adorable, and cute without prior supervision.
Conclusion and Future Work
Multilevel Composite Transportation offers a scalable, optimization-centric approach to hierarchical clustering. By integrating KL divergence into the Optimal Transport framework, it bridges the gap between the flexibility of Bayesian models and the efficiency of geometric optimization. Future research directions include the automatic estimation of cluster cardinalities and the incorporation of group-level metadata to further enrich the clustering context.
Summary updated