Year: 2021

Abstract:
Hypergraphs are used to model higher-order interactions amongst agents and there exist many practically relevant instances of hypergraph datasets. To enable the efficient processing of hypergraph data, several hypergraph neural network platforms have been proposed for learning hypergraph properties and structure, with a special focus on node classification tasks. However, almost all existing methods use heuristic propagation rules and offer suboptimal performance on benchmarking datasets. We propose AllSet, a new hypergraph neural network paradigm that represents a highly general framework for (hyper)graph neural networks and for the first time implements hypergraph neural network layers as compositions of two multiset functions that can be efficiently learned for each task and each dataset. The proposed AllSet framework also for the first time integrates Deep Sets and Set Transformers with hypergraph neural networks for the purpose of learning multiset functions and therefore allows for significant modeling flexibility and high expressive power. To evaluate the performance of AllSet, we conduct the most extensive experiments to date involving ten known benchmarking datasets and three newly curated datasets that represent significant challenges for hypergraph node classification. The results demonstrate that our method has the unique ability to either match or outperform all other hypergraph neural networks across the tested datasets: As an example, the performance improvements over existing methods and a new method based on heterogeneous graph neural networks are close to 4% on the Yelp and Zoo datasets, and 3% on the Walmart dataset.

text: Hypergraphs are used to model higher-order interactions amongst agents and there exist many practically relevant instances of hypergraph datasets. To enable the efficient processing of hypergraph data, several hypergraph neural network platforms have been proposed for learning hypergraph properties and structure, with a special focus on node classification tasks. However, almost all existing methods use heuristic propagation rules and offer suboptimal performance on benchmarking datasets. We propose AllSet, a new hypergraph neural network paradigm that represents a highly general framework for (hyper)graph neural networks and for the first time implements hypergraph neural network layers as compositions of two multiset functions that can be efficiently learned for each task and each dataset. The proposed AllSet framework also for the first time integrates Deep Sets and Set Transformers with hypergraph neural networks for the purpose of learning multiset functions and therefore allows for significant modeling flexibility and high expressive power. To evaluate the performance of AllSet, we conduct the most extensive experiments to date involving ten known benchmarking datasets and three newly curated datasets that represent significant challenges for hypergraph node classification. The results demonstrate that our method has the unique ability to either match or outperform all other hypergraph neural networks across the tested datasets: As an example, the performance improvements over existing methods and a new method based on heterogeneous graph neural networks are close to 4% on the Yelp and Zoo datasets, and 3% on the Walmart dataset.

heading: 1 INTRODUCTION
text: Graph-centered machine learning, and especially graph neural networks (GNNs), have attracted great interest in the machine learning community due to the ubiquity of graph-structured data and the importance of solving numerous real-world problems such as semi-supervised node classification and graph classification (Zhu, 2005; Shervashidze et al., 2011; Lü & Zhou, 2011). Graphs model pairwise interactions between entities, but fail to capture more complex relationships. Hypergraphs, on the other hand, involve hyperedges that can connect more than two nodes, and are therefore capable of representing higher-order structures in datasets. There exist many machine learning and data mining applications for which modeling high-order relations via hypergraphs leads to better learning performance when compared to graph-based models (Benson et al., 2016). For example, in subspace clustering, in order to fit a d-dimensional subspace, we need at least d+1 data points (Agarwal et al., 2005); in hierarchical species classification of a FoodWeb, a carbon-flow unit based on four species is significantly more predictive than that involving two or three entities (Li & Milenkovic, 2017). Hence, it is desirable to generalize GNN concepts to hypergraphs.
One straightforward way to generalize graph algorithms for hypergraphs is to convert hypergraphs to graphs via clique-expansion (CE) (Agarwal et al., 2005; Zhou et al., 2006). CE replaces hyperedges by (possibly weighted) cliques. Many recent attempts to generalize GNNs to hypergraphs can be viewed as redefining hypergraph propagation schemes based on CE or its variants (Yadati et al., 2019; Feng et al., 2019; Bai et al., 2021), which was also originally pointed out in (Dong et al., 2020). Despite the simplicity of CE, it is well-known that CE causes distortion and leads to undesired losses in learning performance (Hein et al., 2013; Li & Milenkovic, 2018; Chien et al., 2019b).
In parallel, more sophisticated propagation rules directly applicable on hypergraphs, and related to tensor eigenproblems, have been studied as well. One such example, termed Multilinear PageRank (Gleich et al., 2015), generalizes PageRank techniques (Page et al., 1999; Jeh & Widom, 2003) directly to hypergraphs without resorting to the use of CE. Its propagation scheme is closely related to the Z eigenproblem which has been extensively investigated in tensor analysis and spectral hypergraph theory (Li et al., 2013; He & Huang, 2014; Qi & Luo, 2017; Pearson & Zhang, 2014; Gautier et al., 2019). An important result of Benson et al. (2017) shows that tensor-based propagation outperforms a CE-based scheme on several tasks. The pros and cons of these two types of propagation rule in statistical learning frameworks were examined in Chien et al. (2021a). More recently, it was shown in Tudisco et al. (2020) that label propagation based on CE of hypergraphs does not always lead to acceptable performance. Similarly to Chien et al. (2021a), Benson (2019) identified positive traits of CE eigenvectors but argued in favor of using Z eigenvectors due to their more versatile nonlinear formulation compared to that of the eigenvectors of CE graphs.
We address two natural questions pertaining to learning on hypergraphs: “Is there a general framework that includes CE-based, Z-based and other propagations on hypergraphs?” and, “Can we learn propagation schemes for hypergraph neural networks suitable for different datasets and different learning tasks?” We give affirmative answers to both questions. We propose a general framework, AllSet, which includes both CE-based and tensor-based propagation rules as special cases. We also propose two powerful hypergraph neural network layer architectures that can learn adequate propagation rules for hypergraphs using multiset functions. Our specific contributions are as follows.
1. We show that using AllSet, one can not only model CE-based and tensor-based propagation rules, but also cover propagation methods of most existing hypergraph neural networks, including HyperGCN (Yadati et al., 2019), HGNN (Feng et al., 2019), HCHA (Bai et al., 2021), HNHN (Dong et al., 2020) and HyperSAGE (Arya et al., 2020). Most importantly, we show that all these propagation rules can be described as a composition of two multiset functions (leading to the proposed method name AllSet). Furthermore, we also show that AllSet is a hypergraph generalization of Message Passing Neural Networks (MPNN) (Gilmer et al., 2017), a powerful graph learning framework encompassing many GNNs such as GCN (Kipf & Welling, 2017) and GAT (Veličković et al., 2018).
2. Inspired by Deep Sets (Zaheer et al., 2017) and Set Transformer (Lee et al., 2019), we propose AllDeepSets and AllSetTransformer layers which are end-to-end trainable. They can be plugged into most types of graph neural networks to enable effortless generalizations to hypergraphs. Notably, our work represents the first attempt to connect the problem of learning multiset function with hypergraph neural networks, and to leverage the powerful Set Transformer model in the design of these specialized networks.
3. We report, to the best of our knowledge, the most extensive experiments in the hypergraph neural networks literature pertaining to semi-supervised node classification. Experimental results against ten baseline methods on ten benchmark datasets and three newly curated and challenging datasets demonstrate the superiority and consistency of our AllSet approach. As an example, AllSetTransformer outperforms the best baseline method by close to 4% in accuracy on Yelp and Zoo datasets and 3% on the Walmart dataset; furthermore, AllSetTransformer matches or outperforms the best baseline models on nine out of ten datasets. Such improvements are not possible with modifications of HAN (Wang et al., 2019b), a heterogeneous GNN, adapted to hypergraphs or other specialized approaches that do not use Set Transformers.
4. As another practical contribution, we also provide a succinct pipeline for standardization of the hypergraph neural networks evaluation process based on Pytorch Geometric (Fey & Lenssen, 2019). The pipeline is built in a fashion similar to that proposed in recent benchmarking GNNs papers (Hu et al., 2020a; Lim et al., 2021). The newly introduced datasets, along with our reported testbed, may be viewed as an initial step toward benchmarking hypergraph neural networks.
All proofs and concluding remarks are relegated to the Appendix.

heading: 2 BACKGROUND
text: Notation. A hypergraph is an ordered pair of sets G(V, E), where V = {1, 2, . . . , n} is the set of nodes while E is the set of hyperedges. Each hyperedge e ∈ E is a subset of V , i.e., e ⊆ V . Unlike a graph edge, a hyperedge e may contain more than two nodes. If ∀ e ∈ E one has |e| = d ∈ N, the
hypergraph G is termed d-uniform. A d-uniform hypergraph can be represented by a d-dimensional supersymmetric tensor such that for all distinct collections i1, . . . , id ∈ V , Ai1,...,id = 1(d−2)! if e = {i1, ..., id} ∈ E , and Ai1,...,id = 0 otherwise. Henceforth, A:,...,id is used to denote the slice of A along the first coordinate. A hypergraph can alternatively be represented by its incidence matrix H, where Hve = 1 if v ∈ e and Hve = 0 otherwise. We use the superscript (t) to represent the functions or variables at the t-th step of propagation and ‖ to denote concatenation. Furthermore, Θ and b are reserved for a learnable weight matrix and bias of a neural network, respectively. Finally, we use σ(·) to denote a nonlinear activation function (such as ReLU, eLU or LeakyReLU), which depends on the model used.
CE-based propagation on hypergraphs. The CE of a hypergraph G(V, E) is a weighted graph with the same set of nodes V . It can be described in terms of the associated adjacency or incidence matrices which we write with a slight abuse of notation as A(CE)ij = ∑ i3,...,id∈V Ai,j,i3,...,id and H(CE) = HHT , respectively. It is obvious that these two matrices only differ in their diagonal entries (0s versus node degrees, respectively). One step of propagation of a F -dimensional node feature matrix X ∈ Rn×F is captured by A(CE)X or H(CE)X; alternatively, in terms of node feature updates, we have
CEpropA: X(t+1)v,: = ∑ e:v∈e ∑ u:u∈e\v X(t)u,:; CEpropH: X (t+1) v,: = ∑ e:v∈e ∑ u:u∈e X(t)u,:, (1)
Many existing hypergraph convolutional layers actually perform CE-based propagation, potentially with further degree normalization and nonlinear hyperedge weights. For example, the propagation rule of HGNN (Feng et al., 2019) takes the following node-wise form:
X(t+1)v,: = σ ([ 1√ dv ∑ e:v∈e we |e| ∑ u:u∈e X (t) u,:√ du ] Θ(t) + b(t) ) , (2)
where dv denotes the degree of node v, we is a predefined weight of hyperedge e and σ is the ReLU activation function. The hypergraph convolution in HCHA (Bai et al., 2021) uses different degree normalizations and attention weights, with the attention weights depending on node features and the hyperedge features. If datasets do not contain hyperedge feature information or if the features come from a different domain compared to the node features, one cannot use their attention module (Bai et al., 2021). HyperGCN replaces each hyperedge by an incomplete clique via so-called mediators (Yadati et al., 2019). When the hypergraph is 3-uniform, the aforementioned approach becomes a standard weighted CE. Hence, all the described hypergraph neural networks adapt propagation rules based on CE or its variants, potentially with the addition of nonlinear hyperedge weights. The described methods achieve reasonable good performance on standard cocitation and coauthor benchmarking datasets.
Tensor-based propagations. As mentioned in the introduction, there exist more elaborate tensorbased propagation schemes which in some cases outperform CE-based methods. The propagation rules related to Z eigenproblems such as multilinear PageRank (Gleich et al., 2015) and spacey random walks (Benson et al., 2017) are two such examples. The Z eigenproblem for an adjacency tensor A of a d-uniform hypergraph is defined as:
λx = Axd−1 , ∑
i2,...,id
A:,i2,...,idxi2 . . . xid , x ∈ Rn and ‖x‖2 = 1. (3)
Here, Axd−1 equals ∑ i2,...,id
A:,i2,...,idxi2 . . . xid , an entity frequently used in the tensor analysis literature. The Z eigenproblem has been extensively studied both in the context of tensor analysis and network sciences; the problem is also known as the l2 eigenproblem (Lim, 2005; Gautier et al., 2019). We refer the interested readers to Qi & Luo (2017) for a more detailed theoretical analysis of the Z eigenproblems and Benson (2019) for its application in the study of hypergraph centralities.
By ignoring the norm constraint, one can define the following tensor-based propagation rule based on (3) according to:
Zprop: X(t+1)v,: = ∑ e:v∈e (d− 1) ∏ u:u∈e\v X(t)u,:. (4)
Despite its interesting theoretical properties, Zprop is known to have what is termed the “unit problem” (Benson, 2019). In practice, the product can cause numerical instabilities for large hyperedges. Furthermore, Zprop has only been studied for the case of d-uniform hypergraphs, which makes it less relevant for general hypergraph learning tasks. Clearly, CEprop and Zprop have different advantages and disadvantages for different dataset structures. This motivates finding a general framework that encompasses these two and other propagation rules. In this case, we aim to learn the suitable propagation scheme under such a framework for hypergraph neural networks.

heading: 3 ALLSET: ONE METHOD TO BIND THEM ALL
text: We show that all the above described propagation methods can be unified within one setting, termed AllSet. The key observation is that all propagation rules equal a composition of two multiset functions, defined below. Definition 3.1. A function f is permutation invariant if and only if ∀π ∈ Sn, where Sn denotes the symmetric group of order n!, f(xπ(1), . . . ,xπ(n)) = f(x1, . . . ,xn). Definition 3.2. We say that a function f is a multiset function if it is permutation invariant.
Next, let Ve,X = {Xu,: : u ∈ e} denote the multiset of hidden node representations contained in the hyperedge e. Also, let Z ∈ R|E|×F ′ denote the hidden hyperedge representations. Similarly, let Ev,Z = {Ze,: : v ∈ e} be the multiset of hidden representations of hyperedges that contain the node v. The AllSet framework uses the update rules
Z(t+1)e,: = fV→E(Ve,X(t) ; Z (t) e,: ), X (t+1) v,: = fE→V(Ev,Z(t+1) ; X (t) v,:), (5)
where fV→E and fE→V are two multiset functions with respect to their first input. For the initial condition, we choose Z(0)e,: and X (0) v,: to be hyperedge features and node features, respectively (if available). If these are not available, we set both entities to be all-zero matrices. Note that we make the tacit assumption that both functions fV→E and fE→V also include the hypergraph G as an input. This allows degree normalization to be part of our framework. As one can also distinguish the aggregating node v from the multiset Ve,X(t) , we also have the following AllSet variant:
Z(t+1),ve,: = fV→E(Ve\v,X(t) ; Z (t),v e,: ,X (t) v,:), X (t+1) v,: = fE→V(Ev,Z(t+1),v ; X (t) v,:), (6)
For simplicity, we omit the last input argument X(t)v,: for fV→E in (6), unless explicitly needed (as in the proof pertaining to HyperGCN). The formulation (5) lends itself to a significantly more computationally- and memory-efficient pipeline. This is clearly the case since for each hyperedge e, the expression in (5) only uses one hyperedge hidden representation while the expression (6) uses |e| distinct hidden representations. This difference can be substantial when the hyperedge sizes are large. Hence, we only use (6) for theoretical analysis purposes and (5) for all experimental verifications. The next theorems establish the universality of the AllSet framework.
Theorem 3.3. CEpropH of (1) is a special case of AllSet (5). Furthermore, CEpropA of (1) and Zprop of (4) are also special cases of AllSet (6).
Sketch of proof. If we ignore the second input and choose both fV→E and fE→V to be sums over their input multisets, we recover the CE-based propagation rule CEpropH of (1) via (5). For CEpropA, the same observation is true with respect to (6). If one instead chooses fV→E to be the product over its input multiset, multiplied by the scalar |Ve,X(t) | − 1, one recovers the tensor-based propagation Zprop of (4) via (6).
Next, we show that many state-of-the-art hypergraph neural network layers also represent special instances of AllSet and are strictly less expressive than AllSet. Theorem 3.4. The hypergraph neural network layers of HGNN (2), HCHA (Bai et al., 2021), HNHN (Dong et al., 2020) and HyperSAGE (Arya et al., 2020) are all special cases of AllSet (5). The HyperGCN layer (Yadati et al., 2019) is a special instance of AllSet (6). Furthermore, all the above methods are strictly less expressive than AllSet (5) and (6). More precisely, there exists a combination of multiset functions fV→E and fE→V for AllSet (5) and (6) that cannot be modeled by any of the aforementioned hypergraph neural network layers.
The first half of the proof is by direct construction. The second half of the proof consists of counterexamples. Intuitively, none of the listed hypergraph neural network layers can model Zprop (3) while we established in the previous result that Zprop is a special case of AllSet.
The last result shows that the MPNN (Gilmer et al., 2017) framework is also a special instance of our AllSet for graphs, which are (clearly) special cases of hypergraphs. Hence, AllSet may also be viewed as a hypergraph generalization of MPNN. Note that MPNN itself generalizes many wellknown GNNs, such as GCN (Kipf & Welling, 2017), Gated Graph Neural Networks (Li et al., 2015) and GAT (Veličković et al., 2018). Theorem 3.5. MPNN is a special case of AllSet (6) when applied to graphs.

heading: 4 HOW TO LEARN ALLSET LAYERS
text: The key idea behind AllSet is to learn the multiset functions fV→E and fE→V on the fly for each dataset and task. To facilitate this learning process, we first have to properly parametrize the multiset functions. Ideally, the parametrization should represent a universal approximator for a multiset function that allows one to retain the higher expressive power of our architectures when compared to that of the hypergraph neural networks described in Theorem 3.4. For simplicity, we focus on the multiset inputs of fV→E and fE→V and postpone the discussion pertaining to the second arguments of the functions to the end of this section.
Under the assumption that the multiset size is finite, the authors of Zaheer et al. (2017) and Wagstaff et al. (2019) proved that any multiset functions f can be parametrized as f(S) = ρ (∑ s∈S φ(s) ) , where ρ and φ are some bijective mappings (Theorem 4.4 in Wagstaff et al. (2019)). In practice, these mappings can be replaced by any universal approximator such as a multilayer perceptron (MLP) (Zaheer et al., 2017). This leads to the purely MLP AllSet layer for hypergraph neural networks, termed AllDeepSets.
AllDeepSets: fV→E(S) = fE→V(S) = MLP (∑ s∈S MLP(s) ) . (7)
The authors of Lee et al. (2019) argued that the unweighted sum in Deep Set makes it hard to learn the importance of each individual contributing term. Thus, they proposed the Set Transformer paradigm which was shown to offer better performance than Deep Sets as a learnable multiset function architecture. Based on this result, we also propose an attention-based AllSet layer for hypergraph neural networks, termed AllSetTransformer. Given the matrix S ∈ R|S|×F which represents the multiset S of F -dimensional real vectors, the definition of AllSetTransformer is
AllSetTransformer: fV→E(S) = fE→V(S) = LN (Y + MLP(Y)) ,
where Y = LN (θ + MHh,ω(θ,S,S)) ,MHh,ω(θ,S,S) = ‖hi=1O(i), O(i) = ω ( θ(i)(K(i))T ) V(i), θ , ‖hi=1θ(i), K(i) = MLPK,i(S), V(i) = MLPV,i(S). (8)
Here, LN represents the layer normalization (Ba et al., 2016) and θ ∈ R1×hFh is a learnable weight; in addition, MHh,ω is a multihead attention mechanism with h heads and activation function ω (Vaswani et al., 2017). Note that the dimension of the output of MHh,ω is 1×hFh where Fh is the hidden dimension of V(i) ∈ R|S|×Fh . In our experimental setting, we choose ω to be the softmax function which is robust in practice. Our formulation of projections in MHh,ω is slight more general than standard linear projections. If one restricts MLPK,i and MLPV,i to one-layer perceptrons without a bias term (i.e., including only a learnable weight matrix), we obtain standard linear projections in the multihead attention mechanism. The output dimensions of MLPK,i and MLPV,i are both equal to R|S|×Fh . It is worth pointing out that all the MLP modules operate row-wise, which means they are applied to each multiset element (a real vector) independently and in an identical fashion. This directly implies that MLP modules are permutation equivariant.
Based on the above discussion and Proposition 2 of Lee et al. (2019) we have the following result. Proposition 4.1. The functions fV→E and fE→V defined in AllSetTransformer (8) are permutation invariant. Furthermore, the functions fV→E and fE→V defined in (8) are universal approximators of multiset functions when the size of the input multiset is finite.
Note that in practice, both the size of hyperedges and the node degrees are finite. Thus, the finite size multiset assumption is satisfied. Therefore, the above results directly imply that the AllDeepSets (7) and AllSetTransformer (8) layers have the same expressive power as the general AllSet framework. Together with the result of Theorem 3.4, we arrive at the conclusion that AllDeepSets and AllSetTransformer are both more expressive than any other aforementioned hypergraph neural network.
Conceptually, one can also incorporate the Set Attention Block and the two steps pooling strategy of Lee et al. (2019) into AllSet. However, it appears hard to make such an implementation efficient and we hence leave this investigation as future work. In practice, we find that even our simplified design (8) already outperforms all baseline hypergraph neural networks, as demonstrated by our extensive experiments. Also, it is possible to utilize the information of the second argument of fV→E and fE→V via concatenation, another topic relegated to future work.
As a concluding remark, we observe that the multiset functions in both AllDeepSets (7) and AllSetTransformer (8) are universal approximators for general multiset functions. In contrast, the other described hypergraph neural network layers fail to retain the universal approximation property for general multiset functions, as shown in Theorem 3.4. This implies that all these hypergraph neural network layers have strictly weaker expressive power compared to AllDeepSets (7) and AllSetTransformer (8). We also note that any other universal approximators for multiset functions can easily be combined with our AllSet framework (as we already demonstrated by our Deep Sets and Set Transformer examples). One possible candidate is Janossy pooling (Murphy et al., 2019) which will be examined as part of our future work. Note that more expressive models do not necessarily have better performance than less expressive models, as many other factors influence system performance (as an example, AllDeepSet performs worse than AllSetTransformer albeit both have the same theoretical expressive power; this is in agreement with the observation from Lee et al. (2019) that Set Transformer can learn multiset functions better than Deep Set.). Nevertheless, we demonstrate in the experimental verification section that our AllSetTransformer indeed has consistently better performance compared to other baseline methods.

heading: 5 RELATED WORKS
text: Graph neural networks on graphs. GNNs have received significant attention in the past, often under the umbrella of Geometric Deep Learning (Bronstein et al., 2017). Many successful architectures have been proposed for various tasks on graphs, including GCN (Kipf & Welling, 2017), GAT (Vaswani et al., 2017), GraphSAGE (Hamilton et al., 2017), GIN (Xu et al., 2019) and many others (Klicpera et al., 2019; Wu et al., 2019; Velickovic et al., 2019; Li et al., 2020; Xu et al., 2018; Chien et al., 2021b). There have also been some recent attempts to use Transformers in GNNs (Baek et al., 2021; Yun et al., 2019; Hu et al., 2020b). Nevertheless, all these methods only apply to graphs and not to hypergraphs. Although CE can be used in all these case, this is clearly not an optimal strategy due to the previously mentioned distortion issues. There are also many techniques that can improve GNNs in various directions. For example, PairNorm (Zhao & Akoglu, 2019) and DropEdge (Rong et al., 2019) allow one to build deeper GNNs. ClusterGCN (Chiang et al., 2019) and
GraphSAINT (Zeng et al., 2019), on the other hand, may be used to significantly scale up GNNs. Residual correlation (Jia & Benson, 2020) and CopulaGNN (Ma et al., 2021) have been shown to improve GNNs on graph regression problems. These works highlight new directions and limitations of not only our method, but also hypergraph neural networks in general. Nevertheless, we believe that AllSet layers can be adapted to resolve these issues using similar ideas as those proposed for graph layers.
Hypergraph learning. Learning on hypergraphs has attracted significant attention due to its ability to capture higher-order structural information (Li et al., 2017; 2019). In the statistical learning and information theory literature, researchers have studied community detection problem for hypergraph stochastic block models (Ghoshdastidar & Dukkipati, 2015; Chien et al., 2018; 2019a). In the machine learning community, methods that mitigate drawbacks of CE have been reported in (Li & Milenkovic, 2017; Chien et al., 2019b; Hein et al., 2013; Chan et al., 2018). Despite these advances, hypergraph neural network developments are still limited beyond the works covered by the AllSet paradigm. Exceptions include Hyper-SAGNN (Zhang et al., 2019), LEGCN (Yang et al., 2020) and MPNN-R (Yadati, 2020), the only three hypergraph neural networks that do not represent obvious special instances of AllSet. But, Hyper-SAGNN focuses on hyperedge prediction while we focus on semi-supervised node classification. LEGCN first transforms hypergraphs into graphs via line expansion and then applies a standard GCN. Although the transformation used in LEGCN does not cause a large distortion as CE, it significantly increases the number of nodes and edges. Hence, it is not memory and computationally efficient (more details about this approach can be found in the Appendix F). MPNN-R focuses on recursive hypergraphs (Joslyn & Nowak, 2017), which is not the topic of this work. It is an interesting future work to investigate the relationship between AllSet and Hyper-SAGNN or MPNN-R when extending AllSet to hyperedge prediction tasks or recursive hypergraph implementations. It is also possible to define propagation schemes based on other tensor eigenproblems, such as H eigenproblems (Qi & Luo, 2017). Defining propagation rules based on H eigenproblems can lead to imaginary features which is problematic: A more detailed discussion regarding this direction is available in the Appendix G.
Star expansion, UniGNN and Heterogeneous GNNs. A very recent work concurrent to ours, UniGNN (Huang & Yang, 2021), also proposes to unify hypergraph and GNN models. Both Huang & Yang (2021) and our work can be related to hypergraph star expansion (Agarwal et al., 2006; Yang et al., 2020), which results in a bipartite graph (see Figure 1). One particular variant, UniGIN, is related to our AllDeepSets model, as both represent a hypergraph generalization of GIN (Xu et al., 2019). However, UniGNN does not make use of deep learning methods for learning multiset functions, which is crucial for identifying the most appropriate propagation and aggregation rules for individual datasets and learning tasks as done by AllSetTransformer (see Section 6 for supporting information). Also, the most advanced variant of UniGNN, UniGCNII, is not comparable to AllSetTransformers. Furthermore, one could also naively try to apply heterogeneous GNNs, such as HAN (Wang et al., 2019b), to hypergraph datasets converted into bipartite graphs. This approach was not previously examined in the literature, but we experimentally tested it nevertheless to show that the performance improvements in this case are significantly smaller than ours and that the method does not scale well even for moderately sized hypergraphs. Another very recent work (Xue et al., 2021) appears at first glance similar to ours, but it solves a very different problem by transforming a heterogeneous bipartite graph into a hypergraph and then apply standard GCN layers to implement fV→E and fE→V , which is more related to HNHN (Dong et al., 2020) and UniGCN (Huang & Yang, 2021) and very different from AllSetTransformer.
Learning (multi)set functions. (Multi)set functions, which are also known as pooling architectures for (multi)sets, have been used in numerous problems including causality discovery (Lopez-Paz et al., 2017), few-shot image classification (Snell et al., 2017) and conditional regression and classification (Garnelo et al., 2018). The authors of Zaheer et al. (2017) provide a universal way to parameterize the (multi)set functions under some mild assumptions. Similar results have been proposed independently by the authors of Qi et al. (2017) for computer vision applications. The authors of Lee et al. (2019) propose to learn multiset functions via attention mechanisms. This further inspired the work in Baek et al. (2021), which adopted the idea for graph representation learning. The authors of Wagstaff et al. (2019) discuss the limitation of Zaheer et al. (2017), and specifically focus on continuous functions. A more general treatment of how to capture complex dependencies among multiset elements is available in Murphy et al. (2019). To the best of our knowledge, this work is the first to build the connection between learning multiset functions with propagations on hypergraph.

heading: 6 EXPERIMENTS
text: We focus on semi-supervised node classification in the transductive setting. We randomly split the data into training/validation/test samples using (50%/25%/25%) splitting percentages. We aggregate the results of 20 experiments using multiple random splits and initializations.
Methods used for comparative studies. We compare our AllSetTransformer and AllDeepSets with ten baseline models, MLP, CE+GCN, CE+GAT, HGNN (Feng et al., 2019), HCHA (Bai et al., 2021), HyperGCN (Yadati et al., 2019), HNHN (Dong et al., 2020), UniGCNII (Huang & Yang, 2021) and HAN (Wang et al., 2019b), with both full batch and mini-batch settings. All architectures are implemented using the Pytorch Geometric library (PyG) (Fey & Lenssen, 2019) except for HAN, in which case the implementation was retrieved from Deep Graph Library (DGL) (Wang et al., 2019a). The implementation of HyperGCN1 is used in the same form as reported in the official repository. We adapted the implementation of HCHA from PyG. We also reimplemented HNHN and HGNN using the PyG framework. Note that in the original implementation of HGNN2, propagation is performed via matrix multiplication which is far less memory and computationally efficient when compared to our implementation. MLP, GCN and GAT are executed directly from PyG. The UniGCNII code is taken from the official site3. For HAN, we tested both the full batch training setting and a mini-batch setting provided by DGL. We treated the vertices (V) and hyperedges (E) as two heterogeneous types of nodes, and used two metapaths: {V → E → V, E → V → E} in its semantic attention. In the mini-batch setting, we used the DGL’s default neighborhood sampler with a number of neighbors set to 32 during training and 64 for validation and testing purposes. In both settings, due to the specific conversion of hyperedges into nodes, our evaluations only involve the original labeled vertices in the hypergraph and ignore the hyperedge node-proxies. More details regarding the experimental settings and the choices of hyperparameters are given in the Appendix I.
Benchmarking and new datasets. We use ten available datasets from the existing hypergraph neural networks literature and three newly curated datasets from different application domains. The benchmark datasets include cocitation networks Cora, Citeseer and Pubmed, downloaded from Yadati et al. (2019). The coauthorship networks Cora-CA and DBLP-CA were adapted from Yadati et al. (2019). We also tested datasets from the UCI Categorical Machine Learning Repository (Dua & Graff, 2017), including 20Newsgroups, Mushroom and Zoo. Datasets from the area of computer vision and computer graphics include ModelNet40 (Wu et al., 2015) and NTU2012 (Chen et al., 2003). The hypergraph construction follows the recommendations from Feng et al. (2019); Yang et al. (2020). The three newly introduced datasets are adaptations of Yelp (Yelp), House (Chodrow et al., 2021) and Walmart (Amburg et al., 2020). Since there are no node features in the original datasets of House and Walmart, we use Gaussian random vectors instead, in a fashion similar to what was proposed for Contextual stochastic block models (Deshpande et al., 2018). We use postfix (x) to indicate the standard deviation of the added Gaussian features. The partial statistics of all datasets are provided in Table 1, and more details are available in the Appendix H.
Results. We use accuracy (micro-F1 score) as the evaluation metric, along with its standard deviation. The relevant findings are summarized in Table 2. The results show that AllSetTransformer is the most robust hypergraph neural network model and that it has the best overall performance when compared to state-of-the art and new models such a hypergraph HAN. In contrast, all baseline methods perform poorly on at least two datasets. For example, UniGCNII and HAN are two of the best performing baseline models according to our experiments. However, UniGCNII performs poorly on Zoo, Yelp and Walmart when compared to our AllSetTransformer. More precisely, AllSetTransformer outperforms UniGCNII by 11.01% in accuracy on the Walmart(1) dataset. HAN has poor performance when compared AllSetTransformer on Mushroom, NTU2012 and ModelNet40. Fur-
1 https://github.com/malllabiisc/HyperGCN 2 https://github.com/iMoonLab/HGNN 3 https://github.com/OneForward/UniGNN
thermore, it experiences memory overload issues on Yelp and Walmart with a full batch setting and performs poorly with a mini-batch setting on the same datasets. Numerically, AllSetTransformer outperforms HAN with full batch setting by 9.14% on the Mushroom and HAN with mini-batch setting and by 16.89% on Walmart(1). These findings emphasize the importance of including diverse datasets from different application domains when trying to test hypergraph neural networks fairly. Testing standard benchmark datasets such as Cora, Citeseer and Pubmed alone is insufficient and can lead to biased conclusions. Indeed, our experiments show that all hypergraph neural networks work reasonably well on these three datasets. Our results also demonstrate the power of Set Transformer when applied to hypergraph learning via the AllSet framework.
The execution times of all methods are available in the Appendix I: They show that the complexity of AllSet is comparable to that of the baseline hypergraph neural networks. This further strengthens the case for AllSet, as its performance gains do not come at the cost of high computational complexity. Note that in HAN’s mini-batch setting, the neighborhood sampler is performed on CPU instead of GPU, hence its training time is significantly higher than that needed by other methods, due to the frequent I/O operation between CPU and GPU. On some larger datasets such as Yelp and Walmart, 20 runs take more than 24 hours so we only recorded the results for first 10 runs.
The performance of AllDeepSets is not on par with that of AllSetTransformer, despite the fact that both represent universal approximators of the general AllSet formalism. This result confirms the assessment of Lee et al. (2019) that attention mechanisms are crucial for learning multiset functions in practice. Furthermore, we note that combining CE with existing GNNs such as GCN and GAT leads to suboptimal performance. CE-based approaches are also problematic in terms of memory efficiency when large hyperedges are present. This is due to the fact the CE of a hyperedge e leads to Θ(|e|2) edges in the resulting graph. Note that as indicated in Table 2, CE-based methods went out-of-memory (OOM) for 20Newsgroups and Yelp. These two datasets have the largest maximum hyperedge size, as can be see from Table 1. HAN encounters the OOM issue on even more datasets when used in the full batch setting, and its mini-batch setting mode perform poorly on Yelp and Walmart. This shows that a naive application of standard heterogeneous GNNs on large hypergraphs often fails and is thus not as robust as our AllSetTransformer. The mediator HyperGCN approach exhibits numerical instabilities on some datasets (i.e., Zoo and House) and may hence not be suitable for learning on general hypergraph datasets.

heading: 7 ETHICS STATEMENT
text: We do not aware of any potential ethical issues regarding our work. For the newly curated three datasets, there is no private personally identifiable information. Note that although nodes in House datasets represent congresspersons and hyperedges represent members serving on the same committee, this information is public and not subject to privacy constraints. For the Walmart dataset, the nodes are products and hyperedges are formed by sets of products purchased together. We do not include any personal information regarding the buyers (customers) in the text. In the Yelp dataset the nodes represent restaurants and hyperedges are collections of restaurants visited by the same user. Similar to the Walmart case, there is no user information included in the dataset. More details of how the features in each datasets are generated can be found in Appendix H.

heading: 8 REPRODUCIBILITY STATEMENT
text: We have tried our best to ensure reproducibility of our results. We built a succinct pipeline for standardization of the hypergraph neural networks evaluation process based on Pytorch Geometric. This implementation can be checked by referring to our supplementary material. We include all dataset in our supplementary material and integrate all tested methods in our code. Hence, one can simply reproduce all experiment results effortlessly (by just running a one-line command). All details regarding how the datasets were prepared are stated in Appendix H. All choices of hyperparameters and the process of selecting them are available in Appendix I. Our experimental settings including the specifications of our machine and environment, the training/validation/test split and the evaluation metric. Once again, refer ro the Appendix I and Section 6. We also clearly specify all the package dependencies used in our code in the Supplementary material.

heading: A CONCLUSIONS
text: We proposed AllSet, a novel hypergraph neural network paradigm that represents a highly general framework for hypergraph neural networks. We implemented hypergraph neural network layers as compositions of two multiset functions that can be efficiently learned for each task and each dataset. Furthermore, for the first time, we integrated Deep Set and Set Transformer methods within hypergraph neural networks for the purpose of learning the described multiset functions. Our theoretical analysis demonstrated that most of the previous hypergraph neural networks are strictly less expressive then our proposed AllSet framework. We conducted the most extensive experiments to date involving ten known benchmarking datasets and three newly curated datasets that represent significant challenges for hypergraph node classification. The results showed that our method has the unique ability to either match or outperform all other baselines, including the state-of-the-art hypergraph neural networks UniGNN (Huang & Yang, 2021). Remarkably, our baseline also included HAN (Wang et al., 2019b), the heterogeneous hypergraph neural networks, via star expansion as the new comparative method in the hypergraph neural network literature for the first time. Our results show that leveraging powerful multiset function learners in our AllSet framework is indeed helpful for hypergraph learning. As a promising future direction, more advanced multiset function learners such as Janossy pooling (Murphy et al., 2019) can be used in our AllSet framework and potentially further improve the performance. We left this topic in future works.

heading: B PROOF OF THEOREM 3.3
text: First, we show that one can recover CEpropH (1) from AllSet (5). By choosing fV→E and fE→V to be the sums over appropriate input multisets and by ignoring the second input, we obtain
Z(t+1)e,: = fV→E(Ve,X(t) ; Z (t) e,: ) = ∑ x∈V
e,X(t)
x = ∑ u∈e X(t)u,:, (9)
X(t+1)v,: = fE→V(Ev,Z(t+1) ; X (t) v,:) = ∑ x∈E
v,Z(t+1)
x = ∑ e:v∈e Z(t+1)e,: . (10)
Combining these two equations gives X(t+1)v,: = ∑ e:v∈e Z(t+1)e,: = ∑ e:v∈e ∑ u∈e X(t)u,:, (11)
which matches the update equations of CEpropH (1).
Next, we prove that one can recover CEpropA (1) from AllSet (6). We once again choose fV→E and fE→V to be the sums over appropriate input multisets and ignore the second input term. This results in the following update equations:
Z(t+1),ve,: = fV→E(Ve\v,X(t) ; Z (t),v e,: ) = ∑ x∈V
e\v,X(t)
x = ∑ u∈e\v X(t)u,:, (12)
X(t+1)v,: = fE→V(Ev,Z(t+1),v ; X (t) v,:) = ∑ x∈E
v,Z(t+1),v
x = ∑ e:v∈e Z(t+1),ve,: . (13)
Combining the two equations we obtain X(t+1)v,: = ∑ e:v∈e Z(t+1),ve,: = ∑ e:v∈e ∑ u∈e\v X(t)u,:, (14)
which represents the update rule of CEpropA from (1).
In the last step, we prove that one can recover Zprop (4) from AllSet (6). By choosing fV→E and fE→V to be the product and sum over appropriate input multisets, respectively, and by ignore the
second input, we have:
Z(t+1),ve,: = fV→E(Ve\v,X(t) ; Z (t),v e,: ) = ∏ x∈V
e\v,X(t)
x = ∏ u∈e\v X(t)u,:, (15)
X(t+1)v,: = fE→V(Ev,Z(t+1),v ; X (t) v,:) = ∑ x∈E
v,Z(t+1),v
x = ∑ e:v∈e Z(t+1),ve,: . (16)
Combining these two equations we arrive at X(t+1)v,: = ∑ e:v∈e Z(t+1),ve,: = ∑ e:v∈e ∏ u∈e\v X(t)u,:, (17)
which matches Zprop from (4). This completes the proof.

heading: C PROOF OF THEOREM 3.4
text: First we prove that the hypergraph neural network layer of HGNN (2) is a special instance of AllSet (5). By choosing fV→E and fE→V to be the weighted sum over appropriate input multisets, where the weights are chosen according to the node degree, edge degree, and edge weights, and by ignore the second input, we have:
Z(t+1)e,: = fV→E(Ve,X(t) ; Z (t) e,: ) = ∑ u∈e X (t) u,:√ du , (18)
X(t+1)v,: = fE→V(Ev,Z(t+1) ; X (t) v,:) = σ ( 1√ dv ∑ e:v∈e weZ (t+1) e,: Θ(t) |e| + b(t) ) . (19)
Since fV→E and fE→V both use the hypergraph G as their input, the functions can use the node degrees, edge degrees and edge weights as their arguments. Also, it is not hard to see that our choices for fV→E (18) and fE→V (19) are permutation invariant in Ve,X(t) and Ev,Z(t+1) , respectively. Plugging (18) into (19) leads to:
X(t+1)v,: = σ ( 1√ dv ∑ e:v∈e we |e| ∑ u∈e X (t) u,:√ du Θ(t) + b(t) ) , (20)
which represents the HGNN layer (2).
For the HCHA layer, we have a node-wise formulation that reads as follows:
X(t+1)v,: = σ
([ 1
dv ∑ e:v∈e weα (t) ve |e| ∑ u:u∈e α(t)ueX (t) u,:
] Θ(t) + b(t) ) , (21)
where the attention weight α(t)ue depends on the node features X(t) and the feature of hyperedge e. Here, σ(·) is a nonlinear activation function such as LeakyReLU and eLU. An analysis similar to that described for HGNN can be used in this case as well. The only difference is in the choice of the attention weights αue and αve. The definition of attention weights for HCHA is presented below.
α(t)ue = exp(σ(aT [X (t) u,: ‖ Z(t)e,: ]))∑
e:u∈e exp(σ(a T [X (t) u,: ‖ Z(t)e,: ]))
. (22)
Clearly, the attention function in (22) has Ve,X(t) and Z (t) e,: as its arguments. Furthermore, we can choose fV→E and fE→V as:
Z(t+1)e,: = fV→E(Ve,X(t) ; Z (t) e,: ) = ∑ u∈e α(t)ueX (t) u,:, (23)
X(t+1)v,: = fE→V(Ev,Z(t+1) ; X (t) v,:) = σ ( 1√ dv ∑ e:v∈e weα (t) veZ (t+1) e,: Θ(t) |e| + b(t) ) . (24)
Note that both (23) and (24) are permutation invariant, which means that they are valid choices for fV→E and fE→V . Combining these two equations reproduces the HCHA layer of (21).
For the HyperGCN layer, ignoring the degree normalization, one can use the following formulation:
X(t+1)v,: = σ ([∑ e:v∈e ∑ u:u∈e w(t)uv,eX (t) u,: ] Θ(t) + b(t) ) . (25)
Here, the weight w(t)uv,e depends on all node features within the hyperedge {X(t)u,: : u ∈ e}, and σ(·) is a nonlinear activation function (for example, ReLU). The same analysis as presented for the previous cases may be used in this case as well: The only difference lies in the choice of the weights w (t) uv,e. According to the original HyperGCN paper (Yadati et al., 2019), these weights are defined as
w(t)uv,e =
{ 1
2|e|−3 if u ∈ {ie, je} or v ∈ {ie, je}, 0 otherwise. , (26)
where (ie, je) = argmaxu,v∈e‖(X(t)u,: −X(t)v,:)Θ(t)‖. (27)
Again, it is straightforward to see that w(t)uv,e is a function of Ve\v,X(t) and X (t) v,: . Also, it is permutation invariant with respect to Ve\v,X(t) . Hence, we can choose fV→E and fE→V as
Z(t+1),ve,: = fV→E(Ve\v,X(t) ; Z (t),v e,: ,X (t) v,:) = ∑ u∈e\v w(t)uv,eX (t) u,:, (28)
X(t+1)v,: = fE→V(Ev,Z(t+1),v ; X (t) v,:) = σ (∑ e:v∈e Z(t+1),ve,: Θ (t) + b(t) ) . (29)
Combining the two equations leads to the HyperGCN layer from (25).
Next, we show that HNHN layer introduced in Dong et al. (2020) is a special case of AllSet (5). The definition of HNHN layer is as follows
Z(t+1)e,: = σ
([ 1
de,l,β ∑ u∈e du,r,βX (t) u,:
] Θ
(t) E + b (t) E
) , (30)
X(t+1)v,: = σ
([ 1
dv,l,α ∑ e:v∈e de,r,αZ (t+1) e,:
] Θ
(t) V + b (t) V
) , (31)
where de,l,β = ∑ u∈e |du|β , du,r,β = dβu; dv,l,β = ∑ e:v∈e |dv|α, dv,r,α = dαv . (32)
Note that α and β are two hyperparameters that can be tuned in HNHN. As before, σ(·) is a nonlinear activation function (e.g., ReLU). It is obvious that we can choose fV→E and fE→V according to (30) and (31), respectively. This is due to the fact that these expressions only involves degree normalizations and linear transformations.
Finally, we show that the HyperSAGE layer from Arya et al. (2020) is a special case of AllSet (5). The HyperSAGE layer update rules are as follows:
Z(t+1)e,: =
( 1
|e| ∑ u∈e (X(t)u,:) p
)1/p , (33)
X(t+1),?v,: =
( 1
|{e : v ∈ e}| ∑ e:v∈e (Z(t)e,: ) p )1/p + X(t)v,: , (34)
X(t+1)v,: = σ
( X (t+1),? v,:
||X(t+1),?v,: || Θ(t+1)
) . (35)
where σ(·) is a nonlinear activation function. The update (33) can be recovered by simply choosing fV→E to be the lp (power) mean. For the fE→V component, we first model fE→V as a composition
of another two multiset functions. The first is the lp (power) mean with respect to its first input, while the second is addition with respect to the second input. This recovers (34). The second of the two defining functions can be chosen as (35), which is also a multiset function. This procedure leads to fE→V . This completes the proof of the first claim pertaining to the universality of AllSet.
To address the claim that the above described hypergrpah neural network layers have strictly smaller expressive power then AllSet, one only has to observe that these hypergraph neural network layers cannot approximate arbitrary multiset functions in either the fV→E or fE→V component. We discuss both these functions separately.
With regards to the HGNN layer, it is clear that two linear transformations cannot model arbitrary multiset functions such as the product in Zprop (4). For the HCHA layer, we note that if all node features are identical and the hyperedge features are all-zero vectors, all the attention weights αue are the same. This setting is similar to that described for the HGNN layer and thus this rule cannot model arbitrary multiset functions. For the HyperGCN layer (25), consider a 3-uniform hypergraph as its input. In this case, by definition, the weights wuv,e are all equal. Again, using only linear transformations one cannot model the product operation in Zprop (4); the same argument holds even when degree normalizations are included. For the HNHN layer, note that the E → V component of (31) is just one MLP layer that follows the sum ∑ e:v∈e, which cannot model arbitrary multiset functions based on the results of Deep Sets (Zaheer et al., 2017). As a final note, we point out that the HyperSAGE layer involves only one learnable matrix Θ and is hence also a linear transformation, which cannot model arbitrary multiset functions.
This completes the proof.

heading: D PROOF OF THEOREM 3.5
text: The propagation rule of MPNN reads as follows: m(t+1)v,: = ∑
u∈N(v)
Mt(X (t) u,:,X (t) v,: ,Z (0),v e,: ), X (t+1) v,: = Ut(X (t) v,: ,m (t+1) v,: ). (36)
Here, m denotes the message obtained by aggregating messages from the neighborhood of the node v, while Mt and Ut are certain functions selected at the t-th step of propagation. To recover MPNN from AllSet (6), we simply choose fV→E and fE→V as
Z(t+1),ve,: , fV→E(Ve\v,X(t) ; Z (t),v e,: ) = fV→E({X(t)u,:}; Z(t),ve,: ) = X(t)u,: ‖ Z(0),ve,: , s.t. u ∈ e \ v,
X(t+1)v,: , fE→V(Ev,Z(t+1),v ; X (t) v,:) = fE→V({Z(t+1),ve,: }e:v∈e; X(t)v,:)
= Ut ( X(t)v,: , ∑ e:v∈e M ′t(Z (t+1),v e,: ,X (t) v,:) ) = Ut ( X(t)v,: , ∑ e:v∈e Mt(X (t) u,:,X (t) v,: ,Z (0),v e,: ) ) . (37)
Hence, MPNN is a special case of AllSet for graph inputs.

heading: E PROOF OF PROPOSITION 4.1
text: The proof is largely based on the proof of Proposition 2 of the Set Trasnformer paper (Lee et al., 2019) but is nevertheless included for completeness. We ignore all layer normalizations as in the proof of (Lee et al., 2019) and start with the following theorem.
Theorem E.1 (Theorem 1 in Lee et al. (2019)). Functions of the form MLP ∑
(MLP) are universal approximators in the space of permutation invariant functions.
This result is based on Zaheer et al. (2017). According to Wagstaff et al. (2019), we have the constraint that the input multiset has to be finite.
Next, we show that the simple mean operator is a special case of a multihead attention module. For simplicity, we consider the case of a single head, which corresponds to h = 1, as we can always set the other heads to zero by choosing MLPV,i(S) = 0 for all i ≥ 2. Following the proof of Lemma 3 in Lee et al. (2019), we set the learnable weight θ to be the all-zero vector and use ω(·) = 1 + g(·)
(element-wise) as an activation function such that g(0) = 0. The MH1,ω module in (8) then becomes
MH1,ω(θ,S,S) = O(1) = ω ( θ(MLPK,1(S))T ) MLPV,1(S) = |S|∑ i=1 MLPV,1(S)i. (38)
The AllSetTranformer layer (8) takes the form
fV→E(S) = Y + MLP(Y), where Y = |S|∑ i=1 MLPV,1(S). (39)
Note that Y is a vector. Clearly, we can choose an MLP such that MLP(Y) equals to another MLP(Y) that results in subtracting Y. Thus, we have:
fV→E(S) = MLP(Y) = MLP  |S|∑ i=1 MLPV,1(S)  . (40) By Theorem E.1, it is clear that fV→E(S) is a universal approximator for permutation invariant functions. The same analysis applies to fE→V(S).

heading: F A DISCUSSION OF LEGCN
text: Line expansion (LE) is a procedure that transform a hypergraph or a graph into a homogeneous graph; a node in the LE graph represents a pair of node-hyperedge from the original hypergraph. Nodes in the LE graph are linked if and only if there is a nonempty intersection of their associated node-hyperedge pairs. As stated by the authors of LEGCN (Yang et al., 2020), for a fully connected d-uniform hypergraph their resulting LE graph has Θ(d|E|) nodes and Θ(d2|E|2) edges. This expansion hence leads to very large graphs which require large memory units and have high computational complexity when coupled with GNNs such as GCN. To alleviate this drawback, the authors use random sampling techniques which unfortunately lead to an undesired information loss. In contrast, we define our AllSet layers directly on hypergraph which leads to a significantly more efficient approach.

heading: G HYPERGRAPH PROPAGATION RULES BASED ON THE H EIGENPROBLEM
text: As outlined in the main text, in this case we associate a d-uniform hypergraph G with an adjacency tensor A. The H eigenproblem for A states that
Axd−1 = λx[d−1], where x[d−1]i = (xi) d−1. (41)
Similar to Zprop, we can define Hprop (41) in a node-wise fashion as
Hprop: X(t+1)v,: = ∑ e:v∈e (d− 1) ∏ u:u∈e\v X(t)u,:  1d−1 . (42) Although taking the 1/(d− 1)-th root resolves the unit issue that exists in Zprop (4), it may lead to imaginary features during updates. It remains an open question to formulate Hprop in a manner that ensures that features remain real-valued during propagation.

heading: H ADDITIONAL DETAILS PERTAINING TO THE TESTED DATASETS
text: We use 10 available benchmark datasets from the existing hypergraph neural networks literature and introduce three newly created datasets as described in the exposition to follow. The benchmark datasets include cocitation networks Cora, Citeseer and Pubmed4, obtained from Yadati et al. (2019). The coauthorship networks Cora-CA5 and DBLP-CA6 are also adapted from Yadati et al. (2019). 4 https://linqs.soe.ucsc.edu/data 5 https://people.cs.umass.edu/ mccallum/data.html 6 https://aminer.org/lab-datasets/citation/DBLP-citation-Jan8.tar.bz
In the cocitation and coauthorship networks datasets, the node features are the bag-of-words representations of the corresponding documents. Datasets from the UCI Categorical Machine Learning Repository (Dua & Graff, 2017) include 20Newsgroups, Mushroom and Zoo. In 20Newsgroups, the node features are the TF-IDF representations of news messages. In the Mushroom dataset, the node features represent categorical descriptions of 23 species of mushrooms. In Zoo, the node features are a mix of categorical and numerical measurements describing different animals. The computer vision and graphics datasets include the Princeton CAD ModelNet40 (Wu et al., 2015) and the NTU2012 3D dataset (Chen et al., 2003). The visual objects contain features extracted using Group-View Convolutional Neural Network(GVCNN) (Feng et al., 2018) and Multi-View Convolutional Neural Network(MVCNN) (Su et al., 2015). The hypergraph construction follows the setting described in Feng et al. (2019); Yang et al. (2020).
The three newly introduce datasets are adapted from Yelp (Yelp), House (Chodrow et al., 2021) and Walmart (Amburg et al., 2020). For Yelp, we selected all businesses in the “restaurant” catalog as our nodes, and formed hyperedges by selecting restaurants visited by the same user. We use the number of stars in the average review of a restaurant as the corresponding node label, starting from 1 and going up to 5 stars, with an interval of 0.5 stars. We then form the node features from the latitude, longitude, one-hot encoding of city and state, and bag-of-word encoding of the top-1000 words in the name of the corresponding restaurants. In the House dataset, each node is a member of the US House of Representatives and hyperedges are formed by grouping together members of the same committee. Node labels indicate the political party of the representatives. In Walmart, nodes represent products being purchased at Walmart, and hyperedges equal sets of products purchased together; the node labels are the product categories. Since there are no node features in the original House and Walmart dataset, we impute the same using Gaussian random vectors, in a manner similar to what was done for the contextual stochastic block model (Deshpande et al., 2018). In both datasets, we fix the feature vector dimension to 100 and use one-hot encodings of the labels with added Gaussian noise N (0, σ2I) as the actual features. The noise standard deviation σ is chosen to be 1 and 0.6.

heading: I COMPUTATIONAL EFFICIENCY AND EXPERIMENTAL SETTINGS
text: All our test were executed on a Linux machine with 48 cores, 376GB of system memory, and two NVIDIA Tesla P100 GPUs with 12GB of GPU memory each. In AllSetTransformer, we also used a single layer MLP at the end for node classification. The average training times with their corresponding standard deviations in second per run, for all baseline methods at all tested datasets, are reported in Table 4. Note that the reported times do not include any preprocessing times for the hypergraph datasets as these are only performed once before training. Table 4 lists the average training time per run with the optimal set of hyperparameters obtained after tunning; the average training times per run for different sets of hyperparameters used in the tuning process are reported in Table 5.
Choices of hyperparameters. We tune the hidden dimension of all hypergraph neural networks over {64, 128, 256, 512}, except for the case of HyperGCN and HAN, where the original implementations do not allow for changing the hidden dimension. For HNHN, AllSetTransformer and
AllDeepSets we use one layer (a full V → E → V propagation rule layer), while for all the other methods we use two layers as recommended in the previous literature. We tune the learning rate over {0.1, 0.01, 0.001}, and the weight decays over {0, 0.0005}, for all models under consideration. For models with multihead attentions, we also tune the number of heads over the set {1, 4, 8}. The best hyperparameters for each model and dataset are listed in Table 6. Note that we only use default setting for HAN due to facts that its DGL implementation has all parameters set as constants and its much higher time complexity per run.

Review summaries:
Transferring standard graph operators to the hypergraph setting is non-trivial and several message passing operators have been considered in the setting of hypergraphs, including clique-expansion and tensor based. In this paper the authors propose a general framework where learnable multiset functions are used in order to learn the hypergraph propagation map from the data. In particular, this framework contains  many previously considered propagation maps as particular cases

Hypergraphs can capture group/set relationships in real-world data.  Several hypergraph neural networks have been proposed in the literature to exploit both group relationships among nodes and node features for learning with hypergraph data.  The contributions of the paper are  1) generalisation of most existing methods into a single framework (named AllSet),  2) exploration of AllSet based on Deep Sets [NeurIPS'17] and Set Transformer [ICML'19], and  3) empirical evaluation on existing benchmarks and three curated hypergraph datasets 

The paper proposes a framework for hyper graph neural networks.  It argues that existing work propagates a hyper graph by first transforming it into a regular graph trough clique expansion, which may lose information.  Alternatively, the propagation is based on tensors.  The proposed framework seeks to combine these different ways of propagations into one unified framework.  The proposed framework is called AllSet, with two instantiations AllDeepSets and AllSetTransformer.  Experiments are conducted on several graph datasets.