Source-linked AI summary
A Robust Watermark-based Fingerprint Framework for GNNs Ownership Verification
Han Zhang, Yan Wang, Guanfeng Liu, Pengfei Ding, Huaxiong Wang, Kwok-Yan Lam
TL;DR
GNN ownership verification must address performance degradation from out-of-distribution watermarks, unrealistic watermark-training assumptions, and dependence on specific output levels. REMARK generates crafted in-distribution watermarks and extracts fingerprints from output differences, achieving state-of-the-art accuracy, robustness, and generalizability across datasets and architectures. The framework preserves protected-model utility while removing the stated verification assumptions.
Problem
Existing GNN ownership-verification methods face out-of-distribution watermark degradation, watermark-containing training-set assumptions, and dependence on specific output levels.
Method
REMARK generates crafted in-distribution watermark graphs using protected-model decision logic and training-set distributions, then extracts fingerprints from output differences across watermarked and original graphs.
Results
REMARK achieves state-of-the-art ownership-verification performance in accuracy, robustness, and generalizability across six real-world datasets and four GNN architectures.
Takeaways & Limitations
REMARK preserves protected-model utility, removes watermark-training and fixed-output-level assumptions, and supports robust verification across multiple output levels.
Abstract
from arXiv · showhide
The high training cost of Graph Neural Networks (GNNs) has raised growing concerns regarding model ownership infringement, such as model stealing and unauthorized misuse. To verify model ownership and prevent significant economic losses, two groups of GNN Ownership Verification (OV) methods have been proposed: watermark-based methods and fingerprint-based methods. However, these methods typically face three limitations: (1) the performance degradation of protected models caused by out-of-distribution (OOD) watermark graphs with respect to the training set; (2) the unrealistic assumption that surrogate models have been trained on a watermark-containing training set; and (3) over-reliance on specific output levels for fingerprint extraction. In this paper, we propose a Robust watErMArk-based fingeRprint frameworK for GNNs, named REMARK. REMARK first generates carefully crafted in-distribution watermark graphs that maximize output differences between GNN models, thus mitigating OOD-induced performance degradation. REMARK then extracts robust fingerprints from these output differences to verify GNN ownership, thereby removing the assumptions that surrogate models must be trained on a watermark-containing dataset or expose specific output levels. Extensive experiments across widely used real-world datasets and GNN architectures demonstrate that REMARK achieves state-of-the-art OV accuracy and robustness while preserving the utility of protected models.
1. Introduction
Existing GNN ownership-verification methods rely on watermark-triggered behavior or output-distribution fingerprints, but face distributional, training-data, and output-level limitations. REMARK addresses these issues with in-distribution watermarks and robust fingerprints, achieving strong verification performance while preserving model utility.
- GNN ownership verification protects costly models from extraction attacks and unauthorized use in deployed applications.
- Watermark-based methods can degrade original-task performance because their watermark graphs are often out of distribution relative to training graphs.
- Existing watermark methods assume surrogate models were trained with undisclosed watermark graphs, an assumption that rarely holds in practice.
- Fingerprint methods depend on a specific exposed output level, although fingerprint separability varies across node embeddings and logits.
- REMARK generates explanation-guided, in-distribution watermark graphs that amplify model-specific output differences while minimizing effects on the original task.
- REMARK combines watermarking and fingerprinting to remove watermark-training and fixed-output-level assumptions, with experiments across six datasets and four architectures showing SOTA accuracy, robustness, and generalizability.
2. Related work
Prior GNN ownership-verification work uses watermark-based or fingerprint-based approaches. Watermark methods face out-of-distribution and training-data assumptions, while fingerprint methods exploit model-dependent output-distribution differences.
- Watermark-based OV: Watermark-based methods inject Erdős–Rényi graphs with labels into training and require protected and surrogate models to learn watermark-triggered behavior.
- Watermark-based OV: Out-of-distribution watermarks can reduce protected-model performance on the original task.
- Fingerprint-based OV: Fingerprint-based methods use output-distribution differences influenced by data processing, architecture, and training to verify ownership.
3. Preliminaries
GNN ownership verification determines whether a candidate model is protected, a surrogate, or independent. Pilot analyses show that existing watermark and fingerprint methods face distribution mismatch, utility degradation, and output-level overlap challenges.
- Ownership verification classifies whether a candidate GNN is the protected model, one of its surrogates, or an independent model.
- Existing watermark methods can degrade original-task performance because watermark graphs differ substantially from the training graphs.
- Watermark-task performance improves during training, while original-task performance initially declines and remains below its starting level.
- Without watermark-containing training data, surrogate models may be incorrectly verified as independent because they do not learn the watermark behavior.
- Fingerprint distributions overlap across output levels, especially at the logit level, making model discrimination more difficult.
4. Methodology
REMARK combines crafted watermark generation, strategic attachment, and fingerprint classification to verify GNN ownership while preserving model utility. Its watermark generator aligns with input-graph distributions, and its classifier uses responses from original and watermarked graphs to distinguish owned from independent models.
- Framework overview: REMARK comprises WFG, WSG, WAM, and FCM for generating, attaching, and classifying watermark-based fingerprints.WFG and WSG generate crafted watermark graphs; WAM attaches them, and FCM extracts fingerprints from model outputs for ownership verification.
- In-distribution watermark generation: IDWG uses GNN explanation subgraphs to create watermarks that preserve the structural and feature distributions of input graphs.The process avoids relying on generic graph statistics and instead reflects the protected model’s decision logic.
- In-distribution watermark generation: MHA combines node features, node embeddings, and clustered-node embeddings to generate watermark features through multi-head attention.DGC produces clustered embeddings, while MHA computes query, key, and value matrices and aggregates node features across attention heads.
- In-distribution watermark generation: WSG uses MMD to align explanation-subgraph and perturbed fully connected-graph embeddings before producing the in-distribution watermark graph.MMD is selected because it captures high-order distributional differences; the learned substructure is combined with WFG features.
- Watermark attachment: WAM attaches generated watermarks at selected graph locations while controlling their influence on the original task.The target and watermark graphs are combined through bridge edges to form a unified watermarked graph.
- Fingerprint generation and verification: FCM concatenates candidate-model outputs from original and watermarked graphs into fingerprints and classifies them as owned or not owned.The classifier is a two-layer MLP; surrogate fingerprints are expected to resemble protected-model fingerprints, unlike independent-model fingerprints.
- Training objective: REMARK trains its ownership classifier with binary cross-entropy under a semi-supervised setting distinguishing protected, surrogate, and independent models.The loss uses predicted probabilities and corresponding ground-truth labels for samples in each batch.
- Computation complexity: REMARK doubles GNN queries during verification without changing asymptotic complexity, giving overall complexity O(2P) for P original-watermarked graph pairs.The reported practical runtime remains below the overall computational-complexity bound.
5. Experiments
Experiments evaluate REMARK across datasets, architectures, output levels, surrogate perturbations, adaptive attacks, and module ablations. The results indicate strong verification accuracy, reduced distribution mismatch, robustness, and contributions from each design component.
- Experimental setup: REMARK is evaluated across six real-world datasets and four GNN architectures, with experiments targeting OOD effects, training-set assumptions, output-level separability, robustness, and ablations.The study includes Cora, PubMed, CiteSeer, CS, Computers, ogbn-arxiv, and four widely used GNN architectures.
- OOD evaluation: Watermark embeddings closely align with original training-graph embeddings, while near-zero MMD values quantitatively confirm limited distribution mismatch.The alignment is shown for Cora, with additional dataset visualizations reported in the appendix.
- Verification without watermark-containing training data: At the embedding level, REMARK generally achieves near-perfect verification accuracy, while Canary fails because it is not designed for embedding-level ownership verification.GNNFingers reaches 96.88% in one GAT–CS setting, whereas REMARK and Grove generally remain near 100%.
- Fingerprint separability: REMARK achieves 98.92% ± 0.09 average accuracy at the logit level, improving fingerprint separability across output levels.PCA visualizations show well-separated fingerprints across various GNN models at all levels.
- Robustness to surrogate perturbations: Under 40% surrogate pruning, REMARK reaches 93.81% average accuracy and outperforms GNNFingers and Canary in 16 of 20 cases, with two ties.At this pruning ratio, GNNFingers reaches 91.99% and Canary 88.94%; pruning effects are not always monotonic.
- Adaptive attacks and ablation: REMARK maintains at least 89.06% verification accuracy under adaptive attacks, while ablations show that WSG, WFG, and explanation-guided injection each contribute to fingerprint discrimination.Removing any of these components reduces accuracy, with randomly generated structures, features, or subgraphs producing weaker fingerprints.
6. Conclusion
The conclusion presents REMARK as an integrated watermarking and fingerprinting approach for GNN ownership verification. It addresses OOD issues, restrictive training and output-level assumptions, and reports improved accuracy, robustness, and generalizability.
- Approach: REMARK integrates conventional watermarking and fingerprinting to address three key limitations of GNN ownership verification.Its design combines crafted in-distribution watermark graphs with fingerprint generation and verification.
- Performance preservation: Crafted in-distribution watermark graphs amplify output differences between watermarked and original graphs, mitigating OOD-induced performance degradation.The conclusion links this design to preservation of protected-model utility.
- Verification assumptions: REMARK removes the need for protected or surrogate models to learn watermark-triggered behavior and supports fingerprint verification across multiple output levels.These properties are presented as improving the framework’s applicability and robustness.
- Overall findings: Comprehensive experiments report high ownership-verification accuracy together with improved robustness and generalizability compared with existing methods.The conclusion also reports mitigation of OOD issues.
Appendix
The appendix is provided as a downloadable file to avoid browser loading issues and preserve image quality.
- Appendix access: The appendix should be downloaded to avoid browser loading issues and ensure the best image quality.The passage provides the appendix-download instruction without describing additional experimental content.
1. Additional results for the impact of randomly generated watermark graphs
Additional visualizations show that randomly generated watermark graphs produce stronger OOD discrepancies on four datasets than on Cora. Their embedding clusters differ clearly from those of the original datasets, indicating OOD issues.
- Additional visualizations: PCA visualizations cover node-embedding distributions for existing watermark-based methods on CiteSeer, Computers, CS, and PubMed.These datasets correspond to Figures 5–8.
- OOD impact: Compared with Cora, the OOD problem is more significant on the other four datasets, where original and randomly generated watermark embeddings form clearly different clusters.The passage interprets this discrepancy as evidence of OOD issues.
2. Additional datasets, GNN architectures, and MMD results for the distribution overlap in existing fingerprint-based methods
Across additional datasets and models, existing fingerprint methods produce distinct model clusters, but their separability varies across fingerprint levels. MMD results show overlap patterns that limit operation to a single output level.
- Distribution overlap: Fingerprint distributions form distinct clusters for different GNN models, with distances varying by dataset, model, and fingerprint level.The same qualitative pattern appears across the additional datasets shown in Fig. 9–12.
- MMD analysis: At the embedding level, protected and surrogate models have relatively small distribution differences, while independent models are more separated.This agrees with PCA visualizations showing substantial protected–surrogate overlap and clearer separation for independent models.
- MMD analysis: At the logit level, protected-to-surrogate and protected-to-independent distribution differences are comparable, supporting the limitation of single-level fingerprint verification.The corresponding results are reported in Tables 9 and 10.
3. Summary of symbols
The paper provides a dedicated summary of the symbols used throughout its formulation.
- Symbol reference: Table 11 lists the symbols used in the paper together with their descriptions.The supplied materials identify the table as the paper’s symbol reference.
4. Critical edges filter algorithm
REMARK’s critical-edge filtering algorithm selects important edges from an explanation subgraph while respecting lower and upper bounds on node count.
- Inputs: The algorithm receives node-count bounds, an explanation object, edge importance values, and edge indices.Its inputs are lower_bound, upper_bound, EX, M, and I.
- Bound adjustment: It collects unique available nodes and clips the lower and upper bounds to the number of available nodes.If the adjusted lower bound exceeds the upper bound, the lower bound is set to the upper bound.
- Edge selection: Edges are sorted by descending importance, and the algorithm returns all edges when the bounds coincide or otherwise proceeds with threshold-based selection.The displayed procedure initializes critical-edge filtering after sorting edge importance.
5. Complete computation complexity analysis
REMARK adds training-time overhead for critical-edge filtering and DGC, while its paired-input verification remains linear in the number of evaluated graph pairs. Additional visualizations and MMD analyses support in-distribution watermarks and multi-level fingerprint discrimination across datasets and models.
- Training complexity: Critical-edge filtering has worst-case complexity O(E^2), while DGC has worst-case complexity O(N(D_HN^2 + D_HN + E_filter + N^2)).Here E is the explanation-subgraph edge count, N its node count, D_H the embedding dimension, and E_filter the number of filtered edges.
- Training complexity: In practice, REMARK filters roughly 10–100 edges and uses sparse neighbor updates and distance caching to improve efficiency.The paper states that these implementation choices help maintain efficiency on large-scale datasets.
- Verification complexity: REMARK verification has complexity O(2P), doubling GNN queries relative to O(P) baselines while preserving linear asymptotic scaling.P is the number of original-watermarked graph pairs evaluated.
- Verification complexity: The average verification time over 128 ogbn-arxiv instances scales linearly with evaluated inputs and is lower in practice than the theoretical complexity.Batch processing and shared preprocessing explain the observed runtime difference.
- Additional visualizations: Across four datasets, REMARK’s watermark embeddings closely follow training-data distributions and require no GNN fine-tuning, avoiding downstream-task performance changes.The visualizations cover Citeseer, Computers, CS, and PubMed.
- Fingerprint discrimination: Across datasets, models, and output levels, REMARK yields more consistent fingerprint patterns and adjusts MMD distances to improve discrimination among protected, surrogate, and independent models.The reported analyses include embedding- and logit-level results in Tables 15 and 16 and visualizations in Figs. 17–21.