Synthetic Data Generation of Many-to-Many Datasets via Random Graph Generation
Authors: Kai Xu
Georgi Ganev
Emile Joubert
Rees Davison
Olivier Van Acker
Luke Robinson
Venue: ICLR 2023 poster (2023)
Keywords: synthetic data generation
random graph generation
differential privacy

Abstract: Synthetic data generation (SDG) has become a popular approach to release private datasets.
In SDG, a generative model is fitted on the private real data, and samples drawn from the model are released as the protected synthetic data.
While real-world datasets usually consist of multiple tables with potential \emph{many-to-many} relationships (i.e.~\emph{many-to-many datasets}), recent research in SDG mostly focuses on modeling tables \emph{independently} or only considers generating datasets with special cases of many-to-many relationships such as \emph{one-to-many}.
In this paper, we first study challenges of building faithful generative models for many-to-many datasets, identifying limitations of existing methods.
We then present a novel factorization for many-to-many generative models,  which leads to a scalable generation framework by combining recent results from random graph theory and representation learning.
Finally, we extend the framework to establish the notion of $(\epsilon,\delta)$-differential privacy.
Through a real-world dataset, we demonstrate that our method can generate synthetic datasets while preserving information within and across tables better than its closest competitor.

Published as a conference paper at ICLR 2023
SYNTHETIC DATA GENERATION OF MANY-TO-MANY DATASETS VIA RANDOM GRAPH GENERATION
Kai Xu"
Georgi Ganev
Emile Joubert
Rees Davison
Hazy
Hazy georgi @hazy. com
Hazy emi le@hazy..co.o com
Hazy rees@hazy com
me@xuk.ar ad
Olivier Van Acker
Luke Robinson
Hazy
Hazy
ovanac01@mail bbk.ac. ac.uk uk
luke@hazy.com
ABSTRACT
Synthetic data generation (SDG) has become popular approach to release pri- vate datasets, In SDG, generative model is fitted on the private real data, and samples drawn from the model are released as the protected synthetic data. While real-world datasets usually consist of multiple tables with potential many-to-many relationships (i.c. many-to-mann -o-ynyy datasets), recent research in SDG mostly focuses on modeling tables independently or only considers generating datasets with spe- cial cases of many-to-many relationships such one-to-many. In this paper, we first study challenges of building faithful generative models for many-to-many datasets, identifying limitations of existing methods. We then present novel factorization for many-to-many generative models, which leads to a scalable gen- eration framework by combining recent results from random graph theory and representation learning. Finally, we extend the framework to establish the notion of (e, 8) -ddifferrntial privacy. Through real-world dataset, we demonstrate that our method can generate synthetic datasets while preserving information within and across tables better than its closest competitor.
INTRODUCTION
Private data release has gained much attention in recent years due to new regulations in privacy such as General Data Protection Regulation (GDPR). To obey such regulations and to protect privacy, popular approach from the machine learning community called synthetic data generation (SDG) is developed in various domains (Nowok et al., 2016 Montanez et al. 2018 Xu & Veeramachaneni 2018 Xu et al. 2019 Lin et al. 2020 Tucker et al. 2020) Xu et al. |021] et 2001). In SDG, synthetic data that is statistically similar but not identical real data is released as replacement of the real data to protect. On top of it, special attention has also been paid to make sure these methods work well on tabular data as most real-world datasets are stored tables in databases (Montanez
et al. 2018 Xu & Veeramachaneni 2018 Xu et al. 2019 Nazabal et al. 2020: Ma et al. (020)).
At the core of most SDG methods are generative models probabliiic models that one can drawn samples from. Usually generative model is firstly trained to capture the distribution of the private real data, and then samples are drawn from the model they can be released as protected synthetic data. However, this procedure without extra care does not have guarantees privacy. To tackle this, research in this direction has also been focusing on differentially private generative models (Zhang (et al. 2017, Xie et al., 22188 [Joddnn et al. 2018)) generativv models that satisfy notion of privacy called differential privacy (Dwork et al. 2014), which controls the amount of information individual datum reveal. Appendix proovides an illustration of how generative models are used for SDG.
2018]Jordon
While real-world datasets usually consist of multiple tables with potential many-to muny-to-many relation- ships. SDG for such type of data is not well-studied. Most of recent work focuses on modeling tables
independently (Xu & Veeramachaneni 2018 Xu et al. 2019: Nazabal et al.) 2020 Ma et al. 2020) considers generating many-to- to-many relationships but only for special cases such as mn-tto-many (Getoor et al. 2007 Montanez et al. 2018). As a side effect, privacy for multi-table SDG with many-
Now at Amazon; work done prior to joining Amazon 1 Also Ph.D candidate the University College London

---

Published as a conference paper at ICLR 2023
dog(n()
deginn) -J
0
0
1
1
11
deg(nv)
dogtnf) -J
0
0
2
3
degin!) -1
0
1
0
0
0
deg(
2
0
0
0
2
2
0
0
Aglo0=)
0
0
3
1
0
2
(a) Bipartite graph B with annotations (b) Adjacency matrix G (left) and (c) BJDD matrix Pa with supports for node degrees
biadjacency matrix B (right) du deg(nu), d. deg(nv)
Figure 1: An illustration of bipartite graphs and their related representations and statistics.
to-many relationships is also under-studied. In fact, relationships in real data can also reveal private information (Sala et al., 2011 Proserpio et al. 2012). For example, in a customer-merchant dataset, the number of links to merchant could reveal its identity because of its uncommon popularity.
This paper studies the challenge of building faithfu generative models (Webb al., 2018) to synthesize data together with their many-tt-many relationships, and proposes novel factorization for many-to-many generative models, which leads scalable approach by combining results from random graph theory and representation learning. In short, our paper has the following contributions:
1. We study possible factorization of faithful generative models for many-to to-many data and identify limitations of those taken by existing approaches.
2. We propose novel factorization for modeling distributions over many-to-man data and we use it to develop a synthetic data generation framework using methods from random graph generation, node representation learning and set representation learning.
3. We extend the proposed framework to establish the notion of (c, differrretl privacy.
4. We evaluate two model instances from our framework, BayesM2M and NeuralM2M, the MOVIELENS dataset, demonstrating its superior performance over its closest competitor, SDV, especially on capturing information in many-to- mo-many relationships.
2 BACKGROUND AND NOTATIONS
Bipartite and multipartite graphs A bipartite graph B = (U, V, is a tuple of two disjoint node
sets U, V (called upper and lower nodes respectively) as well as a set of edges L between them. Each
node is represented by a tuple of its index and attribute, e.g. n = (ith xT)
U for k = 1..... U].
Each edge is represented by a tuple of node indices, i.e. 1s := (1t (h) E L for k: = 1,..., [L] Such edge sets can be represented for an illustration. A generalised notion of bipartite graphs called multipartite graphs, denoted as M
adjacency matrices G or biadjacency matrices B;
figure Ib
M = ((TT))== (T. k)=1), are graphs with N disjoint node sets and M s (*) edge sets.
Modeling datasets with many-to-man, relationships Paatasets with many-to-many relationships, such relational databases, can be viewed as multipartite graphs. Denote the generating distribution of a given multipartite graph Maaa as Pasta (M). The goal of this paper is to build a generative model po(M) with learnable parameter 0 and develop learning algorithm Ai that takes Mana as inputs and outputs the optimal model pa- with parameter 0", s.t. pa- (M) is close to (M). After learning, a sample M is drawn from the model and used as synthetic data; we denote this sampling process/algorithm as A2
Differential privacy In this work, we are interested in establishing the standard (e, -diifferenni privacy, a.k.a. (e, o)-D approximate DP. Denote A Ag Ai. We say model pa with A is (c, 6DDP according to the following definition (Dwork et al. 20144:
Definition 1 ((c, 5DP for pe with A). A generative model pe with the synthesis algorithm A is (e, (DP for all S C Range(A) (A) and for all B,B that differ on a single element:
P(A(B) E ES) S (xp())P(A((B) E ES)+ +
'The term "faithfull" as in faithful generative models refers to the fact that the model does not introduce any conditional independence that is not true in general (Webb al. 2018). It is true for how our proposed model factorizes individual tables well their relationships.
'Note here we are intended to avoid using terms such as primary/foreign keys and parents/children from the relational database literature. This is because in order to model the joint distribution for given dataset, parent- child directions can he rearranged for modeling convenience in favor of some particular factorization of the joint.
2

---

Published as a conference paper at ICLR 2023
In our case, S is the output of the synthesis algorithm A's training procedure, B is a many-to to-many dataset while we are interested in the most general case (with strongest privacy protection) and define an element a single node that could be part of either U or V. If 6 = 0, we also call model po with A satisfies e-differential privacy, i.e. c-DP.
Learning graph distributions Consider the distribution Paaa(L) for a given set of edges aam Unlike setup in work like Liao et al. (2019) in which multiple samples from Pdata are given, we are presented with a single sample from Pdata- Therefore, rather than replying on the standard notion of learning as probability divergence minimization using empirical samples, consider learning model po (T.) such that samples from it share similar graph properties as Luttaa
Graph properties We consider the dK -dixtribbutions from Mahadevan et al. (206)) with d = 2, defined the (joint) degree distribution of all pairs of d nodes in the graph | We call all graphs with a given dK- distiisiibuutions dk- ggrapss. For example, OK -graphss share the same graph density, 1 K -graphs share the same distribution of node degrees, 2Krgraphs share the same joint distributions of degrees of node pairs, etc. We call models that sample dK -graphs d.K -egeerrrrsorss We consider the same notion for bipartite graphs, defining bipartite dKK -grrphss, and consider learning pa that generates bipartite 2 K- -Kgraphhs of data. For a bipartite graph B, we denote its bipartite joint degree distribution
(BJDD) the empirical distribution of samples ((deg(n(tt)) deg(n(()))) k=1- )=))==>>>>>>> where n(i) denotes
[I.]
the node with index (similarly i(n) is the node index for node n.) and (n) is the degree of the node n. Such empirical distribution can be represented as a matrix PJ along with the supports du, d,, for both dimensions; see figure Tc for an illustration. One can also compute the (marginal) degree distri- butions of the upper or lower nodes from BJDD. For example, that of upper nodes P., a probability vector (a vector of whose elements sum up to 1) in which its i-th element [ E, PJ H jl/ /d, [t].
3 RELATED WORK
Generative models for tabular data In general, there are two categories of generative models that have been successfully applied to tabular data. One is based on classic graphical models. This includes directed graphical models such Bayesian networks PrivBayes (PrivBayes: [Zhang et al. (017) and auto-regressive models (synthpop: Nowok et al. 2016) as well as undirected graphical models such as factor graphs (MST: McKKenna et al. 2019). For these models, data is usually discretized in order to facilitate efficient learning. Another is based on recently emerged deep generative models such as variational autoencoders (VAEs; Kingma & Welling, 2013 Rezende et al.) 2014) and generative adversarial nefworks (GANs; Goodfellow et al. 2014). Unlike graphical models, work on deep generative models has been mostly focusing on developing methods to directly model heterogeneous data, which are mixed-type data with different types of continuous (real, positive real, ett) and discrete variables (categorical, ordinal, etc), which includes specific pre-processing steps, neural network architecture design, improving training, etc (Xu & Veeramachaneni, 2018 Xu et al. 2019
Nazabal et al. 2020 Ma et al. 20200; for surveys, see Fan et al. (2020); Borisov et al. (2021).
Generative models for relational data Probabilistic relational models (PRMs) (Friedman et al. 1999; Getoor et al. (007)) is the most well-established approach to building distributions over relational data. /etoor et al. (2077) describes two ways of dealing with structural uncertainty but only with learning methods for structures, i.e. finding the best structures. While it is possible to extend these methods to samplers by using Markov chain Monte Carlo for sampling, applying them to datasets scale would be challenging. Mostly related to our work is Synthetic Data Vault (SDV) (Patki et al. 2016, Montanez et al. 2018), which is based on PRMs and considers the task of synthesizing relational data with links. However, SDV only models one-to-many relationships by recording the children count per row and generates one-to many links by sampling the number of children. Because SDV cannot handle many-to-one relationships, the so-called "multiple parents" problem occurs in certain scenarios (Montanez et al., 2018). For example, consider three tables
"With d increasing, samples from the dK distribbutions become more similar to the data but generating dK- graphs is increasingly computationally complex; luckily 2K -gaphhs are sufficient for most practical purposes Mahadeean et al. 2006). Also note that with d + co, d.K -sriis describe any given graph completely. In addition, from privacy perspective, a large d means high sensitivity in the d -eriies, which requires much noise to be added for achieving c-DP for given (Sala al. 2011).
3

---

Published as a conference paper at ICLR 2023
A - B C forming an one-mony- relationship. At generation time, SDV has to generate A and C' first and conditionally generates B given A and C. at which stage it is unclear whether the children counts in A or C' should be used. MMntanez et al. (2018) suggests to either randomly pick table for the conditional generation or to perform weighted averaging between parents. Another related work based PRMs is Ben Ishak al. (20T6), which describes generator for many-to-many data with links. However, the work only targets generating testing data-data used as test examples in a software engineering setup. Thus, the generator is learnable.
Random graph generation One line of work in this direction is built on the classic degree sequence problem, which the problem of finding some or all graphs with a given degree sequence (Molloy & Reed 1995). Mahadevan et al. (2006) introduces the notion of dKK -graphhs and studies generating them via classic random graph methods, such as the pseudograph or configuration approach (Molloy & Reed 1995: Aiello et al. 2000). As classic methods in general cannot correctly sample d.K -graphs with d 2 2, a few follow-up up works improves the sampling for these graphs (Stanton & Pinar 2012
Gjoka et al. 2013 2013). Unlike previous work that focuses on general graphs. [Boooojeni et al. (0117)
specifically considers sampling bipartite graphs that preserves the 2 -distributiinn Another line of methods, unlike above-mentioned methods that can generate arbitrary-sized graphs, can only generate graphs with the same size as the data graph, e.g. spectral-basee approach in Baldesi et al. (2018). or
expands it by a whole number, c.g. method based on fractal expansions from Belletti et (2019).
Differentially private SDG In terms of DP generative models, a few graphical models discussed above (PrivBayes, MST) are originally proposed in DP context. For deep generative models, there are two generic training algorithms that make models differentially private: differentially private stochastic gradient descent (DP-SGI) HUP-SSG:(bbr (bbadi et al. 2016) and private aggregation of teacher ensembles
(PATE: Papernot et al.) 2016 2018), leading methods such as DP-GAN (Xie et al. 2018) and
PATE-GAT (Jordon et al. 2018). Regarding random graph generation, Sala et al. (2011): Proserpio et al. (2012) consider the release of graphs in a differentially private manner based on d.K -generratssss.
To the best of our knowledge, there is no work specifically targeting differentially private synthesis of
bipartite graphs, nor previous work for differentially private synthesis for many-to-many datasets.
4 MODELING MANY-TO-MANY DATASETS WITH DIFFERENTIAL PRIVACY
In this section, we first discuss the challenges of building faithful generative models (Webb et al. 2018 for many-to-many datasets by studying possible factorization of the joint distribution (section 1.1). during which we also identify the limitations of the factorization that existing approaches are based on. Based on a novel factorization, we use methods from random graph generation, node representation learning and set representation learning develop new type of scalable generative model for many- to-many datasets section Finally, we extend the model to be (e, 8) -iiffferrentially private section 4.3 Also note that in this section, for brevity, we omit the model parameter 0 in py unless it is necessary.
4.1 FAITHFUL GENERATIVE MODELS FOR MANY-TO-MANY DATASETS
To simplify the discussion, we first focus on modeling bipartite graph and will later extend it to multipartite graphs. For the joint distribution p(U, L),,, where U, V are two tables with rows linked by edges in L, that we are interested in, considering the fact that the roles of U and V are exchangeable, there are only three possible factorization of the joint P(U, V, L) = Pyoin:
FACTORIZATION S p(U)p(L U)p(V L. P(U)p(V | U)p(L V)
FACTORIZATION E
FACTORIZATION A p(L)p(U L)p(V U.L)
Pjoint
Within all factorization, there are 6 sub-models in total to consider.
P(U) (the single-table model) can be any generative model for single table generation. p(L U) (the semi-conditional edge model) requires to generate edges based on one of the table- the row count generation used in Montanez et al. (2018) is in fact an example of such. However, a general case of this model can be computational challenging: For any subset of U, it requires checking if they together link to existing or new node in V.
p(V L, (the conditional table model) requires to generate each node in V based on the first table and all connections. As per node in V is connected subset of nodes in U via IL,
4

---

Published as a conference paper at ICLR 2023
((L) (BJDD matrix
cruheddingg
ambeddinng
AVI
Roggeggtor y
Aogpegatoo y
V
mode eneoder 3
mode eneoder y
mode umbbedding MU
bode embbeshling
MUIE)
(a) Learning (models can be fitted in parallel)
(b) Sampling (generation is sequential)
Figure 2: Illustrations of how the proposed framework works during learning and sampling phases. it requires to condition on a set of varied number of nodes for modelling, which can be done using aggregation function or a aggregator (Geetoor et al. 2007, Montanez et al. 2018). P(V TJ) (the table-conditional table model) requires to generate one table conditioned on another (while marginalizing all edges). This model can be computational challenge to implement. A potential work-around is to model the two-table joint p(U, V) directly by joining two tables and apply a generative model on the joined table. However, this could easily lead to table with an intractable scale. And perhaps more importantly, it is hard to undo this join operation from the synthetic data to recover individual tables in general [
p[L U, V) (the edge prediction model) predicts the existences of edges between node pairs and is essential probabilistic models used in many recommender systems.
p(L) (the edge model) requires to model the edges (i.e. the graph) unconditionally-thie is the type of random graph models that usually studied in random graph theory.
p(U L) (the edge-conditional table model) requires to generate one of the table given the
topology of edges. One way to achieve such conditioning is by using node embedding to condition on. This also related to node attributes generation/prediction in graph models.
As discussed, approaches from Getoor et al. (2007): Montanez et al. (2018) correspond to FACTORIZA- TION S and there is no easy way to extend p(L to general many-to-man case. FACTORIZATION also has the scalability issue p(V | U) (or similarly P(U V) as discussed. Our approach will then be based on FACTORIZATION A that does not have such concerns/limiiations.
Considering edges attributes So far our discussion assumes there are no edge attributes, which is not true in general, e-g. ratings in MOVIELENS. The way to deal with this is by adding an extra edge attribute model that is similar to p(L D, V) but generates edge attributes instead. One can use any edge prediction model for this purpose-raie rather than predicting the existence of edges it generates the edge attributes-aud and the corresponding generation step is performed after all other data is generated.
Extending to multipartite graphs For given datasets with multiple tables, we assume the links at table level are given. Thus we can impose an arbitrary order on the tables and generate the edges and tables in order; this is similar to how arbitrary order is imposed networks. Extra care needs to be taken for graph generation when generating graphs involving tables with more than one connection, which will be explained in section 4.2.1
random variables in Bayesian
4.2 RANDOM GRAPH GENERATION BASED MANY-TO-MA MANY SYNTHESIS
We now describe how to model the three distributions in our proposed factorization Pjoint = ((U) L)((V U.L.; p(L) in section 1.2.1 P(U L) in section 4.2.2 and p(V L, U) in section 4.2.3 Figure also provides an illustration of the learning and sampling process for the proposed method.
4.2.1 GRAPH MODELING VIA RANDOM GRAPH GENERATION
We consider using bipartite dK -generatoorr to model (LL) that take in a target BJD J and generate random graph satisfying this J. Boroojeni et al. (017) proves the existence of an algorithm for
As concrete example, suppose U has single column C₁ with continuous variable, V has another column C2 (with either continuous discrete variable) and L indicates every row in U is linked with two rows in V. After joining two tables, we will arrive with a table in which two columns C2, C2 in which there are duplicated elements in C: due to the one-to-n to-many relationship: it is also possible to undo the join operation on this real dataset. However, for any generative model that treats Ci as continuous variable, the probability of having duplicated elements in C1 is exactly O. which means any synthetic dataset would effectively giving dataset with one-to-one relationship between U and V, after undoing the join operation.
5

---

Published as a conference paper at ICLR 2023
sampling bipartite graphs with target BJD J, giving rise bipartite 2K -ggeerrttssss. The idea is to first generate a bipartite graph based on random pairing, after which the graph matches the 2K distribution but has potentially repeated edges. Then, rewiring process is performed to make the graph simple-a a graph is called simple if there is no loop or multiple edges (West et al. (001). Boroojeni et al. (2017) shows that such rewiring process exists and can always produce graph with the target BJD. Since the prescribed algorithm of rewiring in Boroojeni et al. (017)) contains a few mistakes/typos, we present corrected version in algorithm
appendix B
To complete the description of pa (IL), we also need to define how to obtain J that bipartite algorithm I take in. For this, we draw samples from PJ with a preseribed number of edges. However, as this might invalidate the input to algorithm 17 which may cause infinite loops in rewiring, we stop the rewiring process after a predefined maximum number of iterations. To this end, sampling from J together with algorithm define po (T.) through its generative process, where @ is the BJDD matrix PJ.
"Backward compatibilitty" of the graph generator One consideration taken into account while selecting the model for p(L) was "backward compatibility" to one-to-men ma-y and many many-to-one to-one prob- lems. This refers to the cases where if the data graph contains only one-to-many relationships, the generated graphs shall do so. The 2K 2K -generator indeed satisfies this property while, in contrast, spectral-base based graph generation methods such as Baldesi et al. (20T8) usually fail hold it.
Learning and sampling Learning of this model only involves computing the BJDD matrix from the data graph; if table is involved in multiple edges, the joint distribution of all degrees per node is learned. Sampling from the model is defined by sampling from PJ followed by algorithm]
4.2.2 CONDITIONAL MODELING VIA NODE EMBEDDING
We now discuss how to model upper nodes U conditioned on edges L. This distribution essentially models set of nodes given topology, which can be dealt with the use of node embedding as:
P(U L)- P(r' B(L,
(1)
where the node encoder 3 computes node embedding of node i in graph L; its range is ran( RRH,, where H3 is the dimension of the node embedding. Intuitively speaking, 3 computes the representation of the local topology of node in L; if the representation is rich enough, nł, and nž are conditional independent given the representation, for any i. As such, once given B, this distribution can be modeled by any existing conditional generative model. A few candidates of such B are:
1. Node statistics: d-step neighbour count (number neighbours of distance d) can be used. As simple example, d 1 means using node degrees as 1d embeddings. It can be generalised to use a collection of counts with H3 different d. giving to an embedding of size H3.
2. Node embedding: Methods to learn node embedding such as DeepWalk (Perozzi al. 2014 and node2vec (Grover & Leskovec 2016) can also be used as 3.
Addition discussion independence assumptions behind equation can be found in appendix
caan
Learning Learning of this model only involves learning the conditional generative model. There no learning for either node statistics or node embedding (for the two approaches mentioned above).
4.2.3 CONDITIONAL MODELING VIA SET EMBEDDING
Consider a node ny E V with neighbors ne(n.) C U. It is easy to see that, given ne(n.). ny is conditionally independent with any other ni, E V. Thus, we have p(V L, UJ II,,ev ev p(n. ne(n.)), where p(n. ne(n.)) is conditional distribution whose condition is multiset a set that allows repeated elements. Without imposing any order on ne(n.), one way to condition on this through a fixed-size set embedding computed by aggregator 7, which leads to model
p(V L, = II. ey p(n (ne(n))))
$ Algoritthm I assumes two conditions for the input J: J[. [ S (,, J Jj. and (ii) the degree sums for upper and lower nodes are the same (which would be true as long as Σ, J j/.. integer for all i and E, ji.. is integer for all j) (Boroojeni et al. 2017)

---

Published as a conference paper at ICLR 2023
Equation 2 requires aggregator y (U) + R where (ow(U) is the power of UJ and H, is the dimension of the set embedding. If the set embedding of neighbours from y is rich enough, any two nodes n, and ni, are conditionally independent given the corresponding set embeddings. A few candidates of such y are:
1. Summary statisties: count, sum, n-th order moments, q-percent quantiles, etc. can be used. both count and sum are used and d different moments and quantiles are used, the total dimen- sion of the embedding is D + D + x D + x for nodes with D D-dimensional attributes. also fit a distribution on the set and use the distribution parameters as the embedding. MMntanez et al. (2018) suggests using a Gaussian copula; for nodes with D-dimensional attributes, the dimension of the embedding is D + D2
2. Distribution parameters: One
3. Set embedding: The deep sets architecture (Zaheer et al. 2017) is specifically proposed to produce set embedding. It contains two neural networks, to compute an embedding for each element in the set and one to aggregate the element embeddings into a set embedding.
Addition discussion on independence assumptions behind equation 2 can be found in appendix C
Learning Learning of this model involves learning the set embedding (if it option 3) and learning the conditional generative model. Learning of the deep sets models can be difficult depends on the choice of the conditional generative model. However, if this model is also implemented by neural networks, one can learn in an end-to-end fashion using the learning objective of the conditional generative model. As there is no existing method to train deep sets in an unsupervised manner, cannot be used with classic models like Bayesian networks. We leave that to future work.
4.3 ESTABLISHING DIFFERENTIAL PRIVACY
We now describe how to extend the learning of each sub-model in pu V) = Pe, (L))p,, (U L)po, (V) L. U) such that the learned parameter (6,, 02. 03) with corresponding privacy budgets G1, C2, and c3 (c1 + C2 + C3 = <) is (c, 5)DDP becomes (c, 8)-DP by Theorem. [ (defined below). Note that we assume the required privacy budgets for each component in each sub-model are given; how to optimally spend the budget is a question for future work that is out of the scope of this paper.
Pe, (L) with 6 For pei 0, is the BIDD matrix PJ. As per the definition in section 2 we are interested in masking the presence of absence of single node of either U or V. which is stronger privacy notion than edge protection. To do so we follow the strategy in Sala et al. (20TT): Proserpio al. (2012) that uses the Laplace mechanism to make PJ c-DP. The main difference here is that we are operating on bipartite graphs instead of general graphs. Specifically, after measuring the BJD matrix
J from data graphs, to achieve e-DP, we add noise following Cap( Sig where Sig 4 max(d4, dj) to the i-th row, j-th column entry of (Sala et al. 2011 Proserpio et al. 2012).
Ped (U L) with E2 For Pe,. O2 consists the parameter of the underlying generative model for the conditional, for which we choose some existing DP ones and follow their learning algorithms.
Pe, (V U) with 63 For pe,, Bg consists both the parameter of the set embedding model as well as that of the underlying generative model for the conditional. For the former, if such embedding or from Gaussian copula (the second option in section 4.2.3), there is no learnable parameter for the node embedding model; if such embedding is based on the deep sets architecture, which is only defined when it can be trained end-to-end with the generative model, we use DP-SGD (Abadi et al.) 2016) for training. For the underlying generative model not trained jointly, we choose some existing DP ones and follow their learning algorithms.
is fre-fixed (referred as "statistics" in section
Theorem 1 ((c, 6)-DP for Po with A). Given the factorization, po (U, V, L) = po, (L))po, (U L)peg (V) | IL, UJ, as well as pe, (LL) being (E1, O)DP, pe, (U L) being (ez, 8)-DP, and pe, (V I, U) being (ea, dD- by sequential composition it follows that po (U, V, is (EI +
should be noted that the proposed formulation is flexible enough to allow for the privacy protection of the nodes from only one of U and V but not the other. For instance, if we choose to protect only U, we can set E3 = do when learning Po. (V L, U) and d, = 0 for all j when learning Po, (L), making the overall synthetic data generation process (c,0)-DP (e1 + 62 =).
7

---

Published as a conference paper at ICLR 2023
5 EVALUATION
Dataset We consider the MOVIELENS in our evaluation. MOVIELENS is a dataset that contains users' ratings to different movies (Harper & Konstan 2015). The user and movie tables have their own attributes such as user ages and movie genres and have a many-to-many relationship through existing ratings. We choose MOVIELENS as is commonly used datasets to study graph properties (Harper & Konstan, 2015:
Baldesi et al. 2018 Belletti et al. 2019).
Pre-processing We discretize all features into maximally 30 bins. Note this discretization step is optional: for our study, it is meant to make modeling and evaluation easier, which is an orthogonal consideration to the main point of the study which is to assess the performance of many- toyy-toomn to-many modelling. Also note do not use any privacy budget during pre-processing by assuming all information needed are public, which is again a separate concern that is out of the scope of this paper.
5.1 QUALITY OF MANY-TO MANY-TO-MANY MODELING
In this section, we evaluate the quality of the proposed model in terms of synthetic data similarity. We consider set of baselines well as two realizations of the proposed method, which we explain next.
Baseline We consider SDV Montaneez et al. 2018) as the baseline method in our evaluation B SDV decomposes many-to-many relationships into multiple one-to-many ones and has the "multiple parents" (discussed in section 3) To handle this, instead of randomly picking one table as the parent as suggested by Montanez et al. (2018). we experiment both options and report the one with better results.
Two model instances from the proposed framework The proposed framework enables range of new generative models with different options in each submodel detailed in section 4.2 In this evaluation, we focus two typical ones built on different single table models: Bayesian network with the network building method from Zhang et al. (2017), referred as BN, and an autoregressive model in which each conditional is modelled by a neural network, referred as NeuralAR. The two realizations are then (i) a classic non- -orrameettticc approach in which the single table models used are BN, referred as Bayesian many-to-man many (BayesM2M) and (ii) a neural-based approach which the single table models used are NeuralAR, referred as neural many-to-many (NeuralM2M), In both realizations, for pTL), we use the 2K -enerator.. In M2yesM2M, for p(U L), we use node statistics with d-step counts for d = 1,2; for p(V II, U). we use summary statistics with count, sum, n-th order moments for n = 1, 2,3 3 and q-percent quantiles for q = 0.25, 0.5, 0.75. NeuralM2M, for U | IL). we use node2vec to extract node embeddings; for p(V L, U), we use the deep sets architecture (Zaheer et al. 2017) to consume a set of node (equivalently a set of rows).
Metries As the primary goal of SDG is to mimic the distribution of the real data, we consider three sets of metrics based on distributional similarity to evaluate the generation quality. The first set con- sists metrics that specifically evaluate the quality of relationship generation, which are one minus the total variation distances between the dKK -iistribbuuus of real and synthetic data for d = 1, 2 (bounded between and 1). The second set consists the pairwise mutual information (MI) similarity for each ta- ble to evaluate the quality of individual tables. For pair of real and synthetic tables, we first compute the normalized M Wbetween each pair of columns in each table; for tables with m features, this gives a pair of m X y matrices. The MI similarity is then defined as the average Jaccard indices between each pair of entries. Compared to alternative metrics such as f-divergences, this metric is bounded between O and thus is easy to interpret. The third set consists the metrics capture correlations between table pairs rooted in their many-to-m -tamyyy relationships, i.e. cross-table similarity. For each pair, we join the tables by their links into single table and compute the pairwise MI similarity for each pair between two tables; for a pair of two tables with m and n features, this gives a pair of y x n matrices. The MI similarity is then defined as the average Jaccard indices between each pair of entries. To help understand our metrics, we provide detailed definitions with step-by-step examples in appendix D
Table I summarizes the main results from experiments with the above setups. Compared SDV, both
'e use the official implementation of SDV at g hub. www/sc//ccccc... deettrddee//ee dww/ddd/////eeee /DV in our experiments. For discrete X.Y, we have Y) < min(H((X) H(Y)). Thus normalized MI is defined as T(X;Y) mi)mm/HHmiiX))) H(Y)), which bounded between O and 1.
8

---

Published as a conference paper at ICLR 2023
Table 1: Quality of many-to-many tany modelling MOVIELENS. All metrics are bounded between O and with being the theoretical maximal value, i.e. higher the better. Numbers are mean and standard deviation based on 5 runs with different random seeds.
Degree Similarity
Mutual Information Similarity
Method
Marginal
Joint
U
V
Table
SDV
0.867 = 0.003
0.614 0.012
0.547 + 0.033
0.334 + 0.017
0.440 = 0.035
BayesM2M
0.756 + 0.041
0.345 - 0.016
0.561 - 0.031
0.955 = 0.016
0.634 0.028
NeuralM2M
0.846 + 0.045
0.562 + 0.031
0.613 + 0.016
realizations of the proposed method obtains better scores in terms of graph similarity (marginal and joint degree similarity). This supports our choice of using random graph generation the starting point of the whole generative process. Among two realizations, NeuralM2M has a better score in MI similarity for U, indicating that the node representation from node2vec contains more information than simple-minded node statistics. On top of this, NeuralM2M also has larger the gain/different between MI similarity for U and V than M2y,sM2M,, indicating that deep sets architecture learn better set representation than fixed summary statistics. As a result of using random graph generation and learnable neural-based representations, NeuralM2M has the best cross-table similarity. We present more results on further metrics in appendix D
5.2 PERFORMANCE UNDER DIFFERENTIAL PRIVACY CONSTRAINTS
For the two typical realizations of the proposed framework, we now evaluate how the generation qual- ity of their differentially private variants changes with different privacy budgets. We focus the cross- table similarity in this section as it is the most comprehensive metric for many-to-many modelling.
Privacy budgets For both realizations, we vary in {0.1, 10.0, 1, 000.0, oo). For NeuraIM2M, in addition set 5 = 1 x 10-5 and use sensitivity (gradient clipping norm) of 5.0 in DP-SGD.
Figure 3 summarizes the main results from experiments with the above setups. As it can be seen, even though NeuralM2M performs well in a non-DP setup, its performance drops quickly with even a slightly smaller privacy budget. In comparison, BayesM2M has a better privacy-similario trade-off. The main reason behind this is that the components in NeuralM2M rely on iterative training in which noise is added per iteration in order to establish differential privacy, making it hard to optimally spend the privacy budget or to obtain a tight DP bound. On the other side, most of the component in BayesM2M are pre-fixed and BNs can achieve DP by only adding noises to the measurement (i.e. counting for discreized data) of each table column.
0.6
BayesM2M
similarity
NeuralM2M
0.5
0.4
Inf
1000.0
10.0
0.1
Figure 3: Cross-table similarity with pri- vacy budgets e on MOVIELENS
DISCUSSION AND CONCLUSION
Limitation The overall quality of the proposed framework depends the choice of random graph generation methods. In this paper, we mostly focus on the 2K-generator that can generate arbitary-sized graphs but at its best matches the -distribbuus of the real data. Some other graph generation methods such as Baldesi et al. (2018), Belletti et al. (2019) can capture more graph statistics but can only generate graphs with the same size as the data graph or expands it by whole number.
Societal impacts On the positive side, the proposed method improve SDG for many-to-many data and can be used to release such data with DP guarantees, protecting the privacy of relevant individuals. However, as all generative model-based SDG methods, the synthetic data may be different from the real one in certain ways, causing potential disparity issues.
To conclude, this paper studies the challenge of building faithful generative models for many-to-many datasets and present a novel generation framework based on random graph generation, node and set representation learning. The proposed framework is demonstrated to be better than its closest competi- tor SDV in terms of the generation quality on the widely-studies MOVIELENS dataset. We also study the behaviour of proposed model under different DP constraints, highlighting potential future works.

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
William Aiello, Fan Chung, and Linyuan Lu. random graph model for massive graphs. In Proceedings of the thirty-second anmual ACM symposium on Theory of computing, pp. 171-180, 2000.
Luca Baldesi, Carter T Butts, and Athina Markopoulou. Spectral graph forge: Graph generation targeting modularity. In IEEE INFOCOM 2018-IEEE Conference Computer Communications, pp. 1727-1735. IEEE, 2018.
Francois Belletti, Karthik Lakshmanan, Walid Krichene, Yi-Fan Chen, and John Anderson. Scalable realistic recommendation datasets through fractal expansions. arXiv preprint arXiv:1901.080 2019.
Mouna Ben Ishak, Philippe Leray, and Nahla Ben Amor. Probabilistic relational model benchmark generation: Principle and application. Intelligent Data Analysis, 20(3):615-635, 2016.
Vadim Borisov, Tobias Leemann, Kathrin SeBler, Johannes Haug, Martin Pawelezyk, and Gjergji Kasneci. Deep neural networks and tabular data: A survey. arXiv preprint arXiv:2 10.01889, 2021.
Asma Azizi Boroojeni, Jeremy Dewar, Tong Wu, and James M Hyman. Generating bipartite networks with a prescribed joint degree distribution. Journal of complex networks, 5(6):839-857, 2017.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor Comput. Sci., 9(3-4):211 1-7077, 2014.
Ju Fan, Junyou Chen, Tongyu Liu, Yuwei Shen, Guoliang Li, and Xiaoyong Du. Relational data synthesis using generative adversarial networks: A design space exploration. Proc. VLDB Endow. 13(12):1962-1975, jul 2020. ISSN 2150-8097 doi: 10.4477834077903447332 URL https
7/doi orgiioorg/000
3407802]
Nir Friedman, Lise Getoor, Daphne Koller, and Avi Pfeffer. Learning probabilistic relational models. In IJCAI, volume 99, pp. 1300-1309, 1999.
Lise Getoor, Nir Friedman. Daphne Koller, and Benjamin Taskar. Probabilistic relational models. Introduction to statistical relational learning, 8, 2007.
Minas Gjoka, Maciej Kurant, and Athina Markopoulou. 2.5 k-graphs: from sampling generation. IEEE, 2013.
Minas Gjoka, Bálint Tillman, and Athina Markopoulou. Construction of simple graphs with target joint joint degree matrix and beyond. In 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 1553-1561. IEEE, 2015.
Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 2016.
Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), dec 2015. ISSN 2160-6455. doi: 10.1145/2827872. URL 1145/2827872
James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. Pate- gan: Generating synthetic data with differential privacy guarantees. In International conference learning representations, 2018.
10

---

Published as a conference paper at ICLR 2023
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6990, 2014.
Diederik P Kingma and Max Welling, Auto-encoding variational bayes.
arXiv preprint
arXiv:1312.61 2013.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in Neural Information Processing Systems, 32, 2019.
Zinan Lin, Alankar Jain, Chen Wang, Giulia Fanti, and Vyas Sekar. Using gans for sharing networked time series data: Challenges, initial promise, and open questions. Proceedings of the ACM Internet Measurement Conference, IMC 220 pp. 464-483, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450381383 doi: 00.14453419994444236643 URL
Chao Ma, Sebastian Tschiatschek, Richard Turner, José Miguel Hemándezz-oobto, and Cheng Zhang. VAEM: deep generative model for heterogeneous mixed type data. Advances in Neural Information Processing Systems, 33:1 13:7-12311227, 2020.
Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat. Systematic topology analysis and generation using degree correlations. ACM SIGCOMM Computer Communication Review, 36(4): 135-146, 2006.
Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphical-model based estimation and inference for differential privacy. International Conference on Machine Learning, pp. 4435- 4444. PMLR, 2019.
Michael Molloy and Bruce Reed. A critical point for random graphs with given degree sequence. Random structures & algorithms, 6(2-3):161-180 1995.
Andrew Montanez al. SDVV open source library for synthetic data generation. PhD thesis, Massachusetts Institute of Technology, 2018.
Alfredo Nazabal, Pablo M Olmos, Zoubin Ghahramani, and Isabel Valera. Handling incomplete heterogeneous data using VAEs. Pattern Recognition, 107: 2020.
Beata Nowok, Gillian M. Raab, and Chris Dibben. synthpop: Bespoke creation of synthetic data in Journal of Statistical Software, 74(11):1-26, 2016. doi: 10.186377jss.0044.11. URL
https: wwwpw//wwwww..//mm jstatsoft org. http:///........aee////////////r
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.05755. 2016.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. arXiv preprint /802: 2018.
N. Patki, R. Wedge, and K. Veeramachaneni. The synthetic data vault. In 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pp. 399-410, Oct 2016. doi: 10.1109/DSAA.2016..20
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Davide Proserpio, Sharon Goldberg, and Frank McSherry. A workflow for differentially--rrvall graph synthesis. In Proceedings of the 2012 ACM workshop on Workshop on online social networks, pp. 13-18, 2012.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference on machine learning. pp. 1278-1286. PMLR, 2014.
11

---

Published as a conference paper at ICLR 2023
Alessandra Sala, Xiaohan Zhao, Christo Wilson, Haitao Zheng, and Ben Y Zhao. Sharing graphs using differentially private graph models. In Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference, pp. 81-98, 2011.
Isabelle Stanton and Ali Pinar. Constructing and sampling graphs with prescribed joint degree distribution. Journal of Experimental Algorithmics (JEA), 17:3-1, 2012.
Yuchao Tao, Ryan McKenna, Michael Hay, Ashwin Machanavajihala, and Gerome Miklau. Benchmarking differentially private synthetic data generation algorithms. arXiv preprint arXiv:21 2021.
Allan Tucker, Zhenchen Wang, Ylenia Rotalinti, and Puja Myles. Generating high-fidelity synthetic patient data for assessing machine learning healthcare software. NPJ digital medicine, 3(1):1-13, 2020.
Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions sets. In International Conference Machine Learning, pp. 6487-6494. PMLR, 2019.
Stefan Webb, Adam Golinski, Rob Zinkov, Tom Rainforth, Yee Whye Tch, Frank Wood, et al. Faithful inversion of generative models for effective amortized inference. Advances in Neural Information Processing Systems, 31, 2018.
Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv: 1802.0669, 2018.
Kai Xu, Rajkarn Singh, Marco Fiore, Mahesh K. Marina, Hakan Bilen, Muhammad Usama, Howard Benn, and Cezary Ziemlicki. Spectragan: Spectrum based generation of city scale spatiotemporal mobile network traffic data. In Proceedings of the 17th International Conference on Emerging Networking EXperùments and Technologies. CoNEXT 1,, pp. 243-258, New York, NY. USA, 2021. Association for Computing Machinery. ISBN 978 97719993999 (ttLhhtp::: htRLhhttss///di..oooot /tt../////....111445551313131111 . 3494844
doi: 0114443348993.34444888
Lei Xu and Kalyan Veeramachaneni. Synthesizing tabular data using generative adversarial networks
arXiv preprint arXiv: /81 I.I 1264, 2018
Lei Xu, Maria Skoularidou, Alfredo Ireesta-Iffate,, and Kalyan Veeramachaneni. Modeling tabular data using conditional GAN. Advances in Neural Information Processing Systems, 32, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Jun Zhang, Graham Cormode, Cecilia M Procopiue, Divesh Srivastava, and Xiaokui Xiao. Privbayes: Private data release via bayesian networks. ACM Transactions on Database Systems (TODS), 42 (4):1 41, 2017.
Alexander Ziller, Dmitrii Usynin, Rickmer Braren, Marcus Makowski, Daniel Rueckert, and Georgios Kaissis. Medical imaging deep learning with differential privacy. Scientific Reports, 11(1):1-8 2021.
A HOW GENERATIVE MODELS ARE USED FOR SYNTHETIC DATA GENERATION
Figure 4 provides a flow chart to demonstrate the high-level workflow of generative models as applied to synthetic data generation in practice. As a more concrete example, suppose the real data is a many-to- -o-nnyy dataset that contains user reviews of various movies: It contains table of users, table of movies and a table describes how each user rates a movie (in a many-to-many fashion as a user could rate multiple movies and movie can be reviewed by multiple users). Such dataset may
12

---

Published as a conference paper at ICLR 2023
private anviromment
generalive model
synthatic data
downstream tacks dais anelysis model training
generative
DP syntheiic data
Figure 4: How generative models are used for synthetic data generation. To begin with, the real data stays in a private environment and cannot be shared with a third party due to privacy compliance. Depending whether not the synthetic data needs to be DP (according compliance), the use of the generative model goes through a different route. If no DP is required, we can fit generative model on the real data, both of which needs to stay in the private environment. Then synthetic data is sampled from the model, leaves the private environment and can be shared with a third-party to perform any downstream tasks of interest. If DP is needed for the synthetic data, fit DP generative model on the real data and the model can leave the private environment as the model is also DP. The rest of the process follows similarly that of the non-DP route.
contain sensitive information such as user information (which may contain personally identifiable information) and how users rate movies (a user may identified by how many movies he or she rated). The two routes of how generative models can be used to provide a synthetic copy of the data resolves this problem, especially the DP route. Downstream tasks such as data analysis (c.g. analysis of user behaviour) model training (c.g. to train recommender systems) can then be performed on the synthetic data that shared publicly by any third-pan -artt.
B BIPARTITE 2K GENERRATORR
The complete algorithm of the bipartite 2K -generrasssss from Boroojeni et al. (0177) with corrections is given in algorithm The algorithm consists two parts. The first part (Line 4 to Line 18) is called random pairing. works by first creating stubs for each node based on its degree; the stubs for node with index and degree d is list .,..., i). After stubs for all nodes created, they
randomly paired based the joint degree distribution/counts, This is simply done by enumerating the joint degree count: At each iteration for a pair of degree d1, d2, we randomly sample di stubs with degree dj and d2 stubs with degree d2 and pair them accordingly. This step ensures the joint degree distribution matches while with potential repeated edges. The second part (Line 20 to Line 52) resolves repeated edges while preserving the joint degree counts. [Boroojeni et al. (2017) shows that there are only two cases how such repeated edges could appear and how to resolve each of them accordingly with the joint degree counts unchanged. Note that the algorithm presented Boroojenn iet al. (0017) contains several mistakes even though their proof is correct; algorithm [ based on our own realization of situations in the proof but essentially the same algorithm.
C INDEPENDENCE ASSUMPTIONS
Node embedding models As mentioned in section 4.2.2 from 3 is rich enough such that any two nodes Thy and ra!, are conditional independent given the representations. This is more likely be true node embedding (option 2 above) is used. However, node statisties (option 1) is still appealing due to its simplicity and computational efficiency thus there exists an inherent fddlity-compuration trade-off between these two modeling choices.
equation only holds if the representation
Set embedding models As mentioned in section 4.2.3 equation 2 only holds if the embedding from y is rich enough such that any two nodes n, and n. are conditionally independent given the corresponding set embeddings. This can be made true if set embedding (option 3 above) is used with a large enough dimension (Wagstaff' et al.) (219)) This could be potentially made true if distribution parameters (option 2 above) is used, if the distribution family is flexible enough. However, summary
13

---

Published as a conference paper at ICLR 2023
statistics (option is still appealing due to its simplicity and computational efficiency thus there exists an inherent fideltty-compuattinn trade-off between these three modeling choices.
D DETAILED EEXPLANATION OF METRICS USED IN SECTION 5
In section 5 we used set of metries that are not commonly used for evaluation. To repeat, the two reasons we prefer these metrics are (i) they are bounded between 0 and and (ii) they are easy to compute once the data is discretized, e-g. not requirement for training classifier for density ratio estimation in computing f-divergences. We now provide more formal description of these metrics.
D.1 DEGREE SIMILARITY
Let p. q be the probability vectors representing the 1K 1K--dstribution (with the same support) of the real and synthetic graphs. The marginal degree similarity is defined
9)
=1
where TV is the total variation distance and pt, q are the i-th element p.
Let P. Q be the probability matrices representing the corresponding -didistriitttinn (with the same support). Similarly, the joint degree similarity defined as
TV 2
Q) =
Pay
where Pijs Qzy are the i-th row, j-th column entry of P.
As (V, E [o, 2]. it can be easily shown that the two above degree similarity metrics are bounded by and 1 with 1 being the maximal and best value.
D.2 MUTUAL INFORMATION SIMILARITY
Let X, Y be two datasets with the same number of discrete columns/features (m)) For each dataset, we compute the normalized mutual information between each pair of columns, giving the pairwise MI matrix.
The normalized mutual information between two random variables X, Y is defined as H(X) + H(Y) H(X, Y)
MI(X,
nMI(X,Y)= == min(H(X), H(Y)}
min (H()), H(Y))
where MI refers to the mutual information and Н refers to the Shannon entropy. This quantity is bounded by 0 and 1 due to (i) the positivity of entropy and (ii) the inequality below
H(X, Y) 2 max(H(X),
property of joint entropy multiply by add marginal entropies simplification
H(X, Y) S min(-H(X). -(Y))
H(X) + H(Y) - H(X, Y) < H((X) + H(Y) + min(-H(XX, -()--H(X),-H()) MI(X,Y) min(H(X)..H(T))
Then the pairwise MI matrix, c.g. M for X can be defined by its i-th row, j-th column entries Mij
Mi = nMI,X,,
where X,, Xj the random variables for the i-th and j-th columns of the dataset X. As the dataset is assumed to be given in discrete, the entropy each column and the joint entropy a pair of columns can be easily estimated by first estimating the empirical probabilities followed by the definition of Shannon entropy.
Let M. N be the pairwise MI matrices for X, Y respectively, the MI similarity is then defined
Σ
J(Mag No²)
m
14

---

Published as a conference paper at ICLR 2023
Table 2: Quality of many-to-many tany modelling MOVIELENS. All metrics are bounded between O and with being the theoretical maximal value, i.e. higher the better. Numbers are mean and standard deviation based on 5 runs with different random seeds.
Total Variation Similarity V
Method
U
Cross-Table
SDV
0.855 + 0.032
0.937 0.001
0.624 = 0.004
B2yesM2M
0.758 + 0.037
0.951 + 0.027
0.742 0,038
NeuralM2M
0.800 + 0.061
0.926 + 0.012
0.745 0.046
Table 3: Quality of many-to-many modelling MOVIELENS. All metrics are bounded between 0 and with being the theoretical maximal value, i.e. higher the better.
Recommender System
SDV
BayesM2M
NeuralM2M
Real Data
Fl score
0.522
0.507
0.591
0.591
where Mj,, Nig the i-th row, j-th column entries accordingly and J is the Jaccard index defined as
((A, B) min A, B} [ B}
easy to see this metric bounded by 0 and with being the maximal and best value.
Cross-table MI similarity To compute the cross-table MI similarity score, for pair of real tables X1, X2 and synthetic tables Y1, Y2, we first join (join as in relational algebra or databases) the two table pairs (X,, X2 and Y1, Y2) into X and Y by the graph/links between them. Then, we simply follow the MI similarity described above to compute the score.
D.3 TOTAL VARIATION SIMILARITY
Tao et al. 2021) uses similar metric as in appendix D.2 where the pairwise mutual information between marginals is replaced by pairwise total variation distance (which is between 0 and as defined by Q) = Σxex P = z) - Q(X' = r2 2 for two discrete distributions P, Q over domain X). We also report this metric with the only modification being that we use 1 - TV(P, Q) instead, which makes the number higher the better for consistent interpretability
the mutual information similarity (while still being bounded between 0 and 1). We refer this metric as total variation similarity. Table[]showw the results. Note that even the single-table performance, which mainly dependent on the choice of single-table models, of ours is slightly worse than that of SDV (column U) or similar (column V), the cross-table performance of ours still better with a noticeable margin (column Cross-Tablee This is a strong indication of the benefit of our proposed many-to-many modeling approach.
D.4 RECOMMENDER SYSTEM
Finally, we train recommender systems on both real and synthetic datasets and compare their performance on a set aside test data. We report the results in Table We see that both SDV and BayesM2M experience similar drop in performance compared to the recommender trained on the real data. For BayesM2.,, we conjecture that the drop is because that the maximum number of parents is limited to 2, meaning no higher-level correlation is captured. Similar explanation can be made to the drop for SDV, where the single-table model (Gaussian copula) can only capture pairwise correlations. On the other hand, NeuralM2M achieves the same score as than the real due to the more powerful single-table model well as many many-to-man -t-mmny modeling framework. This is perhaps surprising, as the the recommender system trained on the real data observes (almost) the same movies in the fitting and predicting steps while the M2u one trained entirely on synthetic movies.
15

---

Published as a conference paper at ICLR 2023
E REPRODUCIBILITY
E
CODE
Our implementations of BayesM2M and NeuralM2M are available githgg.thhhccm com hazy/ m2m
F.2
EXPERIMENT DETAILS
In this section provide some experimental details that missing in section 5
Bayesian networks For BNs, we set the number of parents to be 2. The network building algorithm follows (Zhang et 2017) exactly.
Neural autoregressive models For NeuralARs, the architecture for each classifier is as follows
1. Each discrete variable is passed to an embedding layer with an embedding size of 20, after which all embeddings are concatenated, giving a imput embedding of size de
2. (Optional) When the deep sets architecture is used, each node is passed to a linear layer with output size 10 (i.e. node embedding size), then summed (i.e. summation the aggregation function) and passed to linear layer with output size 50 (i.e. set embedding size). We also overload the notation de by this set embedding size this step is performed.
3. The input embedding is passed to multi-layer perceptron of de ReLyy 50 ReLy 50 Softmax do where ReLU refers to the rectified linear unit activation function, Softmax refers to the he softmax function and do is the output dimension, equal to the number of unique values of the output features.
Data is split by 80/20 into training and validation sets. All training is done using the ADAM optimizer (Kingma & Ba 2014) for maximally 1, 000 steps with learning rate of 1 x 10-3 and a batch size of 500. We also use learning rate scheduler with the sine function with exponential amplitude decay with minimal learning rate of 2 10-4 and 5-epoch periodicity Finally, early training is used based on the loss computed on the validation set: there is no loss drop for epochs, the training is early stopped.
node2vec We use the Julia implementation of node2vec 10
We keep all default parameters except set- ting the number of walks to be 10, the walk length be 100, p = and an embedding size of 20.
Privacy accountant We apply a simple-minded way to spread the privacy budget. First, the privacy budget is evenly split among three sub-models. Second, within each sub-model, the budget is further evenly split to each component. For BNs, it means the network building and counting. For NeuralARs, we simply record the number iterations used for training per classifier in the non-private version and evenly spread the privacy across all iterations. Note this (assuming the number of iterations per classifier known) is for evaluation purpose only and by no means this strategy is an optimal way to spend the privacy budgets.
E.3 TOTAL COMPUTATION RESOURCES
All experiments are conducted on an Amazon EC2 instance of type c5. cx.4xlarge with CPUs only.
All neural networks are implemented using http://///athhhb.oo////tt//////
9This is done using the Si SinExp from ParameterScchedllers]] http::/dhcc....t..t.pass/stttaaa Parametertt erSchhculee ler.. 11). 10The code is available http://:/ggthhbb.co////
16

---

Published as a conference paper at ICLR 2023
Algorithm Bipartite 2 2K' -enerator (Boroojeni al, 2017 corrected)
Input: BJD J with supports du d,
2: Output: Edges L
3: Initialise L= 0
Initialise edges as empty set
4: # Part 1: random pairing
5: Su f S. x
> Initialise stubs as empty lists
6: Compute degree sequences u, from J
7: for in E E,....,|uul |,],, E 1,,... 1,...,ufi do
8: Append in Su
9: end for
for by L..... [v), k I,..., v(ūe] do
11: Append by to S.
end for
13:
ior........ dul.j E |d,| do
14:
k J
15:
Randomly pop & node indices { from Su s.t. the corresponding nodes n2(()) has degree
duli]
16:
Randomly pop & node indices { ( from s, s.t. the corresponding nodes ni(()) has degree
d.(j]
17:
Add edges {(t 2) to L
18: end for
# Part 2: rewiring process (corrected version)
20: L, t repeated edges in IL
> Repeated edges to resolve
while I,
empty do
22: Randomly pop edge (Hu, in) from Ly
Th f- ((aa).70 ny <- n(i,); n(y +- Thes ny f- Thy
24:
U' nn. deg(n.)) deg(n.)) {na)
25:
V + {n deg(nz)) = deg(nw) [w)] {nu)
26:
if |U|| 0 then
27:
ni <- uniform sample from {ni, E V \ no(n()) ne(n()) \ (c(nz) * 0} then
28:
else if |
29:
Th -- uniform sample from {n/, E U') ne(n") ne(n())) ne(n).) ) + 0} else if IL, ((v E V U' ne(n()) ne(n.) of and ne(n',) \ ne(nu)) # 0] +
30:
then
(n/g,n()) n2,,) + uniform sample from 1'2 else if 4/" : {n', V ne(n")) } @ then
32:
33:
n', < uniform sample from 771
34:
elset Boroojeni et al. (2017) proves that in this branch the set to draw samples is non-empty.
35:
ni uniform sample from {n(, U') ne(n())
36:
end if
37:
if ni, n., then
b Case
38:
n +- --niform sample from ne(n.. ne(n)))
39:
Remove edge (i(n() (((nn)),i((n)) (m)))) from L
40:
Add edges {(i(n.), i(n))), i(n()) to IL
41:
else n', n, then
D Case
42:
Rw + uniform sample from ne(n(,) ne(nw)
43:
Remove edge (i(n()), i(n.)) from L
Add edges ((((n))) i(n.))) (i(n.w) ((n))) to L
45:
else
D Case
Top f uniform sample from ne ne(n)) ) ne(n.)
47:
nh f- uniform sample from ne(n ) ne ne(n.)
Remove edges ((i(n',) i(n (i(m)) ((x4)) from L.
49:
Add edges (i(m..) i(nww) )), (i(n) ((n)))) (i(n)), to
50: end
51: I, repeated edges in L
52:
end while
53: return IL
17


Reviews:
[{"review_id": "iUFFVyKdYN", "reviewer": "Reviewer_62xs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper consider the problem of synthetic data generation by fitting a generative model to the dataset and then drawing samples from it. The authors consider tabular datasets with many to many relationships.\nThe key idea that the authors propose is to decompose the likelihood in a certain way and then model each of the factors using appropriate techniques such as sampling structured graphs and constructing graph embeddings. The paper also presents a differentially private extension of the above technique. The authors conduct experiments on a benchmark dataset to adjudge the efficacy of this modeling using appropriate metrics.", "summary_of_the_review": "The paper presents a systematic investigation of generative modeling of tabular data with many to many relationships, which seems like a natural and interesting problem. The proposed apporach, while natural, requires non-trivial application of prior techniques (such as random graph generation). The apporach is evaluated on a benchmark datasets and the metrics showcase improvements over a prior approach. I am mostly positive about the paper but have some basic questions (see above) which I hope the authors response will adress.\n", "strength_and_weaknesses": "Strengths:\n\n* The problem is natural since a lot of real world datasets are tabular and have many to many relationships. A generative model which preserves these properties is important for downstream usecases such as synthetic data generation. \n* The paper is well-written; it provides a systematic investigation of approaches to the problem discussing why (extensions of) prior work seem insufficient and how the authors remedy these via proposed approach. Overall, I think the write-up is generally accessible to the wider ICLR audience. There are parts where it gets a little heavy on citing and drawing from prior work (Section 4) without enough details (more on this later). \n\nWeaknesses:\n\n* I think a simple small example of a (made-up) tabular dataset with many-to-many relationships will help the readers. Admittedly, I am not very familiar with this area, and so it took me some time to understand the intended use-case and how the abstraction captures the setting.\n\n* Clarification on modelling assumptions: The proposed approach is to fit a generative model is on a given (single) dataset, which in the simplest setting is a bi-partite graph. In order for the model to learn from this single graph, there need to be (some kind of) sufficient independence between the vertices/edges which provide an overall statistical leverage. The authors do not present a formal statistical model of the underlying graph, however, when fitting the generative model, the factorization implicitly uses certain statistical assumptions (which a-priori, I am not sure if it holds generally); in particular Eqns, (1) and (2).\nA formal model would help ascertain the validity of such a decomposition.\nAlso, a discussion on why these independence assumptions are valid in typical usecases would be helpful.\n\n* The structure of the paper essentially presents a decomposition of the problem into many sub-problems (which is novel, as far as I understand) and then the authors draw from prior work to to solve the sub-problem. \nMy issue is that the presented description of the technique is minimal and, in places, relegated to a citation. A reader who is not familiar with prior works doesn't really understand the details. Also, it gives the impression that the authors are essentially combining different techniques together.\n\n* (Minor) When discussing various possible factorization of the joint density model, the author argue why modelling of certain factors is not a good idea. While this is good in the sense that it showcases that the authors considered alternatives before finalizing the presented approach, some of the negative aspects are rather \"hand-wavy\" -- saying that \"model can be computational challenge to implement\" is perhaps not the strongest defense against using that method.\n\n* A differentially private extension is based on running DP-SGD on the loss obtained after parametrizing the generative model (NueralM2M). The authors say that it has worse performance than the other method. DP-SGD has a clipping parameter and the empirical performance typically is sensitive to its choice. I am wondering if the authors tried to tune this parameter and yet observe this worse performance. Some details would be helpful here.\n\n* Some elaboration om what it means by \"faithful\" in the context of \n\"faithful generative models\" would be useful.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QptXZuBH4M", "reviewer": "Reviewer_Ysb4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents an algorithm of synthetic data generation for many-to-many dataset. In particular, the authors decompose the overall distribution into three components and model the relationship in each component independently. Furthermore, the authors also present a private version of the algorithm and conduct experiments on real-world datasets.", "summary_of_the_review": "The paper presents a synthetic data generation algorithm for many-to-many datasets. The idea is well-motivated and the authors do a good job in presenting the algorithms. However, I am not sure the novelty is enough since the privatization part in sec 4.3 is a direct application of Laplace mechanism for pre-fixed embedding and the authors only briefly mention about training embedding privately with DP-SGD without providing any further details. Therefore, the paper can be improved if the authors can\n1. Add more details about the embedding learning with DP-SGD\n2. Provide theoretical guarantee (privacy or utility) of the proposed algorithm.", "strength_and_weaknesses": "Strength:\n\nDeveloping differentially private SDG is an important and well-motivated topic. The idea to decompose the joint distribution into multiple components and treat each component separately is interesting. \n\nWeakness:\n\n1. The privatization step in section 4.3 is straightforward and may not be scalable. It looks like in the case of prefix embeddings, there are no learnable parameters for $P(U|L)$ and $P(V|L, U)$, and the privatization process reduces into a direct application of Laplace mechanism to the BJD matrix. Moreover, the noise added to each entry of the BJD matrix scales with the number of nodes, which can be prohibitively large for complicated graphs with plenty of nodes.  Finally, the authors mention that we can use DP-SGD to train the embedding. If that is the case, it would be better if the authors can present the training objective and algorithm details in the paper.\n2. The descriptions of the distribution model in section 4.2 are not clear. In particular, the authors only provide very general introduction to different node embeddings β or aggregators γ. It would be better if the authors can present more details about the how these embeddings and aggregators work. \n3. In the experiment, the authors mention that “we use node2vec to extract node embeddings”. I am wondering how the authors privatize this embedding learning step to prevent the privacy leakage.\n\nQuestion:\n1. This is a follow-up question about the privatization step in experiments. In section 4.3, the authors mention that \"otherwise we use DP-SGD to train the embedding\". I notice that the author do not mention any training details concerning DP-SGD in experiment (section 5), so my question is that whether the authors implement DP-SGD in any of the experiments. If yes, it would be great if the authors can provide more relevant implementation details.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CpsuangTMY", "reviewer": "Reviewer_zdm5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Consider the problem of synthetically generating data based on real data with multiple tables and links between tables, such as a movie recommendation dataset, and if possible, in a differentially private way.  This paper suggests a new approach for doing so and applies it to real data.", "summary_of_the_review": "As the paper convincingly solves a novel and interesting problem, and after rebuttal, explains the evaluation criteria and shows improved results over previous methods, I recommend acceptance.", "strength_and_weaknesses": "Strengths\n+ Solves a novel problem of generating multiple-table data with rich dependency structure.\n+ Does a good job of relating the work to previous approaches and showing the novelty of the approach.\n\nWeaknesses/Questions\n- The evaluation criteria are not well explained.  Why does high similarity of mutual information indicate high-quality synthetic data?  Are the metrics used in this paper novel, or have they been previously used in the literature. [after rebuttal: addressed]\n- The paper could be improved if some other evaluations founds in the literature were incorporated.  If one were to train a recommender system on the synthetic data, does it find similar features to a recommender system trained on the real data? [after rebuttal: addressed]\n- Is there any way to empirically evaluate the quality of the differential privacy in hiding individuals? [after rebuttal: addressed]\n- I'm not sure that \"faithfulness\" is really a property of this method, since it doesn't check the conditional independencies in the real data. However, I think the paper uses the term \"faithfulness\" to capture the fact that the model doesn't underfit the real data by assuming a constrained dependency structure.  Perhaps a better way to describe this property of the method is that it is potentially consistent for arbitrary dependency structures? [after rebuttal: addressed]\n\nAdditional questions/comments after rebuttal:\n- How do prove the statement in Appendix C that n_u and n_u' are conditionally independent for sufficiently rich \\beta?  Is the proof also in Wagstaff et al. 2019?\n- Typo in Appendix D 'Detailed Eexplanation'\n\nNote: I am not familiar with the differential privacy literature, so I defer to other reviewers in the evaluation of the claims of differential privacy.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster