betaFeedback

WorksComputer Science

Certifying Graph Neural Networks Against Label and Structure Poisoning

Abstract

Robust machine learning for graph-structured data has made significant progress against test-time attacks, yet certified robustness to poisoning - where adversaries manipulate the training data - remains largely underexplored. For image data, state-of-the-art poisoning certificates rely on partitioning-and-aggregation schemes. However, we show that these methods fail when applied in the graph domain due to the inherent label and structure sparsity found in common graph datasets, making effective graph-partitioning difficult. To address this challenge, we propose a novel semi-supervised learning framework called deep Self-Training Graph Partition Aggregation (ST-GPA), which enriches each graph partition with informative pseudo-labels and synthetic edges, enabling effective certification against node-label and graph-structure poisoning under sparse conditions. Our method is architecture-agnostic, scales to large numbers of partitions, and consistently and significantly improves robustness guarantees against both label and structure poisoning across multiple benchmarks, while maintaining strong clean accuracy. Overall, our results establish a promising direction for certifiably robust learning on graph-structured data against poisoning under sparse conditions.

Introduction

Graph Neural Networks (GNNs) are highly susceptible to adversarial perturbations in their input graph applied at test or training time ([44]; [4]). Subsequently developed empirical defenses are at the continual risk of being rendered ineffective by more sophisticated

ways to choose adversarial perturbations ([14]; [27]). This motivates the development of robustness certificates, which provide provable guarantees about the stability of predictions under worst-case data perturbations, allowing to rigorously assess and mitigate adversarial vulnerabilities. While significant advances in providing such provable guarantees for GNNs against test-time attacks have been made ([8]; [9]), certifying robustness of GNNs against data poisoning, where an adversary can manipulate the graph structure ([43]) or node-labels ([23]) at training time, remains largely underexplored.

The most effective approaches to derive poisoning robustness guarantees in the image domain rely on partitioning the training data, learning separate (base) classifiers, and aggregating predictions (e.g., via majority vote) ([18]). However, we demonstrate that these methods fail when directly applied to common graph learning tasks such as node classification. In particular, we find that the core challenge is sparsity: both labels and graph structure are often too sparse to provide effective training signals under data partitioning, leading to poor performance for label certificates and vacuous robustness guarantees for structure poisoning. This raises a critical question:

How can we effectively analyze and guarantee the trustworthiness of GNNs in the presence of structure and label poisoning, while maintaining their utility?

In this work, we address this challenge by introducing a novel semi-supervised learning framework called deep Self-Training Graph Partition Aggregation (ST-GPA) that successfully overcomes the sparsity problem and enables effective poisoning certification of GNNs against structure and label poisoning (see Figure 1). In particular, our method enriches the subgraphs created through partitioning the original graph, with synthetic data generated using carefully designed self-training approaches. Self-training is a concept from semi-supervised learning ([2]) that refers to training a model on its own predictions to expand the leverageable training set. Concretely, for each sparsely labeled graph partition, our method efficiently generates synthetic (pseudo) labels, expanding the available node-label set. In a similar spirit, for each sparsely connected subgraph, our method generates synthetic edges through solving a link prediction problem, endowing each subgraph with a more informative structure. Then, by training GNNs as base classifiers on these enriched subgraphs and aggregating their outputs using a majority vote, we obtain strong certificates for label poisoning, structure poisoning, and joint label-structure poisoning. Our contributions are:

Deep Self-Training Graph Partition Aggregation (ST-GPA)

Figure 1. Deep Self-Training Graph Partition Aggregation (ST-GPA). To certify against structure poisoning, the graph’s edges are partitioned. The resulting set of sparse graphs are enriched with informative pseudo-edges and then, an ensemble of GNNs is trained on the partitions. To certify against label poisoning, the graph’s node labels are partitions, and the resulting sparsely labeled graphs enhanced with pseudo-labels, before training the ensemble. To jointly certify against both poisoning, ST-GPA partitions both the edges and labels and adds pseudo-edges and pseudo-labels.

  • (i) In § 3 we generalize the partition-and-aggregate paradigm prevalent in the image domain to derive poisoning robustness certificates to non-i.i.d structured data. Then, in § 4, we identify and characterize a failure mode of certifying robustness against poisoning using this paradigm on graph-structured data rooted in the label and structure sparsity found in common graph datasets.

  • (ii) In § 5 we propose deep Self-Training Graph Partition Aggregation (ST-GPA), a novel semi-supervised learning framework that augments partitions with carefully obtained pseudo-labels and/or synthetic edges, overcoming the sparsity problem when partitioning graph-structured data.

  • (iii) ST-GPA is the first effective certificate against structure and label poisoning for node classification with graph neural networks. In particular, we set a new state-of-the-art certified poisoning robustness for GNNs across multiple benchmarks, while being efficient and obtaining competitive clean accuracies (see § 7).

Overall, our work highlights the importance of self-training in certifying poisoning robustness of GNNs and lays the foundation for future work against training-time attacks in the graph domain. We believe that our insights on improving partition-based certification using self-training may be of independent interest beyond graph learning.

Preliminaries

We consider an attributed, undirected graph G⊆GG \subseteq\mathcal{G} described by a feature matrix X∈Rn×mX \in\mathbb{R}^{n \times m} of mm-dimensional features for nn nodes and a set of edges E⊆{{i,j},i,j∈[n]}\mathcal{E} \subseteq\{\{i,j\}, i,j \in[n]\} with [n]={1,…,n}[n] = \{1,\ldots,n\}, where two nodes ii and jj are connected if and only if {i,j}∈E\{i,j\} \in\mathcal{E}, and each node belongs to one out of CC classes with Y=[C]\mathcal{Y} = [C]. We study semi-supervised transductive node classification. That is, the full graph G=(E,X,y)G = (\mathcal{E},X,y) is available during training but its nodes are only partially labeled. This is modeled with a label vector y∈(Y∪{−1})ny \in(\mathcal{Y} \cup\{-1\})^n, where entry yi∈Yy_i \in\mathcal{Y} indicates the label of node ii, and yi=−1y_i = -1 means the node is unlabeled. We model GNNs as functions f:G→Ynf : \mathcal{G} \to\mathcal{Y}^n, and collect the labels in the graph in the set Y=⋃v∈Vlabeled{(v,yv)}\mathcal{Y} = \bigcup_{v \in V_{\mathrm{labeled}}}\{(v,y_v)\} and the node attributes in the set X=⋃v∈V{(v,Xv)}\mathcal{X} = \bigcup_{v \in V}\{(v,X_v)\}. We write graph datasets as D=(E,X,Y)\mathcal{D} = (\mathcal{E},\mathcal{X},\mathcal{Y}).

Perturbation model. In this work, we study two types of poisoning attacks on graph-structured data: label flipping and structure perturbations. To quantify the strength of an attack, we define attack budgets rlr_l, rsr_s, which bound the number of allowed modifications to labels and structure, respectively. We model the set of possible poisoned graphs G~\widetilde{G} as a ball centered around the clean graph GG:

Brl,rs(G)={G~=(E~,X,y~)∣δ(y~,y)≤rl, Δ(E~,E)≤rs}(1)\mathcal{B}_{r_l,r_s}(G) = \left\{\widetilde{G} = (\widetilde{\mathcal{E}},X,\widetilde{y}) \mid\delta(\widetilde{y},y) \le r_l,\ \Delta(\widetilde{\mathcal{E}},\mathcal{E}) \le r_s\right\} \tag*{(1)}

where Δ(X,Y)=∣(X∖Y)∪(Y∖X)∣\Delta(\mathcal{X},\mathcal{Y}) = |(\mathcal{X} \setminus\mathcal{Y}) \cup(\mathcal{Y} \setminus\mathcal{X})| is the symmetric difference of two sets, and δ(y~,y)=∑i=1n1y~i≠yi\delta(\widetilde{y},y) = \sum_{i=1}^{n}\mathbf{1}_{\widetilde{y}_i \ne y_i} is the number of different entries (Hamming distance) of two vectors. Eq. (1) models three different perturbation models: (i) label flipping (rl>0,rs=0r_l > 0, r_s = 0); (ii) structure poisoning (rl=0r_l = 0, rs>0r_s > 0); and (iii) both together (rl>0r_l > 0, rs>0r_s > 0).

Deep partition aggregation. State-of-the-art certified robustness guarantees for supervised image classification under poisoning attacks have been achieved via the partition-and-aggregate paradigm. The most prominent implementation of which is Deep Partition Aggregation (DPA) ([18]). The core idea is to partition an i.i.d. training set DD into kk disjoint subsets and to train independent classifiers fD(i):X→Yf_D^{(i)}: \mathcal{X} \to\mathcal{Y} deterministically on each partition ii. At inference time, for a given input x∈Xx \in\mathcal{X}, the final prediction is made via majority vote across all base classifiers:

gD(x)=arg⁡max⁡c∈Y nc(D,x),(2)g_D(x) = \underset{c \in\mathcal{Y}}{\arg\max}\ n_c(D,x), \tag*{(2)}

where nc(D,x)=∑i=1k1[fD(i)(x)=c]n_c(D,x) = \sum_{i=1}^{k} \mathbf{1}[f_D^{(i)}(x) = c] counts the number of classifiers predicting class cc for input xx. This setup enables a formal robustness guarantee for the aggregated prediction under poisoning:

Theorem 2.1 ([18]). Given a clean dataset DD, the majority-vote prediction remains unchanged, i.e. gD(x)=gD~(x)g_D(x) = g_{\widetilde{D}}(x), for any perturbed dataset D~∈Br(D)\widetilde{D} \in B_r(D) bounded by the attack budget rr, as long as

r≤⌊nc(D,x)−max⁡c′≠c(nc′(D,x)+1c′<c)2⌋,(3)r \le\left\lfloor\frac{n_c(D,x) - \max_{c' \ne c}\left(n_{c'}(D,x) + \mathbf{1}_{c'<c}\right)}{2} \right\rfloor, \tag*{(3)}

where c=gD(x)c = g_D(x) is the predicted class on the clean dataset.

Generalized Deep Partition Aggregation for Non-i.i.d. Data

Even though DPA has been formulated for image data, the general paradigm to derive poisoning guarantees can be readily generalized to non-i.i.d. structured data. The main idea is based on recognizing that deriving a guarantee like Thm. 2.1 does not depend on the i.i.d. nature of the dataset, but rather on a partitioning scheme hh where the potentially poisoned objects are partitioned into subsets independent of one another. In particular, it can be formulated w.r.t. a general set of objects O\mathcal{O} that may be poisoned, where o1∈Oo_1 \in\mathcal{O} may not be independently sampled from another o2∈Oo_2 \in\mathcal{O} (e.g., in a graph, one node may not be independently sampled from another node), as long as the partition o1o_1 is grouped into, is not affected by the value of any other element in O\mathcal{O}, and thus, poisoning any object can only affect one partition.

To formulate such a split-and-majority voting certificate for general (potentially structured) data, assume a dataset D=(T,O)D = (\mathcal{T}, \mathcal{O}) consisting of a set of objects T\mathcal{T} that are known to be clean and a set of objects O\mathcal{O} that may be poisoned. For example, for i.i.d. image data O={xi}i=1n\mathcal{O} = \{x_i\}_{i=1}^{n} and T=∅\mathcal{T} = \varnothing. Then, kk partitions Pi\mathcal{P}_i with i∈[k]i \in[k] are created as follows:

Pi:=(T,{o∈O∣h(T,o)=i(modk)})(4)\mathcal{P}_i := \left(\mathcal{T}, \{o \in\mathcal{O} \mid h(\mathcal{T},o) = i \pmod{k}\}\right) \tag*{(4)}

where hh is a deterministic (hash) function that takes T\mathcal{T} and one o∈Oo \in\mathcal{O} as input and outputs a number in N\mathbb{N} representing the partition index, into which the given object oo should be grouped. Then, one independently trains base classifiers fD(i):X→Yf_D^{(i)}: \mathcal{X} \to\mathcal{Y} on each partition Pi\mathcal{P}_i, where X\mathcal{X} represents a general data domain. Without loss of generality, we assume fD(i)f_D^{(i)} to output a scalar class prediction, i.e., Y⊆N\mathcal{Y} \subseteq\mathbb{N}. For example, for node classification, the data domain can be defined as X=(G,N0)\mathcal{X} = (\mathcal{G},\mathbb{N}_0) where G\mathcal{G} is the set of possible graphs and the second element in the tuple refers to the index of a node, for which a class prediction is sought.1 Now, given an input x∈Xx \in\mathcal{X}, the final prediction is made as in DPA for images via a majority vote across all base classifiers (Eq. (2)), which we denote gD(x)g_D(x).

Lastly, for general data domains, the set difference Δ(D,D~)\Delta(D,\widetilde{D}) may not always be an appropriate distance measure. Thus, assume a general distance function d(D,D~)d(D,\widetilde{D}) between the clean dataset DD and the perturbed dataset D~\widetilde{D}. Further, different choices of hash function hh may affect how many partitions dh∈Nd_h \in\mathbb{N} are at most affected when poisoning an object o∈Oo \in\mathcal{O}. If a perturbation of size d(D,D~)d(D,\widetilde{D}) leads to at most pp changed partitions given hh. Then, the scalar dhd_h links d(D,D~)d(D,\widetilde{D}) to pp as follows: dh⋅d(D,D~)≥pd_h \cdot d(D,\widetilde{D}) \ge p. Exemplary, dh>1d_h > 1 if one object is partitioned (duplicated) into multiple partitions as done by Wang et al. [36]. Now, we can state the following general theorem that follows the proof strategy outlined by Levine & Feizi [18] and we refer to App. § 15.§ 1 for the proof:

Theorem 3.1 (Generalized DPA). Given a clean, possible non-i.i.d. and structured dataset DD, and a poisoned dataset D~\widetilde{D}, the majority-vote classifier prediction remains unchanged, i.e., gD(x)=gD~(x)g_D(x) = g_{\widetilde{D}}(x), as long as dhd(D,D~)≤⌊(nc(D,x)−max⁡c′≠c(nc′(D,x)+1c′<c))/2⌋=rm(D,x)d_h d(D,\widetilde{D}) \le\left\lfloor\left(n_c(D,x)-\max_{c' \ne c}\left(n_{c'}(D,x)+\mathbf{1}_{c'<c}\right)\right)/2\right\rfloor= r_m(D,x), where c=gD(x)c = g_D(x) is the predicted class on the clean dataset.

We refer to the right-hand side of the condition in Thm. 3.1 as the robust margin rm(D,x)r_m(D,x) of a sample xx given a dataset DD. To conclude, we need to find a function hh, a scalar dhd_h, and a distance measure d(D,D~)d(D,\widetilde{D}) to get a robustness guarantee for an ensemble classifier with Thm. 3.1.

Generalized DPA for graphs. We define a general hash function hh in Eq. (5) that allows to partition a graph based on its node features X\mathcal{X}. This hash function can be used for all three perturbation models captured by Eq. (1):

h(X,o)={h(Xi∥Xj)+h(Xj∥Xi)if o∈Eh(Xv)if o∈V(5)h(\mathcal{X},o) = \begin{cases} h(X_i\Vert X_j) + h(X_j\Vert X_i) & \text{if } o \in\mathcal{E} \\ h(X_v) & \text{if } o \in\mathcal{V} \end{cases} \tag*{(5)}

The hash function h(X,o)h(\mathcal{X},o) determines the partition index for an edge, by taking the features of the incident nodes and concatenating them. We add both orderings to make the partitioning process invariant to the actual node order. When partitioning labels, h(X,o)h(X,o) takes the corresponding node’s features as input. The hh in Eq. (5) can be any hash function, in our experiments we choose the MD5 hash. As each edge or label is in exactly one partition, dh=1d_h=1.

Finally, we choose three distance metrics for the three different threat models. For label poisoning, we take the Hamming distance δ(y,y~)\delta(y,\tilde{y}) between label vectors. For graph structure poisoning, we use the symmetric set difference Δ(E,E~)\Delta(E,\tilde{E}) between edge sets. Inserting or deleting an edge in the graph leads to Δ(E,E~)=1\Delta(E,\tilde{E})=1 and the modification of an edge to Δ(E,E~)=2\Delta(E,\tilde{E})=2. Similarly, the insertion or deletion of an edge leads to exactly one affected partition based on hh, but a modification of an edge affects two. For a combination of label and structure poisoning, we add up the two distances d((E,y),(E~,y~))=δ(y,y~)+Δ(E,E~)d((E,y),(\tilde{E},\tilde{y}))=\delta(y,\tilde{y})+\Delta(E,\tilde{E}). This is indeed a distance metric (see App. C.2). Given the graph dataset DD from Sec. 2, plugging in these distance measures along with our hh from Eq. (5) and dh=1d_h=1 into Thm. 3.1, we get the following conditions for our certificates to hold:

G~∈Brl>0,rs=0(G): δ(y,y~)≤rm(D,x)(6)\tilde{G}\in B_{r_l>0,r_s=0}(G):\ \delta(y,\tilde{y})\leq r_m(D,x) \tag*{(6)}
G~∈Brl=0,rs>0(G): Δ(E,E~)≤rm(D,x)(7)\tilde{G}\in B_{r_l=0,r_s>0}(G):\ \Delta(E,\tilde{E})\leq r_m(D,x) \tag*{(7)}
G~∈Brl>0,rs>0(G): d((E,y),(E~,y~))≤rm(D,x)(8)\tilde{G}\in B_{r_l>0,r_s>0}(G):\ d((E,y),(\tilde{E},\tilde{y}))\leq r_m(D,x) \tag*{(8)}

where rm(D,x)r_m(D,x) is the robust margin introduced in Thm. 3.1. In the context of transductive node classification, xx refers to a node that we seek to classify in the graph DD. In general, xx could refer to a node in an arbitrary graph different to DD.

Limitations of the Simple Partitioning in the Graph Domain

We first expose that the partitioning scheme used by DPA does not work well on graph datasets due to their inherent label and structure sparsity. In the context of image classification, obtaining provable poisoning robustness through partitioning yields significant results [18]. For example, using 1,000 partitions on CIFAR-10 achieves a certified accuracy of 50% against 392 label flips. The key factor in deriving strong robustness guarantees through partitioning is the number of partitions kk. Increasing kk increases the possible perturbation budget one can certify. Notably, the maximum number of tolerated perturbations before the certified ratio drops to 0% is ⌊k2⌋\left\lfloor\frac{k}{2}\right\rfloor. Thus, one can argue that the number of partitions kk should be as large as possible to produce good certified radii. The primary constraint on increasing kk is the size of the training dataset. With 50,000 training images in CIFAR-10, it is feasible to use k=1,000k=1,000 partitions while maintaining acceptable performance of the base classifiers fD(i)f_D^{(i)}. Critically, this approach does not straightforwardly translate to graph learning as we outline in the following.

Commonly used semi-supervised graph datasets come with significantly lower label rates compared to image datasets (see Table 1 in App. A). Regarding label-flipping, applying the partitioning scheme naively to node labels results in partitions with few labeled nodes – often fewer than the number of classes. Figure 2 shows that when using 40% of nodes for training on Cora-ML, having k=281k=281 partitions yields an average of only 4 labeled nodes per partition, even though there are 7 classes. This restricts the certification bound to 140 label flips, and base classifiers suffer from significantly reduced performance, as each model only has access to on average 4 labels during training. Even worse, Figure 4(a) shows that k=80k=80 partitions already leads to a clean accuracy of only close to 40% for an ensemble of GCNs [12] on Cora-ML, whereas a GCN trained without partitioning achieves ∼\sim78.77% accuracy.

Average number of training labels across partitions

Figure 2. Label sparsity (Cora-ML)

Certified accuracy plots for Cora-ML and PubMed under label flipping and structure perturbations

Figure 4. The effectiveness of our method is demonstrated by the increase in certified accuracy compared to the naive partition-based approach from § 4. (a) and (b) are certified against Label Flipping (LF) with k=80k = 80 and k=500k = 500 partitions, respectively; (c) and (d) are certified against Structure Perturbations (SP) with k=800k = 800 partitions; (e) is certified against both (LF&SP) with k=250k = 250 partitions. We showcase the stark improvement of robustness both on Cora-ML and PubMed, demonstrating that our method works for both smaller and larger graphs. The red lines in (c) and (d) represent the performance of an infinitely robust MLP, serving as a trivial baseline for structure perturbation. The green dots are the non-robust clean accuracies of the same model trained without any partitions.

Name# Nodes# Training Labels# Edges# Features# ClassesAvg. Degree
Cora-ML28108437981287972.84
CiteSeer21106333668370361.74
Cora27088125069143371.87
PubMed1971759154432450032.25
Wiki-CS117015862161233001018.47
Amazon-Computers1375282514917227671035.76
Amazon-Photo76504590238162745831.13
ogbn-arxiv16934396001166243128406.89

Table 1. Statistics of Datasets. The number of training labels is 30% of all nodes for Cora-ML, CiteSeer, Cora, PubMed; 60% for Amazon-Computers and Amazon-Photo; and 5% for Wiki-CS and ogbn-arxiv.

For structure partitioning, the graph structure rapidly deteriorates as the edges are divided among partitions, rendering the approach ineffective for GNNs. This is illustrated in Figure 3, where we plot the mean of average node degrees across partitions. When the number of partitions exceeds k>50k>50, connectivity in the different subgraphs becomes virtually nonexistent. Since GNNs rely on message passing to aggregate information from neighbors, this severely impairs their ability to learn meaningful representations. Under such conditions, the classifiers’ performance deteriorates to that of a multilayer perceptron (MLP), which, however, is already robust to structure perturbations since it does not utilize any edge information. Overall, partitioning-based robustness certificates cannot be naively applied in the graph domain due to the inherent label and structure sparsity, motivating the need for more sophisticated methods.

Mean average degree across partitions

Figure 3. Structure sparsity (Cora-ML)

Deep Self-Training Graph Partition Aggregation

To address these sparsity challenges, we propose various semi-supervised learning methods to enhance the performance of the weak classifiers by selecting either pseudo-labels or edges, or both, on each partition’s limited training data. This enables us to obtain strong certificates on graphs.

Algorithm 1 ST-GPA against label flipping

Input: Graph data D=(E,X,Y)D = (\mathcal{E}, \mathcal{X}, \mathcal{Y}), selectiveness tt, co-training method CT⁡(E,X,y,t)\operatorname{CT}(\mathcal{E}, \mathcal{X}, y, t), self-training method ST⁡(E,X,y,t)\operatorname{ST}(\mathcal{E}, \mathcal{X}, y, t), training order otrn=(op1,…,opR)∈{CT⁡,ST⁡}Ro_{\mathrm{trn}} = (op_1, \ldots, op_R) \in\{\operatorname{CT}, \operatorname{ST}\}^{R}, hash function hh, number of partitions kk

Output: An ensemble classifier prediction and the associated certificate for a test node vv.

  1. Split labels into partitions yi={y∣y∈Y,h(X,y)≡i(modk)}y_i = \{y \mid y \in\mathcal{Y}, h(\mathcal{X}, y) \equiv i \pmod{k}\}

  2. for each partition ii do

  3. for each operation opop in given order otrno_{\mathrm{trn}} do

  4. y^=op(εi,X,yi,t)\hat{y} = op(\varepsilon_i, \mathcal{X}, y_i, t)

  5. yi=yi∪y^y_i = y_i \cup\hat{y}

  6. end for

  7. Train fif_i on D^={E,X,yi}\hat{D} = \{\mathcal{E}, \mathcal{X}, y_i\}

  8. end for

  9. Count base classifier predictions nc(v)n_c(v) for all c∈[C]c \in[C]

  10. Obtain majority class c∗=arg⁡max⁡c∈[C]nc(v)c^* = \arg\max_{c \in[C]} n_c(v)

  11. Calculate robust margin (see Thm. 3.1)

rm=⌊nc∗(v)−max⁡c′≠c∗(nc′(v)+1c′<c∗)2⌋r_m = \left\lfloor\frac{n_{c^*}(v) - \max_{c' \ne c^*}\left(n_{c'}(v) + \mathbb{1}_{c' < c^*}\right)}{2} \right\rfloor
  1. return c∗,rmc^*, r_m

Semi-Supervised Learning for Label Generation

To maximize utilization of the limited available labels within each partition, we employ two complementary pseudo-label generation methods: (i) Co-Training (CT), and (ii) Self-Training (ST). First, co-training leverages graph structure to propagate existing labels to neighboring nodes. While Li et al. (2018) proposes to generate pseudo-labels for the training of a GNN using ParWalks (Wu et al., 2012), its high computational complexity renders this approach impractical for larger graphs. Instead, we propose the use of label propagation (LP) (Zhu & Ghahramani, [42]) to significantly speed up the co-training process. The key advantage of LP is that it does not require computing the inverse of a Laplacian matrix inherent to ParWalks, and thus can be efficiently applied to larger graphs. Second, for self-training, we propose training a GNN on the existing labeled data and selecting the most confident predictions (as determined by their softmax scores) to serve as pseudo-labels for subsequent training iterations. Notably, both methods (co- and self-training) can be applied consecutively as we demonstrate in § 7, where we observe that applying first co-training and then self-training works best (see Figure 5(a)).

Three plots showing certified accuracy under label and structure perturbations

Figure 5. (a) Different orders of co-training and self-training against Label Flipping (LF) on Cora-ML with k=80k = 80 and label propagation as co-training method; (b) Label propagation provides similar performance in co-training compared to ParWalks (Wu et al., 2012) while being scalable to larger graphs, demonstrated on Cora-ML with 80 partitions; (c) Our method provides significant improvements against Label Flipping (LF) and Structure Perturbations (SP) on PubMed with 200 partitions with link prediction, co-training then self-training, while stacking more rounds of semi-supervised learning in said order yields further but marginal improvement.

In LP we propagate a score matrix S∈RN×CS \in\mathbb{R}^{N \times C} in which Si,jS_{i,j} represents the likelihood of node ii belonging to class jj. SS is initialized as one-hot encoded label matrix S(0)=YS^{(0)} = Y (where an unlabeled node has a row of zeros in YY) and propagated with the normalized adjacency matrix A~=D−12AD−12\widetilde{A} = D^{-\frac{1}{2}} A D^{-\frac{1}{2}}, as shown in Eq. (9):

S(i+1)=αA~S(i)+(1−α)Y(9)S^{(i+1)} = \alpha\widetilde{A}S^{(i)} + (1-\alpha)Y \tag*{(9)}

Algorithm 2 ST-GPA against structure perturbations

Input: Graph dataset D=(E,X,Y)D=(\mathcal{E}, \mathcal{X}, \mathcal{Y}), selectiveness ε\varepsilon, link prediction method LP⁡(Ei,X,Y,ε)\operatorname{LP}(\mathcal{E}_i,\mathcal{X},\mathcal{Y},\varepsilon), hash function hh, number of partitions kk

Output: An ensemble classifier prediction and the associated certificate for a test node vv.

  1. Split edges into partitions Ei={e∣e∈E,h(X,e)≡i(modk)}\mathcal{E}_i = \{e \mid e \in\mathcal{E}, h(\mathcal{X}, e) \equiv i \pmod{k}\}

  2. for each partition ii do

  3. E^i=LP⁡(Ei,X,Y,ε)\hat{\mathcal{E}}_i = \operatorname{LP}(\mathcal{E}_i,\mathcal{X},\mathcal{Y},\varepsilon)

  4. Ei=Ei∪E^i\mathcal{E}_i = \mathcal{E}_i \cup\hat{\mathcal{E}}_i

  5. Train fif_i on D^={Ei,X,Y}\hat{D} = \{\mathcal{E}_i,\mathcal{X},\mathcal{Y}\}

  6. end for

  7. Count base classifier predictions nc(v)n_c(v) for all c∈[C]c \in[C]

  8. Obtain majority class c∗=arg⁡max⁡c∈[C]nc(v)c^* = \arg\max_{c \in[C]} n_c(v)

  9. Calculate robust margin (see Thm. 3.1)

rm=⌊nc∗(v)−max⁡c′≠c∗(nc′(v)+1c′<c∗)2⌋r_m = \left\lfloor\frac{n_{c^*}(v) - \max_{c' \ne c^*}\left(n_{c'}(v) + \mathbb{1}_{c' < c^*}\right)}{2} \right\rfloor
  1. return c∗,rmc^*, r_m

where 1−α1-\alpha is the teleport probability. This propagation is iterated until convergence or a cutoff iteration. Both co-training and self-training result in a score matrix S∈RN×CS \in\mathbb{R}^{N \times C}, which is used for selecting pseudo-labels. We introduce a hyperparameter tt representing the number of pseudo-labels with the highest scores added per class via either method to control the selectiveness. A lower tt adds less but often higher-quality pseudo-labels, while higher tt adds more but less-confident ones. We present the full certification pipeline against label flipping in Algo. 1. Note that only Lines 9–11 have to be repeated to get a certificate for other nodes.

Semi-Supervised Learning for Edge Generation

Motivated by the concept of self-training in graph machine learning, we extend semi-supervised learning to edge prediction by generating pseudo-edges instead of pseudo-labels. Guided by the homophily assumption, we generate pseudo-edges that connect node pairs likely belonging to the same class based on a model trained on the current graph. Here, modern link prediction methods (Zhang & Chen, [41]; Kazi et al., [11]) struggle as the edges in every partition are extremely sparse (see § 4). Instead, we try to capture the overall graph structure and dilute the effect of possible inter-class edges by adding in a denser graph than the original one. Within each partition, we first train a GNN to obtain initial node predictions and confidence scores, typically represented by the softmax outputs of the final GNN layer. We then iteratively add edges between node pairs with the highest sum of confidence of being in the same class. The number of edges added is controlled by a hyperparameter ε\varepsilon, which specifies the multiplier of the number of added edges within each partition relative to the original graph. Using this expanded edge set, a second GNN is trained to produce final predictions used for certification. Our certification pipeline against structure perturbation is outlined in Algo. 2.

On first sight, a downside of our link prediction scheme is that we sample a denser graph for each partition than the original one. If this is implemented naively, it will have roughly O(kn2)O(kn^2) time and memory complexity, which does not scale well with the graph size and the number of partitions. To address this, we introduce an efficient algorithm in App. § 17.§ 1, which has a near-linear complexity based on managing a global edge-candidate heap.

With the proposed methods addressing either label flipping or structure perturbations, a scheme for certifying against both types of attacks becomes possible. We partition both labels and edges into partitions, perform semi-supervised edge and label generation iteratively, and obtain the final base classifier by training on the extended edges and labels, before we take the majority vote and compute certificates. We provide pseudocode for this joint pipeline in App. § 17.§ 2.

Experimental Evaluation

In this section, we investigate the robustness guarantees derived by Deep Self-Training Graph Partition Aggregation (ST-GPA) and showcase the improvement of ST-GPA compared to simple partition aggregation on graphs.2

Experimental details. We demonstrate results for transductive node classification on four datasets: Cora-ML (Bojchevski & Günnemann, [1]), and the three Planetoid datasets CiteSeer, Cora, and PubMed (Yang et al., [40]); and for three GNNs: Graph Convolutional Networks (GCN) (Kipf & Welling, [12]), Graph Attention Networks (GAT) (Veličković et al., [35]), and APPNP (Klicpera et al., [13]). To train a robust classifier, we partition graphs as described in § 5. Each round of semi-supervised learning adds pseudo-labels or edges to the training sets of the individual partitions, while keeping the partitions isolated. We train an ensemble classifier after each round of pseudo-label or pseudo-edge generation to investigate the effect of the individual semi-supervised learning steps. Results are reported using certified accuracy, which is the percentage of test nodes whose predictions are correct and provably robust, as a function of the perturbation size defined in Eq. (1). In all figures, colored areas represent the standard deviation over 3 seeds. We represent a baseline ensemble classifier trained on partitions without any semi-supervised learning as dashed lines. It is important to note that MLPs exhibit infinite robustness against structure perturbations, since they do not utilize edges during training. Consequently, any model with certified accuracy against structure perturbations below that of an MLP is trivial. Thus, we include an MLP as baseline as a red-dotted line in the structure perturbation plots. In these plots, we discard the trivial part of the curve below this baseline. We provide further details on our setup in App. § 13.

ST-GPA yields strong certified robustness. Figure 4 demonstrates the stark improvement of certified accuracies by our proposed certification method ST-GPA, against Label Flipping (LF) in Figure 4(a) and Figure 4(b), Structure Perturbation (SP) in Figure 4(c) and Figure 4(d), and both label and structure perturbations in Figure 4(e). If partitioning is applied naively, i.e., without our semi-supervised learning schemes from § 5, we only get marginal certified accuracy curves (orange dashed lines) due to the sparsity of labels or edges as discussed in § 4. In the structure case on Cora-ML (Figure 4(c)), the clean accuracy of an ensemble GCN is even worse than an infinitely robust MLP, rendering the naive approach ineffective. In contrast, with our method we restore the ensemble classifier’s clean accuracy to a higher level compared to an ensemble without semi-supervised learning, typically around 70% to 80%, and this also allows the certified accuracy curves to drop down slower, meaning higher certified accuracy against the same number of perturbations. We include as a reference the clean accuracy of a GCN trained without any partitioning, and thus leading to certified accuracies of 0% for any non-zero perturbation. Table 2 in App. A reports clean accuracies on other datasets.

MLPGCNGATAPPNP
Cora-ML74.02(0.26)78.77(2.10)76.95(0.37)85.13(0.24)
CiteSeer70.35(0.20)67.46(0.45)64.98(2.38)72.30(0.61)
Cora67.78(0.06)76.18(0.41)75.77(1.22)83.39(0.82)
PubMed73.09(0.05)83.66(1.33)79.01(0.56)87.49(0.41)

Table 2. Model Clean Accuracies on Datasets. We report the clean accuracy (percentage) on the test nodes with given dataset and model with the standard deviation of 3 repeated experiments with different initialization seeds to the model.

For certifying label flipping, we demonstrate the effect of the order of co- and self-training in Figure 5(a). We find that first co- and then self-training generally works best. This can be understood as self-training involves training a GNN on the available labels in a partition. With k=80k = 80 partitions, each partition contains only ∼10\sim10 labels on smaller datasets. In contrast, co-training with label propagation does not require a representation learning step and effectively leverages the graph structure despite the extremely low label rate, producing high-quality pseudo-labels that can be further improved by subsequent self-training rounds. This effect is consistent across all investigated datasets as we show in Figure 8 in App. B.2. Consequently, we adopt this order for all experiments involving label flipping.

Certified accuracy against label flipping on different datasets

Figure 8. We show different orders of co-training and self-training against label flipping on different datasets. k=80k = 80 unless otherwise stated.

In our certificate against both label flipping and structure perturbations, we perform link prediction, then co-training with label propagation, and finally self-training on labels. We perform several rounds of edge and label generation in this order because label propagation relies on the meaningful graph structure that link prediction generates, and self-training generally works better after co-training, as we find out in Figure 5(a). In Figure 5(c) we show that our method introduces significant improvements in the first round, where additional rounds can lead to further improvements.

Co-training with label propagation is similarly performant as ParWalks yet scalable. Since Li et al. (2018) proposed ParWalks in combination with self-training to address low label rates, we compare ParWalks with the Label Propagation (LP) from Zhu & Ghahramani [42]. As shown in Figure 5(b), the performance advantage of ParWalks over LP is negligible. This is consistent across different datasets as shown in Figure 10 in App. B.2. Given that LP with random teleportation does not require computing the inverse of the Laplacian, we adopt LP as our primary method.

Figure 10. Comparison between our method (co-training with label propagation) and ParWalks(Wu et al. (2012)). The results are achieved by co-training then self-training on given datasets, with k=80k = 80 partitions unless otherwise stated.

Our method works with any GNN. The first row in Figure 6 shows the certification performance of a GCN, GAT, and APPNP with and without our approach. The results show similar performance improvements and trends across all models, with clean accuracy boosted to around 80% for LF, 76% for SP, and 67% for both. We highlight this because our partition-based certificate is architecture-agnostic, and does not assume anything about the underlying classifiers themselves. Thus, our method stays compatible with better underlying GNNs, for which one can expect to produce better certificates. Exemplarily, in App. B.4 we use a modern graph transformer as base classifier (Wu et al., 2022).

Six plots comparing certified accuracy under label and structure perturbations

Figure 6. Figure 6. In (a) to (c) our method improves upon naive partition-based certification w/o semi-supervised learning, regardless of the GNN type; (d) to (f) demonstrate for GCNs that our method scales very well for larger number of partitions kk, which provides better certificates.

Our method scales well with partitions. The second row in Figure 6 shows the effect of varying the number of partitions kk. The results demonstrate the effectiveness and scalability of our method: as kk increases, which is necessary to derive stronger guarantees, the baseline performance rapidly declines due to the sparsity of labels and structure per partition. However, our experiments indicate that link prediction, co-training, and self-training are required for non-trivial robustness guarantees. This is supported by more results in Figure 11 in App. B.2. We observe that dividing labels to more than 100 partitions becomes impractical given the training size of 30% on Cora-ML, as partitioning would result in some partitions containing no labeled nodes, making training on those partitions infeasible. Further experiments on the selectiveness hyperparameter tt and ε\varepsilon, and label propagation teleportation parameter α\alpha are included in App. B.5.

Figure 11. Scalability over kk with our link prediction method.

Our label flipping certificate scales well to large graphs. In App. B.3 we show that our label flipping certificate scales well to large graphs such as ogbn-arxiv, or significantly more dense graphs such as Wiki-CS. For more details on the time complexities and scaling behavior of both our label flipping and structure certificate, we refer to App. F, as well as to our discussion in § 9.

Related Work

Studying upper bounds on adversarial robustness against test- and training-time perturbations through adversarial attacks is well established for message-passing GNNs ([4, 44, 43, 27, 8]), as well as for more modern graph transformers ([5]). Furthermore, self-training has been successfully used in empirical defenses against such attacks ([17] (Li et al. 2024)). In contrast to adversarial attacks, robustness certificates provide a lower bound on adversarial robustness, and certificates against test-time attacks are well researched for i.i.d. data (Li et al., 2023), as well as for the graph domain ([8, 32, 33, 9]). However, there are few works studying certification against changes to the training data. For the image domain, there are three main approaches: (i) partition-and-aggregate ([18]), (ii) randomized smoothing (over the training data) ([37]), and (iii) differential privacy (Ma et al., 2019); and we refer to Gosch et al. [7] for a representative survey.

Most related to our work is the partition-and-aggregate scheme by Levine & Feizi [18], with various follow-up works ([36, 3, 28, 31, 26, 30]). However, it was mainly studied in the image domain so far. Regarding graphs, Lai et al. [16] develop a collective, probabilistic poisoning certificate against node injection based on randomized smoothing ([15]), which however, is not applicable to the perturbation models studied in this work. Gosch et al. [7] develop a certification paradigm to certify node-feature poisoning, extended to label poisoning by Sabanayagam et al. [29], but both cases are limited to infinite-width GNNs. Further, the label certificate by Sabanayagam et al. [29] does only scale to graph datasets having at most 100–200 training labels and thus, does not scale to even our smallest datasets. However, we still provide a comparison to Sabanayagam et al. [29] in App. § 18.§ 1. Concurrently to our work, Mohgaonkar et al. [26] extended the scalability of the label certificate by Sabanayagam et al. [29] to scale to image datasets. However, the scaling is only possible at additional costs of the clean accuracy, and again, only valid for infinite-width networks. Further, they did not study graph certification. Li et al. (2025) apply partitioning to derive poisoning certificates for GNNs. However, they do not certify against label flipping, and their structure certificates are below the performance of an MLP (see App. § 18.§ 2) and thus, vacuous. Further, their feature certification is only applicable to graph classification, as every node is in all partitions. Overall, our work is the first to provide effective, non-vacuous certified robustness guarantees for GNNs against both label and structure poisoning in node classification tasks.

Discussion and Limitations

We’ve shown that our semi-supervised training schemes are essential for meaningful robustness guarantees in the graph domain with partition-based methods. In this section, we address and discuss the limitations of our method and show how this hints to promising research directions.

Application to heterophilic graphs. While our certification framework is general, the chosen semi-supervised training components rely fundamentally on homophily, which limits their applicability to heterophilic graphs, which we empirically quantify through a study on synthetic graphs in App. § 21. Thus, addressing heterophily requires different semi-supervised learning approaches, such as novel label propagation or link prediction methods tailored to heterophilic structures, each of which represents its own independent research challenge. However, the core ideas of partitioning and self-training remain applicable and could inspire effective robustness guarantees if adapted properly to heterophilic settings.

Link prediction can be expensive. Furthermore, while the label certificate scales well to larger graphs, another important limitation is the computational overhead of link prediction on denser or larger graphs, necessary for effective structure certificates. Our method can produce semi-dense partitions by adding edges to capture the graph structure and diluting the effect of noisy inter-class edges, increasing memory and runtime costs. This overhead prevents scaling link prediction effectively to large datasets like ogbn-arxiv, as shown in our scalability analysis in App. § 19. While alternative link prediction algorithms might alleviate this, most are designed for full graphs rather than sparse partitions, making this a non-trivial challenge.

For a detailed discussion on tightness, we refer to App. § 20.

Conclusion

We derive a self-training framework (ST-GPA) that significantly improves certified robustness against poisoning in sparse graph-structured domains. By adding both synthetic labels and structure through effective semi-supervised learning techniques, our method overcomes the limitations of existing partition-based approaches. Empirical results show large improvements in certified robustness to both label and structure poisoning without compromising clean accuracy. Our findings highlight that effectively leveraging semi-supervised learning on sparse data is essential for provably robust graph machine learning against poisoning through partition-based approaches. This potentially offers a promising direction for building more robust models in semi-supervised settings beyond the graph domain.

Impact statement

This work advances the field of robustness certification by enabling robustness of graph neural networks against structure and label poisoning attacks, thereby fostering more reliable and trustworthy machine learning. While there might be many further potential societal consequences of our work, none which we feel must be specifically highlighted here.

Acknowledgements

This work has been funded by the DAAD program Konrad Zuse Schools of Excellence in Artificial Intelligence (sponsored by the Federal Ministry of Education and Research) and by the German Research Foundation, grant GU 1409/4-1. The authors of this work take full responsibility for its content.

Experiment Setup

Datasets. As described in the beginning of § 7, we use the 3 Planetoid datasets ([40]) Cora, CiteSeer and PubMed, available on PyTorch Geometric,3 and the citation dataset Cora-ML ([1]). As a standard procedure in graph machine learning ([34]), we preprocess all the datasets by taking the largest connected component and force the graph to be undirected. The statistics of the dataset we use can be found in Table 1. The training, validation and test set nodes are determined with scikit-learn’s train_test_split() function,4 with random_state fixed to 12138. We first separate the test nodes’ indices from training and validation (and unused), then use this function again to separate the training set from the validation with the same seed. Only the 30% training labels are available to the model during training. Additionally, we evaluate the label certificates on Wiki-CS ([25]) and ogbn-arxiv ((Hu et al., 2020)), and we sample 1/10th of their original training labels. The 2 Amazon datasets ((Shchur et al., 2018)), Amazon-Photo and Amazon-Computers, are also used for evaluating label certificates, and the same scheme as the Planetoid datasets for splitting the nodes is used.

We follow a 30%-10%-30% train-validation-test split of node labels for all experiments except for larger datasets following Li et al. (2025). Note that the 10% validation set is typically used for regularization tasks such as hyperparameter tuning and early stopping when training a single GNN. However, since we use a fixed set of hyperparameters and do not employ early stopping, the validation set is not utilized during training.

Model Parameters. We used Graph Convolutional Networks (GCN)([12]), Graph Attention Networks (GAT), and Approximate Personalized Propagation of Neural Predictions (APPNP)([13]) throughout our evaluations.

Our GCNs consist of 2 layers of GCNConv layer with added self-loops from pytorch geometric.5 At the bottleneck we use 8 hidden channels, a dropout layer, and ReLU activation. For GAT we use 2 GATConv layers from pytorch geometric.6 The first layer condense the feature channels to 8 hidden channels with 8 attention heads, and applies dropout and ELU activation, and the second layer then condense the 8 × 8 dimension in the middle to class-wise logits. The APPNP model consists of a 2 layer MLP with 8 hidden channels and then an APPNP layer from pytorch geometric7 to propagate representations, with number of iterations K=10K = 10, and teleport probability α=0.1\alpha= 0.1. In structure perturbation experiments specifically, we don’t use dropout as it provides us with better results. For additional evaluation of label certificates on a modern graph transformer, we use NodeFormer (Wu et al., 2022) and the exact setup as their published code. Additionally, we use an 2 layered MLP as baseline against structure perturbations. It also has 8 hidden units and no dropouts. Note that here in our setup, the GCN with an empty graph is strictly equivalent to the MLP. Both other attack models use dropouts with a probability of 0.5. All other unstated parameters follow the pytorch geometric default.

Hyperparameters for Training. For GNN training, we use a fixed set of hyperparameters inherited from Li et al. (2018), which are commonly used in GNN models. Specifically, all models are trained for 200 epochs without early stopping, using the Adam optimizer with a learning rate of 0.01 and a weight decay of 5×10−45 \times10^{-4}. However, due to the unstable nature of GNN training, we choose the epoch with the lowest loss for prediction. To calculate this without overfitting, we separate the data in each partition in halfs, and use one half for training and another for evaluation of the loss. Note that this split happens to the partitioned 30% labels or edges each partition have access to.

For label propagation, we iterate until the score matrix converges, but cap off at 100 iterations.

Evaluation Process. As described in § 5, either all edges, the 30% training set labels, or both are partitioned for the weak classifiers, depending on different types of attacks. We perform transductive node classification, meaning that the weak classifiers then have access to all the graph data G=(E,X,y)G = (E, X, y) except for the poisoned items, which are partitioned in the first place.

All models are evaluated with at least 3 different deterministically chosen seeds for model initialization to evaluate the repeatability of our results. The seeds are chosen by python’s random module. We seed the random module with a fixed seed of 123456, and then use random.randint(0, 2**32) to generate a deterministic random seed each time we repeat an experiment.

After the training is done, we evaluate the certified accuracies on the 30% test nodes. This is done by storing the class predictions of each weak classifier for each node and calculate the robust margin as introduced in Eq. (8). Then the certified accuracies we reported are given by calculating the ratio of test nodes whose robust margin, together with a specific perturbation size, satisfies Eq. (8).

Hyperparameters Summary. Here we provide a table of all hyperparameters involved as a summary to our description of the experiment setup, alongside their default values and selection criteria. Throughout this paper, all hyperparameters take their default values (if any) unless otherwise stated.

hyperparameterdescriptionattack modelsrelated modelsdefault valueselection criteria
lrlearning rateallall0.01follows Li et al. (2018)
wdweight decayallall5×10−45 \times10^{-4}follows Li et al. (2018)
eptraining epochsallall200follows Li et al. (2018)
esearly stoppingallallNonefollows Li et al. (2018)
init_seedseed for python random moduleallall123456/
repetitionnumber of repeated experimentsallall3/
num_layersnumber of layers in the modelallall2prevents overfitting
hidden_sizehidden channelsallall8prevents overfitting
dropoutdropout probability in dropout layersallGCN, GAT0.5prevents overfitting
activationactivation function between 2 layersallGCN, APPNP, MLPReLU/
activationactivation function between 2 layersallGATELU/
train_size% of labels for trainingallall30%/
val_size% of labels for validationallall10%/
test_size% of labels for testingallall30%/
kknumber of partitionsLF80Figure 6
kknumber of partitionsSPall800Figure 11
kknumber of partitionsLF&SP200Figure 6
orderorder of co-training and self-trainingLF, LF&SPallC/T then S/TFigure 8
co-train methodParWalks(PW) or label propagation(LP)LF, LF&SPallLPFigure 10
ttnumber of pseudo-labels per classLF, LF&SPall50Figure 14(a)
α\alphateleport probability in label propagationLF, LF&SPall0.9Figure 14(b)
ϵ\epsilon×\times pseudo-edges than original graphSPalldataset specificFigure 15

Table 3. Hyperparameters

Additional Experiment Results

Clean Accuracy of Ensembles

In Figure 7 we show the clean accuracies of an ensemble classifier if the partitioning scheme is applied trivially, i.e. without semi-supervised learning. In the label case, the sparsity degrades the clean accuracy of the ensemble as kk goes larger. With k=100k = 100 partitions, the clean accuracy drops to just over 20%. In the edge partitioning case, lack of edge information degrades the clean accuracy of an ensemble below that of an MLP’s over about k=30k = 30 partitions. The deterioration of performance shown here necessitate the introduction of semi-supervised learning schemes within the sparse partitions.

Deterioration of clean accuracy of ensembles on Cora-ML

Figure 7. Deterioration of clean accuracy of ensembles on Cora-ML. Standard deviations are reported as colored areas over 3 different seeds.

Additional Results on Other Datasets

Here we present results on other datasets supporting our conclusion from § 7, which have been presented in the main part based on one exemplary dataset. Note that the subfigures marked with (*) are already present in § 7.

The order of co-train then self-train generally works the best against label flipping. Figure 8 showcases this. Our method restores the clean accuracy to generally 70% to 80%, while having higher certified accuracies, despite the poor performance with vanilla partitions.

Against both label and structure perturbations on smaller datasets, our method provides improvement but the limit of kk prevents meaningful joint certificates. Due to the extreme sparsity of labels and edges if we are facing poisoning of both, we can’t use too many partitions, typically limiting kk to around 10. Although the curve drops too fast due to a small kk, yielding hardly any usable certified accuracy against even 1 poisoned label or edge, our method still provides 15% to 20% clean accuracy increase.

Co-training with label propagation is similarly performant as ParWalks yet scalable. Our method has similar certified accuracy compared to ParWalks across datasets, except for CiteSeer where it’s about 10% less. However, we argue that this is compensated by the vastly shorter training time and the characteristic that scales easily to larger datasets by our method.

Link prediction allows arbitrarily large kk which generates even better certificates. In Figure 11, we demonstrate the near-perfect scalability of link prediction on generating certificates. The number of partitions kk determines the maximum achievable robustness with the partitioning scheme. Therefore, given sufficient computational resources, increasing kk directly leads to improved robustness. Furthermore, we emphasize that kk is theoretically unbounded in its capacity to enhance robustness against structure perturbations.

Certified accuracy under different numbers of rounds of edge and label generation against label and structure perturbations

Figure 9. Different number of rounds of link prediction + co-training + self-training against both label and structure perturbations.

Certifying Label Flipping on Larger and More Diverse Datasets

Our co-training and self-training scheme also scales to larger and more diverse datasets. Figure 12 shows the performance gain upon a trivial partitioning scheme on Wiki-CS, amazon-computers, amazon-photos, and ogbn-arxiv. Wiki-CS and the amazon datasets include significantly more edges than the citation datasets. ogbn-arxiv includes significantly more nodes and edges (see also Table 1 in App. § 13). Our co-training and self-training generally restores clean accuracy well, while also having a higher certified accuracy. For Wiki-CS and ogbn-arxiv we used 1/10 of the label rate as other datasets to demonstrate this improvement with fewer partitions. Using the original split, a larger kk would also be possible, and likely improve results (compare Figure 12(d) and Figure 12(e)). Our structure certificate struggles to scale well to such large and dense datasets, as we discuss in § 9.

Certifying label flipping on larger and denser graph datasets

Figure 12. Certifying label flipping on larger and denser graph datasets. MLP baseline for ogbn-arxiv refers to an MLP ensemble.

Additional Results for Graph Transformers

Our co-training and self-training scheme also applies to modern graph transformers. Figure 13 shows that our method improves certified accuracy from 20% to over 70%, showcasing that it works well with modern graph transformer architectures, apart from the result in Figure 6(a) and Figure 6(b) in § 7. In particular, we find that NodeFormer w/o our semi-supervised learning strategies struggles to learn from sparsely labeled partitions. However, enriching the partitions with pseudo-labels using our proposed co-training scheme leads to good clean accuracies and certified robustness of the GT-ensemble against label poisoning.

Certifying label flipping on Cora-ML using NodeFormer

Figure 13. Certifying label flipping on Cora-ML using NodeFormer (k=40k = 40).

Ablations on Hyperparameters

Ablation of $t$

Figure 14a. Ablation of tt

Ablation of $\alpha$

Figure 14b. Ablation of α\alpha

The hyperparameter tt offers a way to balance between performance and robustness. Figure 14(a) illustrates the impact of varying the number of pseudo-labels tt added during training. When tt is small, such as t=1t = 1 or t=10t = 10, the pseudo-labels are too selective and insufficient in quantity to effectively train the subsequent GNN. Conversely, when tt is too large, for example t≥600t \ge600, the quality of the pseudo-labels deteriorates, which negatively affects the ensemble classifier’s performance. Therefore, selecting an appropriate range for tt is critical to achieving optimal certified accuracy. For Cora-ML, this corresponds roughly to the range 50≤t≤20050 \le t \le200. Since t=50t = 50 works already quite well and introduce less computation overhead, we fix t=50t = 50 for all experiments.

Certifying label flipping on Cora-ML with $k=80$ partitions

Figure 14. Certifying label flipping on Cora-ML with k=80k = 80 partitions.

The random teleport probability α\alpha is pretty robust, but need to be properly chosen. Figure 14(b) shows the certificates with co-training then self-training, but varying the random teleport probability α\alpha An α=0\alpha= 0 means always randomly teleport to a labeled node in co-training, while an α=1\alpha= 1 means no random teleport. As demonstrated by the results, the performance generally plateaus when 0.01≤α≤0.990.01 \le\alpha\le0.99. As long as α\alpha isn’t chosen to be too large or too small, the certified accuracy remains the best achievable one. We choose to fix α=0.9\alpha= 0.9 for all experiments.

Figure 15a. Cora-ML

Figure 15b. CiteSeer

Figure 15c. Cora

There is a best ε\varepsilon for each dataset that we can tune to maximize robustness. ε\varepsilon serves as a control parameter for the selectiveness in adding pseudo-edges. A too small ε\varepsilon fails to capture sufficient graph structure, while a too large ε\varepsilon introduces noise that reduces the signal-to-noise ratio in the generated graph, thereby degrading performance. So there is a best ε\varepsilon in between, and according to Figure 15, this best value varies a lot between datasets, even though the size of which are similar. To avoid high overheads in all other experiments, we cap ε\varepsilon to 20.

Figure 15. Certifying structure perturbations on the three smaller datasets with k=800k = 800 partitions.

Proof of Theorems

Proof of Generalized DPA

We restate Thm. 3.1 before proving it:

Theorem 3.1 (Generalized DPA). Given a clean, possible non-i.i.d and structured dataset DD, and a poisoned dataset D~\tilde{D}, the majority-vote classifier prediction remains unchanged, i.e., gD(x)=gD~(x)g_D(x) = g_{\tilde{D}}(x), as long as dh(D,D~)≤[nc(D,x)−max⁡c′≠c(nc′(D,x)+1c′<c)]/2=rm(D,x)d_h(D,\tilde{D}) \le[n_c(D,x)-\max_{c' \ne c}(n_{c'}(D,x)+\mathbb{1}_{c'<c})]/2 = r_m(D,x), where c=gD(x)c=g_D(x) is the predicted class on the clean dataset.

Proof. We first introduce a lemma that gets rid of the floor operation:

Lemma C.1 (Floor operation equivalency).

a≤⌊b2⌋⇔2a≤b,∀a,b∈N(10)a \le\left\lfloor\frac{b}{2} \right\rfloor\Leftrightarrow2a \le b, \forall a,b \in\mathbb{N} \tag*{(10)}

Proof. a≤⌊b2⌋≤b2⇒a≤b2a \le\left\lfloor\frac{b}{2} \right\rfloor\le\frac{b}{2} \Rightarrow a \le\frac{b}{2} and $2a \le b \Rightarrow a \le \frac{b}{2} \Rightarrow a = \lfloor a \rfloor \le \left\lfloor \frac{b}{2} \right\rfloor$

We use the shorthand notation of ncn_c being nc(D,x)n_c(D,x) and n~c\tilde{n}_c being nc(D~,x)n_c(\tilde{D},x), and r=d(D,D~)r = d(D,\tilde{D}).

Given Thm. 3.1 and Lemma C.1

2dh⋅r≤nc−max⁡c′≠c(nc′+1c′<c)(11)2d_h \cdot r \le n_c - \max_{c' \ne c}(n_{c'} + 1_{c'<c}) \tag*{(11)}

We get rid of the max operation by taking any class and move all terms to one side

0≤nc−nc′−1c′<c−2dh⋅r, ∀c′≠c(12)0 \le n_c - n_{c'} - 1_{c'<c} - 2d_h \cdot r,\ \forall c' \ne c \tag*{(12)}

Because the training is conducted in a deterministic manner, the classifier will give the same prediction if the training data is the same. So the number of weak classifiers that predicts differently for a node fi(v)≠f~i(v)f_i(v) \ne\tilde{f}_i(v) is also at most dh⋅rd_h \cdot r. So for any class, the number of predictions changed is bounded by

∀cˉ∈[C], ∣ncˉ−n~cˉ∣≤dh⋅r(13)\forall\bar{c} \in[C],\ |n_{\bar{c}} - \tilde{n}_{\bar{c}}| \le d_h \cdot r \tag*{(13)}

From Eq. (13) we plug in cˉ=c\bar{c} = c and cˉ=c′\bar{c} = c' to get

nc−n~c≤dh⋅r(14)n_c - \tilde{n}_c \le d_h \cdot r \tag*{(14)}
n~c′−nc′≤dh⋅r(15)\tilde{n}_{c'} - n_{c'} \le d_h \cdot r \tag*{(15)}

which is equivalent to

nc≤n~c+dh⋅r(16)n_c \le\tilde{n}_c + d_h \cdot r \tag*{(16)}
−nc′≤−n~c′+dh⋅r(17)-n_{c'} \le-\tilde{n}_{c'} + d_h \cdot r \tag*{(17)}

Plugging this to Eq. (12), we have

∀c′≠c, 0≤nc−nc′−1c′<c−2dh⋅r≤n~c+dh⋅r−n~c′+dh⋅r−1c′<c−2dh⋅r(18)\begin{aligned} \forall c' \ne c,\ 0 &\le n_c - n_{c'} - 1_{c'<c} - 2d_h \cdot r \\ &\le\tilde{n}_c + d_h \cdot r - \tilde{n}_{c'} + d_h \cdot r - 1_{c'<c} - 2d_h \cdot r \tag*{(18)} \end{aligned}
=n~c−n~c′−1c′<c(19)= \tilde{n}_c - \tilde{n}_{c'} - 1_{c'<c} \tag*{(19)}

So for the ensemble classifier trained on poisoned data

n~c≥max⁡c′≠c(n~c′+1c′<c)(20)\tilde{n}_c \ge\max_{c' \ne c}(\tilde{n}_{c'} + 1_{c'<c}) \tag*{(20)}

and the ensemble classifier’s prediction is unchanged because cc is the majority class.

Proof of Distance Function

The following is a proof that d((E,y),(E~,y~))d((E,y),(\tilde{E},\tilde{y})) is a distance.

Proof. We recall that d((E,y),(E~,y~))d((E,y),(\tilde{E},\tilde{y})) is defined to be the sum of symmetric set difference between edges and the hamming distance between labels

d((E,y),(E~,y~))=Δ(E,E~)+δ(y,y~)(21)d((E,y),(\tilde{E},\tilde{y})) = \Delta(E,\tilde{E}) + \delta(y,\tilde{y}) \tag*{(21)}

and a function d:M×M→Rd : M \times M \to\mathbb{R} is a distance on metric space MM if ∀x∈M\forall x \in M, d(x,x)=0d(x,x)=0, d(x,y)>0d(x,y)>0, x≠yx \ne y, d(x,y)=d(y,x)d(x,y)=d(y,x), and d(x,y)≤d(x,z)+d(y,z)d(x,y) \leq d(x,z)+d(y,z).

We first note that d(⋅,⋅)d(\cdot,\cdot) between one (E,y)(\mathcal{E},\mathbf{y}) and itself is 0 because both its terms are 0; It’s value is always positive as it’s the sum of two positive numbers, if both input are distinct; d(⋅,⋅)d(\cdot,\cdot) is symmetric because both its terms are symmetric and changing the order of objects doesn’t affect the value.

To prove triangle inequality

d((E1,y1),(E3,y3))=Δ(E1,E3)+δ(y1,y3)(22)d((\mathcal{E}_1,\mathbf{y}_1),(\mathcal{E}_3,\mathbf{y}_3)) = \Delta(\mathcal{E}_1,\mathcal{E}_3) + \delta(\mathbf{y}_1,\mathbf{y}_3) \tag*{(22)}
≤Δ(E1,E2)+Δ(E2,E3)+δ(y1,y2)+δ(y2,y3)(23)\leq\Delta(\mathcal{E}_1,\mathcal{E}_2) + \Delta(\mathcal{E}_2,\mathcal{E}_3) + \delta(\mathbf{y}_1,\mathbf{y}_2) + \delta(\mathbf{y}_2,\mathbf{y}_3) \tag*{(23)}
=d((E1,y1),(E2,y2))+d((E2,y2),(E3,y3))(24)= d((\mathcal{E}_1,\mathbf{y}_1),(\mathcal{E}_2,\mathbf{y}_2)) + d((\mathcal{E}_2,\mathbf{y}_2),(\mathcal{E}_3,\mathbf{y}_3)) \tag*{(24)}

So d((E,y),(E~,y~))d((\mathcal{E},\mathbf{y}),(\widetilde{\mathcal{E}},\widetilde{\mathbf{y}})) is indeed a distance metric.

□\square

Algorithm 3 Efficient Edge Candidate Selection for Link Augmentation

Input: Number of nodes per class ncn_c, node confidence scores per class: {Sc=[sc,1,sc,2,…,sc,nc]}\{S_c = [s_{c,1}, s_{c,2}, \ldots, s_{c,n_c}]\} sorted descending, desired number of edges to add ε⋅e\varepsilon\cdot e

Output: Top-ε⋅e\varepsilon\cdot e pseudo-edges with highest sum of confidence scores

  1. Initialize global max-heap GG (size = number of classes)

  2. for each class cc do

  3. &nbsp;&nbsp;&nbsp;&nbsp;Initialize empty local max-heap LcL_c

  4. &nbsp;&nbsp;&nbsp;&nbsp;Insert initial pair (0,1)(0, 1) with score s=Sc[u]+Sc[v]s = S_c[u] + S_c[v] and class index as tuple (u,v,s,c)(u, v, s, c) into GG

  5. end for

  6. while number of added edges smaller than ε⋅e\varepsilon\cdot e do

  7. &nbsp;&nbsp;&nbsp;&nbsp;Extract top (u,v,s,c)(u, v, s, c) from global heap GG

  8. &nbsp;&nbsp;&nbsp;&nbsp;Add e=(u,v)e = (u, v) to candidate edge set

  9. &nbsp;&nbsp;&nbsp;&nbsp;For local heap LcL_c, consider children pairs:

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;child1=(u,v+1)child_1 = (u, v + 1) if v+1≤ncv + 1 \leq n_c

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;child2=(u+1,v)child_2 = (u + 1, v) if u+2=vu + 2 = v

  12. &nbsp;&nbsp;&nbsp;&nbsp;for each valid child pair (u,v)(u, v) do

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute sum of score s=Sc[u]+Sc[v]s = S_c[u] + S_c[v]

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Insert tuple (u,v,s)(u, v, s) into LcL_c

  15. &nbsp;&nbsp;&nbsp;&nbsp;end for

  16. &nbsp;&nbsp;&nbsp;&nbsp;Extract next top tuple (u′,v′,s)(u', v', s) from LcL_c

  17. &nbsp;&nbsp;&nbsp;&nbsp;Insert (u′,v′,s,c)(u', v', s, c) into global heap GG

  18. end while

  19. return Final candidate edges across all classes

Algorithms

Efficient Selection of Pseudo-Edge Candidates

As the number of nodes, kk or ε\varepsilon goes up, the number of possible edge pairs also scales up, which results in significant computational overhead. To address this challenge, we propose a time and memory-efficient algorithm for selecting edge candidates with the highest combined confidence scores across all classes. The algorithm for selecting edges is described in Algo. 3. A global max-heap keeps track of which class has the next best edge candidate according to the sum of scores. We initialize the global heap by inserting the first pair (0,1)(0, 1) from each class, as these pairs hold the maximum possible sum of scores within their respective classes. To add edges, we repeatedly pick the top element from the global heap until the number of edges selected exceeds the threshold defined by ε\varepsilon.

To supply the global heap with the best candidates from each class, every class maintains a local heap, which is initially empty. Each time an edge is selected from the global heap, the algorithm accesses the corresponding class’s local heap and inserts the next candidate pairs. To prevent local heaps from becoming prohibitively large, we do not insert all possible node pairs at once. Instead, node pairs are added only when they can potentially represent the best candidate. This is enabled by pre-sorting nodes and their confidence scores within each class in descending order. Consequently, nodes with smaller indices correspond to higher scores. This ordering induces a binary tree structure over node pairs, illustrated in Figure 16, where an edge (u,v)(u, v) has a larger combined score than (u,v+1)(u, v + 1), and (u+1,v)(u + 1, v). As the criterion, the sum of scores, is commutative, (u,v)(u, v) and (v,u)(v, u) represent the same edge candidate, so we consider only node pairs (u,v)(u, v) where u<vu < v. This results in the half binary tree structure in Figure 16.

Tree structure for spawning edge candidates

Figure 16. Tree structure for spawning edge candidates. An edge in layer ii is guaranteed to have a higher score than in layer i+1i + 1 and a lower score than in layer i−1i - 1.

Since most nodes have two parents, simply adding both (u,v+1)(u, v + 1) and (u+1,v)(u + 1, v) to the local heap would result in duplicate insertions of many nodes. To avoid this, we add the pair (u+1,v)(u + 1, v) only when u+2=vu + 2 = v. This condition effectively removes the red dashed connections shown in Figure 16 and ensures that each edge pair is added to the local heap exactly once. This also guarantees that the local heap always contains the node pair with the highest possible sum of scores.

Proposed General Certification Pipeline Against Both Label Flipping and Structure Perturbations

Algo. 4 shows the joint certification pipeline for ST-GPA. Regarding the training order, we do edge generation first, since we find effective co-training relies on meaningful graph structure. Further, we assume the number of label partitions kyk_y and structure partitions kek_e are the same, i.e., k=ke=kyk = k_e = k_y. Otherwise, the partitioning in Lines 1-2 has to be adapted to duplicate the objects associated to the smaller partition number into all partitions, affecting dhd_h when calculating the certificate using the base classifier counts based on Thm. 3.1.

Algorithm 4 ST-GPA joint pipeline

Input: Graph dataset D=(E,X,Y)D = (\mathcal{E}, \mathcal{X}, \mathcal{Y}), a label propagation method y^=LP(ei,X,y)\hat{y} = LP(e_i, \mathcal{X}, y), a label self-training method y^=LST(ei,X,y)\hat{y} = LST(e_i, \mathcal{X}, y), an link prediction method e^i=EST(ei,X,y)\hat{e}_i = EST(e_i, \mathcal{X}, y), a training order otrn=(op1,…,opR)∈{LP,LST,EST}Ro_{trn} = (op_1, \ldots, op_R) \in\{LP, LST, EST\}^{R}, number of partitions kk

Output: An ensemble classifier prediction and the associated certificate for a test node vv.

  1. Split labels into partitions yi={y∣y∈Y,h(X,y)≡i(modk)}y_i = \{y \mid y \in\mathcal{Y}, h(\mathcal{X}, y) \equiv i \pmod{k}\}

  2. Split edges into partitions ei={e∣e∈E,h(X,e)≡i(modk)}e_i = \{e \mid e \in\mathcal{E}, h(\mathcal{X}, e) \equiv i \pmod{k}\}

  3. for each operation opop in the given order otrno_{trn} do

  4. &nbsp;&nbsp;for each partition ii do

  5. &nbsp;&nbsp;e^i\hat{e}_i or y^=op(ei,X,yi)\hat{y} = op(e_i, \mathcal{X}, y_i)

  6. &nbsp;&nbsp;ei=ei∪e^ie_i = e_i \cup\hat{e}_i or yi=yi∪y^y_i = y_i \cup\hat{y}

  7. &nbsp;&nbsp;end for

  8. end for

  9. Train base classifiers fif_i for each partition ii on final edges, labels and features, i.e., on D^={ei,X,yi}\hat{D} = \{e_i, \mathcal{X}, y_i\}.

  10. Count base classifier predictions nc(v)n_c(v) for all c∈[C]c \in[C]

  11. Obtain majority class c∗=arg⁡max⁡c∈[C]nc(v)c^* = \arg\max_{c \in[C]} n_c(v)

  12. Calculate robust margin (see Thm. 3.1)

rm=⌊nc∗−max⁡c′≠c∗(nc′(v)+1c′<c∗)2⌋r_m = \left\lfloor\frac{n_{c^*} - \max_{c' \ne c^*}\left(n_{c'}(v) + \mathbb{1}_{c' < c^*}\right)}{2} \right\rfloor
  1. return c∗,rmc^*, r_m

Comparison to Existing Works

Comparison to LabelCert for Label Flipping

LabelCert [29] introduce the first exact certification method for GNNs against label poisoning, leveraging the Neural Tangent Kernel to reformulate the bilevel poisoning problem as a Mixed-Integer Linear Program. While their certificates are exact in the infinite-width limit, the MILP-based approach is computationally tractable only for binary classification tasks with a very small number of labels (20-40 in total), which represents a highly constrained experimental regime. Evaluation on a binary class Cora-ML dataset (Table 4) reveals that our method achieves certified accuracies that are remarkably competitive despite this sub-optimal setting for label partitioning. Specifically, our approach matches LabelCert within a small margin at a 5% perturbation budget and outperforms it at 10% perturbations. Furthermore, our method scales to graph datasets several orders of magnitude larger in both number of nodes and number of label classes than what LabelCert can handle, demonstrating a practical advantage that extends well beyond the narrow binary setting in which exact MILP-based certification is feasible.

MethodLabel Perturbations5%10%
Ours (co-train then self-train)66.5 ± 17.836.2 ± 1.4
LabelCert68.7 ± 6.832.6 ± 2.0

Table 4. Certified accuracy (%) on Cora-ML (binary) under label poisoning, comparing our method to LabelCert.

Discussion on the Relation to PGNNCert Against Structure Perturbations

Li et al. (2025) apply a similar partitioning scheme PGNNCert to derive poisoning certificates for GNNs. In their work, a threat model of arbitrarily perturbing edges, nodes, and node features (but not labels) is considered. In this section, we provide comparison between our results and theirs. Due to that their certified accuracy does not outperform an infinitely robust MLP, we do not report them in § 7.

To compare our works directly, we adopted their published code and use their exact dataset splits. We then run our proposed approach on their data split. Note that the only difference in the setup is the model and hyperparameters for training, where we use a 2-layered GCN as described in App. § 13, and they use a 3-layered GCN with skip connections and linear layer. In PGNNCert, 2 different partitioning schemes were proposed, namely edge centric and node centric, which has similar performance against structure perturbations, so we report the result with the node centric variant only. Due to the limitation of implementation of PGNNCert, their code does not scale to larger number of partitions due to memory limits, so we choose k=60k = 60 as a compromise and keep other parameters exactly the same for a fair comparison. Note that normally our link prediction scheme can be used with significantly larger kk-s to generate competitive certificates, so we also report k=600k = 600 with the same setup. Although PGNNCert doesn’t report results on Cora, their code can be easily adapted as the Planetoid datasets share the same data loader in PyTorch, so we report results on Cora as well.

As shown in Figure 17, PGNNCert-N’s performance is consistently outperformed by the infinitely robust MLP baseline on all datasets. In the mean time, our link prediction method shows similar improvements to certified accuracy over the MLP baseline as previously reported in § 7 and App. § 14. At k=60k = 60, the allowed perturbation budget is very small. But the reported k=600k = 600 curves shows the normal performance of our method with more partitions, yielding larger perturbation budgets.

Certified accuracies of our method compared to Li et al. (2025) for Cora-ML, CiteSeer, and Cora

Figure 17. Certified accuracies of our method compared to Li et al. (2025), ε=30\varepsilon= 30. PGNNCert-N’s performance falls steadily below the MLP baseline which is infinitely robust to structure perturbation; a trivially applied partitioning scheme has only on-par clean accuracy with an MLP, yielding hardly any meaningful perturbation budget; with our proposed link prediction method, the certified accuracies is most competitive.

Provided that PGNNCert’s performance is below the MLP baseline in the case of structure perturbation, we don’t report a comparison to PGNNCert in the results in this paper, as we already use the MLP baseline as a lowest acceptable case in all our results against structure perturbation.

In PGNNCert, no certificate against label flipping is reported. As we have already shown in App. § 14.§ 1, the partitioning scheme does not readily transfer to labels, so we don’t compare our results with PGNNCert on label flipping.

Scalability of Our Methods

In this section, we analyze the scalability of our three proposed self-training methods by reporting the relative time used in our experiments. In all our experiments, we use a single NVIDIA GTX1080Ti GPU. The link prediction uses CPU only. While it can be easily parallelized, we report the performance on 1 CPU core only, as link prediction on individual partitions are usually done so. The times reported are for relative reference, considering the number of nodes and edges in each dataset.

We first point out that the time complexity scales linearly with the number of partitions kk, since the partitions are disjoint once they are created. Partitioning the dataset takes a negligible amount of time, and can easily be accelerated by pre-processing the dataset and storing all the partition indices. Consequently, it is reasonable that we only report the time taken per partition in this section. The memory complexity is irrelevant w.r.t. kk by the same reason that the partitions are disjoint. The training on individual partitions could be done in a parallel or distributed manner.

Table 5 shows the time taken to train an individual partition on all datasets we tested. Label partition training is generally very fast. Note that the time portion reported for training without semi-supervised learning represents the time baseline for training on the raw partition, which has also similar time complexity of training on the clean graph. Judging from the percentages reported, co-training and self-training is just another round of training of a GNN, which takes similar time as training the first one on the raw partition. The results show good scalability of our label self-training methods as the time portion stays roughly equal regardless of the size of the dataset, and the total time necessary to train the ensemble scales roughly linearly with the graph size (number of nodes).

Cora-MLCiteSeerCoraPubMedWiki-CSogbn-arxiv
graph size (Nr. nodes)2810211027081971711701169343
training time per partition (s)6.45.55.52.73.140.9
thereof training w/o SSL36.1%37.3%36.4%31.9%29.0%31.4%
thereof C/T26.8%24.7%25.2%30.8%36.4%37.0%
thereof S/T37.1%38.0%38.4%37.3%34.6%31.6%

Table 5. Time used for co-training and self-training with t=50t = 50

Table 6 shows the time taken per partition for edge semi-supervised training. Although smaller datasets has faster training time per partition, more partitions are required in structure perturbation to generate a meaningful certificate. Therefore, the time taken to train an edge ensemble is usually comparably longer than a label ensemble. In the smaller datasets, training without and with the pseudo-edges take roughly the same time. However, as the number of edges grows, training with pseudo-edges becomes the predominant factor in total training time, and the time taken to find the pseudo-edges becomes non-negligible. On larger graphs, this is especially a choking factor as we usually add more pseudo-edges than there originally are (ε≫1.0\varepsilon\gg1.0), making the link prediction very time-consuming.

Cora-MLCiteSeerCoraPubMedWiki-CSogbn-arxiv
graph size (Nr. edges)798136685069443242163431166243
training time per partition (s)1.91.02.09.319.367.8
thereof training w/o SSL32.3%58.7%57.5%14.4%8.2%6.6%
thereof L/P7.3%3.8%5.5%13.8%34.5%42.8%
thereof training with pseudo-edges60.4%37.5%37.0%71.8%57.2%50.6%

Table 6. Time used for link prediction with ε=1.0\varepsilon= 1.0

Empirical Tightness and Transfer Attacks

Since our method provides exact certification that already incorporates the lower bound on robustness, a key open question is how tight these certificates are in practice. To investigate this empirically, we conduct a transfer attack using Meta-PGD from Mujkanovic et al. [27], transferring adversarial edges crafted against a GCN surrogate to our partition-and-ensemble framework. We note that gradient-based attacks such as PR-BCD (Mujkanovic et al., [27]) cannot be directly applied to ensemble-based methods, since doing so would require differentiating through the random partitioning and unrolling the training of many base classifiers on distinct graph subsets, a significant technical challenge for which no established solution currently exists. Shown in Figure 18, the transfer attack proves largely ineffective: robust accuracy remains stable at k=800k = 800. We attribute this to two factors: the non-adaptiveness of the attack, which is optimized against a single GCN rather than the ensemble, and the strong graph partitioning inherent to our method, which dilutes the influence of any fixed set of adversarial edges across independently trained base classifiers. Here we want to note the findings from Mohgaonkar et al. [26], who demonstrate on image datasets that DPA-based methods for label certification tend to be overly conservative for small kk, but approach tightness for larger kk. Thus, one could expect similar behavior for graphs.

Figure 18. Performing a transfer attack from a GCN using Meta-PGD for structural poisoning. We find the transfer attack from a GCN to be mostly ineffective in reducing the accuracy of the ensemble (k=800k = 800 for both, certified and robust accuracy).

These results motivate an important open problem: the development of adaptive poisoning attacks tailored specifically to partition-and-ensemble methods. Such attacks would need to simultaneously optimize adversarial edges with respect to the partitioning scheme and the ensemble decision rule, which is a non-trivial objective given the discrete and stochastic nature of graph partitioning. Progress in this direction would enable a rigorous empirical assessment of certificate tightness beyond what transfer attacks can currently provide, and we view it as an important avenue for future work.

Discussion on the Impact of Homophily

In this section, we conduct a systematic study on Contextual Stochastic Block Models (CSBMs), investigating what threshold of homophily our certification method requires for good empirical results. We vary homophily from 0% (pure heterophily) to 100% (pure homophily) in terms of the percentage of edges that connect same-class nodes. We find that both our certificates against label and structure perturbations start to provide benefits from 60% homophily, with strong results when the homophily exceeds 70%. (For context, Cora has 81% homophily.) The detailed results are shown in Figure 19 and Figure 20, and we refer to the figure captions for details on the experimental setup.

Figure 19. Label flipping certificate results with k=50k = 50 on CSBM graphs with different levels of homophily. hh = percentage of edges that connect same class nodes. CSBM: 774 nodes (same number of nodes/class and edge density as Cora). Other parametrization following Gosch et al. [6] with K=1.5K = 1.5, and σ=1\sigma= 1. We use 60% nodes for training and 20% for validation and testing respectively.

Figure 20. Our structural certificate on CSBM graphs with diff level of homophily. hh = percentage of edges that connect same class nodes. CSBM: 774 nodes (same number of nodes per class as Cora), other parametrization following Gosch et al. [6] with K=1.0K = 1.0, and σ=1\sigma= 1. For certification we use k=100k = 100 partitions and ε=1\varepsilon= 1. 60% nodes are used for training and 20% for validation and testing respectively.

References

  1. [1]Bojchevski, A. and Günnemann, S. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference on Learning Representations (ICLR), 2018.
  2. [2]Chapelle, O., Schölkopf, B., and Zien, A. Semi-Supervised Learning (Adaptive Computation and Machine Learning). MIT Press, 2006.
  3. [3]Chen, R., Li, Z., Li, J., Wu, C., and Yan, J. On collective robustness of bagging against data poisoning. In International Conference on Machine Learning (ICML), 2022.arxiv.org/abs/2205.13176
  4. [4]Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., and Song, L. Adversarial attack on graph structured data. In International Conference on Machine Learning (ICML), 2018.arxiv.org/abs/1806.02371
  5. [5]Foth, P., Gosch, L., Geisler, S., Schwinn, L., and Günnemann, S. Adversarial robustness of graph transformers. Transactions of Machine Learning Research (TMLR), 2025.arxiv.org/abs/2407.11764
  6. [6]Gosch, L., Sturm, D., Geisler, S., and Günnemann, S. Revisiting robustness in graph machine learning. In International Conference on Learning Representations (ICLR), 2023.arxiv.org/abs/2305.00851
  7. [7]Gosch, L., Sabanayagam, M., Ghoshdastidar, D., and Günnemann, S. Provable robustness of (graph) neural networks against data poisoning and backdoor attacks. Transactions on Machine Learning Research (TMLR), 2025.arxiv.org/abs/2407.10867
  8. [8]Günnemann, S. Graph Neural Networks: Adversarial Robustness, pp. 149–176. Springer Nature Singapore, 2022.DOI
  9. [9]Hojny, C., Zhang, S., Campos, J. S., and Misener, R. Verify- ing message-passing neural networks via topology-based bounds tightening. In International Conference on Machine Learning (ICML), 2024.arxiv.org/abs/2402.13937
  10. [11]Kazi, A., Cosmo, L., Ahmadi, S.-A., Navab, N., and Bronstein, M. M. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):1606–1617, 2023.DOI
  11. [12]Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.arxiv.org/abs/1609.02907
  12. [13]Klicpera, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations (ICLR), 2019.
  13. [14]Koh, P. W., Steinhardt, J., and Liang, P. Stronger data poisoning attacks break data sanitization defenses. Machine Learning, 111:1–47, 2022.arxiv.org/abs/1811.00741
  14. [15]Lai, Y., Pan, B., Chen, K., Yuan, Y., and Zhou, K. Collective certified robustness against graph injection attacks. In International Conference on Machine Learning (ICML), 2024a.arxiv.org/abs/2403.01423
  15. [16]Lai, Y., Zhu, Y., Pan, B., and Zhou, K. Node-aware bismooting: Certified robustness against graph injection attacks. In IEEE Symposium on Security and Privacy (SP), 2024b.arxiv.org/abs/2312.03979
  16. [17]Lee, W. and Park, H. Self-supervised adversarial purification for graph neural networks. In International Conference on Machine Learning (ICML), 2025.arxiv.org/abs/2605.23239
  17. [18]Levine, A. and Feizi, S. Deep partition aggregation: Provable defense against general poisoning attacks. In International Conference on Learning Representations (ICLR), 2021.arxiv.org/abs/2006.14768
  18. [23]Lingam, V., Akhondzadeh, M. S., and Bojchevski, A. Rethinking label poisoning for GNNs: Pitfalls and attacks. In International Conference on Learning Representations (ICLR), 2024.
  19. [25]Mernyei, P. and Cangea, C. Wiki-cs: A wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv:2007.02901, 2020.arxiv.org/abs/2007.02901
  20. [26]Mohgaonkar, A., Gosch, L., Sabanayagam, M., Ghoshdastidar, D., and Günnemann, S. Exact certification of neural networks and partition aggregation ensembles against label poisoning. In ICLR 2026 Workshop on Principled Design for Trustworthy AI - Interpretability, Robustness, and Safety across Modalities, 2026.arxiv.org/abs/2604.11416
  21. [27]Mujkanovic, F., Geisler, S., Günnemann, S., and Bojchevski, A. Are defenses for graph neural networks robust? In Advances in Neural Information Processing Systems (NeurIPS), 2022.
  22. [28]Rezaei, K., BaniHesham, K., Chegini, A., and Feizi, S. Run- off election: Improved provable defense against data poisoning attacks. In International Conference on Machine Learning (ICML), 2023.arxiv.org/abs/2302.02300
  23. [29]Sabanayagam, M., Gosch, L., Günnemann, S., and Ghoshdastidar, D. Exact certification of (graph) neural networks against label poisoning. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2412.00537
  24. [30]Saxena, A., Schuchardt, J., Scholten, Y., and Günnemann, S. Provable robustness against backdoor attacks via the primal-dual perspective on differential privacy. arXiv preprint arXiv:2605.21780, 2026.arxiv.org/abs/2605.21780
  25. [31]Scholten, Y. and Günnemann, S. Provably reliable conformal prediction sets in the presence of data poisoning. In International Conference on Learning Representations (ICLR), 2025.
  26. [32]Scholten, Y., Schuchardt, J., Geisler, S., Bojchevski, A., and Günnemann, S. Randomized message-interception smoothing: Gray-box certificates for graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
  27. [33]Scholten, Y., Schuchardt, J., Bojchevski, A., and Günnemann, S. Hierarchical randomized smoothing. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
  28. [34]Schur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018.
  29. [35]Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.arxiv.org/abs/1710.10903
  30. [36]Wang, W., Levine, A., and Feizi, S. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In International Conference on Machine Learning (ICML), 2022.
  31. [37]Weber, M., Xu, X., Karlas, B., Zhang, C., and Li, B. RAB: Provable Robustness Against Backdoor Attacks . In IEEE Symposium on Security and Privacy (SP), 2023.
  32. [40]Yang, Z., Cohen, W. W., and Salakhutdinov, R. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning (ICML), 2016.
  33. [41]Zhang, M. and Chen, Y. Link prediction based on graph neural networks. Conference on Neural Information Processing Systems (NeurIPS), 2018.
  34. [42]Zhu, X. and Ghahramani, Z. Learning from labeled and unlabeled data with label propagation. Journal of Software Engineering and Applications, 5(7), 2003.
  35. [43]Zügner, D. and Günnemann, S. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations (ICLR), 2019.
  36. [44]Zügner, D., Akbarnejad, A., and Günnemann, S. Adversarial attacks on neural networks for graph data. In SIGKDD, pp. 2847–2856, 2018.

Paper details

vlnc:W_7dbzyf6b
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents