Introduction

Graphs can represent the relationships between real world factors and play an important role in many fields1,2. Graph Neural Networks (GNNs) have shown outstanding performance in citation network3, social networks4, and recommendation systems5. However, graphs cannot describe the relationships between elements for some higher-order complex systems6, which makes GNNs inefficient in learning system’s higher-order information. Therefore, researchers have proposed a method that can describe higher-order relationships, i.e., the hypergraph7. Numerous works have shown that the hypergraph is more advantageous than the common graph in modeling complex relationships. Specifically, the graph represent only binary relationships, i.e., each edge connects two nodes. Hypergraphs are able to represent multivariate relationships, allowing a single hyperedge to connect multiple nodes, which enables hypergraphs to more naturally model complex relationships in the real world, such as groups in social networks8 and multiple user-item interactions in item recommendation systems9. For example, in a collaborative network of scientists, where nodes represent scientists, a graph can only represent a collaborative relationship between two scientists and cannot represent a relationship between multiple scientists. In hypergraphs, the relationships of multiple collaborators in a paper can be represented using hyperedges (edges in a hypergraph are called hyperedges), i.e., a paper that is a collaboration of K scientists can be represented by a hypergraph containing K nodes. In addition, the topology of hypergraphs is more flexible and can accommodate complex data relationships and hierarchical structures. For datasets with multi-level or multi-dimensional relationships (e.g., biological networks10, knowledge graphs11, etc.), hypergraphs can better capture these complex relationships.

In recent years, Hypergraph Neural Networks(HGNNs) based on the hypergraph have also emerged12,13. HGNNs have achieved remarkable results in node classification14, graph classification and link prediction tasks, in addition to satisfactory results in computer vision15, biology16 and chemistry17.

In addition to traditional deep models that are easy to fail under attacks18,19,20,21, deep models based on graph are also fragile22,23. For example, in a fraud detection system, a fraudulent user can escape system detection by adding connections to other high-credit users, which can lead to serious consequences. Therefore, researchers have proposed many graph adversarial attacks to study the robustness of GNNs24,25. Graph adversarial attacks can be classified into targeted and untargeted attacks based on the goal of the attack26. In the targeted attack, the attacker focuses on the classification of some test nodes27. The attack misclassifies the target nodes into the specified label indicating the success of the attack. In the untargeted attack, the attacker usually focuses on global test nodes classification and the attack succeeds when the test nodes are misclassified28. In the untargeted attack, the attacker does not need to know the target label in advance and can categorize to any wrong label, which makes the attack more flexible and adaptable. Targeted attacks are aimed at a specific label, which are more stringent and require more attack resources. In addition, the untargeted attack make it more difficult for the model to establish detection and defense mechanisms against the attack, thus increasing the likelihood of a successful attack. The targeted attack makes the attack tend to operate on users with higher privileges, which can be easily detected by the defense model. Therefore, the untargeted attack are more practical in real attacks and have attracted the attention of many researchers.

Almost all of the research on graph adversarial attacks has focused on GNNs and less on HGNNs. Hu et al.29 demonstrated that HGNNs are also vulnerable to adversarial attacks. Specifically, they proposed the first attack model for HGNNs( HyperAttack), which uses gradients to modify node links to achieve the attack. However, HyperAttack is set as the target attack. From the above introduction, we know that the target attack has many limitations and is difficult to apply to real attacks. In this paper, our aim is to try to minimize the research gap in adversarial attacks on HGNNs.

The results of GNNs adversarial attacks show that the attacks make the similarity between nodes decrease by adding/deleting malicious links. Inspired by this, we propose a Derivative Graph-based Hypergraph Structure Attack(DGHSA). In graphs, the cosine or Jaccard is usually used to measure node similarity30,31. Derivative graph is utilized to analyze and quantify the similarity of nodes in hypergraphs, which is applied in the study of language networks based on hypergraph modeling32. The smaller the value of the derivative graph indicates that the nodes are more similar in the hypergraph. Thus, DGHSA uses the derivative graph to select the optimal perturbation. Specifically, DGHSA consists of two modules: candidate set generation and evaluation. DGHSA first calculates the training gradients of HGNNs and generates candidate sets by modifying the hypergraph structure according to the gradient rules. Subsequently, DGHSA calculates the derivative graph values of each candidate set. Our aim is to maximize the similarity of the nodes. In other words, DGHAS selects the candidate with the largest derivative graph value as the current optimal perturbation hypergraph. DGHSA can be used to cause harm in many real-world application scenarios, for example, citation networks, transportation networks, and bioinformatics. Taking bioinformatics as an example, HGNNs can be used for gene association analysis discovery by modeling complex relationships between genes to infer potential genetic causes of disease. DGHSA alters the correlation data between certain genes and generates some noisy data, leading to erroneous disease associations in disease prediction models and affecting clinical decisions and treatment options. Studying untargeted attacks on HGNNs can help us gain a deeper understanding of the vulnerabilities and security risks of HGNNs. By analyzing how attackers can corrupt the performance of models without specific targets, potential weaknesses in the structure and learning mechanisms of HGNNs can be revealed.

Finally, we summarize our contributions as follows:

  • We propose the untargeted attack against HGNNs, namely DGHSA. DGHSA implements the attack by modifying the hypergraph structure.

  • DGHSA uses the derivative graph metric to select the optimal perturbation hypergraph, which has never been used in previous work on graph adversarial attacks.

  • A number of experiments have demonstrated the effectiveness of DGHSA.

The rest of this work is organized as follows. In Section Related work, we first review the work related to the hypergraph learning and graph adversarial attack. In Section Preliminary, we introduce some fundamentals of the HGNNs and untargeted attack. In Section Attack model, we introduce DGHAS in detail, including candidate set generation and evaluation. Section Experiments presents the experimental dataset, parameters and experimental results. We conclude our work in Section Conclusion. In Appendix Examples of derivative graph, we demonstrate that the derivative graph is applicable in hypergraph attacks.

Related work

Hypergraph learning

Influenced by the advantages of GNNs, researchers started to focus on how to extend GNNs to hypergraphs and proposed many hypergraph-based neural networks. Feng et al.12 proposed the earliest hypergraph neural network(HGNN) by extending GNNs spectral methods to hypergraphs. Yadati et al.13 proposed a model based on hypergraph spectral theory(HyperGCN), which addresses semi-supervised problems on hypergraphs. Ding et al.33 proposed HyperGAT, which captures higher-order action relations between objects. HyperGAT shows efficient learning ability on a hypergraph-based text classification task. Huang et al.34 proposed MultiHGNN, a multigraph neural network, which showed excellent results on multimodal feature datasets. Sun et al.35 proposed HWNN using polynomial approximation wavelet transform instead of Fourier transform, which has lower running time than traditional HGNNs and is applied to heterogeneous hypergraph. The literature36 proposed a hypergraph convolutional network(HNGN) incorporating nonlinear activation function and normalization operation, which consists of four stages including normalized node, updated hyperedge, normalized hyperedge and updated node. The literature37 proposed a hypergraph line graph based convolutional neural network(LHCN), which maps the hypergraph into a line graph, and then uses graph convolution operations in the line graph to implement downstream tasks. The literature38 proposed a hypergraph attention homogeneous network(HAIN), which generates line graphs in an implicit way to solve the problem of high computational cost when LHCN converts hypergraphs to line graphs. Yu et al.39 proposed a multichannel hypergraph convolutional network(MHCN) for social recommendation systems, which uses multiple higher-order user relationships in a multichannel setting to improve the performance of the model in social recommendation tasks. Li et al.14 proposed an end-to-end hypergraph transformation neural network(HGTN), which uses attention mechanisms to find important semantic information in the hypergraph.

Graph adversarial attack

With the interest in the security of GNNs, graph adversarial attacks continue to make new works. Nettack is the first work to study graph adversarial attacks on attribute graphs, which iteratively generates adversarial samples based on GCN gradients with greedy strategies22. Sun et al.40 introduced projected gradient descent(PGD) to graph adversarial attack to the unsupervised node embedding algorithm for the poisoning attack and proved the effectiveness of the attack in a downstream link prediction task. The literature41 proposed a meta-learning attack(Mettack), which implements the attack by training the original graph structure as hyperparameters. Dai et al.42 proposed an adaptive trigger-based backdoor attack with a strict perturbation budget limit to ensure the invisibility of the attack. In addition, Chen et al.43 proposed a feature-based trigger backdoor attack(NFTA) which achieves an effective attack without the knowledge of GNNs. Wang et al.44 proposed an attack using node attributes based on certification robustness, which attacks nodes with large certification perturbations. The results showed that the larger the certification perturbation of a node, the more important that node is for maintaining graph robustness. Li et al.45 proposed an attribute obfuscation attack (AttrOBF) for social networks, which misleads GNNs for misclassification by fuzzy optimal training of user attribute values. The literature25 proposed a method to maximize the spectral distance to achieve the attack(SPAC), which uses an efficient approximation to reduce the time complexity of feature decomposition. Ju et al.46 proposed a black-box attack method using a reinforcement learning framework, where the attacker is not using a surrogate model to query model parameters or training labels to achieve advanced performance. The literature28 proposed a fake node injection attack(NICKI), which learns the node representation and then generates fake node features and edges to achieve misclassification of target nodes into different labels. The literature27 degrades GNNs performance by injecting adversarial links between nodes with different labels.

Preliminary

For convenience, Table 1 gives the frequently used notations.

Table 1 Notations frequently used in this paper and their corresponding descriptions.
Full size table

Hypergraph neural network

Given a hypergraph \(G = (V,E,W)\), where \(V = \{ {v_1},{v_2},...{v_{|V|}}\}\) represents the set of nodes, \(E = \{ {e_1},{e_2},...,{e_{|E|}}\}\) denotes the set of hyperedges, and W is the weight matrix of hyperedges. The incidence matrix H denotes the adjacency of the hypergraph, where the rows denote the nodes and the columns denote the hyperedges. If the hyperedge e contains node v can be denoted as \(H(v,e) = 1\), otherwise \(H(v,e) = 0\).

Our work uses HGNNs to predict the labels of nodes. The core of HGNNs is a message passing mechanism in which each node gets a representation in a rich potential space by aggregating information from its neighbors. The general formulation of this representation learning mechanism takes the following recursive formulation12.

$$\begin{aligned} {X^{(l + 1)}} = \sigma \left( D_v^{ - \frac{1}{2}}HWD_e^{ - 1}{H^T}D_v^{ - \frac{1}{2}}{X^{(l)}}{\Theta ^{(l)}}\right) . \end{aligned}$$
(1)

where \(X^{(l)}\) represents the signal of the hypergraph at l-th layer, \(\sigma (\cdot )\) denotes the nonlinear activation function, W is the weight of the hyperedges, \(D_e\) is the diagonal matrix representing the hyperedge degree (hyperedge degree is the number of nodes contained in the hyperedges), \(D_v\) is the diagonal matrix representing the node degree (node degree is the number of hyperedges containing nodes), and \(\Theta ^{(l)}\) denotes the training parameters at l-th layer.

The two-layer hypergraph convolutional network can be represented as:

$$\begin{aligned} Z = f(H,X) = soft\max (\widehat{H}{\textrm{Re}} LU\left( \widehat{H}X{\Theta ^{(1)}}){\Theta ^{(2)}}\right) . \end{aligned}$$
(2)

where \(\widehat{H} = D_v^{ - \frac{1}{2}}HWD_e^{ - 1}{H^T}D_v^{ - \frac{1}{2}}\), \(\Theta ^{(1)}\) and \(\Theta ^{(2)}\) are denoted as the training parameters of the first and second layers, respectively. The optimal classifier \({f_{{\Theta ^*}}}( \cdot )\) is obtained for the semi-supervised problem by minimizing the cross-entropy loss of all labeled nodes:

$$\begin{aligned} {L_{tra}}(\Theta ;H,X) = - \sum \limits _{v \in {V_L}} {\ln {Z_{v,{Y_v}}}}. \end{aligned}$$
(3)

where \({V_L}\) denotes the set of labeled nodes, i.e., the training set. \({Y_v}\) represents the true label of node v. \({Z_{v,{Y_v}}}\) denotes the probability that node v is predicted as \({Y_v}\).

Problem definition

The attacker achieves the attack by adding/deleting malicious link perturbations to the original hypergraph to maximize the loss of node predicted labels and true labels. The above process can be described as

$$\begin{aligned} \begin{aligned}&\underset{H^{\prime }}{\arg \max } \sum _{v \in V_T} L_{a t k}\left( f_{\Theta ^*}\left( v, H^{\prime }\right) , Y_v\right) , \\&\text{ s.t. } \Theta ^*=\underset{\Theta }{\arg \max }\ \sum L_{\text{ tra } }(\Theta ; H, X), \quad \left\| H^{\prime }-H\right\| \le \Delta . \end{aligned} \end{aligned}$$
(4)

where \({V_T}\) represents the node test set, \({\Theta ^*} = \{ {\Theta ^1},{\Theta ^2}\}\) represents the optimal training parameters, \(H^{\prime }\) and represents the perturbation hypergraph. Note that we only modify the node adjacency, rather than the node features. The attack needs to ensure not only the feasibility of the attack, but also the invisibility, so we use a budget \(\Delta\) to limit the attacker’s attack bound.

Targeted attack and untargeted attack

In graph adversarial attacks, targeted and untargeted attacks are two different types of attacks that have different goals and forms of expression. The following is a detailed explanation of these two attacks and a comparison of their expressions.

The targeted attack typically uses a loss function that causes the model to output a specific target label on the adversarial sample, which can be formally represented as follows:

$$\begin{aligned} \begin{aligned}&\arg \max _{H^{\prime }} \sum _{v \in V_S} \mathbb {I}\left( Y_v = C_{tar}\right) , \\&\text{ s.t. } Y_v=\arg \max f_{\Theta ^*}\left( H^{\prime }, X\right) , \left\| H-H^{\prime }\right\| \le \Delta . \end{aligned} \end{aligned}$$
(5)

where \(\mathbb {I}(x)\) is the indicator function. If x is true, \(\mathbb {I}(x)\) returns 1, otherwise \(\mathbb {I}(x)\) returns 0. \(Y_v\) is the predicted label and \(C_{tar}\) is the label specified by the attacker. \(V_S\) is a set of partial nodes in the test set.

The purpose of an untargeted attack is to cause the input samples to be misclassified into any label without specifying the target label. The attacker simply ensures that the output of the model is not the correct label. The training objective of the untargeted attack can be expressed as:

$$\begin{aligned} \begin{aligned}&\arg \max _{H^{\prime }} \sum _{v \in V_T} \mathbb {I}\left( Y_v \ne C\right) , \\&\text{ s.t. } Y_v =\arg \max f_{\Theta ^*}\left( H^{\prime }, X\right) , \left\| H-H^{\prime }\right\| \le \Delta . \end{aligned} \end{aligned}$$
(6)

where C is the true label of nodes.

Attack model

In this section, we describe the DGHSA building blocks in detail, and the overall framework of DGHSA is illustrated in Fig. 1. Overall, DGHSA contains two main components, the candidate set generation and the evaluation candidate set modules. To obtain the optimal candidate set at t iterations, we first train using HGNNs to obtain the gradient matrix of the incidence matrix H, and then use different strategies to add or remove links to obtain the candidate sets, as shown in Fig. 1a–c. How does an attacker select the candidate sets to achieve an effective attack? To solve this question, we introduce the derivative graph to help the attacker make a decision. The derivative graph can measure the similarity between nodes and is often used in the classification task. Smaller derivative graph values indicate more similar nodes in the hyperedges. We calculate the derivative graph value of each candidate hypergraph and select the candidate hypergraph with the largest derivative value as the perturbed hypergraph at moment t, as shown in Fig. 1d and e.

Fig. 1
figure 1

DGHSA overall framework. DGHAS consists of two modules: (a)–(c) are expressed as candidate set generation module, (d)–(e) are expressed as evaluation candidate set module.

Full size image

Candidate set generation

Traditional gradient attacks tend to fall into local optima and thus do not get the best perturbation. The aim of DGHSA is to generate multiple candidate sets and select the best perturbation from them to improve the efficiency of the attack. In this section, our aim is to generate a candidate set \({C^{(t)}} = \{ H_1^{(t)},H_2^{(t)},\ldots ,H_n^{(t)}\}\) containing n hypergraphs, where t represents the t-th iteration and \(H_i^{(t)}\) represents the i-th candidate. Please note that DGHSA only attacks the hypergraph structure without any modification to the features, so the feature information is the same in each candidate set.

To obtain the gradient information of the incidence matrix H, DGHSA is first trained with HGNNs. Then, calculating the derivative of the training loss with respect to the incidence matrix H obtains the gradient matrix:

$$\begin{aligned} {g^{{H^{(t)}}}} = \frac{{\partial {L_{atk}}}}{{\partial {H^{(t)}}}}. \end{aligned}$$
(7)

The gradient reflects the sensitivity of the model to changes in the inputs, and attacking entity with larger absolute values of the gradient causes a larger impact, thus enabling better attacks. DGHSA utilizes this rule to sort \({|g^{{H^{(t)}}}|}\) from largest to smallest, and select the node with the largest gradient. Modify the node link according to the graph gradient algorithm experience.

$$\begin{aligned} \left\{ {\begin{array}{*{20}{c}} {g_{(i,j)}^{{H^{(t)}}} > 0,{H_{(i,j)}} = 0}.\\ {g_{(i,j)}^{{H^{(t)}}} < 0,{H_{(i,j)}} = 1}. \end{array}} \right. \ \end{aligned}$$
(8)

Entity (i, j) is added to the candidate set \({C^{(t)}}\) if it satisfies Eq. (8). The above process is repeated until the end of \(||{C^{(t)}}|| = n\). Note that the added candidate set is not repeated and the entity (i, j) is modified at most once. In addition, the advantage of building the candidate set is that it can avoid the gradient attack to be trapped in the optimal value situation.

Candidate set evaluation

Graph attack studies show that attacks tend to remove links between nodes with high similarity or add links between nodes with large similarity differences. Inspired by this, we use the derivative graph to evaluate candidate sets. The derivative graph is a measure of node similarity within a hyperedge. It considers node dissimilarity and can represent node similarity and difference in the hypergraph. The definition of the derivative graph \(D \in {\mathbb {R}^{N \times N}}\) is as follows:

$$\begin{aligned} {D_{i,j}} = \frac{{{F_{i,i}} - {F_{i,j}} + {F_{j,j}} - {F_{i,j}}}}{{{F_{i,j}}}} = \frac{{{F_{i,i}} - 2{F_{i,j}} + {F_{j,j}}}}{{{F_{i,j}}}}. \end{aligned}$$
(9)

The smaller \({D_{i,j}}\) means that node i and node j are more similar. Node i and node j never appear together in a hyperedge, we set \({D_{i,j}} = 0\). In addition, the diagonal values of D are set to 0.

In Eq. (9), \(F \in {\mathbb {R}^{N \times N}}\) represents the frequency matrix of the hypergraph, which is defined as:

$$\begin{aligned} F_{i,j}^{(t)} = \left\{ {\begin{array}{*{20}{c}} {\deg (i),\mathrm{ }\quad if\mathrm{ }\quad i = j}.\\ {|\{ e|v_i,v_j \in e\} |,\mathrm{ }\quad if\mathrm{ } \quad i \ne j}. \end{array}} \right. \end{aligned}$$
(10)

The diagonal elements of the frequency matrix F are the hyperdegrees of node i. The remaining elements are the number of nodes i and j that are on the same hyperedge at the same time.

In the Appendix Examples of derivative graph, we use simple examples to demonstrate that the derivative graph can be effectively applied in our attacks. The purpose of DGHSA is to modify the node links so that the derivative graph value of the hypergraph increases, i.e., the worse the similarity of the nodes within the hyperedges. The derivative value of each candidate hypergraph is calculated.

$$\begin{aligned} DH_k^{(t)} = sum(D(H_k^{(t)})). \end{aligned}$$
(11)

The larger \(DH_k^{(t)}\) indicates that modifying the links can make the similarity difference between the nodes before increasing, the more advantageous to the attack.

Finally, we obtain the optimal perturbation map by filtering the candidate set \({C^{(t)}}\).

$$\begin{aligned} {H^{(t)}} =\arg \max ({C^{(t)}}) =\arg \max (DH_1^{(t)},DH_2^{(t)},...,DH_n^{(t)}). \end{aligned}$$
(12)

Algorithm and time complexity

Algorithm 1 summarizes the specific attack process of DGHSA.

Algorithm 1
figure a

Derivative graph-based hypergraph atructure attack (DGHSA).

Full size image

We analyzed the time complexity of DGHSA. First, HGNNs are used as pre-trained models with time complexity \(\mathscr {O}({T_{pre}}||H|| \cdot ||X||)\), where \({T_{pre}}\) is the number of HGNNs pre-trained. DGHSA contains two modules for generating and evaluating candidate sets. In the module of generating candidate sets, the time complexity of computing the loss function of the incidence matrix is the same as the time complexity of training HGNNs, i.e., \(\mathscr {O}({T_{pre}}||H|| \cdot ||X||)\). The time complexity for filtering the generated candidate sets is very low, and we ignore it here. Therefore, the above module time complexity is \(\mathscr {O}(T \cdot {T_{pre}}||H|| \cdot ||X||)\), where T is the number of attack iterations. When evaluating the candidate set, both the time consumption of the computation frequency and the derivative graph matrix are \(\mathscr {O}(|V|\log |V|)\) . The other operations (e.g., sorting the derivative graph values) have low complexity and are neglected. Therefore, the candidate set evaluation module time complexity is \(\mathscr {O}(T \cdot |V|\log |V|)\). The final time complexity of DGHSA can be expressed as \(\mathscr {O}(T({T_{pre}}||H|| \cdot ||X|| + |V|\log |V|)).\)

Experiments

Datasets

Four common datasets ( Cora-ML, ACM, Citeseer and NTU) are used in our experiments, which are often used to evaluate the performance of HGNNs. These four types of datasets have different network characteristics, where the ACM and Citeseer datasets are featured discretely, and Cora-ML and NTU are datasets with continuous features. In addition, we validate the effectiveness of DGHSA from node classification and visual object classification tasks, respectively. Cora-ML and Citeseer are citation networks, where nodes represent papers and hyperedges represent citation relationships among papers. ACM is a collaboration network, where nodes represent papers and hyperedges represent the collaboration relationships of papers. NTU is a visual object classified dataset where the features represent the shape of the object. The statistics of these four datasets are in Table 2. It is worth noting that we use only the node features and labels. The adjacency relations between nodes are generated using some common methods, which will be described in detail in later sections.

Table 2 Statistics of four datasets.
Full size table

Baselines

Currently, there are few works on HGNNs adversarial attacks and the number of comparable models is less. The literature29 is the most relevant work to this paper. Equations (5) and (6) show that targeted and untargeted attack optimization goals are different. In addition, the code from literature29 is unpublished and more difficult to reproduce, so we cannot extend it to untargeted attacks. We have selected several representative models. Their details are described below.

Random: Random is a simple attack method that randomly modifies the adjacency of the nodes. In many works, Random is often used as a comparison model.

HyperDegree: Common GNNs adversarial attacks have shown that nodes with larger degrees of attack can degrade the performance of GNNs. Extending to hypergraphs, HyperDegree is a method to attack nodes with larger hyperdegree.

Fast gradient attack (FGA): FGA extracts the adjacency gradient in HGNNS training, and then modifies the link with the largest absolute gradient to update the perturbation hypergraph.

Victim model

In the experiments of this paper, we use two HGNNs models as victim models, HGNN-KNN and HGNN-\(\varepsilon\)47. They are both distance-based HGNNs, which are described in detail as follows.

HGNN-KNN: HGNN-KNN first finds the nodes of K nearest neighbors in the feature space and then generates a hyperedge to connect these nodes. The hyperedges contain nodes that are uniformly all K.

HGNN-\(\varepsilon\): HGNN-\(\varepsilon\) connects the nearest neighbor nodes within the range \(\varepsilon\) in the feature space using a hyperedge. The number of nodes within the hyperedge is not uniform.

Parameters and metrics

Parameters. The parameters related to HGNNs are set as follows: HGNN-KNN nearest neighbor parameter K is set to 10, HGNN-\(\varepsilon\) range parameter \(\varepsilon\) is set to 0.5. The number of layers is set to 2, the hidden layer unit is 64. The number of training times is set to 300, and the learning rate of Adam optimizer is \({10^{ - 3}}\). The datasets are set in the ratio of 0.2 and 0.8 for the training and test sets. The budget \(\Delta = \lambda N\), \(\lambda\) set by default to 0.05. The candidate set size n is set to 5.

Metrics. For a comprehensive evaluation of DGHSA, we use the classification success rate and the derivative graph ratio to measure the attack effectiveness. It is worth noting that the derivative graph ratio is proposed by us for the first time to evaluate the attack performance.

Classification Success Rate(CSR): CSR indicates the classification accuracy of HGNNs in the test set, and a lower rate indicates a better attack effectiveness.

$$\begin{aligned} CSR = \frac{ \mathbb {I}\left( Y_v \ne C\right) }{|V_T|}. \end{aligned}$$
(13)

Derivative Graph Ratio(DGR): The derivative graph reflects the similarity of the nodes in the hypergraph. DGR is defined as the perturbed hypergraph derivative graph value over the clean hypergraph derivative graph value, which can be described by a mathematical expression as:

$$\begin{aligned} DGR = \frac{DH^{\prime }}{DH}. \end{aligned}$$
(14)

\(DH^{\prime }\) is the perturbed hypergraph derivative graph value. Larger DGR indicates less similarity of nodes, i.e., better attack performance.

Main experiment

Table 3 The CSR (\(\%\)) and DGR of the attack are under four datasets, with lower CSR or higher DGR indicating better attack performance.
Full size table

In this section, we validate the effectiveness of DGHSA, and the results are shown in Table 3. We observe that all attack achieve well performance on all datasets, which indicates that attacking the structure of the hypergraph can effectively reduce the accuracy of HGNNs.

Attack effectiveness. We analyze the performance of DGHSA in terms of CSR and DGR, respectively. CSR: Table 3 shows the node classification accuracies of various models with different datasets. When the victim model is taken as HGNN-KNN, the best attack performance is achieved by DGHSA in Citeseer. Specifically, the CSR of Random, HyperDegree, and FGA, DGHSA are 63.60\(\%\), 63.12\(\%\), 61.67\(\%\) and 58.10\(\%\), respectively. The lower CSR indicates the better attack performance. The CSR decrease indicates that the performance of HGNNs depends on the structural information of the graph. The attacker changes the topology of the hypergraph by modifying the entity relationships, which affects the information propagation and feature learning process. The same results in other datasets, DGHSA shows better performance in reducing the CSR of HGNNs. DGR: It is observed from Table 3 that each attack is able to raise the derivative graph value. The derivative graph value can reflect the similarity of nodes within the hypergraph, and a higher DGR indicates a poorer similarity of nodes, i.e., a greater damage caused by the attack. Since the original hypergraph derivative graph value is large, we keep 4 decimal places when counting the derivative graph value of the hypergraph. When the victim model is HGNN-KNN, DGHSA has the highest derivative graph ratio after the attack, which is 0.0339, 0.0317 and 0.0076 higher than the DGR of Random, HyperDegree, and FGA in NTU, respectively. This indicates that DGHSA causes higher damage relative to other attacks with the same budget, i.e., the attack is more effective. In addition, the above results indicate that attacks usually lead to a decrease in node similarity, which is the same as the conclusion obtained in GNNs adversarial attacks. Finally, the small change of DGR indicates that the hypergraph still maintains its original structural characteristics after the attack, which at the same time reflects the invisibility of the attack.

Attack transferability. We used two HGNNs models to verify the transferability of DGHSA. The results demonstrate that DGHSA achieves optimal attacks under both victim models, which indicates that DGHSA has better transferability. In the ACM dataset, the DGHSA reduces the classification accuracy of HGNN-KNN and HGNN-\(\varepsilon\) 3.50\(\%\) and 3.38\(\%\), and improves graph derivative values by 0.0815 and 0.0820 respectively, which achieves excellent results in all the compared models. Intuitively, both HGNN-KNN and HGNN-\(\varepsilon\) utilize similar information propagation mechanisms that share commonalities in dealing with node features and hypergraph structures, and the same attack methods can effectively interfere with information propagation, thus affect the performance of multiple HGNNs.

Impact of budget on attack performance

Fig. 2
figure 2

The impact of budget on CSR. The first and second rows show the results for HGNN-KNN and HGNN-\(\varepsilon\) under the four datasets, respectively. Attack performance is positively related to attack budget.

Full size image

Since the DGR changes are not as obvious as the CSR, we use the CSR to verify the performance of the DGHSA in this and later sections. In this section, we investigate the performance of various attacks with different budgets. Figure 2 shows CSR of HGNNs for budget factors \(\lambda\) of 0.04–0.09.

In all cases, our proposed model achieves the best performance, i.e., HGNNs have the lowest CSR after being attacked by DGHSA. For example, Fig. 2d shows that the classification accuracy of Random, HyperDegree, FGA and DGHSA are \(\{\)74.81\(\%\), 73.01\(\%\) \(\}\), \(\{\)74.12\(\%\), 72.02\(\%\) \(\}\), \(\{\)72.15\(\%\), 69.20\(\%\) \(\}\) and \(\{\)71.05\(\%\), 67.14\(\%\) \(\}\) when the budget factor \(\lambda\) are \(\{\)0.04, 0.09\(\}\), respectively. As the budget factor \(\lambda\) increases, the attacker can make modifications to more nodes or edges. This means that the attacker can implement more sophisticated strategies, such as destroying multiple key nodes or edges at the same time, thus significantly affecting the propagation and aggregation process of information. Since the effects of an attack tend to be cumulative, multiple small structural modifications may act in conjunction, leading to a significant performance degradation of HGNNs in classification tasks. In addition, the topological attribute attack (HyperDegree) can reduce the accuracy of HGNNs, but its attack performance is limited only to be better than the Random attack. Therefore, this attack is difficult to be applied in practical attacks.

Impact of HGNNs parameters on DGHSA performance

In this section, we investigate the effect of HGNNs parameters K and \(\varepsilon\) on DGHSA performance as follows.

Figure 3 shows the CSR of HGNN-KNN with different parameters K. We observe that DGHSA effectively reduces the accuracy of HGNN-KNN regardless of the value of K. For example, when K are \(\{\)5, 10, 15\(\}\), the CSR of DGHSA are \(\{\)73.65\(\%\), 74.89\(\%\), 74.67\(\%\) \(\}\) in Fig. 3b, respectively. In other datasets, the results are the same(as shown in Fig. 3a, c and d). We observe that the classification accuracy of clean hypergraphs also changes under different parameter K, but the fluctuation is not large, so it is normal for DGHSA to have fluctuations under different K. In other words, the parameter K does not affect the performance of DGHSA.

Fig. 3
figure 3

CSR of DGHSA with different parameters K. The parameter K does not affect the performance of DGHSA.

Full size image

Similarly, we also investigated the effect on DGHSA and the results are shown in Fig. 4. DGHSA has good metastability and thus achieves good performance in HGNN-\(\varepsilon\) as well. Observing Fig. 4a–d, it can be seen that DGHSA reduces the accuracy in Cora-ML, ACM, Citeseer and NTU by an average of 4.6\(\%\), 3.3\(\%\), 5.0\(\%\) and 4.25\(\%\) in different parameters \(\varepsilon\), respectively. As in the case of parameter K, parameter \(\varepsilon\) does not affect the performance of DGHSA.

The above results illustrate that our proposed model can be equally effective under various HGNNs parameters, i.e., DGHSA has good stability.

Fig. 4
figure 4

CSR of DGHSA with different parameters \(\varepsilon\). The parameter \(\varepsilon\) does not affect the performance of DGHSA.

Full size image

Impact of the number of candidate sets on the performance of DGHSA

Figure 5 shows the effect of the number of candidate sets n on the performance of DGHSA. Observing the Fig. 5a–d, we can find that the candidate set sampling mechanism can improve the performance of DGHSA. For example, in Fig. 5a, CSR of HGNN-KNN and HGNN-\(\varepsilon\) are \(\{\)65.78\(\%\), 63.70\(\%\) \(\}\) and \(\{\)65.26\(\%\), 63.27\(\%\) \(\}\) when n=\(\{\)2, 12\(\}\), respectively. In the other datasets, the performance of DGHSA improves as n increases. This is because when the number of candidate sets n is large, the less likely the attack is to fall into a local optimum. It is worth noting that the performance of DGHSA does not improve significantly when n is larger. In Citeseer, the classification accuracy of HGNN-KNN experiences a decrease of 3.56 percent when n ranges from 2 to 6, and a decrease of 0.19 percent as n increases from 6 to 12. Intuitively, the best perturbation found by the attack when n is larger is the same as the perturbation found when n is less further.

Further, we study the DGHSA runtime at different n. Here we take Cora-ML as an example, and the results are shown in Table 4. When the victim model is HGNN-KNN the time spent by DGHSA is 0.89 and 2.23 with n of 2 and 12, which is very satisfying. Since DGHSA computes the derivative graph and evaluates the candidate sets more times when there are more candidate sets, the running time increases. The above results demonstrate that DGHSA can achieve better performance with less time spent. In addition, combining Table 4 and Fig. 5a shows that n is positively proportional to the performance of DGHSA.

Fig. 5
figure 5

CSR in different parameters n. The performance of DGHSA becomes better with the increase of n.

Full size image
Table 4 Taking Cora-ML as an example, the running time (in minutes) of DGHSA in different parameters n.
Full size table

Conclusion

In this paper, we propose a modified hypergraph structure attack (DGHSA), which focuses on reducing the classification accuracy of the global nodes. To obtain the optimal perturbation graph at each moment, we first use a gradient algorithm to obtain the set of perturbation hypergraph candidates. Previous studies have shown that adversarial attacks tend to make the node similarity worse. Therefore, we use the derivative graph to measure the similarity of each perturbation hypergraph and select the hypergraph with the larger derivative graph value as the optimal perturbation hypergraph. We validated the effectiveness of DGHSA on four commonly used datasets.

However, DGHSA is a white-box attack algorithm that relies on gradient information and node labels to accomplish the attack, and perhaps the attack is not effective in some large-scale hypergraphs. In the future, we consider bypassing the computation of gradient, and adopt a heuristic-based approach to generate perturbations. Alternatively, using comparative learning, an unsupervised attack can be designed which can be achieved without knowing the node labels is the attack. For large-scale hypergraphs, the attack can be optimized by converting the full hypergraph to a subhypergraph. In this paper, our experiments focus on classification tasks, and in future work we can design attacks oriented to link prediction or association detection tasks. Moreover, according to the conclusions of this paper, when attacking temporal or dynamic hypergraph neural networks, we aim to achieve the attack by reducing the node similarity.