Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Thresholded Local Hyper-Flow Diffusion (TL-HFD), a novel first-order method that enhances seeded clustering in submodular hypergraphs by maintaining a localized active region around the seeds during computation. The method achieves exact local updates and establishes finite-time dual suboptimality, demonstrating that the localized approach can outperform traditional Hyper-Flow Diffusion (HFD) methods, particularly in noisy environments. Empirical results indicate that TL-HFD not only matches but often improves upon HFD while activating less volume, showcasing its efficiency and effectiveness in practical applications.
TL-HFD achieves exact local updates while significantly reducing computational volume, outperforming traditional methods in noisy scenarios.
Local Hyper-Flow Diffusion (HFD) gives an edge-size-independent Cheeger-type guarantee for seeded clustering in general submodular hypergraphs, but existing HFD solvers do not keep intermediate computation local at every iteration. We introduce Thresholded Local HFD (TL-HFD), a first-order method that maintains an active region around the seeds, performs projected subgradient updates on that region and its immediate boundary, and expands via thresholded (top-k) boundary activation. We prove that the local update is exact: the degree-preconditioned projected subgradient step restricted to the active region and its boundary coincides with the unrestricted global update. We establish finite-time dual suboptimality for both exact and thresholded updates, treating the latter as inexact projected subgradient steps with explicit skipped-boundary error. We further derive an additive activated-volume bound controlled by realized local subgradient norms and the minimum boundary-push among newly activated vertices, and translate approximate dual optimality with localized support into a robust sweep-cut guarantee for early-stopped iterates. For general submodular cut-costs, each iteration is local in the scanned region and oracle-sensitive in the hyperedge primitive. Empirically, TL-HFD often matches or improves over HFD while activating less volume, with the largest gains on noisy instances where diffusion tends to absorb non-target vertices.