# Thresholded Local Hyper-Flow Diffusion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 47 references that are in the map.
- First posted on arXiv 8 Jun 2026.

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

- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [Hypergraph Diffusions and Resolvents for Norm-Based Hypergraph Laplacians](https://mlsanity.com/paper/2307.11042/) (2023)
- [Local Clustering in Hypergraphs through Higher-Order Motifs](https://mlsanity.com/paper/2507.10570/) (2025)

## Abstract (arXiv)

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.