UNR-Explainer: Counterfactual Explanations for Unsupervised Node Representation Learning Models
Authors: Hyunju Kang
Geonhee Han
Hogun Park
Venue: ICLR 2024 poster (2024)
Keywords: XAI
Unsupervised node representation learning
Counterfactual Explanations
Primary area: visualization or interpretation of learned representations
TL;DR: UNR-Explainer aims to provide counterfactual explanations for a single target node in unsupervised node representation models.

Abstract: Node representation learning, such as Graph Neural Networks (GNNs), has become one of the important learning methods in machine learning, and the demand for reliable explanation generation is growing. Despite extensive research on explanation generation for supervised node representation learning, explaining unsupervised models has been less explored. To address this gap, we propose a method for generating counterfactual (CF) explanations in unsupervised node representation learning, aiming to 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. Furthermore, we introduce a Monte Carlo Tree Search (MCTS)-based explainability method for generating expressive CF explanations for **U**nsupervised **N**ode **R**epresentation learning methods, which we call **UNR-Explainer**. The proposed method demonstrates improved performance on six datasets for both unsupervised GraphSAGE and DGI.

Published as a conference paper at ICLR 2024
UNR-EXPLAINER, COUNTERFACTUAL EXPLANATIONS FOR UNSUPERVISED NODE REPRESENTATION LEARN- ING MODELS
Hyunju Kang, Geonhee Han, Hogun Park Department of Artificial Intelligence
Sungkyunkwan University
Suwon, Republic of Korea
(neutor, gunhee81 78, hogunpark (aaarrkkkkkkkkkkk (8skku.
ABSTRACT
Node representation learning, such Graph Neural Networks (GNNs), has emerged as a pivotal method in machine learning. The demand for reliable expla- nation generation surges, yet unsupervised models remain underexplored in this gard. To bridge this gap, we introduce a method for generating counterfactual (CF) explanations 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-Expir ENNR-xxplineer for generating expressive CF explanations for Unsupervised Node Representation learning methods based on Monte Carlo Tree Search (MCTS). The proposed method demonstrates superior performance on diverse datasets for unsupervised GraphSAGE and DGI. Our codes are available at /ht.tss:: //gi thub. com/h jong /unnnnguunree wwwp rexplainerr
INTRODUCTION
Unsupervised node representation learning encodes networks into low-dimensional vector spaces without relying on labels. Prior studies (Grover & Leskoved 2016) Kipt & Welling 2017) Xu et al.,
2019 Veličković et al. 2018 Xu al. 2021 have demonstrated state-of-the-arr performance across diverse tasks. Notably,
the top k-nearest nodes significantly impact downstream tasks such as link (Wang al. 2023). outlier detection (Goodgee al.) (022), and recommen- dation (Boytsov et al. 2016). The growing prevalence of these models in real- real-world applications has led to an increased demand for understanding their outputs. Particularly, understanding why a node occupies specific position is pivotal, shedding light on both learned embeddings and related tasks. Top-k link prediction, for instance, predicts potential future links by considering the top-k nearest unobserved nodes the target node in the embedding space. Local clustering in Wang et al. (2023) efficiently approximates global clusters by categorizing top-k nearest nodes into homogeneous clusters.
prediction, clustering
Despite the importance of the top-k nearest nodes in unsupervised representation learning, recent studies explainability have largely overlooked them. While existing research (Yuan al.) 2020; Ying et al. 2019 Luo et al.) 2020 Zhang et al. 2023) has mainly focused on explaining graph representation learning, relying on class labels, this method often falls short in unsupervised settings. Among the few studies that attempt to explain embedding vectors, Liu et al. (2018) utilize a hierarchical clustering model represent learned embeddings in taxonomy, providing comprehensive view of the structure but limited in explaining individual nodes. TAGE (Xie et al. 2022) provides explanations for each instance by identifying subgraphs with high mutual information with the learned embeddings. However, TAGE is limited in its capacity for counterfactual reasoning as it doesn't optimize for counterfactual properties.

---

Published as a conference paper at ICLR 2024
Counterfactual (CF) reasoning methods (Lu- cic et al. 2022
(8) CF-reasoning supervised learning
(b) CF reasossnn clustering
(c) CF-reasoning top-k prediction
Lin et al. 2021 Bajaj et al.
2021: Tan et al. 2022; Ma et al. 2022) offer
human- Juman-interpretable explanations by addressing the question "If certain edges had not occurred, would the prediction label Y have remained un- changed?" Despite active research on CF reason- ing in supervised settings for graph domains, its application in unsupervised settings remains un- derexplored. To explain node of interest in the embedding space, we employ CF reasoning in unsupervised settings by minimally perturbing edges crucial for the current top-k nearest nodes, yiclding disparate results. Figure[[ illustrates general CF reasoning in supervised settings, identifying edges causing label changes. However, this method is inapplicable in unsupervised settings due to the absence of class labels and decision boundaries. By utilizing top-k nearest nodes, we can explain learned embedding vectors and related tasks in unsupervised settings. For instance, Figure (I-b) depicts CF-reasoning in clustering task, where perturbing pertinent edges change the node's 's local neighborhood in the embedding space, potentially changing cluster assignments. Similarly, Figure (c) illustrates CF-reasoning in a top-k (here, ks = 3) link prediction task, where identifying edges that significantly affect top-k neighbors may yield different results in embedding- -ased link prediction tasks.
emb + [lAO::::mmm :mmb after perturbation (if changged)
Figure 1: Scenarios for counterfactual (CF) reason-
ing in downstream tasks. Best viewed in color.
To provide the CF reasoning in unsupervised learning, we introduce UNR-Explaines for unsupervised node representations (Hamilton et al.) 2017, Veličković et al.) 2018). Firstly, we define the CF explanation for unsupervised models by measuring the change of the top-k nearest neighboring nodes after perturbation, formulating it as Imporkance. To identify the explanatory subgraph, we employ Monte Carlo Tree Search (MCTS) (Swicchowski et al. 2022) tailored for our problem, inspired by Random Walk with Restart (Pan et alla||22.000 2004). Our novel subgraph traversal approach offers several advantages: 1) The subgraph by UNR- EiRlaxxlaieer is sparse yet efficient as CF explanations. 2) UNR- Explainer finds more expressive subgraphs than existing MCTS methods by alleviating search bias, as elucidated in Theorem ] UNR-Explainer provides meaningful CF explanations for unsupervised settings as demonstrated by extensive experiments. Given the significance of top-k nearest nodes in downstream tasks, our method facilitates the exploration of significant factors affecting embedding vectors, thereby expanding the applicability of CF reasoning in unsupervised learning.
RELATED WORKS
XAI for unsupervised models. While active studies have been conducted on explaining supervised models, the interest in XAI for unsupervised models (Montavon et al., 2022 Crabbé & van der Schaar 2022) has just ignited. In Montavon et al. (2022), neuralization propagation (NEON) is proposed to explain k-means clustering and kernel density estimation using wiser-wise relevance propagation. On the other hand, the authors in Crabbé & van der Schaar (2022) propose a method to explain the representation vectors without labels, providing a label-free importance score function highlight the important features and examples. However, both approaches are limited to apply to graph-structure data without consideration of the relationship between instances.
XAI for unsupervised node representation. Recent studies (Liu et al. 2018 Xie et al. 2022
Park & Neville 2023) have explored explainability for unsupervised node representation learning models on graphs. Liu al. (2018) propose method explain the learned network embedding by describing the inherent hierarchical structures through a taxonomy using the hierarchical clustering model. This approach converts the representation vector into a taxonomy for a comprehensive view but is limited to explaining the prediction of a node of interest. On the other side, TAGE (Xie) cet al., 2022) explains individual nodes in the form of a subgraph sharing high mutual information with the embedding vector. Consequently, the explanation from the TAGE could expand to various downstream tasks predicting node or graph labels by simply updating the gradient of the class label in the downstream model. However, TAGE has limitation in providing counterfactual explanations by minimal perturbation to change the class label. GRAPH- WGD (Park & Neville (023) is also relevant to our proposed method, while it aims generate global explanations for learned models.
2

---

Published as a conference paper at ICLR 2024
Counterfactual explanations. Most counterfactual reasonings for graphs explain predictions in supervised learning. Studies such as CF-GNNExplainer (Lucic et al. 2022), RCExplainer (Bajaj et al. 2021), and CF² (Tan et al. 2022) remove the important edges to emphasize the significant impact of edges in input on the prediction of class labels. CLEAR (Ma et al. 2022), and GCFExplainer (Huang et al. 2023) encourage the counterfactual result toward desired labels by adding new nodes or edges and removing the existing ones simultancously. The mentioned methods are limited to applying unsupervised models, for instance, CF-GNNExplainer (Lucic et al. 2022) as a pioneer of counterfactual explanation for the graph domain employs its counterfactual loss which is limited to applying unsupervised models. RCExplainer (Bajaj et al., 202T) leverages the decision boundaries to tackle the robustness of counterfactual explanations, but the decision region heavily relies on class labels. In the same manner, other explainability methods make it difficult to exclude the information from the class labels. Contrasting with existing XAI methods in supervised learning, UNR-Explaing is designed to generate counterfactual explanations in unsupervised learning contexts without relying on labels.
PROBLEM FORMULATION
3.1 NODE REPRESENTATION LEARNING
Notation An input graph G = {V,E, W} has a set of vertices V = foo, eN} with the node feature matrices X E R N xd and a set of edges & = ((),, Uj E V} with a edge's 's weight set W (w(r,yy) W()).)y) E [0, 1], (v;, v1) E E&). When the node has edges as E,- = {1,, (1), 1T) e E}, the neighboring nodes of the node v is expressed as é N,
Node representation learning such as GraphSAGE (Hamilton et al., 2017) aims to extract rep- resentation vectors of nodes by aggregating its attributes and information that is sampled from the local neighborhood. A trained unsupervised node representation model for an input graph G are represented as (9) = emb. For node v V. the representation vector is given by funsup (G,v) v) = emb,, It is calculated by stacking the embedding vector hy for a node v following as h, = o (M + Mags ..
I EueN, Xu) where Maelf and Magg are learnable parameter matrices.
In unsupervised settings, it optimizes that nearby nodes are close and distant nodes are far apart in the embedding space by defining k-hop neighbors as positive samples and other nodes as negative ones.
3.2 COUNTERFACTUAL EXPLANATION FOR UNSUPERVISED NODE REPRESENTATION LEARNING
Given (unnup(G, = emby, counterfactual reasoning aims to identify an explanation G. Ev,, We) G such that removing or weakening edges in E, from G to form G' = EV,E-E,,. W- W.} results in emb, & emb', as funsup(9" = emb', while minimizing the difference between and g'. The counterfactual explanation G, for an unsupervised node representation learning is inherently difficult to define the counterfactual property as emb, f emb', being subject to Junsup(C (G, v) emb, and funeup (g', v) emb'y- It is problematic because any edge is possible to be the trivial counterfactual explanation after perturbation causing emb, & emb''. Thus, defining the meaningful difference between two embedding vectors is necessary to provide a relevant counter- factual explanation for the target node v of interest. Since top-k nearest neighboring nodes are critical to downstream tasks, we exploit top-k nearest neighboring nodes to define the counterfactual explana- tion for the unsupervised model. This approach is well aligned with models such as GraphSage and node2vee (Grover& Leskovee (016;] Hammlton et al.) 2017) since their objective function optimizes the embedding vector in which similar nodes are located relatively close while dissimilar ones are far away. Thus, the top-k nearest neighboring nodes share similar features for related downstream tasks. Therefore, we utilize the top-k nearest neighboring nodes define the counterfactual property for unsupervised representation learning models as follows:
Definition 1 Given funsup (G.eupGGG)) v) emby and funsup ( emb',, hyper-parameter k and function N U, k), a counterfactual property for the node v as emby & emb', is satisfied when NN N (emb, k) & KN N N v,kk, k).
3

---

Published as a conference paper at ICLR 2024
3.3 MEASURING Importance FOR COUNTERFACTUAL EXPLANATIONS
Upon the Definition D. we define a measure to quantify the Importance of the subgraph G. as
counterfactual explanation below:
Importance(fuseer e, (set(k e, se
(S (fooupp 2,),1, (I)
where KN N is found based on the Euclidean distance. Using Importance, we define a counterfactual
explanation G. for the embedding vector in unsupervised node representation learning below:
Definition 2 Given funsup(G () emb counterfactual reasoning aims to identify subgraph G. (V.,e,, W.} = G such that removing or weakening edges in & from G to form G' = {V,E- Eg, W - W,, maximizes the Importance while minimizing the difference between and g'.
If the subgraph G3 is critical the target node's 's node embedding, the effect of the perturbation must be significant based on the counterfactual assumption. Hence, the subgraph G3 is employed as the explanation for the target node's 's node embedding. If the Importance is O, observe effect on the top-k neighboring nodes in the updated embedding space. Meanwhile, when the Importance is all surrounding neighbors are changed, fully satisfying the counterfactual property. We note that we leverage an LSH hashing (Shrivastava & Li 2014) to obtain the nearest neighbors efficiently. To obtain the perturbed G'. we employ the perturbation method which weakens the weight of the input graph edges equivalent to the edges of the subgraph. An overview of Importance function is provided in Algorithm 2 Appendix [B] Additionally, we theoretically analyze the upper bound of Importance
upon GraphSAGE in Theorem
2 in Appendix C.2
4 OUR PROPOSED METHOD
Our goal is to find an explanation subgraph G3 as a counterfactual explanation with the highest Importance score change the top-k neighbors in embedding space while maintaining the minimum edge size [9s]. It is defined as
arg min max (Fmpprttacce((mmmn(())))))) k).
(2)
9.1
G.
Due the exponential number of existing subgraphs, an efficient traversal method is required. Thus, we leverage the Monte Carlo Tree Search (MCTS) (Sutton & Barto 2018) which is one of reinforcement learning and well-known to outperform in large search spaces (Silver al. 2017). MCTS utilizes search tree in which series of actions is selected from root to leaf node resulting in the maximum reward according to the pre-defined reward function. We tailor the MCTS suit our problem setting by applying the Importance as the reward to obtain the explanation subgraph g.. This method brings the advantages of not only searching subgraphs efficiently thanks to the reinforcement algorithm but also searching the subgraph sparse yet expressive.
4.1 SUBGRAPH TRAVERSAL METHOD
We initialize a search tree in which each node N; has properties as (S(N), A(N:)) where S(N;) denotes a state and A(N:) represents a of actions. The node N; in the tree corresponds to the node v E V in the input graph G, and S(N;) indicates an index of the node v. The edges in the tree mean actions é A(N,). The action is select one node in the search tree equivalently meaning that we add new edge or node gradually in the candidate subgraph. To start in the initial search tree, we set root node So
as the index of the node to explore subgraphs around the target node v. At each iteration f, the algorithm travels from the root node No to leaf node N;. resulting in the trajectory T, = {(No, 01) ..., (N., ))) Then, we can transform the path n. to S(N.)) E {(S(N.) Ve, a, = N,, 1++1 = NR. ao = Ny) defined as a function Convert(r) = 9r. Consequently, searching the subgraph G. by searching the path via the MCTS algorithm is possible. A pair (N, a,) of node N; and action aj stores statistics (C(N,,a), Q(N. a), L(N,,a) which are described as following: 1) C(N;,a) is the number of visits for selecting the action a e A(N,) the node
subgraph G. (V,,E,, W.). V.
S(N))
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 UNR-Exppainse with restart
1: Input: trained model funsup (.), input graph G. NNN parameter k. target node v, exploration
term X, probability p~ Uni (O, 1) and restart probability Prestart
2: Initialization: Initialize 9 = (}. step O, and set a root node No. ((N)) (
3: while termination condition do
4: cur N ode +- No; trajectory 7 0)+++ 1; Expand the child nodes of cur N ode a) in Eq.
5: Select A(cur Node) by
6: while Node is not leaf node do
7:
if p Prestort then
8:
cur + No: Append pair (No, a) into the trajectory T Obtain a' using (3.(3) and select randomly action a A(N)) a* curNode + N₁ by action a
9:
10:
11:
end
12:
Select a A(curNode)) by UCB(cur a) in Eq.(3
13:
Append a pair (curNooe Node, a) into the trajectory т
14:
curNode + N, by action
15:
end while
16:
if the leaf node has child then
17:
Expand the child nodes of curNode
18:
Select a A( N Vode) by (Cu a) in Eq.
19:
Append a pair (cur Node, a) into the trajectory end
21:
Calculate the reward by R(T)
Backpropagate the reward and visit counts (Nv E
23:
G- Convert(T); Append 9- into the list Gt
end while
25:
Return G. from Gi using Eq. 2
No. 2) Q(N.;a) a) is action value that calculated the maximum value in of rewards L(N,,a) a) aiming to obtain the highest important subgraph. 3) L(N:, a) is a list of obtained rewards from reward function R(r) every iteration when (N, a) r. 4) R(T) the reward function to calculate Importance as R(T)= Importance (funsup (funsu()). (,,,,,, v). We obtain the subgraph G, from Convert(() Gr. Utilizing the statistics, the algorithm searches the path with the highest Importance
based on the upper confidence boundary (UCB) in (Swiechowski et al. 2022) as UCB(N,,))
aNN.a))
In(C(No.a)) C(N.o)
a" = arg MaggaxxUCDD ArggauUCBBNN.....c A(N.)
While the Q(N,, a) promotes choosing the action with a higher reward, the latter term relating to C(N,, a) encourages exploration by choosing the less visited action. A hyperparameter À controls the magnitude of exploration balance exploitation and exploration. Additionally, the term P intends to provide useful information for the guidance of exploration. In the case of the term P= 1 as constant, UCB does not utilize the additional guidance. Further, we discuss the benefit of our setting compared to other employments of MCTS and prove the efficiency of our exploration method through the ablation study in Table 4
4.2 THE PROPOSED UNR-EAN SAR-EXPLAINER
The vanilla MCTS algorithm in our setting has an issue of low expressiveness in the selection step in the aspect of the UCB formula theoretically. Because the existing UCB-based search policy tends to generate the subgraph in depth-first manner rather than in breadth-first manner, the previously appeared node is seldom selected by the UCB-based formula, leading not to explore close hop neighboring nodes even its importance. Based on empirical assumption demonstrated experimentally in studies (Bajaj et al. 2021; Yuan et al.) 202T), we present theoretical analysis of the expressiveness limitation inherent in the vanilla MCTS algorithm follows.
5

---

Published as a conference paper at ICLR 2024
Theorem Let be an action aj at arbitrary node N₂ in trajectory {(No, (1lo,aa1):..) (N₂, az) }. resulting in a next node Ng. Suppose a1, 02 E <(())) where the action a₁ leads to a node Nm with a state function ((Nm) S(N;), and the action a2 leads to a node N, with S(N,) S(N.). Then, we have
UCB(NN,, a1) UUBB(NR
We provide proof and detailed analysis of Theorem in Appendix C.1 To ensure that the resulting subgraphs of the traversal are more expressive and accurate, we introduce a new selection policy in the following section. The overview of the algorithm is described in Algorithm
Selection with a new policy. At every iteration, a restart probability Prestart [0. 1],p
frrmo0 1) is sampled. When p Prestart, it returns to the root node and randomly explores another path a e A(N)) a" excluding the optimal one from the root. Thus, promotes more connections centered around the target node. Implementing the restart probability as new selection policy has several advantages: 1) It reduces the bias towards deep-first traversal, increasing the likelihood of generating diverse candidate subgraphs. 2) It helps to prevent getting stuck an isolated island or infinite iteration. When p 2 Prestort. the algorithms select the child nodes with the higher UCB score in Eq. (3. The selection continues until it reaches the leaf node. It is described in line from 5 to 15 of Algorithm
Expansion. When arriving the leaf node, the tree expands if the number of visits to the leaf node is more than one. The tree adds the child nodes from the neighboring nodes of the current node's s state in the input graph G. However, considering all neighbor nodes as child nodes causes exponential search space. Therefore, we randomly select nodes from the neighbors of the leaf nodes in the input graph G compute them more efficiently, setting the expansion number E to be equal to the average degree of the input graph G. It is described in line from 16 to 20 of Algorithm [
Simulation. We transform the obtained trajectory T to the subgraph Gy. As The generated subgraph 9- is a candidate of the important subgraph stored in a list G, we measure the Importance of the subgraph G, for the reward. It is described in line 21 of Algorithm [
Backpropagation. Finally, we update the reward and the number of visits to the statistics of related nodes the trajectory. The number of visits C( C(N;,0) a) renewed for C(N,, a) + 1. Then, we append the obtained reward to a list of rewards T.(N,, a). Consequently, the action value Q(Ni, a)) updated by max a.), These updated statistics are exploited for the next selection to explore the subgraph with higher Importance. It is described in line 22 of Algorithm
Termination condition. Our subgraphs have two main properties as the counterfactual explanation. First, the importance is close to 1, affecting all the top-k neighbors after perturbation. Second, the size of the subgraph is minimal. To achieve the goal, we explore the subgraph setting the terminal condition as Importance == 1.0 with limited but enough steps T. When the algorithm ends after meeting the condition, we select the subgraph with a minimum size of the subgraph among the one with maximum Importance. As result, we effectively search the explanatory subgraphs satisfying the properties of counterfactual explanations.
EXPERIMENTS
5.1 DATASETS
The experiments are conducted on three synthetic datasets (Ying al. 2019 Luo al. 2020) and three real-world datasets from Py Torch-Geometrice (Fey & Lenssen 2019). The synthetic datasets (BA-Shapes, Tree- Cycles, and Tree-Grid (Ying et al. 20199) are used, containing network motifs such as houses, cycles, and grid- grid-structure motifs respectively. These motifs serve as the ground truth of the datasets to evaluate the explanation method (Yuan et al. 2020). The real-world datasets (Cora, CiteSeer, and PubMed (Grover & Leskovec 2016)) are citation networks commonly used in graph domain tasks. Each node indicates a paper and each edge notes a citation between papers. The features of the nodes represented as bag-of-won words of the papers and each node is labeled as the paper's 's topic. Additionally, we exploit the NIPS dataset from Kaggle to employ the case study of our method. The statistics of the datasets are reported in Table 7 in the Appendix.

---

Published as a conference paper at ICLR 2024
Table 1: Evaluation of CF explanations synthetic datasets in unsupervised settings ground- truth. Prc, Rel, and Impt indicate Precision, Recall, and Importance. The best performances on each dataset are shown in bold.
BA-Shapes
Tree-Cycles
Tree-Grds
Methods
Pre
1mpt
Pre
Impt
Size
Pre
Rel
Impt
Size
1hop-2N
0.934
0.156
0.492
1.0
0.900
0.150
0.277
1.0
0.965
0.161
0.683
1.0
Ihop-3N
0.943
0,314
0.817
2.0
0.895
0.298
0.994
2.0
0.959
0.320
0.633
2.0
k-NN graph
0.025
0.012
0.392
1.8
0.017
0.006
0.148
1.5
0.013
0.004
0.337
1.1
RW-G
0.890
0.263
0.597
1.8
0.862
0.302
0.591
2.1
0.925
0.459
0.834
3.4
RW-G w/ Restart
0,881
0.268
0.683
1.9
0,840
0,300
0.641
2.1
0.917
0,496
0.922
3.6
Taxonomy induction
0.731
0.310
0.292
1.8
0.765
0.298
0.454
1.8
0.377
0.140
0.369
0.9
TAGE
0.422
0.225
0.220
2.4
0.290
0.230
0.166
0.415
0.360
0.260
2.3
UNR-Explainer
0,923
0.288
1,000
1.9
0,903
0.324
1,000
2.1
0,943
0.519
0.994
3.6
5.2 BASELINE METHODS
In unsupervised settings, we compare UNR-Explainer with seven baselines as follows: 1) 1hop-2N is subgraph of an ego network in which edges are randomly removed until the number of nodes is two 2) 1hop-3N is a subgraph of an ego network in which edges are randomly removed until the number of nodes three. 3) k-NN graph
subgraph whose nodes and edges are top-5 nearest neighbors in the embedding space. 4) RW-G generates subgraph by the random walk algorithm by traveling neighboring nodes from the target node v. For fair comparison, the number of nodes and edges in the graph is mostly equal to one from our proposed method. 5) RW-G w/ Restart are generated in the same way as RW-G but applying random walk with restart. 6) Taxonomy induction (Liu et al., (018)) outputs the clusters as the global explanation of the embedding vector. We expect that the subgraphs in the cluster can be utilized as a local explanation. 7) TAGE (Xie et al. 2022) generates a subgraph with high mutual information of the learned embedding vector.
5.3 EVALUATION METRICS
We evaluate explanation subgraphs in the counterfactual aspect by the following metrics: 1) Impor- tance of the explanation subgraph 9, is utilized to measure the impact in the embedding space. 2) Size (Tan et al., (022) shows how the explanation is effective with minimal perturbation on synthetic and real-world datasets. 3) Precision Recall (Tan et al. 2022) on average w.r.t ground truth are measured on the synthetic datasets. 4) Validity (Verma et al. 2020) is commonly used to effectiveness related to f() & f(G') in supervised learning. By utilizing Importance, we calculated the averaged validity for the unsupervised model as V Validity(G.)
Importance(fuae (unsuup() (-), G. G.. u, k) 1.0)]. 5) Probability of Necessity as PN (Tan et al. 2022) in top-k link prediction tasks are used to measure how predictions as Hit 5 changed demonstrate the effectiveness of the explanations. 6) Homogeneity represents the percentage that the top-k neighbors of a node of interest belong to the same cluster of the node of interest in the node embedding space after perturbing the generated expla- nation for each baseline. Original Homogeneity in the learned embedding space before perturbation expressed as the input graph in Table 3 7) Homogeneity means the difference between the H Homogeneity of Input graph and the Homogeneity of each baseline.
5.4 RQI: PERFORMANCE OF UNR-EXPLAINDR AND OTHER BASELINE MODELS
We demonstrate the performance of UNR-Explainer showing our explanation graphs change the top-k nearest nodes and impacts related downstream tasks in node classification, link prediction, and clustering in unsupervised settings in Table I| 2 and 3 From Table I on synthetic datasets, we demonstrate that UNR- Explainer describes the ground truth, showing the highest Recall and Importance among basclines on BA-Shapes and Tree-Cycles datasets. In the experiment, 1hop-3N demonstrates the highest Precision on both the BA-Shapes and Tree-Cycles datasets, and 1hop-2N exhibits the highest Precision on the Tree-Grids dataset. Regarding the BA-Shape dataset, there are 80 house-structured motifs, each comprising 5 nodes as the ground truth, and only a few edges Ihop-2N
in these motifs are connected to the base BA graph. When we generate explanations and 1hop-3N for nodes within these house motifs, the precision tends to be high. This is due to the increased probability that the explanation will include another node from the house-structured motif, thereby aligning with the ground truth. Similarly, for other synthetic datasets constructed in the same manner, Thop-2N and Thop-3N exhibit high precision but low recall. k-NN graph in
7

---

Published as a conference paper at ICLR 2024
Table 2: Evaluation of CF explanations on real-world datasets in unsupervised settings. Vid, Impt, and PN indicate Validity, Importance, and Probability of Necessity. The best performances on cach dataset are shown in bold.
Cora
CiteSoer
FubMed
Methods
Vid 1
1mpt 1
1
Size
Impt
PN
Size
Vid 1
Impt
Size
1bop-2N
0.210
0.465
0.006
1.0
0,340
0.551
0.020
1.0
0.485
0.623
0,000
1.0
Ihop-3N
0.428
0.659
0.021
2.0
0.503
0.714
0.035
1.6
0.639
0.724
0.000
1.5
k-NN graph
0,253
0.593
0.019
3.3
0.243
0.609
0.028
3.3
0.022
0.090
0.000
1.0
RW-G
0.265
0.544
0.019
3.6
0.393
0.643
0.024
2.7
0.478
0.631
0.027
2.0
RW-G w/ Restart
0.327
0.614
0.019
3.8
0.453
0.696
0.029
2.8
0.514
0.662
0.029
3.1
Taxonomy induction
0.243
0,548
0.023
9.7
0.236
0.528
0.037
4.9
0.035
0.061
0.000
1.8
TAGE
0.232
0.482
0.016
5.4
0.254
0.487
0.031
3.7
0.082
0.268
0.012
11.8
UNR-Explainer
0.911
0.960
0.051
3.8
0.778
0.910
0.054
2.8
0.847
0.903
0.034
3.7
Table 3: Evaluation of CF explanations upon clustering tasks on real-world datasets. Hmg and A Hmg indicate Homogeneity and the change of Homogeneity.
Cora
CiteSeer
PubMed A Hmg
Methods
Hmg
A Hmg
Hmg
A Hmg
Hmg
Input graph
0.866
0.863
0.697
Thop-2N
0.695
0.171
0.564
0.298
0.372
0.325
Ihop-3N
0.520
0.347
0.401
0.462
0.299
0.398
N--NN graph
0.621
0.245
0.629
0.234
0.636
0.061
RW-G
0.646
0.220
0.487
0.376
0.364
0.333
RW-G w/ Restart
0.594
0.272
0.441
0.422
0.331
0.366
Taxonomy induction
0.598
0.268
0.595
0.268
0.579
0.118
TAGE
0.627
0.240
0.569
0.294
0.555
0.142
UNR-Explainer 0.315
0,551
0.272
0.591
0.243
0.454
the embedding space is limited to constructing the subgraph valid in the input graph since graph neural networks encounter challenges preserving graph topology. RW-G w/ Restart demonstrates proposed selection policy, showing higher recall than RW-G with a slightly larger size. Explanations from Taxonomy induction based on global clusters are not as sufficient as local CF explanations. On the Tree-Grid dataset, UNR-Explainer does not reach the ground truth due to the minimal constraint of the size. In the case of TAGE, it reaches the highest recall on Tree-Grids datasets but the largest size and the lowest Importance without satisfying counterfactual measurements.
Table 2 shows the results on real-world datasets, where UNR-Explainer records the best score in all metrics except size. Explanations by UNR-Explaine impact most of the top-k neighbors after perturbation, showing the highest Validity and Importance with a smaller size of subgraphs than Taxonomy induction and TAGE. When we apply the embedding vector into top-5 link prediction tasks, originally the accuracy of the prediction is 0.570, 0.575, and 0.55 respectively on Cora, SiteSeer, and Pubmed datasets. After the perturbation of each explanation, the predictions w.r.t PN change the most in the case of UNR- Expplixpl due to the significant difference of top-k neighbors. None of Taxonomy induction and TAGE optimize the counterfactual term, resulting in lower PN. On PubMed datasets, we sample 10% of nodes and evaluate the change of probability in node classification.
demonstrate that explanatory graphs affect clustering tasks in unsupervised set- tings. When l is equal to 20, the majority of the top-k neighbors in the embedding space typi- cally belong to the same cluster of node of interest, as observed by the homogeneily values of 0.866, 0.863, and O. 696 on the Cora, CiteSeer, and PubMed datasets, respectively. After perturbating of found explanations by UNR-Explainer, the homogeneily of original top-k neighbors drops signif- icantly at the most among baselines, which means that node of interest is no longer part of the cluster but different one as a counterfactual result. Hence, explanations by UNR- -xN--Exp affect top-k neighbors in the embedding but also the output of related downstream tasks.
In Table
5.5
RQ2: A CASE STUDY IN COMMUNITY DETECTION 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 a co-author network dataset of the NIPS con- ferences (Hamner) 2017). Upon applying Graph- SAGE in unsupervised settings, we extract signifi-
01. 8
87 610
(S)
Imput graph G
Embeddding space
Figure 2: Case study on NIPS datasets.
8

---

Published as a conference paper at ICLR 2024
cant subgraphs using INR-Explainer illustrating its effectiveness in impacting k-means clustering task. In Figure a target node, highlighted as yellow node a representing Caglar Gulcehr, is initially part of the cluster of Yoshua Bengio, known for publications primarily related to deep learning and general machine learning, represented by node d. In this figure, node positions in the embedding space determined through t-SNE learning (van der Maaten & Hinton 2008). After perturbing the found explanation graph, illustrated by red edges, the node aligns with the cluster of Nicolas Heess, notable for publications primarily related reinforcement learning, as represented by node n.
5.6 RQ3: ABLATION STUDY WITH OTHER ACTS-BASER SUBGRAPH TRAVERSAL METHODS
Table 4:
We evaluate variants of the MCTS algorithm considering the design of the action, the expan- sion, the JCBB-ased formula, and the restart as shown the result Table [ As evaluation metrics, Importance, explanation size, and the mean inference time (8) per node are measured. As result, UNR-Explainer shows the best re- sults considering the importance and inference time (s). In SubgraphX (Yuan al. 202T), D. its action is to prune equally meaning to remove nodes. Since counterfactual explanations must be minimal with high validity, SubgraphX fails to find the subgraph particularly when it deals with the high-degree target node showing bigger size than other baselines. We note that Prx means proximity as the term P for better guidance in Eq 3 However, none of the Prx helps guide the important subgraph. On the contrary, our proposed UNR-Explainer makes it possible to search the sparse yet expressive subgraph efficiently with high importance. Detailed information including the node's proximity (Prx) is written in Appendix D.3
Ablation study of the MCTS based
method Cora dataset.
Name MCTS
Time(s)
Impt
Size
11.30
0.942
3.43
SubgraphX-1
176.30
0.936
28.49
SubgraphX-2
146.02
0.937
25.66
MCTS-Avg
10.11
0.949
3.62
MCTS-Prx
9.85
0,951
3.71
MCTS-Prx:
7.14
0.956
3,59
MCTS-Prx3
10:55
0.953
3.60
UNR-Explaiiee w/o
8.11
0.955
3.67
UNR-Explainer 4.63
0.960
4.5
5.7
RQ4: PARAMETER SENSITIVITY
We evaluate the robustness model relating to crucial hyperparameters, such as the top-k number of neighbors i and the restart probability Prestart using the GraphSAGB model on the Cora dataset.
1.00
1.00
Importance
0.95
0.95
The results are shown in Figure 3 As the hyper- parameter k increases, the importance decreases.
0.85
0.85
This because the hyperparameter determines the range of the local region in the embedding space, and larger region containing nodes further away from the target node is less affected. Further- more, the importance increases until the restart probability Prestart reaches 0.2, the value used in our model's setting. Additionally, we observe that the exploration X does not affect the models' performance much.
20
Prestart
Figure 3: The study of parameter sensitivity for the number of the nearest neighbors as & and the restart probability Preaturt-
CONCLUSION
In this paper, we propose a counterfactual explanation method, UNR-Explainer, to explain the unsupervised node representation vector of a single node. We define k-nearest neighbor-bar based counterfactual explanation and propose new selection policy to identify the important subgraph that prioritizes returning back to the target node to find multiple paths in the search tree. Our experimental results show that the important subgraphs generated by UNR-Explainer have higher local impacts in both unsupervised and supervised downstream tasks compared to other baseline methods.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGMENT
We thank the anonymous reviewers for their valuable feedback and insights. Hogun Park is the corresponding author. This work was supported by the National Research Foundation of Korea (NRF) (202RRICICION) 10054007; and by the Institute of Information & Communications Technology Planning Evaluation (ITTP) grant funded by the Korea government (MSIT): (No. 2019-0-00421, Artificial Intelligence Graduate School Program (Sungkyunkwan University)) and (No.
Knowledge Information Structure Technology for the Multiple Variations of Digital Assets). This research also supported by the Culture, Sports, and Tourism R&D Program through the Korea Creative Content Agency grant funded by the Ministry of Culture, Sports and Tourism in 2024 (Project Name: Research neural watermark technology for copyright protection of generative Al 3D content, 25%).
REFERENCES
Mohit Bajaj. Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. In Proceedings of the Neural Information Processing Systems, 2021.
Leonid Boytsov, David Novak, Yury Malkov, and Eric Nyberg. Off the beaten path: Let's replace term-based retrieval with k-nn search. In Proceedings of the The Conference on Information and Knowledge Management, pp. 1099-1108. 2016.
Jonathan Crabbé and Mihaela van der Schaar. Label-free explainability for unsupervised models. In Proceedings of the International Conference on Machine Learning. 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py PyTorch Geometric. In Pro- ceedings of the International Conference on Learning Representations Workshop on Representation Learning Graphs and Manifolds, 2019.
Adam Goodge, Bryan Hooi, See-Kiong Ng, and Wee Siong Ng. Lunar: Unifying local outlier detec- tion methods via graph neural networks. In Proceedings of the Association for the Advancement of Artificial Intelligence, volume 36, pp. 6737-6744 6745, 2022.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the ACM SIGKDD international conference Knowledge discovery and data mining, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the Neural Information Processing Systems, 2017.
Ben
Hamner.
Nips
papers,
2017.
URL
https:/
Internation iona Wor LdWi wewhheeeeeoooeeeeeeecc kagg le.glle.. wtt.cccccc/s/.. hts///svvv999
Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Global counterfactual explainer for graph neural networks. In Proceedings of the ACM International Conference on Web Search and Data Mining, pp. 141-149, 2023.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations, 2017.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In Proceedings of the International Conference on Machine Learning, 2021.
Ninghao Liu, Xiao Huang, Jundong Li, and Xia Hu. On interpretation of network embedding via taxonomy induction. In Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, 2018
Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In Proceedings of the International Conference Artificial Intelligence and Statisties, 2022.
10

---

Published as a conference paper at ICLR 2024
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Proceedings of the Neural Information Processing Systems, pp. 19620-19631, 2020.
Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. Clear: Generative counterfactual explanations on graphs. In Proceedings of the Neural Information Processing Systems, 2022.
Grégoire Montavon, Jacob Kauffmann, Wojeiech Samek, and Robert Müller. Explaining the predictions of unsupervised learning models. In Proceedings of the xxAI in Conjunction with International Conference on Machine Learning, 2022.
Jia- Yu Pan, Hyung-Jeong Yang. Christos Faloutsos, and Pinar Duygulu. Automatic multimedia cross-modal correlation discovery. In Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, 2004.
Hogun Park and Jennifer Neville. Generating post-hoe explanations for skip-gram-based node embeddings by identifying important nodes with bridgeness. Neural Networks, 164:546-561, 2023.
Anshumali Shrivastava and Ping Li, Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Proceedings of the Neural Information Processing Systems, volume 27, 2014.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676)3354-355 2017.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Maúdziuk. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, pp. 1-66, 2022.
Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the International World Wide Web Conference, 2022.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 986):2579--665, 2008.
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò. Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In Proceedings of the International Conference on Learning Representations, 2018.
Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint
0at:20000119966 2020.
Yan Wang, Yan Ma, Hui Huang, Bin Wang, and Debi Prasanna Acharjya. A split-merge merge clustering algorithm based on the k-nearest neighbor graph. Information Systems, 1 111:102124, 2023.
Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. Task-agnostic graph explanations. In Proceedings of the Neural Information Processing Systems, 2022.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. In Proceedings of the Neural Information Processing Systems, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the International Conference Learning Representattinss, 2019.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You. Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Proceedings of the Neural Information Processing Systems, 2019.
11

---

Published as a conference paper at ICLR 2024
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Proceedings of the International Conference on Machine Learning, 2021.
Shichang Zhang, Jiani Zhang, Xiang Song. Soji Adeshina, Da Zheng, Christos Faloutsos, and Yizhou Sun. Page-link: Path-based graph neural network explanation for heterogeneous link prediction. In Proceedings of the International World Wide Web Conference, pp. 3784-3793, 2023.
12

---

Published as a conference paper at ICLR 2024
Input graph
Algorithm
Fi
53
Prosee
$ wcb 1.5
B ucb 0.7
Eq. (2)
Pindet
Impportance(fusuuy (..G. 0,K 3) (q.
Importance
Perturb (G.9.)
Funsap(g)
Zg
1
1.0
semb,
95
perturbed edges
eemb'
Figure 4: Overall procedure of UNR-Explainer to explain the unsupervised node representation embedding of node O (target node). Our proposed method is to search the most important subgraph G. as the explanation for the target node. (Best viewed in color.)
A OVERVIEW OF
The overview of UNR-Explainer is provided in Figure Initially, the input & and learned model Sunsup()) (.) are provided. These are used in the importance function described in Eq. [ under Algorithm| to traverse the most contributive subgraph.
B THE ALGORITHM OF Importance
We describe the process of calculating the Importance for the subgraph G, detailed in Algorithm 2 First, the perturbation remove the edges of the subgraph 9, from the input graph G. Subsequently. we construct the perturbed graph gperturbed and obtain the k-nearest neighbors (kNN) for the target node v. Finally, the Importance G. is evaluated as the difference between the top-k nearest neighbors in G and perturbed.
Algorithm 2 Importancel Sarennceennnnn Jussup (a (). D.G.ss,
1: Input: embedding model f funssu('), input graph G (V,E,W) W), subgraph 9, (V.,Es, W.). target node v, the number of top-k neighbors NNN as
2: Sperturbed (V,E E,,W),
3: emb < Sunoup(( (9)
4: emb' funsup (Geerturbed)
5: O NNN (emb, e, # get the top-k neighbors of v in emb
6: (eN('emb', u. k) # get the top-k neighbors of emb'
7: Return (O) set(N))/k: # Importance.
C THEORETICAL ANALYSIS
C.I EXPRESSIVENESS OF MCTS- BASED SUBGRAPH TRAVERSAL
We present a theoretical analysis of the expressiveness limitation inherent in the vanilla MCTS algorithm, specifically its restriction to searching for the optimal explanatory subgraph. We analyze the low expressiveness in the selection step in the aspect of the UCB formula theoretically. In the vanilla MCTS, generating the subgraph in breadth-first manner requires previously appeared
13

---

Published as a conference paper at ICLR 2024
node as newly expanded child node in the tree return back to the root node. Yet, the previously appeared node seldom selected by the UCB-bases formula, as the action doesn't 't yield any gain due to difference in Eg. Before presenting this analysis, introduce empirical assumption that has been demonstrated experimentally in studies (Bajaj et al. 2021: Yuan et al. (021). as follows:
The graph that is perturbed by more edges of results in changes to more components of kN (emb,, v, k) in the embedding space.
Assumption
Based on Assumption we theoretically analyze the expressiveness of the vanilla MCTS subgraph traversal procedure in Theorem and present proof as follows.
Let be an action 0g at an arbitrary node N; in a trajectory Tr = {(No,, a1 (1), )...., (N1, az) (3)) resulting in next node Ng. Suppose a1, u2 A(Na) where the action aı leads to node Nm with state function S(Nm) # S(N)), and the action 02 leads to a node Nn with S(N,) S(N.). Then, we have
Theorem 1
UCB(N& a1) 2 (UBB(NR.
(5)
Proof. When the algorithm selects an action (1) or (Nk, az) using Equation (3) at the node
NR. we assume that the number of visit counts is identical as C(N,, C(N+ 0-) Then only
term Q(N,, uy) matters Equation (3). To calculate the Imporance as the reward, the trajectory is converted into the subgraph G Er, using the function Conwerl(T.. Since the action (Ng, a1) adds a new edge in the trajectory Te-1, the size of edges in a subgraph G1 is equal to |E,] + On the contrary, the action (Nk, a2) does not add any edge such that the size of edges in subgraph G2 is equal to E, Accordingly, the size of edges is different as (E(G)) ) > [E(). Using the Assumption their Importance values have the following relationship:
Importance( (),9, 91, Importance(fussugl O) k,,,,,,
(6)
Therefore, Q(Ne, a1) 2 Q(Ns, 02) is obtained. Finally, we can see that UCB(N&, a1) 2 UCB((N,, 02) because of C(N 02N,,
As demonstrated in Theorem D we have ascertained that the importance of a subgraph increases with the number of edges it contains. With the vanilla MCTS, generated subgraphs exhibit lower expressiveness, showing less preference for generating in breadth-firs manner, which requires selecting previously visited nodes, rather than depth-first manner. Additionally, the vanilla method also carries the risk of being stuck in an isolated region with infinite iterations.
C.2 UPPER BOUND OF Importance FUNCTION
We theoretically analyze the Importance function by deriving the upper bound.
Assuming that ()) )) is trained unsupervised GraphSAGE, model with one layer, using a mean aggregator, let G be an input graph, and G, be a candidate explanatory subgraph for a target node E V where V is a list of nodes in G. When we consider the top-k neighbors for node the Importance of the subgraph GR can be bounded as follows:
Theorem 2
Importancee unssup (-), G, U,)),
Σ CagllMaggIlllCn Aull2))
[iop-Rl
where CLp is a Lipschitz constant vector for the activation function in the GraphSAGE, Magg is weight matrix that aggregates information from neighbors, and A, is the difference between the embedding vector fumsup (v) (i.e., emb,) before and after the perturbation.
Proof. Since the change of top-k nearest nodes in Importance is proportional the change of distance of top-k nearest nodes in the perturbed embedding vector, it is expressed as below:
Importance((fuspp D.G.G.,, |set(::N(eemb, k)) set( set(k:NN(embb' k))))
Σ
(dist(hv, hn) dist(h'' hi.))
(7)
Muppil Ve
14

---

Published as a conference paper at ICLR 2024
where hy means emby, hu means embu. h'v means emb',, h' means emb', after perturbation for abbreviation. The top-k nearest nodes Vop- is output from the kNN algorithm in the embedding space emb. The function dist(h,. h.)) is expressed as ||h, hull2 and we can define the upper bound of the importance using the Reverse triangle inequality below:
Idist(h,, h.)) dist(h' v. h' ..] = ||h, hull2 l|h', b'ull2
s s h.) (h', h',,lla
In inductive settings, we assume that hy is used in the same way as GraphSAGE (Hamilton et al., 2017) with single layer, where Msstr and Magg are trainable parameters, Xv is a feature of node No is a node set of node v's neighbors, and a indicates an activation function.
hy o MM MAgK
Σ U.N.
X.)
(9)
V
Next, we substitute hy from Equation into Equation ( This leads us to Equations [I and 12 obtained by canceling out the terms M and M under the premise that the node features remain unchanged. In Equation (7), we then obtain the upper bound by introducing CLp, which is referred to as the Lipschitz constant for the activation function. By applying the Cauchy-Schwand
inequality, we derive Equation (18). In this equation, A, represents the change in the embedding vector before and after perturbation, simplification made for the sake of brevity.
I1 - h.) -hh' -h',)l12
(10)
= =llo(Maarr(x -x,) + Magg
Σ PeNu
Σ xa)) quNu
(11)
[Nrll
Wall
-o(Msait(Xy xn) Mags
W'v
Σ
Xp
W qeN
Σ xa))ll2
(12)
PEA
= <Maoe
Σ Xp
Σ Xq
(13)
Nol peN.
Wil qeNu
1
W'
Σ p
Xp + W
Σ
x.) x)12
(14)
qeN"..
110 (Musse
(Nool peN.
Σ
Xp
[ PeN
1
Σ Xp
(15)
1
Σ Xx Wi'l Nil gEN,
Σ
xg x11)
(16)
qeNu'
$ CLp((IMaee (aaMa (A,, A.2)12))
(17)
$ CLpllMMaR MalMalllllllll - Aulla.
(18)
Theorem 2 establishes that the upper bound is influenced by the weight matrices Magg. A, and A... Assuming that the weight matrix Magg is fixed after training (i.e., in an inductive setting), we describe four cases of how the importance score can be changed. First, when A, and A, are small, the importance score becomes a low value. Second, when Ag is large but Au is small, the target vector is relatively changed even further, causing the importance score to become large. Conversely, A, is small, but A, is large, while the neighhoring nodes move to a different area, the target vector remains, leading vector v and its top-k neighboring nodes to move in the same direction, then the importance becomes small, but in the opposite direction, resulting in significant importance. Overall, the theoretical analysis suggests that the absolute value of importance is contingent on ||aaglle.
large importance score. Lastly, when both A, and A, large, causing the
15

---

Published as a conference paper at ICLR 2024
UNR-Explainer w/o restart
Ground truth
RW
1hop-3N
1hop-2N
UNR-Explainer
BA-Shapes
Tree-Cycles
Tree-Grid
Figure 5: The examples of obtained subgraphs by different models synthetic datasets.
D MORE EXPERIMENT RESULTS
D.1 QUALITIVE ANALYSIS OF SYNTHETIC DATASETS
We conduct a case study utilizing the ground truth of the synthetic datasets. As shown in Figure 5 the yellow node represents the target node, while the black nodes and edges are parts of the subgraph obtained by each baseline model. It is important to note that the grey nodes and edges represent the k-hop neighboring nodes of the target node in the input graph, providing relevant contextual information. The RW-G method generates path-shaped subgraphs that fail to reach the ground truth, particularly noticeable on the BA Ah-Shapes dataset. On the other hand, subgraphs generated by baselines such 1hop-3N and 1hop-2N are included in the ground truth but prove insufficient when the ground truth exists beyond a 1-hop distance. In contrast, both UNR-Explainer w/o restart and UNR-Explaine
more closely approximate parts of the ground truth. The difference between these two methods is not severe on small datasets, but generally, UNR-Explainer encourages the subgraph to have more connections centered around the target node. In conclusion, we illustrate how UNR-Explainer more accurately represents the ground truth, offering a superior explanation compared to other baselines.
D.2 DETAILS OF CASE STUDY
Detailed information nodes is described in Table
D.3 DESCRIPTION THE VARIANTS THE MCTS- ALGORITHM
In Table 6 describe the detailed information about variants of the MCTS- based algorithm presented in T4ble The term Action in Table refers to the design of the action in MCTS; Adding represents the addition of nodes, while Removing denotes the deletion of nodes. The Expansion refers to the design of the expansion strategy in MCTS. During child node expansion, All represents the expansion all neighboring nodes child nodes, while Sample means that we select nodes to match the average degree of the input graph from among the neighboring nodes, thereby reducing the search space. The term Restart indicates whether we apply our new selection policy, as explained in Section 3. The term UCB refers to the variant of the UCB formula (Eq. (3). Prx1, Prx2, and Prx3 represent different proximity measures. Prxl corresponds to the degree of node the input graph, assuming high-degree nodes are potentially more influential. Prx2 represents the number of common neighboring nodes the target node in the input graph, under the assumption that nodes with more common neighbors related to the target node potentially more influential. Prx3 corresponds to the cosine similarity between the current state node and the target node the imput graph, with the assumption that nodes with similar features are potentially more influential. However, these three
16

---

Published as a conference paper at ICLR 2024
Table 5: Description of nodes representing names of authors Figure
Node
Name
a
Caglar Gulcehr
b
Razvan Pascanu
C
Yann Dauphin
d
Yoshua Bengio
Guillaume Desjardins
f
Kyunghyun Cho
g
Surva Ganguli
h
Guido Montufar
1
Pieter Abbeel
j
Volodymyr Mnih
k
Koray Kavukcuoglu
1
John Schulma
m
Theophane Weber
Nicolas Heess
Table 6: Description of the variants of the MCTS-based algorithm in Table
We abbreviate the E as
(n(C(No.e)) due to the limiation of the space.
C(N.a)
No.
Name
Action
Expansion
Restart
UCB
MCTS
Adding
All
X
Avg(W + XE
SubgraphX-1
Removing
All
X
Agg(((N,,0) XE
3
SubgraphX-2
Removing
Sample
X
Avg(W(N,,a)) XE
MCTS-Avg
Adding
Sample
X
(NN.W)
X
5
MCTS-Prx1
Adding
Sample
Max(W (N, + Præl E
6
MCTS-Prx2
Adding
Sample
Max(W (()))))) Pra2
7
MCTS-Pro
Adding
Sample
Max(W (NN,W,, ())+)))+) Præ3 E
8
UNR-Explaings w/o
Adding
Sample
X
Max(W
9
UNR-Explainer
Adding
Sample
O
Ma,,W(N;,a)
proximity measures did not result in significant gains, contrary to our expectations, and increased the computational cost; as a result, none them are applied in our method.
Comparison with SubgraphX
The distinction between UNR- WuR-Exxlainer and SubgraphX is primarily discussed in terms of the reward function, action definition, and exploration strategy in MCTS. 1) The utilization of the reward function varies, as each is designed for distinct settings. SubgraphX employs the Shapley value in the reward function, which is not suitable for unsupervised settings without labels. On the other hand, our reward metric is specifically tailored to measure the importance of subgraphs in unsupervised settings. 2) The definition of action UNR-Explainer differs significantly from SubgraphX. In SubgraphX, the action involves pruning nodes from the input graph until the number of remaining nodes reaches a predefined threshold. This approach is problematic when the subgraph serves as a counterfactual explanation, as more computation is required to achieve the desired size. In contrast, the action in UNR-Explainer involves adding an edge to the candidate subgraph, a more efficient strategy for exploring minimal subgraphs. The efficiency of this action is demonstrated in Table which shows that SubgraphX-basee methods generate larger subgraphs and require more inference time. 3) We propose a new selection strategy, inspired by the Random walk restart, to promote more connections around the target node, suitable for our problem setting. 4) Moreover, we employ a sampling method during the expansion stage to reduce the computational cost of exploration. Consequently. UNR- Explainer is more efficient in searching for counterfactual explanatory subgraphs from the perspective of the MCTS-based algorithm.
17

---

Published as a conference paper at ICLR 2024
Table 7: The statisties of each dataset and the performance of the downstream tasks each dataset using trained unsupervised node representation vector.
Datasets
BA-Shapes
Tree- Pree-Cycle
Tree-Grid
# classes
4
2
2
# nodes
700
871
1,231
# edges
2,055
971
1,565
Model
GraphSAGE
GraphSAGE
GraphSAGE
Homogeneity
0.314
0.013
0.015
Silhouette
0.612
0.998
0.97
Task
node
node
node
ACC/AUC
0.486
0.583
0.587
Datasets
Cora
CiteSeer
Pubmed
# classes
7
6
3
# nodes
2,708
3,312
19,717
# edges
5,429
4,732
44,338
Model
GraphSAGE
GraphSAGE
DGI
Homogeneity
0.471
0.215
0.006
Silhouette
0.177
0.160
0.073
Task
link
node
node
ACC/AUC
0.909
0.830
0.695
D.4 TIME COMPLEXITY ANALYSIS
Let / be the number of iterations, n be the number of nodes in the search tree, [V] be the number of vertices in our input graph G. the time complexity of our UNR- -NN--xxlainer w/o restart in an inductive setting mainly depends on O(t-log(r)) (1) (V)..V().. Additionally, the O(IV)) is required for the kNN function due to the simulation. When we employ UNR-Explainer for selection, due to the probability of the restart Prestart, the time complexity for the search is Onn) in the worst case. Therefore, the total time complexity to search the important subgraph as the explanation for the target node is O S(t-n-1p IVD) In the worst case, if approaches [V/, the complexity could become approximately O(VV²). To circumvent this situation, there are two strategies: establishing stopping criteria and setting an upper stopping criterion, or the traversal is stopped when case
bound for Firstly, t is set to 1,000 meeting Importance = 1.0 is found. Secondly, the number nodes in the traversal graph limited to constant value; in this paper, we set it to 20. Moreover, in every iteration, nodes for the expansion step. which helps avoid the exponential expansion n. For these reasons, the time complexity of UNR-Explainer is approximately O(VV), because both and n could be regarded as constants.
sample most
D.S EXPERIMENTAL SETUP
To evaluate proposed explanation method, we first train the unsupervised node representation model using GraphSAGE (Hamilton et al. 2017) and DGI (Veličković et al. 2018). 'he resulting trained embedding vector is then used for downstream tasks such link prediction and node classification. For the node classification task, we use the synthetic datasets and divide the embedding vector into random train and test subset with 80% and 20% of the data, respectively. For the real-world datasets, we perform the link prediction task, so we split the edges of the graph into random train and test subsets with 90% and 10% of the data. Top-k link prediction is evaluated by the AUC. A logistic regression model is employed for both the node classification and the performance is evaluated by calculating the accuracy for node classification.
Additionally, to assess the quality of the initial embeddings, we report Homogeneity using labels and Silhouette Coefficient without labels, which are commonly used in clustering tasks. The homogeneity measures how instances with the same labels are contained in the same cluster, and the number of clusters is set equal to the number of classes. The Silhouette Coefficient measures how well separated each cluster is. Higher values of homogeneity and Silhouette Coefficient indicate better performance of the clustering model The above experimental setup is described in Table (7) Noteworthly, we set for top-k neighbors 5, the exploration term À as 1, and Prestart 0.2.
18

---

Published as a conference paper at ICLR 2024
D.6 IMPLEMENTATION DOWNSTREAM TASKS
Using the trained embedding vector in unsupervised learning, we conduct the node classification task. The logistic regression model in Scikit-learn is used. We set the max iter as 300.
Node classification:
Link prediction:
Using the trained embedding vector in unsupervised learning, conduct the link prediction task. We split the graph to generate the train and test dataset using WTToch-GGeometrt (Fey & Lenssen 2019). To predict the link between two nodes, assume there is a link between the target node and its top-k nearest nodes.
D.7 IMPLEMENTATION OF UNSUPERVISED NODE REPRESENTATION MODELS
We employ the GraphSAGE (Hamilton al. 2017 and DGI Vellckovic et al. 2018) model to demonstrate the performance of our proposed method in the inductive setting. We note that the GraphSAGE model and DGI are implemented using the Py PyTorch geometric Fey & Lenssen (2019).
The detailed information is as below:
GraphSAGE (Hamilton al. 2017) We use the aggregating operator follows: x/ M Magg je X,- Here, while x means node features, Mself and Magg are the trainable parameters, and M represents local neighboring nodes around node i. We set the hyperparameters as follows: the batch size as 256, the number of hidden dimensions as 64, the number of hidden layers as the dropout as 0.5, and the optimizer as Adam. On BA-shapes, we set the number of epochs as 100 and the learning rate as 0.01. On other datasets, we set the number of epochs as150 and the learning rate as 0.01.
DGI (Veličković et al. 2018): We use the GraphSAGE as the encoder of the DGI model, setting the number hidden dimensions as 512, batch size as 256, the number of hidden channels as 512, the number of hidden layers as 2, dropout 0.5, the number of epochs as 50, optimizer as Adam, and the learning rate as 0.001.
D.8 BASELINES IN UNSUPERVISED LEARNING
Taxonomy Induction (Liu et al. 2018): We implement the model using the code and the setting of hyperparameters from the authors in Matlab. We the number of clusters as 50 for all real-world datasets and 5,3, 2 for BA-Shapes, Tree-Cycles, and Tree-Grids respectively.
TAGE (Xie et al. 2022): Since TAGE is available to provide the explanation for the embedding vector, we do not utilize the second stage which connects to the downstream task MLP to evaluate the explainer in unsupervised manner. We set the number of epochs as 100, the learning rate as 0.0001, k as 5, the gradient scale as 0.2, Ay as 0.05, and A as 0.002. The implementation is followed by (Xie et al. 2022
D.9 PACKAGES REQUIRED FOR IMPLEMENTATIONS
python 3.9.7
pytorch 1.13.1
pytorch-cluster == 1.6.0
Pyg = 2.2.0
pytorch-scatter = 2.1.0
pytorch-sparse 0.6.16
cuda = 11.7.1
numpy 1.23.5
tensorboardx = 2.2
networkx = 3.0
scikit-leam == 1.1.3
seipy = 1.9.3
pandas 1.5.2
19

---

Published as a conference paper at ICLR 2024
E LIMITATION, FUTURE WORK, AND NEGATIVE SOCIETAL IMPACTS
We focus primarily on providing counterfactual explanations for unsupervised node representation models. However, it's important note that actionability and diversity are also key properties to consider in these explanations. A well-known example of counterfactual explanations is the case of credit application prediction discussed in (Verma al. 2020p. Counterfactual explanations offer more than mere output explanations; they also provide actionable recommendations, especially when a loan application is rejected, Additionally, providing multiple explanations enhances the diversity of possible actions, thereby allowing applicants to select the most suitable options. However, defining the desired action in unsupervised settings is challenging. Since the desired action closely linked to the problem settings and datasets, specific assumptions. akin to the loan application example, are required. Therefore, we leave the exploration of actionability and diversity in counterfactual explanations for unsupervised models future work. As of the current stage of our research, have not recognized any negative societal impacts associated with this work.
20


Reviews:
[{"review_id": "8qXxxq6QIR", "reviewer": "Reviewer_eAe7", "summary": "This work explores explanation generation for unsupervised node representation learning.  The authors propose a Monte Carlo Tree Search (MCTS)-based method to generate counterfactual (CF) explanations. Specifically, this method aims to identify the most important subgraphs that cause a significant change in the k-nearest neighbors of a node. The proposed method is incorporated into unsupervised GraphSAGE and DGI, and the performance on six datasets confirms the efficacy of the proposed method.", "questions": "1. Why do the authors choose the MCTS-based framework rather than other gradient-based or causal-based interpretable methods? Can you show the relevant analyses?\n2. Can the authors state what new challenges your approach addresses compared to existing counterfactual explanation methods on supervised learning?\n3. Can the author give some applications of real-world scenarios or do some pilot studies to show the benefit of the perturbation strategy of only removing edges?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is an interesting research topic to improve the interpretability of unsupervised learning models on graphs. \n2. This can help to find the explanations of  GNN models with unseen downstream tasks.\nThe proposed method is tested on several datasets and shows satisfactory results.\n3. The paper is well-structured and organized.", "weaknesses": "1. The work is somehow incremental work. SubgraphX proposed a Monte Carlo tree search algorithm to efficiently explore different subgraphs. Compared with SubgraphX, the authors seem to just add a new policy, “restart”, in the Selection step to mitigate the search bias. The design makes sense but results in limited novelty.\n2. The indicators of counterfactual explanations are not rigorous. The perturbations of the input graph not only change the node embedding of interest ($emb_{v} \\neq emb_{v}^{'}$) but also change other node embeddings. It does not match the Figure 1 (b) and (c) illustrated.\n3. The motivation should be further improved. The authors do not state the challenges of generating counterfactual explanations in unsupervised learning compared with supervised methods, such as CF-GNNExplainer, RCExplainer, and CF2.\n4. The authors do not provide real-world applications or pilot studies to support their claim that \"the perturbation strategy of adding edges or nodes has a significant risk in real-world scenarios\"\n5. Minor error: Page 9 The first line is not left-justified; Measures in Table 1 are not arrowed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VeDgHeveH3", "reviewer": "Reviewer_8JCL", "summary": "The paper introduces a novel method for explaining graph neural networks. The authors focus on counterfactual explanations and propose the UNR-Explainer, which aims to identify subgraphs that, when perturbed, lead to significant changes in node embeddings. The paper evaluates various explanation methods in unsupervised settings using synthetic and real-world datasets. The proposed method leverages the Monte Carlo Tree Search (MCTS) for efficient traversal in large search spaces. The paper also provides a theoretical analysis of the upper bound of Importance and discusses the algorithm for calculating Importance.", "questions": "1)\tHow does the method scale with larger and more complex graphs? Are there any computational or memory constraints that might limit its applicability to very large datasets?\n2)\tHow sensitive is the method to the degree of perturbation applied to the subgraph? Would minor changes in perturbation lead to significantly different results in the algorithm of importance?\n3)\tGiven the contrastive approach employed by DGI and the inductive learning capability of GraphSAGE, how might these characteristics influence the types of counterfactual explanations generated? Furthermore, how would the proposed counterfactual explanation method adapt and perform when integrated with generative models such as GraphGAE or S2GAE?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1)\tThe paper tackles CF reasoning in unsupervised settings, a relatively unexplored area potential implications for explainability in graph neural networks and unsupervised learning.\n2)\tThe paper leverages the Monte Carlo Tree Search (MCTS), a technique from reinforcement learning, to efficiently traverse the search space of potential subgraphs. MCTS is known for its effectiveness in large search spaces, making it a suitable choice for this problem.\n3)\tThe paper clearly defines the counterfactual property for unsupervised representation learning models, providing a solid foundation for their method.\n4)\tThe paper includes a theoretical analysis of the upper bound of Importance for GraphSAGE, adding a rigorous foundation to their empirical findings.", "weaknesses": "1)\tWhile the paper does evaluate on both synthetic and real-world datasets, it might benefit from testing on more diverse datasets, especially those from different domains or with different characteristics. Information on how the method scales with larger datasets or more complex graphs, and its computational efficiency, would be valuable.\n2)\tI believe the paper would greatly benefit from additional visual illustrations or diagrams to depict the proposed method. Visual aids can provide a clearer understanding and offer readers an intuitive grasp of the methodology. Given the complexity and novelty of the approach, diagrams or flowcharts could enhance comprehension and make the content more accessible to a broader audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qi4fBjHFhU", "reviewer": "Reviewer_TnSw", "summary": "The paper proposes a method called UNR-Explainer for generating counterfactual explanations in unsupervised node representation learning models. The goal of these explanations is to provide information for understanding unsupervised downstream tasks. UNR-Explainer performs Monte Carlo Tree Search to find the explanation subgraph. The subgraph importance is measured by the change of the top-k nearest neighboring nodes after perturbation. UNR-Explainer is evaluated on six datasets including both synthetic ones and real-world ones, and UNR-Explainer is shown to outperform existing explanation methods.", "questions": "1. In Table 1 for the synthetic datasets, the naive random selection baselines 1hop-2N and 1hop-3N achieve the best results in terms of precision. Why? Any discussions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. UNR-Explainer shows the good quantitative performacne, and the case study on NIPS shows UNR-Explainer can select qualititatively meaningful subgraphs.\n\n2. The importance metric proposed in Equation 1 is novelt to me.\n\n3. Time complexity analysis and discussion of limitation are both included in the appendix.\n\n4. Code is provided for reproducibility.", "weaknesses": "1. Lacking discussions. Some baseline methods considered in the experiment section are very simple but achieve strong performance without discussion or analysis. See question 1 as well.\n\n2. Efficiency. MCTS-based explanation can be slow than other explanation methods, e.g., gradient-based methods, especially on large graphs. This is verified by the time complexity as well.\n\n3. Presentation can be further improved. Some figures have text that is too small to read. For example, embedding labels in figure 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QHHAVfQgXz", "reviewer": "Reviewer_WfpS", "summary": "The authors introduce a new method to obtain counterfactual (CF) explanations from unsupervised node learning. Their method uses a learned unsupervised node learning method to get embeddings. They then define their method via the importance function which they try to maximize while minimizing the edge alterations to the graph (minimizing the counterfactual explanation). They provide an upper bound on the Importance function. \n\nThey alter a Monte Carlo Tree Search (MCTS) method to get the CF. The MCTS uses the Importance function as a reward which looks for subgraphs that are important but sparse. They show that their MCTS does not degrade the expressiveness of subgraph explanations like the vanilla MCTS would by altering the reward function. They do this by choosing the action where the upper confidence boundary (UCB a term used in their MCTS which dictates which edge to take in traversal) is larger. They also show analysis showing that the UCB for an edge that leads to a new node is greater thus prioritizing exploring new paths. They claim these alterations to the vanilla MCTS leads to more expressive explanations which are partially supported by theoretical claims. \n\nThey also have quite a large and expansive set of experiments. They do experiments on 3 synthetic datasets (BA-Shapes, Tree-Cycles, and Tree-Grid) and 3 real datasets (Cora, CiteSeer, and PubMed), parameter sensitivity study, ablation study and a case study. They conduct their experiments on 8 methods (including theirs) on several metrics: Precision/Recall, Validity, size of the model and Importance. They show promising behaviour of their method in comparison to other methods in many settings with various evaluation metrics. They also show a case study on the NIPS dataset a social network of citations. They show by perturbing explanation graphs on a particular author they can obtain a graph that belongs to a different author that belongs to a different subfield of ML. They also conduct an ablation study showing variants of the MCTS algorithm which is fundamental to their methodology. They show their variant of MCTS can find expressive explanations (high importance score) while being efficient. Finally they also show experiments of parameter sensitivity. They show what effects the choice of the restart parameter, perturbation parameter, and the number of neighbors has on their method. They do this by varying the choice of hyperparameter and evaluating the importance score on the Cora Dataset.", "questions": "Although the authors provided a study of hyperparameter sensitivity, why did they select k=5. Clearly, as seen in the experiments the choice of k does seem to impact the importance score. More discussion of the effect of the choice of k would be beneficial for practitioners. \n\nAlso their method seems to underperform in the synthetic experiments particularly with the precision measure. Significantly smaller methods do better than UNR-Explainer in these settings which is seemingly consistent throughout the synthetic experiments. Any discussion as to why this is would be beneficial to readers and the authors.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well written. The design of the paper from problem definition, to methodology, to experimental evaluation follows clearly and is well designed. The authors also motivate their work by addressing the problem in a well defined manner. The Importance measure is novel and inventive way to quantify the counterfactual explanation. The alterations to the MCTS to construct these counterfactual explanations is reasonable and well grounded by theory to supplement their decisions. The paper also employs theory on the Importance measure to show an upper bound. \n\nThe experimental list is fairly exhaustive and shows superior performance to several other methods in multiple datasets and cases. The case study is a nice touch to display their method’s ability to obtain meaningful counterfactual explanations. The ablation study shows that their variant of MCTS can find expressive subgraphs while being efficient in comparison to other tree search methods. Finally, having a study to show their methods sensitivity/robustness to choices of hyperparameters is important for anyone seeking to employ this method.", "weaknesses": "There could be more discussion on experiments where the UNR-Explainer underperforms compared to other methods. \n\nAlso further explanation on certain hyperparameter choices could be made more clear for the readers. Such as the choice of k in each experimental setting. A discussion on when to use a particular larger/smaller value of k would be interesting. The authors do have experiments showing the sensitivity of the number of neighbors, they also have a limited discussion on this phenomenon. However this hyperparameter is central to their method (their importance measure is heavily influenced by it) a discussion to explain what settings would require very large k vs very small k would be beneficial to solidify their work although it is not necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)