OpenNovelty.org

CheckMate! Watermarking Graph Diffusion Models in Polynomial Time

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 6.4Download Report PDF
GraphsWatermarkingDiffusion ModelsNetworks
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 dequantizes 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://anonymous.4open.science/r/checkwate.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Overall Novelty Assessment

The paper proposes CheckWate, a watermarking framework for graph diffusion models that embeds checkerboard patterns in latent eigenvalues with polynomial-time verification. According to the taxonomy, this work occupies the 'Latent Space Eigenvalue Watermarking' leaf under 'Graph Diffusion Model Watermarking', where it appears as the sole paper in its specific category. The broader 'Graph Diffusion Model Watermarking' branch contains only three papers total, suggesting this represents a relatively sparse and emerging research direction within the larger watermarking landscape.

The taxonomy reveals three main branches: graph diffusion model watermarking, GNN model watermarking, and static graph data watermarking. CheckWate's neighboring leaves include molecular graph diffusion watermarking and zero-watermarking approaches, both addressing generative model protection but through different mechanisms (Gaussian shading vs. plug-in verification). The sibling branches focus on discriminative GNN architectures with trigger-based methods and static dataset protection through topology modification. CheckWate bridges theoretical concerns about graph isomorphism with practical generative model protection, occupying a distinct position that combines diffusion model generation with isomorphism-invariant verification.

Among 27 candidates examined across three contributions, no clearly refuting prior work was identified. The core CheckWate framework examined 7 candidates with 0 refutations, while the dequantization mechanism and sparsification enhancement each examined 10 candidates, also with 0 refutations. This suggests that within the limited search scope, the combination of eigenvalue-based watermarking, approximate dequantization with theoretical guarantees, and latent sparsification for graph diffusion models appears novel. However, the analysis explicitly covers top-K semantic matches and citation expansion, not an exhaustive literature review, meaning undiscovered overlaps may exist beyond these 27 papers.

Given the sparse taxonomy structure and absence of refuting candidates among those examined, CheckWate appears to address an underexplored intersection of graph generation, isomorphism-invariant verification, and polynomial-time detectability. The limited search scope (27 papers) and emerging nature of graph diffusion watermarking suggest caution in claiming definitive novelty, though the specific technical combination—eigenvalue embedding with dequantization guarantees—shows no direct precedent within the analyzed literature.

Taxonomy

Core-task Taxonomy Papers
8
3
Claimed Contributions
27
Contribution Candidate Papers Compared
0
Refutable Paper

Research Landscape Overview

Core task: watermarking graph diffusion models with polynomial time verification. The field addresses intellectual property protection for graph-structured data and models, organized into three main branches. Graph Diffusion Model Watermarking focuses on embedding verifiable signatures into generative models that produce graphs, often leveraging latent space properties or eigenvalue manipulations to ensure efficient verification. Graph Neural Network Watermarking targets discriminative architectures, embedding triggers or backdoors that can be detected through model behavior on specific inputs. Static Graph Data Watermarking embeds marks directly into fixed graph datasets, modifying topology or node features while preserving utility. These branches reflect a progression from protecting static artifacts to safeguarding dynamic generative processes, with verification complexity emerging as a central concern across all settings. Recent work reveals contrasting priorities: some methods prioritize imperceptibility and robustness against adversarial removal (e.g., Imperceptible Watermarking[3], GUISE[8]), while others emphasize transferability across model architectures (Transferable Watermarking[2]) or plug-and-play deployment (PlugMark[6]). Knowledge graph and embedding-specific approaches like KGMark[5] and WGLE[7] address domain-specific constraints. CheckMate[0] sits within the latent space eigenvalue watermarking cluster, sharing conceptual ground with GENIE[1] in targeting generative diffusion models but distinguishing itself through polynomial-time verification guarantees—a feature that addresses scalability bottlenecks present in earlier graph watermarking schemes like Graph Watermarks[4]. This emphasis on computational efficiency positions CheckMate[0] as bridging theoretical rigor with practical deployment needs, contrasting with methods that achieve strong empirical robustness but lack formal verification bounds.

Claimed Contributions

CheckWate: polynomial-time watermarking framework for graph diffusion models

The authors introduce CheckWate, a novel framework that embeds checkerboard patterns into the eigenvalues of noisy latents during graph generation. By leveraging isomorphism-invariant eigenvalues, the method achieves polynomial-time watermark verification, circumventing the NP-hardness associated with graph isomorphism problems.

7 retrieved papers
Approximate dequantization mechanism with theoretical guarantees

The authors develop a method to reverse the quantization step in graph diffusion by using eigenvector properties to reconstruct continuous latents from discrete adjacency matrices. They provide theoretical bounds on reconstruction error and watermark detectability, enabling accurate watermark verification without solving NP-complete graph matching problems.

10 retrieved papers
Latent sparsification mechanism for robustness enhancement

The authors propose a sparsification technique that replaces unlikely entries in the reconstructed noisy latent with zeros, constraining eigenvalue distributions to prevent false positives. This mechanism improves watermark detection robustness, particularly under adversarial graph perturbations such as edge or node modifications.

10 retrieved papers

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Within the taxonomy built over the current TopK core-task papers, the original paper is assigned to a leaf with no direct siblings and no cousin branches under the same grandparent topic. In this retrieved landscape, it appears structurally isolated, which is one partial signal of novelty, but still constrained by search coverage and taxonomy granularity.

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

CheckWate: polynomial-time watermarking framework for graph diffusion models

The authors introduce CheckWate, a novel framework that embeds checkerboard patterns into the eigenvalues of noisy latents during graph generation. By leveraging isomorphism-invariant eigenvalues, the method achieves polynomial-time watermark verification, circumventing the NP-hardness associated with graph isomorphism problems.

Contribution

Approximate dequantization mechanism with theoretical guarantees

The authors develop a method to reverse the quantization step in graph diffusion by using eigenvector properties to reconstruct continuous latents from discrete adjacency matrices. They provide theoretical bounds on reconstruction error and watermark detectability, enabling accurate watermark verification without solving NP-complete graph matching problems.

Contribution

Latent sparsification mechanism for robustness enhancement

The authors propose a sparsification technique that replaces unlikely entries in the reconstructed noisy latent with zeros, constraining eigenvalue distributions to prevent false positives. This mechanism improves watermark detection robustness, particularly under adversarial graph perturbations such as edge or node modifications.

Table of Contents