Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The contributions of the paper: 

1) study the drawbacks of cross-entropy loss in the global attack of GNNs and propose alternative losses;

2) propose a scalable attacking algorithm based on the randomized block gradient descent algorithm. It also introduces a heuristic to enforce sparse adjacent matrix and avoid the computation on dense matrix;

3) propose a more efficient defense method based on an existing method, Soft Medoid.


main_review: Strength:
1. The major focus of this paper is to study the adversarial robustness of GNNs on a larger scale. This is important since most of the existing attack and defense methods for GNNs are limited to very small data. 

2. The instigation and discussion on the ineffective of CE loss in the global attack of GNNs are interesting. It points out that attacking methods based on CE loss might waste attacking budgets, which provides useful insight for the development of stronger attacking methods. 

3. The proposed scalable attacking method seems quite efficient and experiments support its effective and efficiency.

Weakness:

1. The author doesn't provide a sufficient explanation for the proposed tanh Margin loss so that this loss design is unclear. Moreover, it is unclear why PGD algorithm doesn't improve over CE. The explanation due to the learning dynamics of PGD and independence assumption  (line 129-133) are confusing and vague. It is better to make it more precise and clear.

2. The proposed attacking algorithm is a bit heuristic and doesn't provide any theoretical justification.

3. It is hard to understand the scalable defense in Section 4. The proposed Soft Median method is based on Soft Medoid but the paper doesn't provide sufficient detail to demonstrate the idea. Therefore, it is unclear how the proposed method improves the efficiency of Soft Medoid. In particular, note that the dimension-wise median has been explored and showed to be worse than Soft Medoid in Soft Medoid paper, which should be discussed. The idea of the differentiable relaxation of the median is unclear.

4. Some important related works are missing. For example, it is stated that the authors are not aware of any defense that scales to graphs significantly larger than PubMed. However, the defense on datasets such as obgn-arxiv and DP has been explored in the paper "GNNGUARD: Defending Graph Neural Networks against Adversarial Attacks", which needs to be discussed and even compared.

Overall, the paper provides insightful investigations on the attacking and defense of GNNs. The proposed methods push the research in this area to a much larger scale, which is a very important direction. However, the writing can be significantly improved to make every part more precise and clear.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies adversarial attack and defense of GNNs at scale. The authors investigate the relationship between surrogate losses and accuracy, and scalable attack and defense algorithms. Some theoretical intuitions and extensive empirical evaluation are provided to support the claims.
main_review: Strength
- Overall, this paper is clearly-written. While this paper wraps a lot of content, the high-level overview in the Introduction makes it easier for the reader to parse the content.
- As far as I know, adversarial attack and defense for large-scale GNNs have not been well-explored and this is an interesting topic. 
- I find the analysis of the surrogate losses very interesting. The insight that the loss should guide the attack to focus on the correctly-classified boundary points could be helpful for the development of future attack methods.
- This paper has an extensive empirical evaluation.


Weakness
- The proposed attack is a white-box attack assuming almost everything (labels, gradients, etc) is available to the attacker. A white-box attack under the large-scale setup is rarely practical, which makes the proposed attack method less interesting.
- The assumption 2 is very unrealistic. The budget needed to flip the prediction of a node depends on the node features and its neighborhoods. Assumption 2 (and the proof of Proposition 1) assumes a uniform function g across all nodes. This is impossible, even approximately. With that said, while the significance of Proposition 1 is weakened due to the unrealistic assumption, the two properties defined in Definition 1 are still intuitively desirable.
- A table summarizing the theoretical computation complexity of the proposed methods and previous methods will be helpful.

Additional questions
- The study of surrogate losses does not seem to be relevant to the scale of GNNs. Is there anything that I missed?
- Could you elaborate on the reasons why MCE does not work well for PGD?
- Property (II) and property (B) essentially indicate a "diminishing-return" for the decrease of loss when the margin grows larger. This seems to align with the results in [22]. However, in A.2 the authors state that they mismatch. Could you elaborate more on the reasons? Also, the authors mention in A.2 that "our analysis suggests that the CW loss should be effective once the budget is large enough", but I did not find the relevant analysis. Could you point out where it is located?

Minor suggestions
- The naming of "budget-aware" loss in Definition 1 is a little bit confusing, since the definition itself does not involve the budget. Losses of this type favor correctly-classified boundary points, and has a diminishing slope when going further from the boundary. A more straightforward name such as "diminishing-slope" loss would be more informative. 
- A typo: line 124, the subscript n should be i.

limitations_and_societal_impact: This paper has a good discussion on limitations and societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses the problem of adversarial robustness for GNN regarding attack and defense on large graphs up to 100 million nodes. In terms of attack, they show that existing attack methods are weak for large graphs. To address this, they introduce the Masked Cross Entropy (MCE) which only considers correctly classified nodes on the attack. In addition, they also tackle the issue of handling large graphs which should be scaled with quadratic space complexity of adjacency matrix, and introduce the Projected Randomized Block Coordinate Descent (PR-BCD) based on Bernoulli sampling. In terms of defense, the authors propose the Soft median with differentiable relaxation of the Median. 
main_review: Originality
====
In this paper, the authors tackle the problem of GNN robustness in a large graph, which is important for GNN robustness but not addressed so far. This paper first points out the problem of existing attacks with their weakness in a large graph and suggests a theoretically guaranteed method with improved surrogate loss and scalable optimization method. This paper also provides the cue of scalable defense for a large graph.

Quality
====
The method sound convincing and the theoretical foundation seems solid. There are diverse comprehensive analyses that are helpful to understand the claim of the paper. The experimental setup covers the diverse sizes of graphs ranging from 2.8k to 111M against various attack and defense methods. 

Significance
====
In experiments, they show that their attack and defenses are reasonably fast and require much less memory that can cover sufficiently large graphs like Papers 100M. In quantitative analysis, they show that the proposed attack significantly drops the performance against other margin losses in Figure 6 and Table 2 and the proposed Soft Median defense resists the attacks much better than the baselines.

Clarity
====
The problem and method are generally well-motivated and clear. However, the overall presentation is disappointing. 
- In methodology sections (Section 2,3,4), subsections are rarely used and most topics are divided by only paragraph and bold title. It makes the paper looks fuzzy. 
- There is no abstractive description of the overall methods. I suggest authors add the comprehensive figure to outline the entire method to help authors better understand the overall methods.
- The caption of Figure 7 is insufficient and Figure 7 is not referenced in the main paper.
I think most of the presentation issues are due to the page limit of the main paper. I hope it will be more clarified in revision.
 
limitations_and_societal_impact: The presentation quality can be improved in revision, as noted in the Clarity section of the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies adversarial attacks against graph neural networks as well as adversarial robustness at scale. 
The authors first propose two first-order optimization attacks, i.e., PR-BCD and GR-BCD. The authors then propose an empirical scalable defense based on soft median aggregation. Both attacks and defenses are evaluated on benchmark datasets and show their effectiveness. 

Strengths
+The studied problem is important
+Propose a novel attack loss function
+Evaluation is extensive

Weaknesses
-The paper studies white-box attacks
-Algorithm details are unclear
-The proposed defense is empirical
main_review: —-Threat model

The paper studies white-box attacks, which is not practical from my perspective. 

—Algorithm details

From Figure 2, both tanh margin and cross entropy spend a lot of budgets on misclassified nodes. What’s the takeaway of Figure 2? 

Is Assumption 1 satisfied when performing global attacks, as they aim to reduce the performance of all nodes and could largely perturb the graph (given enough budget) which involves a substantial number of nodes? 

What’s the key difference between the proposed PR-BCD attack in Algorithm 1 and the optimization-based attack in [36]? 

PR-BCD needs to sort the probability mass before removing entries with the lowest probability mass. Sorting a huge vector is time-consuming. How could this sorting be scalable to huge graphs?    

How is the PPR matrix calculated in huge graphs, as it needs to compute the inverse of a huge matrix? 
  
What’s $\pi(v)_u$ in Eqn (6)? 

My main concern is that the proposed soft median based defense is empirical and does not have theoretical guarantees. As the paper mainly focuses “robustness” of GNNs, I doubt that empirical defenses provide a false sense of robustness.



—Evaluation
 
The term “perturbed accuracy” makes me confused.  

No global attack results on Papers 100M. 


—Other comments: 

In conclusion,  … our novel Soft Median which is differentiable as well as provably robust. => This is inaccurate.  



limitations_and_societal_impact: The authors addressed the limitations of their work
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the robustness of graph neural networks on a massive scale compared to the existing robustness work that focuses on smaller graphs, in terms of three perspectives: surrogate loss, attack, and defense. 
- The firstly proposed surrogate loss can be used to enhance the strength of adversarial attacks.
- The authors propose the scalable attack method for large graphs, which is implemented with sparse operations for reducing space complexity by considering a subset of entire adjacency elements when optimizing networks.
- Lastly, the authors propose the scalable yet robust function for aggregating neighboring information on graph neural networks, which is adopted from the previous Soft Medoid method for the scalable purpose.
main_review: ### Strengths
- Compared to existing robustness studies that mostly deal with smaller graphs, this paper provides valuable insights on robustness of large-scale graphs. Interestingly, the proposed attack methods can attack entire 2 million nodes at once. Also, the defense method can reduce the strength of attacks on large and even small graphs, while requiring minimal complexities. I believe this large-scale robustness framework is a good contribution to the graph neural network community, and can bring interesting follow-up work on a real-world scale.
- This paper is well written and well polished, and especially most of the claims are supported with empirical results. Also, a theoretical definition of the global optimum of surrogate loss, and the proposed loss function under this theoretical ground are technically strong.
- While this paper focuses on large-scale graphs, the proposed surrogate loss can be further used for general purposes, since it shows good performances on even small graphs.
- The authors provide a well-structured source code.

### Weaknesses
- While the authors claim that the proposed Masked Cross Entropy and tanh Margin losses improve the strength of attacks more on larger graph cases, the empirical results do not support this. First of all, the results of surrogate loss in Figure 6 are obtained by the smallest graph in the paper. Also, additional experiments in the supplementary file (Figure 15) show that existing losses, such as NC and elu Margin, are more effective compared to the proposed losses on some datasets (CoraML and Citeseer with FGSM and arXiv ML with PR-GCN).
- Regarding defense, while the proposed Soft Median coupled with PPRGo clearly shows good robustness performances, the Soft Median coupled with GDC is generally weak compared to the baseline, Soft Medoid coupled with GDC. I agree with effective scalability of the authors' method, but it would be better to clearly discuss the result and reason of degenerating performances of authors' one.

### Related work
- I am curious about why the authors do not experimentally compare their method against the existing large-scale adversarial attack method [1]. While Li et al. [1] only consider local attacks, it could be directly compared with the authors' local adversarial attack method in the Robustness w.r.t. local attacks paragraph of Section 5.

### Clarity
- I am confused about the relationship between density, perturbation, and margin in section 2 associated with figure 2. It would be better to have few explicit sentences for explaining the intrinsic meaning of the figure.
- In figure 3 (b), the block size is most small for 1.0E+07. Is it correct?
- It is hard to understand equation 6. There are no details on $\pi$ function, encoder, and combination of PPRGo. It would be better to more formally explain it in the supplementary file, if there is a space issue.

### Typo
- In figure 8, the caption indicates (d), (e), and (f), while the actual figure only includes two sub-figures: (a) and (b).

[1] Li et al. Adversarial attack on large scale graph, arXiv 2020.

limitations_and_societal_impact: The authors clearly outline the limitations and potential societal impact of their work, and I am completely satisfied with them.
review_title: null

Meta-review: This paper tackles the adversarial robustness of large-scale GNNs, which is practically important but has been overlooked. The authors provide a novel observation that the conventional cross-entropy (and Carlini-Wagner) loss guides the attacker to attack nodes that are already misclassified when attacking large GNNs, which results in the waste of the computing budget. Then, the authors show that under certain assumptions, a budget-aware loss can achieve the optimal solution, and propose a realization of such surrogate loss, Masked Cross Entropy (MCE), which only considers correctly classified samples, and thus is more efficient. The authors further propose scalable attacks and a scalable defense mechanism which modifies the aggregation function in the message passing framework. The experimental validation of the proposed attacks and the defenses show that they are indeed effective, and efficient in terms of computation and memory cost. 

The following are the pros and cons of the paper mentioned in the initial reviews.

Pros
- The tackled problem of ensuring robustness of a large-scale GNNs against adversarial attacks, is an important yet unexplored problem. 
- The study of the drawbacks of the cross-entropy loss when attacking GNNs is both novel and interesting.
- The proposed surrogate loss, Masked Cross Entropy, is both novel and effective for attacking large-scale GNNs, and has a potential to be further explored for other adversarial defense problems. 
- The proposed attack and the defense methods are efficient and scalable, which makes the model practical.
- The paper is well-written and is accompanied with well-structured source code. 

Cons

- The proposed attack and the defense methods are heuristic and lack theoretical justification. 
- The assumption of white-box attack for large-scale GNNs is impractical.
- The assumption on the expected budget required to ensure the optimality of the solution with the budget-aware loss is unrealistic.
- The effectiveness of the proposed attacks are shown on a small-scale graph.
- Lack of discussion and experimental comparison against relevant baselines, such as Li et al. 20, which also considers defense against adversarial attacks on large graphs.  
- Missing memory and time complexities of the different types of attacks. 

While the initial reviews were a bit split, during the discussion period, the reviewers and the authors actively engaged in very thorough, constructive discussions. This cleared away many of the concerns from the reviewers, and the reviewers unanimously agreed to accept the paper at the end. The authors convinced the reviewers that the assumption of white-box attack is reasonable in the defender’s point of view, and acknowledged the reviewers’ arguments that the black-box attack could be more practical when considering the tradeoff between clean and robust accuracy. The authors provided a more detailed explanation of the assumption, asymptotic time and memory complexities, and detailed discussion and experimental comparison against Li et al. 20. The lack of strict theoretical guarantees for the proposed attacks and the defenses are not critical, as their effectiveness have been verified with extensive empirical analysis.

In sum, this is a strong paper that tackles a novel and practical problem, analyzes the problem with an existing approach, and proposes an effective solution backed up with both theoretical and empirical analysis, which makes it a clear accept. I praise the authors and the reviewers for their constructive and active discussions, and advise the authors to incorporate them into the revision, as well as the new results they provided in the responses. 
Decision: Accept (Poster)