PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hyunju Kang, Geonhee Han, Hogun Park

arXiv:2605.17285v1cs.LGcs.AI

TL;DR

Unsupervised node representation explainability lacks effective counterfactual methods focused on nearest-neighbor structure. The paper introduces UNR-Explainer, which uses an Importance measure and restart-based MCTS to find minimal explanatory subgraphs; experiments report higher local impacts than baselines across downstream tasks.

  • Problem

    Explainability research has largely overlooked counterfactual reasoning for unsupervised node representations and their top-k nearest neighbors.

  • Method

    UNR-Explainer measures top-k neighbor changes after edge perturbation and uses restart-based MCTS to search for sparse, expressive explanatory subgraphs.

  • Results

    UNR-Explainer’s important subgraphs have higher local impacts than baseline methods across unsupervised and supervised downstream tasks.

  • Takeaways & Limitations

    Nearest-neighbor-based counterfactual explanations provide information about factors affecting embeddings and related downstream tasks.

  • Takeaways & Limitations

    Actionability and diversity remain unresolved because defining a desired action is challenging in unsupervised settings.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Unsupervised node representations support important downstream tasks, but existing explanations largely overlook nearest-neighbor changes and counterfactual reasoning. UNR-Explainer addresses this gap with sparse, expressive subgraph explanations found using MCTS.

  • Top-k nearest nodes significantly affect downstream link prediction, clustering, outlier detection, and recommendation tasks.
  • Existing graph explainers generally rely on class labels, while embedding explanations provide limited individual-node insight in unsupervised settings.
  • Counterfactual reasoning minimally perturbs edges to identify changes in a node’s top-k nearest neighbors, rather than supervised prediction labels.
  • UNR-Explainer defines importance through nearest-neighbor changes and uses MCTS with restart-inspired traversal to identify sparse, expressive explanatory subgraphs.

2 RELATED WORKS

Related work has developed explanations for unsupervised representations and graph embeddings, but counterfactual graph explanations have primarily targeted supervised class-label predictions.

  • Unsupervised-model explainability methods also include relevance propagation and label-free importance scoring for representations.
  • Taxonomy-based explanations organize learned embeddings hierarchically but are limited for explaining an individual node’s prediction.
  • TAGE identifies subgraphs with high mutual information for instances in unsupervised node representation learning.
  • Most graph counterfactual methods remove or add edges to alter supervised class-label predictions, limiting their direct applicability to unsupervised settings.

3 PROBLEM FORMULATION

The paper formulates unsupervised counterfactual explanations as minimal edge perturbations that substantially change a target node’s nearest neighbors in embedding space. Importance quantifies the resulting neighbor change.

  • 3.1 NODE REPRESENTATION LEARNING: The input graph contains vertices, node features, weighted edges, and neighborhood sets used by node representation learning.
  • 3.1 NODE REPRESENTATION LEARNING: GraphSAGE computes node representations by aggregating node attributes with information sampled from local neighborhoods.
  • 3.2 COUNTERFACTUAL EXPLANATION FOR UNSUPERVISED NODE REPRESENTATION LEARNING: A counterfactual subgraph removes or weakens selected edges, producing a perturbed graph and a changed target-node embedding while minimizing graph differences.
  • 3.2 COUNTERFACTUAL EXPLANATION FOR UNSUPERVISED NODE REPRESENTATION LEARNING: Embedding change alone is insufficient because any edge perturbation could become trivial; meaningful explanations therefore use changes in top-k nearest neighbors.
  • 3.2 COUNTERFACTUAL EXPLANATION FOR UNSUPERVISED NODE REPRESENTATION LEARNING: The counterfactual property holds when the top-k neighbor sets before and after perturbation differ.
  • 3.3 MEASURING Importance FOR COUNTERFACTUAL EXPLANATIONS: Importance measures the fraction of top-k neighbors replaced after removing the explanation subgraph, using Euclidean-distance nearest neighbors.

4 OUR PROPOSED METHOD

UNR-Explainer searches for minimal subgraphs that maximize nearest-neighbor change using a tailored MCTS procedure. Restart-based exploration addresses vanilla MCTS’s depth-first search bias.

  • 4 OUR PROPOSED METHOD: UNR-Explainer seeks the highest Importance explanation while maintaining the minimum number of perturbed edges.
  • 4.1 SUBGRAPH TRAVERSAL METHOD: MCTS traverses exponentially many candidate subgraphs by selecting graph actions from a root target node to a leaf.
  • 4.1 SUBGRAPH TRAVERSAL METHOD: Each search-tree action adds a node or edge to a candidate subgraph, and the traversed path is converted into the explanatory graph.
  • 4.1 SUBGRAPH TRAVERSAL METHOD: Rewards equal Importance, while visit counts, action values, and reward lists guide UCB-based selection and backpropagation.
  • 4.2 THE PROPOSED UNR-EXPLAINER: Vanilla MCTS tends toward depth-first traversal, causing previously visited nodes and nearby-hop alternatives to be underexplored.
  • 4.2 THE PROPOSED UNR-EXPLAINER: The proposed restart policy returns searches to the target root and excludes the previously optimal root action, promoting diverse target-centered connections.
  • 4.2 THE PROPOSED UNR-EXPLAINER: Random neighbor expansion limits exponential search growth, while simulation evaluates candidate paths and termination favors Importance 1 with minimal size.

5 EXPERIMENTS

UNR-Explainer is evaluated on synthetic and real-world graphs using counterfactual explanation metrics, downstream tasks, a case study, MCTS ablations, and parameter sensitivity. It generally identifies impactful, compact subgraphs, with performance varying by dataset and baseline.

  • 5.4 RQ1: PERFORMANCE OF UNR-EXPLAINER AND OTHER BASELINE MODELS: On synthetic datasets, UNR-Explainer achieves the highest Recall and Importance on BA-Shapes and Tree-Cycles, while simple baselines often obtain higher Precision.1hop-3N has the highest Precision on BA-Shapes and Tree-Cycles, and 1hop-2N has the highest Precision on Tree-Grids.
  • 5.4 RQ1: PERFORMANCE OF UNR-EXPLAINER AND OTHER BASELINE MODELS: On real-world datasets, UNR-Explainer records the best score on every reported metric except explanation size.It achieves the highest Validity, Importance, and Probability of Necessity while using smaller subgraphs than Taxonomy induction and TAGE.
  • 5.4 RQ1: PERFORMANCE OF UNR-EXPLAINER AND OTHER BASELINE MODELS: UNR-Explainer most strongly changes top-k neighbors and downstream outputs, including link-prediction necessity and clustering homogeneity after perturbation.On Cora, CiteSeer, and PubMed, original top-20-neighbor homogeneity is 0.866, 0.863, and 0.697, respectively, and drops most after UNR-Explainer perturbations.
  • 5.5 RQ2: A CASE STUDY IN COMMUNITY DETECTION ON NIPS DATASETS: The NIPS case study shows a target node moving from a deep-learning cluster to a reinforcement-learning cluster after perturbing the extracted explanation graph.The target is Caglar Gulcehr, initially clustered with Yoshua Bengio and subsequently aligned with Nicolas Heess.
  • 5.6 RQ3: ABLATION STUDY WITH OTHER MCTS-BASED SUBGRAPH TRAVERSAL METHODS: MCTS variants are compared by Importance, explanation size, and inference time, with UNR-Explainer producing the best Importance and inference-time results.The ablation considers action, expansion, UCB-based formula, and restart designs.
  • 5.7 RQ4: PARAMETER SENSITIVITY: Increasing k decreases Importance, while Importance rises with restart probability until prestart reaches 0.2.The study uses GraphSAGE on Cora and examines k and prestart as robustness-related hyperparameters.

6 CONCLUSION

UNR-Explainer defines counterfactual explanations for unsupervised node representations through changes in a target node’s top-k neighbors and identifies explanatory subgraphs with MCTS.

  • 6 CONCLUSION: UNR-Explainer identifies important subgraphs for a single node’s unsupervised representation using a k-nearest-neighbor counterfactual definition and a tailored MCTS selection policy.The policy prioritizes returning to the target node to find multiple paths in the search tree.
  • 6 CONCLUSION: The method removes a candidate subgraph’s edges, recomputes the perturbed embedding, and measures the difference between the original and perturbed top-k nearest neighbors.This Importance calculation provides the counterfactual criterion for selecting explanatory subgraphs.

C THEORETICAL ANALYSIS

The theoretical analysis characterizes limitations of vanilla MCTS traversal and bounds the Importance function for one-layer mean-aggregating GraphSAGE under inductive assumptions.

  • C.1 EXPRESSIVENESS OF MCTS-BASED SUBGRAPH TRAVERSAL: The analysis assumes that perturbing more edges adjacent to a node changes more components of its top-k neighborhood in embedding space.This assumption underlies the expressiveness analysis of vanilla MCTS.
  • C.1 EXPRESSIVENESS OF MCTS-BASED SUBGRAPH TRAVERSAL: Theorem 1 shows that vanilla MCTS favors actions producing larger subgraphs, reducing preference for breadth-first traversal that revisits previously visited nodes.The resulting search can favor depth-first exploration and may remain in an isolated region indefinitely.
  • C.2 UPPER BOUND OF Importance FUNCTION: Theorem 2 bounds Importance for a one-layer mean-aggregating GraphSAGE model using the aggregation weight matrix, activation Lipschitz constant, and embedding changes.The bound is derived under an inductive setting with trained model parameters and unchanged node features.
  • C.2 UPPER BOUND OF Importance FUNCTION: Importance is low when target and neighboring embeddings move similarly, but large when their perturbation-induced changes differ substantially.The analysis also states that the absolute Importance depends on the norm of Magg.
  • C. THEORETICAL ANALYSIS: The synthetic-subgraph examples illustrate the explanatory-subgraph construction used to study model behavior.The cited figure passage identifies examples from different models but does not report a theoretical result.

D.1 QUALITIVE ANALYSIS OF SYNTHETIC DATASETS

On synthetic datasets, UNR-Explainer produces subgraphs that more closely approximate ground-truth structures than the compared baselines, while its MCTS variants are described by their search designs.

  • D.1 QUALITIVE ANALYSIS OF SYNTHETIC DATASETS: UNR-Explainer more accurately represents synthetic ground truth than the baselines, with explanations centered on the target node and containing more connections.The difference between the restart and no-restart variants is small on small datasets, while both approximate ground-truth parts more closely.
  • D.1 QUALITIVE ANALYSIS OF SYNTHETIC DATASETS: RW-G produces path-shaped subgraphs that can miss ground truth, while 1hop-3N and 1hop-2N are insufficient when relevant structure extends beyond one hop.These comparisons are reported particularly for the BA-Shapes dataset and synthetic cases with ground truth beyond one hop.
  • D.3 DESCRIPTION OF THE VARIANTS OF THE MCTS-BASED ALGORITHM: Table 6 describes MCTS variants through action design and expansion strategy, including adding or removing nodes and expanding all or sampled neighbors.Sampling selects neighbors to match the input graph’s average degree and reduce the search space.
  • D.3 DESCRIPTION OF THE VARIANTS OF THE MCTS-BASED ALGORITHM: The paper reports that proximity measures did not yield significant gains and increased computational cost, so they were excluded from UNR-Explainer.This is an author-reported design decision for the final method.
  • D.1 QUALITIVE ANALYSIS OF SYNTHETIC DATASETS: Table 7 summarizes dataset statistics and downstream-task performance for the trained unsupervised node representations.The supplied passage identifies the table’s scope without reporting its cell values.

D.4 TIME COMPLEXITY ANALYSIS

The time-complexity analysis expresses UNR-Explainer’s search cost in terms of iterations, search-tree size, graph size, and restart behavior.

  • D.4 TIME COMPLEXITY ANALYSIS: Without restart, UNR-Explainer’s inductive search mainly depends on O(t⋅log(n)⋅∣V∣), with an additional O(∣V∣) cost for kNN simulation.With restart-based selection, the search is O(n) in the worst case.

D.5 EXPERIMENTAL SETUP

The evaluation trains unsupervised node representation models and uses their embeddings for node classification and link prediction, while also assessing clustering quality.

  • D.5 EXPERIMENTAL SETUP: GraphSAGE and DGI embeddings support downstream node classification and link prediction evaluation.Node classification uses logistic regression, while link prediction evaluates predicted links after splitting the graph into training and test data.
  • D.5 EXPERIMENTAL SETUP: Homogeneity and Silhouette Coefficient assess the quality of the initial embeddings for clustering.Homogeneity uses labels, whereas Silhouette Coefficient evaluates cluster separation without labels; higher values indicate better performance.

D.7 IMPLEMENTATION OF UNSUPERVISED NODE REPRESENTATION MODELS

The study implements GraphSAGE and DGI in an inductive setting with specified architectures, training hyperparameters, and software dependencies, alongside baseline explainers.

  • D.7 IMPLEMENTATION OF UNSUPERVISED NODE REPRESENTATION MODELS: GraphSAGE and DGI are implemented with PyTorch Geometric to evaluate the proposed method in the inductive setting.The implementation section identifies these two unsupervised node representation models as the evaluation models.
  • D.7 IMPLEMENTATION OF UNSUPERVISED NODE REPRESENTATION MODELS: GraphSAGE aggregates each node's features with the mean of its local neighbors using trainable self and aggregation parameters.The reported configuration uses batch size 256, 64 hidden dimensions, two hidden layers, dropout 0.5, and Adam optimization.
  • D.7 IMPLEMENTATION OF UNSUPERVISED NODE REPRESENTATION MODELS: Taxonomy Induction is reproduced using the authors' Matlab code and settings, while TAGE is evaluated without its downstream-task MLP stage.The number of clusters is set separately for real-world and synthetic datasets.
  • D.7 IMPLEMENTATION OF UNSUPERVISED NODE REPRESENTATION MODELS: The experiments use specified versions of Python, PyTorch, PyTorch Geometric components, CUDA, NumPy, and related scientific libraries.The environment includes Python 3.9.7, PyTorch 1.13.1, PyG 2.2.0, CUDA 11.7.1, and scikit-learn 1.1.3.

E LIMITATION, FUTURE WORK, AND NEGATIVE SOCIETAL IMPACTS

The paper leaves actionability and diversity in unsupervised counterfactual explanations for future work because desired actions depend on problem settings and datasets.

  • E LIMITATION, FUTURE WORK, AND NEGATIVE SOCIETAL IMPACTS: Actionability and diversity are not addressed because defining desired actions in unsupervised settings requires problem- and dataset-specific assumptions.The paper focuses primarily on counterfactual explanations for unsupervised node representation models and reports no recognized negative societal impacts.
Loading 2605.17285v1…