Secure Deep Graph Generation with Link Differential Privacy

1 Introduction

Nowadays, open data of networks (graphs) play a pivotal role in data mining and data analytics [Yang et al., 2020; Xie et al., 2020]. 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 [Sigurbj¨ornsson and Van Zwol, 2008; Kuhn, 2009]. However, graph 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 at stake under collective attack models facilitated by the underlying graph structure [Zhang et al., 2019; Cai et al., 2018; Sun et al., 2018]. Can we find a way to securely generate graph data without drastic sanitization that essentially renders the released data useless?

∗Corresponding Author

†Equal Contribution

Figure 1: A toy pair of anonymized and generated networks.

In dealing with such tension between the need to release utilizable data and the concern of data owners' privacy, quite a few secure deep generative models have been proposed recently, focusing on grid-based data like images, texts and gene sequences [Papernot et al., 2018; Sun et al., 2020a; Sun and Lyu, 2020]. 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 graph data, due to its modeling of complex interactive objects.

Motivating scenario. In Figure 1, 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 (i.e., (a) in Figure 1) 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 a similar set of customers (e.g., a 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 1 triangle, and customer B as the only node with degree 2 and within 1 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.

As the first contribution in this work, we define and formulate the goals of secure graph generation as preserving global graph structure while protecting individual link privacy. Continue with the toy example, the solution we propose is to train a deep graph generation model on the original network and release the generated networks (e.g., (b) in Figure 1). Towards the utility of generated networks, we require them to be similar to the original networks from a global perspective, which can be measured by various commonly graph 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 information in the generated networks cannot confidently reveal the existence or absence of any individual links in the original networks (e.g., the attacker may still identify customers A and B in network (b), but their link structure may have changed).

Subsequently, there are two unique challenges in learning such structure-preserved and privacy-protected graph generation models, which have never been explored so far.

Challenge 1: 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 and Shmatikov, 2009]. Moreover, graph structure can always be converted to numerical features such as spectral embedding, after which most attacks on grid-based data like model inversion [Fredrikson et al., 2015] and membership inference [Shokri et al., 2017] can be directly applied for link identification. Existing frameworks [Nobari et al., 2014; Xue et al., 2012] for graph link protection only demonstrate certain types of privacy regarding specific empirical measures without principled theoretical guarantee. How can we design an effective mechanism with rigorous privacy protection on links in graphs against various attacks?

Challenge 2: Effective preservation of global graph structure. To capture the global graph structure, the model has to 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 arbitrary node orders. How can we allow a graph 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 generation of graph data with deep neural networks. Technically, towards the aforementioned two challenges, we develop Differentially Private Graph Generative Adversarial Networks (DPGGAN), which imposes DP training over a link reconstruction based graph generation model for rigorous individual link privacy protection, and further ensures structure-oriented graph comparison for effective global graph structure preservation. In particular, we first formulate and enforce edge-DP via gradient distortion by properly injecting designed noises during model training. Then we leverage graph convolutional networks [Kipf and Welling, 2017] through a generative adversarial network architecture [Gu et al., 2019] to enable structure-oriented graph discrimination.

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 graphs by computing a suite of commonly used graph properties to compare the global structures of generated graphs with the original ones. On the other hand, we validate the privacy of individual links by evaluating links predicted from the generated graphs on the original graphs. Consistent experimental results show that DPGGAN is able to effectively generate graphs that are similar to the original ones regarding global graph structure, while at the same time useless towards individual link prediction.

2 RelatedWork

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., 2014]. Recent advances in deep learning have led to the rapid development of DP-oriented learning schemes. Among them, the Gaussian Mechanism [Dwork et 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 ∆2f = max ‖G-G′ ‖1=1 ‖f(G) - f(G′ )‖2, we have:

where N(0, ∆2f 2σ2 ) is a random variable obeying the Gaussian distribution with mean 0 and standard deviation ∆2fσ. The randomized mechanism Mf(G) is (ε, δ)-DP if σ ≥ ∆2f √2 ln(1.25/δ)/ε 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 1 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; Sun et al., 2020b]. For example, [Frigerio et al., 2019] enforces DP on the discriminators, and thus inductively on the generators, in a GAN scheme. However, none of them can be directly applied to graph data due to the lack of consideration of structure generation.

For graph structured data, two types of privacy constraints can be applied, i.e., node-DP [Kasiviswanathan et al., 2013] and edge-DP [Blocki et al., 2012], which define two neighboring graphs to differ by at most one node or edge. In this work, we aim at secure graph generation, and particularly, we focus on edge privacy because it is essential for the protection of object interactions unique for graph data. Several existing works have studied the protection of edge-DP. For example, [Sala et al., 2011] generates graphs based on the statistical representations extracted from the original graphs blurred by designed noise, whereas [Wang and Wu, 2013] enforces the parameters of dK-graph models to be private. However, based on shallow graph generation models, they do not flexibly capture global graph structure that can support various unknown downstream analytical tasks.

Graph Generation (GGen). GGen has been studied for decades and is widely used to synthesize network data for developing various collective analysis and mining models. Earlier works mainly use probabilistic models to generate graphs with certain properties [Watts and Strogatz, 1998; Barab´asi and Albert, 1999], 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 and Welling, 2016; Bojchevski et al., 2018; You et al., 2018; Simonovsky and Komodakis, 2018] For example, NetGAN [Bojchevski et al., 2018] converts graphs into biased random walks, learns the generation of walks with GAN, and assembles the generated walks into graphs; GraphRNN [You et al., 2018] regards the generation of graphs as node-and-edge addition sequences, and models it with a heuristic breadth-firstsearch scheme and hierarchical RNN. These deep learning models can often generate graphs with much richer properties, and flexible structures learned from real-world networks.

To the best of our knowledge, no existing work on deep GGen has looked into the potential privacy threats laid during the learning and generation with powerful models. Such concerns are rather urgent in the graph setting, where sensitive information can often be more easily compromised in a collective manner [Zhang et al., 2014], and privacy leakage can easily further propagate [Sun et al., 2018].

3 DPGGAN

In this work, we propose DPGGAN for securely generating graphs, whose global structures are similar to the original sensitive ones, 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 mechanismM satisfies (ε, δ)-edge-DP if for any two neighboring graphs G1, G2 ∈ G, which differ by at most one edge, Pr[M(G1) ∈ S] ≤ exp(ε) × Pr[M(G2) ∈ S] + δ, where S ⊂ range(M).

Our key insight is, a 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 a 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 rigorously protecting individual link privacy.

To ensure DP on individual links, we exploit the existing link reconstruction based graph generation model GVAE [Kipf and 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 crossentropy (BCE) loss on graph adjacency matrices in GVAE with a structure-oriented graph discriminator based on GCN and the framework of VAEGAN [Gu et al., 2019]. 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 and Welling, 2017], which is shown to be promising in calculating universal graph representations [Maron et al., 2019; Xu et al., 2019]. To guarantee individual link privacy without severely damaging global network structure, in this work, we harness the power and simplicity of GCN under the consideration of edge-DP by adapting the link reconstruction based graph variational autoencoder (GVAE) [Kipf and Welling, 2016] as our backbone graph generation model.

Notably, we are given a graph G = {V, E}, where V is the set of N nodes (vertices), and E is the set of M links (edges), which can be further modeled by a binary adjacency matrix A. As a common practice [Hamilton et al., 2017], we set the node features X simply as the one-hot node identity matrix. The autoencoder architecture of GVAE consists of a 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

where µ = gµ(X,A) is the matrix of mean vectors µi, and σ = gσ(X,A) is the matrix of standard deviation vectors σi. g·(X,A) = ˜AReLU( ˜AXW0)W1 is a two-layer GCN model. gµ and gσ share the first-layer parameters W0. ˜A=D- 12AD- 12 is the symmetrically normalized adjacency matrix of G, with degree matrix Dii = ∑Nj=1 Aij . gµ and gσ form the encoder network.

To generate a graph G′ , a reconstructed adjacency matrix A′ is computed from Z by an FNN decoder

where σ(z) = 1/(1 + e-z ), 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

where Lrec 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 Kullback-Leibler divergence towards the Gaussian prior p(Z) = ∏Ni=1 p(zi) = ∏Ni N(zi|0, I).

Enforcing DP. The probabilistic nature of Z allows the model to be generative, meaning that after training the model with an input graph G, we can detach and disregard the encoder, and then freely generate an unlimited amount of graphs G′ with similar links to G, by solely drawing random samples of Z from the prior distribution N(0, I) and computing A′ with the learned decoder network w.r.t. Eq. (3). However, as shown in [Kurakin et al., 2017], powerful neural network models like VAE can easily overfit training data, so directly releasing a trained GVAE model poses potential privacy threats.

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 Definition 2, the inequality guarantees that the distinguishability of any one edge in the graph will be restricted to the privacy leak level proportional to ε, quantifying the absolute value of privacy information possibly to be leaked by a graph generation model.

According to Eq. (3), GVAE essentially takes a 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 mechanismM, as long as 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, we leverage the Gaussian mechanism (Definition 1) [Dwork et al., 2014] and DPSGD [Abadi et al., 2016] to enforce edge-DP on it. In our setting, G is the original training graph. Then Eq. (1) tells us that a link reconstruction based graph generation model M can be randomized to ensure (ε, δ)-edge-DP with properly parameterized Gaussian noise. Prominently, we follow DPSGD [Abadi et al., 2016] to inject a designed Gaussian noise to the gradients of our decoder network clipped by a hyper-parameter C as follows

where L is the loss function of a link reconstruction based graph generation model, C is the clipping hyper-parameter for the model's original gradient to bound the influence of each link, and σ is the noise scale hyper-parameter.

Now we prove that the noised clipped gradient ˜ gθ,L applied as above guarantees the learned graph generation model to be edge-DP, with a different condition from that in Definition 1 due to the nature of graph generation.

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 c1 and c2 that for any ε < c1q2T , iteratively updating the model T times with ˜ gθ,L attains it with (ε, δ)-edge-DP for any δ > 0 if we choose

The proofs of Theorem 1 are detailed in Appendix A.

For the training of the DPGVAE decoder, L in Eq. (5) is specified as Lrec in Eq. (4). Due to the link reconstruction nature of DPGVAE, we derive the following Corollary.

Corollary 1.1 (DPGVAE edge-DP). Under the same conditions in Theorem 1, iteratively updating the decoder in DPGVAE for T times with ˜ gθ,Lrec attains it with (ε, δ)-edge-DP.

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 N(0, I). Due to the randomness of the normal Gaussian distribution, the sampling process can be regarded as (0, 0)-DP. By the composability property of DP [Dwork et al., 2014], generating graphs from random noises with the DPGVAE decoder satisfies (ε, δ)-edge-DP, 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 to induce minimum interruptions.

Improving structure learning. Besides individual link privacy, we also aim to preserve the global network structure

,

to 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 a 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 et al., 2019; Xu et al., 2019]. Therefore, we borrow the framework of VAEGAN and compute a structure-oriented generative adversarial network (GAN) loss as

where g′ and f ′ are GCN and FNN networks similar as defined before, besides at the end of g′ the node-level representations are summed up as the graph-level representation, which resembles the recently proposed GIN model for graph-level representation learning [Xu et al., 2019]. In this DPGGAN framework, the decoder also serves as the generator, while D = f ′ · g′ is the discriminator.

Following [Gu et al., 2019], the encoder is trained w.r.t. Lrec + λ1Lprior, the generator w.r.t. Lrec - λ2Lgan, and the discriminator w.r.t. λ2Lgan, where λ1 and λ2 are hyper-parameters. In practice, to apply DPSGD to our graph generation model, we consider various options for noise injection towards the appropriate DP constraints, such as adding noises to the GCN encoder, latent graph representation, FNN decoder, GCN discriminator or any of their combinations. With theoretical justification and empirical analysis, we find injecting a designed Gaussian noise to the clipped gradients of our decoder network sufficiently leads to edge-DP of generated graphs while best preserving the desired global graph structures. Therefore, Eq. (5) with Lrec substituted by Lrec - λ2Lgan is applied to distort the gradients of the decoder (generator) and guarantee edge-DP, which can be used to securely generate networks with the other parts disregarded after training. Furthermore, to achieve the best performance without losing the DP guarantee, we gradually reduce C in Eq. (5) for an adaptive perturbation.

The overall framework. The overall framework of DPGGAN is shown in Figure 2, and the training process is detailed in Algorithm 1.

In Figure 2, the original graph is fed into the GCN-based encoder network g to compute node embeddings, which is then compared with the prior distribution N(0, I) and fed into the FNN-based decoder/generator network f to produce the reconstructed graph and generated graph. After going through the GCN-based discriminator network part 1 (g′ ), a reconstruction loss is computed between the reconstructed graph and the original graph, and a discrimination loss is computed for the generated graph and original graph after the FNN-based discriminator network part 2 (f ′ ).

In Algorithm 1. For a better description, we shorten gθ,(Lrec-λ2Lgan) ( ˜ gθ,(Lrec-λ2Lgan) ) as gθ ( ˜ gθ ). In the algorithm, for proper gradient distortion, we devise gradient clipping and noise injection, which is only applied to the generator network f . We also gradually reduce the clipping

Algorithm 1 DPGGAN

Input: Graph data G(A,X), clipping parameter C, decay ratio γ, privacy budget ε, noise scale σ, total number of nodes N, batch size B = qN, learning rate η, maximum number of training epochs T , loss weighing parameters λ1 and λ2

Output: Differentially private decoder f .

Initialize weights randomly for gµ, gσ, f , g′ and f ′ .

for epoch t = 0 to T do

for iteration i = 0 to N/B do Sample a subgraph Gsub(Asub, Xsub) of size B Mean vector: µ ← gµ(Xsub, Asub) Standard deviation vector: σ ← gσ(Xsub, Asub) Update q(Z|X, A) ← ∏Ni=1 N (zi|µi, diag(σ2 i )) Sample zi, zj ∼ q(Z|X, A) Reconstruct adjacent matrix A′ ← σ(f (zi)T , f (zj )) Lprior = DKL(q(Z|X, A)‖p(Z)) Lgan = log(D(A)) + log(1 - D(A′ )) for node xi ∈ Gsub do Compute gθ(xi) ← ∂(Lrec - λ2Lgan)/∂xi end Clip gradient: ¯ gθ(xi) ← gθ(xi)/max(1, ‖gθ(xi)‖2 C ) Perturb gradient ˜ gθ ← 1B (∑i ¯ gθ(xi) +N(0, σ2C 2 I)) Average gradient: gθ ← 1B ∑i gθ(xi) Update f + ←- η · ˜ gθ; f ′ , g′ + ←- η · ∇g′ ·f ′λ2Lgan; Update gµ, gσ + ←- η · ∇g(Lrec + λ1Lprior) end Update C = C ∗ γ

end

hyper-parameter C as the volume of gradients decreases along training.

In the experimental analysis, existing works often fix δ as a dataset-specific value like 10-5 , and then analyze the performance of models based on fixed privacy budget ε [Abadi et al., 2016] or fixed noise scale σ [Papernot et al., 2018]. According to Theorem 1, our experiments are conducted with fixing the noise scale σ = 2q√T log(1/δ)/ε, where ε < 2 log 1 qσ q2T. In this work, other σ, to control the variance, we also fix δ, the sampling ratio q, 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.

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 a reconstruction loss Lrec = ‖g′ (A)-g′ (A′ )‖22 captures the intrinsic structural difference between G and G′ instead of the simple sum of the differences over their individual links. Note that the effectiveness of our structure-oriented 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 fulfills our 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].

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 as DPGVAE. Since we also do not release D after training, we can simply retrieve Corollary 1.2 from Theorem 1 as follows.

Corollary 1.2 (DPGGAN edge-DP). Under the same conditions in Theorem 1, iteratively updating the generator in DPGGAN for T times with ˜ gθ,(Lrec-λ2Lgan) attains it with (ε, δ)-edge-DP.

With Corollary 1.2, we attain DPGGAN with the same (ε, δ)-edge-DP protection of DPGVAE. For both DPGVAE and DPGGAN, the decoder/generator networks only get exposed to the noised and clipped gradients, representing the partial sensitive information within the training graphs. Hence, it prevents the inference of training graphs from both learned model parameters and generated graphs.

4 Experimental Evaluations

We conduct two sets of experiments to evaluate the effectiveness of DPGGAN in preserving global network structure and protecting individual link privacy. All code and data are in the Supplementary Materials accompanying 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, i.e., 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 facilitate a 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., 2018], with default hyper-parameter settings and no DP constraints.

For GVAE and our models, we use two-layer GCNs with sizes 32 → 16 for both gµ and gσ of the encoder network, where the first layer is shared. We use two-layer FNNs with sizes 16 → 32 for f of the decoder (generator) network. For DPGGAN, we use another two-layer GCN with the same sizes for g′ and a three-layer FNN with sizes 16 → 32 → 1 for f ′ . For DP-related hyper-parameters, we follow existing works [Abadi et al., 2016; Shokri and Shmatikov, 2015] to fix δ to 10-5 , σ to 5, and q to 0.01 (which determines the batch size B as B = qN with N as the graph size). Then we vary ε from 0.1 to 10 to see how much graph-level utilities are preserved under different privacy budgets. According to Eq. (6), we terminate the training of DPGGAN at T iterations when ε is depleted. Other than the essential hyper-parameters in Eq. (6), we empirically set the clipping hyper-parameter C to 5, decay ratio γ to 0.99, learning rate η to 10-3 , and the loss weighing hyper-parameters λ1 and λ2 both to 0.1. We do not observe the model to be very sensitive to the setting of these non-essential hyper-parameters.

All experiments are done with four GeForce GTX 1080 GPUs and a 12-core 2.2GHz CPU. The training time of DPenforced models is often slightly shorter due to early stops when the privacy budget runs out, (e.g., a typical train of GVAE, DPGVAE, 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 a 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, on DBLP). Although efficiency is not our primary concern, short runtimes (especially for generation) are favorable for efficient data share.

Preserving global structures. To show that DPGGAN effectively captures global network structures, we compare it and DPGVAE under different privacy budgets (controlled by ε in Eq. (6)), regarding a suite of graph statistics commonly used to evaluate the performance of graph generation models, especially from a global perspective [Bojchevski et al., 2018; You et al., 2018; Yang et al., 2019]. 1 In particular, we train all models from scratch to convergence on each graph in the datasets. Each time, the trained model is used to generate one graph, which is compared with the original one regarding the suite of graph statistics. Then we average the absolute differences between generated and original graphs, ensuring that the positive and negative differences do not cancel out.

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 are 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 graph classification, the most widely studied graph-level downstream task, to evaluate the global utilities of generated graphs. Particularly, we evaluate the accuracy of GIN [Xu et al., 2019], the state-of-the-art graph classification model, with the default hyper-parameter setting.

In Table 1, our DP-constrained models constantly yield highly competitive and even better results compared with the non-private baselines of NetGAN and GraphRNN regarding global graph structural similarity between generated and original networks on both datasets. As we gradually increase the privacy budget ε, our both models apparently perform better, showing the effectiveness of our privacy constraints and a clear trade-off between privacy and utility. DPGGAN consistently outperforms DPGVAE under the same privacy budgets, supporting our novel design of the GAN framework. Moreover, as shown 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. All these results demonstrate the global structure preservation ability of DPGGAN.

1 Statistics we use including LCC (size of the largest connected component), TC (triangle count), CPL (characteristic path length), GINI (gini index) and REDE (relative edge distribution entropy).

Protecting individual links. To show that DPGGAN effectively guarantees individual link privacy, we train models shown in Figure 3 for another K times on each dataset. Instead of complete networks, we 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 we evaluate the individual link prediction accuracy by comparing links predicted in the generated networks and links hidden during training in the original networks.

As shown in Figure 3, for both datasets, links predicted on the networks generated by DPGGAN models are much less accurate than those predicted on the original networks (13.0%-16.9% and 27.3%-28.6% accuracy drops on DBLP and IMDB, respectively) as well as the networks generated by most non-private models (11.1%-15% and 18.1%-19.5% accuracy drops compared with GGAN on DBLP and IMDB, respectively). 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 Appendix B.

5 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 provide a compelling system for secure graph generation through the appropriate integration of deep graph generation models and differential privacy. Comprehensive experiments show our model to be effective in both preserving global graph structure and protecting individual link privacy.