Robust Heterogeneous Graph Neural Network Explainer with Graph Information Bottleneck

Thank you for your review and your comments. We hope that our answers below help resolve any questions or potential misunderstandings.

1. If the edge representations are directly sampled from the variational distribution? The forward process deserves detailed introduction.

In the variational inference, the process of sampling edge representations directly from the variational distribution is part of the generative process for reconstructing the graph structure:

1. RHGIB uses an encoder (GCN) to learn latent representations for each node in the graph. The encoder outputs the mean and variance of the variational distribution for each node's latent representation, typically assuming a Gaussian distribution for the latent variables.

2. Once the encoder outputs the mean and variance for each node, we sample the latent node embeddings from a Gaussian distribution $\mathcal{N}(\mu_i, \sigma_i^2)$ for each node $v_i$, where $\mu_i$ and $\sigma_i^2$ are the mean and variance produced by the encoder for node $v_i$.

3. The goal is to predict the edges in the graph, and the edges are assumed to be generated from the dot product of the latent node representations. Specifically, the edge between two nodes $v_i$ and $v_j$ is predicted as follows: $\hat{A}_{ij} = \sigma(z_i^T z_j)$ where $z_i$ and $z_j$ are the latent embeddings of nodes $v_i$ and $v_j$, and $\sigma(\cdot)$ is a sigmoid function that squashes the result into a probability (between 0 and 1).

4. For each node, sample latent variables $z_i$ from the variational distribution $\mathcal{N}(\mu_i, \sigma_i^2)$, and then compute the edge predictions based on these sampled values.

5. To allow backpropagation through the sampling process (since sampling is non-differentiable), the reparameterization trick is used. The reparameterization trick expresses the latent variable $z_i$ as: $z_i = \mu_i + \sigma_i \cdot \epsilon$ where $\epsilon \sim \mathcal{N}(0, I)$ is a random noise vector sampled from a standard normal distribution, and $\mu_i$ and $\sigma_i$ are the mean and standard deviation predicted by the encoder.

2. Elaboration on the denoising variational inference is recommended, especially for the motivation of Formula (4).

The motivation for performing denoising variational inference lies in the fact that heterogeneous graphs in the real world are often accompanied by noise, which can negatively affect the predictions of graph neural networks and lead to biased explanation results. By using denoising variational inference, we can effectively extract clean node representations from the original features and graph structure, mitigating the impact of noise and ensuring that the model's predictions are more accurate and reliable. This also enhances the model's robustness and its ability to understand complex semantics. At the same time, we have theoretically proven that existing heterogeneous graph methods amplify the effects of noise, further emphasizing the need to take measures to mitigate information degradation caused by noise. In Equation (4), due to the different distributions between noisy graph data and standard graph data, we transform the noisy distribution into the original distribution from a distributional perspective, introducing a transformation of the distribution.

3. How to acquire the edge type embedding $\mathbf{r}_{\varphi(e)}$ is missing in the manuscript.

We apologize for any confusion caused by our wording. We directly use one-hot encoding to encode each edge type, which is a common operation in other heterogeneous graph methods, such as simple-HGN [1], HINormer [2], and PHGT [3]. We have included the relevant details in the revised manuscript.

Reference:

[1] Lv, Qingsong, et al. "Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks." Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining. 2021.

[2] Mao, Qiheng, et al. "Hinormer: Representation learning on heterogeneous information networks with graph transformer." Proceedings of the ACM Web Conference 2023. 2023.

[3] Lu, Zhiyuan, et al. "Heterogeneous Graph Transformer with Poly-Tokenization." Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, International Joint Conferences on Artificial Intelligence Organization. 2024.

Thank you for your review and your comments. We hope that our answers below help resolve any questions or potential misunderstandings.

Q1. How can it be proven that the statistical features and distributions of graph data are affected by existing noise? Since the main goal of the paper is to eliminate noise present in real-world data, the authors only provide results where noise has been added to edges in the real dataset. How can these experimental results effectively reflect the noise in the real world? Is it possible to elaborate on the specific impacts of noise on the statistical features of graph data and provide related experiments or theoretical support to demonstrate the model's ability to effectively remove noise from real-world data?

Noise in real-world data is difficult to identify, so it is typically added manually. This is also the approach taken in related fields, such as adversarial attacks [1,2,3], for experimentation. Many existing studies have explored noise in the real world, such as applications in healthcare [4], communication systems [5], and image processing [6], demonstrating that our random noise can reflect real-world scenarios.

We measure the impact of noise on the graph distribution through the variation of the KL divergence, and it can be observed that noise significantly disrupts the graph distribution:

We evaluated the denoising performance under a 60% noise scenario (which significantly exacerbates the damage to the graph), and the comparison results with the ground truth are as follows:

Reference:

[1] Zhu, Dingyuan, et al. "Robust graph convolutional networks against adversarial attacks." Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019.

[2] Zhang, Mengmei, et al. "Robust heterogeneous graph neural networks against adversarial attacks." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 4. 2022.

[3] Ma, Jiaqi, Shuangrui Ding, and Qiaozhu Mei. "Towards more practical adversarial attacks on graph neural networks." Advances in neural information processing systems 33 (2020): 4756-4766.

[4] Gravel, Pierre, Gilles Beaudoin, and Jacques A. De Guise. "A method for modeling noise in medical images." IEEE Transactions on medical imaging 23.10 (2004): 1221-1232.

[5] Farsad, Nariman, et al. "Channel and noise models for nonlinear molecular communication systems." IEEE Journal on Selected Areas in Communications 32.12 (2014): 2392-2401.

[6] George, Swapna Mol, and P. Muhamed Ilyas. "A review on speech emotion recognition: a survey, recent advances, challenges, and the influence of noise." Neurocomputing 568 (2024): 127015.

Q2. In Proof of THEOREM 1, why the method based on neighbor aggregation does not consider the influence of node v_j's neighbors on node v_i? This could affect the effectiveness of neighbor aggregation, and it is suggested that the authors provide a detailed explanation of the rationale behind this assumption and discuss the interactions between nodes during the aggregation process.

The meta-path-based method directly aggregates all nodes along the meta-path, considering multi-hop nodes simultaneously based on the length of the meta-path. As a result, the neighbors of node $v_j$ have a significant impact on node $v_i$, which is why we found that this approach can amplify the noise effect. In contrast, the neighbor aggregation-based method, within the message-passing framework, only considers the influence of node $v_i$'s neighbors at each layer, and only at the second layer does it begin to incorporate the information from the neighbors of node $v_j$. Moreover, the influence is inversely related to the degree, making it much smaller compared to the meta-path-based method. Additionally, during the second layer of aggregation, the meta-path-based method further expands its influence range, dramatically amplifying the noise effect.

Thank you for your review and your comments. We hope that our answers below help resolve any questions or potential misunderstandings.

C1: For graph learning with HG, meta-path-based algorithms in one of the key technique. But how to select meta-path is important. Meta-paths are usually given by domain experts. As shown in the methdology and theoretical analyses, the proposed is robust to noise with meta-path-based methods. Would the theorem be applied for non-meta-path methods? For example, for node classification, a simple GCN/GAT on the target node layer/domain without meta-path is a straightforward baseline. How is the effect of noise for a simple GNN without meta-path?

I believe you may have misunderstood our approach. We have theoretically demonstrated the amplification effect of noise in heterogeneous graph neural networks using meta-path-based methods. In Appendix B, we compare the impact of noise on methods without meta-paths and those based on meta-paths, which lays the foundation for our choice of the base prediction model. The architecture of the prediction model we selected is detailed in Appendix D.3.

C2: The methodology section could be more concise and easier to follow.

Thank you for your comments. We have added descriptions of relevant concepts and removed unnecessary words. Additionally, we have adjusted the wording in the explanation subgraph sampling part to improve the readability of the paper.

C3: How does the proposed handle feature noise in addition to structural noise? The paper seems to focus primarily on structural noise.

In this paper, we mainly focus on structural noise because it has more practical significance, such as adversarial attacks [1], structural damage [2], etc. Current research indicates that graph structural information is crucial for classification tasks [3]. Therefore, we focus on structural noise. At the same time, in the datasets we used, only the target-type nodes have features, while the features of other types of nodes are filled with a matrix of ones. We will investigate feature noise and the scenario of attribute-free graphs in our future work.

Reference:

[1] Liu, Zihan, et al. "Towards reasonable budget allocation in untargeted graph structure attacks via gradient debias." arXiv preprint arXiv:2304.00010 (2023).

[2] Wang, Senzhang, et al. "V-InFoR: a robust graph neural networks explainer for structurally corrupted graphs." Advances in Neural Information Processing Systems 36 (2024).

[3] Luo, Dongsheng, et al. "Parameterized explainer for graph neural network." Advances in neural information processing systems 33 (2020): 19620-19631.

C4: The paper does not explore the generalizability of RHGIB to other graph tasks except for node classification, such as link prediction or graph classification as mentioned in introduction.

Our method holds great potential for providing explanations in link prediction and graph classification tasks. For link prediction, please extract the subgraph around the link's k-hop (where k is the number of layers in the HGNN) and then use a relation-based explanation generator to identify the key graph components that influence the link prediction. For graph classification, you can simply add a readout layer after the HGNN to generate an explanation subgraph that has a significant impact on the overall graph classification. Our method is flexible and can provide explanations for different tasks.

C5: The main contribution of this paper is on robustness on HG with noise. However, there is no experiments on specific investigation of the robustness. For example, a synthetic HG with community structure can be generated with existing graph generator (groundtruth is know for the synthetic graphs), such as Stochastic Block Model (SBM), Girvan-Newman Algorithm, and Caveman Graph Generator. Noise can be added by random deleting/adding edges. How would the proposed explain a GNN node clustering ability for the two HGs (one is noise-free, the other is with noise)?

We presented the model's performance under different levels of noise influence in Table 1, where it can be observed that RHGIB demonstrates strong robustness. The method you suggested for conducting experiments on synthetic graphs is excellent, and we will implement it in our future work. As for node clustering explanations under noisy conditions, we can first mitigate the noise through denoising variational inference, and then, during the explanation generation process, sample the key subgraphs that influence the model's decision, just as we would with a noise-free graph.

Thank you for your review and your comments. We hope that our answers below help resolve any questions or potential misunderstandings.

1. The motivation of doing graph denoising for post-hoc explanation is unclear and unreasonable to me. The post-hoc explainer should truly reflect the important subgraph structure and features that the target GNN relies on for prediction. If noisy edges play an important role in the target GNN’s prediction, the post-hoc explainer should reflect that, which is one purpose of doing post-hoc explanation, i.e., discovering potential issues in the algorithm and data. Doing denoising from the post-hoc explainer perspective would make the explainer unable to explain the target GNN well, especially when the target GNN relies on noisy edges for prediction. I think developing a robust self-explainable heterogenous GNN would be more convincing.

Many studies have shown that existing graphs contain noise, which can affect model predictions, such as [1], [2], and [3]. However, there are currently no relevant explainers that interpret the model's decision-making process in the presence of noise. From our experiments, we found that existing explainers are highly susceptible to noise, and the impact is significant.** The post-hoc explainer we designed accurately reflects the key subgraph structures and features upon which the prediction relies. The relation-based explanation generator captures key components of the message-passing process through a weighted sampling method, which can be quantitatively assessed. As demonstrated by the experimental results and case studies, our approach achieves competitive performance. We argue that, regardless of whether noisy edges impact the prediction, they should be removed and not fed into the GNN for prediction, as noisy edges carry no meaningful information. Providing explanations for clean graphs (i.e., denoised graphs) is a more reasonable approach. To address potential concerns, we conducted experiments under 60% noise conditions to validate the success rate of noise elimination. This scenario significantly damages the graph features, and the denoised graph was compared with the ground truth. The experimental results are as follows:

The denoising module we designed effectively eliminates the interference of noisy edges. Additionally, in Section 4.1, we theoretically demonstrate the model's denoising capability. Inputting the denoised graph into the model yields the best explanation results.

2. Many important details of the methodology about heterogeneous graph neural networks are missing. For example, how do the authors model $p(\mathcal{G}|\mathbf{Z})$ for the heterogeneous graph that takes different types and edges and nodes into consideration? How do the authors model $p(\mathcal{\tilde{G}}|\mathcal{G})$. Currently, the whole methodology is described in a way that almost has nothing to do with heterogeneous graphs.

We have provided further details of our method throughout the paper. In the revised manuscript, we have added an introduction to the relevant parameters, including heterogeneous attention coefficients and edge type embeddings. We also improved the description of the method to enhance readability. In the denoising inference section, we did not consider the heterogeneity of the graph because noisy edges significantly disrupt the heterogeneity, introducing spurious heterogeneity. Moreover, the false noise edges between different types of nodes generate misleading semantics for the model, and modeling the heterogeneity would only amplify the noise's impact. If heterogeneity were modeled in the $p(\mathcal{G}|\mathbf{Z})$ part, the model's inference would be interfered with by the false edge types, leading to biased predictions. In contrast, we treated the graph as homogeneous during the denoising inference, considering only the original graph distribution and the noise distribution, thereby enhancing the denoising performance. Regarding the $q(\mathcal{\tilde{G}}|\mathcal{G})$, it is an intermediate variable in the formula optimization. For the overall denoising inference objective, we approximate the objective using the Monte Carlo sampling method. During optimization, a constraint is introduced that forces $q_{\Psi}^{\prime}(\mathbf{Z}|\mathcal{G})$ to approximate the standard Gaussian distribution $p(\mathbf{Z})$.