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

Response to Reviewer WfpS

We sincerely appreciate your valuable feedback for reviewing this paper. For the potential concerns you bring up, we would like to address them as follows. ### **W1 \& Q2: Clarity of disscusion** Thank you for your constructive comment. In the BA-Shape dataset, there are 80 house-structured motifs, each comprising 5 nodes, which are considered the correct answers. Only a few edges in these motifs are connected to the base BA graph. In our experiments, we focused on evaluating the performance of explanation generation for nodes within these house motifs. In such cases, when employing 1hop-2N and 1hop-3N for searching explanations, 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, 1hop-2N and 1hop-3N exhibit high precision but low recall. ### **W2 \& Q1: More discussion of choosing $k$** Thank you for your valuable question. In this paper, $k=5$ was chosen as a hyper-parameter because it performed well on average across evaluation measures such as importance, fidelity, and validity. However, we acknowledge that practitioners might select different values for $k$ depending on the desired level of interpretation. Specifically, $k$ is closely associated with the detail of the generated explanation and the number of hops, so its selection may vary based on the domain expert's judgment. For instance, in a social network analysis, a $k$ value close to the average node degree may be suitable for explanations focusing on immediate connections, such as close friends. Conversely, for understanding important local clusters, a higher $k$ might be more appropriate. This decision can be informed by domain knowledge.

Response to Reviewer TnSw

We sincerely appreciate your valuable feedback for reviewing this paper. For the potential concerns you bring up, we would like to address them as follows. ### **W1 \& Q1: Improving discussions** Thank you for your constructive comment. In the BA-Shape dataset, there are 80 house-structured motifs, each comprising 5 nodes, which are considered the correct answers. Only a few edges in these motifs are connected to the base BA graph. In our experiments, we focused on evaluating the performance of explanation generation for nodes within these house motifs. In such cases, when employing 1hop-2N and 1hop-3N for searching explanations, 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, 1hop-2N and 1hop-3N exhibit high precision but low recall. ### **W2: Addressing efficiency** Thank you for raising this important point. UNR-Explainer has a time complexity of $O(t \cdot n \cdot |V|)$, where $t$ is the number of iterations, $n$ is the number of nodes in the search tree, and $|V|$ is the number of nodes in the input graph. In the worst case, if $n$ approaches $|V|$, the complexity could become approximately $O({|V|}^2)$. To circumvent this situation, there are two strategies: establishing stopping criteria and setting an upper bound for $n$. Firstly, $t$ is set to 1,000 as a stopping criterion, or the traversal is stopped when a case meeting $Importance = 1.0$ is found. Secondly, the number of nodes in the traversal graph is limited to a constant value; in this paper, we set it to 20. Moreover, in every iteration, we sample at most 3 nodes for the expansion step, which helps avoid the exponential expansion of $n$. For these reasons, the time complexity of UNR-Explainer is approximate $O(|V|)$, because both $t$ and $n$ could be regarded as constants. While most gradient-based methods (e.g., PG-Explainer [1]) have the time complexity of $O(|E|)$, where $|E|$ is the number of edges in the input graph, the complexity of UNR-Explainer could be more efficient than these methods, especially when the input graph is dense. In addition to addressing the time complexity issue, the MCTS-based framework finds the explanation subgraphs, which are mostly connected. In contrast, gradient-based methods such as PG-Explainer [1] incorporate a connected loss term in their objective term to achieve connectedness. Despite this, they often fail to consistently generate connected subgraphs, as the additional regularization term does not guarantee generating connected subgraphs. **Reference** [1] Luo, Dongsheng, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. "Parameterized explainer for graph neural network." Advances in neural information processing systems 33 (2020): 19620-19631. ### **W3: Enhancing presentations** Thanks for your valuable feedback. We revised all figures to improve the presentation of our paper.

Response to Reviewer 8JCL [1/2]

We sincerely appreciate your valuable feedback for reviewing this paper. For the potential concerns you bring up, we would like to address them as follows. ### **W1 \& Q1: Addressing scalability** Thank you for raising this important point. Scalability is an important factor to be considered particularly in real applications on very large graphs. As a matter of time complexity, UNR-Explainer has a time complexity of $O(t \cdot n \cdot |V|)$, where $t$ is the number of iterations, $n$ is the number of nodes in the search tree, and $|V|$ is the number of nodes in the input graph. In the worst case, if $n$ approaches $|V|$, the complexity could become approximately $O({|V|}^2)$. To circumvent this situation, there are two strategies: establishing stopping criteria and setting an upper bound for $n$. Firstly, $t$ is set to 1,000 as a stopping criterion, or the traversal is stopped when a case meeting $Importance = 1.0$ is found. Secondly, the number of nodes in the traversal graph is limited to a constant value; in this paper, we set it to 20. Moreover, in every iteration, we sample at most 3 nodes for the expansion step, which helps avoid the exponential expansion of $n$. For these reasons, the time complexity of UNR-Explainer is approximately $O(|V|)$, because both $t$ and $n$ could be regarded as constants. While most gradient-based methods (e.g., PGExplainer [1]) have the time complexity of $O(|E|)$, where $|E|$ is the number of edges in the input graph, the complexity of UNR-Explainer could be more efficient than these methods, especially when the input graph is dense. **Reference** [1] Luo, Dongsheng, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. "Parameterized explainer for graph neural network." Advances in neural information processing systems 33 (2020): 19620-19631. ### **W2: Providing overview of UNR-Explainer** Thank you for your suggestion. We attached the figure describing an overview of UNR-Explainer in a revised version of our paper and attached [link](https://anonymous.4open.science/r/unr0929/overview.jpg). ### **Q2: Addressing sensitivity of perturbation effect** Thanks for your valuable question. As demonstrated in our additional experiments, the sensitivity of the $Importance$ measure in UNR-Explainer varies with different perturbation rates (details available at this [link](https://anonymous.4open.science/r/unr0929/perturbation_param.jpg). Specifically, when the perturbation parameter lies between 0.0 and 0.3, there is a gradual decline in $Importance$ observed on the Cora and CiteSeer datasets. However, for perturbation parameters exceeding 0.4 — implying that 40% or more of messages that ought to be weakened are retained — the effectiveness of the perturbation is reduced, leading to a lower $Importance$.

Response to Reviewer 8JCL [2/2]

### **Q3-1: Addressing analysis of explanations by models as GraphSAGE vs DGI** Thanks for bringing up this question. In general, UNR-Explainer yields explanations of varying sizes when used with different node representation models such as GraphSAGE and DGI. Specifically, explanations under the GraphSAGE model average 4.5 nodes and 3.8 edges, while those under DGI average 3.9 nodes and 3.1 edges. Typically, GraphSAGE-generated explanations include more distant nodes and a greater number of connections in the input graph compared to DGI. We have provided visualizations of these explanations via this [link](https://anonymous.4open.science/r/unr0929/cora-gs-dgi.jpg). In Case 1, the explanations under GraphSAGE and DGI are common, while in Case 2, although the overall structure of the explanations is similar, the GraphSAGE explanation includes an additional node at a 2-hop distance from the target node. This trend is even more pronounced in Case 3. We hypothesize that this difference may be attributed to the methods used for defining positive and negative samples during training. GraphSAGE treats nodes near a target node on a fixed-length random walk as positive samples, as implemented in [pytorch-geometric](https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/loader/link_neighbor_loader.html#LinkNeighborLoader) with settings [10, 10]. Conversely, DGI employs a corruption function that randomly permutes node features while keeping the edge index constant to generate negative samples. This broader range of positive samples in GraphSAGE could influence UNR-Explainer to generate explanations that encompass more distant nodes and edges. ### **Q3-2: Adapting UNR-Explainer to explain generative models** Thank you for your insightful question. Graph Auto Encoders (GAE), such as VGAE [1] and S2GAE [2], are prominent in generation-based unsupervised and self-supervised learning on graphs. These models typically consist of two components: an encoder, which is a graph neural network producing latent representations, and a decoder, which reconstructs the input graph using these representations. The latent representation, containing implicit information, is crucial for downstream tasks like node and graph classification, where GAE models demonstrate superior performance. Hence, there is a significant demand for explaining these models in real-world applications. UNR-Explainer can be adapted to explain the encoder of GAE-based models like VGAE and S2GAE. This compatibility arises mainly because UNR-Explainer provides node-level explanations, aligning well with the output of the node-level embedding by the encoders in these models. Moreover, UNR-Explainer's ability to provide explanations without relying on class labels makes it potentially suitable for self-supervised learning models. However, adapting UNR-Explainer to GAE models involves defining explanations for generation-based GAEs and designing appropriate experimental settings, especially evaluation metrics. Additionally, the specific processes of each model must be considered. For instance, in VGAE [1], we need to control the randomness of the reparameterization trick to assess the perturbation effect accurately. In the case of S2GAE [2], which uses edge-masking and direction-aware graph masking, these perturbation methods may conflict with UNR-Explainer's perturbation process, necessitating additional adjustments. Moreover, since UNR-Explainer is designed to explain models with only an Encoder part, adapting it to generative models with a Decoder part would require further methodological considerations. To our knowledge, explainability for generative models on graphs is one of the less explored areas in research. We are grateful for your question, as it highlights an exciting direction for our future research endeavors. **Reference** [1] Kipf, Thomas N., and Max Welling. "Variational graph auto-encoders." arXiv preprint arXiv:1611.07308 (2016). [2] Tan, Qiaoyu, Ninghao Liu, Xiao Huang, Soo-Hyun Choi, Li Li, Rui Chen, and Xia Hu. "S2GAE: Self-Supervised Graph Autoencoders are Generalizable Learners with Graph Masking." In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 787-795. 2023.

Response to Reviewer eAe7 [1/3]

We sincerely appreciate your valuable feedback for reviewing this paper. For the potential concerns you bring up, we would like to address them as follows. ### **W1: Addressing novelty** Thank you for raising the important question. We acknowledge that our method is not the first to implement Monte Carlo Tree Search (MCTS) in the graph XAI (Explainable Artificial Intelligence) domain. Prior works, such as RationaleRL [1] and SubgraphX [2], have utilized MCTS in their problem settings, each with a reward function tailored to their specific objectives. However, applying existing MCTS frameworks directly to unsupervised node learning models is challenging. The difficulty lies in defining suitable rewards and managing the increased uncertainty in exploring the graph space. To mitigate the challenges, we propose a new procedure that is different from the existing MCTS framework with respect to five key aspects. The distinctions between our model and SubgraphX are summarized in the table below. First, our $Importance$ function shown in Equation (1) of our main text quantifies the change of top-k neighbors in the embedding space after perturbation, bringing up the benefits of recognizing the significant influence of important subgraph $G_s$ in related downstream tasks. Thus, our contribution not only relies on developing the proper design of MCTS for counterfactual explanations but also sheds light on explaining unsupervised node representation learning. For clarification, we describe the difference between SubgraphX and UNR-Explainer regarding to the design of MCTS as below: | Design criteria | SubgraphX | UNR-Explainer | |------------------------|--------------------|--------------------------------| | Target model | supervised models | unsupervised models | | Reward function | Shapley value | Importance function in Eq. (1) | | Action | to prune | to add | | Selection | argmax | random walk with restart | | Expansion | without sampling | with sampling | | Action value | mean | max | Consequently, our design of Monte Carlo Tree Search (MCTS) in UNR-Explainer reduces the computational time by 97.37\% as [(4.64 - 176.3) ÷ 176.3] ×100 and performance increased by 1.9\% as [(0.96 - 0.42) ÷ 0.942] ×100 in the Table 4 of our paper, compared to SubgraphX-1. The significant improvement in the computational cost indicates the emphasis on MCTS design to tailor its problem settings. To avoid costly and unnecessary exploration, we propose a suitable MCTS framework for counterfactual explanations in unsupervised settings. Additionally, the new selection strategy and reward functions are theoretically analyzed with respect to the bounds of value and expressiveness, respectively. **Reference** [1] Jin, Wengong, Regina Barzilay, and Tommi Jaakkola. "Multi-objective molecule generation using interpretable substructures." In International conference on machine learning, pp. 4849-4859. PMLR, 2020. [2] Yuan, Hao, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. "On explainability of graph neural networks via subgraph explorations." In International conference on machine learning, pp. 12241-12252. PMLR, 2021. ### **W2: Clarity of Figure 1** Thank you for your thoughtful comments. For brevity, we have simplified the counterfactual explanations in Figure-1 (b) and (c). As indicated, when edges near the node of interest are perturbed, the neighboring nodes' positions are affected. In contrast, nodes that are distant from the node of interest, but share structural similarities and similar feature distributions, will maintain their original embeddings unchanged. We have updated the figure to better illustrate this distinction in a revised version of our paper.

Response to Reviewer eAe7 [2/3]

### **W3 & Q2: Addressing motivation** Thank you for pointing this out. UNR-Explainer is designed to generate counterfactual explanations in unsupervised learning contexts without relying on labels, contrasting with XAI methods in supervised learning. We highlight the limitations of existing methods when applied to unsupervised learning: - CF-GNNExplainer [1] as a pioneer of counterfactual explanation for the graph domain enhances explainability. Its loss function is formulated as $L = L_{pred}(v, \bar{v}| f, g) + βL_{dist}(v, \bar{v} | d)$, where $v$ is the original node and $\bar{v}$ is generated by the CF model. In this function, $f$ represents a predicted class label, and $g$ is the counterfactual (CF) model generating $\bar{v}$. The term $L_{pred}$ denotes a counterfactual loss ensuring $f(v) \neq f(\bar{v})$, while $L_{dist}$ quantified the distance between the input graph and the found explanation. However, as indicated in Definition 2 of our paper, the condition $f(v) \neq f(\bar{v})$ in supervised settings can be analogous to $emb_{v} \neq emb_{v}^{\prime}$ in unsupervised learning. Yet, $emb_{v} \neq emb_{v}^{\prime}$ alone provides limited information for determining the importance of each edge. To address this and aid in generating beneficial explanations for related downstream tasks, we introduce a novel $Importance$ measure for counterfactual explanation in unsupervised node representation learning. - RCExplainer [2] tackles the robustness of counterfactual explanations by leveraging the decision boundaries of a GNN in supervised settings. However, the decision region in [2] heavily relies on class labels, making it unsuitable for unsupervised settings where class labels are absent or when no specific downstream tasks are defined. - CF2 [3] combines factual and counterfactual explanations to address the limitations of each approach. However, the process for generating explanations in CF2, as defined in Equations (10), (11), and (12) in [3], also depends on class labels for graph/node classification. This reliance makes direct application to unsupervised settings challenging. In conclusion, UNR-Explainer provides insights into counterfactual explanations in unsupervised settings without relying on class labels. It offers the advantage of describing potential impacts on related downstream tasks, such as link prediction and clustering. **Reference** [1] Lucic, Ana, Maartje A. Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. "Cf-gnnexplainer: Counterfactual explanations for graph neural networks." In International Conference on Artificial Intelligence and Statistics*, pp. 4499-4511. PMLR, 2022. [2] Bajaj, Mohit, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. "Robust counterfactual explanations on graph neural networks."Advances in Neural Information Processing Systems 34 (2021): 5644-5655. [3] Tan, Juntao, 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." InProceedings of the ACM Web Conference 2022*, pp. 1018-1027. 2022.

Response to Reviewer eAe7 [3/3]

### **W4 \& Q3: Addressing real-world scenario** Thank you for your invaluable question. We address the potential risks inherent in explainability techniques, particularly those involving modification methods like adding new nodes or edges, in real-world scenarios. In the context of social network graphs, an explanation graph generated by allowing the addition of nodes to a subgraph (used for explaining link prediction or clustering) might include nodes that are not actually observable. For example, it may suggest connections with individuals who have never met, rendering the explanation invalid for the end-user. Similarly, in citation graphs, if the explanation for link prediction includes a non-existent citation subgraph, it becomes challenging to interpret. When learning from the molecule datasets for drug discovery, permitting the addition of numerous nodes can lead to significant deviations from [chemical valency rules](https://en.wikipedia.org/wiki/Valence_(chemistry)). Such alterations could render the explanations not only inaccurate but also impractical for practical applications. To circumvent these issues, our approach emphasizes the removal of important connections to provide counterfactual explanations. This method ensures that the explanations remain grounded in the actual structure of the dataset, thereby enhancing their validity and applicability. ### **W5: Rectifying minor error** Thank you for your thoughtful comment. We revised this issue in the current version of our paper. ### **Q1: Rationale for MCTS** Thank you for raising the important question. Our approach offers several advantages over gradient-based or causal-based interpretable methods. Firstly, unlike gradient-based methods such as PG-Explainer [1], which attempt to ensure connectedness through a connected loss term but often fail to guarantee connected subgraphs, our MCTS-based framework reliably identifies exploratory subgraphs that are connected. This is because the additional regularization term in gradient-based methods does not consistently lead to connected subgraphs. Secondly, our objective function is not a differential equation, setting it apart from gradient-based methods. While SubgraphX [2] employs the Shapley value for the importance measurement in its MCTS framework, our $Importance$ measure quantifies the change in the k-nearest neighbor nodes after perturbation, making our MCTS-based approach more suitable for exploring significant subgraphs in unsupervised settings. As for causal-based methods like GEM [3] and OrphicX [4], they rely on structural causal models (SCM), which are predominantly based on the assumption of existing class labels. Developing a causal-based model for explaining embedding vectors in unsupervised settings is an intriguing area for future research. However, in the absence of external SCM models, our method solely relies on our $Importance$ function to provide explanations in unsupervised settings. **Reference** [1] Luo, Dongsheng, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. "Parameterized explainer for graph neural network." Advances in neural information processing systems 33 (2020): 19620-19631. [2] Yuan, Hao, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. "On explainability of graph neural networks via subgraph explorations." In International conference on machine learning, pp. 12241-12252. PMLR, 2021. [3] Lin, Wanyu, Hao Lan, and Baochun Li. "Generative causal explanations for graph neural networks." In International Conference on Machine Learning, pp. 6666-6679. PMLR, 2021. [4] Lin, Wanyu, Hao Lan, Hao Wang, and Baochun Li. "Orphicx: A causality-inspired latent variable model for interpreting graph neural networks." In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13729-13738. 2022.