Cascade of Phase Transitions for Multi-Scale Clustering

Tony Bonnaire, Aurélien Decelle, Nabila Aghanim

Abstract

We present a novel framework exploiting the cascade of phase transitions occurring during a simulated annealing of the Expectation-Maximisation algorithm to cluster datasets with multi-scale structures. Using the weighted local covariance, we can extract, a posteriori and without any prior knowledge, information on the number of clusters at different scales together with their size. We also study the linear stability of the iterative scheme to derive the threshold at which the first transition occurs and show how to approximate the next ones. Finally, we combine simulated annealing together with recent developments of regularised Gaussian mixture models to learn a principal graph from spatially structured datasets that can also exhibit many scales.

Introduction

Clustering high-dimensional data often involves navigating complex energy landscapes. Traditional methods like $k$-means or standard Expectation-Maximization (EM) for Gaussian Mixture Models (GMMs) are prone to getting trapped in local maxima and require a pre-specified number of clusters ($K$). This paper proposes a framework that treats clustering as a physical process, utilizing simulated annealing to observe a "cascade of phase transitions" as the model temperature (variance) is lowered. By tracking these transitions, researchers can automatically uncover hierarchical structures without needing to know the "correct" number of clusters in advance.

Methodology: Annealing and Stability

The core approach involves slowly decreasing the variance $\sigma^2$ of GMM components, viewing the negative log-likelihood as "free energy." The authors distinguish between two strategies:

  • Hard Annealing: A global variance is enforced across all components, which is excellent for identifying the primary scales of a dataset.
  • Soft Annealing: An inverse-Gamma prior is introduced on the variances, allowing individual components to adapt their local size while following a global cooling schedule. This is specifically designed for complex cases like overlapping or nested clusters.

Critically, the authors use Linear Stability Analysis to derive the exact threshold ($T_c$) at which the first split (phase transition) occurs. This threshold corresponds to the maximum eigenvalue of the data covariance matrix, providing a rigorous starting point for the annealing process.

Multi-Scale Hierarchical Detection

As the temperature drops, components undergo successive splits, revealing the data's hierarchical structure. The authors track the ratio $\Gamma_k/\sigma^2$ (weighted local covariance over global variance). When this ratio approaches unity, it indicates that a component has resolved a physical structure at that scale. This allows for an a posteriori interpretation: by over-specifying $K$, the annealing process naturally groups components, and the $\Gamma_k/\sigma^2$ metric identifies when real structures are resolved.

Figure 3: Hierarchical clustering of a 10-cluster 5D dataset. The top panel shows the trajectories of components in the PC1-PC2 plane. The bottom panels show the evolution of the size ratio for different macro-clusters as a function of the annealing parameter.

Resolving Nested Structures with Soft Annealing

While hard annealing excels at identifying distinct scales, it can struggle with nested clusters (e.g., a dense cluster within a sparse one). Soft annealing addresses this by allowing components to "relax" locally. The paper demonstrates that while hard annealing might fail to distinguish these overlapping densities, soft annealing successfully recovers both the nested structure and the correct variances for both components.

Figure 4: Soft annealing applied to nested clusters. The top panel illustrates the trajectories resolving the inner and outer clusters. The bottom panel shows the size ratios and (inset) the evolution of the order parameter Q and variance estimation accuracy.

Key Insights and Results

  • Clustering as a Phase Transition: The splitting of a cluster into sub-clusters is a physical transition. The first split always occurs along the direction of the data's first principal component.
  • Robustness: The method accurately estimated cluster variances even when 70% of the data points were removed in sparse sampling tests.
  • Scale Independence: The 2D diagrams produced allow for analysis of the annealing process regardless of the actual dimensionality of the data space.

Conclusion

By framing clustering as a sequence of phase transitions, this method provides a robust, scale-independent way to uncover hierarchical structures. Future work aims to connect these GMM phase transitions to latent representation learning in deep models like Restricted Boltzmann Machines, potentially offering new insights into how neural networks organize information.

Summary updated

Abstract

We present a novel framework exploiting the cascade of phase transitions occurring during a simulated annealing of the Expectation-Maximisation algorithm to cluster datasets with multi-scale structures. Using the weighted local covariance, we can extract, a posteriori and without any prior knowledge, information on the number of clusters at different scales together with their size. We also study the linear stability of the iterative scheme to derive the threshold at which the first transition occurs and show how to approximate the next ones. Finally, we combine simulated annealing together with recent developments of regularised Gaussian mixture models to learn a principal graph from spatially structured datasets that can also exhibit many scales.
BibTeX
@inproceedings{bonnaire2021cascade,
  author = {Tony Bonnaire and Aurélien Decelle and Nabila Aghanim},
  title = {{Cascade of Phase Transitions for Multi-Scale Clustering}},
  booktitle = {Physical},
  year = {2021},
  doi = {10.1103/physreve.103.012105},
}
Figure