MARIOH: Multiplicity-Aware Hypergraph Reconstruction
This addresses the challenge of accurately modeling higher-order interactions in networks for researchers and practitioners in fields like social network analysis or bioinformatics, representing an incremental improvement over existing methods.
The paper tackles the problem of reconstructing hypergraphs from projected graphs, which simplifies higher-order interactions and causes information loss, by proposing MARIOH, a supervised method that uses edge multiplicity to achieve up to 74.51% higher reconstruction accuracy compared to state-of-the-art methods on 10 real-world datasets.
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.