Graph Neural Networks (GNNs) have emerged as a prominent graph learning model
in various graph-based tasks over the years. Nevertheless, due to the
vulnerabilities of GNNs, it has been empirically proved that malicious
attackers could easily corrupt the fairness level of their predictions by
adding perturbations to the input graph data. In this paper, we take crucial
steps to study a novel problem of certifiable defense on the fairness level of
GNNs. Specifically, we propose a principled framework named ELEGANT and present
a detailed theoretical certification analysis for the fairness of GNNs. ELEGANT
takes any GNNs as its backbone, and the fairness level of such a backbone is
theoretically impossible to be corrupted under certain perturbation budgets for
attackers. Notably, ELEGANT does not have any assumption over the GNN structure
or parameters, and does not require re-training the GNNs to realize
certification. Hence it can serve as a plug-and-play framework for any
optimized GNNs ready to be deployed. We verify the satisfactory effectiveness
of ELEGANT in practice through extensive experiments on real-world datasets
across different backbones of GNNs, where ELEGANT is also demonstrated to be
beneficial for GNN debiasing. Open-source code can be found at
this https URL

使用 ELEGANT 框架，我们对 Graph Neural Networks (GNNs) 的公平性水平进行了理论认证分析，该框架可以有效抵御恶意攻击者对输入图数据的扰动，并在不重新训练 GNNs 的情况下提供可信度保证。

ELEGANT：关于图神经网络公平性的认证防御

ELEGANT: Certified Defense on the Fairness of Graph Neural Networks

Patch adversarial attacks on images, in which the attacker can distort pixels
within a region of bounded size, are an important threat model since they
provide a quantitative model for physical adversarial attacks. In this paper,
we introduce a certifiable defense against patch attacks that guarantees for a
given image and patch attack size, no patch adversarial examples exist. Our
method is related to the broad class of randomized smoothing robustness schemes
which provide high-confidence probabilistic robustness certificates. By
exploiting the fact that patch attacks are more constrained than general sparse
attacks, we derive meaningfully large robustness certificates against them.
Additionally, in contrast to smoothing-based defenses against L_p and sparse
attacks, our defense method against patch attacks is de-randomized, yielding
improved, deterministic certificates. Compared to the existing patch
certification method proposed by Chiang et al. (2020), which relies on interval
bound propagation, our method can be trained significantly faster, achieves
high clean and certified robust accuracy on CIFAR-10, and provides certificates
at ImageNet scale. For example, for a 5-by-5 patch attack on CIFAR-10, our
method achieves up to around 57.6% certified accuracy (with a classifier with
around 83.8% clean accuracy), compared to at most 30.3% certified accuracy for
the existing method (with a classifier with around 47.8% clean accuracy). Our
results effectively establish a new state-of-the-art of certifiable defense
against patch attacks on CIFAR-10 and ImageNet. Code is available at
this https URL

本研究介绍了一种针对图像贴片对抗攻击的可证明防御方法，并通过对以往方法的比较，证明了该方法在 CIFAR-10 和 ImageNet 上能有效提高防御水平，是当前领先的防御方法之一。