Totally Dynamic Hypergraph Neural Networks

1 Introduction

Graphs are widely used in real applications including social networking [Berahmand et al., 2021], web search [Wang et al., 2021], and recommendation systems [Wu et al., 2022] since they can efficiently capture relationships among data. However, the construction of the regular graph is based on pairwise relations, which makes it difficult to describe complex relationships. Hypergraphs can handle this problem naturally. The hypergraph is a good alternative to address the above issue by connecting every hyperedge with an arbitrary number of nodes. As a result, the hypergraph is able to capture complex relationships among nodes, and thus having more expressive ability than regular graphs.

∗Corresponding author (seanzhuxf@gmail.com)

This work was supported in part by the National Key Research and Development Program of China under Grant No. 2022YFA1004100.

Previous hypergraph methods can be divided into two categories, i.e., static hypergraph neural networks (SHGNNs) and dynamic hypergraph neural networks (DHGNNs). SHGNNs conduct representation learning by using the initialized hypergraph structure to capture the relatuionships among nodes. To do this, HGNN [Feng et al., 2019] employed the convolution method and HGNN+ [Gao et al., 2022] introduced a spatial-based hypergraph convolution. However, SHGNNs are highly dependent on the initialized hypergraph structure, which usually has redundant information and cannot discover hidden relationships among nodes. To address these issues, DHGNNs were proposed to learn latent connections from features and can mine more useful information. For instance, [Jiang et al., 2019] proposed to reconstruct the hypergraph using both kNN and k-means. [Bai et al., 2021] proposed using continuous values to construct the incidence matrix and the attention mechanism to learn the connection weights. DeepHGSL [Zhang et al., 2022] uses hidden representations in multiple hypergraph convolutional layers to construct the hypergraph. HSL [Cai et al., 2022] samples hyperedges from the initial hypergraph structure (i.e., removing redundant hyperedges) and utilizes attention mechanisms to capture more relationships among nodes and hyperedges for the hypergraph construction.

Previous DHGNNs ignore the adjustment of the number of hyperedges, i.e., hyperedge number, resulting in being unavailable to correctly explore the hypergraph structure. That is, no matter how the nodes are allocated, the hyperedge number is always the same. To address this issue, t-DHL [Gao et al., 2020] attempts to adaptively adjust the hyperedge number by projecting the hyperedge space onto a binary tensor. However, it is a traditional machine learning method and cannot be used in an end-to-end way, thus difficultly exploring the relationship among nodes. Besides, we observe that it is essential for considering the hyperedge features to adjust the hyperedge number. Actually, a hyperedge connects a set of nodes, so that the common information among these nodes (the hyperedge features for short) can be used for characterizing this set of nodes. In contrast, the hyperedge is not necessary if it cannot represent the common characteristics of a set of nodes by a specific measurement, e.g., the attention coefficients between the hyperedge and the nodes in this paper. In this way, the hyperedge number is updated with the hyperedge features. However, the hyperedge features are unavailable for most datasets and few studies focused on considering the hyperedge features for hypergraph neural networks.

To address the above issues, in this paper, we propose a new method, namely, Totally Dynamic Hypergraph Neural Network (TDHNN) shown in Figure 1, to learn dynamical hyperedge features for updating the hyperedge number, including four steps, i.e., hyperedge feature sampling, hyperedge feature update, hypergraph construction, and hypergraph convolution. The first two steps generate the hyperedge features and the third step adjusts the hyperedge number. Hence, the aforementioned issues in previous methods have been explored. In particular, both of the hyperedge features and the hyperedge number are adaptively adjusted with the updated node features. As a result, our method avoids the influence of the low quality of the initial hypergraph.

Different from previous methods, the main contributions of our proposed method are summarized as follows:

• We propose a new end-to-end dynamic hypergraph framework, which can dynamically adjust the hypergraph structure and the number of hyperedges.
• We propose a simple hypergraph convolution algorithm based on the learned hyperedge features.
• We propose a supervised constraint loss and an unsupervised constraint loss to improve the learned hypergraph.

2 Methodology

A hypergraph is defined as G = (V, E,H). V = {v1; v2; ...; vn} is the set of all nodes accompanied by nodes feature matrix Xv ∈ Rn×dn in which feature dimension is dn; E = {e1; e2; ...; em} is the set of all hyperedges, with each hyperedge e ⊂ E constitutes a subset of V [Arya et al., 2020]. Similar to V, E should also have a feature matrix Xe ∈ Rm×de , although this feature matrix is unavailable in most datasets. H ∈ Rn×m is the incident matrix, which implies the topology of the hypergraph. In incident matrix H, each row hi represents the relationship between the i-th node and all hyperedges, hi,j = 1 means there is a connection between the i-th node and the j-th hyperedge, otherwise the opposite. hi,j can also be a continuous value, indicating the connection strength between the i-th node and the j-th hyperedge. Since H implies the topology of a hypergraph, we also use H to denote the hypergraph for simplicity. The degree of a hyperedge ei indicates the number of nodes contained in this hyperedge, denoted by ⌈(ei). In this paper, given a set of nodes V and its feature matrix Xv, our goal is to learn a hyperedge feature distribution P(Xe|Xv) and use this distribution to sample a suitable number of hyperedges to construct a hypergraph H, then use hypergraph convolution to update node features.

2.1 Hyperedge Feature Sampling

Common methods for constructing hypergraphs, such as kNN [Huang et al., 2009], l1-hypergraph [Wang et al., 2015], or constructing hypergraph based on existing graph structures [Fang et al., 2014], all construct hyperedges centered at nodes, which means the number of hyperedges is equal to the number of nodes. As the sample size increases, the number of hyperedges also becomes very large. Not only will it cause many nodes to appear on multiple hyperedges, but it will also reduce computational efficiency. If we have the features of hyperedges in advance and construct hypergraphs centered on hyperedges, we can break the above limitations. However, hyperedge features are unavailable for most datasets, which poses a challenge. To solve this problem, we propose to sample hyperedges from a trainable distribution P(Xe|Xv), and use the relationship between the sampled hyperedges and training samples to update hyperedge features and this distribution. Specifically, we assume that each hyperedge's feature dimension is independent and obeys a trainable Gaussian distribution (Xe)i,j ∼ N(µj , diag(σj )), where µ ∈ R1×de and σ ∈ R1×de . At the very beginning, we randomly initialize this distribution and sample m times to get the initial hyperedge feature matrix Xe ∈ Rm×de . Since the sampling process is discrete and cannot produce gradients, we use reparameterization skill [Kingma and Welling, 2013] to make µ and σ trainable, i.e., we first sample Q ∈ Rm×de from N(0, 1), and then use the following formula to get Xe:

where ⊙ represents the Hadamard multiplication.

2.2 Hyperedge Feature Update

Subsequently, we propose to use the attention coefficient to represent the correlation between each hyperedge and all nodes. Nevertheless, attention can only be computed if the hyperedge features and node features belong to the same feature space [Bai et al., 2021], so we first use a mapping function f(·) to map the input features Xv onto the feature space of the hyperedge features:

Then we adopt the same attention calculation method as Transformer [Vaswani et al., 2017], including q(·), k(·) and v(·) three trainable mapping function:

where Ae ∈ Rm×n is the attention matrix of hyperedges, αei,vj is the attention coefficient of hyperedge ei and node vj. After that, we aggregate the features of the top kn nodes with the highest attention coefficient into the hyperedge:

where MLP (·) is Multi-Layer Perceptron, concate(·) means concatenation. The topkn (·) here means that for each row of Ae, keep the first kn values and set the rest to zero. In this way, we connect µ and σ with the input features Xv. Thus we can use backpropagation to update them. Note that we resample hyperedges at each iteration.

2.3 Hypergraph Construction

Now we have the features of m hyperedges. As mentioned before, building a hypergraph is actually a clustering process, and each hyperedge is equivalent to a cluster centroid. So, we have to put each node into appropriate clusters. From the perspective of clustering, we have the features of the cluster centroids and the features of the samples; the easiest way is to calculate the distance between each sample and each cluster centroid and then divide each sample into the nearest cluster. Nevertheless, from the hypergraph structure and application perspective, a node can be connected to an arbitrary number of hyperedges. For example, in a co-author network, each author can associate multiple works simultaneously. Here we still use the Transformer-like attention method to calculate the attention coefficient between nodes and hyperedges instead of their distances. However, unlike using the hyperedges queries q(Xe) to match the keywords of nodes k( ˆXv) in the previous step, in this step, we use the nodes queries q( ˆXv) to match the hyperedges keywords k( ˆXe):

where Av ∈ Rn×m is the attention matrix of hyperedges, αvi,ej is the attention coefficient of node vi and hyperedge ej . This reverse is because we need to ensure there are no isolated nodes since isolated nodes cannot exchange information from the constructed hypergraph, which may affect the performance of downstream tasks. Then we put each node into the ke hyperedges with the highest attention coefficient:

the topke (·) here means that for each row of Av, keep the first ke values, and set the rest to zero.

Supervised Constraint

To improve the learned hypergraph structure, we designed a supervised constraint function and an unsupervised constraint function. As mentioned above, each hyperedge can be regarded as the centroid of a cluster, and constructing a hypergraph is to divide nodes with the same label into the same cluster. In other words, for any pair of nodes vi and vj with the same label, we hope them to be connected to the same hyperedges. Since the i-th row of the incident matrix H is the connection between the i-node and hyperedges and the H we learned in Eq. (6) is continuous, what we have to do is to minimize the distance between hi and hj , i.e., min d(hi, hj ). From this, we can get the loss function:

where C represents the set of categories of nodes in a dataset, c ∈ C represents a specific category and d(·) is the distance function. Eq. (7) can also be regarded as a kind of contrastive learning using only positive samples.

Adjusting the Number of Hyperedges

Since we learn the distribution of hyperedge features instead of fixed hyperedge features, we can change the number of hyperedges by adjusting the number of samples m. The challenge is that the number of samples is non-differentiable, and we cannot adjust it from backpropagation. From the graph theory perspective, we can solve this challenge if we know what kind of hyperedge and node relationship constitutes an optimal hypergraph. However, this is also a very challenging topic, and there is currently no relevant theoretical research. In order to allow the model to find a better sampling number adaptively, we designed a simple but effective evaluation criterion to judge whether the number of learned hyperedges is appropriate. We define the saturation score of a hypergraph:

where Eempty = {e|e ∈ E, ⌈e = 0} is the set of empty hyperedges in the hypergraph, and SH is the saturation score of the hypergraph H, i.e., the proportion of non-empty hyperedges to all hyperedges. This idea is very intuitive: if there are too many empty hyperedges in a hypergraph, which proves that these hyperedges are redundant, we then reduce the number of samples; at the same time, due to the extreme situation of sampling, it is possible to sample outliers, so we should also allow a few numbers of empty hyperedges. In order to achieve this, we set two hyperparameters β ∈ [0, 1] and γ ∈ [0, 1], which represent the lower and upper limits of saturation score, respectively. After each iteration, we adjust the number of samples according to the saturation score:

2.4 Hypergraph Convolution

Simple Hypergraph Convolutional Layer

We then use the learned hyperedge features and the constructed hypergraph to update the nodes' features. [Feng et al., 2019] proposed the first hypergraph convolution formula:

In Eq. (11), H⊤X(t) v Θ(t) is to multiply the feature matrix of nodes with a weight matrix and then convert it into the feature matrix of hyperedges according to the hypergraph structure. Then it is multiplied by H, which assigns the hyperedge features to each corresponding node again. Since the hyperedge features are sampled from a trainable distribution, we do not need to convert node features to hyperedge features in Eq. (11). Thus the convolution formula can be simplified as:

We first multiply the learned features of hyperedges by a weight matrix Θ ∈ Rde×d and then assign the hyperedge features to each relevant node according to the learned hypergraph structure. Note that at each layer, we reconstruct H according to the current layer's hyperedge and node features.

A previous work [Huang and Yang, 2021] pointed out that self-loops are very important for hypergraph convolution. In a hypergraph, self-loops are hyperedges that contain only one node. If self-loops are not introduced, the representation of a node will only be affected by the features of its neighbor nodes in the previous layer and lose its own features. Therefore, Eq. (12) can be modified as:

where ˜H(t) = concat(H(t) ,H′ ) ∈ Rn×(m+n) , H′ ∈ Rn×n is a diagonal incident matrix in which each node vi belongs to only one hyperedge ei with degree ⌈(ei) = 1. Since there is only one node in the hyperedge of the self-loop, we can directly regard the features of the node as the hyperedge features, i.e., ˜X(t) e = stack(X(t) e , ˆX(t) v ) ∈ R(m+n)×de . However, instead of taking the form of Eq. (13), our final convolution formula is:

where w is a trainable parameter. That is, we add the features of nodes themselves on the basis of Eq. (12). In fact, Eq. (14) is equally valid and more computationally efficient than Eq. (13).

Unsupervised Constraint

We use the labeled nodes to get the supervised constraint and hope that the nodes with the same label would be divided into the same hyperedge; similarly, for the unsupervised constraint, we hope that the nodes divided into the same hyperedge would be more similar. In the supervised stage, our constraint loss was directly applied to H, and in the unsupervised stage, we added a constraint on node features after the convolutional layer:

Finally, we evaluate our model on the node classification task, so the final loss function is:

where Le is the empirical loss of node classification, and λ1 and λ2 are trade-off hyperparameters.

2.5 The Connection and Difference with k-means

The way we construct a hypergraph is similar to k-means. The primary process of k-means is (1) randomly selecting cluster centroids, (2) clustering, (3) updating the cluster centroids, then repeating (2) and (3) until convergence. The pipeline of the proposed TDHNN is (1) sampling hyperedges, (2) assigning nodes to each hyperedge, (3) updating the feature distribution of hyperedges, then repeating (2) and (3) until convergence. The main differences between our method and k-means are as follows:

• k-means learns features of cluster centroids, while TDHNN learns the feature distribution of hyperedges;
• k-means selects fixed k cluster centroids, while TDHNN dynamically adjusts the number of samples according to the saturation score of the learned hypergraph;
• Each cluster in k-means is disjoint, while TDHNN has intersections between hyperedges.

3 Experiments

3.1 Experimental Settings

Datasets

Following the work of the first hypergraph convolutional neural network [Feng et al., 2019], we use two visual object classification datasets (i.e., Princeton ModelNet40 [Wu et al., 2015] and National Taiwan University 3D model (NTU for short)). Among them, ModelNet40 contains 12, 311 objects with 40 types, and NTU contains 2, 012 objects with a total of 67 types of 3D shapes. Like [Feng et al., 2019], we use Group-View Convolutional Neural Network (GVCNN) [Feng et al., 2018] and Multi-view Convolutional Neural Network (MVCNN) [Su et al., 2015] for feature extraction and consider the case of using one set of features separately and using two sets of features at the same time. We adopted the same split standard for ModelNet40 and NTU, i.e., 80% as the training set and 20% as the testing set. Since the standard split of a dataset uses fixed training samples, a method may be affected by the fixed data distribution. For better comparison, we use the same method as [Jiang et al., 2019] to randomly sample different proportions of the data on Cora [Veliˇckovi´c et al., 2017] as the training set. Specifically, in addition to the standard split, we respectively select 2%, 5.2%, 10%, 20%, 30%, and 44% of the data to train.

Comparison Methods

Our comparison methods include two classic graph models, i.e., GCN [Kipf and Welling, 2016] and GAT [Veliˇckovi´c et al., 2017]; three hypergraph convolutional neural networks, i.e., HGNN, HGNN+, and HNHN [Dong et al., 2020]; and two dynamic hypergraph networks, i.e., DHGNN, HyperGCN [Yadati et al., 2019], DeepHGSL [Zhang et al., 2022] and HSL [Cai et al., 2022]. We implement GCN and GAT by the open tool PyTorch Geometric [Fey and Lenssen, 2019], and we implement HGNN, HGNN+, HNHN, HyperGCN and DeepHGSL by the open tool DHG (DeepHypergraph) [Gao et al., 2022]. For DHGNN and HSL, we use their source code for experiments.

Setting-up

We uniformly set the feature dimension of the hyperedge de to 128 and the initial sampling number of the hyperedge m to 100. The number of nodes used to update the hyperedge features and the number of hyperedges each node belongs to are set to 10. For the hypergraph saturation score, we set the lower limit β to 0.9, and the upper limit γ is set to 0.95. We used dropout [Srivastava et al., 2014] to prevent overfitting and set the drop rate to 0.2. The optimizer we use is Adam [Kingma and Ba, 2014], and the learning rate is 0.001.

3.2 Result and Discussion

Visual Object Classification

The experimental results of visual object classification are shown in Table 1. The proposed TDHNN achieves the best results among all comparison methods, regardless of the set of features used, both on ModelNet40 and NTU. Compared with graph algorithms GCN and GAT, TDHNN has an average increase of 2.82% and 2.88%, respectively. Compared with the static hypergraph algorithms HGNN, HGNN+, and HNHN, TDHNN has an average improvement of 1.33%, 1.6%, and 2.12%, respectively. Compared with dynamic hypergraph algorithms DHGNN, HyperGCN, DeepHGSL and HSL, our classification accuracy has averagely increased by 2.22%, 2.77%, 6.25% and 1.95% respectively. In general, hypergraph algorithms outperform graph algorithms on ModelNet40 and NTU. However, some algorithms show instability in the experimental results. For example, when HNHN uses the features of GVCNN and MVCNN on ModelNet40, respectively, it shows high accuracy (92.10% and 91.10%, respectively). However, the accuracy improvement is not obvious when fusing these two sets of features simultaneously (93.80%). Compared with other methods, it is even lower, and a similar situation occurs at NTU. When DHGNN uses the features of MVCNN alone, the accuracy is relatively low, whether it is on ModelNet40 or NTU, but it achieves good grades when fusing these two sets of features. In sharp contrast to these two methods, TDHNN has achieved better results, showing better stability and compatibility, whether using a specific feature alone or fusing two sets of features simultaneously.

Overall, the proposed TDHNN has three advantages: first, by applying the hypergraph structure, we can better mine the multi-relationships in the data; second, we dynamically learn the hypergraph structure, which can fully mine the potential relationships in the data; third, we can dynamically adjust the number of hyperedges to help learn a more reasonable hypergraph structure.

Citation Network Classification

The experimental results of experiments on Cora using different proportion samples are shown in Table 2. As is shown, TDHNN has achieved the best results except for the 2% split, which is 76.11% second to DHGNN (76.90%) with a gap of 0.8%. Compared with graph algorithms GCN and GAT, TDHNN has an average increase of 4.11% and 1.57%, respectively. Compared with the static hypergraph algorithms HGNN, HGNN+, and HNHN, TDHNN has an average improvement of 3.14%, 4.37%, and 6.18%, respectively. Compared with dynamic hypergraph algorithms DHGNN, Hyper- GCN, DeepHGSL, and HSL, our classification accuracy has averagely increased by 1.07%, 17.38%, 2.86% and 3.09% respectively. Specifically, under the split of 2% and 5.2%, HGNN, HGNN+, and our TDHNN have achieved relatively similar performance. However, with the increase of the training ratio, the advantage of TDHNN is revealed, which might be attributed to the supervised constraint loss Ls.

3.3 Ablation Study

The proposed TDHNN has three main components, a hyperedge updater (HU for short), supervised constraints (C1 for short), and unsupervised constraints (C2 for short). To demonstrate the effectiveness of each part, we tested different combinations of these components. As shown in Table 3, first, TDHNN has an average increase of 1.22%, 3.75%, and 3.13% on ModelNet40, NTU, and Cora compared to using only a single component, respectively. In the case of only using HU, the performance of the model at each dataset is acceptable, especially on ModelNet40 (97.28%), which is close to using all components. In the case of using only C1, the overall performance drops a lot on ModelNet40 (94.24%) and NTU (77.74%), but it is slightly better on Cora than using only HU (increased by 0.3%). When only using C2, ModelNet40 also performed very well (97.36%), and it was also better than using only HU or C1 on Cora. When any two components are used in combination, the overall performance is not significantly improved compared with using a single component. Specifically, when combining C1 and C2, the model cannot even converge on ModelNet40 and NTU (the classification accuracy is 7.86% and 6.43%, respectively). However, when combining all these components, the model's performance achieves the best, and the case of non-convergence does not exist anymore.

3.4 Visualizations

In order to better show the ability of TDHNN, we use the tSNE algorithm [Van der Maaten and Hinton, 2008] to reduce the dimensionality of the embedding of the model and visualize it. We also calculate the Silhouette score [Rousseeuw, 1987] of the embedding to evaluate it. We perform the same experiment on HGNN+ and HNHN for comparison. The experimental results are shown in Figure 2. As is shown, in the experimental results of TDHNN, the boundaries of categories are clearer. The Silhouette scores also prove this point, where the Silhouette score of HGNN+ and HNHN are 0.3531 and 0.3344, respectively, while TDHNN is 0.5081, which is 15.50% and 17.34% higher than the previous two methods.

3.5 Running Time

In order to demonstrate the computational efficiency of TDHNN, we compared the time required for each iteration with the latest dynamic hypergraph methods. As shown in the Table 4, TDHNN improved by an average of 9.44 seconds, 3.01 seconds, and 2.31 seconds per epoch compared to DHGNN, HyperGCN, and DeepHGSL on three datasets. Compared to HSL, TDHNN is on average 0.04 seconds slower, that is because HSL samples and obtains new structures from existing hypergraph structures rather than using features for reconstruction. In addition, we did not compare TDHNN with static methods as they did not reconstruct hypergraphs.

3.6 Sensitivity Analysis

Effect of Hypergraph Saturation Threshold

We tested the effect of setting the saturation threshold on the model on ModelNet40 and NTU. We set the lower threshold β from 0.1 to 0.9 with a step size of 0.1 and the corresponding upper threshold γ = β + 0.05. According to the experimental results, on ModelNet40, with the change of β and γ, the model's accuracy has almost no change. On NTU, the model's accuracy fluctuates slightly with the change of threshold; the model reaches its best at the point β = 0.9, but overall the difference is not much. The result shows that the learned hypergraph indeed has a large number of redundant edges. Although these redundant hyperedges do not affect the model's accuracy, they add many unnecessary calculations, reducing the computational efficiency. Thanks to our strategy of dynamically adjusting the number of hyperedges, our model can control the number of redundant hyperedges by setting a threshold, thus reducing the computational overhead. Specifically, considering the convolutional operation H(t)X(t) e Θ(t) in Eq. (12), the time complexity is O(n × m × de) + O(n × de × d) = O(nm). When using a traditional method such as kNN to generate a hypergraph, the number of hyperedges m is equal to the number of nodes n, then the time complexity is O(n2 ). In contrast, the proposed TDHNN sets m as a constant, and the model optimizes this constant at each iteration so that the time complexity of convolution is reduced to O(n).

Trade-off between Two Constraints

In order to make the learned hypergraph better, we set a supervised constraint and an unsupervised constraint. How to set the weight of these two constraints is a question worth discussing. We conducted experiments on ModelNet40 and NTU, respectively, and set λ1 and λ2 from 10 to 100 with a step size of 10. It can be concluded that: (1) TDHNN is less sensitive to λ1 and λ2 since as λ1 and λ2 change, the variance of TDHNN's accuracy within each data distribution tested is relatively low; (2) for different data distributions, the influence of λ1 and λ2 is different, i.e., the trade-off of λ1 and λ2 depends on the dataset.

4 Conclusion

In this paper, we propose a novel dynamic hypergraph learning framework that can dynamically adjust both the structure of the hypergraph and the number of hyperedges. As far as we know, this may be the first work that constructs hypergraphs centered on the features of hyperedges, and it opens up a new way for the research and learning of hypergraph neural networks. The proposed TDHNN learns the feature distribution of hyperedges and adjusts the number of samples according to the saturation score of the learned hypergraph to dynamically adjust the hypergraph structure. To make the constructed hypergraph more reasonable, we propose two constraints on the graph and features after convolution. Experiments demonstrate the effectiveness of our method. However, this method also has many aspects that can be improved. For example, the measurement of hypergraph saturation and the strategy of adjusting the number of hyperedges may be too simple; the relationship between the number of hyperedges and samples has yet to be further explored and theoretically proved. It is also the direction we need to continue in-depth research and exploration in the future.

Contribution Statement

Zongqian Wu made equal contributions to this work. He was involved in the overall design of the method, conducted comparative experiments, contributed to chart design, and participated in some writing tasks.