# Supervised Hypergraph Reconstruction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 23 Nov 2022.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Hyper-SAGNN: a self-attention based graph neural network for hypergraphs](https://mlsanity.com/paper/1911.02613/) (2019)
- [HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphs](https://mlsanity.com/paper/2010.04558/) (2020)
- [Hypergraph reconstruction from network data](https://mlsanity.com/paper/2008.04948/) (2020)
- [Evolution of Real-world Hypergraphs: Patterns and Models without Oracles](https://mlsanity.com/paper/2008.12729/) (2020)
- [Predicting Scientific Success Based on Coauthorship Networks](https://mlsanity.com/paper/1402.7268/) (2014)

## Abstract (arXiv)

We study an issue commonly seen with graph data analysis: many real-world complex systems involving high-order interactions are best encoded by hypergraphs; however, their datasets often end up being published or studied only in the form of their projections (with dyadic edges). To understand this issue, we first establish a theoretical framework to characterize this issue's implications and worst-case scenarios. The analysis motivates our formulation of the new task, supervised hypergraph reconstruction: reconstructing a real-world hypergraph from its projected graph, with the help of some existing knowledge of the application domain. To reconstruct hypergraph data, we start by analyzing hyperedge distributions in the projection, based on which we create a framework containing two modules: (1) to handle the enormous search space of potential hyperedges, we design a sampling strategy with efficacy guarantees that significantly narrows the space to a smaller set of candidates; (2) to identify hyperedges from the candidates, we further design a hyperedge classifier in two well-working variants that capture structural features in the projection. Extensive experiments validate our claims, approach, and extensions. Remarkably, our approach outperforms all baselines by an order of magnitude in accuracy on hard datasets. Our code and data can be downloaded from bit.ly/SHyRe.