Generating Robust Counterfactual Witnesses for Graph Neural Networks
<|reference_start|>Generating Robust Counterfactual Witnesses for Graph Neural Networks: 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.<|reference_end|>
@article{qiu2024generating,
    title={Generating Robust Counterfactual Witnesses for Graph Neural Networks},
    author={Dazhuo Qiu, Mengying Wang, Arijit Khan, Yinghui Wu},
    journal={arXiv preprint arXiv:2404.19519},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.19519},
    primaryClass={cs.LG cs.DB}
}