Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is in the area of graph representation learning, and more specifically, they focus on edge representation learning. The proposed method is an edge representation learning framework that is based on Dual Hypergraph Transformation (DHT), that transforms the edges of the original graph into the nodes of a hypergraph and nodes to hyperedges. The dual hyper graph construction allows to apply any off-the-shelf message passing techniques designed for node representations to edge representation. Then, they proposed two novel graph pooling methods for the hypergraph to obtain compact graph-level edge representations; to cluster (HyperCluster) or drop (HyperDrop) edges to obtain holistic graph-level edge representations. They validate the edge representations on various synthetic and molecular datasets for graph representation and generation downstream tasks. When tested on the graph classification task, the proposed method outperforms the state-of-the-art comparison graph polling methods.

-- Edit after the discussion phase: I acknowledge that I have read the authors' response and the other reviews.
main_review: The paper is well-written and well-structured. The authors work on an interesting problem of edge representation learning and more specifically the propose a framework to construct a hypergraph and apply off-the-shelf message-passing methods from node to edge representations. The related work is dense and covers most important related works. The methodology section (Section 3) contains all details for the proposed edge representation learning method, and justifications with references when needed. The experimental setup is nicely done, it has a good structure with all the necessary details and analyses (including results summarization in Tables and Figures). The authors include edge reconstruction results in the ZINC molecule and synthetic datasets, as well as graph reconstruction results in the ZINC molecule and some examples. They have added the graph compression results figures that shows the relative size of compressed graphs from the proposed method to the node pooling method (GMT). The results on the graph generation task against MolGAN and MARS show that the proposed method outperforms the others. The graph classification results are shown against various datasets and various pooling methods. Overall, the paper discusses some nice ideas regarding the edge representation learning and how to apply message passing techniques for node representation learning to edge representation learning. Also, the authors propose two edge pooling methods and they provide a convincing analysis of an in-depth experimentation they have done that shows the performance improvements.
limitations_and_societal_impact: The authors discuss the limitations of this work in the paper, they also include a section for this purpose in the Appendix, and there are no concerns for potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new edge representation learning model by hypergraph transformation and message passing. Two edge pooling schemes are designed to learn a holistic representation. The proposed model is validated on graph reconstruction, generation, and classification tasks, and the experimental results show the proposed model outperforms the baseline models on several datasets.
main_review: This paper studies an interesting and useful problem, to learn the representation of edge. The proposed idea and method are intuitive. The experiment results are impressive. However, I have a few concerns about this paper.
(1) Transforming edges to nodes is not very novel, and the strategy is adopted by many existing works, e.g. edge clustering in network community detection. What is the main difference between this paper and the combination of the above transformation and a GCN?
(2) Does the transformation increases the complexity of message passing, especially for the scale-free networks (few hubs with very high degree)?
(3) The descriptions of the tasks in the experiments are not clear and may cause misunderstanding. For example, edge reconstruction is to reconstruct the feature of edge actually.
limitations_and_societal_impact: The authors adequately addressed the potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: --------------------------------------------------------------------------------------------------------------------------

* Most graph representation learning methods focus on representing nodes or entire graphs but not edges.
* The paper proposes a dual hypergraph transformation of the input graph (nodes become hyperedges while edges become nodes) to easily learn representations of edges in the graph (the key idea is to use a node representation learning method on the dual).
* Experiments on graph reconstruction and graph generation, two tasks in which edges are crucial, demonstrate the benefits of the proposed edge representation learning method.
main_review: --------------------------------------------------------------------------------------------------------------------------

### **Strengths**

--------------------------------------------------------------------------------------------------------------------------

1. **Quality of Submission**

The methods used (Dual Hypergraph, HyperCluster, HyperDrop) are appropriate for the tasks (graph reconstruction, generation, and classification). 
The submission is a complete piece of work (i.e., not a work in progress).
The authors have also evaluated the weaknesses (albeit briefly) of their work (page 14 of supplementary/appendix).

--------------------------------------------------------------------------------------------------------------------------

2. **Clarity of Presentation**

The submission is well-organised and well-written.
The submission contains a detailed supplementary material that includes code, details of additional experiments, and descriptions of baselines, datasets, tasks, and hyperparameters.
The code seems well-organised and can be easily adapted by others without much effort.

--------------------------------------------------------------------------------------------------------------------------

### **Weaknesses**
The submission can be strengthened by improving the originality, significance of the contributions and positioning with prior work better.

--------------------------------------------------------------------------------------------------------------------------

1. **Originality of Contributions**

The tasks are not new and the methods used are well-known.
The hyperedges of the dual hypergraph are not treated any differently from pairwise edges: the key idea is to run a known graph-based method on the transpose of the incidence matrix (a straightforward idea) as discussed in line 207.
HyperCluster and HyperDrop are also straightforward adoption of known techniques from prior graph pooling models [e.g., (i) Hierarchical graph representation learning with differentiable pooling, NeurIPS'18, (ii) Self-attention graph pooling, ICML'19] to nodes of the dual hypergraph. 

--------------------------------------------------------------------------------------------------------------------------

2. **Significance of Experimental Results**

The graph generation results in Table 2 reveal higher variances for the proposed method than baselines. 
The experimental methodology could be strengthened by using statistical tests to validate the significance of performance gains.
The authors should clarify how a simple Multi-layer Perceptron (MLP) baseline (without graph connectivity information) performs on graph reconstruction, generation tasks (this would strengthen claims made in lines 37--42).

--------------------------------------------------------------------------------------------------------------------------

3. **Positioning with Prior Work**

Learning representations for both nodes and hyperedges in a hypergraph has been a recent topic of research interest which includes the following publications:
* Be More with Less: Hypergraph Attention Networks for Inductive Text Classification, In EMNLP'20
* Session-based Recommendation with Hypergraph Attention Networks, In SDM'21.

The submission can be strengthened by positioning (and comparing) with hypergraph attention networks since they can be applied easily to a dual hypergraph.
The results on oversmoothing (Figure 10) are not surprising since dropping nodes and/or edges from a graph is  well-known to alleviate oversmoothing issues, e.g., Bayesian Graph Neural Networks with Adaptive Connection Sampling, ICML'20.

--------------------------------------------------------------------------------------------------------------------------
limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new approach for computing edge-level representations. The core idea of the paper is to realize message passing not just in the original graph (the primal) that is provided in input to the model, but on the dual hypergraph (where nodes are edges and hyperedges are nodes in the primal) where additional processing such as clustering or dropping can be applied in order to respectively compute graph-wise edge representations or improve the quality of message passing on the primal as irrelevant edges are hopefully dropped on the dual. The authors validate the quality of the model on graph/edge reconstruction tasks on synthetic and molecular datasets (ZINC12), graph generation and graph classification tasks.
main_review: Overall I believe the paper is on the acceptance side despite there are a number of issues I would like the authors to clarify in the rebuttal.

First of all, the authors refer to the dual of the original graph (the primal) as an hypergraph (as multiple nodes are connected by same edges in the dual), however they don’t exploit at all the hypergraph nature of the dual and realize message passing on it as if it was a simple graph. This idea is not novel and was already exploited in https://arxiv.org/abs/1806.00770 for computing edge level representations that can be used for refining an attention mechanism on the primal. Additionally, the complexity of processing the dual as described in the paper - Table 1 seems to be wrongly stated. The authors mention that alternative methods for constructing the adjacency matrix of the dual require O(m^2) operations (with m = number of edges), however because of the sparse nature of the adjacency matrix (if I’m not mistaken) this can actually be realized resorting to edge lists and dictionaries (one mapping edges to incident nodes and one mapping nodes to incident edges) with a complexity equal to O(m*d_max) (with d_max the maximum node degree), which is significantly cheaper and actually the same complexity required by the method of the authors for processing the dual. In this sense, the authors mention in the paper that they can just transpose the incidence matrix of the primal for obtaining the incidence matrix of the dual hypergraph, but they don’t provide any detail on how this can avoid the construct of an edge list in the dual which I believe is still required for realizing message passing therein. I would be happy if the authors could clarify this detail in their rebuttal.

While the idea of processing the dual graph is not novel per se, to the best of my knowledge using message passing on the dual to identify not so relevant or noisy edges in the primal (and thus realize some sort of learnable rewiring operation) is a new contribution to the field (and personally what I found to be the most interesting bit of the paper). However, the justification for why one would want to use this seems to be rather weakly justified in the paper. The authors in particular stress that for graph classification tasks, dropping edges (and not nodes) allows to compute lossless graph-wise representations as all nodes are preserved in the final aggregation process while not so relevant edges are removed. However, one could argue the same for the edges of the dual graph and that, as some edges might be noisy in the primal, some edges might be noisy in the dual which would correspond to dropping nodes in the original graph (in this case loosing some information in the node-wise final aggregation process would actually be beneficial for graph classification problems). Hence, while I believe there is some merit in the idea of pruning the original graph, learning to discard some edges if needed, the justification presented in the paper doesn’t seem to be well argued and I would recommend the authors to rephrase this in terms of rewiring the original graph. I would like the authors to additionally reply on this in their rebuttal as well.

Similarly to the above, the idea of coupling a graph-wise representation based on node features with one explicitly aimed at representing edges I believe is a new (despite not particularly original) contribution that seems to favour graph generation and reconstruction tasks in particular.

On the experimental side, I believe the experiments are overall good and extensive, however I think there might be room for improvement. In particular, for the edge and graph reconstruction tasks, the authors compare with previous approaches that only implicitly use edge features for refining node representations. However, while the importance of computing edge representations seems clear from the experiment, I believe comparing with https://dl.acm.org/doi/abs/10.1145/3394486.3403389 / https://www.ijcai.org/Proceedings/2019/0366.pdf  that explicitly compute edge representations in the message passing procedure coupled with a suitable pooling (e.g. even a simple mean/sum/max on the added colored nodes representing the edges) would have greatly improved the reader understanding of the benefits of processing the dual with respect to an alternative simple solution. 

Other comments on the experiments I would like to clarify with the authors:

1. the authors propose just a qualitative analysis on their synthetic dataset for edge reconstruction, I believe showing some quantitative results on this as well would improve the strength of the experimental section.

2. The graph compression experiment in the paper is confusing. What do the authors mean with the relative size of the full graph in Figure 7?

In conclusion, while the presentation of the core ideas of the paper could be improved and there are a series of items that I would like the authors to address in the final manuscript, I think the manuscript does present some contribution to the field and I’m thus (even if weakly) in favor of its acceptance provided that the authors clarify the issues I highlighted.

Other Minor comments:


1) line 92/94, this seems an over statement. As mentioned above, potentially we can simply compute edge-level features by adding for each edge e, a new colored node which is connected to the end points of e and run message passing on this expanded graph. I would rephrase softening the claim.
2) Figure 3 / 5, compression ratio is never defined in the paper, what do the authors mean with this?
3) Figure 5, why did the authors show the reconstruction performance of nodes and edges together when they already showed edge reconstruction performance in Figure 3? 

I believe it would be clearer if the authors were showing the reconstruction performance of nodes and edges separately to understand the performance of the model  (e.g. in term of accuracy in figure 5 we see an improvement of the baselines wrt figure 3, while the proposed model seem to worsen, is the node-wise accuracy of the baselines at a node level better than the one of the proposed solution? If yes, why?)

4) Citation to https://arxiv.org/abs/1907.10903 is missing, despite the authors compare with it to showing the robustness of the model wrt oversmoothing.
5) What kind of pooling do the authors use for Hyperdrop without GMT in table 3? I was not able to find that detail anywhere in the paper nor supplementary material. Are the authors using HyperCluster as well in that experiment? 

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper proposes a new edge representation learning model through Dual Hypergraph Transformation. 
Finding good representation of edges remains an under-studied problem and the results of this paper can be considered as progress towards the problem.
 The proposed model outperforms 
baselines on several tasks such asl graph reconstruction, generation, and classification tasks.  
However, the authors should incorporate the salient points of the discussion in the final submission.

Decision: Accept (Poster)