KGMark: A Diffusion Watermark for Knowledge Graphs
Authors: Hongrui Peng
Haolang Lu
Yuanlong Yu
WeiYe Fu
Kun Wang
Guoshun Nan
Venue: ICML 2025 poster (2025)
Keywords: Watermarking
Knowledge Graph
Diffusion Models
Generative Models
Primary area: social_aspects->fairness
TL;DR: We present KGMark, the first watermarking method for knowledge graph embeddings that ensures high detectability, transparency, and robustness across various graph modifications.

Abstract: Knowledge graphs (KGs) are ubiquitous in numerous real-world applications, and watermarking facilitates protecting intellectual property and preventing potential harm from AI-generated content. Existing watermarking methods mainly focus on static plain text or image data, while they can hardly be applied to dynamic graphs due to spatial and temporal variations of structured data. This motivates us to propose KGMark, the first graph watermarking framework that aims to generate robust, detectable, and transparent diffusion fingerprints for dynamic KG data. Specifically, we propose a novel clustering-based alignment method to adapt the watermark to spatial variations. Meanwhile, we present a redundant embedding strategy to harden the diffusion watermark against various attacks, facilitating the robustness of the watermark to the temporal variations. Additionally, we introduce a novel learnable mask matrix to improve the transparency of diffusion fingerprints. By doing so, our KGMark properly tackles the variation challenges of structured data. Experiments on various public benchmarks show the effectiveness of our proposed KGMark.

KGMark: A Diffusion Watermark for Knowledge Graphs
Hongrui Peng Haolang Lu"
Yuanlong Yu'
Weiye Fu'
Kun Wang² 2
Guoshun Nan
Abstract
KGMark
Watermark Transparency aosesues the impart of watermeking on the kntosedge graphis usasilty, ensuring minisl disuptionn
AMAL
DS3
Input Graph 5
Embedding
1771
1715
Knowledge graphs (KGs) are ubiquitous in nu- merous real-world applications, and watermark- ing facilitates protecting intellectual property and preventing potential harm from Al-generated con- tent. Existing watermarking methods mainly fo- cus on static plain text or image data, while they can hardly be applied to dynamic graphs due to spatial and temporal variations of structured data. This motivates
Graph
Weterman
Tronsporency
Embedding G.t Embedding Cu2 Embedding Gug KGMark Extract Watermark DetoctabilRt
the identilying the watermaris presence.
Detectobility
DETECTED
propose KGMark, the first graph watermarking framework that aims to gen- erate robust, detectable, and transparent diffusion fingerprints for dynamic KG data. Specifically, we propose a novel clustering-bast based alignment method to adapt the watermark to spatial varia- tions. Meanwhile, we present a redundant embed- ding strategy to harden the diffusion watermark against various attacks, facilitating the robustness of the watermark to the temporal variations. Ad- ditionally, we introduce a novel learnable mask matrix to improve the transparency of diffusion fingerprints. By doing so, our KGMark properly tackles the variation challenges of structured data. Experiments various public benchmarks show the effectivenesss of our proposed KGMark.
Input Graph f
KGMark Embedding
KGMark Extract
Watermark Robustness
svaliaatis watermani's restisnne to attacka,
ensuring durobility integrty
AGAINST ATTACTER
X Robustness
Figure 1. Overview of our KGMark. KGMark implements a KGE watermarking scheme that preserves transpareney, enables reliable detection, and remains robust against various post-editing attacks.
swering (Yin et al., 2024; Zhou et al., 2024), and recom- mendation systems (Fan et al., 2019; Wang et al., 2019). Deep learning- based models such as GraphRNN (You et al., 2018), Graph VAE (Simonovsky & Komodakis, 2018), Mol- GAN (Cao & Kipf. 2022), and DiGress (Vignac et al., 2023) have emerged as powerful tools for generating high-quality synthetic graphs, supporting applications such as graph clas- sification, molecular design, and prrseure-preserving data augmentation in machine learning pipelines.
1. Introduction
However, existing synthetic graph generation methods may inadvertently embed biases (Shomer et al., 2023; Dong et al., 2022) or misleading (Yang et al., 2024a) information and are vulnerable to malicious alterations by attackers (Zhang et al., 2019), potentially introducing harmful content that compro- mises analyses even facilitates the exploitation of real- world systems (Jiang et al., 2024; Wang et al., 2025). Fur- thermore, presenting synthetic graphs as original research can violate intellectual property rights, undermining trust in academic and commercial environments (Smits & Borghuis, 2022: Zhu et al., 2024b). Ensuring traceability, integrity, and copyright protection of synthetic counterparts causes a significant amount of compute and memory footprints due to the notorious designs (LIANG et al., 2024; Charpenay & Schockaert, 2025), which even unnerves large corporations, let alone individual researchers.
The growing adoption of generative models has signifi- cantly expanded the creation and utilization of synthetic data (Bauer et al., 2024), including structured formats such as time-serics data (Das et al., 2024), tabular data (Vero et al., 2024), and graphs (Han et al., 2025; Wang et al., 2023). Among these, Knowledge graphs (KGs) (Ji al., 2022) especially crucial due to their ability repre- sent complex relationships and semantic hierarchies (An et al., 2025), making them indispensable for applications such as semantic search (Chen et al., 2024), question an-
'Equal contribution 'Beijing University Of Posts and Telecom- munications, Beijing, China *Nanyang Technological Univer- sity, Singapore. Correspondence to: Guoshun Nan <nan- guo2021 I @ bupp.edu..n..... Kun Wang <wang ntu.edu.sg>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Watermarking techniques (Radford et al., 2021; Podell et al., 2023) have proven to be effective in ensuring the authentic-

---

KGMark: A Diffusion Watermark for Knowledge Graphs
ity of synthetic data in image and text generation (Wen et al., 2023; Zhao et al., 2023a). However, off-the-shelf water- marking algorithms (Liu et al., 2024) appear to lag behind in the era of graph structures, despite their increasing impor- tance in various domains. This gap makes watermarking for KGs an unsolved and looming challenge.
rior performance of KGMark, showing its robustness, transparency, and high detectability across various post- editing attack scenarios.
2. Related Work
2.1. Watermarking Al-generated Content
The core challenges of graph watermarking lie in achieving robustness against spatial-temporal variations and maintain- ing transparency. Embedded watermarks must preserve KG semantics while resisting structural perturbations caused by dynamic node/edge updates (c.g., temporal evolution in recommendation systems (Wang et al., 2019)) and graph isomorphism (e.g.. node relabeling or spatial rearrange- ments (Bouritsas et al., 2023)). Conventional watermarking methods (Bouritsas al.. 2023), designed for static and unstructured data, often exhibit limited robustness under the spatial-temporal variations of dynamic KGs, posing chal- lenges in mitigating risks of Al-generated KG misuse (Liu et al., 2025). The inherent heterogeneity of knowledge graphs further necessitates embedding watermarks at the knowledge graph embedding (KGE) level to reconcile se- mantic fidelity with detection resilience (Le et al., 2024).
As Al technologies continue to evolve and generate increas- ingly sophisticated content, the necessity for robust wa- termarking solutions for Al-generated content has gained prominence (Zhao al., 2023b; Zhu et al., 2024a). This technique serves critical role in addressing issues such as copyright infringement (Zhang et al., 2024b), misinfor- mation, and the ethical implications surrounding the use of Al in creative processes. In particular, watermarking helps to distinguish Al-generated work from human-created con- tent (Asnani et al., 2024), thereby enhancing credibility in the digital landscape (Barman et al., 2024).
2.2. Watermarking Synthetic Unstructured Data
Watermarking synthetic unstructured data, such as plain text (Dathathri et al., 2024) and images (Zhang et al., 2024a; Wen et al., 2024), is crucial for ensuring data integrity, pro- tecting intellectual property, and preventing misuse. Com- mon methods include pre-applying watermarks to train- ing datasets, enabling models to generate inherently wa- termarked data (Yu et al., 2021; Zhao et al., 2023c), or modifying the sampling process in large language models to subtly alter output word distributions and encode water- marks (Kirchenbauer et al., 2023). A widely used approach in diffusion models involves embedding watermarks into the initial noise vector or latent space without retraining (Wen et al., 2024; Yang et al., 2024b; Yang. 2024), ensuring trans- parency and robustness through reversibility. In this work, we conduct the first systematic exploration of adaptively incorporating this method into knowledge graphs.
To address these challenges, we propose KGMark, the first watermarking scheme specifically designed for knowledge graphs, based on diffusion models. KGMark employs graph alignment with a learnable mask matrix to spatially adapt watermarks to structural variations, ensuring seamless inte- gration between topology and embedded signals. For tem- poral robustness, we design redundant embedding strategies coupled with likelihood estimation, enabling resilient extrac- tion despite incremental graph updates. KGMark requires no prior assumptions about graph stability or isomorphism, making it agnostic to node ordering and scalable to evoly- ing KGs. The watermark is detectable exclusively through secure keys, ensuring resistance to adversarial attacks while preserving KG utility (Nandi et al., 2024).
3. Proposed Method: KGMark
Through rigorous testing, we demonstrate that KGMark achieves: high detectability, with a watermark detection AUC up to 0.99; @ maintaining KG quality and limiting downstream task performance loss to within the range of 0.02% ~ 9.79% 9,; and @ high robustness, retaining an AUC of around 0.95 against various post-editing attacks.
3.1. Preliminary of Latent Diffuusion Model
The core idea of the Diffusion Model can be summarized in two phases: the forward diffusion process and the reverse diffusion process (Chang et al., 2023; Rombach al., 2021). In the forward diffusion process, the latent representation Zo is progressively corrupted by Gaussian noise over T steps, resulting in:
Briefly, our key contributions are summarized follows: We introduce KGMark, the first watermarking scheme de- signed for KGE, embedding robust and transparent water- marks into graph structures protect intellectual property and ensure data integrity.
((1 = N(Z;; (1
(1)
As - T, 2T converges to an approximate standard Gaus- sian distribution. The reverse diffusion process starting from noise ZT, the model denoises it step-by-step to recover Zo:
We propose effective solutions to key challenges, in- cluding redundancy- embedding and the Learnable Adaptive Watermark Matrix, which significantly enhance the performance of KGMark
N(Zz-11 t), (Z,, t))
(2)
We demonstrate through rigorous experiments the supe-
Our method employs a latent diffusion model (LDM) with
2

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Target KG
Community Subgraph
Aligned Subgraph Embedding
Mask&Signature
O
/
Sec 3.5
Sec 3,5
Community
Alignment
Encoder
detection
DDMI
Noise Vector
8 p 0.87
Sec
8 P2= 0.98
Sec 3
Rolation
Atteration
8
8 -3= null
Extract
Attack
Decoder
Any a?
Embedded Noise Vector
WATERMARK DETECTED
DDMI
Isomorphic Variation
Subgraph Deletion
Attacked Graph
Watermarked Graph
Figure 2. Pipeline of the proposed KGMark. The target KGE undergoes community detection and alignment before watermark embedding, enabling robust watermark extraction under attacks (Relation Alteration, Suhgraph Deletion, and Isomorphic Variation).
DDIM (Song al., 2022) for sampling. DDIM's determin- istic inversion process allows efficient recovery of the initial noise vector z which is then used for watermark embed- ding, ensuring imperceptibility and integrity preservation in the latent space. The precise control offered by DDIM's reverse diffusion process is key to balancing watermark robustness and reconstruction fidelity.
function. The attack objective is then formulated as:
min si + 5), +
Σ 1 lg
(5)
where sim(..) denotes a similarity measure, and y is a trade-off parameter that controls the allowed perturbation budget. successful attack reduces the similarity score while maintaining the semantic validity of subgraphs.
3.2. Overview of KGMark
As illustrated in Figure 2, isomorphic variations preserve local subgraph structure, while stronger perturbations com- promise the global topology. This highlights another unique characteristic of graph- based watermarking: the adversary can strategically degrade global structural fidelity while preserving local usability.
The proposed watermarking framework embeds a water- mark into a KGE & = EV, The process begins by encod- ing 9 into latent representation Zu using a graph encoder, trained under a VAE framework.
Watermark Embedding: A signature S is embedded into designated latent subspaces:
Watermark Extraction: For watermark extraction, G is encoded and inverted to approximate ZINY The Fourier transform of ZINV is computed as:
A = F ((2 - M)) + F(S)-M, M
(3)
where F(-) denotes the Fourier transform, and M a mask matrix defining embedding regions for S. The watermarked latent vector is then derived via inverse Fourier transform:
y = FZNNN s.t. BDI] 14, Var[D.] =
of
(6)
A test statistic T computed by comparing ) with (S. M)).
z = =- S S~1(00,21))
(4)
The P-value is evaluated using noncentral x² distribution, and the watermark is detected if the P-value is below a predefined significance level.
Where 2 determines the variance of the normal distribution. 2y undergoes reverse diffusion, yielding 2 which is decoded to reconstruct the watermarked graph g
fulfill the three essential properties of watermarking transparency during embedding, robustness against ad- versarial perturbations, and detectability upon extraction, KGMark introduces three dedicated designs across the em- bedding, extraction, and attack resilience stages.
Attack Modeling: We define the attack intensity by the total perturbation 8 applied to the graph G, where 5 Σ. 6c. and each åe denotes the perturbation (e.g., post- editing operations) applied to a subgraph Goub-
The adversary aims to invalidate the watermark by reducing the similarity between the extracted watermark and the orig- inal signature S. Let (()) denote the watermark extraction
Specifically, we present: (1) a Learnable Adaptive Water- mark Mask Matrix (Sec. 3.3) to ensure transparent water- mark embedding, (2) a Defending Against Isomorphism and
3

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Structural Variations module (Sec. 3.5) enhance water- mark robustness under perturbations, and (3) Likelihood- Based Watermark Verification mechanism (Sec. 3.4) validate the embedded watermark.
To characterize the sparsity of the learnable mask matrix M. we define its density as:
j==1 Mij
(e
(10)
m7
3.3. Learnable Adaptive Watermark Mask Matrix
where m n is the total number of elements in M. This met- ric quantifies the proportion of nonzero entries, balancing watermark imperceptibility and robustness against attacks.
Principle 3.1 (Latent Space Equilibrium), To preserve the latent space equilibrium during watermark embedding, we decompose the total perturbation into two parts: (1) the inherent noise from DDIM inversion, and (2) the additional distortion from watermark embedding. Let -k, be the
During watermark extraction, we evaluate all candidate Ml. The decision rule is formulated as Equation (11):
kk,
kj step latent from DDIM inversion, ΣT-N, the latent from DDIM without watermark, and -k; the latent with wa- termark. The total deviation satisfies:
Gelassified = [T. 3... (ML, 9), (M) <
(II)
[1. VM, (M,, > 8
where fee (a(M, g) denotes the extracted signature from G
ZINV ŽT- -2 -ks
17 2T -kg SE.
using matrix M, d(.,-) is the distance metric quantifying the difference between signatures, and ó is the threshold determining signature validity.
DDIM sampling loss
Watermark embedding loss
(7)
This formulation isolates the unavoidable sampling error from the controllable embedding distortion, guiding water- mark design to minimize overall latent drift.
3.4. Likelihood- Watermark Verification
In KGMark, watermark detection utilizes likelihood ratio test, where the null hypothesis Ho assumes the noise vector Y follows Gaussian distribution NO, x²Ic). Under the alternative hypothesis Hi, the graph contains a watermark, introducing a detectable deviation from this distribution.
To operationalize Latent Space Equilibrium, we design a learnable masking mechanism that controls how water- mark signals are injected into the latent space. Watermark embedding inevitably introduces reconstruction loss L for g. quantified by the discrepancy between the z and 24 (Fridrich al., 2002). Specifically, we introduce a learnable, adaptive mask matrix M. optimized for the struc- ture of G. Ml is trained to minimize L in Equation (8), which quantifies the discrepancy between the Z!NV and zy.
To integrate the distance metric d(s,-) and the signature extraction function Sex. we define the residual vector R as the difference between the extracted signature and the optimal reference signature K E S:
R [Mx 9) K*
(12)
The distance metric .(: thus measures the magnitude of R. which quantifies the deviation between the extracted sig- nature and the expected reference signature. The likelihood of observing R under Ho is given by Equation (13):
C Σ JE[L.T]
, - -DDIM (Z (((IIN,,SM))) M,M,,,77 7) ||
(8)
where T denotes the total diffusion steps, and ky satisfies 0 < ki T. The function fw represents the watermark em- bedding function, while f denotes the DDIM sampling process at time step kj-
(- |2, 20
[(R|H0) = II
exp
(13)
VTT22 VEM V
where a² = 1 EiEM |2 is the estimated variance of the residual vector, computed as the mean squared deviation of the residuals within the mask region MI.
To further refining, we adopt a "sample-then--ee eebeed" strat- egy with a correction term aSS. Ml (a is a tunable coefficient), ensuring better alignment in the latent space.
The likelihood ratio test statistic À is defined as the logarith- mie ratio of the likelihoods under Ho and Hi:
L=
Σ :E(I.T]
INV
A = 2=-21op supHo C(R(Ho)
(9)
(14)
[n (JR (ZINV S),S M) + aSS Mi] ["
supR, L(R(7L,)
For watermark detection, we employ a simplified test statis- tic Í. defined in Equation (15), which directly quantifies the deviation of R. from the expected values under Ho:
As L shown in Equation (9), ~ (O I) represents a noise vector sampled from standard normal distribution, where I is the identity matrix. The adaptive nature of M ensures that it is specific to each graph G, making the watermark embedding robust to structural variations.
=
1
Σ
R2
1.
(15)
σ²
iEM
4

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Under Ho. T follows noncentral chi-squared distribution with degrees of freedom [M| and noncentrality parameter A + >. K2 (Patnaik, 1949). The p-value for wa- termark detection is then calculated using the cumulative distribution function (CDF) of this distribution (Glasserman, 2004), as shown in Equation (16):
The local term ||A - Ålle captures edge-level modifica- tions, including Gaussian noise, Relation Alteration, and Triple Deletion. The global term || - L'Il2 reflects low- frequency structural changes often introduced by smoothing attacks that diffuse information across the graph (Table 1).
Principle 3.2 Infformation-Thhrreee Robustness). The watermark embedding W must ensure that the mutual infor- mation ( + =A)) between the original watermark S and the extracted signature under attack satisfies:
p= Pr (MMMAA S T
Ho)
IKI
+ A
(16)
exp
dx.
Jo I
M 2
2
inf 1(S:T(9" + +AA)) 23 AA
(19)
If the p is below a significance level a, 9 is considered wa- termarked; otherwise, the null hypothesis Ho is not rejected.
where 3 > O is a lower bound guaranteeing detectable information retention. This is achieved by enforcing that the watermark encoding W(G) maximizes the effective in- formation capacity C(W) under adversarial constraints:
3.5. Defending Isomorphism and Structural Variations
Real-world graph upplications encounter isomorphism and structural variations, which are unique graph-structured data and can be exploited for attacks (Yu et al., 2023). Isomorphism refers to graphs that preserve their overall structural connectivity but differ in node ordering or node- specific properties. Structural variations involve more sub- stantial modifications that can alter the graph's topology or the relationship between nodes. See Appendix A for details.
C(W) = min [H(S) H(S T( + +AA)).. ((0)
AA
where H-) denotes entropy. The principle mandates that critical graph substructures (e.g.. high-centrality commu- nities) encode S with minimal entropy loss HSS (T{))), ensuring robustness against D)
To satisfy Principle 3.2, we partition G into I communi- ties {= with vertices ranked by centrality ny()). The watermark is embedded as:
Isomorphism Variations: Graph isomorphism (Yan & Han, 2002) transformations alter the latent space represen- tation 2g of a graph, despite preserving its inherent proper- ties (Bouritsas et al., 2023). To address this, we ensure 20 remains invariant under adjacency matrix reorderings via a graph alignment procedure. Let V(G) denote the set of vertices, and A the adjacency matrix. Vertices are reordered by degree deg(v:) and clustering coefficient C(v:):
W(G) Ü ( U im1
(21)
vEC;
where (C,) injects S into the community's spectral profile
(resilient to 1 - 1l and V(u) encodes S via edge- weight distributions around high-centrality vertices (resis- tant to || - Al) This dual encoding maximizes C(W) by distributing S across both low-frequency (global) and high-frequency (local) structural invariants.
deg(v:) > deg(v;) = i< deg(v;) = deg(w;) - C(v,) 2 C(vy).
(17)
Graph attributes (vertex features, edge weights, adjacency matrix) are adjusted to the new vertex order, preserving structural consistency.
4. Experiments
The experimental evaluation of KGMark assesses its effec- tiveness in terms of watermark transparency, detectability, and robustness across various attack scenarios and datasets.
Let AA E 10 1|nxn denote the perturbation matrix, where AAol quantifies the attack intensity as the number of edge modifications. Structural variations introduce perturbations multiple scales of graph topology, formalized by the divergence metric:
Structural Variations:
4.1. Experiment setup
Datasets. We evaluate our approach using three public datasets representing diverse real-world scenarios: Last-FM (music) (Çano et al., 2017), MIND (news) (Wu et al., 2020), and Alibaba-iFashion (e-commerce) (Chen et al., 2019). Table provides summary of these datasets.
D(g.))= = |A- All +a L -''-
(18)
local perturbations
global spectral shifts
where Lt is the pseudoinverse of the graph Laplacian L, and a balances local and global contributions. This diver- gence aligns with the attacker's objective in Equation (5), where the constraint |All < limits the attack inten- sity, and (T + S) measures degradation of the extracted watermark.
Variants. Since KGMark is the first watermarking scheme for Knowledge Graph Embedding (KGE), we explored mul- tiple variants in the experiments. W/O LAWMM: Using a fixed watermark mask matrix with the same density, in- stead of applying the Learnable Adaptive Watermark Mask
5

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Table 1. Watermark Detectability & Robustness (Relation Alteration, Triple Deletion, two adversarial attacks (1.2 Metric, NEA), Isomor-
phism Variation (Iso.a))). We evaluate the detectabiliit of the watermark under clean samples and its robustness under editing attacks with structural and isomorphism variations. Includes four baselines and three variants compared with KGMark.
Relation Alteration
Triple Deletion
Adversarial
Datasets
Method
Clean
Iso Iso
Avg
10%
30%
50%
10%
30%
50%
1.2 Metric
NEA
DwtDet
0,9837
0,9730
0,8813
0.8371
0.9457
0.8577
0.7724
0.9577
0,9638
0.6039
0.8776
DetQim
0,9749
0.9548
0,8623
0.8139
0.9121
0.8049
0.7073
0.9203
0,9278
0.5867
0.8465
TreeRing
0,9814
0.9207
0.8321
0.7392
0.9442
0.8599
0.8091
0.9621
0.9584
0.6257
0.8632
GaussianShading
0,9882
0.9481
0,8745
0.7998
0,9217
0.8846
0.7850
0,9364
0.9512
0.6094
0.8699
AliF
W/O LAWMM
0,9980
0,9623
0,9352
0.9147
0.9795
0.9592
0.9341
0.9817
0.9706
0.9895
0,9625
Only CL
0.9942
0.9537
0,9216
0.8864
0.9214
0.8745
0.8063
0.9426
0,9535
0.9635
0.9218
Only VL
0,9828
0.9765
0,9433
0.9172
0,9670
0.9148
0,8592
0.9521
0.9676
0,9787
0,9459
KGMark
0.9991
0.9810
0.9564
0.9207
0.9829
0.9669
0.9320
0.9841
0.9809
0.9933
0.9697
DwtDet
0.9793
0.9563
0.8827
0.8161
0.9334
0.8413
0.7610
0.9358
0,9291
0.6348
0.8669
DetQim
0.9785
0.9542
0,8703
0.8269
0.9046
0.8071
0.6993
0.9209
0.9198
0.5708
0,8452
TreeRing
0,9862
0.9128
0.8554
0.8171
0.9704
0.8617
0.7831
0.9682
0.9543
0.5763
0.8685
GaussianShading
0,9903
0.9076
0.8455
0.7930
0.9334
0.8746
0.8284
0.9767
0,9681
0.5845
0.8702
MIND
W/O LAWMM
0,9984
0.989
0.9743
0,9335
0.9895
0.9609
0.9328
0.9915
0,9864
0.9705
0.9727
Only CL
0,9973
0.9792
0,9515
0.9287
0.9624
0.9074
0.8449
0.9697
0.9713
0,9846
0.9497
Only VL
0,9956
0,9814
0.9658
0.9346
0,9647
0.9154
0.8804
0.9683
0,9618
0,9861
0.9554
KGMark
0.9987
0.9907
0.9751
0,9314
0.9781
0.9726
0.9576
0,9849
0.9883
0,9842
0,9762
DwtDet
0,9801
0.9636
0,8834
0,8229
0.9570
0.8353
0,7415
0.9596
0.9678
0.6407
0.8752
DetQim
0,9842
0.9527
0.8773
0.8062
0,9083
0.7972
0.7125
0.9144
0.9161
0.5938
0.8463
TreeRing
0.9879
0.9167
0,8353
0.7982
0,9316
0.9024
0.8519
0.9553
0.9487
0.6109
0,8738
GhussianShading
0.9795
0.9356
0,8658
0,8303
0.9519
0.9145
0.8667
0.9638
0,9594
0.6551
0.8922
Last-FM
W/O LAWMM
0.9982
0.9929
0,9857
0,9468
0.9785
0.9420
0.9057
0.9794
0,9852
0.9970
0,9711
Only CL
0.9962
0,9893
0.9367
0,9073
0.9773
0.9206
0.8737
0.9156
0.9205
0.9901
0,9427
Only VL
0.9929
0.9726
0.9308
0.9034
0,9824
0.9275
0.8661
0,9053
0.9112
0,9912
0,9383
KGMMrk
0.9976
0.9973
0.9844
0,9421
0.9796
0.9350
0.9031
0,9886
0,9814
0.9977
0.9707
Table We use three KG datasets from different domains.
series of related experiments is carried out. All experiments are conducted on single NVIDIA A800.
Name
Entities
Relations
Triples
Alibaba-iFashion (AliF)
59,156
51
279,155
MIND
24,733
512
148,568
4.2. Defectability
Last-FM
58,266
464,567
To evaluate the detectability of KGMark, we calculate the false positive rate (FPR), true positive rate (TPR), and their corresponding average AUC values, as summarized in Ta- ble 1. The evaluations are conducted under a configuration where the DDIM inference steps are set to 75, and the pre- defined significance level is fixed at 5 x 10-5, To further ex- amine the impact of significance levels and DDIM inference steps on watermark detectability, we perform controlled experiments by varying these parameters.
Matrix (LAWMM). @ Only CL: Applying the watermark exclusively in the Community Layer, selecting specific ver- tices vertex groups within each community. 2 Only VL: Applying the watermark exclusively in the Vertex Layer, selecting multiple vertices or vertex groups within a specific community. O W/O Watermark (Control): Reconstruct- ing the knowledge graph without any watermark.
Baselines. As the first watermarking framework designed for diffusion KGE, we introduce four additional baselines to validate KGMark's 's effectiveness. TreeRing (Wen et al., 2023) and GaussianShading (Yang et al., 2024b) are node- level watermarking methods designed for diffusion models (Images), embedding watermarks by replacing 5% of nodes in the graph. DwtDet (Cox et al., 2007) and DetQim (Chen & Wornell, 2001) are classical watermarking techniques that modify transformed coefficients to balance imperceptibility and robustness.
Table summarizes the detection performance of KGMark under various attack scenarios. Across all settings, KGMark consistently maintains high detectability. We also evalu- ate an ablated variant (W/O LAWMM) that removes the Learnable Adaptive Watermark Mask, which is designed to preserve transparency while balancing embedding de- tectability. Interestingly, this variant cxhibits slightly higher detectability in some cases, likely due to stronger watermark signal strength without the masking constraint. However, the full KGMark still achieves comparable superior per- formance overall. This result also highlights the effective- ness of LAWMM in achieving favorable trade-off between watermark detectability and semantic transparency.
Implementation details. We first employ the RotatE (Sun et al., 2019) model to embed the knowledge graph, with an embedding dimension of 4096. Our watermarking method applied to the above-processed datasets, and subsequent
6

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Table Watermark Transparency. evaluate transparency of watermarking from two dimensions: the similarity knowledge graph embedding before and after watermarking and the quality of watermarked knowledge graph. We mark the best transparency score only for the four baselines and two KGMark variants, the original KG and W/O Watermark serve as control groups.
Cosine Similarity
KG Quality Metrie @ 75 Steps
Datasets
Method
50 Steps
65 Steps
75 Steps
GMR +
HMR +
AMR 4
Hils@ 10 f
Original KG
1.828
1.162
135,459
0.8980
W/O Watermark
0.7971
0.8797
0.9674
3.026
1.579
141.412
0.8318
DwtDet
0.7215
0.7928
0.8251
5.096
1.699
157.036
0.6933
DetQim
0.7509
0.7633
0.7653
5.104
1.654
161.142
0.7385
AliF
TreeRing
0.7761
0.8431
0,9071
3.928
1.618
152.634
0.8017
GaussianShading
0.2879
0.3226
0.3538
6.641
1.798
172.813
0.5137
W/O LAWMM
0.7662
0.7838
0.8643
3,457
1.624
147.305
0.7871
KGMark
0.7839
0,8309
0.9482
3.046
1.580
141.904
0.8296
Original KG
7.197
1.975
155.656
0.6649
W/O Watermark
0.7345
0.8290
0,9579
9.853
2.215
168,906
0,5734
DwtDet
0.7831
0.8244
0.8312
11.328
2.328
188.992
0.5216
DetQim
0.7549
0.7574
0.7703
12.037
2.753
205.485
0)48335
MIND
TreeRing
0.7976
0.8108
0.8581
11.102
2.297
182.925
0.5108
GaussianShading
0,2843
0.3196
0.3728
14.523
3.312
234.064
0,3940
W/O LAWMM
0.7469
0.8235
0.8902
10.819
2.238
173.194
0.5332
KGMark
0.8083
0.8533
0.9397
10.508
2.226
169.305
0.5683
Original KG
3.571
1.202
1711.695
0.8436
W/O Watermark
0.8293
0.9157
0.9410
4.455
1,452
1715.907
0.8431
DwtDet
0.7215
0.7928
0.8433
4,519
1,502
1734.823
0,8221
DetQim
0.7509
0.7633
0.7679
5.139
1.704
2043.249
0.7264
Last-FM
TreeRing
0.7262
0.7896
0.8364
4.733
1.652
1772.961
0,8149
GaussianShading
0.3252
0.3649
0.4184
6.349
2.016
2192.492
0.6463
W/O LAWMM
0.7628
0.8809
0.8948
4.456
1.452
1716.828
0.8430
KGMark
0.8876
0.9051
0.9161
4.455
1.452
1716.365
0.8430
Obs.0 KGMark's detectability remains consistently high with optimal DDIM steps and significance levels. Figure 3a illustrates the impact of significance levels and DDIM inference steps on the AUC values. Within the signif- icance level range of le - le - 4, increasing the DDIM steps significantly enhances detection performance by re- ducing watermark information loss. Meanwhile, the AUC values remain exceptionally stable, approaching for con- figurations with higher steps, highlighting KGMark's 's robust and consistent performance under suitable conditions.
However, inconsistencies between embedding and detec- tion steps introduce minor declines in performance, seen in higher-step configurations where AUC decreases from 0.99785 ~ 0.9967. This highlights the critical importance of alignment between the two stages. Notably, the detec- tion stage exerts a more significant influence on watermark retrieval accuracy, reinforcing the need for fine-grained con- trol this stage achieve optimal detectability.
4.3. Transparency
We evaluate the transparency of KGMark, which measures the extent to which the watermark preserves the structural and functional integrity of the original KGE.
However, for higher significance levels 1e-3 3 ~ 1e 2, the AUC values drop more sharply. This decline attributed to higher inference steps reducing p-values for negative samples, thereby increasing the false positive rate (FPR) and accelerating the drop in detection accuracy.
Obs. G KGMark achieves strong transparency by mini- mally impacting KG structure and usability. As shown in Table 3, KGMark achieves high cosine similarity scores (e.g., 0.9482 for AliF at 75 steps) compared to the non- watermarked version, indicating that the watermark does not significantly distort the KG's inherent relationships. This demonstrates that the watermark is seamlessly integrated without disrupting the KG's core structure.
Obs. Increasing detection-stage DDIM steps boosts detectability, while stage alignment further enhances performance. Results in Figure 3b demonstrate that higher DDIM steps detection stage yield marginal improve- ments AUC, with values consistently exceeding 0.996 across most configurations. For example, as detection steps increase from lower to higher ranges, the AUC improves slightly, showcasing the positive impact of precise parameter tuning during detection.
To further evaluate the KG's quality post-watere nost-watermarking. we measure forecast task performance using GMR, HMR, AMR, and Hits 10 metrics. KGMark's 's results are nearly

---

KGMark: A Diffusion Watermark for Knowledge Graphs
0.96
1,00
0.98
Embeddiing-Tmg Staps
70
75
0.998
1.000
0.9995
1.0000
0.9990
Fixed Mask AUC
LAWMM AUC
Fixed Mask Cosine
Cosine
0.9
Couine Similarit
0.94
88
0.996
0.9985
0.92
8-
-0.994
0.90
0.9980
DDIM Inference Steps 75
0.88
DDIM Inference Steps 65
-0.992
0,9975
0.6
0.86
DDIM Inference Steps
0.990
16-1
18-4
50
55
60
65
70
75
0.015
0.025
0.05
0.075
0.1
Significance Level
Detection-Time Steps
Density
(a) Watermark Detectability
(b) Ablation on DDIM Steps
(c) Effect of Mask Density
Figure Ablation. (a) AUC under varying significance levels and DDIM inference steps. (b) Different DDIM inference steps during embedding and detection. (c) Effect of watermark mask density all datasets, with DDIM steps set to 75 and significance level 5e-5.
on par with the original KG and the non-watermarked ver- sion. For example, in AliF, KGMark achieves a Hits @ 10 score of 0.8296, slightly lower than the non-watermarked score 18.318 Similar trends are observed across MIND and LMs where KGMark consistently outperforms the version without LAWMM. These findings confirm that KG- Mark preserves the KG's utility for downstream tasks, suring the watermarked KG remains functional and reliable.
Table 4. Watermark Detectability & Robustness (Gaussian Noise & Smoothing). We impose two common attacks against images on KGE and evaluate the robustness of these two attacks under different attack intensities.
Gaussian Noise
Smoothing
Datasets
Method
10%
30%
50%
10%
30%
50%
DwiDet
0.98
0.89
0.86
0.94
0.90
0.81
DwiQim
0.93
0.84
0.69
0.90
0.82
0.77
TR
0.92
0.86
0.81
0.92
0.86
0.78
GhaussianSadding
0.94
0.91
11.99
0.90
0.83
0.79
Experimental results in Figure 3c show that the density of the watermark mask matrix also influences watermark transparency. Higher density causes a slight increase de- tectability. However, this comes the cost of transparency, cosine similarity [LAWMM_cosing 0.671, reflecting degradation in KG integrity. This trade- off underscores the need to balance density for optimal detectability and transparency.
W/O LAWMM
0.98
0.95
0.92
0.95
0.91
0.88
Only CL
0.98
0.94
0.90
0.93
0.90
0.84
Only VI.
0.96
0.92
0.87
0.91
0.87
0.82
KGMark
0.98
0.96
0.91
0.94
0.92
0.89
DwtDet
0.96
0.90
0.96
0.81
drops from 0.933 to
DwiQim
0.93
0.81
0.94
0.79
0.91
0.86
0.77
0.94
0.91
0.83
MIND
GaussianShuding
0.94
0.89
0.85
0.90
0.86
0.83
W/O LAWMM
0.98
0.95
0.91
0.95
0.92
0.89
Only CL
0.98
0.93
0.90
0,96
0.92
0.87
Only VI.
0.94
0.93
0.91
0.95
0.91
0.89
KGMark
0.99
0.96
0.92
0.96
0.93
0.90
4.4. Robustness
DwiDet
0.96
0.90
0.85
0.95
0.85
0.77
We next assess the robustness of KGMark, focusing on its ability to withstand wide range of post-editing attacks without compromising watermark integrity. To evaluate the robustness of our watermarking scheme, we systemati- cally analyze its performance under five post-editing attacks with varying intensities: Gaussian noise injection, Gaus- sian smoothing(Hu et al., 2024), relation alteration, triple deletion, and graph isomorphism variation. Attack inten- sity is quantified by the proportion of affected entities or triples, ranging from 10% to 50%, simulating real-world adversarial scenarios. We further incorporate two stronger adversarial attacks into our evaluation: NEA (Bojchevski & Günnemann, 2019), a graph poisoning attack targeting node embeddings, and the L2 Metric attack (Bhardwaj et al., 2021), which perturbs embeddings via instance attribution analysis. These attacks introduce fine-grained and targeted perturbations, enabling rigorous robustness evaluation under realistic and challenging adversarial settings.
DwiQim
0.95
0.84
0.74
0.95
0.92
0.82
0.93
0.89
0.86
0.92
0.89
0.85
Last-FM
GaussianShuding
0.96
0.92
0.92
0.86
W/O LAWMM
0.99
0.96
0.95
0.91
Only CL.
0.97
0.96
0.92
0.93
0.91
0.89
Only VL
0.98
0.96
0.93
0.94
0.90
0.86
KGMurk
0.99
0.97
0.93
0.95
0.93
0.91
structural disruptions. As shown in Table 4 and Table 1, the robustness of the watermark varies significantly across method variants. The standalone Community Layer (Only CL) and Vertex Layer (Only VL) exhibit weaker resilience compared to the full KGMark. For instance, under triple deletion attacks on AliF at 50% intensity, Only CL and Only VL achieve AUC scores of 0.8063 and 0.8592, respec- tively, while KGMark maintains a robust score of 0.9320. This underscores the necessity of combining (Community Layer) and fine-grained (Vertex Layer) embed- ding strategies. Notably, the variant without LAWMM (W/O LAWMM) demonstrates comparable robustness to KGMark, as LAWMM is primarily designed for transparency and does not compromise robustness.
-grrine
Obs. O KGMark's hierarchical embedding ensures ro- bustness by mitigating both local perturbations and
8

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Our analysis reveals that KGMark is particularly sensitive to triple deletion and high-intensity smoothing attacks while maintaining strong robustness against other attack types. Under triple deletion attacks on AliF, the AUC drops from 0.9829 at 10% intensity to 0.9320 at 50% intensity, reflect- ing a significant but manageable decline. Similarly, under smoothing attacks, the AUC decreases from 0.94 at 10% intensity to 0.89 50% intensity on AliF. In contrast, KG- Mark demonstrates exceptional resilience to Gaussian noise and relation alteration, achieving AUC of 0.93 at 50% intensity under Gaussian noise attacks on Last-FM. These results validate that KGMark effectively balances robustness and usability, even under aggressive post-editing attacks.
(V,,R)) RGAT updates node representations as:
h h(+1)_ = Σ
air W
(22)
FER (ENr(w)
where Ni (v) denotes neighbors connected via relation r, Wr is relation-specific transformation, and o is the learned attention weight.
Relational graph neural networks (Schlichtkrull et al., 2017) (e.g.. RGAT, RGCN) better enhance the expressiveness of the latent space z ~ qo (z(g)bs by capturing structural depen- dencies. However, our experiments show that relation-based models are vulnerable to adversarial attacks, which disrupt attention weights and cause representation shifts:
4.5. Case Study
We conduct case study the downstream task of news recommendation using the MIND dataset, comparing the performance of knowledge graph embeddings with and without the proposed watermark. The experiments are car- ried out using the Deep Knowledge-Aware Network (DKN) model (Wang et al., 2018), which has been trained for 10 epochs on the MIND dataset. To simulate controlled user profile, we restrict the user's click history by focusing on strong interest in sports news. Additionally, we randomly sample 5 news items from the model's 's output for evaluation.
||,, ho
R FR (MEN.(V]WW...0
Σ
(a hh,))? (23)
where (v) is the modified neighborhood. This degrada- tion also impacts VAE reconstruction, reducing watermark detectability. Using non-relational models such as GCN or GAT mitigates this vulnerability but lowers latent space expressiveness, leading to suboptimal reconstruction:
(xt.(o<z())]]pez) t,
(loge 4. (24)
Orginal KG
DKN J
MBA
Lakeee
Football
KG (KGMark)
Thus, relational modeling improves representation quality but increases attack susceptibility, requiring a balance be- tween robustness and expressiveness.
Enittles
Portrlt
Michipan
KG based News Recommendation
KG based News RecommendatoonKGMarrk))
Football: Dantonio scofts dumb question about Michigan State's s ottensive staff
Footbull: Rackets guard Gerald Green reportedly has brokan foot
5.2. Embedding Dimensions and DDIM Generality
The dimensionality of embeddings affects watermark de- tectability and robustness, requiring a balance with task per- formance. While DDIM inversion is central to our method, compatibility with advanced samplers remains an open prob- lem. Future work will explore conditional sampling im- prove reconstruction quality and watermark transparency.
Football: Texans sign Dr lavier Edwaads practice squid
NBA: Lakers' Ales Caruso spaiens Internet momes, but has real game
NBA Doncic recelved stitches but didn't suffer concussion Lakers
Football: Pan-12 power rankings Defeats of ranked osporents...
Figure 4. Case Study. Workflow and representative results.
The results, shown in Figure 4, highlight that the content and subcategories of targeted recommendations remain consis- tent with and without watermarking. Despite the watermark, the recommendation system focuses on sports news and identifies trending topics, such as the 12 power rank- ings." Entity recognition remains stable, with consistent identification of sports figures, teams, and locations across both versions. Additionally, the recommendation logic and hot topic recommendations remain unchanged, indicating no impact from the watermarking process.
6. Conclusion
In this paper, we introduce KGMark, novel watermarking scheme for knowledge graphs, leveraging diffusion models to ensure robustness, transparency, and detectability. Our method addresses key challenges in graph integrity, offering a secure solution that maintains semantic fidelity even in dynamic environments. KGMark provides a foundation for securing the integrity and ownership of synthetic knowl- edge graphs, with potential applications spanning academic research to commercial deployments in fields like recom- mendation systems and GraphRAG.
5. Discussion
5.1. Variational Autoencoder
KGMark's 's implementation employed a VAE based on the Relational Graph Attention Network (RGAT) (Busbridge et al., 2019), which extends GAT (Veličković et al., 2018) by incorporating relational dependencies. Given a KG g =
Acknowledgements
We would like to thank the anonymous reviewers for their valuable feedback. We are also grateful to the open-source

---

KGMark: A Diffusion Watermark for Knowledge Graphs
community for providing benchmark datasets and founda- tional libraries that made this research possible. This work was supported in part by the National Natural Science Foun- dation of China (oo.22710664) the National Natural Sci- ence Foundation of China (No.62301072 and the National Natural Science Foundation of China (N0.62271066).
conference on machine learning, pp. 695-704. PMLR, 2019.
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via sub- graph isomorphism counting. IEEE Transactions Pat- tern Analysis and Machine Intelligence, 45(1):657-666 2023.
Impact Statement
Busbridge, D., Sherburn, D., Cavallo, P., and Hammerla, N. Y. Relational graph attention networks, 2019.
This work proposes KGMark, the first diffusion water- marking framework for knowledge graphs, aiming to en- hance intellectual property protection and traceability in Al-generated KGE data. Given the increasing reliance on synthetic KGs in downstream applications such as recom- mendation systems, semantic search, and language model augmentation, our method enables robust, transparent, and detectable watermarking at the embedding level. We do not foresee immediate negative societal impact from this work. However, we acknowledge that any technology for own- ership control may raise ethical concerns if misused, such as improper surveillance or censorship. To mitigate this, we focus strictly on benign applications such as integrity verification and content provenance.
Çano, E., Morisio, M., et al. Music mood dataset creation based on last. fm tags. In 2017 International Confer- ence on Artificial Intelligence and Applications, Vienna, Austria, pp. 15-26, 2017.
Cao, N. D. and Kipf, T. Molgan: An implicit generative model for small molecular graphs, 2022.
Chang, Z., Koulieris, G. A., and Shum, H. P. H. On the design fundamentals of diffusion models: survey, 2023,
Charpenay, V. and Schockaert, S. Capturing knowledge graphs and rules with octagon embeddings. In Proceed- ings of the Phirty-Thine International Joint Conference on Artificial Intelligence, 2025.
References
An, B., Ding, M., Rabbani, T., Agrawal, A., Xu, Y., Deng, C., Zhu, S., Mohamed, A., Wen, Y., Goldstein, T., and Huang, F. Waves: benchmarking the robustness of image watermarks. In Proceedings of the s1 International Conference on Machine Learning. JoLR.org, 2025.
Chen, B. and Wornell, G. A class of provably good meth- ods for digital watermarking and information embed- ding. IEEE Trans. on Information Theory, 47(4):291-314, 2001.
Asnani, V., Collomosse, J., Bui, T., Liu, X., and Agarwal, S. Promark: Proactive diffusion watermarking for causal attribution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10802- 10811, 2024.
Chen, S., Fang, H., Cai, Y., Huang, X., and Sun, M. Differ- entiable neuro-symbolic reasoning on large-scale knowl- edge graphs. In Proceedings of the 37th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2024. Curran Associates Inc.
Barman, N. R., Sharma, K., Aziz, A., Bajpai. S., Biswas, S., Sharma, V., Jain, V., Chadha, A., Sheth, A., and Das, A. The brittleness of ai-generated image watermarking techniques:
Chen, W., Huang, P., Xu, J., Guo, X., Guo, C., Sun, F,, Li, C., Pfadler, A., Zhao, H., and Zhao, B. Pog: Personalized outfit generation for fashion recommendation at alibaba ifashion. In Proceedings of the 25th ACM SIGKDD In- ternational Conference on Knowledge Discovery & Data Mining, KDD 19,, pp. 2662-2670. Association for Com- puting Machinery, 2019. ISBN 9781450362016. doi: 10. 10.1145/329250003333665
Examining their robustness against visual paraphrasing attacks. arXiv preprint arXiv:2408.1044 2024.
Bauer, A., Trapp, S., Stenger, M., Leppich, R., Kounev, S., Leznik, M., Chard, K., and Foster, I. Comprehensive exploration of synthetic data generation: A survey, 2024.
Cox, I., Miller, M., Bloom, J., Fridrich, J., and Kalker, T. Digital watermarking and steganography. Morgan kaufmann, 2007.
Bhardwaj, P., Kelleher, J., Costabello, I.,, and O'Sullivan, D. Adversarial attacks on knowledge graph embed- dings via instance attribution methods. arXiv preprint arXiv:2111.031200 2021.
Das, A., Kong, W., Sen, R., and Zhou, Y. A decoder-only foundation model for time-series forecasting. In Proceed- ings of the 41st International Conference on Machine Learning. JMLR.org, 2024.
Bojchevski, A. and Günnemann, S. Adversarial attacks on node embeddings via graph poisoning. In International
10

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Dathathri, S., See, A., Ghaisas, S., Huang, P.-.,, McAdam, R., Welbi, J., Bachani, V., Kaskasoli, A., Stanforth, R., Matejovicova, T., Hayes, J., Vyas, N., Merey, M. A., Brown-Cohen, J., Bunel, R., Balle, B., Cemgil, T., Ahmed, Z., Stacpoole, K., Shumailov, I., Baetu, C., Gowal, S., Hassabis, D., and Kohli, Scalable wa- termarking for identifying large language model outputs. Nature, 634(8035):818 823, 2024.
Z., Heller, K., Weller, A.. Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st Inter- national Conference Machine Learning, pp. 26199- 26214. PMLR, 2024.
LIANG, K., Liu, Y., Li, H., Meng, I.., Liu, S., Wang, S., sihang zhou, and Liu, X. Clustering then propagation: Select better anchors for knowledge graph embedding. In The Thirty-eightt Annual Conference on Neural Informa- tion Processing Systems, 2024.
Dong, Y., Wang, S., Wang, Y., Derr, T., and Li, On structural explanation of bias in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 316-326, New York, NY, USA, 2022. Association for Computing Machinery.
Liu, A., Pan, L., Lu, Y., Li, J., Hu, X., Zhang, X., Wen, L., King, I., Xiong, H., and Yu, S. A survey of text watermarking in the of large language models, 2024.
Liu, J., Ke, W., Wang, P., Wang. J., Gao, J., Shang, Z., Li, G., Xu, Z., Ji, K., and Li, Y. Fast and continual knowledge graph embedding via incremental lora. In Proceedings of the Thirty- Third International Joint Conference on Artificial Intelligence, 2025.
Fan, W., Ma, Y.. Yin, D., Wang. J., Tang, J., and Li, Q. Deep social collaborative filtering. In Proceedings of the 13th ACM Conference Recommendeer Systems, pp. 305-313, New York, NY, USA, 2019. Association for Computing Machinery.
Nandi, A., Kaur, N., Singla, P., and Mausam. Dynasemble: Dynamic ensembling of textual and structure-based mod- els for knowledge graph completion. In Annual Meeting of the Association for Computational Linguistics, 2024.
Fridrich, J., Goljan, M., and Du, R. Lossless data embed- ding new paradigm in digital watermarking, EURASIP Journal on Advances in Signal Processing, 2002:1-12, 2002.
Patnaik, P. The non-central x 2-and f-distribution and their applications. Biometrika, 36(1/2):202-25 2322, 1949.
Glasserman, P. Monte carlo methods in financial engineer- ing, 2004.
Han, H., Wang, Y., Shomer, H., Guo, K., Ding. J., Lei, Y., Halappanavar, M., Rossi, R. A., Mukherjee, S., Tang, X., He, Q., Hua, Z., Long, B., Zhao, T., Shah, N., Javari, A., Xia, Y., and Tang, J. Retrieval-augmenned generation with graphs (graphrag), 2025.
Podell, D., English, Z., Lacey, K., Blattmann, A., Dockhorn, T., Müller, J., Penna, J., and Rombach, R. Sdxl: Im- proving latent diffusion models for high-resolution image synthesis, 2023.
2025.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., and Sutskever, I. Learning transferable visual models from natural language supervision. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, pp. 1748-8763. PMLR, 2021.
Hu, Y., Jiang, 7., Guo, M., and Gong, N. A transfer attack to image watermarks. arXiv preprint 15X55. 2024.
Ji, S., Pan, S., Cambria, E., Marttinen, P., and Yu, P. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, 33(2)4994-514 2022.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models, 2021.
Jiang, P., Cao, L., Xiao, C.. Bhatia, P., Sun, J., and Han, J. KG-FIT: Knowledge graph fine-tuning upon open-world knowledge. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I,, and Welling, M. Modeling relational data with graph convolutional networks, 2017.
Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I., and Goldstein, T. A watermark for large language models. In International Conference on Machine Learning, pp. 17061-17084. PMLR, 2023.
Shomer, H., Jin, W., Wang, W., and Tang. J. Toward degree bias in embedding based knowledge graph completion. Proceedings of the ACM Web Conference 2023, pp. 705-715, New York, NY, USA, 2023. Association for Computing Machinery.
Le, D., Zhong, S., Liu, Z., Xu, S., Chaudhary, V., Zhou, K., and Xu, Z. Knowledge graphs can be learned with just intersection features. In Salakhutdinov, R., Kolter,

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Simonovsky, M. and Komodakis, N. Graphvae: Towards generation of small graphs using variational autoencoders. In Kürková, V., Manolopoulos, Y., Hammer, B., Iliadis, L., and Maglogiannis, I. (eds.). Artificial Neural Net- works and Machine Learning- ICANN 2018, pp. 412- 422, Cham, 2018. Springer International Publishing.
in Neural Information Processing Systems, pp. 58047- 58063. Curran Associates, Inc., 2023.
Wen, Y., Kirchenbauer, J., Geiping, J., and Goldstein, T. Tree-rings watermarks: Invisible fingerprints for diffu- sion images. Advances in Neural Information Processing Systems, 36, 2024.
Smits, J. and Borghuis, T. Generative Al and Intellectual Property Rights, pp. 223-344, T.M.C. Asser Press, The Hague, 2022.
Wu, F., Qiao, Y., Chen, J.-H., Wu, C., Qi, T., Lian, J., Liu, D., Xie, X., Gao, J., Wu, W., and Zhou, M. MIND: large-scale dataset for news recommendation, Jurafsky, D., Chai, J., Schluter. N., and Tetreault, J. (eds.), Proceed- ings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 3597-3606, Online, July 2020. Association for Computational Linguistics. doi: 10. 12553//112200.almmmii.....
Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models, 2022.
Sun, Z.,, Deng, Z.-H., Nie, J.-Y., and Tang. J. Rotate: Knowl- edge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10199 2019.
Yan, X. and Han, J. gspan: Graph-based based substructure pattern mining. In 2002 IEFF International Conference on Data Mining, 2002. Proceedings., pp. 721-724. IEEE, 2002.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks, 2018.
Vero, M., Balunović, M., and Vechev, M. Cuts: customiz- able tabular synthetic data generation. In Proceedings of the s/ International Conference on Machine Learning. JMLR.org org., 2024.
Yang. Guise: Graph gaussian shading watermark, 2024.
Yang, Y. Chen, J., and Xiang, Y. A review on the reliability of knowledge graph: from a knowledge representation learning perspective. World Wide Web, 28(1):4, 2024a.
Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffusion for graph generation, 2023.
Yang, Z., Zeng, K., Chen, K., Fang, H., Zhang, W., and Yu, N. Gaussian shading: Provable performance-losseen image watermarking for diffusion models. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12162-12171, 2024b.
Wang, H., Zhang, F., Xie, X., and Guo, M. Dkn: Deep knowledge-aware network for news recommendation. In Proceedings of the 2018 world wide web conference, pp. 2018.
Yin, H., Wang, Z., and Song, Y. Rethinking complex queries on knowledge graphs with neural link predictors. In The Twelfth International Conference on Learning Represen- tations, 2024.
Wang, K., Liang, Y., Li, X., Li, G., Ghanem, B., Zimmer- mann, R., Zhou, Z., Yi, H., Zhang, Y., and Wang, Y. Brave the wind and the waves: Discovering robust and generalizable graph lottery tickets. IEEE Transactions on Puttern Analysis and Machine Intelligence, 46(5):3388- 3405, 2023.
You, J., Ying, R., Ren, X., Hamilton, W., and Leskovec, J. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Ma- chine Learning, pp. 5708-5717 PMLR, 2018.
Wang, K., Zhang, G., Zhou, Z., Wu, J., Yu, M., Zhao, S., Yin, C., Fu, J., Yan, Y., Luo, H., et al. A comprehensive survey in Ilm (-agent) full stack safety: Data, training and deployment. arXiv preprint MXXI::5504.15888 2025.
Yu, N., Skripniuk, V., Abdelnabi, S., and Fritz, M. Artifi- cial fingerprinting for generative models: Rooting deep- fake attribution training data. In Proceedings of the IEEE/CVF International conference on computer vision, pp. 14448-14457, 2021.
Wang, X., He, X., Wang, M., Feng, F., and Chua, T.-S. Neural graph collaborative filtering. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 165-174, New York, NY, USA, 2019. Association for Computing Machinery.
Yu, Z., Zhang, C., and Deng, C. An improved gnn using dynamic graph embedding mechanism: novel end-to- end framework for rolling bearing fault diagnosis under variable working conditions. Mechanical Systems and Signal Processing, 205:11 2023.
Wen, Y., Kirchenbauer, J., Geiping, J., and Goldstein, T. Tree-rings watermarks: Invisible fingerprints for diffu- sion images. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances
Zhang, H., Zheng, T., Gao, J., Miao, C., Su, L., Li, Y., and Ren, Data poisoning attack against knowledge graph
12

---

KGMark: A Diffusion Watermark for Knowledge Graphs
embedding. In Proceedings of the Twenty-Eighth Interna- fional Joint Conference Artificial Intelligence, LJCAI- 19, pp. 4853-4859. International Joint Conferences Artificial Intelligence Organization, 2019.
Zhang, L., Liu, X., Martin, A. V., Bearfield, X. Brun, Y., and Guan, H. Attack-resilient image watermarking using stable diffuuion. In The eiiht Annual Conference on Neural Information Processing Systems, 2024a.
Zhang, X., Li, R., Yu, Xu, Y., Li, W., and Zhang, Editguard: Versatile image watermarking for tamper lo- calization and copyright protection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1194--1977, 2024b.
Zhao, X., Ananth, Li, L., and Wang, Y--. Provable robust watermarking for ai-generated text, 2023a.
Zhao, X., Zhang, K., Su, Z., Vasan, S., Grishchenko, I., Kruegel, C., Vigna, G., Wang, Y.-X., and Li, Invisible image watermarks are provably removable using genera- tive ai. arXiv preprint S...vv:2306.095555 2023b.
Zhao, Y., Pang, T., Du, C., Yang, X., Cheung, N.-M., and Lin, M. recipe for watermarking diffusion models. arXiv preprint PrXXiv2303.11133 2023c.
Zhou, Z.,, Zhang, Y., Yao, J., quanming yao, and Han, B. Less is more: One-shot subgraph reasoning on large- scale knowledge graphs. The Twelfth International Conference on Learning Representations, 2024.
Zhu, M., Chen, H., Yan, Q., Huang, X., Lin, G., Li, W., Tu, Z., Hu, H., Hu, J., and Wang, Genimage: A million-see scale benchmark for detecting ai-generated image. Advances in Neural Information Processing Systems, 36, 2024a.
Zhu, P., Takahashi, T., and Kataoka, H. Watermark- embedded adversarial examples for copyright protection against diffusion models. 2024 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 24420-24430, 2024b.
13

---

KGMark: A Diffusion Watermark for Knowledge Graphs
A. Defending Against Isomorphism and Structural Variations
Algorithm 1 Graph Alignment
Require: Input graph G = (V, F)) with vertex attributes and adjacency matrix A
Ensure: Normalized graph G
I: For each v E V:
2: d'u] f- deg(v), clu] +- c(u) Compute the degree and clustering coefficient for each vertex
3: V. < Sort(V, d, c) Sort V first by degree d'u) and then by clustering coefficient clu) in ascending order
4: A' Reorder(A, V)) Reorder rows and columns of A according to the order in V,
5: G+ 0
6: for Vo do
7: G+ for}
Add vertex U; to G
8: end for
9: for (1s, 1j) E do
10: G+ (( 4/)}
Add edge (u), to G
11: end for
12: for U; E V. do
13:
RearrangeAttriuutes(;; G)
Rearrange or update attributes of n based on the new order C
end for
15: return G
Symbol Definitions:
d/o]: The degree of vertex v, i.e., the number of edges incident to c.
clul: The clustering coefficient of vertex measures the degree to which vertices in graph tend to cluster together.
G: The normalized graph after vertex and edge processing.
RearrangeAttriuuuesstt (u; G): A function to reorder update the attributes of vertex o in the normalized graph & based on the sorted vertex list Vo.
Algorithm/ outlines graph alignment process designed enhance the robustness of graph against isomorphism and structural variations, which common forms of attack. The process begins by calculating the degree and clustering coefficient for each node. These attributes reflect the node's connectivity and the density of its neighbors, which are crucial for determining the node's importance within the graph.
Next, the nodes are sorted based on these attributes, first by degree and then by clustering coefficient. This sorting ensures that nodes with lower connectivity are processed first, while more central nodes appear later. Following the sorting, the graph's 's adjacency matrix reordered to match the new node order, preserving the graph's original relationships.
A new graph, G, is created by adding nodes in the sorted order. As each node is added, its attributes updated according to the new structure, ensuring consistency. Finally, the edges are added to the new graph based on the original connections, but aligned with the new node ordering.
The output is a normalized graph that is less susceptible to structural perturbations. This process helps improve the graph's 'ss resilience to attacks that alter its structure, making it more stable for applications like watermarking, where the goal is to embed and extract watermarks while maintaining robustness against manipulation.
Algorithm 2 describes process for redundantly embedding watermark into graph based on its subgraphs. The aim is to enhance the robustness of the watermark against structural modifications and attacks by embedding it in multiple subgraph communities.
The process starts by computing the number of communities based on the graph's total number vertices | and a predefined smallest embedded size s. The graph is then partitioned into / non-overlapping communities C₁, C2...., Ct, ensuring that every vertex in the graph is assigned to exactly one community, and the communities do not overlap.
14

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Algorithm 2 Redundant Embedding Based Subgraphs
Input: Graph G (V, E), Smallest embedded size s, Watermark W
2: Output: Watermarked graph G'
3: / [[V]/s] Compute the number of communities
4: C+ (C1, C2.,,i.
5: when Ui C V and C,nc, - 0, Vi j Partition G into non-overlapping communities
6: for each community
do 7: Vc, - {v) E Ci, selected based on predefined strategy)
8: Cnorm + GraphNormalizationi,, A²)
Normalize the graph structure
9: for each vertex e E Vo do
10:
FimbedWatermark(f W) end for end for
Embed watermark into selected vertices
13:
14: return G'
Next, for each community c E C, the algorithm selects a subset of vertices, Vc,, based on a predefined strategy, which could be influenced by factors such as node importance or connectivity. The subgraph corresponding to each community, c, is then normalized using the 'GraphNormalization" function. This step ensures that the internal structure each community is standardized, making the watermark embedding more robust to structural variations.
After normalizing the graph structure, the watermark is embedded into selected vertices of each community using the 'Embed Watermmat function. This embedding process is repeated for each vertex in every community. By embedding the watermark redundantly across different communities of the graph, the method increases the likelihood of watermark retention even if parts of the graph undergo modification or attack.
Finally, the watermarked graph G' returned, which contains the embedded watermark a redundant and robust manner, ensuring better resilience to structural changes or adversarial perturbations. This approach is particularly useful for applications that require high security, such as digital watermarking in graphs, where the goal is protect the integrity of the watermark despite potential attacks.
B. Case Study in Embedding Space
To further demonstrate the effectiveness of our proposed watermarking method, a case study is conducted on the dataset AliF related to customer behavior analysis. We select 2400 entity embeddings from five communities (A-E) from AliF for watermark embedding and visualize the embedding vectors before and after processing by dimensionality reduction. The case background is presented in Table 5, the result of the visualization shown in Figure 5
Table 5, Case Background.
Number Entities
total
Dimensions of Embeddings
DDIM Inference Steps
Density of Mask
Cosine Similarity
A
C
524
507
524
420
425
2400
4096
75
0.015
0.9535
For visualization purposes, we used the t-SNE technique reduce the dimensionality of the embedding vectors from 4096 This technique particularly suitable for mapping data from high-dimensional two-dimensional three-dimensional space while preserving local structural relationships between data points.
The similarity between points i; and xy in high-dimensional space is defined by the conditional probability pyte follows, where ||,, 1I represents the squared Euclidean distance. a, is parameter that controls the width of the neighborhood of the point 2;.
11112//00 exp (-1|x;
P5ke Σ Aetti cxp 11|a0; - x 12 22222
(25)
15

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Original Feature Distribution
Watermarked Feature Distribution
20
10
10
-10
-10
40
40
20
20
30
10
-10
-10
-10
-30
30
Figure Ablation study density of the watermark mask matrix on datasets. Each subfigure corresponds a different method.
To symmetrize the similarity, the joint probability is defined as follows, where is the total number of data points.
Pylé + Palj
Pij
(26)
2n
In low-dimensional space, the similarity between the points yi and yj is defined by the t-distribution as:
(1 + 11ys Ms 11
d ΣKSU (1 + 18ve yi 12)
(27)
t-SNE uses Kullback-Leible (KL) divergence dissimilarity measure between high-dimensional distribution Piyand low-dimensional distribution 9t-- The goal is to minimize the following loss function:
Pij
L
Piş log
(28)
K
t-SNE optimizes the loss function L using Stochastic Gradient Descent (SGD). During the optimization, the position of the low-dimensional embedding yi is gradually adjusted, that the tow-dimensional similarity 4ú is closer to the high-dimensional similarity Pij-
In Figure 5, it can be found that the color gradient and position distribution of the points in the figure almost remain unchanged before and after the embedding of the watermark, indicating that the embedding of the watermark does not significantly change the geometric structure the original embedding. In addition, both images show spherical distribution that gradually diffuses from the center to the outside, and the density of the points remains same, indicating that the characteristics of the original vector embedding are well preserved after embedding the watermark. The watermark embedding may introduce only slight perturbations in some local details some dimensions, but these perturbations not sufficient to cause significant effects the overall distribution.
Then, we carry out watermark detection on the watermarked knowledge graph, and we select the significance level as 5e-5, We report their P-values to check whether the watermark is detected. In summary, our watermarking method performs well in terms of transparency. neither destroys nor enhances the distribution characteristics the original embeddings, but also achieves certain robustness and detectability.
16

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Table 6. Case Result.
Community
P-value
Is Detected
A
8.29e 27
B
1.52e 26
C
4.20e 19
D
1.88e 15
E
3.27e 34
C. Latent Diffusion Model
C.1. Variational Autoencoder
To effectively capture the intricate structure of graph data, we employ Variational Autoencoder (VAE). This advanced model maps the entity embeddings of the knowledge graph into latent space, where the underlying patterns and relationships can be more efficiently represented and analyzed. To ensure that can adequately and accurately capture the complex patterns inherent in the graph structure, we utilize multiple Relational Graph Attention (RGAT) modules. These modules are specifically designed to handle the relational nature of the graph data, allowing the model to focus on different types of relationships and entities within the graph. By leveraging the power of multiple RGAT modules, we can produce higher-quality latent representations that better encapsulate the essential characteristics of the graph structure. These embeddings are then sampled using the reparameterization trick. This technique enables us introduce stochasticity in differentiable manner, which is crucial for the training process of the VAE, Finally, the sampled embeddings are decoded back into the reconstructed entity embeddings, allowing to evaluate the quality of the learned representations and the model's ss overall performance in capturing and reconstructing the graph data.
C.2. Diffuuion, DDIM and Inversion
Denoising Diffusion Implicit Models (DDIM) provide efficient alternative to standard diffusion- generative models by leveraging non-Mar Markovian forward and reverse process. This section introduces the DDIM sampling process, its inversion, and the necessary mathematical formulation and derivation.
Forward Diffusion Process:
The forward process in DDIM maps data point Zg Rdd a noisy latent variable Zr over T timesteps. It is defined as:
Z, an /1 are, e~ 1,,
(29)
where dg is scheduling parameter that controls the noise variance timestep t.
Reverse Diffusion Process:
The reverse process reconstructs Zy from Zy by iteratively denoising the latent variable. DDIM modifies the reverse process to make deterministic, defined as:
Z,-1 Va-11Zo V a4-16tt
(30)
where 2, the predicted clean data at timestep and is obtained via:
20 Z, vI-
(31)
Vot:
The noise e, is predicted using pre-trate me-trrieed noise estimation model, typically parameterized co co(Z,.t)
DDIM Sampling:
DDIM employs a deterministic sampling strategy by reparameterizing the reverse process. Specifically, the update step
becomes:
Z, 12. v1 - at-1 1 9) Ct
(32)
17

---

KGMark: A Diffusion Watermark for Knowledge Graphs
where y [0, 1] controls the stochasticity of the process. Setting results in fully deterministic process, while vj introduces controlled randomness.
Inversion Process:
DDIM supports exact inversion, enabling the recovery of Z, from - By rearranging Eq. (32), the inversion is expressed as:
Z, Za + v1 0t 1) Et-
(33)
This exact inversion capability is crucial for tasks such as embedding watermarks debugging generative processes.
D. Watermark Embedding in Frequency Domain
0.05
0.32 0.15 0.36
0.37
0.43
57.22
-22.22
-8.93
-22.22
0.05
0.33 0.13 0.37
0.38
0.42
-0114
11.35
31.17 82.95 32.58 114.51
-0.14 -1.36
-1.05
32.17
-1.03
FFT
IFFT
Z
Z
Mask Matrix
0100 ...... 000
0110 001
010
Figure 6. Watermark Embedding in Frequency Domain.
The theoretical basis of watermark embedding in the frequency domain is mainly based on the frequency domain transfor- mation technology in signal processing. The essence of the Fourier transform we employ is separate the time domain and frequency domain characteristics, and the Fourier transform decomposes the time domain signal into frequency do- main components; that is, the signal is represented frequency domain, Low-frequency components usually contain the main energy of the signal (such as the overall structure or low-resolution features). High-frequency components: Describe rapid changes in the signal (such as detail or texture information). The watermark is embedded in some specific frequency components of the frequency domain (such as middle frequency or high frequency), which can not only hide the watermark but also reduce the impact on the data's original structure. The frequency domain properties after the Fourier transform are robust to certain linear operations such as compression, smoothing, rotation, and cropping: for example, the rotation operation only causes a phase change in the frequency domain, while the amplitude spectrum remains stable. This makes the method of embedding the watermark in the frequency domain highly robust to these transformations.
superposition of sine waves with different frequencies. In the
Our method uses the energy distribution characteristics, perceptual sensitivity, and frequency domain stability of the Fourier transform frequency domain to embed the watermark into the frequency domain, and then realizes the flexible and adaptive selection of the frequency region through our LAWMM to achieve the goal of invisibility, robustness, and detectability of the embedded watermark. These theoretical foundations provide solid foundation for frequency domain watermarking
18

---

KGMark: A Diffusion Watermark for Knowledge Graphs
technology and also explain its advantages in the face of common attacks such as compression, geometric transformation, and smoothing.
E. Metrics
E.1. Detectability and Robustness
We use the AUC as an authoritative indicator for evaluating the detectability and robustness of our watermarking methods.
Area Under Curve (AUC): AUC refers to the area under the Receiver Operating Characteristic (ROC) curve, widely used metric for evaluating classification models. The AUC score ranges from to I, with value closer to indicating better model performance. It represents the probability that a randomly chosen positive sample will be ranked higher than a randomly chosen negative sample. Mathematically, AUC can be expressed as:
Np
N
AUC
I(
v/)
(34)
N₂N,
(=
where Np and N₂ are the numbers of positive and negative samples, respectively, yt and yy are the predicted scores of the positive and negative samples, and T(y > Vy) is the indicator function that is 1 if y/ Yj- and 0 otherwise.
E.2. Transpareney
We evaluate the transparency of watermarking from two dimensions: the similarity of knowledge graph embedding before and after watermarking and the quality of watermarked knowledge graph. Therefore, we used the following two categories of evaluation metries.
We use cosine similarity to evaluate the similarity of knowledge graphs.
Cosine Similarity: Cosine similarity is similarity measure between non-zero vectors in inner product space. It is widely used in many fields, including information retrieval, natural language processing, and machine learning. The cosine similarity between two vectors A and B is defined as:
A B
cosine similarity (A, B)
(35)
AA
B
For quality, we use the following four metrics. Given a set of test triples T = {(h, r, t)} in knowledge graph G. let r(h, t) denote the rank of the correct entity/ (or h) among all candidates in ranking task.
Geometric Mean Rank (GMR): GMR captures the overall ranking tendency a multiplicative rather than additive manner, making it particularly suitable for datasets where ranking distributions exhibit heavy tails. It provides insights into the overall ranking distribution, making it useful for comprehensive model evaluation. The GMR is defined as follows:
+
GMR
II th, (K,T.))TT
(36)
Harmonic Mean Rank (HMR): HMR mitigates the influence of extremely high ranks, ensuring that poor predictions do not disproportionately impact the evaluation. Moreover, HMR is expressed directly in rank space, making it more interpretable while still benefiting from reciprocal weighting.
HMR
(37)
Emhroer r(h.))
Arithmetic Mean Rank (AMR): AMR directly reflects the average rank of correct entities, making it easy to understand and compare across models. A major limitation of AMR is that is heavily influenced by extremely high-rank values, which can distort performance evaluation.
AMR
1
r(h,t). (h.r:
Σ
(38)
T
19

---

KGMark: A Diffusion Watermark for Knowledge Graphs
Hits@k: H provides direct measure of retrieval success within fixed rank cutoff, making useful for real-world applications requiring top-k recommendations.
Hits @
Σ
Tr t) S kl,
(39)
[T|
(k,r,t))T
where I[-] is the indicator function that returns if the condition holds and otherwise. This metric evaluates whether the correct entity appears within the top-k ranks.
F. Notations and Definitions
Table 7. Notations and Definitions
Notation
Definition
F())
Fourier Transform
Watermark mask matrix
S
Watermark signature
o²
Variance of the watermark signature
Zyp NA
Watermarked latent representation
Initial noise vector recovered via DDIM inversion Loss function in watermark embedding Threshold for latent space equilibrium Total perturbation in an attack
L
Perturbation applied to each subgraph G₃
Norm type the attack objective
Y
Fourier transform result during watermark extraction Mean of Y
of
Variance of Y
T
Test statistic for watermark detection
X
Likelihood ratio test statistic
Simplified test statistic
P-value for watermark detection Significance level for watermark detection Density of the watermark mask matrix Watermark embedding in the community layer Watermark embedding in the vertex layer Effective information capacity of watermark encoding
((C,)
(v)
C(W)
H()
Entropy
D(G.G)
Divergence metrie between graphs G and Ō Pseudoinverse of the graph Laplacian Perturbation matrix for the graph Centrality of vertex v Predicted clean data in DDIM inversion
Lt
AA
(())
Zo
Stochasticity control parameter in DDIM sampling Predicted noise in DDIM reverse process Scheduling parameter in DDIM forward diffusion process Parameter controlling neighborhood width in t-SNE
ét
at
Pij
Joint probability in high-dimensional space
45
t-distribution similarity in low-dimensional space
L
Loss function in t-SNE optimization
20


Reviews:
[{"review_id": "g4r5W86nLo", "reviewer": "Reviewer_zE4M", "summary": "The paper presents KGMark, a watermarking framework designed for Knowledge Graphs (KGs), which are widely used in applications like semantic search, question answering, and recommendation systems. The primary goal of KGMark is to embed robust, detectable, and transparent watermarks into dynamic KGs to protect intellectual property and ensure data integrity, especially in the context of AI-generated content.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer zE4M:\n\nWe appreciate your insightful comments, which mainly focus on:\n\n- Empirical validation under stronger adversarial attacks\n\n- Clarification of the limitations of KGMARK\n\n- Discussion of KGMARK’s role in privacy protection for sensitive data\n\n-----\n\n## Adversarial Attacks\n\nWe have incorporated two recent and stronger adversarial attacks NEA[1] and L2 Metric [2] into our evaluation. \nIn 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. \n\n| Datasets | Method | Clean  | Relation Alteration (50%) | Triple Deletion (50%) | Gaussian Noise (50%) | Smoothing (50%) | L2 Metric | NEA    | IsoVar |\n| -------- | ------ | ------ | ------------------------- | --------------------- | -------------------- | --------------- | --------- | ------ | ------ |\n| AliF     | DwtDct | 0.9837 | 0.8371  | 0.7724   | 0.8626   | 0.8053   | 0.9577 | 0.9638 | 0.6039 |\n|          | DctQim | 0.9749 | 0.8139   | 0.7073   | 0.6949   | 0.7665  | 0.9203    | 0.9278 | 0.5867 |\n|          | TR     | 0.9814 | 0.7392   | 0.8091  | 0.8063 | 0.7823  | 0.9621  | 0.9584 | 0.6257 |\n|          | GS     | 0.9882 | 0.7998   | 0.7850  | 0.8921   | 0.7906   | 0.9364  | 0.9512 | 0.6094 |\n|          | **KGMark** | **0.9991** | **0.9207**   | **0.9320**  |**0.9136**   | **0.8887** | **0.9841**  | **0.9809** | **0.9933** |\n| MIND     | DwtDct | 0.9793 | 0.8161    | 0.7610   | 0.8285  | 0.8121  | 0.9358  | 0.9291 | 0.6348 |\n|          | DctQim | 0.9785 | 0.8269   | 0.6993   | 0.7186  | 0.7935  | 0.9209   | 0.9198 | 0.5708 |\n|          | TR     | 0.9862 | 0.8171   | 0.7831  | 0.7721  | 0.8296   | 0.9682   | 0.9543 | 0.5763 |\n|          | GS     | 0.9903 | 0.7930   | 0.8284  | 0.8536   | 0.8252    | 0.9767   | 0.9681 | 0.5845 |\n|          | **KGMark** | **0.9987** | **0.9314**   | **0.9576**   | **0.9232**   | **0.9012**  | **0.9849**   | **0.9883** | **0.9842** |\n| Last-FM  | DwtDct | 0.9801 | 0.8229  | 0.7415  | 0.8514   | 0.7740   | 0.9596    | 0.9678 | 0.6407 |\n|          | DctQim | 0.9842 | 0.8062  | 0.7125  | 0.7383  | 0.8174    | 0.9144   | 0.9161 | 0.5938 |\n|          | TR     | 0.9879 | 0.7982  | 0.8519  | 0.8632  | 0.8531  | 0.9553   | 0.9487 | 0.6109 |\n|          | GS     | 0.9795 | 0.8303  | 0.8667  | 0.8912  | 0.8575  | 0.9638   | 0.9594 | 0.6551 |\n|          | **KGMark** | **0.9976** | **0.9421**  | **0.9031**  | **0.9295**   | **0.9131**   | **0.9886**  | **0.9814** | **0.9977** |\n\nWe 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.\nAnother 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.\n\n\n[1] Node embedding attacks via graph poisoning (NEA) \n\n[2] knowledge graph embedding attacks via instance attribution methods\n\n------\n\n##  Limitations\n\n\n\nWhile 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.\n\n------\n\n## Privacy Protection\n\nWhen (KGs) involve sensitive information, they face several privacy risks:\n\n1. Tampering risk: Attackers may alter the generated graph to inject harmful content, potentially leaking sensitive information.\n2. Disturbing sensitive subgraphs: Even with structure-aware embedding, watermarking may affect subgraphs involving sensitive entities.\n3. Key misuse: If the watermark key is exposed, it could be exploited for data tracing or structural inference.\n\nKGMARK 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.\n\n*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.*", "claims_and_evidence": "The claims made in the submission are well-supported by experimental results and case studies. However, to further strengthen the claims, the authors could consider additional experiments on testing against more extreme or adaptive attacks such as attacks specifically designed to remove watermarks.", "methods_and_evaluation_criteria": "Standard metrics such as FPR (False Positive Rate) and TPR (True Positive Rate) for detectability and cosine similarity for transparency have been used.", "theoretical_claims": "The theoretical claims have been checked and to the best of my knowledge seem valid.", "experimental_designs_or_analyses": "The authors use three datasets (Last-FM, MIND, and Alibaba-iFashion) representing diverse real-world scenarios. These datasets are appropriate for evaluating the generalizability and effectiveness of KGMark across different domains.", "relation_to_broader_scientific_literature": "This work is quite innovative and to the best of my knowledge, there are no other watermarking techniques for knowledge graphs.", "essential_references_not_discussed": "To the best of my knowledge, there are no essential references that are not discussed.", "other_strengths_and_weaknesses": "Strengths:\n-  The document appears to be well-structured and comprehensive.\n-  This is an innovative work related to the watermarking of KGs\n\n\nWeaknesses: \n- Additional experiments on testing against more extreme or adaptive attacks such as attacks specifically designed to remove watermarks.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1. What are some limitations of this work? \n2. Are there any privacy concerns that need to be discussed when the KG contains sensitive data?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mhE1N9fxuq", "reviewer": "Reviewer_dihZ", "summary": "This paper proposes a watermarking method for knowledge graphs (KGs) using diffusion models. The authors claim their method embeds watermarks into KGs via diffusion-based encoding, ensuring traceability, integrity, and copyright protection. The method primarily relies on diffusion encoding, subgraph preservation principles, and loss functions aimed at robustness against certain graph-based attacks. Experimental evaluations were conducted on datasets such as AliF and MIND to validate the effectiveness of watermark embedding, extraction accuracy, and impact on downstream tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer dihZ:\n\nWe sincerely thank you for your constructive and thoughtful suggestions.\n\nWe understand that your comments mainly concern the following four aspects:\n\n- The robustness of KGMARK under stronger adversarial attacks\n- Concerns about KGMARK’s performance across datasets\n- Explanation of the strategies in *Learnable Adaptive Watermark Mask Matrix* and *Defending Isomorphism and Structural Variations*\n- Writing and presentation issues\n\n------\n\n## robustness \n\nGuided 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.\n\n------\n\n## Performance vs. Baseline\n\nGuided 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). \n\n| Datasets    | Method      | CosSim@50 | CosSim@65 | CosSim@75 | GMR ↓  | HMR ↓ | AMR ↓    | Hits@10 ↑ |\n| ----------- | ----------- | --------- | --------- | --------- | ------ | ----- | -------- | --------- |\n| **AliF**    | Original KG | -         | -         | -         | 1.828  | 1.162 | 135.459  | 0.8980|\n|| DwtDct| 0.7215    | 0.7928    | 0.8251    | 5.096  | 1.699 | 157.036  | 0.6933|\n|| DctQim| 0.7509    | 0.7633    | 0.7653    | 5.104  | 1.654 | 161.142  | 0.7385|\n|| TR       | 0.7761    | 0.8431    | 0.9071    | 3.928  | 1.618 | 152.634  | 0.8017|\n|| GS       | 0.2879    | 0.3226    | 0.3538    | 6.641  | 1.798 | 172.813  | 0.5137|\n|| **KGMark**      | **0.7839**    | **0.8309**    | **0.9482**    | **3.046**  | **1.580** | **141.904**  | **0.8296**  |\n| **MIND**    | Original KG | -         | -         | -         | 7.197  | 1.975 | 155.656  | 0.6649|\n|| DwtDct      | 0.7831    | 0.8244    | 0.8312    | 11.328 | 2.328 | 188.992  | 0.5216|\n|| DctQim| 0.7549    | 0.7574    | 0.7703    | 12.037 | 2.753 | 205.483  | 0.4835|\n|| TR| 0.7976    | 0.8108    | 0.8581    | 11.102 | 2.297 | 182.925  | 0.5108|\n|| GS| 0.2843    | 0.3196    | 0.3728    | 14.523 | 3.312 | 234.064  | 0.3940|\n|| **KGMark**| **0.8083**    | **0.8533**    | **0.9397**    | **10.508**| **2.226** | **169.305**  | **0.5683**|\n| **Last-FM** | Original KG | -         | -         | -         | 3.571  | 1.202 | 1711.695 | 0.8436|\n|| DwtDct| 0.7215    | 0.7928    | 0.8433    | 4.519  | 1.502 | 1734.823 | 0.8221|\n|| DctQim| 0.7509    | 0.7633    | 0.7679    | 5.139  | 1.704 | 2043.249 | 0.7264|\n|| TR| 0.7262    | 0.7896    | 0.8364    | 4.733  | 1.652 | 1772.961 | 0.8149|\n|| GS| 0.3252    | 0.3649    | 0.4184    | 6.349  | 2.016 | 2192.492 | 0.6463|\n|| **KGMark**   | **0.8876**   | **0.9051**   | **0.9161**  | **4.455**  | **1.452** | **1716.365** | **0.8430**  |\n\nWe 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.\nDwtDct [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.\n\n[3] Gaussian Shading: Provable Performance-Lossless Image Watermarking for Diffusion Models \n\n[4] Tree-Ring Watermarks: Fingerprints for Diffusion Images that are Invisible and Robust\n\n[5] Digital Watermarking and Steganography\n\n[6] A class of provably good methods for digital watermarking and information embedding\n\n------\n\n## Explanation of Strategies\n\nA detailed explanation of the rationale behind KGMARK’s design is presented in our response to *Reviewer 1f2k (KGMARK’s Designing)*.\n\nWe have also elaborated on the core strategies and their underlying motivations in our responses to *Reviewer 1f2k (Robustness Strategy)* and *Reviewer voAk (Transparency Strategy)*.\n\nIn 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.\n\n-----\n\n## Writing Issues\n\nWe sincerely appreciate your careful feedback and will make the following revisions in the final version: \n\n1. Correcting the section reference in Figure 2.\n2. Clarifying the duplicated variable usage.\n3. Relocating the algorithm for better coherence.\n4. Refining Sections 3.3 and 3.5 to improve clarity and readability.\n\nWe will thoroughly proofread the paper and clarified the sentences.\n\n*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.*", "claims_and_evidence": "The authors' key empirical claims lack strong evidence. The claim of robustness against graph-based attacks is weak, as the evaluations do not compare against advanced adversarial attacks. Similarly, the claim of preserving graph integrity and traceability is undermined by significant performance drops in downstream tasks like MIND and Alif. These issues reveal major gaps in empirical support, further compounded by the absence of baseline comparisons on diffusion watermarking [1,2].\n[1] Gaussian Shading: Provable Performance-Lossless Image Watermarking for Diffusion Models\n[2] Tree-Ring Watermarks: Fingerprints for Diffusion Images that are Invisible and Robust", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria have several fundamental issues. Primarily, the choice to use diffusion models for watermark encoding on graphs is not well-justified, especially given significant drops in Hit@10 performance on downstream tasks (MIND and Alif) observed even with reconstruction alone. Furthermore, essential evaluations against more advanced attack methods prevalent in recent graph attack literature are missing such as [3,4].\n[3] Adversarial attacks on knowledge graph embeddings via instance attribution methods\n[4] Adversarial attacks and defenses on graphs", "theoretical_claims": "The paper contains inconsistencies and ambiguities in its theoretical formulations, particularly in equations (4) and (9), where the definition of variable S changes without clarification. Additionally, critical conceptual misunderstandings or mislabeling, such as referring to objectives as \"principles\" add to the confusion.", "experimental_designs_or_analyses": "The experimental design has several critical flaws. The evaluation fails to compare with state-of-the-art diffusion-based watermarking methods [1,2]. Additionally, the significant performance drop on the AliF and MIND datasets, as shown in previous sections, raises serious concerns about its paradigm suitability.", "relation_to_broader_scientific_literature": "The paper is mainly related to diffusion-based watermarking methods, graph watermarking, graph robustness and graph embedding techniques.", "essential_references_not_discussed": "The paper does not discuss significant recent advances in diffusion-based watermarking methods [1,2], and graph robustness [3,4].", "other_strengths_and_weaknesses": "While the idea of integrating diffusion models with watermarking in graphs is promising, poor execution and writing severely limit its impact. The paper lacks a clear motivation for using diffusion models for watermarking, and inconsistent, confusing technical explanations further weaken its clarity. Sections 3.3 and 3.5 are particularly unclear, making it difficult to understand what is being optimized, how different loss terms interact, or how watermark extraction works in practice. Additionally, the challenges posed by heterogeneous nodes and relations in knowledge graphs are not addressed.", "other_comments_or_suggestions": "Statements like \"potentially introducing harmful content that compromises analyses or even facilitates the exploitation of real-world systems\" and discussions such as \"unnerves large corporations, let alone individual researchers\" in page 1 are vague or inaccurate.\nIn Figure 2, community detection and alignment correspond to Section 4.4, and Section 4.3 relates to extraction. However, since these are experimental sections, shouldn't they reference Sections 3.5 and 3.3 instead?", "questions_for_authors": "Please refer to the weakness mentioned above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pmagqNUfTn", "reviewer": "Reviewer_1f2k", "summary": "This manuscript presents a novel watermarking method for knowledge graph embeddings to ensure the traceability and auditability of knowledge graphs, claiming to embed invisible signatures into diffusion-based latent representations using the Fourier transform. It addresses key challenges by incorporating multi-level redundancy, graph alignment, and a learnable mask to enhance robustness and transparency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 1f2k:\n\nWe sincerely appreciate your thoughtful comments, which primarily concern the following three aspects:\n\n- Design choices behind KGMARK\n\n- Algorithmic ration for the redundant embedding strategy\n\n- Consideration of computational efficiency\n\n-----\n\n## KGMark's Designing\n\nKGMARK 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:\n\n- **Non-Euclidean topology**: KGs lack the spatial continuity of images, making frequency or pixel-based watermarking inapplicable.\n- **High sensitivity to structural changes**: Small perturbations can cause large semantic shifts.\n- **Large scale and sparsity**: Real-world KGs require scalable and efficient embedding strategies.\n\nTraditional 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.\n\nFor 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.\n\nKGMARK 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.\n\nWe further demonstrate the effectiveness of KGMark across multiple baselines, with detailed results presented in our response to *Reviewer dihZ (Performance vs. Baseline)*.\n\n-----\n\n## Robustness Strategy\n\nTo 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:\n\n$$\n\\inf_{\\|\\Delta A\\|_0 \\leq \\delta} I(\\mathcal{S}; T(\\mathcal{G}^w + \\Delta A)) \\geq \\beta\n$$\n\nHere, $\\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}$.\n\nTo 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:\n\n$$\n\\mathcal{W}(\\mathcal{G}) = \\bigcup _ {i=1}^l \\Phi(\\mathcal{C}_i) \\cup \\bigcup _ {v \\in \\mathcal{C}_i} \\Psi(v)\n$$\nHere, $\\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.\n\nTo justify our choice of high-centrality vertices for embedding, we highlight three key considerations:\n\n- We assume attackers aim to modify the graph without harming its usability, and thus tend to avoid high-centrality nodes.\n- High-centrality nodes are structurally stable due to their dense connections, making embedded watermarks more resilient to local changes.\n- 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.\n\n-----\n\n## Time complexity\n\nThe 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.\n\n$$\nAvgTimeCost = \\frac{TotalTimeCost}{\\text{Number of Nodes}}\n$$\n\nTo provide a more accurate evaluation, we will include the average runtime of KGMARK in the revised version.\n\n*We appreciate your detailed comments and hope our responses have clarified the key contributions and addressed your concerns.*", "claims_and_evidence": "This paper emphasizes the detectability, transparency, and robustness of the proposed watermarking method, KGMark. These claims are supported by the following aspects:\n\n1.  Theoretical Derivation: The paper rigorously presents the mathematical formulation of KGMark along with detailed derivations, ensuring the theoretical correctness of the proposed method.\n2.  Experimental Evidence: Comprehensive evaluations are conducted to assess the detectability, transparency, and robustness of KGMark, with results demonstrating the effectiveness of the approach.\n3.  Case Study: The paper provides a case study for specific downstream tasks, showcasing the practical utility of KGMark in real-world scenarios.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria align well with the problem at hand. The study:\n\n1.   The AUC is used to evaluate the detectability and robustness of KGMark.\n2.   The transparency of KGMark is evaluated by the cosine similarity and quality metrics of knowledge graph embeddings.\n3.   Extensive ablation experiments have been performed on multiple variants of KGMark and their associated hyperparameters.", "theoretical_claims": "In this paper, the mathematical expression of KGMark and the related theoretical derivation are given, and the attacks on KGmark are modeled. The proofs are logically sound and mathematically rigorous.", "experimental_designs_or_analyses": "The paper selects three KG datasets from different domains to evaluate KGMark.\n\n1.   The detectability of KGMark on clean samples was evaluated.\n2.   The robustness of KGMark under different kinds and intensities of attacks is evaluated.\n3.   The transparency of KGMark is evaluated by the similarity and quality of knowledge graph embeddings.", "relation_to_broader_scientific_literature": "This paper aims to introduce watermarking technology into knowledge graph, which ensures the traceability and auditability of knowledge graph and protects its intellectual property rights to a certain extent. I think this is a meaningful and useful exploration.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "## Strength：\n\nKGMark presents an outstanding exposition of a novel watermarking method for KGEs. Driven by an insightful motivation to protect the copyrights,  the proposed KGMark framework introduces key innovations to enhance both transparency and robustness. The Learnable Adaptive Watermark Mask Matrix improves transparency, while multi-level redundancy ensures resilience against structural modifications. Additionally, the incorporation of graph alignment effectively mitigates challenges arising from isomorphism variations. Overall, this approach demonstrates significant potential for safeguarding intellectual property and maintaining data integrity in KGEs.\n\n## Weakness：\n\n- The lack of comparison with relevant baselines makes the effectiveness of the proposed method in various aspects unable to be more credible verified.\n- Although the paper introduces a learnable mask matrix to improve transparency, the relationship between this matrix and the redundant embedding strategy is not explicitly clarified. Further explanation on how these two components interact and contribute to watermark robustness and transparency would enhance the paper.\n- The case study demonstrates KGMark in a recommendation system. However, it remains unclear whether the authors have tested the method in other domains. Expanding the evaluation to other real-world applications would strengthen the paper’s claims of versatility.", "other_comments_or_suggestions": "- While KGMark is the first watermarking scheme designed for knowledge graphs, it would benefit from additional comparisons with existing watermark methods to provide a clearer context for its innovations.\n- The experiments are conducted on relatively small datasets. Evaluating KGMark on larger knowledge graphs would better demonstrate its scalability and robustness in more realistic settings.\n- The paper does not discuss the computational efficiency of KGMark for embedding watermarks in knowledge graphs of varying sizes. Including an analysis of the method’s performance in terms of computational resources and time complexity across different scales would be valuable.", "questions_for_authors": "- Considering the large number of hyperparameters involved in the paper, can you explain the basis for configuring these parameters?\n- The paper mentioned the use of community algorithm to segment the graph. Can you explain the necessity of introducing community algorithm? Why don't we directly select several vertices on the graph for redundant embedding?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LYYXkx2BeE", "reviewer": "Reviewer_voAk", "summary": "Briefly summarize the paper (including the main findings, main results, main algorithmic/conceptual ideas, etc. that the paper claims to contribute). This summary should not be used to critique the paper. A well-written summary should not be disputed by the authors of the paper or other readers.\n\nThis paper introduces KGMark, the first watermarking method for knowledge graph embeddings. It leverages a latent diffusion model to embed watermarks in the frequency domain, using a learnable mask to ensure transparency. Experimental results show its high detectability and robustness against various attacks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer voAk:\n\nThank you for your detailed and constructive feedback.\n\nWe note that your concerns mainly focus on four aspects: \n\n- Scalability and generalizability of KGMark\n- Comparative analysis\n- Embedding strategy and robustness–transparency trade-off\n- Presentation and writing quality\n\n-----\n\n## Dataset Scale and Heterogeneous \n\n**Scale and Generalization**\nKGMark is evaluated on three large-scale, real-world knowledge graphs from diverse domains, ensuring both scalability and generalizability::\n\n- 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.\n\n- 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.\n\n- 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.\n\nThe variety in domains (fashion, music, news) and graph structures allows KGMark to be evaluated under diverse, realistic conditions, ensuring broad generalization ability.\n\n**Heterogeneous Graph Structures**\nAll 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).\nFor 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.\n\n-----\n\n## Baselines\n\nWe have added additional experiments on the baselines, as presented in our response to Reviewer *dihZ (Performance vs. Baseline)* and *zE4M (Adversarial Attacks)*.\n\n\n\n------\n\n## Transparency Strategy\n\nTo further clarify the role of the adaptive mask matrix, we describe how it contributes to both the robustness and transparency of watermark embedding.\n\nWe aim to balance watermark detectability with minimal impact on downstream tasks by jointly minimizing reconstruction and task-related loss:\n\n$$\n\\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\n$$\nIn the refined objective, we introduce two key changes to improve both performance and efficiency:\n\n1. 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.\n\n2. 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.\n\nThe resulting loss is:\n\n$$\n\\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\n$$\nThis formulation enables efficient optimization while enhancing the transparency of the embedded watermark.\n\n\n**Training Process of Adaptive Mask Matrix:**\n\nAnother 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. \n\nIn 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.\n\n------\n\n\n\n## Writing Issues\n\nIn the revised version, we will carefully review the manuscript to correct any grammatical issues and improve overall clarity and writing style.\n\n*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.*", "claims_and_evidence": "The claims made in the submission regarding KGMark’s efficacy in watermarking knowledge graphs are supported by clear and convincing evidence:\n\n1. Theoretical Analysis: The paper provides a detailed theoretical framework, including the use of latent diffusion models, Fourier transform-based watermark embedding, and the Learnable Adaptive Watermark Mask Matrix (LAWMM) to ensure transparency and robustness. It also introduces principles like Latent Space Equilibrium and Information-Theoretic Robustness to justify the method’s design.\n\n2. Experimental Results: The claims are empirically validated through extensive experiments on three diverse datasets (Last-FM, MIND, and Alibaba-iFashion). The results demonstrate high watermark detectability (AUC up to 0.99) and robustness against various attacks (e.g., relation alteration, triple deletion, isomorphism variation) while maintaining minimal impact on the knowledge graph’s usability.\n\nComparative Analysis: The paper compares KGMark with its variants (e.g., without LAWMM, only community layer, only vertex layer) and shows that the full method outperforms these variants in terms of robustness and transparency, supporting the claim that the combined approach is superior.", "methods_and_evaluation_criteria": "The proposed methods, evaluation criteria, and benchmark datasets are well-aligned with the problem of watermarking knowledge graphs:\n1.\tMethods: The proposed KGMark framework leverages a latent diffusion model to embed watermarks in the frequency domain, addressing the unique challenges of spatial-temporal variations and structural complexities in dynamic knowledge graphs. The use of a Learnable Adaptive Watermark Mask Matrix and redundant embedding strategies enhances transparency and robustness while ensuring minimal disruption to the knowledge graph’s usability.\n\n2.\tEvaluation Criteria: The evaluation comprehensively assesses watermark detectability using AUC, transparency through cosine similarity and downstream task performance metrics (e.g., GMR, HMR, AMR, Hits@10), and robustness against various attacks (e.g., relation alteration, triple deletion, isomorphism variation). These metrics effectively capture the critical aspects of watermarking performance in knowledge graphs.\n\n3.\tBenchmark Datasets: The experiments are conducted on three diverse public datasets—Last-FM, MIND, and Alibaba-iFashion—which represent different real-world applications. These datasets provide a robust basis for evaluating the method’s effectiveness and generalizability across various knowledge graph structures and domains.", "theoretical_claims": "The paper presents theoretical claims supported by principles such as Latent Space Equilibrium and Information-Theoretic Robustness. These principles aim to ensure watermark transparency and robustness through mathematical formulations. The claims appear logically consistent and align with the problem context.", "experimental_designs_or_analyses": "The paper presents a well-structured experimental design with:\n\n1. Comprehensive evaluations on three benchmarks (Last-FM, MIND, Alibaba-iFashion) across diverse KG structures.\n\n2. Rigorous testing of watermark detectability, transparency, and robustness against multiple attacks.\n\n3. Comparative analysis of KGMark variants to highlight key components and their combined benefits.", "relation_to_broader_scientific_literature": "The paper effectively situates its contributions within the broader scientific context by drawing on key concepts from diffusion models, watermarking techniques[1] [2], and knowledge graph[3] management. It leverages the strengths of diffusion models to embed watermarks in a way that balances transparency and robustness[4], building on prior work that has demonstrated the effectiveness of these models in generating and protecting synthetic data[5]. Additionally, the paper integrates ideas from graph neural networks and watermarking to address the unique challenges of structured data, such as graph isomorphism and dynamic updates. \n\n1. Wen, Y., Kirchenbauer, J., Geiping, J., and Goldstein, T. Tree-rings watermarks: Invisible fingerprints for diffu sion images. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, pp. 58047 58063. Curran Associates, Inc., 2023.\n\n2.  Yang, Z., Zeng, K., Chen, K., Fang, H., Zhang, W., and Yu, N. Gaussian shading: Provable performance-lossless image watermarking for diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12162–12171, 2024b.\n\n3.  Yang, Y., Chen, J., and Xiang, Y. A review on the reliability of knowledge graph: from a knowledge representation learning perspective. World Wide Web, 28(1):4, 2024a.\n\n4.  Barman, N. R., Sharma, K., Aziz, A., Bajpai, S., Biswas, S., Sharma, V., Jain, V., Chadha, A., Sheth, A., and Das, A. The brittleness of ai-generated image watermarking techniques: Examining their robustness against visual paraphrasing attacks. arXiv preprint arXiv:2408.10446, 2024.\n\n5.  Bauer, A., Trapp, S., Stenger, M., Leppich, R., Kounev, S., Leznik, M., Chard, K., and Foster, I. Comprehensive exploration of synthetic data generation: A survey, 2024.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. Originality and Creativity: Adapting diffusion-based watermarking to structured data like knowledge graphs is novel. Traditional methods for images or text often fail to account for spatial-temporal variations and relational complexities, which KGMark effectively addresses.\n\n2. Clarity and Presentation: The paper presents its methodology clearly, with detailed explanations of theoretical foundations and practical implementations. Diagrams and pseudocode enhance understanding.\n\nWeaknesses:\n\n1. Scalability Concerns:\n\nThe experiments are limited to relatively small datasets, raising questions about the method’s scalability to larger, more complex knowledge graphs like Wikidata. Addressing scalability is crucial for real-world applications, where knowledge graphs often contain millions of entities and relationships.\n\n2. Generalizability:\n\nThe paper lacks a thorough discussion on how well KGMark would perform on different types of knowledge graphs (e.g., biomedical, social networks) or in diverse application scenarios. Demonstrating generalizability across various downstream domains would strengthen the paper’s impact.\n\n3.  Comparative Analysis:\n\nWhile the paper compares KGMark with its variants, it lacks a direct comparison with existing watermarking methods from other domains (e.g., image or text watermarking). Such comparisons would provide a clearer picture of KGMark’s unique advantages and potential limitations.", "other_comments_or_suggestions": "Overall, the paper is well-written and presents a novel approach to watermarking knowledge graphs. Here are a few suggestions:\n\n1. Clarify Scalability: Include a brief discussion on how KGMark can be scaled to handle larger knowledge graphs.\n\n2. Expand Generalizability: Add a section on potential applications beyond the tested datasets to highlight broader applicability.\n\n3. Proofread: Minor typos and grammatical errors should be corrected to enhance readability. For example, the Method section inconsistently refers to equations as \"Equ. (x)\" in some places and \"Equation (x)\" in others, which should be standardized..、", "questions_for_authors": "1. Comparative Analysis: How does KGMark compare to existing watermarking methods from other domains (e.g., image or text)? A direct comparison would highlight its unique advantages.\n\n2. Optimal Embedding Strategy: What is the optimal strategy for selecting vertices or communities for watermark embedding, and how does it influence performance under various attacks?\n\n3. Robustness vs. Transparency Trade-off: How does the learning process of the adaptive watermark mask matrix ensure it balances robustness and transparency without overfitting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers all agree to accept the paper. I recommend acceptance.
Decision: Accept (poster)