arXiv:2606.09340cs.LG2026-06

提出一种局部扩散方法,提升种子聚类的精度与效率。

Thresholded Local Hyper-Flow Diffusion

论文配图:Thresholded Local Hyper-Flow Diffusion
图 1 · 摘自论文原文
  • 基于阈值激活边界,保持计算局部性
  • 每轮迭代仅处理活跃区域及邻边,降低计算量
  • 在噪声数据上表现更优,适合大规模稀疏图

局部超流扩散(HFD)为一般次模超图中的种子聚类提供了边数无关的切比雪夫型保证,但现有求解器无法在每轮迭代中保持中间计算的局部性。本文提出阈值局部超流扩散(TL-HFD),一种一阶方法:围绕种子维护一个活跃区域,在该区域及其边界上进行投影梯度更新,并通过阈值(top-k)边界激活扩展。证明了局部更新是精确的:在活跃区域及其边界上施加度预条件投影梯度步,等价于全局无限制更新。建立了精确与阈值更新的有限时间对偶次优性,将后者视为带有显式跳过边界误差的非精确投影梯度步。进一步推导出由实际局部梯度范数和新激活顶点最小边界推动控制的加性激活体积界,并将近似对偶最优性与局部支持结合,转化为早期停止迭代的鲁棒割集保证。对于一般次模割代价,每轮迭代在扫描区域上是局部的,且对超边原语敏感。实验表明,TL-HFD通常匹配或优于HFD,同时激活更少体积,在噪声实例上提升显著,有效避免非目标顶点被吸收。

原文摘要 · Abstract (English)

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.

图神经网络聚类优化算法超图

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。