# SPARK: Stochastic Propagation via Affinity-guided Random walK for training-free unsupervised segmentation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 27 references that are in the map.
- First posted on arXiv 31 Jan 2026.

## Builds on (most cited first, 20 of 20)

- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016)
- [SDXL: Improving Latent Diffusion Models for High-Resolution Image Synthesis](https://mlsanity.com/paper/2307.01952/) (2023)
- [Semantic Understanding of Scenes through the ADE20K Dataset](https://mlsanity.com/paper/1608.05442/) (2016)
- [COCO-Stuff: Thing and Stuff Classes in Context](https://mlsanity.com/paper/1612.03716/) (2016)
- [Localizing Objects with Self-Supervised Transformers and no Labels](https://mlsanity.com/paper/2109.14279/) (2021)
- [Cut and Learn for Unsupervised Object Detection and Instance Segmentation](https://mlsanity.com/paper/2301.11320/) (2023)
- [Single-Stage Semantic Segmentation from Image Labels](https://mlsanity.com/paper/2005.08104/) (2020)
- [Open-Vocabulary Universal Image Segmentation with MaskCLIP](https://mlsanity.com/paper/2208.08984/) (2022)
- [Diffuse, Attend, and Segment: Unsupervised Zero-Shot Segmentation using Stable Diffusion](https://mlsanity.com/paper/2308.12469/) (2023)
- [ReCo: Retrieve and Co-segment for Zero-shot Transfer](https://mlsanity.com/paper/2206.07045/) (2022)
- [TokenCut: Segmenting Objects in Images and Videos with Self-supervised Transformer and Normalized Cut](https://mlsanity.com/paper/2209.00383/) (2022)
- [Unsupervised Object Localization: Observing the Background to Discover Objects](https://mlsanity.com/paper/2212.07834/) (2022)
- [Progressive Knowledge Distillation Of Stable Diffusion XL Using Layer Level Loss](https://mlsanity.com/paper/2401.02677/) (2024)
- [EmerDiff: Emerging Pixel-level Semantic Knowledge in Diffusion Models](https://mlsanity.com/paper/2401.11739/) (2024)
- [DiffCut: Catalyzing Zero-Shot Semantic Segmentation with Diffusion Features and Recursive Normalized Cut](https://mlsanity.com/paper/2406.02842/) (2024)
- [A Simple Approach to Automated Spectral Clustering](https://mlsanity.com/paper/2107.12183/) (2021)
- [iSeg: An Iterative Refinement-based Framework for Training-free Segmentation](https://mlsanity.com/paper/2409.03209/) (2024)
- [Unsupervised Segmentation by Diffusing, Walking and Cutting](https://mlsanity.com/paper/2412.04678/) (2024)

## Abstract (arXiv)

We argue that existing training-free segmentation methods rely on an implicit and limiting assumption, that segmentation is a spectral graph partitioning problem over diffusion-derived affinities. Such approaches, based on global graph partitioning and eigenvector-based formulations of affinity matrices, suffer from several fundamental drawbacks, they require pre-selecting the number of clusters, induce boundary oversmoothing due to spectral relaxation, and remain highly sensitive to noisy or multi-modal affinity distributions. Moreover, many prior works neglect the importance of local neighborhood structure, which plays a crucial role in stabilizing affinity propagation and preserving fine-grained contours. To address these limitations, we reformulate training-free segmentation as a stochastic flow equilibrium problem over diffusion-induced affinity graphs, where segmentation emerges from a stochastic propagation process that integrates global diffusion attention with local neighborhoods extracted from stable diffusion, yielding a sparse yet expressive affinity structure. Building on this formulation, we introduce a Markov propagation scheme that performs random-walk-based label diffusion with an adaptive pruning strategy that suppresses unreliable transitions while reinforcing confident affinity paths. Experiments across seven widely used semantic segmentation benchmarks demonstrate that our method achieves state-of-the-art zero-shot performance, producing sharper boundaries, more coherent regions, and significantly more stable masks compared to prior spectral-clustering-based approaches.