Higher-Order Learning with Graph Neural Networks via Hypergraph Encodings

General response

Due to the character limit, please see reviewer [UZHC] for our general response. We apologize for the inconvenience.

We now address each of the reviewer's comments and questions individually:

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.

• 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.

• 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.

• 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.

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.

• 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.

A more in-depth discussion of the practical computational overhead [...] would significantly strengthen the paper's empirical contributions.

• 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:

• 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:

• Note that HCP-ORC calls a julia routine.

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?

• Please see the response above.

Could the normalization or aggregation steps within these HNNs be inadvertently diminishing the unique information provided by the unnormalized encodings [...]?

• 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.

How much did the size of the graph (nodes/edges) increase when lifted to a hypergraph [...]?

• 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

General response

Due to the character limit, please see reviewer [UZHC] for our general response. We apologize for the inconvenience.

We now address each of the reviewer's comments and questions individually:

mostly the experimental evaluation. While the authors (roughly) claim that "holding the parameter constant makes everything more fair", I strongly disagree with this claim. [...].

• We thank the reviewer for voicing their concerns. Our experimental evaluation was indeed meant to ensure fairness and followed [1] and [2].

• 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.

• 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.

• 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.

• 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.

• 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.

My main problem with the experiments is that the provided results are not representative of the model for each of the datasets [...].

• 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.

I would also like to see a plain graph transformer and a simple MLP as baselines [...].

• Please find additional results with an MLP and GT below. Hyperparameters were again obtained using grid search as above.
• We would be happy to provide additional results using other datasets during the discussion period.

please use booktabs.

• Thank you for pointing us to the package. We have updated our tables.

In general, the tables are hard to read and it is not directly clear what they show [...].

• Great suggestion. A plot for each of table 2 and 3, with accuracies plotted on the y-axis has been added.
• 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.

having only the "best" value in bold but not everything within or with overlapping standard deviations is problematic [...] multiple models are equally good.

• 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.

it could be made more clear that there are settings where both graphs and hypergraphs are used "together"

• 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.

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.

• We have adjusted that line to reflect that in the WL hierarchy, GIN is not necessarily more expressive than GPS.
• 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.

Leman is written without h.

• Thank you. The text is updated.

65ff: message passing only sometimes add self-loops [...].

• Thank you for noting this and apologies for the oversight. We have updated this.

74: maybe also cite a second one here such as LGI-GT [2] that follows up on GPS

• Thank you for this suggestion. We have added this citation.

91: as encodings are crucial for graph transformers, I would have expected this to be much more prominent here. [...]

• 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.

How do a pure GT and MLP react to the hypergraph embeddings?

• Please see additional results above.

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.

• Please see additional results above/ the response to reviewer [GZBz].

What is the main difference between UniGCNII and a model such as HGNN [...]

• 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.
• The overall insight that we are reporting - HGNNs do not benefit from hypergraph encodings- still stands.

[1] Fesser, Weber, Effective Structural Encodings via Local Curvature Profiles. In The Twelfth International Conference on Learning Representations.

[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.

[3] Tönshoff, Ritzert, Rosenbluth, and Grohe. Where did the gap go? reassessing the long-range graph benchmark.

[4] Huang & Yang. Unignn: a unified framework for graph and hypergraph neural networks.

[5] Feng, You, Zhang, Ji, & Gao. Hypergraph neural networks.

[6] Zhang, Li, Xiao, Xu, Rong, Huang, & Bian. Hypergraph convolutional networks via equivalency between hypergraphs and undirected graphs.

[7] Wang, Gan, Qiu, Huang, & Wipf. From hypergraph energy functions to hypergraph neural networks.

General response

Due to the character limit, please see reviewer [UZHC] for our general response. We apologize for the inconvenience.

We now address each of the reviewer's comments and questions individually:

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.

• 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.
• 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.

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.

• 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:

• 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:

• Here is the average ranking of each hypergraph encoding across GCN and GPS on graph regression tasks. Lower is better.

• If the reviewer is interested in more specific tables (per specific model or modality), we are happy to provide these too.

• 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.

• 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.

The runtime needed to compute all the different encodings is not (neither theoretically nor empirically) shown.

• 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:

• The average time needed to lift the graph to hypergraphs is 0.0003s ± 0.0005s. Below are the runtimes on Citeseer:

• 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.

Other comments

• Thank you for pointing these out, we have addressed all of these comments in our revised version of the paper.

Which of the encodings should be used? Can you say anything about which one might be better depending on the dataset?

• Please refer to table above.

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?

• 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:

Computing 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.

• For the runtime, please see our earlier response.

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?

• 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.

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?

• 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].

Why are the last three entries in Equation 8 (and in LDP) repeated?

• 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.

[1] Fesser, L. and Weber, M., Effective Structural Encodings via Local Curvature Profiles. In The Twelfth International Conference on Learning Representations.

[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.

[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.

General response

Thank 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].

We now highlight a few important points raised by reviewers that we address in our rebuttal:

• 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).
• 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.
• 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.
• We have added pre-processing runtimes (for lifting graph to hypergraphs, and for computing encodings).

We believe that these additions have made the paper significantly better and more accessible and thank the reviewers again for their input.

[*] 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.

[+] 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.

We now address each of the reviewer's comments and questions individually:

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?

• 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.

• 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.

Encodings improve graph-level models but not hypergraph architectures. This discrepancy is noted but not analyzed.

• 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.

All proofs of expressive power are conducted within BREC datasets. Given so, the theoretical contributions can be limited.

• 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.

It would be better to provide a formal point of view of the term higher-order information and hypergraph-level encoding.

• Please see response above.

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.

• 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.
• 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.

[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.

[2] Fesser, L. and Weber, M., Effective Structural Encodings via Local Curvature Profiles. In The Twelfth International Conference on Learning Representations.

[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.

Better avoid the term "High-order information" in the title if it lacks a formal definition, though the author explains it is somehow encoded with a hyperedge.

We will revise the text to make it clearer to the reader what we mean by "higher-order information".

shares a similar design or corresponds to a simplified form of the existing models, such as [*]. [...]

We thank the reviewer for this point. We consider both the Hodge Laplacian, as well as the normalized Laplacian from [*] in all our experiments, e.g. "Norm H-20-LAPE" in Table 1. See Appendix A.4.1 for more details. We consider unweighted hyper-edges, so $W=I$. The combinatorial Hodge-Laplacian, originally introduced in [1], extends the graph Laplacian as a natural shift operator for hypergraphs [2,3]. The $k$-th combinatorial Hodge-Laplacian on simplicial complexes is $L_k = B_k^\top B_k + B_{k+1} B_{k+1}^\top$ $B_1=H$ in [*]. The quantity we use is $L_0=B_1 B_1^\top$ and $L_1=B_1^TB_1$ as for hypergraphs, we only have rank $0$ (nodes) and rank 1 (hyperedges) simplices, so $B_0=0$, $B_k=0, k>1$. The hypergraph Laplacian in [*] originates from the fact that node classification on hypergraphs can be viewed as a regularization framework:

\arg \min R_{emp}(f) + \Omega(f) $$ where $\Omega(f)$ is a regularizer defined on the hypergraph, $R_{\mathrm{emp}}(f)$ denotes the supervised empirical loss, and $f(\cdot)$ is the classification function. The regularizer $\Omega(f)$ is given by

\Omega(f) = \frac{1}{2} \sum_{e \in E} \sum_{{u,v} \subseteq V} \frac{\ h(u,e) , h(v,e)}{\delta(e)} \left( \frac{f(u)}{\sqrt{d(u)}} - \frac{f(v)}{\sqrt{d(v)}} \right)^2,

where $h(u,e)$ indicates the incidence between vertex $u$ and hyperedge $e$, $\delta(e)$ is the degree of hyperedge $e$, and $d(u)$ is the degree of vertex $u$. Then the normalized regularizer can be written as $ \Omega(f) = f^\top \Delta f. $ where: $$ \Delta = I - D_v^{-1/2} B_1 D_e^{-1} B_1^\top D_v^{-1/2}.

The convolution on hypergraphs in [*] can be formulated as:

$$Y = D_v^{-1/2} B_1 W D_e^{-1} B_1^\top D_v^{-1/2} X \Theta$$

Our goal is not to construct a new layer as in [*], but to augment the graph's features, as a generalization of graph-level encodings (e.g., [4, 5]). In the main text, we present results for the Hodge-Laplacian because on graphs, it reduces to the graph Laplacian - this makes it a natural choice for a comparison of graph- and hypergraph-level LAPE encodings. Empirically, the Hodge Laplacian-based encodings appear to slightly outperform the Normalized Laplacian ones. It is not obvious if this trend generally holds due to some inherent properties of the Laplacians, so we will include this as an area for future research.

In the proofs of Theorem 3.2 and 3.5 [...] there exist graph pairs that can be distinguished by H-k-, but cannot be distinguished by k- [...]. But is the first statement, "H-k-* is strictly more expressive than the 1-WL test", proved? Also, both statements seem trivial. "H-k-* is strictly more expressive than k-*" can be informative, but is missing.

In the proofs of theorem 3.2 and 3.5, we use pair 0 of the Basic category of BREC, which is 1-WL indistinguishable. Thus, the first statement follows from the fact that the general class of MPGNNs (GIN specifically) is as expressive as 1-WL [6]. To establish strictly better expressivity of MPGNNs (GIN) with hypergraph encodings, it is sufficient to identify a set of non-isomorphic graphs that cannot be distinguished by the 1-WL test, but that differ in their encodings. This is because MPGNNs are at most as powerful as 1-WL, but enrichment with more expressive hypergraph-level information allows for distinguishing these graphs. Note that some graph-level encodings are also more expressive than 1-WL (see, e.g., [7]).

We thank the reviewer for pointing out that our explanations could have been clearer. We have revised the text accordingly.

[*] Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019, July). Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence.

[1] Eckmann, B. (1944). Harmonische funktionen und randwertaufgaben in einem komplex. Commentarii Mathematici Helvetici, 17(1).

[2] Schaub, M. T., Zhu, Y., Seby, J. B., Roddenberry, T. M., & Segarra, S. (2021). Signal processing on higher-order networks: Livin’on the edge... and beyond. Signal Processing, 187.

[3] Lim, L. H. (2020). Hodge Laplacians on graphs. Siam Review, 62(3).

[4] Dwivedi, Luu, Laurent, Bengio, & Bresson, (2021). Graph neural networks with learnable structural and positional representations. arXiv:2110.07875.

[5] Dwivedi & Bresson. A generalization of transformer networks to graphs. In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021

[6] Xu, Hu, Leskovec, & Jegelka. (2018). How powerful are graph neural networks?. arXiv:1810.00826.

[7] Fesser & Weber, (2023). Effective structural encodings via local curvature profiles. arXiv:2311.14864.

Thank you for the quick response.

The reviewer is correct in highlighting the particular difficulties that come with a continuous feature space when providing a formal proof of Step 1. We agree that in this case, Step 1 must be stated independently of any claim about GIN. This might take the following general form:

Following the constructions in Principal Neighborhood Aggregation and Breaking the Expressive Bottlenecks of GNNs, we deterministically map every real-valued feature vector to a unique discrete token via an order-preserving injection $Z:\mathbb{R}^{d}\to\mathbb{N}$. The multiset $\{Z(x_{u})\}_{u\in\mathcal{N}(v)}$ is then processed by an injective SUM + MLP (or the degree-scaled SUM used in PNA), after which an injective MLP updates the node state. Because both $Z$ and the aggregator are injective on multisets, each round reproduces the exact 1-WL coloring, establishing $\text{H-k-\*} \succeq \text{1-WL}$ even in continuous feature spaces, where H-k-* denotes an MPGNN equipped with our hypergraph encoding.

We will incorporate this kind of argument in the final manuscript, thereby making the first part of the proof required for Theorems 3.2 and 3.5 explicit. We will also be sure to cite both Principal Neighborhood Aggregation and Breaking the Expressive Bottlenecks of GNNs and thank the reviewer for bringing up these papers.

We hope this clarifies Step 1 and are happy to address any further questions.