CoSG: Counterfactual Explainers for Signed Graphs

Signed graph neural networks (SGNNs) have shown strong performance in modeling positive and negative relations in signed graphs. However, their black-box nature limits the understanding of prediction behavior and raises concerns about model trustworthiness. Counterfactual explanations (CEs) provide actionable recourse and reveal causal dependencies by identifying minimal input perturbations that would alter model predictions. Despite their promise, CEs remain largely unexplored for signed graphs, where predictions depend jointly on graph structure and relation polarity. To bridge this gap, we first study the problem of generating counterfactual explanations for signed graphs. This problem is particularly challenging because it requires optimizing over a discrete and heterogeneous perturbation space to identify sparse yet effective explanations while enabling the trained explainer to generalize to unseen instances. To address these challenges, we propose CoSG, a novel model-agnostic explainer that generates counterfactual explanations for link sign prediction on signed graphs. Specifically, CoSG decouples edge polarity from edge existence to enable differentiable sign-aware perturbations and trains the explainer across instances under a unified objective that balances counterfactual validity and perturbation sparsity, allowing CoSG to efficiently generate concise, actionable explanations for unseen instances. Extensive experiments on real-world signed graphs demonstrate the superiority of CoSG over state-of-the-art graph explainers in generating counterfactual explanations.