RESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning
With scalable Laplacian solvers now available, the next frontier is to exploit them more effectively for high-quality hypergraph partitioning. In this work, we revisit spectral hypergraph…
- 用途
- 原典で確認
- 難易度の目安
- Hard
- 実装コストの目安
- Low
概要
With scalable Laplacian solvers now available, the next frontier is to exploit them more effectively for high-quality hypergraph partitioning. In this work, we revisit spectral hypergraph partitioning from the perspective of spectral embedding geometry. Through a systematic analysis of circuit hypergraphs and controlled synthetic (hyper)graphs, we identify a ray-like embedding structure that helps explain the effectiveness of projection-based partitioning. We further show that the geometry of spectral embeddings can be systematically influenced through Laplacian design and hyperedge reweighting. Guided by these insights, we propose FRESHPart, a feedback-reshaped spectral partitioning framework that refines the spectral embedding through Geometry Feedback and Search Feedback, producing embeddings that are better aligned with projection-based partitioning. On the Titan23 benchmark, FRESHPart achieves average cut reductions over hMETIS of 13.09% at $ε=2\%$ and 25.21% at $ε=20\%$, surpassing the strongest previously reported results (12.16% and 22.53%, respectively), while completing every benchmark in under 120 s on a single GPU.
参考リンク
リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。
実装を始めるプロンプト
参考リンクを確認したうえで、次の内容をコピーして利用できます。
# 論文・記事 RESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning # 概要 With scalable Laplacian solvers now available, the next frontier is to exploit them more effectively for high-quality hypergraph partitioning. In this work, we revisit spectral hypergraph… # 原典 https://arxiv.org/abs/2611.05729 上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。