Title: HYPER-SAGNN: A SELF-ATTENTION BASED GRAPH NEURAL NETWORK FOR HYPERGRAPHS

Abstract: Graph representation learning for hypergraphs can be used to extract patterns among higher-order interactions that are critically important in many real world problems. Current approaches designed for hypergraphs, however, are unable to handle different types of hypergraphs and are typically not generic for various learning tasks. Indeed, models that can predict variable-sized heterogeneous hyperedges have not been available. Here we develop a new self-attention based graph neural network called Hyper-SAGNN applicable to homogeneous and heterogeneous hypergraphs with variable hyperedge sizes. We perform extensive evaluations on multiple datasets, including four benchmark network datasets and two single-cell Hi-C datasets in genomics. We demonstrate that Hyper-SAGNN significantly outperforms the state-of-the-art methods on traditional tasks while also achieving great performance on a new task called outsider identification. Hyper-SAGNN will be useful for graph representation learning to uncover complex higher-order interactions in different applications.

1. INTRODUCTION:

Graph structure is a widely used representation for data with complex interactions. Learning on graphs has also been an active research area in machine learning on how to predict or discover patterns based on the graph structure (Hamilton et al., 2017b) . Although existing methods can achieve strong performance in tasks such as link prediction and node classification, they are mostly designed for analyzing pair-wise interactions and thus are unable to effectively capture higher-order interactions in graphs. In many real-world applications, however, relationships among multiple instances are key to capturing critical properties, e.g., co-authorship involving more than two authors or relationships among multiple heterogeneous objects such as "(human, location, activity)". Hypergraphs can be used to represent higher-order interactions (Zhou et al., 2007) . To analyze higher-order interaction data, it is straightforward to expand each hyperedge into pair-wise edges with the assumption that the hyperedge is decomposable. Several previous methods were developed based on this notion (Sun et al., 2008; Feng et al., 2018) . However, earlier work DHNE (Deep Hyper-Network Embedding) (Tu et al., 2018) suggested the existence of heterogeneous indecomposable hyperedges where relationships within an incomplete subset of a hyperedge do not exist. Although DHNE provides a potential solution by modeling the hyperedge directly without decomposing it, due to the neural network structure used in DHNE, the method is limited to the fixed type and fixed-size heterogeneous hyperedges and is unable to consider relationships among multiple types of instances with variable size. For example, Fig. 1 shows a heterogeneous co-authorship hypergraph with two types of nodes (corresponding author and coauthor). Due to the variable number of both authors and corresponding authors in a publication, the hyperedges (co-authorship) have different sizes or types. Unfortunately, methods for representation learning of heterogeneous hypergraph with variable-sized hyperedges, especially those that can predict variable-sized hyperedges, have not been developed.

In this work, we developed a self-attention based graph neural network, called Hyper-SAGNN that can work with both homogeneous and heterogeneous hypergraphs with variable hyperedge size. Using the same datasets in the DHNE paper (Tu et al., 2018) , we demonstrated the advantage of Hyper-SAGNN over DHNE in multiple tasks. We further tested the effectiveness of the method in predicting edges and hyperedges and showed that the model can achieve better performance from the multi-tasking setting. We also formulated a novel task called outsider identification and showed that Hyper-SAGNN performs strongly. Importantly, as an application of Hyper-SAGNN to singlecell genomics, we were able to learn the embeddings for the most recently produced single-cell Hi-C (scHi-C) datasets to uncover the clustering of cells based on their 3D genome structure (Ramani et al., 2017; Nagano et al., 2017) . We showed that Hyper-SAGNN achieved improved results in identifying distinct cell populations as compared to existing scHi-C clustering methods. Taken together, Hyper-SAGNN can significantly outperform state-of-the-art methods and can be applied to a wide range of hypergraphs for different applications.

2. RELATED WORK:

Deep learning based models have been developed recently to generalize from graphs to hypergraphs (Gui et al., 2016; Tu et al., 2018) . The HyperEdge Based Embedding (HEBE) method (Gui et al., 2016) aims to learn the embeddings for each object in a specific heterogeneous event by representing it as a hyperedge. However, as demonstrated in Tu et al. (2018) , HEBE does not perform well on sparse hypergraphs. Notably, previous methods typically decompose the hyperedge into pair-wise relationships where the decomposition methods can be divided into two categories: explicit and implicit. For instance, given a hyperedge (v 1 , v 2 , v 3 ), the explicit approach would decompose it directly into three edges, (v 1 , v 2 ), (v 2 , v 3 ), (v 1 , v 3 ), while the implicit approach would add a hidden node e representing the hyperedge before decomposition, i.e., (v 1 , e), (v 2 , e), (v 3 , e). The deep hypergraph embedding (DHNE) model, however, directly models the tuple-wise relationship using MLP (Multilayer Perceptron). The method is able to achieve better performance on multiple tasks as compared to other methods designed for graphs or hypergraphs such as Deepwalk (Perozzi et al., 2014) , node2vec (Grover & Leskovec, 2016) , and HEBE. Unfortunately, the structure of MLP takes fixed-size input, making DHNE only capable of handling k-uniform hypergraphs, i.e., hyperedges containing k nodes. To use DHNE for non-k-uniform hypergraphs or hypergraphs with different types of hyperedges, a function for each type of hyperedges needs to be trained individually, which leads to significant computational cost and loss of the capability to generalize to unseen types of hyperedges. Similarly, heterogeneous hyper-network embedding (Baytas et al., 2018 ) also used MLP as part of the model which requires fixed size input to train the model. Another recent method, hyper2vec (Huang et al., 2019) , can also generate embeddings for nodes within the hypergraph and outperforms other hypergraph embedding methods such as HGE (Yu et al., 2018) in the node classification task. However, hyper2vec cannot solve the link prediction problem directly as it only generates the embeddings of nodes in an unsupervised manner without a learned function to map from embeddings of nodes to hyperedges. Also, for k-uniform hypergraphs, hyper2vec is equivalent to node2vec, which cannot capture the high-order network structures for indecomposable hyperedges (as shown in Tu et al. (2018) ). Moreover, graph neural network based methods (Yadati et al., 2018; Feng et al., 2019; Bai et al., 2019) have been proposed to generalize the convolution operation or attention mechanism from graphs to hypergraphs. However, these methods mainly focus on the hypergraphs where node attributes are known and are typically used for semi-supervised node classification tasks. Similar to hyper2vec, these methods cannot be directly used for predicting hyperedges. Our Hyper-SAGNN in this work addresses all these challenges with a self-attention based graph neural network that can learn embeddings of the nodes and predict hyperedges for non-k-uniform heterogeneous hypergraphs.

3. METHOD:



3.1. DEFINITIONS AND NOTATIONS:

Definition 1. (Hypergraph) A hypergraph is defined as G = (V, E), where V = {v 1 , ..., v n } represents the set of nodes in the graph, and

E = {e i = (v (i) 1 , ..., v (i)

k )} represents the set of hyperedges. For any hyperedge e, it can contain more than two nodes (i.e., δ(e) ≥ 2). If all hyperedges within a hypergraph have the same size of k, it is called a k-uniform hypergraph. Note that even if a hypergraph is k-uniform, it can still have different types of hyperedges because the node type can vary for nodes within the hyperedges. Definition 2. (The hyperedge prediction problem) We formally define the hyperedge prediction problem. For a given tuple (v 1 , v 2 , ..., v k ), our goal is to learn a function f that satisfies:

f (v 1 , v 2 , ..., v k ) = ≥ s, if (v 1 , v 2 , ..., v k ) ∈ E < s, if (v 1 , v 2 , ..., v k ) / ∈ E (1)

where s is the threshold to binarize the continuous value of f into a label, which indicates whether the tuple is an hyperedge or not. Specifically, when we are given the pre-trained embedding vectors or the features of nodes X = {x 1 , ..., x i }, we can rewrite this function as:

EQUATION

where the vectors g(x i ) can be considered as the fine-tuned embedding or embedding vectors for the nodes. For convenience, we refer to x i as the features and g(x i ) as the learned embeddings.

3.2. STRUCTURE OF HYPER-SAGNN:

Our goal is to learn the functions f and g that take tuples of node features (x 1 , ..., x k ) as input and produce the probability of these nodes forming a hyperedge. Without the assumption that the hypergraph is k-uniform and the type of each hyperedge is identical, we require that f can take variable-sized, non-ordered input. Although simple functions such as average pooling f (g(x 1 ), ..., g(

x k )) = 1 K k i=1 g(x i

) satisfy this tuple-wise condition, previous work showed that the linear function is not sufficient to model this relationship (Tu et al., 2018) . DHNE used an MLP to model the non-linear function, but it requires that an individual function needs to be trained for different types of hyperedges. Here we propose a new method to tackle the general hyperedge prediction problem. , x k ), representing the features for nodes 1 to k, passes through two branches of the network resulting in static embeddings ( s1, s2, ..., s k ) and dynamic embeddings ( d1, d2, ..., d k ), respectively. The layer for generating dynamic embeddings is the multi-head attention layer. An example for its mechanism on node 1 here is shown in the figure as well. Then the pseudo-euclidean distance of each pair of static and dynamic embeddings is calculated by onelayered position-wise feed-forward network to produce probability scores (p1, p2, ..., p k ). These scores are further averaged to represent whether this group of nodes form a hyperedge.

Graph neural network based methods such as GraphSAGE (Hamilton et al., 2017a) typically define a unique computational graph for each node, allowing it to perform efficient information aggregation for nodes with different degrees. Graph Attention Network (GAT) (Veličković et al., 2017) utilizes a self-attention mechanism in the information aggregation process. Motivated by these properties, we propose our method Hyper-SAGNN based on the self-attention mechanism within each tuple to learn the function f . We first briefly introduce the selfattention mechanism. We use the same terms as the self-attention mechanism described in Vaswani et al. (2017) ; Veličković et al. (2017) . Given a group of nodes ( x 1 , x 2 , ..., x k ) and weight matrices W Q , W K , W V that represent linear transformations of features before applying the dot-product attention to be trained, we first compute the attention coefficients that reflect the pairwise importance of nodes:

e ij = W T Q x i T W T K x j , ∀1 ≤ i, j ≤ k (3)

We then normalize e ij by all possible j within the tuple through the softmax function, i.e.,

EQUATION

Finally, a weighted sum of the transformed features with an activation function is calculated:

EQUATION

In GAT, each node is applied to the self-attention mechanism usually with all its first-order neighbors. In Hyper-SAGNN, we aggregate the information for a node v i only with its neighbors for a given tuple. The structure of Hyper-SAGNN is illustrated in Fig. 2 .

The input to our model can be represented as tuples, i.e., ( x 1 , x 2 , ..., x k ). Each tuple first passes through a position-wise feed-forward network to produce ( s 1 , s 2 , ..., s k ), where s i = tanh(W T s x i ). We refer to each s i as the static embedding for node i since it remains the same for node i no matter what the given tuple is. The tuple also passes through a multi-head graph attention layer to produce a new set of node embedding vectors ( d 1 , d 2 , ..., d k ), which we refer to as the dynamic embeddings because they are dependent on all the node features within this tuple.

Note that unlike the standard attention mechanism described above, when calculating d i , we require that j = i in Eqn. (5). In other words, we exclude the term α ii W T V x i in the calculation of dynamic embeddings. Based on our results we found that including α ii would lead to either similar or worse performance in terms of hyperedge prediction and node classification (see Appendix A.6 for details). We will elaborate on the motivation of this choice later in this section.

With the static and dynamic embedding vectors for each node, we calculate the Hadamard power (element-wise power) of the difference of the corresponding static/dynamic pair. It is then further passed through a one-layered neural network with sigmoid as the activation function to produce a probability score p i . Finally, all the output p i ∈ [0, 1] is averaged to get the final p, i.e., Figure 3 : Illustration of the method for generating node features for node i in the hypergraph. In the walk based approach, a biased random walk on hypergraphs is used to produce walking paths (the yellow circles in the walking paths represent node i). These walks are further used to train a skip-gram model to generate features. In the encoder based approach, the i-th row of the adjacency matrix (as shown in the figure where the orange/white blocks represent whether or not node i is adjacent to other nodes in the graph) is used as the input to an autoencoder. The output of the encoder part is used as the features for node i.

EQUATION

By design, o i can be regarded as the squared weighted pseudo-euclidean distance between the static embedding s i and the dynamic one d i . It is called pseudo-euclidean distance because we do not require the weight to be non-zero or to sum up to 1. One rationale for allowing negative weights when calculating the distance could be the Minkowski space where the distance is defined as

d 2 = x 2 + y 2 + z 2 -t 2 .

Therefore, for these high-dimensional embedding vectors, we do not specifically treat them as euclidean vectors.

Our network essentially aims to build the correlation of the average "distance" of the static/dynamic embedding pairs with the probability of the node group forming a hyperedge.

Since the dynamic embedding is the weighted sum of features (with potential non-linear transformation) from neighbors within the tuple, this "distance" reflects how well the static embedding of each node can be approximated by the features of their neighbors within that tuple. This design strategy shares some similarities with the CBOW model in natural language processing (Mikolov et al., 2013) , where the model aims to predict the target word given its context (see Appendix A.5 for the analysis of the static/dynamic embedding pairs). In principle, we could still include the α ii term to obtain the embedding d * i . Alternatively, we can directly pass d * i through a fully connected layer to produce p * i while the rest remains the same. However, we argue that our proposed model would be able to produce s i that can be directly used for tasks such as node classification while the alternative approach is unable to achieve that (see Appendix A.6 for detailed analysis).

3.3. APPROACHES FOR GENERATING FEATURES:

In an inductive learning setting with known attributes for the nodes, x i can just be the attributes of the node. However, in a transductive learning setting without knowing the attributes of the nodes, we have to generate x i based on the graph structure solely. Here we use two existing strategies to generate features x i . As shown in Fig. 3 , the first approach is the random walk based method. We designed a biased random walk scheme for nodes in hypergraphs and used that to sample walks. Then, similar to node2vec, a skip-gram model is trained to generate features. The second approach is the encoder based approach where the corresponding row of the adjacency matrix is used as the features. The features are further passed through an autoencoder-like structure to reduce the dimensionality with the output of the hidden layer used as the features. The detailed description of these two approaches can be found in Appendix A.1.

4. RESULTS:

We sought to compare Hyper-SAGNN with the state-of-the-art method DHNE as it has already been demonstrated with superior performance over previous algorithms such as DeepWalk, LINE, and HEBE. We first used the same four datasets in the DHNE paper to have a direct comparison. The details on these datasets can be found in the Appendix A.2. The details on the parameters used in this section for both Hyper-SAGNN and other methods can also be found in the Appendix A.3. The details of the tasks and the evaluation metrics used in this section are explained in the Appendix A.4.

4.1. PERFORMANCE COMPARISON WITH EXISTING METHODS:

We evaluated the effectiveness of our embedding vectors and the learned function with the network reconstruction task. We compared our Hyper-SAGNN using the encoder based approach and also the model using the random walk based pre-trained embeddings against DHNE and the baseline node2vec. We first trained the model and then used the learned embeddings to predict the hyperedges of the original network. We sampled the negative samples to be 5 times the amount of the positive samples following the same setup of DHNE. We evaluated the performance based on both the AUROC (Area Under the Receiver Operating Characteristic curve) and the AUPR (Area under the Precision-Recall curve). As shown in Table 1 , Hyper-SAGNN can capture the network structure better than DHNE over all datasets either using the encoder based approach or the random walk based approach. We further assessed the performance of Hyper-SAGNN on the hyperedge prediction task. We randomly split the hyperedge set into training and testing set by a ratio of 4:1. The way to generate negative samples is the same as the network reconstruction task. As shown in Table 2 , our model again achieves significant improvement over DHNE for predicting the unseen hyperedges. The most significant improvement is from the wordnet dataset, which is about a 24.6% increase on the AUPR score. For network reconstruction and hyperedge prediction tasks, the difference between the random walk based Hyper-SAGNN and the encoder based Hyper-SAGNN is minor.

In addition to the tasks related to the prediction of hyperedges, we also evaluated whether the learned embeddings are effective for node classification tasks. A multi-label classification experiment and a multi-class classification experiment were carried out for the MovieLens dataset and the wordnet dataset, respectively. We used Logistic Regression as the classifier. data was chosen to be from 10% to 90% for the MovieLens dataset, and 1% to 10% for the wordnet dataset. We used averaged Mirco-F1 and Macro-F1 to evaluate the performance. The results are in Fig. 4 . We observed that Hyper-SAGNN consistently achieves both higher Micro-F1 and Macro-F1 scores over DHNE for different fractions of the training data. Also, Hyper-SAGNN based on the random walk generally achieves the best performance (Hyper-SAGNN-W in Fig. 4 ).

4.2. PERFORMANCE ON NON-k-UNIFORM HYPERGRAPH:

Next, we evaluated Hyper-SAGNN using the non-k-uniform heterogeneous hypergraph. For the above four datasets, we decomposed each hyperedge into 3 pairwise edges and added them to the existing graph. We trained our model to predict both the hyperedges and the edges (i.e., nonhyperedges). We then evaluated the performance for link prediction tasks for both the hyperedges and the edges. We also performed the node classification task following the same setting as above. The results for link prediction are in Table 2 . Fig. 4 shows the results for the node classification task. We observed that Hyper-SAGNN can preserve the graph structure on different levels. Compared to training the model with hyperedges only, including the edges into the training would not cause obvious changes in performance for hyperedge predictions (about a 1% fluctuation for AUC/AUPR).

We then further assessed the model in a new evaluation setting where there are adequate edges but only a few hyperedges presented. We asked whether the model can still achieve good performance on the hyperedge prediction based on this dataset. This scenario is possible in real-world applications especially when the dataset is combined from different sources. For example, in the drug dataset, it is possible that, in addition to the (user, drug, reaction) hyperedges, there are also extra edges that come from other sources, e.g., (drug, reaction) edges from the drug database, (user, drug) and (user, reaction) edges from the medical record. Here for each dataset that we tested, we used 50% of the edges and only 5% of the hyperedges to train the model. The results are in Fig. 5 .

When using only the edges to train the model, our method still achieves higher AUROC and AUPR score for hyperedge prediction as compared to node2vec (Table 2 ). We found that when the model is trained with both the downsampled hyperedge dataset and the edge dataset, it would be able to reach higher performance or suffer less from overfitting than being trained with each of the datasets individually. This demonstrates that our model can capture the consensus information on the graph structure across different sizes of hyperedges. 

4.3. OUTSIDER IDENTIFICATION:

In addition to the standard link prediction and node classification, we further formulated a new task called "outsider identification". Previous methods such as DHNE can answer the question of whether a specific tuple of nodes (v 1 , v 2 , ..., v k ) form a hyperedge. However, in many settings, we might also want to know the reason why this group of nodes will not form a hyperedge. We first define the outsider of a group of nodes as follows. Node v i is the outsider of the node group

EQUATION

We speculated that Hyper-SAGNN can answer this question by analyzing the probability score p 1 to p k (defined in Eqn. 7). We assume that the node v i with the smallest p i would be the outsider.

We then set the evaluation as follows. We first trained the model as usual, but at the final stage, we replaced the average pooling layer with the min pooling layer and fine-tuned the model for several epochs. We then fed the generated triplets with known outsider node into the trained model and calculated the top-k accuracy of the outsider node matching the node with the smallest probability. Because this task is based on the prediction results of the hyperedges, we only tested on the dataset that achieves the best hyperedge prediction, i.e., the drug dataset. We found that we have 81.9% accuracy for the smallest probability and 95.3% accuracy for the top-2 smallest probability. These results show that by switching the pooling layer we would have better outsider identification accuracy (from 78.5% to 81.9%) with the cost of slightly decreased hyperedge prediction performance (AUC from 0.955 to 0.935). This demonstrates that our model is able to accurately predict the outsider within the group even without further labeled information. Moreover, the performance of outsider identification can be further improved if we include the cross-entropy between p i and the label of whether v i is an outsider for all applicable triplets in the loss term. Together, these results show the advantage of Hyper-SAGNN in terms of the interpretability of hyperedge prediction.

4.4. APPLICATION TO SINGLE-CELL HI-C DATASETS:

We next applied Hyper-SAGNN to the recently produced single-cell Hi-C (scHi-C) datasets (Ramani et al., 2017; Nagano et al., 2017) . Genome-wide mapping of chromatin interactions by Hi-C (Lieberman- Aiden et al., 2009; Rao et al., 2014) has enabled comprehensive characterization of the 3D genome organization that reveals patterns of chromatin interactions between genomic loci. However, unlike bulk Hi-C data where signals are aggregated from cell populations, scHi-C provides unique information about chromatin interactions at single-cell resolution, thus allowing us to ascertain cell-to-cell variation of the 3D genome organization. Specifically, we propose that scHi-C makes it possible to model the cell-to-cell variation of chromatin interaction as a hyperedge, i.e., (cell, genomic locus, genomic locus). Note that the hyperedege here is "partially non-ordered", namely (cell i, locus j, locus k) should be equivalent to (cell i, locus k, locus j). Our method is able to guarantee that while DHNE cannot achieve that directly. For the analysis of scHi-C, the most common strategy would be revealing the cell-to-cell variation by embedding the cells based on the contact matrix and then applying the clustering algorithms such as K-means clustering on the embedded vectors. We performed the following evaluation to assess the effectiveness of Hyper-SAGNN on learning the embeddings of cells by representing the scHi-C data as hypergraphs.

We tested Hyper-SAGNN on two datasets. The first one consists of scHi-C from four human cell lines: HAP1, GM12878, K562, and HeLa (Ramani et al., 2017) . The second one includes the scHi-C that represents the cell cycle of the mouse embryonic stem cells (Nagano et al., 2017) . We refer to the first dataset as "Ramani et al. data", and the second as "Nagano et al. data" for abbreviation.

We trained Hyper-SAGNN with the corresponding datasets. Due to the large average degrees of cell nodes, the random walk approach would take an extensive amount of time to sample the walks. Thus, we only applied the encoder version of our method. We visualize the learned embeddings by reducing them to 2 dimensions with PCA and UMAP (McInnes et al., 2018) (Fig. 6A-D ).

We quantified the effectiveness of the embeddings by applying K-means clustering on the Ramani et al. data and evaluating with Adjusted Rand Index (ARI). In addition, we also assessed the effectiveness of the embeddings with a supervised scenario. We used Logistic Regression as the classifier with 10% of the cell as training samples and evaluated the multi-class classification task with Micro-F1 and Macro-F1. We did not run K-means clustering on the Nagano et al. data as it represents a state of continuous cell cycle which is not suitable for a clustering task. We instead used the metric ACROC (Average Circular ROC) developed in the HiCRep/MDS paper (Liu et al., 2018) to evaluate the performance of the three methods on the Nagano et al. data. We compared the performance with two recently developed computational methods based on dimensionality reduction of the contact matrix, HiC-Rep/MDS (Liu et al., 2018) and scHiCluster (Zhou et al., 2019) . Because Hyper-SAGNN is not a deterministic method for generating embeddings for scHi-C, we repeated the training process 5 times and averaged the score. All these results are in Fig. 6E . For the Ramani et al. data (Fig. 6A-B ), the visualization of the embedding vectors learned by Hyper-SAGNN exhibits clear patterns that cells with the same cell type are clustered together. Moreover, cell line HAP1, GM12878, and K562 are all blood-related cell lines, which are likely to be more similar to each other in terms of 3D genome organization as compared to HeLa. Indeed, we observed that they are also closer to each other in the embedding space. Quantitative results in Fig. 6E are consistent with the visualization as our method achieves the highest ARI, Micro-F1, Macro-F1 score among all three methods. For the Nagano et al. data, as shown in Fig. 6C -D, we found that the embeddings exhibit a circular pattern that corresponds to the cell cycle. Also, both HiC-Rep/MDS and Hyper-SAGNN achieve high ACROC scores. All these results show the effectiveness of representing the scHi-C datasets as hypergraphs using Hyper-SAGNN, which has great potential to provide insights into the cell-to-cell variation of higher-order genome organization.

5. CONCLUSION:

In this work, we developed a new graph neural network called Hyper-SAGNN for the representation learning of general hypergraphs. The model has the flexibility to deal with homogeneous and heterogeneous, and uniform and non-uniform hypergraphs. We demonstrated that Hyper-SAGNN can improve or match state-of-the-art performance for hypergraph representation learning while addressing the shortcomings of prior methods such as the inability to predict hyperedges for non-k-uniform heterogeneous hypergraphs. Hyper-SAGNN is computationally efficient as the input size to the attention layer is bounded by the maximum hyperedge size as opposed to the number of neighbors.

One potential improvement of Hyper-SAGNN as future work would be to allow information aggregation over all the first-order neighbors before calculating the static/dynamic embeddings for a node with the additional computational cost. With this design, the static embedding for a node would still satisfy our constraint that it is fixed for a known hypergraph with varying input tuples. This would allow us to incorporate previously developed methods on graphs, such as GraphSAGE (Hamilton et al., 2017a) and GCN (Kipf & Welling, 2016) , as well as methods designed for hypergraphs like HyperGCN (Yadati et al., 2018) into this framework for better link prediction performance. Such improvement may also extend the application of Hyper-SAGNN to semi-supervised learning.

A APPENDIX A.1 DETAILS OF THE STRATEGIES FOR GENERATING FEATURE VECTORS:

We first define the functions used in the subsequent sections as follows: a hyperedge e with weight w(e) is incident with a vertex v if and only if v ∈ e. We denote the indicator function that represents the incident relationship between v and e by h(v, e), which equals 1 when e is incident with v. The degree of vertex and the size of hyperedge are defined as: As shown on the right side of Fig. 3 , the first method to generate features is referred to as the encoder based approach, which is similar to the structure used in DHNE (Tu et al., 2018) . We first obtain the incident matrix of the hypergraph H ∈ R |V |×|E| with entries h(v, e) = 1 if v ∈ e and 0 otherwise. We also calculate the diagonal degree matrix D v containing the vertex degree d(v) = e∈E h(v, e).

d(v)

We thus have the adjacency matrix A = HH T -D v , of which the entries a(v i , v j ) denote the concurrent times between each pair of nodes (v i , v j ). The i-th row of A, denoted by a i , shows the neighborhood structures of the node v i , which then passes through a one-layer neural network to produce x i :

EQUATION

In DHNE, a symmetric structure was introduced where there are corresponding decoders to transform the x i back to a i . Tu et al. (2018) remarked that including this reconstruction error term would help DHNE to learn the graph structure better. We also include the reconstruction error term into the loss function, but with tied-weights between encoder and decoder to reduce the number of parameters that need to be trained.

A.1.2 RANDOM WALK BASED APPROACH:

Besides the encoder based approach, we also utilize a random walk based framework to generate the feature vectors x i (shown on the left side of Fig. 3 ). We extend the biased 2nd-order random walks proposed in node2vec (Grover & Leskovec, 2016) to generalize to hypergraphs. For a walk from v to x then to t, the strategies are described as follows.

The 1st-order random walk strategy given the current vertex x is to randomly select a hyperedge e incident with x based on the weight of e and then to choose the next vertex y from e uniformly (Zhou et al., 2007) . Therefore, the 1st-order transition probability is defined as:

EQUATION

We then generalize the 2nd-order bias α pq from ordinary graph to hypergraph for a walk from v to x to t as:

EQUATION

where the parameters p and q are to control the tendencies that encourage outward exploration and obtain a local view.

Next we add the above terms to set the biased 2nd-order transition probability as:

EQUATION

where Z is a normalizing factor.

With the well-defined 2nd-order transition probability π(t|v, x), we simulate a random walk of fixed length l through a 2nd-order Markov process marked by

P (c i = t|c i-1 = x, c i-2 = v) = π(t|v, x)

, where c i is the i-th node in the walk. A Skip-gram model (Mikolov et al., 2013; Mikolov et al., 2013) is then used to extract the node features from sampled walks such that the nodes that appear in similar contexts would have similar embeddings.

A.2 DETAILS OF THE DATASETS USED IN THIS WORK:

The four datasets used in the first part of our evaluation are:

• GPS (Zheng et al., 2010): GPS network. The hyperedges are based on (user, location, activity) relations.

• MovieLens (Harper & Konstan, 2015) : Social network. The hyperedges are based on (user, movie, tag) relations, describing peoples' tagging activities.

• drug: Medicine network from FAERS1 . The hyperedges are based on (user, drug, reaction) relations.

• wordnet (Bordes et al., 2013) : Semantic network from WordNet 3.0. The hyperedges are based on (head entity, relation, tail entity), expressing the relationships between words.

Details of the datasets are shown in Table A1 .

Table A1 : Datasets used in this work. Note that the columns under "#(V)" correspond to the columns under "node type" for each dataset. 

DATASETS NODE TYPE #(V) #(E):



A.3 PARAMETER SETTING:

We downloaded the source code of DHNE from its GitHub repository. The structure of the neural network of DHNE was set to be the same as what the authors described in Tu et al. (2018) . We tuned parameters such as the α term and the learning rate following the same procedure. We also tried adding dropout between representation vectors and the fully connected layer for better performance of DHNE. All these parameters were tuned until it was able to replicate or even improve the performance reported in the original paper. To make a fair comparison, for all the results below, we made sure that the training and validation data setups were the same across different methods.

For node2vec, we decomposed the hypergraph into pairwise edges and ran node2vec on the decomposed graph. For the hyperedge prediction task, we first used the learned embedding to predict pairwise edges. We then used the mean or min of the pairwise similarity as the probability for the tuple to form a hyperedge. We set the window size to 10, walk length to 40, the number of walks per vertex to 10, which are the same parameters used in DHNE for node2vec. However, we found that for the baseline method node2vec, when we tuned the hyper-parameter p, q and also used larger walk length, window size and walks per vertex (120, 20, 80 instead of 40, 10, 10) , it would achieve comparable performance for node classification task as DHNE. This observation is consistent with our designed biased hypergraph random walk. But this would result in a longer time for sampling the walks and training the skip-gram model. We therefore kept the parameters consistent with what was used in DHNE paper.

For our Hyper-SAGNN, we set the representation size to 64, which is the same as DHNE. The number of heads in the multi-head attention layer is set to 8. When using the encoder based approach to calculate x i , we set the encoder structure to be the same as the encoder part in DHNE. When using the random walk based approach, we decomposed the hypergraph into a graph as described above.

We set the window size to 10, walk length to 40, the number of walks per vertex to 10, to allow time-efficient generation of feature vector x i . The results in Section 4.1 showed that even when the pre-trained embeddings are not so ideal, Hyper-SAGNN can still well capture the structure of the graph.

To train the model, we used the Adam optimizer with learning rate 1e-3. Each batch contains 96 positive hyperedges with 480 negative samples. The training is terminated when it reaches the maximum training epoch number ( 100) or the performance on the validation set no longer improves.

A.4 EXPERIMENT SETTING:

To compare the performance of Hyper-SAGNN with other baseline methods, we used the same three tasks in the DHNE paper, i.e., network reconstruction, link prediction, and node classification. In this section, we describe the setting of these three tasks and the evaluation metrics.

Network reconstruction aims to reconstruct the input hypergraph from the learned embedding. Specifically, a hypergraph G = (V, E) is used as input to the algorithm. After training, the model makes predictions for the original hyperedge set E. Link prediction, on the other hand, aims to predict the unseen hyperedge set E based on the model trained with hypergraph G = (V, E). These two tasks can be regarded as binary classification tasks and thus can be evaluated by metrics such as AUROC and AUPR. For both tasks, the negative samples are set to be 5 times the amount of the positive samples following the same setup of DHNE.

For the node classification, after training the model, the embeddings for the nodes are used to train a Logistic Regression classifier with targets as the pre-defined labels for the nodes. Here we have a multi-label classification and a multi-class classification task for dataset MovieLens and wordnet, respectively, making the metrics defined for binary classification not applicable. Therefore, the performances are evaluated by Micro and Macro F1 scores that are used for quantifying the performance of multi-label/multi-class classification.

A.5 ANALYSIS OF THE DYNAMIC EMBEDDINGS:

In this section, we discuss the relationships between dynamic embeddings and static embeddings.

As mentioned in the Method section, we design the model to establish the connection between the probability score for a tuple with how well the static embedding of each node can be approximated by the features of their neighbor within that tuple. If the model works as we designed, the dynamic embedding of node i conditioned on an actual hyperedge (i, j, ..., k) should approximate the static embedding of node i better. In contrast, the dynamic embedding of node i when it is a member of a non-hyperedge tuple would not have a good "approximation". To evaluate this, after training the model we collected all the dynamic embeddings for nodes when they are within the tuples of positive samples, which would be referred to as positive dynamic embeddings. We also collected the dynamic embeddings for nodes when conditioned on the "hard negative samples" (the negative samples that are generated by only changing one node in the positive samples), which would be referred to as negative dynamic embeddings. We tested whether the positive dynamic embeddings indeed resemble the static embeddings better by comparing the performance of node classification using dynamic embeddings and static embeddings. For each node, since the number of positive and negative dynamic embeddings is not finite, we sampled and averaged a number of them as the features. The remaining setting of node classification is the same as described in the main text. As shown in Fig. A1 , in general, the positive dynamic embeddings can achieve much better performance as compared to the negative dynamic embeddings. Both the micro and macro F1 scores increase when more positive dynamic embeddings are sampled and averaged. When averaging all positive dynamic embeddings and using those as features, the node classification performance is close to what we achieved using static embeddings. This analysis demonstrates that the positive dynamic embeddings "approximate" the static embeddings as they contain sufficient information for accurate node classification. In addition, for the negative dynamic embeddings where only one node is changed when generating negative samples, it performs dramatically worse. Note that we exclude the α ii term in the calculation of dynamic embeddings, which makes the dynamic embedding for node i the combination of features of its neighbor within a given tuple. These results demonstrate that the probability scores for each node indicate the "distances" of static/dynamic embedding pairs that reflect how well the static embedding of each node can be approximated by the features of their neighbor within that tuple. The results based on static embeddings are marked as "static". Results based on positive/negative dynamic embeddings are marked as "dynamic P/dynamic N". The numbers of dynamic embeddings sampled during this process are also included in the legend.

A.6 COMPARISON OF HYPER-SAGNN VS. THE VARIANTS As mentioned above, unlike the standard GAT model, we exclude the α ii term in the self-attention mechanism. To test whether this constraint would improve or reduce the model's ability to learn, we implemented a variant of our model (referred to as variant type I) by including this term. Also, as mentioned in the Method section, another potential variant of our model would be directly using the d * i to calculate the probability score p * i . We refer to this variant as variant type II. For variant type II, on node classification task, since it does not have a static embedding, we used W T v x i . The rest of the parameters and structure of the neural network remain the same.

We then compared the performance of Hyper-SAGNN and two variants in terms of AUC and AUPR values for network reconstruction task and hyperedge link prediction task on the following four datasets: MovieLens, wordnet, drug, and GPS. We also compared the performance in terms of the Micro F1 score and Macro F1 score on the node classification task on the MovieLens and the wordnet dataset. For the MovieLens dataset, we used 90% nodes as training data while for wordnet, we used 1% of the nodes as training data. All the evaluation setup is the same as described in the main text. To avoid the effect of randomness from the neural network training, we repeated the training process for each experiment five times and made the line plot of the score versus the epoch number. To illustrate the differences more clearly, we started the plot at epoch 3 for the random walk based approach and epoch 12 for the encoder based approach. The performance of the model using the random walk based approach is shown in Fig. A2 to Fig. A5 . The performance of the model using the encoder based approach is shown in Fig. A6 to Fig. A9 .

For models with the random walk based approach, Hyper-SAGNN is the best in terms of all metrics for the GPS, MovieLens, and wordnet dataset. On the drug dataset, Hyper-SAGNN achieves higher AUROC and AUPR score on the network reconstruction task than two variants, but slightly lower AUROC score for the link prediction task (less than 0.5%).

For models with the encoder based approach, the advantage is not that obvious. All 3 methods achieve similar performance in terms of all metrics for the GPS and the drug dataset. For the Movie-Lens and wordnet dataset, Hyper-SAGNN performs similar to variant type I, higher than variant type II on the network reconstruction and link prediction task. However, our model achieves slightly higher accuracy on the node classification task than variant type I.

Therefore, these evaluations show that the choice of the structure of Hyper-SAGNN can achieve higher or at least comparable performance than the two potential variants over multiple tasks on multiple datasets. 

:

http://www.fda.gov/Drugs/

Figures and Tables:

Figure 1: An example of the coauthorship hypergraph. Here authors are represented as nodes (in dark blue and light blue) and coauthorships are represented as hyperedges.

Figure 2: Structure of the neural network used in Hyper-SAGNN. The input ( x1, x2, ..., x k ), representing the features for nodes 1 to k, passes through two branches of the network resulting in static embeddings ( s1, s2, ..., s k ) and dynamic embeddings ( d1, d2, ..., d k ), respectively. The layer for generating dynamic embeddings is the multi-head attention layer. An example for its mechanism on node 1 here is shown in the figure as well. Then the pseudo-euclidean distance of each pair of static and dynamic embeddings is calculated by onelayered position-wise feed-forward network to produce probability scores (p1, p2, ..., p k ). These scores are further averaged to represent whether this group of nodes form a hyperedge.

Figure4: Performance of classification on MovieLens and wordnet datasets. Hyper-SAGNNs trained with the random walk based approach and the encoder based approach are marked as Hyper-SAGNN-W, Hyper-SAGNN-E, respectively. The models trained with a mix of edges and hyperedges are denoted with "(mix)".

Figure 5: AUROC and AUPR scores of Hyper-SAGNN for hyperedge prediction on the downsampled dataset over training epochs.

Figure 6: (A) and (B): Visualization of the learned embedding based on Hyper-SAGNN for the Ramani et al. data. (C) and (D): Visualization of the learned embedding based on Hyper-SAGNN for the Nagano et al. data. Embedding vectors are projected to two dimensional space using either UMAP or PCA. (E): Quantitative evaluation of the Hyper-SAGNN on two scHi-C datasets

Figure A1: Node classification performance comparison for static embeddings and dynamic embeddings.The results based on static embeddings are marked as "static". Results based on positive/negative dynamic embeddings are marked as "dynamic P/dynamic N". The numbers of dynamic embeddings sampled during this process are also included in the legend.

Figure A2: Performance comparison of Hyper-SAGNN -Walk and Variant Type I, II (GPS)

AUC and AUPR values for network reconstruction. The models trained with the random walk based approach and the encoder based approach are marked as Hyper-SAGNN-W and Hyper-SAGNN-E, respectively.

Table content: <table><tr><td/><td colspan="2">GPS</td><td colspan="2">MOVIELENS</td><td colspan="2">DRUG</td><td colspan="2">WORDNET</td></tr><tr><td/><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td></tr><tr><td>node2vec-mean</td><td>0.572</td><td>0.188</td><td>0.557</td><td>0.197</td><td>0.668</td><td>0.246</td><td>0.613</td><td>0.215</td></tr><tr><td>node2vec-min</td><td>0.570</td><td>0.187</td><td>0.535</td><td>0.186</td><td>0.682</td><td>0.257</td><td>0.576</td><td>0.201</td></tr><tr><td>DHNE</td><td>0.959</td><td>0.836</td><td>0.974</td><td>0.878</td><td>0.952</td><td>0.873</td><td>0.989</td><td>0.953</td></tr><tr><td>Hyper-SAGNN-E</td><td>0.971</td><td>0.877</td><td>0.991</td><td>0.952</td><td>0.977</td><td>0.916</td><td>0.989</td><td>0.950</td></tr><tr><td>Hyper-SAGNN-W</td><td>0.976</td><td>0.857</td><td>0.998</td><td>0.986</td><td>0.988</td><td>0.945</td><td>0.994</td><td>0.956</td></tr></table>

The proportion of the training

Table content: <table><tr><td>0.48</td><td colspan="4">MovieLens Micro F1</td><td>wordnet Micro F1</td><td>0.32</td><td colspan="4">MovieLens Macro F1</td><td>0.55</td><td>wordnet Macro F1</td></tr><tr><td>0.44</td><td/><td/><td/><td>0.60</td><td/><td>0.28</td><td/><td/><td/><td>0.45</td></tr><tr><td>0.40</td><td/><td/><td/><td>0.50</td><td/><td>0.24</td><td/><td/><td/><td>0.35</td><td>DHNE Hyper-SAGNN-W Hyper-SAGNN-E</td></tr><tr><td/><td/><td/><td/><td>0.40</td><td/><td>0.20</td><td/><td/><td/><td>0.25</td><td>Hyper-SAGNN-W(mix) Hyper-SAGNN-E(mix)</td></tr><tr><td>0.36</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>0.02 0.04 0.06 0.08</td><td/><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>0.02 0.04 0.06 0.08</td></tr></table>

Performance evaluation based on AUROC and AUPR for hyperedge/edge prediction. Methods with annotation (mix) represent Hyper-SAGNN trained with a mixture of edges and hyper-edges. Datasets marked with "(2)" represent the performance on pair-wise edge prediction (i.e., non-hyperedges).

Table content: <table><tr><td/><td colspan="2">GPS</td><td colspan="2">MOVIELENS</td><td colspan="2">DRUG</td><td colspan="2">WORDNET</td></tr><tr><td/><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td></tr><tr><td>node2vec -mean</td><td>0.563</td><td>0.191</td><td>0.562</td><td>0.197</td><td>0.670</td><td>0.246</td><td>0.608</td><td>0.213</td></tr><tr><td>node2vec -min</td><td>0.570</td><td>0.185</td><td>0.539</td><td>0.186</td><td>0.684</td><td>0.258</td><td>0.575</td><td>0.200</td></tr><tr><td>DHNE</td><td>0.910</td><td>0.668</td><td>0.877</td><td>0.668</td><td>0.925</td><td>0.859</td><td>0.816</td><td>0.459</td></tr><tr><td>Hyper-SAGNN-E</td><td>0.952</td><td>0.798</td><td>0.926</td><td>0.793</td><td>0.961</td><td>0.895</td><td>0.890</td><td>0.705</td></tr><tr><td>Hyper-SAGNN-W</td><td>0.922</td><td>0.722</td><td>0.930</td><td>0.810</td><td>0.955</td><td>0.892</td><td>0.880</td><td>0.706</td></tr><tr><td>Hyper-SAGNN-E (mix)</td><td>0.950</td><td>0.795</td><td>0.928</td><td>0.799</td><td>0.956</td><td>0.887</td><td>0.881</td><td>0.694</td></tr><tr><td>Hyper-SAGNN-W (mix)</td><td>0.920</td><td>0.720</td><td>0.929</td><td>0.811</td><td>0.950</td><td>0.889</td><td>0.884</td><td>0.684</td></tr><tr><td/><td colspan="2">GPS (2)</td><td colspan="2">MOVIELENS (2)</td><td colspan="2">DRUG (2)</td><td colspan="2">WORDNET (2)</td></tr><tr><td/><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td><td>AUC</td><td>AUPR</td></tr><tr><td>Hyper-SAGNN-E (mix)</td><td>0.921</td><td>0.899</td><td>0.971</td><td>0.967</td><td>0.981</td><td>0.973</td><td>0.891</td><td>0.897</td></tr><tr><td>Hyper-SAGNN-W (mix)</td><td>0.931</td><td>0.910</td><td>0.999</td><td>0.999</td><td>0.999</td><td>0.999</td><td>0.923</td><td>0.916</td></tr></table>

Peer review (iclr2020):
This paper proposes a new graph neural network model capable of performing tasks over hyperedges of variable type and size (i.e. different number and types of graph nodes connected by different hyperedges). They experimentally verify its effectiveness over the previous state of the art on several datasets and tasks. I lean toward accepting this paper. It is a relevant topic area, the design appears novel relative to recent work, and the presentation is mostly clear. The design decisions are well-motivated and discussed (e.g. the choices to use the static embedding, the exclusion of the diagonal self-attention weights). Performance is tested on previously used datasets and tasks, for a thorough comparison against recent best methods (DHNE). The model is clearly described. A possible weakness of this paper is that the evaluation data sets are all k-uniform hypergraphs with k=3. This is perhaps the minimal case which their method can address. For all the discussion of generality to heterogeneous hyperedges, it would have been better to include some dataset (even if synthetic) to establish baseline performance over while ablating k>3 and multiple hyperedge types. This remains completely un-investigated (even the genome dataset appears to be k=3?). Although, their edge/hyperedge ablation on these datasets partially addresses the point and the result (Fig 5) seems promising. Some other notes: Eq 5. Given that it is the default, explicitly write that the summation is over j!=i Eq 8. Probably leave the ellipses out between v_{i-1} and v_{i+1}? The tasks and measures like AUC, AUPR, and network reconstruction could be described somewhere, even if in an appendix. Some/many training hyperparameters not listed? EDIT: Post rebuttal, authors have provided evidence of good performance on data sets with k=4 and k=5, addressing my main concern, and have addressed the smaller notes. Raising score but still am not expert in this area.