Improved Expressivity of Hypergraph Neural Networks through High-Dimensional Generalized Weisfeiler-Leman Algorithms
Authors: Detian Zhang
Chengqiang Zhang
Yanghui Rao
Li Qing
Chunjiang Zhu
Venue: ICML 2025 poster (2025)
Keywords: Hypergraph Isomorphism Test
Generalized Weisfeiler-Leman Algorithms
Hypergraph Neural Networks
Graph Neural Networks
Expressive Power
Primary area: theory->deep_learning

Abstract: The isomorphism problem is a key challenge in both graph and hypergraph domains, crucial for applications like protein design, chemical pathways, and community detection.
Hypergraph isomorphism, which models high-order relationships in real-world scenarios, remains underexplored compared to the graph isomorphism.
Current algorithms for hypergraphs, like the 1-dimensional generalized Weisfeiler-Lehman test (1-GWL), lag behind advancements in graph isomorphism tests, limiting most hypergraph neural networks to 1-GWL's expressive power.
To address this, we propose the high-dimensional GWL (k-GWL), generalizing k-WL from graphs to hypergraphs.
We prove that k-GWL reduces to k-WL for simple graphs, and thus develop a unified isomorphism method for both graphs and hypergraphs. We also successfully establish a clear and complete understanding of the GWL hierarchy of expressivity, showing that (k+1)-GWL is more expressive than k-GWL with illustrative examples.
Based on k-GWL, we develop a hypergraph neural network model named k-HNN with improved expressive power of k-GWL, which achieves superior performance on real-world datasets, including a 6\% accuracy improvement on the Steam-Player dataset over the runner-up.
Our code is available at https://github.com/talence-zcq/KGWL.

Improved Expressivity of Hypergraph Neural Networks through
High-Dimensional Generalized Weisfeller-Leman Algorithms
Detian Zhang'
Chengqiang Zhang'
Yanghui Rao?
Qing Li Chunjiang Zhu 4
Abstract
1. Introduction
Hypergraphs have gained increasing attention in recent years, because of their ability to naturally model wide range of systems where regh relationships exist among their constituting parts. In hypergraphs, a hyperedge allows the connection of an arbitrary number of nodes and can eas- ily abstract high-order relationships in social systems (Lotito et al., 2022), biology Saachez-Gorostine authorship collaboration networks (Wu al., 2022), ecology (Grilli et al., 2017), and neuroscience (Xiao al., 2019). Despite the powerful expressiveness, hypergraph research, such as representation learning (Antelmi et al., 2023) and isomorphism test (Feng et al., 2024), has been underex- plored compared to the graph counterpart because of the inherent complexity and the lack of popular tools. ad- dition, simply transforming hypergraphs to simple graphs either leads an inevitable loss of information (Zhou et al., 2006) adds significantly many auxiliary nodes/edges that increase space and time requirements in downstream tasks (Yang et al., 2019; Yoon et al., 2020). It is demanding to develop hypergraph isomorphism test and representation learning algorithms. The two topics are closely related as the expressivity of hypergraph neural networks (HNNs), i.e., what functions the HNN models can approximate, can resort to the power of isomorphism test in distinguishing non-isomorphic hypergraphs (Morris al., 2023).
The isomorphism problem is key challenge in both graph and hypergraph domains, crucial for applications like protein design, chemical path- ways, and community detection. Hypergraph iso- morphism, which models high-order relationships in real-world scenarios, remains underexplored compared to the graph isomorphism. Current al- gorithms for hypergraphs, like the 1-dimensional generalized Weisseiler-Lehman test (I-GWL), lag behind advancements in graph isomorphism tests, limiting most hypergraph neural networks to 1- GWL's expressive power. To address this, we propose the high-dimensional GWL (k-GWL.), generalizing k- WL from graphs to hypergraphs. We prove that k-GWL reduces to k-WL for simple graphs, and thus develop a unified isomorphism method for both graphs and hypergraphs. We also successfully establish clear and complete understanding of the GWL hierarchy of expressiv- ity, showing that (k+1 I<+I) is more expressive than k-GWL with illustrative examples. Based on k-GWL, we develop a hypergraph neural net- work model named k-HNN with improved expres- sive power of k-GWL, which achieves superior performance on real-world datasets, including a 6% accuracy improvement on the Steam- Player dataset over the runner-up. Our code is available at https: /tt///itttt thub. coom/talenee calence-zcca KGWL.
et al., 2019), co-
In hypergraph representation learning, HGNN (Feng et al., 2019) used the clique expansion technique to approximate hypergraphs as graphs, and then ran graph convolution (Kipf & Welling, 2016) but cannot recover hypergraph structures with hyperedges in another hyperedge. HyperGCN (Yadati et al., 2019) replaced each hyperedge with incomplete clique. Then PlyperSAGE (Arya et al., 2020) first learned to embed hypergraphs directly by propagating messages in a two-stage procedure, which can be described as pass- ing messages from vertices to hyperedges, and then back to vertices from hyperedges. UniGNN (Huang & Yang, 2021) unified the two-stage hypergraph learning by gener- alizing several Graph Neural Networks (GNNs) to HNNs, pointing out that its expressive power is bounded by the I-dimensional generalized Weisfeiler-Leman test (1 (1-GWL). Subsequent works, such as AllSetTransformer (Chien et al.,
'School of Computer Science and Technology, Soachow Uni- versity, Suzhou, China "School of Computer Science and Engi- neering, Sun Yat-sen University, Guangzhou, China Department of Computing, the Hong Kong Polytechnic University, Hong Kong "Department of Computer Science, University of North Carolina Greensboro, Greensboro, NC. Correspondence to: Chunjiang Zhu <c Srchuu@unng.eduss
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Expressivity of Hypergraph Neural Networks through High- Digg--Dimensional Generalized Weisfeller-Leman Algorithms
2022) and ED-HNN (Wang et al., 2023), are also of the two-stage HNN type. Feng al. (2024) further introduced hypergraph isomorphism test algorithm, referred to as 1-GWL. It also mentioned that I-GWL can degrade into 1-
2. Related Work
2.1. Expressivity of GNNs
Two seminal works (Xu et al., 2018; Morris et al., 2019) related the problems of graph isomorphism test and GNNs, revealing that any GNN architecture cannot be more pow- erful than 1-WL. in terms of distinguishing non-isomorphic graphs. Morris et al. (2019) proposed new GNN architec- ture to overcome the limitations of 1-WL by learning fea- tures over the k-tuple vertices instead of vertices. Later, sev- eral works gradually proposed the incorporation of unique vertex identifiers (Vignac et al., 2020), randomized vertex labels (Sato et al., 2021; Abboud et al., 2021) and subgraph information (Zhao et al., 2021; Zhang & Li, 2021; Papp et al., 2021; Papp & Wattenhofer, 2022: Bouritsas et al., 2022; Qian et al., 2022; Frasca et al., 2022) into the vertex attributes to further enhance the expressiveness of GNNs. Zhou et al. (2023) unified this framework to propose the (k,/)-WL algorithm, which can be seen as applying k-WL to graph with / vertices that are assigned additional features. They also provided a theoretical analysis of the expressivity of (k.I)-WL, establishing an expressivity hierarchy for algo- rithms with different values of k and 1. Zhang et al. (2023b) studied the expressivity related to biconnectivity and de- signed a 1-WL's variant that can encode general distance metrics. Bodnar et al. (2021) developed a WL for handling simplicial complexes (generalizations of graphs). A more comprehensive discussion of the WL test in GNNs can be found in the survey (Morris et al., 2023).
WI. applied to graphs, thus promoting the theoretical unification of isomorphism tests.
Both GNNs and I-dimensional WL test (1-WL) (Weisfeiler & Leman, 1968) aggregate messages from neighbors and iteratively update node representations and can be consid- ered as neural and discrete variants. In the graph domain, researchers have striven for a good understanding that clas- sic GNNs, including GCN and GIN (Xu et al., 2018), have expressive power upper bounded by 1 1-WL (Morris et al., 2019), and a series of subgraph GNNs (Qian et al., 2022; Frasca et al., 2022: Zhang et al., 2023a) have expressive power at most 3-WL. Here, the dibensiinnii WL test (k-WL) (Immerman & Lander, 1990) can be viewed as us- ing k-tuples of vertices to replace the original vertices in the graph for isomorphism test. However, currently there is no research study that can enhance the expressivity of I-GWL in a systematic way as k-WI, resulting in that the expressive power of most current HNNS is limited to I-GWL. Therefore, a significant research gap exists in extending the I-GWL algorithm to its higher-dimensional counterparts and designing HNNs guided by these more powerful algorithms.
In this paper, we propose a nigher-dimensional version of 1-GWL, namely k-GWL. It is generalization of k-WL that can accept hypergraphs as input and process complex and diverse high-order relations therein. Based on the different aggregation methods of k-tuple neighbors, we propose two variants, namely the folklore variant k-GFWL and the obliv- ious variant k-GOWL. We prove that the proposed k-GWL. can degenerate to k- WL when applied to simple graphs, subject to that the initialization of k-tuple features uses our aob-hypegrraph extraction method that deletes singleton hy- peredges (Theorem 5.1). It unifies the high-dimensional isomorphism tests for both simple graphs and hypergraphs. Moreover, we prove the expressive power of (k+1)-GWi) surpasses that of k-GWL for k 2 1 (Theorems 5.2 and 5.3) with illustrative examples. The (k+1)-GOWL has the same expressive power as k-KFWL. for 2 2 (Theorem 5.4).
2.2. HNNS and Their Expressivity
The development of HNNs shifted from single-stage message-passingg framework (Feng et al., 2019; Yadati et al., 2019) to a two-stage update/aggregattin process (Arya et al., 2020; Huang & Yang, 2021; Chien et al., 2022; Wang et al., 2023). In particular, Chien et al. (2022) unified a whole class of two-stage models with multiset functions, which allows to learn the most adequate update/aggregation for individual dataset/task. Inspired by hypergraph diffusion (Li al.. 2020), Wang et al. (2023) proposed ED-HNN that computes specialized hyperedge-to-nod messages for nodes in a hy- peredge and can approximate any cemmutation-equivrrinn hyperedge diffusion. Huang & Yang (2021) developed a unified framework for GNNs and HNNs. It also proposed I-GWL for hypergraph isomorphism test following (Böker, 2019) and bounded the expressive power of UniGNN by 1-GWI. Feng al. (2024) separately developed 1-GWI. and also designed hypergraph subtree and hyperedge kernel methods that improved earlier hypergraph kernels (Wach- man & Khardon, 2007: Bai et al., 2014). In this paper, we propose a k-dimensional generalized WL algorithm (k- GWL), filling the research gap in hypergraphs where no higher expressive-power algorithm existed. Additionally,
With these, we successfully establish a clear and complete understanding of the GWL expressivity hierarchy (Eq. (7)).
Furthermore, we develop high-dimensional HNN models, namely k-HNNs, based on the proposed k-GWL. We show that K-HNNs are provably more powerful than existing HNN models and have expressive power at most k-GWL (The- orems 6.1 and 6.2). In our experiments, k-HNNs achieve superior performance across all datasets. Notably, on the Steam-Player dataset, our methods outperform the second- best approach by about 6% in accuracy.
2

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensionll Generalized Weisfeiler-LLman Algorithms
we design k-HNNs based on k-GWL, with its theoretical expressivity upper bounded by k-GWI. Luo al. (2023) studied the expressivity of hypergraph neural networks and constructed hierarchies of arity (the maximum number of vertices in hyperedges) and depth. For example, when the depth is larger than a certain value, a neural logic machine with larger arity is more expressive. In contrast, this paper generalizes k-WL to k-GWL, unifies graph and hypergraph isomorphism tests, and establishes clear generalized WL hierarchy for hypergraphs.
obtained by putting all elements in one position, while k- FWL aggregates the colors of neighbors obtained by putting one element in all k positions. Grohe & Otto (2015) proved that K-OWL is as powerful as the folklore (k- I)-FWL for k +>> 2.
However, the above isomorphism algorithms cannot be di- rectly applied to hypergraphs. Recently, the 1-dimensional Generalized WL (1-GWL) was proposed for the hyper- graph isomorphism test (Feng et al., 2024; Huang & Yang, 2021). 1-GWL considers two neighborhoods: vertex's 's hy- peredge neighbors (N(v)) and hyperedge's 's vertex neighbors (e).). In iteration 0, the colors of a (c) and cia) (v) are initialized using their original labels, if any. In iteration t > 0, the color updating rules are as follows.
3. Preliminary on the WL Algorithm
Let HG = EV,E, X) be a hypergraph, where V is the set of vertices, & is the set of hyperedges, and X' is the vertex feature vectors. In the incidence matrix H E {0, 1 1)1lix él, each entry H(v, e) indicates whether vertex is in the hy- peredge (w) denotes the set of hyperedge neighbors of vertex i.e., hyperedges containing v, and (e) denotes the set of vertex neighbors of hyperedge e, i.e., vertices in e.
(e) HASH (c (e), HG (1) (EN(())
(0) = HASH (t (cl (v), (G) | (ENN)()))
Huang & Yang (2021) proved that the two-stage HNN, UniGNN, has expressivity upper bounded by I-GWL. It is
The 1-dimensional Weisfeiler-Leman (1-WL) (Weisfeiler & Leman, 1968) is a classic algorithm for graph isomor- phism test and has expressivity no worse than classic GNNs. Let G be a graph with possibly labeled vertices. In iteration O, the coloring 6j (v) is initialized by the label of vertex v or a uniform value if no label is provided. 1-WL iteratively updates the color for vertex u according to its original color and the colors of its neighbors. Specifically, the color is computed as
easy to see this also holds for AllSet and thus many HNNs that are its special case (Thm. 3.4 in (Chien et al., 2022)).
4. High-Dimensional Generalized WL
(0)
In this section, we present our main method k-GWL for the hypergraph isomorphism test. For clarity, tuples are ordered and allow repetitive elements; multisets are unordered and allow repetitive elements; and sets are unordered and do not allow repetitive elements. In k-GWL, we consider k-tuples, which allow repetitions of vertices. There are two types of hypergraphs: the input hypergraph and the k-tuple hyper- graph (see its construction in Section 4.1.2). Hyperedges in both types of hypergraphs are sets, that is unordered.
1t (v) = HASH( (ct (v), (ai (w)))E))))))))
where HASH bijectively maps the above pair to unique color which has not been used in previous iterations.
It is well known that 1-WL is not able to distinguish all non- isomorphic graphs (Cai et al., 1992). The k-dimensional Weisteiler-Leman (k-LL) was proposed to improve the expressiveness (Immerman & Lander, 1990). It assigns colors to k-tuples of vertices and iteratively updates them. In iteration 0, the color (00)) (v) of k-tuple v E G* is initialized as the isomorphism/atomic type of the subgraph induced by k vertices in v. In iteration & > 0, the color of tuple v is computed by
4.1. How k-G Works
For our proposed k-GWL hypergraph isomorphism test, the k-WL algorithm is a natural reference. The principle of k-WI K-WL is to color k-tuples instead of single vertices. To achieve that, it builds a k-tuple graph with each vertex as k-tuple, initializes the k-tuple features, and then applies 1-WL graph coloring in the k-tuple graph. To develop the k-GWI. hypergraph isomorphism test algorithm, we ask the following research questions (RQs):
C (v) = HASH(C Ck (v),
(1)
(v,,(v.w) w E V(G)) 1 <
RQ1: How can we initialize the k-tuple features in the k- tuple hypergraph while ensuring that, when given a simple graph input, the k-tuple features keep the same as k-WL?
where (v, w) refers a high-order neighbor of obtained by replacing the jth element of v by w. There is another variant of k-WI. that differs slightly in how they aggregate neighborhood information and is denoted folklore k- WL (k- FWL) in machine learning literature (Maron et al., 2019; Morris et al., 2019). The above one is called oblivious k- WL OW-)..). K-OWL aggregates the colors of neighbors
How can we construct the k-tuple hypergraph from the original hypergraph so that we can apply 1-GWL hyper- graph coloring?
RQ2:
RQ3: How to develop HNNs with an expressive power up-
3

---

Improved Expressivity of Hypergraph Neural Networks through High- Highh-Dimensional Generalized Weisfeller-Leman Algorithms
per bounded by k-GWL, significantly improving the upper bound 1-GWI. of most existing HNNs?
subsequent theoretical analysis. The singleton deletions are reasonable, since the main role of hyperedge connections is to represent higher-order relations among multiple vertices, With only one vertex in a hyperedge, it might be good to remove it. We put detailed explanation in Appendix C. In our experiments, we find that the removal of singleton hyper- edges significantly enhances the hypergraph classification performance.
In the following, we discuss how to address these research questions one-by oe- (with RQ3 answered in Section 6) and explain our k-GWL methods.
4.1.1. K- K-TUPLE FEATURE INITIALIZATION (RQ1)
The initialization of k-tuple features is a crucial step in realizing the strong expressive power of k-dimensional hy- pergraph coloring, A random initialization cannot capture unique characteristics of the collection of k vertices in each k-tuple and is limited in getting theoretical guarantees on the expressivity. A more desirable way is to initialize k-tuple features according to the isomorphism type of the induced nub-hypergraph. In this way, two k-tuples get the same initial color if their induced pub-hypeggraphs are isomor- phic. This helps build necessary connections among those k-tuples to ensure the theoretical expressivitiy. We formally define two isomorphic hypergraphs:
graph
hypergraph
equivalent
V2
Y2
subgraphs induced by (21 and (v1.v3)
v3
Definition 4.1. Given hypergraphs HC1 (V1, H1)X1), HgG = (V2, H2, X2) with vertex features X1, X2 and k- tuples s², s² in HG, and HCg (with the jth element as s! sf). respectively. We say s', s² are isomorphic and have the same isomorphism type (or called atomic type) iff
Figure 1. Induced sub- sub-hypergraph extraction.
Formally, as the first step of k-GWL, initialize the color of k-tuples s = (UI,..., Ux) E V(HG)* instead of individual vertices.
Viz, is E [k], = 1/1 s = /
c (s) = ISO
(2)
E [k], X = X2.22.
where (s) represents the sub-hypergraph of HG in- duced by the k-tuple s using the above technique, and the ISO function colors a sub-hypergraph according to its iso- morphism type.
Wig,..., in (s.,,...s s2 H²2
[k), (s!,.....!)
E
H'
Extracting the sub-hypergraph induced by (vertices in) k-tuple is required and crucial step, before computing its isomorphic type. While computing the subgraph induced by k-tuple in a simple graph is trivial (obtained by re- taining only the rows and columns of the adjacency matrix corresponding to vertices in the k-tuple), the counterpart operation in hypergraphs needs special and careful consid- erations. Taking Fig.
4.1.2. K- T-PLL HYPERGRAPH CONSTRUCTION (RQ2)
In k- WL. k-tuple graph is constructed where two k-tuples are connected, called neighbors, if they differ only by one of the k entries. Then, 1-WL can be applied on the graph to lift the expressivity up to k- k-WI.. In the hypergraph setup, 1-GWL must be applied in hypergraphs, but it is not clear how construct hypergraph structures based on k-tuples to preserve their high-order relations.
example, the top graph and hypergraph equivalent and we given 2-tuples (U1, vs) and (vi, v2). But if we simply keep the corresponding rows and non-empty columns in the incidence matrix (similar to simple graphs), then the resulting sub-hypergraph in the bottom right would not be equivalent as the subgraph in the bottom left! This is because after the extraction, there are multiple hyperedges that contain only a single vertex. This would prevent the degeneration of k-GWL to k-WL for input simple graphs
In the proposed k- k-GWL, the connection patterns between k- tuples are still rooted at and managed by their neighborhood relations, i.c., being the same in all k entries but only one entry. First, let (, w) be the k-tuple obtained by replacing the 5th element of s by w. We define the neighbors of a k-tuple (v1, 2%) in ((Hg)* as k-tuples obtained by replacing the j-th component of by w E V(HG). The definition of the neighbors of a k-tuple N(s) is the same as the graph setting.
To address this issue, we propose to delete singleton hyper- edges (those with only a single vertex). With this extra step, the subgraph and nub-hypergraph extractions become consis- tent and aligned for input simple graphs, paving the road for
N(s) [0,(s, w) (VI, (U,, Ug-1, w. Uyt1. vk)
(3)
15 j S ki w E V(HG))

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensionll Generalized Weisfeller-Leman Algorithms
are included in hyperedge e3.
original hypergnaph
3-tople
In the oblivious hypergraph HGk,o, a k-tuple has k hy- peredges, one for each position j represented as (fs} U {0,(s, w) | w V(HH)))). The set of hyperedges Eg in the oblivious hypergraph HG is then defined as follows:
Depan:
PP
& - u w) w E V(H9)}) 1 i k s V(H()**
(5)
K-GOWL Hypergreph Neijhhers
K-SPWL Hypergraph Nasphborr tiin
As an example, in Fig. right, when we choose the first position as j to replace every vertex with u1, the resulting 3- tuples (22, 02, v3), (03, 02 v3). (ug, U2 vz), and (vy, 02 va) together with s are placed in hyperedge 61. When we choose the second and third positions as j respectively, we have that (U1, u1 v3), (01, D3 U3), (01, U1, 23), (U1, Ub. v3)) and s are in hyperedge 62 and (V1, U2 e1), (V1; U2, U2), (2), 02, U4), (U1, U2, 03) and are hyperedge ez. It should be noted that the construction of k-tuple hypergraphs in k-GWL does not depend the actual hyperedges in the original hypergraph, which are only used in the isomorphism type. It will be different for HNNs in Section 6 though.
K-6PWL Hopergraph Local Neghbarr
K-GOWL Hypangroph Lecal Neighere
Figure 2. Illustration of k GFFL and k-GOWL hypergraph neigh- bors and hypergraph local neighbors for k-tuple (U1, V2, Ua), where A 3. When considering set-based k-mples, k-tuples with re- peated vertices are absent, such as es, 64,, and eş in the left.
is natural connect k-tuple and each of its neighbors using hyperedge, similar to k-WL. But this would result in k n hyperedges only for a k-tuple, making it prohibitively large and limiting the scalability. Instead, it is reasonable to connect a k-tuple with multiple k-tuples in its neighbors us- ing a hyperedge, since they formulate a high-order neighbor- hood relationship. We construct two types of k-dimensional hypergraphs, depending on changing position j or vertex w to identify the neighboring k-tuples (which will affect the aggregation methods in applying 1-GWL later). They are the k-dimensional folklore hypergraph HGk. and k- dimensional oblivious hypergraph HG*.o for k-tuples. The k-GWL variants running on them are called k-dimensional folklore GWL (k-GFWL) and k-dimensional oblivious GWL (k- GOWL), respectively.
Both k-GWL and k-WL allow repetitions of vertices in k-tuples. In the initialization of k-tuple features, they ex- tract sub-hypergraphs and subgraphs induced by the set of vertices in k-tuples and then use the isomorphism type as features, where the set operation before extraction re- moves vertex repetitions. For the construction of k-tuple hypergraphs and k-tuple graphs, because tuples allow repeti- tions, the vertex replacement strategies in the oblivious and folklore variants ("all elements in one position" vs. "one element in all k positions") still work with no issues.
4.1.3. APPLYING 1-GWL IN K-TUPLE HYPERGRAPH
With k-tuple hypergraph HG (either HGR, or HGk,o) at hand, we can proceed with applying 1-GWL to iteratively update the color of every k-tuple s, cg at iteration t. In each iteration, 1-GWL updates both colors of hyperedges (0) (e) and k-tuples of (s) in the k-tuple hypergraph H9K, (0) The initial colors c (e) for all hyperedges are the same while the initial k-tuple colors Cj (s) are set based on their isomorphism type. Let NN(e)) be k-tuple neighbors of hy- peredge e and (s) be hyperedge neighbors of k-tuple s. The updating rules are defined as follows:
In the folklore hypergraph HGr. k-tuple has n hy- peredges, one for each vertex E V(HG) represented as (s. 61 (s, w), (2 ()), .........s.. (s, w)). The set of hyperedges E among k-tuples in HGr, is defined by the following formula:
(1)
Ex,, = (s, (s, w), (2,s, w), ... (x(s,w)) (0,,,.,,,,ss I
(0)
(4)
w E V(H9), s E *
For example, in Fig. 2 left, we consider the 3-tuple (V1, U2, 03) as our k-tuple s with & 3. If we choose V4 as vertex w to replace vertex at each position of s, the resulting 3-tuples (va, 12, va), (vi, us, 0s), (vi, U2, 14) together with s itself are included in hyperedge ei. If we choose Us as vertex w, the 3-tuples (1s, U2 vg). (V), Us vg). (11, U2, Us) and s itself are included in hyperedge e2. If 11 chosen, the 3-tuples (vi, 01, v3), (1i, 02, 01) and s itself
(4) k (e) = HASH C
(e), lo (1) (G(e))
(4)
(s) HO)-HASH( Co (s). (() (e) (eE
The process can be considered as two-stage updating: first update hyperedge colors by the colors of k-tuples in it and its color in the previous iteration, and then update k-tuple
5

---

Improved Expressivity of Hypergraph Neural Networks through Higgh-Diennsonal Generalized Weisfeiler-LLman Algorithms
colors by the newly updated colors of hyperedges containing it and its color in the previous iteration. For example, in Fig. 2 left, we compute the color of the 3-tuple (v1, U2, v3) as follows. We first aggregate the colors of (V), U2 03), (vi,
isomorphism tests for both simple graphs and hypergraphs.
Theorem 5.1. Given a simple graph g E), let (RR)))()) and ((k.) (s) be unique color labels that the k-WL and k-GWL assign the k-tuple to, respectively, There exists a bijective function & that maps the color C(R, (s) from k- t-WL to k-tuple color ((k.gul)(s) from k-GWL.
(4,,"4,00 M4,, va), U2, 12, U4), (v1, V2, va), and é1 to update the color of e1. Similarly, the color of eg is updated. Then, we use the updated colors of e₁ and e2 and the previous color of (11, U2, 03) to update the 3-tuple's color. After each iteration, compare the multisets of k-tuple colors for two input hypergraphs. We can determine whether they are isomorphic or not in at most h iterations. The pseudocode of proposed k-GWL is shown in Appendix B and multiple complete executions of k-GWL are shown in Appendix D.
To construct the GWL hierarchy, our theoretical results indicate that as the dimension k increases, the expressive power of k-GWL stricill increases and (k+1) (K+1)-GOWL. has the same expressivity as k-GFWL for k > 2. We will show shortly that 2-GOWL has a stronger expressive power than 1-GFWL.
Theorem 5.2. Vk 2 L, (k+1)-GOWL > G-GLLL
4.2. Complexity
Theorem 5.3. Vk 2 1, (k+/) k-GFWL.
The computational complexity of the proposed k-GWL with iterations is (hm)) where m is the complexity in one iteration and m = |V]d, + [E]dg. Here du and de are the average degrees of vertices and hyperedges in the k-tuple hypergraph H (instead of the original hypergraph). In
Theorem 5.4. vk 2 (k+1)-GOWI = k-GFWI.
(r)
(b)
48
N
HGK.. and K. we can derive the number of hyperedges [E] based on their definitions: |E in H9r., is n* n, while in H&s.o. | is ne* k. Here n represents the total number of k-tuples in (HHG). Additionally, the average de- gree de in / is k whereas in Hg.... it is n. Therefore, the total time complexity for both k-GFWI, and k- k-GOWI. algorithms are Ohh- n² n k) = Ohhk- 1** Here the run-time is independent of the number of hyperedges in the original hypergraph.
15
v6
47
g
g
g
N8
Figure 3. (a) A Hard Instance that 1-GWL fails but 2-GOWL suc-
coeds; (b) A Harder Instance that 1-GWL and 2-GOWL fail but 2-GFWL succeeds.
In the graph realm, the WL hierarchy is quite clear that
5. Theoretical Properties
1-OWL _ I-FWL _ 2-OWL
In this part, we discuss theoretical results on the expres- sive power of the two variants of k-GWL to distinguish non-isomorphic hypergraphs. All the proofs are given in Appendix A. For two isomorphism algorithms A and B, we denote their respective final colors of hypergraph HG as CA (HG) and св (HG). We say:
< 3-WWW = 2-FWL
(6)
< 4-OWL _ 3-FWL....
and most GNNs (such subgraph GNNs (Frasca et al., 2022)) have expressive power no greater than 3-OWI. The progress in the realm of hypergraphs lags much behind, with only 1-GWL developed before our work. In this work, we successfully establish a clear and complete understanding of the GWL hierarchy, which is outlined below:
A is more powerful than B (B 3 A) for any pair of hypergraphs HG, and HG2. c, = ca (HG2) + (HH9)) (B(HG2) Otherwise, there exists pair of hypergraphs that B can distinguish while A cannot, denoted as B A A.
1-GOWL _ 1-GFWL- - 2-GOWL
< <3-GOWL 2 2-GFWL
(7)
A is powerful as B (A B) B 3 A B.
< 4-GOWL 2 3-GFWL....
A is strictly more powerful than B (B < A) if
Remarkably, unlike that 2-0WL ~ 1-WL in the WL hi- erarchy, have 2-GOWL > 1-GWL in the hypergraph GWI. hierarchy. To showcase, we give hard pair of hy- pergraphs in Fig. 3(a) which 2-GOWL successfully dis- tinguishes but 1-GOWL and 1-GFWL fail. We also pro- vide another pair of hypergraphs in Fig. 3(b) to confirm 2- 2-GFWL > 2-GOWL. Both 1-GWI, and 2-GOWI. fail
A A A z B.
5.1. The GWL Hierarchy and Connection with Existing WL algorithms
We first show that k-GWL degenerates to k- WL for simple graphs (instead of hypergraphs), unifying high-dimensional
6

---

Improved Expressivity of Hypergraph Neural Networks through High- High--Dimensionll Generalized Weisfeiler-Leman Algorithms
to distinguish the non-isomorphic hypergraphs, whereas 2-GFWL successfully identifies them. We refer readers to Appendix D for detailed and step-by-step executions of k-GWL in these hard instances. In fact, the hypergraphs in Fig. 3(a) can be distinguished only by the initialization step of 2-GOWL, whereas those in Fig. 3(b) require the subsequent color refinement in 2.. The established GWL expressivity hierarchy can not only help improve our understanding on the theoretical capability of existing meth- ods, but also guide the development of highly expressive and practical hypergraph models.
6. k-Dimensionall Hypergraph Neural Networks (k-HNNs)
In the following, to address RQ3, we propose k-HNNs based on the k-GWL algorithm, whose expressive power is upper bounded by k-GWL. Due to scalability and limited GPU memory, we consider set-based k-tuples in the k-GWL, called k-sets, where ordering and repeated vertices in a tu- ple are ignored. We treat each possible k-set as a vertex and construct hypergraph structure based on the k-sets. As discussed earlier, we can construct two types of k-set hypergraphs, HGR. and HGR.... based on Equations (4) and (5), respectively. However, to further leverage the structural information in the original hypergraph HG and reduce GPU memory usage, we define a local neighborhood construc- tion for the k-set hypergraph. The local neighbors of a k-tuple (UI, .... v&) are defined as follows:
5.2. Further Improving HNN Expressivity by Adding Vertex Labels
Zhou et al. (2023) devised fairly general method to en- hance the GNN expressivity through adding limited labels to vertices. The method can be applied to our k-GWL to further enhance the expressivity. Their idea is to assign extra labels I,...., to / vertices, but runs k-WL on the whole graph with the additional labels only for those I ver- tices. This is repeated for every possible labeled graph and then the final representation of the graph is aggregated from the representations of all labeled graphs. This pro- duces (k,l)-WL with a strictly stronger expressive power than k-WL for 2 2. It is straightforward to implement the approach in k-GWL., which results in (k,I)-GWI. with even higher expressivity. However, the heavy computational cost of O(h (7)* n2* n k) makes it impractical. We perform an additional experiment on (1,2)GGWL to validate the performance as shown in Appendix E. We leave the development of efficient sampling methods for hypergraphs and adding more expressive vertex labels (e.g., structural and positional encodings for vertices), instead of using only vertex IDs in I-tuples, for future work.
N(s) = {0, w) = (UI,... Py W, 1J+1, ub)
(8)
1 $ j - k, w E V(HL), (w, m5) E E(H())
In the prumed k-set hypergraph structures, Hok.s and Hg' we trim the original neighbors of each k-set by retaining only those neighbors with the differing nodes vj and belonging to the same hyperedge in the original hy- pergraph HG. For example at the bottom of Fig. 2, the local neighbors of (V1, U2 U3) contain only 3-sets (vi, U2, 24) and (ui, U2, 05), with other 3-sets pruned such as (14, 02, va) and (V1, Ug 03). This is because, in the original hypergraph, only Uy shares hyperedge with 04 and its but v1, d2 do not. We observe subtle differences in the resulting local k-set hypergraph structures: in the k- k-GFWL version, (v1, 02 v2) and (e1, U2 U2) belong to two separate hyperedges, whereas in the k-GOWL version, they are in the same hyperedge. Unlike k-GWL, for k-HNNs based on local neighborhoods, the actual hyperedges of the input hypergraph do influence the construction of the k-set hypergraph.
5.3. Applying k-WL to Graphs transformed from Hypergraphs
Given the k-set hypergraph H (= Hg. , or Hg! k. we can apply any base HNN (of expressivity at most I-GWL) in k-HNN to significantly enhance the expressivity to be at most k-GWL. Similar to k-GWL, we first initialize the isomorphism type of all k-sets based on their induced sub- hypergraphs. In the implementation, one could use I-GWL to determine the isomorphism type. which shows promising empirical performance our experiment since induced sub- hypergraphs are often small. To take advantages of the base HNN, we combine the embeddings learned by the base HNN with the isomorphism-tyre fcatures fis to get the k-set initial features, which can be expressed as:
One could transform hypergraphs to graphs via a bijec- tive mapping. such as the star expansion or line expansion (Yang et al., 2022), and then apply L- on the transformed graphs for isomorphism testing. This looks promising at first glance. However, even though the transformation is bijective, it does not guarantee the results of k-WL on the transformed graphs are the same as those of k-GWL the original hypergraphs. For instance, we can find two non-isomorphic hypergraphs where k-GWL. can distinguish them but k-WL cannot distinguish their transformed graphs. Figure 3(a) provides such an example: while 1-WL (equiva- lent to 2-OWL.) fails to distinguish the transformed graphs, 2-GOWL successfully identifies the original hypergraphs. Therefore, this indirect method does not achieve the same expressive power as our k-GWL algorithm.
(0) +
(())
D Wo))
(9)
WEB
where xx is the initial feature of k-set s in HG', x1 is the embedding of vertex e learned by the base HNN, and W.
7

---

Improved Expressivity of Hypergraph Neural Networks through Hiigh-Dimensional Generalized Weisfeller-Leman Algorithms
is the learnable parameters. We also define that all initial features of hyperedges in Hg9 are the same.
hypergraph deep learning models with target expressivity k-GWL, similar to the relation between k-IGNs and k-WL. (Maron et al., 2019).
Then in each K-HNN layer t > O, we can compute the feature vector for each k-set in [V(H])] by the base HNN. In our implementation, we adopt the following variant of UniGNN as the base HNN:
Theorem 6.1. Given a hypergraph HG = [V,E} and let
k P 2. Then for all iterations 2 0. for initial features zs (0) consistent with the initial colorings e of and for all weights W(O)
2 = =D= Hy (1111) w (t-1)
(10)
(11) Theorem 6.2. Let A: HG + Rd be a k-HNN based on k-tuple neighborhood. With a sufficient number of layers, for any pair of hypergraphs that k-GWL, determines as non- isomorphic, A also determines them as non- non-isomorphic if (1) the aggregation and update functions in the base HNN of A are injective, and (2) A's hypergraph embedding readout function is injective.
(1t) = oD_ Hy xe ) + x= (t-1)
where x!" and =² are the latent representations of hyper- edge and k-tuple in HGL, at layer i, respectively. W!)) and W are the learnable parameters. a is an activation function, such as ReLU. Hş is the incidence matrix of hy- pergraph Hg D₂ and De the diagonal matrices of the k-set degrees and hyperedge degrees. Additionally, we add residual connections (He et al., 2016) as a means of alleviating the oversmoothing phenomenon.
7. Experiments
In this section, we give brief discussions on the experiments and the details of experimental setups and results are in Appendix E.
vertex embedding:
Input:
Base HNN
Datasets: In the experiments, we adopt three types of real- world hypergraph classification datasets proposed in HIC [14), which are IMDB, Steam- Paaaer, and -witter-Friend, ranging from movie staff's game players, social media. The IMDB dataset further contains four distinct subsets. To assess the efficacy of capturing distinct correlation struc- tures, all datasets exclude the original vertex features. Keep- ing the original vertex features makes it easier to distinguish -onmisomooppicc hypergraphs, due to the potentially very different vertex features. Hence, it is a common practice to exclude these features and focus on structural informa- tion only. See statistics of the datasets and the constructed k-tuple hypergraphs in Tables 5, 6 and 7 of Appendix E.
pree-prccess k-set hypergraph
feature concat
k-set structure:
isomorphsim feature:
k-def init feature:
42
sn
me
hypergraph embedding
k-det embodding
S-Set HNN
roadout
HG
Figure 4. Illustration of the proposed k-dimensional HNNs.
After calculating the embeddings x²5 for all k-sets in the fi- nal layer (7-th layer), we can apply a permutation-invarian readout function, such as the sum function, in the k-set embeddings and obtain a hypergraph-leve embedding as: f(H)) = >voo xx (T), This resulting hypergraph em- bedding can then be used for downstream tasks, such as hypergraph classification. The complete workflow of the model is shown Fig. 4.
Compared Methods: All experiments are conducted on a server with 1080Ti GPU 11GB, except for 3-HNNs run- ning on a GPU cluster with 40GB memory. Due to the two different neighbor aggregation approaches, we obtain two variants of our models: k-FHNNs and k-OHNNs. For fair comparisons, we choose competitive hypergraph deep learning methods as baselines, including MLP, HyperGCN (Yadati et al., 2019), HNHN (Dong et al., 2020), UniGNNII (Huang & Yang, 2021), AllSerTransformer (Chien et al., 2022), ED-HNN (Wang et al., 2023), and HIC adapted from the 1-GWL subtree kernel method (Feng et al., 2024). The number of layers and the number of parameters for all the models are in Appendix E.7.
Expressivity The expressivity analysis of k-HNNs is based on k-tuples, instead of k-sets. To demonstrate the expres- sivity of k-HNNs, let [ d denote that k-tuple coloring e refines k-tuple coloring d, or equivalently, c(v) = c(w) implies d(v)= = =d()) for every k-tuple v, w. We prove that the coloring ck from k-GWL refines the features (t) which means that k-HNNs have expressive power upper bounded by k-GWL. We further show that when the ag- gregation, update, and readout functions are injective, the expressivitiy of k-HNNs is the same as k-G The devel- opment of k-HNNs allows us to have new way to design
(()
Main Results The experimental results for three types of real-world hypergraph datasets are presented in Table 1. First, our proposed two HNN models outperform other com- pared methods across all datasets. Notably, on the Steam- Player dataset, 2-FHNN outperforms the runner-up model,
8

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized Weisfeller-Leman Algorithms
Table 1. Experimental Results on Various Datascts
IMDB- FORM
IMDB-DIR GENRE
IMDB. FRI-
IMDB WRI-GENRF
STRAM-PL
TWITTER
MLP
62.97:1.555
71.62+1.31
52.94
34.7343.16
56.3010.99
60.31
HYPERGCN
65.70=3.12
78.4621.37
49.7244.34
31.03+5.71
59,02+1.27
63.9242.11
HNHN
67.10a1.46
79.30s1.92
55.2942.86
44.9142.84
58.48&1 .09
61.2340.9 99
UNIGCNHI
64.90=1.57
75.16#0.92
52.41+3.10
40.19:2.08
58.8941.40 .40
60.9242.32
SRTTRANNSSRRR
66.76+2.55
79.31+0.94
52.6744.77
54.09+2.41
61.87+1.87
64.03+1.3
ED-HNN
66.181
74.65a181
50.0743.13
35.0742.10
58.3542.22
60.7642.18
HIC
19.1.94.49
79.43+0.63
49.74a5.09
49.83+3.35
58.35&1.01
62.37&1.61
2- 2-OHNN
67.25a2.35
79.75a1.14
55.3543.74
50,08&1.89
65.97&1.37
64.12a1.30
2-FHNN
68.11+2.46
78.52+1.07
55.36+3.30
45.44=1.24
67.53+1.23
62.37=1.91
3-OHNN (SAMPLE SIZE 10)
67.66 07.6922.59
79.11=1.11
52.75:4.12
$7.5013.55
63.00:2.00
62.97+2.04
3-FHNN (SAMPLE SIZE
67.07:2..3
78,90:1.10
50.56.1..9
53.8412.05
61.50:11.59
63.05.3..67
Table 2. Results on Different Sub-Ilyeergraph Extraction Methods
Table 4. Time per Epoch (s) for Different Samplings (2-FHNN)
2-FHNN
2-FHNN-S
2-OHNN
2-OHNN-S
20
AL.1
IMDB-Dre DIR-FORMI
68.11+2.4
58.55a1.3
67.25:2.3
60.11#2.0
IMDB-DID -EEBB-DDR-FOOO DIR-FORM
7.58
8.46
8.46
8.58
10.27
IMDB-DuR-Gain
78.52+1.0
76.33+1.2
79.75+1.1
74.79+1.0
IMDB-DIR- DIR--GERE
13.81
14.59
15.34
15.54
20.71
IMDB WRI- FORM
55.3613.3
53.0642.9
55.35+3.7
51.94+24
IMDB BMDB-WRI-PRRE -RRI-ORM
1.49
1.57
1.59
1.59
1.72
IMDB-WER WRI-GENRE
45.44a1.2
36.3811.5
50.08:1.8
35.9542.3
IMDB-WRI-GHIE WE---RRGGEEE
4.67
4.86
4.83
5.06
5.89
STEAM-PLAYER 67.53+1.2
59.5621.0
65.97=1.3
59.17=1.7
SUTTIM-FRRIEND
62.75+2.1
60.89+1.6
64.12+1.3
61.23+2.1
STEAM-PLAYER 10.75
11.10
11.21
10.87
11.16
TWITTER-
6.82
7.13
7.63
7.34
7.77
Table Results on Sample Vertex Numbers (2-FHNN)
select the top m vertices with the highest degrees. These sampled vertices are then used to construct the k-tuple hy- pergraph and train the models, while the remaining vertices are ignored. Considering the distribution of vertex numbers across the datasets, set m to 5, 10, 15, and 20, result- ing in four experimental groups. The selected results in Table 3 show the effectiveness of the sampling method in approximating the hypergraph classification accuracy.
10
15
20
ALL
IMDB-Du-
66.45e1
65.9742.5
66.51=1.4
d6.67e2.8
68.11+2.5
IMDB-DIR
76.24a1
77.49x1.2
77.40s1.4
77.0422.7
78.52a1.1
IMDB-WaI-Freet
52.33+4
52.78+44
48.6--52
51.11+5.2
55.3643.3
JMDB- Wxt GENRE
47.9363.3
43.1012.3
38.3612
37.3611.
45.Ma1.2
SLEAM-PLAYIR
61.81+2.2
63.45+1.7
65.891199
65.98e15
67,53+1.1
TWITER-PRIENS 62.1521.3
61.081122
62.85=2.1
62.3181.8
62.7582.2
AlsSerTransformrr, by 6% in accuracy. This advantage stems from our model, guided by k-GWL, being able to better capture the high-order structures within hypergraph data. Second, we have run experiments on k-HNNs for k based the vertex sampling strategy with sample size 10 in GPU cluster with 40GB memory. Although not the full 3-HNNs without the sampling. 3-HNNs with the sampling have comparable performance to 2-HNNs across the datasets, while significantly outperforming in the IMDB- Wri-Genre dataset. Third, although 2-FHNN is theoretically more advantageous than 2-OHNN, experimental results re- veal mixed performance across datasets, with each outper- forming in half of the datasets.
Runtime Results To investigate the time complexity of the k- HNNN model, we record the average time required to run one epoch across different datasets and different sampled vertices. Selected results are presented in Table 4. We observe that as the number of sampled vertices decreases, the time required for the model to complete one epoch also decreases. For instance, in the IMDB-Dir-Gent dataset, where the hyperedge degree is higher, the time to complete one epoch decreases by nearly 50% when going from full sampling to sampling vertices.
We also conduct comparative experiments for two sub- hypergraph extraction methods. We append "-S" to the model name when keeping all hyperedges, including sin- gleton hyperedges, in extracting uub-hypergraphs. Table shows the proposed induced sub-hypergraph method not only supports the unification graphs and hypergraphs, but also offers significant empirical advantages.
8. Conclusion
We establish a generalized WL hicrarchy for hypergraphs with increasing expressivity, with the notable difference be- tween 1-GFWL vs. 2-GOWL, unlike its graph counterpart. The hierarchy allows us to design hypergraph neural net- works with the desired expressivity, improves upon most ex- isting hypergraph neural networks whose expressive power is upper bounded by 1-GWL. It is interesting to develop computationally efficient hypergraph deep learning models with provably high expressivity for a large value of k in k-GWL. It is also an interesting direction to characterize the expressive power of graph and hypergraph transformers.
Influence of the Vertex Sampling Strategy In k-HNNs, the time complexity inevitably grows exponentially with the in- crease in To reduce the complexity of k-tuple hypergraph construction, we propose a vertex sampling strategy: we sort the vertex set of each hypergraph dataset by degree and

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensionll Generalized Weiseeller-Leman Algorithms
Acknowledgments
lern Analysis and Machine Intelligence, 45(1):657-668, 2022.
This work was supported by Project Funded by the Priority Academic Program Development of Jiangsu Higher Edu- cation Institutions (PAPD). The work of Yanghui Rao was supported by the National Natural Science Foundation of China (62372483). Qing Li has been supported by the Hong Kong Research Grants Council under General Research Fund (project no. 15200023) as well as Research Impact Fund (project no. R1015-23). Chunjiang Zhu has been supported by Natural Science Foundation CCF-2349369.
Cai, J.-Y., Fürer, M., and Immerman, N. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-110, 1992.
Chien, E., Pan, C., Peng. J., and Milenkovic, O. You are allset: multiset function framework for hypergraph neu- ral networks. In International Conference on Learning Representations, 2022.
Dong. Y., Sawin, W., and Bengio, Hnhn: Hyper-
Impact Statement
graph networks with hyperedge neurons. arXiv preprint
arXiv:2006. 12278, 2020.
This paper establishes a clear and complete understand- ing on the expressivity hierarchy of GWL for hypergraphs, which guides the development of highly expressive, practi- cal hypergraph models. The hypergraph theory and general hypergraph deep learning models proposed in this paper do not have special societal impacts that should be emphasized.
Feng. Y., You, H., Zhang, Z., Ji, R., and Gao, Y. Hypergraph neural networks. In Proceedings of the AAAI confer- ence on artificial intelligence, volume 33, pp. 3558-3565, 2019.
Feng, Y., Han, J., Ying, S., and Gao, Y. Hypergraph iso-
morphism computation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
References
Abboud, R., Ceylan, I., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with random node initialization. International Joint Conferences Artificial Intelligence Organization, 2021.
Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H.
Understanding and extending subgraph gnns by rethink- ing their symmetries. Advances Neural Information Processing Systems, 15:31376-31390 2022.
Antelmi, A., Cordasco, G., Polato, M., Scarano, V., Spag- nuolo, C., and Yang, D. A survey on hypergraph repre- sentation learning. ACM Computing Surveys, 56(1):1-38, 2023.
Grilli, J., Barabás, G., Michalska-Smitte M. and Allesina, S. Higher- interactions stabilize dynamics in com- petitive network models. Nature, 548(7666):100-1111 2017.
Arya, D., Gupta, D. K., Rudinac, S., and Worring, Hy- persage: Generalizing inductive representation learning on hypergraphs. CoRR, abs/2010.04558 2020.
Grohe, M. and Otto, M. Pebble games and línear equations. The Journal of Symbolic Logic, 80(3):797-844, 2015.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016
Bai, L., Ren, P., and Hancock, E. R. A hypergraph kernel from isomorphism tests. In 2014 22nd International Con- ference on Pattern Recognition, pp. 3880-388 3885. IEEE, 2014.
Huang, J. and Yang, J. Unignn: a unified framework for graph and hypergraph neural networks. IJCAI, pp. 2563 6569. ijeai.org, 2021.
Bodnar, C., Frasca, F., Wang, Y., Otter, N., Montufar, G. F,, Lio, P., and Bronstein, M. Weisfeiler and lchman go topological: Message passing simplicial networks. In International Conference Machine Learning, pp. 1026- 1037. PMLR, 2021.
Immerman, N. and Lander, E. Describing graphs: A first- order approach to graph canonization. Springer, 1990.
Kipf, T. N. and Welling, M. Semi-supervised classi- fication with graph convolutional networks. CoRR, abs/1609.02900 00900007 2016. URL http:://axiv...o abs Abs/1609.00 02907.
Böker, J. Color refinement, homomorphisms, and hyper- graphs. In International Workshop Graph-Theoreih Concepts in Computer Science, pp. 338-350, Springer, 2019.
Li, P., He, N., and Milenkovic, O. Quadratic decomposable submodular function minimization: Theory and practice. Journal of Machine Learning Research, 21(106):1-44 2020.
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via sub- graph isomorphism counting. IEEE Transactions on Pat-
10

---

Improved Expressivity of Hypergraph Neural Networks through High- High--Dimensionl Generalized Weisfeller-Leman Algorithms
Lotito, Q. F., Musciotto, F., Montresor, A., and Battiston, F. Higher-order motif analysis in hypergraphs. Communica- tions Physics, 5(1):79, 2022.
Wachman, G. and Khardon, R. Learning from interpreta- tions: rooted kernel for ordered hypergraphs. In Pro- ceedings of the 24th international conference on Machine learning. Pp. 943-950, 2007.
Luo, Y. Shine:
Subhypergraph inductive neural network. Advances in Neural Information Processing Systems, 35: 18779-18792, 2022.
Wang, P., Yang, S., Liu, Y., Wang, Z.,, and Li, P. Equivariant hypergraph diffusion neural operators. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenRe- view.net, 2023. URL https: /ttec///ppeeeeee opprreview.eeeeeeeeoeeeee net/ forum iiddid-iii j.jssnNd.
Luo, Z., Mao, J., Tenenbaum, B., and Kaclbling, L. P. On the expressiveness and generalization of hypergraph neural networks. arXiv preprint arXiv:2303.05440, 2023.
Maron, H., Ben- Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Weisfeiler, B.
and Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 209):12-16, 1968.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Wu, H., Yan, Y., and Ng. M. K.-P. Hypergraph collabora- tive network on vertices and hyperedges. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 45 (3):3245-3258 2022.
Xiao, L., Wang. J., Kassani, P. H., Zhang, Y., Bai, Y., Stephen, J. M., Wilson, T. W., Calhoun, V. D., and Wang, Y.P. Multi-hypergraph learning- based brain functional connectivity analysis in fimri data. IEEE transactions on medical imaging, 39(5): -7711718677711 2019.
Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and leman go machine learning: The story so far. The Jour- nal of Machine Learning Research, 24(1):15865-15925 2023.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018
Papp. P. A. and Wattenhofer, R. A theoretical comparison of graph neural network extensions. In International Con- ference on Machine Learning, pp. 2022.
PMLR,
Yadati, N., Nimishakavi, M., Yadav, P., Nitin, V., Louis, A., and Talukdar, P. Hypergen: new method for training graph convolutional networks on hypergraphs. Advances in neural information processing systems, 32, 2019.
Papp. P. A., Martinkus, K., Faber, L., and Wattenhofer, R. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Informa- tion Processing Systems, 34:21997-22009, 2021.
Yang, C., Wang, R., Yao, S., and Abdelzaher, Semi- supervised hypergraph node classification on hypergraph line expansion. In Proceedings of the 31st ACM Interna- tional Conference on Information & Knowledge Manage- ment, pp.
Qian, C., Rattan, G., Geerts, F., Niepert, M., and Morris, C. Ordered subgraph aggregation networks. Advances in Neural Information Processing Systems, 35:21030~ 21045, 2022.
2022.
Yang, D., Qu, B., Yang. J., and Cudre-Mauroux, P. Revis- iting user mobility and social relationships in Ibsns: hypergraph embedding approach. In The world wide web conference, pp. 2147-2157, 2019.
Sanchez-Gorostiag A., Bajić, D., Osboree, M. L., Poyatos, J. F., and Sanchez, A. High-order interactions distort the functional landscape of microbial consortia. PLoS Biology, 17(12)::3000550, 2019.
Yoon, S.-e., Song, H., Shin, K., and Yi, Y. How much and when do we need higher-order information in hyper- graphs? case study on hyperedge prediction. In Pro- ceedings of The Web Conference 2020, pp. 2627-2633, 2020.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp. 333-341. SIAM, 2021.
Zhang, B., Feng, G., Du, Y., He, D., and Wang, L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Con- ference on Machine Learning, pp. 41019-41077 PMLR, 2023a.
Vignac, C., Loukas, A., and Frossard, P. Building power- ful and equivariant graph neural networks with structural message- paassgg-paasing.... Advances in neural information pro- cessing systems,
2020.

---

Improved Expressivity of Hypergraph Neural Networks through Highh-Dieensionll Generalized Weiseeller-Leman Algorithms
Zhang, B., Luo, S., Wang, L.., and He, D. Rethinking the expressive power of gnns via graph biconnectivity, arXiv preprint arXiv:2301.09505 2023b.
Zhang, M. and Li, P. Nested graph neural networks. Ad- vances in Neural Information Processing Systems, 34: 15734-15747, 2021.
Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars to subgraphs: Uplifting any gnn with local structure aware- ness. arXiv preprint arXiv:21 10.03753, 2021.
Zhou, C., Wang, X., and Zhang, M. From relational pool- ing to subgraph gnns: universal framework for more expressive graph neural networks. In International Con- ference on Machine Learning, pp. 42742-42768. PMLR, 2023.
Zhou, D., Huang, J., and Schölkopf, B. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19, 2006.
12

---

Improved Expressivity of Hypergraph Neural Networks through Higg-Dimennional Generalized Weisfeller-Leman Algorithms
A. Proof
For two isomorphism algorithms A and B, we denote their respective final colors of hypergraph HG as ca(H)) and cn (HG). We say:
A is more powerful than B (B A) if for any pair of hypergraphs H91 and H92, Ca (HGI) ca cA(H2) = (B(H cB(H22). Otherwise, there exists a pair of hypergraphs that B can distinguish while A cannot, denoted as B Σ A.
A is as powerful as B (A B) AMA
A is strictly more powerful than B (B x Bf 3 AAA A # B. For example, for any pair of hypergraphs HG and HG2, CA 1H = (HH + cg (H = cB (HH))),, and there exists at least one pair of hypergraphs HG1 and HG2 such that c (HG1) = cв (H92), but CA (HH)) & cAHG))..
Theorem A.1. (Theorem 5.1 in the main text) Given a simple graph 9 = (V, let (tk and c(k.gwt) (s) be unique color labels that the k-WL and k-GWL assign the k-tuple s to, respectively. There exists a bijective function & that maps the color ((R,u))s)) from k-WL to k-tuple color ((t.gutt) (s) from k-GWL.
Proof. We only prove the oblivious variants on k-OWL and k-GOWL and the proofs for the folklore variants follow analogously.
Proof of injection: We first construct a function o= = () - got))))) and then prove it is a one-to-one mapping (i.e.. no two different sources mapped to the same target). Consider the color c(s, (s) of k-tuple at some iteration t obtained by the k- L.WL.ar algorithm (in Section 3). It is determined by the k-tuple s itself and its neighbors (more exactly, their colors at iteration - 1), which we call the stem k-tuple set {s} U (S, w) w E V(G), 1 S S kj. We model the mapping from ((k,wt) to its stem k-tuple set as an injective function f. In order to connect to k-GWL, we transform the stem k-tuple set into another set {s} U {(fs} U (s. w) w V(G))) 1 S S k). by including s and N(jr)) (s) into a hyperedge. The new set can then be regarded as the k-tuple and its hyperedge neighbors, which can determine the color C(t..gut) (s) of k- k-tuple s obtained by the k-GWL algorithm. We denote by the injectve function the mapping from the new set to ((K.owt) (s). Then the function ø : C(R,wl) (s) - C(R. (s) can be written as a composition function of g and f. 2o o f.
Next, prove Ve(k, ((t,)))) E C( ((l)) (s1)) = ((C(k, (S2)) ((k (s1) c(t, ($2). where C(R..u)) denotes all possible k-tuples' final colors obtained by W-W.. Assume for contradiction that there are two final colors ((k. ($1), C(R, ($2) such that ((t.))t(ss)) & CIR, (52) and ((C()..))
= ($2)). It should be noted that the injective function g is reversible, getting inversion function g- With gー the two same final colors can be transformed into the same set {s} U [({s} u (0, w) w E V(G))) | i j S kj. which further derives the same stem k-tuple set {s} U (8, w) E V(G), 1 S j S k). Similarly, we can apply the inverse function of f to get the same color of leads to a contradiction, is concluded that the a(k, ($1) and ((k,,))(5)) Since the assumption ($1) A ((k,or)) injection holds.
(52)).
Proof of surjection: Here we prove that the two algorithms yield the same number of unique k-tuple colors in every iteration. That is. there is no C(k.gwtt (s) in k-GWL that cannot be mapped from C(k, (s) in k- WL. For the first iteration t = 0, both two algorithms initialize k-tuple color with the isomorphism type. The isomorphism type of a subgraph is determined by two factors: vertex labels and the subgraph structure. Since the vertex labels processed by the two algorithms are consistent in the same graph G. we focus primarily on the structural difference of the subgraphs. Because of the devised sub-hy sub-hypergraph extraction method, it guaranteed that the subgraph and sub-hypergraph induced by the same set of vertices in k-tuple are the same. With the same vertex labels and subgraph structure, the two algorithms output the same k-tuple coloring.
For iteration t >>0 0, the color (() (s) of k-tuple in k-WI. is determined by the stem k-tuple set {s} U (s, w) w E V(G), 1 1 j < k). As shown in the proof of injection, the color (s) in k-GWL is also determined by an equivalent k-tuple set (s) U (((s) U (0, w) w ((G))) 11 و S kj. Thus, both the mapping of ((k,w))(()) (s) and C(k. (s) from the same k-tuple set are injective. Combining the injective property with that the initial colorings in iteration = 0 are the same, we have in iteration > 0, the number of unique colors in the colorings induced by both algorithms is also the same. Therefore, the surjection holds. Finally, since both surjection and injection hold, according to the definition of the bijection, Theorem 5.1 holds.
13

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensionl Generalized Weisfeller-Leman Algorithms
For the proofs in this section, arbitrary input hypergraphs H, G, we have f(H) =(G)) = g(F) g(G). Then - implies that f 9. When both f y and g f hold, there exists a bijective mapping between f and g.
the following notations. Given two functions f.g. we + y to denote that for
Theorem A.2. (Theorem 5.2 in the main text) vk 2 (k+1)-GOWL > k-GOWL.
Proof. k-GOWL uses the isomorphism type of k-tuple to initialize colors, as defined in Definition 4.1. We first prove that Vs E yk-1 4 (s) + of (8.++) by enumerating t. Here, 1 (s, HG) denotes the color of the k-tuple in hypergraph HG after applying (k+I)-GOWL for iterations.
1.
For t = O, the color is an isomorphism type. LH = (V1, H1 X1), HC2 = (V2, Hz, X2), 484 E V/++1 .s E EV
we have
(+ = (57)
(Vi1, 12 [A: + 1/, = -/ + - ( 1|, = X2,x² A
(Vii,.., in E 1k) E H + (8) ,..,,,
[. E H12)
(12)
(Vi [kt], 8/. s/, + = 2 ( [k) X1 x2x; A
(Vi1,.., E (s)....) E H + (s) ....,.))))) H²) 7
( = =0(55+1
Therefore, (s, HG) - (s.4411 Hg))
2. > 0,
In the k-GOWL algorithm, we get
(e) (HASH((C (t-1) ( (ns) ns E NG(e))
((s) (8, w) ( ( V(HG) * BB1) ((bl))**+BB))))
(c)) (HASH (c)), fc (ns) ns E Ns(c'), Ekpo
(13)
I ([( (0,(S.+1,,w) ((H9)))) |1sjs k, S E V(H9)* BB))
(e')
In the above, e' is from &so which consists of only the first k tuples of (k+1))tuples in E Furthermore, we have
(s) = (IASH((C(())) (s), ( (ne) ne E Nc)
(0) w E V(HG))) [isiskti, SE BB))
(8 (HASH(ICk (t-( (s. ( (nc) ne E Nooo Ex.o
(14)
V(HG)))) | 15 k, 8 E V(Hg)* HD))
C (s,x+1)
Since (1) (((s)>+c) ckk (s.A+1) holds for any iteration in k-GOWL, it follows that (k+1)-GOWLZ Z k-GOWL.
It remains to prove that (k+1)-GOWL. # k-GOWI, i.e., there exists pair of hypergraphs such that (k+1)-GOWL can distinguish while k-GOWL cannot. It is well-known that there exists a pair of graphs such that (k+1)-WL can distinguish while k-WL. cannot (Cai et al., 1992). Since graphs are a special case of hypergraphs and k-GWL degenerates to k-WL for these inputs, we can re-use those (hyper-)graphs as the hard instances for k-GOWL which can still be distinguished by (k+1)-GOWL, completing the proof.
14

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized Weisfeller-Leman Algorithms
Theorem A.3. (Theorem 5.3 in the main text) vk 2 (k+1)-GFWL k-GFWI.
Proof. k-GFWL uses the isomorphism type of k-tuple to initialize colors, as defined in Definition 4.1. We first prove that Vs E wk- 1 cf (8.++)) by enumerating t. Here, 141 (s, HG) denotes the color of the k-tuple in hypergraph HG after applying (k+1)-GFWL for iterations.
1. Fort = 0, the color is an isomorphism type. We can re-use Step in the proof of Theorem 5.2 to prove c+1 (s, Hg) + & (s HG), since k-GFWL and k-GOWL, share the same initialization procedure.
2. Vt > 0,
In the k-GFWI. algorithm, we get
(1) (e) = ( ( (ns) ns E Ve(e),Ex11,
((s, 01 (s. w), 02 w), "... W V(H)), V(HG) (1))
( 6 (e') (HASH((C) (1- ((" 12 (ns) ns E No(e'), Ek,
(15)
{ (s.+11, 01 (8 w), Oz (2.4411,, w), (s((5s11 w V(HG), s V(HG)* (1)) +
(c')
(1)
In the above, e' is from E which consists of only the first k tuples of (k+1) Ik+ules in Ex-1, Furthermore, we have
(1) (s) (HASH((CET))) (t-1) (s), CC (ne) ne E NNo(s), Ex+I,
((s (s, w), 02 (2, w), ... (5. w)) w V(H9), E V(Hg)**1 4 (s (c (ne) ne No(s Ek.
(16)
I (s.641, O1 (8.+11, w), (s,,,,1,, ...... (s.+1, V(HG), sa+1 V(Hg)*
(s.+11)
Since (2) ( + Ck (s.x+) holds for any iteration in k-GFWL, it follows that (k+1)-GFWL ł-- k-GFWL.
It remains to prove that (K+1)-GFWL 2 k-GFWL. We can apply the similar proof idea in Theorem 5.2 to get hard instances for k-GFWL which can be distinguished by (KFI), completing the proof.
We first present the following lemma that will be used in the proof of Theorem 5.4 and the lemma will be proved shortly.
Lemma A.4. Let 2 For all hypergraphs Hg, HG', all v, E V(Hg) k+1 and all iterations t 2 (t) co.41(()
(0) (V)) is equivalent to that TSOx+1(v) = (S00+1(v')) and (0.())) c72 (0.(v))) )) all 1 S i sisktl (..+1(V))
Theorem A.S. (Theorem 5.4 in the main text) vk 2 2, (k+1)-GOWL & k-GFWL.
(t) Proof. Let c and co be the coloring of k-GFWL and k-GOWL in the tt iteration, respectively. We prove that for all (t)
(t)
hypergraphs HG, HG' and all iterations 2 0, (1) if HG, HG' are distinguished by Cf,e- they are distinguished by c (I+1)
(t)
and (2) HGG HG' are distinguished by (1) co they are distinguished by cf
To prove (1), suppose HG, HG' are not distinguished by (0) co.41 Then there is bijection f: V(Hg)*+1 V(H
such that (t) (v) (1)
(ott1((()) for all ((Hg))++1
15

---

Improved Expressivity of Hypergraph Neural Networks through High- Bigh--Dinnsional Generalized Weisfeiler-Leman Algorithms
For (u1: "....... ,..), let 4t (u1, ug, ukk ug)) and u'a (ui, ub,,........ ... u/. (e+1) = M(4)). According to (8)
Co,t1(u', and Lemma A.4, we get ISOx+1 (u+) ISO (w',) and thus u/441 = 1//- Let mapping g(u) = (u/, "i2...,,,, = -u. Then is a bijection from V(HL))* to V(Hg")*. Since u = 0x+1(u,,) and
0, (u+) = (1)
n' n'= ( we have (1)
(u(_) by applying Lemma A.4 in the position k + 1. Then g is a bijection that preserves the coloring off and thus Gj cannot distinguish HG, HG'.
I.A. (1+)= (
To prove (2), suppose HG. HG" are not distinguished by o//"". Then there is a bijection g: V(HG)* + V(Hg") =Gi,k ((**"(((())
such that ((+1))() (u) = Gj (g(u)) for all u E v(Hg)*. Let u' = g(u). By the definition of (1+1) in k-GFWL, f..
f.k
we have 6/ (u) = (ff(()) and there is a bijection h : V(HG) + V(Hg') such that for all w E V(HG), we have IS0x+1(uu) (uw) = +IS0++((nh((w)) and (t) (,,,( = o/2 (0, h(w)) for all 1 S < k. This implies I.A (0,(w)) )) = of (0,( )) for all I i I k. It is clearly true that F.e (0x+ (ww, )) = -f (0x (u'h(w))), )). Then by Lemma A.4, we get that (0) (uw)) = 0o (u'h(w)) We can then define a bijection f: V(Hg) k+1 + )(Hg')** j++1 such that f(uw)= = g())h(w) for all u E v(Hg)* and all w E V(Hg). f preserves the coloring 0, and thus C cannot distinguish HG, HG'
We require k 2 2 to ensure that the isomorphism type function ISO0 is activated in k-GFWL, since it has certain distinguishing capability as shown in Figure 3(a). We now prove Lemma A.4.
Proof. (Proof of Lemma A.4) We prove the equivalence by induction on iteration t. The base case t = 0 is trivial. For the inductive step t t + 1, to prove the forward direction, we suppose that [1+1) (t+1)
c, (v) (1+1) (v'). By the definition of
co,+11 we get / 1S00+110 (v) = 1S0x+1(v")) (v'). For S i k 1, it remains to prove J, ((tt)) (0.(v)) )) = J.. cfttt) (0:(v',, .).. By the definition of Co,t+1, we have if (c w)) w E V(HG) = ( (0,(V', w/ E V(HG') Then there is a bijection h: : V(HG) + V(HG') such that 2 (O,(v, w)) = c (0:(v', ((w))) for all w E V(HG).
According to the inductive hypothesis, we have that 100 w)) T.
(t) IS0 h(w))) and (6) (O,((, = (0) (,,00, h(w))))) )(x))) for all 1 S j S k + 1. When j = i, this implies of (0.(v)) =
f. (O,(()) And for all 1 S j S h. we have (0) (0) (V. = (2) (.) By the definition of ((+1)
(e+1) k-GFWL, it follows that Gf.k (0. )) Cfk (O:(v (0:(v')))
For the backward direction, we suppose that (S) = ISOx+1(v') and (++1) (0.vv)) = ((+1) (0.(v()))))) .)) for all of.
=cfk
1 i k + 1. Since ff
(++1) + cj by the inductive hypothesis, it follows that co (v) = c. (v'). By definition of
(8)
a.k+1: prove c.k+i (v)
(t+1)
(t+1)
'o,k+((')) (v'), need to prove that (c.2+1 w)) w E V(H)) = 11 ( (0,(v', w())
(t+1)
w/ E V(HG") for all < i S 1.
Consider only an for Sig S le 1. Because Cjk
(1+1) (0,(v.)) = - f.k
(++1) (0+1)((((')) )), there a bijection h V(Hg) + V(Hg') = IS0x+1 ,)((w) and
such that for all w E V(HG), we have (0,
w)) = for all S j S k. This implies that TSO (v,,)) = 150 (0. h(w))) and F. (0, (O,(v w)))) = (0) (O,, (v)))) for all 1 < < k + Then by the inductive hypothesis, we get that coht1 (0, = 2 (0.(V', ((())). Since h is a bijection, it holds that g ( (0.(v, w)) | w E V(HG) = (0,(V, w')) w' E V(HG") B. completing the proof.
(t)
Theorem A.6. (Theorem 6.1 in the main text) Given hypergraph HG = EV and let k 2 2. Then for all iterations (0)
(0) t 12 O, for initial features 12 consistent with the initial colorings C of k-GL and for all weights W(t)
( C
C
x (t)
(17)
Proof. We prove for an arbitrary iteration t and k-tuples
s, s' E V(HG)*, that (e) = Cx (s') implies x.( = =xx In
(0)
(t)
fact, we can also prove for hyperedges e and e' in H9r, o (e) = ( (e') implies (0 = x (t) In iteration = 0. we
(1)
16

---

Improved Expressivity of Hypergraph Neural Networks through Iligh-Dimensional Generalized Weisfeller-Leman Algorithms
< (s) = = (s') = zi = =xy" since the initial features x are chosen consistent with the initial colorings (0) of k-GWL. Similarly, (0) (0) uniform.
have
Ck (e) c (c') Ta ze' because the initial hyperedge coloring and feature vectors set be
(0) (0)
Let k-tuple s, E V(Hg)* and > 0 such that
CK
e (s) =cx (5'). Suppose for the induction that Ck (1-1)) (s) ch
(s''
ds (t-1)
(t-1) hold. As 6/ (s) C (s'), we know from the (s') of s and s' as well as hyperedge color multisets lo (e) e E [ and (e) E Ma(s') of the hyperedge neighbors of s and s' are identical. The latter, according to the refinement step, implies that the multisets P. ffck -
Fs ()-1) and C ( (c) & (c') 7 3e
(t-1) Fee
k-GWL refinement step that the old colors Ck (s) Ck
(0, w)) 1 S j S k, w V(G) and P== to (t-1) (0,(s w)) 1 و S k; V are identical (together with that the colors of the hyperedges at iteration t 1. 1 (e) e E (s) and Ho (o) e E NNcss') } are the same).
Let Qs - 1 S S w, E V(H9)) and Qs of (w'.w) l S S k V(HG)) be the multisets of feature vectors (corresponding to Ps and Pa with colors replaced by feature vectors). By the inductive hypothesis, we
know that (6-1) 2x ((-1) Qs Qs' and (z--") |c E Ns)ss] !-!-"> |c Ns)ss))) The latter two imply that
txe le E (o)(s) = [ue E No Then, regardless of the choice of the aggregation and updating functions in
k-HNNs, we get xs (t) (e)
zs' since the input of the functions the same. This proves o (s) = c (1) (s') = Is Iz and
(t) (t)
thus Ck
Cra (t)
Theorem A.7. (Theorem 6.2 in the main text) Let A: Hg - Rd be a k-HNN based on k-tuple neighborhood. With sufficiens number of layers, for any pair of hypergraphs that k-GWI. determines as non-isomorphic, A also determines them as com-isooorppic (1) the aggregation and update functions in the base HNN of A are injective, and (2) A's hypergraph embedding readout function injective.
Proof. Let HG, HG' be any pair of hypergraphs that k-GWI. determines non-isomorphic at iteration K. Since A's hypergraph embedding readout function is injective, it suffices to prove that A's two-stage neighborhood aggregation process, with sufficient iterations, embeds Hg and HG' into different multisets of k-tuple embeddings. Suppose A updates k-tuple representations as follows:
2 [ (= f'((l=!"'") | (G()))
x = g( ah 11-1) 11, f(f Nc)))))
where g.g and f.f f' functions injective. The k-GWL applies an injective hash function h to update the k-GWL k-tuple labels:
e (e) = N' ('(a(t (-) |s scN(())))) (s) = (((d le (e) ee e
We will prove, by induction, that for any iteration t, there always exists an injective function a such that
r a(c (t) (s)).
(18)
In addition, we prove that for any iteration i, there always exists an injective function o' such that
o'(e =
(t) (e)).
(19)
For the base case t = 0, Eq. (18) trivially holds since the initial features are set based on the isomorphism type using Eq. (9) which is an injective function. Eq. (19) also holds since the initial hyperedge features in k-HNN are the same as the hyperedge labels in k-GWL. Suppose that Eq. (18) and (19) hold for iteration t 1, we show they also hold for t. With substitutions, the updating of hyperedge representations becomes
17

---

Improved Expressivity of Hypergraph Neural Networks through High-Dimenniioal Generalizeed Weisfeller-Leman Algorithms
_!-² c'o (e)), M([a(c (s)
Since the composition of injective functions is injective, there exists some injective function e such that
1 --( 11 (s) (e)))
We further get that
2!! ('(2-11)0 (e), lo (s) s S
V (N) - (((0 (o). l4 (s) s sE (.(c)))
w (h1)) -1-) ( (e).
Then there exists injective function =' =b¹ (h')- such that xe d'(c (e)). We can then apply similar trick in the updating of k-tuple representations:
"!" gl (s)), ((L (e) Nc()))))
Because the composition of injective functions injective, there exists some injective function vi such that
xr(h)) = (cch (s), (c (c) (cE)s))
= h- l(ck (s),
(s), lo (e) e e No(s))
w h- (s).
Hence, there exists an injective function s / such that x= determines Hg, Hg' as non-isomorphic with different k-tuple labels (/2 (K) (s) B. k-HNN must also have different features
o(c (s)). Therefore, at iteration K, when k-GWL
{ } (c
(s)))) } and decide them as non-isomo.phic.
(K) (s))
18

---

Improved Expressivity of Hypergraph Neural Networks through Iligh-Dimensional Generalized WeiseellerLLeman Algorithms
B. The high-dimensional Weisfeiler-Lehmall test of hypergraph isomorphism algorithm
Algorithm The high-dinensional Weisfeiler-Lehman test of hypergraph isomorphism algorithm
Input: Hypergraphs HG and HG', int k: dimensionailly,, ISO(-): isomorphism intial function, su (s): sub-hypergraph induced by k-tuple from MG, k-tuples hypergraph k9 int h: maximum number of iterations
// 1. Initialize k-tuple s' colors in V(Hg)*.
9 (s) (H (s)), E V(HG)*
(0) (s') - (so E V(Hg))
2. Initialize hyperedge s' color in hypergraph HGg for k-tuples.
9 (c) E.CEE(19))
Ch (e') + 0,e' E(H(g())
++0
while < h and Kcck
( (s) s E V(H = lo (s') Is' V(Hg"** B do
1 ++1
// Gathering hyperedges' k-tuple neighbors color hyperedges. for e/e' EEHG)) x)) do
C (c) + HASH ((o (c) (c). lo (u)
(u) u (c(o))))
Ck
(0) (c') HASH 1-1)) (c'), [qk (m)
(u) u u AG((')
end for
I| 4. Gathering k-tuples' hyperedge neighbors color k-tuples.
for s/s' E V(HG)* (HH')* do
4 (s) + HASH( ((-)) (s). [o (u) (G(s)))
(s') - HASH((Q (s)),
(s'), lo (u) e (s)))
(0
end for end while
Comparing (ot (9 (s) s E v(Hg)* } and (s))(s)) ss E "
(s')
Ensure: Whether Hg and HG' are isomorphic or not.
19

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized Weisfeller-Leman Algorithms
C. Sub-Hypergraph Extractions
We reveal that induced sub-hypergraphs, while appearing straightforward, require careful consideration. Recently there growing interest in learning good representation for sub-hypergraphs in hypergraphs, e-g.. SHINE (Luo, 2022) in bioinformatic applications. Here we propose sub-hypergraph extraction trick and discuss the differences between uub-hypergraphs and traditional subgraphs.
First, let us review the method for extracting subgraphs based on given vertices in simple graph. Given graph G A) with vertex features X E 1 and adjacency matrix A E {0, || Given a set of vertices = {vi,... vi), our purpose is to extract subgraph ( Asub) based on vertices s from G. It is easy to obtain sub E R|+|x by selecting the vertex features from s. The edge relationships among the vertex set can be obtained by retaining only the relevant rows and columns of the adjacency matrix A, resulting in Asub {0, 1) |s|
Then, in the hypergraph HX H) with vertex features X R F and incidence matrix H E {0. 1] the features of the sub sub-hypergraph's 's vertices Xsub E RisixF can be obtained by selecting the features corresponding to the vertex set The main issue lies in how we derive the sub-hypergraph's 's incidence matrix Hub. One could simply retain the relevant rows in the incidence matrix H and delete columns/hyperedges that contain no vertex in S, referred to as H'. But we propose two (cquivalent) rules to prune H':
1. If hyperedge in the nub-hypergraph H' contains at least two vertices from the vertex set in its original hyperedge, then the hyperedge is retained. (In other words, columns with at least two non-zero entries are kept in H'))
2. If hyperedge only contains a single vertex, called a singleton hyperedge, then the hyperedge is deleted from H'. (In other words, columns with only one non-zero entry pruned from H')
Therefore, we obtain Heab E {0, 1111ر by retaining the relevant rows in the incidence matrix and delete colunns/hyperedges that contain no vertex or only one vertex in s, where [U] is the number of hyperedges that con- tain at least two vertices from the set
The first rule is well-motivated in practice and easy to explain. For instance, in citation datasets, hyperedges represent papers and co-authors are the vertices within the hyperedges. When we remove some co-authors from a paper/hyperedge, the co-author relationship among the remaining authors is still maintained.
The second rule essentially ensures that the sub-hypergraph and the subgraph induced by the same set of vertices in an equivalent hypergraph/graph are the same. See the illustrative example in Figure 1. fact, when there a single vertex in hyperedge, the hyperedge information can be either deleted or transformed into an additional vertex feature. We turn to the former, which facilitates the theoretical proof of the relation between k-GWL and k-WL. Additionally, from the experimental results shown in Table 2, we find that deleting singleton hyperedges significantly enhances the hypergraph classification performance compared to retaining them. We believe that our finding on sub-hy uur-hypergraph extractions can be of independent interest.
20

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized Weiseeller-Leman Algorithms
D. Illustrative Examples for Hypergraph Isomorphism Test
For the examples in this section, we only consider k-sets for clarity. The omitted ordering (e.g.. (V), 02) vs. (02, b1)) and vertex repetitions (e.g.. (v), 21 do not affect the correctness. Symmetric 2-tuples have the same features since they have the same induced sub-hypergraph. 2-tuples with vertex repetitions have an induced sub-hypergraph as the vertex itself since singleton hyperedges removed.
D.I. An Example Distinguishable During the Initialization of 2-GWL
(o)
Input
(b)
Initial part
Statistics results
v1
(v1,2)
(3):
(v3,v5):
v6
V2
(v1,v3):
(v2 w4):
(v3,66)
Hosh Map
9
9:1
g
g
(v1,x4)
9
(v2
(x4.5))
:2
c4
2
(v1,55:
1
2
(v2,v6):
(v4.6):
v5
3
2-GWL Process
(v1,66):
(v3,44)
(v5.6))
Success
V2
(v1,2):
(v2,
(v3,v5):
V3
(v1,v3):
(v2,v4):
(v3,v6):
:4
0:1
g'
g
(v1,44
(v2,
(v4,v5):
:4
8
v6
(v1,v5)
(v2,v6):
(v4,v6):
(v1,v6):
(v3,4))
(v5,v6):
(c)
Initial part
Vertex Hyperedge
Hyperedge Vertex
Statistics results
v1:
[3]]
v1:
v2:
v2:00
et: 2.
et:
v3:
[3. 4]
v3
22:
1,
c2:
v4:
[3]
9
0
@ :4
V4:
e3:
e3:
Hash Map
v5:
[3, 4]
Hash Map
V5
e4:
1-GWL
V6
[3]
v6:
Process
[3. 4]
Foil
vt:
[3]
v2:
e1: 2.
et:
v2:
v2:
[3. 4]
v2:
e2:
e2: 4
V3
[3, 4]
gr
e3: 2.
e3:
0
:4
v4:
[3]
e4: 1.
e4:
v5i
[3, 4]
v5:
v6:
v6:
[3. 4]
v6:
Figure An illustrative example where 2-GWL can distinguish and 1-GWL cannot distinguish. Node labels are in circles and edge labels are of red color.
In part (a), two non-isomorphic hypergraphs, G and G', are presented. Part (b) illustrates the initialization process of 2-GWL, where 2-GWL successfully identifies distinct subgraphs in G and G'. For example, the subgraph type generated by (0s, Ub) in G' is unique and does not match any subgraph type in G, allowing us to conclude that they are non-isomorphic.
In contrast, part (c) shows that 1-GWL is unable to distinguish between the two hypergraphs. After each round of 1-GWLI, the color mapping remains the same. Thus, 1 I-GWL fails to distinguish between these two non-isomorphic hypergraphs. Therefore, the expressive power of 2-GWL is indeed stronger than that of I-GWL.
21

---

Improved Expressivity of Hypergraph Neural Networks through Iligh-Dimensional Generalized Weisfeller-Leman Algorithms
D.2. A Harder Example Not Distinguishable During the Initialization of 2-GWL
We have presented an example where non-isomorphic hypergraphs can be distinguished during the initialization phase of 2-GWL in Figure 5. To further validate the expressive power of the k-GWL algorithm, provide more challenging example of non-isomorphic hypergraphs that camnot be distinguished during the initialization phase of 2-GWL. Below, present the details of applying I-GWL, 2-GOWI, and 2-GFWL in the hypergraphs.
Input
Iriticl part
Vertax - Hyparedge
Hypenedige - Vertex
Statistics results
vt:
vt
[3]
v1:
v2:
[3.
V2:
et:
e1:
[3, 4]
v3:
44
#2:
<2: 4
43
M5
V5
e3:
[3,
v5
0:2
:
v6
[3. 4]
V6:
Hosh Map
65:
[3, 4]
Hash Map
c6:
66:
v8:
[3)
Foil!
vt:
vk
[3]
[3.
v1:
M
[3.
v2:
62:1.10
22:
[3,
6:2
16
43:
4]
64: 4
[3,
v5
[3. 4]
v0:
o6:
66
[3,4]
v7
g
[3)
Figure 6. Illustration of I-GWL failing to distinguish two particular non-isomorphic hypergraphs. Node labels are in circles and edge labels are red color.
In Figure 6, we show that I-GWL is unable to distinguish the challenging example of non-isomorphic hypergraphs. Similarly to part (c) in Figure 5, after each round of 1 1-GWL, the types and quantities colors generated remain consistent with those from the previous round. Therefore, 1-GWL fails to distinguish these two -oomisomorppic hypergraphs.
In the following, show that 2-GFWL successfully distinguishes the non-isomorphic hypergraphs while 2-GOWL cannot distinguish. We start with the details of the initialization part of 2-GWL (shared by 2-GFWL and 2-GOWL), shown in Figure 7.
We observe that cardinalities of the 2-tupe colors in the two hypergraphs keep the same, although the colors for (Us, va), Us), (v4, v8) and (us, v6) are different. This indicates that neither 2-GFWL nor 2-GOWL can distinguish these two non-isomorphic hypergraphs during the initialization phase.
In the next step, our 2-GOWL and 2-GFWL algorithms construct hyperedges for each initialized 2-tuple to connect with its corresponding 2-tuple hypergraph neighbors. For brevity, we only consider the 2-tuples (va, v4) and (va, us) and construct their 2-tuple hypergraph neighbors. The 2-tuple hypergraphs and their isomorphism test processes are shown in Figure 8 and Figure 9, respectively.
In Figure& 8, we use the hyperedge construction formula of k-GOWI. mentioned in Section 4. 1.2 as follows:
E = |l (0,
V(H9))) | < k, e V(H))*
can be deemed as replacing a specific vertex in the k-tuple with all vertices from the original vertex set to form a k-tuple neighbor, and then all these k-tuple neighbors are connected to form a hyperedge. Specifically, for the 2-tuple (Fa, vg), we observe that by replacing e3 in (V3, v4) with U1, U2, Vs. Ug. V7, and Us. we obtain six 2-tuple neighbors. These six neighbors
22

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized Weisfeller-Leman Algorithms
Irpul
part
(v1,22)
(v2.88)
(v3,44
(+9,5)
(+5,v))
[vl,22
(v2,x0)
(+4,40)
(v5.v6)
(41x3)
(22
(+3,5)
(v4,66)
(v5,47)
(Н1,3)
(v2,-4)
(V3.5)
(H9,66)
(+5,47)
(22
(v3
(+4,7))
(v5,v))
(v1,44
(v2,45)
(v3.v63:
(+4,77)
(+5,w0)
(v2,663
(v4.60)
(vL,55
(v2,v63
(+9,8))
v6
(41,6)
(72,77
(V3
(v1.6)
(x2,77)
(v1,7)
(v2,88)
(v6,17)
(v7,v6)
(7L,77
(v2,v0):
(v6,77)
(97.v0)
(v1,0)
(66,48)
(vL.88
(vl,22
(v2,v3y
(v3:44)
(v4,5)):
(-5
M3
(vE.v)
(22,4)
(+3,5)
(v1,66)
(15w7)
(vlx22
(vl,88g
(+2,44)
(v2,x3)
(v3,v4g
(+4,5)
(H1,x6)
(-5,77)
(-5,v6)
(x2,553
(x3.v6)
(+4,77)
(+5,88
(vl,44
(v2.6)
(v3
(-9,47):
(-5,v8)
(vL,55+
(+2
(v3,77)
(+4,6))
V7
(vl.v53
(vl:77
(v2,77)
(v2,v8)
(v3,v8)
(v6,7)
(V7,8)
(v1.66
(v2,v63
(v2.77)
(V3,77 (77
(v3
(+9,v83
(vl.77
(v2.v6):
(+6.77)
(v7,v0)
(vi.88
(66,8)
(v1.88
(v6,v8)
Figure 7. The initialization phase of the 2-GWL cannot distinguish the non-isomorphic hypergraphs as well.
are connected to (13, U4) by the hyperedge e1, forming parts of the 2-tuple hypergraph. The construction process for (v3, Us) follows similarly.
Next, we perform the 1-GWL. color relabeling on the constructed 2-tuple hypergraph. As result, we obtain that in G, 2-tuple (Us, 04) is assigned color "9' and (V3, 0s) is assigned color '10'. In G', 2-tuple (V3, 04) is assigned color '10' and (va, us) is assigned color '9', The cardinalities of colors for these two 2-tuples remain consistent with the input. Therefore, 2-GOWL unable to distinguish these two non-isomorphic hypergraphs.
In Figure 9, k-GFWL constructs the of hyperedges as follows:
E = (s, 0 (s, w), (2 w), 00(ss, w)) | V(H9), s V(Hg)*}
can considered as replacing every vertex the k-tuple with specific vertex from the original vertex set to form k-tuple neighbor, and then all these k-tuple neighbors are connected form hyperedge. Specifically, for the 2-tuple (va, 04), replace both ey and v4 with vi, resulting in the 2-tuple neighbors (V1, and (v1, These two neighbors, along with (Vy, va). connected by the hyperedge 61. The construction process for (V3, Us) is similar.
Finally, we perform the 1-GWL coloring on the constructed 2-tuple hypergraph. The results are that in G, (03, v4) is assigned color '9' and (W3, 0t)) assigned color '10'. In G', (V3, vg) is assigned color '11' and (V', 03) is assigned color '12'. Since the 2-tuple colors in the two non-isomorphic hypergraphs differ, the 2-GFWL algorithm successfully distinguishes between the two hypergraphs.
23

---

Improved Expressivity of Hypergraph Neural Networks through High- High--Dimensionl Generalized Weisfeller-Leman Algorithms
2-50WLL
Vertex Hyperedge
Hyperadge Vertex
(/2.0
(v3,44)
(v4,5)
(+4.5]0
(44,7
(+4,8)
(4.50)
(-3,4))
[2.
(x8,44
:1
Hash
9
68.8
(x3v5)
Hosh Map
(x3,45)
10
6.12
3]
(V.
Kvlx8)
12. 3]
Kvd.33)
<l.
(3394)
[+4,5)
(44.5)
(4477
[vd.5
62:
(v3,4)
(v3,-1):
g'
1
(+1,8)
(00x0)
@111
(22.5
(4.56
Vv.33
21:1
et:
(v3,v5):
[2, 3]
(x3w5):
(+x66)
65-77
(5.5)
04.55
68
2x33
Figure 8. Illustration of 2-GOWL failing to distinguish non-isomorphic hypergraphs.
Statistice
Wil 1.f
c 2
(+3,4)
43.4
(r3w4)
March Mrp
6:94))
46:8
Secoees
42:3
10 43
0'
11, 51
(43,4)
6030x::
11 0
11, 6)
di1eh
65.7
Figure 9. Illustration of 2-GFWL successfuly distinguishing nommosomoi hy hypergraphs.
24

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized Weisfeller-Leman Algorithms
E. Experiment Details
E.1. Experimental Setups
Datasets: the experiments, we adopt three types of real-world hypergraph classification datasets proposed in HIC [14], which are IMDB, Steam-Player, and Twitter-Friend. In the IMDB datasets, two correlations co-director used for high-order dataset construction. In the dataset name, "Dir" and "Wri" indicate hypergraphs constructed from the co-director and co-writer relationships, respectively. The staff (director/writer) of each movie forms hypergraph. "Form" categorizes movies by type (e.g., animation, drama), while "Genre" classifies them by genre (e.g., adventure, crime). The Steam-Player dataset comprises games played by Steam users, represented as hypergraphs, where vertices represent games played, and hyperedges connect games with shared tags. The goal of the dataset to identify each user's preference: single-player or multi-player games. The Twitter-Frienn dataset a social media dataset where each hypergraph represents a user's friends. Hyperedges connect users who are friends. The label indicates whether the user posted about "National Dog Day" or "Respect Tyler Joseph". To assess the efficacy of capturing distinct correlation structures, all datasets exclude the original vertex features. Full dataset statisties in Table 5, where |u| and |e] represent the number of vertices and the number of hyperedges in a hypergraph, respectively. dy and de are the average degrees of vertices and hyperedges, respectively. In addition, we provide the information of k-tuple hypergraphs generated by the 2-GWI. algorithm, which are presented in Table and Table 7, respectively.
corvelaiios-ccoddieeeooo and co-writer- are
Table 5. Statistics of Input Hypergraph Datasets
DATASET
HYPERGRAPHS
# CLASSES
AVG./o|
AvG./el
MAX.(p/
MAX./e|
de
d,
IMDB-DIR-FORM
1869
15.7
39.2
264
450
3.7
IMDB-DIE DIR--GERRE
3393
3
17.3
36.4
264
450
3.8
5.9
IMDB-WER WRI-FORM
374
10.1
3.7
180
23
5.0
1.5
IMDB-WER -RR--RRIGE
1172
6
12.8
4.4
273
75
5.2
1.5
PLAYER
2048
13.8
46.4
140
4.5
14.9
FRIEND
1310
2
21.6
84.3
166
603
4.3
16.4
Table 6. Statistics of k- T-pue Hypergraphs by 2-GOWL
DATASET
AvG. m|
AvG./el d.
dv
IMDB-DIRS DIR-FORM
223.4
368.1
12.6
IMDB-DIR- DIRRGENRE
301.8
477.2
9.6
12.7
MDDBWRRI-FOO
117.6
44.5
6.4
3.6
MMDB-WRIGENNT
266.8
94.7
8.3
3.9
STEAM-PLAYER
96.8
21.7
12.6
2.9
TWITTER-FRIENT 345.2
611.5
13.7
21.2
Table 7. Statistics of k- k-Tuple Hypergraphs by 2-GFWL
DATASET
AVG. lo]
AvG.|e|
do
---DI--FORM
223.4
6773.3
2.5
14.2
IMDB-DE WADB-DI--GEET DIR-GENRE
301.8
9068.1
2.5
14.8
IMDB-W -RI-FORM
117.6
3435.15
2.6
7.7
266.8
10009.7
2.6
10.2
STEAM-PLAYER
96.8
511.0
3.0
12.0
TWITTER-FRIIHH 345.2
7684.9
2.5
22.1
Compared Methods: In k-HNN, the number of neighbors for each k-set grows exponentially with k, which is constrained by the GPU memory capacity. Therefore, we mainly focus on l: == 2 (except for 3-HNNs with vertex sampling). Due to the two different neighbor aggregation approaches, we obtain two variants of our models: k-FHNN and k-OHNN, Since our models are end-to-end trained HNNs with node features and hypergraph structure as input and final hypergraph features as output, we choose several representative hypergraph deep learning methods as baselines. These include: HyperGCN (Yadati et al., 2019), HNHN (Dong et al., 2020), UniGNNII (Huang & Yang. 2021), AllSerTransformer (Chien
25

---

Improved Expressivity of Hypergraph Neural Networks through High--Dimensionll Generalized Weisfeller-LLman Algorithms
et al., 2022), and ED-HNN (Wang et al., 2023). Furthermore, we adapt the 1-GWL kernel kernel method (Feng et al., 2024) to an end-to-end model, resulting in HIC as another baseline. To further emphasize the contribution of structural information to the learning process, we also include the 2-layer MLP of width 128 baseline model. Note that some of the above methods were originally proposed for node classification tasks. Therefore, we add the same readout module in their final step, where the embeddings of all nodes are summed to obtain the final hypergraph embedding used for classification.
Other Details: To evaluate the model's performance, we report the average classification accuracy over 5-fold cross- validation along with standard deviation. This metric intuitively measures the model's 's ability to distinguish different types of hypergraphs. We use the Adam optimizer with a learning rate of 0.001 and terminate the training if there is no improvement in the validation performance after 50 epochs. All experiments are conducted on server with an Intel E5-2650 CPU (2.20GHz), 256GB RAM, and an NVIDIA 1080Ti GPU (I1GB), except the experiment for 3-HNNs on GPU cluster consisting of 10 Sugon X640 G30 GPU servers. including 1 management node and 9 GPU compute nodes. Each node is equipped with dual Intel Xeon 6248R CPU, 512GB RAM, and 8 Nvidia Tesla A100 GPU(40GB).
E.2. Main Result
The experimental results for three types of real-world hypergraph datasets are presented in Table 1. Based on those results, we have four observations. First, our proposed two HNN models outperform other compared methods across all datasets. Notably, on the Steam- Player dataset, 2-FHNN outperforms the runner-up model, ArnSerTransoommr, by 6% in accuracy. This advantage stems from our model, guided by k-GWL, being able to better capture the high-order structures within hypergraph data. Second, we have run experiments on k-HNNs for k sample size 10 in GPU cluster with 40GB memory. Although not the full 3-HNNs without the sampling, 3-HNNs with the sampling have comparable performance to 2-HNNs across the datasets, while significantly outperforming in the HIDB-Wri-eent dataset. Third, in the LMDB-Wri-Form dataset, the structure-free MLP model achieves relatively high ranking, trailing our model by only 3% in accuracy. This indicates that leveraging high-order structural information in this dataset still has a large space for improvement. Fourth, although 2-FHNN is theoretically more advantageous than 2-OHNN, experimental results reveal mixed performance across datasets. For instance, 2-FHNN performs better on datasets such as MMDB-Dir-Form,
based on the vertex sampling strategy with
and Player,, while 2-OHNN outperforms on IMDB-Di- Genre, BMDB-Wri-Gentt and Twitter- Friend datasets. Therefore, in practical applications, it is essential to select the model that best suits the specific scenario.
E.3. Impact of Sub-hypergraph Extraction Methods
We here conduct comparative experiments for different aub-hypergraph extraction methods to show the proposed induced uub-hypergraph method not only supports the unification of graphs and hypergraphs, but also offers empirical advantages. We append "-S" to our model when keeping all hyperedges, including singleton hyperedges, in extracting sub-hypergraphs. Note that this only changes the initial features of k-sets, i.c., isomorphism types, due to a possibly different induced sub- sub-hypergraphe while the k-set hypergraph structure remains unchanged. The experimental results are presented in Table 2. We observe that when k-sets use sub-hypergraphs containing a large number of singleton hyperedges as the isomorphism type features, the model performs poorly across all datasets. However, when we remove singleton hyperedges from the sub-hypergraphs, the model achieves an average performance improvement of 5.4% across all datasets, with a maximum improvement of 14%. This highlights the indispensable role of our induced uub-hypergraph module and its significant impact on the empirical performance of k-HNN.
E.4. Influence of the Vertex Sampling Strategy
In k-GWL, the time complexity inevitably grows exponentially with the increase in k. To reduce the complexity of k-tuple hypergraph construction, we propose a vertex sampling strategy. Specifically, we sort the vertex set of each hypergraph dataset by degree and select the top m vertices with the highest degrees. These sampled vertices are then used to construct the k-tuple hypergraph and train the models, while the remaining vertices are ignored.
Considering the distribution of vertex numbers across the datasets, we set m to 5, 10, 15, and 20, resulting in four experimental groups. Additionally, we included fully sampled experiment (using all vertices) baseline for comparison. We conduct the same sampling experiments on both the 2-FHNN and 2-OHNN models. The experimental results for different models are shown in Table 3 and Table 6, respectively.
26

---

Improved Expressivity of Hypergraph Neural Networks through Iligh-Dimensional Generalized Weiseeller-Leman Algorithms
Table 3. 77.40 .44
Results on Sample Vertex Numbers (2-FHNN)
5
10
15
20
ALL
IMDB- PE83-DIR-FORRR FORM
66.45+0.98
65.9742.54
66.51
66.6742.83
68.11=2.46
IMDB-DIR-GENTT
76.24+0.98
77.49=1.23
77.0442.67
78.52:1.07
IMDB-W RI-FORM
52.22+3.99
52.78+4.39
48.61=5.20
51.1145.23
55.36+3.30
MMDB-WRIGENNE 47.9343.26
43.10+2.33
38.36#1.98
37.76+1.58
45.44=1.24
STEAM-PLAYE
61.8142.20
63.43=1.71
65.88+1.91
65.98+1.51
67.53#1.23
WUITER--FRIETE 1..15
61.08=1.23
62.85+2.14
62.31
62.75=2.18
Table Results on Sample Vertex Numbers (2-HHNN)
5
10
15
20
ALL
IMDB- BOOB--DR-FER DIR-FORM
66.45+1.31
66.72+1.50
67.10 147
67.15+1.27
67.25+2.35
IMDB- HIDB-DIR-GGE DEI--DDRREEE
76.39+1.85
75.68=1.45
17.49=1.43
15.1241.03
79.75+1.14
MMDB-WRI-FOE
49.4426.37
49.17+2.58
53.0645.08
51.9443.58
55.35+3.74
IMDB-V TEE---R--EERRR
47.50+3.17
42.93+2.54
36.90=3.50
18.19.1.80
50.08=1.89
STEAM-
STEAM-PLAYER PLAYER
60.88+1.25
62.94=1.01
65.05+0.69
64.75+1.77
65.97=1.37
WUITTER-FRIENT 61.54+1.95
61.92+2.81
62.08+1.16
62.85+2.59
64.12+1.30
Based on those results, we have three observations. First, for both the 2-FHNN and 2-OHNN models, the performance improves as the number of sampled vertices m increases, reaching its peak when all vertices are sampled. This trend is particularly pronounced in the Steam- Player dataset, where the performance difference between the case with 5 sampled vertices and the full sampling scenario as high as 6%. Second, in some datasets, such as MMDB-Wri-Fome and IMDB- Wri-Genre, the model performance initially decreases and then increases as the number of sampled vertices increases. This may be because, in these datasets, the key structural information is concentrated in few high-degree vertices. Adding low-degree vertices, which lack meaningful information, number of sampled vertices is low, 2- 2-FHNN generally performs better than 2-OHNN. For example, in the cases where m 5 and m = 10, 2-FHNN outperforms 2-OHNN in 9 out of the 12 experimental datasets. This suggests that 2-FHNN is more promising in the setting of aggressive pruning for high efficiency.
interfere with learning the graph structure. Third, when the
E.5. Runtime Results
To investigate the time complexity of the k-HNN model, we record the average time required to run one epoch across different datasets and vertex sampling sizes. The runtime results for 2-FHNN and 2-OHNN are presented in Table 4 and Table 7, respectively. Additionally, we also recorded the average time required to run one epoch across different hypergraph learning models. The runtime results are shown in Table 8.
Table 4. Time per Epoch (scconds) for Different Sampling Numbers (2-FHNN)
10
15
20
ALL
IMDB-DIR-FORD
7.58
8.46
8.46
8.58
10,27
IMDB-D SEEB-DDR-GENE GENNE
13.81
14.59
15.34
15.54
20.71
IMDB- WRI-FORM.
1.49
1.57
1.59
1.59
1.72
IMDB-WRI-GENT WRI-GENRE
4.67
4.86
4.83
5.06
5.89
PLAYER
10.75
11.10
11.21
10.87
11.16
6.82
7.13
7.63
7.34
7.77
From the experimental results in Table and Table 7, we make the following three observations. First, even with the same number of sampled vertices, the runtime of the same model varies significantly across different datasets. For instance. in the 2-FHNN model experiments, when sampling five vertices, the average runtime per epoch time is only 1.49 the IMDB-WE WADB-Wri-Genre dataset, while it rises to 13.81 s on the IMDB-Dir-Gentt dataset, a nearly 9-fold difference. This discrepancy can likely be attributed to the considerable difference in the average degree of hyperedges in the original hypergraph topology. For example, the average hyperedge degree in the IMDB-Wir Wri-Genre dataset is only 3.7, compared to 36.4 in the MMDB-Dir-Genre dataset, which is almost 10 times higher. As a result, even if two hypergraphs have the same number of nodes, differences in their topological structures can lead to substantial differences in model runtime.
27

---

Table 8. Time per Epoch (s) for Different HNN Models Improved Expressivity of Hypergraph Neural Networks through High- Hiigh-Dimensional Generalized Weisfeller-Leman Algorithms
Table 7. Time per Epoch (s) for Different Sampling Numbers (2-OHNN)
10
15
20
ALL
IMDB-DIR-FORD 7.50
8.30
8.51
8.50
8.98
MMDB-DIR-GENRE
13.65
14.46
14.90
15.41
17.41
MMBB-WRIFFORD
1.50
1.53
1.56
1.54
1.57
IIDB-RRI-GENRE
4.59
5.09
5.12
5.25
6.96
9.09
11.34
11.41
11.32
11.55
TWITTER-FRIEE 6.71
7.10
7.56
7.43
7.71
IMDB-
IMDB-DIR-GENTE HIDB-WRI-FORM
IMDB- WRI-GENRE
STEAM-PLAYER
TWITTER-PRIET
HNHN
7.4
10.78
0.3
0.87
2.94
1.37
HYPERGCN
39.54
131.23
3.8
13.58
98.49
100.73
HIC
3.68
10.27
0.99
3.16
5.58
4,48
UNIGCNH
5.52
9.92
0.98
3.18
5.4
3.19
SETTANS
5.8
10.24
1.01
3.28
5.69
4.16
ED-HNN
5,66
10.19
0.99
3.29
5.63
4.64
((OUR)
8.98
17.41
1.57
6,96
11,55
7.71
(-URS)
10.27
20.71
1.72
5.89
11.16
7.77
Second, the number of sampled vertices increases, the time required for the model to complete one epoch also increases. However, the rate of increase differs across datasets. We speculate that this is related to the average degree of the hyperedges in the datasets. For instance, in the epoch increases by nearly 50% when going from sampling 5 vertices to full sampling. In contrast, in the dataset, where the degree of hyperedge lower, the time required to complete one epoch only increases by about 15%.
dataset, where the hyperedge degree is higher, the time to complete one
Third, when the number of vertices inevitably increases, using 2- O-HNNN will have a lower runtime compared 2-FHNN, even though their theoretical time complexities for constructing k-tuples the same. For example, in the IMDB-Dir-Genre dataset, under the full sampling of vertices, 2-OHNN requires 14% less time than 2-FHNN.
Based on the experimental results in Table 8, we also make three observations. First, the training time per epoch for HyperGCN is significantly higher than all the other models. For example on the Twitter-Frient dataset, it is 14 times longer than the second-most time-consunen consumins model. This is because HyperGCN a spectral HNN that involves expensive dataset. Note that we did not include a variant of HyperGCN (Yadati al., 2019) that could run faster the expense of worse embeddings.
Laplacian computations for every hypergraph
Second, apart from HyperGCN, our 2-OHNN and 2-FHNN methods have the highest runtime. This is due to the computation of the k-set embeddings. However, the runtimes of our models do not exhibit explosive growth; they remain within an acceptable range, at most twice of the fast model UniGCNII.
Finally, combining with the runtime results of the vertex sampling experiment in Table and Table 7, when the number of sampled vertices is 5, the runtimes of 2-FHNN and 2-OHNN become much closer to those of the main models. Especially in the MIDB-DIR-GENTE dataset, with vertices sampled, the time ratio between our 2-FHNN and 2-OHNN models and the fastest model, UniGCNII, shrinks within factor of 1.4.
E.6. Efffec of Adding Node Labels
To validate whether the inclusion of additional node labels can enhance the expressive power of the model, we conduct the following experiments using the HIC model the baseline (whose expressive power is upper bounded by 1-GWL). We select two nodes in the graph to include additional feature values of 1 and 2, while the remaining nodes receive additional feature value of O. To ensure that each' pair of nodes is select at least once, we generate P(n, 2) label graphs, where P(n, 2) represents all possible combinations of selecting 2 nodes from nodes. We aggregate the final embeddings of all label graphs process by the HIC model to obtain the final graph embedding, which is then used for graph classification tasks. The variants obtain by the HIC model using this method are referred to as (II2)-HIC. The experimental results HIC and (1,2)-HIC are shown in Table 9.
28

---

Improved Expressivity of Hypergraph Neural Networks through Hligh-Dimensional Generalized WeiseellerLLeman Algorithms
Table Comparison the Inclusion of Additional Node Labels
MODEL
-RRM
STEAM-PLAYER
HIC 49.74.5..09 33.6113.33
58.35-11011 61.15:13.08
(1,2)-HIC
The experimental results indicate that adding additional node labels can indeed improve the model's accuracy. For example, on the For-- and Steam-Playe datasets, the model's performance improves by approximately 3.5% on average, further demonstrating that this method enhances model's expressive power.
E.7. The Number Layers and The Number of Parameters the Tested Models
Table 10. The Number Parameters in the Models with to Layers
MODEL
LAYER
2 LAYERS
LLYEERS
MLP
NA
9,219
20,102
HYPERGCN
NA
59.395
87,942
HNHN
NA
125,443
192,131
UNIGCNII
NA
41,731
58,115
ALLSETTRANSFORMER
135,171
NA
NA
ED-HNN
109,443
NA
HIC
NA
25,987
59,907
K-HNNs
117,379
216,963
316,547
Table 11. The Best-Performing Number of Layers in the Models
MODEL
IMDB FORM IMDB IMDB-DIR-G DIR-GENRE
IMDB MMBB-WRI-PRE WRI-FORM
IMDB WKI- BRI-GENRE
STEAM-PLAYER
TWITTER: TWITTER-PRIEND
MLP
3
2
3
2
HYPERGCN
2
HNHN
UNIGCNII
AILSETTRANSFORMER
ED-HNN
HIC
2
3
3
2-OHNN
2-FHNN
Here report the number of parameters for all tested models towards transparent comparison. We run different number of layers from to 3 for each of the models and report the highest performance achieved in Table 1. The best-performing number of layers in the tested models and their corresponding number of parameters can be found in Tables 11 and 10, respectively. For MLPs used in these models, we uniformly set the number of hidden layers as and their dimension as 128. In Table 10, k-HNNs have the same number of parameters for different values of k since they share the same neural network architecture. can be observed that our k-HNN models, AllSerTransformer, and HNHN use more parameters than others. However, our proposed models and ArlSeTTranffomer clearly outperform other baselines as shown in Table 1. For both graph and hypergraph deep learning, it still open problem how address the trade-off between expressive power and model complexity. In addition, run-times of our methods are mostly smaller than double those of compared methods, while the vertex sampling approach can effectively reduce the run time to be closer to that of other methods.
report the average time per epoch for all the models in Table 8 of Appendix E.5. The
29


Reviews:
[{"review_id": "tFbkBAk52S", "reviewer": "Reviewer_yrE6", "summary": "This work generalize high-order weisfeiler-Lehman test and high-order GNNs on graph to hypergraph. Furthermore, it build expressivity hierarchy among different orders of WL test on hypergraph. Using it instead of hyperGNNs corresponding to 1-WL leading to performance increase on real-world datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">The number of parameters is not compared between baselines and the proposed models, which may lead to unfair comparison.\n\nThank you for the valuable comment. We have collected the number of parameters in all tested models and reported them in the table below. It can be observed that our k-HNN models use more than three times the parameters compared to several models, double the parameters of HNHN, but notably fewer parameters than AllSetTransformer. However, our proposed models and AllSetTransformer clearly outperform other baselines as shown in Table 1. For both graph and hypergraph deep learning, it is still an open problem on how to address the trade-off between expressive power and model complexity. In addition, we report the average time per epoch for all the models in Table 8 of Appendix E.5. The run-times of our methods are mostly smaller than double those of compared methods, while the vertex sampling approach can effectively reduce the run-time to be closer to that of other methods.  \n\n \n\n| Models       | The number of parameters | \n|--------------|--------------------------| \n| MLP          | 20102                   | \n| HyperGCN     | 87942                   | \n| HNHN         | 187014                  | \n| UniGCNII     | 52230                   | \n| AllSetTransformer  | 390790                  | \n| ED-HNN        | 103558                  | \n| HIC          | 54406                   | \n| k-HNNs       | 365382                  | \n\nNote: k-HNNs have the same number of parameters for different values of k since they share the same neural network architecture.\n\n>Models corresponding to k-WL with k>2 should also be included.\n\nA: In our experiments, we had access only to a normal GPU server with a 1080Ti GPU with 11GB memory. Due to limited GPU memory, we considered only the case of $k = 2$. However, we recently obtained access to a GPU cluster with 40GB memory and have run experiments using our k-HNNs for $k=3$ based on the vertex sampling strategy with sample size 10. As shown in the table in our response to Reviewer H4JM, 3-HNNs with the sampling show comparable performance to 2-HNNs across the datasets, while outperforming the previously best model AllSetTransformer in the IMDB-Wri-Genre dataset. We will run the full 3-HNNs without the sampling (when there is no rebuttal time limit) and expect higher accuracy and include the results in the paper.\n\n>The adaption of k-WL to hypergraph is too straightforward and lacks novelty.\n\nk-WL cannot be directly applied to hypergraphs. The two main challenges in generalizing k-WL to hypergraphs are: (1) how to initialize the features of k-tuples through sub-hypergraph extractions while ensuring degeneration to k-WL, and (2) how to construct k-tuple hypergraphs from the original hypergraphs so that 1-GWL can be applied. Our key findings include: (a) establishing a Generalized WL hierarchy for hypergraphs with increasing expressivity, with the notable difference between 1-GFWL vs 2-GOWL, unlike its graph counterpart. (b) The hierarchy allows us to design hypergraph neural networks with the desired expressivity, improves upon most existing hypergraph neural networks whose expressive power is upper bounded by 1-GWL. \n\n>Text in figures are small and hard to read. Table 3 is too wide.\n\nA: Thank you for the comment to help improve the presentation of the paper. We will adjust the figures and table accordingly.  \n\n>Hypergraph can be bijectively mapping to a bipartite graph, with nodes and hyperedges in hypergraph as nodes in graph. Can we directly apply k-WL to this bipartite graph?\n\nThank you for the good question. One could transform hypergraphs to graphs via a bijective mapping, such as star expansion or line expansion [a], and then apply k-WL on the transformed graphs for isomorphism testing. However, even though the transformation is bijective, it does not guarantee the results of k-WL on the transformed graphs are the same as those of k-GWL on the original hypergraphs. For instance, we can find two non-isomorphic hypergraphs where k-GWL can distinguish them but k-WL cannot distinguish their transformed graphs. Figure 3(a) provides such an example: while 1-WL (equivalent to 2-OWL) fails to distinguish the transformed graphs, 2-GOWL successfully identifies the original hypergraphs. Therefore, this indirect method does not achieve the same expressive power as our k-GWL algorithm. We will include this observation in the final version. \n\nReference: \n\n[a] Chaoqi Yang, Ruijie Wang, Shuochao Yao, and Tarek F. Abdelzaher. \"Semi-supervised hypergraph node classification on hypergraph line expansion.\" In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 2352-2361. 2022.", "claims_and_evidence": "Yes. The proposed k-WL on hypergraph is meaningful for improving hypergraph network. The proposed method achieves provably high expressivity and better performance on real-world hypergraph datasets.", "methods_and_evaluation_criteria": "Yes, the tasks and baselines are representative for hypergraph domain and can show the performance of hyperGNN clearly.", "theoretical_claims": "Yes. I checked the proof for main theorem 5.2 and 5.3. The language and proofsketchs are commonly used in expressivity analysis. The proof is correct.", "experimental_designs_or_analyses": "1. The number of parameters is not compared between baselines and the proposed models, which may lead to unfair comparison.\n\n2. Models corresponding to k-WL with $k>2$ should also be included.", "relation_to_broader_scientific_literature": "It is related to high-order WL test and high-order GNN commonly used in graph. This work adapts it to hypergraph. Some details like the initialization of k-WL on hypergraph is meaningful.", "essential_references_not_discussed": "The related work is detailed and exhaustive, including representative expressive GNNs and representative HNNs.", "other_strengths_and_weaknesses": "The adaption of k-WL to hypergraph is too straightforward and lacks novelty. Improved complexity is also a weakness.", "other_comments_or_suggestions": "Text in figures are small and hard to read. Table 3 is too wide.", "questions_for_authors": "Hypergraph can be bijectively mapping to a bipartite graph, with nodes and hyperedges in hypergraph as nodes in graph. Can we directly apply k-WL to this bipartite graph?", "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": "", "extra_scores": {}}, {"review_id": "G5Gexck7wI", "reviewer": "Reviewer_H4JM", "summary": "The paper introduces the k-dimensional Generalized Weisfeiler-Leman (k-GWL) algorithm, an extension of the classical Weisfeiler-Leman (WL) test to hypergraphs. The primary contribution is the formulation of k-GWL, which generalizes k-WL from graphs to hypergraphs, providing a unified theoretical framework for hypergraph isomorphism testing. Building on k-GWL, the authors introduce k-HNN (k-dimensional Hypergraph Neural Networks), which leverage k-GWL's structure to enhance hypergraph representation learning. Empirical evaluations on six real-world hypergraph classification datasets demonstrate that k-HNN achieves state-of-the-art (SOTA) performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">The underperformance on IMDB-Wri-Genre suggests that certain hypergraph structures may not benefit from k-GWL, requiring further investigation. \n\nThank you very much for your comment. Following the suggestion of Reviewer yrE6, we have run experiments on k-HNNs for $k=3$ based on the vertex sampling strategy with sample size 10 in a GPU cluster with larger memory. As shown in the table below, 3-HNNs with the sampling show comparable performance to 2-HNNs across the datasets, while outperforming the previously best model AllSetTransformer in the Wri-Genre dataset. We will run the full 3-HNNs without the sampling (when there is no rebuttal time limit) and expect higher accuracy and include the results in the paper. We examined the dataset statistics in Table 5 of Appendix: there are six classes in Wri-Genre, which is significantly higher than in other datasets, making it a challenging dataset where every model seems to struggle. Moreover, in the two co-writer datasets (Wri-Genre and Wri-Type), there are significantly smaller number of hyperedges, with only about four hyperedges on average in a hypergraph, and each vertex participates in only 1.5 hyperedges on average. We was suspecting that the less amount of high-order information in the original hypergraph leads to a more dispersed construction of local neighbors between k-sets, which is not friendly to k-HNNs. However, the results of 3-HNNs with the sampling seem not support the thought.\n\n| Method               | IMDB_Dir_Form    | IMDB_Dir_Genre   | IMDB_Wri_Form   | IMDB_Wri_Genre  | Steam_Player    | Twitter_Friend  |\n|----------------------|------------------|------------------|-----------------|-----------------|-----------------|-----------------|\n| AllSetTransformer          | 66.76±2.55       | 79.31±0.94       | 52.67±4.77      | 54.09±2.41      | 61.87±1.87      | 64.03±1.34      |\n| 2-OHNN               | 67.25±2.35       | 79.75±1.14       | 55.35±3.74      | 50.08±1.89      | 65.97±1.37      | 64.12±1.30      |\n| 2-FHNN               | 68.11±2.46       | 78.52±1.07       | 55.36±3.30      | 45.44±1.24      | 67.53±1.23      | 62.75±2.18      |\n| 3-OHNN (Sample Size 10)   | 67.66±2.59       | 79.11±1.11       | 52.75±4.12      | 57.50±3.55      | 63.00±2.01      | 62.97±2.04      |\n| 3-FHNN (Sample Size 10)   | 67.07±2.33       | 78.90±1.1        | 50.56±2.69      | 53.84±2.05      | 61.50±1.59      | 63.05±3.67      |\n\n>It seems like [1] also discuss the expressivity of HNNs, but it is not cited by this paper.\n\nThank you for sharing the paper. We will ensure the following discussions are included in the final version. \n\n“(Luo et al, 2022) studied the expressivity of hypergraph neural networks and constructed hierarchies of arity (the maximum number of vertices in hyperedges) and depth. For example, when the depth is larger than a certain value, a neural logic machine with a larger arity is more expressive. In contrast, this paper generalizes k-WL to k-GWL, unifies graph and hypergraph isomorphism tests, and establishes a clear expressivity hierarchy for hypergraphs.” \n\n>Comparison to Approximate WL Methods: How does k-GWL compare to randomized WL tests.\n\nWe could not find papers introducing randomized WL tests after a Google search but do our best to discuss it based on our understanding. Our models with the vertex sampling become an approximation of the original k-GWL, effectively saving run-time at the expense of slight decrease in prediction accuracy. Randomized/approximate WL seems orthogonal with our k-GWL and can be combined for better computational efficiency. \n\n>No training time comparisons—it is unclear how much additional overhead k-HNN introduces compared to existing models.  \nTraining Time Comparison: Can you provide training time vs. existing HNNs? How much overhead does k-GWL introduce? \n\nSorry for not making the results of training time and their comparison easier to see. In Table 8 of Appendix E.5, we report the average time per epoch for different hypergraph learning models. The run-times of our k-HNN methods are mostly smaller than double those of other compared methods. The vertex sampling approach can effectively reduce run-time to be closer to that of other methods. For both GNNs and HNNs, it is still an open problem on how to further improve the trade-off between expressive power and run-time.\n\n>Can you explain more on the Definition 4.1? From my understanding, $s$ represents ID of nodes, then what does $s^1_{i_1} = s^1_{i_2}$ mean?\n\nSorry for the confusion. We use $s$ to represent a k-tuple and $s^1$ to represent a k-tuple in $HG_1$. The $i^{th}$ element in $s^1$ is referred to as $s_i^1$. $\\forall i_1, i_2 \\in [k], s^1_{i_1} = s^1_{i_2} \\leftrightarrow s^2_{i_1} = s^2_{i_2}$ means that if the $i_1^{th}$ element and $i_2^{th}$ element in $s^1$ are the same, then the $i_1^{th}$ element and $i_2^{th}$ element in $s^2$ are also identical.", "claims_and_evidence": "Claims Supported:\n\n- The expressivity hierarchy of k-GWL is rigorously proven (Theorems 5.1–5.4).\n\n- The reduction of k-GWL to k-WL for graphs is well-supported by theoretical results.\n\n- The claim that k-HNN outperforms existing hypergraph neural networks is empirically validated on diverse datasets.", "methods_and_evaluation_criteria": "- The chosen task of hypergraph classification aligns well with the proposed method.\n- The benchmark datasets (IMDB, Steam-Player, Twitter-Friend) cover diverse domains, ensuring broad applicability.", "theoretical_claims": "No, I did not check the proofs, but the overall statements make sense.", "experimental_designs_or_analyses": "Pro:\n- Strong empirical performance across diverse datasets, confirming the practical benefits of k-HNN.\n\n- Ablation studies (removal of singleton hyperedges) provide useful insights.\n\nCon:\n- No training time comparisons—it is unclear how much additional overhead k-HNN introduces compared to existing models.\n\n- The underperformance on IMDB-Wri-Genre suggests that certain hypergraph structures may not benefit from k-GWL, requiring further investigation.", "relation_to_broader_scientific_literature": "- The paper builds on the Weisfeiler-Leman hierarchy and extends prior work on hypergraph neural networks.\n\n- It contributes to hypergraph isomorphism testing by formalizing k-GWL as a higher-order method.", "essential_references_not_discussed": "It seems like [1] also discuss the expressivity of HNNs, but it is not cited by this paper.\n\n\n[1] Luo, Zhezheng, et al. \"On the expressiveness and generalization of hypergraph neural networks.\" arXiv preprint arXiv:2303.05490 (2023).", "other_strengths_and_weaknesses": "Pro:\n- Establishes a clear theoretical expressivity hierarchy for hypergraphs.\n\n- Provides a unified framework that extends existing graph and hypergraph isomorphism methods.\n\nCon:\n- Computational overhead remains a concern, especially for large k.\n\n- The method is only tested on classification tasks, limiting its generalizability.", "other_comments_or_suggestions": "- Comparison to Approximate WL Methods: How does k-GWL compare to randomized WL tests.\n- Training Time Comparison: Can you provide training time vs. existing HNNs? How much overhead does k-GWL introduce?\n- Can you explain more on the Definition 4.1? From my understanding, $s$ represents ID of nodes, then what does $s^1_{i_1}=s^1_{i_2}$ mean?", "questions_for_authors": "Same as comments.", "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": "", "extra_scores": {}}, {"review_id": "rBO22TxGG0", "reviewer": "Reviewer_eKNU", "summary": "The paper defines a k-WL variant for hypergraphs which did not exist so far. The test relies on a new structure that only relies on the nodes of the hypergraph and follows the idea of k-FWL or k-WL (the oblivious variant) which differ in the order of aggregation. They additionally come up with a GNN variant of it which effectively generalizes k-WL from Morris et al 2019 (using the same tricks with sets instead of tuples and local aggregation, both making the algorithm theoretically weaker). For most levels, the difference between k-FWL and k-OWL for hypergraphs follows the same pattern as for graphs (with FWL being one level stronger), but for hypergraphs this does not hold on the first level, which is surprising.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">As mentioned before, I was struggling with lacking formality around sets, multisets, and tuples. Misleading examples.\nInjectivity and resulting equality in expressivity should only hold when its about tuples.\n\nThank you for the valuable comment. We should formally define tuples, multisets, and sets in k-GWL and will include the following definitions at the beginning of Section 4.1. \n\n“Tuples are ordered and allow repetitive elements; multisets are unordered and allow repetitive elements; and sets are unordered and do not allow repetitive elements. In k-GWL, we consider k-tuples, which allow repetitions of vertices. There are two types of hypergraphs: the input hypergraph and the k-tuple hypergraph (see its construction in Section 4.1.2). Hyperedges in both types of hypergraphs are sets, that is unordered.” \n\nWe will add the following discussions on how to handle repetitions of vertices in k-tuples in Section 4. “Specifically, both k-GWL and k-WL allow repetitions of vertices in k-tuples. In the initialization of k-tuple features, they extract sub-hypergraphs and subgraphs induced by the *set* of vertices in k-tuples and then use the isomorphism type as features, where the set operation before extraction removes vertex repetitions. For the construction of k-tuple hypergraphs and k-tuple graphs, because tuples allow repetitions, the vertex replacement strategies in the oblivious and folklore variants (\"all elements in one position\" vs. \"one element in all k positions\") still work with no issues.” \n\nFor better illustrating the construction of k-tuple hypergraphs, we will plot a new version of Figure 3 based on k-tuples, where repetitions of vertices are considered. For example, the folklore hypergraph now includes five hyperedges instead of only two. The hyperedge with $v_1$ in all three positions of $(v_1,v_2,v_3)$  includes $(v_1,v_2,v_3)$, $(v_1,v_1,v_3)$, and $(v_1,v_2,v_1)$. The oblivious hypergraph still has three hyperedges but $e_1$ with all vertices in the first position of $(v_1,v_2,v_3)$ includes two extra k-tuples $(v_2,v_2,v_3)$ and $(v_3,v_2,v_3)$. \n\nLast but not least, we will explicitly state that all our theoretical findings on the k-GWL hierarchy and equivalence of k-HNNs and k-GWL (theorems in Sections 5 and 6) are based on using k-tuples. The only place where we switch from k-tuples to k-sets is in the implementation of k-HNNs. Ignoring the vertex ordering and repetitions of vertices in k-tuples makes k-HNNs considerably more practical.\n\n>p5: it is only once mentioned indirectly how the hyperedges are included in the construction...\n\nThanks for bringing this issue to our attention. In Section 4, we will emphasize that the construction of k-tuple hypergraph in k-GWL does not depend on the set of hyperedges in the original hypergraph, which is only used in the isomorphism type. In Section 6, we will point out, unlike k-GWL, for k-HNNs based on local neighborhoods, the actual hyperedges of the input hypergraph do influence the construction of the k-tuple hypergraph.\n\n>sec 5.2: what is done about permutations...\n\nThank you for pointing out the issue. The original idea of relational pooling (that inspires $(k,l)$-WL) is to build expressive permutation-invariant models, where permutation invariance is obtained by averaging or summing over representations under all permutations of node IDs. Later on, local relational pooling performs permutation and averaging within a subgraph of size $l$ to reduce computational complexity. Similarly, $(k,l)$-WL assigns extra labels $1,2,\\cdots,l$ to $l$ vertices, but runs k-WL on the whole graph with the additional labels only for those $l$ vertices. This is repeated for every possible labeled graph and then the final representation of the graph is aggregated from the representations of all labeled graphs. The extra vertex labels help boost expressivity. One can apply the same idea in k-GWL to get $(k,l)$-GWL. In the computational complexity, the term for the labelling should be $\\binom{n}{l}^l$ (that is, select $l$ vertices from $n$ vertices and then assign $l$ labels to the $l$ vertices).\n\n>Other Comments Or Suggestions\n\nThank you for your detailed comments. We sincerely appreciate your efforts in helping enhance the presentation of this manuscript and will apply these comments. \n\n>sec 7: is it common to exclude original vertex features? And how do results change if you add them? \n\nKeeping the original vertex features makes it easier to distinguish non-isomorphic hypergraphs, due to the potentially very different vertex features. Hence, it is a common practice to exclude these features and focus on structural information only.  We used the datasets from (Feng et al., 2024), which performed the pre-processing. Unfortunately, they have not provided the original vertex features, but we expect the accuracy would be higher with original vertex features being added. \n\n> Analysis of underperformance in Wri-Genre\n\nPlease refer to the first response to Reviewer H4JM.", "claims_and_evidence": "All the claims are backed with evidence, typically proofs.", "methods_and_evaluation_criteria": "yes, proofing theorems about theoretical results indeed makes a lot of sense. Since there are not many hypergraph datasets, testing might be a bit harder. It would be interesting to see how the method works on databases (which are inherently hypergraphs), but those are typically too big to be handled by even 2-WL due to the exponential blowup.", "theoretical_claims": "I did not check the proofs, but the results are not surprising (except for the difference between 1-GFWL vs 2-GOWL which they showed using an example).\n\nI would like to mention that the notation could be more clear and explicit in certain situations, especially when it comes to tuples, multisets, and sets and how they are interacting and how duplicates are handled.", "experimental_designs_or_analyses": "looks good (given that there are not many hypergraph datasets available and databases are too big).", "relation_to_broader_scientific_literature": "The paper very clearly states where it stands in term of hypergraph GNN research and also clearly shows the research gap.", "essential_references_not_discussed": "none.", "other_strengths_and_weaknesses": "As mentioned before, I was struggling with lacking formality around sets, multisets, and tuples. \n\nIn section 3, please mention explicitly that hyperedges are unordered (which becomes relevant because the tuples of k-WL are ordered and k-WL somewhat expects relations to have an ordering as well). It would be nice if that difference was thoroughly discussed.\n\np5: it is only once mentioned indirectly how the hyperedges are included in the construction - namely only indirectly through the isomorphism type. This is not directly expected intuitively and could be mentioned explicitly. It took me quite a while to figure out that the whole construction really only depends on the vertex set and none of the introduced hyperedges depended on the actual hyperedges of the hypergraph we are working on. It would also be nice to mention that the runtime is independent of the number of hyperedges in the original hypergraph. The way it is written in sec 4.2 could be quite a bit clearer (as there is a set of hyperedges mentioned, but that does not seem to be the set of hyperedges of the original hypergraph, but rather of the constructed one).\n\np5: the examples are misleading as they do not consider repetitions which are (for standard k-WL) allowed. \n\nGenerally, I would have liked a very early explicit mention for the 2-GOWL vs 1-GFWL case instead of just writing this holds for k>=2. Because at least I was thinking about what that should mean and what is happening in the abovementioned case (as it is different from graphs). \n\nsec 5.2: to me this section is not clear at all, what is done about permutations and how is the relation to individualization and refinement? (where you also put labels to stuff but in a way that does not change things). Furthermore, I would expect $\\binom{n}{l}^l$ instead of without the exponent.", "other_comments_or_suggestions": "Please note that the paper did NOT use the official template (but probably last year's template without the line numbers). \n\np3 first equation and eq 1 both have an extra pair of unnecessary brackets. Also eq 1 is not nicely indented (please align below the = symbol) same for eq 4 and 5 (and probably any multiline formula in the paper)\n\np3 the Babai 2016 citation is really unexpected here. It really has nothing to do with the whole paragraph (at least in my understanding) \n\np3 it would be nice to describe the exact difference between FWL and OWL here as it is used later on. Or at least do so in the appendix.\n\np3 end: please mention here that this compares tuples against sets and make explicit how duplicate entries in tuples are handled.\n\np3 def 4.1: I believe that is still just the atomic type that is known in logic. Or is there any difference (if yes, please mention it here)\n\np4 def of N(s): this looks to be identical to the graph setting, so it would be nice to state that this part is not new but rather standard.\n\np5: a good way to describe the difference between OWL and FWL is \"all elements in one position\" as opposed to \"one element in all k positions\". \n\np3 isomorphiosm -> isomorphism\np4 usng -> using\np6 typography in eq 6 and 7: please use \\text{FWL} etc instead of just writing $GOWL$. This should also avoid the - sign to have that amount of space (in doubt, move it into the \\text{} part.", "questions_for_authors": "My main questions are in the textbox about Other Strengths And Weaknesses. I am especially interested in the difference between sets, multisets, and tuples and would like the paper to be a bit more formal in that regard. Otherwise I really like the results (but the presentation could still be improved).\n\n\nsec 7: is it common to exclude original vertex features? And how do results change if you add them?\n\nExpressivity: injectivity and resulting equality in expressivity should only hold when its about tuples and not when its sets. Otherwise please write more about that difference here.\n\nHow small is the average hyperedge degree in Wri-Genre and why is that a problem? Is it really that different to the other datasets?", "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": "", "extra_scores": {}}, {"review_id": "JBt5o6anEu", "reviewer": "Reviewer_NmFi", "summary": "The paper presents a higher-order version of the WL test for hypergraphs. It is a conservative extension of the well-known higher-order WL for graphs, in the sense that when run over graphs, both tests have the same expressive power. A hypergraph-GNN architecture is then designed in terms of this higher-order test: It is shown that the expressive power of such hyperedge-GNNs is bounded by that of the higher-order WL test, and that it is always possible to emulate the expressive power of the test over graphs with n vertices by one of these hyperedge-GNN architectures. Experiments analyzing the suitability of the approach on real-world datasets.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">As mentioned before, I feel lukewarm about this paper. While it is a solid piece of work and may interest some researchers in the community, it lacks truly innovative contributions. Perhaps its main strength lies in the clear presentation of the extension of k-WL from graphs to hypergraphs, but I have doubts about whether this alone is sufficient to justify acceptance at ICML. \n\nk-WL cannot be directly applied to hypergraphs. The two main challenges in generalizing k-WL to hypergraphs are: (1) how to initialize the features of k-tuples through sub-hypergraph extractions while ensuring degeneration to k-WL, and (2) how to construct k-tuple hypergraphs from the original hypergraphs so that 1-GWL can be applied. Our key findings include: (a) establishing a Generalized WL hierarchy for hypergraphs with increasing expressivity, with the notable difference between 1-GFWL vs 2-GOWL, unlike its graph counterpart. (b) The hierarchy allows us to design hypergraph neural networks with the desired expressivity, improves upon most existing hypergraph neural networks whose expressive power is upper bounded by 1-GWL. \n\n>Q1. About the removal of singleton hyperedges: Does it mean that you allow no vertex colors in hypergraphs? Do you allow for repetition of vertices in hyperedges? Cannot you then encode a singleton hyperedge of the form (v) with (v,v)?\n\nThank you for the comments. We allow vertex colors/features in hypergraphs, such as the example of vertex colors 1 and 2 in Figure 3’s hard instances. In addition to removing singleton hyperedges, one could also consider adding the singleton hyperedge information as an extra vertex feature. However, the singleton hyperedges still need to be removed, ensuring that k-GWL can degenerate to k-WL for simple graphs, with consistent sub-hypergraphs and subgraphs.  We treat hyperedges as sets and do not allow duplicate vertices in hyperedges. But we allow repetitions of vertices in k-tuples, which is discussed in our response to Reviewer eKNU. \n\n>Q2. Regarding your result that k-folklore and (k+1)-oblivious WL are equally expressive: I understand that this is a proper generalization of the result obtained by Grohe & Otto for graphs. But your proof seems considerably simpler. In fact, Grohe & Otto requires heavy machinery based on linear algebra and linear programming to obtain this result. Please compare your result against them and explain how you managed to obtain the results without extending their machinery.\n\nThank you for the good question. You are right that Grohe & Otto (2015) used heavy algebraic and linear programming methods to establish the equal expressivity between k-folklore and (k+1)-oblivious WL. Later, Grohe in his LICS'21 paper “The Logic of Graph Neural Networks” provided a considerably simpler less-than-one-page proof based on mathematical induction on iterations and analysis on the two variants’ computations. (See page 16 of https://arxiv.org/pdf/2104.14624, Proof of Theorem V.6 in Appendix.) We performed a careful adaptation of this simpler proof for hypergraphs, showing the equivalence of k-folklore and (k+1)-oblivious Generalized WL.", "claims_and_evidence": "All theoretical results are supported by carefully written proofs. My only concern refers to the proof that k-folklore and (k+1)-oblivious WL coincide in expressive power (see my comments in the Questions for Authors).", "methods_and_evaluation_criteria": "Yes, the experimental data has been chosen appropriately.", "theoretical_claims": "I have not read all proofs in the appendix, but I know in depth this class of results and I am basically convinced about their correctness (save for the equivalence of k-folklore and (k+1)-oblivious WL, see below).", "experimental_designs_or_analyses": "I have not checked this since I do not have enough competence to do it.", "relation_to_broader_scientific_literature": "The paper extends a well-established line of research on graphs and hypergraphs, exploring the expressive power of GNNs in relation to isomorphism tests. The techniques employed are standard within this literature. In this sense, while the paper is solid and well-rounded, it is somewhat incremental and not particularly innovative. For instance, all separability results obtained in the paper are shown by a direct translation into well-known (and sophisticated) results for graphs. This raises some doubts about its suitability for ICML. In my view, it falls slightly below the standard one would expect from a strong ICML paper.", "essential_references_not_discussed": "I think that the related literature is well-covered in the paper.", "other_strengths_and_weaknesses": "As mentioned before, I feel lukewarm about this paper. While it is a solid piece of work and may interest some researchers in the community, it lacks truly innovative contributions. Perhaps its main strength lies in the clear presentation of the extension of k-WL from graphs to hypergraphs, but I have doubts about whether this alone is sufficient to justify acceptance at ICML.", "other_comments_or_suggestions": "I have no further comments.", "questions_for_authors": "Q1. About the removal of singleton hyperedges: Does it mean that you allow no vertex colors in hypergraphs? Do you allow for repetition of vertices in hyperedges? Cannot you then encode a singleton hyperedge of the form (v) with (v,v)? \n\nQ2. Regarding your result that k-folklore and (k+1)-oblivious WL are equally expressive: I understand that this is a proper generalization of the result obtained by Grohe & Otto for graphs. But your proof seems considerably simpler. In fact, Grohe & Otto requires heavy machinery based on linear algebra and linear programming to obtain this result. Please compare your result against them and explain how you managed to obtain the results without extending their machinery.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a variant of the k-dimensional Weisfeiler-Leman test for hypergraphs, called k-GWL. The expressivity hierarchy of k-GWL is rigorously proven in Theorems 5.1–5.4. The paper additionally introduces a GNN variant of the k-GWL test (k-HNN) which generalizes k-WL from Morris et al 2019. Their k-HNN seems to outperform existing hypergraph neural networks empirically on some datasets.


The reviewers positively emphasized the strong empirical performance across diverse datasets, and the theoretical analysis of the expressivity hierarchy for hypergraphs introduced by the paper.


The reviewers also identified a few limitations:


1. Since there are not many hypergraph datasets, testing the method is challenging. It would have been more interesting to see how the method works on datasets which are inherently hypergraphs, but those are typically too big to be handled by even 2-WL due to the exponential blowup. This leads to the next point, which is a main limitation of the method: its computational overhead.


2. Computational overhead remains a concern, especially for large k.


3. In the experiments, the number of parameters is not the same between baselines and the proposed models, which makes it unclear in what sense the comparison is fair. Does the current paper use the recommended hyperparameters from the original papers that published each competing method? This is not written in the paper. If accepted, please add a section that discusses how the architecture and the hyperparameters were chosen for each competing method.


If accepted, please incorporate the reviewer’s comments in the camera-ready version of the paper.
Decision: Accept (poster)