HeTa: Relation-wise Heterogeneous Graph Foundation Attack Model

1 Introduction

Heterogeneous graphs (HGs), prevalent in fields like biological networks [Ma et al., 2023] and knowledge graphs [Sanmartin, 2024], realistically represent complex systems with diverse nodes and edges across different domains. Existing heterogeneous graph neural networks (HGNNs) are often vulnerable to adversarial attacks due to perturbation amplification from the complex coupling of heterogeneous nodes and relations [Zhang et al., 2022]. Therefore, developing tailored attack methods for HGNNs is essential for assessing their robustness and ensuring the security of their applications.

∗Corresponding author.

Current attacks on HGs primarily utilize gradients from surrogate models with structures similar to the target model to perform topology attacks, thereby degrading the performance of the target HGNN. Broadly speaking, these attacks mainly fall into two groups: (1) targeted attack, which aim to reduce the performance of specific target instances but nontarget might remain unchanged to avoid being detected [Wang et al., 2024]; and (2) global attacks, which have recently emerged to reduce the overall performance of HGNNs with limited budget [Shang et al., 2023]. While promising, existing methods on HGs rarely account for the generalization of attackers, which necessitates retraining attack parameters for different target HGNNs and new HGs. Although some recent works have attempted transferable attacks [Shang et al., 2023; Zhao et al., 2024], they fail to achieve cross-domain applicability and require elevated permissions to manipulate either the graph structure or the training data.

Due to their powerful generalization capabilities, foundation models have revolutionized the fields of Natural Language Processing [Qin et al., 2023] and Computer Vision [Liu et al., 2024], demonstrating significant potential in learning general, open-world knowledge from diverse data sources. This has endowed them with strong expressiveness and adaptability, enabling them to excel across a wide range of tasks and datasets. Building on this concept, Graph Foundation Models (GFMs) constitute a significant advancement in graph-structured data, facilitating cross-domain and crosstask generalization through the training of a unified, transferable vocabulary (e.g., basic graph elements like relations and subgraphs). This advancement prompts us to consider a natural question: Can we design a foundation attack model for HGNNs that enables generalizable perturbations across different HGNNs, and quickly adapts to new HGs?

To address this question, we empirically investigate the impact of removing different relation subgraphs from various HGNNs on the ACM dataset as Figure 1, as the relationships among nodes often serve as the fundamental semantic of HGs [Wang et al., 2022; Wang et al., 2019]. The results clearly show that the importance of the relations is consistent across these HGNNs, i.e., R1>R2>R3. Specifically, removing relation R1 typically leads to the most significant performance drop across all HGNNs (up to 23.6%), while removing R3 causes only a minor impact (up to 2.8%). It indicates that these HGNNs share a common importance pattern across relational subgraphs and are likely to be consistently vulnerable when the most crucial relation is perturbed. This motivates us to view relations as the fundamental shared attack unit, laying the groundwork for a foundation attack model for HGNNs.

Despite its potential, achieving this goal entails significant challenges. First, how to identify the shared importance distribution of attack semantic units across different HGNNs? The differences in structural and feature distribution between HGs are considerable [Xia and Huang, 2024]. Therefore, different HGNNs requires careful heuristic design and generally involves significantly large and diverse parameter spaces to model semantic diversity [Wang et al., 2019], making it difficult to uncover the underlying generalizable principles shared across HGNNs. Second, once the importance pattern is captured, how to design universal attack criteria based on this pattern to progressively destroy each critical semantic unit in the HG? Since the HG is decomposed into different attack units with varying semantics, it is crucial to attack these units precisely, step by step, based on their importance, while employing a low-budget and low-permission strategy.

In this paper, we propose a relation-wise Heterogeneous graph foundation atTack model (HeTa), which identifies shared attack patterns based on relational semantics, enabling the attack process on HGs to generalize. Specifically, we develop a lightweight foundation surrogate model to provide a unified characterization of different HGNNs, i.e., simplifying their propagation mechanisms to model the importance distribution of shared relational semantic units. A simple parametric mechanism that enables fast generalization to new graphs. Subsequently, we implement a relation-by-relation serialized attack process based on the learned relation weights. This involves injecting adversarial nodes into each relation subgraph, with gradients from the carefully designed attack loss guiding the generation of fake edges, enabling a low-budget attack that requires minimal permissions to perturb the original topology. Finally, the perturbed HG can be fed into different target HGNNs to evaluate the attack's effectiveness and generalizability, and the attack on a new HG can be quickly fine-tuned by freezing part of the attacker's parameters. Our key contributions are as follows:

• To our knowledge, it is the first foundation attack model for HGNNs. We also verify that different HGNNs share common vulnerabilities in relation-aware attack units.
• We propose HeTa, a novel generalizable HGNN attack model, that enables transferability across different target HGNNs and easily adapts to new HGs.
• Extensive experiments on three public datasets demonstrate the effectiveness and generalizability of our proposed HeTa under node injection and evasion attacks.

2 RelatedWork

2.1 Heterogeneous Graph Neural Network

HGNNs are widely acclaimed for enhancing node representations. According to the way to handle heterogeneity, HGNNs mainly fell into meta-path-aware and relation-aware methods. The former relies on carefully designed meta-paths to aggregate information, often involving complex relation combinations. [Fu and King, 2024; Wang et al., 2019]. The latter is aggregate messages from neighbors of different relations [Yu et al., 2022; Yang et al., 2023]. Recent advancement have focused on leveraging LLM to achieve generalization across diverse HGs [Tang et al., 2024]). AnyGraph learns a foundation model from a vast of graphs to effectively handle the heterogeneity [Xia and Huang, 2024]. Despite significant differences, these HGNNs essentially regard relations as the most fundamental semantic units.

2.2 Adversarial Attack on Graph Neural Network

Graph adversarial attacks have gained traction because minimal perturbations can mislead models. Homogeneous graph attack, such as [Chen et al., 2018] and [Goodfellow et al., 2014] use gradient information to guide attack edges. [Zhang et al., 2024] proposes a susceptible-reverse influence sampling strategy for selecting neighbors. While in HG, the adversarial robustness remains less explored. Roughly speaking, attacks in HGNNs fell into target attack and global attack. The former manipulate graph to mislead target instances, e.g., [Zhao et al., 2024] proposes a semantic-aware mechanism to automatically identify and generate perturbations to mislead target nodes. While the latter aim to destroy the total performance, e.g., [Shang et al., 2023] proposes a structured global attack method guided by edge attention. While promising, no existing study has yet explored a generalizable foundation model for HGNNs.

3 Preliminaries

3.1 Heterogeneous Graph

Heterogeneous Graph (HG), G = (V, E,F), consists of an node set V, an edge set E and a feature set F. G is also associated with a node type mapping function ϕ : V → T and an edge type mapping function ψ : E → R. T and R denote the predefined type sets of node and edge, where |T | + |R| > 2. Let Vτ denotes the node set of type τ ∈ T , the feature set F is composed of |T | feature matrices, F = {Fτ , τ ∈ T }, Fτ ∈ R|Vτ |×dτ , where dτ is the feature dimension of τ nodes.

Relation Subgraph. Given a HG, G = (V, E,F), Gr is a subgraph of G that contains all edges of relation r. The adjacency matrix of Gr is Ar ∈ RN×N , where N is the number of nodes in G. Ar[i, j] = 1 if ⟨vi, r, vj⟩ exists in Gr, otherwise Ar[i, j] = 0, where vi, vj ∈ V, r ∈ R. A is adjacency matrix for G, i.e., A = ∑Rr=1 Ar.

3.2 Node Injection Attack in HG

Given a HG, G = (A,F), node injection attack (NIA) generates a fake node set Nin and connects to existing nodes in G. The perturbed HG after injecting Nin can be denoted as G ′ = (A′1 ,A′2 , ...,A′|R| ; F ′1 , F ′2 , ..., F ′ |T | ). E.g., for two types of nodes in G, Author (A) and Paper (P), connected by edges type P-A, after injecting fake nodes Nin of type P, we have:

where APA ∈ RN×N is the subgraph of P-A type, Ein ∈ RN×|Nin| is the adjacency between the original and injected nodes, and E0 ∈ R|Nin|×|Nin| is the adjacency between injected nodes. FP ∈ RN×dP and Fin ∈ R|Nin|×dP are the features of the original and the injected nodes, respectively.

Foundation Attacker's Goal. The foundation attacker aims to construct generalizable perturbation graphs that degrade the target model's performance, which can transfer to new scenarios, like new target models and graph domains.

Attacker's Knowledge and Capability. We focus on NIA in black-box and evasion settings, where the attacker can only modify the test data without access to the target model's parameters or architecture [Sun et al., 2022]. Given a clean HG, G = (A, F), we train a surrogate model fθ and freeze its parameters. Next, the attacker is trained based on the surrogate model's behavior to generate fake nodes and inject them into G, forming a perturbed graph, G ′ = (A′ , F ′ ), within budget. Finally, we apply the attacked G ′ to other target models to reduce their predictions. The unified formulation is:

where θ∗ denotes the surrogate model's optimal parameters trained by the loss L, i.e., the cross-entropy loss for node classification. The higher L(fθ∗ (G ′ )), the better the performance of the attack. The injected node set Nin is limited by a injected rate ρ and total node number N in G, the degree of each injected node v is limited by average degree K of G.

4 Proposed Framework

In this section, we introduce HeTa, a novel foundation attack model designed specifically for HGNNs by identifying relation-aware shared attack units. An overview of the framework is shown in Figure 2.

4.1 A Lightweight Foundation Surrogate Model

We introduce a foundation surrogate model to represent the vulnerabilities of different HGNNs, aiming to achieve two key objectives: (1) Generalization, providing a unified description of the common characteristics shared across various HGNNs, and (2) Vulnerability Learning, identifying the importance distribution of fundamental attack units in HGs.

Heterogeneous Features Alignment. Since different node types τ ∈ T in HGs typically come from inconsistent distributions, we first align the original features hv ∈ R1×dτ of various node types into a unified vector space:

where h0v denotes the unified node representations in a shared semantic space. The feature aligner, i.e., Projector(·), can be flexibly configured as any trainable model for different node types; here, we instantiate it using a linear transformation.

Heterogeneous Foundation Message Passing. Building on the experimental results shown in Figure 1, which reveal a unified vulnerability pattern across different HGNNs from a relational perspective, we propose treating relational subgraphs as the fundamental attack units. To this end, we employ an ensemble multi-relational message passing mechanism [Wang et al., 2022] to model relational semantics in HGs using learnable coefficients, i.e., the weights of fundamental attack units in our case. Specifically, messages from different relation subgraphs are aggregated by weighted summation based on the learned relational coefficients:

where µr and ˆ Ar represent the weight and the normalized adjacency matrix of relation r, respectively, with ∑Rr=1 µr = 1. Given by ˆ Ar = ˜D- 1 2 r ˜ Ar ˜D- 12 r , ˜ Ar = Ar + I and ˜Dr = Dr + I, where Dr is the degree matrix of Ar. σ denotes activation function, we use ReLU here. To preserve the node's original information as much as possible and prevent oversmoothing, we employ residual connections:

where H0 = [h01 , h02 . . . , h0N ] is the initial features from Projector(·), and α ∈ [0, 1] is a adjustable scaling factor. The Classifier(·) is used to output the probability distribution Ypred of node labels and is implemented as an MLP in our work. We use cross-entropy loss for node classification as the training objective, as shown in Eq.(2). Each element in µ = [µ1, µ2, . . . , µ|R|] is initially set to 1 |R| , and adaptively learned during this training.

Consequently, the optimized µ indicates the importance distribution of relational attack units, which identify common vulnerabilities across HGNNs. Furthermore, its lightweight parameterization enables rapid adaptation to new HGs, and we will validate its generalizability in the experiments.

4.2 Relation-wise Generalizable Perturbation Generation

Traditional attacks on HGNNs typically generate perturbations based on an overall attack loss, without considering the disruption of each individual semantic component within the HG, leading to incomplete attacks. To alleviate this issue, we leverage the importance distribution across various relationaware attack units provided by the surrogate model and systematically attack each unit in a serialized manner-i.e., at each step, identifying and attacking the most important relation. In this way, the semantics of the entire HG will be progressively and thoroughly disrupted after M steps.

Relation-wise Attack Principle. We identify fundamental attack units, relation weight µ by surrogate model, and the relations with larger weights play a more crucial role in the model's training and prediction. Based on this, we introduce a step-by-step relation-wise attack strategy to progressively perturb the most critical parts of the HG. The weights at step 0 are initialized as µ. Specifically, at step m, we attack the relation unit r with the largest weight:

To prevent consecutive attacks from targeting the same relation, we introduce a penalty term β to dynamic reweight the relation unit that was attacked in the previous step, thereby obtaining the weights for next step: µm+1 r = µmr β .

Attack Loss. During attacks, we reversely optimize the training objective of the surrogate model. Here, our loss function Latk includes the Carlini-Wagner (CW) attacks loss [Carlini and Wagner, 2017] Lcw and the inverse of the KL divergence [Ji et al., 2020] Lkl. The objective of the attack is to minimize the Latk:Latk = Lcw + Lkl. (7)

The CW loss minimizes the difference between the correct category and the maximum probability of other categories:

where pv,c denotes the probability that node v is predicted to be target class c and maxyv̸=c pv,yv represents the probability of the most likely incorrect class. V is test node set and k (set as 0 here) is a confidential level of making wrong predictions. The Lkl shifts the model's probability distribution:

where Dkl is KL divergence, ˆ yv the predicted label distribution from surrogate model for node v ∈ V , and yv is the groundtruth. pv denotes the predicted probability that v belongs to its true category. To prevent gradient explosion when pv → 0, we use a smooth loss function [Zou et al., 2021]:

where r is a control factor (set as 4 here).

Relation-wise Attack. At each attacking step m ∈ [1,M], the disruption of the relation-aware semantic unit r involves two phases: first, generate the corresponding fake node set N r in , including their type and features, based on the relation of the current attack unit; second, create fake edge set Er in connecting these fake nodes, guided by the gradient information of the current relation subgraph.

(1) Fake Node Generator. Based on the current attack relation r selected in Eq.(6), we randomly choose the injected node type from the head and tail entity types of relation r, denoted as ϕin(r). The remaining unselected type is then designated as the connecting node type, denotes as ϕcon(r). Here, we define the initial features and connections of the injected node vin ∈ N r in . Specifically, we assume that vin is initially connected to all nodes of type ϕcon(r), and this connection will be further optimized by the edge selector. To enhance the imperceptibility of vin, we calculate the cluster center of all nodes of type ϕcon(r) as the prototype hcon, then randomly sample a node feature x0in close to hcon as the initial feature of vin. To optimize the fake node's features for a more effective attack, we define a specific fake node generator f ϕin(r) g for node type ϕin(r) as follows:

where xmin is the feature of fake node vin at time step m, with an initial state x0in . xmneighbor corresponds to the feature aggregation of vin's neighbors. We set the fake node generators for different node types as distinct MLPs here.

(2) Fake Edge Selector. Then, the attacker will determine which target nodes in G to connect with the injected vin ∈ N r in , aiming to maximize disruption of the graph information. A straightforward approach is to use the gradient of Lcw with respect to the relation subgraph to guide the attack, targeting the positions where the gradient changes most significantly [Wang et al., 2020]. However, applying backpropagation to compute the gradients of each fake node's connections is challenging for large-scale graphs. We utilize an approximation strategy to simplify, after injecting vin, we linearize the surrogate model with multi-layer graph convolution and precompute the gradient ∂Lcw ∂A′m r in forward propagation, then selecting top-K absolute value as neighbors for vin:

where A′m r is the attacked relation subgraph at the m-th step after injecting vin, and [·]:,j is the j-th column in the matrix, i.e., fake node. Details are in the Appendix A.

4.3 Applications of Perturbation

Built on the foundation principles of the surrogate model and relation-wise attack, the perturbed HG, G ′ = (A′ , F ′ ), generalizes to degrade downstream HGNNs and quickly adapts to new HGs through simple fine-tuning.

Degrading Target HGNNs. The attacked G ′ can be directly used to degrade predictions of various target models:

where ftarget(·) can be any trained target HGNN, without the need to modify its internal architecture or parameters. ˆ Ytarget is the prediction on the perturbed HG, which performance will significantly decrease compared to the original HG.

Adaptation to New HGs. HeTa has two parts of trainable parameters, i.e., the surrogate model and the fake node generators. Assume we have trained a surrogate model fθ∗ and a set of fake node generators fg∗ = {f (k) g∗ }K k=1 on G1. Now, for a new graph G2 that may have a different distribution from G1, we can quickly adapt to G2 by freezing fg∗. Specifically, the fθ can be easily retrained due to its lightweight nature. Then, we can randomly select J frozen fake node generators from fg∗ for the new graph G2, provided that J <= K.

4.4 Additional Analysis

Remark 4.1. Given a HG with a set of relation-aware attack units A = {A1,A2, ...,A|R|}, for each Ar ∈ A, the vulnerability of the target node to the semantic unit r increases as the degree of the node decreases.

Proof: We focus on the attack unit Ar when injecting vin.

where A′r ∈ R|N+1|×|N+1| , er is the injected edge set, D′r is the degree matrix of A′r . d1 is the degree of the fake node with existing nodes, while d2 is the degree of the fake node (set as K). Given by ˆ A′ r = ˜D- 12 r (A′r +I) ˜D- 12 r , ˜Dr =Dr+I. For simplicity, let λ = ˜Dr + d1, GD = λ- 1 2 (A′r + I)λ- 12 , dr = d2 + 1. For the alignment feature H from Eq.(3), the learnable parameters in the surrogate model denotes as W2, the gradient ∂Lcw ∂er can be derived as follows:

where D∗ r represents the degree information of the original graph G after injecting vin. IV is index set for test nodes. In this way, the first term can be ignored as it does not involve the injected fake nodes. We then analyze and simplify the second term as:

We observe that as λ decreases, i.e., the degree of the target node decreases, the gradient increases, making the node more susceptible to attack. Details are provided in the Appendix A.

5 Experiments

5.1 Experimental Settings

Datasets. In our experimental evaluation, we utilize three HG datasets: DBLP 1 , ACM 1 , and IMDB 2 . Details of these datasets are displayed in Appendix B.1.

Target HGNN Backbones. We validate the effectiveness and generalizability of HeTa on four widely used HGNNs, i.e., HAN [Wang et al., 2019], HGT [Hu et al., 2020], RGCN [Schlichtkrull et al., 2018], SimpleHGN [Lv et al., 2021]. Under evasion attacks, these HGNNs are trained on the clean graph and remain frozen parameters during evaluation.

Attack Baselines. We compare two types of baselines: (1) Heterogeneous graph attacks: specifically [Zhang et al., 2022], called RoHe-attack. Given the lack of injection attacks tailored for HGs, we also compare (2) Homogeneous graph attacks: FGA [Chen et al., 2018], G2A2C [Ju et al., 2023]. The details are in the Appendix B.2.

Implementation Details. The implementation details of the experiments are provided in Appendix B.3, and the pseudo-code for HeTa can be found in Appendix C.

5.2 Overall Performance

We conduct attacks on the surrogate model and use the perturbed graph obtained as the input for the target model, the results are shown in Table 1. We have the following observations: (1) The proposed HeTa achieves state-of-the-art HeTa G 2 A2C

1 https://github.com/THUDM/HGB

2 https://github.com/seongjunyun/Graph Transformer Networks

Figure 4: Results on IMDB dataset. 'Clean': no attack; 'IMDB': attacker trained on IMDB; 'trans ACM': attacker trained on ACM and adapted to IMDB. SHGN is SimpleHGN.

(SOTA) performance across all datasets and backbones. This further substantiates the effectiveness of HeTa in HGNN attack. Specifically, with a 0.01 node injection, compared with the best baseline attack, performance drops are up to 19% in IMDB, nearly 20% in DBLP, and almost 35% in ACM. (2) Our proposed HeTa can generalize across various target HGNN models. Surprisingly, the perturbations trained on the surrogate model achieved SoTa attack across all target models, causing significant performance degradation. Notably, with a 0.01 node injection, the average performance degradation by nearly 12% in IMDB, 15% in DBLP, and 19% in ACM. This generalization is attributed to the unified modeling of different HGNNs based on relational semantics.

5.3 Merits of HeTa

HeTa achieves cross-graph transferability. We pretrain the fake node generator in HeTa on the ACM dataset, freeze its parameters, and only fine-tune the surrogate model to adapt to the IMDB dataset. For G2A2C, we also freeze its generator and finetuning with its own loss. The results in Figure 4 (and additional results in Figure 9 in the Appendix) show that the performance of trans ACM is close to that of IMDB, particularly on RGCN and HGT, where they are nearly identical. HeTa shows strong cross-graph transferability, this is because our attacker has learned universal characteristics within HGs, enabling it to efficiently adapt to new graph distributions.

Universality of our foundation surrogate model. We conduct experiments to validate the effect of dropping relation subgraphs with varying importance assigned by µ in Figure 5a. According to µ, it indicates that R1 (author-paper) > R2 (paper-term). The results show that removing R2 has little impact, while removing R1 causes a significant performance drop across all HGNNs. Notably, RGCN's performance drops sharply after removing R1, as it relies heavily on R1. This suggests that HeTa can identify the unified importance distribution of relations across various HGNNs.

HeTa exhibits strong data efficiency. We sample a small subset of nodes from the full training data at different ratios to create a new dataset, as shown in Figure 5b. Thanks to the minimal number of parameters in our surrogate model, which enables efficient training use of limited data. Specifically, when using only 25% of the training data, the attacker already achieves performance comparable to that with the full dataset, highlighting its data efficiency.

ACM

IMDB

Figure 6: Ablation study with an injection rate of 0.01.

5.4 Model Analysis

Ablation Study. Since a key design of HeTa is the selection of fake edges, we replace this strategy with random edge selection at an injection rate of 0.01, as shown in Figure 6. From the result, the full method achieves the best performance, demonstrating that our key design can significantly degrade the performance of the target model.

Hyper-parameter Study. We analyze the impact of the injection degree K and the penalty term β in Figure 3. K controls the influence range of injected nodes, and β guides the selection of attack relations. Smaller K enhance attack effects by carefully selecting neighbors within a limited influence range, maintaining low visibility. However, larger K values can enhance attacks by broadening the influence. Attack effects initially improve with β, peaking at β = 1.8, and then deteriorate due to excessive punishment causing attack dispersion. More results are presented in Appendix D.1.

5.5 Conclusion

In this study, we introduce the foundation attack model within HGNNs, HeTa, which identifies shared attack patterns based on relational semantics, thereby enabling the attack process on HGs to generalize. We design a lightweight surrogate model to simplify various HGNN propagation mechanisms and model the important distribution of shared relational semantic units. Then we propose a relation-by-relation serialized attack process, which involves injecting adversarial nodes into each relation and generating fake edges. Experiments conducted on three datasets across four HGNN backbones have demonstrated that our method not only outperforms existing attack models but also exhibits remarkable generalization ability.

Acknowledgements

This work was supported in part by the Zhejiang Provincial Natural Science Foundation of China under Grant LDT23F01015F01, in part by the Key Technology Research and Development Program of the Zhejiang Province under Grant No. 2025C1023 and in part by the National Natural Science Foundation of China (No. 62372146, 62322203, 62172052).