Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoors

Authors: Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, Stephan Günnemann
Primary area: learning on graphs and other geometries & topologies
Keywords: graph neural networks, provable robustness, certificates, poisoning, data poisoning, backdoor attacks, neural tangent kernel, adversarial robustness, mixed-integer linear programming, support vector machines

Abstract:
Generalization of machine learning models can be severely compromised by data poisoning, where adversarial changes are applied to the training data. This vulnerability has led to interest in certifying (i.e., proving) that such changes up to a certain magnitude do not affect test predictions. We, for the first time, certify Graph Neural Networks (GNNs) against poisoning attacks, including backdoors, targeting the node features of a given graph. Our certificates are white-box and based upon (i) the neural tangent kernel, which characterizes the training dynamics of sufficiently wide networks; and (ii) a novel reformulation of the bilevel optimization problem describing poisoning as a mixed-integer linear program. Consequently, we leverage our framework to provide fundamental insights into the role of graph structure and its connectivity on the worst-case robustness behavior of convolution-based and PageRank-based GNNs. We note that our framework is more general and constitutes the first approach to derive white-box poisoning certificates for NNs, which can be of independent interest beyond graph-related tasks.

Decision: reject
Reviewer scores: 6, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730517005025

thread_type:
official_review

<thread_object>
creator: reviewer_dgk8

<content>
summary:
The authors leverage the Neural Tangent Kernel (NTK) to capture the complex training dynamics of GNNs and reformulate the bilevel optimization problem describing poisoning as a mixed-integer linear program. This allows them to provide white-box certificates for GNNs and neural networks in general, which was previously an unsolved problem.

strengths:
- Provide a comprehensive theoretical analysis to support the methodology 
- Very inspiring to leverage NTK to defend the adversarial and backdoor attacks
- Reformulated the bilevel optimization problem describing poisoning as a mixed-integer linear program

weaknesses:
- this paper only considers the scenario where the adversaries manipulate the node features, but there are plenty of graph attack works that manipulate the graph structure and the node features at the same time. Could the method in this paper be leveraged for poisoned data with both graph structures and node features manipulated?
- The experiments only compare the GNNs with MLP. Could authors provide some adversarial/backdoor defense baselines? While the comparison with MLPs demonstrates the positive impact of QPCert, it does not adequately illustrate the extent of QPCert's effectiveness.
- In Figure 2, MLP consistently has the lowest accuracy when evaluated in the PL task, but MLP can have a better performance than some GNNs in Figure 3 (PU and BU tasks) when perturbation budges are large. Could the author explain what factors lead to these differences?

questions:
the same as weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671943028

thread_type:
official_review

<thread_object>
creator: reviewer_b7b5

<content>
summary:
I'm rating this paper as "8: accept, good paper".

Summary: the paper proposes a certification against white-box and backdoor attacks, by making use of Graph NTK and the fact that for sufficiently wide networks the network is throughly understood given the input data and the neural tangent kernel.

strengths:
- Clear writing
- Elegant ideas to make the bi-level optimisation feasible and tracktable

weaknesses:
-

questions:
- In line 369 it is mentioned that: "... We note as we are the first work to study white-box certificates for clean-label attacks on node features in graphs in general, there is no baseline prior work. ...". Even if there are no baselines for white-box attacks, aren't the certificates for black-box baselines still applicable? Specially because these methods are different in, e.g., their relaxation which may differently affect their performance and one cannot presume superiority of certificate in black-box versus white-box setting?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731095270577

thread_type:
official_review

<thread_object>
creator: reviewer_ns1a

<content>
summary:
The paper introduces a white-box certification framework, QPCert, for evaluating the robustness of neural networks, specifically Graph Neural Networks (GNNs), against data poisoning and backdoor attacks. This framework, grounded in Neural Tangent Kernel (NTK) theory, reformulates poisoning detection as a mixed-integer linear program (MILP), enabling robustness certificates against node feature perturbations in GNNs. Thexperimental results to validate QPCert's effectiveness.

strengths:
1. This paper studies an interesting problem: the certified robustness against data poisoning and backdoor attacks.
2. The extensive theoretical analysis is provided.
3. The paper is well written.

weaknesses:
1. While the theoretical analysis is promising, the empirical evaluation could be strengthened to more comprehensively demonstrate the effectiveness of the proposed certification method. Currently, only one attack, APGD [1], is considered in the experiments. Since certification methods aim to provide provable guarantees against all attacks within a specific threat model, it would be beneficial for the authors to clarify how their certification framework addresses the threat models of other commonly studied attacks, such as graph poisoning and backdoor attacks [2, 3, 4]. This would provide a more insightful discussion of the method’s robustness and scope of applicability, beyond specific attack evaluations
2. It appears that the Neural Tangent Kernel (NTK) approach is currently limited to specific GNN architectures such as GCN, SGC, and GraphSage, which could restrict the broader applicability of the proposed method. It would be helpful if the authors could discuss any challenges or limitations in extending their method to other GNN architectures or clarify why these specific GNNs were chosen as representative examples. Additionally, outlining potential directions for adapting the approach to other types of GNNs could strengthen the paper's discussion and broaden its scope.
3. The proposed method addresses node feature perturbation attacks, yet structural perturbations are often more prevalent and impactful in real-world scenarios. It would strengthen the paper if the authors could discuss the challenges in adapting their method to structural perturbations or clarify their focus on feature perturbations. Additionally, a comparison of the practical implications of feature versus structural perturbations in real-world applications would provide valuable insights into the method's scope, limitations, and potential future directions.


[1] Reliable Evaluation of Adversarial Robustness with an Ensemble of Diverse Parameter-free Attacks.

[2] Adversarial Attacks on Graph Neural Networks via Meta Learning.

[3] Graph Backdoor.

[4] Unnoticeable Backdoor Attacks on Graph Neural Networks.

questions:
1. Please add more experiments against some realistic graph poisoning and backdoor attacks.
2. Please discuss applying the proposed method to more advanced GNNs.
3. There are some works that study clean-label (graph) backdoor attacks [1, 2], can the proposed method be applied to this attack?

[1] Clean-Label Backdoor Attacks.

[2] A clean-label graph backdoor attack method in node classification task.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731407946577

thread_type:
official_review

<thread_object>
creator: reviewer_ptk3

<content>
summary:
The paper introduces a novel framework, QPCert, for certifying the robustness of GNNs, against data poisoning and backdoor attacks. This work leverages the NTK for white-box certification and reformulates the poisoning problem as a MILP to provide formal guarantees for GNNs. The authors explore this certification's effectiveness across various GNN architectures and benchmark datasets, and also analyze the effect of graph structure on robustness, presenting insights for architectural choices in GNNs with robustness considerations.

strengths:
The paper is generally well-organized and thorough, with sections on methodological background, detailed steps in QPCert’s derivation, and clear experimental results. Extensive experiments are conducted across multiple GNN architectures and datasets. The analysis includes diverse attack scenarios and perturbation models, highlighting the framework’s adaptability and utility.

weaknesses:
Although the focus is on feature perturbations, robustness against graph structure modifications is a critical issue for GNNs. Future work on structural robustness would greatly enhance the scope and impact of this framework.

On the assumption on large Width: The reliance on the NTK’s emight limit applicability to smaller, practical network sizes. 

How your work can be extended to graph classification?

Given the MILP reformulation, computational costs may scale poorly with large datasets,

questions:
No questions
</content>
</thread_object>

</thread>
<thread>
creation date:
1732303085892

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global response

comment:
We thank all reviewers for their helpful feedback and insightful questions! Based on it, we now include interesting **new results and discussions** in the revised paper. We highlight changes to the original draft in blue and all line numbers in the rebuttal, if not indicated otherwise, refer to the updated draft. 

Specifically, the revised paper now includes the following **new experiments**:
- **Three new attacks:** One additional graph poisoning attack [1] and two graph backdoor attacks [2] leading to a thorough evaluation of the tightness of QPCert (App. I.3)
- A **comparison** with **two poisoning defenses**: GNNGuard [3] and Elastic Graph Neural Networks [4] (App. I.7)

Furthermore, the revised paper now includes:
- An **extension** of QPCert **to graph classification** (App. N.5)
- A detailed discussion on **extending** QPCert to structure perturbation (App. N.2)
- Guidelines on the **broader applicability** of QPCert to arbitrary GNN architectures (App. N.4.)
- **Practical implications** of feature perturbations compared to structure perturbations (App. N.3)
- Clarifications on the **applicability** to commonly studied perturbation models and attacks (App. N.1)

[1] Zügner et al. "Adversarial Attacks on Graph Neural Networks via Meta Learning", ICLR 2019  
[2] Xing et al. "A Clean-Label Graph Backdoor Attack Method in Node Classificaiton Task", Knowledge-Based Systems 2024   
[3] Zhang et al. "GNNGuard: Defending Graph Neural Networks against Adversarial Attacks", NeurIPS 2020
[4] Liu et al. "Elastic Graph Neural Networks", ICML 2021

**EDIT:** (25.11.) Included comparisons to poisoning defenses.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper tries to design a white-box certificate for Graph Neural Networks (GNNs) against poisoning attacks, including backdoors, with a threat model on the node features. The solution first uses neural tangent kernel to turn a GNN training problem into an SVM problem, and then turns the bilevel optimization problem into a mixed-integer linear program (MILP).  The tightness of the worst-case NTK bounds for GNNs is then analyzed.  Extensive experiments are shown that demonstrate the effectiveness of QPCert, along with the role of graph data and the impact of different architectural components in GNNs.

The paper addresses an important problem.  Along with the rebuttal, it considered quite a number of extensions that arise from the real practice.  My major concern is the computational cost, which reviewer PTK3 raised, but was not sufficiently addressed in the rebuttal.  QPCert needs to solve a MILP to the global optimal (not local optimal), and in the worst case its complexity is exponential in the number of labeled nodes.  In the Cora-ML experiment with 140 labeled nodes, certifying a node can take between one minute and several hours using two CPUs.  In contrast, for CSBM and Cora-MLb which have 80 and 20 labeled nodes respectively, certifying one node typically takes several seconds up to one minute on a single CPU.  So it clearly scales superlinearly.  I think this computational cost needs to be addressed first, before considering other extensions of QPCert. For example, what about turning P(Q) in Theorem 1 into a maximization problem, which doesn’t need to be solved to the global optimal?  I understand strong duality can be tricky here though.