GraphProt: Certified Black-Box Shielding Against Backdoored Graph Models

1 Introduction

The abundance of graph data has led to the widespread adoption of graph learning models, such as Graph Neural Networks (GNNs), across diverse domains including social network analysis [Fan et al., 2019], molecular biology [Wieder et al., 2020], and recommendation systems [Safae et al., 2023; Wu et al., 2021]. With the increasing complexity of these models, there is a growing trend to outsource the training process to third parties, giving rise to a popular business model known as Machine Learning as a Service (MLaaS). While MLaaS can significantly simplify model training, it concurrently raises critical security concerns, particularly backdoor risks. Specifically, adversaries utilize poisoning training to implant backdoor and exploit trigger-embedded inputs to activate it for output manipulation.

∗Corresponding author.

To mitigate graph backdoors, several defense methods have been developed. Those methods leverage explainability to identify and remove triggers based on external tools, modelrelevant details, and loss functions [Jiang and Li, 2022; Downer et al., 2024], or employ additional benign samples or model parameters for fine-tuning to mitigate backdoor impact [Zhang et al., 2024; Yang et al., 2024]. However, to safeguard the privacy and intellectual property of the model owner and prevent extraction attacks, defenders are commonly prohibited from using the aforementioned model-related information or utilizing auxiliary data to fine-tune the model. This restriction makes it challenging to implement current methods in MLaaS scenarios.

To address the limitations, we deploy input subgraph details for prediction to mitigate backdoor effects induced by triggers. Within malicious graph input, trigger is the functional component, despite comprising a small fraction. Suppose the subgraph entirely lacks the trigger or contains only a trivial fragment, the backdoor will remain dormant and fail to activate. For one malicious input, most predictions of its subgraphs are typically normal. Hence, we determine output by majority vote on predictions of subgraphs within suspicious test graphs to avoid malicious results in testing. For benign samples, assuming that the subgraph incorporates sufficient feature-rich information, the accuracy of majority vote can be guaranteed.

Based on this insight, we propose GRAPHPROT, a certified black-box defense method against backdoor attacks on GNN-based graph classifiers. It functions within the testing phase to ensure robust output, irrespective of input maliciousness or benignity, demanding exclusively graph inputs. Specifically, for the test input, we first implement designed feature clustering and topological clustering to filter out the potential anomalous parts maximally. Subsequently, multiple subgraphs are sampled from the filtered graph utilizing three proposed methods, founded on topology connectivity and node characteristics. Finally, we use one devised ensemble classifier to predict the subgraphs and perform majority vote on the results to derive the inference decision for the input. Additionally, we provide a certified robustness proof for GRAPHPROT, showing that, under specific trigger size, no further attack attempts can compromise its certified efficacy-regardless of trigger type or target. The proposed method is depicted in Fig. 1. Our contributions are listed as follows:

• We propose GRAPHPROT, a provable black-box backdoor defense method for graph classifiers, which operates solely on the input test graph and several queries. The method functions independently of model-specific knowledge, supplementary resources, or external tools.
• In GRAPHPROT, we introduce a graph anomaly filtering method to maximally eliminate segments with significant anomalies in both features and topology. Moreover, we devise three subgraph sampling strategies based on topology and node characteristics.
• Evaluation results reveal that GRAPHPROT can effectively reduce attack success rates, attaining efficacy comparable to white-box defenses and exhibiting marginal reductions in benign data accuracies.

2 RelatedWork

2.1 Graph Neural Backdoor Attack

This attack aims to manipulate graph models to output adversary-prescribed targets upon receiving triggerembedded graphs.

Backdooring graph model is implemented by datapoisoning [Xi et al., 2021; Zhang et al., 2021; Li et al., 2024]. Adversaries incorporate premeditated triggers ∆ into part of training graphs Dtr and modify their ground truths as targets y∆ to compel the model f(·) to learn the mapping between ∆ and y∆ in training. The trained f(·) misclassifies triggerembedded graphs as y∆, while correctly classifying benign data.

To adapt backdoors to multiple graph learning scenarios, the data-poisoning paradigm has been improved to suit the demands of federated learning, contrastive learning, prompt learning, and hardware-based graph systems [Xu et al., 2022; Zhang et al., 2023; Lyu et al., 2024; Alrahis et al., 2023]. Moreover, several studies augment backdoor efficiency, efficacy, and concealment through explainability, transferability, multi-targets, and spectrum [Xu et al., 2021; Zheng et al., 2024; Yang et al., 2022; Wang et al., 2024; Zhao et al., 2024].

2.2 Graph Neural Backdoor Defense

Currently, only several defenses are researched for graph backdoors, which identify and eliminate triggers within test graphs to detect attacks and avoid backdoor activations.

Graph classification backdoor defense is initially explored via explainability tools and available poisonous data to set thresholds for recognizing and removing malicious triggers [Jiang and Li, 2022]. Moreover, clustering is introduced to identify triggers and utilize model structure details for finetuning to enhance robustness [Yang et al., 2024]. Also, explainability metrics from logits and topology are harnessed to inspect sample poisoning [Downer et al., 2024].

3 Background

3.1 Graph Classification

A graph is represented as G = (V,E,X) ∈ G , where V = {v1, v2, . . . , vn} is a set of n nodes, E denotes the set of edges connecting the nodes in V , and X ∈ Rn×d signifies d-dimensional feature for all nodes v ∈ V . With a training set Dtr = {(Gi, yi)}ni=1 containing training graphs Gi and their corresponding ground truth yi ∈ Y, a graph classifier f(·) : G → Y can be trained. Given a testing graph G, the model can then be utilized to predict its label: f(G) = ˆ y. Typically, the graph classifier is a GNN-based model such as GCN, SAGE, and GAT [Kipf and Welling, 2017; Hamilton et al., 2017; Veliˇckovi´c et al., 2018].

3.2 Threat Model

Graph model owners can externalize the training to MLaaS providers and provision trained models for end-user interaction. However, adversaries can implant backdoors by compromised training processes or data-poisoning. To counter these vulnerabilities, defenders must implement countermeasures, while upholding privacy and intellectual property protection policies.

Adversary's Goals and Capabilities

Given a graph classifier f(·), the adversary aims to embed backdoor within f (·), which misclassifies graphs with trigger ∆ = (V ∗ ,E∗ ,X∗ ) (e.g., specific subgraph) into premeditated class: f(G ⊕ ∆) = y∆, while functioning normally on benign graphs: f(G) = y. To validate the efficacy of our method, we adopt the most stringent white-box attack setting, where adversaries can manipulate the training process, access model-concerned information, and acquire full training and additional datasets for attacks.

Defender's Goals and Capabilities

Current graph backdoor defenses work under white-box or gray-box settings, wherein the defenders have unrestricted or partial access to model-related knowledge, e.g., parameters, layer embeddings, and accessible datasets. However, due to privacy policies and access restrictions, a black-box assumption is more realistic. In this study, we adopt a strictly blackbox defense with only access to the input and limited queries.

4 Methodology

4.1 Overview

Given a suspicious test graph G, GRAPHPROT executes a three-step workflow to ensure robust inference, circumvent potential backdoor activation, and preserve benign sample accuracy. (1) We detect and purge potential anomalies by topology-feature-filtering mechanism. (2) Multiple subgraphs are sampled by leveraging both the structural topology and intrinsic node attributes. (3) These subgraphs are retained for predictions, with robust GNN inference aggregated via majority voting. The framework is shown in Fig. 1. The theoretically certified defense proof is articulated in Sec. 4.3.

4.2 DetailedMethod

Graph Anomaly Filtration

This step aims to maximally mitigate explicit anomalous nodes Vanomaly (i.e., outliers) within the test graph G (not full removal). Certain explicit Vanomaly manifest feature distributions that diverge substantially from the inherent properties and structural regularities of G. Furthermore, Vanomaly negatively impact data predictions as they significantly deviate from original dataset distribution, resulting in inaccuracies or output instability. To identify them to the maximum degree, clustering methods are employed, exploiting the disparities in their feature distributions relative to the normal dataset. Using clustering, G is subdivided into anomalous and benign components, and the smaller portion is excluded, given that Vanomaly forms only a peripheral fraction of poisoned graphs. The filtration procedure is described as follows:

where C(·) is the clustering function and G′ signifies the filtered test graph.

For clustering C(·), we harness the intrinsic attributes of graph data. Topological and feature-driven clustering methods are independently deployed to identify anomalies, acquiring discrete anomalous segments. The overlapping segment is considered anomalous, while the rest is deemed normal. The utilized clustering methods are outlined as follows:

• Topology Clustering: Some Vanomaly exhibit distinctive topology (e.g., anomalous density patterns or connectivity structures) that varies markedly from G. The Spectral Clustering is used to divide nodes V ⊆ G into two clusters via the adjacent matrix A (from E, V ). The cluster with minimal cardinality is considered anomalous.
• Feature Clustering: Vanomaly may show distinct node feature distribution (e.g., abnormal central tendency or dispersion). We utilize Gaussian Mixture to divide V ⊆ G into two clusters via feature matrix X ⊆ G and the cluster with lower cardinality is designated as anomalous.

Trimodal Subgraph Sampling

This step samples the filtered graph G′ into K subgraphs. To this end, we propose three sampling strategies, random sampling (GRAPHPROT-R), topology-sampling (GRAPHPROTT), and topology-feature sampling (GRAPHPROT-TF).

• Random Sampling (GraphProt-R): A subset of nodes VG ∈ V ′ are randomly sampled according to the samplerate p = |VG| |V ′ | and retain the topological and features of VG to form a subgraph G. This is demonstrated by

where S(·, ·) refers to the random sampling operator with two inputs: the sampling target and sample size.

• Topology Sampling (GraphProt-T): Spectral clustering is employed on the adjacent matrix of G′ to partition V ′ into ⌊ |V ′ | K ⌋ clusters. We then randomly draw one node from each cluster, with their topology and node attributes retained, to construct the subgraph G. The process is detailed below:

where S(·, ·) is the spectral clustering function with two inputs: the sampling target and the sample size.

• Topology-feature Sampling (GraphProt-TF): Based on the topology sampling results G of (GRAPHPROT-T), we further conduct a feature-level selection. For each VG ⊆ G, a fraction r of the feature dimensions is stochastically retained, preserving these values while zeroing the remainder to form the new node features X′G :

where the node feature vector xi is d-dimensional, UG indicates the selected feature dimensions, and 1UG denotes the binary mask vector.

Robust Model Inference

This step infers prediction of the suspicious test G from K sampled subgraphs {Gk}. Given {Gk} and the victim model f(·), each Gk is individually classified via f(·), with the final output determined by a majority vote ensemble. This procedure can be delineated as follows:

where g(·) is the ensemble classifier, Ny denotes the count of subgraphs predicted as the class y, and I(·) represents the indicator function. In the event of a tie, the label corresponding to the smaller index is preferentially selected.

In the MLaaS setting, we take g(G) as the final output for the suspicious test graph G, ensuring the prevention of backdoor activation while maintaining benign input accuracy. This approach operates within the constraint of querying the black-box GNN K times, without relying on auxiliary information or explainability tools.

4.3 Certifying Robustness

Although GRAPHPROT is effective in the empirical evaluation, its resilience to adaptive attacks (e.g., adaptive triggers & targets) remains uncertain. Hence, we formally propose a certified (provable) defense for our model GRAPHPROT-R so that no further attacks can compromise the certified accuracy.

If the trigger involves injecting new nodes into the graph, we find the worst-case node number of the trigger graph. Let n∆ denote the node numbers in poisoned subgraph G∆ (w/ trigger nodes and edges).

Theorem 1. (Certified robustness for graph injection trigger). Given a testing graph G, a trained backdoored graph classifier f, and the ensemble classifier g defined in Eq. (8) with random subgraph sampling (GraphProt-R). Let G denote the subgraphs with s nodes sampled from G with replacement. Suppose yA and yB are the classes with the most votes and the second largest votes during the ensemble. We define pA and pB as the lower and upper bound of probability P(f(G) = yA) and P(f(G) = yB), respectively. We guarantee that the model still predicts class yA for graphs G∆ inserted with any trigger size smaller than r if:

where n and n∆ are the node numbers in G and G∆, respectively, and δA = pA-(⌊pA ·ns ⌋)/ns , δB = (⌈pB ·ns ⌉)/ns - pB are the residuals.

Note: In the main paper, s = ⌊p · |V |⌋.

Proof. See Appendix A in the supplementary materials.

If the trigger is attached to the existing nodes (involves node feature modification and edge modification among r nodes), we have the following simplified certifying condition:

Theorem 2. (Certified robustness for in-graph trigger). Given a testing graph G, a trained backdoored graph classifier f, and the ensemble classifier g defined in Eq. (8) with subgraph random subgraph sampling (GraphProt-R). Let G denote the subgraphs with s nodes sampled from G with replacement. Suppose yA and yB are the classes with the most votes and the second largest votes during the ensemble. We define pA and pB as the lower and upper bound of probability P(f(G) = yA) and P(f(G) = yB), respectively. We guarantee that the model still predicts class yA for graphs G∆ inserted with any trigger size smaller than r if:

where n is the node numbers in G, and δA = pA - (⌊pA · ns ⌋)/ns , δB = (⌈pB · ns ⌉)/ns - pB are the residuals.

Proof. See Appendix A in the supplementary materials.

5 Experiment

In this section, we present the results of our comparative analyses and ablation studies on GRAPHPROT. Notably, it functions within rigorous black-box conditions (with access limited to the test graph and few queries). Consequently, we primarily assess whether our approach achieves comparable efficacy to current defense strategies.

5.1 Experimental Settings

Victim Models

We exploited 3 state-of-the-art (SOTA) GNN models as benchmark targets for backdoor defense: (1) Graph Convolutional Network, GCN, extending convolution operations on graphs [Kipf and Welling, 2017]; (2) SAGE, which formulates node embeddings by sampling and aggregating neighborhood features [Hamilton et al., 2017]; and (3) Graph Attention Network, GAT, deploying attention mechanisms to modulate node weights [Veliˇckovi´c et al., 2018]. The models were subjected to backdoor attacks for subsequent defense evaluations.

Attack Methodologies

We adopted 3 graph backdoor paradigms: (1) GTA, which implements a trigger generator to forge a graph model implanted with backdoor via bi-level optimization [Xi et al., 2021]; (2) SBA, harnessesing intricately designed subgraph triggers to train the backdoored model [Zhang et al., 2021]; and (3) Motif, which designs triggers using motif statistics to execute the attack [Zheng et al., 2024].

Experiment Datasets

We employed 6 benchmark datasets: AIDS [Rossi and Ahmed, 2015], ENZYMES [Dobson and Doig, 2003], DHFR [Morris et al., 2020], NCI1 [Wale and Karypis, 2006], PROTEINS [Borgwardt et al., 2005], and COLLAB [Yanardag and Vishwanathan, 2015]. For each dataset, we randomly allocated two-thirds of the graphs for training the backdoored victimmodel, preserving the remainder for empirical testing.

Comparison Baselines

The SOTA white-box defenses were opted for comparative analysis: (1) GNNSECURER, incorporating topological saliency metrics and model-intrinsic interpretability for backdoor identification [Downer et al., 2024]; (2) FINE-PRUNING, mitigating backdoor through the systematic excision of selective GNN parameters and iterative fine-tuning refinements [Liu et al., 2018]; and (3) RS, robustified GNN framework, which fortifies robustness by introducing random noise into graph, coupled with classifier smoothing [Wang et al., 2021].

Evaluation Metrics

We analyze GRAPHPROT from two dimensions: (1) defensive efficacy and (2) capacity to preserve benign input accuracy.

The effectiveness of defense mechanisms for poisoned graph is primarily assessed by attack success rate (ASR):

wherein a diminished ASR reflects better defensive efficacy. The preservation of GNN performance post-defense for benign samples is evaluated via accuracy drop (ADP) metric:

where ACCcl and ACC represent GNN accuracies on benign data for the non-backdoored (benign) and backdoored models, respectively. A suppressed ADP signifies augmented performance preservation.

Additionally, we utilize benign data accuracy of backdoored GNN (i.e., ACC) in ablation studies to observe variations.

5.2 Comparison Study

Our GRAPHPROT is evaluated in 2 aspects: (1) efficacy across various GNNs and datasets (cf. Tab. 1), and (2) robustness under diverse attack strategies and datasets (cf. Tab. 2). In the first evaluation, GTA is deployed as the attack (trigger size = 5, bi-level optimization epoch = 20). The second evaluation used SBA (5-node Erd˝os-R´enyi trigger) and Motif (trigger size = 5) for attacking GCN. The GRAPHPROT configuration includes the subgraph number K= 5, the samplerate p = 0.2, and the feature selection proportion r = 0.8.

Defense Results across GNNs and Datasets

From Tab. 1, the following observations can be discerned: (1) regarding defensive efficacy, generally, GRAPHPROT > GNNSECURER > FINE-PRUNING > RS, with ASR values of 19.7%, 20.9%, 34.1%, and 37.9%, respectively. GRAPHPROT achieves the most lowest ASRs and demonstrates better overall anti-backdoor capability (solely requires test input & K queries). (2) In terms of benign input accuracy preservation, RS > GRAPHPROT > FINE-PRUNING > GNNSECURER, with ADP values of 1.3%, 5.3%, 8.0%, and 9.7%, respectively. GRAPHPROT closely aligns with SOTA whitebox defense paradigms and shows slight ADP disparity, underscoring its competitive efficacy in preserving regular performance. (3) The ASRs of benign models marginally surpass that of GRAPHPROT and GNNSECURER across several cases

(e.g., under AIDS set & GAT) due to the adversarial attack nature of GTA, which remain partially effective without explicit backdoor training.

Defense Results across Attacks and Datasets

From Tab. 2, the following points can be identified: (1) GRAPHPROT demonstrates better overall defense efficacy with consistently lower ASR (GRAPHPROT: 17.2% < GNNSECURER : 24.3% < RS : 26.1% < FINE-PRUNING : 39.7%), highlighting its robustness across attacks and datasets. (2) With respect to benign data accuracy retention, GRAPHPROT attains an ADP of 4.5%, surpassed solely by RS (1.3%), and exceeding the performance of GNNSECURER (8.3%) and FINE-PRUNING (11.9%). (3) GNNSECURER ranks as the second most effective defense, and FINEPRUNING exhibits the least effective performance, with the highest ASR and ADP.

5.3 Ablation Study

We delve into the key factors influencing GRAPHPROT-R, GRAPHPROT-T, and GRAPHPROT-TF via comprehensive ablation studies, examining (1) subgraph number, (2) trigger size, (3) trigger pattern, and (4) sample-rate and feature fraction. This study leveraged the GTA attack on GCN trained via AIDS set, and the results are presented in Fig. 2.

Subgraph Number

Multiple subgraph numbers K were configured at intervals of 3, ranging from 1 to 22, to examine variations in ASR and ADP. The results are shown in Fig. 2a.

From the figure, with increasing K, the ASR declines, with GRAPHPROT-TF = 6% < GRAPHPROT-T = 14% < GRAPHPROT-R = 19%, highlighting improved robustness. Meanwhile, the ACC for all three methods improves and progressively stabilizes, with GRAPHPROT-T = 90% > GRAPHPROT-R = 87% > GRAPHPROT-R = 86%. Generally, GRAPHPROT-TF achieves the best defense but incurs the lowest ACC due to joint topology-feature sampling. Conversely, GRAPHPROT-R minimizes ACC degradation but yields the highest ASR, with GRAPHPROT-T exhibiting intermediary performance.

Trigger Size

We executed attacks with trigger sizes t ranging from 1 to 10 and deployed GRAPHPROT next. Notably, the average graph size in AIDS set is 15.69, indicating that a trigger size t = 8 exceeds the halfway threshold. The findings are illustrated in Fig. 2b.

For defense efficacy, as t escalates, ASR rises across all methods, with defense efficacy following the hierarchy of GRAPHPROT-TF > GRAPHPROT-T > GRAPHPROT-R. Concerning the benign data accuracy, the fluctuation in ACC remains negligible (variations < 3%). The ACC is highest for GRAPHPROT-T, succeeded by GRAPHPROT-R and GRAPHPROT-TF. Furthermore, when t ≈ 8 (half the average graph size), the ASR across all methods rises sharply. GRAPHPROT-TF exhibits the most restrained increase, likely attributed to its node feature sampling mitigating trigger.

Trigger Pattern

The evaluation implemented SBA attack using diverse trigger types (w/ 5 nodes): (1) Erd˝os-R´enyi Graph, (2) Small World Graph, (3) Preferential Attachment (PA) Graph, and (4) Complete Graph. The defense results are shown in Fig. 2c.

Overall, the differences in ASR and ACC among defense methods utilizing various triggers are marginal, suggesting consistent defense efficacy across trigger types. GRAPHPROT-R demonstrates moderate ACC but encounters limitations with elevated ASR, particularly in Preferential Attachment networks. Conversely, GRAPHPROT-T attains better ACC alongside the lowest ASR, whereas GRAPHPROT-TF upholds both robust ACC and minimal ASR.

Sample-Rate and Feature Fraction

We first evaluate how the sample-rate p of GRAPHPROT-R influences defense efficacy. Sample-rates (0 - 100%) were applied for GRAPHPROT-R, with the outcomes shown in Fig. 2d. Referring to the figure, at higher p, both ASR and ACC

increase, with ACC rising more steeply. When p = 0.2, ASR remains comparatively low, while ACC achieves a relatively high level.

We subsequently adjusted the feature fraction r of GRAPHPROT-TF across [0, 100]% to evaluate its impact (results illustrated in Fig. 2d). Based on the figure, when r increases, both ASR and ACC exhibit upward trends, though ACC grows at a more pronounced rate. Peak performance is observed at r ≈ 0.8, where ACC approximately achieves its peak with minimal ASR, indicating an optimal balance.

5.4 Certified Robustness Study

In Sec. 4.3, we elucidate the theoretically certified robustness of GRAPHPROT. Furthermore, we inspect the discrepancy between the achieved defensive accuracy of our method and its theoretically certified accuracy. We conduct GTA attacks against GCN trained on the AIDS and NCI1 sets. After applying GRAPHPROT-R (w/ K = 1000 & multiple sample-rates p), we examine certified accuracy ACCcert (i.e., benign data accuracy conforming to Eq. (10)) and defense data accuracy ACCdef (i.e., poisoned data accuracy satisfying Eq. (11)). The findings are illustrated in Fig. 3.

The results across datasets indicate that as p increases, ACCcert and ACCdef exhibit non-monotonic trends, first rising and then falling. When p ≈ 20%, both ACCcert and ACCdef attain their maxima, thereafter converging towards 0 as p → 60%. This phenomenon stems from the amplification of both benign and malicious node features with increasing p, finally causing a sharp degradation in ACCdef. To equilibrate benign and poisoned sample accuracy, p is set to 20%. For the AIDS and NCI1 sets, the ACCdef reached 56.4% and 40.3%, respectively, exceeding the ACCcert of 36.0% and 24.1%.

6 Conclusion

We introduce GRAPHPROT, an input-dependent black-box defense strategy requiring no ancillary data, external tools, or model specifications. Our approach mitigates backdoor activation by leveraging topology-feature-filtering and samplingbased robust model inference. We further provide GRAPHPROT with a formally certified robustness guarantee. Empirical evaluations conducted on multiple attack paradigms and benchmark datasets confirm its effectiveness in reducing attack success rates while preserving benign data accuracy.

Acknowledgments

This research is supported by National Nature Science Foundation of China (Nos. 62202303, U20B2048, and U2003206), Shanghai Sailing Program (No. 21YF1421700), Action Plan of Science and Technology Innovation of Science and Technology Commission of Shanghai Municipality (No. 22511101202), and the Financial Support for Non-PAIR Research Centres (PolyU 1-CE1N).

Contribution Statement

†Xiao Yang and Yuni Lai contributed equally.