LMCC-MBC: Metric-Constrained Model-Based Clustering with Wasserstein-2 Distance of Gaussian Markov Random Fields

Problem: This paper studies a clustering problem for data with special properties like time or spatial positions. This paper focuses on the case when there is the effect of metric autocorrelation in data, which means the variance of feature vectors is positively correlated to their temporal/spatial distances.

Modelling: The authors propose a metric-constrained model-based model that leverages the correlation between adjacent estimated models and their locations in metric space. They use Gaussian Markov Random Fields to model inter-observation dependency and use Wasserstein-2 distance to measure the distance between estimated model parameters. Because of the metric autocorrelation, they use a metric penalty that decreases as distance increases.

Key results: From the experimental results, their algorithm appears to be computationally more efficient than other methods and has better performance in terms of ARI and NMI.

This work attempts to address the metric autocorrelation problem in model-based clustering. To be specific, each data sample is modeled by a Gaussian Markov Random Field, and the distance between GMRFs are measured by Wasserstein-2 distance. The conventional clustering assumption objective is then optimized to minimize intra-cluster distances and maximize inter-cluster distances. The authors argue that the combination of Wasserstein-2 distance and GMRF is cautiously chosen and provide some theoretical analyses.

In this paper, the authors focus on metric-constrained clustering (when clustering is based not only on the features of the data points but also on constraints in a metric space (time, geo data points). Within that framework, they propose a new metric-constrained model-based clustering approach, LMCC-MBC (Locally Monotonically and Continuously Constrained Model-Based Clustering) optimized to maximize intra-cluster cohesion and inter-cluster separation, working as follows:

-For each data point, compute the neighboring set of points in the metric-constraint space (not using the features) and fit a Gaussian Markov Random Field model with Graphical Lasso algorithm.

-For each pair of observations, compute model and metric distances (at this stage, we still don’t leverage features of the data points).

-Compute a semivariogram from the two distances and $\rho$ the range of the fitted semivariogram

-Compute weighted distance matrix M based on model, metric distances, semivariogram, $\rho$

-Run the some density-based clustering method (ex: DBSCAN) on M for the final clustering partition.

Wasserstein-2 distance is used as the model distance.

Q1: Theoretical soundness of LMCC-MBC and the generalized model-based semivariogram

A1, Part 1: Interpreting LMCC-MBC loss as goodness-of-fit tests

We wish to clarify the soundness of our design of the LMCC-MBC loss function as well as the theoretical interpretation of our proposed generalized model-based semivariogram from the perspective of goodness-of-fit tests. LMCC-MBC is effectively minimizing the hinge loss penalty of data point pairs that do not pass the goodness-of-fit test (see Appendix 7.4, Eq 16). The loss combines two types of tests -- those independent to metric autocorrelation and those dependent to metric autocorrelation. Please see a detailed discussion in Appendix 7.4. Here we present a brief summary:

Wasserstein distance is commonly used for carrying out goodness-of-fit tests (Panaretos&Zemel 2018): Given the empirical distribution $µ_n$ associated with the sample $X_1, . . . ,X_n ∼ µ$ and $Y_1, . . . , Y_m ∼ ν$ with corresponding empirical distribution $ν_m$, the squared Wasserstein-2 distance $d_m^2 = W_2^2(µ_n, ν_m)$ is a test statistic for the null hypothesis $µ = ν$. It follows a normal distribution (Panaretos&Zemel 2018, Eq 6) with the Wasserstein-2 distance of the true underlying models as the mean. We do not have access to these means, and use empirical means (both with and without metric autocorrelation) in their places. The expected Wasserstein-2 distance for a given metric distance bin is part of the goodness-of-fit tests, and we formally define it as Model-based semivariogram in Section 4.1 since it has similar form to the classical semivariograms.

A downstream bottom-up clustering algorithm (e.g. DBSCAN) tries to find the clustering with the best sum of goodness-of-fit test value. This can be interpreted as finding clustering assignments that maximize the total significance of both significance tests.

References:

Statistical Aspects of Wasserstein Distances (Panaretos&Zemel 2018)

A1, Part 2: Main contribution of our work -- Goodness-of-fit test vs likelihood-based loss functions

The most important contribution of our work is a novel family of clustering objectives -- i.e., instead of optimizing the total data likelihood, we propose to minimize the number of failed goodness-of-fit tests, which compare pairs of data points and their underlying models in the clustering. The goodness-of-fit tests can integrate metric autocorrelation as part of the mean statistics. Please see detailed discussions in Appendix 7.4, but here we provide a brief summary:

Existing model-based clustering algorithms formulate their clustering objective from the perspective of data likelihood -- for example, in TICC and STICC. Although data likelihood as a loss function fits well with model selection criteria such as the Akaike Information Criterion (AIC), it also leads to non-trivial top-down optimization procedures such as EM, which have several drawbacks: Firstly, the EM step is very time-consuming and takes many iterations to converge. Secondly, the clustering result relies heavily on the initial assignment, and the optimization is subject to local optima. Thirdly, tuning the hyper-parameters (e.g., number of clusters) requires expensive retraining. Finally, the data likelihood objectives have a lack of flexibility when modeling constraints such as spatial metric autocorrelation as a generative process.

In order to enable efficient and flexible bottom-up clustering, we propose to formulate the loss function in terms of only pairwise computations between data points. Our solution mainly relies on goodness-of-fit tests (i.e., whether two samples come from a statistically identical distribution) as the pairwise computation. Please see a detailed discussion in Appendix 7.4.

References:

https://en.wikipedia.org/wiki/Akaike_information_criterion

Q4: Ablation study on tuning hyperparameters

A4: We added an ablation study to investigate the influence of shift hyperparameter and the number of neighbors in Appendix 7.6 (Figure 4) using the most complicated iNaturalist 2018 dataset. We show that the search space of single hyperparameters is nearly convex. Thus, we can easily and quickly tune the hyperparameters by hierarchical grid search.

For every hyperparameter choice, we do not need to re-compute the covariance matrices. Instead, we only need to re-run the distance-based clustering algorithm. Thus the time complexity of a complete grid search is only $O(ABn^2)$, where $A$ and $B$ are the grid sizes of the number-of-neighbor hyperparameter and the shift hyperparameter.

Instead, the competing baselines TICC/STICC must re-run the entire algorithm when tuning hyperparameters. That means the complete grid search is $O(ABCKn^2d^2)$, even if we only tune the most important \lambda and \beta hyperparameters.

Q3: Theoretical and Empirical Space-and-Time Complexity Analysis

A3: First we show that the overall time complexity of LMCC is $O(n^2d^2)$:

Here, $d$ is the data dimension, $n$ is the number of data points, and $K$ is the cluster number. Firstly, we need to estimate covariance matrices for each data point, which is $O(n^2\cdot d\cdot min(n,d))$. Since in most cases, $n >> d$, the complexity becomes $O(n^2d^2)$. After estimating the covariances, we compute the pairwise Wasserstein-2 distances, which is again $O(n^2d^2)$, because we need to do matrix multiplication ($O(d^2)$) $n^2$ times. Finally, we apply a distance-based clustering algorithm like DBSCAN on the Wasserstein-2 distance matrix, which is again $O(n^2)$. Thus the overall time complexity of LMCC is $O(n^2d^2)$.

Next, we show that the complexities of the SOTA models (TICC and STICC) are $O(C\cdot K\cdot n^2d^2)$, where $C$ is how many iterations it takes to converge. $C$ usually increases with $K$ and $n$. This is because as $K$ and $n$ increase, it is harder to stabilize the cluster assignment.

TICC/STICC needs to 1) compute an initial cluster assignment by kMeans, which is $O(n^2)$; 2) estimate cluster-wise covariance matrices and compute the likelihood of each data point against each cluster, which is $O(K\cdot n^2d^2)$; 3) update cluster assignment, which is reported $O(K\cdot n)$ in the original papers; 4) repeat (1) to (3) C times until convergence. Thus the overall time complexity is $O(CK\cdot n^2d^2)$. This means, theoretically the execution time of TICC/STICC is $C\cdot K$ times longer than that of LMCC-MBC.

We also evaluated the empirical time complexity of each algorithm. Please refer to the “RT” column in Table 2 of Appendix 7.5. We can see that TICC/STICC is much slower than our LMCC-MBC. Notice the time TICC/STICC takes highly depends on how many iterations it takes to converge.

The spatial complexity of both LMCC and TICC/STICC is $O(n\cdot d^2)$, since all we need to store is the covariance matrices of each data point.

We have added these as an additional section in Appendix 7.5.

Q2: The choice of Wasserstein-2 distance, GMRF, and other components

A2: We wish to summarize the reasons we choose Wasserstein-2 distance and GMRF here.

1) The choice of Wasserstein-2 distance

As is stated in Part 1 of the general rebuttal, theoretically we need a goodness-of-fit statistic to investigate two random samples and test whether their underlying models are statistically identical. Wasserstein-2 distance is one of the statistics. The reason why Wasserstein-2 is unique is that it is the only computable statistical distance that metricizes weak convergence (Gibbs & Su, 2002). That means, even though other statistics such as KL-divergence can also be used to quantify how similar two distributions are, only Wasserstein-2 distance guarantees that when the distance becomes 0, two distributions are the same. This is a stronger encouragement for intra-cluster cohesion.

2) The choice of GMRF

The choice of the model is task-specific, and Wasserstein-2 distance can be applied to other types of models. The GMRF used in our study enjoys computational efficiency. While there are approximate algorithms that compute Wasserstein-2 distance between two arbitrary distributions, the Wasserstein-2 distance between 2 normal distributions has a closed form and can be very easily computed. LMCC can be easily applied to non-GMRF problems by changing the way we compute Wasserstein-2 distance. We will explore non-GMRF LMCC-MBC in future works.

3) The choices of other components such as Graphical Lasso and DBSCAN

The estimation of the covariance matrices (of GMRF) for each data point (e.g., Graphical Lasso) and the distance-based clustering (e.g., DBSCAN) afterward, do not rely on the choice of specific implementations. For example, Graphical Lasso can be replaced with Minimum Covariance Determinant (MinCov) or Shrunk Covariance (Shrunk), and DBSCAN can be replaced with HDBSCAN or OPTICS. In Appendix 7.7.1 and 7.7.2, we added ablation studies that compare the clustering performances of different LMCC variances by using different covariance matrix estimation algorithms and different distance-based clustering algorithms on the Pavement dataset. Please refer to Table 3 and Table 4 for the experimental results (we will add experiments for all datasets for the final version). The result shows that though using different implementations of covariance matrix estimation and distance-based clustering affects the clustering performance, all variations of LMCC-MBC still significantly outperform the strongest baselines. For example, LMCC with MinCov achieves 80.82 ARI and 73.78 NMI on the Pavement dataset compared to 77.64 ARI and 77.22 NMI with Graphical Lasso, while the baseline TICC only achieves 62.27 ARI and 61.89 NMI.
The analysis above justifies both theoretically and empirically that LMCC-MBC is a generic clustering framework and not a simple combination of existing components. The complete ablation experiment results can be found in Table 3, Appendix 7.7.

This paper advocates for using the Wassestein-2 distance to measure discrepancy between GMRFs in a model-based clustering framework. It includes some nice technical novelty but ultimately the reviewers are lukewarm on the extent of the contributions. Several reviewers appreciated the thoughtful rebuttal but even after slightly adjusting their scores upward, the paper falls below the bar and can be improved by incorporating some of these constructive criticisms

Reject