Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Authors: Ruochi Zhang
Yuesong Zou
Jian Ma
Venue:  (2020)
Keywords: graph neural network
hypergraph
representation learning

Abstract: Graph representation learning for hypergraphs can be utilized 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 state-of-the-art methods on traditional tasks while also achieving great performance on a new task called outsider identification. We believe that Hyper-SAGNN will be useful for graph representation learning to uncover complex higher-order interactions in different applications. 

Published as a conference paper at ICLR 2020
HYPER-SAGNN: A SELF-ATTENTION BASED GRAPH NEURAL NETWORK FOR HYPERGRAPHS
Ruochi Zhang
Yuesong Zou
Jian Ma
School Computer Science Carnegie Mellon University
School of Computer Science Carnegie Mellon University III, Tsinghua University
School of Computer Science
Camneiie Mellon University j jianma@ @ css cmu edd
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 generie for various learning tasks. Indeed, models that can predict variable-sized heterogeneous hy- peredges have not been available. Here we develop a new self-attention based graph neural network called Hyper-SAGNN applicable to homogeneous and het- erogeneous 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 significantly outperforms the ofate-of-the-an 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 plex higher-order interactions in different applications.
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 how to predict or dis- cover patterns based on the graph structure (Hamilton et al.] 20176). Although existing meth- ods achieve strong performance in tasks such 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, rela- tionships 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 interac- tions (Zhou et al. 2007). To analyze higher-order interaction data, is straightforward to ex- pand each hyperedge into pair-wise edges with the assumption that the hyperedge is decomposable. Several previous methods were developed based on this no- tion (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 indecom- posable hyperedges where relationships within an incom- plete subset of a hyperedge do not exist. Although DHNE provides a potential solution by modeling the hyperedge di- rectly 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. [ shows a heteroge- neous co co-authorship hypergraph with two types of nodes (corresponding author and coauthor). Due to the variable number of both authors and corresponding authors in publication, the hyperedges (co-authorship) have different sizes types. Unfortunately, methods for representation learning heterogeneous hypergraph with variable-sized hyperedges, especially those that predict variable-sized hyperedges, have not been developed.
Coauthorship (hyperedge) Corresponding Author (node) Coauthor (node)
example of the authorship hypergraph. Here authors are represented as nodes (in dark blue and light blue) and coauthorships are repre- sented hyperedges.
Figure 1:

---

Published as a conference paper at ICLR 2020
In this work, we developed self-attention based graph neural network, called Hyper- 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), 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 single- cell genomics, we were able to learn the embeddings for the most recently produced single-cell Hi-C (scHi-C) -C) datasets uncover the clustering of cells based on their 3D genome structure (Ra-) mani et al., 2017 Nagano et al. 2017). We showed that Hyper-SAGNN achieved improved results in identifying distinet cell populations as compared to existing scHi-C clustering methods. Taken together, Hyper-SAGNN can significantly outperform state-of-the-ard methods and can be applied to a wide range of hypergraphs for different applications.
RELATED WORK
Deep learning based models have been developed recently to generalize from graphs to hyper- graphs (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 rep- resenting 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: ex- plicit and implicit. For instance, given hyperedge (v1, 02, 22)2 the explicit approach would decom- pose it directly into three edges, (V), 02). (12, U3), (2), va). while the implicit approach would add hidden node representing the hyperedge before decomposition, i.e., (vi,e), e), (12, e), (13,e) e). The deep hypergraph embedding (DHNE) model, however, directly models the tuple-wise relationship using MLP (Multilayer Perceptron). The method is able achieve better performance on multiple tasks as compared to other methods designed for graphs or hypergraphs such as Deepwalk (Per-) 077i 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 individu- ally, 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 al., (2019), can also generate embeddings for nodes within the hyper- graph 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, hyper2vee is equivalent to node2vec, which cannot capture the high-order network structures for indecomposable hyperedges (as shown in Tu 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 fo- cus 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 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, where V = fei,..., 2
represents the set of nodes in the graph, and E {o; (o ((.,,()))))) (())) represents the set of hyperedges. For any hyperedge e, it can contain more than two nodes (i.c., ō(e) > 2). If all hyperedges within a hypergraph have the same size of k; it is called k-uniform hypergraph. Note
2

---

Published as a conference paper at ICLR 2020
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 (U1, 222, ..., Uk) our goal is to learn a function f that satisfies:
8, if (U1, 02 ... (x) E E f(U1. U2, Uk) = < s, if (V1, 02 Uk) $ E
(1)
where s is the threshold to binarize the continuous value of f into 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 = {II, z. we can rewrite this function as:
f(11, 022 ..., 2k) _ f(g(z1), ((22) g(x)))
(2)
where the vectors g(x;) can be considered as the fine-tuned embedding or embedding vectors for the nodes. For convenience, we refer to H; as the features and g(x;)) the learned embeddings.
3.2 STRUCTURE OF HYPER-SAGNI
Our goal is learn the functions and g that take tuples of node features (#1,..., as in- put and produce the probability of these nodes forming a hyperedge. Without the assumption that the hypergraph k--uniform and the type of each hyperedge identical, we require that f can take variable-sized, non-ordered input. Although simple functions such as average pooling * "i=g(r> g(z)) 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 requires that an individual function needs be trained for different types of hyperedges. Here we propose a new method to tackle the general hyperedge prediction problem.
Graph neural network based methods such as GraphSAGE (Hamilton al. 2017a) typically define unique com- putational graph for each node, al- lowing it to perform efficient informa- tion aggregation for nodes with differ- ent degrees. Graph Attention Network (GAT) (Veličković et al., 2017) utilizes self self-attention mechanism in the infor- mation aggregation process. Motivated by these properties, propose our method Hyper-SAGNN based on the self-attention mechanism within each tuple to learn the function f.
Multi-head Attention on mode
Multi-head Attention
d
Gu
(di 5,
( Rc)
Hadamard power
Sigmoud
Average
Structure of the neural network used in Hyper- SAGNN. The input (τi, H.,... representing the fcatures for nodes to passes through two branches of the network resulting in static embeddings (31, 82.... 56) and dynamic em- beddings (d1, d2, di), respectively. The layer for generat- ing dynamic embeddings is the multi-head attention layer. An example for its mechanism on node here is shown in the figure well. Then the pseudo-euclidean distance of each pair of static and dynamic embeddings is calculated by one- layered position-wise feed-forward network to produce proba- bility scores (p1, P2...., Pw). These scores are further averaged represent whether this group of nodes form hyperedge.
Figure 2:
We first briefly introduce the self- attention 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 11 22, .... Z&)) and weight matrices Wo. K, Wv that represent linear transformations of features be- fore applying the dot-product attention to be trained, we first compute the at- tention coefficients that reflect the pair- wise importance of nodes:
G = (W? T (WKx;) VI We then normalize eg by all possible j within the tuple through the sofumax function, i.e.,
(3)
exp(e.y)
aij = Σ Eisieh exp(ea)
(4)
3

---

Published as a conference paper at ICLR 2020
Finally, weighted sum of the transformed features with activation function is calculated:
d; tanh
Oisy WV az
(5)
In GAT, each node is applied to the self-attention mechanism usually with all its first-order neigh- bors. In Hyper-SAGNN, we aggregate the information for node 22 only with its neighbors for given tuple. The structure of Hyper-SAGNN is illustrated in Fig. 2
The imput our model can be represented as tuples, i.c., (2,, RK). Each tuple first passes through a position-wis -isse feed-forward network to produce (31, 82, ..., 5k), where 8; = tanh ( z²). We refer each as the static embedding for node since it remains the same for node i no matter what the given tuple is. The tuple also passes through a multi-heal graph attention layer to produce a new set of node embedding vectors (dj, d2. d 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, we require that j o i in Eqn. 5 In other words, we exclude the term og W,,W in the calculation of dynamic embeddings. Based on our results we found that including 0g would lead to either similar or worse performance in terms of hyperedge prediction and node classification (see Appendix 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, calculate the Hadamard power (element-wise power) of the difference of the corresponding static/dynamic pair. It then fur- ther passed through a one-layered neural network with sigmoid the actívation function pro- duce a probability score pi. Finally, all the output E
[0, 1] is averaged to get the final p, i.e.
0: W. ((ds 3,))0)+ +
(6)
R
E p: Σ (o.)
(7)
Walk Based Approach
By design, o can be regarded the squared weighted pseudo-euclidean distance between the static embedding & and the dynamic one d, It called pseudo-euclidean distance because we do not require the weight to be non-zero or to sum up to One rationale for allowing nega- tive weights when calculating the distance could be the Minkowski space where the distance is de- fined as d² = x² + + 2² t². Therefore, for these high-dimensions do not specifically treat them as euclidean vec-
Encoder Appraahi
Blased Random Waik
Skip gram Model
embedding vectors, we
tors.
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 hy- pergraphs is used to produce walking paths (the yel- low circles in the walking paths represent node i). These walks are further used to train skip-gram model generate features. In the encoder hased approach, the i-th row 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 an auto- encoder. The output of the encoder part is used as the features for node i.
Our network essentially aims to build the correlation of the average "distance" of the static/dynamic embedding pairs with the proba- bility of the node group forming a hyperedge. Since the dynamic embedding is the weighted sum of features (with potential non-lineat trans- formation) 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) eet 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, could still include the Ois
4

---

Published as a conference paper at ICLR 2020
term obtain the embedding di. Alternatively, layer to produce p while the rest remains the same. However, we argue that our proposed model would be able to produce s; that can be directly used for tasks such node classification while the alternative approach is unable to achieve that (see Appendix A.6 for detailed analysis).
directly pass dj through fully connected
3.3 APPROACHES FOR GENERATING FEATURES
In inductive learning setting with known attributes for the nodes, ã. can just be the attributes of the node. However, in a transductive learning setting without knowing the attributes of the nodes, have generate z based on the graph structure solely. Here we use two existing strategies to generate features z.. As shown in Fig. B the first approach is the random walk based method. We designed biased random walk scheme for nodes in hypergraphs and used that sample walks. Then, similar to node2vec, a skip-gram model is trained to generate features. The second approach 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-lik 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. A.I
4 RESULTS
We sought to compare Hyper-SAGNN with the state-of-the-ar 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 HlyperSAAGN 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 hyper- edges 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- rreaal curve). As shown in Table 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.
Table 1: AUC and AUPR values for network reconstruction. The models trained with the random walk based approach and the encoder hased approach are marked as Hyper-SAGNN-W and Hyper-SAGNN-FF respectively.
GPS
MOVIELENS
DRUG
WORDNET
AUC
AUPR
AUC
AUPR
AUC
AUPR
AUC
AUPR
node2vec-mean
0.572
0.188
0.557
0.197
0.668
0.246
0.613
0.215
node2vec-min
0.570
0.187
0.535
0.186
0.682
0.257
0.576
0.201
DHNE
0.959
0.836
0.974
0.878
0.952
0.873
0.989
0.953
Hyper-SAGNNE
0.971
0.877
0.991
0.962
0.977
0.916
0.989
0.950
Hyper-SAGNN-W
0.976
0.857
0.998
0.986
0.988
0.945
0.994
0.956
We further assessed the performance of Hyper-SAGNN on the hyperedge prediction task. We ran- domly split the hyperedge set into training and testing set by ratio of 4:1. The way to generate negative samples is the same 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 24.6% increase on the AUPR score. For network reconstruction and hyperedge prediction tasks, the difference between the ran- dom walk based Mlyper-SAGNe 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 classification experiment were carried out for the MovieLens dataset and the wordnet dataset, respectively. We used Logistic Regression the classifier. The proportion of the training
5

---

Published as a conference paper at ICLR 2020
MovieLens Micro
wordinet Micro F1
MovieLens F1
wardnet Macro F1
0.48
0.55
0.60
0.22
0.45
0.50
0.24
0.35
0.40
Mypen Sash-S
0.40
0.25
Hype-SAShh Bjyn)
Mepe-SAkkii whrrii
0.38
0.2
0.02
0.04
0.08
0.2
0.22
Figure 4: Performance 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)".
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-FI and Macro-FI to evaluate the performance. The results are in Fig. 4 We observed that Hyper-SAGNN consistently achieves both higher Micro-FI 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.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., non- hyperedges). 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 Fig. 4 shows the results for the node classification task.
Table 2: Performance evaluation based on AUROC and AUPR for hyperedge/edge prediction. Methods with annotation (mix) represent Hyper-SAGNN trained with mixture of edges and hyper-edges. Datasets marked with "(2)" represent the performance on pair-wise edge prediction (i.c., non-hyperedges).
GPS
MOVIELENS
DRUG
WORDNET
AUC
AUPR
AUC
AUPR
AUG
AUPR
AUC
AUPR
node2vec-
0.563
0.191
0.562
0.197
0.670
0.246
0.608
0.213
node2vec- min
0.570
0.185
0.539
0.186
0.684
0.258
0.575
0.200
DHNE
0.910
0.668
0.877
0.668
0.925
0.859
0.816
0.459
Hyper-SAGMe SAGNN-E
0.952
0.796
0.926
0.793
0.961
0.895
0.890
0.705
Hyper-SAGNI SAGNN-GNN-N
0.922
0.722
0.930
0.810
0.955
0.892
0.880
0.706
MypeN-SAGNN-EE (mix)
0.950
0.795
0.928
0.799
0.956
0.887
0.881
0.694
Hyper-SAGNN-W (mix)
0.920
0.720
0.929
0.811
0.950
0.889
0.884
0.684
GPS (2)
MOVIELENS (2)
DRUG (2)
WORDNET (2)
AUC
AUPR
AUC
AUPR
AUC
AUPR
AUC
AUPR
Hyper-SAGNN-E SAGNN-E (mix)
0.921
0.899
0.971
0.967
0.981
0.973
0.891
0.897
Hyper-SAGNN-W (mix)
0.931
0.910
0.999
0.999
0.999
0.999
0.923
0.916
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 1% fluctuation for AUC/AUPR).
We then further assessed the model in 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 appli- cations especially when the dataset is combined from different sources. For example, in the drug the (user, drug, reaction) hyperedges, there are also extra
dataset, it is possible that, in addition 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 train the model. The results are in Fig.
When using only the edges to train the model, our method still achieves higher AUROC and AUPR score for hyperedge prediction compared to node2vec (Table 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 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.

---

Published as a conference paper at ICLR 2020
AUROC MovieLens
AUROC wordnet
AUROC of drug
AUROC of GPS
0.90
0.75-
0.87-
0.85-
0.88
0.8--
0.90
0.84
AUPR of MovieLens
AUPR of wordnet
AUPR of drig
AUPR GPS
0.75
0.35-
0.65
0.80-
0.25-
0.55
Onty
20
30
Figure 5: AUROC and AUPR scores of Hyper-SAGNN for hyperedge prediction on the downsampled dataset over training epochs.
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 (#1, uy.... 0k) form a hyperedge. However, in many settings, might also want to know the reason why this group of nodes will not form hyperedge. We first define the outsider of a group of nodes as follows. Node i2 is the outsider of the node group (u1, 02,-., uk) if it satisfies:
Ee E E, (UI, U2 .... V4-1, Uit Uk) Ee Ee
(8)
de E E, s.t. Ej E {1,2..., # (v,, EE)
(9)
We speculated that Hyper-SAGNN can answer this question by analyzing the probability score P1 to pk (defined in Eqn. We assume that the node e; with the smallest p; would be the outsider. We then set the evaluation 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 probabil- ity. 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 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. $1.9% with the cost of slightly decreased hyperedge prediction perfor- mance (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; and the label of whether V; 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 (Ra- mani et al. 2017 Nagano et al. 2017). Genome-widd mapping of chromatin interactions by Hi- C (Lieberman-Ale Aidunn-Aidennnn 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 pro- vides 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 nod-orde,"d", 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
7

---

Published as a conference paper at ICLR 2020
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.
two datasets. The first one consists of scHi-C from four human cell lines: HAPI, 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 al.) 2017). We refer to the first dataset as "Ramani el al. data", and the second as "Nagano et al. data" for abbreviation. We trained HyPeN-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. (A-)..
We tested Hyper-SAGNN
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 ef- fectiveness of the embeddings with 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-FI and Macro-F1. We did not run K K-means clustering on the Nagano et al. data as represents 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/MDDS paper (Liu et al.) 2018) to evaluate the performance of the three methods the Nagano et al. data. We compared the per- formance with two recently developed computational methods based on dimensionality reduction of the contact matrix, HiC- ReppRRs (Liu et al. 2018) and scHiCluster (Zhou et al. 2019). Because Hyper-SAGNi is not deterministic method for generating embeddings for scHi-C, we repeated the training process 5 times and averaged the score. All these results are Fig. 6
A UMAP Ramani et Datusel
HeLLa HAP1
C
G1 mid-S late-S/22
UMAP Nagano al. Detaset
1.0
0.57
0.80
0.8
K362
0.8
0.4
0.2
Ramani al. Micro-F1
Ramani al.
Masro-F1 0:1 0.83
B PCA Ramani of al. Dataset
PCA Nagano Datasel
0.08
0.00
0.8
0:76
0.8
Hyper-SAGNN HiC-RepMMDS
sai KCkuster
0.
Nagano et al. AGROC
Figure 6: (A) and (B): Visualization of the learned embedding based Hyper- SAGNN for the Ramani al. data. (C) and (D): Visualization the learned embedding based on Hyper-SAGNN for the Nagano al. data. Embedding vectors are projected two dimensional space using either UMAP or PCA. (E): Quantitative evaluation of the Hyper-SAGNN on two scHl-CC datasets
For the Ramani et al. data (Fig. 6A-)), 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 organizagaaieeeee organization as compared to Hel.a Indeed, we observed that they are also closer to each other in the embedding space. Quantitative results in Fig. 6 are consistent with the visualization as our method achieves the highest ARI, Micro-Fl, Macro- Fl 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-SAGNI, which has great potential to provide insights into the cell-to-cell variation of higher-order genome organization.
8

---

Published as a conference paper at ICLR 2020
5 CONCLUSION
In this work, developed graph neural network called Hyper-SAGNN for the representation learning of general hypergraphs. The model has the flexibility to deal with homogeneous and het- erogeneous, and uniform and non-uniform hypergraphs. We demonstrated that Hyper-SAGNN can improve or match state-of-the-arr performance for hypergraph representation learning while address- ing the shortcomings prior methods such as the inability 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 the number of neighbors.
One potential improvement of Hyper-SAGNN as future work would be to allow information aggre- gation 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 node would still satisfy our constraint that it is fixed for known hypergraph with varying input tuples. This would allow us to incorporate previously developed methods on graphs, such GraphSAGE (Hamilton jet al. 2017a) and GCN (Kipf & Welling (0166.. as well as methods designed for hypergraphs like HyperGiCN (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.
ACKNOWLEDGMENT
J.M. acknowledges support from the National Institutes of Health Common Fund 4D Nucleome Program grant UJ5DDK10996, National Institutes of Health grant R01HG007352, and National Science Foundation grant 1717205. Y.Z.. (Yao Class, IIS, Tsinghua University) contributed this work as a visiting undergraduate student at Carnegie Mellon University during summer 2019.

---

Published as a conference paper at ICLR 2020
REFERENCES
Song Bai, Feihu Zhang, and Philip HS Torr. Hypergraph convolution and hypergraph attention. arXiv preprint N.ti:/990.001550 2019.
Inci M Baytas, Cao Xiao, Fei Wang, Anil K Jain, and Jiayu Zhou. Heterogeneous hyper-network embedding. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 875-880. IEEE, 2018.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26, pp. 2787-2795. Curran Associates, Inc., 2013.
Fuli Feng, Xiangnan He, Yiqun Liu, Liqiang Nie, and Tat-Seng Chua. Learning on partial-order hy- pergraphs. Proceedings of the 2018 World Wide Web Conference, pp. 1523-1532. International World Wide Web Conferences Steering Committee, 2018.
Yifan Feng, Haoxuan You, Zizhao Zhang. Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3558-3565, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge Discovery and Data Mining, pp. 855 864. ACM, 2016.
Huan Gui, Jialu Liu, Fangbo Tao, Meng Jiang, Brandon Norick, and Jiawei Han. Large-scale em- bedding learning in heterogeneous event data. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 907-912. IEEE, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs: Methods and applications. arXiv preprint arXiv:/709.0558. 2017b.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4): December 2015. ISSN 2160-6455.
Jie Huang, Chuan Chen, Fanghua Yc, Jiajing Wu, Zibin Zheng, and Guohui Ling. Hyper2vee: Biased random walk for hyper-network embedding. In International Conference on Database Systems for Advanced Applications, pp. 273-277. Springer, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 2016.
Erez Lieberman-Aiden Nynke L Van Berkum, Louise Williams, Maxim Imakaev, Tobias Ragoczy, Agnes Telling, Ido Amit, Bryan I Lajoie, Peter J Sabo, Michael O Dorschner, et al. Comprehen- sive mapping of long-range interactions reveals folding principles of the human genome. Science, 326(5550))289-293 2009.
Jie Liu, Dejun Lin, Galip Gürkan Yardmmıı, and William Stafford Noble. Unsupervised embedding of single-cell hi-c data. Bioinformatics, 34(13)=19--1104, 2018
Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 880200342, 2018.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient Estimation of Word Repre- sentations in Vector Space. arXiv e-prints, art. 1xX.v:1301.3781. Jan 2013.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionallity In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26. pp. 3111-11111 Curran Associates, Inc., 2013.
10

---

Published as a conference paper at ICLR 2020
Takashi Nagano, Yaniv Lubling, Csilla Vámai,, Carmel Dudley, Wing Leung, Yael Baran, Netta Mendelson Cohen, Steven Wingett, Peter Fraser, and Amos Tanay. Cell-cycle dynamics of chromosomal organization single-cell resolution. Nature, 547(7661)x61, 2017.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 701-710. ACM, 2014.
Vijay Ramani, Xinxian Deng, Ruolan Qiu, Kevin L. Gunderson, Frank J Steemers, Christine M Disteche, William S Noble, Zhijun Duan, and Jay Shendure. Massively multiplex single-cell hi-c. Nature Methods, 14(3):263, 2017.
Suhas SP Rao, Miriam H Huntley, Neva Durand, Elena K Stamenova, Ivan D Bochkov, James Robinson, Adrian L Sanborn, Ido Machol, Arina D Omer, Eric S Lander, et al. A 3d map of the human genome at kilobase resolution reveals principles of chromatin looping. Cell, 159(7): 1665-1680, 2014.
Liang Sun, Shuiwang Ji, and Jieping Ye. Hypergraph spectral learning for multi-label classification. In Proceedings of the 14th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining, pp. 668-676. ACM, 2008
Ke Tu, Peng Cui, Xiao Wang. Fei Wang, and Wenwu Zhu, Structural deep embedding for hyper- networks. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint vrXiv:/7100 10903, 2017.
Nagamand Yadati, Madhav Nimishakavi, Prateck Yadav, Anand Louis, and Partha Talukdar. Hy- pergen: Hypergraph convolutional networks for semi-supervised classification. arXiv preprint 1et::8809000.50 2018.
Chia-An Yu, Ching-Lun Tai, Tak-Shing Chan, and Yi-Hsuan Yang. Modeling multi-way relations with hypergraph embedding. In Proceedings of the 27th ACM International Conference on Infor- mation and Knowledge Management, pp. 1707-1710. 2018.
Vincent W. Zheng, Bin Cao, Yu Zheng, Xing Xie, and Qiang Yang. Collaborative filtering meets mobile recommendation: A user-centered approach. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI' 10, pp. 236 666-241.4 AAAI Press, 2010.
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing systems, pp. 1601- 1608, 2007.
Jingtian Zhou, Jianzhu Ma, Yusi Chen, Chuankai Cheng, Bokan Bao, Jian Peng, Terrence J Se- jnowski, Jesse R Dixon, and Joseph Ecker. Robust single-cell hi-e clustering by convolution- and random-walk-baase imputation. Proceedings of the National Academy of Sciences, pp. 201901423, 2019.

---

Published as a conference paper at ICLR 2020
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 with weight w(e) is incident with a vertex if and only if v E e. We denote the indicator function that represents the incident relationship between v and by hu e), which equals when is incident with v. The degree of vertex and the size of hyperedge are defined as:
d(r) -
Σ B
h(w e)w(e)
(10)
(())
h(u, e) le]
(11)
NEV
A.1.1 ENCODER BASED APPROACH
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 the structure used in DHNE eTu al.; 2018). We first obtain the if
incident matrix of the hypergraph H R with entries h(c, We also calculate the diagonal degree matrix Dy containing the vertex degree d((v) = EeEg h(v, e)- We thus have the adjacency matrix A = HHT D.. of which the entries a(v,, my) denote the concurrent times between each pair of nodes (V,, v2). The i-th row of A, denoted by d; shows the neighborhood structures of the node U/, which then passes through one-layer neural network to produce म..
and 0 otherwise.
= (Wenc + benc)
(12)
In DHNE, symmetric structure was introduced where there are corresponding decoders to trans- form the e back to d; TTu 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 fied-weight between encoder and decoder 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 Z (shown the left side of Fig. We extend the biased 2nd-order random walks proposed in node2vec (Grover & Leskovec 2016) to generalize to hypergraphs. For a walk from then to f, the strategies described follows.
The Ist-order random walk strategy given the current vertex x is to randomly select a hyperedge incident with x based on the weight of and then choose the next vertex y from uniformly (Zhou et al. 2007). Therefore, the 1st-order transition probability is defined as:
h(t, e)h(z, e)
क (t|x) A
Σ w(e)
(13)
8(e)
cEE
We then generalize the 2nd-order bias Qpp from ordinary graph hypergraph for walk from v to to / as:
1/p.
ap.a (p.a(1, (1, v)
1. else if Be E, s.t. E E
(14)
1/g.
otherwise
where the parameters p and g 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:
(t(ar) (to(ter) if 3e E E, s.t. U, E otherwise
(t u, 2²
2
(15)
0,
where Z is normalizing factor.

---

Published as a conference paper at ICLR 2020
With the well-defined 2nd-order transition probability ((t]u, 2)), we simulate random walk of fixed
length through 2nd-order Markov process marked by P(c, = - = 2, C2-2 = v) = π (f] t,, x), where c; is the i-th node in the walk. A Siip-rram model (Mikolov 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 FAERS 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
Datasets used in this work. Note that the columns under "#(V)" correspond the columns under "node type" for each dataset.
Table A1:
DATASETS
NODE TYPE
a(E)
GPS
user
location
activity
146
70
5
1,436
MovieLens
user
movie
tag
2,113
5,908
9.079
47,967
drug
user
drug
reaction
12
1,076
6,398
171,756
wordnet
head
relation
tail
40,504
18
40,551
145,966
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.) (218)). We tuned parameters such as the a 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 was able to replicate or even improve the perfor- mance reported in the original paper. To make 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 de- composed graph. For the hyperedge prediction task, we first used the learned embedding to predict pairwise edges. We then used the mean min of the pairwise similarity 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 10, which the same parameters used in DHNE for node2vec. However, we found that for the baseline method node2vec, when we tuned the hyper-parameter p. 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 longer time for sampling the walks and training the skip -raa-grmm 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 the multi-head attention layer set to 8. When using the encoder based approach to calculate 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 z,, The results in Section 4.1 showed that even when the
hhtp://wwwwflaaggw//Dmmgs
2

---

Published as a conference paper at ICLR 2020
pre-trained embeddings are not ideal, Hyper-SAGNN can still well capture the structure of the graph.
To train the model, used the Adam optimizer with learning rate 1c-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 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 metries.
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, dict 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 be 5 times the amount of the positive samples following the same setup of DHNE.
the other hand, aims to pre-
For the node classification, after training the model, the embeddings for the nodes are used train a Logistic Regression classifier with targets as the pre-defined labels for the nodes. Here we have a multi-label classification and multi-class classification task for dataset MovieLens and wordnet, respectively, making the metrics defined for binary classification not applicable. Therefore, the per- formances are evaluated by Micro and Macro F1 scores that are used for quantifying the performance of multi-lahel/multi--hhe classification.
A.S 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 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, ..., k) should approximate the static embedding of node better. In contrast, the dynamic embedding of node when it is a member of a non-hyperedge tuple would not have a good "approximation". To evaluate this, after training the model 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. Al in general, the positive dynamic embeddings can achieve much better performance as compared to the negative dynamic embeddings. Both the micro and macro Fl 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 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 ai term in the calculation of dynamic embeddings, which makes the dynamic embedding for node i the combination of features of its neighbor within 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.
3

---

Published as a conference paper at ICLR 2020
MovieLans Micro F1
wordhet Micro F1
MovieLans Macro F1
wordnet Macro F1
0.45
0.30
0.00
Embedding type
Kleic
Uysammi
0.55
0.40
0.30
dynamio
dynamte
dynamio
dyremic N
0.26
Uyremmic N
Oynamic N-
0.
0.4
66
0.8
0.02
0.04
0.06
0:08
0.2 0.4
0.6
0.8
0.02
0.04
0.05
0.08
Fraction of training data
Figure A1: Node classification performance comparison for static embeddings and dynamic emheddings. The results based on static embeddings marked as "static". Results based on positive/negative dynamic embeddings 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-SAGNT VS. THE VARIANTS
As mentioned above, unlike the standard GAT model, we exclude the og term in the self-attention mechanism. To test whether this constraint would improve reduce the model's ability learn, we implemented a variant of our model (referred to as variant type 1) by including this term. Also, as mentioned in the Method section, another potential variant of our model would be directly using the d; to calculate the probability score p. We refer to this variant as variant type II. For variant type II, on node classification task, since it does not have static embedding, we used W 2g. 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 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 the node classification task the MovieLens and the wordnet dataset. For the MovieLens dataset, we used 90% nodes as training data while for wordnet, used 1% of the nodes training data. All the evaluation setup is the same 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- is the best in terms of all metrics for the GPS, Movielens, and wordnet dataastt. 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 metrics for the GPS and the drug dataset. For the Movie- Lens and wordnet dataset, Hyper-SAGNN performs similar to variant type higher than variant type II on the network reconstruction and link prediction task. However, our model achieves slightly higher accuracy the node classification task than variant type Therefore, these evaluations show that the choice of the structure Hyper- can achieve higher at least comparable performance than the two potential variants over multiple tasks multiple datasets.
4

---

Published as a conference paper at ICLR 2020
Network Reconsiruction AUROC
Network Reconstruction AUPR
Link Predictionn AUROC
10-
0.-
Link Prodiction AUPR
Node Classification F1-micro
Node Classification F1-macro
0.64-
3.5-
0.40
0.00
Nyper-SAGM Variant Type
00.44
4.04
40
20
48
Figure A2: Performance comparison of Hyper-SAGNN Walk and Variant Type I, II (GPS)
Network Reconstruction AUROC
Network Reconstruction AUPR
Link Predictioon AUROC
1.00
0.84
3.55
3.64
8.75
Link Prediction AUPR
Node Classification F1 F1-micro
Node Classification F1-macro
0.32
6.78
0.29
8.74-
0:27
Figure A3: Performance comparison of Hyper-SAGNe SAGNN Walk Variant Type (MovieLens)
Network Reconstruction AUROC
Network Reconstruction AUPR
Link Prediction AUROC
0.34
0.564
1.00
6.84-
0.54
Prediction AUPR
Node Classification F1-micro
Node Classification
0.55
-3.54
0.04
Figure A4: Performance comparison of Elyper-SAGNI Walk and Variant Type I, Il (drug)
5

---

Published as a conference paper at ICLR 2020
Network Reconsinuction AUROC
Network Reconstruction AUPR
Link Prediction AUROC
1,88
0.86
0.64-
0.00-
Link Prediction AUPR
Node Classification F1-micro
Node Claseification
F1 -mmcrr
0.70
0.50-
0.34
0.30
10
10
16
10
16
Figure A5: Performance comparison of Hyper-SAGNN Walk and Variant Type I, II (wordnet)
Network Reconstruction AUROC
Network Reconstruction AUPR
Prediction AUROC
0.07
0.56
0.22
0.52
Prediction AUPR
Node Classification F1-micro
Classification F1-macro
0.04-
0.04
0.50
0.75
6.00
0.00
Hyper&AGWN
0.70
Vertett Type
Varant Type
Figure A6: Performance comparison of Hyper-SAGNN Encoder and Variant Type Il (GPS)
Network Reconstruction AUROC
Network Reconstruction AUPR
Link Prediction AUROC
0.55
0.88
0.1-
Link Prediction AUPR
Node Classification F1-micro
Node Classification
0.79
9.46
0.42
Figure A7: Performance comparison of Hyper- -Ayper-SAGNNN- Encoder and Variant Type II (MovieLens)

---

Published as a conference paper at ICLR 2020
Network Reconstruction AUROC
Network Reconstruction AUPR
Link Prediction AUROC
1.00
0.54
0.22
8.30
Link Prediction AUPR
Node Classification F1-micro
Node Classification F1-macro
0.52
0.4-
0.64
0.00
0.60-
Figure A8: Performance comparison of Hyper-SAGNN Encoder and Variant Type II (drug)
Network Reconstruction AUROC
Network Reconstruction AUPR
Link Prediction AUROC
0.22
1.00
0.20
D.E.-
Link Prediction AUPR
Classification F1-micro
Classification F1 F1-macro
0.72
6.4-
0.24-
0.20
Figure A9; Performance comparison of Hyper-SAGNN Encoder and Variant Type Il (wordnet)
7


Reviews:
[{"review_id": "SkgvBi60YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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.\n\nA 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.\n\nSome other notes:\nEq 5.  Given that it is the default, explicitly write that the summation is over j!=i\nEq 8.  Probably leave the ellipses out between v_{i-1} and v_{i+1}?\nThe tasks and measures like AUC, AUPR, and network reconstruction could be described somewhere, even if in an appendix.\nSome/many training hyperparameters not listed?\n\n\nEDIT: 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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlYRqICtH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis work is tackling the problem of predicting variable-sized heterogeneous hyperedges in hypergraphs. The authors do so by introducing a multi-head attention mechanism that takes in a set of node features and predicts the probability of this set of nodes forming a hyperedge.\n\n- Quality and clarity: \n\nThe quality of the paper is good, the writing is clear and the reasoning is relatively easy to follow. The problem the authors are trying to tackle is also clearly defined. The motivation of the dynamic and static embedding choice could be explained better. The intuition that the pseudo-distance tells us how well the static embedding\nof a node can be approximated by the features of the neighbour within the tuple somewhat makes sense, but I also have the impression that this is just one possible interpretation and what happens in practice could actually be quite different. A more formal treatment and analysis of this intuition would be very helpful.\n\n- Originality: \nThe main contribution here is to propose a more flexible formulation to improve over the fixed MLP used by DHNE. This in itself is a good idea, but overall is an incremental improvement.\n\n- Significance: \nThe results are convincing, DHNE is clearly outperformed on the benchmarks. Depending on the ease of training the model compared to DHNE, this work might be a useful contribution for the ICLR community.\n\nOther points\n\nThe related work section should be expanded by discussing relationships to:\n\nBai, Song, Feihu Zhang, and Philip HS Torr. \"Hypergraph Convolution and Hypergraph Attention.\" arXiv preprint arXiv:1901.08150 (2019).\n\nFeng, Yifan, et al. \"Hypergraph neural networks.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 2019.\n\n------------------\nPost-rebuttal\n------------------\n\nI would like to thank the authors for their in-depth response. I found the additional analysis on the dynamic node embeddings insightful and it is reassuring that it confirms the claims. Overall I think the rebuttal addresses my major concerns and I will raise my score.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work introduces a new neural network model that can represent hyperedges of variable size, which is experimentally shown to improve or match the state of the art on several problems. 

Both reviewers were in favor of acceptance given the method's strong performance, and had their concerns resolved by the rebuttals and the discussion. I am therefore recommending acceptance. 
Decision: Accept (Poster)