Frustrated Random Walks: A Fast Method to Compute Node Distances on Hypergraphs
This addresses the need for fast node distance estimation in hypergraphs, with applications in recommender systems and targeted advertising, though it is incremental as it builds on random walk methods.
The paper tackled the problem of efficiently computing node distances on hypergraphs by proposing frustrated random walks (FRW), which achieved comparable accuracy to DeepWalk but with significantly shorter runtime for cases with a small number of targets.
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 advertising, 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.