Improved Expressivity of Hypergraph Neural Networks through High-Dimensional Generalized Weisfeiler-Leman Algorithms

As mentioned before, I feel lukewarm about this paper. While it is a solid piece of work and may interest some researchers in the community, it lacks truly innovative contributions. Perhaps its main strength lies in the clear presentation of the extension of k-WL from graphs to hypergraphs, but I have doubts about whether this alone is sufficient to justify acceptance at ICML.

k-WL cannot be directly applied to hypergraphs. The two main challenges in generalizing k-WL to hypergraphs are: (1) how to initialize the features of k-tuples through sub-hypergraph extractions while ensuring degeneration to k-WL, and (2) how to construct k-tuple hypergraphs from the original hypergraphs so that 1-GWL can be applied. Our key findings include: (a) establishing a Generalized WL hierarchy for hypergraphs with increasing expressivity, with the notable difference between 1-GFWL vs 2-GOWL, unlike its graph counterpart. (b) The hierarchy allows us to design hypergraph neural networks with the desired expressivity, improves upon most existing hypergraph neural networks whose expressive power is upper bounded by 1-GWL.

Q1. About the removal of singleton hyperedges: Does it mean that you allow no vertex colors in hypergraphs? Do you allow for repetition of vertices in hyperedges? Cannot you then encode a singleton hyperedge of the form (v) with (v,v)?

Thank you for the comments. We allow vertex colors/features in hypergraphs, such as the example of vertex colors 1 and 2 in Figure 3’s hard instances. In addition to removing singleton hyperedges, one could also consider adding the singleton hyperedge information as an extra vertex feature. However, the singleton hyperedges still need to be removed, ensuring that k-GWL can degenerate to k-WL for simple graphs, with consistent sub-hypergraphs and subgraphs. We treat hyperedges as sets and do not allow duplicate vertices in hyperedges. But we allow repetitions of vertices in k-tuples, which is discussed in our response to Reviewer eKNU.

Q2. Regarding your result that k-folklore and (k+1)-oblivious WL are equally expressive: I understand that this is a proper generalization of the result obtained by Grohe & Otto for graphs. But your proof seems considerably simpler. In fact, Grohe & Otto requires heavy machinery based on linear algebra and linear programming to obtain this result. Please compare your result against them and explain how you managed to obtain the results without extending their machinery.

Thank you for the good question. You are right that Grohe & Otto (2015) used heavy algebraic and linear programming methods to establish the equal expressivity between k-folklore and (k+1)-oblivious WL. Later, Grohe in his LICS'21 paper “The Logic of Graph Neural Networks” provided a considerably simpler less-than-one-page proof based on mathematical induction on iterations and analysis on the two variants’ computations. (See page 16 of https://arxiv.org/pdf/2104.14624, Proof of Theorem V.6 in Appendix.) We performed a careful adaptation of this simpler proof for hypergraphs, showing the equivalence of k-folklore and (k+1)-oblivious Generalized WL.

As mentioned before, I was struggling with lacking formality around sets, multisets, and tuples. Misleading examples. Injectivity and resulting equality in expressivity should only hold when its about tuples.

Thank you for the valuable comment. We should formally define tuples, multisets, and sets in k-GWL and will include the following definitions at the beginning of Section 4.1.

“Tuples are ordered and allow repetitive elements; multisets are unordered and allow repetitive elements; and sets are unordered and do not allow repetitive elements. In k-GWL, we consider k-tuples, which allow repetitions of vertices. There are two types of hypergraphs: the input hypergraph and the k-tuple hypergraph (see its construction in Section 4.1.2). Hyperedges in both types of hypergraphs are sets, that is unordered.”

We will add the following discussions on how to handle repetitions of vertices in k-tuples in Section 4. “Specifically, both k-GWL and k-WL allow repetitions of vertices in k-tuples. In the initialization of k-tuple features, they extract sub-hypergraphs and subgraphs induced by the set of vertices in k-tuples and then use the isomorphism type as features, where the set operation before extraction removes vertex repetitions. For the construction of k-tuple hypergraphs and k-tuple graphs, because tuples allow repetitions, the vertex replacement strategies in the oblivious and folklore variants ("all elements in one position" vs. "one element in all k positions") still work with no issues.”

For better illustrating the construction of k-tuple hypergraphs, we will plot a new version of Figure 3 based on k-tuples, where repetitions of vertices are considered. For example, the folklore hypergraph now includes five hyperedges instead of only two. The hyperedge with $v_1$ in all three positions of $(v_1,v_2,v_3)$ includes $(v_1,v_2,v_3)$, $(v_1,v_1,v_3)$, and $(v_1,v_2,v_1)$. The oblivious hypergraph still has three hyperedges but $e_1$ with all vertices in the first position of $(v_1,v_2,v_3)$ includes two extra k-tuples $(v_2,v_2,v_3)$ and $(v_3,v_2,v_3)$.

Last but not least, we will explicitly state that all our theoretical findings on the k-GWL hierarchy and equivalence of k-HNNs and k-GWL (theorems in Sections 5 and 6) are based on using k-tuples. The only place where we switch from k-tuples to k-sets is in the implementation of k-HNNs. Ignoring the vertex ordering and repetitions of vertices in k-tuples makes k-HNNs considerably more practical.

p5: it is only once mentioned indirectly how the hyperedges are included in the construction...

Thanks for bringing this issue to our attention. In Section 4, we will emphasize that the construction of k-tuple hypergraph in k-GWL does not depend on the set of hyperedges in the original hypergraph, which is only used in the isomorphism type. In Section 6, we will point out, unlike k-GWL, for k-HNNs based on local neighborhoods, the actual hyperedges of the input hypergraph do influence the construction of the k-tuple hypergraph.

sec 5.2: what is done about permutations...

Thank you for pointing out the issue. The original idea of relational pooling (that inspires $(k,l)$-WL) is to build expressive permutation-invariant models, where permutation invariance is obtained by averaging or summing over representations under all permutations of node IDs. Later on, local relational pooling performs permutation and averaging within a subgraph of size $l$ to reduce computational complexity. Similarly, $(k,l)$-WL assigns extra labels $1,2,\cdots,l$ to $l$ vertices, but runs k-WL on the whole graph with the additional labels only for those $l$ vertices. This is repeated for every possible labeled graph and then the final representation of the graph is aggregated from the representations of all labeled graphs. The extra vertex labels help boost expressivity. One can apply the same idea in k-GWL to get $(k,l)$-GWL. In the computational complexity, the term for the labelling should be $\binom{n}{l}^l$ (that is, select $l$ vertices from $n$ vertices and then assign $l$ labels to the $l$ vertices).

Other Comments Or Suggestions

Thank you for your detailed comments. We sincerely appreciate your efforts in helping enhance the presentation of this manuscript and will apply these comments.

sec 7: is it common to exclude original vertex features? And how do results change if you add them?

Keeping the original vertex features makes it easier to distinguish non-isomorphic hypergraphs, due to the potentially very different vertex features. Hence, it is a common practice to exclude these features and focus on structural information only. We used the datasets from (Feng et al., 2024), which performed the pre-processing. Unfortunately, they have not provided the original vertex features, but we expect the accuracy would be higher with original vertex features being added.

Analysis of underperformance in Wri-Genre

Please refer to the first response to Reviewer H4JM.

The number of parameters is not compared between baselines and the proposed models, which may lead to unfair comparison.

Thank you for the valuable comment. We have collected the number of parameters in all tested models and reported them in the table below. It can be observed that our k-HNN models use more than three times the parameters compared to several models, double the parameters of HNHN, but notably fewer parameters than AllSetTransformer. However, our proposed models and AllSetTransformer clearly outperform other baselines as shown in Table 1. For both graph and hypergraph deep learning, it is still an open problem on how to address the trade-off between expressive power and model complexity. In addition, we report the average time per epoch for all the models in Table 8 of Appendix E.5. The run-times of our methods are mostly smaller than double those of compared methods, while the vertex sampling approach can effectively reduce the run-time to be closer to that of other methods.

Note: k-HNNs have the same number of parameters for different values of k since they share the same neural network architecture.

Models corresponding to k-WL with k>2 should also be included.

A: In our experiments, we had access only to a normal GPU server with a 1080Ti GPU with 11GB memory. Due to limited GPU memory, we considered only the case of $k = 2$. However, we recently obtained access to a GPU cluster with 40GB memory and have run experiments using our k-HNNs for $k=3$ based on the vertex sampling strategy with sample size 10. As shown in the table in our response to Reviewer H4JM, 3-HNNs with the sampling show comparable performance to 2-HNNs across the datasets, while outperforming the previously best model AllSetTransformer in the IMDB-Wri-Genre dataset. We will run the full 3-HNNs without the sampling (when there is no rebuttal time limit) and expect higher accuracy and include the results in the paper.

The adaption of k-WL to hypergraph is too straightforward and lacks novelty.

k-WL cannot be directly applied to hypergraphs. The two main challenges in generalizing k-WL to hypergraphs are: (1) how to initialize the features of k-tuples through sub-hypergraph extractions while ensuring degeneration to k-WL, and (2) how to construct k-tuple hypergraphs from the original hypergraphs so that 1-GWL can be applied. Our key findings include: (a) establishing a Generalized WL hierarchy for hypergraphs with increasing expressivity, with the notable difference between 1-GFWL vs 2-GOWL, unlike its graph counterpart. (b) The hierarchy allows us to design hypergraph neural networks with the desired expressivity, improves upon most existing hypergraph neural networks whose expressive power is upper bounded by 1-GWL.

Text in figures are small and hard to read. Table 3 is too wide.

A: Thank you for the comment to help improve the presentation of the paper. We will adjust the figures and table accordingly.

Hypergraph can be bijectively mapping to a bipartite graph, with nodes and hyperedges in hypergraph as nodes in graph. Can we directly apply k-WL to this bipartite graph?

Thank you for the good question. One could transform hypergraphs to graphs via a bijective mapping, such as star expansion or line expansion [a], and then apply k-WL on the transformed graphs for isomorphism testing. However, even though the transformation is bijective, it does not guarantee the results of k-WL on the transformed graphs are the same as those of k-GWL on the original hypergraphs. For instance, we can find two non-isomorphic hypergraphs where k-GWL can distinguish them but k-WL cannot distinguish their transformed graphs. Figure 3(a) provides such an example: while 1-WL (equivalent to 2-OWL) fails to distinguish the transformed graphs, 2-GOWL successfully identifies the original hypergraphs. Therefore, this indirect method does not achieve the same expressive power as our k-GWL algorithm. We will include this observation in the final version.

Reference:

[a] Chaoqi Yang, Ruijie Wang, Shuochao Yao, and Tarek F. Abdelzaher. "Semi-supervised hypergraph node classification on hypergraph line expansion." In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 2352-2361. 2022.

The underperformance on IMDB-Wri-Genre suggests that certain hypergraph structures may not benefit from k-GWL, requiring further investigation.

Thank you very much for your comment. Following the suggestion of Reviewer yrE6, we have run experiments on k-HNNs for $k=3$ based on the vertex sampling strategy with sample size 10 in a GPU cluster with larger memory. As shown in the table below, 3-HNNs with the sampling show comparable performance to 2-HNNs across the datasets, while outperforming the previously best model AllSetTransformer in the Wri-Genre dataset. We will run the full 3-HNNs without the sampling (when there is no rebuttal time limit) and expect higher accuracy and include the results in the paper. We examined the dataset statistics in Table 5 of Appendix: there are six classes in Wri-Genre, which is significantly higher than in other datasets, making it a challenging dataset where every model seems to struggle. Moreover, in the two co-writer datasets (Wri-Genre and Wri-Type), there are significantly smaller number of hyperedges, with only about four hyperedges on average in a hypergraph, and each vertex participates in only 1.5 hyperedges on average. We was suspecting that the less amount of high-order information in the original hypergraph leads to a more dispersed construction of local neighbors between k-sets, which is not friendly to k-HNNs. However, the results of 3-HNNs with the sampling seem not support the thought.

It seems like [1] also discuss the expressivity of HNNs, but it is not cited by this paper.

Thank you for sharing the paper. We will ensure the following discussions are included in the final version.

“(Luo et al, 2022) studied the expressivity of hypergraph neural networks and constructed hierarchies of arity (the maximum number of vertices in hyperedges) and depth. For example, when the depth is larger than a certain value, a neural logic machine with a larger arity is more expressive. In contrast, this paper generalizes k-WL to k-GWL, unifies graph and hypergraph isomorphism tests, and establishes a clear expressivity hierarchy for hypergraphs.”

Comparison to Approximate WL Methods: How does k-GWL compare to randomized WL tests.

We could not find papers introducing randomized WL tests after a Google search but do our best to discuss it based on our understanding. Our models with the vertex sampling become an approximation of the original k-GWL, effectively saving run-time at the expense of slight decrease in prediction accuracy. Randomized/approximate WL seems orthogonal with our k-GWL and can be combined for better computational efficiency.

No training time comparisons—it is unclear how much additional overhead k-HNN introduces compared to existing models.
Training Time Comparison: Can you provide training time vs. existing HNNs? How much overhead does k-GWL introduce?

Sorry for not making the results of training time and their comparison easier to see. In Table 8 of Appendix E.5, we report the average time per epoch for different hypergraph learning models. The run-times of our k-HNN methods are mostly smaller than double those of other compared methods. The vertex sampling approach can effectively reduce run-time to be closer to that of other methods. For both GNNs and HNNs, it is still an open problem on how to further improve the trade-off between expressive power and run-time.

Can you explain more on the Definition 4.1? From my understanding, $s$ represents ID of nodes, then what does $s^1_{i_1} = s^1_{i_2}$ mean?

Sorry for the confusion. We use $s$ to represent a k-tuple and $s^1$ to represent a k-tuple in $HG_1$. The $i^{th}$ element in $s^1$ is referred to as $s_i^1$. $\forall i_1, i_2 \in [k], s^1_{i_1} = s^1_{i_2} \leftrightarrow s^2_{i_1} = s^2_{i_2}$ means that if the $i_1^{th}$ element and $i_2^{th}$ element in $s^1$ are the same, then the $i_1^{th}$ element and $i_2^{th}$ element in $s^2$ are also identical.