Landing Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs

The landing probability of a vertex in a hypergraph is the probability of a random walk ending at the vertex after making a prescribed number of steps. Landing probabilities are of importance for a number of learning tasks on hypergraphs, including higher-order PageRanks and (local) community detection. We perform the first mean-field study of landing probabilities of random walks on hypergraphs and examine clique-expansion and tensor-based methods. In particular, we evaluate the mean-field characteristics of the two methods over a class of random hypergraph models for the task of seed-set community expansion. We determine parameter regimes in which one method outperforms the other and propose a new hybrid expansion method termed "partial clique-expansion" to reduce the projection distortion and reduce the complexity of tensor-based methods on partially expanded hypergraphs.