# GeoPointGAN: Synthetic Spatial Data with Local Label Differential Privacy

Teddy Cunningham  University of WarwickCoventryUK
<EMAIL_ADDRESS>,  Konstantin Klemmer  University of
WarwickCoventryUK<EMAIL_ADDRESS>,  Hongkai Wen  University of
WarwickCoventryUK<EMAIL_ADDRESS>and  Hakan Ferhatosmanoglu
University of WarwickCoventryUK<EMAIL_ADDRESS>
(2022)

###### Abstract.

Synthetic data generation is a fundamental task for many data management and
data science applications. Spatial data is of particular interest, and its
sensitive nature often leads to privacy concerns. We introduce GeoPointGAN, a
novel GAN-based solution for generating synthetic spatial point datasets with
high utility and strong individual level privacy guarantees. GeoPointGAN’s
architecture includes a novel point transformation generator that learns to
project randomly generated point co-ordinates into meaningful synthetic co-
ordinates that capture both microscopic (e.g., junctions, squares) and
macroscopic (e.g., parks, lakes) geographic features. We provide our privacy
guarantees through label local differential privacy, which is more practical
than traditional local differential privacy. We seamlessly integrate this
level of privacy into GeoPointGAN by augmenting the discriminator to the point
level and implementing a randomized response-based mechanism that flips the
labels associated with the ‘real’ and ‘fake’ points used in training.
Extensive experiments show that GeoPointGAN significantly outperforms recent
solutions, improving by up to 10 times compared to the most competitive
baseline. We also evaluate GeoPointGAN using range, hotspot, and facility
location queries, which confirm the practical effectiveness of GeoPointGAN for
privacy-preserving querying. The results illustrate that a strong level of
privacy is achieved with little-to-no adverse utility cost, which we explain
through the generalization and regularization effects that are realized by
flipping the labels of the data during training.

Synthetic Data Generation, GAN, Spatial Point Pattern, Local Differential
Privacy

††copyright: acmcopyright††journalyear: 2022††doi:
XX.XXXX/XXXXXXX.XXXXXXX††conference: 2022 International Conference on
Information and Knowledge Management (CIKM’22); October 17-22, 2022; Atlanta,
GA, USA††booktitle: 2022 International Conference on Information and Knowledge
Management (CIKM ’22), October 17-22, 2021, Atlanta, GA, USA††price:
15.00††isbn: 978-1-4503-9999-9/18/06

##  1\. Introduction

Generating synthetic datasets of high utility is a fundamental challenge in
many data management tasks, such as private data sharing (e.g.,
Machanavajjhala et al., 2008; Zhang et al., 2017; Ge et al., 2021; Cunningham
et al., 2021b, a), benchmark generation (e.g., Gu et al., 2015; Ghazal et al.,
2013), and database management system testing (Bruno and Chaudhuri, 2005;
Binnig et al., 2007; Torlak, 2012).

A key priority when generating synthetic data is preserving the privacy of
sensitive information while maintaining high utility. Differential privacy
(DP) and its local variant, LDP, have become the de facto privacy standards
for synthetic data generation owing to their mathematically rigorous privacy
guarantees, and several studies have tackled the issue of generating private
synthetic datasets (e.g., Zhang et al., 2021; Huang et al., 2019; Cunningham
et al., 2021a). Whereas the centralized setting of DP relies on a trusted
aggregator, LDP offers a stronger degree of privacy by allowing users to
perturb their data _before_ sharing it with the aggregator.

In this paper, we develop a locally private machine learning-based solution
for generating synthetic data from real data, with the aim to preserve the
characteristics of the original real data faithfully. We focus on spatial
point data as the proliferation of mobile technologies and location-based
services has made (private) spatial data increasingly valuable to data
scientists, companies, and researchers. Spatial datasets are also used in
several societally important fields, such as ecology (Velázquez et al., 2016),
geology (Zuo et al., 2009), and epidemiology (Gatrell et al., 1996), many of
which need to contend with the need to preserve the privacy of the data
subjects (e.g., animals from being poached illegally, individuals being
identified from contact tracing apps).

However, when dealing with spatial data, the traditional form of LDP can be
unnecessarily restrictive in terms of how it deals with sensitive data, as it
normally adopts an “all-or-nothing” approach in which all data needs to be
perturbed (Malek et al., 2021). This affects the utility of the synthetic data
for common location analytics tasks. Label privacy (Chaudhuri and Hsu, 2011)
provides a more practical means for achieving the necessary privacy protection
without sacrificing utility. It is based on the notion that the features of a
point are public (and so do not need to be perturbed), whereas the label
associated with the data is private (and so does need to be perturbed).
Applied to the setting of spatial data, label privacy leads to the following
idea: as all location information is public knowledge, it is only a person’s
association with a particular location point at a particular time that is
private and in need of perturbation. Consequently, we combine the idea of
label privacy with LDP and utilize label-LDP to provide sufficient privacy
protections when generating synthetic spatial data.

In theory, GANs offer a general purpose solution for the data generation
problem due to their objective of learning the optimal functional mapping from
some random noise input to a faithful representation of real data (Goodfellow
et al., 2014). However, most existing GAN architectures for point data stem
from computer vision and are designed for capturing simplified continuous
shapes and meshes. As such, they are not optimized to handle complex spatial
patterns observed in the real world, as our experiments show. Furthermore,
they do not support local privacy and are unsuitable for generating large-
scale spatial datasets. Our solution, GeoPointGAN, addresses these limitations
through several key technical novelties in learning the multi-scale
partitioned structures of spatial point data. GeoPointGAN’s architecture uses
extended PointNets in both the generator and discriminator and, rather than
sampling from a lower-dimensional latent vector, the generator ingests
randomly generated pseudo-co-ordinates and learns a transformation to generate
realistic outputs. The discriminator provides outputs on the point level,
rather than the batch level, which allows for highly localized training and
the seamless integration of local privacy mechanisms.

Given that they operate with data with ‘real’ and ‘fake’ labels, GANs present
an intuitive setting for implementing label-LDP. GeoPointGAN incorporates
label-LDP through a randomized response mechanism that flips the labels
provided to the discriminator, thereby providing plausible deniability to each
individual’s association with a location. We also outline how, as labels are
only flipped once, label-LDP does not suffer from the same vulnerability of
traditional LDP in which locations can be revealed through repeated querying.
Beyond its privatization properties, label flipping also has potential
generalization and regularization effects on the model performance, which we
contextualize with related literature. In most settings, local privacy
mechanisms are known to introduce a lot of noise and typically a large
database is needed to generate useful output. But, as we demonstrate in our
experiments, incorporating label-LDP into our training process has negligible
effects on model performance, which indicates that GeoPointGAN is effective at
minimizing the impacts of the added noise.

We evaluate GeoPointGAN against three recent GAN-based approaches using four
real-world datasets, each of which exhibit different characteristics. The
first set of experiments show that GeoPointGAN significantly outperforms
existing GAN-based methods in generating spatial point data, improving by up
to 10 times compared to the most competitive baseline. In the second set of
experiments, we use the synthetic data generated by GeoPointGAN to answer
location analytics queries, namely range, hotspot, and facility location
queries. GeoPointGAN performs excellently in most settings and the synthetic
data obtains very similar answers to the queries as the real data does.
Interestingly, in some settings, privatized GeoPointGANs perform slightly
better than non-private GeoPointGANs, which supports our hypothesis that label
flipping can help to realize generalization and regularization benefits.

Our strong results confirm that GeoPointGAN is a robust method for generating
practical private synthetic data that can be a worthy substitute for non-
private real data for many data science tasks, and it can also be used to
accurately answer other queries, such as proximity queries and clustering-
based analysis. Finally, generating datasets with privacy guarantees motivates
further downstream applications. For example, by harnessing the ubiquity of
mobile devices, open data portals can be populated with the private mobility
patterns of millions of individuals, with little overhead cost due to the
distributed nature of the data collection.

##  2\. Related Work

GANs. GANs have been utilized for a range of data types, including image data
(Goodfellow et al., 2014), audio streams (Akbari and Liang, 2018), text data
(Chen et al., 2018), traffic patterns (Zhang et al., 2020), and gene
expressions (Dizaji et al., 2018). In the geospatial domain, GANs have been
used for generating digital elevation maps (Klemmer and Neill, 2021) and
global surface temperatures (Klemmer et al., 2022). Existing GAN approaches
for continuous spatial point co-ordinates mostly deal with point clouds that
are simplified, continuous representations of shapes and surfaces. The first
GAN tailored to point clouds (r-GAN) (Achlioptas et al., 2018) builds on
advances in processing point clouds in neural networks, most notably PointNet
(Qi et al., 2017). Generating faithful shapes based on point cloud datasets,
such as ShapeNet (Chang et al., 2015), is an active research challenge (e.g.,
Li et al., 2018; Shu et al., 2019; Gal et al., 2020). Further studies have
utilized GANs for point cloud upsampling (Li et al., 2019), shape completion
(Sarmad et al., 2019), or against adversarial attacks (Zhou et al., 2020).
Their applications to real-world data have been limited thus far, with a few
recent exceptions such as an application to Lidar data (Caccia et al., 2019).

Geospatial datasets have different characteristics, which means their point
patterns are very different from the point clouds that describe shapes and
meshes. They do not have a mesh-like structure, they are typically more
complex and noisy, and may be governed by underlying dynamics such as self-
excitement. Few studies have tackled this class of data using GANs: Xiao et
al. (2017) use Wasserstein GANs to learn temporal (one-dimensional) point
processes, while Klemmer et al. (2019) learn conditional GANs contextualized
by the co-ordinates of continuous spatial point data. However, these works
provide no intuition for point transformations or for producing new spatial
point patterns similar to the input. The challenging nature of generating
spatial point patterns and the lack of existing work addressing this problem
help to motivate our work.

Private GANs. In recent years, there have been a number of studies proposing
differentially private GANs, including DPGAN (Xie et al., 2018), DP-CGAN
(Torkzadehmahani et al., 2019), PATE-GAN (Yoon et al., 2019), and the work of
Frigerio et al. (2019), which extends DPGAN to continuous, discrete, and time
series data. Existing private GANs have focused on other specific domains,
such as medical (Yoon et al., 2019; Beaulieu-Jones et al., 2019; Torfi et al.,
2020), image (Torkzadehmahani et al., 2019), or time series data (Wang et al.,
2020), as opposed to spatial data. Furthermore, all existing private GANs use
centralized DP, normally by clipping and adding noise to the gradient during
training (Xie et al., 2018; Frigerio et al., 2019) or applying existing
private frameworks (e.g., Yoon et al., 2019; Augenstein et al., 2019). This
different privacy setting means we cannot compare them to our work.

Location Privacy. Both DP and LDP have increasingly been applied with
location-specific variants, such as geoindistinguishability (Andrés et al.,
2013). Most work has focused on data publication with DP (e.g., Mohammed et
al., 2011; Chen et al., 2012; Acs and Castelluccia, 2014; Cormode et al.,
2012; Xiao and Xiong, 2015; Ghane et al., 2018; Gursoy et al., 2018), as
opposed to data synthesis and LDP. Some other work exists on private
trajectory synthesis and publication (e.g., He et al., 2015; Gursoy et al.,
2020; Qu et al., 2020), but recently proposed solutions, in both the
centralized (e.g., He et al., 2015; Gursoy et al., 2020) and local settings
(Cunningham et al., 2021b), all possess a common limitation. They all produce
outputs that correspond to arbitrary grid cells or places of interest, whereas
we generate co-ordinate data (i.e., the same form as the input data). While
one could extend these solutions to generate individual points (e.g., by using
uniform sampling), Cunningham et al. (2021a) show that adapting existing
solutions in this way fails to produce high-quality synthetic spatial point
data. Their purpose-built solution is designed for the centralized DP setting,
which leaves generating high-quality spatial point data in local privacy
settings as an important, yet unaddressed, challenge. We note that there has
been some work on location data in local settings (i.e., LDP and variants
thereof). Chen et al. (2016) use personalized LDP for spatial data
aggregation, Xiong et al. (2019) focus on continuous location sharing using
randomized response, and Cunningham et al. (2021b) publish LDP-compliant
sequences of places of interest. However, extensions of these works to our
setting are unviable owing to their fundamentally different problem and/or
privacy settings.

Label DP. Label-DP was formally introduced by Chaudhuri and Hsu (2011) and has
since been the focus of several studies (Wang and Xu, 2019; Ghazi et al.,
2021; Esfandiari et al., 2021; Yuan et al., 2021; Malek et al., 2021). All of
these works are based on the same premise as our work: only the labels
attached to data are sensitive, with the data itself being non-sensitive.
Despite this work, almost all prior work has been in the centralized setting;
only Busa-Fekete et al. (2021) consider the local setting. Hence, we are the
the first to apply label-LDP to GANs to generate privacy-preserving spatial
point data with LDP-style guarantees.

##  3\. Method

Figure 1. GeoPointGAN modeling pipeline including the label-LDP mechanism

Before introducing GeoPointGAN, we first present some background on GANs, and
discuss the privacy setting we follow in our work.

###  3.1. GANs

GANs are a family of models that seek to learn the data generating process of
observed data $\mathbf{x}\sim p_{data}(\mathbf{x})$. Learning is facilitated
through two networks: a generator $G$, and a discriminator $D$. The generator
$G(\mathbf{z},\Theta_{G})$ with parameters $\Theta_{G}$ maps a random noise
input $\mathbf{z}\sim p_{\mathbf{z}}(\mathbf{z})$ to the feature space of the
real data $\mathbf{x}$ so that $G:\mathbf{z}\xrightarrow{}\mathbf{x}$. The
discriminator $D([\mathbf{x},\mathbf{\hat{x}}],\Theta_{D})$, parameterized by
$\Theta_{D}$, then attempts to distinguish real data $\mathbf{x}$ from
synthetic samples $\mathbf{\hat{x}}$, so that
$D:[\mathbf{x},\mathbf{\hat{x}}]\xrightarrow{}\\{0,1\\}$, with 0 and 1
denoting labels of ‘fake’ and ‘real’ data points respectively. The learning
process follows from a min-max game between $G$ and $D$, which is given as
$V(D,G)$:

(1) $\begin{split}\min_{G}\max_{D}V(D,G)=&\mathbb{E}_{\mathbf{x}\sim
p_{data}(\mathbf{x})}\bigl{[}\log D(\mathbf{x})\bigr{]}+\\\
&\mathbb{E}_{\mathbf{z}\sim
p_{\mathbf{z}}(\mathbf{z})}\bigl{[}\log(1-D(G(\mathbf{z})))\bigr{]}\end{split}$

In our case, the input feature vector $\mathbf{x}\in\mathbb{R}^{m}$ represents
the spatial co-ordinates of a point in $m$-dimensional space.

###  3.2. Privacy Setting

####  3.2.1. Local Differential Privacy

The centralized model of DP (Dwork, 2006) offers strong privacy guarantees
through a level of plausible deniability but assumes that the data aggregator
can be trusted, which may not always be appropriate, especially when highly
sensitive data (e.g., location data) is concerned. Therefore, we focus on the
local setting as it achieves a stronger level of privacy by allowing users to
perturb the data before sharing it with the data aggregator.

###### Definition 3.1 ($\epsilon$-local differential privacy (Duchi et al.,
2013)).

A randomized mechanism $\mathcal{M}$ satisfies $\epsilon$-local differential
privacy if, for any two inputs $\mathbf{x}_{i},\mathbf{x}_{j}$ and output
$\mathbf{y}$:

(2) $\textstyle\Pr[\mathcal{M}(\mathbf{x}_{i})=\mathbf{y}]\leq
e^{\epsilon}\times\Pr[\mathcal{M}(\mathbf{x}_{j})=\mathbf{y}]$

where $\epsilon$ is the privacy budget that controls the level of privacy
protection. The intuition with LDP is that, given the output $y$, an adversary
cannot (with high confidence) identify the input value.

One important property of LDP is post-processing. Formally, for any two
mechanisms $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, if $\mathcal{M}_{1}$
satisfies $\epsilon$-LDP, then the composition
$\mathcal{M}_{2}(\mathcal{M}_{1}(\cdot))$ satisfies $\epsilon$-LDP (regardless
of whether $\mathcal{M}_{2}$ satisfies $\epsilon$-LDP itself) (Del Rey et al.,
2020). In a practical sense, the post-processing property allows the output of
an LDP mechanism to be used and manipulated infinitely, without affecting its
privacy guarantee, as long as there is no further interaction with the private
data.

LDP can be achieved by using randomized response (Warner, 1965) in which a
user reports their true data with probability $p$, and reports an alternative
response with probability $q$. LDP attaches strong privacy guarantees to
randomized response outputs. To satisfy LDP in the generalized randomized
response setting, the probability a user reports true information is
$p=\frac{e^{\epsilon}}{e^{\epsilon}+d-1}$, where $d$ is the size of the output
set. Hence, the probability of reporting any other single output is
$q=\frac{1}{e^{\epsilon}+d-1}$.

####  3.2.2. Label Local Differential Privacy

The notion of LDP is extended to label-LDP if we consider each feature vector
$\mathbf{x}_{i}$ to have a label $l_{i}\in\mathcal{L}$, together denoted as
$(\mathbf{x}_{i},l_{i})$.

###### Definition 3.2 ($\epsilon$-label-LDP).

A randomized mechanism $\mathcal{M}$ satisfies $\epsilon$-label-LDP if, for
any labeled feature vector $(\mathbf{x},l)$ with the input labels
$l_{i},l_{j}\in\mathcal{L}$ and output label $l_{k}\in\mathcal{L}$:

(3) $\textstyle\Pr[\mathcal{M}((\mathbf{x},l_{i}))=(\mathbf{x},l_{k})]\leq
e^{\epsilon}\times\Pr[\mathcal{M}((\mathbf{x},l_{j}))=(\mathbf{x},l_{k})]$

It is intuitive to observe that label-LDP possesses the same post-processing
property as traditional LDP, and that randomized response can be used to
ensure label-LDP.

As explained in Section 1, label-LDP provides more practical, yet sufficiently
private, protection to data by only perturbing the label attached to a feature
vector. This is appropriate for our problem given that we deem information
about locations in a region to be sufficiently public with only one’s
association with a location being private information. From Definition 3.2,
the intuition is that an adversary cannot (with high confidence) identify
whether the person was at the reported location or not.

We assume that the dataset of real points covers a sufficiently large
proportion of the domain in which fake points can be generated. This is to
prevent the labels being sufficiently correlated with features, which would
undermine privacy (Busa-Fekete et al., 2021). For example, if the ratio
between land area and total area was too small, many fake points could be
generated in nonsensical locations (e.g., oceans), which would allow an
adversary to identify fake points and, by extension, real points. While this
assumption does not affect the mechanism in any way, we impose this soft
constraint as an extra layer of protection against privacy leakage.

Finally, although one could naïvely apply randomized response directly to the
real data, this limits the dataset size to approximately
$\tfrac{Ne^{\epsilon}}{e^{\epsilon}+1}$, which heavily limits the range of
analytics tasks for which the private data can be used. Hence, a more flexible
solution that can generate datasets of any size is necessary.

####  3.2.3. Examples

To further illustrate the use of label-LDP in our setting and its advantage
over traditional LDP, consider the following two example scenarios. In both
examples, although having the original locations with perturbed labels is
useful in itself, the samples may not be representative and, in any case, they
will be noisy, owing to perturbation. As such, being able to generate datasets
of any size based on the original distribution is important, and gives end
users more flexibility.

For our first example, consider that a city’s government wants to know the
distribution of its residents’ locations at 10am. This might help to determine
the approximate proportion of people working from home, which is helpful for
managing working conditions or reducing disease spread. Given that the
government will know every resident’s address (e.g., through voter rolls or
council tax information), this information is non-private. The private element
is where each person is at 10am, and residents will want a degree of plausible
deniability, which is provided by label-LDP. In comparison, traditional LDP is
unnecessarily restrictive here as it would require the perturbation of the
location of each resident at 10am, even if their home address is known.

Moreover, repeated use of traditional LDP (through perturbation of the
location) would eventually reveal the true location. While continuous data
sharing is a common need for many real-life applications, traditional LDP
approaches do not address this most practical setting. Whereas, with label-
LDP, as the location itself is deemed to be non-private, each daily report can
be considered to be independent, and so repeated querying does not degrade the
overall privacy level provided to each user. This further motivates label-LDP
as a more robust privacy setting in many practical cases.

Our second example differs from the first as the government no longer has a
plausible location for each individual for which they want to ask a yes-no
question. Imagine a town with 100,000 people, all of which are asked to
privately share their location at 8pm, which is also the time at which a large
number of residents are attending a concert. With traditional LDP, the
locations of each individual would need to be perturbed, which would induce a
large amount of noise into the dataset and greatly affect utility. However,
public knowledge (e.g., news sources) would indicate that many people are at
the concert and so we should expect a large number of reported locations to be
associated with the concert. As such, label-LDP still gives each concert-goer
a degree of plausible deniability regarding their presence at the concert,
while preserving the overall popularity distribution, which is publicly known
(to some extent).

###  3.3. Model Architecture

Existing GAN architectures for point data, mostly stemming from computer
vision research, aim to capture object shape point clouds or mesh-structured
data. As such, they are designed to model simple shapes and object outlines.
Spatial point patterns, such as location data from mobile devices, typically
have a noisy, multi-scale partitioned structure, and may cover the whole
observational area, rather than having clear outlines. For example, while the
point cloud of a chair can roughly be segmented into six elements (four legs,
seat, back), spatial point patterns in the real world can consist of hundreds
of intricate macroscopic (e.g., terrain, cities) and microscopic (e.g., roads,
junctions) elements. GeoPointGAN includes several novel approaches to address
the challenges of generating this data. Its data-processing pipeline and
architecture, outlined in Figure 1, consist of three main components, which we
explain next.

####  3.3.1. Generator

GeoPointGAN samples a noise vector of the same dimensionality as the desired
output. This is equivalent to sampling $B$ random points
$\mathbf{z}=[\tilde{c}_{z}^{1},...,\tilde{c}_{z}^{m}]$ with co-ordinates $c$
in the same space $m$ as a real point $\mathbf{x}=[c^{1},...,c^{m}]$. This is
in contrast to traditional GAN approaches, which sample a Gaussian noise
vector $\mathbf{z}$ from a lower-dimensional latent space. Rather than
learning a model that ‘upsamples’ from a low-dimensional latent space to a
higher-dimensional output space, we thus aim to learn a model that transforms
data from an $m$-dimensional latent space to a meaningful representation in
the same $m$-dimensional space.

We use this noise sampling strategy to design a novel PointNet-based
generator. PointNet (Qi et al., 2017) was originally devised for
classification and segmentation of raw point clouds. While it has been used as
the basis for GAN discriminators before (see Achlioptas et al., 2018), we
propose the first GAN that utilizes PointNet in the generator. Particularly,
its ability in providing transformation invariant properties for unordered
data is desirable for spatial point generation. This is achieved by running
the input through symmetric functions (e.g., max pooling operators) to compute
global point set features. This step is followed by a segmentation network
that combines the global information (e.g., city boundaries, rivers) with
local, point-wise information (e.g., roads, junctions) to learn a combined
representation. Lastly, a spatial transformer network (STN) (Jaderberg et al.,
2015) aligns the learned global and local point set features with the output
space. We find that the traditional STN architecture is unable to resolve the
complexities of spatial point datasets sufficiently, owing to the shallowness
of the neural networks deployed. In particular, while macroscopic structures
(e.g., coastlines) can be captured reliably, the STN is incapable at learning
small-scale patterns (e.g., minor roads). Consequently, we extend the STN such
that we have five one-dimensional convolutional layers, with four fully
connected layers, adding batch normalization between every layer and the ReLu
function (except the last layer). Altogether, we refer to this altered
PointNet as ‘Large PointNet’.

As a final step, our generator takes the transformation invariant, aligned
features of Large PointNet and projects them into the $m$-dimensional output
space using four fully connected layers. This is similar to the prediction
head for point segmentation, only that we produce $m$ features per point (our
synthetic co-ordinates), rather than one. These design choices are informed by
extensive testing and are validated in our experiments.

####  3.3.2. Discriminator

Our discriminator architecture is inspired by Achlioptas et al. (2018), but
comes with some fundamental technical improvements and a critical change that
lets us incorporate our label-LDP mechanism. First, we run points through our
‘Large PointNet’ module. This balances the capacity for learning point set
representations between the generator and discriminator, allowing for an
evenly matched min-max game. The discriminator’s prediction head consists of
two fully connected layers and a sigmoid activation. Second, we alter the last
fully connected layer to produce predictions not on the batch, but rather the
point level. That is, the discriminator’s task is thus to determine whether
each individual point is real or fake, as opposed to each batch of points.
Constructing the discriminator in this way allows us to seamlessly incorporate
a localized privacy mechanism into model training.

####  3.3.3. Privacy Mechanism

We integrate point-level privacy guarantees into GeoPointGAN by
probabilistically flipping the labels of the real and fake points (using
randomized response) before showing the data samples to the discriminator.
Whereas LDP would require perturbation of each co-ordinate point (using, say,
the Laplace or exponential mechanism), with label-LDP, perturbing the label is
sufficient. In our setting, we have two (pseudo-)labels – ‘real’ and ‘fake’ –
which means that $d=2$ and that flipping can be conducted using biased coin
tosses in which the probability that a label’s true status is maintained is
$p$, and the probability that a label’s status is flipped is $q=1-p$. The
labels of real points are flipped on users’ devices during data pre-
processing, which ensures that the central agent (i.e., the GAN networks)
never has access to this information. Should a real point be sampled several
times throughout training, it will always have the same (flipped) label. From
Definition 3.2, the intuition follows that the discriminator cannot determine
(with high probability) that a point with a real label is actually real, or
whether it is a fake point masquerading as a real one (or vice versa).

In a practical setting, all training is conducted by a central agent (who can
be trusted or untrusted) on a remote server. Individual data is collected
through mobile devices and each individual is responsible for flipping the
label associated with their location. Hence, the only data transferred from
this device is the location and the flipped label, which means that no central
agent can definitively determine the true label with absolute certainty.
Importantly, the discriminator does not know which points are generated by the
generator, and which points are transmitted to the server by users; it can
only distinguish points based on their perturbed labels. In summary, the
discriminator has no way of (definitively) knowing whether any one point is
real with a real label, real with a fake label, fake with a real label, or
fake with a fake label.

####  3.3.4. Effects on Training and Generalization

A label flipping approach such as ours does not necessarily reduce model
performance, but can even have beneficial effects. In predictive models,
randomly flipping labels can act as a regularizer, preventing the model from
overfitting and improving generalization (Xie et al., 2016). When working with
noisy labels, label flipping can incorporate the uncertainty of the labels
into the model (Nguyen et al., 2019). There is a vast collection of literature
that focuses on GAN regularization and robustness, and addresses problems such
as limited data availability or generator-discriminator imbalance.
Manipulating the (pseudo)-labels of GANs has proven to be a successful
strategy to this end. Specifically, adding noise to the labels or applying
one-sided label smoothing have been shown to improve GAN training and these
are common best practices (Salimans et al., 2016). Finally, Jiang et al.
(2021) provide a study that is closely related to our approach. The authors
propose to feed the discriminator with fake data masquerading as real data
(i.e., fake data with real labels). While this is proposed mainly as an
augmentation strategy for sparse data environments, it is very similar to our
label flipping approach, although they do not feed the discriminator real data
with fake labels as we do. The authors also provide a theoretical intuition
for training convergence and their approach. Their proof highlights how a GAN
trained with label flipping augmentation minimizes the Jensen-Shannon
divergence between the (smoothed) real and synthetic data distributions and
is, in theory, able to perfectly capture the data generating process. Hence,
we expect that private GeoPointGANs will (to a certain extent) perform as well
as non-private GeoPointGANs (i.e., ones with no label flipping).

###  3.4. Model Training

Algorithm 1 describes the training of GeoPointGAN. Note that Lines 1-2 are
conducted on user devices, although we include the steps here for
completeness. Before training, each real point is assigned the ‘real’ label:
$l_{i}=1$ (Line 1). These labels are then flipped with probability $q$, where
$q$ is controlled by the privacy budget, $\epsilon$ (Line 2). Perturbed labels
are denoted as $l^{\prime}_{i}$. We then initiate the training loop (Line 3).
At each training step, $B$ points are sampled from the real data without
replacement (so as to not oversample points from high-density areas) (Line 4).
$B$ random co-ordinates are also drawn from the noise prior $p_{\mathbf{z}}$
(Line 5) and transformed in $G$ to generate $B$ fake points:
$\mathbf{\hat{x}}=G(\mathbf{z})$. The label of each fake point,
$\hat{l}_{i}=0$, is flipped with probability $q$ to obtain
$\hat{l}^{\prime}_{i}$ (Line 6). Real points $(\mathbf{x},l^{\prime})$ and
fake points $(\mathbf{\hat{x}},\hat{l}^{\prime})$ are then classified as real
or fake by $D$, after which $D$ is updated using the optimizer (Line 7). We
then train $G$ by generating $B$ new fake points (Line 8), flipping their
labels with probability $q$ (Line 9), and once more classifying them using
$D$. $G$ is then updated using its optimizer (Lines 10). This concludes one
training step. $D$ and $G$ continuously play this game, with $G$ getting
better and better at generating synthetic data. After $T$ training steps, the
label-LDP generator is published (Line 11).

Algorithm 1 GeoPointGAN training

1:$\mathcal{D}$, $\epsilon$, $B$, $T$

2:Assign real points real labels:
$\\{\mathbf{x}_{1},...,\mathbf{x}_{n}\\}\rightarrow\\{(\mathbf{x}_{1},l_{1}),...,(\mathbf{x}_{n},l_{n})\\}$

3:Flip real labels with prob. $q=\frac{1}{e^{\epsilon}+1}$ to obtain
$\\{(\mathbf{x}_{1},l^{\prime}_{1}),...,(\mathbf{x}_{n},l^{\prime}_{n})\\}$

4:for $1$ to $T$ do

5: Sample $B$ real points with flipped labels:
$\\{(\mathbf{x}_{1},l^{\prime}_{n}),...,(\mathbf{x}_{B},l^{\prime}_{B})\\}$

6: Sample $B$ random co-ordinates $\\{\mathbf{z}_{1},...,\mathbf{z}_{B}\\}$
from noise prior $p_{\mathbf{z}}$

7: Flip fake point labels with probability $q$ to obtain
$\\{\hat{l}^{\prime}_{1},...,\hat{l}^{\prime}_{n}\\}$

8: Update $D$ by ascending its stochastic gradient:

9:$\nabla_{\Theta_{D}}\frac{1}{B}\sum_{i=1}^{B}\Big{[}\log
D(\mathbf{x}_{i},l^{\prime}_{i})+\log(1-D(G(\mathbf{z}_{i}),\hat{l}^{\prime}_{i})\Big{]}$

10: Sample $B$ random co-ordinates $\\{\mathbf{z}_{1},...,\mathbf{z}_{B}\\}$
from noise prior $p_{\mathbf{z}}$

11: Flip fake point labels with probability $q$ to obtain
$\\{\hat{l}^{\prime}_{1},...,\hat{l}^{\prime}_{n}\\}$

12: Update $G$ by ascending its stochastic gradient:

13:$\nabla_{\Theta_{G}}\frac{1}{B}\sum_{i=1}^{B}\Big{[}\log(D(G(\mathbf{z}_{i}),\hat{l}^{\prime}_{i})\Big{]}$

14:return $G$

###  3.5. Privacy Analysis

We now discuss some important aspects of the mechanism, from a privacy
perspective. First, we show the proposed label flipping approach satisfies
$\epsilon$-label-LDP.

###### Theorem 3.3.

GeoPointGAN satisfies $\epsilon$-label-LDP.

###### Proof.

For ease of understanding, in this proof, we denote points with real and fake
labels as and $\mathbf{x}^{0}$, respectively The probability that a real label
tells the discriminator that it is a real label is:
$\Pr[\mathcal{M}()\\!=\\!]\\!=\\!p\\!=\\!\frac{e^{\epsilon}}{e^{\epsilon}+1}$.
Hence, the probability that a real label tells the discriminator that it is a
fake label is $1\\!-\\!p$. That is,
$\Pr[\mathcal{M}()\\!=\\!\mathbf{x}^{0}]\\!=\\!q\\!=\\!\frac{1}{e^{\epsilon}+1}$.
Similarly, $\Pr[\mathcal{M}(\mathbf{x}^{0})\\!=\\!\mathbf{x}^{0}]\\!=\\!p$ and
$\Pr[\mathcal{M}(\mathbf{x}^{0})\\!=\\!]\\!=\\!q$. From Equation 3, we have:

∎
$\textstyle\frac{\Pr[\mathcal{M}()=]}{\Pr[\mathcal{M}(\mathbf{x}^{0})=]}=\frac{p}{q}=\frac{e^{\epsilon}}{e^{\epsilon}+1}/\frac{1}{e^{\epsilon}+1}=e^{\epsilon}$

As discussed in Section 3.2, label-LDP has the same post-processing properties
as LDP, which means that privatized data can be manipulated freely without
affecting the privacy guarantee (as long as the true data is not ‘touched’
again). In our setting, the labels are perturbed by users before they are
shown to the discriminator, and the true label is never used again. This means
that the entire training procedure operates under post-processing, and our
privacy guarantee remains in tact throughout training.

Many DP mechanisms suffer when points are repeatedly sampled, which causes the
privacy leakage to increase each time a point is sampled. Our mechanism is
designed such that these attacks are redundant as point labels are flipped
once, and once only, before training begins. That is, when $\mathbf{x}_{i}$ is
sampled during any training step, it will always have the same perturbed label
$l^{\prime}_{i}$. This means that there is no privacy leakage even if a point
is sampled more than once during different training steps. Note that, as we
sample without replacement, the same point cannot be sampled multiple times
during a single training step.

Figure 2. Sample plots of real and synthetic data; from top to bottom: Porto,
Beijing, New York City and 3D Road

##  4\. GAN Evaluation

We evaluate GeoPointGAN in two parts using four real spatial datasets. The
first part, presented in this section, evaluates both non-private and private
versions of GeoPointGAN using two fundamental point cloud and GAN metrics. We
compare GeoPointGAN against three alternative GAN-based approaches. In the
second part (Section 5), we evaluate GeoPointGAN’s practical query-based
performance using three common location analytics tasks.

###  4.1. Experiment Set-Up

Data. All experiments use the following open-source, real-world datasets. They
exhibit a range of characteristics (e.g., alignment of the data with the road
network, structure of the road network), which allow us to study GeoPointGAN
in a variety of contexts.

We use two taxi trajectory datasets from Porto (Geolink, 2015) and Beijing
(Yuan et al., 2010; Yuan et al., 2011). We extract the latitude and longitude
co-ordinates from the raw data and, remove all points that fall within
nonsensical geographic regions (e.g., bodies of water). Although points in the
real data are linked, we remove this spatio-temporal linkage and consider each
point individually. Note that doing this has no effects on privacy, as each
point has its own privacy guarantee. The final Porto dataset contains 79,360
points over an area of 24.7km2, and the Beijing dataset contains 158,260
points across a region with an area of 104.7km2.

We also use 311 call data from New York City (NYC) (New York City Open Data,
2020), filtering the dataset to only include data from Manhattan. The dataset
has 163,220 points, each of which represents the location provided by the
caller. Unlike the other datasets, the New York data is closely aligned with
the road network, which itself is grid-like and ordered.

Our final dataset – ‘3D road’ – provides three-dimensional spatial co-
ordinates (latitude, longitude, and altitude) of the road network in Jutland,
Denmark (Kaul et al., 2013). The dataset comprises over 430,000 points,
covering an area of 185 $\times$ 135 km2.

Training Setting. We follow a standardized training process. At each training
step, 7,500 points are randomly sampled from the real dataset. We use the Adam
optimizer with decoupled weight decay (Loshchilov and Hutter, 2019) and an
initial learning rate of $4\text{\times}{10}^{-5}$. The learning rate is
decreased by a factor of 10 after 5,000, 50,000, and 90,000 training steps. We
train 1,000 steps per epoch for a total of 100 epochs. All training is
conducted on a single RTX 2080 GPU. With this set-up, model training times do
not exceed two hours. Overall, GeoPointGAN, like r-GAN, experiences training
that is reliable and consistent. At no point during any of our training runs
do we experience mode collapse or exploding gradients.

Benchmarks. We compare GeoPointGAN against three state-of-the-art GANs. The
first – r-GAN (Achlioptas et al., 2018) – is the method that is most closely
related to GeoPointGAN and it is designed to operate on raw point clouds
(point co-ordinates). The other two baselines, tree-GAN (Shu et al., 2019) and
PCGAN (Arshad and Beksi, 2020), are designed for graph-structured point clouds
(e.g., meshes, shapes). All baselines are trained according to the
configuration outlined by the original authors.

Despite the development of other private GANs (e.g., DPGAN, PATEGAN), these
works all use the centralized DP, which is fundamentally different from our
label-LDP setting. Similarly, although other private methods for synthetic
spatial data generation exist, these methods also use different forms of
privacy. For example, Chen et al. (2016) use personalized LDP, and Cunningham
et al. (2021a) use centralized DP. As our privacy setting is different from
all of these works, any comparison between them is meaningless.

Evaluation Metrics. To evaluate GeoPointGAN’s ability to preserve the
underlying distribution of the real data, we use two widely used utility
measures: Chamfer distance (CD) and earth mover’s distance (EMD). As a
continuous and pairwise smooth function, Chamfer distance is a well-
established measure of point cloud distance. For a set of real points
($\mathcal{R}$) and synthetic points ($\mathcal{S}$), CD is defined as:

(4) $\textstyle
CD(\mathcal{R},\mathcal{S})=\sum_{r\in\mathcal{R}}\min_{s\in\mathcal{S}}\|r-s\|^{2}+\sum_{s\in\mathcal{S}}\min_{r\in\mathcal{R}}\|r-s\|^{2}$

where $\|\cdot\|$ is some distance measure, and $r$ and $s$ are individual
real and synthetic points, respectively. We use normalized Euclidean distance
in our evaluation.

EMD – a common metric for evaluating GANs – can be viewed as an optimization
problem that seeks to transform one probability distribution into another
while minimizing the cost of this operation. While the computational cost of
obtaining the exact distance is too high for it to be used in deep learning
algorithms (and hence approximations are used), we use its exact version as an
evaluation measure. Defining $\phi:\mathcal{R}\rightarrow\mathcal{S}$ as a
bijection, EMD is defined as:

(5) $\textstyle
EMD(\mathcal{R},\mathcal{S})=\min_{\phi:\mathcal{R}\rightarrow\mathcal{S}}\sum_{e\in\mathcal{R}}\|r-\phi(r)\|$

###  4.2. Results

####  4.2.1. Baseline Comparison

Figure 2 depicts plots of the real data, alongside samples from GeoPointGAN
and r-GAN. We do not include visualizations for tree-GAN and PCGAN as they
performed poorly. While r-GAN succeeds at capturing macroscopic structures,
such as the outline of Manhattan and Central Park, it lacks the capacity to
model more intricate structures within the outline, such as individual streets
or junctions. On the other hand, GeoPointGAN is able to reproduce microscopic
structures to a reasonable extent.

We calculate mean CD and EMD values by taking 60 samples of 7,500 points each
from the fully trained generators. These values are shown in Table 1. Note
that, here, we use a non-private GeoPointGAN (i.e., $\epsilon=\infty$) to
ensure a fair comparison with the baselines, which have no privacy mechanism.
The tree-based methods perform particularly poorly as they fail to learn the
spatial data distribution. This justifies the decision to use generative
models that are capable at operating on raw point co-ordinates, rather than
shapes or meshes. GeoPointGAN offers substantial improvements of up to 70%
over r-GAN, with consistently better CD and EMD values, which reflects its
ability to preserve microscopic features and generate accurate spatial point
data.

Table 1. Mean CD and EMD values Method | Chamfer Distance | Earth Mover’s Distance
---|---|---
NYC | Por. | Beij. | 3DR | NYC | Por. | Beij. | 3DR
tree-GAN (Shu et al., 2019) | 0.649 | 0.437 | 0.651 | 1.247 | 0.601 | 1.085 | 0.733 | 1.080
PCGAN (Arshad and Beksi, 2020) | 0.160 | 0.348 | 0.092 | 0.796 | 0.305 | 0.831 | 0.283 | 0.896
r-GAN (Achlioptas et al., 2018) | 0.226 | 0.034 | 0.032 | 0.264 | 0.364 | 0.275 | 0.084 | 0.526
GeoPointGAN | 0.014 | 0.019 | 0.021 | 0.074 | 0.031 | 0.027 | 0.032 | 0.085
Figure 3. Real and synthetic data for different privacy budgets; data for New
York City, zoomed in on Central Park

(a) Porto

(b) Beijing

(c) New York

(d) 3D Road

Figure 4. Chamfer distance across different datasets

####  4.2.2. Effect of Privatization

To assess how the application of our label-LDP mechanism affects GeoPointGAN
performance, with particular focus on the sensitivity of GeoPointGAN to the
privacy budget, we again draw 60 samples of 7,500 points from the real and
synthetic datasets. We consider seven privacy budgets:
$\epsilon=\\{0.1,0.25,0.5,1,2,5,10\\}$. As none of the baselines are
competitive with GeoPointGAN and they were not designed with privacy-
preserving mechanisms in mind, we exclude them from this part of the
evaluation. Figure 2 shows the effect of privatization on the generated data.
We observe that lower privacy budgets have a negative impact on visual
similarity. Figure 3 further illustrates how the preservation of macroscopic
geographic features (e.g., Central Park in New York City) is affected by
changing the privacy budget.

Figure 4, which shows the variation in CD as the privacy budget varies,
highlights more interesting behavior. First, as expected, a very low privacy
budget results in poor utility with utility increasing as $\epsilon$
increases. However, when $\epsilon>1$, the CD values start to increase,
leading to (albeit subtle) U-shaped curves. This indicates that our hypothesis
that label flipping can aid performance is supported with empirical evidence.
Specifically, we can quantify the optimal degree of label flipping to be when
$\epsilon\approx 1$ (i.e., $q\approx 27\%$). In some cases, better utility is
gained using private GeoPointGANs (cf. Beijing), which further demonstrates
the power of regularization through privatization.

Interestingly, the structure of the underlying data also appears to influence
this behavior. In New York, where the data is more closely aligned with a
strict grid structure, the U-shape is more pronounced, indicating that the
regularization properties of GeoPointGAN are more influential here.
Conversely, in Porto, where the true data (and road network) lacks a clear
structure, the U-shape is more subtle and very high privacy budgets correct
the curve downwards. Finally, for 3D Road, we see large CD values and larger
variations in these values, which suggests that the complexity and spatial
extent of the dataset pushes GeoPointGAN to its limits.

##  5\. Data Analytics Tasks

We now evaluate GeoPointGAN using two popular data analytics tasks – range and
hotspot queries – both of which are popular for location analytics. We then
apply our solution to the data-driven spatio-temporal task of facility
location. We assess the ability for GeoPointGAN to preserve the answers to
these queries to demonstrate the applicability of our solution in a database
and data science setting. Given the poor qualitative and quantitative
performance of the baselines, and their non-private nature, it is not
meaningful to compare GeoPointGAN against them for these queries. As such, the
aim of this evaluation is to compare GeoPointGAN to the optimum (i.e., maximum
similarity with the real data).

(a) MAE – Porto

(b) MAE – Beijing

(c) MAE – New York

(d) MPE – Porto

(e) MPE – Beijing

(f) MPE – New York

Figure 5. Variation in MAE/MPE as the query radius varies

###  5.1. Range Queries

Range queries are commonly used in databases, as well as a primitive for
location analytics. For example, they can be used to quickly assess how many
customers are potentially available to a business, or measure accessibility to
key services within a certain time, such as schools, hospitals, or vaccination
centers. To assess this, we specify a set, $\mathcal{P}$, of 200 arbitrary
places in each city to be the basis of our range queries, and these places are
randomly selected from the set of nodes in each city’s road network. The
extent of each range query is the circular region defined by the radius,
$\rho$, and centered on place $\pi$. For each synthetic sample, we answer the
set of range queries for all $\pi\in\mathcal{P}$ and all values for $\rho$,
and we quantify of error using the mean absolute error (MAE) and mean
percentage error (MPE). Having conducted range queries for all 60 synthetic
data samples, we take the mean of the MAE and MPE values. We consider the
following $\rho$-values: {50, 100, 200, 500, 1000} meters.

Figure 5 shows the effect that $\rho$ has on the MAE/MPE of the query answer.
As expected, MAE increases as $\rho$ increases, although MPE decreases; both
of these trends are acceptable when considered together. As a particularly
impressive outcome, we see that synthetic data generated with higher privacy
budgets (i.e., $\epsilon\geq 0.25$) performs as well, and sometimes better,
than the data generated using the non-private version of GeoPointGAN. Close
inspection indicates that the privatized GeoPointGAN performs best when
$\epsilon\approx 1$, which is concordant with the findings in Section 4.2.2.

###  5.2. Hotspot Analysis

Hotspot analysis identifies regions with a high number of points and, like
range queries, it is fundamental in location analytics. For example,
businesses need to identify popular regions for advertising, and city agencies
have to manage congestion and traffic flow. We analyze hotspots for the three
two-dimensional datasets by generating kernel density estimates (KDEs) for the
real and synthetic datasets. The KDE uses the two-dimensional Gaussian kernel
defined over a uniform grid with dimensions of $g\times g$, where $g$ denotes
the granularity. We use a range of granularities:
$g=\\{2^{6},2^{7},2^{8},2^{9},2^{10}\\}$, and define hotspots to be grid cells
in which the density is greater than the 95th percentile. For each of the 60
samples, we assess query response similarity between the real and synthetic
data using the Sørensen-Dice coefficient (SDC):

(6) $\textstyle
SDC=\frac{2\big{|}\mathcal{H}_{\operatorname{r}}\bigcap\mathcal{H}_{\operatorname{s}}\big{|}}{\big{|}\mathcal{H}_{\operatorname{r}}\big{|}+\big{|}\mathcal{H}_{\operatorname{s}}\big{|}}$

where $\mathcal{H}$ is the set of hotspots.

(a) Porto

(b) Beijing

(c) New York

Figure 6. Variation in SDC as the hotspot granularity varies

Figure 6 shows the variation in mean SDC values as the hotspot granularity
increases and, once again, we observe similar findings. Namely, (a) poor
performance is observed when $\epsilon=0.1$, while other $\epsilon$ values are
competitive with the non-private GeoPointGAN; (b) private GeoPointGANs
sometimes outperform the non-private version; and (c) private GeoPointGANs
perform best with a middling $\epsilon$ value, though the exact value depends
on the city.

###  5.3. Facility Location Queries

Facility location is an example (of which there are many) of an end
application for our work. Facility location queries are more complex as they
are a combination of range and hotspot queries. We consider two variants: Max-
Inf and Min-Dist. In the Max-Inf case, we aim to select the most influential
candidate facilities, where influence is commonly defined as the total number
of customers that the facilities attract. The Min-Dist query instead selects
facilities that minimize the total distance between customers and the
facilities. For both queries, individual location data is needed to accurately
model the behaviors of potential customers, which motivates the use of models
like GeoPointGAN.

Outline. Imagine a hot dog salesperson that wishes to locate $k$ outlets
throughout Manhattan. Since more business could potentially be generated if
her outlets were located at the intersections of busy streets, we use the same
location set as used for the range queries (as this was a selection of road
intersections). Each $\pi\in\mathcal{P}$ represents a candidate facility, we
consider 100 facilities, and assume that there are no existing facilities.
$\mathcal{F_{\operatorname{r}}}$ and $\mathcal{F_{\operatorname{s}}}$ denote
the sets of selected facilities when the real and synthetic data is used,
respectively. To quantify similarity between $\mathcal{F_{\operatorname{r}}}$
and $\mathcal{F_{\operatorname{s}}}$, we use the SDC (Equation 6), using
$\mathcal{F}$ in place of $\mathcal{H}$. Our evaluation uses
$k=\\{1,5,10,20,50,75\\}$.

Results. Figure 7 shows the variation in SDC values for the Max-Inf query.
GeoPointGAN produces synthetic data that answers queries with high accuracy,
and the non-private GeoPointGAN performs exceptionally well in most cases,
especially in Porto for which it obtains near-optimal results. The effect of
changing the privacy budget is also noticeable, and we continue to see the
phenomenon of privatized versions of GeoPointGAN performing as well as non-
private versions. We conduct the same analysis for the Min-Dist query and
similarly strong results are obtained for all values of $\epsilon$ and $k$. We
omit the corresponding plots due to space limitations.

These strong results demonstrate the practical benefit of our approach and
illustrate that facility location can tolerate the noise that is inherent in
GAN-based sampling and that is required for label-LDP. This robustness can
also be exploited for other data science tasks, such as nearest neighbor
queries and clustering.

(a) Porto

(b) Beijing

(c) New York

Figure 7. Variation in SDC as $\bm{k}$ varies for the Max-Inf query

##  6\. Final Remarks

As demonstrated through our experiments, GeoPointGAN is a robust method for
generating large synthetic spatial datasets with practical levels of privacy
and high utility, both statistically and with respect to several location
analytics tasks. Indeed, in some settings, private GeoPointGANs perform better
than non-private versions – a remarkable and important observation. This
phenomenon is possible due to the design of our privacy mechanism, which
exploits the inherent noise in label flipping to harness the regularization
effects that can be realized when training GANs.

Beyond these findings, our work provides further insights about the level of
privacy provided. While GeoPointGAN demonstrably fulfills the requirements of
label-LDP, the actual level of privacy provided is higher in many practical
settings. As Malek et al. (2021) note, simply removing the sensitive labels of
a public dataset and training a model in an unsupervised fashion, complies
with label-(L)DP. We take this further by accounting for situations where,
even if we remove the identifier (e.g., taxi ID, 311 caller name), we are
still conscious of leaking information based on knowledge regarding the
veracity of each point (e.g., if locations can help to identify the caller).
Specifically, we use pseudo-labels (to denote whether points are real or fake)
to obfuscate the training data by removing certainty within the model as to
what input represents real data. In this sense, the level of privacy provided
is stronger than what is necessarily required with label-LDP, although
quantifying this achieved level of privacy is non-trivial. And, while this
level of privacy may not necessarily be strong enough to satisfy LDP in
theory, it may satisfy LDP to some extent in practice. We leave further
exploration of these ideas and challenges for future work.

Acknowledgments. This work is supported in part by the Sponsor UK Engineering
and Physical Sciences Research Council u under Grant No. Grant #EP/L016400/1.

## References

  * (1)
  * Achlioptas et al. (2018) Panos Achlioptas, Olga Diamanti, Ioannis Mitliagkas, and Leonidas Guibas. 2018.  Learning Representations and Generative Models for 3D Point Clouds. In _ICML_. 40–49.  http://proceedings.mlr.press/v80/achlioptas18a.html
  * Acs and Castelluccia (2014) Gergely Acs and Claude Castelluccia. 2014.  A Case Study: Privacy Preserving Release of Spatio-Temporal Density in Paris. In _ACM SIGKDD_. 1679–1688.  https://doi.org/10.1145/2623330.2623361
  * Akbari and Liang (2018) Mohammad Akbari and Jie Liang. 2018.  Semi-Recurrent Cnn-Based Vae-Gan for Sequential Data Generation. In _IEEE International Conference on Acoustics, Speech and Signal Processing_.  https://doi.org/10.1109/ICASSP.2018.8461724
  * Andrés et al. (2013) Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013\.  Geo-indistinguishability: differential privacy for location-based systems. In _ACM SIGSAC_. 901–914.  https://doi.org/10.1145/2508859.2516735
  * Arshad and Beksi (2020) Mohammad Samiul Arshad and William J. Beksi. 2020.  A Progressive Conditional Generative Adversarial Network for Generating Dense and Colored 3D Point Clouds. In _International Conference on 3D Vision_. 712–722.  https://doi.org/10.1109/3DV50981.2020.00081
  * Augenstein et al. (2019) Sean Augenstein, H. Brendan McMahan, Daniel Ramage, Swaroop Ramaswamy, Peter Kairouz, Mingqing Chen, Rajiv Mathews, and Blaise Agüera y Arcas. 2019\.  Generative Models for Effective ML on Private, Decentralized Datasets.  (2019).  arXiv:1911.06679
  * Beaulieu-Jones et al. (2019) Brett K. Beaulieu-Jones, Zhiwei Steven Wu, Chris Williams, Ran Lee, Sanjeev P. Bhavnani, James Brian Byrd, and Casey S. Greene. 2019\.  Privacy-Preserving Generative Deep Neural Networks Support Clinical Data Sharing.  _Circulation: Cardiovascular Quality and Outcomes_ 12, 7 (2019), e005122.  https://doi.org/10.1161/CIRCOUTCOMES.118.005122
  * Binnig et al. (2007) Carsten Binnig, Donald Kossmann, Eric Lo, and M. Tamer Özsu. 2007.  QAGen: Generating Query-Aware Test Databases. In _ACM SIGMOD_. 341–352.  https://doi.org/10.1145/1247480.1247520
  * Bruno and Chaudhuri (2005) Nicolas Bruno and Surajit Chaudhuri. 2005.  Flexible Database Generators. In _PVLDB_. VLDB Endowment, 1097–1107.
  * Busa-Fekete et al. (2021) Robert Istvan Busa-Fekete, Andres Munoz Medina, Umar Syed, and Sergei Vassilvitskii. 2021.  Population Level Privacy Leakage in Binary Classification wtih Label Noise. In _NeurIPS_.  https://openreview.net/forum?id=Gf2EuAB9Xj
  * Caccia et al. (2019) Lucas Caccia, Herke Van Hoof, Aaron Courville, and Joelle Pineau. 2019.  Deep Generative Modeling of LiDAR Data. In _IEEE International Conference on Intelligent Robots and Systems_.  https://doi.org/10.1109/IROS40897.2019.8968535
  * Chang et al. (2015) Angel X. Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu. 2015.  ShapeNet: An Information-Rich 3D Model Repository.  (2015).  http://arxiv.org/abs/1512.03012
  * Chaudhuri and Hsu (2011) Kamalika Chaudhuri and Daniel Hsu. 2011.  Sample Complexity Bounds for Differentially Private Learning. In _Conference on Learning Theory_ , Vol. 19. PMLR, 155–186.  https://proceedings.mlr.press/v19/chaudhuri11a.html
  * Chen et al. (2018) Liqun Chen, Shuyang Dai, Chenyang Tao, Dinghan Shen, Zhe Gan, Haichao Zhang, Yizhe Zhang, and Lawrence Carin. 2018\.  Adversarial text generation via feature-mover’s distance. In _NeurIPS_.
  * Chen et al. (2012) Rui Chen, Benjamin C.M. Fung, Bipin C. Desai, and Nériah M. Sossou. 2012.  _Differentially Private Transit Data Publication: A Case Study on the Montreal Transportation System_.  213–221.  https://doi.org/10.1145/2339530.2339564
  * Chen et al. (2016) Rui Chen, Haoran Li, A. K. Qin, Shiva Prasad Kasiviswanathan, and Hongxia Jin. 2016.  Private spatial data aggregation in the local setting. In _IEEE ICDE_.  https://doi.org/10.1109/ICDE.2016.7498248
  * Cormode et al. (2012) Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. 2012.  Differentially Private Spatial Decompositions. In _IEEE ICDE_.  https://doi.org/10.1109/ICDE.2012.16
  * Cunningham et al. (2021a) Teddy Cunningham, Graham Cormode, and Hakan Ferhatosmanoglu. 2021a.  Privacy-Preserving Synthetic Location Data in the Real World. In _SSTD_.  https://doi.org/10.1145/3469830.3470893
  * Cunningham et al. (2021b) Teddy Cunningham, Graham Cormode, Hakan Ferhatosmanoglu, and Divesh Srivastava. 2021b.  Real-World Trajectory Sharing with Local Differential Privacy.  _PVLDB_ 14, 11 (2021).  https://doi.org/10.14778/3476249.3476280
  * Del Rey et al. (2020) Angel M. Del Rey, Xingxing Xiong, Shubo Liu, Dan Li, Zhaohui Cai, and Xiaoguang Niu. 2020\.  A Comprehensive Survey on Local Differential Privacy.  _Security and Communication Networks_ (2020).  https://doi.org/10.1155/2020/8829523
  * Dizaji et al. (2018) Kamran Ghasedi Dizaji, Xiaoqian Wang, and Heng Huang. 2018\.  Semi-supervised generative adversarial network for gene expression inference. In _ACM SIGKDD_.  https://doi.org/10.1145/3219819.3220114
  * Duchi et al. (2013) John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013.  Local Privacy and Statistical Minimax Rates. In _IEEE FOCS_. 429–438.  https://doi.org/10.1109/FOCS.2013.53
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential Privacy. In _Automata, Languages and Programming_. Springer Berlin Heidelberg, Berlin, Heidelberg, 1–12.
  * Esfandiari et al. (2021) Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. 2021.  Label differential privacy via clustering.  arXiv:2110.02159
  * Frigerio et al. (2019) Lorenzo Frigerio, Anderson Santana de Oliveira, Laurent Gomez, and Patrick Duverger. 2019\.  Differentially Private Generative Adversarial Networks for Time Series, Continuous, and Discrete Open Data. In _ICT Systems Security and Privacy Protection_. 151–164.
  * Gal et al. (2020) Rinon Gal, Amit Bermano, Hao Zhang, and Daniel Cohen-Or. 2020\.  MRGAN: Multi-Rooted 3D Shape Generation with Unsupervised Part Disentanglement.  arXiv:2007.12944
  * Gatrell et al. (1996) Anthony C. Gatrell, Trevor C. Bailey, Peter J. Diggle, and Barry S. Rowlingson. 1996.  Spatial Point Pattern Analysis and Its Application in Geographical Epidemiology.  _Transactions of the Institute of British Geographers_ (1996).  https://doi.org/10.2307/622936
  * Ge et al. (2021) Chang Ge, Shubhankar Mohapatra, Xi He, and Ihab F. Ilyas. 2021\.  Kamino: Constraint-Aware Differentially Private Data Synthesis.  arXiv:2012.15713 [cs.DB]
  * Geolink (2015) Geolink. 2015.  Taxi Service Trajectory Prediction Challenge @ ECML/PKDD 15 – Dataset.  Retrieved August 15, 2019 from http://www.geolink.pt/ecmlpkdd2015-challenge/dataset.html
  * Ghane et al. (2018) Soheila Ghane, Lars Kulik, and Kotagiri Ramamohanarao. 2018\.  Publishing Spatial Histograms under Differential Privacy. In _SSDBM_. Article 14\.  https://doi.org/10.1145/3221269.3223039
  * Ghazal et al. (2013) Ahmad Ghazal, Tilmann Rabl, Minqing Hu, Francois Raab, Meikel Poess, Alain Crolotte, and Hans-Arno Jacobsen. 2013.  BigBench: Towards an Industry Standard Benchmark for Big Data Analytics. In _ACM SIGMOD_. 1197–1208.  https://doi.org/10.1145/2463676.2463712
  * Ghazi et al. (2021) Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. 2021.  Deep Learning with Label Differential Privacy. In _NeurIPS_ , A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (Eds.).  https://openreview.net/forum?id=RYcgfqmAOHh
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014\.  Generative Adversarial Nets. In _NeurIPS_. 2672–2680.  http://papers.nips.cc/paper/5423-generative-adversarial-nets
  * Gu et al. (2015) Ling Gu, Minqi Zhou, Zhenjie Zhang, Ming-Chien Shan, Aoying Zhou, and Marianne Winslett. 2015\.  Chronos: An elastic parallel framework for stream benchmark generation and simulation. In _IEEE ICDE_. 101–112.  https://doi.org/10.1109/ICDE.2015.7113276
  * Gursoy et al. (2018) Mehmet Emre Gursoy, Ling Liu, Stacey Truex, and Lei Yu. 2018\.  Differentially private and utility preserving publication of trajectory data.  _IEEE Transactions on Mobile Computing_ 18, 10 (2018), 2315–2329.
  * Gursoy et al. (2020) Mehmet Emre Gursoy, Vivekanand Rajasekar, and Ling Liu. 2020\.  Utility-Optimized Synthesis of Differentially Private Location Traces.  arXiv:2009.06505
  * He et al. (2015) Xi He, Graham Cormode, Ashwin Machanavajjhala, Cecilia M Procopiuc, and Divesh Srivastava. 2015\.  DPT: differentially private trajectory synthesis using hierarchical reference systems.  _PVLDB_ 8, 11 (2015), 1154–1165.
  * Huang et al. (2019) Zhiqi Huang, Ryan McKenna, George Bissias, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. 2019.  PSynDB: Accurate and Accessible Private Data Generation.  _PVLDB_ 12, 12 (2019), 1918–1921.  https://doi.org/10.14778/3352063.3352099
  * Jaderberg et al. (2015) Max Jaderberg, Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu. 2015.  Spatial transformer networks. In _NeurIPS_.
  * Jiang et al. (2021) Liming Jiang, Bo Dai, Wayne Wu, and Chen Change Loy. 2021\.  Deceive D: Adaptive Pseudo Augmentation for GAN Training with Limited Data. In _NeurIPS_ , Vol. 34. 21655–21667.  https://proceedings.neurips.cc/paper/2021/file/b534ba68236ba543ae44b22bd110a1d6-Paper.pdf
  * Kaul et al. (2013) Manohar Kaul, Bin Yang, and Christian S. Jensen. 2013\.  Building accurate 3D spatial networks to enable next generation intelligent transportation systems. In _IEEE Mobile Data Management_.  https://doi.org/10.1109/MDM.2013.24
  * Klemmer et al. (2019) Konstantin Klemmer, Adriano Koshiyama, and Sebastian Flennerhag. 2019.  Augmenting correlation structures in spatial data using deep generative models.  (may 2019).  arXiv:1905.09796 http://arxiv.org/abs/1905.09796
  * Klemmer and Neill (2021) Konstantin Klemmer and Daniel B. Neill. 2021.  Auxiliary-task learning for geographic data with autoregressive embeddings. In _SIGSPATIAL: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems_.
  * Klemmer et al. (2022) Konstantin Klemmer, Tianlin Xu, Beatrice Acciaio, and Daniel B. Neill. 2022.  SPATE-GAN: Improved Generative Modeling of Dynamic Spatio-Temporal Patterns with an Autoregressive Embedding Loss. In _AAAI 2022 - 36th AAAI Conference on Artificial Intelligence_.  arXiv:2109.15044v1
  * Li et al. (2018) Chun-Liang Li, Manzil Zaheer, Yang Zhang, Barnabas Poczos, and Ruslan Salakhutdinov. 2018\.  Point Cloud GAN.  (2018).  arXiv:1810.05795
  * Li et al. (2019) Ruihui Li, Xianzhi Li, Chi Wing Fu, Daniel Cohen-Or, and Pheng Ann Heng. 2019.  PU-GAN: A point cloud upsampling adversarial network. In _IEEE ICCV_.  https://doi.org/10.1109/ICCV.2019.00730
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization. In _ICLR_.  arXiv:1711.05101
  * Machanavajjhala et al. (2008) Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. 2008.  Privacy: Theory meets Practice on the Map. In _IEEE ICDE_. 277–286.  https://doi.org/10.1109/ICDE.2008.4497436
  * Malek et al. (2021) Mani Malek, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramèr. 2021.  Antipodes of Label Differential Privacy: PATE and ALIBI.  arXiv:2106.03408
  * Mohammed et al. (2011) Noman Mohammed, Rui Chen, Benjamin C.M. Fung, and Philip S. Yu. 2011\.  Differentially Private Data Release for Data Mining. In _ACM SIGKDD_. 493–501.  https://doi.org/10.1145/2020408.2020487
  * New York City Open Data (2020) New York City Open Data. 2020\.  311 Service Requests from 2010 to Present.  Retrieved January 23, 2020 from https://data.cityofnewyork.us/browse?q=311
  * Nguyen et al. (2019) Duc Tam Nguyen, Chaithanya Kumar Mummadi, Thi Phuong Nhung Ngo, Thi Hoai Phuong Nguyen, Laura Beggel, and Thomas Brox. 2019\.  Self: Learning to filter noisy labels with self-ensembling.  arXiv:1910.01842
  * Qi et al. (2017) Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. 2017\.  PointNet: Deep learning on point sets for 3D classification and segmentation. In _IEEE CVPR_.  https://doi.org/10.1109/CVPR.2017.16
  * Qu et al. (2020) Youyang Qu, Shui Yu, Wanlei Zhou, and Yonghong Tian. 2020\.  GAN-Driven Personalized Spatial-Temporal Private Data Sharing in Cyber-Physical Social Systems.  _IEEE Transactions on Network Science and Engineering_ 7, 4 (oct 2020), 2576–2586.  https://doi.org/10.1109/TNSE.2020.3001061
  * Salimans et al. (2016) Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen. 2016.  Improved Techniques for Training GANs. In _Advances in Neural Information Processing Systems_ , D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Eds.), Vol. 29. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2016/file/8a3363abe792db2d8761d6403605aeb7-Paper.pdf
  * Sarmad et al. (2019) Muhammad Sarmad, Hyunjoo Jenny Lee, and Young Min Kim. 2019\.  RL-GAN-net: A reinforcement learning agent controlled gan network for real-time point cloud shape completion. In _IEEE CVPR_.  https://doi.org/10.1109/CVPR.2019.00605
  * Shu et al. (2019) Dongwook Shu, Sung Woo Park, and Junseok Kwon. 2019\.  3D point cloud generative adversarial network based on tree structured graph convolutions. In _IEEE ICCV_.  https://doi.org/10.1109/ICCV.2019.00396
  * Torfi et al. (2020) Amirsina Torfi, Edward A. Fox, and Chandan K. Reddy. 2020\.  Differentially Private Synthetic Medical Data Generation using Convolutional GANs.  arXiv:2012.11774
  * Torkzadehmahani et al. (2019) Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten. 2019\.  DP-CGAN: Differentially Private Synthetic Data and Label Generation. In _IEEE CVPR_.
  * Torlak (2012) Emina Torlak. 2012\.  Scalable Test Data Generation from Multidimensional Models. In _ACM SIGSOFT_.  https://doi.org/10.1145/2393596.2393637
  * Velázquez et al. (2016) Eduardo Velázquez, Isabel Martínez, Stephan Getzin, Kirk A. Moloney, and Thorsten Wiegand. 2016\.  An evaluation of the state of spatial point pattern analysis in ecology.  https://doi.org/10.1111/ecog.01579
  * Wang and Xu (2019) Di Wang and Jinhui Xu. 2019\.  On Sparse Linear Regression in the Local Differential Privacy Model. In _ICML_ , Vol. 97. PMLR, 6628–6637.  https://proceedings.mlr.press/v97/wang19m.html
  * Wang et al. (2020) Shuo Wang, Carsten Rudolph, Surya Nepal, Marthie Grobler, and Shangyu Chen. 2020.  PART-GAN: Privacy-Preserving Time-Series Sharing. In _Artificial Neural Networks and Machine Learning_. 578–593.
  * Warner (1965) Stanley L. Warner. 1965\.  Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias.  _J. Amer. Statist. Assoc._ 60, 309 (1965), 63–69.  https://doi.org/10.1080/01621459.1965.10480775
  * Xiao et al. (2017) Shuai Xiao, Mehrdad Farajtabar, Xiaojing Ye, Junchi Yan, Le Song, and Hongyuan Zha. 2017\.  Wasserstein Learning of Deep Generative Point Process Models. In _NeurIPS_. 3247–3257.  http://papers.nips.cc/paper/6917-wasserstein-learning-of-deep-generative-point-process-models
  * Xiao and Xiong (2015) Yonghui Xiao and Li Xiong. 2015.  Protecting Locations with Differential Privacy under Temporal Correlations. In _ACM SIGSAC_. 1298–1309.  https://doi.org/10.1145/2810103.2813640
  * Xie et al. (2018) Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. 2018.  Differentially Private Generative Adversarial Network.  (2018).  arXiv:1802.06739 http://arxiv.org/abs/1802.06739
  * Xie et al. (2016) Lingxi Xie, Jingdong Wang, Zhen Wei, Meng Wang, and Qi Tian. 2016.  DisturbLabel: Regularizing CNN on the loss layer. In _IEEE CVPR_.  https://doi.org/10.1109/CVPR.2016.514
  * Xiong et al. (2019) Xingxing Xiong, Shubo Liu, Dan Li, Jun Wang, and Xiaoguang Niu. 2019.  Locally differentially private continuous location sharing with randomized response.  _International Journal of Distributed Sensor Networks_ 15, 8 (2019).  https://doi.org/10.1177/1550147719870379
  * Yoon et al. (2019) Jinsung Yoon, James Jordon, and Mihaela van der Schaar. 2019\.  PATE-GAN: Generating Synthetic Data with Differential Privacy Guarantees. In _ICLR_.  https://openreview.net/forum?id=S1zk9iRqF7
  * Yuan et al. (2011) Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. 2011\.  Driving with knowledge from the physical world. In _ACM SIGKDD_. 316.  https://doi.org/10.1145/2020408.2020462
  * Yuan et al. (2010) Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang. 2010.  T-drive: driving directions based on taxi trajectories. In _ACM SIGSPATIAL_. 99\.  https://doi.org/10.1145/1869790.1869807
  * Yuan et al. (2021) Sen Yuan, Milan Shen, Ilya Mironov, and Anderson C. A. Nascimento. 2021.  Practical, Label Private Deep Learning Training based on Secure Multiparty Computation and Differential Privacy.  Cryptology ePrint Archive, Report 2021/835.  https://ia.cr/2021/835
  * Zhang et al. (2017) Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2017\.  PrivBayes: Private Data Release via Bayesian Networks.  _ACM Trans. Database Syst._ 42, 4 (2017).  https://doi.org/10.1145/3134428
  * Zhang et al. (2020) Yingxue Zhang, Yanhua Li, Xun Zhou, Xiangnan Kong, and Jun Luo. 2020.  Curb-GAN: Conditional Urban Traffic Estimation through Spatio-Temporal Generative Adversarial Networks. In _ACM SIGKDD_.  https://doi.org/10.1145/3394486.3403127
  * Zhang et al. (2021) Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021\.  PrivSyn: Differentially Private Data Synthesis. In _USENIX Security Symposium_.  https://www.usenix.org/conference/usenixsecurity21/presentation/zhang-zhikun
  * Zhou et al. (2020) Hang Zhou, Dongdong Chen, Jing Liao, Kejiang Chen, Xiaoyi Dong, Kunlin Liu, Weiming Zhang, Gang Hua, and Nenghai Yu. 2020.  LG-GAN: Label Guided Adversarial Network for Flexible Targeted Attack of Point Cloud Based Deep Networks. In _IEEE CVPR_.  https://doi.org/10.1109/CVPR42600.2020.01037
  * Zuo et al. (2009) Renguang Zuo, Frederik P. Agterberg, Qiuming Cheng, and Lingqing Yao. 2009.  Fractal characterization of the spatial distribution of geological point processes.  _International Journal of Applied Earth Observation and Geoinformation_ (2009).  https://doi.org/10.1016/j.jag.2009.07.001