Year: 2020

Abstract:
Graphs are the most ubiquitous form of structured data representation used in machine learning. They model, however, only pairwise relations between nodes and are not designed for encoding the higher-order relations found in many real-world datasets. To model such complex relations, hypergraphs have proven to be a natural representation. Learning the node representations in a hypergraph is more complex than in a graph as it involves information propagation at two levels: within every hyperedge and across the hyperedges. Most current approaches first transform a hypergraph structure to a graph for use in existing geometric deep learning algorithms. This transformation leads to information loss, and sub-optimal exploitation of the hypergraph’s expressive power. We present HyperSAGE, a novel hypergraph learning framework that uses a two-level neural message passing strategy to accurately and efficiently propagate information through hypergraphs. The flexible design of HyperSAGE facilitates different ways of aggregating neighborhood information. Unlike the majority of related work which is transductive, our approach, inspired by the popular GraphSAGE method, is inductive. Thus, it can also be used on previously unseen nodes, facilitating deployment in problems such as evolving or partially observed hypergraphs. Through extensive experimentation, we show that HyperSAGE outperforms state-of-the-art hypergraph learning methods on representative benchmark datasets. We also demonstrate that the higher expressive power of HyperSAGE makes it more stable in learning node representations as compared to the alternatives.

heading: 1 INTRODUCTION
text: Graphs are considered the most prevalent structures for discovering useful information within a network, especially because of their capability to combine object-level information with the underlying inter-object relations (Wu et al., 2020). However, most structures encountered in practical applications form groups and relations that cannot be properly represented using pairwise connections alone, hence a graph may fail to capture the collective flow of information across objects. In addition, the underlying data structure might be evolving and only partially observed. Such dynamic higher-order relations occur in various domains, such as social networks (Tan et al., 2011), computational chemistry (Gu et al., 2020), neuroscience (Gu et al., 2017) and visual arts (Arya et al., 2019), among others. These relations can be readily represented with hypergraphs, where an edge can connect an arbitrary number of vertices as opposed to just two vertices in graphs. Hypergraphs thus provide a more flexible and natural framework to represent such multi-way relations (Wolf et al., 2016), however, this requires a representation learning technique that exploits the full expressive power of hypergraphs and can generalize on unseen nodes from a partially observed hypergraph.
Recent work in the field of geometric deep learning have presented formulations on graph structured data for the tasks of node classification (Kipf & Welling, 2016), link prediction (Zhang & Chen, 2018), or the classification of graphs (Zhang et al., 2018b). Subsequently, for data containing higher-order relations, a few recent papers have presented hypergraph-based learning approaches on similar tasks (Yadati et al., 2019; Feng et al., 2019). A common implicit premise in these papers is that a hypergraph can be viewed as a specific type of regular graph. Therefore, reduction of hypergraph learning problem to that of a graph should suffice. Strategies to reduce a hypergraph to a graph include transforming the hyperedges into multiple edges using clique expansion (Feng et al., 2019; Jiang et al., 2019; Zhang et al., 2018a), converting to a heterogeneous graph using star
expansion (Agarwal et al., 2006), and replacing every hyperedge with an edge created using a certain predefined metric (Yadati et al., 2019). Yet these methods are based on the wrong premise, motivated chiefly by a larger availability of graph-based approaches. By reducing a hypergraph to regular graph, these approaches make existing graph learning algorithms applicable to hypergraphs. However, hypergraphs are not a special case of regular graphs. The opposite is true, regular graphs are simply a specific type of hypergraph (Berge & Minieka, 1976). Therefore, reducing the hypergraph problem to that of a graph cannot fully utilize the information available in hypergraph. Two schematic examples outlining this issue are shown in Fig.1. To address tasks based on complex structured data, a hypergraph-based formulation is needed that complies with the properties of a hypergraph.
A major limitation of the existing hypergraph learning frameworks is their inherently transductive nature. This implies that these methods can only predict characteristics of nodes that were present in the hypergraph at training time, and fail to infer on previously unseen nodes. The transductive nature of existing hypegraph approaches makes them inapplicable in, for example, finding the most promising target audience for a marketing campaign or making movie recommendations with new movies appearing all the time. An inductive solution would pave the way to solve such problems using hypergraphs. The inductive learning framework must be able to identify both the node’s local role in the hypergraph, as well as its global position (Hamilton et al., 2017). This is important for generalizing the learned node embeddings that the algorithm has optimized on to a newly observed hypergraph comprising previously unseen nodes, thus, making inductive learning a far more complex problem compared to the transductive learning methods.
In this paper, we address the above mentioned limitations of the existing hypergraph learning methods. We propose a simple yet effective inductive learning framework for hypergraphs that is readily applicable to graphs as well. Our approach relies on neural message passing techniques due to which it can be used on hypergraphs of any degree of cardinality without the need for reduction to graphs. The points below highlight the contributions of this paper:
• We address the challenging problem of representation learning on hypergraphs by proposing HyperSAGE, comprising a message passing scheme which is capable of jointly capturing the intra-relations (within a hyperedge) as well as inter-relations (across hyperedges).
• The proposed hypergraph learning framework is inductive, i.e. it can perform predictions on previously unseen nodes, and can thus be used to model evolving hypergraphs.
• HyperSAGE facilitates neighborhood sampling and provides the flexibility in choosing different ways to aggregate information from the neighborhood.
• HyperSAGE is more stable than state-of-the-art methods, thus provides more accurate results on node classification tasks on hypergraphs with reduced variance in the output.

heading: 2 RELATED WORK
text: Learning node representations using graph neural networks has been a popular research topic in the field of geometric deep learning (Bronstein et al., 2017). Graph neural networks can be broadly classified into spatial (message passing) and spectral networks. We focus on a family of spatial message passing graph neural networks that take a graph with some labeled nodes as input and learn embeddings for each node by aggregating information from its neighbors (Xu et al., 2019). Message passing operations in a graph simply propagate information along the edge connecting two nodes. Many variants of such message passing neural networks have been proposed, with some popular ones including Gori et al. (2005); Li et al. (2015); Kipf & Welling (2016); Gilmer et al. (2017); Hamilton et al. (2017).
Zhou et al. (2007) introduced learning on hypergraphs to model high-order relations for semisupervised classification and clustering of nodes. Emulating a graph-based message passing framework for hypergraphs is not straightforward since a hyperedge involves more than two nodes which makes the interactions inside each hyperedge more complex. Representing a hypergraph with a matrix makes it rigid in describing the structures of higher order relations (Li et al., 2013). On the other hand, formulating message passing on a higher dimensional representation of hypergraph using tensors makes it computationally expensive and restricts it to only small datasets (Zhang et al., 2019). Several tensor based methods do perform learning on hypergraphs (Shashua et al., 2006; Arya et al., 2019), however they are limited to uniform hypergraphs only.
To resolve the above issues, Feng et al. (2019) and Bai et al. (2020) reduce a hypergraph to graph using clique expansion and perform graph convolutions on them. These approaches cannot utilize complete structural information in the hypergraph and lead to unreliable learning performance for e.g. classification, clustering and active learning (Li & Milenkovic, 2017; Chien et al., 2019). Another approach by Yadati et al. (2019), named HyperGCN, replaces a hyperedge with pair-wise weighted edges between vertices (called mediators). With the use of mediators, HyperGCN can be interpreted as an improved approach of clique expansion, and to the best of our knowledge, is also the state-of-the-art method for hypergraph representation learning. However, for many cases such as Fano plane where each hyperedge contains at most three nodes, HyperGCN becomes equivalent to the clique expansion (Dong et al., 2020). In spectral theory of hypergraphs, methods have been proposed that fully exploit the hypergraph structure using non-linear Laplacian operators (Chan et al., 2018; Hein et al., 2013). In this work, we focus on message passing frameworks. Drawing inspiration from GraphSAGE (Hamilton et al., 2017), we propose to eliminate matrix (or tensor) based formulations in our neural message passing frameworks, which not only facilitates utilization of all the available information in a hypergraph, but also makes the entire framework inductive in nature.

heading: 3 PROPOSED MODEL: HYPERSAGE
text: The core concept behind our approach is to aggregate feature information from the neighborhood of a node spanning across multiple hyperedges, where the edges can have varying cardinality. Below, we first define some preliminary terms, and then describe our generic aggregation framework. This framework performs message passing at two-levels for a hypergraph. Further, for any graphstructured data, our framework emulates the one-level aggregation similar to GraphSAGE (Hamilton et al., 2017). Our approach inherently allows inductive learning, which makes it also applicable on hypergraphs with unseen nodes.

heading: 3.1 PRELIMINARIES
text: Definition 1 (Hypergraph). A general hypergraph H can be represented as H = (V,E,X), where V = {v1, v2, ..., vN} denotes a set of N nodes (vertices) and E = {e1, e2, ..., eK} denotes a set of hyperedges, with each hyperedge comprising a non-empty subset from V. X ∈ RN×d denote the feature matrix, such that xi ∈ X is the feature vector characterizing node vi ∈ V. The maximum cardinality of the hyperedges in H is denoted as M = max
e∈E |e|.
Unlike in a graph, the hyperedges of H can contain different number of nodes and M denotes the largest number. From the definition above, we see that graphs are a special case of hypergraphs with
M=2. Thus, compared to graphs, hypergraphs are designed to model higher-order relations between nodes. Further, we define three types of neighborhoods in a hypergraph:
Definition 2 (Intra-edge neighborhood). The intra-edge neighborhood of a node vi ∈ V for any hyperedge e ∈ E is defined as the set of nodes vj belonging to e and is denoted by N(vi, e) Further, let E(vi) = {e ∈ E | vi ∈ e} be the sets of hyperedges that contain node vi. Definition 3 (Inter-edge neighborhood). The inter-edge neighborhood of a node vi ∈ V also referred as its global neighborhood, is defined as the neighborhood of vi spanning across the set of hyperedges E(vi) and is represented by N(vi) = ⋃ e∈E(vi) N(vi, e).
Definition 4 (Condensed neighborhood). The condensed neighborhood of any node vi ∈ V is a sampled set of α ≤ |e| nodes from a hyperedge e ∈ E(vi) denoted by N(vi, e;α) ⊂ N(vi, e).

heading: 3.2 GENERALIZED MESSAGE PASSING FRAMEWORK
text: We propose to interpret the propagation of information in a given hypergraph as a two-level aggregation problem, where the neighborhood of any node is divided into intra-edge neighbors and inter-edge neighbors. For message aggregation, we define aggregation function F(·) as a permutation invariant set function on a hypergraph H = (V,E,X) that takes as input a countable unordered message set and outputs a reduced or aggregated message. Further, for two-level aggregation, let F1(·) and F2(·) denote the intra-edge and inter-edge aggregation functions, respectively. Schematic representation of the two aggregation functions is provided in Fig.2. Similar to X we also define Z as the encoded feature matrix built using the outputs zi of aggregation functions. Message passing at node vi for aggregation of information at the lth layer can then be stated as
x (e) i,l ← F1 ({xj,l−1 | vj ∈ N(vi, e;α)}), (1)
xi,l ← xi,l−1 + F2 ({x(e)i,l |vi ∈ E(vi)}), (2)
where, x(e)i,l refers to the aggregated feature set at vi obtained with intra-edge aggregation for edge e.
The combined two-level message passing is achieved using nested aggregation function F = F2. To ensure that the expressive power of a hypergraph is preserved or at least the loss is minimized, the choice of aggregation function should comply with certain properties.
Firstly, the aggregation function should be able to capture the features of neighborhood vertices in a manner that is invariant to the permutation of the nodes and hyperedges. Many graph representation learning methods use permutation invariant aggregation functions, such as mean, sum and max functions (Xu et al., 2019). These aggregations have proven to be successful for node classification problems. For the existing hypergraph frameworks, reduction to simple graphs along with a matrix-based message passing framework limits the possibilities of using different types of feature aggregation functions, and hence curtails the potential to explore unique node representations.
Secondly, the aggregation function should also preserve the global neighborhood invariance at the ‘dominant nodes’ of the graph. Here, dominant nodes refer to nodes that contain important features, thereby, impacting the learning process relatively more than their neighbors. The aggregation function should ideally be insensitive to the input, whether the provided hypergraph contains a few large
hyperedges, or a larger number of smaller ones obtained from splitting them. Generally, a hyperedge would be split in a manner that the dominant nodes are shared across the resulting hyperedges. In such cases, global neighborhood invariance would imply that the aggregated output at these nodes before and after the splitting of any associated hyperedge stays the same. Otherwise, the learned representation of a node will change significantly with each hyperedge split.
Based on these considerations, we define the following properties for a generic message aggregation function that should hold for accurate propagation of information through the hypergraphs.
Property 1 (Hypergraph Isomorphic Equivariance). A message aggregation function F(·) is equivariant to hypergraph isomorphism, if for two isomorphic hypergraphs H = (V,E,X) and H∗ = (V∗,E∗,X∗), given that H∗ = σ •H, and Z and Z∗ represent the encoded feature matrices obtained using F(·) on H and H∗, the condition Z∗ = σ • Z holds. Here, σ denotes a permutation operator on hypergraphs.
Property 2 (Global Neighborhood Invariance). A message aggregation scheme F(·) satisfies global neighborhood invariance at any node vi ∈ V for a given hypergraph H = (V,E,X) if for any operation Γ(·), such that H∗ = Γ(H), and zi and z∗i denote the encoded feature vectors obtained using F(·) at node vi on H and H∗, the condition z∗i = zi holds. Here Γ(H) could refer to operations such as hyperedge contraction or expansion.
The flexibility of our message passing framework allows us to go beyond the simple aggregation functions on hypergraphs without violating Property 1. We introduce a series of power mean functions as aggregators, which have recently been shown to generalize well on graphs (Li et al., 2020). We perform message aggregation in hypergraphs using these generalized means, denoted byMp and provide in section 4.2, a study on their performances. We also show that with appropriate combinations of the intra-edge and inter-edge aggregations Property 2 is also satisfied. This property ensures that the representation of a node after message passing is invariant to the cardinality of the hyperedge, i.e., the aggregation scheme should not be sensitive to hyperedge contraction or expansion, as long as the global neighborhood of a node remains the same in the hypergraph.
Aggregation Functions. One major advantage of our strategy is that the message passing module is decoupled from the choice of the aggregation itself. This allows our approach to be used with a broad set of aggregation functions. We discuss below a few such possible choices.
Generalized means. Also referred to as power means, this class of functions are very commonly used for getting an aggregated measure over a given set of samples. Mathematically, generalized
means can be expressed as Mp = ( 1 n ∑n i=1 x p i ) 1 p , where n refers to the number of samples in the aggregation, and p denotes its power. The choice of p allows providing different interpretations to the aggregation function. For example, p = 1 denotes arithmetic mean aggregation, p = 2 refers to mean squared estimate and a large value of p corresponds to max pooling from the group. Similarly, Mp can be used for geometric and harmonic means with p→ 0 and p = −1, respectively. Similar to the recent work of Li et al. (2020), we use generalized means for intra-edge as well as inter-edge aggregation. The two functions F1(·) and F2(·) for aggregation at node vi is defined as
F (i) 1 (s) =  1|N(vi, e)||N(vi)| ∑ vj∈N(vi,e) |E(vi)|∑ m=1
1
|N(vi, em)|
−1 xpj  1 p
(3)
F (i) 2 (s) =  1 |E(vi)| ∑ e∈E(vi) (F1(s)) p  1p (4) where we use ‘s’ for concise representation of the unordered set of input as shown in Eq.1. Here and henceforth in this paper, we remove the superscript index ‘(i)’ for the sake of clarity and further occurrences of the two aggregation functions shall be interpreted in terms of node vi. Note that in Eq. 3 and Eq. 4, we have chosen the power term p to be same for F1 and F2 so as to satisfy the global neighborhood invariance as stated in Property 2. Note, the scaling term added to F1 is added to balance the bias in the weighting introduced in intra-edge aggregation due to varying
cardinality across the hyperedges. These restrictions ensure that the joint aggregation F2(·) satisfies the property of global neighborhood invariance at all times. Proof of the two aggregations satisfying Property 2 is stated in Appendix B.
Sampling-based Aggregation. Our neural message passing scheme provides the flexibility to adapt the message aggregation module to fit the desired computational budget through aggregating information from only a subset N(vi, e;α) of the full neighborhood N(vi, e), if needed. We propose to apply sub-sampling only on the nodes from the training set, and use information from the full neighborhood for the test set. The advantages of this are twofold. First, reduced number of samples per aggregation at training time reduces the relative computational burden. Second, similar to dropout (Srivastava et al., 2014), it serves to add regularization to the optimization process. Using the full neighborhood on test data avoids randomness in the test predictions, and generates consistent output.

heading: 3.3 INDUCTIVE LEARNING ON HYPERGRAPHS
text: HyperSAGE is a general framework for learning node representations on hypergraphs, on even unseen nodes. Our approach uses a neural network comprising L layers, and feature-aggregation is performed at each of these layers, as well as across the hyperedges.
Algorithm 1 HyperSAGE Message Passing Input : H = (V,E,X); depth L; weight matri-
ces Wl for l = 1 . . . L; non-linearity σ; intra-edge aggregation function F1(·); inter-edge aggregation function F2(·)
Output: Node embeddings zi| vi ∈ V h0i ← xi ∈ X | vi ∈ V for l = 1 . . . L do
for e ∈ E do hli ← h l−1 i
for vi ∈ e do hli ← hli + F (i) 2 (s)
end end hli ← σ(Wl(hli/||hli||2)) | vi ∈ V
end zi ← hLi | vi ∈ V
Algorithm 1 describes the forward propagation mechanism which implements the aggregation function F(·) = F2(·) described above. At each iteration, nodes first aggregate information from their neighbors within a specific hyperedge. This is repeated over all the hyperedges across all the L layers of the network. The trainable weight matrices Wl with l ∈ L are used to aggregate information across the feature dimension and propagate it through the various layers of the hypergraph.
Generalizability of HyperSAGE. HyperSAGE can be interpreted as a generalized formulation that unifies various existing graphbased as well as hypergraph formulations. Our approach unifies them, identifying each of these as special variants/cases of our method. We discuss here briefly the two popular algorithms.
Graph Convolution Networks (GCN). The GCN approach proposed by Kipf & Welling (2016) is a graph-based method that can be derived as a special case of HyperSAGE with maximum cardinality |M | = 2, and setting the agggregation function F2 = Mp with p = 1. This being a graph-based method, F1 will not be used.
GraphSAGE. Our approach, when reduced for graphs using |M | = 2, is similar to GraphSAGE. For exact match, the aggregation function F2 should be one of mean, max or LSTM . Further, the sampling term α can be adjusted to match the number of samples per aggregation as in GraphSAGE.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETUP
text: For the experiments in this paper, we use co-citation and co-authorship network datasets: CiteSeer, PubMed, Cora (Sen et al., 2008) and DBLP (Rossi & Ahmed, 2015). The task for each dataset is to predict the topic to which a document belongs (multi-class classification). For these datasets, xi corresponds to a bag of words such that xi,j ∈ xi represents the normalized frequency of occurence of the jth word. Additional details related to the hypergraph topology are presented in Appendix
A.2. Further, for all experiments, we use a neural network with 2 layers. All models are implemented in Pytorch and trained using Adam optimizer. See Appendix A.2 for implementation details.

heading: 4.2 SEMI-SUPERVISED NODE CLASSIFICATION ON HYPERGRAPHS
text: Performance comparison with existing methods. We implemented HyperSAGE for the task of semi-supervised classification of nodes on a hypergraph, and the results are compared with stateof-the art methods. These include (a) Multi-layer perceptron with explicit hypergraph Laplacian regularisation (MLP + HLR), (b) Hypergraph Neural Networks (HGNN) (Feng et al., 2019) which uses a clique expansion, and (c) HyperGCN and its variants (Yadati et al., 2019) that collapse the hyperedges using mediators. For HyperSAGE method, we use 4 variants of generalized means Mp with p = 1, 2,−1 and 0.01 with complete neighborhood i.e., α = |e|. For all the cases, 10 data splits over 8 random weight initializations are used, totalling 80 experiments per method and for every dataset. The data splits are the same as in HyperGCN described in Appendix A.1.
Table 1 shows the results obtained for the node classification task. We see that the different variants of HyperSAGE consistently show better scores across our benchmark datasets, except Cora cocitation where no improvement is observed compared to HGNN. Cora co-citation data is relatively small in size with a cardinality of 3.0± 1.1, and we speculate that there does not exist enough scope of improving with HyperSAGE beyond what HGNN can express with the clique expansion.
For the larger datasets such as DBLP and Pubmed, we see that the improvements obtained in performance with HyperSAGE over the best baselines are 6.3% and 4.3% respectively. Apart from its superior performance, HyperSAGE is also stable, and is less sensitive to the choice of data split and initialization of the weights. This is evident from the scores of standard deviation (SD) for the various experiments in Table 1. We see that the SD scores for our method are lower than other methods, and there is a significant gain in performance compared to HyperGCN. Another observation is that the HyperGCN method is very sensitive to the data splits as well as initializations with very large errors in the predictions. This is even higher for the FastHyperGCN variant. Also, we have found that all the 4 choices of p work well with HyperSAGE for these datasets. We further perform a more comprehensive study analyzing the effect of p on model performance later in this section.
Stability analysis. We further study the stability of our method in terms of the variance observed in performance for different ratios of train and test splits, and compare results with that of HyperGCN implemented under similar settings. Fig. 3 shows results for the two learning methods on 5 different train-test ratios. We see that the performance of both models improves when a higher fraction of data is used for training, and the performances are approx-
imately the same at the train-test ratio of 1/3. However, for smaller ratios, we see that HyperSAGE outperforms HyperGCN by a significant margin across all datasets. Further, the standard deviation for the predictions of HyperSAGE are significantly lower than that of HyperGCN. Clearly, this implies that HyperSAGE is able to better exploit the information contained in the hypergraph compared to HyperGCN, and can thus produce more accurate and stable predictions. Results on Cora and Citeseer can be found in Appendix C.
Effect of generalized mean aggregations and neighborhood sampling. We study here the effect of different choices of the aggregation functions F1(·) and F2(·) on the performance of the model. Further, we also analyze how the number of samples chosen for aggregation affect its performance. Aggregation functions from Mp are chosen with p = 1, 2, 3, 4, 5, 0.01 and −1, and to comply with global neighborhood invariance, we use aggregation function as in Eq. 4. The number of neighbors α for intra-edge aggregation are chosen to be 2, 3, 5 and 10. Table 2 shows the accuracy scores obtained for different choices of p and α on DBLP and Pubmed datasets. For most cases, higher value of p reduces the performance of the model. For α = 2 on DBLP, performance seems to be independent of the choice of p. A possible explanation could be that the number of neighbors is very small, and change in p does not affect the propagation of information significantly. An exception is p = −1, where the performance drops for all cases. For Pubmed, the choice of p seems to be very important, and we find that p = 0.01 seems to fit best.
We also see that the number of samples per aggregation can significantly affect the performance of the model. For DBLP, model performance increases with increasing value of α. However, for Pubmed, we observe that performance improves up to α = 5, but then a slight drop is observed for larger sets of neighbors. Note that for Pubmed, the majority of the hyperedges have cardinality less than or equal to 10. This means that during aggregation, information will most often be aggregated from all the neighbors, thereby involving almost no stochastic sampling. Stochastic sampling of nodes could serve as a regularization mechanism and reduce the impact of noisy hyperedges. However, at α = 10, it is almost absent, due to which the noise in the data affects the performance of the model which is not the case in DBLP.

heading: 4.3 INDUCTIVE LEARNING ON EVOLVING GRAPHS
text: For inductive learning experiment, we consider the case of evolving hypergraphs. We create 4 inductive learning datasets from DBLP, Pubmed, Citeseer and Core (co-citation) by splitting each
of the datasets into a train-test ratio of 1:4. Further, the test data is split into two halves: seen and unseen. The seen test set comprises nodes that are part of the hypergraph used for representation learning. Further, unseen nodes refer to those that are never a part of the hypergraph during training. To study how well HyperSAGE generalizes for inductive learning, we classify the unseen nodes and compare the performance with the scores obtained on the seen nodes. Further, we also compare our results on unseen nodes with those of MLP+HLR. The results are shown in Table 3. We see that results obtained with HyperSAGE on unseen nodes are significantly better than the baseline method. Further, these results seem to not differ drastically from those obtained on the seen nodes, thereby confirming that HyperSAGE can work with evolving graphs as well.

heading: 5 CONCLUSION
text: We have proposed HyperSAGE, a generic neural message passing framework for inductive learning on hypergraphs. The proposed approach fully utilizes the inherent higher-order relations in a hypergraph structure without reducing it to a regular graph. Through experiments on several representative datasets, we have shown that HyperSAGE outperforms the other methods for hypergraph learning. Several variants of graph-based learning algorithm such as GCN and GraphSAGE can be derived from the flexible aggregation and neighborhood sampling framework, thus making HyperSAGE a universal framework for learning node representations on hypergraphs as well as graphs.

heading: A EXPERIMENTS: ADDITIONAL DETAILS
text: We perform multi-class classification on co-authorship and co-citation datasets, where the task is to predict the topic (class) for each document.
A.1 DATASET DESCRIPTION
Hypergraphs are created on these datasets by assigning each document as a node and each hyperedge represents (a) all documents co-authored by an author in co-authorship dataset and (b) all documents cited together by a document in co-citation dataset. Each document (node) is represented by bagof-words features. The details about nodes, hyperedges and features is shown in Table 4. We use the same dataset and train-test splits as provided by Yadati et al. (2019) in their publically available implementation 1.
A.2 IMPLEMENTATION DETAILS
We use the following set of hyperparameters similar to the prior work by Kipf & Welling (2016) for all the models.
• hidden layer size: 32 • dropout rate: 0.5 • learning rate: 0.01 • weight decay: 0.0005 • number of training epochs: 150 • λ for explicit Laplacian regularisation: 0.001

heading: B CHOICE OF INTER-EDGE AND INTRA-EDGE AGGREGATIONS
text: Proof. For any given hypergraph H1 = (V,E1,X), let vi denote a node at which global neighborhood equivariance exists. The aggregation output F1(s) at vi can then be written using generalized means Mp as
F1(s) =  1 |N(vi, e)| ∑ vj∈N(vi,e) xp1j  1p1 . (5) To reiterate here, s denotes the unordered set of input as shown in Eq. 5. Further, the inter-edge aggregation F2(·) can be stated as
1HyperGCN Implementation: https://github.com/malllabiisc/HyperGCN
F2(s) =  1|E(vi)| ∑ e∈E(vi)  1 |N(vi, e)| ∑ vj∈N(vi,e) xp1j  p2 p1  1 p2
(6)
This equation can be rewritten as
F2(s) =  1|E(vi)|   1 |N(vi, eq)| ∑
vj∈N(vi,eq)
xp1j
 p2 p1 + ∑
e∈E(vi),e6=eq
 1 |N(vi, e)| ∑ vj∈N(vi,e) xp1j  p2 p1   1 p2
(7) Further, let
Ψ = ∑
e∈E(vi),e6=eq
 1 |N(vi, e)| ∑ vj∈N(vi,e) xp1j  p2 p1 , (8)
then Eq. 7 can be rewritten as
F2(s) =  1|E(vi)|   1 |N(vi, eq)| ∑ vj∈N(vi,eq) xp1j  p2 p1 + Ψ   1 p2
(9)
Let us assume now that hyperedge eq is split into r hyperedges given by E(vi, eq) = {eq1 , eq2 . . . eqr}. Stating the aggregation on the new set of hyperedges as F̃2(s), we assemble the contribution from this new set of hyperedges with added weight terms wj as stated below.
F̃2(s) =  1|E(vi)|  ∑
e∈E(vi,eq)
 1 |N(vi, e)| ∑ vj∈N(vi,e) wjx p1 j  p2 p1 + Ψ   1 p2
(10)
For the property of global neighborhood invariance to hold at vi, the following condition should be satisfied: F2(vi) = F̃2(vi). Based on this, we would like to solve for the weights wj . For this, we equate the two terms and obtain 1
|N(vi, eq)| ∑
vj∈N(vi,eq)
xp1j
 p2 p1 = ∑
e∈E(vi,eq)
 1 |N(vi, e)| ∑ vj∈N(vi,e) wjx p1 j  p2 p1
(11)
We further solve for the variables p1, p2 and wj where Eq. 11 holds. For the sake of clarity, we first simplify Eq. 11 using the following substitutions: α = p2p1 , β = 1 |N(vi,eq)| and βmj = wj |N(vi,em)| , where the index m here is used to refer to the mth hyperedge from among the r hyperedges obtained on splitting eq . Further, let zj = x p1 j for vj ∈ N(vi, eq) and zmj = x p1 j for vj ∈N(vi, em) and em ∈ E(vi, eq). Based on these substitutions, Eq. 11 can be restated as
βα(z1 + z2 + . . .+ zN ) α = (β11z1 + β12z2 + . . .+ β1jzj + . . .+ β1NzN ) α
+ (β21z1 + β22z2 + . . .+ β2jzj + . . .+ β2NzN ) α+
... + (βr1z1 + βr2z2 + . . .+ βrjzj + . . .+ βrNzN ) α. (12)
We seek general solutions for wj and α which holds for all values of zj ∈ [0, 1] since every element in the normalized feature vectors xj lies in [0, 1].
For a generalized solution, the coefficients of zj on the right should be equal to the coefficient of zj on the left. The term on the left can be reformulated as
βα(z1 + z2 + . . .+ zN ) α = βα(z1 + (z2 + z3 + . . .+ zN )) α (13)
Consider the case when |z1| ≤ |z2 + z3 + . . . |, we expand Eq. 13. using binomial expansion for real co-efficients,
βα(z1 + (z2 + z3 + . . .)) α = βα(
( α
0
) zα1 + ( α
1
) zα−11 (z2 + z3 + . . .+ zN )+
...
+
( α
α− 1
) z1(z2 + z3 + . . .+ zN ))
= βα(zα1 + α(z α−1 1 z2 + z α−1 1 z3 + . . .+ z α−1 1 zN )+
...
+ αz1(z2 + z3 + . . .+ zN ) α−1) (14)
Without any loss of generality, we consider splitting of hyperedge eq into r hyperedges such that nodes vγ1 and vγ2 are not contained in the same hyperedge anymore. This implies that RHS in Eq. 14 should not contain product terms of z1 and z2. Hence, the term zα−11 z2 should be such that
α− 1 = 0⇒ α = 1⇒ p1 = p2 (15)
Putting α = 1 and comparing the coefficients in Eq.12, we get β = β11 + β12 + . . .+ β21 + β22 . . .+ βr1 + βr2 + . . .
1
|N(vi, eq)| = r∑ m=1 wj |N(vi, em)|
(16)
wj = 1
|N(vi, eq)| ∗
( r∑
m=1
1
|N(vi, em)|
)−1 (17)
Thus, if an edge eq is split into multiple edges E(vi, eq), then for the two aggregations to hold, the conditions are p1 = p2 and wj = 1|N(vi,eq)| ∗ (∑r m=1 1 |N(vi,em)| )−1 ∀ e ∈ E(vi, eq).
While we provide above a description related to splitting a certain hyperedge eq into r hyperedges, the derived results can be used to compute global neighborhood itself on any given node vi. Similar to eq above, node vi together with its global neighborhood (counted as N(vi)) can be interpreted as a virtual hyperedge that has been split into a number of hyperedges that actually exist and contain vi. These resultant hyperdges are equivalent to the r hyperdges obtained after splitting, as stated above.

heading: C STABILITY TEST ON CORA AND CITESEER

Review summaries:
In this paper, the authors study the problem of learning node embeddings for hypergraphs. While most of the existing studies consider reducing hyper-graphs into graphs, this paper studies learning embeddings directly on the hypergraphs using two stages of aggregations / sampling. The efficacy of the proposed method is illustrated in a semi-supervised as well as inductive setting, where the method achieves better performances than the baselines.