Secure Network Release with Link Privacy
Authors: Carl Yang
Haonan Wang
Ke ZHANG
Lichao Sun
Venue:  (2021)
Keywords: generative model
graph neural network
data release

Abstract: Many data mining and analytical tasks rely on the abstraction of networks (graphs) to summarize relational structures among individuals (nodes). Since relational data are often sensitive, we aim to seek effective approaches to release utility-preserved yet privacy-protected structured data. In this paper, we leverage the differential privacy (DP) framework, to formulate and enforce rigorous privacy constraints on deep graph generation models, with a focus on edge-DP to guarantee individual link privacy. In particular, we enforce edge-DP by injecting Gaussian noise to the gradients of a link reconstruction based graph generation model, and ensure data utility by improving structure learning with structure-oriented graph comparison. Extensive experiments on two real-world network datasets show that our proposed DPGGAN model is able to generate networks with effectively preserved global structure and rigorously protected individual link privacy.

Under review as a conference paper at ICLR 2021
SECURE NETWORK RELEASE WITH LINK PRIVACY
Anonymous authors Paper under double-blind review
ABSTRACT
Many data mining and analytical tasks rely on the abstraction of networks (graphs) summarize relational structures among individuals (nodes). Since relational data are often sensitive, we aim to seek effective approaches to release utility- preserved yet privacy-protecee
structured data. this paper, we leverage the differential privacy (DP) framework to formulate and enforce rigorous privacy constraints on deep graph generation models, with focus on edge-DP to guarantee individual link privacy. In particular, we enforce edge-DP by injecting Gaussian noise to the gradients of a link reconstruction based graph generation model, while ensuring data utility by improving structure learning with structure- graph comparison. Extensive experiments on two real-world network datasets show that our proposed DPGGAN model is able to generate networks with effectively preserved global structure and rigorously protected individual link privacy.
INTRODUCTION
Nowadays, open data of networks play pivotal role in data mining and data analytics (Tang et al. 2008 [Sen et al.) 2008 Blum et al. 2013] Leskovec & Krevl, 2014). By releasing and sharing structured relational data with research facilities and enterprise partners, data companies harvest the enormous potential value from their data, which benefits decision-making on various aspects, including social, financial, environmental, through collectively improved ads, recommendation, retention, and so on (Yang et al., 2017: 2018: Sigurbjörnsson & Van Zwol 2008 Kuhn 2009). However, network data usually encode sensitive information not only about individuals but also their interactions, which makes direct release and exploitation rather unsafe. More importantly, even with careful anonymization, individual privacy is still stake under collective attack models facilitated by the underlying network structure (Zhang et al. 2019 Cai et al. 2018). Can we find a way to securely release network data without drastic sanitization that essentially ly renders the released data useless?
In dealing with such tension between the need to release utilizable data and the concern of data owners' privacy, quite few models have been proposed recently. focusing on grid-based data like images, texts and gene sequences (Frigerio et al., 2019
Papernot et al.) 2018 Triastcyn & Faltings
2018 Narayanan & Shmatikov 2008) Xie et al. 2018
Chen et a 2018 Boob et al. | [0118] Dy & Krause 2018 Lecuyer et al. [0188] Zhang al. 201 8). However, none of the existing models can
be directly applied to the network (graph) setting. While a secure generative model on grid-based data apparently aims to preserve high-level semantics (e.g., class distributions) and protect detailed training data (e.g., exact images or sentences), it remains obtuse what to be preserved and what to be protected for network data, due to its modeling of complex interactive objects.
Motivating scenario. In Figure I a bank aims to encourage public studies on its customers' community structures. It does so by firstly anonymizing all customers and then sharing the network (L.e., (a) in Figure T) to the public. However, an attacker interested in knowing the financial interactions (e.g., money transfer) between particular customers in the bank may happen to have access to another network of similar set of customers (e.g., malicious employee of another financial company). The similarity of simple graph properties like node degree distribution and triangle count between the two networks can then be used to identify specific customers with high accuracy in the released network (e.g., customer A as the only node with degree 5 and within triangle, and customer B as the only node with degree 2 and within I triangle). Thus, the attacker confidently knows the A and B's identities and the fact that they have financial interactions in the bank, which seriously harms customers' privacy and poses potential crises.

---

Under review as a conference paper at ICLR 2021
B
(a) Anonymized original net.
(b) DPGGAN generated net.
Figure 1: A toy pair of anonymized and generated networks.
As the first contribution in this work, we define and formulate secure network release goals as preserving global network structure while protecting individual link privacy. Continue with the toy example, the solution we propose is to train graph neural network model on the original network and release the generated networks (e.g., (b) in Figure TT. Towards the utility of generated networks, we require them to be similar to the original networks from global perspective, which can be measured by various graph global properties (e.g., network (b) has very similar degree distribution and the same triangle count as (a)). In this way, we expect many downstream data-mining and analytical tasks on them to produce similar results as on the original networks. As for privacy protection, we require that the information in the generated networks cannot confidently reveal the existence absence of any individual links in the original networks (e.g., the attacker may still identify customers and B in network (b), but their link structure has changed).
Subsequently, there are two unique challenges in learning such structure- structure-preserved preserved and privacy- protected graph generation models, which have not been explored by existing literature far.
Challenge Rigorous protection of individual link privacy. The rich relational structures in graph data often allow attackers to recover private information through various ways of collective inference (Zhang et al. 2014; Narayanan Shmatikov 2009 Backstrom et al., 2007). Moreover, graph structure can al always be converted to numerical features such as spectral embedding, after which most attacks on grid-hased data like model inversion (Fredrikson et al.) (015)) and membership inference (Shokri et al.) 2017) can be directly applied for link identification. How effective mechanism with rigorous privacy protection on links in networks against various attacks?
design an
Challenge 2: Effective preservation of global network structure. To capture the global network structure, the model has constantly compare the structures of the input graphs and currently generated graphs during training. However, unlike images and other grid-based data, graphs have flexible structures, and thus they lack efficient universal representations (Dong al.) 2019). How can we allow network generation model to effectively learn from the structural difference between two graphs, without conducting very time-costly operations like isomorphism tests all the time?
Present work. In this work, for the first time, we draw attention to the secure release network data with deep generative models. Technically, towards the aforementioned two challenges, develop Differentially Private Graph Generative Nets (DPGGAN), which imposes DP training over a link reconstruction based network generation model for rigorous individual link privacy protection, and further ensures structure-oriented graph comparison for effective global network structure preservation. In particular, we first formulate and enforce edge-DP via Gaussian gradient distortion by injecting designed noise into the sensitive modules during model training. Then we leverage graph convolutional networks (Kipf Welling 2017) through a variational generative adversarial network architecture (Gu et al. 2019 network comparison.
Larsen et al.) 2016) to enable structure-orrented
To evaluate the effectiveness of DPGGAN, we conduct extensive experiments on two real-world network datasets. On one hand, we evaluate the utility of generated networks by computing suite of commonly concerned graph properties to compare the global structure of generated networks with the original ones. On the other hand, we validate the privacy of individual links by evaluating links predicted from the generated networks on the original networks. Consistent experimental results show that DPGGAN is able to effectively generate networks that are similar to the original ones regarding global network structure, while at the same time useless towards individual link prediction.
2

---

Under review as a conference paper at ICLR 2021
2 RELATED WORK
Differential Privacy (DP), Differential privacy is a statistical approach in addressing the paradox of learning nothing about an individual while learning useful information about a population (Dwork et al. 2006). Recent advances in deep learning have led to the rapid development of DP-oriented learning schemes. Among them, the Gaussian Mechanism (Dwork al. 2014). defined as follows. provides a neat and compatible framework for DP analysis over machine learning models.
Definition 1 (Gaussian Mechanism (Dwork et al. 2014)). For a deterministic function f with its 2--norm sensitivity as A2f- GG-G"
funcmiinisticcunciion
max
[G)
[(G')lla we have:
My(G) & F(G) + NOO0 A2l20²).
where NO, 02) is a random variable obeying the Gaussian distribution with mean and standard deviation A2fo. The randomized mechanism (G) is (E, if 2 A2f A2f.22m(1.25/8) and & < 1.
Following this framework, (Abadi et al. 2016) proposes a general training strategy called DPSGD, which looses the condition on the overall privacy loss than that in Definition by tracking detailed information of the SGD process to achieve an adaptive Gaussian Mechanism.
DP learning has also been widely adapted to generative models (Frigerio et al. 2019 Papernot et al.
2018
Triasteyn & Faltings 2018 Narayanan & Shmatikov [2008] Mohammed et al. 201 Xie et al.
2018 Chen et al. 2018 Boob et al. 2011; Dy & Krause 2018 Lecuyer et al.
[0188] Zhang et al.
2018
For example, (Frieerio et al. 2219 Chen et al. 2018: Boob et al. 2018 Zhang et al. 2018
share the same spirit by enforcing DP on the discriminators, and thus inductively on the generators, in generative adversarial network (GAN) scheme. However, none of them can be directly applied to graph data due to the lack of consideration of structure generation.
For graphs' structural data, two types of privacy constraints can be applied, i.e., node-DP (Ka- siviswanathan et al. 2013) and edge-DP (Blocki et al. (012),, which define two neighboring graphs to differ by at most one node or edge. In this work, we aim at the secure release of network data, and particularly, we focus on edge privacy because it is essential for the protection of object interactions unique for network data compared with other types of data. Several existing works have studied the protection of edge-DP. For example, (Sala et al. (011)) generates graphs based on the statistical representations extracted from the original graphs blurred by designed noise, whereas (Wang Wu 2013) enforces the parameters of dK- dK-graph models to be private. However, based on shallow graph generation models, they do not flexibly capture global network structure that can support various unknown downstream analytical tasks (Zhang al. 2019 Wasserman & Zhou 2010).
Graph Generation (GGen). GGen has been studied for decades and is widely used to synthesize network data used to develop various collective analysis and mining models (Evans & Lambiotte 2009 Hallac et al.) (017)) Earlier works mainly use probabilistic models to generate graphs with
certain properties (Erdós & Rényi 1960] Watts & Strogatz 1998 Barabási & Albert, 1999, Newman 2001), which are manually designed based on sheer observations and prior assumptions.
Thanks to the surge of deep learning, many advanced GGen models have been developed recently. which leverage different powerful neural networks in a learn-to-generate manner (Kipf & Welling
2016, BBojhheski et al. [0188] You et al. 2018b; (Simonovsky & Komodakis [018: Li et al. 2018
You al. [2018a] Jin et a 2018 Grover al. 2017]De Cao & Kipl 2018] Zou & Lerman 2018
Ma et al. 2018). For example, NetGAN (Bojchevski et al. (0188) converts graphs into blased random walks, learns the generation of walks with GAN, and assembles the generated walks into graphs;
GraphRNN You et al. 2018b) regards the generation of graphs as node-and-edge addition sequences, and models it with a heuristic wreadth-fisst-eant
scheme and hierarchical RNN. These neural network based models can often generate graphs with much richer properties, and flexible structures learned from real-world graphs.
To the best of our knowledge, no existing work on deep GGen has looked into the potential privacy threats laid during the learning and releasing of the powerful models. Such concerns are rather often be more easily compromised in et al. 2007 Zhang et al. (0144) and privacy leakage
urgent in the network setting, where sensitive information collective manner (Dai et al. can easily further propagate (Narayanan & Shmatikov 2009 Zügner al. 2018).
3

---

Under review as a conference paper at ICLR 2021
3 DPGGAN
In this work, we propose DPGGAN for the secure release generated networks, whose global graph structures are similar to the original sensitive networks, but the individual links (edges) between objects (nodes) are safely protected. To provide robust privacy guarantees towards various graph attacks, we propose to leverage the well-studied technique of differential privacy (DP) (Dwork et al. 2014) by enforcing the edge-DP defined as follows.
Definition 2 (Edge Differential Privacy (Blocki et al.) 2012)) A randomized mechanism M satisfies (c, -edge-DD- if for any two neighboring graphs G1. G2 E G. which differ by at most one edge, Pr[M((n) E S) S exp(E) X Pr(M(G22 E S + 5, where S C range(M))
Our key insight is, graph generation model M satisfying the above edge-DP should learn to generate similar graphs given the input of two neighboring graphs that differ by at most one edge; as consequence, the information in the generated graph does not confidently reveal the existence or absence of any one particular edge in the original graph, thus protecting individual link privacy.
To ensure DP on individual links, we exploit the existing link reconstruction based graph generation model GVAE (Kipf & Welling 2016). and design a training algorithm to dynamically distort the gradients of its sensitive model parameters by injecting proper amounts of Gaussian noise based on the framework of DPSGD (Abadi et al., 2016). We provide theoretical analysis on applying DPSGD to achieve edge-DP with GVAE based on the nature of graph data and the link reconstruction loss. Moreover, to improve the capturing of global graph structures, we replace the direct binary cross-entropy (BCE) loss on graph adjacency matrices in GVAE with a structure-oriented graph discriminator based on GCN (Kipf & Welling 2017) and the framework of VAEGAN (Gu et al.
2019 Larsen et al. 2016). We further prove the improved model to maintain the same edge-DP.
Backbone GVAE. Recent research on graph models has been primarily focused around GCN (Kipf & Welling 2017), which is shown to promising calculating universal graph representations (Maron et al.] 2019 Xu et al.) 2019/Chen et al. 2019 Keriven & Peyré 2019). In this work, we harness the power of GCN under the consideration of edge-DP by adapting the link reconstruction based graph variational autoencoder (GVAE) (Kipf & Welling 2016)
backbone graph generation model.
Notably, we are given a graph G = {V, E). where is the set of N nodes (vertices), and E is the set of M links (edges), which can be further modeled by binary adjacency matrix A. As common practice (Hamilton et al.) 2017). we set the node features X simply as the one-hoo not node identity matrix. The autoencoder architecture of GVAE consists of GCN-based graph encoder to guide the learning of a feedforward neural network (FNN) based adjacency matrix decoder, which can be trained to directly reconstruct graphs with similar links as in the input graphs. A stochastic latent variable Z is further introduced as the latent representation of A as
N
(Z A) II (Z, A) II N (Zil diag(a?)),
where μ g. (X, A) is the matrix of mean vectors pi, and a go (X is the matrix of standard deviation vectors a; g. [X, A) ÁReLU (AX.,) W, is a two-layer GCN model. g₁, and go share the first-layer parameters W 6- Á D AD- à is the symmetrically normalized adjacency matrix of G, with degree matrix D = Σ Aij. By and go form the encoder network.
To generate graph G', a reconstructed adjacency matrix A' is computed from Z by an FNN decoder N N IIII o (f(2,)f((zz)) =11==1
N N
p PAAIZ)
IIII =11=1
where (2)= = 1/(1+ + )), f is a two-layer FNN appended to Z before the logistic sigmoid function. The whole model is trained through optimizing the following variational lower bound
Lyer = Lre:
Lprior
(4)
llog (A - DKI
where Crve is implemented as the sum of an element-wise binary cross entropy (BCE) loss between the adjacency matrices of the input and generated graphs, and Lprior is a prior loss based on the Hiilbackk-Libbee divergence towards the Gaussian prior p(Z) II." p(z,) = II, (.
4

---

Under review as a conference paper at ICLR 2021
Enforcing DP. The probabilistic nature of Z allows the model be generative, meaning that after training the model with an imput graph G, we can detach and disregard the encoder, and then freely generate unlimited amount of graphs G' with similar links to G, by solely drawing random samples of Z from the prior distribution (o, I) and computing A' with the learned decoder network w.r.f. Eq. B). However, shown in (Kurakin et al., 2017 Gondim-Ribein et al.) (018)), powerful neural network models like VAE can casily overfit training data, so directly releasing a trained GVAE model poses potential privacy threats, links in its generated graphs may be highly indicative towards links in the training graphs.
In this work, we care about the generation model's rigorously protecting the privacy of individual links in the training data, i.e., ensuring edge-DP. Particularly, in Definition2 the inequality guarantees that the distinguishability of any one edge in the graph will be restricted to the privacy leak level proportional to e, quantifying the absolute value of privacy information possibly to be leaked by graph generation model.
According to Eq. 33. GVAE essentially takes graph G, in particular, the links E among the nodes V in G, as input and generates a new graph G' by reconstructing the links E' among the same set of nodes V. Therefore, if we regard GVAE as the mechanism M, as long its model parameters are properly randomized, the framework satisfies edge-DP. To be specific, any two input graphs G1 and G2 differing by at most one link in principle lead to similar generated graphs G', so information in G' does not confidently reveal the existence or absence of any particular link in G1 or G2.
To exploit the well-structured graph generation framework of GVAE, mechanism (Definition[] T (Dwork et al. (014) and DPSGD (Abadi et al. (016)) to enforce edge-DP on it. In our setting, G is the original training graph. Then Eq. (1 tells us that link reconstruction based graph generation model M can be randomized to ensure (e, 0) d-ddge-D with properly parameterized Gaussian noise. Prominently, we follow DPSGD (Abadi al., 2016) to inject designed Gaussian noise to the gradients of our decoder network clipped by a
leverage the Gaussian
C' as follows.
N
|| (V + +N1(0,
$o.c
Σ :=1
V Ve,,oL/max/
(5)
N
where C is the loss function of a link reconstruction based graph generation model, C' is the clipping hyper-parameter for the model's original gradient bound the influence of each link, and the noise scale hyper-parametes In the following theorem, we analyze and prove that the noised clipped gradient ğe.c applied above guarantees the learned graph generation model to be edge-DP, with a different condition from that in Definition I due to the learning process of link based graph generation model.
Theorem 1. In training a link reconstruction based graph generation model on a graph with N nodes with batch size B, given the sampling probability q = B/N, and the number of steps T, there exist explicit constants e1 and 02 that for any e < c1q2T, iteratively updating the model T times with ga,c e attains it with (e, -ddgge-D for any > if we choose
q log((1))))
where 61 2 1. log ga 02 S $1//col - for any Co E (0, 1).
The proofs of Theorem [ Mree detailed Appendix A
For the training of the DPGVAE decoder, L in Eq. 5 is specified as Lree in Eq. 4 Due to the link
reconstruction nature of DPGVAE, we derive Corollary from Theorem I as follows.
Corollary 1.1 (DPGVAE edge-DP). Under the same conditions in Theorem the decoder in DPGVAE for T times with Lo. attains it with (e, -ddgge-D.
7 iteratively updating
In the generation stage, we can disregard the encoder and only use the decoder to generate an unlimited amount of graphs from randomly sampled vectors from the prior distribution (O, I). Due to the randomness of the normal Gaussian distribution, the sampling process can be regarded as (0, DD- By the composability property of DP (Dwork et al.) 2014). generating graphs from random noises with the DPGVAE decoder satisfies (e, -eddeg--- whose release in principle does not disclose sensitive information regarding individual links in the original sensitive networks. Since we do not release the encoder network, we do not need to clip and perturb its gradients during training induce minimum interruptions.
5

---

Under review as a conference paper at ICLR 2021
Original Sensitive
GCN-Based Encoder Network (&. &.))
FNN--based Decoder
Reconstructed Graph
FNN-based
Decoder
Graph
(Generator) Network (f)
(Generator) Network (f)
Clip+Noise
Sample
GCN Based Discriminator Network
FNN INN-based
Discriminator Netwark
Part 21f)
Training
Inference
Edge-DP Graph
Figure 2: Neural architecture of DPGGAN (best viewed color): Our novel graph generation model consists of a GCN- based encoder, an FNN- based decoder (generator), and GCN+FNN-brit diseriminator. Sensitive data and modules are marked as red, while safe operations (i.e., gradient clipping, noise injection and sampling) marked as green, leading DP modules and data.
Improving structure learning, Besides individual link privacy, we also aim to preserve the global network structure ensure the utility of released data. As we discuss before, original GVAE computes the reconstruction loss between input and generated graphs based on the element-wise BCE between their adjacency matrices. Such computation is specified on each link, rather than the graph structure as a whole. To improve the global graph structure learning. we leverage GCN again, which has been shown universally powerful in capturing graph-level structures (Maron al. 2019 Xu et al. 2019 Chen et al. 22199] Keriven & Peyré 2019). In particular, we borrow the framework of VAEGAN from recent research (Gu et al. 2019] Larsen et al. 2016 Yang et al. 2019), and compute structure-oriented generative adversarial network (GAN) loss
Lyan lolg(((()) log(1 - D(A))
(6) where g' and f' are GCN and FNN networks similar defined before, besides at the end of g'' the node-level representations are summed up as graph-level representation, which resembles the recently proposed GIN model for graph-level representation learning (Xu et al., (019). In this DPGGAN framework, the decoder also serves as the generator, while D = f' is the discriminator.
with D(A) (X(g'(X,
Following (Gu et al. 2019), the encoder is trained w.t. Cree + λ Sprior. the generator w.r.t. Cree Ag and the discriminator w.z.t dz Az where A and x2 are aaper-parameter.. To enforce DP constraints and complete our proposed DPGGAN framework, Eq. ( with Lree substituted by Lree - >22 is applied to distort the gradients of the generator and guarantee edge-DP, which can be used securely generate networks with the other parts disregarded after training. The overall framework of DPGGAN is shown in Figure 2 and the training process is detailed in Appendix B
The intuition behind the novel design of DPGGAN is, the GCN encodings g' (A) and g' (A')) capture the graph structures of G and G', so reconstruction loss Cree |lg'(A) - -g'(A gA'' captures the intrinsic structural difference between G and G' instead of the simple sum the differences over their individual links. Note that the effectiveness of our structure- -onnture-orrented discriminator is critical not only because it can directly enforce effective training of the graph generator through the minimax game in Eq. (6). but also because it can learn to relax the penalty on certain individual links through flexible and diverse configurations of the whole graph as long as the global structures remain similar, which exactly fulfillls goals of secure network release. The benefits of such diversity enabled by the VAEGAN have also been discussed in image generation (Gu et al., 2019 Larsen et al. 2016).
Compared with DPGVAE, DPGGAN does not directly compute the link reconstruction loss based on BCE in Eq. 4 but rather computes it based on the graph discriminator D. However, the link reconstruction based graph generator of DPGGAN is exactly the same DPGVAE. Since also do not release after training, we can simply retrieve Corollary [.2 from Theorem I as follows. Corollary 1.2 (DPGGAN edge-DP). Under the conditions in Theorem 7 iteratively updating the generator in DPGGAN for T times with J0,(C.us X2L attains it with (e, -eddgeDD
With Corollary 1.2 we attain DPGGAN with the same (e, 8) -ddge--DDD DP protection of DPGVAE. For both DPGVAE and DPGGAN, the decoder/ decoder/generator generator networks only get exposed the noised and clipped gradients, representing the partial sensitive information within the training graphs. Hence, prevents the inference of training graphs from both learned model parameters and generated graphs.

---

Under review as a conference paper at ICLR 2021
4 EXPERIMENTAL EVALUATIONS
We conduct two sets of experiments to evaluate the effectivvnesss of DPGGAN in preserving global network structure and protecting individual link privacy. All code and data are also in the submission.
Experimental settings. To provide a side-to-side comparison between the original networks and generated networks, we use two standard datasets of real-world networks, ie., DBLP, and IMDB. DBLP includes 72 networks of author nodes and co-author links, where the average numbers of nodes and links are 177.2 and 258; IMDB includes 1500 networks of actor/actress nodes and co-star links, with average node and link numbers 13 and 65.9.
To show that DPGGAN effectively captures global network structures, we compare it and DPG- VAE under different privacy budgets (controlled by in Eq. (32)), regarding a suite of graph statistics commonly used to evaluate the performance of graph generation models, especially from global perspective (Bojchevski et al. 2018 You et al. 201 8b Yang et al. 2019) In particular, we train all models from scratch to convergence for K' times, where K is the number of networks in the datasets. Each time, the trained model is used to generate one network, which is compared with the original network regarding the suite of graph statistics. Then we average the absolute differences between the generated networks and the original networks, ensuring that the positive and negative differences do not cancel out. The results are summarized in [
Beyond the single value statistics, we also compare the generated graph regarding degree distribution and motif counts. For degree distribution, we convert each graph into a 50-dim vector (all nodes with degree larger than 50 binned together); for motif counts, we enumerate all 29 undirected motifs with 3-5 nodes and convert each graph into a 29-dim vector by motif matching. We compute the average cosine similarity between pairs of original graphs and generated graphs. Furthermore, we use the most widely studied graph-level downstream task, i.e., graph classification, to evaluate the global utilities of generated graphs. In particular, we evaluate the accuracy of the state-of-the-ar graph classification model, i.e., GIN (Xu et al., 2019), with the default parameter setting and 4:1 training-testing ratio. The results are summarized in Table 2
To facilitate better understanding towards how the graph statistics reflect the global network structure captured by the models, we also provide results of two recent deep network generation methods, i.e., NetGAN (Bojchevski et al.] 2018) and GraphRNN (You et al. 2018b). with default parameter settings and no DP constraints at all. this experiment, we expect to see the more effective structure-preserve models generate networks that are more similar to the original ones regarding various global and distributional graph properties and achieve high graph classification accuracy, thus maintaining high network data utility.
To show that DPGGAN effectively guarantees individual link privacy, we train all models for another K times each dataset. Instead of complete networks, randomly sample 80% of the original networks' links to train the models. After training and generation, we use degree distribution to align the nodes in the generated networks with those in the original networks. Then evaluate the standard AUC metric on the task of individual link prediction by comparing links predicted in the generated networks and links hidden during training in the original networks. In this experiment, we models generate networks that are less useful for
expect to see the more effective privacy-protecae predicting individual links in the original networks, thus guaranteeing network data privacy.
All experiments are done with four GeForce GTX 1080 GPUs and a 12-core 2.2GHz CPU. The training time of DP-enforced models is often slightly shorter due to early stops when the privacy budget runs out, (e.g., typical train of GVAE, DAGVAE. and DPGGAN takes 60, 42 and 53 seconds on average on DBLP). The generation times of the three models are roughly the same (e.g.. 0.02 second on average on DBLP). As direct comparison, NetGAN and GraphRNN take longer times under the same settings, especially for the generation (e.g., 89, and 4.5 seconds for NetGAN to train and generate, and 75 and 2.4 seconds for GraphRNN, DBLP). Although efficiency is not our primary concern, short runtimes (especially for generation) are favorable for efficient data share.
Due to space limitation, detailed settings of the neural architectures and hyper- parame-ars of our models are put into Appendix
SSattsstics we use including LCC (size of the largest connected component), TC (triangle count), CPI. (characteristic path length), GINI (gini index) and REDE (relative edge distribution entropy).
7

---

Under review as a conference paper at ICLR 2021
DBLP Networks
IMDB Networks
Models
LCC
TC
CPL
GINI
REDE
LCC
TC
CPL
GINI
REDE
Original
107.5
59,90
3.6943
0.3248
0.9385
13.001
305.9
1.2275
0.1222
0.9894
GVAE(no DP)
7.51
66,93
0.1330
0.0213
0.0084
0.0145
25.83
0.0121
0.0030
0.0016
NetGAN(no DP)
9.66
39.87
0.1943
0.0105
0.0022
0.0083
27.54
0.0192
0.0042
0.0011
GraphRNN(no DP)
10.27
57.43
0.2043
0.0415
0.0052
0.0594
27.26
0.0214
0.0155
0.0094
DPGVAE(c=10)
21.96
175.29
0.2471
0.0339
0.0153
0.0147
43.63
0.0367
0.0036
0.0030
DPGVAB(<=1)
23.80
187.20
0.3059
0.0343
0.0156
0.0253
43.73
0.0373
0.0038
0.0031
DPGVAB(==..)
26.07
215.13
0.3342
0.0344
0.0158
0.0320
44.12
0.0392
0,0042
0.0032
(PGGAN(E=10)
10.61
64.75
0.2035
0.0224
0.0093
0.0040
22.89
0.0164
0.0010
0.0017
DPGGAN(e=1)
12.38
70.97
0.2643
0.0353
0.0117
0.0053
23.81
0.0168
0.0029
0.0023
DPGGAN(==O.I)
24.62
77.41
0,2713
0,0485
0.0191
0,0113
24.91
0.0168
0.0029
0.0025
Table 1: Performance evaluation over compared models regarding suite of important graph structural statistics. The Original rows include the values of original networks, while the rest rows are the average absolute difference between generated networks by different models and the original networks. Therefore, smaller values indicate better capturing of global network structure and thus better global data utility. Bold font is used for values ranked top-3.
DBLP Networks
IMDB Networks
Models
Degree dist.
Motif ct.
GIN acc.
Degree dist.
Motif ct.
GIN acc.
GVAE(no DP)
0.6171
0,4093
0.3029
0.5132
0.4129
0.4698
Neno DP)
0.5754
0.4109
0.3471
0.4921
0.3891
0.4350
GraphRNN(no DP)
0.5454
0.3672
0.3210
0.4635
0.3721
0.3875
DDGVAA(==I) 0.5476
0,4038
0.3043
0.5081
0.4021
0.4625
DPGGAN(E=1)
0.6092
0.4150
0.3261
0.5486
0.4150
0.4725
Table 2: Performance evaluation regarding degree distribution, motif counts and GIN accuracy. Larger values for both cosine similarity and classification accuracy indicate better graph urility. Bold font is used for values ranked top-2.
Preserving global structures. In Table I. our strictly DP-constrained models constantly yield highly competitive and even better results compared with the strongest DP-free baselines regarding global network structural similarity between generated and original networks on both datasets, clearly showing the effectiveness of our models on global network structure preservation. As we gradually increase the privacy budget E, our two models (especially DPGGAN) apparently perform better, showing the effectiveness of our privacy constraints and clear trade-off between privacy and utility. Furthermore, as in Table 2 the graphs generated by DPGGAN are competitively similar to the original graphs regarding both degree distributions and motif counts, while achieving satisfactory graph classification accuracy. The improvements of DPGGAN all passed t-tests with p-value 0.01, which corroborates our novel design of the structure-oriented graph generation framework.
Protecting individual links. For both datasets, links predicted on the networks generated by DPG- GAN are much less accurate than those predicted on the original networks (26%-35% and 15%-20% AUC drops DBLP and IMDB, respectively)
well the networks generated by all baselines. This means even if the attackers identify nodes in the generated (released) networks of DPGGAN, they cannot leverage the information there to accurately infer the existence or absence of links between particular pairs of nodes on the original networks. This directly corroborates our claim that DPGGAN is effective in protecting individual link privacy.
Due to space limit, more details and discussions regarding the experimental results are put into we also provide graph visualizations for qualitative visual inspections.
Appendix D In Appendix B
CONCLUSION
Due to the recent development of deep graph generation models, synthetic networks are generated and released for granted, without the concern about possible privacy leakage over the original networks used for model training. In this work, for the first time, we pay attention to the task of secure network release and formulate its goals as preserving global network structure while protecting individual link privacy. Subsequently, we adopt the well-studied DP framework and develop DPGGAN, which protects individual link privacy by enforcing edge-DP on the graph generation model while preserving global network structure with a structure- -oreettre-rreetee graph discriminator. Comprchensive experiments show that DPGGAN is advantageous in generating networks that globally similar to the original ones (thus effectively maintaining network data utility), and at the same time, useless for predicting individual links in the original network (thus rigorously protecting network data privacy).
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. SIGSAC, 2016.
Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW, 2007.
Albert-Lászió Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439): 509-512, 1999.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet.. The johnson--inadenstrauss transform itself preserves differential privacy. FOCS, 2012.
Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. JACM, 2013.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. In JCML, 2018
Digvijay Boob, Rachel Cummings, Dhamma Kimpara, Uthaipon (Tao) Tantipongpipat, Chris Waites, and Kyle Zimmerman. Private synthetic data generation via gans. arXiv preprint (EX3:::803.03144 2018.
Cai, He, Guan, and Y. Li. Collective data-sanitization for preventing sensitive information inference attacks social networks. TDSC, 2018.
Qingrong Chen, Chong Xiang, Minhui Xue, Bo Li, Nikita Borisov, Dali Kaarfar, and Haojin Zhu. Differentially private data generative models. arXiv preprint arXi:: 2018.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. NIPS, 2019.
Quanyu Dai, Qiang Li, Jian Tang, and Dan Wang. Adversarial network embedding. In AAAI, 2018.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805.11977 2018
Kun Dong, Austin Benson, and David Bindel. Network density states. KDD, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. Theory cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Theoretical Computer Science, 9(3 4):211-407 2014.
Jennifer G. Dy and Andreas Krause (eds.). Differentially privute database release via kernel mean embeddings, volume 80, 2018.
Pál Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17-61. 1960.
TS Evans and Renaud Lambiotte. Line graphs, link partitions, and overlapping communities. Physical Review E, 80(1):016105, 2009.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence informa- tion and basic countermeasures. In SIGSAC, 2015.
Lorenzo Frigerio, Anderson Santana de Oliveira, Laurent Gomez, and Patrick Duverger. Diffcrentially private generative adversarial networks for time series, continuous, and discrete open data. In IFIP SEC, 2019.
George Gondim- Condim--ibbero, Pedro Tabacof, and Eduardo Valle. Adversarial attacks on variational autoencoders. arXiv preprint 1rXiv:1806.0e0 04646, 2018.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. arXiv preprint 1 2017.
Xiaodong Gu, Kyunghyun Cho, Jungwoo Ha, and Sunghun Kim. Dialogwae: Multimodal response generation with conditional wasserstein auto-encoder. In ICLR, 2019.
David Hallac, Youngsuk Park, Stephen Boyd, and Jure Leskovee. Network inference via the time-varying graphical lasso. In KDD, 2017.

---

Under review as a conference paper at ICLR 2021
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIPS. 2017.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICML, 2018.
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. TCC, 2013.
Nicolas Keriven and Gabricl Peyré. Universal invariant and equivariant graph neural networks. In NIPS, 2019.
Thomas N Kipf and Max Welling. Variational graph ancodenc...rs. In NIPS Workshop on Bayesian Deep Learning, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Kristine M Kuhn. Compensation as signal of organizational culture: the effects of advertising individual or collective incentives. IJHRM, (637))6634-6648 2009.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial machine learning at scale. ICLR, 2017.
Anders Boesen Lindbo Larsen, Søren Kaae Sønderby, Hugo Larochelle, and Ole Winther. Autoencoding beyond pixels using a learned similarity metric. In ICML, 2016.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. arXiv preprint 1802..1802.088 2018.
Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap stanford. wdw/ June 2014.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. In /CML,, 2018.
Tengfei Ma, Jie Chen, and Cao Xiao. Constrained generation semantically valid graphs via regularizing variational autoencoders. In NIPS, 2018.
Haggai Maron, Heli Ben-Hamu, Nadav Sharmir, and Lipman Yaron. Invariant and cquivariant graph networks. In ICLR, 2019.
Noman Mohammed, Rui Chen, Benjamin C. M. Fung, and Philip S. Yu. Differentially private data release for data mining. In KDD, 2011.
Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large datasets (how to break anonymity of the netflix prize dataset). SP, 2008.
Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. SP, 2009.
Mark Newman, Clustering and preferential attachment growing networks. Physical review 64(2): 025102, 2001.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private lcarning with pate. /CLR, 2018.
Alessandra Sala, Xiaohan Zhao, Christo Wilson, Haitao Zheng, and Ben Zhao. Sharing graphs using differentially private graph models. SIGCOMM, 2011.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification network data. mag., 2008
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In SIGSAC, 2015.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In ISP, 2017.
Börkur Sigurbjörnsson and Roclof Van Zwol. Flickr tag recommendation based on collective knowledge. In WWW, 2008.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In ICANN, 2018
10

---

Under review as a conference paper at ICLR 2021
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Areeminer: extraction and mining of academic social networks. KDD, pp. 9900998,000 2008.
Aleksei Triastcyn and Boi Faltings. Generating artificial data for private deep learning. AAAI, 2018.
Yue Wang and Xintao Wu. Preserving differential privacy in degree-correlatin based graph generation. TDP, 6 (2):127-145, 2013.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. JASA, 105(489):375-389, 2010.
Duncan Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks. nature, 393(6684):440, 1998.
Liyang Xie, Kaixiang Lin. Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv:/882.06633) 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Carl Yang, Lanxiao Bai, Chao Zhang, Quan Yuan, and Jiawei Han. Bridging collaborative filtering and semi-supervised learning: neural approach for poi recommendation. In KDD, 2017.
Carl Yang, Xiaolin Shi, Luo Jie, and Jiawei Han. know you'll Il be back: Interpretable new user clustering and churn prediction mobile social application. In KDD, 2018.
Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In NIPS, 2019.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovee. Graph convolutional policy network for goal-directed molecular graph generation. In NIPS, 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William I. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In ICMI,, 2018b.
Aston Zhang, Xing Xie, Kevin risk in anonymized heterogeneous information networks. In EDBT, 2014.
Chang, Carl A Gunter, Jiawei Han, and XiaoFeng Wang. Privacy
Xinyang Zhang, Shouling Ji, and Ting Wang. Differentially private releasing via deep generative model (technical report). arXiv preprint arXiv:1801 1001.0099, 2018.
Yanjun Zhang. Xin Zhao, Xue Li, Mingyang Zhong, Caitlin Curtis, and Chen Chen. Enabling privacy-preee preserving sharing of genomic data for gwass decentralized networks. In WSDM, 2019.
Dongmian Zou and Gilad Lerman. Encoding robust representation for graph generation. arXiv preprint 1r09. 2018.
Daniel Zügner. Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. KDD, 2018

---

Under review as a conference paper at ICLR 2021
A APPENDIX: PROOFS FOR THEOREM 1
In this appendix, we provide proofs for Theorem and derive Corollary [.] and Corollary 1.2 Theorem [ indicates link privacy protection achieved through updating model's parameters with elipped and noised gradient (latter referred to as DP learning) for link reconstruction based graph generation models. Corollary 1.1 and Corollary 1.2 derived from Theorem support us to guarantec (c, de-dge-D for DPGVAE and DPGGAN with DP leamnng in Theorem
The proof for Theorem is divided into three steps. We first briefly introduce the definition of the moment accountant privacy analysis and respective properties Section A for it being fundamentals our proof. Note that in (Abadi et al. (2016). DPSGD is originally designed for classical machine learning tasks, such as image classification. Therefore, in Section A.2 we leverage moment accountant to conduct the extended privacy analysis of DPSGD for general types of data and loss functions. Then in Section we apply the conclusion from Section (A.2onA.nnnn graph data and the link reconstruction loss function derive the theoretical analysis over edge-DP achieved by link reconstruction based graph generation models and finish our proof for Theorem Following the conclusion in Theorem T we tune gradient representations to certain gradient functions leveraged in training VAG decoder and DPGGAN generator to derive Corollary 1.1 and Corollary 1.2 as the theoretical support for the (s, -edeeeDD held by respective models.
A.1 MOMENT ACCOUNTANT
Our proof for Theorem D is mainly based moment accountant (Abadi et al. 2016). The definition of moment accountant and the properties leveraged in our proof are listed below.
Definition Let M D + R. a randomized mechanism and d, a pair of adjacent databases. Let auæ denote an auxiliary input. For an outcome o E RR the privacy loss at o is defined as:
Pr[M(aux, d) ol
e co; M, oux, c, dd) - log Pr [M (aux, d') = o]
(7)
The privacy loss random variable C (M, auæ, d, d') is defined as e (MM(d); M, oux, d, d'), i.ethee random variable defined by evaluating the privacy loss at an outcome sampled from M(d).
Definition 4. Let M D + R be randomized mechanism and d, d' pair of adjucent databases. Let auæ denote auxiliary input. The moments accountant is defined as:
(x
A max a. (>s aux, dl d')
auz,d.d'
where a (A; aux, d, d') A log E lexp (AC (M, d, d')) is the moment generating of the privacy loss random variable.
The following properties of the moments accountant proved in (Abadi 2016
Property 4.1. (Composability) Suppose that mechanism consists of a sequence of adaptive mechanisms Mi...., .M, where M; IT R, x DD R;. Then, for any output sequence 01,-..y Ok-1 and any X, we have
k am (x; Σ am; ..oo.......-1,,d d.)
(9)
where M is conditioned M. 's output being o, for < k. Property 4.2. [Tail bound] For any e > 0, the mechanism M (5,8)- DDD for
8 min exp (Am Ae)
(10)
A.2 THE GENERALIZED PRIVACY ANALYSIS OF DPSGD
To achieve (c, -edge DP for graph data, we exploit DPSGD (Abadi al. 2016) with necessary adaptions according to the special nature of graph data compared to other types of data (e.g. images), for which DPSGD was originally designed. The original DPSGD only provides DP proof for gradient function f clipped by C' with its fz-norm sensitivity A 1. C C. For classical tasks of machine learning like image classification, Aaf = C' is obvious. However, in more complex task like graph learning, minor change in the training dataset can probably induce different gap according to the chosen measurement. To explore potential of DPSGD with customized machine learning tasks. we further prove the privacy performance of DPSGD with a gradient function f with form sensitivity Azf s.
Therefore, to prepare for the proof for Theorem bound of privacy loss for Gaussian Mechanism as below.
first leverage moments accountant to derive the upper
12

---

Under review as a conference paper at ICLR 2021
Lemma 1. Suppose that f D - R2 with I[[()) Let and let J be sample from [zi] where each i [n] is chosen independently with probabiliry g i6a" Then for any positive integer
8² x2
In = the
Gaussian Mechanism M(d) Died f (d.) N (0, (0) satisfies
am v x² (1 g) +0(888100)
(II)
Proof. Fix d' Eier(m f (d:) = 0. Thus M(d) and M (d') are distributed identically except for the first coordinate and hence we have one- one-dimensional problem. Let denote the pdf of N (0, r²) and let denote the pdf of N (s, o²). We have
d d' d'U (dn). Without loss of generality, we assume f (d.) = s ej and
M (d')
(12)
M(d) ~ μ (1 q)f10 + gus.
We want show that
Bawa ((M())/HO(2)))) a,
(13)
Rzoap (mo(=)//(2))) aa
where is value be determined. We will use the same method as in (Abad et al. 2016) to prove both bounds, Assume have two distributions un and va, and wish to bound
Egann [vo(2)//c(3)))) EZNus [v0(=)//o(3))/41]
(14)
Leveraging binomial expansion, we obtain
E B (po(2)/v<(z))
E Bsne,
(1 + (vo(2) v.(x)) ((4z))/u.. (=))
Benns
(1+ (vo(z) v.(x)) (((x))//u(())) (11
(15)
A+1
X+1 ) Exnr, [[vo[()) (u.z))/v.()))
Σ
t=
The first term in Eq. 1S is 1, and the second term is
(o(2) - vo(2)]
+o 12(2) mo(2) vs(2) de
(A + 1)BEND
v2(2)
v=(2)
(16)
=A+1) mu(z)da (z(2)dz
-10
-A+11(1111) =0
Regarding conditions stated in the lemma, for both cases, where =
and = μoo P1 the
third term is bounded by q² x2 + 1)/(1 q)o² and this bound dominates the sum of the remaining terms. We provide the proof for the case of (vo po. V4, 11), and the proof of the other is similar.
13

---

Under review as a conference paper at ICLR 2021
To upper bound the third term in 15 note that pu(2) (1 (2) and write
Mo(2) 1(22) 27
Bz
1((2)
[Ho(x) - Ma(2)
= q Ezau
1(2)
(17)
(uu(2) 1z))2))
q²
de
pu(2)
-00
9
4:00
((o(2) - -a(=))² d=
d Bougo
{
(nolz) - pe,
2
(z(
(=)
Recalling the definition μlo and the normal distribution, we have
Ezans ( [a(2)) - (1())
)
(1-eap)
2sz 82 27
EENaa
(=(=)
2a²
(18)
288 - 8²
)
482 25²
1 2B
exp
20
ExNuo
exp
20²
For the second term in Eq.
18 Exnee
exp
22z=o²
we have
285
52
)
1
( (== s)?)
Be-po
exp
exp
dz =
(19)
20²
2
2T
20²
For the third term in Eq.
18).
have
Asz
20
x²
+00
1
(=2-2s))
Ez-po
exp
exp
de
20²
0
o
2m
20²
000
(20)
8²
exp
x²
Thus, for Eq.
18
we have
( [Ho(2) (Ho(s)=
m1(=))
E Exwuo
exp (5//03) -1
(21)
(z(2)
Hence, the third term in the hinomial expansion of Eq.
15 is
(
1+1
Ezen
( [p(()) - m(x) m(2)
(no(z)-u(z)
+(+
expl (
(22)
2
2(1 4)
For a 2 8, is easy to get exp(
S
2n² of. Therefore, we retrieve that
(
1 +
[uu()) ( 1==))
m(x))
)
27
X(A + 2)
Bren
(23)
2
9)02
By standard calculus, get [a(()) (z(()) = - uh (z)dz Note that 16(2) is monotonically decreasing in (-o0, +oo). Thus, hound the remaining terms, derive
Vz 0: (oo()) m.(=)) -s(z s)nr(2)/o²
Az 2 8: (a((2) p.(2)] S zspu(z)/o²
(24)
vA < (m0(s) -..(=) 5 mo(2) (exp (s² (32/20²)
- 3d ppooz\/00
14

---

Under review as a conference paper at ICLR 2021
We can then write
[o(z) (12)
(1(2)
[0(2) 11(=)
[1=)
de
(²=)
(25)
! [(=)
(a(2) ml=)
d2
(===)
(u(a) - (((2)
[(=)
d2.
((2)
We consider these terms individually. repeatedly make use three observations: (1) po - /
q (Jo (2), 2 (1 q)Ho. (3) 2 gra. and (4) Tp [|=|]] s o o'(t 1)!!. The first term can then be bounded by
po(2)|= 11'd=
/ o 21
qls
Me
dz
(26)
98
Ms 1(2 s) dz
2
-00
98"
(t:
1)!!
20
Then the second term is at most
(1 - 9) ( m(2)) ( (o(2)
d'
- pu(=)) cl
(1 q)¹ I u(2) (6"100))| dz
q¹
dz
(27)
S n' 21
0)'02""
Similarly, the third term is at most
q'
- 25 J.
p=(=) dz (ts'(t11)!! (I (1-4)* q)--
(28)
Under the assumptions on q, a, and A, is easy to check that the three terms, and their sum, drop off geometrically l'sst in L for > 3. Hence the binomial expansion (5) is dominated by the = 3 term, which is O (s %8/0"" Therefore, the lemma is proved.
With Lemma we retrieve the upper bound of privacy loss the Gaussian Mechanism. Hence, based on Lemma D and Property 4.1 we provide the generalized privacy analysis of DPSGD with different learning tasks, which iteratively performs multiple times of the Gaussian Mechanism.
R2 with [[f(-)) S s. Let J be a sample from [N] that each E [N] chosen independently in probability q = |J//,, given the number of steps T. for any cu E (0, 1), there exist explicit constants C1 and ou that with any < CT iteratively computing T times of M(d) in Lemma /
Lemma 2. Suppose that f
attains it with (e, 8)-DP for any 5 > 0 if we choose
g8y T (1g(1/8)
(29)
where c₁ 2 co
log go and 02 S v voo
for any Oo E (0,1). 1).
Proof. Assume for now that o, À satisfy the conditions Lemma I After T times of iteration, with Property
4.1 we derive that a(A)= < Tg's X²/0". In order to to guarantee the whole training process to be (s, 8) -DP.
combining a()) with Property 4.2 for any co E (0, 1), we choose
Tq 2x² 2////0= //2 onde, exp((co 1) < 5.
(30)
15

---

Under review as a conference paper at ICLR 2021
Plugging the condition À 1 of log & into Eq. accomplish (e. ()DP) by setting
30 derive the bound for as log T to cy ge
1
gs T log(1/6)
(31)
Vcol1 ca)
where Co E (0,1).
A.3 PRIVACY ANALYSIS FOR THE LINK RECONSTRUCTION BASED GRAPH GENERATION MODELS WITH DPSGD
In this section, conduct the theoretical privacy analysis for link reconstruction based graph generation model based on Lemma Ia and obtain the conclusion of Theorem
Theorem 1 In training link reconstruction based graph generation model on a graph with N nodes with batch size B. given the sampling probability 9 B/N, and the number of steps T, there exist explicit constants e₁ and 0g that for any eiq"T, iteratively updating the model T times with go.c attains with (e, edgee DP for any > if we choose
9V log(1/8)
where 01 log +.- 02 1/1//oo co) for any co E (0, 1).
Proof. Recall the expression of ğs,4 as in Eq.
I ( + /
N Σ
90.c
1 N
V Ve..e//mxx(
where L is the loss function for a link reconstruction based graph generation model, C is the clipping hyper- parameter for the model's original gradient to bound the influenee of each node, and the noise scale pypper-aarmmete. According to Definition] | Go.c is Gaussian mechanism. Therefore, we first analyze the fz-norm sensitivity of the clipped gradient function Ge,c. and then plug the sensitivity value to Lemmaaaan conclude the privacy cost of training DPG,AE, thus finishing the proof for Thereom T
Following the graph reconstruction procedure in (Simonovsky & Komodakis 2018), single value in the adjacency matrix sufficient to represent one edge the respective graph for both directed and undirected graphs. Therefore, referring to Definition 2 though changing an edge
graph affects 2 nodes for node classification tasks, for a structural inference task, i.e., graph reconstruction, as our work targeting at, adding or removing an edge only results at most I record difference. Together with V.,.e being clipped as its 2--nrrm
no more than C, we obtain the sensitivity of M v.. max(1, & C.
With plugging in the clipped Ve,,eL'ss sensitivity (s = C) into Lemma 2 we derive Theorem I We prove that, given the sampling probability q = B/N and the number of steps T, with explicit constants C 2 og log 1
and < (1-)) where co (0, 1), through iteratively updating model T times with Eq. 5 the outcome generation model achieves (s, -dde DP for any ε "T and 8 >> when choose
(ogg//))
(32)
Recall the training process for the decoder in DPGVAE and the generator in DPGGAN in Section
3 in Jo.c
is substituted with Cree and Cree + X2L respectively. For both Lree and Lree + Ag their gradients are clipped with C and adding Gaussian noises during the training process. Based on Theorem [ we derive
Corollary 1.I and 1.2 for the decoder in DPGVAE and the generator in DPGGAN respectively below.
Corollary I.I VAE edge-DP). Under the same conditions in Theorem I iteratively updating the decoder in DPG V
E times with Go.Er.e attains it with (e, 8)-edge-DP.
Corollary 1
DPGGAN Ddge Under the same conditions Theorem iteratively updating the generator DPGGAN T times with
attains with (s, 6)-edge-DP.
With Corollary [.I and 1.2 under specified conditions, the public model (either the decoder in DPGVAE or the
generator in DPGGAN) Is guaranteed with (s. -ddge-DDPP by the DP training process. For both DPGVAE de- coder and DPGGAN generator updated with noised and elipped representations of the sensitive training graph,
16

---

Under review as a conference paper at ICLR 2021
they only record noised and partial sensitive information. DPGVAE decoder and DPGGAN generator's link reconstruction procedures, reflecting training information, only allude the desensitize information rather than the truc sensitive training information. Thus, DPGVAE decoder and DPGGAN generator not only prevent privacy leakage from their inner parameters with DP learning but also preserve the raw private training graphs from being accurately inferred through the respective outputs.
B APPENDIX: DETAILED TRAINING ALGORITHM
The overall architecture of DPGGAN is shown in Figure in the main content. In Figure 2, the original graph is fed into the GCN based encoder network compute node embeddings, which is then compared with the prior distribution.//U I) and fed into the FNN-based decoder/generator network f produce the reconstructed graph and generated graph. After going through the GCN-based based discriminator network part 1 (g') ). a reconstruction loss computed between the reconstructed graph and the original graph, and discrimination loss is computed for the generated graph and original graph after the FNN-based discriminator network part 2 (f').
Algorithm DPGGAN
Input Graph data G(A, X), clipping parameter C, decay ratio y, privacy budget e, noise scale a, total number of nodes N, batch size
gN, learning rate 1), maximum number of training epochs T,, loss weighing parameters Å and X2
Differetiiffrrttiaalll private decoder f.
Initialize weights randomly for ga- go. Bo. g' and
for epoch f = 0 to do
for iteratinn i to N/B do
Sample subgraph G (A.uh, Xauh) of size B Mean vector: gu (Xsub, Asub)
Standard deviation vector: + go (Xoub; Asub)
Update (Z A) II N .V (NZz,lm diag(o?))
Sample 24, 3, ~ (Z) X, A)
Reconstruct adjacent matrix A' off(z)) f(2,))
10
Eprae DRL (g (Z A (l))
Lgan log (D(A)) + log(1 D(A'))
12
for node v; G.ub do
13
Compute go (z:) + 0(Crec Xz
14
end
Clip gradient: (0;)) go(z:)/mazel( (nselrrdll)
15
Perturb gradient Ōe + B EE (xx)))) )+ + NO0,000
16
17
Average gradient: go <- E, (z;)
Update f + n Jo: f.g + P..Ver ve
//apply DP learning to the generator
19
Update g go + n (g + A(prrio))
end
21
Update C C#t
22 end
Here, we give more details towards its training procedures in Algorithm 1 For a better description, shorten as go go In the algorithm, for proper gradient distortion, devise gradient clipping in Line [3] and noise injection in Line I6 which is only applied to the generator network
90,iCrre g0.iCree-2g (gan) (io,CCCe (Caeac-Ag
Line [8] In Line 21 we gradually reduce the clipping byrer--rr C' as the volume of gradients decreases
along training.
In the experimental analysis, existing works often fix 5 as a dataset-speciffe value like 10-5, and then analyze the performance of models based fixed privacy budget (Abadi al. 2016) fixed noise scale (Papernot al. 2018). According to Theorem [ our experiments are conducted with fixing noise scale 2 T log(1//)/e,, where < 2 log 1 "1 In this work, other than the noise scale a, control the variance, we also fix 6, the sampling ratio g. for better analysis of the model's privacy loss. Note that we vary the number of training iterations (query number) T to study the relation between the model's performance and the privacy budget.
17

---

Under review as a conference paper at ICLR 2021
0.0
0.80
0.8
0.75
0.7
0.6
0.65
0.4
DF50 1p10 1.
0.55
DVAC
MADAY
090001 120
--- pr0se (26
0.90
9.50
125
1775
0.50
0.5
0.50
1.50
125
175
2.00
(a) DBLP
(b) IMDB
Figure 3: Accuracy of links predicted based networks generated by DPGGAN with varying hyper-parameters and evaluated on the original networks. Lower AUC means the information in the generated networks is less useful in revealing the true existence or absence of links in the original networks, thus better individual data privacy.
C APPENDIX: MORE DETAILS OF EXPERIMENTAL SETTINGS
For GVAE and our models, we use two-layer GCNs with sizes 32 -> 16 for both g,, and ga of the encoder network, where the first layer is shared, and use two-layer FNNs with sizes 16 - 32 for f of the decoder (generator) network. For DPGGAN, we use another two-layer GCN with same sizes for g' and a three-layer FNN with sizes 16 + 32 + for f', For De-related hyper-parametert we follow existing works (Abadi et al.) 2016 Shokri & Shmatikov 2015) to fix 5 to 10 a to 5, and g to 0.01 (which determines the batch size B as vary from 0.1 10
how much graph-level utilities we terminate the training of DPGGAN T iterations when e depleted. Other than the essential parameters in Eq. (32). we empirically set the clipping parameter C' to 5, decay ratio to 0.99, learning rate to 10 and the loss weighing parameters a and X both to 0.1. We do not observe the model to be very sensitive to the setting of these non-essential parameters.
B N with N the graph size). Then
preserved under different privacy budgets. According Eq.
D APPENDIX: MORE DETAILS OF EXPERIMENTAL RESULTS
In this work, we define the goals of secure network release as preserving global network structure while protecting individual link privacy. In the main content, have presented experimental results support the effectiveness of DPGGAN in both perspectives. That is, for global network structure preservation, we show that the generated graphs of DPGGAN are competitively similar to the original graphs in comparison with the DP-free state-of ofte--of-hhe-at art graph generative models regarding a suite of commonly concerned global graph statistics, and for individual link privacy protection, show that the links predicted in the generated graphs of DPGGAN are useless (with low accuracy) when evaluated in the original graphs.
The suite of statistics measures the glohal network structure from different perspectives. As can he inferred from TC, CPL, and GINI, the IMDB networks are in general smaller. tighter, and likely more structurally complex than the DBLP networks, which favors link generation models (e.g.. GVAE) over sequence generation models (e.g.. NetGAN, and GraphRNN). Consequently, DPGGAN also performs better on the IMDB networks, indicating its advantages in modeling complex link structures as whole.
addition to the graph statistics, we further demonstrate the data utility of networks generated hy DPGGAN with graph classification, which is the most widely studied graph-level downstream task. We deem this task important towards evaluating network data utility, especially under our consideration of global network structure preservation, because correct graph classification requires the generated graphs to share essential structural properties with the original graphs. As we can see from Table in the main paper, the data utilities evaluated with graph classification are consistent with those evaluated with global graph statistics, as shown in Table I in the main paper. Our two up-constrained models yield highly competitive performance compared with the DP-free state-of-the-art graph generative models.
As for privacy protection, we conduct more detailed inspections of the performance of individual link prediction. particular, we vary two of the major paremeerreetess, i.e., the privacy budget e, and sampling ratio g. Consistently with the results in Table | larger privacy budgets lead to more privacy leakage, which allows attackers to infer individual links in the original networks with higher accuracy. While some op-constrained deep learning models are observed to be sensitive to the sampling ratio during training (Ahadi et (016 Shokri & Shmatikav 2015), the privacy protection of DPGGAN is robust when g is changed in large ranges in practice.
18

---

Under review as a conference paper at ICLR 2021
E APPENDIX: QUALITATIVE GRAPH VISUALIZATIONS
To understand the bchaviors and performances of compared algorithms, conduct visualizations hetween the original graphs and graphs generated graphs by different algorithmss We mainly focus on visualization of DBLP author networks, since they are in general smaller, sparser and thus easier to visually inspect. We draw the graphs with Network
In general,
observe in Figure 4-10:
The graphs generated by algorithms without constraints NetGAN and GraphRNN are more similar to the original graphs, which is consistent with our results Table and in the main paper.
2. After enforcing the DP constraints, the graphs generated by DAGVAE significantly different from the graphs generated by GVAE, especially regarding local structures around individual nodes.
3. The graphs generated by DPGGAN, while also having different local structures compared with those generated by GVAE, have more similar global structures with the original graphs.
Original
NetGAN
GraphRNN
GVAE
DPGVAE
DPGGAN
Figure 4: Visualizations on DBLP author network
hhpps//nctworkx. iithubio
19

---

Under review as a conference paper at ICLR 2021
Original
NetGAN
GraphRNN
GVAB
DPGVAE
DPGGAN
Figure 5: Visualizations on DBLP author network 2.
Original
NetGAN
GraphRNN
GVAE
DPGVAE
DPGGAN
Figure 6: Visualizations on DBLP author network 3.
20

---

Under review as a conference paper at ICLR 2021
Original
NetGAN
GraphRNN
GVAE
DPGVAE
DPGGAN
Figure 7: Visualizations DBLP author network 4.
Original
NetGAN
GraphRNN
GVAE
DPGVAE
DPGGAN
Figure 8: Visualizations on DBLP author network 5.
21

---

Under review as a conference paper at ICLR 2021
Original
NetGAN
GraphRNN
GVAE
DPGVAE
DPGGAN
Figure 9: Visualizations on DBLP author network
Original
NetGAN
GraphRNN
GVAE
DPGVAE
DPGGAN
Figure 10: Visualizations on DBLP author network
22


Reviews:
[{"review_id": "rv8OrMoNQxU", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of learning graph properties with differential privacy (DP) constraints on edges. The problem is well-motivated in the paper with potential applications in social network learning where interactions between users (nodes) are sensitive. \n\nThe techniques involve recent advances in graph generation networks and DP deep learning. The network structure is based on recently proposed Graph VAE and VAEGAN. DPSGD is used during the training process to ensure the privacy guarantee of the process. Experiments are conducted to compare the proposed algorithm to a few nonprivate algorithms and the performance is comparable in certain applications.\n\nAn interesting observation of the paper is that it is enough to preserve privacy when training the generator network since the inference is only based on the generated network. \n\nMy main concern about the paper is its novelty. It seems to combine results from different areas. I hope the novelty can be further explained in the response.\n\nOther comments:\n1. In the experiments, it would be better to report delta values for the privacy guarantees for each experiment.\n2. It seems the exact nonprivate counterpart of DPGGAN is not included in the experiments. It would be nice to have results on it to see the exact influence of privacy. For example, in Table 2, Both DPVAE and DPGGAN seem to perform better than NetGAN and GraphRNN algorithms. It would be better if the authors can decouple the influence of privacy and network structure.\n3. It seems unnecessary to include the whole proof of DPSGD in the appendix since it is almost identical to the original paper. Including the sensitivity analysis would be enough to me.", "extra_scores": {}, "extra_text": {}}, {"review_id": "iNmCCy1cDhl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work consider the problem of link privacy when releasing models that are trained on graph data. It achieves this by making a generative graph model based on a VAE differentially private. Differential privacy is obtained by adding noise to gradients during training (DPSGD approach). The paper uses graph metrics and a classification downstream task to evaluate the utility of generated graphs. Comparison of algorithms with related work and details of the mechanism could be expanded to articulate novelty and significance of the work.\n\nI. The paper is well written and nicely merges ideas of DP + VAE + graphs for edge privacy.\nII. It would be good to see the main body of the paper articulating what the difference is between papers that use DPSGD from Abadi et al. as is and this paper. That is, what exactly had to be changed for graph data. Even after reading the appendix it was not obvious.\nIII. Experimental results could include accuracy of classification tasks of graph network models as it seems baselines in the paper use non-private generated networks only for downstream tasks. It may suggest that accuracy of generated networks on these tasks is already not optimal and the utility impact of DP is smoothened as a result.\n\nDetailed comments:\n1. Theorem 1 and page 5. Please consider adding what is different from DPSGD mechanism; what was the challenge in applying DPSGD in this setting.\n2. A2 states \"However, in a more complex task like graph learning, a minor change in the training dataset can probably induce a different gap according to the chosen measurement.\" The use of word \"probably\" is worrisome. Sensitivity should be properly analyzed when guaranteeing DP and adding noise based on it.\n3. Lemma 1: please articulate how s and C depend on each other or relate, if at all. How is this result  different from that in Abadi et al. What would noise addition/clipping be?\n4. Theorem 1 proof in Appendix: please explain how this is different from Abadi et al. given that s=C.\n5. Does Algorithm 1 make use of s? If not why Lemma 1 was needed.\n6. Please explain how Algorithm 1 differs from DPGAN work in Xie et al 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YT9k3FiXnQu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method, Differentially Private Graph Generative Nets (DPGGAN), to release graph in way the preserves utility while preserving privacy. This method trains a deep graph generation model in a differentially private manner, by injecting Gaussian noise to the gradients of link reconstruction module, thereby claiming to guarantee edge privacy, while ensuring utility via a structure learning component based on a variational generative adversarial network (GAN) architecture, to enable structure-oriented graph comparison to the original.\n\nThe motivation of the work is sound, yet the work does not deliver on its main promise: while the claim is made that link privacy is protected, there is no experiment to justify this claim. While an experiment is mentioned that purportedly does this, the mentioned results are not shown, neither in the main paper, nor in the appendix. The closest the work comes to reporting such results is this statement:\n\n  \"... links predicted on the networks generated by DPGGAN are much less accurate than those predicted on the original networks (26%-35% and 15%-20% AUC drops on DBLP and IMDB, respectively) as well as the networks generated by all baselines.\"\n\nThese results are not presented, and the privacy parameters ε that lead to them are not discussed. Thus, it is hard to know how much utility has to be sacrificed for the sake of the privacy gains mentioned. Further, a drop of 15% does not corroborate the claim that the released data useless for link prediction.\n\nOverall, while the paper claims to offer robust privacy guarantees towards various graph attacks, such guarantees are not explicitly spelled out. It seems to be taken for granted that a differentially private link reconstruction provides the intended guarantees, yet that begs the question of what protection is achieved in practice, under a learning-based attack. The fact that learning under differentially privacy can be surprising successful, and thus constitutes an attack on differential privacy, has been established in previous work [1]. This paper should reflect more thoroughly on what privacy means in the proposed setting, how it is shown, and what utility it corresponds to. On the other hand, there have been efforts to define explicit guarantees regarding link reconstruction [2, 3], which this work does not take in consideration.\n\nIncidentally, the paper claims that graphs lack efficient universal representations, citing [Dong et al., 2019]. It is not clear how the cited paper, which studies a form of universal graph representation, supports this statement. Besides, there is work explicitly dealing with efficient universal graph representations [4], based on similar principles to those studied in the cited work.\n\nLast, previous work [5] has already established, to a higher degree that it is done here, that any kind of structural identification attack can effectively be prevented using random edge perturbation, even while important properties of the whole network, as well as of subgraphs thereof, can be accurately calculated on the perturbed data. Given these results, it is unclear what this work adds to what has been already established.\n\nReferences:\n[1] Personal privacy vs population privacy: learning to attack anonymization. KDD 2011.\n[2] k-isomorphism: Privacy-preserving network publication against structural attacks. SIGMOD 2010.\n[3] L-opacity: Linkage-Aware Graph Anonymization. EDBT 2014.\n[4] NetLSD: Hearing the Shape of a Graph. KDD 2018.\n[5] Delineating social network data anonymization via random edge perturbation. CIKM 2012.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Va3lS8jL9KR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of releasing sensible structured data, where there are two inlined challenges: 1. The global network structure should be effectively preserved; 2. The link privacy should be rigorously protected. This paper looks at the secure release of network data with deep generative models. Specifically, the paper develops two models, DPGVAE and DPGGan, which can be viewed as a combination of DP-SGD and graph generation techniques. Extensive experiments are carried out on real-world network datasets, and the positive results have shown the effectiveness of the new models.\n\nI think the problem this paper looks at is both interesting and fundamental. Most of the current DP works focus on estimating one specific property of the dataset's underlying distribution, e.g., mean of the distribution. However, in many real-world applications, the tasks can not be known beforehand, and a potential solution is to release synthetic datasets under DP constraint. As far as I know, there are few papers in this area of privately releasing synthetic datasets with deep generative models.\n\nThis paper has proposed two models (DPGVAE and DPGGan), both reasonable to me. Meanwhile, experiments are carried out on real-world network datasets, and it has shown that for many structural statistics, the algorithms have competitive performance. I have little background knowledge of graph generation, and I can not give many technical comments:\n1. I will be appreciated if the authors can provide the results when $\\varepsilon = \\infty$, which I expect to be better than the case when $\\varepsilon = 10$. Does it mean your algorithm outperforms the current best algorithm in IMDB when there is no privacy constraint?\n2. I think it is also interesting to include some experiments on synthetic datasets. I believe for some extreme graph structure, DP should have more impact. For example, if the objective is to estimate the number of triangles in the graph, I expect the privacy to incur more loss when the underlying graph is complete compared with a sparse graph.\n3. From the algorithmic perspective, I  think both models can be viewed as a simple combination of DP-SGD and graph generation techniques. I am not sure this paper has made many theoretic contributions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies synthetic data generation for graphs under the constraint of edge differential privacy. There were a number of concerns/topics of discussions, which we consider separately:
1. Theoretical contributions. There are not that many theoretical contributions in this paper. I think this is OK, if the other components are compelling enough. On the theory, the authors mention that accounting for the constants is important in the analysis of DPSGD. On the contrary, I would say that these constants are not very important: if one requires specific constants, numerical procedures can determine values, otherwise for the sake of theory, no one generally needs these constant factors.

2. Empirical/experimental contributions. This was the primary axis for evaluation for this paper. None of the authors were especially compelled by the results. The methods are essentially combinations of known tools from the literature, and it is not clear why these are the right ones to solve this problem in particular. If the results were very exciting, that might be sufficient to warrant acceptance, but it is still not clear how significant the cost of privacy is in this setting. The experiments are not thorough enough to give serious insight here. It is a significant oversight to not provide results on DPGGAN without the privacy constraint, as this is the best performing model with privacy. The omission of something as important as this (and lack of inclusion in the response, with only a promise to include later) is indication that the experiments are not sufficiently mature to warrant publication at this time. The decision of rejection is primarily based on concerns related to the empirical and experimental contributions.

3. Privacy versus link reconstruction. Reviewer 4 had concerns about the notion of privacy, claiming that it does not correspond to the probability of a link being irrecoverable. This is differential privacy "working as intended", which is not intended to make each link be irrecoverable: it is simply to make sure the answer would be similar whether or not the edge were actually present, so it may be possible to predict the presence of an edge even if we are differentially private with respect to it (e.g., the presence of many other short paths between two nodes are likely to imply presence of an edge). Some discussion of this apparent contradiction might be warranted, as this might mislead reader who are specifically trying to prevent edge recovery. It might also be worthwhile to have discussion of node DP in the final paper. The authors comment "we focus on edge privacy because it is essential for the protection of object interactions unique for network data compared with other types of data" -- the stronger notion of node differential privacy might also be applicable here. It would indeed be interesting to know whether it can preserve the relevant statistics (some of which seem more "global" and thus preservable via node DP).


Decision: Reject