  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.
