Exact Certification of (Graph) Neural Networks Against Label Poisoning

We thank you for your positive feedback! Based on your comments, we have now significantly expanded our experimental evaluation, solidifying our results. We address your mentioned weaknesses and questions in detail below. References [A]-[D] are provided in the global response.

W1 - Evaluate on a broader variety of real-world datasets

We have now expanded our experiments to include four additional real-world graphs: Wiki-CS [A], Polblogs [B], Cora [C], and Chameleon [D] (a heterophilic dataset) - leading to a total of six real-world datasets investigated. We evaluate our binary class certificates on these datasets similar to Cora-ML and Citeseer and provide the results in Figure 7, and Tables 7-10, with detailed discussion in Appendix G.2.2. We observe that the results discussed in Section 4 generalize to these datasets as well. This is especially interesting, as some of these datasets have very different characteristics to Cora-ML and Citeseer, which were already included in the original submission. In particular, Wiki-CS has significantly fewer class-homogeneous neighborhoods than the common citation datasets [1], Polblogs has no node-features and is purely dependent on the graph structure, and Chameleon is a heterophilic dataset.

W2 - Regarding the contribution

We respectfully disagree that our contribution is incremental. While [1] also reformulates the bilevel problem associated to data feature poisoning by leveraging the SVM equivalence, the technical challenges and resulting contributions are fundamentally different, as outlined below:

1. Difference in adversary: [1] addresses the feature poisoning setting, whereas we focus on a different problem of label poisoning, which introduces distinct challenges.
2. Difference in the final results:
   • While [1] provided only incomplete sample-wise certificates, we derive exact sample-wise certificates. Crucially, we also derive an exact collective certificate. Note that collective certificates are at least as important as sample-wise certificates as substantially established in our work (refer to Section 4.1). However, [1] did not provide a collective certificate.
   • Through the exactness of our certificates, we gain valuable insights on architecture and data-specific properties on robustness, and reveal a novel phenomenon of robustness plateauing.
3. Technical differences: There are many technical differences to [1] emerging right from the first step:
   • In [1], the single-level reformulation obtained after employing the KKT conditions results in a bilinear optimization (product of two continuous variables in Eqs. 4, 5, 7). This bilinear problem is then translated to a MILP by introducing auxiliary variables with relaxations. In our case, the single-level reformulation using the KKT conditions results in a multilinear optimization, involving products of a continuous variable with two binary variables (Eq. 5), along with bilinear terms (in Eqs. 4 and 6). These distinctions make the techniques in [1] not applicable to our problem. We address these challenges by systematically introducing auxiliary variables and modeling them exactly using linear constraints to derive the MILP.
   • As [1] did not tackle collective certification, we introduce a novel modeling strategy to tackle this problem.
   • For the multi-class setting, [1] provides an incomplete sample-wise certificate based on naively applying their binary-class certificate for each class consecutively. In contrast, we provide an exact multi-class sample-wise certificate by directly developing a novel MILP formulation for the multi-class case.

We also want to highlight that deriving exact certificates is a major advancement, as it enables deeper insights into architecture and data-specific properties influencing robustness (refer Section 4). We tried to make these differences clear in the related work Lines 173-176 and in the Introduction Lines 94-96, but have now included an extended discussion on the differences in Appendix E and referred to it in Lines 176-177.

Q1: Adjusting Figures 2c and 3c

All our figures are created with a color-blind friendly coloring scheme and provided in high-quality PDFs for clarity even upon zooming. In particular, this is also true for Figures 2c and 3c, which are created in the same manner as the other figures. However, we are happy to improve them to be more reader-friendly and would like to ask what the concrete problems are with the current coloring or legend. This would help us to address this concern more effectively.

[1] Gosch et al. Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks. Arxiv 2024.

We thank you for the thorough and positive review and the support for acceptance. We incorporated your raised points into the updated draft and thereby, improved upon our initial submitted version. We address the weaknesses and questions in detail below.

The “Exact” Certificates are Approximations

It is correct that finite-width networks can show significant deviations in training behavior. We did adjust the framing of our method, but before we go into details about the changes, we want to clarify that the exactness of the certificates transports to finite-width networks with high probability, if they have sufficient width. Concretely, the output difference between an infinite-width network and a finite-width network with width $w$ is bounded by $\mathcal{O}(\frac{\ln w}{\sqrt{w}})$ with probability $p=1-\exp(-\Omega(w))$. This means that the output difference approaches $0$ with high probability for increasing $w$ and given a sufficiently large $w^*$, the output difference will be too small to change the worst-case prediction as calculated by our certificate (e.g., using the MILP from Thm. 1). Thus, given finite but sufficient width, our certificate is still exact, but the exact guarantee only holds with probability $p$ as the bound only holds with this probability, and with probability $1-p$ no (exact or inexact) statement can be made. Conceptually, this is similar to randomized smoothing [1] where the (inexact) guarantee holds with a certain probability $p'$ and doesn't hold with probability $1-p'$.

We did not intend to claim exact certification of finite but not sufficiently wide networks, and we tried to make this clear in the original draft (Lines 81, 89-90, and 109 as well as in the "On Finite Width Certification" discussion in conclusion). However, we agree that this should be made more clear and the framing of the method adjusted to avoid any potential misunderstandings. Thus, we made the following clarifying changes to the draft:

• We updated the abstract (Line 26) and introduction (Line 81) to clearly state sufficient width.
• We updated our claim $(i)$ in the introduction to explicitly state that our certificate applies to infinite-width NNs and with high probability for finite but sufficiently wide networks (Lines 100-101).
• We moved the technical discussion on finite-width certification from the conclusion to the preliminaries (see Lines 150-156) and further extended it with a discussion on the probability with which the certificate holds for finite-width networks.

We are confident to now clearly convey when our certificate is exact throughout the manuscript and are open to welcome any additional input or suggestions.

L132: The NTK Q_{ij} is defined as the expectation over all model initialisations. Does this mean the certificate also holds wrt. the expectation over model initialisations?

Thank you for this insightful observation! You are correct that the certificates hold with respect to the expectation over model initializations. As a result, our certificates can be understood as providing guarantees at the population level of the parameters, offering a perspective that differs from most certification methods, which typically focus on guarantees for a specific, fixed initialization of the model. We have now added a paragraph to the conclusion (Lines 525–529) to highlight this distinction.

[1] Cohen et al. "Certified Adversarial Robustness via Randomized Smoothing", ICML 2019

Thank you for addressing my comments! I agree with your point that the certificates are exact with probability $p$ - I should have phrased this better. I appreciate the added clarifications, particularly regarding the qualitative bounds early in the paper.

Is it possible to explicitly compute or bound the probability $p$ for a given model? If so, it would be valuable to include this for the models used in the experiments.

Thank you for the response! In the following, we address your follow-up question.

It is possible to derive a bound for the probability $p$ (and the output difference) that more explicitly takes the model architecture into account. Thus, we now include the bounds on the probability and output deviation to include the depth, width, and activation functions used in a model in Appendix E and refer to it in Lines 155-156 (marked red). To obtain this, we follow the derivations in [1,2]. Concretely, we consider a graph neural network with depth $L$, width $w$, employing activation functions with Lipschitz constant $\rho$, and trained using the regularized Hinge loss with $C$ as the regularization constant. Let the network parameters $W$ during training move within a fixed radius $R>0$ to initialization $W_{init}$, i.e. $\\{W |\ ||W-W_{init}|| \leq R\\}$. Then, we get the bound for the output difference between an infinite-width and a finite-width network as $\mathcal{O}(\frac{R^{3L+1}\rho \ln w}{C w})$ with probability $p=1-L\exp(-\Omega(w))$. However, this theoretical bound is not directly computable unless constants in the derivation are preserved and applied to specific inputs. Unfortunately, the literature on the NTK so far is mainly concerned with providing convergence statements in big-O notation and not with calculating the individually involved constants. While we believe it is possible to derive such constants, this is a complex and intricate theoretical task that we find interesting, but outside of our scope. We now include a discussion on the computability of these bounds in Appendix E Lines 1005-1009.

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

[2] Chen et al. On the equivalence between neural network and support vector machine. NeurIPS 2021

We thank you for your thoughtful and positive review! Based on your questions and concerns, we could significantly improve upon our initial submission. We address the mentioned weaknesses and questions in detail below. References [A]-[D] are provided in the global response.

W2 - Method largely tested on synthetic data and generalization to real-world graphs.

We have now expanded our experiments to include four additional real-world graphs: WikiCS [A], Polblogs [B], Cora [C], and Chameleon [D] (a heterophilic dataset). We evaluate our binary class certificates on these datasets similar to Cora-ML and Citeseer and provide the results in Figure 7, and Tables 7-10, with a detailed discussion in Appendix G.2.2. We observe that the results discussed in Section 4 generalize to these datasets as well.

W1, W3 & Q1 - Trading exactness with scalability

Indeed, we do consider and test a strategy to trade exactness with scalability discussed in Appendix A, Lines 764-772. In particular, we discuss how to obtain a non-exact multi-class certificate by leveraging the individual binary-class certificates instead of solving the more complex exact multi-class certificate. In Figure 16b (App. H) we show that this strategy yields useful guarantees on Cora-ML.

While in our work, the focus lies on exact certification, we are also convinced that trading-off exactness with scalability is a fruitful way for future work to tackle the important problem of scaling. Thus, we want to note that we explicitly mentioned this in the "Scalability" paragraph in the Conclusion (see Line 539).

Q2 - Discussion on data-dependent robustness hierarchies

These are very interesting questions that we have also asked ourselves. While we cannot give the ultimate answer to why a certain architecture performs better than another, we conducted several experiments to understand how certain dataset characteristics influence robustness. We explore the influence of graph size in our original draft (see Figure 12) as well as the effect of graph density and homophily on collective robustness in Figures 5c and 5d. In the updated draft, we have extended this analysis to multiple GNNs as well as to sample-wise certification (see Figure 11 in Appendix G.2.6). Interestingly, our findings reveal consistent robustness hierarchies across these varying settings. However, our results also show that robustness properties strongly depend on underlying structural graph properties and class information.

We hope that these results inspire future work on a more deeper understanding of the "why". In this context, we see our certificate as a tool to uncover such robustness hierarchies and, thereby, making them accessible for further studies.

W3 and Q4 - Discussion on technical novelty

While [1] reformulates the bilevel problem associated to data feature poisoning by also leveraging the SVM equivalence, the technical challenges and resulting contributions are fundamentally different, as outlined below:

1. Difference in adversary: [1] addresses the feature poisoning setting, whereas we focus on a different problem of label poisoning, which introduces distinct challenges.
2. Difference in the final results:
   • While [1] provided only incomplete sample-wise certificates, we derive exact sample-wise certificates. Crucially, we also derive an exact collective certificate. Note that collective certificates are as important as sample-wise certificates as substantially established in our work (refer to Section 4.1). However, [1] did not provide a collective certificate.
   • Through the exactness of the certificates, we gain valuable insights on architecture and data-specific properties on robustness, and reveal a novel phenomenon of robustness plateauing.
3. Technical differences: The technical differences emerge right from the first step:
   • In [1], the single-level reformulation obtained after employing the KKT conditions results in a bilinear optimization (product of two continuous variables in Eqs. 4, 5, 7). This bilinear problem is then translated to a MILP by introducing auxiliary variables with relaxations. In our case, the single-level reformulation using the KKT conditions results in a multilinear optimization, involving products of a continuous variable with two binary variables (Eq. 5), along with bilinear terms (in Eqs. 4 and 6). These distinctions make the techniques in [1] not applicable to our problem. We address these challenges by systematically introducing auxiliary variables and modeling them exactly using linear constraints to derive the MILP.
   • As [1] did not tackle collective certification, we introduce a novel modeling strategy to tackle this problem.
   • For the multi-class setting, [1] provides an incomplete sample-wise certificate based on naively applying their binary-class certificate for each class consecutively. In contrast, we provide an exact multi-class sample-wise certificate by directly developing a novel MILP formulation for the multi-class case.

We highlight that deriving exact certificates is a major advancement, as it enables deeper insights into the architecture and data-specific properties influencing robustness (refer Section 4). We included this discussion now in Appendix E and referred to it in prior works discussion in Lines 176-177.

W4 and Q3 - Clarification on the computational complexity

The computation complexity of the fixed quantities in our final MILP certificates are:

• NTK for GNNs $Q$ is computed between all pairs of graph nodes involving simple products and sums, thus leading to $\mathcal{O}(m^2)$ complexity where $m$ is the number of labeled nodes.
• Positive constants $M_u$ and $M_v$ are $\mathcal{O}(m)$

While these inputs to MILP contribute polynomial complexity, the overall computation of the certificate is dominated by the MILP solution process, which is NP-hard with exponential complexity determined primarily by the integer variables in the problem. We note that the original poisoning objective in Eq. 3 is also NP-hard, while the MILP reformulation makes the problem tractable. To address the reviewer’s concern, we have now included this discussion in lines 270–275 of the updated manuscript.

[1] Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, Stephan Günnemann. Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks. Arxiv 2024.

We thank you for the constructive feedback! Based on your feedback, we improved our paper and we address all your raised weaknesses and questions below.

W1 - Clarification of the approximation error due to NTK

We kindly disagree that we do not consider the approximation error. We state that our certificates only hold for sufficiently wide networks in the introduction (lines 81, 89-90, and 109) and discuss this in detail in conclusion (see "On Finite Width Certification" Lines 506-512 in the original draft). However, we do agree that this should be made more clear to avoid any potential misunderstandings. Thus, we made several clarifying changes to the draft:

• We updated the abstract (Line 26).
• We updated our claim $(i)$ in the introduction to explicitly state that our certificate applies to infinite-width NNs and with high probability for finite but sufficiently wide networks (Lines 100-101).
• We moved the technical discussion on finite-width certification from the conclusion to the preliminaries (see Lines 150-156) and further extended it (see answer to Q1 & Q2 below for details).

We hope this fact is now clearly conveyed throughout the manuscript and we welcome additional feedback or specific suggestions that could further improve the discussion.

Q1 & Q2 - Tightness & When considering the approximation error in this framework, is this method an exact certification method?

If the width of a network is not sufficiently wide, our certificate does not apply and hence, can't be used to provide an exact or inexact guarantee. However, if the width of a network is sufficiently wide, the certificate's guarantee holds with high probability, and if it holds, it is exact (tight).

To clarify, the crucial fact here is that our method does not underestimate the robustness of the studied model (like an inexact certificate would). In particular, if the model is not infinitely-wide but has finite but sufficient width $w$, our method provides an exact guarantee with a certain probability $p$ and does not apply (neither providing an exact or inexact guarantee) with probability $1-p$. The probability $p$ can be derived to be $p=1-\exp^{-\Omega(w)}$ [1], which we now include in our discussion on certifying finite-width networks (Lines 150-156). Conceptually, this is similar to randomized smoothing [2], which provides an (inexact) guarantee that holds with a probability $p'$ and with probability $1-p'$ does not hold at all. Note that $p$ approaches $1$ exponentially as a function of the width $w$ and, thus, is a high-probability statement.

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

[2] Cohen et al. "Certified Adversarial Robustness via Randomized Smoothing", ICML 2019

Concerning 1

To avoid any misunderstanding, we absolutely agree that in the finite-width case, there is an approximation error that is bounded by $\mathcal{O}(\frac{\ln w}{w})$, where $w$ is the width of the network. Important to recognize now is that this means that for an increasing $w$, the approximation error approaches $0$ (as $\frac{\ln w}{w} \rightarrow 0$ for $w \rightarrow \infty$). Thus, there exists a certain finite but sufficiently large width $w'$, at which the approximation error is small enough, so that it can't change the worst-case prediction as calculated for an infinite-width network.

Example. Assume a binary classification task and that we are interested in certifying a node $t$. Further, assume our sample-wise certificate for an infinite-width GNN outputs that node $t$ is certifiably robust (or unrobust) with a worst-case prediction score $p_t^*$. Now, as the approximation error approaches $0$ for increasing $w$, we know that there exists (a sufficiently large) width $w'$, for which the approximation error will be smaller than $p_t^*$ and thus, can't change the sign of the prediction $p_t^*$. Then, the certificate will still be exact for all finite-width networks that have widths $\ge w'$. However, as the bound only holds with probability $p=1-\exp(-\Omega(w))$, the certificate is exact for such sufficiently wide networks with probability $p$ and can't be applied (i.e., does not provide any guarantee) with probability $1-p$. This example can be generalized to certify an arbitrary collection of nodes by considering the closest worst-case prediction to the decision boundary as given by our certificate.

Thus, we agree that if one does not assume sufficient width, there is an approximation error that would render the certificate inexact. In particular, one would obtain an inexact certificate with probability $p$ and no guarantee at all with probability $1-p$. However, given the sufficient width assumption, the infinite-width certificate transports to an exact certificate for a sufficiently wide but finite network with probability $p$ as agreed by Reviewer 9xfS in their response to our rebuttal (see Reviewer 9xfS's Official Comment).

Paper Updates. We did not intend to claim exact certification of finite but not sufficiently wide networks. This is the reason why we, in the revised paper, made more clear that our exact certificate is only applicable for infinite-width or finite but sufficiently wide networks (see the changes in the abstract Line 26 and Introduction Lines 81/82 and 100/101). Note that we also explicitly write this in the updated discussion on finite-width networks (Lines 150-156) cited by you, where we state "As a result, given sufficient width, a guarantee for the infinite-width case will translate to a high-probability guarantee for the finite-width case." However, we have now uploaded a new draft, where we explicitly state (see Lines 157-159 marked red) that if a finite-width network does not have sufficient width, the certificate would become incomplete. We are happy to provide more adaptations if you think this fact is still not conveyed appropriately.

Note. To employ our certificate in an incomplete way to finite-width networks would require to explicitly compute the approximation error bounded by $\mathcal{O}(\frac{\ln w}{w})$. For this, one would need knowledge of the concrete constants involved in the bound. Unfortunately, the literature on the NTK so far is mainly concerned with providing convergence statements in big-O notation and not with calculating the individually involved constants. Calculating these is a complex and intricate theoretical task that we find interesting, but outside of our scope, and we now include a discussion on this in App. E Lines 1005-1009.

We hope we have addressed your remaining two concerns and are happy to provide further clarifications if needed.

We thank you for the detailed response and for clarifying your remaining concerns. Below, we address these concerns in detail, first by addressing Concern 2 and then, following up with Concern 1.

Concerning 2

The feature certificate provided in [1] is inherently incomplete due to the following: The bilevel feature certification problem for infinite-width networks is stated in their Eq. 4 [1]. This is reformulated into a single-level problem denoted $P_3$. Subsequently, the authors relax $P_3$ to make it tractable, thus deriving an incomplete certificate. This is explicitly written by the authors in their "Discussion and related work" - Section 5 (Page 9) under 'How tight is QPCert?' as well as in the last sentence on Page 5 in the methods section. The technical reason for this is that for feature certification, the NTK matrix $Q$ is itself a variable, as it is a function of the feature matrix $X$ over which [1] optimizes. As [1] also optimizes over the dual variables $\alpha$, the terms $\alpha_i Q_{ij}$ arising in their optimization problem $P_3$ (see their Eq. 4 & 5) are multiplications of two continuous variables which can't be exactly modeled linearly (see also the last paragraph in Section 5 in [1], where the relaxation is introduced).

This contrasts with our work, where we optimize over the labels $y$ (which are constant in [1]) instead of the features leading to $Q_{ij}$ staying constant in our label certification problem. Thus, the arising terms (i) $y_i \alpha_i Q_{ij}$ and (ii) $y_i y_j \alpha_i Q_{ij}$ in our optimization problem (see Section 3.1) are multiplications of a discrete ($y_i$) with a continuous variable ($\alpha_i$) in case (i) and a multiplication of two discrete ($y_i,y_j$) with one continuous variable ($\alpha_i$) in case (ii). In Section 3.1, we introduce techniques to model these multilinear terms exactly allowing us, in conjunction with other modelling techniques we introduce in Section 3.1, to convert the bilevel label certification problem for kernelized SVM's and infinite-width networks (as provided in our Eq. 4) into a mixed-integer linear problem in an exact way. Thus, in contrast to [1], we do not employ a relaxation to solve the arising certification problem leading to an exact certificate. In a similar way, our multi-class certificate (Appendix A) and collective certificate (Section 3.2) are exact, whereas [1] proposes a relaxed multi-class certificate through a simple application of their incomplete sample-wise certificate in their Appendix E, and they do not provide a collective certificate.

We now updated our technical comparison to [1] in Appendix F to make this point more clear (see Lines 1021/1022 and Lines 1026-1028 marked in red).

[1] Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, Stephan Günnemann. Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks. Arxiv 2024

We want to thank you for the positive response and for raising the score!