Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies classifiers that collectively output many predictions based on a single input. Existing adversarial robustness certificates assume that an adversary can use different perturbed inputs to attack different predictions, and ignore the fact of a single shared input, thereby being overly pessimistic. This paper proposes a collective certificate that computes the number of simultaneously certifiable nodes for which the predictions can be guaranteed to be stable (not change). It is conducted basically by fusing individual certificates into a provably stronger certificate through explicitly modeling locality. 
Pros: This is the first effort that considers collective robustness certificate. 
Cons: 
1.	As discussed in the paper, the proposed approach is designed to exploit locality. Without locality, it is equivalent to a naïve combination of base certificates that sums over perturbations in the entire graph. 
2.	The writing of the paper can be improved. The abstract seems to be unfinished. It appears to be hard to include sufficient preliminaries to clearly describe the research problem in a conference paper. It’s probably better to have a longer version as a journal paper.  

review_title: This paper proposes a new concept called “collective robustness certificate” that computes the number of predictions which are simultaneously guaranteed to remain stable under perturbation. 

final_score: rating: 7: Good paper, accept
review_content: ** Summary:
In the context of structured prediction, where multiple predictions are simultaneously made based on a single input, this works argue that existing robustness certificates independently operating on each node prediction end up with overly pessimistic results. Rather than that, this work advocates to collectively certify the overall accuracy using a single perturbed graph at a time. Starting from the building-blocks of base certificates, the authors formulate a global optimization problem, which is made tractable via a number of relaxation steps resulting in a final mixed-integer linear programming (MILP). Experimental results demonstrate clear advantage of the proposed certificates over base ones, with reasonable computational overheads coming from solving the MILP.

The paper is well-motivated, well-written and easy to follow. I think this is a valid method to assess robustness of classifier satisfying locality like GCN.

** Strength:
 - This work is well-motivated. The arguments are valid on the limitations of independent based certificates for collective tasks. Experimental results convincingly show how such certificates are pessimistic in the addressed context.
 - The writing is clear and well-structured, easy to understand and follow. 
 - Nice discussion on the limitations
 
** Limitations:
 - Typos:
 	+ Eqn. (2): $f_n(\boldsymbol {X}^{'}, \boldsymbol{A}^{'}) = f_n(\boldsymbol{X}^{''}, \boldsymbol{A}^{ \textcolor{red}{''}})$

 	+ Eqn. (7): $\boldsymbol {X}^{''}_{i,d} = \psi_i^{(n)}\boldsymbol {\textcolor{red}{X}}^{'}_{i,d} + (1-\psi_i^{(n)})\boldsymbol {\textcolor{red}{X}}_{i,d}$
 
 

** Justification of rating: overall this is an interesting paper. The motivation, arguments and results are convincing.
review_title: Interesting paper. Well-motivated. Good results

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper addresses the limitation of the existing adversarial robustness certificates that ignores that a single shared input is present, and thus assumes an adversary can use different perturbed inputs to attack different predictions. A novel collective certificate fusing single certificates into a stronger one, is proposed by explicitly modeling local structure of input data using graph convolution node classifiers. In terms of certified ratio, the collective certificate significantly improve the results compared with existing individual certificates. 

-quality: the technical quality is sound.

-clarity: the input data, problem formulation and method are clearly described.

-originality & significance: it is the first attempt in considering collective robust certificates (CRCs) by fusing individual adversarial certificate. As shown in the experiments, the certified ratio of the CRC is significantly improved over existing adversarial one. I think the collective robust certificate has some impacts for robust graph node classifications.

Pros: The paper is well motivated. The problem and the method are both clearly presented. The improvements of the collective robust certificate over the existing ones is sufficiently high in terms of certified ratios.

Cons: I do not find any notable weaknesses.
review_title: This paper first proposes a collective robustness certificate by fusing individual certificates into a provably stronger one, which significantly outperforms existing adversial certificates. Thus, I vote for accepantance.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary
-------------
Current methods on adversarial robustness certificates consider data points independently which are highly pessimistic for structured data. This work proposes the first collective robustness certificate that considers the structure of the graph by modeling locality in order to derive stronger guarantees  that the predictions remain stable under perturbations.

This work focuses on Graph Neural Networks comparing between a Naive collective certificate (baseline) and a proposed collective certificate that combines single-node certificates effectively. 

The experiments compares these two methods against certified ratio vs. attribute and edge perturbations on the datasets Cora-ML, Citeseer, and PubMed.

Pros
------
- The paper is well-written and easy to follow.
- The paper tries to address a very common problem of adversarial attacks where data points are structured. Although it is a common problem, it was not explored with respect to collective robustness certificates before this work.
- The paper shows a novel, effective way of combining individual certificates by incorporating locality.
- The paper presents an LP-relaxation method that allows us to solve the certificate fast for large graphs where mixed-integer problems are prohibitively costly.
- The paper shows strong theory and experiments to illustrate the efficacy of the proposed collective certificate.
- The experiments show run-time and uncertainty measures with multiple runs for statistical significance.

Questions
--------------
- Is there a reason why [1] was not discussed in the paper? it is highly relevant as it also studies adversarial robustness for structural attacks. 
- How does the proposed method apply to robust Associative Markov Networks (AMN) in [1]?
- Did you try running the proposed method on WebKB and Reuters which are present in this work [1]?
- How does the linear relaxation in this work differ from the one provided in [1]?
- How would the proposed method compare against robust AMN [1]?
- Can the findings be used to come up with robust methods outside classification, like segmentation and scene understanding?

In summary, I like the novelty of this method and the through experiments that were conducted that illustrate the efficacy of the proposed collective certificate, thus I recommend an accept.

[1] Kai Zhou, Yevgeniy Vorobeychik. Robust Collective Classification against Structural Attacks. UAI 2020. 

------- Post rebuttal
I am satisfied with most of the rebuttal the authors have provided, and I have raised my score to an 8. 

review_title: great work but some comparisons could be missing.

Meta-review: This paper considers a new setting of robustness, where multiple predictions are simultaneously made based on a single input. Different from existing robustness certificates which independently consider perturbation of each prediction, the authors propose collective robustness certificate that computes the number of predictions which are simultaneously guaranteed to remain stable under perturbation. This yields more optimistic results. Most reviewers think this is a very interesting work and the authors present an effective method to combine individual certificate. The experimental results are convincing. I recommend accept.
Decision: Accept (Poster)