Towards Robust Heterogeneous Graph Explanations under Structural Perturbations

Thank you for your review and valuable comments. We address your questions and clarify the misunderstandings as follows. Our proposed controllable structural perturbation is a heuristic yet flexible approach designed to simulate realistic noise for evaluating its impact on explainers. It aims to maintain comparability with prior studies [1,2,3] and enable targeted evaluation in adversarial or highly irregular scenarios. This method can be replaced by other graph structure perturbation techniques.

---

W1: Uniform neighbor degree distributions should be discussed.

---

The uniform assumption was introduced to simplify the derivation, a practice widely adopted in prior works [4,5]. In the context of noise injection, our focus is on the statistical impact of perturbations on the overall graph structure, rather than the precise changes for individual nodes. In this scenario, assuming a uniform distribution effectively captures the perturbation effects in an average sense. To further validate this, we analyzed the degree distributions of the DBLP, ACM, and Freebase datasets before and after perturbation, as shown in Table 4 in the Appendix. The results indicate that our method achieves significant noise effect while only slightly altering the degree distribution (with JS divergence < 0.22), as demonstrated in Table 2 of the main text. Additionally, we conducted experiments comparing the performance of the explainer under the Uniform Assumption and the actual degree distribution. The results, presented in Table 3 of the Appendix, confirm that the uniform assumption has minimal impact on model performance compared to using the real distribution.

---

W2: It is unclear how equation (23) follows from (22) and how the latter follow from (21), e.g., what approximation is used.

---

From Eq. (22) to Eq. (23), we simplify Eq. (22) by noting that $d_i^r$ is the degree of the current node, and when $d_i^r$ is of the same order as $\bar{d}^r$, the term $(d_i^r + \bar{d}^r)$ can be roughly approximated as $d_i^r$. From Eq. (21) to Eq. (22), we apply the assumption of uniform degree distribution among neighbors, the degrees of neighbors $d_j^r$ can be approximated by the average degree $\bar{d}^r$. We respectfully argue that the approximations used are standard in spectral graph theory and expectation analysis under uniform degree assumptions, and are commonly adopted in prior works involving degree-based analysis. Nonetheless, we agree that a brief explanation in the main text or appendix will help improve readability. We also checked all formulas in the paper and corrected minor typing errors.

---

W3: It appears that the probabilities in Equation (3) can be greater than 1.

---

Thank you for raising this concern. We understand the reviewer’s point regarding the possibility of probabilities exceeding 1 in Eq. (3), especially in cases like a star graph where degree imbalance exists. However, we would like to clarify that the expression: $\eta_r^+\cdot\frac{d_i^r+d_j^r}{2\bar{d}^r}$ is bounded and does not exceed 1 under our construction. The term $\frac{d_i^r+d_j^r}{2\bar{d}^r}$ normalizes local degrees by the global average degree $\bar{d}^r$, and its expectation is 1. Moreover, the multiplier $\eta_r^+\in[0,1]$ ensures that the final probability remains valid. We have clarified this in the revised version to avoid further confusion.

---

W4: The definition of the variables in formula 4 is unclear.

---

The purpose of Equation 4 is to obtain the perturbation budget for different edge types. All definitions are given in lines 97-100. $\mathcal{E}_r$ represents the edges of type $r$.

---

W5: The notation in Line 62 in Section 2.1 is not defined and is unclear.

---

We have thoroughly reviewed our definition of heterogeneous graphs, and all notations have been properly defined.

---

W6: It is unclear how B^+ and B^- are chosen in Equation (5).

---

We explain the corresponding options in the Implementation Details on lines 236-245.

---

W7: Difference from real-world noise.

---

Structural perturbation is widely used to simulate real-world noise in GNN. Prior works have shown that real-world noise is random in nature, often arising from missing or spurious edges, and is typically modeled as uniform edge addition or deletion [1,3]. Building on this, we propose a heterogeneous-specific strategy for more flexible and controllable noise modeling. It replicates real-world noise (as in our experiments), ensures comparability with prior work, and enables targeted perturbation by edge type or degree to simulate adversarial or highly irregular scenarios for broader robustness evaluation.

---

W8: Influence is not defined in Theorem 3.2.

---

Here, influence refers to the amplification factor of messages during the GNN message-passing process, which has been described similarly in prior works [2,3].

---

W9: The quantity in Theorem 3.2 is greater than 1 but it can be arbitrarily close to 1.

---

Thank you for pointing this out. We have deleted ‘significantly’ in the revised manuscript.

---

W10: MAE=RMSE^2.

---

We must point out your mistake: $RMSE=\sqrt{MSE}\ne\sqrt{MAE}$. In our experiments, both MAE and RMSE are equally important. MAE directly reflects the average error magnitude, while RMSE better evaluates the model's ability to handle outliers. In our experiments, we used logit values, and we have illustrate in the revised manuscript.

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] 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.

[3] 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.

[4] Sun, Zeyu, et al. "Generalized equivariance and preferential labeling for gnn node classification." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 8. 2022.

[5] Dawn, Sucheta. "Graph Neural Networks for Homogeneous and Heterogeneous Graphs: Algorithms and Applications." (2025).

As mentioned previously, the responses in the authors' rebuttal were not sufficient to address the concerns raised in my original review.

Overall, I believe this manuscript falls significantly short from the standards of publication and presentation at NeurIPS.

To reiterate the issues that contribute to my score:

i) The definitions in Equations (3), (4), and (5) are not justified theoretically and seem rather arbitrary (only high level justifications have been provided for choice of parameters which can be applied to many other choices of parameters, other than what is used in this work).

ii) There are inaccuracies in these definitions (Equations (3), (4), and (5)) as mentioned in my original review, such as probabilities being above 1 for specific choices of parameters, among other issues.

iii) The statement of Theorem 3.1 is general whereas its "proof" is provided for a special case with uniform degree graphs. Consequently, the theorem is in fact not proved.

iv) Even for the special case, the proof of Theorem 3.1 includes several inaccuracies in its approximations (e.g., Equations (22) and (23)). The justification provided by the authors in their response, that there is "a quadratic term $\frac{{d^r_i}^2}{2\bar{d}^r}$ and a linear term $\frac{d^r_i}{2}$" and that the "quadratic term grows faster" is flawed. Note that $\frac{{d^r_i}^2}{2\bar{d}^r}$ is not quadratic as it has a degree in denominator. So, both terms grow linearly.

v) The statement of Theorem 3.2 is ambiguous. The theorem is a statement about "influence" which is never defined rigorously, so it is unclear what is being stated/proved.

vi) Sections 3.3 and 3.4 are restatements of well-known concepts in the literature (e.g., graph information bottleneck, the reparameterization trick, etc.)

vii) Section 4.1 has an inaccuracy in defining RMSE and MAE with respect to indicator variables rather than logits, which the authors confirm. As a result, the definitions in this section do not align with the actual simulations and implementations provided in the manuscript.

The above issues encapsulate only a subset of the inaccuracies and ambiguities in the manuscript. Given the limited novelty, numerous inaccuracies in theoretical foundations, and the lack of a sufficient response in the rebuttal, I maintain my score.

We sincerely thank your comments. We acknowledge that the initial manuscript had certain issues in presentation and clarity, especially in the placement of assumptions and the wording of derivations. However, we would like to emphasize that the rebuttal process is intended to assess whether the authors’ response adequately resolves the concerns, not merely to reiterate criticisms without engaging with the clarifications provided. Your follow-up response does not engage with these clarifications in good faith and fails to specify which technical issues remain unresolved. If the reviewer believes that any specific issue remains unaddressed, we sincerely invite further clarification. Otherwise, we believe it is reasonable to consider that our responses have fully addressed the concerns raised.

Uniform degree assumption should stated in the theorem, in the current manuscript, such assumptions are introduced and used in the proof in the appendix.

We agree that assumptions used in a theorem's proof should be clearly stated. The uniform assumption was introduced in the proof in the Appendix C as a standard simplification, following common practice in prior work. While our intention was to simplify the derivation without overstating the generality of the theorem. In the revised manuscript, we explicitly include this assumption in the theorem statement and clarify the scope of the result. However, this is clearly a presentation issue, not a technical flaw. The derivation remains valid under the stated condition.

"Roughly approximated" is vague; needs precise derivation.

$d^r_i \cdot \eta_r^+ \cdot \frac{d^r_i + \bar{d}^r}{2\bar{d}^r}=\eta_r^+ \cdot (\frac{{d^r_i}^2 + d^r_i \bar{d}^r}{2\bar{d}^r})=\eta_r^+ \cdot (\frac{{d^r_i}^2}{2\bar{d}^r}+\frac{d^r_i}{2})$. This expression consists of two terms: a quadratic term $\frac{{d^r_i}^2}{2\bar{d}^r}$ and a linear term $\frac{d^r_i}{2}$. The quadratic term $\frac{{d^r_i}^2}{2\bar{d}^r}$ grows asymptotically faster than the linear term $\frac{d^r_i}{2}$ as $d^r_i$ increases. Consequently, the quadratic term becomes the dominant component in the expression for $\mathbb{E}[\Delta d_{i, +}^{r}]$, and the linear term can be omitted in the leading-order approximation. This yields the simplified form. We provide detailed derivations and cite relevant literature in the revised version. These approximations are technically valid and widely accepted.

The restrictions that ensure probabilities remain bounded below 1 must be mentioned in the text of the manuscript.

We would like to respectfully clarify that your concern regarding probabilities potentially exceeding 1 in Eq. (3) has already been directly addressed in our initial rebuttal. As we previously explained:

The term $\frac{d_i^r + d_j^r}{2\bar{d}^r}$ normalizes local degrees by the global average degree $\bar{d}^r$, and its expectation is 1. Moreover, the multiplier $\eta_r^+ \in [0,1]$ ensures that the final probability remains valid.

We also explicitly stated that this explanation has been added to the revised manuscript for clarity and to avoid future confusion.

Given this, we are unsure which part of the concern remains unresolved. If there is a specific issue that you feel has not been adequately addressed, we would sincerely appreciate it if you could point it out so that we can clarify further. Otherwise, we believe this point has been properly resolved both mathematically and in terms of manuscript presentation.

Misinterpretation of MAE = RMSE².

Regarding the computation of RMSE and MAE, we respectfully reiterate that we have already clarified this point in our rebuttal with revision. We respectfully note that the current response appears to restate the original concern without acknowledging the clarification already provided.

Other Points (Notation, Definitions, Implementation)

All minor notational ambiguities and definitional issues have been addressed in detail in our previous response, with references to the main text or appendix.

In summary, while we acknowledge that the initial submission had certain issues in presentation, we have explicitly addressed every concern raised, including clarifying assumptions, providing detailed derivations, correcting ambiguous wording, and revising the manuscript accordingly.

We hope that our substantial revisions and clarifications can be evaluated fairly in light of the paper’s contributions.

Thank you for your review and valuable comments. We address your questions and clarify the misunderstandings as follows.

---

Q1: Would it be possible to discuss how the denoising variational inference and the attention mechanism that captures heterogeneous relations, respectively, contribute to the overall performance, for example, based on evaluation experiments using homogeneous graphs?

---

While our explainer is primarily designed for heterogeneous graphs where the heterogeneous explanation generator is crucial for capturing key semantics across multiple node and edge types, the proposed method can also generalize to homogeneous graphs. In such settings, RoHeX leverages robust representations learned through denoising variational inference, which helps produce more accurate and stable explanations, even in the absence of relation types. To support this, we conducted experiments on the homogeneous graph dataset BA-Shapes and performed ablation analysis to isolate the contributions of different modules. We observed that incorporating the denoising variational inference led to a 7.4% improvement in AUC over GNNExplainer, and overall, RoHeX outperformed existing homogeneous GNN explainers in explanation quality. These results demonstrate that both the denoising and relation-aware components contribute positively, with denoising playing a key role in robustness and generalization.

---

Q2: There are some typographical errors in the text.

---

Thank you for pointing this out. Upon careful review, we confirm that the issue you mentioned was indeed a typographical error on our part. We appreciate your careful reading, and we have corrected the corresponding expressions in the revised version. We have also re-checked all related mathematical expressions to ensure consistency throughout the paper.

We thank the reviewer for the constructive comments and positive feedback on our theoretical analysis and robustness evaluation. We address each weakness and question below.

---

Q1: Can RoHeX be applied to other GNN tasks?

---

RoHeX is designed with a modular explanation framework that can, in principle, be extended to other GNN tasks such as link prediction and graph classification. For link prediction, the explanation target shifts from a node to an edge (or pair of nodes). The denoising variational inference module remains applicable, and the explanation generator can be adapted to highlight subgraphs contributing to the predicted link. In fact, our structural noise analysis is edge-centric and directly supports such extensions. For graph classification, the explanation module would be applied at the graph level. This adds a Readout function to the overall. The denoising encoder can extract graph-level latent representations, and the explanation generator can identify critical substructures within the whole graph.

We will include a discussion of this generalization potential in the final version and plan to validate RoHeX on these tasks in future work.

---

Q2: The ability of the structural perturbation method to simulate realistic noise.

---

Structural perturbation is widely used to simulate real-world noise in GNN. Prior works have shown that real-world noise is random in nature, often arising from missing or spurious edges, and is typically modeled as uniform edge addition or deletion [1,2]. Building on this, we propose a heterogeneous-specific strategy for more flexible and controllable noise modeling. It replicates real-world noise (as in our experiments), ensures comparability with prior work, and enables targeted perturbation by edge type or degree to simulate adversarial or highly irregular scenarios for broader robustness evaluation.

---

Q3: In the explanation method in Section 3.4, how are important subgraph edges selected?

---

After generating the probability matrix, we can select edges in the key subgraph based on edge importance by applying a threshold for sampling. In our experiments, the threshold is set to 0.5.

Reference:

[1] Zhu, D., Zhang, Z., Cui, P., & Zhu, W. (2019, July). Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining (pp. 1399-1407).

[2] Zhang, M., Wang, X., Zhu, M., Shi, C., Zhang, Z., & Zhou, J. (2022, June). Robust heterogeneous graph neural networks against adversarial attacks. In Proceedings of the AAAI conference on artificial intelligence (Vol. 36, No. 4, pp. 4363-4370).

We sincerely thank the reviewer for the thoughtful and constructive feedback. We are encouraged by the reviewer’s recognition of the importance and novelty of our work, particularly the integration of denoising and relation-aware explanation within heterogeneous GNNs. We address each of the reviewer’s comments and questions in detail below.

---

Q1: Can we add the same Metrics as xPath (Accuracy, Fidelity, and Probability Fidelity from xPath)?

---

We present the results of accuracy fidelity and probability fidelity in the following table:

These metrics are fully compatible with RoHeX. Our results show that RoHeX consistently outperforms xPath and other baselines on these metrics across multiple heterogeneous datasets, further validating the effectiveness of our method under fidelity-oriented evaluation.

---

Q2: The experiments do not include commonly used heterogeneous graph benchmarks such as IMDB. Has RoHeX been tested on these datasets? If so, how does it perform in those settings?

---

Thank you for highlighting this. The dataset used in our paper is from heterogeneous graph benchmarks [1].

We have now added two widely-used heterogeneous graph benchmarks: IMDB and AMiner in our revised experiments. The results are shown in the following table:

On both datasets, RoHeX outperforms existing explainers in terms of MAE, RMSE, accuracy fidelity and probability fidelity, reaffirming its generalizability across diverse multi-relational graph structures.

---

Q3: Evaluation on Simpler, Homogeneous Graph.

---

We acknowledge the importance of demonstrating the versatility of our approach beyond heterogeneous settings. Although RoHeX is primarily designed for heterogeneous graphs, its denoising and bottleneck-based framework can generalize to homogeneous graphs as well.

To that end, we have added experiments on the BA-Shapes dataset, a standard synthetic benchmark for homogeneous GNN explanation tasks. We compare RoHeX with GNNExplainer and PGExplainer, two popular methods in this space. Results show that RoHeX achieves competitive or superior performance, highlighting the robustness of our variational denoising strategy even in homogeneous settings. In future work, we plan to extend RoHeX to more datasets.

[1] Lv, Q., Ding, M., Liu, Q., Chen, Y., Feng, W., He, S., ... & Tang, J. (2021, August). Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining (pp. 1150-1160).