A hypergraph is a generalization of a graph that arises naturally when
attribute-sharing among entities is considered. Although a hypergraph can be
converted into a graph by expanding its hyperedges into fully connected
subgraphs, going the reverse way is computationally complex and NP-complete. We
therefore hypothesize that a hypergraph contains more information than a graph.
In addition, it is more convenient to manipulate a hypergraph directly, rather
than expand it into a graph. An open problem in hypergraphs is how to
accurately and efficiently calculate their node distances. Estimating node
distances enables us to find a node's nearest neighbors, and perform label
propagation on hypergraphs using a K-nearest neighbors (KNN) approach. In this
paper, we propose a novel approach based on random walks to achieve label
propagation on hypergraphs. We estimate node distances as the expected hitting
times of random walks. We note that simple random walks (SRW) cannot accurately
describe highly complex real-world hypergraphs, which motivates us to introduce
frustrated random walks (FRW) to better describe them. We further benchmark our
method against DeepWalk, and show that while the latter can achieve comparable
results, FRW has a distinct computational advantage in cases where the number
of targets is fairly small. For such cases, we show that FRW runs in
significantly shorter time than DeepWalk. Finally, we analyze the time
complexity of our method, and show that for large and sparse hypergraphs, the
complexity is approximately linear, rendering it superior to the DeepWalk
alternative.

我们提出了一种基于随机游走的新方法，用于超图上的标签传播，其中我们将节点距离估计为随机游走的预期命中时间，并引入了困惑随机游走来更好地描述高度复杂的实际超图。我们还将我们的方法与 DeepWalk 进行了基准测试，结果显示在目标数量较小的情况下，FRW 在运行时间上具有明显的计算优势。最后，我们分析了我们方法的时间复杂度，并表明对于大型稀疏的超图，复杂度近似为线性，优于 DeepWalk 的替代方案。