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

• URL: http://arxiv.org/abs/2602.00516v1
• Date: Sat, 31 Jan 2026 05:12:17 GMT
• Title: SPARK: Stochastic Propagation via Affinity-guided Random walK for training-free unsupervised segmentation
• Authors: Kunal Mahatha, Jose Dolz, Christian Desrosiers,
• Abstract summary: Training-free segmentation methods rely on an implicit and limiting assumption, that segmentation is a spectral graph partitioning problem over diffusion-derived affinities.<n>We introduce a Markov propagation scheme that performs random-walk-based diffusion with an adaptive label pruning strategy.<n>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.
• Score: 18.627047608492795
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Adaptive Partitioning and Learning for Stochastic Control of Diffusion Processes [3.058685580689604]
  We study reinforcement learning for controlled diffusion processes with unbounded continuous state spaces.<n>We introduce a model-based algorithm that adaptively partitions the joint state-action space.<n>This adaptive scheme balances exploration and approximation, enabling efficient learning in unbounded domains.
  arXiv  Detail & Related papers  (2025-12-17T00:52:19Z)
• Foundations of Diffusion Models in General State Spaces: A Self-Contained Introduction [54.95522167029998]
  This article is a self-contained primer on diffusion over general state spaces.<n>We develop the discrete-time view (forward noising via Markov kernels and learned reverse dynamics) alongside its continuous-time limits.<n>A common variational treatment yields the ELBO that underpins standard training losses.
  arXiv  Detail & Related papers  (2025-12-04T18:55:36Z)
• NERVE: Neighbourhood & Entropy-guided Random-walk for training free open-Vocabulary sEgmentation [18.627047608492795]
  We propose a training-free method for Open-Vocabulary Semantics (OVSS) called NERVE.<n>NERVE integrates global and fine-grained local information, exploiting the neighbourhood structure from the self-attention layer of a stable diffusion model.<n>Our method does not require any conventional post-processing techniques like Conditional Random Fields (CRF) or Pixel-Adaptive Mask Refinement (PAMR)
  arXiv  Detail & Related papers  (2025-11-11T13:43:57Z)
• Effective Test-Time Scaling of Discrete Diffusion through Iterative Refinement [51.54933696252104]
  We introduce Iterative Reward-Guided Refinement (IterRef), a novel test-time scaling method tailored to discrete diffusion.<n>We formalize this process within a Multiple-Try Metropolis framework, proving convergence to the reward-aligned distribution.<n>IterRef achieves striking gains under low compute budgets, far surpassing prior state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-11-04T02:33:23Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Robust Spectral Fuzzy Clustering of Multivariate Time Series with Applications to Electroencephalogram [6.62414474989199]
  We introduce a fuzzy clustering framework in the spectral domain to extract frequency-specific monotonic relationships across variables.<n>Our method takes advantage of dominant frequency-based cross-regional connectivity patterns to improve clustering accuracy.<n>As a flagship application, we analyze electroencephalogram recordings, where our approach uncovers frequency- and connectivity-specific markers of latent cognitive states.
  arXiv  Detail & Related papers  (2025-06-28T12:02:01Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework.<n>We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points.<n>Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Correspondence-Free Non-Rigid Point Set Registration Using Unsupervised Clustering Analysis [28.18800845199871]
  We present a novel non-rigid point set registration method inspired by unsupervised clustering analysis. Our method achieves high accuracy results across various scenarios and surpasses competitors by a significant margin.
  arXiv  Detail & Related papers  (2024-06-27T01:16:44Z)
• Tackling Ambiguity from Perspective of Uncertainty Inference and Affinity Diversification for Weakly Supervised Semantic Segmentation [12.308473939796945]
  Weakly supervised semantic segmentation (WSSS) with image-level labels aims to achieve dense tasks without laborious annotations. The performance of WSSS, especially the stages of generating Class Activation Maps (CAMs) and refining pseudo masks, widely suffers from ambiguity. We propose UniA, a unified single-staged WSSS framework, to tackle this issue from the perspective of uncertainty inference and affinity diversification.
  arXiv  Detail & Related papers  (2024-04-12T01:54:59Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.