Rethinking Label Poisoning for GNNs: Pitfalls and Attacks

We thank the reviewer for their valuable feedback. We address the raised questions below.

W1-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.

Response W1-1. We strongly disagree with this comment. Unlike other domains (e.g. Computer Vision) in GNNs we are often interested in the sparsely labeled scenario where the number of labeled nodes is relatively small $\mathcal{V}_l \ll \mathcal{V}$. This is the standard in the literature.

We advocate using validation set that is at most as large as the train set. The pitfall of using large validation set has been extensively studied for semi-supervised learning. The highly influential paper from Oliver et al. (2018) [1] offers an extensive discussion on this pitfall for general semi-supervised learning (see their P.6). To briefly summarize their points, in real-world applications the larger validation set would instead be used as the train set. Another issue is that any objective (e.g. accuracy) used for hyperparameter tuning would be significantly noisier across runs when using a realistically small validation set which disproportionately affects method that are sensitive to h-params.

It would benefit the discussion if the reviewer can point us to other arguments that they find unconvincing.

[1] Realistic Evaluation of Deep Semi-Supervised Learning Algorithms. Oliver et al., NeurIPS 2018.

W1-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.

Response 1-2. In the introductory paragraph of our Appendix we provide comprehensive details on the hyper-parameter configurations we use during both attack (paragraph 2) and defense (paragraph 3) phases. We added a forward pointer for clarity in the updated version. Additionally, we share our code which does hyper-parameter tuning and provides additional implementation level details.

It would benefit the discussion, if the reviewer can point us to other statements that are ambiguous.

W1-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.

Response W1-3. We mentioned in our paper that the previous attacks were primarily introduced for binary classes. Then, for a fair comparison, we introduced the multi-class extension of these attacks. We therefore fail to see the contradiction that the reviewer is pointing out to.

W2. 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. ...

Response W2. We provide clarification on our proposed approaches. It is important to note that our simplest linear surrogate attacks, despite not retaining the non-linearity property, are very effective on other non-linear GNN models like GCN, RTGNN, GAT etc. This highlights the transferability of our attacks. In addition to this, we also introduce NTK attacks that take into account the non-linearity of GCNs. This is expected since linear GNNs perform competitively to non-linear GNN on several homophilous datasets [1, 2].

For the LSA family of attacks, we prove that the MILP can be efficiently solved (see Proposition 1 for a closed-form solution and Proposition 2 for the proof that the LP is integral). These results are novel and show that the globally optimal MILP solution can be efficiently computed. We also prove that random binary attacks are stronger than multi-class variants (Proposition 3).

The Meta attacks that we introduce do not use any surrogate models in the inner-optimization. Our adaptive meta attacks uses the exact same model and not a surrogate model in the inner optimization. For additional implementation-level insights, please refer to our code.

[1] Simplifying Graph Convolutional Networks. Wu et al., ICML 2019

[2] Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective. Wei et al., NeurIPS 2022

We thank the reviewer for their valuable feedback. We address the raised questions below.

W1. 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?

Response R1. Since a similar comment was brought up by multiple reviewers we address it in a joint meta response (see the top comment and the newly added section A.18).

W2. 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.

Response W2. We elaborated this point in the updated version. The highly influential paper from Oliver et al. (2018) [1] offers an extensive discussion on this pitfall for general semi-supervised learning (see their P.6). To briefly summarize their points, in real-world applications the larger validation set would instead be used as the train set. Another issue is that any objective (e.g. accuracy) used for hyperparameter tuning would be significantly noisier across runs when using a realistically small validation set which disproportionately affects method that are sensitive to h-params.

[1] Realistic Evaluation of Deep Semi-Supervised Learning Algorithms. Oliver et al., NeurIPS 2018.

Q1. Could you please explain how the final poisoned label is computed via...

Response. Instead of Hadamard product, we need a matrix product. Thank you for noticing this typo.

Correct version: $\widehat{\mathbf{Y}}_l = \mathrm{diag}(\mathbf{b}) \mathbf{H} + \mathrm{diag} (\mathbf{1}_L - \mathbf{b}) \mathbf{Y}_l$.

We also updated the paper to reflect this.

We thank the reviewer for their valuable feedback. We address the raised questions below.

W1. 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.

Response W1. Since a similar comment was brought up by multiple reviewers we address it in a joint meta response (see the top comment and the newly added section A.18).

W2. 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.

Response W2. You are correct our attacks are essentially a multi-label extension in terms of formulation. However, our novelty lies in the way we approach the optimization.

Optimal Linear Family of Attacks: In contrast to previous approaches that rely on a greedy solution for identifying poisoned labels, our solution is optimal. Specifically, for the LSA family of attacks, we demonstrate the efficiency of solving the Mixed-Integer Linear Program (MILP) with a closed-form solution (refer to Proposition 1) and prove the integrality of the Linear Program (LP) in Proposition 2. These findings are novel and highlight the computational efficiency of obtaining the globally optimal MILP solution.

Adaptive Meta attacks: At a high level, all meta attacks follow a similar routine -- unrolling the inner level optimization for K steps for each outer loop iteration. While various meta gradient-based attacks exist, what distinguishes them is the nuanced setup of the poisoning process. To the best of our knowledge, our work is the first to introduce a family of meta-attacks for label poisoning for GNNs. Our formulation utilizes soft-top-k followed by k-subset-selection along with the proposed Gumbel-softmax loss.

Furthermore, we prove that random binary attacks surpass their multi-class counterparts (Proposition 3). Additionally, we introduce Neural Tangent Kernel (NTK) attacks.

W3-1. 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…

Response W3. Only the training and validation sets are equal and the remaining nodes correspond to the test set. We advocate using validation set that is at most as large as the train set. The pitfall of using large validation set has been extensively studied for semi-supervised learning. The highly influential paper from Oliver et al. (2018) [1] offers an extensive discussion on this pitfall for general semi-supervised learning (see their P.6). Briefly, one of their critical points is that in real-world applications the larger validation set would instead be used as the train set.

[1] Realistic Evaluation of Deep Semi-Supervised Learning Algorithms. Oliver et al., NeurIPS 2018.

W3-2. "… 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."

Response W3-2. The basis for poisoning attacks is that we do now know which labels are potentially poisoned. If the defender does have access to a small, clean-label validation set, they could simply ignore the training set and train for a fixed number of epochs on this secure clean validation set. This would render all label-poisoning attacks completely ineffective. We demonstrate this with the experiment in section A.10 in the appendix.

This is more acute for sparsely-labeled node classification. Unlike other domains (e.g. computer vision) in GNNs we are often interested in the sparsely labeled scenario where the number of labeled nodes is relatively small $\mathcal{V}_l \ll \mathcal{V}$. This is the standard in the literature. Some methods, use all labels for training, while others split $\mathcal{V}_l$ into train/val sets and use the latter for early stopping/fine-tuning. Our attacks remain agnostic to this.

We thank the reviewer for their valuable feedback. We address the raised questions below.

W1. It is not super clear if the newly proposed approach are using insights coming from the different pitfalls. Especially the HP tuning one.

Q4. You are introducing two new attacks. Did you leverage some insights coming from the 6 pitfalls to define these attacks ?

Response W1/Q4. Since a similar comment was brought up by multiple reviewers we address it in a joint meta response (see the top comment and the newly added section A.18).

W2. 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)

Response W2. The third pitfall we've identified stems from the fact that prior studies evaluated their attacks on undefended models, such as vanilla GCN and GAT, without considering defense models like CPGCN and RTGNN designed to counter label poisoning attacks. In our evaluation, we include these defenses and additionally AblationGCN -- a certified defense against feature attacks which can be viewed as an extreme version of label poisoning attack (refer to Fig. 4).

Q1. 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 ?)

Response Q1. We appreciate your observation. As suggested, we acknowledge that the outer loss (L) is flexible and can be replaced with various metrics. For example, in Sec 4.2 we introduce an approximate differentiable variant of the 0-1 loss in our meta-attack which we term as the Gumbel-softmax loss. Ablative experiments in Section A.8.2 demonstrate the superior performance of the Gumbel-softmax loss compared to the cross-entropy loss.

Q2. As mentioned above, paragraph 3 do not address 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)

Response Q2. In the updated version of the paper we updated Fig. 2 where now the second subplot includes a defense (CPGCN) thus showing how the second pitfall can be addressed.

Q3. 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)

Response Q3. Thank you for the great suggestion. In the updated paper we marked each pitfall with P1 – P6 for clarity and also updated Fig. 2 using these identifiers.