This paper introduces a new class of explanation structures, called robust
counterfactual witnesses (RCWs), to provide robust, both counterfactual and
factual explanations for graph neural networks. Given a graph neural network M,
a robust counterfactual witness refers to the fraction of a graph G that are
counterfactual and factual explanation of the results of M over G, but also
remains so for any "disturbed" G by flipping up to k of its node pairs. We
establish the hardness results, from tractable results to co-NP-hardness, for
verifying and generating robust counterfactual witnesses. We study such
structures for GNN-based node classification, and present efficient algorithms
to verify and generate RCWs. We also provide a parallel algorithm to verify and
generate RCWs for large graphs with scalability guarantees. We experimentally
verify our explanation generation process for benchmark datasets, and showcase
their applications.

介绍了一种新的解释结构类别，称为鲁棒反事实证人，用于提供图神经网络的稳健而反事实和事实解释。研究了 GNN 基于节点分类的这类结构，并提供了高效算法来验证和生成鲁棒反事实证人。通过对基准数据集进行实验证实了解释生成过程，并展示了它们的应用。