Presentation
Hyperefs: Adaptive Clique Sampling for Scalable Effective Resistance Estimation in Large Hypergraphs
DescriptionWe propose HyperEFs, a scalable framework for effective resistance estimation in large hypergraphs based on adaptive clique sampling. The proposed sampling strategy enables smooth transitions between star and clique expansions of hyperedges, substantially improving the quality of Krylov subspace embeddings. HyperEFs estimates pairwise effective-resistance distances in large hypergraphs in nearly linear time and integrates seamlessly into state-of-the-art multilevel hypergraph partitioning frameworks, yielding significantly improved solution quality. Extensive experiments on VLSI benchmarks demonstrate up to 100× speedup over HyperEF 2.0 with greatly reduced memory usage. On large-scale hypergraph datasets such as Titan23, our framework achieves superior cut sizes, demonstrating exceptional runtime scalability and efficiency.
Event Type
Research Manuscript
TimeTuesday, July 283:42pm - 3:54pm PDT
LocationMtg Room 203AB