Research map / Graph learning / Graph self-supervised learning
UNR-Explainer: Counterfactual Explanations for Unsupervised Node Representation Learning Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UNR-Explainer, an MCTS-based method with a restart-based selection policy that finds sparse counterfactual subgraphs explaining top-k nearest-neighbor changes in unsupervised node embeddings (GraphSAGE, DGI).
Problem
Explaining unsupervised node representation models lacks counterfactual explanations because there are no class labels or decision boundaries; the paper targets counterfactual explanations for changes in a node's top-k nearest neighbors in embedding space, which matter for downstream link prediction
Approach
Defines counterfactual "Importance" as the fraction of a node's top-k embedding neighbors changed when a candidate subgraph's edges are removed, and searches for minimal, high-Importance subgraphs with MCTS augmented by a random-walk-with-restart selection policy that returns to the target node.
Key results
- On Cora, UNR-Explainer reaches Validity 0.911 and Importance 0.960 vs. best baseline Validity 0.327 and Importance 0.614 (RW-G w/ Restart).
- On Tree-Cycles and BA-Shapes, UNR-Explainer achieves Importance 1.000, the highest among baselines, with recall 0.324 and 0.288.
- On Cora clustering, UNR-Explainer reduces homogeneity to 0.315 from 0.866 (delta 0.551), the largest drop among compared methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UNR-Explainer counterfactual subgraphs instead of baseline explanations | Unsupervised GraphSAGE explanations · Cora, CiteSeer, and PubMed | Importance: 0.544 / 0.643 / 0.631 (RW-G) -> 0.960 / 0.910 / 0.903 | Helped |
| Use UNR-Explainer counterfactual subgraphs instead of baseline explanations | Unsupervised GraphSAGE/DGI explanations · Cora, CiteSeer, and PubMed | Validity: 0.265 / 0.393 / 0.478 (RW-G) -> 0.911 / 0.778 / 0.847 | Helped |
| Use UNR-Explainer explanations rather than the strongest recall baseline | Unsupervised GraphSAGE explanations · Tree-Grids | Recall: 0.360 -> 0.519 | Helped |
| Use UNR-Explainer explanations rather than 1hop-3N | Unsupervised GraphSAGE explanations · BA-Shapes | Precision: 0.943 -> 0.923 | Hurt |
| Use UNR-Explainer explanations rather than 1hop-3N | Unsupervised GraphSAGE explanations · Tree-Cycles | Importance: 0.994 -> 1.000 | Helped |
| Use UNR-Explainer explanations rather than 1hop-2N | Unsupervised GraphSAGE explanations · Tree-Grids | Precision: 0.965 -> 0.943 | Hurt |
| Add the restart selection policy (ablation) | UNR-Explainer MCTS · Cora | Importance: 0.955 -> 0.960 | Helped |
| Add the restart selection policy (ablation) | UNR-Explainer MCTS · Cora | Inference time (s): 8.11 -> 4.63 | Helped |
| Use average rather than maximum reward in UCB (ablation) | MCTS subgraph traversal · Cora | Importance: 0.949 vs. 0.960 | Hurt |
| Add node degree as UCB proximity guidance (ablation) | MCTS subgraph traversal · Cora | Importance: 0.951 vs. 0.960 | Hurt |
| Add common-neighbor count as UCB proximity guidance (ablation) | MCTS subgraph traversal · Cora | Importance: 0.956 vs. 0.960 | Hurt |
| Add feature cosine similarity as UCB proximity guidance (ablation) | MCTS subgraph traversal · Cora | Importance: 0.953 vs. 0.960 | Hurt |
Surprising findings
- Restart-based selection increased Importance but did not reduce the subgraph size on Cora (4.5 vs 3.67 without restart).
Limitations
- Explanation is restricted to a single target node and its local top-k neighborhood.
- UNR-Explainer does not reach ground truth on Tree-Grids due to size constraint.
- Theoretical upper bound is derived only for one-layer mean-aggregator GraphSAGE under an assumed monotonicity property.
Experimental setup
Datasets: BA-Shapes Tree-Cycles Tree-Grids Cora CiteSeer PubMed NIPS co-author network
Benchmarks: BA-Shapes Tree-Cycles Tree-Grids Cora CiteSeer PubMed
Metrics: Importance Size Precision Recall Validity Probability of Necessity Homogeneity Delta Homogeneity Time
Baselines: 1hop-2N 1hop-3N k-NN graph RW-G RW-G w/ Restart Taxonomy induction TAGE SubgraphX
Builds on: Monte Carlo Tree Search SubgraphX TAGE GraphSAGE Deep Graph Infomax
Closest papers by meaning
- COMRECGC: Global Graph Counterfactual Explainer through Common Recourse (ICML 2025 · similarity 0.87)
- GnnXemplar: Exemplars to Explanations - Natural Language Rules for Global GNN Interpretability (NeurIPS 2025 · similarity 0.87)
- Higher Order Structures for Graph Explanations (AAAI 2025 · similarity 0.87)
- Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.87)
- Factorized Explainer for Graph Neural Networks (AAAI 2024 · similarity 0.86)
- Graph Inverse Style Transfer for Counterfactual Explainability (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.