Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks
Authors: Lukas Gosch
Mahalakshmi Sabanayagam
Debarghya Ghoshdastidar
Stephan Günnemann
Venue: Accepted by TMLR ()

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

Published in Transactions on Machine Learning Research (06/2025)
Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks
Lukas Gosch
Lgosch@tum.d
School of Computation, Information and Technology & Munách Data Science Institute Technical University of Munich; Munich Center for Machine Learning (MCML)
Mahalakshmi Sabanayagam'
m.ssbbansaaeggam@@amm..d
School of Compulation, Information and Technology
Technicol University of Munich
Debarghya Ghoshdastidar
d. d.ghoshdastiddrrBuum..d
School of Computation, Information and Technology & Munich Dota Science Institute Technical University of Munich;; Munich Center for Machine Learning (MCML)
Stephan Günnemann
w.guennemann@tum.cco
School of Computation, Information and Technology & Munich Data Science Institute Technical Universily of Munich; Munich Center for Machine Learning (MCML)
Reviewed on OpenReview: https: // openreview. net/ permm id= g IAPLDAGVE
Abstract
Generalization of machine learning models be severely compromised by data poisoning, where adversarial changes are applied to the training data. This vulnerability has led to interest in certifying (i.e., proving) that such changes up to certain magnitude do not affect test predictions. We, for the first time, certify Graph Neural Networks (GNNs) against poisoning attacks, including backdoors, targeting the node features of a given graph. Our certificates are white-box and based upon (i) the neural langent kernel, which characterizes the training dynamics of sufficiently wide networks; and (ii) novel reformulation of the bilevel optimization problem describing poisoning mixed-integer linear program. Consequently, we leverage our framework to provide fundamental insights into the role of graph structure and its connectivity on the worst-case robustness behavior of convolution-base based GNNs. We note that our framework is more general and constitutes the first approach to derive white-box poisoning certificates for NNs, which can be independent interest beyond graph-related tasks.
and PageRank-
1 Introduction
Numerous works showcase the vulnerability of modern machine learning models to data poisoning, where adversarial changes are made to the training data (Biggio et al. 2012 Muüoz-Gonzzle et al. 2017 Zügner & Günnemann 2019a Wan et al. 2023 as well as backdoor attacks affecting both training and test sets (Goldblun el al. 2023). The practicabiliuy of data poisoning attacks on modern web-scale datasets has been impressively showcased by Carlini et al. (2024) and a critical concern for practitioners and enterprises Grosse et al., 2023 Siva Kumar al.) 2020). Reliable detection of poisoning examples is an unsolved problem (Goldblum al. 2023) and empirical defenses against such threats continually at risk of being compromised by future attacks (Koh et al. 2022 Sueiu et al. 2018). This motivates the development of robustness certificates, which provide formal guarantees that the prediction for a given test data point remains unchanged under certain corruptions of the training data.
FEqual contribution.

---

Published in Transactions on Machine Learning Research (06/2025)
Table I: Representative selection of data poisoning and backdoor certificates. Poisoning refers to (purely) training-timi attacks. A backdoor attack refers to joint training and test-time perturbations. Certificates apply to different attack types: (i) Clean-label: modifies the features of the training data; (ii) Lippi-fippingg
modifies the labels of the training data; (iii) Joint: modifies both features and labels; (iv) General attack: allows (arbitrary) insertion/deletion, i.e,, dataset size doesn't need to be constant; (v) Node injection: particular to graphs, refers to adding nodes with arbitrary features and malicious edges into the graph. It is most related to (iv) but does not allow deletion and can't be compared with (i) and (ti). Note that certificates that only certify against (dit) - (u) cannot certify against clcan-label or label-flipping attacks individually.
Perturbation Model
Applics to Node Cls.
Deterministic
Certified Models
Approach
Pols. Backd.
Attack Type
Ma et al.
2019
Diff. Private Learners
X
Joint
Differential Privacy
Lan nb al
2121
Dift. Private Learners
X
General
Difierentaa Privary
Waing 65
X720
Smoothed Classifeer
X
V
Joint
Randomized Smoothing
Weber
2125
Black Box
Smoothed Chussifer
X
Clem--lbel
Randomised Smoothing
Zlauu es aL 2122
X
Smoothed Classiter
V
Joint
X
Randomized Smoothing
Lai el ml
10211b
Smoothed Chassfler
x
Node Injection
Randomized Smoothing
Jia
2021
Ensemble Classibie
x
General
X
Ensemble (Majority Vote)
Resenfeld et s._ 20/20
Smoothed Classifier
X
Label Flip.
X
Randomized Smoothing
Lavine & Feizi
1721
Ensemble Classifier
X
Tabel Fline/General
Ensemble (Majority Votej
Wang al.
22
Ensemuble Chussifer
X
General
Ensemble (Majority Vote)
Rexarl <6 m]
2023
Eneemble Classifier
X
General
X
Ensemble (Run-Off Fllction)
Drews e a|]
2120
White Box
DecisSon Trees
x
General
Abstract Interpretation
Meyer
Decision Tress
X
General
Abstract Interpretation
Jia et Al
k-Neazest, Neighbors
X
Geueral
X Majority Vote
2024
Naive Rayes Classifier
X
Clomn-lahel
Algorithmic
Ours
NNs & SVMs
Clemn-Lbel
NTK & Linear Programuning
Robustness certificates can be categorized as providing deterministic or probabilistic guarantees, and as being white box, i.e. developed for a particular model, black box (model-agnostic). While each approach has its strengths and applications (Li et al.
2023), we focus white-bor certificates as they can provide a more direct understanding into the worst-case robustness behavior of commonly used models and architectural choices (Tjeng et al.] 2019: Mao et al.) 2024 Banerjee et al. 2024). The literature on poisoning certificates is less developed than certifying against test-time (evasion) attacks and we provide an overview and categorization in Table ! Notably, white-box certificates are currently available only for decision trees (Drews et al., 2020);
nearest neighbor algorithms (Jia et al.) 2022), and naive Bayes classification (Bian et al.) 2024). In the case of Neural Networks (NNs), the main challenge in whito-box poisoning certification comes from capturing their complex training dynamics. As a result, the current literature reveals that deriving white-box poisoning certificates for NNs, and by extension Graph Neural Networks (GNNs), is still an unsolved problem, raising the question if such certificates can at all be practically computed.
In this work, we give a positive answer to this question by developing the first approach towards white-box certification of NNs against data poisoning and backdoor attacks, and instantiate it for common convolution-based and PageRank- bilevel optimization problem over the training data D that includes training on D as its inner sub- problem. To overcome the challenge of capturing the complex training dynamics of NNs, we consider the Neural Tangent Kernel (NTK) that characterizes the training dynamics of sufficiently wide NNs under gradient flow (Jacot et al., 2018 Arora et al.) 2019). In particular, we leverage the equivalence between NNs trained using the coft-margin loss and standard soft- margin Support Vector Machines (SVMs) with the NN's NTKs as kernel matrix (Chen et al.) 2021). Using this equivalence, we introduce a novel reformulation of the bilevel optimization problem as a Mixed-Integer Linear Program (MILP) that allows to certify test datapoints against poisoning well as backdoor attacks for sufficiently wide NNs (see Fig. D.. Although our framework applics to wide NNs in general, solving the MILP scales with the number of labeled training samples. Thus, it is a natural fit for semi-supervised learning tasks, where one can take advantage of the low labeling rate. In this context, we focus on semi-supervisod node classification in graphs, where certifying against node feature perturbations is particularly challenging due to the interconnectivity between nodes Zügner & Günnemann,
GNNNs Concretely, poisoning can be modeled as a
NTK
GGNN
SVM
MILP
NTK
(G)NN Certificate
SVM
Certificate
Figure 1: Illustration of our poisoning certifica- tion framework QPCert.
2

---

Published in Transactions on Machine Learning Research (06/2025)
2019b Scholten et al. 2023) Here, our framework provides general and elegant way to handle this interconnectivity inherent to graph learning, by using the corresponding graph NTKs (Sabanayagam et al.
2023 of various GNNs. Our contributions are:
(1) We are the first to certify GNNs in node cossiffissiinatiion tasks against poisoning and backdoor attacks targeting node features. Our certification framework called QPCert is introduced Sec. t and leverages the NTK to capture the complex training-dynamics of GNNs. Further, it can be applied to N.ss in general and thus, it represents the first approach on white-boz poisoning certificates for NNs.
(ii) Enabled by the white-box nature of our certificate, we conduct the first study into the role of graph data and architectural choices on the worst-case robustness of many widely used GNNs against data poisoning and backdoors (Sec. We focus on convolution and PageRank-baseed architectures and contribute the derivation of the closed- foosed-form NTK for APPNP (Gasteiger et al. 2019), GIN (Xu et al, 2018 and GraphSAGE Hamilton ct al. 2017 in App. C
(iii) We contribute reformulation of the bilevel optimization problem describing poisoning as MILP when instantiated with kernelized SVMs, allowing for white-box certification of SVMs. While we focus on the NTK as kernel, our strategy can be transferred to arbitrary kernel choices.
We represent matrices and vectors with boldfaced upper and lowercase letters, respectively. w and My denote i-th and ij-th entries of v and M. M, is the i-th row of M, In the identity matrix, laxn the matrix of all Is of size n X n. We use (...) for scalar product, Il-Ila for vector Euclidean norm and matrix Frobenius norm, 1[]] for indicator function, for the Hadamard product, [|] for expectation, and [2] for
Notation.
the smallest integer 2 (ceil). [n] denotes {1,2, 1.,2....n1p n}. App. A provides a complete list of symbols we use.
2 Preliminaries
We are given a partially-labeled graph G = (S, with n nodes and a graph structure matrix S E R220" representing for example, a normalized adjacency matrix. Each node E [n]] has features æ; E Rdd of dimension d collected in a node feature matrix X E R=xd_ We assume labels y E (1..... K} are given for the first m < n nodes. Our goal is to perform node classification, either in a transductive setting where the labels of the remaining time should be classified. The set of labeled nodes is denoted V2 and the set of unlabeled nodes Vv.
m nodes should be inferred, or in an inductive setting where newly added nodes at test
Perturbation Model. We assume that at training time the adversary A has control over the features of an e-fraction of nodes and that [(1 [[-e)nn] nodes are clean. For backdoor attacks, the adversary can also change the features of test node of interest. Following the semé-verified learning setup introduced in Charikar et al. (0117), we assume that A nodes are known to be uncorrupted. We denote the verified nodes by set Vy and the nodes that can be potentially corrupted as set U. We further assume that the strength of A to poison training or modify test nodes is bounded by a budget ò E I4. More formally, A can choose a perturbed i; E (xx) := {* | - zillp= S 5) for each node under control. We denote the set of all perturbed node feature matrices constructible by A from X as A(X) and A(g) {(S, X) X E A(X)). Tn data poisoning, the goal of A is to maximize misclassification in the test nodes. For backdoor attacks aims to induce misclassification only in test. nodes that it controls.
Learning Setup. GNNs are functions fo with (learnable) parameters 0 E R and L number of layers taking the graph g = (S) as input and outputting a prediction for each node. We consider lincar output layers with weights WL+1 and denote by [o(G); E R the (unnormalized) logit output associated to node i. Note for binary classification f9() E R. We define the architectures such as MLP, GCN (Kipf & Welling 2017). ) SGC (Wu et al.) 2019), (A) (Gasteiger et al., 2019) and others in App.
B We focus on binary classes
V E (=1} and refer to App. F for the multi-class case. Following Chen al. 2021 the parameters 0 are
learned using the soft-margin loss
() = min
W
L+1 112 +
max (x)))
2
3

---

Published in Transactions on Machine Learning Research (06/2025)
where the second term is the Hinge loss weighted by a regularization C R+. Note that due to its non- differentiability, the NN is trained by subgradient descent. Furthermore, we consider NTK parameterization (Jacot et al. 2018) in which parameters 0 are initialized from a standard Gaussian NV 1/width). Under NTK paramcterization and large width limit, the training dynamics of fo(g) are precisely characterized by the NTK defined between nodes i and j as Qiy = Q(x,, xy) VV((Voo VoJo(G),)] E R.
Equivalence of NN to Soft-Margin SVM with NTK. Chen et al. 2021 show that training NNs in the infinite-width limit with C(0, g) is equivalent to training soft-margin SVM with (sub)gradion descent using the NN's NTK as kernel. Thus, both methods converge to the same solution. We extend this equivalence to GNNs, as detailed in App. D More formally, let the SVM be defined as fo(g);
(x; = (8, ((x))) where ((-) is the feature transformation associated to the used kernel and 0 = 3 are the learnable parameters obtained by minimizing [(0, g). Following Chen et al. (2021), we do not include a bias term. To find the optimal 8r, instead of minimizing L(0,9), we work with the equivalent dual
m
m
Pi(Q)= min- Σ
E
yayaaaaQQi s.l. 0 0sasSo
(1)
2
with the Lagrange multipliers a E RT and kernel Q:, D 2ÿ) E R computed between all labeled nodes i.j E [m]. The optimal dual solution may not be unique and we denote the set of a solving (Q) by S(Q).
However, any a E S(Q) corresponds to the same unique 3 = - Maa; (()); minimizing L(0, 9) (urges & Crisp 1999). Thus, the SVM prediction for a test node t using the dual is fe J.V (XVM(x) (xx) = Σ y:a for any E S(Q), where Qn is the kernel between test node and training node i. By choosing Q to be the NTK of GNN fe, the prediction equals fo(9); if the width of the GNN's hidden layers goes to infinity. Thus, a certificate for the SVM directly translates to a certificate for infinitely-wide GNNs. Given finite-width, where the smallest layer width is h, the output difference between both methods can be bounded with high probability by O(Inh) (the probability - as h - o0). Thus, the certificate translates to a high probability guarantee for sufficiently wide finite networks.
vR)
3 QPCert: Our Certification Framework
Poisoning a clean training graph G can be described as a bilevel problem where an adversary A tries to find a perturbed & E A()) that results in a model 0 minimizing an attack objective (0,
min Can (0, s.t. t. GEA(G) A D min L(O', ()) 3
(2)
6'
Eq. ( is called an upper-level problem and ming ((0', () the lower-level problem. Now, a sample-wise poisoning certificate can be obtained by solving Eq. ( with an (0 () chosen to describe if the prediction for a test node changes compared to the prediction of a model trained on the clean graph. However, this approach is challenging as even the simplest bilevel problems given by a linear lower-level problem embedded in an upper-level linear problem are NP-hard (Jeroslow, 1985). Thus, in this section, we develop a general methodology to reformulate the bilevel (aamlle-wise) certification problem for kernelized SVMs as a mixed-integer lincar program, making certification tractable through the use of highly efficient modern MILP solvers such as Gurobi (Gurobi Optimization, LLC 2023) CPLEX (Cplex) 2009). Our approach can be divided into three steps: (1) The bilevel problem is reduced to single-level problem by exploiting properties of the quadratic dual (Q):: (2) We model 9 E A(g) by assuming a bound on the effect any õ can have on the elements of the kernel Q. This introduces relaxation of the bilevel problem from Fqq. (2) and allows to fully express certification as a MILP; (3) In Sec. 3.1 choose the NTK of different GNNs as kernel and develop bounds on the kernel elements to use in the certificate. In the following, we present our certificate for binary classification where ys } Vi E [n] and transductive learning, where the test node is already part of g. We generalize it to a multi-class and inductive setting in App. Fl
A Single-Level Reformulation. Given an SVM JSVM trained on the clean graph 9, its class prediction for a test node & is given by sgn(f:) = sgn( (zx)). ). If for all ğ e A(G) the sign of the prediction does not change if the SVM should be retrained on G. then we know that the prediction for is certifiably robust. Thus,
4

---

Published in Transactions on Machine Learning Research (06/2025)
the attack objective reads Lau(0, sgn(fe) Σx= Uia where Qus denotes the kernel computed between nodes and i on the perturbed graph G and indicates robustness if greater than zero, Now, notice that the perturbed graph 9 only enters the training objective Eq. (1) through values of the kernel matrix Q E R=** Thus, we introduce the set A(Q) of all kernel matrices Q, constructable from 9 E A()). Furthermore, we denote with S(Q) the optimal solution set to (I()). As a result, we rewrite Eq. 2 for kernelized SVMs as
P2(Q): min sgn( a
Σ Qua s.t. { A a
(3)
and certify robustness if the optimal solution to (2(Q) is greater than zero. Crucial in reformulating (2(Q) into a single-level problem are the Karush TucheTTucke (KKT) conditions of the lower-level problem (1(Q). Concretely, the KKT conditions of (Q) are
Vi E [m]
Σ , Qij - Us + 0.
(Slationarily)
(4)
04 2 0, C 0; 2 0, u 2 0, vr 20, 0,
(Primal and Dual feasibility)
(5)
n = 0, uy a.) =
(Complementary slackness)
where u E R and V E R" are Lagrange multipliers. Now, can state (see App. G for the proof):
Proposition 3.1. Problem (Q) given by Eq. 41 is convex and satisfies strong Slater's constraint. Conse-
quently, the single-level optimization problem Ps(Q) (Q) arising from P2(Q) by replacing a E S(²) with Eqs.
to 6 has the same globally optimal solutions as P2(
A Mixed-Integer Linear Reformulation. The computational bottleneck of Pa(Q) are the non-linear product terms between continuous variables in the attack objective well as in Eqs. and (6) making Qq( a bilincar problem. Thus, we describe in the following how Ps(Q) can be transformed into a MILP. First, the complementary slackness constraints can be linearized by recognizing that they have combinatorial structure. In particular, u, 0 if a; > 0 and 2 0 if ag < C. Thus, introducing binary integer variables and t E (0, 1)", we reformulate the constraints in Eq. (6) with big-M constraints
Vi [m]:
u S Ma 0; I C(1 - 8,), 8, E 10,
(7)
& S Mc,t C - a, S C(1 ((11))), t.), t E 10,
where Ma, and Mo, are positive constants. In general, verifying that a certain choice of big- Ms results in valid (mixed-intoger) reformulation of the complementary constraints Eq. 6 i.c., such that optimal solution to the original bilevel problem is cut off, is at least hard as solving the bilevel problem itself (Kleinert et al. 2020). This is problematic as heuristic choices can lead to suboptimal solutions to the original problem (Pineda & Morales 2019). However, additional structure provided by (i( and Pa(Q) together with insights into the optimal solution set allows us to derive valid and small Ma, and M., for all i [m].
Concretely, the adversary A can only make a bounded change to G. Thus, the dlement-wise difference of any Q E A(Q) to Q will be bounded. As a result, there exist element-wise upper and lower bounds OH < 20 S Q4 for all i,j E [m] U (t} and valid for any Q E A(Q). In Sec. 3.1 we derive concrete lower and upper bounds for the NTKs corresponding to different common GNNs. This, together with 0 < ag S C, allows us to lower and upper bound En Uij in Eq. (4). Now, given an optimal solution (a* Q" q²" v*) to Pa (),, observe that either us or of are zero, or can be freely varied between any positive values as long as Eq. is satisfied without changing the objective value or any other variable. As a result, one can use the lower and upper bounds on Ey D Qij to find the minimal value range for u, and U; such that Eq. (4) Dy can always be satisfied for any a' and Q'. Consequently, one can find constants Ma, and Mo, given in Proposition 3.2 such that only redundant solutions regarding large oi and og will be cut off and the optimal solution value stays the same as for (2) not affecting the certification (for formal proof see App. H.
Proposition 3.2 (Bg-MM's) Replacing the complementary slackness constraints Eq. (6) in Ps(Q) with the big- M constraints given in Eq. does not eut. away solution values of P3 P3(Q), is for any [m), the big-M values
5

---

Published in Transactions on Machine Learning Research (06/2025)
fulfill the following conditions. For notational simplicity j Condition(j) denotes j E {j E [m] Condition(
If y/ = 1 then
Mu. 2
Σ
Σ
C -1 A
}:
1AQ455
M 2
Σ
C
Σ
CQ +1.
joリ== - 20
; 30
If yi = -1 then
Mas 2
Σ
C¹
Σ
C
1:00 IAQU20
Paj=
M
2
Σ
CO
Σ
C +1.
J:H =
====-1AQ
To obtain the tightest formulation for P()) we set the big-M's M's to equal the conditions.
Now, the remaining non-linearities come from the product terms a Qig- We approach this by first introducing new variables Zzy for all j E [m] U (t) and set Zi = a, Qij. Then, we replace all a, Qiy in Eq. 44) and in the objective in Eq. (3) with Zij- This alone has not changed the fact that the problem is bilinear, only that the bilinear terms have now moved to the definition of Zyy. However, we have access to lower and upper bounds on Qij. Thus, replacing Zij = a, aiQi with linear constraints Zij S aa and Ziz 2 az results in relaxation to (Q))). This resolved all non-linearities and we can write the following theorem.
Theorem 3.3 (MILP Formulation). Node certifiably robust against adversary A if the optimal solution to the following MTLPP denoted by P(Q) is greater than zero
min sgn( Σ Yu s.t. a.
Vi E [m] (1). E [m]
Zig S 20,00 a,
Zig 2 a
m
Vi E [m]
Σ
Will Zig
u, + 1; =
1=1
0 2 0, C a; 2 0, u, 2 0, v, 0,
4, S Masi, a, S C(1 - s:), & E (0.1), 4 < Moli, C 0; S C(1-4), 4 E 10.
P(Q) includes backdoor attacks through the bounds Øt, and Qy for all j e [m], which for an adversary A who can manipulate t will be set different. On computational aspects, P(Q) involves (m + 1)2 + 5m variables out of which 2m are binary. Thus, the number of binary variables, which mainly defines how long it takes MILP-solvers to solve a problem, scales with the number of labeled samples.
3.1 QPCert for GNNs through their NTKs
To certify a specific GNN using our QPCert framework, we need to derive element-wise lower and upper bounds valid for all NTK matrices Q E A(Q) of the corresponding network, that are constructable by the adversary. As a first step, we introducee the NTKs for the GNNs of interest before deriving the bounds. While Sabanayagam al. (2023) provides the NTKs for GCN and SGC with and without skip connections, we derive the NTKs for (A)PPNP, GIN and GraphSAGE in App. C For clarity, we present the NTKs for fG( with hidden layers L = 1 here and the general case for any L in the appendix. For L = the NTKs generalize to the form Q = M(E O E)MT + MEM for all the networks, with the definitions of M, E, E and É detailed in Table 2 Thus, it is important to note that the effect of the feature matrix X, which the adversary can manipulate, enters into the NTK only as a product XX" making this the quantity of interest. when bounding the NTK matrix.
Focusing on p 1, in Bx(x) and X A(X), we derive the bounds for X by considering := {i: E Vv as the set of all unverified nodes that the adversary can potentially control. We present the

---

Published in Transactions on Machine Learning Research (06/2025)
worst-case element-wise lower and upper bounds for XXT XX + A in terms of A in Lemma 3.4 and Lemmas E.1 and E.2 in App.
Table 2: The NTKs of GNNs have the general form Q
M @ E)M² + MEM for L = 1. The definitions of
M. E, E and E are given in the table. z = S + In and
T= ((1 + I) + A Ka(z) = (I arccos (z)) and Ki (2) =
Lemma 3.4 (Bounds for A, = 20). Given
(z (TT arccos (z)) v 2²).
(x) and any X E A(X), then XX"
xX + A where the worst-case bounds for A, A J/j S is I D vi,j E [n] are
GNN
M
Σ
Eij
E.j
GCN
S SX
VEn
60
4 = 81
u 6 X uu
SGC
S SXX
Egj
1
_ j),
GraphSAGE Z ZXXTZ
V
Eng
Ki
Eig
4/ x|X [ 1 Eu
(A)PPNP P XX 1
Rgg
+ +B
GIN
I. TTT laxe 111
Ens
K0
VEn
Enj
The NTK bounds Q and Q are now de- rived by simply propagating the bounds for
MLP
I, Xx" Inxn
K00
XXT through the NTK formulation since the multipliers and addends are positive. To elaborate, we compute 0 by substituting xx"
XX +
A4,
and likewise for T. Only bounding Eig and Éig needs special care as discussed in App. E.1 prove that the bounds are tight in the worst-case App. E.2
Further, we
Theorem 3.5 (NTK bounds are tight). The worst-case NTK bounds are tight for GNNs with linear activations such as SGC and (A)PPNP, and an MLP with o(2) = for p = (1,2,00) in (,(x).
4 Experimental Results
We present (i) the effectiveness of QPCert in certifying different GNNs using their corresponding NTKs against node feature poisoning and backdoor attacks; (ii) insights into the role of graph data in worst-case robustness of GNNs, specifically the importance of graph information and its connectivity; (iid) study of the impact of different architectural components in GNNs on their provable robustness. The code base and datasets to reproduce the experimental results can be found at htttps://github.. wwtpe/ooeeee/////eeeeeeee
Dataset. We use the real-world graph dataset Co (Bojchevski & Günnemann 2018 where we generate continuous 384-dim. embeddings of the abstracts with a modern sentence transformer similar to Fuchsgruber et al. (2024). Furthermore, for binary classification, we use Cora-ML. and another real-world graph WikiCS (Mernyei& & Cangea 2022) and extract the subgraphs defined by the two largest classes. We call the resulting datasstss FL.h and WikiCSb, respectively. Lastly, we use graphs generated from Contextual Stochastic Block Models (CSBM) (Deshpande et al., 2018 for controlled experiments on graph parameters. We give dataset statistics and information the random graph generation scheme in I.I For Cora-MLb and WikiCSb, we choose 10 nodes per class for training, leaving 1215 and 4640 unlabeled nodes, respectively. For Cora-ML, we choose 20 training nodes per class resulting in 2925 unlabeled nodes. From the CSBM, we sample graphs with 200 nodes and choose 40 per class for training, leaving 120 unlabeled nodes. All results are averaged over 5 seeds (Cora-ML: 3 seeds) and reported with standard deviation. We do not need a separate validation set,, as we perform 4-fold pross-validation (CV) for hyperparameter tuning.
GNNs and Attack. We evaluate GCN, SGC, (A)PPNP, GIN, GraphSAGE, MLP, and the skip connection variants GCN Skip-a and GCN Skip-PC (see App. B). All results concern the infinite-width limit and thus, are obtained through training an SVM with the corresponding GNN's NTK and, if applicable, applying QPCert using Gurobi to solve the MILP from Theorem 3.3 We fix the hidden layers to L= 1, and the results for L. = 4 are provided in App. J.2 For CSBMs we fix C = 0.01 for comparability between experiments and models in the main section. We find that changing C has little effect on the accuracy but can strongly affect the robustness of different architectures. Other parameters on CSBM and all paramoters on real-world
Mall-MiniL from http::://igggnnffssccc///eeeeeee httpc///eeccccccaaaaeeeeeee////e www.strrrnnseeeeeeootootota Maaeee/aaaaMMMMMa--MM-a L8-v2

---

Published in Transactions on Machine Learning Research (06/2025)
GDI Cortitte Accuracy
Cern Avemuryy
Cer Fied Ausurauy
Cee Lied Aucuracy
DICK
8
CC SCT
un
01
15
CA
02
Returiation Budgel (p
Pecturintion Budge
Pertarlation
Burlge 6 (p
Pertarbation Budgel 8
(a) Cora-MLb: Pado =
(b) WikiCSh: Padv
(c) Cora-MLb: Padv = 0.1
(d) WikiCSh: Padv 0.1
Figure Poison Labeled (PL) setting for Cora-MT.b and WikiCSb. (a)-(b): QPCert effectively provides
non-trivial guarantees. (a)-(d); All GNNs show higher certified accuracy than an MLP.
Certibed Accuracc
Cartifee Accuraucy
Ceet Reetdieed Accurayy
Cartifiee Accurary
OCN BLC
APPSP
Guptbiict
0.
AGC
Su BGC
CCN Sky. IY
GreaSAGE GEX Si.,
CEN Sij-
alt ue d1
18
Pertubbttoon Budges 5 (p
Pertuciation Budget
Perturation Budget (p oc)
Pertubation Budget
(a) Cora-MLb: PU
(b) Cora-MLb: BU
(c) CSBM: PU
(d) CSBM: BU
Figure& 3: Certifiable robustness in the Poisoning Unlabeled (PU) and Backdoor Unlabeled (BU) setting with
Pady = 0.1 for Cora-MLb and Padv = 0.2 for CSBM. We refer to App. M for WikiCSb.
datasets are set using 4-fold Cross Validation (CV) (see App. 1.2 for details). The SVM's quadratic dual problem is solved using QPLayer (Bambade et al. 2023). differentiable quadratic programming solver. Thus, to evaluate tightness regarding graph poisoning, we use APGD (Croce & Hein 2020) with their reported hyperparameters as attack, but differentiate through the learning process using two different strategies: (i) QPLayer, and (fi) the surrogate model proposed MetaAttack (Zügner Günnnemann 2019a). To evaluate backdoor tightness, we use the clean-label backdoor attack from Xing et al. (2024), and the above APGD attack, but at test time additionally attack the target node.
Adversarial Evaluation Settings. We calegorize four settings of interest. (1) Poison Labeled (PL): The adversary A can potentially poison the labeled data VL. (2) Poison Unlabeled (PU): Especially interesting in a semi-supervisod setting when A can poison the unlabcled data Vu, while the labeled data, usually representing a small curated set of high quality, is known be clean [Shejwalkar et al.) 2023 (3) Backdoor Labeled (BL): Like (1) but the test node also controlled by A. (4) Backdoor Unlabeled (BU): Like (2) but again, the test node is controlled by A. Settings (1) and (2) are evaluated transductively, i.e. on the unlabeled nodes Vy already known at training time. Note that this means For the backdoor attack settings (3) and (4) the test node is removed from the graph during training and added inductively at test time. The size of the untrusted potential adversarial node set U is set in percentage Pado E {0.01, 0.02, 0.05, 0.2, 0.5, }} of the scenario-dependdnt attackable node set and resampled for each seed. We consider node feature perturbations (x) with p = {1, oc} and provide all results for p p= 1 in set in percentage of 24 of the underlying distríbution, and for real data to absolute values. Our main evaluation metric is certified accuracy, referring the percentage of correctly classified nodes without attack that are provably robust against data poisoning backdoor attacks of the assumed adversary A. As there are no other white-box poisoning certificates applicable to neural networks, there are no white-box certificate basclines. Furthermore, we note that we are the first work to study certificates for clean-label allacks on node features in graphs. In particular, all current black-box certificates do not apply to graph learning or lp perturbation models (see Sec. G). Thus, there is no direct bascline prior work. However, we adapt the saiit-anddmajjoiin vote principle from Levine & Feizi (2021) for black-box certification of node-feature perturbations in graphs and provide a comparison in App. Furthermore, we provide comparison with two common poisoning defenses in App. J.8
test nodes may be corrupted for (2).
App. J.6 and K.4 In the case of CSBM,
8

---

Published in Transactions on Machine Learning Research (06/2025)
CertiSed Accrrcy
CortiiSed Accurace
Certified Accuraac B
APPSP
A
NPPNP
8
APPSP
65
Perturbation Budget 5 (p 1p=00 00)
Perturation Budget 8ip=
Perturiation Budget (p o0)
(a) SGC (WikiCSb:PU)
(b) CSBM: PU
(c) Cora-MLb: PU
(d) CSBM: PU
Figure 4: Poison Unlabeled for WikiCSb (Pude = 0.02), Cora-MLb PPad==0.1) CSBM (Pads = 0.2). (a) Certified accuracy gain: difference of certified acc. to an MLP. (b) Graph connectivity analysis where ex is ep and og in CSBM model. (c) APPNP analysis based on a. (d) Tightness of QPCert (differentiation through the learning process using QPLayer).
Non- Trivial Certificates and On the Importance of Graph Information. We evaluate the effectiveness of our certificates in providing non-trivial robustness guarantoes. Consider the PL setting where can poison all labeled nodes (Pade = 1) for which a trivial certificate would return 0% certified accuracy. Figs. 2a and 2b prove that QPCert returns non-trivial guarantees. Further, they highlight
interesting insight: All GNNs have significantly better worst-case robustness behavior than the certified accuracy of an MLP, Thus, leveraging the graph connectivity, significantly improves their certified accuracy, even when faced with perturbations on all labeled nodes. In Figs. 2c and 2d we show that this observation stays consistent for other Pade. We observe similar results for Mo (App. D and CSBM (App. J.I., establishing that this behavior is not datasct-spcciffc.
In Fig. 3 we evaluate the poison unlabeled (PU) and backdoor unlabeled (BU) settings. When poisoning only unlabeled data (PU), the MLP's training process is not affected by the adversary, as the MLP does not access the unlabeled nodes during training. Thus, this provides good baseline for our certificate to study GNNs. Again, QPCert provides non-trivial certified robustness beyond the MLP baseline. Close to all GNNs show certified accuracy exceeding the one of an MLP for small to intermediate perturbation budgets (6 s 0.1) for Cora (Fig. Ba) and CSBM (Fig. Bel, with a similar picture for WikiCSb (App. M and Cora-MI ML (App. L). Note that the small certified accuracy drop for an MLP stems from the transductive learning setting, in which the MLP is confronted with the potentially perturbed unlabeled training nodes at test time. For WikiCSb, Fig. 4a elucidates in detail the certified accuracy gain of an SGC to MLP and for other GNNs, see App. M (and App. K. for Cora-MLb, App. J.1 for CSBM). Concerning backdoor attacks on unlabeled nodes Figs. 3b and 3d show that most GNNs show significantly better certified robustness than an MLP, even so MLP training is not affected by A. We observe similar results for a BL setting for Cora-MLb (App. K.I), WikiCSb (App. My, and CSBM (App. J.1]. These results show that leveraging graph information can significantly improve certified accuracy across all attack setlings. Further, across all evaluation settings and datasets, we find GIN and GraphSAGE to provide the lowest certified accuracies of all GNNs; their most important design difference is choosing a sum-aggregation scheme. We note that comparison across architecture can be affected by the certificate's tightness and we hypothesize that the high worst-case robustness of SGC compared to other models may be due to the certificate being tighter (Theorem 3.5 However, this still allows us to derive architectural insights for specific GNNs.
On Graph Connectivity and Architectural Insights We exemplify study directions enabled through our certification framework. By leveraging CSBMs, we study the effect of graph connectivity in the poisoning unlabeled setting in Fig, 4b for a GCN. Interestingly, we observe an inflection point at a perturbation strength 8 0.05, where higher connectivity leads to higher certified accuracy against small perturbations, whereas higher connectivity significantly worsens certified accuracy for strong perturbations. These trends are consistent across various architectures and attack settings (App. J.2) Secondly, we study the effect of different a choices in APPNP in a poison unlabeled setting in Fig. 4cl on Cora-MLb. Interestingly, it also shows an inflection point at a perturbation strength (6 = 0.1), where higher a increases the provable robustness for larger 5, whereas worsens the provable robustness for smaller 8. Notably, this phenomenon is unique to the PU setting (see App. K.2) and similarly observed in CSBM as shown in App. J.2 This setup is different the connectivity analysis from Fig. 4b as the a in APPNP results in a weighted adjacency matrix rather than
9

---

Published in Transactions on Machine Learning Research (06/2025)
increasing or decreasing the number of edges in the graph. We compare different normalization choices for S in GCN and SGC in App. K.3. Through these analyses, we note that our certification framework enables informed architectural choices from the perspective of robustness.
5 Discussion
How Tight is QPCert? We compute an upper bound on the provable robustness using APGD by differentiating through the learning process. The results in Fig. show that the provable robustness bounds are tight for small pertubation budgets 8 but less tight for larger 6, demonstrating one limitation (for other settings and attacks see App. J.3 While theoretically, the NTK bounds are tight (Theorem (.5), the approach of deriving element-wing bounds
Q to model A leading to relaxation of (2( can explain the gap between provable robust ness and an empirical attack. Thus, an opportunity for future work is to explore alternative approaches for modeling A in the MILP P(Q).
Is QPCert Deterministic or Probabilistic? Our certification framework is inherently deterministic, offering deterministic guarantees for kernelized SVMs using the NTK as the kernel. When the width of a NN approaches infinity, QPCort provides a deterministic robustness guarantee for the NN due to the exact equivalence between an SVM with the NN's NTK as kernel and the infinitely wide NN. For sufficiently wide but finite-width NNs this equivalence holds with high probability (Chen et al. 2021), making our certificate probabilistic in this context. However, note that this other methods such as randomized smoothing (Cohen et al. 2019), in which the certification approach itself is probabilistic and heavily relies on the number of samplings and thus, inherently introduces randommess.
guarantee is qualitatively different from
How General is QPCert? While we focus on (G)NNs for graph data, our framework enables whito-box poisoning certification of NNs on any data domain. QPCert can be readily extended to other architectures, provided the equivalence between the network and NTK holds and the corresponding NTK bounds are derived. We detail these criteria in App. 0.4 Further, it allows for certifying general kernelized SVMs for arbitrary kernel choices if respective kernel bounds as in Sec. [.1 are derived. To the best of our knowledge, this makes our work the first white-box poisoning certificate for kernelized SVMs. Moreover, the reformulation of the bilevel problem into a MILP is directly applicable to any quadratic program that satisfies strong Slater's constraint and certain bounds on the involved variables, hence the name QPCert. Thus extensions to certify quadratic programming layers in NN (Amos & Kolter (017) or other quadratic learners are thinkable. Therefore, we believe that our work opens up numerous new avenues of research into the provable robustness against data poisoning.
On QPCert's Perturbation Model. We study node feature perturbations due to the fact that: (i) they are of practical concern in many applications of GNNs such as spam detection (Li et al. 2019) or fake news detection (Hu et al., 2024]. and we refer to App. 0.3 for a detailed discussion on their practical relevance; and (ii) certification against them poses unique graph-related challenges due to the interconnectedness of nodes (Scholten et al.) 2022 Zügner & Günnemann 2019b). In contrast, certifying against poisoning the graph structure remains an open, but important problem. We outline the thereby arising complex technical challenges in App. 0.2 Furthermore, we study clean-label attacks bounded by ly-threat models instead of arbitrary perturbations to nodes controlled by A. Gollblum et al. (2023) distinctively names studying bounded clean-label attacks as an open problem, as most works assume unrealistically large input perturbations. Morcover, we study semi-verified learning (Charikar et al. 2017). This is particularly interesting for semi-supervised settings, where often a small fraction of nodes are manually verified and labeled (Shejwalkar et al.) 2023), or when learning from the crowd (Meister & Valiant) 2018 Zeng & Shen 2023). However, this may produce overly pessimistic bounds when large fractions of the training data are unverified, but the adversary can only control small part of it. In App. A.p. we further contextualize our threat model within the scope of commonly studied poisoning attacks. Last but not least, we note that we focus on studying certification against poisoning threat models compared to test-time attacks, as they severely understudied (see Sec. G while highly relevant in practice (see Sec.
How Scalable is QPCert? QPCert scales to the size of common benchmark graphs such as Cora-ML or WikiCS. This is comparable to the size of datasets currently manageable by deterministic cortificates for test-time attacks for GNNs (Hojny et al. 2024). Here, it is important to note that poisoning certification is
10

---

Published in Transactions on Machine Learning Research (06/2025)
inherently more complex as it requires accounting for the model's training dynamics rather than certifying static model. Thus, this demonstrates the effectiveness of our modeling approach. Nevertheless, deterministic certification even in the "simpler' scenario of test-time attacks is NP-hard (Katz et al. 2017). As a result, all
deterministic certificates, also against test-time attacks, have difficultics scaling to large-scale datasets
et al. 2023) and QPCert is no except.ion. We explore QPCert's computational limits in detail in App. N further improve scalability, it would be an interesting avenue for future work to investigate strategies to relax P(Q) to achieve an even more favorable trade-off between scalability and tightness.
6 Related Work
The literature on poisoning certificates is significantly less developed than certifying against test-time (evasion) attacks (Li et al. 2023) and we provide an overview in Table
Black-Box Poisoning Certificates. Black-box certificates for poisoning are derived following three different.
approaches: (1) Randomized smoothing, popular probabilistic test-time certificate strategy (Cohen et al. 2019), with randomization performed over the training dataset (Rosenfeld et al. 2020 Weber et al. 2023 Zhang et al. 2022). Also following this approach, Hong et al. (2024) certifies dlifusiion-based data sanitation via randomized smoothing.
(tt) Ensembles: Creating separate partitions of the training data, training individual base classifiers on lop of them and certifying constructed ensemble classifier (Levine Peizi
2021 Jia et al. 2021 Wang et al. 2022 Rezaci et al. [023] Chen et al. 2022;; (fii) Differential Privacy (DP):
: Ma al. (2019) show that any (e, O)-DP learner enjoys a certain provable poisoning robustness. [Liu
ct al. (023)) extend this result to more general notions of DP. Xie et al. (2023) derives guarantees against
arbitrary data poisoning in DP federated learning setup.
White-Box Poisoning Certificates. There is little literature on white-boz poisoning certificates and existing techniques (see Table I cannot be extended to NNs. Drews et al. (2020) and Meyer et al. (0021) derive poisoning certificates for decision trees using abstract interpretations, while Jia et al. (2022) provides a poisoning certificate for nearest neighbor algorithms basod on their inherent majority voting principle. Recently, Bian al. (2024) derives a poisoning certificate for naive Bayes elassification. A concurrent work (Sosnin al. 2024 develops a gradient- based certificate for data poisoning for an MLP in non-graph setting based on over-approximating the reachable set of parameters. However, their relaxation suffers from significant lightness issues, and in App. O.5 we show for MLPs that QPCert can certify significantly larger perturbation budgets. Further, their method is difficult to extend to other architectures, while this can be readily done with QPCert. We note that Steinhardt et al. (2017) develops statistical bounds on the loss for data sanitation defenses that are not applicable certify classification.
Poisoning Attacks and Defense Using the Bilevel Formulation.
The bilevel problem in Eq. (2) is studied by several works in the context of developing poisoning attacks or empirical defenses (Biggio et al.
2012 Xiao et al.] 2015 Koh & Liang] 2017 Jagielski et al., 2018). Biggio et al. (2012) and Xiao et al. [2015] iteratively solve the bilevel problem associated to an SVM trained on the hinge loss with gradient ascent to generate poisoned samples. Notably, Mei & Zhu 2015 reformulate the bilevel problem Pz(Q) for SVMs to a bilinear single-level problem similar to P2(Q) )) but only solve it heuristically for attack generation and do not realize the possibiiltty of MILP reformulation and certificate. Koh & Liang (2017) also considers the bilevel problem to detect and generate poisoned samples using influence functions (gradient and Hessian vector product) for linear model well as convolutional neural networks. In the case of graphs, Lingam et al. (2024) develops a label poisoning attack for GNNs using the bilevel problem with regression objective and including NTKs as surrogate models.
Poisoning Certificates for Graph Neural Networks. Currently, there are no white-box poisoning certificates for GNNs, nor clean-label poisoning certificates for the task of node classification. There are only two type of works on poisoning certificates for GNNs with both being black-box and differing incomparably in their thrcat model to QPCert. The first is Lai et al. (2024b) and their follow-up (Lai et al.) 2024a), which uses the randomized smoothing paradigm to develop probabilistic and black-box certificates for
Thh mechanism to derive a poisoning certificate from certain privacy guarantee is model agnostic, thus we count it as box. However, the calculated privacy guarantees may depend on whxte-box knowledge.
11

---

Published in Transactions on Machine Learning Research (06/2025)
node injection. Second, concurrent to our work, Li et al. 2025 develops black-box poisoning certificate for GNNs based on ensembling (Levine & Feizi, 2021). While their method allows to certify clean-label attacks for graph classification, it cannot be applied to certify clean-label attacks for node classification as their partitioning stratogy includes the poisoned node in cach partition. Thus, this affects each base classifier through the training gradients resulting in no certified accuracy. Furthermore, it assumes arbitrary (unbounded) modifications of data and thus, settings with high Padv such as Pade = 1 studied in Figs. 2a and 2b would always lead zero certified accuracy and being unable to provide non-trivial guarantees.
Test-time (Evasion) Certificates for Graph Neural Networks. When it comes to certifying test-time (evasion) attacks instead of training-time perturbations (poisoning), the literature is more extensive. Existing evasion certificates usually either lackle certifying node feature perturbations (Scholten et al.] 2023 2022
Zügner & Günnemann 2019b) or structure perturbations (Schuchardt et al., 2021: Zügner & Günnemann
2020: Bojchevski & Günnemann 2019) separately. There are some works whose methods can tackle both under limiting assumptions. Exemplary, (Bojchevski et al.) 2020) developed a black- randomized smoothing evasion certificate and can (probabillssticllly) certify features of a smoothed classifier if they are discrete. Xia] et al. (2024) derive black-box evasion certificate based partitioning the graph and using the ensemble certification method from Levine & Feizi (2021). However, their certificate only concerns the ensemble and not individual GNNs and, as is common for all ensemble- based works, assumes arbitrary (unbounded) perturbations for controlled nodes. Hojny et al. (2024) is the only white-box evasion certificate work that can certify structure and feature perturbations but is only applicable to GNNs that don't normalize the adjacency matrix in any non-linear way excluding most commonly used GNNs such as GCN or APPNP.
7
Conclusion
We derive an effective white-box poisoning certificate framework for sufficiently-wide NNs via their NTKs and demonstrate its applicability to semi-supervised node classification tasks common in graph learning. In particular, we show that QPCert provides non-trivial robustness guarantees and insights into the worst-case poisoning robustness to feature perturbations of wide range of GNNs. Moreover, our framework extends beyond GNNs and graph learning tasks, enabling certification of any neural network where NTK equivalence holds as well as any kernelized SVM, given the derivation of respective kernel bounds. Our extensive analysis of QPCert showcases both its strengths and directions for future research. We discuss this in detail in Sec. 5 and summarize the main points here. While we show the element bounding of the kernel to be tight (Theorem 3.5 there still a gap between the empirical and provable robustness for larger perturbations. Thus, this motivates further research into developing more sophisticated strategies to derive the kernel bounds. Furthermore, QPCert focuses on node feature perturbations, while extending it to structural perturbations presents new technical challenges (App. O.2 offering another avenue for future rescarch. In terms of scalability, QPCert effectively certifies common benchmark graphs such as Cora-ML and WikiCS. Further advancing deterministic certification techniques to efficiently scale to significantly larger datasets is an open and impactful research direction.
Broader Impact Statement
Our method represents a robustness certificate for white-box models. This allows more informed decision when it comes to the safety aspects of currently used models. However, insights into worst-case robustness can be used for good but potentially also by malicious actors. We strongly believe that research about the limitations of existing models crucial in making models safer and thus, outweighs potential risks. We are not aware of any direct risks coming from our work.
Acknowledgements
The authors want to thank Yau Scholten and Pascal Esser for the interesting discussions. The authors also want to thank them and Leo Schwinn, for the helpful feedback on the manuscript. This paper has been supported by the DAAD programme Konrad Zuse Schools of Excellence Artificial Intelligence, sponsored by the German Federal Ministry of 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
12

---

Published in Transactions on Machine Learning Research (06/2025)
References
Brandon Amos and J. Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference on Machine Learning (ICML), 2017.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advonces in Neural Information Processing Systems (NeurIPS), 2019.
Antoine Bambade, Fabian Schramm, Adrien Taylor, and Justin Carpentier. QPLayer: efficient differentiation of convex quadratic optimization. 2023. URL https: /tttps://inra..ie hal hcce///cccccee///100100305555
Debangshu Banerjee, Avaljot Singh, and Gagandeep Singh. Interpreting robustness proofs of deep neural networks. In International Conference on Learning Representations (ICLR), 2024.
Song Bian, Xiating Ouyang, ZHIWEI FAN, and Paris Koutris. Naive bayes classifiers over missing data: Decision and poisoning. In International Conference on Machine Learning (ICML., 2024.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In International Conference on Machine Learning (ICML), 2012.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Neural Information Processing Systems (NeurIPS), 2019.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference Learning Representations, 2018.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günneeaann Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning (ICML), 2020.
Christopher J. C. Burges and David Crisp. Uniqueness of the svm solution. In Advances in Newral Information Processing Systems (NeurIPS), 1999.
Carlini, M. Jagielski, C. Choquette- Choo, Paleka, W. Pearce, H. Anderson, A. Terzis, K. Thomas, and F. Tramèr. Poisoning web-scale training datasets practical. In IEEE Symposium on Security and Privacy (SP), 2024.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2017.
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.
Ruoxin Chen, Zenan Li, Jie Li, Junchi Yan, and Chentao Wu. On collective robustness of bagging against data poisoning. In International Conference on Machine Learning, pp. 3299-33911 PMLR, 2022.
Yilan Chen, Wei Huang, Lam Nguyen, and Tsui-Wer Wei Weng. On the equivalence between neural network and support vector machine. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning (ICML), 2019.
IBM ILOG Cplex. V12. 1: User's manual for cplex. International Business Machines Corporation, 2009.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free altacks, 2020.
Enyan Dai, Minhua Lin, Xiang Zhang, and Suhang Wang. Unnoticeable backdoor attacks on graph neural networks. Tn Proceedings of the ACM Web Conference 2023, pp. 2263 2273,277, 2023.
13

---

Published in Transactions on Machine Learning Research (06/2025)
S. Dempe and J. Dutta. Is bilevel programming special case of a mathematical program with complementarity constraints? Math. Program., 131:37-48, 2012. doi:
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
Samuel Drews, Aws Albarghouthi, and Loris D'Antoni. Proving data-poisoning robustness decision trees. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 1083-1097, 2020.
Dominik Fuchsgruber, Tom Wollschläger, and Stephan Günnemann. Energy-based epistemic uncertainty for graph neural nelworks. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
Johannes Gasteiger, Alcksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference Learning Represenlations (ICLR), 2019.
Jonas Geiping, Liam H Fowl, W. Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. In International Conference Learning Representations (ICLR), 2021.
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 defenses. IEEE Transactions Pattern Analysis & Machine Intelligence, 45(02):1563 1580, 2023. ISSN 1939-3539.
Lukas Gosch, Daniel Sturm, Simon Geisler, and Stephan Güineemann. Revisiting robustness in graph machine learning. In International Conference on Learning Representations (ICLR), 2023.
Kathrin Grosse, Lukas Bieringer, Tarek R. Besold, Battista Biggio, and Katharina Krombholz. Machine lcarning security in industry: A quantitative survey. IEEE Transactions on Information Forensics and Securily, 18:1749-11 1762, 2023.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances Neural Information Processing Systems (NeurIPS), 2017.
Christopher Hojny, Shiqiang Zhang, Juan S. Campos, and Ruth Misener. Verifying message-pasee passing neural networks via Nopology-basee bounds tightening. In International Conference on Machine Learning (ICML), 2024.
Sanghyun Hong, Nicholas Carlini, and Alexey Kurakin. Diffusion denoising certified defense against clcan-label poisoning. arXiv preprint arXiv:2403. 11981, 2024.
Bo Hu, Zhendong Mao, and Yongdong Zhang. An overview of fake news dotoction: From a new perspective. Fundamental Research, 2024. ISSN 2667-3258.
W. Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Metapoison: practical general- purpose clean-label data poisoning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in noural networks. Advances in neural information processing systems, 31, 2018.
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In IEEE Symposium Security and Privacy (SP), 2018.
Robert G Jeroslow. The polynomial hierarchy and a simple model for competitive analysis. Mathematical programming, 1985.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Jinyuan Jia, Xiaoyu Cao, and Neil Zhengiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. In Proceedings of the A AT conference artificial intelligence, volume 35, pp. 7961-7969, 2021.
Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong, Certified robustness of nearest neighbors against data poisoning and backdoor attacks. In AAAI Conference on Artificial Intelligence (AAAI), 2022.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Rehuplex: An efficient SMT solver for verifying deep neural networks. In Rupak Majumdar and Viktor Kuncak (eds.), International Conference on Computer Aided Verification (CAV), volume 10426, pp. 177117, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 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.org/ 10. 120.1127////0 opt.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning (ICML), 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning, 111(1):1 47, 2022.
Yuni Lai, Bailin Pan, Kaihuang Chen, Yancheng Yuan, and Kai Zhou. Collective certified robustness against graph injection attacks. In International Conference on Machine Learning (ICML), 2024a.
Yuni Lai, Yulin Zhu, Bailin Pan, and Kai Zhou, Node-aware bi-smoothing: Certified robustness against graph injection attacks. In JEEE Symposium on Security and Privacy (SP), 2024b.
Thai Le, Suhang Wang, and Dongwon Leo. Malcom: Generating malicious comments to attack neural fake news detection models. In 2020 IEEE International Conference on Dala Mining (ICDM), 2020.
A Levine and S Feizi. Deep partition aggregation: Provable defense against general poisoning attacks. In International Conference on Learning Representations (ICLR), 2021.
Ao Li, Zhou Qin, Runshi Liu, Yiqun Yang, and Dong Li. Spam review detection with graph convolutional networks. In International Conference on Information and Knowledge Management (CIKM), 2019.
Jiate Li, Meng Pang, Yun Dong, and Binghui Wang. Deterministic certification of graph neural networks against graph poisoning attacks with arbitrary perturbations. In arXiv preprint arXiv:2503.1854 2025.
Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. In IEEE Symposium on Security and Privacy, (SP), 2023.
Vijay Lingam, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Rethinking label poisoning for GNNs: Pitfalls and attacks. In International Conference on Learning Representations (ICLR), 2024.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the lincarity of large non-lincar models: when and why the langent kernel is constant. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Shijie Liu, Andrew C. Cullen, Paul Montague, Sarah M. Erfani, and Benjamin I. P. Rubinstein. Enhancing the antidote: Improved pointwise certifications against poisoning attacks. In AAAI Conference on Artificial Intelligence (AAAI), 2023.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Liu Hua, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference on Machine Learning (ICML), 2021.
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially- private learners: Attacks and defenses. In International Joint Conference on Artificial Intelligence (IJCAT), 2019.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Yuhao Mao, Mark Niklas Mueleer, Mare Fischer, and Martin Vechev. Understanding certified training with interval bound propagation. In International Conference on Learning Representations (ICI.), 2024.
G.P. McCormick. Computability of global solutions to factorable nonconvex programs: Part convex underestimating problems. Mathematical Programming, 10:147-175, 1976.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-sct attacks machine learners. In AAAI Conference Artificial Intelligence (AAAI), 2015.
Michela Meister and Gregory Valiant. A data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory (COLT), 2018.
Péter Mernyei and Cätälina Cangea. Wiki-os: A wikipedia-based benchmark for graph neural networks. International Conference on Machine Learning (ICML) GRL+ Workshop, 2022.
Anna Meyer, Aws Albarghouthi, and Loris D' A'ttoni.. Certifying robustness to programmable data bias in docision trees. Advances in Neurol Information Processing Systems (NeurIPS), 2021.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning, second edition. The MIT Press, 2018
Luis Muñoz- Gonzáázz, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Tupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradient optimization. Proceedings of the 10th ACM workshop on artificial intelligence and security, pp. 27 38, 2017.
Salvador Pineda and Juan Miguel Morales. Solving lincar bilevel problems using big-ms: Not all that glitters is gold. IEEE Transactions Power Systems, 34(3):2469-2277 2019. doi: (..1099/PPRS..20 2019.2892007.
Keivan Rezaei, Kiarash Banihashem, Atoosa Chegini, and Soheil Feizi. Run-off election: Improved provable defense against data poisoning attacks. In International Conference on Machine Learning (ICML), 2023.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label-fippiig attacks via randomized smoothing. In International Conference on Machine Learning, pp. 8230 8241. PMLR, 2020.
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.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized mnsssage-interception smoothing: Gray-box certificates for graph neural networks. In Advances in Neural Information Processing Systems, NeurIPS, 2022.
Yan Scholten, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnerann. Hierarchical randomized smoothing. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Jan Schuchardt, Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Collective robustness certificates: Exploiting interdependence in graph neural networks. In International Conference on Learning Represenlations (ICLR), 2021.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, (9)) Sep. 2008.
Virat. Shejwalkar, Lingjuan Lyu, and Amir Houmansadr. The perils of learning from unlabeled data: Backdoor attacks on semi-supervised learning. In International Conference on Computer Vision (ICCV), 2023.
Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia. Adversarial machine bearinnginddsste perspectives. In 2020 IEFE Securily and Privacy Workshops (SPW), pp. 69 69-75, 2020.
16

---

Published in Transactions on Machine Learning Research (06/2025)
Amira Soliman and Sarunas Girdzijauskas. Adagraph: Adaptive graph-based algorithms for spam detection in social networks. In Networked Systems, pp. 338-354, 354, 2017.
Philip Sosnin, Mark N. Müller, Maximilian Baader, Calvin Taay, and Matthew Wicker. Certified robustness data poisoning in gradient-based training, 2024.
J Michael Steele. The Cauchy-Schewary master class: an introduction to the art of mathematical inequalities. Cambridge University Press, 2004.
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data, poisoning attacks. Advances in neural information processing systems, 30, 2017.
Octavian Suciu, Radu Märginean, Yigitcan Kaya, Hal Daumé, and Tudor Dumitras. When does machine learning fail? generalized transferability for evasion and poisoning altacks. In USENIX Conference on Security Sympostum (SEC), 2018.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming, 2019.
Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Clean-label backdoor attacks, 2019. URL httpp:://openreview http://wwweeeoooommmocccooooeeee
Alexander Wan, Eric Wallace, Sheng Shen, and Dan Klein. Poisoning language models during instruction luning. In International Conference on Machinn Learning (ICML), 2023.
Binghui Wang, Xiaoyu Cao, Jinyuan jia, and Neil Zhenqiang Gong. On certifying robust against backdoor attacks via randomized smoothing, 2020.
Guan Wang, Sihong Xie, Bing Liu, and Philip S. Yu. Identify online store review spammers via social review graph. ACM Trans. Intell. Syst. Technol., 3(4), 2012.
Haoran Wang, Yingtong Dou, Canyu Chen, Lichao Sun, Philip S. Yu, and Kai Shu. Attacking fake news detectors via manipulating news social engagement. In ACM Web Conference (WWW), 2023.
Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In International Conference Machine Learning (ICML), 2022.
Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. In IEEE Symposium on Security and Privacy (SP), 2023.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. Tn International Conference on Machine Learning (ICML), 2019.
Zhaohan Xi, Ren Pang, Shouling Ji, and Ting Wang. Graph backdoor. In 30th USENIX Security Symposium (USENIX Security 21), pp. 1523 1540, 2021.
Zaishuo Xia, Han Yang, Binghui Wang, and Jinyuan Jia. GNNCert: Deterministic certification of graph
neural networks against adversarial perturbations. In International Conference on Learning Representations (ICLR), 2024.
Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? In International Conference on Machine Learning (ICML), pp. 1689 1698. PMLR, 2015.
Chulin Xie, Yunhui Long, Pin- Yu Chen, Qinbin Li, Sanmi Koyejo, and Bo Li. Unraveling the connections between privacy and certified robustness in federated learning against poisoning attacks. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023.
Xiaogang Xing, Ming Xu, Yujing Bai, and Dongdong Yang. A clean-label graph backdoor attack method in node classification task. Knowledge- Based Systems, 304:112433, 2024.
17

---

Published in Transactions on Machine Learning Research (06/2025)
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2018.
Shiwei Zeng and Jie Shen. Semi-verified pac learning from the crowd. In International Conference on Artificial Intelligence and Statistics (ATSTATS), 2023.
Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural nerworks against. adversarial attacks. In Advances in Neural Information Processing Systems (NewrlPS), 2020.
Yuhao Zhang, Aws Albarghouthi, and Loris D'Antoni. Bagflip: A certified defense against data poisoning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems (NewrIPS), 2022.
Daniel Zügner and Stephan Günnemann. Adversarial attacks graph neural networks via meta learning. In International Conference on Learning Represenlations (ICLR), 2019a.
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In International Conference on Knowledge Discovery & Data Mining (KDD), 2019b.
Daniel Zügner and Stephan Günnemann. Certifialle robustness of graph convolutional networks under structure perturbations. In ACM International Conference on Knowledge Discovery & Data Mining (SIGKDD), 2020.
18

---

Published in Transactions on Machine Learning Research (06/2025)
A Symbols and Abbreviations
In addition to the general notations provided, we give a detailed list of symbols and abbreviations use with descriptions in the following.
(S.
A graph with structure matrix R and feature matrix X Raxd
The label vector [K] of size $
Vr.
The set of all labeled nodes in graph g The set of all unlabeled nodes in graph g
Vu
VV
The set of verified nodes in graph G
U
The set of potentially corrupted nodes in graph
(x(x)
The set of allowed perturbations { || =|p S with budget ó E R The adversary A chooses node feature perturbations from Bp
A(G)
fo(g)
GNN with learnable parameters The prediction of GNN for node i
(0(9);
(SVM(x))
The SVM objective equivalent to fo(G); in the infinite-wine width limit
C(0,9)
The soft-margin loss
c
The regularization strength E R2 in (),
w
The weight matrix of I-th layer
Q
The NTK matrix of size n x n corresponding fo(g) The set of optimal dual solutions to SVM S M (x:) The dual variables of the SVM JSVM m
S(Q)
pe
The clean prediction of the SVM for a test node t, i.e., E/s Nia where a' E S(Q) perturbed graph E A(9)
ğ
(a
The attack objective
Q
The NTK matrix Rexx corresponding to g
A(Q)
All NTK matrices Q constructable from ğ E A(G)
u
The Lagrangian multipliers E 12mh in the stationarity condition of the KKT
s,t
The binary integer variables E (0.1)
Ma, M
The positive constants in big-M M constraints
Q!
The lower bound for Q
The upper bound for Q
Zg
A variable that is = Q,
(()@)
The bilevel optimization problem describing node feature poisoning
P2(Q)
The bilevel optimization problem terms of the NTK matrix Q
Ps(Q)
The single-level optimization problem
P(Q)
The final MILP
The optimal a to P(Q)
19

---

Published in Transactions on Machine Learning Research (06/2025)
u², V
The optimal u, v to P(Q)
8",
The optimal S, t to P(Q)
The optimal P(Q)
A
The perturbation matrix added to xX"
A
The lower bound for Au The upper bound for Aij
A
PL
Abbr. for Poison Labeled setting
PU
Abbr. for Poison Unlabeled sctting
BL
Abbr. for Backdoor Labeled setting
BU
Abbr. for Backdoor Unlabeled setting
B
Architecture Definitions
We consider GNNs as functions fo with (lcarnable) parameters 0 E R and L number of layers taking the graph G = (S as input and outputs a prediction for each node. We consider linear output layers with weights WL+1 and denote by fo();; E R the (unnormalized) logit output associated to node i. In the following, we formally define the NG) such as MLP, GCN (Kipf & Welling 2017). SGC (Wu et al. 2019 and (A)PPNP (Gasteiger et al., 2019) considered in our study.
Definition B.1 (MLP). The L-layer Multi-Layer Perceptron is defined as fo(g); f8 (.MLP(x.) WL+ % (x:). With o o ow ((-1) (x: ) + bO)) and (0)) (xx) z; W Rduixdd and b(0) E Rd are the weights/ beights/biases /biases of the 1-th layer with dg = d and d = K. a--) is an element-wise activation function. If not mentioned otherwise, we choose a(2) ReLU(==) max(0,
Definition B.2 (GCN& & SGC). Graph Convolution Network fo JGCN (G) Kipf Welling 2017 of depth L is defined fo(9) = d (()+)(()) with &0 (9) ( (0(00-)) ((() and og (1)
(g) SXW()) W() Rddixdd
are the 1-th layer weights, do = d, d K, and (2)) ReLU(z) applied element-wist A Simplified Graph Convolution Network f5GC(() Wu et al. 2019) is GCN with lincar (2) =2.
Definition B.3 (GraphSAGE). The L-lerrr GraphSAGE (G))GE(() Hamilton et al. 2017 is defined as (G)
fe(g) = 0g (() with oh (g) = o (G) + So (1 (1-1) w(D). w xd the 1-th layer weights, dg d, dr+1 K, and (()) ReI.U(2) applied element-wise. S is fixed to row normalized adjacency (mean aggregator), D-1A.
(( (9)) and (G) = XW, 11 (
Definition B.4 (GIN). A one-layer Graph Isomorphism Network JGIN (Xu et al. 2018 is defined fe(g) f (MMP(() (G) with G ((1 e)I+ A)X where is a fixed constant and an one-layer ReLU as MLP. Definition B.5 PPNP. The Personalized Propagation of Neural Predictions Network f (PPNP(() Gasteiger et al. 2019 is defined as fo(g) PH where H. MLPP (x:) and P a(I, (1 a) -1 The Approximate PPNP defined with = (1 - a) k + t K-1 (1 - a) where a E [0. 1] and K E N is fixed constant.
For APPNP and GIN, we consider an MLP with ono-layer ReLU activations as given in the default. implementation of APPNP.
Along with the GNNs presented in Definitions B.1 to B.5 consider two variants of popular skip connections
in GNNs given a name in Sabanayagam et al. (2023): Skip-PC (pre-convolution). where the skip is added
to the features before applying convolution (Kipl & Welling 2017); and Skip-a, which adds the features lo each layer without convolving with S (Chen et al. 2020). To facilitate skip connections, we need to enforce constant layer size, that is, d, = d,-1- Therefore, the input layer is transformed using a random matrix W H, XW of size n x h where W. ~ (O 1) and the hidden layer size. Let H, be the output of layer using which formally define the skip connections follows.
20

---

Published in Transactions on Machine Learning Research (06/2025)
Definition B.6 (S). In Skip-PC (pre-convolution) network, the transformed imput Ho is added to the hidden layers before applying the graph convolution S, that is, Vi E [L] 0g (g) =
s (o(o)) + to (Ho) w where (2 can be linear or ReLU.
Skip-PC definition deviates from Kipf & Welling (017)) because we skip the input layer instead of the previous one. We define Skip-a defined in Sabanayagam et al. 2023 similar to Chen et al. (020)).
Definition B.7 (Skip-a). Given an interpolation coefficient E (0,1), Skip-a network is defined such that the transformed input Ho and the hidden layer are interpolated linearly, that is, 08 (g)
(11 (1-0) a) (G) + ad, (Ho) W, Vi e [4], where 0g (2) can be linear ReLU.
C Derivation of NTKs for (A)PPNP, GIN and GraphSAGE
In this section, we derive the NTKs for (A)PPNP, GIN and GraphSAGE, and state the NTKs for GCN and SGC from Sabanayagam et al. [022).
C.1 NTK for (A)PPNP
We derive the closed-form NTK expression for (A)PPNP fo(9) (Gasteiger et al. 2019 in this section. The learnable parameters are only part H. In practice, H = R
B2 where node features X (W1 E Rdxh, W₂ E R B1 Raxh, B2 E [. Note that in the actual implementation of the MLP, B2 vector and we consider it be a matrix by having the same columns so that we can do matrix operations easily. Same for B2 as well. We give the full architecture with NTK parameterizatiin in the following,
fa(9)= P( (W, + W,) + B₂)
(8)
where h + oo and all parameters in 0 are initialized as standard Gaussian \(0, 1). Co is constant to We derive for K 1 as all the outputs are equivalent in (V),, (o)o()) Hence, we first write down
preserve the input norm (Sabanayagam et al. 2023
expectation. The NTK between nodes and j is
E
(-N(0.1)
the gradients for node following Arora
2019
Sabanayagam al.
2023
@f)(G); Co (P)o(()))
16 = = + B
OW2 Vh
0So()), (I.)TIn.
0B,
(G) & x" (P 1, w OG()))
OW, Vh
(9) C,
1, e ((1)
Vh
We note that B2 has only one learnable parameter for K 1, but is represented a vector of size with all entries the same. Hence, the derivative is simply adding all entries of Pt. First, we compute the covariance between nodes i and in G1.
E (XWW (G))s (G1) [ + B1)a. (XW, +WW+DD +B)),R]
IE
Since the expectation is over W, and Bi and all entries are (0, 1), and i.i.d, the cross terms will be in expectation. Also, for l * W. it is O. Therefore, it gets simplified to
E (G1) (G1)ga) =E X,W, WF + (B,Bf),)
=(Xx") in + (E1).)
(9)
21

---

Published in Transactions on Machine Learning Research (06/2025)
Thus, = XX 1 uxn and let (Ei), = [(0(4)))0(011 and (Et)., = ( computed using the definitions in Theorem C.1 for ReLU non- con-iincrrity Now, we can compute the NTK for each paramcter matrix and then sum it up to get the final kernel.
(5(()): 0[((5);
2 P
OW2
OW2
h
P. (PP
= C.P.P.
(10)
(f)(
(f)
Pilax PJ
(11)
0B2
0B2
(f((9)
(9)
40000 (RGGEHGHHHGGGEPEEPPPPPPPP
(12)
JB
(5-(9); 0(0(9)1
= Σ
&
f.h
x P 1, W o (g (Pf 1n W @ ((())) P9
OW1 OW,
h
P.
(P. W (G1)an
Σ ( (P) W bo (g))ba)
h=000
P
( P P (xx E)
(13)
Finally, the NTK matrix for the considered (A)PPNP is sum of Eqs. 10 to 13 as shown below.
Q og (PE,P" Plaxn PT PÊ
XXX
E, PT) E, P"))
= e (P E + 1axx) Pd + P (Xx + 1 1axn)
o (P E 1nxx) PT + P E E,) P?)
(14)
Note that ea is a constant, and it only scales the NTK, so we set it to 1 in our experiments. Since we use a linear output layer without bias term at the end, that is, By = 0, the NTK we use for our experiments is reduced
Q P ( P P7).
C.2
NTK for GIN
The GIN architecture Definition B.4 is similar to APPNP: P and X in APPNP are Identity and & in GIN, respectively. Hence the NTK is exactly the same as APPNP with these matrices. Thus, the NTK for GIN is
Σ O ET) Q ==
with Σ, = GGT 1 18xn E
(F) and É = [a(F)o(F)T]
F-N(O,E))
22

---

Published in Transactions on Machine Learning Research (06/2025)
C.3 NTKs for GCN and SGC
We restate the NTK derived in Sabaaaayagam et al. (2023) for self containment. The GCN of depth L with width di + oo vl E {l,..., , the network converges to the following kernel when trained with gradient flow.
Theorem C.1 (NTK for Vanilla GCN). For the GCN defined in Definition B.2 the NTK Q at depth L and K = is
L+1
Q4)= =
Σ S
((....(s (2x O Ex) S O BATTSST o... ....o... &E.)s
(15)
k=1
L+1-K terms
Here Σg Ruxx is the co-variance between nodes of layer h. and is given by E, SXX Σg SE
with Eg Co
E
(FF))(FF)*] E, Co
E [o(F) and Ef+1 Laxn.
F=)(()
F~N(0,EE))
(Ex)ss
En (Bx);; = VV (En)gs 1n
V (Ex)ss (Ek)ss
(Ei))e
(Bx) Ko
(Is)i (Ei)
1 where (2)2)= (π arccos(2)) and (2(2)
1 (2 arccos(2)) + v1 v/-=2).
π
π
C.4 NTK for GraphSAGE
From the definition of GraphSAGE Definition B3 it is very similar GCN with row normalization adjacency S D-1A where A and D are adjacency matrix with self-loop and its corresponding degree matrix. The differences in GraphSAGE are the following: there is no self-loop to the adjacency as S = D A, and the neighboring node features are weighted differently compared to the node itself using W1 and W2. Given that the NTK is computed as the expectation over weights at initialization and infinite width, both W, and W₂ behave similarly. Hence, these weights can be replaced with a single parameter W which transforms the network definition of GraphSAGE to (G (I W and similarly (G) (I ())(()) ) with S = D-'DDAAA. A. Thus, the NTK for GraphSAGE is the same as GCN with the difference in the graph normalization S.
D Equivalence of GNNs to SVMs
We show the equivalence between GNNs and SVMs by extending the result from Chen et al. 2021 which showed that an infinito-width NN trained by gradient descent on a soft-margin loss has the same training dynamics as that of an SVM with the NN's NTK as the kernel. The fulerum of their proof that directly depends on the NN is that the NTK stays constant throughout the training (refer to (Chen et al. 2021] Theorem 3.4)). As we consider the same learning setup with only changing the network to GNNs, it is enough to show that the graph NTKs stay constant throughout training for the equivalence to hold in this case.
Constancy of Graph NTKs. This constancy of the NTK in the case of infinitely-wide NNs is deeply studiod in Liu et al.) 2020) and derivod the conditions for the constancy as stated in Theorem D.1
Theorem D.1 (QLiu et al. 2020)). The constancy of the NTK Uhroughout the training of the NN holds if and only if (i) the last layer of the NN is linear; (ii) the Hessian spectrol norm ||]] of the neural network with respect to the parameters is small, that is, O with the width of the network; (Mii) the parameters of the network w during training and at initialization is bounded, that is, porameters time t, We, satisfies l wolla S.
Now, we prove the constancy of graph NTKs of the GNNs by showing the three conditions.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Linear last layer. The GNNs considered in Definitions B.1 and B.7 have linear last layer.
( Small Hessian spectral norm. Recollect that we use NTK parameterization for initializing the network parameters, that is, (0,, 1/witth). This is equivalent to initializing the network with standard normal
M(0,1) 1) and appropriately normalizing the layer outputs (Arora et al., 2019 Sabanayagam et al. 2023). To exemplify, the APPNP network definition with the normalization given in Eq. (8). Similarly for other (!) $0 where h is the width of the layer 1. As all our GNNs
GNNs, the normalization results in scaling %6 have a simple matrix multiplication of the graph structure without any bottleneck layer, the Hessian spectral norm is (In h/ Vh) as derived for the multilayer fully connected networks in Liu et al. (2020). Therefore, h - 00 the spectral norm + 0.
(iit) Bounded parameters. This is dependent only on the optimization of the loss function as derived in
Chen et al. (2021 Lemma D.1). We directly use this result as our loss and the optimization are the same as
Chen et al. 2021
With this, we show that the considered GNNs trained by gradient descent on soft-margin loss is equivalent to SVM with the graph NTK as the kernel.
E Derivation of NTK Bounds and Theorem 3.5
In this section, we first present the bounds for A in the case of p 2 and p = 1 in (x) (Lemma E. and
Lemma E.2 and then derive Lemmas 3.4 E.1 and E.2 and Theorem 3.5 stated in Sec. 3.1
Lemma E.1 (Bounds for A, = 2). Given B2 (x) and any X A(X), then XX" = Xx" A where the
worst-case bounds for A, A = Au s 2 for all and j E [n], is
A jj = 6 X 2/ E 4] X| I2j = aa-o'liiunjjuuiin
A 6 6 X 2 ii E 41
X 2 j 41 EllEEEEEE
(16)
Lemma E.2 (Bounds for A, p = 1). Given (x) and any X A(X), then XX" = XX" + A where the worst-case bounds for A, A s Au Σ 2 for all and E [n].
A 8| X ; | E 4] i| x 1
Eu| EljEEANj
6
X || i 4 + X زز 41 L
(17)
To derive Lemmas 3.4 E.1 and
E.2 we consider the perturbed feature matrix X E A(X) and derive the based on the perturbation model (x) where p = 0o, p 2 and = 1 in our study. Let's say W the set of nodes that are potentially controlled by the adversary A(X) and x x + r E Rad where I; is the adversarial perturbations added to node by the adversary, therefore, | 1p < 8 and r > for i E U and r, = for i o U. Then
worst-case bounds for XX" T'
XXT = [X+ (X+
XXX TXX XI +II XX +A.
(18)
As result, it suffices to derive the worst-case bounds for A, A < A < AU for different perturbations. To do so, our strategy is to bound the scalar products (T,, X,) and (T,, T3) element-wise, hence derive
A < Ag A In the following, we derive D and A for the cases when p = 20, = 2 and p = 1 in (x).
Case (i): Derivation of Lemma 3.4 for p == co. In this case, the perturbation allows ||X], X1 S + 1 =1 for all p. E [1) we have
then by Hölder's incquality (a, b) S |a | where 1
p
(T, (1,,,)) < [Tll X
|11 S 8||,
[T, r3)]
|Talla|
D < d - d82.
(19)
24

---

Published in Transactions on Machine Learning Research (06/2025)
Using Eq. 19
the worst-case lower bound 1 is the lower bound of rx" XT" + +TT":
0+
if Eu if j Eu
X11,,
(20)
811 x
6dd
if i Eu and i i j-
The last case in Eq. 220) is due to the fact that (T,, D,) 2 0, hence A = 0. Finally, the Eq. 220 can be succinctly written using the indicator function as
4 = - X 1 E EU] - 6 X:Il 1i E E4 aunjeuunuuuera
deriving the lower bound in Lemma 3.4 Similarly, applying the Hölder's inequality for the worst-case upper bound, get
0+
if &u ilieu iE if Eu.
8 8||x||1i
4
(21)
8111,111+
d
Thus, we derive Lemma 3.4 by succinetly writing it as
1 + 8 X E4 &aliEunnenn
Case (ii): Derivation of Lemma E.1 for p 2. The worst-case lower and upper bounds of Ai for p 2 is derived in the similar fashion p Here, the perturbation allows IX X,lla 5. Hence,
(T, < D X s X|,
(T,, I,, S T T 1l2 - 8²
(22)
Using Eq.
we derive the lower and upper bounds of A,y:
0+
if i,j &u if Eu if EU if i Eu
0+
if i,j 4u ifieu
1|,,
0||X; 1122+
A
A =
1/
=
||
5
X lla
jf
82
82
if if
Case (iit): Derivation of Lemma is derived in the similar fashion p Here, the perturbation allows |X, X,l1ı 5. Hence,
E.2 for p 1. The worst-case lower and upper bounds of Aij for p
(T X,x) X I 6 X 1
T TT & [ I 1 & T E².
(23)
Using Eq.
we derive the lower and upper bounds of Ay:
0+
if i,j $ zu if El
0+
if $ if
XX 11
8||X, 1loo
4 =
A =
5 X,, lloo
if eu if Eu
if EU
82
if ifje
25

---

Published in Transactions on Machine Learning Research (06/2025)
E.1 Bounding Fay and Byy in the NTK
NTKs for GNNs with non-lincar ReLU activation have E and E with non-linear K1(2) and Ko(2) functions in their definitions, respectively. In order to bound the NTK, need strategy to bound these quantities well. In this section, we discuss our approach to bound Eig and Eij through bounding the functions for any GNN with L layers. For ease of exposition, we ignore the layer indexing for the terms of interest and it is understood from the context. Recollect that the definitions of and E are based on Σ, which is a lincar combination of and the previous layer. So, we consider that this stage, we already have Σ, ΣL and E Now, we expand the functions in the definition and write Eig and Eij using their corresponding Σ as follows:
Eij EE
Eij VEn
)) + v11
Σ Ej;
Eij
arccos
(24)
1
Dij
Eij
arccos
(25)
Eis Eis
We derive the lower and upper bounds for Eij and Eig in Algorithm 1
Algorithm Procedure to compute Etj, En Eig and Ey
Given E, E and E
Let s
V E4
s"
/ E
if 74 " > 0 then
D
22
a'
=
gu a²
else
ΣV
al
a"
end if
if
[/1
then
2
ij
8
s
else
1 st
1/
10
end if
FL
(a) T arccos (a!)) + v1 bm
Ey a" (π - arccos (a")) + v1 B²
EL 1 (π arccos (a'))
FL
"ig π [TT arccos (a"))
E.2 Derivation of Theorem 3.5 NTK Bounds are Tight
We analyze the tightness of NTK bounds by deriving conditions on graph G = (S, X) when A and A are attainable exactly. As our NTK bounding strategy based on bounding the adversarial perturbation X and the non-linear functions ko(2) and Ky (2),,, it is easy see that the bounds with con-lincarities cannot be tight. So, consider only linear GCN (=SGC), (A)PPNP and MLP with linear activations.
26

---

Published in Transactions on Machine Learning Research (06/2025)
Now, we focus deriving conditions for the given node features X using the classic result the equality
condition of Hölder's inequality (Steele) 2004), and then analyze the NTK bounds. Steele
(2004
Fig. 9.1)
a
shows that the bounds on (a, b) using the Höder's inequality is reached when |a:|a= [b,]" analyze
Using this,
bbl
A = (T, ( (T)
(26)
in which we call (T,, F) as interaction term. Following this analysis, the tightness NTK bounds is derived below for p = do and p Case (i): p oo. In this case, the feature bounds in Eq. 19 are tight,
Vj. X3 and Vi, T =
where G is some constant such that ||T I 5 so the perturbation budget is satisfied. As a result, the upper bound of Ayy in Lemma 3.4 is achieved exactly in the following cases,
(a) Number of adversarial nodes 1: Here the interaction term in Eq. (66 is for all i and j. Then for the one adversarial node i, there exists X; E R4., one can set r; = +ô1, to achieve the upper bound.
(b) Number of adversarial nodes > 1: Here the interaction term is ş 0 for all the adversarial nodes i and j. Then, for the adversarial nodes i and if there exist X; E TR. and Xj E IR4 then for r, = T2 +ō1d upper bounds are achieved.
The NTKs with linear activations Qi achieve the upper bound in these cases. Similarly, the lower bound in Lemma 3.4 achieved exactly as discussed in the following,
(a) Number of adversarial nodes 1: Here the interaction term in Eq. 266 0 for all i and j. Then for the adversarial node i, there exists X, E I$ one can set r, = -61a to achieve the lower bound.
(b) Number of adversarial nodes > 1: Here the interaction term is o O for all the adversarial nodes i and j. Then, for the adversarial nodes and j if there exist. X; E Rd and X, E Rdd then for r; = -ôl and r3 = +81d;
leading tight lower bounds of Lemma 3.4 The lower and upper tight bounds of A together lead to tight NTK bounds for linear activations. Note that there is need to impose any structural restriction the graph S to achieve the tight bounds for NTK.
Case (ti): p = 2. In this case, the feature bounds in Eq. 12 are tight,
Vi X, and I, are linearly dependent
and [|T||22 S 8 so the perturbation budget is satisfied. As a result, the upper bound of Ag in Lemma E. is achieved exactly in the following,
(a) Number of adversarial nodes = Here the interaction term in Eq. (66 is 0 for all i and j. Then for the one adversarial node i, and any X, RRd one can set r, +6 X la
x to achieve the upper bound.
(b) Number of adversarial nodes > 1: Here the interaction term is * 0 for all the adversarial nodes and j. Then, for the adversarial nodes and j, if there exist X, E I2 and X, E IR are linearly dependent, then for [x tight upper bound is achieved.
D. 1==+0-x x, and E, +8 X;
The NTKs with linear activations Qıy achieve the worst-case upper bound in these cases. Similarly, the lower bound in Lemma. F.1 is achieved exactly discussed in the following,
(a) Number of adversarial nodes = 1: Here the interaction term in Eq. (26) is O for all i and j. Then for the adversarial node i, and any X, Rd one set r; - X
| to achieve the lower bound.
(b) Number of adversarial nodes > Here the interaction term is + for all the adversarial nodes and j. Then, for the adversarial nodes and j, if there exist X, E IR and X, E IRd are linearly dependent, then for X, r, - 1 and r, +6 x; 1
27

---

Published in Transactions on Machine Learning Research (06/2025)
leading to tight lower bounds of Lemma. E.1 The lower and upper tight bounds of A together leads to tight NTK bounds for linear activations. Note that there is no need to impose any structural restriction on the graph S to achieve the tight bounds for NTK, same as the p = oo case. We further note that only one instance of achieving the worst-case bound is stated, and one can construct similar cases, for example by considering opposite signs for the features and pert perturbations.
Case (fii): p In this case, the feature bounds in Eq. 23 are tight,
Vj, Xj and Vi, i3 cl [k = arg max X,]
k'
where c c- d to satisfy [[il S 6. As result, the upper bound of Aij in Lemma E.2 is achieved exactly in the following cases,
(a) Numbor of adversarial nodes 1: Here the interaction term in Eq. 26 is O for all i and j. Then for the one adversarial node i, for any j, X, + 0 and arg max X, = k, one can set F = sgn(X jx)6 and Ta 0 v k # k achieve the upper bound.
(b) Number of adversarial nodes > 1: Here the interaction term is + 0 for all the adversarial nodes and j. Then, for the adversarial nodes i and j if there exist arg max X; = arg max X, = k and sgn(Xix) sgn(X,))) then for Fi = Fy = sgn(Xix) )o and vk' # k. Fiv- = I fy = upper bounds are achieved.
The NTKs with lincar activations Qiy achiove the upper bound in these cases. Similarly, the lower bound in Lemma E.2 is achieved exactly as discussed in the following,
(a) Number of adversarial nodes 1: Here the interaction term in Eq. (6) is 0 for all i and j. Then for the one adversarial node i, for any J, X, + 0 and arg max Xj = k, one can set Dik sxn(X and Ta = 0 v k' + k to achieve the lower bound.
(b) Number of adversarial nodes > 1: Here the interaction term is + 0 for all the adversarial nodes and j. Then, for the adversarial nodes and j if there exist arg max X; = arg max X, = and sgn(X,x) = - sgn(X then for F& =
rs = sgn(X,x)0 and Ak' * k, Fs = T = 0,
leading to tight lower bounds of Lemma E.2 The lower and upper tight bounds of A together leads to tight NTK bounds for linear activations. Again, there is no need impose any structural restriction on the graph S to achieve the tight bounds for NTK.
F Multi-Class Certification
In this section, we discuss the certification for multi-class. We abstract the NN and work with NTK here. Hence, to do multi-class classification using SVM with NTK, we choose One-Vs-All strategy, where we learn K classifiers. Formallyy we learn , ;.....,8 3 which has corresponding duals at, at,..., a In order to learn 8 all samples with class label e are assumed to be positive and the rest. negative. Assume from hence on that for all c, 8 corresponds the optimal solution with the corresponding dual a Then the prediction for a node t is c* arg max, of where P Em Ua where Q is the NTK matrix.
Given this, we propose simple extension of our binary certification where to certify a node t as provably robust, we minimize the MILP objective in Theorem 3.3 for the predicted class c* and maximize the objective for the remaining K 1 classes. Finally, certify t to be provably robust only if the objective for c* remains maximum. Formally, we state the objective below.
Theorem F.1. Node with original predicted class c* is certifiably robust against adversary A if c' C where e' is defined in the following. Using the MILP P(Q) in Theorem 3.3 define.
P(Q). := P(Q) using at, with the only change in obj. to (-1)2[ete))
Σ Zoi
1m
c/ arg max P(Q).. c-
(27)
[[[K]
28

---

Published in Transactions on Machine Learning Research (06/2025)
G Proof of Proposition 3.1
We restate Proposition 3.1
Proposition 1. Problem (i( given by Eq. ①1 is conver and satisfies strong Slater's constroint. Conse-
quently, the single-level optimization problem (2( arising from P2(Q) by replacing E S(Q) with Eqs. 4 to has the same globally optimal solutions as P2(Q).
Given any Q E A(Q). We prove two lemmas, leading us towards proving Proposition 3.1
Lemma G.1. Prohlem Pi (Q) is conver.
Proof. The dual problem () associated do an SVM with bias term reads
m
m
m
P1 min
a4
Ui,aa,a,Qij
s.t.
a. a. = S Vi E [m]
(28)
==
It is a known boxtbook result that QQ) is convex and we refer to Mohri et al. (2018) for a proof. A necessary and sufficient condition for an optimization problem to be convex is that the objective function as well as all inequality constraints convex and the equality constraints affine functions. Furthermore, the domain of the variable over which is optimized must be conyex set. As removing the bias term of an SVM results in dual problem (Q) which is equivalent to (Q) only with the constraint Σn 0:3i O removed, the necessary and sufficient conditions for convexity stay fulfilled.
Now. we define strong Slater's condition for (Q) embedded in the upper-level problem P2(Q) defined in Eq. 33 which we from here on will call strong Slater's constraint qualification DDmpe & Dutta, 2012
Definition G.2 (Slater's CQ). The lower-level convex optimization problem Pi(Q) fulfills strong Slater's Coustraint Qualification, if for any upper-level feasible Q AA()), there exists point a(Q) in the feasible set of P (Q) such that constraint in Pi(Q) is active, i.e. 0 < aQQ); C' for all [m].
Lemma G.3. Problem (i) fulfills strong Slater's constraint qualification.
Proof. We prove Lemma G.3 through a constructive proof. Given any upper-level feasible Q E A(Q). Let a be an optimal solution to P (Q). We restrict ourselves to cases, where (i( is non-degenerate, i.e. the optimal solution to the SVM #VV corresponds to a weight vector B * 0. Then, at least for one index f E [m] it must hold that a; > 0.
Assume that j is the index in (m] with the smallest a, > 0. Let e = aj/m + 0. Now, we construct a new a' from a by for each e [m]] setting:
If a; = 0, sot ae c.
If aq C, set af C c.
The new a' fulfills 0 < a' (²), < C for all i [m]. (()) degenerate, set a'(²); =C/2 for all [m]. This concludes the proof.
Dempe & Dutta 2012 establish that any bilevel optimization problem U whose lower-level problem is convex and fulfills strong Slater's constraint qualification for any upper-level feasible point has the same global solutions as another problem defined by replacing the lower-level problem L U with L's Karash Kuhn Tucker conditions. This, together with Lemmas G.T and G.3 concludes the proof for Proposition
29

---

Published in Transactions on Machine Learning Research (06/2025)
H Setting big-M constraints
We repeat Proposition 3.2 for readability.
Proposition H.1 (Big-M's M's). Replacing the complementary slackness constraints Eq. (6 in Pa(Q) with the big- M constraints given in Eq. does not cut away solution values of Ps(Q), ; if for any E [m], the big-M values For notational simplicity j Condition(j) denotes j E {j E [m] Condition(())-
fulfill the following conditions.
If yı = then
Ma; 2
Σ
C
Σ
C² -1
(29)
ji9s =
j:;= =- IAQU
Q 50
Me,-
2
Σ
C
Σ
C² +1
(30)
190=-1n@f 20
j: 1=
If y; = -1 then
Ma; 2
Σ
C
Σ
CÂI -1
(31)
3:0 3w-=--nQu! 20
, 50
M 2
Σ
C
Σ
CQ +1
(32)
1
= <0
Proof. Denote by UB an upper bound to Σラ=1 Vill Zzz and by LB lower bound to Σ V.dgZis. The
existence of these bounds follows from Vi and V/ 1-1,1] and Zij azQis with 0 aj C and
0 s Qu S Q i.e the boundedness of all variables.
un and vs need to be able to be set such that EØ=1 Willi Zig - u4 + U; = (see Eq. 4 can be satisfied given any and Q part of an optimal solution to (s( By using UB and LB we get the following inequalities:
UB u, + 21
(33)
and
LB ui + + $1
(34)
Denote Σ Zij by T. Thus, if 1, sctting v; 0 and 44 SUB-1A4 LB allows to satisfy
Eq. 4 1( <1, 1, setting u; 0 and < AB 2 1 UB allows to satisly Eq. 4 Note that for a given i, we are free to set and to arbitrary positive values, as long they satisfy Eq. as they don't. affect the optimal solution value nor the values of other variables.
Thus, adding u, I UB - and 4 < 1 LB as constraints to P2(Q) does not affect its optimal solution. Consequently, setting M,, 2 UB and M,,, 2 LB, are valid big-M constraints the mixed-integer reformulation of the complementary slackness constraints Eq. (6) The UB and LB values depend the sign of yı Yj and the bounds on aj and Qi and the right terms Eqs. 29 to represent the respective U. and LB arising. This concludes the proof.
Additional Experimental Details
1.1
Datasets
The CSBM implementation is taken from Gosch
publicly released under MIT license. Cora-ML taken from (Bojchevski & Günnemann 2018) also released under MIT license. Cora-ML, has 2995 nodes
2023
30

---

Published in Transactions on Machine Learning Research (06/2025)
with 8158 edges, and 7 classes. It traditionally comes with 2879 dimensional discrete bag-of-words node feature embedding from the paper abstract. As we focus on continuous perturbation models, we use the abstracts provided by [Bojchevski & Günnemann 2018 together with all-MimiL-M-L6-v2,, a modern sentence transformer from https: htttp:://uggs:: htt.///gggggaacceeee//m/ dimensional continuous ure embeddings. From Cora-MI, we extract the subgraph defined by the two most largest classes, remove singleton nodes, and call the resulting binsry-classffication datasct Cora-MLb. It has 1235 nodes and 2601 edges. WikiCSb, created from extracting the two largest classes from WikiCS, is the largest used dataset with 4660 nodes and 72806 edges.
transformers ore aall -Ml-MMMilM----------- L6-v2 to gencrate 384-
1.1.1 CSBM Sampling Scheme
A CSBM graph with n nodes is iteratively sampled as: (a) Sample label y/ ~ Bernoulli(1/2) Vi [n]: (b) Sample feature vectors X:lya (yip,, W(ypp,o'Ia): (c) Sample adjacency Aij Bernoulli(p) if yr = yy Aij Bernoulli(g) otherwise, and A Aiy- Following Gosch et al. (2023) set p,q through the maximum likelihood to Cora (Sen et al., 2008) (p = 3.17%, q= 0.74%), and element-wise to Ka/2vd with d n In (n)J, 1, and K 1.5, resulting in an interesting classification scheme where both graph structure and features necessary for good generalization. We sample 200 and choose 40 nodes per class for training, leaving 120 unlabeled nodes.
1.2 Code, Hyperparameters, and Architectural Details
Code. We provide the code base with datasets and configuration files to reproduce the experiments in https://github. hwtpa//ccccccaap///eeeeeee The randomness in the experiments is controlled by setting fixed seeds which are given in the experiment configuration files.
Hyperparameters and Architectural Details. We fix S to Srow for GCN, SGC, GCN Skip-a and GCN Skip-PC following Sabanayagam et al. (2023). and to Saym for APPNP following its original implementation. From the GNN definitions App. B the graph convolution for GIN (1 [1++)1++ I + A, for GraphSAGE is I+D-IA.
For APGD, we use the reported hyperparameters from Croce & Hein (2020).
We outline the hyperparameters for Cora-MT.b, for CSBM all parameters are mentioned above except the Skip-a for GCN Skip-a which was set to 0.2.
GCN (Row Norm.): C = 0.75
GCN (Sym. Norm.): C C=1
SGC (Row Norm.): C = 0.75
SGC (Sym. Norm.): 0.75
APPNP (Sym. Norm.): C' = 1, 0.1
MLP: C 0.5
GCN Skip-a: C = 1, a = 0.1
GCN Skippe: C 0.5
GraphSAGE: C 0.1
GIN: C 0.05
For Cora-MI, the following hyperparameters were set:
GCN (Row Norm.): C = 0.05
SGC (Row Norm.): C 0.0575
31

---

Published in Transactions on Machine Learning Research (06/2025)
APPNP (Sym. Norm.): C 0.15, 0.2
MLP: C 0.004
GCN Skip-a: C = 0.04, a = 0.2
GCN Skippe: C 0.03
GraphSAGE: C = 0.002
GIN: C = 0.0125
For WikiCSb:
GCN (Row Norm.): C =
SGC (Row Norm.): C === 5
APPNP (Sym. Norm.): C 0.75,
MLP: C = 0.175
GCN Skip-a: C 0.1, a 0.1
GCN Skippe: C ==1
GraphSAGE: C 0.175
For the halfmoon dataset:
MLP: C' 0.025
1.3 Hardware
CPU using Gurobi internal cluster. Experiments for CSBM, Cora-ML.b and WikiCSb do not require more than 15GB of RAM. Cora-ML experiments do not require of RAM. The time to certify node depends on the size of MILP well as the structure of the concrete problem. On our hardware, for CSBM and Cora-MLb certifying one node typically takes several seconds up to one minute on a single CPU. For Cora-ML, cortifying a node can take between one minute and several hours (< 10) using two CPUs depending on the difficulty of the associated MILP.
Experiments
than 20GB
Additional Results: CSBM
J.1 Evaluating QPCert and Importance of Graph Information
Fig. 5a shows the same result as Fig. 2a from Sec. establishing that including graph information boosts worst-case robustness in CSBM too. This also shows that the result is not dataset-specific. In Fig. we provide the remaining settings in correspondence to Fig. 3 Poison Labeled PL and Backdoor Labeled BL for CSBM. Similarly, the heatmaps showing the certified accuracy gain with respect to MLP is presented in Fig. G
32

---

Published in Transactions on Machine Learning Research (06/2025)
Certified Avcuracy
Cortified Avcuracy
Certified Accuracy
GEN
GCN
ARCAP SOC
APPNF
APPNP
SGC
SGC
GraphSAGE
GIN
GranSAGE
0.2
Sup-PC
OCN Skip
GCN Sap
GCN Ski
MLP
ML.
MLP
001
C.U2
0.05
6.1
0.2
DOL 022
005
01
012
6.5
001 002
0.05
0.1
0.2
0.5
Perturbation Budget 5
00)
Perturbation Budget
20)
Perturbation Budget 6 (p 00)
(a) CSBM: PL, Pado =1
(b) CSBM: PL, Pado = 0.2
(c) CSBM: BL, Pade = 0.2
Figure 5: Certifiable robustness for different (G)NNs in Poisoning Labeled (PI.) and Backdoor Labeled (BI) setting.
Acemraay Guin
Ceetifll Accurass Gain
05-
Acrunccy
03.
01
03-
Budget 8
Dodlee
Bodges
Badget
44
-M
100
001
01r Oe di
10 d2 bo
30 02
oiinienss el do to
Adversarial Nodes Pade
Adversrrial Nodes Pade
Advensarial Nodes Pade
Advessarial Nodes Pade
(a) GCN
(b) SGC
(c) APPNP
(d) GIN
Dadget (p [0]
Clrtt Actunry Gain
Coisa
6.5-
8
02-
Budget 5 Gip
+00
-4
0.6
Budget 5
0.0
007
Ceetiied
-6
0.0
601 in o1 63 05
om on 100
05
so
10
Adversarial Nodes Pado
Adversarial Nodes Podo
Adversarial Nodes Pade
(e) GraphSAGE
(f) GCN Skip-PC
(g) GCN Skip-o
Figure Heatmaps of different GNNs for Poison Unlabeled (PU) setting.
J.2 On Graph Connectivity and Architectural Insights
We prosent the sparsity analysis for SGC and APPNP in (a) and (b) of Fig. showing a similar observation to GCN in App. J.2 The APPNP analysis for PU and PL are provided in (c) and (d) of Fig, 7 showing the inflection point in PU but not in PT. Additionally, we show the influence of depth, linear vs ReLU,
regularization and row vs symmetric normalized adjacency in Fig.
Octtifidd Accurccy
Oettiied Accuracy
Lieedd Accarncy
CcrL Aocarocy
08
APINP APPNP
900
002 5.5
APRNN LIX
9
APPSP 1.30
zie
Perturbation Budget (p 00)
Perturbation Budget (P 2)
Pertrratton Budget (p 0c)
Perturbation Budget (P 00)
(a) SGC, PU
(b) APPNP, PU
(c) APPNP, PU
(d) APPNP, PL
Figure 7: (a)-(b): Graph connectivity analysis where ex is op and eq in CSBM model. GCN is provided in
Fig. 4b (c)-(d); APPNP analysis based on a.
33

---

Published in Transactions on Machine Learning Research (06/2025)
Cortified Accurwey
SGC SGU Curtified Accuracy
Cortilie Aucuracy
Coriifie Aucurney 15 T
64-
9.4
OCX
GEN PC
513% Skp-n
9GD
als
Perturbation Budget 6 (p 00)
Pertarbation Budget 6 (p = 00)
Perturbation Budget 8 (p oc)
Porturbation Budget 8 (p = o0)
(a) S in GCN, SGC
(b) Hidden layers I.
(c) Skip connections
(d) Regularization
Figure 8: (a): Symmetric and row normalized adjacencics the choice for S in GCN and SGC. (b): Effect of number of hidden layers L. (c): Linear and relu for the Skip-PC and Skip-a. (d): Regularization C' in GCN. All experiments in PU setting and Pade 0.2.
J.3 Tightness of QPCert
First, we present the tightness of QPCert in Figs. 9 and 10 evaluated with our strongest employed attacks for each setting: For graph poisoning (Fig. D1 APGD employed with direct differentiation through the learning process (QPLayer) for the PU setting Fig. 9b and for the PL setting in Fig. ga For the backdoor attack setting (Fig. 10), first a poisoning allack is carried out with APGD (QPLayer) and then, the respective lest. node is additionally attacked with APGD in an evasion setting. Fig. [ob]shows shows the result for the BU setting and Fig. 10a for the BI. setting. Interstingly, QPCert seems to be more tight in backdoor setting than in a pure poisoning setting. However, this could also be explained by the fact that an evasion attack is easier to perform than a poisoning attack and thus, APGD potentially provided lower upper bounds to the actual robustness than for the pure poisoning setting. Another interesting observation that for the backdoor settings, the rankings of the GNNs regarding certified robustness scems to roughly correspond to the robust accuracies obtained by the backdoor allack.
In Fig. I performing a gradient- crasient-based attack (APGD) using either exact gradients with QPLayer or meta- gradients obtained through MetaAttack's surrogate model is compared. For both the PL (Fig, 11a and PU (Fig. [1b] setting using exact gradients results in a lower upper bound to the robust accuracy (i.e., a stronger attack). Thus, we use the exact gradients from QPLayer to measure the tightness of QPCert. graddggaddentss from MetaAttack are obtained by adapting Algorithm 2 in (Zügner & Günnemaun 2019a) to feature perturbations, through setting maximum number of iterations as the stop criterion and instead of choosing an edge with maximal score, update the feature matrix with the meta-gradient using APGD. In MetaAttack, A trading of the self-supervised with the training loss is set to 0.5. Interestingly, for small budgets, Atlakt can lead to the opposile intended elfect. Exemplary, for GCN in the PL setting with 8 = 0.1, the generalization performance is slightly increased. This indicates that for small perturbation budgets, the meta-gradient of MctaAttack's surrogate model does not transfer well to the infinite-wddth networks. However, for larger budgets, MetaAttack still provides a strong, albeit weaker attack than exact gradients. In Figure Fig. 12 we compare performing the above mentioned gradient- based backdoor attack with the simple backdoor strategy proposed by Xing al. (2024) with a trigger size of 0.5. We observe that Xing et al. (2024)'s 's attack is significantly weaker compared to the gradient-based attack and only starts to reduce accuracy of the models for high attack budgets. This can be explained by several observations For small budbus,ets, the backdoor trigger is often distorted in the backdoored nodes by having to project the perturbation back into the allowed balball and secondly, the attack is simple, static and not adaptive. Concretely, it simply copies certain features to other nodes without considering the attacked model. We want to note that similar to MetaAttack, for small budgets, for BU we can observe for MLP that the change actually results in slightly higher generalization of the model under attack, showing that for small budgets, the backdoor strategy in Xing et al. (2024) is not effective.
34

---

Published in Transactions on Machine Learning Research (06/2025)
Certified Accuracy
Certified Accuracy
0.8
0.8
Jongg bognn lannt
JONCE bomis hound.
0.6
0.6
GON
APPNP
APPNP
0.4
SGC
SOC
GIN
0.2
GrapLSAGE
0.2
GrapISAGE
GUN Skip-PC
GUN Skip-PC
GCN Skip
0.0
MIL
0.
MLP
0.01
0.02
0.05
0.2
0ô1 002
0.05
0.1
0.2
0.5
Perturbation Budget (p 00)
Perturbation Budget ô (p 00)
(a) CSBM:
(b) CSBM: PU
Figure 9: Tightness of our certificate for data poisoning. Both PU and PL with Padv 0.2 evaluated with APGD (QPLayer).
Certified Accuracy
Certified Accuracy
0.8
0.8
0.6
"pper bommy
0.6
upper bout
GCN
GCN
APPNP
APPNP
0.4
SGC
0.4
SGC
GIN
GIN
GraphSAGE
GraphSAGE
GCN Skip
GCN Skip PC
GCN Skap-
GCN Skip-
0.0
0.01
0.02
0.05
0.1
0.2
0.5
0
0.0 0.02
0.05 0.1
0.2
0.5
Perturbation Budget (p 00)
Perturbation Budget 8 (p = 00)
(a) CSBM: BL
(b) CSBM: BU
Figure 10: Tightness of our certificate for backdoor attacks. Both BU and BL again with Padv 0.2.
Robust Accuracy
Robust Accuracy
0.8
0.8
0.6
0.6
QPCert
GIN
QPCert
CIN
MetnArtack
GripUSAGE
Metwdstank
GriphSAGE
GCN
GCN Skip.
Skip-
0.4
APPNP
GCN Skip-o
041
APPNP
GEN--N-- Skip-o
SGC
MIP
SGC
MIP
0.01
0.02
0.05
0.01
0.02
0.05
0.1
0.2
0.3
Perturbation Budget 8 (p= 00)
Perturbation Budget d (p= 00)
(a) CSBM: PL
(b) CSBM: PU
Figure 11: Comparison of performing gradient-based attack (APGD) using either exact gradients using QLLayer or using surrogate meta-gradients using MetaAttack's surrogate model. Both PL and PU with Pade = 0.2.
35

---

Published in Transactions on Machine Learning Research (06/2025)
Robust Accuracy
Robust Accuracy
0.8
0.8
0.6
0.6
0.4
0.4
APCD-based
T GIN
APCI-hased
GIN
0.2
Xing
GCN
GUN Skip- PC
GraphSAGE
0.2
GCN
GUN Skip-PC
APPNP
Skip-
APPNP
Skip-a
0.0
SGC
+ MLP
SGC
MLP
0.01
0.05 0.1
0.02
0.2
Perturbation Budget 8 (p 00)
Perturbation Budget 5 (p 00)
(a) CSBM: BL
(b) CSBM: BU
Figure 12: Comparison of performing gradient- gradient-based backdoor attack versus the simple backdoor attack proposed in Xing et al. (022)).
36

---

Published in Transactions on Machine Learning Research (06/2025)
Certified Accuracy
Cortified Avcuracy
Certified Accuracy
0.8
0.8
0.5-
0.6
0.6
0.6
GPtrt 6--00
QPCptt Dall
QPCes 0.01
0.4
GPteet d 0:00
GPtke d EUOS
0.4
QPCcn Buts
0.4
oe 0.00
0.2-
GPCksi-d
0.2
0.2
GPtsi
QPCen
OPC
0.0
DPA e
0.00
DEA
OuL
002
0.5 0.1
0.2 0.5
0.01
0.02
0,5
D1
022 0.5
002
0,05
0.1
02 05
Adversarial Nodes Fraction E
Adversarial Nodes Fraction E
Adversarial Nodes Fraction E
(a) SGC
(b) GCN
(c) APPNP
Figure 13: QPCert (loo) in comparison to DPA (k- = 20 partitions) for different architectures in the poison- labeled setting on CSBM. QPCert clearly outperforms DPA except for very large f
J.4 Comparing QPCert with Deep Partition Aggregation (DPA)
Technical Details of Adapting DPA to Graphs. To compare QPCert with the mplit-and-majority voting-based certification strategy called Deep Partition Aggregation (DPA) first outlined by (Levine & Feizi
2021), we partition the graph into & subgraphs, by creating k node-partitions P. through hashing. Denote the set of nodes by V, then the node-partitions are created as follows:
P. = {o E V/D mod k ==
(35)
The (induced) subgraph G, corresponding to P, is then created by connecting all nodes in P. that have original edge in G. The certificate is then obtained by training k independent classifiers f. on the h partitions and take the majorily vote over all Sa for a new incoming lest data point. The certificate derived in (Levine & Feizi 2021 then pertains to the majority-voting classifier and not to the individual ft. To make the certificate applicable to transductive node classification, if the test node is not already part of P,, it is added to G after training, where edges from to nodes in P: are added to G3, if they are existing in the original graph G.
Important Differences between QPCert to DPA. We want to note some fundamental differences in the two certification approaches that are important to have in mind when discussing any comparison between them. QPCert is white-box vs DPA being black-box. This means that QPCert derives a certificate for the neural network under question, whereas DPA derives certificate for the majority-ruling classifier and not for the underlying neural networks. Thus, they cortify two different classifiers. As a result, DPA docs not allow to gain insights into the poisoning robustness behavior different neural networks, but a comparison to QPCerl. can illuminate which method under which setting allows for the highest robustness guarantees. Furthermore, QPCert assumes f,-normed adversary whereas DPA assumes that the adversary can arbitrarily perturb controlled data point. As result, DPA would always result in trivial (zero) certified robustness if all nodes can be perturbed, which is the setting we study in Figs. 2a and 2b and where QPCert provides non-trivial certified robustness. Furthermore, if not more is known about the adversary, based on its proof strategy, DPA can provide at most a certificate against & /22-perturbed nodes. This is problematic for semi-supervised learning settings such as node classification, if the underlying graph is sparsely labeled, as then the number of partitions must be set relatively low as there are otherwise no labeled samples to populate the partitions.
Results. Fig. 13 compares QPCert with DPA in the poison-labeles labeled setting. For DPA, we use k 20 partitions it leads to the best roburacy-robustness tradeoff for DPA (see Fig, 14] Fig. 13 clearly highlights that QPCert leads to significantly higher cortified accuracies for 4--bounded adversarics up to strong perturbations 8 & 0.5. This clearly highlights given an e--bounded adversary QPCert significantly outperforms DPA. The high certified accuracy of QPCert also stems from leveraging white- box knowledge not available to DPA. As in percent of the distance between the two class means of the Gaußian from which the node features are sampled, choosing 8 and norm perturbations allows completely recenter the node features in high-probability area of the other class. Here, it is interesting to observe that the bounds of DPA and
37

---

Published in Transactions on Machine Learning Research (06/2025)
Certified Avcuracy
0.5
Cortified Avcuracy
0.8
Certified Accuracy
0.5
DPP
DPA 10
DPA k
A 20
0.0
DPA =
0.5-
DPA 6
0.4
0.4
0.4
0.2
0.0
OUL 1082
0.66
0.1
0.2
0.5
0.01 6
0.02
0.5
D.1
0.2 0.5
001 002
0,06 0.1
02 03
Adversarial Nodes Fraction
Adversarial Nodes Fraction e
Adversarial Nodes Fraction e (c) APPNP
(a) SGC
(b) GCN
Figure 14: Comparing different partition sizes & DPA for different GNN architectures on CSBM. On average, k == 5 leads to 16 labeled nodes per partition, k 10 to 8 labeled nodes per partition, and k 20 to labeled nodes per partition. k 20 leads to the best tradc-off between accuracy and certified robustness.
QPCert roughly overlap. Tf' -> oc, the bounds from QPCert will become trivial (zero). However, 6 >>> would be strong outliers in the training data and could be easily detected and removed.
Further Experimental Details. We test k 10, 10, 20} it leads to 16,8 and 4 labeled nodes per partition, respectively. At 20, the hashing can result in partitions with no labeled samples. Tf this happens, we ignore such partitions in the majority voting classifier. Furthermore, the perturbation model assumed in our work allows a certain fraction of trusted nodes. Thus, applying DPA can provide certificates slightly above the k/2 threshold.
J.5 Results for 2 Perturbation Budget
We present the results for p perturbation budget evaluated CSBM and all the GNNs considered. We focus Poison Unlabeled setting. Fig. 15 show the results of the certifiable robustness for all GNNs and the heatmaps showing the accuracy gain with respect to MLP is in Fig. 15 All the results are in identical to = oc setting and we do not see any discrepancy.
Crrido ghin
81
Cerliiel Ancurscy Goin
Certibedd Accuracy
Budget 8 1p
Budget 8 ip
01
ARPST
Budgot 6
GRG GUN Sep-s
BI
0.e
8.6
-1
80
8.01
16
60
MBP
zic eiz
010 cat was ca na
cin ua uós ni na
alo et uz
Perturbation Budget (p
Adversarial Nodes Pude
Adversorial Nodes Pulr
Adversarial Nodes Pode
(a) CSBM: PU
GIN
(c) GraphSAGE
(d) GCN
Cariided Acominy Cain
Cariided Acotmry Cain
ALL
Cantifee Acourrry Clun
81
Cuttiadd Gain
0.5-
033
80
45
Dudget 6 (p
-01
Budget 8 (p
09
Budget
000
Budget
ere
602-
w82-
02
auc
8m
6o1 o0r rup 01 05 05
601 par e1 an 85
06 0s9 #1 e4 65
amatenie e1 63 05
Adversarial Nodes Pade
Advensarial Nodes Pade
Advensacial Nodes Paie
Adversarial Nodes Paie
(e) SGC
(I) APPNP
(g) GCN Skip-PC
(h) GCN Skip-a
Figure 15: (a): Certifiable robustness for different (G)NNs in Poisoning Unlabeled (PU) for = 2. (b)-(h): Certified accuracy gain for heatmap for all GNNs. All experiments with Poisoning Unlabeled (PU) and
Pade 0.2
38

---

Published in Transactions on Machine Learning Research (06/2025)
J.6 Results for Perturbation Budget
Similar to p 2, also present the results for perturbation budget evaluated CSBM and all the
GNNs considered for Poison Unlabeled setting in Fig. I6 All the results are in identical to p oc setting and we do not see any discrepancy.
Certifeed Accuray
100
Corrili antriricg gain
Cartifod 1)
(p=
02
Budget (p
DCC SDC
0.1
01
51
6.44
DIS
Budges
-02
Budget
GUN Sipu
em
GON Sup-o
00
D6
Pertarbation Budget (p = 1)
Adversarial Nodes Podo
Adversarial Nodes Pade
Advessriia Nodes Pade
(a) CSBM: PU
(b) GCN
(c) SGC
(d) APPNP
Dodget Up 1]
1]
Up
Budget 1p
0.3
54
0.8-
Budget
0.8-
Budget
4.8-
6ub
110
ale tub ca
din tae na us
bin tazuis us
Mu us db Advessarial Nodes
Adversarial Nodes
Adversarial Nodes
Adversarial Nodes
(e) GCN PC
(f) GCN Skip-a
(g) GIN
(h) GraphSAGE
Figure 16: (a): Certifiable robustness for different (G)NNs in Poisoning Unlabeled (PU) for = 1. (b)-(h): Certified accuracy gain for heatmap for all GNNs. All experiments with Poisoning Unlabeled (PU) and Pade 0.2.
J.7 Comparison Between oc and 2
We provide a comparison bet ween p = oo and perturbation budget, showing that = 2 is lighter than oc for the same budget as expected.
Certified Accuracy
0.8
0.6
0
0.4
P=2
GCN
APPNP
0.2
SGC
MLP
0.0
0.01 0.02
0.05 0.1
0.2
0.5
Perturbation Budget
Figure 17: Comparison between p = oo and p for Poison Unlabcled setting. Padv 0.2.
39

---

Published in Transactions on Machine Learning Research (06/2025)
J.8 Comparison to Common Poisoning Defenses
In Fig. 18 compare two common poisoning defenses namely GNNGuard (Zhang & Zitnik 2020 and ElasticGNN [Luu et al. 2021) with the certified accuracy provided by QPCert. While the accuracies provided by a defense are not certified accuracies (i.c., they are only upper bounds to the true robust accuracy) and hence, can only be compared partly with the certified accuracy which represents a true lower bound to the robust accuracy. However, a comparison is still interesting as allows to answer the question, how big the gap between the best-certified accuracy the robust accuracy provided by defenses is and if we could even get certified accuracy result comparable to poisoning defense's accuracy. Interestingly, Fig. I8 shows that for small to intermediate budgets, the certified accuracy of infnite-width GCN as provided by QPCert is higher than the robust accuracy provided by the defense basclinos. This can be explained by the fact that even ElasticGNN and GNNGuard show lower base clean accuracy despite significant hyperparameter tuming (experimental details see below paragraph) paired with a few very brittle predictions. We hypothesize that this is due the difficult learning problem CSBM poses (despite being a small dataset) paired with the fact that both poisoning defenses have GCN-like base models where the graph propagation scheme adapted to be more robust. poisoning while potentially trading off clean accuracy.
Both poisoning defenses are trained using the non-negative likelihood loss and the ADAM optimizer following Zhang & Zitnik 2020). GNNGuard uses 2-layer GCN baseline model and hyperparameters are scarched in the grid: (i) number of filters {8, 16, 32), (ii) dropout (0, 0.2, 0.5), (iii learning rate (0.01, 0.001), }, (iv) weight decay (5e - 3, le - 3,5e 5e 4, le 4} over seeds resulting in 720 models. For ElasticGNN the hyperparameter grid reported in Liu et al. (2021) is explored over 10 sceds resulting in 11520 models due ElasticGNN having more hyprpparameters to are attacked using MetaAttack adapted to feature perturbations done in App. T.3 The infinitewiddth GCN is attacked using the exact gradient obtained from the QPLayer implementation.
It's hidden layer size is fixed 32. Both baseline defenses
Accuracy
0.6
0.4
Robust Acc.
Cortified
0.2
GCN (oo-width)
ElastieGNN
0.0
GNNGward
0.01
0.02
0.05
0.1
0.2
0.5
Perturbation Budget 8 (p
00)
Figure 18: Comparison of different poisoning defenses with the certified accuracy obtained by QPCert CSBM.
K Additional Results: Cora-MLb
K.1 Evaluating QPCert
Fig.
1aa shows the certified accuracy on Cora-MLb for the BL settings for Peert 0.1. Figs. 19b to
19d
and 20 show a detailed analysis into the certified accuracy difference of different GNN architectures for PU
setting for Peert 0.1.
40

---

Published in Transactions on Machine Learning Research (06/2025)
Certited Accurocy
Contited alretoc griss
APPAT
Buiged
Cor Biol
GN O3% Sieper
12
on
180
61
-63
Pertuubation Budges 5 (p
Artommsttal
pus
(a) BL, Pade =
(b) GCN
(c) SGC
(d) APPNP
Figure 19: (a) Backdoor Labeled (BL) Sctting. (b)-(d) Hcatmaps of GCN, SGC, and APPNP for Poison
Unlabeled (PU) setting on Cora-MLb with Pade 0.1.
Cortieed galn
835
Dalaet
ti 03 45 Advrauid Nodea Roe.
dis 61 da
012
die ols da da Advanszza Nodee Pus.
Adverasial Nodes
Advenaral Nodaa Bac
(a) GCN Skip-a
(b) GCN Skippe
(c) GraphSAGE
(d) GIN
Figure 20: Heatmaps of GCN Skip-a, GCN Skippe, GraphSAGE, and GIN for Poison Unlabeled (PU) sctting on Cora-MLb with Pade 0.1.
K.2
APPNP
Fig.
shows that the inflection point observed Fig.
4c
not observed in the other scttings.
Cortified Accuracy
1.0
Certified Accuracy
3.0
APPNP 0.1
Certified Accuracy
APPNP 61 APPNP
0.8
APPNP 0.3
06-
0.0
APENE
0.6-
APPNP 0.1
MLP
MIP
APPNP o 0.2
APPNP
0.2-
APPNP
0.2
0.2
MLP
0.0
002
0.01
002
0.6 0.1
0.5
001
0.02
0.5 01
0.2
Perturbation Budget 8 (p 2)
Perturbation Budget 5 (p = 2)
Perturbation Budget 5 (p 2)
(a) PT.
(b) BL.
(c) BU
Figure 21: Cora-MLb, all settings with Pade = 0.05.
K.3 Symmetric vs. Row Normalization of the Adjacency Matrix
41

---

Published in Transactions on Machine Learning Research (06/2025)
Certified Accuracy
Certified Accuracy
088
0.5
0.8
GCN Rom
CCN Row.
0.4
Sym
0.1
GCN Synn
SGC
SGC
0.2
SGC
MLP
MLP
0.n
0.22
005 0.1 02
022 0.5 Perturbation Budget (p = 2)
0ot 0.12
00s 0.1
Perturbation Budget 5 (p = 2)
(a) S in GCN, SCC, PU
(b) S in GCN, SGC, PL
Figure 22: Influence of symmetric and row normalized adjacency in GCN and SGC for poison unlabeled and poison labeled settings.
K.4 Results on Adversary
Fig. 23 shows the cert certifiable robustness to adversary on Cora-MLb datasel. The observation is consistent
to the CSBM case.
Ceriited Accurary
Coriffed Avcanicy
Ceriifed Ascuracy
Ccriified Aocuray
APONP
DIN DIS EOPENT
CASA ERppor
CKS tap-Pt MIP
nix
Perturhation Budget (p
Porturaation Budget (p
Perturbation Budget
Perturbation Hudget
(a) PU Pade = 0.1
(b) PL Pado
(c) BU Pade 0.1
(d) BL Pade 0.1
Figure 23:
Cora-MLb results for PL, PU, BI. and BU under p = perturbation.
L Additional Results: Cora-ML
For Cora-ML we choose 100 test nodes at random and investigate in Fig. 24a the poison labeled (PL) setting with a strong adversary Pade 1.0 for GCN, SGC and ML.P. It shows that QPCert can provide non-trivial robustness guarantees even in multiclass settings. Fig, 24b shows the results for poison unlabeled (PU) and Pade = 0.05. Only SGC shows better worst-case robustness than MLP. This, together with both plots showing that the certified radii are lower compared to the binary-case, highlights that white-box certification of (G)NNs for the multiclass case is a more challenging task.
0.5
GCN
0.
SGC
Coriified Accunay
MLP
Certified Aceuray
0.7
APPXP
Skip-o
0.6
CCN Skip-PC
GrapASAGE
0.5
GUN
GIN
0.4
SGe
MLP
0,3
GapASAGE
0.0
0,2
0.6
Gil
Perturbation budget 5 (p 2)
Perturbation budget (p
(a) Cora-ML PL Prddo 1.0
(b) Cora-ML PU Pade 0.05
Figure 24: Cora-ML results for PL and PU.
42

---

Published in Transactions on Machine Learning Research (06/2025)
M Additional Results: WikiCSb
shows for the poisoned unlabeled setting that until certain perturbation budget, GNNs lead to higher certified accuracy an MLP. However, Padv 0.02 it also shows that the certified accuracy of GNNs can be highly susceptible even to few perturbed nodes. Figs. 26b to 26d and 27 show a more detailed analysis into the certified accuracy difference different GNN architectures for PU setting for Peert = 0.02. We want to note the especially good performance of choosing linear activations (SGC). Fig. 25b that all GNNs achieve better certified accuracy as MLP. Lastly, Fig. 26a
Fig. 25a
shows the certified accuracy on WikiCSb
for the BL settings for Poert 0.1.
Certified Accuracy
Certified Accuracy
1.0
0.6
11.-
0.4
SGU
0.4
SUC
GraphSAGE
GrapiNAGE
GCN SkipPC
0.2
GCN Skips
GUN
0.0
0.01
0022
0.00
0.1
0.2
0.02
0.22
0
0.2 055
Perturbation Budget (p 2)
Perturbation Budget 6 (p
2)
(a) WikiCS: PU
(b) WikiCS: BU
Figure 25: Certifiable robustness for different (G)NNs in Poisoning Unlabeled (PU) and Backdoor Unlabeled
(BU) setting with Pade = 0.02 for WikiCSb.
Certifted Aveurocy
Dullet 0
Bustet lo
Artour cal sefect
-03
8m
HUP
ela di da Artomsottal Nodio
642 LM
di sdo 42 od
Perturatton Budges (p 2)
Atheraraal Nodie Pack
Advenorial Norkes pus.
(a) BL, Pade = 0.1
(b) GCN
(c) SGC
(d) APPNP
Figure 26: (a) Backdoor Labeled (BL) Setting. (b)-(d) Heatmaps of GCN, SGC, and APPNP for Poison
Unlabeled (PU) setting on WikiCSb with Pade = 0.02.
ME
0.
0.5
Cortified accurary gain
0.5
0.2
-12
0.2
Budger (p
-17
-02
000
Budges
-B0
87
4.7
dnt nie uis da 02 ub Adversorial Nodes fan
0.2 062
I1.
n1
0.5
sutl ouz cui
01 222 0
Adversorial Nodes Pads
Adversariaal Nodes pude
(a) GCN Skip-a
(b) GCN Skippe
(c) GraphSAGE
Figure 27: Heatmaps of GCN Skip-a, GCN Skippe, GraphSAGE, and GIN for Poison Unlabeled (PU) setting on Wi with Pado 0.02.
43

---

Published in Transactions on Machine Learning Research (06/2025)
N Computational Limits of QPCert
To understand the computational limits of QPCert, we evaluate the certification runtime synthetic graphs generated using the CSBM with 1000 and 10000 nodes. For each graph, we vary the number of labeled nodes per class as {10, 20, 50, 100, 200, 500). Thereby, we effectively simulate the semi-supervised learning setting. Note that in the case of 1000 nodes, 500 labeled nodes per class leaves no test node, thus we do not evaluate this setting. We compute the average runtime certify single test node, computed over 50 test nodes and random seeds as shown in Fig. 28
1000 nodes
Certification Time (sec)
10000 nodes
10a
10
10a
10-3
10
20 Number of labeled nodes per class
50
100
200
500
Figure 28: Certification time measured in seconds for graphs of sizes 1, 000 and 10, 000 nodes with varying number of labeled nodes per class.
Importantly, Fig. 28 shows that the computational complexity of QPCert is not determined by the total number of nodes in the graph, as evidenced by the difference in time between 1000 and 10000 nodes is within the standard deviation. It rather scales near-exponentially with the wamber of labeled nodes, which is typically small practical semi-supervised settings. As a result, QPCert remains tractable even on significantly large graphs, provided the number of labeled nodes remains moderate. This type of scaling bchavior may be different to other approaches for poisoning certification such as the spli--and-majorily voling approach, whose computation time depends the total size of the graph and the number of partitions, but not necessarily the number of labeled data. However, all approaches on poisoning certification independent of the data domain have some computational bottleneck and are thus, currently limited to small to medium-sized datasets and we refer to the references in Sec. for more details.
44

---

Published in Transactions on Machine Learning Research (06/2025)
O Further Discussions
O.1 Applicability to Commonly Studied Perturbation Models and Attacks
QPCert applies to any poisoning or backdoor attack that performs ep-bounded feature perturbations. As such, QPCert is directly applicable to clean-label (graph) backdoor attacks as proposed by Turner et al. (2019) and Xing al. (2024), and clean-label poisoning attacks such Huang et al. (2020) and Geiping al. 2021]. It. is not directly applicable to poisoning of the graph structure performed by MetaAttack Zügner & Günnemann, 2019a)- However, the MetaAttack strategy can be casily adapted to poison node
features done in App. J.3 and we discuss the challenges to extend QPCert to structure perturbations in App. 0.2 The backdoor attack proposed by Dai et al. (2023) changes the node features and training labels jointly and thus, our method is applicable if the training labels will be kept constant or the poisoned nodes are sampled only from the class, the training label should changed to. Similar, Xi et al. (2021) develops a backdoor attack that changes the features and graph structure jointly and thus, QPCert is not applicable given the graph structure changes.
O.2 Certifying Against Graph Structure Perturbations
In the following, we discuss how to approach certifying against poisoning of the graph struct ure and the open challenges that arise in the process. To certify against poisoning the graph structure, again Eq. (2) has to solved but now, the adversary A can change the graph structure instead of the node features, meaning the optimization in Eq. (2) performed w.r.t. the graph structure matrix S and thus, reads
min Latt (0, S. t. SEA(S) A 0 E arg L(0', 8
(36)
with S A(S) representing the perturbed graph structure matrices constructable by the adversary and -5, x). Indeed, will be possible reformulate this problem into a single-level problem similar the description in Sec. 3 While in theory, QPCert Theorem 3.3 also applies to structure perturbations, the 3.1 does result in loose bounds for structure perturbations,
untrusted node will always result in lower bound in the respective adjacency matrix entry of 0 and an upper bound of thus, spanning the whole space of possible entries.
bounding strategy from Sec. 3.1
To overcome this, one can approach certifying graph structure perturbations by including the NTK computation into the optimization problem with the drawback that each type of GNN architecture will require slight adaptations of the optimization problem depending on its corresponding NTK. Assuming that the chosen model is an I, 1 layer GCN (the formulation be easily extended to arbitrary layers, App. C.3 the bilevel optimization problem reads as follows
m maa s.l. 3 A(S)S) A a a S(Q)
min S.S.Q.E, E, E, E.
sgu (fx) Σ
(37)
Q = S @ ET)ST + +2 ES
(38)
Σ, = ŠXXŠ"
(39)
Σ, ŠE
(40)
E = C
E
(FF)
(41)
F0,10,E,)
E =
E
(((F)((F))]
(42)
(0,
E 1
(43)
45

---

Published in Transactions on Machine Learning Research (06/2025)
This (non-linear) bilevel problem can be transformed into single-level problem as described in Sec. 3
the inner-level problem E S(Q) is the same as in Eq. 3 and the same strategy can be applied to linearly model the resulting constraints from the KKT conditions. However, a crucial difference to Eq. 3 are the
additional non-linear constraints arising from optimizing over the NTK computation. Eqs. 338 to (40) are
multilinear constraints that can be reduced to bilinear constraints by introducing additional variables as follows (for brevity, again writing the problem in its bilevel form):
min sgn( Qa s.t. Se A(S) a ((Q)
(44)
Q= H H₂
(45)
H1= = ΣΙ ④ E
(46)
H H
(47)
H SH
(48)
H2 Σ₂ E2
(49)
Σ, M
(50)
M = SX
(51)
M2= = ESST
(52)
Σ== = SM₂
(53)
E - Co P~,
[F)
(54)
E F,,
E
[F(F)
(55)
E2 1nxn
(56)
where the optimization over the same variables as the previous problem, and additionally the variables H1, Hi H", H2, M1, and M2. Eqs. (45) and (51) are linear constraints, the rest of the newly introduced constraints represent bilinear terms. The same bilinearization strategy can be applied given the NTK computation over arbitrary layers. The remaining non-linear and non-bilinear terms are Eqs. (54 and (55) They can be solved in closed-form resulting in relatively well-behaved functions as shown in App. E. Thus, a convex relaxation of the expectation terms can be derived by e.g., choosing linear functions that lower and upper bound the expectation terms.
Assume for now that one can linearly model Š A(S), this can be achieved by e.g., choosing the adjacency matrix without normalization as graph structure matrix done by Hojny et al. (2024). Then, the crucial question is:
How to effectively solve the orising bilinear problem??
In particular, the bilincarities arise in both, the constraints and objective, and thereby this contrasts e.g., with Zügner & Günnemann (2020) who only have to deal with bilinear objective but have linear constraints.
The problem can be slightly simplified if S is chosen be the unnormalized adjacency matrix, as then any S is discrete and thus Eqs. (47, (48) and (2)) represent multiplications of continuous with discrete variable and thus, can be linearly modeled using standard modeling techniques. However, the objective and Eqs. (46), (4 and (50) remain products of continuous variables and thus, can fundamentally not be modeled lincarly. One polential way to tackle this, is to use techniques of convex relaxations of bilinear functions as e.g., the so called McCormic envelope (McCormick, 1976). However, it is not clear common bilinear relaxation techniques can scale to problems of the size necessary to compute practical certificates for machine lcarning datasets, nor it clear if the relaxations introduced in the process result in tight enough formulations yield non-trivial cert ificates. This is complicated by the fact that problems that studied in the bilinear
46

---

Published in Transactions on Machine Learning Research (06/2025)
optimization literature often significantly smaller than the problem size can expect from certifying graph structure perturbations. However, it is not unlikely that further progress in bilinear optimization will make this problem tractable.
We want to note that linearly modeling Š A(S) by choosing an unnormalized adjacency matrix as the graph structure matrix results in a restriction of possible architecture to certify. could be possible to adapt Zügner& & Günnemann (2020)'s 's modeling technique for the symmetric-degree normalized adjacency matrix they use to certify finite-width GCN to the above optimization problem without increasing its difficulty it is already bilinear.
O.3 Practical Implication of Feature and Structure Perturbations
Both feature and structure perturbations find complementary applications real-world scenarios. In particular, important application areas for graph learning methods with adversarial actors are fake news detection (Hu et. al. 2024) and spam detection (Li et. al. 2019). Regarding fake news detection, feature perturbations can model changes to the fake news content to (controlled) user account comments and profiles to mislcad detectors (Hu et al. 2024 Lc ct al. 2020). Structure perturbations allow to model a change in the propagation patterns (e.g,, through changing a retweet graph) (Wang el al. 2023 The qualitative difference in the application feature compared to structure perturbations is similar for spam detection. Here, feature perturbation can model spammers trying to adapt their comments to avoid detection (Li et al., 2019 Wang al.) 2012p. In contrast, structure perturbations can model behavioral changes in the posting patterns of spammers imitate real users (Soliman Girdzijuskas) 2017 Wang al. 2012
0.4 QPCert for Other GNNs
While our analysis focused on commonly used GNNs with and without skip connections, QPCert is broadly applicable to any GNN and NN with well-defined analytical form of the NTK. The following challenges and considerations have be taken into account when extending QPCert other architectures:
1. NTK-network equivalence: The equivalence between the network and NTK breaks down when the network has non-linear last layer or bottleneck layers [Liu et al. 2020 Consequently, our certificates do not hold for such networks.
Analytical form of NTK: Deriving a closed-form expression for NTK is needed to derive bounds on the kernel. This might be challenging for networks with batch-normalizations or advanced pooling layers.
3. Bounds for the NTK: Ensuring non-trivial certificates requires deriving tight bounds for the NTK. Depending on the NTK, additional adaptation of our bounding strategy may be necessary.
Most message-par nessage-passing networks satisfy these criteria, making QPCert readily applicable to wide range of architectures. However, we note that the equivalence between the network and NTK becomes difficult to establish when the training optimization procedure is changed to any other momentum-based or sccond-order gradient descent, or adversarial training where the optimization is minimization of the maximum adversarial loss. Specifically, the bounded parameter evolution required for the NTK equivalence as discussed in App. D is hard to guarantec and can significantly deviate from initialization even the infinito- width setting.
0.5 Comparison to Sosnin et al. (2024)
develops a gradient-based cortificate for data poisoning for an MLP called Abstraci Gradient Training (AGT). To compare QPCert with their method, we use the halfmoon dataset from Sosnin et al. (2024) and investigate the poison labeled setting with Pade = in Fig. 29 where a trivial certificate would result in no certified accuracy. Fig. 29 shows that our method allows to certify over one order of magnitude larger perturbations than using AGT, highlighting that QPCert is likely significantly tighter. We want to note that AGT gets less tight the more epochs are used for training.
As mentioned in Sec. 5 concurrent work (Sosnin et al. 2024
47

---

Published in Transactions on Machine Learning Research (06/2025)
1.0
Certified Accuracy
0.6
0.2
MLP (QPCart)
MLP (AGT)
0.0
0.001
0.002
0.005
0.01
0.02
0.05
Perturbation Budget 5 (p = 00)
Figure 29: Certifiable robustness of an MLP as provided by QPCert compared to AGT from Sosnin et al. (2024 for the halfmoon dataset in a poison labeled (Pude=1) setting.
Thus, Sosnin et. al. (0024) Irain using only 1-4 epochs and the MLP for AGT in Fig. 29 is also only trained using four epochs following their work. In contrast, QPCert certifies network trained to convergence, Note that AGT certifies finite-width network, whereas QPCert certifies an infinite-width network.
48


Reviews:
[{"review_id": "I9ks2MNMLH", "reviewer": "Reviewer_JJcv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The problem of providing certificate for data poisoning attacks are important. \n2. The provided bound remains tight for smaller perturbation budget.\n\n\nWeaknesses:\n1. The scalability of the approach is still in question. The tested benchmark datasets are still of small size and empirical data poisoning attacks and adversarial examples are tested on much larger dataset with many more nodes and edges.\n2. The baseline did not consider some simple adaptations of certifiable defenses from the Euclidean data. For example, the split-and-majority voting based certifiable methods should also be applicable to the setting considered in this paper. One can partition the nodes into different subsets, and ignore the potential connection between different subsets, and then apply the certifiable method. Even though their certificate is for arbitrary manipulation, a much stronger threat model than what is considered in this paper, it still still be interesting to see what is their gap at smaller poisoning ratios and how the gap becomes larger as the poisoning ratios increase. \n3. Comparison to the approach of Sabanayagamet al. (2023) should also be added to the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the certifiable robustness of graph neural networks against clean label data poisoning attacks and backdoor attacks that add bounded perturbation on the node features. The main idea is to use Neural Tangent Kernel to represent neural network as soft-margin SVMs and formulate the bi-level optimization as mixed integer programing problem and solves the relaxed version of the problem to provide certificate. The computed approximate certifiable bounds on the benchmark datasets show that the certifiable bounds are relatively tight for smaller perturbation magnitude, but the gap between the tested actual poisoning attacks and certifiable bounds become larger for larger perturbation size.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Include results of adaptation from Euclidean data and at least the majority voting based method should be included. \n2. Include the comparison to the method from Sabanayagamet al. (2023) as a baseline, for settings where both the baseline and the proposed approaches apply. \n3. If possible, should evaluate on larger datasets, and see what size of data starts to give the computational limit. Note that, other baselines from the Euclidean data may not have such computational bottleneck. \n4. Discuss how the certificate changes when arbitrary feature manipulations are allowed for poisoning. Will this certificate be trivial in this case?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AR2xneEUHg", "reviewer": "Reviewer_tdW2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has the following **Strengths**:\n- This paper is well-written, and the presentation is clear.\n- It is the first white‑box poisoning (or backdoor) certificate for graph neural networks. It can defend against both training‑time and test‑time corruption.\n- Extensive theoretical analysis and experimental results validate the effectiveness of the proposed method.\n\nThis paper has the following **Weaknesses**:\n- The framework is restricted to feature perturbations and is not effective against attacks based on graph structures.\n- The process may require a significant amount of time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present QPCert, a novel white-box certification framework that provides provable guarantees for graph neural networks (GNNs). It can also be applied to other neural networks. It can protect against node feature-based attacks from both data poisoning attacks and clean-label backdoor attacks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think this paper is of good quality. I only have a few minor questions/suggestions:\n1. Would it be possible to include a notation table to improve clarity?\n2. In Appendix H.3 Hardware, it says, \"The time to certify a node depends on the size of MILP as well as the structure of the concrete\nproblem\". Could you please add some figures or tables to show how it impacts the time? I wonder how the time needed will change.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y7nYmNTCB6", "reviewer": "Reviewer_Qbt7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. This paper considers the influence of graph structure when applying NTK to analyze GNNs. This modeling choice is theoretically thoughtful and non-trivial.\n2. In the experiments, the authors evaluate different perturbation rates, which provides a more comprehensive understanding of worst-case robustness.\n\nCons:\n\n1. The evaluation is limited to small to medium-sized graphs (≲ 5,000 nodes), such as Cora-ML (3K nodes), WikiCSb (4.6K nodes), and synthetic CSBM (200 nodes). In contrast, real-world graphs often contain 10,000+ nodes and exhibit highly dynamic structures. The scalability of QPCert to such scenarios remains unclear.\n2. The method assumes that the attacker can perturb node features during training. However, if the attacker has access to this extent, it raises the question: why not perform the attack at test time instead? Test-time attacks are typically harder to detect and do not rely on access to the training pipeline. The paper would benefit from a clearer motivation and contextualization of the threat model in this regard.\n3. If a GNN is adversarially trained before applying QPCert, it may alter the training dynamics and, consequently, the resulting robustness properties. However, QPCert’s current theoretical framework assumes NTK dynamics under standard (non-robust) training. As such, it is unclear whether QPCert can still provide valid or tight certificates for adversarially trained models. This limitation is worth acknowledging and exploring.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is not only a certification framework grounded in NTK theory and MILP solvability, but also a methodological study for reasoning about training-time robustness in graph learning. It carves out a space between theoretical formalism and practical vulnerability — a space increasingly relevant in a world where machine learning systems are deployed in adversarial environments but rarely endowed with certifiable defenses.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Discuss the scalability limitations more explicitly, and clarify whether QPCert can be extended to larger, real-world graphs (10,000+ nodes).\n- Refine the threat model justification—specifically, explain why training-time perturbations are prioritized over potentially stealthier test-time attacks.\n- Clarify whether QPCert can still provide valid certificates for adversarially trained models, or acknowledge this as a limitation.", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, from the review process all reviewers agreed that problem tackled is interesting and relevant, and the presented results are demonstrably sound. Based on the reviewers' unanimous recommendation, the AE will recommend acceptance of this paper.

Moving forward, the applicability of the proposed method to structural perturbations remains an avenue for future exploration. The authors have already initiated this discussion in Appendix O.2 and the conclusion, and they are encouraged to delve deeper into these considerations as a natural progression of this line of research.
Decision: Accept (poster)