KGMark: A Diffusion Watermark for Knowledge Graphs

Dear Reviewer voAk:

Thank you for your detailed and constructive feedback.

We note that your concerns mainly focus on four aspects:

• Scalability and generalizability of KGMark
• Comparative analysis
• Embedding strategy and robustness–transparency trade-off
• Presentation and writing quality

---

Dataset Scale and Heterogeneous

Scale and Generalization KGMark is evaluated on three large-scale, real-world knowledge graphs from diverse domains, ensuring both scalability and generalizability::

• Alibaba-iFashion: 1.21B user clicks from 5.54M users, 4.68M products, and 192K outfit sets. It supports both recommendation and compatibility prediction tasks, and has been deployed in real-world e-commerce systems.

• Last-FM: Combines user-tag data from Last. fm with the Million Song Dataset and playlists, covering 5,075 songs with emotion labels and 464K triples. It enables tasks like emotion classification and multimodal analysis.

• MIND: Includes ~1M users and 161K news articles with 2.4M click records and 512 relation types. It supports news recommendation, classification, and content-based cold-start modeling.

The variety in domains (fashion, music, news) and graph structures allows KGMark to be evaluated under diverse, realistic conditions, ensuring broad generalization ability.

Heterogeneous Graph Structures All datasets naturally exhibit heterogeneous characteristics. Nodes represent different entity types (e.g., users, products, songs, articles), and edge semantics vary (e.g., click, purchase, like). For example, MIND includes 512 relation types, indicating complex, multi-relational structures. Modeling these interactions requires a heterogeneous graph framework, which KGMark is designed to support.

---

Baselines

We have added additional experiments on the baselines, as presented in our response to Reviewer dihZ (Performance vs. Baseline) and zE4M (Adversarial Attacks).

---

Transparency Strategy

To further clarify the role of the adaptive mask matrix, we describe how it contributes to both the robustness and transparency of watermark embedding.

We aim to balance watermark detectability with minimal impact on downstream tasks by jointly minimizing reconstruction and task-related loss:

$$\mathcal{L} = \sum_{j \in [1, \mathcal{T}]} \left\| \mathcal{Z} _ {\mathcal{T}-k_j}^{\text{INV}} - f _ {\text{DDIM}}^{k_j} \left( f _ w(\mathcal{Z} _ \mathcal{T}^{\text{INV}}, \mathcal{S}, \mathbb{M}), \mathcal{T} \right) \right\|^2$$

In the refined objective, we introduce two key changes to improve both performance and efficiency:

1. While $f_w$ learns to embed the signature $\mathcal{S}$ via the mask $\mathbb{M}$, the resulting latent representation may deviate from the original, potentially altering structural information. To improve alignment, we introduce a correction term $\alpha \mathcal{S} \cdot \mathbb{M}$, which reduces the gap between the watermarked and original latent representations. This better alignment helps preserve the graph's inherent structure, indirectly supporting downstream task performance.

2. Since gradients on $\mathbb{M}$ accumulate across all diffusion steps, direct optimization becomes computationally intensive. To mitigate this, we adopt a "sample-then-embed" strategy. First sampling the latent representation and then applying watermark embedding which simplifies training and reduces complexity.

The resulting loss is:

$$\mathcal{L} = \sum_{j \in [1, \mathcal{T}]} \left\| \mathcal{Z} _ {\mathcal{T}-k_j}^{\text{INV}} - \left[ f _ w\left(f _ {\text{DDIM}}^{k_j}(\mathcal{Z} _ \mathcal{T}^{\text{INV}}, \mathcal{T}), \mathcal{S}, \mathbb{M}\right) + \alpha \mathcal{S} \cdot \mathbb{M} \right] \right\|^2$$

This formulation enables efficient optimization while enhancing the transparency of the embedded watermark.

Training Process of Adaptive Mask Matrix:

Another goal of the adaptive mask matrix is to improve watermark transparency without sacrificing robustness. As shown in Figure 3(c), the density of the watermark mask matrix is the primary factor affecting transparency.

In contrast, its impact on watermark detectability (i.e., robustness) is relatively minor. Based on this observation, LAWMM is designed to learn an adaptive mask matrix that maintains a fixed density while improving transparency through training. To ensure control over the final density, we regulate the number of training epochs. We find that setting the number of epochs to 50 yields an average density of approximately 0.015, which aligns with our desired sparsity level.

---

Writing Issues

In the revised version, we will carefully review the manuscript to correct any grammatical issues and improve overall clarity and writing style.

Your insights were extremely helpful in improving the presentation of our work. We hope the revisions and clarifications reflect the value of our contribution more clearly.

Dear Reviewer 1f2k:

We sincerely appreciate your thoughtful comments, which primarily concern the following three aspects:

• Design choices behind KGMARK

• Algorithmic ration for the redundant embedding strategy

• Consideration of computational efficiency

---

KGMark's Designing

KGMARK is specifically designed for knowledge graphs (KGs), which differ significantly from images or text in both structure and semantics. Traditional methods developed for images or text are difficult to apply to KGs due to their unique characteristics:

• Non-Euclidean topology: KGs lack the spatial continuity of images, making frequency or pixel-based watermarking inapplicable.
• High sensitivity to structural changes: Small perturbations can cause large semantic shifts.
• Large scale and sparsity: Real-world KGs require scalable and efficient embedding strategies.

Traditional watermarking techniques often assume dense and continuous data representations, making them ill-suited for the sparse and structured nature of KGs. These methods typically lack structural adaptability and fail to account for the non-Euclidean topology, rendering them vulnerable to perturbations such as isomorphic transformations or large-scale deletions. As a result, they often fail to ensure robustness or transparency in such settings.

For example, Gaussian-Shading is designed for image generation, where watermarks are embedded by modifying the initial latent noise during sampling. This approach relies on controlling the sampling process from the start. In our setting, however, the graph is already generated, and we recover its latent state via DDIM inversion. Applying Gaussian-Shading post hoc would overwrite the inverted latent representation and break the reconstruction process, making it incompatible with our framework.

KGMARK is thus tailored to address these challenges through graph-aware mechanisms. By leveraging graph alignment and community-based redundant embedding, it ensures both robustness and transparency under structural perturbations.

We further demonstrate the effectiveness of KGMark across multiple baselines, with detailed results presented in our response to Reviewer dihZ (Performance vs. Baseline).

---

Robustness Strategy

To ensure robustness against adversarial perturbations, we require that the amount of information retained about the original watermark $\mathcal{S}$ remains above a guaranteed threshold, even after the graph is modified. This is quantified by the mutual information between the original watermark and the extracted result under perturbation:

$$\inf_{\|\Delta A\|_0 \leq \delta} I(\mathcal{S}; T(\mathcal{G}^w + \Delta A)) \geq \beta$$

Here, $\Delta A$ denotes a bounded structural modification to the watermarked graph $\mathcal{G}^w$, and $T(\cdot)$ is the watermark extraction function. The inequality ensures that even under worst-case sparse attacks (e.g., modifying up to $\delta$ edges), the extractor can still recover meaningful information about $\mathcal{S}$.

To satisfy this robustness condition, we adopt a redundant embedding strategy that spreads the watermark across both global and local graph structures. Specifically, we partition the graph $\mathcal{G}$ into $l$ communities $\{ \mathcal{C} _ i\} _ {i=1}^l$, with vertices ranked by their centrality $\eta(v)$. The watermark is then embedded as:

$$\mathcal{W}(\mathcal{G}) = \bigcup _ {i=1}^l \Phi(\mathcal{C}_i) \cup \bigcup _ {v \in \mathcal{C}_i} \Psi(v)$$

Here, $\Phi(\mathcal{C}_i)$ encodes $\mathcal{S}$ into the structural signature of each community, while $\Psi(v)$ encodes it around high-centrality vertices. This dual-layer design ensures that the watermark is preserved even when parts of the graph are modified, thereby improving robustness by maximizing the information retained across complementary substructures.

To justify our choice of high-centrality vertices for embedding, we highlight three key considerations:

• We assume attackers aim to modify the graph without harming its usability, and thus tend to avoid high-centrality nodes.
• High-centrality nodes are structurally stable due to their dense connections, making embedded watermarks more resilient to local changes.
• Although community detection may vary across runs, unstable nodes are few and weakly connected. They are excluded from embedding, so this does not affect redundancy or robustness.

---

Time complexity

The computational cost of KGMark is primarily determined by the watermark embedding and optimization processes, with the majority of the time spent on DDIM inference. The runtime is directly correlated with the size of the knowledge graph.

$$AvgTimeCost = \frac{TotalTimeCost}{\text{Number of Nodes}}$$

To provide a more accurate evaluation, we will include the average runtime of KGMARK in the revised version.

We appreciate your detailed comments and hope our responses have clarified the key contributions and addressed your concerns.

Dear Reviewer dihZ:

We sincerely thank you for your constructive and thoughtful suggestions.

We understand that your comments mainly concern the following four aspects:

• The robustness of KGMARK under stronger adversarial attacks
• Concerns about KGMARK’s performance across datasets
• Explanation of the strategies in Learnable Adaptive Watermark Mask Matrix and Defending Isomorphism and Structural Variations
• Writing and presentation issues

---

robustness

Guided by the reviewer's suggestions, we have added experiments with stronger adversarial attacks([1], [2]) and included corresponding baselines([3], [4], [5], [6]). The results are presented in our response to Reviewer zE4M (Adversarial Attacks). We hope this clarifies the robustness of KGMARK.

---

Performance vs. Baseline

Guided by the reviewer's suggestion about KGMARK's performance across datasets, we have added comparisons with four watermarking baselines (two preprocessing-based, two diffusion-based).

We hope the results of these additional experiments demonstrate that KGMark consistently outperforms TreeRing (TR)[3], GaussianShading (GS)[4], both of which replace 5% of nodes with watermark data across multiple downstream tasks. DwtDct [5] and DctQim [6] are both frequency-domain post-processing watermarking techniques that embed watermark signals into transformed frequency coefficients, aiming to balance robustness and imperceptibility.

[3] Gaussian Shading: Provable Performance-Lossless Image Watermarking for Diffusion Models

[4] Tree-Ring Watermarks: Fingerprints for Diffusion Images that are Invisible and Robust

[5] Digital Watermarking and Steganography

[6] A class of provably good methods for digital watermarking and information embedding

---

Explanation of Strategies

A detailed explanation of the rationale behind KGMARK’s design is presented in our response to Reviewer 1f2k (KGMARK’s Designing).

We have also elaborated on the core strategies and their underlying motivations in our responses to Reviewer 1f2k (Robustness Strategy) and Reviewer voAk (Transparency Strategy).

In the revised version, we will revise the relevant sections(3.3 and 3.5) in the our paper to provide a clearer and more comprehensive explanation of both the learnable mask mechanism and the robustness design for handling isomorphism and structural variations.

---

Writing Issues

We sincerely appreciate your careful feedback and will make the following revisions in the final version:

1. Correcting the section reference in Figure 2.
2. Clarifying the duplicated variable usage.
3. Relocating the algorithm for better coherence.
4. Refining Sections 3.3 and 3.5 to improve clarity and readability.

We will thoroughly proofread the paper and clarified the sentences.

We thank the reviewer's helpful suggestions. The negatives pointed out by the reviewer are very insightful and have inspired us to reflect more deeply on our paper. We believe that the revisions have strengthened our paper.

Dear Reviewer zE4M:

We appreciate your insightful comments, which mainly focus on:

• Empirical validation under stronger adversarial attacks

• Clarification of the limitations of KGMARK

• Discussion of KGMARK’s role in privacy protection for sensitive data

---

Adversarial Attacks

We have incorporated two recent and stronger adversarial attacks NEA[1] and L2 Metric [2] into our evaluation. In the following table, we retain the original five high-intensity attacks, introduce two additional adversarial attack types, and evaluate KGMark against four newly added baseline methods. The results show that KGMARK consistently outperforms four baseline methods acrosss three dataset, demonstrating superior robustness.

We also highlight that the robustness enhancement in KGMARK allows it to retain watermark fidelity even under high-intensity perturbations (e.g., random deletion of 50% of entities), where baseline methods fail significantly. Another interesting observation is that while KGMark shows better performance than the baselines under low-intensity attacks (to be detailed in the extended version), its robustness remains relatively stable as the attack strength increases. In contrast, most baselines exhibit noticeable performance degradation under higher levels of perturbation.

[1] Node embedding attacks via graph poisoning (NEA)

[2] knowledge graph embedding attacks via instance attribution methods

---

Limitations

While the embedding dimensionality may influence the balance between watermark detectability and downstream performance, this can be mitigated through adaptive tuning in future work. Additionally, extending our DDIM-based framework to support newer sampling strategies is a promising direction we plan to explore.

---

Privacy Protection

When (KGs) involve sensitive information, they face several privacy risks:

1. Tampering risk: Attackers may alter the generated graph to inject harmful content, potentially leaking sensitive information.
2. Disturbing sensitive subgraphs: Even with structure-aware embedding, watermarking may affect subgraphs involving sensitive entities.
3. Key misuse: If the watermark key is exposed, it could be exploited for data tracing or structural inference.

KGMARK incorporates embedding-level mechanisms to mitigate the above risks and enhance privacy protection. Moreover, KGMark is model-agnostic and can be easily integrated into existing knowledge graph embedding (KGE) frameworks. This compatibility enables combination with complementary privacy-preserving techniques (such as differential privacy) to achieve multi-layered protection.

We sincerely appreciate your valuable feedback, which has helped us improve the quality and clarity of our work. We hope our responses have addressed your concerns and clarified the contributions of our paper.