FedGMark: Certifiably Robust Watermarking for Federated Graph Learning
Authors: Yuxin Yang
Qiang Li
Yuan Hong
Binghui Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Watermark
Federated Graph Learning
Primary area: safety_in_machine_learning

Abstract: Federated graph learning (FedGL) is an emerging learning paradigm to collaboratively train graph data from various clients. However, during the development and deployment of FedGL models, they are susceptible to illegal copying and model theft. Backdoor-based watermarking is a well-known method for mitigating these attacks, as it offers ownership verification to the model owner. We take the first step to protect the ownership of FedGL models via backdoor-based watermarking. Existing techniques have challenges in achieving the goal: 1) they either cannot be directly applied or yield unsatisfactory performance; 2) they are vulnerable to watermark removal attacks; and 3) they lack of formal guarantees. To address all the challenges, we propose FedGMark, the first certified robust backdoor-based watermarking for FedGL. FedGMark leverages the unique graph structure and client information in FedGL to learn customized and diverse watermarks. It also designs a novel GL architecture that facilitates defending against both the empirical and theoretically worst-case watermark removal attacks. Extensive experiments validate the promising empirical and provable watermarking performance of FedGMark. Source code is available at: https://github.com/Yuxin104/FedGMark.

FedG Certifiably Robust Watermarking for Federated Graph Learning
Yuxin Yang!. Qiang Li
Yuan Hong
Binghui Wang2*
'College of Computer Science and Technology, Jilin University, Changchun. Jilin, China Department of Computer Science, Illinois Institute of Technology, Chicago, Illinois, USA School of Computing, University of Connecticut, Storrs, Connecticut, USA
Abstract
Federated graph learning (FedGL) is emerging learning paradigm to collabora- tively train graph data from various clients. However, during the development and deployment of FedGL models, they susceptible to illegal copying and model theft. Backdoor-based watermarking is well-known method for mitigating these attacks, offers ownership verification to the model owner. We take the first step to protect the ownership of FedGL models via backdoor- based watermarking. Existing techniques have challenges in achieving the goal: 1) they either cannot be directly applied or yield unsatisfactory performance; 2) they are vulnerable to watermark removal attacks; and they lack of formal guarantees. To address all the challenges, we propose FedGMark, the first certified robust backdoor-based wa- termarking for FedGL. FedGMark leverages the unique graph structure and client information in FedGL to learn customized and diverse watermarks. It also designs novel GL architecture that facilitates defending against both the empirical and the- oretically worst-case watermark removal attacks. Extensive experiments validate the promising empirical and provable watermarking performance of FedGMark. Source code is available at: https: gighuu....... com wwtp:/cccooyyooooooo wctm//uxii.114//eeM/aar
Introduction
Federated Graph Learning (FedGL) [Xie et al. 2021 Wang et al. 2022a Tan et al. 2023 Yao et al.
2024] leverages a server and multiple clients collaboratively train GL methods Kipf and Welling
2017
Hamilton et al. 2017] via federated learning (FL.) (McMahan el al.) 2017: Li el al. 2021
recent years, FedGl. has attracted increasing interest domains such as disease prediction [Png el al, [202]]. recommendation systems (Back et al.) [023] Wu et al. 2022
Karimireddy al.22000) (020).
Li al. 2022b), and molecular classification [He et al. 2022). In addition, several industries have deployed/open-sooured their FedGL frameworks, such Alibaba's FederatedScope- GNNN (Wang el al. 2022b and Amazon's FedML-GNN [Vidya et al.). However, FedGL models are typically left unprotected, rendering them vulnerable threats like illegal copying, model theft, and malicious distribution. For instance, a business competitor may replicate a model to gain competitive advantages malicious user may sell the model for profits. These threats waste the model owner's 's investment (e.g., labor costs, time, and energy) and infringe upon the legitimate copyrights of the model.
Backdoor-based watermarking [Uchida et al. 2017] Adi er al. 2018 Bansal et al. 2022 is de facto model ownership verification technique mitigate the above threats. This technique typically consists of two steps: 1) Embedding the target model with watermark. The model owner injects specific backdoor trigger (i.c., watermark) into some clean samples and trains the target model with
CCorrssponiing Author (bwang70@iit.edl)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Results of adapting the random graph- watermarking GL method [Xu et al. 2023 to watermark FedGL models. "MA": main task accuracy: "WA": watermark accuracy.
Datasets
Attack
Fed-GIN WAT
Fed-GSAGE MA1 WAT
Fed-GCN WAt
Datasets
Attack
Fed-GIN
Fed-GSAGE
Fed-GCN
MA1
MA
MA
WAT
MAT
WAT
MAT
WAT
Nome
0.82 0.47
0.82
0.42
0.80
0.43
None
0.71 0.56
0.70
0.54
0.70
0.52
MUTAG
Distillation
0.38
0.80
0.35
0.75
0.32
PROTEINS
Distillation
0.71 0.30
0.70
0.32
0.70
0.28
Finctuning
0.82 0.33
0.80
0.29
0.78
0.27
Finetuning
0.71 0.27
0.70
0.29
0.70
0.25
Layayer Pert.
0.78 0.24
0.79 0,23
0.79
0.19
1-Layer Pert.
0.67 0.16
0.65
0.15
0.68
0.17
None
0.73 0.39
0.70
0,38
0.71
0.38
Nore
0.73 0.57
0.71
0.57
0,72
0.53
DD
Distillation
0.72 0.32
0.70
0.30
0.70
0.30
COLLAB
Distillation
0.72 0.47
0.73
0.49
0,71
0.47
Finctuning
0.72 0.19
0.70
0.21
0.70
0.22
Finetuning
0.72 0.35
0.72
0.36
0,71
0.40
1-Layer Pert.
0,70 0.11
0.70
0.15
0.70
0.12
1-Layer Pert.
0.67 0.31
0.66
0.26
0.68
0.38
this watermarked data along with the remaining clean data. Then the trained target (watermarked) model could have both high watermark accuracy (i.e., accurately classify testing data with the same watermark as the owner desires) and main task accuracy (i.e., accurately classify clean testing data). 2) Model ownership verification. When suspecting the target model is illegally used by others, the model owner can recruit trusted third party for model ownership verification. Particularly, the true model owner knows how the target model behaves as expected by providing the trusted third party the carefully designed watermarked data, while the illegal parties cannot do so. Notice that, since all the clients have devoted computation and data to the training, they have a strong intention to jointly protect their ownership of the model.
In this paper, we aim to protect the ownership of FedGL models via backdoor- based watermarking. We observe backdoor- -baeed watermarking methods for protecting the ownership of FL model on non-graph data [Li el al.) 2022a Tekgul et al.) 2021 Shao el al. 2022 Yang et al. 2023 I Lansari
el al. 2023) or centralized GL. model on graph data [uu et al. 2023 have been recently developed.
However, applying these methods for protecting FedGl. models faces challenges and weaknesses.
Inapplicable or ineffective: Existing methods for non-graph data cannot be directly applied for graph data. For instance, they require input data have same size, while graphs can have varying sizes; they are unable to consider the connectivity information such as edges connecting nodes in the graph data. The only method for graph data (Xu et al.) [023] uses a naive random graph (e.g.. generated by the ER model [Gilbert [959]) as a watermark. Extending this watermark from centralized GL to FedGL models exhibits unsatisfactory performance, as shown in Table [] For instance, the watermark accuracy is less than 60% in all the studied graph datasets and FedGL models. The core reason is the random graph watermark does not use any graph structure information or client information that are unique in FedGL.
Vulnerable to watermark removal attacks: They are vulnerable to existing watermark removal techniques such as distillation and finetuning (Bansal er al. [2022) (more details in Section 2.3 For instance, as illustrated Table |] distillation can reduce the watermark accuracy to less than 30%.
Lack weak formal guarantees: All these methods do not provide formal robustness guarantees against watermark removal attacks. This could make them even vulnerable to more advanced attacks. For instance, our proposed layer-perturbation attack can further reduce the watermark accuracy, e.g., perturbing only 1-layer parameters of the watermarked model yields only 10% watermark accuracy (while main accuracy is marginally affected). |Bansal et al. [2022] proposed the first certified watermark for centralized non- non-graph learning models against la model parameter perturbation. However, its certified radius is only 1.2, meaning the l2 norm of (usually million- dimensional) perturbation vector cannot exceed 1.2 to maintain the watermark accuracy.
We address all the above issues by proposing certified robust backdoor- based watermark method for FedGL, called FedGMark FedGMark enjoys several properties: 1) Its designed watermarks can handle varying size graphs and utilize both graph structure and client information unique in FedGL models; 2) It is empirically robust to both existing watermark removal attacks and the proposed layer- perturbation attack; and 3) more importantly, it is provably robust to the layer seyer-perturbation attack (the layer parameters can be arbitrarily perturbed), when the number of the perturbed layers is bounded.
IIn typical FL, a server and multiple clients collaboratively train global model stored in the server, which used by all clients for their tasks. Accordingly, in our ownership verification problem in FedGL, all clients design their own watermark data and collaboratively train the watermarked global model, which is for joint ownership by all participating clients. Note that we do not consider the case where the clients did not participate in watermark training. but claim the ownership of the model (actually these clients do not know how do so).

---

Ifi ei)
16l...ff
Sclendd
/0hr60 (A)
Grepho
Edge
Chtinghe:
Sdoadd
Silexdd
105 (B)
(A)
Cikent
Koe Thestigg
KoyNaa
Chees
Cliss
Custoniaed Watcrmark Gencratoe (CWG)
Robust Model Loader (RMEL)
Cortified Rabrattacss Ganruntce
Figure 1: Overall pipeline of the proposed certified watermarks.
Specifically, as depicted in Figure 1 FedGMark consists of two modules: 1) Customized Watermark Generator (CWG): it learns the customized watermark for individual graphs and clients in FedGL, by integrating the edge information from the client graphs and the unique key features of the clients. CWG can significantly enhance the diversity and effectiveness the generated watermarks. 2) Robust Model Loader (RMI.). RMI designs a new GL. model that consists of multiple submodels, where each submodel can be any existing GL model. also introduces a voting classifier for assembling the submodels' predictions. Such design can facilitate deriving the certified watermark performance against the (worst-case) mayer-perturbatio attack.
We evaluate FedGMark on four real-world graph datasets (MUTAG, PROTEINS, DD, and COLLAB) and three FedGL models including Fed-GIN, Fed-GSAGE, and Fed-GCN, whose base GL models are GIN [Xu er al., 2019), GSAGE [Hamilton et al. [017]. and GCN (Kipf and Welling 2017]. respectively. Extensive experimental results show FedGMark achieves high main accuracy and watermark accuracy under no attacks and watermark removal attacks. high certified watermark accuracy, and significantly outperforms the existing method. Such good results demonstrate the potential of FedGMark as a watermarking method to protect the ownership of FedGL. models.
We summarize main contributions of this paper follows:
To our best knowledge, this is the first work to protect the ownership of emerging FedGL models.
We propose a certifiably robust backdoor-basee based watermarking method FedGMark for FedGL.
We validate the effectiveness of FedGMark in multiple FedGL. models and real-world graph datasets under no attack, existing backdoor removal attacks, and worst-case seyer-perturbation attacks.
2 PRELIMINARIES
2.1 Federated Graph Learning (FedGL)
Given graph G (V, as input, GL model for graph classification learns graph classifier that outputs a label f(G) = y E Y for a graph. Here, V, E, Y represent the set of nodes, edges, and labels, respectively.
E {o, 1) xVV| is the binary adjacency matrix G, where A [u), 0g] = there exists edge between nodes v; and Uk. and 0 otherwise, with |V] the total number of nodes. FedGL employs FL techniques [McMahan et al. [017] to collaboratively train GL models with a set of (c.g., T) clients T (1..... ,T') and server. Assuming each client T has set of graphs G', we illustrate the training process of FedGL using the e-th epoch as an example: 1) Initially, the server distributes the global model parameters 0g randomly selected subset of clients Te, where T, S 2) Upon receiving 8.. each client trains its local model parameter H* with its own graphs G and updates its model parameters via SGD, i.e., 0f 0:-1 n70b_ L(os; G.), where L(0.; G represents a loss function, e.g., cross-entropy loss. After training, client submits its update model parameters 0 the server. 3) The server aggregates local model parameters of the selected clients i.e., ( E T and updates the global model parameter, e.g., se+1 = ... Σ.er, 0 via the average aggregation [MMMahan et al. 2017], for the next epoch. This iterative process continues until the global model converges or reaches the maximum number of epochs.
2.2 Backdoor-based Watermarking for GL
Backdoor-based watermarking (Uchida el al. 2017 Adi el al. 2018 Bansal et al. 2022 Xu et al.
2023) adopts the idea of backdoor attack [Bagdasaryan el al. 2020; Wang et al.) 2020; Saha et al.
2020 from the adversarial realm to facilitate model ownership verification. To watermark the GL
3

---

model, assume the model owner has set of clean graphs G and selects subset of graphs Gu C G to inject the watermark. In the existing method [Xu et al. 2023], the model owner first generates random graph (e-g., via the ER-model) as the watermark for each to-be- watermarrkkd graph. For instance, for graph G E G with label y, the generated random graph is G2 (its size is often smaller than G). The owner then attaches G. to G to produce the watermarked graph Gw, where nodes in G are randomly chosen and the edge status of these nodes are replaced by edges in G.. Finally, the owner assigns desired label different from y to Gw. The watermarked graphs together with the clean graphs are used to train the GL model. During model ownership verification, the one who can predict a high accuracy on these watermarked graphs can claim to be the model owner.
We note this method can be extended to watermark FedGL models, where each client can generate its own random graphs as the watermark and train its local model with the watermarked graphs and clean graphs. The server then aggregates the watermarked local models to update the global model.
2.3 Watermark Removal Attacks
We consider three possible watermark removal attacks aiming infringe the FedGL model ownership: distillation and finetuning from (Shaficinejad et al. 2002], and our proposed layer-perturbation attack. In all attacks, the attacker (e.g., malicious user) is assumed to know the target watermarked model.
1) Distillation. This attack has access to some unlabeled data sampled from the same data distribution. To remove watermarks without affecting the target model's 's main task performance, the attacker uses the unlabeled data to distill the target model during training. Specifically, the attacker initializes its model with the target model and labels the unlabeled data by querying the target model. The attacker's 's model is then updated with these unlabeled data and their predicted labels.
2) Finetuning. This attack assumes the attacker has some labeled data. The attacker then leverages the labeled data to further finetune the target model in order to forget the watermark. This attack is shown to pose greater threat than the distillation attack [Bansal el al. 2022).
3) patturi attack. This attack also assumes the attacker has some labeled data. As knowing the target watermarked model (and hence the architecture). the attacker can mimic training an unwatermarked model with the same architecture as the target model using the labeled data. To further test the model robustness, we assume the attacker also knows some true watermarked samples, similar to Diang et al., 2023]. Then, the attacker can replace any layer(s)* parameters of the target model with those from the unwatermarked model to maximally reduce the watermark accuracy on its watermarked samples, while maintaining the main task performance. Our results (e.g.. in Table [ show this peetupeeturbation attack (even only perturbing layer parameters) is much more effective than the other two attacks (even though the whole model parameters can be perturbed).
2.4 Threat Model
We follow existing methods (Shatieinejad et al. [2021] Bansal et al., 2022 Xu et al., 2023 Jiang el al. 2023). where the adversary is assumed to know all details of the pretrained watermarked FedGL model, but does not tamper with the training process. This means all clients and the server are benign and follow the federated training protocol, and the attack happens at the testing/inference time. We highlight this is in stark contrast to the training wrimein-tiime Byzantine attack on FL where some clients are malicious and they manipulate the training process.
Attacker's knowledge. The attacker has white-box access to the pretrained watermarked FedGL model. In addition, the attacker may also know some clean (unlabeled or labeled) training data, as well as watermarked data. Note that this setting actually makes our defense design the most challenging. If the defense can successfully defend against the strongest white-box attack on the watermarked FedGL model, will also be effective against weaker attacks, such as black-box attacks.
Attacker's capability. The attacker can modify the pretrained model via leveraging its white-bon box access to the trained model and its hold training and watermarked data. For instance, the attacker can finetune the pretrained model via the labeled training data. More details of the capabilities of considered attacks are described in Section 2.3
Attacker's 's goal. The attacker aims to remove the watermark based on its knowledge and capability, while maintaining the model utility. This allows it to illegally use the model without detection.

---

3 FedGMark: Our Certified Robust Watermark for FedGL
3.1 Motivation and Overview
Recall that the random graph based watermark is unable to ensure high watermark accuracy for protecting FedGI. (as shown [.. This is because such random watermark does not use any graph structure or client information during FedGL. training. Our results also show this method is vulnerable to the three watermark removal attacks. These weaknesses inspire us to design a more effective and robust watermarking method specially for FedGL model ownership verification.
We propose FedGMark, the first certified robust backdoor-based watermarking method for FedGL. FedGMark comprises two main components: Customized Watermark Generator (CWG) and Robust Model Loader (RML) (as depicted in Figure []] The CWG module utilizes the unique property of each client, as different clients could have difterent properties (e.g., distributions of their graph data) and their optimal watermark could be different. Particularly, CWG learns the customized watermark for each graph using its structure information, and outputs set of diversified watermarked graphs for each client. Further, inspired by existing GNNs [Xu al. 2019], the RML module designs new GL model that consists of multiple submodels, each being any existing GL. model. It also introduces a voting classifier for aggregating the prediction results from the submodels. Under this design, FedGMark can be proved to be certified robust against the worst-case eyyer-petturbation attack, once the number of perturbed layers bounded. The model owner (e.g., participating clients in FedGL) adopts the designed GL model to train the local watermarked model with the learnt watermarked graphs and the remaining clean graphs. After the server-client training terminates, the ownership of the trained FedGL model can be verified via measuring its performance on set of testing graphs injected with the global watermark, which is the integration of all clients' local watermarks.
3.2 Customized Watermark Generator (CWG)
CWG consists of two networks: GatingNet and KeyNet. GatingNet designs the watermark for each graph separately using the edge information, while KeyNet learns client-wise watermarking style using predefined keys (e.g., client ID in this paper). The customized watermark for each client's graph is then decided using the output of GatingNet and KeyNet. Detailed network archilectures of CWG can be seen in Table 7 in Appendix C We demonstrate how CWG can learn a customized watermark using a graph G = -Vi, ED') from client i as an instance. The details are as follows:
We first randomly select nw nodes V {(i,--. ... Un... from V as watermark nodes and construct a corresponding mask matrix M' E (0, 111l">//VV such that M [uy. Us] = 1 if Uj. Uk E V and 0 otherwise. We also update the adjacency matrix A' of G according to V i..., setting A [[,, 2y] =
0, Vuy, 2i Vi o-- This allows us focus on learning the edge status between watermarked nodes.
Given the client i's ID string k", we utilize cryptographic hash function, such as MD5, to convert it into an integer (e.g., 128-bit long with the integer range [0, 2 1)). This integer is then employed as a seed to produce a key matrix K E g v'l, Then, we employ GatingNet and KeyNet to extract edge features and key features, resulting in A GatingNettAA) E [0, 1] 1| and (Ky) [o, 101" respectively.
K
We finally Iearn the customized watermark for G by integrating A K' and M', and obtain the corresponding watermarked graph as G = (Vi 1E Here E, is the set of edges according to the updated adjacency matrix A + W', where ① is the element-wise addition and W I((Á' O K') > 0.5) @ M' contains the edge status between the watermark nodes Vi Here, @ is the element- wise product, I(()) is indicator function returning if p is true, and 0 otherwise. We adopt 0.5 as a threshold to decide the presence of edges between watermarked nodes.
3.3 Robust Model Loader (RML)
This module aims design GL model that is provably robust to the layer- peverperturbation attack. Towards this end, we design a GL model architecture to incorporate multiple submodels; and devise majority voting- yoting-based ensemble classifier top of the predictions of these submodels.
Architecture of the proposed GL model. Intuitively, each client can take a base GL model (e.g.. GIN [Xu et al. 2019]) and split it according to the layer indexes to obtain multiple submodels. For instance, a 8-layer GIN can be represented with layer indexes (4, ...... .ls). Splitting this GIN into submodels (GIN1," GIN,} with layer indexes {4 12, [4,, ds means GIN, contains layers
5

---

(121-1.2s1 last, , from the GIN. However, submodels splitted in this way are coupled from each other, making them unable to defend against layer- peyeerperturbation attacks. To tackle this problem. we design the novel GL. model 0 that is an ensemble of set of S independent submodels (01, 12, 0s where each submodel v2 is a base GL model. This approach can hence be easily adapted any existing FedGL. Further, to prevent homogeneity, we define varying channels for these submodels to diversify them. Details of the model architecture are shown in Table S in Appendix
A majority-voting based ensemble classifier. The designed GL model architecture inspires us to leverage the idea of ensemble classifier, which can combine the predictions of base "weak" classifiers. Specifically, we propose majority voting- based ensemble classifier to combine the predictions of the submodels. Given a testing graph G and a graph classifier f, we denote the prediction of the submodel 9, for G as y = f G) E Y. For GL model @ with S submodels { 02 ss), we count the submodels that classify G to be y as N, Ei= ((, G) y). Then we introduce our majority-voting based ensemble classifier to classify G as: 9(0, G) = arg maxyev Ny. In cases of ties, our ensemble classifier g selects the label with smaller index.
3.4 Training the Proposed FedGL Model
The overall training process consists of three iterative steps: 1) training the proposed GL model in all clients; 2) training the CWG module in watermarked clients, i.e., the clients that aim to inject watermarked graphs for protecting the model ownership; and 3) aggregating the clients' GL models to produce the target watermarked model. The final global model is the learnt watermarked FedGL model. Details of training can be seen in Algorithm I in the Appendix.
Step 1: Training the proposed GL model. Assume we have Tw watermarked clients with indexes [1, Tw.. For each watermarked client i, we split its training graphs G into the watermarked graphs G with target label, say Vu. and remaining clean graphs G. and then customize the watermark for each graph in G using the CWG module (see Step 2). Given the client's GL. model 6 with S submodels {u)i, . 12.
I' we train each submodel 0) via minimizing the loss on G. and G i.e.,
O) = arg minn, T(0); G UG For an unwatermarked client i E [Ter w: + 1, T), utilize all clean graphs G* to train each submodel off separately, i.e.. 0j arg ming; L(0). G*).
Step 2: Training the CWG. We denote the parameters of the CWG module for a watermarked client i E Tw).. [.]. as w. The parameters include two networks, GatingNet and KeyNet. Each client i trains its CWG w² to ensure that the generated watermarks be effective and diverse. Formally, we have w = arg min,, L(0'; G i E [w.
Step 3: Aggregating clients' GL models. The server averages GL models {0' her to produce the global model 0, and distributes this model to selected clients in the next iteration.
3.5 Model Ownership Verification
When suspecting the target FedGMark model 0 is illegally used by others, the model owner (all the participating clients their representative) verification. Typically, the judge requests both the true model owner and the illegal party to provide some test data for verification. Only when the one knows the predictions by the target model for the provided test data by both parties, the judge will confirm this party the model ownership. In particular, besides providing the clean data G by both parties that behave normally, the true model owner especially provides the designed watermarked data G that only s/he knows the model behaves on. As result, both parties know the prediction results on G but the illegal party is hard predict accurately on G provided by the true model owner.
recruit trusted judge for model ownership
3.6 Certified Robustness Guarantees against Layer-Perturbation Attacks
We show the above design, with any layer- peverreetuurbaion attack, ensures the predictions of the learnt wa- termarked FedGL model and its compromised counterpart for the watermarked graphs are consistent, once the number of perturbed layers is bounded. Given the target watermarked FedGL model 0 and its S submodels { 0s). we denote 0' as the comprised model and [NI,.... : O'g} as its S sub- models. For each watermarked graph Gw,, we the ensemble classifier g on submodels' predictions, i.c., its predictions on 0 and 0' are g(0, Gw) = arg max and g(0', Gw) arg max,erN', respectively, where N, = , (1,,,, G) = y) and N = = (8', G) = y). Then we have the following result guaranteeing the number of perturbed layers on the target watermarked model.

---

Theorem (Certified number of perturbed layers r.) Let 0, 8', 9, and Gw be above defined. Sup- pose N and NB are the largest and second largest count outputted by g on G For any layer- perturbation atlack, we have g(0, Gw) =g(0", Gw),, when the number of perturbed layers satisfies:
rSr (NA NB + I[A < -) 12
(1)
where I[|] is the indicator function and r is called the certified number of perturbed layers.
We also show the tightness of our derived r* in the following theorem:
Theorem (Tightness of r" Without using extra information of f. our derived r" in Theorem is
right. l.e., r" is the maximum number of perturbed layers tolerated by our target watermarked model.
The proofs of Theorems 1 and are deferred to Appendix A
4
Experiments
In this section, we comprehensively evaluate FedGMark on multiple datasets, FedGL models, attack baselines, and experimental settings, More experimental results and discussions are in Appendix.
4.1
Experimental Setup
Datasets and models. We evaluate our FedGMark on four real-world graph datasets for graph
classification: MUTAG (Debnath et al. 1991], PROTEINS [Borgwardt et al. [005]] DD [Dobson
and Doig 2 and COLLAB Yanardag and Vishwanathan 2015]. Details about the statistics of
those datasets are shown in io Appendix C Following prior work (Shen et al.) [2022] Xia er
al.] [2024, J, we choose the well-known GIN (Xu al. 2019), , GSAGE (Hamilton al.] 7]. and
GCN [Kipf and Welling 2017) as the GL model. All these network architectures involved in the experiments are detailed in Table in Appendix C
Parameter setting. We implement our method using one NVIDIA GeForce GTX 1080 Ti GPU.
In FedGL, we use T 40 clients in total and train the model 200 iterations. The server randomly selects 50% clients in each iteration. We define the target label of watermarking graphs as 1, and each participating client randomly selects 10% graphs with labels not 1 as the watermarking graphs. We extensively validate the effectiveness and robustness of the proposed watermarking method with the following hyperparameters details: the number of submodels S {4,8, 16), the number watermarked clients To = (5. 10, 20} (both S and Tw are halved on MUTAG due to less data), the watermarked nodes Tu = [3. 4, 5). and the number of perturbed layers r = {1.... .5 in the peyrr-petturbation attack. By default, we set S = 4, Tw = 10, The 4, r = 1. While studying the impact of a hyperparameter, we fix the others as the default value.
Evaluation metric. We use three metrics for evaluation: the main task accuracy (MA), watermark accuracy (WA), and certified WA (CWA@r). An effective and robust watermarked model is expected to achieve both high MA and WA. CWA evaluates the certified robustness of FedGMark against layer-perturbation attacks. CWA@r is defined as the fraction of testing graphs that are provably predicted as the target label, when at most r layers in client models can be arbitrarily perturbed.
Attack baselines. We evaluate FedGMark against existing watermark removal attacks including distillation and finetuning, and our proposed layer-perturbation attack. In our setting, the layer- perturbation attack can replace any layer(s)' parameters of the target watermarked model with those from the unwatermarked model to maximally reduce the watermark accuracy on its watermarked graphs. When perturbing multiple layers, we utilize a greedy algorithm to decide the perturbed layers-we we search for one optimal perturbed layer at each step. Specifically, we first traverse perturbing layers in the watermarked model and find the one that maximally reduces the watermark accuracy. We then search for the remaining layers based on this one and continue the process.
4.2 Empirical Results: MA and WA
4.2.1 Results under the Default Setting
We first assess our FedGMark against empirical and puttrrperturbation attacks under the default setting. Experimental results are provided in Table 2
We have the following observations:
1) Our FedGMark significantly outperforms the existing method under no attack. Recall in Table D that [Xu et al. 2023) obtains < 60% WAs across datasets and FedGL. models. In contrast, FedGMark can achieve WAs > 70% in almost all cases, while having similar MAs.
7

---

Table 2: Results of our FedGMark under empirical watermark removal attacks.
Datasets
Attack
Fed-GIN MAT
Fed-GSAGE
Red-GCN MA1
Datasets
Attack
Fod-GIN MAT
Fed-GSAGE
Red-GCN
WAT
MA1
WA
WAT
WAT
MA1
MA1
WAT
None
0.81
0.90
0.85
0.89
0.83
0.83
Nome
0.72 0.86
0.72 0,82
0.73 0.84
MUTAG
Distillation
0.83 0.87
0.81
0.70
0.80
0.80
PROTEINS
Distilationn
0,70 0.34
0.70
0.80
0,70
0.79
Finctuning
0.82 0.88
0.79
0.76
0.78
0.81
Finctuning
0,70
0.34
0.71
0.82
0.72
0.80
L-Lyyer Pert.
0.82 0.90
0.83
0.91
0.81
Layyerr Pert.
0.73
0.86
0.74
0.83
0.74
0.85
None
0.73 0.65
0.74
0.57
0.74
0.56
None
0.73 0.75
0,74
0.74
0.73
0.70
Distillaionn
0.56
0.72
Distillation
0.70
Finetuning
0.72 0.62
0.74
0.57
0.74
0.55
Finetuning
0.72 0.70
0.75
0.71
0.72
0.67
L-Layer Pert.
0.72 0.65
0.75
0.55
0.73
0.57
L-yyeer Pert.
0.72 0.76
0.73
0.74
0.74
0.71
clarz)
dios)
claani
clack)
chust]
MUTAG
PROTEINS
DD
COLLAB
Figure 2: Example learnt watermarks and watermarked graphs by FedGMark. CWGs generated by different clients produce unique watermarks, characterized by distinct edge connection patterns.
Table 3: Impact of on FedGMark against our layer-perturbation attack.
Datasets
Attack
Fed-GiN MAT WAT
Fed-GSAGE
Fed-GCN MA1 WAt
Datasets
Attack
Fed-GIN
Fed-GSAGE
Fed-GCN
(S 8)
MA WAT
MA1 WAT
MA1 WAT
MA1 WA1
MUTAG
None
0.83 0,93
0.83 0.92
0.78 0.87
PROTEINS
None
0.73 0.86
0.71 0.85
0.74
I-Layer Pert.
0.84 0.92
0.79 0.76
I-Layer Pert.
0.70 0.86
0.71
0.73
None
0.57
0.74 0,50
0.72
I-Layer Pert.
0.72 0.56
0.73 0.50
0.74 0.50
I-T Lyer Pert.
0.73 0.72
0.74 0.75
0.72 0.72
(S = 16)
None
0.83 0,90
0.86 0.87
0.79 0.79
PROTEINS
Nonc
0.72 0.86
0.72 0.85
0.71 0.85
MUTAG
I-Layer Pert.
0.81 0.90
0.84 0.86
0.79 0.80
I-Layer Pert.
0.73 0.86
0.72 0.85
0.73 0.85
DD
None
0.70 0.61
0.74 0.54
0.73 0.50
COLLAB
None
0.71 0.76
0.72
0.74
0.72 0.72
Layer Pert.
0.73 0.61
0.74 0.54
0.74
0.50
Layer Pert.
0.71 0.76
0.71 0.73
0.72 0.72
Such significant improvements confirm the superiority of our learnt watermarks over the random watermarks in [Xu al. 2023). Figure also visualizes example learnt watermarks and we see these watermarks are diversified due to the proposed CWG.
Our FedGMark exhibits resistance existing empirical attacks. As shown in Table existing methods are vulnerable to distillation and finetuning attacks. In contrast, the WAs of FedGMark under these two attacks are almost the same as those under no attack, demonstrating FedGMark is robust to the existing attacks.
3) Our FedGMark is resilient to the proposed layer perturbation attack. We notice that the existing method has difficulties in defending against the proposed layer-perturbation attacks and shows an unsatisfactory WA, e.g., < 25% WA in almost all cases under the 1-layer perturbation attack. Conversely, FedGMark obtain close WA compared that without attack. This verifies our ensemble classifier in FedGMark is capable of resisting the 1-layer perturbation attack.
4.2.2 Impact of Hyperparameters
This section studies the impact of hyperparameters in FedGMark against the seyerrperturbation attack.
Impact of #submodels S. We first examine the impact of S on the performance of FedGMark and report the results against the 1-layer perturbation attack Table We observe that the learnt watermarked model can resist to the 1-layer perturbation attack under all S and both the MAs and WAs are also similar. This indicates the number of submodels marginally affects the watermarking performance against the 1 lllayer perturbation attack.

---

Table 4: Impact of #perturbed layers on FedGMark against our layer-perturbation attack. Compared with Table 2 the change in MA is less than 4% in all cases.
Datasets
#Perturbed Layers
1
3
4
Datasets
#Porturbed Layers
1
3
4
(Net)
WAT
WAT
WAT
WAT
WAT
(Net)
WAT
WAT
WAT
WAT
WAT
Fed-GIN
0.90
0.89
0.54
0.23
0.16
Fed-GIN
0.86
0.84
0.58
0.46
0.39
MUTAG
Fed GSAGE
0.91
0.89
0.55
0.21
0.13
PROTEINS
Fed. GSAGE
0.83
0.81
0.55
0.45
0.44
Fod-GCN
0.84
0.83
0.49
0.24
Fod-GCN
0.85
0.82
0.57
0.48
0.41
Fod-GIN
0.65
0.56
0.32
Fed-GIN
0.76
0.58
0.36
Fed-GSAGE
0.58
0.55
0.49
0.28
COLLAB
Fod-GSAGE
0.74
0.57
0.35
Fed.GCN
0.57
0.54
0.48
0.29
0.24
Fed-GCN
0.71
0.70
0.52
0.32
0.21
0.4
Fed
0.2
0.8
0.6
0.4
CWAIT Fed
0.2
2-14
1
3
0
2 #Paturbed Layers:
#Perturbed Layers
#Perturbed Layers
Layors:
MUTAG
PROTEINS
DD
COLLAB
Figure 3: CWA vs. #perturbed layers in the layer-perturbation attack.
Impact of #watermarking clients T. The results on T,, and T. 20 are shown in Figure 4 in Appendix. We see that: the larger number of clients generating watermarks, the better our watermarking performance. For instance, the WA improves by 11%, 9%, and 7%, respectively on the three FedGL. models on PROTEINS when Tw increases from 5 to 20. This is because more watermark clients (thus more watermarked graphs) can ensure the FedGL model better learns the relation between the watermarks and the target label.
Impact of the watermark size n.. We also investigate n. 3 and nh 5, and the results presented in Figure in Appendix. Similarly, FedGMark obtains higher WA with larger n This is because a larger watermark size can facilitate the trained FedGL model better learn the watermark.
Impact of #perturbed layers. Finally, Table 4 shows the results of FedGMark vs. different #perturbed layers. We observe that: 1) The WA decreases increasing the #perturbed layers. This is because the attacker has more attack capability by perturbing more layers. 2) Despite the theoretically guaranteed CWA being 0 #perturbed layers > 3 as later depicted in the Figure 3 our empirical watermarking performance can still achieves WA from 48% to 58%. Note that the change in MA is 4% in all cases, compared with Table
4.2.3 Ablation Study
Table 5: Impact of different modules in FedGMark.
We investigate the contribution of each module in FedGMark, including the GatingNet and KeyNet in CWG, and the submodels used RML. The results under the default setting and no attack are shown in Table 5 First, GatingNet plays a crucial role on generating more effective watermarks and results in an improvement WA from 8% to 21%. Second, KeyNet facilitates watermark differentiation between clients, leading to improve on WA from 5% to 8%.
Models G.Nett K.Net RML
MUTAG PROTEINS DD
COLLAB
MAT
WAT
MA1 WAT
MA
WAT
MA"
WAt
0.81
0.90
0.72
0.86
0.73
0.65
0.73
0.75
(b)
0.81
0.84
0.72
0.80
0.72
0.57
0.72
0.70
0.81
0.89
0.73
0.86
0.11
0.66
0.72
0.75
0.82
0.47
0.71
0.56
0.73
0.39
0.73 0.57
Third, the submodels in RML. has negligible impact on WA/MA. However, it important to defend
against the perturrerturbttoon attack, shown in Section 4.3

---

4.3 Certified Robustness Results: Certified WA
In this section, we evaluate the certified robustness of FedGMark against the layer perturbation attack. The CWAs on the three FedGL models and four datasets are depicted in Figure We have several observations: 1) FedGMark achieves promising provable robustness results against the worst-case layer perturbation attack, when the #perturbed layers is within the certified range in Eqn ① For instance, when S = 4 and 0 < r S 2, CWA is close to WA without attack (r = 0). 2) As S increases, the certified #perturbed layers also increases, showing that more number of submodules in RML can better provably defend against the mayer-perturbation attack. For instance, when S = 16, the CWA is 86% on MUTAG even when 5 any layers in the global model are arbitrarily perturbed, while it is O when S = 4. However, this is at the cost of requiring more computational resources (c.g., GPU memory, runtime). As shown in Table 10 in Appendix, the runtime linearly to S.
5 Related Work
Backdoor-based watermarking for centralized models on non-graph data. Many backdoor-baa based watermarking methods (Lv et al.) [2023] Yan et al., [023] Tekgul et al. [202]] Yang et al.) [023] Li er al. 2022a (hao et al. [222]] Lansari et al. [2023] have been proposed that can empirically protect the model ownership. These methods mainly focus on centralized learning models on non non-graph (e.g.. image) data. Compared with non-graph data, graph data have unique graph structure information, e.g., entities are connected by links. Similarly, compared with centralized models, FL models are collaboratively trained by multiple clients, which could have their own uniqueness. [Bansal ef al. [022] is the first watermarking method for centralized non-graph models with certified guarantee. However, its certified robustness performance is unsatisfactory.
Backdoor-based watermarking for FL models on non-graph data. A few recent works Tekgul er
al. [021]] Li et al. [222a]] ; Bansal er al. [2022] design backdoor-basee watermarks for protecting
the ownership of FL models on non non-graph data, where the watermark can be injected into client's s
data or server's validation data. For instance, Tekgul et al.) [202T) presented WAFFLE, an approach to watermark DNN models by incorporating re-training step via watermarked data at the server. Li et al.] [2022a] leveraged each client's ' private watermark to verify FI. model ownership, ensuring non-conflicting watermarks across different clients. However, these techniques cannot be directly applied to graph data, as they often require fixed input data, while graph data often have varying sizes. Moreover, all these methods do not provide guaranteed watermarking performance under the attack.
Backdoor-based watermarking for centralized GL models on graph data. The only work (Xu er al. 2023) handling graph data uses random graph as the watermark. This method can be extended to the FedGL model, but its watermarking performance is far from satisfactory especcially vulnerable to watermark removal attacks such as distillation, finetuning. and the layer perturbation attack.
Backdoor attacks for centralized and federated GL models on graph data. Several works (Zhang er al.) 202T Yang et al., 2024) design backdoor attacks to manipulate GL models, enabling the attacker to influence the learned model to serve its purpose-the model will predict the attacker-chosen
label for test graphs once they contain a predefined trigger. For instance, Zhang et al. [202]] uses
random subgraphs as the trigger to backdoor centralized GL models, while Yang el al. [0244] learns
subgraph trigger backdoor FedGL models. Note that the goal of these works is orthogonal ours.
Conclusion
We protect the model ownership of emerging FedGL trained on distributed graph data, and use the de facto backdoor-based watermarking method. We develop the first certifiably robust backdoor- watermarking method FedGMark for FedGL. FedGMark demonstrates the capability of achieving high empirical watermarking performance under no attack, under existing backdoor removal attacks and the proposed stronger layer-perturbent worst-case pertuurettur attack, once the number of perturbed layers is bounded by Theorem !
attack. FedGMark is also provably robust against the
Acknowledgments. We thank all anonymous reviewers for the constructive comments. Li is partially supported by the National Natural Science Foundation of China under Grant No. 62072208, Key Research and Development Projects of Jilin Province under Grant No. 20240302090GX. Hong is partially supported by the National Science Foundation under grant No. CNS-2302689, CNS- 2308730, CNS-2319277 and CMMI-2326341. Wang is partially supported by the National Science Foundation under grant No. ECCS-2216926, CNS-2241713, CNS-2331300 and CNS-233966
10

---

References
Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas, and Joseph Keshet. Turning your weakness into strength: Watermarking deep neural networks by backdooring. In 27th USENIX Security Symposium (USENIX Security 18), pages 1615-1631, 2018.
Jinheon Back, Wonyong Jeong, Jiongdao Jin, Jachong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. In International Conference on Machine Learning, pages 1396-1415. PMLR, 2023.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International conference on artificial intelligence and statistics, pages 2938-2948, PMLR, 2020.
Arpit Bansal, Ping-yeh Chiang, Michael J Curry, Rajiv Jain, Curtis Wigington, Varun Manjunatha, John P Dickerson, and Tom Goldstein. Certified neural network watermarks with randomized smoothing. In International Conference on Machine Learning, pages 1450-1465. PMLR, 2022.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017.
Karsten Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, [1(sup(_1):i47- i56, 2005.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-799 797, 1991.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 3044):114111144, 1959.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Chaoyang He, Emir Ceyani, Keshav Balasubramanian, Murali Annavaram, and Salman Avestimehr. Spreadgnn: Decentralized multi-task federated learning for graph neural networks molecular data. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6865- 6873, 2022.
Zhengyuan Jiang, Minghong Fang, and Neil Zhenqiang Gong. Ipeert: Provably robust intellec- tual property protection for machine learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3612-3621, 2023.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pages 5132-5143. PMLR, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Mohammed Lansari, Reda Bellafqira, Katarzyna Kapusta, Vincent Thouvenot, Olivier Bettan, and Gouenou Coatrieux. When federated learning meets watermarking: A comprehensive overview of techniques for intellectual property protection. Machine Learning and Knowledge Extraction, 5(4):1382-1466, 2023.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International conference on machine learning, pages 6357- 6368. PMLR. 2021.
11

---

Bowen Li, Lixin Fan, Hanlin Gu, Jie Li, and Qiang Yang. Fedipr: Ownership verification for federated deep neural network models. IEEE Transactions on Pattern Analysis and Machine Intellignnce. 45(4):4521-455 2022.
Zheng Li, Muhammad Bilal, Xiaolong Xu, Jielin Jiang, and Yan Cui. Federated learning -bsedd cross-enterprise recommendation with graph neural networks. IEEE Transactions on Industrial Informatics, 19(1))673-68 682, 2022.
Peizhuo Lv, Pan Li, Shengzhi Zhang, Kai Chen. Ruigang Liang, Hualong Ma. Yue Zhao, and Yingjuu Li. A robustness-assurgg white-box watermark in neural networks. IEEE Transactions on Dependable and Secure Computing, 2023.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efiie effficient learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pages 1273-1282. PMLR, 2017.
Liang Peng, Nan Wang, Nicha Dvornek, Xiaofeng Zhu, and Xiaoxiao Li, Fedni: Federated graph learning with network inpainting for population-baal based discase prediction. IEEE Transactions on Medical Imaging, 2022.
Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 11957-11965. 2020.
Masoumeh Shafieinejad, Nils Lukas, Jiaqi Wang. Xinda Li, and Florian Kerschbaum. On the robustness of backdoor- based watermarking in deep neural networks. In Proceedings of the 2021 ACM workshop on information hiding and multimedia security, pages 177-188, 2021.
Shuo Shao, Wenyuan Yang, Hanlin Gu, Zhan Qin, Lixin Fan, Qiang Yang. and Kui Ren. Fedtracker: Furnishing ownership verification and traceability for federated learning model. arXiv preprint arXiv:2211.07166.. 2022.
Yun Shen, Xinlei He, Yufei Han, and Yang Zhang. Model stealing attacks against inductive graph neural networks. In 2022 IEEE Symposium Security and Privacy (SP), pages 1175-1992. IEEE, 2022.
Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang. Federated learning on non-iid graphs via structural knowledge sharing. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 9953 9961,9911111 2023.
Buse GA Tekgul, Yuxi Xia, Samuel Marchal, and N Asokan. Waffle: Watermarking in federated learning. In 2021 40th International Symposium on Reliable Distributed Systems (SRDS), pages 310-320. IEEE, 2021.
Yusuke Uchida, Yuki Nagai, Shigeyuki Sakazawa, and Shin'ichi Satoh. Embedding watermarks into deep neural networks. In Proceedings of the 2017 ACM on international conference on multimedia retrieval, pages 269-277,200 2017.
Vidya et al. Fedml supports several out-of-the-box deep learning algorithms for various data types, such of things (iot) data.
tabular, text, image, graphs. and internet https: /wws///ww..aa/ amazon.maaa..cmmmmm how.o//m.ccombooogo///cciieneeee wwtp/maahhineneeeeeeeeeee learning/ 2ete-eefddrate--eearrae -aters-ooowwwsses feamb--emllleeeeee th- ama without shar ing sogg-ensitive-dae data/
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. Advances in Neural Information Processing Systems, 33:16070- 16084, 2020.
Binghui Wang, Ang Li, Meng Pang, Hai Li, and Yiran Chen. Graphfl: A federated learning framework sepi-supe node classification on graphs. In 2022 IEEE International Conference on Data Mining (ICDM), pages 498-507. IEEE, 2022.
12

---

Zhen Wang, Weirui Kuang, Yuexiang Xie, Liuyi Yao, Yaliang Li, Bolin Ding, and Jingren Zhou. Federatedscope gnn: Towards a unified, comprehensive and efficient package for federated graph learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 41 4110-4120, 2022.
Peter Wills and François G Meyer. Metrics for graph comparison: a practitioner's s guide. Plos one, 15(2):e0228728, 2020.
Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Tao Qi, Yongfeng Huang, and Xing Xie. A federated graph neural network framework for privacy-preserving personalization. Nature Communications, 13(1):3091, 2022.
Zaishuo Xia, Han Yang, Binghui Wang, and Jinyuan Jia. Gnncert: Deterministic certification of graph neural networks against adversarial perturbations. In International Conference on Learning Representations, 2024.
Han Xie, Jing Ma, Li Xiong. and Carl Yang. Federated graph classification over non-iid graphs. Advances in neural information processing systems, 34:18839-18852 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Jing Xu, Stefanos Koffas, Oguzhan Ersoy, and Stjepan Picek. Watermarking graph neural networks based on backdoor attacks. In 2023 IEEE 8th European Symposium on Security and Privacy (FuroS& P), pages 11 1199119977 IEEE, 2023.
Yifan Yan, Xudong Pan, Mi Zhang, and Min Yang. Rethinking [White-Bos) watermarks on deep learning models under neural structural obfuscation. In 32nd USENIX Security Symposium (USENIX Security 23), pages 2347-2364, 2023.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
Wenyuan Yang. Shuo Shao, Yue Yang, Xiyao Liu, Ximeng Liu, Zhihua Xia, Gerald Schaefer, and Hui Fang. Watermarking in secure federated learning: A verification framework based on client-side backdooring. ACM Transactions on Intelligent Systems and Technology, 15(1):1-25, 2023.
Yuxin Yang, Qiang Li, Jinyuan Jia, Yuan Hong, and Binghui Wang. Distributed backdoor attacks on federated graph learning and certified defenses. In Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security, 2024.
Yuhang Yao, Weizhao Jin, Srivatsan Ravi, and Carlee Joe-Wong. Fedgen: Convergence- communication tradeoffs in federated training of graph convolutional networks. Advances in Neural Information Processing Systems, 36, 2024.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine robust distributed learning: Towards optimal statistical rates. In International conference machine learning, pages 5650-5659. Pmlr, 2018.
Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. In SACMAT, 2021.
13

---

A Proofs
Proof of Theorem 1 Given a watermarked graph Gw. a base graph classifier f. our ensemble classifier g, and the target watermarked FedGL model 0 { J Let 0' be the watermarked FedGL model after the pertuubertnnattonn attack. We denote by = f(V; Gw) the prediction of G by submodel i, and 9 Gw) = arg max N₂ the prediction of G by the target model 8, where
N₂ - "[ ( largest votes of the output of the ensemble classifier 9 on the target model & and Gu. respectively. Similarly. let Na and N3 B respectively denote the corresponding votes of the model 6'. Under our GL model architecture, each perturbed layer affects most 1 submodel in the worst case. Therefore, N' and N satisfy the following equations when layers in are perturbed:
y) and 0 = { Assume NA and NB are the largest and second
NA NA NA +T,
(2)
NB N NB +r.
Thus, G( = g)00) G) when N > N, This means NA-N -1 > NB +r 1(A < B), where I(A < B) indicates we select label with a smaller index in case of ties. Hence, satisfies:
r rsr NA NB + I(A B) -
Proof of Theorem 2 We use proof by contradiction, i.e., when r >> r", we can build base classifier f' such that there exists s0, Gw) * g(0', Gw.). We select the smallest r = r* + for simplicity, indicating that r + layers whose model parameters can be arbitrarily perturbed. Assume there exist graph classifier f' under which, (r" + 1) submodels whose original predictions on G. are the label A and now become B after r* + layers are perturbed. Then we have N' -Na- (r* + 1) and N = NB + (r* 1). Since r" is the largest number such that Equation (2) is satisfied, i.e. NA- - 1* > NB - 1(A < B) + r holds. Thus,
NA (r" + +1) - NB - 1(A < +)+ (r" +1).
Or N < Nz. Hence, g(0, G.)) = A + B = a000/OG.gaa if A>> B.
B Algorithm 1
Algorithm 1 The training process of FedGMark
Input: clients TJ. watermarked clients [1, Tw., training graphs G' (i E [1, initial global model CWG wi, #Perturbed Layers r, unique key k for client i E [1, T..)). the number of submodels S. Output: Target global model Oepoct, and target local models 0² spock (j E [1, Tw]).
0,, initial
1: for each epach in [1, epoch] do each client i E [1, T)
3:
if E ['.] then
4:
Divide G' into G and G D> clean & watermarked samples G CWG(GG k²)
6:
end if
7:
01, 02,- Og divide(0.)
8:
for each submodel j in [1, do
9:
83 arg min L(0,; G*)
10:
end for = joint(
00 0i. if [1, Tw then
0%))
12:
13:
w arg min L (0 Gl,)
14:
15:
end for
16:
0.+1 Te Eier, 0: i- Server selects T. clients for aggregation
17:
end for
14

---

Table 6: Statistics of datasets.
Datasets
#Graphs
#Classes
Avg. #Node Avg. # Edge
#Training graphs
#Testing graphs
1
2
3
2
MUTAG PROTEINS
188
2
17.93
19.80
83
42
42
21
1110
2
37.72
70.35
440
300
220
150
DD COLLAB
950
2
208.3
518.76
330
303
165
152
4981
3
73.49
2336.66
517
1589
1215
258
794
608
Table Detailed network architectures of CWG.
Name
Network Architectures
Input
Output
GatingNet
2 (Linear- |Vlearr///&&aa ReLU & Dropout-0.05)
A' {0, 1IMII
A' [0. 1].1111117)
Linear- [V| & Sigmoid
KeyNet
2 (Linear-|W]]4 ReLU & Dropout-0.05.
K E
K E [0. M|
Linear- V Sigmoid
Table 8: Detailed network architectures for S = {4, 8, 16) in Fed-GIN, Fed-GSAGE, and Fed-GCN models within our watermark. The convolutional (conv) layers in these three models are GINConv, GSAGEConv, and GCNConv, respectively. Here, x represents the input dimension, while y represents the output dimension. BN is short for BarchNorm.
submodels 1-4
submodels 5-8
submodels 9-16
Linear-r X M
Linear-r X y
Linear-w X y
Linear-z X
conv-2x64 64 & BN-64
conv-ix 128 & BN-128
ConV- 72 & BN-72
conv- 96 & BN-96
ReLU & Linear-64xy
ReLU & Linear- 1
ReLU & Linear-22xy
ReLU & Linear-96x,,
2x (conv-64x66) x4 & BN-64
2 (conv-122 128 128 BN- IN-1288
2 (conv-72272 & 2 (conv-966x
& BN-96
ReLU & Linear-64 x4)
ReLU & Lincar-10 128 xy)
ReLU & Linear-72xy)
ReLU & Linear-96x:
conv-64x64 64& & BN-64
conv-128x64 & BN-64
conv-72x64 & BN-64
conv-96x 64 & BN-64
ReLU & Linear-64xy
ReLU & Linear-64
ReLU & Linear-64xy
ReLU & Linear-64xy,
Linear-x y
Linear-2 y
Linear-2 X y
Linear-z X y
c4 & BN 66
conv- 128 & 128-128
conv-2x72 & BN-72
conv-rx96 & BN-9
ReLU & Linear-64 xy
ReLU & 1iinarr-188-
ReL.U & Linear-72xx
ReLU & Linear-96x,,
2 (60nv-64x64 & BN-64
2 (conv-128x x 128 & BN-
(comV-72272 72 & BN-72 2 2x(cmv-96x996 & BN-96
ReLU & Linear-64xx y)
ReL.U & Linear- 12aaarr--2:: 128x
ReLU & Linear-72xg)
ReLU & Linear-96xy)
conv-64x32 BN-32
conv-128x32 & BN-32
conv-72x32 BN-32
conv-96x32 & BN-32
ReLU & Linear-32
ReLU & Linear-32xy
ReLU & Linear-32xy
ReLU & Linear-32xy
Linear-J: y
Lincar-2 y
Linear-2 X y
Linear-z X
co & BN-64
conv-a 128 & BN-128
conv-rx72 & BN-72
conv-a & BN-96
ReLU & Linear-64xy,
ReLU & Linear- 128xy
ReLU & 7ixear-22xy
ReLU Linear-96
2 (conv-64x64 & BN-64
2 (conv- 12w x 128 & BN-128
2 (conv-72277 72 & BN-72 2x(con-996x96 & BN-96
ReLU & Linear-64x
ReLU & Linear- 128 xy)
ReLU & Linear-72xx
ReLU & Linear-96xy)
conv-64x 16 & BN-16 16
conv-128 16 & BN-16
conv-72 16 & BN-16
conv-96 16 & BN-
ReLU & Linear-
16xy -enear-16xgg
ReLU & Linear-16:: 16xy
ReLU & Lincar- 16xy
ReLU Linear-
Linear-r X y
Linear-r X y
Linear-2 X y
Linear-z X
conv-2x64 & BN- -N-
conV-2x 128 & BN-128
conv- 72 & BN-72
conv-zx96 & BN-96
ReLU & Linear-64
ReLU & Linear- Linear-128xy
ReLU & Linear- 72xy
ReLU & Linear-96
2x cconv-64x60 & BN-64
2 (conv- 128 128 BN-
(conV-72272 BN-72
2x (conv-96x99 & BN-96
ReLU Linear-64x y) conv-64 x8 & BN-8
ReL.U & Linear- 1heea-128x9p 128x
ReLU Linear-72xy)
ReLU & Linear-96xy)
conv-1 10m--128x40 x & BN-8
conv-72x8 & BN-8
conv-96x8 & BN-8
ReI.U & Linear-8x0 xy
ReLU & & Linear-8 8 x
ReI.U & Linear-8xy
ReLU & Linear-8xp
C More Experimental Details
Table shows the statistics of the used graph datasets. Table shows the network architectures of the CWG component. Table shows the detailed network architectures of Fed-GIN, Fed-GSAGE, and Fed-GCN models.
15

---

MA
WA
Fod-GIN
Fod-GSAGE
Fod-GCN
MA WA
MA WA
Desillation
Fineuning T
Finttuing
To
finetuiing T, None (b) PROTEINS
Fanstning
(a) MUTAG
MA WA
MA WA
T.:55: Nore
Desillation
Finetuiig To 20: Nome Divillation
Fineturing
Ta 5: Note
Dedilition
finetuning T 20: None
Des latton
Fineluning
(c) DD
COLLAB
Figure 4: Impact of Tw on FedGMark against prior watermark removal and layer- attacks.
MA
WA
Fed-GIN
Fed-GSAGE
Fod-GCN
MA/ WA
MA WA
1t Nore Dediliatoon
Erituring
% 5. None Devilation
Finsturigg
1: None
Dali Dalilation
firetuning
Fu
Mone
Des lution
Finsluning
(a) MUTAG
(b) PROTEINS
MA WA
MA WA
Distilation
Freetning
None
Decillatiann
Finsturing
None Dibilltioo
Dist Balton
Fineluning
(c) DD
(d) COLLAB
Figure 5: Impact of nw on FedGMark against prior watermark removal and syyer-perturbatioon attacks.
Table 9: Effect of learning rate (lr) and #local epochs (le).
le 5
Ir = 0.01
Datasets
Ir = 0.01
Ir = 0.05
Ir = 0.1
le = 5
le = 10
Ic =
20
MA1
WAT
MA1
WAT
MA
WA
MA WAT
MA WAT
MA
WA
MUTAG PROTEINS
0.81 0.90
0.84
0.79
0.90
0.90
0.84
0.90
0.76
0.92
0.72 0.86
0.71
0.71
0.73
0.72
0.86
0.72
0.87
0.89
DD
0.73
0.65
0.71
0.57
0.70
0.53
0.73
0.65
0.73
0.66
0.73
0.69
COLLAB
0.73 0.75
0.72
0.71
0.70
0.65
0.73
0.75
0.74
0.75
0.73
0.77
D More Experimental Results
Impact of #watermarking clients T,, and watermark size nw See results in Figure S and Figure 5 respectively. We can see FedGMark achieves better watermarking performance with a larger number of clients generating watermarks; and larger watermark size.
Impact of learning rate (Ir) and #local epochs (le). The results with varying Ir and le are shown in Table 9 in Appendix. We see that large ir may reduce WA, and WA increases slightly le grows, iddiating more thorough training makes our method perform better.
Scalability of Mark. Compared with graph-based or non-robust watermarking methods, the computation overhead FedGMark mainly from the introduced submodel models (fixing all other parameters, such as #clients, #iterations, to be the same). Particularly, the overhead scales linearly with the number submodels and the runtime results are shown in Table I0
FedGMark under watermark/backdoo detection attacks. Many existing works [Zhang er al.
202T] show the trigger-reverse based backdoor detection ineffective to "stealthy" backdoor. This because the effectiveness of trigger reverse attacks largely depends on the statistical differences between clean data and backdoored data. Since do not notice any graph backdoor trigger- attack, we instead propose to quantitatively test the structure similarity between the generated watermarked graphs and the clean graphs. Here we use the metries NetSim and DeltaCon proposed in Willss and Meyer 2020), with the range [0, 1] and the higher value the larger similarity. As shown Table we observe watermarked graphs and their clean counterparts are structurally very close. This implies that the proposed watermarks are hard to be detected.
16

---

Table 10: Number of submodels S vs. the runtime of RML. We observe an almost linear relationship between the total training time Ct and the number of submodels S, expressed C2 R C.. where C, denotes the training time for an individual submodel.
Datasets
S
4
16
Datasets
5
8
16
(Net)
time(s)
(Net)
time(s)
Fed-GIN
0.46
0.74
1.32
Fed-GIN
2.79
5.10
9.49
MUTAG
Fed-GSAGE
0.28
0.48
0,90
PROTEINS
Fed-GSAGE
2.72
4.25
8.31
Fed-GCN
0.30
0.53
0.94
Fed-GCN
2.73
4.56
8.95
Fed-GIN
11.14
20.12
36.74
Fed-GIN
161.46
296.68
563.51
DD
Fed-GSAGE
11.75
19.82
31.57
COLLAB
Fed-GSAGE
152.23
281.78
551.86
Fed-GCN
11.61
19.51
33.23
Fed-GCN
163.03
293.55
544.17
Table 1I: Structure similarity of generated watermarked graphs and clean graphs.
Datasets
MUTAG
PROTEINS
DD
COLLAB
NetSim (1)
0.97
0.98
0.99
0.99
DeltaCon (1)
0.98
0.98
0.99
0.99
Table 12: Results of FedGMark on IID and non-IliDhheterggeneous datasets.
Datasets
MUTAG
PROTEINS MA WAT
DD
COLLAB
MA1
WA
MA1
WAT
MA
WA
IID
0.81
0.90
0.72 0.86
0.73
0.65
0.73 0.75
Non-IID
0.80
0.89
0.72 0.83
0.72
0.63
0.75
Table 13: Results of FedGMark against p% malicious clients whose watermarked data are mislabeled.
0%
10%
20%
30%
40%
MUTAG
.81/.90
.80/90
.80/89
.80/.80
.80/711
PROTEIN
.72/.86
.72/.85
.72/.76
.71/.67
.70/667
DD
.73/.65
.72/.63
.721.58
.71/.53
.71/.52
COLLAB .731.75
.741.74
.731.68
.73/.61
.72/.60
FedGMark non-IID/heterogeeneou datasets. Recall that the local watermarks in FedGMark are learnt by considering the unique properties in each client. Such unique properties may include the heterogeneity across clients' data. To validate this, also test FedGMark with non-IID graphs across clients and show results in Table 12, where each client holds a single label data. We observe that FedGMark demonstrates strong performance non-IID datasets, indicating that the learnt customized watermarks effectively capture the heterogeneity of clients' graphs.
FedGMark against more Knowledgeable/stronn clients and the server are benign and assume the attacker does not know our CWG. Here, we test FedGMark against stronger adversaries, where some clients malicious and the these malicious clients also has access to the CWG component to manipulate the FedGL training. First, we consider a passive attack where all malicious clients do not CWG to generate customized local watermarks. Model (b) in Table 5 shows the maximum WA decrease is 9%, where all clients do not use CWG.
ad advessaries. In our threat model, assume all
Second, we test an active attack where malicious clients modify their watermark data's label to obfuscate the training. Specifically, all malicious clients' watermark data are labeled (c.g., 2) differently from the target label (e.g.. 1) and then follow the federated training. The results in Table 13 show MA/WA is marginally affected even with 20% malicious clients.
FedGMark with alternative aggregation methods. The current FedGMark's evaluation focuses on FedAvg for aggregating client models. Here, we evaluate FedGMark using Multi-Krun -rum (Blanchard et al. 2017] and Trim-meat mean (Ynn et al. [2018) aggregation methods that consider data quality (e.g.. remove outlier clients). Specifically, Multi-Krum filters set of p clients whose gradients largely deviated from others, while Trim-mean trims off q highest and lowest values for each parameter in clients' models. Table shows the results with p = 10 and q = 10. We can see these robust aggregators achieve robustness-utility tradeoff, and MA and WA are not largely different.
17

---

Table 14: Results of our FedGMark against Multi-Krum
Blanchard et al. 2017 and Trim-mean Yin
al. 2018 aggregation methods.
Datasets
MUTAG MAT
PROTEINS MAT
DD
COLLAB
WAt
WAt
MA
WAt
MA1
WAT
Avg
0.81
0.90
0.72 0.86
0.73 0.65
0.73 0.75
Multi Krum
0.78
0,92
0.73
0.85
0.72
0.63
0.73
0.74
Trim-mean
0.75
0.93
0.70
0.87
0.70
0.65
0.71 0.77
Table 13: FedGMark with alternative triggers.
Datascts
feature
structure
feature-structure
MUTAG PROTEIN
81/.78
81/.90
.79/992
.721.77
.721.86
.73/.87
DD COLLAB
.721.53
.73/66
.74/.66
.71.677
.73175
.72/.76
0.9
0.9
0.7
0.8
0.8
WA
WA
WA
0.7
0.8
0.7
Icall
lood
0.5
0,6
0,7
Fed GIN Fed GSAGG Fed GCN
Ted-GIN GIN Fed GSAGE Fed GCN
Fed GIN
Fed GSAGE Fed Fed-GCN
Fed GIN Fed Fed GEAGG Fed GCN
MUTAG
PROTEINS
DD
COLLAB
Figure 6: Global watermark vs. local watermarks 1-4.
FedGMark with alternative triggers such as feature-based triggers and hybrid triggers. The current. FedGMark relies on graph structural information to learn the trigger used in watermark. Here, we adjust FedGMark to learn feature-based triggers and hybrid feature-structure triggers.
To learn feature-based triggers, we first select set of nodes from graph as the target nodes, and learn the watermarked features for the target nodes (we do not watermark structure). We use graph G (V', E', X') from client i for illustration, where X is the node feature matrix. We then define Seature-mast M [yy] = if Uy E V and 0 otherwise, where V the paper. Then, we introduce a feature network (FeaNet) that learns watermarked node features as X = FeaNet x+) @ M The FeaNet takes input X and outputs matrix having the same size X e.g., has the same architecture GetingNet but adjusts the input size. The corresponding watermarked graph is defined as G = (V', E' X By generating a set of watermarked graphs G for client we minimize the loss on client i's both clean graphs G and G
to is the watermark node set described
Further, to learn feature-structure triggers, we combine FeaNet (that gets X with GatingNet/Key/Ntt (that gets EE and the watermarked graphs are G (Vi, E X We then minimize the loss on G: and G More details about training refer to Section 3.4.
10
We evaluate these triggers and the results are in Table 15 We observe that structure information alone sufficient to enable designing effective triggers.
E Discussion
Global watermark vs. local watermarks. In this paper, each client employs CWG to generate watermarks (i.c., local watermarks) to train the local model. During testing, we can use either local watermarks or global watermark, i.e., fully connect local watermarks. Here, we further evaluate the impact of global watermark vs. local watermarks of the target watermarked model under default settings. For better clarity, we randomly select four local watermarks labeled as local watermarks 1 to 4. The experimental results depicted in Figure demonstratee that, despite not being part of the training process, the global watermark performs slightly better than local watermarks. This implies that distributed training of FedGI. can aggregate the effects of local watermarks, providing foundation for utilizing the global watermark for verification.
18

---

Table 16: FedGMark with confidence scores summation against layer-perturbation attack.
Datasets
Fed-GIN
Hed-GSAGE
Fed-GCN MA1 WAT
Datasets
Fed-GIN
Fed-GSAGE
Fed-GON
MAT WAT
MA1 WAT
MA1
WAT
MA1 WAT
MAT WAT
0.55
0.65
0.81
0.52
0.52
0.63 0.67
MUTAG
0.70 0.65
0:71 0.60
0.73 0.44
PROTEINS
0.70 0.83
0.71 0.84
0.73 0.86
16
0.81 0.83
0.81 0.76
0.79 0.75
16
0.72 0.85
0.72 0.85
0.71 0,83
0.39
0.70 0.28
0.75 0.43
0.69
0.67 0.52
0.66 0.51
DD
8
0,70 0.42
0:72 0.48
0.73 0.46
COLLAB
0.74 0.61
0.74
0.66
0.72 0.62
0.73
0.59
0.74 0.54
0.71 0.42
0.71
0.72
0.72 0.70
Table 17: MA/WA on synthesized graphs for watermarking.
Watermark train/test graphs
MUTAG
PROTEINS
DD
COLLAB
0.910
0.7270.86
0.7370.65
0.73/0.75
synthesized graphs
0.80/ 0.88
0.71
0.72/ 00.64
0.72 0.73
Ensemble classifier with majority voting vs. summation on submodels' outputs. In this paper, we propose an ensemble classifier g aggregate the predictions of each submodel 9. through voting mechanism and classify graph as g(0, G) = arg yax y. where N₂ = Σ T [ G) = y). Another common strategy, as used in GL models such as GIN [Xu er al. 2019 is sum the prediction confidence vector of each submodel a, i.e., g(6, G) = arg max, yerta where f;
E.=f((0; G) and f outputs a probabilistic confidence vector whose summation is 1. Here, we also test our FedGMark with this strategy against the I-layer perturbation attack, and the results shown in Ta We notice the results do not remain consistent across different numbers of submodels and worse than those in Table 3 especially when S is small. This suggests that the summing-base ensemble classifier is not robust to the layer-perturbation attack, emphasizing the necessity of our proposed majority-voting based ensemble classifier.
FedGMark against offfine clients that cannot provide watermark data or malicious clients that provide fake watermark samples during ownership verification. We deem that our ownership verification is still robust against offline clients and malicious clients, if its number is less than 50%. During ownership verification, each client provides its own watermark data the trusted judge. When some clients are offline, the trusted judge can simply neglect them and only use participating clients' watermark data for verification.
When facing malicious clients, their negative effect can be circumvented through majority voting- based approach. Specifically, all clients provide their own watermark data to the judge and obtain the watermark accuracy per client. Though the watermark accuracy on malicious clients could be very low, the majority of benign clients can produce more number of high watermark accuracy, compared to the number of low accuracy. When the judge uses the majority-vot strategy, the final watermark accuracy is still high, ensuring the accurate ownership claim for benign clients.
Using clients' training graphs as the watermark samples and sending them to the trust judge may lead to privacy leakage. We clarify that the watermark data are not necessarily generated from the training/test samples. Remember the primary goal of backdoor-based watermarking to force the model to memorize the relationship between the backdoor trigger (in the watermark samples) and the target label, while the samples to inject the trigger do not have constraints, i.e., they can be from training samples or artificially synthesized (which does not contain privacy information of any training/test data). For conveniences, existing methods inject backdoor triggers into the training/test samples. To validate this, we synthesize a set of random graphs using the popular Erdōs- model (via the NetworkX toolbox) and the watermark samples are generated by injecting the learnt watermark on the synthesized graphs. Under the default setting, test on Fed-GIN and show results in Table [7] where we observe WAs are very close to those shown in the paper on the four datasets.
Furthermore, since all clients intend to verify model ownership. it is reasonable to believe that these clients are willing to provide their watermark data-whether generated from private training/test data or non-private synthesized data data-excllsively to a trusted judge, with informed consent and in accordance with legal and ethical standards. From this perspective, the data is confidential between each client and the trusted judge. We acknowledge it is very interesting future work to design provably private mechanism for model ownership verification that the verifier cannot access the watermark data but can guarantee the correctness of verification.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state the research problem, motivation, and contributions this paper in the Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of the approach in the Discussion section, e.g., using clients' training graphs as watermark samples and sending them to the trusted judge could lead to privacy leakage.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
20

---

Answer: [Yes]
Justification: We provide complete theory background in the main text, and present proofs in the supplementary.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our experimental results are reproducible. We provide detailed experimental settings in the main text.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
21

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We include links to the source code in the abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/ppulli//guu /tto://uuuddeeoooouuuubmmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide training and test details in the experimental part.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
Our experimental results are stable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
22

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments can be reproduced using one NVIDIA GeForce GTX 1080 Ti GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttt:://ttur://// htt.rr/s.....oolaoccccccccccddee
Answer: [Yes]
Justification:
This research conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Positive societal impacts: Our proposed watermark i.e. FedGMark can protect the ownership of FedGL. models.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
23

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no the above risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We cite the reference of datasets employed this paper following their requirements.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There is no dataset contribution in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "Q8jpZIpcgr", "reviewer": "Reviewer_Y9Y7", "summary": "This work studies watermarking for federated graph learning (FGL) to protect the ownership of participants. It proposes a customized watermark generator for local clients that can capture the local graph structure and private client information, and a robust model loader consisting of multiple GL submodels and a majority-voting-based ensemble classifier, which can defend against the proposed layer-perturbation attack.", "questions": "1. When the set of selected clients for aggregation is different from the set of watermarked clients, can the method achieve stable convergence?\n\n2. Is the layer-perturbation attack applied before or after submodel splitting? If it is applied after, does it perturb all submodels or not?\n\n3. Out of curiosity, is it possible to federated learn the local watermarking? How do you expect this would perform?", "limitations": "Please see Weaknesses above.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work claims to be the first to study watermarking for FGL models.\n\n2. The method can leverage local graph and client information to generate customized watermarks.\n\n3. The paper introduces a layer-perturbation attack to further demonstrate the certifiably robustness of the proposed backdoor-based watermarking for FGL.\n\n4. The work is well-motivated with preliminary studies.", "weaknesses": "1. The concept of ownership in FGL can be confusing and is not well-defined in this paper. For example, can every client claim ownership of the federated trained model? Since the watermarks from different clients are different, can any single client claim entire ownership? Additionally, for clients who participate in the FL but do not have watermarks, how can they claim ownership?\n\n2. The motivation for using local customized watermarks is not clear. The following problems arise: (1) It is unclear how to conduct ownership verification. Should it use the global watermark or the local watermarks? (2) If using a global watermark, what is the necessity of employing customized watermarks, or what is the adequate way to aggregate the global watermark from customized watermarks? If using local watermarks, how can the customized watermarks be used across clients?\n\n3. The method requires specific GL models (to be split to multiple submodels), which can be hard to adapt to existing FGL methods, especially for advanced FGL methods.\n\n4. The motivation for incorporating submodels for GL is missing. Why is this design necessary?\n\n5. (1) What does “layer indexes” for splitting GL models mean? From section 3.3, it is not clear how the submodels are split and how the split submodels are decoupled from each other regarding cascaded structures. (2) Additionally, structural information can be important for graph learning. How would discarding such structural information impact in this setting?\n\n6. The global model is obtained by simply averaging uploaded clients’ models (not weighted by data size, or applying proxy terms for regularization). Can this method address the potential heterogeneity issue when local watermarks are highly disparate from each other?\n\n7. The proposed method can introduce efficiency issues, as it significantly increases the number of parameters and computation time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for appreciating the motivation and novelty of this work (first to study robust watermarking for FedGL models).**  \n\n**W1: Clarify the concept of ownership in FedGL**\n\nIn typical FL, a server and multiple clients collaboratively train a global model stored in the server, which is used by all clients for their tasks. Accordingly, in our ownership verification problem in FedGL, *all* clients design their own watermark data and *collaboratively train the watermarked global model*, which is for *joint ownership by all participating clients*. \n\nFurther, since all clients have devoted computation and data to the training, they have a strong intention to jointly protect their ownership of the model. Hence, we do not consider the case where the clients did NOT participate in watermark training, but claim the ownership of the model (actually these clients do not know how to do so). \n\n**W2: (1) Global or local watermarks for ownership verification; (2) Motivation of developing local customized watermarks**\n\n(1) We use the global watermark (integration of local watermarks) for ownership verification, in line with the fact that the watermarked global model is collaboratively learnt from all clients with their local watermarks. Figure 6 in Appendix also shows global watermark is more effective than local watermarks.   \n\n(2) Learning local customized watermarks is to utilize the unique property of each client, as  different clients could have different properties (e.g., distributions of their data) and their optimal watermark could be different. Also, the learnt customized watermarks enhance the ownership verification performance. For instance, Table 5 shows watermark accuracy improves 8% with local customized watermarks. \n\n**W3: Require split specific GL models to multiple submodels**  \n\nSorry for the confusion! In our design, we do not split the existing GL model into multiple submodels. Instead, we can use *any* GL model (e.g., a 3-layer GIN) as a submodel and each client’s GL model is an ensemble of a set of submodels (More details in Response to **W5**). Hence, our approach can be easily adapted to any FedGL, where it can use any aggregator or base GL model. For instance., our experiments conducted on Fed-GIN means we use the average aggregator and GIN as the submodel. \n\n**W4: Why incorporate submodels for GL** \n\nOur goal is to ensure the *provable robustness* of our watermarked FedGL model against layer-perturbation attacks. Recall that we propose a majority-voting based ensemble classifier on the submodels of our GL. Based on this, we can guarantee the ownership verification is provably accurate, when the \\#perturbed layers on GL models satisfies Eqn (1) in Thm 1. \n\n**W5: (1) What does “layer indexes” mean? (2) Structural information is important.**  \n\n(1) A GL model contains multiple layers. E.g., a 8-layer GIN can be represented with layer indexes {$l_0, \\ldots, l_7$}. Splitting this GIN into 4 submodels $\\{GIN_1, \\cdots, GIN_4\\}$ with layer indexes {$l_0, l_1$} … {$l_6, l_7$} means $GIN_i$ contains layers $l_{2i}$, $l_{2i+1}$ from the GIN. *However, submodels splitted in this way are coupled from each other, making them unable to defend against layer-perturbation attacks*. To tackle this problem, we *design the novel GL model that is an ensemble of a set of independent submodels*, where each submodel is a base GL model, e.g., GIN or GCN.  \n\n(2) Yes, it is. All our submodels are GL models that take the whole graph as input, and hence retrain the graph structure information. \n\n**W6: Can this method address the potential heterogeneity issue?**\n\nGood question! Per the Response to **W2**, local watermarks are learnt by considering the unique properties in each client. Such unique properties may include the heterogeneity across clients’ data. To validate this, we test our method with non-IID graphs across clients, where each client holds a single label data. The MA/WA results are below:   \n\n|Dataset |MUTAG | PROTEINS |  DD  |  COLLAB |\n|:------------|--------------:|:-------------:|:-------------:|:-------------:|\n| paper results | 0.81 / 0.90 | 0.72 / 0.86 | 0.73 / 0.65 | 0.73 / 0.75 |\n| non-IID| 0.80 / 0.89 | 0.72 / 0.83 | 0.72 / 0.63 | 0.72 / 0.75 |\n\nWe can see FedGMark also performs well with non-IID datasets. This implies the learnt customized watermarks indeed capture the heterogeneity of clients’ graphs. \n\n**W7: Efficiency issues** \n\nSee Response to Comment#3 in the global rebuttal. \n\n\n**Q1: Selected clients for aggregation different from watermarked clients** \n\nIn our experiments, the server randomly selects a fraction (e.g., 50\\%) of clients for aggregation in each training round. Also, all clients participating in the model ownership verification have watermarked data. Hence, there is no case where the set of clients selected for aggregation differs from the set of watermarked clients.\n\n**Q2: Layer-perturbation attack before or after submodel splitting?** \n\nIt is before submodel splitting (ensemble). \n\n**Q3: Federally learn the local watermarking?** \n\nIn our method, local watermarks are learnt using the global model (see Step 2 in Section 3.4), which is *federally* trained by all clients’ local models. From this point of view, local watermarks are also federally learnt by all clients.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QVY9VqBmm2", "reviewer": "Reviewer_ZEKF", "summary": "This paper addresses the problem of protecting model ownership in the emerging domain of Federated Graph Learning (FedGL) by proposing FedGMark, a backdoor-based watermarking technique. The authors argue that existing watermarking approaches are either inapplicable to graph data or exhibit weaknesses in terms of robustness against removal attacks and lack of formal guarantees. FedGMark aims to overcome these limitations by leveraging graph structure and client information to learn customized watermarks, employing a novel graph learning (GL) architecture that enhances robustness, and providing certified robustness guarantees against layer-perturbation attacks.", "questions": "1. Could you quantify the communication overhead of FedGMark during federated training, especially compared to random graph-based watermarking (in terms of local training time, size of watermarked data, etc.)?\n2. How do you envision FedGMark being deployed in a real-world FedGL system? What practical challenges might arise during implementation and watermark verification?\n3. How would the certified robustness guarantees be affected by more advanced watermark removal attacks beyond layer perturbation (e.g., those involving trigger reverse engineering)?\n4. How would the effectiveness of FedGMark be affected if the attacker had more knowledge about the watermarking process, such as access to the CWG architecture or the private key generation method?", "limitations": "1. FedGMark's evaluation focuses solely on FedAvg for aggregating client models. The impact of alternative aggregation methods (e.g., those prioritizing clients based on data quality or model performance) on both watermark robustness and overall FedGL model performance remains unexplored.\n2. The paper acknowledges the increased computational cost of using more submodels (S) in RML but doesn't fully analyze the scalability of FedGMark. Further investigation is needed to understand how performance scales with different numbers of clients.\n3. FedGMark relies heavily on structural modifications of the graph as the watermark.  The effectiveness and robustness of alternative trigger designs, such as feature-based triggers, hybrid triggers, or combinations of different trigger types, have not been explored. \n4. The paper lacks specific details about the hyperparameters used for training the GL models on the client-side. The impact of client training dynamics, particularly the choice of learning rate and the number of local epochs, on the watermarking performance and robustness of FedGMark remains unclear and requires further investigation.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper clearly outlines the limitations of existing watermarking techniques and presents a well-motivated approach to address them. The design of FedGMark, with its CWG and RML modules, is tailored to the specific challenges of watermarking in FedGL.\n-  FedGMark demonstrates promising empirical performance in terms of both main task accuracy and watermark accuracy. It outperforms the baseline approach (random graph-based watermarking) significantly, especially under watermark removal attacks.\n- The paper provides theoretical guarantees for the robustness of FedGMark against layer-perturbation attacks, a unique and valuable contribution in the watermarking literature.", "weaknesses": "1. The reliance on pre-defined private keys for watermark generation may not be practical in all scenarios, and alternative key management methods should be explored.\n2. The assumption of limited attacker knowledge about the watermarked model may not hold in practice. Evaluating FedGMark against more knowledgeable adversaries would provide a more realistic assessment.\n3. The focus on FedAvg for model aggregation limits the exploration of other aggregation methods and their impact on watermark robustness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for appreciating the well-motivated approach, promising performance, and robustness guarantees.**\n\n**W1: Alternative key management methods** \n\nWe clarify the predefined key is used by the Watermark Generator to know which local watermark is learnt for which client. It is like an identifier of the client and only needed and known by the client’s watermark generator to generate the customized watermark. This is different from the role of the key management methods in crypto. To avoid confusion, we will not use the term “private key”, but “client ID”.  \n\n**W2 (Q4): Against more knowledgeable adversaries.**\n\nAs suggested, we test the attacker that has access to CWG to manipulate the FedGL training. We assume some clients are malicious and test two attacks. First, we consider a *passive* attack where all malicious clients DO NOT use CWG to generate customized local watermarks. Model (b) in Table 5 shows the *maximum* WA decrease is 9\\%, where *all* clients do not use CWG.   \n\nSecond, we test an *active* attack where malicious clients modify their watermark data’s label to obfuscate the training. Specifically, all malicious clients’ watermark data are labeled (e.g., 2) differently from the target label (e.g., 1). The results below show MA/WA is marginally affected even with 20% malicious clients. \n\n||0%|10%|20%|30%|40%|\n|-|-|-|-|-|-|\n|MU|.81/.90|.80/.90|.80/.89|.80/.80|.80/.71|\n|PR|.72/.86|.72/.85|.72/.76|.71/.67|.70/.67|\n|DD|.73/.65|.72/.63|.72/.58|.71/.53|.71/.52|\n|CO|.73/.75|.74/.74|.73/.68|.73/.61|.72/.60| \n\n**W3 (L1): Other aggregation methods**\n\nWe test M-Krum [Blanchard et al 18] and T-mean [Yin et al 19] that consider data quality (e.g., remove outlier clients). M-Krum filters a fraction $p$ of clients whose gradients largely deviated from others, while T-mean trims off a fraction $q$ of highest and lowest values for each parameter in clients’ models. We set $p=10\\%$ and $q=10\\% $, and the MA/WA results are as follows. We see these aggregators achieve a robustness-utility tradeoff, and MA and WA are not largely different.  \n\n||Avg|M-Krum|T-mean|\n|-|-|-|-|\n|MU|.81/.90|.78/.92|.75/.93|\n|PR|.72/.86|.73/.85|.70/.87|\n|DD|.73/.65|.72/.63|.70/.65|\n|CO|.73/.75|.73/.74|.71/.77|\n\n**Q1(L2): Scalability**\n\nSee Response to Comment#3 in the global rebuttal. \n\n**Q2: (1) Deployment of FedGMark; (2) Challenges**\n\n**(1) Deployment**: *Stage I: Server-client model for FedGMark training*\n\n- Setup: Server and clients make an agreement on, e.g., the GL model, the aggregator, and server initializes the global model.\n\n- Local training: Clients download the global model, define their watermark data, locally train their watermarked GL model (with the CWG and RML module) using the global model, and upload the updated local model to the server; \n\n- Server aggregation: Server aggregates local watermarked models of selected clients to update the global watermarked model.\n\nThe final global watermarked model is shared by all clients for legal use.   \n\n*Stage II: Ownership verification.* See Response to Comment#2 in the global rebuttal.\n\n**(2) Challenges:** We consider security and privacy threats, and data quality.  \n\n- **Security**: How to guarantee all clients and the server are benign or detect / remove malicious ones? How to mitigate more advanced attacks? \n\n- **Privacy**: Though FL methods do not access the data, they may still leak data privacy in practice. How to provably protect the data privacy, while keeping the utility? \n\n- **Data quality**: Low quality data negatively affects the utility. This could reduce the interest for clients with high-quality data to participate in the FL. How to ensure all data have high quality? \n\n**Q3: Attacks use trigger reverse engineering** \n\nSee Response to Comment#4 in the global rebuttal. \n\n**L3: Alternative triggers design** \n\n**Response:** We add some details to adjust FedGMark to the suggested alternative triggers. \n\nTo learn feature-based triggers, we first select a set of nodes from a graph as the target nodes, and learn the watermarked features for the target nodes. We use a graph $G^i = (V^i, E^i, X^i) $  from client $i$ for illustration, where $X^i$ is the node feature matrix. We then define a feature-mask $M_f^i[v_j]=1$ if $v_j \\in V_w^i$ and 0 otherwise, where $V_w^i$ is the watermark node set described in the paper. Then, we introduce a feature network (FeaNet) that learns watermarked node features as $X_w^i = FeaNet(X^i) \\odot M_f^i$. The FeaNet takes input $X^i$ and outputs a matrix having the same size as $X^i$, e.g., it has the same architecture as GatingNet but adjusts the input size. The corresponding watermarked graph is defined as  $G_w^i=(V^i, E^i, X_w^i)$. By generating a set of watermarked graphs {$G_w^i$} for client $i$, we minimize the loss on client $i$’s both clean graphs {$ G_c^i$} and {$G_w^i$}. More details about training refer to Section 3.4.     \n\nFurther, to learn feature-structure triggers, we combine FeaNet (that gets $X_w^i$) with GatingNet/KeyNet (that gets $E_w^i$), and the watermarked graphs are $G_w^i=(V^i, E_w^i, X_w^i)$. We then minimize the loss on {$G_c^i$} and {$G_w^i$}. \n\nWe evaluate these triggers and the results are follows. We observe that structure information alone is sufficient to enable designing effective triggers.  \n\n||f| s| f-s|\n-|-|-|-\nMU|.81/.78|.81/.90|.79/.92\nPR|.72/.77|.72/.86|.73/.87\nDD|.72/.53|.73/.65|.74/.66\nCO|.73/.67|.73/.75|.72/.76\n\n**L4: Performance on hyperpara.**\n\nBy default, we set the learning rate (lr) to 0.01 and \\#local epochs (le) to 5. The results with more lr and le are below: \n\n||(le=5)lr=.01|.05|.1|(lr=.01)le=5|10|20\n-|-|-|-|-|-|-\nMU|.81/.90|.84/.89|.79/.90|.81/.90|.84/.9|.76/.92\nPR|.72/.86|.71/.79|.71/.73|.72/.86|.72/.87|.72/.89\nDD|.73/.65|.71/.57|.70/.53|.73/.65|.73/.66|.73/.69\nCO|.73/.75|.72/.71|.70/.65|.73/.75|.74/.75|.73/.77\n\nWe see that a large lr may reduce WA, and WA slightly increases as le grows, indicating more thorough training makes our method perform better.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C9sGZdxe04", "reviewer": "Reviewer_djtK", "summary": "This manuscript introduces FedGMark, a backdoor-based watermarking method specifically designed to protect Federated Graph Learning (FedGL) models from illegal copying and model theft. They claim that the proposed FedGMark is the first method to safeguard the intellectual property of FedGL models, offering certified robustness against watermark removal attacks, leveraging unique graph structures and client information to create customized and diverse watermarks. Experiments demonstrate its effectiveness and robustness.", "questions": "Please refer to Weaknesses part", "limitations": "Please refer to Weaknesses part", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper introduces FedGMark to address the overlooked vulnerability of FedGL model ownership and identifies three main challenges in current watermarking techniques: inapplicability to graph data, vulnerability to removal attacks, and lack of formal guarantees. The proposed method, including CWG and RML, is clear and intuitive, and the authors have provided comprehensive experiments to support their approach.", "weaknesses": "1.\tI strongly recommend setting a \"Threat Model\" subsection to clarify the potential security threats to FedGL. In my opinion, since the authors consider watermark removal attacks like distillation and finetuning, FedGL operates under a white-box setting.\n2.\tThe paper assumes attackers know the internal information of the target watermarked model, enabling distillation, finetuning, and layer-perturbation attacks. However, I find the white-box setting narrow and trivial. The authors should consider black-box attacks, which are more challenging and meaningful. Many studies on black-box attacks can be found.\n3.\tIn watermarking-related literature, robustness and fidelity are more frequently used terms than watermark accuracy and task accuracy.\n4.\tIn the \"Inapplicable or Ineffective\" item, the authors state, \"For instance, they require input data to have the same size, while graphs can have varying sizes,\" which is not entirely accurate. For example, some Wavelet and DCT-based watermarking methods can be scalable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for appreciating the intuition and motivation of the proposed solution and the comprehensive evaluations to support the solution.** \n\n**W1: Clearly define the \"Threat Model\"**\n\nThanks for the suggestion! See Response to Comment#1 in the global rebuttal.\n\n\n**W2: Consider black-box attacks**\n\nWe emphasize this is a defense paper aiming to design a robust watermarking scheme for FedGL. As many lessons have learnt and to avoid the false sense of security [Carlini et al. 2019], an effective defense should be tested against the strongest white-box attacks. This is because a defense that is effective against (impractical) weaker attacks does not imply it is effective against stronger attacks. To this end, we assume the attacker knows all information of the target watermarked model, and *this setting actually makes our defense design the most challenging*. Moreover, if the defense can successfully defend against the strongest white-box attack on the watermarked FedGL model, it is naturally effective against any weaker attacks (thus including black-box attacks). \n\nNicholas Carlini et al., On evaluating adversarial robustness. arXiv, 2019.\n\n**W3: Replace watermark accuracy main task accuracy with robustness and fidelity**.\n\nThank you for the suggestion. We will change the terms. \n\n**W4: Statement on “... while graphs can have varying sizes” is not entirely accurate** \n\nWe agree that certain types of graphs (like wavelets) have the same size. However, our statement is for the general graph datasets whose graph sizes are varied.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "He8o2uczmH", "reviewer": "Reviewer_yEMY", "summary": "This paper investigated the problem of watermarking the Federated Graph Learning (FGL) models. This paper proposed the first backdoor-based FGL watermarking framework, called FedGMark. Specifically, to tackle the issues of ineffectiveness and vulnerability of existing methods, FedGMark designed two modules respectively. One is a Customized Watermark Generator (CWG). CWG aimed to generate the watermarked trigger samples (graphs) using each client's secret key. The other is the Robust Model Loader (RML). RML guaranteed that the watermarked models were certifiably robust against layer perturbation attacks.", "questions": "1. Clarify the threat model.\n2. Address the privacy concern.\n3. Analysis or experiments on the robustness against backdoor defenses.\n4. Clarify the procedure of ownership verification in FedGMark.", "limitations": "This paper does not include a discussion of the limitations. However, I think there is a strong assumption that the clients need to be trustworthy in FedGMark. A discussion on this assumption is necessitated.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The first attempt to watermark federated graph learning models.\n- The watermarked models are certifiably robust against attacks.\n- Experiments on various datasets and models validate the effectiveness of FedGMark.", "weaknesses": "My major concerns are as follows.\n1. Unclear threat model: The threat model and the problem formulation of this paper is unclear. What's the capability of the adversary and the defender? And more importantly, who is the adversary to steal the FGL model? This paper proposed to watermark the FGL model from the client side, which means the clients should be trustworthy. Is the central server an adversary in this paper? To my best knowledge, the typical threat model of various attacks in FL (e.g., backdoor attacks or Byzantine attacks) assumes that some of the clients may be malicious. The author should add a section on the threat model or problem formulation and clarify why they make these assumptions. This may be helpful to better understand the problem the authors tried to solve.\n2. Privacy concern: I also worry that utilizing FedGMark may raise privacy concerns. In Section 3.4, the watermarked client needs to use a subset of its training graphs as the watermarked graphs. However, in FL, the client's graphs are privacy-sensitive, and using them to verify ownership may lead to privacy leakage. This is contrary to the original purpose (preserve privacy) of FL.\n3. Missing experiments on the robustness against backdoor defense: This paper considers three different watermark removal attacks. However, since FedGMark utilizes backdoor-based watermarking methods, it is important to validate whether FedGMark is robust against backdoor defenses.\n4. Missing introduction to ownership verification: This paper lacks an important section to introduce the ownership verification procedure of FedGMark.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for appreciating the novelty of the studied problem and the proposed certified robust watermarking scheme against attacks.** \n\n**W1: Clearly define the Threat Model and Problem; Who is the adversary to steal the FedGL model); Are clients and central server an adversary? Make assumptions clear**  \n\nThanks for the suggestion! See Response to Comment#1 in the global rebuttal.\n\n\n**W2: Privacy concerns raised by FedGMark**\n\n**Response:** FedGMark does not pose additional data privacy concerns. Like classic FL, all (watermarked) clients *locally* process their watermark data and train the model, and then submit the trained model to the server. Hence, the server cannot access the private data. \n\n**W3: Test backdoor defenses based attacks against FedGMark**\n\nSee Response to Comment#4 in the global rebuttal. \n\n**W4: Introduce the \"ownership verification\" procedure of FedGMark**\n\nThanks for the suggestion! See Response to Comment#2 in the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**We thank all reviewers for their constructive comments! We first summarize the global response to the common comments raised by the reviewers and then reply to individual reviewers’ comments.**

**Comment#1:Threat Model (djtK-W1 and yEMY-Q1)** 

**Response:** Thanks for the suggestion! We add more details about our motivation, assumption, threat model and problem definition. 

**Motivation, Adversary and Assumptions:** Watermarking is designed to safeguard **well-trained models** against threats like illegal copying and unauthorized distribution.  An adversary could be, e.g.,  
- a business competitor seeking to replicate a model to gain competitive advantages by significantly reducing development costs 
- a malicious user who sells the model for profits
- a cybercriminal who uses the stolen model for malicious purposes such as conducting large-scale spam campaigns   
 
In the paper, we follow existing methods [Shafieinejad et al., 21, Bansal et al., 22, Xu et al. 23, Jiang et al., 23], where the adversary is assumed to *know all details of the pretrained watermarked FedGL model*, but does NOT tamper with the training process. *This means all clients and the server are benign and follow the federated training protocol*, and the attack happens at the testing/inference time. We highlight this is in stark contrast to the *training-time* Byzantine attack on FL where some clients are malicious and they manipulate the training process.

**Threat model:** 
- *Attacker’s knowledge:* The attacker has white-box access to the pretrained watermarked FedGL model. In addition, the attacker may also know some clean (unlabeled or labeled) training data, as well as watermarked data.  

- *Attacker’s capability:* The attacker can modify the pretrained model via leveraging its white-box access to the trained model and its hold training and watermarked data. For instance, the attacker can finetune the pretrained model via the labeled training data. More details of the capabilities of considered attacks are described in Sec 2.3. 

- *Attacker’s goal:* To remove the watermark based on its knowledge and capability, while maintaining the model utility. This allows it to illegally use the model without detection.

**Problem definition:** As the defender, we focus on protecting the ownership of the trained FedGL model from the aforementioned security threats. In particular, we aim to build a *certifiably robust* watermarking scheme for FedGL against the worst-case layer-perturbation attack, such that the learnt watermarked FedGL model can achieve two goals:

- High task accuracy (fidelity): predict correct labels as many as possible for clean test graphs 

- High (certified) watermark accuracy (robustness): (provably) predict the target label as many as possible for test graphs with the watermark

**Comment#2: Ownership Verification (ZEKF-Q2 and yEMY-W4)** 

**Response:** As FedGMark uses backdoor-based watermarking, the ownership verification procedure of FedGMark is similar to that of the standard backdoor-based watermarking (Line 35-40). Specifically, when suspecting the target FedGMark model is illegally used by others, the model owner (all the participating clients or their representative) can recruit a trusted judge for model ownership verification. Typically, the judge requests both the true model owner and the illegal party to provide some test data for verification. Only when the one knows the predictions by the target model for the provided test data by both parties, the judge will confirm this party the model ownership. In particular, besides providing the clean data by both parties that behave normally, the true model owner especially provides the designed watermarked data that only he knows the model behaves on. As a result, both parties know the prediction results on clean data, but the illegal party is hard to predict accurately on the watermarked data provided by the true model owner. 

**Comment#3: Scalability of FedGMark (Y9Y7-W7 and ZEKF-Q1)**

**Response:** Compared with graph-based or non-robust watermarking methods, the computation overhead of FedGMark is mainly from the introduced submodel models (fixing all the other parameters, such as \#clients, \#iterations, to be the same). Particularly, the overhead scales linearly with the number of submodels $S$. Here we copy the runtime result from Table 9 in Appendix for reference, where $S=1$ is the runtime of the existing method. 

|Runtime(s)|MUTAG|PROTEINS|DD|COLLAB|
|-|-|-|-|-|
|S=1|0.13|0.72|2.99|37.65|
|S=4|0.46|2.79|11.14|161.46|
|S=8|0.74|5.10|20.12|296.68|
|S=16|1.32|9.49|36.74|563.51|

We believe the computation overhead is not an issue in practice, compared with the importance of designing a provably robust watermark that aids the ownership verification of the FedGL model. Note that as all clients have devoted computation and data to the training, they have a strong intention to jointly protect their ownership of the FedGL model.

**Comment#4: More watermark removal attacks (ZEKF-Q3 and yEMY-W3)**

**Response:** Many existing works [Wang et al 20, Zhang et al. 21] show the trigger-reverse based backdoor detection/removal is vulnerable to the ``stealthy” backdoor. This is because the effectiveness of trigger reverse attacks largely depends on the statistical differences between clean data and backdoored data. Since we do not notice any graph backdoor trigger-reverse attack, we instead propose to quantitatively test the structure similarity between the generated watermarked graphs and the clean graphs. Here we use the metrics NetSim and DeltaCon proposed in [Wills and Meyer’20], with the range [0,1] and the higher value the larger similarity. The results are below: 

Dataset|MUTAG|PROTEINS|DD|COLLAB
-|-|-|-|-
NetSim|0.97|0.98|0.99|0.99
DeltaCon|0.98|0.98|0.99|0.99

We observe the watermarked graphs and their clean counterparts are structurally very close. This implies that the proposed watermarks are hard to be detected or removed.

Meta-review: The paper proposes a watermarking method for federated graph learning (FGL). The method relies on a local watermark generator at each client to capture the local graph structure and private client information; the paper also proposes a novel GL architecture to defend against watermark removal. The authors have addressed all the major concerns and I strongly encourage the authors to include them in the final version of the paper.
Decision: Accept (poster)