COPYCOP: Ownership Verification for Graph Neural Networks

# CopyCop: Ownership Verification for Graph Neural Networks
Source: [https://arxiv.org/html/2605.05360](https://arxiv.org/html/2605.05360)
Rahul Nandakumar McCombs School of Business University of Texas at Austin Austin, TX rahul\.nandakumar@utexas\.edu &Deepayan Chakrabarti McCombs School of Business University of Texas at Austin Austin, TX deepay@utexas\.edu

###### Abstract

Given two GNNs that output node embeddings, how can we determine if they were trained independently? An adversary could have trained one GNN specifically to mimic the other GNN’s embeddings\. To obscure this relationship between the GNNs, the adversarial GNN might then transform its output embeddings\. The two GNNs could have different architectures, weights, and embedding dimensions, and the adversary can transform the embeddings\. Despite these stringent conditions, our algorithm \(namedCopyCop\) can identify such copycat GNNs, unlike existing watermarking and fingerprinting methods\. We also provide theoretical guarantees forCopyCop\. Finally, experiments on 14 datasets and 5 GNN architectures demonstrate thatCopyCopis accurate and robust against a broad class of adversarial attacks and transformations\. Code is available at:[https://anonymous\.4open\.science/r/CopyCop\-Graph\-Ownership\-Verification\-8143/README\.md](https://anonymous.4open.science/r/CopyCop-Graph-Ownership-Verification-8143/README.md)

## 1Introduction

Graph Neural Networks \(GNNs\) are increasingly deployed as reusable embedding models, often exposed through Embeddings\-as\-a\-Service\[peng\_are\_2023\]\. In this setting, users query a model with graphs and obtain node embeddings that can be reused for downstream tasks\. While this enables flexible reuse, it also raises a fundamental question:*can we determine whether another model was independently trained, or derived from a deployed GNN?*

An adversary can train a surrogate GNN to mimic a victim model’s embeddings by querying the victim on many graphs and learning from the resulting input\-output pairs\. The adversary can then apply transformations such as rotation, scaling, permutation, or changes in embedding dimension\. These transformations may substantially change the representation while preserving downstream performance, making the surrogate appear unrelated to the victim\. Furthermore, the surrogate GNN’s architecture can be different from the victim GNN\. Thus, given a victim GNN that outputs embeddings, our goal is to identify surrogate GNNs despite changes in architecture, parameters, embedding dimension, or output transformation\.

Existing surrogate detection methods fall into two categories: watermarks and fingerprints\. Watermarking methods modify training so that the model produces distinctive outputs on special graphs\[zhao\_watermarking\_2021,xu\_watermarking\_2023,pregip\]\. However, an adversary can bypass such signals through model extraction: by querying the victim on ordinary graphs and training only on the resulting input\-output pairs, the surrogate need not reproduce the special watermarked behavior\[lukas\_sok\_2021\]\.

Fingerprinting methods avoid modifying the victim model and instead rely on intrinsic properties of its outputs\. For GNNs that output embeddings, existing methods typically compare the victim and candidate embeddings directly\[grove\]\. However, simple transformations such as rotation or changes in embedding dimension can make embeddings appear different to a classifier while preserving downstream accuracy\. As a result, existing embedding\-based fingerprints are vulnerable to cosmetic changes in the surrogate representation\.

![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/overview.png)Figure 1:Overview ofCopyCop\.:Under the embeddings\-as\-a\-service model, the victim GNN provides embeddings for input graphs, which can then be used for downstream tasks\. An adversary can train a surrogate GNN to mimic these embeddings and then transform them, achieving similar accuracy while obscuring the surrogate relationship\.CopyCopdetects surrogate models under such transformations without watermarking the victim GNN\.### 1\.1Our Contributions

We proposeCopyCop, a fingerprinting method for GNNs that is robust to a wide range of adversarial transformations, including rotations, scaling, and changes in embedding dimension\. Our method is architecture\-agnostic: the victim and surrogate GNNs may use different architectures, parameters, and embedding dimensions\. Moreover, our fingerprints are randomized and can be regenerated at any time, so leaked fingerprints do not permanently compromise the method\. To our knowledge,*CopyCopis the first fingerprinting method for GNN embeddings that works under a broad class of transformations, across GNN architectures, and at any time\.*

The key idea is to use stationary points of the embedding function as fingerprints\. A node’s embedding is a function of the graph structure and node features\. Since an adversary may transform the embedding space, the fingerprint must be invariant to such transformations\. We prove that stationary points of the embedding function have this invariance property\. We show how to sample stationary points from the victim GNNMMand test whether these points are also stationary for a candidate GNNZZ\. This test lets us determine, with high confidence, whetherZZis independently trained or a surrogate ofMM\.

We prove thatCopyCopdetects surrogate models under reasonable conditions, irrespective of GNN architecture or embedding dimension\. Empirically, we evaluateCopyCopon 14 datasets and 5 popular GNN architectures\. The results show thatCopyCopis robust to model extraction, pruning, fine\-tuning, and a broad range of embedding transformations\.

The rest of the paper is organized as follows\. We discuss related work in Section[2](https://arxiv.org/html/2605.05360#S2)\. In Section[3](https://arxiv.org/html/2605.05360#S3), we present our proposed method and prove its robustness against embedding transformations\. We empirically validate our approach in Section[4](https://arxiv.org/html/2605.05360#S4), and conclude in Section[5](https://arxiv.org/html/2605.05360#S5)\. All proofs and extra experiments are deferred to the Appendix\.

## 2Related Work

Our work on ownership verification is related to the broader area of adversarial attacks to infer the graph’s structure and properties\[zhang\_gnnguard\_2020,deng2022garnet,wang\_group\_2022,zhang\_inference\_2022\]\. Robustness against backdoor attacks is also related to trustworthy AI\[dai\_comprehensive\_2024\]and integrity verification\[8953972,kuttichira2022verification,wang2023publiccheck\], and query\-based schemes for GNNs in MLaaS\[wu2024securing\]\. Here, we present an overview of the work that is most closely related to us\.

Model stealing attacks and defenses:Model stealing attacks and defenses have been studied for images\[papernot\_practical\_2017\]and text\[krishna\_thieves\_2020\], among others\. One defense is to perturb the model’s layers\[lee\_defending\_2019\], but this fails to counter model extraction attacks\[juuti\_prada\_2019\]\. Other defenses detect model extraction attacks based on their query patterns\[juuti\_prada\_2019\]\. However, we assume that the victim GNN is public, or the adversarial queries can be successfully hidden\. Similar attacks have been proposed for GNNs\[defazio\_adversarial\_2019,shen\_model\_2022\], but\[lukas\_sok\_2021\]show that current defenses are insufficient\. A related but distinct problem is*integrity verification*: detecting whether a deployed model has been tampered with after deployment\[8953972,kuttichira2022verification,wang2023publiccheck\]\. However, we focus on*ownership*verification of a separately trained surrogate that may differ entirely in architecture and weights\.

Watermarks:Watermarks can be embedded in the victim model’s weights by regularizing the model parameters during training\[uchida\_embedding\_2017\]\. Other approaches embed backdoors, training the model to return improbable outputs for special inputs\[adi\_turning\_2018,darvish\_rouhani\_deepsigns\_2019,kwon\_blindnet\_2022,zhao\_recipe\_2023\]\. Backdoor\-based watermarks have also been proposed for GNNs\[zhao\_watermarking\_2021,xu\_watermarking\_2023,pregip\]\. However, watermarks can degrade performance\[grove\], and are susceptible to model extraction attacks\[lukas\_sok\_2021\]\.

Fingerprints:Unlike watermarks, fingerprints do not modify the victim model\. Fingerprints can be based on model weights\[chen\_deepmarks\_2019\], special inputs for which some surrogate and independent models give very different outputs\[lukas\_deep\_2021\], pairs of samples along special vectors that straddle decision boundaries\[peng\_fingerprinting\_2022\], or confidence levels of surrogate models\[maini\_dataset\_2021\]\. For GNNs, existing methods rely on the similarity of embeddings between victim and surrogate models\[grove\]\. This approach applies only when the victim and surrogate GNNs have the same embedding dimension, limiting its generality\. In contrast, our approach works for surrogates with any GNN architecture or embedding dimension\.

## 3Proposed Method

A graph is a tuple\(G,X\)\(G,X\)whereG=\(V,E\)G=\(V,E\)hasn:=\|V\|n:=\|V\|nodes, each with features𝒙i∈ℝD\{\\bm\{x\}\}\_\{i\}\\in\\mathbb\{R\}^\{D\}, andX=\(𝒙1,…,𝒙n\)X=\(\{\\bm\{x\}\}\_\{1\},\\ldots,\{\\bm\{x\}\}\_\{n\}\)\. Let𝒟\\mathcal\{D\}denote the data distribution over feasible pairs\(G,X\)\(G,X\)\. Add\-dimensional GNNHHis a function𝒉:\(G,X\)→ℝd×n\{\\bm\{h\}\}:\(G,X\)\\to\\mathbb\{R\}^\{d\\times n\}, whoseit​hi^\{th\}column𝒉i​\(G,X;H\)∈ℝd\{\\bm\{h\}\}\_\{i\}\(G,X;H\)\\in\\mathbb\{R\}^\{d\}\(or𝒉i​\(X\)\{\\bm\{h\}\}\_\{i\}\(X\)when context is clear\) is theembeddingof nodeii\. We are given add\-dimensionalvictimGNNMMwhose embeddings have the following property\.

###### Assumption 3\.1\(Embedding properties\)\.

𝒉i​\(X\)\{\\bm\{h\}\}\_\{i\}\(X\)is twice\-differentiable with bounded Hessian, and there exist constantsα¯M\\underline\{\\alpha\}\_\{M\}andα¯M\\overline\{\\alpha\}\_\{M\}such that0<α¯M≤‖𝒉i‖≤α¯M0<\\underline\{\\alpha\}\_\{M\}\\leq\\\|\{\\bm\{h\}\}\_\{i\}\\\|\\leq\\overline\{\\alpha\}\_\{M\}for all feasibleGG,XX, andii\.

Next, we see ad′d^\{\\prime\}\-dimensional GNN modelZZ, possibly using a different architecture and dimension thanMM\. We can queryZZwith a few graphs and observe its outputs, but we have no access toZZ’s internals\. Our goal is todetermine whether GNNZZis an independently trained model or a surrogate of the victim GNNMM\.We define a surrogate model as follows\.

###### Definition 3\.2\(Surrogate model\)\.

Ad′d^\{\\prime\}\-dimensional GNNM′M^\{\\prime\}, with embeddings𝒉i′:=𝒉i​\(G,X;M′\)∈ℝd′\{\\bm\{h\}\}\_\{i\}^\{\\prime\}:=\{\\bm\{h\}\}\_\{i\}\(G,X;M^\{\\prime\}\)\\in\\mathbb\{R\}^\{d^\{\\prime\}\}, is a surrogate of GNNMMifthere existfunctionsϕ:ℝd→ℝd′\\phi:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{d^\{\\prime\}\}and𝒉^:\(G,X\)→ℝd×n\{\\hat\{\\bm\{h\}\}\}:\(G,X\)\\to\\mathbb\{R\}^\{d\\times n\}such that

supG,X,i\\displaystyle\\sup\_\{G,X,i\}‖𝒉^i​\(G,X\)−𝒉i​\(G,X;M\)‖≤ϵ,\\displaystyle\\\|\{\\hat\{\\bm\{h\}\}\}\_\{i\}\(G,X\)\-\{\\bm\{h\}\}\_\{i\}\(G,X;M\)\\\|\\leq\\epsilon,𝒉i′\\displaystyle\{\\bm\{h\}\}\_\{i\}^\{\\prime\}=ϕ​\(𝒉^i\),\\displaystyle=\\phi\\left\(\{\\hat\{\\bm\{h\}\}\}\_\{i\}\\right\),\(1\)for every graph\(G,X\)\(G,X\)that is feasible or is in aδ\\delta\-neighborhood of a feasible graph \(ϵ\\epsilonandδ\\deltaare small positive numbers specified later\)\.

For intuition, the adversary can query the victim modelMMon graphs\(G,X\)\(G,X\), collect the resulting embeddings𝒉i​\(G,X;M\)\{\\bm\{h\}\}\_\{i\}\(G,X;M\)for all nodes, and train a GNN whose embeddings𝒉^i\\hat\{\{\\bm\{h\}\}\}\_\{i\}approximate𝒉i\{\\bm\{h\}\}\_\{i\}\. The adversary may then apply an additional transformation layer that outputsϕ​\(𝒉^i\)\\phi\(\\hat\{\{\\bm\{h\}\}\}\_\{i\}\)\.

Alternatively, the adversary can trainM′M^\{\\prime\}end\-to\-end using\(G,X\)\(G,X\)as input andϕ​\(𝒉i\)\\phi\(\{\\bm\{h\}\}\_\{i\}\)as the target output\. Even though the adversary never explicitly constructs an intermediate representation𝒉^i\\hat\{\{\\bm\{h\}\}\}\_\{i\}, it is still useful to characterize the connection between𝒉i\{\\bm\{h\}\}\_\{i\}and𝒉i′\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\.

In both cases, the victim and surrogate models output embeddings𝒉i∈ℝd\{\\bm\{h\}\}\_\{i\}\\in\\mathbb\{R\}^\{d\}and𝒉i′∈ℝd′\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\\in\\mathbb\{R\}^\{d^\{\\prime\}\}, respectively, and our algorithm relies only on these outputs\. The link between the two is given by the \(unobserved\)𝒉^i\\hat\{\{\\bm\{h\}\}\}\_\{i\}andϕ​\(⋅\)\\phi\(\\cdot\)introduced in Definition[3\.2](https://arxiv.org/html/2605.05360#A2.EGx1)\. Their existence is used solely in our analysis\.

Next, we motivate our proposed method on the special case of no reconstruction error \(ϵ=0\\epsilon=0\) before discussing the general case\.

### 3\.1The Perfect Reconstruction Case

Here,𝒉^i=𝒉i\{\\hat\{\\bm\{h\}\}\}\_\{i\}=\{\\bm\{h\}\}\_\{i\}, soM′M^\{\\prime\}outputs embeddings𝒉i′=ϕ​\(𝒉i\)\{\\bm\{h\}\}\_\{i\}^\{\\prime\}=\\phi\(\{\\bm\{h\}\}\_\{i\}\)\. Not all choices ofϕ​\(⋅\)\\phi\(\\cdot\)are realistic\. For example,ϕ​\(𝒉\)=𝟎\\phi\(\{\\bm\{h\}\}\)=\\bm\{0\}would lead to useless embeddings\. More generally, ifϕ​\(𝒉1\)=ϕ​\(𝒉2\)\\phi\(\{\\bm\{h\}\}\_\{1\}\)=\\phi\(\{\\bm\{h\}\}\_\{2\}\)for𝒉1≠𝒉2\{\\bm\{h\}\}\_\{1\}\\neq\{\\bm\{h\}\}\_\{2\}, thenϕ​\(⋅\)\\phi\(\\cdot\)loses information\. This can hurt performance on downstream tasks, so the adversary will avoid such aϕ​\(⋅\)\\phi\(\\cdot\)\.

###### Assumption 3\.4\(Local invertibility\)\.

The transformationϕ​\(⋅\)\\phi\(\\cdot\)is differentiable and locally invertible:

∇𝒘ϕ\|𝒉\\displaystyle\\left\.\\nabla\_\{\{\\bm\{w\}\}\}\\phi\\right\|\_\{\\bm\{h\}\}\\;:=limt→0ϕ​\(𝒉\+t​𝒘\)−ϕ​\(𝒉\)t≠0\\displaystyle:=\\;\\lim\_\{t\\to 0\}\\frac\{\\phi\(\{\\bm\{h\}\}\+t\{\\bm\{w\}\}\)\-\\phi\(\{\\bm\{h\}\}\)\}\{t\}\\;\\neq\\;\\bm\{0\}∀𝒉∈ℝd,𝒘∈ℝd,‖𝒘‖=1\.\\displaystyle\\forall\{\\bm\{h\}\}\\in\\mathbb\{R\}^\{d\},\{\\bm\{w\}\}\\in\\mathbb\{R\}^\{d\},\\\|\{\\bm\{w\}\}\\\|=1\.\(2\)

Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)ensures thatϕ​\(𝒉1\)≠ϕ​\(𝒉2\)\\phi\(\{\\bm\{h\}\}\_\{1\}\)\\neq\\phi\(\{\\bm\{h\}\}\_\{2\}\)for any two close embeddings𝒉1≠𝒉2\{\\bm\{h\}\}\_\{1\}\\neq\{\\bm\{h\}\}\_\{2\}\. The assumption holds for many intuitive transformations, such as rotation, non\-zero scaling, projection to a higher dimension, and translation, and for any composition of such functions \(Lemma[A\.2](https://arxiv.org/html/2605.05360#A1.Thmtheorem2)in the Appendix\)\. Note that projecting to a lower dimension loses information, so the adversary will avoidd′<dd^\{\\prime\}<d\.

We need a fingerprint that is invariant under any transformation satisfying Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\. We will show that this strong requirement is met by the stationary points of𝒉i​\(X\)\{\\bm\{h\}\}\_\{i\}\(X\), as defined below\.

###### Definition 3\.5\.

LetFFbe any GNN\. We define thequery tuples𝒬\\mathcal\{Q\},directional derivative∇𝒘𝒉i​\(G,X;F\)\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;F\)of an embedding at a query tuple, and thestationary points𝒮​\(F\)\\mathcal\{S\}\(F\)of GNNFF:

𝒬\\displaystyle\\mathcal\{Q\}=\{\(G,X,i,𝒘\)∣\(G,X\)∈supp​\(𝒟\),i∈\{1,…,n\},𝒘∈ℝD,‖𝒘‖=1\}\\displaystyle=\\bigl\\\{\(G,X,i,\{\\bm\{w\}\}\)\\mid\(G,X\)\\in\\mathrm\{supp\}\(\\mathcal\{D\}\),\\;i\\in\\\{1,\\ldots,n\\\},\\;\{\\bm\{w\}\}\\in\\mathbb\{R\}^\{D\},\\;\\\|\{\\bm\{w\}\}\\\|=1\\bigr\\\}𝒉i\(τ​𝒘\)​\(G,X;F\)\\displaystyle\{\\bm\{h\}\}\_\{i\}^\{\(\\tau\{\\bm\{w\}\}\)\}\(G,X;F\)=𝒉i​\(G,\[𝒙1,…,𝒙i−1,𝒙i\+τ​𝒘,𝒙i\+1,…,𝒙n\];F\),\\displaystyle=\{\\bm\{h\}\}\_\{i\}\\left\(G,\\begin\{bmatrix\}\{\\bm\{x\}\}\_\{1\},\\ldots,\{\\bm\{x\}\}\_\{i\-1\},\{\\bm\{x\}\}\_\{i\}\+\\tau\{\\bm\{w\}\},\{\\bm\{x\}\}\_\{i\+1\},\\ldots,\{\\bm\{x\}\}\_\{n\}\\end\{bmatrix\};F\\right\),∇𝒘𝒉i​\(G,X;F\)\\displaystyle\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;F\)=limτ→0𝒉i\(τ​𝒘\)​\(G,X;F\)−𝒉i​\(G,X;F\)τ∀\(G,X,i,𝒘\)∈𝒬\\displaystyle=\\lim\_\{\\tau\\to 0\}\\frac\{\{\\bm\{h\}\}\_\{i\}^\{\(\\tau\{\\bm\{w\}\}\)\}\(G,X;F\)\-\{\\bm\{h\}\}\_\{i\}\(G,X;F\)\}\{\\tau\}\\quad\\forall\(G,X,i,\{\\bm\{w\}\}\)\\in\\mathcal\{Q\}𝒮​\(F\)\\displaystyle\\mathcal\{S\}\(F\)=\{\(G,X,i,𝒘\)∈𝒬∣‖∇𝒘𝒉i​\(G,X;F\)‖=0\}\.\\displaystyle=\\bigl\\\{\(G,X,i,\{\\bm\{w\}\}\)\\in\\mathcal\{Q\}\\mid\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;F\)\\\|=0\\bigr\\\}\.We will refer to∇𝒘𝒉i​\(G,X;F\)\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;F\)as∇𝒘𝒉i​\(X\)\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(X\)when the context is clear\.

A stationary point is a graphGGwith featuresXXsuch that nudging a node’s features𝒙i\{\\bm\{x\}\}\_\{i\}in the direction±𝒘\\pm\{\{\\bm\{w\}\}\}does not change its embedding𝒉i\{\\bm\{h\}\}\_\{i\}to first order\. But if𝒉i\{\\bm\{h\}\}\_\{i\}is unaffected, so isϕ​\(𝒉i\)\\phi\(\{\\bm\{h\}\}\_\{i\}\),for anyϕ​\(⋅\)\\phi\(\\cdot\)\.Thus, this point is also stationary for the surrogate model\. The next lemma formalizes this property\.

###### Lemma 3\.6\.

Let𝐰∈ℝD,‖𝐰‖=1\{\\bm\{w\}\}\\in\\mathbb\{R\}^\{D\},\\\|\{\\bm\{w\}\}\\\|=1, and𝐡i′=ϕ​\(𝐡i\)\{\\bm\{h\}\}\_\{i\}^\{\\prime\}=\\phi\(\{\\bm\{h\}\}\_\{i\}\)for someϕ​\(⋅\)\\phi\(\\cdot\)satisfying Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\. Then,‖∇𝐰𝐡i​\(X\)‖=𝟎\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(X\)\\\|=\\bm\{0\}if and only if‖∇𝐰𝐡i′​\(X\)‖=𝟎\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\(X\)\\\|=\\bm\{0\}\.

This suggests the following algorithm: given the victim GNNMMand the unknown GNNZZ, test if𝒮​\(M\)=𝒮​\(Z\)\\mathcal\{S\}\(M\)=\\mathcal\{S\}\(Z\)\. By Lemma[3\.6](https://arxiv.org/html/2605.05360#S3.Thmtheorem6), the test succeeds ifZZis a surrogate ofMM\. But we expect the test to fail ifZZis an independent model, since every such model should converge to a different local optimum\. Now, we observe empirically that𝒮​\(M\)\\mathcal\{S\}\(M\)and𝒮​\(Z\)\\mathcal\{S\}\(Z\)are large sets, making direct comparison difficult\. Hence, we use a sampling\-based approach, as follows\.

Algorithm 1DetectSurrogate \(Special case\)1:GNNs

MMand

ZZ
2:Draw independent samples

TTfrom

𝒮​\(M\)\\mathcal\{S\}\(M\)
3:Check if all points in

TTare stationary for

ZZ
4:returnSurrogateif

T⊆𝒮​\(Z\)T\\subseteq\\mathcal\{S\}\(Z\)elseIndependent

In Section[3\.2](https://arxiv.org/html/2605.05360#S3.SS2), we will show how we sample from𝒮​\(M\)\\mathcal\{S\}\(M\)\. We will also remove the need to computeZZ’s gradients\. Next, we formalize the assumption of differences between the stationary points of the victim and any independent model, and use it to prove the algorithm’s correctness\.

###### Assumption 3\.7\(Idiosyncratic stationary points\)\.

\(a\)𝒮​\(M\)\\mathcal\{S\}\(M\)is equipped with a probability measureμM\\mu\_\{M\}from which we can draw samples\. \(b\) There existsγM\>0\\gamma\_\{M\}\>0such that for any independently trained modelII,μM​\(𝒮​\(M\)∖𝒮​\(I\)\)≥γM\.\\mu\_\{M\}\\\!\\bigl\(\\mathcal\{S\}\(M\)\\setminus\\mathcal\{S\}\(I\)\\bigr\)\\;\\geq\\;\\gamma\_\{M\}\.

Informally, if we sample a stationary point from𝒮​\(M\)\\mathcal\{S\}\(M\)according toμM\\mu\_\{M\}, then with probability at leastγM\\gamma\_\{M\}this point is not also a stationary point for the independent modelII\.

###### Theorem 3\.8\.

Ifϵ=0\\epsilon=0and Assumptions[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1),[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2), and[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7)hold, then Algorithm[1](https://arxiv.org/html/2605.05360#alg1)is correct with probability at least1−e−2​\|T\|​γM21\-e^\{\-2\|T\|\\gamma\_\{M\}^\{2\}\}\.

### 3\.2General Case

Now,𝒉^i​\(X\)\{\\hat\{\\bm\{h\}\}\}\_\{i\}\(X\)can be any function within a band of widthϵ\\epsilonaround𝒉i​\(X\)\{\\bm\{h\}\}\_\{i\}\(X\)\(Definition[3\.2](https://arxiv.org/html/2605.05360#A2.EGx1)\)\. Hence, its stationary points may differ fromMM\. The function𝒉^i​\(X\)\{\\hat\{\\bm\{h\}\}\}\_\{i\}\(X\)could even be discontinuous, so we cannot assume that its directional derivatives exist\. So we cannot directly check for stationary points in Algorithm[1](https://arxiv.org/html/2605.05360#alg1)\. Instead, we approximate the stationarity checks, as shown below\.

###### Definition 3\.9\.

LetFFbe any GNN model\. For a tuplet=\(G,X,i,𝒘\)∈𝒬t=\(G,X,i,\{\\bm\{w\}\}\)\\in\\mathcal\{Q\}andδ\>0\\delta\>0, define,

qF​\(t\)\\displaystyle q\_\{F\}\(t\)=‖𝒉i\(δ​𝒘\)​\(X\)−𝒉i​\(X\)‖‖𝒉i​\(X\)‖,\\displaystyle=\\frac\{\\\|\{\\bm\{h\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\(X\)\-\{\\bm\{h\}\}\_\{i\}\(X\)\\\|\}\{\\\|\{\\bm\{h\}\}\_\{i\}\(X\)\\\|\},βF\\displaystyle\\beta\_\{F\}=Et∼μM​qF​\(t\)Et∼𝒟e​x​p​qF​\(t\),\\displaystyle=\\frac\{E\_\{t\\sim\\mu\_\{M\}\}q\_\{F\}\(t\)\}\{E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}q\_\{F\}\(t\)\},\(3\)where𝒉i\(δ​𝒘\)​\(X\)\{\\bm\{h\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\(X\)depends onttas defined in Definition[3\.5](https://arxiv.org/html/2605.05360#A2.EGx3),

\(G,X\)\\displaystyle\(G,X\)∼𝒟,\\displaystyle\\sim\\mathcal\{D\},i∣G,X\\displaystyle i\\mid G,X∼Uniform​\(1,…,n\),\\displaystyle\\sim\\mathrm\{Uniform\}\(1,\\ldots,n\),𝒘∣G,X,i\\displaystyle\{\\bm\{w\}\}\\mid G,X,i∼Uniform​\(\{v∈ℝD,‖v‖=1\}\)\.\\displaystyle\\sim\\mathrm\{Uniform\}\(\\\{v\\in\\mathbb\{R\}^\{D\},\\,\\\|v\\\|=1\\\}\)\.

For intuition,qF​\(t\)q\_\{F\}\(t\)is a \(normalized\) magnitude of change in an embedding when we change the features𝒙i\{\\bm\{x\}\}\_\{i\}of nodeiiin the direction𝒘\{\\bm\{w\}\}, andβF\\beta\_\{F\}compares the expected change near the stationary points ofMMversus randomly chosen points in𝒬\\mathcal\{Q\}\. The formula forβF\\beta\_\{F\}is also invariant under common transformations of the embeddings \(Theorem[A\.3](https://arxiv.org/html/2605.05360#A2.EGx11)\)\. We will show below thatβF\\beta\_\{F\}is small whenFFis the victim model or a surrogate, but not whenFFis an independent model\. Thus,βF\\beta\_\{F\}mimics the properties of the directional derivative at stationary points𝒮​\(M\)\\mathcal\{S\}\(M\)\.

###### Lemma 3\.10\.

Under Assumption[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1), forδ\\deltasmall enough,βM=O​\(δ\)\\beta\_\{M\}=O\(\\delta\)\.

Lemma[3\.10](https://arxiv.org/html/2605.05360#S3.Thmtheorem10)shows thatβM\\beta\_\{M\}is small for the victim model\. Next, considerβM′\\beta\_\{M^\{\\prime\}\}for a surrogate modelM′M^\{\\prime\}\. Here, we need a stronger version of Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\. Instead of just requiring‖ϕ​\(𝒗1\)−ϕ​\(𝒗2\)‖≠0\\\|\\phi\(\{\\bm\{v\}\}\_\{1\}\)\-\\phi\(\{\\bm\{v\}\}\_\{2\}\)\\\|\\neq 0when‖𝒗1−𝒗2‖≠0\\\|\{\\bm\{v\}\}\_\{1\}\-\{\\bm\{v\}\}\_\{2\}\\\|\\neq 0, we now bound the change in norm due toϕ​\(⋅\)\\phi\(\\cdot\)\.

###### Assumption 3\.11\.

ϕ​\(𝟎\)=𝟎\\phi\(\\bm\{0\}\)=\\bm\{0\}, and there exist positive constantsc,Cc,Csuch that

c​‖𝒗1−𝒗2‖≤‖ϕ​\(𝒗1\)−ϕ​\(𝒗2\)‖≤C​‖𝒗1−𝒗2‖\.c\\\|\{\\bm\{v\}\}\_\{1\}\-\{\\bm\{v\}\}\_\{2\}\\\|\\;\\leq\\;\\\|\\phi\(\{\\bm\{v\}\}\_\{1\}\)\-\\phi\(\{\\bm\{v\}\}\_\{2\}\)\\\|\\;\\leq\\;C\\\|\{\\bm\{v\}\}\_\{1\}\-\{\\bm\{v\}\}\_\{2\}\\\|\.\(4\)

###### Lemma 3\.12\.

Suppose Assumptions[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1)and[3\.11](https://arxiv.org/html/2605.05360#S3.Thmtheorem11)hold, andϵ\\epsilonis as defined in Definition[3\.2](https://arxiv.org/html/2605.05360#A2.EGx1)\. Then, forδ\\deltasmall enough and any surrogateM′M^\{\\prime\}withϵ=o​\(δ\)\\epsilon=o\(\\delta\),

βM′=O​\(\(C/c\)2⋅max⁡\(ϵ/δ,δ\)\)\.\\beta\_\{M^\{\\prime\}\}\\;=\\;O\\\!\\left\(\(C/c\)^\{2\}\\cdot\\max\(\\epsilon/\\delta,\\,\\delta\)\\right\)\.\(5\)

The adversary wants a low reconstruction errorϵ\\epsilonso that the downstream accuracy of the surrogateM′M^\{\\prime\}is comparable to that of the victimMM\. But, by Lemma[3\.12](https://arxiv.org/html/2605.05360#S3.Thmtheorem12), a smallϵ\\epsilonforcesM′M^\{\\prime\}to have a smallβM′\\beta\_\{M^\{\\prime\}\}, just likeβM\\beta\_\{M\}\(Lemma[3\.10](https://arxiv.org/html/2605.05360#S3.Thmtheorem10)\)\. This result is independent of how the adversary trainsM′M^\{\\prime\}\. Next, consider an independent modelII\. By Assumption[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7), at least aγM\\gamma\_\{M\}fraction of the stationary points ofMMare unique toMM, so they are not stationary forII\. We further qualify this assumption next\.

###### Assumption 3\.13\.

Idiosyncratic stationary points ofMMare not special for independent modelsII:

Et∼μM​\[qI​\(t\)∣t∉𝒮​\(I\)\]=Et∼𝒟exp​\[qI​\(t\)\]\.E\_\{t\\sim\\mu\_\{M\}\}\\\!\\left\[q\_\{I\}\(t\)\\mid t\\notin\\mathcal\{S\}\(I\)\\right\]\\;=\\;E\_\{t\\sim\\mathcal\{D\}\_\{\\mathrm\{exp\}\}\}\\\!\\left\[q\_\{I\}\(t\)\\right\]\.\(6\)

Assumption[3\.13](https://arxiv.org/html/2605.05360#S3.Thmtheorem13)states that the idiosyncratic stationary points ofMMare not special forIIin any way\. We only require the independent modelIIto deviate significantly fromMMfor these points; however, we keep this version to simplify the exposition\. Figure[6](https://arxiv.org/html/2605.05360#A2.F6)in the Appendix shows some evidence in favor of this assumption\. With this assumption, we show thatβI=O​\(1\)\\beta\_\{I\}=O\(1\), unlike surrogate models\.

###### Lemma 3\.14\.

LetMMandIIbe independent models\. Suppose Assumptions[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1)holds for both models, and Assumptions[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7)and[3\.13](https://arxiv.org/html/2605.05360#S3.Thmtheorem13)hold\. Then, forδ\\deltasmall enough,βI≥γM\+O​\(δ\),\\beta\_\{I\}\\geq\\gamma\_\{M\}\+O\(\\delta\),whereγM\\gamma\_\{M\}is defined in Assumption[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7)\.

Our goal is to determine if the GNNZZis a surrogate of the victimMMor an independent model\. Lemmas[3\.10](https://arxiv.org/html/2605.05360#S3.Thmtheorem10),[3\.12](https://arxiv.org/html/2605.05360#S3.Thmtheorem12), and[3\.14](https://arxiv.org/html/2605.05360#S3.Thmtheorem14)show thatβZ\\beta\_\{Z\}is small \(O​\(δ\)O\(\\delta\)orO​\(ϵ/δ\+δ\)O\(\\epsilon/\\delta\+\\delta\)\) ifZZis the victim model or a surrogate, but at leastγM\\gamma\_\{M\}ifZZis independent\. This motivates Algorithm[2](https://arxiv.org/html/2605.05360#alg2)\(also see Remark[A\.1](https://arxiv.org/html/2605.05360#A1.Thmtheorem1)in Appendix[A](https://arxiv.org/html/2605.05360#A1)\)\.

Algorithm 2DetectSurrogate \(General case\)1:GNNs

MMand

ZZ, number of samples

ℓ\\ell, threshold

θ\\theta
2:

T←ℓT\\leftarrow\\ellsamples from

𝒮​\(M\)\\mathcal\{S\}\(M\)⊳\\trianglerightDef\.[3\.5](https://arxiv.org/html/2605.05360#A2.EGx3)

3:

R←ℓR\\leftarrow\\ellsamples from

𝒟exp\\mathcal\{D\}\_\{\\exp\}over

𝒬\\mathcal\{Q\}⊳\\trianglerightDef\.[3\.9](https://arxiv.org/html/2605.05360#A2.EGx5)

4:

β^Z←\(∑t∈TqZ​\(t\)\)/\(∑t∈RqZ​\(t\)\)\\hat\{\\beta\}\_\{Z\}\\leftarrow\\big\(\\sum\_\{t\\in T\}q\_\{Z\}\(t\)\\big\)/\\big\(\\sum\_\{t\\in R\}q\_\{Z\}\(t\)\\big\)⊳\\trianglerightEq\.[3](https://arxiv.org/html/2605.05360#S3.E3)

5:returnSurrogateif

β^Z≤θ\\hat\{\\beta\}\_\{Z\}\\leq\\thetaelseIndependent

###### Theorem 3\.15\.

Under the assumptions of Lemmas[3\.12](https://arxiv.org/html/2605.05360#S3.Thmtheorem12)and[3\.14](https://arxiv.org/html/2605.05360#S3.Thmtheorem14)and large enoughℓ\\ell, Algorithm[2](https://arxiv.org/html/2605.05360#alg2)withθ=γM/2\\theta=\\gamma\_\{M\}/2is correct with high probability\.

Selectingθ\\thetain Algorithm[2](https://arxiv.org/html/2605.05360#alg2):Theorem[3\.15](https://arxiv.org/html/2605.05360#S3.Thmtheorem15)shows thatθ\\thetadepends on the unknown parameterγM\\gamma\_\{M\}\. However,γM\\gamma\_\{M\}is upper\-bounded byβI\\beta\_\{I\}for any independent modelII\(Lemma[3\.14](https://arxiv.org/html/2605.05360#S3.Thmtheorem14)\)\. Thus, we can train several independent GNNs on the same data asMMto get an upper bound forγM\\gamma\_\{M\}, which we then use to set the threshold\. Alternatively, one can use the distribution ofβI\\beta\_\{I\}over all datasets and GNN architectures \(Figure[6](https://arxiv.org/html/2605.05360#A2.F6)in the Appendix\)\.

Sampling stationary points:Recall that a stationary point is a tuple\(G,X,i,𝒘\)∈𝒬\(G,X,i,\{\\bm\{w\}\}\)\\in\\mathcal\{Q\}such that‖∇𝒘𝒉i​\(G,x;M\)‖=0\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,x;M\)\\\|=0\(Definition[3\.5](https://arxiv.org/html/2605.05360#A2.EGx3)\)\. To find such a point, we sample a point\(G,X0,i,𝒘\)∼𝒟e​x​p\(G,X\_\{0\},i,\{\\bm\{w\}\}\)\\sim\\mathcal\{D\}\_\{exp\}\(Definition[3\.9](https://arxiv.org/html/2605.05360#A2.EGx5)\) and solve

X=arg​minX⁡\(‖∇𝒘𝒉i​\(G,X;M\)‖‖𝒉i​\(G,X;M\)‖\+λ⋅‖X−X0‖F‖X0‖F\)\.X=\\operatorname\*\{arg\\,min\}\_\{X\}\\left\(\\frac\{\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;M\)\\\|\}\{\\\|\{\\bm\{h\}\}\_\{i\}\(G,X;M\)\\\|\}\+\\lambda\\cdot\\frac\{\\\|X\-X\_\{0\}\\\|\_\{F\}\}\{\\\|X\_\{0\}\\\|\_\{F\}\}\\right\)\.\(7\)We then use\(G,X,i,𝒘\)\(G,X,i,\{\\bm\{w\}\}\)when a sample from𝒮​\(M\)\\mathcal\{S\}\(M\)is needed in Algorithm[2](https://arxiv.org/html/2605.05360#alg2)\. In the first term, we normalize‖∇𝒘𝒉i‖\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|by‖𝒉i‖\\\|\{\\bm\{h\}\}\_\{i\}\\\|since this matches the form ofqMq\_\{M\}\(Definition[3\.9](https://arxiv.org/html/2605.05360#A2.EGx5)\)\. The second term ensures that the chosen node featuresXXare close toX0X\_\{0\}drawn from the data distribution\. Hence,\(G,X\)\(G,X\)looks like a realistic graph\. We use a solver that does not require access to gradients\[bennet2021nevergrad\]\. Figure[5](https://arxiv.org/html/2605.05360#A2.F5)in Appendix[B](https://arxiv.org/html/2605.05360#A2)shows that the graphs picked using Equation[7](https://arxiv.org/html/2605.05360#S3.E7)are all distinct\.

The optimization in Eq\.[7](https://arxiv.org/html/2605.05360#S3.E7)operates on the node featuresXX, not on the graph structureGG\. For very large graphs, it is not necessary to optimize over the entire feature matrixXX\. Since the goal is to find a stationary point for the embedding of a single nodeii, it suffices to optimize over the features of nodeiiand itskk\-hop neighborhood\. This reduces the per\-iteration cost to a forward pass over a local subgraph of size depending onkk, rather than the full graph\. In our experiments, the embedding dimension has a larger effect on runtime than graph size\.

Extension to integer\-valued features:When the features are constrained to be integers, we cannot construct𝒉i\(δ​𝒘\)\{\\bm\{h\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\(Definition[3\.5](https://arxiv.org/html/2605.05360#A2.EGx3)\) for arbitraryδ\>0\\delta\>0and direction𝒘\{\\bm\{w\}\}\. Instead, we setδ=1\\delta=1and sample𝒘∈ℝD\{\\bm\{w\}\}\\in\\mathbb\{R\}^\{D\}from the set of axis\-aligned unit vectors:𝒘=𝒆j,where​j∼Uniform​\{1,…,D\},\{\\bm\{w\}\}=\\bm\{e\}\_\{j\},\\text\{ where \}j\\sim\\text\{Uniform\}\\\{1,\\ldots,D\\\},and𝒆j\\bm\{e\}\_\{j\}is the standard basis\-vector along thejt​hj^\{th\}feature\. We also replace∇𝒘𝒉i\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}by𝒉i\(𝒘\)−𝒉i\{\\bm\{h\}\}\_\{i\}^\{\(\{\\bm\{w\}\}\)\}\-\{\\bm\{h\}\}\_\{i\}in Equation[7](https://arxiv.org/html/2605.05360#S3.E7)when sampling stationary points\. While Theorem[3\.15](https://arxiv.org/html/2605.05360#S3.Thmtheorem15)assumes a smallδ\\delta, we show empirically that this approach works well in practice\.

Robustness against countermeasures:Suppose the adversary can examine the queries sent to their surrogate model\. The adversary cannot detect or penalize queries about stationary points for two reasons\. First, the regularization in Equation[7](https://arxiv.org/html/2605.05360#S3.E7)makes those graphs look realistic\. Second, recall that we query the surrogate with a graph\(G,X\)\(G,X\)\. Our chosen\(G,X\)\(G,X\)is stationary only for a random nodeiiand direction𝒘\{\\bm\{w\}\}, both unknown to the adversary\.

The adversary could take a different approach by adding noise to their output embeddings\. However, this degrades their downstream performance\. Furthermore, the adversary does not know how much noise is needed to go beyondCopyCop’s surrogate detection threshold\. This depends onCopyCop’s scores for independent models, which the adversary does not have access to\. We also show in Section[4](https://arxiv.org/html/2605.05360#S4)thatCopyCopis robust against adversarial attacks such as pruning and fine\-tuning, which introduce noise\.

Finally, note that Algorithm[2](https://arxiv.org/html/2605.05360#alg2)generates new query graphs each time\. Thus, even if some query graphs leak, future surrogate detection remains secure\.

## 4Experiments

Table 1:AUC of surrogate detection under model extraction attack \(higher is better\):Each AUC is computed by classifying all surrogates \(across all random seeds and all 5 GNN architectures\) against all independent models \(again across seeds and architectures\)\. PreGIP’s predictions are occasionally worse than random \(in red\)\. Averaged over 14 datasets,CopyCopdominates for all GNN architectures\. It has a perfect AUC for GCN, and is nearly perfect for MixHop\.We ran experiments to assess the accuracy ofCopyCopand competing methods for the surrogate GNN identification problem\. We used 14 datasets from diverse domains and tested 5 popular GNN architectures against various adversarial attacks and embedding transformations\.

Datasets:We present results on 14 graph datasets covering molecules, citations, co\-purchases, social, and financial networks\. Each dataset consists of several graphs with associated node features\. For datasets containing only a single graph, we used k\-hop subgraphs around randomly chosen nodes\. All datasets are available from thePyGlibrary, and their details are in Appendix[B](https://arxiv.org/html/2605.05360#A2)\.

Base GNN Models:We used the GCN\[kipf2017semi\], GIN\[xu2019how\], GraphSage\[hamilton2017inductive\], ARMA\[bianchi2022conv\], and MixHop\[abu\-el\-haija\_mixhop\_2019\]GNN architectures\. For each dataset, we trained all models on two data splits per task \(node or graph classification/regression\)\. For each model, we set it as the victim and the others as independent models\. The surrogate models are trained via the following adversarial attacks\.

Competing methods:We compare our method with the recent watermarking method PreGIP\[pregip\]and the fingerprinting method GrOVe\[grove\]\. PreGIP’s surrogate detection does not directly test embeddings\. So, for PreGIP, we score every graph by computingmean\-distance​\(Ga,Gb\)\\text\{mean\-distance\}\(G\_\{a\},G\_\{b\}\)over watermark graph pairs\(Ga,Gb\)\(G\_\{a\},G\_\{b\}\), and normalizing it by the same formula for randomly\-chosen pairs of graphs\. We compute surrogate detection AUCs using these scores\. Using other formulas, such as cosine similarity, reduces PreGIP’s performance \(Appendix[B](https://arxiv.org/html/2605.05360#A2)\)\.

### 4\.1Accuracy under Model Extraction Attack

We first show that watermarking via PreGIP is vulnerable to model extraction attacks\. Here, the adversary samples graphs, gets their embeddings from the victim model, and trains a GNN to output similar embeddings\. For each dataset, we trained independent models using multiple GNN architectures across two data splits\. Treating each as a victim, we then trained surrogate models\. For PreGIP, we followed the same procedure, but watermarked the victim before training the surrogate\.

We evaluated bothCopyCopand PreGIP on all surrogate and independent models\. Each method assigns a score to determine whether a model is a surrogate or independent\. Table[1](https://arxiv.org/html/2605.05360#S4.T1)reports the AUC of surrogate detection based on these scores\.

CopyCopis accurate:CopyCophasperfect surrogate detection \(AUC=1\)on73%73\\%of all combinations of datasets and GNN architectures\. The AUC exceeds0\.90\.9in83%83\\%of the cases\.CopyCop’s average AUC is highest for GCN \(always perfect\), MixHop \(0\.990\.99\), and GIN \(0\.960\.96\)\.

CopyCopoutperforms watermarks:Across all GNN architectures,CopyCop’s AUC is 17%\-48% betterthan PreGIP\. For GIN,CopyCopoutperforms by48%48\\%\. Furthermore, PreGIP’s scoring is sometimes worse than random \(highlighted in red in Table[1](https://arxiv.org/html/2605.05360#S4.T1)\)\.

Recall that in model extraction, the adversary uses the victim model to create a new training set\. This set is unlikely to contain PreGIP’s watermark graphs\. This limits the effectiveness of watermarking\. In contrast,CopyCopuses no watermarks and works well for all architectures\.

### 4\.2Accuracy under Embedding Transformations

Having shown that watermarking \(PreGIP\) is vulnerable to model extraction, we now examine the robustness of fingerprinting \(GrOVe\) under embedding transformations\. We constructed surrogate models by applying various transformations to their output embeddings, including ones that may violate our assumptions, and evaluated all methods on these modified models\.

Recall that, given an independent model and a surrogate, we compared their scores to determine which is the surrogate\. After transformation, the surrogate’s score may change, potentially altering this comparison\. To quantify this effect, we measured the fraction of independent models for which the prediction differed before and after transformation\. A lower fraction indicates greater robustness\. Table[2](https://arxiv.org/html/2605.05360#S4.T2)reports these fractions, averaged over all 14 datasets\.

CopyCopis robust against embedding transformations:CopyCopis immune to rotation, scaling, projection to a higher dimension, and combinations of these \(0%0\\%change\)\. This matches Theorem[A\.3](https://arxiv.org/html/2605.05360#A2.EGx11)\. We find that exponentiation has the greatest effect onCopyCop\. Exponentiation distorts distances between embeddings \(Assumption[3\.11](https://arxiv.org/html/2605.05360#S3.Thmtheorem11)\), which affects detection accuracy \(Lemma[3\.12](https://arxiv.org/html/2605.05360#S3.Thmtheorem12)\)\. We note thatCopyCopworks for translations, even though they do not match Assumption[3\.11](https://arxiv.org/html/2605.05360#S3.Thmtheorem11)\.

PreGIP and GrOVe are affected in different ways:PreGIP is much more susceptible to exponential and power transformations thanCopyCop\. In contrast, GrOVe is inapplicable when the surrogate embeddings are projected to higher dimensions\. GrOVe is also more sensitive thanCopyCopto the scaling of embedding components\.

CopyCopPreGIPGrOVeEmbedding TransformationGCNGINGSageARMAMixHopGCNGINGSageARMAMixHopGCNGINGSageARMAMixHopPermute0%0%0%0%0%0%0%0%0%0%0%4%4%15%0%Rotate0%0%0%0%0%0%0%0%0%0%0%4%10%16%0%Rotate, scale by 50%0%0%0%0%0%0%0%0%0%0%32%28%48%0%Project\(ℝd→ℝ5​d\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{5d\}\), rotate, scale by 50%0%0%0%0%0%0%0%0%0%N/AN/AN/AN/AN/AMultiply byd×dd\\times dGaussian mat\.1%1%2%2%2%2%1%4%7%3%0%18%29%35%0%\(as above\) and scale each entry by Unif\(1,10\)\(1,10\)2%1%2%3%3%3%2%3%7%4%7%52%50%53%8%Multiply by5​d×d5d\\times dGaussian mat\.0%0%1%1%1%1%0%2%4%2%N/AN/AN/AN/AN/A\(as above\) and scale each entry by Unif\(1,10\)\(1,10\)1%1%1%1%1%1%0%2%4%3%N/AN/AN/AN/AN/A𝒉i​j→tan−1⁡\(𝒉i​j\)\{\\bm\{h\}\}\_\{ij\}\\to\\tan^\{\-1\}\(\{\\bm\{h\}\}\_\{ij\}\)3%0%4%1%2%4%45%12%3%10%0%0%0%1%0%𝒉i​j→exp⁡\(𝒉i​j\)\{\\bm\{h\}\}\_\{ij\}\\to\\exp\(\{\\bm\{h\}\}\_\{ij\}\)13%9%20%40%26%11%77%20%40%31%0%7%27%8%7%𝒉i​j→sigmoid​\(𝒉i​j\)\{\\bm\{h\}\}\_\{ij\}\\to\\text\{sigmoid\}\(\{\\bm\{h\}\}\_\{ij\}\)7%2%14%21%12%4%43%2%3%9%0%0%0%0%0%𝒉i​j→sinh​\(𝒉i​j\)\{\\bm\{h\}\}\_\{ij\}\\to\\text\{sinh\}\(\{\\bm\{h\}\}\_\{ij\}\)9%1%4%16%7%9%77%14%30%34%0%6%12%7%4%𝒉i​j→tanh​\(𝒉i​j\)\{\\bm\{h\}\}\_\{ij\}\\to\\text\{tanh\}\(\{\\bm\{h\}\}\_\{ij\}\)3%0%5%1%2%10%48%15%8%15%0%0%0%1%0%𝒉i​j→𝒉i​j3\{\\bm\{h\}\}\_\{ij\}\\to\{\\bm\{h\}\}\_\{ij\}^\{3\}7%5%17%16%12%9%77%44%66%34%0%8%21%10%4%𝒉i​j→𝒉i​j5\{\\bm\{h\}\}\_\{ij\}\\to\{\\bm\{h\}\}\_\{ij\}^\{5\}7%5%21%21%16%16%77%54%72%44%4%8%25%14%7%Translate each entry by118%2%14%21%12%0%0%0%0%0%0%0%0%0%0%Translate each entry byUnif​\(1,5\)\\mathrm\{Unif\}\(1,5\)8%3%18%26%18%0%0%0%0%0%0%0%0%0%0%Translate each entry byUnif​\(1,10\)\\mathrm\{Unif\}\(1,10\)9%3%20%26%22%0%0%0%0%0%0%0%0%0%0%Normalize to unitL1L\_\{1\}norm1%0%3%6%1%22%56%37%18%20%0%0%0%2%0%Normalize to unitL2L\_\{2\}norm1%0%3%6%2%22%57%38%15%19%0%0%1%7%0%Average4%1%7%10%6%5%28%12%13%11%15%22%25%26%16%

Table 2:Sensitivity to embedding transformations \(lower is better\):We report the fraction of independent models for which the classification changes after transforming the surrogate \(averaged over 14 datasets\)\. Lower values indicate greater robustness\. PreGIP performs poorly for GIN models and under exponential and power transformations\. GrOVe is inapplicable when transformations change the embedding dimension \(counted as100%100\\%error\)\.CopyCopremains robust everywhere\.![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/Prune.png)\(a\)Effect of pruning
![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/Finetune.png)\(b\)Effect of fine\-tuning

Figure 2:AUC of surrogate detection against pruning and fine\-tuning attacks:Results are normalized against no\-tuning/fine\-tuning\.
### 4\.3Accuracy under Other Adversarial Attacks

In apruning attack, the adversary zeros out a fraction of the surrogate model’s weights\. To evaluate robustness, we computeCopyCop’s AUC for detecting the pruned surrogate among independent models, normalized by the AUC of the unpruned model\. Figure[2\(a\)](https://arxiv.org/html/2605.05360#S4.F2.sf1)reports the trimmed mean of these normalized AUCs across multiple datasets \(Citeseer, Pubmed, DBLP, Amazon, Computers\)\.

CopyCopremains robust up to𝟒𝟎%\\mathbf\{40\\%\}pruning, after which the detection AUC declines gradually\. Notably, for GIN, the AUC remains stable even with up to 70% of weights pruned\.

Next, we consider afine\-tuning attack, where the adversary updates the surrogate using a small labeled dataset\. Figure[2\(b\)](https://arxiv.org/html/2605.05360#S4.F2.sf2)shows thatCopyCop’s detection AUC remains stable throughout fine\-tuning\. Meanwhile, the downstream task accuracy saturates after 20–40 iterations \(Figure[4](https://arxiv.org/html/2605.05360#A2.F4)in the Appendix\), indicating limited benefit from further updates\. Overall,CopyCopis robust to fine\-tuning attacks\.

### 4\.4Additional analyses

![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/VaryNumStatPts.png)\(a\)Varying \# of stationary points
![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/VaryLambda.png)\(b\)Effect of varyingλ\\lambda
![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/Time.png)\(c\)Time to find stat\. point

Figure 3:CopyCopneeds only 20–40 stationary points to reach near\-maximum AUC\. AUC is largely insensitive toλ\\lambda, except for ARMA whereλ=0\.01\\lambda=0\.01is preferred\.CopyCopneeds only2020–4040stationary points to reach near\-maximum AUC across all GNN architectures \(Figure[3\(a\)](https://arxiv.org/html/2605.05360#S4.F3.sf1)\), consistent with Theorem[3\.8](https://arxiv.org/html/2605.05360#S3.Thmtheorem8)\. Surrogate detection is largely insensitive to the regularizationλ\\lambdain Equation[7](https://arxiv.org/html/2605.05360#S3.E7), except for ARMA whereλ=0\.01\\lambda=0\.01is preferred \(Figure[3\(b\)](https://arxiv.org/html/2605.05360#S4.F3.sf2)\)\. The wall\-clock time per stationary point grows with embedding dimension and is shortest for GCN, longest for ARMA \(Figure[3\(c\)](https://arxiv.org/html/2605.05360#S4.F3.sf3)\)\.

## 5Conclusions

We introducedCopyCop, a fingerprinting method for verifying the ownership of GNNs that output node embeddings\. Our key insight is that stationary points of the embedding function are invariant under a broad class of transformations, making them a robust basis for fingerprinting\. This allowsCopyCopto detect surrogate models even when the adversary changes architectures, embedding dimensions, or applies complex transformations to the embeddings\.

We complement this idea with a practical sampling and testing procedure, along with theoretical guarantees for surrogate detection\. Empirically, across 14 datasets and 5 GNN architectures,CopyCopconsistently achieves high detection accuracy and outperforms existing watermarking and fingerprinting methods\.

One direction of future work is to relax or validate assumptions about the transformation function and the distribution of stationary points\. Also, improving the efficiency of stationary point discovery, especially for very large graphs or higher\-dimensional embeddings, would further enhance scalability\.

## References

## Appendix ARemarks and Proofs

###### Lemma A\.2\(Closure under composition\)\.

Iff:ℝd→ℝd′f:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{d^\{\\prime\}\}andg:ℝd′′→ℝdg:\\mathbb\{R\}^\{d^\{\\prime\\prime\}\}\\to\\mathbb\{R\}^\{d\}each satisfy Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2), thenf∘gf\\circ galso satisfies Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\.

###### Proof of Lemma[A\.2](https://arxiv.org/html/2605.05360#A1.Thmtheorem2)\.

Letwwbe any unit vector andhhany point in the domain ofgg\. By the chain rule,

∇w\(f∘g\)\|h=Jf\|g​\(h\)⋅Jg\|h​w=Jf\|g​\(h\)⋅∇wg\|h\.\\nabla\_\{w\}\(f\\circ g\)\\big\|\_\{h\}=J\_\{f\}\\big\|\_\{g\(h\)\}\\cdot J\_\{g\}\\big\|\_\{h\}\\,w=J\_\{f\}\\big\|\_\{g\(h\)\}\\cdot\\nabla\_\{w\}g\\big\|\_\{h\}\.Sinceggsatisfies Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2),∇wg\|h≠0\\nabla\_\{w\}g\\big\|\_\{h\}\\neq 0\. Letv:=∇wg\|hv:=\\nabla\_\{w\}g\\big\|\_\{h\}; thenv≠0v\\neq 0, sov/‖v‖v/\\\|v\\\|is a unit vector\. Sinceffsatisfies Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2),

Jf\|g​\(h\)​v=‖v‖⋅∇v/‖v‖f\|g​\(h\)≠0\.J\_\{f\}\\big\|\_\{g\(h\)\}\\,v=\\\|v\\\|\\cdot\\nabla\_\{v/\\\|v\\\|\}f\\big\|\_\{g\(h\)\}\\neq 0\.Hence∇w\(f∘g\)\|h≠0\\nabla\_\{w\}\(f\\circ g\)\\big\|\_\{h\}\\neq 0, sof∘gf\\circ gsatisfies Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\. ∎

###### Proof of Lemma[3\.6](https://arxiv.org/html/2605.05360#S3.Thmtheorem6)\.

LetJ′J^\{\\prime\},JϕJ^\{\\phi\}, andJJbe the Jacobians of the functions𝒉i′​\(X\)\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\(X\),ϕ​\(𝒉\)\\phi\(\{\\bm\{h\}\}\), and𝒉​\(X\)\{\\bm\{h\}\}\(X\)respectively \(these exist by Assumptions[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1)and[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\)\. By the chain rule,

∇𝒘𝒉i′​\(X\)\\displaystyle\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\(X\)=J′\|X​𝒘\\displaystyle=\\left\.J^\{\\prime\}\\right\|\_\{X\}\{\\bm\{w\}\}=Jϕ\|𝒉i​\(X\)​J\|X​𝒘=Jϕ\|𝒉i​\(X\)​∇𝒘𝒉i​\(X\),\\displaystyle=\\left\.J^\{\\phi\}\\right\|\_\{\{\\bm\{h\}\}\_\{i\}\(X\)\}\\left\.J\\right\|\_\{X\}\{\\bm\{w\}\}=\\left\.J^\{\\phi\}\\right\|\_\{\{\\bm\{h\}\}\_\{i\}\(X\)\}\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(X\),Hence,∇𝒘𝒉i​\(X\)=0⇒∇𝒘𝒉i′​\(X\)=0\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(X\)=0\\Rightarrow\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\(X\)=0\. Conversely, suppose∇𝒘𝒉i′​\(X\)=0\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}^\{\\prime\}\(X\)=0\. Then,Jϕ\|𝒉i​\(X\)​𝒗=𝟎\\left\.J^\{\\phi\}\\right\|\_\{\{\\bm\{h\}\}\_\{i\}\(X\)\}\{\\bm\{v\}\}=\\bm\{0\}, where𝒗:=∇𝒘𝒉i​\(X\)\{\\bm\{v\}\}:=\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(X\)\. If𝒗≠𝟎\{\\bm\{v\}\}\\neq\\bm\{0\}, then𝟎=Jϕ\|𝒉i​\(X\)​𝒗=‖𝒗‖⋅∇𝒗/‖𝒗‖ϕ\|𝒉i​\(X\)\\bm\{0\}=\\left\.J^\{\\phi\}\\right\|\_\{\{\\bm\{h\}\}\_\{i\}\(X\)\}\{\\bm\{v\}\}=\\\|\{\\bm\{v\}\}\\\|\\cdot\\left\.\\nabla\_\{\{\\bm\{v\}\}/\\\|\{\\bm\{v\}\}\\\|\}\\phi\\right\|\_\{\{\\bm\{h\}\}\_\{i\}\(X\)\}, which is impossible by Assumption[3\.4](https://arxiv.org/html/2605.05360#A2.EGx2)\. Hence,∇𝒘𝒉i​\(X\)=𝒗=𝟎\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(X\)=\{\\bm\{v\}\}=\\bm\{0\}\. ∎

###### Proof of Theorem[3\.8](https://arxiv.org/html/2605.05360#S3.Thmtheorem8)\.

By Lemma[3\.6](https://arxiv.org/html/2605.05360#S3.Thmtheorem6), Algorithm[1](https://arxiv.org/html/2605.05360#alg1)fails iffZZis independent butT⊆𝒮​\(Z\)T\\subseteq\\mathcal\{S\}\(Z\)\. SupposeZZis an independent model\. Eacht∈Tt\\in Tis drawn independently using measureμM\\mu\_\{M\}\. We have,Et∼μM​\[𝟙t∈𝒮​\(Z\)\]=P​\(t∈𝒮​\(Z\)\)≤1−γME\_\{t\\sim\\mu\_\{M\}\}\[\\mathds\{1\}\_\{t\\in\\mathcal\{S\}\(Z\)\}\]=P\(t\\in\\mathcal\{S\}\(Z\)\)\\leq 1\-\\gamma\_\{M\}by Assumption[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7)\. Algorithm[1](https://arxiv.org/html/2605.05360#alg1)fails with probability

P​\(\|T∩𝒮​\(Z\)\|\|T\|=1\)\\displaystyle P\\left\(\\frac\{\|T\\cap\\mathcal\{S\}\(Z\)\|\}\{\|T\|\}=1\\right\)≤\(1−γM\)\|T\|≤exp⁡\(−γM⋅T\)\.\\displaystyle\\leq\(1\-\\gamma\_\{M\}\)^\{\|T\|\}\\leq\\exp\\left\(\-\\gamma\_\{M\}\\cdot T\\right\)\.∎

###### Proof of Lemma[3\.10](https://arxiv.org/html/2605.05360#S3.Thmtheorem10)\.

For any feasible tuplet=\(G,X,i,𝒘\)t=\(G,X,i,\{\\bm\{w\}\}\),

qM​\(t\)\\displaystyle q\_\{M\}\(t\)=‖𝒉i\(δ​𝒘\)​\(X\)−𝒉i​\(X\)‖‖𝒉i​\(X\)‖=δ⋅‖∇𝒘𝒉i‖\+O​\(δ2\)‖𝒉i‖\.\\displaystyle=\\frac\{\\\|\{\\bm\{h\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\(X\)\-\{\\bm\{h\}\}\_\{i\}\(X\)\\\|\}\{\\\|\{\\bm\{h\}\}\_\{i\}\(X\)\\\|\}=\\frac\{\\delta\\cdot\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\+O\(\\delta^\{2\}\)\}\{\\\|\{\\bm\{h\}\}\_\{i\}\\\|\}\.Fort∈𝒮​\(M\)t\\in\\mathcal\{S\}\(M\),‖∇𝒘𝒉i‖=0\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|=0soqM​\(t\)=O​\(δ2\)q\_\{M\}\(t\)=O\(\\delta^\{2\}\)\(since‖𝒉i‖≥α¯M\\\|\{\\bm\{h\}\}\_\{i\}\\\|\\geq\\underline\{\\alpha\}\_\{M\}by Assumption[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1)\)\. Now,uM:=Et∼𝒟e​x​p​‖∇𝒘𝒉i‖\>0u\_\{M\}:=E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\>0because the GNN’s outputs must be affected by changing inputs for at least some graphs\. So,Et∼𝒟e​x​p≥δ​uM\+O​\(δ2\)α¯ME\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\geq\\frac\{\\delta u\_\{M\}\+O\(\\delta^\{2\}\)\}\{\\overline\{\\alpha\}\_\{M\}\}\. Hence,

βM≤O​\(δ2\)δ​uM/α¯M\+O​\(δ2\)=O​\(δ\)\.\\displaystyle\\beta\_\{M\}\\leq\\frac\{O\(\\delta^\{2\}\)\}\{\\delta u\_\{M\}/\\overline\{\\alpha\}\_\{M\}\+O\(\\delta^\{2\}\)\}=O\(\\delta\)\.∎

###### Theorem A\.3\.

For any modelFF,βF\\beta\_\{F\}is unchanged under any combination of

rotation:𝒉→O​𝒉\\displaystyle\{\\bm\{h\}\}\\to O\{\\bm\{h\}\}\(O​orthonormal\)\\displaystyle\(O\\text\{ orthonormal\}\)scaling:𝒉→c​𝒉\\displaystyle\{\\bm\{h\}\}\\to c\{\\bm\{h\}\}\(c≠0\)\\displaystyle\(c\\neq 0\)up\-projection:𝒉→\[𝒉T,0,…,0⏟ℓ​times\]T\\displaystyle\{\\bm\{h\}\}\\to\[\{\\bm\{h\}\}^\{T\},\\underbrace\{0,\\ldots,0\}\_\{\\ell\\text\{times\}\}\]^\{T\}\(arbitrary​ℓ\)\.\\displaystyle\(\\text\{arbitrary \}\\ell\)\.

###### Proof of Theorem[A\.3](https://arxiv.org/html/2605.05360#A2.EGx11)\.

qF​\(t\)q\_\{F\}\(t\)is clearly invariant under these transformations, soβF\\beta\_\{F\}is too\. ∎

###### Proof of Lemma[3\.12](https://arxiv.org/html/2605.05360#S3.Thmtheorem12)\.

∥\\displaystyle\\\|ϕ\(𝒉^i\(δ​𝒘\)\)−ϕ\(𝒉^i\)∥\\displaystyle\\phi\(\{\\hat\{\\bm\{h\}\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\)\-\\phi\(\{\\hat\{\\bm\{h\}\}\}\_\{i\}\)\\\|≤C​‖𝒉^i\(δ​𝒘\)−𝒉^i‖\\displaystyle\\leq C\\\|\{\\hat\{\\bm\{h\}\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\-\{\\hat\{\\bm\{h\}\}\}\_\{i\}\\\|≤C​\[‖𝒉^i\(δ​𝒘\)−𝒉i\(δ​𝒘\)‖\+‖𝒉i\(δ​𝒘\)−𝒉i‖\+‖𝒉^i−𝒉i‖\]\\displaystyle\\leq C\\left\[\\\|\{\\hat\{\\bm\{h\}\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\-\{\\bm\{h\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\\\|\+\\\|\{\\bm\{h\}\}\_\{i\}^\{\(\\delta\{\\bm\{w\}\}\)\}\-\{\\bm\{h\}\}\_\{i\}\\\|\+\\\|\{\\hat\{\\bm\{h\}\}\}\_\{i\}\-\{\\bm\{h\}\}\_\{i\}\\\|\\right\]≤C​\[2​ϵ\+δ​‖∇𝒘𝒉i‖\+O​\(δ2\)\]\\displaystyle\\leq C\\left\[2\\epsilon\+\\delta\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\+O\(\\delta^\{2\}\)\\right\]≤C​\[δ​‖∇𝒘𝒉i‖\+O​\(ϵ\+δ2\)\]\.\\displaystyle\\leq C\\left\[\\delta\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\+O\(\\epsilon\+\\delta^\{2\}\)\\right\]\.Also,

‖ϕ​\(𝒉^i\)‖≥c​‖𝒉^i‖≥c​\(‖𝒉i‖−ϵ\)≥c​\(α¯M−ϵ\)≥c​α¯M/2\\displaystyle\\\|\\phi\(\{\\hat\{\\bm\{h\}\}\}\_\{i\}\)\\\|\\geq c\\\|\{\\hat\{\\bm\{h\}\}\}\_\{i\}\\\|\\geq c\(\\\|\{\\bm\{h\}\}\_\{i\}\\\|\-\\epsilon\)\\geq c\(\\underline\{\\alpha\}\_\{M\}\-\\epsilon\)\\geq c\\underline\{\\alpha\}\_\{M\}/2forϵ\\epsilonsmall enough, where the first inequality follows from Assumption[3\.11](https://arxiv.org/html/2605.05360#S3.Thmtheorem11)\. Hence,

qM′​\(t\)\\displaystyle q\_\{M^\{\\prime\}\}\(t\)≤C​\[δ​‖∇𝒘𝒉i‖\+O​\(ϵ\+δ2\)\]c​α¯M/2\.\\displaystyle\\leq\\frac\{C\\left\[\\delta\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\+O\(\\epsilon\+\\delta^\{2\}\)\\right\]\}\{c\\underline\{\\alpha\}\_\{M\}/2\}\.Similarly,​qM′​\(t\)\\displaystyle\\text\{Similarly, \}q\_\{M^\{\\prime\}\}\(t\)≥c​\[δ​‖∇𝒘𝒉i‖\+O​\(ϵ\+δ2\)\]2​C​α¯M\.\\displaystyle\\geq\\frac\{c\\left\[\\delta\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\+O\(\\epsilon\+\\delta^\{2\}\)\\right\]\}\{2C\\overline\{\\alpha\}\_\{M\}\}\.DefineuM:=Et∼𝒟e​x​p​‖∇𝒘𝒉i‖\>0u\_\{M\}:=E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\\\|\>0as in the proof of Lemma[3\.10](https://arxiv.org/html/2605.05360#S3.Thmtheorem10)\. Then,

Et∼μM​\[qM′​\(t\)\]\\displaystyle E\_\{t\\sim\\mu\_\{M\}\}\\left\[q\_\{M^\{\\prime\}\}\(t\)\\right\]≤Cc​α¯/2⋅O​\(ϵ\+δ2\)\\displaystyle\\leq\\frac\{C\}\{c\\underline\{\\alpha\}/2\}\\cdot O\(\\epsilon\+\\delta^\{2\}\)Et∼𝒟e​x​p​\[qM′​\(t\)\]\\displaystyle E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\left\[q\_\{M^\{\\prime\}\}\(t\)\\right\]≥c​\(δ⋅uM\+O​\(ϵ\+δ2\)\)2​C​α¯M\\displaystyle\\geq\\frac\{c\(\\delta\\cdot u\_\{M\}\+O\(\\epsilon\+\\delta^\{2\}\)\)\}\{2C\\overline\{\\alpha\}\_\{M\}\}So,​βM′\\displaystyle\\text\{So, \}\\beta\_\{M^\{\\prime\}\}≤\(Cc\)2⋅O​\(\(ϵ\+δ2\)δ\)\\displaystyle\\leq\\left\(\\frac\{C\}\{c\}\\right\)^\{2\}\\cdot O\\left\(\\frac\{\(\\epsilon\+\\delta^\{2\}\)\}\{\\delta\}\\right\)\(since​ϵ=o​\(δ\)\)\\displaystyle\(\\text\{since \}\\epsilon=o\(\\delta\)\)≤\(Cc\)2​O​\(max⁡\(ϵ/δ,δ\)\)\.\\displaystyle\\leq\\left\(\\frac\{C\}\{c\}\\right\)^\{2\}O\\left\(\\max\(\\epsilon/\\delta,\\delta\)\\right\)\.∎

###### Proof of Lemma[3\.14](https://arxiv.org/html/2605.05360#S3.Thmtheorem14)\.

As in the proof of Lemma[3\.10](https://arxiv.org/html/2605.05360#S3.Thmtheorem10), we defineuI:=Et∼𝒟e​x​p​‖∇𝒘𝒉i​\(G,X;I\)‖\>0u\_\{I\}:=E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;I\)\\\|\>0and find that

Et∼𝒟e​x​p​\[qI​\(t\)\]\\displaystyle E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\[q\_\{I\}\(t\)\]≥δ​uI\+O​\(δ2\)α¯I=Θ​\(δ\)\.\\displaystyle\\geq\\frac\{\\delta u\_\{I\}\+O\(\\delta^\{2\}\)\}\{\\overline\{\\alpha\}\_\{I\}\}=\\Theta\(\\delta\)\.\(9\)Fort∈𝒮​\(I\)t\\in\\mathcal\{S\}\(I\), we have

qI​\(t\)\\displaystyle q\_\{I\}\(t\)≥δ​‖∇𝒘𝒉i​\(G,X;I\)‖\+O​\(δ2\)α¯I=O​\(δ2\)\.\\displaystyle\\geq\\frac\{\\delta\\\|\\nabla\_\{\{\\bm\{w\}\}\}\{\\bm\{h\}\}\_\{i\}\(G,X;I\)\\\|\+O\(\\delta^\{2\}\)\}\{\\overline\{\\alpha\}\_\{I\}\}=O\(\\delta^\{2\}\)\.\(10\)Now,

Et∼μM​\[qI​\(t\)\]\\displaystyle E\_\{t\\sim\\mu\_\{M\}\}\\left\[q\_\{I\}\(t\)\\right\]=P​\(t∈𝒮​\(I\)\)⋅Et​\[qI​\(t\)∣t∈𝒮​\(I\)\]\\displaystyle=P\(t\\in\\mathcal\{S\}\(I\)\)\\cdot E\_\{t\}\\left\[q\_\{I\}\(t\)\\mid t\\in\\mathcal\{S\}\(I\)\\right\]\+P​\(t∉𝒮​\(I\)\)⋅Et​\[qI​\(t\)∣t∉𝒮​\(I\)\]\\displaystyle\+P\(t\\notin\\mathcal\{S\}\(I\)\)\\cdot E\_\{t\}\\left\[q\_\{I\}\(t\)\\mid t\\notin\\mathcal\{S\}\(I\)\\right\]=P​\(𝒮​\(M\)∩𝒮​\(I\)\)⋅O​\(δ2\)\\displaystyle=P\(\\mathcal\{S\}\(M\)\\cap\\mathcal\{S\}\(I\)\)\\cdot O\(\\delta^\{2\}\)\+P​\(𝒮​\(M\)∖𝒮​\(I\)\)⋅Et∼𝒟e​x​p​\[qI​\(t\)\]\\displaystyle\+P\(\\mathcal\{S\}\(M\)\\setminus\\mathcal\{S\}\(I\)\)\\cdot E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\left\[q\_\{I\}\(t\)\\right\]≥γM⋅Et∼𝒟e​x​p​\[qI​\(t\)\]\+O​\(δ2\),\\displaystyle\\geq\\gamma\_\{M\}\\cdot E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\left\[q\_\{I\}\(t\)\\right\]\+O\(\\delta^\{2\}\),So,​βI\\displaystyle\\text\{So, \}\\beta\_\{I\}≥γM⋅Et∼𝒟e​x​p​\[qI​\(t\)\]\+O​\(δ2\)Et∼𝒟e​x​p​\[qI​\(t\)\]\\displaystyle\\geq\\frac\{\\gamma\_\{M\}\\cdot E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\left\[q\_\{I\}\(t\)\\right\]\+O\(\\delta^\{2\}\)\}\{E\_\{t\\sim\\mathcal\{D\}\_\{exp\}\}\\left\[q\_\{I\}\(t\)\\right\]\}≥γM\+O​\(δ\),\\displaystyle\\geq\\gamma\_\{M\}\+O\(\\delta\),where we used Equation[10](https://arxiv.org/html/2605.05360#A1.E10)and Assumption[3\.13](https://arxiv.org/html/2605.05360#S3.Thmtheorem13)in the second equality, and Equation[9](https://arxiv.org/html/2605.05360#A1.E9)in the last step\. ∎

###### Proof of Theorem[3\.15](https://arxiv.org/html/2605.05360#S3.Thmtheorem15)\.

Since𝒉i\{\\bm\{h\}\}\_\{i\}is upper\- and lower\-bounded \(Assumption[3\.1](https://arxiv.org/html/2605.05360#S3.Thmtheorem1)\), so isqZ​\(t\)q\_\{Z\}\(t\)\. Then, the numerator and denominator ofβ^Z\\hat\{\\beta\}\_\{Z\}converge to their counterparts forβZ\\beta\_\{Z\}by Hoeffding bounds, and the result follows\. ∎

Table 3:AUC for classifying surrogate versus independent models under model extraction attack:This is similar to Table[1](https://arxiv.org/html/2605.05360#S4.T1), except that we use cosine similarity for PreGIP instead of distances\.CopyCopis comprehensively better, especially for the GIN architecture\.
## Appendix BExperimental Details

Table[5](https://arxiv.org/html/2605.05360#A2.T5)shows the characteristics of our 14 datasets\. Table[3](https://arxiv.org/html/2605.05360#A1.T3)compares the surrogate detection AUC ofCopyCopand a version of PreGIP where the scores are based on cosine\-similarity rather than distances between embeddings of pairs of watermarks graphs\. PreGIP with cosine similarity shows worse results than using distances, so we focus on the latter in the main paper \(Table[1](https://arxiv.org/html/2605.05360#S4.T1)\)\.

Figure[4](https://arxiv.org/html/2605.05360#A2.F4)shows the normalized accuracy of the surrogate model on a downstream task after being fine\-tuned for that task\. We report the trimmed means over 5 datasets\. All models stabilize within 20\-40 epochs, with the greatest benefits occurring for GraphSage and MixHop\. Note thatCopyCop’s surrogate detection accuracy remains robust throughout fine\-tuning \(Figure[2\(b\)](https://arxiv.org/html/2605.05360#S4.F2.sf2)\)\.

Figure[3\(a\)](https://arxiv.org/html/2605.05360#S4.F3.sf1)showsCopyCop’s normalized AUC when we vary the number of stationary points used in Algorithm[2](https://arxiv.org/html/2605.05360#alg2)\(parameter namedℓ\\ell\)\. We need only20−4020\-40points to achieve a high surrogate detection accuracy\.

Figure[5](https://arxiv.org/html/2605.05360#A2.F5)shows the distribution of cosine similarities between the node features of two stationary points of the same size\. The distribution is mostly concentrated around0, showing that most stationary points are distinct from each other\. Hence, Algorithm[2](https://arxiv.org/html/2605.05360#alg2)picks distinct graphs for its queries\.

Figure[6](https://arxiv.org/html/2605.05360#A2.F6)shows the distribution ofCopyCop’s scoreβ^Z\\hat\{\\beta\}\_\{Z\}for all independent models \(Equation[8](https://arxiv.org/html/2605.05360#A1.E8)\)\. Suppose the stationary points of the victim model are not in any way special points for the independent models\. Then, we would expect the percentile scores to be spread uniformly between0to100100, with a mean aroundβ^Z=50\\hat\{\\beta\}\_\{Z\}=50\. We see that for most datasets and GNN architectures, theβ^Z\\hat\{\\beta\}\_\{Z\}scores are indeed around5050\. This provides some evidence for our Assumptions[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7)and[3\.13](https://arxiv.org/html/2605.05360#S3.Thmtheorem13)\. Table[4](https://arxiv.org/html/2605.05360#A2.T4)lists the GNN architectures and configurations used in our experiments\. All seeds are fixed for reproducibility\. We used standard configurations from the literature and did not tune hyperparameters for highest accuracy; our goal was to evaluate whether CopyCop works across a diverse range of trained models\.

Compute resources:All experiments were run on a single workstation with an Intel Core i9\-10980XE CPU \(18 cores / 36 threads\), 256 GB of RAM, and 2×\\timesNVIDIA RTX 3090 GPUs \(24 GB each\)\. The benchmark spans 14 graph datasets and 5 GNN architectures \(GCN, GIN, GraphSAGE, ARMA, MixHop\) per dataset, with stolen and independent copies for each base model\. All \(dataset, architecture\) pairs are independent of one another, so we ran them as independent processes\. Wall\-clock per\-stationary\-point timings reported in Figure[3\(c\)](https://arxiv.org/html/2605.05360#S4.F3.sf3)is per\-process \(not summed across parallel workers\)\.

Table 4:GNN model configurations:All GNNs output node embeddings, whose accuracy is tested on downstream tasks\. For node\-level tasks, a final linear layer produces the output\. For graph\-level tasks, we append GlobalMeanPooling \+ Dropout \+ Linear\.![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/Finetune_dsacc.png)Figure 4:Accuracy of downstream task under fine\-tuning:The accuracy is normalized by the accuracy before fine\-tuning\. We report the trimmed mean of the normalized accuracy across 5 datasets\. The accuracy stabilizes after 20\-40 epochs\.![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/Cosines_citeseer.png)Figure 5:Cosine similarity of stationary points:We picked 25 stationary points for 2\-node graphs constructed using Equation[7](https://arxiv.org/html/2605.05360#S3.E7)for the Citeseer dataset\. For every pair of graphs, we computed the cosine similarity between their node features after flattening the feature matrices into vectors\. We show the distribution of cosine similarity\. This shows that most stationary points are nearly orthogonal to each other, showing that our sampling approach in Algorithm[2](https://arxiv.org/html/2605.05360#alg2)picks distinct stationary points\.![Refer to caption](https://arxiv.org/html/2605.05360v1/FIG/Indep_pscores.png)Figure 6:CopyCop’s score distribution for independent models:We show the distribution ofβ^Z\\hat\{\\beta\}\_\{Z\}\(Eq\.[8](https://arxiv.org/html/2605.05360#A1.E8)\) for all independent models across all GNN architectures and datasets\. Recall thatβ^Z\\hat\{\\beta\}\_\{Z\}is an average of percentile scores\. The distribution peaks around50%50\\%, which is exactly the expected value if the stationary points of the victim model were “random” points for the independent models \(see Assumptions[3\.7](https://arxiv.org/html/2605.05360#S3.Thmtheorem7)and[3\.13](https://arxiv.org/html/2605.05360#S3.Thmtheorem13)\)\.Table 5:Dataset characteristics