  A hypergraph is a generalization of a graph that arises naturally when
attribute-sharing among entities is considered. Compared to graphs, hypergraphs
have the distinct advantage that they contain explicit communities and are more
convenient to manipulate. An open problem in hypergraph research is how to
accurately and efficiently calculate node distances on hypergraphs. Estimating
node distances enables us to find a node's nearest neighbors, which has
important applications in such areas as recommender system, targeted ads, etc.
In this paper, we propose using expected hitting times of random walks to
compute hypergraph node distances. We note that simple random walks (SRW)
cannot accurately compute node distances on highly complex real-world
hypergraphs, which motivates us to introduce frustrated random walks (FRW) for
this task. 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.
