Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors aim at building the equivalency between hypergraphs and undirected graphs. They introduce the concept of generalized hypergraphs and demonstrate their equivalency with undirgraphs in terms of random walk. They further proposed two spectral-based convolution operations for the undigraphs. 

main_review: Strengths
1. This paper provides some theoretical understanding of the equivalency of hypergraphs and undirected graphs.

Weakness
1. The paper is not very well written. The motivation is not clearly described.
2. Some concepts and definitions are not clearly presented. 
3. Traditional GNN methods for undirected graphs should be included as baselines.

More comments

1. It would be better if the authors could provide more motivation for transferring hypergraphs into undirected graphs. What are the benefits? Are the equivalency through random walks good enough for downstream tasks? Will there be information loss when transferring hypergraphs into undirected graphs?
2. Definition 1 is not clearly presented. Specifically, why there are suddenly two Q matrices, what are their relation to the common definition of hypergraph, which only has a single matrix Q. Also, what is $\rho$ for? 
3. What is the concept of ``oversmoothing issue'' for hypergraphs? Is it defined upon the corresponding undirected graphs? 
4. In Section 3, are these two spectral operations developed based on the Laplacian matrix for the corresponding undirected graphs? If so, how are they different from the existing methods for undirected graphs? Why not directly adopt existing operations for undirected graphs? Do they have any specialty corresponding to the hypergraphs? 
5. In Section 4.1, what are the benefits of modeling the citation datasets as hypergraphs? Also, other baselines for undirected graphs such as GCN and APPNP (the SHSC is a bit similar to APPNP) should be included. 
6. In Section 4.3, why is constructing such hypergraphs for the protein reasonable? It would be better if the authors could provide more explanations. 


summary_of_the_review: Overall, the motivation for building such equivalency is not very clearly presented. The proposed convolution operations seem to be ``general'' for undirected graphs but not specifically related to the hypergraphs (except for the involved Laplacian is derived from the hypergraph). Also, it would be better if the authors could include existing GNN methods for undirected graphs for comparison to demonstrate the superiority of their proposed framework.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the problem of showing equivalency of Generalized Hypergraphs to undirected graphs (in the sense that a natural random walk on the hypergraph is equivalent to the natural random walk on a weighted undirected clique graph). They do so via establishing a Hypergraph Laplacian and identifying its properties that help prove this equivalence. They leverage this equivalency to build a Hypergraph  convolution neural network by viewing the weighted undirected graph as a lower-order encoder of hypergraphs. They use empirical studies to show that the constructed Hypergraph Convolution NN on four different network based classification task, where the underlying network structure forms a hypergraph.
main_review: The main strengths of this paper are as follows:

+ The paper is well-written and clearly explains both pros and cons of the methods. The technical contributions are sufficiently novel and deep. The experimental results justify the main claims made by the paper.

+ There are a number of new ideas in the paper that may be useful independently.

+ The considered problem of developing Hypergraph convolutional NN is practically relevant and useful in many applications (the paper already shows 4 such applications).

The main weakness of the paper are as follows:

To a large extent I did not find any significant weakness of this paper. The paper was very well-written and they already go in significant depth on the weakness of their methods.
summary_of_the_review: Overall I am very positive about this paper.  AS mentioned above, I find the techniques and the evaluation to be solid with very little in terms of weakness.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proves under what conditions the equivalency between a generalized hypergraph (a hypergraph with node weights $Q_1$ and $Q_2$ for two-step random walk) and an undirected graph holds. The theory applies to ordinary hypergraphs as a special case with $Q_1=Q_2=H$. Then, the authors derive the stationary random walk distribution, the hypergraph Laplacian, as well as the generalized spectral hypergraph convolution form leveraging the Laplacian. To alleviate oversmoothing, they further propose to use a diffusion kernel to build a simple hypergraph spectral convolution. Experiments on four tasks show better performance than state-of-the-art methods.
main_review: Strengths:
1. The theory for the equivalency between generalized hypergraph and undigraph is interesting, which allows using any GNNs designed for undigraphs to solve hypergraph problems in principle.
2. The strong empirical performance.
3. The introduction of two new tasks: protein quality assessment and protein fold classification for hypergraph GNNs.

Weaknesses:
1. The Notations part in Sec. 2 is not clear at first glance. For example, what is $q_e(u)$ and what is $q_(u)$? They are used without definitions.
2. The Introduction contains many unfamiliar terms for people not working on hypergraphs, such as edge-dependent (independent)-vertex weights. I am confused on their meanings until reading into Sec 2.1
3. The theory only shows that performing two-step random walk on weighted hypergraphs can be equivalent to performing random walk on a weighted graph under some conditions. However, it does not clearly tell whether the mapping from hypergraph to graph is injective, i.e., from the weighted graph you can perfectly recover the original hypergraph. Can the authors comment on that?
summary_of_the_review: Though I am not familiar with the hypergraph field, this paper seems to provide some useful theory and techniques for hypergraph learning. I resort to other reviewers to evaluate the novelty and significance of the theory.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Real-world relational datasets (e.g., academic data, protein data) contain group relationships and can be modelled via hypergraphs.  One way to capture group higher-order relationships is to define a hypergraph with edge-dependent vertex weights (EDVWs) and such a hypergraph has been shown to be equivalent to directed graphs [Chitra et al., ICML'19]. The main contributions of this paper are:
1) Proposal of a generalised hypergraph capturing EDVWs with equivalence to undirected graphs,
2) Proposal of a Laplacian based on the generalised EDVW and exploration of existing spectral convolutional methods, and
3) Empirical evaluation on academic, protein, and visual object datasets.
main_review: ### **Strengths**

1. **Quality of Paper**

The paper is technically sound and claims are well supported by theoretical analysis. 
Extensive experimentation across different domains adds to the quality of the paper.
The paper also discusses limitations in addition to highlighting its strengths.


2. **Clarity of Presentation**

The paper is clearly written and well organised. 
The appendix is comprehensive with both theoretical proofs and empirical details (e.g., dataset construction, hyperparameters, etc.). 
The authors have also released the source code as part of the supplementary material. 


### **Weaknesses**

1. **Originality of Contributions**

The theory of equivalence between EDVW hypergraph and undirected graph is a small contribution of the paper in which vertex weights are added into the first step of the random walk. Empirically, however, edge-dependent vertex weights have been previously explored  in the form of attention mechanisms (node-level and edge-level attention mechanisms), e.g., the HGAT model proposed in (i) Be More with Less: Hypergraph Attention Networks for Inductive Text Classification, EMNLP'20, and (ii) Session-based Recommendation with Hypergraph Attention Networks, SDM'21. Another weakness of the paper is that once the Laplacian is defined, the proposed methods, viz., GHCN and SHSC are straightforward applications of existing spectral convolutional methods viz., ChebNet [Defferrard et al. NeurIPS'16] and SSGC [Zhu & Koniusz, ICLR'21] to hypergraphs.


2. **Significance of Empirical Evaluation**

The paper can be significantly improved by comparing with the HGAT baseline, i.e., a baseline with node-level, edge-level attention mechanisms.
Moreover, SSGC and ChebNet on the clique expansion are also important missing baselines in all the experiments. 
Empirical insights (e.g., comparison of attention weights and weights in the proposed $Q$ matrix for visual and protein data) would improve the paper. 
summary_of_the_review: Overall the paper is clear and of good quality with claims being well supported by theoretical analysis. However, the novelty is incremental and experimental results are marginally significant. Positioning with important prior work and evaluation with missing baselines would significantly improve the paper.
review_title: null

Meta-review: Standard algorithms for deep hypergraph learning have not been designed for hypergraphs with edge-dependent vertex weights (EDVWs), where the weight of a vertex can depend on the edge of which it isa member. This paper develops a connection between EDVW-hypergraphs and undirected simple graphs, thus enabling the use of existing undirected-graph neural networks as subroutines. This is done via a unified random-walk framework.

(Two typos: ``equivalency" should be ``equivalence", and ``undigraphs" should be ``undirected graphs".) 

The theory of equivalence between EDVW-hypergraphs and undirected graphs via random walks is a good contribution. The experimentation across different domains is laudable. 

However, there are concerns over the lack of key baselines in the experiments. The author rebuttal has presented additional results with some baselines: sensitive hyperparameters (e.g., learning rate) are not tuned for the baselines. The clarity of the paper is mixed. The map from hypergraphs to graphs is not injective, so there could be ambiguity issues (different hypergraphs mapped to the same graph, thus having the same representations). 

Also, the contributions of Section 3 (designed for simple undirected graphs alone) do not appear significantly novel.
Decision: Reject