CAT-Walk: Inductive Hypergraph Learning via Set Walks

Summary

The paper proposes an hyperedge learning method suitable for modelling temporal hyperedges. The approach consists of a novel hyperedge-centric random walk, a permutation-invariant pooling method and a technique for anonymizing both the identity of the nodes and the identity of the hyperedges. Different than standard random walks for hypergraphs that samples sequences of nodes, the SetWalk generates sequences of hyperedges, making it strictly more powerful than clique-expantion based methods. The pooling method used to encode the hyperedges represents a variation of MLP-mixer and the authors proved empirically that it is more powerful than other pooling approaches such as mean pooling and RNNs. Finally, the anonymization startegy incorporates positional information from hyperedges, while still allowing the model to be applied in the inductive setup. The experimental setup validates the benefits of applying the CAT-Walk for hyperedge prediction. Additionally, they also validate the importance of each component in a series of ablation studies.

Strengths

* The proposed method contains a series of components that could be useful beyond the hyperedge prediction task presented in this paper. The idea of producing hyperedge-centric random walk is interesting and it is worth being explored in other contexts where random walk is required. Moreover the set-based pooling is a general technique that could be useful in other architectures where a set-level aggregator is needed. * The paper is very nicely presented. Even if the proposed architecture contains a complex pipeline, containing several components, each one with its own notations, the paper is easy to follow, with a nice structure and good visualisations. * The paper introduces completely novel concepts and results presented in the experimental part clearly show the advantages of incorporating them in the method.

Weaknesses

* SetWalk constitutes an hypergraph random walk technique that, instead of producing sequences of nodes, it produces sequences of hyperedges. Given that, I am wondering what is the connection between the SetWalk method and a classical graph-based random walk applied on the line expansion of the hypergraph? * The paper mentions that “[the proposed method] removes self-attention and RNNs from the walk encoding procedure, avoiding their limitations.” A detailed discussion about what are these limitations and how the proposed method overcomes them is required. * The universal approximation results from [1] show that, by applying another function on top of the summation presented in Eq.4 $g(\sum_i f(x_i))$ leads to a universal approximator for multisets. How does SetMixer pooling compare to that in terms of expressivity? What are the advantages of using SetMixer instead of this classical approach? * The paper mentions several times that a common drawbacks brought by various pooling methods is that they are losing important information. While being more expressive than some of them, it is not clear what are the limitations of SetMixer (if any). Is SetMixer universal approximator? If not, what are some examples of sets that SetMixer is not able to distinguish due to losing information. * In Eq.5, shouldn’t the multiplication with W_s^2 be a right side multiplication. The way it is defined at this moment is not a permutation invariant function (which would contradict the results in Theorem 3). * Theorem 4 states that the anonymization technique introduced in the paper is more expressive than any existing anonymization strategies based on CE, mentioning that it can distinguish at least a pair of graphs that is not distinguished by those. However, being “more expressive than” should also imply that it does not lose any expressivity compared to CE. However, the statement from Theorem 4 is unclear in this respect, since it is not obvious if the proposed method is able to distinguish between every pair of graphs that the previous methods are able to distinguish. This aspect should be more clearly mention in thetext. * A couple of additional ablation studies should be included in order to clearly emphasize the advantages brought by CAT-Walk. A few suggestions include: 1. replacing the SetMIXER not only with RNNs but also self-attention/transformer as a more recent and powerful baseline. 2. Replacing the pooling with the sum-based universal approximator for sets g(sum_i f(x_i)) where f and g are 2-layers MLPs seems a fairer comparison than the basic MEAN-pooling operator. * In the ablation studies paragraph, which type of the hypergraph random walk is used for comparison? A citation or description of the method would be useful, [1] How Powerful are Graph Neural Networks? Xu et al

Questions

Please refer to the questions mentioned in the Weaknesses section.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

A couple of limitations are mentioned in the paper.

Summary

The paper proposes an inductive approach to temporal hypergraph learning. The method includes two main components: a hypergraph random walk called SET-WALK and a pooling strategy termed SETMIXER, for extracting higher-order causal patterns. In addition, the authors design a simple neural network for hyperedge encoding.

Strengths

- The paper is well-organized. - The authors provide a new direction for the random walk on hypergraph, though the random walk seems more complicated than the CE-based random walk. - The paper gives many intuitions and theoretical analyses to demonstrate the superior performance of set-walk compared to existing walks. - The set-walk can be regarded as a generalization of node-walk on hypergraph, which seems interesting and useful. - The experiments in Table 1 suggest the proposed methods significantly outperform the baselines.

Weaknesses

1. The method contains several components: including Time Encoding, SetMixer, Setwalk, and MLP-Mixer. The experiments only provide three datasets in Table 2 to evaluate each component. It would be more convincing if each component could be evaluated in all datasets and all settings in Table 1. 2. Some definitions are not very easy to understand. It would be better to add some schematic for illustrating those concepts, e.g. Def. 1 and Def. 2. 3. The experiments on node classification are inadequate. There are many important baselines and benchmarks concerning node classification, such as [1][2]. [1] Equivariant Hypergraph Diffusion Neural Operators [2] Hypergraph Convolutional Networks via Equivalency Between Hypergraphs and Undirected Graphs

Questions

Is any hypergraph random walk can replace the set-walk in the CAT-Walk network?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

The paper proposes a walk-based learning method for temporal hyperedge prediction. Several conceptional contributions are made to walks in (temporal) hypergraphs which are compared to existing techniques such as clique or star expansion to represent hypergraphs by simple (weighted) graphs. A corresponding neural architecture is proposed and shown to outperform existing methods in an extensive experimental comparison.

Strengths

* The newly introduced concepts and ideas on walks in hypergraphs are nicely motivated by the shortcomings of existing methods. The authors provide illustrative examples, which are discussed in sufficient detail. * The paper is well-written and comprehensive. The appendix provides interesting additional results and answers most of my questions. * The experimental comparison is extensive and shows good results for the proposed method.

Weaknesses

* While the conceptional contributions are nicely motivated, this is not the case to the same extent for the design choices of the neural architecture. Some arguments remain vague or are not clear to me. Theorem 2 makes a statement on set functions (or pooling) and suggests that applying a function $f$ to the individual elements (or subsets of fixed size $k$) and computing their sum "can cause missing information." The statement is not precise, and the meaning of "$f$ is some function" is unclear. The proof in the appendix also is not helpful and essentially states that it is clear that the sum is less informative than the set itself. In light of the following papers [[Deep Sets](https://arxiv.org/abs/1703.06114), [Some Might Say All You Need Is Sum](https://arxiv.org/pdf/2302.11603.pdf)] this is not clear. * The approach shows great results for the task of "temporal hyperedge prediction", which is very specific. For the standard task of node classification, it still works well but the improvement is less significant.

Questions

* Can you make Theorem 2 more precise and address the above-mentioned concerns? * For some datasets, it is not clear to me how hyperedges were derived. For example, face-to-face contacts in the high school dataset naturally give rise to simple graphs. Can you explain this? * The considered task of "temporal hyperedge prediction" is very specific. Which competitors were designed for this task?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

A detailed discussion of the prediction tasks the approach is (most) suitable for would strengthen the paper.

Summary

The paper introduces a novel way of defining random walks on hypergraph. The random walks consist in a sequence of hyperedges, where the transition probabilities take into account both the temporal closeness of the hyperedges and the importance of the nodes through which the hyperedges are connected. The resulting random walk is more expressive (in the sense that transition probabilities capture more features of the hypergraph) than the Clique expansion and star expansion random graphs. These random walks are used to build an encoding of the nodes using a permutation invariant procedure. Finally these encodings are fed into a 2 layer MLP that outputs hyperedge predictions. The model compares favorably to other approaches used in the literature.

Strengths

The paper is clearly written. Although I’m not completely familiar with the relevant literature, the method seems novel and aims to solve a relevant problem in hypergraph link prediction. The theoretical reasons for introducing a new type of random walk on hypergraphs are compelling, and the method indeed manages to solve the expressivity problems associated to earlier random walk approaches. The experimental results are well cured and show a significant improvement in performance over previous algorithms.

Weaknesses

The theorems 1 and 2 are stated in an informal and imprecise way. While I understand the need not to flood the main text with mathematical details, one would have expected to find a rigorous formulation at least in the appendix. In partiuclar the definition of «expressiveness», «missing information» are not made explicit.

Questions

Can you comment on the number of hyperparameters (such as $\alpha,M,m$) used in CAT-WALK compared to those needed in other algorithms? Is there more hyperparameter tuning to do when using CAT-WALK?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have addressed the limitations of their algorithm.

Thanks for the response

Thanks for the detailed response. It effectively addressed my concerns. Therefore, I will increase my rating to Accept.