Random Walks on Hypergraphs with Edge-Dependent Vertex Weights
  Hypergraphs are used in machine learning to model higher-order relationships
in data. While spectral methods for graphs are well-established, 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
edge-dependent 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 walk-based 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 edge-independent vertex weights do not utilize higher-order
relationships in the data. Finally, we demonstrate the advantages of
hypergraphs with edge-dependent vertex weights on ranking applications using
real-world datasets.
