# Bayesian contiguity constrained clustering, spanning trees and dendrograms

arXiv: https://arxiv.org/abs/2302.12546 · HTML: https://mlsanity.com/paper/2302.12546/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2023.

## Built on by (most cited first, 2 of 2)

- [A Short-Term Predict-Then-Cluster Framework for Meal Delivery Services](https://mlsanity.com/paper/2501.08466/) (2025)
- [Scalable inference of spatial regions and temporal signatures from time series](https://mlsanity.com/paper/2605.05008/) (2026)

## Abstract (arXiv)

Clustering is a well-known and studied problem, one of its variants, called contiguity-constrained clustering, accepts as a second input a graph used to encode prior information about cluster structure by means of contiguity constraints i.e. clusters must form connected subgraphs of this graph. This paper discusses the interest of such a setting and proposes a new way to formalise it in a Bayesian setting, using results on spanning trees to compute exactly a posteriori probabilities of candidate partitions. An algorithmic solution is then investigated to find a maximum a posteriori (MAP) partition and extract a Bayesian dendrogram from it. The interest of this last tool, which is reminiscent of the classical output of a simple hierarchical clustering algorithm, is analysed. Finally, the proposed approach is demonstrated with real applications. A reference implementation of this work is available in the R package gtclust that accompanies the paper (available at http://github.com/comeetie/gtclust)