A hypergraph is a generalization of a graph that arises naturally when we consider attribute-sharing among entities. 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 hence hypothesize that a hypergraph contains more information than a graph. Moreover, it is more convenient to manipulate a hypergraph directly, rather than expanding it into a graph. An open problem in hypergraphs is how to accurately and efficiently calculate their node distances. Once node distances are defined, we can find a node’s nearest neighbors, and perform label propagation on hypergraphs using a K-nearest neighbors (KNN) approach. In this paper, we propose two methods to achieve this. In the first, we compute expected hitting times of random walks on a hypergraph as node distances; in the second, we generalize the DeepWalk method to hypergraphs. 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. Using real-world datasets, we show that FRW and DeepWalk can beat SRW with a large margin. For large and sparse hypergraphs, our method for computing the expected hitting times of random walks is approximately linear in time complexity, rendering it superior to the DeepWalk method.
Research areas