- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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?
-
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.