Research map / Learning theory and algorithms / Clustering

MC-GTA: Metric-Constrained Model-Based Clustering using Goodness-of-fit Tests with Autocorrelations

ICML 2024 · Learning theory and algorithms › Clustering · approach: Clustering approximation algorithms · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MC-GTA, a model-based metric-constrained clustering method that uses a Wasserstein-2 generalized semivariogram and a hinge-loss objective derived from goodness-of-fit tests, avoiding EM iterations.

Problem

Metric-constrained clustering of temporal and spatial data ignores metric autocorrelation, and existing model-based methods (TICC/STICC) rely on EM with a soft metric penalty that is computationally unstable and slow to converge.

Approach

Replace the univariate semivariogram with a multivariate generalization using square Wasserstein-2 distance between per-observation GMRF models, fit a theoretical semivariogram, and penalize intra-cluster pairs whose W2^2 exceeds the shifted semivariogram via a hinge loss, interpreted as goodness-of-fit tests; clustering is then done with DBSCAN on the resulting pairwise loss matrix, with no EM it

Key results

• MC-GTA-w achieves best ARI/NMI on most datasets, e.g., Pavement ARI 77.64 / NMI 77.22 vs. TICC 62.27 / 61.89.
• On Gesture, MC-GTA-w reaches ARI 26.51 vs. TICC 12.20 (NMI 55.34 vs 23.20); MC-GTA-w also has NMI 42.97 on iNat2018-style table vs. STICC not converging.
• MC-GTA runs about 5-15x faster than TICC/STICC (e.g., Pavement 14s vs 508s) and converges where STICC returns NC on large datasets.

Measured effects reported in the paper

Surprising findings

• SKATER outperforms MC-GTA on the Climate dataset, which the authors attribute to contiguous cluster regions with disjoint boundaries.
• Metric-constrained MC-GTA is worse than GMM on the sparse Climate and iNaturalist spatial settings without a global prior, due to the sampling-radius dilemma.

Limitations

• Performance degrades on spatially sparse data (Climate), where neighborhoods must include metrically distant observations with high variance.
• Gaussian Markov Random Field assumption; extension to non-Gaussian MRFs left to future work.
• Introduces margin hyperparameter delta that must be tuned, and relies on Graphical Lasso covariance estimation.

Experimental setup

Datasets: Pavement Vehicle Gesture Climate iNaturalist-2018 NYC Foursquare POI NYC Landuse (PLUTO) synthetic 1D temporal synthetic 2D spatial

Benchmarks: Pavement Vehicle Gesture Climate iNaturalist-2018 POI Landuse synthetic temporal synthetic spatial

Metrics: ARI NMI runtime (s)

Baselines: k-Means DBSCAN HDBSCAN DTW PCK-Means MDST-DBSCAN SKATER GMM TICC STICC

Builds on: TICC STICC ST-DBSCAN Graphical Lasso DBSCAN

Closest papers by meaning

• Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints (AAAI 2021 · similarity 0.85)
• Approximation Scheme for Weighted Metric Clustering via Sherali-Adams (AAAI 2024 · similarity 0.85)
• Fast unsupervised ground metric learning with tree-Wasserstein distance (ICLR 2025 · similarity 0.83)
• Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.83)
• On the cohesion and separability of average-link for hierarchical agglomerative clustering (NeurIPS 2024 · similarity 0.82)
• SEC: More Accurate Clustering Algorithm via Structural Entropy (AAAI 2024 · similarity 0.82)