Disentangled and Self-Explainable Node Representation Learning

We gratefully thank the reviewer for the insightful comments provided in the review. For clarifications on the proposed evaluation metrics and key desiderata, please refer to the first global response. Here we provide detailed answers to the specific concerns.

1. Evaluation metrics: We hope that our global response on clarification of metrics has already resolved your concerns. Specifically, the AUC that you mentioned is the AUC score used by GNNexplainer for computing alignment of explanations with human perceived ground-truth explanations. Our Comprehensibility metric already serves a similar purpose, using another classification metric –F1– instead of AUC as the evaluation criterion. F1 is stricter in the sense that AUC can provide exaggerated scores for small sized explanations (i.e. the task of detecting small subgraphs is inherently highly imbalanced).

2. Enhancing human-interpretability: As detailed in our global response, we use plausibility to assess how well our explanations align with human reasoning and also point to its difference with Comprehensibility. Similar to GNNExplainer, we evaluate on synthetic datasets with planted subgraphs, which serve as ground-truth human rationales for explaining specific node labels. Our results in Appendix A.6.3 demonstrate that the most important embedding dimension identified by the downstream classifier consistently aligns with the true explanation subgraph. Additionally we add visualisations of the found explanations in Figure A7 of the Appendix. While this marks a significant step towards human-centric evaluation, conducting studies with actual human participants is beyond the scope of this work due to the substantial resources required. Moreover, designing effective human evaluation protocols remains a challenging research problem in itself. We view this as an important direction for future research and are optimistic that our proposed metrics provide a strong foundation for advancing human-in-the-loop evaluations.

3. Stronger baselines: We would like to clarify that the methods mentioned by the reviewer are not inherently interpretable and, therefore, do not serve as direct competitors to DiSeNE. Instead, DiSeNE is designed to complement existing unsupervised learning approaches by making their embeddings interpretable. To further highlight the versatility and effectiveness of DiSeNE, we are actively incorporating additional unsupervised learning methods into our framework—not as a comparison for competition, but to demonstrate the broad applicability and impact of the interpretability enhancements it provides. While these enhancements will be continuously added to our GitHub repository as part of an ongoing effort, they are beyond the scope of the current submission and will not affect the core contributions presented here.

4. Visualization of explanations: We appreciate the reviewer’s suggestion to enhance the clarity of the exposition through visualizations. We have included in Appendix A.5.1 a visualization of the explanation subgraphs in a simple scenario to highlight how the disentanglement helps extract more interpretable graph structures. Specifically, Figure A2 illustrates how various embedding methods can be interpreted once trained on the synthetic BA-Cliques dataset, where each dimension-specific subgraph is highlighted in a different panel. From the figure, it is evident that for DeepWalk and GAE the subgraphs exhibit significant overlap, which can be attributed to non-zero correlations between the latent features. In contrast, the uncorrelated features of DiSeNE produce distinct, non-overlapping explanations. Moreover, in Figure A7 (and related Appendix section) we report local explanations for binary node classification, comparing DiSeNE with well-established graph explainers, showing again competitive performance in highlighting the important sub-structures.

5. Please refer to Point 3.

We gratefully thank the reviewer for the insightful comments provided in the review. For clarifications on the proposed evaluation metrics and key desiderata, please refer to the first global response. Here we provide detailed answers to the specific concerns.

1. Application to semantic-rich scenarios: We acknowledge the reviewer’s concern regarding the applicability of our approach in semantic-rich scenarios. While GNNs are naturally designed to incorporate semantic input through node attributes, we intentionally took a different direction in our work. Our approach focuses exclusively on learning from the graph’s topological structure, as node attributes are not always aligned with structural information (e.g., in cases of heterophily [1]), which can degrade learning performance. Although semantic features can be integrated into the learning process in various ways [2], we chose a more straightforward approach that is broadly applicable in typical settings. Specifically, since the ultimate goal of node embeddings is to solve downstream tasks, our method produces interpretable structural features $\mathbf{h}(u)$ that can easily be combined with semantic attributes $\mathbf{x}(u)$ by concatenation $[\mathbf{h}(u); \mathbf{x}(u)]$. This results in a fully transparent feature set, enabling the use of well-established explanation techniques for tabular data to explain the downstream tasks effectively.

2. Clarifications on key desiderata: Please refer to our global response which mainly focuses on this clarification. We are happy to answer any further questions.

3. Comparisons with other interpretability-focused methods: We emphasize that our approach focuses on explaining model encodings, unlike methods such as GNNExplainer and PGExplainer, which explain model decisions. This makes direct comparisons unsuitable. However, we can use our interpretable embeddings to train downstream models. Explanations for model decisions are then extracted by using feature interpretability techniques. In that sense, existing feature interpretability techniques are complementary to our approach. Since the input features are interpretable, we can associate subgraphs with the most important features as explanations. Comparisons with GNNExplainer and PGExplainer are now provided in Appendix A.6.3, where we also included two additional synthetic datasets for node classification, Tree-Cliques and Tree-Grids. Reported results show that our method is capable of producing graph explanations with comparable, or even better, Plausibility metrics than GNNExplainer-PGExplainer.

[1] Zhu, Jiong, et al. "On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks." arXiv preprint arXiv:2409.17475 (2024).

[2] Tan, Qiaoyu, et al. "Collaborative graph neural networks for attributed network embedding." IEEE Transactions on Knowledge and Data Engineering (2023).

In their response, the authors address the lack of definition and operationalization of explanatory metrics by providing conceptual explanations of the metrics and comparisons with existing methods, but do not detail specific mathematical formulas or pseudo-codes. In response to concerns about inadequate performance on traditional tasks, the authors acknowledged that the main contribution of the model is in explanatory enhancements and plan to supplement the revised version with trade-off analysis and optimization results. In response to concerns about the limited scope of the dataset, the authors illustrate the applicability of the model to complex graph structures through theory, but make no commitment to extend the scope of the evaluation. Finally, in response to the issue of an outdated baseline model, the authors do not respond directly to how to introduce more modern comparison methods, and the overall response fails to fully address all reviewer concerns.

Also considering the concerns raised by reviewer Y413, I have decided to drop my score.

We would like to emphasize that our Initial Response was just a clarification of the main concerns pointed out by several reviewers. We have now posted a complete rebuttal, where we have addressed each issue and included also the revised paper.

We would also like to point out that all our metrics were accompanied by mathematical formulas already in the initial version, and that pseudo-codes have been added in the Appendix. In the box above, we have also answered the reviewer’s concerns about the limited scope of the datasets and baseline models.

In our rebuttal, we clarified any further issues raised by reviewers. If you have concrete questions about any mathematical equations, or about other answers, please let us know.

We gratefully thank the reviewer for the insightful comments provided in the review. For clarifications on the proposed evaluation metrics and key desiderata, please refer to the first global response. Here we provide detailed answers to the specific concerns.

W1. Practical utility of self-explainability: We appreciate the reviewer’s observation regarding the need for further clarification of the term "self-explainable." In our context, "self-explainable" refers to the ability to derive global explanations for the embedding space in the form of subgraphs (one per dimension), as detailed in Section 3.1. However, this feature would hold little value if the resulting subgraphs were not interpretable—i.e., if they could not convey meaningful insights to a human observer, despite being straightforward to extract. Therefore, the capability to generate dimensional subgraphs is intrinsically tied to identifying human-comprehensible functional components within the input graph, such as structural communities. In essence, the embeddings should align with significant substructures of the graph. To illustrate this, Figure A2 in the Appendix provides a practical visualization of the global explanations. Moreover, the corresponding subsection A.5.1 highlights why our method is particularly effective for extracting them.

W2. Comparisons with other interpretability-focused methods: We emphasize that our approach focuses on explaining model encodings, unlike methods such as GNNExplainer and PGExplainer, which explain model decisions. This makes direct comparisons unsuitable. However, we can use our interpretable embeddings to train downstream models. Explanations for model decisions are then extracted by using feature interpretability techniques. In that sense, existing feature interpretability techniques are complementary to our approach. Since the input features are interpretable, we can associate subgraphs with the most important features as explanations. Comparisons with GNNExplainer and PGExplainer are now provided in Appendix A.6.3, where we also included two additional synthetic datasets for node classification, Tree-Cliques and Tree-Grids. Reported results show that our method is capable of producing graph explanations with comparable, or even better, Plausibility metrics than GNNExplainer/PGExplainer.

W3. Calibration of proposed metrics against established metrics: We have addressed this point in our global response under clarification on metrics. Please let us know if you have further questions. We would like to emphasize that we use plausibility to assess how well our explanations align with human reasoning. Similar to GNNExplainer, we evaluate on synthetic datasets with planted subgraphs, which serve as ground-truth human rationales for explaining specific node labels. Our results in Appendix A.6.3 demonstrate that the most important embedding dimension identified by the downstream classifier consistently aligns with the true explanation subgraph. Additionally we add visualizations of the found explanations in Figure A7 of the Appendix. While this marks a significant step towards human-centric evaluation, conducting studies with actual human participants is beyond the scope of this work due to the substantial resources required. Moreover, designing effective human evaluation protocols remains a challenging research problem in itself. We view this as an important direction for future research and are optimistic that our proposed metrics provide a strong foundation for advancing human-in-the-loop evaluations.

Q1. Please refer to the response W2.

Q2. Scalability: We appreciate the reviewer’s question about the scalability of our approach. We put in the appendix A.3 an analysis of the complexity of the algorithm, showing that our method has $\mathcal{O}(|\mathcal{E}| K + |\mathcal{V}|K^2 + |\mathcal{V}|K T L)$ runtime complexity and $\mathcal{O}(|\mathcal{V}| K + |\mathcal{V}|L )$ space complexity ($T$ refers to the window size, $L$ to walks length). Despite the proposal of a scalable approach to very large graphs is not among the purposes of this work, we emphasize that these quantities are in line with well-established techniques for node embeddings [1].

Q3. Visualizations of interpretable graph structures: We appreciate the reviewer’s suggestion to enhance the clarity of our metrics through visualizations. Figure A2 illustrates how various embedding methods can be interpreted once trained on the synthetic BA-Cliques dataset, where each dimension-specific subgraph is highlighted in a different panel. From the figure, it is evident that for DeepWalk and GAE the subgraphs exhibit significant overlap, which can be attributed to non-zero correlations between the latent features. In contrast, the uncorrelated features of DiSeNE produce distinct, non-overlapping explanations.

[1] Tsitsulin, Anton, et al. "FREDE: anytime graph embeddings." Proceedings of the VLDB Endowment 14.6 (2021).

Clarification on key desiderata

One of the reviewers explicitly asked about dimensional interpretability which we first explain in detail below. We also provide intuitive explanations about the other two and are happy to provide more details if required.

1. Dimensional interpretability. Our framework assigns "responsibility" for reconstructing a local relationship (an edge) to specific dimensions, based on their contribution to the edge likelihood or the probability of reconstructing that edge through the embeddings. Equation 1 quantifies this contribution. We appreciate the reviewer’s insight regarding the relationship between the locality of edges and the global nature of embeddings. Our framework bridges this gap as follows:
   • Decomposing Relationships by Dimensions: Embeddings are multidimensional, with each dimension representing specific latent features (e.g., social similarity, geographic proximity, shared interests). A given edge between $u$ and $v$ may rely more heavily on certain dimensions. For instance, if dimension $d_1$ strongly influences edges where proximity is critical, it can be interpreted as capturing the property of "geographic proximity." This perspective shows how local relationships (edges) are directly informed by the global dimensions of the embeddings, with each dimension contributing uniquely to reconstructing particular relationships.
   • Global Explanation composed of Local Roles: The global graph structure is reconstructed by aggregating these local relationships. Each dimension contributes to reconstructing specific edges or substructures, and together, these contributions create a unified representation of the entire graph—analogous to assembling a puzzle, where every piece is essential to completing the overall picture. Thus, the global nature of embeddings emerges as a direct consequence of their contributions to local relationships, resolving the apparent conflict between locality and globality.
2. Structural faithfullness mainly says that the obtained embeddings should be faithful to input graph structure which we enforce using a graph reconstruction-based loss function.
3. Finally, we have structural disentanglement which seeks to ensure that the dimensions of the embeddings are disentangled, meaning each dimension is responsible for reconstructing a distinct set of edges. This is achieved by minimizing the loss function in Equation 4, which penalizes correlation between the edge importance attribution scores of different dimensions. By reducing this correlation, we ensure that each dimension contributes uniquely to the reconstruction of edges, avoiding redundancy and promoting interpretability.