Sampling hypergraphs via joint unbiased random walk

Hypergraphs are instrumental in modeling complex relational systems that encompass a wide spectrum of high-order interactions among components. One prevalent analysis task is the properties estimation of large-scale hypergraphs, which involves selecting a subset of nodes and hyperedges while preserving the characteristics of the entire hypergraph. This paper aims to sample hypergraphs via random walks and is the first to perform unbiased random walks for sampling of nodes and hyperedges simultaneously in large-scale hypergraphs to the best of our knowledge. Initially, we analyze the stationary distributions of nodes and hyperedges for the simple random walk, and show that there is a high bias in both nodes and hyperedges. Subsequently, to eliminate the high bias of the simple random walk, we propose unbiased random walk strategies for nodes and hyperedges, respectively. Finally, a single joint walk schema is developed for sampling nodes and hyperedges simultaneously. To accelerate the convergence process, we employ delayed acceptance and history-aware techniques to assist our algorithm in achieving fast convergence. Extensive experimental results validate our theoretical findings, and the unbiased sampling algorithms for nodes and hyperedges have their complex hypergraph scenarios for which they are applicable. The joint random walk algorithm balanced the sampling applicable to both nodes and hyperedges. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.