Connectivity-Preserving Boundary Moves for Connected Subspace Clustering at Full Grid Resolution

Many scientific datasets are fields on a map: sea level on an ocean grid, activity on a brain lattice. When we cluster the time series at each location, we usually want the clusters to be connected regions. Ordinary clustering breaks the map into scattered speckles. The best current method for connected clustering of such data alternates between two steps. It fits a low-dimensional subspace to each region, then reassigns points and repairs any broken regions by greedily merging fragments. The repair step is irregular graph work: finding connected components and merging them one after another. That work does not map onto GPUs, and it is why the method was only run on a map with 8,160 points instead of the full dataset of 532,000.

We propose a different discrete step. Points are only allowed to move across the boundary between neighboring regions, and a move is allowed only if a fixed-size test on the point's 3×3 neighborhood certifies that the region it leaves stays connected. Every intermediate partition is therefore connected, so no repair is ever needed. Because the test is a local stencil (a fixed-size pattern check applied at every grid point), it runs in parallel on a regular tiled grid, just like a convolution. The question of whether to exploit sparsity becomes a measured choice: points that change label are few and scattered, but they lie along region boundaries. In the grid's natural spatial ordering, those boundaries touch a predictable set of hardware-sized tiles, so no costly reordering is required.

Core Claim

Connected $m'$-subspace $k$-clustering, introduced in Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy, partitions the $n$ vertices of a spatial adjacency graph into $k$ connected regions. Each region is fitted by an $m'$-dimensional affine subspace, and the goal is to minimize the total squared distance from each point to its region's subspace. That paper's heuristic, IterMerge, alternates between fitting subspaces and assigning points globally, followed by greedy fragment merging.

We claim the discrete block of this alternation can be replaced by conflict-free parallel sweeps of connectivity-certified boundary moves. The resulting method has four properties:

  1. It is a monotone block-coordinate method that stays inside the connected feasible set.
  2. It needs no component detection or merging after initialization.
  3. It reaches reconstruction cost at least as low as IterMerge on the 2° benchmark.
  4. It scales to the full-resolution Copernicus Marine Service (CMEMS) sea level grid, which the original work could not process.

The certificate comes from Reasoning about Connectivity Constraints, which builds constraint-programming propagators for connectivity. That paper shows that on planar graphs, connectivity of several shapes can be maintained by forbidding alternating in/out/in/out labelings around graph faces. We reuse this as a single-point test: removing point $v$ from its region is safe if the ring of $v$'s eight neighbors, labeled "in region" or "not in region," contains no such alternation and $v$ is not the region's last point. The test is sufficient but not necessary. It rejects some moves that a global check would allow, so the price of locality is extra conservatism. Measuring that price is a central part of the program.

Research Program

The objective is

$$ F(z, \{U_j, \mu_j\}) = \sum_{v=1}^{n} \big\| (I - U_{z_v} U_{z_v}^\top)(x_v - \mu_{z_v}) \big\|^2 \quad \text{s.t. each } \{v : z_v = j\} \text{ is connected in } G. $$

Here $x_v$ is the 365-dimensional monthly anomaly series at grid point $v$ and $z_v \in \{1,\dots,k\}$ is its region label. $U_j$ is an orthonormal basis for region $j$'s $m'$-dimensional subspace and $\mu_j$ is its offset. $G$ is the spherical ocean grid graph with land treated as holes.

The continuous block refits $U_j, \mu_j$ from per-region sufficient statistics: counts, sums and 365×365 scatter matrices. Each accepted move changes these by a rank-one addition to one region and a rank-one subtraction from another. This mirrors the discrete/continuous split in ARMOR, which alternates gradient updates of continuous factors with greedy least-squares updates of a hardware-constrained 2:4 mask. Here the discrete object is a connected partition rather than a sparsity mask.

The discrete block runs one sweep in four stages:

  1. Mark boundary points, meaning points with a neighbor in another region.
  2. For each boundary point, compute its residual under its own subspace and under the subspace of each adjacent region. There are at most eight candidates on the grid, usually one or two.
  3. Propose the best candidate if it lowers $F$.
  4. Accept the move only if the face-alternation test passes for the region being left. Joining a region the point already touches keeps that region connected automatically.

Simultaneous moves can interfere, so the grid is colored with nine colors on a stride-3 lattice. Points of the same color have disjoint 3×3 neighborhoods. Moves within one color class are therefore equivalent to applying them one at a time, which keeps both the connectivity guarantee and the monotone decrease of $F$ exact under parallel execution. Seams need specific handling: the longitude wrap is treated as ordinary adjacency, the polar rows are handled explicitly, and land cells count as "not in region" in the test. Each sweep and each refit is non-increasing in $F$, and the feasible set is finite. The alternation therefore terminates at a partition where no certified single move helps.

The known weakness of this design is that local moves may stall where IterMerge's global reassignment would jump. We study two escapes. The first is an exact variant that finds articulation points of each region once per sweep with the linear-time Hopcroft–Tarjan method, the one used in Reasoning about Connectivity Constraints. An articulation point is a point whose removal disconnects the region, so any boundary point that is not one may move. The second is a hybrid that runs one IterMerge step every $T$ sweeps.

The sparsity question is treated as a measurement. The set of points that can move changes every sweep, which is exactly the dynamic unstructured pattern for which SMaT is unsuitable. SMaT packs scattered nonzeros into Tensor Core tiles using a Jaccard-similarity row reordering, and that reordering is an expensive offline step. We avoid reordering altogether by keeping points in spatial (row-major or Hilbert-curve) order, so region boundaries fall into a limited set of fixed tiles. Residuals are computed densely inside active tiles only, in the spirit of the tile-aligned pruning of Tile-Wise Sparsity, which keeps GPU tiles dense while varying which parts of the matrix are computed. We will report tile occupancy, the fraction of tiles touched divided by the fraction of points active, as the direct measure of how much structure the spatial ordering recovers.

Baselines

The naive reference point is unconstrained subspace clustering with sparse subspace clustering via orthogonal matching pursuit (SSC-OMP). Connected Subspace Clustering reports that this method produced up to 1,966 disconnected components for 25 requested clusters on the 2° grid. It is run with the same $k$ and $m'$ and shows what ignoring topology costs.

The strongest existing competitor is IterMerge from the same paper. It is the only method that alternates subspace fitting with connectivity enforcement at every iteration. Across 160 configurations it was the strongest in 73.75% of cases and consistently beat Connected Ward's method. No absolute reconstruction cost or runtime for it on the 2° grid is reported in the material available on Lacuna. We will therefore rerun it ourselves on identical data, the same range of $k$ and $m'$, and identical initializations, with the same number of random restarts and the same wall-clock budget per configuration. The proposal beats it if either of two results holds:

  1. On the 2° grid, it matches or lowers the median reconstruction cost with a win rate above one half across the same 160-configuration sweep, at equal or lower wall-clock time.
  2. It completes the full-resolution grid, where IterMerge either fails to finish within the budget or finishes with a higher cost.

PostMerge, which runs unconstrained alternation and repairs connectivity once at the end, is included because it is the cheapest connected alternative. The same paper found it worse than IterMerge, so it serves as a lower bar. Connected Ward's method is included as the agglomerative baseline. Because Connected Subspace Clustering found that initializer rankings flip between $m'=0$ and $m'=15$, every method is started from both Ward and IterMerge outputs.

Two ablations isolate our key ingredients. The first swaps the local face test for the exact articulation-point test while keeping everything else fixed; this measures the cost of conservatism. The second swaps active-tile residual evaluation for dense evaluation of all points against all adjacent subspaces; this measures whether the sparsity machinery is worth anything.

Why not just…?

Why not just port IterMerge to a GPU and compute all residuals densely? For the residual computation alone this is a real threat. At full resolution, 532,000 points against 25 subspaces in 365 dimensions is a modest dense workload for a modern GPU. We expect dense residuals to be competitive, and the dense-versus-tile ablation will show this if so. The part that does not port well is IterMerge's repeated component detection and its sequential merging of the smallest fragment. Profiling IterMerge at 2°, 1°, 0.5° and 0.25° will measure what share of runtime the discrete step takes. The file flags this asymmetry, where the combinatorial block dominates each outer iteration, as a known limitation of alternating optimization. If that share turns out small, our speed claim fails, and the contribution reduces to the always-connected invariant and cost quality.

Why not just add coordinates or a soft spatial penalty to the features? Connected Subspace Clustering reports that the spatial-spectral hyperspectral method EGCSC still left dozens of disconnected fragments on this data. DCA combines deep embeddings with a 26-neighbor spatial graph on brain voxels, and it is likewise soft and can leave isolated voxels. A soft penalty needs a repair step anyway and adds a weight to tune. Our method has neither.

Why not just run fast linear-time agglomeration and stop? Recursive nearest-neighbor merging from Fast clustering for scalable statistical analysis on structured images avoids the giant-cluster collapse that single linkage suffers on lattices. It runs in about a second, but it never fits subspaces, so it cannot optimize our objective directly. We will use it as a full-resolution initializer and as a reference cost. If our sweeps do not improve substantially on its output, the alternation is not earning its cost.

Why not just allow any move that the exact articulation-point test permits? This is a live option, and it is our first ablation. If the exact variant reaches clearly lower cost at similar speed, the local certificate is the wrong choice and we will adopt the exact test with per-sweep batching.

Proposed Experiments

All experiments use the CMEMS global gridded sea level anomaly product, as in Connected Subspace Clustering. We first reproduce the 2° spherical grid with 8,160 points and the same 160 configurations of $k$ and $m'$, then move to 1°, 0.5° and full resolution with about 532,000 points. For every run we report:

  • reconstruction cost $F$;
  • a verified component count, which must equal $k$;
  • wall-clock time split into the continuous and discrete blocks;
  • number of sweeps to termination;
  • tile occupancy.

We run three decisive checks. The first tests whether certified local moves match IterMerge's cost at 2°; if not, locality is too restrictive. The second tests whether the rejection rate of the local test relative to the exact test stays low as resolution increases. Finer grids make regions thicker, so we expect fewer articulation-like points on the boundary. The third tests whether the discrete step's share of runtime drops from dominant, in profiled IterMerge, to minor, in our method, at full resolution.

A secondary check targets the role of the spatial ordering. We compare row-major and Hilbert-curve orderings for tile occupancy. As an upper bound we also run SMaT-style reordering recomputed every sweep, which should show why static spatial order is preferable when the active pattern keeps changing.