Venue: NeurIPS 2022 Conference

Reviews:

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: This paper proposes a novel method based on randomized smoothing to achieve robustness for graph neural networks. The task here is to certify the classification accuracy of GCN under any possible attacker who can perturb a bounded number of node features. Compared to the existing method, the proposed one considers random edge ablation and random node-level ablation. As a result, the approach achieves higher certified accuracy than existing baselines by a large margin.
strengths_and_weaknesses: Strengths:
- Solid technical contributions: To the best of my knowledge, this is the first paper that applies random **edge** ablation. Existing approaches for certifying the smoothed GCNs only consider random **node** ablation. When edge ablation comes into play, the certification can take the graph topology into consideration to achieve a better robustness certification. This paper studies this problem in depth, by providing an upper bound of $\Delta$ for certification and characterizing the computing methods for exact certification for general graphs or tree-structured graphs.

- Great writing quality: the paper is easy to follow with just few typos/ambiguities. Especially, the paper studies the proposed smoothing scheme in-depth, beyond just showing a good empirical performance. This in-depth investigation includes theoretically characterizing the limitations and advantages of different graph smoothing protocols, proposing more expensive though tighter computing methods, and presenting quite a few ablation studies, especially those revealing the benefits of sparsity.

Weaknesses:
- The proposed method is a bit specific to graph neural networks with node perturbations. In other words, the method could be further benefited from extensions to a wider range of threat models, i.e., node addition/removel, edge feature perturbations, etc.

- More training techniques can be applied to further strengthen the certified robustness guarantee. For example, SmoothMix training (Jeong et al), SmoothAdv training (Salman et al), and DRT training (Yang et al).

Overall, I think these weaknesses are overall not critical. Disclaimer: I'm not actively working with GNNs. So I didn't evaluate the impact of this paper to GNN community nor whether the evaluation follows standardized protocols. I will refer to other reviewers' comments on these aspects to adjust my score if necessary.
questions: In terms of suggestions for the authors, see weaknesses.
Questions on writing:
- Line 234 and Appendix I: in the training process, how is the node mask t optimized?
- Line 284: what does $\epsilon=0.022$ stand for?
Suggestions on writing:
- Line 252-262: from the equation formulation, it is straightforward to see that the proposed certification is independent of perturbed feature dimensions $d$. Maybe we can omit Figure 4(a) and Line 252-262 to the appendix since it consumes much space.
limitations: See weaknesses.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a new gray-box certification method for graph neural networks (GNNs) using smoothing. Unlike previous approaches, it uses utilizes the underlying message passing based principle (e.g., deleting edges, ablating nodes, etc) to obtain a stronger guarantee. To achieve certification, the authors first derived the worst case change in label probability and then proposed practical way to give a sound lower bound.

strengths_and_weaknesses: Strength:

1. This method can give stronger certification compared to previous approach.
2. The theoretical results presented in this paper are novel and practical.
3. Experimental evaluation shows both speed and certification benefits compared to pure black box methods.

Weaknesses:

1. I am a bit concerned about the confidence level alpha=0.05 used for certification, because it means that the guaranteed robustness only holds with a probability of 95%. Some existing works such as (Zugner and Gunnemann 2019)  using deterministic certification methods do not have this limitation.

questions: Can you show results with different confidence levels and see how strong the method is with a smaller alpha? How many samples are required and what is the certification accuracy for different levels of alpha?

limitations: Yes, the author discussed limitations of this work explicitly and I see no obvious negative societal impacts.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a technique to certify the robustness of Graph Neural Networks. Inspired by randomized smoothing, the proposed method takes advantage of the graph structure to get obtain various certificates (e.g., on accuracy). For the studied threat model, these certificates are tighter than proposed in the literature so far. The threat model consist of allowing an adversary to arbitrarily manipulate the features (i.e., emitted messages) of a subset of nodes.
strengths_and_weaknesses: Strengths:
* The authors are the first to truly take advantage of network structure to certify GNN (at least from a smoothing perspective).
* The results clearly demonstrate that they can certify a larger proportion of cases than prior methods (when the number of features increases).
* The threat model is fairly broad and could have practical applications

Weaknesses:
* It would help the reader to explain a bit why the studied threat model is interesting and when it arises in the real-world. The certification method which relies on smoothing can only be used for offline analysis or, if used online (let's say on the network of machine), will be prohibitly expensive to run (i.e., sampling of various network configurations).
* My knowledge of graph robustness is fairly limited, but I assume there has been a number of works (not specifically designed for machine learning applications) that also provide robustness to the threat model considered (e.g., r-robustness). Maybe expanding the literature survey slightly and expanding the experiments to demonstrate that r-robust networks are 100% certifiable (using the proposed approach) would help make a stronger and broader point.
questions: The paper is well-written. I would appreciate if the authors address the weaknesses stated above.
limitations: Yes, the limitations are reasonably addressed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a robustness certification against adversarial attacks on graph data. The model will randomly ablate some nodes and delete some edges so that the adversarial impact on certain nodes will not propagate to the target node with high probability. They show that the pipeline achieves good robustness, especially at larger distances.
strengths_and_weaknesses: ## Strengths

* The robustness certification can be verified against arbitrary perturbation on the adversarial nodes. In the pipeline, the certification is achieved by blocking the messages from the adversarial nodes. Therefore, it can provide certification without restricting the perturbation magnitude on each node. This seems a realistic setting to me - in practical graph data settings, considering the number of adversarial nodes (users) is more important than considering the magnitude of adversarial perturbation on each node. 

* The experimental evaluation is comprehensive. The authors evaluate their approach in different settings, e.g. with skip-connections and under different sparsifications. These approaches show the flexibility of their approach to different cases.


## Weaknesses:

* Only feature-based attack robustness is considered. Actually, a wide range of attacks on GNNs will focus on edge-modification attacks (e.g. [a,b]). The paper does not discuss the applicability of their approach against this type of attack. Actually, it feels to me that the proposed approach can still be adapted as long as both nodes of the edge are considered as adv nodes, although such a bound seems like a loose bound.

[a] Zügner D, Günnemann S. Adversarial Attacks on Graph Neural Networks via Meta Learning[C]//International Conference on Learning Representations. 2018.

[b] Xu K, Chen H, Liu S, et al. Topology attack and defense for graph neural networks: an optimization perspective[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019: 3961-3967.

* The certification result is node-specific and not applicable in practice. If I understand correctly, the exact certification provided by the algorithm is "given a target node, the adversarial perturbation on a specific node set can/cannot be certified to be robust", but not "given a target node, we can allow arbitrary N nodes to be attacked". The latter is a more useful certificate that can be achieved by previous approaches, while the current one is limited to a specified node set.
questions: In the experimental setup, how is the subgraphs generated exactly? Since the nodes are randomly sampled, does the edge only exist if both nodes are sampled? How do you guarantee that the graph is still connected and not too sparse?

I am curious why the authors keep mentioning gray-box certification in contrast to black-box. Since the certification is performed by the model itself, the model will for sure know the exact data as well as other information. So I can only imagine the white-box (which also satisfies gray-box and black-box) setting of the certification.
limitations: As mentioned in the weaknesses, I think the authors can improve by considering the edge-based attacks.
review_title: null

Meta-review: metareview: The paper proposes a novel approach to certify the robustness of graph neural networks via randomized smoothing. It does so by treating the networks as ``gray-box'' models and leveraging message passing routines. This yields an improved lower bound on probabilistic certification.

All reviewers recognized the technical quality of the work and its novel perspective on adversarial robustness for graph neural networks. Some concerns regarding the probabilistic certification and the experimental details have been successfully addressed during the rebuttal.

The paper is recommended for acceptance, conditioned on the inclusion of the additional experiments and discussions arisen in the rebuttal.
confidence: Certain
Decision: Accept