On efficient multilevel clustering via Wasserstein distances

Viet Huynh, Nhat Ho, Nhan Dam, Xuan Long Nguyen, Mikhail Yurochkin, Hung Bui, Dinh Phung

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

We propose a novel approach to the problem of multilevel clustering, which aims to simultaneously partition data in each group and discover grouping patterns among groups in a potentially large hierarchically structured corpus of data. Our method involves a joint optimization formulation over several spaces of discrete probability measures, which are endowed with Wasserstein distance metrics. We propose several variants of this problem, which admit fast optimization algorithms, by exploiting the connection to the problem of finding Wasserstein barycenters. Consistency properties are established for the estimates of both local and global clusters. Finally, experimental results with both synthetic and real data are presented to demonstrate the exibility and scalability of the proposed approach.

Original languageEnglish
Pages (from-to)6421-6463
Number of pages43
JournalJournal of Machine Learning Research
Volume22
Issue number1
Publication statusPublished - Jan 2021

Keywords

  • Multi-level clustering
  • Optimal transport
  • Wasserstein barycenter

Cite this