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

Thanks for the authors' detailed explanation. My questions for Q1 and Q3 are almost solved. However, for Q2, I believe the authors may have misunderstood my questions. I do not expect to apply QPCert to other defense baselines and also don't expect to see the analytical NTK for a poisoning defense. Actually, I want to compare the effectiveness (certified accuracy) of QPCert with other graph defense baselines. Therefore, could the authors test some existing graph defense methods, such as [1][2][3], on the datasets this paper uses?

[1] GNNGuard: Defending Graph Neural Networks against Adversarial Attacks.

[2] Elastic Graph Neural Networks.

[3] Graph Information Bottleneck.

Thank you for the positive review! We very much value the appreciative feedback and updated the draft to reflect your questions. Below, we answer to your weaknesses and questions in detail.

---

Could the method in this paper be leveraged for poisoned data with both graph structures and node features manipulated?

We agree that tackling graph structure perturbations (or feature and structure perturbations jointly) is an important problem as we mention in our conclusion in Lines 501/502. It is thinkable to extend QPCert to also tackle structure certification, but this leads to several yet unsolved technical challenges. As a result, we have now included a detailed discussion on extending QPCert to structure perturbations in Appendix N.2, which we link to in the conclusion (Lines 502/503). In particular, the general strategy of QPCert to reformulate the bilevel optimization problem into a single-level problem is still applicable. However, an immediate application of the bounding scheme (Section 3.1) to structure perturbations would result into loose bounds that requires to include the NTK optimization into the optimization problem. Thus, we show in Appendix N.2 how this can lead to a mixed-integer bilinear problem describing structure perturbations and describe the open and yet unsolved technical challenges to make this problem tractable.

---

The experiments only compare the GNNs with MLP. Could authors provide some adversarial/backdoor defense baselines?

In our analysis, we focus on commonly used message-passing GNNs with and without skip-connections, as they are widely used in practice and cover a representative spectrum of design choices. Thus, these networks allow us to demonstrate the effectiveness of QPCert with respect to the most commonly used GNNs for node classification. We agree that applying QPCert to adversarial/backdoor defense baselines is an interesting question. However, in order to include defense baselines, it is first necessary to derive their NTK in analytical form. This is a non-trivial task and while we provide such derivations for common message-passing GNNs, we are not aware of NTK derivation techniques for poisoning defenses so far (either for GNNs or general NNs). The moment the analytical NTK for a poisoning defense is available, it can be immediately integrated into our framework and we now also include a detailed discussion on extending QPCert to other architectures in Appendix N.4.

---

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?

The reason is that in the poison unlabeled (PU) or backdoor unlabeled (BU) settings only the unlabeled nodes are attacked and as an MLP ignores unlabeled nodes during training, it is not affected by such a poisoning attack. We discuss this in Lines 406/407 in the draft and updated the discussion to make this more clear. Additionally, the reason why the MLP still loses some accuracy in the PU task is that due to the transductive setting, the attacked unlabeled nodes in the training graph correspond to the test nodes. Thus, the MLP is confronted with the attacked nodes at test time resulting in an evasion attack for the MLP. However, as the attacked nodes are only seen at test time for the MLP, they cannot affect the clean node predictions, and thus, the MLP accuracy plateaus for strong budgets (see e.g., Figure 3a $\delta=0.2$ and $\delta=0.5$). This is slightly different for the BU task. Due to the backdoor setting, every test node can be attacked, and thus, with a certain attack strength $\delta$, the MLP can't provide a guarantee even though its training was not affected. To provide a more clear experiment description, we now added this additional clarification into the draft in lines 411-413.

Thank you for your positive review and recommendation to accept our paper! Below, we address your questions in detail.

---

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?

We agree that one cannot presume superiority of a certificate in black-box vs. white-box setting. Unfortunately, all so far developed black-box poisoning certificates have only been developed for the image domain (or in general, i.i.d data) and cannot be directly applied to graph learning tasks. There is one exception [1] who extend the randomized smoothing-based poisoning certificate framework to graph learning, but they only consider the case of injecting completely new nodes into the training graph (as we mentioned in Related Work line 488/489). Extending their framework to be applicable to $\ell_p$-bounded perturbations is non-trivial and would require a new method derivation. We agree that our initial argumentation in the manuscript did not make this point clear and thus, we added these arguments in lines 372-374 in the experimental results section for more clarity.

[1] Lai et al. "Node-aware bi-smoothing: Certified robustness against graph injection attacks", IEEE S&P 2024

W3 (b) - Practical implications of feature versus structural perturbations

Indeed both feature and structure perturbations find different real-world applications. As particular examples, two important application areas for graph-based learning methods are fake news detection [1] and spam detection [2]. Regarding fake news detection, feature perturbations can model changes to the fake news content or to (controlled) user account profiles to avoid detection [1,3,4]. Structure perturbations allow to model a change in the propagation behavior (e.g., retweeting) to again, avoid detection [5]. A similar qualitative differentiation holds true for spam detection. Here, feature perturbations can model spammers trying to adapt their comments so as to mislead detectors [2,6,7]. On the other hand, structure perturbations can model a behavioral change in the posting pattern of a spammer, so as to post comments to different product items or stores to imitate real users [6,7]. We tried to touch upon this in Lines 499/500 in the conclusion and now included an extended discussion in Appendix N.3 linked in Lines 499/500.

[1] Hu et al. "An overview of fake news detection: From a new perspective", Fundamental Research 2024
[2] Li et al. "Spam Review Detection with Graph Convolutional Networks", CIKM 2019
[3] Le et al. "MALCOM: Generating Malicious Comments to Attack Neural Fake News Detection Models", ICDM 2020
[4] He et al. "PETGEN: Personalized Text Generation Attack on Deep Sequence Embedding-based Classification Models", SIGKDD 2021
[5] Wang et al. "Attacking fake news detectors via manipulating news social engagement", WWW 2023
[6] Wang et al. "Identify Online Store Review Spammers via Social Review Graph", ACM TIST 2012
[7] Soliman et al. "AdaGraph: Adaptive Graph-Based Algorithms for Spam Detection in Social Networks", 2017

EDIT: (25.11.) Updated Line Numbers in Responses

We thank you for the constructive review! Based on it, we now strengthened our empirical evaluation with new experiments and updated the draft with several important discussions. Below, we address all your mentioned weaknesses and questions in detail.

W1 & Q1 - Add more realistic graph poisoning and backdoor attacks

We have now added three new attacks: another graph poisoning attack namely MetaAttack [1] adapted to feature perturbations, as well as two graph backdoor attacks. This results in a thorough evaluation of the tightness of QPCert. As backdoor attacks, we implemented the clean-label graph backdoor attack from [2] as well as an attack that is allowed to use the complete $\ell_p$-ball budget freely for the poisoned nodes and target node. We refer to Appendix I.3 for details and new results and updated the experimental details discussion in Lines 352-356.

We want to clarify that our usage of the APGD attack in the manuscript corresponds to a strong graph poisoning strategy where we directly differentiate through the training process by solving the SVM's quadratic problem associated to an infinitely-wide GNN with QPLayer [3] - a differentiable quadratic programming solver. APGD comes into play as a more sophisticated updating scheme regarding creating the poisoned graph based on the above-calculated gradient, compared to doing simple projected gradient descent.

[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] Bambade et al. "QPLayer: efficient differentiation of convex quadratic optimization", 2023

W1 & Q3 - Clarification on application to common threat models

To avoid any misunderstandings, we want to clarify that our method directly addresses any poisoning or backdoor attacks that perform $\ell_p$ bounded feature perturbations. In particular, the (certified) accuracies reported in Figures 2 and 3 are provable lower bounds for the robust accuracy achieved against the strongest adversary possible (within the given $\ell_p$-norm bounds) and thus, are valid for all conceivable attack strategies within the given $\ell_p$ bounds. As a result, the reported certified accuracies and thus, the applicability/effectiveness of QPCert, is independent of any specific attack evaluations.

Regarding addressing threat models of commonly studied attacks:

• QPCert is directly applicable to the clean-label (graph) backdoor attacks proposed in [1,2]. Both attacks perform bounded feature perturbations to labeled training nodes. This is exactly the setting we call "backdoor labeled" in our experiments, and e.g., Figure 13 (a) shows the certified accuracies in this setting that are immediately valid for any of the investigated NNs if they would be attacked with the attacks in [1,2]. As mentioned above, we now also implement the backdoor attack from [2] (see Appendix I.3).
• QPCert is applicable to graph poisoning with MetaAttack if the gradient is taken w.r.t. to the graph features instead of the graph structure. Indeed, as mentioned previously, we adapt MetaAttack [1] to perform graph feature poisoning and the results can be found in Appendix I.3.
• The backdoor attack in [3] changes features and training labels jointly, thus our method is only applicable to [3] if the training labels will be kept constant. Similarly, [4] changes the features and graph structure jointly. So far, QPCert does not allow to certify against graph structure changes and, as detailed in the answer to W3, we now detail the challenges to certify graph structure changes in Appendix N.2.

We have now included a discussion on which threat models of commonly studied attacks are addressed by QPCert in Appendix N.1 and point to this discussion in line 475 (Section 5).

[1] Turner et al. "Clean-Label Backdoor Attacks", 2018
[2] Xing et al. "A Clean-Label Graph Backdoor Attack Method in Node Classificaiton Task", Knowledge-Based Systems 2024
[3] Dai et al. "Unnoticeable Backdoor Attacks on Graph Neural Networks", ACM Web Conference 2023
[4] Xi et al. "Graph Backdoor", USENIX Security 2021

W2 & Q2 - QPCert for more advanced GNNs and clarification on the choice of the GNNs

Applicability to other GNNs While our analysis focused on commonly used GNNs with and without skip connections, QPCert is broadly applicable to any GNNs with a well-defined analytical form of the NTK. When extending QPCert to other architectures the following challenges and considerations can arise:

1. NTK-network equivalence: The equivalence between the network and NTK breaks down when the network has a non-linear last layer or bottleneck layers [1]. Consequently, our certificates do not hold for such networks.
2. Analytical form of NTK: Deriving a closed-form expression for the NTK is needed to derive bounds on the kernel. This might be challenging for networks with batch-normalizations or advanced pooling layers.
3. Tight bounds for the NTK: Ensuring non-trivial certificates requires deriving tight bounds for the NTK. Depending on the NTK, additional adaptation of our bounding strategy may be necessary.

Despite these considerations, most message-passing networks satisfy these criteria, making QPCert readily applicable to a wide range of architectures, which we demonstrated by incorporating eight different GNNs (including MLP). We have added a discussion outlining these challenges in Appendix N.4 and reference it in Line 461.

Why the chosen architectures? We chose to focus on common message-passing networks, as they are widely used in practice and cover a representative spectrum of design choices including skip connections. Thus, these networks allow us to demonstrate the applicability and potential of QPCert with respect to the most commonly used GNNs for node classification.

[1] Liu et al. On the linearity of large non-linear models: when and why the tangent kernel is constant. NeurIPS 2020.

W3 (a) - Discussing challenges of adapting QPCert to structural perturbations

We now include a detailed technical discussion on the challenges arising when adapting QPCert to certify structure perturbations in Appendix N.2 and reference it in the conclusion (Line 503/504). On a technical level, to certify structure perturbations, the general strategy of QPCert to reformulate the bilevel optimization problem into a single-level problem is still applicable. However, as we argue in Appendix N.2., to avoid loose bounds and thus, a non-vacuous certificate, the NTK computation has to be included into the optimization problem. Therefore, we now derive and provide the associated optimization problem in Appendix N.2 (Eqs. 45-57), together with a discussion on the unsolved challenges that would allow to make this problem tractable. Broadly, the challenges are:

1. The resulting optimization problem is still untight and fundamentally bilinear with both the objective and constraints having many bilinearities (multiplications of two continuous variables) that cannot be modeled linearly.
2. While potential bilinear relaxations are conceptually possible, making them tight enough and scaling them to problem sizes of practical interest for certification are open challenges.

We agree that tackling graph structure perturbations is an important problem as we discuss in our conclusion (Lines 502-504). We focus on feature certification as, next to open technical challenges regarding structure certification discussed in App. N.2, it $(i)$ has different and complementary real-world applications that we detail in our answer to W3b below, and $(ii)$ poses unique graph-related challenges due to the interconnectedness of nodes, which QPCert can elegantly handle through the use of the graph NTK. The unique challenge of certifying feature perturbations in the face of interconnected data points is also the reason why there is a distinct line of work focused on certifying node feature perturbations [1,2,3]

[1] Zügner et al. "Certifiable robustness and robust training for graph convolutional networks", KDD 2019
[2] Scholten et al. "Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks", NeurIPS 2022
[3] Scholten et al. "Hierarchical Randomized Smoothing", NeurIPS 2023

Thank you for the positive review! We appreciate the feedback and below, address the weaknesses in detail.

---

Future work on structural robustness would greatly enhance the scope and impact of this framework

We agree that future work on structure perturbations is important as we mention in the conclusion in Lines 502-504. We have now included an extensive technical discussion in Appendix N.2 on how our framework could be extended to graph structure perturbations and what the respective open technical challenges are. Broadly, extending the framework to structure perturbations introduces the following open challenges:

1. The resulting optimization problem will be untight and fundamentally bilinear with both the objective and constraints having many bilinearities (multiplications of two continuous variables) that cannot be modeled linearly.
2. While potential bilinear relaxations are conceptually possible, making them tight enough and scaling them to problem sizes of practical interest for certification are open challenges.

We hope that our work and the added discussion lay the foundations for future work tackling this important but yet unsolved problem.

---

How your work can be extended to graph classification?

Our work can be readily extended to graph classification using the graph NTK of the corresponding neural network trained for such a task. Note that in this case, the kernel is computed between all pairwise graphs instead of nodes. [1] provides a derivation of a graph NTK that can be applied in this context. By utilizing this NTK in our MILP framework, robustness certificates for graph classification can be obtained. We elaborate on the technical details in Appendix N.5 (linked in the discussion Line 461) and provide a brief outline here:

The primary adaptation required is deriving entry-wise bounds for the NTK. Specifically, the NTK computation for graph classification involves pairwise feature matrix covariances, $X_iX_j^T$ where $X_i$ is the feature matrix of graph $i$, we adapt our derivation for this case. Detailed derivation for $\ell_2$ feature perturbation is given in the revised version, leading to the following bounds.

For graph pairs $i,j$, let the adversarial feature matrix covariance be $X_i'X_j'^T=X_i X_j^T + \Delta_{ij}$. Let $\mathcal{U}\_i$ be the set of all potentially corrupted nodes for graph $i$ and $(X_j)\_b$ the node feature vector of node $b$ associated to graph $j$. Then the element-wise bounds on $\Delta_{ij}$ are given by

$(\Delta_{ij})^L_{ab} = -\delta \lVert (X_j)_b \rVert_2 {1}[a \in \mathcal{U}_i] - \delta \lVert (X_i)_a \rVert_2 {1}[b \in \mathcal{U}_j] - \delta^2 {1}[a \in \mathcal{U}_i \land b \in \mathcal{U}_j \land a \ne b]$

$(\Delta_{ij})^U_{ab} = \delta \lVert (X_j)_b \rVert_2 {1}[a \in \mathcal{U}_i] + \delta \lVert (X_i)_a \rVert_2 {1}[b \in \mathcal{U}_j] + \delta^2 {1}[a \in \mathcal{U}_i \land b \in \mathcal{U}_j \land a \ne b]$

Using these bounds, similar to node classification, we can propagate them through the NTK computation to get the bounds on NTK. Using the NTK bounds, we can apply QPCert to get the certificate for graph classification.

[1] Du et al. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. NeurIPS 2019.

---

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

Indeed, as is true for all deterministic certificates [1] scaling to large datasets is challenging. Thus, we discuss this as an important avenue for future research in the discussion Lines 504-506.

[1] Lie et al. "Sok: Certified robustness for deep neural networks", IEEE S&P 2023

EDIT: (25.11.) Corrected Line Numbers