# Random walks on hypergraphs

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2019.

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

- [Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs](https://mlsanity.com/paper/2110.14416/) (2021)
- [Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs](https://mlsanity.com/paper/2203.16939/) (2022)
- [Inference of hyperedges and overlapping communities in hypergraphs](https://mlsanity.com/paper/2204.05646/) (2022)
- [CAT-Walk: Inductive Hypergraph Learning via Set Walks](https://mlsanity.com/paper/2306.11147/) (2023)
- [Temporal Inductive Logic Reasoning over Hypergraphs](https://mlsanity.com/paper/2206.05051/) (2022)
- [Machine Learning on Dynamic Graphs: A Survey on Applications](https://mlsanity.com/paper/2401.08147/) (2024)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Interaction Measures, Partition Lattices and Kernel Tests for High-Order Interactions](https://mlsanity.com/paper/2306.00904/) (2023)
- [Learning the effective order of a hypergraph dynamical system](https://mlsanity.com/paper/2306.01813/) (2023)
- [Multi-view Spectral Clustering on the Grassmannian Manifold With Hypergraph Representation](https://mlsanity.com/paper/2503.06066/) (2025)
- [Scalable tensor methods for nonuniform hypergraphs](https://mlsanity.com/paper/2306.17825/) (2023)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)
- [On the convergence of nonlinear averaging dynamics with three-body interactions on hypergraphs](https://mlsanity.com/paper/2304.07203/) (2023)
- [Network classification through random walks](https://mlsanity.com/paper/2505.21706/) (2025)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [HIAL: A New Paradigm for Hypergraph Active Learning via Influence Maximization](https://mlsanity.com/paper/2507.20490/) (2025)

## Abstract (arXiv)

In the last twenty years network science has proven its strength in modelling many real-world interacting systems as generic agents, the nodes, connected by pairwise edges. Yet, in many relevant cases, interactions are not pairwise but involve larger sets of nodes, at a time. These systems are thus better described in the framework of hypergraphs, whose hyperedges effectively account for multi-body interactions. We hereby propose a new class of random walks defined on such higher-order structures, and grounded on a microscopic physical model where multi-body proximity is associated to highly probable exchanges among agents belonging to the same hyperedge. We provide an analytical characterisation of the process, deriving a general solution for the stationary distribution of the walkers. The dynamics is ultimately driven by a generalised random walk Laplace operator that reduces to the standard random walk Laplacian when all the hyperedges have size 2 and are thus meant to describe pairwise couplings. We illustrate our results on synthetic models for which we have a full control of the high-order structures, and real-world networks where higher-order interactions are at play. As a first application of the method, we compare the behaviour of random walkers on hypergraphs to that of traditional random walkers on the corresponding projected networks, drawing interesting conclusions on node rankings in collaboration networks. As a second application, we show how information derived from the random walk on hypergraphs can be successfully used for classification tasks involving objects with several features, each one represented by a hyperedge. Taken together, our work contributes to unveiling the effect of higher-order interactions on diffusive processes in higher-order networks, shading light on mechanisms at the hearth of biased information spreading in complex networked systems.