acceptodds
Under review as a conference paper at ICLR 2027

CoSG: Counterfactual Explainers for Signed Graphs

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural network, explainable AI, counterfactual explanation, signed graph

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_4fWBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CoSG generates counterfactual explanations for link predictions by frozen signed graph neural networks. An amortized MLP predicts two masks over existing edges in a target pair’s local computation graph: one controls edge existence, and the other controls sign preservation or flipping. These masks define differentiable scores for preserving, removing, or sign-flipping each edge. Training combines a prediction-changing objective with perturbation penalties and entropy regularization; inference selects the highest-scoring discrete action per edge.

The paper evaluates CoSG on BitcoinOTC, Twitter, and Epinions using SGCN and SNEA backbones. Across ten runs, it reports higher prediction-flip rates than the evaluated baselines, generally competitive sparsity, and millisecond-scale inference. Additional experiments examine full-test performance, backbone depth, loss components, perturbation restrictions, and hyperparameter sensitivity.

Critical strengths
  1. The method directly represents sign changes as counterfactual interventions. Separating edge existence from polarity provides a simple differentiable formulation for preservation, deletion, and sign flipping. The perturbation-restricted study in Table 9 demonstrates that sign flipping is particularly consequential for the evaluated signed-graph models. This is useful evidence about an aspect that deletion-only explanations miss.

  2. Amortized inference offers a practical benefit, supported across several settings. CoSG learns from 300 training pairs and generates explanations for held-out pairs without instance-specific optimization. Table 1 reports substantial validity gains across three datasets and two backbones, while the full-test results in Table 4 remain close to the sampled evaluation. Together, these results provide encouraging evidence for efficient explanation generation within the evaluated graphs.

Critical weaknesses
  1. The comparisons confound the proposed method with access to a more powerful perturbation space. CoSG can both remove edges and flip signs, whereas all learned baselines in Table 6 are restricted to removal. Random sign flipping does not replace a learned or optimized sign-aware counterfactual baseline. This matters because Table 9 shows that CoSG-FL nearly matches full CoSG: validity is 0.66 versus 0.68 on BitcoinOTC, 0.55 versus 0.58 on Twitter, and 0.50 versus 0.52 on Epinions with SGCN. These results suggest that much of the advantage may come from allowing sign flips. A baseline using the same three actions—for example, instance-specific optimization of the same relaxation—is needed to establish the contribution of the learned policy and objective.

  2. The evaluation supports sparse prediction-changing perturbations, but does not establish several stronger explanation claims. Sparsity is averaged across instances without separating successful from unsuccessful outputs, and no restoration test or small-instance exact comparison assesses whether successful perturbations contain unnecessary edits. Moreover, Appendix C.4 defines Fidelity as absolute change in the original class’s logit, although Section 4.1 describes a confidence decrease. This metric can reward increased confidence in the original prediction and is sensitive to logit scaling. Finally, validity accepts any change among positive, negative, and non-edge classes, so it does not reveal how often CoSG actually reverses polarity. These omissions limit the evidence for minimal sign-changing explanations; the further claims of actionable recourse and causal dependencies are not validated by the reported experiments.

Questions for authors
  1. Controlled comparison: How does CoSG compare with an instance-specific optimizer using the same preserve/remove/flip actions, relaxation, and perturbation costs? Does its validity–edit-count advantage persist when the perturbation space is matched?

  2. Evaluation clarification: Can you report class-transition counts, successful-only edit counts, and the fraction of successful explanations that remain valid after restoring individual edits? Is the implemented Fidelity metric the absolute logit change in Appendix C.4 or the confidence decrease described in Section 4.1?

  3. Access assumptions: The introduction states that explanation proceeds “without access to model internals,” but CoSG uses encoder embeddings and differentiates the prediction loss through a weighted SGNN. What access is actually required, and how are weighted positive/negative aggregation and normalization implemented for each backbone?

  4. Instance conditioning: The edge representation contains candidate-edge endpoint embeddings but no explicit target-pair representation or original edge sign. How does the policy distinguish different target predictions with overlapping computation graphs? Is dependence on the target entirely through recomputing embeddings on each extracted graph?

Reviewer_kLtAOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes CoSG, a counterfactual explanation method for signed graphs, primarily targeting link sign prediction in Signed Graph Neural Networks. The method employs two learnable masks to separately model edge existence and edge polarity, enabling three types of operations: edge preservation, edge removal, and sign flipping. The authors further introduce a differentiable perturbation mechanism and train an explainer that generalizes across instances by combining a counterfactual prediction loss, perturbation sparsity constraints, and regularization terms. Experiments on three real-world signed graph datasets and two SGNN models demonstrate that CoSG outperforms existing baselines in counterfactual validity, sparsity, and inference efficiency.

Critical strengths
  1. Introducing counterfactual explanations for link sign prediction in signed graphs is a meaningful research direction. Compared with conventional graph explanation methods, CoSG explicitly considers both edge existence and edge polarity, enabling counterfactual explanations involving edge removal and sign flipping, which makes the approach well suited to signed graph settings and potentially useful in practice.

  2. The experiments cover three real-world signed graph datasets and two SGNN architectures, along with ablation studies, hyperparameter sensitivity analyses, and efficiency comparisons. CoSG achieves substantial performance improvements across multiple experimental settings, while its shared explainer avoids the computational overhead of instance-specific optimization during inference.

Critical weaknesses
  1. The authors argue that existing graph counterfactual explanation methods cannot handle edge polarity, motivating the need for a new sign-aware framework. However, existing counterfactual explanation methods could potentially be extended to signed graphs by treating positive and negative edges as different relation types. The paper does not sufficiently explain why such a straightforward extension would be inadequate.

  2. In Table 1, most learning-based counterfactual explanation baselines, such as CF-GNNExplainer and CF2, only support edge removal, whereas CoSG allows both edge removal and sign flipping. Therefore, the compared methods operate over different perturbation search spaces, raising concerns about the fairness of the comparisons.

  3. The authors describe CoSG as a model-agnostic counterfactual explainer. However, in Section 3.1, the explainer requires access to node embeddings produced by the target SGNN and performs differentiable optimization through the frozen SGNN during training. Therefore, the method relies on internal model representations and gradient propagation rather than solely on prediction outputs, making the model-agnostic claim insufficiently justified.

  4. Although CoSG achieves the highest Validity in Table 1, its success rates range from only 52% to 82%, indicating that a considerable proportion of the generated counterfactual graphs fail to change the model's predictions. The authors should report the average number of perturbations specifically for valid counterfactual explanations and further evaluate the trade-off between counterfactual validity and perturbation cost.

Questions for authors

Weaknesses

Reviewer_C3LXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper claims to be the first work to investigate counterfactual explanations for signed graphs. The problem is formulated as finding the smallest set of edge removals and sign flips that change the predicted class of some edge (s,t). The proposed method, CoSG, trains an MLP to predict for each edge whether to keep/remove/flip an edge. The MLP is trained once with losses to alter the SGNN prediction, minimize perturbations, and encourage binary values; and then is applied to unseen pairs.

Critical strengths
  • The problem is relevant, as there is little work on counterfactual explanations on SGNNs
  • The method is clearly described sign flips are a natural extension for SGNNs, and results show significant increases in validity and fidelity
Critical weaknesses
  • The evaluation does not separate the value of flipping signs from the value of CoSG as every learned baseline can only remove edges
  • Sparsity does not necessarily indicate small, interpretable explanations. Referring to Figure 8, almost every edit flips an edge incident to s or t, so how does the sparsity and validity compare to just greedily flipping incident edges on s and t?
  • Counterfactual explanations are untargeted, so a change from positive to nonexistent is also considered a valid explanation, but this can inflate validity because positive-to-nonexistent is easier than positive-to-negative.
  • Offline training cost is claimed to be amortized but training time is not reported
Questions for authors
  • How does CoSG compare to a simple baseline such as CF-GNNExplainer but trained to predict a [-1,1] mask (-1: sign flip, 0: remove, 1: keep) instead of a [0,1] mask?
  • How long does offline training take?
  • What validity and sparsity do you get from a simple baseline that flips every edge incident on s or t?
  • How does sparsity change when only valid explanations are counted? What fraction of valid explanations involve the nonexistent class? Do you allow edits on the target edge (s,t) [if flipping target edge is allowed, then it can trivially explain the sign]?

Comments on the paper

1 comment
Area_Chair_esn7OpenReview ↗

Please check the rebuttal

Dear Reviewers,

The deadline for the discussion is approaching soon. Please check the rebuttal and respond accordingly.

Best,

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.