Random Walks on Hypergraphs with EdgeDependent Vertex Weights
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:11721181, 2019.
Abstract
Hypergraphs are used in machine learning to model higherorder relationships in data. While spectral methods for graphs are wellestablished, spectral theory for hypergraphs remains an active area of research. In this paper, we use random walks to develop a spectral theory for hypergraphs with edgedependent vertex weights: hypergraphs where every vertex v has a weight $\gamma_e(v)$ for each incident hyperedge e that describes the contribution of v to the hyperedge e. We derive a random walkbased hypergraph Laplacian, and bound the mixing time of random walks on such hypergraphs. Moreover, we give conditions under which random walks on such hypergraphs are equivalent to random walks on graphs. As a corollary, we show that current machine learning methods that rely on Laplacians derived from random walks on hypergraphs with edgeindependent vertex weights do not utilize higherorder relationships in the data. Finally, we demonstrate the advantages of hypergraphs with edgedependent vertex weights on ranking applications using realworld datasets.
Related Material


