Exact Certification of (Graph) Neural Networks Against Label Poisoning
Authors: Mahalakshmi Sabanayagam
Lukas Gosch
Stephan Günnemann
Debarghya Ghoshdastidar
Venue: ICLR 2025 Spotlight (2025)
Keywords: graph neural networks
robustness
certificates
provable robustness
neural networks
label poisoning
label flipping
poisoning
mixed-integer linear programming
neural tangent kernel
support vector machines
Primary area: learning on graphs and other geometries & topologies
TL;DR: First exact sample-wise and collective certificates for (graph) neural networks against label poisoning based on the neural tangent kernel and reformulating the bilevel label poisoning problem into a mixed-integer linear program.

Abstract: Machine learning models are highly vulnerable to label flipping, i.e., the adversarial modification (poisoning) of training labels to compromise performance. Thus, deriving robustness certificates is important to guarantee that test predictions remain unaffected and to understand worst-case robustness behavior. However, for Graph Neural Networks (GNNs), the problem of certifying label flipping has so far been unsolved. We change this by introducing an exact certification method, deriving both sample-wise and collective certificates. Our method leverages the Neural Tangent Kernel (NTK) to capture the training dynamics of wide networks enabling us to reformulate the bilevel optimization problem representing label flipping into a Mixed-Integer Linear Program (MILP). We apply our method to certify a broad range of GNN architectures in node classification tasks. Thereby, concerning the worst-case robustness to label flipping: $(i)$ we establish hierarchies of GNNs on different benchmark graphs; $(ii)$ quantify the effect of architectural choices such as activations, depth and skip-connections; and surprisingly, $(iii)$ uncover a novel phenomenon of the robustness plateauing for intermediate perturbation budgets across all investigated datasets and architectures. While we focus on GNNs, our certificates are applicable to sufficiently wide NNs in general through their NTK. Thus, our work presents the first exact certificate to a poisoning attack ever derived for neural networks, which could be of independent interest. The code is available at https://github.com/saper0/qpcert.

Published as a conference paper at ICLR 2025
EXACT CERTIFICATION OF (GRAPH) NEURAL NET- WORKS AGAINST LABEL POISONING
Mahalakshmi Sabanayagam's Lukas Gosch 1,,3
Stephan Günnemann 1.2.3
Debarghya Ghoshdastidar
School of Computation, Information and Technology, Technical University of Munich 2 Munich Data Science Institute Munich Center for Machine Learning (MCML); Germany (m. sabanayagam, 1. gosch s g.gennemann, d. d.ghoshdastidar ett um. de
ABSTRACT
Machine learning models are highly vulnerable to label flipping, i.e., the adversar- modification (poisoning) of training labels to compromise performance. Thus, deriving robustness certificates is important to guarantee that test predictions re- main unaffected and to understand worst-case robustness behavior. However, for Graph Neural Networks (GNNs), the problem of certifying label flipping has far been unsolved. We change this by introducing an exact certification method, deriving both sample-wise and collective certificates. Our method leverages the Neural Tangent Kernel (NTK) to capture the training dynamics of wide networks enabling us to reformulate the bilevel optimization problem representing label flipping into a Mixed- Integer Linear Program (MILP). We apply our method to certify a broad range of GNN architectures in node classification tasks. Thereby, concerning the worst-case robustness to label flipping: (i) we establish hierarchies GNNs on different benchmark graphs; (fi) quantify the effect architectural choices such as activations, depth and skip-connections; and surprisingly, (iii) un- cover a novel phenomenon the robustness plateauing for intermediate perturba- tion budgets across all investigated datasets and architectures. While we focus GNNs, our certificates are applicable to sufficiently wide NNs general through their NTK. Thus, work presents the first exact certificate poisoning attack ever derived for neural networks, which could be of independent interest. The code is available anttps://githne com http://pc/c//p/e//eeeeaeeee
INTRODUCTION
Machine learning models are vulnerable to data poisoning where adversarial perturbations are ap- plied to the training data to compromise the performance of a model at test time (Goldblum et al.) 2023). In addition, data poisoning has been observed in practice and is recognized as a critical con- cern for practitioners and enterprises (Kumar et al. 2020 Grosse et al., 2023 Cinà al. 2024). The practical feasibility was impressively demonstrated by Carlini et al. (2024), who showed that with only $60 USD they could have poisoned several commonly used web- web-scale datasets.
Label flipping is a special type of data poisoning where a fraction of the training labels are corrupted, leaving the features unaffected. This type of attack has proven widespread effectivity ranging from classical methods for i.i.d. or graph data (Biggio et al.] 2011] Liu et al. 2219), to modern deep learning systems for images, text, or graph-based learning (Jha et al. [2023] Wan et al. 2023 Lingam Lennmlaay.LLnggmm et al., 2024). Exemplary, [Linaam et al. (2024) showed that one adversarial label flip could reduce the accuracy of Graph Convolution Networks (GCNs) (Kipf & Welling 2017) by over 17% on smaller version of Cora-ML (McCallum et al. (2000). Similarly, Fig. la demonstrates for the Karate 1977) > that one label-flip can reduce accuracy of GCN by 50%.
Club network (Zachary
Although several empirical defenses have been developed to counter label flipping attacks (Zhang al. 2020. Paudice al., 2019), they remain vulnerable to increasingly sophisticated attacks (Koh)
et al.
2022 This highlights the need for robustness certificates which offer formal guarantees
* "qqual contribution.

---

Published as a conference paper at ICLR 2025
Karute Club
CCN arc. M6a2%% Catlifidd aoc, - 20.28%
SGC are. 16. Cortified arc. 02.91%
GNN Label Flipping
NIX
SVM Label Flipping (Bilevel Problem)
(Bilevel Problem)
lelckel fippoed LANE rolous
Coneenty SFM Teaising
Our Method
Single Level Reformulstion
(Nonlineur Problem)
Envovizzaiion
NIX
GNN Cortificate
MILP Reformulation
(a) Worst-casc robustness to one label flip of two GNNs.
(b) Illustration of our label- flipping certificate.
Figure 1: (a) The Karate Club network is visualized with its labeled and unlabeled (o) nodes. The adversarial label flip calculated by our method outlined in (b) provably leads to most node predictions being flipped for two GNNs (GCN & SGC). The certified accuracy refers to the percentage of correctly classified nodes that remain robust to the attack.
that the test predictions remain unaffected under given perturbation model. However, there currently no works on certifying label poisoning for Graph Neural Networks (GNNs) and as a result, little is known about the worst-case (adversarial) robustness of different architectural choices. That a difference in behavior can be expected is motivated in Fig. la where exchanging the ReLU in a GCN with an identity function forming Simplified Graph Convolutional Network (SGC) (Wu et al. 2019), results in significantly higher worst-case robustness to label flipping for Karate Club.
In general, robustness certificates can be divided into being exact (also known as complete), i.e., returning the exact adversarial robustness of a model representing its worst-case robustness to a given perturbation model, or incomplete, representing an underestimation of the exact robustness. Complete certificates allow us to characterize and compare the effect different architectural choices have on worst-case robustness as exemplified in Fig. la whereas incomplete certificates suffer from having variable tightness for different models, making meaningful comparisons difficult (Li et al., 2023). Currently, even for i.i.d. data there are no exact poisoning certificates for NNs, and ex- isting approaches certify label-fliping are limited randomized smoothing (Rosenfeld et al., 2020) and partition-based aggregation (Levine & Feizi, [20T]) which offer incomplete guarantees for smoothed or ensembles of classifiers. Thus, adapting these techniques to graphs will not enable us to understand the effect of specific architectural choices for GNNs on their worst-case robustness. The lack of exact certificates can be understood due to the inherent complexity of capturing the effect a change in the training data has on the training dynamics and consequently, is an unsolved problem. This raises the question: is even possible to compute exact certificates against label poisoning?
In this work, we resolve this question by first deriving exact sample-wise robustness certificates for sufficiently wide NNs against label flipping and evaluate them for different GNNs focusing on semi-supervised node classification. Based on our sample-wise derivation we develop an exact collective certification strategy that certifies the entire test set simultancously. This is of particular importance for poisoning certificates, and then evaluated. Consequently, an attacker can only choose one perturbation to the training set targeting the performance process of a network, our approach takes inspiration from Gosch et al.] (2024) and makes use of the Neural Tangent Kernel (NTK) of different GNNs (Sabanayagam al. 2023), which precisely characterizes the training dynamics of sufficiently wide NNs (Arora et al. 2019). Concretely, we leverage the equivalence of wide NN trained using the soft-margin loss with a Support Vector Machine (SVM) that uses the NTK of the network as its kernel (Chen et al. (02T). This allows us to reformulate the bilevel optimization problem describing label flipping as a Mixed-Integer Linear Program (MILP) yielding certificate for wide NNs as illustrated in Fig. [bb] As the MILP scales with the number of labeled data, our method is good to certify GNNs for semi-supervised node- classification on graphs, due to the usually encountered sparse labeling. While Gosch et al. (2024) were the first to use the NTK to derive model-specific poisoning certificates, their work is limited to feature perturbations and incomplete sample-wise certification. Thus, our contributions are:
model is usually trained once on given training set
all test points. To capture the effect of label flipping on the training
(i) We derive the first exact robustness certificates for NNs against label flipping. Next to sample- wise certificates (Sec. 3.I), we develop exact collective certificates (Sec. 3.2) particularly important for characterizing the worst-case robustness of different architectures to label poisoning. Concretely, certificates apply to infinite- width NNs and hold with high probability for wide finite-width NNs.
(ii) We apply our certificates to a wide-range of GNNs for node-classification on both, real and synthetic data (Sec. [4). Thereby, we establish that worst-case robustness hierarchies are highly
2

---

Published as a conference paper at ICLR 2025
data-dependent, and quantify the effect of different graph properties and architectural choices (e.g., activations, depth, skip-connectionn on worst-case robustness.
(iii) Using the collective certificate, we uncover surprising phenomenon: across all datasets, most architectures show a worst-case robustness plateaus for intermediate attack budgets so far not ob- served with adversarial attacks (Lingam et al. 2024).
(iv) Beyond (wide) NNs, our MILP reformulation is valid for SVMs with arbitrary kernel choices. Thus, it is the first certificate for kernelized SVMs against label flipping.
Notation. We use bold upper and lowercase letters to denote a matrix A and vector a. respectively. The i-th entry of vector is denoted by dg and the ij-entry of matrix A by A.j. We use the floor operator [n] for the greatest integer S n. and [n] to denote {1, (1.2..... .n)- Further, (---) for scalar product, E for the expectation and [[]] for the indicator function. We use I|-Ipp with p 2 for
vector Euclidean norm and matrix Frobenius norm, and for vector O-norm.
2 PROBLEM SETUP AND PRELIMINARIES
We consider semi-supervised node classification, where the input graph G = (S, X) contains nodes, each associated with a feature vector x; E Rd aggregated the feature matrix X E Ruxd Graph structure is encoded in S E R20". typically representing type of adjacency matrix. Labels provided for subset of nodes (m S n1). Without loss of generality, we assume that the first m nodes are labeled. The objective is to predict the labels for the n m unlabeled nodes in transductive setting to classify newly added nodes in an inductive setting.
y E {1....,K
GNNs. An L-layer GNN fo with learnable parameters 9 takes the graph G as input and outputs a prediction for each node with [Q( m for multiclass and (G) E Rn for binary classifi- cation; the output for a node i is denoted by [o()) We consider GNNs with a linear output layer parameterized using weights (L++1) and refer to Sec. for details on the used architectures.
Infinite-width GNNs and the Neural Tangent Kernel. When the width of fe goes infinity and the parameters are initialized from Gaussian (O, 1/width), the training dynamics of fa are exactly described by its NTK (Jacot et al., 2018 Arora al. 2019). For node classification, the NTK of model fe is defined between two nodes 2 and j as Qij (el(V (Veool)))) Vefe(G),) Sabanayagam et al. 2023), where the expectation is taken over the parameter initialization.
On the Equivalence to Support Vector Machines. In the following, we focus on binary node classification with y/ E [+1] and refer to App. A for the multi-class case. We learn the parameters i of a GNN by optimizing the soft-margin loss by gradient descent:
m
1 (L+1)
min C(O,)) min
max (ofo( + 2C
O is regularization constant. In the infinite-width limit, the training dynamics for Eq. (I) are the same as those of an SVM with fe 's NTK as kernel. Thus, solving Eq. ( is equivalent to solving the dual problem of SVM without bias (Gosch et al. 2024 Chen et al. 20211:
where C' >
m
m m
Py(y: : min Σ a5
+
ΣΣ ==
yauoaa, s.t. OSa a S. Ci e [m)
where a E R.m are the SVM dual variables, and Qiy the NTK of fo between nodes and j. The solution to Eq. 22) is not guaranteed to be unique; hence, denote by S(y) the set of a vectors solving Py().. Given any a, an SVM predicts the label of a node / by computing sign(> mm im= I:a:Q.:).
On widht GNN Certification using NTK. Any exact certificate derived for SVM with NTK as its kernel directly provides exact deterministic guarantees for infinite-width GNNs through their cquivalence. Concerning the finite-width case, where w denotes the smallest wayth of the GNN, the output difference to the SVM is bounded by O In with probability exp( ((w))
//w
shown in Gosch et al. 2024]; Liu al. 2020) (see App. E for more model-specine guarantees). Thus, for increasing w the output difference approaches O while the probability approaches 1. Note that the certificate becomes incomplete for fixed finite but not sufficiently wide network.
3

---

Published as a conference paper at ICLR 2025
Label Poisoning. We assume that before training the adversary A has control over the labels of an
e-fraction of labeled nodes. Formally, A can choose perturbed labels y E A(y) == {ý E [K] ll vllo $ [em]] with the goal to minimize the correct predictions of test nodes described by an attack objective Latt (0, 3) after training on y. This can be written as a bilevel optimization problem
min Case Ca (), S.t. y E A(y) A 0 E arg min C("', 9). y.
(3)
Prior Work on Poisoning and its Bilevel Formulation. Developing poisoning attacks by approx- imately solving the associated bilevel problem is common for SVMs (Biggio et al.; (2012), deep networks (Muñoz-González et al., 2017 Koh al. 2022), and GNNs alike Ziigner & Günnemann 2019). From these, we highlight Mei & Zhu (2015) who focus on SVMs and similar to us, transform the bilevel problem into a single-level one, but only approximately solve with a gradient-based ap- proach and don't It consider label flipping. Regarding label flipping. [Biggio et al. (2011) and Xiao al. 2012) develop attacks for SVMs solving Eq. (3) with non-gradient based heuristics; [Lingam it al. 2024 create an attack for GNNs by solving Eq. ( with a regression loss, replacing the GCN with a surrogate model given by the NTK. Concerning certificates for data poisoning, there are only few works with none providing exact guarantees. The approaches based differential privacy (Mal iet al. (2019), randomized smoothing (Rosenfeld et al.] 2020] Lai et al. 2024), and majority voting (Levine & Feizi 2021) are inherently incomplete. In contrast, similar us. Goocch et al. (2024) directly solve the bilevel formulation to obtain sample-wise feature poisoning certificates for wide (G)NNs. However, their reformulation not exact or applicable to the label flipping problem, and they do not provide a collective certificate. We detail the technical differences in App.
3 LABELCERT FOR LABEL POISONING
Our derivation of label flipping certificates for GNNs is fundamentally based on the equivalence with an SVM using the NTK of the corresponding network as its kernel. Concretely, our derivations follow three high-level steps depicted in Fig. lb (i) we instantiate the bilevel problem in Eq. (3) for (kernelized) SVMs with a loss describing misclassification and using properties of the SVM's dual formulation, we transform it into single-level non-linear optimization problem; (fi) we introduce linearizations of the non-linear terms, allowing us to further reformulate the non-linear problem into an equivalent mixed-integer linear program; and (iéi) by choosing the NTK of a network as the kernel, solving the resulting MILP yields a certificate for the corresponding sufficiently-wide NN. In Sec. we present our sample-wise certificate for label flipping and then, derive collective certification strategy in Sec. 3.2 We note that the reformulation process requires no approximations relaxations; hence, the derived certificates
exact. In what follows, dual formulation as our model, hence the model parameters 0 are the dual variables a. Further, we present the certificates for binary labels yı {+1] and discuss the multi-class case in App. A
choose SVM in its
3.1 SAMPLE- WISE CERTIFICATION
To obtain a sample-wist certificate, we have to prove that the model prediction for test node & can't ' be changed by training on any y E A(y). Let a be an optimal solution to the dual problem (y) obtained by training on the original labels y and denote by P. > yaaa Qts the corresponding SVM's prediction for t. Similary, let a be an optimal solution to Py(ý) with perturbed labels y and the new prediction be Pt. Ei Qti. As an SVM assigns class based on the sign of its prediction, the class prediction changes if and only if sign(f:) pt о Thus, the bilevel problem
Pz(y): min sign (p:) a.y
Σ Bi
s.t. EE A a
(4)
certifies robustness, if the optimal solution is > 0. However, bilevel problems are notoriously hard to solve (Schmidt & Beck 2023), making P2(y) intractable in its current form. Now, notice that the inner optmization problem a E S(ý) consists of the SVM's dual problem P1(5), which is convex and fulfills Slater's ss condition for every ý (see App. B). Thus, we can replace a E St)) with P1 (s''s Kahush-Kuhn-Jie Tucker (KKT) conditions to obtain single-level problem P3(y) that shares
In our implementation, we treat the undefined case of pr Pt as misclassification.
4

---

Published as a conference paper at ICLR 2025
the same optimal solutions as P2(y) (Dempe & Dutta 2012). The KKT conditions define three sets of constraints. First, stationarity constraints from the derivate of the Lagrangian of Py(y):
Vi E [m]
Σ U.j -1
(5)
where u1 v E m are the Lagrangian dual variables. Secondly, feasibility ranges for all i E [m]:
aj 0, C 0g 0, Uy 2 0, U/ 2 0, and lastly, the complementary slackness constraints:
Vi E [m]] i 0, ua(C - 0;) =
(6)
Thus, the resulting single-level optimization problem P3(y) now optimizes over y. u and v.
A Mixeed-nteger Linear Reformulation. (3(y) is difficult solve non-linear problem Eq. (5)
defines multilinear constraints and both, the objective and Eq. (6) are bilinear. Thus, to make (y tractable, introduce (exact) linearizations of all non-linearities, as well linearly model the adversary y E A(y).
(t) Modeling the adversary: First, have to ensure that the variable ý E {-1,1}"m To do so, model y as being continuous and introduce a binary variable y' 10, that enforces ý (-1,1] through adding the constraint yJ 2y( - 1 for all i E [m]. Then, the bounded perturbation strength | yllo I [cm] can be formulated as:
172
yeut S 2 eem].
(ii) Objective and Stationarity constraint: The non-linear product terms in the objective can be lin- earized by introducing
variable Rm with o,Üi- Since for all E [mi] it holds that 0 S a, S C and U. E [=1], the multiplication 2; = a,Ü; can be modeled by
Vi E [m]
S S
C(1 ū.) S C(1 + ū:)
(8)
Thus, replacing all product terms a, in Py with 2; and adding the linear constraints of Eq. (8) resolves the non-linearity the objective. As the product terms also appear in the stationarity u, v 0.
constraints of Eq. (5) they become bilinear reading Vi [m]. Σラ= 21
As the non-linear product terms Dızy in the stationarity constraints binary with a continuous variable, we linearize them following a similar strategy. We introduce a
also the multiplication of
new variable R R m with Ry representing Diz and replace all occurrences of Tizg with Rij-
Then, as -C < zj < C we model Rij 2i by adding the linear constraints
Vi,j E [m] CC + 01) < R2j 2j S C(1 + 0:), -C(1 ū.) < R.j 23 S C(1 0.) (9)
resolving the remaining non- linearity in the stationarity constraint.
(iit) Complementary Slackness constraints: The bilinear complementary slackness constraints in Eq. (6) represent conditionals: if a; 0 then u, = else u, 2 and similar for 2;- Thus, we model them using equivalent big- formulation:
Vi [m]
u, S Ma, Si, a, C(1 st). s; e (0,
0; S Mo,t,. C- < C(1 42), t; E 1}.
(10)
where introduce binary variables t 10.1) and large positive constants Ma, and My, for each E [m]. Usually, defining valid big-M's for complementary slackness constraints prohibitively difficltt (Kleinert al. 2020). However, in App. C we show how to special structure in our problem to set valid and small big-M values, not cutting away the relevant optimal solutions to Py(y).
With all non-linear terms in Pa(y) linearized and having modeled ý E A(y), we can now state:
Theorem (Sample-wise MILP) Given the adversary A and positive constants Ma, and Ma, set in App. for all i [m)) the prediction for node f. is certifiably robust the optimal solution to
5

---

Published as a conference paper at ICLR 2025
the MILP P(y), given below, is greater than zero and non- non-robust otherwise.
P(y): min 8. 2 u.v.s.t.R
sign (pc)
QQu 8.1.
yı S 2 Vi E [m]] D: =22/
m
Vi,j
[m]]
Rí Quj 1 14 + U/ 0, U4 00 8s 12 0, 1/5 E {0,1},
j=1
C(1 + U1) $ Ray 22 5 C(1+ -C(1 1.) - Rūj- - 2, - C(1 - -;),
a, 2, S ai 0: C(1 (1) 2 C(1 + ū:) 0g,
44 S Mi, 04 C(1 - 81), t S Ma ai 2 Cl2, & (0.1), 4 E (0, 13.
Computational Complexity. The inputs to MILP Ply) are computed in polynomial time: the NTK Q in (m²) and the positive constants M2 and M, in ((m). While these contribute polynomial complexity, the overall computation of the certificate is dominated by the MILP solution process, which NP-hard with exponential complexity. Thus, the computation is dominated by the MILP whose runtime strongly correlates with the number of integer variables. P(y) has in total 3m binary variables and thus, it gets more difficult to solve as the number of labeled training data increases.
3.2 COLLECTIVE CERTIFICATION
For collective certification, the objective is to compute the number of test predictions that simul- taneously robust to any y E A(y).. This implies that the adversary is restricted to choose only one y to misclassify a maximum number of nodes. Thus, it is fundamentally different from sample-wise certification, which certifies each test node independently. Let 'T be the set of test nodes. Then, the collective certificate can be formulated using Eq. 33) by choosing to maximize EveT L * pr] as:
Cyly :mxx
L # Pcl
s.t. E A(y) A a E S(g).
(11)
LET
Following the sample-wise certificate, we transform the bilevel problem Cy into a single-level one, by replacing the inner problem linear modeling techniques for the stationarity and complementary slackness constraints, as well as for the adversary. To tackle the remaining non-linear objective, we first introduce a variable Vt E T and write the single-level problem obtained so far as:
S(ý) with its KKT conditions. Then, apply the same
E {0, 1} 17 where c.
L.:: # po]
m
C2(y):
max y.y''' U.V.S.
Σe, a s.l. Pt =
Σ 2,1ss constraints of P(y),
LET
VET
sign(p:) Pc > 0 then c = else c. 1.
Now, notice that because -C < C for all i [m]] Pt is bounded as - -C 1Qul S Pt I C' Et t IQuil for all t E T. Let 4, and h, be the respective lower and upper bounds to pt. Then, we can linearize the conditional constraints in Cy()):
Vt E T: Vp, > 0 S (c), 2 40x,
Vg. < 0:: p. 2 4(1 - -a), Pt S hGc. (12)
As result, we can state the following theorem (in App. D we formally write out all constraints):
Theorem (Collective MILP) Given the adversary A. positive constants Ma; and My; set as in
App. for all E [m]. and 1, h e R with 4 = -C 'Qui and he = C C 1uel the maximum number of test nodes that are certifiably non-robust is given by the MILP Cly).
-
m
Cly): max Σe c
s.t. constraints of Ply). V WET:p :P: Σ
2Q0 4 {0, 1),
c.a.".y'' IET
WET: Vp. 0: p: S he(1 cc), Pt. hen, Vp. 0 Pe 2 4 - ct) Pt S h4c.
Computational Complexity. C(y) has 3m + [T] binary variables. Thus, the larger the set to verify, the more complex to solve the MIL.P

---

Published as a conference paper at ICLR 2025
10.
Ceriifed Accirary
Coriifdd Avcurary
SGO XPPNP
Certiiel Aceumyy
APPPr CITY GrelekkEE
GIN
GIN
GRIESAGE
Sigea
GEUN Strp-n
GUN Skieo
0.4
Skip-PO
MIP
62:
E
0/6
0.16
02
0.5
0.15
0:55
01
0.10
0.35 0.
Perturbation budgger e
Perturbation brcggot
Perturbation budget e
(a) Cora-MLb (Sample-wise)
(b) Citeseerb (Sample-wise)
(c) CSBM (Sample-wise
Figure 2: Certified accuracies as given by our sample- wise certificate, for multi-class Cora-ML and Citeseer see App. other datasets in App. H.I A clear and consistent hierarchy emerges across perturbation budgets concerning the worst-case robustness of different GNNs.
EXPERIMENTAL RESULTS
In Sec. 4.1 we thoroughly investigate our sample-wis wise and collective certificates. Sec. 4.2 discusses in detail the effect of architectural choices and graph structure.
Datasets. We use the real-world graph datasets Cora-ML (Bojchevski & Günneeannn 2018 and Citeseer (Giles et al.] 1998) for multi-class certification. We evaluate binary class certification using Polblogs (Adaii & Glance, 2005), and by extracting the subgraphs containing the top two largest classes from Cora-ML, Citeseer Wiki-CS (Mernyei & Cangea 2020). Cora (McCallum et al. 2000 and Chameleon (Rozemberezki al. 2021) referring these Cora-MLb, Citeseerb, Wiki-CSb, Corab and Chameleonb, respectively. To investigate the influence of graph-specific properties on the worst-case robustness, we generate synthetic datasets using random graph models, the Contex- tual Stochastic Block Model (CSBM) (Deshpande et al.) 2018) and the Contextual Barabási-Albert Model (CBA) (Gosch et al., 2023). We sample a graph of size n 200 from CSBM and CBA. We refer to App. G for the sampling scheme and dataset statistics. We choose 10 nodes per class for training for all datasets, except for Citeseer, for which we choose 20. No separate validation set is needed as we perform 4-fold vols-vvlidation (CV) for hyperparameter tuning. All results are averaged over 5 seeds (multiclass datasets: 3 seeds) and reported with their standard deviation.
GNN Architectures. We evaluate broad range of convolution-bart and PugeRank-basee GNNs: GCN (Kipi & Welling (017)) SGC (Wu et al. 2019), GraphSAGE (Hamilton et al. 2017). GIN (Xu et al. 2019), APPNP (Gasteiger al. 2019), and GCN with two skip-connection variants namely GCN SCip-PC and GCN Skip-a (Sabanayagam et al.) [203).. We also evaluate an MLP. All results concern the infinite-width limit and are obtained by solving the MILPs in Thm. and Thm.
lusing Gurobi 11.0.1 (Gurobi Optimization, LLC (2023) and the GNN's NTK as derived in Gosch et al. (2024) and Sabanayagam et al. (2023). We investigate L = {1. 4) hidden layers, not explicitly stated, I All other hyperparameters are chosen based on 4-fold CV, given in App. G.2 We define the
row and symmetric normalizations as Snow D- A. Saym D 10011/220 A/ 1/22 with D and Å the degree and adjacency matrices of the given graph g with an added self-loop.
{0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.5, 1} for the adversary A, and define .A's strength as 'weak' if e E (0, 0.1). 'intermediate' if e E (0.1, and 'strong' if E (0.3, 1]. The test set for collective certificates consists of all unlabeled nodes on CSBM and CBA, and random samples of 50 unlabeled nodes for real-world graphs. The sample- wise certificate is calculated all unlabeled nodes. We report certified ratios, referring to the percentage of test-node predictions that are provably robust to A. For sample-wise certificates, also report certified accuracy, that the percentage of correctly classified nodes that are also provably robust to A. As our results are obtained with exact certificates, they establish a hierarchy of the investigated models regarding worst-case robustness to label flipping for given dataset and which we refer to as 'robustness hierarchy' or 'robustness ranking'. Since no prior work on exact certification for label flipping exists, the only baseline for comparison is an exhaustive enumeration of all possible perturbations infeasible for anything beyond one or two label flips.
Evaluation. We consider perturbation budgets
4.1 CERTIFIABLE ROBUSTNESS OF GNNS TO LABEL POISONING
We start by demonstrating the effectiveness of our sample-wise certificate to certify a large spec- trum of GNNs against label flipping on different datasets in Fig. Interestingly, our certificate
7

---

Published as a conference paper at ICLR 2025
Table 1: Certified ratios in [%] calculated with our exact collective certificate on different datasets for (0.05, 0.1, 0.1,0.15) 0.15) (see App. H.2.1 for all e). As baseline for comparison, the certified ratio of a GCN is reported. Then, for the other models, we report their absolute change in certified ratio compared GCN, i.e., their certified ratio minus the mean certified ratio of GCN. The most robust model for choice of is highlighted in bold, the least robust in red.
Cora-MLb
Citeveerb 0.10
CSBM
0.05
0.10
0.15
0.15
0.05
0.10
0.15
GCN
86.4 16
55.6 107
46.8 1:60
65.6 125
50.0 1977
41.6 1:
85.7 1.3
67.0 197
48.0 1:0
SGC
=2
+7.6
+28 +61
+3.6 =90
+0.4 + 108
+04+
+7.8 #:2
+21.9 =5
+34.3 #3
APPNP
46.8 123
-2
+4.0 4:5
+08811
-2.4
-2.1 1M
-6.2
-1.7
4.8 1:41
+6.0
2.0
1A6
1866
+1,2
1K7
150
+2.6 1.0
GraphSAGE
-6.0
+1.2 =32
+16
+9.6 1:36
+3.2
+2.4
-0.2 #:4
-2.3 s:00
+0.6 1:44
GCN Skip-o
-1.2
+1.
-0.1
+2.1
GCN Skip-PC
-2.0=60
+3
+354
+15.6
+9.2 55
+3.6 2.
+4.9 #:0
+15.0 =22
+20.1 296
MI.P
121
18
1.3
104
-04
19.
-16.3
4,2
SKN Stq-
SiC
GUN Str-PU
5GC
GUN Sep-1N
Cartifee Ratio
6.2
Cattiee Patio
APPNP Ouleeise
CertiSed Ratlo
APFN
84
8
6.
0.36
02
3.25
C3
005
011
0.10 02
0.25 01
055
000
0.5 0.1
0.15
02
0.25
0.5
Perturbation bunggel
Perturbation bunggel
c
Perterbation budger
(a) Cora-MLb (Collect. & Sample.) (b) Citeseerb (Collect. & Sample.)
(c) CSBM (Collect. & Sample.)
Figure 3: Certified ratios of selected architectures as calculated with our sample- wise and collective certificate. We refer to App. H.2.22 for collective results all GNNs. Collective certification pro- vides significantly higher certified ratios, and uncovers a plateauing phenomenon for intermediate e.
highlights: (i) a clear and nearly consistent hierarchy emerges across perturbation budgets c. Ex- emplary, for Cora-MLb (Fig. 2a) and 0.05, APPNP is most robust achieving certified accuracy of 79.1 + 10.9%, whereas GraphSAGE achieves only 52.8 + 5.8%, and an MLP even drops to 22.7 + 5% In addition, the rankings of the GNNs stay nearly consistent across perturbations for all datasets. (ii) The rankings of GNNs differ for each dataset. Exemplary, in contrast to Cora-MLb, the most robust model for Citeseerb is GCN Skip-PC (Fig, 2b), and for CSBM is SGC (Fig. 2c). (ūāt) Our certificate identifies the smallest perturbation beyond which no model prediction is cer- rifiably robust for each dataset. From Fig. the thresholds for Cora-MI.b is (0.15, 0.2), for Cite- seerb is (0.1, 0.15, and for CSBM is (.2)) except for GCN Skip-PC at (0.2, 0.25 and SGC
at (0.25, 0.3). These findings underscore the capabilities of sample-wise certificates to provide a detailed analysis of the worst-case robustness of GNNs to label poisoning.
We now move to collective certification which is a more practical setting from the adversary's perspective, where the attacker can change the training dataset only once to misclassify the entire test set. Here, we demonstrate the capabilities of our Thm. 2 in certifying GNNs. In Fig. 3 we contrast the certified ratios obtained by sample-wise certification with those obtained by our collec- tive certificate for selected architectures. They highlight a stark contrast between sample-wise and collective certification, with the collective certificate leading to significantly higher certified ratios, and the capability to certify even strong adversaries. Exemplary, Fig. 33 shows for the intermediate perturbation E 0.2 that the sample-wise certificate cannot certify any GNN. However, the collec- tive certificate leads to certified ratios of > 40% for all shown GNNs. This substantial difference because the adversary is now restricted to creating only a single label perturbation attack the entire test data, but the magnitude of the difference in certified ratios is still significant. Further, the most robust model may not coincide with the sample-we wise case as e.g., for Cora-ML.b < 0.1 APPNP achieves the highest sample-wist but from Tab. [ SGC the highest collective robustness. This highlights the importance of collective certification to understand the worst-case robustness for the more practical scenario. In App. H.2.4 we calculate average robustness rankings for GNNs for more comprehensive e ranges and show that collective robustness rankings too are data dependent.
Fig, Ba shows another surprising phenomenon uncovered by our collective certificate. The certified ratio seems to plateau for intermediate budgets e E [0.15, 0.3). Exemplary, for SGC and APPNP, the certified ratio from 0.2 to e 0.25 reduces by only 0.8%, whereas the drop between
8

---

Published as a conference paper at ICLR 2025
GUN
OCN UEN Stip
Certifeed Raião
Certifll Raisa
Certifel Raião
GEN Skiper
0.4
0.0
00
010
01
0,6
022
01:0 0.5
10.
11.6
0.1
0.5
02
0125
05
055
0305
04
R05
0.5 03 uS
Portorbatton
budgett
Perturtiaiio budget.
Pertartation hudges,
(a) Saw VS Sym in Cora-MLb (left) Citeseerb (right)
(b) Skip-o vs depth in Cora-MLb
Figure 4: Selected architectural findings based on our collective certificates. (a) The effect of graph normalizations Srow and Sym data-dependent. (b) For
depth does not improve robustness, shown for GCN Skip-a, see App. H.2.5 for other GNNs and datasets.
CINES
11 12 1r El
Ci 12 12
13
to e3
Do Eo 03 Fettrratin briget
(a) Cora-MLb: APPNP
(b) Cora-MLb: GCN
(c) CSBM: Density
(d) CSBM: Homophily
Figure 5: Graph structure findings based on our collective certificates. (a)-(b) (b) The higher amount of graph information improves certifiable robustness. (c) (d) Graph density and homophily positively
affect the certifiable robustness, shown for GCN using CSBM, see App. f.2.6ffor more results.
0.05 t 0.01 is 25.6% and 27.2%. respectively. The certified ratio of GCN for 0.2 and e = 0.25 stays even constant (Tab. () as is also observed for GCN Skip-a (Fig. 4b). The plateau for intermediate appears for some architectures on Citeseerb, Wiki-CSb and Chameleonb, but is less pronounced, whereas Polblogsb shows near perfect plateauing (see App. H.2.3). On CSBM, SGC and GCN Skip-PC do not exhibit plateauing, while other architectures show a prominent plateau for intermediate e (Fig.3e) interestingly. a robustness plateau can be provoked by increasing the density in the graph (Figs. [c and [d).. However, graph structure alone cannot explain the phenomenon, as Fig. 3c also shows near constancy of an MLP from 0.15 to = 0.2.
Another strong observation from the sample-wise and collective certificates is the importance of graph structure in improving the worst-case robustness of GNNs. From the certified accuracies in Fig. 2 an MLP always the least accurate model without any perturbation robust than its GNN counterparts, as expected. Interestingly, the certified ratio plots in Fig. [ show that MLP consistently the least robust and the most vulnerable model for weak perturbation bud- gets. Thus, leveraging graph structure consistently improves sample-wist and collective robustness label flipping, which is studied in detail in Sec. 4.2
0), and also less
4.2 FINDINGS ON ARCHITECTURAL CHOICES AND GRAPH STRUCTURE
Leveraging our collective certificate, we investigate the influence different architectural choices on certifiable robustness. (I) Linear activations in GNNs known to generalize well. Exem- plary, SGC, which replaces the ReLU non-linearity in GCN to linear activation, achieves better or similar generalization performance as GCN, both empirically (Wu et al. 2019) and theoreti- cally Sabanayagam et al. (2023). Complementing these results, we find that SGC is consistently better ranked than GCN across all datasets (Tab. [3). suggesting that linear activation is as good as or better than ReLU for certifiable robustness as well. (II) Additionally, in SGC and GCN, the graph normalization a design choice with Snow and Saym being popular. While previous works Wang et al.) 2018 [Sabanayagam et al.) 2023) suggest that S.m. leads to better generalization than Saym, our findings show that the effectiveness of these normalizations for certifiable robustness is highly dataset-dependenn
demonstrated in Fig. 4a for Cora-MLb and Citeseerb. (LII) Skip- connections in GNNs are promoted to construct GNNs with large depths as is shown to mitigate over-smoothing (Chen et al., 2020). Our findings show that increasing the depth in GNNs with skip-connections has either little or more pronounced negative effects on certifiable robustness, evidenced in Fig. 4b. For other GNNs and more general study depth refer Fig.

---

Published as a conference paper at ICLR 2025
Next, building on the importance of graph information, conduct deeper study into the influence of graph structure and its connectivity on certifiable robustness. (I) We first explore the role of graph input in the GNNs: in APPNP, the a parameter controls the degree of graph information incorporated into the network-lowe a implies more graph information. Similarly, in convolution- based GNNs, the graph structure matrix S in GCN can be computed using weighted adjacency matrix 3A. These experiments clearly confirm that increasing the amount of graph information improves certifiable robustness up to intermediate attack budgets, as demonstrated for Cora- MLb in Figs. 5a and 5b Interestingly, for stronger budgets, the observation changes where more graph information hurts certifiable robustness, pattern similarly observed in Goosc et al.) (2024) for feature poisoning using an incomplete sample-wise certificate. (I7) We then analyze the effect of graph density and homophily by taking advantage of the random graph models. To assess graph density, we proportionally vary the density of connections within (p) and outside (g) the classes, while for homophily, we vary only keeping fixed. The results consistently show that higher graph density and increased homophily improves certitiable robustness with inflection point for stronger budgets as observed in Figs. 5e [5] Additionally, our results generalize to changing the number of labeled nodes (App. H.2.7 and to dynamic graphs that evolve over time (App. H.4.
CONCLUSION
By leveraging the NTK that describes the training dynamics of wide neural networks, introduce the first exact certificate for label flipping applicable to NNs. Crucially, we develop not only sample- wise but also collective certificates, and establish several significant takeaways by evaluating broad range of GNNs on different node classification datasets:
Key Takeaways on Certifying GNNs Against Label Poisoning
robustness hierarchies of GNNs are strongly data dependent. 2. Collective certificates complement sample-wise, providing holistic picture of the
There is no silver bullet:
worst-case robustness of models.
3. Certifiable robustness plateaus at intermediate perturbation budgets.
4. Linear activation helps, and depth in skip-connections hurts certifiable robustness.
5. Graph structure helps improving robustness against label poisoning.
Among the results, the intriguing plateauing of certifiable robustness in collective evaluation has so far not been observed. While we conduct a preliminary experimental investigation, the cause of the plateauing is still unclear, and a more rigorous analysis remains an open avenue for future research.
Generality of our certification framework. Our certification strategy extends beyond GNNs and applies to general wide NNs through their NTKs and any kernelized SVM. Exemplary, we demon- strate the applicability to MLP in Sec. 4 and to linear kernel XXx where X is the feature matrix (a non-NN based model) in H.3 In addition, since our certificates leverage the NTK of the NN, they hold with respect to expectation over network initializations. As result, they provide guarantees at the population level of the parameters, thus certifying NN for general parameteriza- tion. This distinguishes our framework from most certification methods, which typically focus on guarantees for a specific, fixed network parameterization.
Scalability. Exact certification, even for the much simpler case of test-time attacks, where the model to be certified is fixed, is already NP-hard (Katz et al. 2017). Thus, it is inherently difficult and a current, unsolved problem scale exact certificates to large datasets. In fact, state-of-the-ar exact
certificates against test-time (evasion) attacks for image classification scale up to CIFAR-10 (Li al. 2023), and for GNNs to graphs the size of Citeseer (Hojny et al., 2024). Similarly, we find that the scaling limits of our certificates are graphs the size of Cora-ML. or Citeseer, even though the exact certification of poisoning attacks adds additional complexity with the model being certified is not fixed and the training dynamics must be included in the certification. As first step toward improving scalability, we introduce a more scalable but incomplete multi-class certification strategy in App. A.2 that relaxes exactness. Here, observe that the results surprisingly close and often even match the exact certificate. This demonstrates the effectiveness of our relaxation and highlights that further analysis into its tightness an interesting topic for future study.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
Our work allows for the first time exact quantification of the worst-case robustness of different (wide) GNNs label poisoning. While a potentially malicious user could misuse these insights, we are convinced that understanding the robustness limitations of neural networks in general and GNNs, particular, is crucial to enable safe deployment of these models in the present and future. Thus, we believe the potential benefits of robustness research outweigh its risks. Additionally, we do not see any immediate risk stemming from our work.
7 REPRODUCIBILITY STATEMENT
We undertook great efforts to make our results reproducible. In particular, the experimental de- tails are outlined detail in Sec. 4 and App. G All chosen hyperparameters are listed App. G Randomness in all experiments is controlled through the setting of seeds in involved pseudorandom number generators. The code to reproduce our results, including all experimental configuration files, can be found at
com/ saper0/ cppertt
ACKNOWLEDGEMENTS
The authors thank Aleksei Kuvshinov, Arthur Kosmala and Pascal Esser for the helpful feedback on the manuscript. This paper has been supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the German Federal Ministry Education and Research; by the German Research Foundation, grant GU 1409/4-1; as well as by the TUM Georg Nemetschek Institute Artificial Intelligence for the Built World.
REFERENCES
Lada A Adamic and Natalic Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, 2005.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems (NeurIPS), 2019.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Proceedings of the Asian Conference on Machine Learning. PMLR, 2011.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector ma- chines. In International Conference on Machine Learning (ICML), 2012.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In International Conference on Learning Representations, 2018.
N. Carlini, M. Jagielski, C. A. Choquette- Chhoo, D. Paleka, W. Pearce, H. Anderson, A. Terzis, K. Thomas, and F, Tramer. Poisoning web-scale training datasets practical. In 2024 IEEE Symposium on Security and Privacy (SP), 2024.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, In International Conference on Machine Learning (ICML), 2020.
Yilan Chen, Wei Huang, Lam Nguyen, and Tsui-Wei Weng. On the equivalence between neu- ral network and support vector machine. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Antonio Emanuele Cinà, Kathrin Grosse, Ambra Demontis, Battista Biggio, Fabio Roli, and Mar- cello Pelillo. Machine learning security against data poisoning: Are we there yet? Computer, 2024.
11

---

Published as a conference paper at ICLR 2025
S. Dempe and J. Dutta. Is bilevel programming special of mathematical program with complementarity constraints? Mathematical Programming. 2012.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations (ICLR), 2019.
C LLee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, 1998.
M. Goldblum, D. Tsipras, C. Xie, X. Chen, A. Schwarzschild, D. Song, A. Madry, B. Li, and T. Goldstein. Dataset security for machine learning: Data poisoning, backdoor attacks, and de- fenses. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2023.
Lukas Gosch, Daniel Sturm, Simon Geisler, and Stephan Günnemann. Revisiting robustness in graph machine learning. In International Conference on Learning Representations (ICLR), 2023.
Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, and Stephan Günnemann. Provable robustmess of (graph) neural networks against data poisoning and backdoor attacks. arXiv preprint arXiv:2407./0860 2024.
Kathrin Grosse, Lukas Bieringer, Tarek R. Besold, Battista Biggio, and Katharina Krombholz. Ma- chine learning security in industry: A quantitative survey. IEEE Transactions on Information Forensics and Security, 18:1749-1762 2023.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs Advances in neural information processing systems (NeurIPS), 2017.
Christopher Hojny, Shiqiang Zhang, Juan S. Campos, and Ruth Misener. Verifying message-passing neural networks via espology-based bounds tightening. In Proceedings of the 41st International Conference On Machine Learning. Vienna, Austria, PMLR 235, 2024.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Rishi Dev Jha, Jonathan Hayase, and Sewoong Oh. Label poisoning is all you need. In Thirty- seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle D. Julian, and Mykel J. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. International Conference on Computer Aided Verification, 2017.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. Journal of Machine Learming Research (JMLR), 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Thomas Kleinert, Martin Labbé, Fränk Plein, and Martin Schmidt. There's no free lunch: On the hardness of choosing correct big-m in bilevel optimization. Operations Research, 68 (6):1716- 1721, 2020. doi: https://doi..og hrtp:///doo.or////00 1.. 1117//ppe..20111111 1944..944.
Pang Wei Koh, Jacob Steinhardt, and Perey Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning, 2022.
Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia. Adversarial machine learning-indun per- spectives. In 2020 IEFE security and privacy workshops (SPW). IEEF, 2020.
12

---

Published as a conference paper at ICLR 2025
Yumi Lai, Yulin Zhu, Bailin Pan, and Kai Zhou. Node-aware bi-smoothing: Certified robustness against graph injection attacks. In IEEE Symposium on Security and Privacy (SP), 2024.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference Learning Representations (ICLR), 2021.
Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. In IEEE Sympo- sium on Security and Privacy (IEEE S&P), 2023.
Vijay Lingam, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Rethinking label poisoning for GNNs: Pitfalls and attacks. In International Conference Learning Representa- tions (ICLR),2024
Chaoyue Liu, Libin Zhu, and Misha Belkin, On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Xuanqing Liu, Si Si, Xiaojin Zhu, Yang Li, and Cho-Jui Hsich. A unified framework for data poisoning attack to graph-based semi-supervised learning. Conference Neural Information Processing Systems (NeurIPS), 2019.
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentialll--rrival learners: Attacks and defenses. In International Joint Conference Artificial Intelligence (IJCAI), 2019.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In Association for the Advancement of Artificial Intelligence (AAAI), 2015.
Péter Mernyei and Cätälina Cangea. Wiki-es: A wikipedia- based benchmark for graph neural net- works. Graph Representations and Beyond Workshop @ ICML, 2020.
Luis MuñoozGGozzllez, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradien optimization. In Proceedings of the 10th ACM workshop on artificial intelligence and security, 2017.
Andrea Paudice, Luis Gonzálzz and Emil C Lupu. Label sanitization against label flipping poisoning attacks. In ECML PKDD 2018 Workshops: Nemesis 2018, UrbReas 2018, SoGood 2018, IWAISe 2018, and Green Data Mining 2018, Dublin, Ireland, September 10-14, 2018, Proceedings 18, 2019.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In International Conference on Machine Learning (ICML), 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
Mahalakshmi Sabanayagam, Pascal Esser, and Debarghya Ghoshdastidar. Analysis of convolutions, non-linearity and depth in graph neural networks using neural tangent kernel. Transactions on Machine Learning Research (TMLR), 2023.
Martin Schmidt and Yasmine Beck. A gentle and incomplete introduction bilevel optimization. In Lecture Notes, Trier University, 2023.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008.
Alexander Wan, Eric Wallace, Sheng Shen, and Dan Klein. Poisoning language models during instruction tuning. In International Conference on Machine Learning (ICML), 2023.
Xiaoyun Wang, Minhao Cheng, Joe Eaton, Cho-Jui Hsich, and Felix Wu. Attack graph convolutional 10751, networks by adding fake nodes. arXiv preprint arXiv: 1875. 2018.
13

---

Published as a conference paper at ICLR 2025
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International Conference on Machine Learning (ICML) 2019.
Han Xiao, Huang Xiao, and Claudia Bekert. Adversarial label flips attack on support vector ma- chines. In ECA! 2012. 2012.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Wayne W Zachary, An information flow model for conflict and fission in small groups Journal of anthropological research, 1977.
Mengmei Zhang, Linmei Hu, Chuan Shi, and Xiao Wang. Adversarial label-flipping attack and defense for graph neural networks. In 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 2020.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Representations (ICLR), 2019.
14

---

Published as a conference paper at ICLR 2025
A MULTI-CLASS LABEL CERTIFICATION
To generalize the binary classification setting in Sec. to multi-class classification, we use a one-vs- all classification approach. This means, given K classes, K binary learning problems are created, one corresponding to each class E [K], where the goal is to correctly distinguish instances of class c from the other classes d' E [ c' * c, which are collected into one "rest" class. Assume that Pa is the prediction score of a classifier for the learning problem corresponding to class Then, the class prediction c* for a node is constructed by ex arg max Pe-
In the following, we first present exact multi-class certificate in App. A.I and present relaxed (incomplete) certificate in App. A.2 that significantly improves computational speed while being empirically nearly as tight as the exact certificate.
A.1 EXACT CERTIFICATE
For the following development of an exact certificate for the multi-class case, we assume an SVM given in its dual formulation (Eq. (2) as our model. Further, without loss of generality, assume for a learning problem corresponding to class e that nodes having class e will get label 1 and nodes corresponding to the other classes e' E [K], d' * have label -1. We collect the labels for the learning problem associated e in the vector y The original multi-class labels are collected the vector y. Thus, one y defines tuple (y'..... ..........) y²). Thus, any ý A(y) spawns perturbed tuple (y) . ). ). We denote by è the originally predicted class with prediction score pa.
To know whether the prediction can be changed by particular ý E A(y), we need to know if Ps max Pe can be forced to be smaller than 0 for any y E A(y). By collecting the individual predictions in a vector p E RK this problem can be formulated as the following optimization problem:
Mi (y): min
PE - pp"
(13)
p.p" 8 S
s.t. p² =
max Po [
(14)
m
Ve [K] Pe = max
oa s.l. a S89)
(15)
(y',..., 5*) E A (ly y*))
(16)
where we represented y E A(y) in Eq. 16 equivalently by the labels y defined for each of the K learning problems. First note that M₁ ( defines a complicated (trilevel) optimization problem where Eq. (15) defines K bilevel problems that are independent of one another. However, observe that the objective in Eq. (15) represents the prediction of an SVM for node and thus, Σ &ra has the same value for any choice of a E S()"), i.e., while the optimal dual variables are not unique, the prediction value As a result, problem (ý) can be written equivalently as
M2(y): min Pe p"
(17)
P.P" "'......
s.t. p"
max Pe
(18)
<E[K](()
m
Vc [K] Pe = Σ HajQu
(19)
a E S(y")
(20)
(
)*) E A ((y)
(21)
Problem M2(y) now corresponds to a bilevel problem with K inner problems a E S(y*) that independent of one another. As the inner problems are independent of another, M2(y) can
15

---

Published as a conference paper at ICLR 2025
actually be written single bilevel problem with single inner-problen that decomposes into K independent problems. This can be seen by the fact that solving the individual dual problems a E S()") for all e [K] is equivalent to solving the following single optimization problem:
min NN)
Mifafafau
s.t. 0 of S C vi E AcE [K] (22)
Let's denote the set of optimal solution to Eq. rewrite My) as follows:
22
similarly as S ((y',..., yK)). Then, we can
Ms(8):
min
PE p
(23)
P.p P. S....
8.t. p"
max Pr
(24)
DE (E(A()(A)
m
Pe = Σ KatQu Ae [K]
(25)
(a
a K E ((''....,."" y.).
(26)
E ((y"....,
(27)
Now, we want to formulate the bilevel problem My as a MILP. For this, we have address how to linearly model Eqs.
24
26 and 27 in the following.
Inner Problem. To linearly model Eq. (6).. recognize that it still a convex optimization problem fulfilling Slater's 's condition by the same argumentation as provided in App. Thus, we can replace (a.,... xx) E ES ((y' ,............................... y k) with its KKT conditions and won't change the optimal solutions to the optimization problem. The KKT conditions (a+, (a''...., x S ((yt,...,, y*), )) turn out to the KKT conditions of the individually involved subproblems of E S()*) for e E [K] due to their independence from one another. Then, the exact same linear modeling strategy for the stationarity and complementary slackness constraints can be leveraged, as introduced in Sec. 3.1 Note that now get class-dependent dual variables of and uē as well as class- dessndeenndnnt binary variables sf and tς for each labeled node and class c. Thus, we have successfully linearized Eq. 26 and for all constraints written out, refer Thm. 3
Max. To model the max in Eq. 24 note that = -C lower and upper bound to Pa. respectively, valid for all [K]. Now, the maximum constraint Eq. (4 can be linearly modeled introducing a binary variable E (0, K with
EE 1= 1uu and p" = C CE 1uu define
be IA K (0) (](((((
Σ
2 Pes D' Pc (1 bx) D4), be E (0,1) (28)
Adversary. Lastly, we have to linearly model the adversary in Eq. For this, we represent the original labels in a new vector y' e {0, 11Tm with Jf" 1f of and 0 otherwise for all classes E [K] and labeled nodes E [m]. Similarly, we introduce binary variables y E {0. 1) m with v/ = 1 of = and 0 otherwise. Our goal to use ý'c to define ÿ and at the same time model
for all i E [m] and e E [K]. As node i can only be in one class, T/c can only be for one c and has to be 0 for all other classes. This can be ensured by the constraint Σx T/ = 1. Lastly, the adversaries' strength can be modeled using
the adversaries' strength. Setting ÿ can be achieved by the linear constraint jf 2
K
Σ
(1
Σ
yf
<
|em]
(29)
c=l
16

---

Published as a conference paper at ICLR 2025
Thus, have successfully shown how to linearly model Eqs. the following theorem:
24
226 and (27) and can state
Theorem 3 (Multiclass MILP) Given the adversary A, positive constants Mú, and Mo, set as
in App. Sooor all i E [m]] A c [K], and p², p" R with p' = -iE== 'Qul and p Lin Qual the prediction for node t is certifiably robust if the optimal solution to the MILP
C E
M (y), given below, is greater than zero and non-robust otherwise.
M(y):
min R.a.t.R.z...aa 8
Pe P" s.t.
S'..."k
3....
K
K Σ c=1
Σ
S [em].
1,
Σ
b =
1=1
c=1
AA [K] \ {c] pp" 2 Pe, p' S Pe + (1 - bp - -p²). be E {0,
4CE [K] : Pe = 21s
Aa [y] Aije [m] Σ Ri Qij - of
< R +2 - C(1 + +
C(1- - -
E [K] AiE [m]
- of S of s of - - -1) 5 CC <
of
u, S s a +f), 4/ M af Ctg
of E [0, (0,1).
1/20, of 20
3f = 20 - 1. / E (0.1)
Computation Complexity. The MILP has 3Km + K binary variables.
A.2 INEXACT CERTIFICATE
Thm. can be extended to incomplete multi-class certificate by strategy similarly proposed in Gosch et al. (2024). Assume that e is the original prediction of our model without poisoning. Now, solve optimization problem very similar to P(y) from Thm. 1 for each learning problem defined by e E [K]. but change the objective min sign(())) Ei 2, 2,Qre either to min > 2Qu c = c* or max Σm QQu if + c". Then, the original prediction is certifiably robust, if the solution to the minimization problem is still larger than the maximum solution to any maximization problem.
Tightness. On first sight, one might expect that such strategy trades of tightness significantly with scalability. However, we surprisingly find on Citeseer that the inexact certificate provides mostly the same certified accuracy, or a certified accuracy only very marginally below the exact certificate as shown in Tab, 2 We hypothesise that this is due to the fact that the most effective label perturbation may be one that flips the training labels of the predicted class to the runner-up (second highest logit score) class until the budget is exhausted. While the relaxation allows for independent changes to each of the K classifiers until the budget is used up. following the above argumentation, being able to make these independent changes to the other classes (not the highest predicted or hecond-highest) may not make the adversary significantly stronger.
Scalability. The exact multi-class certificate introduces K times as many binary variables as the binary certificate. The inexact certificate manages to reduce the multi-class certification problem to a binary one and thereby significantly improve scalability. Exemplary, for Cora-ML, the multi-class certificate is not computable in reasonable runtimes due to the larger C' values of the different GNNs. However, running the incomplete certificate makes the problem running in reasonable time with an average certification runtime of around 20 minutes per node (using two CPUs) with some rare cases taking up to 6h. The results for Cora-ML can be found in App.
17

---

Published as a conference paper at ICLR 2025
Table 2: Certified accuracy in [%]] for Citeseer of the exact vs incomplete multiclass certificate.
E {0, 0.01, 0.02, 0.03, 0.05) refers the attack budget (fraction of flipped labels in the training set.)
(Clean Acc.)
0.01
0.02
0.03
0.05
GCN
Exact
66 = 3.3
10.7 0..7225
0=0
0
0 0 0
Incomplete
66 3.3
1.5
0=0
0
0
SGC
Exact
65.3 + 4.1
5
9.2
0.7
0
Incomplete
65.3
3.77
8.7
0.7
0
GCN Skip-a
Exact
5.2
2.
2116
0
0
Incomplete
5.2
2.
2
0
0
GCN Skip-PC
Exact
6..7
2.7
0.7
0
0
Incomplete
66.7 1.9
20.3
0.7
0
0 0
B SLATER CONDITION
It is generally known that the SVM dual problem is convex quadratic program. We now show that the SVM dual problem (y) in a E S(y) fulfills (strong) Slater's 's condition, which a constraint qualification for convex optimization problems, for any choice of y A(y). This allows to reformulate the bilevel problem in Sec. [.1 be reformulated into single-level problem with the same globally optimal solutions (Dempe & Dutta 2012). Our argumentation is similar to (Gosch
et al. 2024) and adapted to the label-flipping case.
First, we define Slater's condition for the SVM problem:
Def. (Slater's condition) A convex optimization problem P Py( fulfills strong Slater's Constraint Qualification, there exists point in the feasible set of Pi (5) such that construint in Pi (i()) is active, iee. 0i < Cor all E [m].
Proposition 1 P)()) fulfills Slater's condition for any choice y E A(y).
Proof. It is easy to see that for a given fixed y, Slater's condition holds: choose = C/2 for all [m], this is feasible (but optimal) solution with no active constraints. That Slater's condition for P1 (ÿ) holds for any ý E A(y) can again be seen by noting, that the feasible solution defined by setting a; C/2 for all E [m] is independent solution without active constraints for any choice of y.
given y and and stays a feasible
C BIG-M
Proposition 1 Replacing the complementary slackness constraints Eq. (6 in Ps(y) with the big-M M constraints given in Eq. (10) does not cut away solution values of Ps(y), foror all E [m], the big-M values are set following Eqs. (30 and (31)
Ma, Σ CIQul-1
(30)
M
CIQu++1
(31)
Furthermore, Eqs.
30 and
(31 define the lightest possible big-M values.
Proof. The proof strategy follows[Gosch Gosch et al. (2024) and is adapted to the label flipping case. First,
lower and upper bound the term Σラ= R.jQu Qij for any [m] in the stationarity constraints.
As Raj ūiz, and -C S zj < C and ūs E (-1,1), follows that LB - Σm CIQ S
ET Rí, Qu < ΣТ OlQ U. It is easy to see, that the bounds are tight.
Now, the dual variable u; and v; are coupled with the other variables in the overall MILP only through the stationarity constraints Σ/ RejQis Qij uy for all E [m] and do not feature
18

---

Published as a conference paper at ICLR 2025
in the objective of Ps(rry). Thus, only have to ensure that any upper bound on u, Us cannot affect any optimal choice for the other optimization variables. This is achieved no feasible choice of Rij is cut from the solution space, which in turn is guaranteed, if any bound u, Us still allow the term _m مØ=1 QijQis in the stationarity constraint, to take any value between LB and B.
Using these bounds, we get
UB - + LB 4 S1
(32)
(33)
For the first inequality, assume UB > 1, then by setting eq 0 and u4 S UB fullfils all constraints and does not cut away any solution value. Similarly, if UB < 1, set un = and o S 1 - UB. For the second incquality, for LB > set set u, 0 and v2 & 1--12 LB. By only enforcing the so mentioned least constraining bounds for uN and 0;, exactly arrive at Eqs. (30) and 31 where tightness follows from the tighness of the bounds.
0 and u, S LB 1 and for LB <
D COLLECTIVE CERTIFICATE
We present the full version of the collective certificate Thm. 2 here.
Theorem (MILP Formulation) Given the adversary A. positive constants Mu; and My, set as
in App. foor all E [m], and and h e R with 1, -C E Qu and h2 C Di=1 Qu. the maximum number of test nodes that are certifubly non-robust is given by the MILP Cly).
C(y): max a.y M. u.V.A. R.C. ET
Σe Ct
8.1.
Pt = Σ
2,Qti
Σ 1=1
- --ūi - 2 2mm,] Vi [m] ū. = 23/ 1,
1=1
VIET: c {0,
Vg. > 0: P: < h1 -c), Pt > 4,
Vp. <::: 4(1 42), pt h4cr,
Vi.j E [m]
Qis - 14 + = =0, 4 0, 8 0, y {0, 1}.
C(1 + 5i) S Ríj + 2 S C(1 + 01), -C(1 - m/) s RS - S C(1 - -g),,
a, S 4 a a, - -CC(1 - 91) S S C(1 (.) a;
44 S Mn,81, 81, a; S C(1 si). 0 S My a, 2 Ct. 8, e (0, 1}, to E (0,1).
E FINITE-WIDTH MODEL-SPECIFIC GUARANTEES
We derive model-specific guarantees for finite-width setting that includes the depth, width, and ac- tivation functions used. To obtain this, we follow the derivation in Liu et al. (2020); Chen et al. (202T) and consider normalized input node features, bounded spectral norm of the graph convolu- tion. Lipschitz and smooth activation function. Concretely, we consider graph neural network with depth L, width w and activation function with Lipschitz constant p. and trained using 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 Wi.., i.e. (W) W Wineell < R). Then, the output difference between an infinite-wide network and a finite-width network determined by the deviation of the finite-width NTK at time from the NTK at initialization, similar to standard neural networks (Chen et al. 2021 Section F.1). Now, this NTK deviation determined by the Hessian spectral norm of the network shown in Liu et al. (2020). Thus, we bound the Hessian spectral norm by bounding the parameters, each layer outputs, their gradients and second-orde gradients. Since consider the node features X are normalized and the spectral norm of graph convolution S
19

---

Published as a conference paper at ICLR 2025
bounded we get the Hessian spectral norm be bounded as O [ Inm
Consequently, using this, we get the bound for the output difference between an infinite-width network and a finite-width
network as O 1t22 12 pln with probability p
eep((- This is the same the bounds in Liu et al. (020). Note that 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. Thus, it an interesting open question derive the explicit constants involved in the bounds.
F COMPARISON TO QPCERT GOSCH ET AL. (2024)
WhileGossh et (024)) also reformulates the bilevel problem associated to data feature poisoning using the SVM equivalence, similar to our approach on a high level, the technical challenges and
resulting contributions are fundamentally different, as outlined below: (i) Difference adversary: different problem
Gosch et al.] (2024) addresses the feature poisoning setting, whereas we focus
of label poisonnig. (ii) Difference in the final outcome: While Gosch et al. (2024) derives an
incomplete sample-wist wise certificate, derive exact certificates for both sample- wise and collective cases. Note that collective certificates are as important as sample-wise certificates as substantially established in Sec. 4 (tii Technical differences: In Goseh et al. 2024), the single-level reformu- lation is a bilinear optimization (product of two continuous variables). As a product between two continuous variables can't be modeled exactly in linear way. Gosch et al. (2024) relax the original optimization problem resulting in the incompleteness of their certificate. In contrast, our single-level reformulation is a nonlinear optimization, involving products of a continuous variable with bi- nary variables (Eq. (9)). along with bilinear terms (Eqs. (4) and (6)). These distinctions make the techniques in Gosch al. (2024) not applicable our problem. However, the techniques we intro- duce in Sec. 33.1 us to model these new non-linearities linearly in an exact fashion, resulting in an exact certificate.
G EXPERIMENTAL DETAILS
Datasets. We consider multi-class Cora-ML and Citeseer. Using these, we create binary datasets, Cora-MLb and Citeseerb. addition we generate synthetic datasets using CSBM and CBA random graph models. In Tab. we provide the statistics for the datasets.
Dataset
# Nodes
# Edges
# Classes
Cora-ML
2,810
7,981
7
Cora-MLb
1,245
2,500
2
Citeseer
2,110
3,668
6
Citeseerb
1,239
1,849
2
Wiki-CSb
4,660
72,806
2
Polblogs
1,222
16,714
2
Corab
1,200
1,972
2
Chamelconb
294
1,182
2
CSBM
200
367+16
2
CBA
200
389+33
2
Table 3: Dataset statisties
G.1 GENERATING GRAPHS FROM RANDOM GRAPH MODELS
CSBM. A CSBM graph G with nodes is iteratively sampled as (a) Sample label yı Bernoulli(1/2 Vi [n]: (b) Sample feature vectors XsIy; (yu,,, (c) Sample adja-
cency Ag Bernoulli(p) if y, Yj, Aij Bernoulli(g) otherwise, and Ays Ay. Following prior work Gosch et al. (2023), we set p. g through the maximum likelihood to Cora (Sen et al.
Thhe spectral norm of is < for all practically used convolutions.
20

---

Published as a conference paper at ICLR 2025
2008
(p 3.17%, 0.74%), and μ clement-wise to Ko/2Vá with d (n)] 1, and K = 1.5, resulting in an interesting classification scheme where both graph structure and features necessary for good generalization.
CBA. Similar to CSBM, we sample nodes in a graph & using CBA following Gosch ct al. 2023
The iterative process for each node [n]] follows: (a) Sample label yi Bernoulli(1 2): (b)
Sample feature vectors X; 1) ~ (yi Ia); (c) Choose m neighbors based on a multinomial distribution, where the fixed parameter m is the degree of each added node. The probability of
choosing neighbour j is Pj = (1+dkg,) )mng the fixed affinity between nodes i and based on their class labels. When a neighbor node j gets sampled more than once, set Aij 1.
Joei where deg, is the degree of node j and wij is
G.2 HYPERPARAMETERS
We set the hyperparameters based on 4-fold cross- pross-validation, and regarding the regularization pa- rameter C, we choose the smallest one within the standard deviation of the best validation accuracy for simulated datasets and the best one based the validation accuracy for all real datasets.
For CSBM, we choose to Srow for GCN, SGC, GCN Skip-a and GCN Skip-PC, S Sym for APPNP with its a 0.1. GIN and GraphSAGE
with fixed S. In the case of L = the regularization parameter C is 0.001 for all GNNs except APPNP where C = 0.5. For = 2, C 0.001 for all, except GCN with C 0.25 and GCN Skip-a with C 0.25. For L 4, again C 0.001 for all, except GCN with C' = 0.25 and GCN Skip-a with C' = 0.5.
For CBA, the best S is Say for GCN, SGC, GCN Skip-o, GCN Skip-PC, and APPNP with its = 0.3. GIN and GraphSAGE are with fixed S. In the case of L = 1. the regularization parameter is 0.001 for all GNNs. For L 2, C 0.001 for all, except GCN with C 0.25 and GCN Skip-a with C = 0.25. For L = 4, again C = 0.001 for all, except GCN with C = 0.5 and GCN Skip-a with C 0.25.
We outline the hyperparameters for real world datasets. All hyperparameter choices for all architec- ture and experiments can be found in the experiment files in the linked code.
C-values
Cora-MLb
Citeseerb
Cora-ML
Citeseer
GCN (Row Norm.)
0.075
0.75
0.004
0.0001
GCN (Sym. Norm.)
0.075
0.1
SGC (Row Norm.)
0.075
2.5
0.004
0.0001
SGC (Sym Norm.)
0.05
APPNP (Sym. Norm.)
0.5, a = 0
0.5, a = 0.2
MLP GCN Skip-a (Row Norm.)
0.025
0.025
0.1, & = 0.1
0,25, & = 0.3
0.004,a = 0.2
0.0001, a = 0.5
GCN SkipPC (Row Norm.)
0.075
0.075
0.003
0.0001
GIN GraphSAGE
0.025
0.005
0.0075
0.025
Table 4: Best Hyperparameters Real World.
C-values
Wiki-CSb
Polblogs
Corab
Chamelconb
GCN (Row Norm.)
1
10
0.25
10
SGC (Row Norm.)
0.5
10
0.1
0.5
APPNP (Sym. Norm.)
==
0.25, a = 0.2
0.75, a = 0.3
MLP GCN Skip-a: (Row Norm.)
0.75
0.001
0.25
0.1
0.1 1
10, a 0.1
0.5,x 0.1
GCN SkipPC (Row Norm.)
2.5
0.25
GIN GraphSAGE
0.175
0.075 0.75
0.025
0.01
0.01
0.75
Table 5: Best Hyperparameters Real World.
21

---

Published as a conference paper at ICLR 2025
For Cora-MLb, further, the following architectures used with row normalization:
GCN 1.=2: C=0.05
GCN L=4: C=0.1
GCN Skip-PC L=2: C=0.05
GCN Skip-PC L=4: C=0.01
GCN Skip-a L=2: C=0.075, a 0.1
GCN Skip-a L=4: C=0.1, a = 0.2
GCN 0.25A: C=0.05
GCN 0.5.A: C=0.075
GCN 0.75A: C=0.075
We choose the best C given by 4-fold CVV, except for Cora-ML, where we choose the smallest C in the standard deviation of the best validation parameters CV,
G.3 HARDWARF
We used Gurobi to solve the MILP problems and all our experiments are CPU internal cluster. The memory requirement to compute sample-wise and collective certificates depends on the length MILP solving process. The sample-wise certificate for Cora-MLb and Citeseerb requires less than GB of RAM and has runtime of few seconds to minutes. For the multi-class case, the exact certificate took up GB RAM and had runtime between minute 30 minutes. The collective certificate for Cora-MLb required between 1 to 25 GB of RAM with an average requirement of 2.8 GB. The solution time took between a few seconds, and for some rare instances up 3 days, the average runtime was 4, 2h. The runtime and memory requirements for collective certification on Citeseerb were similar Cora-MLb.
H ADDITIONAL RESULTS
H.1 SAMPLE-WISE CERTIFICATE FOR CBA AND POLBLOGS
1.0
GCN
GCN
Certified Accuracy
SGC
Certified Accuracy
APPNP
0.8
GCN Skip-o
GIN
GCN Skip-PC
0.6
GraphSAGE GCN Skip-a
0.6
GIN
CraphSAGE
0.4
Skip=PC
0.4
MLP
MLP
0.2
0.0
0.05
0.1
0.15
0.2
0.25
0.3
0.05
0.1
0.15
0.2
Perturbation budget
Perturbation budget
(a) CBA
(b) Polblogs
Figure 6: Certified accuracy computed with our sample-wise certificates for CBA and Polblogs datasets.
Fig. shows the certified accuracy computed with our sample-wise certificates for all considered GNNs. See Fig. 2 for other datasets.
22

---

Published as a conference paper at ICLR 2025
H.2 COLLECTIVE CERTIFICATE
H.2.1 FULL CERTIFIED RATIO TABLES
Certified ratios for all architectures and all for Cora-MLb (Tab. 6 Citeseerb (Tab. WikiCSb (Tab. R). Polblogs (Tab. 9 Corab (Tab. [0). Chamelonb (Tab. TTP. and CSBM (Tab. We note that we do not report
the mean certified ratio is 0 for all architectures.
Table 6: Certified ratios in [%] calculated with our exact collective certificate on Cora-MLb for e E {0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.5). As baseline for comparison, the certified ratio of a GCN reported. Then, for the other models, we report their absolute change in certified ratio compared to GCN, i.e., their certified ratio minus the mean certified ratio of a GCN. The most robust model for choice of is highlighted in bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
86.4 + 6.1
55.6 + 10.7
46.8 + 6.0
43.6 2.3
43.6 + 2.3
41.6 + 2.0
8.4 + 3.9
GCN
96.4=26
55.6 10.7
46.8 60
43.6 23
43.6
41.6 2u
8.4
SGC
+2.4 5.2
+7.6 19.2
+2.8 16.1
+2,4 144
+1.6 138
+0.4 128
+0.0 1:34
APPNP
+3.2 #7.9
+6.8 122
-1.2
-0.8 + 1.5
-1.6 1.6+11
-2.8 227
-8.0 08
GIN
-488 4.1
+6.0 #:55
-2.0
-5.6 5.2
-6.8 5:57
-8.0 #:64
+4.8 3:00
GraphSAGE
-6.0
+5.2
+1.611.11
+1.6 +1.6141 141
-1.2 1:39
-..0 139
+3.6 1:28
GCN Skip-a
-1.2
+1.6
+0.8
+0.8
+0.0
-044
+0.8 + 3.9
GCN Skip-PC
-2.0..00
+2.4
42.4
41.6130
-0.0 40.0
2.4
+2.0 4.1
MLP
-20.4
51
-6.8
-4.8
-6.0
-7.2
+8.8
Table 7: Certified ratios in [%] calculated with our exact collective certificate Citeseerb for e E (0.05, 0.1, 0.15, 0.25, 0.3, 0.5). As baseline for comparison, the certified ratio of a GCN reported. Then, for the other models, report their absolute change in certified ratio compared to a GCN, ie., their certified ratio minus the mean certified ratio of a GCN. The most robust model for choice of is highlighted in bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
65.6 + 12.5
50.0
7.1
35.6 s4
29.2 52
21.6 #
6.8
SGC
+3.6
+0.4 108
-0.4 10.
-0.8 100
-0.0
3.64 7.0
+2.8
APPNP
4.
+0.8 2.59
4.14
+81
+1.6
+4.8
+2.0
GIN
+6.8
+0.8
+1.2
+6.0
+9.6
+11.6
+4.0
GraphSAGE
19.6
15.
+2.4
+4.4
+7.6
+8.8 166
+4.8
GCN Skip-a
+10.0
+3.2 1.0
+2.0
1.4
+5.2
+6.0.66
+3.6.13
GCN Skip-PC
+15.6
+9.2
+3.6
4.4
+4,0
+7.6
1.6.1
MLP
-0.4
-6.8
-0.4
43.2
+6.8
+11.2
+11.6
Table 8: Certified ratios in [%] calculated with our exact collective certificate on WikiCSb for e E (0.05, 0.1, 0.15,,111000 0.2, 0.25, 0.3, 0.5). As baseline for comparison, the certified ratio of a GCN is reported. Then, for the other models, we report their absolute change in certified ratio compared to GCN, i... their certified ratio minus the mean certified ratio of a GCN. The most robust model for choice of is highlighted in bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
80.0 1.
71.6
54.4 1.54
42,0
36.4 1.99
31.6
4.0
SGC
+9.2
+2.4
-6.0 111
-0.4 1.11
+2.4 166
+0.0 13.3
-2.8
APPNP
+7.2 6.3
-20.0
.9.2
+0.0
-6.8
-22.8 1.2
-4.0 1.00000
GCN Skip-a
-0.0 =31
-3.6
+0.0 =91
-1.2
-0.8
-1.2
GCN Skip-PC
+2.4
+2.0
+1.2 139
+4.0
+2.0
+0.8
MLP
-5.6
-12.0 11.6
-5.2
-3.2
-5.6
137
23

---

Published as conference paper at ICLR 2025
Table 9: Certified ratios in [%]] calculated with our exact collective certificate on Polblogs for {0.05, 0.1, 0.15, 0.2, 0.250 0.3, 0.5]. As baseline for comparison, the certified ratio of GCN is reported. Then, for the other models, we report their absolute change in certified ratio compared to a GCN, i.e, their certified ratio minus the mean certified ratio of GCN, The most robust model for choice of is highlighted in bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
73.2 + 14.1
42.4 19
42.0 + 36
42.0 36
42.0 + 166
42.0 =30
4,4 29
SGC
+22.4 1:20
+47.2 13.
+26.4 1129
+3.2 245
+0,4 15.3
-0.4 4.5
-2.8 1.5
GCN SkipPC
+10.8 5.5
+15.2 + ma
+2.0 =20=228
+1.2
-0.4 20
-0.8 = 166
+5.2
GCN Skip-a
-1.2
+0.0 #48
+0.4 =48
+0.0
+0.0
+0.0 =42
+1.2
GIN
+40
+13.2 +
+0.8 =37
-2.8
-3.6
99.6
+4.6
GraphSAGE
42.4
+10.4 6.3
+0.8 =2
-1.6
-3.6 56
-5.2 +
+6.0 11.5
MLP
-73.2
42.4 000
-42.0 000
-42.0 #.000
42.0 + uo
-42.0 +:000
-4.4 +: 0.0
Table 10: Certified ratios in [%] calculated with our exact collective certificate on Corab for
{0.05, 0.1, 0.15, 0.2, 0.25, 0.3,0.5), 0.5). As baseline for comparison, the certified ratio of GCN is reported. Then, for the other models, we report their absolute change in certified ratio compared to GCN, i.e., their certified ratio minus the mean certified ratio of GCN. The most robust model for a choice e highlighted in bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
77.6 =
50.4 + 135
33.6 + 3.
29.6 + 4.6
28.8 + 4.7
25.2 =
11.2 2.7
SGC
+6.0 22.3
+0.8 11.1
+2.8
+2,4 14.6
+1.2 15.5
+2.0 =:5.0
-0.4 3:32
APPNP
-1.6
-5.2 1:66
-2.8 5.7
1..6
-2.4 1.
-1.6
-2.4 3:55
GIN
1.6
-2.4 121
+2.0
-0.8
12
2.555
-0.4
GraphSAGE
+0.0 :46
433
+
+0.8
+6.4
+1.2
+1.6 13.0
GCN Skip-a
-0.4
-90
+3.6
+1.2
-5.6
-1.2
-0.4
GCN Skip-PC
-3.6
+1.2 47.3
+2.0
+1.6
-1.2 454
-2.0 453
-0.8 15
MLP
-15.6 236
-9.2 #31
+1.2
+: 10.9
+2.4 9.0
-2.4
400
-2.8
4.6
+0.4 4 3.4
Table 11: Certified ratios in [%] calculated with exact collective certificate Chameleonb for
E {0.05, 0.1, 0.15, 0.2, 0.25, 0.5. As baseline for comparison, the certified ratio of a GCN reported. Then, for the other models, report their absolute change in certified ratio compared to GCN, i.., their certified ratio minus the mean certified ratio of GCN. The most robust model for a choice of is highlighted bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
69.6
52.4
41.6
33.2
26.8
22.8
9.6
SGC
-0.0 1 62
+2.8 1600
+4.4 158
+5.2 146
+5.6 139
+4.8 146
+1.2 116
APPNP
-2,8 1: 146
-3.2 922
-8.0 1.7
-7.6 1.64
16
-800 1:53
4.00 133
GIN
-26.8 8.6
-28.4 10.0
-23.2 1:99
-18.8 4.9
-16.4 1:711
-13.6 66.66666
-5.2 4:32
GraphSAGE
-5.2 4.5
-8.4 12.6
16.4
-2.4 à: 11.
4142
-0.4 11.
+0.0 #:00
MIP
-29.6 22.1 22.1
-38.8 4.5
-29.2 4.6
-21.2
-16.0
+12.4441
-6.0 4 23
Table 12: Certified ratios [%] calculated with our exact collective certificate on CSBM for
{0.05, 0.1, 0.15,, 0.2, 0.25, 0.3, 0.5, 1}. As baseline for comparison, the certified ratio of a GCN is reported. Then, for the other models, we report their absolute change in certified ratio compared to GCN, i.e., their certified ratio minus the mean certified ratio of GCN, The most robust model for a choice of e highlighted in bold.
0.05
0.10
0.15
0.20
0.25
0.30
0.50
GCN
85.7 6.5
67.0
1.0+99 9.7
48.0 2 6.0
44.7 + 4.3
40.8 + 5.2
34.7 = 7.0
2.9 = 1.7
SGC
+7.8+28.8
5.1.9
+34.3 8.3
+22.3 16.0
+9.2 20.8
-7.1 + 19.4
-1.7 1.77+000 0.8
APPNP
111474
-6.2 7.2
3.4
-0.3 2.4
+1.8 1.8
-0.3 6.7
+1.7 1.6
GIN
8.7
13.0
9.66+
9.44
-10.4
+2.3
GraphSAGE
4077
-2.3 8.0
4.4
-3.0 +: 2.1
+3.0
+3.4
+1.4
2.0
GCN Skip-a
-0.1 0.146
009+8.0
+2.1
-0.3 3.7
+0.6
2277
+0.8
2.2
GCN Skip-PC
+4.9 +4.9+3.0
+15.0 6.2
+.0.1
+7.6 12.0
-2.2
-5.4 13.1
-0.8
MI.P
-16.3
4.2
5.199
24

---

Published as a conference paper at ICLR 2025
H.2.2 COLLECTIVE ROBUSTNESS OF ALL ARCHITECTURES
[ shows the certified ratio as computed with our collective certificate for all investigated archi- tectures on different datasets.
Fig.
cere
1.0-
GUN Sttp
Ceriied Ratio
UJN Scp-PP
CCNN Siet-a
Cerriftd Ratio
sup ArPAR
GCN Ski-PU
GEN Skip-o
Oucifeed Ratio
APPN"
500
GCN Skip
64
Perturbation badget
Perturbation bacgett
Perterbation budget
(a) Cora-MLb
(b) Citeseerb
(c) Wiki-CSb
DCX
GapbeaGE
CortiBed itakko
104
CBV GribRaGE
MIP
Certifed Racio
Skipo
Certffeed Ratio
as
SGC
GIN
APPN?
0
35s
0.5 055 01
02
6:5 03
05
0.6
05 011
9:15
03 D2
0:35
Petturatiin budgett
Perturbation basggot
Porterbation burlett
(d) Polblogs
(e) Corab
(1) Chameleonb
OCN staC
1.8-
OCN
OrgGRAGE GLSN Skip-n
Certited Ratio
IN Sazoo
Certified Ratio
AP//N
GUN Saap-111
GTN
02
Perturbation budget
coturbstion budgett
(g) CSBM
(h) CBA
Figure 7: Certified ratio computed with our collective certificate for all investigated models.
H.2.3 ROBUSTNESS PLATEAUING PHENONMENON
The strength of plateauing appears to depend on both the dataset and the model architecture. The Polblogs dataset shows the strongest plateauing effect out of all datasets. This indicates, as Polblogs has no features, that in graph context, the effect is more strongly pronounced if the features carry less information compared to the structure. While for Polblogs for all architectures, for Cora-MLb for all architectures and for CSBM for many architectures, the emergence of robustness plateau for intermediate e is strikingly visible (see e.g., Fig- 7 the picture is more subtle for Citeseerb, Wiki- CSb and Chameleon. Focusing on Citeseerb, while for all architectures, the effect of increasing reduces for larger it is not immediately visible from Fig. 7blif this effect is particularly pronounced intermediate budgets or continuously goes on until show a continuous plateauing to 0 for = 1. However, if one compares the mean certified ratio difference from e 0.1 to e = 0.3 (Ameat) to one from e = 0.3 e 0.5 (Astrong), we can find architectures showing a stronger plateauing phenomenon for intermediate GIN Amed = 17.6% compared to Astrony = 22.4% and for MLP Amed = 10.4% compared to A ettong 14.4% (also see Tab. 7. This closer study suggests that both structural and statistical properties the data, as well as architectural design choices, jointly influence this behavior.
1. Indeed, some architectures seem to
Exemplary, for
H.2.4 ROBUSTNESS RANKINGS BASED ON COLLECTIVE CERTIFICATION
To compare robustness rankings for different perturbation budgets and datasets, Tab. 13 computes average ranks based on the average certified ratio computed by our collective certificate for 'weak' (e E (0.0.1). "intermediate" (e E (0.10.33) and 'strong' (e (0.3, 1)) perturbation strengths (we
25

---

Published as a conference paper at ICLR 2025
exclude 1, all models have certified ratio of 0). Tab. 13 shows that robustness rankings are highly data dependent as already seen in the sample-wise case, and also highly depend on the strength of the adversary.
Table 13: Average rank based the average certified ratio computed using exact collective certificate for 'weak' (c E (0, 0.1]). 'intermediate' (c E 0.3)) and 'strong' (c E (0.3, 1)) perturbation strengths and different datasets. The most robust model highlighted in bold and the least robust in red. Total refers to E (0, 1).
Cora-MLb
Citeseerb
CSBM
(0.0g 0.1
(0.1,033
(0.3,
total
[0,0.3]
0.3]
(0.3,
total
(0.0.1)
(0.1,03)
(0.3, 1]
total
GCN
5.0
3.5
6.0
4.29
7.0
6.75
8.0
7.0
3.0
3.5
6.0
3.71
SGC
1.5
1.0
6.0
1.86
6.0
7.5
5.0
6.71
1,0
2.5
8.0
2,86
APPNP
5.75
6.5
3.75
GIN
4.5
7.75
2.0
6.0
4,0
1,75
3.0
2.57
6.5
6.75
2.0
6.0
GraphSAGE
5.0
GCN Skip-o
4.5
3.25
5.0
3,86
2.5
4.0
4,0
3.57
4.0
3.5
5.0
3.86
GCN Skip-PC
4.5
3.0
4.0
3.75
1.0
3.0
7.0
3.0
2,0
3.75
7.0
3.71
MLP
8.0
7.25
1.0
6.57
8.0
3.75
1.0
4.57
8.0
6.14
H.2.5 EFFECT OF DEPTII
We analyze the influence of depth in detail in this section and present (i) across depths and datasets, skip-connections, GCN Skip-PC: and GCN Skip-o, results in certifiable robustness that is consis- tently better or good the GCN. Fig. demonstrates it for Cora-MLb, CSBM and CBA for = = 2, 4). (ii) depth, in general, decreases the certifiable robustness as observed Fig. 9 In some cases, it is good L 1 and only in Cora-MLb for GCN, L 4 is better for small perturbations while is still worse than 1.
1.3
1.0
Cerlided Ronio
OCX OUK Sip
Cartiled Rasão
GCX
Certitee Rasio
OEN GEN Sip
GEN Siip
84
0.4
0.2
0.2
02
0131 Pertarbation bucgot
01
Paturlation burlges
Pettrbetion budget e
(a) CSBM L
(b) CSBM L =
(c) CSBM =4
GES GEN Sidp
Certibed Ratic
LEE 2ipp SuP
Cartiiad [talic
G.S. Nopoo GLN Scper
0.5
Cattiled
Pertarbation burlge
Pertarbation
Perturbetion hudgee
(d) CBA ==1
(c) CBA L =
CBA L
1.5
CCN
CCN
OCN Skipsn
Cectilied Ratio
Contafted Ratlo
SkG-PC
10.
02
02
035
05 035 Perturbation bunlge
315 61
035
61
c15 05 635 13
05
015 61 615 d2 035 63 05
Pertarbation budgged
Pertabbttonn hudlges
(g) Cora-MLb 1=
(h) Cora-MLb L
(i) Cora-MLb L ==4
Figure 8: Effect skip-connections showing GCN Skip-PC and GCN Skip-a results in certifiable robustness that is consistently better than GCN across Cora-MLb, CSBM and CBA and depths = (1,2,4).
26

---

Published as a conference paper at ICLR 2025
Oetiied Raiio
Cuttifed Ralio
CES P CUN Pi
Cortifed Railo
SGC
60
035 15 Pertarlation
011 015
62 Perturbation budget
Portarbation budgges
Cora-MIbb
(b) Cora-MLb
CSBM
Ceralied Ratio
Ceralfeed Ratio
Corvatted Dtalio
60
00
06
315 0655 b1
02
n35 DJ 05
0.55 DE
035
02
035
23
65
0155
03
6.15
02 0.35 DJ 05
Perturbation budget
Pertarbation buigee
Pertarbation budget c
(d) CSBM
(e) CSBM
(I) CSBM
Figure 9: Effect depth for GCN, SGC, and GCN with skip-connections showing the depth in general affects certifiable robustness negatively.
H.2.6 EFFECT OF GRAPH CONNECTIVITY
Fig. TO shows the increased connection density and homophily in the graphs increases certifiable robustness across GNNs such as GCN and SGC, using CSBM and CBA. Sample-wise certificates for all considered GNNs showing the same observation is demonstrated in Fig. 11 It is interesing to also note that the hierarchy of GNNs remains consistent across the settings.
GINES
13 an Potulalki belgit
to
10 so 02 budgt
Irdget
(a) CSBM: Density, SGC (b) CSBM: Homophily, (c) CBA: Density, GCN
(d) CBA: Density, SGC
SGC
Figure 10: Effect of graph structure showing increased connection density and homophily in the graphs increases certifiable robustness.
Cerated SAGE
Orgh
Orotad Duulo
dhd Baie
0
Paruriati tolot
Iniipt
(a) Density 2x
(b) Density 0.5x
(c) Homophily 2p, q
(d) Homophily 0.5p,
Figure 11: Sample-wise certificates for CSBM on the effect of graph structure showing increased connection density and homophily in the graphs increases certifiable robustness evaluated CSBM.
H.2.7 EFFECT OF GRAPH SIZE
In this section, we show that the results are consistent when the number labeled nodes are in- creased to 20 nodes per class using CSBM. Fig. 12 shows the sample-wise and collective certificates showing similar behavior as the ones computed using n = 10. is interesting to note that the hierar- chy of GNNs observed in sample-wise certificate for n 20 is the same 10. The plateauing
27

---

Published as a conference paper at ICLR 2025
phenomenon is also observed. Fig. 16 shows representative results showing the depth analysis and graph structure analysis also results in the same finding.
GON
GCN
GraphSaGE GCN Skip Skip-
Cortified Avcaruey
SGC APPNP
SGC
Certified Ratio
0.8
GIN
MI.
GraphSAGE GCN Skip-a
0.6
Skip-PC
MLP
0.2
0.2
0.3
0.25 03 Perturbation budgel
Perturbation budget
(a) CSBM: sample-wise
(b) CSBM: collective
Figure 12: The results consistent when 20 per class is considered for CSBM. Figure showing sample-wise and collective certificates
Cortifeed Racio
GEN ICN OCN
Certiöe Pacilo
0.5
GOX 83x GCN 8x
GCN
CertuSed
3.
0.
22
022
60
06
0.3 635 01
B35 02 7:55 03. 05
010 015
01 0.5 05 0.55 03 05
20 0.55 33 85 010 010 01
01 Perterbation budger
Perturbation budged
Perturbation bungget c
(a) CSBM: GCN
(b) CSBM: SGC
(c) CSBM: Sparsity, GCN
Figure 13: Consistency of results for a larger number of labeled nodes shown using CSBM.
H.3 GENERALITY OF CERTIFICATES TO OTHER MODELS
In addition to MLP (a non-graph neural network architecture), we demonstrate the applicability of our certificates other non-GNN based models such as linear kernel XX"", where the feature matrix. The collective certificate results for Cora-MLb and the random graph models CSBM and CBA provided in Fig. 14 Our experiments demonstrate that the certificates are directly applicable to kernels and standard networks, such as fully connected and convolutional networks. Since our primary focus is on the graph node classification problem, convolutional networks were not included in this study, but their inclusion would follow the same methodology.
CeN
DCN MIL
CCN Ski-FF KI
1.0
GEN
GON Shp-
6.8
SUC
APPNP
EXT
Cortiãed Ratio
0.2
APPNE
XN*
Catteed Rabio
5021
APPNP
X.Y"
88
Re
Coniiied
6.4
Perturlattion
burgeel
Pesturbstion burigel
Perterbetion budget
(a) Cora-MLb
(b) CSBM
(c) CBA
Figure 14: Generality of certificates to other models demonstrated using linear kernel Cora-MLb, CSBM and CBA.
28

---

Published as a conference paper at ICLR 2025
H.4 CERTIFICATES FOR DYNAMIC GRAPHS
Our certification framework is easily adaptable to dynamic graph settings depending on the learning strategy. To demonstrate it, consider inductive setting where the training graph grows during inference. In Fig. [5] we provide the collective certificate results for Cora-MLb by inductively adding the test nodes the training graph. Results are comparable the static graph analysis.
10-
GUN
Grapt
GCN Skip-o
Certiffed Ratio
a. 0.6
APEAP
GCN Skip PS
GIN
MLP
80
0.55
0.1
02
0.5
05
05
Perturbation budget
Figure 15: Certified accuracy computed with our sample-wise certificates for CBA dataset.
Furthermore, other learning methods such as aggregating temporal structural and/or feature informa- tion through summing over the temporal information (Kazemi et al., (2020) is also possible without any modification to the certificate and adapting only the adjacency and/or feature matrices in NTK computation. While we demonstrate adaptability certain dynamic graph learning settings, we ac- knowledge that extending the framework to handle highly dynamic scenarios with frequent structural changes remains a promising area for future research. Incorporating temporal NTK computation or online certification methods could further enhance its applicability.
I MULTI-CLASS EXPERIMENTAL. RESULTS
We run exact sample-wise multi-class certificate for Citeseer for selected architectures (Fig. 16a and the inexact sample-wist wise variant for Cora-ML (Fig.I6b). In App. A.2 we show that our relaxed certificate provides the same nearly as good certified accuracy as the exact certificate, while being much more scalable. Thus, for more details on the incomplete multi-class certificate including a detailed tightness discussion, refer App. A.2
16b).
Cortified Accuracy
T- GCN
Cortified Accuracy
GCN
0.6
GCN Skip-n
GCN Skip-a
GCN Skip-PC
GON Skip-PC
0.2
0.2
0.01
0.02
0.08
0.08
0.02
0.03
0.05
0.1
Perturbation budget
Perturbation budget
(a) Citeseer
(b) Cora-ML
Figure 16: Sample-wise certificates for multi-class datasets.
29


Reviews:
[{"review_id": "ydTEogEQhn", "reviewer": "Reviewer_QNjQ", "summary": "This work investigates the exact robustness certification for GNN against label poisoning attack. They use the NTK to approximate the wide GNN, and reformulate the bilevel optimization problem into a MILP. The authors believe that their framework can be applied to other GNNs through its NTK. Finally, they conduct experiments to show their certification for various GNNs over several datasets.", "questions": "1. When considering the approximation error in this framework, is this method an exact certification method? (especially when the width of GNN is not sufficiently wide).\n2. How to evaluate the tightness of the certifies computed by this method?\n3. What is the total computational complexity of the proposed method?\n4. What is the novelty of the techniques in this work?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The robustness certification is a vital problem for GNN and other NNs. It is hard to obtain an exact robustness certification.\n2. The author proposes a novel framework for robustness certification against label poisoning, and their main idea is to approximate the model by its NTK. It seems to be easy to apply this framework to other models.\n3. The computational complexity of solving the MILP is not very large. The authors conduct experiments on several datasets and GNNs to show its empirical performance.", "weaknesses": "1. My main concern is about the approximation error when using NTK to approximate GNN. The approximation error exists unless the model is infinitely wide, especially when we use a pooling layer. However, the authors aim to obtain exact certificates, but the approximation error is not considered in this work.\n2. A limitation of this framework is that it requires the width of the model to be sufficiently large, and it cannot be used for narrow NNs. \n3. An important recent work is [a], which studies the robustness certification of GNN against data poisoning. I find that the techniques and framework in this work are very similar to [a], which limits the contribution of this work.\n4. The authors only show the computational complexity of solving the MILP. However, since it approximates GNN by its NTK, it is necessary to show the computational complexity of computing the NTK of GNN.\n\n[a] Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, Stephan Günnemann. Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks. Arxiv 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g97FlJHatU", "reviewer": "Reviewer_ktGU", "summary": "The paper \"Exact Certification of Graph Neural Networks Against Label Poisoning\" introduces the first exact certification method, for deriving complete sample-wise and collective robustness certificates for Graph Neural Networks, against adversarial label flipping. \nUsing the Neural Tangent Kernel (NTK), the authors leverage the dynamics of wide networks in order to recast the bilevel optimization problem of label flipping, as a Mixed-Integer Linear Program (MILP). In this work, the authors establish hierarchies of GNNs on different benchmark graphs, and quantify the effect of architectural options to the worst-case robustness flipping.", "questions": "1. Scalability and Complexity: Given the computational complexity of your MILP-based certification, have you considered or tested any strategies to approximate or simplify the certification process for larger datasets? Would relaxing the exactness of the certification improve scalability while retaining useful guarantees?\n\n2. Dataset Dependence: Your results highlight that robustness hierarchies among GNN architectures vary across datasets. Can you elaborate on why certain architectures may perform better on specific datasets? What dataset characteristics influence these hierarchies?\n\n3. Intermediate Perturbation Plateau: You observed a plateau in robustness for intermediate perturbation budgets across several GNN architectures and datasets. Do the authors have any hypotheses about the causes of this phenomenon, and do you plan further analysis to understand it more deeply?\n\n4. Extension Beyond GNNs: While the method can theoretically be applied to other types of neural networks, have you tested it on non-GNN architectures? If so, how did the performance and scalability compare?\n\n5. Unaddressed Adaptability to Dynamic Graphs: Real-world graphs often change over time, yet the certification process assumes a static graph. Can your methodology adapt to provide certification for dynamic or evolving graphs?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.   The authors introduce a novel exact robustness certification method for label flipping attacks on neural networks, particularly Graph Neural Networks (GNNs). This work is impactful given that exact certification for poisoning attacks is generally unsolved for GNNs​.\n2. By leveraging the Neural Tangent Kernel (NTK), the paper rigorously reformulates the robustness certification problem as a Mixed-Integer Linear Program (MILP). The authors were able to extend previous work [1], deriving complete certificates, and collective certification.\n3. The approach offers wide applicability, as it can extend beyond GNNs to general neural networks, offering a framework that could potentially influence robustness research across various domains in machine learning​.\n4. The authors identified a novel phenomenon of robustness plateauing for intermediate perturbations.\n\n\n[1]. Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, and Stephan G¨unnemann. Provable robustness of (graph) neural networks against data poisoning and backdoor attacks. arXiv preprint arXiv:2407.10867, 2024.", "weaknesses": "1. The high complexity of Mixed-Integer Linear Program (MILP)  could introduce computational overhead, which may be prohibitive for real-time or large-scale applications. \n2. Additionally, the certification method is largely tested on synthetic datasets. Although effective on these datasets, it’s unclear how well it would generalize to real-world graphs.\n3. Finally, the paper focuses solely on exact certification. The authors are encouraged to consider trade-offs between exactness and scalability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VVtHqRLsPC", "reviewer": "Reviewer_9xfS", "summary": "The paper presents a novel approach to certify Graph Neural Networks (GNNs) against label poisoning attacks by introducing exact sample-wise and collective robustness certificates. The authors leverage the Neural Tangent Kernel (NTK) to capture training dynamics, reformulating the label-flipping problem as a Mixed-Integer Linear Program (MILP). This method allows for exact robustness certification across multiple GNN architectures in node classification tasks, establishing robustness hierarchies and investigating the effect of architecture-specific choices on resilience to label flipping. A key contribution is the discovery of a plateau effect in robustness for intermediate perturbation budgets, which has implications for understanding adversarial robustness in GNNs.", "questions": "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? If so, it would be good to highlight this, as it deviates from most work on certification which computes certificates wrt. the concrete parameter initialisation used for the particular model training.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "**The Problem Addressed is Highly Relevant**\n\nPoisoning attacks, of which label flipping is one variant, are highly relevant in machine learning and pose a significant security risk. While empirical defenses can sometimes weaken this effect, it is prudent to develop methods that can guarantee their absence and accurately measure their influence. The paper thus addresses a key challenge to develop more secure and trustworthy models.\n\n**The Proposed Method is Sound Under The Infinite-Width Assumption**\n\nThe proposed method is sound under the infinite-width assumption. While this assumption does not hold in practice (see weaknesses), it gives a good theoretical basis for reasoning about model behavior. Computing exact (and not just sound but incomplete) certificates has several advantages, including a better comparison of different models’ robustness.\n\n**Extensive Evaluation**\n\nConsidering the method's limited scalability, the evaluation is thorough, spanning several models and datasets. I find the finding of plateaus especially intriguing, which has potential for additional investigations in the future.\n\n**Good Reproducibility**\n\nThe authors provide many implementation details in the paper and the appendix, and include their code for reproducibility.", "weaknesses": "**The “Exact” Certificates are Approximations**\n\nThe authors claim exact certificates (e.g., L68), which means the certificate has neither false positives nor false negatives. However, this only holds under the assumption of infinite-width models, and not for finite-width models used in practice. While I am not an expert in NTKs, my understanding is that there can be significant deviations in training behavior, especially for deeper models. I would therefore argue that the framing of the certificates should be adjusted to account for this, putting less emphasis on the certificates being “exact” for neural networks and highlighting more the fact that they are approximations. The authors acknowledge this in the conclusion; however, it should be reflected in the claims (e.g., section 1, abstract) as well.\n\n**Limited Scalability**\n\nThe second major limitation is the method’s inherent limited scalability to small-scale models and graphs. This is common to all certification methods, but especially prevalent in exact methods. I thus don’t see this as a reason against acceptance, but it does limit the method’s practical applicability and raises questions of whether the findings hold in larger-scale settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FQ490pAX7i", "reviewer": "Reviewer_5hi6", "summary": "This paper introduces exact certificates for graph neural networks against label poisoning. The author reformulate the certification problem into a Mixed Integer Linear Program (MILP) using  Neural Tangent Kernel (NTK), deriving both sample-wise and collective certificates for GNNs in node classification tasks. The method is tested on various GNNs and datasets.", "questions": "In addition to the concerns mentioned in the weaknesses, some figures are not very reader-friendly, such as Figures 2c 3c. Consider adjusting the colors and legends for better clarity.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow. It introduces first exact certificates for graph neural networks against label poisoning. \n- The evaluation presents insights that guide future designs and improvements in GNNs regarding label poisoning.", "weaknesses": "+ The NTK is data dependent, but the paper only evaluates two real-world datasets, Cora-ML and Citeseer. This raises concerns about the generalizability of the findings. It would strengthen the paper to evaluate on a broader variety of real-world datasets.\n+ Given that the core technique of NTK-based MILP formulation is already established [1], the contribution seems incremental.\n\nReferences:\n\n[1] Gosch, Lukas, et al. \"Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks.\" arXiv preprint arXiv:2407.10867 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)