Hypergraph Neural Networks through the Lens of Message Passing: A Common Perspective to Homophily and Architecture Design

Q4. As previously commented in the response to Weaknesses 3, we skip hyperedge mini-batching when the dataset fits into memory. However, the adoption of node mini-batching (within hyperedges) in the MultiSet framework is driven by a fundamental shift in data processing. Specifically, the generation of multiple node representations corresponding to the hyperedges they belong to benefits from this approach. Given that the number of potential connections grows exponentially with the number of nodes, the development and application of novel mini-batching schemas become a relevant tool to scale hypergraph models. Apart from adding this rationale in our revised manuscript, we additionally updated Table 6 of the paper to represent the number of hyperedge-dependent node representations and visualize our argument.

References

[Wang et al., 2023]: Equivariant Hypergraph Diffusion Neural Operators, ICLR'23.

Thank you for your detailed review and the recognition of the strengths of our work. We appreciate the constructive comments you provided, as it will undeniably help us improve it. We would like to address the concerns and questions you have raised:

Weaknesses

W1. Please refer to Section 5.2 (Can homophily help us Understand our experemental results) and detailed discussion in Supplementary Material A (Interplay of Message Passing Homophily and Models Performances) where we address this concern. We illustrate the application of the proposed message-passing homophily measure. These sections emphasize its utility in capturing the dynamic nature of homophily and demonstrate its effectiveness in assessing hypergraph models' performance in comparison to the classical clique-expanded homophily measure [Wang et al., 2023] across diverse datasets.

W2. Originally, we decided not to consider these datasets because, in contrast to our selected dataset benchmark, they do not include node features. This implies that node attributes need to be artificially generated before hypergraph models can be applied, and we were concerned about the implications of assessing the results under these circumstances.

However, we agree that broadening the set of homophilic datasets could improve the overall quality of our paper, and can potentially reveal valuable insights. Therefore, following your suggestion, we have expanded our evaluation over Senate, Congress, House and Walmart datasets characterized in [Wang et al., 2023]. The results are added in Table 16 to the revised manuscript in Section J in the Supplementary Materials, and they can also be seen in the following Table:

Looking at the results, we observe that our MultiSetMixer model outperforms AllSetTransformer and AllDeepSets on the Senate and House datasets, while being on par within a standard deviation in the other two. Overall, we observe that our MultiSetMixer architecture shows good performance over low-homophilic datasets.

W3. Indeed, this is an interesting aspect that needed further clarification in the paper. As suggested by the reviewer, the hyperedge mini-batching is particularly useful for very large datasets; whenever the network fits into memory, this step can be skipped. Regarding the node mini-batching within a hyperedge, we empirically found that, due to the involved distribution shifts, it can be useful to keep it even when the full hyperedge can be stored in memory. The revised manuscript includes these reflections in Supplementary Materials Section K.

W4. Thank you for the suggestion, we agree that this could be an insightful line of research to further exploit hyperedge-based node representations. Unfortunately, this might fall out of the scope of this paper; we believe that the consideration of hyperedge-dependent node/edge classes represent a substantial shift in our evaluation (from the definition of datasets to its rigorous assessment) and perhaps could represent a contribution by itself in a future extension of this work. In this regard, we have added to our revised paper this interesting possibility as a future work. Please refer to Supplementary Materials C (Extended Conclusion and Discussion)

Questions

Q1. Thank you for the suggestion. In response, we have incorporated Section A (Interplay of Message Passing Homophily and Models' Performances) into the supplementary material. This section underscores the significance of formulating a dynamic homophily measure and illustrates its effectiveness in assessing the performance of hypergraph models.

Q2. It is an interesting question. We provide an in-depth response in Supplementary Materials A (Interplay of Message Passing Homophily and Models' Performances) and Supplementary Materials B (Comparison and Analysis between MultiSet and AllSet Framework Performances). These sections comprehensively explore the performance of the proposed MultiSetMixer and the other message-passing models across diverse datasets characterized by varying levels of homophily.

Q3. We kindly refer to the previous response of the Weaknesses 2, as we already described there the challenges and insights observed when tackling the new set of low-homophilic datasets (Wallmart, Congress, Senate and House). Thank you again for the suggestion.

(continuation)

W5. We strongly believe that the path towards an AGI solution in this area will rely on a deeper understanding of the domain (graph, hypergraph, topological, geometrical) where data comes from Transformer-based architectures can benefit from deep architectures, but we argue that, whenever relational interactions play a crucial role for the considered task, leveraging these natural inductive biases in the first place can be key to design more scalable solutions.

In this work, we aim to shift the focus of our community towards the study of higher-order network properties and requirements, with the goal of designing concepts and models that can naturally accommodate them (instead of just lifting graph-based counterparts). Improving our understanding on how to analyze and design hypergraph architectures could potentially result in new pipelines that would allow more and larger layers, overcoming the oversmoothing and oversquashing limitations of current methodologies.

Achieving AGI through a more scalable and interpretable framework that can naturally exploit the relational connections present in the data is a powerful research direction for the future, and (as discussed for W3) we believe our results are a step in that direction.

W6. We reckon that by addressing the concerns raised in this comment, our work can significantly improve its overall quality; the revised paper has been updated to this end in the following way:

• Added a detailed analysis on homophily vs. performance: See Appendix A, where we show that our homophily measure correlates better with HGNN models' performance compared to classical homophily measures over the clique-expanded hypergraph. Our findings underscore the crucial role of correctly expressing homophily in HGNNs, emphasizing the potential of our proposed homophily score in capturing higher-order dynamics.

• Updated Evaluation and Conclusions sections to relate the obtained results with our original questions. In particular, our results suggest that:

  • There is room for improvement in designing hypergraph models that better accommodate higher-order relationships; our MultiSetMixer implementation outperforms other solutions in some datasets (e.g. 20newsgrops) leveraging the natural connectivity distribution shift as described in Section 5.2. Additionally, we demonstrate that our model performs consistently better on 3D object segmentation datasets.
  • Our analysis on the most used dataset benchmark reveals the need of a new set of datasets if we aim at improving our understanding in modelling relational data in its diverse possibilities. For instance, looking at the homophily analysis we can observe the lack of diversity of datasets in some homophily levels (most of them are in the range of 80-90%). Moreover, in our connectivity-based experiments, we also find that some datasets do not have meaningful hyperedge connections (Zoo, Pubmed, Citeseer).

W7. Thank you for your suggestion, we believe that the revised manuscript (Sections 1, Introduction, and Section 6, Discussion) better formulates our motivations and the contributions of our work, and further discusses the challenges addressed by our introduced MultiSet framework.

References

[Sun et al., 2023]: Self-supervised Hypergraph Representation Learning for Sociological Analysis. TKDE.2023

[Ma et al., 2022] : Is Homophily a Necessity for Graph Neural Networks?, ICLR 2022

[Veldt et al., 2023]: Combinatorial characterizations and impossibilities for higher-order homophily, Science Advances

[Kovalenko et al., 2022]: Vector Centrality in Hypergraphs, Elsevier'22.

[Liu et al., 2022] Graph Self-Supervised Learning: A Survey, TKDE’22

[Huang et al., 2021]: UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks, IJCAI-21

Thank you for your detailed and constructive review. We truly appreciate the time and effort you invested in providing feedback to improve the quality of the manuscript. We would like to carefully address each of your comments and concerns:

Weaknesses

W1. Thanks for the reference, of which we were not aware during submission. We have included the reference in our discussion; in particular, the revised paper discusses the main differences with respect to our introduced homophily notion in Section M of the supplementary materials.

The concepts of Social Equivalence and Social Conformity, as introduced by [Sun, et al., 2023], differs significantly from our definition of homophily. Following a message passing scheme, our definition allows us to examine different time points, attempting to answer how similar a node is (w.r.t. its class) to the nodes it can reach with $t$ steps of message passing. This consideration extends to hyperedges edges as well. Furthermore, the concepts of social environment evolving and social polarization, which instead can be studied dynamically, also differ from our message passing homophily. This distinction arises because these concepts rely on node representations provided by a model, while our message passing homophily remains independent of any model.

W2. We respectfully disagree with the reviewer; there have been more than 100+ top-tier publications in the last years focusing on the impact of homophily in graph representation learning (40+ only in the ICLR conference), some of which provide meaningful insights in this regard. For instance, [Ma et al., 2022] explored, both theoretically and empirically, that GCN has the potential to achieve good performance if nodes with the same label share similar neighborhood patterns. Homophilous graphs always satisfy such assumptions, which explains why GCN typically works well for them.

In the graph literature, the concept of homophily is already well studied, but we found that this is not true for hypergraphs. Our work aims to address this by introducing a “natural” way of defining homophily directly for hypergraphs. For example, the proposed homophily measure overcomes the unrealistic assumption of uniform hyperedges needed in the previous definition of [Veldt et al., 2023]. We argue that our homophily concept can become a practical tool for the community to perform insightful analysis of hypergraph models similar to the ones with GNNs. Please see Supplementary Materials A for the extended discussion on the interplay of the proposed homophily measure and model performances.

W3. This is an interesting aspect. Indeed, in our main table (Table 1 in the paper), we presented the performance of a hypergraph transformer architecture executed over node features enhanced with positional encoding, which is aligned to the 2nd branch mentioned in the comment. Note that the positional encodings are derived from hypergraph connectivity using hyperedge vector centrality [Kovalenko et al., 2022]. On average, these results closely align with those of MLP, indicating that a straightforward use of transformer-based architecture is not immediately beneficial in hypergraph learning. Conversely, the implementation of AllSetTransformer employing the transformer architecture for enhanced message passing, demonstrates consistently strong performance. Note that self-attention is used within every hyperedge over the node features and among hyperedges without any position encodings. Overall, our results show that standard or hybrid message passing architectures are still state-of-the-art on hypergraph datasets, but this can change (potentially) with the exploration of larger and more diverse datasets, with a similar shift happening also in graph neural networks [Liu et al., 2022]. We believe our work, with a clear analysis of different datasets and the effect of mini-batching, is a significant step in that direction.

W4. We concur with the reviewer's insight. The observation may be attributed to the homophily level diminishing between steps 0 and step 1 for the dataset under consideration (see Table 5 in the supplementary materials). This implies that executing two steps might yield inferior results compared to opting solely for node aggregation. Perhaps the only exception is when introducing an attention mechanism in the procedure, as shown by the fact that AllSetTransformer consistently outperforms its more simple AllDeepSets counterpart.

We would also like to clarify that our MultiSetMixer implementation does not implement residual connections; looking, for instance, at the results of UniGNN [Huang et al., 2021], which does include them, they suggest that this component does not play a crucial role, as suggested by the reviewer.

Thank you for your thorough review. We appreciate the constructive feedback you provided, as it will certainly help enhance our paper. We would like to address the concerns and questions you have raised:

Weaknesses

1. Thank you for pointing out the need to improve the presentation and organization. To address your concern, we have partially rewritten the main body of the paper. In particular, we have updated Sections 1 (Introduction), 3 (Defining and Measuring Homophily in Hypergraphs), 4 (Methods), 5 (Experimental Results), and 6 (Discussion).

2. We appreciate your perspective, and following the previous response, we highlighted the challenges addressed by our proposed methods in Section 1. However, we argue that our main technical proposals—i.e., a novel definition of Message Passing homophily for hypergraphs, the MultiSet framework, and the MultiSetMixer implementation with mini-batching—represent valuable contributions to the community. So far, hypergraph modeling has focused on adapting existing graph-based concepts and methodologies by lifting them to higher-order domains. In contrast to this, the technical aspects introduced in our paper represent a shift towards the definition of concepts and methodologies directly over hypergraph-based structures, whose soundness does no longer rely on graph-related notions but rather on novel, efficient ways of analyzing and processing multi-set interactions. The revised manuscript further remarks and clarifies the common technical motivation of our proposals and the potential implications they might bring to our community.

Questions

1. All datasets used across our evaluation involve a node classification task. Following previous studies and benchmarks (e.g., [Chien et al. 2022]), we consider the test accuracy as the performance metric, representing the percentage of nodes that were successfully classified by each model over the test split. In particular, Tables 1-4 show the mean and standard deviation of the test accuracy achieved by each model over 15 different training, validation, and test splits, considering at each of these splits 2 different model initializations. Therefore, each entry in these tables aggregates the information of 30 different runs of a particular model.

References

[Chien et al. 2022] You Are AllSet: A Multiset Learning Framework for Hypergraph Neural Networks. ICLR,2022

We appreciate your detailed feedback and for raising relevant aspects in your review to improve the quality of the paper; we thoroughly addressed your concerns in our revised manuscript. Please, let us detail how exactly we confronted your comments as follows:

Weaknesses

W1 Please refer to Section 5.2 (Can Homophily Help us Understand our Experemental Results) and detailed discussion in Supplementary Material A (Interplay of Message Passing Homophily and Models Performances) where we address this concern. We illustrate the application of the proposed message-passing homophily measure. These sections emphasize its utility in capturing the dynamic nature of homophily and demonstrate its effectiveness in assessing hypergraph models' performance in comparison to the classical clique-expanded homophily measure [Wang et al., 2023] across diverse datasets.

W2 First of all, apologies for not including these two related works in our manuscript. We have updated Sections D in the supplementary materials (Extended Related Works on Hypergraph Neural Networks) to include a brief description of them as well as to explain their main differences with respect to our model. In particular, let us summarize them as follows:

EDHNN [Wang et al., 2023] does not generate independent, hyperedge-based representations of nodes. This method incorporates the option of hyperedge-dependent messages from hyperedges to nodes, but at each iteration of the Message Passing it aggregates all these messages to generate a unique node hidden representation. In contrast to this, our MultiSet framework allows to keep across the MP procedure as many representations of a node as the number of hyperedges it belongs to, only requiring a pooling/aggregation at the readout phase.

HNN [Aponte et al., 2022] does allow multiple hyperedge-based representations across the MP, but we did not initially include it in our related work because the theoretical formulation of this unpublished paper is not clear and rigorous, and the evaluation is neither reproducible nor comparable to other hypergraph models; not only its code is not publicly available, but they only use AUC as performance metric, instead of the gold-standard accuracy used in the graph/hypergraph literature. Whereas we realize now we should have added a comment on this in the original manuscript, we argue that our MultiSet framework represents a step forward by rigorously formulating a simple but general MP framework for hypergraph modeling that is flexible enough to deal with hyperedge-based node representations and residual connections, demonstrating as well that it generalizes previous hypergraph and graph models.

Overall, we reckon that MultiSet can be a positive and novel contribution to our community by defining a strong and rigorous theoretical formulation upon which new hypergraph models can be designed and implemented.

W3 Thank you for this suggestion. We agree that an extensive analysis of the reasons behind the performance variations between MultiSet and AllSet frameworks can improve the quality of the paper. Consequently, we have added a new section –Appendix B– dedicated to highlighting the performance differences observed across all datasets analyzed between the main implementations of both frameworks, MultiSetMixer and AllSet models.

W4 Thank you for pointing out the need to improve the presentation of the key contributions. To address it, we have updated the main body of the paper. In particular, Sections 1 (Introduction), 3 (Defining and Measuring Homophily in Hypergraphs), 4 (Methods), 5 (Experemental Results), and 6 (Discussion). In addition to this, and following the reviewer suggestion about giving more relevance to the contributions of the MultiSet framework and the introduced homophily measure, we have updated Sections 1, 5 and 6 to elaborate on these aspects and added discussions in Supplementary Materials A and B.

Questions

Q1 When we mention "top-3 connectivity level," we are referring to the three most frequent sizes of hyperedges in the hypergraph. We've incorporated the explanation within the model description (Supplementary Materials E). Specifically, we consider the sizes of all the hyperedges, order them according to descending frequency of appearance in the hypergraphgraph, and select the top-3 ones. Hence, we use three separate encoders for the corresponding hyperedges (those cardinalities that are in top-3). For the rest of the hyperedges we used a 4th separate encoder.

Q2 We apologize for the oversight; as you pointed out, the padding is performed when |e| < L. We have corrected this in the revised manuscript and specified that the special padding tokens consist in 0-valued vectors.

References

[Wang et al., 2023]: Equivariant Hypergraph Diffusion Neural Operators, ICLR'23. [Aponte et al., 2022]: A Hypergraph Neural Network Framework for Learning Hyperedge-Dependent Node Embeddings, arxiv 22

Thank you for addressing my concerns with your response. I read your updated paper in detail. Part of the concerns were resolved (raised score accordingly), however, there are still some remaining issues.

(weakness 1) In usual heterophily related papers, experiments showing the change of accuracies w.r.t homophily measure are provided. Such experiments with usual settings are preferable(Refer to Figure 2 in [3]) Also, as you have shown the change of homophily score w.r.t the number of layers, it would be more persuasive if you compare how the performance of traditional hypergraph NN methods and homophily score change as layer increases.

Also, even though the point of multiset framework is about generalizing allset( or UNIGCN2) with some theoretical analysis, novelty seems to be marginal. Moreover, the necessity of generalizing allset needs to be provided. (Example, why allset does not fit to some problems or data. And how multiset can solve those problems)

Reference [3] : [NIPS 22] Revisiting Heterophily For Graph Neural Networks (https://openreview.net/pdf?id=NjeEfP7e3KZ)

Thank you very much for providing feedback of our revised manuscript, and for your time given the short notice.

1. It is a good point that in usual heterophily-related papers experiments show the change of accuracies w.r.t homophily measure. However, we argue that there is currently a big gap between the understanding of homophily in the graph and hypergraph domains. Whereas in graph literature the concept is well-defined and has already been shown to strongly correlate with downstream task performance, the notion of homophily is still vague in higher-order networks, without even a practical definition.

As detailed in our paper, there have been multiple attempts to define higher-order homophily (e.g. CE and k-uniform versions), but they currently have strong limitations: as we show in the revised paper, CE homophily doesn't capture how models for hypergraphs behave, and the k-uniform homophily measure is not applicable to non-uniform hypergraphs, which highly restricts its applicability.

Therefore, by showing that our message-passiing homophily can help explain HGNN model performances, we argue that our work represents a meaningful contribution to our community. While further exploration of connections, as depicted in Figure 2 of [3], could be beneficial, we believe it goes beyond the scope of our paper. However, we think our introduced homophily concept can be really helpful in addressing these goals in future work.

2. Regarding the justification for introducing the novel framework, MultiSet framework extends the existing hypergraph neural network models (such as AllSet and UniGCN) by offering a broader scope and enabling hyperedge-dependent node representations. As has been highlighted by Reviewer wbgf, this is indeed a strength of our proposal, as it opens new research opportunities in this yet not so-well explored field; for instance, it will allow to explore datasets where node classes are hyperedge-dependent [Choe et al., 2023] (please refer to Supplementary Materials C (Extended Conclusion and Discussion)). While all this is not yet tackled in our current work, we strongly believe it will pave the path for the future research, helping to design novel architectures and benchmarking datasets.

References

[3] : [NIPS 22] Revisiting Heterophily For Graph Neural Networks (https://openreview.net/pdf?id=NjeEfP7e3KZ)

[Choe et al., 2023]: Classification of Edge-dependent Labels of Nodes in Hypergraphs, KDD'23