Rethinking Label Poisoning for GNNs: Pitfalls and Attacks
Authors: Vijay Lingam
Mohammad Sadegh Akhondzadeh
Aleksandar Bojchevski
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Label Poisoning Attacks
Pitfalls
Primary area: learning on graphs and other geometries & topologies

Abstract: Node labels for graphs are usually generated using an automated process or crowd-sourced from human users. This opens up avenues for malicious users to compromise the training labels, making it unwise to blindly rely on them. While robustness against noisy labels is an active area of research, there are only a handful of papers in the literature that address this for graph-based data. Even more so, the effects of adversarial label perturbations is sparsely studied. More critically, we reveal that the entire literature on label poisoning for GNNs is plagued by serious evaluation pitfalls. Thus making it hard to conclude how robust GNNs are against label perturbations. After course correcting the state of label poisoning attacks with our faithful evaluation, we identify a discrepancy in attack efficiency of $\sim9\%$ on average. Additionally, we introduce two new simple yet effective attacks that are significantly stronger (up to $\sim8\%$) than the previous strongest attack. Our strongest proposed attack can be efficiently computed and is theoretically backed.

Published as a conference paper at ICLR 2024
RETHINKING LABEL POISONING FOR GNNS: PITFALLS AND ATTACKS
Vijay Lingam Mohammad Sadegh Akhondzadeh?
Aleksandar Bojchevski
CISPA Helmholtz Center for Information Security vi jijylingammm 81 06 @0gamill com, (makhondz, a. a.opsa//saa.occcooookk.o.o momi-koelna de
University of Cologne
ABSTRACT
Node labels for graphs are usually generated using an automated process or crowd- sourced from human users. This opens up avenues for malicious users to compro- mise the training labels, making it unwise to blindly rely on them. While robustness against noisy labels is an active area of research, there are only a handful of papers in the literature that address this for graph-based data. Even more so, the effects reveal that
adversarial label perturbations is sparsely studied. More critically, the literature on label poisoning for GNNs is plagued by evaluation pitfalls. Thus making it hard to conclude how robust GNNs against label perturbations. After course correcting the state of label poisoning attacks with our faithful evaluation, we identify discrepancy in attack efficiency of ~ 9% average. Additionally, we introduce two new simple yet effective attacks that are significantly stronger (up to 8%) than the previous strongest attack. Our strongest proposed attack can be efficiently computed and is theoretically backed.
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as a powerful tool to learn from graph- graph-structured data. From social network analysis and recommendation systems, to bio-informatics and traffic prediction, their wide-ranging applications highlight their importance (Wu et al. 2019b). Consequently, we need to understand their robustness, especially if we aim to integrate them in safety-critical domains. There is large body of work showing that GNNs are susceptible to feature and structure perturbations, which can significantly degrade their performance (see c.g. surveys by Sun et al. (2023). 3, Chen et al.
(2020). and Jin et al. (2. This vulnerability exposes them to potential adversarial attacks, thereby compromising the integrity of their outputs. Even if there is no adversary, we argue that understanding the worst-case robustness of model can be highly informative, especially when comparing models.
Among the various attack vectors, label poisoning poses a distinct threat. In many real-world scenarios, labels for training data are often generated through crowd-sourcing or other non-expert sources. For example, in a federated learning setting where multiple peers collaboratively train a shared model, any peer may submit potentially poisoned labels. Similarly, models are often trained on data scraped from the internet without careful quality control. This opens up an avenue for attackers to implant poisoned labels, thereby manipulating the learning process of GNNs. Label poisoning attacks can be subtle and challenging to detect, thereby complicating defenders' efforts to mitigate them. This is especially true for graphs since we cannot easily "see" whether the node's 's label is correct, unlike for e.g. images. Such attacks can be specifically crafted to manipulate recommendation or advertising systems, granting a competitive advantage (Fang et al. 2018 Zhang et al. 2021).
Recent work by Carlini et al. (2023) demonstrates the practicality of data poisoning attacks for crowd-sourced and publicly-crawled datasets. The strength of the poisoning attack depends on the data available to the attacker access to full/partial training labels/graph structure. For illustration purposes, we compute the optimal label flipping attack for the GCN model (Kipf & Welling 2017) on tiny version of the Cora-ML. dataset by exhaustively enumerating all possible label flips (more details in the $ B.I. We observe that only a single adversarial label flip can drop GCN's test performance from 81.27 45.04 64.3646 26, a staggering drop of ~1%
https: thu.. com/ / jayl. htw.jjyylliln9///mmmmm www.m///ettaaaaaee
a Poi soni moniingforre oGNNS

---

Published as a conference paper at ICLR 2024
We will show that similar results hold in general across all datasets and models, a relatively few flips are enough to significantly affect performance. Despite its potential impact, label poisoning for GNNs has been relatively under-explored in the research community. leaving critical gap in our understanding of their robustness. While label poisoning is better understood for non-graph data (Biggio et al., [201 Jin et al. 202T), graphs come with unique challenges due to label sparsity and the interdependence between nodes, We aim to fill this gap by conducting a comprehensive robustness analysis of GNNs under label poisoning, making key contributions.
1.
We pinpoint significant pitfalls in the evaluation setup of previous studies on label poisoning. These pitfalls make it nearly impossible to accurately interpret the results of previous studies, resulting in a distorted portrayal. The root issue is that prior assessments fail to accurately replicate the actions of a defender. By rectifying these pitfalls, we establish a more reliable and faithful evaluation framework for gauging the robustness of GNNs against label poisoning.
2. We propose two simple, yet highly effective, families of baseline attacks that stem from different approximations of the (NP-hard) bi-level optimization problem associated with label poisoning. Our two strategies, each with different advantages, rely on linear surrogates and meta learning respectively. These attacks are significantly stronger than previous ones, affecting both vanilla and noise-aware models. This demonstrates the pressing demand for more robust defense mechanisms, especially considering the transferability of our attacks, wherein a strategy devised for one model can effectively contaminate numerous other models.
3. We shed light on a curious phenomenon where unconstrained attacks perform worse than binary attacks, where the attacker is constrained to only flip among two classes. In addition to experimental evidence, we show that random binary flips lead to provably lower accuracy.
We show that the mixed integer linear program (MILP) associated with our linear surrogate attack can be efficiently solved by proving that its LP relaxation is integral. Moreover, we provide closed-form optimal solution for the binary variant which can be computed even faster.
BACKGROUND: THREAT MODEL, EXISTING ATTACKS & RELATED WORK
We focus on label poisoning attacks for semi-supervised node classification. The adversary can perturb the labels of a small fraction of training nodes, keeping the features and the structure unperturbed.
Problem setting. We are given graph represented by its [V] x |V] adjacency matrix A and its [V] x D feature matrix X, where V is the set of nodes. The D-dimensional features can be discrete continuous, and the graph can be directed, undirected, weighted unweighted. We represent the ground-truth labels as one-hot encoded row vectors in matrix Y (0. 1)12i*C where C' is the number of classes. We denote with Y, and Y, the labels corresponding to the subset of training (labeled) nodes V and the test (unlabeled) nodes V,, Given A, X, Yi we learn the parameters O* of a model ((0), e.g. a GNN, by minimizing some loss L (usually cross-entropy).
Threat model. The attacker can perturb the training labels Y; to reduce the performance on the test nodes. We assume that the attacker has complete knowledge of X. We consider three settings where the attacker knows: (i A and all ground-true labels Y: (ii) A, the ground-truth labels for the training nodes Yi only, and predicted labels for the test nodes Y,: and (iii) no access to A and all ground -ruth labels Y. We focus on (i) and defer (ii) and (iii) to $ B.8 In all settings, the attacker is only allowed to perturb Yi. The first setting corresponds to the worst-case scenario and is important for understanding the intrinsic robustness of our models, regardless of whether it is feasible to execute such attack in practice. We can write down the label poisoning attack as a bi-level optimization problem:
H
arg max L(0" A, Y.)
(I)
s.t. 0" =rg min HH),,, || H1 S 2
where H denotes the potentially poisoned training labels, E 10 is the perturbation budget, and [<[Vi]] is the maximum number of labels that can be flipped. The inner problem corresponds to training a model with potentially poisoned training node labels, while the outer problem maximizes the loss the test nodes, given the optimal parameters 0- Optimally solving the bi-level problem in Eq. I or often even just the inner problem itself, is intractable hNP-hard) in general. Attacks differ in how they construct an approximation this problem.
2

---

Published as a conference paper at ICLR 2024
Defense model. The defender is given dataset with potentially poisoned labels, but does not know which labels are poisoned. Since we're re dealing with poisoning, the defender trains the model from scratch. This could be vanilla model or noisc/poison-axe model they can use all available labels for training (e.g. label propagation) or split them into training and validation sets (e.g. GNNs). Often the defender also performs hyper-parameter tuning before
robust model. Depending
the
deployment since GNNs are sensitive to h-params (Shchur et al. 20188 Li & King (2020).
Heuristic-based attacks. The random label-flipping attack (RND) randomly selects a subset of training nodes within the budget, and then randomly selects incorrect labels for each selected node. The degree-based label-flipne flbel-flipping attack (DEG) selects the highest degree nodes given a budget, and randomly assigns incorrect labels. As we will show in 5 even these simple baselines can outperform some prior attacks under a fair evaluation.
Learning-based attacks. All previous attacks approximately solve Eq. 1 by using fixed surrogate model. They all replace the inner problem with a closed- form solution, but differ in how they tackle the outer problem. The poisoned labels are then applied to a target model.
Liu et al. (219 propose a gradient-
label propagation attack (LP) for graph-based semi- supervised learning (G-SSL) models. Note that this attack was primarily designed for binary-class datasets that are i.i.d in nature, with G-SSI. methods applied on top. Nonetheless, it can be adapted to our graph setting. LP replaces the inner optimization in [Eg. I with the closed- form solution of label propagation. They replace the loss in the outer problem with an expectation over Iearnable Bernoulli variables that model the probability of flipping the label of a given node. They optimize this new loss using a reparametrization trick and gradient descent.
Zhang al. 2020) build top of the LP attack and propose LAFAK (LFK) that replaces the inner optimization in Eqq.1 with a regression-based closed-form solution of a linearized GCN. They remove the non-linearities in 2-layer GCN (Kipf & Welling 2017p: SOFTMAX(A A RELU(ÁXe, 02) + SOFTMAX(A X0). where Å is the symmetric normalized adjacency matrix. and 0₁ and 0g are reparameterized into a single matrix E DxC Here, the (implicit) surrogate model is SGC (Wu al. 2019ap. Next, they replace the cross-entropy loss with a least squares surrogate loss, using regression to perform classification. That is, 0 = arg ming X 1i11 + >110 where ğt e {-1,+131M) is the vector of (potentially poisoned) binary training labels, X = X are the diffused features, (+), select the subset of rows corresponding to training nodes, and the regularization strength. Now, 0 = (X/ X + - X ÿt. Similar to LP, they substitute the non-differentiable parts of the outer problem with continuous surrogates and use gradient descent-based optimizer.
Liu et al. (2022) propose the maximum gradient attack (MG) based on label propagation. Unlike LP which uses similarity matrix that is constructed by applying Gaussian kernel the feature matrix, MG proposes multiple ways to construct propagation matrix A (e.g.. PageRank matrix, hidher-order adjacency matrix). Then, they greedily select the top nodes within the budget with the highest gradient w.r.t. the outer loss, and set their label to the false class with the highest index.
Binary vs. multi-class. The default implementation of LFK and LP support only binary labels. Thus, for multi-class datasets they consider only the subset of the graph whose nodes belong to the two most frequent classes, restricting their attack to flips among these two classes. Note, this restriction is only for the attack phase, during evaluation the entire (multi-class) graph is used. It turns out that this restriction to binary flips may strengthen the attack efficacy, as suggested by our theory in 4.3 As a side note, this binary approach may limit the maximum perturbation budget. In S B.6 we discuss this issue in detail and propose a minor bascline extension to alleviate it.
Discussion. All these attacks have shortcomings. The LP attack primarily built for G-SSL datasets that do not contain a graph, limiting its efficacy on message-passing based GNNs. LFK relies on several continuous surrogates to enable gradient flow. These approximations hurt its performance. However, coincidentally, restricting to binary flips boosts its attack performance. MG's greedy approach can be myopic. While these existing label attacks claim severe degradation in GNNs performance with minimal label perturbations, we identify serious flaws in their evaluation setup. In the following section (8 3). we discuss and fix these pitfalls and perform a faithful evaluation of the existing label attacks. We provide further discussion of broader related work in $ B.2
3

---

Published as a conference paper at ICLR 2024
Clean
RND
LP
LFK
MG
A Test Accuracy
82
72
52
Equalized
wo-Ip
w-hp
Small Val
0%
5%
15%
30%
0% 5% 15%
30%
0% 5%
15%
30%
Random splits.
b) Hyperparameter tuning.
Poisoned validation.
Figure 1: Previous evaluations use class class-equalized splits (P4), untuned models (P5), and umpoisoned (clean) and unreasonably large val set P6). We fix these pitfalls in (a), (b), and (c) respectively.
SIX PITFALLS AND REMEDIES
After careful inspection, we conclude that the evaluation of previous attacks does not simulate the full potential of defender. In short, the dataset splits and the training/tuning routine simulated by the attacker when evaluating the strength of their proposed attacks in the previous works we examined not realistic and flawed. the rest of this section, we carve out the specifics of the pitfalls we identified, empirically validate them with our experiments, and offer remedies. Here we show results on the Cora-ML (McCallum et al. 2000) dataset for the GCN (Kipf & Welling, 2017) model. In I provide detailed information the setup. In $ 1.17 we provide further experiments additional datasets and models which lead to the same conclusions. For the sake of completeness, we sweep the poisoning budget across the range [5%, 10%, 15% 20%, 30%] of training dataset. For the Cora-MI. dataset these budgets correspond to [7, 14, 21, 28, 42] training labels out of 2810 in expectation. In practice, smaller budgets are likely be more relevant. We plot our findings in Fig. 1
First three pitfalls. We focus on the common sparsely labeled scenario where the fraction of train nodes relatively small, |M] < [. J. P1. The first pitfall arises since all previous attacks evaluate on data splits with validation set size much larger than that of the training set (e.g. 500 validation vs 140 train nodes on Cora-ML in the default setting). Oliver et al. (2018) offer an extensive discussion on this pitfall for general semi-supervised learning (see their P.6). Briefly, in real-world applications the larger val set would instead be used as the train set. Also, h-params tuning would be noisier when using a realistically small validation set. P2. The second pitfall is the failure to report the standard deviation across multiple splits. This crucial since GNNs are highly sensitive to the split, especially for sparsely labeled data. We remedy these pitfalls by using validation and train set of the same size, and by reporting the mean and standard deviation across 10 splits (more details in B.8). P3. The third pitfall, is only evaluate attacks undefended models. We find that noise/poison-ant models can offer some robustness against these attacks. We explore this in detail in $
random split. In the (default) class-equalized setting both the train and val sets contain equal number of samples per class. This does not preserve the global class distribution and treats each class equally. Another potential way to split the dataset is to randomly sample nodes for train and val sets (referred to as random setting). We argue that this is more realistic, as the train/val class distribution would more closely align with the test/true class distribution. From Fig. aa), we deduce that switching to the random setting significantly degrades the performance of tabell-oisooing attacks. Compared the learning- bassed attacks which show a difference of up to 17%, the heuristic attacks (RND and DEG) are less susceptible to changes in data splits. LFK and I.P attacks flip pairs of popular classes, and MG attack always flips to the label with the highest index. The class distribution in all studied datasets is skewed with 2 or 3 majority classes (see [S B.15). Since the random setting has more samples from popular classes, the model has better chances at learning a more robust decision boundary and thus weakens the attack's efficacy.
P4. Class-equalized
P5. Hyper-paramette Even though this is well established (Li & King 2020), all previous poisoning studies still use the default h h-params to evaluate the effectiveness of their proposed attack. Since the default h params tuned work with clean (unpoisoned) labels they might be suboptimal. On OnFi.. T(b) we show
tuning. GNNs are usually highly sensitive to hyper hyper-parameteer parameters (h- (h-params).
4

---

Published as a conference paper at ICLR 2024
P1.P4.5..P
P4.P5.66
P5.P6
P6
No Pittalls
Test Accuracy
80
GCN
GAT
APPNP
CPGCN
60
40
20
0%
5%
15%
30%
0%
5%
15%
30%
0%
5%
15%
30%
0%
5%
15%
30%
Figure 2: Each bar corresponds to an evaluation setup with subset of pitfalls (LFK, Cora-ML). Pitfall P2 is fixed since we report standard deviations. P3 is fixed by evaluating the CPGNN defense.
the performance various attacks with and without tuning. Fine-tuning with only 20 configurations (see { B) can significantly deteriorate the attack, manifested as increase in test accuracy. The recovery in performance is more pronounced in learning- based attacks and at higher poison percentages. At 5% and 15% budget the claimed state-of-the-arr attack, MG, is ineffective the RND baseline. We observe this anomaly across models and datasets as documented in B.8) LFK seems to be the strongest attack followed by LP. Since tuning GNNs is relatively cheap (Table 13) and since the untuned model performs poorly, it is a reasonable assumption that the defender will tune their models.
P6. Clean validation set. All existing attacks assume in their evaluation that the validation set labels are clean (not poisoned). We hypothesize that having a clean (and large, see first pitfall) validation set can aid the model in recovering accuracy by avoiding overfitting on the poisoned train set. Additionally, it is unrealistic to treat the train and validation sets separately - if the defender has a clean validation set they can simply ignore the poisoned train set (see S 1. for detailed analysis). Note, unlike e.g. image classification, for cenissuperiised node classification both train and val set are usually small since | << [Vul, and often have equal size. To remedy this pitfall, we poison the available sparse set of labels Vi which the defender can use for training and/or validation as they fir Since we train GNNs, we create 10 different train/val sets from the poisoned Vi and report the average across splits. We refer to this as the CV setting, and on Fig. Ifc) efficacy of all attacks. This is expected, since the defender no longer has a clean validation set.
that it boosts the
Cumulative effect of the pitfalls. In Fig. 2] we sequentially apply the series of remedies and plot LFK's performance. Moving from class-equalized splits to random splits has the largest impact on average, followed by hyper-parameter tuning. Comparing the first and last bar for a given budget shows that the attack performance on average worsens, e.g. for the LFK attack on Cora-ML by ~9% across models. Additional comparisons are provided [ B.8 which lead to the same conclusions. We advocate for using our proposed evaluation procedure as it better reflects real scenarios. In S 4 we introduce our new attacks, which we compare against these baselines $ 5
LABEL POISONING ATTACKS
Motivated by the results in $ where we showed that previous attacks are not as effective as claimed, we design new simple and effective baseline attacks. These attacks are independent from the pitfalls but we discuss some connections in $ B.18 We propose two different strategies to approximate the bi-level poisoning problem in Fq. that rely on: (i) linear surrogate models and (ii) meta learning.
4.1 LINEAR SURROGATE ATTACK
We start by replacing the inner optimization problem with a linear surrogate for which we can obtain the optimal weights 0* in closed-form. We explore two different variants. First, similar to Zhang et al. (2000) we use an SGC (Wu et al. (2019a) surrogate which is equivalent to linearizing a vanilla 2-layer GCN (Kipt & Welling 2017). We use SGC, since despite its simplicity shows similar performance to its non-linear counterpart across datasets. Second, we use the Neural Tangent Kernel (NTK)
"Some methods, such as label propagation, use all labels for training, while others like GNNs split V/ into train/val sets and use the latter for early stopping/fine- -uningt Our attacks remain agnostic this.
5

---

Published as a conference paper at ICLR 2024
for an infinitely-wird wide GCN (Sabanayagam et al. 2022). We the NTK since it is theoretically well-founded and it has been shown to capture the behavior of its finite-width counterpart.
In both cases, unlike Zhang al. 22200) which only support binary labels, replace the inner problem with 0 arg ming || X H| 2 + || In this surrogate multi-output ridge regression problem, 0 E R DxC we regress against the one-hot labels H. thereby supporting multi-class problems. For the SGC variant X X and for the NTK variant X is the kernel matrix derived by Sabanayagam et al. (022) see S B. for more detail). The fooeed-fomm solution is readily obtained
as 0" = X; H where X (X*X X + A is a constant that can be pre-computed once for each dataset. Given our insights from pitfall P5 we choose the À that maximises the validation accuracy on average across splits, preventing overfitting to single split. Now, we rewrite the surrogate variant of Eq. I ass the following mixed-integer linear program (MILP):
min C(Y,, Y.) (0
(2a)
H -Yllo - 2cl
(2b)
P, X Hic 11
(2c)
(2d)
where H is a binary variable, L = [V] is the number of training nodes, and 1,. is the all-ones vector of size L. Here, Eq. 2b enforces the budget constraint, [q. computes the predictions Y, for
the test nodes, and Eq. 2d enforces a one-hot encoding. We explore several variants for the loss in
Eq. 2a "probability" for the true class. The benefit of this loss is that it is linear in Y, and Y... Alternativel, can compute the most likely label for each node, by computing the arg max over the rows of Y,,. This requires additional auxiliary binary variables to encode the arg max, making it inherently less scalable.
One choice is L(Y., P,, sum Y à Y,,) which is equivalent to minimizing the predicted
The MILP problem in Eq. 2 finds the optimal subset of nodes to perturb and which labels to perturb them to (via H). Next, we show that, surprisingly, the optimal poisoned labels can be efficiently computed by calling any LP solver (we use MOSEK). The proof $ A exploits total unimodularity.
Proposition 1. The optimal solution of Eq. 2 is integral, i.e. H E {0, 1) LxC when relaxing the MILP to LP such that H [0, 1) T
We also explore another variant where we fix the target label, e.g. the false label with the highest probability as predicted by a clean model (see [ B.5 for details). We call the first variant SGC and the second SGC-FIX. For SGC-FIX we only have to find the optimal subset of nodes which should be significantly easier. In fact, we have the following closed-fome solution.
Proposition 2. Given fixed target labels Yú the optimal nodes to poison are the subset of nodes corresponding to the smallest [cL]] negative elements of an L-dimensional vector e, where the 1-th element of e is computed as q = Eii Qupi where Q = X,,,, P
X Y Yi, and R = Yy-
See $ A for a proof. Intuitively, when Y7 is fixed we can rewrite the MILP in a canonical form as mimbe (0.1). c subject to 6" 1,. S eL where is a constant, which can be efficiently solved by returning the [eL.] smallest (negative) elements in
4.2 META ATTACKS
For the second family of attacks we take an orthogonal approach where we directly optimize the poisoned labels Y; via gradient descent. Since Eq. 1 is bi-level problem we need to differentiate through the inner optimization. Here, unlike the previous attack the inner problem is w.n.t the actual target model (c.g. the non-linear GCN) which is itself trained with gradient descent. Therefore, resort to computing meta gradients by unrolling the inner optimization for a fixed number of epochs and differentiating through it. Unrolled optimization is common in the meta learning literature, where the goal is e.g. to learn the optimal hyper- parameters (or the structure) of a model (Huang et al. 2020
We use numerically stable algorithms to compute X without explicitly computing the matrix inverse.

---

Published as a conference paper at ICLR 2024
Mujkanovic et al. 2022). Intuitively, one can think of Y "hyper- papperrprameters" to be optimized for the inner problem. At high level, most meta-attacks follow a similar procedure by unrolling the inner-level optimization for K steps during each iteration of the outer loop. However, the attacks differ precisely in the problem-specific instantiating of this recipe. We explore three different ways (standard, fixed, expanded) parameterize the poisoned labels.
Standard meta attack. We first initialize the free parameter matrix Yog E ERI.C. to learn the log-probability of flipping to given target label for each training node. We obtain Y by sampling proportional to the log pog-bbbbabiliiess in Ylog using the Gumbel-softmax trick (Jang et al. 2017 on each row. In the forward pass Yog is "hard" (one-hot encoding), while using the softmax probabilities in the backward pass. We also initialize a parameter vector b E R with the goal of learning which good candidate for poisoning. To enforce the budget we apply soft-top-k
subset of nodes followed by k-subser-selection (Paulus al. 2020) to obtain b top; We construct the final poisoned labels by H (lag(b)Y + diag(1, problem which we train for a fixed number of epochs, and use meta-gradients of b w.r.t. the outer loss for learning. During the forward pass we used hard top-k for b, sampled proportional to the respective soft-top-k scores which are used during the backward pass.
by We feed H into the inner optimization
Gumbel-softmax loss. The choice of loss function in the outer problem can impact the attack performance. The loss of interest is the 0-1 loss (i.e. the test accuracy), which is non-differentiable. There are several options to circumvent this issuc by constructing different approximations. The simplest idea is to just use the cross-entropy loss (which is also used in the inner problem) on the "soft" predictions Yi. Another approach which was shown to perform better for other attacks (see e.g. (Mujkanovic et al. (022)) is the margin loss, where we minimize the margin between the true class and the most probable false class. We propose a third alternative that exploits the Gumbel-Softmax trick. Specifically, in the forward pass we sample hard predictions from Y, using the Gumbel-Softman reparametrization trick, while using the soft predictions for the backward pass. That is for node i we sample a prediction via onehot (arg ma + Pic}) where 9e ~ Gumbel 1) and Pic is the predicted probability for class e obtained from the (i, c)-th entry of Yu. Given the one-hot encoded hard predictions, we can compute the accuracy via the Hadamard product with the ground-truth -trth Yu. We study the choice of loss functions and their effects in B.8.2 since our newly proposed loss performs the best on average we use it in the main experiments.
Fixed and expanded meta attacks. We construct a fixed one-hot Y E {0, 10,1) similar to our LSA attack by determining fixed target label for each training node (e.g. the most likely false class for a clean model). Similar to the standard meta attack, we let b learn to select the subset of poisoned labels, which now always flip fixed target label. We discuss the expanded variant in S B.3
daptive attacks. Our meta attacks are an instance of, so-called, adaptive attacks which were shown be significantly better than surrogate-based attacks. This bitter lesson was learned for both computer vision (Carlini & Wagner, 2017] AAhaaly et al.] 2018 Tramer et al., (020) and GNNs (Mujkanovic al. 2022). As we will see in S 5| adaptive attacks are not always superior for label poisoning.
4.3
THE CURIOUS PHENOMENON OF BINARY FLIPS
We explore additional variants of all of our attacks, where instead of allowing the attacker to select the poisoned labels from the entire training set, we restrict their access only to subset of labels corresponding to two classes. We refer to these as -BIN variants. This will allows us to compare the the prior baselines on their own terms since they do not natively support multi-class attacks. Similar to LAFAK we choose 2 candidate classes and always flip between them, e.g. the two most frequent classes. In [S 5) we see that practice the binary variants perform surprisingly well, often even better than their multi-class variants. This is interesting, since in theory any feasible solution for the binary variants is also feasible for the multi-class variants, i.c. multi-class is strictly more powerful. Even the RND and DEG baselines benefit. We investigate this phenomenon experimentally and theoretically.
Surrogate loss gap. We first identify a discrepancy between the binary and multi-class performance caused by the use of least squares surrogate loss for the inner problem. We compute the optimal attacks and compare models trained with least squares (LS) vs. cross-entropy (CE). Then we compute the difference in accuracy when we switch from L.S (the attack's surrogate) CE (the defender's
7

---

Published as a conference paper at ICLR 2024
Table Difference in performance when training the model with cross-entropy vs. least squares loss for Cora-ML. The multi-class at- tack has significantly higher A in accuracy, overfitting to the linear regression surrogate.
Table 2: Accuracy comparison between multi- class and binary SGC attacks without hyper- parameter tuning, on Cora-ML and GCN. The multi-class attack is stronger here. but not after tuning (see Fig. 3) indicating overfitting.
A
bin acc
A mul
A bin loss
A loss
multi
binary
5%
-0.02
+1.79
+0.76
+0.78
5 %
74.49 (2.22)
75.01 (1.13)
10% %
+1.55
+3.76
+0.86
+0.88
10% %
67.02 (2.43)
70.35 (1.80)
15 %
+0.69
+6.01
+0.95
+0.96
15 %
59.10 (1.81)
65,50 (1.86)
20% %
-0.82
+8.36
+1.09
+1.06
20% %
54.76 (1.46)
60.08 (3.04)
30% %
-2.18
+9.88
+1.33
+1.27
30%
47.76 (1.45)
45.78 (4.20)
actual evaluation) denoted with A bin for the binary attack (and Ame for the multi-class attack). In Table I we that difference in accuracy is negligible when using the binary attack, and quite large for the multi-class attack, even growing with increased budget c. The loss shows no significant difference. Thus, the binary variants perform better since they incur smaller surrogate loss gap.
acc
Adversarial overfitting, We also identify overfitting to the default h- b-parameters. In Table 2 we see that when run the SGC attack
untuned model, the multi-class variant is better, however, this is not true for the tuned model (see Fig. 3). Both findings indicate that the unconstrained multi-class attacks are more likely overfit to either the surrogate the untuned model and thus are unable to find poisons that generalize to the final tuned model used by the defender. Binary attacks are "regularized". Finally, for the random heuristic attacks we can prove that the binary variant optimal.
Proposition 3. Let the adversary flip label p to label q # p with probability & by and retain label p with probability 1 - where e is the poisoning budget, tng E {0, 1) indicates whether the adversary allowed to flip p to q, and Eggp lyq is the number of allowed classes. The test accuracy of the Bayes optimal classifier trained randomly flipped labels is minimized for =1 (binary flips).
EXPERIMENTAL EVALUATION
We conduct comprehensive comparison between our family attacks and all baseline methods. Furthermore, for the first time and in response to one of the identified pitfalls, we assess our attacks against two defense mechanisms specifically designed to withstand label perturbations: CPGCN (Zhang et al. 2020) which introduces clustering-basee based loss, and RTGNN (Qian et al.), which uses self-reinforcement and consistency regularization. Label poisoning can also be viewed as an extreme version of feature perturbation. To account for this, we also evaluate our strongest attack and the strongest baseline (LFK) against ALBATIONGCN (Scholten et al. 2022), one of the recent certified defenses against feature perturbations for GNNs (seels 16). See for implementation and tuning details. In B.&we we provide additional results, including larger scale graphs and ablations. The change in homophily due to poisoning is minor (8 B.1T). In all experiments, we use the final evaluation setting (CV) that we propose in which avoids all of the identified pitfalls.
SGC
SGC-FIX
SGC-BIN
META
META-FIX
META-BIN
A Test Accuracy
0.4
GCN
GAT
CPGCN
0.3
0.2
0.1
0.0
5
10
20
25
5
10
20
25
5
10
15
20
30
Poison Percentage
Poison Percentage
Poison Percentage
Figure 3: Different variants of the attacks that we propose. Binary variants are best average.
8

---

Published as a conference paper at ICLR 2024
RND-BIN
MG
LFK SGC-BIN
NTK-BIN BIN
Ours
Baselines
DEG-BIN
LP
META-DIN
Houristics
Á Test Accuracy
0.4
GCN
CPGCN
RTGNN
0.3
0.2
0.1
0.0
5
10
15
20
25
30
10
15
20
25
30
5
10
15
20
25
30
Poison Percentage
Poison Percentage
Poison Percentage
Figure 4: Our strongest attacks significantly outperform the baselines across various models.
Attack variants. We first study the different variants of our attacks. We denote with -FIX and -BIN the fixed and binary subset variants respectively. In Fig. 3 we show the difference in the accuracy of clean vs. poisoned labels for different budgets. We infer that on average linear surrogate attacks are better than meta-based attacks. One reason is the fact that we are able to solve the MILP in Eq. 2 exxctll (and efficiently). That is, we find the optimal attack (given the surrogate), while the meta-based attacks suffer from optimization issues. Binary variants are significantly stronger than multi-class. Similar trends hold for the baselines (see S B.8
We discussed this phenomenon in 4.3
Attacks. For ease of comparison, we pick the best performing (on average) attack from each family that we introduced in [ 4 namely: SGC-BIN, NTK- BIN and META-BI BIN. We compute the difference in test performance between the clean-accuracy and poisoned accuracy for each budget across attacks, and plot them on Fig. 4 Higher difference shows a stronger attack. We observe that all our attacks (in solid), particularly SGC-BIN attack, outperform baseline attacks with maximum gains of up to 13%. We observe similar trends across different models and datasets as we show B.8
CPGCN and RTGNN are two recent defenses that have been introduced to specifically tackle pairwise noise in labels where the flips between classes is fixed. Attacks like LFK, LP, and the binary variants of our proposed attacks can be viewed as (adversarial) pairwise noise. While RTGNN has claimed impressive recovery in performance with pairwise noise rate of up 40%, we find that our simple attacks can cause debilitating effect on its performance with as low as 10% noise in labels.
Surprisingly the SGC-based attacks transfer well to a wide range of vanilla GNNs as well as robust GNNs. Moreover, our simple attack formulation significantly outperforms prior attacks that use complicated routines. contrast to the success of meta-gradient attacks for graph/feature perturbations (Mujkanovic et al. 2022), we observe meta attacks to be inferior on average.
Ablation and limitations. We further examine how each attack performs per split, and also quali- tatively analyse the effect of poisoning on the learned representations. These results are available is B.7 Moreover, our attacks are unsurprisingly even stronger on the default (flawed) setting as show in & 1. While it may not always be easy implement our threat models in practice we still gain significant insights into the inherent resilience of the models. Our theoretical insights (Proposition 3) apply only random flips, and extending this to the worst-case is left for future work.
DISCUSSION AND CONCLUSION
There are two main messages in our work. First, careful evaluation of poisoning attacks is critical to accurately assess robustness. All examined previous studies commit serious pitfalls for which we provide remedies. The crux of the issue is faithfully simulating the defender when testing an attack, which includes proper tuning and splitting strategies. Second, simple label poisoning attacks are surprisingly powerful- - all examined models, including those designed to be robust, are highly vuinerable. Interestingly, contrary to popular conceptions, in our setting linear surrogate attacks outperform adaptive meta attacks. We gave experimental and theoretical insights into a curious phenomenon of why binary variants perform better compared to their multi-class counterpart. It would be interesting to study this in more depth in the future. Our findings highlight the urgent need to further study poisoning attacks, well develop robust defenses and certificates against them.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We offer comprehensive technical descriptions of our proposed attacks in 4 The hypper-parameter ranges we explore for both the attack and defense phases are included in the initial section of B We provide proof' for our propositions in A Furthermore, we make our code publicly available.
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Proceedings of the Asian Conference on Machine Learning, Proceedings of Machine Learning Research, 2011.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: inductive learning via ranking. In International Conference on Learning Representations, 2018.
Unsupervised
Nicholas Carlini and David A. Wagner. Adversarial examples are not easily detected: Bypassing detection methods. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017.
Nicholas Carlini, Matthew Jagielski, Christopher A. Choquette-Choo Daniel Paleka, Will Pearce, Hyrum Anderson, Andreas Terzis, Kurt Thomas, and Florian Tramèr. Poisoning web-scale training datasets is practical, 2023.
Liang Chen, Jintang Li, Jiaying Peng, Tao Xie, Zengxu Cao, Kun Xu, Xiangnan He, and Zibin Zheng. A survey of adversarial learning on graphs. ArXiv, 0bss/2003.05730 2020.
Minghong Fang, Guolei Yang, Neil Zhenqiang Gong, and Jia Liu. Poisoning attacks to graph- based recommender systems. In Proceedings of the 34th Annual Computer Security Applications Conference. Association for Computing Machinery, 2018.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs In Proceed- ings of the 34th International Conference Neural Information Processing Systems, 2020.
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, 2020.
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Vota-R, and Bo Li. Manip- ulating machine learning: Poisoning attacks and countermeasures for regression learning. IEEE Symposium on Security and Privacy (SP), 2018.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In International Conference on Learning Representations, 2017.
Wei Jin, Yaxing Li, Han Xu, Yigi Wang. Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adversarial attacks and defenses on graphs. SIGKDD Explor. Newsl,, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
10

---

Published as a conference paper at ICLR 2024
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Interaational Conference on Learning Representations (ICLR), 2017.
Yaoman and Irwin King. AutoGraph: Automated graph neural network. In Neural Information Processing. Springer International Publishing, 2020.
Hongshuo Liang, Erlu He, Yangyang Zhao, Zhe Jia, and Hao Li. Adversarial attack and defense: A survey. Electronics, 2022.
Vijay Lingam, Manan Sharma, Chanakya Ekbote, Rahul Ragesh, Arun Iyer, and Sundararajan Sellamanickam. A piece- wise polynomial filtering approach for graph neural networks. In Machine Learning and Knowledge Discovery in Databases. Springer International Publishing, 2023.
Ganlin Liu, Xiaowei Huang, and Xinping Yi. Adversarial label poisoning attack graph neural networks via label propagation. In Computer Vision ECCV 2022: 17th European Conference, Proceedings, Part V. Springer-Verlag Verlag. 2022.
Xuanging Liu, Si Si, Xiaojin Zhu, Yang Li, and Cho-Jui Hsieh. A Unified Framework for Data Poisoning Attack to Graph-Bast Baspl- Superiipe Learning. 2019.
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Scymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojehevski. Are defenses for graph neural networks robust? In Advances in Neural Information Processing Systems, 2022.
Avital Oliver, Augustus Odena, Colin Raffel, Ekin D. Cubuk, and lan J. Goodfellow. Realistic evaluation of deep semi-supervised learning algorithms. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Diane Oyen, Michal Kucer, Nicolas Hengartner, and Har Simrat Singh. Robustness to label noise depends the shape of the noise distribution. Advances in Neural Information Processing Systems, 35:35645 -36666, 2022.
Max B. Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris Maddison. Gradient estimation with stochastic softmax tricks. In Proceedings of the 34th International Conference Neural Information Processing Systems, 2020.
Siyi Qian, Haochao Ying, Renjun Hu, Jingbo Zhou, Jintai Chen, Danny Z. Chen, and Jian Wu. Robust training of graph neural networks via noise governance. WSDM '23. Association for Computing Machinery.
Mahalakshmi Sabanayagam, Pascal Mattia Esser, and Debarghya Ghoshdastidar. Representation power of graph convolutions: Neural tangent kemel analysis. ArXiv, 2022.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized message cesssage-iteerception smoothing: Gray-box certificates for graph neural networks. Advances in Neural Information Processing Systems, 2022.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. ArXiv, 2018.
L. Sun, Dou, C. Yang, K. Zhang, J. Wang, P. S. Yu, L. He, and B. Li. Adversarial attack and defense graph data: A survey. IEEE Transactions Knowledge amp; Data Engineering, 2023.
Zhiyi Tian, Lei Cui, Jie Liang, and Shui Yu. A comprehensive survey poisoning attacks and countermeasures in machine learning. ACM Computing Surveys, 2022.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems, 2020.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks, In Proceedings of the 36th International Conference on Machine Learning, 2019a.
11

---

Published as a conference paper at ICLR 2024
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2019b.
Hengtong Zhang, Changxin Tian, Yaliang Li. Lu Su, Nan Yang. Wayne Xin Zhao, and Jing Gao. Data poisoning attack against recommender system using incomplete and perturbed data. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
Mengmei Zhang, Linmei Hu, Chuan Shi, and Xiao Wang. Adversarial label fhip-in attack and defense for graph neural networks. In 2020 IEEE International Conference Data Mining (ICDM), 2020.
12

---

Published as a conference paper at ICLR 2024
A
PROOFS
When the target labels are fixed we can efficiently obtain the optimal subset of poisoned nodes in a closed-form solution with Proposition 2 However, even when we optimize over H, i.e. optimize over both the subset and the target labels, we can still solve the MILP efficiently. We will show that relaxing H from {0, 1] 1.x to [0. 1] Fxx in Eq. still results in an integral (i.e. binary) solution. Therefore,
solve the MILP by solving the corresponding relaxed LP.
Proof Proposition 7y. Let M = N C. With L(Y,, P,) - sum Yu 2 Pn) we can rewrite Eq. 2 in the following canonical form
min c² x w (0,11)
Aæ =
Ga I h
where
IN.... IN. O). IN is the identify matrix, O is N M zero matrix, b 1N the
times
-IM
-IM
ones vector, G
=
IM
Is OM is the zeros vector, and h = [-vec Y)), vec vec(Y))) c2N] and
0M
1s
c= vec Ve, X,) Here, Ar implements the one-hot constraint, while Ga S implements the T.1- T-1-norm budget constraint, where we have twice the number of variables to encode the absolute value. Since b and h are integral (because Y, is one-hot encoded), to show that the optimal solution integral only need show that A and G' are totally unimodular. Since the identity matrix n is totally unimodular, the result directly follows given the fact that is totally unimodular then so are -T,T" [T. I]. and TT, T
Proof Prrposiiionn 2). When the target labels labels fixed we rewrite the MILP from Eq 2 in terms of auxiliary variables that control the subset poisoned labels. The resulting MILP is:
min C(Y.:: Pa)) be 1
(3a)
H diag(( (b) o Yi + diag(1, b) Yi
(3b)
Y, = X,X.H
(3c)
b" 1 EL
(3d)
Given L(Y,, Pv) = sum Y, C Y,) we can rewrite the MILP in Eq. 3 (and equivalently Eq. 2 as
arg argmin vee (Y.)² vec ( b" EN bE(0.1)M
We can simplify Eq. without changing the minimum by omitting the terms that do not depend on
arg min vec(Y.,) "r.ce be 10,1)x
vvc (x,Xi (diag(b) o (8 ( xi))
6" IN SeN
(5)
Now we define Q = X, P - y Yi and R = Yu we can again rewrite as:
arg min b be (0,1)
6d b=1n SeN
where the (-th element of is computed as q = E QuPlyRey. This follows since the objective in Eq. 5) equuas Enz QQ Pt, R. This problem is equivalent to selecting up to elements from c such that their sum is minimized. The optimal solution is to select the |eN] smallest negative elements (or all negative elements if the number of negative elements is [eN]).
13

---

Published as a conference paper at ICLR 2024
Proof Prrposition 3/. Our proof relies the theory about robustness to label noise that recently derived in Oyen et al. (2022). We denote with Y* the random variable corresponding to the ground- truth labels, and with Y the random variable for the noisy labels. We define the distribution that
randomly flips ground-truth y* to noisy Y as:
[1-6 p=
1.
p p
From the definition, Y Y* a multinomialy distributed and 1/pg determines which noisy (poisoned) label is chosen. Let X denote the random variable for the features.
Denote with f()), = Prob[Y = q X = x = Ep- (x)), the noisy posterior of the Bayes optimal classifier, where f (x)g is the analogous clean (unperturbed) posterior. From the definition of Uly (and (pg) we that controls the number of allowed target classes, and 1 corresponds to binary flips. Technically, for 8 = 1 each class can choose a different (but single) target class. This slightly more generally that our binary variants. For classes, we recover the multi-class variant of the random heuristic baseline.
1, where C is the total number of
Oyen al. (2022) showed that clean accuracy (for class q) depends on s:
fq
[arg max [(r); = g) Y = a ~ 1 + exp s+1
rs()
(6)
-2f 1) (E- x41
where 1 -B(((()) They also show that the noisy accuracy (for class q) depends on 8:
E[I(arg max f(z); 9) Y = q fq (1- (1- c(s 1)
+ c ( c(s c(s 11
To prove Proposition 3 we need to show that the clean accuracy (for class q) in Eq. 6 as a function for each class q. Analogously, one easily show that Eq. is also
of is minimized for minimized for 8 = 1, but we focus on Eq. since it the more relevant quantity for our setting.
We will prove that the function r(s) in Eq. is monotonically increasing for 1,2,.... 11 First, we need to find its derivative w.r.t. and analyze its sign. We have:
1112/ +
fg Vr(s)
8
(-1 + 2 2l +8) [1+S]² I+s
x
(-1+ + 2f())
c- 14s)
(-1+ 2f (1 +s) (c- Its
(8)
8
82
x
(-122/na (f))
2
1 lte
We need to analyze the sign of each component this expression. Since, 0 fr < 1 the first term is non-negative. The second term is always positive due to the exponential function. The last term is positive due to the square in the denominator.
It remains to analyze the sign of the third term inside the largest parentheses. This term expands to:
2
2
2f
1
2fz
(1+s)²
(1+ 8)2
(1+3}*
(1+
1
1
With some algebra show that the term simplifies
(E - 2fze)
(9)
s2
14

---

Published as a conference paper at ICLR 2024
This means that the sign of the entire expression is determined by the sign of Eq.. First, we consider
the case that 1 < fq I 1. Since s is positive we only care about the nominator which we can
rearrange as e(1 - 2 Since 0 < < 1 is positive we need to show 1 - 2f < 0. Given that
f 1. we have that 2f; > 2. This implies that 2 > 1 since is positive and 1 in the worst-case. Which means 2 < 0.
Now, combining all the components: the negative sign in front of the derivative and the negative term (f-2 together make the derivative Vr(s) positive for all & = 1,...,C. C 1.
It remains to consider the case where f < 1. Similar to Oyen et al. (022) we argue that in this case the classification no better than random chance which would give vacuous result since in this case label noise actually would improve (rather than hurt) the performance.
B APPENDIX
The appendix is structured as follows. B. contains additional details on the motivation experiment we introduced in the main paper. In B.2, we provide extended discussion of related work. In $ B.3 we provide details on the expanded meta attack. S B.4 contains details regarding our NTK -bseed attacks. In B.3 we provide additional details on the variants of our LSA attack. In B.6 provide details on extending the baselines to
In S B.7 we provide qualitative and quantitative analysis of poisoning attacks. In B.8] we provide additional experiments along with ablative studies to offer more insights. /S 8.9 provides details on dataset statistics. In SS B. 10 we show how label poisoning attacks can be thwarted if a clean validation dataset is assumed to be available (unrealistic setting).{S I B.I...diaa discusses the effect of label poisoning on graph homophily. In B. we evaluate our attacks on the previously used (flawed) setting. In S B.13 we study the effectiveness of our attacks under partial information scenario. B.13 provides timing analysis for our proposed evaluation setting. /S B.15 B.15 provides label frequency analysis for our benchmark datasets. In | 1.16 we evaluate our attacks against certified defense model. In i 1.17 we provide additional ablation studies on pitfalls. Finally, in ß B.18) we provide insights on the connections between the identified pitfalls and the attacks we devised.
First, we discuss how we tune the hyper-parameten in both the attack and the defense phase of our evaluation.
Attack phase tuning. For our LSA family of attacks, we fine-tuned the regularisation term within the range [le-3, 1e3] in logarithmic steps. For the meta attacks, we set the learning rate for the inner and the outer routine optimization to 1c-2 and le-1. The weight decay for both the optimizers are set to 5e-4. The number of inner optimization iterations (epochs) is set to 15. Additional gains in the attack strength can be achieved by further fine-tuning these hyper-parameteed this due lack of computational resources, since our evaluation setup is already quite expensive. For the rearning-based baseline attacks (LP, MG, LFK), we sweep through the hyper-parameters ranges suggested by the authors in their papers.
We refrain from doing
Defence phase tuning. Post obtaining the poisoned labels, as identified in our of pitfalls 3 we perform thorough dyper-parameter tuning of the target model. Specifically, for the shared general hyper- parametersses we sweep the following ranges: 10.1, 0.01, 0.05, 0.08] for the learning rate, [0.0, 0.005, 0.0005, 0.00005) for weight decay, and [0.3, 0.5, 0.7] for dropout. We fix the hidden dimensions to 64, again due to limited computation resources. Model specific hyper-parameter are tuned in the ranges suggested by the respective papers. We empirically observe that higher learning rates allow models to recover better from label poisoning attacks. We use Optuna (Akiba et al. 2019) to optimize the hyper-paramett parameters search, and set the number of trials to 20. For learning we use the Adam optimizer (Kingma& & Ba 2015), with 1000 maximum number of epochs and an early stopping patience of 100. The majority of our experiments are run on an Nvidia k80 GPU with 24GB memory, and the remaining experiments were run using A 100 GPU with 40GB of memory.
15

---

Published as a conference paper at ICLR 2024
B.1 MOTIVATION EXPERIMENT
In the motivation experiment discussed in the main paper, we focused on the Cora-ML dataset and extracted a sub-sample from its largest connected component. This sub-sample referred to as Cora-ML-ttiny, and consists 93 nodes categorized into 3 classes. To conduct our analysis, we created 10 distinct splits for training, validation, and test sets, each with a size of 19, 19, and 55, respectively. By exhaustively examining all possible label flips within a budget constraint of 1, we discovered that a single ad adversarial label flip could lead to a significant reduction of ~ 17% in test performance on average.
B.2 EXTENDED DISCUSSION OF RELATED WORK
Adversarial attacks for machine learning (ML) an active and important area of research, especially with ML applications becoming ubiquitous, and have been studied extensively in the literature (Jin cet al. 2021 Sun et al. 2023 Liang et al. 2022). Attacks can be broadly classified into evasion and poisoning. For evasion attacks the model is fixed and the attacker perturbs the input at test time. Evasion attacks are conducted during the testing phase, where the model is fixed and the attacker perturbs a test instance to degrade model performance (Biggio & Roli, 2018). Poisoning attacks are conducted before the model is trained, where the attacker can perturb the training data with an intention to degrade model performance control model behavior. Poisoning is significantly more challenging than evasion since it results in difficult bi-level optimization problem.
Robustness of GNNs. Currently, we have an extensive body of work on the (adversarial) robustness of GNNs. The overwhelming majority of studies focus on adversarial attacks that add or remove a small fraction of edges and/or perturb the node features. Consequently, various heuristic defenses have been developed, as well certificates to provide provable robustness guarantees. For a detailed overview of both attacks and defenses we recommend the surveys by |Sun et al. (2023), Chen et al. (2020), and Jin al. (222I), Label poisoning attacks, despite their importance and potential impact, have been surprisingly gly sparse with only a few exceptions (Liu et al. 2019 Zhang et al. 2020: Liu et al. 2022). Interestingly, Mujkanovicc et al. (2022) recently showed that adaptive attacks designed specifically to circumvent a given target model or defense - are still able to manipulate almost all models. In other words, have made significantly less progress than it initially appears towards designing robust models. One conclusion from their work is that we have to carefully think about the evaluation setup avoid overly optimistic results. This echoed our pitfalls findings.
Poisoning attacks. Most poisoning attack assume that the attacker has access to the training data, and position the proposed attack worst-case robustness analysis. Such attacks have been extensively studied for classical ML models like SVMs (Biggio et al. (011). as well as recent (deep learning) models. Lots of different threat models have been considered, including allowing arbitrary changes (both features and labels), clean label poisoning (only features), and poisoning only the labels, which our focus. See Jagielski et al. (2018) and Tian et (2022) for a comprehensive overview.
B.3 EXPANDED META ATTACK
We first construct Y E {0, 10 by enumerating over all possible false (one-hot) labels for every node in the training set. Next, we initialize a parameter matrix B E NxC-IXX from a uniform distribution. The idea is to learn B to select a good subset of poisoned labels. To enforce the budget we apply soft-top-k followed by k-subser--seeen selection (Paulus et al. (2000) on top of vee( B) where vec(.) vectorizes the matrix |
We construct the final poisoned labels as:
C-1
H = (BO
+ ((1 B) Yrse:
(10)
0=0
We feed Y into the inner optimization problem which we train for a fixed number of epochs, and use meta-gradients B w.r.t. the outer loss for learning. During the forward pass we used hard top-l for B, sampled proportional to the respective soft-top-k scores which are used during the backward pass.
"We place no additional constraints on B to ensure multiple flips are not selected for the same label. In practice this is not issue, since the optimizer learns the entire budget and select k-unique label flips.
16

---

Published as a conference paper at ICLR 2024
B.4 NTK ATTACK
Our variants of the NTK-based attacks are exactly the same as our SGC variants, except in how we construct X. For the NTK variants, X corresponds to the NTK kernel matrix for 2 layer ReLU GCN derived by Sabanayagam al. (2022) (see Eq. in their paper). Given X generate poisoned labels following the procedure in $ 4.1
B.5 ADDITIONAL DETAILS ON THE MILP FORMULATION OF LSA
In one variation of our LSA attacks instead of learning H, we construct it by selecting a subset of nodes to poison from preset target false labels Y,
As we showed in Proposition 2 the benefit of fixing Y is that we can obtain a closed-form solution for the MILP. We explore the following variants:
Y MMMARIIN: we perturb labels to the false label with the highest probability as predicted by clean model (trained using ground truth training labels).
Y-RANDOM: we perturb labels to randomly chosen false class.
-BBNAARY+: we sort all classes w.r.t their frequency in a descending order and pair consecutive classes to flip them.
We compare these variants for in S B.8 In the main text we use YMRAGIN for the -FIX attacks.
B.6 EXTENDING THE BASELINES TO MULTI-CLASS
As consequence of the binary-class approach, the baselines might have limit on the maximum perturbation budget. For example, in the default (previously-used, non-CV) evaluation setting for the Cora-ML. dataset the candidate set of potential flips of size most 20% since Cora-ML. has classes and the two most frequent classes span up to 20% of the training set depending Therefore, LFK and LP by default cannot accommodate higher budgets. To enable this, while not deviating from the original design of the attack, propose minor extension. We first exhaust the 20% budget by perturbing labels the two most frequent classes and then we fix these perturbed labels. For the remaining budget, perturb the clean labels, but by restricting the attack scope a candidate set consisting of the next two most frequent classes. This process is repeated until the budget is completely exhausted. The multi-class setting can be handled better, however, we restrain from such adaptations to remain true to the original design of the attack. This also means that for the 20% budget, in the previous evaluation setting, LFK and LP become equivalent and deterministic because all the labels of the nodes in the candidate set are flipped to their counterpart. Note, that this issue is not present once we apply our remedies from and is only relevant for the experiments showing the pitfalls of previous evaluations.
the split.
B.7 QUANTITATIVE AND QUALITATIVE ANALYSIS OF POISONING ATTACKS
On Fig. 5w show how many times a given attack wins, i.e. leads to lowest accuracy, across all splits and all models (for Cora-MI and Citeseer). Different variants of our linear attacks win most often.
Analysing the poison. Finally, we study how the learned representations change before and after poisoning with SGC-BIN. On Fig. (left) nicely according to the class shown with different colors. We also see that the subset of poisoned nodes (shown with cross) is spread out. The poisoned representations (right) for different classes highly overlapping. Moreover, the two target classes that we flip (green and pink) overlap the most.
that for the clean model the representations cluster
B.8 ADDITIONAL EXPERIMENTS
B.8.1 ADDITIONAL. EXPERIMENTS ON STRONGEST ATTACKS
To extend our main paper analysis on strongest attacks, we provide additional experimental results for strongest attacks SGC-BIN and META-BIN) several datasets and models. We plot the
17

---

Published as a conference paper at ICLR 2024
500
Cles oead
43
-00
Figure 5: Strongest per split.
Figure 6: t-SNE of the logits before and after poisoning.
results in Fig. Our findings from the main paper that our attacks significantly outperform previous attacks still hold.
B.8.2 EFFECT LOSS FUNCTIONS PROPOSED META ATTACKS
We study the effect of different loss functions Cross Entropy, Margin, and the proposed Gumbel Softmax loss, on the META attack for the Cora-ML dataset. We tabulate the results in Table 3) We can observe that the proposed Gumbel Softmax based loss function boosts the attack performance in general.
Table 3: Effect of loss functions for the proposed META attack on the Cora-ML dataset.
Poison Ratio
Cross Entropy Loss
Margin Loss
Gumbel Softmax Loss
5%
78.51
79.25
79.80
10%
75.96
75.27 11.93
73.35 1,.34
15%
67.78
68.7543.20
65.81 :3,30
20%
63.36
63.88
61.60
30%
16.13
56. 172.74
54.53
B.8.3 SCALING OUR ATTACKS TO LARGER GRAPHS AND LARGER NUMBER OF CLASSES
To further study the efficacy of proposed attacks, extend analysis two additional datasets.
Specifically, we evaluate on the CoraFull dataset (Bojchevski & Günnemann 2018) that contains 70 output classes, and the OGBN-ArXin dataset (Hu al. 2020) medium sized graph with 169K nodes. Following Lingam et al. 2023), we apply a dimensionality reduction on the node features of CoraFull using PCA (top 500 dimensions). The statisties for all datasets are tabulated in Table 7
Larger number of classes. Since the number of classes for CoraFull is relatively higher compared to the other datasets, the choice of how we fix Y can be potentially more impactful. Therefore, we compare the three variants outlined in / B.5 against the baselines. We can infer from Table 4]that our attacks outperforms existing attacks, and that the -IINARY+ variant is the best average. These results signify that our attacks also scale well to datasets with larger number classes.
Table 4: Comparing different attacks on the CoraFull dataset. The strategy how initialize Y can impact the attack performance. The -MARGIN and -BINAR++ variants outperform -RANDOM.
--MAGIIN
Y-BINAR++
Y Y-RANDOM
DEG
RND
LP
MG
5%
56. 56.14 14..54
55.96
57.41 +0.52
55.70
57.01
57.38
56.1 19
10%
51.27+0.54
50.221084
54.19.00.00
54.022...0
55.21
53.52+0.27
52.15
15%
46.31 +0.57
43.99.1027
51.67 +0.69
52.86
54.7444.73
49.66
47.5K 47.58_0.58
20%
41.47
38.1044..4
48.30
51.53 51.53
53.5644.5a
49. 49.08
43. 03.02220.56
30%
33.29 +0.68
27.92
40.93
48.5644
51.29
49.10+0.10
31.71 $1.71=0008
18

---

Published as a conference paper at ICLR 2024
Table 5: Comparing different attacks on OGBN-ArXiv.
Table Evaluation the extended vari- ant of our meta attack GCN model for different datasets.
Our SGC-BIN attack also scales to large graphs and still outperforms existing attacks by significant margin. The LFK attack, with its current implementation, could not be executed because of Time Limit Exceeded error.
Cora-ML
Citeseer
Pubmed
5 %
80. 80.68
70.62
76.
SGC-BIN
RND
DEG
LP
MG
LFK
10%
1..5
68 08.8852.77
73.20
1 %
64.31
67.14
66.56
66.15
67.21
TLE
15%
77.76+1.30
66.9621.50
69.02+3.00
3
62.17
67.09
66.36
60.56
66.69
TLE
20%
1..34
64.24g33.0
61.28
5
48.20
66.90
66.12
55.62
66.72
TLE
30%
71.73
60.08 23.41
50.51
Larger graphs. Next, we study the medium-sized OGBN-ArXiv dataset to test scalability to larger graphs. Since the OGBN-ArXiv dataset contains large number of training nodes, we evaluate the attacks on budget ranges (1% 11% 3%, 5%%.. We also use the default splits since the data is chronologically split. In Table 5 we see that our proposed attack, SGC-B BIN, outperforms existing attacks.
B.8.4 CONFUSION MATRIX ANALYSIS
To analyse how the test node predictions are affected by the strongest baseline attack (LFK) and our strongest proposed attack (SGC-BIN), we plot the confusion matrices for the 15% budget in Fig. Even though both LFK and SGC-BIN poison the training nodes belonging the same two classes (class 2 and class 4), after the SGC-BIN attack the model more consistently confuses the test predictions for these two classes.
B.8.5 EXTENDED META ATTACK
In Table 6 we evaluate the extended variant of our meta attack. Overall, we can conclude that this variant weaker compared to the other meta variants (and our surrogate attacks) while still outperforming some of the baselines. In any case, we include these results for completeness.
B.8.6 ATTACKING WITHOUT ACCESS GROUND-TRUTH TEST LABELS
In our main paper, we described a second threat model, where the ground truth labels are only available for training nodes and only the predictions available for test nodes (no ground-truth labels). We evaluate our strongest attacks SGC-BIN and META-BII in this setting and plot the results on Fig. We observe that the performance of our attacks in this setting close the worst-case setting where the attacker knows the test ground-truth labels. Especially for SGC-BIN there is almost no difference between using the ground-truth labels vs. the predictions. Additionally, our attacks that use predictions also outperform the baselines that use ground-truth labels.
500
423
200
350
104
Figure 7: Confusion matrices for test set for GCN model poisoned with the LFK (left) and SGC-
BIN (right) attacks using 15% poisoning budget on the Cora-ML. dataset.
19

---

Published as a conference paper at ICLR 2024
MG
LP
LFK
SGC-BIN
META-BIN
Y True
Y Pred
Cora-MI.
Citeseer
Puhmed
A Test Accuracy
0.4
0.3
0.2
0.1
0.0
5
10
15
20
25
30
5
10
15
20
25
30
5
10
15
20
25
30
Poison Percentage
Poison Percentage
Poison Percentage
Figure 8: Evaluating our attacks under the two different threat models given access to: ground-truth test labels vs. only predictions. Our attacks outperform the baselines even without access to ground-truti test labels.
B.9 DATASET STATISTICS
In Table 7
we tabulate dataset statistics. We additionally include the train/val/test split statistics for the default and the proposed CV setting. Note that in the CV setting, the test accuracy is measured all the remaining unlabeled nodes, and the train and val set have the same size.
Table 7: Dataset statistics.
Dataset
Nodes
Features
Classes
Prain//al/Test Split
Default
CV
Cora-ML
2810
2879
140/500/1000
440/14002530
Citeseer
2110
3703
6
120/500/1000
120/ 20/1//0//00
Pubmed
19717
500
60/500/1000
60/60/1 19597
CoraFull 18800
500
70
000001400/16000
OGBN-ArXiv 169343
128
40
90941/29799/48603
90941/29799448603
B.10 TRAINING WITH CLEAN VALIDATION-SET
As mentioned in the $ assuming access to clean validation dataset is not realistic scenario, particularly in the graph domain where we are often interested sparsely labeled scenarios where both the training and validation sets small and typically of the same size. Consequently, the defender can always exploit the limited clean validation set to train the model and thwart the attacker's 's efforts. To illustrate this further, demonstrate that the defender train the model using the clean validation data while maintaining performance.
In this experiment, assume access to small validation with just 20 labels per class the standard choice. This constitutes roughly 5% of Cora-ML, 6% of Citeseer, and 0.3% of Pubmed datasets. We train GCN model for 200 epochs using this validation and discard the potentially poisoned training set. We perform this experiment across 10 different splits, (Table 8 illlutrrates the results, demonstrating that all poisonini attacks can be effectively neutralized.
B.11 How LABEL POISONING INFLUENCES GRAPH HOMOPHILY
While it is fact that label poisoning attacks can disrupt the smoothness of labels in graph, these attacks do not provide the defender with the ability to detect the specific poisoned labels. The defender presented with graph that may contain tainted training labels and starts with no knowledge of the graph's 's homophily rate before the poisoning occurred. Moreover, real-world graphs exhibit varying levels of homophily, with examples such OGBN-ArXiv having 63% homophily rate, and Pubmed
20

---

Published as a conference paper at ICLR 2024
RND-BIN
- LP
NTK-BIN
Ours
DEG-BIN
LFK
META-BIN
Heuristics
MG
SGC-BIN
Baselines
CoraML
Citeseer
Pubmed
A Test Accuracy
0.4
0.3
GCN
0.2
0.1
0.0
A Test Accuracy
0.4
0.3
0.2
GAT
0.1
0.0
A Test Accuracy
0.4
0.3
APPNP
0.2
0.1
0.0
A Test Accuracy
0.4
0.3
CPGCN
0.2
0.1
0.0
A Test Accuracy
0.4
0.3
RTGNN
0.2
0.1
0.0
5
10
15
20
25
30
5
10
15
20
25
30
10
15
20
25
30
Poison Percentage
Poison Percentage
Poison Percentage
Figure 9: Our strongest attacks significantly outperform the baselines across various models and datasets.
21

---

Published as a conference paper at ICLR 2024
Table 8: Test accuracy on large clean validation training set.
Dataset
Test Accuracy (%)
Cora-ML
85.30=0.95
Citeseer
75.62
Pubmed
82.40=1.000
boasting approximately 80%. However, even the defender knows about the graph's homophily, we demonstrate that label poisoning does not significantly change the graph's h'ss homophily. [able and Table 10jlluuttrtee how the global and local homophily rates change only minimally for different poison budgets when using the SGC-BINattack:
Table 9: Edge (global) homophily ratio.
Dataset
0
5
10
15
20
30
Cora-ML
0.82
0.80
0.79
0.79
0.78
0.77
Citeseer
0.80
0.78
0.77
0.76
0.75
0.74
Pubmed
0.84
0.84
0.84
0.84
0.84
0.83
Table 10: Node (local) homophily ratio.
Dataset
10
15
20
30
Cora-ML 0.82
0.83
0.83
0.82
0.81
0.80
Citeseer
0.80
0.80
0.79
0.78
0.77
0.76
Pubmed
0.84
0.86
0.86
0.86
0.86
0.86
B.12 ATTACK PERFORMANCE UNDER THE DEFAULT (FLAWED) SETTING
We also evaluate our proposed attack under the default and flawed evaluation setting to demonstrate that attacks outperform the baselines by even wider margin. The reason for advocating the new evaluation protocol to simulate the attack/defense scenario more realistically, not because favors attacks. Table shows the results for the Cora-MI. dataset, clearly demonstrating attack's superior performance over baseline attacks.
1. ATTACKS UNDER PARTIAL INFORMATION SCENARIO
We further conduct experiments involving partial information to evaluate our poisoning attack. In this context, we exclusively utilized node features and excluded the graph structure for the attacker. The attacks were executed on a graph generated from the k-nearest neighbors illustrates result. Our results reveal that our SGC-BIN KNN attack (with partial information, considering only node features) closely matches LFK's performance when it has access to complete graph information. Additionally, it outperforms LFK by approximately 2% on average under partial information. This highlights that our proposed attack surpasses the previous state-of-the-arr method, even scenarios with partial information.
the node, Table 12
B.14 TIMING ANALYSIS
We compute the average time taken in seconds (over 20 different runs) for single hyper-parameter configuration for our proposed evaluation setting and tabulate in Table 13 We can infer that tuning GNNs is relatively cheap.
22

---

Published as a conference paper at ICLR 2024
Table 11: Performance comparison of proposed attacks and basclines under default evaluation setting on the Cora-ML dataset.
Attack
5%
10%
20%
SGC-BIN
66.80
60.78 :2.03
53,88 3:7.2
49.12
META
61.80 13.37
59.48 11.96
58.27 1:205
50.30_13.08
LFK
66.43
67.33
58.9342.38
55.94:3.41
RND
80.03
4...9922.11
76.21 2:299
74. 74.1942.84
DEG
79.98
76.95
74.28
70.41
MG
78.71 12.54
72.08 15.25
63.7416.87
58.74.7.10
Table 12: SGC-BIN KNN and LFK KNN illustrate attacks with partial information using K-nearest neighbors (K=20) for graph construction. Meanwhile, SGC-BIN, LFK, and LP demonstrate attack performance with full information (adjacency matrix and node features).
Cora-ML
5%
10 %
15%
20
30 %
SGC-BIN
76.57
69.50
59.81
55.55
47.47
LFK
76.38
73.98
67.50
63.49
52.80
LP
80.48
76.4040.58
68.83
63.0642.50
57.57 +0.62
SGC-BIN KNN
77.99+1.72
74.83+2.04
67.77 #2.10
63.17
50.43
LFK KNN
77.49 +2.25
75.56
69.47
65.54
53.93
B.15 LABEL FREQUENCY ANALYSIS
In Fig. 10 we plot the label frequency ratio for the benchmark datasets. We can observe that the frequency distribution is skewed with one more popular classes, This reinforces our earlier point that eaualleue splits do not capture the underlying distribution of labels.
0.25
0.20
0.20
0.15
0.15
0.10
0.10
0.07
0.06
Figure 10: Label frequency ratio for benchmark datasets.
B.16 EVALUATION AGAINST CERTIFIED DEFENSE MODEL
Label poisoning be considered as extreme version of feature poisoning. To explore this implication, we evaluate our strongest attack SGC-BIN and the strongest baseline attack LFK on AB- LATIONGCN, of the recently certified defense mechanisms against feature perturbations. We tabulate our results in Table 14, We can infer that our proposed attack can inflict heavy damage on the model's performance.
23

---

Published as a conference paper at ICLR 2024
Table 13: Timing analysis.
Dataset
K-80 GPU
A100 GPU
Cora-ML
16.3s
10.2s
Citeseer
18.9s
11.8s
Pubmed
36.4s
12.5s
Table 14: Efficacy of SGC-BIN BIN vs. LFK attacks on AblationGCN, certified defense against feature perturbations.
0%
5%
10%
15%
20%
30%
Cora-ML
SGC-BIN
79.17
71.80+1.65
66.3441.70
59.77+1.25
54.57+1.25
46.60
LFK
79.17
71.63
68.32
63.1711.73
58.93
50.81 2.16
Citeseer
SGC-BIN
68.25
62.90
56.4443.22
49.6442.05
44.76.2.32
36.39 1.63
LFK
68.25
63.1042.06
59.6442.02
53.10
50.86
40.42_2.68
PubMed
SGC-BIN
78.07+1.17 78.07+1117
67. 67.02+1.81
61.38
56.40
53.73
47.77
LFK
67.36+1.43
61.80+4.73
57.07
55.87+2.74
50.35
B.17 17 ABLATION STUDY ON PITFALLS
In this section, expand upon the experiments conducted in the main paper by including additional
datasets and models. The majority our observations in Fig. 11 Fig. 12 Fig. 13] align with the findings reported in the main paper. Specifically, for the Citeseer and Pubmed datasets, we notice that, in certain budget scenarios, our proposed CV splits appear to be advantageous to the attacker when compared to the default configuration for the LFK attack.
Fig. 14 Fig. 15
B.18 CONNECTIONS BETWEEN PITFALLS AND ATTACKS
Our main goal is to establish principled evaluation protocol to ensure that research on label poisoning (for ourselves and others) is on a solid ground. We see two equally important parts to this goal:
Evaluation setup that simulates the full potential of defender as realistically possible.
Simple yet effective baseline attacks to
reference point for the future.
These two parts are addressed by the (remedies of the) pitfalls and the attacks. On one hand, you can definitely see them two disjoint contributions. On the other hand, having fair evaluation in mind, implicitly guided our design of the attacks. For example, pitfalls P3 and P6 can be seen as form of overfitting to the splits and default h-params respectively. Therefore, when selecting h-params attacks (e.g. the value of for LSA attacks and the learning rate for meta attacks) choose h h-params that minimize the test accuracy on average across splits, preventing overfitting to a single split. Moreover, to remedy P6 poison V, which implicitly impacts the bi-level optimization. Moreover, while fixing the identified pitfalls leads to a fairer evaluation it also decreases the effectiveness of previous attacks. This provided additional motivation to introduce the new baseline attacks. Under the previous evaluation setting, we observe that META attacks significantly outperform other attacks (see 33 B.12). However, in the new fairer setting, META attacks don't generalize effectively as linear attacks. This highlights the need for a careful evaluation.
24

---

Published as a conference paper at ICLR 2024
(a) GCN- CI
(b) GAT Cora-MI.
(c) MCLN--C
Cage
(d) GCN- CiteSeer
(e) GAT- CiteSeer
(f) APPNP- CiteSeer
(g) GCN Pubmed
(h) GAT Pubmed
ii) APPNP- Pubmed
Figure 11: Analyzing the effect of each evaluation setting on the performance of the LFKattack across three models and three datasets.
25

---

Published as a conference paper at ICLR 2024
Neceoge
Peroedage
(a) GCN Cora-MI.
(b) GAT Cora-MI.
(c) APPNP Cora-ML
.04
(d) GCN- CiteSeer
(e) GAT CiteSeer
(I) APPNP CiteSeer
(g) GCN Pubmed
(h) CAT Pubmed
(i) APPNP Pubmed
Figure 12: Effect of validation set size the performance of poisoning attacks across three models and three datasets.
26

---

Published as a conference paper at ICLR 2024
Naceogg
Peroedage
(a) GCN Cora-MI.
(b) GAT Cora-MI.
(c) APPNP Cora-ML
404
(d) GCN- CiteSeer
(e) GAT CiteSeer
(i) APPNP CiteSeer
(g) GCN Pubmed
(h) CAT Pubmed
(i) APPNP Pubmed
Figure 13: Effect of data split the performance of poisoning attacks across three models and three datasets.
27

---

Published as a conference paper at ICLR 2024
Niceoge
Phroedage
(a) GCN Cora-MI.
(b) GAT Cora-MI.
(c) APPNP -C
.04
20.
(d) GCN- CiteSeer
(e) GAT CiteSeer
(i) APPNP CiteSeer
(g) GCN Pubmed
(h) CAT Pubmed
ii) APPNP Pubmed
Figure 14: Analyzing the effect of proper hyper-parameters tuning on the performance of poisoning attacks across three models and three datasets.
28

---

Published as a conference paper at ICLR 2024
Neceoge
Peroedage
(a) GCN Cora-MI.
(b) GAT Cora-MI.
(c) APPNP -C
.04
20.
(d) GCN- CiteSeer
(e) GAT CiteSeer
(i) APPNP CiteSeer
(g) GCN Pubmed
(h) CAT Pubmed
ii) APPNP Pubmed
Figure 15: Analyzing the effect of proper cross-validation the evaluated performance of poisoning attacks across three models and three datasets.
29


Reviews:
[{"review_id": "zbA5jhTKaR", "reviewer": "Reviewer_JRv5", "summary": "The paper focus on adversarial attacks in the context of graph learning algorithms. In particular it considers label poisoning (a specific case of data poisoning) for GNN algorithms. This work highlights the vulnerability of models to these attacks and the methodological problems of previous studies in evaluating this vulnerability. It also presents new attacks and provides some new insights on adversarial attacks “overfitting”.", "questions": "* In Eq. (1) could we replace the argmax on L by an argmax on another metric (error rate) without loss of generality ? What would be the impact of having a more general formulation here ? (aka adversary trying to maximize error rate and not necessarily maximize loss ; would it change the design typically of the Meta attack ?)\n* As mentioned above, paragraph 3 do not adress the defense-awareness pitfall ; would it be feasible to have a Figure like Fig 2 that takes this pitfall into account ? (if you have the experiments ready)\n* I would suggest to add a number (P1, ..., P6) to refer to each of the pitfalls, which would make the paper easier to read (+ it would also improve the readability of some figures)\n* You are introducing two new attacks. Did you leverage some insights coming from the 6 pitfalls to define these attacks ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper is well written and well structured\n* Pushing for higher standards in adversarial attacks is important for the research community\n* The discussion on binary attacks overfitting is interesting (and would worth being investigated more)", "weaknesses": "* t is not super clear if the newly proposed approach are using insights coming from the different pitfalls. Especially the HP tuning one.\n* Paragraph 3 mentions the pitfalls of undefended models but defers it to paragraph  ; as a result we cannot get a complete picture of the impact on the performance (and we expect this pitfall to have a large impact as well)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0UWasmY45q", "reviewer": "Reviewer_82Ci", "summary": "The paper first analyze the exiting problems in the current evaluation on the label-poisoning attack in the graph data. Through the analysis, the paper finds that the current evaluation has validation/test data unbalanced problem and is only tested in a single hyperparameter setting. The evaluation also keeps the labels in the validation/test data is clean. Then the paper proposes a new attack that formalize the label poisoning attack problem into a mixed-integer linear program. The paper also proposes to try  an orthogonal approach where it directly optimize the poisoned label through gradient descent and use the gumbel-softmax loss to enforce the discrete property. Extensive experiments have been conducted to verify the effectiveness of the proposed method.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and not hard to follow.\n2. The analysis of current problem in the evaluation does help the future study in the label poisoning community.", "weaknesses": "1. The paper is not well-organized. The analysis on current evaluation doesn't help to understand why the new method is proposed. The paper does want to include a lot of discussion on different parts of the label-poisoning attack. However, I find they are not well-connected and I fail to find a coherent logic flow in the paper.\n2. Since I am not from this community, the proposed method seems a very natural formulation to conduct the label flip idea. Therefore, I am not sure whether the paper has enough novelty. Also, the formulation is also heavily based on the previous study and the proposed method is like a multi-label extension to me.\n3. Some pitfalls proposed are weird to me. I am not sure why the split between training, validation and test should be equal. As a semi-supervised learning task, it is usually to let them differ in my opinion and I am also not sure why the validation set should be poisoned as well since the validation set should be used to select model and do cross-validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eEJtm5krKn", "reviewer": "Reviewer_FFMY", "summary": "This paper investigates label poisoning attacks against graph neural networks (GNNs). The paper first argues that major flaws exist in the evaluation of existing attacks against GNNs that needs to be resolved. These issues, such as the distribution of training/validation nodes and hyper-parameter selection, are related to faithfully considering the capabilities of defenders against such label poisoning attacks. The paper provides a critical evaluation of these pitfalls and demonstrate that they can have a significant effect on the performance of existing attacks. In the second part of the paper, two novel label poisoning attacks are introduced. The first one, called linear surrogate attack, uses a linear model as a surrogate for the models that one aims to attack. Then, a novel mixed-integer linear program is proposed to find the optimal solution for this attack. The second attack, dubbed meta attack, is motivated through the use of meta-learning for solving the bi-level optimization problem used for generating the label poisoning attack. Finally, the paper investigates the reasons behind superior performance of label poisoning attacks that only consider two classes to perform their flipping. Empirical and theoretical results for all the contributions are provided. Interestingly, the proposed linear surrogate attacks outperform all existing label poisoning attack baselines on both vanilla and defended GNNs.", "questions": "Besides the above-mentioned questions, here are some additional questions/suggestions:\n\n- Could you please explain how the final poisoned label is computed via $\\hat{\\boldsymbol{Y}}\\_{l} = \\mathrm{diag}(\\boldsymbol{b}) \\odot \\boldsymbol{H} + \\mathrm{diag}(\\mathbf{1}\\_{L} - \\boldsymbol{b}) \\odot \\boldsymbol{Y}\\_{l}$?\n\n- Using larger legends and axis labels for the plots is highly encouraged.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- This paper pins down vital cracks in evaluation of label poisoning attacks and show that they can play a crucial role on the model performance. The authors present these pitfalls and argue around the unrealistic nature of each one. These arguments are supported by extensive experimental results, validating the authors' claims.\n\n- The presented linear surrogate and meta attacks are novel and effective. The paper presents these two new methods and introduces new theory to support such attacks. Experimental results also demonstrate that these two attacks can outperform state-of-the-art baselines by a large margin.\n\n- The most important part of this submission, in my view, is its writing and presentation. Instead of presuming that the reader is familiar with this topic, the authors present their ideas in detail and explain the intuition behind each step, making it extremely easy for the reader to navigate through the paper. Given the abundance of contributions in the paper, it could have been easy to drown the reader with a flow of information, but the authors present all these ideas in a coherent manner, making the paper a pleasure to read.", "weaknesses": "- Perhaps the most problematic issue with the current submission for me is the lack of direct relationship between the proposed methods and the discussions of the first half of the paper. It would have been nicer if the authors could make the connection of these two parts more clear. In other words, was the design of the proposed attacks in any form motivated by the flaws in evaluating label poisoning attacks in GNNs, or these two parts of the paper shall be seen as two disjoint contributions?\n\n- Besides, providing some explanation/intuition about the first pitfall of baseline evaluation would be nice. At the moment, the paper just states that existing methods use considerably larger validation sets than training ones, but it doesn't go into the details of why this is a pitfall. Elaborating on the during the second paragraph of Section 3 is much appreciated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0pcN5XzYvx", "reviewer": "Reviewer_Cen8", "summary": "This paper evaluates the current state of research on label poisoning in Graph Neural Networks (GNNs). The authors point out that while noisy labels in machine learning have been extensively studied, the same cannot be said for graph-based data, especially in the context of adversarial label perturbations. The paper identifies evaluation pitfalls in existing literature, questioning the conclusions drawn about the robustness of GNNs against label poisoning. To address this, the authors delve into various attack strategies, explore the intricacies of loss functions, and aim to provide a more accurate understanding of GNN vulnerabilities.", "questions": "Refer to weakness part.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Formalisation: This paper provides a formalisation for the research questions.\n2. Focus on Nuances: A lot of part of this paper focuses on discriminating the nuances of existing methods, which contributes to building trustworthy GNNs from an accountability view. The authors don't just critique existing literature but also provide a summarisation of pitfalls in existing works.", "weaknesses": "1. Unconvincing arguments, presentation ambiguity and self-contradiction: (1) Lot of arguments in this paper are not convincing. For example, it says “The first pitfall arises since all previous attacks evaluate on data splits with validation set size much larger than that of the training set (e.g. 500 validation vs 140 train nodes on Cora-ML in the default setting).” Actually, this kind of data partitioning is practical in graph learning as model developers focus on training and validating datasets in the training phase. It is hard to say this is a pitfall. (2) A lot of the statements are ambiguous. For example, it says “We observe that fine-tuning with only 20 configurations can significantly deteriorate the attack performance, as evidenced by an increase in test accuracy.” The configurations are not explained clearly here. (3) Self-contradictive statement. In the beginning, it says that one drawback of related works is they focus on the binary task, however, they can be generalised to multiclass tasks, as shown in the evaluation part of this paper.\n2. Limited novelty. Although the research problem has been formulated, the proposed solutions have limited contribution. First, the method in section 4.1, only focuses on the liner GCN model, which ignores the non-linear property of most GNN models. The second method introduces a learning-based method to select nodes for flipping, however, the effectiveness will be limited by the expression ability of the surrogate model in the inner optimisation. Considering these limitations, existing methods can be adapted to the current setting, and unhighlighted research challenges in this paper, the novelty of the proposed methods is weak.\n3. Objective Presentations. Broad claims, especially critiques of an entire domain of literature, require comprehensive evidence and careful presentation to avoid potential overgeneralization. For example, the statement that the \"entire literature on label poisoning for GNNs is plagued by serious evaluation pitfalls\" is a strong assertion. From the segments I reviewed, there wasn't exhaustive and convincing evidence presented to substantiate such a broad critique. While the paper might delve deeper into this in sections I haven't extracted, from the available content, this claim appears to lack detailed supporting examples.\n\nA research paper's strength lies not just in its findings but also in the clarity and robustness of its evaluation methods. When critiquing other works for evaluation pitfalls, it becomes crucial for the paper to transparently outline its own methodology limitations. Considering these weaknesses in this paper, the authors are suggested to polish this paper carefully.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)