Hypergraph Structure Learning for Hypergraph Neural Networks

1 Introduction

Graphs are ubiquitous across the real world and Graph Neural Networks (GNNs) [Kipf and Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018] have shown superiority in modeling the graph structure and node features. Since graphs only capture the pairwise relationship among entities, it is desirable to capture high-order interactions to learn effective node representations. The hypergraph, where each hyperedge can connect any number of nodes, can encode high-order relationships and has drawn increasing attention from many fields such as recommendation systems [Yu et al., 2021] and computer vision [Gao et al., 2020]. A series of Hypergraph Neural Networks (HGNNs) [Chien et al., 2021; Huang and Yang, 2021; Feng et al., 2019], which generalize GNNs to hypergraphs, has been proposed based on different message passing schemes.

∗Contact Author

Most HGNNs follow a two-stage message passing scheme, i.e., iteratively update hyperedge representations by aggregating nodes' information and then update the node representations by aggregating incident hyperedges' information. The message passing process of these methods relies on the input hypergraph structures. Hence, the hypergraph structure is crucial for HGNNs to learn expressive node representations. Most existing HGNNs simply presume that the hypergraph structure is perfect, which is not always true. Specifically, the quality of hypergraph structures needs to be improved in the following 3 aspects.

• Firstly, the hypergraph structures may contain taskirrelevant information, noise, or even mistakes, which are unnecessary information and need to be removed.
• Secondly, the hypergraph structures may contain falsenegative connections, i.e., some nodes should be included in certain hyperedges but they are not. The implicit connections, which describe the underlying relationships and can be viewed as an enhancement of the original structure, are also important and need to be included in the hypergraph.
• Finally, the hypergraph structures may not be ideal for the downstream tasks since the raw structure only describe the relations among nodes from the input feature space. It may fail to reflect relations among nodes from high-level feature space. In addition, some connections in the hypergraph can be discarded while others need to be emphasized depending on the downstream tasks.

Therefore, it is important to jointly optimize the hypergraph structure and the HGNNs towards downstream tasks. The hyperedge and node representations learned by HGNNs provide information for learning better hypergraph structures. The newly learned hypergraph structures, in return, serve as the input of HGNNs to learn better hyperedge and node representations.

Although hypergraph structure learning is important, it is challenging and unexplored. Many graph structure learning methods have been proposed to adaptively learn graph structures for GNNs. Unlike the graph structure learning problem where only pair-wise relationships are considered, we need to model high-order relationships in hypergraphs and update the structure where a hyperedge may connect any number of nodes. Due to the complexity and the inherent nature of hypergraphs, these methods can not be directly applied to hypergraphs.

In this work, we present a Hypergraph Structure Learning (HSL) framework for HGNNs, aiming at jointly learning the hypergraph structure and the HGNNs that are optimized towards the downstream tasks. Specifically, we propose a twostage sampling process for learning the hypergraph structures. In the first stage, the hypergraph structures are adjusted at a coarse-grained level via hyperedge sampling. In the second stage, the hypergraph structures are adjusted at a fine-grained level via incident node sampling. Potential implicit connections are discovered based on the hyperedge and node representations learned by HGNNs in this stage. The discrete sampling processes are differentiable with the help of the Gumbel Softmax trick. To maintain the consistency between the optimized hypergraph structure and the original input structure, intra-hyperedge contrastive learning is proposed to maximize the mutual information between the node representations from different hypergraph structures. These three modules, together with the backbone HGNNs, play a synergistic effect in learning better hypergraph structures and HGNNs. Experimental results on a variety of datasets demonstrate the effectiveness of our design. The contribution of this work can be summarized as follows:

• To the best of our knowledge, this is the first work to jointly optimize the discrete hypergraph structure and HGNNs in an end-to-end way, such that our method has comparable or better performance and induces sparsified hypergraph structures.
• The proposed HSL, which consists of hyperedge sampling, incident node sampling, and intra-hyperedge contrastive learning, provides a framework for jointly optimizing the hypergraph structures and HGNNs.
• The extensive experiments conducted on 7 datasets show that HSL outperforms the state-of-the-art HGNNs while adaptively sparsifying hypergraph structures according to downstream tasks.

2 RelatedWork

2.1 Hypergraph Neural Networks

Graphs have limitations for representing high-order relationships. In a hypergraph, the complex relationships are encoded by hyperedges that can connect any number of nodes. [Zhou et al., 2006] introduced hypergraph to model high-order relations for semi-supervised classification and clustering of nodes. Recent works [Feng et al., 2019; Yadati et al., 2019; Bai et al., 2021] have designed different message passing strategies and have shown superiority in higher-order representation learning for graphs. [Feng et al., 2019] proposes the first HGNN method, which uses the clique expansion to transform hypergraphs to graphs and applies graph embedding techniques. UniGNN [Huang and Yang, 2021] proposes to unify hypergraph and GNN models using hypergraph star expansion. Many variations of GNNs can be incorporated in UniGNN. [Chien et al., 2021] proposes a general HGNN framework that implements HGNN layers as compositions of two multiset functions and covers propagation methods of most existing HGNNs.

2.2 Graph Structure Learning

Many graph structure learning methods have been proposed to learn ideal graph structures for GNNs [Zhu et al., 2021; Franceschi et al., 2019; Chen et al., 2020b; Luo et al., 2021; Zheng et al., 2020]. Some of these methods directly optimized the adjacency matrix with certain constraints such as low-rank, sparsity, and smoothness. Other methods model the existence of the edge as a metric function between pairwise nodes or a certain distribution.

Hypergraph structure learning is relatively under-explored. DHSL [Zhang et al., 2018] simultaneously optimizes the label projection matrix and the hypergraph structure iteratively, but it neither scale to large hypergraphs nor utilizes highlevel representations. DHGNN [Jiang et al., 2019] uses KMeans and KNN to adaptively construct hypergraph, which is not optimized along with the HGNNs in an end-to-end way. HERALD [Zhang et al., 2021] optimize hypergraph Laplacian matrix instead of the discrete hypergraph incidence matrix, which means it can not be easily combined with the general HGNNs framework based on two-stage message passing.

3 Method

As illustrated in Figure 1, we present Hypergraph Structure Learning (HSL) framework for HGNNs. Inspired by the inherent properties of hypergraphs, the hypergraph structure learning process can be viewed as a two-stage sampling process: hyperedge sampling and incident node sampling. Leveraging the idea that the node representations learned from the original hypergraph and optimized hypergraph should be consistent, intra-hyperedge contrastive learning is applied.

3.1 ProblemDefinition

In this paper, we focus on the node classification task on hypergraphs, which map each node to a set of labels. Let G = (V, E) denote the hypergraph with node set V and hyperedge set E. Each hyperedge e ∈ E is a subset of V. Let N = |V| denotes the number of nodes and E = |E| denotes the number of hyperedges. Ni = {e ∈ E|i ∈ e} denotes the incident hyperedges of node i. The incident matrix represents the hypergraph structure and is denoted as H ∈ {0, 1}N×E , where Hij = 1 indicates that hyperedge j contains node i. The input node features are denoted as X ∈ RN×dv , where dv is the dimension of node features. The goal of node classification on hypergraphs can be formulated as learning an HGNN F(X,H) mapping hypergraph structure and node features to node labels. The goal of hypergraph structure learning is to learn the HGNN F(X, ˆH) and optimal hypergraph structure ˆH simultaneously.

3.2 HGNNs

HGNNs can be viewed as a two-stage message passing procedure [Huang and Yang, 2021; Chien et al., 2021], which can be formulated as follows.

fV→E and fE→V are two permutation-invariant functions which aggregating information from nodes and hyperedges respectively. In the first stage of message passing, node representations {xk}k∈ej within each hyperedge are aggregated by fV→E to form hyperedge representation hj. In the second stage, the node representations xi are updated with its incident hyperedges {hk}k∈Ni using fE→V.

Recent works on HGNN have proposed many implementations for fV→E and fE→V. HSL adopts AllSetTransformer [Chien et al., 2021] as the backbone network since it is a general and expressive framework of HGNNs.

3.3 Hyperedge Sampling

Inspired by the nature of hypergraph, HSL firstly performs hyperedge sampling to filter out task-irrelevant hyperedges. As a hyperedge can connect any number of nodes, hypergraph structure learning is performed in a coarsen-grained level in this stage. To sample hyperedges, we introduce a binary mask vector m ∈ {0, 1}E , with mi denotes the existence of the hyperedge i. Each binary number mi is considered to be drawn from a Bernoulli distribution, parameterized by zei , i.e., mi ∼ Bern(zei ). ze ∈ [0, 1]E , the Bernoulli distribution parameter vector for hyperedges, is trainable parameters and is optimized jointly with the downstream task. Since it describes the importance of each hyperedge, a small value of zei indicates that the hyperedge i is likely to be noise and should be removed.

The discrete sampling process is not differentiable. To support a learnable and discrete sampling process, HSL applied the Gumbel Softmax trick [Maddison et al., 2017;

Jang et al., 2017] for gradient approximation. For each hyperedge i, the Gumbel Softmax is applied to generate the differentiable binary mask mi. ϵ0 , ϵ1 is Gumbel random noise sampled from Gumbel(0, 1) and τ is the temperature of the softmax distribution. σ denotes the sigmoid function.

With the sampling mask m, the incident matrix ˜H of the hypergraph structure after hyperedge sampling can be formulated as follows. Γ : RE → RN×E denotes the broadcasting operator, which repeats the mask vector m for N times to construct a binary mask matrix Me ∈ RN×E for hyperedge sampling. ⊙ denotes the Hadamard product.

3.4 Incident Node Sampling

In the hyperedge sampling stage, unnecessary hyperedges are pruned. In this stage, hypergraph structure learning is performed at a fine-grained level. Incident node sampling aims at refining the hypergraph structure via removing irrelevant nodes from hyperedges and adding potential nodes to hyperedges.

Before sampling incident nodes, the input hypergraph structure can be enhanced if the implicit connections between nodes and hyperedges are discovered. The default fixed hypergraph structure is possibly noisy with missing falsenegative connections. To learn the implicit connections, it is necessary to augment the ˜Hwith a residual hypergraph structure ∆H. Based on the node representation ˜x and the hyperedge representation h extracted by HGNNs, we can find the most similar node-hyperedge pairs, which are potential connections with a high possibility. Let S ∈ RN×E denote the similarity matrix between nodes and hyperedges. To increase the expressive power, HSL adopted the multi-head weighted cosine similarity as the metric function. The similarity is computed as the average of nc independent similarity scores using nc weight vectors {wi}nc i=1 .

To reduce the expensive computation and noise, the residual hypergraph structure ∆H is sparsified via a threshold padd, which denotes the proportion of the connections (the number of non-zero values in the incident matrix) between the residual hypergraph structure ∆H and original structure H. Specifically, the connections between nodes and hyperedges are selected according to the largest values in the similarity matrix S at the ratio padd. Since the residual hypergraph structure ∆H aims at discovering implicit connections using learned node and hyperedge representations, the original connections in the input hypergraph structure are not included in ∆H. Let top(S, padd) denote the function which select the largest items in the matrix S according to the ratio padd. The computation of ∆H can be formulated as follows.

H + ∆H represent the enhanced hypergraph structure, which includes the original connections and possible implicit connections. To further refine the hypergraph structure, HSL performs incident node sampling based on the enhanced hypergraph structure H+∆H. Similar to hyperedge sampling, we introduce a binary mask matrix Mv ∈ RN×E for incident node sampling. Each binary number of Mvij is also considered to be drawn from a Bernoulli distribution, parameterized by Zvij . Zv ∈ [0, 1]N×E denotes the Bernoulli distribution parameter matrix. A small value of Zvij indicates that the connections between hyperedge j and node i are more likely to be unnecessary and node i should be removed from hyperedge j. Zv is computed by an MLP taking node and hyperedge representations as inputs. In other words, the semantic information from node and hyperedge representation is utilized to decide the existence probability of the connections between nodes and hyperedges.

To support the differentiable Bernoulli sampling process, the Gumbel Softmax trick is applied for binary mask matrix Mv , which can be obtained via

After performing incident node sampling with mask matrix M v , the final hypergraph structure ˆH can be obtained via

A Previous study [Huang and Yang, 2021] points out that self-loops are crucial in HGNNs and the performance drop significantly for most datasets when the hypergraph is unself-looped. In the data preprocessing stage, self-loops are added to the hypergraphs where each self-loop only contains one node. The rationale is that the self-loops provide a shortcut to perform message passing only using the representation of the target node in the previous layer. If the self-loop of a certain node is missing, the representation of that node may be easily misguided by neighborhood nodes. The model degenerates to MLP if the hypergraph only contains self-loops and every node is isolated. To enhance the expressive power of the model, the self-loops should not be included in both of the sampling processes. Since the self-loops are included in the hypergraph, the number of hyperedges E should be greater or equal to the number of nodes N. Let the last N hyperedges {ei}Ei=E-N denote the self-loops. I ∈ {0, 1}N×E denotes the incident matrix of all the self-loops. The final hypergraph structure ˆH can be formulated as follows.

3.5 Intra-Hyperedge Contrastive Learning

To maintain the consistency between the original hypergraph structure H and the altered structure ˆH, intra-hyperedge contrastive learning is proposed. On the one hand, the node representations extracted by HGNNs based on H and ˆH should maintain the same or similar semantic information. On the other hand, the message passing scheme may result in an over-smoothing issue [Li et al., 2018] and the representations of the node in the same hyperedge should be distinguishable from each other. The node representations extracted by HGNNs based on H and ˆH are different views of the same node and they should be consistent. Intra-hyperedge contrastive learning is applied to minimize the distance between the representations of the same node from differents views and maximize the distance between the representations of different nodes in the same hyperedge.

Let ˆx, x denote the node embedding from hypergraph structure ˆH,H respectively. Ti = {j ∈ e|e ∈ Ni} denote the set of neighbour nodes which are in the same incident hyperedges as node i. HSL follows SimCLR [Chen et al., 2020a] and adopts the InfoNCE loss [Gutmann and Hyv¨arinen, 2010], which maximize the mutual information between the node representation from different views. Let ϕ denotes the similarity function for contrastive learning, which is implemented as cosine similarity. The intra-hyperedge contrastive loss LCL is formulated as follows.

The hyperedge sampling and incident node sampling process are implemented by mask matrix Me and Mv respectively. Let λ denotes the hyper-parameter balancing the crossentropy loss function LT and the intra-hyperedge contrastive loss LCL. The sampling processes are jointly optimized with the loss function of the downstream task LT during training.

The final training objective L can be formulated as follows.

4 Experiments

4.1 Experimental Setups

To evaluate the effectiveness of HSL, experiments are conducted on 7 public datasets: Cora, Citeseer, Coauthor-Cora, Coauthor-DBLP [Yadati et al., 2019; Rossi and Ahmed, 2015; Sen et al., 2008], NTU2012 [Chen et al., 2003], 20Newsgroups [Zhou et al., 2006]. The statistics of the datasets are shown in Table 2. In Citeseer and Cora dataset, the coauthorship hypergraphs are constructed where a hyperedge connects all documents co-authored by one author. In Coauthor-Cora and Coauthor-DBLP dataset, the co-citation hypergraphs are constructed where a hyperedge connects all documents cited by an author.

HSL is compared against 6 baseline models: (1) MLP: Only using the node feature as input and ignoring the hypergraph structure, (2) DHGNN [Jiang et al., 2019]: Dynamic Hypergraph Neural Networks, a method using KNN and K-Means to adaptively update hypergraph structure, (3) CEGAT: Using clique-expansion to transform hypergraphs to graphs and applying GAT [Velickovic et al., 2018], (4) HGNN [Feng et al., 2019]: Hypergraph Neural Networks, (5) UniGCNII [Huang and Yang, 2021], (6) AllSetTransformer [Chien et al., 2021].

We perform semi-supervised node classification tasks in the transductive setting on these datasets. In the semisupervised node classification task, the labels for the test nodes are predicted by HGNNs based on the hypergraph structure, the input features of all nodes, and limited node labels for training. The datasets are randomly split into the training, validation, and test set in a 0.5:0.25:0.25 ratio. The experiments are repeated with 20 random data splits. The number of HGNN layers is set to 1. We use the Adam optimizer with a learning rate tuned over {0.001, 0.0001} on the validation set. The hidden dimension of HGNNs on different datasets is tuned over {64, 128, 256, 512}. The hyperparameter padd for enhancing hypergraph structure is tuned over {0, 0.01, 0.02, 0.05}. All programs are implemented using the Pytorch Geometric library (PyG) [Fey and Lenssen, 2019] with PyTorch 1.8 on an Nvidia RTX 3090 GPU.

4.2 Experimental Results

The Accuracy of the Node Classification tasks. The performance of all methods is summarized in Table 1. The experimental results show that HSL has the best overall performance when compared to the state-of-the-art. With the structure learning modules, HSL effectively optimizes the hypergraph structure. The HGNNs can learn better node representations from better hypergraph structure, leading to better performance on the downstream node classification tasks. The expressive ability of methods that use fixed hypergraph structure as input (CEGAT, HGNN, UniGCNII, AllSetTransformer) is limited by the hypergraph structure which is not suitable for downstream tasks. DHGNN [Jiang et al., 2019] applied KNN and K-Means to dynamically adjust the hypergraph structure. It achieves promising accuracy on Cora and Citeseer dataset, but its performance is not desirable on other datasets. DHGNN is not optimized in an end-to-end way and the degree of the hyperedges or nodes is fixed according to a pre-defined hyper-parameter k, which greatly hinders the representation ability of the model. Jointly optimized with the downstream task, our proposed HSL can dynamically adjust the hypergraph structure with no constraint on the degrees or neighbors of the hyperedges and nodes.

The Pruning Rate of the HSL. To further examine the effect of the HSL, we compute the pruning rate rv of the learned hypergraph structure ˆH. rv denote the sparsity of the optimized hypergraph structure ˆH compared with the original hypergraph structure H, i.e., the ratio between the number of non-zero values in ˆH and H. As shown in Table 1, HSL can effectively sparsify the input hypergraph structure while achieving the best performance at the same time, indicating that HSL can keep the most task-relevant and informative part of the hypergraph structure. HSL achieves the average pruning rate of 59.7% and 11.31% for the Citeseer dataset. Noticed that the gap in the performance between the MLP and other hypergraph-based methods is narrow (smaller than 1%) for some datasets such as Citeseer, 20Newsgroups. It indicates that the hypergraph structures are not helpful to these HGNNs on the downstream task. Taking the fixed input hypergraph as ground truth may result in sub-optimal performance. HSL can dynamically adjust the hypergraph structure and prune the unnecessary hyperedges and connections, balancing the accuracy and the sparsity. In the Citeseer and 20Newsgroups datasets, the gap between MLP and hypergraph-based methods is the smallest. HSL achieves the highest pruning rate in those two datasets.

(b) 20Newsgroups

Figure 2: The performance of HSL and AllSetTrasnformer on randomly corrupted Cora and 20Newsgroups datasets.

Robustness Against Noisy Datasets. To evaluate the robustness of HSL to hypergraphs with noisy or missing connections, we construct hypergraphs where nodes are randomly added to or removed from hyperedges. We choose AllSetTransfomer as the baseline model. Experiments are conducted on different levels of noise, ranging from -100% to 100%. -100% means removing all the connections between hyperedges and nodes and 100% means adding the same number of connections as the original hypergraph structure. As shown in Figure 2, HSL outperforms AllSetTransformer at a different level of noise.

Figure 3: Ablation Study.

Ablation Study. We analyze the influence of hyperedge sampling, incident node sampling, and intra-hyperedge contrastive learning modules of our proposed HSL. As shown in Figure 3, all of the three modules contribute to the performance. The following 3 variations of HSL are compared: (1)Base: The backbone HGNN without any hypergraph structure learning modules, (2)+edge: The backbone HGNN combined with hyperedge sampling module, (3)+node: The backbone HGNN combined with incident node sampling module, (4)-CL: HSL without the intra-hyperedge contrastive learning module. All of these modules are important. The hyperedge sampling module aims at learning the hypergraph structure at a coarse-grained level while the incident node sampling module aims at learning the hypergraph structure at a fine-grained level. The intra-hyperedge contrastive learning module plays an important role in maintaining the consistency between the optimized structure and the original structure. These three modules play a synergic effect to achieve the best performance.

(a) Base. Acc: 73.11%

(b) HSL. Acc: 73.79%

Figure 4: Visualization of the hypergraph structure optimized by HSL and the original hypergraph structure using star expansion. The blue dots denote the node while the red dots denote the hyperedges. The edge denotes the connection between hyperedges and notes.

Visualization. We visualized the hypergraph structure optimized by HSL and the original hypergraph structure using star expansion. On the Citeseer dataset, HSL achieves a pruning rate of 11.31%. As shown in Figure 4, HSL significantly condenses the hypergraph structure while achieving better accuracy, indicating that HSL effectively prunes task-irrelevant connections and hyperedges.

5 Conclusion

Recently, many variations of HGNNs have been proposed, generalizing GNNs to hypergraphs. HGNNs are capable of capturing higher-order relationships among entities and have achieved great success in many applications. However, the hypergraph structure on which HGNNs rely may not always be ideal. It may contain noise, task-irrelevant information, or false-negative connections. In this paper, we propose HSL, which consists of a hyperedge sampling module, incident node sampling module, and intra-hyperedge contrastive learning module, for jointly learning hypergraph structure and HGNNs. Unnecessary hyperedges and connections between hyperedges and nodes are pruned. In addition, hypergraph structures are enhanced by learning potential implicit connections. Extensive empirical studies demonstrate the superiority of our model.