Higher-Order Learning with Graph Neural Networks via Hypergraph Encodings
Authors: Raphaël Pellegrin
Lukas Fesser
Melanie Weber
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Relational Learning
Hypergraph Neural Networks
Discrete Curvature
Primary area: deep_learning
TL;DR: We propose encodings based on hypergraph Laplacians and discrete notions of curvature to capture higher-order information.

Abstract: Higher-order information is crucial for relational learning in many domains where relationships extend beyond pairwise interactions. Hypergraphs provide a natural framework for modeling such relationships, which has motivated recent extensions of graph neural network (GNN) architectures to hypergraphs. Most of these architectures rely on message-passing to encode higher-order information. In this paper, we propose to instead use hypergraph-level encodings based on characteristics such as hypergraph Laplacians and discrete curvature notions. These encodings can be used on datasets that are naturally parametrized as hypergraphs and on graph-level datasets, which we reparametrize as hypergraphs to compute encodings. In both settings, performance increases significantly, on social networks by more than 10 percent. Our theoretical analysis shows that hypergraph-level encodings provably increase the representational power of message-passing graph neural networks beyond that of their graph-level counterparts. For complete reproducibility, we release our codebase: https://github.com/Weber-GeoML/Hypergraph_Encodings.

Higher-Order Learning with Graph Neural Networks via Hypergraph Encodings
Raphael Pellegrin" Independent Researcher
Lukas Fesser* Harvard University
raphaelpeellggrineaalmmm harvard.
lukas_fesserrfas harvard. edu
Melanie Weber
Harvard University
mveber@seas. harvard.edu
Abstract
Higher-order information is crucial for relational learning in many domains where relation- ships extend beyond pairwise interactions. Hypergraphs provide natural framework for modeling such relationships, which has motivated recent extensions of graph neural network (GNN) architectures to hypergraphs. Most of these architectures rely encode higher-order information. this paper, we propose to instead use hypergraph- encodings based on characteristics such as hypergraph Laplacians and discrete curvature notions. These encodings can be used on datasets that are naturally parametrized as hy- pergraphs and graph-level datasets, which reparametrize as hypergraphs to compute encodings. both settings, performance increases significantly, on social networks by more than percent. Our theoretical analysis shows that hypergraph-level encodings provably increase the representational power of message-passinn graph neural networks beyond that of their graph-level counterparts. For complete reproducibility. we release our codebase: bictps///githh www//Weee---eeeeeoooooeeeeo HetieGG///M/////aaaararr Encodings
passsag--passine
Introduction
Many datasets have inherent "multi-way" structure, where downstream tasks depend on relationships between groups of entities that ordinary graphs, whose edges pairwise relationships. cannot represent (Bick et al., 2023] Benson et al. 2021] Schaub et al., (02T). Hypergraphs overcome this by allowing hyperedges that connect any number of vertices. How models effectively leverage such higher-order information for learning?
The enhanced flexibility of hypergraphs has motivated a growing body of literature on hypergraph neural network architectures, including message-passing (Huang & Yang 2021) and transformer- based models (Liu et al. 2024). Naively extending these paradigms from graph neural networks to hypergraphs often fails to capture crucial substructures. On the other hand, reparametrizing hypergraph standard graph via clique expansion introduce redundant pairwise edges that obscure higher-order structures. This suggests that architectural bias alone is insufficient.
While previous work has focused such architectural extensions, we propose different route. Instead encoding higher-order structure as inductive biases directly, we propose a data augmentation approach. Encodings that augment the input with structural information (e.g., spectra (Dwivedi et al.) 2023), motif counts (Zhao et al. 2021). discrete curvature (Fesser & Weber (2024a) have been shown to yield significant performance gains. However, encodings have been studied almost exclusively at graph-level and fail to capture higher-order information specific to hypergraph representations.
These authors* contributed equally.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this work we design hypergraph-leve encodings based on classical hypergraph characteristics, and prove that they capture higher-order structural information that cannot be represented by standard hypergraph geessageppassing architectures existing graph-level encodings. Our experimental results benchmark the new encodings combination with graph- and hypergraph- message-passinng as well as transformer-based architectures. While hypergraph-level encodings offer only marginal benefit for hypergraph-level architectures, they yield significant performance gains when paired with graph-level sessage-passiigg and transformers.
1.1 Related Work
Topological Deep Learning has emerged as the dominant framework for learning on topological do- mains, including hypergraphs, well simplicial, polyhedral and more general cell complexes (Haji)
et al. 2022 2024; Papillon et al.) 2023). Many classical graph-learning architectures have been
extended these domains. In the case of hypergraphs, this includes pressage-passingg (Huang &
Yang 2021 Wang et al., 2022 2023 and transformer-based (Liu et al., 2024) hypergraph neural networks.
To the best our knowledge, encodings have so far only been studied in the context of graph-level learning (Dwivedi al. 2023). Popular encodings leverage structural and positional information
captured by classical graph characteristics (Rampášek et 2022 Kreuzer et al., 2021 Cai Wang 2018
Zhao et al. 2021 Fesser & Weber 2024a Bouritsas et al. (2022).
1.2
Summary of Contributions
The main contributions of this paper are as follows:
(I)
We introduce hypergraph-level encodings that augment a (byper-)graphh-stuuttur input with higher-order positional and structural information captured in hypergraph characteristics.
(2) We show that hypergraph-level encodings are provably expressive than their graph-level counterparts.
33) We show that hypergraph-leve encodings can significantly enhance the performance of graph neural networks applied to hypergraph expansions.
2
Background
We consider graphs G = XV, F) with node attributes representing pairwise relations between nodes in V. We further consider hypergraphs = (V, F) where hyperedges F denote relations between groups nodes. Hypergraphs can be reparametrized as A graph can be lifted to hypergraph
RR|V and edges E C V XV,
graphs using clique expansions; for more details see Apx. A. 1 by adding a hyperedge for every set of vertices that are pairwise connected in the graph effectively turning each clique into single higher-order relation; see Apx. A.2 In a graph,
represent the EJ. In hypergraph, we similarly define the neighborhood of node i V as NG {j V {i} Be F such that {i,j) S e) i.e., the set of nodes; that co-occur with in at least one hyperedge. The degree d, of a vertex of an undirected (hyper)graph H (V, X, F)) is the number of (hyper)edges that contain i (Klamt et al.
set of all nodes j that are adjacent to i as Ar = (j E V (i,j)
2009).
2.1 Architectures
Message-passing GNN. Message-Passing (MP) (Gori al., 2005 Hamilton al. 2017) is prominent learning paradigm in relational learning, where a node's representation is iteratively updated based on the representations of its neighbors. Formally, let z denote the representation of node at layer l. Message- passing implements the following update,
I+1
(1(
( 1/2 (z5)
PEN.
where 1/z denotes an aggregation function (e.g., averaging) acting on the 1-hop neighborhood. Nr, of (if self-loops are added, we consider p Nr U {v} instead), and Φi update function with trainable

---

parameters, such as an MLP. The number of MP iterations is commonly referred to as the depth of the network. Representations are initialized by the node attributes in the imput.
Transformerrbased GNN. The second major class of architectures for relational learning is transformer-based (GT). Networks consist of blocks of multi-head attention layers (Global (tlobalAAtt(())) Attn(-)), followed by fully-connected feedforward networks. In the recent literature, hybrid architectures, which combine MP and attention layers, have been shown exhibit strong performance on several state of the art benchmarks (Rampásek et al. 2022).
Graph-level Architectures. Our selection of graph-level architectures includes two message-passing passing GNNs (MPGNNs) and one hybrid architecture. GCN (Kipf & Welling 2016) is one of the simplest
and most popular MPGNNs, making it an important reference point. GIN (Xu et al. 2018) is designed to be a maximally expressive MPGNN. GraphGPS (Rampášek et al. 2022) is a widely used hybrid architecture that performs well across the benchmarks considered here. These models remain strong baselines and still outperform many newer models in both node- and graph-level tasks (Luo et al. 2024). As baselines, we evaluate simple instances of all three architectures without additional model interventions. An overview of the architectures can be found in Tab. 4 more detailed descriptions are deferred to Apx. B.I
Hypergraph-level Architectures. The architectures analyzed in this study implement message- passing, which on hypergraphs is implemented via tww-twwhae two-phase scheme: messages are passed from nodes to hyperedges and then back to nodes (Huang & Yang 202I). Formally.
htt1 = Φ1 (fa))
J = d2 2 (++1) JEEE.)
JEEE.
Here, 2y denotes the node features of node j. he denotes the edge feature of edge e, Ej is the set of all hyperedges containing j. and Φ1 and de are permutation-invarian from vertices and hyperedges respectively. ã. indicates the output of the message-passin layer before activation or normalization. Tab. D provides an overview of the hypergraph-level architectures considered here; more detailed description can be found in Apx. B.2
functions for aggregating messages
2.2 Encodings
Structural (SE) and Positional (PE) encodings enhance MPGNNs by providing access to struc- tural information that is crucial for downstream tasks, but that these networks cannot inherently learn (Dwivedi et al., 2023 Rampášek et al. 2022). Encodings can capture either local or global properties of the input graph. Local PEs supply nodes with information about their position within local clusters or substructures, such as their distance to the centroid of their community. In contrast, global PEs convey a node's overall position within the entire graph, often based on spectral properties like the eigenvectors of the Graph Laplacian (Kreuzer et al.] 2021 or random-walk based node similarities (Dwivedi et al., 202T). Graph-level SEs capture structural information, such as pair-wise node distances, node degrees, or statistics regarding the distribution of neighbors' degrees (Cai & Wang 20118), or discrete curvature (Fesser& & Weber, 2024a). Empirical evidence demonstrates that incorporating these PEs and SEs significantly improves the performance of GNNs (Rampášck et al. 2022).
2.3 Representational Power
key theoretical question evaluating the effectiveness of different relational learning architectures is their representational power or expressivity: Which functions can and cannot be learned by the model? This question can be analyzed through the lens of a model's 's ability to distinguish graphs that are not topologically identical (isomorphic). The 1- Peeisseiler--eemale (1-WL) test (Weisfeiler & Leman 1968) provides heuristic for this question. Notably, Xu et al. (2018) showed that MPGNNS (specifically, GIN) are expressive the 1-WL test. While 1- (and, by extension, MPGNNs) is effective for many classes of graphs, it has notable limitations, such as in distinguishing regular graphs. Generalizations of this procedure, known as the k-WL test, establish hierarchy of progressively more powerful tests. At the same time, several graph characteristics are known to be more expressive than the 1-WL test. Consequently, combining MPGNNs with encodings based on these characteristics can enhance their expressivity (Southern et al. 2023 We conduct an expressivity analysis in Apx.
Fesser & Weber 2024a Bouritsas et al. 2022).
With the exception of PhenomNN WWag et al.
2023
3

---

3 Hypergraph-leve Encodings
3.1 Laplacian Eigenvectors
Let Dr be the degree matrix, and A be the adjacency matrix. The Graph Laplacian A Dr A classical graph characteristic that often leveraged for the design of encodings. Laplacian Eigenvector PE (LAPE) are defined as
LapPE U1, Un)) E R
where A = U AU is spectral decomposition; k is a hyperparameter. Note that the eigenvectors only defined up to =1; we follow the convention in (Dwivedi et al. 2021) and apply random sign flips.
In order to define hypergraph-Ieve extension of LAPE, we have consider first the choice of Laplacian. We focus on the Hodge Laplacian here, but discuss other choices, specifically the normalized hypergraph Laplacian and random- Laplacian, in Laplacian is motivated by its desirable properties, including that it is symmetric.
Our choice of the Hodge
Definition 3.1. (Hodge Laplacian). Let B1 denote an incidence matrix whose entries indicate relations between nodes and hyperedges. node is on the boundary of hyperedge j. the relation is expressed as i j.
[
(Bi),,
ERIXXIF
0 otherwise
The 0- and 1-Hodge Laplacian are given by Ho B Bi and Hi B,Bf.
We define the eigenvectors of the Hodge Laplacian. We show below that the additional higher-order information captured by H-k-LAPE, but not by k-LAPE or standard message- weessage-psssing provably enhances the representational power of the architecture. The proofs in this and subsequent sections refer to graphs in the BREC dataset (Wang & Zhang 2023), more information on which is provided in the Apx. E. We outline the computations of the different encodings for specific pair of the BREC dataset Apx. F2
Positional Encoding (H-k-LAPE) in analogy to Eq. using the top
Theorem 3.2. (H-k-LAPE Expressivity). For any k. MPGNNs with H-k-LAPE are strictly more expressive than the 1-WL test and hence MPGNNs without encodings. Furthermore, there exist graphs which can be distinguished using H-k-LAPE, but not using k-LAPE.
Remark 3.3. In the proof of our theorems, we follow a two-step strategy. We first note that the seminal work by Xu et al. (2018) has established that standard MPGNNs the 1-WL test, with GIN constructed specifically to be as expressive as the 1-WL test. It can be shown via adaptation of Xu al. (2018) that adding encodings does not decrease MPGNNs expressivity, ie., GIN -and thus MPGNNs- with encodings are at least as expressive as the 1-WL test. To establish strictly better expressivity, it is sufficient identify set of non-isomorppic graphs that cannot be distinguished by the 1-WL test, but that differ in their encodings.
most expressive as
Proof. Pair of the "Basic" category in BREC (Apx. E.1 is pair of non-isomorphic, 1-WL indistinguishable graphs (see Fig. []. The pair is ELAPP-indistinguiin with H-1-LAPE (see Apx.
but can be distinguished
Remark 3.4. (H-LAPE Complexity). Computing full spectral decomposition of A has complexity ((VV)), where [V| is the number of nodes in the input hypergraph. However, by exploiting sparsity and the fact that we only require the top eigenvectors, Lanczos' algorithm can be used to compute H-k-LAPE in ((F
3.2 Random Walk Transition Probabilities
Another widely used positional encoding, Random Walk PE (RWPE), is defined using the probability of random walk revisiting node after ... steps, formally
P
A RWPE
(RW,, RW2 RW?)² IR
(3)

---

Pair (basic)
Graph 10 nodes, 26 edges
Hyperaraph (13 hyperedges)
10 nodes, 26 edges
113 hyperedges)
Hypergraph A Eoge Degree Distrbbttinn11 haperedges
Hypergraph Edge Degree Untrexuticnl hyperedges)
Hypergraph Node Degree Distibbtion
Hypergraph E Node Degree Instritutionss
Count
4
Hyperadge Size
Hyperedie
Cegree
Degree
Figure I: A pair of graph from the BREC "Basic" category (top left), the graphs' liftings (top right), the hyperedge sizes (bottom left) and node degrees (bottom right).
where k is a hyperparameter. Since the return probabilities depend on the graph's 's topology, they capture crucial structural information. Notably, k-RWPE does not suffer from sign ambiguity like LAPE, instead providing unique node representation whenever nodes have topologically distinct k-hop neighborhoods.
We define analogous notion of PEs at the hypergraph level. We consider the following notion:
Definition 3.5. (Random Walks Hypergraphs (Coupette al., 2022)). We define Equal-
Nodes Random Walks (EN) and Equal-Edges Random Walks (EE), which induce the following two measures:
N.. ifj E
(i M
14 (i)
(4)
otherwise
otherwise
where N2 the neighbors of and transition probabilities are given by
1 PEE (i + 5) Heli e e, e, 2}
Σ (elfC))Ce)
1
le
For an EN random walk, considering move from node i, pick one of the neighbors of node i at random. For the EE scheme, we first pick a hyperedge that belongs to at random and then pick one of the nodes in the hyperedge at random.
We can now define Hypergraph Random Walk Positional Encodings (H-k-RWPE) in analogy to k-RWPE. Again, we can show that H-k-RWPE provably enhances the representational power of an MPGNN, beyond those of k-RWPE.
Theorem 3.6. (H-k-RWPE Expressivity). For l 2 2, MPGNNs with H-k-RWPE are strictly more expressive than the I-WL test and hence than MPGNNs without encodings. There exist graphs which can distinguished using H-k-RWPE, but not using graph-level k-RWPE.
Proof. Pair 0 of the "Basic" category BREC is pair of non-isomorphic graphs that not 1-WL-- distinguishable. The pair cannot be distinguished with graph-level 2-RWPF, but can be distinguished using the H-2-RWPE encodings computed at the hypergraph level (see Apx.
Remark 3.7. Note that k-RWPE less expressive that (k + 1)-RWPE and H-K-RWPE is less expressive than (kt + 1)-H-RWPE. Remark 3.8. (H-K-RWPE Complexity). Computing H-k-RWPE scales as O(VV (e where dmux the highest node degrec in the input hypergraph.
5

---

3.3 Local Curvature Profiles
Recently was shown that discrete Ricci curvature yields an effective structural encoding at the graph level (Fesser & Weber (024a)). Ricci curvature is a classical tool from Differential Geometry that
allows for characterizing local and global properties of geodesic spaces. Discrete analogues of Ricci curvature (Forman 20033 Ollivier 2007) have been studied extensively on graphs and, more recently,
on hypergraphs (Leal et al. 2202 Coupette et al. 2022 Saucan & Weher 2019). Here, we focus on
defining hypergraph-lever curvatures, we defer all details on graph-level notions to Apx.A.. A.5
We restrict ourselves two notions of discrete Ricci curvature, originally introduced by Forman Forr man 2003) and Ollivier (Ollivier] 2007), which have previously been considered for graph-level encodings. We begin with Forman's curvature:
Definition 3.9. (Forman's Ricci Curvature Hypergraphs (H-FRC) (Leal et al. 202 The H-FRC of a hyperedge is defined as F(e) = Ex dz).
Ollivier's Ricci curvature derives from a fundamental relationship between Ricci curvature and the behavior of random walks on geodesic spaces. To define an analogous notion on hypergraphs, we leverage again the previously introduced notions of random walks (Coupette et al., 2022).
Definition 3.10. (Ollivier's Ricci Curvature on Hypergraphs (H-ORC) (Coupette et al. 2022)). The H-ORC of a subset of nodes on hypergraph is defined as:
AGG(s)
<(s)
(5)
d(s)
where d((s) = {max
s} and where d(i,j) is the length of shortest path connecting nodes i, j. We define for a hyperedge e
<(e) = 1 AGG(e).
Here, AGG(-) denotes an aggregation function.
Different types of aggregations could be considered for the choice of AGG(.) Here, we choose AGG(-) to be the average of the Wasserstein distances between all pairs {ū,j} hyperedge e, i...
1 AGG(e) = (1)
Σ (R.)Cc
W Wi
We can now define the actual encoding, extending Local Curvature Profiles (LCP) (Fesser & Weber 2024a), computed at the graph level, to hypergraphs.
Definition 3.11. (Hypergraph Curvature Profile (HCP)). For v E V let (M) denote a curvatwe
multi-ser consisting of the curvatures of all hyperedges containing v, CMS(e) (K(e) : E e, e F), where λ may be chosen to denote either H-FRC or H-ORC. We define HCP as the following five summary statistics of CMS(p):
HCP(v) = =[ (min(CMS(v)) max mean (CMS())), www.mmmeddmaa/mammm (CMM(())
(8)
As for the other proposed encodings, we investigate the expressivity of HCP. Note that ORC computed at the graph level is by itself very expressive, leading to LCP provably enhancing the expressivity of MPGNNs. In fact, there exist variants of ORC which can distinguish graphs that are not 3-WL. distinguishable (Southern et al. (003).. However, the same is not true for graph-level FRC. This merits a closer analysis of HCP where is chosen to be the H-FRC.
Theorem 3.12. (HCP Expressivity). MPGNNs with HCP (k denoting H-FRC) are strictly more expressive than the 1-WL test and hence than MPGNNs without encodings. In contrast, leveraging LCP with standard FRC at the graph level does not enhance expressivity.
Proof. Consider the 4 by Rook and the Shrikhande graphs, which cannot be distinguished by the WL test for h < 3. All nodes in both graphs have identical LCP-FRC, namely [-8, 88 -8 -8, 0j. This is because all nodes have degree 6, consequently their FRC -8. However, when computing
HCP-FRC FRC on the lifted hypergraphs the curvatures differ: In the Rook graph, all nodes have HCP-FRC

---

[0, O, O, O, 0), whereas in the Shrikhande graph all nodes have HCP-FRC [-12, -12, -12 12, (see Apx. F.T. Furthermore, it is possible to find non-isomorphic graphs with the same LCP, but different HCP (even up to scaling): Pair 0 of the "Basic" category in BREC is an example where both graphs have the same ICP, but different HCP (even up to scaling) (see Apx. F.2 for additional details).
Remark 3.13. (HCP Complexity). Computing the H-FRC and hence the HCP-FRC scales as O(I (mmx)) where Émax denotes the size of the largest hyperedge. On the other hand, computing H-ORC incurs significant computational cost: The computation of the Wi-distance, which scales as (FFlemax) introduces a significant bottleneck. Hence, HCP-FRC has significant scaling advantages over HCP-ORC.
3.4 Local Degree Profile
Lastly, we define hypergraph--evel notion of Local Degree Profiles (LDP) (Cai & Wang 2018).
which captures structural information encoded in the node degree distribution over a node's ' 1-hop neighborhood. We consider the multi-set of node degrees in the 1-hop neighborhood of node v, i.e. DN = {du/u E No and define
LDP(v)= = [d.; min(DD(vv) max(DN(u)) mean(DN())), (Dd)an(DN(()))........) (tN()) (9)
An analogous notion on the hypergraph level (H-LDP) can be defined by a simple extension. Again, H-LDP exhibits improved expressivity:
Theorem 3.14. (H-LDP Expressivity). MPGNNs with H-LDP are strictly more expressive than the 1-WL test and hence than MPGNNs without encodings. There exist graphs which can be distinguished using H-LDP, but not using LDP.
Proof. The 4 by 4 Rook graph and the Shrikhande graph cannot be distinguished by LDP, as all nodes the same degree, resulting in LDPs [6, 6, 6, 6, 6, O]. However, they can be distinguished using H-LDP: The nodes in the Rook graph have H-LDP [2, 2,
0J. the nodes in the Shrikhande graph [6, 6, 6, 6, 6, 0] (see Apx. F.I. Furthermore, it is possible to find non-isomorphic graphs with the same LDP, but different H-LDP even up scaling: Pair 0 of the "Basic" category in BREC is an example, where both graphs have identical LDPs, but different H-LDPs, even to scaling. For more details, see Fig. and Apx.
F2
Remark 3.15. (H-LDP Complexity). Computing H-LDP scales O( (mmxx) We only need to count the degree for each node and save the statistics of I-neighborhood for each node. Remark 3.16. We observe that in the examples demonstrating the enhanced representational power of HCP and H-LDP, the respective profiles are scalar multiples of each other. It is common in hypergraph architectures to normalize node attributes during preprocessing, which would obscure the structural differences captured by the two encodings. However, we emphasize that no such preprocessing is applied in our experiments.
4 Experiments
4.1 Experimental setup
Throughout all of our experiments, we treat the computation of encodings as a preprocessing step, which is first applied all graphs in the data considered. We then train GNN part of the preprocessed graphs and evaluate its performance on a withheld set of test graphs (nodes in the case of node classification). Settings and optimization hyperparameters are held constant across baseline models for all encodings, so that hyperparameter tuning can be ruled out as a source of performance gain. We obtain the settings for the individual encoding types via hyperparameter tuning. For all preprocessing methods and hyperparameter choices, we record the test set performance of the settings with the best validation performance. As there is a certain stochasticity involved, especially when training neural networks, we accumulate experimental results across 50 random trials. We report the mean test accuracy, along with the 95% confidence interval for the node classification tasks on hypergraph datasets in Tab. and for tasks on graph datasets in Tab. 2 3 10 11 12 and 13 For Peptides-func, we report average precision and for Peptides-struct the mean absolute error (MAF).
Details on all datasets can be found in Apx.
7

---

Model (Encodings))
cisseer-CCCC)) (T)
cora-CA (f)
corn-CC(1)
pubmed-CC(() (*)
DELP (1)
GCN (No Encoding)
09.28 + 0.28
76.51
+ 0.82
75.43
0:26
84.66
0.49
75.66 + 0.S1
GCN (HCP-FRC)
71.03 + 0.51
T8.43
+ 0.76
76.61 + 0.811
84.78
0.57
76.49 + 0.90
GON (HCP-ORC)
0.54
0.70
85.12
0.8G
GCN (--19-
68.63
0.71
84
0.60
75.92
0.28
24 + 63
76.18 + 0.88
GCN (EN II- 19 RWPE)
68.85
0.91
17.19
1: 0.64
75,33
0.35
56.33 1 0.681
76.76 0.84
GON (Hodge H-20-LAPE)
69.61 0.45
0.85
0.31
50.06
0.62
77
0.93
GCN (Norm, H-20-LAPP))
63.13
0.77
78.13
0.79
76.18
0.29
85.78 = 0.65
76.92 0.88
UaiGIN (No Emcoding)
63.36 1.76
75.72
1.16
71.10
1.37
75.32
1.09
71.05 +
UsiGCN (HCP-FRC)
61.20 + 1.83
74.64
+ 1.45
66.98 + 1.59
67.37
1.78
71.02 + 1.43
UniGIN (HCP-DRC)
61.81 + 1.70
75.03
+ 1.33
70.42
1.17
71.64
1.52
70.69 + 1.62
UniGCN (EE 11-1--WWEE))
1.52
74.61
1.18
UnicICN 19
63.09
1.62
75.30
1.37
71.21
1.34
74.61
1.00
71.26 + 1.47
UniGIN (Hodge A-P0-L-APE)
63.46 + 1.58
76.64 + 1.37
71.31
1.19
75.37
1.01
70.71
+ 1.61
UniGCN (Nom.. 11-2-LAPPE)
63.41 1.61
75.55
+ 1.48
71,20
1.24
75.30
1.01
71.10 1 1.33
Table I: GCN and UniGCN performance hypergraph datasets with different hypergraph encodings. We report mean accuracy and standard deviation over 50 runs. In our tables, the best value is in bold and the second best in blue. In case of overlap, we underline. For example, for citeseer-CC, GCN (HCP-ORC) is underlined because it is the tied best model-encoding pair, up to 0.51 accuracy (the accuracy of the best pair GCN (HFC-FRC)).
Model (Envadings)
Collab (1)
Imdb
Reddit (f)
Peptides-
Peptides-s (L)
OCN (No Encoding)
61.94 + 1.27
48.10 + 1.02
67.87 # 1.38
0.532 0.005
0.266 0.002
GCN (LCP-FRC)
68.36 1.13
63.42
+ 1.47
79.53
0.537
0.006
0.261 0.003
GUN (LCPPORC)
70.48 0.97
67.93
+ 1.55
50.76
1.54
0.561
+ 0.006
0.262 4: 0. 0..004
OCN (19-RWPF)
49.63 2.38
50.41
+ 1.26
78.93
1.60
0.538
0.007
0.265 0.003
GCN (20-LAPE)
58.33 1.64
48.82
1.31
77.26
0.006
0.003
GEN (HCF-HRC)
72.03 0.61
64.64 + 0.88
0.58
0.669
0.004
0.255 00.
OCN (HCP--RRC)
70.82 0.66
66.16 + 0.75
60.35
0.72
0.659
0.004
0.258 0.003
OCN (EE (9-RWP))
69.63
1:0:::000 0.71
73.96
1 0.65
82.79
1 0.62
0.546
1 0.006
0. 0,263 1: 0.003
GCN 18-19-WWPE]
68.85
0.91
0.48
0.79
0.005
U.263 0.003
GCN (Hodge H-20-LAPP))
60.61 + 0.45
71.38 : 0.75
79.46
18787 0. 0.005
0.254 008
OCN (Norm. 11-20-LAPE)
09.13:10.77
71.05
1 0.82
50.06
0.67
0.557 1 0.008
0.253 1 0 003
Table 2: GCN performance with graph level encodings (top) and hypergraph level encodings (bottom). We report mean and standard deviation across 50 runs.
4.2 Comparison of Hypergraph- and Graph-level Architectures
We begin by comparing the utility of our encodings for message-passing architectures that operate at the graph at the hypergraph level. Hypergraph neural networks predominantly used for node classification in hypergraphs. In fact, we are not aware of hypergraph classification datasets analogous to the graph datasets used in the previous subsection. As such, we choose five common hypergraph node classification datasets: Cora-CA, Cora-CC, Citeseer, DBLP, and Pubmed. We use clique expansion to convert these hypergraphs into graphs (empirically, we found this be the best performing expansion see Apx. A. and train GCN on them with either no encoding or one of our hypergraph encodings. As a hypergraph-level message-past paaagggg architecture, we use UniGCN (Huang & Yang. 2021). Additional experiments with UniGIN, UniGAT, and other architectures are presented in Apx. G along with a detailed explanation of the clique expansions we use.
Graph-level message-passing Benefits from Hypergraph-level Encodings. sented in Tab. [ Somewhat surprisingly. we note that even on these datasets, which are originally hypergraphs, GCN with no encodings outperforms UniGCN. Perhaps even more surprising, UniGCN does not seem to benefit from any of the encodings provided. Apx. G shows that the same holds true for UniGIN and UniGAT. GCN on the other hand clearly benefits from (most) hypergraph-level encodings, although admittedly less so than when used for graph classification. Previous work has reported similar differences in the utility of encodings for graph and node classification tasks. Overall, we take our results this subsection and in Apx. Glas as evidence that our proposed hypergraph-level encodings present a strong alternative to established message-passinn passing architectures at the hypergraph level.
Our results are pre-
4.3 Hypergraph-level Encodings Capture Higher-order Information Effectively
We now evaluate to what extent our hypergraph encodings can be used for datasets that are originally graph-structured We lift these graphs to the hypergraph level (see. Apx. A.2 for details) and compare
8

---

Model (Kneodings)
Reddit (t)
Enzymes (1)
Proteins (1)
Pepdides-f (t)
Peptides- (U)
GPS (So Enceding)
80,94 + 1.42
46,853 + 1.14
74.10
0.98
0.593 0.009
0.262
0.003
GFS (LCF-TRC)
80.53 1 1.55
43.75 1 1:39
13:35
1.07
0.598
0.010
0.257
0,003
GPS (LCI--ORC)
82.83
1.47
48.31
74.88
1.20
0,613
0.010
0,252
003
GPS (19 RWPE)
81.92
1.31
51.09
1: 1.64
71.92
1.18
0.394
0.011
0.257
0.003
GPS (20-LAPE)
82.05 + 1.29
42,90 + 1.36
71.46
1:25
0.699 + 0.011
0.253 + 0.003
GPS (HCP-FRC)
81.68 + 1.16
47.66 + 0.92
74.50 = 1.13
0.604 + 0.010
0.254 + 0. 0.003
GPS ORCC)
1.24
48.19
74.32
606 0,010
0.254 004
GPS (EE PE)
84.04 + 1.07
61.83
+ 1.07
76.08
1.14
0.616 + 0.009
0.261
0.003
GPS (EN H: JWW PE)
84.25 +: 1.13
51.28
1.12
74.82
1:11
0.017 0.010
0.252 0.003
GPS (Hodge H-20-
1.21
78.95
0.602 0.030
0.252
GPS (Norm, HH-20-LAPE)
83. 2 1.18
47.78
1 0.98
74.03 = 10
0. 604 1 0.010
0.254 0. 0.002
Table 3: GPS performance with graph level encodings (top) and hypergraph level encodings (bottom). We report mean and standard deviation across 50 runs.
against encodings computed at the graph level. Tables 2 GPS, respectively; additional results with GIN can be found in Apx. D
10 and 3
report results for GCN and
Performance Gains with Hypergraph-level Encodings. We note several things: 1) adding encod- ings is beneficial in nearly all scenarios, 2) encodings computed the hypergraph level are always at least as beneficial as their cousins computed at the graph level (e.g. H-RWPE is at least as useful as RWPE), and 3) on social network datasets (Collab, Imdb, and Reddit), hypergraph encodings provide the largest performance boosts, often by wide margin. This aligns with our intuition, as social networks can often naturally thought of as hypergraphs.
Positional vs Structural Encodings. Our results with GPS confirm our observations with GCN. Hypergraph-level encodings significantly boost performance on almost all datasets (only Proteins is not statistically significant) and are generally more useful than their graph-level analogues. Further, while GCN usually performed best with local structural encodings such as the Local Curvature Profile, GraphGPS seems to benefit more from global positional encodings such as (Hypergraph-) Random Walk Positional Encodings. This aligns with previous findings in the literature using graph-level encodings (Fesser& & Weber 2024a)..
Utility beyond Weisfeiler-Leman Our previous results on the BREC dataset indicate that much of the utility of our hypergraph-leve encodings can perhaps be attributed to improving the expressivity of GCN and GPS. To better quantify this, we run an additional suite of experiments on the Collab, Imdb, and Reddit datasets using the GIN. As noted previously, GIN is provably as powerful as the 1-WL test and therefore more expressive than GCN. Our results in Apx. Apx.Dishor show that GIN has indeed a higher baseline accuracy (without encodings) than GCN, and benefits significantly less from encodings than both GCN and GPS. Nevertheless, our hypergraph- boost performance. We take this as evidence that providing information from domains other than the computational domain (graphs in our setting) provides benefits beyond increased expressivity.
encodings significantly
5 Discussion
In this study, we proposed hypergraph-level encodings as an approach for leveraging higher-order relational information. Our results show that combining hypergraph encodings with graph-level architectures leads to enhanced representational power and significant performance gains in "multi- way"" relational learning tasks.
Lessons for Model Design. Our study is motivated by the observation that graph-level architectures applied to a hypergraphs' clique expansions frequently outperform hypergraph-Ieved architectures, even when the inputs naturally parametrized hypergraphs. While hypergraph-leve encodings do not significantly enhance the performance of hypergraph architectures, they can lead to substantial performance gains when used in graph architectures. Notably, random balk- (H-A-RWPE) and curvature- based encodings (HCP) are particularly effective across data sets. These findings suggest a augmer
graph-level architecture augmented with hypergraph-level encodings suitable model choice for higher-orde order learning tasks.
Limitations. A key limitation of this study, and many of the related works, is lack of benchmarks consisting of true hypergraph-sttruture data, Many of the existing data sets consists of graphs that are reparametrized ("lifted"") to hypergraphs, hypergraphs that can be casily reparametrized

---

as graphs. This suggests the establishment of better benchmark key direction for future work. Given the promise of topologiaal deep learning for scientific machine learning, we envision future benchmarks that are based on scientific data, where multi-way interactions are known to arise naturally GGarcia-Chung et al. 2023: Gjorgjieva et al., 2011). Another limitation of this study arises in the choice of hypergraph architectures. While our selection was guided by cop-performing models in recent benchmarks (Huang Yang 2021; Telyatnikov et al. (2024), a more comprehensive analysis could further strengthen the validity of the reported observations.
Other Future Directions. Despite the aforementioned caveats regarding datasets and the breadth of architectures included in this study, our observations raise questions about the effectiveness of existing pessage-passingg schemes on hypergraphs. We believe that a thorough analysis of these architectures" ability to effectively encode higher-order information into learned representations is an important direction for future work. A possible lens for such an investigation could be graph reasoning tasks, as previously suggested in (Luo et al. 2023).
Additionally, the negative results observed regarding hypergraph--evel encodings paired with hypergraph-level architectures warrant further exploration. Specifically, understanding how to effec- tively augment hypergraph inputs with structural and positional information that be leveraged by hypergraph-level architectures is a promising direction for further study.
Lastly, while this study primarily focused hypergraph learning, there several other topological domains of interest, including simplicial complexes, polyhedral complexes, and more general CW complexes. Extending the present study these domains represents another interesting avenue for further investigation.
6 Broader Impacts
This paper presents work whose goal is to advance theoretical understanding of Machine Learn- ing. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Acknowledgments
LF was supported by a Kempner Graduate Fellowship. MW was partially supported by NSF award CBET-21 12085 and DMS- 2406924 and an Alfred P. Sloan Research Fellowship in Mathematics. Some of the computations in this paper were run on the FASRC Cannon cluster supported by the FAS Division of Science Research Computing Group at Harvard University.
References
Ames, B. N., Durston, W. E., Yamasaki, E., Lee, D. (1973). Careinogens are mutagens: a simple test system combining liver homogenates for activation and bacteria for detection. Proceedings of the National Academy of Sciences, 70(8), 2281-2285.
Banerjee, (2021). On the spectrum of hypergraphs. Linear algebra and applications, 614, 82-110.
Benson, A. R., Gleich, D. F., & Higham, D. J. (2021). Higher-order network analysis takes off, fueled by classical ideas and new data, arXiv preprint 1.X0022003.00031.
Bick, C., Gross, E., Harrington, H. A., & Schaub, M. T. (2023). What are higher-order networks? SIAM Review, 65(3), 686-731.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., & Kriegel, H.-P. (2005). Protein function prediction via graph kernels. Bioinformatics, 21(suppl 1), i47-i56.
Bouritsas, G., Frasca, F., Zafeiriou, S., & Bronstein, M. M. (2022). Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1), 657-668.
10

---

Cai, C. & Wang, Y. (2018). A simple yet effective baseline for non-attributed graph classification. arXiv preprint Xrviv: 1811.0350
Chen, M., Wei, Z., Huang, Z.. Ding, B., & Li, Y. (2020). Simple and deep graph convolutional networks. In International conference on machine learning (pp. 1725-1735):: PMLR.
Coupette, C., Dalleiger, S., & Rieck, B. (2022). Ollivier-ricci curvature for hypergraphs: A unified framework. arXiv preprint arXiv:2210. 12048.
Debnath, A. K., Lopez de Compadre, R. L., Debnath, G., Shusterman, A. J., & Hansch, C. (1991). Structure-activig relationship of mutagenic aromatic and heteroaromatic nitro compounds. correla- tion with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2), 786-797.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2023). Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43), 1-48.
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2021). Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875.
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., & Beaini, D. (2022). Long range graph benchmark. Advances in Neural Information Processing Systems, 35, 22326-22340,
Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33 (pp. 3558-3565).
Fesser, L., de Haro Ivánez, S. S., Devriendt, K., Weber, M., & Lambiotte, R. (2024). Augmentations of forman's 's ricci curvature and their applications in community detection. Journal of Physics: Complexity, 5(3), 035010.
Fesser, L. & Weber, M. (2024a). Effective structural encodings via local curvature profiles. In International Conference on Learning Representations.
Fesser, L. Weber, M. (2024b). Mitigating over-smoothing and over-squashing using augmentations of forman-ricci curvature. In Learning on Graphs Conference (pp. 19-1).: PMLR.
Forman, R. (2003). Bochner's method for cell complexes and combinatorial Ricci curvature. Discrete and Computational Geometry, 29(3), 323-374.
Garcia-Chune A., Bermúdez-Montafia M., Stadler, P. F., Jost, J., & Restrepo, G. (2023). Chemically inspired erd (h {o} sr' enyi oriented hypergraphs. arXiv preprint (xXii:2309006551.
Gjorgjieva, J., Clopath, C., Audet, J., & Pfister, J.-P. (2011). A triplet spike-timing deependenndeeeee plasticity model generalizes the bienenstock- coopeee--roooooe-mmuuooooooooo rule to higher-order spatiotemporal correlations. Proceedings of the National Academy of Sciences, 108(48), 19383-19388.
Gori, M.. Monfardini, G., Scarselli, (2005). A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, volume 2 (pp. 739-734).
Hagberg, A., Swart, P. J., & Schult, D. A. (2008). Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States).
Hajij, M., Papillon, M., Frantzen, F., Agerberg, J., AlJabea, I., Ballester, R., Battiloro, C., Berárddz,, G., Birdal, T., Brent, A., et al. (2024). Topox: a suite python packages for machine learning on topological domains. Journal of Machine Learning Research, 25(374), 1-8.
Hajij. M., Zamzmi, G., Papamarkou, T., Miolane, N., Guzmán- Sáenz, A., & Ramamurthy, K. N. (2022). Higher-order attention networks. arXiv preprint arXiv:2206. 2et.:22060000666, 2(3), 4.
Hamilton, W., Ying, 7., Leskovee, J. (2017). Inductive representation learning on large graphs.
Advances in neural information processing systems, 30.

---

Huang, J. & Yang, J. (2021), Unignn: unified framework for graph and hypergraph neural networks. arXiv preprint arXiv:2105.00956.
Kim, S., Lee, S. Y., Gao, Y., Antelmi, A., Polato, M., & Shin, K. (2024). A survey on hypergraph neural networks: An in-depth and step-by-step guide. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 6544).
Kipf, T. N. & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprini arXiv:1609.022
Klamt, S., Haus, U.-U., & Theis, F. (2009). Hypergraphs and cellular networks. PLoS computational biology, 5(5), e1000385.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., & Tossou, P. (2021). Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34,
Leal, W., Restrepo, G., Stadler, P. F., & Jost, J. (2021). Forman-rices curvature for hypergraphs. Advances in Complex Systems, 24(01), 2150003.
Liu, Z., Tang. B., Ye, Z., Dong, X., Chen, S., & Wang, Y. (2024). Hypergraph transformer for seni-supereised classification. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 7515-7519).: IEEE.
Luo, Y., Shi, L.,, & Wu, X.-M. (2024). Classic gnns are strong baselines: Reassessing gnns for node classification. Advances in Neural Information Processing Systems, 37, 97650-97667
Luo, Z., Mao, J.. Tenenbaum, J. B., & Kaelbling, L. P. (2023). On the expressiveness and generaliza- tion of hypergraph neural networks. arXiv preprint arXiv:2303.08 05490.
Mulas, R., Kuehn, C., Böhle, T., & Jost, J. (2022). Random walks and laplacians on hypergraphs: When do they match? Discrete Applied Mathematics, 317, 26-41.
Ollivier, Y. (2007). Ricci curvature of metric spaces. Comptes Rendus Mathematique, 345(11), 643-646.
Papillon, M., Sanborn, S., Hajij. M., & Miolane, N. (2023). Architectures of topological deep learning: A survey on topological neural networks. Arxiv. Submitted to Transactions on Pattern Analysis and Machine Intelligence.
Praggastis, B., Aksoy, S., Arendt, D., Bonicillo, M., Joslyn, C., Purvine, E., Shapiro, M., & Yun, J. Y. (2023). Hypernetx: A python package for modeling complex network data as hypergraphs. arXiv preprint arXiv:2310.11626
Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., Beaini, D. (2022). Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35, 14501-14515.
Rossi, R. & Ahmed, N. (2015). The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI conference on artificial intelligence, volume 29.
Saucan, E. & Weber, M. (2019). Forman's ricci curvature-from networks to hypernetworks. In Complex Networks and Their Applications VII: Volume I Proceedings The 7th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2018 7 (pp. 706-717): Springer.
Schaub, M. T., Zhu, Y., Seby, J.-B., Roddenberry, T. M., & Segarra, S. (2021). Signal processing on oigher-order networks: Livin' on the edge... and beyond. Signal Processing, 187, 108149.
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., & Eliassi-Rad, T. (2008). Collective classification network data. Al magazine, 29(3), 93-93.
Southern, J., Wayland, J., Bronstein, M. M., & Rieck, B. (2023). On the expressive power of ollivier-ricci curvature graphs.
12

---

Sun, L., Ji, S., & Ye, J. (2008). Hypergraph spectral learning for multi-label classification. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 666)676).
Telyatnikov, L., Bernardez, G., Montagna, M., Vasylenko, P., Zamzmi, G., Hajij, M., Schaub, M. T., Miolane, N., Scardapane, S., & Papamarkou, T. (2024). Topobenchmark: A framework for benchmarking topological deep learning.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks, arXiv preprinl arXiv: 1710.
Wang. P., Yang, S., Liu, Y., Wang, Z., & Li, P. (2022). Equivariant hypergraph diffusion neural operators. arXiv preprint wxXiv:2207.06680
Wang, Y., Gan, Q., Qiu, X., Huang, X., & Wipf, D. (2023). From hypergraph energy functions to hypergraph neural networks. In International Conference on Machine Learning (pp. 35605- 35623).: PMLR.
Wang. Y. Zhang, M. (2023). Towards better evaluation of gnn expressiveness with brec dataset.
arXiv preprint 204.42230..07702.
Wang, Y. & Zhang, M. (2024). An empirical study of realized gnn expressiveness. In Forty-first International Conference on Machine Learning.
Weisfeiler, B. & Leman, A. (1968). The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9), 12-16.
Xu, K., Hu, W., Leskovec, J. Jegelka, S. (2018). How powerful are graph neural networks? arXiv preprint arXiv: 1800000000
Yadati, N., Nimishakavi, M., Yadav, P., Nitin, V., Louis, A., & Talukdar, P. (2019). Hypergen: A new method for training graph convolutional networks on hypergraphs. Advances neural information processing systems, 32.
Yanardag, P. & Vishwanathan, S. (2015). Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 1365-1374).
Zhao, L., Jin, W., Akoglu, L., & Shah, N. (2021). From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint 10X0v:21
Zhou, D., Huang, J., Schölkopf, B. (2006). Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19.
13

---

A Extended Background
A.1 Hypergraph Expansions
There exist several expansion techniques for reparametrizing hypergraphs as graphs. Here, we focus clique expansion, which empirically found to be the best performing expansion. For more details see, e.g., (Sun et al. 2008).
To reparametrize hypergraph и (V, F) graph via clique expansion, we define G (V, X, E) where = (HK,,, Ce, P}. An example is given in Fig. 2
Original Hypergraph
Ciique Expansion
Figure 2: Example of clique expansion of hypergraph graph. The plots are created using NetworkX (Hagberg et al. 2008) and HyperNetX (Praggastis et al. 2023).
A.2 Lifting graphs hypergraphs
The term "lifting" refers generally to the reparametrization of one topological domain to another, usually one that captures richer higher-order information. In our setting we lift graphs to hypergraphs by adding hyperedges to groups of nodes that are pairwise interconnected. An example of lift of graph to hypergraph shown in Fig
Hypa gi Representciinn
Figure 3: Lifting of graph to hypergraph.
A.3 Weighted-Edges (WE) Hypergraph Random walks
We define Weighted-Edgee Random Walks (WE), which induce the following measure
w (i + j), if N
M WF (i)
(10)
otherwise
where N2 are the neighbors of and transition probabilities are given by
PWE (i + +
Σ
(11)
Eueen (Ifl -1)
(eHli)Se))
14

---

The probability of picking a hyperedge is directly proportional to the number of nodes in the hyperedge minus
A.4 Laplacians
Several notions of Laplacians have been studied on hypergraphs. In this work, we consider two types of Laplacians on graphs for implementing H-LAPE, the Hodge-Laplacian, with we defined in the main text, and the normalized Laplacian, which we discuss below. Additionally, we comment on random walks hypergraphs Laplacians. However, since they need be symmetric, there are not suitable for use in H-LAPE. Nonetheless, their spectrum provides an additional means for defining structural encodings.
A.4.1 Normalized graph and hypergraph Laplacian
For graphs, the symmetrically normalized graph Laplacian is defined as
I AD, D.
DD,
(12)
where L = D. - A is the standard graph Laplacian.
The normalized hypergraph Laplacian Zhou et al. 2006 Feng et al. 2019 is defined
- A=1-D;""B,; where Dy and De are the diagonal node and edge degree matrices. The Dirichlet energy E(f) of scalar function hypergraph is defined
= (D, - B,D.'
(13)
f(v) 2 Vilu)) v((v)
E(J) = -
f(u)
(14)
lel
eE {u,o]Ce
The normalized hypergraph Laplacian satisfies
-
(15)
which establishes that the normalized hypergraph Laplacian is positive semi-definite (Zhou et al. 2006). The smallest eigenvalue of A
A.4.2 Random walks hypergraph Laplacians
D,'A,, where, as usual, Dr denotes For graph, the random walk Laplacian is defined as I, -------- the degree matrix and A the adjency matrix. The probability of a random walk transitioning from node to j is given by LLn = 4.. Mulas et al. (022) introduce a generalized auddomwalk Laplacians on hypergraphs: For any random walk on a hypergraph, they define in analogy to the graph case
1 iff
Laj
(16)
1-P(i++)
This random walk notion is equivalent the EE scheme in Coupette al. (2022). defined in the main text: Starting at choose one of the hyperedges containing with equal probability. then select any of the vertices of the chosen hyperedge (other than v)) with equal probability. Formally, we write
Aij
Pi( j)
(17)
D
A similar notion was previously studied in [Banerjee] 202T)
Note that the random-wall Laplacian need not be symmetric. As result, is not suitable for defining H-LAPE. However, in some recent works, the spectrum of the graph Laplacian, rather than its eigenvectors, have been used SE (Kreuzer et al. [20T]. An analogous notion can be defined at the hypergraph level, which we term Hypergraph Laplacian Structural Encoding (H-LASE). We analyze the expressivity of such SEs, establishing that they provably more expressive than the 1-WI. test/ MPGNNs.
15

---

Theorem A.1. (H-LASE Expressivity). MPGNNs with H-LASE are strictly more expressive than the 1-WL test and hence than MPGNNs without encodings. Further, there exist graphs, which can be distinguished using H-LASE, but not using standard, graph-level LASE.
Proof. Consider the 4 by Rook and Shrikhande graphs: the two graphs are isospectral using the Normalized, Random Walk and Hodge Laplacians. But the two graphs's 's liftings to hypergraphs not isospectral for the Normalized Laplacian. D.
A.5 Discrete Curvature
Forman's curvature. Forman 2003)
proposed curvature definition on CW complexes, which derives from a fundamental relation between Ricci curvature and Laplacians (Bochner- Weizenböck identity). For simple, undirected, and unweighted graph G = (V, X, F.), the Forman-Ric curvature (FRC) of an edge {u, v)
E is given by:
FR(u, v) 4 deg(u) deg(v).
The edge-based Forman curvature definition be extended to capture curvature contributions from higher-order structures. Incorporating cycle counts up to order (denoted as AFx) has been shown to enrich the utility of the notion. Setting k = 3 and k 4, the Augmented Forman-Ricct curvature given by
AF) 4 deg(u) u) deg(v) (v) + +3A(u, v) AF) = - deg(u) - deg(v) + 32 (u, v) + 20 u),
where Auu, v) and (u, v) represent the number of triangles and quadrangles containing the edge {u, v). Prior work in the graph machine learning literature has demonstrated the effectiveness of these notions, e.g., (Fesser & Weber [2024b] Fesser et al. 2024). To the best of our knowledge, characterizations of such higher-order information via hypergraph curvatures have not been previously studied in this literature.
Ollivier's curvature. We also consider the Ollivier-Ricci Curvature (ORC), a notion of curvature on metric spaces equipped with probability measure (Ollivier (007)) On graphs endowed with the shortest path distance .), the ORC an edge { is defined as
Wi Wi M4)
x(i.j)
(18)
d(i,j)
where W, denotes the Wasserstein distance, Recall that, in general, Wi(s) between two probability distributions μ1, M2 is defined as
/ d(x, v)((x, y) da dy
W (1(1 inf
(19)
mET())))))
where T(11, is the set of measures with marginals /41, /42- In our case, the measures are defined by uniform distribution
the 1-hop neighborhoods of the nodes i and j.
Remark A.2. (ORC in a general setting). As noted in (Southern al. (023), the ORC can be defined in more general setting on graphs, where the metric d does not have to be the shortest- path distance. Furthermore, the probability measures need not uniform probability measures in the 1-hop neighborhood of the node. This is shown to be beneficial in distinguishing 3-WL. indistinguishable graphs using the ORC computed with respect to measures induced by m-hop random walks where > 1.
16

---

B
Architectures
Architecture
Type
Level
U pdate Function
x (D-12Ab-1/xx''")
GCN KKipf & Welling 2016
MP
graph
1= A+
Du -2,Ay
GIN
Xu al.
2018
MP
graph
x1+ MI.' (11 (1+c)x* + AX
x gl+ GPS' GPS' (x', E.,A) A)
XM g = MPNN, (X), E A)
GPS Rampfikk al.
2022
hybrid (MP, GT)
graph
X GlobalAtti (X-)
xl+1 MLP(X + X
UniGCN Huang & Yang 2021
MP
hypergraph
8/-1 V4, EiER, J.. w
UnIGIN Huang Yang
2021
hypergraph
2/11 w (a+ ejal Deen, 1
=0 (a" [wiNit] wh) explaie
UniGAT (Huang Yang 2021
MP
hypergraph
a EPER, "y
# EeED, a.1 1--
AGE (Huang Yang
hypergraph
a/+1
w (x)) + (GGREGATE((AE )OEE,))
# 2,ي. EecE, VE
UniGCNII Huang & Yang. 2021
MP
hypergraph
2/th = (a1 - B)1 aw!) (a- + aa?)
where and hyperparaneters
HGNN Feng
2019
MP
hypergraph
x
1/, B. D x' W!)
y = ReLU (1- Rauaaa""aaaaa--""
PhenomNN Wang al. 2023
MP
hypergraph
where 8 = f(X; w + Ao
(L, y
Table 4: Overview of Architectures. W represents a trainable weight matrix for layer 1. e represents learnable parameter. We use matrix notation except for Huang & Yang (202I) where we use vector notation.
B.1
GNN architectures
B.1.1
GCN
GCN extends convolutional neural networks graph-structured data. derives a shared representa- tion by integrating node fcatures and graph connectivity through message-passee Mathematicallyy GCN layer is expressed as
X = x -0 (D=1"A--1D-11""""""
where W' the learnable weight matrix at layer 1, and --1/2 AD- 1/2 is the normalized adjacency matrix of the original graph with added self-loops. This graph has adjacency matrix À = A + IN and node degree matrix D. The activation function a is typically chosen as ReLU or a sigmoid function.
B.1.2 GIN
GIN is message-passing graph neural network (MPGNN) designed for maximum expressiveness, meaning it can learn a broader range of structural patterns compared to other MPGNNs like GCN. GIN is inspired by the Weisfeiler-Leman (WL) graph isomorphism test. Formally, the GIN layer is
given by
zt+1 MMLP'
(L+ xt
Σ 1
(20)
JENr
17

---

where o denotes the feature of node at layer 1, NS represents the neighbors of node i, and is learnable parameter. The update step is carried out using multi-layer perceptron MLP(-). which is fully connected neural network.
B.1.3 GraphGPS
GraphGPS is a hybrid graph transformer (GT) model that integrates MPGNNs with transformer layers effectively capture both local and global patterns in graph learning. It enhances standard GNNs by incorporating positional encodings (which provide node location information) and structural encodings (which capture graph-theoretic properties of nodes). By alternating between GNN layers (for local aggregation) and transformer layers (for global attention), GraphGPS can efficiently model both short-range and long-range dependencies in graphs. It employs multi-head attention, residual connections, and layer normalization to maintain stability and improve learning performance. Mathematically, GraphGPS updates the node and edge features as follows:
x El GPS (X', A),
computed as:
x E++1 MPNN (x', EE,AA M
x GlobalAttn (x!),
x MLP(X + +x 1)-1)-
where MLP(-) is a 2-layer Multi-Layer Perceptron (MLP) block. Note that we omit the batch normalization in this exposition.
B.2 HNN architectures
Models on the hypergaph-level domain are approaches that preserve the hypergraph structure during learning (Kim al. 2024). [Huang & Yang (202T) proposes UniGCN, UniGIN, UniGAT, Uni and UniGCNII, which directly generalize the classic GCN, GIN, GAT (Veličković et al. (011)) and GraphSAGE (Hamilton et al., (017)) and GNCII (Chen al. 2020). We also study PhenomNN Wang ct al. (2023) and ED-HNN et al. (2022).
B.2.1 UniGCN
UniGCN follows the two-phase scheme (described in 2.1 and sets the second aggregation function Φ2 to
w w4b
(21)
Vd,
de
BEE;
where W is trainable weight matrix, d, = Eie (d: + 1) is the average degree of an hyperedge
(after adding self-loops to the original hypergraph), and where N₁ and Et) are the neighborhood of vertex and the incident hyperedges to after adding self loops.
B.2.2 UniGIN
UniGIN also follows the two-phase scheme and sets the second aggregation function Φ2 to be
(a+e)ot
2/11-W
Σ M+41 ee
(22)
18

---

B.2.3 UniGAT
UniGAT adopts an attention mechanism to assign importance score to each of the center node's neighbors (Huang Yang 202T). The attention mechanism formulated as
1+1 aa" explo 1+1)
[ W w'(+1)) ))
(23)
al+1
(24)
le
EvEE, exp(a
E die
(25)
eEE.
B.2.4
UniSAGE
UniSAGE follows the two-phase scheme and sets the second aggregation function Φ2 to be
x!
W' + AGGREGATE(( (1+(t) JOEF, -))
(26)
B.2.5
UniGCNII
UniGCNII updates node features using:
141 ++1 ((1 (11-8)T (w") - a) + +ax.)
8/11 d. eEE,
(27)
(28)
where a and are hyperparameters.
B.2.6 HGNN
HGNN (Feng et al. 2019) utilizes the normalized hypergraph Laplacian 13 which expands the hypergraph to graph via elique expansion. HGNN also follows the two-phase scheme (described in Using non-linear activation the HGNN layer update is:
2.1
X(+ =0 (D. (D. BJ D, 122
(29)
where X X.
B.2.7 PhenomNN
PhenomNN Wang et al. 2023 is defined on a hypergraph H = (V, F)) with incidence matrix B1 E {0, 1} M node features X E xd and base predictor f(X; W) E glVixd and produces embeddings y e [ via
layers. Writing De R [[ for the hyperedge degree matrix, define the clique-expansion adjacency
Ac BB
De diag(Ac1)
= D. BT, D3 diag(As1).
(30)
At iteration I, let
Y Ac AcY (Ho + H Dc Y Hollo
(31)
1 As Y (HI +HH) D3 y' H111,
(32)
where Hg, H1 E Bdddd are learned compatibility matrices, and set ò = De Au + D3 X1 + I. Then
y++ R RCLURRLLLLL (1- + D - + f + (Ls yd V2))):
(33)
with step-size a, Laplacian Ls = D. As, and nonlinearity ReLU(Z)) (0, Z). Tying
(Ho, Hi, W, λo at across layers yields unrolled proximal-gradient descent that provably converges to the minimizer of a hypergraph energy while remaining implementable via standard mossage-passing primitives. We can re-express PhenomNN in the node-wise MP form:
19

---

u =a
Σ
vyW + s/w, + +aD f(x;; W)
(34)
JEN!
where No are the neighbors in the clique expansion graph, and:
W 4/ = a ai.;'' | |olAckk + H + A + H. -1] w (1 a) aD NolDoli, a + (M1
(35)
(36)
C Experimental details
C.1
Datasets
We consider multiple datasets commonly used for benchmarking in the literature, including social networks, chemical reaction networks, and citation networks.
C.1.1 Graph Datasets
Collab, Imdb and Reddit are proposed in (Yanardag & Vishwanathan 2015). Collab is a collection of ego-networks where nodes are researchers. The labels correspond to the fields of research of the authors. Imdb is also collection of ego-networks. Nodes are actors and edge between two nodes is present if the actors played together. The labels correspond to the genre of movies used to construct the networks. Reddit is collection of graphs corresponding to online discussion threads on reddit. Nodes correspond to users, who are connected if they replied to each other comments. The task consists in determining if the community is discussion-community community.
question answering
Mutag is collection of graphs corresponding to nitroaromatic compounds (Debnath et al. 1991). The goal to predict their mutagenicity in the Ames test (Ames et al. 1973) using S. typhimurium TA98.
Proteins and Enzymes are introduced (Borgwardt et al. 2005 These datasets use the 3D structure of the folded proteins to build graph of amino acids.
Peptides is chemical data set introduced in (Dwivedi et al. 2022 The graphs derived from peptides, short chains of amino acid, such that the nodes correspond to the heavy (non-hydrogen) atoms while the edges represent the bonds between them. Peptides-fune func is a graph classification task, with total of 10 classes based on the peptide function (Antibacterial, Antiviral, etc). Peptides-struct a graph regression task.
We outline basic characteristics of these datasets in Tab. 5
Collab
Imdb
Reddit
Mulag
Enzymes
Proteins
Peptides-fune
Peptides-struct
# graphs
5000
1000
2000
188
600
1113
15,535
15,535
avg. mode per graph
74.49
19.77
425.57
17.93
31.86
37.40
150.94
150.94
classes
3
2
10
Table 5: Dataset Statistics for Collab, Imdb, Reddit, Mutag, Enzymes, Proteins and Peptides.
C.1.2 Hypergraph Datasets
We use five datasets that naturally parametrized as hypergraphs: pubmed, Cora co-authorship (Cora-CA), cora co-citation (Cora-CC), Citeseer (Sen et al. 2008) and DBLP (Rossi & Ahmed 2015).
We use the same pre-processed hypergraphs as Yadati al. (2019), which are taken from Huang Yang (021)). The hypergraphs are created with each vertex representing document. The Cora data set, for example, contains machine learning papers divided into one of seven classes. a given graph of the co-authorship datasets Cora-CA and DBLP, all documents co-authored by one author form one hyperedge. In pubmed, citeseer and Cora-CC, all documents cited by an author from one hyperedge. We outline basic characteristics of these datasets in Tab. 6
20

---

Pubmed
Cora-CA
Cora-CC
Citeseer
DBLP
# hypemodes, V
19717
2708
2708
3312
43413
# hyperedges,
7963
1072
1579
1079
22535
# features, d
500
1433
1433
3703
1425
# classes,
7
6
6
Table 6: Dataset statistics.
We use these datasets in semi-supervised hypernode classification tasks, where the objective is to predict labels for test nodes given the hypergraph structure, node features, and limited number of training labels.
C.2 Hyperparameters
For GNNs.
We outline the hyperparameter used for Tab.
1 Tab.
Tab.
10 and Tab.
13
in Tab.
Tab.
Tab.
Features
citeseer-CC
Cora-CA
Cora-CC
Pubmed-CC
DBLP
Num. Layers
Hidden Dim.
128
128
128
128
128
Learning Rate
0.001
0.001
0.001
0.001
0.001
Dropout
0.2
0.2
0.2
0.2
0.2
Batch Size
50
Epochs
300
300
300
300
300
Table 7: Hyperparameter settings for Tab. (for GCN),
Features
Collab
Imdb
Reddit
Mutag
Enzymes
Proteins
Peptides-f
Peptides-s
Num. Layers
4
Hidden Dim.
64
64
64
64
64
64
235
235
Learning Rate
0.001
0.001
0.001
0,001
0.001
0,001
0.001
0.001
Dropout
0.5
0.5
0.5
0.5
0.5
0.5
0.1
0.1
Batch Size
50
50
50
50
50
Epochs
300
300
300
300
300
300
300
300
Table 8: Hyperparameter settings used for GCN for Tab. and 10
Features
Collab
Imdb
Reddit
MP-Layer
GIN
GIN
GIN
Num. Layers
4
4
4
Hidden Dim.
64
64
64
Learning Rate
0.001
0.001
0.001
Dropout
0.2
0.2
0.2
Batch Size
50
50
50
Epochs
300
300
300
Table 9: Hyperparameter settings for GIN for Tab. 13
For HNNs.
For the hypergraph architectures (Huang & Yang 2021)) )), we use weight decay of 0.0005, patience of 200 and 200 epochs. The learning rate is set to 0.01, the dropout to 0.6. The activation layer between UniConvs is relu. We add self loops to the (hyper-)graphs. The number of convolution heads The number hidden layers is 2. The parameters for PhenomNN are presented Tab. 27 and
the parameters for HGNN are presented in Tab. 29
21

---

D Additional GNN results
We include additional results with graph-level and hypergraph-level encodings with GCN (Tab. 10 and GPS (Tab. T
Model (Encodings)
Enzymes (1)
Proteins (t)
GCN (No Encoding)
28.03 + 1.15
71.48 = 0.90
GCN (I.CP-FRC)
27.66 + 1.48
70.89 + 1.16
GCN (LCP-ORC)
33.17 + 1.43
74.22 + 1.77
GCN (19-RWPE)
30.66 + 1.78
71.94 = 1.58
GCN (20-LAPE)
28.52 + 1.16
71.46 =: 1.52
GCN (HCP-FRC)
30.87 + 1.38
71.27 = 1.20
GCN (HCP-ORC)
32.83 + 1.36
73.78 + 1.25
GCN (EE H-11-RWPE)
31.74 1 1.30
73.83 1 1.08
GCN (EN H-19-RWPE)
30.93 1 1.27
74.05 1 1.13
GCN (Hodge H-20-LAPE)
29.46 1.14
72.89 1 1.31
GCN (Norm. H-20-LAPE)
29.60 1.21
73. 12 + 1.36
Table 10: GCN performance with graph level encodings (top) and hypergraph level encodings
(hottom). We report mean and standard deviation across 50 runs.
Model (Encodings)
Collab (f)
Imdb (t)
GPS (No Encoding)
74.17 1.33
70.93 + 1.21
GPS (LCP-FRC)
74.22 + 1.27
71.46 + 1.77
GPS (LCP-ORC)
74.52 1.18
71.84 1.26
GPS (19-RWPE)
74.29 1.42
66.40
1.53
GPS (20-LAPE)
74.74 + 1.23
70.67 + 1.18
GPS (HCP-FRC)
73.37 1.59
71.48 1.03
GPS (HCP-ORG
74.18 + 1.22
72.05
1.15
GPS (EE H-19-RWPE)
76.19 + 1.29
73.19
1.07
GPS (EN H-19-RWPE)
75.92 1.33
73.08
1.24
GPS (Hodge H-20-LAPPE)
76.10 1.16
73.15
1.02
GPS (Norm. H-20-LAPE)
75.81 1 1.21
1 1.18
Table 11: GPS performance with graph level encodings (top) and hypergraph level encodings (bottom). We report mean and standard deviation across 50 runs.
We include additional results with graph-level and hypergraph-level encodings on the Mutag dataset with GCN and GPS (Tab. 12) and on the social networks Collab, Imdb, and Reddit using GIN (Tab. 13p.
Encodings
GCN (1)
GPS (1)
No Encoding
65.96 1.76
80.40 1.53
LCP-FRC
67.04 1.49
83.94 1.94::20 2.06
LCP-ORC
83.09 1.71
84.93 : 1.82
19-RWPE
71.75 + 2.08
80.13 1113:1 1.65
20-LAPE
73.30 + 1.95
82.27 + 1.57
HCP-FRC
80.85 1.77
89.36 1.68
EE H- 19-RWPE
85.32 1.63
88.65 1 2.24
EN H- 19-RWWE
82.34 + 2.68
88.49 + 2.12
Hodge H-20-LAPE
83.66 1.90
86.72 + 1.96
Norm. H-20-LAPE
81.68 1.79
86.90 1.81
Table 12: GCN and GPS performance on the Mutag dataset with various graph and hypergraph encodings. We report mean and standard deviation across 50 runs.
22

---

Model (Encodings)
Collab
Imdb (1)
Reddit (1)
GIN (No Encoding)
67.44 + 1.13
67.12 + 1.36
75.38 + 1.27
GIN (LCP-FRC)
71.96 1 1.30
70.18 + 1.44
69.66 1 1.62
GIN (LCP-ORC)
72.60 1 1.28
70.64 + 1.32
87.19 + 1.56
GIN (19-RWPE)
71.76 + 1.34
69.35 = 2.24
74.40 + 1.68
GIN (20-LAPE)
71.52 + 1.26
68.16 + 2.83
75.84 + 1.65
GIN (HCP-FRC)
71.44 1: 1.46
70.40 1 1.52
70.53 1 1.48
GIN (HCP-ORC)
72.18 + 1.37
69.92 + 1.50
84.82 1 1.62
GIN H-19-RWPE)
72.08 +: 1.40
70.23 + 1.78
77.87 +: 1.49
GIN (EN
72.32 + 1.42
70.53 = 1.80
77.46 + 1.53
GIN (Hodge H1-20-LAPE)
72.16 16 + 1.39
69.37 = 1.65
79.94 1.81
GIN (Norm. H-20-LAPE)
71.95 + 1.35
69.48 = 1.71
79.15 + 1.54
Table 13: GIN performance with selected graph-leve encodings (top) and hypergraph level encodings
(bottom). We report mean and standard deviation across 50 runs for the Collab, Imdb, and Reddit datasets, In our tables, the best value in bold, the second best in blue and the third best in green.
E
Empirical Expressivity Analysis
E.1 BREC Dataset
The BREC dataset is expressiveness dataset containing H-WL-indistinguishaar graphs in categories:
Basic, Regular, Extension, and CFI graphs (Wang & Zhangl (024)). The 140 pairs of regular graphs are further sub-categorized into simple regular graphs (50 pairs), strongly regular graphs (50 pairs), 4-vertex condition graphs (20 pairs) and distance regular graphs (20 pairs). Note that we remove pairs that include non-connected graphs from the original 400 pairs arrive total of 390 pairs. Graphs in the Basic category (60 pairs, of which we remove 4) are non-regular. Some of the CFI graphs are WWW-indistinguishall. We provide a plot of the number of nodes and edges in each categories' graphs in Fig. and Fig. 5
Distribution of Node Counts Acress BREC Graph Categories
aapic
Pars:
fuis: 56.0
Peire 97.0
Pars: 91.0
250
Pairs: 20.0
de
Count
200
150
100
50
Figure 4: Histogram of the number of nodes in the graphs in BREC. The bars are stacked. We exclude pairs containing non-connected graphs from the original 800 graphs to arrive at 780 graphs. Best seen in color.
23

---

Distribution Edge Graph Categories
ontiama on
AxDx
eauer
Pars, 56.0
50.0
str
neguler bedic
ctt
extemiio
Palis 20.0
Parr:20000
COUPS
203
400
600
800
Number of Edges
Figure Histogram of the number of edges the graphs BREC. The bars are stacked. We exclude pairs containing non-connected graphs from the original 800 graphs to arrive at 780 graphs. Best seen in color.
E.2 Empirical comparaisons of encodings
We provide comparison of encodings computed the graph level and the hypergraph level in Tab. 14 We report the percentage of pairs in BREC that can be distinguished using the encodings, up permutation. The results in this table further illustrate theorems A. 3.14 We note that hypergraph-level encodings, with the exception of Hodge H-LAPE. are unable to distinguish pairs the "Distance Regular" category. The "CFI" category is also notoriously difficult: Some pairs are 4-WI WWL-indistinguuihabll.
3.6 3.12 and
(Kncodings)
Regular
Exteasion
VeVertes-Condittion
Regular
Grapt: 1-WLKGIN
Gruph
1lypersph (LDP)
91.07
91.0
100
25.77
100
Gmpph (LCP-FRC)
Hypergagh (HCP-FRC)
91.07
96.0
100
26.8
100
0
Gmapl (LCP-ORC)
100
100
100
100
55.67
100
0
Hlyergsph (HCP-ORC)
100
100
100
94.85
100
100
Graph (EE RWPE)
0
0
0
0
0
0
0
Hypergraph H-2-WWPE)
91.07
82
50.52
100
Graph (EE 3 RWPE)
85.21
92
6.19
0
Hlpergraphh
4-RWPE)
100
96
83.51
Hypergraph H-4-RWPF)
100
92.78
Graph (EE
100
95.88
Hypergraph (BE H-5-KWPP)
100
100
98
95.88
100
0
Grapls (EE 20 REP
100
100
100
3.09
Hypergraph (BE H-20-RWPE)
100
100
100
3.09
100
Origh (Normalized (-LAPE)
0.0
0.0
0
0
0
Hypergraph (Nomaalized LAAE))
91.07
90
25.77
100
Graph (Tlodge I-LAPE) Hypergraph (Hodge
48.21
100
100
71.13
7.22
100
74.23
Table 14: Difference in encodings the BREC dataset (390 pairs). We report the percentage of pairs with different encoding up to row permutation, at different level (graph or hypergraph). For the ORC Computations, we use the code from (Coupette et al. 2022) applied to hypergraphs and graphs.
24

---

Detailed Comparaison of encodings
E1 Rook and Shrikhande graphs
The Rook and Shrikhande graphs are examples of strongly regular graphs with parameters srg(16.6,2.22, meaning that they have 16 nodes, all of degree 6, and that any ajacent vertices share common neighbors, while any non-adjacent vertices also share common neighbors. We illustrate these graphs 6
We first compute 2-RWPE. The first entry is 0, as random walk from node i with 1-hop does not return to node i. The second entry is:
1
6
6
6
JEN;
Figure 6: The Rook graph and the Shrikhande graph. Those two non-isomorphic graphs can be hard to distinguish: they are both srg(16,6,2,2) and are isospectral.
Hypergraph Representation hyperedges)
Original Graph
Biparttt Representation
hypergraph
Figure 7: The Rook graph (left), its lifting (right) and its lifting's bipartite representation (center).
For the Rook graph's 's lifting to hypergraph (which we shall call the Rook hypergraph), the edges and vertices degree matrices are D. 4Ig and D. = 2/16: every hyperedge has 4 nodes, and every node two hyperedge (see 7 For the Shrikhande graph's lifting to hypergraph (which we call the Shrikhande hypergraph). these matrices are D. 3/s and D.. = 67 6: every hyperedge has nodes, and every node in hyperedge. Using Def. 33.9 we see that for the Rook graph, the FRC of
any edge is 4(2 -2) 2) 0, while for Shrikhande graph, the FRC of any edge is 3(2 6) -12
25

---

F22 Pair 0 of the "Basic" Category of BREC
BREC Dataset basic Category
Pair 0
edges
nades, edges
Degree Distribution (10 total nodes!
Graph A Graph
Stacietice:
cogaoe evec 6.029
Nusca rulcesa et 11.330 12000
& pear 000 133
0003
Dereter 2,00 3..000 160
Count
Dede dee 1000e 10:30 10445
Degree
Graph A Adjacency Matrix
Graph Adjacency Matrix
Node Index
Mode
Node Index
Node Index
Figure 8: The pair 0 of the "Basic" category in BREC. Top: the two graphs in the pair. Second row:
the (node) degree distributions and some statisties. Bottom: the adjacency matrices of the graphs.
26

---

Pyperdgee
fopenopei
CoaFt
Hipervege The
Hecheedge Stee
Mode Degrae
Rade Degree
Figure 9: The pair of the "Basic" category in BREC. Top: the two graphs in the pair. Second row: the graphs' liftings. Third row: the sizes of the (hyper)edges. Bottom: the node degrees.
We compute various encodings on this pair.
F.2.1
RWPE
The 1st entry of the RWPE encoding is O. We now compute one of the 2nd entries at the graph level. Start with node 0, node of degree 4, on pair A (see random-walker can go nodes of degree 4 (the node 3), 5 (the node 7) or 6 (the nodes 5 and 8). Thus, the probability of coming back to node after hops is 1 1
+
0.19583.
We report the full encodings for 2-RWPE in 15 We can actually see they are the same (up to row permutation.
At the hypergraph level, H-2-RWPE are different because the maximum absolute value of the last (sccond) column of the encoding for hypergraph A is 0.2503052503052503 while it is
27

---

0.0
0.19583
0.0
0.196
0.0
0.1916
0.0
0.196
0.0
0.20555556
0.1916
0.0
0.18
0.0
0.1916
0.0
0.196
0.0
0. 19583
0.0
0.18
0.0
0.18
0.0
0.196
0.0
0.18
0.0
0. 0.19883
0.0
0.18
0.0
0.18
0.205
0.0
0.1916
0.0
0. 0919883
Table 15: Pair (left) and Pair B (right) 2-RWPE encodings. They match we reorder the rows of
pair A follow: (4, 6, 1, 9, 0, 5, 7).
0.2935064935064995 for graph B. The full encodings can be found 16 It is straightforward to check that the two encodings cannot be made the same even to scaling and row permutation.
0.0
0.15842491
0.15165945
0.0
0.24619611
0.0
0.158187 18888182
0.0
0. 15650409
0.0
0.21682409
0.0
0.14429618
0.15999091
0.0
0.24619611
0.0
0. 1590999
0.0
0.18442491
0.0
0.29350649
0.0
0.25030525
0.0
0.26695527
0.0
0,241 75824
0.0
0.21682409
0.0
0. 144296118
0.0
0.15165945
0.0
0. 0.15620094
0.0
0.15818T88
Table 16: Pair A (left) and Pair B (right) H-2-RWPE encodings.
F.2.2 FRC
We now turn our attention to the FRC-LCP and FRC-HCP. The FRC-LCP of both pairs is presented The encoding match with the following ordering for pair A: (6, 5, 0, 2, 3, 7, 4, 9).
-6.00
-4.00
-5.25
-5,50
0.8291562
-7.00
-5.00
-6.20
-6.00
0.74833
-7.00
-6.00
-6.60
-7.00
0.48989795
-8.00
-6.00
-7.33
-7.50
0.74535599
-7.00
-6.00
-6.60
-7.00
0.48989795
-6.00
-4.00
-5.25
-5.50
0.8291562
-6.00
-4.00
-.25
-5.00
0.8291562
-7.00
-6.00
-6.60
-7.00
0.48989795
-8.00
-7.00
-7.33
-7.00
0.47140452
-7.00
-6.00
-6.60
-7.00
0.48989795
-8.00
-6.00
-7.33
-7.50
0.74535599
-6.00
.4.00
-5.25
-5.00
0. 0.8291562
-7.00
-5.00
-6.20
-6.00
0.74833 148
-7.00
-5.00
-6.20
-6.00
0.74833148
-7.00
-5.00
-6.20
-6.00
0,74833148
-8.00
-7.00
-7.33
-7.00
0.47140452
-8.00
-6.00
-7.00
-7.00
0.81649658
-8.00
-6.00
-7.00
-7.00
0.81649658
-8.00
-6.00
7.33
-7.50
0.74535599
-8.00
-6.00
77.3
-7.50
0.74535599
Table 17: Pair A (left) and Pair B (right) FRC-LCP encodings. They match with the following
permuation: (6,
2, 4, 8, 9)
At the hypergraph level, they are different because the maximum absolute value of encoding graph A 12.0, the maximum absolute value of encoding graph B is 10.0. The full encodings are presented in 18 It is straightforward to check that the matrices camnot be scaled and row permuted to match.
28

---

9
-6
-7
-6
1.41421356
-5
-
2.44948974
-9
-5
7.6
-9
188561808
10
-8
-8.6
-8
0.8
-9
-5
7.6
1.88561808 1808
5.3
2.49443826
9
-
-6
1.41421356
88
5
-7
-8
1.41421356
-11
-5
-7.8
-9
2.4
88
-7
-8
1.41421356
-12
-6
9.3
1.88561808 808
88
2
-
5.3
-6
2.49443826
-
-
6..6
-6
1.69967317
88
-2
-5
-5
2.44948974
-9
5
6.6
-6
1.69967317
-7
1.67332005
-12
-6
-9
-9
1.73205081
-10
-6
-8
-8
1.13470054
-2
-6
9.3
-9
188561808
-10
-8
-8.6
-8
0.8
Table 18: Pair A (left) and Pair B (right) FRC-HCP encodings.
F.2.3 1-LAPE
Using the Normalized Laplacian, the pair is 1-LAPE indistinguishable (up permuation, and sign flip, as the eingenvectors are defined up to +)). The 1-LAPE encodings are presented in 19
0.30348849
0.30348849
0.3441236
0.3441236
0.3441236
0,30348849
0.30348849
0.3441236
0.28097574
0.28097574
0.28097574
0.28097574
0.30348849
0.30348849
0,30348849
0.30348849
0.3441236
0.3441236
0.3441236
0.34412.36
Table 19: Pair A (left) and Pair B (right) Normalized following ordering for pair A: (0. 3, 2, 4, 7,
I-LAPE encodings. They match with the
At the hypergraph level, H-I-LAPE are different because the maximum absolute value 4048248290463863 for pair A and 0.392232270276637777 for pair B. The H-1-LAPE can be found in 20
0.25
0.2773501
0.40824829
0.39223227
0.40824829
0.2773501
0.25
0,39223227
0.40824829
0.39223227
0.40824829
0.39223227
0.25
0.2773501
0.25
0.2773501
0.20412415
0.19611614
0.204124415
0.19611614
Table 20: Pair A (left) and Pair B (right) Normalized H-1-LAPE encodings.
F.3 Additional Plots
present the pairs 0 of the regular category, alongside with the graphs' liftings, Fig. We present the pairs 0 of the strongly regular category in Fig.
29

---

Tsperdpen
Typeeedge Stee
Hyperrdoe See
Rade Degine
Moce Dogrne
Figure 10: The pair 0 of the regular category BREC. Top: the two graphs in the pair. Second row: the graphs' liftings. Third row: the sizes of the (hyper)edges. Bottom: the node degrees.
30

---

100L e0ga
roerrdee Size
Hypenege See
Rade Degine
Mice Degine
Figure 11: The pair of the strongly regular category in BREC. Top: the two graphs in the pair. Second row: the graphs' liftings. Third row: the sizes of the (hyper)edges, Bottom: the node degrees.
G Detailed ablation study for HNNs
G.1
UniGNN
We run node-level classification tasks using HNNs (Huang & Yang 202 We present results using
UniGAT in Tab. 22 UniGCN in Tab. 23 UniGIN in Tab. 24] UnISAGE in Tab. 25 and UniGCNII in
Tab. 26 For these experiments, we repeat experiments over data splits Yadati al. 2019) with different random seeds (80 total experiments). We train for 200 epochs and report the mean and std
of the testing accuracies across runs. We use the Adam optimizer with learning rate of 0.01 and weight decay of 0.0005. We use the relu activation function. The patience is set to 200 epochs, and the dropout probability for the input layer 0.6. The number of hidden features is set 8, and the number of layers is 2.
31

---

For this semi-supervised hypernode classification task, each dataset is split so that small fraction of labeled nodes used for training (with label rates ranging from 0.8% 5.2%, depending on the dataset see Tab. 21 and the rest are used for testing and validation.
Dataset
Total Samples
Train
Test/Val
Classes
Cora-CA
2,708
140 (5.2%)
2,568 (94.8%)
Citeseer
3,312
138 (4.2%)
3,174 (95.8%)
Cora-CC
2,708
140 (5.2%)
2,568 (94.8%)
Pubmed
19,717
78 (0.4%)
19,639 (99.6%)
Table 21: Train/Test split proportions in the hypergraph datasets.
Model
citeseer-CC (1)
cora-CA
cora-CC (1)
pubmed-CC (t)
UniGAT (HCP-FRC)
61.08 # 1.85
74.85 1.66
65.95 + 3.24
66.34 + 1.79
UniGAT (LDP)
62.07 + 1.68
75.47
1.47
69.31 2.23
68.41 + 1.79
UniGAT (Hodge H-20-LAPE)
63.21 + 1.53
75,80 1.23
71.22 1.60
75.77 + 1.05
UniGAT (Norm. H-20-LAPE)
63.15 + 1.63
1.50 75.65
71.23 + 1.87
75.77 + 1.02
UniGAT (H-19-RWPEE EE)
62.97 + 1.51
75.65
1.40
70.78 + 1.85
74.78 + 1.18
UniGAT (H-19-RWPEE EN)
62.88 + 1.53
75.76 1.37
70.74 1.86
74.75 + 1.18
UniGAT (H-19-RWPEE WE)
62.97 + 1.45
75.53 1.53
70.86 + 1.93
74.82 + 1.12
UniGAT (no encodings)
63.25 + 1.48
75.68 1.45
71.16 1.55
75.62 + 1.09
Table 22: Node level classification for hypergraph using hypegraph encodings for UniGAT. The depth
is 2.
Model
citeseer-CC (1)
cora-CA (1)
cora-CC (t)
pubmed-CC (f)
UniGCN (HCP-FRC)
61.20 + 1.83
74.64 # 1.45
68.98 1.59
67.37 4: 1.73
UniGCN (LDP)
61.67 + 1,90
75.17 # 1.54
69.17 + 1.58
69.33 + 1.57
UniGCN (Hodge H-20-LAPE)
63.46 # 1.58
75.64 1.37
71.31 1.19
75.37 + 1.01
UniGCN (Norm. H-20-LAPE)
63,41 1.61
75.55 1.48
71.20 1.24
75.30 1.01
UniGCN (1-19-RWPEE EE)
63.29 1.52
75.34 1.28
71.13 1.24
74.61 1.18
UniGCN (1--1-RWWEE EN)
63.09 # 1.62
75.30 1.37
71.21 + 1.34
74.61 + 1.09
UniGCN (H--1--RWPE) WE)
63,04 1.74
7
71.40 + 1.25
74.59 + 1.11
UniGCN (no encodings)
63.36 + 1.76
75.72 # 1.16
71.10 + 1.37
75.32 + 1.09
Table 23: Node level classification for hypergraph using hypegraph encodings for UniGCN. The
depth is 2.
Model
citeseer-CC (t)
cora-CA (f)
cora-CC (t)
pubmed-CC (t)
UniGIN (HCP-FRC)
59.10 + 1.84
72.91 + 1.88
57.77 3.10
65.55 + 2.40
UniGIN (LDP)
59.88 # 2.37
73.83 + 1.59
62.96 + 2.89
67.41 + 3.16
UniGIN (Hodge H-20-LAPE)
60.67 2.23
74.29 + 1.62
67.67 + 2.50
75.11 + 1.47
UniGIN (Norm. H-20-LAPE)
60.18 + 2.37
74.12 1.46
67.92 + 2.23
75.09 + 1.45
UniGIN 19-19-WWEEE EE)
60.33 + 2.04
74.03 + 1.51
67.70 + 2.15
74.44 + 1.44
UniGIN (H-19-RWPPE) EN)
60.13 + 2.31
74.04 1.58
67.62 + 2.46
74.34 + 1.37
UniGIN (H- (H-19-RWPER WE)
60.23 # 2.19
73.97 + 1.61
67,50 + 2.46
74.44 + 1.32
UniGIN (no encodings)
60.56 + 2.31
73.97 + 1.56
67.70 + 2.33
75.02 + 1.39
Table 24; Node level classification for hypergraph using hypegraph encodings for UniGIN, The depth
is 2.
32

---

Model
citeseer- CC (1)
cora-CA (1)
cora-CC (1)
pubmed-CC (t)
UniSAGE (HCP-FRC)
59.10 + 2.29
72.37 1.96
57.35 + 3.15
65.71 # 2.58
UniSAGE (LDP)
59.97 + 2.27
73.88 1.71
63.08 + 2.68
67.53 : 3.09
UniSAGE (Hodge H-20-LAPE)
60.55 + 2.02
74.13 1.57
67.80
75.03 1.42
UniSAGE (Norm. H--2--APPE)
60.54 = 2.19
74.10 = 1.52
67.89 + 2.37
75.07 = 1.44
UniSAGE (1-19-RWPEE EE)
60.29 = 2.17
73.99 1.59
67.76 1.91
74.41 = 1.43
UniSAGE RH-RE- EN)
60.30 + 2.33
74.00 1.57
67.86 + 2.15
74.29 + 1.36
UniSAGE 19-RRPEE WE)
60.22 + 2.22
73.97 1.35
67.82 + 2.18
74.37 # 1.33
UniSAGE encodings)
60.56 2.10
74.16 1.50
67.80 + 2.33
75.02 + 1.44
Table 25; Node level classification for hypergraph using hypegraph encodings for UniSAGE. The depth is 2.
Model
citescer-CC (f)
cora-CA (f)
cora-CC (1)
pubmed-CC (t)
UniGCNU (HCP-FRC depth
61.19 1.65
75.50
66.83
1.88
65.00 + 2.18
UniGCNII (LDP depth 2)
62,34 t 1.62
76.39 + 1.58
68.65 = 1.59
67.40 = 1.93
UniGCNII (Hodge 11-20-LAPE depth 2)
63.90 + 1.87
76.68 + 1.44
71.09 = 1.20
75.51 $ 1.13
UniGCNII (Norm. H-20-LAPE depth 2)
64.09 1.80
76.79 + 1.31
71.06 1.28
75.44 1.09
UniGCNII (H-19-RWPP) EE depth
63.72 1.55
76.59 1.39
70.64 1.28
75.05 0.99
UniGCNII 111-19-RWPER EN depth 2)
63.67 1.47
76.56 + 1.48
70.87 # 1.31
75.01 + 0.98
UniGCNII (1--1--RPPE WE depth 2)
63.71 # 1.53
76.74 + 1.36
70.68 = 1.30
75.03 + 0,96
UniGCNII (no encodings depth 2)
64.13 + 1.68
76.70 + 1.43
70.68 = 1.53
75.40 = 1.18
UniGCNII (HCP-FRC depth 8)
62.05 + 1.47
75.97 + 1.37
66.45 + 1.88
64.27 : 2.66
UniGCNII (LDP depth 8)
62,90 = 1.40
76.98 + 1.28
69.06 = 1.67
66.78 = 2.23
UniGCNII (Hodge H-20-LAPE depth 8)
65.18 1.41
77.06 + 1.22
71.93 1.15
75.29 1.33
UniGCNII (Norm. H-20-LAPE depth 8)
65.01 1.60
77.00 1.37
71.91 1.26
75.30 1.35
UniGCNII 19-RWPEE depth
64.77 1.49
76.95 1.31
71.57 1.22
74.59 1.40
UniGCNII (H-19 19-RWPEE EN depth 8)
64.66 + 1.43
76.92 + 1.20
71.79 + 1.14
74.61 + 1.35
UnIGCNII (H-19 19 RWPEE WE depth 8)
64.75 # 1.46
76.85 + 1.23
71.60 # 1.28
74.60 # 1.37
UniGCNII (no encodings depth 8)
64.72 +: 1.58
77.17 + 1.34
71.57 # 1.32
75.24 * 1.30
UniGCNII (HCP-FRC depth 64)
62,93 + 1.45
75.01 + 1.40
65.54 + 1.93
64.44 + 2.82
UniGCNII (LDP depth 64)
63.60 + 1.61
75.89 + 1.41
69.85 = 1.65
66.80 2.07
UniGCNII (Hodge H-20-LAPE depth 64)
65.38 1.53
76.35 + 1.08
72.52 1.38
75.36 1.29
UniGCNII (Norm. H-20-LAPE depth 64)
65.25 1.60
76.24 1.16
72.68 1.36
75.36 1.29
UniGCNII
EE depth 64)
65.40 1.49
76.25 + 1.17
72.62 + 1.24
74.54 + 1.43
UniGCNII (H-19-RWPPE) EN depth 64)
65.38 # 1.56
76.31 + 1.15
72.59 1 1.25
74.63 # 1.36
UniGCNII (1-11-RRWPE WE depth 64)
65.20 1.52
76.16 + 1.20
1.27 72.65
74.60 1.33
UniGCNII (no encodings depth 64)
65.24 1.67
76.34 + 1.12
72.64 * 1.06
75.34 + 1.24
Table 26: Node level classification for hypergraph using hypegraph encodings for UniGCNII (depth:
2, 8, 64).
G.2 PhenomNN
We conduct experiments using PhenomNN with the hyperparameters from Wang et (0233). 3). The model employs hidden dimension of 64 units with single hidden layer architecture. For the CaanooNNN-speciin parameters, we set X 20 and X 80 control the weighting between different adjacency matrices, a = 0.1 for residual connections, and 16 propagation steps. Training performed with a learning rate of 0.01, high dropout rate of 0.7 regularization, and up to 1000 epochs with early stopping patience of 100. L.2 regularization is applied with weight decay of x 10-4 The normalization type set to "full". The full set of parameters presented Tab. The results presented in Tab. 28
33

---

Parameter Category
Parameter
Value
Core Model
Hidden dimension
64
Number of hidden layers
1
Base block layers Batch normalization
I
False
PhenomNN-Specifte
A A (residual)
20
80
0.1
Propagation steps
16
Normalization type
Full
Training
Learning rate
0.01
Dropout rate
0.7
Epochs
1000
Weight decay
10-4
Early stopping patience
100
Additional
K (APPNP)
10
a (GCNII)
0.1
À (GCNII)
0.5
A
0
Table 27: Hyperparameters used for the PhenomNN experiments.
Model
citeseer-CC (1)
cora-CA (t)
cora-CC (1)
pubmed-CC (t)
PhenomNN (HCP-FRC)
58.87 + 1.03
74.03 0.97
54.02 + 2.06
68.88 = 01.44
PhenomNN (HCP-ORC)
64.89 + 0.45
75,93 +
72.21 + 0.31
77.37 = 0.23
PhenomNN (LDP)
62.54 + 0.52
75.67 0.50
62.28 # 3.33
70.63 = 0.87
PhenomNN (Hodge H-20-LAPE)
64.98 + 0.58
76.76
72.18 0.33
78.36 # 0.23
PhenomNN (Norm. H-20-LAPE)
64.75 + 0.52
76.64
72.06 + 0.68
78.27 + 0.25
PhenomNN (H-20-RWPEE EE)
64,23 + 0.40
7.557
72.18 = 0.52
77.97 = 0.29
PhenomNN (11-00-RPPEE EN)
64.47 = 0.62
76.39 0.57
71.57 = 0.73
78.10 = 0.20
PhenomNN (11-20-RPPEE WE)
64.52 0.69
7
72.30 = 0.79
78.06 0.24
PhenomNN (no encodings)
64.96 0.58
76.98 0.41
72.27 + 0.41
78.09 + 0.24
Table 28: Node level classification for hypergraph using hypegraph encodings for PhenomNN, Mean
accuracy (%) + standard deviation results over 10 train-test splits.
G.3 HGNN
We conduct experiments using HGNN with the hyperparameters presented Tab, 29 The results are presented in Tab. 30
Parameter
Value
hidden dims
128.0
dropout_rar rate
0.5
learning_rat rate rate
0.01
weight_ decay
0.0005
epochs
500.0
patience
50.0
ratio
0.2
normalize_feature
False
mormalize_cncodinng
False
Table 29: HGNN configuration parameters. Model depth: 2 layers.
34

---

Model
citeseer-CC (1)
cora-CA (1)
cora-CC (1)
pubmed-CC (1)
HGNN (HCP-ORG
58.48 1.24
59.41 1,53
59.93 + 1.40
71.69 + 1.41
HGNN (HCP-FRC)
56.04 1.54
58.36 1.93
56.37 2.47
65.83 + 1.70
HGNN (LDP)
57.07 = 1.39
59.85 # 1.71
58.06 +.12
67.12 1.30
HGNN (Hodge H-20-LAPEE
58.82 = 1.24
60.10 = 1.64
60.15
72.47 + 1.37
HGNN (Norm. H-20-LAPE)
58.68 1,40
60.20 = 1,55
60.16 1.55
72.47 + 1.36
HGNN (1--1-RWPEE EE)
57.79 1.33
59.14 + 2.15
59.76 - 1.53
72.42 1.28
HGNN (H-19-RWPEE EN)
57.73
59.28 1.97
59.79
72.39
HGNN (H- 19-RWPEE WE)
57.69 + 1.22
59.29 + 1.91
59.69
1.57
72.38 + 1.31
HGNN (no encodings)
58.24 + 1.20
60.35 1.48
59.48
72.60
Table 30: Node level classification for hypergraph using hypegraph encodings for HGNN. We report mean accuracy and standard deviation over 80 runs (8 seed with ten each). We the splits present in Tab 21
H Rankings of encodings
We rank the hypergraph encodings by raw accuracies on all (graph model, datasets) pairs. We then average the rankings by model by task in Tab. [3 32 33
34
[5]
36 For example, average the
rankings over GPS, GCN and GIN for graph classification tasks in Tab.
Encoding
Average Rank (L)
EE H-19-RWPE
2.24
EN H- 1--9--WPE
2.53
HCP-ORC
3.13
Hodge H-20-LAPE
4.12
Norm. H-20-LAPE
4.29
HCP-FRC
4.41
No Encoding
6.71
Table 31: Average ranking of each hypergraph encoding across all dataset evaluations on graph classification tasks using the models GPS, CGN, and GIN. Lower is better. A total of 17 evaluations were considered.
Encoding
Average Rank ({)
EE H-19-RWPE
1.43
EN H-19-RWER
2.14
HCP-ORC
4.00
Hodge H-20-LAPE
4.28
HCP-FRC
4.71
Norm. H-20-LAPE
5.71
No Encoding
6.43
Table 32: Average ranking each hypergraph encoding across all dataset evaluations on graph classification tasks using GPS. Lower is better. A total of evaluations were considered.
35

---

Encoding
Average Rank ())
EE H-19-RWPE
2.43
HCP-ORC
2.67
EN H-19-RWPE
3,00
HCP-FRC
3.86
Hodge H-20-LAPE
4.14
Norm. H-20-LAPE
4.29
No Encoding
6.71
Table 33: Average ranking of each hypergraph encoding across all dataset evaluations graph
classification tasks using GCN. Lower is better. total evaluations were considered.
Encoding
Average Rank (1)
EE H-19-RWFP
3.67
EN H-19-RWPE
2.33
HCP-ORC
2.33
Hodge H-20-LAPE
3.67
Norm. H-20-LAPE
4.33
HCP-FRC
5,00
No Encoding
6.67
Table 34: Average ranking of each hypergraph encoding across all dataset evaluations on graph
classification tasks using GIN. Lower is better. A total of 3 evaluations considered. Note that the rows are not ordered by average rank here.
Encoding
Average Rank (!)
EE H-19-RWPE
1.38
EN H-19-RWPE
2.13
HCP-ORC
4.0
Hodge H-20-LAPE
4.0
Norm. H-20-LAPE
5.5
HCP-FRC
4.63
Encoding
6.5
Table 35: Average ranking of each hypergraph encoding across all dataset evaluations on graph classification and regressions tasks using GPS. Lower better. total of 8 evaluations were considered. Note that the rows are not ordered by average rank here.
Encoding
Average Rank (L)
EE H-19-RWPE
2.75
EN H-19-RWPE
3.25
HCP-ORC
2.86
Hodge H-20-LAPE
3,88
Norm. H-20-LAPE
3.88
HCP-FRC
3.75
No Encoding
6.75
Table 36: Average ranking of each hypergraph encoding across all dataset evaluations graph classification and regressions tasks using GCN, Lower is better. A total of 8 evaluations were considered. Note that the rows are not ordered by average rank here.
36

---

I Runtimes
We present the runtimes necessary to compute the graph and hypergraph encodings on Imdb in Tab. 37and and on Mutag in Tab. 38
1.1
On Imdb
Encoding Method
Encodings on original graphs
Encodings on lifted hypergraphs
Random Walk EN
0.0007 1 0.0009
0.0006 + 0.0008
Curvature FRC
0.0009 # 0.0005
0.0007 = 0.0003
Degree
0.0010 + 0.0005
0.0010 = 0.0005
Laplacian Hodge
0.0014 0.0022
0.0003 0.0002
Laplacian Normalized
0,0075 0.0113
0.0007 = 0.0003
Random Walk EE
0,0182 = 0.0397
0.0022 = 0.0031
Curvature ORC
5.1573 # 0.1235
5.1990 = 0.0994
Table 37: Encoding runtimes (mean + std in seconds) original graphs and clique-lifted hypergraphs
for the first 50 graphs of Imdb.
1.2 On Mutag
Encoding Method
Encodings original graphs
Encodings lifted hypergraphs
Laplacian Hodge
0.0003 0.0001
0.0003 = 0.0001
Random Walk EN
0.0004 0.0002
0.0004 = 0.0001
Curvature FRC
0.0007 = 0.0002
0.0007 = 0.0002
Degree
0.0007 + 0.0002
0.0007 = 0.0002
Laplacian Normalized
0.0012 = 0.0006
0.0007 = 0.0002
Random Walk EE
0.0024 0.0012
0.0017 0.0007
Curvature ORC
5.3687 + 0.2250
5.3564 = 0.1863
Table 38: Encoding runtimes (mean + std in seconds) on original graphs and clique-lifted hypergraphs
for the first 50 graphs in Mutag.
J Hardware specifications and libraries
All experiments in this paper were implemented in Python using Py PyTorch, Numpy Py Torch Geometric, and Python Optimal Transport.
Our experiments were conducted on local server with the specifications presented in Tab.
Components
Specifications
Architecture
X86 64
OS
UBUNTU 20.04.5 LTS x86_64 64 AMD EPYC 7742 64-CORE NVIDIA A100 TENSOR CORE 40GB
CPU
GPU
RAM
Table 39: Server specifications.
37

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: this work, we support formal claims on the proposed encoding 's expressivity with proofs and provide experimental results for several graph learning benchmark evidence of the claimed performance gains.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation long as it is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mention limitations throughout the paper. The discussion section has a dedicated paragraph on limitations of our study, including a lack of benchmarks with true hypergraph- structured data and con-exhaustivv comparison against existing hypergraph neural network architectures.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those
discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificationn asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
38

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide proofs for all theoretical results in the main text the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: The experimental setup is described in section 4 in the main text. Additional experimental details on data sets and hyperparameter choices are given in Appendix C. We publicty release the code in an anonymous repository.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., .. the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-soure models, it may be that access to the model is limited in some way (c.g.. to registered users), but should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
39

---

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We make the code available in anonymous repository. The repository includes documentation that provides instructions for running the code and reproducing results. The C.1.
experiments in this study leverage publicly available data sets, details are provided in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://ni)) httpp//ccpcccpppcccc/////////// guides/Codeeuubmiss ssi ssoonoliccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https (oodeeuumisssiooo....
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all training and testing details in the main text and in Appendix C. Hardware specification and usage of libraries is detailed in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: All results are reported with error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main
claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
40

---

The method for calculating the enror bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors). It should be clear whether the error bar is the standard deviation the standard emror of the mean.
It is OK to report 1-sigma enror bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [Yes]
Justification:
The computing resources used in this study are detailed in Table 26.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn' 't make into the paper).
Code of ethics
Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp//sc/pppp..ct/ttttetttaaaaa
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. g.. if there a special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents work whose goal is to advance our theoretical understanding of Machine I Learning. There are many potential societal consequences, none of which we feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
41

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faimesss considerations (e.g,, deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses addition attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Data sets and models are referenced throughout the main text and appendix. Licenses are listed in Appendix H.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcone com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
42

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Implementations of the proposed encodings provided in anonymous repository. No new data sets are introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection. curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants. whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
43

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy hattap//heerrpssccc///drrrrerrss (LMM) for what should or should not be described.
44


Reviews:
[{"review_id": "TnvwjLJX0E", "reviewer": "Reviewer_UZHC", "summary": "This paper introduces hypergraph-level encodings to enhance higher-order relational learning. The authors propose structural and positional encodings (e.g., hypergraph Laplacian eigenvectors, random walk transition probabilities, curvature profiles) that capture higher-order information beyond pairwise interactions. Theoretical analysis proves that the encodings increase the expressivity of message-passing GNNs beyond the 1-WL test. Experiments show performance gains when combining hypergraph encodings with graph-level architectures, though hypergraph-specific architectures benefit minimally.", "questions": "- It would be better to provide a formal point of view of the term higher-order information and hypergraph-level encoding.\n- Why do hypergraph architectures (e.g., UniGCN) not benefit from hypergraph encodings?\n- The incidence matrix given in Definition 3.1 is also used in [1]. Also, the proposed covariance matrix $B_1B_1^T$ seems to be a simple form of $HWD^{-1}H^T$ in [1]. Please discuss their differences.\n\n[1] Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33 (pp. 3558-3565).", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "##### Strengths\n\n- High-order information is crucial for complex tasks and is a promising research topic. The authors propose a novel shift from architectural extensions (e.g., message-passing hypergraph NNs) to data-centric hypergraph encodings.\n- Well-structured with clear statements. Appendices provide the necessary background.\n- Theoretical proofs (Theorems 3.2, 3.5, 3.11) demonstrate enhanced expressivity. Extensive experiments validate claims, with ablation studies and scalability analysis.\n\n##### Weaknesses\n\n- It is still unclear why the covariance matrix of the incidence matrix, as shown in Definition 3.1, helps to capture higher-order information. Theorem 3.2 shows that this way has higher discrimination power for nonisomorphic graphs. Does this mean all models with higher discrimination power potentially capture higher-order information?\n- Encodings improve graph-level models but not hypergraph architectures. This discrepancy is noted but not analyzed.\n- All proofs of expressive power are conducted within BREC datasets. Given so, the theoretical contributions can be limited.", "was_revised": true, "final_justification": "After discussing with the authors, the concern remains: the paper has technical issues in its proofs in Theorem 3.2 and 3.5. Although the authors propose possible solutions in rebuttal, trying to fix the proofs, the conclusion that their proofs rely on is still controversial.", "rebuttal": "## General response\n\nThank you to all the reviewers for thoughtful and insightful feedback! We are pleased that reviewers are excited about the novel contributions of our work. Reviewers remark that **\"higher-order information is crucial for complex tasks and is a promising research topic\"** [UZHC] and that **\"using encodings for improving MPNN-performance is an interesting research direction\"** [Ej7N]. Reviewers also note that \"the paper is well-written and easy to follow\" [6gkV] and appreciate the **theoretical motivations** for our work [UZHC, 6gkV], as well as the extensive experiments [UZHC, GZBz].\n\nWe now highlight a few important points raised by reviewers that we address in our rebuttal:\n\n- **Additional experiments** with MLPs and GTs [6gkV]: We provide additional results using MLPs and vanilla graph transfomers (GTs) without message-passing. These results support our claims that hypergraph-level encodings are generally useful and often - but not always - outperform their graph-level counterparts (LCP-FRC, RWPE).\n- More extensive hyperparameter tuning and **state-of-the-art results** [GZBz, Ej7N, 6gkV]: Several reviewers wondered if our encodings would still be useful with models that achieve SOTA performance. We first note that the models we consider, e.g. GCN and GIN, have recently been shown to outperform many newer models, including GTs, on several benchmarks [*], [+]. Using either the hyperparameters provided in these papers or by running HP searches when unavailable, we significantly increase the performance of our baseline models. With now close to SOTA results, we still find the same trends: our encodings are generally useful and often outperform their graph-level counterparts.\n- **Extended discussion** of why HGNNs do not seem to benefit from hypergraph-level encodings [GZBz, UZHC]: we have included additional remarks about oversmoothing and normalization in HGNNs and about encoding information that HGNNs might compute implicitly, as well as references to recent works that we think might allow one to make this discussion rigorous.\n- We have added **pre-processing runtimes** (for lifting graph to hypergraphs, and for computing encodings).\n\nWe believe that these additions have made the paper significantly better and more accessible and thank the reviewers again for their input.\n\n[*] Luo, Y., Shi, L. and Wu, X.M., Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence. In Forty-second International Conference on Machine Learning.\n\n[+] Luo, Y., Shi, L. and Wu, X.M., 2024. Classic gnns are strong baselines: Reassessing gnns for node classification. Advances in Neural Information Processing Systems, 37, pp.97650-97669.\n\n**We now address each of the reviewer's comments and questions individually:**\n\n> It is still unclear why the covariance matrix of the incidence matrix, as shown in Definition 3.1, helps to capture higher-order information. Theorem 3.2 shows that this way has higher discrimination power for nonisomorphic graphs. Does this mean all models with higher discrimination power potentially capture higher-order information?\n\n- Thank you for raising this point. The covariance matrix $B_1B_1^T$ is useful because it captures how often two vertices appear together in a hyperedge, and its eigenvectors—the Hodge-Laplacian encodings—retain that higher-order signal even after we project back to a simple graph. Theorem 3.2 shows that feeding these encodings to a message-passing GNN makes it strictly more expressive than 1-WL.\n\n- Capturing higher-order information allows for higher expressivity. Here, higher-order information refers to interaction patterns that involve three or more vertices simultaneously. Formally, any hyperedge $e \\subseteq V$ with $|e| > 2$, encodes such information. Such interactions (often called \"higher-order interactions\" in network science [1]) cannot be reconstructed from the pairwise edge set alone, so they encode genuinely new structural signals beyond a graph's 1-skeleton. Many of the graph characteristics that form the basis of graph-level encodings capture higher-order information as well, e.g., Ollivier's Ricci curvature (LCP-ORC) captures local cycle counts. However, if these characteristics are computed on a hypergraph parametrization, richer higher-order information is captured. This is confirmed by both our theoretical and computational analysis: Our expressivity results (Thm. 3.2, 3.5, 3.11, 3.13) show that pairs of graphs exist that can be distinguished by computing the respective characteristics at the hypergraph-level, but not by its graph-level analogue. *This progression of richer encoded higher-order information induces a hierarchy of more expressive models.* We illustrate this on the example of local curvature profiles (LCP): Simple Forman curvature computed on a graph's 1-skeleton cannot capture higher-order information. Using a curvature notion that encodes higher-order information (augmented Forman curvature or Ollivier's curvature, both of which capture cycle counts, see Apx. A.5), is provably more expressive [2]. Computing Ricci curvature on the hypergraph-level is provably more expressive than its graph-level counterpart (Thm. 3.11). Our empirical comparison of hypergraph- and graph-level encodings also confirms this intuition.\n\n> Encodings improve graph-level models but not hypergraph architectures. This discrepancy is noted but not analyzed.\n\n- Thank you for pointing this out - we agree that this is indeed a very interesting point. We suspect that since hypergraph layers already process the full incidence structure, the co-incidence statistics that, for example, our Hodge encodings add are largely redundant: most of that signal is already available to the architecture. By contrast, a standard graph GNN sees only pairwise edges; the encodings inject complementary higher-order cues it would otherwise miss, hence the larger gains. We believe that this intuition could be made rigorous using techniques similar to [3], which operates at the graph level, but consider this beyond the scope of the current paper.\n\n> All proofs of expressive power are conducted within BREC datasets. Given so, the theoretical contributions can be limited.\n\n- We would like to point out that Theorems 3.2, 3.5, 3.11, 3.13 and A.1 are stated for all finite graphs/hypergraphs; the proofs simply exhibit witness pairs that are 1-WL-hard, and we picked those pairs from BREC because the dataset conveniently aggregates many classic counter-examples in one place, making the exposition shorter and letting us reuse them for the empirical section. Crucially, several proofs already rely on graphs that pre-date—and in fact are not unique to—BREC: e.g. the Rook vs. Shrikhande pair.\n\n> It would be better to provide a formal point of view of the term higher-order information and hypergraph-level encoding.\n\n- Please see response above.\n\n> The incidence matrix given in Definition 3.1 is also used in [1]. Also, the proposed covariance matrix $B_1B_1^T$  seems to be a simple form of $HWD^{-1}H^T$  in [1]. Please discuss their differences.\n\n- Thank you for bringing this up. Please note that we do not propose the 0- or 1-Hodge Laplacian $B_1^TB_1$ and $B_1B_1^T$. These are well-established quantities in the theory of hypergraphs.\n- Our covariance $B_1 B_1^{\\top}$ simply multiplies the (unsigned) incidence matrix by its transpose, so the diagonal records vertex degrees and the off-diagonal entry $(i,j)$ counts how many hyperedges jointly contain $v_i$ and $v_j$; no weighting or size normalisation is applied. This raw co-incidence statistic is what we later diagonalise to obtain positional encodings. In contrast, HGNN first weights each hyperedge by $W$ and then divides by its size through $D_e^{-1}$, giving the normalised operator $H W D_e^{-1} H^{\\top}$ (and its symmetric variant $D_v^{-1/2} H W D_e^{-1} H^{\\top} D_v^{-1/2}$) that appears inside every convolution layer. This choice turns each hyperedge into a clique whose contribution is averaged across its members, making the matrix row- and column-balanced. This is useful for stable message passing but less informative about absolute co-membership frequencies. Accordingly, $B_1 B_1^{\\top}$ reduces to the (combinatorial) graph Laplacian when $|e|=2$, whereas $H W D_e^{-1} H^{\\top}$ collapses to a degree-normalised adjacency; the two operators are thus complementary rather than equivalent. We hope this clarifies and would be happy to elaborate further.\n\n[1] Aktas, M.E., Nguyen, T., Jawaid, S., Riza, R. and Akbas, E., 2021. Identifying critical higher-order interactions in complex networks. Scientific reports, 11(1), p.21288.\n\n[2] Fesser, L. and Weber, M., Effective Structural Encodings via Local Curvature Profiles. In The Twelfth International Conference on Learning Representations.\n\n[3] Kanatsoulis, C., Choi, E., Jegelka, S., Leskovec, J. and Ribeiro, A., Learning Efficient Positional Encodings with Graph Neural Networks. In The Thirteenth International Conference on Learning Representations."}, {"review_id": "zT9U3DAfUR", "reviewer": "Reviewer_Ej7N", "summary": "The paper proposes to use hypergraph encodings in order to enhance performance of graph neural networks. These encodings are designed to capture higher-order structural and positional information, which cannot be captured by standard MPNNs. Expressivity is also partly investigated theoretically.\nThe experimental evaluation shows that the encodings outperform graph-level methods, especially on social networks.", "questions": "Please improve the quality of the paper by making sure that all definitions are correct and included. Please define all variables used. I like the idea of the paper, but in the current state, I am against accepting it.\n\n**Q1** Which of the encodings should be used? Can you say anything about which one might be better depending on the dataset?\n\n**Q2** What is the computational complexity of all the proposed encodings (there are some missing an analysis)? What was the runtime for computing them in practice?\n\n**Q3** Regarding the significance of the proposed methods.\n\na) For hypergraphs: As stated in the discussion section, it seems there is not really data available that is naturally represented as hypergraphs. At first glance, it does not seem to be useful then, or am I missing something?\n\nb) For traditional graphs: In the experimental evaluation, the encodings outperform the models without encoding. However, they are not compared to state-of-the-art GNNs, so this seems more like an ablation study. Can you comment on that?\n\n**Q4** Why are the last three entries in Equation 8 (and in LDP) repeated?", "limitations": "Computational complexity of the proposed encodings was not discussed as a limitation.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**S1** The idea of the paper is nice, using encodings for improving MPNN-performance is an interesting research direction. Since the source code is available online, and the experimental setup is described in great detail, one should be able to reproduce the results easily. \n\n**S2** The discussion at the end is really extensive. Most limitations are discussed in detail.\n\n**W1** The presentation of the paper can be improved significantly. In the background section several definitions are incomplete or missing. For the graph definition, V should be included (G=(V,X,E)) and F should be defined formally. The neighborhood of a vertex is not formally defined. The abbreviations GNN and MPGNN are used but never introduced. A short intuition of how a graph is transformed into a hypergraph should be given within the paper (currently it is only in the appendix). D, d_k, A, RW (and maybe other variables) are never defined. Some variables (like d) also seem to be used multiple times in different ways. H-LDP is also not formally defined. In the references, there are multiple duplicate entries.\n\n**W2** From the experimental evaluation, it seems as though no encoding consistently outperforms the others. If there are differences in performance, these could be highlighted by computing a ranking of the methods over all datasets.\n\n**W3** The runtime needed to compute **all** the different encodings is not (neither theoretically nor empirically) shown.\n\nOther comments:\n\n- Many (not all) paragraph titles are missing the .\n- For some sections/subsections the title is not capitalized consistently.\n- A figure showing an overview of the different encodings would be nice.\n---\n- l17ff maybe rephrase the first sentence or split it in two.\n- l171 (see F.2) maybe Appendix missing?\n- l212 Both graphs were not introduced before, so \"again\" is not fitting (and maybe the graphs should also be defined first).\n- l230 Why does the LDP not get an equation number?\n- l260 When referring to tables in the appendix, please make clear that they are in the appendix.\n- l302 Lehman -> Leman\n- l303 hypergrpah -> hypergraph", "was_revised": true, "final_justification": "The authors have addressed my concerns in their rebuttal and provided additional results.\nGiven this, I would lean slightly more towards acceptance.\nI think the formatting and quality issues can be addressed within the time frame of the rebuttal/until the camera-ready version is due.", "rebuttal": "## General response\n\nDue to the character limit, please see reviewer [UZHC] for our general response. We apologize for the inconvenience.\n\n**We now address each of the reviewer's comments and questions individually:** \n\n> The presentation of the paper can be improved significantly. In the background section several definitions are incomplete or missing. For the graph definition, V should be included (G=(V,X,E)) and F should be defined formally. The neighborhood of a vertex is not formally defined. The abbreviations GNN and MPGNN are used but never introduced. A short intuition of how a graph is transformed into a hypergraph should be given within the paper (currently it is only in the appendix). D, d_k, A, RW (and maybe other variables) are never defined. Some variables (like d) also seem to be used multiple times in different ways. H-LDP is also not formally defined. In the references, there are multiple duplicate entries.\n\n- We thank the reviewer for pointing this out and apologize for the oversights. The graph definition has been adjusted and definitions for the neighborhood of a vertex, the H-LDP, and missing variables have now been included. GNN and MPGNN are now formally introduced and duplicate entries in the references have been removed.\n- To provide intuition on how a graph is transformed into a hypergraph in the main text, we propose to include the following: A graph is “lifted” to a hypergraph by adding a hyperedge for every set of vertices that are pairwise connected in the graph—effectively turning each clique into a single higher-order relation.\n\n> From the experimental evaluation, it seems as though no encoding consistently outperforms the others. If there are differences in performance, these could be highlighted by computing a ranking of the methods over all datasets.\n\n- This is an excellent point for which we would like to thank the reviewer. We now compute the average ranking of each hypergraph encoding across all model and dataset evaluations on graph regression and classification tasks, as well as node classification tasks:\n\n| **Encoding**           | **Average Rank (↓)** |\n|------------------------|----------------------|\n| EE H-19-RWPE           | 2.71         |\n| EN H-19-RWPE           | 3.04                 |\n| HCP-ORC                | 3.22                 |\n| Hodge H-20-LAPE        | 3.67                 |\n| Norm. H-20-LAPE        | 4.00                 |\n| HCP-FRC                | 4.08                 |\n| No Encoding            | 6.67                 |\n\n- On graph-classification tasks, RWPE should be used. We found the EE scheme to be be superior to EN. On graph regression tasks and node classification tasks, H-LAPE should be used. We found that using the Hodge Laplacian is more beneficial than using the Normalized Laplacian. Below is the average ranking of each hypergraph encoding across GPS, GCN, and GIN on graph classification tasks:\n\n| **Encoding**         | **Average Rank (↓)** |\n|----------------------|-----------------------|\n| EE H-19-RWPE         | 2.24                  |\n| EN H-19-RWPE         | 2.53                  |\n| HCP-ORC              | 3.13                  |\n| Hodge H-20-LAPE      | 4.12                  |\n| Norm. H-20-LAPE      | 4.29                  |\n| HCP-FRC              | 4.41                  |\n| No Encoding          | 6.71                  |\n\n- Here is the average ranking of each hypergraph encoding across GCN and GPS on graph regression tasks. Lower is better.\n\n| **Encoding**         | **Average Rank (↓)** |\n|----------------------|-----------------------|\n| Hodge H-20-LAPE      | 2.0                   |\n| Norm. H-20-LAPE      | 2.5                   |\n| EE H-19-RWPE         | 3.0                   |\n| EN H-19-RWPE         | 3.5                   |\n| HCP-FRC              | 3.5                   |\n| HCP-ORC              | 4.0                   |\n| No Encoding          | 7.0                   |\n\n- If the reviewer is interested in more specific tables (per specific model or modality), we are happy to provide these too.\n\n- Furthermore, we include similar tables that consider both graph and hypergraph encodings. Beside LCP-ORC, which is expensive to compute, all hypegraphs encodings have a lower average rank. The lowest average rank is still achieved using EE RWPE and EN RWPE.\n\n- We also include better formatting of our tables (best encoding in bold, the second best underlined) and we also include ties to highlight the best encoding while taking into consideration the 1 std bands.\n\n> The runtime needed to compute all the different encodings is not (neither theoretically nor empirically) shown.\n\n- Please note that we do provide theoretical complexity analyses for our encodings. The complexity analysis for the H-LDP was missing (thank you for pointing this out) but has now been added. Additional empirical runtime results which we will include in the paper can be found below. For every dataset, we compute the average time needed to compute the encodings on the hypergraphs. If the dataset is a graph dataset, we also include the time needed to lift graphs to hypergraphs, and the time needed to compute the graph encodings. Below are the runtimes for IMDB (the mean ± std are in seconds) on original graphs and clique-lifted hypergraphs:\n\n| **Encoding Method**     | **Encodings on original graphs** | **Encodings on Lifted hypergraphs** |\n|-------------------------|----------------------------------|-------------------------------------|\n| EN 19-RWPE & EN H-19-RWPE        | 0.0007 ± 0.0009                  | 0.0006 ± 0.0008                     |\n| LCP-FRC & HCP-FRC          | 0.0009 ± 0.0005                  | 0.0007 ± 0.0003                     |\n| LDP & HDP                  | 0.0010 ± 0.0005                  | 0.0010 ± 0.0005                     |\n| Hodge 20-LAPE & Hodge H-20-LAPE         | 0.0014 ± 0.0022                  | 0.0003 ± 0.0002                     |\n| Norm. 20-LAPE & Norm. H-20-LAPE    | 0.0075 ± 0.0113                  | 0.0007 ± 0.0003                     |\n| EE 19-RWPE & EE H-19-RWPE          | 0.0182 ± 0.0397                  | 0.0022 ± 0.0031                     |\n| LCP-ORC & HCP-ORC          | 5.1573 ± 0.1235                  | 5.1990 ± 0.0994                     |\n\n- The average time needed to lift the graph to hypergraphs is 0.0003s ± 0.0005s. Below are the runtimes on Citeseer:\n\n| Encoding Method         | Citeseer-CC |\n|-------------------------|-------------|\n| HCP-FRC                 | 0.0710      |\n| H-LDP                   | 0.0906      |\n| Normalized H-20-LAPE    | 0.9175      |\n| EN H-19-RWPE            | 2.8710      |\n| Hodge H-20-LAPE         | 2.8988      |\n| HCP-ORC*                | 13.6736     |\n| EE H-19-RWPE            | 183.6963    |\n\n- Note that we only need to do this one before training, and that our Python code is not optimized. HCP-ORC calls a julia routine.\n\n> Other comments\n\n- Thank you for pointing these out, we have addressed all of these comments in our revised version of the paper.\n\n> Which of the encodings should be used? Can you say anything about which one might be better depending on the dataset?\n\n- Please refer to table above.\n\n> What is the computational complexity of all the proposed encodings (there are some missing an analysis)? What was the runtime for computing them in practice?\n\n- The complexity analysis of the H-LDP was indeed missing. Thank you for pointing this out. We have now included the following statement to make up for this:\n\nComputing H-LDP scales as $O(|F|f_{max})$, where F is the hyper-edges set and $f_{max}$ is the size of the biggest hyper-edge. We only need to count the degree for each node and save the statistics of 1-neighborhood for each node.\n\n- For the runtime, please see our earlier response.\n\n> For hypergraphs: As stated in the discussion section, it seems there is not really data available that is naturally represented as hypergraphs. At first glance, it does not seem to be useful then, or am I missing something?\n\n- We do believe that there are datasets that can be naturally thought of as hypergraphs, especially social interaction networks such as IMDB.  Our comment in the discussion was meant to illustrate that more datasets that contain multi-way interactions would be extremely valuable for the topological deep learning community. We will revise the corresponding paragraph to make this clearer.\n\n> For traditional graphs: In the experimental evaluation, the encodings outperform the models without encoding. However, they are not compared to state-of-the-art GNNs, so this seems more like an ablation study. Can you comment on that?\n\n- Our goal here was to illustrate the benefits that standard graph neural networks that are most likely to be used in practice can obtain from capturing higher-order information, not to beat benchmarks, similar to [1] and [2]. We would also like to slightly push back against the notion that GCN or GIN are not *state-of-the-art*, as these architectures have recently been shown to still be competitive with more recent GNNs, including sophisticated graph transformers [3].\n\n> Why are the last three entries in Equation 8 (and in LDP) repeated?\n\n- This was indeed a typo, which has now been fixed. Equation 9 also suffered from the same typo and has also been fixed. We consider the min, max, mean, median, and std values of the CMS (Eq 8) or of the multi-set of node degrees.\n\n[1] Fesser, L. and Weber, M., Effective Structural Encodings via Local Curvature Profiles. In The Twelfth International Conference on Learning Representations.\n\n[2] Nguyen, K., Hieu, N.M., Nguyen, V.D., Ho, N., Osher, S. and Nguyen, T.M., 2023, July. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning (pp. 25956-25979). PMLR.\n\n[3] Luo, Y., Shi, L. and Wu, X.M., Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence. In Forty-second International Conference on Machine Learning."}, {"review_id": "3XNZBOk1ac", "reviewer": "Reviewer_6gkV", "summary": "The paper works on hypergraphs and neural networks for them. The main contribution is the lifting of common positional and structural encodings from graphs to hypergraphs for which they claim that they are always superior to their graph counterpart, even though all datasets are lifted graph datasets (mostly because there are no true hypergraph datasets available).", "questions": "1) How do a pure GT and MLP react to the hypergraph embeddings? \n\n2) Do the main results (i.e. hypergraph variant is always better than \"normal\" one) carry over when getting closer to SOTA results?  E.g. there seems to be diminishing returns for GIN which starts with a higher performance.\n\n3) What is the main difference between UniGCNII and a model such as HGNN which reports a lot better results on cora and pubmed? (on pubmed a simple GCN is stronger than any of the hypergraph networks)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\nThe main strength is a clear and lifting procedure for the structural and positional embeddings, allowing them to make sense of hyperedges. The experiments indicate that each hypergraph-lifted encoding is always better than the corresponding graph-level encoding. The paper is well-written and easy to follow.\n\n**Weaknesses:**\nmostly the experimental evaluation. While the authors (roughly) claim that \"holding the parameter constant makes everything more fair\", I strongly disagree with this claim. In the experiments, the absolute performance of the models is also really low and for example a simple HGNN from 2019[1] achieves significantly higher performance than any of the models in this paper. I would have expected this model to be a baseline. \n\nMy main problem with the experiments is that the provided results are not representative of the model for each of the datasets and thus the performance gains through additional encodings could behave entirely different when performing a small hyperparameter search based on a generally good architecture. Instead of reporting 50 trained models for each dataset, reporting the average of 5 while using the other 45 for hyperparameter tuning would be much preferred by me.\n\nI would also like to see a plain graph transformer and a simple MLP as baselines as both architectures rely only on encodings to learn about the graph/hypergraph structure. \n\n\n** further detailed comments**\n- please use booktabs.\n- In general, the tables are hard to read and it is not directly clear what they show - maybe it is possible to make a plot that directly compares each PE with its lifted variant?\n- having only the \"best\" value in bold but not everything within $1\\sigma$ or with overlapping standard deviations is problematic as it indicates that there is a single best model while this is not significant and actually multiple models are equally good.\n- it could be made more clear that there are settings where both graphs and hypergraphs are used \"together\"\n- 306: with encodings (e.g. LapPE) there is no difference in expressiveness between any of the models (at least in terms of non-uniform expressivity). GPS internally uses GIN, so it should not be worse-off. It would be nice that all those expressiveness results only hold in the regime without encodings.\n- Leman is written without h.\n- 65ff: message passing only sometimes add self-loops while the formula assumes that this is always the case.\n- 74: maybe also cite a second one here such as LGI-GT [2] that follows up on GPS\n- 91: as encodings are crucial for graph transformers, I would have expected this to be much more prominent here. I was also surprised to find RWSE later but not in this paragraph.\n\n\n[1] Hypergraph Neural Networks, Feng et al. AAAI 2019\n[2] LGI-GT: Graph Transformers with Local and Global Operators Interleaving, Yin and Zhong IJCAI-23", "was_revised": true, "final_justification": "The weaknesses (especially the experimental evaluation) has been thoroughly addressed in the rebuttal and the updated experiments support the claims of the paper well. Doing the promised changes is well possible within the time until the camera ready version.", "rebuttal": "## General response\n\nDue to the character limit, please see reviewer [UZHC] for our general response. We apologize for the inconvenience.\n\n**We now address each of the reviewer's comments and questions individually:** \n\n> mostly the experimental evaluation. While the authors (roughly) claim that \"holding the parameter constant makes everything more fair\", I strongly disagree with this claim. [...].\n\n- We thank the reviewer for voicing their concerns. Our experimental evaluation was indeed meant to ensure fairness and followed [1] and [2].\n- We see where the reviewer's skepticism is coming from  and provide additional results with hyperparameter tuning below. We will include both results, along with further hyperparameter searches for all models.\n- To select the hyperparameters for these additional experiments, we conducted a grid search over the following hyperparameters: num. layers $\\in \\{4, 6, 8\\}$, hidden dim $\\in \\{64, 128\\}$, learning rate $\\in \\{0.01, 0.001\\}$, and dropout $\\in \\{0.25, 0.5\\}$. For the configuration with the highest validation accuracy, we provide the average test accuracy over five random seeds in the table below (standard deviations are therefore slightly larger). We refer the reviewer to the updated GCN table in the response to reviewer [GZBz] due to the character limit.\n\n- For the node classifications tasks on hypergraph-level datasets, we clarify that: A- the choice of UniGCN in table 1 is meant as a direct comparison between GCN and UniGCN; B - we use the same data and splits as in UniGNN [4] - we are performing semi-supervised hypernode classification, with a small percentage of hypernodes used for training.\n- While [5] reports 80.1% on pubmed (table 2), our choice was originally motivated because [4] seems to indicate that UniGNN and UniGNNII achieve better accuracies on our particular train/test/validation splits. Please see Table 1 and 3 in UniGNN [4]: UniGNN and UniGNNII are superior to HGNN  on this task. [6] presents similar numbers for HGNN. We will provide the experiments with HGNN in the discussion period.\n\n- We are also adding more hypergraph-based models (eg PhenomNN [7]) to address the point raised by the reviewer. We still find that the model does not benefit from any of our hypergraph-level encodings, which we believe indicate that this is a more general phenomenon affecting HGNNs more broadly.\n\n| **Model**| **citeseer-CC**| **cora-CA**| **cora-CC**        | **pubmed-CC**      |\n|----------------------------------|--------------------|--------------------|--------------------|--------------------|\n| PhenomNN (no encodings)| 64.96 ± 0.58       | 76.98 ± 0.41   | 72.27 ± 0.41       | 78.09 ± 0.24       |\n| PhenomNN (HCP-ORC)| 64.89 ± 0.45       | 75.93 ± 0.41       | 72.21 ± 0.31       | 77.37 ± 0.23       |\n| PhenomNN (LDP)| 62.54 ± 0.52| 75.67 ± 0.50       | 62.28 ± 3.33       | 70.63 ± 0.87       |\n| PhenomNN (Hodge H-20-LAPE)       | 64.98 ± 0.58   | 76.76 ± 0.71       | 72.18 ± 0.33       | 78.36 ± 0.23   |\n| PhenomNN (H-20-RWPEE EN)         | 64.47 ± 0.62       | 76.39 ± 0.57       | 71.57 ± 0.73       | 78.10 ± 0.20       |\n\n> My main problem with the experiments is that the provided results are not representative of the model for each of the datasets [...].\n\n- We hope that the additional results after careful hyperparameter tuning presented above alleviate the reviewer's concerns. We would be happy to provide additional results using GIN, GPS, or another model the reviewer might be interested in during the discussion period.\n\n> I would also like to see a plain graph transformer and a simple MLP as baselines [...].\n\n- Please find additional results with an MLP and GT below. Hyperparameters were again obtained using grid search as above.\n- We would be happy to provide additional results using other datasets during the discussion period.\n\n| Model (Encodings)| Collab (↑)| Imdb (↑)| Reddit (↑)|\n|----------------------------|-----------------|-----------------|-----------------|\n| MLP (No Encoding)| 51.80 ± 1.55    | 48.26 ± 1.98    | 49.08 ± 1.92    |\n| MLP (LCP-FRC)| 64.09 ± 1.51    | 48.96 ± 2.40    | 71.36 ± 3.26    |\n| MLP (LCP-ORC)| 67.86 ± 1.94    | 63.26 ± 3.13    | 76.04 ± 2.08    |\n| MLP (19-RWPE)              | 50.21 ± 2.32    | 49.37 ± 2.15    | 72.19 ± 2.05    |\n| MLP (20-LAPE)              | 57.12 ± 1.77    | 49.19 ± 1.48    | 74.53 ± 1.67    |\n| MLP (HCP-FRC)              | 68.45 ± 1.62    | 60.22 ± 2.07    | 78.33 ± 2.12    |\n| MLP (HCP-ORC)              | 67.90 ± 1.58    | 62.88 ± 1.85    | 77.46 ± 2.29    |\n| MLP (EE H-19-RWPE)         | 66.14 ± 1.73    | 68.37 ± 1.73    | 79.17 ± 1.62    |\n| MLP (Hodge H-20-LAPE)      | 66.71 ± 1.45    | 66.84 ± 1.91    | 76.48 ± 1.83    |\n\n| Model (Encodings)| Collab (↑)      | Imdb (↑)        | Reddit (↑)      |\n|-----------------------------|-----------------|-----------------|-----------------|\n| GT (No Encoding)| 53.07 ± 1.52    | 49.56 ± 1.28    | 51.04 ± 1.14    |\n| GT (LCP-FRC)| 69.13 ± 2.06    | 50.24 ± 2.15    | 75.93 ± 1.80    |\n| GT (LCP-ORC)| 70.46 ± 1.84    | 61.45 ± 2.03    | 78.42 ± 1.79    |\n| GT (19-RWPE)| 60.39 ± 2.33    | 61.94 ± 2.12    | 77.03 ± 2.18    |\n| GT (20-LAPE)| 61.87 ± 2.21    | 60.92 ± 2.24    | 78.31 ± 2.27    |\n| GT (HCP-FRC)| 70.88 ± 1.01    | 60.83 ± 1.16    | 80.02 ± 2.12    |\n| GT (HCP-ORC)| 69.12 ± 1.17    | 66.44 ± 1.48    | 80.34 ± 2.30    |\n| GT (EE H-19-RWPE)| 68.14 ± 1.09    | 70.79 ± 1.37    | 81.57 ± 2.24    |\n| GT (Hodge H-20-LAPE)| 67.38 ± 0.92    | 70.58 ± 1.42    | 80.28 ± 2.21    |\n\n> please use booktabs.\n\n- Thank you for pointing us to the package. We have updated our tables.\n\n> In general, the tables are hard to read and it is not directly clear what they show [...].\n\n- Great suggestion. A plot for each of table 2 and 3, with accuracies plotted on the y-axis has been added.\n- It is indeed our intent with table 2 and table 3 to compare PEs to their lifted variants. We refer the reviewer to the response to reviewer [Ej7N] where we add average ranking of each encodings.\n\n> having only the \"best\" value in bold but not everything within\n or with overlapping standard deviations is problematic [...] multiple models are equally good.\n\n- This is a great point. We have now added a scheme where we underline the encodings that fall in the $\\pm 1 std$ band of the best encodings accuracy. These suggest more clearly that on graph-classification tasks, RWPE should be used and that on graph regression tasks and node classification tasks, H-LAPE should be used.\n\n> it could be made more clear that there are settings where both graphs and hypergraphs are used \"together\"\n\n- Could the reviewer clarify this point? We do compute graph-based and hypergraph-based encodings (on the graphs' liftings) to compare these side by side after passing them through various models for training. However, we do not believe our method jointly uses graphs and hypergraphs in the same model.\n\n> 306: with encodings (e.g. LapPE) there is no difference in expressiveness between any of the models (at least in terms of non-uniform expressivity). GPS internally uses GIN, so it should not be worse-off. It would be nice that all those expressiveness results only hold in the regime without encodings.\n\n- We have adjusted that line to reflect that in the WL hierarchy, GIN is not necessarily more expressive than GPS.\n- This is indeed an interesting point. Our table 14 (682ff) does suggest that the different expressiveness results only hold in the regime without encodings: we have clarified the text.\n\n> Leman is written without h.\n\n- Thank you. The text is updated.\n\n> 65ff: message passing only sometimes add self-loops [...].\n\n- Thank you for noting this and apologies for the oversight. We have updated this.\n\n> 74: maybe also cite a second one here such as LGI-GT [2] that follows up on GPS\n\n- Thank you for this suggestion. We have added this citation.\n\n> 91: as encodings are crucial for graph transformers, I would have expected this to be much more prominent here. [...]\n\n- Thank you for this suggestion. We have changed this paragraph to mention the importance of encodings for graph transformers as well as MPGNNs. Although we do mention random-walk based node similarities, these encodings are now mentioned explicitly in the paragraph.\n\n> How do a pure GT and MLP react to the hypergraph embeddings?\n\n- Please see additional results above.\n\n> Do the main results (i.e. hypergraph variant is always better than \"normal\" one) carry over when getting closer to SOTA results? E.g. there seems to be diminishing returns for GIN which starts with a higher performance.\n\n- Please see additional results above/ the response to reviewer [GZBz].\n\n> What is the main difference between UniGCNII and a model such as HGNN [...]\n\n- We added two additional baselines, including a recent one (PhenomNN) and based in the figures reported in the literature, we are close to SOTA on the hypernode classifications using UniGNNII.\n- The overall insight that we are reporting - HGNNs do not benefit from hypergraph encodings- still stands.\n\n[1] Fesser, Weber, Effective Structural Encodings via Local Curvature Profiles. In The Twelfth International Conference on Learning Representations.\n\n[2] Nguyen, Hieu, Nguyen, Ho, Osher, and Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning (pp. 25956-25979). PMLR.\n\n[3] Tönshoff, Ritzert, Rosenbluth, and Grohe. Where did the gap go? reassessing the long-range graph benchmark.\n\n[4] Huang & Yang. Unignn: a unified framework for graph and hypergraph neural networks.\n\n[5] Feng, You, Zhang, Ji, & Gao. Hypergraph neural networks.\n\n[6] Zhang, Li, Xiao, Xu, Rong, Huang, & Bian. Hypergraph convolutional networks via equivalency between hypergraphs and undirected graphs.\n\n[7] Wang, Gan, Qiu, Huang, & Wipf. From hypergraph energy functions to hypergraph neural networks."}, {"review_id": "r0WRqPfpl6", "reviewer": "Reviewer_GZBz", "summary": "This paper proposes a data augmentation approach for graph neural networks (GNNs) by introducing hypergraph-level encodings from hypergraph Laplacians and discrete curvature to capture higher-order structural information.\n\nThe authors theoretically demonstrate that these encodings enhance the representational power of GNNs.\n\nExperiments demonstrate improvements on various datasets, particularly when used with graph-level architectures applied to hypergraphs or lifted graphs.", "questions": "1. Is it possible that current hypergraph message-passing schemes (e.g., the two-stage node-to-hyperedge-to-node employed by UniGCN) inherently struggle to integrate such explicit, pre-computed node-level features effectively compared to how standard GNNs integrate them?\n2. Could the normalization or aggregation steps within these HNNs be inadvertently diminishing the unique information provided by the unnormalized encodings (as hinted at in Remark 3.14 regarding normalization obscuring differences)?\n3. What was the approximate pre-processing time for the encodings on representative datasets?\n4. How much did the size of the graph (nodes/edges) increase when lifted to a hypergraph (nodes/hyperedges/total incidence entries), and how did this impact subsequent GNN training time/memory compared to using only graph-level encodings or no encodings?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The paper provides theoretical analysis in the form of Theorems 3.2, 3.5, 3.11, 3.13, demonstrating that the proposed hypergraph-level encodings provably increase the representational power of GNNs. \n2. The authors provide an anonymized codebase and extensive appendices detailing architectures (Appendix B), datasets (Appendix C), hyperparameters (Appendix C.2), and further experimental results (Appendix D, G) and expressivity analysis (Appendix E, F).\n\n$~$\n\n### Weaknesses\n\n1. The experiments primarily focus on performance improvements over old models (e.g., GCN, UniGCN, GPS) and lack a comparison against state-of-the-art baselines, see surveys [1, 2]. Moreover, it is unclear from the paper how the demonstrated improvements compare against the current state-of-the art results on the respective datasets.\n2.   The observation that dedicated hypergraph neural networks (like UniGCN) do not benefit significantly from these hypergraph-level encodings is intriguing and counter-intuitive (lines 276-278, Appendix G). While the paper suggests it as an area for future work (lines 340-343), a more elaborated discussion or hypothesis in the main text about why this might be the case (e.g., are HNNs already implicitly capturing this, or are current message-passing schemes in HNNs not well-suited to integrate such explicit features?) would add depth.\n3. A more in-depth discussion of the practical computational overhead, especially for very large graphs leading to dense hypergraph expansions would be beneficial. An accuracy - run time trade-off analysis, including the pre-processing times, would significantly strengthen the paper's empirical contributions. \n\n$~$\n\nReferences\n1. A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide, In KDD 2024.\n2. A Survey of Graph Transformers: Architectures, Theories and Applications, In arXiv 2502.16533.", "was_revised": true, "final_justification": "After considering the rebuttal and discussions, I acknowledge that several concerns were addressed by the authors. The theoretical analysis is well-supported, preprocessing overhead is minor, and clearly quantified. Extensive experiments in the rebuttal demonstrate thoughtful and transparent empirical validation.", "rebuttal": "## General response\n\nDue to the character limit, please see reviewer [UZHC] for our general response. We apologize for the inconvenience.\n\n**We now address each of the reviewer's comments and questions individually:** \n\n> The experiments primarily focus on performance improvements over old models (e.g., GCN, UniGCN, GPS) and lack a comparison against state-of-the-art baselines [...] it is unclear from the paper how the demonstrated improvements compare against the current state-of-the art results on the respective datasets.\n\n- Thank you for voicing this concern. As mentioned in the general response, the GNNs we consider such as GCN and GIN have recently been shown to still outperform many newer models, including GTs, in both node- and graph-level tasks [1], [2], [3]. Using the hyperparameters provided in [3] or, when those are unavailable, using a more extensive hyperparameter search, we significantly increase the performance of GCN on all graph-level datasets and come within range of more advanced models such as GRIT [4] and GraphViT [5] on peptides-func and peptides-struct.\n\n|GCN+Encodings|Collab (↑)|Imdb (↑)|Reddit (↑)|Enzymes (↑)|Proteins (↑)|Peptides-f (↑)|Peptides-s (↓)|\n|---|---:|---:|---:|---:|---:|---:|---:|\n|(No Encoding)|62.69 ± 2.02|50.04 ± 2.23|68.45 ± 2.36|29.93 ± 2.64|72.00 ± 2.85|0.662 ± 0.012|0.259 ± 0.007|\n|(LCP-FRC)|70.26 ± 2.57|65.08 ± 2.65|80.26 ± 2.12|29.59 ± 2.68|72.22 ± 1.67|0.660 ± 0.011|0.258 ± 0.006|\n|(LCP-ORC)|71.94 ± 2.07|68.35 ± 1.90|81.66 ± 1.87|34.79 ± 2.52|74.84 ± 1.60|0.677 ± 0.010|0.252 ± 0.004|\n|(19-RWPE)|50.83 ± 2.53|50.77 ± 2.98|80.50 ± 2.06|31.27 ± 1.63|72.98 ± 1.83|0.674 ± 0.011|0.249 ± 0.004|\n|(20-LAPE)|58.64 ± 2.19|49.19 ± 2.14|77.66 ± 2.35|28.72 ± 1.67|72.55 ± 1.81|0.669 ± 0.009|0.250 ± 0.005|\n|(HCP-FRC)|72.34 ± 1.61|65.25 ± 1.78|83.12 ± 1.83|32.24 ± 2.36|71.64 ± 1.79|0.665 ± 0.012|0.248 ± 0.006|\n|(HCP-ORC)|70.94 ± 2.15|67.21 ± 2.37|81.53 ± 2.28|33.71 ± 2.30|75.72 ± 1.95|0.681 ± 0.007|0.246 ± 0.007|\n|(EE H-19-RWPE)|71.36 ± 2.25|74.82 ± 2.06|82.88 ± 1.96|31.98 ± 2.11|75.38 ± 2.42|0.683 ± 0.008|0.245 ± 0.004|\n|(EN H-19-RWPE)|70.05 ± 1.88|74.42 ± 1.52|84.52 ± 1.38|31.92 ± 2.02|75.93 ± 2.57|0.680 ± 0.007|0.246 ± 0.005|\n|(Hodge H-20-LAPE)|71.03 ± 1.42|72.60 ± 2.37|79.80 ± 1.59|29.53 ± 1.60|74.68 ± 2.14|0.678 ± 0.007|0.247 ± 0.004|\n|(Norm. H-20-LAPE)|69.17 ± 1.43|71.33 ± 1.59|80.21 ± 2.12|31.42 ± 2.83|74.32 ± 1.30|0.684 ± 0.009|0.245 ± 0.006|\n\n- We would be happy to provide additional results using GIN, GPS, or another model the reviewer might be particularly interested in during the discussion period.\n\n- At the hypergraph-level, we provide additional results using PhenomNN [6], a HGNN that is closer to the state-of-the-art. However, we still find that the model does not benefit from any of our hypergraph-level encodings, which we believe might indicate that this is a more general phenomenon affecting HGNNs more broadly (as the reviewer also seemed to suspect). Below is the hypernode-level accuracy for hypergraphs using hypergraph encodings with PhenomNN. Mean accuracy (%) ± standard deviation over 10 train-test splits.\n\n|**PhenomNN + Encoding**|**citeseer-CC**|**cora-CA**|**cora-CC**|**pubmed-CC**|\n|---|---:|---:|---:|---:|\n|No encoding|64.96 ± 0.58|76.98 ± 0.41|72.27 ± 0.41|78.09 ± 0.24|\n|HCP-FRC|58.87 ± 1.03|74.03 ± 0.97|54.02 ± 2.06|68.88 ± 1.44|\n|HCP-ORC|64.89 ± 0.45|75.93 ± 0.41|72.21 ± 0.31|77.37 ± 0.23|\n|LDP|62.54 ± 0.52|75.67 ± 0.50|62.28 ± 3.33|70.63 ± 0.87|\n|Hodge H-20-LAPE|64.98 ± 0.58|76.76 ± 0.71|72.18 ± 0.33|78.36 ± 0.23|\n|Norm. H-20-LAPE|64.75 ± 0.52|76.64 ± 0.49|72.06 ± 0.68|78.27 ± 0.25|\n|H-20-RWPEE EE|64.23 ± 0.40|76.24 ± 0.57|72.18 ± 0.52|77.97 ± 0.29|\n|H-20-RWPEE EN|64.47 ± 0.62|76.39 ± 0.57|71.57 ± 0.73|78.10 ± 0.20|\n|H-20-RWPEE WE|64.52 ± 0.69|76.54 ± 0.57|72.30 ± 0.79|78.06 ± 0.24|\n\n> The observation that dedicated hypergraph neural networks (like UniGCN) do not benefit significantly from these hypergraph-level encodings is intriguing [...] a more elaborated discussion or hypothesis in the main text about why this might be the case [...] would add depth.\n\n- Thank you very much for raising this important point. We agree that this is indeed a very interesting point. We suspect that since hypergraph layers already process the full incidence structure, the co-incidence statistics that, for example, our Hodge encodings add are largely redundant: most of that signal is already available to the architecture. By contrast, a standard graph GNN sees only pairwise edges; the encodings inject complementary higher-order cues it would otherwise miss, hence the larger gains. We believe that this intuition could be made rigorous using techniques similar to [7], which operates at the graph level, but given the length and complexity of their arguments, we consider this beyond the scope of the current paper.\n\n> A more in-depth discussion of the practical computational overhead [...] would significantly strengthen the paper's empirical contributions.\n\n- Thank you very much for raising this important point. Please note that the lifting of graphs to hypergraphs (if working on graph data) and the computing of encodings is a pre-processing step applied only once before feeding the feature matrix to models. No further computations are needed during training. The empirical runtime results have been added in the paper, and some can be found below. For every dataset, we compute the average time needed to compute the encodings on the hypergraphs. If the dataset is a graph dataset, we also include the time needed to lift graphs to hypergraphs, and the time needed to compute the graph encodings. Below are the runtimes for IMDB (the mean ± std are in seconds) on original graphs and clique-lifted hypergraphs:\n\n|Encoding Method|Encodings on original graphs|Encodings on Lifted hypergraphs|\n|---|---:|---:|\n|EN 19-RWPE & EN H-19-RWPE|0.0007 ± 0.0009|0.0006 ± 0.0008|\n|LCP-FRC & HCP-FRC|0.0009 ± 0.0005|0.0007 ± 0.0003|\n|LDP & HDP|0.0010 ± 0.0005|0.0010 ± 0.0005|\n|Hodge 20-LAPE & Hodge H-20-LAPE|0.0014 ± 0.0022|0.0003 ± 0.0002|\n|Norm. 20-LAPE & Norm. H-20-LAPE|0.0075 ± 0.0113|0.0007 ± 0.0003|\n|EE 19-RWPE & EE H-19-RWPE|0.0182 ± 0.0397|0.0022 ± 0.0031|\n|LCP-ORC & HCP-ORC|5.1573 ± 0.1235|5.1990 ± 0.0994|\n\n- The average time needed to lift the graph to hypergraphs is 0.0003s ± 0.0005s. Note that our Python code is not optimized. Below are the runtimes on Citeseer:\n\n|Encoding Method|Citeseer-CC|\n|---|---:|\n|HCP-FRC|0.0710|\n|H-LDP|0.0906|\n|Normalized H-20-LAPE|0.9175|\n|EN H-19-RWPE|2.8710|\n|Hodge H-20-LAPE|2.8988|\n|HCP-ORC*|13.6736|\n|EE H-19-RWPE|183.6963|\n\n- Note that HCP-ORC calls a julia routine.\n\n> Is it possible that current hypergraph message-passing schemes [...] inherently struggle to integrate such explicit, pre-computed node-level features effectively compared to how standard GNNs integrate them?\n\n- Please see the response above.\n\n> Could the normalization or aggregation steps within these HNNs be inadvertently diminishing the unique information provided by the unnormalized encodings [...]?\n\n- Thank you for these questions. **Normalization:** We ran the experiments for UniGNN [1] without normalizing the encodings (we also ran the experiments with normalization, although they are not reported in the paper - the performance differences where within standard deviations). In the graph case, we don't normalize the features before the first layer at all. **Aggregation:** We originally suspected that oversmoothing might be to blame here, i.e. node features becoming increasingly similar with depth, thereby washing out the information provided by the encodings. We do not believe that this is the case though because 1) the HGNNs we use are not very deep (always less than 10 layers) and 2) some of the HGNNs we consider were specifically designed to avoid oversmoothing, such as UniGCN, which suffers minimal performance drops with 64 layers compared to 4 layers, for example.\n\n> How much did the size of the graph (nodes/edges) increase when lifted to a hypergraph [...]?\n\n- The size of the set of vertices remains unchanged when we lift a graph to a hypergraph, because, in our setting we lift graphs to hypergraphs by adding hyperedges to groups of nodes that are pairwise interconnected. Thus the set of vertices of the hypergraph is the same as the set of vertices of the original graph. The number of hyperedge in the lifted hypergraph is at most the number of edges in the original graph.\n\n[1] Luo, Y., Shi, L. and Wu, X.M., Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence. In Forty-second International Conference on Machine Learning.\n\n[2] Luo, Y., Shi, L. and Wu, X.M., 2024. Classic gnns are strong baselines: Reassessing gnns for node classification. Advances in Neural Information Processing Systems, 37.\n\n[3] Tönshoff, J., Ritzert, M., Rosenbluth, E. and Grohe, M., Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. In The Second Learning on Graphs Conference.\n\n[4] Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P.K., Coates, M., Torr, P. and Lim, S.N., 2023, July. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning. PMLR.\n\n[5] He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y. and Bresson, X., 2023, July. A generalization of vit/mlp-mixer to graphs. In International conference on machine learning. PMLR.\n\n[6] Wang, Y., Gan, Q., Qiu, X., Huang, X. and Wipf, D., 2023, July. From hypergraph energy functions to hypergraph neural networks. In International Conference on Machine Learning. PMLR.\n\n[7] Kanatsoulis, C., Choi, E., Jegelka, S., Leskovec, J. and Ribeiro, A., Learning Efficient Positional Encodings with Graph Neural Networks. In The Thirteenth International Conference on  Learning Representations."}]

Author rebuttal:

Meta-review: This paper introduces a data-centric approach to capture higher-order relationships in graphs by augmenting node features with novel hypergraph-level encodings derived from Laplacians, curvature, and random walks.

The work's primary strengths are its novel and provably expressive hypergraph encodings and an extensive experimental evaluation showing these encodings significantly boost the performance of standard GNNs. Some concerns are the limited performance gain when applying these encodings to native hypergraph neural network architectures and a theoretical proof framework whose assumptions were debated by one reviewer. The discussion period was effective, with the authors running numerous new experiments that resolved the most critical initial weaknesses. Concerns about weak experimental baselines and lack of hyperparameter tuning were fully addressed with new results and additional MLP/GT baselines. The authors also provided detailed runtime analysis and addressed multiple presentation issues. This effort led three of the four reviewers to raise their scores. The primary debatable point is a technical disagreement with one reviewer about the assumptions underlying the expressivity proofs in continuous feature spaces. Nevertheless, the consensus shifted strongly in favor of acceptance due to the strengthened empirical evidence. Therefore, I recommended acceptance.
Decision: Accept (poster)