# MARIOH: Multiplicity-Aware Hypergraph Reconstruction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 1 Apr 2025.

## Builds on (most cited first, 18 of 18)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [HNHN: Hypergraph Networks with Hyperedge Neurons](https://mlsanity.com/paper/2006.12278/) (2020)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)
- [How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction](https://mlsanity.com/paper/2001.11181/) (2020)
- [Further Generalizations of the Jaccard Index](https://mlsanity.com/paper/2110.09619/) (2021)
- [The why, how, and when of representations for complex systems](https://mlsanity.com/paper/2006.02870/) (2020)
- [How Do Hyperedges Overlap in Real-World Hypergraphs? -- Patterns, Measures, and Generators](https://mlsanity.com/paper/2101.07480/) (2021)
- [Hypergraph reconstruction from network data](https://mlsanity.com/paper/2008.04948/) (2020)
- [Hypergraph Motifs: Concepts, Algorithms, and Discoveries](https://mlsanity.com/paper/2003.01853/) (2020)
- [Predicting Scientific Success Based on Coauthorship Networks](https://mlsanity.com/paper/1402.7268/) (2014)
- [Higher-order motif analysis in hypergraphs](https://mlsanity.com/paper/2108.03192/) (2021)
- [HashNWalk: Hash and Random Walk Based Anomaly Detection in Hyperedge Streams](https://mlsanity.com/paper/2204.13822/) (2022)
- [Encapsulation Structure and Dynamics in Hypergraphs](https://mlsanity.com/paper/2307.04613/) (2023)

## Abstract (arXiv)

Hypergraphs offer a powerful framework for modeling higher-order interactions that traditional pairwise graphs cannot fully capture. However, practical constraints often lead to their simplification into projected graphs, resulting in substantial information loss and ambiguity in representing higher-order relationships. In this work, we propose MARIOH, a supervised approach for reconstructing the original hypergraph from its projected graph by leveraging edge multiplicity. To overcome the difficulties posed by the large search space, MARIOH integrates several key ideas: (a) identifying provable size-2 hyperedges, which reduces the candidate search space, (b) predicting the likelihood of candidates being hyperedges by utilizing both structural and multiplicity-related features, and (c) not only targeting promising hyperedge candidates but also examining less confident ones to explore alternative possibilities. Together, these ideas enable MARIOH to efficiently and effectively explore the search space. In our experiments using 10 real-world datasets, MARIOH achieves up to 74.51% higher reconstruction accuracy compared to state-of-the-art methods.