We investigate certified robustness for GNNs under graph injection attacks.
Existing research only provides sample-wise certificates by verifying each node
independently, leading to very limited certifying performance. In this paper,
we present the first collective certificate, which certifies a set of target
nodes simultaneously. To achieve it, we formulate the problem as a binary
integer quadratic constrained linear programming (BQCLP). We further develop a
customized linearization technique that allows us to relax the BQCLP into
linear programming (LP) that can be efficiently solved. Through comprehensive
experiments, we demonstrate that our collective certification scheme
significantly improves certification performance with minimal computational
overhead. For instance, by solving the LP within 1 minute on the Citeseer
dataset, we achieve a significant increase in the certified ratio from 0.0% to
81.2% when the injected node number is 5% of the graph size. Our step marks a
crucial step towards making provable defense more practical.

我们研究图注入攻击下 GNN 的认证鲁棒性。现有研究仅通过验证每个节点提供逐节点的证书，导致认证性能非常有限。在本文中，我们首次提出了集体证书，同时为一组目标节点提供认证。为了实现这一目标，我们将问题形式化为二次约束的线性规划问题，并进一步开发了一种定制线性化技术，使我们能够将问题松弛为线性规划，从而能够高效地求解。通过全面的实验证明，我们的集体认证方案显著改善了认证性能，同时具有最小的计算开销。例如，在 Citeseer 数据集上在 1 分钟内解决线性规划问题时，当注入节点数量占图大小的 5% 时，我们的认证比例从 0.0% 增加到 81.2%。我们的工作是实现可证明的防御更加实际的关键进展。