Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the problem conducting untargeted poisoning attacks against graph neural networks by pertaining edges of the original graph. The authors identified the problem of attack loss design, which mostly uses the same loss function (i.e., negative cross entropy) for model training, and pointed out that, with the wrong loss function, attack budget is wasted on causing misclassification for nodes that are already misclassified. Then a debasing solution is proposed by multiplying the gradients with their confidence scores and the obtained simple attack strategy outperforms the existing baselines significantly. 
strengths_and_weaknesses: I like the idea of the paper as it challenges some of the common beliefs in the attack design against graph neural networks, which is novel and signficant. The presentation of the paper is also very clear and easy to follow. Overall, the strength of the paper significantly outweighs the weakness. However, I have the following concerns:
1) the work by Ma et al., [9] (reference in the paper) and one missing work linked below [1] might deserve more discussion, as they are more related to the key problem identified in the paper: the downside of choosing a wrong type of attack loss.
[1] Ma et al., "Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem", WSDM 2022.  
2) the identified problem and fixable solution given in the paper is only demonstrated for the case of cross-entropy loss, and so the conclusion is not very generic.


questions: I do not list this as a question that will change my decision, but I am curious to know, if there are any other ways (e.g., designing new attack loss) to perform the edge perturbation instead of renormalizing the gradient.
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: - The authors tackle the problem of the attack objective (the form of cross-entropy function) in the untargeted attacks on node-level classification models. 
- They show that nodes with low confidence significantly affect the gradient.
- To alleviate this problem of inefficient attack budgets, they propose a novel attack objective whose corresponding gradient is not affected by the confidence of nodes. 
- They conduct experiments on gray-box poisoning attack and shows that the proposed attack method GraD (based on the proposed gradient-debias attack objective) can significantly improve the attack performance.
strengths_and_weaknesses: # Strengths
- The authors states an interesting problem in the cross-entropy based attack objective. (Figure 1 was very helpful to understand the concept!)
- The authors explain the proposed problem using a simple mathematics. Also, they mathematically explain their proposed attack objective can solve the problem.
- They conduct fair comparison on various datasets and achieve the state-of-the-art attack performance.

# Weaknesses
- The usage of the method seems limited to gray-box / white-box attack on GCN-based node classification models. 
- Ablation studies seem insufficient.
questions: - I hope that the explanation of the purpose of the poisoning attack is simply added to the introduction or related works.
- Why are there no line numbers in your submission?
- I want to know more scenarios to apply GraD other than gray-box / white-box attack on GCN-based node classification models if exist. 
- If I understood correctly, we can apply GraD to white-box attack too. Can you show some white-box attack results of GraD and white-box baseline methods? 
- One can replace the attack objective of GraD to the original negative cross-entropy loss and compare it with GraD as an ablation study. Is there already a baseline corresponding to it in the table 1, 2? If not, I want to see this result.

POST REBUTTAL COMMENTS: The authors answer the questions. My concerns have been addressed. They can apply their method also in the white-box attack setting. They add broader impacts and fix some minor issues in the paper. I adjust my score from 6 to 7.
limitations: This paper handle the adversarial attack which can be used by malicious adversaries. That said, I wish that the authors include ethics or broader-impact statement in the paper or appendix.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the graph modification attack in a untargeted poisoning setting by editing the edges, and reveals that using the negative cross entropy as the attack loss will cause unreasonable budget allocation issue. Thus, the paper proposes a new attack objective by plugging the confidence to reduce the influence of the negative cross entropy. The authors conduct some experiments to validate their findings.
strengths_and_weaknesses: *Originality & Significance*: Studies around graph adversarial attack and defense are of great importance to the community. However, given the limited scope of the focus in this paper, the significance might be weakened. See the Questions below for more details.

*Quality*: The authors conduct certain theoretical and empirical analysis to validate their claims. However, the experiments might not be sufficient to fully support the effectiveness of the proposed method. See the Questions below for more details.

*Clarity*: The paper is well-organized yet not easy to follow. There are too many undefined mathematical symbols and typos.

questions: Starting from an interesting observation of the budget allocation in the untargeted poisoning graph modification attack, the authors reveal that using negative cross entropy loss can affect the gradients signals passed to the adversary hence the adversary keeps allocating budgets to attack the low confidence nodes. However, there are several concerns raised when I read the paper.

1. The scope of the studied attack might be too limited. In fact, graph adversarial attacks can have both poisoning and evasion, targeted and untargeted, modification and injection attacks [1,2,3]. Especially, [3,4] point out that the poisoning attack can have severe issues due to the ill-defined imperceptibility. More justification and discussions are required for the reasons about why adopting the setting in the paper. Otherwise, the limited setting used and discussed in this paper weakens the significance and novelty of the paper, given that the main contribution of this work is to propose a new adversarial objective for graph adversarial attacks. 

2. Important experiments seem to be missed in the paper. Since the proposed objective can improve the budget allocation of the graph adversarial attack, the authors only conduct two experiments with 2 specific allowed budgets, which is significantly less than existing literatures [1,2,3,4,5,6,7], providing weak support to the effectiveness of the proposed objective.

3. It would be more interesting if the authors could discuss and evaluate the budget allocation during the targeted attack to the large scale graphs [8,9] which tends to be appealing in practice, as we often do not have sufficient budgets to attack all of the test nodes in a large scale graph while many of node classification applications focus on the large scale graphs. In the literature, the graph injection attack can serve a good proxy [4].

4. The scope of the experiments is also limited. The authors only test with GCN, GAT, GraphSage, while neglecting many defense methods [6,7], as well as methods such as Nettack that can also be leveraged to attack and see the survey [1,2,3] for more details. Some representative datasets such as Pubmed are missed.

5. In experimental setup, ``Each experiment is repeated ten times with a fixed random seed’’, what is the point to fixing the random seeds and repeat the experiments? How do they produce different results if the random seeds are fixed?

6. The writing is hard to follow. There are too many undefined mathematical symbols and typos. Here are some of them (not sure why authors cancel the line numbers, making the reviewers hard to point out the specific locations of their concerns):
    - In 3.1, ``while the prediction of f θ is denoted by the probability distribution P_vi’’
    - In Eq. 4, what is z_i?
    - After Eq. 4, `` where V ∗ is a subnet of nodes’’
    - In Sec. 4, is it the linearized GNN, SGC or GCN?
    - In Sec. 4, y_i is undefined.
    - In Eq. 6, what is A^grad? What is A^grad with subscript v_i? Does it mean taking some entry in A^grad?
    - After Fig. 4, ``We consider this to be since the node deviates from the centroid of any class.’’




References:

[1] Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, Jiliang Tang. Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies. SIGKDD Explorations 2020.

[2] Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S. Yu. Adversarial Attack and Defense on Graph Data: A Survey. arXiv 2020.

[3] Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, Jie Tang. Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning. NeurIPS 2021 Datasets and Benchmark Track.

[4] Yongqiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, James Cheng. Understanding and Improving Graph Injection Attack by Promoting Unnoticeability. ICLR 2022.

[5] Shuchang Tao, Qi Cao, Huawei Shen, Junjie Huang, Yunfan Wu, Xueqi Cheng. Single Node Injection Attack against Graph Neural Networks. CIKM 2021.

[6] Xiang Zhang, Marinka Zitnik. GNNGuard: Defending Graph Neural Networks against Adversarial Attacks. NeurIPS 2020.

[7] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, Jiliang Tang. Graph Structure Learning for Robust Graph Neural Networks. KDD 2020.

[8] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, Stephan Günnemann. Robustness of Graph Neural Networks at Scale. NeurIPS 2021.

[9] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, Suhang Wang. A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability. arXiv 2022.

limitations: The authors did not provide such a discussion.
review_title: null

Meta-review: metareview: The authors study graph modification attack (through editing the edges) in the setting of untargeted poisoning and show that negative cross entropy is not a good candidate for the attack loss. Instead they propose a novel attack objective to study the problem. 

The reviewers found the topic timely and of interest to the community. They felt that the theoretical and empirical analysis could be improved to validate their claims, but overall the positives seemed to outweigh the negative perceived by the reviewers. 
confidence: Less certain
Decision: Accept