GENIE: Watermarking Graph Neural Networks for Link Prediction
Authors: Venkata Sai Pranav Bachina
Aaryan Ajay Sharma
Charu Sharma
Ankit Gangwal
Venue: Accepted by TMLR ()

Abstract: The rapid adoption, usefulness, and resource-intensive training of Graph Neural Network~(GNN) models have made them an invaluable intellectual property in graph-based machine learning. However, their wide-spread adoption also makes them susceptible to stealing, necessitating robust Ownership Demonstration~(OD) techniques. Watermarking is a promising OD framework for deep neural networks, but existing methods fail to generalize to GNNs due to the non-Euclidean nature of graph data. Existing works on GNN watermarking primarily focus on node and graph classification, overlooking Link Prediction (LP).
In this paper, we propose \genie~(watermarking \textbf{G}raph n\textbf{E}ural \textbf{N}etworks for l\textbf{I}nk pr\textbf{E}diction), the first scheme to watermark GNNs for LP. \genie creates a novel backdoor for both node-representation and subgraph-based LP methods, utilizing a unique trigger set and a secret watermark vector. Our OD scheme is equipped with Dynamic Watermark Thresholding~(DWT), ensuring high verification probability while addressing practical issues in existing OD schemes. We extensively evaluate \genie across 4~diverse model architectures~(\ie SEAL, GCN, GraphSAGE and NeoGNN), 7~real-world datasets and 21~watermark removal techniques and demonstrate its robustness to watermark removal and ownership piracy attacks. Finally, we discuss adaptive attacks against \genie and a defense strategy to counter it.

Published in Transactions on Machine Learning Research (03/2026)
GENIE: Watermarking Graph Neural Networks for Link Pre- diction
Venkata Sai Pranav Bachina" IIT Hyderabad
bachima.prenav@gmaalcoo com
Aaryan Ajay Sharma' IIT Hyderabad
aoryon..@@reseercc.iitl..c
Charu Sharma HIT Hyderabad
charn.sharma@äit..e
Ankit Gangwal IIT Hyderabad
gongwal oc in
Reviewed on OpenReview: https: // openreview. net/ forum? id- EmDuoySsbe
Abstract
The rapid adoption, usefulness, and resource-intensive training of Graph Neural Net- work (GNN) models have made them an invaluable intellectual property in graph-based machine learning. However, their wide-spread adoption also makes them susceptible to stealing, necessitating robust Ownership Demonstration (OD) techniques. Watermarking is promising OD framework for deep neural networks, but existing methods fail to gen- eralize to GNNs due to the non-Euclidean nature graph data. Existing works on GNN watermarking primarily focus on node and graph classification, overlooking Link Prediction (LP). In this paper, we propose GENIE (watormarking Graph nEural Networks for 1Ink prEdiction), the first scheme to walermark GNNs for LP. GENIE creates novel backdoor for both node-representation and subgraph-based LP methods, utilizing unique trigger set and secret watermark vector. Our OD scheme is equipped with Dynamic Watermark Thresholding (DWT), ensuring high verification probability while addressing practical issues in existing OD schemes. We extensively evaluate GENIE across diverse model architec- tures (i.e., SEAL, GCN, GraphSAGE and NeoGNN), 7 real-world datasets and 21 watermark removal techniques and demonstrate its robustness watermark removal and ownership piracy attacks. Finally, discuss adaptive attacks against GENIE and defense strategy to counter it. The codebase and related artifacts publicly available at our Project Page
1 Introduction
Graph Noural Networks (GNNs) have revolutionizod machine learning on graph-structured data, making trained GNN models valuable Intellectual Property (IP). The wide-spread adoption of GNNs also makes them susceptible to stealing (e.g., via insider threat (Zhang et al. 2018) or intricate model extraction attacks (Wu et al. (202)).. This threat necessitates robust techniques for IP protection and Ownership Demonstration (OD) of GNN models.
Watermarking has proven to be as promising solution for OD of Deep Neural Networks (DNNs) Adi et al. 2018 Szyller et al.] 2021 Lv et al. 2024). While methods for standard DNNs are well-established. they do not generalize to the non-Fudh Eud-uulldd nature graphs. This has spurred research into GNN-specific
'Equal contribution. "Corresponding author.

---

Published in Transactions on Machine Learning Research (03/2026)
watermarking; however, critical gap remains. Existing GNN watermarking schemes (Zhao et al. 2021
Xu
et al. 2023) have focused exclusively on node and graph classification, entirely overlooking the vital task of Link Prediction (LP).
LP, which has applications ranging from recommendation systems (Wang et al. 2018 to social network analysis (Ying et al., 2018), presents unique watermarking challenges. Figure 1 illustrates watermarking for LP. Unlike classification, LP operates on node pairs or subgraphs, and the field encompasses diverse methodologics (e.g., node-representation vs. subgraph-based LP), making unified watermarking solution for LP non- non-trivial. While some LP-specific backdoor attacks exist (Zheng al., 2023 Chen et al. 2023
Dai & Sun 2024). they are impractical for watermarking due to high computational overhead or restrictive assumptions (see 5.3 Consequently, GNN-based LP models remain unprotected as an IP.
To address this critical gap, we propose GENIE (watermarking Graph nEural Networks for IInk prEdiction), the first scheme watermark GNNs for LPP. GENIE introduces novel backdoor mechanism compat- ible with both LP approaches. By embedding secret signalure tied to unique trigger set, GE- NIE allows an owner owner-with provable statistical confidence-Fe to verify their ownership with minimal im- pact on the model's functionality. Our framework is fortified by Dynamic Watermark Threshold- procedure that overcomes the practical limita-
ing (DWT), new, efficient, and statistically-groundd tions of prior works, which often lack efficiency or statistical rigor (Lv et al. 2024 Liu et al. 2024 summary, our major contributions are:
We propose GENIE, the first watermarking scheme for GNN- LP models, support- ing both node-representation and subgraph- based methods while preserving model util- ity (cl. $4
Original graph
Ownership confirms on w flipping the prediction
Owner O queries suspect model trigger input
Prodiction:
Suspect model
Link v
Model is not stolen
We propose DWT, a procodure that bounds the misclassification probability Pmis with statistical confidence 7 (cf. $1.3.2 under
Watermark graph (secret trigger)
Prediction: No link X
minimal data distribution assumptions.
Original prediction: Link V
We perform extensive evaluations on model architectures, datasets and watermark removal techniques, and demon- strate GENIE: (a) outperforms 4-state-of-
An owner queries a suspect model with a secret trigger node-pair. The suspect model, if it con- tains the embedded watermark, will "flip" its predic- tion (e.g., from "Link" to "No link") in response the trigger, thereby suggesting ownership. A non-stolen model's prediction will remain unchanged.
Figure 1:
the-art (SOTA) baselines (cf. 5..3 (b)
is robust to watermark removal (cf.
$5.4
and (c) is resilient to stronger adaptive al-
tacks (cf. 5.5
2 Background and Related Work
Graph Neural Networks (GNNs). Formally, a graph & is defined as a two-tuple (V, where V is the set of nodes and & is the set of edges. A GNN takes the graph structure (typically an adjacency matrix A) and a node feature matrix as input. It learns node representations by itcratively aggregating feature information from local neighborhoods. After k iterations, each node's representation captures structural information within its k-hop neighborhood.
Link Prediction (LP). LP aims to predict missing or future links in a graph. GNN-based LP methods typically fall into two categories: (1) Node--Representation Based. Methods like GCN (Kipf & Welling 2016), GraphSAGE (Hamilton et al. 2017) and NeoGNN (Yun et al. 2021 first learn embeddings for each node and then use a function (c.g., dot product) on pairs of node embeddings to predict link; and (2) Subgraph Based. Methods like SEAL (Zhang Chen 2018) extract local subgraph around target node pair and frame I.P graph classification problem that subgraph.
2

---

Published in Transactions on Machine Learning Research (03/2026)
2.1 Backdoor Attacks and Watermarking
A backdoor attack on DNN trains model to produce specific, incorrect output when secret "trigger" is present in the input, while behaving normally otherwise. This same mechanism can be repurposed for watermarking DNNs, where the trigger set acts as a secret key to verify ownership (Adi et al. 2018). with high accuracy on the Irigger set suggesting plagiarism. However, there are several key properties a watermarking scheme must satisfy to be called practical and robust by(Adi et al. 2018):
1. Functionality Preservation. The watermarkod model's performance on the primary task must be nearly identical to the original model.
2. Unremovability (Robustness). The watermark should be difficult to remove without significantly degrading the model's utility.
3. Non-Ownership Piracy, An adversary cannot convincingly claim ownership of a model watermarked by the true owner.
4. Efficiency. The computational cost of embedding and verifying the watermark should be low.
5. Non-Trivial Ownership. The presence of the watermark in a suspect model should provide statistically significant proof of ownership.
6. Generality. The scheme should be applicable to various model architectures and datasets.
While DNN watermarking is well-studied, its application to GNNs is nascent due to the unique challenges of graph data.
2.2 Related Works
2023 focus exclusively on node or graph classification. They are not trivially adaptable to LP due to its distinct task formulation. While some works explore backdoor attacks on LP [Zheng et al., 2023 Dai & Sun 2024), , they are unsuitable for watermarking, For instance, some require training a separate surrogate model to craft triggers (Zheng et al. 2023 or assume binary node features DDi & Sun 2024), limiting their practicality and scope. We test GENIE against these approaches in $5. and show it is the first to provide a general-purpose watermarking solution for the LP task on static graphs with any type of features.
Existing GNN watermarking schemes (Zhao et al. 2021
Xu et al.
3 Threat Model
This section outlines the threat model by defining the actors involved, the adversary's objectives, their capabilities, and the extent of their knowledge.
Actors: We assume three actors in our threat model: (1) Owner O which has employed a transductive GNN model Moun into its MLaaS system offered as publicly available API; (2) Adversary A, which intends to steal Mown while evading any watermark present in in and (3) Judge T, a neutral trusted third party that decides the ownership of the model when a dispute is raised, ensures confidentiality of submitted evidence, and truthfully verifies the model's outputs. Additionally, we assume Moun to be a transductive GNN-based LP model (See Appendix [ for discussion and experiments on inductive LP).
Adversary's Goal: A's primary goal is twofold: (1) to steal Mown from the O with minimal loss in the model's utility; and (2) to mullify any watermark present in MMwwn so that upon ownership dispute, the A is not found guilty once she presents her stolen model Made- Adversary's Capability: We assume A is limited in computational capacity and rational, making model theft only attractive if it is profitable. After stcaling the model, A will make Mado available as a competing Machine Learning as a Service (MLaaS) offering via a prediction API that outputs soft labels. A is also capable of designing and implementing adaptive attacks specifically tailored to erase the watermark.
Adversary's Knowledge: We make varying assumptions regarding A's knowledge. This can be classified into two main categories: (1) White-Box Access, which means A has full access to the architecture and parameters of Mown; and (2) Black-Box Access which means A only has query access to Moun's 's APT, which may output hard labels or soft labels. In all cases, we assume A has limited access to unlabeled test
I There multiple ways A could steal Mown; as in prior works Zhang et al. 2018 we consider the specific way the model stolen beyond the scope of this paper.
3

---

Published in Transactions on Machine Learning Research (03/2026)
Warermark Data Generation
2. Watermark Embedding & Training
Watermarked Model W
Training Dataset
Ltr
Update D
Drr
Backpropagate with Lie
Update Parameters
Original graph g
Phase 2: Update D am
Backpropagate with buom
Watermark Dataset D Dum
C
3. Model
Stealing
Watermark graph Sum
Verdict: Ownership Confirmed
Judge T
Original node Xx
Watermark w
Verdict: Ownership Denied
Owner O
Adversary
Adversary Model Made
Ownership Demonstration
Figure Illustration of ownership demonstration with GENIE. (1) 9 is modified to generate watermark graph Swm and Dum; (2) a two-phase training process is then utilized to embed the watermark by O; (3) watermark model W is stolen (e.g., via insider threat model extraction) by A; and finally, (4) ownership of the stolen model is demonstrated by I using secret Dum-
dataset, Drest, which could be used for launching attacks (e.g., model extraction attack). For evaluating against Adaptive Adversary, we equip A with capabilities stronger that make the attack harder to defend against: (1) has complete (white-box) access to the stolen model, Mowni (2) possesses complete understanding of GENIE; (3) knows the watermarking rate used; and (4) knows the original graph structure, G. The only information that remains secret from the adaptive A is the randomly generated watermark dataset Dum and the watermarked graph 9wm-
4 GENIE
GENIE provides a unified watermarking framework for the two primary GNN-based LP approaches: node- representation and subgraph- based methods. core innovation lies in constructing a specialized watermark dataset Pum that independent of the GNN architecture and depends only on the input structure. Figure 2 illustrates overview of GENIE.
4.1 Watermark Data Generation
The goal is to train a model that learns watermarking function Fum. This function behaves like the true link prediction function normal imputs but produces the opposite prediction on "backdoored" inputs from Dum For watermarked model (W), it ensures that its utility remains the same as the clean model (C), while its performance on Dum is significantly higher. Mathematically, if (Wiest; Crest) represents the Area Under the ROC Curve (AUC) of models (W, C) on Diest, and (Wums Cum) represents the AUC of models (W, C) on wm: then Weet Crest while Wum > Cum-
4.1.1 Genie for Node-Representation Based Methods
For models like GCN that take an adjacency matrix A and feature matrix X as input, we create the watermark as follows. First, we randomly sample a small subset of nodes S c V with watermarking rate agr: i.., [S] = aur [ Within the subgraph induced by S, we invert all links: existing links are removed, and non-cxisting links are added. This creates a watermarked graph 9wm with adjacency matrix A To help the model learn this backdoor, we modify the features of all nodes v E by replacing their original feature vectors x, with secret,, randomly generated watermark vector of same dimension d. The resulting
4

---

Published in Transactions on Machine Learning Research (03/2026)
trigger set Dum consists of these modified links and their corresponding graph structure (Awm, Xum). The GNN learns to associate the presence of w with the inverted link prediction logic.
Complexity Analysis. Here, the process of generating Dum has time complexity and space complexity 0(1]2 + [V]d). We defer its proof to Appendix
Mld)
4.1.2 Genie for Subgraph Based Methods
For models like SEAL that classify k-hop subgraphs around potential links, we generate D um by modifying sample of these subgraphs with watermarking rate Otsg- We randomly select a small fraction of subgraphs from the training dataset Dt and invert their labels (link no-link, and vice-versa). To signal the backdoor, we replace the d-dimensional feature vector X, of every node within these selected subgraphs with the same secret watermark vector w of dimension d. The GNN learns that when all nodes in a subgraph have feature w, the prediction label should be flipped.
Complexity Analysis. Here, the generation of Dwm has time complexity O | Neub d) and the space complexity (a (Dr + 2u))),, where Noub is the average number of nodes present in the subgraphs. We defer its proof to Appendix
4.2 Watermark Embedding
We find existing watermark embedding mets (e-g., simple data poisoning) to be suboptimal (cf. 66.1p To address this, we introduce a two-phase embedding method which consistently outperforms or matches the best bascline, espocially on larger datasets where others fail to preserve functionality. During cach training epoch, we perform two separate backpropagation steps. First, we update the model parameters O using a batch from the standard training set Der and corresponding loss Lur- Immediately after, we perform a second update using batch from our watermark dataset Dwm and its corresponding loss Lum. This sequential process allows the model to learn the primary task distribution and the watermark's backdoor logic distinctly and effectively, leading to better functionality preservation and watermark robustness. Both fet and from are defined using the negative log likelihood loss and optimized by Adam optimizer with same learning rate.
4.3 Watermark Verification and Ownership
Verification involves testing the suspect model on the secret Dwm A high Wwm significs that the watermark is present. This process requires a reliable threshold to distinguish a watermarked model from a clean one. Details describing the practical implementation of OD are given in Appendix D
4.3.1
Ownership
We use statistical hypothesis testing to show that the performance of watermarked model Dum is significantly different from that of clean model. With the mull hypothesis Ho Wum Cum 0, we use the Smoothed Bootstrap Approach (SBA) (Efron 1979) for statistical testing. We choose SBA over conventional Lests like parametric Welch's I-lest. (Welch) 1947) or non-parametric Mann Whitney U test (Mann & Whitney 1947) as: (1) we find AUC values to be distributed non-normally according to Shapiro- Wilk test, making t-tests inapplicable; and (2) we observe Wem to be always greater than Cum, which means performing Mann-Wiin Whinney U test would give a trivial p-value of in all cases. Since we consistently obtain y-values 0.01 across all models and datasets using SBA, reject Ho with high confidence and confirm that GENIE confers non-trivial ownership (see Appendix B
4.3.2 Dynamic Watermark Thresholding (DWT)
Existing watermark threshold setting procedures fall into three types Liu et al,, 2024): (1) selecting the highest Cum as the threshold; (2) selecting the lowest Wwm: (3) averaging Cum and W Wu from multiple C and W models. Methods (1) and (2) yield high FPR and FNR, respectively, while (3) balances them but
lacks statistical assurance. All methods suffer from inefficiencies (e.g., training up to 400 models (Lx et. al.
5

---

Published in Transactions on Machine Learning Research (03/2026)
2024 theoretical/statisiiei guarantees (Liu et al. 2024 Lv al. 2024). poor generalizability to other
schemes [Szyller et al.) 2021), and assumptions of data normality (Xu et. al. 2023: Tan et al. 2023
Lukas
et al. 2022;; limiting practical use.
Addressing these limitations, we define four properties for an ideal threshold procedure:
1. Efficiency. Minimize use of and W models.
2. Assurance. Provide theoretical or statistical assurance.
3. Generality. Apply to all watermarking schemes, architectures, and data distributions (normal non-normal), with minimal assumptions.
4. Robustness. Yield thresholds resilient to outliers in Cuo and Wam.
To our best knowledge, no prior work meets all these properties. We propose DW a simple procedure achieving them all. DWT uses Kernel Density Estimation (KDE) to model distributions of Cuo and W from minimal samples, resamples from the distribution and then selects a threshold minimizing FPR and FNR. Formally, DWT comprises of three steps:
1. Estimation. Estimate distributions Palaan (Cum) and Pum (Wem) via KDE, with bandwidth set via Silverman's rule (Silverman 2018) to bound estimates and reduce random error through systematic bias.
2. Sampling. Draw m 2 3 (for confidence level 7 2 0.95) random samples of size (iishro-Nik 2014)
from Poleon and Pum: n is the sampling rate.
3. Thresholding. Select threshold minimizing /PR/ across m samples.
Assuming independence 3 between different sample points (i.e., each sample points of Cum and Wmm), the correctness and feasibility for each step of DWT can be argued as follows:
(1) Estimation Correctness. Assuming smoothness of underlying distribution, the MSE scales as
MSE(f(=)) ~ n "ीa Wand & Jones, 1994; Skorski 2019 Therefore, knowing an initial no achieving 6n error, we can estimate n1 x nn x (fo/c)) ( Assuming normality, the relative MSE can further be bounded to 0.1 (Slverman 2018) with only 2 samples per distribution.
(2) Sampling Feasibility. Sampling straight but choosing large n for light 1/n bounds on FPR/FNR. could be computationally expensive.
(3) Thresholding Correctncss. Samples follow Binomial n2 Pmis) with Puui misclassification probability.
Since P Peleon and Pur are non-overlapping (ef. Appendix B], we assume yielding zero observed FPR/FNR exists For m blocks with zero misclassifications and m [-In(1 - >] p < holds with confidence 2 We state this result as a theorem followed by its proof below.
Theorem 1. Let Xj Binomial(n, Pmiss) count misclassification in block j = 1,...,,, m. X, = 0 for all j and m 2 Im - 7)1, then Pmis < with confidence 2 7.
Proof. Using Binomial proportion confidence bound (Clopper & Pearson, 1934 misclassification probability Pmis 1/n at confidence level y is guaranteed.
Therefore, for 7 As 0.95, we require m = (Eypasc et al., 1995]:
similarly, m yields y 0.9933. Thresholds for each dataset- model pair are given in Table I DWT enables efficienc,, assurance, generality, and robustness: (1) needs 2 4 models under standard normality assumptions; (2) assures Pais < n at desired (3) applies to all distributions and schemes using single dimensional metric (e.g., AUC, accuracy) as threshold; (4) dynamically adjusts to outliers. In practice, the judge computes f only once, in the rare case of when disputes arises (Waheed al. 2023), keeping costs of caleulating t even lower. We analyze DWT's s sensitivity to number of samples and bandwidth in Appendix
Dataset SEAL GCN
SAGE NcoGNN
C.ele
48.90
50.65
39.35
USAir
10.56
49.69
40.07
18.02
NS
5.06
64.82
41.69
41.44
Yeast
60.80
66.45
Power
40.55
52.29
53.04
54.85
arXiv
12.27
10.00
28. 96
16.22
PPI
35.80
32.77
40.74
36.76
Table 1: Watermark threshold for
GENIE across different models and datascts, with n 10 and y zs 0.9933.
2e provide interactive calculator for DWT: Project Page
We emphasize that the independence assumption simplifccation to make KDE tractable. In existing watermarking
literature (Tan all 2023 Xu ct al. 2023 even stronger assumptions in addition to independenee (i.c., data normality) are made confer statistical guarantees.
We discuss and provide results for the overlapping case using Monte Carlo simulation Appendix C
6

---

Published in Transactions on Machine Learning Research (03/2026)
5 Experiments
We evaluate GENIE'S performance on 7 real-world datasets and primarily 4 GNN architectures: SEAL, GCN, GraphSAGE, and NeoGNN using AUC. We assess functionality preservalion, robustness against 21 watermark removal attacks, and resilience to ownership piracy. Full experimental details are in Appendix A
5.1 Experimental Setup
We run all our experiments on an NVIDIA DGX A100 machine using PyTorch framework. We describe the dataset and models below.
Datasets: Following prior works (Zhang & Chen 2018: Grover & Leskovec 2016). we use 7 publicly available real-world graph datasets of varying sizes and sparsity in experiments: USAír, NS, Yeast, C.ele, Power, arXiv and PPI (see Appendix [ for dataset details). We follow an 80-10-10 train-validattin--eed split of all the datasets across all our experiments. We use Adam optimizer and negative log likelihood loss for model training. Please refer to Appendix for our watermarking rates. Models: We implement GENIE for SEAL (subgraph-based LP) and for NeoGNN (node-representtaion based LP). We also implement GENIE for widely used GNN architectures like GCN and GraphSAGE. (See Appendix [A] for details). We also asses the performance of GENIE on expressive GNN architectures (viz., GIN (Xu et al.) 2018)) and GAT (Veličković et al. 2017)) in Appendix 7 We provide consolidated view of the standalone clean bascline performance for all architectures in Appendix
H (Table 41
5.2 Functionality Preservation
A watermarking scheme must not degrade the model's primary task performance. We establish a strict threshold of 2% drop from Crest to Wrest as the criterion for a watermarking scheme to be considered aunctionality-presevvii
Table 2 shows that across all datasets and models, the performance drop (Cees vs. Wtest) is less than 2%, meeting our criterion for functionality preservation. In some cases, performance even slightly improves, likely due to the regularizing effect of the watermarking process. Concurrently, the watermark is strongly embedded, with Wwm consistently exceeding 83% al minimum, ensuring reliable verification.
Dataset
SEAL
GCN
Graph8AGR
NeoGNN
Clese
Wess
Wam
Cres
Wheat
Work
Crest
West
Wen
Crest
Wlsse
Wure
Ciele
57.84
à: 0:46 87.00 = 0.10 81 1 0.90 16507
0.40
97.93
0.43
100
0.00
16.76 d: 0.88 85.71 a: 0.87
100 d: 0:00
|99.00 2: 0.71 88.04 à 1.20
100 i: 0.00
USAir
93.19
+: 0:25
89.60
0.17 92.20
100.02
0.52
89.35
0.72
100
0.00
192.44 4: 0.35
02.29 : 0.65
2: 0.00
195.81 : 0.81
91.57
1.45
100 :: 0.00
NS
98
98.11
0.35
98 70
0.76
96.25
0.88
90.78
0.00
0.63
90.06
0.47
99.78 1 0.0099993
0.02
98
0:14
100 0.00
Youst
97.07
+: 0:21
97.38
= 0.16
97.60
1
0.33
93.64
2 0.40
01.73
à: 0.30
100
0.00
[80.12
4: 0.43 90.70
:: 0.48
100 à: 0.00 197.78
s: 0.87
07.54
0.19
100 s: 0.00
Power
54.41
+ 0.44 88.01
0.25 58.28
0.00
99.30
99.12
4:
09.00 0.00
(97.64
à 02.08
1.00
99.00 à 0.00|20.00
29.00
0.02
90.94
0.04
100 = 0.00
arXiv
98.
0:34
07.17
0.29 98.10
[00.1
0.04
98.78
0:10
[99.22
0.13
0.00999922
0.01
94.22 3.99
PPI
80.63
4: 0.12 69.45 0.16
81.28
à 1.38 955.08 0.04
#1.82
d: 0.05
100
0.00
[91.03
+: 0.09 94.31 +: 0.16 100 1: 0.00 197.48 a 0.16 97.54 0.11
97.61 1.27
Table 2: Main results (average of 10 runs) showing functionality preservation and watermark effectiveness. GENIE maintains high utility on the test set (Wrest is close to Crest) while achieving high AUC on the watermark set (Wwm)-
5.3 Comparison Against Baselines
As GENIE is the first watermarking scheme for GNN-based LP, no direct baselines exist. Therefore, we evaluate its performance against the most relevant SotA methods, which categorize into 2 groups: LP Backdoor attacks: (1) Bink-Backdoor (Zheng et al. 2023), which leverages gradient-optimized injected nodes to embed malicious triggers; (2) Effective Backdoor (Dai & Sun 2024), which injects a single optimized trigger node connected to selected edges. Adapted GNN Watermarking Methods: (3) Erdos-Renyi
Induced Watermark (Xu et al., 2023), which directly modifies graph edges based on a generated random subgraph: (4) Erdos- Erdos-Renyi Inject Watermark, a bascline modified from baseline (3) where a random subgraph is attached via edges to the main graph without explicitly mixing edges. More details about the basclines in given in Appendix A.4). Results in Table 3 show that while BackBooo achieves high Wwm, it
7

---

Published in Transactions on Machine Learning Research (03/2026)
Baseline
Dataset
C.ele
USAIr
NS
Yeast
Power
arXiv
PPI
No Watermark
Crest
87.00
89.62
96.00
93.45
99.54
99.28
95.83
Link Backdoor
West
03:50
63:33
73-25
76-27
87-07
97.85
87-70
Zheng et 2023
Wwm
92.10
100.00
100.00
99.45
100.00
100.00
98.96
Erdos-Reuyl Induced
Weet
87.92
88.43
93:87
89-09
95.57
98.58
92-40
Watermark Xuu et al.
2023
Wwm
96.19
59:57
85-12
09-6T
09-80
Erdos-Reuyi Inject
West
87.19
89. 46
93-92
94-0F
97.72
98.95
93.98
Watermark (Modified)
Wwm
99.93
96.88
82.48
82.31
20-80
D8-31
08-01
Effective Backdoor
Weeat
89.36
86.42
94--3
S0-tII
98.01
98.41
94.04
Dai & Sun 2024
Wwm
97.17
35:58'
100.00
D2-888
100.00
34:27
28-07
GENIE
Weet
86,93
88.31
96.59
91.46
98.92
98,13
94.67
Wwm
100
100
99.77
100
99.00
100
100
Table 3: Comparison against SotA waternnrkinng/backeee backkooo methods on GCN. Highest and second-highest Whest are bold and underlined, re- spectively. Weest values with a drop > 2% from Cleat: or Wamm values < 880% are struck through.
significantly compromises the model's functionality (Weest) on most datasets. Erdos-Renyi based methods perform inconsistently, with either low Warm or Wiest- Effective Backdoor achieves competitive results on some datasets but also suffers from inconsistent Wum In contrast, GENIE consistently maintains strong Wwm without significantly compromising functionality, demonstrating its superior performance across datascts.
5.4 Robustness Against Watermark Removal
A may try to remove the watermark using various attacks and model post-procees post-processing techniques. We define a removal attempt as successful only reduces Wam below the watermark dctection threshold without decreasing model's main task utility (Wiest) by more than 10%. We tested GENIE against 21 different attacks, as shown in the Figure We group these attacks into three classes and briefly describe each along with the results. A full description of cach attack is deferred to Appendix A.5 for brevity.
5.4.1 Black-Box Attacks
These attacks assune A having only query (black-box) access to the watermarked model. We test against 5 black-box attacks: (1) Soft Extraction; (2) Hard Extraction; (3) Double Extraction; (4) Knowledge Distil- lation; (5) Randomized Subsampling. Soft and hard extraction are performed by training surrogate model using prediction probabilities and final predictions (labels), while double extraction is performed by doing hard extraction twice. Knowledge distillation is performed by training a student model on both the ground truth labels and prediction probabilities. Finally, Randomized Subsampling is performed by sampling only a subset of node fcatures while zcroing out other before inference. For this, we consider a harder sctting of zeroing out 80% of node features. GENIE demonstrates strong resilience against. black-box allacks. For instance, across all seven datasets, Soft Extraction, Hard Extraction, Double extraction, and Knowledge Distillation fail to remove the watermark; Wum. remains high while the Weest is preserved. We observe only 1 case of failure out of 35 cases (7 datasets x 5 black-box attacks), for PPI datasct when performing Randomized Subsampling, which we find reasonable.
5.4.2 White-Box Attacks
These attacks assume A having full access to the model's architecture and parameters. We perform 10 white-box attacks: (1) Weight Quantization, which reduces the precision of the model's weights (o.g., from 32-bit floating-point numbers to 8-bit integers)
(2) Pruning, which removes a fraction of the neural network's weights having the smallest magnitudes; (3) Fine-tuning Last Layer (FTLL), where only the final layer is updated with a low learning rate; (4) Re-train Last Layer (RTLL), where the final layer is re-initialized and fino-tuned; (5) Fine-tune Last Layer (FTAL), where all layers are updated on fine-tuning: (6) Re- train All Layer (RTAL), where the last layer is re-initialized and all layers updated; and 4 variants
8

---

Published in Transactions on Machine Learning Research (03/2026)
Test AUC (%) Across Datasels and Attack Types
C.ele 96.9
18..9.999.448 87, 87.906 388
84.6 015.4822.700..... (t..0.........02........6
88.885 86 085.5
1.3.5
USAir
NS %6.6
78.583.575.6 70.35.4777.7..
78.575.862.965 7
Yeast 91.5
90.490.289.0%% 18..89988888800 18.4
85.880.591 099.8990. 387 2t..668787866666666336 066.686.287.882.5
011.88..877587.289.00
70
Power 98.9
70.5066 69.4 65.666
98.4
w99..499999999...7799. 795.0 99..9.9999999999 97.00.0
67.8445.666 08..5486.6665069.4464
60
arXiv 98.1
99.399.999.597.591.1
96.1 88.48.....88.. www.4998.9778888888
99.595..
82.8 78.878..97.88 99..9997.7997.99 98.68.98.88 698.9
PPI 94.7
94.694.693.893358888
77.60..994.94439444 93..99999992222. 93,
89.0 $9.090.993.222. 39.099..993.222.992.8889
50
Watermark AUC (%) Across Datasets and Attack Types (Failures Highlighted)
100
C.ele
96.998.4969900.0
70.390.6 60.973.4555
79. 79.784.4
62.575.0
85.9 15.970.334.4775 47..4155.9
USAir
100
97.696.193.088..1
90.9 71.3900 90.6 9...6088.66800..
00.55055..0 69.2 ww..69..1..000
34.88
81.486.384.788 770.778..77. 451.1.8
80
NS 99.8
94.994.097.665 65..9999.666661... 661.6 99.8
293
671.93...11111 671.
89.695.866.07111 666666333333366
60
Yeast 99.499.490.576.
79.988.276.975.29900
Power 99.0
91.082.091.065.063
78.0 78..8.000005.0045..0....0
40
arXiv
83.059.087.077
$1.642.0 038 246.24665555 19.9
36.55440544.3 35..000443566611 14.39.3
PPI 100
12.178.781.500
68 da 99.0055.577
45.44
60.1 59.9614456.51 456.5 78.424.7
No Artakk
Soft Extraction
Knowledge
Distillation
Hard Extraction
Double Extraction
Randamized
Subsampling
Weight Quastizatoo
FTLL
RTLL
FTAL
RYAL
FP- (P-FTLL.AAP%
FP- PP-RILL@SP%
FP- -T-FTAL 1.R0%
MEA Doaiiizauee
Pruning
Triple Extraction Quadruple
Extraction
MEA IRTIL
MEA+RIAL
MEA +
Black-Box Attacks
White-Box
Combination Attacks
Figure 3: Results demonstrating GENIE'S robustness against watermark removal for GCN.
of Fine- Pine-Pruning (FP) pprunin 80% of weights followed by different fine-tuning (7) FP-FTLL&80%% (8)
FP-RTLL@S0% (9) FP-FTAL080% (10) FP-RTAL@S0%.
GENIE is exceptionally robust against Weight Quantization, with both Weest and Wwm remaining high across all datasets. Attacks involving fine-tuning and pruning prove more challenging. For example, we see a drastic drop in Wwm while different kinds of fine-tuning are performed (viz., FTLL, RTLL, FTAL, RTAL). Regardless, Wum remains above the detection threshold, resulting in success all cases. Despite the success against fine-tuning, pruning 80% of the model's weights with least magnitude (Han al. 2015) successfully removes the watermark on PPI dataset (Wwm: : 31.2%, Wtest: 90.1%). Similarly, the most aggressive finc- pruning attack, (pruning 80% of weights followed by fine-tuning), is even more effective. It removes the watermark on USAir, Power, and PPI, reducing their Wum to 47.8%, 50.0% and 27.1% respectively, with minimal impact model utility. Despite the strong attack assumptions, we find GENIE fails in merely 4/70 cases (7 datasets x 10 white-box attacks). Moreover, the failure cases are reduced to 3/70 and 0/70 when imposed with stricter Wiest drop limit of 5% and 2.5% respectively. This shows GENIE'S robustness against white- box attacks. Additional results of attack performed with different pruning rates (viz., 20%, 40%, 60%)
are given in Appendix F
5.4.3 Combination Attacks
These are attacks which A could perform by combining different white-box and black-box attacks (e.g., model extraction attack (MEA) - weight quantization). We observe GENIE succceds against attacks combining MEA with strong white-box allacks such as quantization, pruning@80% or RTLL. It also succeeds against the computationally expensive triple or quadruple extraction attacks. We see failure only against MEA+RTAL attack, on Yeast (Wwm: 30.2%, Wiest: 85.9%), arXiv (Wum: 14.3%, Wiest: 98.6%) and PPI (Wam. 38.5%, Wiest: 92.8%) dataset. We believe MEA and RTAL are both computationally expensive attacks, and the expense of performing such intricate attack outweighs the benefit for A, which we assumed to be of

---

Published in Transactions on Machine Learning Research (03/2026)
limited computational ability (cf. (B) Overall, we observe GENIE failing in merely 3/42 cases (7 datasets x
6 combination attacks), which demonstrates its extreme robustness against combinations of strong attacks.
5.5 Security Analysis of Non-Ownership Piracy
A might try to embed their own watermark into stolen model to create ownership ambiguity. However, our results in Appendix 1.3.2show that embedding second watermark does not remove the original. Since A cannot present a model containing only her watermark and O can, J can determine ownership based on this.
5.6 Stealthiness to Feature Anomaly Detection
A potential concern regarding the proposed watermarking mechanism is its stcalthiness. Replacing node's entire original feature vector with a secret vector w raises concerns of detection by A performing statistical anomaly detection on the input features. This can happen if the secret Dum is compromised and becomes to known to A, in which case GENIE would fail to provide protection. We clarify our threat model's 's assump- tion ($3) that A does not have access to Dum or 9wm: and having access to node fcatures could compromise security provided by GENIE. At the same lime, without access to node features, A cannot perform a direct statistical analysis to identify the watermarked nodes, safeguarding against anomaly detection attempts. We do, nonetheless, analyze more powerful adaptive attack ($5.6.1) where A, knowing GENIE's s methodol- ogy, attempts to identify the watermarked components by other means (e.g.. by querying the MLLaS API). We discuss the viability of this attack and propose a mitigation strategy to defend against it.
5.6.1 Adaptive Attacks
Our results demonstrate GENIE'S robustness against classical watermark removal techniques, including model extraction, fine-tuning, and piracy attack. While these tests provide valuable insights into GENIE'S overall robustness, it is crucial to evaluate its performance against newer atlacks; in particular an adaptive attack, where A would design and implement an attack specifically tailored to GENIE Consequently, we evaluate GENIE under harsher assumptions than previously considered attacks (e.g., in model extraction, access to resources such as G and W was restricted). In the adaptive attack setting that we consider, access to both G and W will be given to A, and robustness of GENIE'S watermark will be evaluated under these harsher assumptions.
To simulate real-world scenario, we assume that A accesses Mown (i.e., W) through an MLaaS system, querying Mown using only V. It is analogous to the standard assumption of the user of an MLaaS being oblivious to its underlying complexities (c.g., a user avails the service of a recommendation MLaaS system using only node IDs, i.e,, V, while being oblivious to the underlying (A, X)). We summarize the state of an adaptive A as follows: (1) A has access to Mede (i.e., W) apart from O's MLaaS; (2) A understands GENIE and knows that Mads has been watermarked using GENIE; (3) A knows the watermarking rate used (viz., aur aeg): and (4) A knows the original graph G.
The only information which A cannot infer from knowing GENIE are Dum and Grems which are secret, since they are created by random sampling. We discuss the viability of an adaptive attack that exploits this information for node representation and subgraph-based methods of GENIE as follows:
Node representation--asse methods. In hopes to break GENIE (i.c., to remove the watermark from Mado); A may altempt. to guess links present in Drom and construct 9wo by continuously querying O's MLaaS system. If successful, A can compare Gum (V, Eum) with G = =V,, E) to get the randomly sampled watermark links Swm = (E)Eum) U (Ewn and then fine-tune Mado with the labels opposite to Sum. potentially removing the watermark.
To defend GENIE against such an attack, O can design the MLaaS system to invert the output whenever a user attempts to query the links Sum- Consequently, any attempt to reconstruct 9um by querying O's MLaaS system would only result reconstruction of G instead of Gwm. To conclude, such a defense closes all doors for A to guess Pwn, thereby protecting O against such an adaptive A.
10

---

Published in Transactions on Machine Learning Research (03/2026)
Subgraph-based methods. If link present in Dum is queried to O's MLaaS system, the returned output will not be watermarked, i.., the MLaaS system will classify the link correctly. It is because during inference: (1) Mown constructs the k-hop subgraph Gu surrounding the link; and (2) performs binary classification of Gk- Since G& s node feature vectors X, have not been replaced with the secret watermark vector w present in D Dam: Mown will output the correct prediction of the link. Therefore, the guessing of links present Dar by querying O's MLaaS system infeasible. Consequently, the exploitation of D Dum 's knowledge not possible, in case of subgraph-based methods.
6 Ablations
6.1 Watermark Embedding
Embedding / Datazet
C.ele
USAir
NS
Yeast
Power
arXiv
PPI
Embadding
Cteat
87.30
89.62
93.45
89.84
59.28
95.83
Xu al
2023
J3-87
38-57
.49-85T
J4477
20-55"
26-15
Warm
Adi et al
2018
Weest
86.50
91:45
90.28
04.00
09.28
00.00
95.05
Warm
90.62
34461
96.07
96.00
4-88
21-05
Uniform Lose
85.37
30-05
44
02.02
98.20
83-20
31-45
Cum))
Warm
100
98.83
90.78
09.00
100
MGDA
Whest Warm
88.57
80.93
95.76
12.82
89.04
106-007
J0HHT
Weest 00.99
68.34
96.55
81:46
88.92
98.13
94.67
100
100
100
Table 4: Comparison among embedding methods. Highest and the second highest Weest values bold and underlined, ivspectively. Similarly, Weett values having drop greater than 2% from Crest W Wiom values being less than 80% are struck through.
We compare watermark embedding method on GCN models with baselines: (1) Fino-tuning
D Xu et al., 2023); (2) Data poisoning by mixing Dum and D.. AAd et al., 2018); (3) Uniform
Loss (i.e., -= Ler + Lum): and (4) Multiple Gradient Descent Algorithm (MGDA) (Désidéri 2012). with
Pareto-optimal loss (i.e., L -1 Lar + a22omm
[1 + 02 = 1, where 01, 02 are learnable scaling coefficients).
From results in Table we observe Xu et al.ss method and uniform loss violates functionality preserving constraint imposed in $5.2 Similarly, MGDA fails to preserve functionality in large datasets like arXiv and PPI. And while Add al. method gets highest Wrest, it fails to achieve high W.m, for reliable detection. These results show superiority of GENIE'S embedding approach over others.
6.2 Watermarking Pretrained Models
To study the feasibility of embedding watermarks into existing models, we investigate practical scenario where a model owner may realize the need for IP protection after model has already been trained. For this ablation, our experimental design begins with GCN model pre-trained on the primary link prediction task. Using these pre-trained weights as the starting point, instead of a random initialization, we then apply GENIE'S two-phase water- mark embedding approach (cf. (4.2) to inject the watermark. The results, presented Table 5 show negligible degradation in Weest from Crest across datasets, while maintaining consistently high watermark detection (Wumm & 100%). This confirms that our embedding method can effectively wa- termark pre-trained models, preserving their original utility while enabling reliable watermark verification.
Dataset Ciea Wiea
W
C.ele USAir
86.9
89.05
100
88.3
88.42
100
NS
96.6
95.85
99.78
Yeast
91.5
92.09
100
Power
98.9
98.81
99.00
arXiv
98.1
98.27 100
PPI
94.7 94.46 100
Table 5: Watermarking pretrained models.
11

---

Published in Transactions on Machine Learning Research (03/2026)
6.3 Hyperparameter Sensitivity Analysis
We investigate the sensitivity of GENIE to several key hyperparameters. First, we analyze the impact of the watermarking rate Our by varying it from 10% to 50%. Table G illustrates that increasing Our leads to a progres- sive decline in Wrest, which is particularly notable beyond 30%. Conversely, Wwm remains consistently high across all rates, indicating robustness of the watermark embed- ding even at lower rates. Second, we experiment with different statistical distributions for the generation of the watermark vector (Normal, Uniform, Poisson, Exponen- tial, and Bernoulli). As shown in Table [8] this choice has no significant effect on the effectiveness of GENTE
Watermarking Rate Our (%)
Dataset
10
20
30
40
50
Wiest
91.39
88.06
84.85
75.98
72.58
USAir
Wmm
100
100
99.86
99.73
99.68
Weett
86.93
83.67
77.91
70.94
65.78
C.ele
Wum
100
99.97
99.88
99.51
97.87
Wust
96.59
92.87
90.28
83.31
79.91
NS
Wum
99.77 95.96
93.47
91.45
88.57
Table 6: Impact of watermarking rate Oar-
7 Evaluation on Expressive Architectures (GAT and GIN)
To demonstrate the architcctural generalizability of GENIE beyond standard convolution-based aggregators (like GCN and GraphSAGE), we extended our evaluation to include Graph Attention Networks (GAT) and Graph Isomorphism Networks (GIN). These architectures introduce distinct challenges for watermarking: GAT employs anisotropic attention mechanisms that could potentially learn to "ignore" the watermark trig- ger by assigning it low attention weights, while GIN relies on sum-pooling and highly expressive isomorphism tests which might be sensitive to the structural perturbations introduced by the trigger.
Table summarizes the performance of GENIE on these architoctures across all seven datasots. The results indicate two key findings:
Robustness to Attention and Isomorphism: We achieve near-perfect watermark accuracy (Wum 2 99.0%) for both GAT and GIN across all datasets. This empirically confirms that the attention mechanism in GAT successfully aliends to the trigger features during the fine-tuning phase, and the injectivity of GIN's aggregation preserves the trigger signal effectively.
2. Utility Prescrvation and Regularization: For GIN, the utility loss remains strictly within the 2% threshold, with the largest drop observed on Yeast (1.64%). Interestingly, for GAT, we observe a phenomenon where the watermarked model frequently outperforms the clean bascline (c.g., +6.33% on PPI, +3.111% on NS). We hypothesize that the injection the walermark pattern acts as a form of structural regularization or data augmentation for sreention-based models, preventing overfitting on smaller sparser datasets without compromising ownership verification.
GAT
GIN
Dataset
Creat
Wiest
Wmm
Crest
Whest
Wmom
USAir
90.16
91.68
100.0
90.05
88.81
100.0
C.ele
82.78
86.79
100.0
83.12
82.71
100.0
NS
95.31
98.42
99.78
86.06
90.93
99.78
Yeast
88.89
92.57
100.0
88.54
86.90
100.0
Power
99.84
99.62
99.00
86.75
91.39
99.00
Xiv
99.19
99.39
100.0
99.30
99.26
100.0
PPI
88.58
94.91
100.0
92.96
91.36
100.0
Table 7: Performance of GENIE on GAT and GIN architectures across seven datasets. The table compares clean test AUC (Crest), watermarked test AUC (Waest), and watermark verification accuracy (Wum). GENIE consistently achieves high verification rates regardless of the aggregation mechanism.
12

---

Published in Transactions on Machine Learning Research (03/2026)
7.1 Efficiency
The computational efficiency of watermarking scheme crucial, as directly impacts its cost-effectiveness and practical adoption. In GENIE, computational overhead stems from two sources: the one-time Dum gener- ation and the per-epoch training. For watermark generation, the time complexity for node-representation methods includes a quadratic lerm, (((onr|)) (V))2) (cf. Appendix Eb. While this quadratic factor might sug- gest a practical bottleneck for extremely large-scale graphs (e.g., social networks with billions of nodes), our empirical analysis shows the required watermarking rate Our is not fixed. As shown in Table 9 Onr systenatically decreases as graph size increases, dropping from 10-15% for small datasets (e.g., C.ele, USAir) to 4% for large dataset. like arXiv. Thus, the base of the quadratic term, i.e., the number of selected water- mark nodes (a remains proportionally small, mitigating this potential bottleneck. For training, the overhead is primarily determined by the size of the trigger set, each epoch requires separate backprop- agation for both the training set and the trigger set. Table g illustrates this overhead in terms of Ota and Our- Our analysis confirms that while rates can be higher for smaller datasets (e.g., max Our of 15%), for large datasets, both Oagg and Our remain below 4%. This demonstrates that GENIE'S overall computational overhead is reasonable and scalable. Our evaluation already spans all benchmark datasets used in the GNN LP literature, including OGB datasets (cf. Appendix G
8 Conclusion
We introduced GENIE, the first watermarking scheme designed to protect the intellectual property of GNNs for link prediction. By creating novel backdoor for both node-representation and subgraph-based methods and pairing it with a statistically robust verification process (i.c., DWT), GENIE provides a practical and secure solution for ownership demonstration. Our extensive evaluations confirm that GENIR is effective, pre- serving model utility while demonstrating strong robustness against a wide array of sophisticated watermark removal, model extraction, and piracy attacks. Although we perform preliminary experiments on inductive link prediction, we leave more robust analysis to future work. Extending robust ownership demonstration dynamic temporal networks, where structural evolution could disrupt the embedded trigger, remains open problem. We hope our work spurs further research in securing graph-based machine learning models across diverse and evolving domains.
Broader Impact Statement
In this paper, we present method to watermark GNNs for link prediction using novel backdoor method. Though our work uses this backdoor for the positive cause of ownership demonstration and IP protection, we acknowledge it could also be used for harm. Given the potential implications of our finding for deployed ML systems and user-facing applications, we have taken multiple steps to ensure the ethical handling and responsible dissemination of our results. All experiments were conducted in controlled environments using publicly available datasets and models. At no point did we target production systems, external APls, or third-party applications. No sensitive, proprietary, or human-related data were involved in this study. We have adhered to standard ethical research guidelines to ensure that the dissemination of this work minimizes harm and promotes positive impact through increased model robustness.
References
Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas, and Joseph Keshet. Turning Your Weakness Into a Strength: Watermarking Deep Neural Networks by Backdooring. In USENIX Security, pp. 1615-1631, 2018.
V Batagelj and A Mrvar. Pajek Datasets: http://vlado.. fmf. httpa//iili/////p/ttooooo/a/a/aa US- Airg7. net, 2006.
Jinyin Chen, Haiyang Xiong, Haibin Zheng, Jian Zhang, and Yi Liu. Bon-ooooooor: Backdoor Attack on Dynamic Link Prediction. IEEE TNSE, 2023.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Charles J Clopper and Egon S Pearson. The Use of Confidence or Fiducial Limits Illustrated in the Case of the Binomial. Biometrika, 26(4):404-413, 1934.
Jiazhu Dai and Haoyu Sun. Backdoor Attack against. Link Prediction Tasks with Graph Neural Networks. 2024.
arXiv preprint:2401.022
David DeFazio and Arti Ramesh. Adversarial Model Extraction on Graph Neural Networks. arXiv preprint:1912.0777 077221, 2019.
Jean-Antoine Désidéri. Multiplo- Gradient Descent Algorithm (MGDA) for Multiobjective Optimization. Elsevier Comples Rendus Mathemalique, 350(5):313 318, 2012.
B Efron. Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, pp. 1-26, 1979.
Ernst Eypasch, Rolf Lefering, CK Kum, and Hans Troidl. Probability of Adverse Events That Have Not Yet Occurred: A Statistical Reminder. Bmj, 31 37005))))6619 620, 1995.
Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. A Survey of Quantization Methods for Efficient. Neural Network Inference. In Low-Pooer Computer Vision, pp- 291 326. CRC, 2022.
Aditya Grover and Jure Leskovec. Nede2Vec: Scalable Feature Learning for Networks. In KDD, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. NewrIPS, 30, 2017.
Song Han, Jeff Pool, John Tran, and William Dally, Learning both Weights and Connections for Efficient Neural Network. NeurIPS, 28:1-9, 2015.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge a Neural Network. arXiv preprint:1503.02 02031, 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Advonces in Newral Information Processing Systems, 33:22118 221333,, 2020.
Leskovec Jure. Snap Datasets: Stanford Large Network Dataset Collection. http: // snap stanford. edu/ data 2014.
Thomas N Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Networks. arXiv preprint:1609 02907, 2016.
Jian Liu, Rui Zhang, Sebastian Szyller, Kui Ren, and N Asokan. Falsc Claims Against Model Ownership Resolution. In 33rd USENIX Securily Symposium, pp. 6885 6902, 2024.
Nils Lukas, Edward Jiang, Xinda Li, and Florian Kerschbaum. SoK: How Robust is Image Classification Deep Neural Network Watermarking? Tn IEFE S&P, pp. 787-804, 2022.
Peizhuo Lv, Hualong Ma, Kai Chen, Jiachen Zhou, Shengzhi Zhang, Ruigang Liang, Shenchen Zhu, Pan Li, and Yingjun Zhang. MEA-Defender: A Robust Watermark against Model Extraction Attack. arXiv preprint:2401.1565 15239, 2024.
Matt Mahoney, Large Text Compression Benchmark, 2011.
Henry B Mann and Donald R Whitney. On a Test of Whether One of Two Random Variables Is Stochastically Larger than the Other. The Armals of Mathematical Stalistics, pp. 50 60, 1947.
Mark EJ Newman. Finding Community Structure in Networks using the Eigenvectors of Matrices. Physical Review E, 74(3):036104, 2006.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Walter G Park. International Patent Protection: 1960-2005. Research policy, 37(4):761-76,, 2008.
Hossein Pishro-Nik. Introduction to Probability, Statistics, and Random Processes. Kappa Research, LLC Blue Bell, PA, USA, 2014.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova, A Critical Look at the Evaluation of GNNs under Heterophily; Are we Really Making Progress? arXiv preprint wrXiv:2302.16644 2023.
Benodek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scalc Attributed Node Embodding. Journal of Complex Nelworks, (2))xnnab114 2021a.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, (2)ccnab014, 2021b.
Ahmed E Samy, Zekarias T Kefato, and Sarünas Girdzijauskas Leap: Inductive Link Prediction via Learn- able Topology Augmentation. In International Conference on Machine Learning, Optimization, and Data Science, pp. 448 463. Springer, 2024.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation. arxiv preprinl arXiv:1811. 1.05668, 2018.
Yun Shen, Xinlei He, Yufei Han, and Yang Zhang. Model Stealing Autakk against Inductive Graph Neural Networks. In IEEE S&P, pp. 1175-1192, 2022.
Bernard W Silverman. Densily Estimation for Stalistics and Data Analysis. Routledge, 2018.
Maciej Skorski. Kernel Density Estimation Bias under Minimal Assumptions. arXiv preprint:1901.0010 2019.
Neil Spring, Ratul Mahajan, David Wetherall, and Thomas Anderson. Measuring ISP Topologies with Rocketfuel. ACM SIGCOMM Computer Communication Review, 32(4):133-145, 2002.
Chris Stark, Bobby-Joc Breitkreutz, Teresa Reguly, Lorric Boucher, Ashton Breitkreutz, and Mike Tyers. Biogrid: A General Repository for Interaction Datasets. Nucleic Acids Research, 34(1):535 539, 2006.
Mark Saroufim Suraj Subramanian and Jerry Zhang. Practical Quantization in PyTorch, 2022. URL https:
Sebastian Szyller, Buse Gul Atli, Samuel Marchal, and N Asokan. DAWN: Dynamic Adversarial Water-
marking of Neural Networks. In ACM MM, pp. 4417-4425, 2021.
Jingxuan Tan, Nan Zhong, Zhenxing Qian, Xinpeng Zhang, and Sheng Li. Deep Neural Network Water- marking against Model Extraction Attack. In 31st ACM International Conference Multimedia, pp. 1588 1597, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXis preprint arXiv: 10903, 2017.
Christian Von Mering, Roland Krause, Berend Snel, Michael Cornell, Stephen G Oliver, Stanley Fields, and Peer Bork. Comparative Assessment of Large-Scale Data Sets of Protein-Protein Interactions. Nature, 417:399 403, 2002.
Asim Waheed, Vasisht Duddu, and N Asokan. GrOVe: Ownership Verification of Graph Neural Networks using Embeddings. In IEEE Symposium on Securily and Privacy (SP), pp. 2460 2477, 2023.
Matt P Wand and M Chris Jones. Kernel Smoothing. CRC press, 1994.
Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion- Scale Com- modity Embedding for F-Commerce Recommendation in Alibaba. In KDD, pp. 839 848, 2018.
15

---

Published in Transactions on Machine Learning Research (03/2026)
Duncan Watts and Steven H. Strogatz. Collective Dynamics of Wooall-Wordd Nature, 393(6684): 440-442, 1998.
Bernard L Welch. The generalization of 'STUEENT'Sppobleen when several different population varlances are involved. Biometrika, 34(1):28-35 35, 1947.
Bang Wu, Xiangwen Yang, Shirui Pan, and Xingliang Yuan. Model Extraction Attacks on Graph Neural Networks: Taxonomy And Realisation. In ASIACCS, pp. 337 350, 2022.
Jing Xu, Stefanos Koffas, Oguzhan Ersoy, and Stjepan Picek. Watermarking Graph Neural Networks Basod on Backdoor Attacks. In IEEE EuroS&P, pp. 1179 1197, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka, How powerful are graph neural networks? arXiv preprinl or Xiv: 0.0000, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting Semi-Supervised Learning with Graph Embeddings. In International conference machine learning, pp. 40-48, PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In KDD, pp. 974-983, 2018.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How Transferable are Features in Deep Neural Networks? NewrIPS, 27:1-9, 2014.
Scongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-Gnns: Neighborhood Overlap-Aware Graph Neural Networks for Link Prediction. Advances in Neural Information Processing Systems, 14:13683-16994 2021.
Jialong Zhang, Zhongshu Gu, Jiyong Jang, Hui Wu, Mare Ph Stoecklin, Heqing Huang, and lan Molloy, Protecting Intellectual Property of Deep Neural Networks with Watermarking, In Proceedings of the 2018 on Asia Conference on Computer and Communications Securily, pp. 159-172, 2018.
Muhan Zhang and Yixin Chen. Link Prediction Based on Graph Neural Networks. NeurIPS, 31:1-11, 2018.
Xiangyu Zhao, Hanzhou Wu, and Xinpeng Zhang. Watermarking Graph Neural Networks by Random Graphs. In IEEE ISDFS, pp. 1 1-6, 2021.
Haibin Zheng, Haiyang Xiong, Haonan Ma, Guohan Huang, and Jinyin Chen. Link-Backdoor Backdoor Attack on Link Prediction via Node Injection. IEEE TCSS, 11:1816-1831, 2023.
Jiong Zhu, Gaotang Li, Yn Yang, Jing Zhu, Xuehao Cui, and Danai Koutra. On the Impact of Feature Hetcrophily on Link Prediction with Graph Neural Networks. Advances in Neural Information Processing Systems, 37:65823 65851, 2024.
A Experiment Setup Details
Our codebase and related artifacts are publicly available at http://gthhb..oom/iiaaAktiit Seaprrarrrringrrapp--eerree-eeee Linie--ooooiii-----iitiiiii
A.1 Dataset Description
USAir (Batagelj & Mrvar 2006 is network of US Airlines. NS Newman 2006 is a collaboration network of researchers in nelwork science. Yeast, (Von Mering et al. 2002 is a protein-protein interaction network in yeast. C.ele (Watts & Strogatz 1998) is a neural network of C.elegans. Power (Watts & Strogatz, 1998) an electrical grid network of the western US. arXiv (Jurc 2014) collaboration network of arXiv Astro Physics from the popular Stanford SNAP dataset library. PPI (Stark et al.) 20066 is a protein-protein interaction work from BioGRID database. The dataset statistics given in Table
16

---

Published in Transactions on Machine Learning Research (03/2026)
Dataset
Nodes
Edges
USAir
332
2,126
NS
1,589
2,742
Yeast
2,375
11,693
C.ele
297
2,148
Power
4,941
6,594
arXiv
18,772
198,110
PPI
3,890
76,584
Table 8: Dataset statistics.
A.2 Model setup
SEAL: We use DGCNN as the GNN engine SEAT. We use the default. setting of DGCNN, i.e., four convolutional layers (32, 32, 32, 1 channels), a SortPooling layer (with 0.6), two 1-D convolution layers (with 16, 32 output channels), and neuron dense layer. We train our models for a total of 50 epochs (for both training with or without watermark). We
learning rate of 0.0001.
GCN, SAGE: We use 3-layer GCN and GraphSAGE model with hidden layer of dimension 256. We use a 3-layer MLP for downstream binary classification with 256 hidden layer neurons. We train our models for total of 400 epochs (for both training with or without a watermark). We use a learning rate of 0.001. Neo-GNN: We use 3-layer GCN with a hidden channel dimension of 256 as the GNN engine of Nco-GNN. We use a 3-layer MLP for downstream binary classification with 256 hidden layer neurons. We train our models for total of 400 epochs (for both training with or without watermark). We use learning rate of 0.001.
Both fir and Cuo use the same loss function (i.e., negative log likelihood) and optimizer (i.e., Adam) with the same learning rale. Table 9 lists our watermarking rate for each dalaset and respective model.
A.3 Watermarking Rates
The watermarking rates for GCN, GraphSAGE, and NeoGNN are similar since all of them are node- representation based methods, but it is different for SEAL since it a subgraph-based method. The watermarking rates are chosen based on the tradeoff between lowest loss on West and highest Wwm
Dataset
C.ele USAir NS Yeast Power ar Xiv PPI
GCN
10
15
10
5
4
GraphSAGE
10
5
SEAL
30
30
35
20
40
3
4
NeoGNN
10
5
Table 9: Watermarking rate (i.e., asg for SEAL and our for GCN, GraphSAGE, and NeoGNN) used in our experiments.
A.4 Baseline Setup
We briefly describe each baseline method used for comparisons:
Link-Bad Backdoor (Zheng et al.) 2023) Link-Backdood employs a gradient-based node injection strategy. Specifically, the attacker injects fake nodes to create a subgraph trigger involving target link nodes. Gradient information from the target model optimizes both the structure of the injected trigger and node features to ensure effective backdoor attacks while minimizing modification to benign data. During inference, the presence of the injected trigger causes intentional misclassification of specific links.
17

---

Published in Transactions on Machine Learning Research (03/2026)
Erdos-Renyi Induced Watermark (uu et al., 2023) This method generates an Erdos-Rent Renyi (ER) graph based on predefined watermarking rate and replaces edges among randomly selected nodes in the main graph with the edges from the ER graph. The watermark trigger comprises positive and negative edges within the ER subgraph. This direct replacement modifies the graph structure significantly, potentially affecting the original graph functionality.
Erdos-Renyl Inject Watermark (Modified Baseline) Our modified ER injection method generates ER graph based on the watermarking rate but, instead of direct edge replacement, connects each ER node to random nodes of the main graph. Positive and negative edges within the ER subgraph form the watermark trigger set. Importantly, the connecting edges between the ER subgraph and the main graph are excluded from training and watermark sets, used only for message passing during training.
Effective Backdoor (Dai & Sun, 2024) This approach introduccs a single trigger node with random features. The node is connected equally to selected positive and negative edges in the main graph, which constitute the watermark trigger set. These selected edges are manipulated (removal of positive edges and addition of negative edges) to form reliable backdoor trigger. Connections between the trigger node and the main graph are solcly used for message passing and are excluded from training or watermark datasets.
A.5 Detailed Explanation of Watermark Removal Methods
Model Extraction Attack Such attacks (Shen et al., 2022; DeFazio & Ramesh 2019 Wu et al. 2022)
pose & significant. threat to DNNs as they enable an adversary to steal the functionality of a vietim model. In these attacks, A queries the victim model (i.e., Win our case) using publicly available test samples and collect responses to train surrogate model (i.c., Made) to steal W's functionality. The literature on model extraction attacks is limited in the context of LP tasks on GNNs. Therefore, to evaluate GENIE against model extraction attacks, we modify the loss function employed in the knowledge distillation process (Hinton al. 2015) as outlined in Eq. and Eq. 2
Leoft LCE (0 (Bwm) , (Oadw)).
(1)
Lhord Lan (1 (0wm) 9 (Ondv)).
(2)
Here, Bwo and Gado denote the model parameters of Wand Madvs 6(0mm) and Φ(Badv) represent the log- its (i.e., output scores) produced by Wand Madu, while (0wm)) and (fadv) denote the hard predictions (e.g.. 0 or 1) made by the respective model. LCe denotes cross-entropy loss.
We consider 2 types of model extraction techniques, viz., soft label and hard label. In soft label extraction, we apply Los between the logits of W and Madv to train Mode (cf. Eq. I. In hard label extraction, we apply Loe between the predictions of W and Mado to train Madu (cf. Eq. 2 We train Madv model using half of Drest and evaluate it with the other half.
Knowledge Distillation It is the process of transferring knowledge from teacher model to student model (Hinton et al., 2015). In our context, the teacher is W and the student is Made. The extraction process comprises training Madr on the logits of W and the ground truth (Hinton et al. 2015 It helps with decreasing the overfitting of the victim model (i.e., W). Consequently, A might be able to remove the watermark and reproduce the core model functionality.
Model Finc-Tuning Fino-tuming (Ysinski et al., 2014) one of the most commonly used attacks to remove the watermark since it is computationally inexpensive and does not compromise the model's core functionality much. To test GENIE against this attack, we use half of Dreat for fine-tuning and evaluate the fine-tuned model's (i.e., Madv) performance with the other half. Through extensive experinentation and analysis, we determined that limiting the training process to 50 epochs serves as an optimal strategy (i.e., to avoid the risk of overfitting Mady on the subset of Diest used for fine-tuning). We evaluate GENIE against 4 variations of fine-tuning. These can be classified into two broad categories (Yosinski et al. 2014):
Last layer fine-tuning: This fine-tuning procedure updates the weights of only the last layer of the target model. It. can be done in the following two ways.
18

---

Published in Transactions on Machine Learning Research (03/2026)
1. Fine-Ture Last Layer (FTLL): Freezing the weights of the target model, updating the weights of
its last layer only during fine-tuning.
2. Re-Train Last Layer (RTLL): Freezing the weights of the target model, re-initializing the weights of only its last layer, and then fine-tuning it.
All layers fine-tuning: This fine-tuning procedure updates weights of all the layers of the target model. It a stronger setting compared to the last layer fine-tuning method as all the weights are updated, which makes tougher to retain the watermark. It can be done the following two ways.
Fine-Tune All Layers (FTAL): Updating weights of all the layers of the target model during fine- tuning.
Re-Train All Layers (RTAL):
Re-initializing the weights of target model's last layer, updating weights of all its layers during fine-tuning.
FTLL is considered the weakest attack because it has the least capacity to modify the core GNN layers responsible for learning the watermark. Conversely, RTAL is considered the toughest attack because it enables complete fine-tuning of all model layers, providing the highest flexibility to potentially overwrite or distort the watermark embedded across multiple layers.
Model Compression It is a technique to reduce the size and complexity of a DNN, thereby making it more efficient and casily deployable. Compressing the model can inadvertently or otherwisc act as an attack against the watermark. Thus, lest. GENIE'S robust.nsss with following two model compression techniques:
Model pruning: Model parameter pruning (Han et al. 2015) selects fraction of weights that have the smallest absolute value and makes them zero. It is computationally inexpensive watermark removal techmique.
Weight quantization: It is another model compression technique to reduce the size of a model. It changes the representation of weights to a lower-bit system, thereby saving memory. It is often used to compress large models, e.g., LLMs (Gholami al.] (022).. We follow the weight quantization method (Suraj Subramanian & Zhang 2022 with bit-size (Tan et al. 2023
Fine-Pruning It key defense against backdoor attack that combines model pruning and fine-tuning It is more effective than individual pruning or fine-tuning, which makes it difficult for the watermark to survive. We start by pruning fraction of the smallest absolute weights. Next, we fine-tune the pruned model with half of Diest and evaluate the pruned fine-tuned model (i.e., MMdo)) with the other half. We perform an exhaustive evaluation with pruning fractions ranging from 0.2-0.8 a step size of 0.2, which is followed by one of the four types of model fine-tuning (i.c., FTLL, RTLL, FTAL, RTAL). Our rigorous experiments aim to provide a holistic understanding of GENIE'S robustness against the fine-pruning technique.
B Statistical assurance of non-trivial ownership in Genie
The values of Cumn and W are given for n 10 different C and (Dum, W) in Table 10 (for SEAL), Table II (for GCN), Table 12 (for GraphSAGE), and Table I3 (for NeoGNN), The corresponding p-values are also mentioned. To correct for multiple comparison, appropriate corrections such Bonferroni or BH correction must. be applied. However, we observe that for each dataset. and architecture, the p-value is observed to be much below the significance level, i.e., 1 1- 0.05 (p = 0.000 in most cases). Therefore, we reject Hg for each architecture and dataset as described in 4.3
C Analysis of DWT
C.1 Sensitivity Analysis
To evaluate the robustness and stability of DWT, we conduct sensitivity analysis with respect the number of initial samples and the bandwidth used for estimating the underlying distributions. The primary
19

---

Published in Transactions on Machine Learning Research (03/2026)
Dataset
AUC (%)
p-value
Cum
38.63
25.60
23.70
28.72
22.48
23.29
20.39
22.62
26.83
24.97
C.ele
0.000
Wwm
76.58
77.19
77.32
78.91
78.72
77.69
78.24
77.39
78.24
75.94
Cwm
8.00
6.97
5.88
7.10
7.61
7.92
6.92
8.72
7.72
8.79
USAir
0.000
Wwm
94.01
94.02
94.65
93.59
93.81
95.17
95.39
94.13
94.08
94.14
Cuo
3.41
1.73
2.25
2.57
1.91
1.72
2.04
2.50
3.70
2.10
NS
0.000
Wwm 98.66
98.71
98.75
98.68
98.65
98.73
98.69
98.72
98.73
98.73
Cum
14.37
6.73
12.49
15.54
10.21
8.03
4.23
40.05
5.02
10.72
Yeast
0.000
Wwm
97.50
98.02
98.09
97.75
97.83
97.21
97.47
97.15
97.87
97.96
Cwm
13.64
19.46
18.60
12.09
15.09
12.01
12.48
12.69
29.46
12.25
Power
0.000
Wwm
88.28
88.31
88.33
88.27
88.25
88.24
88.28
88.26
88.31
88.32
Cum
7.04
2.38
3.09
2.16
3.43
4.98
7.95
6.72
2.61
5.73
arxiv
0.000
Wwm
97.98
97.88
98.18
98.26
97.94
98.08
98.36
98.33
98.30
98.23
Cuon
9.96
12.76
9.68
12.09
9.90
15.35
10.44
13.89
11.99
26.02
PPI
0.000
Wwm
83.81
83.81
84.51
82.78
86.25
83.82
84.94 84.23 81.93 86.81
Table 10: Non-trivial ownership results for SEAL.
Dataset
AUC (%)
p-value
Cum
4.00
7.82
0.00
0.00
13.85
0.44
7.14
2.04
11.77
31.36
C.ele
0.000
Wwm
100.0
99.89
100.0
100.0
100.0
99.78
100.0
100.0
99.86
98.82
Cwm
31.48
19.20
13.64
16.18
20.16
13.55
33.48
14.27
13.13
29.94
USAir
0.000
Wwm
100.0
100.0
100.0
99.91
100.0
99.96
99.83
100.0
100.0
99.78
Cum
0.00
3.40
11.76
4.33
0.00
6.93
15.22
13.57
5.25
40.74
NS
0.002
Wom
82.00
94.44
100.0
99.31
98.78
97.65
97.75
98.75
98.75
97.84
Cum
18.34
16.53
13.33
0.00
18.93
27.81
18.34
12.88
10.06
18.80
Yeast
0.000
Wwm
100.0
99.59
100.0
100.0
100.0
99.74
100.0
100.0
100.0
100.0
Cum
10.07
0.00
0.00
3.56
7.69
0.00
0.00
22.31
2.55
30.79
Power
0.000
W
98.96
98.00
94.44
100.0
92.90
98.44
99.22
97.55
98.47
100.0
Cuo
2.26
1.24
2.91
1.09
1.58
2.08
1.72
1.45
1.26
6.67
arXiv
0.000
Wwmm
100.0
99.99
100.0
100.0
100.0
99.99
100.0
99.98
100.0
100.0
Cuna
8.07
8.96
5.78
4.48
6.94
6.18
4.17
5.28
10.85
22.14
PPI
0.000
Wom
100.0
100.0
100.0
99.98
99.96
100.0
100.0
100.0 99.97
99.96
Table 11: Non-trivial ownership results for GCN.
objective is to understand how the sample size and bandwidth, denoted by s and h respectively, influences the mean and variance of the resulting watermark threshold, 6, even under cases where a large h would yield overlapping probability distributions.
The analysis employs a Monte Carlo simulation framework. For cach datasot, we vary (1) the sample size s over values {4, 5,..., 10) keeping the bandwidth h hu constant; (2) the bandwidth h over values (0.5hn, 0. 0,75h,, ba, 1.25/o, 1.5hg, 2ho} keeping 10 constant. Here, by is the bandwidth obtained using
20

---

Published in Transactions on Machine Learning Research (03/2026)
Dataset
AUC (%)
p-value
Cuoa
7.63
3.32
9.57
12.40
2.22
25.78
7.62
12.93
13.67
15.38
C.ele
0.000
Wwm
99.88
99.86
99.61
99.59
99.78
100.00
99.61
99.55
100.0
100.0
Curn
8.57
5.78
7.43
3.78
11.09
3.86
18.38
7.64
20.85
25.00
USAir
0.000
Wwm
99.90
100.0
100.0
99.96
100.0
100.0
100.0
100.0
100.0
100.0
Cum
9.34
16.44
19.66
7.76
28.39
11.25
18.00
21 .28
17.46
25.00
NS
0.000
Wwm
91.52
99.11
97.16
96.95
97.31
96.50
89.75
97.68
96.28
97.62
Cum
0.00
18.00
20.14
31.00
23.47
7.96
0.00
18.37
12.24
40.62
Yeast
0.007
Wmm
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Cum
0.00
2.00
30.56
2.47
3.56
0.00
0.00
15.00
12.00
25.00
Power
0.000
Wwm
97.53
92.00
97.57
96.30
94.44
97.53
96.28
93.50
98.00 92.97
Cuo
0.00
2.00
30.56
2.47
3.56
0.00
0.00
15.00
12.00 25.00
arXiv
0.000
Wum
97.53
92.00
97.57
96.30
94.44
97.53
96.28
93.50
98.00 92.97
Cuon
23.12
12.98
16.74
3.12
9.58
4.92
7.46
4.39
17.12 25.00
PPI
0.000
Wwm
100.0
100.0 99.90
99.97
99.89
100.0
99.97
100.0
100.0 99.83
Table 12: Non-trivial ownership results for GraphSAGE.
Dataset
AUC (%)
p-value
Celegans Cwm
20.31
28.12
23.44
12.50
25.00
14.06
18.75
23.44
23.44
15.62
0.000
Wum
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Cum
11.33
12.60
10.16
12.89
11.23
11.33
10.64
14.84
11.91
9.18
USAir
0.000
Wwm
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Cwm
23.11
20.22
28.89
26.44
31.78
26.44
17.33
28.89
23.11
11 31.78
NS
0.000
Wwm
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Cwm
5.33
7.10
8.28
9.47
9.47
6.80
8.88
8.28
5.62
9.47
Yeast
0.000
Wwm
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Cum
50.00
45.00
45.00
50.00
50.00
50.00
50.00
50.00
50.00
45.00
Power
0.000
Wwm
100.0
100.0
100.0
97.00
100.0
100.0
100.0
100.0
100.0
100.0
Cum
8.38
1.17
9.42
7.64
1.25
8.15
9.01
8.20
7.05
9.86
arXiv
0.000
Wom
97.34
94.03
93.64
90.38
87.73
96.19
97.
99.97
98. 70
92.44
Cwm
24.52
2.85
15.15
11.11
10.47
16.25
17.95
6.52
10.19
12.81
PPT
0.000
W
100.0
99.91 97.43
97.61
95.32
94.63
97.52 97.06
100.0
96.97
Table 13: Non-trivial ownership results for NcoGNN.
Silverman's rule of thumb of 1000 independent. trials. The procedure for each trial is as follows:
Silverman 2018). For fixed value of s and t, we perform simulation consisting
Subsampling: We randomly draw, without replacement, a subsample of s data points from the complete set of scores obtained from clean models (C). Concurrently, we draw another subsample of size s from the complete set of scores from watermarked models (W).
21

---

Published in Transactions on Machine Learning Research (03/2026)
C.ele
USAir
Yeast
Power
arXiv
PPI
38.46 21.31
50.08 + 6.28
48.65
29.07
36.63 + 7.38
41.06 20.95
7.72 + 4.16
24.31 + 12.91
38.04 18.95
49.91 + 4.02
48.65
26.04
37.57 + 7.34
40.80 18.40
7.69 3.79
23.65 + 12.06
38.98 + 17.07
19.43 + 3.16
18.60 + 23.60
39.37 + 6.55
10.96 + 16.42
7.51 + 3.52
23.97 + 11.61
38.96 15.32
49.46
2.47
48.01
21.35
40.50
5.67
42.36
13.71
7.31 3.30
23.51 + 11.06
38.61 = 14.30
49.31 = 1.67
46.58 = 19.98
42.02 + 3.91
45.53 = 7.60
7.09 - 3.13
23.38 + 10.65
44.79 11.33
49.10
1.38
55.60
16.93
41.80
2.60
48.37
6.62
8.67 2.53
28.18 1 7.89
10
49.67 = 0.79
49.10 + 0.50
63.63 + 0.92
41.64 1 0.56
51.24 + 0.85
9.84 1 0.13
32.24 + 0.43
50.63
49.69
64.82
42.35
52.29
10.00
32.77
Table 14: Sensitivity analysis of DWT to the number of samples s. t is the reported threshold.
C.ele
USAir
NS
Yeast
Power
arXiv
PPI
0.5hg
40.24 + 0.56
40.99 + 0.44
51.88 0.67
34.49 + 0.43
40.68 + 0.60
8.21
0.09
27.05 - 0.31
0.7
44.66 + 0.80
44.81 + 0.61
57.34 + 1.04
37.83 + 0.62
45.63 + 0.98
8.98 + 0.14
29.47 + 0.45
ho
49.11 + 1.10
48.64 + 0.79
62.90 + 1.38
41.22 + 0.80
50.52 + 1.22
9.73 + 0.19
31.90 1 0.61
1.25/kg
53.56 + 1.35
52.55 + 0.89
68.08 + 1.66
44.54
1.02
55.56 + 1.42
10.50 1 0.23
34.35 + 0.77
1.5ha
57.85 + 1.68
56.46 + 1.01
68.47 + 1.10
47.92 + 1.21
60.66
+ 1.72
11.27 + 0.28
36.77 + 0.89
2ho
66.93 + 2.09
64.37 + 1.25
68.33 + 0.95
1.46 54.84
70.69 + 2.21
12.79 + 0.37
41.68 + 1.21
50.65
49.69
64.82
42.35
52.29
10.00
32.77
Table 15: Sensitivity analysis of DWT to bandwidth h. t is the reported threshold.
Threshold Estimation with s: The DWT procedure is executed using the two smaller subsamples of size 8, with threshold value, 4, for the i-th trial.
3. Threshold Estimation with h: The DWT procedure is executed using bandwidth h, with thresh- old value, t, for the i-th trial.
After exccuting all 1000 trials for a given 8 or h, we obtain 1000 threshold values, {fi, f2...,... 11000>- From this distribution, we compute the sample mean (1) and sample standard deviation (a.) to quantify the expected threshold and its variability. This entire process repeated for each value of {4, 5,......, 10}
and h E (0.5hg, 0.75hg, ho, 1.25/g, 1.5/g. 2h,} for every dataset under evaluation. Table 14 15 show the
results for GCN. In both the tables, observe the reported threshold to be more than the mean threshold
in most cases, indicating the reported thresholds avoid large FPR. We also see / less when overly smooth h 2 1.5hg is used to yield overlapping distributions, indicating the reported thresholds avoid large FNR as well.
C.2 Theoretical Analysis
We elaborate on the proof sketch of the theorem given in
4.3 adapted from Eypasch et al.
1995p.
Proof. We first note that
Pr(X, 0) (1 (1-
(3)
Hence, observing X, = -0 for all j -= 1...., ......., m yields
Pr(X, = O,..., Xmm = =0) = (11-1) ((1-p)")m = (1 p)) mn
(4)
If p 1, then using the inequality, th + V x R we get,
(1 - p) s e + $ e n
(5)
implying
(1
< exp( (mmp) -m
(6)
22

---

Published in Transactions on Machine Learning Research (03/2026)
Thus,
Pr (all zeros
p> 1/n) S e
(7)
If we choose such that
2 - 1n(1 1111-y
(8)
then the probability of observing zero events in all m blocks despite p 2 1/n is at most 1 1-1 Equivalently, whenever we do observe zero events in all m blocks, it follows with confidence at least y that < 1/n.
D Ownership Demonstration
We now outline the process for O to demonstrate her ownership A's model (i.e., Madv). OD uses J briefly outlined in $3 GENIE has two-step OD procedure that involves model registration step and a dispute resolution step.
Model registration: As preemptive step of OD, O first sends G to J to procure D Dum, addressing the problem of malicious plaintiff outlined in (Lin ct al. 2024). J then writes the cryptographic hash of Duo onlo a time-stamped public bulletin board (e.g., blockchain) to provide the proof of anteriority case of a dispute. We call this preemptive step model registration since analogous to patent registration common in the protection of IP rights (Wahood ct al.) 2023
Park 2008). The procured D Dwm will then be used for embedding the watermark into M, i.e., train untrained M to be W by O.
Dispute resolution: When dispute arises, OD involves the following steps: (1) O accuses A of plagiarizing her model W; (2) A sends Mado to J for an evaluation; (3) O sends Dum and the hashes of all the files. Here, the hashes are sent via a secure communication channel to ensure that the files are not tampered with; (4) I runs a check on the hashes of the files sent. Next, J checks the record of Dumm the public bulletin board. If matching record found, J first calculates the watermark threshold t, and evaluates Mado on Dum to get Wwe. The OD ends with comparison of Wiem against 6, settling the dispute between O and A with just verdict. On the other hand, if record is not found, the dispute resolves in O's defeat.
E Time and Space Complexity Analysis
Redesseeprsontttionn Based Methods. Time Complenity: The total time is the sum of the times for each step in the watermark generation process.
1. Node Sampling: Sampling |S] nodes from [V] nodes uniformly at random takes O((S)) = O(anr (VD) time.
2. Watermark Graph Construction: Constructing the watermark graph 9wm involves creating the complement of the subgraph induced by S, denoted Gs. This requires iterating through all possible pairs of nodes in S to determine the edges in the complement Es. This step has time complexity of (([S)2)= = (V))).
Feature Matrix Modification: For each of the |S| nodes, the d-dimensional feature vector is replaced with the watermark vector w. This operation takes O(S) d) O(anr time.
Combining these steps, the dominant terms determine the overall time complexity. Therefore, the total time complexity is O((anr VI) + (Vd)).
Space Complexily: The space complexity determined by the storage requirements for the generated wa- termark dataset Dum (Ewm Awm: Xums Num).
1. Adjacency Matrix Awm: Storing the adjacency matrix for the entire graph Gwo requires O(())) space.
Feature Matrix X Storing the modified node feature matrix for all nodes requires O(V]d) space.
23

---

Published in Transactions on Machine Learning Research (03/2026)
3. Edge Index Eum: The edge index for the watermarked portion contains edges from &s U The number of these edges is bounded by O([S))). This is subsumed by the O(D2)) term for the full adjacency matrix.
Proof. The total space complexity is dominated by the storage of the full graph's adjacency and feature matrices, resulting in O(122 + (Vld).
]
Proof. The proof is divided into analyzing the time and space requirements.
Time Complexity: The process involves sampling subgraphs and modifying the features of all nodes within them.
1. Subgraph Sampling: Sampling = [[ subgraphs from the training set of size T takes ((s) = ()sgg) time.
This is the most, computationally intensive step. For each of the s sampled subgraphs, iterate through its Nuub nodes and replace their d-dimensional feature vectors with the watermark vector w. The total time for this operation is O(s Nout d) (aasy T Nuub d).
Feature Matrix Modification:
3. Label Inversion: Inverting the labels for the subgraphs takes O(s) time.
The feature modification step is the dominant factor. Thus, the total time complexity is O(a,gT Nuub d).
Space Complexity: The space complexity is determined by the storage nceded for the watermark dataset
D Dam: which consists of the s modified subgraphs.
For each of the s modified subgraphs, we need to store its structure and node features.
Node Features: Storing the features for Noub nodes, each of dimension d, requires O(Nsub d) space per subgraph.
3. Subgraph Structure:
Storing the adjacency information for subgraph of Neub nodes (e.g., adjacency matrix) requires ((N space per subgraph.
The lotal space required is the space per subgraph multiplied by the number of subgraphs Therefore, the total space complexity is O(s (Naudd + N2. = O(o.gT(NNal (Noudd + N2
F
Additional Results
F.1 Inductive Link Prediction results
Inductive link prediction is useful case where predictions need to be made on unseen nodes that are not present during the training time. Accordingly, the threat model for walermarking inductive link prediction also differs significantly from the transductive setting. We summarize the difference between the two settings in Table [6
We watermark the state-of-the-arl inductive link prediction method LEAP Sany el al. 2024) using GENIE keeping all hyperparameters identical to those used in LEAP. On Wikipedia (Rozemberzzki et al. 2021a and PubMed (Yang al.] 2016), ; at a 3% watermarking rate (Table 17h, GENIE attains high W Wm of 25% and 100.00% while having drop from Crest Wrest by less than 2 percentage points (a 0.55% gain on Wikipedia and 0.39% drop PubMed).
24

---

Published in Transactions on Machine Learning Research (03/2026)
Aspect
Transductive
Inductive
Graph soope
Fixed graph at train and test time.
New nodes or graphs appear at test time.
Adversary observability
Adversary can observe or reconstruct large parts of the training (target) graph.
Adversary lacks access to training graph.
Atack surface
Query-based graph reconstruction, graph. Model can overfit to triggers; higher watermark verification easier. Stronger adversary with high graph visibility.
Model extraction and retraining on different graphs.
fine-tuning, pruming
Watermark exposure
Triggers must generalize; higher wa- termark verification is harder. Weaker adversary due to limited data overlap.
Threat model implication
Table 16: Threat model differences between transductive and inductive link prediction settings
Metric
Wikipedia (%)
PubMed (%)
Crest 89.50
94.90
Wiest
90.05
94.51
Wum 97.25
100.00
Table 17: AUC metrics on Wikipedia and PubMed. Watermarking rate is 3%
F.2 Effect of Watermark Vector Distribution
We analyze the effect of watermark vector distribution using GCN with watermarking rates as mentioned A.3 on USAir, Celegans and NS datasets in [8] We find that the watermark vector distribution has almost effect the performance GENIE making it robust to multiple distríbutions.
Dataset
Watermark vector distribution
Normal
Uniform
Esponential
Bernoull
USAir
Whest
Wwm
58.34
100
89.31
100
88.83
100
$7.29
100
87.90
100
C.cle
Whest
N8
Wiest Wwmm
96.59 90.77
09.77
98.02
97.10 90.77
96.75
99.77
99.77
96.47
Table 18: Impact of Watermark vector distribution
F.3
GCN
F.3.1 White- Attacks at different % (Robustness)
Pruning Table 19 shows the results of GCN watermarked using GENIE under Pruning attack from 20-80%
pruning percentages.
25

---

Published in Transactions on Machine Learning Research (03/2026)
Pruue Porcentage (%)
Dataset
C.cle
Weest
Wam
88. 91.
100
86.97
100
66.31
100
83.92
100
70.31
75.43
USAi
Wiest
Wiest
90 00.00
96.25
90.01
96.08
91.31
Warm
99.77
99.77
99.77
99.08
85.55
Youst
Wiesi
91.46
91.27
100
89.97
85.71
80.50
74.35
Power
Whest Wumm
98
90
99.00
09.00
95.00
99.
08.32
74.00
05.00
02:43
arXiv
100
07:911
99.98
83.08
94.79
41.95
84.37
PPI
Weest
Warm
94.07
100
94, 60
100
04.06
100
02.88
78.87
90.00
Table 19: Impact of model pruning.
Finc-pruning Tables
23
present results for different fino-pruning tests for the GCN model.
Percentage (%)
40
00
80
Clele
Wiest
$6.98
00.02
80.
75.54
UBAir
Wam
Wrest
86.34
100
89:15
91.21
68.85
00:42
87.50
86.30
09:52
87.53
NS
89.77
90.77
95.88
87.55
80.11
Yonst:
Wamm
Wiest
91.46
100
01.52
91.41
90.50
85.20
80.00
83.30
96.64
Power
Wiest
99.00
05.02 02
99.00
95,00
87.00
72.00
arXiv
Weest Warm
98.13
100
06 54
$6.51
61.51
08
59:24
88.07
B6 74
30.07
PP1
Warm
84.07
1.00
94
32
85.52
94. 73
79.43
51.97
Table 20: Impact of pruning + FTLL.
(%)
20
40
60
80
Weest
100
67.51
USAir
Wrast Wam
88.34
87.57
87.50
65.09
86.59
100
82.12
82.81
19.58
81.62
NS
Weert
97.56
Yonst
Wiest Wam
91.46
100
00.72
58.16
00.19
88.16
77.51
83.87
96.24
94.01
Weest
09.
98.73
99.00
08.00
acXiv
Weest Wamm
98.18
100
05 64
44.85
08
47.04
88.07
48:31
86.74
39.69
84.07
94.
04.04
63.54
100
58.41
01.42
53.16
Table 21: Impact of pruning + RTLL.
26

---

Published in Transactions on Machine Learning Research (03/2026)
Prupe Porcentage (%)
Datwst
C.cle
Whast
Wwm
$6.305
100
75-13
71.87
60.93
77.27
78.12
75.48
14.68
82.50
USAir
Weest
NS
Wiest
Wamm
99.77
96.69
91.00
89:11
84.06
69.38
85.00
88.60
97.54
92.22
Yeust
Wiest
100
90.06
09.40
Power
Whest
Whmm
80.00 00
82
88. 00
97.30
07.
87.00
84.00
97:68
67.09
86.07
axXiv
98.13
1.00
08:
08:
05.50
33.05
88.
17.00
PPI
Wease
Warm
94.67
100
04. 02
80
04.04
75.39
66.20
93.08
98.57
15.36
Table 22: Impact of pruning + FTAL.
(%)
20
40
60
80
C.ele
Weest
Ut
Weest
$8.34
85.46
84.91
63.26
64.50
Whmm
100
63.76
65.32
62.79
47.75
N5
Wtast
Youst
Whmm
Whest
91.46
100
88.70
$4.002
92.39
65.47
89.94
64.50
82.89
83.31
Wiest
64.99
acXiv
Wiest Wam
98.18
100
05.
20.67
98.01
19.46
97:61
17.99
96.52
13.03
Wiest 94.67
02.79
1000
44.81
27:05
Table 23: Impact of pruning + RTAL.
F.3.2 Non-Ownership Piracy
GENIE injects watermark into an untrained model while A has access to only W. In a real-world setting, A can still generate her own pirated trigger set and train stolen W obtain Mado (gencrally called pirated model). Given that training on just the pirated trigger set might lead decrease in Weests would want to identify optimal number of epochs for training with the pirated trigger set such that Madv has high AUC on both Drest and the pirated trigger set. Figure 4 shows the variations in Madv's 's performance D Dum. Deest, and pirated trigger set during pirated watermark embedding process across different numbers of epochs for GCN over NS dataset; cf. Figure 5 for other datasets.
1.0
0.9
0.8
0.7
0.6
Proated Watomark AUCA
AUC
Visterrmn threshold Tolorable
50
100
150
250 spochs
200
300
250
400
Figure An example of Made's 's performance trajectory on D um D Deests and pirated trigger set during embedding of pirated watermark across training. AU AUCo and A denote Wiom and Wrest, respec- tively.
Drest
27

---

Published in Transactions on Machine Learning Research (03/2026)
We that Made performs well on Dum: Drest; as well on pirated trigger sets around 20th epoch. If O challenges A to present her model at this point, Madv will contain A's pirated watermark well as O's watermark. However, O can present W containing only her watermark. Thus, identifying the true owner will be casy in such a dispute. We further observe that around 250 epoch, AUC Dam drops below the watermark threshold (ef. Table [], but Whest is below the tolerable utility loss (i.e., up to 10%; following the definition of failure in $5.4) is willing to tolerate. Even A chooses to train for even higher epochs while embedding the pirated watermark, Made continues to lose its utility; rendering the Madu useless. Hence, we take the liberty to claim that GENIE is robust against piracy attacks (i.e., A cannot fraudulently claim ownership or fabricate watermark over a pirated model). Now, we present the results for the other datasets in Figure
1.0-
1.0
1.0
0.9
0.9
0.8
0.8-
0.7
0.7
0.8-
Piated matermark
Pirated wetermark AUC
Pintted wateermerk
AUC
AUC
AUC
0.6-
AUC
threshold
AUXC
Watermar Urreshold utility
0.4-
Watermark threshold
Abe
Tolerable Utilty 1060
Tolorable utility loss
5
50
120
150
200
250
300
350
400
50
100
150
360 spochs
200
25D
350 460
0
50
100
150
200
250
380
150
450
spoctts
epachs
(a) C.ele
(b) USAir
(c) PPI
0.8
Prated
AUC
0.6
AUC
0.7
AUC
AUC
Pirated watermank AUC
0.4-
Toler uiiity
Watermark thresholo
0.6
Natormakk threshols Tele dble Juily loss
AUC Dur
Welemmark threshold Tolerable Utility 055
0
50
150
200
300 350 400
100
200 250 spochs
300
350
400
100
150
200 opachs
250
360
400
epochs
(d) Power
(e) Xiv
(f) Yeast
Figure 5: Non-ownership piracy test for GCN model on different datasets. AU AUO W Wwm and Weest; respectively.
D and AU denote
Drase
F.4 GraphSAGE
Tables
24 32
present results for different robustness tests for the GraphSAGE model.
Coudition/Dataaet
Cicle
UsAir
N8
Yeast
Power
arXiiv
PP1
Before model
Wiesi
56.
51.89
94.35
91.23
94.57
100.00
100.00
89.77
100.00
80.00
100.00
100
After aoti
Wiest
86 69
99.76
82.50
90. 70
03.29
90. 41
94.68
extraction
Wwm
100 00
76.33
86.66
100.00
85:00
85.00 42
100 00
After hard
55 66
90
89.74
60.56
25
94.28
95.31
06.21
83.11
100.00
91.00
100.00 00.00
Table 24: Impact of model extraction.
28

---

Published in Transactions on Machine Learning Research (03/2026)
Coudition/Dataan
C.ole
USAir
N8
Yeast
Power
arViv
PP1
Weeat
dtstillation
After
Wazat
87.37
92.31
86.89
90.35
91.30
90.48
99679 100.00
distillation
Werm
81.25
60.30
71.78
98.52
90.00
89.44
Table 25: Impact of knowledge distillation.
Dataset
Fine-tuning Method
FTLL
RTLL
FTAL
RTAL
Chole
Wieat
86
84.37
82:75
76.51
Wan
100 00.00
100.0
92.19
85.94
90.62
USAir
91.89
90
80.28
88.47
100.00
100.0
86.39
Waest
94.35
90.31
81:31
89:71
Wagm
99.77
80.32
Yeast
90.44
90.37
88.3
68.98
85.89
100.00
100.00
100.00
99.41
99.41
Weat
91.29
82:18
89.18
Wmmm
Jired
ArXiv
98. 40
96
69.43
99
Wamm
100.00
90.88
09.14
19:00
16-H5
Winal Warm
99.57
94.77
43. 86
83.99
92.54
Table 26: Impact of model fine-tuning.
Percentage (%)
20
40
60
80
Weeat Wamm
USAI
Wreat
Wam
91.89
100.0
91.90
100.0
91.88
100.0
91.78
100.0
88.71
95.83
Wreat
Yeart
Wreat Wiem
90.44
90.30
$9.86
88 33
75 75.85
100.0
100.0
100.0
100.0
66. 96
Power
Weeat
arXiv
Weeat Waom
100.00
99. 40
100.00
99. 80
100.00
99:35
85.00 25
90
93:91
52.87
PDI
Weest
100.00
Table 27: Impact of model pruning.
Condition/Datennn
Ciele
USAir
Yoast
arXiv
PP1
Before
Weeat
86.46
91. 30
04.35
80.44
01.23
90.
94.07
quantisation
Wam
100.00
100.00 00
39.2 77
100.00
99.00
100.00
100.00
After quantiaation
$3.09
89.98
91.49
87.
92.68
100.00
100.00
99.00
85.26
Table 28: Impact of weight quantization.
29

---

Published in Transactions on Machine Learning Research (03/2026)
Pruue Percenlage (%)
Dateset
C.cle
Wease
Warm
100. 00
86.4
100.00
89.21
100.00
58. 73
100.00
87.
87.59
$7.50
USAi
Weest
100.0
100.0
N8
Weest
Wamm
94.36
99.77
99.38
88.46
09. 38
88.00
99.3
88 60.72
77.50
59.11
Yeass
Wreed
90.44
100.0
100.0
100.0
90
Power
Weeed
Warm
01:23
99.00
99
94.38
99. 00
94.20
04 25
90 00
92. 87
00
acXiv
Wened
100.00
99.40
99.
98. 02
25-6T
90 33
66
PPI
Weant Wam
94.37
0
94.74
100.0
04.01
100.0
94 36
01.92
Table 29: Impact of pruning + FTLL.
Dataset
Prune Percentage (%)
C.ele
Weest
Wwo
100.00
56.46
84.31
92.19
84 56
87. 50
84.96
85.93
85.55
65.62
Whast
N8
Wiest Wiom
84.35
99.77
98.44
93.07
93. 32
98. 88
95.88
93:17
90.44
80.82
Yoart
Weest
100.0
100.0
96.44
70.41
Power
Weest Wwm
91.25 235
91.02
93. 98
933.77
89.37
99.00
95.00
94.000
99.000
83.00
aiXiv
Wiest
PPI
Wieat Wiom
94.67
100.0
93.94
100.0
93. 76
08.89
93.02
933.48
90.00
40.07
Table 30: Impact of pruning + RTLL
Dateset
Prune Percentage (%)
80
Clole
Wwm
Wicat
100.00
88.46
$2.78
96.57
83.11
73.43
85.08
81.20
79.62
68.76
Wheat
Waom
N8
Wwm
Wieet
94.35
90.77
91.77
92.68
85. 55
01.31
91.71
20.22
$5.10
62.44
Weest
Wamm
Power
Waom
Wasst
98.00
91.29
92.90
58.00
92.08
58 00
92.15
67. 00
91.96
Wasst
90.4
Wamm
100.00 00
10-01
12-12"
25-71"
3-02
94.57
98. 70
00
03.06
100.00
40.85
35-16"
12-17
22-10
Table 31: Impact of pruning + FTAL.
30

---

Published in Transactions on Machine Learning Research (03/2026)
Pruue Percenlage (%)
Dataset
20
80
C.cle
Weest
Wam
100.00
56.46
92.19
62.78
63. 53.11
62.83
61.20
79.09
73.44
79.62
USAi
Wiest
Wiest
94.85
02.08
01.31
91.71
86.10
Wwr
99.77
91.77
86, 66
99.22
82.44
Youst
Wiesi
100.00
30.40
86,
18
92.89
84.88
71.00
88.34
Power
Whest
Wum
80. 00
91.23
36-05
88.03
.36-00
88 40
43-00
87.70
62:90
82:
arXiv
Waom
11-27
25
99.15
9.40
.405
PPI
Wiest Wwm
100.00
04.67
92.62
48.07
02.26
41.05
00.87
91.99
26-17
90.51
Table 32: Impact of pruning + RTAL.
F.5
SEAL
Tables 33 39
present results for different robustness tests for the SEAL model.
Dataset
Fine Method
No FT
FTLL
RTLL
FTAL
RTAL
C.ele
Wital
USAir
Wheat
Whem
02.35
06.66
92. 46
08.81
03.05
01.47
03.08
01:79
88.00
92.49
Wheat
98
46
98
99.25
98
98.77
98.78
58.30 58.26
Youst
Whns
Wanm
87
96
06
38
87. 04
95.49
86.35
84.73
91.
96
Power
88.78
85 45.64
87.31 88.78 78
88.63
87.19
57.04
84:20
83
Table 33: Impact of model fine-tuning.
Purcentage (%)
40
00
80
Chelo
Wiest
$6.60
63.98
85. $5.60
$5.48
USAir
Weest
Wamm
96.66
89.95
95.61
99.31
92:24
95.81
85.08
91:40
86.25
81.06
NS
88.77
98.78
96
97.97
97.58
87.53
85.58
85.19
Yonst:
Wense Warm
90.04
87.
98. 53
98.27
97.
82.66
B6.06
83.37
Power
Waom
88.78
88.85
$4.68
87.98
76.88
$3.50
Table 34: Impact of model pruning.
Condition/ Datasot
C.cle
USAir
NS
Yoast
Belore
Weest
88.50
95.66
98.61
85.64
quantisation
Wom
84.27
92.35
98.77
96
88.78
After quantixation
84.34
80.08
80.32
67.48
76.37
87.61
Table 35: Impact of weight quantization.
31

---

Published in Transactions on Machine Learning Research (03/2026)
Prupe Porcentage (%)
Datwst
C.ale
Whast
86. 50
83.82
90.00
89.53
65.41
Wam
54.27
83.99
63.97
64.13
83:24
USAir
Weest
92.31
NB
Wiest
95.61
98.36
98.06
95.74
96.73
Warm
95.77
99.76
97.60
97.4
92.36
Youat
Wiest
07.11
96.88
96.38
96.37
02.76
Power
Whest
$0.64
87.
87. 08
86.20
68-21
Wwm
88. 63
67.
76.97
60.08
Table 36: Impact of pruning + FTLL.
Datwet
Percentage (%)
40
60
Ciale
Whest
50.
89-77
Waom
84.27
63.94
84.21
83.42
USAir
Wiest Whrm
95.66
98.17
95.
95.34
92.52
92.85
91.00
91.06
90.46
90.62
Whest Waom
08.02
91.05
Yonst
Whest Wim
97.06
97.11
07:17
96.88
B6.62
96.34
95.41 41
00:48
91:17
92.36
Whest Wwon
Table 37: Impact of pruning + RTLL.
(%)
20
40
60
80
Weest
USAir
Wiest Wamm
96.66
99.02
92.78
03.22
92.50
92.85
91.50
91.70
91:51
90.35
N8
Wiest
96.77
90.98
31.57
0.04
Yenrt
Weest Wwmm
97.06
98..39
98:44
96.27
0b.59
.14
85. 80
94:23
93.56
84.39
Wiest
98.78
66 32
86.21
19.40
J2-0T
Table 38: Impact of pruning + FTAL.
Dateset
Prune Percentage (%)
80
C.ale
84 50
8S
85.54
65.75
Warm
84.27
88.73
$8.80
83.73
82.76
USAir
Winst Warm
92.50
N8
98.81
98.
96. 822
95.34
9T.87
Wamm
98.77
03.60
42.97
20.32
5.03
Yoast
Wiest Wamm
57.08
96.93
02.69
92.99
92.92
Power
Wies Wamm
85.04
82.71
82.70
82.76
82.83
88.78
11-03
14:00
11-75
10-57
Table 39: Impact of pruning + RTAL.
G Performance of GENIE on Additional Datasets
We have conducted preliminary testing on additional datasets of varying sizes, i.c., ogbl-collab (Hu al. 2020), Wikipedia (Mahoney 2011 and Router (Spring al.] 2002). ogbl-collab is author collaboration
32

---

Published in Transactions on Machine Learning Research (03/2026)
network with 235,868 nodes and 1,285,465 edges. Wikipedia dataset has 4,777 nodes, 184,812 edges, and 40 attributes. Router is router-level Internet network dataset with 5,022 nodes and 6,258 edges.
Table shows Creat, Weest, and Wwm- We observe that GENIE could successfully watermark the model with minimal utility loss, which indicates that GENIE satisfies functionality preservation requirements on these datasets as well. We keep further testing (e.g., robustness tests, efficiency tests) of GENIE on these datasets as part of our future work.
SEAL
GCN
GraphSAGE
Dataset
Ctest
Weest
Wwm
Ctest
Whest
Wmrm
Ctest
Wiest
Wwmn
Router
95.68
95.86
96.22
96.75
96.53
95.23
92.85
96.27
95.44
ogbl-collab
95.56
95.17
99.92
96.39
100.00
95.71
96.94
100.00
95.79
Wikipedia 91.12
91.13
84.72
92.09
90.21
99.58
93.24
92.91
100.00
Table 40: Watermark verification performance (average 10 runs) of GENIE across 3 models and additional
datasets.
Baseline Model Performance
To facilitate a clearer assessment of the underlying utility of the GNN architectures used in this study, we provide a dedicated tabulation of the clean baseline performance (Crest) in Table 41 These values represent the Link Prediction AUC of the models (SEAL, GCN, GraphSAGE, and NeoGNN) trained using standard protocols without any watermark injection. This serves as the independent reference point for calculating the utility loss (Crest Wtest) discussed in Section 5.1.2.
Dataset
SEAL
GCN
GraphSAGE
NeoGNN
C.ele
87.84 + 0.46
88.97 0.44
86.76 1 0.68
89.03 1 0.71
USAir
98.19 + 0.25
90.02 + 0.52
92.44 + 0.35
95.81 + 0.81
NS
98.10 + 0.15
95.44 0.74
90.90 0.63
99.93 = 0.02
Yeast
97.07 + 0.21
93.64 = 0.40
89.12 = 0.43
97.78 = 0.57
Power
84.41 + 0.44
99.36 0.17
87.54 1.02
99.96 = 0.02
arXiv
98.14 + 0.14
99.31 + 0.04
99.62 + 0.01
99.92 + 0.01
PPI
89.63 + 0.12
95.08 0.04
94.03 0.09
97.43 + 0.16
Table 41: Clean baseline performance (Crest) of the GNN architectures Link Prediction tasks (AUC %). These values represent the model utility prior to watermark injection.
Extended Evaluation: Impact of Feature Heterophily
In this section, we address the impact of fcature heterophily on the GENIE framework. We first clarify the homophily characteristics of our primary datasets and then present comprehensive evaluation on specific heterophilic benchmarks to demonstrate the robustness of our watermarking scheme.
1.1 Homophily Ratios and Dataset Selection
Regarding the datascts used in our main evaluation (c.g., USAir, NS, Power, Router, C. clegans), we clarify that these are topology-only datasets lacking intrinsic node attributes. To enable GNN training, we gen- erated node features using node2vec. Since node2vec explicitly generates embeddings based on structural proximity, it inherently induces a high degree of feature homophily (i.c., connected nodes possess similar em- beddings by design). Furthermore, since these datasets lack ground-truth node labels, standard label-basee homophily metrics are inapplicable. We therefore treat these datasets inherently homophilie.
33

---

Published in Transactions on Machine Learning Research (03/2026)
To strictly quantify this relationship despite the circularity of structure-derived features, computed the Feature Homophily Score (K) as formally defined by Zhu et. al. (Zhu et al. 2024). The metric K represents the average mean-centered cosine similarity of connected nodes, where K > 0 indicates homophily. As shown all original datasets exhibit positive scores, confirming their homophílic nature.
in Table 42
Datasct
Homophily Score (K)
Interpretation
Power
0.5587
Strongly Homophilic
arXiv
0.4988
Strongly Homophilic
PPT
0.2266
Homophilic
NS
0.1895
Homophilic
Yeast
0.1593
Homophilic
USAir
0.0229
Weakly Homophilic
C. ele
0.0109
Weakly Homophilic
Table 42: Feature Homophily Scores (K) for the original datasets used in the main evaluation. indicates feature homophily.
To rigorously evaluate GENIE under heterophily, we expanded our evaluation to include seven dalasets widely recognized in the literature for their heterophilic properties: Chameleon (Rozemberczki et al. (0211))
Squirrel (Rozemberczki et al. 2021b), Roman-empire (Platonov et al.) 2023). Amazon-ratings (Platonov
et al. 2023), Minesweeper (Platonov et al., 2023). Tolokers (Platonov et al. 2023), Questions
Platonoov et al.) 2023), and E-comm (Shchur et al. 2018). These datasets possess intrinsic node features (e.g., text, ratings) independent of the graph structure, providing a suitable testbed for heterophily.
GENIE remains robust in heterophilic environments due to the stark contrast between the natural data distribution and our injected watermark signal:
Background Distribution: In heterophilic graphs, the general data distribution follows the rule that connected nodes typically possess dissimilar features.
Injected Signal: The GENIE trigger creates specific set of links between nodes that share the eract same secret feature vector w.
Result:
The watermark introduces a pattern of perfect feature homophily that stands in contrast to the predominantly heterophilic structure of the graph. Because this injected signal deviates from the general data distribution, it creates distinctive pattern that is straightforward for the model lo isolate and memorize during the fine-tuning phase.
Challenges and Architecture. The primary challenge in this sctting is Utility Preservation. Standard GNNs often struggle with heterophily. If model is strictly optimized penalize feature similarity maximize heterophilic performance, it might resist learning the homophilic watermark pattern. To address this, we utilized GraphSAGE encoder with an MLP decoder for these experiments, architecture known to effectively decouple ego-embeddings from neighbor-embedding in heterophilic tasks.
1.2 Empirical Results
Table 43 summarizes the performance of GENIE on these benchmarks. The results confirm our hypothesis: GENIE achieves near-perfect Watermark Accuracy (2 99%) across all datasets regardless of the background heterophily. Furthermore, the Utility Loss negligible (typically 1%). Notably, datascts like Amazon- ratings and Questions, the watermarked model marginally outperforms the clean baseline, suggesting the watermark may provide regularization effect.
34

---

Published in Transactions on Machine Learning Research (03/2026)
Dataset
Creat
Wtest
Wwr
Chameleon
99.16
99.14
100.00
Squirrel
99.41
99.37
100.00
E-comm
98.49
97.49
100.00
Amazon-ratings
50.44
50.52
100.00
Minesweeper 88.81
88.15
100.00
Tolokers
97.53
96.58
100.00
Questions
51.36
51.60
99.22
Table 43: Performance of GENIE on heterophilic graph benchmarks using GraphSAGE. The table compares the Clean Test. AUC (Ctest), Watermarked Test AUC (Wesst) and Watermark Verification Accuracy (Wwm).
1.3 Quantitative Analysis of Heterophily
To quantitatively characterize the heterophily of the new benchmarks, we report the Edge Homophily (Hedge) and Adjusted Homophily (Hadt) scores. Unlike our initial topology-only datasets, these benchmarks pos- ground-truth node labels, allowing us to utilize standard label-based metrics widely adopted in GNN
literalure Platonov et al. 2023
Edge Homophily (Hledge): Measures the fraction of edges connecting nodes of the same class. It is defined as:
Hedge I[(u, v) E E: yu =yo
99)
3
where & is the set of edges and Yur Ye denote the class labels of nodes a and Low values indicate that neighbors likely belong to different classes.
Adjusted Homophily (Hadj): Corrects Hedge to account for the number of classes and class imbalance. It is defined as:
Hadj Hedge Ee k== D -x=1 D2
(10)
where C is the number of classos, and Dr is the empirical degree proportion of class k. Values of Hadj 2o O indicate random connectivity, while Hadj < 0 indicates strong heterophily.
As shown in Table 44 datasets such as Tolokers and Questions exhibit negative adjusted homophily, con- firming their strong heterophilic structure. Chameleon and Squirrel show low adjusted homophily (* 0.03), indicating connectivity largely independent node labels. Despite these challenging structural properties, GENIE maintains high verification success, validating its robustness.
Datasct
Hedge
Hadj
Interpretation
Questions
0.8396
1.7706
Strong Heterophily
Tolokers
0.5945
-0.1883
Strong Heterophily
Minesweeper
0.6828
0.0087
Heterophilic
Squirrel
0.2221
0.0277
Heterophilic
Chameleon
0.2299
0.0353
Heterophilic
Amazon-ratings
0.3804
0.1505
Weak Homophily
E-comm
0.7772
0.7186
Homophilic
Table 44: Label Homophily Scores for the heterophilic benchmarks.
35

---

Published in Transactions on Machine Learning Research (03/2026)
J Notations used in our paper
In this section, we establish the mathematical conventions and terminology utilized throughout the manuscript. To assist the reader in navigating the technical descriptions of our watermarking framework and its evaluation, we provide a comprehensive glossary of symbols in Table 45 The table is organized to distinguish between general graph theoretic notations, specific entities within our threat model, and the performance metries used quantify utility and watermark verification success.
Notation
Description
First Introduced
(V.E)
graph
V
Set of nodes of g
Set of edges of
A
Adjacency matrix of G
0
Owner
A
Adversary
J
Judge
M
Generic GNN model
Mown
O's trained model
C
Clean Noonwwatermarke) model Watermarked model
W
Made
A's model Generic graph dataset
D
Der
Training dataset
Drest
Testing dataset
D umm
Watermarking dataset (secret)
Cum
AUC score of C on Dum
Wwm
AUC score of W on D Pum
Weast
AUC score of W Drest
Creat AUC score of C on Drest
Table 45: A summary of the notations used in our work.
K Algorithms for GENIE
In this scction, we outline the algorithms for both nodd-represcntttton and subgraph-based link prediction methods using GENIE. Algorithm outlines the watermark embedding algorithm for node-representation based link prediction methods, Algorithm link prediction methods, Algorithm 3 outlines the DWT method and finally Algorithm f outlines the final ownership demonstraion.
2 outlines the watermark embedding algorithm for subgraph- based
36

---

Published in Transactions on Machine Learning Research (03/2026)
Algorithm Embedding Watermark using GENTE for Node Representation-basde methods
Require: Graph 9 (V,E), Node features X, Clean edges Eirains Model fa, Budget p, Dimension d Watermarked GNN model fø-
Ensure:
1: 1. Watermark Generation
2: Generate secret watermark vector ~ (N E IR
3: Randomly sample node subset Vum C V based on budget P
Construct trigger edge set &wm by pairing all nodes Vum and removing all existing edges Feature Injection
for each node Vum do
X, f-s {Replace features of trigger nodes}
8: end for
3. Watermark Embedding
10: Initialize model parameters
11: while not converged do
12: Sample batch of clean edges Belean C Etrain
13: Compute clean loss Lelean on Belean
14: Update 8 <- VoooCclnn
15:
Sample batch of trigger edges Bum C Ewm
16:
Compute watermark loss Lum on Bun
17:
Update <- f - v) (from))
18: end while
19: return se-
Algorithm Embedding Watermark using GENTE for Subgraph-basod methods
Require: Training links Eraai (Positives & Negatives), Graph G, Node features X, Budget p
Ensure: Watermarkod SEAL model fo-
1. Watermark Generation
Generate secret watermark vector Rd
2. Subgraph Crcation
4: Extract enclosing subgraphs for all training links: Dall + {Extract(u, v) (u, v) E Etrain]
5: 3. Trigger Set Selection
6: Randomly select a subset subgraphs Dum C Dau based on budget p Trigger Modification (Features & Labels)
for each subgraph 9: D um do Replace all node features in 9i with 10: Flip label: 1 y/
11: end for
12: 5. Dataset Splitting
13: Remove trigger samples from training set: Derain t Daul \ D um
14: Watermark Embedding
15: Initialize model parameters 0
16: while not converged do
17: Sample batch of clean subgraphs Belean C Dirain
18: Compute clean loss Calann on Balann
19:
Update 0 - 0 - 1/ (fCeean))
20:
Sample batch of trigger subgraphs Bum C D wm
21:
Compute watermark loss Luo on Bur
22:
Update 0 + v/ (Lum)
end while
24:
return fg-
37

---

Published in Transactions on Machine Learning Research (03/2026)
Algorithm Dynamic Watermark Thresholding (DWT)
Require: Clean scores Se, Watermark scores Sw, Sample size n, Confidence
Ensure: Threshold t*
1: m + [--In11-))) (Minimum blocks for confidence 7
2: for & E {c,w] do
3: ō f- std(Sx)
4: ha 1.06 oF |Sx| (Silverman's Rule)
5: P. < KDE ha) (Estimate Distribution)
end for
7: for j = 1 to m do
Sample blocks x P. and X Pe size n
9: end for
10: return s.t. Vj: max(x!") < l < min(X(
Algorithm 4 GENIE Ownership Demonstration
Require: Owner O, Adversary A, Judge J, Blockchain Ensure: Ownership Verdict V (Confirmed, Denied}
1: Phase 1: Model Registration
O Requests registration with graph
3: J: Generates secret watermark dataset Dum from G
Writes cryptographic hash ((D... B
5: O: Embeds Dwn into model
6: Phase 2: Dispute Resolution
7: O + J: Submits Dwm, Mown and claims ownership
8: A J: Submits suspect model Medv
9: J: Retrieves hash hatored Re)d(BB)
10: if ((Dum) # Ratored then
11: return Denied (Hash Mismatch Evidence Tampered)
12: end
J: Calculates threshold using DWT procedure
14: J: Computes watermark score t- Eval( Dwm)
If >>>> then
16: return Confirmed
else
18: return Denied
19: end
38


Reviews:
[{"review_id": "bdy2dQtaml", "reviewer": "Reviewer_pwuv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces GENIE, a watermarking framework for Graph Neural Networks (GNNs) trained for link prediction (LP). The core contribution is a watermarking method that embeds a latent signature into LP models that can be revealed using a secret trigger, while preserving LP task performance. GENIE supports both node-representation-based LP methods (e.g., GCN, GraphSAGE, NeoGNN) and subgraph-based LP methods (e.g., SEAL). GENIE constructs a watermark by modifying a small, secret subset of nodes or subgraphs by inverting edges and replacing the node features with a fixed vector. The watermark is embedded in the model using a two-phase training procedure that alternates between clean and watermarked updates in each training epoch. For ownership verification, the paper proposes Dynamic Watermark Thresholding (DWT), a statistically motivated heuristic that calibrates watermark detection threshold along with a confidence guarantee. Robustness is tested against black-box, white-box, and combined attacks, with failure defined in terms of both watermark removal and performance degradation.\n\nStrengths:\n- The work presents the first watermarking framework explicitly designed for GNN link prediction. The method supports general node-based and subgraph-based models.\n- The experiments cover several architectures, real-world datasets, and watermark removal attacks. The results are reasonably convincing.\n- The proposed DWT procedure provides a theoretically motivated heuristic for choosing watermark verification thresholds.\n\nWeaknesses:\n- The presentation makes the method hard to follow, particularly in the verification and thresholding stages. There are no explicit algorithmic descriptions for watermark embedding, threshold calibration, or verification. The presentation of the statistical arguments is dense.\n- Notation is occasionally overloaded (e.g., using the same variables for models and their scalar watermark scores). Variables and objects are introduced without proper definitions. (E.g., $\\mathcal{F}_{wm}$ is a function from what to what? What are the dimensions of the node features?)\n- It seems that there are implicit theoretical assumptions and computational overhead for DWT, which would benefit from further clarification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The experimental evidence supports the main claims of the paper regarding GENIE. The proposed DWT procedure is presented along with a clear statistical rationale. Some assumptions underlying the statistical model (e.g., approximate independence of verification trials) appear heuristic rather than rigorously justified. However, those assumptions seem to be standard in the watermarking community, and are empirically supported by the differences observed between clean and watermarked models.", "audience_yn": "Yes", "audience_explanation": "The paper addresses a practically relevant and theoretically interesting problem at the intersection of graph learning and security. Researchers and practitioners working on GNNs, link prediction, and deployed ML systems would be interested in the findings.", "requested_changes": "Readability and notation\n\n- Include explicit algorithm boxes for the main procedures: watermark embedding, threshold calibration (DWT), and ownership verification. Each algorithm should clearly list inputs, steps, and outputs. Offline calibration and online verification should be clearly separated.\n- Clarify and tighten notation, particularly in the statistical testing section. The paper occasionally conflates sets of models (e.g., $\\mathcal{W}, \\mathcal{C}$) with their scalar watermark scores (e.g., AUC on $D_{\\mathrm{wm}}$). Explicitly distinguish between models, scores, and score distributions.\n- Add a table that lists key variables (e.g., $\\mathcal{W}, \\mathcal{C}, D_{\\mathrm{wm}}, W_{\\mathrm{wm}}, C_{\\mathrm{wm}}$) and abbreviations (e.g., DWT), along with references to their definitions.\n\nTheoretical assumptions\n- Please clarify how the Bernoulli/binomial model used in Theorem 1 relates to the practical verification procedure, which involves AUC scores computed on correlated LP queries and KDE-based resampling. Explicitly state that the confidence guarantee is heuristic under approximate independence if that is the case. Be upfront about the limitations introduced by those assumptions, and contextualize them as standard assumptions/simplifications in the watermarking community if that is the case.\n\nComputational costs and calibration overhead\n- DWT seems to require training multiple clean and watermarked reference models to estimate score distributions. If that is the case, please state this requirement explicitly, report how many reference models are typically needed, and clarify that this calibration is a one-time, offline cost. Providing an estimate of the additional computational overhead would help readers assess practical and computational costs.", "broader_impact_concerns": "The paper includes a Broader Impact Statement that appropriately acknowledges the dual-use nature of watermarking and backdoor-based techniques. No further ethical concerns are identified beyond those discussed by the authors.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9juWt9saG4", "reviewer": "Reviewer_7pcm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes GENIE, which is the first general watermarking framework designed specifically for GNNs performing link prediction, a task for which existing watermarking approaches do not apply. The propose method embeds a hidden backdoor into the model by generating a secret watermark dataset: it modifies selected nodes or subgraphs by inverting their link labels and replacing their features with a secret watermark vector. The model is trained in two phases, first on normal data to preserve utility, then on watermark data so that it reliably flips predictions on trigger inputs while remaining indistinguishable from a clean model on ordinary queries.\nTo verify ownership, GENIE introduces Dynamic Watermark Thresholding (DWT), which estimates the distribution of watermark-trigger outputs using kernel density estimation and selects a threshold ensuring statistically bounded misclassification probability.\nExtensive experiments across multiple GNN architectures, datasets, and attack types show that GENIE preserves model performance, achieves near-perfect watermark detection, and remains robust against model extraction, fine-tuning, and adaptive attacks.", "claims_and_evidence_yn": "No", "claims_explanation": "The reviewer considers this to be the most significant issue of the paper. In real-world MLaaS (Machine Learning as a Service), the reviewer believes that use cases in which the type of GNN targeted in this paper, namely, transductive GNNs, are directly provided as a service are extremely limited and not common. Although such cases are theoretically possible, the reviewer is not aware of any concrete examples where they are actually deployed as services. Transductive learning assumes that the “set of nodes is fixed,” meaning that the nodes appearing during testing are exactly the same as those seen during training. Under this assumption, the system cannot handle unseen nodes, which seems fundamentally incompatible with MLaaS, where APIs are exposed to external users. A transductive GNN is therefore imagined to be a model “closed within an internal system.” For example, one might imagine internal use cases such as knowledge-graph completion within a company, but such systems are generally restricted to internal use and are unlikely to be offered externally as APIs. Without concrete examples where such a setting arises in MLaaS, it is difficult for the significance of the proposed technique in the paper to be conveyed convincingly.", "audience_yn": "Yes", "audience_explanation": "The problem setting is theoretically possible, and having watermarking techniques available for link prediction itself would likely attract interest from those working toward the practical deployment of GNNs in society.", "requested_changes": "First, as noted above, it is necessary to provide a convincing argument that MLaaS based on GNNs—especially in the transductive setting—is realistically plausible.\n\nThe following points are minor, but I would like them to be revised:\n1. There is a reference to the loss L_{wm} corresponding to D_{wm},  in Section 4.2, but the concrete definition of this loss appears only in Section B.1.2, and it remains undefined/unknown in the main text. Since the design of the loss function is an important issue, please describe it explicitly in the main body of the paper.\n\n2. Are there differences in the threat model between the transductive and inductive settings? If there are, please make them explicit; if not, please state that clearly. My impression is that the difference between transductive and inductive settings is substantial, because the scope of data observable to the adversary changes.", "broader_impact_concerns": "Since this is research related to security protection, there is always a possibility that attackers may use the results as a reference for evasion, but this is inherently unavoidable. There is no particular concern unique to this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gNzVXMldul", "reviewer": "Reviewer_NS4E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces GENIE, a watermarking framework tailored for GNN-based link prediction, addressing a gap left by prior GNN watermarking work that focused only on node and graph classification. GENIE embeds a backdoor trigger via a secret watermark vector and modified links/subgraphs, using a two-phase training procedure that maintains model utility while enabling reliable ownership verification. To make verification statistically sound and efficient, the authors propose Dynamic Watermark Thresholding (DWT), a KDE-based method requiring only a few clean and watermarked models. Experiments across multiple datasets, architectures, and 21 removal attacks demonstrate strong robustness, though the experiments raise questions about generalisability to more expressive GNNs and heterophilous datasets.\n\nKey Strengths:\n\n(i) Addresses a real gap in the literature by focusing on watermarking for link prediction rather than node/graph classification.\n(ii) Extensive empirical evaluation to show method's efficacy and robustness to attacks.\n(iii) The method seems to be practical on a real-world scale because the watermarking rates reduce with graph size, making the method scalable.\n\nKey Weaknesses:\n\nA few clarifying questions: \n(i) What technically stops this method from generalising to node classification and graph classification tasks as well? If it can generalise, then draw an analogy to show how the approach will work for these tasks.\n(ii) Is there any reason why the experiments are not conducted with more expressive and better-performing GNNs such as GIN and GAT? Do attention mechanisms, etc., pose any challenge to GENIE? Show empirically.\n(iii) The authors must share the homophily ratios of the datasets, where applicable. \n(iv) How does the method work in the face of heterophily? Are there any challenges to keep in mind when dealing with watermarking for link prediction in the case of heterophily?\n\nSome edits to be made for more clarity: \n(i) The model performance should be added in 5.1.2 or in the appendix and pointed out in this section. It is understandable that the C_{test} may indicate towards model performance, but having it in one place may make reading easy.\n(ii) In section 6.3, Table 16 has numbers computed with what values of the alpha_{nr}/alpha_{sg} parameter?\n(iii) Table 5: Degradation in W_{test} compared to what? The original pre-trained performance should be added in this table, I assume.", "claims_and_evidence_yn": "No", "claims_explanation": "The claims are largely well-supported by empirical evidence; however, evaluating the method on more expressive GNN architectures and on heterophilous datasets would help more concretely establish the scope and efficacy of GENIE.", "audience_yn": "Yes", "audience_explanation": "The paper has proposed a watermarking strategy for GNNs trained for link prediction. This problem has not been widely studied in the concerned literature. The proposed approach may be of interest.", "requested_changes": "(a) critical to securing your recommendation for acceptance: Please address clarifying questions in weaknesses.\n(b) would simply strengthen the work in your view: Make edits as suggested in weaknesses.", "broader_impact_concerns": "None", "additional_comments": "None", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)