Thank you for your response. We aim to address each of your comments below.

Comparison to other GNN watermarking methods.

In our paper, we highlight the limitations of backdoor watermarking methods, particularly their introduction of intentional misclassification and ambiguity. Additionally, the metrics for evaluating watermarking success differ fundamentally: prior methods, such as [1] and [2], measure watermarking accuracy (prediction success on backdoor samples), while our approach relies on hypothesis testing to demonstrate statistically significant patterns in explanations. This makes direct comparisons impossible.

Moreover, we emphasize that our method does not claim superiority in terms of classification accuracy. Instead, the key advantage of our method lies in addressing critical security concerns, such as the susceptibility of backdoor-based methods to data poisoning and the inherent ambiguity in watermark verification.

Model extraction attack.

To address concerns about model extraction attacks, we implemented a knowledge distillation attack [3]. Knowledge distillation has two models: the original “teacher” model, and an untrained “student” model. During each epoch, the student model is trained on two objectives: (1) correctly classify the provided input, and (2) mimic the teacher model by mapping inputs to the teachers’ predictions. The student therefore learns to map inputs to the teacher’s “soft label” outputs (probability distributions) alongside the original hard labels; this guided learning process leverages the richer information in the teacher’s soft label outputs, which capture nuanced relationships between classes that hard labels cannot provide. By focusing on these relationships, the student model can generalize more efficiently and achieve comparable performance to the teacher with a smaller model and fewer parameters, thus reducing complexity.

We find that in the absence of a strategically-designed defense, the knowledge distillation attack successfully removes our watermark ($p>0.05$). This is unsurprising, since model distillation maps inputs to outputs but ignores mechanisms that lead to auxiliary tasks like watermarking.

To counter this, we outline a defense framework that would incorporate watermark robustness to knowledge distillation directly into the training process. Specifically, during training and watermark embedding, an additional loss term would penalize reductions in watermark performance. At periodic intervals (e.g., after every x epochs), the current model would be distilled into a new model, and the watermark performance on this distilled model would be evaluated. If the watermark performance (measured by the number of matching indices) on the distilled model is lower than the watermark performance on the main model, a penalty would be added to the loss term. This would ensure that the trained model retains robust watermarking capabilities even against knowledge distillation attacks.

Performance without watermarking.

We have updated the paper (Table 1) to include accuracy rates in the absence of watermarking. For your convenience, we list them here. Note that accuracy rates are reasonable both with and without watermarking.

Other graph tasks.

While our results focus on node classification, our method can be extended to other graph learning tasks, such as edge classification and graph classification. The key is to obtain $n \times F$ features matrices that we can derive explanations from. For node classification, each of our $T$ target subgraphs yields a $n \times F$ matrix of node features. For edge classification, we can generate similar matrices for edge features. For graph classification, we can accomplish something similar by having each row in a $n \times F$ matrix represent the features of an individual graph; rather than have one such matrix for each of $T$ target subgraphs, we instead have one matrix per collection of subgraphs.

Please see further details of this extended logic in Appendix Section A.5 in our revisions.

---

References

[1] Zhao, Xiangyu, Hanzhou Wu, and Xinpeng Zhang. "Watermarking graph neural networks by random graphs." 2021 9th International Symposium on Digital Forensics and Security (ISDFS). IEEE, 2021.

[2] Xu, Jing, et al. "Watermarking graph neural networks based on backdoor attacks." 2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P). IEEE, 2023.

[3] Gou, Jianping et al. “Knowledge Distillation: A Survey.” International Journal of Computer Vision 129 (2020): 1789 - 1819.

Update: Extension to other Graph Learning Tasks

Thank you again for your previous comments on our work. Your question about applications to other graph learning tasks was mirrored by Reviewer ub6g, and to address this, we now have additional results to share.

In our previous comments, we outlined a framework for extending our methodology to other graph learning tasks (more details in Appendix Section A.5). To illustrate the broader applicability of our approach, we have now included results from watermarking explanations of predictions on the widely-used MUTAG [1] dataset within the graph classification framework. These results consistently yield p-values below 0.05 under varied configurations, demonstrating that our method can be effectively applied to other graph learning tasks.

While the edge classification framework would align closely with our node classification approach, watermarking for graph classification requires more modifications to our framework; therefore, the above results provide strong evidence of the flexibility of our method.

---

[1] Debnath, Asim Kumar et al. “Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity.” Journal of medicinal chemistry 34 2 (1991): 786-97.

Thank you for your thoughtful review and comments. We address your concerns below.

GNN explanation intuition.

To streamline our description, we have moved some of the detailed math in Section 3.2 to Appendix A.2, keeping only the final regression problem in the main paper. Here, we provide high-level insight into how the explanation process works:

• Our explanations are the output of a closed-form ridge regression problem applied to a transformation of the node features and node predictions (using Gaussian kernel matrices inspired by GraphLIME, though we do not use GraphLIME itself).
• While ridge regression assigns non-zero weights to all features, the relative magnitudes of the regression coefficients indicate the most influential features. However, our goal is not to analyze the explanations themselves for feature importance. Instead, we use the explanations as an embedding space for our watermark.
• During our embedding process, we intentionally manipulate the feature attribution vectors to align with a predefined watermark, prioritizing the ability to match a specific pattern over interpretability. Ridge regression’s non-zero weights provide the flexibility needed for precise alignment with the desired watermark. By contrast, Lasso regression’s sparsity-inducing nature would limit the ability to manipulate attribution vectors for embedding, making it less effective for our purpose.

To clarify, our method does not rely on the explanations to interpret GNN predictions. Instead, we use them as a structured space where ownership information can be securely embedded and later verified.

Adversary knowledge.

Our primary assumption is that the adversary does not have knowledge about the watermarked subgraphs. While we consider scenarios where they might know additional details, such as the number and size of the subgraphs, this is not our main focus. Rather, we include this analysis to demonstrate that even with such additional knowledge, our method remains robust. These scenarios are possible but not central to our default assumptions; they are presented to emphasize the resilience of our approach under varying conditions.

Verifier knowledge.

Our point in stating that the verifier only has black-box access is to emphasize that no additional information or model access is necessary for verification. Even in a scenario where the verifier is restricted to this limited level of access, they can still successfully perform the verification task. This highlights the robustness of our approach, which does not rely on access to model parameters or other privileged information.

[1] Zhao et al. “Watermarking Graph Neural Networks by Random Graphs.” ISDFS, 2020

[2] Xu et al. “Watermarking Graph Neural Networks based on Backdoor Attacks.” EuroS&P 2023

[3] Bansal, Arpit, et al. “Certified Neural Network Watermarks with Randomized Smoothing.” ICML 2022

[4] Müller, Luis, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. “Attending to Graph Transformers.” TMLR, 2024.

Thank you for your comments! We address each of your concerns below.

Tight threat model.

We’d like to clarify the capabilities of each party in our threat model.

• Adversaries: We assume adversaries have black-box access to the model and no knowledge of the watermark. Even in cases where adversaries gain white-box access (e.g., for fine-tuning or pruning), locating the watermark remains computationally intractable without precise knowledge of its location.

• Verifier: The verifier only requires black-box access to the model for verification, making the approach broadly applicable and robust.

• Model Owner: The model owner has white-box access to the training process and the data. This assumption is realistic and not unique to our method; many backdoor-based watermarking approaches also rely on access to training data for embedding or verification purposes [1-3].

Our method minimizes reliance on data pollution and avoids ambiguity, addressing the limitations of backdoor-based watermarking methods while leveraging access commonly assumed in this domain. We believe this combination of practicality and robustness makes our approach suitable for a wide range of scenarios, even if universal applicability is not guaranteed.

Fine-tuning with a larger learning rate.

Our default choice for fine-tuning learning rate was 0.1x the learning rate on the original task. To address your concern, we have conducted additional fine-tuning experiments with scaled learning rates (1x and 10x) – see Figure 12 in the appendix of our revised paper.

We find that larger learning rates accelerate the rise in the MI p-value, indicating faster degradation of the watermark. For instance, at 1x, the p-value increases sharply within the first 10 epochs. However, this comes at a significant cost: by the time fine-tuning accuracy (on the new dataset) increases to a reasonable level, accuracy on the original training set drops substantially, making the attack impractical as the model’s utility on the original task is severely compromised.

Additionally, the fine-tuning results in the original submission were inadvertently obtained by fine-tuning on the original training dataset. In the updated experiments, we fine-tuned on a separate validation set to better reflect realistic attack scenarios. This adjustment introduced some differences—most notably, a decline in original training accuracy—but, as previously noted, this strengthens our position by showing that fine-tuning attacks not only affect the watermark but also significantly degrade the model’s utility, reducing the attack’s stealth. Despite these changes, the p-value trends remain consistent: for Photo and PubMed datasets, the p-value stays roughly below 0.1 throughout fine-tuning, and for CS, it only rises above 0.1 after prolonged fine-tuning. These findings reaffirm the robustness of our method while highlighting the trade-offs faced by an attacker.

Other graph tasks.

While our results focus on node classification, our method can be extended to other graph learning tasks, such as edge classification and graph classification. The key is to obtain $n \times F$ features matrices that we can derive explanations from. For node classification, each of our $T$ target subgraphs yields a $n \times F$ matrix of node features. For edge classification, we can generate similar matrices for edge features. For graph classification, we can accomplish something similar by having each row in a $n \times F$ matrix represent the features of an individual graph; rather than have one such matrix for each of $T$ target subgraphs, we instead have one matrix per collection of subgraphs.

Please see further details of this extended logic in Appendix Section A.5 in our revisions.

Other models.

Graph Neural Networks are the more popular choice for graph learning tasks and a natural starting point for node classification. In contrast, Graph Transformers introduce significant computational complexity due to their reliance on global attention mechanisms [4], adding unnecessary overhead to the multi-part optimization task. While extending our method to Graph Transformers is an interesting direction for future work, it falls outside the current scope of our focus.

Accuracy without watermarking.

We have updated the paper (Table 1) to include accuracy rates in the absence of watermarking. For your convenience, we list them here. Note that accuracy rates are reasonable both with and without watermarking.

Thank you for your question. We address your question below.

Black-Box Explanations and Verification: Clarification

It is true that GraphLIME itself is an iterative, gradient-based process that requires white-box model access. To clarify, we do not directly apply GraphLIME: rather, the Gaussian kernel matrices used by GraphLIME inspire our closed-form regression problem. (We've revised our Introduction and Section 3.2 to emphasize this point.) This process takes node features and node predictions as inputs and outputs a feature attribution vector. Notably, it operates in a black-box setting, meaning it does not require access to the protected model's internal parameters. This query is highly-efficient, since the closed-form regression only requires a single query.

We welcome further questions on this topic.

Suggested Improvements

To address concerns about normality, we applied the Shapiro-Wilk test [1] to our Matching Indices (MI) distributions. Below are the average p-values from 5 trials for three GNN architectures. These results fail to reject the null hypothesis of normality.

Baselines and Robustness Experiments.

We aim to include these results as part of our broader revisions alongside other responses.

---

References

[1] Ghasemi, Asghar and Saleh Zahediasl. “Normality Tests for Statistical Analysis: A Guide for Non-Statisticians.” International Journal of Endocrinology and Metabolism 10 (2012): 486 - 489.

Comparison to EaaW

Thank you for the review and opportunity to address your concerns regarding our work’s relation to “Explanation as a Watermark” (EaaW) [1]. We address each of your key points below, outlining our contributions, differences, and similarities.

Contributions

• Watermarking in the graph domain. Our work fills a gap in the literature by extending explanation-based watermarking to the graph domain, requiring non-trivial adaptations for explanation generation and watermark alignment.

• Verification without reliance on ground truth. Our method avoids requiring a third party to know the ground-truth watermark, enhancing security by eliminating the need to share private information.

• Theoretical hardness of watermark identification. We prove that locating our watermarks is NP-hard, providing a formal guarantee of robustness.

Differences

• Domain-specific focus. Our work focuses on the graph domain, addressing structural relationships, multi-hop dependencies, and graph connectivity—challenges absent in the standard DNNs used in EaaW.

• Beyond LIME-Based Sampling. Unlike GraphLIME [2], LIME [3], and EaaW, we do not rely on local sampling around individual inputs. Instead, our target subgraphs consist of multiple disconnected nodes sampled from across the node classification network, reducing overlap with adversary-selected subgraphs. Additionally, we watermark only a selected subset of node features rather than the full feature signal, enhancing robustness and minimizing watermark size. To clarify, GraphLIME’s primary influence on our work lies in its use of Gaussian kernel matrices for regression, as described in Section 3.2.

• Regression input. EaaW’s regression inputs are binary masks isolating specific feature subsets from a single trigger sample, enabling targeted attribution analysis. In contrast, our regression takes a matrix of node features aggregated across disconnected nodes, capturing broader feature relationships in the graph domain.

• Disjoint training sets. EaaW optimizes for classification performance on a training set that includes the trigger sample. In contrast, our method uses disjoint subsets for classification and watermarking optimization; we found this separation was necessary for loss convergence.

• Verification method. Our method does not compare adversarial samples to a ground-truth trigger, instead requiring target subgraphs with maximally similar explanations.

Similarities

• Motive and high-level insight. Both works aim to address the limitations of backdoor-based watermarking by watermarking explanations. This does not undermine our originality, as the challenges of backdoor mechanisms are well-documented [4,5,6], providing a natural and necessary starting point to consider other embedding spaces, like explanations.

• High-level embedding approach. Both EaaW and our work use ridge regression and a hinge-like loss function to embed watermarks. We acknowledge this similarity and will cite EaaW in section 4.1 of our paper. However, our methodology diverges in domain, sampling, and verification.

---

We acknowledge that EaaW should have been cited. This omission was not intentional. Given the similar embedding approach, deliberately omitting citation would have been counterproductive; it was a mistake made during a time-constrained submission process, and we regret this oversight. While our embedding approaches overlap, our contributions lie in domain-specific adaptations, novel applications, and verification strategies. These distinctions will be clarified further in our revisions.

---

References

[1] Shao, Shuo, Yiming Li, Hongwei Yao, Yiling He, Zhan Qin, and Kui Ren. “Explanation as a Watermark: Towards Harmless and Multi-bit Model Ownership Verification via Watermarking Feature Attribution.” Proceedings of the Network and Distributed System Security Symposium (NDSS), 2025.

[2] Huang, Q. et al. “GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks.” IEEE Transactions on Knowledge and Data Engineering 35 (2020): 6968-6972.

[3] Ribeiro, Marco Tulio et al. ““Why Should I Trust You?”: Explaining the Predictions of Any Classifier.” Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2016): n. pag.

[4] Gu, Tianyu et al. “BadNets: Evaluating Backdooring Attacks on Deep Neural Networks.” IEEE Access 7 (2019): 47230-47244.

[5] Liu, Jian, Rui Zhang, et al. “False Claims against Model Ownership Resolution.” Proceedings of the USENIX Security Symposium, 13 Apr. 2023.

[6] Yan, Yifan, et al. "Rethinking {White-Box} Watermarks on Deep Learning Models under Neural Structural Obfuscation." Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23), 2023, pp. 2347–2364.

Dear Author(s):

Thank you for your response and the revisions made to the paper. I appreciate that the revised version now includes a comparison with our previous NDSS paper, and I am pleased to see that the contributions based on our work have been fairly presented. Given the methodological similarities between the two works, I believe such a discussion is indeed essential.

I also acknowledge the effort the authors have made in designing and implementing a watermarking solution specifically tailored for GNNs. As such, I respectfully request that the reviewers and area chair reconsider the contributions of this paper in light of the revised version.

PS: While I agree that the reviewers partially addressed my concerns about the methodology in terms of hypothesis testing, I still have some doubts about the comprehensiveness of the paper in terms of robustness. I suggest the authors conduct more adaptive attacks for discussion.

Best Regards,