Explainable Graph Representation Learning via Graph Pattern Analysis

Dear Reviewer Un2e,

We highly appreciate your detailed comments that have improved the quality of our work significantly Our responses to the weaknesses you mentioned are as follows.

Response to Weakness 1:

Thank you so much for pointing out these issues. We have revised the manuscript thoroughly to correct all these language and formatting errors and enhance readability. Your detailed suggestions improved the quality of our paper a lot.

Response to Weakness 2:

Thank you for your nice suggestion. We followed them and have rewritten Chapters 4 and 5 thoroughly. The text with significant changes are highlighted in red.

Response to Weakness 3:

Currently, our pattern selection focuses on commonly used graph patterns in graph theory and we utilized seven patterns in the experiments. More importantly, as can be seen from Tables 3 and 5, our method already outperformed strong baselines of graph classification and clustering.

However, there are domain-specific patterns (especially when the size of each graph is large), like certain functional groups in biochemistry or particular methods of community detection in social networks, that we have not yet explored. We plan to include these specialized patterns in our revised paper to broaden the method's applicability and enhance its relevance to various fields.

Response to Weakness 4:

We have used the REDDIT-B dataset, which consists of 2000 graphs with an average of 429.63 nodes per graph, and the REDDIT-M5K dataset, which includes 4999 graphs with an average of 508.52 nodes per graph. These datasets are considered large-scale to some extent, especially when the computation source is limited. Currently, our equipment can only support experiments at this scale. (REDDIT-B: 7063s around 2h for one epoch running with 10 subgraphs sampled for each pattern; REDDIT-M5K, 25260s around 7h for one epoch running with 10 subgraphs sampled for each pattern).

It would be highly appreciated if you could check our paper again. We are continuously improving the writing and organization after the revision deadline. We are looking forward to your feedback.

Response to Question 1:

There are two advantages.

• Graph representation learning is usually an unsupervised learning task and graph patterns have practical meanings or functions in analyzing graph data. Therefore, it is important to understand what graph patterns are learned by a graph representation learning model. Our model can explicitly show the importance of different graph patterns and hence provide clear evidence of what graph patterns are important and discriminative in a given unlabeled dataset.

• In addition, explicitly taking advantage of different graph patterns can improve the accuracy in downstream tasks such as graph classification, which has been demonstrated by our experiments and our Theorem 5.2. Please refer to the discussion following Theorem 5.2: adding diverse patterns reduces the generalization error bound.

Response to Question 2:

Understanding important patterns in graph representations benefits real-world scenarios in several key aspects. First, it provides domain experts with interpretable insights about which structural features are crucial for specific properties, such as functional groups in molecules or community structures in social networks. Second, it helps ML practitioners design more focused and efficient feature extraction strategies by identifying the most informative patterns. Additionally, this understanding enables better model validation and refinement by comparing the importance of the learned pattern with domain knowledge.

Response to Question 3:

Unfortunately, it is not feasible because a graph pattern is based on multiple nodes rather than a single node and our method is specialized in graph-level representation learning.

Response to Question 4:

We appreciate your suggestion. We guess you mean assigning a score (e.g. classification accuracy) to the pattern we considered in our method. This is easy to implement in supervised learning, as we have shown by the table in Part I of Rebuttal. Given the importance indicator $\lambda$, we can just evaluate the classification accuracy of each of the top $k$ patterns separately. However, for unsupervised representation learning, there is no ground truth label, therefore we have to use only the weight parameters $\lambda$ as scores for explanation.

We are also considering to construct a mapping from $\lambda$ to the classification accuracy, which will improve the efficiency of explicit explanation.

Thank you again. We are looking forward to your feedback.

Dear Reviewer T9g2,

We thank you for your comments that have improved the quality of our work a lot. Our responses to your comments are as follows.

Response to Weakness 1:

We appreciate this suggestion regarding the organization of our introduction. While our paper introduces a novel concept of representation-level explainability in graph learning, we agree that the transition from post-hoc explainers could be better presented. In the revision, we reorganized the introduction to:

i) First emphasize that unlike previous post-hoc and instance-level methods, our work focuses on a fundamental question: "What specific information about a graph is captured in graph representations?" ii) Then explain how pattern analysis provides a natural solution - comparing substructures within specific graph patterns allows us to understand what information is embedded in representations. iii) Finally present our technical approach to learning and explaining representations via pattern analysis.

Response to Weakness 2:

Thank you for raising this point. Previous studies of explaining GNNs are usually supervised learning and use classification accuracy, AUROC, Fidelity, Probability of Sufficiency, etc, as scores for node features, edges, and motifs to evaluate their contribution, in comparison to the entire input [1]. Our work is different from these previous work in two aspects: 1) our methods work are mainly unsupervised, though we have supervised variants; 2) we aim at representation-level explanation. However, we have provided evaluations through the following aspects:

• In many figures such as Figure 2 and Figure 4, we use t-SNE to visualize the learned features of different graph patterns, which intuitively show the discrimination ability of different graph patterns.
• For each dataset, as shown in Table 2 in our paper, we highlighted the two patterns with the largest contribution. The results are consistent with the properties of the graphs in each dataset. For instance, the chemical rings are important to determine the mutagenicity, while our method identified that circles make the largest contribution.
• Direct evaluation in our method is easy to implement. For instance, the following table shows the classification accuracy of individual patterns and their different combinations on the MUTAG dataset. The best performance is shown in bold. It is worth mentioning that our method has the following significant advantage compared to other methods:
  • Our method can not only identify the contribution of each individual pattern but also find the optimal combination of patterns, leading to improved classification accuracy.

[1] Kakkad et al. A Survey on Explainability of Graph Neural Networks. 2023. https://arxiv.org/pdf/2306.01958

Response to Weakness 3:

We agree that the discussion of node representation explanations deserves more attention, although our approach is based on subgraph structures (patterns) rather than from a node perspective. In the revision, we will add a detailed discussion of UNR-Explainer and its related node representation explanation approach and compare our pattern-based method with UNR-Explainer in terms of methodology and applications. Further, we will reduce redundant discussions of post-hoc explanations while maintaining the necessary background.

Response to Weakness 4:

Thanks for the insightful comments. Our work aims at representation learning which is usually an unsupervised learning problem, though we provided a supervised variant of PXGL-GNN. This means our methods PXGL-EGK and PXGL-GNN are not designed to explain the prediction in supervised learning. To explain the prediction, one should prefer sample or feature attribution methods. Nevertheless, it is still possible to combine our pattern-based explanation with other explanation methods to explain prediction in supervised learning.

Response to Minor:

Thanks for pointing this out. We added the highlights.

Thank you for the rebuttal. From the beginning, I appreciate the novelty of the method. I agree with the authors that the proposed method differs from post-hoc explanation methods in model-level or local-level explanations since PXGL-GNN cannot pinpoint or generate the important subgraph. That's why the second paragraph has been confusing for me. Unfortunately, my concern has not been solved yet in the revised version, so I decided to maintain my score.

Dear Reviewer T9g2,

We have thoroughly revised the Introduction, where the text with significant changes is highlighted in red. The first two pages of the paper are at the anonymous link: https://anonymous.4open.science/api/repo/ICLR-Rebuttal-86F4/file/4579_Explainable_Graph_Represe.pdf?v=5d6afadc It would be highly appreciated if you could take into consideration the new revision.

Sincerely,

Authors

Dear Reviewer YwKS,

We sincerely appreciate your comments that have improved the quality of our work a lot. Our responses to your comments are as follows.

Response to Weakness 1:

Thanks for pointing out this. In the following table, we use three datasets to show the accuracy of Graph Classification of our PXGL-EGK model with different number of layers (L).

The results reveal that the model performs best at $L = 5$. With fewer layers, the model lacks sufficient capacity for representation; with more layers, the model is too complex and has overfitting performances. This is consistent with our theoretical analysis, since when the model is complex the gap between training error and the testing error becomes large.

Response to Weakness 2:

Yes. The following table shows the classification accuracy given by PXGL-GNN with different combinations of patterns on the MUTAG dataset. We see that by including more patterns, the classification accuracy tends to be higher. This is consistent with our theoretical analysis of Theorem 5.2 (please refer to the text around equation (15)). It is worth noting that when numerous patterns are used, our method can automatically identify the importance of each pattern and provide an optimal combination of the patterns.

Performance comparison of different pattern combinations on MUTAG dataset. The best performance is shown in bold.

Response to Weakness 3:

Thanks for pointing this out. The following table provides some results about the impact of $Q$ on the classification accuracy and time cost on the MUTAG dataset. We see that the time cost is roughly linear with $Q$ and the accuracy is not sensitive to $Q$ when it is larger than $5$.

Table: Impact of sampling number Q on MUTAG dataset (20 epochs, 7 patterns)

Thank you for your rebuttal. I think the authors have addressed the concerns I raised well. I am inclined to raise my score and hope the revised version will be included if the paper is accepted.

Dear Reviewer 3Cyd,

We appreciate your comments that have improved the quality of our work a lot. Our responses to weaknesses you mention as follows.

Response to Weakness 1

This is an insightful comment. We didn't show the time complexities of kernel computation and subgraph (e.g. graphlet) sampling. In the updated manuscript, we modified the time complexities by adding the complexities of kernel computation and subgraph sampling. For convenience, we show some results as follows:

Given a dataset with $N$ graphs (each has $n$ nodes and $e$ edges), we select $M$ different patterns and sample $Q$ subgraphs of each pattern. The time complexity of PXGL-EGK is $\mathcal{O}(N^2\sum_{m=1}^M\psi_i)$, where $\psi_i$ denotes the time complexity of the $m$-th graph kernel. For instance, the time complexities of the graphlet kernel, shortest path kernel, and Weisfeiler-Lehman Subtree kernel are $\mathcal{O}(n^k)$, $\mathcal{O}(n^4)$, and $\mathcal{O}(hn+he)$ respectively, where $k$ and $h$ are some kernel-specific hyperparameters. Regarding PXGL-GNN, suppose each representation learning function $F_m$ is an $L$-layer GCN, of which the width is linear with $d$. For both supervised and unsupervised learning, suppose the batch size and the number of iterations in the optimization are $B$ and $T$ respectively. Then, in supervised learning, the time complexity is $\mathcal{O}(TBMQL(ed+nd^2)+NQ\sum_{m=1}^M\vartheta_m)$, where $\vartheta_m$ denotes the time complexity of generating a sample of the $m$-th pattern. For instance, when the $m$-th pattern is graphlets with size $k\in\\{3,4,5\\}$, we have $\vartheta_m\leq nu^{k-1}$ [1], where $u$ denotes the maximum node degree of the graph. In unsupervised learning, the time complexity is $\mathcal{O}(TBMQL(ed+nd^2)+TB^2+NQ\sum_{m=1}^M\vartheta_m)$.

Here we show the time costs of the sampling stage and training stage on the MUTAG dataset.

[1] Shervashidze et al. Efficient graphlet kernels for large graph comparison. AISTATS 2009.

Response to Weakness 2:

Thanks for pointing it out. Our theoretical analysis focuses on demonstrating the robustness and generalization capabilities of our model PXGL-EGK, since robustness and generalization are two important aspects of any machine learning model.

Our robust analysis shows that the representations produced by PXGL-EGK remain stable even when the input graphs are altered by noise under some mild conditions, such as the spectral norms of the weight matrices and the adjacency matrix are not too large. Specifically, PXGL-EGK is notably resilient to changes in the graph structure (like perturbations to node features) and increasing the minimum node degree tends to enhance its robustness.

Additionally, our generalization analysis shows the upper bound of the difference between training error and testing error. It is worth noting that in the proof (see (36)) of the theorem, we used an aggressive relaxation such that $\boldsymbol{\lambda}$ was not present in $\eta$. By keeping $\boldsymbol{\lambda}$, we can obtain

$

\eta = \frac{\tau}{\sqrt{n}} \rho^L \hat{\beta}_ W^{L-1} \beta_X (1 + \beta_ A)^L (1 + \alpha)^{-L} \left[ \hat{\beta}_ W \gamma_ {\Delta C} + \gamma_{C} \left(\hat{\beta}_ W\Vert\boldsymbol{\lambda}_ {\mathcal{D}}-\boldsymbol{\lambda}_ {\mathcal{D}^{\backslash i}}\Vert+ L \hat{\beta}_ {\Delta W}\Vert\boldsymbol{\lambda}_ {\mathcal{D}^{\backslash i}}\Vert\right) \right]

$

Since $\Vert\boldsymbol{\lambda}_ {\mathcal{D}}\Vert_ 1=\Vert\boldsymbol{\lambda}_ {\mathcal{D}^{\backslash i}}\Vert_ 1=1$, when $M$ is larger, $\Vert\boldsymbol{\lambda}_ {\mathcal{D}}-\boldsymbol{\lambda}_ {\mathcal{D}^{\backslash i}}\Vert$ and $\lVert\boldsymbol{\lambda}_ {\mathcal{D}^{\backslash i}}\Vert$ are potentially smaller. This means that when we include more graph patterns, the generalization bound (linear with $\eta$ shown in Section 5.2) of our PXGL-GNN becomes tighter, which potentially leads to higher classification accuracy. This is actually supported by our experiments. For instance, the following table shows the influence of different combinations of patterns on the MUTAG dataset. We can see that more patterns do better.

We have added the above discussion to the updated paper.

Response to Weakness 3:

Yes, they are entirely different. Our PXGL-EGK introduces a novel concept in explainable graph learning at the representation level, which is a first in this field. This differs significantly from previous approaches to explainable graph learning. Our PXGL-EGK method pioneers representation-level explainability in graph learning. It seeks to answer a fundamental question: What specific information about a graph is captured within its representations.

Existing model-level explainability methods in graph learning, such as GLG-Explainer [1] and GCFExplainer [2], aim to make the model's overall behavior more transparent. Instance-level methods, like GNNExplainer [3], provide explanations for specific predictions by detailing the reasoning behind particular classifications.

[1] Steve Azzolin, et al. Global explainability of gnns via logic combination of learned concepts.

[2] Zexi Huang, et al. Global counterfactual explainer for graph neural networks. ICDM, 2023.

[3] Zhitao Ying et al. Gnnexplainer: Generating explanations for graph neural networks. NIPS 2019.

Response to Weakness 4:

Thanks for providing the related references. We included them in our updated manuscript and added the following discussion:

• UNR-Explainer [1] identifies the top-k most important nodes in a graph to determine the most significant subgraph. It is a classic instance-level explainable graph learning method focused on node representation. However, this task is entirely different from our approach, as it addresses node-level representation rather than representation-level explainability. For this reason, we did not include a comparison.

• MotifExplainer [2] identifies critical motifs (small subgraphs) in a graph. However, it does not address graph representation learning or representation-level explainability. Instead, it focuses on understanding what specific information about a graph is captured in its representations. Since this is fundamentally different from our work, we did not compare our method to theirs.

[1] Kang, Hyunju, Geonhee Han, and Hogun Park. "UNR-Explainer: Counterfactual Explanations for Unsupervised Node Representation Learning Models." The Twelfth International Conference on Learning Representations, 2024.

[2] Yu, Zhaoning, and Hongyang Gao. "MotifExplainer: a motif-based graph neural network explainer." arXiv preprint arXiv:2202.00519, 2022.

Response to Weakness 5:

Subgraph counting graph kernels involves sampling specific subgraph patterns and counting their occurrences. For example, random walk kernels [1] sample random walks, subtree kernels [2] sample trees, and graphlet kernels [3] sample graphlets. In our work, we directly use the subgraph sampling functions provided by these traditional graph kernels in the GraKel tool https://ysig.github.io/GraKeL/0.1a8/.

Here we use the MUTAG dataset to show the sensitivity of accuracy and time cost to the number of samples $Q$ for each pattern. We see that the time cost is roughly linear with $Q$ and the accuracy is not sensitive to $Q$ when it is larger than $5$.

Table: Impact of sampling number Q on MUTAG dataset (20 epochs, 7 patterns)

[1] Borgwardt et al. Protein function prediction via graph kernels. Bioinformatics, 2005.

[2] Giovanni et al. A tree-based kernel for graphs. SIAM, 2012.

[3] Shervashidze et al. Efficient graphlet kernels for large graph comparison. AI and statistics, 2009

Response to Weakness 6:

You're right that GNNs face limitations in expressive power. This issue has been extensively studied in [1], which shows that GNNs can capture graph patterns when subgraphs are small. A more powerful alternative is to use graph transformers, which have significantly greater expressive capacity. As an extension of our work, we plan to incorporate graph transformers into our PXGL-EGK method to address these limitations.

[1]B Zhang et al. Beyond weisfeiler-lehman: A quantitative framework for GNN expressiveness

Thank you again for your comments. We are looking forward to your feedback.