# Hypergraph Random Walks, Laplacians, and Clustering

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 20 of 20)

- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [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)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [CAT-Walk: Inductive Hypergraph Learning via Set Walks](https://mlsanity.com/paper/2306.11147/) (2023)
- [A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation](https://mlsanity.com/paper/2408.05459/) (2024)
- [Temporal Inductive Logic Reasoning over Hypergraphs](https://mlsanity.com/paper/2206.05051/) (2022)
- [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)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [Randomized Algorithms for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2402.08134/) (2024)
- [HyperMagNet: A Magnetic Laplacian based Hypergraph Neural Network](https://mlsanity.com/paper/2402.09676/) (2024)
- [Modeling Edge-Specific Node Features through Co-Representation Neural Hypergraph Diffusion](https://mlsanity.com/paper/2405.14286/) (2024)
- [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)
- [Scalable tensor methods for nonuniform hypergraphs](https://mlsanity.com/paper/2306.17825/) (2023)
- [Hypergraph clustering using Ricci curvature: an edge transport perspective](https://mlsanity.com/paper/2412.15695/) (2024)
- [Scalable Hypergraph Structure Learning with Diverse Smoothness Priors](https://mlsanity.com/paper/2504.03583/) (2025)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering](https://mlsanity.com/paper/2606.02887/) (2026)

## Abstract (arXiv)

We propose a flexible framework for clustering hypergraph-structured data based on recently proposed random walks utilizing edge-dependent vertex weights. When incorporating edge-dependent vertex weights (EDVW), a weight is associated with each vertex-hyperedge pair, yielding a weighted incidence matrix of the hypergraph. Such weightings have been utilized in term-document representations of text data sets. We explain how random walks with EDVW serve to construct different hypergraph Laplacian matrices, and then develop a suite of clustering methods that use these incidence matrices and Laplacians for hypergraph clustering. Using several data sets from real-life applications, we compare the performance of these clustering algorithms experimentally against a variety of existing hypergraph clustering methods. We show that the proposed methods produce higher-quality clusters and conclude by highlighting avenues for future work.