Pith. sign in

REVIEW 5 major objections 4 minor 36 references

COMBINEX: A Unified Counterfactual Explainer for Graph Neural Networks via Node Feature and Structural Perturbations

T0 review · 5 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read COMBINEX is a counterfactual explainer that jointly optimizes edge and node-feature perturbations to flip a GNN's prediction with minimal changes.

desk verdict The edge channel never fires in the experiments, so the 'joint balancing' claim is unsupported; the feature-only variant is the real result, and the paper overclaims validity. read the letter →

arxiv 2502.10111 v1 pith:R6JW6Q36 submitted 2025-02-14 cs.LG

Flavio Giorgi , Fabrizio Silvestri , Gabriele Tolomei This is my paper · ORCID
classification cs.LG
keywords counterfactualexplanationsgraphneuralnetworksexplainableAInodeclassificationedgeperturbationfeature
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

COMBINEX is a counterfactual explainer for Graph Neural Networks that produces a modified graph, changed in both edges and node features, that makes the model output a desired class. The paper's central claim is that treating structural and feature perturbations as a single joint optimization, rather than as separate procedures, yields counterfactuals that are minimal, valid, and closer to the data distribution. This matters because current GNN explainers almost exclusively delete edges, and feature edits are either ignored or applied naively. The authors report that on their benchmark suite COMBINEX achieves a validity of 1.0 across datasets and architectures while keeping edge and node sparsity low, and they attribute this to the joint objective and to an edge-vector sparsification trick that also cuts runtime.

What carries the argument

Two coupled perturbation matrices drive the method: an edge perturbation vector $EP$ multiplied against the edge weights, sigmoid-activated to stay in $(0,1)$, and a node feature perturbation vector $P$ whose discrete components pass through a tanh and are clamped to feature bounds. The loss couples them through the scalar $\alpha$, which schedules how much of the budget goes to edges versus features. A second load-bearing mechanism is the edge-weight nullification theorem: for GCN and GraphConv (and ChebConv with filter size 1), setting an entry of $EP$ to zero produces exactly the same message-passing outcome as removing the corresponding edge from the adjacency matrix, so the explainer can work with the compact edge vector instead of a dense adjacency matrix.

What would settle it

Re-run the node-classification experiments on a benchmark where node labels are genuinely per-node rather than inherited from the graph-level class, and compare COMBINEX's validity and edge-sparsity to the values reported on the adapted biological datasets; a large drop would indicate that the perfect validity scores depend on the dataset adaptation. As a second check, run COMBINEX with a ChebConv oracle of filter size $K>1$ and test whether setting an edge weight to zero still yields identical predictions to removing the edge, since the appendix proves the equivalence should fail in that regime.

Watch

Extended reading notes

Core claim

COMBINEX frames counterfactual explanation as minimizing a total loss $L_{\text{total}} = \eta L_{\text{CE}} + (1-\alpha)L_E + \alpha L_X$, where $L_{\text{CE}}$ pushes the perturbed graph toward the target class, $L_E$ measures structural distance as $\sum |\sigma(EP) - 1|$ over edges, and $L_X$ combines L1 loss for discrete features with MSE for continuous features. Two differentiable perturbation matrices, an edge weight vector $EP$ and a node feature vector $P$, are optimized by gradient descent and then thresholded to produce a discrete counterfactual graph. The parameter $\alpha$, governed by a scheduling policy, trades off edge and feature changes. The paper additionally proves that nullifying an edge weight is equivalent to deleting the edge for GCN and first-order ChebConv layers, which justifies a scalable edge-vector sparsification that avoids materializing the full adjacency matrix. The central empirical claim is that this joint scheme is valid, faithful, and sparse across node and graph classification benchmarks and across three GNN architectures.

Load-bearing premise

The evaluation assumes that merging the graph-classification datasets (AIDS, Enzymes, Proteins) into single large graphs and assigning the graph label to every node yields a meaningful node-classification task; if those node labels are not semantically valid, the reported validity and fidelity numbers do not reflect real-world node classification.

Editorial extensions

If this is right

  • Counterfactual explanations for GNN node and graph classifiers can be generated with both edge deletions and feature changes in one pass, giving users more actionable what-if scenarios.
  • The equivalence theorem implies that edge-vector sparsification scales to graphs with tens of thousands of edges without materializing modified adjacency matrices, so explanation runtime and memory need not grow with the dense adjacency.
  • The $\alpha$ scheduling policies give practitioners a single knob to choose between editing topology and editing features, which the experiments suggest should be tuned per dataset and oracle.
  • High reported validity across architectures suggests that letting feature perturbations take part in the search substantially enlarges the set of reachable counterfactuals, potentially reducing the need for large structural changes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's node-classification adaptation of graph-classification datasets, assigning the graph label to every node, is a testable choice: if the model is mostly predicting a near-constant label, valid counterfactuals may be trivial feature tweaks; a cleaner test would compare on datasets with genuinely node-level semantics.
  • Because the reported edge sparsity is often 0 for COMBINEX, the joint optimization may in practice collapse to feature-only editing on many benchmarks; the claimed benefit of balancing could be probed by measuring how often the final counterfactual actually changes at least one edge when $\alpha$ permits it.
  • The equivalence theorem is stated for GCN and first-order ChebConv; the paper concedes it fails for higher-order Chebyshev filters, so the runtime advantage may not transfer to higher-order spectral architectures without additional care.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 4 minor

Summary. COMBINEX proposes a counterfactual explainer for graph neural networks that jointly optimizes node-feature and edge perturbations through a weighted loss with a scheduling parameter alpha. The method is evaluated on node and graph classification tasks across many datasets and three GNN architectures, with results reported in a main table and a large appendix. The paper also contributes an edge-weight vector sparsification technique intended to scale edge edits to larger graphs, with proofs of equivalence to adjacency-matrix edge removal for GCNConv, ChebConv (K=1), and GraphConv.

Significance. If the joint optimization of feature and structural perturbations worked as claimed, the paper would address a real gap in the graph counterfactual explanation literature, and the edge-weight sparsification trick could be a useful efficiency contribution. The paper also provides a complexity analysis, handles continuous and discrete features separately, and releases a GitHub repository. However, the experimental evidence does not support the central joint-balancing claim: the structural channel is almost never active, the main-text validity claim is contradicted by the appendix, the fidelity metric is used in ways that are undefined or negative, and the adaptation of graph-classification datasets to node classification is not justified. These problems undermine the main conclusions as presented.

major comments (5)
  1. [Section 5.1 and Appendix A.6/A.7] The main text states that COMBINEX 'maintains a perfect score of 1 across all datasets and architectures,' but the appendix reports many lower validity values, for example COMBINEXdef on PubMed with GCNConv is 0.650 (Table 11), on Wiki with GraphConv is 0.130 (Table 18), and on Proteins with GCNConv is 0.390 (Table 22). This overgeneralization misrepresents the experimental results and should be corrected or heavily qualified.
  2. [Algorithm 2 (line 3) and Tables 3, 5-7] The edge loss is defined as L_E = sum(|sigma(EP)-1|), which is minimized when the sigmoid of every edge weight equals 1, i.e., when no edge is removed; moreover, Algorithm 1 initializes EP to 1, and the examples in the paper never cross the 0.5 threshold to delete an edge. The empirical result is that edge sparsity is 0.000 in nearly every reported COMBINEX row, and COMBINEXfeat, which omits the edge channel entirely, achieves the same validity and fidelity as COMBINEXdef. Consequently, the central claim of jointly balancing edge and feature perturbations is not supported by the experiments.
  3. [Section 5, Evaluation Measures and Tables 3, 5-7] The fidelity metric is not defined precisely in the paper, yet the tables report negative values (e.g., -0.944 for Random Edges on AIDS with ChebConv in Table 5, -1.000 for CFF in Table 3) and 'n.d.' for many baselines. A fidelity score that is not bounded and can be negative cannot support the paper's qualitative claims that COMBINEX 'ranks among the best-performing methods in fidelity.' The metric needs a clear definition and a justification of its range and interpretation.
  4. [Appendix A.5.4 and Tables 20-22] The biological datasets (AIDS, Enzymes, Proteins) are originally graph-classification datasets, and the paper adapts them to node classification by assigning the graph-level label to every node. This adaptation is mentioned in one sentence but never described or validated. If the node labels are not semantically meaningful for node classification, the validity and fidelity numbers reported for these datasets do not reflect a real node-classification task and should not be used as evidence of generalizability.
  5. [Theorem 6.1 and Section 6] The proof of the claimed equivalence between edge-weight nullification and adjacency-matrix edge removal in GCNConv is not correct as stated. Setting an edge weight to zero also changes the degree matrix used in the renormalized adjacency (since the degree is computed from the weighted adjacency), but the proof keeps D fixed and simply asserts that the resulting normalized adjacency matrices are equal. As a result, the scalability argument built on this equivalence is not formally established, and the statement needs to be corrected or restricted to unnormalized message passing.
minor comments (4)
  1. [Algorithm 1, lines 12-13] Both update rules read 'P_{t+1}^x <- P_t^x - gamma grad_{P,EP}(L)' and 'EP_{t+1}^x <- EP_t^x - gamma grad_{P,EP}(L)', using a combined gradient and an undefined x subscript; the EP update should use the gradient with respect to EP only, and the x subscript should be removed or defined.
  2. [Equation (2)] The constraint is written as 'f(g(A,X)) != f(g(\tilde A,\tilde X)) = y_t', which is logically ambiguous; it should be stated as 'f(g(A,X)) != y_t and f(g(\tilde A,\tilde X)) = y_t'.
  3. [Table 3 caption] The abbreviation 'n.d.' is used throughout the tables but is never defined in the text; the authors should state what it stands for (presumably 'not defined' or 'not determinable') and explain when it applies.
  4. [Section 5.1] The phrase 'regardless for the alpha scheduling policy' should be 'regardless of the alpha scheduling policy'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the joint feature/edge loss is an independent formulation, and the CF-GNNExplainer self-citation is not load-bearing.

full rationale

COMBINEX's loss (Eq. 3) is a direct, explicit translation of the optimization problem (Eq. 2): minimize topology and feature distances subject to a prediction flip. No fitted parameter is later renamed as a prediction, and no term in the loss is defined in terms of the metric it is used to support. The only overlap with the authors' prior work is the adoption of Lucic et al.'s tanh/sigmoid differentiable perturbation scheme (Section 4.1), which is an implementation choice rather than a load-bearing uniqueness or optimality argument; the added feature-loss term and joint alpha-weighted objective are independent contributions. The reported edge sparsity of 0.000 is consistent with L_E = sum |sigma(EP)-1|, which by design penalizes edge removal, but that is a design/objective property, not a circular derivation: the central 'balanced joint perturbation' claim is weakened empirically, not by construction. The validity metric also deserves a caveat: Algorithm 1 line 14 only stores candidates with y_new = y_t, so validity is measured on prediction-changing candidates; nevertheless, a score of 1.000 across all test instances still records that a valid candidate was found for every instance, so it is not a pure tautology. Overall, no derivation step reduces to its own inputs.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The method relies on standard differentiable GNN assumptions, the equivalence theorem for edge weight sparsification, and a questionable dataset adaptation. No new physical or conceptual entities are introduced.

free parameters (1)
  • alpha (trade-off weight) = varies by policy; default value not specified
    Controls the balance between edge and feature losses. The paper evaluates six scheduling policies and reports all; performance depends heavily on this choice (Section 5.2).
assumptions (3)
  • domain assumption The oracle GNN is differentiable with respect to node features and edge weights, allowing gradient-based optimization through the continuous relaxations.
    Algorithm 1 backpropagates through g(G(X_p, E_p)); this requires differentiable message passing.
  • domain assumption Edge weight nullification is equivalent to edge removal in GCN and GraphConv with the same normalization.
    Theorems 6.1 and A.2 assume the degree matrix is recomputed from the modified edge weights; this is not guaranteed in all GNN implementations.
  • ad hoc to paper Graph-level labels can be used as node-level labels when adapting graph-classification datasets for node classification.
    Section A.5.4 states the adaptation but provides no justification; the resulting node task is not standard.

how reviews work

0 comments
Cite this review

Pith. "Pith review of COMBINEX: A Unified Counterfactual Explainer for Graph Neural Networks via Node Feature and Structural Perturbations." pith.science (2026). https://pith.science/paper/R6JW6Q36

@misc{pith2026250210111,
  author       = {Pith},
  title        = {Pith review of: COMBINEX: A Unified Counterfactual Explainer for Graph Neural Networks via Node Feature and Structural Perturbations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R6JW6Q36}},
  note         = {Machine review of arXiv:2502.10111}
}
read the original abstract

Counterfactual explanations have emerged as a powerful tool to unveil the opaque decision-making processes of graph neural networks (GNNs). However, existing techniques primarily focus on edge modifications, often overlooking the crucial role of node feature perturbations in shaping model predictions. To address this limitation, we propose COMBINEX, a novel GNN explainer that generates counterfactual explanations for both node and graph classification tasks. Unlike prior methods, which treat structural and feature-based changes independently, COMBINEX optimally balances modifications to edges and node features by jointly optimizing these perturbations. This unified approach ensures minimal yet effective changes required to flip a model's prediction, resulting in realistic and interpretable counterfactuals. Additionally, COMBINEX seamlessly handles both continuous and discrete node features, enhancing its versatility across diverse datasets and GNN architectures. Extensive experiments on real-world datasets and various GNN architectures demonstrate the effectiveness and robustness of our approach over existing baselines.

Figures

Figures reproduced from arXiv: 2502.10111 by the authors.

Figure 1
Figure 1. Comparison of two approaches for generating coun [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 27 canonical work pages

  1. [1]

    Plamen P Angelov, Eduardo A Soares, Richard Jiang, Nicholas I Arnold, and Peter M Atkinson. 2021. Explainable artificial intelligence: an analytical review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 11, 5 (2021), e1424

    2021

  2. [2]

    Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. 2021. Robust counterfactual explanations on graph neural networks. Advances in Neural Information Processing Systems 34 (2021), 5644– 5655

    work page 2021

  3. [3]

    Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, S V N Vishwanathan, Alexander J Smola, and Hans-Peter Kriegel. 2005. Protein function prediction via graph kernels. Bioinformatics 21, suppl_1 (2005), i47–i56

    work page 2005

  4. [4]

    Jialin Chen, Shirley Wu, Abhijit Gupta, and Rex Ying. 2023. D4explainer: In- distribution gnn explanations via discrete denoising diffusion. arXiv preprint arXiv:2310.19321 (2023)

    work page Pith review arXiv 2023

  5. [5]

    Ziheng Chen, Fabrizio Silvestri, Jia Wang, He Zhu, Hongshik Ahn, and Gabriele Tolomei. 2022. Relax: Reinforcement learning agent explainer for arbitrary predictive models. In Proceedings of the 31st ACM international conference on information & knowledge management. 252–261

    work page 2022

  6. [6]

    Paul D Dobson and Andrew J Doig. 2003. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology 330, 4 (2003), 771–783

    2003

  7. [7]

    Filip Karlo Došilović, Mario Brčić, and Nikica Hlupić. 2018. Explainable artificial intelligence: A survey. In2018 41st International convention on information and communication technology, electronics and microelectronics (MIPRO). IEEE, 0210–0215

    work page 2018

  8. [8]

    Yuan Gao, Junfeng Fang, Yongduo Sui, Yangyang Li, Xiang Wang, Huamin Feng, and Yongdong Zhang. 2024. Graph Anomaly Detection with Bi-level Optimization. In Proceedings of the ACM Web Conference 2024 (Singapore, Sin- gapore) (WWW ’24). Association for Computing Machinery, New York, NY, USA, 4383–4394. doi:10.1145/3589334.3645673

    work page arXiv 2024

Show all 36 references
  1. [9]

    Riccardo Guidotti. 2022. Counterfactual explanations and how to find them: literature review and benchmarking. Data Mining and Knowledge Discovery (2022), 1–55

    2022

  2. [10]

    Riccardo Guidotti, Anna Monreale, Fosca Giannotti, Dino Pedreschi, Salvatore Ruggieri, and Franco Turini. 2019. Factual and counterfactual explanations for black box decision making. IEEE Intelligent Systems 34, 6 (2019), 14–23

    2019

  3. [11]

    Mingguo He, Zhewei Wei, and Ji-Rong Wen. 2022. Convolutional neural net- works on graphs with chebyshev approximation, revisited. Advances in neural information processing systems 35 (2022), 7264–7276

    2022

  4. [12]

    National Cancer Institute. 2004. AIDS Antiviral Screen Data. https://wiki.nci. nih.gov/display/ncidtpdata/aids+antiviral+screen+data Accessed: 2025-01-10

    2004

  5. [13]

    Hyunju Kang, Geonhee Han, and Hogun Park. [n. d.]. UNR-Explainer: Counter- factual Explanations for Unsupervised Node Representation Learning Models. In The Twelfth International Conference on Learning Representations

  6. [14]

    Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)

    2016 arXiv

  7. [15]

    Jure Leskovec and Rok Sosič. 2016. SNAP: A General-Purpose Network Anal- ysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology (TIST) 8, 1 (2016), 1

    2016

  8. [16]

    Yifei Liu, Chao Chen, Yazheng Liu, Xi Zhang, and Sihong Xie. 2021. Multi-objective explanations of GNN predictions. In 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 409–418

    2021

  9. [17]

    Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. 2022. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics. PMLR, 4499–4511

    2022

  10. [18]

    Scott Lundberg. 2017. A unified approach to interpreting model predictions. arXiv preprint arXiv:1705.07874 (2017)

    2017 arXiv

  11. [19]

    Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. 2022. Clear: Generative counterfactual explanations on graphs. Advances in neural information processing systems 35 (2022), 25895–25907

    2022

  12. [20]

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33. 4602–4609

    2019

  13. [21]

    European Parliament. 2023. Artificial Intelligence Act: Deal on Comprehensive Rules for Trustworthy AI

    2023

  14. [22]

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang

  15. [23]

    Mario Alfonso Prado-Romero, Bardh Prenkaj, Giovanni Stilo, and Fosca Giannotti

  16. [24]

    Why should i trust you?

    Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016. " Why should i trust you?" Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 1135–1144

    2016

  17. [25]

    Kaspar Riesen and Horst Bunke. 2008. IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning. InStructural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshop, SSPR & SPR 2008 (Lecture Notes in Computer Science, Vol...

    2008 doi

  18. [26]

    Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. 2004. BRENDA, the enzyme database: updates and major new developments.Nucleic Acids Research 32, suppl_1 (2004), D431–D433

    2004

  19. [27]

    Ilia Stepin, Jose M Alonso, Alejandro Catala, and Martín Pereira-Fariña. 2021. A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access 9 (2021), 11974–12001

    2021

  20. [28]

    Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. 2022. Learning and evaluating graph neural network explana- tions based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022. 1018–1027

    2022

  21. [29]

    Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas. 2017. Interpretable predictions of tree-based ensembles via actionable feature tweak- ing. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 465–474

    2017

  22. [30]

    Zheng, Jacqueline A

    Felix Wong, Erica J. Zheng, Jacqueline A. Valeri, Nina M. Donghia, Melis N. Anahtar, Satotaka Omori, Alicia Li, Andres Cubillos-Ruiz, Aarti Krishnan, Wengong Jin, Abigail L. Manson, Jens Friedrichs, Ralf Helbig, Behnoush Ha- jian, Dawid K. Fiejtek, Florence F. Wagner, Holly H....

    2023

  23. [31]

    Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Xiaojie Guo. 2022. Graph neural networks: foundation, frontiers and applications. InProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 4840–4841

    2022

  24. [32]

    Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Sourav S Bhowmick, and Juncheng Liu. 2023. PANE: scalable and effective attributed network embedding. The VLDB Journal 32, 6 (2023), 1237–1262

    2023

  25. [33]

    Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semi- supervised learning with graph embeddings. In International conference on machine learning. PMLR, 40–48

    2016

  26. [34]

    Wayne W Zachary. 1977. An information flow model for conflict and fission in small groups. Journal of anthropological research 33, 4 (1977), 452–473. A Appendix A.1 Edge Nullification Theorem for ChebConv Theorem A.1. In a Chebyshev Convolutional Network (Cheb- Conv), setting ...

    1977

  27. [2020]

    arXiv preprint arXiv:2002.05287 (2020)

    Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 (2020)

    2020 arXiv

  28. [2023]

    A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges. Comput. Surveys (Sept. 2023). doi:10.1145/ 3618105

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.