Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking
Authors: Simon Zhang
Cheng Xin
Tamal K. Dey
Venue: Accepted by TMLR ()

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 (WL-1) algorithm. The WL-1 algorithm can approximately decide whether two graphs are isomorphic. However, GWL-1 has limited expressive power. In fact, GWL-1 can only view the hypergraph as a collection of trees rooted at each of the nodes in the hypergraph. Furthermore, message passing on hypergraphs can already be computationally expensive, particularly with limited GPU device memory. To address these limitations, we devise a preprocessing algorithm that can identify certain regular subhypergraphs exhibiting symmetry with respect to GWL-1. Our preprocessing algorithm runs once with the time complexity linear in the size of the input hypergraph. During training, we randomly drop the hyperedges of the subhypergraphs identifed by the algorithm and add  covering hyperedges to break symmetry. We show that our method improves the expressivity of GWL-1. Our extensive experiments 1 also demonstrate the effectiveness of our approach for higher-order link prediction on both graph and hypergraph datasets with negligible change in computation.

Published in Transactions on Machine Learning Research (11/2024)
Expressive Higher-Order Link Prediction through Hyper- graph Symmetry Breaking
Simon Zhang
zhan 125 220puuuuee.c edu
Department of Computer Science
Purdue University
Cheng Xin
rulgges edu
Department of Computer Science Rutgers Universiby
Tamal K. Dey
tamaldeySpurdue.com edu
Department of Compuler Science Purdue Universily
Reviewed on OpenReview: https: openreview. net/ forum? id= oG655
?
-yy
scallions
choose
choese
predict: {parm. cheese, mozz. cheese, sauce, scallions]
chicken gingor
Nce peppers a
a
are indistinguishable by GWL-1 8; node isomrrphimm classes
curry unioqg
salaum butter
pasta
la
at
Figure 1: An illustration of hypergraph of recipes. The nodes are the ingredients and the hyperedges are the recipes. The task of higher order link prediction is to prodict hyperedges in the hypergraph. A negative hyperedge sample would the dotted hyperedge. The Asian ingredient nodes (a) and the European ingredient nodes (3) form two separate isomorphism classes. However, GWT-1 cannot. distinguish between these classes and will predict false positive for the negative sample.
Abstract
A hypergraph consists of 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 miss- ing 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 isomor- phism. Many existing hypergraph representation learners, are bounded expressive power by the Generalized Weisfeiler Lehman-1 (GWL-1) algorithm, generalization of the Weis- feiler Lehman-1 (WL-1) algorithm. The WL-1 algorithm can approximately decide whether two graphs are isomorphie. However, GWL-1 has limited expressive power. In fact, GWL-1 can only view the hypergraph as a collection of trees rooted at cach of the nodes in the hypergraph. Furthermore, message passing on hypergraphs can already be computationally expensive, particularly with limited GPU device memory. To address these limitations, we devise a preprocessing algorithm that can identify certain regular subhypergraphs exhibit- ing symmetry with respect to GWL-1. Our preprocessing algorithm runs once with the time complexity linear in the size of the input hypergraph. During training, randomly

---

Published in Transactions on Machine Learning Research (11/2024)
drop the hyperedges of the subhypergraphs identifed by the algorithm and add covering hyperedges to break symmetry. We show that our method improves the expressivity of GWL-1. Our extensive experiments also demonstrate the effectiveness of our approach for higher-order link prodiction on both graph and hypergraph datasets with negligible change in computation.
1 Introduction
Hypergraphs can model complex relationships in rcal-world networks, extending beyond the pairwise con- nections captured by traditional graphs. Figure [ is an example hypergraph consisting of recipes of two different types of dishes, which are largely determined by the ingredients to be used. In this hypergraph; the hyperedges are the recipes, and the nodes are the ingredients used in each recipe. The Asian recipes are presented in the right part of the figure, which consist of combinations of the ingredients of soy sauce, scallions, rice, peppers, chicken, ginger, curry and onions. The European recipes are presented in the left part of the figure, which consist of combinations of the ingredients of Parmesan cheese, mozzarella cheese, salami, butter, eggs, and pasta.
Hypergraphs have found applications in diverse fields such as recommender systems Lü et al. 2012). visual classification Feng et al. (2019). and social networks Li al. (2013). Higher-order link prediction is the task of predicting missing hyperedges in hypergraph. For this task, when the hypergraph is unattributed, it is important to respect the hypergraph's symmetries, or automorphism group. This brings about challenges to learning an expressive view of the hypergraph.
A hypergraph neural network (hyperGNN) is any neural network that learns on a hypergraph. This is in analogy to a graph neural network (GNN), which is a neural network that learns on a graph. Many existing hyperGNN architectures follow a computational message passing model called the Generalized Weisfeiler Lehman-1 (GWL-1) algorithm Huang & Yangl (2021), hypergraph isomorphism testing approximation scheme. GWT-1 is a generalization of the message passing algorithm called Weisfeiler Lehman-1 (WT-1) algorithm Weisfeiler & Leman (1968) used for graph isomorphism testing.
GWL-1, like WL-1 on graphs, is limited in how well it can express its imput. Specifically, by viewing a hypergraph as a collection of rooted trees, GWL-1 loses topological information of its input hypergraph and thus cannot fully recognize the symmetrics, or automorphism group, of the hypergraph. In fact, the hyperGNN views the hypergraph as having positvvositive symmetriiss. For a task like transductive hyperlink prediction, this can result in predicting false-positive hyperlinks as shown in Figure [ Furthermore, such issue can become even worse during test time since the automorphism group of the hypergraph might change. It is thus important to find a way to improve the expressivity of existing hyperGNNs.
Let a hypergraph H. = EV,E) denote a pair where V is a set of nodes and & C 2", a collection of subsets of V, indexes a set of hyperedges. GWI-1 views a hypergraph as a collection of trees rooted at the nodes. These rooted trees are formed by viewing each node-hyperedge incidence as an edge and recursively expanding about the nodes and hyperedges alternately. As an example of the GWT.1 algorithm, one step of GWT-1 would output a collection of depth 1 trees rooted at each node where leaves are the incident hyperedges of each node. Two steps of GWL-1 would output a collection of depth 2 trees where the depth 1 trees of one step of GWL-1 have their leaves expanded with the incident nodes of the hyperedges the new leaves. This leaf expansion process can be repeated, alternating nodes and hyperedges. This is the recursive expansion of the GWL-1 algorithm.
We can recover hyperGNNs by expressing the computation of GWL-1 as a matrix equation. Parameterizing the expression with learnable weights, GWI-1 becomes a neural network, called a hypergraph neural network (lyperGNN), similar to graph neural networks (GNN)s. In practice this is implemented through repeated sparse matrix multiplication.
Computing on hypergraph can also be very expensive. The subsets e E E that contain a node v E V form the neighborhood of v E V. This means just the neighborhood size of the nodes in hypergraphs can
httpp:://githhb.ccmm http:://hh...tllooooommee/e///pa
2

---

Published in Transactions on Machine Learning Research (11/2024)
grow exponentially with the number of nodes of the hypergraph. Thus, computationally more expensive message passing scheme over GWT-1 based hyperGNNs may bring difficulties.
In order to address the issue of the expressivity of hyperGNNS for the task of hyperlink prediction while also respecting the computational complexity of computing on a hypergraph, we devise a method that selectively breaks the symmetry of the hypergraph topology itself coming from the limitations of the hyperGNN archi- tecture. Our method is designed as an efficient 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, do not increase the computational complexity of training.
Similar to a substructure counting algorithm Bouritsas et al. (2022), , we identify certain symmetries in in- duced subhypergraphs. However, unlike in existing work where node altributes are modified, such as random noise being appended to the node attributes Sato et al. (2021), we directly target and modify the symmetries in the topology. This limits the space for augmentation, which can prevent extreme perturbations of the data. The algorithm identifies a cover of the hypergraph by disjoint connected components whose nodes are indistinguishable by GWL-1. During training, we randomly replace the hyperedges of the identified sym- metric regular induced subhypergraphs with single hyperedges that cover the nodes of each subhypergraph. We show that our method of hyperedge hallucination to break symmetry can increase the expressivity of existing hypergraph neural networks both theoretically and experimentally.
Contributions. In the context hypergraph representation learning and hyperlink prediction, we have a method that can break the symmetries introduced by conventional hypergraph hypergraph neural networks are based the GWT.11 algorithm on hypergraphs. However, the GWT-1 algorithm on hypergraphs views the hypergraph as collection of rooted trees. This introduces false positive symmetries. We summarize our contributions in this work as follows:
hyypegggap neural networks. Conventional
Provide a formal analysis of GWL-1 on hypergraphs from the perspective of algebraic topol- ogy. Our analysis offers a novel characterization of the expressive power and limitations of GWL-1. By leveraging concepts from algebraic topology, we establish a precise connection between GWL-1 and the universal covers of hypergraphs, providing deeper insights into the algorithm's behavior on complex hypergraph structures.
Devise an efficient hypergraph preprocessing algorithm to identify false positive symmetries of GWL-1. We propose linear time preprocessing algorithm to identify specific regular subhyper- graphs that exhibit symmetry with respect GWL-1, which are potential sources of expressivity limitations.
Introduce a data augmentation scheme that leverages the preprocessing algorithm's output improve GWL-1's expressivity. During training, we randomly modify the hyperedges of the iden- tified symmetric subbypergraphs, effectively breaking symmetries that GWL-1 cannot distinguish. This approach enhances the model's ability to capture fine-grained structural information without significantly increasing computational complexity.
Provide formal analysis and performance guarantees for our method. We rigorously prove how our approach improves the expressivity of GWL-1 under certain conditions. These theoretical results offer valuable insights into the circunstances under which our method can enhance hyper- graph representation learning, providing a solid foundation for its practical application.
Perform extensive experiments on real-world datasets to demonstrate the effectiveness of our approach. Our comprehensive evaluation spans various hypergraph and graph datasets, showcasing consistent improvements across different hypergraph neural network architectures for higher-order link prediction tasks. These empirical results validate the practical utility of our method and its ability to enhance existing models with minimal computational overhead.
2 Background
The following notation is used throughout the paper:
3

---

Published in Transactions on Machine Learning Research (11/2024)
Let N a (0.1,..))22 {..., and real numbers respectively. Let [n] (1....,m C z+ denote the integers from 1 to E Z+.
-,,,,,,,, _ {1,.... and I denote the naturals, integers, positive integers,
For a set A, let (+) denote the set of all subsets of A of size k. Given the set A, multiset is defined 1. A submultiset B S Á is defined by
by A a mA, B & (B,m) m') with B S A and m'(e) S m(e), Ve E B. A multiset with its elements explicitly enumerated with the double curly brace notation: {a, a, a...... The cardinality of a multiset A, is defined as |Á] - &EEA m(e). For two multisets À (A, B (B) we may define their multiset sum by ÁU & (AUB, MAUB MA mB).
A + zt. A set is also multiset with
For two pairs of multisets Ā = (Á1, 12). = (B), B2), denote their multiset sum by their elementwise multiset sum: AUB (A, (A, L. B1, Ag u B2). Similarly, for two pairs of sets A = (A1, = (B1, B2), denote their union by their elementwise union: AUB é (A1 U B1, A2 U B2).
Let P: A t)); t) denote a probability distribution parameterized by R. The distribution Pt has some domain D, which we denote by dom(P.). The notation supp(P:) 2 {ær dom(P.) P.(x) > 0} denotes the support of a distribution P..
A Bernoulli distribution P, A P(X:p) is probability distribution parameterized by 0 < 1 with the following definition:
k=1 = =)( 1 k=0
(1)
The random variable Bernoulli(p) Pp called Bernoulli random variable.
2.1
Group Theory
To better study hypergraphs, we use some concepts group theory. Here we give a brief introduction to some of them. For more details, see Dummit & Foote (2004).
Definition 2.1. A group G is a set equipped with a binary operation % that satisfies the following four properlies:
1. Closure: For every o, b E G, the result of the operation a * is also in G.
Associativity: For every a, b, E G, (a * b) * = a * (b c).
3. Identity Element: There crists an element G such that for every E G, e axc=======
4. Inverse Element: For each a E G, there exists an element b E G such that a * b b e (such element b is unique for a and is often denoled as a-1.
Permutation Groups A permulation group is group where the elements are permutations of a set, and the group operation is the composition of these permutations. Permutations are bijective functions that rearrange the elements of a set.
Group Isomorphism and Automorphism Two groups G and H are called isomorphic if there exists a bijective function Φ : G + such that for all a, E G, ø(a * b) = p(a) * @(b). This means that G and H have the same group structure, even if their elements are different. Such bijective funtions are called isomorphisms. Tf G H, isomorphism to group itself is called an automorphism. The set of all automorphisms of group G forms group, with group operations given by compositions. Such group is called the aulomorphism group of G, denoted as Aul(G).
Group Action A group action is a formal way in which group G operates on set X. Formally, a group action is a map G x + (denoted (g,z) > x) that satisfies the following two properties:
1. For all X, where is the identity element in G.
4

---

Published in Transactions on Machine Learning Research (11/2024)
2. For all h h G and z E X, (gh) g (h.2).
Group actions are useful for studying the symmetry of objects, as they describe how the elements of a group move or transform the elements of a set.
Stabilizer In the context of group actions, the stabilizer of an element x in a set X (where a group G acts on X) is the set of elements G that leave x fixed. Formally, the stabilizer of in is given by:
Stobo (x) - to E -g-x=xx
2.2 Isomorphisms on Higher Order Structures
In this section, we go over what a hypergraph is and how this structure represented as tensors. We then define what a hypergraph isomorphism is.
A hypergraph is a generalization of graph. Hypergraphs allow for all possible subsets over set of vertices, called hyperedges. We can thus formally define a hypergraph as:
Definition 2.2. An undirected hypergraphs is a pair H = (V, E) consisting of a set of verlices V and a set of hyperedges & c 2 where 2 is the power set of the verter set V.
For a given hypergraph H = (V,E), a hypergraph G = (V',8) is subhypergraph of H. if V S V and 8' CE.
A subhypergraph induced by W C V is defined (W 2 NE). Similarly, for a subset of hyperedges F C E, subhypergraph induced by F is defined as (U,
For a given hypergraph H. we also use VH and Ex to denote the sets of vertices and hyperedges of H. respectively. According to the definition, a hyperedge is nonempty subset of the vertices. 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,, hypergraph can include some symmetries that are captured by isomorphisms. These isomorphisms are defined by bijective structure preserving maps.
Definition 2.3. For two hyperyraphs H and D, structure preserving map p: H + D is a puir of maps p (pv: : Vn + VD. ps En + Ex) such that ve E En, pe(e) & {pv(v)) is e Ep. A hypergraph isomorphism is a structure preserving map p = (pv, such that both pv and Pe are bijective. Two hypergraphs are said to be isomorphic, denoted as H D, if there exists an isomorphism between them. When H = D, an isomorphism p is called an automorphism on H. All the automorphisms form a group, which we denote as AH)(
A graph isomorphism is the special case of a hypergraph isomorphism between 2-uniform hypergraphs according to Definition 2.3
A neighborhood (v) & (Unce e, fe: E e)) of node v E V of a hypergraph 7 = (V,E) is the subhypergraph of H induced by the set of all hyperedges incident to v. The degree of u is denoted deg(v) = (Ex())-- A degree vector of a node of is defined as: (vg (Ife: e 3 v, le| = =H))
A simple but very common symmetric hypergraph of importance to our task, namely the neighborhood- regular hypergraph, or just regular hypergraph.
Definition 2.4. A neighborhood--eguua hypergroph is hypergraph where all neighborhoods of each node are isomorphic to each other.
A d-uniform neighborhood of o is the set of all hyperedges of size d in the neighborhood of v. Thus, in a neighborrhood-regilar hypergraph, all nodes have their d-uniform neighborhoods of the same cardinality for all d E N.
Representing Higher Order Structures as Tensors: There are many data stuctures one can define on higher order structure like hypergraph. An n-order tensor Maron et al. (2018). as generalization of
5

---

Published in Transactions on Machine Learning Research (11/2024)
adjacency matrix on graphs can be used to characterize the higher order connectivities. For simplicial complexes, which are hypergraphs where all subsets of hyperedge are also hyperedges, Hasse diagram, which is a multipartite graph induced by the poset relation of subset amongst hyperedges, or simplices, differing in exactly one node, 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.5 (star expansion bipartite graph). Given hypergraph H (V,E), the star expansion bipar- tite graph By,g is the bipartite graph with vertices V and edges {(v,e) E V x & e).
Definition 2.6. The star exponsion incidence mabria H of hypergraph H (V,E) is the [V] x 2 0-1 incidence matric H where H..e = iff for (v.e) E V x E for some fixed orderings on both V and 2
In practice, as data to machine learning algorithms, the matrix is sparsely represented by its nonzero entries.
To study the symmetries of a given hypergraph H. (V,E), we consider the permutation group on the vertices V, denoted as Sym(V), which acts jointly the rows and columns of star expansion adjacency matrices. We assume the rows and columns of star expansion adjacency matrix have some canonical ordering, say lexicographic ordering, given by some prefixed ordering of the vertices. Therefore, each hypergraph H. has a unique canonical matrix representation H.
We define the action of a permutation π E SVm(V) on a star expansion adjacency matrix H:
(t H) _,== e= (M Hg-1(1)) (0))
(2)
Based on the group action, consider the stabilizer subgroup of Sym(V) on an incidence matrix H:
Sta = { Sym(V) | π H H}
(3)
For simplicity we omit the lower index of Sym(V) when the permutation group is clear from context. Tt can be checked that Stab(Hf) S Sym(V) is subgroup. Intuitively, Stab(11) consists of all permutations that fix H. These equivalent to hypergraph automorphisms the original hypergraph H.
Proposition 2.1. (H) = Slab(HH) equivalent as isomorphic groups.
We can also define a notion of isomorphism between k-node sets using the stabilizers on H. Definition 2.7. For a given hyperyyrph H with slar erpansion matris H, two k-node sets S,T C V are called isomorphic, denoted as S = T, if 3r E Stab(H) x(S) = T
Such isomorphism is an equivalance relation on k-node sets. When k = 1, we have isomorphic nodes, denoted u 2 for u, E V. Node isomorphism also studiod as the so-called structural equivalence Lorrain & White (1971). Furthermore, when S ~z T we can then say that there matching due to the graph of the S}. This matching is between the node sets S and T that matched
map of the form ((sT((s) nodes are isomorphic.
2.3 Invariance and Expressivity
For given hypergraph H = =VVE), want to do hyperedge prediction on H, which is to predict missing hyperedges from k-node sets for k 2 2. Let [V] |1| = m, and H znx²" be the star expansion adjacency matrix of H. To do hyperedge prediction, 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 k-node representation that is injective on k- node set isomorphism classes from H. We break up the definition of most-expressive k-node representation into possessing two properties, as follows:
study k-node representations g (2) x Znx2" Re that map
Definition 2.8. Let g (2) Z . be a k-node representation on a hapergraph H. Let H E Z Zux2" be the star expansion adjacency matrix of H. for nodes. The representation g k-node most expressive if SS C V, |S| = S = k the following two conditions are satisfied:

---

Published in Transactions on Machine Learning Research (11/2024)
1. g is k-node invariant: 3r at() S
H) g k-node expressive ße E Stab H x(5) S' g H) + g(S 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 k-sized hyperedges
set of k nodes.
We can also define the symmelry group of a k-node representation map 9 on H as the set of all permutations on V that make the representation map k-node invariant. This is formally defined below:
Definition 2.9. For g (x) Z2x2" T k-node representation
hypergraph H.
Sy)( e { E Sym(V) VS,S' E (H) (() = - =($"
(4)
2.4 Generalized Weisfeiler-Lhmann
We describe a generalized Weisseiler-Tehhman-1 (GWT-11) hypergraph isomorphism test similar to Huang Yang (2021); Feng al. (2023) based on the WL-1 algorithm for graph isomorphism testing. There have
been many parameterized variants of the GWL-1 algorithm implemented as neural networks, see Section 3
Let H be the star expansion matrix for hypergraph H. We define the GWT-1 algorithm as the following two step procedure on H at iteration number 2 0.
+ 0,,1+ +
fett + ((fee WyDree Ve E (x(l h +- ((h, se+1) Breer Vo E Vx(H))
(5)
This is slightly different from the algorithm presented in Huang & Yang 2021 at the f update step. Our update step involves edge representation f2, 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 (H) and (H) as the hyperedge and node ith ileration GWL-1, called i-GLL-1, values on an unattributed hypergraph H with star expansion H. If GWL-1 is run to convergence then we omit the itcration number i. We also mean this when we say =0.
For a hypergraph H with star expansion matrix H, GWT-1 is strictly more expressive than WT-1 A = H D-1 HJ with D. diag(II". 1,), the node to node adjacency matrix, also called the clique expansion of H. This follows since triangle with its 3-cycle boundary: T and a 3-cycle C3 have exactly the same clique expansions. Thus WL-1 will give the same node values for both T and C3. GWL-1 on the star expansions Hy and Hc,, on the other hand, will identify the triangle as different from its bounding edges.
Let ('H A (H), Sin (H) and (H) A [N',, (H),... ,4,, (H)) be two vectors whose entries are ordered by the column and row order of H, respectively.
Proposition 2.2. The update sleps ('H and (H) of GWL-1 are permatation equinariant; For any и Sym(V), let: क (-) & (x-1(e)) (H),... S (z-1(en)( and π - (H) [h(-)(.,)(1)) (H). h (I1)]:
WEN,, (HH = ("( H), n (H))) = hm(m (m H)
(6)
Define the operator AGG as k-set map to representation space gd. Define the following representation of a k-node subset S C V of hypergraph H with star expansion matrix H:
h*(S, H) A (GG
(7)
where (H) is the node value of i-GWL-1 on H for node v. The representation h(S, H) preserves hyperedge isomorphism classes shown below:
7

---

Published in Transactions on Machine Learning Research (11/2024)
Proposition 2.3. Let H) (H) with an injective AGG map. The representation WSS,, H) is k-node invoriant. but. not necessarily k-node expressive for S set of k modes.
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 node reprosentations (H) are also paramctorizod and rewritten into a message passing hypergraph neural network with matrix equations Huang & Yang (2021). For example, the HNHN Dong et al. (2020) hyperGNN architecture can be viewed parameterization of GWL-1:
x (H x Wh bg)) x(+1) = o (HX w bb))
(8)
where a is a nonlinearity, X are vector representations of h'(H) and ('H)) respectively, and WE, Wr, by, by are learnable weight matrices. Selting 600² 0, 0, 0, we maintain permutation equivari- ance in Proposition 2.2 Furthermore, the HNHN equations of Equation g become in direct analogy to the steps of GWL-1 from Equation 5
3 Related Work and Existing Issues
There are many hyperlink prediction methods. Most message passing based methods for hypergraphs are basod on the GWL-1 algorithm. These include [Haang & Yang (2021); Yadati al. (2019); Feng et al.)
2019 ; Gao al.
[022]; |:
Dong et. al. 22020 Srinivasan et al. 2021 Chien al. (2022) Zhang al. (2018).
Examples of message passing based approaches that incorporate positional encodings hypergraphs include
SNALS Wan et al.
2021). The paper Zhang et al. (201 uses pair-wise node attention mechanism to do
higher order link prediction. For survey on hyperlink prediction, see Chen & Liu (002)).
Varions methods have been proposed to improve the expressive power of GNNs due to symmetries in graphs. In Papp & Wattenhofer (2022), substructure labeling 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.
2023 Wijesinghe & Wang (2021). All of the previously mentioned methods depend on a fixed subgraph radius size. This prevents capluring symmetries that span long ranges across the graph. Zhaang 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.
(203bb) and encoding substructures Zeng et al.
Cycles are a common symmetric substructure. There are many methods that identify this symmetry. Cy2C Choi al. is a method that encodes cycles to cliques. It has the issue that if the the cycle-bast, 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 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 Zhhnng et. al. (2022) For more related work, see the Appendix.
Data augmentation is commonly used approach to improve robustness to distribution shifts Yao et al.) (2022b), recognize symmetries Chen et al. (2020b), and handle data imbalance Chawla et al. (0022). In the graph domain, a priori knowledge of the data distribution can inform rule-based data augmentations. In molecular classification, prior knowledge of the physical meaning of the data can be used to augment graphs Sun et al. (2021). Data augmentations can also be learned through data generation methods. For example a link prediction neural network GAE Kipf & Welling (2016b) can be used to propose edges improve node classification Zhao et al. (2021). For a survey on graph data augmentation, see Zhao et al. 2022).
8

---

Published in Transactions on Machine Learning Research (11/2024)
4 A Characterization of GWL-1
A hypergraph can be represented by bipartite graph By,g from V to & 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 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 two nodes in any graph with the same color are connected by edge. We define a 2-colored isomorphism formally here:
Definition 4.1. A 2-colored isomorphism is graph isomorphism on two 2-colored graphs that preserves node colors. It is denoted by =
A 2-colored isomorphism from graph G to itself is called 2-colored automorphism. The set of all 2-colored automorphisms on G is denoted (G).
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 hyperodge partition. See Figure a[a) as an example. We let By, Be be the red and blue colored nodes in By,g respectively.
Proposition 4.1. We have two hypergraphs (11, E22, iff Bv, _ Bv where By is the stor exponsion bipartite graph of E.)
We define topological object for a graph originally from algebraic topology called a universal cover: Definition 4.2 (Hatcher (2005)). The universal covering of connected graph G is a (potentially infinite) groph G logether with map pa G++ G such that:
1. Vo E V(G), palN(a)) is an isomorphism onto N (p)(
G is simply connected (a tree)
We call such Pa the universal covering map and G the universal cover of G. A covering graph is a graph that satisfies property but not necessarily in Definition 4.2 The universal covering & is essentially unique Hatcher (2005) in the sense that it can cover all connected covering graphs of G. Furthermore, define rooted isomorphism G2 z Hy as an isomorphism between graphs G and H that maps to y and vice versa. Let G¹²² denote the rooted universal cover G2 with every leaf of depth (number of edges) exactly i E Z+. It is a known result. that:
Theorem 4.2. Krebs & Verbitsky [2015)] Let G and H be two connected graphs. Let PC G + G.PH H + H be the universal covering maps of G and H respectively. For any E N, for any two nodes x E G and y E H: G = G3 ilf the WL-1 algoritlem assigns the same value to nodes x = pā( and y = (
We generalize the second result stated above about a topological characterization of WL-1 for GWT-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 By to a 2-colored tree universal cover By.g where the red/ /luue nodes of By,g are lifted to red/blue nodes in By,g. Furthermore, the labels 0 are placed on the blue nodes corresponding to the hyperedges in the lift and the labels () are placed on all its corresponding red nodes in the lift. Let (B. denote the k-hop rooted 2-colored subtree By,g with root ă and ps.,s (ō) = x for any I E (By.e).
Theorem 4.3. Let Hi E)) and H2 (V2, be two connected hypergraphs. Let By and By be two canonically colored bipartite graphs for Hi and H2 (vertices colored red and hyperedges colored blue). Let pBv,.s, Bv + B PBuzez By2 + By be the universal coverings of By Es and By respectively. For any i Zt, for any of the nodes Iι E By e1 E Be, and x2 E By, E Be,
(189-1) =e (BV2,,)) )zz il' Se =fe
9

---

Published in Transactions on Machine Learning Research (11/2024)
(Bog) 2.3 c2
(Beg
(Bog
(B 2011234
Wic
e'o.1
17.
50.13
61,2,
$1.28
PB
PB c
PB cg
PB
824
50,2,,
6'0,3,
G
waa
13
6'0,,,
50,1,2,3
3.0
B B
C (V,E (b)
C
EV,
Cg V E (d)
C (V 8 ((V)) (e)
(a)
(f)
Figure 2: An illustration of hypergraph symmetry breaking. (c,d) 3-regular hypergraphs C₁, Cg with and 5 nodes respectively and their corresponding universal covers centered at any hyperedge (Bog )e..... (Bog) ).........
with universal covering maps PB (b,e) the hypergraphs C1. Cg which are Ca, C3 with 5-sized hyperedges attached them and their corresponding universal covers and universal covering maps. (a.f) are the corresponding bipartite graphs of Ö2, Cg. (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
(i )8 =e (B2)
E) iff h h22-
with fa, hi the ith GWL-1 values for the hyperedges and nodes respectively where = PBv (ē1), 21 pB (T1), e2 eB (62), I2 PBv,.e, (ā2).
Theorem 4.3 states that a 2-colored isomorphism is maintained during each step of the GWL-1 algorithm. Thus we can view the GWT.-1 algorithm on a hypergraph as equivalent computing a universal cover of the star expansion bipartite graph up to 2-colored isomorphism. We can thus deduce from Theorems 4.3 4.2 that GWL-1 reduces to computing WL-1 the bipartite graph up the 2-colored isomorphism.
Corollary 1. Let H, = &V),e) and Hi (V2, E2) be two connected hyperryophs. Let By and By be laoo canonically colored bipartûle graphs for Hi and Hz (vertices colored red and hyperedgee colored blue). Let PBv By, + Ev, Bys + Br be the universal coverings of By and By respectively. For any iegie2. Z",
(B) = (B)r iff g = gi.
with ghn Si the i-th WL-1 values for 02 E (B V(Bv,,s) respectively where vn = PBv, (01), 12 = PBv, Sg (Tz).
See Figure 2 for an illustration of the universal covering of the corresponding bipartite graphs for two 3-uniform neighborhood regular hypergraphs.
4.1 A Limitation of GWL-1
Due to the equivalence of GWL-1 to viewing the hypergraph H. as a collection rooted trees, we can show that the automorphism group of H is a subgroup of the automorphism of this collection of rooted trees. This is stated in the following proposition:
Theorem 4.4. Let h+ [V]² x z Rd be the L-GWL-1 representation of nodes for hypergraph H. in Equation then
Aut(H) = Stab(H) C Sym(h+(H) = Aut, (L)
(9)
By Proposition 2.1 Aut(H) _ Stab(H) H). The subgroup relationship follows by definition of the symmetry group of representation map given in Definition 2.9 and the equivariance of L-GWT.-1 due to Proposition
10

---

Published in Transactions on Machine Learning Research (11/2024)
2.2
The last group isomorphism follows by the equivalence between L-GWI-1 and the universal cover of the star expansion bipartite graph By.g up to 2T.-hops.
Since there are more automorphisms over the GWL-1 view of the hypergraph, many false positive symmetries might exist. Consider the following example. For two acighborhood-reguuaa hypergraphs C1 and C22 the red/blue colored universal covers Bc, Rc, of the star expansions of C1 and C2 are isomorphic, with the same GWL-I values on all nodes. However, two neighbortooodrregular hypergraphs of different order become distinguishable if single hyperodge covering all the nodes of each neighborhood-reguunn 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 C = C2 L CV. the hypergraph with two 3-regular hypergraphs Cf and Cg acting as two connected components of C. As shown in Figure 2 the node representations the two hypergraphs are identical due to Theorem 4.3
Given a hypergraph H, we define a special induced subhypergraph R S H whose node set GWL-1 cannot distinguish from other such special induced subhypergraphs.
Definition 4.3. L-GWI-1 symmetric induced sublgpergraph C of H is a connected induced subley- pergraph determined by VR S VH, some subset of nodes that are all indistinguishable amongst each other by L-GWL-1:
= (H), VR
(10)
When L oc, we call such R GWL-1 symmetric induced subhypergraph. Furthermore, if H. then we say H. is GWL-1 symmetric.
This definition similar to that of 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 A hyperggaph is GWL-1 symmmetrie if and only if it is L-GWT.-1 symmetrie for all I, 2 if and only H neighborhood regular.
Our goal is to find GWL-1 symmetric induced subhypergraphs a given hypergraph and break their symmetry without affecting any other nodes.
5 Method
Our goal is to learn from a training hypergraph and then predict higher order links in a temporally later hypergraph transductively. This can be formulated as follows:
Problem 1. Hyperlink Transductive Learning: Let V be nodes.
Given a training hypergroph sampled time tor E R: For (V, (Etr)gt) ~ P(H; (t),, learn a boolean predictor on hypergraph input so that:
For testing hypergraph sampled time the E RR, lee > by
For (V, ~ t(H;tte) and Ere S (Ere)ge:
E(((),sc),)) predicts whether e E (Ere)gt \: Ete, Ve E 2V
We will assume that the unobservable hyperedges are of the same size à so that only need to predict k-node sets. In order to preserve the most information while still respecting topological structure, aim to start with an invariant multi-node representation to predict hyperedges and increase its expressivenoss, as defined in Definition 2.8] For input hypergraph H and its matrix representation H, to do the prediction of missing hyperedge on node subsets, we use a multi-node representation h(S, H) for S C ((H) as in Equation 7 due to simplicity, guarantced invariance, and improve its expressivity. We aim to not affect the computational complexity since message passing on hypergraphs is already quite expensive, especially GPU memory.
11

---

Published in Transactions on Machine Learning Research (11/2024)
tou
(a)
(b)
Figure 3: An illustration of Algorithm for 1-GWL-1.
In (a) a hypergraph is shown. Each node is labeled with pair. The left part of the pair in Greek alphabet is its isomorphism class. The right part of the pair in Latin alphabet is its 1-GWL-1 class, which is determined by its neighborhood of hyperedges. In (b) the multi-hypergraph formed by covering the original hypergraph by hyperedges (light blue boxes) which are determined by the connected components of 1-GWT-1 indistinguishable node sets. The nodes can now be relabeled by 1-GWT-1. All hyperedges can assigned learnable weights. For downstream training, the new hyperedges are randomly added and the existing hyperedges within each new hyperedge are randomly dropped.
Our method a preprocessing algorithm that operates on an input training hypergraph = (V, Err with Eor C gEt)) In order increase expressivity, we search for potentially indistinguishable regular induced subhypergraphs
that they be replaced with hyperedges that span the subhypergraph to break the symmetries that prevent GWL-1 from being more expressive. We devise algorithm, which is shown in Algorithm D It takes as input hypergraph 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 H.
First we introduce some combinatorial definitions for hypergraph data that we will use in our algorithm: Definition 5.1. A hypergraph H. = (V,E) is connected if By.s is connected graph.
A connected component of H is a connected induced subhypergraph which is not properly contained in any connected sublyperyyuph of H.
Our preprocessing algorithm is explicitly given in Algorithm We describe it in words here:
A Algorithm:
For a given E Z and any L-GWL-1 node value CL. the first step is to construct the induced subhypergraph Ho, from the L-GWI-11 class of nodes:
Ve, a -
(11)
where hy denotes the L-GWL-1 class of node v.
We then compute the connected components of He,, Denote Cc, as the set of all connected compo- nents of Hog. If L oo, then drop L. Each of these connected components is subhypergraph of H. denoted Rez,s where Re Hez H for i 1,... (Cell-
3. Gather the collection of node sets and hyperedge sets formed by Roz = 1,-.., |Coz
We call the subhypergraphs in Co, found by the symmetry finding Algorithm 1 as maximally connected I- T-GWL-1 equal valued subhypergraphs.
12

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm 1: A Symmetry Finding Algorithm
Data: Hypergraph H = (V,&), represented by its star expansion matrix H. E Z+ is the number
of iterations to run GWL-1.
Result: A pair of collections: (Ry D. R = U,(ER, 1) where R are disconnected
subhypergraphs exhibiting symmetry in H. that are indistinguishable by L-GWL-1. UL t (H); < {UL(o] Ve E e
Uz|o] is the I-GGL-1 value of node e V. +/
BVn 5- (ipprrtiteH)) /* Construct the bipartite graph from H. */
3 Ry t {}: Rg + 0
4 for C E 16 do
5
Vcl + f : Uz|u] = = + f Vu Ec
Coz + CompecleeCommonnentsss
= (Ver EeL)
for ReL Cee do
Rv t Rv (VR.Z. 1: Rø RE ERiyy
end
10 end
11 return RR)
We will use the output hyperedges of the preprocessing algorithm to "softly" cover the input hypergraph. This will introduce multiplicities to the hyperedges. We formally define such generalization of a hypergraph, called multi-hypergraph here:
Definition 5.2. A multi- hyper-hhpp H. = (V,E) is pair consisting of set of nodes V and multiset of hyperedges & A (E, m) where & 2 and m : 3 + z is multiplicity function.
The star expansion incidence matrix of mulgi-hyyergraph H can now be defined as:
Definition 5.3. The star exponsion incidence matric H of a multt-hgperrraah H= = (V, is the [V] (2 Z+) (infiiile) 0-1 incidence matriz H where H = 1 iff u E e for (v,e) E V x & for some fined orderings on both V and 2 x z=.
In practice, of course, the multiplicity function of H is bounded and only the nonzeros of this matrix are kept track of. Thus the star expansion incidence matrix is actually a sparse finite matrix.
On a multi--yypergaphh H = (V,E), we can define the degree of a vertex v E V in terms of the cardinality of multiset: deg(v) & Iffe : 3 9 uB! E.so m(e) where m(e) is the multiplicity, or number repeated occurrences, of in e v).
Letting (if be the multiset of hyperedges of H and (H) the set of nodes of H. message passing through incidences is still well defined. We sunmarize this in the following proposition:
Proposition 5.1. The GWL-1 algorithm of Equation can be computed on multi- hultt--hpprggaah H. Thus, (H) and (S, H) are well defined on its star incidence matria H.
This implication of Proposition 5.1 is that GWL-1 based hyperGNNS can learn on multi-hypergraphs using the star expansion incidence matrix representations
on H. we collect its output (Rv, Rg). During training, for each 1,... Ce,. we randomly perturb Rex, to form a random multi-hypergraph Hr by:
Downstream Training: After executing Algorithm I
Attaching (with multiplicity) single hyperedge that covers VR with probability qi and not attaching with probability 1-q.
All the hyperedges in Rez, are dropped or kept with probability and 1 respectively.
Our method similar to the concept of adding virtual nodes Hwang al. (2022) in graph representation learning. This is due to the equivalence between virtual nodes and hyperedges by Proposition 4.1 For
13

---

Published in Transactions on Machine Learning Research (11/2024)
guarantee of improving expressivity, see Lemma 5.4 and Theorems 5.5
5.6 For an illustration of the data
augmentation, see Figure 2
Alternatively, downstream training using the output of Algorithm 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 with symmetric subhypergraphs randomly replaced. This, however, computationally expensive.
In Figure g an illustration of Algorithm I is shown. For the hypergraph shown in Figure (a), two graph cycles are glued at single node while separate hypergraph is glued at that same node. With 1-GWL-1, there is large class of nodes labeled "a" that are indistinguishable Each of the connected components of these 1-GWI-1 node classes is covered by a single hyperedge (light blue box) to form a multi- hypergraph. We show in Section 5.1 that in this multihypergraphh, the nodes express more of the original hypergraph. The data augmentation procodure during downstream training can then be applied to the blue boxes and the original hyperedges within each blue box separately.
Illustration:
5.1 Algorithm Guarantees
We show some guarantees for the output of Algorithm [ We will assume the following notation to denote the relevant substructures on single hypergraph found by Algorithm
Notation:
Let H = (V.E) be a hypergraph with star expansion matrix H as before.
Let (Ry, be the output of Algorithm | on H for L E Z+. We call this collection of nodes and hyperedges
as GWL-1 symmetric induced components. Let:
A, & (V,ELRV)
(12)
be the multi-hypergraph formed from H after adding all the hyperedges from Ry and let Hr be the star expansion matrix of the resulting multi-hypergraph Hr. Let:
VaL - {u EEVE Vo, : R.R. Ce.. VAl s}
(13)
be the set all nodes of I-GWT-1 class er belonging to a connected component in Co2 of 8 2 1 nodes in Hoz, the induced subhypergraph of L-GWL-1, Let:
GL a (
(14)
the set of all L-GWL-1 values on H. Let:
S., A (VRoyall Rey, E Cop)
(15)
be the set of node set sizes of the connected components in Hez.
Properties of (Ry, Rg) from Algorithm
In the following proposition, we show that the subhypergraphs found by Algorithm ! are GWL-1 symmetric. This should be evident by line 5 of Algorithm [ where an induced subgraph of the bipartite graph is formed from nodes of the same L-GWL-1 values.
Proposition 5.2. If L oc, for any GWL-1 node value computed on H. all connected component subhypergraphs Res C. are GWL-1 symmetric as hypergraphs.
Algorithm 1 outputs a partition of the entire hypergraph. This follows from the fact that GWL-1 already covers the entire hypergraph after single hop.
Proposition 5.3. If L 2 the output (Rv, Re) of Algorithm
i
partitions subgraph of H. meaning:
v LIVeRVV V and E D LIER,
(16)
14

---

Published in Transactions on Machine Learning Research (11/2024)
The output of Algorithm I can additionally be used to guarantee improvement in expressing the hypergraph:
Prediction Guarantees:
In order to guarantee that the GWL-1 symmetric components Re,, found by Algorithm carry additional information, there needs be a separation between them to prevent an intersection between the rooted trees computed by GWT-1. We define what it mcans for two node subsets to be sufficiently separated via the shortest hyperedge path distance between nodes in V as follows:
Definition 5.4. Two subsets of nodes U, U2 S V are sufficiently L-separated if:
min d(v1, U2) > L E2
(17)
where d(v1, U2) & eut.e............eeeve...e. k is the shortest hyperedge path distance from i1 V to U2 E V.
A collection of node subsets C C 2 is sufficiently L-separated if all pairs of node subsets are sufficiently L-separated.
Our definition of sulficiently Z-separated is similar in nature to that of well separation between point sets Callahan & Kosaraju (1995) in Euclidean space. Assuming that the Cet are sufficiently L-separated from each other, intuitively mcaning that no two nodes from two separate VR.g. E Ry are within L hyperedges away, then the cardinality each component (VRezsl is recognizable. This is stated the following lemma:
Lemma 5.4. If L Z+ is small enough so that after running Algorithm 1 on L, for any L--GWT-1 node class CL on V the collection of Cas, is sufficiently L-separated,
then after forming AL, the new L-GWL-1 node classes of VR for i = L,,.,Coe in Hr are all the same class ej but are distinguishable from er depending on (VRozal-
We can then use this lemma to show that under certain conditions for large hypergraphs, augmenting the hypergraph H. to the multi-hypergraphe H. will give a guarantee on the mumber of pairs of k-node sets that become distinguished which were indistinguishable as sets of GWT.11 values.
Theorem 5.5. Let |V| = L Z+ and col(v) A Eneereo le| and assuming that the collection of node subsets Ce,. is sufficiently L-separated.
If (v) O(log tff n), E for any constant e <> 0; |Sen. S S.YeL E C2. S constant, and |Ver.øl O Vs E CeL- then for l E Z+ and k-tuple C (L) E 92, to (n) (n2kee) many pairs of k-node sets S o S2 such that (H))))) = (h (11) C, as ordered k-tuples, while ((S,,H,) * h(S2, H2) also by L steps of GWL-1.
1..k there ewists
The conditions of Theorem 5.5 assume an arbitrarily large hypergraph that is sparse and for every E GL has CoN sufficiently I-separated, has a bounded set of node set sizes from Se, and a controlled growth for each node set size from Sey, The idea behind the proof of Theorem 5.5 is that under these conditions, there are enough isomorphic rooted trees computed by L-GWL-1. It can then be shown that over all pairs of k-sets of nodes with elementwise isomorphic rooted trees, that they can be distinguished by the component size they belong in. We give simple example hypergraph that illustrates the condition of Theorem 5.5
Example: A simple example of a hypergraph that statisfics the conditions of Theorem 5.5 is a union of many disconnected hypergraphs H. = U,H, = (),E) with [Vr,l < S where S < 00 is a small constant independent of n = IV 2 S. Such a hypergraph could be a social network where the nodes are user instances and the hyperedges are private groups. The disconnected hypergraphs represent disconnected communities where a user can only belong a single community.
We show that algorithm increases expressivity (Definition 2.8 for h(S, H) of Equation Theorem 5.6 (Invariance and Expressivity). If L = oc, GWL-1 enhanced by Algorithm ant to node isomorphism classes of and can be strictly more expressive than GWL-1 to determine node isomorphism classes.
still invari-
15

---

Published in Transactions on Machine Learning Research (11/2024)
Proving expressivity from Theorem 5.4 follows from the added information of component sizes viewable by each node in its vicinity. Proving the invariance from Theorem 5.4 follows by proof by contradiction, which uses the maximality of the connected components found in Algorithm I
When training on a hypergraph with the data augmentations, every possible symmetry observed from the random augmentations will be learned. Thus the symmetry group of h on the random matrix H, is isomorphic the intersection of all symmetries over each augmentation sample. This is expressed as follows:
Sym(hh(Bn)) & n
Sym(h (fr)) ((,-((H))
(18)
We show that the intersection over all symmetries of the estimated multi-hyyergrapph Hr, has fewer sym- metries than that of the L-GWL-1 view of the hypergraph collection of rooted trees. We call this symmetry breaking.
Proposition 5.7. The malti-hygerrrrahh Hr breaks the symmetry of the L-GWI-1 view of the hypergraph Hi
Sym(h+(ft))) S Aula R2L (.
(19)
This follows by the fact that the identity augmentation is in the support of the distribution of random augmentations and that Sym(h+(Azz) = Aul. (.,rr))) by Theorem 4.4
Since hyperGNNs represent each node v E V by message passing through the neighbors in the rooted tree (By.e), at v. If probabilities are assigned between nodes, then T layers of a hyperGNN can be viewed as computing the random walk probability of ending on any node starting from some uniformly chosen node, We define these terms in the following:
Definition 5.5 (Chitra & Raphael 2019)). A random walk a (multi) hypergraph = (V,E) is a Markov w(c) chain with state space V with transition probabilities Pa,e - Ee deg(u]le? where w(e) : E + [0, is some discrele probability distribution on the hyperredges. When not specified, this is the consland function.
Assuming H. is connected, let X₃ E V denote the state of the Markov chain at step t with P(X, = v) = M Ye E V. Letting - 00, this probability converges to the stationary distribution on the nodes V, which is independent of the time. This is expressed in the following definition:
Definition 5.6. A stationary distribution π. V - [0, 1] for a Morkov chain with transition probabililies Pu, is defined by the relationship Evev Pa (u) = T()).
deg(u) For a (malli) hypergraph random walk we have the closed form: a(v) Evey deg(u) for U V assuming H is a connected (malti) hypergraph.
For the downstream training, we show that there are Bernoulli hyperedge drop/ trop/attachment probabilities p. 9: respectively for each Rey., 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.8. For a connected hypergraph H. = =V,,),, let (Ry,Re) be the output of Algorithm 1 on H. Then there are Bernoulli probabilities p. 9s for i 1,... (Ryl for attaching a covering hyperedge so that is an unbiased eslimator of n.
The intuition for Proposition 5.8 is that if hyperedge is added to cover connected subhypergraph Re,, containing at least one hyperedge, then allowing any of the hyperedges in Reg, to drop is enough to keep the estimated stationary distribution á unbiased.
Time Complexity:
Proposition 5.9 provides the time complexity of our algorithm.
Proposition 5.9 (Complexity). Algorithm 1 runs in time (mmz(H)L + (n m)), which is order linear in the size of the input star expansion matriz H for hypergroph (V,E), if L is independent of nnz(H), where = [VI mnz(H) vV) a Evey deg(v) and [8).
16

---

Published in Transactions on Machine Learning Research (11/2024)
Since Algorithm runs in time linear in the size of the input when L is constant, in practice it only takes small fraction of the training time for hypergraph neural networks.
6 Evaluation
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 way tie. All datasets involve predicting hyperedges of size 3.
Table 1:
PR-AUCT
Busdine
Ouz
Holeu 0.12
PR-AUCT
Bastiza
Ours
Basea -niiap
PR-AUCT
Basdine
Our
Busin, isleop
BGNN
0008
a: 0.08
HGNN
0,90 6:13
1.10
0,90 1.13
HGNN
0.96
0.98
0,36 0.04
BGNNP
058 2002
0.00
HGNNNP
0.90
1.00 0.07
1,00 0.003
HGNNN
0.96 0.96 0.005
0.98
0.00
0.97 0.07
HKHS
038 = 0001
0.96 0.07
0.9 # 0.04
HNHN
0.00
0.31 0.0012
6.900+00.10
TININ
0.00 a 0.02
0.9 U.
0.06 0.00
HVprEGUNN
0,88 + 0.0
0
4 0:11
0 + 0.088
1 00,00
1.00 4: 0.133
1.00 0.002
PopeeCICN
0.00 + 0.05
0.98 + 0.00
0.00 0.00
UnICAT
0006
0.08
0.07
UsIGAT
0.00
L.00 0.003
1,00 0.00
UWIGON
UnIGON
0.01
URIGON
0.06
0.96
0.90
UnIGIN
087
0.00
0.8 0.10
0.85 +: 0.08
UnIGIN
0.90++00112
0.05 0.06
0.00++00:11
UnICIN
0.07 0.03
0.97 0:10
0.00 0.05
UnISAGE
0.86 0.04
0:80 + 0.05
0.64 + 0.09
UGSAGR
0.90 0.16
1.00 0.08
0.90 + 0.17
UniAAGE
0.96 + 0.30
0.50 + 1.10
0.00 0.02
(a)
DAWN
(c)
CONTACT--IGI--COOO
PR-AUC-
Buseline
Owes
Besela
PR-AUCT
Basellne
Oues
Bascla.+eding
PR-AUC-
Braeline
Owas
Blsclo,
RGNN
0.86 + 0.6
0.9 + 0.01
0.56 + 0.03
HGNN
0.35 + 0.07
0.97 + 0.00
0,36 + 0.07
HGNN
0.76
0.85 +
0.71 0.114
HGNNP
0:56=
0.09
0.07
HGNNP
0.30
0.96 s: 0.00
HGNNP
0.88=0009
0.85 0.08
0.86 0.00
HNHN
0.0
0.05
HNNHN
0.34
0.37
0.95 0,90
HNNIN
0.72
0.82
0.74
HVpe
097 0001
0.9 0.055
0.96 J. 0.08
HNDerGON
0.92 10.00
0.000 0.04
0.04 à 0.08
HCy
0.08
0.844 0.05
1.00 a 0.07
UnIGAT
036 2 000
098
1 0.0
0358
0.02
UmCAT
0.04 1 0.08
0.35
1.144
0,37 1 U.DS
UNIGAT
0.80
0.53 1 0.03
0.78
1: 0.05
UNIGON
0.9 + 0.00
0.97
+ 0.14
0.97 + 0.10
UniOCN
0.07 + 0.08
0.07
0.14
0.07 + 0.05
UnIGCN
0.8+000.6
0.80 + 0:10
0.1 + 0.07
UniGIN
0.09
0.02
+ 0.05
UniGNN
UnIGIN
0.19
0
0.61 +0111
UnISAGE
0.08
4: 0.05
0.02
CaBAAG
0.333
0.07
0.08
0.32 :: 0.04
UnOSACI8
0.72
0.71
0.11
(e)
RMAAL-EU
We evaluate our method on higher order link prediction with many of the standard hypergraph neu- ral 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--IGH-SCHOOOL
EMAIL-EU, CAT-EDGE-MADISON- RESTAURANTS. These datasets range from representing social interactions they develop over time to collections of reviews to drug combinations before overdose. We also evaluate on the AMHERST41 dataset, which is a graph datasct. All of our datascts are unattributed hypprgraphs/grappe
CONTACTTPRIMARY-SCHOON
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 hyperodges 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/ncgative nngative 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 possibility that certain datasets are out-of-distributie 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 Per to predict. For validation and test, we remove 50% of the edges from both validation and test to set as the positive examples Poot, Pte to prodict. For train, validation, and test, we sample |Porl. Poatl |Ptel negative link samples from the links of train, validation and test.
17

---

Published in Transactions on Machine Learning Research (11/2024)
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. The coloring scheme is the same as in Table !
PR-AUCT
HGNN
HGNNP
HNHN
HypeGGN
UniGAT
UniGUN
UniGIN
UniSAGE
Ours
0.3++0.100 0.10
0.6 + 0.06
0.64++0.06
0.71 0.00
0.72 0.08
0.70++000
0.73++005
0.73 0.006
CNPe Enseline
0.22 0.08
0,02 0.10
0.63 0.04
0.71 0.07
0.20=
0.07
0.73= 0.05
INperGNN -edrop
0.61 a: 0.00
0.61 a 0.03
0.61 0.09
0.71 0.02
0.09 0.05
0.73 0.09
0.73 1: 0.01
APPNP
0.42 0.07
0.42
0.42
0.077
0
0.42=0077
0.42
0.42
0.42 0.07
0.42: 0.03
042:1 0.03
0.42 0.00
0.42 0:03
0.42=000 0.03
0.42 :: 0.03
0.42 :1 0.03
0.42 1: 0.03
GAT
0.49 0.06
0.49 0.06
0.49 0.05
0.49 +.00
0.43= 0.06
0.40 + 0.06
0.49 - 0.06
0.40 + 0.06
GAT-eeirop
0.09
0.49
0.06
0.06
0.40
GCN2
0.56 0.12
0.56 0.12
0.56 3 0.12
0.56 0 0.12
0.56
0.12
0.56 2: 0.12
0.56 =: 0.11
0.56 1: 0.12
GUN2+edrop
0.51 0.02
0.51 0,02
0..02
0.54 1551100
0.54 0.02
0.54 L 0.02
0.54 0.02
0.51 1 0.02
0.40 0.00
0
0.30 0.03
0.03
0
0.60 0.00
0:03
0,40 0.00
i
0.65 0.04
0.65 + 0.04
0.05 0.00
0.04
0.05
0.65 0.04
0.65 + 0.04
0.65 + 0.04
GIN
0.100
0.73
0.73
0:010
0.7300.10
0.73 0:330
0.75 0.30
0.73 0.300
GIN-edoog
0.73+-0.0 0.10
0.73 0.10
0.73++0.10
0.73
0.73 0.10
0.73++0.30
0.73 0733+0010
0.73 +730+00.10
Graph&AGE
0.44 0.01
0.44 0.01
0.44 0.001
0.14
0.66 0.01
0.00
0.41 0.00
0.41 0.00
0.44 0.10
0.44 0.10
0.10
0.11
0.10
0.44 0.30
0.31
6.1 Architecture and Training
Our algorithm serves as a preprocessing stop for seleetive data augmentation. Given a single training hypergraph H, the Algorithm [ is applied and during training, the identified hyperedges of the symmetric induced subhypergraphs of 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 large set of symmetric subhypergraphs, we run 2 iterations of GWL-1.
We implement M(SS, H) from Equation 7 as follows. Upon extracting the node representations from the hypergraph neural network, we use a mulli-layer-perceetrro (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 this multi-node representation for training. We always use layers of hyperGNN convolutions, hidden dimension of 1024, and a learning rate of 0.01.
6.2 Higher Order Link Prediction Results
We show in Table D 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 Laplaciann 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 an unattributed hypergraph.
We show in Table 2 the PR-AUC scores on the A 4MHREST41. 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. (0117), GCN2 Chen et al. (2020a), GCN Kipf & Welling (2016a). GIN Xu et al. 2018), and GraphSAGF Hamilton et al. (2017). For every hyperGNN/GN
architecture, we also
apply drop-odge Rong et al. (2019) to the input graph and use this also as bascline. The number of layers of each GNN is set 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 the data level. There was also not much of a concern for computational time since our algorithm runs in time OH)z((H) + n + m), which is optimal since it is the size of the input.
18

---

Published in Transactions on Machine Learning Research (11/2024)
100
GWLL-1 Classes
120
80
Size of MMaimaall Connected GWWL-
100
Maxima Connected
8
comment O
40
00 00
Lam--mo 00
40
20
128
1024
2048
128
1024
2048
Number Nodes
Number of Nodes
(a) Boxplot of the sizes of the connected components with equal GWL-1 node values from the hy-MMSBM sampling algorithm where there are three independent communities.
(b) Boxplot of the sizes of the connected components with equal GWL-1 node values from the My-MMSBM sampling algorithm where any two of the three communities can communicate.
Experiment on the relationship between the sizes of connected components of equal GWL-1 node values and the communication between communities.
Figure 4:
6.3 Empirical Observations on the Components Discovered by the Algorithm
According to Proposition B.14 we know that the symmetry finding algorithm always covers the hypergraph and thus that we can generate on the order of O(2l2)) counterfactual multi-hyporgraphhs. It is known that a large set of data augmentations during learning improves learner generalization. The cover by GWL-1 symmetric components follows a distribution depending on the data.
We show Figure the distributions for the component sizes over all GWL-1 symmetric connected compo- nents for samples from the Hy-MMSBM model Ruggeri al. (2023). This model to sample hypergraphs with communily structure. In Figure 4a we sample hypergraphs with 3 isolated communities, meaning that there is 0 chance of any intercommections between any two communities. In Figure 4b sample hypergraphs with 3 communities where every node in community has weight of to stay in its community and a weight of 0.2 to move out to any other community. We plot the boxplots as a function of increasing num- ber of nodes. We notice that the more communication there is between communities for more nodes there is more spread possible connected component sizes. Isolated communities should make for predictable clusters cooneectd//neeeed components.
7 Discussion
Our proposed data augmentation method uses symmetry breaking to handle the symmetries induced by GWL-1 based hyperGNNs. Symmetry breaking provides some guarantees that the symmetries induced by the hyperGNN are brought closer to the symmetries of the training hypergraph. These include hyperlink prediction guarantees. In addition, symmetry breaking prepares the hyperGNN for an automorphism group different from the symmetries it views during training. This brings about an important question regarding the invariant automorphism group across training and testing, namely:
What is the relationship between the symmetries of the training and testing hypergraphs?
We answer this question the context temporal shift from training to testing. The term 'temporal shift" is usually used in the context of distribution shifts Yao al. (202aa). We define it in terms of transductive hyperlink prediction.
19

---

Published in Transactions on Machine Learning Research (11/2024)
A temporal shift from training to testing means that the testing hyperedges have temporal future relation- ship with the training hyperedges.
We formalize a hypergraph in terms of a physical system that can change over time with the following assumptions.
Assumption 7.1. If we view a hypergraph as a physical system of particles where only the nodes have mass, then the task of transductive higher order link prediction is on closed system Londau & Liffsitt (1600] This means no mass can enter leave this system.
Given modes V, con view each node E V along with the hypergraph H = (V,8) il belongs in microstate (v, H) of a statistical ensemble.
In Rasheusky 1955) the entropy of a graph is defined through the orbits of the automorphism group. We generulize this to a node based defonition for leppergraphs. Our definiliion uses a similar probability on mi- crostates. We define the hypergraph topological entropy of hypergraph H. (V,E) by:
S
Σ Pu (H) log(p.(H)):
(20)
(H(
with (H)
Eney (H)
where (H) 2 Fu E V : u HH wH| is the number of nodes u E V isomorphic to node v, including v itself. (See Definition 2.
Assumption 7.2. (Second Law of Thermodynamics ): The second law of thermodynamics Carnot (1788) states that the entropy of closed system must increase over time. This is denoted by the following equalion:
AS > 0
(21)
This law be used in terms of the hypergraph topological entropy as defined in Assumption 7.1
We also assume the following random model the hypergraph predict Let tr, te represent temporally ordered training and testing distributions where (E.)gt are the hyperedges of (Ho))t. Assumption 7.3. For each node E V, let X be independent Bernoulli random variables of some probability go E [0, 1]. Let (()x))el be the number of testing hyperedges of (Hee)gt. is a rondom variable defined by:
(((X,)vev)= = Σ NueeX
(22)
V3v
Assume further that ((Ere)g)): (V, (Enc)gt) P(H; (ze) only depends on n.
Let X,, be Bernoulli random variable with probability Qman- Assume that f satisfics
P(f(Xuzu do = l). Xuzu)
< 2) do(X, = .)., (u))
in -=1)=1 Vu E
(23)
These assumptions show that with high probability there are node isomorphism classes which decrease in size:
Theorem 7.1. Under Assumptions 7.1 7.3 and the Second Law of Thermodynamics on the hypergraph viewed as a closed system:
hE v, so that: nh ((Hee)) > no (Hlee)))))) Vo E U, with probobility O
(24)
Proof. By the second law of thermodynamics, we must have that between the training hypergraph (Her) = (V, (E))) and testing hypergraph (Hea)gt (V, (Ete)gt) which is temporally later than (Hrr)gt>
AS
Σ p. ((Hro) log(p, VEV
Σ ge ((H())(())) >
(25a)
vEV
20

---

Published in Transactions on Machine Learning Research (11/2024)
If we take upper bound on AS, get the following consequence:
Pr. (o(((er)g)) = Po((Her)ge > po((He))))) Vo E u for some U S v.u +
O< < log(
(26)
Po. Pr((Hse)gd VEV
If ((Hergg))) no (HHHee))))) Vu E E C V, conclude that some nodes will shrink the size of their ground truth isomorphism class.
We show that this occurs with high probability by bounding the complementary case.
Nodes rarcly increase their isomorphism class size:
C V, we show that under Assumption 7.3 node isomorphism class cardinality growth occurs with low probability due an anti-concettration bound multivariate polynomials Fox et al. (2021)
For the complementary case, n. (g)(()))))) S ny (HHe)))))))
In this complementary case, must have that the nodes in M C V increased the number of nodes isomorphic to them. This implies that each of these nodes E U must have changed their degree vector upon changing (Her)ge ge to (Mee)ge- This change requires that some other node u E V, u * obtains a degree vector equal to the degree vector v.
Let us define this space of all possible testing hyperedge sets with this necessary condition:
Deg DegVec (v, (H {E E suppl (upe(P((( ha)) Du E V, degvee (v) = my) u + (27)
We can express the relationship between the change in n, with membership in Deg Vec (v: (Hee)gt):
no ((Her)))))) I nu (HHee))))) = (Ere)ge E Deg Vec (v, (Hec)gt)
(28)
Letting
Emin (v)
min EeDogVoo (v. (Hec)a))
El, Vu EV
(29a)
and
Tmaz (v)=
max (rr
E) Vo EV
(29b)
We can then say that the number of testing hyperedges (E )rl) is in the interval [Emin (v), Emax [m)x(
(Ere) E DegV eCe (Hle)ge) + Imin (v) S J((Xx)uev) (w)
(30)
Let the diameter of the interval [Emin (v), Fma (v) be given by D:
D 2 Iman (v) (min(()
(31)
This only depends on since the minimizers and maximizers Exmin Exmax of Equations 29a and 29b satisfy: Fremin Fizmax E Deg (v, (Hte)gt) and thus belong to the suppl (P(;:te)) We know that any E E supp( ((E (Eette)) has that [E] depends only by Assumption
Define the median M on [Imin (u), Zmaa (v) by:
M Fmaa (v) + Fmin (v)
(32)
2
We thus have that:
Tmin (v) (((x))vv)) S (m)x(v)
(v) + (f((X))vev)) M 5 D
(33)
Piecing together Equations
28
30
and
33
have by monotonicity:
P(n, ((Her)g)) n. ((Haa)))))) P(amin (v) < [((Xu)uev) S (maa((1)
(34a)
21

---

Published in Transactions on Machine Learning Research (11/2024)
S -(( - MM < <D)
(34b)
S P(IM f((Xu)ueV)) < < ( Vu )
(34c)
Where the last inequality comes from the anti-concentration bound of Theorem 1.2 of Fox et al. 202 which states:
P(If((X,)vev) - z < 0 vn
) E
(35)
for any which may depend on n and any E R. Setting x = M,s == D, gives the last inequality.
Theorem 7.1 states that the ground truth node isomorphism classes for the nodes must shrink with probability on order ((+))) Thus, for large n >> O, we have that with high probability that the nodes u S V,u + 0 have n. ((He))at) no((He))g))
We can recognize this property of (Hae)ge by shrinking the automorphism group that the hypergraph encoder recognizes from the training hypergraph. According to Proposition 5.7 symmetry breaking as given in
Equation 18 does this.
Our method breaks the symmetry of GWL-1 based hyperGNN. This, of course, not of importance if the symmetry group of the GWL-1 based hyperGNN on some training hypergraph is already the trivial group. Nonetheless, our symmetry breaking method is theoretically beneficial. Our method can also be used within other rewnstream learning methods such as feature averaging Lyle et al. (2020), and ensemble methods, mentioned in Section 5
8 Conclusion
Many cxisting hyperGNN architectures are based on the GWL-1 algorithm, which is hypergraph isomor- phism testing algorithm. We have characterized and identified the limitations of GWL-1. GWL-1 views the hypergraph as a collection rooted trees. This means that hyperGNNs recognize more symmetries than the natural automorphisms of the training hypergraph. In fact, 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 hypergraph, we have devised preprocessing algorithm that identifies all such connected components. These components cover the hypergraph and allow for downstream data augmentation of symmetry breaking by training on random multi-hyppegraph. We show that this approach improves the expressivity of a hyperGNN learner, including in the case of hyperlink prediction. We perform extensive experiments to evaluate the effectiveness of our approach and make empirical observations about the output of the algorithu on hypergraph data.
22

---

Published in Transactions on Machine Learning Research (11/2024)
References
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.
Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph neural networks. Advances in Neural Information Processing Systems, 33:8017 8029, 2020.
llya Amburg, Nate Veldt, and Austin R. Benson. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of the Web Conference, 2020a.
llya Amburg, Nate Veldt, and Austin R Benson. Fair clustering for diverse and experienced groups. arXiv:2006.055/ 2020b.
Devanshu Arya, Deepak K Gupta, Stevan Rudinac, and Marcel Worring, Hypersage: Generalizing inductive representation learning on hypergraphs. orXiv preprint arXiv:2010. wrX::22000004588 2020.
Song Bai, Feihu Zhang, and Philip HS Torr. Hypergraph convolution and hypergraph attention. Pattern Recognition, 110:107637, 2021.
Pierre Baldi and Peter Sadowski. The dropout learning algorithm. Artificial intelligence, 210:78-12 2014.
Mikhail Belkin and Partha Niyogi. Laplacian cigenmaps for dimensionality reduction and data representation.
Newral compulation, 15(6):1373 1396, 2003.
Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaic, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the Notional Academy of Sciences, 2018a. ISSN 0027-8424.
doi: 10.1073/ppas.18000 pttp:/aaass.0.111....11
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.
Garrett Birkhoff. Lattice theory, volume 25. American Mathematical Soc., 1940.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lchman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625 2040,,640444 2021.
Antoine Bordes, Nicolas Usunier, Alberto Carcia-Duran. Jason Weston, and Oksana Yakhnenko. Translat- ing embeddings for modeling multi-relational data. In C.J. Burges, L.. Bottou, M. Welling, 7. Ghahra- mani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Cur- ran Associates, Inc., 2013. URL https:://rroceedinn nwwrrpe.uc.eeeeeee wttps/pcppppppepaeeaaeeaaeeeeeee filess/paper/201///// LLcecAa7722222133344466888882203 pdf.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pollern Analysis and Machine Intelligence, 45())6657 668, 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-1922 2022.
Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to Ehnearest-neighhen and n-body potential fields. J. ACM, 42(1):67-90 jan 1995. ISSN 0004-5411. doi: 10.1145/200866.200 200885.. URL httttt:://oi.oooo 10. 1011/1110200/ 200853
Sadi Carnot. Réflevions sur la puissance motrice du feu. Number 26. Vrin, 1978.
Nitesh V Chawla, Kevin W Bowyer, Lawrence Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-355 -377, 2002.
23

---

Published in Transactions on Machine Learning Research (11/2024)
Can Chen and Yang- Yu Liu. A survey hyperlink prediction. arXiv preprint arXiv:2207.0991 2022.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pp. 1125-1735. PMLR, 2020a.
Samantha Chen, Sunhyuk Lim, Facundo Memoli, Zhengehao Wan, and Yusu Wang. Weisfeiler-lehman Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Leorning, volume 162 of Proceedings of Machine Learning Research, pp. 3371-3416. PMTR, 17-23 Jul 2022. URL
meets Kromov-Wasserseee
attps://procceeding.. mlr. pwwps//16eeeeepppptpppppppppp hhtp///cccc2coccc .tml
Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. The weisteiler-echman distance: Reinterpretation and connection with gnns. arXiv preprinl arXim:2302.0071 007113 2023.
Shuxiao Chen, Edgar Dobriban, and Jane Lee. A group-theoretic framework for data augmentation.
Journal of Machine Learning Research, 21(245):1-77 71, 2020b.
Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. You are allset: A multiset function framework for hypergraph neural networks. arXiv preprinl arXiv:2106.1228 2021.
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://openrevier.. wwt.://eooroom//ddnh/lil////////
Uthsav Chitra and Benjamin Raphacl. Random walks on hypergraphs with edge-dependent vertex weights. Kamalika Chaudhuri and Ruslan Salakhutdinno (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 httpss:/pproceeddngg.. mwr. www.mm........vv....mm www.raa9hitaaaa...mm html
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 Learning Representations.
Nicolas Crossley, Andrea Mechelli, Petra Vértes, Toby Winton-Brown, Ameera Patel, Cedric E Ginestet, Philip McGuire, and Edward T Bullmore. Coguitive relevance of the community structure of the human brain functional coactivation network. Proceedings of the National Academy of Sciences, 110 (28):1 11111111318888 11588, 2013.
Janez Demšar. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research, 7:1-30, 2006.
Yihe Dong, Will Sawin, and Yoshua Bengio. Hnhn: Hypergraph networks with hyperedge neurons. arXiv preprint arxiv:2006.1 12278, 2020.
David Steven Dummit and Richard M Foote. Abstract algebra, volume Wiley Hoboken, 2004.
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks, In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 3558-3565, 2019.
Yifan Feng, Jiashu Han, Shihui Ying, and Yue Gao. Hypergraph isomorphism computation. arXiv preprint 21Ki:23377.13999 2023.
Jacob Fox, Matthew Kwan, and Lisa Sauermann. Combinatorial anti-concentration inequalities, with appli- cations. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 171, pp. 227-248. Cambridge University Press, 2021.
Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. Hgnn+: General hypergraph neural networks. JEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
24

---

Published in Transactions on Machine Learning Research (11/2024)
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. Xr preprinl ar arXiv:1810005997 2018.
Lorenzo Giusti, Claudio Battiloro, Lucia Testa, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa. Cell attention networks. arXiv preprint arXic:2209.081 2022.
Chris Godsil and Gordon Royle. Algebraic graph theory, volume 207. Springer Science & Business Media, 2001.
Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Cheng. Link prediction on n-ary relational data. In Proceedings of the 28th International Conference on World Wide Web (WWW'19), pp. 583-593, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Allen Hatcher. Algebraic topology. Web, 2005.
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.
Jing Huang and Jie Yang. Unignn: a unified framework for graph and hypergraph neural networks. arXiv preprinl ar xrx::22155.0080 2021.
EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis virtual nodes in graph neural networks for link prediction. Tn The First Learning on Graphs Conference, 2022.
Jinwoo Kim, Saeyoon Oh, Sungjun Cho, and Seunghoo Hong. Equivariant hypergraph neural networks. In European Conference on Computer Vision, pp. 103. Springer, 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint ar arXiv: 02907, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint orXiv:1611.073b0 2016b.
Oliver Knill. A brouwer fixed-point theorem for graph endomorphisms. Fized Point Theory and Applications, 2013 2013.
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.
Lev Davidovich Landau and Evgenii Mikhailovich Lifshitz. Mechanics, volune 1. CUP Archive, 1960.
Dongjin Lee and Kijung Shin. I'm me, we're we're us, and i'm us: Tri-directional contrastive lcarning on hyper- graphs. arXiv preprint arXiv:2206. 04 739, 2022.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diam- eters. ACM Transactions Knowledge Discovery from Data, 1(1), 2007. doi: URL https: org/10 1100.11444 1145/1217299 1217301
1217301.
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.
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.
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, 44788 2020.
Shouheng Li, Dongwoo Kim, and Qing Wang. Local vertex colouring graph neural networks. 2023b.
25

---

Published in Transactions on Machine Learning Research (11/2024)
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 Neurol Information Processing Systems, 34:20887 20902, 2021.
Francois Lorrain and Harrison C White. Structural equivalence of individuals in social networks. The Journal of mathematical sociology, (11):99 80, 1971.
Linyuan Lü, Matúš Medo, Chi Ho Young, Yi-Cheng Zhang, Zi-Ke Zhang, and Tao Zhou. Recommender systems. Physics reports, 519(1):1 49, 2012.
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Blocm-Roddy. On the benefits of invariance in neural networks. arXiv preprint ar Xrv:20005. 00155,000.7.. 2020.
Haggai Maron, Heli Ham,H, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks.
arXiv preprinl Xie::8111 099002, 2018.
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:
URL https://doi http:///oooogg//.... pttg//...7///ooooooo... 10711/oorrnaaa pone.
0136497
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. In International Conference on Machine Learning, pp. 17323-173455. PMLR, 2022.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnm: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34:21997-22009 2021.
Nicolas Rashevsky. Life, information theory, and topology. The bulletin of mathematical biophysics, 17: 229 229-235, 1955.
Petar Ristoski and Heiko Paulheim. Rdf2vec: Rdf graph embeddings for data mining, In The Seman- tic Web-ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17-21, 2016, Proceedings, Part 15, pp. 498 514. Springer, 2016.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arxio preprint urXiv:19011 1000.10930 2019.
Nicolò Ruggeri, Federico Battiston, and Caterina De Bacco A framework to generate hypergraphs with community structure. arXiv preprinl arXiv:2212.0855 08593, 22, 2023.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 STAM internalional conference on dala mining (SDM), pp. 333-341 STAM, 2021.
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.
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/2740008.274255 URL https://doi.
org/10. 0rg/10.114//2 1145/2740908. 2742839
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. arXiv preprint arX:::1910.00452 2019.
Balasubramaniam Srinivasan, Da Zheng, and George Karypis. Learning over familics of pets-hyp representation learning for higher order tasks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 756 764. STAM, 2021.
26

---

Published in Transactions on Machine Learning Research (11/2024)
Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isclla, Jean-Frangois 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)ee23176, 2011.
Mengying Sun, Jing Xing, Huijun Wang, Bin Chen, and Jiayu Zhou. Mocl: data-driven molecular fingerprint via knowledge-aware contrastive learning from molecular graph. In Proceedings of the 27th ACM SIGKDD conference knowledge discovery & data mining, pp. 3585-3594, 2021.
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 Sinteenth ACM International Conference on Web Search and Data Mining, pp. 625-633, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 10903, 2017.
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.
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.
Xiyuan Wang, Pan Li, and Muhan Zhang. Improving graph neural networks on multi-node tasks with labeling tricks. arxiv preprint orXb::2344.1077, 2023.
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.038: 2022.
Boris Weisfeiler and Andrei Leman. The reduction of graph canonical form and the algebra which appears therein. nti, Series, 2(9):12 16, 1968.
Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and Richong Zhang, On the representation and embed- ding of knowledge bases beyond binary relations. arXiv preprint arXiv:1604.0866 2016.
Asiri Wijesinghe and Qing Wang. A new perspective on' how graph neural networks go beyond weisfeiler- lehman?". In International Conference on Learning Representations, 2021.
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 syslems, 31(1): 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 111: 00826, 2018.
Naganand Yadati, Madhay Nimishakavi, Pratock Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. Advances in neural information processing systems, 32, 2019.
Huaxiu Yao, Caroline Choi, Bochuan Cao, Yoonho Lee, Pang Wei W Koh, and Chelsea Finn. Wild-time: A benchmark of in-the-wiit distribution shift over time. Advances in Neural Information Processing Systems, 35:10309-10324, 2022a.
Huaxiu Yao, Yu Wang, Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Improving out- of-distribution robustness via selective augmentation. In International Conference on Machine Learning, pp. 25407-25437. PMLRR 2022b.
Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local higher-order graph clustering. In Proceedings of the 23nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2017. doi: 011144//309993330080666 URL http:////0a..orr//011114/1/3/333
3098069
27

---

Published in Transactions on Machine Learning Research (11/2024)
Jiaxuan You, Jonathan M GomeesSelman, Rex Ying, and Jure Leskovec. Identity-aware graph neural net- works. In Proceedings of the AAAT conference on artificial intelligence, volume 35, pp. 10737-10745, 2021.
Dingyi Zeng, Wanlong Liu, Wenyu Chen, Li Zhou, Malu Zhang, and Hong Qu. Substructure aware graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 11129- 11137, 2023.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivily. arXiv preprinl or Xiw:2301.09506 2023.
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.
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 Newrel Information Processing Systems, volume 34, pp. 15734 15747. Curran Associates, Inc., 2021. URL http:::/ http://///....e.aaee.e.aaaaaaaaa
neur cc/paper files/
pdf
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.
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. Aduances in Neural Information Processing Systems, 34: 9061 9073, 2021.
Ruochi Zhang, Yuesong Zou, and Jian Ma. Hyper-sagun: self-attention based graph neural network for hypergraphs. arXiv preprint orXiv: 19100661,, 2019.
Simon Zhang, Soham Mukherjee, and Tamal K Dey. GEFL: Extended filtration learning for graph classifi- cation. In Learning on Graphs Conference, pp. 16-1. PMLR, 2022.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the aaai conference. on artificial intelligence, volume 35, pp. 11015 11023, 2021.
Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: A survey, arXiu preprint arXiv:2202.08871. 2022.
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. AT open, 1:57 81, 2020.
28

---

Published in Transactions on Machine Learning Research (11/2024)
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 (WT-1) algorithm is an isomorphism testing approximation algorithm. 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 graph G = (X, A) (a pair of the set of node altribules and the graph's adjacency structure):
h. +- Xo, Vu E VG hot +- [h B (br Ve E Ve
(36)
The algorithm terminates after the vertex labels converge. For graph isomorphism testing, the concatenation of the histograms of vertex labels for each iteration output the graph representation. Since we are only concerned with node isomorphism classes, ignore this step and just consider the node labels h2 for every Vc.
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 homomorphisme 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 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 vector representation for each node. A GNN must use some initial node altributes 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 al. (2020): Wu et al. (2020).
A.2 Link Prediction
The task link prediction on graphs involves the prediction of the existence of links. There are two kinds of link prediction. There transductive link prodiction where the same nodes are used for all of train validation and lesting. There is also inductive link prediction where the test validation and training nodes can all be disjoint. Some existing works link prediction include Zhang & Chen (017)) Higher order link prediction is generalization of link prediction to hypergraph data.
A common way to do link prediction is to compute 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:
MS {u, v}) = a ahh hw)
(37)
29

---

Published in Transactions on Machine Learning Research (11/2024)
where S is pair of nodes. As shown in Proposition B.4 this guaranteems equivariant 2-node represen-
tation but can often give false predictions even with fully expressive node-based GNN Wang et al. (0233
A common remedy for this problem is to introduce positional encodings such as SEAL Wang et al. (2022)
and DisodiggEncoddngg 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 compute 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 expres- sivity, 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. considers randomly dropping edges and generating data through a generative model on hypergraphs. The work of Loe & Shin (2022) also performs data augmentation on a hypergraph so that homophilic relationships are maintained. does this through contrastive losses the node to node, hyperedge hyperedge and intra hyperedge level. Neither of these methods provide guarantees for their data augmentations.
As mentioned in the main lext, an ensembbe of neural networks can be used with a drop-out Baldi & Sadowski (2014h like method on the output of the Algorithm. Subgraph neural networks Alsentzer et al. (2020) et al.
lan
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
ct al. 2022;; Chien al. (2021): Bai al. (2021): Li al. (2023a): Arya et al.) (020)).
30

---

Published in Transactions on Machine Learning Research (11/2024)
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 hypergraph and its corresponding matrix represenlation called the slar expansion matrix::
Definition B.1. An undirected hypergraph is pair H (V,E) consisting of a set of vertices V and set of hyperedges & _ where 2 is the power set of the vertez set V.
Definition B.2. The star expansion incidence matrix H of hyperggrphh H. = (V,8) is the [V] x 2 2 0-1 incidence matrix H where H = iff for (v,e) E V & for some fixed orderings on both V and 2
We recall the definition of an isomorphism between hypergraphs:
Definition B.3. For two hypergraphs H and DD structure preserving map P H D is pair of maps (pv Vx + VD.PE Ex - ED) such that Ve E Ex,pe(e) (ov(e:) hypergraph isomorphism is structure preserving map = (pv, PE) such that both Pv and Pe are bijective. Two hypergraphs are said to be isomorphic, denoted as H = D, if there erists an isomorphism between them. When H = D, an isomorphism is called an automorphism on H. All the automorphisms form a group, which we denole as Aul(H).
e) E ED. A
The action π E Sym(VV on the star expansion adjacency matrix H is repeated here for convenience:
( e. (u................... Hx (() (0))..... ((xx))
(38)
Based on the group action, consider the stabilizer subgroup of Sym(V) on the star expansion adjacency matrix H defined as follows:
Slabsym(v) {-r E Sym()) π H = H}
(39)
For simplicity omit the lower index when the permutation group is clear from the context. It can be checked that SHab(HI) I Symn(V is subgroup. Intuitively, Stab(H) consists of all permuations that leave H fixed.
For a given hypergraph H = EV,E), there is a relationship between the group of hypergraph antomorphisms (ut(H) and the stabilizer group Stab(H)) H)) on the star expansion adjacency matrix. Proposition B.1. (u) = Stab(H) are equivalent as isomorphic groups.
Proof. Consider E Aut(H), define the map 4 := plv(1)- The group element E Sym(VV acts as a stabilizer of H since for any entry (v, e) in H, Hx-1())=--10) = (a H)u,e = iff ा T E Ex iff e E Ex iff Since (v, e) was arbitrary, æ preserves the positions of the nonzeros.
Ho,c = = Heex=
We can check that & well defined injective homorphism as restriction map. Furthermore is surjective which is equivalent to e E & iff T(v) E (e) E E which implies E E iff (e) E Thus & is a group isomorphism from Aut(H) to Stab(H)
since for any Stab(H), must have Hy 1 iff (π H)v,e Hz-1(0).=-66
In other words, to study the symmetrics of given hypergraph H. we can equivalently study the auto- morphisms Aul(H) and the stabilizer permutations Slab(H) on its star expansion adjacency matrix H. Intuitively, the stabilizer group < Slab(H) < Sym(V) characterizes the symmetries in a graph. When the graph has rich symmetries, say a complete graph, Stab(H) = Sym(V) can be as large as the whole permutaion group.
Nontrivial symmetries be represented by isomorphic node sets which define as follow:
31

---

Published in Transactions on Machine Learning Research (11/2024)
Definition B.4. For given hypergraph H with stor cxpansion matriz H, two k-node sets S,T V are called isomorphic, denoted as S =T, if 3t E Stab(H), (S)) = ' and π TT) = S.
When & 1, we have isomorphic nodes, denoted # for E V. Node isomorphism is also studied the so-called structural equivalence in Lorrain & White (1971). Furthermore, when S = T we can then say that there matching due to the graph of the map of the form {(s, (s)) E S). This matching is between the node sets S and so that matched nodes are isomorphic.
Definition B.5. A k-node representation h is k-permutation equivariant if:
for all E (V), S E 2 with [S] = l((T S, H) π -H) Proposition B.2. If k-node represenlation h is k-permuuattion equicariant, then h is k-node invariant.
Proof. given S, S E EC with |S| = |5 = k.
if there exists a π E Stab(H) (meaning क H = H) and x(S) = S" then
h(S", H1 = h(S", π H) (by π H H) h(S H) (by k-permutation equivariance of and m(S) S')
(40)
We revisit the definition of the symmetry group of k-node representation map on hypergraph H.
Definition B.6. For h: [V]* Zng Znx2" + Rdd a k-node representation on a hypergruph H.
Sym(h) A { E Sym((V x(S) = h(S H) = ,))}
(41)
32

---

Published in Transactions on Machine Learning Research (11/2024)
B.2 Properties of GWL-1
Here are the steps of the GWL-1 algorithm on the star expansion matrix H is repeated here for convenience:
+ 0.1% - 0
fett (. Ve E E(H) h < ((, f(t " Brees Ve E V(H)
(42)
Where {H) denotes the nonzero columns of and 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.
(ff B. = H( Weeee if (Se Bree) = (8" Wh Beee)eee E E(H) and BBEe) (W [0 let1 Bete (11 pitt Bose i0l (he Weet'Beee)
(43a)
' BoEe)Vo V(H)
(43b)
Proof. Equation 43a
follows since
[( h2) BuEe = ((f Be
(44a)
ill f Ie and CheBre.
(44b)
iff (fé, Gh (f:: Ne
(44c)
For Equation 43b
we have:
[( BuEe =[(h (1 frttt Roeeoe p V(H)
(45a)
iff (M) (( B. Q(W' (( e ". Wueeee E V(H)
(45b)
iff h4 n², and (fa: (1t Huse,ee = [(f c: Bheerve V(H)
(45c)
iff hr = h" and ffa B= {f= B V(H)
(45d)
These follow by the definition of multiset equality and since there is no loss of information upon factoring out constant tuple entry of each pair in the multisets.
Proposition B.3. The update steps of GWL-1: ((H) A (H), ... St (H) and h² A
hi, (H),..., hrs (H)), are permutation equivariant; in other words, For any x Sym(V), let π f' & h (H)), we have vi N, (H)
[ft (e))))))(H) (H), S fa-)(e.)) (H) and π (HH) & [ (,)
(H), (H),
fi( and π (H) (7 H)
Proof. We prove by induction on i:
Base case, i i= 0:
= 0 0= (e) (v))-_ (w))..)))) (H) f0 H) since the æ cannot affect a list of empty sets and the definition of the action on defined Equation 38
(H))
Jn (x)) JT X]. Xx-1(n) ho 1(0 (H) 1g H)) by definition of the group action Sym(V) acting the node indices of node attribute tensor as defined in Equation 38
Induction Hypothesis:
m (HH)] (H) fi(m H) and [ NHHH),
h (T H)
(46)
Induction Step:
33

---

Published in Transactions on Machine Learning Research (11/2024)
(e++(((H (H)}, [(T (
[([T ((T=- (H)),, U((T (e) ta (H))) Buee)) BoEe
(47)
(T) H), ((f(( H), ML(T H)) Ooee
( H)
F (H)) [(TT (HH))e (ar (H)))) (fé(T H), hi(T B)Beee
(48)
fet1(m (T)
Definition B.7. Let h [v] x Znx2" - RRd. be the star expansion adjacency matriz of H for nodes. The representation h k-node most expressive if YS,S' C |S
RR be a k-node representation on a hypergraph H. Let H E Z ZXx2"
|S| = |S| = the following two conditions satisfied:
is k-node invariant: Er E Stab(H), = = = h(S, H) = b(S',H)
2. h is k-node expressive dn Slab(H), x S hs H) + h( H)
Let AGG be a permutation invariant map from a set of node representations to lRd
Proposition B.4. Let h(S, = AGGves [,; (H) with injective AGG and hi, permutation equivariant. The representation h(S, H) is k-node invariant but not necessarily k-node expressive for S set of k nodes.
Proof. 3m Stab H) s.t. (SS) S', =
+ ((() = o/f for = 1,...,,11... 18,, H H
= (/) (H) = ( H) = (H) (By permutation equivariance of h and π H ===00 =H H)
AGG [ht (H) AGG of [kt (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, A(S,H) implies the existence of permutation that maps S to S" (see Zhang et al. (2021)).
A hypergraph can be represented by a bipartite graph By,g from V to & where there is edge ev,e) in the bipartite graph iff node is incident to hyperedge This bipartite graph By,e is called the star expansion bipartite graph.
We introduce 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.8. A 2-colored isomorphism is a graph isomorphism on two 2-colored graphs that preserves node colors. In particular, between two graphs G1 and G2 the vertices of one color G must map to vertices of the same color in G2. is denoted by =
A bipartite graph must always have a 2-coloring. In fact, the 2-coloring with all the nodes the node bipartition colored red and all the nodes in the hyperedge bipartition colored blue forms canonical 2- coloring of By.g. Assume that all star expansion bipartite graphs are canonically 2-colored.
Proposition B.5. We have two hypergraphs E1) (V2, Ex) iff Bv, Re By, where By,g is the star expansion bipartäte graph of (V,E)
34

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. Denote L(Bv,,e,) as the left hand (red) bipartition of B to represent the nodes V; of (Vi, and R(By,,e;) as the right hand (blue) bipartition of By,,; to represent the hyperedges & of (V; &.). We use the left/right bipartition and V.YE, interchangeably since they are in bijection.
= there an isomorphism π V1 - V2, this means
is bijection and
has the structure preserving property that (u1...,, ux) E E iff (T(UI),... .... T(u))) E Ez.
We may induce 2-colored isomorphism n²" V(Bv,,,, V(By, so that X² (1( ()) = where equality here means that x" (L))) acts on (((Bv,,,) the same way that does on V/. Furthermore n' has the property that x² ="]n(, (e) (",,,.... uz) = (TT()), (ux)), V(ui,..., up.) E &,, following the structure preserv- ing properly of isomorphism m
The map x² is a bijection by definition of being an extension of bijection.
The map xt is also 2-colored map since it maps &( to L(Bv,,s)) and R(By, to R(Bv,,aa)
We can also check that the map is structure preserving and thus 2-colored isomorphism since (ug, (u1...., My..,,,...... Uy...., uz)) & E( ), Vi = I...., k iff (u; E V1 and (u1...., V...,........ Wi.... ux) E & iff x(u,) E V/ and (T(#1),,, (w.)...., T..,,T((uu (wx)) E & iff (u,), (T,, (T"(,,, "iat.,,,,n... ux)) E ((B), Vi l,...k. k. This follows from x being structure preserving and the definition of x²
If there 2-colored isomorphism n² By,, + Byr then it has the propertics that
n² is a bijection,
(is 2-colored): T' (l(((,))) L(Br,e,) + L(Br,,e) and x T'I((( R(Bv,,,,) + R(Bv,,s))
(it structure preserving): (ui, (ui, ui,... ux)) E E(By),,);; 1, iff (T"( T" (" .,.,,.,,, ux)) E EBB,,, I,...,
This then means that we may induce V1 V/2 so that 7=" [((B))))) We can check that π is a bijection since π is the 2-colored bijection 'T restricted to L(By,,.,) thus remaining bijection.
We can also check that n is structure preserving. This means that (ui...., uk) & iff (us (Miy..., uis... uk)) E (By,,,, )ii = I,.... & ifT (m" (ux), (T7" (u.,..,, "i, ux))) E(By,,,,, iff (T (T()), ..., (uu)) E2
Vii Vi== 1,.... ifl (7 (ui,..., ux)) E R(Bv
We define a topological object for a graph originally from algebraic topology called a universal cover: Definition B.9. [Hatcher (2005)) A universal covering of connected graph G is (potentially infinite) graph G, s.t. there is a map PG G + G called the universal covering map where: Vx V()), paIN(s) is an isomorphism onto N(pa(z)).
2. G is simply connecled (a tree)
A covering graph is graph that satisfies property 1 but not necessarily property 2 in Definition known that a universal covering & covers all the graph covers of the graph G. Let T". denote a tree with root x where every node has depth r. Furthermore, define a rooted isomorphism G2 Hy as an isomorphism between graphs G and that. maps x to y and vice versa. We will use the following result prove a characterization of GWL-1:
B.9 It is
Lemma B.6 Krebs & Verbitsky (2015)). ). Let and S trees and x E VTT) and y E V(S) be their vertices of the same degree with neighborhoods N(x) = {#1, ... 2x} and N(y) (yi.... yr). Let r 2 Suppose that -x-1 2 St. and Tr 2 Sy for all < k. Then T e +1+1
35

---

Published in Transactions on Machine Learning Research (11/2024)
A universal cover of 2-colored bipartite graph is still 2 colored. When we lift nodes and hyperedge nodes to their universal cover, we keep their respective red and blue colors.
Define a rooted colored isomorphism Th =e Th as a colored tree isomorphism where blue/red node ēτ /0 maps to blue/red node ē2/0z and vice versa.
In fact, Lemma B.6 holds for 2-colored isomorphisms, which we show below:
Lemma B.7. Let T and be 2-colored trees and x E (T) and y E (SS) be their vertices of the same degree with neighborhoods (x)) = {ar,.... .... ".) and N(y) fu...... ynd- Let r 2 Suppose that T _ Sy and TH = Sy for all i k. Then T =e St.
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 the root must match in color.
If T _e Sy and Th =e ST, for all S k and ((x) {51, -. must match in color. The neighborhoods (xx) and (y)) then must both be of the opposing color. Since rooted colored isomorphisms are rooted isomorphisms, we must have T--1 S and T = Sy for all < k. By Lemma B.6. we have T _ S Once the roots match in color, rooted tree isomorphism is the same as a rooted 2-colored tree isomorphism. Thus, since x and y share the same color, T = St+1 J
(w) Tk),, N
[yi- the roots æ and y
Theorem B.8. Let H1 E1) and H2 E2) be two connected hypergraphs. Let Bv, and Bv, be two canonically colored biportite graphs for Hi and Hz (vertices colored red and hyperedges colored blue)
For any E zt, for any of the nodes Iı E By E By, and x2 E Bv E Bv2
(Bii = (BVg,)) 82 10 Sé, =fez
e = (eee),) iff hi, = h
with fi the ith GWL-1 values for the hyperedges and nodes respectively where er = PB (e1); 21 e (ø1), = es (e2), x2 = pB (ă2). The maps PBv, Bvr,E + Byi PBv, BBr + By are the universal covering maps of By and By respectively.
Proof. We prove by induction:
Let The = (B), (D),,) where é is pullback of hyperedge, meaning PBv,ee (2)) = Similarly, let TA = (o THe (B),,) THe (d), Wk N, whore é, E2 3z, 82 are the respective pullbacks of eI, 21,
Define (2-colored) isomorphism of multisets of graphs to mean that there exists bijection between the two multisots so that each graph in one multisct is (2-colored) isomorphic with exactly one other element in the other multiset.
By Observation we can rewrite GWL-1 as:
12 1. +
(49)
ltt1 + (Jé, (lilbre E En
(50)
hit1 + (h), Usit1 W Boee)Vo E Vn
(51)
Base Case i = 1:
Th. ~ Til iff (Th, =e To, and NTD BaIEN(E)) Se HTO (a)))( (By Lemma B.7
(52a)
iff (fe, = for and (h B = (he }) (By Equation 49
(52b)
ift Sl. S2, (By Equation 50
(52c)
36

---

Published in Transactions on Machine Learning Research (11/2024)
Th = T iff (T _ S and &T (eJN(E))))) S TT (ege(sa)))) (By Lemma B.7
(53a)
ifT (M2, N2 and (S2,) &s Bb) (By Equation
49
(53b)
iff foz = foz (By Equation 51
(53c)
Induction Hypothesis: For i 1, T = T ist Laz Loz and Tee = T iff hi =112
Induction Step:
T 2 = T2tt1 iff (T2) 22-1 = 2:-1 and (T (a) Se (EE (By Lemma B.7
(54a)
iff (fé, fex and ( B Che B) (By Induction Hypothesis)
(54b)
ifl Set = -e+ (By Equation 50
(54c)
22 =e T2; iff (T2) = 2 and [T?
21 BGEN(E))) =e TT? 2i-i-11
((GEN(2))) (By Lemma B.7
(55a)
R1
iff (h hi and (.f B fff B) (By Equation 49
(55b)
iff hi, = hi, (By Equation 51
(55c)
We write here the theorem characterizing the WL-1 algorithm on a graph by the graph's universal cover.
Theorem B.9. Krebs & Verbitsky (015)] Let G and H be two connected graphs. Let pG G - G,PH
H + H be the universal covering maps of G and respectively. For any E N, for any lwo nodes x E G and y E H: G = Gi iff the WL-1 algorithm assigns the same value to nodes x = Pa(ă) and y = PH
It follows immediately from Theorem that that the WL-1 algorithm on colored star expansion bipartite graphs of two hypergraphs corresponds to constructing their universal covers.
Corollary 2. Let Hi = EV),E, and H2 (V2, be two connected hyperrguphs. Lel By, Es and B be two canonically colored bipartite graphs for Hi and Hz (vertices colored red and hyperedges colored blue). Let pBv,.s, Bv + P.Bu.ee Bu + Br the universal coverings of By and By respectiucly. For any E Z+,
(BV), = (B3r,)) s. iff gin = I
with go, S'z the i-th WL-1 values for v1 E V(By,,E)) V(Bu,,,) respectively where V1 = PBv, ss (01), U2 = PBv, (7z).
Furthermore, for i 2,
2+ -
9uz
2+i iff 1+ = 144 Vun E L(Bv, ..) Yuz E L(Bv,,e) and
2++ 2+h iff 12+1 =
= 1241, Ver E R(By, & Vez R(Bv,.s)
Proof. The first equivalence ( )o, S (B2i-1 (B b2 iff gt, g follows directly by Theorem 2
The successive two equivalences follow by Thcorem B.8 and the first equivalence.
Observation 3. If the node values for nodes x and y from GWL-1 for iterations on two hypergraphs Hi and H2 are the same, then for all j with < j $ i, the node values for GWL-1 for j iterations on x and y also agree. In particular deg(z) deg(y).
37

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. There is 2-color isomorphism subtrees (B s ) and (B% of the i-hop subtrees of the universal covers rooted about nodes 2 E V1 and y E V2 for I j S i since (B e, )a = (Big,e))- By Theorem B. we have that GWL-1 returns the same value for a and y for each 0 S ii.
Theorem B.10. Let h² [V]] x 22 zRx2" + R2d be the L-GWL-1 representation of nodes for hypergraph H in Equation then
AH)(H) = Stab(H) _ Sym(h" = Aut (222)
(56)
Proof. 1. Aut(H) Stob(H) follows by Proposition B.1
2. Stab( H) (y)( follows by definition of the symmetry group of representation map given in Definition B.6 and the equivariance of L-GWL-1 due to Proposition B.3 Let Set denote the collection of all finite sets. We know that
(S, H) & (GG((
(57)
for AGG Set + Rd an injective set representation map and that S has cardinality For any π E Stab(H) S Sym(V), we must have H H we check that π satisfies:
π tuu)= + h(u, = h(v, H), VE
(58)
If (w) v and π H. we can use the oquivariance of h4 to get right hand necessary condition:
4- (", H) h² (u, π (H)) (=((),, = (r H)
3. The last group isomorphism follows by the equivalence between L-GWL-1 and the universal cover up to 2L-hops given in Theorem B.8
For any π E (H)), it must satisfy Tuu) = v = h(u, H) = M(U, H), Vu, E V. We map each π to a 2-colored isomorphism : + Oe which is the 2-colored isomorphism determined by the Theorem B.8
(By.) N (B x(u))
((ي))
iff hh (n(( = h" H) 11 V
(59)
Certainly the map t - de is a homomorphism because:
1. & maps the identity identity:
(B% aa 2. (BPr))a ill 1/2 = h² h", H), Vu EV
(60)
can have only one 2-colored isomorphism determining (B a = (BVte)a, which is the identity.
2. t perserves composition: T2 o n + (Ø2) (01)e
By definition of mi and n2:
(u) U + hu, H) M(v H) iff (B = (B Yu E
(61a)
m)())
(2(1) = w + h(u, H) = h(w. H) iff (B2Le)s = (B2r.) - EV
(61b)
Combining, we get:
(B aa = (BV,2) = (B (w)
(B m (u)
(62)
where the first isomorphism (d1) on (B2L)) )u, the second isomorphism from (122) on (Bbte)a and the third isomorphism is (g1) (ei)e on (B2L) V.8 k7( -,70)
Proposition B.11. Tf GWL-1 cannot. distinguish two connected hyperyraphs H. and H2 then HyperPageR ank will not either.
Proof. HyperPageRank is defined on a hypergraph with star expansion matrix H as the following stationary distribution II:
lim (D=1 1 H. D -1"==
(63)
n2000
38

---

Published in Transactions on Machine Learning Research (11/2024)
If H is connected bipartite graph, II must be the cigenvector of (D,' Н De H²) for eigenvalue 1. In
other words, IT must satisly
(D²² (D...H.. -
(64)
By Theorem of Huang Yang 2021 we know that the UniGCN defined by:
het1 + 62 k() = We HH hh
(65a)
h t 01 )(+2)= = W. H . h141
(65b)
for constant We and W, weight matrices, equivalent to GWL.1 provided that Φi and Φ2 are both injective as functions. Without injectivity, can only guarantee that if UniGCN distinguishes H1, H2 then GWL-1 distinguishes H1, H2. In fact, cach matrix power of order in Equation 63 corresponds to h so long as we satisfy the following constraints:
W. D W, D and h2 +-
(66)
We show that the matrix powers UniGCN under the constraints of Equation 66 by induction:
Base Case: 0: hg I
Induction Hypothesis: n > 0:
= h (D H D. -²
(67)
Induction Step:
(D,1 11 h())
(68a)
=D, . (DD= H H (b)))
(68b)
= (D H DD H
(D H D TT
(68c)
n+1 = -D H D )m = h
(68d)
Since we cannot guarantee that the maps Φ1 and d are injective Equation 68b must be that the output
hy, coming from UniGCN with the constraints of Equation 66 at most as powerful as GWL-1.
In general, injectivity preserves more information. For example, if Φ1 is injective and if oi arbitrary map (not guaranteed to be injective) then:
& (h1) di (h2) h h2 of (h1) 0i (h2)
(69)
HyperpageRank is exactly powerful UniGCN under the constraints of Equation 66 ank is at most powerful GWL-1 in distinguishing power.
Thus HyperPageR
]
39

---

Published in Transactions on Machine Learning Research (11/2024)
(B0g)e...2
(Beg
(Bog
(B 2011
2.3
Wic
e'o.1
17.0
50.12
61,2,
$1.28
PB 28
PB c
PB cg
PB
824
50,2,,
6'0,3,
G.
wa
13
6'0,,,
50,1,2,3
6'u3,2344
3.0
B B
C (V, (b)
C
EV,
Cg V E (d)
C (V 8 ((V)) (e)
(a)
(f)
Figure 5: An illustration of hypergraph symmetry breaking. (c,d) 3-regular hypergraphs C₁, Cg with and 5 nodes respectively and their corresponding universal covers centered at any hyperedge (Bog )e..... (Bog)e.....
with universal covering maps PB (b,e) the hypergraphs C1. Cg which are Ca, C3 with 5-sized hyperedges attached them and their corresponding universal covers and universal covering maps. (a.f) are the corresponding bipartite graphs of Ö2, Cg. (c,d) are indistinguishable by GWL-1 and thus will give identical node values by Theorem B.S. 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:
Algorithm A Symmetry Finding Algorithm
Data: Hypergraph 7 = (V,E), represented by its star expansion matrix H. L E Z+ is the mumber of iterations to run GWL-1.
Result: A pair of collections: (Rv = (Vn,), R, Ræ = Uy(En,)) }) where R, are disconnected
subhypergraphs exhibiting symmetry in H that are indistinguishable by L-GWL-1.
Edeg {(deg(v) E c} Ve e E}
2 UL + 9 + [Uz[u] Vu E V};
/* Uz is the L-CWL-1 value of node C V. */
Byn En Bipartite(H)) /- Construct the bipartite graph from H.
Ry t (); Rg +
for CL E2 do
VoL + {u E V: Ur|u] = ct), + E Voz Vu E
Co, + CommectedCoomponnnts/
= Eer)
for Rend E Coo, do
Rv t Ry U (fRR,,. :: Rg t Re ER.
10
end
end
return (Rv, (Rv
We also repeat here for convenience some definitions used in the proofs. Given hypergraph H = (V,E), let
Vez {ue V: = (H)
(70)
be the set of nodes of the same class as determined by L-GWL-1. Let He, be an induced subgraph of H. by Ve,-
Definition B.10. A L-GLL-1 symmetric induced subhypergraph R C. H. of H. is a connected induced subhypergraph determined by VR S VH: some subset of nodes that are all indistinguishable amongst each other by L-GWL-1:
N (HT, Vu, VR
(71)
40

---

Published in Transactions on Machine Learning Research (11/2024)
When L oC, we call such R GWL-1 symmetric induced subhypergraph. Furthermore, i H. then say H is GWT-1 symmetric.
Definition B.11. neighborhout-regniee hyperyraph is a hypergraph where all neighhorhoods of each node are isomorphic to each other.
Observation A hypergraph H is GWT.11 symmmetrie if and only if it is I--GWI-1 symmetrie for all I. 2 if and only H neighborhood regular.
Proof.
1. First if and only if
By Theorem B.8 GWT-1 symmetric hypergraph H (V,E) means that for every pair of nodes u, e V. (Bv,g)e Se (By,s)o. This implies that for any L 2 1, (BV,)) a _ (B by restricting the rooted isomorphism to 2T-hop rooted subtrees, which means that (H) (H). The converse is true since I is arbitrary. If there can be constructed for L = oo by infinite extension.
cycles, can just take the isomorphism for the largest. Otherwise, isomorphism
2. Second if and only if
Let pBv.e be the universal covering map for By,g, Denote ū, ū by the lift some nodes v, u E V by PBv.s"
Let (a))) be the rooted bipartite lift of (N(u)) If H is L-GWT-1 symmetric for all 2 1 then with L 1, (B%,e)a = (N(u))a = (N(v)) _ (B, iff (N(u)), = (N(v)) Vu, V since N(u) and N(v) are cycle-less for any u, E V. For the converse, assume all nodes v E V have (N())) = (N'), for some 1-hop rooted tree (N'), rooted at node x, independent of any v E V. We prove by induction that for all L 2 1 and for all V, (Byte) = (N for 2L-hop tree (Nr2), rooted at node x.
Base case: == 1 is by assumption.
Inductive step: If (B2L. = (N2)) 2L-th layer of (B%)e)s a) =e (N2L).- Each (N(w))a is independent of the root since every u E V has (N(ā))& = (N²), iff (N(ū)) = (N²)2 for an independent of V. This means (B2L.t) = (N2L+22, for the same root node x where (N2L+2), is constructed in the same manner as (B%)e) Vu E.
form (B by attaching (N(ū)) to each node å in the
Proposition B.12. Let H (V,E) be a multi-hypperraph.
A huppi-hhpprrrrap isomorphism, like for hypergraphs, is defined by a structure preserving map (pv : VH VD, Pg: Ex + Ep) but where Pe is bijection between mullisets.
The star exponsion bipartite graph of the multi- hypte-hyperggaph H: Bygg, is defined before the bipartite graph with vertices V and edges (v.e) E V x uiued e}.
With these definitions on multi-hugpergraple Proposition multi- hulti-hypergrrphs.
B.5 Theorem
B.8 and Corollary
2 also hold for
Proof. In the proposition, theorem and corollary, replace the set with the multiset & and the proofs become identical.
B.3.1 Algorithm Guarantees
Continuing with the notation, as before, let H. = (V,E) be a hypergraph with star expansion matrix and let (Rv, RR) be the output of Algorithm on H for L E Z+. Denote Cc,, as the set of all connected components of Hezi
Ce, A (Ce, conn. comp. Ce, of Har) If = oc, then drop the L. Thus, the hypergraphs represented by (Rv, Re) come from Co, for cach Cp. Let:
(72)
Hr A (V,EURv)
(73)
41

---

Published in Transactions on Machine Learning Research (11/2024)
be H. after adding all the hyperedges from Ry and let H1 be the star expansion matrix of the resulting multi-hypergraphh Hr. Let:
GL _ (he [
(74)
be the set of all L-GWL-1 values on H. Let:
Va - (u E Ve, : E R, R Coy: Vnl =
(75)
be the set of all nodes of I-GWI-1 class ep belonging a connected component in Coz of s 2 nodes in H the induced subhypergraph of T-GWT.11. Let:
SeL - (VRRzall: ReL, E CeL}
(76)
be the set of node set sizes of the connected components in Her.
Proposition B.13. If L 0c, for any GWL-1 node value for H. the connected component induced subhupergraphs Re,is for = .,. [Cdl are GWL-1 symmetric and neighborhood-regulon
Proof. Let pBv. be the universal covering map for By Denote 0, ū, U' ÿ by the lift of some nodes D, u, v', u' E EV by P
Let L 00 and let He = Ed) For any i, since u E Ve, (Bv,e)u =c (By,e)o for all u, VR.." Since Re, is maximally connected we know that every neighborhood (H.(u) for E Ve induced by H. has NH.(u) = (()) n He. Since L = oo we have that NH, (u) = (N), Vu, VR.. since otherwise WLOG there are w/, of E Vn.,. with Nw. (u') F Nr. (v') then WLOG there is some hyperedge e E &Nn, (w" with some w e, w + u' where cannot be isomorphism with any E ENN 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 & between NH. (u'), Nu'))) to one of the hyperedges. This means that (Bv((w),)) is the rooted universal covering subtree centered about w not passing through u' that is connected to u' E (By,)) by e. However, o' has no e and thus cannot. have Tn for x E V(N(e))). satisfying T2 _ (Byy(u))e) with connected to e' by hyperedge e' isomorphic to in its neighborhood in (Bv.g)v. This contradicts that (By.s) = (By.e)s..
We have thus shown that all nodes in Ve have isomorphic induced neighborhoods. By the Observation this is equivalent to saying that Re is GWL-1 symmetric and neighborhood regular.
We show the partitioning of H by Algorithm 12
Proposition B.14. If L 1, the output (Rv, Re) of Algorithm 7 partitions subgraph of H. meaning:
V LIVERV V and C L
(77)
Proof. = LiveRy
For given subset of nodes U/ C V, let ComectedCoomonentsss. (4) be the collection of node subsets of U4 where each node subset forms connected component in H.
Let h (H) denote the L-GWL-1 node value of v E V.
Let (L) & Uney ComneceedComponentts, ((u E V: h!) = h!(HH)) denote the collection of node sets of common I-GWT.-1 values for given T..
By the definition of Ry, since every connected component is size atleast 1 and every node considered, we must have Uvey Ry = V. Since each connected component of given GWL-1 value is maximal, meaning there is no superset of nodes that is connected, two connected components can intersect through either nodes or hyperedges. Furthermore, single node can belong to only one GWL-1 value, thus the values form a partition of V. This proves V = UVVR,
2. E:
This follows since Rg are the hyperedges of each connected component spanned by Rv. These connected components form disconnected subhypergraphs of H.
42

---

Published in Transactions on Machine Learning Research (11/2024)
Prediction Guarantecs:
In order to guarantee that the GWL-1 symmetric components Re found by Algorithm 12 carry additional information, there needs to be a separation between them to prevent an intersection between the rooted trees computed by GWL-1. We redefine from the main paper what it means for two node subsets to be sufficiently separated via the shortest hyperedge path distance between nodes V as follows:
Definition B.12. Two subsets of nodes U1 C V are sufficiently L-separated if:
min 2,,42
v() > L
(78)
where d(v1, v2) _ EE k is the shortest hyperedge path distance from in E to U2 EV. A collection of node subsels C C 2 is sufficiently L-sspporated if all pairs of node subsels are sufficiently L- L-separated.
Our definition of sufficiently L-separated is similar in nature to that of well separation between point sets Callahan & Kosaraju (1995 in Euclidean space.
We give another definition that will be useful for the proof of the following lemma:
Definition B.13. slar graph N₂ 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.
Assuming that the Cc,, are sufficiently L-separated from each other, intuitively meaning that no two nodes from two separate VR.z.. E Ry are within L hyperedges away, then the cardinality of each component (RRe,al is recognizable.
Lemma B.15. If L Zt is small enough so that after running Algorithm on L, for any L-GWL-1 node class er on V the collection of Cos is sufficiently L-separated,
then after forming AL, the new L-GWL-1 node classes of Vor i = I,..,Coo, Co. in He are all the same class eg but are distinguishable from depending on (VRei.al.
Proof. After running Algorithm on H = (V,E), let Hr. = -Vi, & (V be the hypergraph formed by attaching a hyperedge to each VR.g..'
For any CL, L-GWL-1 node class, let Rez,i = 1,... /Cell be a connected component subhypergraph of Hez. Over all (c pairs, all the Rez are disconnected from each other and for each er each Rez is maximally connected on Hez.
Upon covering all the nodes VR.,.. of cach induced connected component subhypergraph Rey, with single hyperedge e = VR.g.. of size = IVRe,.. we claim that every node of class ey becomes CL,s, a L-GWL-1 node class depending on the original L-GWL-1 node class eL and the size of the hyperedge s.
Consider for cach u E VR.gi the 2L-hop rooted tree (BoLe)a for psv.e (0) v. Also, for cach v E VR.g.. define the tree
T. 22--1 e
(79)
We do not index the tree Te by u since it does not depend on E VR.g... We prove this in the following.
proof for: Te does not depend on E V
Let node be the lift of e to (B2L-1) Define the star graph (N()))a as the 1-hop neighborhood of in (B31-1) )e. We must have:
(B =. ((N()))a u
U
(B2L--) 2a)a
(80)
iEV
Define for each node v E e with lift ū:
(N(2, A (Vivee)) \ (T), \ ((),))))
(81)
43

---

Published in Transactions on Machine Learning Research (11/2024)
The tree (N ú)); is star graph with the node e deleted from (N())).. The star graphs (N(è, 6)) S (N)) do not depend on 8 as long as ö E V(N(E))) In other words,
(N 8)); = (Ni(, De. Vū, d' e ViNTE \ (é)
(82)
Since the rooted tree (B )a, where is the lift of by universal covering map pBv.e: has all pairs of nodes û, E in it with (B a. = ( which implies
(B = (B "w, Vū, Ve, e
(83)
By Equations
83
82
thus have:
(B24-1 Pitol,eee = ())
U
(B ())s
(84)
BEV M6)
This proves that To does not need to be indexed by E VRE.... We continue with the proof that all nodes in VReziS become the L-GWL-1 node class Cz,a for VR
Since every e E V becomes connected to a hyperedge e = VReyA in H. we must have:
(8% = ((B3)e) U(8,8) Telo, Ve E VRaz.e
(85)
The notation ((B)))) U(a,)) Te)s denotes a tree rooted at ū that is the attachment of the tree T. rooted at to the node 0 by the edge @.. é). As usual, we assume ö, è are the lifts of v V, E & respectively. We only need to consider the single since I was chosen small enough that the 2T.-hop tree (B2L ) does not contain a node û satisfying p (ä) = u with u E VRez.s for all j = I,.... Cecl.j + Since Te docs not depend on V E VR.
(B% a = (B%,))), Vu, v E VRez.
(86)
This shows that (f(( (H), Vu, v E VRozi by Thcorem B.8 Furthermore, since each v E VR. S D in H is now incident to new hyperedge VRog..e must have that the L-GWI-1 class eL of VR. H is now distinguishable by (VRezal.
We will need the following definition to prove the next lemma.
Definition B.14. A partial universal cover of hypergraph (V.E) with an unezpanded induced subty- pergraph R, denoted UH, R)v, is graph cover of Bv,s where we freeze By S By.g as an induced subgraph.
A I-hop rooled parlial universal cover of hypergraph H = EV,E) with an unexpanded induced subbypergraph R, denoted (U' (H, R)y,)) for u E V or (H, R)v,s) for e E E, where ë, are lifts of v,e, is rooted graph cover of By.g where we freeze ByR.ER S Bvv as an induced subgraph.
Lemma B.16. Assuming the same conditions Lemmma B.15 where H = (V,E) is hypergraph and for all L-GWL-1 node classes with connected components Rezis discovered by Algorithm 4 so that L 2 diam(Ror,.) Instead of only adding the hyperedges (VRoz to E as stated in the main paper, let H4 A (V,(E) LR)), meaning H with each Rey for i = I,... |Cop having all of its hyperedges dropped and with a single lypperdgee that covers VREg. and let H = (V, EVEERRY then:
The GWL-1 node classes of VReg. for i Lc..,,CCell in H are all the same class dr, but are distinguishable from et depending on (VR.yal
44

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. For any CL: L-GWI-1 node class, let Rer,s; i 1,..,,/Ce,, be connected component subhypergraph of Hee-- These connected components are discovered by the algorithm. Over all (cr,,) pairs, all the Re are disconnected from each other. Upon arbitrarily deleting all hyperedges in each such induced connected component subhypergraph Ren,' and adding a single hyperedge of size s = IVR.,.l we claim that every node of class EL becomes C,,e a I-GWI-1 node class depending on the original the size of the hyperedge 8.
L-G L-GWT-1 node class eg and
Define the subhypergraph made up of the disconnected components Rei. as:
R = R
(87)
Since I. 2 diam(Rez,)); we can construct the 2T-hop rooted partial universal cover with unexpanded induced subhypergraph R, denoted by (H, R)v,,),, Vu of H as given in Definition [..4
Denote the hyperedge nodes, or right hand nodes of the bipartite graph by B(VR,ER) by R(B(VR. ER)). Their corresponding hyperedges are &R S E(U(H, S E. Since each Rezi is maximally connected, for any nodes u, U E VR we have:
(U2 R), R)a R((((VR ER))); = 2 (HH (H, \ R(B(VR, ER))),
(88)
by Proposition B.13 where (2H R)s \ R(B(VR, ER)) denotes removing the nodes R(B(VR, ER)) from 1,2,(,,, R)a- This follows since removing R(B(VR: ER)) removes an isomorphic neighborhood of hyperedges from each node in VR. This requires assuming maximal connectedness of each Rez.s- Upon adding the hyperedge
Coz 2 VRey.
(89)
covering all of VR.z. after the deletion of ER.z. for every (cI, i) pair, we see that any node u E VREE." is connected to any other node v E VRez.. through lez,s in the same way for all nodes u, v E VR In fact, we claim that all the nodes VR still have the same GWI-11 class.
We can write the multi- hyperrah H4, equivalently (V. (E) E(Re),)) L (ecr,+D)) which is the multi- hypergraph formed by the algorithm. The replacement operation on H can be viewed in the universal covering space By.g as taking UHH R) and replacing the frozen subgraph ByR with the star graphs (NR, R2 (), of root node Êeg, determined by hyperedge Ger,s for each connected component indexed by ()., Since the star graphs (N (Ee,,)))e,,," are cycle-less, we have that:
(UH, \ ((B(VRREx))) U UNNR (err So Bv
(90)
Viewing Equation 90 locally, by our assumptions on L, for any v E VRega we must also have:
(U (H, \ (R(B(VR, U(N (Eew)le.. =o Byn, Ex,
(91)
We thus have (B%) FR )a = (B2) V2, En, )a for every u, U. E VRegN with ū, T being the lifts of u, v by PBv.s
since (H, R)a \ R(B(VR &R)))a _ (H, R), R(B(RR ER))), for every u, E VRe,.. as in Equation 88 These rooted universal covers now depend on a new hyperedge Cen., and thus depend on its size s.
This proves the claim that all the nodes in Vie,,. retain the same L-GWL-1 node class by changing H. to H. and that this new class is distinguishable by == (VR.,al- In otherwords, the new class can be determined by c.. Furthermore, CL,s on the hyperedge eez.' cannot become the same class as an existing class due to the algorithm.
Theorem B.17. Let |V] - n, E z+ and vol(o) 2 Encesasu lel and assuming that the collection of node subsets Cap, is sufficiently L-separated.
If vol(u) O(log fo n), Vu E V for any constant e <> 0; 18,,1 S S,Yee Cr, S constant, and |Vez,ol ), Vs E Coo, then for k E z+ and k-tuple C = (CL,1, ...; CL,)), CL, E Gr L..k there exists
O 30 (x)
45

---

Published in Transactions on Machine Learning Research (11/2024)
(n22kr) many pairs of k-node sets $1 of S2 such that (H))s) (hEEs, (H)) C, as ordered k-tuples, while isS1,, HL) + h(S2, H1) also by L steps of GWL-1.
Proof.
1. Constructing forests from the rooted universal cover trees
The first part of the proof is similar to the first part of the proof of Theorem of Zhang et al. (2021)
Consider an arbitrary node E V and denote the 2L-hop tree rooted from the universal cover as (B ) as in Theorem B.8 As each node
has volume vol(e) = Ever le| = Olog 1ff n), then every edge E E has |e| (log n) and for all v E V we have that deg(t) Olog -े n), we can say that every node in (Byte) has degree d = Ollog i-s ar n). Thus, the number of nodes in (Byte) )), denoted by (V((B satisfies (((()))) S Eie d' O(dh)) Ollog 1 1z). We set K maxvev (V((()g))) )ol as the maximum number of nodes of (BVg)) and thus Ollog - n). For all V, expand trees (BV,g)s (BVe)s by adding K ( )al independent nodes. Then, all (B%,,)s have the same number of nodes, which is K, becoming forests instead of trees.
2. Counting |9/|:
Next, we consider the number of non-isomorphic forests over K nodes. Actually, the number of non- isomorphic graphs over K nodes is bounded by 2(5) = exp(O(log 1s n)) = o(n²-9). Therefore, due to the pigconhole principle, there cxist o(ni-e) w(n") many nodes whose (B% are isomorphic to cach other. Denote GL as the set of all L-GWI-1 values. Denote the set of these nodes as Vez. which consist of nodes whose I-GWT-1 values are all the same value c, E 9L after L iterations of GWT-1 by Theorem B.8 For fixed L, the sets Vez form partition of V, in other words, Len. Vez = V. Next, we focus on looking at k-sets of nodes that are not equivalent by GWT-1.
For any eg E 9t, there is a partition Ve, = U. VoL.s where VeL.. the set of nodes all of which have L-GWI- class er. and that belong to connected component of size in Hoz. Let S., A (DRRgss Regsi E Cey denote the set of sizes 2 of connected component node sets of Hez. We know that [S S S where S is independent of n.
3. Computing the lower bound:
Let Y denote the number of pairs of k-node sets S * S2 such that (h (c..,)).......a as ordered tuples, from L-steps of GWL-1. Since if any pair of nodes u, have the same L- GWL-1 values CL, then they become distinguishable by the size of the connected component in Hez that they belong to. We can lower bound Y by counting over all pairs of l tuples of nodes ((u1,.., ug), (V1..., 2x)) E (I VaL.n) ( VeL.)) that both have L-GWT-1 values (C(L,)), -. ((L.)) where there is atleast one i i [{,,.,, k) where un and ii belong to different sized connected components 8,, s/ E Soqu. with s; $ sy. We
(he (H))vvs) C'
have:
Y 2
1
Σ
II
VL Co.. IIV 1e
(92a)
M
((
I
st S
i=
Σ
IVL
Σ
vL Vo.. P)]
(92b)
M
1=1
S.ESL
(n)) E TlT ste
Using the fact that for each i E {l,..., k), Mec..ol = Ex,ESepenn (Vecene) and by assumption (en.)))
O( 12" for any E Sepay thus we have:
20
Y 2 -((S)* 2ke
log )] = 2ke
(93)
46

---

Published in Transactions on Machine Learning Research (11/2024)
Example: A simple example of hypergraph that statisfies the conditions of Theorem B.17 is union of many disconnected hypergraphs H. = U,H, (V,E) with [Vull I S where S < co is small constant independent of N = [V] 2 S. Such hypergraph could be social network where the nodes are user instances and the hyperedges are private groups. The disconnected hypergraphs represent disconnected communities where a user can only belong to a single community.
Even though Theorem B.17 does not depend on the cardinality of a set of disconnected hypergraphs Ha indistinguishable by GWL-1, due the disconnected nature of H and the small size of its components, there is a large chance of obtaining a large number of such components. We give very rough estimate of this in the following:
Assuming that H = U,H, has cach Hi i..dd sampled from distribution of s-uniform d-regular hypergraphs of n nodes, denoted Rn,,,d: P(H; = ad). If the parameters (n,,,d) d) for Rn,s. satisfy nd = |E|s where 1l E Zt, then a well defined hypergraph formed. This distribution can be factorized as follows:
P(H, Rm,dd) P(de((v) dr= = s, |V] n. nd mod 0) = s||V| P()P] n)
(94)
where:
P(deglv) = ddr== 11)r=8,17000 s.()(H)) = n, nd mod & =0 2
Vo VH.
(95a)
5$
P(r = s|[((H))))) -) -12 ->1= S'
1
P(IV(L))) =
for n. S SSN
(95b)
and we have that
1 S+2
P(Hi is neighborhood regular) 2 P(Hz is a cycle graph) 2 s
(96)
and that:
P(h(H,,H)) = h(H1, H), is neighborhood regular)
(97a)
2 (M,, H) l(HH, H), Hi is a cycle graph of length S)
(97b)
2 P(H, is a cycle graph of length P(H, is a cycle graph of length S)
(97c)
2(S+2)
vi
(97d)
where a cycle graph is a 2-uniform hypergraph where each node has degree 2.
Since we sample each H4 L..dd, the indicator random variable is a Bernoulli random variable. By Hoeffding's incquality on the sum of Bernoulli random variables, we get:
m Prt IH, is neighborhood regular and h(H,, 70) = h(H,, 70) 2 g2s+4 +t)) se
22
(98)
where Em |V = M This means that with large number of samples m, or large n, it is possible for the number of regular hypergraphs H4 equivalent up to GWL-1 to be atleast of order ((ym) + g2stz with high probability. This is one of the simplest examples that demonstrates Theorem B.17
m
For the following proof, we will denote S as node or hypergraph automorphism with respect to hypergraph H.
Thcorem B.18 (Invariance and Expressivity). If = xo, GWL-1 enhanced by Algorithm 1 is still invari- ant to node isomorphism classes of H. and can be strictly more expressive than GWL-1 to determine node isomorphism classes.
47

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. 1. Expressivity:
Let L 2 be arbitrary. We first prove that L-GWL-1 enhanced by Algorithm I is strictly more expressive for node distinguishing than L-GWL-1 on some hypergraph(s). Let C2 and C be two 3-regular hypergraphs from Figure 2 Let H= C Lg be the disjoint union of the two regular hypergraphs. I. iterations of GWT-1 will assign the same node class to all of Va. These two subhypergraphs can be distinguished by L-GWL-1 for L 2 1 after editing the hypergraph H. from the output of Algorithm and becoming 7 = O UCG. This is all shown in Figure 2 Since L was arbitrary, this is true for L co.
2. Invariance:
For any hypergraph H. let = (), be H. modified by the output of Algorithm 1 by adding hyperedges to VR...- GWL-1 remains invariant to node isomorphism classes of H on H.
a. Case 1 (node u E V has its class e changed to class cs):
Let L Z+ be arbitrary. For any node u with L-GWL-1 class changed to c2 in H. if E* for any E V. then the GWL-1 class of v must also be ca. In otherwords, both u and belong to s-sized connected components in He We prove this by contradiction.
Say u belong to a L-GWL-1 symmetric induced subhypergraph S with [Vsl = s.
i. Say y is originally of L-GWI-1 class c and changes to L-GWI-1 cy for s H. WLOG.
If this is the case then belongs to I-GWT.-1 symmetric induced subhypergraph S' with [V = s'. Since there is a π E AH)(H) with æ(u) and since s' < &,, by the pigeonhole principle some node w E Vs must have x xww) & Vgr Since S and S' are maximally connected, T(w) cannot share the same L-GWL-1 class as w. Thus, must be that (B2,)) , ((w) #e (B3))) where w x(w) are the lifts of w. x(w) by universal covering map PBy.s. However w and xww) both belong to L-GWI-1 class e in H. meaning (B% =. (Bi))) contradiction.
ii Say node v E has its class unchanged.
The argument for when v does not change its class after the algorithm, follows by noticing that since e is the GWL-1 node class of u, Ca is the GWL-1 node class of u and e = c,. Thus we must have u #H v once again by the contrapositive of Theorem B. This also gives a contradiciton.
Since was arbitrary, the contradiction must be true for co.
b. Case 2 (node V has its class unchanged):
Now assume L co. Let P8,,e be the universal covering map of By.g- For all other nodes w' Sн v' for u', e' E V unaffected by the replacement, meaning they do not belong to any Re, discovered by the algorithm, if the rooted universal covering tree rooted at node K' connects to any node i in / hops in (B) where pBv, (i') = ul, PBv. (w)) = w and where w has any class e in H. then must also connect to a node in hops in (B%,))a where PBv. = and w S z. Furthermore, if w becomes class C, in H due to the algorithm, then also becomes class e, in A. This will follow by the previous result on isomorphic w and = both of class with w becoming class C in H.
Since -= 0o: For any w V connected by some path of hyperedges to u' E V, consider the smallest for which (Bb,g)ar the Lhhop universal covering tree of H rooted at ū', the lift of u', contains the lifted w of w E V with GWL-1 node class at layer L. Since u' EH v' by т. We can use to find some 2 = T(w).
We claim that is hops away from 8'_ Since v' I of due to some π E Aut(H) with T(w') = using Proposition B.2 for singleton nodes and by Theorem B.S we must have (B =, (B),g) as isomorphic rooted universal covering trees due to an induced isomorphism क of where we define an induced isomorphism म (By.s) + (By.e) between rooted universal covers (By,e) i and (By,)er for i', &' E ((By.)) as =()) - =b if ((a)= = b Va, b E V(Bv,s) connected to u' and o' respectively and Psv.e (ā) a, PBv.e (b) = b. Since I is the shortest path distance from á' to W. there must exist some shortest (as defined by the path length in By.s)
48

---

Published in Transactions on Machine Learning Research (11/2024)
path P of hyperedges from x' to w with no cycles. Using 9, must map P to another acyelic shortest path of the same length from of to This path correponds to a length shortest path from o' to E in (By,g)
If w has GWL-1 class e in H. that doesn't become affected by the algorithm, then z also has GWL-1 class in H. since w S 2.
If w has class c and becomes G2 in H. by the previous result, since w z 2 we must have the GWI.11 classes d and d" of and in H be both equal to cs.
The node connected to u' was arbitrary and so both i and the isomorphism induced & are I hops away from V' and e' respectively, with the same GWL-1 class e' in H. thus (By,e) = (B3ge)t
We have thus shown, if u S e for u E H. then in H we have 1 = h4 (F) using the duality between universal covers and GWL-1 from Theorem B.8 and Proposition B.12
Here redefine the symmelry group of the L-GWL-1 node representation map as in the main paper:
Sym(h+((A))
n
Sym(h" (fr)))
(99)
Bi-P((B2)
Proposition B.19. The multi-hupeerraah Hy breaks the symmetry of the L-GWL-1 view of the hypergraph H:
Sym(h" (ftz)) S Auto 1L
(100)
Proof. By Equation 99 we have that Symn(h (ft.) = N8I=P(AL) Sym (HF))) Since the original inci- dence matrix H belongs to supp( (P(F))) we must have MAL-P((L) Sym(h (fF)) S (y)( Since Sy)(h+(H) = Aute (ut V.E); we thus have:
(fL(h)(BL))- = N
Sym(h+ Sym(h+(H)) = A AL 2 1 HL-P(B2)
(101)
which proves the symmetry breaking statement.
Proposition B.20 (Complexity). Let H be the star exponsion matrix of H. Algorithm runs in time O(I. + (n + m)), the size of the imput hypergraph when viewing as constant, where n the number of nodes, nn=(H) vol(V) e Evey and m is the number of hyperedges.
Proof. Computing Edeg, which requires computing the degrees of all the nodes in each hyperedge takes time (H)) The set Edeg can be stored as a hashset datastructure. Constructing this takes O(nnz(H)). Computing GWT-1 takes (H)) time assuming a constant I. number of iterations. Constructing the bipartitc graphs for H takes time O(nne(H) (H) + n + m) since is an information preserving data structure change. Define for each E C, := [Vel, m. [E,). Since the classes partition V, we must have:
Σ CEC
noj
Σ mai moinnzz(H) = I nno()ll)) CEC
(102)
CEC
where He the star expansion matrix of He. Extracting the subgraphs can be implemented as masking operation on the nodes taking time O(n.) to form V. followed by searching over the neighbors of V, in time O(m.) to construct Ec. Computing the connected components for He for predicted node class takes time O(n,- + me + mn)(H.)). Itcrating over each connected component for a given and extracting their nodes and hyperedges takes time 0(n., + +m.,) where n., = Σ, Ne, m. Σ; me;- Checking that a connected component has size at least 3 takes ((1) time. Computing the degree on for all nodes in the connected component takes time (n,.)) since computing degree takes O(1) time. Chocking that the set of node degrees of the connected component doesn't 'tt belong Edeg can be implemented as check that the hash of the set of degrees is not in the hashset datastructure for Edeg-
49

---

Published in Transactions on Machine Learning Research (11/2024)
Adding up all the time complexities, get the total complexity is:
(H)) + ((nmz(H))))))) + n + m) +
[(((ne + me + nmz(H.)) +
Σ
O(ne + mc,)) (103a)
oEC
comn. comp. He
O(nzz(H) + m)
(O me nmz O(ne mc))
(103b)
oEC
O( +
(103c)
7
Proposition B.21. For connected hyperyraph H. let (Rv, Rg) be the output of Algorithm 4 on H. Then there Bernoulli probabililies p. qi for i 1,- [Rvl for attaching covering hypperedge that ft is unbiased estimator of
Proof. Let Ce, (Rey,sh be the maximally connected components induced by the vertices with L-GWI-1 values ez. The set of vertex sets ()(Re and the set of all hyperedges (z(E(Roz,)) over all the connected
components Rez,s for = 1...., Cc, form the pair (Rv,
For a hypergraph random walk on connected H = (V,8), its stationary distribution a on V is given by the closed form:
T(v) = deg(v)
(104)
for V.
Let At EV, be the random multi-hypergraph determined by p and qi for i L.v.. These probabilities determine H by the following operations on the hypergraph H:
Attaching a single hyperedge that covers VR.,.. with probability qi and not attaching with proba- bility 1 9:-
All the hyperedges in Rey, are dropped/kept with probability p and 1 - respectively.
1. Setup:
Let deg(v) lif: e wHll for u E V(H) and deg(S) & Emevis) deg(u) for S S H. subhypergraph.
Let
Bernoulli(p) & {1
prob. p
(105)
0 prob. - p
and
Binom(n, p)
Bernoulli(p)
(106)
Define for each v E V, C(u) to be the unique Rey,s whore v E Rey, This mcans that we have the following independent random variables:
X A Bernoulli(1 - p), Ve E (i.i.d. across all e E E)
(107a)
Xc(e) A Bernoulli(g)
(107b)
As well as the following constant, depending only on C(v):
mc(w)
Σ deg(u)
(108)
dEV(C(()
where C(v) C V2 V
50

---

Published in Transactions on Machine Learning Research (11/2024)
Let & be the stationary distribution of H. Its expectation B[A] can be written as:
Eewees X Xc(o)
a(0) - mc(w) + SeuNEC(ooe Xe + (C(e)
(109)
Letting
No A Σ
X. = (inom((eg(())
(110a)
N + Xo())
(110b)
D _ mc(e) +
Σ
Xe + Xc(e)
(110c)
@uNEC(V)).EE
C D Σ
lel) mc()) =
Σ
X mom Binom Pu, p) me(e))
(110d)
E.ViEEE
where Fg - ue E
and so we have: A(0)= = D22
We have the following joint independence No 1 Xc(e) C due to the fact that each random variable describes disjoint hyperedge sets.
2. Computing the Expectation:
Writing out the expectation with conditioning on the joint distribution P(D, No, Xc(o)), we have:
deg(v) deg (C(v))
B[a(e)] Σ
Σ
Σ
= k N, = Xow) b)
(111a)
k=mo
1 deg(v) (eg(
Σ
NN = = P(D = k, N. J, xc()) =
=
(111b)
0= 1=0 k=mo((
1 deg(v) (e)(
Σ
Σ
P(D p
j+b
= j. N.
= =b)
(111c)
k
6=0
1=0
k=me(t)
deg(v) deg(O(u))
Σ
j+b
= j)P(Xc()) =
(111d)
k
b=0
1=0
k=mo(
deg(u) (o))
j+b P(C = k deg(t) mcc)) -J)--((XXxc bb)
(111e)
b=0 k=mo())
deg(u) de)(
Σ
j+b P(Binom(For (F,, 1- pp) -
(11ff)
6=0
k=
P(Binom(deg(u), 1 pp) = P(Bernoulli(gs) =b)
deg(v) deg(C(v))
+
F. k - deg(v)j mole)
1 (deg(()) ( 1 dest P(Bernoulli(g) (q) = b) (111g)
k
0=0
1=0
kmmcte)
v) (())
j +
Fb
Σ
k
k -
deg(v) mc(w)
6=0
1=0
k=ma
(111h)
(dg((i)
1
ddegto) P P(Bernoulli(g) =
51

---

Published in Transactions on Machine Learning Research (11/2024)
deg(v) deg (eg(C(v))
F. deg(v)s mc(v)
1 (dey)(e) 1 )des(e)
j ++1
Σ
Σ
q:) + +4
(111i)
j
k=mot
deg(v) deg(C(())
Σ
Fe k deg(v)ū mc(o)
(a (1- )
de (deg(e))
) (1- 1)
+ at 1
j
k=mo())
(111j)
= Ci(p + (:C2()
(111k)
3. Pick and
We want to find and di so that [[{(v)] = (p() + (.C((p) = T())
We know that for given p E [0, 1], we must. have:
a (7(u)-Cic
(112)
C2(p)
In order for qi E [0, 1], must have T(0) 2 Ci( and z(v) - Ci (p) S C2(p).
a. Pick p sufficiently large:
Notice that
0 S (i) S O
E Binom(deg(e)). p)]) = O deg(v)(1 - -p)) (113)
Binom (Fu, p) mc(n)
mo(1))
and that
0 os O
(114)
for [0, sufficiently large. This is because
Ci(p) s 0 deg(v)(1 - -pp) p))
(115)
mc(+)
and
2 mc(r)
(1g(v)(1-1))) - C2())
(116)
Piecing these two inequalities together gets the desired inequality 114
We can then pick p [0, 1] even larger than the previous p that for the C' > 0 which gives Ci(p) <
C' deg(v)(1 p), we achieve mecs)
C' deg(u) - p) (())= mc(o) + EEEo(j) mc(e)
deg(v)
Ci(p) <
(117)
We then have that there exists so that
sCi = T())
(118)
Using this relationship, we can then prove that for a sufficiently large p E [0, 1J, we must have a gi E [0, 1]
b. p [0, 1] sufficiently large implies qi O: We thus have qa 2 0 since its numerator is nonnegative:
m(p) (p) 1)C()))201
(119)
52

---

Published in Transactions on Machine Learning Research (11/2024)
C. p [0,1] 1] sufficiently large implies q: S 1:
- = (s -
π()) - Ci()) - sCi(p) - Ci(p)
(
1)C1(0) s C2(p) - s1
(120)
53

---

Published in Transactions on Machine Learning Research (11/2024)
C
Additional Experiments
Itac 5a CRNL Waweed Cannn Campa. oi Siseeniiantt
Altaatt
0.10
hypegraph darasets grash datasets
typengrphh cut entenats graph datasets
0.08
Secaan S3t Come. Comps wth Stze
0.06
0.04
0.02
0.00
5,000
10000
15000
20000
3003
10000
13000
20000
Num. Nodes
Num. Nodea
(a) Fraction of components of size atleast 3 (b) Average size of components of size atleast 3 from Algorithm
selected by Algorithm D
Figure
As we are primarily concerned with symmetries in 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 6aa value (T. 2) 2) that are atleast 3 in cardinality from Algorithm 1 as a function of the number of nodes of the hypergraph. For these datasets, it is much more common for the connected components to be of sizes 1 and 2. On the right, in Figure [b] we show the distribution the sizes of the connected components found by Algorithm
plot the fraction of connected components of the same L-GWL-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 both plots, the graph datascts appear to have more nodes and consistent fraction and size of components, while the hypergraph datasets have higher variance in the fraction of components, which is expected since there more possibilities for the connections in hypergraph.
54

---

Published in Transactions on Machine Learning Research (11/2024)
We show below the critical difference diagrams Demšar (0006) of the average PR-AUC ranks (per- centiles) for two datasets from Table 1 across all the downstream hyperGNNs. Each plot contains the PR-AUC ranks of the three compared approaches: baseline, 50% hyperedge drop, and Our method. The bars in each plot represents statistical insignificance between the two approaches according to runs of cach experiment.
Critical difference diagram of average score ranks for Sarddg--mmmmion---ssttrraattteer HGMA
0.60
0.62
0.64
0.66
0.68
0.70
0.5
0.6
0.7
0.8
0.9
baseline 10 drop (..59
(00
baseline (C.61)
HNHH
HyperGiN
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.5
0.6
0.7
0.8
0.9
baseline [0.33]
(0.44)_
drop
drop (0.74)
baseline (0.6
UniGAT
UniGCN
0.55
0.60
0.65
0.70
0.75
0.4
0.5
0.6
0.7
0.8
bas [
(0.74)
drop (0.42)_
(0.77
(0.86) Ours
UniGIN
UniSAGE
0.5
0,6
0.7
0.8
0.55
0.60
0.65
0.70
0.75
0.80
0.85
(0.87)
0o.8 83) baseline
Figure 7: Critical difference diagrams of CAT-EDGE- BANAGG--AADOO---STAURRAAAAA
Critical difference diagram average score ranks for aal-edge-vegaa--bas--ee HGNNP
HGNN
0.650 0.675 0.700
0.725
0.75
Ours 10.0 10.6
00.71) baseline basgleg (8:87)
(0.79) Ours
HNHHN
HyperGCN
0.55
0.65
0.75
0.55
0.60
0.65
0,70 0.75
0.85
bas [8:59)
(0.76) Ours
drop (6.62)
<0 831 baseline
UnIGAT
0.50
0.55
0.60
0.65
0.70 0.75
0.7
0.8
Grop (9.5)
(0.77)
(0.81) Ours
baseliie (0.7
UniGIN
UniSAGE
0.65
0.66
0.67
0.68
0.69
0.70
0.55
0.60
0.65
0.70
0.75
10 drop 8..8
(0.69) baseline baseling (8:57)
(0.78) Ours
Figure 8: Critical difference diagrams of CXT-DDGGE-TIOAS--ARRS---
55

---

Published in Transactions on Machine Learning Research (11/2024)
C.1 Additional Experiments Hypergraphs
In Table B we show the PR-AUC scores for four additional hypergraph datasets, CAT-EDGE--RAIN, CAT- WIKIPEOPLE-OBI, and JF17K 17K for predicting size 3 hyperedges.
Table 3: PR-AUC on four other hypergraph datasets. The top average scores for each hyperGNN method, or row, is colored. Red scores denote the top scores in a row. Orange scores denote two way tie and brown scores denote a threeway tie.
PR-AUCT f
Baseline
Ours
Reseln.+edrop
PR-AUCT f
Baseline
Ours
Raseln.+edrop
HGNN
0.75 + 0.01
0.79 + 0.11
0.74 + 0.09
HGNN
0.95 + 0.10
0.99 + 0.04
0.96 - 0.09
HGNNP
0.75 0.05
0.78 0.10
0.74 0.12
HGNNP
0.95 0.06
0.96 0.09
0.96 0.08
HNHN
0.74
0.74 = 0.02
0.74 + 0.05
HNHN
1,00 - 0.08
0.99 +: 0.09
0.95 = 0.10
HyperGCN
0.74
0.50 + 0.07
0.50 + 0.12
HyperGCN
0.76 + 0.03
0.67 0.14
0.68 0.09
UnIGAT
0.73 0.07
0.81 0.10
0.81 1 0.09
UniGAT
0.87 = 0.07
1.00 4 0.09
0.99 = 0.08
UniGCN
0.78 0.04
0.81 = 0.09
0.71 + 0.08
UniGCN
0.99 + 0.07
0.96 + 0.09
0.92 = 0.05
UnIGIN
0.74 0.09
0.74 0.03
0.74 1 0.07
UniGIN
0.98 0.06
0.96 0.08
0.95 0.06
UniSAGE
0.74 0.03
0.74 = 0.12
0.74 + 0.01
UniSAGE
0.94 + 0.05
0.98 + 0.07
0.97 = 0.07
(a)
can moce BRARY
(b) CAT EDGG EEG.E-V
wwcas RAT BAS-ERIIEW
PR-AUC 1
Baseline
Ours
+edrop
PR-AUC 1
Baseline
Ours
Baseln. tedrop
HGNN
0.52 0.01
0.57 0.08
0.54 + 0.10
HGNN
0.59 0.04
0.63 0.04
0.45 + 0.09
HGNNP
0.52 + 0.03
0.54 = 0.07
0.54 + 0.06
HGNNP
0.71 0.07
0.63 + 0.07
0.57 + 0.04
HNHN
0.73 + 0.03
0.73 = 0.07
0.73 + 0.00
HNHN
0.73 = 0.04
0.73 4: 0.03
0.73 :: 0.04
HyperGCNN
0.54 0.05
0.55 + 0.02
0.49 + 0.10
HyperGCN
0.59 0.05
0.58 0.09
0.48 + 0.01
UniGAT
0.49 +.09
0.54 + 0.04
0.53 + 0.04
UniGAT
0.61 0.07
0.61 + 01.04
0.51 + 0.08
UnIGCN
0.46 1 0.08
0.68 0.08
0.51 + 0.08
UniGCN
0.58 0.00
0.60 0.03
0.59 + 0.02
UniGIN
0.73 + 0.09
0.73 0.01
0.73 + 0.02
UniGIN
0.80 + 0.04
0.77 + (1.08
(1.75 + 0.05
UniSAGE
0.73 0.06
0.73 + 0.02
0.73 + 0.08
UniSAGE
0.79 0.02
0.77 + 01.08
0.77 + 0.01
(c)
WamPcorcascon
(d) JPI7K
C.2 Experiments on Graph Data
the PR-AUC test scores for link prediction some nonattributed graph datasets. The train-val-test splits are predefined for FB11K-237 and for the other graph datasets a single graph is deterministically split into 80/5/15 for train/val/test
We show in Tables 4 5 6
We remove 10% of the edges in training and let them be positive examples Per to predict. For validation and test, we remove 50% of the edges from both validation and test to set as the positive examples Poat, Pte to predict. For train, validation, and test, we sample
1.2 Ptel negative link samples from the links of train, validation and test. Along with hyperGNN architectures GNN architectures: APPNP Gasteiger et al. (2018), GAT Veličkovié et al. (2017), GCN2 Chen et al. (2020a), 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. (011)) 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 used on the initial node positional encodings. Since graphs do not have any hyperedges beyond size 2, graph neural networks fit the inductive bias of the graph data more easily and thus may perform better than hypergraph neural wer baselines more often than expected.
use for the hypergraph experiments,
also compare with standard
56

---

Published in Transactions on Machine Learning Research (11/2024)
Table 4: PR-AUC on graph dataset JOHNSHOPKINS55. 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 two-way tie in the column, and brown color denotes a three-or-more-way Lie in the column.
PR-AUCT 1
HGGNN
HINNP
INNI
HyperGCC
UniGAT
UniGCN
UniGIN
UniSAGE
Ours
0.71 1 0.04
0.71 = 0.09
0.69 + 0.09
0.75
0.75 = 0.09
0.74::0.09
0.65 + 0.08
0.65 : 0.07
NN Baseline
0.68 2 0.00
0.69 = 0.06
0.67 + 0.02
0.75
0.74 0.02
0.74
0.65 + 0.05
0.64 : 0.08
NN Besein.tedrop
0.67 + 0.02
0.70 + 0.07
U.66 + 0.00
0.75 + 0.03
0.73 + 0.08
0.74 0.05
0.63 + 0.01
0.64 + 0.03
APPNP
0.40 +: 0.03
0.40 + 0.03
U.40 + 0.03
0.40 + 0.03
0.40 + 0.08
0.40 +: 0.00
0.40 + 0.03
0.40 + 0.03
APPNP-edrop
0.40 : 0.13
0.40
0.40 + 0.13
0.40 0.13
0.40 0.13
0.13
0.40 - 0.13
0.40
GAT
0.49 = 0.03
0.49 = 0.03
0.49 + 0.03
0.49 = 0.03
0.49 = 0.08
0.00
0.49 + 0.03
0.49 0.03
0.51 2 0.05
0.51
0.51 + 0.05
0.51 = 0.05
0.51 = 0.05
0.00
0.51 - 0.05
0.51 0.05
GCN2
0.50 + 0.09
0.50 + 0.09
U.50 0.09
0.50 0.09
0.50 0.09
0.50
0.50 4.009-009
0.50 0.09
GCN2++edrog +edrop
0.07
0.07
0.56 + 0.07
0.56 0.07
0.56 0.07
0.56 0.06
0.56
GCN
0.73 0.02
0.73
0.73 #
0.73 0.02
0.73
0.73
0.02
0.73 0.02
+eN+o
0.73
0.01
0.73 0.01
0.73
0.73 0.01
0.78
0.73 0.70
GIN
0.00
0.03
0.06
0.73
0.73 0.06
0.73
0.73 0.76
edrop
0.73 0.01
0.03
0.73 + 0.01
0.73 0.01
0.73 0.01
0.73
0.73 0.70
GraphSAGE
0.73 0.08
0.73 0.08
0.73 + 0.08
0.73 = 0.08
0.73 0.08
0.73
0.73
0.73 0.08
GraphSAGE-Asrroo
0.73 0.09
0.73 + 0.09
0.73 + 0.09
0.73 0.09
0.73 0.09
0.73
0.09
0.73 0.09
0.73 + 0.09
Table 5: PR-AUC on graph dataset FB15K-237. Each column is a comparison of the baseline PR-AUC scores against the PR-AUC score for our method (first row) applied to 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.
AR-AUCT f
HGNN
HGNNP
HNHN
HyperGCN
UniGAT
UniGCN
UniGIN
Uni
Ours
0.66 0.06
0.78 + 0.02
0.63 + 0.07
0.82 0.10
0.75 0.05
0.74
0.75 0.03
0.75 : 0.06
NyperCNN Buseline
0.65 1 0.06
0.65 : 0.06
0.65 : 0.04
0.82 0.00
0.74 0.04
0.00
177::00.00
0.77 0.01
hyperCNN Beseln. -edrop
0.65 2 0.09
0.65 - 0.00
0.64 + 0.05
0.82 0.00
0.72 = 0.00
0.73 0.00
0.72 0.07
APPNP
0.72 0.10
0.72 + 0.30
0.72 + 0.10
0.72 0.10
0.72
+.72
0.72 0.72
APPNP+edrop
0.71 2
0.71 0.05
0.71 : 0.05
0.71 0.05
0.71 0.05
0.71 0.01
0.71
GAT
0.64 0.06
0.06
0.61 0.06
0.64 0.00
0.64 0.06
0.64 0.06
0.64
GAT -edrop
0.61 0.09
0.61 0.09
0.61 : 0.09
0.61 - 0.09
0.61 161:00 0.09
0.61
0.61 0.09
0.61 0.09
GCN2
0.66 + 0.03
0.66 + 0.03
0.66 + 0.03
0.66 0.03
0.66 + 0.03
0.66
0.66
+ 0.03
0.66 0.03
GCN2+edrop
0.65 + 0.10
0.65 0.10
U.65 + 0.10
0.65 0.10
0.65 + 0.10
0.65
0.65 U.10
0.65 0.10
GCN
0.69 : 0.03
0.03
0.69 = 0.03
0.69 0,03
0.69 0.03
0.09
0.69 0.03
0.09
GCN+edrop
0.71 # 0.06
0.71
0.71 = 0.06
0.71 1
0.71 0.06
0.71
0.71 + 0.06
0.71#0.00
GIN
0.73 0.03
0.73
0.73 - 0.03
0.73
-.73
0.73
0.73 0.03
0.03
+lN+edrop
0.56 + 0.07
0.56 + 0.07
U.56 + 0.07
(1.56 0.07
0156 + 0.07
0.56 0.07
0.56 + 0.07
0.56 + 0.07
GraphSAGE
01.46 + 0.15
0.46 + 0.15
U.46 + 0.15
0.46 + 0.15
0.46 + 0.15
0.46 0.15
0.46 + 0.15
0.46 0.15
GraphSAGE++drrop
0.47 2 0.01
0.47 = 0.01
0.47 : 0.01
0.47 0.01
0.47 = 0.01
0.40
0.47 + 0.01
0.47 0.01
Table 6: PR-AUC on graph dataset AIFB. Each column is comparison of the bascline 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 poroo-or-more-weer tic in the column.
PR-AUC
HGNN
HGNNP
HNHN
HyperGCN
UniGAT
UniGCN
UniGIN
UniSAGE
Ours
0.79 + 0.11
0.73 + 0.10
0.73 0.02
0.85 + 0.07
0.75 + 0.10
0.84 + 0.09
0.72 + 0.03
0.72 + 0.12
hyperGNN Baseline
0.72 + 0.07
0.72 02240000 0.07
0.72 0.06
0.85 4 0.05
0.75 + 0.09
0.005
0.72 + 0.07
0.72 + 0.06
hyperGNN tedrop
0.72 : 0.05
0.08
0.72 + 0.06
0.85 + 0.07
0.73 = 0.09
0.84 0.066
0.72 = 0.03
0.72 - 0.07
APPNP
0.81 ::: 0.12
0.81
0.81 + 0.12
0.81 + 0.12
0.51 = 0.12
0.81 0.12
0.81 = 0.12
0,81 + 0.12
APPNP+odrop
0.80 0.05
0.00
0.80 + 0.05
0.80 + 0.05
0.90 = 0.05
0.00
0.50 0.05
0.80 0.05
GAT
0.50 0.02
0.02
0.50 + 0.02
0.50 + 0.02
0.50 + 0.02
0.50 + 0.02
0.50 + 0.02
0.50 + 0.02
GeT++
0.33 0.02
0.33
0.33 0.02
0.33 + 0.02
0.33 = 0.02
0.33 4.00
0
GCN2
0.83 3 0.05
0.03
0.83=00005
0.83 + 0.05
0.83 = 0.05
0.83 0.05
0.83 0.83
CCN2+eeropp
0.78 0.04
0.00
0.00
0.78 + 0.04
0.78 = 0.04
0.78 0.00
0.78
0.78
GCN
0.73 + 0.14
0.13
0.73 + U.14
0.73 + 0.14
U.73 + 0.14
0.78
0.73
0.14
+edrop
0.75 0.08
0.75
0.75 + 0.08
0.75 0.08
0.75 = 0.08
0.75
0.75
0.75
GIN
0.73 0.00
0.73
0.73 0.000
0.73 0.00
0.00
0.73 = 0.00
0.70
0.00
0.70
GIN
0.73 0.10
0.13
0.73 0.100
0.73 0.10
0.73 = 0.10
0.73
0.13
0.73
GraphSAGE.
0.46 + 0.15
0.15
0.46 0.15
0.46 +
0.15
0.46
0.46
0.46+0..1 0.15
0.46
GraphSAGEE+edrop
0.47 4 0.01
0.00
0.47 0.01
0.47 + 0.01
0.47 = 0.01
0.47 0.47
0.47
57

---

Published in Transactions on Machine Learning Research (11/2024)
D Dataset and Hyperparameters
Table 7 lists the datasets and hyperparameterss used in our experiments. All datasets are originally from Ben- son et al. (2018b) or are general hypergraph datascts provided in (inha et al. (2015); Amburg et al. (2020a)
We list the lotal number of hyperedges (81, the total number of vertices [ the positive to negalive label ratios for arain/val/ter
and the percentage of the connected components searched over by our algorithm that are size atleast 3. A node isomorphism class is determined by our isomorphism testing algorithm. By Proposition B.2 we can guarantee that if two nodes are in separate isomorphism classes by our isomorphism tester, then they are actually nonisomorphic.
We use 1024 dimensions for all hyperGNN/CG COGGNNNNNNNNN /GNN layer latent spaces, 5 layers for all hypergraph/ /graph neural networks, and a common learning rate 0.01. Exactly 2000 epochs are used for training.
The hyperGNN architecture basclines are described in the follwoing:
HGNN Feng et al. (209 A neural network that generalizes the graph convolutionn to hypergraphs where there are hyperedge weights. Its architecture can be described by the following update step for the + I-layer from the /th layer:
x(+1) oD, HWD x(")
(121)
where Dy E R2 is the diagonal node degree matrix, De Rmxm is the diagonal hyperedge degree matrix, H E R=xm is the star incidence matrix, W is the diagonal hyperedge weight matrix, ( E Raad is node signal matrix, W(() E Raxd is a weight matrix, and a is nonlinear activation. Following the matrix products, as a message passing neural network, HGNN is GWL-1 based since the nodes pass to the hyperedges and back.
HGNNP Feng et al. (2023 is an improved version of HGNN where asymmetry is introduced into the message passing weightings to distinguish the vertices from the hyperedges. This is also a GWL-1 based message passing neural network. It is described by the following node signal update oquation:
((+1) HW DE H x x00 (()))
(122)
where the matrices are exactly the same as from HGNN.
HyperGCN Yadati et al. (2019) computes GCN on a clique expansion of hypergraph. This has an updateable adjacency matrix defined as follows:
[ (1,5) E E
49 = 0 (i,j) & E
(123)
where
E ((eesee) argmaxx.jee (x -
(124)
x(1+1) =o Σ (.x"")
(125)
wEN(w)
The (0) E Rnxd is the node signal matrix at layer 1, the W E Raxd is the weight matrix at layer 1, and a is some nonlinear aclivation. This architecture has less expressive power than GWL-1.
HNHN Dong et al. (2020) This is like HGNN but where the message passing is explicitly broken up into two hyperedge to node and node to hyperedge layers.
x o x w + 6
(126a)
and
((+1) = oHH (1) E wi + (
(126b)
where E TRaX is the star expansion incidence matrix, / w e Raxd D0 E Rmm 1 E R are weights and biases, x(0 x(()) are the hyperedge and node signal matrices at layer 1, and o is a nonlinear activation function. The bias vectors prevent HNHN from being permutation equivariant.
58

---

Published in Transactions on Machine Learning Research (11/2024)
UniGNN Huang & Yang 2021 The idea is directly related to generalizing WL-1 GNNs to Hyper- graphs. Define the following hyperedge representation for hyperedge E &:
1 C
x
(127)
UniGCN: a generalization of GCN to hypergraphs
x
dd Σ
1
(128)
Vile
UniGAT: generalization of GAT hypergraphs
Que = osa" [X] ( w xff
(129a)
eluee Öuue
(129b)
UEE Cooe
((++1)
aveheW
(129c)
e3v
UniGIN: a generalization of GIN to hypergraphs
x(++1 ((1 ((1+))x!))
Σ he)
(130)
UniSAGE: generalization of GraphSAGE to hypergraphs
x((+1) (X + Σ (he))
(131)
All positional encodings are computed from the training hyperedges before data augmentation. The loss we use for higher order link prediction is the Binary Cross Entropy Loss for all the positive and negatives sam- ples. Hypergraph neural network implementations were mostly taken from https:://tt thub. commiMMonLab/ DeepHypergraph) which uses the Apache License 2.0.
Table 7: Dataset statistics and training hyperparameters used for all datasets scoring all experiments.
Dataset Information
Dalasel
[8]
[V]
At.tr
% of Coun. Comps. Selected
ONT-EDGE-DIA EDGE-DAWN
$7,104
2,109
8.82110,511
1,915/2,296
1,867/2,285
0.05%
RMAIL-EU ED
234,760
998
1,800/2,159
570/681
626/ 749
0.6%
CONTACT- SCHOOL
1,620/1,921
461/545
350/415
9.3%
TTT-EDEE-MUSCC BLUES-REVIBN
694
1,106
16/19
7/6
3/3
0.14%
CAT-EDGE-V TN--BIGE-VEGAS-BBAREE SEAGAAS-AASS-EEIEEES
1,194
1,234
72/96
12/14
11/13
0.7%
SERACTT-IGI--SE SCCE-S
7,818
2,640/3, 1/43
176/208
175/205
CAT-EDGE- BRAIN
21,180
638
13,037 13.087/13,811
2,793/3,135
2,791/3,020
9.9%
JOHNSHOPKISS55
298,537
5,163
29.853/35,634
9,329/11,120
27. 27.988/20 223,853
2.0%
4.646/5,572
1,452/1,739
1.356/5,222
0.02%
AMHERST44
145,522
2,234
14,322/17,211
4.547/6.379
16,125 634,633
4.4%
FR15K-237
272,115
14,505
27,211/32,60
8,767/10,66 100,0
00,233/122,777
2.11%
WIKIPEOPLE-OEL
27.211/32.630
10,254/12,301
1,161/1,396
0.05%
JF17K
76,379
28,645
11,907/14,287
1.341/1.608
1,311/1,608
0.6%
We describe here some more information about each dataset we use in our experiments as provided by Benson al. (2018b): Here is some information about the hypergraph datasets:
59

---

Published in Transactions on Machine Learning Research (11/2024)
Amburg al. (0200a CAT-EDGE-DAWNY Here nodes are drugs, hyperedges are combinations of drugs taken by patient prior to an emergency room visit and edge categories indicate the pat ient disposition (e.g., 'sent home', "surgery", 'released to detox").
Benson et al. [2018a); Yin al. (2017): Leskovec et al. MO0T-EMAI--EU This is a temporal higher- order network datasct, which here mcans sequence of timestamped simplices, or hyperedges with all its node subsets existing as hyperedges, where each simplex is set of nodes. In email communication, messages can be sent to multiple recipients. In this dataset, nodes are email addresses at a European research institution. The original data source only contains (sender, receiver, timestamp) tuples, where timestamps are recorded at 1-second resolution. Simplices consist of a sender and all receivers such that the email ween the two has the same timestamp. We restricted to simplices that consist. of most 25 nodes.
Stehlé et al. (2011) CONTACT-PLLMARR--CHHOO This is a temporal higher-order network dataset, which here mcans a sequence timestamped simplices where each simplex is a set of nodes. The dataset constructed from interactions recorded by wearable sensors by people al a primary school. The sensors record interactions at a resolution of 20 seconds (recording all interactions from the pre- vious 20 seconds). Nodes are the people and simplices are maximal cliques of interacting individuals from interval.
Amburg et al. (220bb CAT-EDGE- and hyperedges are users who reviewed an establishment particular category (different types of bars in Las Vegas, NV) within a month timeframe.
EDEA--EEEE-E VEGAS-EEE--BBEE AARS-REVIEWS: Hypergraph where nodes are Yelp users
Benson et al. [0188a]; Mastrandrea et al. 2015 CONTACT--ICH--SHHOOL This is a temporal higher- order network datasct, which here mcans a sequence of timestamped simplices where cach simplex is a set of nodes. The datasel constructed from interactions recorded by wearable sensors by people at a high school. The sensors record interactions a resolution of 20 seconds (recording all interactions from the previous 20 seconds). Nodes are the people and simplices are maximal cliques of interacting individuals from an interval.
This is a graph whose edges have categorical edge labels. Nodes represent brain regions from an MRT scan. There are two edge categories: one for connecting regions with high fMRI correlation and one for connecting regions with similar activation patterns.
Crosslcy et al. 2013 CAT-EDGE-BRANL
Lim et al.
202 JOHNSHOОPKINS55. Non-homophilous graph datasets from the facebook100 dataset.
Ristoski & Paulheim 2016 AIFB:
The AIFB dataset describes the AIFB research institute in terms of its staff, research groups and publications. The dataset was first used to predict the affiliation (i.e., research group) for people in the dataset. The dataset contains 178 members of five research groups, however, the smallest group contains only four people, which is removed from the dataset, leaving four classes.
Lim et al.
2021 AMHERST41: Non-homophilous graph datasets from the facebook100 datasct.
FB15K-21 A subset of entities that are also present in the Wikilinks database (2012) and that also have at least 100 mentions in Freebase (for both entities and relationships). Relationships like h//poppl/person///ee pppsonnnaationalittt which just reverses the head and tail compared to the relationship '/people/ ppeeple/personn/ person/natiionalttt nnaionaality" are removed. This resulted in 592,213
Bordes et al.
Singh et al.
triplets with 14,951 entities and 1.345 relationships which were randomly split.
Guan ct al. 2019) WIKIPEOPLE-OBII The Wikidata dump was downloaded and the facts concerning entities of type human were extracted. These facts are denoised. Subsequently, the subsets of elements which have at least 30 mentions were selected. And the facts related to these elements were kept. Further, each fact was parsod into a set of its role-value pairs. The remaining facts were randomly split into training set, validation set and test set by a percentage of 80%:10%:10%. All binary relations are removed for simplicity. This modifies WikiPeople to WikiPeople-Obi.
60

---

Published in Transactions on Machine Learning Research (11/2024)
Wen et al. JF11KK The full Freebase data in RDF format was downloaded. Entities involved in very few triples and the triples involving String, Enumeration Type and Numbers were removed. A fact representation was recovered from the remaining triples. Facts from meta-relations having only a single role were removed. From cach meta-relation containing more than 10,000 facts, 10,000 facts were randomly selected.
61

---

Published in Transactions on Machine Learning Research (11/2024)
D.1
Timings
We perform experiments on cluster of machines equipped with AMD MI100s GPUs and 112 shared AMD EPYC 7453 28-Core Processors with 2.6 PB shared RAM. We show here the times for computing each method. The timings may vary heavily for different machincs as the memory we used is shared and during peak usage there is a lot of paging. We notice that although our data preprocessing algorithm involves seemingly costly steps such as GWT-1, connected connected components etc. The complexity of the entire preprocessing algorithm is linear in the size of the input as shown in Proposition [3.20] Thus these operations are actually very efficient in practice shown by Tables g and 10 for the hypergraph and graph datasets respectively. The preprocessing algorithm is run on CPU while the training is run on GPU for 2000 epochs.
Table 8: Timings for our method broken up into the preprocessing phase and training phases (2000 epochs) for the hypergraph datasets.
Timings (hh:mm) + (8)
Timings (hh.mm)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
2m::4ss1::88
35m:9s
HGNN
1.72s::5s
2m::1ls::1 2m:10s=:s
HGNNP
1m:52si0s
35m:16si0s
HGNNP
1.42s
HNHN
1m:55si0s
35m:0s:11s
HNHN
1.99s
3m:43s::2s
HyperGCN
1m:50s11ss
58m:17s:179s
HyperGCN
1.
4m:12s:::3s
UniGAT
1m:54s+0s
1h:19m:344s-t-00
UniGAT
1.8
3m:54s-+2277
UniGCN
1m:50s12s
35m:11s::2a
UniGCN
2.93s
3m:15s=:::s
UniGIN
1m:50s11s
35m:12s::1288
UniGIN
2.24s
3m:17s=11s
UniSAGE
1m:51si0s
35m: 16s
UniSAGE
2.04s
3m: 13s
(a) CAT-EDGE- DAWN
(b) CAT- BEE---DEEE-------- BLUES-REEUSS
Timings (hh:mm) (s)
Timings (hh:mm)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
4.17s
19544s
HGNN
5.84st1s
6m:49s:8s
HGNNP
4s
2m:41s-553s
HGNNP
0.82s
9m:8s+19s
HNHN
3.
2m:27s::15s
HNHN
5.95s10s
8m:21s119s
HyperGCN
1.81
2m:27s=:0s
HyperGCN
5.74st0s
10m:16s
UniGAT
1.91s
2m:27s=3306s
UniGAT
8.80s
2m:31s::282s
UniGCN
2s
2m:30s:12s
UniGCN
6.35s
65:7s
UniGIN
3. 3s
2m:27s=:119s
UniGIN
5.99s
10m:41s::433
UniSAGE
1.65s-t0s
2s
UniSAGE
5.97s
9m:50s
(c) CAN--DOG--VEGA----ARR--EEEE
(d) CONTACTT-RIMARY-SCIOOO
Timings (hh:mm) = (s)
Timings (hh:mm)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
23. 1s
17s
HGNN
4s89s
1m:27s:18s 2m:42s=::0s
HGNNP
23.25s:0s
19m::2ss::49
HGNNP
2.12s
HNHN
2s.27st1s
1m:112-:63s
HNHN
2.12st0s
2m:30s=t42s
HyperGCN
2s
21m:166 1s
HyperGCN
2.11st0s
40.11s=3s
UniGAT
1s
5m:13s
UniGAT
2.13st0s
3m:18s-t-8s
UniGCN
25.44s+10s
5m151s::0019
UniGCN
2.11st0s
3m:21s+:2s
UniGIN
18
19m:10s:::3977
UniGIN
2.11s:00
2m:24s:1:0s
UniSAGE
14.08s:22s
36m:29s:4:ss
UniSAGE
2.11st0s
2m:8s:449s
(e) EMAIL-EU
(f) CAT-EDGE MADISON RESTAURANT SEEERRAANTTRREEEEE REVIEWS
62

---

Published in Transactions on Machine Learning Research (11/2024)
Table 9: Timings for our method broken up into the preprocessing phase and training phases (2000 epochs) for the hypergraph datasets.
Timings (hh:mm) + (s)
Timings (hhamm)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
15. 4s
1m:59sstss
HGNN
11.34s=10s
4m:24s-6s
HGNNP
12.72s
2m:29s:t0s
HGNNP
6.02s
4m:13s=22s
HNHN
12. 17
3:::6s+00s
HNHN
6.01s
5m:33s 1s
HyperGON
12.47s:1s
4s
HyperGCN
6.32s
1m:33s::0s
UniGAT
12. 0s
1sd1slls
UniGAT
6.04s10s
4m: 1s:::s
UniGCN
12.50s:0s
2m:29s::3s
UniGCN
5.79s
4m:12s:i:s
UniGIN
12.57s:0s
2m::66s3:s
UniGIN
6.64811s
3m: 1s
UniSAGE
12.67s:10s
1m:50s::20s
UniSAGE
5.70s
3m:2s:t0s
(a) CONTACT-HIGH-SSHHOOLL
(b) CAT-EDGE- BRAIN
Timings (hh:mm)
Timings (hh:mm) + (s)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
3m:30s+55s
1
HGNN
1m:11s:552s
37m:18s:t9s
HGNNP
1ss
1h:48m:57s:tts
HGNNP
7m:34s=1s
47m:56s: Is
HNHN
3m:41s1ls
2h:9m:34s=1s
HNHN
6m:21ss1s
49m:33s: Is
HCPerGCN
3m:24s+1s 1s
58m:27s:11s
HyperGCN
8m:20s
28m:25s: 1s
UniGAT
3m:50s
4h:21m:24s:+1s
UniGAT
10m:40s:11s
1h:54m:36st1s
UniGCN
3m:38s+1s
19
UniGCN
7m:25s
2h:40m:20s::1s
UniGIN
3s:50s+1s
27m:50s#11s
UniGIN
10m:37s+t1s
2h:48m:35s+ts
UniSAGE
3m:41s11s
27m:22s:t1s
UniSAGE
1m:
2h:35m::4::11
(c) WIKIPROPLE-ORI
(d) JF17K
63

---

Published in Transactions on Machine Learning Research (11/2024)
Table 10: Timings for method broken up into the preprocessing phase and training phases (2000 epochs) for the graph datasets.
Timings (hh:mm) + (8)
Timings (hh:mm) + (s)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
11m:14==555
53m:21s:28455
HGNN
17m:9s=164s
12m:38s=5549
HGNNP
11m:10::22s
35:
HGNNP
15m:34s:161s
20m:26s::124s
HNHN
13955
11:35:::15s:1:19:
HNHN
15m:31s::883
18m:11s:::30s
HyperGCN
33s98s:0s
5m:8s::0s
HyperGCN
15m:46s::22s
4m:17s=88s
UniGAT
1m:59s=1120s
2h:2m:47s=20s
UniGAT
1m:27s=6s
16m:30s:t0s
UniGCN
34.37s:10s
1h:17m::88s::2
UniGCN
15m:57s.124s
18m::42s:h:70s
UnIGIN
34.05s11s
1h:16m:38s:77
UniGIN
16m:14s:173s
16m::2s::395
UniSAGE
34.36s10s
1h:16m:34s:t:3s
UniSAGE
8m:42s=660s
8m::49-13224s
(a) JOHNSHOPKINS55
(b) AIFB
Timings (hh:mm) + (8)
Timings (hh:mm) + (s)
Method
Preprocessing Time
Training Time
Method
Preprocessing Time
Training Time
HGNN
4m:1stils
111776
HGNN
3m:32s=19s
1h:19m:5s::4684:
HGNNP
3m:53sst4s
39m:30s11:s
HGNNP
3m:26s=10s
2h:19m:44s:::3586
HNHN
3m:16s+22s
44m:7s:77ls
HNHN
3m:27s=0s
1h:55m:48s::22s
HyPerGCN
3m:35s +3s
5m:22s 258
HyperGCN
3m:28s+000 Os
10m:31s-118s
UniGAT
11.92s10ss
1h:51m::33s. 123s
UniGAT
3m:24s
3h:50m:24s:191s
UniGCN
3m:20s16s
39m:18s:151.
UniGCN
3m
1h:39m:46s:113s
UniGIN
3m:21s+88
38
UniGIN
3m:17
1h:36m:47s4335
UniSAGE
11.27s10s
58m:48s.1956
UniSAGE
3m:25s 13s
1h:37m:16s::
(c) AMHERST4]
(d) FB15K-237
64


Reviews:
[{"review_id": "2X1jvxzFa5", "reviewer": "Reviewer_8Vjw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Symmetry is an important problem when predicting.  In several domains one has found that specific wiring in a neural network (e.g., a convolutional neural network) can exploit symmetry (e.g., invariance under translation in a picture) simplifies the learning problem.  Looking at a graph-theoretic representation is clearly a good idea to start with.\n\nHowever, I have several concerns:\n* The paper doesn't discuss clearly the expected applicability and limitations of the proposed approach.\n* The paper has a lot of minor technical issues which make accumulate and make it very hard to follow after a number of sections (details see below).\n* While the paper says (correctly) hypergraph computation is costly in terms of computation, there is no systematic experimental evaluation of the benefits against the added computational cost\n* The discussion is mostly restricted to the proposed preprocessing algorithm, there is little discussion of the interaction with other ingredients of the learning \n\nSec 1.\n* \"For this task, when the hypergraph is unattributed, it is important to respect the hypergraph’s symmetries, or automorphism group.\" : this sentence is rather vague.  Until we succeed at predicting all missing links correctly, we can't determine the automorphism group of a graph.  Maybe you want to make a more statistical statement?  In such case one could first try to learn the statistic pattern (maybe expressing some symmetry) after which one could try to respect that pattern during link prediction.  It would help a lot if you could provide an example here of what you mean.\n* \"GWL-1 views a hypergraph as a collection of trees rooted at the nodes. These rooted trees are formed by viewing each node-hyperedge incidence as an edge and recursively expanding about the nodes and hyperedges alternately.\" : it is quite common to represent a hyper-edge as a tree, but the part \" ... and recursively expanding about the nodes and hyperedges alternately\" is unclear to me.\n* \"We can recover hyperGNNs\" : what is \"recover\" here?  Do you mean \"represent\"?\n* \"by expressing the computation of GWL-1 as a matrix equation.\": While we can express WL and its variants using matrix equations in a few ways, it is unclear how this brings us closer to a hyperGNN.\n* \"This means just the neighborhood size of the nodes in hypergraphs can grow exponentially with the number of nodes of the hypergraph\" : The neighborhood of a node v is commonly defined as the set of all nodes adjacent to v.  This set is bounded by the total number of nodes in the (hyper)graph, and hence not exponential.  Maybe you mean that the number of edges in a hypergraph can be exponential in the number of nodes of the hypergraph, as for $n$ nodes we get $2^n-1$ possible hyperedges ?\n* \"In order to address the issue of the expressivity of hyperGNNS for the task of hyperlink prediction\" : It is still unclear what \"expressivity\" exactly is meant here.  this paragraphs forms the motivation of the work and hence deserves being clear.\n* \"This limits the space for augmentation, which can prevent extreme perturbations of the data.\" : it is unclear what is \"augmentation\" here.  The term has meanings in various context, e.g., \"data augmentation\" refers to adding more data without changing the original data (and hence without perturbing it).\n\n\nSec 2.\n\n* $\\tilde{B}\\subset \\tilde{A}$ requires as the first of two conditions that $\\tilde{B}\\subset \\tilde{A}$ which looks like a recursive definition.  maybe the condition must be $B\\subset A$ ?  What if $A=B$ but for some elements $m'(e)<m(e)$, the normal interpretation of multisubset is that in that case too $\\tilde{B}\\subset \\tilde{A}$, but not according to the definition provided.  \n* Multiset union:  Some other authors define $m_{A\\cup B} = \\max(m_A,m_B)$, which is consistent with set union, while the provided definition is not.  Indeed if $A=\\\\{1,2\\\\}$ and $B=\\\\{2,3\\\\}$ then $A\\cup B=\\\\{1,2,3\\\\}=(\\\\{1,2,3\\\\},\\\\{(1,1),(2,1),(3,1)\\\\})$, but if $A$ and $B$ are seen as multisets we get $A\\sqcup B = (\\\\{1,2,3\\\\},\\\\{(1,1),(2,2),(3,1)\\\\})$\n* \"an induced subhypergraph is a subhypergraph\" : given that two hypergraphs were around in the previous sentence, it is less ambiguous to say \"an induced subhypergraph of $H$ is ...\"\n* \"A hypergraph isomorphism is a structure preserving map $\\rho = (\\rho_V , \\rho_E )$ such that both $\\rho_V$ and $\\rho_E$ are bijective\" : this definition deviates from the normal one in literature.  Consider hypergraphs $H=(V_H,E_H)$ and $D=(V_D,E_D)$ with $E_D=E_H$ and $V_D\\subset V_H$ (i.e., $H$ is $D$ plus a few isolated vertices), and consider $\\phi_V=\\\\{(v,v)|v\\in V_D\\\\}$ and $\\rho_E=\\\\{(e,e)|e\\in E_D\\\\}$, then both mappings are bijections but $H$ and $D$ are commonly not called isomorphic.\n* Definition of neighborhood: The definition says the neighborhood of v is a hypergraph with v and all edges incident with v.  The sentence says \"is the subhypergraph of H induced by the set of all hyperedges incident to v\".  This is not consistent.  If $H=(\\\\{1,2,3\\\\},\\\\{\\\\{1,2\\\\},\\\\{2,3\\\\},\\\\{1,3\\\\}\\\\})$, then $(\\\\{1,2,3\\\\},\\\\{\\\\{1,2\\\\},\\\\{1,3\\\\}\\\\})$ is not an induced subgraph according to the earlier definition of induced subgraph.\n* Def 2.8, second condition.  In formal logic, there is a problem.  An implication $p\\Rightarrow q$ is true is either $p$ is false or $q$ is true.  The condition hence means that there does not exist a permutation for which $\\pi(S)\\neq S'$.  Except for degenerate cases, finding a permutation such that $\\pi(S)\\neq S'$ is rather easy, implying that except for degenerate cases (the empty graph, the complete graph), there is no \"most expressive\" g.  \n* Even if the logic of Def 2.8 would make sense, i would still dislike the word \"most\" in the term \"most expressive\", as \"most\" implies a comparison, and no order relation is defined.\n\n\nIn later sections too, a lot of minor issues obscure the explanation.\nAs a result, I'm not fully understanding the algorithm presented in Section 5.\n\n\nThe proposed algorithm is a preprocessing algorithm.  Section 6 doesn't seem to provide an in-depth explanation of the link prediction training algorithm that is combined with this preprocessing algorithm, and doesn't discuss potential interactions between the choice of the preprocessing algorithm and the choice of the training algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method to use symmetry to improve higher order link prediction strategies.  The paper offers a lot of theory, a method using some of these concepts, and then experimental results.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is critical to improve the technical writing of the paper, so individual sentences and paragraphs are formally correct, and every concept is defined before it is used.  To achieve this, a rigorous reading and editing of the complete text is necessary, my detailed comments only are a sample of the issues in the text.\n\nIt is also very important to provide sufficient discussion and context to the paper, e.g.,\n- for which applications do you expect your method to yield more substantial or less substantial gains?\n- what in the computational cost in practice, and how does this trade off to predictive performance gains?\n- what are limitations of the method?\n- what alternative choices could you have made and what would have been the effect?\n- and maybe: how do methods working on symmetries in the data (such as the proposed one) compare to methods working on symmetries in the model (in the spirit of convolutional neural networks or GNNs which constrain the dependencies of nodes on their inputs to be symmetric) ?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AkNTDA7sJ6", "reviewer": "Reviewer_woGA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThe paper introduces a novel approach to improving the expressivity of hyperGNNs by targeting topological symmetries. This is an interesting direction that has yet to be widely explored in the context of hypergraph learning.\n\nThe authors provide a formal analysis of GWL-1 on hypergraphs from an algebraic topology perspective, which offers new insights into the algorithm's behavior on complex hypergraph structures. This theoretical foundation strengthens the paper's contributions.\n\nThe proposed preprocessing algorithm to identify symmetric sub-hypergraphs is efficient, with linear time complexity relative to the input size. This is important for practical applications on large-scale hypergraphs.\n\nThe paper reports extensive experiments on both hypergraph and graph datasets, demonstrating consistent improvements across different hyperGNN architectures. This suggests the method's potential broad applicability.\n\nCons:\n\nIt would be helpful to see more detailed comparisons with other state-of-the-art methods for higher-order link prediction. While the authors mention improvements, more context on how their method compares to other recent approaches would strengthen the empirical results.\n\nThere's limited discussion. There is limited discussion, particularly in the data augmentation scheme. More analysis in this area could help readers understand the robustness of the approach. Despite these minor points for potential improvement, the paper presents a novel and theoretically grounded approach to an important problem in hypergraph learning. The combination of theoretical analysis, algorithmic innovation, and empirical validation makes a compelling case for the method's effectiveness. The work makes a meaningful contribution to the field.\n\nDespite these minor points for potential improvement, the paper presents a novel and theoretically grounded approach to an important problem in hypergraph learning. The combination of theoretical analysis, algorithmic innovation, and empirical validation makes a compelling case for the method's effectiveness. The work appears to make a meaningful contribution to the field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of higher-order link prediction in hypergraphs, focusing on improving the expressivity of hypergraph neural networks (hyperGNNs) based on the Generalized Weisfeiler-Lehman-1 (GWL-1) algorithm. The authors propose a preprocessing algorithm to identify symmetric substructures in hypergraphs and a data augmentation scheme to break these symmetries during training. The goal is to enhance the ability of GWL-1-based models to capture fine-grained structural information without significantly increasing computational complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the above weaknesses.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b5Jo5EmHJR", "reviewer": "Reviewer_FDVh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The approach has a low computational complexity and since it is a data pre-processing step, it can be applied to any downstream hyper graph neural networks architecture.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors tackle the problem of hyper edge prediction in temporal hyper graphs. The motivation is that many approaches use  the GWL-1 algorithm that fails to distinguish some non-isomorphic cases.\nThey propose an efficient pre-processing algorithm that randomly drops hyper edges when maximally connected nodes with the same GWL-1 value are detected. They prove that this approach provably increases expressivity (i.e. the pair of k-node sets that became distinguishable) under certain conditions. They empirically evaluate the effectiveness of the approach on several hyper graph neural networks architectures on several dataset and compare it to a baseline of randomly dropping a hyper edge with a 50% uniform chance.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors make the following claims on the issues regarding existing alternative approaches:\n1. some methods depend on a fixed subgraph radius size which prevents capturing symmetries that span\nlong ranges across the graph\n2. some methods add metric information on each node relative to all other nodes which would be very computationally expensive on hyper-graphs\n3. some methods specifically tackle cycles (which are responsible for many symmetries) with approaches that are not permutation invariant or that attach cells to cycles yielding much denser hyper edge distributions \n4. some approaches use cell attention networks \nThe underlying notion is that the proposed approach does not have the same issues. It is however unclear if these issues have an effect in practice. It would be desirable to empirically show that this is the case:\n1. are there datasets where the hyper edge existence depends on long range dependencies? can it be shown that the proposed approach can deal with these cases? does the distance of the long range dependency have any effect on the performance of the method? (the downstream approach is still based on message passing, so it would be surprising if this was the case)\n2. the proposed approach is based on running the GWL-1 algorithm for L steps, so there is a cost associated, how does this cost compare in practice with the approaches that add metric information to nodes?\n3. does the proposed approach suffer from the presence of cycles? what is the dependency w.r.t. the density of cycles in input?\n4. what is the drawback of cell attention networks? does the approach deal gracefully with the cases that are difficult for cell attention networks?\n\nThe authors identify the conditions under which the approach guarantees that an increasing number of node sets become distinguishable: these conditions include the notion of L-separation and controlled growth of node set size. The paper would benefit from showing in practice that these conditions are met in real world cases.\n\nSimple baselines to gauge the difficulty of the tasks are not available. What is the performance of a hyper edge predictor based on a frequency threshold (e.g. if a hyper edge existed in the past above a certain frequency than it will be predicted to exist in the future).\n\nThe tabular results for the  empirical evaluation  are not easy to interpret, i.e. is the proposed approach significantly better than the baseline or then the random dropping approach? Please report a critical difference diagram (Demˇsar J (2006) Statistical comparisons of classifiers over multiple data sets. Machine Learning Research 7:1–30) to show the significance of the results (e.g. using https://scikit-posthocs.readthedocs.io/en/latest/generated/scikit_posthocs.critical_difference_diagram.html).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has gone through revisions, and I believe is now in good state.  There may be more suggestions, but I think the paper now hits the right notes.
Decision: Accept (poster)