##

Simon Zhang<EMAIL_ADDRESS>
Department of Computer Science
Purdue University Cheng Xin<EMAIL_ADDRESS>
Department of Computer Science
Purdue University Tamal K. Dey<EMAIL_ADDRESS>
Department of Computer Science
Purdue University

## Expressive Higher-Order Link Prediction through Hypergraph Symmetry
Breaking

Simon Zhang<EMAIL_ADDRESS>
Department of Computer Science
Purdue University Cheng Xin<EMAIL_ADDRESS>
Department of Computer Science
Purdue University Tamal K. Dey<EMAIL_ADDRESS>
Department of Computer Science
Purdue University

###### Abstract

A hypergraph consists of a set of nodes along with a collection of subsets of
the nodes called hyperedges. Higher order link prediction is the task of
predicting the existence of a missing hyperedge in a hypergraph. A hyperedge
representation learned for higher order link prediction is fully expressive
when it does not lose distinguishing power up to an isomorphism. Many existing
hypergraph representation learners, are bounded in expressive power by the
Generalized Weisfeiler Lehman-1 (GWL-1) algorithm, a generalization of the
Weisfeiler Lehman-1 algorithm. However, GWL-1 has limited expressive power. In
fact, induced subhypergraphs with identical GWL-1 valued nodes are
indistinguishable. Furthermore, message passing on hypergraphs can already be
computationally expensive, especially on GPU memory. To address these
limitations, we devise a preprocessing algorithm that can identify certain
regular subhypergraphs exhibiting symmetry. Our preprocessing algorithm runs
once with complexity the size of the input hypergraph. During training, we
randomly replace subhypergraphs identifed by the algorithm with covering
hyperedges to break symmetry. We show that our method improves the
expressivity of GWL-1. Our extensive experiments
111https://anonymous.4open.science/r/HypergraphSymmetryBreaking-B07F/ also
demonstrate the effectiveness of our approach for higher-order link prediction
on both graph and hypergraph datasets with negligible change in computation.

Figure 1: An illustration of a hypergraph of recipes. The nodes are the
ingredients and the hyperedges are the recipes. The task of higher order link
prediction is to predict hyperedges in the hypergraph. A negative hyperedge
sample would be the dotted hyperedge. The Asian ingredient nodes ($\alpha$)
and the European ingredient nodes ($\beta$) form two separate isomorphism
classes. However, GWL-1 cannot distinguish between these classes and will
predict a false positive for the negative sample.

###  1 Introduction

In real world networks, it is common for a relation amongst nodes to be
defined beyond a pair of nodes. Hypergraphs are the most general examples of
this. These have applications in recommender systems Lü et al. (2012), visual
classification Feng et al. (2019), and social networks Li et al. (2013). Given
an unattributed hypergraph, our goal is to perform higher order link
prediction with deep learning methods while also respecting symmetries of the
hypergraph.

Current approaches towards higher order link prediction are based on the
Generalized Weisfeiler Lehman 1 (GWL-1) algorithm Huang & Yang (2021), a
hypergraph isomorphism testing approximation algorithm that generalizes
Weisfeiler Lehman 1 (WL-1) Weisfeiler & Leman (1968)to hypergraphs. These
methods, called hyperGNNs, are parameterized versions of GWL-1.

To improve the expressivity of hypergraph/graph isomorphism approximators like
GWL-1 or WL-1, it is common to augment the nodes with extra information You et
al. (2021); Sato et al. (2021). We devise a method that, instead, selectively
breaks the symmetry of the hypergraph topology itself coming from the
limitations of the hyperGNN architecture. Since message passing on hypergraphs
can be very computationally expensive, our method is designed as a
preprocessing algorithm that can improve the expressive power of GWL-1 for
higher order link prediction. Since the preprocessing only runs once with
complexity linear in the input, we do not add to any computational complexity
from training.

Similar to a substructure counting algorithm Bouritsas et al. (2022), we
identify certain symmetries in induced subhypergraphs. However, unlike in
existing work where node attributes are modified, we directly target and
modify the symmetries in the topology. During training, we randomly replace
the hyperedges of the identified symmetric regular induced subhypergraphs with
single hyperedges that cover the nodes of each subhypergraph. We show that our
method can increase the expressivity of existing hypergraph neural networks.

We summarize our contributions as follows:

  * •

We characterize the expressive power and limitations of GWL-1.

  * •

We devise an efficient hypergraph preprocessing algorithm to improve the
expressivity of GWL-1 for higher order link prediction

  * •

We perform extensive experiments on real world datasets to demonstrate the
effectiveness of our approach.

###  2 Background

We go over what a hypergraph is and how these structures are represented as
tensors. We then define what a hypergraph isomorphism is.

####  2.1 Isomorphisms on Higher Order Structures

A hypergraph is a generalization of a graph. Hypergraphs allow for all
possible subsets over a set of vertices, called hyperedges. We can thus
formally define a hypergraph as:

######  Definition 2.1.

An undirected hypergraph is a pair $\mathcal{H}=(\mathcal{V},\mathcal{E})$
consisting of a set of vertices $\mathcal{V}$ and a set of hyperedges
$\mathcal{E}\subset 2^{\mathcal{V}}\setminus(\\{\emptyset\\}\cup\\{\\{v\\}\mid
v\in{\mathcal{V}}\\})$ where $2^{\mathcal{V}}$ is the power set of the vertex
set ${\mathcal{V}}$.

We will assume all hypergraphs are undirected as in Definition 2.1. For a
given hypergraph ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$, a hypergraph
${\mathcal{G}}=({\mathcal{V}}^{\prime},{\mathcal{E}}^{\prime})$ is a
subhypergraph of ${\mathcal{H}}$ if
${\mathcal{V}}^{\prime}\subseteq{\mathcal{V}}$ and
${\mathcal{E}}^{\prime}\subseteq{\mathcal{E}}$. For a
${\mathcal{W}}\subseteq{\mathcal{V}}$, an induced hypergraph is a
subhypergraph
$({\mathcal{W}},{\mathcal{F}}=2^{\mathcal{W}}\cap{\mathcal{E}})$.

For a given hypergraph ${\mathcal{H}}$, we also use
${\mathcal{V}}_{\mathcal{H}}$ and ${\mathcal{E}}_{\mathcal{H}}$ to denote the
sets of vertices and hyperedges of ${\mathcal{H}}$ respectively. According to
the definition, a hyperedge is a nonempty subset of the vertices. A hypergraph
with all hyperedges the same size $d$ is called a $d$-uniform hypergraph. A
$2$-uniform hypergraph is an undirected graph, or just graph.

When viewed combinatorially, a hypergraph can include some symmetries, which
are called isomorphisms. On a hypergraph, isomorphisms are defined by
bijective structure preserving maps. Such maps are a pair maps that respect
hyperedge structure.

######  Definition 2.2.

For two hypergraphs ${\mathcal{H}}$ and ${\mathcal{D}}$, a structure
preserving map $\rho:{\mathcal{H}}\to{\mathcal{D}}$ is a pair of maps
$\rho=(\rho_{\mathcal{V}}:{\mathcal{V}}_{\mathcal{H}}\to{\mathcal{V}}_{\mathcal{D}},\rho_{\mathcal{E}}:{\mathcal{E}}_{\mathcal{H}}\to{\mathcal{E}}_{\mathcal{D}})$
such that $\forall
e\in{\mathcal{E}}_{\mathcal{H}},\rho_{\mathcal{E}}(e)\triangleq\\{\rho_{\mathcal{V}}(v_{i})\mid
v_{i}\in e\\}\in{\mathcal{E}}_{\mathcal{D}}$. A hypergraph isomorphism is a
structure preserving map $\rho=(\rho_{\mathcal{V}},\rho_{\mathcal{E}})$ such
that both $\rho_{\mathcal{V}}$ and $\rho_{\mathcal{E}}$ are bijective. Two
hypergraphs are said to be isomorphic, denoted as
$\mathcal{H}\cong{\mathcal{D}}$, if there exists an isomorphism between them.
When $\mathcal{H}={\mathcal{D}}$, an isomorphism $\rho$ is called an
automorphism on ${\mathcal{H}}$. All the automorphisms form a group, which we
denote as $Aut(\mathcal{H})$.

A graph isomorphism is the special case of a hypergraph isomorphism between
$2$-uniform hypergraphs according to Definition 2.2.

A _neighborhood_ $N(v)\triangleq(\bigcup_{v\in e}e,\\{e:v\in e\\}$) of a node
$v\in{\mathcal{V}}$ of a hypergraph
${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$ is the subhypergraph of
${\mathcal{H}}$ induced by the set of all hyperedges incident to $v$. The
_degree_ of $v$ is denoted $deg(v)=|{\mathcal{E}}_{N(v)}|$. A simple but very
common symmetric hypergraph is of importance to our task, namely the
neighborhood-regular hypergraph, or just regular hypergraph. This is defined
here:

######  Definition 2.3.

A neighborhood-regular hypergraph is a hypergraph where all neighborhoods of
each node are isomorphic to each other.

A $d$-uniform neighborhood of $v$ is the set of all hyperedges of size $d$ in
the neighborhood of $v$. Thus, in a neighborhood-regular hypergraph, all nodes
have their $d$-uniform neighborhoods of the same degree for all
$d\in\mathbb{N}$.

$\textbf{Representing Higher Order Structures as Tensors}:$ There are many
data stuctures one can define on a higher order structure like a hypergraph.
An $n$-order tensor Maron et al. (2018), as a generalization of an adjacency
matrix on graphs can be used to characterize the high order connectivities.
For simplicial complexes, which are hypergraphs where all subsets of a
hyperedge are also hyperedges, a Hasse diagram, which is a multipartite graph
induced by the poset relation of subset amongst hyperedges, or simplices,
differing in exactly one node, is a common data structure Birkhoff (1940).
Similarly, the star expansion matrix Agarwal et al. (2006) can be used to
characterize hypergraphs up to isomorphism.

In order to define the star expansion matrix, we define the star expansion
bipartite graph.

######  Definition 2.4 (star expansion bipartite graph).

Given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, the _star
expansion bipartite graph_ $\mathcal{B}_{\mathcal{V},\mathcal{E}}$ is the
bipartite graph with vertices ${\mathcal{V}}\bigsqcup{\mathcal{E}}$ and edges
$\\{(v,e)\in{\mathcal{V}}\times{\mathcal{E}}\mid v\in e\\}$.

######  Definition 2.5.

The star expansion incidence matrix $H$ of a hypergraph
$\mathcal{H}=(\mathcal{V},\mathcal{E})$ is the $|{\mathcal{V}}|\times
2^{|{\mathcal{V}}|}$ $0$-$1$ incidence matrix $H$ where $H_{v,e}=1$ iff $v\in
e$ for $(v,e)\in{\mathcal{V}}\times{\mathcal{E}}$ for some fixed orderings on
both ${\mathcal{V}}$ and $2^{{\mathcal{V}}}$.

In practice, as data to machine learning algorithms, the matrix $H$ is
sparsely represented by its nonzeros.

To study the symmetries of a given hypergraph
${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$, we consider the permutation
group on the vertices ${\mathcal{V}}$, denoted as $Sym({\mathcal{V}})$, which
acts jointly on the rows and columns of star expansion adjacency matrices. We
assume the rows and columns of a star expansion adjacency matrix have some
canonical ordering given by some prefixed ordering of the vertices, say
lexicographic ordering. Therefore, each hypergraph ${\mathcal{H}}$ has a
unique canonical matrix representation $H$.

We define the action of a permutation $\pi\in Sym({\mathcal{V}})$ on a star
expansion adjacency matrix $H$:

$\displaystyle\begin{split}(\pi\cdot{H})_{v,e=(u_{1}...v...u_{k})}\triangleq{H}_{\pi^{-1}(v),\pi^{-1}(e)=(\pi^{-1}(u_{1})...\pi^{-1}(v)...\pi^{-1}(u_{k}))}\end{split}$
(1)

Based on the group action, consider the stabilizer subgroup of
$Sym({\mathcal{V}})$ on an adjacency matrix $H$:

$Stab_{Sym({\mathcal{V}})}(H)=\\{\pi\in Sym({\mathcal{V}})\mid\pi\cdot H=H\\}$
(2)

For simplicity we omit the lower index of $Sym(\mathcal{V})$ when the
permutation group is clear from context. It can be checked that
$Stab(H)\subseteq Sym({\mathcal{V}})$ is a subgroup. Intuitively, $Stab(H)$
consists of all permutations that fix $H$. These are equivalent to
automorphisms on the original hypergraph $\mathcal{H}$.

######  Proposition 2.1.

$Aut({\mathcal{H}})\cong Stab(H)$ are equivalent as isomorphic groups.

Intuitively, hypergraph automorphisms and stablizer permutations on star
expansion adjacancy matrices are equivalent. We will use these two terms
interchangeably. We can also define a notion of isomorphism between $k$-node
sets using the stabilizers on $H$.

######  Definition 2.6.

For a given hypergraph ${\mathcal{H}}$ with star expansion matrix $H$, two
$k$-node sets $S,T\subseteq\mathcal{V}$ are called _isomorphic_ , denoted as
$S\simeq T$, if $\exists\pi\in Stab(H),\pi(S)=T$ and $\pi(T)=S$.

Such isomorphism is an equivalance relation on $k$-node sets. When $k=1$, we
have isomorphic nodes, denoted $u\cong_{{\mathcal{H}}}v$ for
$u,v\in{\mathcal{V}}$. Node isomorphism is also studied as the so-called
structural equivalence in Lorrain & White (1971). Furthermore, when $S\simeq
T$ we can then say that there is a matching amongst the nodes in sets $S$ and
$T$ so that matched nodes are isomorphic.

####  2.2 Invariance and Expressivity

For a given hypergraph $\mathcal{H}=({\mathcal{V}},{\mathcal{E}})$, we want to
do hyperedge prediction on ${\mathcal{H}}$, which is to predict missing
hyperedges from $k$-node sets for $k\geq 2$. Let $|{\mathcal{V}}|=n$,
$|{\mathcal{E}}|=m$, and $H\in\mathbb{Z}_{2}^{n\times 2^{n}}$ be the star
expansion adjacency matrix of ${\mathcal{H}}$. To do hyperedge prediction, we
study $k$-node representations
$h:[\mathcal{V}]^{k}\times\mathbb{Z}_{2}^{n\times
2^{n}}\rightarrow\mathbb{R}^{d}$ that map $k$-node sets of hypergraphs to
$d$-dimensional Euclidean space. Ideally, we want a most-expressive $k$-node
representation for hyperedge prediction, which is intuitively a $k$-node
representation that is injective on $k$-node set isomorphism classes from
$\mathcal{H}$. We break up the definition of most-expressive $k$-node
representation into possessing two properties, as follows:

######  Definition 2.7.

Let $h:[\mathcal{V}]^{k}\times\mathbb{Z}_{2}^{n\times
2^{n}}\rightarrow\mathbb{R}^{d}$ be a $k$-node representation on a hypergraph
$\mathcal{H}$. Let $H\in\mathbb{Z}_{2}^{n\times 2^{n}}$ be the star expansion
adjacency matrix of $\mathcal{H}$ for $n$ nodes. The representation $h$ is
$k$-node most expressive if $\forall S,S^{\prime}\subset\mathcal{V}$,
$|S|=|S^{\prime}|=k$, the following two conditions are satisfied:

  1. 1.

$h$ is k-node invariant: $\exists\pi\in Stab(H),\pi(S)=S^{\prime}\implies
h(S,H)=h(S^{\prime},H)$

  2. 2.

$h$ is k-node expressive $\nexists\pi\in Stab(H),\pi(S)=S^{\prime}\implies
h(S,H)\neq h(S^{\prime},H)$

The first condition of a most expressive $k$-node representation states that
the representation must be well defined on the $k$ nodes up to isomorphism.
The second condition requires the injectivity of our representation. These two
conditions mean that the representation does not lose any information when
doing prediction for missing hyperedges on $k$ nodes.

####  2.3 Generalized Weisfeiler-Lehman-1

We describe a generalized Weisfeiler-Lehman-1 (GWL-1) hypergraph isomorphism
test similar to Huang & Yang (2021); Feng et al. (2023). There have been many
variants upon this GWL-1 algorithm for hypergraphs, many generalizing existing
graph neural network methods which are bounded by WL-1 in expressivity. See
Section 3 for more. For an explanation of GNNs and WL-1, see Appendix.

Let $H$ be the star expansion matrix for a hypergraph $\mathcal{H}$. We define
the GWL-1 algorithm as the following two step procedure on $(X,H)$ at
iteration number $i\geq 0$ where $X$ is the node attributes indexed by the
nodes:

$\displaystyle\begin{split}f_{e}^{0}\leftarrow\\{\\},h_{v}^{0}\leftarrow
X_{v}\\\ f_{e}^{i+1}\leftarrow\\{\\{(f_{e}^{i},h_{v}^{i})\\}\\}_{v\in
e},\forall e\in\mathcal{E}_{{\mathcal{H}}}(H)\\\
h_{v}^{i+1}\leftarrow\\{\\{(h_{v}^{i},f_{e}^{i+1})\\}\\}_{v\in e},\forall
v\in\mathcal{V}_{{\mathcal{H}}}(H)\end{split}$ (3)

This is slightly different from the algorithm presented in Huang & Yang (2021)
at the $f_{e}^{i+1}$ update step. Our update step involves an edge
representation $f_{e}^{i}$, which is not present in their version. Thus our
version of GWL-1 is more expressive than that in Huang & Yang (2021). However,
they both possess some of the same issues that we identify. We denote
$f_{e}^{i}(H)$ and $h_{v}^{i}(H)$ as the hyperedge and node ith iteration
GWL-1, called $i$-GWL-1, values on an unattributed hypergraph ${\mathcal{H}}$
with star expansion $H$. If GWL-1 is run to convergence then we omit the
iteration number $i$. We also mean this when we say $i=\infty$.

For a hypergraph $\mathcal{H}$ with star expansion matrix $H$, GWL-1 is
strictly more expressive than WL-1 on $A=H\cdot D_{e}^{-1}\cdot H^{T}$ with
$D_{e}=diag(H^{T}\cdot\mathbf{1}_{n})$, the node to node adjacency matrix,
also called the clique expansion of $\mathcal{H}$. This follows since a
triangle with its $3$-cycle boundary: $T$ and a 3-cycle $C_{3}$ have exactly
the same clique expansions. Thus WL-1 will give the same node values for both
$T$ and $C_{3}$. GWL-1 on the star expansions $H_{T}$ and $H_{C_{3}}$, on the
other hand, will identify the triangle as different from its bounding edges.

Let $f^{i}(H)\triangleq[f^{i}_{e_{1}}(H),\cdots f^{i}_{e_{m}}(H)]\text{ and
}h^{i}(H)\triangleq[h^{i}_{v_{1}}(H),\cdots h^{i}_{v_{n}}(H)]$.

######  Proposition 2.2.

The update steps $f^{i}(H)$ and $h^{i}(H)$ of GWL-1 are permutation
equivariant; For any $\pi\in Sym({\mathcal{V}})$, let: $\pi\cdot
f^{i}(H)\triangleq[f^{i}_{\pi^{-1}(e_{1})}(H),\cdots,f^{i}_{\pi^{-1}(e_{m})}(H)]$
and $\pi\cdot h^{i}(H)\triangleq[h^{i}_{\pi^{-1}(v_{1})}(H),\cdots
h^{i}_{\pi^{-1}(v_{n})}(H)]$, we have:

$\forall i\in\mathbb{N},\pi\cdot f^{i}(H)=f^{i}(\pi\cdot H)\text{, }\pi\cdot
h^{i}(H)=h^{i}(\pi\cdot H)$ (4)

Define the operator $AGG$ as a permutation invariant map on a set of vectors
to representation space $\mathbb{R}^{d}$. Define the following representation
of a subset of the nodes of a hypergraph ${\mathcal{H}}$ with star expansion
matrix $H$:

$h(S,H)=AGG_{v\in S}[h_{v}^{i}(H)]$ (5)

where $h_{v}^{i}(H)$ is the node value of $i$-GWL-1 on $H$. The representation
$h(S,H)$ preserves hyperedge isomorphism classes as shown below:

######  Proposition 2.3.

Let $h(S,H)=AGG_{v\in S}[h_{v}^{i}(H)]$ with injective AGG and $h_{v}^{i}$
permutation equivariant. The representation $h(S,H)$ is $k$-node invariant but
not necessarily $k$-node expressive for $S$ a set of $k$ nodes.

It follows that we can guarantee a $k$-node invariant representation by using
GWL-1. For deep learning, we parameterize $AGG$ as a universal set learner.
The vector $h^{i}(H)$ is also parameterized and rewritten into a message
passing hypergraph GNN with matrix equations such as in Huang & Yang (2021).

###  3 Related Work and Existing Issues

There are many hyperlink prediction methods. Most message passing based
methods for hypergraphs are based on the GWL-1 algorithm. These include Huang
& Yang (2021); Yadati et al. (2019); Feng et al. (2019); Gao et al. (2022);
Dong et al. (2020); Srinivasan et al. (2021); Chien et al. (2022); Zhang et
al. (2018). Examples of message passing based approaches that incorporate
positional encodings on hypergraphs include SNALS Wan et al. (2021). The paper
Zhang et al. (2019) uses a pair-wise node attention mechanism to do higher
order link prediction. For a survey on hyperlink prediction, see Chen & Liu
(2022).

There have been methods to improve the expressive power due to symmetries in
graphs. In Papp & Wattenhofer (2022), substructure labeling is formally
analyzed. One of the methods analyzed includes labeling fixed radius ego-
graphs as in You et al. (2021); Zhang & Li (2021). Other methods include
appending random node features Sato et al. (2021), labeling breadth-first and
depth-first search trees Li et al. (2023b) and encoding substructures Zeng et
al. (2023); Wijesinghe & Wang (2021). All of the previously mentioned methods
depend on a fixed subgraph radius size. This prevents capturing symmetries
that span long ranges across the graph. Zhang et al. (2023) proposes to add
metric information of each node relative to all other nodes to improve WL-1.
This would be very computationally expensive on hypergraphs.

Cycles are a common symmetric substructure. There are many methods that
identify this symmetry. Cy2C Choi et al.  is a method that encodes cycles to
cliques. It has the issue that if the the cycle-basis algorithm is not
permutation invariant, isomorphic graphs could get different cycle bases and
thus get encoded by Cy2C differently, violating the invariance of WL-1.
Similarly, the CW Network Bodnar et al. (2021) is a method that attaches cells
to cycles to improve upon the distinguishing power of WL-1 for graph
classification. However, inflating the input topology with cells as in Bodnar
et al. (2021) would not work for link predicting since it will shift the
hyperedge distribution to become much denser. Other works include cell
attention networks Giusti et al. (2022) and cycle basis based methods Zhang et
al. (2022). For more related work, see the Appendix.

###  4 A Characterization of GWL-1

A hypergraph can be represented by a bipartite graph
$\mathcal{B}_{\mathcal{V},\mathcal{E}}$ from $\mathcal{V}$ to $\mathcal{E}$
where there is an edge $(v,e)$ in the bipartite graph iff node $v$ is incident
to hyperedge $e$. This bipartite graph is called the star expansion bipartite
graph.

We introduce a more structured version of graph isomorphism called a $2$-color
isomorphism to characterize hypergraphs. It is a map on $2$-colored graphs,
which are graphs that can be colored with two colors so that no two nodes in
any graph with the same color are connected by an edge. We define a
$2$-colored isomorphism formally here:

######  Definition 4.1.

A $2$-colored isomorphism is a graph isomorphism on two $2$-colored graphs
that preserves node colors. It is denoted by $\cong_{c}$.

A bipartite graph always has a $2$-coloring. In this paper, we canonically fix
a $2$-coloring on all star expansion bipartite graphs by assigning red to all
the nodes in the node partition and and blue to all the nodes in the hyperedge
partition. See Figure 2(a) as an example. We let
${\mathcal{B}}_{{\mathcal{V}}},{\mathcal{B}}_{{\mathcal{E}}}$ be the red and
blue colored nodes in ${\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}$
respectively.

######  Proposition 4.1.

We have two hypergraphs
$(\mathcal{V}_{1},\mathcal{E}_{1})\cong(\mathcal{V}_{2},\mathcal{E}_{2})$ iff
$\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}\cong_{c}\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$
where $\mathcal{B}_{\mathcal{V}_{i},\mathcal{E}_{i}}$ is the star expansion
bipartite graph of $(\mathcal{V}_{i},\mathcal{E}_{i})$

We define a topological object for a graph originally from algebraic topology
called a universal cover:

######  Definition 4.2 (Hatcher (2005)).

The _universal covering_ of a connected graph $G$ is a (potentially infinite)
graph $\tilde{G}$ together with a map $p_{G}:\tilde{G}\to G$ such that:

  1. 1.

$\forall x\in{\mathcal{V}}(\tilde{G})$, $p_{G}|_{N(x)}$ is an isomorphism onto
$N(p_{G}(x))$.

  2. 2.

$\tilde{G}$ is simply connected (a tree)

We call such $p_{G}$ the _universal covering map_ and $\tilde{G}$ the
_universal cover_ of $G$. A covering graph is a graph that satisfies property
1 but not necessarily 2 in Definition 4.2. The universal covering $\tilde{G}$
is essentially unique Hatcher (2005) in the sense that it can cover all
connected covering graphs of $G$. Furthermore, define a rooted isomorphism
$G_{x}\cong H_{y}$ as an isomorphism between graphs $G$ and $H$ that maps $x$
to $y$ and vice versa. It is a known result that:

######  Theorem 4.2.

[Krebs & Verbitsky (2015)] Let $G$ and $H$ be two connected graphs. Let
$p_{G}:\tilde{G}\rightarrow G,p_{H}:\tilde{H}\rightarrow H$ be the universal
covering maps of $G$ and $H$ respectively. For any $i\in\mathbb{N}$, for any
two nodes $x\in G$ and $y\in H$:
$\tilde{G}_{\tilde{x}}^{i}\cong\tilde{G}_{\tilde{y}}^{i}$ iff the WL-1
algorithm assigns the same value to nodes $x=p_{G}(\tilde{x})$ and
$y=p_{H}(\tilde{y})$.

We generalize the second result stated above about a topological
characterization of WL-1 for GWL-1 for hypergraphs. In order to do this, we
need to generalize the definition of a universal covering to suite the
requirements of a bipartite star expansion graph. To do this, we lift
$\mathcal{B}_{\mathcal{V},\mathcal{E}}$ to a $2$-colored tree universal cover
$\tilde{\mathcal{B}}_{\mathcal{V},\mathcal{E}}$ where the red/blue nodes of
$\mathcal{B}_{\mathcal{V},\mathcal{E}}$ are lifted to red/blue nodes in
$\tilde{\mathcal{B}}_{\mathcal{V},\mathcal{E}}$. Furthermore, the labels
$\\{\\}$ are placed on the blue nodes corresponding to the hyperedges in the
lift and the labels $X_{v}$ are placed on all its corresponding red nodes in
the lift. Let
$(\tilde{\mathcal{B}}_{\mathcal{V},\mathcal{E}}^{k})_{\tilde{x}}$ denote the
$k$-hop rooted $2$-colored subtree with root $\tilde{x}$ and
$p_{{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}(\tilde{x})={x}$ for any
$x\in{\mathcal{V}}({\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}})$.

######  Theorem 4.3.

Let $\mathcal{H}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ and
$\mathcal{H}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})$ be two connected
hypergraphs. Let $\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}$ and
$\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$ be two canonically colored
bipartite graphs for $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ (vertices colored
red and hyperedges colored blue). Let
$p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}:\tilde{\mathcal{B}}_{\mathcal{V}_{1},\mathcal{E}_{1}}\rightarrow\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}},p_{\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}}:\tilde{\mathcal{B}}_{\mathcal{V}_{2},\mathcal{E}_{2}}\rightarrow\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$
be the universal coverings of $\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}$
and $\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$ respectively. For any
$i\in\mathbb{N}^{+}$, for any of the nodes
$x_{1}\in\mathcal{B}_{\mathcal{V}_{1}},e_{1}\in\mathcal{B}_{\mathcal{E}_{1}}$
and
$x_{2}\in\mathcal{B}_{\mathcal{V}_{2}},e_{2}\in\mathcal{B}_{\mathcal{E}_{2}}$:

$(\tilde{\mathcal{B}}^{2i-1}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{e}_{1}}\cong_{c}(\tilde{\mathcal{B}}^{2i-1}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{e}_{2}}$
iff $f^{i}_{e_{1}}=f^{i}_{e_{2}}$

$(\tilde{\mathcal{B}}^{2i}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{x}_{1}}\cong_{c}(\tilde{\mathcal{B}}^{2i}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{x}_{2}}$
iff $h^{i}_{x_{1}}=h^{i}_{x_{2}}$ , with $f^{i}_{\bullet},h^{i}_{\bullet}$ the
$i$th GWL-1 values for the hyperedges and nodes respectively where
$e_{1}=p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}(\tilde{e}_{1})$,
$x_{1}=p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}(\tilde{x}_{1})$,
$e_{2}=p_{\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}}(\tilde{e}_{2})$,
$x_{2}=p_{\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}}(\tilde{x}_{2})$.

See Figure 2 for an illustration of the universal covering of two $3$-uniform
neighborhood regular hypergraphs and their corresponding bipartite graphs.
Notice that by Theorems 4.3, 4.2 GWL-1 reduces to computing WL-1 on the
bipartite graph up to the $2$-colored isomorphism.

####  4.1 A Limitation of GWL-1

For two neighborhood-regular hypergraphs $C_{1}$ and $C_{2}$, the red/blue
colored universal covers $\tilde{B}_{C_{1}},\tilde{B}_{C_{2}}$ of the star
expansions of $C_{1}$ and $C_{2}$ are isomorphic, with the same GWL-1 values
on all nodes. However, two neighborhood-regular hypergraphs of different order
become distinguishable if a single hyperedge covering all the nodes of each
neighborhood-regular hypergraph is added. Furthermore, deleting the original
hyperedges, does not change the node isomorphism classes of each hypergraph.
Referring to Figure 2, consider the hypergraph $\mathcal{C}=C_{4}^{3}\sqcup
C_{5}^{3}$, the hypergraph with two $3$-regular hypergraphs $C_{4}^{3}$ and
$C_{5}^{3}$ acting as two connected components of $\mathcal{C}$. As shown in
Figure 2, the node representations of the two hypergraphs are identical due to
Theorem 4.3.

Given a hypergraph ${\mathcal{H}}$, we define a special induced subhypergraph
${\mathcal{R}}\subset{\mathcal{H}}$ whose node set GWL-1 cannot distinguish
from other such special induced subhypergraphs.

######  Definition 4.3.

A _$L$ -GWL-1 symmetric_ induced subhypergraph
${\mathcal{R}}\subset{\mathcal{H}}$ of ${\mathcal{H}}$ is a connected induced
subhypergraph determined by
${\mathcal{V}}_{{\mathcal{R}}}\subset{\mathcal{V}}_{{\mathcal{H}}}$, some
subset of nodes that are all indistinguishable amongst each other by
$L$-GWL-1:

$h_{u}^{L}(H)=h_{v}^{L}(H),\forall u,v\in{\mathcal{V}}_{\mathcal{R}}$ (6)

When $L=\infty$, we call such ${\mathcal{R}}$ a GWL-1 symmetric induced
subhypergraph. Furthermore, if ${\mathcal{R}}={\mathcal{H}}$, then we say
${\mathcal{H}}$ is _GWL-1 symmetric_.

This definition is similar to that of a symmetric graph from graph theory
Godsil & Royle (2001), except that isomorphic nodes are determined by the
GWL-1 approximator instead of an automorphism. The following observation
follows from the definitions.

######  Observation 1.

A hypergraph ${\mathcal{H}}$ is GWL-1 symmetric if and only if it is $L$-GWL-1
symmetric for all $L\geq 1$ if and only if ${\mathcal{H}}$ is neighborhood
regular.

Our goal is to find GWL-1 symmetric induced subhypergraphs in a given
hypergraph and break their symmetry without affecting any other nodes.

Figure 2:  An illustration of hypergraph symmetry breaking. (c,d) $3$-regular
hypergraphs $C_{4}^{3}$, $C_{5}^{3}$ with $4$ and $5$ nodes respectively and
their corresponding universal covers centered at any hyperedge
$(\tilde{\mathcal{B}}_{C^{3}_{4}})_{e_{*,*,*}},(\tilde{\mathcal{B}}_{C^{3}_{5}})_{e_{*,*,*}}$
with universal covering maps
$p_{\mathcal{B}_{C_{4}^{3}}},p_{\mathcal{B}_{C_{5}^{3}}}$. (b,e) the
hypergraphs $\hat{C}_{4}^{3},\hat{C}_{5}^{3}$, which are $C_{4}^{3},C_{5}^{3}$
with $4,5$-sized hyperedges attached to them and their corresponding universal
covers and universal covering maps. (a,f) are the corresponding bipartite
graphs of $\hat{C}_{4}^{3},\hat{C}_{5}^{3}$. (c,d) are indistinguishable by
GWL-1 and thus will give identical node values by Theorem 4.3. On the other
hand, (b,e) gives node values which are now sensitive to the the order of the
hypergraphs $4,5$, also by Theorem 4.3.

###  5 Method

Our goal is to predict higher order links in a hypergraph transductively. This
can be formulated as follows:

######  Problem 1.

Given input data ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$ and ground
truth hypergraph
${\mathcal{H}}_{gt}=({\mathcal{V}},{\mathcal{E}}_{gt}),{\mathcal{E}}\subset{\mathcal{E}}_{gt}$,
where ${\mathcal{E}}$ is observable: Predict
${\mathcal{E}}_{gt}\setminus{\mathcal{E}}$.

We will assume that the unobservable hyperedges are of the same size $k$ so
that we only need to predict on $k$-node sets. In order to preserve the most
information while still respecting topological structure, we aim to start with
an invariant multi-node representation to predict hyperedges and increase its
expressiveness, as defined in Definition 2.7. For input hypergraph
${\mathcal{H}}$ and its matrix representation $H$, to do the prediction of a
missing hyperedge on node subsets, we use a multi-node representation $h(S,H)$
for $S\subset{\mathcal{V}}(H)$ as in Equation 5 due to its simplicity,
guaranteed invariance, and improve its expressivity. We aim to not affect the
computational complexity since message passing on hypergraphs is already quite
expensive, especially on GPU memory.

Our method is a preprocessing algorithm that operates on the input hypergraph.
In order to increase expressivity, we search for potentially indistinguishable
regular induced subhypergraphs so that they can be replaced with hyperedges
that span the subhypergraph to break the symmetries that prevent GWL-1 from
being more expressive. We devise an algorithm, which is shown in Algorithm 1.
It takes as input a hypergraph $\mathcal{H}$ with star expansion matrix $H$.
The idea of the algorithm is to identify nodes of the same GWL-1 value that
are maximally connected and use this collection of node subsets to break the
symmetry of ${\mathcal{H}}$.

First we introduce some combinatorial definitions for hypergraph data that we
will use in our algorithm:

######  Definition 5.1.

A hypergraph ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$ is connected if
${\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}$ is a connected graph.

A connected component of ${\mathcal{H}}$ is a connected induced subhypergraph
which is not properly contained in any connected subhypergraph of
${\mathcal{H}}$.

######  Definition 5.2.

Chitra & Raphael (2019) A random walk on a hypergraph
${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$ is a Markov chain with state
space ${\mathcal{V}}$ with transition probabilities
$P_{u,v}\triangleq\sum_{e\supset\\{u,v\\}:e\in{\mathcal{E}}}\frac{\omega(e)}{deg(u)|e|}$,
where $\omega(e):{\mathcal{E}}\rightarrow[0,1]$ is some discrete probability
distribution on the hyperedges. When not specified, this is the uniform
distribution.

######  Definition 5.3.

A stationary distribution $\pi:{\mathcal{V}}\rightarrow[0,1]$ for a Markov
chain with transition probabilities $P_{u,v}$ is defined by the relationship
$\sum_{u\in{\mathcal{V}}}P_{u,v}\pi(u)=\pi(v)$.

For a hypergraph random walk we have the closed form:
$\pi(v)=\frac{deg(v)}{\sum_{u\in{\mathcal{V}}}deg(u)}$ for $v\in{\mathcal{V}}$
assuming ${\mathcal{H}}$ is a connected hypergraph.

The Algorithm:  Our method is explicitly given in Algorithm 1. For a given
$L\in\mathbb{N}^{+}$ and any $L$-GWL-1 node value $c_{L}$, we construct the
induced subhypergraph $\mathcal{H}_{c_{L}}$ from the $L$-GWL-1 class of nodes:

$\mathcal{V}_{c_{L}}\triangleq\\{v\in\mathcal{V}:c_{L}=h_{v}^{L}(H)\\},$ (7)

where $h_{v}^{L}$ denotes the $L$-GWL-1 class of node $v$. We then compute the
connected components of ${\mathcal{H}}_{c_{L}}$. Denote
${\mathcal{C}}_{c_{L}}$ as the set of all connected components of
${\mathcal{H}}_{c_{L}}$. If $L=\infty$, then drop $L$. Each of these connected
components is a subhypergraph of ${\mathcal{H}}$, denoted
$\mathcal{R}_{c_{L},i}$ where
$\mathcal{R}_{c_{L},i}\subset\mathcal{H}_{c_{L}}\subset\mathcal{H}$ for
$i=1...|{\mathcal{C}}_{c_{L}}|$.

Downstream Training:  After executing Algorithm 1, we collect its output
$({\mathcal{R}}_{V},{\mathcal{R}}_{E})$. During training, for each
$i=1...|{\mathcal{C}}_{c_{L}}|$ we randomly perturb $\mathcal{R}_{c_{L},i}$
by:

  * •

Attaching a single hyperedge that covers $\mathcal{V}_{\mathcal{R}_{c_{L},i}}$
with probability $q_{i}$ and not attaching with probability $1-q_{i}$.

  * •

All the hyperedges in $\mathcal{R}_{c_{L},i}$ are dropped or kept with
probability $p$ and $1-p$ respectively.

Let $\hat{{\mathcal{H}}}$ be the estimator of the input hypergraph
${\mathcal{H}}$ as determined by the random drop and attaching operations.
Since $\hat{{\mathcal{H}}}$ is random, each sample of $\hat{{\mathcal{H}}}$
has a stationary distribution $\hat{\pi}$. The expected stationary
distribution, denoted $\mathbb{E}[\hat{\pi}]$, is the expectation of
$\hat{\pi}$ over the distribution determined by $\hat{{\mathcal{H}}}$. We show
in Proposition 5.6 that the probabilities
$p,q_{i},i=1...|{\mathcal{C}}_{c_{L}}|$ can be chosen so that $\hat{\pi}$ is
unbiased.

Our method is similar to the concept of adding virtual nodes Hwang et al.
(2022) in graph representation learning. This is due to the equivalence
between virtual nodes and hyperedges by Proposition 4.1. For a guarantee of
improving expressivity, see Lemma 5.2 and Theorems 5.3, 5.4. For an
illustration of the data augmentation, see Figure 2.

Alternatively, downstream training using the output of Algorithm 1 can be
done. Similar to subgraph NNs, this is done by applying an ensemble of models
Alsentzer et al. (2020); Papp et al. (2021); Tan et al. (2023), with each
model trained on transformations of ${\mathcal{H}}$ with its symmetric
subhypergraphs randomly replaced. This, however, is computationally expensive.

Data: Hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, represented by its
star expansion matrix $H$. $L\in\mathbb{N}^{+}$ is the number of iterations to
run GWL-1.

Result: A pair of collections:
$(\mathcal{R}_{V}=\\{\mathcal{V}_{R_{j}}\\},\mathcal{R}_{E}=\cup_{j}\\{\mathcal{E}_{R_{j}}\\})$
where $R_{j}$ are disconnected subhypergraphs exhibiting symmetry in
$\mathcal{H}$ that are indistinguishable by $L$-GWL-1.

1

$U_{L}\leftarrow h_{v}^{L}(H);{\mathcal{G}}_{L}\leftarrow\\{U_{L}[v]:\forall
v\in\mathcal{V}\\}$ ;

/* $U_{L}[v]$ is the $L$-GWL-1 value of node $v\in{\mathcal{V}}$. */

2

${\mathcal{B}}_{{\mathcal{V}}_{{\mathcal{H}}},{\mathcal{E}}_{{\mathcal{H}}}}\leftarrow
Bipartite({\mathcal{H}})$ /* Construct the bipartite graph from
${\mathcal{H}}$. */

3

4$\mathcal{R}_{V}\leftarrow\\{\\}$; $\mathcal{R}_{E}\leftarrow\\{\\}$

5for  _$c_{L}\in{\mathcal{G}}_{L}$_ do

6
${\mathcal{V}}_{c_{L}}\leftarrow\\{v\in\mathcal{V}:U_{L}[v]=c_{L}\\},{\mathcal{E}}_{c_{L}}\leftarrow\\{e\in\mathcal{E}:u\in\mathcal{V}_{c_{L}},\forall
u\in e\\}$

7 $\mathcal{C}_{c_{L}}\leftarrow$
ConnectedComponents$({\mathcal{H}}_{c_{L}}=({\mathcal{V}}_{c_{L}},{\mathcal{E}}_{c_{L}}))$

8 for  _${\mathcal{R}}_{c_{L},i}\in{\mathcal{C}}_{c_{L}}$_ do

/* There should be at least $3$ nodes to form a nontrivial hyperedge */

9 if  _$|\mathcal{V}_{\mathcal{R}_{c_{L},i}}|\geq 3$_ then

10
$\mathcal{R}_{V}\leftarrow\mathcal{R}_{V}\cup\\{\mathcal{V}_{\mathcal{R}_{c_{L},i}}\\}$;
$\mathcal{R}_{E}\leftarrow\mathcal{R}_{E}\cup\mathcal{E}_{\mathcal{R}_{c_{L},i}}$

11 end if

12

13 end for

14

15 end for

return $(\mathcal{R}_{V},\mathcal{R}_{E})$

Algorithm 1 A Symmetry Finding Algorithm

Algorithm Guarantees: We show some guarantees for using the output of
Algorithm 1.

Notation:  Let $\mathcal{H}=(\mathcal{V},\mathcal{E})$ be a hypergraph with
star expansion matrix $H$ and let
$({\mathcal{R}}_{{\mathcal{V}}},{\mathcal{R}}_{{\mathcal{E}}})$ be the output
of Algorithm 1 on $H$ for $L\in\mathbb{N}^{+}$. Let
$\hat{{\mathcal{H}}}_{L}\triangleq({\mathcal{V}},{\mathcal{E}}\cup{\mathcal{R}}_{V})$
be ${\mathcal{H}}$ after adding all the hyperedges from
${\mathcal{R}}_{{\mathcal{V}}}$ and let $\hat{H}_{L}$ be the star expansion
matrix of the resulting hypergraph $\hat{{\mathcal{H}}}_{L}$. Let
$V_{c_{L},s}\triangleq\\{v\in{\mathcal{V}}_{c_{L}}:v\in
R,R\in{\mathcal{C}}_{c_{L}},|{\mathcal{V}}_{R}|=s\\}$ be the set of all nodes
of $L$-GWL-1 class $c_{L}$ belonging to a connected component in
${\mathcal{C}}_{c_{L}}$ of $s\geq 1$ nodes in ${\mathcal{H}}_{c_{L}}$, the
induced subhypergraph of $L$-GWL-1. Let
${\mathcal{G}}_{L}\triangleq\\{h_{v}^{L}(H):v\in{\mathcal{V}}\\}$ be the set
of all $L$-GWL-1 values on $H$. Let
${\mathcal{S}}_{c_{L}}\triangleq\\{|{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}|:{\mathcal{R}}_{c_{L},i}\in{\mathcal{C}}_{c_{L}}\\}$
be the set of node set sizes of the connected components in
${\mathcal{H}}_{c_{L}}$.

######  Proposition 5.1.

If $L=\infty$, for any GWL-1 node value $c$ computed on $\mathcal{H}$, all
connected component subhypergraphs $\mathcal{R}_{c,i}\in{\mathcal{C}}_{c}$ are
GWL-1 symmetric as hypergraphs.

######  Lemma 5.2.

If $L\in\mathbb{N}^{+}$ is small enough so that after running Algorithm 1 on
$L$, for any $L$-GWL-1 node class $c_{L}$ on ${\mathcal{V}}$ none of the
discovered $\mathcal{V}_{\mathcal{R}_{c_{L},i}}$ are within $L$ hyperedges
away from any $\mathcal{V}_{\mathcal{R}_{c_{L},j}}$ for all $i,j\in
1...|{\mathcal{C}}_{c_{L}}|,i\neq j$, then after forming
$\hat{{\mathcal{H}}}_{L}$, the new $L$-GWL-1 node classes of
$\mathcal{V}_{\mathcal{R}_{c_{L},i}}$for $i=1...{\mathcal{C}}_{c_{L}}$ in
$\mathcal{\hat{H}}_{L}$ are all the same class $c^{\prime}_{L}$ but are
distinguishable from $c_{L}$ depending on
$|\mathcal{V}_{\mathcal{R}_{c_{L},i}}|$.

We also have the following guarantee on the number of pairs of distinguishable
$k$-node sets on $\hat{{\mathcal{H}}}$:

######  Theorem 5.3.

Let $|{\mathcal{V}}|=n,L\in\mathbb{N}^{+}$. If
$vol(v)\triangleq\sum_{e\in{\mathcal{E}}:e\ni
v}|e|=O(\log^{\frac{1-\epsilon}{4L}}n),\forall v\in{\mathcal{V}}$ for any
constant $\epsilon>0$; $|{\mathcal{S}}_{c_{L}}|\leq S,\forall
c_{L}\in{\mathcal{C}}_{L}$, $S$ constant, and
$|V_{c_{L},s}^{L}|=O(\frac{n^{\epsilon}}{{\log^{\frac{1}{2k}}(n)}}),\forall
s\in{\mathcal{C}}_{c_{L}}$ , then for $k\in\mathbb{N}^{+}$ and $k$-tuple
$C=(c_{L,1}...c_{L,k}),c_{L,i}\in{\mathcal{G}}_{L},i=1..k$ there exists
$\omega(n^{2k\epsilon})$ many pairs of $k$-node sets $S_{1}\not\simeq S_{2}$
such that $(h^{L}_{u}(H))_{u\in S_{1}}=(h^{L}_{v\in S_{2}}(H))=C$, as ordered
$k$-tuples, while $h(S_{1},\hat{H}_{L})\neq h(S_{2},\hat{H}_{L})$ also by $L$
steps of GWL-1.

We show that our algorithm increases expressivity (Definition 2.7) for
$h(S,H)$ of Equation 5.

######  Theorem 5.4 (Invariance and Expressivity).

If $L=\infty$, GWL-1 enhanced by Algorithm 1 is still invariant to node
isomorphism classes of ${\mathcal{H}}$ and can be strictly more expressive
than GWL-1 to determine node isomorphism classes.

The complexity for our algorithm is in Proposition 5.5.

######  Proposition 5.5 (Complexity).

Algorithm 1 runs in time $O(nnz(H)L+(n+m))$, the size of the input star
expansion matrix $H$ for hypergraph
${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$, if $L$ is independent of
$nnz(H)$, where $n=|{\mathcal{V}}|$,
$nnz(H)=vol({\mathcal{V}})\triangleq\sum_{v\in{\mathcal{V}}}deg(v)$ and
$m=|{\mathcal{E}}|$.

Since Algorithm 1 runs in time linear in the size of the input when $L$ is
constant, in practice it only takes a small fraction of the training time for
hypergraph neural networks.

For the downstream training, we show that there are Bernoulli hyperedge
drop/attachment probabilities $p,q_{i}$ respectively for each
${\mathcal{R}}_{c_{L},i}$ so that the stationary distribution doesn’t change.
This shows that our data augmentation can still preserve the low frequency
random walk signal.

######  Proposition 5.6.

For a connected hypergraph ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$, let
$({\mathcal{R}}_{V},{\mathcal{R}}_{E})$ be the output of Algorithm 1 on
${\mathcal{H}}$. Then there are Bernoulli probabilities $p,q_{i}$ for
$i=1...|{\mathcal{R}}_{V}|$ for attaching a covering hyperedge so that
$\hat{\pi}$ is an unbiased estimator of $\pi$.

###  6 Evaluation

PR-AUC $\uparrow$ | Baseline | Ours | Baseln.+edrop
---|---|---|---
HGNN | $0.98\pm 0.03$ | $0.99\pm 0.08$ | $0.96\pm 0.02$
HGNNP | $0.98\pm 0.02$ | $0.98\pm 0.09$ | $0.96\pm 0.10$
HNHN | $0.98\pm 0.01$ | $0.96\pm 0.07$ | $0.97\pm 0.04$
HyperGCN | $0.98\pm 0.07$ | $0.98\pm 0.11$ | $0.98\pm 0.03$
UniGAT | $0.99\pm 0.06$ | $0.99\pm 0.03$ | $0.99\pm 0.07$
UniGCN | $0.99\pm 0.00$ | $0.99\pm 0.03$ | $0.99\pm 0.08$
UniGIN | $0.87\pm 0.02$ | $0.86\pm 0.10$ | $0.85\pm 0.08$
UniSAGE | $0.86\pm 0.04$ | $0.86\pm 0.05$ | $0.84\pm 0.09$

(a) cat-edge-DAWN

PR-AUC $\uparrow$ | Baseline | Ours | Baseln.+edrop
---|---|---|---
HGNN | $0.90\pm 0.13$ | $1.00\pm 0.00$ | $0.90\pm 0.13$
HGNNP | $0.90\pm 0.09$ | $1.00\pm 0.07$ | $1.00\pm 0.03$
HNHN | $0.90\pm 0.09$ | $0.91\pm 0.02$ | $0.90\pm 0.08$
HyperGCN | $1.00\pm 0.00$ | $1.00\pm 0.03$ | $1.00\pm 0.02$
UniGAT | $0.90\pm 0.06$ | $1.00\pm 0.03$ | $1.00\pm 0.06$
UniGCN | $1.00\pm 0.01$ | $0.91\pm 0.01$ | $0.82\pm 0.09$
UniGIN | $0.90\pm 0.12$ | $0.95\pm 0.06$ | $0.90\pm 0.11$
UniSAGE | $0.90\pm 0.16$ | $1.00\pm 0.08$ | $0.90\pm 0.17$

(b) cat-edge-music-blues-reviews

PR-AUC $\uparrow$ | Baseline | Ours | Baseln.+ edrop
---|---|---|---
HGNN | $0.96\pm 0.10$ | $0.98\pm 0.05$ | $0.96\pm 0.04$
HGNNP | $0.96\pm 0.05$ | $0.98\pm 0.09$ | $0.97\pm 0.07$
HNHN | $0.96\pm 0.02$ | $0.97\pm 0.08$ | $0.97\pm 0.06$
HyperGCN | $0.93\pm 0.05$ | $0.98\pm 0.07$ | $0.96\pm 0.09$
UniGAT | $0.96\pm 0.01$ | $0.98\pm 0.14$ | $0.97\pm 0.04$
UniGCN | $0.96\pm 0.04$ | $0.96\pm 0.11$ | $0.96\pm 0.09$
UniGIN | $0.97\pm 0.03$ | $0.97\pm 0.11$ | $0.96\pm 0.05$
UniSAGE | $0.96\pm 0.10$ | $0.96\pm 0.10$ | $0.96\pm 0.02$

(c) contact-high-school

PR-AUC $\uparrow$ | Baseline | Ours | Baseln.+edrop
---|---|---|---
HGNN | $0.95\pm 0.03$ | $0.96\pm 0.01$ | $0.95\pm 0.03$
HGNNP | $0.95\pm 0.02$ | $0.96\pm 0.09$ | $0.96\pm 0.07$
HNHN | $0.94\pm 0.07$ | $0.97\pm 0.10$ | $0.95\pm 0.05$
HyperGCN | $0.97\pm 0.01$ | $0.97\pm 0.05$ | $0.96\pm 0.08$
UniGAT | $0.95\pm 0.02$ | $0.98\pm 0.07$ | $0.98\pm 0.02$
UniGCN | $0.96\pm 0.00$ | $0.97\pm 0.14$ | $0.97\pm 0.10$
UniGIN | $0.95\pm 0.09$ | $0.97\pm 0.02$ | $0.95\pm 0.05$
UniSAGE | $0.96\pm 0.08$ | $0.95\pm 0.05$ | $0.96\pm 0.02$

(d) contact-primary-school

PR-AUC $\uparrow$ | Baseline | Ours | Baseln.+edrop
---|---|---|---
HGNN | $0.95\pm 0.07$ | $0.97\pm 0.08$ | $0.96\pm 0.07$
HGNNP | $0.95\pm 0.07$ | $0.96\pm 0.02$ | $0.96\pm 0.01$
HNHN | $0.94\pm 0.01$ | $0.97\pm 0.02$ | $0.95\pm 0.06$
HyperGCN | $0.92\pm 0.01$ | $0.94\pm 0.06$ | $0.94\pm 0.08$
UniGAT | $0.94\pm 0.08$ | $0.98\pm 0.14$ | $0.97\pm 0.08$
UniGCN | $0.97\pm 0.08$ | $0.97\pm 0.14$ | $0.97\pm 0.06$
UniGIN | $0.93\pm 0.07$ | $0.94\pm 0.11$ | $0.93\pm 0.09$
UniSAGE | $0.93\pm 0.07$ | $0.93\pm 0.08$ | $0.92\pm 0.04$

(e) email-Eu

PR-AUC $\uparrow$ | Baseline | Ours | Baseln.+edrop
---|---|---|---
HGNN | $0.75\pm 0.09$ | $0.85\pm 0.09$ | $0.71\pm 0.14$
HGNNP | $0.83\pm 0.09$ | $0.85\pm 0.08$ | $0.85\pm 0.04$
HNHN | $0.72\pm 0.09$ | $0.82\pm 0.03$ | $0.74\pm 0.09$
HyperGCN | $0.87\pm 0.08$ | $0.83\pm 0.05$ | $1.00\pm 0.07$
UniGAT | $0.80\pm 0.09$ | $0.83\pm 0.03$ | $0.78\pm 0.05$
UniGCN | $0.84\pm 0.08$ | $0.89\pm 0.10$ | $0.71\pm 0.07$
UniGIN | $0.69\pm 0.14$ | $0.76\pm 0.05$ | $0.61\pm 0.11$
UniSAGE | $0.72\pm 0.11$ | $0.71\pm 0.10$ | $0.64\pm 0.10$

(f) cat-edge-madison-restaurants

Table 1: Transductive hyperedge prediction PR-AUC scores on six different
hypergraph datasets. The highest scores per HyperGNN architecture (row) is
colored. Red text denotes the highest average scoring method. Orange text
denotes a two-way tie and brown text denotes a three-way tie. All datasets
involve predicting hyperedges of size $3$.

We evaluate our method on higher order link prediction with many of the
standard hypergraph neural network methods. Due to potential class imbalance,
we measure the PR-AUC of higher order link prediction on the hypergraph
datasets. These datasets are: cat-edge-DAWN, cat-edge-music-blues-reviews,
contact-high-school, contact-primary-school, email-Eu, cat-edge-madison-
restaurants. These datasets range from representing social interactions as
they develop over time to collections of reviews to drug combinations before
overdose. We also evaluate on the amherst41 dataset, which is a graph dataset.
All of our datasets are unattributed hypergraphs/graphs.

Data Splitting:  For the hypergraph datasets, each hyperedge in it is paired
with a timestamp (a real number). These timestamps are a physical time for
which a higher order interaction, represented by a hyperedge, occurs. We form
a train-val-test split by letting the train be the hyperedges associated with
the 80th percentile of timestamps, the validation be the hyperedges associated
with the timestamps in between the 80th and 85th percentiles. The test
hyperedges are the remaining hyperedges. The train validation and test
datasets thus form a partition of the nodes. We do the task of hyperedge
prediction for sets of nodes of size $3$, also known as triangle prediction.
Half of the size $3$ hyperedges in each of train, validation and test are used
as positive examples. For each split, we select random subsets of nodes of
size $3$ that do not form hyperedges for negative sampling. We maintain
positive/negative class balance by sampling the same number of negative
samples as positive samples. Since the test distribution comes from later time
stamps than those in training, there is a possibility that certain datasets
are out-of-distribution if the hyperedge distribution changes.

For the graph dataset, the single graph is deterministically split into
80/5/15 for train/val/test. We remove $10\%$ of the edges in training and let
them be positive examples $P_{tr}$ to predict. For validation and test, we
remove $50\%$ of the edges from both validation and test to set as the
positive examples $P_{val},P_{te}$ to predict. For train, validation, and
test, we sample $|P_{tr}|,|P_{val}|,|P_{te}|$ negative link samples from the
links of train, validation and test.

PR-AUC $\uparrow$ | HGNN | HGNNP | HNHN | HyperGCN | UniGAT | UniGCN | UniGIN | UniSAGE
---|---|---|---|---|---|---|---|---
Ours | $0.73\pm 0.10$ | $0.61\pm 0.05$ | $0.64\pm 0.06$ | $0.71\pm 0.09$ | $0.72\pm 0.08$ | $0.70\pm 0.08$ | $0.73\pm 0.03$ | $0.73\pm 0.06$
HyperGNN Baseline | $0.62\pm 0.09$ | $0.62\pm 0.10$ | $0.63\pm 0.04$ | $0.71\pm 0.07$ | $0.70\pm 0.06$ | $0.69\pm 0.07$ | $0.73\pm 0.06$ | $0.73\pm 0.09$
HyperGNN Baseln.+edrop | $0.61\pm 0.03$ | $0.61\pm 0.03$ | $0.61\pm 0.09$ | $0.71\pm 0.06$ | $0.71\pm 0.02$ | $0.69\pm 0.05$ | $0.73\pm 0.09$ | $0.73\pm 0.04$
APPNP | $0.42\pm 0.07$ | $0.42\pm 0.07$ | $0.42\pm 0.07$ | $0.42\pm 0.07$ | $0.42\pm 0.07$ | $0.42\pm 0.07$ | $0.42\pm 0.07$ | $0.42\pm 0.07$
APPNP+edrop | $0.42\pm 0.03$ | $0.42\pm 0.03$ | $0.42\pm 0.03$ | $0.42\pm 0.03$ | $0.42\pm 0.03$ | $0.42\pm 0.03$ | $0.42\pm 0.03$ | $0.42\pm 0.03$
GAT | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$
GAT+edrop | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$ | $0.49\pm 0.06$
GCN2 | $0.56\pm 0.12$ | $0.56\pm 0.12$ | $0.56\pm 0.12$ | $0.56\pm 0.12$ | $0.56\pm 0.12$ | $0.56\pm 0.12$ | $0.56\pm 0.12$ | $0.56\pm 0.12$
GCN2+edrop | $0.54\pm 0.02$ | $0.54\pm 0.02$ | $0.54\pm 0.02$ | $0.54\pm 0.02$ | $0.54\pm 0.02$ | $0.54\pm 0.02$ | $0.54\pm 0.02$ | $0.54\pm 0.02$
GCN | $0.40\pm 0.03$ | $0.40\pm 0.03$ | $0.40\pm 0.03$ | $0.40\pm 0.03$ | $0.40\pm 0.03$ | $0.40\pm 0.03$ | $0.40\pm 0.03$ | $0.40\pm 0.03$
GCN+edrop | $0.65\pm 0.04$ | $0.65\pm 0.04$ | $0.65\pm 0.04$ | $0.65\pm 0.04$ | $0.65\pm 0.04$ | $0.65\pm 0.04$ | $0.65\pm 0.04$ | $0.65\pm 0.04$
GIN | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$
GIN+edrop | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$ | $0.73\pm 0.10$
GraphSAGE | $0.44\pm 0.01$ | $0.44\pm 0.01$ | $0.44\pm 0.01$ | $0.44\pm 0.01$ | $0.44\pm 0.01$ | $0.44\pm 0.01$ | $0.44\pm 0.01$ | $0.44\pm 0.01$
GraphSAGE+edrop | $0.44\pm 0.10$ | $0.44\pm 0.10$ | $0.44\pm 0.10$ | $0.44\pm 0.10$ | $0.44\pm 0.10$ | $0.44\pm 0.10$ | $0.44\pm 0.10$ | $0.44\pm 0.10$

Table 2: PR-AUC on graph dataset amherst41. Each column is a comparison of the
baseline PR-AUC scores against the PR-AUC score for our method (first row)
applied to a standard HyperGNN architecture. Red color denotes the highest
average score in the column. Orange color denotes a two-way tie in the column,
and brown color denotes a three-or-more-way tie in the column.

####  6.1 Architecture and Training

Our algorithm serves as a preprocessing step for selective data augmentation.
Given a single training hypergraph ${\mathcal{H}}$, the Algorithm 1 is applied
and during training, the identified hyperedges of the symmetric induced
subhypergraphs of ${\mathcal{H}}$ are randomly replaced with single hyperedges
that cover all the nodes of each induced subhypergraph. Each symmetric
subhypergraph has a $p=0.5$ probability of being selected. To get a large set
of symmetric subhypergraphs, we run $2$ iterations of GWL-1.

We implement $h(S,H)$ from Equation 5 as follows. Upon extracting the node
representations from the hypergraph neural network, we use a multi-layer-
perceptron (MLP) on each node representation, sum across such compositions,
then apply a final MLP layer after the aggregation. We use the binary cross
entropy loss on this multi-node representation for training. We always use $5$
layers of hyperGNN convolutions, a hidden dimension of $1024$, and a learning
rate of $0.01$.

####  6.2 Higher Order Link Prediction Results

We show in Table 1 the comparison of PR-AUC scores amongst the baseline
methods of HGNN, HGNNP, HNHN, HyperGCN, UniGIN, UniGAT, UniSAGE, their
hyperedge dropped versions, and "Our" method, which preprocesses the
hypergraph to break symmetry during training. For the hyperedge drop
baselines, there is a uniform $50\%$ chance of dropping any hyperedge. We use
the Laplacian eigenmap Belkin & Niyogi (2003) positional encoding on the
clique expansion of the input hypergraph. This is common practice in
(hyper)link prediction and required for using a hypergraph neural network on
an unattributed hypergraph.

We show in Table 2 the PR-AUC scores on the amhrest41. Along with HyperGNN
architectures we use for the hypergraph experiments, we also compare with
standard GNN architectures: APPNP Gasteiger et al. (2018), GAT Veličković et
al. (2017), GCN2 Chen et al. (2020), GCN Kipf & Welling (2016a), GIN Xu et al.
(2018), and GraphSAGE Hamilton et al. (2017). For every HyperGNN/GNN
architecture, we also apply drop-edge Rong et al. (2019) to the input graph
and use this also as baseline. The number of layers of each GNN is set to $5$
and the hidden dimension at $1024$. For APPNP and GCN2, one MLP is used on the
initial node positional encodings.

Overall, our method performs well across a diverse range of higher order
network datasets. We observe that our method can often outperform the baseline
of not performing any data perturbations as well as the same baseline with
uniformly random hyperedge dropping. Our method has an added advantage of
being explainable since our algorithm works at the data level. There was also
not much of a concern for computational time since our algorithm runs in time
$O(nnz(H)+n+m)$, which is optimal since it is the size of the input.

####  6.3 Empirical Observations on the Components Discovered by the Algorithm

As we are primarily concerned with symmetries in a hypergraph, we empirically
measure the size and frequency of the components found by the Algorithm for
real-world datasets. For the real-world datasets listed in Appendix D, in
Figure 3(a), we plot the fraction of connected components of the same
$L$-GWL-1 value ($L=2$) that are large enough to be used by Algorithm 1 as a
function of the number of nodes of the hypergraph. We notice that the fraction
of connected components is not large, however every dataset has a nonzero
fraction. On the right, in Figure 3(b) we show the distribution of the sizes
of the connected components found by Algorithm 1. We see that, on average, the
connected components are at least an order of magnitude smaller compared to
the total number of nodes. Common to both plots, the graph datasets appear to
have more nodes and a consistent fraction and size of components, while the
hypergraph datasets have higher variance in the fraction of components, which
is expected since there are more possibilities for the connections in a
hypergraph.

(a) Fraction of components of size atleast $3$ selected by Algorithm 1.

(b) Average size of components of size atleast $3$ from Algorithm 1.

Figure 3:

In terms of the number of identified connected components, there are at least
exponentially many interventions that can be imposed on the hypergraph from
simply dropping components. Thus, even finding just $10$ components result in
at least $2^{10}\approx 10^{3}$ many counterfactual hypergraphs. It is known
that a large set of data augmentations during learning is beneficial to the
learner for generalization purposes.

###  7 Conclusion

We have characterized and identified the limitations of GWL-1, a hypergraph
isomorphism testing algorithm that underlies many existing HyperGNN
architectures. A common issue with distinguishing regular hypergraphs exists.
In fact more generally, maximally connected subsets of nodes that share the
same value of GWL-1, which act like regular hypergraphs, are
indistinguishable. To address this issue while respecting the structure of a
hypergraph, we have devised a preprocessing algorithm that improves the
expressivity of any GWL-1 based learner. The algorithm searches for
indistinguishable regular subhypergraphs and simplifies them by a single
hyperedge that covers the nodes of the subhypergraph. We perform extensive
experiments to evaluate the effectiveness of our approach and make empirical
observations about the output of the algorithm on hypergraph data.

### References

  * Agarwal et al. (2006) Sameer Agarwal, Kristin Branson, and Serge Belongie.  Higher order learning with graphs.  In _Proceedings of the 23rd international conference on Machine learning_ , pp. 17–24, 2006.
  * Alsentzer et al. (2020) Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik.  Subgraph neural networks.  _Advances in Neural Information Processing Systems_ , 33:8017–8029, 2020.
  * Amburg et al. (2020a) Ilya Amburg, Nate Veldt, and Austin R. Benson.  Clustering in graphs and hypergraphs with categorical edge labels.  In _Proceedings of the Web Conference_ , 2020a.
  * Amburg et al. (2020b) Ilya Amburg, Nate Veldt, and Austin R Benson.  Fair clustering for diverse and experienced groups.  _arXiv:2006.05645_ , 2020b.
  * Arya et al. (2020) Devanshu Arya, Deepak K Gupta, Stevan Rudinac, and Marcel Worring.  Hypersage: Generalizing inductive representation learning on hypergraphs.  _arXiv preprint arXiv:2010.04558_ , 2020.
  * Bai et al. (2021) Song Bai, Feihu Zhang, and Philip HS Torr.  Hypergraph convolution and hypergraph attention.  _Pattern Recognition_ , 110:107637, 2021.
  * Baldi & Sadowski (2014) Pierre Baldi and Peter Sadowski.  The dropout learning algorithm.  _Artificial intelligence_ , 210:78–122, 2014.
  * Belkin & Niyogi (2003) Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural computation_ , 15(6):1373–1396, 2003\.
  * Benson et al. (2018a) Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg.  Simplicial closure and higher-order link prediction.  _Proceedings of the National Academy of Sciences_ , 2018a.  ISSN 0027-8424.  doi: 10.1073/pnas.1800683115.
  * Benson et al. (2018b) Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg.  Simplicial closure and higher-order link prediction.  _Proceedings of the National Academy of Sciences_ , 115(48):E11221–E11230, 2018b.
  * Birkhoff (1940) Garrett Birkhoff.  _Lattice theory_ , volume 25.  American Mathematical Soc., 1940.
  * Bodnar et al. (2021) Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein.  Weisfeiler and lehman go cellular: Cw networks.  _Advances in Neural Information Processing Systems_ , 34:2625–2640, 2021.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.  URL https://proceedings.neurips.cc/paper_files/paper/2013/file/1cecc7a77928ca8133fa24680a88d2f9-Paper.pdf.
  * Bouritsas et al. (2022) Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(1):657–668, 2022.
  * Cai et al. (2022) Derun Cai, Moxian Song, Chenxi Sun, Baofeng Zhang, Shenda Hong, and Hongyan Li.  Hypergraph structure learning for hypergraph neural networks.  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_ , pp. 1923–1929, 2022.
  * Chen & Liu (2022) Can Chen and Yang-Yu Liu.  A survey on hyperlink prediction.  _arXiv preprint arXiv:2207.02911_ , 2022.
  * Chen et al. (2020) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.  Simple and deep graph convolutional networks.  In _International conference on machine learning_ , pp. 1725–1735. PMLR, 2020.
  * Chen et al. (2022) Samantha Chen, Sunhyuk Lim, Facundo Memoli, Zhengchao Wan, and Yusu Wang.  Weisfeiler-lehman meets gromov-Wasserstein.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 3371–3416. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/chen22o.html.
  * Chen et al. (2023) Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang.  The weisfeiler-lehman distance: Reinterpretation and connection with gnns.  _arXiv preprint arXiv:2302.00713_ , 2023.
  * Chien et al. (2021) Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic.  You are allset: A multiset function framework for hypergraph neural networks.  _arXiv preprint arXiv:2106.13264_ , 2021.
  * Chien et al. (2022) Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic.  You are allset: A multiset function framework for hypergraph neural networks.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=hpBTIv2uy_E.
  * Chitra & Raphael (2019) Uthsav Chitra and Benjamin Raphael.  Random walks on hypergraphs with edge-dependent vertex weights.  In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 1172–1181. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/chitra19a.html.
  * (23) Yun Young Choi, Sun Woo Park, Youngho Woo, and U Jin Choi.  Cycle to clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation.  In _The Eleventh International Conference on Learning Representations_.
  * Crossley et al. (2013) Nicolas A Crossley, Andrea Mechelli, Petra E Vértes, Toby T Winton-Brown, Ameera X Patel, Cedric E Ginestet, Philip McGuire, and Edward T Bullmore.  Cognitive relevance of the community structure of the human brain functional coactivation network.  _Proceedings of the National Academy of Sciences_ , 110(28):11583–11588, 2013.
  * Dong et al. (2020) Yihe Dong, Will Sawin, and Yoshua Bengio.  Hnhn: Hypergraph networks with hyperedge neurons.  _arXiv preprint arXiv:2006.12278_ , 2020.
  * Feng et al. (2019) Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao.  Hypergraph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pp. 3558–3565, 2019.
  * Feng et al. (2023) Yifan Feng, Jiashu Han, Shihui Ying, and Yue Gao.  Hypergraph isomorphism computation.  _arXiv preprint arXiv:2307.14394_ , 2023.
  * Gao et al. (2022) Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji.  Hgnn+: General hypergraph neural networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Gasteiger et al. (2018) Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  _arXiv preprint arXiv:1810.05997_ , 2018.
  * Giusti et al. (2022) Lorenzo Giusti, Claudio Battiloro, Lucia Testa, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa.  Cell attention networks.  _arXiv preprint arXiv:2209.08179_ , 2022.
  * Godsil & Royle (2001) Chris Godsil and Gordon F Royle.  _Algebraic graph theory_ , volume 207.  Springer Science & Business Media, 2001.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * Hatcher (2005) Allen Hatcher.  _Algebraic topology_.  Web, 2005.
  * Hu et al. (2022) Yang Hu, Xiyuan Wang, Zhouchen Lin, Pan Li, and Muhan Zhang.  Two-dimensional weisfeiler-lehman graph neural networks for link prediction.  _arXiv preprint arXiv:2206.09567_ , 2022.
  * Huang & Yang (2021) Jing Huang and Jie Yang.  Unignn: a unified framework for graph and hypergraph neural networks.  _arXiv preprint arXiv:2105.00956_ , 2021.
  * Hwang et al. (2022) EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma.  An analysis of virtual nodes in graph neural networks for link prediction.  In _The First Learning on Graphs Conference_ , 2022.
  * Kim et al. (2022) Jinwoo Kim, Saeyoon Oh, Sungjun Cho, and Seunghoon Hong.  Equivariant hypergraph neural networks.  In _European Conference on Computer Vision_ , pp. 86–103. Springer, 2022.
  * Kipf & Welling (2016a) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016a.
  * Kipf & Welling (2016b) Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016b.
  * Knill (2013) Oliver Knill.  A brouwer fixed-point theorem for graph endomorphisms.  _Fixed Point Theory and Applications_ , 2013(1):1–24, 2013.
  * Krebs & Verbitsky (2015) Andreas Krebs and Oleg Verbitsky.  Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth.  In _2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science_ , pp. 689–700. IEEE, 2015.
  * Lee & Shin (2022) Dongjin Lee and Kijung Shin.  I’m me, we’re us, and i’m us: Tri-directional contrastive learning on hypergraphs.  _arXiv preprint arXiv:2206.04739_ , 2022.
  * Leskovec et al. (2007) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  _ACM Transactions on Knowledge Discovery from Data_ , 1(1), 2007.  doi: 10.1145/1217299.1217301.  URL https://doi.org/10.1145/1217299.1217301.
  * Li et al. (2013) Dong Li, Zhiming Xu, Sheng Li, and Xin Sun.  Link prediction in social networks based on hypergraph.  In _Proceedings of the 22nd international conference on world wide web_ , pp. 41–42, 2013.
  * Li et al. (2023a) Mengran Li, Yong Zhang, Xiaoyong Li, Yuchen Zhang, and Baocai Yin.  Hypergraph transformer neural networks.  _ACM Transactions on Knowledge Discovery from Data_ , 17(5):1–22, 2023a.
  * Li et al. (2020) Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  _Advances in Neural Information Processing Systems_ , 33:4465–4478, 2020.
  * Li et al. (2023b) Shouheng Li, Dongwoo Kim, and Qing Wang.  Local vertex colouring graph neural networks.  2023b.
  * Lim et al. (2021) Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim.  Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.  _Advances in Neural Information Processing Systems_ , 34:20887–20902, 2021.
  * Lorrain & White (1971) Francois Lorrain and Harrison C White.  Structural equivalence of individuals in social networks.  _The Journal of mathematical sociology_ , 1(1):49–80, 1971.
  * Lü et al. (2012) Linyuan Lü, Matúš Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, and Tao Zhou.  Recommender systems.  _Physics reports_ , 519(1):1–49, 2012.
  * Maron et al. (2018) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  _arXiv preprint arXiv:1812.09902_ , 2018.
  * Mastrandrea et al. (2015) Rossana Mastrandrea, Julie Fournet, and Alain Barrat.  Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys.  _PLOS ONE_ , 10(9):e0136497, 2015.  doi: 10.1371/journal.pone.0136497.  URL https://doi.org/10.1371/journal.pone.0136497.
  * Papp & Wattenhofer (2022) Pál András Papp and Roger Wattenhofer.  A theoretical comparison of graph neural network extensions.  In _International Conference on Machine Learning_ , pp. 17323–17345. PMLR, 2022.
  * Papp et al. (2021) Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer.  Dropgnn: Random dropouts increase the expressiveness of graph neural networks.  _Advances in Neural Information Processing Systems_ , 34:21997–22009, 2021.
  * Ristoski & Paulheim (2016) Petar Ristoski and Heiko Paulheim.  Rdf2vec: Rdf graph embeddings for data mining.  In _The Semantic Web–ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17–21, 2016, Proceedings, Part I 15_ , pp. 498–514. Springer, 2016.
  * Rong et al. (2019) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  _arXiv preprint arXiv:1907.10903_ , 2019.
  * Ruggeri et al. (2023) Nicolò Ruggeri, Federico Battiston, and Caterina De Bacco.  A framework to generate hypergraphs with community structure.  _arXiv preprint arXiv:2212.08593_ , 22, 2023.
  * Sato et al. (2021) Ryoma Sato, Makoto Yamada, and Hisashi Kashima.  Random features strengthen graph neural networks.  In _Proceedings of the 2021 SIAM international conference on data mining (SDM)_ , pp. 333–341. SIAM, 2021.
  * Singh et al. (2012) Sameer Singh, Amarnag Subramanya, Fernando Pereira, and Andrew McCallum.  Wikilinks: A large-scale cross-document coreference corpus labeled via links to Wikipedia.  Technical Report UM-CS-2012-015, 2012.
  * Sinha et al. (2015) Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June (Paul) Hsu, and Kuansan Wang.  An overview of microsoft academic service (MAS) and applications.  In _Proceedings of the 24th International Conference on World Wide Web_. ACM Press, 2015.  doi: 10.1145/2740908.2742839.  URL https://doi.org/10.1145/2740908.2742839.
  * Srinivasan & Ribeiro (2019) Balasubramaniam Srinivasan and Bruno Ribeiro.  On the equivalence between positional node embeddings and structural graph representations.  _arXiv preprint arXiv:1910.00452_ , 2019.
  * Srinivasan et al. (2021) Balasubramaniam Srinivasan, Da Zheng, and George Karypis.  Learning over families of sets-hypergraph representation learning for higher order tasks.  In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_ , pp. 756–764. SIAM, 2021.
  * Stehlé et al. (2011) Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, et al.  High-resolution measurements of face-to-face contact patterns in a primary school.  _PloS one_ , 6(8):e23176, 2011.
  * Tan et al. (2023) Qiaoyu Tan, Xin Zhang, Ninghao Liu, Daochen Zha, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu.  Bring your own view: Graph neural networks for link prediction with personalized subgraph selection.  In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_ , pp. 625–633, 2023.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Wan et al. (2021) Changlin Wan, Muhan Zhang, Wei Hao, Sha Cao, Pan Li, and Chi Zhang.  Principled hyperedge prediction with structural spectral features and neural networks.  _arXiv preprint arXiv:2106.04292_ , 2021.
  * Wang et al. (2022) Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li.  Equivariant and stable positional encoding for more powerful graph neural networks.  _arXiv preprint arXiv:2203.00199_ , 2022.
  * Wang et al. (2023) Xiyuan Wang, Pan Li, and Muhan Zhang.  Improving graph neural networks on multi-node tasks with labeling tricks.  _arXiv preprint arXiv:2304.10074_ , 2023.
  * Wei et al. (2022) Tianxin Wei, Yuning You, Tianlong Chen, Yang Shen, Jingrui He, and Zhangyang Wang.  Augmentations in hypergraph contrastive learning: Fabricated and generative.  _arXiv preprint arXiv:2210.03801_ , 2022.
  * Weisfeiler & Leman (1968) Boris Weisfeiler and Andrei Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  _nti, Series_ , 2(9):12–16, 1968.
  * Wijesinghe & Wang (2021) Asiri Wijesinghe and Qing Wang.  A new perspective on" how graph neural networks go beyond weisfeiler-lehman?".  In _International Conference on Learning Representations_ , 2021.
  * Wu et al. (2020) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1):4–24, 2020.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Yadati et al. (2019) Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar.  Hypergcn: A new method for training graph convolutional networks on hypergraphs.  _Advances in neural information processing systems_ , 32, 2019.
  * Yin et al. (2017) Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich.  Local higher-order graph clustering.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM Press, 2017.  doi: 10.1145/3097983.3098069.  URL https://doi.org/10.1145/3097983.3098069.
  * You et al. (2021) Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec.  Identity-aware graph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 35, pp. 10737–10745, 2021.
  * Zeng et al. (2023) Dingyi Zeng, Wanlong Liu, Wenyu Chen, Li Zhou, Malu Zhang, and Hong Qu.  Substructure aware graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pp. 11129–11137, 2023.
  * Zhang et al. (2023) Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He.  Rethinking the expressive power of gnns via graph biconnectivity.  _arXiv preprint arXiv:2301.09505_ , 2023.
  * Zhang & Chen (2017) Muhan Zhang and Yixin Chen.  Weisfeiler-lehman neural machine for link prediction.  In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 575–583, 2017.
  * Zhang & Li (2021) Muhan Zhang and Pan Li.  Nested graph neural networks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 15734–15747. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper_files/paper/2021/file/8462a7c229aea03dde69da754c3bbcc4-Paper.pdf.
  * Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen.  Beyond link prediction: Predicting hyperlinks in adjacency space.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Zhang et al. (2021) Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin.  Labeling trick: A theory of using graph neural networks for multi-node representation learning.  _Advances in Neural Information Processing Systems_ , 34:9061–9073, 2021.
  * Zhang et al. (2019) Ruochi Zhang, Yuesong Zou, and Jian Ma.  Hyper-sagnn: a self-attention based graph neural network for hypergraphs.  _arXiv preprint arXiv:1911.02613_ , 2019.
  * Zhang et al. (2022) Simon Zhang, Soham Mukherjee, and Tamal K Dey.  Gefl: Extended filtration learning for graph classification.  In _Learning on Graphs Conference_ , pp. 16–1. PMLR, 2022.
  * Zhou et al. (2020) Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  _AI open_ , 1:57–81, 2020.

## Appendix

###  Appendix A More Background

We discuss in this section about the basics of graph representation learning
and link prediction. Graphs are hypergraphs with all hyperedges of size $2$.
Simplicial complexes and hypergraphs are generalizations of graphs. We also
discuss more related work.

####  A.1 Graph Neural Networks and Weisfeiler-Lehman 1

The Weisfeiler-Lehman (WL-1) algorithm is an isomorphism testing approximation
algorithm. It involves repeatedly message passing all nodes with their
neighbors, a step called node label refinement. The WL-1 algorithm never gives
false negatives when predicting whether two graphs are isomorphic. In other
words, two isomorphic graphs are always indistinguishable by WL-1.

The WL-1 algorithm is the following successive vertex relabeling applied until
convergence on a graph $G=(X,A)$ (a pair of the set of node attributes and the
graph’s adjacency structure):

$\displaystyle\begin{split}h_{v}^{0}&\leftarrow X_{v},\forall
v\in\mathcal{V}_{G}\\\
h_{v}^{i+1}&\leftarrow\\{\\{(h_{v}^{i},h_{u}^{i})\\}\\}_{u\in
Nbr_{A}(v)},\forall v\in\mathcal{V}_{G}\end{split}$ (8)

The algorithm terminates after the vertex labels converge. For graph
isomorphism testing, the concatenation of the histograms of vertex labels for
each iteration is output as the graph representation. Since we are only
concerned with node isomorphism classes, we ignore this step and just consider
the node labels $h_{v}^{i}$ for every $v\in\mathcal{V}_{\mathcal{C}}$.

The WL-1 isomorphism test can be characterized in terms of rooted tree
isomorphisms between the universal covers for connected graphs Krebs &
Verbitsky (2015). There have also been characterizations of WL-1 in terms of
counting homomorphisms Knill (2013) as well as the Wasserstein Distance Chen
et al. (2022) and Markov chains Chen et al. (2023).

A graph neural network (GNN) is a message passing based node representation
learner modeled after the WL-1 algorithm. It has the important inductive bias
of being equivariant to node indices. As a neural model of the WL-1 algorithm,
it learns neural weights common across all nodes in order to obtain a vector
representation for each node. A GNN must use some initial node attributes in
order to update its neural weights. There are many variations on GNNs,
including those that improve the distinguishing power beyond WL-1. For two
surveys on the GNNs and their applications, see Zhou et al. (2020); Wu et al.
(2020).

####  A.2 Link Prediction

The task of link prediction on graphs involves the prediction of the existence
of links. There are two kinds of link prediction. There is transductive link
prediction where the same nodes are used for all of train validation and
testing. There is also inductive link prediction where the test validation and
training nodes can all be disjoint. Some existing works on link prediction
include Zhang & Chen (2017). Higher order link prediction is a generalization
of link prediction to hypergraph data.

A common way to do link prediction is to compute a node-based GNN and for a
pair of nodes, aggregate, similar to in graph auto encoders Kipf & Welling
(2016b), the node representations in any target pair in order to obtain a
$2$-node representation. Such aggregations are of the form:

$h(S=\\{u,v\\})=\sigma(h_{u}\cdot h_{v})$ (9)

where $S$ is a pair of nodes. As shown in Proposition B.4, this guaranteems an
equivariant $2$-node representation but can often give false predictions even
with a fully expressive node-based GNN Wang et al. (2023). A common remedy for
this problem is to introduce positional encodings such as SEAL Wang et al.
(2022) and DistanceEncoding Li et al. (2020). Positional encodings encode the
relative distances amongst nodes via a low distortion embedding for example.
In the related work section we have gone over many of these embeddings. We
have also used these in our evaluation since they are common practice and must
exist to compute a hypergraph neural network if there are no ground truth node
attributes. According to Srinivasan & Ribeiro (2019), fully expressive
pairwise node representations, as defined by $2$-node invariance and
expressivity, can be represented by some fully expressive positional
embedding, which is a positional embedding that is injective on the node pair
isomorphism classes. It is not clear how one would achieve this in practice,
however. Another remedy is to increase the expressive power of WL-1 to WL-2
for link prediction Hu et al. (2022).

####  A.3 More Related Work

The work of Wei et al. (2022) also does a data augmentation scheme. It
considers randomly dropping edges and generating data through a generative
model on hypergraphs. The work of Lee & Shin (2022) also performs data
augmentation on a hypergraph so that homophilic relationships are maintained.
It does this through contrastive losses at the node to node, hyperedge to
hyperedge and intra hyperedge level. Neither of these methods provide
guarantees for their data augmentations.

As mentioned in the main text, an ensemble of neural networks can be used with
a drop-out Baldi & Sadowski (2014) like method on the output of the Algorithm.
Subgraph neural networks Alsentzer et al. (2020); Tan et al. (2023) are
ensembles of models on subgraphs of the input graph.

Some more of the many existing hypergraph neural network architectures
include: Kim et al. (2022); Cai et al. (2022); Chien et al. (2021); Bai et al.
(2021); Li et al. (2023a); Arya et al. (2020).

###  Appendix B Proofs

In this section we provide the proofs for all of the results in the main paper
along with some additional theory.

####  B.1 Hypergraph Isomorphism

We first repeat the definition of a hypergraph and its corresponding matrix
representation called the star expansion matrix::

######  Definition B.1.

An undirected hypergraph is a pair $\mathcal{H}=(\mathcal{V},\mathcal{E})$
consisting of a set of vertices $\mathcal{V}$ and a set of hyperedges
$\mathcal{E}\subset 2^{\mathcal{V}}\setminus(\\{\emptyset\\}\cup\\{\\{v\\}\mid
v\in{\mathcal{V}}\\})$ where $2^{\mathcal{V}}$ is the power set of the vertex
set ${\mathcal{V}}$.

######  Definition B.2.

The star expansion incidence matrix $H$ of a hypergraph
$\mathcal{H}=(\mathcal{V},\mathcal{E})$ is the $|{\mathcal{V}}|\times
2^{|{\mathcal{V}}|}$ $0$-$1$ incidence matrix $H$ where $H_{v,e}=1$ iff $v\in
e$ for $(v,e)\in{\mathcal{V}}\times{\mathcal{E}}$ for some fixed orderings on
both ${\mathcal{V}}$ and $2^{{\mathcal{V}}}$.

We recall the definition of an isomorphism between hypergraphs:

######  Definition B.3.

For two hypergraphs ${\mathcal{H}}$ and ${\mathcal{D}}$, a structure
preserving map $\rho:{\mathcal{H}}\to{\mathcal{D}}$ is a pair of maps
$\rho=(\rho_{\mathcal{V}}:{\mathcal{V}}_{\mathcal{H}}\to{\mathcal{V}}_{\mathcal{D}},\rho_{\mathcal{E}}:{\mathcal{E}}_{\mathcal{H}}\to{\mathcal{E}}_{\mathcal{D}})$
such that $\forall
e\in{\mathcal{E}}_{\mathcal{H}},\rho_{\mathcal{E}}(e)\triangleq\\{\rho_{\mathcal{V}}(v_{i})\mid
v_{i}\in e\\}\in{\mathcal{E}}_{\mathcal{D}}$. A hypergraph isomorphism is a
structure preserving map $\rho=(\rho_{\mathcal{V}},\rho_{\mathcal{E}})$ such
that both $\rho_{\mathcal{V}}$ and $\rho_{\mathcal{E}}$ are bijective. Two
hypergraphs are said to be isomorphic, denoted as
$\mathcal{H}\cong{\mathcal{D}}$, if there exists an isomorphism between them.
When $\mathcal{H}={\mathcal{D}}$, an isomorphism $\rho$ is called an
automorphism on ${\mathcal{H}}$. All the automorphisms form a group, which we
denote as $Aut(\mathcal{H})$.

The action of $\pi\in Sym(\mathcal{V})$ on the star expansion adjacency matrix
$H$ is repeated here for convenience:

$(\pi\cdot{H})_{v,e=(u_{1}...v...u_{k})}\triangleq{H}_{\pi^{-1}(v),\pi^{-1}(e)=(\pi^{-1}(u_{1})...\pi^{-1}(v)...\pi^{-1}(u_{k}))}$
(10)

Based on the group action, consider the stabilizer subgroup of
$Sym({\mathcal{V}})$ on the star expansion adjacency matrix $H$ defined as
follows:

$Stab_{Sym({\mathcal{V}})}(H)=\\{\pi\in Sym({\mathcal{V}})\mid\pi\cdot H=H\\}$
(11)

For simplicity we omit the lower index when the permutation group is clear
from the context. It can be checked that $Stab(H)\leq Sym({\mathcal{V}})$ is a
subgroup. Intuitively, $Stab(H)$ consists of all permuations that leave $H$
fixed.

For a given hypergraph ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$, there is
a relationship between the group of hypergraph automorphisms
$Aut({\mathcal{H}})$ and the stabilizer group $Stab(H)$ on the star expansion
adjacency matrix.

######  Proposition B.1.

$Aut({\mathcal{H}})\cong Stab(H)$ are equivalent as isomorphic groups.

###### Proof.

Consider $\rho\in Aut(\mathcal{H})$, define the map
$\Phi:\rho\mapsto\pi:=\rho|_{\mathcal{V}(\mathcal{H})}$. The group element
$\pi\in Sym({\mathcal{V}})$ acts as a stabilizer of $H$ since for any entry
$(v,e)$ in $H$, $H_{\pi^{-1}(v),\pi^{-1}(e)}=(\pi\cdot H)_{v,e}=1$ iff
$\pi^{-1}(e)\in\mathcal{E}_{\mathcal{H}}$ iff $e\in\mathcal{E}_{\mathcal{H}}$
iff $H_{v,e}=1=H_{\pi\circ\pi^{-1}(v),\pi\circ\pi^{-1}(e)}$. Since $(v,e)$ was
arbitrary, $\pi$ preserves the positions of the nonzeros.

We can check that $\Phi$ is a well defined injective homorphism as a
restriction map. Furthermore it is surjective since for any $\pi\in Stab(H)$,
we must have $H_{v,e}=1$ iff $(\pi\cdot
H)_{v,e}=H_{\pi^{-1}(v),\pi^{-1}(e)}=1$ which is equivalent to $v\in
e\in{\mathcal{E}}$ iff $\pi(v)\in\pi(e)\in\mathcal{E}$ which implies
$e\in\mathcal{E}$ iff $\pi(e)\in\mathcal{E}$. Thus $\Phi$ is a group
isomorphism from $Aut({\mathcal{H}})$ to $Stab(H)$ ∎

In other words, to study the symmetries of a given hypergraph ${\mathcal{H}}$,
we can equivalently study the automorphisms $Aut({\mathcal{H}})$ and the
stabilizer permutations $Stab(H)$ on its star expansion adjacency matrix $H$.
Intuitively, the stabilizer group $0\leq Stab(H)\leq Sym({\mathcal{V}})$
characterizes the symmetries in a graph. When the graph has rich symmetries,
say a complete graph, $Stab(H)=Sym(\mathcal{V})$ can be as large as the whole
permutaion group.

Nontrivial symmetries can be represented by isomorphic node sets which we
define as follow:

######  Definition B.4.

For a given hypergraph ${\mathcal{H}}$ with star expansion matrix $H$, two
$k$-node sets $S,T\subseteq\mathcal{V}$ are called _isomorphic_ , denoted as
$S\simeq T$, if $\exists\pi\in Stab(H),\pi(S)=T$ and $\pi(T)=S$.

When $k=1$, we have isomorphic nodes, denoted $u\cong_{{\mathcal{H}}}v$ for
$u,v\in{\mathcal{V}}$. Node isomorphism is also studied as the so-called
structural equivalence in Lorrain & White (1971). Furthermore, if $S\simeq T$
we can then say that there is a matching amongst the nodes in the two node
subsets so that matched nodes are isomorphic.

######  Definition B.5.

A $k$-node representation $h$ is k-permutation equivariant if:

for all $\pi\in Sym(\mathcal{V})$, $S\in 2^{\mathcal{V}}$ with $|S|=k$:
$h(\pi\cdot S,H)=h(S,\pi\cdot H)$

######  Proposition B.2.

If $k$-node representation $h$ is $k$-permutation equivariant, then $h$ is
$k$-node invariant.

###### Proof.

given $S,S^{\prime}\in\mathcal{C}$ with $|S|=|S^{\prime}|=k$,

if there exists a $\pi\in Stab(H)$ (meaning $\pi\cdot H=H$) and
$\pi(S)=S^{\prime}$ then

$\displaystyle\begin{split}h(S^{\prime},H)&=h(S^{\prime},\pi\cdot H)\text{ (by
$\pi\cdot H=H$)}\\\ &=h(S,H)\text{ (by $k$-permutation equivariance of $h$ and
$\pi(S)=S^{\prime}$)}\end{split}$ (12)

∎

####  B.2 Properties of GWL-1

Here are the steps of the GWL-1 algorithm on the star expansion matrix $H$
with node attributes $X$ is repeated here for convenience:

$\displaystyle\begin{split}f_{e}^{0}\leftarrow\\{\\},h_{v}^{0}\leftarrow
X_{v}\\\ f_{e}^{i+1}\leftarrow\\{\\{(f_{e}^{i},h_{v}^{i})\\}\\}_{v\in
e},\forall e\in\mathcal{E}(H)\\\
h_{v}^{i+1}\leftarrow\\{\\{(h_{v}^{i},f_{e}^{i+1})\\}\\}_{v\in e},\forall
v\in\mathcal{V}(H)\end{split}$ (13)

Where ${\mathcal{E}}(H)$ denotes the nonzero columns of $H$ and
${\mathcal{V}}(H)$ denotes the rows of $H$.

We make the following observations about each of the two steps of the GWL-1
algorithm:

######  Observation 2.

$\\{\\{(f_{e}^{i},h_{v}^{i})\\}\\}_{v\in
e}=\\{\\{({f^{\prime}}_{e}^{i},{h^{\prime}}_{v}^{i})\\}\\}_{v\in e}\text{ iff
}(f_{e}^{i},\\{\\{h_{v}^{i}\\}\\}_{v\in
e})=({f^{\prime}}_{e}^{i},\\{\\{{h^{\prime}}_{v}^{i}\\}\\}_{v\in e})\forall
e\in\mathcal{E}(H)\text{ and }$ (14a)
$\\{\\{(h_{v}^{i},f_{e}^{i+1}\\}\\}_{v\in
e}=\\{\\{({h^{\prime}}_{v}^{i},{f^{\prime}}_{e}^{i+1}\\}\\}_{v\in e}\text{ iff
}(h_{v}^{i},\\{\\{f_{e}^{i+1}\\}\\}_{v\in
e})=({h^{\prime}}_{v}^{i},\\{\\{{f^{\prime}}_{e}^{i+1}\\}\\}_{v\in e})\forall
v\in\mathcal{V}(H)$ (14b)

###### Proof.

Equation 14a follows since

$\\{\\{(f_{e}^{i},h_{v}^{i})\\}\\}_{v\in
e}=\\{\\{({f^{\prime}}_{e}^{i},{h^{\prime}}_{v}^{i})\\}\\}_{v\in e}\forall
e\in\mathcal{E}(H)$ (15a) $\text{ iff }f_{e}^{i}={f^{\prime}}_{e}^{i}\text{
and }\\{\\{h_{v}^{i}\\}\\}_{v\in e}=\\{\\{{h^{\prime}}_{v}^{i}\\}\\}_{v\in
e}\forall e\in\mathcal{E}(H)$ (15b) $\text{ iff }\\\
(f_{e}^{i},\\{\\{h_{v}^{i}\\}\\}_{v\in
e})=({f^{\prime}}_{e}^{i},\\{\\{{h^{\prime}}_{v}^{i}\\}\\}_{v\in e})\forall
e\in\mathcal{E}(H)$ (15c)

For Equation 14b, we have:

$\\{\\{(h_{v}^{i},f_{e}^{i+1}\\}\\}_{v\in
e}=\\{\\{({h^{\prime}}_{v}^{i},{f^{\prime}}_{e}^{i+1}\\}\\}_{v\in e}\forall
v\in\mathcal{V}(H)$ (16a) $\text{ iff
}\\{\\{(h_{v}^{i},\\{\\{(f_{e}^{i},h_{u}^{i})\\}\\}_{u\in e})\\}\\}_{v\in
e}=\\{\\{({h^{\prime}}_{v}^{i},\\{\\{({f^{\prime}}_{e}^{i},{h^{\prime}}_{u}^{i})\\}\\}_{u\in
e})\\}\\}_{v\in e}\forall v\in\mathcal{V}(H)$ (16b) $\text{ iff
}h_{v}^{i}={h^{\prime}}_{v}^{i}\text{ and
}\\{\\{(f_{e}^{i},h_{u}^{i})\\}\\}_{u\in e,v\in
e}=\\{\\{({f^{\prime}}_{e}^{i},{h^{\prime}}_{u}^{i})\\}\\}_{u\in e,v\in
e}\forall v\in\mathcal{V}(H)$ (16c) $\text{ iff
}h_{v}^{i}={h^{\prime}}_{v}^{i}\text{ and
}\\{\\{f_{e}^{i+1}\\}\\}=\\{\\{{f^{\prime}}_{e}^{i+1}\\}\\}\forall
v\in\mathcal{V}(H)$ (16d)

These follow by the definition of multiset equality and since there is no loss
of information upon factoring out a constant tuple entry of each pair in the
multisets. ∎

######  Proposition B.3.

The update steps of GWL-1: $f^{i}(H)\triangleq[f^{i}_{e_{1}}(H),\cdots
f^{i}_{e_{m}}(H)]$ and $h^{i}(H)\triangleq[h^{i}_{v_{1}}(H),\cdots
h^{i}_{v_{n}}(H)]$, are permutation equivariant; in other words, For any
$\pi\in Sym({\mathcal{V}})$, let $\pi\cdot
f^{i}(H)\triangleq[f^{i}_{\pi^{-1}(e_{1})}(H),\cdots,f^{i}_{\pi^{-1}(e_{m})}(H)]$
and $\pi\cdot h^{i}(H)\triangleq[h^{i}_{\pi^{-1}(v_{1})}(H),\cdots
h^{i}_{\pi^{-1}(v_{n})}(H)]$, we have $\forall i\in\mathbb{N},\pi\cdot
f^{i}(H)=f^{i}(\pi\cdot H)\text{ and }\pi\cdot h^{i}(H)=h^{i}(\pi\cdot H)$

###### Proof.

We prove by induction on $i$:

Base case, $i=0$:

$[\pi\cdot
f^{0}(H)]_{e=\\{v_{1}...v_{k}\\}}=\\{\\}=f_{\pi^{-1}(e)=\\{\pi^{-1}(v_{1})...\pi^{-1}(v_{k})\\}}^{0}(H)=f_{e}^{0}(\pi\cdot
H)$ since the $\pi$ cannot affect a list of empty sets and the definition of
the action of $\pi$ on $H$ as defined in Equation 10.

$[\pi\cdot h^{0}(H)]_{v}=[\pi\cdot
X]_{v}=X_{\pi^{-1}(v)}=h_{\pi^{-1}(v)}^{0}(H)=h^{0}_{v}(\pi\cdot H)$ by
definition of the group action $Sym(\mathcal{V})$ acting on the node indices
of a node attribute tensor as defined in Equation 10.

Induction Hypothesis:

$[\pi\cdot f^{i}(H)]_{e}=f_{\pi^{-1}(e)}^{i}(H)=f_{e}^{i}(\pi\cdot H)\text{
and }[\pi\cdot h^{i}(H)]_{v}=h_{\pi^{-1}(v)}^{i}(H)=h_{v}^{i}(\pi\cdot H)$
(17)

Induction Step:

$\displaystyle\begin{split}[\pi\cdot h^{i+1}(H)]_{v}&=\\{\\{([\pi\cdot
h^{i}(H)]_{v},[\pi\cdot f^{i+1}(H)]_{e})\\}\\}_{v\in e}\\\ &=\\{\\{([\pi\cdot
h^{i}(H)]_{v},\\{\\{([\pi\cdot f^{i}(H)]_{e},[\pi\cdot
h^{i}(H)]_{u})\\}\\}_{u\in e})\\}\\}_{v\in e}\\\ &=\\{\\{h^{i}_{v}(\pi\cdot
H),\\{\\{(f^{i}_{e}(\pi\cdot H),h^{i}_{u}(\pi\cdot H))\\}\\}_{u\in
e}\\}\\}_{v\in e}\\\ &=h^{i+1}_{v}(\pi\cdot H)\end{split}$ (18)

$\displaystyle\begin{split}[\pi\cdot f^{i+1}(H)]_{e}&=\\{\\{([\pi\cdot
f^{i}(H)]_{e},[\pi\cdot h^{i}(H)]_{v})\\}\\}_{v\in e}\\\
&=\\{\\{(f^{i}_{e}(\pi\cdot H),h^{i}_{v}(\pi\cdot H)\\}\\}_{v\in e}\\\
&=f^{i+1}_{e}(\pi\cdot H)\end{split}$ (19)

∎

######  Definition B.6.

Let $h:[\mathcal{V}]^{k}\times\mathbb{Z}_{2}^{n\times
2^{n}}\rightarrow\mathbb{R}^{d}$ be a $k$-node representation on a hypergraph
$\mathcal{H}$. Let $H\in\mathbb{Z}_{2}^{n\times 2^{n}}$ be the star expansion
adjacency matrix of $\mathcal{H}$ for $n$ nodes. The representation $h$ is
$k$-node most expressive if $\forall S,S^{\prime}\subset\mathcal{V}$,
$|S|=|S^{\prime}|=k$, the following two conditions are satisfied:

  1. 1.

$h$ is k-node invariant: $\exists\pi\in Stab(H),\pi(S)=S^{\prime}\implies
h(S,H)=h(S^{\prime},H)$

  2. 2.

$h$ is k-node expressive $\nexists\pi\in Stab(H),\pi(S)=S^{\prime}\implies
h(S,H)\neq h(S^{\prime},H)$

Let $AGG$ be a permutation invariant map from a set of node representations to
$\mathbb{R}^{d}$.

######  Proposition B.4.

Let $h(S,H)=AGG_{v\in S}[h_{v}^{i}(H)]$ with injective AGG and $h_{v}^{i}$
permutation equivariant. The representation $h(S,H)$ is $k$-node invariant but
not necessarily $k$-node expressive for $S$ a set of $k$ nodes.

###### Proof.

$\exists\pi\in Stab(H)$ s.t. $\pi(S)=S^{\prime},\pi\cdot H=H$

$\Rightarrow\pi(v_{i})=v_{i}^{\prime}$ for $i=1...|S|,\pi\cdot H=H$

$\Rightarrow h_{\pi(v)}^{i}(H)=h_{v}^{i}(\pi\cdot H)=h_{v}^{i}(H)$ (By
permutation equivariance of $h^{i}_{v}$ and $\pi\cdot H=H$)

$\Rightarrow AGG_{v\in S}[h_{v}^{i}(H)]=AGG_{v^{\prime}\in
S^{\prime}}[h_{v^{\prime}}^{i}(H)]$ (By Proposition B.2 and AGG being
permutation invariant)

The converse, that $h(S,H)$ is $k$-node expressive, is not necessarily true
since we cannot guarantee $h(S,H)=h(S^{\prime},H)$ implies the existence of a
permutation that maps $S$ to $S^{\prime}$ (see Zhang et al. (2021)). ∎

A hypergraph can be represented by a bipartite graph
$\mathcal{B}_{\mathcal{V},\mathcal{E}}$ from $\mathcal{V}$ to $\mathcal{E}$
where there is an edge $(v,e)$ in the bipartite graph iff node $v$ is incident
to hyperedge $e$. This bipartite graph $\mathcal{B}_{\mathcal{V},\mathcal{E}}$
is called the star expansion bipartite graph.

We introduce a more structured version of graph isomorphism called a $2$-color
isomorphism to characterize hypergraphs. It is a map on $2$-colored graphs,
which are graphs that can be colored with two colors so that no two nodes in
any graph with the same color are connected by an edge. We define a
$2$-colored isomorphism formally here:

######  Definition B.7.

A $2$-colored isomorphism is a graph isomorphism on two $2$-colored graphs
that preserves node colors. In particular, between two graphs $G_{1}$ and
$G_{2}$ the vertices of one color in $G_{1}$ must map to vertices of the same
color in $G_{2}$. It is denoted by $\cong_{c}$.

A bipartite graph must always have a $2$-coloring. In fact, the $2$-coloring
with all the nodes in the node bipartition colored red and all the nodes in
the hyperedge bipartition colored blue forms a canonical $2$-coloring of
$\mathcal{B}_{\mathcal{V},\mathcal{E}}$. Assume that all star expansion
bipartite graphs are canonically $2$-colored.

######  Proposition B.5.

We have two hypergraphs
$(\mathcal{V}_{1},\mathcal{E}_{1})\cong(\mathcal{V}_{2},\mathcal{E}_{2})$ iff
$\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}\cong_{c}\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$
where $\mathcal{B}_{\mathcal{V},\mathcal{E}}$ is the star expansion bipartite
graph of $(\mathcal{V},\mathcal{E})$

###### Proof.

Denote $L(\mathcal{B}_{\mathcal{V}_{i},\mathcal{E}_{i}})$ as the left hand
(red) bipartition of $\mathcal{B}_{\mathcal{V}_{i},\mathcal{E}_{i}}$ to
represent the nodes $\mathcal{V}_{i}$ of $(\mathcal{V}_{i},\mathcal{E}_{i})$
and $R(\mathcal{B}_{\mathcal{V}_{i},\mathcal{E}_{i}})$ as the right hand
(blue) bipartition of $\mathcal{B}_{\mathcal{V}_{i},\mathcal{E}_{i}}$ to
represent the hyperedges $\mathcal{E}_{i}$ of
$(\mathcal{V}_{i},\mathcal{E}_{i})$. We use the left/right bipartition and
$\mathcal{V}_{i}$/$\mathcal{E}_{i}$ interchangeably since they are in
bijection.

$\Rightarrow$ If there is an isomorphism
$\pi:\mathcal{V}_{1}\rightarrow\mathcal{V}_{2}$, this means

  * •

$\pi$ is a bijection and

  * •

has the structure preserving property that $(u_{1}...u_{k})\in\mathcal{E}_{1}$
iff $(\pi(u_{1})...\pi(u_{k}))\in\mathcal{E}_{2}$.

We may induce a $2$-colored isomorphism
$\pi^{*}:\mathcal{V}(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})\rightarrow\mathcal{V}(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})$
so that $\pi^{*}|_{L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})}=\pi$
where equality here means that
$\pi^{*}|_{L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})}$ acts on
$L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})$ the same way that $\pi$
does on $\mathcal{V}_{1}$. Furthermore $\pi^{*}$ has the property that
$\pi^{*}|_{R(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})}(u_{1}...u_{k})=(\pi(u_{1})...\pi(u_{k})),\forall(u_{1}...u_{k})\in\mathcal{E}_{1}$,
following the structure preserving property of isomorphism $\pi$.

The map $\pi^{*}$ is a bijection by definition of being an extension of a
bijection.

The map $\pi^{*}$ is also a $2$-colored map since it maps
$L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})$ to
$L(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}})$ and
$R(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})$ to
$R(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}})$.

We can also check that the map is structure preserving and thus a $2$-colored
isomorphism since
$(u_{i},(u_{1}...u_{i}...u_{k}))\in\mathcal{E}(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}),\forall
i=1...k$ iff ($u_{i}\in\mathcal{V}_{1}$ and
$(u_{1}...u_{i}...u_{k})\in\mathcal{E}_{1}$) iff
$\pi(u_{i})\in\mathcal{V}_{2}$ and
$(\pi(u_{1})...\pi(u_{i})...\pi(u_{k}))\in\mathcal{E}_{2}$ iff
$(\pi^{*}(u_{i}),(\pi^{*}(u_{1},...u_{i},...u_{k}))\in\mathcal{E}(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}),\forall
i=1...k$. This follows from $\pi$ being structure preserving and the
definition of $\pi^{*}$.

$\Leftarrow$ If there is a $2$-colored isomorphism
$\pi^{*}:\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}\rightarrow\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$
then it has the properties that

  * •

$\pi^{*}$ is a bijection,

  * •

(is $2$-colored):
$\pi^{*}|_{L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}):L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})\rightarrow
L(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}})$ and
$\pi^{*}|_{R(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})}:R(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})\rightarrow
R(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}})$

  * •

(it is structure preserving):
$(u_{i},(u_{1}...u_{i}...u_{k}))\in\mathcal{E}(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}),\forall
i=1...k$ iff
$(\pi^{*}(u_{i}),\pi^{*}(u_{1}...u_{i}...u_{k}))\in\mathcal{E}(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}),\forall
i=1...k$ .

This then means that we may induce a
$\pi:\mathcal{V}_{1}\rightarrow\mathcal{V}_{2}$ so that
$\pi=\pi^{*}|_{L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})}$.

We can check that $\pi$ is a bijection since $\pi$ is the $2$-colored
bijection $\pi^{*}$ restricted to
$L(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})$, thus remaining a
bijection.

We can also check that $\pi$ is structure preserving. This means that
$(u_{1}...u_{k})\in\mathcal{E}_{1}$ iff
$(u_{i},(u_{1}...u_{i}...u_{k}))\in\mathcal{E}(\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}})\forall
i=1...k$ iff
$(\pi^{*}(u_{i}),(\pi^{*}(u_{1}...u_{i}...u_{k})))\in\mathcal{E}(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}})\forall
i=1...k$ iff $(\pi^{*}(u_{1}...u_{k}))\in
R(\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}})$ iff
$(\pi(u_{1})...\pi(u_{k}))\in\mathcal{E}_{2}$ ∎

We define a topological object for a graph originally from algebraic topology
called a universal cover:

######  Definition B.8.

(Hatcher (2005)) A universal covering of a connected graph $G$ is a
(potentially infinite) graph $\tilde{G}$, s.t. there is a map
$p_{G}:\tilde{G}\rightarrow G$ called the universal covering map where:

1\. $\forall x\in{\mathcal{V}}(\tilde{G})$, $p_{G}|_{N(x)}$ is an isomorphism
onto $N(p_{G}(x))$.

2\. $\tilde{G}$ is simply connected (a tree)

A covering graph is a graph that satisfies property 1 but not necessarily
property 2 in Definition B.8. It is known that a universal covering
$\tilde{G}$ covers all the graph covers of the graph $G$. Let $T_{x}^{G}$
denote a tree with root $x$. Furthermore, define a rooted isomorphism
$G_{x}\cong H_{y}$ as an isomorphism between graphs $G$ and $H$ that maps $x$
to $y$ and vice versa. We will use the following result to prove a
characterization of GWL-1:

######  Lemma B.6 (Krebs & Verbitsky (2015)).

Let $T$ and $S$ be trees and $x\in V(T)$ and $y\in V(S)$ be their vertices of
the same degree with neighborhoods $N(x)=\\{x_{1},...,x_{k}\\}$ and
$N(y)=\\{y_{1},...,y_{k}\\}$. Let $r\geq 1$. Suppose that $T^{r-1}_{x}\cong
S^{r-1}_{y}$ and $T^{r}_{x_{i}}\cong S^{r}_{y_{i}}$ for all $i\leq k$. Then
$T^{r+1}_{x}\cong S^{r+1}_{y}$.

A universal cover of a $2$-colored bipartite graph is still $2$ colored. When
we lift nodes $v$ and hyperedge nodes $e$ to their universal cover, we keep
their respective red and blue colors.

Define a rooted colored isomorphism
$T_{\tilde{e}_{1}}^{k}\cong_{c}T_{\tilde{e}_{2}}^{k}$ as a colored tree
isomorphism where blue/red node $\tilde{e}_{1}$/$\tilde{v}_{1}$ maps to
blue/red node $\tilde{e}_{2}$/$\tilde{v}_{2}$ and vice versa.

In fact, Lemma B.6 holds for $2$-colored isomorphisms, which we show below:

######  Lemma B.7.

Let $T$ and $S$ be $2$-colored trees and $x\in V(T)$ and $y\in V(S)$ be their
vertices of the same degree with neighborhoods $N(x)=\\{x_{1},...,x_{k}\\}$
and $N(y)=\\{y_{1},...,y_{k}\\}$. Let $r\geq 1$. Suppose that
$T^{r-1}_{x}\cong_{c}S^{r-1}_{y}$ and $T^{r}_{x_{i}}\cong_{c}S^{r}_{y_{i}}$
for all $i\leq k$. Then $T^{r+1}_{x}\cong_{c}S^{r+1}_{y}$.

###### Proof.

Certainly $2$-colored isomorphisms are rooted isomorphisms on $2$-colored
trees. The converse is true if the roots match in color since recursively all
descendants of the root must match in color.

If $T_{x}^{r-1}\cong_{c}S_{y}^{r-1}$ and $T_{x_{i}}^{r}\cong_{c}S_{y_{i}}^{r}$
for all $i\leq k$ and $N(x)=\\{x_{1}...x_{k}\\},N(y)=\\{y_{1}..y_{k}\\}$, the
roots $x$ and $y$ must match in color. The neighborhoods $N(x)$ and $N(y)$
then must both be of the opposing color. Since rooted colored isomorphisms are
rooted isomorphisms, we must have $T_{x}^{r-1}\cong S_{y}^{r-1}$ and
$T_{x_{i}}^{r}\cong S_{y_{i}}^{r}$ for all $i\leq k$. By Lemma B.6, we have
$T_{x}^{r+1}\cong S_{y}^{r+1}$. Once the roots match in color, a rooted tree
isomorphism is the same as a rooted $2$-colored tree isomorphism. Thus, since
$x$ and $y$ share the same color, $T_{x}^{r+1}\cong_{c}S_{y}^{r+1}$ ∎

######  Theorem B.8.

Let $\mathcal{H}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ and
$\mathcal{H}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})$ be two connected
hypergraphs. Let $\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}$ and
$\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$ be two canonically colored
bipartite graphs for $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ (vertices colored
red and hyperedges colored blue)

For any $i\in\mathbb{N}^{+}$, for any of the nodes
$x_{1}\in\mathcal{B}_{\mathcal{V}_{1}},e_{1}\in\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}$
and
$x_{2}\in\mathcal{B}_{\mathcal{V}_{1}},e_{2}\in\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$:

$(\tilde{\mathcal{B}}^{2i-1}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{e}_{1}}\cong_{c}(\tilde{\mathcal{B}}^{2i-1}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{e}_{2}}$
iff $f^{i}_{e_{1}}=f^{i}_{e_{2}}$

$(\tilde{\mathcal{B}}^{2i}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{x}_{1}}\cong_{c}(\tilde{\mathcal{B}}^{2i}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{x}_{2}}$
iff $h^{i}_{x_{1}}=h^{i}_{x_{2}}$ , with $f^{i}_{\bullet},h^{i}_{\bullet}$ the
$i$th GWL-1 values for the hyperedges and nodes respectively where
$e_{1}=p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}(\tilde{e}_{1})$,
$x_{1}=p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}(\tilde{x}_{1})$,
$e_{2}=p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}(\tilde{e}_{2})$,
$x_{2}=p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}(\tilde{x}_{2})$. The
maps
$p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}}:\tilde{\mathcal{B}}_{\mathcal{V}_{1},\mathcal{E}_{1}}\rightarrow\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}},p_{\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}}:\tilde{\mathcal{B}}_{\mathcal{V}_{2},\mathcal{E}_{2}}\rightarrow\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$
are the universal covering maps of
$\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{1}}$ and
$\mathcal{B}_{\mathcal{V}_{2},\mathcal{E}_{2}}$ respectively.

###### Proof.

We prove by induction:

Let
$T_{\tilde{e}_{1}}^{k}:=(\tilde{\mathcal{B}}^{k}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{e}_{1}}$
where $\tilde{e}_{1}$ is a pullback of a hyperedge, meaning
$p_{\mathcal{B}_{\mathcal{V}_{1},\mathcal{E}_{2}}}(\tilde{e}_{1})=e_{1}$.
Similarly, let
$T_{\tilde{e}_{2}}^{k}:=(\tilde{\mathcal{B}}^{k}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{e}_{2}}$,
$T_{\tilde{x}_{1}}^{k}:=(\tilde{\mathcal{B}}^{k}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{x}_{1}}$,
$T_{\tilde{x}_{2}}^{k}:=(\tilde{\mathcal{B}}^{k}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{x}_{2}}$,
$\forall k\in\mathbb{N}$, where
$\tilde{e}_{1},\tilde{e}_{2},\tilde{x}_{1},\tilde{x}_{2}$ are the respective
pullbacks of $e_{1},e_{2},x_{1},x_{2}$.

Define an ($2$-colored) isomorphism of multisets to mean that there exists a
bijection between the two multisets so that each element in one multiset is
($2$-colored) isomorphic with exactly one other element in the other multiset.

By Observation 3 we can rewrite GWL-1 as:

$f_{e}^{0}\leftarrow\\{\\},h_{v}^{0}\leftarrow X_{v}$ (20)
$f_{e}^{i+1}\leftarrow(f_{e}^{i},\\{\\{h_{v}^{i}\\}\\}_{v\in e})\forall
e\in\mathcal{E}_{{\mathcal{H}}}$ (21)
$h_{v}^{i+1}\leftarrow(h_{v}^{i},\\{\\{f_{e}^{i+1}\\}\\}_{v\in e})\forall
v\in\mathcal{V}_{\mathcal{H}}$ (22)

Base Case $i=1$:

$T^{1}_{\tilde{e}_{1}}\cong_{c}T^{1}_{\tilde{e}_{2}}\text{ iff
}(T^{0}_{\tilde{e}_{1}}\cong_{c}T^{0}_{\tilde{e}_{2}}\text{ and
}\\{\\{T^{0}_{\tilde{x}_{1}}\\}\\}_{\tilde{x}_{1}\in
N(\tilde{e}_{1})}\cong_{c}\\{\\{T^{0}_{\tilde{x}_{2}}\\}\\}_{\tilde{x}_{2}\in
N(\tilde{e}_{2})})\text{ (By Lemma \ref{lemma: appendix-induct-
krebsverbitsky-2colored})}$ (23a) $\text{ iff
}(f_{e_{1}}^{0}=f_{e_{2}}^{0}\text{ and
}\\{\\{h_{x_{1}}^{0}\\}\\}=\\{\\{h_{x_{2}}^{0}\\}\\})\text{ (By Equation
\ref{eq: init})}$ (23b) $\text{ iff }f_{e_{1}}^{1}=f_{e_{2}}^{1}\text{ (By
Equation \ref{eq: fei+1})}$ (23c)

$T^{2}_{\tilde{x}_{1}}\cong_{c}T^{2}_{\tilde{x}_{2}}\text{ iff
}(T^{0}_{\tilde{x}_{1}}\cong_{c}T^{0}_{\tilde{x}_{2}}\text{ and
}\\{\\{T^{1}_{\tilde{e}_{1}}\\}\\}_{\tilde{e}_{1}\in
N(\tilde{x}_{1})}\cong_{c}\\{\\{T^{1}_{\tilde{e}_{2}}\\}\\}_{\tilde{e}_{2}\in
N(\tilde{x}_{2})})\text{ (By Lemma \ref{lemma: appendix-induct-
krebsverbitsky-2colored})}$ (24a) $\text{ iff
}(h_{e_{1}}^{0}=h_{e_{2}}^{0}\text{ and
}\\{\\{f_{x_{1}}^{1}\\}\\}=\\{\\{f_{x_{2}}^{1}\\}\\})\text{ (By Equation
\ref{eq: init})}$ (24b) $\text{ iff }f_{e_{1}}^{1}=f_{e_{2}}^{1}\text{ (By
Equation \ref{eq: hvi+1})}$ (24c)

Induction Hypothesis: For $i\geq 1$,
$T_{\tilde{e}_{1}}^{2i-1}\cong_{c}T_{\tilde{e}_{2}}^{2i-1}$ iff
$f_{{e}_{1}}^{i}=f_{{e}_{2}}^{i}$ and
$T_{\tilde{x}_{1}}^{2i}\cong_{c}T_{\tilde{x}_{2}}^{2i}$ iff
$h_{{x}_{1}}^{i}=h_{{x}_{2}}^{i}$

Induction Step:

$T^{2i+1}_{\tilde{e}_{1}}\cong_{c}T^{2i+1}_{\tilde{e}_{2}}\text{ iff
}(T^{2i-1}_{\tilde{e}_{1}}\cong_{c}T^{2i-1}_{\tilde{e}_{2}}\text{ and
}\\{\\{T^{2i}_{\tilde{x}_{1}}\\}\\}_{\tilde{x}_{1}\in
N(\tilde{e}_{1})}\cong_{c}\\{\\{T^{2i}_{\tilde{x}_{2}}\\}\\}_{\tilde{x}_{2}\in
N(\tilde{e}_{2})})\text{ (By Lemma \ref{lemma: appendix-induct-
krebsverbitsky-2colored})}$ (25a) $\text{ iff
}(f_{e_{1}}^{i}=f_{e_{2}}^{i}\text{ and
}\\{\\{h_{x_{1}}^{i}\\}\\}=\\{\\{h_{x_{2}}^{i}\\}\\})\text{ (By Induction
Hypothesis)}$ (25b) $\text{ iff }f_{e_{1}}^{i+1}=f_{e_{2}}^{i+1}\text{ (By
Equation \ref{eq: fei+1})}$ (25c)

$T^{2i}_{\tilde{x}_{1}}\cong_{c}T^{2i}_{\tilde{x}_{2}}\text{ iff
}(T^{2i-2}_{\tilde{x}_{1}}\cong_{c}T^{2i-2}_{\tilde{x}_{2}}\text{ and
}\\{\\{T^{2i-1}_{\tilde{e}_{1}}\\}\\}_{\tilde{e}_{1}\in
N(\tilde{x}_{1})}\cong_{c}\\{\\{T^{2i-1}_{\tilde{e}_{2}}\\}\\}_{\tilde{e}_{2}\in
N(\tilde{x}_{2})})\text{ (By Lemma \ref{lemma: appendix-induct-
krebsverbitsky-2colored})}$ (26a) $\text{ iff
}(h_{e_{1}}^{i}=h_{e_{2}}^{i}\text{ and
}\\{\\{f_{x_{1}}^{i}\\}\\}=\\{\\{f_{x_{2}}^{i}\\}\\})\text{ (By Equation
\ref{eq: init})}$ (26b) $\text{ iff }h_{x_{1}}^{i}=h_{x_{2}}^{i}\text{ (By
Equation \ref{eq: hvi+1})}$ (26c)

∎

######  Observation 3.

If the node values for nodes $x$ and $y$ from GWL-1 for $i$ iterations on two
hypergraphs $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ are the same, then for all
$j$ with $0\leq j\leq i$, the node values for GWL-1 for $j$ iterations on $x$
and $y$ also agree. In particular $\deg(x)=\deg(y)$.

###### Proof.

There is a $2$-color isomorphism on subtrees
$(\tilde{\mathcal{B}}^{j}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{x}}$ and
$(\tilde{\mathcal{B}}^{j}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{y}}$ of
the $i$-hop subtrees of the universal covers rooted about nodes
$x\in\mathcal{V}_{1}$ and $y\in\mathcal{V}_{2}$ for $0\leq j\leq i$ since
$(\tilde{\mathcal{B}}^{i}_{\mathcal{V}_{1},\mathcal{E}_{1}})_{\tilde{x}}\cong_{c}(\tilde{\mathcal{B}}^{i}_{\mathcal{V}_{2},\mathcal{E}_{2}})_{\tilde{y}}$.
By Theorem B.8, we have that GWL-1 returns the same value for $x$ and $y$ for
each $0\leq j\leq i$ . ∎

######  Proposition B.9.

If GWL-1 cannot distinguish two connected hypergraphs $H_{1}$ and $H_{2}$ then
HyperPageRank will not either.

###### Proof.

HyperPageRank is defined on a hypergraph with star expansion matrix $H$ as the
following stationary distribution $\Pi$:

$\lim_{n\rightarrow\infty}(D_{v}^{-1}\cdot H\cdot D_{e}^{-1}\cdot
H^{T})^{n}=\Pi$ (27)

If $H$ is a connected bipartite graph, $\Pi$ must be the eigenvector of
$(D_{v}^{-1}\cdot H\cdot D_{e}^{-1}\cdot H^{T})$ for eigenvalue $1$. In other
words, $\Pi$ must satisfy

$(D_{v}^{-1}\cdot H\cdot D_{e}^{-1}\cdot H^{T})\cdot\Pi=\Pi$ (28)

By Theorem 1 of Huang & Yang (2021), we know that the UniGCN defined by:

$h_{e}^{i+1}\leftarrow\phi_{2}(h_{e}^{i},h_{v}^{i})=W_{e}\cdot H^{T}\cdot
h_{v}^{i}$ (29a)
$h^{i+1}_{v}\leftarrow\phi_{1}(h_{v}^{i},h_{e}^{i+1})=W_{v}\cdot H\cdot
h_{e}^{i+1}$ (29b)

for constant $W_{e}$ and $W_{v}$ weight matrices, is equivalent to GWL-1
provided that $\phi_{1}$ and $\phi_{2}$ are both injective as functions.
Without injectivity, we can only guarantee that if UniGCN distinguishes
$H_{1},H_{2}$ then GWL-1 distinguishes $H_{1},H_{2}$. In fact, each matrix
power of order $n$ in Equation 27 corresponds to $h_{v}^{n}$ so long as we
satisfy the following constraints:

$W_{e}\leftarrow D_{e}^{-1},W_{v}\leftarrow D_{v}^{-1}\text{ and
}h_{v}^{0}\leftarrow I$ (30)

We show that the matrix powers are UniGCN under the constraints of Equation 30
by induction:

Base Case: $n=0$: $h_{v}^{0}=I$

Induction Hypothesis: $n>0$:

$(D_{v}^{-1}\cdot H\cdot D_{e}^{-1}\cdot H^{T})^{n}=h_{v}^{n}$ (31)

Induction Step:

$(D_{v}^{-1}\cdot H\cdot h_{e}^{n})$ (32a) $=(D_{v}^{-1}\cdot
H\cdot((D_{e}^{-1}\cdot H^{T})\cdot h_{v}^{n}))$ (32b) $=(D_{v}^{-1}\cdot
H\cdot D_{e}^{-1}\cdot H^{T})\cdot(D_{v}^{-1}\cdot H\cdot D_{e}^{-1}\cdot
H^{T})^{n}$ (32c) $=(D_{v}^{-1}\cdot H\cdot D_{e}^{-1}\cdot
H^{T})^{n+1}=h_{v}^{n+1}$ (32d)

Since we cannot guarantee that the maps $\phi_{1}$ and $\phi_{2}$ are
injective in Equation 32b, it must be that the output $h_{v}^{n}$, coming from
UniGCN with the constraints of Equation 30, is at most as powerful as GWL-1.

In general, injectivity preserves more information. For example, if $\phi_{1}$
is injective and if $\phi_{1}^{\prime}$ is an arbitrary map (not guaranteed to
be injective) then:

$\phi_{1}(h_{1})=\phi_{1}(h_{2})\Rightarrow
h_{1}=h_{2}\Rightarrow\phi_{1}^{\prime}(h_{1})=\phi_{1}^{\prime}(h_{2})$ (33)

HyperpageRank is exactly as powerful as UniGCN under the constraints of
Equation 30. Thus HyperPageRank is at most as powerful as GWL-1 in
distinguishing power. ∎

Figure 4:  An illustration of hypergraph symmetry breaking. (c,d) $3$-regular
hypergraphs $C_{4}^{3}$, $C_{5}^{3}$ with $4$ and $5$ nodes respectively and
their corresponding universal covers centered at any hyperedge
$(\tilde{\mathcal{B}}_{C^{3}_{4}})_{e_{*,*,*}},(\tilde{\mathcal{B}}_{C^{3}_{5}})_{e_{*,*,*}}$
with universal covering maps
$p_{\mathcal{B}_{C_{4}^{3}}},p_{\mathcal{B}_{C_{5}^{3}}}$. (b,e) the
hypergraphs $\hat{C}_{4}^{3},\hat{C}_{5}^{3}$, which are $C_{4}^{3},C_{5}^{3}$
with $4,5$-sized hyperedges attached to them and their corresponding universal
covers and universal covering maps. (a,f) are the corresponding bipartite
graphs of $\hat{C}_{4}^{3},\hat{C}_{5}^{3}$. (c,d) are indistinguishable by
GWL-1 and thus will give identical node values by Theorem B.8. On the other
hand, (b,e) gives node values which are now sensitive to the the order of the
hypergraphs $4,5$, also by Theorem B.8.

####  B.3 Method

We repeat here from the main text the symmetry finding algorithm:

Data: Hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, represented by its
star expansion matrix $H$. $L\in\mathbb{N}^{+}$ is the number of iterations to
run GWL-1.

Result: A pair of collections:
$(\mathcal{R}_{V}=\\{\mathcal{V}_{R_{j}}\\},\mathcal{R}_{E}=\cup_{j}\\{\mathcal{E}_{R_{j}}\\})$
where $R_{j}$ are disconnected subhypergraphs exhibiting symmetry in
$\mathcal{H}$ that are indistinguishable by $L$-GWL-1.

1 $E_{deg}\leftarrow\\{\\{deg(v):v\in e\\}:\forall e\in{\mathcal{E}}\\}$

$U_{L}\leftarrow h_{v}^{L}(H);{\mathcal{G}}_{L}\leftarrow\\{U_{L}[v]:\forall
v\in\mathcal{V}\\}$ ;

/* $U_{L}[v]$ is the $L$-GWL-1 value of node $v\in{\mathcal{V}}$. */

2

${\mathcal{B}}_{{\mathcal{V}}_{{\mathcal{H}}},{\mathcal{E}}_{{\mathcal{H}}}}\leftarrow
Bipartite({\mathcal{H}})$ /* Construct the bipartite graph from
${\mathcal{H}}$. */

3

4$\mathcal{R}_{V}\leftarrow\\{\\}$; $\mathcal{R}_{E}\leftarrow\\{\\}$

5for  _$c_{L}\in{\mathcal{G}}_{L}$_ do

6
${\mathcal{V}}_{c_{L}}\leftarrow\\{v\in\mathcal{V}:U_{L}[v]=c_{L}\\},{\mathcal{E}}_{c_{L}}\leftarrow\\{e\in\mathcal{E}:u\in\mathcal{V}_{c_{L}},\forall
u\in e\\}$

7 $\mathcal{C}_{c_{L}}\leftarrow$
ConnectedComponents$({\mathcal{H}}_{c_{L}}=({\mathcal{V}}_{c_{L}},{\mathcal{E}}_{c_{L}}))$

8 for  _${\mathcal{R}}_{c_{L},i}\in{\mathcal{C}}_{c_{L}}$_ do

9 if  _$|\mathcal{V}_{\mathcal{R}_{c_{L},i}}|\geq 3$ and
$\\{deg(v):v\in({\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}})\\}\notin E_{deg}$ _
then

10
$\mathcal{R}_{V}\leftarrow\mathcal{R}_{V}\cup\\{\mathcal{V}_{\mathcal{R}_{c_{L},i}}\\}$;
$\mathcal{R}_{E}\leftarrow\mathcal{R}_{E}\cup\mathcal{E}_{\mathcal{R}_{c_{L},i}}$

11 end if

12

13 end for

14

15 end for

return $(\mathcal{R}_{V},\mathcal{R}_{E})$

Algorithm 2 A Symmetry Finding Algorithm

We also repeat here for convenience some definitions used in the proofs. Given
a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, let

$\mathcal{V}_{c_{L}}:=\\{v\in\mathcal{V}:c_{L}=h_{v}^{L}(H)\\}$ (34)

be the set of nodes of the same class $c_{L}$ as determined by $L$-GWL-1. Let
$\mathcal{H}_{c_{L}}$ be an induced subgraph of $\mathcal{H}$ by
$\mathcal{V}_{c_{L}}$.

######  Definition B.9.

A _$L$ -GWL-1 symmetric_ induced subhypergraph
${\mathcal{R}}\subset{\mathcal{H}}$ of ${\mathcal{H}}$ is a connected induced
subhypergraph determined by
${\mathcal{V}}_{{\mathcal{R}}}\subset{\mathcal{V}}_{{\mathcal{H}}}$, some
subset of nodes that are all indistinguishable amongst each other by
$L$-GWL-1:

$h_{u}^{L}(H)=h_{v}^{L}(H),\forall u,v\in{\mathcal{V}}_{\mathcal{R}}$ (35)

When $L=\infty$, we call such ${\mathcal{R}}$ a GWL-1 symmetric induced
subhypergraph. Furthermore, if ${\mathcal{R}}={\mathcal{H}}$, then we say
${\mathcal{H}}$ is _GWL-1 symmetric_.

######  Definition B.10.

A neighborhood-regular hypergraph is a hypergraph where all neighborhoods of
each node are isomorphic to each other.

######  Observation 4.

A hypergraph ${\mathcal{H}}$ is GWL-1 symmetric if and only if it is $L$-GWL-1
symmetric for all $L\geq 1$ if and only if ${\mathcal{H}}$ is neighborhood
regular.

###### Proof.

1\. First if and only if :

By Theorem B.8, GWL-1 symmetric hypergraph
${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$ means that for every pair of
nodes $u,v\in{\mathcal{V}}$,
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{\tilde{u}}\cong_{c}({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{\tilde{v}}$.
This implies that for any $L\geq 1$,
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L})_{\tilde{u}}\cong_{c}({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L})_{\tilde{v}}$
by restricting the rooted isomorphism to $2L$-hop rooted subtrees, which means
that $h^{L}_{u}(H)=h^{L}_{v}(H)$. The converse is true since $L$ is arbitrary.
If there are no cycles, we can just take the isomorphism for the largest.
Otherwise, an isomorphism can be constructed for $L=\infty$ by infinite
extension.

2\. Second if and only if :

Let $p_{{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}$ be the universal
covering map for ${\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}$. Denote
$\tilde{v},\tilde{u}$ by the lift of some nodes $v,u\in{\mathcal{V}}$ by
$p_{{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}$.

Let $(\tilde{N}(\tilde{u}))_{\tilde{u}}$ be the rooted bipartite lift of
$(N(u))_{u}$. If ${\mathcal{H}}$ is $L$-GWL-1 symmetric for all $L\geq 1$ then
with $L=1$,
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2})_{\tilde{u}}\cong_{c}(\tilde{N}(u))_{\tilde{u}}\cong_{c}(\tilde{N}(v))_{\tilde{v}}\cong_{c}({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2})_{\tilde{v}}$,
iff $(N(u))_{u}\cong(N(v))_{\tilde{v}},\forall u,v\in{\mathcal{V}}$ since
$N(u)$ and $N(v)$ are cycle-less for any $u,v\in{\mathcal{V}}$. For the
converse, assume all nodes $v\in{\mathcal{V}}$ have
$(N(v))_{v}\cong(N^{1})_{x}$ for some $1$-hop rooted tree $(N^{1})_{x}$ rooted
at node $x$, independent of any $v\in{\mathcal{V}}$. We prove by induction
that for all $L\geq 1$ and for all $v\in{\mathcal{V}}$,
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L})_{\tilde{v}}\cong_{c}(\tilde{N}^{2L})_{x}$
for a $2L$-hop tree $(\tilde{N}^{2L})_{x}$ rooted at node $x$.

Base case: $L=1$ is by assumption.

Inductive step: If
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L})_{\tilde{v}}\cong_{c}(N^{2L})_{x}$,
we can form
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L+2})_{\tilde{v}}$ by
attaching $(\tilde{N}(\tilde{u}))_{\tilde{u}}$ to each node $\tilde{u}$ in the
$2L$-th layer of
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L})_{\tilde{v}}\cong_{c}(\tilde{N}^{2L})_{x}$.
Each $(\tilde{N}(u))_{\tilde{u}}$ is independent of the root ${\tilde{v}}$
since every $u\in{\mathcal{V}}$ has
$(\tilde{N}(\tilde{u}))_{\tilde{u}}\cong_{c}(\tilde{N}^{2})_{x}$ iff
$(N({\tilde{u}}))_{\tilde{u}}\cong(N^{1})_{x}$ for an $x$ independent of
$u\in{\mathcal{V}}$. This means
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L+2})_{\tilde{v}}\cong_{c}(\tilde{N}^{2L+2})_{x}$
for the same root node $x$ where $(\tilde{N}^{2L+2})_{x}$ is constructed in
the same manner as
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}^{2L})_{\tilde{v}},\forall
v\in{\mathcal{V}}$.

∎

#####  B.3.1 Algorithm Guarantees

Continuing with the notation, as before, let
$\mathcal{H}=(\mathcal{V},\mathcal{E})$ be a hypergraph with star expansion
matrix $H$ and let
$({\mathcal{R}}_{{\mathcal{V}}},{\mathcal{R}}_{{\mathcal{E}}})$ be the output
of Algorithm 1 on $H$ for $L\in\mathbb{N}^{+}$. Denote ${\mathcal{C}}_{c_{L}}$
as the set of all connected components of ${\mathcal{H}}_{c_{L}}$:

${\mathcal{C}}_{c_{L}}\triangleq\\{C_{c_{L}}:\text{conn. comp.
}C_{c_{L}}\text{ of }{\mathcal{H}}_{c_{L}}\\}$ (36)

If $L=\infty$, then drop the $L$. Thus, the hypergraphs represented by
$({\mathcal{R}}_{V},{\mathcal{R}}_{E})$ come from ${\mathcal{C}}_{c_{L}}$ for
each $c_{L}$. Let:

$\hat{{\mathcal{H}}}_{L}\triangleq({\mathcal{V}},{\mathcal{E}}\cup{\mathcal{R}}_{V})$
(37)

be ${\mathcal{H}}$ after adding all the hyperedges from
${\mathcal{R}}_{{\mathcal{V}}}$ and let $\hat{H}_{L}$ be the star expansion
matrix of the resulting hypergraph $\hat{{\mathcal{H}}}_{L}$. Let:

${\mathcal{G}}_{L}\triangleq\\{h_{v}^{L}(H):v\in{\mathcal{V}}\\}$ (38)

be the set of all $L$-GWL-1 values on $H$. Let:

$V_{c_{L},s}\triangleq\\{v\in{\mathcal{V}}_{c_{L}}:v\in
R,R\in{\mathcal{C}}_{c_{L}},|{\mathcal{V}}_{R}|=s\\}$ (39)

be the set of all nodes of $L$-GWL-1 class $c_{L}$ belonging to a connected
component in ${\mathcal{C}}_{c_{L}}$ of $s\geq 1$ nodes in
${\mathcal{H}}_{c_{L}}$, the induced subhypergraph of $L$-GWL-1. Let:

${\mathcal{S}}_{c_{L}}\triangleq\\{|{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}|:{\mathcal{R}}_{c_{L},i}\in{\mathcal{C}}_{c_{L}}\\}$
(40)

be the set of node set sizes of the connected components in
${\mathcal{H}}_{c_{L}}$.

######  Proposition B.10.

If $L=\infty$, for any GWL-1 node value $c$ for $\mathcal{H}$, the connected
component induced subhypergraphs $\mathcal{R}_{c,i}$, for
$i=1...|{\mathcal{C}}_{c}|$ are GWL-1 symmetric and neighborhood-regular.

###### Proof.

Let $p_{{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}$ be the universal
covering map for ${\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}$. Denote
$\tilde{v},\tilde{u},\tilde{v}^{\prime},\tilde{u}^{\prime}$ by the lift of
some nodes $v,u,v^{\prime},u^{\prime}\in{\mathcal{V}}$ by
$p_{{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}$.

Let $L=\infty$ and let $\mathcal{H}_{c}=(\mathcal{V}_{c},\mathcal{E}_{c})$.
For any $i$, since $u,v\in\mathcal{V}_{c}$,
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{u}\cong_{c}({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{v}$
for all $u,v\in\mathcal{V}_{\mathcal{R}_{c,i}}$. Since ${\mathcal{R}}_{c,i}$
is maximally connected we know that every neighborhood
$N_{{\mathcal{H}}_{c}}(u)$ for $u\in{\mathcal{V}}_{c}$ induced by
${\mathcal{H}}_{c}$ has $N_{{\mathcal{H}}_{c}}(u)\cong
N(u)\cap{\mathcal{H}}_{c}$. Since $L=\infty$ we have that
$N_{{\mathcal{H}}_{c}}(u)\cong N_{{\mathcal{H}}_{c}}(v),\forall
u,v\in{\mathcal{V}}_{R_{c,i}}$ since otherwise WLOG there are
$u^{\prime},v^{\prime}\in{\mathcal{V}}_{R_{c,i}}$ with
$N_{{\mathcal{H}}_{c}}(u^{\prime})\not\cong N_{{\mathcal{H}}_{c}}(v^{\prime})$
then WLOG there is some hyperedge
$e\in{\mathcal{E}}_{N_{{\mathcal{H}}_{c}}(u^{\prime})}$ with some $w\in e$,
$w\neq u^{\prime}$ where $e$ cannot be in isomorphism with any
$e^{\prime}\in{\mathcal{E}}_{N_{{\mathcal{H}}_{c}}(v^{\prime})}$. For two
hyperedges to be in isomorphism means that their constituent nodes can be
bijectively mapped to each other by a restriction of an isomorphism $\phi$
between $N_{{\mathcal{H}}_{c}}(u^{\prime}),N_{{\mathcal{H}}_{c}}(v^{\prime})$
to one of the hyperedges. This means that
$({\tilde{\mathcal{B}}_{{\mathcal{V}}\setminus\\{u^{\prime}\\},{\mathcal{E}}}})_{w}$
is the rooted universal covering subtree centered about $w$ not passing
through $u^{\prime}$ that is connected to
$u^{\prime}\in({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{u^{\prime}}$
by $e$. However, $v^{\prime}$ has no $e$ and thus cannot have a $T_{x}$ for
$x\in{\mathcal{V}}_{(\tilde{N}(v^{\prime}))_{v}}$ satisfying
$T_{x}\cong_{c}({\tilde{\mathcal{B}}_{{\mathcal{V}}\setminus\\{u^{\prime}\\},{\mathcal{E}}}})_{w}$
with $x$ connected to $v^{\prime}$ by a hyperedge $e^{\prime}$ isomorphic to
$e$ in its neighborhood in
$(\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}})_{v^{\prime}}$. This
contradicts that
$({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{u^{\prime}}\cong_{c}({\tilde{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}})_{v^{\prime}}$.

We have thus shown that all nodes in ${\mathcal{V}}_{c}$ have isomorphic
induced neighborhoods. By the Observation 4, this is equivalent to saying that
${\mathcal{R}}_{c,i}$ is GWL-1 symmetric and neighborhood regular. ∎

######  Definition B.11.

A star graph $N_{x}$ is defined as a tree rooted at $x$ of depth $1$. The root
$x$ is the only node that can have degree more than $1$.

######  Lemma B.11.

If $L\in\mathbb{N}^{+}$ is small enough so that after running Algorithm 1 on
$L$, for any $L$-GWL-1 node class $c_{L}$ on ${\mathcal{V}}$ none of the
discovered $\mathcal{V}_{\mathcal{R}_{c_{L},i}}$ are within $L$ hyperedges
away from any $\mathcal{V}_{\mathcal{R}_{c_{L},j}}$ for all $i,j\in
1...|{\mathcal{C}}_{c_{L}}|,i\neq j$, then after forming
$\hat{{\mathcal{H}}}_{L}$, the new $L$-GWL-1 node classes of
$\mathcal{V}_{\mathcal{R}_{c_{L},i}}$for $i=1...|{\mathcal{C}}_{c_{L}}|$ in
$\mathcal{\hat{H}}_{L}$ are all the same class $c^{\prime}_{L}$ but are
distinguishable from $c_{L}$ depending on
$|\mathcal{V}_{\mathcal{R}_{c_{L},i}}|$.

###### Proof.

After running Algorithm 1 on ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$,
let
$\hat{{\mathcal{H}}}_{L}=(\hat{{\mathcal{V}}}_{L},\hat{{\mathcal{E}}}_{L}\triangleq{\mathcal{E}}\cup\bigcup_{c_{L},i}\\{{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}\\})$
be the hypergraph formed by attaching a hyperedge to each
${\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$.

For any $c_{L}$, a $L$-GWL-1 node class, let
$\mathcal{R}_{c_{L},i},i=1...|{\mathcal{C}}_{c_{L}}|$ be a connected component
subhypergraph of $\mathcal{H}_{c_{L}}$. Over all $(c_{L},i)$ pairs, all the
$\mathcal{R}_{c_{L},i}$ are disconnected from each other and for each $c_{L}$
each $\mathcal{R}_{c_{L},i}$ is maximally connected on
${\mathcal{H}}_{c_{L}}$.

Upon covering all the nodes ${\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$ of each
induced connected component subhypergraph $\mathcal{R}_{c_{L},i}$ with a
single hyperedge $e={\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$ of size
$s=|\mathcal{V}_{\mathcal{R}_{c_{L},i}}|$, we claim that every node of class
$c_{L}$ becomes $c_{L,s}$, a $L$-GWL-1 node class depending on the original
$L$-GWL-1 node class $c_{L}$ and the size of the hyperedge $s$.

Consider for each $v\in{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$ the $2L$-hop
rooted tree
$({\tilde{\mathcal{B}}^{2L}_{{\mathcal{V}},{\mathcal{E}}}})_{\tilde{v}}$ for
$p_{{\mathcal{B}}_{{\mathcal{V}},{\mathcal{E}}}}(\tilde{v})=v$. Also, for each
$v\in{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$, define the tree

$T_{e}\triangleq({\tilde{\mathcal{B}}^{2L-1}_{\hat{{\mathcal{V}}}\setminus\\{v\\},\hat{{\mathcal{E}}}}})_{\tilde{e}}$
(41)

We do not index the tree $T_{e}$ by $v$ since it does not depend on
$v\in{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$. We prove this in the following.

proof for: $T_{e}$ does not depend on
$v\in{\mathcal{V}}_{{\mathcal{R}}_{c_{L},i}}$:

Let node $\tilde{e}$ be the lift of $e$ to
$({\tilde{\mathcal{B}}^{2L-1}_{\hat{{\mathcal{V}}},\hat{{\mathcal{E}}}}})_{\tilde{e}}$.
Define the star graph $(N(\tilde{e}))_{\tilde{e}}$ as the 1-hop neighborhood
of $\tilde{e}$ in
$({\tilde{\mathcal{B}}^{2L-1}_{\hat{{\mathcal{V}}},\hat{{\mathcal{E}}}}})_{\tilde{e}}$.
We must have:

$({\tilde{\mathcal{B}}^{2L-1}_{\hat{{\mathcal{V}}},\hat{{\mathcal{E}}}}})_{\tilde{e}}\cong_{c}((N(\tilde{e}))_{\tilde{e}}\cup\bigcup_{\tilde{u}\in{\mathcal{V}}_{N({\tilde{e}})}\setminus\\{\tilde{e}\\}}({\tilde{\mathcal{B}}^{2L-2}_{{{\mathcal{V}}},{{\mathcal{E}}}}})_{\tilde{u}})_{\tilde{e}}$
(42)

Define for each node $v\in e$ with lift $\tilde{v}$:

$(N(\tilde{e},\tilde{v}))_{\tilde{e}}\triangleq({\mathcal{V}}_{(N(\tilde{e}))_{\tilde{e}}}\setminus\\{\tilde{v}\\},{\mathcal{E}}_{(N(\tilde{e}))_{\tilde{e}}}\setminus\\{(\tilde{e},\tilde{v})\\})_{\tilde{e}}$
(43)

The tree $(N(\tilde{e},\tilde{v}))_{\tilde{e}}$ is a star graph with the node
$\tilde{v}$ deleted from $(N(\tilde{e}))_{\tilde{e}}$. The star graphs
$(N(\tilde{e},\tilde{v}))_{\tilde{e}}\subset(N(\tilde{e}))_{\tilde{e}}$ do not
depend on $\tilde{v}$ as long as
$\tilde{v}\in{\mathcal{V}}_{(N(\tilde{e}))_{\tilde{e}}}$. In other words,