pith. sign in

arxiv: 2605.17285 · v1 · pith:N3C45PCPnew · submitted 2026-05-17 · 💻 cs.LG · cs.AI

UNR-Explainer: Counterfactual Explanations for Unsupervised Node Representation Learning Models

Hyunju Kang , Geonhee Han , Hogun Park This is my paper

Pith reviewed 2026-05-20 13:37 UTC · model grok-4.3

classification 💻 cs.LG cs.AI
keywords counterfactual explanationsnode representation learningunsupervised learninggraph neural networksMonte Carlo tree searchk-nearest neighborsexplainability
0
0 comments X

The pith

A search method generates counterfactual explanations for unsupervised node embeddings by finding subgraphs that shift a node's nearest neighbors in the learned space.

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

The paper develops a technique to create explanations for graph models that learn node features without any labeled data. It does this by pinpointing subgraphs around a given node that, if altered, would change which nodes end up as its closest matches in the model's internal representation. Readers might value this because it makes sense of otherwise opaque models used for grouping nodes or predicting connections in networks. The technique relies on a search strategy to efficiently explore possible subgraphs and select the most impactful ones.

Core claim

We identify the most important subgraphs that cause a significant change in the k-nearest neighbors of a node of interest in the learned embedding space upon perturbation. The k-nearest neighbor-based CF explanation method provides simple, yet pivotal, information for understanding unsupervised downstream tasks, such as top-k link prediction and clustering. We introduce UNR-Explainer for generating expressive CF explanations for Unsupervised Node Representation learning methods based on a Monte Carlo Tree Search.

What carries the argument

UNR-Explainer, a Monte Carlo Tree Search procedure that locates subgraphs whose perturbation produces large shifts in the k-nearest neighbors of a target node inside the embedding space.

If this is right

  • It supplies direct information for interpreting unsupervised tasks such as top-k link prediction and clustering.
  • It shows better results than existing approaches on multiple datasets when applied to unsupervised GraphSAGE and DGI.
  • It works by searching for the subgraphs that most strongly influence a node's position relative to its neighbors in the embedding space.
  • It yields compact explanations that highlight only the graph elements responsible for the observed neighbor shifts.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same neighbor-shift criterion could be tested on other unsupervised embedding methods that rely on proximity in latent space.
  • Combining the subgraph search with downstream task metrics might produce explanations that are directly tied to prediction accuracy.
  • Scaling the search to very large graphs would require checking whether the Monte Carlo procedure remains efficient.

Load-bearing premise

A change in the k-nearest neighbors within the embedding space counts as a meaningful and sufficient counterfactual explanation for unsupervised downstream tasks such as top-k link prediction and clustering.

What would settle it

An experiment that shows the identified subgraphs produce no measurable change in nearest-neighbor sets or no improvement in interpreting clustering and link-prediction outcomes would disprove the method's explanatory value.

Figures

Figures reproduced from arXiv: 2605.17285 by Geonhee Han, Hogun Park, Hyunju Kang.

Figure 1
Figure 1. Figure 1: Scenarios for counterfactual (CF) reason [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Case study on NIPS datasets. Our explanatory graphs reveal the important con￾nections that impact the top-k neighboring nodes in embedding space, particularly for here case study on a social network. We apply our method on a co-author network dataset of the NIPS con￾ferences (Hamner, 2017). Upon applying Graph￾SAGE in unsupervised settings, we extract signifi￾8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The study of parameter sensitivity for the number of the nearest neighbors as k and the restart probability prestart. We evaluate the robustness of our model relating to crucial hyperparameters, such as the top-k number of neighbors k and the restart probability prestart, using the GraphSAGE model on the Cora dataset. The results are shown in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Overall procedure of UNR-Explainer to explain the unsupervised node representation [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The examples of obtained subgraphs by different models on synthetic datasets. [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
read the original abstract

Node representation learning, such as Graph Neural Networks (GNNs), has emerged as a pivotal method in machine learning. The demand for reliable explanation generation surges, yet unsupervised models remain underexplored. To bridge this gap, we introduce a method for generating counterfactual (CF) explanations in unsupervised node representation learning. We identify the most important subgraphs that cause a significant change in the k-nearest neighbors of a node of interest in the learned embedding space upon perturbation. The k-nearest neighbor-based CF explanation method provides simple, yet pivotal, information for understanding unsupervised downstream tasks, such as top-k link prediction and clustering. Consequently, we introduce UNR-Explainer for generating expressive CF explanations for Unsupervised Node Representation learning methods based on a Monte Carlo Tree Search (MCTS). The proposed method demonstrates superior performance on diverse datasets for unsupervised GraphSAGE and DGI.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces UNR-Explainer, a Monte Carlo Tree Search (MCTS) based approach for generating counterfactual explanations in unsupervised node representation learning. It identifies the most important subgraphs whose perturbation produces a significant shift in the k-nearest neighbors of a target node within the learned embedding space of models such as unsupervised GraphSAGE and DGI. The method is positioned as supplying pivotal information for interpreting downstream unsupervised tasks including top-k link prediction and clustering, with a claim of superior performance across diverse datasets.

Significance. If the k-NN perturbation criterion can be shown to correlate with actual changes in unsupervised task performance, the work would address an underexplored area of explainability for unsupervised GNNs. The MCTS formulation for subgraph search offers a concrete algorithmic contribution that could be extended to other embedding-based models.

major comments (2)
  1. [Abstract] Abstract: the central claim that the method 'demonstrates superior performance on diverse datasets for unsupervised GraphSAGE and DGI' is unsupported by any reported metrics, baselines, statistical tests, dataset specifications, or experimental details, rendering the empirical contribution unevaluable.
  2. [Abstract] Abstract: the definition of a counterfactual explanation as a subgraph perturbation that alters k-nearest neighbors in embedding space is asserted to provide 'pivotal information' for unsupervised downstream tasks, yet no mapping, correlation, or ablation is supplied showing that such k-NN shifts measurably affect or explain performance on top-k link prediction or clustering.
minor comments (1)
  1. The abstract refers to 'diverse datasets' without naming them or describing their characteristics; this information should appear explicitly in the experimental section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address the two major comments on the abstract below. We agree that the abstract requires strengthening to better support our claims and will revise it accordingly while preserving the core contributions of the MCTS-based approach.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the method 'demonstrates superior performance on diverse datasets for unsupervised GraphSAGE and DGI' is unsupported by any reported metrics, baselines, statistical tests, dataset specifications, or experimental details, rendering the empirical contribution unevaluable.

    Authors: We acknowledge that the abstract is necessarily concise and omits specific quantitative details. The full manuscript reports these elements in the Experiments section, including comparisons against baselines, performance metrics on multiple datasets, and results for unsupervised GraphSAGE and DGI. To make the claim evaluable directly from the abstract, we will revise it to include key quantitative highlights and explicit references to the experimental section and tables. revision: yes

  2. Referee: [Abstract] Abstract: the definition of a counterfactual explanation as a subgraph perturbation that alters k-nearest neighbors in embedding space is asserted to provide 'pivotal information' for unsupervised downstream tasks, yet no mapping, correlation, or ablation is supplied showing that such k-NN shifts measurably affect or explain performance on top-k link prediction or clustering.

    Authors: The manuscript motivates the k-NN perturbation criterion by its direct relevance to neighborhood-based unsupervised tasks. Supporting qualitative evidence and case studies appear in the experiments. We agree that an explicit quantitative mapping, such as an ablation measuring downstream task performance changes induced by the identified subgraphs, would strengthen the justification. We will add this analysis in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: method relies on external MCTS search and empirical validation

full rationale

The paper proposes UNR-Explainer, which uses Monte Carlo Tree Search to find subgraphs perturbing k-NN structure in an already-learned embedding. No equations, parameter-fitting loops, or self-referential definitions appear. The claim that such perturbations supply explanations for unsupervised tasks is presented as a modeling choice supported by downstream performance numbers on standard datasets, not derived from or equivalent to the inputs by construction. Self-citations are absent from the provided text, and the core construction does not reduce to renaming or tautological re-use of the target quantity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters or invented entities; the central approach rests on the domain assumption that k-NN shifts provide valid explanations.

axioms (1)
  • domain assumption k-nearest neighbors in the learned embedding space reflect meaningful node similarities for unsupervised tasks
    Invoked when defining what constitutes a significant change upon subgraph perturbation.

pith-pipeline@v0.9.0 · 5684 in / 1208 out tokens · 53879 ms · 2026-05-20T13:37:13.845180+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

68 extracted references · 68 canonical work pages

  1. [1]

    Proceedings of the International World Wide Web Conference , pages=

    PaGE-Link: Path-based graph neural network explanation for heterogeneous link prediction , author=. Proceedings of the International World Wide Web Conference , pages=

    work page

  2. [2]

    Applied Stochastic Models in Business and Industry , volume=

    Analysis of regression in game theory approach , author=. Applied Stochastic Models in Business and Industry , volume=. 2001 , publisher=

    work page 2001

  3. [3]

    NIPS Papers , url=

    Ben Hamner , year=. NIPS Papers , url=. doi:10.34740/DVS/9097 , publisher=

    work page doi:10.34740/dvs/9097

  4. [4]

    Neural Networks , volume=

    Generating post-hoc explanations for Skip-gram-based node embeddings by identifying important nodes with bridgeness , author=. Neural Networks , volume=. 2023 , publisher=

    work page 2023

  5. [5]

    Machine learning , volume=

    Simple statistical gradient-following algorithms for connectionist reinforcement learning , author=. Machine learning , volume=. 1992 , publisher=

    work page 1992

  6. [6]

    Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    Automatic multimedia cross-modal correlation discovery , author=. Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    work page

  7. [7]

    Proceedings of the Neural Information Processing Systems , year=

    Gnnexplainer: Generating explanations for graph neural networks , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  8. [8]

    Proceedings of the Neural Information Processing Systems , year=

    Distributed representations of words and phrases and their compositionality , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  9. [9]

    Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    DeepWalk: Online Learning of Social Representations , author=. Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    work page

  10. [10]

    Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    node2vec: Scalable feature learning for networks , author=. Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    work page

  11. [11]

    , author=

    Evolving network representation learning based on random walks. , author=. Appl Netw Sci 5 , pages=

    work page

  12. [12]

    Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    XGNN: Towards Model-Level Explanations of Graph Neural Networks , author=. Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    work page

  13. [13]

    IEEE Access , volume=

    Providing post-hoc explanation for node representation learning models through inductive conformal predictions , author=. IEEE Access , volume=. 2022 , publisher=

    work page 2022

  14. [14]

    Proceedings of the International World Wide Web Conference , year=

    Line: Large-scale information network embedding , author=. Proceedings of the International World Wide Web Conference , year=

    work page

  15. [15]

    Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    struc2vec: Learning node representations from structural identity , author=. Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    work page

  16. [16]

    Proceedings of the International Conference on Learning Representations , year=

    Keyulu Xu and Weihua Hu and Jure Leskovec and Stefanie Jegelka , title =. Proceedings of the International Conference on Learning Representations , year=

    work page

  17. [17]

    Proceedings of the International World Wide Web Conference , year=

    VERSE: Versatile Graph Embeddings from Similarity Measures , author=. Proceedings of the International World Wide Web Conference , year=

    work page

  18. [18]

    Proceedings of the International Conference on Machine Learning , year=

    On explainability of graph neural networks via subgraph explorations , author=. Proceedings of the International Conference on Machine Learning , year=

    work page

  19. [19]

    Proceedings of the International Conference on Learning Representations , year=

    Semi-Supervised Classification with Graph Convolutional Networks , author=. Proceedings of the International Conference on Learning Representations , year=

    work page

  20. [20]

    IEEE Transactions on Pattern Analysis and Machine Intelligence , year=

    Explainability in graph neural networks: A taxonomic survey , author=. IEEE Transactions on Pattern Analysis and Machine Intelligence , year=

    work page

  21. [21]

    Information Fusion , volume=

    Machine learning for integrating data in biology and medicine: Principles, practice, and opportunities , author=. Information Fusion , volume=

    work page

  22. [22]

    Frontiers in genetics , volume=

    To embed or not: network embedding as a paradigm in computational biology , author=. Frontiers in genetics , volume=. 2019 , publisher=

    work page 2019

  23. [23]

    Nature , volume=

    Mastering the game of go without human knowledge , author=. Nature , volume=. 2017 , publisher=

    work page 2017

  24. [24]

    2018 , publisher=

    Reinforcement learning: An introduction , author=. 2018 , publisher=

    work page 2018

  25. [25]

    Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    On interpretation of network embedding via taxonomy induction , author=. Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining , year=

    work page

  26. [26]

    arXiv preprint arXiv:2006.11371 , year=

    Opportunities and challenges in explainable artificial intelligence (xai): A survey , author=. arXiv preprint arXiv:2006.11371 , year=

    work page arXiv 2006

  27. [27]

    IEEE Transactions on Pattern Analysis and Machine Intelligence , year=

    Higher-order explanations of graph neural networks via relevant walks , author=. IEEE Transactions on Pattern Analysis and Machine Intelligence , year=

    work page

  28. [28]

    arXiv preprint arXiv:2010.05788 , year=

    Pgm-explainer: Probabilistic graphical model explanations for graph neural networks , author=. arXiv preprint arXiv:2010.05788 , year=

    work page arXiv 2010

  29. [29]

    Proceedings of the Neural Information Processing Systems , volume=

    Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS) , author=. Proceedings of the Neural Information Processing Systems , volume=

    work page

  30. [30]

    Proceedings of the Neural Information Processing Systems , year=

    Inductive representation learning on large graphs , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  31. [31]

    Machine learning , volume=

    Finite-time analysis of the multiarmed bandit problem , author=. Machine learning , volume=. 2002 , publisher=

    work page 2002

  32. [32]

    Parameterized Explainer for Graph Neural Network , pages =

    Luo, Dongsheng and Cheng, Wei and Xu, Dongkuan and Yu, Wenchao and Zong, Bo and Chen, Haifeng and Zhang, Xiang , booktitle=. Parameterized Explainer for Graph Neural Network , pages =

    work page

  33. [33]

    Proceedings of the Neural Information Processing Systems , volume=

    Reinforcement Learning Enhanced Explainer for Graph Neural Networks , author=. Proceedings of the Neural Information Processing Systems , volume=

    work page

  34. [34]

    , booktitle=

    Fey, Matthias and Lenssen, Jan E. , booktitle=. Fast Graph Representation Learning with

    work page

  35. [35]

    Proceedings of the xxAI in Conjunction with International Conference on Machine Learning , year=

    Explaining the predictions of unsupervised learning models , author=. Proceedings of the xxAI in Conjunction with International Conference on Machine Learning , year=

    work page

  36. [36]

    Proceedings of the International Conference on Machine Learning , year=

    Label-free explainability for unsupervised models , author=. Proceedings of the International Conference on Machine Learning , year=

    work page

  37. [37]

    Proceedings of the Neural Information Processing Systems , year=

    Task-agnostic graph explanations , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  38. [38]

    & Hines, K

    Counterfactual explanations for machine learning: A review , author=. arXiv preprint arXiv:2010.10596 , year=

    work page arXiv 2010

  39. [39]

    Proceedings of the International Conference on Machine Learning , year=

    Meaningfully debugging model mistakes using conceptual counterfactual explanations , author=. Proceedings of the International Conference on Machine Learning , year=

    work page

  40. [40]

    Proceedings of the The Special Interest Group on Computer–Human Interaction , year=

    'It's Reducing a Human Being to a Percentage' Perceptions of Justice in Algorithmic Decisions , author=. Proceedings of the The Special Interest Group on Computer–Human Interaction , year=

    work page

  41. [41]

    Proceedings of the International Conference on Learning Representations , year=

    Deep graph infomax , author=. Proceedings of the International Conference on Learning Representations , year=

    work page

  42. [42]

    Proceedings of the Neural Information Processing Systems , year=

    Infogcl: Information-aware graph contrastive learning , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  43. [43]

    Proceedings of the Neural Information Processing Systems , year=

    Towards multi-grained explainability for graph neural networks , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  44. [44]

    Proceedings of the International Conference on Artificial Intelligence and Statistics , year=

    Cf-gnnexplainer: Counterfactual explanations for graph neural networks , author=. Proceedings of the International Conference on Artificial Intelligence and Statistics , year=

    work page

  45. [45]

    Proceedings of the International Conference on Machine Learning , year=

    Generative causal explanations for graph neural networks , author=. Proceedings of the International Conference on Machine Learning , year=

    work page

  46. [46]

    Proceedings of the Neural Information Processing Systems , year=

    Robust counterfactual explanations on graph neural networks , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  47. [47]

    Proceedings of the International World Wide Web Conference , year=

    Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning , author=. Proceedings of the International World Wide Web Conference , year=

    work page

  48. [48]

    Proceedings of the Neural Information Processing Systems , year=

    CLEAR: Generative Counterfactual Explanations on Graphs , author=. Proceedings of the Neural Information Processing Systems , year=

    work page

  49. [49]

    Proceedings of the IEEE International Conference on Data Mining , year=

    Reinforcement Learning Based Monte Carlo Tree Search for Temporal Path Discovery , author=. Proceedings of the IEEE International Conference on Data Mining , year=

    work page

  50. [50]

    arXiv preprint arXiv:2101.04167 , year=

    First-order prmcts2blem solving through neural mcts based reinforcement learning , author=. arXiv preprint arXiv:2101.04167 , year=

    work page arXiv

  51. [51]

    Artificial Intelligence Review , pages=

    Monte Carlo tree search: A review of recent modifications and applications , author=. Artificial Intelligence Review , pages=. 2022 , publisher=

    work page 2022

  52. [52]

    Journal of Machine Learning Research , year =

    Meng Liu and Youzhi Luo and Limei Wang and Yaochen Xie and Hao Yuan and Shurui Gui and Haiyang Yu and Zhao Xu and Jingtun Zhang and Yi Liu and Keqiang Yan and Haoran Liu and Cong Fu and Bora M Oztekin and Xuan Zhang and Shuiwang Ji , title =. Journal of Machine Learning Research , year =

    work page

  53. [53]

    Journal of Machine Learning Research , year =

    Laurens van der Maaten and Geoffrey Hinton , title =. Journal of Machine Learning Research , year =

    work page

  54. [54]

    Information Systems , volume=

    A split--merge clustering algorithm based on the k-nearest neighbor graph , author=. Information Systems , volume=. 2023 , publisher=

    work page 2023

  55. [55]

    Proceedings of the Association for the Advancement of Artificial Intelligence , volume=

    Lunar: Unifying local outlier detection methods via graph neural networks , author=. Proceedings of the Association for the Advancement of Artificial Intelligence , volume=

    work page

  56. [56]

    Proceedings of the The Conference on Information and Knowledge Management , pages=

    Off the beaten path: Let's replace term-based retrieval with k-nn search , author=. Proceedings of the The Conference on Information and Knowledge Management , pages=

    work page

  57. [57]

    Proceedings of the ACM International Conference on Web Search and Data Mining , pages=

    Global Counterfactual Explainer for Graph Neural Networks , author=. Proceedings of the ACM International Conference on Web Search and Data Mining , pages=

    work page

  58. [58]

    Langley , title =

    P. Langley , title =. Proceedings of the 17th International Conference on Machine Learning (ICML 2000) , address =. 2000 , pages =

    work page 2000

  59. [59]

    T. M. Mitchell. The Need for Biases in Learning Generalizations. 1980

    work page 1980

  60. [60]

    M. J. Kearns , title =

    work page

  61. [61]

    Machine Learning: An Artificial Intelligence Approach, Vol. I. 1983

    work page 1983

  62. [62]

    R. O. Duda and P. E. Hart and D. G. Stork. Pattern Classification. 2000

    work page 2000

  63. [63]

    Suppressed for Anonymity , author=

    work page

  64. [64]

    Newell and P

    A. Newell and P. S. Rosenbloom. Mechanisms of Skill Acquisition and the Law of Practice. Cognitive Skills and Their Acquisition. 1981

    work page 1981

  65. [65]

    A. L. Samuel. Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development. 1959

    work page 1959

  66. [66]

    Scaling Learning Algorithms Towards

    Bengio, Yoshua and LeCun, Yann , booktitle =. Scaling Learning Algorithms Towards

    work page

  67. [67]

    and Osindero, Simon and Teh, Yee Whye , journal =

    Hinton, Geoffrey E. and Osindero, Simon and Teh, Yee Whye , journal =. A Fast Learning Algorithm for Deep Belief Nets , volume =

    work page

  68. [68]

    2016 , publisher=

    Deep learning , author=. 2016 , publisher=

    work page 2016