Models for image segmentation, node classification and many other tasks map a
single input to multiple labels. By perturbing this single shared input (e.g.
the image) an adversary can manipulate several predictions (e.g. misclassify
several pixels). Collective robustness certification is the task of provably
bounding the number of robust predictions under this threat model. The only
dedicated method that goes beyond certifying each output independently is
limited to strictly local models, where each prediction is associated with a
small receptive field. We propose a more general collective robustness
certificate for all types of models. We further show that this approach is
beneficial for the larger class of softly local models, where each output is
dependent on the entire input but assigns different levels of importance to
different input regions (e.g. based on their proximity in the image). The
certificate is based on our novel localized randomized smoothing approach,
where the random perturbation strength for different input regions is
proportional to their importance for the outputs. Localized smoothing
Pareto-dominates existing certificates on both image segmentation and node
classification tasks, simultaneously offering higher accuracy and stronger
certificates.

本文提出了一种基于新型局部化随机平滑方法的更普遍的模型合集鲁棒性认证方法，并在图像分割和节点分类任务上得到更高的准确性和更强的认证。