Title: LINK PREDICTION IN HYPERGRAPHS USING GRAPH CONVOLUTIONAL NETWORKS

Abstract: 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.

1. INTRODUCTION:

The problem of link prediction in graphs has numerous applications in the fields of social network analysis (Liben-Nowell & Kleinberg, 2003) , knowledge bases (Nickel et al., 2016) , bioinformatics (Lü & Zhou, 2011) to name a few. However, in many real-world problems relationships go beyond pairwise associations. For example, in chemical reactions data the relationship representing a group of chemical compounds that can react is inherently higher-order and similarly, the co-authorship relationship in a citation network is higher-order etc. Hypergraphs provide a natural way to model such higher-order complex relations. Hyperlink prediction is the problem of predicting such missing higher-order relationships in a hypergraph.

Besides the higher-order relationships, modeling the direction information between these relationships is also useful in many practical applications. For example, in the chemical reactions data, in addition to predicting groups of chemical compounds which form reactants and/or products, it is also important to predict the direction between reactants and products, i.e., a group of reactants react to give a group of products. Directed hypergraphs (Gallo et al., 1993) provide a way to model the direction information in hypergraphs. Similar to the undirected hypergraphs, predicting the missing hyperlinks in a directed hypergraph is also useful in practical settings. Figure 1 illustrates the difference between modeling the chemical reactions data using undirected and directed hypergraphs. Most of the previous work on hyperlink prediction (Zhou et al., 2006; Zhang et al., 2018) focus only on undirected hypergraphs. In this work we focus both on undirected and directed hypergraphs.

Recently, Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017) have emerged as a powerful tool for representation learning on graphs. GCNs have also been successfully applied for link prediction on normal graphs (Zhang & Chen, 2018 ; van den Berg et al., 2018; Schlichtkrull et al., 2018; Kipf & Welling, 2016) . Inspired by the success of GCNs for link prediction in graphs and deep learning in general Wang et al. (2017) , we propose a GCN-based framework for hyperlink prediction which works for both undirected and directed hypergraphs. We make the following contributions: Figure 1 : Illustrating the difference between modeling chemical reactions data using undirected and directed hypergraphs. To the left is the undirected hypergraph, in which both the reactants and products are present in the same hyperlink. Whereas in the directed hypergraph (to the right), for a given reaction, the reactants are connected by one hyperlink and products are connected by another hyperlink and both these hyperlinks are connected by a directed link.

• We propose a Graph Convolutional Networks (GCN)-based framework called Neural Hyperlink Predictor (NHP) for the problem of hyperlink prediction. To the best of our knowledge, this is the first ever deep learning based approach for this problem. • We extend the proposed NHP for the problem of hyperlink prediction in directed hypergraphs.

To the best of our knowledge, this is the first ever attempt at the problem of link prediction in directed hypergraphs. • Through extensive experiments on multiple real-world datasets, we show the effectiveness of proposed NHP for link prediction in both undirected and directed hypergraphs.

We have released NHP's source code at this anonymous location: https://anonymous.4open. science/repository/7d86231e-f6ba-4795-ae51-ac28d89f1521/.

2. RELATED WORK:

In this section, we briefly review related work in deep learning on graphs and link prediction on hypergraphs.

Learning representations on graphs::

The key advancements in learning low-dimensional node representations in graphs include matrix factorisation-based methods, random-walk based algorithms, and deep learning on graphs (Hamilton et al., 2017 

3. PRELIMINARIES:

Undirected hypergraph is an ordered pair H = (V, E) where

V = {v 1 , • • • , v n } is a set of n hypernodes and E = {e 1 , • • • , e m } ⊆ 2 V is a set of m hyperlinks.

The problem of link prediction in an incomplete undirected hypergraph H involves predicting missing hyperlinks from Ē = 2 V -E based on the current set of observed hyperlinks E. The number of hypernodes in any given hyperlink e ∈ E can be any integer between 1 and 2 n . This variable cardinality of a hyperlink makes traditional graph-based link prediction methods infeasible because they are based on exactly two input features (those of the two nodes potentially forming a link). The variable cardinality problem also results in an exponentially large inference space because the total number of potential hyperlinks is O(2 n ). However, in practical cases, there is no need to consider all the hyperlinks in Ē as most of them can be easily filtered out (Zhang et al., 2018) . For example, for the task of finding missing metabolic reactions, we can restrict hyperlink prediction to all feasible reactions because the infeasible reactions seldom have biological meanings. In other cases such as predicting multi-author collaborations of academic/technical papers, hyperlinks have cardinalities less than a small number, as papers seldom have more than 6 authors. The number of restricted hyperlinks in such practical cases is not exponential and hence hyperlink prediction on the restricted set of hyperlinks becomes a feasible problem.

Formally, a hyperlink prediction problem (Zhang et al., 2018 ) is a tuple (H, E), where H = (V, E) is a given incomplete hypergraph and E is a set of (restricted) candidate hyperlinks with E ⊆ E. The problem is to find the most likely hyperlinks missing in H from the set of hyperlinks E -E.

Directed hypergraph (Gallo et al., 1993 ) is an ordered pair H = (V, E) where

V = {v 1 , • • • , v n } is a set of n hypernodes and E = {(t 1 , h 1 ), • • • , (t m , h m )} ⊆ 2 V is a set of m directed hyperlinks. Each e ∈ E is denoted by (t, h) where t ⊆ V is the tail and h ⊆ V is the head with t = Φ, h = Φ.

As shown in figure 1 , chemical reactions can be modeled by directed hyperlinks with chemical substances forming the set V . Observe that this model captures and is general enough to subsume previous graph models:

• an undirected hyperlink is the special case when t = h

• a directed simple link (edge) is the special case when |t| = |h| = 1

Similar to the undirected case, the directed hyperlink prediction problem is a tuple (H, E), where H = (V, E) is a given incomplete directed hypergraph and E is a set of candidate hyperlinks with E ⊆ E. The problem is to find the most likely hyperlinks missing in H from the set of hyperlinks E -E.

4. PROPOSED FRAMEWORK NHP:

In this section we discuss the proposed approach for link prediction in hypergraphs. Our proposed NHP can predict both undirected and directed hyperlinks in a hypergraph. We start with how NHP can be used to predict undirected hyperlinks and then explain how NHP can be extended to the directed case. Graph Convolutional Network (Kipf & Welling, 2017) Let G = (V, E), with N = |V|, be a simple undirected graph with the adjacency matrix A ∈ R N ×N , and let the data matrix be X ∈ R N ×p . The data matrix has p-dimensional real-valued vector representations for each node in the graph. The forward model for a simple two-layer GCN takes the following simple form:

EQUATION

where

Ā = D-1 2 Ã D-1 2 , Ã = A + I, and Dii = N j=1 Ãij . Θ (0) ∈ R

p×h is an input-to-hidden weight matrix for a hidden layer with h hidden units and Θ (1) ∈ R h×r is a hidden-to-output weight matrix. The softmax activation function is defined as softmax(x i ) = exp(xi) j exp(xj ) and applied row-wise. For semi-supervised multi-class classification with q classes, we minimise the cross-entropy error over the set of labeled examples, V L .

L = - i∈V L q j=1 Y ij ln Z ij .

(

EQUATION

The weights of the graph convolutional network, viz. Θ (0) and Θ (1) , are trained using gradient descent.

We note that Lugo-Martinez & Radivojac (2017) also follow a similar approach of constructing dual graph followed by node classification for hyperlink prediction. However, ours is a deep learning based approach and (Lugo-Martinez & Radivojac, 2017) do not perform link prediction in the directed hypergraphs. In positive unlabelled learning framework, we construct a plausible negative sampling set based on data similarity (Han & Shen, 2016) . We calculate the average similarity of each unlabelled point u ∈ E -E, to the positive labelled examples in E:

EQUATION

where S represents a similarity function and f represents a map that maps an example to a ddimensional emebedding space f : E → R d . We then rank the unlabelled training examples in E -E in the ascending order of their average similarity scores. We then select the top ones in the ascending order (i. 

4.2. NHP-D: LINK PREDICTION IN DIRECTED HYPERGRAPHS:

As explained in Section 3, hyperlink prediction in directed hypergraphs is the problem of predicting directing links which are tail-head set pairs. However, in practice the collection of the tail and head sets is also incomplete. Therefore, the problem of link prediction in directed hypergraphs also requires to predict missing tail and head sets of nodes besides predicting directed links among them. The tail and head sets of nodes can be thought of as undirected hyperlinks and the directed hyperlink is between these undirected hyperlinks. A straight forward approach for this problem would be to predict the undirected hyperlinks first and then followed by predicting the directed links between pairs. However, this sequential approach may not produce desirable results as the error during the training for directed part would not have any impact on the training for the undirected part. Therefore, we propose the following joint learning scheme, We denote W + L = {(t, h) ∈ E} to be a set of positively labelled directed pairs in loss L d . In other words d ij1 = 1 and d ij0 = 0 for all (i, j) ∈ W + L . The tail hyperlink and the corresponfding head hyperlink are separate hypernodes in the dual and form directed hyperlinks in the primal (with the direction from t to h). The set W + L consists of directed hyperlinks that currently exist in the given directed hypergraph. Note that, for loss L u , the set of positively labelled hypernodes will be,

EQUATION

EQUATION

We sample |W + L | = |E| hypernodes (in the dual) from the unlabelled data using the positive unlabelled approach of 3 to get the set of W - L pairs. We label these pairs negative i.e. d ij1 = 0 and d ij0 = 1 for all (i, j) ∈ W - L . We construct V - L = (t,h)∈W - L t ∪ h similarly as in 5. The sets

V L = V + L ∪ V - L and W L = W + L ∪ W -

L are used to minimise the objective 6. To explain how D is computed, we rewrite equation 1 as:

EQUATION

We use D = g(x 1 , x 2 ) with g being a function that takes the dual hypernode representations x 1 ∈ X and x 2 ∈ X and is parameterised by for example a simple neural network. In the experiments, we used a simple 2-layer multilayer perceptron on the concatenated embeddings x 1 ||x 2 i.e.

g(x 1 , x 2 ) = MLP Θ x 1 ||x 2 .

We train Θ (0) , Θ (1) , and Θ end-to-end using backpropagation.

5. EXPERIMENTS FOR UNDIRECTED HYPERLINK PREDICTION:

In this section, we evaluate NHP on hyperlink prediction in undirected hypergraphs. We performed two different sets of experiments whose motivations and setups are as follows.

Predicting reactions of metabolic networks: Reconstructed metabolic networks are important tools for understanding the metabolic basis of human diseases, increasing the yield of biologically engineered systems, and discovering novel drug targets. We used four datasets of (Zhang et al., 2018) and we show the statistics of the datasets used in table 1. For each dataset, we randomly generated fake reactions according to the substance distribution of the existing reactions. So, the candidate reactions contain already existing ones and the randomly generated fake ones. The number of fake reactions generated is equal to the number of already existing ones. Given a small number of reactions the task is to predict the other reactions. 2 and the construction of the datasets is pushed to the supplementary. A coauthorship hypergraph (primal) contains each author as a hypernode and each paper represents a hyperlink connecting all the authors of the paper. The corresponding dual hypergraph considers each author as a hyperlink connecting all the papers (hypernodes) coauthored by the author. The hyperlink prediction problem is given a small number of collaborations, to essentially predict other collaborations among a given set of candidate collaborations.

5.1. EXPERIMENTAL SETUP:

For each dataset we randomly sampled 10% of the hypernodes to get E and then we sampled an equal number of negatively-labelled hypernodes from E -E in the positive-unlabelled setting of 3. To get the feature matrix X, we used random 32-dimensional Gaussian features (p = 32 in equation 1) for the metabolic networks and bag-of-word features shown in table 2 for the coauthorship datasets.

For fake papers we generated random Gaussian bag-of-word features. We used node2vec (Grover & Leskovec, 2016) to learn low dimensional embedding mapping, f : E → R d with d = 128. We used the clique expansion of the dual hypergraph as input graph to node2vec and cosine similarity to compute similarity between two embeddings.

We compared NHP against the following state-of-the-art baselines for the same E as constructed above.

• Spectral hypergraph Clustering (SHC) (Zhou et al., 2006) : SHC outputs classification scores by f = (I -ξΘ) -1 y. We used SHC on the dual hypergraph. • node2vec (Grover & Leskovec, 2016): One of the most popular node embedding approaches. We note that (Grover & Leskovec, 2016) have shown node2vec to be superior to DeepWalk (Perozzi et al., 2014) and LINE (Tang et al., 2015) and hence we compared against only node2vec. We used node2vec to embed the nodes of the clique expansion (of the dual). We then used an MLP on the embeddings with the semi-supervised objective of equation 2 in the positive unlabelled setting of equation 3. graph can be seen as the star expansion of a hypergraph (Agarwal et al., 2006) with pins (hypernodes) on one side of the partition and boards (hyperlinks) on the other side. We have compared NHP against star expansion. This is essentially approximating the hypergraph with its star exapansion and then running a GCN over it (instead of the clique expansion of NHP).

5.2. EXPERIMENTAL RESULTS:

Similar to (Zhang et al., 2018) , we report mean AUC over 10 trials in table 3 and the mean number of hyperlinks recovered over 10 trials in the top ranked |∆E| ones in table 4 . Note that ∆E ⊂ E is the set of missing hyperlinks with |∆E| = 0.9 * |E|. As we can observe, we consistently outperform the baselines in both the metrics. We believe this is because of the powerful non-linear feature extraction capability of GCNs. We also report Recall@ |∆E| for NHP-U for all datasets (to make the numbers across datasets somewhat comparable). It is got through dividing the mean number of hyperlinks recovered by ∆E. We compared against the following baselines with a multi-layer perceptron (MLP):

6. EXPERIMENTS FOR DIRECTED HYPERLINK PREDICTION:

• node2vec (Grover & Leskovec, 2016) + MLP: We used node2vec for the undirected hyperlink prediction part (as explained in section 5 and a 2-layer perceptron to predict the direction between hyperlinks with the joint objective of equation 4. 

Λ,W ||A + U ΛU T -W W T || 2 F subject to λ i ∈ {0, 1}, i = 1, • • • , m W ≥ 0

We used a 2-layer perceptron in a sequential manner. To get a representation for a hyperlink e, we took the mean of the representations of all the hypernodes v ∈ e from the matrix W above. Note CMM works on the primal hypergraph. • GCN on star expansion (Ying et al., 2018) + MLP: We used the star expansion to approximate the input hypergraph and then run a GCN on it (instead of the clique expansion of NHP). A 2-layer perceptron is used to predict the direction between hyperlinks with the joint objective of equation 4.

As we see in the tables, both NHP-D (joint) and NHP-D (sequential) perform similarly. This can be attributed to the fact that training data to predict directions between hyperlinks is sparse and hence the learned hypernode representations of both the models are similar. Please note that existing apporaches for link prediction on directed simple graphs cannot be trivially adopted for this problem because of the sparsity in the training data.

Comparison to baselines NHP-D outperforms the baselines on 3 out of 4 datasets. The dataset iHN637 seems to be a very challenging dataset on which each model recovers less than half the number of missing hyperlinks.

7. COMPARISON OF POSITIVE UNLABELED LEARNING VS. NEGATIVE SAMPLING UNIFORMLY AT RANDOM:

In order to justify positive-unlabeled learning of equation 3, we compared NHP-U and negative samples chosen uniformly at random. The results for all the undirected hypergraph datasets are shown in tables 8 and 9. In the tables, we have called negative samples chosen uniformly at random from E -E as random negative sampling. We have called negative samples chosen through positive unlabeled learning of equation 3, i.e. NHP-U, as positive-unlabeled learning. Note that the numbers corresponding to this row are the same as those in tables 3 and 4.

In addition to the above two, we used positive unlabeled learning technique of equation 3 to sort the hyperedges (primal) in nondecreasing order of their similarities and then selected uniformly at random from only the first half of the sorted order (i.e. most dissimilar hyperedges). We have called this technique mixed as, intuitively, it provides benefits of both positive unlabeled learning and uniform random negative sampling. More principled approaches than mixed is left for future work.

DISCUSSION OF RESULTS:

As we can see in table 9, the standard deviations of random negative sampling are on the higher side. This is expected as the particular choice made for negative samples decides the decision boundary for the binary classifier. The superior AUC values of mixed in table 8 supports our intuition that it provides benefits of both positive unlabeled learning and uniform random negative sampling. The standard deviations of mixed are much lower but still higher than positive-unlabeled learning.

In general, summarising the results for all datasets, we believe that positive-unlabeled learning is superior to random negative sampling because of the higher confidence (low standard deviation) predictions.

8. CONCLUSION AND FUTURE WORK:

We have introduced NHP, a novel neural approach for hyperlink prediction in both undirected and directed hypergraphs. To the best of our knowledge, this is the first neural method for hyperlink prediction in undirected hypergraphs. NHP is also the first method for hyperlink prediction in directed hypergraphs. • DBLP: We used the DBLP database v43 . We filtered out papers without abstracts, and processed each abstract by tokenizing it and removing stop-words removal. Further, we filtered out papers with one author only. This left 540532 papers.

In order to ensure that the hypergraph formed would be sufficiently dense, we found the number of papers authored by each author and took the top 1000 authors as 'selected authors'. Then we filtered out the papers that were not authored by at least three of the selected authors. Finally, we were left with 1590 papers by 685 of the original 1000 selected authors.

To extract word features from each of these abstracts, we took all words appearing in these abstracts with a frequency greater than 50. Each abstract was thus represented by a 602-dimensional bag-of-words representation.

For both datasets, we randomly sample |E| fake papers according to the author distribution of the existing non-fake papers (2708 and 1590 for CORA and DBLP respectively). We randomly generated Gaussian p dimensional features for these fake papers (1433 and 602 for CORA and DBLP respectively).

:

https://people.cs.umass.edu/ mccallum/data.html

https://linqs.soe.ucsc.edu/data

https://aminer.org/lab-datasets/citation/DBLP-citation-Jan8.tar.bz2

Figures and Tables:

NHP-U: LINK PREDICTION IN UNDIRECTED HYPERGRAPHS Given an undirected hypergraph H = (V, E), as a first step NHP constructs a dual hypergraph H * = (V * , E * ) of H defined as follows. Hypergraph Duality (Scheinerman & Ullman, 2011) The dual hypergraph of a hypergraph H = (V, E) with V = {v 1 , . . . , v n } and E = {e 1 , . . . , e m }, denoted by H * = (V * , E * ) is obtained by taking V * = E as the set of hypernodes and E * = {e * 1 , . . . , e * n } such that e * i = {e ∈ E : v i ∈ e} with e * i corresponding to v i for i = 1, . . . , n. The vertex-hyperedge incidence matrices of H and H * are transposes of each other. The problem of link prediction in H can be posed as a binary node classification problem in H * (Lugo-Martinez & Radivojac, 2017). A label +1 on a node in H * indicates the presence of a hyperlink in H and a label of -1 indicates the absence. For the problem of semi-supervised node classification on the dual hypergraph H * , we use Graph Convolutional Networks (GCN) on the graph obtained from the clique expansion of H * . Clique expansion (Zhou et al., 2006; Feng et al., 2019) is a standard and a simple way of approximating a hypergraph into a planar graph by replacing every hyperlink of size s with an s-clique (Feng et al., 2018).

Figure 2: (best seen in colour) The proposed NHP framework. We convert the hypergraph with the observed hyperlinks and the candidate hyperlinks into its dual in which hyperlinks are converted into hypernodes. We then use a technique from positive unlaballed learning to get plausible negatively labelled hypernodes. The clique expansion of the hypergraph is used to approximate the hypergraph. Then a GCN is run on the graph to classify the unlabelled hypernodes. A label of +1 on e 1 indicates presence of the e 1 in the primal. For more details, refer to section 4.

e. with the lowest similarity values) to construct the set of plausible negative examples F ⊆ E -E. The intuition here is that the set of plausible negative examples contain examples most dissimilar to the positive examples. The GCN on the hypergraph can subsequently be run by minimising the objective 2 over the positive examples in E and the plausible negative examples in F i.e. V L = E ∪ F .

Co-ordinated Matrix Maximisation (CMM) (Zhang et al., 2018): The matrix factorisation-based CMM technique uses the EM algorithm to determine the presence or absence of candidate hyperlinks. • GCN on star expansion (Ying et al., 2018): PinSage (Ying et al., 2018) is a GCN-based method designed to work on the (web-scale) bipartite graph of Pinterest. The Pinterest

Bruna et al., 2014) by a mathematically sound definition of convolution on graph employing the analogy between the classical Fourier transforms and projections onto the eigen basis of the graph Laplacian operator(Hammond et al., 2011). Initial works proposed to learn smooth spectral multipliers of the graph Laplacian, although at high computational cost(Bruna et al., 2014;Henaff et al., 2015). To resolve the computational bottleneck and avoid the expensive computation of eigenvectors, the ChebNet framework(Defferrard et al., 2016) learns Chebyshev polynomials of the graph Laplacian (hence the name ChebNet). The graph convolutional network (GCN) (Kipf &

Table content: <table><tr><td>(RNN, spectral CNN, spatial CNN on graph) were unified into a single message passing neural</td></tr><tr><td>network (MPNN) framework (Gilmer et al., 2017) and a variant of MPNN has been shown to achieve</td></tr><tr><td>state-of-the-art results on an important molecular property prediction benchmark.</td></tr><tr><td>The reader is referred to a comprehensive literature review (Bronstein et al., 2017) and a survey</td></tr><tr><td>(Hamilton et al., 2017) on the topic of deep learning on graphs and learning representation on graphs</td></tr><tr><td>respectively. Below, we give an overview of related research in link prediction on hypergraphs where</td></tr><tr><td>relationships go beyond pairwise.</td></tr><tr><td>Link Prediction on hypergraphs: Machine learning on hypergraphs was introduced in a seminal</td></tr><tr><td>work (Zhou et al., 2006) that generalised the powerful methodology of spectral clustering to hyper-</td></tr><tr><td>graphs and further inspired algorithms for hypergraph embedding and semi-supervised classification</td></tr><tr><td>of hypernodes.</td></tr><tr><td>Link prediction on hypergraph (hyperlink prediction) has been especially popular for social networks</td></tr><tr><td>to predict higher-order links such as a user releases a tweet containing a hashtag (Li et al., 2013) and</td></tr><tr><td>to predict metadata information such as tags, groups, labels, users for entities (images from Flickr)</td></tr><tr><td>(Arya &amp; Worring, 2018). Techniques for hyperlink prediction on social networks include ranking</td></tr><tr><td>for link proximity information (Li et al., 2013) and matrix completion on the (incomplete) incidence</td></tr><tr><td>matrix of the hypergraph (Arya &amp; Worring, 2018; Monti et al., 2017). Hyperlink prediction has also</td></tr><tr><td>been helpful to predict multi-actor collaborations (Sharma et al., 2014).</td></tr><tr><td>In other works, a dual hypergraph has been constructed from the intial (primal) hypergraph to cast</td></tr><tr><td>the hyperlink prediction as an instance of vertex classification problem on the dual hypergraph</td></tr><tr><td>(Lugo-Martinez &amp; Radivojac, 2017). Coordinated matrix maximisation (CMM) predicts hyperlinks</td></tr><tr><td>in the adjacency space with non-negative matrix factorisation and least square matching performed</td></tr><tr><td>alternately in the vertex adjacency space (Zhang et al., 2018). CMM uses expectation maximisation</td></tr><tr><td>algorithm for optimisation for hyperlink prediction tasks such as predicting missing reactions of</td></tr><tr><td>organisms' metabolic networks.</td></tr></table>

Statistics of the four metabolic networks used as undirected hypergraphs

Table content: <table><tr><td>dataset</td><td colspan="4">iAF692 iHN637 iAF1260b iJO1366</td></tr><tr><td># substances, |V |</td><td>628</td><td>698</td><td>1668</td><td>1805</td></tr><tr><td># actual reactions, |E|</td><td>690</td><td>785</td><td>2388</td><td>2583</td></tr><tr><td># candidate reactions, |E|</td><td>2406</td><td>3050</td><td>7260</td><td>7672</td></tr><tr><td colspan="2">dataset</td><td/><td colspan="2">CORA DBLP</td></tr><tr><td colspan="2"># authors, |V |</td><td/><td>1072</td><td>685</td></tr><tr><td colspan="3"># actual papers (collaborations), |E|</td><td>2708</td><td>1590</td></tr><tr><td colspan="2"># candidate papers, |E|</td><td/><td>5416</td><td>3180</td></tr><tr><td colspan="3"># features (vocabulary size), p</td><td>1433</td><td>602</td></tr></table>

Statistics of the two coauthorship networks used as undirected hypergraphs

Table content: <table/>

mean AUC (higher is better) over 10 trials. NHP achieves consistently superior performance over its baselines for all the datasets. Refer to section 5 for more details.

Table content: <table><tr><td>dataset</td><td colspan="2">iAF692</td><td colspan="2">iHN637</td><td colspan="2">iAF1260b</td><td>iJO1366</td><td>CORA</td><td>DBLP</td></tr><tr><td>SHC (Zhou et al., 2006)</td><td/><td>0.69</td><td/><td>0.69</td><td colspan="2">0.69</td><td>0.70</td><td>0.61</td><td>0.64</td></tr><tr><td>node2vec (Grover &amp; Leskovec, 2016)</td><td/><td>0.72</td><td/><td>0.73</td><td colspan="2">0.71</td><td>0.70</td><td>0.59</td><td>0.61</td></tr><tr><td>CMM (Zhang et al., 2018)</td><td/><td>0.50</td><td/><td>0.54</td><td colspan="2">0.58</td><td>0.60</td><td>0.63</td><td>0.44</td></tr><tr><td colspan="2">GCN on star expansion (Ying et al., 2018)</td><td>0.56</td><td/><td>0.54</td><td colspan="2">0.53</td><td>0.48</td><td>0.54</td><td>0.42</td></tr><tr><td>NHP-U (ours)</td><td/><td>0.75</td><td colspan="2">0.75</td><td colspan="2">0.71</td><td>0.72</td><td>0.64</td><td>0.65</td></tr><tr><td>dataset</td><td>iAF692</td><td>iHN637</td><td/><td colspan="2">iAF1260b</td><td colspan="2">iJO1366</td><td>CORA</td><td>DBLP</td></tr><tr><td>SHC (Zhou et al., 2006)</td><td>248 ± 6</td><td colspan="2">289 ± 4</td><td colspan="2">1025 ± 4</td><td colspan="2">1104 ± 19</td><td>1056 ± 14</td><td>845 ± 18</td></tr><tr><td>node2vec (Grover &amp; Leskovec, 2016)</td><td>299 ± 10</td><td colspan="2">303 ± 4</td><td colspan="2">1100 ± 13</td><td colspan="2">1221 ± 21</td><td>1369 ± 15</td><td>813 ± 9</td></tr><tr><td>CMM (Zhang et al., 2018)</td><td>170 ± 6</td><td colspan="2">225 ± 10</td><td colspan="2">827 ± 1</td><td colspan="2">963 ± 15</td><td>1452 ± 13</td><td>651 ± 20</td></tr><tr><td>GCN on star expansion (Ying et al., 2018)</td><td>174 ± 5</td><td colspan="2">219 ± 12</td><td colspan="2">649 ± 10</td><td colspan="2">568 ± 18</td><td>1003 ± 14</td><td>646 ± 15</td></tr><tr><td>NHP-U (ours)</td><td>313 ± 6</td><td colspan="2">360 ± 5</td><td colspan="2">1258 ± 9</td><td colspan="2">1381 ± 9</td><td>1476 ± 20</td><td>866 ± 15</td></tr><tr><td># missing hyperlinks, |∆E|</td><td>621</td><td>706</td><td/><td>2149</td><td/><td>2324</td><td>2437</td><td>1431</td></tr><tr><td>Recall@ |∆E| for NHP-U</td><td>0.50</td><td>0.51</td><td/><td>0.58</td><td/><td>0.59</td><td>0.60</td><td>0.61</td></tr></table>

mean (± std) number of hyperlinks recovered over 10 trials (higher is better) among the top ranked |∆E| hyperlinks. NHP achieves consistently superior performance over its baselines for all the datasets. Refer to section 5 for more details.

Table content: <table/>

Statistics of the four metabolic networks used as directed hypergraphs

Table content: <table><tr><td>iAF692 iHN637 iAF1260b iJO1366</td></tr></table>

mean AUC over 10 trials for all the datasets. Both the proposed models achieve similar results. Refer to section 6 for more details.

Table content: <table><tr><td>dataset</td><td>iAF692</td><td>iHN637</td><td>iAF1260b</td><td>iJO1366</td></tr><tr><td>node2vec (Grover &amp; Leskovec, 2016) + MLP</td><td>255 ± 5</td><td>237 ± 5</td><td>838 ± 13</td><td>902 ± 11</td></tr><tr><td>CMM (Zhang et al., 2018) + MLP</td><td colspan="2">253 ± 9 241 ± 11</td><td>757 ± 26</td><td>848 ± 21</td></tr><tr><td colspan="3">GCN on star expansion (Ying et al., 2018) + MLP 242 ± 5 241 ± 10</td><td>786 ± 13</td><td>852 ± 11</td></tr><tr><td>NHP-D (sequential)</td><td>263 ± 7</td><td>221 ± 10</td><td>867 ± 31</td><td>954 ± 29</td></tr><tr><td>NHP-D (joint)</td><td>262 ± 8</td><td>236 ± 8</td><td>869 ± 13</td><td>944 ± 20</td></tr><tr><td># missing hyperlinks, |∆E|</td><td>467</td><td>514</td><td>1390</td><td>1683</td></tr><tr><td>Recall@ |∆E| for NHP-D (joint)</td><td>0.56</td><td>0.46</td><td>0.63</td><td>0.56</td></tr></table>

mean (± std) number of hyperlinks recovered over 10 trials (higher is better) among the top ranked |∆E| hyperlinks. Both the proposed models achieve similar results. Refer to section 6 for more details. We used the same four metabolic networks to construct directed hyperlinks. The metabolic reactions are encoded by stoichiometric matrices. The negative entries in a stoichiometric matrix indicate reactants and positive entries indicate products. We extracted only those reactions which have at least two substances in each of the reactant side and the product side and the statistics are shown in table5. We labelled randomly sampled 10% of the hyperlinks in the data and use the remaining 90% unlabelled data for testing. Tables6 and 7show the results on the datasets. NHP-D (joint) is the model proposed in 4.2. On the other hand, NHP-D (sequential) is the model which treats undirected hyperlink prediction and direction prediction separately. NHP-D (sequential) first runs a GCN on the clique expansion of the undirected hypergraph to get the node embeddings (without softmax) and then runs a multi-layer perceptron on the concatenated emebeddings to predict the directions.

Table content: <table><tr><td>dataset</td><td>iAF692</td><td>iHN637</td><td>iAF1260b</td><td>iJO1366</td><td>CORA</td><td>DBLP</td></tr><tr><td>random negative sampling</td><td>0.72</td><td>0.76</td><td>0.77</td><td>0.77</td><td>0.62</td><td>0.58</td></tr><tr><td>positive-unlabeled learning</td><td>0.75</td><td>0.75</td><td>0.71</td><td>0.72</td><td>0.64</td><td>0.65</td></tr><tr><td>mixed</td><td>0.78</td><td>0.79</td><td>0.78</td><td>0.79</td><td>0.74</td><td>0.69</td></tr></table>

mean AUC (higher is better) over 10 trials. Mixed consistently achieves the best AUC values. It provides benefits of both positive unlabeled learning and random negative sampling. Refer to section 7 for more details.

Table content: <table><tr><td>dataset</td><td>iAF692</td><td>iHN637</td><td>iAF1260b</td><td>iJO1366</td><td>CORA</td><td>DBLP</td></tr><tr><td>random negative sampling</td><td>236 ± 32</td><td>415 ± 47</td><td>967 ± 125</td><td>1074 ± 168</td><td>978 ± 181</td><td>543 ± 125</td></tr><tr><td>positive-unlabeled learning</td><td>313 ± 6</td><td>360 ± 5</td><td>1258 ± 9</td><td>1381 ± 9</td><td>1476 ± 20</td><td>866 ± 15</td></tr><tr><td>mixed</td><td>317 ± 11</td><td>481 ± 13</td><td>1202 ± 29</td><td>1336 ± 34</td><td>1496 ± 62</td><td>813 ± 36</td></tr><tr><td># missing hyperlinks, |∆E|</td><td>621</td><td>706</td><td>2149</td><td>2324</td><td>2437</td><td>1431</td></tr></table>

mean (± std) number of hyperlinks recovered over 10 trials among the top ranked |∆E| hyperlinks. Positive unlabeled learning of 3 achieves consistently lower standard deviations than the the other two. The standard deviations of random negative sampling are on the higher side. Refer to section 7 for more details.

Table content: <table/>

• Co-ordinated Matrix Maximisation (CMM) (Zhang et al., 2018) + MLP: The matrix factorisation-based CMM technique uses the EM algorithm to determine the presence or absence of candidate hyperlinks for the following optimisation problem:

Table content: <table><tr><td>min</td></tr></table>

Through extensive experiments on multiple real-world datasets, we have demonstrated NHP's effectiveness over state-of-the art baselines. Approaches that augment GCNs with attention (Veličković et al., 2018), self-training and co-training with random walks (Li et al., 2018), edge-feature learning in a dual-primal setup (Monti et al., 2018) have been recently proposed on graph-based semi-supervised learning tasks.Our NHP framework provides the flexibility to incorporate these approaches for more improved performance. An interesting future direction is predicting hyperlinks in partial-order hypergraphs(Feng et al., 2018). We leave extending NHP framework to inductive settings as part of future work. Hyperparameters of GCN used for all the datasets

Table content: <table><tr><td>hyperparameter</td><td>value</td></tr><tr><td>number of hidden units</td><td>16</td></tr><tr><td>number of hidden layers</td><td>2</td></tr><tr><td>dropout rate</td><td>0.5</td></tr><tr><td>L2 regularisation</td><td>5 × 10 -4</td></tr><tr><td>learning rate</td><td>0.01</td></tr><tr><td>non-linearity</td><td>ReLU</td></tr></table>

Peer review (iclr2019):
 [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 @ , 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”