Neural Graph Generation from Graph Statistics
Authors: Kiarash Zahirnia
Yaochen Hu
Mark Coates
Oliver Schulte
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Generation
Local Differential Privacy
Graph Statistics
Latent Adjacency Matrix
TL;DR: This work highlights the potential of learning deep GGMs from aggregate graph statistics as a privacy-preserving alternative to traditional approaches that rely on sensitive graph data.

Abstract: We describe a new setting for learning a deep graph generative model (GGM) from aggregate graph statistics, rather than from the graph adjacency matrix. Matching the statistics of observed training graphs is the main approach for learning traditional GGMs (e.g, BTER, Chung-Lu, and  Erdos-Renyi models). Privacy researchers have proposed learning from graph statistics as a way to protect privacy. 
We develop an architecture for training a deep GGM  to match statistics while preserving local differential privacy guarantees. Empirical evaluation on 8 datasets indicates that our deep GGM model generates more realistic graphs than the traditional GGMs when both are learned from graph statistics only. We also benchmark our deep GGM trained on statistics only, against state-of-the-art deep GGM models that are trained on the entire adjacency matrix. The results show that graph statistics are often sufficient to build a competitive deep GGM that generates realistic graphs while protecting local privacy.

Neural Graph Generation from Graph Statistics
Kiarash Zahirnia', Yaochen Hu², Mark Coates Oliver Schulte Simon Fraser University, HHuawei Noah's s Ark Lab, McGGill University kzahirni@sfu.co ca, yaochen... hu@huawei. com, mark. coates@mcgill. ca, oschulte@sfu.ca ca.
Abstract
We describe new setting for learning deep graph generative model (GGM) from aggregate graph statistics, rather than from the graph adjacency matrix. Matching the statistics of observed training graphs is the main approach for learning traditional GGMs (e.g, BTER, Chung-Lu, and Erdos-Rent Renyi models). Privacy researchers have proposed learning from graph statisties We develop an architecture for training a deep GGM to match statistics while preserving local differential privacy guarantees. Empirical evaluation on 8 datasets indicates that our deep GGM generates more realistic graphs than the traditional non-neural GGMs when both are learned from graph statistics only. We also compare our deep GGM trained on statistics only, to state-of -ffthe-art deep GGMs that trained on the entire adjacency matrix. The results show that graph statistics are often sufficient to build competitive deep GGM that generates realistic graphs while protecting local privacy.
way to protect privacy.
Introduction
Graph generative models (GGMs) have produced many insights into fundamental processes in domains including biology, engineering, and social sciences. Current deep GGMs are based on training data with complete adjacency matrices 66. new deep GGM architecture for setting where the available graph data are summarized by graph statistics, not a complete adjacency matrix. We refer this setting as statistics-but Previous work in network analysis has introduced several parametric non-neural models that support statistics- based graph generation, such as the Chung-Lu model [5), and the BTER model [67]. The parametric models tend to generate less realistic graphs due to lack of expressive power.
This paper presents GenStat,
graph generation.
Our main motivation for generating graphs from statistics is privacy preservation. There is a direct ten- sion between releasing real graphs to the research community and privacy concerns of the individual entities (graph nodes) [63 85). A promising proposal to address it is to release synthetic graphs that preserve the original graph properties while guaranteeing user-specified level of privacy 20 41).
Benchmarking Graph Neural Networks (GNNs) is use-case of GGMs with a privacy guarantee. Synthetic graphs generated by GGMs enable GNN research without information leakage [87].
Statistics-bart based graph generation supports the challenging use case of decentralized graphs [86].
where privacy concerns rule out collecting adjacency matrices in a central repository. Common examples are social graphs [58], e.g., users' connections through their phone contact lists, face-to- face interactions, sexual and friendship networks, or distributed social networks, e.g., Mastodon [58] A solution is have each entity perturb its data and send the perturbed data a curator [86]. However, collecting raw data locally, such as an entity's 's neighbour list, requires heavy noise injection to satisfy privacy, and may result in a dense, distorted graph with low utility. An alternative, used widely in industry including Google, Apple, and Microsoft [9 71 78), is to collect, from each entity's s ego-graph, local node-level graph statistics (2h)/) with a guarantee of Local Differential
"Supported by NSERC Canada Discovery Grant R61 1341
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Privacy (LDP) as strong privacy measure 158 The perturbed node-level statistics are aggregated
summarize important graph properties [58 86 The idea that coarser- coarser-grained information
requires much less noise to satisfy LDP
58 The final step is to generate representative synthetic
graphs for public release. Previous works use parametric statistics-base baased GGM [3
35
48
58
Our GenStat system is a neural alternative that generates substantially more realistic graphs. Figure summarizes the privacy-rreeervin workflow.
Node dogreg.... Perturbation
Perturbed Degree
Triangle Numberr
Perturbation 11.
Perturbed Thiaitgle Number
Aggregated Graph
Mechanism M
Synthetic Graphs
g'
Data Collector
Histogram
(Statistics bebstics---sedddd
GenStat
g
GGM)
Trinnlle Histogram
g
Persuttation Perturnation Mechanism M
Figure 1: Generating realistic-lookin graphs with Local Differential Privacy, See text for detail.
Evaluation. We evaluate the realism of the generated graph structures following previous work [6 41 58 68 72 88). Experiments 8 datasets with diverse characteristics demonstrate the effectiveness of GenStat. Compared to parametric statistics-based methods, GenStal generates graphs that are up to 10 times more realistic on Maximum Mean Discrepancy (MMD) metries. Compared state-of-the. art GGMs (that require access to all adjacencies), the GenStal graphs reach very competitive graph quality, especially on real graph datasets, such datasets of molecules and chemical compounds. Thus in many domains, graph statistics are sufficient for learning to generate realistic graphs. We also evaluate the effectiveness of GenStat for benchmarking GNNs on link prediction as a downstream task and we show GenStal is highly effective. Moreover, graph learning from statistics is much faster than from adjacency matrices. The implementation and datasets are provided GenStar repository ht https://gt gig.gttthbb...o com/ http:/iiaaaaaaaaaaaaa Saw.sshhaaaGenntat... GenStat, git and explained in the Appendix Section 7.9
Contributions.
We introduce GenStat, novel deep graph generative architecture that requires access only to graph-level statistics. To our knowledge, GenStat the first deep GGM that does not require observations of individual nodes edges.
We show that given training statistics collected with local differential privacy guarantee, Gen- Stat also satisfies local differential privacy, while generating high-quality graphs.
We identify permutation-invariat differentiable graph statistics that are based on aggregating node-level information and support realistic graph generation across multiple diverse domains.
2
Related work
Realistic graph generation has been studied extensively for decades, leading to the development of both parametric and neural approaches [24 Figure the Appendix positions GenStar in
the GGM landscape. The objective of previous parametric statistics-based GGMs such as [ 5 18
21
40 56
is to generate graphs with similar statistical properties to observed graphs [46] The
expressive power of their parameter space is limited. More recent machine learning models, including
Deep GGMs 66 88 89]. have higher capacity to generate realistic graphs [6]. However, to our knowledge, they all assume access complete adjacency matrix. Such access incompatible with privacy concerns since adjacency matrices reveal the entities with which an entity has interacted. In contrast, GenStar learns deep GGM using only observed graph statistics and generates realistic graphs for a variety of domains.
Graph statistics. Zahirnia et al. 89 recently introduced joint probabilistic micro-macro macro model over both adjacencies and graph statistics and showed that matching graph-level statistics an effective regularizer for the edge reconstruction loss, which assumes access to all adjacencies. GenStal operates on permutation-invante the statistics used in [89] require all adjacencies.
graph statistics that can be collected locally and privately, whereas some of

---

Statistical databases are database systems that present only aggregate statistics (e.g., sample mean and count) for a subset of the entities represented in the database and ensure that sensitive information is safeguarded while still enabling valuable statistical analysis and research. An example is the database maintained by the U.S. Census Bureau [39]. Statistical databases also protect privacy through aggregate statistics and can be analyzed using the GenStar framework.
Permutation-ine
-nvariance inmautation-nvvaiinneee a GGM should produce the same output irrespective of the node ordering employed in the training set.
is fundamental property of graph-struuttured data (24), which suggests that
is satisfied by many GGMs [23 28 33 54 76 but not all 6 88 89 .. Since GenStar takes as input
permutation-inee invarriannnnnn statistics, its training and the generative graph distribution are permutation-
invariant as well (Section (.3)
Differential privacy (DP) 15 enables the extraction of useful information about a population while providing strong privacy guarantees for individuals. Local differential privacy (L.DP) 36 is stronger guarantee for the decentralized setting [86]. Each entity perturbs its sensitive information before transmitting it to an untrusted curator. Collecting decentralized network statisties under LDP has been deployed by major technology companies, including Google, Apple, and Microsoft [T]
For example, Google's RAPPOR [19] collects randomized statistics to enable analysis of popular web destinations without revealing individual browsing habits.
Graphs and privacy. Privacy-press preserving techniques have been proposed for the release and genera- tion of graph data [4]
63). Yang et al. [85] and Yoon et al. [87 leverage DP to enforce privacy constraints deep GGMs. Yoon al. (87) advocate using generated graphs replace original graphs in GNN research. Therefore the GGM should generate effective benchmark graphs, meaning that GNNs show similar task performance as on the original source graphs. In the decentralized setting, entities perturb sensitive information locally to support the generation and release of synthetic graphs (58 78 86 91] Theoretical analysis shows that perturbing local adjacencies impairs graph quality too much for synthetic graphs to be useful (58). Our experiments confirm this for SOTA deep GGMs (Section 4.3). Therefore, recent studies train parametric GGMs with perturbed local ego-graph statistics 758 to achieve LDP. To our knowledge, GenStat is the first deep GGM that can generate synthetic graphs under LDP.
Graph Anonymization is procedure that disguises or modifies information in graphs, making it anonymous. Anonymization techniques have two main limitations (50 63) These techniques 1) are mainly applicable in a centralized setting and 2) typically protect only against specific known attacks. Narayanan and Shmatikov [51] describe de-anonymization algorithm for an anonymized binary adjacency matrix that effectively re-identifies the nodes in real word graphs, Twitter and Flicker.
Federated Learning is a crivacy-preserving paradigm for building models from separate data sources 190. 20 25 80) used federated learning to learn GNNs on graphs from multiple data sources. These studies assume that each source has trusted access to sufficiently large subgraph to locally train an accurate GNN 80), and they do not target the construction of a GGM.
3 Problem definition and method
Given a set of observed graphs G = (Gt,..., gS), with variable number of nodes, sampled from data distribution p(G'), the goal of GGMs is to learn model that generate similar synthetic We introduce GenStar, a statistics-basee architecture for probabilistic GGMs.
graphs 66 88 89
GenStat assumes that a training graph G is summarized by set of observed M graph statistics, denoted as I {I,m J where the statistic Im is a vector of dimension Dm- Each statistic is computed by a descriptor function @m 1]nn + R++D... that maps an adjacency matrix representing graph with n nodes to vector; we write 6m (A') Iín and (A') = I', Permutation- invariant statistics satisfy (A') = (A',) for all adjacency matrices obtained from A' through a permutation и 10 52 Ch. 7]. Section defines the statistics in our experiments, namely histograms of triangles, neighborhood sizes, random walks and graph size.
3.1 Probabilistic model of graph statistics
Given a distribution (AA) over adjacency matrices, we let I denote the random variable defined by applying the descriptor functions to a random graph A (i.c., I = (Øm [A) Following Ma et al.
3

---

45,, we view the latent adjacency matrix A as sample from an underlying probabilistic adjaceney
matrix A with uu, [0. 1] specifying independent link probabilities. We define the mixture model
P(A[A)= = p(A) = / p(A)))((A) dĀ p(A) p(A|Z)p(Z)dZ,
(1 Au,o) --Au.
(1)
where Zixd is a graph latent representation [Scc 9.1] with associated prior p(Z). The marginal distribution over graph statistics is:
/ (o dA dZ.
Pe (I)
We assume graph statistics are independent given the probabilistic matrix Á and model the conditional distribution each graph statistic as a Gaussian with diagonal variance parameter of
pe (I Im A) II m=1
Om (A)
(3)
Given the conditional distribution Equation the marginal distribution Equation is mixture of Gaussians. Figure 2a illustrates the probabilistic graphical model of GenStar.
Im
Pmm(X
Im
Å
Latent variable
IM
Deterministic function
Z
Trainable function
q(Zl21- TM)
P(A[Z)
p(11 MMA)
(6)
(b)
Figure 2: (a) The proposed latent variable model. The diagram shows the dependency of graph statistics {I LM on the latent probabilistic adjacency A and graph-level latent representation Z. (b) The model's overall architecture.
3.2 Training and variational lower bound
the marginal log-likelihood is the sum of the marginal ligelikels of the individual graphs, log Po P I =, log (I')) The double integral in Equation (2) is generally intractable. We approximate the mixture integral with Variational Auto-Encoder (VAE) to minimize the negative ELBO an approximation of the negative log- ligeliidld for graph statistics:
For an i.i.d. sample of graphs with associated statistics, I'....,T* .
Proposition Let po be the marginal likelihood defined in Equation
2 Then
- In (I)) = -I, I&r SE n0
go (Z .... Thy) In (I) DI......,,,,A))) (A (A)
KL (.b)l,,,,,)))(()))
The proof is in the Appendix Section estimate of the expectation of po (Ii..... TM Á) w.r.t. (A as follows:
7.I.I We approximate the inner integral with a Monte Carlo
/ pa (T) I you (
Z)dA E Po á 2 (po (I) ..... Ih (A)]
T
Σ
Pa [I)
".....,I,,AA'' where A' ~ po(()) (5)
T
t=1

---

where the conditional distribution of the underlying probabilistic adjacency matrix can be modelled as Beta distribution 44
We implement the GenStat objective 4 with an Auto-Encoder in which fully connected neural networks (FCNNs) are used to jointly learn qa Z ........ Iha)
and py (a Z) with learning parameters Figure 2b illustrates the VAE design of GenStat. The prior p(Z) is standard normal distribution. The variational posterior go (Z
2,p) is a factored Gaussian with vector mean and variance. See Appendix Section 7.2 for the neural network design and more details concerning implementation.
3.3 Permutation-invariant graph generation
Given permutation- iommutation-invaiiant statistics, GenStar training permutation-invarre in the sense that the gradient updates are model distribution (A(A) from Equation [ can be made cormuttttioninvariinn by applying a uniform random permutation to the output of the decoder. In addition to generating synthetic graphs, major use of Mtaiiticss-bsse generative models is to define an inference distribution to support prediction tasks like link prediction and graph classification [60]. These inference models apply to graph distributions that assign the same probability to graphs with the same statisties, which is appropriate when the graph model is based statistics only. Accordingly, we define the following cormuutationinvariian inference distribution for a GenStat model:
[76]. Because training is permutation -nttaaiiionivviaannt,, the
(A) = Pa( (A))/Ca((A))
(6)
where the distribution pe (I) over statistics follows Equation 2 and C*((A) is the number of graphs that generate the same statistics as (i.e., C*(a) ((A' (AA) = (A)))..
The following statement summarizes these observations. Appendix Section 7.1.2 provides a proof.
Observation 1. Suppose that GGM parameterized by 0 is trained with the GenStat architecture and cormmutation-iivariann descriptor functions b. Then the following hold.
1. The gradient updates of given training graph A are permutation-invarite
iinaaratin-invaiiann 2. The model distribution Po(A) ) is permutation invariant if the generated adjacency matrix is computed by applying a random permutation to the GenStat output.
3. The inference distribution Po (A) in Equation permutation-imaarian
3.4 GenStat privacy analysis
This section shows that training the GenStat architecture on statisties collected under an LDP guarantee, also satisfies LDP. We employ graph LDP concept known as Edge LDP [58] (78.. which guarantees plausible deniability for the inclusion or removal of a particular edge associated with an individual (node). The neighbor list of u is an n-dimensional vector l, = - lun), with lwv (0, 1} and Luo iff u and v are connected.
Definition 1 (c-Edge LDP). A randomized algorithm R satisfies e-Edge LDP if and only if for any two neighbour lists I and 1, such that I and l' only differ in one bit, and for any output value s E range( the following inequality holds.
p(R(I) =)
An example of a randomized algorithm R is a perturbed node degree: A user calculates her true node degree, adds noise with perturbation mechanism (e.g., the Laplace mechanism (I3), and sends the resulting noisy degree to a data curator. The curator aggregates the perturbed node degrees as local graph statisties that can be used train statistics-bass GGMs, such as GenStat. The following proposition, with proof in Appendix Section 7.1.3] captures the LDP-preserving properties of GenStat.
Proposition Let R (R)...Ms)) be a set of independent randomized algorithms, outputting perturbed node-level statistics, such that algorithm Rm satisfies cm -Edge LDP. Then a GenStat GGM trained on the outputs of R satisfies MM Cm cm- Edge LDP.
5

---

3.5 Observed graph statistics
Graph statistics used a GenStat model are computed by permutation invarrian descriptor functions (A)) that can be applied to probabilistic as well as binary adjacency matrices, and are differentiable with respect to entries in the latent adjacency matrix A. To support local privacy, we use graph statistics that aggregate node-level statistics:
F(G) AGG(()(GL)
(1.2....,,h)
where Gu denotes the node k-hop ego network of node in graph 9 with n nodes, the local statistic f-)) returns a real-valued vector for an ego-graph, and AGG(-) is permutation invariant function (e.g., average, sum, histogram) that takes as input the set of statistics (e.g.. node degree) of the ego-graphs and summarizes them into vector representation. When A represents the graph G, we have that (AA) = F(g) is differentiable if the f()) and AGG(.) functions are differentiable.
The representation of graphs based on local ego-graph properties has been widely studied [22 64
79 83
Recent studies proposed algorithms for estimating k-hop-based graph structural properties
78 [1. Our experiments use three histogram-based k-hop graph statisties: 1) triangle histogram: 2) H-HOP neighbors histogram; 3) histogram of random walks, and graph size. We use a differentiable soft histogram [77]; see Section 7.3 The histogram function h(-) transforms a vector of counts into a real-valued soft histogram. We explain each graph statistic next.
under (L)DP 7 29 30
61
66
Triangle histogram. A triangle histogram counts the number of nodes that participate in given number of triangles. The descriptor function h (A ",,u).
k-HOP neighbors histogram for k = 1, 2, 3, 4. The k-HOP neighbor histogram counts the number of nodes that have given number of k-HOP neighbors. The 1-HOP neighbour histogram is equivalent to the degree histogram. The k- k-Hop descriptor function min(A, 1,,e, min(A u. 1) and (A) = -.. Au,
h (min Ex A 1)) where
Random walk histogram of length r for r 2. The number of walks of length between node and v is given by (A")... The random walk histogram of length r counts the number of node pairs with given number of walks of length connecting them. It is defined by l(AA) 655
Graph size. The size of a graph is its number of edges given by En En. Au,a.
This paper uses these four statistics in the experiments as default statistics and demonstrates that the default statistics are capable of modelling graphs with wide range of structural characteristies; see Section 4 The default statistics are known from prior research to be generally important for graph modelling across different domains and are easy to interpret (24. Different graph statistics are important for different applications [55] The default statistics can be combined with other statistics of interest in specific application.
4 Empirical evaluation
This section compares GenStat with parametric and Deep GGMs. Our design closely follows previous studies on generating realistic graphs 6
We report qualitative and quantitative evaluations of the generated graphs' quality. 1) We compare the performance of GenStar with popular statistics- based GGMs. 2) We compare GenStar with popular deep GGMs. These models require access to all node interactions, so this is not apple-to-appler comparison. It measures how much graph generation quality is lost when generation based on aggregated local statistics, rather than node interactions. 3) We compare GGMs trained under different Edge LDP budgets. 4) We compare GGMs in terms of their benchmark effectiveness for GNNs on link prediction as a downstream task. 5) We also compare deep GGMs and GenStat in terms of generation and training time.
88 89
Comparison methods. We compare GenStat to -tatsstcc-bbssed and deep adjacency- Statistics-batt based baselines. Statistics- -ased GGMs that have been used with LDP guarantees [78 include the Chung-Lo Model [5] and the Block Two-Level Erdos-Renys Renyi Model (BTER) (67]. We also evaluate the Stochastic Block Model (SBM) [ and the Erdos- Renyi model [18], which have
GGMs.
been employed in previous comparisons with deep GGMs details.
88
See Appendix Section 7.4 for further
Deep udjacency-bun baselines include VAF 89, BiGG 6, GRAN 43 and GraphRNN
88 To our knowledge, these are the SOTA models for generating realistic graphs.

---

Datasets. Following previous studies, we use real and synthetic datasets 6 88 89 As the datasets are not new, we describe them briefly. We evaluate our model on 3 synthetic datasets: the Lobster
trees (obsster), Grid [8]] and Triangle-Grid [89] datasets, all of which consist of graphs with regular
structures. We also evaluate our models on real datasets: oghg-molbbbp (oghg-mol) [27], Protein
[12. IMDb [84). PTC [73 and MUTAG [8] We randomly partitioned the datasets into train (70%),
validation (10%). and test (20%) sets 6 88 89 See Appendix Section 77. for detail.
Evaluating the generated graphs. Evaluating the sample quality of GGMs requires a comparison between two sets of graphs - the generated graphs and the (held-out) test sets 6 88 89 Qualitative evaluation compares the generated graphs by visual inspection.
Quantitative approaches compare the distance between the distribution of test graphs and the gen- erated graphs. We use GNN-based [68] 72] and setiistics-based [88] metrics to measure the fidelity (realism) and the diversity of generated graphs. GNN-based metrics extract graph representations with reference GNN that is independent of graph statistics. The reference GNN is either randomly initialized (Random- GN 72 or contrastively trained Sreerained-GNNY G8 Evaluation metrics then compute the discrepancy between the test set representations and the generated set represen- tations; we report F1 PR and MMD RBF. Statistic- evaluation metrics compute the MMD between the test set and generated set with respect to structural properties (orbit counts, degree coefficients, clustering coefficients and diameter) 43 For all GNN-based metrics, we used 10 GNNs with different random initializations and reported mean + standard deviation across different GNNs 772). Following O' Bray et al. [55] we report scores computed from a 50/50 split of the data sets as the ideal score. As in previous work, all models are trained with one random weight initialization to keep the training time feasible 66 42
89 Each trained model is used to generate S new graphs to compare them with the S graphs in the test set. See Appendix Section 7.6 for further detail.
4.1 Comparison of GenStat with statistics-based GGMs on graph realism.
We compare GenStat to non non-neural baseline models that are widely used in network science. Qualitative evaluation. Figure 3 is a visual comparison of randomly selected test and generated graphs graphs for statistics- based GGMs. The GenStar graphs are visually much more similar to the test samples than the baseline graphs. For example, instead of Lobster trees, baselines often generate samples that contain multiple cycles. IMDb graphs exhibit a community structure where multiple small communities are interconnected through central node. For instance, the left IMDb test sample in Figure consists of six communities. None of the baselines was able to generate a graph with high modularity. The Protein samples generated by the baselines exhibit higher density compared the test samples. The GenStal repository contains the complete collection of generated graphs.
Quantitative evaluation. The quantitative evaluation confirms that the quality of graphs generated by GenStat is substantially higher. Table reports the GNN-based MMD RBF scores. GenStat achieved better MMD RBF scores than the baseline GGMs in 12 out of 16 cases. Notably, GenStat generated samples have MMD RBF scores up to ten times smaller than the baselines for the Random-Git F1 PR. The F1 PR of
and Pretrained- GNNN approaches. Appendix Table reports reports the generated graphs by GenStat is substantially higher than those of the baselines. For example, on Protein, the GenStat F1 PR score is 83.72% vs. 71.08% for the next best method with Random- GNN, and 79.95% vs. 23.76% for Pretrained-GNN, Appendix Table 4 shows the results for the statisticx-based evaluation metrics. GenStal generates graphs with up 1-2 orders of magnitude better statistics-baset MMDs, at least in one of the reported MMDs, on almost all datasets.
4.2 Comparison of GenStat with deep adjacency- based GGMs on graph realism
Qualitative evaluation. Appendix Figure 7 provides visual comparison of the graphs generated by GenStat and deep SOTA adjacency- based GGMs. On the real-world datasets, the GRAN graphs are less realistic than the GenStat graphs. For the other comparison methods, the quality of their graphs is visually indistinguishable from those generated by GenStat.
Quantitative evaluation. Table Table@]compan compares GenStat with adjacency- based GGMs in terms of the GGN- based MMD RBF score of the generated graphs. Although GenStal limited to graph statistics, for real- world datasets, it ranks among the top two models in 9 out of 10 reported MMD RBF scores. On the synthetic datasets the GenStal scores are competitive with the GraphRNN and GRAN scores but do not reach the level of BiGG and GraphVAE-MM The difference is that the synthetic datasets
7

---

Test
GenStar
BTER
ChangeLa
SBM
Erdos-Rany' Ranyi
(a) ogbg-mol
(b) Protein
(c) IMDb
(d) Lobster
Figure 3: Visualization of generated graphs by the statistics-bused GGMs. The top row shows
randomly selected graphs from the test set for each dataset, with varying structural characteristics. The other rows show graphs generated by each model. The generated graphs shown are the two visually most similar samples in the generated set.
Table 1: Comparison of GenStat with statistics-base GGMs for the GNN-Based MMD RBF score (lower better). The best result in bold and the second best is underlined.
Dataset
Descriptor
50/50 splat
GenStar*
BTER
Chung- Lu
Erdos Roni
SBM
ogbg-moo
Ruadom GNN
Pretminsd-GGNN
0.00 0.00
0.00
0.05
0.01
0.01
0.21 0.12
0.00
0.05 0.00
0.000
0.22 0.02
0.12 0.07
0.10 0.03
0.21 0.00
Rindom-GNN
0.54
0.59 0.36
0.13
GNN
0.01 0.00
0.00 0.00
0.21 2: 0.04
0.80 2 0.16
0.59 = 0.07
0.50 2: 0.04
IMDb
Random GNN
WeNN
0,00 0.00
0.01 +0000
0.08
0.05
0.02
0.03
0.20
0.07
1: 0.15
0.02
0.23 0.155
0.27 2 0.07
0.16 2: 0.14
0.16 + 0.06
0.12 1: 0.03
0.20 + 0.00
PTC
Preemined-Coi GNN
Ruadom- GNN
0.00
0.06
0.00
0.09
0.17
0.04
0.04
MUTAG
GNN
RINNom-GGNN
0.01 0.00
0.00
0.00
0.05
0.18 + 0.002
0.26
0.05
0.27
0.22 0.03
0.37 0.21
0.41 1:11=:00 0.00
0.35 + 0.06
0.27 0.16
Lobster
Pretrained GNN
Rondom-GGNN
0.03 +-0.0
0..00
0.35
0.10
0,03
0..1 0.01
0.15 + 0.04
0.11
0.14 : 0.02
0.32 0.03
0.44 4 0.10
0.27 0.03
0.22 0.08
Grid
GNN
0.36
Petminal--NNN
0.000
1.17 0.10
T,21 + 13
1.50 0.00
1,21 0.13
1.25 0.09
Triangle Grid
Pretrained-UN CNN
Random-GiNN
0.03 0.00
0.00 +0.00
0,33
11
1 0.13
0J07
0.18
0,80 1 0.17
+ 0.20
1.30 1 0.14
1.18 + 0.20
1.10 + 0.27
1.20 1 0.12
D.78 0.34
1.20 1 0.11
exhibit highly regular local structure (e.g., a grid pattern). We observed similar results for the Fl and statistics-base scores (Appendix Tables andd Apparently the global graph statistics used by GenStat are insufficient for expressing strict local constraints.
In sum, our deep statistics-based based GGM GenStat outperforms previous parametric statistics-based GGMs by orders of magnitude. In an apples-to-oranges comparison with deep GGMs trained on complete adjacency matrices, it is competitive or superior on real-worid datasets, but not on synthetic datasets with highly regular local structures such as grid patterns.
4.3 Graph realism and edge local differential privacy
We examine training both Matistics-based and adjacency-based GGMs with an Edge LDP guarantee. For adjacency-based GGMs, the randomized neighbour list (RNL) approach (58) can be used. Each node randomly flips each bit in its neighbour list with probability TtP and sends the perturbed neighbour list to the untrusted curator. A adjacency-based GGM can then be trained on the collected perturbed adjacency matrix. For e-Edge LDP guarantee, GenStat was trained local ego-graph (node-level) statistics, each perturbed by the Laplace mechanism with variance (Me)² 14]

---

Table 2: Comparison of GenStat with adjacency-based GGMs for the ENN--Based MMD RBF score (lower is better). The best result is in bold and the second best is underlined.
Dataset
Descriptor
50/50 split
GenStar
GraMhVAE-MM
BIGG
GRAN
GraphRNN-S
GraphRNN
ogbg-mol
Random GNN
0.00 2: 0.00
0.05 1: 0.01
0.01 1: 0.00
0.04 4: 0.00
0.44 0.02
0.44 1 0.15
1.53 a: 0.33
Premmined.
0.00 + 0.00
0.01 0.01
8:04 0.000
0.03 + 0.00
0.25 = 00.33
0.54 0.04
0.86 0.09
Protein
Random- GNN
Peetrained-GGNN
0.01 + 0.00
0.00
0.00 + 0.00
0.00 0.01
0.17 + 0.01
0.06 0.01
0.17 0.07
0.11 + 1.00
0.11 0.022
0.05 0.00
0.97 + 0.06
0.18
1.73 + 0.21
IMDb
Random-GNN
0.00 + 0.00
0.05 + 0.03
0 + 0.02
0 + 0.00
11002 = 0.00
1.45 0.03
0.98 0.06
0.03
0,03 0.00
0.42 0.27
0.23
0.12
PTC
Random-GGNN
PedN 0.02 1: 0.00
D.0 0.00
0.00 0.00
0.00 11.00
0.06 1: 0.00
BA03 D1000
0.05 + 0.00
D.03 0.00
0.18 = 0.03
0.14 0.03
0.53 0:03
0:11
0.51 0.11
0.81
MUTAG
Random GNN 0.00 4: 0.00
Pretrained-GNN GNN
0.01
0.05 0.05
0.00
0.09 1: 0.04
0.03
0.09 0.01
0.03 1: 0.00
0.09 = 0.00
0.10 0.01
0.53 4 0.12
0.31
LO8 0.05
Lobster
Rindom-GNN
00.03 2: 0.00
0.35 0.10
0.09 E 0.00
0.11 4 0.00
0.16 6.07
0.36 0.08
0.62 0.05
Prettinned-GGN
0.30 +: 0.00
0.04 + 10/03
0,10 D.00
0.11 +: DA0I
0.29 = 0.03
0.74 D.07
0.22 + 0.01
Grid
Randou-GNN
0.02
0.53
0.35
0,40
0.92
PrtNainnd-GGNN
0.10 0.00
1.17 0.10
0.35 + 0.14
0.29 +: 0.30
0.45 = 0.09
1.27 0.07
1.06 0.0
Triangle Grid
Random: GNN
0,00 4: 0.00
0.33 0.07
0,18 1 0.00
0.38 1: 0.10
0.31 = 0.18
0.79 1 0.14
0.94 1 0.08
Pretrained-GNI GNN
0.03 0.00
1.11 : 0.13
0,15 1 0.02
0.31 1: 0.07
0.12 = 0.27
0.88 0.16
0.96 0.10
We compare the quality of graphs generated by GenStat and BiGG, the best adjacency GGM, against ground-truth test graphs, when each is trained under differential privacy. We also compare perturbed adjacency matrices with the test graphs. This helps us understand the optimal score that can be achieved by an adjacency-based GGM trained on the perturbed adjacency matrices. Graph statistics used in the GenStat model for this experiment are triangle histogram and degree histogram. Figure 4 compares the quality scores under the edge c-LDP guarantee, for E {0.1, 0.5, 1, 3, 4], using the three datasets on which BiGG showed the biggest advantage over GenStat when trained without perturbations (Section 4.2g; see the Appendix for other datasets. GenStat generates more realistic graphs for almost all 6-privacy budgets, as indicated by much lower MMD-RBF scores.
1.0
Gonštat
1.0
Ganštat
1.0
Perturbed Neighbour
Perturbed Neighbour
BIGG
0.8
BIGG
MMD RBF
Genštat Perturbed Neighbour
0.6
0.6
0.6
MMD
MMD
0.4
BIGG
0.2
0.2
0.2
Privacy Budget E
Privacy Budget e
Privacy Budget e
(a) MUSAA
(b) Lobster
(c) Gri
Figure 4: Comparison of GenStat (statistics-based GGM) with BiGG (adjacency-based GGM) under E-Edge LDP guarantee, in terms of the Random GNN-Based MMD RBF score. A lower score is better The lower bound e = 0 ensures perfect privacy.
4.4 Benchmark effectiveness
A use case for statistics- based GGMs is generating crivacy-controlled synthetic graphs for bench- marking the performance of GNNs on downstream tasks, when privacy concerns limit access to the original adjacency matrices in a data collector. The idea behind benchmark effectiveness is that "performance rankings among m GNN models on generated graphs should be similar to the rankings among the same m GNN models on the original graphs" [87]- The methodology is to evaluate each GNN model on the downstream task twice: first on the original dataset, and second on synthetic dataset generated by the GGM. The benchmark effectiveness of the GGM is then measured by the correlation between the GNNs' task scores from the original and the task scores from the synthetic data. Following (87, we benchmark GNNs on link prediction; see Section 778 for further detail. Table T compares the benchmark effectiveness of GenStar with that of BiGG, the SOTA adjacency-bul -ased GGM. On 4 out of 8 datasets, the GenStar benchmark effectiveness is competitive with or superior to the benchmark effectiveness of BiGG. For the other datasets, the benchmark effectiveness of BiGG is better, but the GenStut graphs still show substantive correlation (at least 0.5046 for Pearson correlation). For most of the datasets, the MSE of GenStal is smaller than that of BiGG. In our opinion, the benchmark effectiveness of GenStat for link prediction is impressive,

---

especially considering that the model does not observe specific links during training time, unlike BiGG.
4.5 Generation and training time
Evaluating the edge reconstruction probability is expensive and tends to dominate the training time of adjacency-based GGMs. Training statistics-based methods is therefore generally faster than training adjacency-bed based methods. Specifically, the training time of GenStat is up to two orders of magnitude lower than that of the fastest regressegees model, and up to 5 times lower than that of Graph VAE-MM. In terms of generation time, both VAE-MM and GenStat are much faster than auto-regressive methods, because they generate graphs all-at-on an-once rather than incrementally. Tables 2 and 10 in the Appendix give detailed comparison of the train and generation time of deep GGMs.
5
Discussion and limitations
Graph generative models have a potential attack surface that reveals sensitive information about individuals. Our model contributes to effective analysis of network structure while maintaining privacy guarantees and minimizing access to the sensitive information of individuals. We expect the social impact of our work to be positive. We discuss the limitations of the GenStar +VAE design.
Attributed and heterogeneous graphs. Following 6 g8 89], the reported research studies graph generation issues with relatively simple homogeneous graphs. GenStal can be extended to at- triuutedhhteroggeneou graphs, where nodes/edges possess attributes, including potentially sensitive ones. The graph descriptors can be defined as functions of both feature matrices and edge tensors.
Computational complexity. In our implementation, we used matrix multiplication with ((N3) complexity to exactly compute the descriptors (-)). Approximating graph statistics [16] 32 55 and exploiting the sparsity of real-word graphs are promising avenues for scaling large graphs.
Neural network design. Following 770 89 we used FCNN decoders to generate probabilistic
adjacency matrices. The all-at-once parallel edge generation of FCNN decoders enables fast training and generation time [24] Ch.9.1.2). However, they require specifying a maximum number of nodes, and do not scale to large graphs. These limitations in our current system can be addressed with more scalable decoders, e.g. graph transformers 76
6 Conclusion and future work
caatistics-based graph generative model (GGM) is trained on graph statistics that summarize the graph, rather than a complete adjacency matrix. Non-neural parametric models for ritiistics-based graph generation have been developed in network science for decades. We have described new GenStal framework, which to our knowledge is the first deep GGM architecture based on statistics. Our main motivation for matistics-based graph generation is to avoid requiring sensitive information from individual network participants, especially in the decentralized setting without single trusted data curator. We show that local node-level statistics are collected from individuals under edge local differential privacy (LDP), applying GenStat to the statistics preserves LDP. In empirical evaluation on eight datasets, graphs generated by GenStat were substantially more realistic than those generated by previous statistics-bart based methods (e.g., by an order of magnitude quality metric). On real-world datasets, GenStat graphs show competitive quality to SOTA GGMs that are based the entire adjacency matrix, even though GenStat sees only summary statisties. We also show that because GenStal learns on compressed graph information, training time is much faster than with adjacency-base methods.
the standard MMD RBF
valuable direction for future work is extending statistics-based graph generation to attributed and heterogeneous graphs. There are several directions for scaling GenStat architectures to large graphs, such as approximating expected graph statistics, leveraging graph sparsity, and using more scalable decoders. In terms of application tasks, it would be useful to evaluate how well GenStal supports learning for downstream tasks (link prediction, node classification) with an LDP guarantee [87].
In sum, statistics- based graph generation is fast and effective in generating high-quality graphs. It offers strong option for graph learning that respects individuals privacy.
10

---

References
[1] Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. Advances in Neural Information Processing Systems, 21, 2008
[2] Héber H Arcolezi, Jean- Caan-François Couchot, Bechara Al Bouna, and Xiaokui Xiao. Random sampling plus fake data: Multidimensional frequency estimates with local differential privacy. International Conference on Information & Knowledge Management, pages 47-57, 2021.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer Normalization. stat, 1050:21, 2016.
[4] Nicola De Cao and Thomas Kipf. MoIGAN; An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805.11977 2018.
[5] Fan Chung and Linyuan Lu. The average distances in random graphs with given expected degrees. The National Academy of Sciences, (525))15879-15888 2002.
[6] Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. International Conference on Machine Learning, pages 2302-2312, 2020.
[7] Wei-Yen Day, Ninghui Li, and Min Lyu. Publishing graph degree distribution with node differential privacy. International Conference on Management of Data, pages 123-138, 2016.
[8] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. cruuture-activine relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
[9] Fred W DePiero and John K Carlin. Structural matching via optimal basis graphs. International Conference on Pattern Recognition, 3:449-452, 2006.
[10] Reinhard Diestel. Graph theory, 4th edition, volume 173 of Graduate texts in mathematics. Springer, 2012. ISBN 978-3-642-14278-9)
[11] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30, 2017.
[12] Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771-783. 2003.
[13] Cynthia Dwork. Differential privacy. International Colloquium on Automata, Languages, and Programming, pages 1-12, 2006.
[14] Cynthia Dwork and Jing Lei. Differrnnial privacy and robust statisties. ACM Symposium Theory of Computing, pages 371-380, 2009.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of Cryptography: Third Theory of Cryptography Conference, pages 265-284, 2006.
[16] Talya Eden, Amit Levi, Dana Ron, and C Seshadhri. Approximately counting triangles in sublinear time. SIAM Journal on Computing, 46(5): 1033):66033166, 2017.
[17] Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi, Anton Tsitsulin, and Peilin Zhong, Differ- entially private graph learning via sensitivity-bounded personalized pagerank. arXiv preprint arXiv:2207.0643 069444444.. 2022.
[18] Paul Erdös, Alfréd Rényi, al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 511): 1960.
[19] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: randomized aggregatable privacy-preserving ordinal response. The ACM SIGSAC Conference on Computer and Commu- nications Security, pages 1054-1067, 2014.

---

[20] Dongqi Fu, Jingrui He, Hanghang Tong, and Ross Maciejewski. Privacy-preserving graph analytics: secure generation and federated learning. arXiv preprint SaXiv:2207.000448, 2022.
[21] Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, Edoardo M Airoldi, et al. A survey of statistical network models. Foundations and Trends@ in Machine Learning 2(2): 233,
2010.
[22] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling in graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[23] Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. International Conference on Machine Learning, 97:2434-2444, 2019.
[24] William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
[25] Chaoyang He, Emir Ccyani, Keshav Balasubramanian, Murali Annavaram, and Salman Aves- timehr. SpreadGNN: serverless multi-task federated learning for graph neural networks. arXiv preprint arXiv:2106.027433 2021.
[26] Irina Higgins, Loic Matthey, Arka Pal, Christopher P. Burgess, Xavier Glorot, Matthew M. Botvinick, Shakir Mohamed, and Alexander Lerehner. VAt: Learning basic visual concepts with constrained variational framework. International Conference on Learning Representa- tions, 2017.
[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning graphs Advances in Neural Information Processing Systems, 33:22118-221 221333, 2020.
[28] Han Huang, Leilei Sun, Bowen Du, Yanjie Fu, and Weifeng Lv. GraphGDP: Generative diffusion processes for permutation invariant graph generation. IEEE International Conference on Data Mining, pages 201-210, 2022.
[29] Masooma Iftikhar and Qing Wang. dK-Projection: Publishing graph joint degree distribution with node differential privacy. Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 358-370, 2021.
[30] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Communication--Hfan Effficient triangle counting under local differential privacy. USENIX Security Symposium, pages 537-554, 2022.
[31] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Machine learning, pages 448 0533-456,222 2015.
[32] Tony Jebara and Risi Kondor: Bhattacharyya and expected likelihood kernels. Computational Learning Theory and Kernel Machines, 2777:57-71, 2003.
[33] Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. International Conference on Machine Learning, 162:10362-10383. 2022.
[34] Zach Jorgensen, Ting Yu, and Graham Cormode. Publishing attributed social graphs with formal privacy guarantees, International Conference on Management of Data, pages 107-122, 2016.
[35] Vishesh Karwa and Aleksandra B Slavkovié. Differentially private graphical degree sequences and synthetic graphs. International Conference on Privacy in Statistical Databases, pages 273-285, 2012.
[36] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 400))793-666 201
[37] Thomas Kipf and M. Welling. Variational graph auto-encoders.
arXiv preprint
arXiv:1611.07308. abs/1611.07308, 2016.
12

---

[38] Thomas N. Kipf and Max Welling. Semi Semi-supervised classification with graph convolutional networks, International Conference on Learning Representations, 2017.
[39] Amy Lauger, Billy Wisniewski, and Laura McKenna. Disclosure avoidance techniques at the us census bureau: Current practices and research. Center Disclosure Avoidance Research, US Census Bureau, 2014.
[40] Jure Leskovee, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahra- mani. Kronecker graphs: An approach to modeling networks, Journal of Machine Learning Research, 11(2), 2010.
[41] Yang Li. Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey, ACM Computing Surveys, 55(11): 1-39, 2023.
[42] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference on Learning Representations, 2016.
[43] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. Advances in Neural Information Processing Systems, 32, 2019.
[44] Gabriel Loaiza-Ganen and John P Cunningham. The continuous bernoulli: fixing a pervasive error in variational autoencoders. Advances in Neural Information Processing Systems, 32, 2019.
[45] Tengfei Ma, Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. Advances in Neural Information Processing Systems, 31, 2018.
[46] Emanuele Martorana, Giovanni Micale, Alfredo Ferro, and Alfredo Pulvirenti. Establish the expected number of induced motifs unlabeled graphs through analytical models. Applied Network Science, 5(1):1-23, 2020.
[47] Nikhil Mehta, Lawrence Carin, and Piyush Rai. Stochastic blockmodels meet graph neural networks. International Conference on Machine Learning, 97:4466-4474, 2019.
[48] Darakhshan Mir and Rebecca N Wright. A differentially private estimator for the stochastic kronecker graph model. The 2012 Joint EDBT/ICDT Workshops, pages 167-176, 2012.
[49] Mahdi Pakdaman Nacini, Gregory F. Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. AAAI Conference on Artificial Intelligence, pages 2901- 2907, 2015.
[50] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. Symposium Security and Privacy, pages 111-125, 2008.
[51] Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. IEEE Symposium on Security and Privacy, pages 173-187, 2009.
[52] Mark Newman. Networks. Oxford university press, 2018.
[53] Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernel:: survey. Journal of Artificial Intelligence Research, 12:943-1027, 2021.
[54] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. International Conference on Artificial Intelligence and Statistics, 108:4474 4484, 2020.
[55] Leslie O' O'Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions. International Conference on Learning Representations, 2022.
13

---

[56] Peter Orbanz and Daniel M Roy. Bayesian models of graphs, arrays and other exchangeable random structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2): 437-461, 2014.
[57] Apostolos N Papadopoulos and Yannis Manolopoulos. Structure- based similarity search with graph histograms. Proceedings. Tenth International Workshop on Database and Expert Systems Applications. DEXA 99, pages 174-178, 1999.
[58] Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. ACM SIGSAC Conference on Computer and Communications Security, pages 425 438, 2017.
[59] Bruno Ribeiro and Don Towsley. On the estimation accuracy of degree distributions from graph sampling. IEEE Conference on Decision and Control, pages 5240-5247. 2012.
[60] Matthew Richardson and Pedro M. Domingos. Markov logic networks. Mach. Learn., 62(1-2): 107-136, 2006.
[61] Edo Roth, Karan Newatia, Yiping Ma, Ke Zhong. Sebastian Angel. and Andreas Hacberlen. Mycelium: Large-scale distributed graph queries with differential privacy. The ACM Symposium on Operating Systems Principles, pages 327-343, 2021.
[62] Olch Rybkin, Kostas Danilidis, and Sergey Levine. Simple and effective vae training with calibrated decoders. International Conference Machine Learning, pages 9179-9189, 2021.
[63] Alessandra Sala, Xiaohan Zhao, Christo Wilson, Haitao Zheng, and Ben Y. Zhao. Sharing graphs using differentially private graph models. ACM SIGCOMM Interne! Measurement Conference. IMC '11, Berlin, Germany, November 2- 2011, pages 81-98, 2011.
[64] Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. IEEE International Conference on Acoustics, Speech and Signal Processing, pages 8523-8527, 2021.
[65] Leonardo BL Santos, Luiz Max Carvalho, Giovanni G Soares, Leonardo N Ferreira, and Igor M Sokolov. Beyond the shortest path: the path length index as a distribution. arXiv preprint arXiv:2210.03216. 2022.
[66] Adam Sealfon. Shortest paths and distances with differential privacy. ACM SIGMOD-SIGACT: SIGAI Symposium on Principles of Database Systems, pages 29-41, 2016.
[67] Comandur Seshadhri, Tamara G Kolda, and Ali Pinar. Community structure and scale-free collections of Erdös-Rényí graphs. Physical Review E, 85(5):056109 2012.
[68] Hamed Shirzad, Kaveh Hassani, and Danica J Sutherland. Evaluating graph generative models with contrastively learned features. Advances Neural Information Processing Systems, 2022.
[69] Satyaki Sikdar, Daniel Gonzalez Cedre, Trenton W Ford, and Tim Weninger. The infinity mirror test for graph models. IEEE Transactions on Knowledge and Data Engineering, 35(4): 4281-4292, 2022.
[70] Martin Simonovsky and Nikos Komodakis. Graph VAE: Towards generation of small graphs using variational autoencoders. Artificial Neural Networks and Machine Learning. 11139: 412 422, 2018.
[71] Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. Learning new words. Granted US Patents, 9594741, 2017.
[72] Rylce Thompson, Boris Knyazev, Elahe Ghalebi, Jungtack Kim, and Graham W Taylor. On evaluation metrics for graph generative models. International Conference on Learning Repre- sentations, 2022.
[73] Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001, Bioinformatics, 19(10): 1 1183-1193, 2003.
14

---

[74] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[75] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations. 2018.
[76] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. DiGress: Discrete denoising diffusion for graph generation. International Conference on Learning Representations, 2023.
[77] Zhe Wang, Hongsheng Li, Wanli Ouyang, and Xiaogang Wang. Learnable histogram: Statistical context features for deep neural networks. European Conference on Computer Vision, pages 246-262, 2016.
[78] Chengkun Wei, Shouling Ji, Changchang Liu, Wenzhi Chen, and Ting Wang. AspLDP: collecting and generating decentralized attributed graphs with local differential privacy. IEEE Transactions on Information Forensics and Security, 15:3239-3254, 2020.
[79] Peter Wills and François G Meyer. Metrics for graph comparison: A practitioner's guide. Plos one, 15(2), 2020.
[80] Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Tao Qi, Yongfeng Huang, and Xing Xie. A federated graph neural network framework for fions, 13(1):3091, 2022.
personalization. Nature Communica-
[81] David J. Wu, Joe Zimmerman, Jérémy Planul, and John C. Mitchell. Privacy-preserve shortest path computation. Annual Network and Distributed System Security Symposium, 2016.
[82] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference machine learning, pages 6861-6871 2019.
[83] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
[84] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. International Conference on Knowledge Discovery and Data Mining, pages 1365-1374, 2015.
[85] Carl Yang, Haonan Wang, Ke Zhang, Liang Chen, and Lichao Sun. Secure deep graph generation with link differential privacy. International Joint Conference on Artificial Intelligence, pages 3271-3278, 2021.
[86] Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok- Yan Lam. Local differen- tial privacy and its applications: A comprehensive survey. arXiv preprint arXiv:2008.0300 2020.
[87] Minji Yoon, Yue Wu, John Palowitch, Bryan Perozzi, and Ruslan Salakhutdinov. Graph generative model for benchmarking graph neural networks. ICML., 2023.
[88] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep regressiee models. International Conference on Machine Learning, pages 5708-5717, 2018.
[89] Kiarash Zahirnia, Oliver Schulte, Parmis Naddaf, and Ke Li. Micro and macro level graph modeling for graph variational auto-encoders. Advances in Neural Information Processing Systems, 2022.
[90] Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. A survey on federated learning. Knowledge- -Bssed Systems, 216: 106775 2021.
[91] Yuxuan Zhang, Jianghong Wei, Xiaojian Zhang, Xuexian Hu, and Wenfen Liu. A two-phase al- gorithm for generating synthetic graph under local differential privacy. International Conference on Communication and Network Security, pages 84-89, 2018.
15


Reviews:
[{"review_id": "cTTdhlTd4z", "reviewer": "Reviewer_92Y3", "summary": "The authors introduce a deep graph generator model based on graph statistics. Instead of encoding the graph itself, deterministic high-level graph statistics are first computed from the graph, and these are passed to a neural encoder and graph decoder. The stated main motivation for this approach is for increased privacy: allowing graphs to be generated purely from the graph statistics may be particularly good at preserving graph-level properties while removing user-level private edge/node characteristics. As stated by the authors, it is also the first graph generator that \"does not require observations of individual nodes or edges\".\n\nThe authors do the following in the rest of the work:\n - define an explicit probabalistic model for graph statistics, and use it to derive a variational lower bound for the graph encoding problem.\n - define a permutation-invariant inference distribution for their encoder (\"GenStat\") which can be used for link prediction / graph classification\n - analyze the privacy properties of GenStat\n - benchmark GenStat on standard graph generation evaluations\n - provide a privacy/accuracy tradeoff analysis of GenStat and the most competitive baseline", "questions": "Can the authors comment on my observations about Figure 4? Specifically, does the fact that GenStat maintains constant MMD RBF at all privacy budgets have implications about the true ability of GenStat to preserve privacy? Is there another empirical evaluation that could be done to show GenStat's response to a privacy budget?", "limitations": "Yes, the authors have adequately addressed limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "To the best of my reading, the manuscript appears quite technically sound, with a well-defined problem statement, sound probabalistic setup, accurate loss derivations, and appropriate theoretical analyses. The empirical study is thorough and appropriate for the problem. The writing is clear and easy to follow.\n\nThe contribution itself is interesting and likely to impact graph learning beyond the specific application (graph generation) presented in the paper. The joint distribution of graphs and their derived statistics is an interesting topic of study that has been explored independently in various areas of graph ML.", "weaknesses": "I identify one main weakness, which contributed to my score of 3 and not 4 in the \"Soundness\" category. Based on Figure 4, it seems as though the proposed method GenStat does not respond to the privacy budget: in other words, the measurement of the discrepancy of the generated graphs from the test set (MMD RBF) does not change sensibly to the privacy parameter. On the other hand, the MMD RBF of the most competitive baseline BiGG does decrease with the privacy budget, as expected. This calls into question the effect of the Edge LDP guarantee on GenStat: it is possible that GenStat has a *fixed* privacy effect due to its immediate use of graph high-level graph statistics, rather than one that can be reasonably controlled with an Edge LDP technique. While it is nice that GenStat generates realistic graphs at all privacy budgets, this calls into question how much privacy is actually being preserved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive feedback, especially regarding their observation that \"*The contribution itself is interesting and likely to impact graph learning beyond the specific application (graph generation) presented in the paper.*\"\n\n**Questions.** Can the authors comment on my observations about Figure 4? Specifically, does the fact that GenStat maintains constant MMD RBF at all privacy budgets have implications about the true ability of GenStat to preserve privacy? Is there another empirical evaluation that could be done to show GenStat's response to a privacy budget?\n\n**Answer.** GenStat is indeed sensitive to the privacy budget (ε) in that the MMD-RBF is not constant at all privacy budgets. For example, in the Grid dataset (Figure 4.c), the MMD-RBF of the generated graph by GenStat decreases from ε=1 to ε=3 (larger ε; ε=0 indicates perfect privacy). Increasing the value of ε to 4, and larger, does not significantly improve the quality of generated graphs since GenStat has already reached its near-optimal performance.\n\nFor the other two datasets, Mutag (Figure 4a) and PTC (Figure 4b), GenStat reaches its near-optimal performance even earlier with ε=1. Thus, for the given points with ε>1, the MMD-RBF curve looks flat. If we increase the resolution of the ε-axis to include ε=0.01, 0.1, and 0.5, we observe that the MMD-RBF of GenStat decreases as the privacy budget decreases; please see the following table, which uses the same experimental setting described in Section 4.3.\n\nTable: GenStat under ε-Edge LDP guarantee with different privacy budgets, in terms of the Random GNN-Based MMD RBF score. A lower score is better. A lower ε indicates a stricter privacy measure.\n| ε      | 0.01 | 0.1  | 0.5  | 1    | 2    | 3    | 4    |\n|--------|------|------|------|------|------|------|------|\n| Mutag  | 1.18 | 0.65 | 0.43 | 0.22 | 0.25 | 0.20 | 0.24 |\n| PTC    | 1.81 | 1.18 | 0.40 | 0.05 | 0.06 | 0.05  | 0.06 |\n| Grid   | 1.93 | 1.84 | 1.33 | 0.93 | 0.86 | 0.68 | 0.76 |\n\nWe used the lower resolution with ε≥1 in the paper to focus on the comparison with the adjacency-based model (Bigg). However, we believe Figure 4 would benefit from an increased resolution. Thank you for raising this point."}, {"review_id": "GqQSaZwaDv", "reviewer": "Reviewer_ijbs", "summary": "The paper proposes a new approach to learning deep graph generative models that can generate more realistic graphs while protecting local privacy. The proposed GenStat architecture uses graph statistics instead of the entire adjacency matrix to train deep generative models.", "questions": "- What are the limitations of graph statistics that can be used with GenStat? For example, we can view an adjacency matrix as a type of graph statistics as well.", "limitations": "Some of the limitations of the paper have been discussed, but it is not sufficient (see \"Questions\").", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper presents a new perspective to learning deep graph generative models that can generate more realistic graphs while protecting local privacy.\n- The authors demonstrate that GenStat outperforms other graph generative models in terms of imitating graph statistics from training sets.", "weaknesses": "- The problem is not well motivated. It is unclear to me why the standard graph generation methods (trained with reconstruction loss) will have privacy issues. In practice, when the training set consists of multiple graphs (multiple molecules), a trained graph generative model can unlikely memorize the training data (since GNNs are usually not powerful enough to memorize the raw data). \n- The theoretical results are limited. Although the authors show that the proposed algorithm is differentially private, it does not develop the theoretical properties of a standard graph generation and argues that those methods are not differentially private.\n- The comparison with baselines is limited. The paper should focus more on comparing with modern learning based graph generators. Figure 3 and Table 1 take almost 1 page, but it is not surprising - there have been hundreds of research papers showing that learning-based graph generative models can outperform classic graph generative models. I would highly suggest the authors replace the baselines in Figure 3 with learning based graph generators. \n- The description of the proposed method is vague. After reading the paper, I still could not see the exact algorithm of how a graph is generated (e.g., when nodes have attributes) with GenStat. Many implementation details are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's attention. Our responses to Weaknesses (W) and Questions (Q) are provided below; all references and citations refer to the paper.\n\n**W1.Privacy Issues in Standard GGMs:** We provide a clear motivation for the problem in the introduction (lines 23-38). Graph Generative Models (GGMs) trained with reconstruction loss, have privacy issues because they require access to the adjacency matrix to do training. An adjacency matrix contains sensitive information because it directly reveals the individuals/entities with which a person (node) has interacted. We provide an example in the introduction (lines 31-34) of how Google, Apple and Microsoft collect perturbed node-level graph statistics rather than the actual adjacency matrix in order to preserve the privacy of their users. There is a huge difference between knowing exactly which 10 websites a user visited and knowing that a user visited 10 websites. *The issue of privacy does not revolve around the GNN memorizing the raw data;* it is the collection, storage and processing of the raw data that is the privacy problem.\n\n**W2. Theoretical Results and Edge-LDP in Standard GGMs**. We consider that the paper provides two important theoretical results. \n1) We establish that the proposed method satisfies ε-Edge Local Differential Privacy (*Edge-LDP*); (Proposition 2; lines 162-164); \n2) We show that the gradient updates, model distribution, and inference distribution of the graph generation procedure are permutation-invariant if the descriptor functions are permutation-invariant. (Observation 1; lines 142-147).\n\nThese are the two critical properties of our proposed graph generation scheme – it achieves the desired privacy while respecting the permutation invariance.\n\nWith regard to *“standard”* GGMs, we consider two groups:\n- Methods that require access to adjacency matrices [6,83,40, 82] (lines 58-60) and clearly do not satisfy Edge-LDP because they explicitly process data that contains the edge information. In fact, \"Edge-LDP [54,73], guarantees plausible deniability for the inclusion or removal of a particular edge associated with a node\", lines 150-152. Providing adjacency-based GMMs with nodes’ interactions (adjacency matrix) removes the possibility of any deniability for nodes. \n- Methods that process graph statistics [65,5](lines 55-58). In general, these models can be used to satisfy LDP, but they are not neural methods and their performance is dramatically inferior (see Tables 1,2,4 and Figure 3).\n\n**W3. Baselines.** We remind the reviewer that the key difference between our new GenStat and the previous deep Graph Generative Models(GGM) is that the previous methods require access to potentially sensitive raw data—the entire adjacency matrix—whereas GenStat training is based on summary statistics only. See also Related Work, lines 55-66. The previous work showing that learning-based GGMs can outperform classic GGMs is not an apples-to-apples comparison because the deep GGMs use more information than the classic GGMs (again, the entire adjacency matrix rather than graph statistics). \n1) Our comparison with classic GGMs baselines (Table 1) is, therefore, a new apples-to-apples comparison of our new deep statistics-based method with classic statistics-based methods.\n2) In an apples-to-oranges comparison, we benchmarked our statistics-based GenStat against *5 SOTA deep GGMs (BiGG [6], GraphVAE-MM [83], GRAN [40] and GraphRNNs [82])* that use the entire adjacency matrices (Table 2).\n3) We also compare GenStat against Edge-LDP versions of deep GGMs (Figure 4).\n\nFor all models, we use SOTA evaluation metrics to compare the distance between the distribution of test and generated graphs. We use a)GNN-based [64,68] and b)statistics-based [82] evaluation metrics and c)we also compare the generated graphs by visual inspection (see Tables 1, 2, 3, 4, 5, 6 and figures 7,3 in the Appendix and Paper).\n\nAs per the reviewer's recommendation, we have relocated Figure 7 from the Appendix to the Main Paper and replaced it with Figure 3.\n\n**W4. Method Description.** Node attributes: we discussed in Section 5 (lines 294-297) and following the baselines [6, 82, 83], this work focuses on simple unattributed graphs (graphs without node and edge attributes). However, GenStat can be extended to attributed/heterogeneous graphs, where nodes/edges possess attributes, including potentially sensitive ones, by defining the graph descriptors as functions of both feature matrices and edge tensors (lines 296-297).\\\nGraph Generation: To generate graphs at test time, we use a standard sampling method Ma et al. [42], as follows. We sample graph embeddings from the prior p(Z), then use the decoder to compute a soft adjacency matrix Ã with entries in [0,1] representing link probabilities. We use a 0.5 threshold to convert link probabilities to hard binary links.\n\nWe believe we have clearly described how GenStat is trained through the Paper and Appendix. \n- The proposed probabilistic model is explained in Sec. 3.1 (lines 108-111) as well as in Figure 2.a.\n- The objective function is discussed in Sec. 3.2 (Equation 5).\n- The model architecture is described in Sec. 7.2 (lines 591-610 ) as well as in Figure 2.b.\n- Graph statistics used in GenStat explained in Sec. 3.5 (lines 166-190).\n- The hyperparameters are discussed in Sec. 7.2 (lines 591-610 ).\n- In addition, our repository contains the implementation of the model training procedure, graph statistics, neural model as well as datasets and used hyperparameters.\n\n**Q.** We discussed the limitation of graph statistics used by GenStat in Section 3.5 (lines 166-173). The graph statistics used in GenStat are 1) permutation-invariant; 2) aggregation of node-level statistics (Eq 8); and 3) differentiable.\n*The adjacency matrix* does not have the aforementioned properties; it depends on the node ordering and is not the aggregation of node-level statistics. Consequently, it cannot be used as a statistic for GenStat."}, {"review_id": "CbP3AphUjN", "reviewer": "Reviewer_hsws", "summary": "This paper considers a new setting that learns a deep graph generative model from aggregate graph statistics rather than graph adjacency matrix. The motivation for generating graphs from statistics is privacy preservation. For this task, the authors propose a simple VAE model, where the encoder takes graph statistics as input and the decoder outputs graphs that have similar statistics with the input. Experiments demonstrate the effectiveness of the proposed method to some extent.", "questions": "See Weakness 1.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper proposes a new setting, i.e., learning a deep model for statistics-based graph generation.\n2.\tThe proposed model generates graphs with more similar statistics with training sets than previous parametric models.", "weaknesses": "1.\tMy main concern is about the task setting. \na)\tWhat's the application of the generated graphs. In another word, what downstream tasks can the generated graph be used for?\nb)\tWhich datasets support the claimed application scenario?\nc)\tThe evaluation metrics are not straightforward enough. To demonstrate the usefulness of the generated graphs, I think it necessary to provide evaluation results on downstream tasks.\nd)\tIf only easy statistics are preserved, how to make sure that the generated graphs benefit downstream tasks?\ne)\tHow are the considered graph statistics determined?\n2.\tThe technical contribution is minor, because the proposed model is a naive invariant of VAE. Otherwise, the authors may want to highlight the technical difficulties.\n3.\tSome typos. Line 47 ‘(Appendix Sec. 7.11)’: There is no Sec. 7.11. Line 87: Maybe you forget to bolden Federated Learning. Line 245 ‘87.37% vs. 23.76 for Pretrained-GNN’: Maybe you wrongly copy the results. Same mistake in Table 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's attention to the paper. Our responses to Weaknesses (W) are provided below; all references and citations refer to the paper.\n\n**W1.a and W1.b. Task Setting and Application of Generated Graphs.** As we explain in related work (lines 55-61 and Figure 5), we start with *realistic graph generation* as our basic task that has been studied extensively in previous work for decades, both in parametric and neural approaches, including many papers published at NeurIPS (Zahirnia et al. (2022) and Liao et al. (2019)) and ICML ( Dai et al. (2020); You et al. (2018)) which are our main baselines. The research question we address is how to learn to generate realistic graphs while protecting private information from raw data.\\\nOne of the lessons from the recent impact of generative AI is that generative models are useful independent of downstream tasks. For example, many research groups and companies have addressed the task of generating realistic images, independent of downstream tasks such as image classification. Experimental settings, datasets, and evaluation metrics used in this study closely follow recent studies in realistic GGMs You et al. (2018); Zahirnia et al. (2022); Dai et al. (2020).\n\n**W1.c. Complex Evaluation Metrics and Downstream Tasks for Models Evaluation.** The metrics we employ in this paper for assessing the quality of generated graphs are not straightforward because quantifying the realism of generated structured objects is not straightforward. Indeed, there are research papers devoted to the question of how to evaluate the quality of generated objects, both for images (https://arxiv.org/pdf/2206.10935.pdf) and graphs O’Bray et al. (2022); Shirzad et al. (2022). We use the SOTA graph quality metrics proposed in the previous literature. Lines 215-228 and Appendix 7.6 explain these metrics.\\\nWhile it is true that generative models support downstream applications, the field of generative graph modelling has in general moved towards more direct measures of generated graph quality. Two main reasons are 1) Performance on downstream tasks may not correlate with the quality of generated objects. For example in graph classification, SOTA performance is achieved by differentiable pooling methods, that transform input graphs into sparse unrealistic versions before embedding them for classification. 2) There are potentially many downstream tasks (e.g. node classification, link prediction) and many datasets for evaluating them. It is not clear which tasks/datasets to pick to obtain a ranking of graph generative methods. For further discussion, please see the references we cite, especially O’Bray et al. (2022).\n\n**W1.d. Benefit of Generated Graphs, with Limited Statistics, for Downstream Task.** Like other areas of generative AI, graph generative modelling has moved towards directly estimating the realism of the generated objects. The GNN-based evaluation metrics, used in this and previous studies, are independent of graph statistics or specific downstream tasks and can compute the dissimilarity between any two sets of graphs regardless of the domain, as discussed in (O’Bray et al., 2022). The GNN-based representation allows us to evaluate the model on downstream tasks that were not known during the learning of the representation, as discussed in Shirzad et al. (2022). The statistics we investigate in this paper are good default statistics that are effective across a variety of domains. As suggested in Zahirnia et al. (2022), for specific domains/tasks they can be augmented with domain-specific statistics in a straightforward and flexible manner.\n\n**W1.e. Determining the Graph Statistics.** The default graph statistics used in GenStat are 1) permutation-invariant; 2) aggregations of node-level statistics (that can support Edge LDP); and 3) differentiable (see lines 166- 173). These statistics are known from prior research to be generally important for graph modelling across different domains and are easy to interpret. We should emphasize that GenStat is a flexible framework (lines 95-97), allowing for the incorporation of any graph statistics of interest which satisfy the properties discussed in Section 3.5 (lines 166-173).\n\n**W2. Technical Contribution Compared to a Simple VAE.** While GenStat relies primarily on VAE, as opposed to standard Graph VAE, it is designed to only depend on integrated observed graph-level statistics, which is not a naive extension to VAE. \n- This work, compared to simple VAE, proposes a novel two-level probabilistic model in which the adjacency matrix is latent (as well as the graph-level representation Z) and observed variables are limited to a predefined set of graphs’ statistics (Figure 2). Under this setting, the marginal distribution over the graph statistics is a double integral. We approximate the mixture integral with a Variational Auto-Encoder (VAE) and Monte Carlo decoder.\n- To make the graph-level statistics differentiable and informative, we adopt adaptive soft histogram functions to summarize graphs in permutation invariant vectors with a dimensionality of O(log(N)). For each graph invariant, the diagonal co-variance parameter is computed using the maximum likelihood estimate given the estimated means.\n\n**W3. Typos**\n- **Q.** Line 47 ‘(Appendix Sec. 7.11)’: There is no Sec. 7.11.\\\n**A.** Thank you for identifying the typo. We have now updated the text to refer to (Appendix Sec. 7.9).\n- **Q.** Line 87: Maybe you forget to bolden Federated Learning.\\\n**A.** Thank you for identifying the possibility of a typo. We intended to study Federated Learning under the \"Graphs and privacy.\" subsection as a graph privacy-preserving paradigm. We have not made any changes to the text.\n- **Q.** Line 245 ‘87.37 vs. 23.76 for Pretrained-GNN’: Maybe you wrongly copy the results. Same mistake in Table 3.\\\n**A.** Thank you for identifying the typo. The mentioned results are for the Protein dataset, not IMDb. We have now updated the text.\n\n"}, {"review_id": "l6VGwdXKvF", "reviewer": "Reviewer_bJqH", "summary": "This paper proposes a deep graph generative model from aggregate graph statistics, to protect privacy. The authors designed an inference model to learn latent variables from graph statistics. And the probabilistic model keeps permutation invariance.", "questions": "1. Why do we have to use graph statistics to protect privacy? Why not simply hide the true names/items?\n2. During the inference stage, there are two probabilistic models, which take more time compared with GraphRNN. Can you give a computation complexity analysis compared with popular baselines? (GraphRNN, GRAN)", "limitations": "See weakness.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. To learn the intractable latent variables, the paper proposes a reasonable lower bound.\n2. The probabilistic model could keep permutation invariance.\n3. The model can learn graph statistics explicitly.", "weaknesses": "1. I think it is time-consuming for the descriptor to conclude the graph statistics compared with the adjacency matrix-based model, especially when the number of graphs is large/each graph is large. So the comparison with such models is somewhat unfair.\n\n2. The performance high relies on which graph statistics are used. Without enough/reasonable statistics, the model can not capture the complex dependency.\n\n3. The assumption for latent variables $\\tilde{A}$ to be independent will hurt the expressiveness of the model.\n\n4. The model is hard to be used on molecules. First this  model can not be used on graphs with node features. Second, it is impossible to learn the molecule structures with graph-level statistics (also very hard to design such statistics with node features).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's attention to the paper. Our responses to Weaknesses (W) and Questions (Q) are provided below; all references and citations refer to the paper.\n\n**W1.** We agree that calculating graph statistics has computational overhead. However, the training time of GenStat, *which includes time to conclude graph statistics by descriptor functions*, is substantially faster than those for deep adjacency-based GGMs, up to 2 orders of magnitude compared to SOTA autoregressive models (see Table 7 in the appendix). Evaluating the edge reconstruction probability is expensive and tends to dominate the training time of adjacency-based GGMs (lines 282-283). In addition, graph statistics can be calculated in parallel in near constant time for small and medium size graphs.\n\n**W2.** We agree that the performance of GenStat is influenced by graph statistics. However, our experimental results on 8 datasets, spanning various domains and exhibiting diverse structural properties, demonstrate that the default graph statistics employed in GenStat are capable of modelling graphs with a wide range of structural characteristics. We also should emphasize that GenStat is a flexible framework (lines 95-97), allowing for the incorporation of graph statistics of interest (which satisfy the properties discussed in Section 3.5) in a target application. O’Bray et al. [51] note that different graph statistics are important for different applications. O’Bray et al. [51] therefore advise selecting a GGM based on the graph statistics of interest in the target application.  The adaptability of GenStat enables researchers to tailor the model to suit different applications effectively.\n\n**W3.** We agree that the independence assumption may affect the model’s expressiveness. However, it resulted in much more efficient computations. Moreover, even with the independence assumption, GenStat ranks among the top two models in 8 out of 10 reported MMD RBF scores, for real-world datasets (see Table 2), in comparison with *SOTA adjacency-based GGMs*.\n\n**W4.** *Our experiments actually provide evidence that it is possible to learn molecular structures with graph-level statistics.* We evaluate GenStat on ogbg-molbbbp (*a molecule dataset* containing 2039 real-world molecular graphs) as well as MUTAG and PTC (datasets of chemical compounds). In comparison with deep GGMs, trained on complete adjacency matrices, GenStat is competitive in terms of both GNN-based and statistics-based evaluation metrics (see Tables 2 and 5). In particular, GenStat outperforms the SOTA adjacency-based deep GGMs on ogbg-molbbp (molecular dataset) in terms of GNN-based evaluation metrics (Table 2). We achieved these results with our default statistics. An interesting direction for future research would be to consider domain-specific statistics for molecular graph generation. A possible candidate for such statistics could be derived from the semantic constraints introduced in previous work on molecule graph generation [42].\n\nThe model can expand to generate the node and edge features. For example, as in GraphVAE [66], the decoder generates the node and edge features. The graph descriptors will be defined as functions of both feature and edge matrices, see lines 295 - 297. Our paper follows the graph structure learning research track and shows that modelling aggregated graph statistics displays competitive quality to SOTA adjacency-based GGMs while guaranteeing ε-Edge LDP. SOTA deep GGMs [6, 82, 83] and other traditional  GGMs (BTER, Chung-Lu) that focus on the problem of learning structural information from graphs do not accommodate node and edge features and we wanted to use exactly their setting. We agree that attributed graphs are an important topic and discuss extending statistics-based graph generation to attributed graphs as a valuable direction for future work (lines 321-325).\n\n**Q1.** *Graph anonymization techniques* enable the public release of private graphs by hiding the true names/items. These techniques have two main limitations, as discussed in previous works [47] and https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10098897&tag=1\n1) These techniques provide limited protection, typically only against specific known attacks.\n2) These techniques are mainly applicable in a centralized setting with a trusted data curator.\n\nAs we discussed in the paper, Statistics-based graph generation supports the more challenging use case of decentralized graphs where privacy concerns rule out collecting raw data in a central repository (see lines 27-37). In addition, as we proved in  Lemma 1. of Proposition 2 (lines 578-584) collected perturbed graph statistics satisfy Edge LDP and are secure against post-processing attacks.\n\n**Q2.** Using two probabilistic models can cause computation overhead. However, compared to autoregressive models, GenStat benefits from parallel computation, leading to faster training and generation times, up to 2  orders of magnitude (see Tables 7 and 8).\n\nThe Table below compares the computational complexity of popular GGMs; N and \\|E\\| are nodes and edges numbers. Note for GenStat, we assumed matrix multiplication with O(N^3)  complexity to exactly compute the descriptors. Approximating graph statistics [16, 32, 55] and exploiting the sparsity of real-world graphs can substantially reduce the computational cost (see lines 298-300).\n| Model| Auto-Regressive Steps| Train  | Generation|\n|-|-|-|-|\n| GenStat| O(1) | O(N^3) | O(N^2)|\n| BiGG [6] |log(N)| O(min((\\|E\\|+N)log(N), N^2)) | O(min((\\|E\\|+N)log(N), N^2))|\n| GRAN [4] |N| O(N^2)   | O(N^2)|\n| GraphRNN [82]| \\|E\\| * N| O(N^2)| O(N^2)|\n\nAutoregressive models generate the graphs sequentially, an element at each step where each element is conditioned on the previous ones. The dependencies between steps, make it difficult to parallelize the training process. GenStat generates a graph (updates the gradients) in parallel, which leads to substantially faster training."}]

Author rebuttal:

Meta-review: This paper proposes privacy-aware graph generation from graph statistics. Its key idea is to use deterministic high-level graph statistics to represent a graph and decode a graph from the statistics. This preserves privacy in the sense that the generator does not observe individual nodes or edges for generating the graph. 

The main concern of this problem was about the problem setting of privacy-aware generation, the lack of novelty compared to an existing work [Yoon et al., 2023], and whether the empirical evaluation properly shows the effectiveness of the proposed method under the considered scenario. After a thorough discussion between the reviewers, the reviewers came to an agreement that 
- The considered problem-setting has real-world applications. 
- The work is novel compared to [Yoon et al., 2023] since the existing work does not actually generate a graph and deals with the setting where a private, synthetic "doppelganger" of a single large graph is needed. 

Upon reading the paper myself, I was a bit concerned that the graph being generated does not reflect the applications that actually require privacy-aware generation, e.g., why is privacy-aware generation necessary for Protein or Grid graphs? However, I think this is more about the lack of proper benchmarks fir graph generative models, so I down-weight this issue. 

Overall, I recommend acceptance for this paper.
Decision: Accept (poster)