# Random Walks on Hypergraphs with Edge-Dependent Vertex Weights

arXiv: https://arxiv.org/abs/1905.08287 · HTML: https://mlsanity.com/paper/1905.08287/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2019.

## Built on by (most cited first, 30 of 45)

- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Making Recommender Systems Forget: Learning and Unlearning for Erasable Recommendation](https://mlsanity.com/paper/2203.11491/) (2022)
- [Accelerating science with human-aware artificial intelligence](https://mlsanity.com/paper/2306.01495/) (2023)
- [A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide](https://mlsanity.com/paper/2404.01039/) (2024)
- [Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs](https://mlsanity.com/paper/2203.16939/) (2022)
- [Classification of Edge-dependent Labels of Nodes in Hypergraphs](https://mlsanity.com/paper/2306.03032/) (2023)
- [Learning over Families of Sets -- Hypergraph Representation Learning for Higher Order Tasks](https://mlsanity.com/paper/2101.07773/) (2021)
- [A Hypergraph Neural Network Framework for Learning Hyperedge-Dependent Node Embeddings](https://mlsanity.com/paper/2212.14077/) (2022)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Recent Advances in Hypergraph Neural Networks](https://mlsanity.com/paper/2503.07959/) (2025)
- [CAT-Walk: Inductive Hypergraph Learning via Set Walks](https://mlsanity.com/paper/2306.11147/) (2023)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Temporal Inductive Logic Reasoning over Hypergraphs](https://mlsanity.com/paper/2206.05051/) (2022)
- [Ada-HGNN: Adaptive Sampling for Scalable Hypergraph Neural Networks](https://mlsanity.com/paper/2405.13372/) (2024)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://mlsanity.com/paper/2411.03331/) (2024)
- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [Accelerating science with human versus alien artificial intelligences](https://mlsanity.com/paper/2104.05188/) (2021)
- [Learning the effective order of a hypergraph dynamical system](https://mlsanity.com/paper/2306.01813/) (2023)
- [HyperMagNet: A Magnetic Laplacian based Hypergraph Neural Network](https://mlsanity.com/paper/2402.09676/) (2024)
- [A Simple Hypergraph Kernel Convolution based on Discounted Markov Diffusion Process](https://mlsanity.com/paper/2210.16884/) (2022)
- [Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning](https://mlsanity.com/paper/2309.05798/) (2023)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking](https://mlsanity.com/paper/2402.11339/) (2024)
- [Modeling Edge-Specific Node Features through Co-Representation Neural Hypergraph Diffusion](https://mlsanity.com/paper/2405.14286/) (2024)
- [High-order joint embedding for multi-level link prediction](https://mlsanity.com/paper/2111.05265/) (2021)
- [Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering](https://mlsanity.com/paper/2208.07457/) (2022)
- [Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian](https://mlsanity.com/paper/2305.00462/) (2023)

## Abstract (arXiv)

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 γ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.