论文标题
离散数据的有效鲁棒性证书：图形，图像等的稀疏感知随机平滑
Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More
论文作者
论文摘要
现有的技术来证明模型的鲁棒性用于离散数据仅适用于一小类模型，或者以效率或紧密度为代价。此外，正如我们的发现所表明的那样，它们不考虑输入中的稀疏性，通常对于获得非平凡的保证至关重要。我们根据随机平滑框架提出了一个模型不合时宜的证书，该证书涵盖了早期工作，并且是紧张，高效和稀疏感。它的计算复杂性不取决于离散类别的数量或输入的维度（例如图形大小），从而使其高度扩展。我们显示了方法对各种模型，数据集和任务的有效性 - 特别是突出了其用于图神经网络的使用。到目前为止，由于离散和非i.i.d，很难获得GNN的可证明的保证。图数据的性质。我们的方法可以证明任何GNN并处理图形结构和节点属性的扰动。
Existing techniques for certifying the robustness of models for discrete data either work only for a small class of models or are general at the expense of efficiency or tightness. Moreover, they do not account for sparsity in the input which, as our findings show, is often essential for obtaining non-trivial guarantees. We propose a model-agnostic certificate based on the randomized smoothing framework which subsumes earlier work and is tight, efficient, and sparsity-aware. Its computational complexity does not depend on the number of discrete categories or the dimension of the input (e.g. the graph size), making it highly scalable. We show the effectiveness of our approach on a wide variety of models, datasets, and tasks -- specifically highlighting its use for Graph Neural Networks. So far, obtaining provable guarantees for GNNs has been difficult due to the discrete and non-i.i.d. nature of graph data. Our method can certify any GNN and handles perturbations to both the graph structure and the node attributes.
