When we group data using standard clustering algorithms like $k$-means or spectral clustering, we operate entirely within a feature space. The algorithm looks for points with similar attributes—such as similar traffic speeds, voxel activation levels, or voter demographics—and groups them together.
However, when data points are anchored to physical locations, feature-pure clustering frequently breaks down. It produces a "salt-and-pepper" effect: highly fragmented, non-contiguous clusters scattered across a map. As noted by Anwar et al., clustering road segments based solely on traffic features yields geographically nonsensical zones that are impossible for urban engineers to manage. Whether designing political districts (Stoica et al.), mapping functional brain regions (Wang et al.), or identifying communities (Liang et al.), real-world applications require that clusters maintain physical or logical connectivity.
To solve this, researchers embed spatial connectivity constraints directly into the clustering process. Instead of treating space as an afterthought, this paradigm forces clusters to form single, unbroken subgraphs within a spatial network.
The Core Mechanism: The Spatial Adjacency Graph
To enforce contiguity, we must translate physical space into a mathematical structure that a clustering algorithm can reason about. This is achieved by constructing a topological adjacency graph.
[Physical Space / Grid] [Topological Adjacency Graph]
+---+---+---+ (A) --- (B) --- (C)
| A | B | C | | | |
+---+---+---+ ======> | | |
| D | E | F | (D) --- (E) --- (F)
+---+---+---+ | | |
| G | H | I | (G) --- (H) --- (I)
+---+---+---+
In this graph, every discrete spatial unit (such as a census block, a pixel, or a voxel) is a node, and an edge exists if and only if two units share a physical boundary.
- Hor demonstrates how this graph structure can be used to strictly enforce contiguity in political redistricting, ensuring that no district is split into disconnected geographic islands.
- In neuroimaging, Wang et al. utilize a 26-neighborhood graph to constrain 3D brain voxels, ensuring that functional coherence is explicitly tethered to anatomical proximity.
By introducing this graph, the clustering problem changes fundamentally: the algorithm is no longer just partitioning a set of points; it is partitioning a graph into connected subgraphs.
Algorithmic Strategies for Enforcing Contiguity
Researchers have developed several distinct ways to combine feature similarity with graph-based connectivity constraints.
1. Constrained Agglomeration (Bottom-Up)
The most intuitive approach modifies hierarchical agglomerative clustering. In standard hierarchical clustering, the algorithm searches the entire dataset to find and merge the two closest clusters in feature space. In a spatially constrained variant, a merge is permitted only if the two clusters share an edge in the adjacency graph.
Hovy et al. use a connectivity matrix to restrict the merging of regional dialects, preventing geographically disjointed clusters that might otherwise form due to non-local linguistic similarities (like shared metropolitan speech patterns). Similarly, Vaca et al. restrict urban zone merges to adjacent clusters, using a single parameter to tune the trade-off between discovering niche, localized areas and broad, homogeneous districts.
This constraint also provides a massive computational benefit. As shown by Hoyos Idrobo, restricting feature merges to a predefined connectivity graph drastically reduces the search space, enabling linear-time clustering for high-dimensional images or brain scans.
2. Combinatorial and Flow-Based Encodings (Top-Down)
For exact optimization problems, such as the Connected Max-$k$-Cut or political redistricting, connectivity can be formalized using network flows or constraint programming.
Ermon et al. enforce spatial connectivity by incorporating flow-based encoding into pattern decomposition. By treating the assignment of a cluster label as a commodity flowing through the graph, the model mathematically prevents the generation of fragmented or physically impossible spatial distributions.
Alternatively, Bessiere et al. show that for planar graphs, connectivity can be maintained by forbidding alternating labeling patterns around graph faces. This topological shortcut avoids the extreme computational complexity of running global connectivity checks at every optimization step.
3. Probabilistic and Distance-Dependent Priors
Instead of hard constraints, probabilistic models use spatial decay functions to bias clusters toward contiguity. Janssen utilizes a distance-dependent Chinese Restaurant Process (dd-CRP) to parcellate fMRI data, where the probability of two data points sharing a cluster label decays as their physical distance increases. Ghosh proves that integrating these distance-dependent priors provides a mathematical guarantee that discovered segments form single connected components rather than fragmented patches.
Why In-Loop Constraints Outperform Post-Hoc Repairs
A naive approach to this problem might be to run a standard clustering algorithm first, and then apply a post-hoc "repair" step—such as merging small, isolated pixel fragments into their largest neighboring cluster (Reso et al.; Superpixel segmentation using Linear Spectral Clustering).
However, evidence from Connected Subspace Clustering demonstrates that iterative enforcement of connectivity constraints during optimization yields significantly lower reconstruction costs than post-hoc repairs.
Post-Hoc Repair:
[Feature Clustering] ===> [Fragmented Output] ===> [Blind Boundary Merge] = Low Quality
In-Loop Constraint:
[Feature Similarity + Graph Adjacency] ===(Iterative Optimization)===> [Spatially Coherent Output] = High Quality
When connectivity is enforced in-loop, the optimization process naturally finds boundaries that balance feature homogeneity with structural continuity. Post-hoc repairs, by contrast, blindly overwrite the feature-space optimization to satisfy the topology, destroying data fidelity.
Furthermore, enforcing connectivity during the loop acts as a powerful mathematical regularizer. Thirion et al. note that restricting agglomerative clustering to a regular lattice graph prevents percolation—the mathematical tendency of fast clustering algorithms to collapse into a single dominant "giant cluster." By forcing the algorithm to respect the underlying graph topology, the resulting spatial partitions remain balanced, stable, and physically interpretable.
Key Foundational Work
A Graphical Model for Simultaneous Partitioning and Labeling (2005) — contributed 2 concept elements to this direction.