acceptodds
Under review as a conference paper at ICLR 2027

RACE: RELATION-LEVEL COUNTERFACTUAL EXPLANATIONS FOR HETEROGENEOUS GRAPH NEURAL NETWORKS

Abstract

Counterfactual explanations of graph neural networks identify edge deletions that flip a prediction. On heterogeneous graphs, however, existing methods first collapse the graph into untyped edges, so they cannot answer the question a domain expert actually asks: which relation type drives this prediction? We present RACE (Relation-Aware Counterfactual Explanations), which gives this question an exact, per-instance answer. For every explained instance, an exhaustive search over relation subsets returns the certified minimum relation-deletion set that flips the prediction—or an explicit report that no such deletion exists; each relation-level answer is then refined into a typed edge set within the attributed relations, verified on the discrete model by single-edge restoration. The relation-level answer is exact and deterministic given the frozen backbone, whereas soft-mask baselines vary by 6–8 pp in success rate across runs differing only in random ordering. On ACM, a Cora-derived graph, and ogbn-mag, RACE improves counterfactual success rate over the strongest baseline by up to +2.7 pp while deleting fewer edges, and attains the highest success rate among all same-task baselines on every dataset; the advantage reproduces across four backbones on ogbn-arXiv and on DBLP, with cross-seed relation-set agreement up to 0.89. A synthetic study with known generating mechanisms confirms that the search recovers the relation the trained model actually relies on—and reports infeasibility rather than fabricating an attribution when the model has learned none—so the explanations stay trustworthy exactly where explanations matter.

Primary area:
interpretability and explainable AI
Keywords:
Heterogeneous graphs, graph neural networks, counterfactual explanations, instance-level interventions, explanation verification

Reviews

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

RACE studies counterfactual explanations for frozen heterogeneous GNNs using relation types as intervention units. It exhaustively enumerates relation subsets to find a prediction-flipping deletion that minimizes a lexicographic cost: relation count, local edge fraction, and prediction margin. When no subset flips the prediction, it reports relation-level infeasibility. For feasible instances, it refines the selected relations into an edge-level explanation through discrete single-edge restoration; other instances receive a flat edge-explainer fallback. Completed restoration scans certify single-edge-restoration irreducibility, rather than global edge minimality.

Validation includes several academic-network datasets, multiple GNN backbones, synthetic mechanisms, stability and perturbation studies, and exact edge enumeration on small synthetic subgraphs. The main comparison reports success-rate improvements of approximately 0.8–2.7 percentage points over CF2-hetero, alongside lower reported deletion costs.

Critical strengths
  1. A precise, auditable relation-level counterfactual formulation. Exhaustive enumeration provides an exact answer for small relation vocabularies and distinguishes relation-level infeasibility from search failure. The observed non-monotonicity also motivates checking subsets rather than relying only on full relation removal. This is a useful explanation interface for typed graphs.

  2. The hierarchy connects relation-level explanations to concrete edge interventions. The refinement stage verifies prediction flips on the discrete model and explicitly distinguishes completed irreducibility checks from budget-limited outputs. Experiments across several datasets and backbones provide evidence that the approach is applicable beyond one trained model.

Critical weaknesses
  1. The reported deletion costs are inconsistent with the stated evaluation protocol, undermining the claim of improved success with fewer deletions. Appendix C states that all-target cost assigns failures a penalty of 1.0. Therefore, this average must be at least (1-\mathrm{CSR}). Yet Table 1 reports ACM RACE-hier CSR of 0.224 and cost of 0.176, whereas the stated convention requires cost of at least 0.776. Similar contradictions occur elsewhere in the table. Appendix B additionally says hierarchical fallback costs are imputed using the per-seed CF2 mean, rather than measured from the returned interventions. These issues prevent interpreting the cost comparison as reported. Moreover, RACE-per-edge and PNS-hetero have lower listed costs than RACE-hier on all three datasets, and the common-success comparison reports cheaper hierarchical explanations in only 44% of Cora cases. The success-rate gains remain interesting, but the claimed cost advantage requires consistent, directly measured results.

  2. The scope of the guarantees and their applicability to graph deletion are insufficiently established. The experiments zero message entries while retaining attention normalization over the intact edge set (Section 4.1 and Appendix B). This defines a specific message-masking intervention; physically removing edges and recomputing attention can produce different predictions. Consequently, the certificates establish validity under the specified masking operator, while the broader edge-deletion framing needs qualification or additional validation. The scalability extension also invokes a “first-order Lipschitz bound” without providing its derivation, admissibility conditions, or stopping rules. Given the documented non-monotonicity, the manuscript does not establish when this budgeted search can certify optimality or infeasibility, despite claiming the same output contract as exhaustive search.

Questions for authors
  1. Evaluation clarification: What exact formula produced Table 1’s all-target costs? Please reconcile the values with the failure penalty in Appendix C and explain the fallback-cost imputation in Appendix B. Can you provide measured costs under consistent all-target, successful-only, and common-success conventions?

  2. Intervention clarification: Are attention coefficients recomputed after actual edge removal anywhere in the evaluation? How do relation feasibility, explanation validity, and the main comparative results change when normalization is recomputed on the surviving graph?

  3. Guarantee clarification: Please specify the branch-and-bound bound and explain why it is admissible. When its budget expires, does the method return an uncertified incumbent or an unknown status, rather than certified infeasibility? Please distinguish these outcomes explicitly.

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

This paper studies counterfactual explanations for graph neural networks on heterogeneous graphs, i.e., graphs with several edge (relation) types. The authors argue that existing counterfactual explainers ignore edge types and so cannot say which relation type drives a prediction. They propose RACE, which explains a node's prediction at two levels: the relation types, and then the edges within them, whose removal changes the model's prediction.

Critical strengths

Nil

Critical weaknesses

W1. Limited novelty and small gains. The paper does not identify a challenge specific to heterogeneous graphs that prevents existing counterfactual explainers from being applied to them. Its components are established techniques applied to typed edges: edge-deletion masks with margin and sparsity losses (CF-GNNExplainer, CF2, RCExplainer), a Gumbel-Sigmoid relaxation, greedy deletion followed by one-at-a-time restoration, and NF/SF metrics borrowed from Cai et al. (2025). The only heterogeneity-specific step is grouping edges by relation type, and the paper applies the same grouping to every baseline (the "-hetero" variants), which suggests it is a mechanical adaptation rather than a technical contribution. The relation search is exhaustive enumeration; with K = 2 in all four primary benchmarks (line 268), it amounts to trying four subsets.

The gains do not compensate for this. Table 1 reports +0.8/+2.7/+1.4 pp CSR over CF2-hetero on ACM/Cora/ogbn-mag. These margins are smaller than the variation the paper reports for CF2 across runs that differ only in random ordering (line 348: 0.216 vs. 0.276 on ACM, 0.452 vs. 0.687 on Cora). Taken together, the method reads as an adaptation of existing counterfactual explainers to typed edges, and the results do not show that this adaptation yields a clear improvement.

W2. Misplaced motivation. The authors argue that identifying which edge type drives a prediction is critical, framing it in the abstract and introduction as "the question a domain expert actually asks." I am not convinced. The interplay of different edge types is at the core of heterogeneous graphs, and when a node's incident edges are diverse, a particular edge type need not drive its prediction; the decision may emerge from their combination. Therefore, I believe the paper's motivation is misplaced: targeting edge types one by one is the wrong approach, and focusing on their joint role is better. I agree that a single edge type could drive a prediction in certain cases. However, that forms a special case which the joint approach will still catch.

Can the authors support the claim about domain experts with sources? For example, citations to user studies, any interviews with practitioners, or applied work in which experts explicitly ask which relation type drives a prediction, rather than how several relation types contribute together. Without them, the claim reads as an assumption that the paper's main motivation rests on.

W3. Subjective selection of the counterfactual. The paper states (line 183) that candidates are ranked by "fewest relation types first, then the smallest fraction of the instance's receptive-field edges, then the strongest flip." This ordering is a subjective design choice, and it need not yield the counterfactual, which are by definition minimal. Prioritising the fewest relation types hard-codes the single-edge-type view that I questioned above. It suppresses the interplay of edge types and inherits that bias.

W4. Inconsistency in the method. Let me first lay out the context:

  • Sec 3.3 learns a keep-score for each edge of a given type. It deletes the scored edges in batches until the label flips, then adds back a few of the deleted edges to compensate for the coarse granularity of batch deletion, as long as the label stays flipped. This process is repeated for each edge type.

  • Sec 3.4 selects the subset of edge types using Eq 6: "fewest relation types first, then the smallest fraction of the instance's receptive-field edges, then the strongest flip." At this point, the method has already determined which edge types and which edges within each type to delete.

  • Sec 3.5 then starts adding back deleted edges once more, this time ranked not by the keep-score but by a separate "gradient saliency of the original prediction" (line 199).

This second pruning step appears redundant and ad-hoc. Can the authors explain why the keep-score-based refinement in Sec 3.3 is insufficient, and why a different scoring criterion is needed here?

W5. Baselines adapted to the proposed method's setting.

Sec 4.1, line 292: "GNNExplainer-hetero, RACE-per-edge ... and C2Explainer objectives, all operating on the typed graph with per-relation masks"

The baselines appear to have been modified to produce per-relation-type masks, mirroring the proposed method, even though they naturally treat all relation types jointly. This favours the proposed method, since the comparison is staged on the formulation that the paper advocates. The authors are requested to report the results for the original, unmodified baselines versions. Without this, it is unclear whether the gap reflects the quality of the method or the handicap imposed on the baselines.

W6. Mismatch across tables. The proposed method's flat version numbers don't match across Tables 1 and 3.

DatasetCSR, Table 1CSR, Table 3Cost, Table 1Cost, Table 3
ACM0.216 ±\pm 0.0720.174 ±\pm 0.0460.1590.033
Cora0.452 ±\pm 0.1110.246 ±\pm 0.0710.3050.080
ogbn-mag0.168 ±\pm 0.0080.165 ±\pm 0.0090.3780.220

Their captions seem to indicate that the cost may be calculated differntly as table 1 mentions cost calculation on "all nodes" while table 3 mentions using "feasible-success cost" — the text doesn't define what this is and the reason for this different choice. The CSR columns share a definition and still disagree. Kindly clarify this discrepancy.

W7. Ommitted baselines. The paper omits comparison with a SOTA counterfactual technique ATEX-CF (Zhang et al. 2026) (cited by the authors), as well as some heterogeneous counterfactual explainers close to the paper's setting: CF-HGExplainer (Yang et al. 2023) and HENCE-X (Lv et al. 2023).

Zhang et al. "ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks" ICLR 2026

Yang et al. "Counterfactual Learning on Heterogeneous Graphs with Greedy Perturbation" KDD 23

Lv et al. "HENCE-X: Toward Heterogeneity-agnostic Multi-level Explainability for Deep Graph Networks" VLDB 2023

W8. Related work.

  • Citing two papers, that too from 2019 & 2020, doesn't do justice to the dozens of factual explainers in the literature today. The authors should go for a category based related work, citing survey papers, and using individual papers as representatives of those categories. Citing GNNExplainer and PGExplainer as the be all end all of factual explainers doesn't meet the bar.

  • The related work leaves out essential details even for a tl;dr version, e.g., RCExplainer does a lot more than just use a hinge loss. Its main contribution is its global approach to model decision boudnaries and identify robust counterfactuals.

W9. Cross seed agreement.

Appendix C, line 623: Stability. Cross-seed agreement of the relation set (identity agreement) and Jaccard of the deleted edge sets; for baselines, Jaccard of their masks across seeds.

Models initialised with different seeds are not required to learn identical logic, hence their explanations need not conform.

W10. Poor writing. The paper is very poorly written; information is just dumped in.

  • Section 1's contribution list needs revision; it is a compressed version of the methods section that bounce off the reader's head. The introduction should state what was done and why it matters, not elaborate how.

  • Section 1, line 55: "we solve Sv∗=arg minSCv(S)S_v^* = \text{arg min}_S C_v(S)... Because K is small, enumeration over the 2K subsets is exact" Sv,Cv,KS_v, C_v, K, saliency order: these haven't been introduced yet and are out of place in the intro; the reader is clueless of their meaning.

  • Section 3.3, line 167: "keeping the deletion point that minimizes validity minus λsp\lambda_{sp}-weighted cost?... restore deleted edges in descending keep-score while the satisfied set is preserved." What are validity and cost? What is a satisfied set? These terms are undefined at this point.

  • Please use \citep over \citet or \cite. For example, "GNNExplainer Ying et al. (2019) learns a mask" reads awkwardly; it should be "GNNExplainer (Ying et al., 2019) learns a mask".

  • Eq. 3 has formatting issues.

  • The experiment section's text reads like a log of an automated run rather than a narrative.

I recommend a thorough rewrite with a careful read-through before resubmission.

Questions for authors

Q1. What is the Flat version? RQ2 compares the method's full, heirarchical setup against a flat version. What is that flat version?

  1. line 295 writes "the flat verified pipeline (Sec. 3.3 without the relation phase)" indicating the learnt keep-mask applied across edge types rather than per edge type.
  2. while line 354 writes "Flat verified pipeline. Removing only the relation phase (greedy saliency deletion plus the same single-edge scan and budget, no relation search)" indicating dropping sections 3.3 and 3.4 entirely.

Which one is it? Please state the flat condition's exact algorithm.

Q2. If Sv∗S_v^* contains multiple relation types, does "one at a time" happen individually for each relation type or all types taken together?

Line 198: starting from G Sv∗G \ S_v^∗ (already flipped), we restore edges of Sv∗S_v^∗ one at a time in descending keep-importance order

Q3. What's the difference between Tables 1 and 2? They report the same metrics.

Line 308: Table 1 reports the same-frozen-backbone, targeted comparison Line 321: Table 2 compares all same-task counterfactual methods on the same frozen checkpoints with per-method RNG control.

  • Is table 1 for baselines that natively support heterogeneous graphs and table 2 for the others?
  • What is same-task here? Given a dataset and a trained model, Table 2 presents each explainer's performance on the datasets. What is the "same-task" part here that's absent in Table 1?

Q4. What's the difference between cost and feasible-success cost?

Q5. Appendix C, line 619 writes that failures are assigned the full-cost penalty 1.0. Table 1 reports RACE's CSR, its success rate in finding the counterfactual, to be 0.224. This means 77.6% are failures. If 77.6% of targets were failures at 1.0, shouldn't the mean cost be at least 0.776? Table 1 reports it as 0.176. Kindly clarify: is cost only calculated on the instances where the counterfactual is found?

Reviewer_tbh6OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes RACE, a counterfactual explainer for heterogeneous graphs, that: for each node, tries to delete every subset of relation types and return the subset that changes the prediction, and for each feasible node, restores deleted edges and keeps the minimum set of edges that flip a prediction. The paper achieves marginal improvements (0-3pp) over the baseline, CF2.

Critical strengths
  • The question is relevant: users of heterogeneous models ask which relation type a prediction depends on, which is not answered by edge-level counterfactuals
Critical weaknesses
  • The gain over baselines is marginal and within margin of error.
  • Missing related work on counterfactual explanations on heterogeneous graphs: HENCE-X, CF-HGExplainer, xPath, PaGE-Link
  • The baselines seem weak - multiple baselines report the same CSR and std on ACM and obgn-mag.
  • The relation search is only ever tested on K=2, and on Cora deleting a citation while keeping a common-neighbour can never happen because the edges are dependent on each other.
  • RACE-hier cannot be deterministic if CF2 is not deterministic and RACE falls back to CF2. Without CF2 fallback, RACE has lower CSR than baselines.
Questions for authors
  • Please address weaknesses above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.