Co-Representation Neural Hypergraph Diffusion for Edge-Dependent Node Classification

W1: How our method addresses the three main limitations

Thank you for this insightful comment. Below we clarify the three main limitations and explain how our method addresses each of them.

(1) Adaptive representation size in our method.

We respectfully think the reviewer might have some misunderstandings about this point. The representation size in our paper refers to the node/edge representation size, instead of the weight in the final classification layer. In message passing-based HGNNs, each node ($v_i$) only has one fixed-length representation vector ($x_{v_i}$), which is not adaptive to the node degree and can cause potential information loss. In contrast, our method introduces co-representations $(h_{v_i, e_1}, h_{v_i, e_2},..., h_{v_i, e_n})$, where n is equal to the degree of node $v_i$. Although the final classification layer $f(\cdot)$ only accepts a fixed-length input vector, we can use different co-representations as input to predict different edge-dependent node labels (e.g., $y_{v_i, e_1} = f(h_{v_i, e_1})$, $y_{v_i, e_2} = f(h_{v_i, e_2})$). In this case, we ensure that the representation size is adaptive to the node/edge degree, and this size is not related to the fixed-dimensional weight of the final classification layer.

(2) Adaptive diffusion information in our method.

First, we want to emphasize that this is a common issue for most existing HGNNs, which is first discussed in [a]. Some recent research has shown that introducing edge-dependent messages (adaptive messages) can help improve the performance on hypergraph-related tasks [a,b,c]. However, in each layer, these methods focus on extracting edge-dependent information from a single node representation, while the extracted information is then aggregated back to a single node representation. Therefore, the model needs to repeat the "extract-aggregate-extract" process in each layer, which increases the learning difficulties. In contrast, our method learns node-edge co-representations directly without any aggregation, avoiding the need of this extraction and aggregation process. This also alleviates some computational burden of our method.

In Figure 2 in our original manuscript, we visualize the embeddings (i.e., $h_{v_1, e_1}$, $h_{v_1, e_2}$, …) of the largest-degree node ($v_1$). The results not only demonstrate that our method can produce different embeddings for the same node across different hyperedges, but also show that the embeddings exhibit clear distinctions based on the edge-dependent node labels. More visualizations can be found in Appendix I.4.

We thank Reviewer WHeD for the valuable comments and feedback. Below we respond to the concerns point by point.

(3) Sufficient direct interactions among nodes or edges in our method.

We consider the limitation of lacking direct interactions based on recent research [d], which empirically shows the effectiveness of direct interactions among hyperedges in hypergraph learning. Below we demonstrate the advantage of such direct interactions.

Considering two edges $e_1$ and $e_2$ with a common node $v_1$, when adding direct interactions, information can be passed directly from $e_1$ to update the representation of $e_2$, i.e., $z_{e_1} \xrightarrow[]{m_{e_1, e_2}} z_{e_2}$, where $m_{e_1, e_2}$ represents the specific information for $e_2$ that should be obtained from $e_1$ and cannot be obtained from other nodes or edges. In traditional message passing, information need to be passed through the intermediate node, i.e., $z_{e_1} \xrightarrow[]{m_{e_1, v_1}} x_{v_1} \xrightarrow[]{m_{v_1, e_2}} z_{e_2}$. To avoid information loss in $m_{v_1, e_2}$ compared to $m_{e_1, e_2}$, we need to ensure each preceding variables, i.e., $x_{v_1}$ and $m_{e_1, v_1}$, contains the complete information of $m_{e_1, e_2}$. When information needed in $m_{e_1, e_2}$ is large, this information may be lost in the preceding variables as they need to carry other information (e.g., information about node $v_1$). Additionally, considering the reverse direction of $z_{e_2} \xrightarrow[]{m_{e_2, e_1}} z_{e_1}$, then in traditional message passing, $x_{v_1}$ should also carry information of $m_{e_2, e_1}$. This means the intermediate node $x_{v_1}$ should carry information for the interactions among all neighboring edges, which is more likely to cause information loss. In contrast, with direct interactions, messages do not need to pass through this intermediate node and therefore can solve the problem.

In our method, the interactions among co-representations naturally include direct interactions among nodes or among edges. Since the information gain is highly related to the extent that the interactions among nodes or edges can contribute to task performance in a specific dataset, we added an ablation experiment to empirically compare the performance with and without direct interactions. We provide more details in Appendix I.5 in the updated manuscript. The results are as follows:

• Micro-F1 Results

• Macro-F1 Results

As shown in the tables, direct interactions enhance performance on the ENC datasets. For simpler datasets with relatively low edge degrees, such as Email-Eu, the performance gain is less pronounced compared to that on other datasets. These simpler datasets contain fewer higher-order interactions, limiting the ability to fully demonstrate the benefits of direct interactions. This observation further supports that our method can achieve greater improvements on complex datasets with large node and edge degrees, which is consistent with the findings from our main results.

(2) Non-adaptive messages

• WHATsNet aims to solve this limitation by extracting edge-dependent node representation from a single node representation. However, in the output of each layer, the extracted information is then aggregated back to a single node representation. Therefore, the model keeps repeating the "extract-aggregate-extract" process in different layers, and it forces the model to learn how to extract edge-dependent information from a single node. In contrast, our method directly preserves the co-representations and avoids this extraction and aggregation process. This also alleviates some computational burden of our method. Since this advantage is intuitive and its benefit is evident from the different designs of WHATsNet and our methods, no mathematical proof is given here.

(3) Insufficient direct interactions among nodes or edges

• Although WHATsNet incorporates a within-attention module to extract the edge-dependent node representations from multiple node representations, these extracted representations are only used as temporary variables to update the edge representation. Therefore, WHATsNet cannot directly pass messages among nodes or edges. The information for the interactions among edges still need to be passed through a hub node with limited representation size, which can cause potential information loss. In contrast, from the design of our method, the interactions are among the co-representations, which includes not only node-edge interactions, but also direct node-node and edge-edge interactions. Therefore, our method by design can address this limitation whereas WHATsNet cannot, and thus no mathematical proof is given.

The performance improvement from addressing these three limitations is highly dependent on specific datasets and affected by many factors. Due to the complexity of real datasets, imposing strong assumptions on data distribution for a mathematical proof is unrealistic, as it would not reflect real-world conditions. Therefore, providing empirical evaluation in this case will better reflect the effectiveness of a method on real datasets. We performed experiments on all benchmark ENC datasets and downstream datasets in previous research [a], which demonstrates that our method can achieve the best performance while preserving efficiency. Our ablation studies also support the effectiveness of our method design.

We hope these additional analysis and clarifications can help the reviewer better understand our method and the contribution of our work.

References

[a] Choe et al. Classification of edge-dependent labels of nodes in hypergraphs. In KDD, 2023.

We thank Reviewer WHeD for the additional comments and suggestions. Below we respond to these points in detail.

For the adaptive representation size, the reviewer might have some misunderstandings about the co-representations $h_{v_i, e_j}$ in our method. These co-representations are learned using the hypergraph structure in the HGNN layers, whereas the representations in the classification layer of WHATsNet only incorporate the concatenation $[x_{v_i}, z_{e_j}]$ as inputs. The information loss in the preceding HGNN layers due to non-adaptive representation size cannot be recovered by the final classification layer, which is unable to leverage the neighboring hypergraph structure. We have proved that, in WHATsNet, the output node and edge representations from the HGNN layers, as well as their concatenations, cannot adapt to the node or edge degrees, which can cause potential information loss for complex hypergraphs with large-degree nodes and edges. The information lost in this process cannot be recovered by a simple classification layer without incorporating hypergraph structural information, and the outputs will still lie in a low-dimensional manifold with dimension not larger than that of the input subspace. In contrast, in our method, the representation size of the co-representations in each HGNN layer is adaptive to both the node and edge degrees, which can naturally solve this limitation.

For the first suggestion about experiments, while the reviewer suggests to "refer to the experimental section of [a]", we did already include results for all experiments in [a], due to page limit partly in the appendix. We apologize that the reviewer seems to have missed them because we didn't make the reference to the appendix explicit enough in the main paper. We will make these experiments more explicit in the main paper in our final version. Regarding some other potential applications, [a] also highlights some other potential applications in the introduction, like toxicity prediction and homonyms classification. We believe it is helpful to have such a discussion in the introduction to encourage future application research in the community, even though curated datasets might be unavailable at the current stage. We will carefully indicate some applications without available datasets as potential applications in our final version.

For the second suggestion about method comparisons, our manuscript primarily focuses on comparisons with message passing-based methods, which naturally include WHATsNet. For the detailed comparison specific to WHATsNet, we have provided the comparisons in the previous responses, particularly from the perspective of the three limitations. We appreciate the reviewer’s suggestion and will incorporate these discussions into our final version.

Finally, we sincerely thank the reviewer for the valuable time and effort in helping improve the quality of our manuscript. We still hope these clarifications can help the reviewer better appreciate our work.

References

[a] Choe et al. Classification of edge-dependent labels of nodes in hypergraphs. In KDD, 2023.

Dear authors,

Thank you for the response.

First, regarding the WhatsNet [1], for classifying a node $v_i$ within a hyperedge $e_j$, the model inputs the features of both $v_i$ and $e_j$ into an MLP. Based on my understanding of MLPs, the process involves first projecting the features of $v_i$ and $e_j$ into a hidden space to generate a representation that encapsulates information from both $v_i$ and $e_j$, denoted as $h_{v_i, e_j}$. The MLP then uses $h_{v_i, e_j}$ to produce the label logits. Moreover, as mentioned in the rebuttal entitled Response to Weakness 1 (part 1/2) from the authors to my w1, the adaptive representation size in their method is indeed based on the $h_{v_i, e_j}$. Therefore, based on the authors' rebuttal, in practice, WhatsNet also generates $h_{v_i, e_j}$ just like the proposed method, which enables it to achieve the adaptive representation size.

Additionally, I still think that the actual content of the paper should align with the claims made in the introduction. I recommend the authors consider at least two major modifications: 1. Add more real-world experiments and include them in the experimental section, ensuring that the content related to real-world datasets is at least as substantial as that of the toy settings. For guidance, you may refer to the experimental section of [1]. 2. Add a section in the main paper to provide a point-by-point analysis of why previous methods, particularly WhatsNet, cannot address the limitations mentioned in the introduction, and how the proposed method overcomes these limitations. Overall, I believe this paper requires significant revisions, and thus I will retain my current score.

[1] Choe, Minyoung, et al. "Classification of edge-dependent labels of nodes in hypergraphs." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.

W3: Discussion on the over-smoothing issue and supporting experimental results

In our original manuscript, we have provided experimental results of overcoming the over-smoothing issue in Appendix I.3. We have revised our manuscript and made these additional experiments more explicitly described in the main text.

Diffusion-inspired (hyper)graph neural networks model the convolution as the optimization process for a target regularization function [a, b], which can avoid converging to an over-smoothed solution as the number of layers increases [c]. Empirical results from prior work [a] have demonstrated the robustness of diffusion-based models against the over-smoothing issue. Our method, built on hypergraph diffusion, shares the same advantage. Moreover, the co-representations in our method allow the same node to have distinct representations when interacting within different hyperedges. This ensures that the diffusing information can be diverse, preventing the learned representations from becoming uniform and further mitigating the over-smoothing issue. As illustrated in Figure A2 in Appendix I.3, the performance of the best baseline, WHATsNet, drops sharply when the depth exceeds 4 layers. In contrast, our method continues to improve performance up to 16 layers and remains stable even as the number of layers increases to 64. These results demonstrate that the proposed CoNHD method is better for mitigating the over-smoothing issue and utilizing long-range information.

W1 & W2: Improving readability and optimizing the structure of the manuscript

We thank the reviewer for these thoughtful writing suggestions. In our original manuscript, we added the ADMM part for the completeness of the whole co-representation hypergraph diffusion theory. We agree with the reviewer that it would be better to move the ADMM part to the appendix to have more space for improving readability. We have reorganized this part and added some high-level intuition at the beginning of Section 4.

We thank Reviewer y4P5 for the constructive suggestions and the positive feedback. Below we respond to the suggestions and questions point by point.

W2: Motivation for studying the ENC task

Thanks for this thoughtful question. We would like to emphasize the importance of the ENC task, and then discuss why our method is specifically suited for this task, although it can also be applied for solving other tasks.

(1) ENC is an interesting and important topic for both hypergraph research and applications.

For hypergraph research, most existing works focus on node-level or edge-level tasks. The ENC task, which relies on node-edge pairs, is under-explored. Additionally, as demonstrated by recent research [c], on the traditional node classification task, simply applying an MLP on the node features without considering the hypergraph structure can also achieve competitive results on some datasets. In contrast, in the ENC task, as the node can have different labels across different hyperedges, it forces the model to utilize the hypergraph structure and learn different features of the same node specific to different hyperedges. As indicated in [d], the ENC task "evaluates the capability of models in capturing features unique to hypergraphs".

For applications, as shown in [d], the ENC task is very helpful in many real-world scenarios and downstream tasks. For example, in the game industry, the ENC task can be used to model the score of each player (node) in each match (hyperedge). In electronic commerce, the ENC task can be used to predict the counts of each product (node) in each basket (hyperedge). Moreover, the ENC labels predicted by the model can be used as additional features to improve downstream tasks [d], including ranking aggregation, node-clustering, product-return prediction. We also provide experimental results on these downstream tasks in Appendix I.1 following [d], which demonstrates that the predicted ENC labels can help improve the performance on these downstream tasks.

Therefore, we believe the ENC task is a valuable topic to study. We have revised our manuscript, especially the introduction part, to better highlight the significance of the ENC task.

(2) Why our method is specifically suited for the ENC task and its applicability to other tasks

The primary difference between the ENC task and other tasks (node-level and edge-level tasks) is that a node can have multiple labels across different hyperedges. Therefore, our proposed co-representation strategy is naturally suited for predicting these labels related to node-edge pairs. Meanwhile, our method can be extended to solve other tasks. For example, we can aggregate co-representations corresponding to the same node to generate a single node representations, i.e., $h_{v_1} = f(h_{v_1, e_1}, h_{v_1, e_2}, \ldots, h_{v_1, e_n})$, and use this node representation to perform traditional node classification. However, this violates our design principle of avoiding aggregation, which can cause non-adaptive representation size and potential information loss. Additionally, in traditional node classification, as a node only has one label, the multiple co-representations of a single node may not provide huge improvement on such a task. Nevertheless, we have conducted experiments on traditional node classification tasks in Appendix I.2 in our original manuscript, which is the most common task in existing hypergraph research. The results demonstrate the superior performance and potential of our method beyond the ENC task.

We thank Reviewer JdfB for the valuable comments and feedback. Below we respond to the concerns point by point.

Dear Reviewer JdfB,

Thank you for your valuable time and effort in reviewing our work. We have made an effort to address the concerns and questions you raised. Specifically, we have added discussions about the weaknesses of two other baselines as well as empirical results. We also discussed the applicability of our method to other tasks with experimental support, and included a detailed complexity analysis. We sincerely hope that our responses have sufficiently addressed your concerns.

Your support is very important to our work, and we would greatly appreciate it if you could kindly consider raising your score. If you have any additional questions, we would be willing to have a further discussion on them. Thank you once again for your insightful feedback and thoughtful review.

Best regards,

Authors of Submission 5147

Q1: Comparison to GNNs on the star-expansion graph

It is indeed an option to model the ENC problem as the edge prediction problem on the star-expansion graph, where the nodes and edges in the original hypergraph are treated as vertices in this new graph (to avoid confusion with the nodes in the hypergraph, we use "vertices" to refer to the new nodes in the expansion graph). However, this solution suffers from the following weaknesses.

(1) Overlooking the heterogeneity in hypergraphs.

Performing traditional GNNs on the star-expansion graph treats all the vertices as the same type. However, the vertices can be divided into two types: from node and from hyperedge in the original hypergraph. Processing these two types of vertices in the same overlooks the heterogeneity and affects the performance. In contrast, our method clearly separates the within-edge and within-node interactions, which can leverage such heterogeneity and improve the performance.

(2) Still suffering from the three main limitations.

This graph-based solution still relies on single node and edge representations, and suffers from the three main limitations discussed in our paper, including non-adaptive representation size, non-adaptive messages, and insufficient interactions among nodes or edges, which are addressed in our method.

We have performed experiments with GNNs on the star-expansion graph and reported the performance in Table 1 of our original manuscript. The proposed CoNHD method significantly outperforms the GNN-based methods.

We thank Reviewer wbP8 for the thoughtful comments and feedback. Below we respond to the concerns and questions point by point.

References

[a] Satorras et al. E(n) equivariant graph neural networks. In ICML, 2021.

[b] Wang et al. Equivariant hypergraph diffusion neural operators. In ICLR, 2023.

We hope the responses solve your concern and questions, and we are happy to discuss them if you need further clarification. Thank you!

(2) Why concatenation is not a solution for implementing multi-output functions in HGNNs

It is indeed possible to model a multi-input multi-output function by the following procedure: first concatenate multiple inputs into one single vector, and then apply a feed forward network to generate the output, finally split the single output to multiple vectors, i.e., $[o_1, o_2, \ldots, o_n] = f([x_1, x_2, …, x_n])$.

However, this is not a solution for HGNNs: First, a feed forward network only accepts a fixed-length input, while in our case the number of inputs ($n$) can be different across different edges, which means the concatenated vector should have variable size. Second, this simple implementation cannot guarantee the set permutation equivariance property. For example, when permuting the inputs, like $[o'_2, o'_1, \ldots, o'_n] = f([x'_2, x'_1, \ldots, x'_n])$, we cannot guarantee that the output $o'_2$ is the same as $o_2$. More formally, we cannot guarantee that, given any element $\pi$ from the permutation group $\mathbb{S}_n$, the equality $f(\pi([x_1, x_2, \ldots, x_n])) = \pi(f([x_1, x_2, \ldots, x_n]))$ holds. This property is essential in HGNNs, as the nodes are inherently unordered, and the concatenation ordering of the node features should not affect the outputs and also the final predicted labels. Therefore, we carefully design the two multi-input multi-output functions $\phi$ and $\varphi$ as permutation equivariant set functions.

(3) Introducing co-representations to disseminate a single output into multiple outputs is a critical improvement of ED-HNN [b]

First, we respectfully believe it might not be justified to assess the contribution of a work as limited solely due to its simplicity. Actually, we always want a simple but effective solution, which can be easily implemented and achieve good performance in applications. Below, we demonstrate why the co-representation design in our method is a critical improvement of ED-HNN [b]. (Here we use the name "ED-HNN" as used in the original paper [b], instead of the name "EG-GNN" used by the reviewer. Please correct us if we have any misunderstandings.)

Similar to other message passing-based HGNNs, ED-HNN models the within-edge and within-node interactions as a single-output aggregation process, which brings three limitations.

• Non-adaptive representation size: As discussed in (1), existing message passing-based HGNNs, including ED-HNN, model the within-edge interaction as an aggregation function $z_{e_1} = f(x_{v_1}, x_{v_2}, \ldots, x_{v_n})$. This can cause potential information loss when $n$ is very large.

• Non-adaptive messages: The edge representation $z_{e_1}$ cannot distinguish different node-specific information and therefore can only pass the same message $z_{e_1}$ to different nodes, instead of adaptive messages for different nodes.

• Insufficient direct interactions among nodes and among edges: Message passing-based HGNNs only model interactions between nodes and edges, without direct interactions among the nodes or direct interactions among the edges.

To solve all these three limitations, we carefully design co-representations to disseminate the single output $z_{e_1}$ to multiple outputs $(m_{v_1, e_1}, m_{v_2, e_1}, \ldots, m_{v_n, e_1})$, which can solve the above three limitations in a unified framework. Additionally, we demonstrate that the CoNHD framework is more expressive than message passing-based HGNNs including ED-HNN (see Proposition 3 in our manuscript). As demonstrated in Table 1 and Figure 3, our method also significantly outperformed other baselines, including ED-HNN, on all datasets without sacrificing the efficiency, which proves the superiority of our improvement.

W1: The contributions and novelty of our method

We respectfully think the reviewer might have some misunderstandings about our method and its contributions. Below we clarify the main points and highlight the value of our work.

(1) The multi-input single-output design mentioned in our paper is specific to HGNNs, not GNNs

In our paper, the single-output design is used to describe the process of aggregating messages from multiple nodes to a single hyperedge in HGNNs. This is a specific problem for HGNNs, not GNNs (therefore it is not related to EGNN [a] (the paper [1] mentioned by the reviewer)).

In GNNs, each edge only connects to two nodes (e.g., $e_1 = (v_1, v_2)$), therefore the message from neighboring node $v_2$ to node $v_1$ through edge $e_1$ can always be calculated by a function with two inputs ($m_{v_2, v_1} = f(x_{v_2}, x_{v_1})$). (The EGNN paper mentioned by the reviewer also follows this design, where the implementation of $f(\cdot)$ can be found in Eq. 3 of [a])

However, in HGNNs, each edge can connect any number of nodes (e.g., $e_1 = (v_1, v_2, \ldots, v_n)$) ($n$ can be different for different hyperedges). Therefore, when calculating the message from neighboring nodes ($v_2, \ldots, v_n$) to node $v_1$, the typical solution is to aggregate node information to update the edge representation $z_{e_1} = f(x_{v_1}, x_{v_2}, \ldots, x_{v_n})$, which then propagates back to the node $v_1$ (and also, to the other nodes). In this case, we can see the function $f(\cdot)$ needs to aggregate any number of inputs and generate a single output, which can cause potential information loss when $n$ is very large.

In our method, we introduce co-representations to disseminate the single output $z_{e_1}$ to multiple outputs ($m_{v_1, e_1}, m_{v_2, e_1}, \ldots, m_{v_n, e_1}$). The function $f(\cdot)$ becomes $(m_{v_1, e_1}, m_{v_2, e_1}, \ldots, m_{v_n, e_1}) = f(h_{v_1, e_1}, h_{v_2, e_1}, …, h_{v_n, e_1})$, where each output $m_{v_i, e_1}$ can correspond to each input $h_{v_i, e_1}$. It means, even when $n$ is very large, the outputs of the function can also have $n$ outputs, which can naturally solve the potential information loss problem. Also, this design brings some other advantages like diverse diffusion information and direct interactions among nodes and among edges, which will be discussed below.

Dear Reviewer wbP8,

Thank you for your valuable time and effort in reviewing our work. We have made an effort to address the concerns and questions you raised. In particular, we have clarified the novelty and contributions of our method compared to prior approaches and provided an analysis of the limitations in graph-based solutions. We sincerely hope that our responses have adequately resolved your concerns.

Your support is very important to our paper. We would greatly appreciate it if you could kindly consider raising your score. Should you have any additional questions, we would be more than happy to engage in further discussions. Thank you once again for your thoughtful review and valuable suggestions.

Best regards,

Authors of Submission 5147