# Supervised Hypergraph Reconstruction

Yanbang Wang<EMAIL_ADDRESS>Cornell UniversityIthacaNew YorkUSA and  Jon
Kleinberg<EMAIL_ADDRESS>Cornell UniversityIthacaNew YorkUSA

###### Abstract.

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.

hypergraphs, projection, reconstruction, supervised learning

††copyright: none††ccs: Mathematics of computing Hypergraphs††ccs: Computing
methodologies Machine learning

##  1\. Introduction

Graphs are a mathematical formalism that can describe many real-world complex
systems by recording which pairs of entities in the system are connected,
using the language of nodes and edges. Hypergraphs take this idea further by
extending the concept of edges from pairwise relations to sets of arbitrary
sizes, and thus admit a more expressive form of encoding for multilateral
relationships.

The long-standing problem that this paper addresses is that many datasets that
should have been encoded by hypergraphs ended up being released or studied
almost exclusively in graph format. There are many examples of this
phenomenon: co-authorship networks (Newman, 2004; Sarigöl et al., 2014) where
an edge encodes two author’s collaboration in the same paper, social
interaction networks (Madan et al., 2011; Klimt and Yang, 2004) where an edge
encodes two persons’ interaction in a conversation or email, and protein-
protein interaction networks (Safari-Alighiarloo et al., 2014) where an edge
encodes two proteins’ co-occurrence in one biological process. Co-authorships,
conversations, and bio-processes all typically involve multiple authors,
people, and proteins.

Clearly, pairwise relations (i.e. graphs) contain less information than the
original hypergraphs they come from. Replacing hypergraphs with graphs is
known to bias how people perceive (Wolf et al., 2016), predict (Arya et al.,
2020), and exploit (Arya and Worring, 2018) real-world interconnected systems.
Despite the drawbacks, there are many real-world scenarios where the crucial
underlying hypergraphs are dropped and only projected graphs get studied and
released. These scenarios come in two cases:

  * •

Unobservable: In some key scenarios, the available technology for data
collection can only detect pairwise relations. This is most common in social
science. For example, in (Madan et al., 2011; Ozella et al., 2021; Dai et al.,
2020), sensing methodologies to record physical proximity can be used to build
networks of face-to-face interaction: an interaction between two people is
recorded by thresholding distances between their body-worn sensors. There is
no way to directly record the multiple participants in each conversation by
sensors only. Recovering multi-party events in a purely decentralized, peer-
to-peer network system of communication is an important application.

  * •

Unpublished: Even when they are technically observable, in practice the source
hypergraph datasets of many studies are never released or published. For
example, many of the most impactful studies analyzing coauthorships do not
make available a hypergraph version of their dataset (Newman, 2004; Sarigöl et
al., 2014). Many popular graph learning benchmarks, including arXiv-hepth
(Leskovec et al., 2005), ogbl-collab (Hu et al., 2020), and ogbn-product (Hu
et al., 2020), also do not provide their hypergraph originals. Yet the
underlying, unobserved hypergraphs contain important information about the
domain.

There do exist measures to recover a hypergraph, or at least a part of it,
from graphs in these domains. Traditionally, such recovery process involves
laborious manual work, and only one hypergraph can be recovered at a time,
i.e. the recovery is not generalizable to similar hypergraphs, and is hard to
carry out at scale. To recover unobservable social interactions, social
scientists use surveys that ask students to recall all people they had talked
to in each daily conversation (Ozella et al., 2021); to obtain unpublished
hypergraphs, researchers go great lengths to either replicate tedious data
preprocessing or to trace back to data publishers. Measures like these require
a considerable amount of time, effort, and luck.

Figure 1. The supervised hypergraph reconstruction task. $\mathcal{H}_{0}$ and
$\mathcal{H}_{1}$ belong to the same application domain. Given
$\mathcal{H}_{0}$ (and its projection $G_{0}$), can we reconstruct
$\mathcal{H}_{1}$ from its projection $G_{1}$?

All the scenarios above share a common problem abstraction, as follows. There
is an underlying hypergraph $\mathcal{H}_{1}$ that we cannot directly observe,
and instead we only have access to its projected graph (or, projection)
$G_{1}$, which we define to be the graph on the same node set as the
hypergraph, and with two nodes connected in $G_{1}$ if and only if they belong
to a shared hyperedge in $\mathcal{H}_{1}$. Our goal is to reconstruct
$\mathcal{H}_{1}$ as accurately as possible, given knowledge of $G_{1}$. The
“query” half in Fig.1 illustrates this problem:

We will later discuss a training phase where a known hypergraph from the same
domain is provided. For broadest applicability, we focus on a hard version of
the problem by assuming that the edges of the projected graph $G_{1}$ are
unweighted; they just say whether two nodes appear in at least one hyperedge
together. In Appendix C.2 we will also discuss an easier version of the
problem where $G_{1}$ has weighted edges, recording the number of different
hyperedges that each pair of nodes belongs to.

Our goal towards the reconstruction is two-fold: (1) the reconstructed
hypergraph can benefit data analysis and prediction modeling by providing
efficiently-stored higher-order information for convenient usage; (2) the
reconstruction process necessitates deeper understanding of hyperedge
structure, especially (i) how hyperedges overlap each other in real-world
datasets, and (ii) how different overlap patterns may obscure different
amounts of high-order information once projected. Such understandings can help
data contributors make more informed choice when they consider trade-offs in
projecting higher-order structure out of their data.

The challenge. The biggest challenge in hypergraph reconstruction is that a
given projected graph will gnenerally admit an enormous amount of possible
hypergraphs. In simple cases, a hypergraph can be easily reconstructed if most
of its hyperedges are disjoint — simply by treating every maximal clique as a
hyperedge. However, this can rarely be the case with real-world datasets, in
which multiple hyperedges overlap each other, making some especially hard to
detect. In Sec. 4, we formalize these difficult patterns of overlap and
quantify their theoretical implications. We will also see that these patterns
are ubiquitous in real-world datasets. Therefore, it is extremely hard to
reconstruct a hypergraph arising from an arbitrary application domain without
knowing anything about what hypergraphs look like in that domain.

Previous work. Due to the technical challenge, very little work was done on
this problem, despite its significant value for applications. In graph mining,
the closest tasks are hyperedge prediction and community detection. Hyperedge
prediction (Yadati et al., 2020; Xu et al., 2013;
benson2018simplicialbenson2018sequences) is a fundamentally different problem,
in that the input to it is a hypergraph rather than its projected graph.
Additionally, methods for this problem typically only identify hyperedges from
a given set of candidates, rather than the large implicit spaces of all
possible hyperedges. Community detection, on the other hand, is based on
looking for densely connected subsets of a graph under various definitions,
but not for hyperedges. Both tasks are very different from our goal of
searching hyperedges over the projection.

Besides the above, (Young et al., 2021) is by far the closest related work.
However, it aims to use least number of hyperedges to cover an arbitrary graph
(see its Fig.7), as a way to explain the “local density, global sparsity” of
some networks. Their work attempts parsimonious explanations of data rather
than recovery of ground truth. Consequently, their “principle of parsimony”
does not give high accuracy on many real-world hypergraphs, where there are
significant hyperedge overlaps. We will see in Sec. 6 that all these methods
above yield significantly lower performance than our approach.

Using supervised signal. To help reconstruction in the presence of these forms
of uncertainty, we propose the usage of training data: another hypergraph from
the same application domain. Shown in Fig.1, our effort to reconstruct
hypergraph $\mathcal{H}_{1}$ now involves two inputs: $\mathcal{H}_{1}$’s
projection $G_{1}$, and an additional hypergraph $\mathcal{H}_{0}$ (along with
its projection $G_{0}$) from the same or similar distribution as
$\mathcal{H}_{1}$.

The training data $\mathcal{H}_{0}$ is not only necessary but also reasonable
to have. In practice, $\mathcal{H}_{0}$ often refers to manually collected
data (as described earlier in this section), including surveys of participants
(for social science applications), neuron groups labeled by experts for
another common ancestral species or homologous organ (for biological or
neuroscience applications), or a similar hypergraph obtained from another data
publisher — e.g. for coauthorships, papers from a different database or of a
different year slice.

For now, we assume $\mathcal{H}_{0}$ contains a comparable number of
hyperedges to $\mathcal{H}_{1}$. In Sec. 6.4 we generalize this to a semi-
supervised setting where $\mathcal{H}_{0}$ is downsampled to a smaller
fraction for training, and a transfer setting where $\mathcal{H}_{0}$ comes
from a different distribution than $\mathcal{H}_{1}$. As is standard in
supervised learning, we consider it realistic to assume some knowledge about
our reconstruction goal when searching through the enormous space of
candidates.

That said, inductiveness is enforced in our setting, meaning that two nodes
with the same node ID in $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ are
irrelevant entities. It also means that we are not satisfied with solving one
particular test case but also care about generalizability. More formally,
using $\mathcal{H}_{0}$, we should be able to reconstruct not only
$\mathcal{H}_{1}$ but also other hypergraphs from the same domain as
$\mathcal{H}_{1}$. Therefore, simply memorizing $\mathcal{H}_{0}$’s hyperedges
does not work.

With the help of training data, hypergraph reconstruction, which was
previously almost impossible, now becomes more feasible in principle.
Nevertheless, it still retains considerable challenges that we must address in
designing solutions.

Our approach. We start from the fact that every clique in the projection
qualifies as a hyperedge. There are two critical steps to accomplish in order
to get hyperedges from the cliques: 1. we cannot afford to traverse all
cliques (since there can be too many), so a shortlisting procedure is
necessary to significantly shrink the pool while retaining as many hyperedges
as possible; 2. after obtaining the shortlist, we need to go through cliques
in the shortlist and figure out which ones are real hyperedges.

It is extremely hard to accomplish any step above from the projected graph
alone, so we leverage the supervised signal, $\mathcal{H}_{0}$:

  * •

For shortlisting, we design a sampling strategy based on a key observation of
the consistency in hyperedge distribution between $\mathcal{H}_{0}$ and
$\mathcal{H}_{1}$. We then optimize parameters of our strategy on
$\mathcal{H}_{0}$, and use the optimized strategy to downsample the cliques of
$\mathcal{H}_{1}$.

  * •

For identifying hyperedges, we design two variants of a hyperedge classifier.
We train the classifier on cliques of $\mathcal{H}_{0}$, and then use it to
identify hyperedges from cliques of $\mathcal{H}_{1}$.

Contributions. Our main contribution is three-fold:

  * •

We identify the recovery of higher-order structure as an important and
pervasive issue commonly seen in graph data analysis. To understand the issue,
we establish a topological analysis framework to characterize its implications
and worst-case scenarios. The analysis motivates our formulation of a new
task: supervised hypergraph reconstruction.

  * •

We observe important structural properties of hyperedge distributions from
projected graphs. Based on our observations, we design a new reconstruction
framework, which contains a sampling strategy with theoretical guarantees, and
a hyperedge classifier in two well-working variants.

  * •

We conduct extensive experiments that validate our claims, approach, and
extensions. We adapt 7 baselines and compare them with our approach on 8 real-
world datasets. Our approach outperforms all baselines, and by orders of
magnitude on hard datasets.

##  2\. Preliminaries

Hypergraph. A hypergraph $\mathcal{H}$ is a tuple $(V,\mathcal{E})$, where $V$
is a finite set of nodes, and $\mathcal{E}=\\{E_{1},E_{2},...,E_{m}\\}$ is a
set of sets with $E_{i}\subseteq V$ for all $1\leq i\leq m$. For the purpose
of reconstruction, we assume the hyperedges are distinct, i.e. $\forall 1\leq
i,j\leq m,\;E_{i}\neq E_{j}$.

Projected Graph. $\mathcal{H}$’s projected graph (projection, Gaiman Graph
(Ebbinghaus and Flum, 1999)), $G$, is a graph with the same node set $V$, and
(undirected) edge set $\mathcal{E}^{\prime}$, i.e.
$G=(V,\mathcal{E}^{\prime})$, where two nodes are joined by an edge in
$\mathcal{E^{\prime}}$ if and only if they belong to a common hyperedge in
$\mathcal{E}$. That is,

$\mathcal{E}^{\prime}=\\{(v_{i},v_{j})|v_{i},v_{j}\in E,E\in\mathcal{E}\\}$

Maximal Cliques.. A clique $C$ is a fully connected subgraph. We slightly
abuse $C$ to also denote the set of nodes in the clique. A maximal clique is a
clique that cannot become larger by including more nodes. The maximal clique
algorithm returns all maximal cliques $\mathcal{M}$ in a graph (Bron and
Kerbosch, 1973). The time complexity is linear to $|\mathcal{M}|$ (Tomita et
al., 2006). A maximum clique is the largest maximal clique in a graph.

##  3\. Task Definition

We define supervised hypergraph reconstruction as the following:

  * •

Input: projected graph $G_{1}$, hypergraph $\mathcal{H}_{0}$;

  * •

(Expected) output: hypergraph $\mathcal{H}_{1}$;

  * •

$\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ belong to the same application domain,
but their node indices are not aligned, i.e. the learning is inductive.

  * •

Evaluaton: following (Young et al., 2021) we use the Jaccard Score as the main
metric for evaluating reconstruction accuracy:

$\textbf{Jaccard
Score}=\frac{|\mathcal{E}_{1}\cap\mathcal{R}_{1}|}{|\mathcal{E}_{1}\cup\mathcal{R}_{1}|}$

$\mathcal{E}_{1}$ is the true hyperedges; $\mathcal{R}_{1}$ is the
reconstructed hyperedges.

##  4\. Topological Analysis

We start with a topological analysis to understand our task from a theoretical
perspective. In particular, we seek to answer two questions: Q1. what
topological properties make hypergraphs easy to reconstruct (so that the
projection does not eliminate too much high-order information)? Q2. in the
extreme case, how much information is lost due to the projection? By
characterizing the notion of “ease” and “difficulty” in reconstruction, our
analysis will help data contributors and researchers make more informed choice
in dealing with high-order interactions.

In principle, any clique in a projection qualifies as a candidate for a true
hyperedge. Therefore, towards perfect reconstruction, we should consider
$\mathcal{U}$, the universe of all cliques in $G$, including single nodes. To
enumerate $\mathcal{U}$, a helpful view is the union of the power set 111Given
a set $S$, its power set $\mathcal{P}(S)$ is defined as the set of all subsets
of $S$. For example, $\\{A,B,C\\}$’s power set is
$\\{\\{A,B,C\\},\\{A,B\\},\\{B,C\\},\\{A,C\\},\\{A\\},\\{B\\},\\{C\\},\emptyset\\}$.of
each maximal clique of $G$. Mathematically,

$\mathcal{U}=\bigcup_{C\in\mathcal{M}}\mathcal{P}(C)\setminus\emptyset$

In that sense, maximal clique algorithm is a critical first step for
hypergraph reconstruction, as was applied by (Young et al., 2021) to
initialize the state of its MCMC solver. In the extreme case, one can
intuitively perceive that if the hyperedges of $\mathcal{H}$ are mostly
disjoint with each other, the maximal cliques in $\mathcal{H}$’s projection
must be highly aligned with hyperedges of $\mathcal{H}$. It is impossible to
find all hyperedges without considering all maximal cliques. Therefore, the
accuracy of reconstruction by maximal clique algorithm is a good quantifier
for measuring how “difficult” it is to reconstruct a hypergraph.

###### Definition 1.

A hypergraph $\mathcal{H}=(V,\mathcal{E})$ is Sperner if for every hyperedge
$E\in\mathcal{E}$ there does not exist a hyperedge $E^{\prime}\in\mathcal{E}$
$s.t.$ $E\subset E^{\prime}$.

###### Definition 2.

A hypergraph $\mathcal{H}=(V,\mathcal{E})$ is conformal 222Note that in
database theory the important notions of $\alpha$-acyclicity (Beeri et al.,
1983) and GYO reducibility (Ebbinghaus and Flum, 1999) extend conformity by
further requiring the projected graph to be chordal. The interested readers
are referred to the references for more details. if all the maximal cliques in
its projection $G$ are its hyperedges, i.e. $\mathcal{M}\subseteq\mathcal{E}$.

###### Theorem 4.1.

The maximal cliques of $G$ are precisely all hyperedges of $\mathcal{H}$, i.e.
$\mathcal{M}=\mathcal{E}$, if and only if $\mathcal{H}$ is both Sperner and
conformal.

Theorem 4.1 gives the two strict conditions that $\mathcal{H}$ must satisfy in
order to be “easy” to reconstruct. The Sperner’s definition is self-
explanatory — simply summarized as ”no pair of nested hyperedges”. In
contrast, the conformal property is less clearer. The following theorem
interprets the conformal property by its equivalence of ”uncovered triangle”
property.

###### Theorem 4.2.

A hypergraph $\mathcal{H}=(V,\mathcal{E})$ is conformal iff for every three
hyperedges there always exists some hyperedge $E$ such that all pairwise
intersections of the three hyperedges are subsets of $E$, i.e.:

$\displaystyle\forall E_{i},E_{j},$ $\displaystyle E_{q}\in\mathcal{E},$
$\displaystyle\exists\;E\in\mathcal{E},\;s.t.\;(E_{i}\cap E_{j})\cup(E_{j}\cap
E_{q})\cup(E_{q}\cap E_{i})\subseteq E$

The intuition behind Theorem 4.2 is that a conformal hypergraph cannot have
three hyperedges form a “triangle” whose three corners are “uncovered”. The
theorem gives a nontrivial interpretation of Def. 2 by eliminating the notion
of cliques or max cliques. It shows how to check a hypergraph’s conformity
purely from its hyperedge patterns with no need to further compute any max
cliques, which is a more intuitive way for us to visually understand
conformity.

Based on Def. 1 and 2, we further define the two types of errors that the
maximal cliques algorithm makes:

###### Definition 3.

There exist two types of Error If we treat all maximal cliques as true
hyperedges: an error is defined as  Error I (Error II) if it occurs because of
the projected graph’s violation of Def. 1 (Def. 2).

Fig.2 illustrates patterns of the two errors and their relationship with other
important concepts in our task. Note that here Error I and II are different
from the well-known Type I (false positive) and Type II (false negative) Error
In statistics. In fact, Error I’s are hyperedges that nest inside some other
hyperedges, so they are indeed false negatives; Error II’s can be either false
positives or negatives. For example, in Fig.2 “Error II Pattern” :
$\\{v_{1},v_{3},v_{5}\\}$ is a false positive, $\\{v_{1},v_{5}\\}$ is a false
negative.

Figure 2. The upper half shows patterns of the two types of errors made by
maximal cliques algorithm. In Error I pattern, $E_{2}$ will never be found
(false negative); in Error II pattern, corners of the “triangle” are
“uncovered”, so the max clique $\\{v_{1},v_{3},v_{5}\\}$ is not a hyperedge
(false positive), meanwhile $\\{v_{1},v_{5}\\}$ is missed (false negative).
The bottom half shows the errors’ relationship with $\mathcal{E}$ and
$\mathcal{M}$. If a hyperedge can’t be reconstructed due to both errors, we
count it as Error I.

Dataset | $|\mathcal{E}|$ | $|\mathcal{E}^{\prime}|$ | $|\mathcal{M}|$ | Error I | Error II |
---|---|---|---|---|---|---
DBLP (Benson et al., 2018) | 197,067 | 194,598 | 166,571 | 2.02% | 18.9% |
Enron (Benson et al., 2018) | 756 | 300 | 362 | 42.5% | 53.3% |
Foursquare (Young et al., 2021) | 1,019 | 874 | 8,135 | 1.74% | 88.6% |
Hosts-Virus (Young et al., 2021) | 218 | 126 | 361 | 19.5% | 58.1% |
H. School (Benson et al., 2018) | 3,909 | 2864 | 3,279 | 14.9% | 82.7% |

Table 1. $\mathcal{E}$ is the set of hyperedges; $\mathcal{E}^{\prime}$ is the
set of hyperedges not nested in any other hyperedges; $\mathcal{M}$ is the set
of maximal cliques in $G$. Error I, II result from the violation of conformal
and Sperner properties, respectively. Error I
$=\frac{|\mathcal{E}\backslash\mathcal{E}^{\prime}|}{|\mathcal{E}\cup\mathcal{M}|}$,
Error II
$=\frac{|\mathcal{M}\backslash\mathcal{E}^{\prime}|+|\mathcal{E}^{\prime}\backslash\mathcal{M}|}{|\mathcal{E}\cup\mathcal{M}|}$.

Because both patterns in Fig.2 can be easily realized, real-world hypergraphs
can easily deviate from either / both of the two properties. The significance
of deviation is closely associated with the error rate of maximal cliques
algorithm in reconstruction. A hypergraph that violates the Sperner property
badly can have many pairs of “nested hyperedges”. Common examples include
hypergraphs of email correspondence and social interactions. See Table 1,
Error I column. In the extreme case, a hypergraph contains one large hyperedge
plus many nested hyperedges as proper subsets. Therefore, the worst-case
accuracy of maximal cliques algorithm on a non-Sperner but conformal
hypergraph is $1/(2^{n}-1)$.

That said, one may argue there are still many real-world hypergraphs that are
Sperner or almost Sperner. It turns out that the worst case of violating the
conformal property can also be disastrous:

###### Theorem 4.3.

Let $\mathcal{H}=(V,\mathcal{E})$ be Sperner with $m=|\mathcal{E}|$, and
$p^{(\mathcal{H})}$ the accuracy of maximal clique algorithm for
reconstructing $\mathcal{H}$, then

$\min_{\mathcal{H}}p^{(\mathcal{H})}\leq 2^{-{m-1\choose[m/2]-1}}\ll 2^{-m}$

While the worst case rarely arises in practice, real-world hypergraphs often
create many maximal cliques that are not hyperedges due to the easy
construction of Error II patterns.

Summary. With the topological analysis, we obtain a clearer picture of the
types of hypergraphs that are easy/hard to reconstruct. The easy construction
of the two error patterns indicates that the reconstruction errors can
extensively occur in real-world datasets. It is extremely hard to fix these
errors by just looking at the projection, which necessitates the usage of a
training hypergraph. How do we make the best of the training hypergraph to
help with reconstruction? We elaborate this in the next section.

##  5\. Reconstruction Framework

###  5.1. Overview

Figure 3. Our reconstruction framework takes 4 steps: (1) the clique sampler
is optimized on $G_{0}$ and $\mathcal{H}_{0}$; (2) the clique sampler samples
candidates from $G_{0}$ and $G_{1}$, and passes the result to the hyperedge
classifier; (3) the hyperedge classifier extracts features of candidates from
$G_{0}$ and trains on them; (4) the hyperedge classifier extracts features of
candidates from $G_{1}$ and identify hyperedges.

We have established that a hypergraph is hard to reconstruct purely based on
its projection if it contains many hyperedge overlaps of the two patterns. In
this section, we solve this by leveraging supervised signals. The high-level
idea is that we use a clique sampler to narrow the search space of hyperedges
(clique space in Fig.2), and then use a hyperedge classifier to identify
hyperedges from the narrowed space. Both modules are optimized/trained on the
training data.

Fig.3 gives a more detailed 4-step view, briefly explained in the caption.
They will be elaborated in the following subsections: Sec. 5.2 introduces an
important observation that underpins the clique sampler; Sec. 5.3 details the
clique sampler and its optimization; Sec. 5.4 expalins principles and designs
for the hyperedge classifier.

###  5.2. $\rho(n,k)$-consistency

The $\rho(n,k)$-consistency describes the consistency that we observe in
hyperedge distribution with regard to maximal cliques, among hypergraphs from
the same application domain, e.g. $\mathcal{H}_{0}$, $\mathcal{H}_{1}$. It is
an important property that we leverage in supervised reconstruction.

Given a hypergraph $\mathcal{H}=(V,\mathcal{E})$, its projection $G$, maximal
cliques $\mathcal{M}$, we use $\rho(n,k)$ to denote the expectation that we
find a unique hyperedge by randomly sampling a size-$k$ subset from a random
size-$n$ maximal clique. A $(n,k)$ is called valid if $1\leq k\leq n\leq N$,
with $N$ the size of the maximum clique. $\rho(n,k)$ can be estimated
empirically via the unbiased estimator $\hat{\rho}(n,k)$ defined as:

$\hat{\rho}(n,k)=\frac{|\mathcal{E}_{n,k}|}{|\mathcal{Q}_{n,k}|}$

where

$\displaystyle\mathcal{E}_{n,k}$ $\displaystyle=\\{S\in\mathcal{E}|S\subseteq
C,|S|=k,C\in\mathcal{M},|C|=n\\}$ $\displaystyle Q_{n,k}$
$\displaystyle=\\{(S,C)|S\subseteq
C,|S|=k,C\in\mathcal{M},|C|=n\\}\vspace{-5mm}$

$\mathcal{E}_{n,k}$ denotes the set of size-$k$ hyperedges in size-$n$ maximal
cliques. $Q_{n,k}$ denotes all possible ways to sample a size-$n$ maximal
clique and then a size-$k$ subset (i.e. a $k$-clique) from the maximal clique.
$|Q_{n,k}|$ can be further simplified as
$|\\{C|C\in\mathcal{M},|C|=n\\}|{n\choose k}$.

Our key observation is that if two hypergraphs e.g. $\mathcal{H}_{0}$,
$\mathcal{H}_{1}$, are generated from the same source, their hyperedge
distributions admit similar distributions of $\rho(n,k)$, which we call
$\rho(n,k)$-consistency. Fig.4(a) uses heatmaps to visualizes
$\rho(n,k)$-consistency on a famous communication dataset, Enron (Benson et
al., 2018), where $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ are split based on a
median timestamp of the emails (hyperedges). $n$ is plot on the $y$-axis, $k$
on the $x$-axis. Fig.4(b) further plots $\rho(n,k)$’s heatmaps for five other
datasets in a similar manner. From both figures, we observe that the
distributions of $\rho(n,k)$ exhibit good consistency between training and
query of the same dataset; in contrast, the distributions of $\rho(n,k)$
across datasets are much different. This visual observation can be further
confirmed by quantified measures (see Fig.14 in Appendix).

Also, notice that the second column and the diagonal are darkest, implying
that the ${n\choose k}$ term in $Q_{n,k}$ (the denominator) cannot dominate
the distribution. More concretely, ${n\choose k}$ reaches minimum when $k=n$
or $1$ and grows exponentially as $k$ approaches $0.5n$, and this is true
regardless of the data; here the quotient peaking at $k=2$ means that the term
$|\mathcal{E}_{n,k}|$ that reflects data is playing a numerically meaningful
role. By examining many datasets (see Fig.4(b)), we find that the $\rho(n,k)$
distribution can vary a lot, but there is always great consistency between
training hypergraphs and query hypergraphs from the same application domain.

(a)

(b)

Figure 4. (a) $\rho(n,k)$-consistency on dataset Enron (Benson et al., 2018),
where each node is an email address, each hyperedge is an email.
$\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ are obtained by splitting all emails
by a middle timestamp. (b) $\rho(n,k)$-consistency on more datasets. Notice
that heatmaps in the same columns are similar, while those in the same row are
much different.

Complexity. The main complexity of computing $\rho(n,k)$ involves two parts:
(a) computing $\mathcal{M}$; (b) computing $\mathcal{E}_{n,k}$ for all valid
$(n,k)$.

(a)’s complexity is $O(|\mathcal{M}|)$ as mentioned in Sec. 2. Though in worst
case $|\mathcal{M}|$ can be exponential to $|V|$, in practice we often observe
$|\mathcal{M}|$ on the same magnitude order as $|\mathcal{E}|$ (see Table 1),
which is an interesting phenomenon.

(b) requires matching size-$n$ maximal cliques with size-$k$ hyperedges for
each valid $(n,k)$ pair. The key is that in real-world data, the average
number of hyperedges incident to a node is usually a constant independent from
the growth of $|V|$ or $|\mathcal{M}|$ (see also $\bar{d}(V)$ in Table. 2),
known as the “sparsity of hypergraphs”(Kook et al., 2020). This property
greatly reduces the (average size of) search space for all size-$k$ hyperedges
in a size-$n$ maximal clique from $|\mathcal{E}|$ to $n\bar{d}(V)$. As we see
both $n$ and $\bar{d}(V)$ are typically under $50$ in practice and neither
grows with $|\mathcal{M}|$, b’s complexity can still be viewed as
$O(|\mathcal{M}|)$. Therefore, the total complexity for computing $\rho(n,k)$
is $O(|\mathcal{M}|)$. We extend this result with more empirical evidence in
Sec. 6.3

###  5.3. Clique Sampler

Given a query graph, usually we cannot afford to take all its cliques as
candidates for hyperedges: although we just mentioned that the number of
maximal cliques $|\mathcal{M}|$ is often manageable, the number of cliques
$|\mathcal{U}|$ can far exceed handling capacity as one size-$n$ maximal
clique produces $2^{n}-1$ cliques. Therefore, we create a clique sampler.
Assume we have a limited sampling budget $\beta$, our goal is to collect as
many hyperedges as possible by sampling $\beta$ cliques from $\mathcal{U}$.
Any hyperedge missed by our clique sampler loses the chance to be identified
by the hyperedge classifier in the future, so this step is crucial. Later we
show in Table 6 that good performance can be achieved by $\beta$’s that are
orders of magnitude smaller than —$\mathcal{U}$—.

As mentioned, by looking at just the query $G_{1}$ we cannot locate hyperedges
in the enormous search space of all cliques in $G_{1}$. Fortunately, we can
obtain hints from $G_{0}$ and $\mathcal{H}_{0}$. The idea is that we use
$G_{0}$ and $\mathcal{H}_{0}$ to optimize a clique sampler that verifiably
collects a good number of hyperedges. The optimization process, as marked in
Fig.3 step 1, can be viewed as a procedure that learns knowledge about where
to sample. Then in $G_{1}$, we use the optimized clique sampler to sample
cliques, shown in Fig.3 step 2. We ask that the sampler takes the following
form:

  * ($\star$)

For each valid $(n,k)$, we sample a total of $r_{n,k}|Q_{n,k}|$ size-$k$
subsets (i.e. $k$-cliques) from size-$n$ maximal cliques in the query graph,
subject to the sampling budget: $\sum_{n,k}{r_{n,k}|Q_{n,k}|}=\beta$

$r_{n,k}\in[0,1]$ is the sampling ratio of the $(n,k)$ cell, $|Q_{n,k}|$ is
the size of the $(n,k)$ cell’s sample space in $G_{0}$. To instantiate a
sampler, a $r_{n,k}$ should be specified for every valid $(n,k)$ cell. How to
determine $r_{n,k}$’s? We optimize $r_{n,k}$’s towards collecting the most
training hyperedges from $G_{0}$, with the objective:

$\displaystyle\\{r_{n,k}\\}$
$\displaystyle=\operatorname*{argmax}_{\\{r_{n,k}\\}}\;\mathbb{E}^{c}[\bigcup_{(n,k)}r_{n,k}\odot\mathcal{E}_{n,k}]\vspace{-3.5mm}$

$\odot$ is a set sampling operator that returns a uniformly downsampled subset
of $\mathcal{E}_{n,k}$ at downsampling rate $r_{n,k}$. $\odot$ is essentially
a generator for random finite set (Mullane et al., 2011). See A.4 for more
discussion. $\mathbb{E}^{c}[\cdot]$ returns the expected cardinality. Given
the maximization objective and $\rho(n,k)$-consistency, the optimized sampler
should also collect a good number of hyperedges when generalized to $G_{1}$.
Sec.6.5 validates this claim empirically.

Optimization. To collect more hyperedges from $G_{0}$, a heuristic is to
allocate all budget to the darkest cells of the training data’s heamap
(Fig.4(a)-left), where hyperedges most densely populate. However, a caveat is
that the set of hyperedges $\mathcal{E}_{n,k}$ in each $(n,k)$ cell are not
disjoint if the cells are in the same column. In other words, a size-$k$
clique can appear in multiple maximal cliques of different sizes. Therefore,
taking the darkest cells may not yield best result. In fact, optimizing the
objective above involves maximizing a monotone submodular function under
budget constraint, which is NP-hard.

In light of this, we design the greedy Alg. 1 to approximate the optimal
solution with worst-case guarantee. It takes four inputs: sampling budget
$\beta$, size of the maximum clique $N$, $\mathcal{E}_{n,k}$ and
$\mathcal{Q}_{n,k}$ for all $1\leq k\leq n\leq N$. Lines 2-7 initialize state
variables. Lines 8-16 run greedy selection iteratively.

Algorithm 1 Optimize Clique Sampler

1:$\beta$; $N$; $\mathcal{E}_{n,k}$, $\mathcal{Q}_{n,k}$ for all $1\leq k\leq
N,k\leq n\leq N$

2:for $k=1$ to $N$ do$\triangleright$ traverse $k$ to initialize state
variables

3: $\Gamma_{k}\leftarrow\emptyset$$\triangleright$ union of
$\mathcal{E}_{n,k}$’s picked from column $k$

4: $\omega_{k}\leftarrow\\{k,k+1,...,N\\}$$\triangleright$ available
column-$k$ cells

5: $r_{i,k}\leftarrow 0$ for $i\in\omega_{k}$ $\triangleright$ sampling ratios
for column-$k$ cells

6: $\Delta_{k},n_{k}\leftarrow\;$UPDATE ($k$, $\omega_{k}$, $\Gamma_{k}$,
$\mathcal{E}_{\cdot,k}$, $\mathcal{Q}_{\cdot,k}$)

7:end for

8:while $\beta>0$ do$\triangleright$ the greedy selection starts

9: $k\leftarrow\text{argmax}_{i}{\;\Delta_{i}}$$\triangleright$ selects the
next best $k$

10:
$r_{n_{k},k}\leftarrow\min\\{1,\frac{\beta}{|\mathcal{Q}_{n_{k},k}|}\\}$$\triangleright$
sets cell’s sampling ratio

11: $\Gamma_{k}\leftarrow\Gamma_{k}\cup\mathcal{E}_{n_{k},k}$$\triangleright$
updates state variables

12: $\omega_{k}\leftarrow\omega_{k}\backslash\\{n_{k}\\}$

13: $\beta\leftarrow\beta-|\mathcal{Q}_{n_{k},k}|$

14: $\Delta_{k},n_{k}\leftarrow\;$UPDATE ($k$, $\omega_{k}$, $\Gamma_{k}$,
$\mathcal{E}_{\cdot,k}$, $\mathcal{Q}_{\cdot,k}$)

15: if $\text{max}_{k}\;\Delta_{k}=0$ then break$\triangleright$ breaks if all
cells sampled

16:end while

17:return $r_{n,k}$ for all $1\leq k\leq N,k\leq n\leq N$

Subroutine 1 UPDATE

1:$k$; $\omega_{k}$; $\Gamma_{k}$; $\mathcal{E}_{\cdot,k}$;
$\mathcal{Q}_{\cdot,k}$

2:if $\omega_{k}\neq\emptyset$ then

3:
$\Delta^{\prime}\leftarrow\max_{n\in\omega_{k}}\frac{|\Gamma_{k}\cup\mathcal{E}_{n,k}|-|\Gamma_{k}|}{|\mathcal{Q}_{n,k}|}$

4:
$n^{\prime}\leftarrow\text{argmax}_{n\in\omega_{k}}\frac{|\Gamma_{k}\cup\mathcal{E}_{n,k}|-|\Gamma_{k}|}{|\mathcal{Q}_{n,k}|}$

5:else

6: $\Delta^{\prime}\leftarrow 0$; $n^{\prime}\leftarrow 0$;

7:end if

8:return $\Delta^{\prime}$, $n^{\prime}$

The initialization is done column-wise. In each column $k$, $\Gamma_{k}$
stores the union of all $\mathcal{E}_{n,k}$ that have been selected from
column $k$ so far; $\omega_{k}$ stores the row indices (i.e. $n$’s) of all
available cells in column $k$, i.e. cells that have not been selected;
$r_{i,k}$ is the sampling ratio of each valid cell; line 6 calls the
subroutine UPDATE to compute $\delta_{k}$, which is the best sampling
efficiency among all the available cells, and $n_{k}$, which is the row index
of that most efficient cell.

Lines 8-16 execute the greedy selection. In each iteration, we greedily take
the next most efficient cell among (the best of) all the columns, store the
decision in the corresponding $r$, and update ($\Gamma$, $\omega$,
$\delta_{k}$, $n_{k}$) with $k$ the column index of the selected cell in the
current iteration. Notice that only column $k$ needs to be updated because
$\mathcal{E}_{n,k}$’s with different $k$’s are independent. Finally, the
greedy stops when either having exceeded budget or having traversed all cells.

For a more intuitive view, please refer to Sec.6.5 where we do ablations on
this algorithm and visualize the iterations. As a side bonus, we will also see
in Sec. 6.3 that the greedy actually induces more diverse hyperedge sizes in
reconstruction.

###### Theorem 5.1.

Let $q$ be the expected number of hyperedges in $\mathcal{H}_{0}$ drawn by the
clique sampler optimized by Alg. 1; let $q^{*}$ be the expected number of
hyperedges in $\mathcal{H}_{0}$ drawn by the best-possible clique sampler,
with the same $\beta$. Then,

$q>(1-\frac{1}{e})q^{*}\approx 0.63q^{*}$

Theorem 5.1 gives an important quality guarantee on Alg. 1 by comparing its
result with the best-possible clique sampler. The actual $\frac{q}{q^{*}}$ can
often be much better than $0.63$. Besides, notice that Alg. 1 leaves at most
one $(n,k)$ cell partially sampled. Is that a good design? In fact, it can be
proved that there is always one best clique sampler that leaves at most one
$(n,k)$ cell partially sampled. Otherwise, we can always find two partially
sampled cells and relocate all our budget from one to the other to achieve a
higher $q$.

Relating to Error I & II. The effectiveness of our clique sampler can also be
understood from the perspective of reducing Error I and II. Taking Fig.4(a) as
an example: by learning which non-diagonal cells to sample, the clique sampler
essentially reduces Error I as well as the false negative part of Error II; by
learning which diagonal cells to sample, it further reduces the false positive
part of Error II.

Relating to Standard Submodular Optimization.Our clique sampler takes a
similar greedy form as the standard algorithm for submodular optimization.
However, our clique sampler actually solve a more challenging problem, whose
optimality guarantee is also harder to prove. Please see A.5 for more details.

Precision-Recall Tradeoff. For each dataset, $\beta$ should be specified by
humans. What is the best $\beta$? Clearly a larger $\beta$ yields a larger
$q$, and thus a higher recall $\frac{q}{|\mathcal{E}|}$ with our samples. On
the other hand, a larger $\beta$ also means a lower precision
$\frac{q}{\beta}$, as sparser regions get sampled. $\frac{q}{\beta}$ being
overly low harms sample quality and may jeopardize the training later. Such
tradeoff calls for more calibration of $\beta$. We empirically found it often
good to search $\beta$ in a range that makes
$\frac{q}{|\mathcal{E}|}\in[0.6,0.95]$. More tuning details are in C.

Complexity. The bottleneck of Alg. 1 is UPDATE. In each iteration after a $k$
is picked, UPDATE recomputes
$(|\Gamma_{k}\cup\mathcal{E}_{n,k}|-|\Gamma_{k}|)$ for all $n\in\omega_{k}$,
which is $O(\frac{|\mathcal{E}|}{N})$. Empirically we found the number of
iterations under the best $\beta$ always $O(N)$. $N$ is the size of the
maximum clique, and mostly falls in $[10,40]$ (see Fig.4(b)). Therefore, on
expectation we would traverse
$O(N)O(\frac{|\mathcal{E}|}{N})=O(|\mathcal{E}|)$ hyperedges if
$|\mathcal{E}_{n,k}|$ distributes evenly among different $k$’s. In the worst
case where $|\mathcal{E}_{n,k}|$’s are deadly skewed, this degenerates to
$O(N|\mathcal{E}|)$,

The optimized sampler samples $\beta$ cliques from $G_{0}$, and a similar
number of cliques from $G_{1}$. Later in Fig.11, we empirically confirm that
the two sampling sizes are similar indeed.

###  5.4. Hyperedge Classifier

A hyperedge classifier is a binary classification model that takes a target
clique in the projection as input, and outputs a 0/1 label indicating whether
the target clique is a hyperedge. We train the hyperedge classifier on
$(\mathcal{H}_{0},G_{0})$ where we have ground-truth labels (step 3, Fig.3),
and then use it to identify hyperedges from $G_{1}$ (step 4, Fig.3). To serve
this purpose, a hyperedge classifier should contain two parts (1) a feature
extractor that extracts expressive features for characterizing a target clique
as a subgraph, and (2) a binary classification model that takes an extracted
feature and outputs a 0/1 label. (2) is a standard task and so we use MLP with
one layer of $h=100$ hidden neurons. (1) requires more careful design. Next,
we first discuss (1)’s design principles, then provide two realizations that
we found work well. Our hyperedge classifier addresses Error I and II together
by fitting to the distribution of hyperedges with structural features of the
clique candidates as input.

####  5.4.1. Design Principles

Central to the design of a good feature extractor is a question: what type of
information should it capture about a target clique in the projection? In our
task setup, there are two constraints usable information to ensure broadest
usability of our approach: (1) we do not assume nodes to be attributed, or
edges to have multiplicity; (2) we focus on the inductive case where node
identities are not aligned across training and query (so positional embeddings
like DeepWalk (Perozzi et al., 2014) is unhelpful).

It thus becomes clearer that we are left with the structural features of and
around the target clique. Put differently, the classifier needs to well
characterize the connectivity properties of the local ego graph centered at
the target clique. As we will see in experiment, using structural features in
a supervised manner boosts reconstruction accuracy by an order of magnitude on
difficult datasets.

In that regard, any structural learning model that can well characterize the
structural features can potentially be the classifier — and there are plenty
of them operating on individual nodes (Henderson et al., 2012; Li et al.,
2020; Xu et al., 2018). However, what we do not know yet is what structural
features that characterize a clique (and its surroundings) are important, and
how they can be understood by humans in the clique’s context. Therefore, we
provide the following two feature extractors that accomplish the task via
interpretable features. It is worth mentioning though that they are not the
only choices.

####  5.4.2. “Count”-based Feature Extractor

Many powerful graph structural learning models use different notions of
“count” to characterize the local connectivity patterns. For example, GNNs
typically use node degrees as initial features when node attributes are
unavailable; the Weisfeiler-Lehman Test also updates a node’s color based on
the count of different colors in its neighborhood.

In the context of a target clique as a subgraph structure in a projection, the
notion of “count” can be especially rich in meaning: a target clique can be
characterized by the count of its [own nodes / neighboring nodes / neighboring
edges / attached maximal cliques] in many different ways. Therefore, we create
a total of 8 types of generalized count-based features, detailed in B. Despite
being conceptually simple, these count features works surprisingly well and
can be easily interpreted (see more in Supplement C).

####  5.4.3. Clique-motif-based Feature Extractor

Figure 5. 13 “clique motifs” that encode rich connectivity patterns around a
target clique $C$. Each clique motif is formed by 1 or 2 nodes in the target
clique $+$ 1 or 2 maximal cliques that contain the nodes.

As a second attempt we use maximal cliques as an intermediate that bridges the
projection and the hyperedges. The rationale behind is that the maximal
cliques of a projection can essentially be viewed as a preliminary guess of
the projection’s high-order structures. Such guess not only encompasses all
the projection’s information, but also in itself constitutes a partially
curated form of higher-order structures (which are indicative of the real
higher-order structures, i.e. hyperedges). Meanwhile, the synergy between
maximal cliques and nodes in the target clique also exhibit rich connectivity
patterns, which generalizes the notion of motif, as shown in Fig.5.

Fig.5 enumerates the all 13 connectivity patterns between 1 or 2 nodes of the
target clique and 1 or 2 maximal cliques that contain the target clique’s
nodes. For simplicity we restrict that maximal cliques are at most one hop
away from the target clique. We call the connectivity patterns clique motifs.
Compared to count features, clique motifs are a more principled and systematic
way to extract structural properties. There are two types of components in a
clique motif: node, maximal clique, and three types of relationships: node-
node, node-maximal clique, maxmimal clique-maximal clique. Their concrete
meanings are explained in the legend. We say that a clique motif is attached
to a target clique $C$ if the clique motif contains at least one node of $C$.
We further use $\Phi_{i}^{{(C)}}$ to denote the set of type-$i$ clique motifs
attached to $C$, with $1\leq i\leq 13$.

Given a target clique $C$, how to use clique motifs attached to $C$ to
characterize structures around $C$? We define $C$’s structural feature as a
concatenation of 13 vectors:
$[u_{1}^{{(C)}};u_{2}^{{(C)}};...,u_{13}^{{(C)}}]$. $u_{i}^{{(C)}}$ is a
vector of descriptive statistics that summarize the vectorized distribution of
type-$i$ clique motifs attached to $C$. Mathematically:

$\displaystyle\hskip 8.53581ptu_{i}^{{(C)}}$
$\displaystyle=\textbf{S{\scriptsize UMMARIZE}}(P_{i}^{{(C)}})$
$\displaystyle\vspace{-0.8mm}\hskip 8.53581ptP_{i}^{{(C)}}$
$\displaystyle=\begin{cases}[\textbf{C{\scriptsize OUNT}}(C,i,\\{v\\})\text{,
for }v\text{ in }C],\hskip 42.67912pt\text{if $1\leq i\leq 3$};\\\
[\textbf{C{\scriptsize OUNT}}(C,i,\\{v1,v2\\})\text{, for }v_{1},v_{2}\text{
in }C],\hskip 12.23468pt\text{if $4\leq i\leq 13$};\\\ \end{cases}$

$P_{i}^{{(C)}}$ is a vectorized distribution in the form of an array of counts
regarding $i$ and $C$. $\textbf{C{\scriptsize
OUNT}}(C,i,\chi)=|\\{\phi\in\Phi_{i}^{{(C)}}|\chi\subseteq\phi\\}|$. Finally,
$\textbf{S{\scriptsize UMMARIZE}}(P_{i}^{{(C)}})$ is a function that takes in
a vectorized distribution $P_{i}^{{(C)}}$ and outputs a vector of statistical
descriptors. Here we simply define it to comprise of 4 basic statistical
descriptors:

$\textbf{S{\scriptsize UMMARIZE}}(P_{i}^{{(C)}})=[\text{\small
mean}(P_{i}^{{(C)}}),\text{\small std}(P_{i}^{{(C)}}),\text{{\small
min}}(P_{i}^{{(C)}}),\text{\small max}(P_{i}^{{(C)}})]\vspace{-1mm}$

As we have 13 clique motifs, these amount to 52 structural features. On the
high level, clique motifs extend the well-tested motif methods on graphs to
hypergraph projections with clique structures. Compared to count features,
clique motifs capture structural features in a more principled manner.

##  6\. Experiment

Dataset | $|V|$ | $|\mathcal{E}|$ |  $\mu(\mathcal{E})$ |  $\sigma(\mathcal{E})$ |  $\bar{d}(V)$ |  $|\mathcal{M}|$
---|---|---|---|---|---|---
Enron (Benson et al., 2018) | 142 recipients | 756 emails |  3.0 |  2.0 |  16.0 |  362
DBLP (Benson et al., 2018) | 319,916 authors | 197,067 papers |  3.0 |  1.7 |  1.83 |  166,571
P. School (Benson et al., 2018) | 242 students | 6,352 chats |  2.4 |  0.6 |  63.5 |  15,017
H. School (Benson et al., 2018) | 327 students | 3,909 chats |  2.3 |  0.5 |  27.8 |  3,279
Foursquare (Young et al., 2021) | 2,334 restaurants | 1,019 footprints |  6.4 |  6.5 |  2.80 |  8,135
Hosts-Virus (Young et al., 2021) | 466 hosts | 218 virus |  5.6 |  9.0 |  2.60 |  361
Directors (Young et al., 2021) | 522 directors | 102 boards |  5.4 |  2.2 |  1.05 |  102
Crimes (Young et al., 2021) | 510 victims | 256 homicides |  3.0 |  2.3 |  1.48 |  207
Table 2. Summary of the datasets (query split). $\mu(\mathcal{E})$ and
$\sigma(\mathcal{E})$ stand for mean and std. of the distribution of the
hyperedges’ size. $\bar{d}(V)$: average degree of nodes (w.r.t. hyperedges).
$|\mathcal{M}|$: maximal cliques.

How well does our approach work in practice? How do we make sense of the
reconstruction result? Is our approach robust to scarcity or distribution
shift of training data? These questions are systematically studied in our
experiments.

We introduce settings in Sec. 6.1, followed by performance comparisons of all
methods in Sec. 6.2. In Sec, 6.3 we evaluate the reconstruction on more
dimensions and check what exactly gets recovered. In Sec. 6.4, we evaluate
reconstructions in semi-supervised setting and transferred setting — two
important extensions involving label scarcity and distribution shift,
respectively. Sec. 6.5 reports ablation studies that show the effectiveness of
our clique sampler.

Reproducibility: Our code and data are published at bit.ly/SHyRe.

###  6.1. Experimental Settings

Baselines. For comparison we adapt 7 methods originally proposed in four
different task domains. They are chosen for (1) their best relevance to our
task, and/or (2) their state-of-the-art status within their own task domain.
The baselines and their task domains are:

  * •

Community Detection: Demon (Coscia et al., 2012), CFinder (Palla et al., 2005)

  * •

Clique Decomposition: Max Clique (Bron and Kerbosch, 1973), Edge Clique Cover
(Conte et al., 2016)

  * •

Hyperedge Prediction: Hyper-SAGNN (Zhang et al., 2019), CMM (Zhang et al.,
2018);

  * •

Probabilistic Models: Bayesian-MDL (Young et al., 2021).

Since they are evaluated on our new task, adaptation is necessary, and
decisions are made towards the best fairness of comparison. For example, both
our method and Bayesian-MDL use maximal clique algorithm (i.e. the Max Clique
baseline) as a preprocessing step. Our evaluation ensures that all three of
them use the same implementation as introduced in (Bron and Kerbosch, 1973).
See Appendix C for more details on selection criteria and adaptation.

Data Preparation. We use 8 real-world datasets containing different high-order
relationships: email correspondence, paper coauthorship, social interactions,
biological groups, shared restaurants etc. They feature significantly varying
number of nodes, hyperedges, distribution of hyperedge sizes, etc. summarized
in Table 2.

To generate a training set and a query set, we follow two common standards to
split the collection of hyperedges in each dataset: (1) For datasets that come
in natural segments, such as DBLP and Enron whose hyperedges are timestamped,
we follow their segments so that training and query contain two disjoint and
roughly equal-sized sets of hyperedges. For DBLP, we construct
$\mathcal{H}_{0}$ from year 2011 and $\mathcal{H}_{1}$ from year 2010; for
Enron, we use 02/27/2001, 23:59 as a median timestamp to split all emails into
$\mathcal{H}_{0}$ (first half) and $\mathcal{H}_{1}$ (second half). (2) For
all the other datasets that lack natural segments, we randomly split the set
of hyperedges into halves. To enforce inductiveness, we randomly re-index node
IDs in each split. Finally, we project $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$
to get $G_{0}$ and $G_{1}$ respectively.

Beyond the two common standards, we conduct semi-supervised reconstruction and
transfer reconstruction in Sec. 6.4.

Training Configuration. For models requiring back propagation, we use cross
entropy loss and optimize using Adam for $2000$ epochs and learning rate
$0.0001$. Those with randomized modules are repeated 10 times with different
seeds. See C for more tuning details.

###  6.2. Quality of Reconstruction

| DBLP | Enron | P.School | H.School | Foursquare | Hosts-Virus | Directors | Crimes
---|---|---|---|---|---|---|---|---
CFinder (Palla et al., 2005) | 11.35 | 0.45 | 0.00 | 0.00 | 0.39 | 5.02 | 41.18 | 6.86
Demon (Coscia et al., 2012) | - | 2.35 | 0.09 | 2.97 | 16.51 | 7.28 | 90.48 | 63.81
Maximal Clique (Bron and Kerbosch, 1973) | 79.13 | 4.19 | 0.09 | 2.38 | 9.62 | 22.41 | 100.0 | 78.76
Clique Covering (Conte et al., 2016) | 73.15 | 6.61 | 1.95 | 6.89 | 79.89 | 41.00 | 100.0 | 75.78
Hyper-SAGNN (Zhang et al., 2019) | 0.12$\pm$0.01 | 0.19$\pm$0.17 | 12.13$\pm$0.33 | 8.89$\pm$0.15 | 0.01$\pm$0.01 | 7.35$\pm$0.48 | 1.94$\pm$1.12 | 0.86$\pm$ 0.17
CMM (Zhang et al., 2018) | 0.11$\pm$0.04 | 0.48$\pm$0.06 | 14.26$\pm$0.92 | 4.27$\pm$0.46 | 0.00$\pm$0.00 | 6.44$\pm$ 0.82 | 2.55$\pm$0.62 | 0.57$\pm$0.29
Bayesian-MDL (Young et al., 2021) | 73.08$\pm$0.00 | 4.57$\pm$0.07 | 0.18$\pm$0.01 | 3.58$\pm$0.03 | 69.93$\pm$0.59 | 40.24$\pm$0.12 | 100.0$\pm$0.00 | 74.91$\pm$0.11
SHyRe-count | 81.18$\pm$0.02 | 13.50$\pm$0.32 | 42.60$\pm$0.61 | 54.56$\pm$0.10 | 74.56$\pm$0.32 | 48.85$\pm$0.11 | 100.0$\pm$0.00 | 79.18$\pm$0.42
SHyRe-motif | 81.19$\pm$0.02 | 16.02$\pm$0.35 | 43.06$\pm$0.77 | 54.39$\pm$0.25 | 71.88$\pm$0.28 | 45.16$\pm$0.55 | 100.0$\pm$0.00 | 79.27$\pm$0.40
Table 3. Comparison of different methods on hypergraph reconstruction,
performance measured in Jaccard Similarity (%). Standard deviation is dropped
where the method is deterministic or randomization has no effect on
performance. “-” means the algorithm did not stop in 72 hours.

We name our approach SHyRe (Supervised Hypergraph Reconstruction). Table 3
shows the quality of reconstruction measured in Jaccard Score (see Sec. 3).
The two variants of SHyRe strongly outperform all baselines on most datasets
(7/8). The improvement is most significant on hard datasets such as P. School,
H.School and Enron. We attribute the success to our reconstruction framework
that makes the best out of supervised signals: we derive insights from our
topological analysis, and find ways to efficiently probe high-quality
candidates for hyperedges and for designing good classifiers.

The two variants are close to each other by performance. SHyRe-motif very
marginally wins if we count the number of datasets on which one variant
achieves the best score. We further study the two variants and found that they
both capture a strong feature (more in 6). Among the baselines, Clique
Covering and Bayesian-MDL work relatively well. Still, the “principle of
parsimony” (Young et al., 2021) suffers on dense hypergraphs if we interpret
the result according to Table 2.

Fig.14 further visualizes fine-grained performance measured by partitioned
errors as defined in Def. . Further explanations are included in the caption.
We can see that SHyRe variants significantly reduce more Error I and II than
the baselines.

###  6.3. Further Evaluations of Reconstruction

Beyond Jaccard score, we seek to further understand (a) whether our
reconstructions preserve important properties of the original hypergraphs, (b)
the running time of our reconstructions, and, more curiously, (c) what exactly
gets recovered. To this end, we study the property space, the asymptotic
running time, and an actual visualization of the reconstructions.

Property Space. The procedure works as follows: we first characterize the
property space of the reconstruction using the middle four columns of Table 2:
$[|\mathcal{E}|,\mu(\mathcal{E}),\sigma(\mathcal{E}),\bar{d}(V)]$. $|V|$ is
excluded from the property vector as it is known from the input. Then for each
(dataset, method) combination, we analyze the reconstruction and obtain a
unique property vector. We use PCA to project all (normalized) property
vectors into 2D space, visualized in Fig.7.

In Fig.7, colors encode datasets, and marker styles encode methods. Compared
with baselines, SHyRe variants ( ○and $\times$) produce reconstructions more
similar to the ground truth ($\blacksquare$). The reasons are two-fold: (1)
SHyRe variants usually achieve better accuracy, which encourages a more
aligned property space; (2) as a bonus of our greedy Alg. 1, in each iteration
it tends to look for a cell from a different column. This is because cells in
the same column has diminishing returns due to overlapping of
$\mathcal{E}_{n,k}$ with same $k$, whereas cells in different columns remain
unaffected as they have hyperedges of different sizes. The inclination of
having diverse hyperedge sizes reduces the chance of a skewed distribution.

We also observe that markers of the same colors are generally clustered,
meaning that most baselines work to some extent despite low accuracy
sometimes. Fig.7 also embeds a historgram showing the size distribution of the
reconstructed hyperedges on DBLP. We see the distribution obtained by SHyRe
aligns decently with the ground truth, especially with large hyperedges. Some
errors are made with sizes 1 and 2, which are mostly the Fig.2 nested cases.

Figure 6. Partitioned Performance of all methods on all datasets. Recall that
the Error I and II are mistakes made by Max Clique (Def.6.2). Other methods
may make mistakes that Max Clique does not make, which are counted as “Other
Error”. We can see that SHyRe reduce more Error I and II than other baselines.
Figure 7. 2D embeddings of statistical properties of reconstructed
hypergraphs. Different colors correspond to different datasets; different
markers correspond to different methods. Notice that reconstructions of SHyRe
are closest to ground truth ($\blacksquare$) on most datasets.

Running Time. We claim in Sec. 5 that the clique sampler’s complexity is close
to $O(|\mathcal{M}|)+O(|\mathcal{E}|)=O(|\mathcal{M}|)$ in practice. Here this
claim is substantiated with an asymptotic running time analysis. Both the
clique sampler (Step 1, 2 in Fig.3) and the hyperedge classifier (Step 3, 4 in
Fig.3) are tested. For $p\in[30,100]$, We randomly sample $p\%$ hyperedges
from DBLP and record the CPU time for running both modules of SHyRe-motif. The
result is plot in Fig.8. It shows that both the total CPU time and the number
of maximal cliques are roughly linear to the data usage (size), which verifies
our claim. We provide additional statistics all methods’ time complexity in
Fig.15 Appendix.

Figure 8. Asymptotic running time analysis of SHyRe-motif on DBLP. The bar
plot is aligned with the left y-axis, and the line plot with the right. Notice
that both the total CPU time and the number of maximal cliques are roughly
linear to the data usage (size).

Visualizing the Reconstruction. Fig.9 visualizes a portion of the actual
reconstructed hypergraph by SHyRe-count on DBLP dataset. We include more
explanation and analysis in the caption.

Figure 9. A small part of the hypergraph reconstructed by SHyRe-motif on DBLP
dataset. Projection $G_{1}$ is drawn in black. The shaded ellipsis are the
reconstructed hyperedges. Those with green dashed edges are difficult to
reconstruct in the absence of the training data. Notice that
$\\{3,12,2,0,13,1\\}$ is a maximal clique (in this local graph).

###  6.4. Label Scarcity and Distribution Shift

So far, we have assumed that our training split consists of a comparable
number of hyperedges as the query split. However, sometimes we may only have
access to a small subset of hyperedges or a different but similar dataset.
Will the scarcity of training data or the distribution shift become a problem?
We conduct mini-studies to find out more about reconstruction based on semi-
supervised learning a well as transfer learning.

We choose three datasets of different reconstruction difficulties: DBLP,
Hosts-Virus, and Enron. For each, we randomly drop 80% of the hyperedges in
the training split. Our framework is trained and tuned the same way as in the
main experiment.

Table 4 shows the result. We can see the accuracy of the reconstruction is
negatively influenced on all datasets. However, SHyRe on 20% data still
outperforms the best baseline on full data, meaning that it remains well
functioning in a semi-supervised setting. Comparing column-wise, the influence
is negligible on easy datasets, small on moderately hard datasets, and large
on very hard datasets.

For transfer learning, we train on DBLP 2011, and test SHyRe’s performance on
various other DBLP slices as well as Microsoft Academic Graphs (MAG), a
different bibliographical database similar to DBLP. Fig.10 shows the result.
We can see that SHyRe remains relatively robust to the distribution shift.

Figure 10. Performance of transfer learning: trained on DBLP2011 and tested on various other coauthorship datasets. | DBLP | Hosts-Virus | Enron
---|---|---|---
Best Baseline (full) | 79.13 | 41.00 | 6.61
SHyRe-motif (full) |  81.19$\pm$0.02 |  45.16$\pm$0.55 |  16.02$\pm$0.35
SHyRe-count (20%) |  81.17$\pm$0.01 |  44.02$\pm$0.39 |  6.43$\pm$0.18
SHyRe-motif (20%) |  81.17$\pm$0.01 |  44.48$\pm$0.21 |  10.56$\pm$0.92
Table 4. Performance of semi-supervised reconstruction using 20% of the
training hyperedges, measured in Jaccard Similarity.

###  6.5. Ablation Study on Clique Sampler

In Sec. 5.3 we extensively discuss how to optimize the clique sampler. One
might argue that the optimization appears complex: can we adopt a simpler
heuristic for sampling which works independently of the notion of $r_{n,k}$’s?
We investigate this via an ablation study.

We test three sampling heuristics that might replace the clique sampler. 1.
“random”: we randomly sample $\beta$ cliques from the projection as
candidates. While it is hard to achieve strict uniformness (khorvash, 2009),
we approximate this by growing a clique from a random node and stopping the
growth when the clique reaches a random size; 2.“small”: we randomly sample
$\beta$ cliques of sizes 1 and 2 (i.e. nodes and edges); 3.“head & tail”: we
randomly sample $\beta$ cliques from all cliques of sizes 1 and 2 as well as
maximal cliques.

Fig.11 compares the efficacy in the sampling stage on Enron dataset. It shows
that our clique sampler significantly outperforms all heuristics and so it
cannot be replaced. Also, the the great alignment between the training curve
and query curve means our clique sampler generalizes well. We further report
reconstruction performance on 3 datasets in Table 7, which also confirms this
point.

Figure 11. Our clique sampler and ablation studies. Each marker is an
iteration in Alg. 1. The alignment between the training curve and the query
curve shows that our clique sampler generalizes well.

##  7\. Additional Related Work

There are three lines of work pertinent to the reconstruction task.

Edge Clique Covering is to find a minimal set of cliques that cover all the
graph’s edges. The clique-based projection makes this task highly relevant.
(Erdös et al., 1966) proves any graph can be covered by at most
$[\frac{|V|^{2}}{4}]$ cliques. (Conte et al., 2016) finds a fast heuristic for
approximating the solution. (Young et al., 2021) creates a probabilistic
framework to redefine and solve the task. However, this line of work shares
the “principle of parsimony”, which is often impractical in real-world
datasets.

Hyperedge Prediction is to identify missing hyperedges of an incomplete
hypergraph from a pool of given candidates. Existing work focuses on
characterize a node set’s structural features. The methods span proximity
measures (Benson et al., 2018), deep learning (Li et al., 2020; Zhang et al.,
2019), and matrix factorization (Zhang et al., 2018). Despite the relevance,
the task has a very different setting and focus from ours as mentioned in Sec.
1.

Community Detection finds node clusters within which edge density is much
higher than the outside. Existing work roughly comes in two categories per the
community type: disjoint (Que et al., [n. d.]; Traag et al., 2019), and
overlapping (Coscia et al., 2012; Palla et al., 2005). As mentioned, however,
the notion of “relative density” is not compatible with our focus on cliques.

##  8\. Conclusion

We propose the supervised hypergraph reconstruction task to effectively
understand and compensate for the loss of high-order information common in
graph data analysis. Our well-motivated reconstruction framework consists of a
clique sampler and a hyperedge classifier. Its success is substantiated by
extensive experiments. For future work, our setting can be extended in many
meaningful directions. For example, how can we improve the reconstruction if
we have node attributes or edge multiplicity? What if a hyperedge is projected
not into a clique but into a “star” or a “line”? These studies will
substantially benefit graph analysis and scientific discovery.

## References

  * (1)
  * Arya et al. (2020) Devanshu Arya, Deepak K Gupta, Stevan Rudinac, and Marcel Worring. 2020.  Hypersage: Generalizing inductive representation learning on hypergraphs.  _arXiv preprint arXiv:2010.04558_ (2020).
  * Arya and Worring (2018) Devanshu Arya and Marcel Worring. 2018.  Exploiting relational information in social networks using geometric deep learning on hypergraphs. In _Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval_. 117–125.
  * Beeri et al. (1983) Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. 1983.  On the desirability of acyclic database schemes.  _Journal of the ACM (JACM)_ 30, 3 (1983).
  * Benson et al. (2018) Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018.  Simplicial closure and higher-order link prediction.  _Proceedings of the National Academy of Sciences_ 115, 48 (2018), E11221–E11230.
  * Berge (1973) Claude Berge. 1973\.  Graphs and hypergraphs.  (1973).
  * Berge and Duchet (1975) Claude Berge and Pierre Duchet. 1975.  A generalization of Gilmore’s theorem.  _Recent advances in graph theory_ (1975), 49–55.
  * Bron and Kerbosch (1973) Coen Bron and Joep Kerbosch. 1973.  Algorithm 457: finding all cliques of an undirected graph.  _Commun. ACM_ 16, 9 (1973), 575–577.
  * Brouwer et al. (2013) Andries E Brouwer, CF Mills, WH Mills, and A Verbeek. 2013\.  Counting families of mutually intersecting sets.  _the electronic journal of combinatorics_ (2013), P8–P8.
  * Conte et al. (2016) Alessio Conte, Roberto Grossi, and Andrea Marino. 2016\.  Clique covering of large real-world networks. In _31st ACM Symposium on Applied Computing_. 1134–1139.
  * Coscia et al. (2012) Michele Coscia, Giulio Rossetti, Fosca Giannotti, and Dino Pedreschi. 2012.  Demon: a local-first discovery method for overlapping communities. In _Proceedings of the 18th ACM SIGKDD international conference_. 615–623.
  * Dai et al. (2020) Sicheng Dai, Hélène Bouchet, Aurélie Nardy, Eric Fleury, Jean-Pierre Chevrot, and Márton Karsai. 2020.  Temporal social network reconstruction using wireless proximity sensors: model selection and consequences.  _EPJ Data Science_ (2020).
  * Ebbinghaus and Flum (1999) Heinz-Dieter Ebbinghaus and Jörg Flum. 1999.  _Finite model theory_.  Springer Science & Business Media.
  * Erdös et al. (1966) Paul Erdös, Adolph W Goodman, and Louis Pósa. 1966\.  The representation of a graph by set intersections.  _Canadian Journal of Mathematics_ 18 (1966), 106–112.
  * Henderson et al. (2012) Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. 2012.  Rolx: structural role extraction & mining in large graphs. In _Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining_.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ 33 (2020), 22118–22133.
  * khorvash (2009) Massih khorvash. 2009\.  _On uniform sampling of cliques_.  Ph. D. Dissertation. University of British Columbia.  https://doi.org/10.14288/1.0051700
  * Klimt and Yang (2004) Bryan Klimt and Yiming Yang. 2004.  Introducing the Enron corpus.. In _CEAS_.
  * Kook et al. (2020) Yunbum Kook, Jihoon Ko, and Kijung Shin. 2020.  Evolution of real-world hypergraphs: Patterns and models without oracles. In _2020 IEEE International Conference on Data Mining (ICDM)_. IEEE, 272–281.
  * Leskovec et al. (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005\.  Graphs over time: densification laws, shrinking diameters and possible explanations. In _SIGKDD_.
  * Li et al. (2020) Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. 2020\.  Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning.  _Advances in Neural Information Processing Systems_ 33 (2020).
  * Madan et al. (2011) Anmol Madan, Manuel Cebrian, Sai Moturu, Katayoun Farrahi, et al. 2011\.  Sensing the” health state” of a community.  _IEEE Pervasive Computing_ 11, 4 (2011).
  * Mullane et al. (2011) John Mullane, Ba-Ngu Vo, Martin D Adams, and Ba-Tuong Vo. 2011\.  A random-finite-set approach to Bayesian SLAM.  _IEEE transactions on robotics_ 27, 2 (2011).
  * Newman (2004) Mark EJ Newman. 2004\.  Coauthorship networks and patterns of scientific collaboration.  _Proceedings of the national academy of sciences_ 101, suppl 1 (2004).
  * Ozella et al. (2021) Laura Ozella, Daniela Paolotti, Guilherme Lichand, Jorge P Rodríguez, Simon Haenni, John Phuka, Onicio B Leal-Neto, and Ciro Cattuto. 2021.  Using wearable proximity sensors to characterize social contact patterns in a village of rural Malawi.  _EPJ Data Science_ 10, 1 (2021), 46.
  * Palla et al. (2005) Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005.  Uncovering the overlapping community structure of complex networks in nature and society.  _nature_ 435, 7043 (2005), 814–818.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _Proceedings of the 20th ACM SIGKDD conference_.
  * Que et al. ([n. d.]) Xinyu Que, Fabio Checconi, Fabrizio Petrini, and John A Gunnels. [n. d.].  Scalable community detection with the louvain algorithm. In _2015 IEEE IPDPS_. IEEE.
  * Safari-Alighiarloo et al. (2014) Nahid Safari-Alighiarloo, Mohammad Taghizadeh, Mostafa Rezaei-Tavirani, Bahram Goliaei, and Asghar Peyvandi. 2014.  Protein-protein interaction networks and complex diseases.  _Gastroenterology and Hepatology_ (2014), 17.
  * Sarigöl et al. (2014) Emre Sarigöl, René Pfitzner, Ingo Scholtes, Antonios Garas, and Frank Schweitzer. 2014.  Predicting scientific success based on coauthorship networks.  _EPJ Data Science_ 3 (2014), 1–16.
  * Tomita et al. (2006) Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006\.  The worst-case time complexity for generating all maximal cliques and computational experiments.  _Theoretical computer science_ 363, 1 (2006), 28–42.
  * Traag et al. (2019) Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. 2019\.  From Louvain to Leiden: guaranteeing well-connected communities.  _Scientific reports_ 9, 1 (2019).
  * Wolf et al. (2016) Michael M Wolf, Alicia M Klinvex, and Daniel M Dunlavy. 2016\.  Advantages to modeling relational data using hypergraphs versus graphs. In _2016 IEEE High Performance Extreme Computing Conference (HPEC)_. IEEE, 1–7.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ (2018).
  * Xu et al. (2013) Ye Xu, Dan Rockmore, and Adam M. Kleinbaum. 2013.  Hyperlink Prediction in Hypernetworks Using Latent Social Features. In _Discovery Science_.
  * Yadati et al. (2020) Naganand Yadati, Vikram Nitin, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. 2020.  _NHP: Neural Hypergraph Link Prediction_.  New York, NY, USA, 1705–1714.
  * Young et al. (2021) Jean-Gabriel Young, Giovanni Petri, and Tiago P Peixoto. 2021\.  Hypergraph reconstruction from network data.  _Communications Physics_ 4, 1 (2021), 1–11.
  * Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. 2018\.  Beyond link prediction: Predicting hyperlinks in adjacency space. In _AAAI 2018_.
  * Zhang et al. (2019) Ruochi Zhang, Yuesong Zou, and Jian Ma. 2019.  Hyper-SAGNN: a self-attention based graph neural network for hypergraphs. In _ICLR 2019_.

##  Appendix A Proofs

###  A.1. Proof of Theorem 4.1

###### Proof.

From Def. 2, it suffices to show that for every $C$ that is not a maximal
clique, $C$ is not in $\mathcal{E}$. This holds because in that case $C$ has
to be the proper subset of some maximal clique $C^{\prime}\in\mathcal{E}$, but
since $H$ is Sperner, $C$ cannot be a hyperedge. ∎

###  A.2. Proof of Theorem 4.2

###### Proof.

The “if” direction: Suppose that $\mathcal{H}$ is not conformal. According to
Def. 2, we know that there exists a maximal clique $C\notin\mathcal{E}$.
Clearly for every $C$ with $|C|\leq 2$, $|C|\in\mathcal{E}$. For a
$C\notin\mathcal{E}$ and $|C|\geq 3$, pick any two nodes $v_{1},v_{2}\in C$.
Because they are connected, $v_{1},v_{2}$ must be in some hyperedge $E_{i}$.
Now pick a third node $v_{3}\notin E_{i}$. Likewise, there exists some
different $E_{j}$ such that $v_{1},v_{3}\in E_{2}$, and some different $E_{q}$
such that $v_{2},v_{3}\in E_{3}$. Notice that $E_{j}\neq E_{q}$ because
otherwise the three nodes would be in the same hyperedge. Now we have
$\\{v_{1},v_{2},v_{3}\\}\subseteq(E_{i}\cap E_{j})\cup(E_{j}\cap
E_{q})\cup(E_{q}\cap E_{i})$. Because $\\{v_{1},v_{2},v_{3}\\}$ is not in the
same hyperedge, $(E_{i}\cap E_{j})\cup(E_{j}\cap E_{q})\cup(E_{q}\cap E_{i})$
is also not in the same hyperedge.

The “only if” direction: Because every two of the three intersections share a
common hyperedge, their union is a clique. The clique must be contained by
some hyperedge, because otherwise the maximal clique containing the clique is
not contained by any hyperedge. ∎

Alternatively, there is a less intuitive proof that builds upon results from
existing work in a detour: It can be proved that $\mathcal{H}$ being conformal
is equivalent to its dual $\mathcal{H}^{\prime}$ being Helly (Berge, 1973).
According to an equivalence to Helly property mentioned in (Berge and Duchet,
1975), for every set $A$ of 3 nodes in $\mathcal{H}^{\prime}$, the
intersection of the edges $E_{i}$ with $|E_{i}\cap A|\geq k$ is non-empty.
Upon a dual transformation, this result can be translated into the statement
of Theorem 4.1. We refer the interested readers to the original text.

###  A.3. Proof of Theorem 4.3

Given a set $X=\\{1,2,...,m\\}$ and a hypergraph
$\mathcal{H}=(V,\\{E_{1},...E_{m}\\})$, we define $f:2^{X}\rightarrow 2^{V}$
to be:

$f(S)=\left(\bigcap_{i\in S}E_{i}\right)\bigcap\left(\bigcap_{i\in X\backslash
S}\bar{E_{i}}\right),\;S\subseteq X$

where $\bar{E_{i}}=V\backslash E_{i}$.

###### Lemma A.1.

$\\{f(S)|S\in 2^{X}\\}$ is a partition of $V$.

###### Proof.

Clearly $f(S_{i})\cap f(S_{j})=\emptyset$ for all $S_{i}\neq S_{j}$, so
elements in $\\{f(S)|S\in 2^{X}\\}$ are disjoint. Meanwhile, for every node
$v\in V$, we can construct a $S=\\{i|v\in E_{i}\\}$ so that $v\in f(S)$.
Therefore, the union of all elements in $\\{f(S)|S\in 2^{X}\\}$ spans $V$. ∎

Because Lemma A.1 holds, for any $v\in V$ we can define the reverse function
$f^{-1}(v)=S\Leftrightarrow v\in f(S)$. Here $f^{-1}$ is a signature function
that represents a node in $V$ by a subset of $X$, whose physical meaning is
the intersection of hyperedges in $\mathcal{H}$.

###### Lemma A.2.

If $S_{1}\cap S_{2}\neq\emptyset,S_{1},S_{2}\subseteq X$, then for every
$v_{1}\in f(S_{1})$ and $v_{2}\in f(S_{2})$, $(v_{1},v_{2})$ is an edge in
$H$’s projection $G$. Reversely, if $(v_{1},v_{2})$ is an edge in $G$,
$f^{-1}(v_{1})\cap f^{-1}(v_{2})\neq\emptyset$.

###### Proof.

According to the definition of $f(S)$, $\forall i\in S_{1}\cap
S_{2},\;v_{1},v_{2}\in E_{i}$. Appearing in the same hyperedge means that they
are connected in $G$, so the first part is proved. If $(v_{1},v_{2})$ is an
edge in $G$, there exists an $E_{i}$ that contains both nodes, so
$f^{-1}(v_{1})\cap f^{-1}(v_{2})\supseteq\\{i\\}\neq\emptyset$. ∎

An intersecting family $\mathcal{F}$ is a set of non-empty sets with non-empty
pairwise intersection, i.e. $S_{i}\cap S_{j}\neq\emptyset,\;\;\forall
S_{i},S_{j}\in\mathcal{F}$. Given a set $X$, a maximal intersecting family of
subsets, is an intersecting family of set $\mathcal{F}$ that satisfies two
additional conditions: (1) Each element of $\mathcal{F}$ is a subset of $X$;
(2) No other subset of $X$ can be added to $\mathcal{F}$.

###### Lemma A.3.

Given a a hypergraph $\mathcal{H}=(V,\\{E_{1},E_{2},...E_{m}\\})$, its
projection $G$, and $X=\\{1,2,...,m\\}$, the two statements below are true:

  * •

If a node set $C\subseteq V$ is a maximal clique in $G$, then
$\\{f^{-1}(v)|v\in C\\}$ is a maximal intersecting family of subsets of $X$.

  * •

Reversely, if $\mathcal{F}$ is a maximal intersecting family of subsets of
$X$, then $\cup_{S\in\mathcal{F}}f(S)$ is a maximal clique in $G$.

###### Proof.

For the first statement, clearly $\forall v\in V,\;f^{-1}(v)\subseteq X$.
Because $C$ is a clique, every pair of nodes in $C$ is an edge in $G$.
According to Lemma A.2, $\forall v_{1},v_{2}\in C,\;f^{-1}(v_{1})\cap
f^{-1}(v_{2})\neq\emptyset$. Finally, because $C$ is maximal, there does not
exist a node $v\in V$ that can be added to $C$. Equivalently there does not
exist a $S=f^{-1}(v)$ that can be added to $f^{-1}(C)$. Therefore, $f^{-1}(C)$
is maximal.

For the second statement, because $\mathcal{F}$ is an intersecting family,
$\forall S_{1},S_{2}\subseteq\mathcal{F},\;S_{1}\cap S_{2}\neq\emptyset$.
According to Lemma A.2, $\forall v_{1},v_{2}\in f(\mathcal{F})$,
$(v_{1},v_{2})$ is an edge in $G$. Therefore, $f(\mathcal{F})$ is a clique.
Also, no other node $v$ can be added to $f(\mathcal{F})$. Otherwise,
$f^{-1}(v)\cup\mathcal{F}$ is still an intersecting family while $f^{-1}(v)$
is not in $\mathcal{F}$, which makes $\mathcal{F}$ strictly larger — a
contradiction. Therefore, $\cup_{S\in\mathcal{F}}f(S)$ is a maximal clique.

∎

Lemma A.3 shows there is a bijective mapping between a maximal clique and a
maximal intersecting family of subsets. Given $\mathcal{H}$, $G$ and $X$,
Counting the former is equivalent to counting the latter. The result is
denoted as $\lambda(m)$ in the main text. Lemma 2.1 of (Brouwer et al., 2013)
gives an lower bound: $\lambda(m)\geq 2^{{m-1\choose[m/2]-1}}$.

###  A.4. Proof of Theorem 5.1

We start with some definitions. A random finite set, or RFS, is defined as a
random variable whose value is a finite set. Given a RFS $A$, we use
$\mathcal{S}(A)$ to denote $A$’s sample space; for a set $a\in\mathcal{S}(A)$
we use $P_{A}(a)$ to denote the probability that $A$ takes on value $a$. One
way to generate a RFS is by defining the set sampling operator $\odot$ on two
operands $r$ and $X$, where $r\in[0,1]$ and $X$ is a finite set: $r\odot X$ is
a RFS obtained by uniformly sampling elements from $X$ at sampling rate $r$,
i.e. each element $x\in X$ has probability $r$ to be kept. Also, notice that
the finite set $X$ itself can also be viewed as a RFS with only one possible
value to be taken. Now, we generalize two operations, union and difference, to
RFS as the following:

  * •

Union $A\cup B$:

$\displaystyle\vspace{-1mm}\mathcal{S}(A\cup B)$ $\displaystyle=\\{x|x=a\cup
b,a\in A,b\in B\\}$ $\displaystyle P_{A\cup B}(x)$
$\displaystyle=\sum_{x=a\cup b,a\in A,b\in B}P_{A}(a)P_{B}(b)$

  * •

Difference $A\backslash B$:

$\displaystyle\mathcal{S}(A\backslash B)$ $\displaystyle=\\{x|x=a\backslash
b,a\in A,b\in B\\}$ $\displaystyle P_{A\cup B}(x)$
$\displaystyle=\sum_{x=a\backslash b,a\in A,b\in
B}P_{A}(a)P_{B}(b)\vspace{-1mm}$

The Expectation of the Cardinality of a RFS is denoted by $\mathbb{E}^{c}$
such that $\mathbb{E}^{c}[A]=\mathbb{E}_{a\in\mathcal{S}(A)}|a|$. With these
ready, we have the following propositions that hold true for RFS $A$ and $B$:

  1. (i)

$\mathbb{E}^{c}[A\cup B]=\mathbb{E}^{c}[B\cup A]$

  2. (ii)

$\mathbb{E}^{c}[A\cup B]=\mathbb{E}^{c}[A\backslash B]+\mathbb{E}^{c}[B]$;

  3. (iii)

$\mathbb{E}^{c}[A\cup B]\geq\mathbb{E}^{c}[A]$, $\mathbb{E}^{c}[A\cup
B]\geq\mathbb{E}^{c}[B]$;

  4. (iv)

$\mathbb{E}^{c}[(r\odot X)\backslash Y]=r|X\backslash
Y|=\mathbb{E}^{c}[X\backslash Y]$; ($X$, $Y$ are both set)

###### Lemma A.4.

At iteration $(i+1)$ when Algo. 1 samples a cell $(n,k)$ (l-10), it reduces
the gap between $q^{*}$ and the expected number of hyperedges it already
collects, $q_{i}$, by a fraction of at least $\frac{r_{n,k}|Q_{n,k}|}{\beta}$:

$\frac{q^{*}-q_{i+1}}{q^{*}-q_{i}}\leq 1-\frac{r_{i+1}|Q_{i+1}|}{\beta}$

###### Proof.

$\displaystyle\;q^{*}-q_{i}$ (Thm. 5.1 setup) $\displaystyle=$
$\displaystyle\;\mathbb{E}^{c}[\cup_{j=1}^{z}r^{*}_{j}\odot\mathcal{E}_{j}]-\mathbb{E}^{c}[\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j}]$
(Prop.iii) $\displaystyle\leq$
$\displaystyle\;\mathbb{E}^{c}[(\cup_{j=1}^{z}r^{*}_{j}\odot\mathcal{E}_{j})\cup(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]-\mathbb{E}^{c}[\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j}]$
(Prop.ii) $\displaystyle=$
$\displaystyle\;\mathbb{E}^{c}[(\cup_{j=1}^{z}r^{*}_{j}\odot\mathcal{E}_{j})\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]$
(Prop.ii) $\displaystyle=$
$\displaystyle\sum_{t=1}^{z}\mathbb{E}^{c}[(r^{*}_{t}\odot\mathcal{E}_{t})\backslash((\cup_{j=1}^{t-1}r^{*}_{t}\odot\mathcal{E}_{t})\cup(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j}))]$
(Prop.iii) $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{z}\mathbb{E}^{c}[(r^{*}_{t}\odot\mathcal{E}_{t})\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]$
(Prop.iv) $\displaystyle=$
$\displaystyle\sum_{t=1}^{z}r^{*}_{t}\mathbb{E}^{c}[\mathcal{E}_{t}\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{z}r^{*}_{t}|\mathcal{Q}_{t}|\frac{\mathbb{E}^{c}[\mathcal{E}_{t}\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]}{|\mathcal{Q}_{t}|}$
(Alg. 1, Line 9) $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{z}r^{*}_{t}|\mathcal{Q}_{t}|\frac{\mathbb{E}^{c}[\mathcal{E}_{i+1}\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]}{|\mathcal{Q}_{i+1}|}$
(Def. of $\beta$) $\displaystyle=$
$\displaystyle\;\beta\cdot\frac{r_{i+1}\mathbb{E}^{c}[\mathcal{E}_{i+1}\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]}{r_{i+1}|\mathcal{Q}_{i+1}|}$
(Prop.iv) $\displaystyle=$
$\displaystyle\;\frac{\beta}{r_{i+1}|Q_{i+1}|}\mathbb{E}^{c}[(r_{i+1}\odot\mathcal{E}_{i+1})\backslash(\cup_{j=1}^{i}r_{j}\odot\mathcal{E}_{j})]$
(Thm. 5.1 setup) $\displaystyle=$
$\displaystyle\;\frac{\beta}{r_{i+1}|Q_{i+1}|}(q_{i+1}-q_{i})$

Therefore, $\frac{q^{*}-q_{i+1}}{q^{*}-q_{i}}\leq
1-\frac{r_{i+1}|Q_{i+1}|}{\beta}$ ∎

Now, according to our budget constraint we have

$\displaystyle\sum_{n,k}(1-\frac{r_{n,k}|Q_{n,k}|}{\beta})=z-1$

$z$ is the total number of $(n,k)$ pairs where $r_{n,k}>0$, which is a
constant. Finally, we have

$\frac{q^{*}-q}{q^{*}}=\prod_{i=0}^{z-1}\frac{q^{*}-q_{i+1}}{q^{*}-q_{i}}\leq\prod_{n,k}(1-\frac{r_{n,k}|Q_{n,k}|}{\beta})\leq(1-\frac{1}{z})^{z}<\frac{1}{e}$

Therefore $q>(1-\frac{1}{e})q*$.

###  A.5. Comparing Our Clique Sampler and Standard Submodular Optimization

A.4 suggests two distinctions between our clique sampler and the standard
greedy algorithm for submodular optimization.

  * •

The standard greedy algorithm runs deterministically on a set function whose
form is already known. In comparison, our clique sampler runs on a function
defined over Random Finite Sets (RFS) whose form can only be statistically
estimated from the data.

  * •

The standard submodular optimization problem forbids picking a set
fractionally. Our problem allows fractional sampling from an RFS (i.e.
$r_{n,k}\in[0,1]$).

As a result, we saw in A.4 it is much harder to prove the optimality of our
clique sampler than to prove for the greedy algorithm for Standard Submodular
Optimization.

##  Appendix B Count features

We define a target clique $C=\\{v_{1},v_{2},...,v_{|C|}\\}$. The 8 features
are:

  1. (1)

size of the clique: $|C|$;

  2. (2)

avg. node degree: $\frac{1}{|C|}\sum_{v\in C}d(v)$;

  3. (3)

avg. node degree (recursive): $\frac{1}{|C|}\sum_{v\in
C}\frac{1}{|\mathcal{N}(v)|}\sum_{v^{\prime}\in\mathcal{N}(v)}d(v^{\prime})$;

  4. (4)

avg. node degree w.r.t. max cliques: $\frac{1}{|C|}\sum_{v\in
C}|\\{M\in\mathcal{M}|v\in M\\}|$;

  5. (5)

avg. edge degree w.r.t. max cliques:$\frac{1}{|C|}\sum_{v_{1},v_{2}\in
C}|\\{M\in\small{{\mathcal{M}}}|v_{1},v_{2}\in M\\}|$;

  6. (6)

binarized “edge degree” (w.r.t. max cliques):$\prod_{v_{1},v_{2}\in
C}\mathbbm{1}_{[e]}$, where $e=\sum_{v_{1},v_{2}\in
C}|\\{M\in\small{{\mathcal{M}}}|v_{1},v_{2}\in M\\}|>1$;

  7. (7)

avg. clustering coefficient: $\frac{1}{|C|}\sum_{v\in C}cc(v)$, where $cc$ is
the clustering coefficient of node $v$ in the projection;

  8. (8)

avg. size of encompassing maximal cliques:
$\frac{1}{|\mathcal{M}^{C}|}\sum_{M\in\mathcal{M}^{C}}|M|$, where
$\mathcal{M}^{C}=\\{M\in\mathcal{M}|C\subseteq M\\}$;

Notice that avg. clustering coefficient is essentially a normalized count of
the edges between direct neighbors.

Feature Rankings. We study the relative importance of the 8 features by an
ablation study. For each dataset, we ablate the 8 features one at a time,
record the performance drops, and use those values to rank the 8 features. We
repeat this for all datasets, obtaining the 8 features’ average rankings,
shown in Fig.12. More imporant features have smaller ranking numbers. The most
important feature is binarized edge degree. It is an indicator of “whether
each edge in the target clique has been covered by at least two maximal
cliques”.

Figure 12. Average rankings of the 8 count features. More imporant features
have smaller ranking numbers.

##  Appendix C Experiments

###  C.1. Setup

Machine Specs. All experiments including model training are run on Intel Xeon
Gold 6254 CPU @ 3.15GHz with 1.6TB Memory.

Datasets. The first 4 datasets in Tab.2 are from (Benson et al., 2018); the
rest are from (Young et al., 2021). All source links and data are in our
supplementary materials.

Tuning $\beta$. We found the best $\beta$ by training our model on $90\%$
training data and evaluated on the rest $10\%$ training data. The best values
are reported in our code instructions.

Baseline Selection and Adaptation. For community detection, the criteria are:
1. community number must be automatically found; 2. the output is overlapping
communities. Based on them, we choose the most representative two. We tested
Demon and found it always work best with min community size $=1$ and
$\epsilon=1$. To adapt CFinder we search the best $k$ between $[0.1,0.5]$
quantile of hyperedge sizes on $\mathcal{H}_{0}$. For hyperedge prediction, we
ask that they cannot rely on hypergraphs for prediction, and can only use the
projection. Based on that we use the two recent SOTAs, (Zhang et al., 2018,
2019). We use their default hyperparameters for training. For Bayesian-MDL we
use its official library in graph-tools with default hyperparameters. We
implemented the best heuristic in (Conte et al., 2016) for clique covering.

###  C.2. Task Extension: Using Edge Multiplicities

Throughout this work, we do not assume that the projected graph has edge
multiplicities. Relying on edge multiplicities addresses a simpler version of
the problem which might limit its applicability. That said, some applications
may come with edge multiplicity information, and it is important to understand
what is possible in this more tractable case. Here we provide an effective
unsupervised method as a foundation for further work.

From Sec. 2, the multiplicity of an edge $(u,v)$ is the number of hyperedges
containing both $u$ and $v$. It is not hard to show that knowledge of the edge
multiplicities does not suffice to allow perfect reconstruction, and so we
still must choose from among a set of available cliques to form hyperedges. In
doing this with multiplicity information, we need to ensure that the cliques
we select add up to the given edges multiplicities. We do this by repeatedly
finding maximal cliques, removing them, and reducing the multiplicities of
their edges by 1. We find that an effective heuristic is to select maximal
cliques that have large size and small average edge multiplicities (combining
these for example using a weighted sum).

Table 5 gives the performance on the datasets we study. We can see that with
edge multiplicities our unsupervised baseline outperforms all the methods not
using edge multiplicities on most datasets, showing the power of this
additional information. The performance, however, is still far from perfect,
and we leave the study of this interesting extension to future work.

DBLP | Enron | P.School | H.School
---|---|---|---
82.75 (+1.56) | 19.79 (+3.77) | 10.46 (-32.60) | 19.30 (-35.56)
Foursquare | Hosts-Virus | Directors | Crimes
83.91 (+10.35) | 67.86 (+19.01) | 100.0 (+0.00) | 80.47 (+1.20)
Table 5. Performance of the proposed baseline using available edge
multiplicities. In parenthesis reported the increment against the best-
performed method not using edge multiplicities (cr. Table 3).

###  C.3. Storage Comparison

As mentioned in Introduction, a side bonus of having a reconstructed
hypergraph versus a projected graph is that the former typically requires much
less storage space. As a mini-study, we compare the storage of each
hypergraph, its projected graph, and its reconstruction generated by SHyRe-
count. We use the unified data structure of a nested array to represent the
list of edges/hyperedges. Each node is indexed by an int64. Fig.13 visualizes
the results. We see that the reconstructions take 1 to 2 orders of magnitude
less storage space than the projected graphs and are closest to the originals.

Figure 13. Comparing the storage of original hypergraphs, projected graphs and
reconstructed hypergraphs. Each hypergraph/graph is stored as a nested array
with int64 node indexes. Over the 8 datasets on average, a reconstructed
hypergraph takes only $4.6\%$ the storage of a projected graph.

###  C.4. More Results

Figure 14. Pairwise distance between $\rho(n,k)$ distribution of all datasets using mean squared difference of all cell values (after alignment). The distance matrix obtained is shown above. The diagonal cell is the darkest among its row (or column). Figure 15. CPU time comparison. Notice that Bayesian-MDL’s is written in C++, CMM in Matlab, and all other methods in Python. DBLP | Enron | P.School | H.School
---|---|---|---
$1.0E6$, $(\footnotesize{\gg}6.0E10$) |  $1.0E3$, $6.9E4$ |  $3.5E5$, $2.6E6$ |  $6.0E4$, $8.4E5$
Foursquare | Hosts-Virus | Directors | Crimes
$2.0E4$, $(\gg 1.1E12$) |  $6.0E3$, ($\gg 2.2E12$) |  $800$, $4.5E5$ |  $1.0E3$, $2.9E5$
Table 6. Optimal clique sampling number $\beta$ and total number of cliques $|\mathcal{U}|$. “$\gg$” appears if the dataset contains too many cliques to be enumerated by our machine in 24 hours, in which case a conservative lower bound is estimated instead. | DBLP | Hosts-Virus | Enron
---|---|---|---
original (SHyRe-motif) |  81.19$\pm$0.02 |  45.16$\pm$0.55 |  16.02$\pm$0.35
ablation: “random” |  0.17$\pm$0.00 |  0.00$\pm$0.00 |  0.54$\pm$0.49
ablation: “small” |  1.12$\pm$0.52 |  1.38$\pm$0.70 |  8.57$\pm$0.89
ablation: “head & tail” |  27.42$\pm$0.54 |  29.92$\pm$0.54 |  11.99$\pm$0.10
Table 7. Ablation study: comparing the performance obtained by replacing the
clique sampler with simpler heuristics for sampling.