Link prediction in simple graphs is a fundamental problem in which new links between nodes are predicted based on the observed structure of the graph. However, in many real-world applications, there is a need to model relationships among nodes which go beyond pairwise associations. For example, in a chemical reaction, relationship among the reactants and products is inherently higher-order. Additionally, there is need to represent the direction from reactants to products. Hypergraphs provide a natural way to represent such complex higher-order relationships. Even though Graph Convolutional Networks (GCN) have recently emerged as a powerful deep learning-based approach for link prediction over simple graphs, their suitability for link prediction in hypergraphs is unexplored -we fill this gap in this paper and propose Neural Hyperlink Predictor (NHP). NHP adapts GCNs for link prediction in hypergraphs. We propose two variants of NHP -NHP-U and NHP-D -for link prediction over undirected and directed hypergraphs, respectively. To the best of our knowledge, NHP-D is the first method for link prediction over directed hypergraphs. Through extensive experiments on multiple real-world datasets, we show NHP's effectiveness.
[Relevance] Is this paper relevant to the ICLR audience? yes
[Significance] Are the results significant? somewhat
[Novelty] Are the problems or approaches novel? rather incremental
[Soundness] Is the paper technically sound? yes
[Evaluation] Are claims well-supported by theoretical analysis or experimental results? marginal
[Clarity] Is the paper well-organized and clearly written? okay
Confidence: 2/5
Seen submission posted elsewhere: No
Detailed comments:
In this work, the authors propose an approach to the (hyper-) link prediction problem in both directed and undirected hypergraphs. The approach first applies an existing dual transformation to the hypergraph such that the link prediction problem (in the primal) becomes a node classification problem in the dual. They then use GCNs to classify the (dual) nodes. Experimentally, the proposed approach marginally outperforms existing approaches.
=== Major comments
I found the novelty of the proposed approach rather limited. The proposed approach essentially just concatenates three existing strategies (dual reformulation from Scheinerman and Ullman, GCNs from Kipf and Welling, and negative sampling which is common in many communities, e.g., Han and Chen, but many others, as well). I believe the contribution for link prediction in directed hypergraphs is a more novel contribution, however, I had difficulty following that discussion.
It is difficult to interpret the experimental results. Tables 3 and 6 do not include a measure of variance. Thus, it is not clear if any of the results are statistically significant. It is also not clear whether the “10 trials” mentioned in the figure captions correspond to a 10-fold cross-validation scheme or something else. It is unclear to me what the random feature matrix for the metabolic network is supposed to me or do. It is also unclear to me why “fake papers” are needed for the citation networks; it is clear that “fake author lists” are needed for negative sampling, but it seems they could be attached to existing papers. Similarly, it is unclear how the set of candidate edges (\mathcal{E}) was chosen.
I appreciate that the authors made the code available. I did not run it, but I did have a look, and I believe it could be adapted by others without an unreasonable amount of work.
=== Minor comments
This work is very similar to the arXiv submission 1809.09401. To the best of my knowledge, though, that work has not yet been published in a peer-reviewed venue, so I do not consider it a problem that it is not cited here.
According to Tables 1 and 2, iAF692 and iHN637 datasets are smaller than the other datasets except DBLP; those two are also less dense than DBLP. According to Table 3, NHP-U seems noticeably better than SHC and CMM on the, while does not appear very significant in the other cases. Is there some relationship between NHP’s performance and the size/density of the graph? or is there some other explanation for this behavior?
Related to the above point, Table 3 shows that the performance on the undirected versions for those two datasets is better than on the other two metabolic networks, while Table 6 shows the opposite for the directed versions. Is there some explanation for this? For example, are there qualitative differences in the size of the hypernodes?
The described strategy for negative sampling seems as though it selects “easy” negative samples, in the sense that they are far away from observed positives; thus, they are also likely far away from any sort of decision boundary. How does the performance change if more “difficult” (or just uniformly random) negative samples are chosen?
I believe Recall@100 (or Precision@100, or @$\Delta E$, etc.) is a more meaningful value to report in Tables 4 and 7, rather than the raw number of edges. That is, it would be more helpful to report something so that numbers across datasets are at least somewhat comparable.
=== Typos, etc.
In Equation (4), the “k” index in d_{ijk} is in {1,2}, but in the text, it is in {0,1}.
“table 2” -> “Table 2”, and many other similar examples throughout the paper.
“higher-order etc.” -> “higher-order, etc.”
“GCN based” -> “GCN-based”, and similar in several places in the paper
“a incomplete” -> “an incomplete”