Frustrated Random Walks: A Fast Method to Compute Node Distances on
  Hypergraphs
Enzhi Li Bilal Fadlallah
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.