Hypergraph dismantling aims to fragment a hypergraph into multiple disconnected subcomponents by removing as few nodes as possible. However, existing methods typically assume uniform node removal costs, overlooking the variability introduced by nodes’ functional roles or topological significance. To address this limitation, we propose a cost-aware hypergraph dismantling method (CHD) that explicitly incorporates node removal costs into the dismantling process. Specifically, we first define hyperedge removal costs by quantifying the influence of overlapping nodes shared between hyperedges. We then apply spectral partitioning to identify bridge edges with minimal cutting costs. Finally, nodes with the lowest removal costs within these bridge edges are selected for removal to achieve efficient dismantling. Experiments on six real-world hypergraph datasets demonstrate that CHD outperforms existing baselines, achieving more effective and balanced dismantling performance.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cost-Aware Hypergraph Dismantling via Spectral Bridge Identification

  • Qiao Ke,
  • Ruonan Feng,
  • Li She,
  • Chuang Liu,
  • Xiu-Xiu Zhan

摘要

Hypergraph dismantling aims to fragment a hypergraph into multiple disconnected subcomponents by removing as few nodes as possible. However, existing methods typically assume uniform node removal costs, overlooking the variability introduced by nodes’ functional roles or topological significance. To address this limitation, we propose a cost-aware hypergraph dismantling method (CHD) that explicitly incorporates node removal costs into the dismantling process. Specifically, we first define hyperedge removal costs by quantifying the influence of overlapping nodes shared between hyperedges. We then apply spectral partitioning to identify bridge edges with minimal cutting costs. Finally, nodes with the lowest removal costs within these bridge edges are selected for removal to achieve efficient dismantling. Experiments on six real-world hypergraph datasets demonstrate that CHD outperforms existing baselines, achieving more effective and balanced dismantling performance.