CheckMate! Watermarking Graph Diffusion Models in Polynomial Time
Authors: Roberto Gheda
Abele Mălan
Robert Birke
Maksim Kitsak
Lydia Y. Chen
Venue: ICLR 2026 Poster (2026)
Keywords: Graphs
Watermarking
Diffusion Models
Networks
Primary area: learning on graphs and other geometries & topologies
TL;DR: A watermarking method for graph generative models, with verification  in polynomial time

Abstract: Watermarking provides an effective means for data governance. However, conventional post-editing graph watermarking approaches degrade the graph quality and involve NP-hard subroutines. 
Alternatively, recent approaches advocate for embedding watermarking patterns in the noisy latent during data generation from diffusion models, but remain uncharted for graph models due to the hardness of inverting the graph diffusion process.
In this work, we propose CheckWate: the first watermarking framework for graph diffusion models embedding checkerboard watermark and providing polynomial time verification. 
To address NP-completeness due to graph isomorphism, CheckWate embeds the watermark into the latent eigenvalues, which are isomorphism-invariant. 
To detect the watermark through reversing the graph diffusion process, CheckWate leverages the graph eigenvectors to approximately dequantize the discrete graph back to the continuous latent, with theoretical guarantees on the detectability and dequantization error. 
We further introduce a latent sparsification mechanism to enhance the robustness of CheckWate against graph modifications. 
We evaluate CheckWate on four datasets and four graph modification attacks, against three generation time watermark schemes. CheckWate achieves remarkable generation quality while being detectable under strong attacks such as isomorphism, whereas the baselines are unable to detect the watermark. 
Code available at: https://github.com/r-gheda/checkwate.

Published as a conference paper at ICLR 2026
CHECKMATE! WATERMARKING GRAPH DIFFUSION MODELS IN POLYNOMIAL TIME
Roberto Gheda
Abele Mälan University of Neuchâtel a abele ma anlunn ne.
Robert Birke University Turin
TU Delft
F-gheda@tudelftt.n ft.
bebert..irkk@unnie it
Maksim Kitsak
Lydia Chen
TU Delft
University of Neuchâtel yiyu. weseennninen.. ch
m. kkitsakttudelff....
ABSTRACT
Watermarking provides an effective means for data governance. However, con- ventional post-editing graph watermarking approaches degrade the graph quality and involve NP-hard subroutines. Alternatively, recent approaches advocate for embedding watermarking patterns in the noisy latent during data generation from diffusion models, but remain uncharted for graph models due to the hardness inverting the graph diffusion process. In this work, we propose Check Wa e: the first watermarking framework for graph diffusion models embedding check- erboard watermark and providing polynomial time verification. To address NP- completeness due to graph isomorphism, CheckWate embeds the watermark into the latent eigenvalues, which are isomorphism-inwe invariiinmnnaaiant.... To detect the wa- termark through reversing the graph diffusion process, CheckWate leverages the graph eigenvectors to approximately dequantize the discrete graph back to the continuous latent, with theoretical guarantees on the detectability and de- quantization error. We further introduce a latent sparsification mechanism to en- hance the robustness of CheckWate against graph modifications. We evaluate CheckWat e on four datasets and four graph modification attacks, against three generation time watermark schemes. CheckWate achieves remarkable gener- ation quality while being detectable under strong attacks such as isomorphism, whereas the baselines unable detect the watermark. Code available at: https: / htt///gtttu....// com/r gheda/checkwatee checkwate
INTRODUCTION
Watermarking is a long-established method for data owners to verify the ownership of various data types (Cox et al., 2002) and it has recently been adapted verify synthetic data from generative models (Yang et al. 2024). While graphs are used extensively for modeling real-world applica- tions (Simonovsky & Komodakis 20188) and synthetic graphs are increasingly adopted for knowl- edge discovery (Jo et al. 2023), a significant gap exists in watermarking solutions for them, espe- cially for synthetic graphs The conventional approaches (Zhao al. 2013 Eppstein et al. 2016) embed watermarks in graphs via post-editing, which reduces the graph quality and requires expo- nential time verification. In contrast, modern watermarking methods (Yang et al.) 22244] Wen al.)
2023 Zhu et al., 2025) embed the watermark at sampling-time in the noisy latents of diffusion models. These methods have the advantages quality conservation and robust detectability the expense of inverting the diffusson process. However, their effectiveness has only been validated on modalities other than synthetic graphs.
In contrast to images and tables, graphs can be represented in multiple adjacency matrices via iso- morphism, making differentiating (un)watermarkked graphs hard. Fig. illustrates an example of how node indices be arbitrarily swapped without changing the structure of the graph. The Graph Isomorphism (GI) problem, i.c.. determining whether two graphs are isomorphic, one of the few unresolved questions in complexity theory, not known whether it can be solved

---

Published as a conference paper at ICLR 2026
Watarmark Extraction
Watermerk Extraction
(a)
(b)
(c)
Figure 1: An example of how Graph Isomorphism disrupts watermark patterns. (a) A graph G (b) A valid representation of G, the watermarking pattern can be successfully extracted. (c) Using another valid representation (isomorphism) of G' disrupts the watermarking pattern.
Grohe & Schweitzer p020). While quasi-polynomin algorithms exist for small instances (Grohe & Neuen 2021), GI remains computationally infeasible for large graphs. Further- more, when graphs are modified through addition deletion of edges, solving GI requires address- ing the Graph Edit Distance (GED) problem (Bunke 1997). which is well-known to be NP-hard.
in P (Babai 2016
The discrete nature of graphs presents another unique challenge watermarking, as it complicates watermark verification, particularly when coupled with the GI problem. As graphs are often repre- sented via binary adjacency matrices, graph diffusion models, such GruM (Jo et al. (023), require moving from the continuous space to the discrete one through a quantization step. When watermarks are embedded latents, the verification of watermarks needs invert any graph back its latents, by first dequantizing the graph. Inverting this step requires matching the generated graph with its corresponding dequantized version. This is computationally infeasible due to the complexity of the GI and GED problems.
We introduce CheckWate, the first framework for watermarking graph diffusion models with a ro- bust verification in polynomial time. CheckWate consists of three key components. (i) A checker- board watermark technique that enables embedding watermarking on the noisy latent eigenvalues sampling time. Since eigenvalues the watermark in polynomial time with no loss generalization and without relying on any ap- proximation. (ii) An approximate dequantization mechanism that enables the transition from the discrete domain of the data to the continuous space of diffusion, thus accurate latent reconstruction and watermark verification. (iii) robust detection mechanism that further improves watermark detection robustness, especially for mitigating false positive verification. Drawing upon matrix spar- sification theory, identify reconstruction errors within the noisy latent and impose constraints on the distribution of their eigenvalues. Our work brings the following contributions:
commopphsm-invariian this allows to embed and extract
CheckWate is non-blind graph watermark algorithm with verification in polynomial time, circumventing NP-hardness from graph isomorphism.
CheckWate detects the presence of watermark by accurately inverting graph diffusion, via an approximate dequantization mechanism with a theoretical error bound.
Check CheckWate robustness against post-editing attacks is enhanced by a latent sparsification mechanism.
Extensive evaluation of CheckWate on the graph quality and watermark detectability on four datasets and four graph attacks.
2 RELATED WORK
Graph Diffusion Models Graph synthesizers have been of high interest for the scientific commu- nity the past years. Graph diffusion models generate data starting from random (symmetric) noise. Then, trained neural network iteratively predicts the probability distribution of clean graphs and moves toward such distribution via steps of Denoising Diffusion Probabilistic Model (DDPM) (Ho) al. 2020). Depending on the model, this diffusion can either happen the discrete the contin- wous space. GruM (Jo et al. 2023) introduced novel diffusion model based on Denoising Diffusion Bridge Models (DDBM) (Zhou et al.) 2023) that performs diffusion the latent continuous space and achieves state-of oftte-----h-rrrr generative performance. The denoising process of GruM is proven to converge to the discrete space of the graphs adjacency matrix up quantization.
2

---

Published as a conference paper at ICLR 2026
0.5
0.5
Winner Semiorcle
Wigner Semicircle
0.4
0.4
0.3
0.3
0.2
0.7
0.1
0.1
0.0
-4
-3
-2
-1
1
3
0.0
-4
-3
-2
-1
0
3
Eicervalue
[ioenvalue
(a) Eigenvalues of Gaussian Orthogonal Ensembles.
(b) Eigenvalues of Checkeeboard Ensembles.
Figure 2: Distribution of eigenvalues of random matrices. (a) The eigenvalues of Gaussian Orthog- onal Ensembles (N = 500) follow the Wigner semicirele law (bulk). (b) Checkerboard Ensembles (N 500, k 450, W = (+1.5, +2.5) have N-k eigenvalues outside the semicirele (blip).
Watermarking Synthetic Data Watermarking is one of the key techniques used for verifying the ownership of synthetic data. Effective watermarking requires imperceptibility and robust detectabil- ity. The watermark signals can be embedded during the model training, sampling- time, even post- data generation (He et al.) (024), having different degrees of tradeoff between the data quality and robustness. Post-editing watermarks are the conventional methods applied on real graphs. leading to significant quality degradation. To avoid this problem, newer methods such as TreeRing (Wen et al.) 2023) and Gaussian Shading (Yang et al., 2024)) embed pattern into the latent space. However, TreeRing directly disrupts the Gaussian distribution of noise, limiting the randomness of sampling and resulting in affecting model generative performance. Moreover, these techniques require to un- dergo an implicit diffusion model such as Denoising Diffusion Implicit Model (DDIM) (Song et al.) 2020 or Denoising Bridge Implicit Model (DBIM) (Zheng et al. (024) in order to be accurately in- verted. Which are the implicit versions of DDPM and DDBM respectively (details in Appendix A
Techniques similar to Gaussian Shading have been used to extend applicability to domains different from images such tabular data (Zuu et al. (025) and time series (Soi et al. (2025). Nevertheless, they still require to verify a pattern within the latent. This prevents the application of these methods to the domain of graphs, as graph isomorphism enables representing the data in N! ways.
Graph Watermarking The prior art on watermarking graphs centers on real graph, thus being post-editing approaches. The long standing challenge is to determine two graphs are isomorphic and only quasi time solutions exist. Eppstein et al. (2016) further shows that when undergoing adversarial attack, solving isomorphism requires to address the more complex graph edit distance problem, which is NP-hard. Specifically, /Zhao et al. (2015) and Eppstein et al. (2016)
provide post-editing applications for non-blind graph watermarking. However, Zhao al. 2015)
makes assumptions on the graph node degree distribution to make the GED problem tractable, while
remaining exponential in the cost and not being applicable to all graphs. Eppstein et al. (0016)
provides an approximate NP-complete solution to GI in exponential time. Recently, KGMark (Peng
al., 2025) addresses post-editing watermarking for knowledge graphs only, whereas /Bouréé et al. (2025) proposes watermark graphs in the Fourier spectrum assuming nodes are uniquely labeled.
All of these works make strong assumptions on the data or the attacks that can be performed by the adversaries.
CHECKWATE
We start with preliminaries on random matrix theory in Section 3.1 before introducing the Check-
Wate methodology shown in Fig. 3 In Section 3.2 we first delve into the watermark injection and detection mechanisms (steps 1. inverting quantization (steps C, Finally, in Secciini 3.4] we cover error mitigation strategy,
Then, in Section 3.3] we discuss our proposed method for
which prevents false positives under heavy adversarial perturbations. Further, we provide Check- Wate pseudocode in Appendix 1)
3

---

Published as a conference paper at ICLR 2026
Watermark injection
? Denoising Diflusion
3 Quantization
Checkerizea Ouussen Noise
G
VAAAVA
Generation
Pe ((0
Iscemorphiim Attark
Delection
bv (o
GF ~Vo"Ag-Var
Gº VaVi
Watermark detection
Reverse Dencising Diffusion
Appraximate Dequantization
Figure 3: Pipeline of CheckWate. ! Watermark injection.
Denoising diffusion. 3 Quan-
tization. Dequantization. ( Reverse denoising diffussin.
Watermark detection.
3.1 PRELIMINARIES ON RANDOM MATRIX THEORY
Graph diffusion models such as GruM rely on noisy latent variables modeled as Gaussian Orthog- onal Ensembles (GOEs) (Anderson et al., 2010), i.e., symmetric Gaussian random matrices. The following explains the fundamental properties of random matrix theory used in our framework.
Spectral measure The spectrum of graphs and random matrices essential in capturing informa- tion on the graph structure (Van Mieghem 2023). Eigenvalue distributions are typically divided into two regimes: the bulk (of order O(vN)) and the blip (of order O(N)). For GOBs of size N x N, all eigenvalues lie within the bulk. More precisely, when considering the normalized ensemble XN X/v N, the limiting spectral distribution p follows the Wigner semicircle law (Anderson et al. 2010 with radius R = 2. Fig. 2a shows the distribution of eigenvalues from GOEs.
Checkerboard Ensembles (As, W checkerboard ensembles were introduced by Chen et al. (020 as generalization of Burkhardt et al. (2018). Let (O, 1) be the standard normal distribution.
Definition 3.1. Fix & E N and k-tuple of real numbers W -Wi..... WR), then the N x N (k, -hhcheekerbaard ensemble ((k, W W)-CBE) is the ensemble of matrices C (Ciz) given by:
1) W.
i mod
Cji
i=j= = mod k, with E Z
Checkerboard ensembles have & eigenvalues in the bulk, while the remaining N cigenvalues in the blip. More precisely, for each W, E W. if W, appears i; times in the ensemble, k; eigenvalues of magnitude NW.kk + O(VN). Fig. shows the eigenvalue distribution from a Checkerboard Ensemble. For high enough k Checkerboard ensembles allow to apply significant changes the ensemble spectrum while forcing limited modifications from regular Gaussian noise. This allows strong detectability while preserving generation quality.
3.2 CHECKERBOARD WATERMARK
The key hurdle to embed and detect the watermark pattern on graphs lies in the inherent ambiguity of graph representation, illustrated in Fig. In contrast, taking the image positions cannot be freely permuted without severely degrading visual quality or even altering the picture's s entire meaning. This enables the application of pattern-based watermarks onto their latents, such as Gaussian Shading (Yang et al. (2024) and TreeRing (Wen et al., 2023). Similarly, tabular data can leverage column unambiguity apply row-level watermark detection (Zhu al. 2025
example, pixel
4

---

Published as a conference paper at ICLR 2026
To address this, CheckWate explores the properties of graph eigenvalues in both embedding and detection phases. To embed the watermark, step ①, we insert the checkerboard pattern in the noisy latent of synthetic graph at sampling-time which are not expected in regular GOF, while applying minimal changes to the latent. Specifically, applying minimal changes to the GOE, ensures that the generation quality is preserved. To detect the checkerboard pattern, we first revert the graph to its noisy latent and then inspect the presence of eigenvalues in the blip regime. The advantages of leveraging the eigenvalues of the latent are two-fold: polynomial time computation and isomorphism invariance. This allows to bypass the GI problem and detect watermark in (NN) with no approximation nor generalization loss.
This enables the presence of eigenvalues in the blip,
Watermark injection ! We start graph generation via a random symmetric matrix G* in the latent space. We define GO as checkerboard ensemble with W (W1.... Wi.) an array of size k
[ (N W..
1) i i mod k ==j=u mod k, with Z.
T - GT
Parameter tuning Both and W are hyperparameters that determine the magnitude and frequency of cigenvalues in the blip. They allow to balance generation quality with watermark detectability. In general, checkerboard ensembles have N - k eigenvalues in the blip. Thus, a lower value of increases the watermark strength. Each of the eigenvalues in the blip has magnitude NW./k: + (VNN). Thus, larger W increases the watermark detectability. At the same time, having a lower k increases the amount of non- non-Gaussian entries and a larger Wu/k increases the deviation from Gaussian noise. Both affect negatively generation quality creating a tradcoff with detectability: the larger W. and the smaller k the stronger the watermark and the lower the quality.
Watermark detection c To detect the watermark, we reverse the diffusion process and reconstruct a noisy latent GT" 2 GT, We detail the reconstruction process Section 3.3 Then, we compute the eigenvalues of the normalized G = G //N. If GT" is reconstructed from a watermarked graph, we expect N k eigenvalues to fall in the blip. Thus, we measure the (absolute) largest N k cigenvalues and expect them all to be >> 2. If GT is not reconstructed from a watermarked graph, G is GOE and expect all of its eigenvalues to fall in the bulk, i.e., the largest N - eigen- values are < 2. We derive the expected difference between the computed score of a watermarked graph G and non-watermarked one G to measure CheckWate detectability:
Theorem 3.1 (Watermark Detectability). Ler G be a normalized Gaussian Orthogonal Ensem- bles. Let GW be a N normalized (ks Ww) -.)-Cheecerbaard Ensembles. Let (G) the i-th largest eigenvalue of G. Detectability of CheckWate is defined as:
Lis1 N- A (GW) (N k) Eayy" G00
Liel A (GNW) NN k)
VNW. Ok1)-O((k)
Egy (K.
(2)
We prove Theorem 3.1 in full in Appendix C.I Equation 2 reinforces that the strength of Check- Wate watermark is proportional to W, and inversely proportional to k.
3.3 APPROXIMATE DEQUANTIZATION
Unlike other modalities, graphs are commonly represented via binary adjacency matrices. Hence, generating graphs requires transitioning from the continuous space of denoising diffusion models to the discrete space of binary adjacency matrices through quantization, step @. Inverting this step amounts to matching an edited graph to its dequantized matrix, which reduces to the NP-complete GI and GED problems. We further stress that it is not possible to accurately reconstruct the noisy latent without taking into account quantization and demonstrate this in Table I off 4
To overcome this, we provide a dequantization method, step ④ that leverages fundamental proper- ties of eigenvectors under permutation to approximately reconstruct the dequantized graph latent in ((3)). We discuss next the basic properties of this approximation and derive the exact reconstruc- tion error under the Frobenius norm.
Graph quantization 3 After diffusion, the obtained graph Go is composed of continuous values. Thus, we require to quantize Go to 0-1 graph adjacency matrix. After this step, obtain the
5

---

Published as a conference paper at ICLR 2026
quantized adjacency matrix A:
A = quantize G)), Ag E {0,1]
Approximate dequantization 4 For a given graph A', we need to verify the existence a check- erboard watermark. First, graph A' can be different, ie., permuted, representation of A:
A' PAP-1
where P is an unknown permutation matrix. To accurately reconstruct the original noise G? in continuous space, we need the dequantized version of A', i.e., G PGPP-1 Eigenvectors of permuted graphs permute accordingly up to change eigenbasis, i.e., VA where VA the cigenvectors of A, and Q is Block-diagone matrix that maps the eigenbasis of A to the one of A'. More precisely, Q = diag(Q..... QQ..... Qm) with m the number distinct eigenvalues of A and each Q; being rotation square matrix as large the algebraic multiplicity of eigenvalue X; e(Aa). We leverage this property and combine some algebraic simplification to obtain the approximation of the permuted dequantized graph G";
PV&Q R PVA
Theorem 3.2 (Approximate Dequantization). Let A' be a permulation of A based on a permutation matrix P. Let G be permutation of Go on the same permutation matrix P. Then, G can be accurately approximated as:
GO VV
We prove Theorem 3.2 in Appendix C.2 In the special case in which all the eigenvalues distinct, Q is the identity matrix and equality for [Equation 3 always holds. Further, the error given by the approximation in [Equation can be explicitly derived as function of Q:
Theorem 3.3 (Reconstruction Error). Let Go be an orthogonal matrix and Go computed in Equation 3 Then the reconstruction error can be derived as:
17
GG - GG
Σ
(VQ. Q (VA)slA)
(4)
We prove Theorem proveTheoremm33 3.3 Appendix
C.3 In general, the error increases with eigenvalue multiplicity:
the higher the multiplicity, the higher the error. For a graph G. the number of distinct cigenvalues e(G) and satisfies e(G)d d Therefore, maximum multiplicity always bounded by N d. In(N)
Graphs sampled from the Barabasi-Albert model (Albert & Barabási 2002) have d A In(pN]
Diffusion inversion From here the diffusion process can be easily inverted following one of the known paradigms of DDIM or DBIM (Wen et al., 2023) Yang et al., 2024| Zhu et al. 2025 Soi
et al. 2025). We detail diffusion implicit models and their inversion in Appendix A
Authorship identification via hash and sign To enable identification of the watermark author we use digital bash-based signature (Srivastava et al. 2023). Hash-based signatures a wide-spread cryptographic building block that provides authenticity, unforgeability, and undeniability (Srivastaval et al. 2023). The watermark author can hash-sign the key K V VVV which is then used to enable reversibility of the diffusion process and reconstruct the noisy latent to extract the watermark.
We stress that accurately computing the dequantized matrix Go is essential to enable watermark detectability demonstrate in our experiments in Section
3.4 ROBUST DETECTION VIA LATENT SPARSIFICATION
Even under perfect reversal of the diffusion process, the reconstructed latent G"" 'might be subject several perturbations due to approximation errors stemming from [Equation and adversarial perturbations on the graph A. Unlike watermark reconstructions in other modalities, where errors remain largely localized, eigenvalues encode global structural dependencies within the matrix and are thus far more sensitive to such disturbances. Consequently, the eigenvalues of the perturbed GOE might fall out of the bulk regime, i.e., > and lead to false positive behavior. To prevent this, we apply simple yet efficient robustness enhancing mechanism that replaces entries that were unlikely generated the original noisy latent:
GT max (NGTT),((TT) >0
T
(5)
0
otherwise

---

Published as a conference paper at ICLR 2026
Where <f-) and 6()) are the probability density functions of a normal Gaussian and Dirac distribu- tion, centered at and W respectively. 9 is a threshold parameter that determines the tolerance of the anomaly detection mechanism. This leads to replacement of entries with values unlikely belonging to the original noisy latent with zero entries, i.e., sparsification. Sparsifying the latent allows us to better control the behavior of the eigenvalues and prevent their explosion outside of the bulk.
Rationale After this process, G is sparse GOE. Let q be the number of non-zero elements per matrix row. When q = N. G is GOE and its eigenvalues follow the Wigner semicircle. When < N, most of the eigenvalues lie in the bulk, with higher density around zero (Evangelou 1992). More precisely, for small values of q, the density of eigenvalues is:
p(A) x
(6)
log ((^))*
as (Evangelou 1992). While exponential tails develop outside of the bulk domain, for high enough these eigenvalues are rare and close enough to the bulk not to create any practical problem for watermark detection even under heavy perturbations. We demonstrate this qualitatively in Appendix H and with numerical results in Table 2
4 EVALUATION
We consider four datasets from prior work on graph diffusion models (Jo et al. 2023 Vignac et al., 2022 Martinkus et al. 2022): Planar, Tree, Stochastic Block Model (SBM), and Proteins (Dobson) & Doig). Because no prior semantic watermarking methods exist for graph diffusion, we adapt two state-of-the-ar baselines to the graph domain: Gaussian Shading (Yang et al. 2024) and TreeR- ing (Wen et al.] 2023). We additionally design a graph-specific baseline, Bipartite, which is graph- invariant but severely compromises generative quality due the high correlation of entries of the noisy latents. Implementation details for all baselines, including Bipartite, are in Appendix B Fi- nally, None serves as the non-watermarked reference.
To evaluate generative performance, we follow the setting of Jo et al. (2023). We measure the maximum mean discrepancy (MMD) of four graph statistics between the set of generated graphs and the test set: degree (Deg.). clustering coefficient (Clus.), count of orbits with 4 nodes (Orb.), and the eigenvalues of the graph Laplacian (Spec.). We also compute the percentage of valid, unique, and novel (V.U.N.) graphs for which the validity is defined as satisfying the specific property of each dataset. We evaluate watermark detectability via Z-score, which measures the distance between the mean score of watermarked and non- woneraaerdrrked data normalized by the standard deviation.
4.1 GENERATIVE QUALITY AND WATERMARK DETECTABILITY
We run experiments with no attack on all four datasets. Results are showcased in Table 1 First, we can see that CheckWate achieves state-of-the-art generative quality. Namely, CheckWate is the best performing watermarking method 10 times out of 20, and second-best 9 times out of the remaining 10. The best baseline from the state-of-the-art is Gaussian Shading, which is provably lossless watermarking. TreeRing and Bipartite, fall significantly behind, as they perform up to 10 times worse than the best watermarking method depending on the dataset and quality metric. Both CheckWate and Gaussian Shading achieve generative performance comparable to the one obtained without watermark. Under the Proteins dataset, CheckWate significantly outperforms other baselines including None. We suggest that the enhanced variance obtained via the checkered entries compensates the lack of randomness in the used implicit model.
For detectability, all methods achieve consistent results, except for TreeRing. Bipartite achieves the best Z-score, but lacks generative quality. Gaussian Shading and CheckWate have compara- ble Z-scores, except on Proteins where CheckWate significantly outperforms Gaussian Shading. Finally, we emphasize the detectability obtained with No Dequantization. Not applying a dequanti- zation leads to almost complete -if not complete- loss of the watermark even under attack.
7

---

Published as a conference paper at ICLR 2026
Generative quality is reported as mean maximum discrepancy (MMD) and the ratio of valid, unique, and novel (V.U.N.) samples. Watermark detectability is evaluated via the Z-score, with results shown for both dequantized and non-dequantized graphs. Bold indicates the best result and underline the second best; arrows specify if lower or higher values are preferable. We note with a checkmark detectable Z-scores (> 10).
Table 1:
Quality Metries Orb.
Detectability (Z-Score)
Dataset
Watermark
Deg.
Clus. +
Spec.
V.U.N. (%)
Dequant
No Dequant.
None
0,0009
0:0373
0.0123
0.0078
72.5
Planar
Gaussian Shading
0.0008
0,00367
0.0472
0,0093
62.5
57.6
5.9
[V| = 64
TreeRing
0.0104
0.1255
0.2122
0.0188
1.0
0.0
Synthetic
Bipartite
0.0007
0.0412
0.0653
0.0101
67.5
4999
0.5
Check Wate (ours)
0.0008
0.0418
0.0137
0,0078
67.5
67.6
0.7
None
0.0007
0.0001
0,0126
55
Tree [V] 64
Gaussian Shading
0.0001
0.0090
67.5
59.0
2.9
TreeRing
0.0002
0.0002
0.0122
42.5
0.0
Synthetic
Bipartite
0.0002
0,0002
0.0124
45
4968
0.0
Check (ours)
0.0004
0.0093
47.5
45.0
0.3
None
0.005
0,0504
0.0058
SBM 44 [V] & 187 Synthetic
Goussian Shading
0.0105
0,0498
0.0629
0.0076
72.5
84.7 V
10.7 V
TreeRing
0.0264
0.0612
0.1100
0.0112
52.5
0.6
0.0
Hipartite
0.1178
0.6432
915.8
25.4
CheckWate (ours)
0.0041
0.0520
0.0552
0,0050
52.5
86.8 V
0.0
None
0,4315
0,5436
1.3283
0,2450
Proteins
Gaussian Shading
0.4358
0.5283
1.3332
0.2579
110.3
1.4
100
500 Real
TreeRing
0.4149
0.4137
1.3332
0.3009
1.5
0.0
Bipurtite
0,5114
1,0123
1.4257
0.5636
1724.0 V
2.2
Check Wate (ours)
0.0473
0.2156
0.5986
0.0440
404.7
2.0
Table 2: Watermark detectability (Z-score) under perturbations. The higher the better. Bold denotes best, underlined denotes second-best |/emax is average maximum graph eigenvalue multiplic- ity. We note with checkmark detectable Z-scores (> 10).
Winemee Delectahility (7-8cam 11)
Watermark
Ircer
homorpheer
Edge Deletion
Edge Addiiie
5%
Node Deletion I0%
Shading
2.5
TiecRinx
(4599
548.5
299,0
116.5
488.5
518
Checklate (ours)
(67.62/)
2.9
41.5
36.5
35.6
36.7 V
32.6
$0.9
21.8
50.5 V
31.5
28.6
Coneiin Shading
(900
8.6
0
2.8
122
31
1.9
1.7
3.3
1.3
TreeRing
(1.3)
0
0
Biporiic:
(4067.7
189.9
1037
133.
Checklatt (ours)
(45.0/)
3133
28.8
35.7
33.3
Guusiaa Shating
3.9
TreeRing
Biyer
(8946
107.5
134.1
54.
219.2
20.5
619.3
246.5
141.5
6332
256, /
17.5
Checklttte (ours)
(868-))
80.7
60.3
50.4
10.5 V
15.6
18..
10.6
11.1
$3.8 V
24.4
9.7
Gausiaa Shading
(11933
305.4
0.1
0,7
0S
IL7
0,
077
033
TracKing
(1.00
Bipus
(1734.0/)
1834.
CheokWate (ours)
124.2
4.2 ROBUSTNESS TO GRAPH PERTURBATIONS
We test watermark robustness under four graph-specific perturbations Table 2): Isomorphism, Edge Addition, Edge Deletion, and Node Deletion, each applied at strengths from 5% to 20%. Check- Wate remains detectable under all experimented attacks, with the lowest Z-score (9.7) observed for SBM under 20% node deletion. Bipartite is consistently the strongest watermarking method but sacrifices generative quality. The state-of-the-art methods fail at achieving statistically significant watermark most of the times as TreeRing never reaches a positive Z-score, and Gaussian Shading never surpasses Z-score of 5.3. Notably, under isomorphism, they both consistently achieve Z-score of O, confirming that they are not graph invariant. We also report the average maximum eigenvalue multiplicity [[mazz], showing that generated graphs rarely have low multiplicity. This reinforces the strength of our dequantization mechanism, even with the approximation in Equation 3
4.3 ABLATION STUDIES
8

---

Published as a conference paper at ICLR 2026
Table 3: Watermark detectability (Z-score) under perturbations with ideal dequantization. The higher the better for all. Bold denotes best, underlined denotes second-best.
Planur Datovet
Watermark Detociabiity (Z-Score ")
Watermark
Edge Deletion
Edge Addition
Node Deletion
Isomorphism
10%
Gaussion Shading
(41.6)
0.4
44.3
41.8
36,5
15.4
10.0
37.9
42.0
40.2
40.9
TreeRing
(1.2)
0.0
1.0
0.8
0.4
1.1
1.0
0.7
0..
0.5
0.0
Ripamite
(4820.8
4842.1
4790.6
4424.3
3547.2
858.0
4833.1
4866.8
CheckWate (ours)
(46.5)
46.5
45.6
48.7
52.8
45.4
37.7
20.8
38.1
37.3
37.7
Gaursian Shading
(40.0)
0.3
36.9
37.7
37.7
39.3
39.8
42.1
39.4
39.9
40.8
Tree
TreeRing
(1.0)
0.0
0.7
0.7
0.5
1.0
0.9
0.9
0.7
0.5
0.2
Hiparite
(2661:7)
2651.3
26R3.4
2788.7
2697.1
2759.1
2741.8
2637.4
2642.4
2636.8
2718.7
CheckWate (ours)
32.1
25.6
25.0
Gaussian Shading
(34.4)
0.3
74.1
73.8
67.1
70.4
69.0
77.1
73.7
69.9
75.4
SBM
TreeRing
(1.0)
0.0
0.7
0.4
(1.0
0.3
0.0
0.0
0..3
0.0
0.0
Bipartite
(837.1)
1230,0
964.1
15721.4
31918.5
29797.2
7406.3
1002.2
CheckWate (ours)
(36.8)
86.8
$7.0
47.4
23.2
31.0
18.3
18.0
55.6
36.3
10.3
Proteins
TreeRing
Gaussian Shading
(119.3)
11.0
150.8
151.2
161.3
150.6
153.7
152.5
152.9
153.7
153.3
Bipartite
(1724.0)
1729.8
1643.5
1647.3
16415
1682.6
1648.4
1641.3
1647.0
1648.3
1641.4
CheckHate (ours)
(405.2)
405.0
406.9
290.0
200.1
337.8
146.0
93.9
$70.9
144.0
89.0
Table 4: Watermark detectability (Z-score) under perturbations without sparsification mechanism. The higher the better for all. Bold denotes best, underlined denotes second-best
Pintar Dataset
Waternark Detectability (Z-Score 1
Watermark
Delction
Edge Addition
Node Delction
Isomorphism
5%
10%
20%
5%
10%
20%
5%
10%
20%
Gaussian Shading
(32.0)
TreeRing
(0.0)
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Ripartite
(3527.4)
132.1
54.8
60.0
75.4
18.4
0.7
55.5
54,8
58.9
CheckWate (ours)
(64.1)
35.0
37.4
35.2
32.4
0.0
0.0
0.0
32.2
29.9
29.1
Gaussian Shading
(28.3)
2.0
Tree
TreeRing
(0.0)
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Bipartite
(411.8)
5.5
5.0
3.4
4.1
3.3
CheckWate (ours)
(49.9)
46.8
40.0
30.1
33.4
0.7
0.0
35.7
36.1
27.1
Gaussian Shading
(65.1)
6.2
4.5
3.2
3.7
3.2
SBM
TreeRing
(0.0)
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Bipartite
(737200.7)
127821.4
3150,6
2302,1
395.0
49141.5
0.0
175934
2985.9
14.2
CheckWate (ours)
(86.8)
61.2
53.4
5.5
2.3
Proteins
Gaussian Shading
(71.1)
0.2
0.5
0.4
0.1
0.4
0.6
0.3
0.4
0.3
0.0
TreeRing
(0.0)
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Bipartite
(97.8)
97.3
97.3
97.3
97.3
97.3
97.3
97.3
97.3
97.3
97.3
CheckWate (ours)
(410.9)
136.4
3.1
Ideal dequantization We perform experiments in which assume the permutation matrix P to be known. We dequantize G A' P (A Go) P-1 and consider Go' to be the ideal result of dequantization. Table showcases the results. This allows us to analyze the difference in performance given by the approximation in [Equation 3] Che ckaate achieves enhanced watermark strength, especially under heavier attacks. This can be explained as the eigenvectors of G" tend to change more when under heavier perturbations, making the reconstruction from Equation less robust. Furthermore, we emphasize that isomorphism does not degrade CheckWate detectability, proving graph-invariaal affected the most is Gaussian Shading. Albeit, it continues to have insufficient detectability when under isomorphism as its watermark is not graph-invariant.
of the checkerboard watermarking, We further see that the baseline that is
Robust detection mechanism Finally, we perform experiments with the robust detection mecha- nism disabled. Results are showcased in Table We can clearly see that most Z-scores are reduced. Notably, under the edge addition attack, CheckWate is not detectable even under lighter attacks. This happens as the reconstructed latent diverges from the GOE assumption. This leads to the eigen- values diverging from the bulk. At the same time, applying the robust detection mechanism strains the latent to the sparsified GOE, making its behavior predictable, and forcing the eigenvalues to stay within the bulk. We showcase qualitative comparison in Fig. from Appendix H

---

Published as a conference paper at ICLR 2026
5 CONCLUSIONS
Motivated by the need to efficiently verifying ownership synthetic graph data, we propose CheckWate, the first sampling- -immn watermark for graph diffusion models. CheckWate embeds a checkerboard pattern in the noisy latent and detects the watermark in polynomial time using the noisy latent eigenvalues. The novel design of CheckWate leverages random matrix theory solve multiple hard graph watermarking challenges: bypassing NP-hardness of verifying graphs arising from graph isomorphism, and dequantizing discrete and isomorphic graph representations. Our wa- termark is not only theoretically grounded in watermark verification time and graph reconstruction error, but also practically robust against suuph-modiiications. Our evaluation across four datasets shows that CheckWate achieves state-of-the-art generative quality and remains detectable under graph-specific attacks such as isomorphism, while watermarks of prior are barely detectable. We discuss limitations and future work in Appendix
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our research, we include: code the proposed framework, pseu- docode of watermark detection in appendix. All used datasets are publicly available and instructions to reproduce our results are provided in the code repository.
ETHICS STATEMENT
Our proposed graph watermarking framework has broad applications claiming ownership over synthetic network data such as molecular structures used in drug discovery or material science ap- plications and human interactions on social media, or professional networks.
This paper written with the aid of publicly available LLMs in tasks such grammar checking, spelling correction, and minor rephrasing.
ACKNOWLEDGGENNTS
This work is funded by NEXTWORKx, collaboration between TU Delft and KPN future telecommunication networks. This research was partly funded by the DYMAN project funded by the European Union European Innovation Council under G.A. 101161930. M. Kitsak has been supported by the Dutch Research Council (NWO) grants OCENW.M20.244 and VI.C.242.106.
REFERENCES
Réka Albert and Álszzt-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002. Publisher: APS.
Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices. Number 118. Cambridge university press, 2010.
László Babai. Graph Isomorphism in Quasipolynomial Time, January 2016. arXiv:1512.03547 [cs].
URL http:
//axxiv.orr//abs/11222..33
Daniel Bernstein. ChaCha, a variant Salsa20.
Jade Garcia Bourrée, Anne-Marie Kermarree, Erwan Le Merrer, and Othmane Safsafi. Fast In- Spectrum Graph Watermarks, August 2025. URL http://axxivv.ooooo /ttp://www..../////////2220000. S.Xiv:2502.04122 [es].
Gabriel Budel and Piet Van Mieghem. Detecting the number of clusters in network. Jour- nal of Complex Networks, 86):cnaa044, March 2021. ISSN 2051-1310, 2051-1329. doi: 10. 1093/comnet/cnaa047. URL wtt.thtts///aaaeeeeees oup wtt.c/pp....c.ooce///aatttttaaat
10. DD.1033/comee///caa04//...
H. Bunke. On a relation between graph edit distance and maximum common subgraph. Par-
tern Recognition Letters, 18(8):689-694 August 1997. ISSN 01678655. doi: 10.1016/ 80167-865559770000033..
URL
elseiiier.lseee..............e.. com/retziews
e
10

---

Published as a conference paper at ICLR 2026
Paula Burkhardt, Peter Cohen, Jonathan WeWitt, Max Hlavacek, Steven J Miller, Carsten Sprunger, Yen Nhi Truong Vu, Roger Van Peski, and Kevin Yang. Random matrix ensembles with split limiting behavior. Random Matrices: Theory and Applications, 7(03):1850006, 2018. Publisher: World Scientific.
Fangu Chen, Jiahui Yu, Steven J Miller, and Yuxin Lin. The limiting spectral measure for an ensem- ble of generalized checkerboard matrices. arXiv preprint urXiv:2009.1083 2020.
Ingemar Cox, Matthew Miller, Jeffrey Bloom, and Chris Honsinger. Digital watermarking. Journal of Electronic Imaging, 1 11(3):414-414 2002. Publisher: Society of Photo-Optical Instrumentation Engineers.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4))771-783 Publisher: Elsevier.
David Eppstein, Michael T Goodrich, Jenny Lam, Nil Mamano, Michael Mitzenmacher, and Manuel Torres. Models and algorithms for graph watermarking. International Conference on Informa- Springer, 2016.
fion Security, pp. 283-301.
Ernssto Estrada and Juan A. veltguuezzeel Spectral measures of bipartivity in com- plex networks. Physical Review E. 72(4):046105, October 2005. ISSN 1539-3755, 1550- 2376. doi: 10.1009Physsoo077..0666000 URL https:/ //ti:k//iiikk./. aps org///i/ogo/o0 11C3/PhysRevE. 72. 6460
S. N. Evangelou. A numerical study of sparse random matrices. Journal of Statistical Physics, 69())361-333, October 1992. ISSN 1572-9613. doi: 10.1007/BF01053799 URL https:
ordoi.org/1.... O007/BF11053797
Martin Grohe and Daniel Neuen. Recent Advances on the Graph Isomorphism Problem, January
2021. URL http: /ttt:://arxiiz orq orq/ abs C1366
C1366 arXiv:201 1.01366 [cs].
Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the
ACM, 63(11):128-133) 134, October 2020. ISSN 0001-0782, 1557-7317.
doi: 10.1145/3372123.
https://// acm. otg 1t////001145/337222
Hengzhi He, Peiyu Yu, Junpeng Ren, Ying Nian Wu, and Guang Cheng. Watermarking Generative Tabular Data, May 2024.
14018 2Xv:22405.14015
[cs].
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6855 18551, 2020.
Jachyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with diffusion mixture. arXiv preprint arXiv:2302.03596 2023.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. SPECTRE:
Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators. In Proceedings of the 39th International Conference on Machine Learning, pp. 15159-15179. PMLR, June 2022. /tthsttps: httpt::::/ppoccccnngg. mlr. wwl..ppress/l12//arrrttaao
html
ISSN: 2640-3498.
Hongrui Peng, Haolang Lu, Yuanlong Yu, Weiye Fu, Kun Wang, and Guoshun Nan. KGMark: A Diffusion Watermark for Knowledge Graphs. arXiv preprint arXiv:2505.23873, 2025.
Martin Simonovsky and Nikos Komodakis. GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders, February 2018. URL
arXiv:1802.03488 [cs].
Zhi Wen Soi, Chaoyi Zhu, Fouad Abiad, Aditya Shankar, Jeroen M Galjaard, Huijuan Wang, and Lydia Y Chen. Wake Temporal Chained- Hashing Watermark for Time Series Data. arXiv preprint arXiv:2506.0644 2025.
Jaminng Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502. 2020.
11

---

Published as a conference paper at ICLR 2026
Vikas Srivastava, Anubhab Baksi, and Sumit Kumar Debnath. An Overview of Hash Based Signa- tures, 2023. URL htttt:://epriiiiii iacr. orgg 411 Publication info: Preprint.
Piet Van Mieghem. Graph spectra for complex networks. Cambridge university press, 2023.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.147555 2022.
Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein. Tree-rings watermarks: Invis- ible fingerprints for diffusion images. Advances in Neural Information Processing Systems, 36: 58047-58063, 2023.
Zijin Yang, Kai Zeng, Kejiang Chen, Han Fang, Weiming Zhang, and Nenghai Yu. Gaussian shad- ing: Provable performance-lossiee image watermarking for diffusion models. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 12162-12171, 2024.
Xiaohan Zhao, Qingyun Liu, Haitao Zheng, and Ben Y Zhao. Towards graph watermarks. In Proceedings of the 2015 ACM on Conference Online Social Networks, pp. 101-112, 2015.
Kaiwen Zheng, Guande He, Jianfei Chen, Fan Bao, and Jun Zhu. Diffusion bridge implicit models. arXiv preprint 2405 15885, 2024.
Linqi Zhou, Aaron Lou, Samar Khanna, and Stefano Ermon. Denoising diffusion bridge models. arXiv preprint arXiv:2309.164 2023.
Chaoyi Zhu, Jiayi Tang, Jeroen M Galjaard, Pin-Yu Chen, Robert Birke, Comelis Bos, Lydia Y Chen, and others. Tabwak: A watermark for tabular diffusion models. In International Conference Learning Representations, pp. 1-28. OpenReview. net, 2025.
LIST OF SYMBOLS
8(-)
Probability density function of Dirac distribution
A
The diagonal matrix of the eigenvalues, i.., diag \1, ........ AN)
Eigenvalue
A
Binary graph adjacency matrix
A'
Binary graph adjacency matrix to verify
GO
Generated graph (in the continuous space)
G
Noisy latent
GT
Reconstructed noisy latent
Vx
Figenvectors of matrix X
X
A normalized matrix, i.e., XN = X/VN
Xij
Entry i,j of matrix X
N(u,a)
Gaussian distribution with mean y and a
<(+)
Probability density function of Gaussian distribution
p(-)
Probability density function of eigenvalues of normalized matrix
diag(.)
Diagonal matrix
e(a)
Algebraic multiplicity of eigenvalue
12

---

Published as a conference paper at ICLR 2026
A BACKGROUND ON DIFFUSION MODELS
DDPM Diffusion models generate data starting from a noisy latent representation. Denoising Dif- fusion Probabilistic Model (DDPM) (Ho et al. 2020) has been at the forefront of generation of synthetic data. This framework aims at transitioning from a latent sampled from noise distribution (2T (0, 1)) to a sample of the data distribution 2y through iterative process. More precisely, at each step t. a neural network Eg predicts the noise (t, 21) to predict the next sample 2 as:
2t-1 00
aicolt, 2x) Vaz
ca(t, 21) + ofc 1 a1-1 11---1
of -
where Ot1,..., or are computed from predefinied variance schedule. c N(0, 1) is independent standard Gaussian noise. J, is noise that yields diversification in the generative process.
DDIM By setting o; 0 the generative process becomes deterministic, i.e., implicit. Meaning that, for starting noise 27, the generative process deterministically yields to the same 20. Notably, if the size of the steps is small, i.e., large T, the generative process can be accurately reversed and 2y can be reconstructed from 20 via:
01-1 2e + (VI+VV+++ V
a1+1
a4+1
EB (t, 21)
(8)
based on the approximation eo(1, 21) ~ cal1 1, 21 This paradigm is called the Denoising
Diffusion Implicit Model (DDIM) (Song et al. 2020). Due to capability of reconstructing noisy
latent, it has been used as the backbone of multiple watermarking methodologies (Wen et al. 2023
Yang et al. 2024 Zhu et al. 2025 Soi et al. 2025).
DDBM Denoising Diffission Bridge Models (DDBM) Zhou et al. 2023) generalize diffuusion by al- lowing the endpoints of the diffusion process to be arbitrary distributions rather than always starting from random noise. This enables denoising diffusion to operate usecases such image editing. DDBM learn a bridge score function s(1, x) via neural network. Then, the reverse process can be expressed stochastic differential equation (SDE):
dx' [f(x',t g(t))s(x' f)]dt g())dW
where f(x t) and gt) come from the forward reference diffusion process, and W is a standard Wiener process that introduces diversification in the generative process.
A.1 GRAPH DIFFUSION MODELS
Discrete Graph Diffusion Some of the state-of-the diffusion models perform diffusion using discrete graph representations in the latent space. DiGress (Vignac et al. 2022) is one of the most popular examples. DiGress represents noisy latents as Erdös-Renyi (ER) random graphs in which each edge is independently sampled with 50% chance. The generation follows discrete denoising diffusion process inspired by DDPM: at each timestep f, a neural network predicts a distribution p( GG'), from which the next graph G is sampled.
Continuous Graph Diffusion Other approaches operate on continuous graph representations. GruM (Jo et al. 2023). for instance. models noisy latents as Gaussian Orthogonal Ensembles. Then, the diffusion process is modeled through DDBM process that moves toward the target data dis- tribution. At each step, G' represents the mixture of the possible generated graphs. Relying on the Censtein-Ulhenbad bridge process, GruM shown to converge to the data distribution up to quantization.
B BASELINES
Gaussian Shading (Yang et al. 2024) is sampling-time watermarking framework designed for images. The watermark is embedded in the latent using secure stream cipher such as ChaCha20 (Bernstein) to get uniformly distributed random bits. The noisy latent is generated from these bits using distribution preserving sampling. When the noisy latent is reconstructed, the bits reconstructed. Then, the author can prove their ownership by comparing them with the
13

---

Published as a conference paper at ICLR 2026
generated by the secure stream cipher. Gaussian Shading is proven to deliver lossless gener- ative performance but is not isomorphism invariant as the pattern designed by the stream cipher is disrupted.
TreeRing (Wen et al. 2023) is a sampling-tmme watermarking framework designed for images. TreeRing embeds the watermark in the Fourier space of the noisy latent. When the noisy latent is reconstructed, the watermark is extracted via the Fourier transform. Then, its presence is detected via LI similarity from the original watermarking key and the reconstructed one. TreeRing yields reduced generative performance as it heavily disrupts the initial latent from the Gaussian assumption. Furthermore, it is not isomorphism invariant its pattern is disrupted.
Bipartite is a graph- -raah-invariant baselines we developed based on bipartite graphs. We leverage the fact that graph bipartivity can be verified regardless of the graph representation and that is mono- tonic property. Meaning, a subgraph of a bipartite graph is still bipartite. It starts by generating complete bipartite graph of size N x N. From its adjacency matrix, performs distribution preserv- ing sampling to generate the noisy latent. To detect the watermark, the noisy latent is reconstructed. Then, we discretize the noisy latent as:
5 if ((L) < 0.5
otherwise
Where & is the CDF of the standard normal distribution. To increase its robustness, we leverage monotonicity sample subgraph of L
f0 (L)) < 0.75
L -1 [1
otherwise
Recall that monotonicity means that a subgraph of a bipartite graph is always bipartite. The score
of the watermark is computed via the spectral bipartivity B(z) (Estrada & Bedrrguuzz-Velázqueee 2005). In general 1
2 < ((2) S 1. With (()) = and only a graph is bipartite, and ((2) +
when z is the complete graph and N - oc. Bipartite leads to reduced generative performance
generates noisy latents of non-independent Gaussian noise. It is isomorphism invariant as bipartivity
a graph property (Estrada & Rodríguez- Rodriguez-Velzzquzz 2005)
C PROOFS
C.1 PROOF OF THEOREM 3.1
From Chen et al. 2020) we know that the largest N - k eigenvalues are of magnitude: (1). Hence,
vNW./k+
Σ X ( (N k)
Bqw BGw-((,W)CCm
(VNw/k+
(10)
We now derive the expected average magnitude of the largest N eigenvalues of the GOE, For the sake of simplifying notation, let k = N E [0
Eisl k d (G (N k)
Egaw ~GOE
EGOE
[DDF Wigner (x) 12k' S x x 2]
(11)
Sy x PDD Fw igner (x)dx
(12)
P2 PDF igner (I)dxx
S2 V4-x" dx
= CDFwigger (2) CDF igner (k')
2x
(13)
(4 - 3
(14)
2k' 24'
aresin 2k
2
1x
O0K OKk2)
(15)
14

---

Published as a conference paper at ICLR 2026
Finally, derive the watermark detectability of CheckWate.
N-
E
X1(GW) ((((MM = E
Σ
E
Σ A(ONm)
(16)
VNw/k+ + -01)
(17)
C.2
PROOF OF THEOREM 3.2
With Go defined as Section 3.3
GO P
(18)
(19)
(20)
VA.VA
(21)
Equality for Equation 20 holds whenever Q
C.3 PROOF OF THEOREM 3.3
Whenever A has eigenvalue multiplicity
1, the reconstruction enror be quantified
|| - G = V| QV V - G
(22)
IVA QVVVAVV/G"VVV ' VAll
(23)
GIQV V
(24)
= Σ
(IQ.G Q G. 11:)
112)) 1/2
(25)
m==1
where || || is the Frobenius norm.
D PSEUDOCODE
Algorithm CheckWate Detection
Input: target graph A', reference graph G denoising model M
VA Eigenvectors (A')
2: VA Eigenvectors (Quantize (G9)
3: G"' + VA.Va A T do
Equation 3
4: for forl+ 1, 2,
5: G¹' -- (G
Reverse DBIM
6: end for
7: for (i, j) MEENXA N do
8: if max ((GTT) ).((T)) < 0 then
Equation 5
9: GT 0
10: end if
end for
12:
G
G"
[Normalization)
VN
X X Eigenvalues (GT'). |>| 2
BlipEigenvalues if [BlipEigenvalues]
N then
15: Return SUCCESS
end if
17: Return FAIL
15

---

Published as a conference paper at ICLR 2026
E LIMITATIONS
Watermark discrete latents Some graph diffusion models such as DiGress (Vignac al. 2022) rely on discrete noisy latent and discrete denoising steps DDPM. While inverting discrete denois- ing diffusion remains an untackled problem, techniques similar the checkerboard watermark of CheckWate can also be applied to discrete noisy latents. The key idea of Check Wate watermark lies in moving some of the eigenvalues outside of the bulk (i.e., Wigner semicircle) while applying minimal changes to the latent. In the context of continuous latents, we achieve this by applying the checkered entries. believe that the same idea can be applied in discrete space in the following way.
Eigenvalues of discrete noisy latents (i.e., Erdos-Renys matrices) also follow the Wigner semicircle law, similarly to GOEs, We are interested in moving some of these eigenvalues outside the bulk regime. Budel Van Mieghem (2021) studied the relationship between presence communities and eigenvalues in the blip. We suggest that enforcing the presence of communities in parts of the noisy latent can be used to reproduce CheckWate behavior in the discrete scenario. This can be leveraged to extend the checkered watermark behavior to discrete noisy latents. Furthermore, sparsifying ER graphs, reduces the magintude of its eigenvalues, similarly to the sparsified GOE. Thus, the robust detection mechanism CheckWate remains applicable.
Non-Blind Watermark Our watermark is mon-blind, meaning that the original data needed to ver- ify the presence of the watermark. State-of-the-art watermarking methodologies for images, tabular data, and time series provide blind watermarking, meaning that the watermark can be extracted and verified even without the generated data. No watermarking framework for graph data currently sup- ports blind watermarking, Addressing computational feasibility of non-bline graph watermarking a key step to enable future development this field. Extending CheckWate e to further support blindness is an interesting research gap that will be addressed by future work.
Provable resistance to forgery CheckWate e resistance forgery relies on hardness of dequantiza- tion. Despite our experiments in (Table I show that not using the key leads to impossible verification, is not possible to prove forgery resistance by applying the key after the diffusion process.
F ABLATION STUDY ON DIFFERENT VALUES OF k. W
Here, we widen our results with an extensive analysis of how k and W can affect Z-score and generative quality. The key observations are, as expected, generation quality degrades for larger values W of and smaller kt Accordingly. Z-score increases when smaller and larger. This confirms the theory discussed in Section
G ROC CURVES
We report the ROC curves of the experiments from Table and We provide results under Planar and SBM datasets (the latter one being the dataset with the lowest z-scores) with four different attacks at their maximum strength:
All figures show an AUC of 1.0, which means CheckWate always manages to achieve 100% True Positive Rate and 0% False Positive Rate.
We further provide the same ROC curves without the latent sparsification mechanism:
From the plots, can that under strong edge additions, the AUC of CheckWate reduces severely: 0.5 for Planar and 0.75 for SBM. A result that indicates little to no discriminatory ca- pability.
Furthermore, we would like to highlight figures in Appendix H in which we perform qualitative analysis the eigenvalue distributions of our experiments. Especially, Fig. 8 showcases how the eigenvalues the reconstructed latents tend to explode under edge additions when no latent sparsi- fication is applied.
16

---

Published as a conference paper at ICLR 2026
Table 5: Ablation study on different values for k, W on Planar dataset.
Parameters
degree
cluster
orbit
spectral
V.U.N.
Z-Score
è 0.9, W = +1.0
0.0006
0.0406
0.0039
0.0086
0.55
7.64
A 0.9, W =2.0
0.0009
0.0446
0.0113
0.0068
0.65
38.76
k 0.9, W +3.0
0.0007
0.053
0.0092
0.0087
0.675
95.47
0.9, W = +4.0
0.0011
0.0651
0.0154
0.0096
0.525
176.88
= 0.7, W = +1.0
0.0009
0.0424
0.0022
0.008
0.325
19.35
k 0.7, W +2.0
0.0007
0.0541
0.0119
0.0099
0.4
83.17
& = 0.7, W = +3.0
0.0015
0.0629
0.0283
0.0109
0,25
193.44
K 0.7, W +4.0
0.0021
0.0779
0.0352
0.0111
0.175
349.78
0.5, W #1.0
0.0007
0.0592
0.0046
0.0084
0.25
29.61
à 0.5, W +2.
0.0014
0.0664
0.0178
0.0114
0.275
126.95
0.5, W = +3.0
0.0021
0.0984
0.0354
0.0118
0.125
292.39
W 0.5, W #4.0
0.0047
0.1028
0.0631
0.0121
0.275
525.72
k 0.2, W +1.0
0.0031
0.2282
0.0197
0.0115
134.64
à 0.2, W = +-2
0.007
0.259
0.0734
0.0167
561.77
& 0.2, W =3.0
0.0132
0.2624
0.0435
0.0164
1288.26 26
k 0.2, W = +4.0
0.0198
0,2687
0.0729
0.0231
2303.01
Table 6: Ablation study on different values for k, W on Tree dataset.
Parameters
degree
cluster
orbit
spectral
V.U.N.
Z-Score
À 0.9, W =1.0
0.0001
0.0093
0.55
6.07
t = 0.9, W = =2.0
0.0002
0
0
0.0088
0.55
32.22
A 0.9, W =3.0
0.0001
0.0001
0
0.0094
0.5
81.35
à = 0.9, W = +4.0
0.0001
O
0.0093
0.65
152.06
À 0.7, W =1.0
0.0001
0
0.0084
0.575
16.43
= 0.7, W = +2.0
0.0002
0.0001
0.0001
0.0092
0.55
73.77
k 0.7, W = +3.0
0.0002
O
0.0002
0.0089
0.35
172.15
& 0.7, W = +4.0
0.0001
O
0.0002
0.0088
0.25
316.53
à 0.5, W = +1.0
0.0004
O 0.0001
0.0096
0.65
25.04
à 0.5, W =2.0
0.0001
0.0002
0.0117
0.55
113.12
& 0.5, W = +3.0
0.0003
0.0001
0.0003
0.0111
0.425
262.96
0.5, W = +4.0
0.0002
0.0005
0.0004
0.0093
0.325
471.28
0.2, W = +1.0
0.0001
0.1547
0.0002
0.0146
0.05
120.53
k 0.2, W +2.
0.0006
0.4638
0.0005
0.0148
514.98
= 0.2, W = +3.0
0.0007
0,5882
0.0009
0.0182
1162.53
0.2, W +4.0
0.0008
0.6223
0.0015
0.0151
2068.21
R0C Cerve Lndor More Stuck okrar
RBC Canves ander ODSE X2D TIUM NEaCC glanert
ROC Carves ander C2dC NEMOVIA Atack (parao
33
03
02
(a)
(b)
(c)
(d)
Figure 4: ROC curves of CheckWate on Planar dataset with latent sparsification. (a) ROC curve under attack; (b) ROC curve under edge addition 20%; (c) ROC curve under edge removal 20%; (d) ROC curve under node deletion 20%. AUC is 1.0, indicating perfect discriminatory capability.
17

---

Published as a conference paper at ICLR 2026
Table 7: Ablation study on different values for W on SBM dataset.
Parameters
degree
cluster
orbit
spectral
V.U.N.
Z-Score
è 0.9, W = =100
0.0025
0.0488
0.0507
0.0064
0.775
5.67
A 0.9, W =2.0
0.0021
0.0511
0.0574
0.0045
0.6
27.44
k 0.9, W = +3.0
0.0026
0.052
0.0676
0.0056
0.625
64.8
0.9, W = +4.0
0.0022
0.0514
0.0665
0.0056
0.6
117.22
= 0.7, W = +1.0
0.0035
0.0501
0.072
0.0067
0.725
13.26
k 0.7, W +2.
0.0048
0.0533
0.0517
0.0055
0.575
55.14
& = 0.7, W = +3.0
0.004
0.055
0.075
0.0055
0,475
126.23
K 0.7, W +4.0
0.0044
0.057
0.0855
0.0057
0.525
225.89
0.5, W #1.0
0.0024
0.0524
0.0825
0.0049
0.775
20.29
K 0.5, W +2.
0.0044
0.0528
0.0829
0.0046
0.75
83.1
= 0.5, W = +3.0
0.0048
0.0576
0.0754
0.0058
0.625
188.22
W 0.5, W #4.0
0.0048
0.058
0.0916
0.0055
0.6
336.24
K 0.2, W +1.0
0.0029
0.0514
0.0783
0.0047
0.725
82,68
h 0.2, W = +22
0.0036
0.0507
0.0693
0.0063
0.575
339.44
K 0.2, W =3.0
0.0033
0.0497
0.0485
0.0057
0.425
769.34
k 0.2, W = +4.0
0.0024
0.0502
0.0571
0.0065
0.3
1373.52
Curvoo EOCE ACOITCC Abrac Deer
Curvo L0C2 TEMCNAL Mirc: bdbm)
Charlher HNC 1.X
AMP
61
64
63
02
60
04
13
(a)
(b)
(c)
(d)
Figure 5: ROC curves of CheckWate on SBM dataset with latent sparsification. (a) ROC curve under no attack; (b) ROC curve under edge addition 20%; (c) ROC curve under edge removal 20%; (d) ROC curve under node deletion 20%. AUC is 1.0, indicating perfect discriminatory capability.
(a)
(b)
(c)
(d)
Figure 6: ROC curves of CheckWate Planar dataset without latent sparsification. (a) ROC curve under no attack; (b) ROC curve under edge addition 20%; (c) ROC curve under edge removal 20%; (d) ROC curve under node deletion 20%. Under edge addition, AUC is 0.5, indicating limited discriminatory capability.
Altogether, these results show that: (i) CheckWate provides remarkable performance under TPR and FPR; (ii) Latent sparsification is key for preventing performance degradation under major per- turbations.
H QUALITATIVE RESULTS
18

---

Published as a conference paper at ICLR 2026
10C
HOUPE Matice
(a)
(b)
(c)
Figure 7: ROC curves of CheckWate SBM dataset without latent sparsification. (a) ROC curve under no attack (b) ROC curve under edge addition 20% (c) ROC curve under edge removal 20% (d) ROC curve under node deletion 20%. Under edge addition, AUC is 0.74, indicating limited discriminatory capability.
Ligenvalues (40 graphs)
0.21
025
020
0.15
Criedt
2.35
0.30
3.00
0.00
Byenvelke
(a)
(b)
Eigervaalues reconstrucied samples gracts)
Eigenvalues reconstructed samples (4U graphs))
0.10
0.00
068
0.50
Danety
2.00
0.64
0.07
-0
Dgenvalte
Dieervluee
(c)
(d)
Figure 8: Comparison of eigenvalues with and without anomaly detection mechanism Planar dataset under edge addition attack (10%). (a) and (b) show reconstructed eigenvalues of No wa- termark and CheckWate respectively, with anomaly detection. (c) and (d) show reconstructed eigenvalues of No watermark and CheckWate respectively, without anomaly detection.
19

---

Published as a conference paper at ICLR 2026
Bigansolues rescenstnuctoe
Eiganuciues recenstructoe
0.5
Dete3
Dere.0
0079
0.5
0.5
Pigneatiie
(a) Without watermark.
(b) With Checkwate watermark.
Figure 9: Distribution of reconstructed eigenvalues on Planar dataset under no attack.
Eigansatuuss reconstructse samples (40 graphis
Eigansalues reconstructec samstess 140 grappss)
0.5
0..0
0.55
Ogenwolaz
Oigeivalz
Without watermark.
(b) With CheckHate watermark.
Figure 10: Distribution of reconstructed eigenvalues Planar dataset under isomorphism.
Eggewaluess reconstructee samples graphs)
Elgenvolues graphs)
0.20
005
(a) Without watermark.
(b) With CheckWate watermark.
Figure 11: Distribution reconstructed eigenvalues on Planar dataset under 20% edge removal.
20

---

Published as a conference paper at ICLR 2026
rescenstuuctee
recenszructoe
1015
Dere-0
0.5
0.5
0.5
Pigneatipe
(a) Without watermark.
(b) With Checkwate watermark.
Figure 12: Distribution reconstructed eigenvalues on Planar dataset under 20% edge addition.
Eigansatuus reconstructsec samples (40 graphis
Eigansaluess reconstructae samstes 140 grapps))
0.30
0.75
10.5
00.0
0.25
Ogenwolaz
Oigenvalz
Without watermark.
(b) With CheckHate watermark.
Figure 13: Distribution of reconstructed eigenvalues on Planar dataset under 20% node deletion.
Eigewaluess samples graphs)
Elgenvolues graphs)
0.30
0.1
(a) Without watermark.
(b) With CheckWate watermark.
Figure 14: Distribution of reconstructed eigenvalues on Tree dataset under no attack.
21

---

Published as a conference paper at ICLR 2026
rescenstnuctoe
6.2
Dete:
Dere-9
0.5
0.58
Pigneatuee
(a) Without watermark.
(b) With Checkwate watermark.
Figure 15: Distribution of reconstructed eigenvalues on Tree dataset under isomorphism.
Eigansatuuss reconstructse samples (40 graphis
Eigansalues reconstructee samstess 140 grappss)
0.30
0.25
0.30
075
0.12
0.03
0923
Ogenwolaz
Ogennallz
(a) Without watermark.
(b) With CheckWate watermark.
Figure 16: Distribution of reconstructed eigenvalues Tree dataset under 20% edge removal.
Eigewvluess samples graphs)
Elgenvolues graphs)
0.00
0.73
01550
0.55
0108
00.0
6.75
(a) Without watermark.
(b) With CheckNate watermark.
Figure 17: Distribution of reconstructed eigenvalues on Tree dataset under 20% edge addition.
22

---

Published as a conference paper at ICLR 2026
Eigaesatuus reconstructse samples (40 graphr)
Eigansalues reconstructed samstes 140 grapps))
0.35
0.5
Ogenwolaz
Oigenvalz
Without watermark.
(b) With CheckHate watermark.
Figure 18: Distribution of reconstructed eigenvalues Tree dataset under 20% node deletion.
23


Reviews:
[{"review_id": "ccYPl86GdI", "reviewer": "Reviewer_kR4u", "summary": "The paper proposes a new graph watermarking approach CheckWate with three main contributions:\n(1) a checkerboard watermark technique that embeds signals into noisy latent eigenvalues; since eigenvalues are isomorphism-invariant, detection can be done in polynomial time without solving NP-hard GI/GED problems;\n(2) an approximated dequantization mechanism that projects discrete graphs to a continuous space for accurate latent reconstruction and watermark verification;\n(3) a robust detection mechanism aimed at reducing false positives.\n\nThe experiments show that CheckWate can improve watermark detectability while maintain the graph quanlity.", "questions": "1. Please report quantitative divergence between checkerboard ensembles and Gaussian across $k$. Where is the operational $k$ range in which deviations remain “limited”?\n2. What false positive rates arise from perturbed GOE without the robust step, and what are the FPRs with it? A per-dataset breakdown would substantiate the robustness claim.\n3. Please add a citation and methodological details for the baseline Bipartite, and provide quality-controlled tuning where detectability is traded for higher quality to assess how strong Bipartite can be under matched quality.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well written, logically structured, and easy to follow. The problem is important and well motivated for graph diffusion watermarking.\n* Leveraging eigenvalues for watermark embedding/detection is a reasonable way to bypass GI/GED and keep verification polynomial.\n* The method addresses graph watermark embedding, approximate dequantization, and robust detection in one framework, largely solving the targeted problem at a conceptual level.", "weaknesses": "* Sec. 3.1 states that for high enough $k$, checkerboard ensembles approximate regular Gaussian noise \"while forcing limited modifications\", but there is no quantitative analysis of how does the distribution change with $k$. Since regular Gaussian noise is a key assumption for diffusion latents, this gap weakens the claim.\n* Sec. 3.4 argues that eigenvalues of perturbed GOE may leave the bulk and cause false positives and proposes sparsification to fix this, but experiments do not present the baseline FPR (without robust detection) versus post-fix FPR to show the reduction magnitude.\n* An important baseline, Bipartite, is used but lacks a clear literature reference and detailed explanation in the main text; given its very high Z-scores yet relatively low quality metrics, it would be informative to see tuned variants that trade detectability for better quality, potentially making it a stronger baseline.\n* The paper states that disabling the robust detection mechanism reduces Z-scores, but comparing Table 2 and Table 4 shows both increased and decreased Z-scores, which is inconsistent with the paper's statement.\n* Line 360: “Appendix ??” appears in the draft and should be fixed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "dVsyhRQuVz", "reviewer": "Reviewer_DEc1", "summary": "The authors introduce CheckWate, a novel graph watermarking method for diffusion models. Instead of trying to watermark graph features directly, it is much more efficient to plant the watermark into graph properties that are invariant to isomorphism, i.e., into eigenvalues. This circumvents the watermark detector's need to handle different representations of the same graph, leading to compute performance gains. The authors also introduce dequantization and sparsification mechanisms, which they experimentally validate to be important. The CheckWate system appears to strike a balance between good detection (robustness) and graph quality in comparison to major watermarking systems.", "questions": "- CheckMate (instead of CheckWate) in the title - is this intentional?\n- How is it possible that Gaussian Shading is provably lossless, yet generation quality is at times worse than lossy watermarks (Table 1)? On row 396: \"CheckWate achieves state-of-the-art generative quality\" despite it being lossy.\n- One of the major upsides of CheckWate seems to be efficient detection (i.e., with respect to \"conventional\" exponential time approaches). How does the scheme compare concretely to the other baselines in raw compute cost? Apologies if I missed this in the paper.\n- Do you expect it to be possible to force keys (K) to be the same? This would lead to forgery attacks. It would be nice to have some kind of threat model to make it clear how \"secure\" the watermark needs to be. I suspect this is not as much of a concern as it would be for generic mode watermarks since the graph domain may be less adversarial, but I'd like clarity on this.\n\nPresentation remarks\n- Row 21/22: approximately dequantizes - > approximately dequantize\n- Row 360: Appendix ??", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The watermarking method is novel and its empirical performance is backed by theoretical underpinnings. Clarity on limitations is to be commended - potential future research paths are important and interesting problems. Paper is well-written and scientific with only a few points of concern (mentioned below).", "weaknesses": "- Polytime detector is presented as a major feature of CheckWate, but it is not emphasized in the body. The method appears clearly better than the prior work on graph watermarking that do not circumvent superpolynomial subroutines, but it is unclear how performance compares to the baseline (image) watermarking schemes evaluated.\n- I believe graph isomorphsim is known to be in NP (e.g., Babai's quasipolynomial algorithm [1]), but not known to be NP-complete. There are statements in the paper that contradict this, e.g., row 50.\n- The selected baselines are predominantly image domain watermarks. There is limited comparison to graph domain watermarks.\n- \"exact\" detection mentioned in the abstract is perhaps misleading. Might be worth rephrasing.\n\n[1] Babai, László. \"Graph isomorphism in quasipolynomial time.\" Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "4QwJJlWIHj", "reviewer": "Reviewer_kbtq", "summary": "This paper proposes CheckWate, the first watermarking framework for graph diffusion models that enables verification in polynomial time. Traditional methods are challenged by the computationally hard Graph Isomorphism (GI) problem. To bypass this, CheckWate embeds a \"checkerboard\" watermark into the latent eigenvalues, which are isomorphism-invariant. The framework uses an approximate dequantization mechanism to revert the discrete graph to its continuous latent for verification and a latent sparsification method to improve robustness against attacks. Experiments demonstrate that CheckWate maintains high generation quality and is robust against attacks like isomorphism, where baselines fail completely.", "questions": "See the weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tIt introduces CheckWate, the first watermarking framework specifically designed for graph diffusion models that provides exact and polynomial time verification. \n2.\tThe framework demonstrates strong robustness against various graph modification attacks, including isomorphism, edge deletion, edge addition, and node deletion.", "weaknesses": "1.\tThe paper's primary claim of efficiency is supported by theoretical complexity analysis but lacks empirical validation. A direct comparison of wall-clock runtime against baseline methods, particularly on large-scale graphs, would be necessary to fully substantiate the practical performance benefits of the proposed polynomial-time approach.\n2.\tThe paper could benefit from a careful proofreading to correct minor typographical errors (e.g., around line 360 in the provided draft), which would improve the overall clarity and presentation quality.\n3.\tThe non-blind nature of the watermark raises significant scalability concerns. The paper does not address the retrieval problem when the database of original watermarked graphs (c) is large. Verifying a suspect graph would seem to require a linear scan through all c candidates, leading to a total complexity of $c \\cdot O(N^3)$, which may be impractical for large-scale auditing or copyright enforcement scenarios.\n4.\tThe paper lacks a sensitivity analysis for the key hyperparameters (k, W). A thorough ablation study is needed to demonstrate how different choices of k and W affect the fundamental trade-off between watermark robustness and generative quality, which is crucial for understanding the method's practical applicability across different datasets and requirements.\n5.\tThe reliance on Z-score as the primary metric for detectability is insufficient and potentially misleading. The paper's own results in Table 2 show the Bipartite baseline achieving Z-scores that are an order of magnitude higher than CheckWate, making the proposed method appear far weaker. To provide a true measure of effectiveness, the authors must report standard classification metrics. Reporting the watermark detection ACC and AUC is essential to clarify whether CheckWate's Z-score, while lower, is already sufficient for near-perfect detection, thus framing Bipartite's superior score as a result of severe, quality-damaging overkill.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "WQHUmchBZC", "reviewer": "Reviewer_8DVk", "summary": "This paper introduces CheckWate, a watermarking framework for graph diffusion models that enables polynomial-time watermark verification. The method embeds a checkerboard pattern in the eigenvalues of the latent diffusion space.  The benefit of this approach is that eigenvalues are isomorphism-invariant. Prior techinques based on graph isomorphism (or graph edit distance) run into the issue that these problems are NP-hard. This approach avoids that issue.  \n\nExperiments on four datasets show strong performance under various attacks (isomorphism, edge/node perturbations), outperforming prior diffusion watermarking methods such as Gaussian Shading and TreeRing.", "questions": "What is the empirical running time for watermark detection?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a watermarking method specifically designed for graph diffusion models, a growing area in generative AI and data governance.\n\nThere are mathematical results with proofs.\n\nThere's a good set of experiments: multiple datasets, attacks, comparison approaches.", "weaknesses": "Assumptions (continuous latent spaces?).  (The paper states it could be applied to discrete latent spaces in Appendix D, but doesn't discuss fully.)\n\nWatermark is non-blind.  \n\nPolynomial time here is O(N^3), which is non-trivial;  accordingly, it seems, experimental tests are for graphs with less than 500 nodes. More information on running time would be useful.  \n\nSome writing things to check (I see ?? for missing references, e.g., Appendix ??, please check).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "RhOzyDt1ws", "reviewer": "Reviewer_KeKm", "summary": "This paper proposes CheckWate, a novel sampling-time watermarking framework for graph diffusion models. By embedding checkerboard patterns into the eigenvalues of noisy latent representations, CheckWate achieves isomorphism-invariant, polynomial-time watermark verification. To enable detection from quantized (i.e., discrete) graphs, the authors develop an approximate dequantization method based on spectral properties, and introduce a latent sparsification mechanism to suppress false positives under adversarial graph perturbations. The method is thoroughly evaluated across multiple synthetic and real-world graph datasets under diverse attacks, showing strong generation quality and watermark detectability.", "questions": "Please refer to the weakness part. In short,\n- Can you report ROC/AUC curves or TPR/FPR under fixed thresholds, in addition to Z-scores?\n- Why was 2 chosen as the cutoff between bulk and blip eigenvalues? Have you tested threshold robustness?\n- How does watermark strength (via k and W) affect the tradeoff between detectability and dequantization error?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is the first paper to explore watermarking in graph diffusion models, extending prior image-based techniques to a much more complex domain.\n- The use of graph eigenvalues as watermark carriers is well-motivated by their isomorphism invariance, and the checkerboard embedding leverages known spectral laws to ensure detectability.\n- The approximate dequantization and sparsification modules are theoretically grounded and practically effective, enabling detection even under isomorphism and heavy graph edits.", "weaknesses": "- Z-score does not reflect full detection performance    \nWhile Z-score is useful for summarizing distributional separation, it does not directly reflect practical detection metrics such as true positive rate (TPR), false positive rate (FPR), or ROC curves. As a reviewer, I would prefer to see:\n    - Detection threshold selected to ensure low FPR (e.g., 1%), then report TPR.\n    - Alternatively, a ROC/AUC analysis on the per-graph detection scores.\nThis is especially relevant for real-world deployment or fair method comparison.\n\n- The use of “2” as the bulk-blip threshold lacks justification    \nThe watermark detection pipeline considers eigenvalues with magnitude >2 to be outside the bulk (Line 237). While this is motivated by the Wigner semicircle law, the choice of 2 as a hard threshold can be brittle since real data distributions are finite and noisy.\nI recommend reporting sensitivity analysis of Z-scores under varying thresholds (e.g., 1.8/2.2) or using quantile-based definitions.\n\n- Tradeoff between watermark strength and dequantization accuracy is underexplored     \nAccording to Line 295 and Theorem 3.3, the dequantization error increases with eigenvalue multiplicity, which itself depends on watermark strength (larger W, smaller k). This raises a natural question: Does stronger watermarking hurt detectability due to worse latent reconstruction? The authors should analyze this tradeoff explicitly, possibly via a plot of detectability vs. reconstruction error for varying k and W.\n\n- Line 360 has a type of \"Appendix ??\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)