Clustering in Block Markov Chains

Jaron Sanders, Alexandre Proutière, Se-Young Yun

Abstract

This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the $n$ possible states are divided into a finite number of $K$ groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper, we devise a clustering procedure that accurately, efficiently and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense.

Introduction

In complex dynamical systems ranging from robotics to economics, modeling often involves Markov chains with massive state spaces. To maintain computational tractability, researchers frequently employ state aggregation or clustering to group similar states. While the Stochastic Block Model (SBM) is a well-established framework for clustering static graphs, this research addresses the more dynamic challenge of clustering states based on an observed trajectory—a sample path through the state space.

In a Block Markov Chain (BMC), $n$ states are partitioned into $K$ hidden clusters. States within the same cluster share identical transition probabilities to other clusters. The primary objective is to recover these clusters using only a single observed trajectory $X_0, X_1, \dots, X_T$.

A visualization of a trajectory $X_T$ through a state space where states are grouped into hidden clusters.

This problem introduces unique challenges compared to static graph clustering. First, consecutive observations in a trajectory are dependent, unlike the independent edges in an SBM. Second, there is a fundamental question of detectability: how long must the trajectory $T$ be to allow for accurate cluster recovery?

Methodology: Reaching the Fundamental Limit

The authors approach the problem by first defining the theoretical boundaries through information theory and then building an algorithmic toolset to reach them.

Information-Theoretic Lower Bound

Using a "change-of-measure" argument, the paper derives a quantity $I(\alpha, p)$ that characterizes the inherent difficulty of clustering a specific BMC. This derivation proves that if the trajectory length $T$ is below a certain threshold relative to this value, no algorithm can reliably recover the clusters. This defines the fundamental detectability limit for the system.

Two-Stage Optimal Algorithm

To achieve recovery at this fundamental limit, the authors developed a two-stage procedure:

  1. Spectral Clustering: The algorithm constructs an empirical transition matrix from the sample path. It includes a "trimming" step to remove states visited with extreme frequency (reducing noise) before performing a Singular Value Decomposition (SVD). This provides a "rough" initial clustering that is asymptotically accurate.
  2. Cluster Improvement Algorithm (CIA): Because spectral methods alone often fall short of the exact recovery limit, a recursive refinement step is introduced. The CIA uses the initial estimate to calculate likelihoods and iteratively reassigns states to the clusters they most likely belong to based on the full observed path.

Key Results and Insights

The research identifies that exact recovery becomes feasible when the trajectory length $T$ scales on the order of $n \ln n$. This mirrors results in SBMs but accounts for the temporal dependencies of Markovian dynamics.

A critical insight is the role of mixing time. If the Markov chain does not sufficiently explore the state space or transition between clusters, the resulting sample path bias makes clustering impossible. Furthermore, the framework does not assume reversibility, making it applicable to a broader range of real-world directed dynamics.

Numerical simulations on synthetic datasets (e.g., $n=300$ states, $K=3$ clusters) validated these findings. The two-stage algorithm achieved near-perfect accuracy (99.7%) after just a few iterations of the refinement step, demonstrating that it reaches the information-theoretic optimality as $n \to \infty$.

Conclusion and Future Directions

This work provides a rigorous foundation for state aggregation in complex systems by identifying the fundamental limits of BMC clustering. While the current model assumes a known number of clusters $K$ and focuses on uncontrolled chains, it opens the door for significant advancements. Future research aims to extend these principles to controlled Markov chains (Markov Decision Processes), which could drastically accelerate Reinforcement Learning through automated state abstraction.

Summary updated

Abstract

This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the $n$ possible states are divided into a finite number of $K$ groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper, we devise a clustering procedure that accurately, efficiently and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense.
BibTeX
@article{sanders2020clustering,
  author = {Jaron Sanders and Alexandre Proutière and Se-Young Yun},
  title = {{Clustering in Block Markov Chains}},
  journal = {The Annals of Statistics},
  year = {2020},
  doi = {10.1214/19-aos1939},
}
Figure