Cost-Aware Hypergraph Dismantling via Spectral Bridge Identification
摘要
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.