Selective inference after convex clustering with ℓ1 penalization

François Bachoc, Cathy Maugis-Rabusseau, Pierre Neuvial

TL;DR

This paper tackles the challenge of making reliable statistical inferences after data has been clustered, a common scenario in fields like single-cell genomics. The authors introduce a novel method for "selective inference" that provides statistical guarantees, even when the clustering itself is data-driven. Their approach leverages convex clustering with L1 penalization and offers both theoretical soundness and practical efficiency, implemented in the R package poclin.

What Problem Does This Paper Address?

When we cluster data (e.g., group cells based on gene expression), we often want to ask further questions about these clusters, like "Is there a difference in gene expression between cluster A and cluster B?" The problem is that standard statistical tests assume the data wasn't pre-processed or clustered. Applying them directly after clustering can lead to incorrect conclusions (violating Type I error control). This is known as "selective inference" or "post-selection inference." The paper specifically addresses this issue in the context of convex clustering, a popular method for grouping data that uses L1 penalization, and aims to provide statistically sound tests for differences in means between these data-driven clusters.

Methods

The core of the paper's methodology lies in two main contributions:

  1. Polyhedral Characterization of Clustering: The authors develop a mathematical way to describe exactly when a specific clustering outcome is achieved by the convex clustering algorithm. This involves characterizing the conditions on the data using "polyhedral sets" (geometric shapes defined by linear inequalities). This is a crucial step for deriving statistical guarantees.
  2. Conditional Gaussian Inference: Building on the polyhedral characterization, they leverage existing techniques for inference on Gaussian vectors conditioned to polyhedral sets. This allows them to construct a test procedure whose statistical properties (like controlling the Type I error rate) are guaranteed, even though the clustering itself is random.
  3. Regularization Path Algorithm: As a practical byproduct, they develop an efficient algorithm to compute the convex clustering solution across a range of regularization parameters (λ). This is important because the choice of λ influences the clustering outcome.
  4. Extension to Multi-dimensional Data: The one-dimensional framework is then extended to handle multi-dimensional data by aggregating the results from individual dimensions.

Datasets

The paper uses simulated datasets for its numerical experiments. These simulations are designed to mimic real-world scenarios, particularly those involving Gaussian data with varying signal strengths and correlations. No new real-world datasets are introduced or benchmarked.

Key Insights and Ideas

  • Bridging Clustering and Inference: The paper provides a principled way to connect data clustering with rigorous statistical inference, a gap that has been difficult to bridge.
  • The Power of Polyhedra: Using polyhedral sets to characterize clustering outcomes is a powerful mathematical tool that unlocks the ability to derive precise statistical guarantees.
  • Efficiency Matters: The development of an efficient regularization path algorithm is critical for making these methods practical for larger datasets, as naive optimization can be computationally prohibitive.
  • Conditional Guarantees are Key: The focus on conditional validity (guarantees given a specific clustering) is a strong statistical property that leads to unconditional validity and better interpretability.

Key Results

  • Guaranteed Type I Error Control: The proposed test procedure is shown to control the Type I error rate, meaning it rarely rejects the null hypothesis when it's true, even after data-driven clustering. This is demonstrated through extensive simulations.
  • Statistical Power: The method shows good power to detect differences in means between clusters, especially when the signal is strong and variables are independent.
  • Computational Efficiency: The poclin R package, implementing their regularization path algorithm, is shown to be significantly faster and more memory-efficient than existing generalized Lasso implementations for convex clustering, especially for large datasets. For instance, their method can handle datasets up to $n=100,000$ where others struggle with $n=5,000$.
  • Robustness to Misspecification: The framework is shown to be meaningful even when the clustering is "misspecified" (i.e., no clear intrinsic clusters exist in the data), allowing for assessment of how well the clustering algorithm captured underlying patterns.

Limitations and Future Work

  • Known Covariance Matrix: The theoretical guarantees rely on the assumption that the covariance matrix is known. Relaxing this assumption is an important area for future work, as estimating it can introduce identifiability issues.
  • Fixed Regularization Parameter (λ): The statistical guarantees hold for a fixed λ, which is not data-driven. While the paper provides a procedure to choose λ, it's not part of the formal guarantee. Developing methods for data-driven λ selection while maintaining guarantees is a future direction.
  • Impact of Dependence: The paper notes that variable dependence can reduce the power of the test by affecting the conditioning set. Alleviating this issue is highlighted as an important future research direction.
  • Alternative Aggregation Methods: The numerical experiments primarily used hierarchical clustering for multi-dimensional aggregation. Exploring the benefits of other aggregation strategies is suggested.
  • Conditioning by Order: The current method requires conditioning on the order of observations, which is a byproduct of the polyhedral characterization. Developing tests that only condition on the clustering itself could potentially offer more power.

Summary updated

Abstract

Classical inference methods notoriously fail when applied to data-driven test hypotheses or inference targets. Instead, dedicated methodologies are required to obtain statistical guarantees for these selective inference problems. Selective inference is particularly relevant post-clustering, typically when testing a difference in mean between two clusters. In this paper, we address convex clustering with ℓ 1 penalization, by leveraging related selective inference tools for regression, based on Gaussian vectors conditioned to polyhedral sets. In the one-dimensional case, we prove a polyhedral characterization of obtaining given clusters, that enables us to introduce a test procedure with statistical guarantees. This characterization also allows us to provide a computationally efficient regularization path algorithm. Then, we extend the above test procedure and guarantees to multi-dimensional clustering with ℓ 1 penalization, and also to more general multi-dimensional clusterings that aggregate one-dimensional ones. With various numerical experiments, we validate our statistical guarantees and study the power of our methods to detect differences in mean between clusters. Our methods are implemented in the R package poclin.
BibTeX
@inproceedings{bachoc2025selective,
  author = {François Bachoc and Cathy Maugis-Rabusseau and Pierre Neuvial},
  title = {{Selective inference after convex clustering with <i>ℓ</i><sub>1</sub> penalization}},
  booktitle = {ESAIM},
  year = {2025},
  doi = {10.1051/ps/2025004},
}
Figure