# HashNWalk: Hash and Random Walk Based Anomaly Detection in Hyperedge Streams

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2022.

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

- [I'm Me, We're Us, and I'm Us: Tri-directional Contrastive Learning on Hypergraphs](https://mlsanity.com/paper/2206.04739/) (2022)
- [Classification of Edge-dependent Labels of Nodes in Hypergraphs](https://mlsanity.com/paper/2306.03032/) (2023)
- [Hypergraph clustering using Ricci curvature: an edge transport perspective](https://mlsanity.com/paper/2412.15695/) (2024)
- [Hyperedge Anomaly Detection with Hypergraph Neural Network](https://mlsanity.com/paper/2412.05641/) (2024)
- [MARIOH: Multiplicity-Aware Hypergraph Reconstruction](https://mlsanity.com/paper/2504.00522/) (2025)

## Abstract (arXiv)

Sequences of group interactions, such as emails, online discussions, and co-authorships, are ubiquitous; and they are naturally represented as a stream of hyperedges. Despite their broad potential applications, anomaly detection in hypergraphs (i.e., sets of hyperedges) has received surprisingly little attention, compared to that in graphs. While it is tempting to reduce hypergraphs to graphs and apply existing graph-based methods, according to our experiments, taking higher-order structures of hypergraphs into consideration is worthwhile. We propose HashNWalk, an incremental algorithm that detects anomalies in a stream of hyperedges. It maintains and updates a constant-size summary of the structural and temporal information about the stream. Using the summary, which is the form of a proximity matrix, HashNWalk measures the anomalousness of each new hyperedge as it appears. HashNWalk is (a) Fast: it processes each hyperedge in near real-time and billions of hyperedges within a few hours, (b) Space Efficient: the size of the maintained summary is a predefined constant, (c) Effective: it successfully detects anomalous hyperedges in real-world hypergraphs.