HAS: Hypergraph Adaptive Sampling for Structural Characteristics Preservation

A hypergraph is a mathematical structure capable of representing complex relationships among multiple entities, with widespread applications. However, as the size of hypergraphs continues to grow, their analysis and processing become increasingly challenging. Therefore, how to effectively process large hypergraphs to enable efficient analysis with limited computational resources has become an important research problem. In this article, we propose a method called hypergraph adaptive sampling (HAS), a framework that achieves adaptive batch sampling of hyperedges. This framework adaptively adjusts the sampling probability of hyperedges to ensure that the sampled subhypergraph closely resembles the original hypergraph in terms of structural characteristics, effectively reducing information loss caused by sampling. Extensive experiments are conducted on six public datasets to evaluate, and the results demonstrate that HAS outperforms other algorithms in preserving hypergraph properties. Using our hypergraph sampling method, even when only 20% of the edges of the original image are sampled, the sampled subhypergraph still maintains a small structural error compared to the original hypergraph. The KL divergence of the subhypergraph degree distribution is 0.09, which is 4.1<inline-formula id="IE1" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\boldsymbol\times}$</tex-math></inline-formula> better than the baseline. Last, the efficiency and adaptability of HAS make it applicable not only to hypergraph analysis but also for providing a general and scalable solution for efficiently processing large-scale hypergraph data.