# Differentiable Clustering with Perturbed Spanning Forests

arXiv: https://arxiv.org/abs/2305.16358 · HTML: https://mlsanity.com/paper/2305.16358/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 25 May 2023.

## Builds on (most cited first, 30 of 31)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Deep Clustering for Unsupervised Learning of Visual Features](https://mlsanity.com/paper/1807.05520/) (2018)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Soft-DTW: a Differentiable Loss Function for Time-Series](https://mlsanity.com/paper/1703.01541/) (2017)
- [Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering](https://mlsanity.com/paper/1610.04794/) (2016)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Differentiable Patch Selection for Image Recognition](https://mlsanity.com/paper/2104.03059/) (2021)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection](https://mlsanity.com/paper/2103.17202/) (2021)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [Self-Supervised Learning of Audio Representations from Permutations with Differentiable Ranking](https://mlsanity.com/paper/2103.09879/) (2021)
- [Learning by Sorting: Self-supervised Learning with Group Ordering Constraints](https://mlsanity.com/paper/2301.02009/) (2023)
- [Efficient Computation of Expectations under Spanning Tree Distributions](https://mlsanity.com/paper/2008.12988/) (2020)
- [On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations](https://mlsanity.com/paper/1309.7598/) (2013)
- [Differentiable Rendering with Perturbed Optimizers](https://mlsanity.com/paper/2110.09107/) (2021)
- [Leveraging Recursive Gumbel-Max Trick for Approximate Inference in Combinatorial Spaces](https://mlsanity.com/paper/2110.15072/) (2021)

## Built on by (most cited first, 14 of 14)

- [Grounding Everything: Emerging Localization Properties in Vision-Language Transformers](https://mlsanity.com/paper/2312.00878/) (2023)
- [Uncertainty Quantification via Stable Distribution Propagation](https://mlsanity.com/paper/2402.08324/) (2024)
- [Towards Foundational Models for Dynamical System Reconstruction: Hierarchical Meta-Learning via Mixture of Experts](https://mlsanity.com/paper/2502.05335/) (2025)
- [Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation](https://mlsanity.com/paper/2410.08125/) (2024)
- [Soft Condorcet Optimization for Ranking of General Agents](https://mlsanity.com/paper/2411.00119/) (2024)
- [Differentiable Cluster Graph Neural Network](https://mlsanity.com/paper/2405.16185/) (2024)
- [Building Bridges between Regression, Clustering, and Classification](https://mlsanity.com/paper/2502.02996/) (2025)
- [Differentiable Integer Linear Programming is not Differentiable & it's not a mere technical problem](https://mlsanity.com/paper/2601.17800/) (2026)
- [DistrictNet: Decision-aware learning for geographical districting](https://mlsanity.com/paper/2412.08287/) (2024)
- [Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms](https://mlsanity.com/paper/2506.00732/) (2025)
- [CF-OPT: Counterfactual Explanations for Structured Prediction](https://mlsanity.com/paper/2405.18293/) (2024)
- [A Study on Building Efficient Zero-Shot Relation Extraction Models](https://mlsanity.com/paper/2603.01266/) (2026)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)
- [Do Vision Transformers Need All-to-All Attention? Global Communication Through Elastic Learned Cores](https://mlsanity.com/paper/2605.12491/) (2026)

## Abstract (arXiv)

We introduce a differentiable clustering method based on stochastic perturbations of minimum-weight spanning forests. This allows us to include clustering in end-to-end trainable pipelines, with efficient gradients. We show that our method performs well even in difficult settings, such as data sets with high noise and challenging geometries. We also formulate an ad hoc loss to efficiently learn from partial clustering data using this operation. We demonstrate its performance on several data sets for supervised and semi-supervised tasks.