A Generative Block-Diagonal Model for Clustering

Junxiang Chen, Jennifer G. DyUAI 2016 · OpenReview

Abstract

Traditional clustering methods often struggle with complex data geometries or lack a rigorous probabilistic framework when operating on similarity matrices. We present the Block Mixture Model (BMM), a generative approach that models the block-diagonal structure of similarity matrices using Beta distributions. By treating the similarity matrix itself as observed data, BMM provides a robust alternative to spectral clustering. We derive a variational inference framework for the model and demonstrate its effectiveness on synthetic and real-world benchmarks, particularly in its ability to handle non-linear cluster shapes and structured noise.

Introduction

Clustering is a fundamental task in machine learning, typically addressed by modeling data distributions in feature space (e.g., Gaussian Mixture Models) or by analyzing the spectral properties of similarity matrices (e.g., Spectral Clustering). While feature-based models are often limited by rigid geometric assumptions—such as the assumption of ellipsoidal clusters in GMMs—similarity-based methods are frequently discriminative and lack a generative interpretation. This paper bridges this gap by proposing the Block Mixture Model (BMM), a generative model for similarity matrices that explicitly captures the expected block-diagonal structure of a well-clustered dataset. By adopting a probabilistic approach, BMM allows for the natural incorporation of prior knowledge and the quantification of model uncertainty.

The Block Mixture Model (BMM)

The core intuition behind BMM is that a similarity matrix, when ordered by cluster assignments, should exhibit high-similarity "blocks" along the diagonal and low-similarity "background" regions elsewhere. Since similarity values (derived from kernels like RBF or cosine similarity) are typically bounded between 0 and 1, we employ Beta distributions to model these elements.

Generative Process and Inference

The model assumes that diagonal blocks follow a Beta distribution skewed toward 1, while off-diagonal elements follow a background Beta distribution skewed toward 0. This flexibility allows the model to characterize both dense, highly similar clusters and sparse, noisy backgrounds within a unified mathematical framework. The graphical model for BMM is shown below:

Graphical model representation of the Block Mixture Model (BMM).

The model incorporates latent cluster indicators $z_{nk}$ and cluster probabilities $\pi$. Due to the intractability of exact posterior inference, we utilize Variational Inference (VI) to approximate the distributions. Parameter optimization for the Beta distributions is performed using the BFGS quasi-Newton algorithm during the M-step of the variational EM process, ensuring efficient convergence.

Experimental Evaluation

We evaluated BMM against Spectral Clustering, Non-negative Matrix Factorization (NMF), and Latent Network Models (LNM) across various datasets, including synthetic 2D shapes, handwritten digits (Semeion), and several UCI benchmarks such as the Iris, Wine, and Steel Plate Faults datasets.

Handling Complex Shapes and Structured Noise

A significant advantage of BMM over traditional mixture models is its ability to cluster data with complex, non-linear shapes. Because BMM operates on the similarity matrix rather than raw coordinates, it can successfully separate clusters that are not linearly separable in the original feature space, such as spirals or concentric circles.

BMM successfully clusters complex 2D shapes including spirals, nested moons, and concentric circles.

Furthermore, BMM demonstrates superior robustness to "structured noise"—scenarios where multiple valid clustering patterns may exist within the same matrix. By locking onto the strongest block-diagonal signal, BMM often outperforms spectral methods that may be misled by secondary structures in the data.

Real-World Benchmarks

On the Semeion handwritten digits dataset, BMM achieved superior results in binary classification tasks (e.g., distinguishing '6' from '8') compared to Spectral Clustering and NMF, particularly when using normalized similarity matrices. Across the UCI benchmarks, BMM consistently performed at or above the level of state-of-the-art discriminative methods, demonstrating its versatility across diverse domains.

Discussion and Conclusion

BMM offers a principled probabilistic framework for similarity-based clustering. Its use of Beta distributions provides the flexibility to model varying degrees of cluster density and background noise. However, the model currently assumes a uniform background distribution, which may be violated in datasets with highly heterogeneous inter-cluster similarities, such as the CMU Faces dataset where pose variations create complex off-diagonal patterns.

Future work includes extending BMM to a nonparametric framework using Dirichlet Process Mixtures to automatically infer the number of clusters $K$, and optimizing the computational efficiency of the variational inference steps for large-scale applications.

Summary updated

BibTeX
@inproceedings{chen2016generative,
  author = {Junxiang Chen and Jennifer G. Dy},
  title = {{A Generative Block-Diagonal Model for Clustering}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=_ihhopBd-p_},
}
Figure