Backdoor Attack on Vertical Federated Graph Neural Network Learning

1 Introduction

Graph Neural Networks (GNNs), with their powerful capability to process graph-structured data, have demonstrated significant value in cross-domain applications such as bioinformatics, chemical analysis, medical diagnosis, and financial risk management [Wu et al., 2020]. Specifically, in financial fraud detection scenarios, the use of transaction relationship graphs to identify potential fraudulent activities highlights the unique advantages of GNNs [Cheng et al., 2023]. However, in real-world settings, graph data is often distributed across different stakeholders, and due to data privacy regulations and the need to protect commercial secrets, traditional centralized training paradigms face severe challenges [Liu et al., 2024].

∗Corresponding author

Federated Graph Neural Networks (FedGNN), as a combination of Federated Learning (FL) and GNNs, provide an innovative solution to this challenge [He et al., 2021]. Among them, Vertical Federated Graph Neural Networks (VFGNN) demonstrate unique value in cross-organizational collaboration scenarios due to their ability to handle heterogeneous distributions of features and labels [Mai and Pang, 2023]. For instance, as shown in Figure 1, in a credit evaluation system, financial institutions hold user transaction records and credit labels, social media platforms possess social graphs, and e-commerce platforms provide consumer behavior features. This collaborative multi-party data setting is a typical application scenario for VFGNN.

Although VFGNN effectively protects privacy in distributed scenarios, it also faces significant security challenges, with backdoor attacks being a major potential threat. Attackers can implant concealed trigger patterns to induce specific inputs to produce predefined malicious outputs while maintaining the model's normal predictive performance, posing severe risks to the practical application of VFGNN. For example, in the credit evaluation scenario illustrated in Figure 1, malicious participants could use backdoor attacks to enable high-risk users to obtain credit approvals, leading to serious financial security issues. However, research on backdoor attacks targeting VFGNN remains nearly nonexistent. This is primarily due to two major challenges faced by traditional backdoor attacks in VFGNN scenarios: first, the label isolation mechanism among participants restricts traditional attack paths based on label manipulation; second, the complex topology of graph data requires backdoor triggers to not only maintain structural consistency but also satisfy concealment requirements.

To address the above challenges, this paper proposes a novel graph-structured backdoor attack method based on multi-hop adjacency relationships, termed BVG. This method innovatively designs a backdoor injection mechanism tailored for VFGNNs. First, it employs a multi-hop adjacency trigger generation algorithm to covertly propagate target-class features within the graph structure. Second, a backdoor retention strategy is adopted to enhance the attack's stability. Experimental results demonstrate that BVG requires knowledge of only four target-class nodes to achieve an attack success rate of over 99%, with minimal impact on the performance of the main task. The main contributions of this paper are as follows:

• Reveal backdoor attack risks in VFGNNs: A systematic analysis of security threats within the VFGNN framework highlights unique risk characteristics distinct from traditional scenarios.
• Design multi-hop graph structural triggers: A bilevel optimization strategy generates backdoor triggers for graph propagation, enabling flexible and covert backdoor injection without disrupting the graph structure.
• Develop a backdoor retention strategy: This effectively addresses instability issues in backdoor injection during federated training, improving attack persistence.
• Validate effectiveness through experiments: Extensive experiments on widely-used benchmark datasets demonstrate that BVG is efficient and stable, maintaining high attack success rates even under various backdoor defense mechanisms.

2 RelatedWork

In the fields of VFL and GNN, researchers are investigating backdoor attacks specifically tailored to each domain.

2.1 Backdoor Attacks on VFL

Federated Learning is especially vulnerable to backdoor attacks due to its distributed nature [Zhang et al., 2024]. However, the vertically split model of VFL restricts the attacker's access to the training labels, let alone modify them.

There are two notable directions in attempting to solve this issue. The first is to conduct label inference attacks [Fu et al., 2022] to get some labels in advance. For example, VILLAIN [Bai et al., 2023] leverages label inference to pinpoint samples of the target label and then poisons these samples to inject the backdoor. BadVFL [Naseri et al., 2024] and LR-BA [Gu and Bai, 2023] assume attackers can acquire labels of a certain number of samples from each category with label inference. Another direction is to make the knowledge of a small number of labeled samples from the target class a prerequisite [Chen et al., 2024; Chen et al., 2023a; He et al., 2023]. These methods try to use as few as possible (e.g., 500 for [Chen et al., 2024] and 0.1% for [Chen et al.,

2023a]) the labeled target-class samples to establish links between backdoor triggers and target labels. Normally, in VFL, the backdoor attack can only be conducted in a clean-label manner [Zhao et al., 2020]. Therefore, works like TPGD [Liu et al., 2022] assuming the label modification capability of the active party are impractical.

2.2 Backdoor Attacks on GNN

The unique challenge to graph-oriented backdoor attacks lies in the inherently unstructured and discrete nature of graph data [Xi et al., 2021]. For structured and continuous data like images, attackers can directly stamp a trigger pattern (e.g., a black square on the bottom right of the image) s onto a benign image x to achieve a poisoned sample xp = x + s [Li et al., 2022a]. However, the backdoor attacks against GNN involve design triggers within a large spectrum, including topological structures and descriptive (nodes and edges) features [Xi et al., 2021]. The effectiveness of backdoor attacks largely depends on designing triggers tailored to the specific attributes of the target task. These triggers mainly fall into three categories: malicious subgraph structures, graph structure perturbations, and node attribute manipulation.

Malicious subgraph structures involve adding malicious subgraphs to nodes [Dai et al., 2023], edge endpoints [Zheng et al., 2023], or specific positions in the graph [Zhang et al., 2021; Xi et al., 2021], causing nodes, edges, or graphs to be misclassified. Graph structure perturbation involves injecting special node connections into the training set adversarially, allowing backdoor attacks to be executed by merely modifying the graph's topology during the attack [Yang et al., 2022]. Node attribute manipulation involves carefully designing special node features and adding them to the target class nodes in the training set, followed by adaptive optimization of the graph structure to train a GNN model with backdoors [Xing et al., 2023; Chen et al., 2023b]. Although these methods are viable in centralized GNN scenarios, they all rely on full access to the training set, which is nearly impossible in VFGNN.

The aforementioned backdoor techniques, whether tailored for GNN or VFL, are not applicable to VFGNN due to unique threat models. Existing methods such as CBA, DBA, and Bkd-FedGNN focus on HFGNN and do not address the needs of VFGNN [Xu et al., 2022; Liu et al., 2023]. VFL backdoor attack methods lack consideration for the data structure of graph data, while GNN backdoor attacks face difficulties in handling vertically partitioned data. To address these issues, this paper proposes the BVG algorithm for VFGNN, leveraging multi-hop triggers and a backdoor retention strategy to achieve efficient backdoor attacks.

3 Proposed Approach

In this section, we formalize the backdoor attack problem in VFGNN and provide a detailed threat model. Next, we present our attack method, with a sketch of the entire approach shown in Figure 2.

3.1 ProblemFormulation

Graph data is represented as G = (V,E,X), where V = {v1, . . . , vn} is a set of N nodes, E ⊆ V × V is a set of edges, and X = {x1, . . . , xN} is a set of node attributes, with xi being the attribute of node vi. The adjacency matrix of graph G is denoted as A ∈ RN×N , where Aij = 1 if nodes vi and vj are connected; otherwise, Aij = 0.

We focus on the node classification problem, which is common in real-world applications like social networks. In inductive node classification tasks, only a subset of nodes VL in the training graph have labels YL = {y1, . . . , yNL }. The test nodes VT are disjoint from the training nodes.

In VFGNN, K (K >= 2) participants collaboratively train a model using their private data. Each participant k has its own local graph Gk = (V,Ek ,Xk ), which comprises the entire node set V , a subset of edges Ek , and a subset of feature data Xk [Chen et al., 2020]. From a global perspective, all participants collectively own a global graph Ggl = (V,Egl ,Xgl ), where Egl = E1 ∪ . . . ∪ EK , and for any node attribute in X, xgl i = x1i || . . . ||xKi , where || is the concatenation operator. One of the K participants is an active party that knows the corresponding labels of the labeled node set VL ⊆ V , and all other participants are negative parties that have no access to the label information.

Each participant employs a local GNN model fk parameterized by θk to compute the local output Hk i = fk(G k i ; θk), where G k i denotes the computation graph of node vi. In addition to training its own local model, the active party also trains a top model G parameterized by θtop, which aggregates the outputs from all local models to minimize the loss function L. Therefore, the VFGNN model training can be formulated as

where Θ = {θ1, · · · , θK; θtop} represents the parameters of the overall VFGNN model.

As an adversary in a backdoor attack, the main objectives are threefold: first, to ensure that the federated learning task can be completed successfully; second, to establish a mapping between the trigger and the backdoor target class; and third, to ensure that the backdoor injection remains undetected by the active party. These three objectives must be achieved simultaneously during the VFGNN training process. Specifically, the attacker needs to inject the backdoor cleverly, ensuring that the training process is not disrupted and that no suspicious behavior is exposed. After the VFGNN model is deployed, the attacker can introduce a local trigger to deliberately misclassify the corresponding sample as the target class, thereby completing the backdoor attack. The backdoor attack objective in VFGNN is

where F refers to the VFGNN model, which encompasses both the top model and the bottom models of all participating parties. δ represents the backdoor trigger, a(·) denotes the operation of trigger attachment, and τ is the backdoor target class. ˜H denotes the output of the bottom GNN model after the trigger injection, while H refers to the output without trigger injection.

3.2 Threat Model

We assume the adversary is a passive party, not the active party, because the active party can modify labels and thus easily perform backdoor attacks. All other participants are considered trustworthy.

Adversary's Capacity. The adversary adheres to the VFL protocol, transmitting local features and receiving gradients without manipulating other participants' information.

Adversary's Objective. In VFGNN multi-classification tasks, the adversary's objective is to inject a backdoor into the model during the training phase without being detected. When the poisoned model is deployed for applications, it will misclassify any local data with the backdoor trigger as the designated target class but maintains classification capacity for all other clean data.

Adversary's Knowledge. In backdoor attacks, the adversary requires only a very few training samples labeled target class. Although this requirement deviates from the original VFGNN setting, it is feasible in practical VFGNN applications because it is possible for an adversary to acquire a small number of target class samples through various means, such as direct purchasing [Fu et al., 2022; Gu and Bai, 2023]. Our experiment results indicate that acquiring only one to four target class nodes is sufficient for a successful backdoor attack.

Apart from these limited target samples, the adversary has no information about the models and data of other parties.

3.3 Multi-hop Trigger Generation

Due to the special nature of the VFGNN architecture, all participants are aware of all nodes in the dataset, but possess different attributes of the nodes. Therefore, the adversary cannot generate a subgraph structure as a trigger like common GNN backdoor attacks [Dai et al., 2023; Wang et al., 2024]. Here, the trigger is added to the node attributes. To prepare a trigger, we propose a multi-hop trigger generation method without introducing new nodes. The trigger generation and training are conducted synchronously with the VFGNN model. Additionally, to enhance optimization efficiency, we introduce a hyperparameter ϵ as a trigger threshold. By appropriately setting this threshold, we ensure the stealthiness of the trigger while simplifying the optimization task from a triple optimization to a dual optimization. We use the PGD method [Madry et al., 2018; Huang et al., 2021] to generate the trigger. The optimization formula for the trigger is as follows:

where t is the step index, Gp represents the computation graph of the node vp to inject the trigger, where vp ∈ Vp. ∇δL(F (a(Gp, δt);Θ∗ ) , τ) denotes the gradient of the loss function for the backdoor target class with respect to the trigger, α is the step size, Πϵ keeps δ within an ϵ-ball at each step, F(Θ∗ ) refers to the pre-trained VFGNN model. sgn(·) denotes the sign function.

The multi-hop trigger δ affects the target node and its neighbors, δ = {δ0 , δ1 , · · · , δM }. Here, δm is the trigger added to the attributes of the m-hop neighbors of the target node vp. Therefore, the operation of adding triggers to Gp can be expressed as

where xp is the attribute of node vp, Xm-hop are the attributes of the m-hop neighbors, and δ0 , δm are the triggers added to these attributes, respectively.

According to (3), the generation of the trigger relies on the gradients of the target class nodes τ. The generation of the trigger and the training of the VFGNN model are accomplished together, which can be expressed through the following bi-level optimization:

where the trigger δ is trained according to all known target class nodes VP available to the adversary, VP ∈ VL. Essentially, this trigger serves as a universal trigger for the target class τ [Shafahi et al., 2020; Zeng et al., 2022].

Algorithm 1 Multi-hop Trigger Generation

Require: Training dataset G; number of MTG epochs T ; target class nodes VP with target label τ

Ensure: trigger δ, model parameters Θ

• 1: Initialize: δ ← 0.
• 2: while not reached T do
• 3: for vi in VL parallel do
• 4: Adversary A: updates {G A i = a(GA i , δ)}vi∈VP .
• 5: Passive party:
• 6: for each party k = 1, 2, . . . , K parallel do
• 7: k computes embedded features Hk i using its bottommodel fk.
• 8: end for
• 9: Active party:
• 10: computes Eq. (1), then updates θTop using ∂L ∂θTop .
• 11: sends ∂L ∂Hi to all parties.
• 12: Adversary A:
• 13: computes ∇δL with { ∂L ∂Hi ∂Hi ∂δ }vi∈VP
• 14: updates δ with Eq. (3)
• 15: Passive party:
• 16: for each party k = 1, 2, . . . , K parallel do
• 17: k computes ∇θk L = ∂L ∂Hi ∂Hk i ∂θk .
• 18: k updates model parameters θk.
• 19: end for
• 20: end for
• 21: end while

Algorithm 1 outlines the procedure of the proposed attack. In each iteration of VFGNN model training, the adversary A injects the trigger δ into the local computation graph of known target class samples VP according to (4) (line 4). Subsequently, each participant k computes the node embeddings through the bottom model fk (lines 5-8), where Hk i represents the embedded features of the i-th data from the k-th participant. Upon receiving these embedded features, the active party computes the gradients of the loss function with respect to the top model and the embedded features of each participant according to (1). The top model is then updated, and the gradients of the loss with respect to the embedded features ∂L ∂Hi are transmitted to each participant (lines 9-11), where Hi denotes the aggregation of the embedded features from all participants for the i-th data. After receiving the gradients, the adversary computes ∇δL and updates the trigger using (3). The current model parameters serve as the pretrained model F(Θ∗ ) (lines 12-14). Finally, each participant updates its bottom model based on the gradients sent by the active party (lines 15-19).

3.4 Backdoor Retention

When injecting backdoors, using only a small number of samples may lead to unstable effects. For instance, a backdoor may perform well in one epoch but degrade suddenly in the next. To ensure the stability of backdoors, we propose a method called Backdoor Retention (BR).

The BM method consists of two key steps. First, the attacker evaluates the impact of the backdoor. Since the attacker cannot directly access the output of the VFGNN model during training, they rely on an assumption: if the backdoor is successfully injected, the outputs H of nodes triggered by the injection should exhibit high similarity. Based on this assumption, the backdoor effectiveness E is approximated using the following formula:

where n is the number of nodes involved in the trigger injection, and Hi represents the output of node vi in the attacker's bottom model.

After estimating E, the attacker performs the following actions in each epoch: if E exceeds a predefined threshold, the attacker updates the bottommodel and trigger; otherwise, the model and trigger from the previous epoch are retained. This approach ensures the stability and effectiveness of the backdoor throughout the training process.

4 Experiments

4.1 Experiments Settings

Local GNN Models

To demonstrate the effectiveness of BVG in VFGNN settings with different local GNN structures, we use three common GNNmodels as local participants:

Graph Convolutional Network (GCN) [Kipf and Welling, 2016]: GCN captures local features by propagating and aggregating information between nodes and their neighbors. Each local GNN model in VFGNN uses a two-layer GCN.

Graph Attention Network (GAT) [Veliˇckovi´c et al., 2017]: GAT uses an attention mechanism to assign adaptive weights to neighbor nodes, enhancing the model's ability to focus on important nodes.

Simple Graph Convolution (SGC) [Wu et al., 2019]: SGC simplifies GCN by removing nonlinear activations and reducing layers, making it more efficient while retaining essential graph structural information.

To ensure a fair comparison with previous studies [Chen et al., 2022], we use a two-layer GNN model for each participant's local GNN to extract local node embeddings, with the dimension set to 16. The number of hidden units is fixed at 32. For GCN and GAT, the activation function is ReLU. VFGNN is trained using Adam, with a learning rate of 0.01.

Datasets

This paper uses three widely adopted public datasets to evaluate the performance of BVG, including Cora [McCallum et al., 2000], Cora ml [McCallum et al., 2000], and Pubmed [Sen et al., 2008]. The basic dataset statistics are summarized in Table 1.

Each participant in the VFGNN framework has access to all the nodes in the datasets, but the node features are equally split among the participants. We randomly split the edges of the graphs into equal parts, one for each participant, without overlapped edges between any two participants. We assume the adversary knows only four target class nodes (i.e., |Vp| = 4), which are randomly selected from the training set.

Performance Metrics

To evaluate the performance of the BVG method, we use three common metrics: Attack Success Rate (ASR), Main Task Accuracy (MTA) [Li et al., 2022b], and Mean Squared Error (MSE). Among them, ASR and MTA are the most commonly used evaluation metrics for backdoor attack tasks. ASR measures the proportion of samples in the backdoor test set that are predicted as the target class by the poisoned model. On the other hand, MTA assesses the accuracy of the clean test set on the poisoned model. MSE is used to measure the difference in the output of the bottom GNN model before and after trigger injection. A smaller MSE indicates that the injected trigger is less detectable by the active party, implying better stealth.

Comparison Benchmarks

Due to the lack of research on backdoor attacks in VFGNN, we selected three attack methods from other scenarios for comparison, adapting them to fit VFGNN's tasks and structure. Additionally, we incorporated common GNN backdoor trigger schemes for further comparison. The methods are summarized below:

GF [Chen et al., 2022] Originally designed for adversarial tasks in VFGNN, this method was adapted to minimize the loss of the backdoor class. It involves querying participant embeddings, training a proxy model, and generating an adversarial graph on the proxy model.

TECB [Chen et al., 2023a] A VFL backdoor attack method for image data, adapted here for graph tasks by aligning target node attributes with trigger embeddings. It operates in two stages: training triggers with limited labels and aligning target gradients using the trigger.

VILLAIN [Bai et al., 2023] Designed for VFL backdoor attacks, this method injects triggers into the bottom model's output H, supporting clean-label attacks. It combines label inference using limited labeled samples and data poisoning with trigger masking and randomness for enhanced robustness.

Edge Triggering (ET) This method connects attack nodes to target class nodes via edges, creating a trigger relationship that exploits the graph's topology to influence target node classification.

Node Feature Triggering (NFT) Backdoor attacks are achieved by injecting trigger patterns into nodes with known labels, altering their features to misclassify attack nodes as the target class under specific triggers.

Node Feature Replacement (NFR) Attackers replace the features of attack nodes with those of target class nodes, making their features similar to the target class and inducing misclassification.

4.2 Experiment Results Analysis

Backdoor Task Evaluation

We conducted experiments in a VFGNN framework with two participants, as shown in Table 2. BVG and NFT perform best on the main task, with slight variations across datasets and models. For the backdoor task, BVG consistently achieves the highest attack success rate across all tested models and datasets, demonstrating its effectiveness with minimal impact on main task performance.

We also evaluated the proposed attack method's performance in multi-party VFGNN scenarios where multiple participants are involved. Unlike the two-party setting, multiparty scenarios become more complex due to the increased number of participants and their interactions. Our evaluation focuses on how the presence of multiple participants affects the ASR and the MTA of BVG.

We conducted experiments with two, three, and four participants to evaluate the scalability and effectiveness of the proposed backdoor attack method in multi-party VFGNN scenarios. Each participant was assigned a subset of the graph's edges and node features, with one active party holding the labels for the labeled node set VL. The passive participants, including the adversary, only had partial information about the graph. The experimental results are shown in Figure 3.

The results indicate that the main task accuracy slightly decreases as the number of participants increases. This trend could be attributed to the increased complexity and noise introduced by multiple participants. The backdoor attack success rate remains high across all multi-party settings but slightly decreases as the number of participants increases. The obtained results verify that our attack method is effective even in more complex multi-party environments. The slight decrease in success rate may be due to the dilution of the adversary's influence with more participants.

Backdoor Stealthiness Evaluation

In evaluating the stealthiness of backdoors in VFGNN, we measure the difference in the intermediate layer features of the same node before and after the backdoor injection. If the intermediate layer features show little change after the backdoor injection, we consider the backdoor difficult for the attacker to detect. For comparison, we selected several methods from Table 2 that perform relatively well on the backdoor task, with a particular focus on the performance of the BVG method under multi-hop triggers. Figure 4 shows the backdoor task performance and the average difference in intermediate layer features for five methods across three datasets.

From Figure 4, it is evident that the increase in MSE correlates positively with the increase in ASR. However, despite BVG achieving a significantly higher ASR than VILLAIN, its MSE is much lower than VILLAIN, indicating that BVG exhibits better stealthiness. For the other methods, BVG has slightly worse stealthiness but significantly better ASR performance. More importantly, the ASR performance of ET, NFT, and NFR has almost plateaued.

Attack Efficacy under Defense

To evaluate the robustness of the BVG method, we explored potential backdoor defense strategies within the VFGNN framework. We considered two main types of defense: the first type is GNN backdoor defense methods, such as Prune and Prune+LD [Dai et al., 2023]. These methods defend against backdoor attacks by pruning the edges between nodes with low similarity. Pruning these edges can disrupt the attacker's trigger structure and connections. However, VFGNN's architecture prevents defenders from pruning the adversary's data, making these methods unsuitable.

The second type of defense methods is specific to the VFL framework and can be divided into two categories: label inference defense and backdoor attack defense. Label inference defense operates on the assumption that backdoor attacks often require access to a large amount of label information. To prevent label leakage, defense methods perturb or compress gradients to minimize information leakage. Two representative methods are DP-SGD and gradient compression (GC). DP-SGD provides differential privacy protection by adding noise to gradients [Fu et al., 2022], where the larger the noise amplitude, the smaller the privacy leakage, and vice versa. The GC method [Fu et al., 2022; Kairouz et al., 2021] sends only a subset of gradients with the largest absolute values to participants, thereby reducing privacy leakage. For backdoor attack defense, there are mainly two approaches: one is model reconstruction, which aims to purify the top model of the active party to remove the backdoor, with methods such as model pruning [Liu et al., 2018] and adversarial neuron pruning (ANP) [Wu and Wang, 2021]. The other approach is to introduce interference into intermediate-layer features [Li et al., 2021], such as embedding Gaussian noise into the intermediate features provided to the passive party to disrupt potential backdoor triggers.

In the VFGNN framework, we implemented several VFL backdoor defense methods, each with five parameter settings, as shown in the figures. We present the experimental results when the base model is GCN, and similar conclusions are observed for GAT and SGC models.For label inference defense, as shown in Figures 5 and 6, our method is minimally affected, as the BVG method itself does not rely on label inference. For backdoor attack defense, the results of the ANP method are shown in Figure 7. The ANP method primarily affects model accuracy without effectively suppressing the backdoor. For the defense method involving interference with intermediate-layer features, the experimental results are shown in Figure 8. As model accuracy decreases, the success rate of backdoor attacks also drops, making it difficult for defenders to reduce ASR while maintaining a high MTA.

5 Conclusion

In this paper, we proposed the BVG method for backdoor attacks to Vertical Federated Graph Neural Network (VFGNN). Utilizing a multi-hop trigger generation approach, the BVG method can perform efficient backdoor attacks with very limited knowledge of target class nodes. Extensive experiments on three datasets with three GNN models demonstrate that BVG achieves a high attack success rate while having a minimal impact on the main task accuracy and is unlikely to be detected by the active party. The evaluation of BVG efficacy under various defense methods highlights the robustness and efficiency of the proposed attack method, underscoring the necessity for advanced defense mechanisms in practical federated learning applications to counter such sophisticated backdoor attacks.

Acknowledgments

This work is supported by the National Key Research and Development Program of China (2022YFC3302300), Yangtze River Delta Science and Technology Innovation Community Joint Research Project (YDZX20233100004031), National Natural Science Foundation of China (No. 61873309, No. 92046024, No. 92146002) and Shanghai Science and Technology Project (No. 22510761000). We thank all contributors to the open-source libraries used in this work. Our implementation is publicly available at https://github.com/ yangjr01/VFGNN backdoor.