PaperlayerView exact revision on arXiv

Source-linked AI summary

Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy

Johanna Hillebrand, Jan Höckendorff, Jürgen Kusche, Kelin Luo, Heiko Röglin, Melanie Schmidt, Christian Sohler, Bernd Uebbing

arXiv:2608.14215v1cs.LG

TL;DR

Connected subspace clustering seeks partitions that are both subspace-similar and geographically connected, addressing regional analysis where global PCA can obscure localized signals. The paper proves strong approximation hardness and proposes a merging-based Lloyd-style heuristic that achieves connected regions and strong empirical performance.

  • Problem

    Global PCA can place regionally important, low-variance phenomena such as ENSO in higher-order modes, motivating contiguous regional partitioning for local analysis.

  • Method

    The paper combines subspace reconstruction with graph connectivity, then merges small components into adjacent clusters according to subspace fit until k connected regions remain.

  • Results

    The problem is NP-hard to approximate within factor Ω(|V'|^1/2−ε), while IterMerge attained the lowest final objective in 118 of 160 configurations (73.75%).

  • Takeaways & Limitations

    Combining subspace clustering with topological information offers a practical route to structure-aware clusterings.

  • Takeaways & Limitations

    The proposed approach is sensitive to the neighborhood graph and initialization.

Abstract

from arXiv · show

Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting where we measure variables at different physical locations. When grouping these measurements, we often want clusters that are both internally similar and physically coherent. Thus, we have a constrained clustering problem where the constraint models coherence. Motivated by an application in geodesy, where contiguous regions of the sea surface must be identified for principal component analysis, we introduce the Connected Subspace Clustering problem: given high-dimensional points and a connectivity graph, partition them into $k$ connected clusters, minimizing their total squared distance to the clusters' best-fit $m'$-dimensional affine subspaces. We prove that, even for $m' = 0$ and a grid graph with holes, the problem is NP-hard to approximate within $Ω(n^{1/2-\varepsilon})$ for every $\varepsilon>0$, where $n$ is the number of measurements. We then introduce an efficient Lloyd-style heuristic that alternates subspace fitting with an iterative merging procedure to enforce connectivity. Our method returns exactly $k$ connected regions by construction, whereas unconstrained methods leave up to $1{,}966$ disconnected fragments at higher cost. In a study of 160 configurations on global sea level time series, our merging-based repair is the strongest of four strategies in $73.75\%$ of cases, and consistently outperforms competitors such as (connected) Ward's method across all tested cluster counts. The resulting regions isolate signals aligning with climate indices such as the El Nino-Southern Oscillation and Indian Ocean Dipole. Although developed for geodesy, the approach applies to other spatially embedded multivariate time series, such as climate fields, remote sensing, neuroimaging, and sensor networks.

1 Introduction

Connected Subspace Clustering combines connectivity constraints with subspace reconstruction error to identify contiguous, coherent regions in high-dimensional spatial data. Motivated by sea level geodesy, the paper establishes strong hardness results and proposes a merging-based heuristic for connected, interpretable clustering.

  • Problem formulation: Connected Subspace Clustering combines a graph-topological connectivity constraint with minimizing squared distances to best-fit affine subspaces.The formulation targets contiguous regions with coherent dynamics in structured, high-dimensional datasets.
  • Theory: The problem is NP-hard to approximate within Ω(n^1/2−ε) for every ε > 0, even when m′ = 0 and the connectivity graph is a grid with holes.
  • Algorithm: The proposed heuristic alternates subspace fitting with a generic merging procedure that converts fragmented assignments into connected regions within Lloyd-style k-subspaces algorithms.
  • Application: Connected Subspace Clustering produces spatially coherent and interpretable sea-level regions while achieving the lowest displayed subspace-clustering cost, unlike unconstrained or connected Ward’s alternatives.Unconstrained methods produce fragmented clusters, whereas connected Ward’s method yields coherent but uneven patches that align less well with oceanographic phenomena.
  • Application: The sea level application replaces manual or geographically predefined partitions with data-driven contiguous regions whose total rank-m′ reconstruction error supports regional PCA.The resulting regions group ocean areas with similar sea level anomaly behavior for downstream analyses such as reconstructing pre-satellite-era sea level and separating steric and mass contributions.

2 Problem Definition, Hardness and Algorithmic Overview

Connected subspace clustering partitions high-dimensional measurements into k graph-connected clusters while minimizing squared distances to their best-fit m′-dimensional affine subspaces. The problem is strongly inapproximable even for m′ = 0 on grid graphs with holes, motivating a generic merging-based Lloyd heuristic that restores connectivity.

  • Problem Definition: The objective seeks k clusters whose induced graph subgraphs are connected while minimizing the total squared Euclidean distance to each cluster’s best-fit m′-dimensional affine subspace.Each best-fit subspace is obtained from the cluster mean and the top m′ left singular vectors of the centered data matrix.
  • Hardness: NP-hardness persists for m′ = 0: on grid graphs with holes, the problem is NP-hard to approximate within factor Ω(|V′|^1/2−ε) for any ε > 0.The hardness result holds in Euclidean t-dimensional space for any t ≥ k and follows from a reduction from vertex-disjoint paths on grid graphs.
  • Algorithmic Overview: The merging subroutine decomposes fragmented clusters, repeatedly selects a smallest component, and merges it into the adjacent cluster whose subspace best explains it until k connected components remain.It uses only adjacency information from a finite, simple, undirected neighborhood graph; experiments use a grid graph with holes.
  • Algorithmic Overview: The Lloyd-style heuristic alternates best-fit affine-subspace estimation with reconstruction-error reassignment, using component merging, postprocessing, spatial filtering, or locally restricted reassignment to maintain connectivity.Reassignments can violate connectivity, so the connectivity strategies are used to maintain or restore connected clusters.

3 An Algorithm for Connected Subspace

The algorithm alternates best-fit affine-subspace estimation with reassignment in a Lloyd-style scheme, then uses merging or locality restrictions to enforce spatial connectivity. Its connectivity-repair procedure returns exactly k connected clusters and runs in near-linear time on bounded-degree graphs.

  • 3.1 General Algorithm: The Lloyd-style algorithm alternates assigning points to nearest fitted m′-dimensional subspaces with recomputing those subspaces by principal component analysis.Initialization and convergence criteria require separate specification, while connectivity may be enforced after each iteration or once after termination.
  • 3.2 Initial Clustering: The five initialization methods combine connectivity-constrained agglomerative clustering, Conn-Ward, and connected greedy k-means++ to provide starting clusterings.The agglomerative variants use different dissimilarity measures, while Conn-KMeans++ post-processes k-means++ output to address spatial connectivity.
  • 3.3 Connectivity: Four connectivity strategies differ in when they repair or encourage connectivity: IterMerge, PostMerge, SmoothMerge, and IntegratedConn.IterMerge merges components after each iteration; PostMerge repairs only at the end; SmoothMerge uses Gaussian weighted label voting; IntegratedConn restricts reassignment to neighboring labels but still requires final merging.
  • 3.3 Connectivity: Connectivity repair builds component graphs, repeatedly merges the smallest disconnected component into an adjacent cluster preferred by most of its points, and stops with k connected components.The procedure prioritizes spatial coherence over original labels and can increase the objective function when enforcing connectivity.
  • 3.3 Connectivity: O(n(k + log n)) time is sufficient for connectivity repair on bounded-degree graphs, including the application’s grids, and O(nk) when k = Ω(log n).The implementation uses graph traversal, precomputed rankings, a min-heap, and union–find with path compression.

4 Experimental Evaluation

Across 160 sea-level clustering configurations, IterMerge most often achieved the lowest final objective, while Conn-Subspace improved valid initializations and outperformed Conn-Ward across tested cluster counts. Initialization quality depended on the objective and preprocessing, with unfiltered data sometimes making Agglo-ST unusable.

  • 4.1 Dataset, preprocessing and connectivity graph: The experiments used coarsened CMEMS sea-level anomaly data with 8,160 grid points, filtered temporally and spatially, and represented by a four-neighbor grid graph with holes.Longitude-wrap adjacency accounts for periodicity, and the evaluation uses the four-neighbor graph.
  • 4.2 Initialization methods: Agglo-ST was highly sensitive to preprocessing, often degenerating on unfiltered data into one dominant cluster and tiny clusters that could not support the requested subspace dimension.At k = 20, Agglo-ST was at least 8.98% higher than the next-worst method, while the other four initializations remained usable across tested configurations.
  • 4.3 Connectivity strategies: IterMerge achieved the lowest final objective in 118 of 160 configurations (73.75%), ahead of SmoothMerge, IntegratedConn, and PostMerge.The evaluation comprised 160 base configurations and 640 runs; two configurations lacked refined solutions because Agglo-ST on unfiltered data produced clusters too small for the requested subspace dimension.
  • 4.3 Connectivity strategies: Conn-Subspace lowered the objective from every valid initialization, with the largest reduction reaching 20.3% for Agglo-ST on unfiltered data at k = 15 and m′ = 30.The improvement held even for suboptimal starting partitions.
  • 4.4 Comparison with Conn-Ward: Conn-Agglo-Euc followed by Conn-Subspace with IterMerge attained the lowest objective for every tested k on both filtered and unfiltered data, outperforming Conn-Ward.Conn-Subspace can revise cluster assignments iteratively, whereas Conn-Ward cannot revise assignments after initial formation.

Comparison with Subspace-Clustering and Spatial-Spectral Methods

Connected Subspace Clustering outperforms unconstrained subspace-clustering and spatial-spectral baselines while uniquely returning exactly k connected clusters. Its regional sea-level partitions also isolate variability associated with major oceanographic structures and climate indices.

  • Baseline comparison: 14,473.1 versus 2,947.9 objective value at k = 25 on unfiltered data, while SSC-OMP produces up to 1,966 connected components compared with exactly 25 targeted clusters.EnSC reaches at most 222 connected components but its objective remains consistently above Conn-Agglo-Euc followed by Conn-Subspace with IterMerge at m′ = 30.
  • Baseline comparison: Our method returns exactly k connected clusters, whereas SSC-OMP, EnSC, EGCSC, and EKGCSC produce more connected components than requested and remain worse in every tested configuration.The compared baselines do not guarantee single-component clusters; EGCSC and EKGCSC are less fragmented than SSC-OMP and EnSC but still violate the target cluster count.
  • Implications for Sea Level Research: Regional decomposition reveals sea-level modes that global EOFs can blur, including clusters associated with the Agulhas current, Gulf Stream, ENSO-related variability, and the Indian Ocean Dipole.Cluster 8 spans much of the Atlantic basin, cluster 9 covers the eastern tropical Pacific, and cluster 13 corresponds to the IOD while extending beyond its core region.
  • Implications for Sea Level Research: Regional altimetry EOFs support targeted sea-level-driver analysis and may improve tide-gauge reconstruction, although inconsistencies at cluster boundaries require further study.The application uses the best-performing configuration, Conn-Agglo-Euc followed by Conn-Subspace with IterMerge, on filtered data with k = 15.

5 Conclusion · A Theory · A.1 Further related work

The paper concludes that combining subspace objectives with topological information enables practical structure-aware clustering, while identifying graph and initialization sensitivity as key limitations. Its related-work position distinguishes connected k-means from radius-based connected k-center and summarizes known hardness and approximation results, including the absence of grid-graph results.

  • 5 Conclusion: Combining the subspace clustering objective with topological information offers a practical route to structure-aware clusterings.The approach remains sensitive to the neighborhood graph and initialization.
  • 5 Conclusion: Future work should study simultaneous optimization of the objective and connectivity through bi-criteria optimization and extend the method to other datasets or settings.
  • A.1 Further related work: For unconstrained k-means, the problem is NP-hard for constant k [3] and constant m [34], while k-means++ achieves an O(log k)-approximation.State-of-the-art practical approximation algorithms improve this to an O(1)-worst-case guarantee.
  • A.1 Further related work: Connected k-center work considers minimizing maximum radius: solve trees optimally, while provide an O(log2 k) approximation for general connectivity graphs.
  • A.1 Further related work: Connected k-means is the m′ = 0 special case of connected subspace clustering, using squared Euclidean distances and a sum-based objective rather than radius-based connected k-center.
  • A.1 Further related work: [21] show that connected k-means on star-like graphs is NP-hard to approximate better than Ω(log n) and provide an O(log n)-approximation for that class.
  • A.1 Further related work: [14] show that connected metric k-median is solvable optimally on trees, while general graphs are NP-hard to approximate better than Ω(n1−ϵ) and admit an (n·log2 k)-approximation.
  • A.1 Further related work: There are no reported results for the special case of grid connectivity graphs.

A.2 Proofs for hardness of connected (k, p)- clustering problem · B Application · B.1 Dataset

The paper establishes strong inapproximability for connected clustering through a vertex-disjoint paths reduction, then motivates its sea-level application with satellite-derived SLA data products emphasizing either long-term homogeneity or per-timestep accuracy and spatial sampling.

  • B Application: The connected clustering formulation is instantiated as a constrained problem over spatially organized sea-level measurements, linking the theoretical model to the paper’s geodetic application.The supplied dataset passage identifies the satellite-derived SLA products underpinning this application.
  • A.2 Proofs for hardness of connected (k, p)- clustering problem: Connected (k, p)-clustering is NP-hard to approximate within Ω(|V′|^(1/2−ε)) on grid graphs with holes in Euclidean t-dimensional space for t ≥ k.The result holds for any ε > 0 and constant p ∈ N.
  • A.2 Proofs for hardness of connected (k, p)- clustering problem: The hardness reduction starts from the NP-complete vertex-disjoint paths problem on grid graphs with holes and constructs an expanded connectivity graph with attached gadgets.Selected grid edges are replaced by paths, and structured subgraphs are added around each terminal.
  • A.2 Proofs for hardness of connected (k, p)- clustering problem: If vertex-disjoint terminal paths exist, the constructed discrete clustering instance has cost at most |V| + |V|^2m; otherwise every solution has cost at least m^2.The two bounds distinguish feasible path instances from infeasible ones and yield the approximation gap.
  • A.2 Proofs for hardness of connected (k, p)- clustering problem: An α-approximation for continuous connected (k, p)-clustering can be converted in O(kn) time into a (2pα)-approximation for the discrete variant.This transfer lets the discrete inapproximability result imply hardness for the continuous Euclidean formulation.
  • B.1 Dataset: The application uses satellite-derived sea-level anomaly products from two principal sources: one emphasizes long-term homogeneity, while Copernicus Marine Service prioritizes per-timestep estimation accuracy and enhanced spatial sampling.The CMEMS dataset builds on the steady two-satellite merged constellation formed by TOPEX-Poseidon, Jason-1/2/3, and Sentinel-6A.

B.2 Reimplementation of Thompson and Merrifield

The reimplementation follows Thompson and Merrifield’s [40] average-linkage hierarchical clustering method using their spatial-temporal distance, without explicitly enforcing connectivity. Connectivity emerges only under sufficiently smooth data; otherwise, the segmentation can lack spatial coherence and isolate local extrema.

  • B.2 Reimplementation of Thompson and Merrifield: The reimplementation follows Thompson and Merrifield’s [40] average-linkage hierarchical agglomerative algorithm, implemented according to, without explicit connectivity enforcement.Starting from singleton clusters, it repeatedly merges the pair with minimum average-linkage distance until k clusters remain.
  • B.2 Reimplementation of Thompson and Merrifield: The distance combines geographic separation with time-series correlation, using Haversine spatial distance and Pearson correlation in the spatial-temporal dissimilarity.Pearson correlation ranges from −1 to 1, while the exponential transformation yields higher similarity for nearby, more correlated points; the normalization constant is c0 ≈4328.
  • B.2 Reimplementation of Thompson and Merrifield: Connected clusters arise only when the data is sufficiently smooth in space and time; otherwise, the method produces spatially incoherent segments and can isolate local extrema.The unfiltered-data setting is specifically associated with degraded performance and failure to capture meaningful structures.

B.3 EOFs and PCs for global sea level data

The first three global sea-level EOFs and PCs capture the long-term trend, seasonal cycle, and ENSO signal, respectively, although ENSO is partly mixed with other variability modes. Combining EOF decomposition with subspace clustering can reveal regionally coherent patterns that standard global EOF analysis may obscure.

  • EOFs and PCs: The first three EOFs and PCs capture the long-term trend, seasonal cycle, and ENSO signal, respectively.These results are shown in Figure B.1.
  • EOFs and PCs: The ENSO signal is partially mixed with other variability modes, a known limitation of EOF analysis.
  • EOFs and PCs: Combining subspace clustering with EOF decomposition offers a practical way to extract regionally coherent sea-level variability patterns that standard global EOF analysis may not clearly represent.

B.4 Implications for sea level research … C.2 Details on connectivity methods

Connected subspace clustering isolates contiguous sea-level regions whose dominant signals reveal ENSO-related structure and enable regional reconstruction, while regional separation may create boundary inconsistencies requiring further study. The supplied implementation material expands the connectivity algorithms with pseudocode and distance-recomputation details.

  • B.4 Implications for sea level research: Global EOFs primarily capture the long-term trend and seasonal cycle, with corresponding principal components showing trend and annual variation.The seasonal cycle is associated with solar forcing, ocean heat uptake, and varying land–ocean freshwater fluxes.
  • B.4 Implications for sea level research: Subspace clustering exposes localized sea-level modes: trend and annual-cycle signals dominate most subregions, whereas ENSO dominates the tropical Pacific.Regional separation enables analysis focused on dominant signals and drivers relevant to each region.
  • B.4 Implications for sea level research: Regional signal separation may create inconsistencies at borders between neighboring regions, warranting further investigation.This limitation qualifies the use of regional EOF-based reconstruction.
  • B.4 Implications for sea level research: Contiguous ocean regions enable regional reconstruction of historic sea levels before the altimetry era and may support regional tide-gauge reconstruction using EOFs.The approach could be applied where tide-gauge record density is good; prior eastern-Pacific application is noted as.
  • C Implementation: The appendix states that the main paper skipped the following implementation code, while the accompanying subsection expands the algorithms discussed in Subsection 3.3.These passages identify the implementation material as supplementary algorithmic detail rather than a new empirical result.
  • C.1 Accompanying pseudocode: Average-linkage connectivity updates recompute distances only for clusters in the new neighborhood; shared neighbors use a weighted sum of their two previous distances.Distances are recomputed when a neighboring cluster was adjacent to only one merged cluster, while shared-neighbor distances use both existing values.
  • B.4 Implications for sea level research: Clusters 6 and 9 fit eastern and western Pacific regions, whose first EOFs strongly correlate with ENSO, while cluster 8 shows weak correlation.The annual signal appears in the second EOF for the ENSO-related regions.

C.2.1 Establishing connectivity via merg- · C.2.3 Filtering

The connectivity-merging approach converts disconnected input clusters into exactly k connected regions by iteratively merging small components into neighboring clusters. A Gaussian filtering alternative reduces noise and promotes cohesive regions but may still require connectivity repair.

  • C.2.1 Establishing connectivity via merg-: The method assumes locations and time series are sufficiently correlated that disconnected input clusters consist of small contiguous regions suitable for merging.
  • C.2.1 Establishing connectivity via merg-: The merging algorithm repeatedly removes the smallest connected region and assigns it to the neighboring cluster receiving the largest majority preference until exactly k regions remain.Connected components are formed from same-cluster adjacent points, and each merge decreases the region count by one.
  • C.2.1 Establishing connectivity via merg-: The merging routine runs in O(|E| + n(k + log n)) time, becoming O(n(k + log n)) on bounded-degree graphs and O(nk) when k = Ω(log n).The implementation combines distance and score precomputation, heap maintenance, winner scans, union–find, and neighborhood-edge scanning.
  • C.2.1 Establishing connectivity via merg-: The merging loop executes at most z_0 − k times because every iteration decreases the number of connected components by at least one.
  • C.2.3 Filtering: Gaussian filtering assigns each point a new label using normalized kernel-weighted cluster support within a Haversine-distance neighborhood of radius 3σ.The parameter σ = h/1.178 makes the Gaussian weight fall to half its maximum at half-width h.
  • C.2.3 Filtering: Filtering reduces noise and creates more cohesive regions, but it does not necessarily produce exactly k connected clusters, so the connectivity-repair step is also executed.

D Experiments

The experiments use a parallelized spherical Gaussian filter to smooth data on a geodetic latitude/longitude grid while respecting Earth’s curvature.

  • D Experiments: The study implements a parallelized spherical Gaussian filter because standard pointwise kernels do not account for curvature on Earth’s geodetic grid.The filter operates over a structured spatial grid defined on Earth’s surface.

D.1 Data Preprocessing · D.2 Subspace Clustering · D.3 Hyperspectral Imaging

The appendix details curvature-aware, missing-data-robust preprocessing and evaluates connected subspace clustering against unconstrained subspace and hyperspectral methods. Unconstrained baselines produce fragmented or less coherent regions, while EGCSC yields more coherent clusters than EKGCSC in the reported comparison.

  • D.1 Data Preprocessing: The preprocessing filter performs curvature-aware Gaussian spatial smoothing while excluding NaN values from weighted averages and supporting independent parallel processing across time steps and locations.Neighbor weights use great-circle Haversine distance, cutoff radius r_c = 3σ, and a user-specified half-width h.
  • D.1 Data Preprocessing: The filter produces a spatially smoothed dataset that respects Earth’s curvature and remains robust to missing observations.Validity is determined by excluding locations whose spherical neighborhoods contain invalid observations across all time steps.
  • D.1 Data Preprocessing: Additional experiments compare the proposed approach with representative subspace-clustering and hyperspectral-segmentation algorithms selected for stability, feasibility, and solution quality.The appendix notes that other algorithms were also tested but were not selected for presentation.
  • D.2 Subspace Clustering: Unconstrained SSC-OMP and EnSC produce fragmented clusterings, with SSC-OMP consistently yielding less coherent clusters and EnSC forming multiple connected components on filtered data.The comparison covers k = 8, 15, 20, and 25 on filtered and unfiltered data, using γ = 50 with otherwise default parameters.
  • D.3 Hyperspectral Imaging: The hyperspectral comparison evaluates GraphConvSC’s EGCSC and EKGCSC variants after adapting them for spherical, incomplete inputs and selecting parameters that produced the best results.The experiments use code from and include configured parameters reported in Table D.1.
  • D.3 Hyperspectral Imaging: EGCSC produces more coherent clusters than EKGCSC in the reported hyperspectral-imaging examples.Example clusterings are shown in Figure D.1.
  • D.3 Hyperspectral Imaging: The appendix reports subspace-clustering costs before and after applying the connectivity repair methods, alongside comparisons with the subspace and hyperspectral baselines.Tables organize initial costs and changes from Alg. 3.1 using the connectivity methods described in Subsection 3.3.

D.4 Results

The results compare distances from points to fitted subspaces across filtered and unfiltered data for 8, 15, 20, and 25 clusters, while noting that Agglo-ST can fail on unfiltered inputs.

  • D.4 Results: Agglo-ST performs poorly on unfiltered data, producing one dominant cluster and other clusters too small to compute m′-dimensional subspaces.Its corresponding table values are therefore missing for the affected unfiltered configurations.
Loading 2608.14215v1…