# Smooth Anonymity for Sparse Binary Matrices

Hossein Esfandiari
Google Research  Alessandro Epasto
Google Research  Vahab Mirrokni
Google Research  Andres Munoz Medina
Google Research  Sergei Vassilvitskii
Google Research

###### Abstract

When working with user data providing well-defined privacy guarantees is
paramount. In this work we aim to manipulate and share an entire sparse
dataset with a third party privately. In fact, differential privacy has
emerged as the gold standard of privacy, however, when it comes to sharing
sparse datasets, as one of our main results, we prove that _any_
differentially private mechanism that maintains a reasonable similarity with
the initial dataset is doomed to have a very weak privacy guarantee. Hence we
need to opt for other privacy notions such as $k$-anonymity are better at
preserving utility in this context. In this work we present a variation of
$k$-anonymity, which we call smooth $k$-anonymity and design simple algorithms
that efficiently provide smooth $k$-anonymity. We further perform an empirical
evaluation to back our theoretical guarantees, and show that our algorithm
improves the performance in downstream machine learning tasks on anonymized
data.

##  1 Introduction

In fact, when working with user data, maintaining user privacy is absolutely
essential. In this work we study a situation where we intend to share an
entire (manipulated) dataset, without violating user privacy. Then the dataset
might be used by the public for several different purposes. Hence, to measure
the accuracy regardless of the downstream task, we use a general purpose
metric to measure the similarity of the initial dataset with the shared
dataset. To measure the privacy there are a large body of work that attempt to
provide formal privacy measures. At a high level, there are two distinct
approaches to quantifying privacy, differential privacy and $k$-anonymity.

Differential privacy is a property of a data processing algorithm and it
ensures that small changes in input (typically the presence or absence of any
individual user) lead to minimal changes in the output. All differentially
private algorithms are randomized, and the uncertainty introduced by the
randomization provides a layer of protection. On the other hand, $k$-anonymity
is a property of the dataset. To make a dataset $k$-anonymous one either
generalizes or removes data that is identifiable, so that in the final dataset
any information is shared by at least $k$ distinct users. Both approaches have
their own pros and cons, which we briefly discuss next. (We defer the formal
definitions to Section 3.)

The main advantage of differential privacy is that the output of a
differentially private algorithm remains such even in the face of arbitrary
post-processing by an adversary armed with additional side information about
the users. This is one reason why it has emerged as the gold standard of
privacy. However, as we share more information the differential privacy
measure gets weaker. In this work we prove that sharing sparse binary matrices
with differential privacy guarantees is infeasible (See Theorem 4.3). Roughly
speaking, we prove that any differentially private algorithm either provides a
very weak privacy guarantee, or significantly changes the dataset, destroying
the underlying signal.

On the other hand, $k$-anonymity Sweeney (2002) is a popular pre-processing
technique that can be used to provide some level of privacy. While
$k$-anonymity can be vulnerable to certain attacks Ranjit et al. (2008), it
still provides meaningful guarantees when adversaries have limited access to
side information Bassily et al. (2013). Moreover, in cases where a data
analyst cannot withstand noise, it still represents a formal way to give
privacy protections. Making a dataset $k$-anonymous while best preserving
utility is an NP-hard problem Aggarwal et al. (2005). Current approximation
algorithms offer the guarantee of removing at most $O(\log(k))$ times more
elements than that of an optimal solution, however, such a bound is vacuous
when the optimal solution has to remove a constant fraction of the dataset (or
anything smaller than a $1-O\left(\frac{1}{\log\left(k\right)}\right)$
fraction). In those cases the algorithm that just returns a null dataset
achieves the same guarantee.

In this work, we strive to design an approach for sharing a binary matrix,
while respecting the privacy of the users. In order to do this we study a
variant of $k$-anonymity (called smooth-$k$-anonymity). Then we provide a
polynomial-time approximation algorithm for smooth-$k$-anonymity in binary
matrices and in theory improve the approximation guarantees of the state of
the art results for $k$-anonymization.

In the binary matrix representation, each row represents the data of one user
and each column corresponds to a feature, and if the user $u$ has the feature
$f$, element $(u,f)$ in the matrix is $1$. This representation captures the
following common setups:
Bipartite Graphs: The nodes of one side correspond to the users and the nodes
of the other side corresponds to the features. If user $u$ has feature $f$,
there is an edge between $u$ and $f$.
User Lists: We have a collection of lists of users, and each list is
associated with a feature. If user $u$ has feature $f$, user $u$ exists in the
list associated with $f$.
Points in a Binary Space: Each user is associated with a point. The
coordinates of the point are equivalent to the respective row in the matrix
representation.

##  2 Related work

The problem of anonymizing data is very well studied. One of the first
techniques for anonymizing data sets was $k$-anonymity Sweeney (2002). This
notion was intended for tabular data where each row corresponds to a user and
each column corresponds to a particular feature. The authors define
$k$-anonymity in terms of quasi-identifiers. That is, columns in the data set
that, combined, could single out a user. A $k$-anonymous dataset is one where
every user is indistinguishable from $k$-other users with respect to the
quasi-identifier set only (that means that the columns not corresponding to
quasi-identifiers are not anonymized). Other works have improved upon this
definition by enforcing other restrictions such as requiring $l$-diversity
Machanavajjhala et al. (2007) or $t$-closeness Li et al. (2007) for non quasi-
identifiers, on top of $k$-anonymity for quasi-identifiers. The choice of
quasi-identifiers is crucial since an attacker with just a small amount of
information about a user could de-anonymize a dataset Narayanan and Shmatikov
(2008).

The majority of work on $k$-anonymity has been focused on finding the optimal
$k$-anonymous dataset. That is, one that approximates the original data the
best. Meyerson and Williams (2004) showed that this task is in fact NP-hard,
although it admits a $O(k\log k)$ approximation with running time exponential
in $k$. Later on, Aggarwal et al. (2005) obtained a polynomial time
approximation of $O(k)$ which was improved by Kenig and Tassa (2012); Park and
Shim (2010) to a $O(\log k)$ approximation. Several variants of these
algorithms including using set cover approximations Wang et al. (2010). In
addition to these algorithms with provable guarantees, other work has provided
heuristics for different notions of anonymization. For instance LeFevre et al.
(2006) has defined a heuristic algorithm for k-anonymization of quasi-
identifiers based on the construction similar to that of kd-trees Friedman et
al. (1977). Other authors have defined heuristics based on clustering Byun et
al. (2007); Zheng et al. (2018). None of those methods have provable
guarantees in our context.

Another related work to ours is that of Cheng et al. (2010), which defines the
notion of $k$-isomorphism in social network graphs. Essentially, a graph is
$k$-isomorphic if it can be decomposed into a union of $k$ distinct isomorphic
sub-graphs. This notion of anonymity is limited to social network graphs as
the goal is to prevent an attacker from identifying a user based on the
structure of their neighborhood.

A different framework for achieving anonymity is differential privacy Dwork
and Roth (2014). Unlike $k$-anonymity, differential privacy provides
mathematical guarantees on the amount of information that can be gained by an
attacker that observes a differentially private dataset. Differential privacy
has been effectively applied for statistics release Dwork and Smith (2010) and
empirical risk minimization Chaudhuri et al. (2011) among many other
scenarios. The vast majority of differential privacy examples require the
mechanism to output a summarized version of the data: a statistic or a model
in the case of risk minimization. To release a full dataset in a
differentially private manner, Kasiviswanathan et al. (2011) introduces the
notion of local differential privacy. Local differential privacy allows us to
release a full dataset while protecting the information of all users.

Methods from differential privacy have also been used for the release of
private graph information. For instance, Nissim et al. (2007) shows how to
compute the minimum spanning trees and the number of triangles in a graph.
Eliáš et al. (2020) recently showed how to preserve cuts in graphs with
differential privacy.

Kasiviswanathan et al. (2013) introduce the notions of edge and node
differential privacy in graph settings and show how to calculate functions
over graphs under node differential privacy by capping the number of edges per
node. Arguably the work most related to this paper is that of Nguyen et al.
(2016). The authors propose edge-differential privacy in order to release an
anonymous graph. Similar to our results in Corollary 4.2, the authors show
that a value of $\epsilon$ in $\Omega(\log n)$ is needed in order to achieve
non-trivial utility guarantees, where $n$ is the number of nodes in the graph.

We observe that some work has been devoted to combining differential privacy
with k-anonymity guarantees. Li et al. (2011) show that enforcing
$k$-anonymity in certain data-oblivious ways on a sub-sampled dataset, is
sufficient to show differential privacy guarantees.

Our algorithmic techniques are related to the lower bounded facility location
problem Ahmadian and Swamy (2012); Guha et al. (2000); Svitkina (2010). This
problem has been first introduced and studied independently by Karget and
Minkoff (2000) and Guha et al. (2000). Lower bounded clustering problems have
been motivated by privacy purposes Motwani and Nabar (2008). They both provide
bicriteria approximation algorithms for this problem. Later, Svitkina (2010)
provided a $448$-approximation algorithm for this problem. This is the first
constant approximation algorithm for this problem. Ahmadian and Swamy (2012)
improved Svitkina’s result and give an $82.6$ approximation algorithm for this
problem. To the best of our knowledge the latter is the best approximation
algorithm for the lower bounded facility location problem.

##  3 Setup

Given the equivalence of binary matrices and bipartite graphs, for ease of
notation we mostly use graph theoretical terminology to describe our work. We
assume we are given a bipartite graph, where one set of nodes corresponds to
users and another set of nodes corresponds to features. This is a common
modeling step, for instance in location analysis applications the features may
represent places visited; in social network modeling, the features may
represent interests shared by different users; and so on.

Let $U=\\{u_{1},\ldots,u_{n}\\}$ denote a set of users and
$F=\\{f_{1},\ldots,f_{m}\\}$ a set of features. Throughout the paper we use
$n$ and $m$ as the $|U|$ and $|F|$, respectively. The edge set $E$ of the
graph is defined as follows, given $u\in U$ and $f\in F$, we say $e=(u,f)\in
E$ if user $u$ is associated with item $f$. We denote this graph by $G=(U\cup
F,E)$. Let $\mathbb{G}$ denote the space of all bipartite graphs over $U\cup
F$, a mechanism $\mathcal{M}\colon\mathbb{G}\to\mathbb{G}$ is a (possibly
randomized) function that maps $G=(U\cup F,E)$ to another graph
$G^{\prime}=(U\cup F,E^{\prime})$ with the same set of nodes but with possibly
different edges. Throughout the paper given two sets $A$ and $B$ we denote
their symmetric difference by $A\oplus B$.

We now introduce the different notions of privacy we will be using throughout
the paper.

######  Definition 3.1.

Edge differential privacy. We say a randomized mechanism $\mathcal{M}$
preserves $\epsilon$-edge differential privacy if for any two graphs $G=(U\cup
F,E)$ and $G^{\prime}=(U\cup F,E^{\prime})$ such that $|E\oplus E^{\prime}|=1$
the following holds for all $A\subset\mathbb{G}$:

$P(\mathcal{M}(G)\in A)\leq e^{\epsilon}P(\mathcal{M}(G^{\prime})\in A),$

Edge differential privacy implies that the output of a mechanism does not
change too much if a single edge of the input graph is changed. Thus an
adversary that observes the output of $\mathcal{M}(G)$ may not be able to
infer if a single edge was present or not in the graph.

However, if a user has a high degree in $G$, then the output of an edge-
differentially private algorithm may still leak information about the presence
or absence of that user in the graph. This leads to a definition of node-
differential privacy which we detail below.

######  Definition 3.2.

We say that two graphs $G=(U\cup F,E),G^{\prime}=(U\cup
F,E^{\prime})\in\mathbb{G}$ are node neighboring if there exists $u\in U$ such
that $|E\oplus E^{\prime}|=|\\{e\in E\colon e=(u,f)\ \text{for }\ f\in
F\\}\oplus\\{e\in E^{\prime}\colon e=(u,f)\ \text{for }\ f\in F\\}$

That is, two graphs are node neighboring if one can be obtained from the other
by replacing all the edges of a single user.

######  Definition 3.3 (Node differential privacy).

We say a mechanism $\mathcal{M}$ preserves node differential privacy if for
any two node neighboring graphs $G$ and $G^{\prime}$ and for all
$A\subset\mathbb{G}$

$P(\mathcal{M}(G)\in A)\leq e^{\epsilon}P(\mathcal{M}(G^{\prime})\in A).$

Under this notion of anonymity, it is very unlikely for an adversary to
identify a user in a particular dataset. While the above notions of
differential privacy provide quantifiable protection against an attacker, as
we will see, they also require adding a non-trivial amount of noise.

For this reason we revisit an older notion of privacy: $k$-anonymity. While
the original definition of $k$-anonymity Sweeney (2002) requires defining
quasi-identifiers, in this work we assume that every feature can be used as a
quasi-identifier.

We first introduce some notation. We will consider graphs in $\mathbb{G}$ with
fixed node sets $U\cup F$, and varying edge sets. Let $G=(U\cup
F,E)\in\mathbb{G}$ be one such graph, notice that the graph is identified by
$E$. For a given edge set $E$, let $F_{u}(E)=\\{f\in F\colon(u,f)\in E\\}$ be
the items associated with $u$ in the set edge set $E$. Notice we can then
partition users into equivalence classes. Formally, let

$C_{u}(E)=\\{u^{\prime}\in U|F_{u}(E)\equiv F_{u^{\prime}}(E)\\}.$

Now we are ready to formally define $k$-anonymity by suppression.

######  Definition 3.4 ($k$-anonymization and $k$-anonymization by
suppression).

A mechanism $\mathcal{M}$ is $k$-anonymous if for any graph $G=(U\cup
F,E)\in\mathbb{G}$, $\mathcal{M}(G)=(U\cup F,E^{\prime})$ satisfies:

  1. 1.

For every $u\in U$, $|C_{u}(E^{\prime})|\geq k$.

The mechanism $\mathcal{M}$ is $k$-anonymous by suppression if it also
satisfies

  1. 1.

$E^{\prime}\subset E$

That is the set of items associated with each user in the output graph, is the
same of that of at least $k$ users. Moreover, in $k$-anonymity with
suppression the output set of edges $E^{\prime}$ needs to be a subset of $E$.
Notice that with a $k$-anonymous output an adversary can only distinguish a
user up to a set of $k$ different people.

Finally, we introduce our variant of the above definition.

######  Definition 3.5 (smooth-$k$-anonymity).

A mechanism $\mathcal{M}$ is smooth-$k$-anonymous if for any graph $G=(U\cup
F,E)\in\mathbb{G}$, $\mathcal{M}(G)=(U\cup F,E^{\prime})$ satisfies:

  1. 1.

For every $u\in U$, $|C_{u}(E^{\prime})|\geq k$.

  2. 2.

For every $u\in U$, and every $f\in F$, $(u,f)\in E^{\prime}$ implies
$|\\{u^{\prime}\in C_{u}(E^{\prime})\colon(u^{\prime},f)\in
E^{\prime}\\}|\geq\nicefrac{{|C_{u}(E^{\prime})|}}{{2}}$

This definition is very similar to Definition 3.4. The main difference between
the definitions is that a smooth-$k$-anonymous mechanism is only allowed to
add edges to the output if, for each equivalence class of users and each item
connected to them, the majority of such edges belong to the original graph.
Figure 1 we depict the difference between our smooth-$k$-anonymous and
k-anonymity with suppression.

Figure 1: Depiction of $k$-anonymity with suppression and smooth-$k$-anonymity
for $k=4$. (left) Original input graph $G$. (center) $k$-anonymous with
suppression graph. Notice the removal of the edges to the first and last
feature. (right) smooth-$k$-anonymous graph, we preserve the edges to the
first feature and add a new edge to it.

We conclude this section by defining the utility measure of a mechanism. In
order for a mechanism to be useful it should preserve as much as possible of
the graph structure. In this paper we measure this by the Jaccard similarity
of two graphs.

######  Definition 3.6.

Given two graphs $G=(U\cup F,E),G^{\prime}=(U\cup F,E^{\prime})$ we denote the
Jaccard similarity of them by $J(G,G^{\prime}):=\frac{|E\cap
E^{\prime}|}{|E\cup E^{\prime}|}$.

##  4 Comparison of privacy notions

In this paper we introduce the new algorithmic problem of finding the best
smooth-k-anonymization of a graph. For this reason, in this section, we
provide some comparison between smooth-$k$-anonymity and alternative privacy
notions that can be used for data release.

###  4.1 Comparison with differential privacy

Node differential privacy As we have briefly discussed, node-differential
privacy provides the best theoretical guarantees for privacy protection. In
the specifics of our setup, node-differential privacy is equivalent to the so-
called _local_ differential privacy Kasiviswanathan et al. (2011), where every
user is acting separately without coordination from some global authority.

Let $G=(U\cup F,E)$, borrowing from local differential privacy ideas, one way
of achieving node differential privacy is by releasing $\mathcal{M}(G)=(U\cup
F,E^{\prime})$ built according to Algorithm 1. The algorithm is parameterized
by a randomized response probability $p$. It is not hard to show that in order
to achieve $\epsilon$-node differential privacy
$p=\frac{2}{1+e^{\frac{\epsilon}{|F|}}}$. Notice that this value converges to
$1$ exponentially fast as a function of the size of the feature set $F$. That
is, even for relatively small graphs, in order to achieve any meaningful
privacy guarantee, the probability of returning a completely random graph is
very close to $1$. For this reason, this notion is not amenable to be used
with good utility in our setting.

Algorithm 1 Randomized response

Input: $G=(U\cup F,E)$, randomized response prob. $p$

Output: anonymized graph $G^{\prime}=(U\cup F,E^{\prime})$.

for $u\in U,f\in F$

Sample $Y\sim\textrm{Bernoulli}(p)$

if $Y=1$ then $(u,f)\in E^{\prime}$ with probability $1/2$.

else if  $(u,f)\in E$ then $(u,f)\in E^{\prime}$

Edge differential privacy Algorithm 1 can also be used to define a mechanism
$\mathcal{M}$ that is edge differential privacy. In that case one can achieve
$\epsilon$-edge differential privacy by setting $p=\frac{2}{1+e^{\epsilon}}$
(see Appendix B.1 ).

In this section fist we consider Algorithm 1 as a natural way to provide
differential privacy and upper bound the Jaccard similarity of the input and
the output graphs of this algorithm. Later in this section we show that a
similar bound holds for all differential privacy algorithms.

Figure 2: The $\epsilon$ necessary for a given Jaccard, as a function of
density

.

We now upper bound the similarity of the output of the algorithm with
$\epsilon$-edge differential privacy. The bound depends on the density
$\lambda$ of the graph $G$ defined as: $\lambda(G)=\frac{|E|}{|U||F|}.$ The
proof of this theorem is available in Appendix 4.1 .

######  Theorem 4.1.

Let $G=(U\cup F,E)\in\mathbb{G}$ be a graph, $\delta>0$. Let $\mathcal{M}$ be
a mechanism that generates a graph according to Algorithm 1 with
$p=\frac{2}{1+e^{\epsilon}}$. Let $Q=|U||F|$ and
$C(\delta)=\frac{\log(2/\delta)}{2}$. If
$\frac{p}{4}\geq\sqrt{\frac{C(\delta)}{Q}}$, then with probability at least
$1-\delta$:

$J(\mathcal{M}(G),G)\leq\frac{1-\frac{1}{e^{\epsilon}+1}}{1+\frac{1}{e^{\epsilon}+1}\frac{1-\lambda}{\lambda}}+2\sqrt{\frac{C(\delta)}{Q}},$

where $\lambda:=\lambda(G)$.

Using Theorem 4.1, we can plot in Figure 2 a lower bound for the $\epsilon$
needed to achieve a certain level of Jaccard similarity utility, given a
density factor $\lambda$. Notice that for reasonably sparse datasets, say
graphs with density around $1/10{,}000$, one needs an $\epsilon$ higher than
$10$ to obtain a Jaccard Similarity of more than $50\%$. This result will be
confirmed in Section 6 in our empirical analysis.

The previous Theorem allows us to derive the following.

######  Corollary 4.2.

If the average degree of the input graph is $O(m^{0.99})$, for any
$\epsilon\in o(\log m)$, $\epsilon$-DP gives a solution with Jaccard
similarity of $o(1)$.

This means that, when the average user-degree is poly-logarithmic (or even
$m^{0.99}$) we need $\epsilon\in\Omega(\log m)$ to achieve a constant Jaccard
similarity with $\epsilon$-edge differential privacy. It is well-known that
many real-world matrix datasets are sparse. For instance in the context of
real-world networks, classical theoretical models Albert and Barabási (2002)
as well as empirical studies Backstrom et al. (2012); Leskovec et al. (2007)
postulate constant average degree or degrees growing slower than the size of
the graph.

The above results show that using randomized response, any differentially
private approximation to a graph with high utility requires an exceptionally
large value of $\epsilon$, thus rendering void any privacy guarantees. Later
in Theorem 4.3 we show a similar bound on $\epsilon$ for all differentially
private algorithms. In fact, for such a high $\epsilon$, the algorithm likely
maintains the graph $G$ unmodified thus exposing users to re-identification
risks. For this reason we believe $k$-anonymity might in fact provide better
protection in practice, especially in scenarios where our goal is to produce a
private version of the input graph with high utility.

Unfortunately, however, all of the previous work Aggarwal et al. (2005); Kenig
and Tassa (2012) provide non-trivial guarantees on the quality of a
$k$-anonymous mechanism only when $J(E,E_{\textrm{Opt}})\geq 1-O(\frac{1}{\log
k})$, in other words when very few edges need to be removed, as the similarity
between the graph and the optimal $k$-anonymous graph is very high. By
contrast, we show in Section 5 one can achieve a constant approximation to the
optimal smooth-$k$-anonymous solution in less restrictive scenarios.

Hardness of Differential Privacy So far in this section we analyzed randomized
response and show that this mechanism requires an unacceptably large
$\epsilon$. One may ask if there is any other $\epsilon$-differential privacy
mechanism with a small $\epsilon$ that guarantees the output to be similar to
the input. The following theorem rules out the existence of such a mechanism.
The proof of this theorem is presented in Appendix B.3 .

######  Theorem 4.3.

Let $\mathcal{M}$ be an arbitrary mechanism that satisfies $\epsilon$-edge
differential privacy. Let $\alpha$ be a parameter such that for any input
graph $G=(U\cup F,E)$, we have $\alpha\leq E[J(\mathcal{M}(G),G)]$. We have
$\epsilon\in\Omega\big{(}\log(\alpha^{2}nm)\big{)}.$

###  4.2 Comparison with $k$-anonymity by suppression

In this section we compare $k$-anonymity by suppression with
smooth-$k$-anonymity. First, in terms of privacy, we notice that both
smooth-$k$-anonymity and $k$-anonymity by suppression guarantee that every
user in the output is indistinguishable from at least $k$-users. Moreover,
observe that since smooth-$k$-anonymity is allowed to add edges to the output
graph, an attacker would not be certain whether an edge was in the original
graph or not.

We now show formally that the optimum solution of smooth-$k$-anonymity may
preserve a significantly larger fraction of the input data than regular
$k$-anonymity. To show this separation rigorously, we adopt the bipartite
stochastic block model (SBM), which is commonly used in modeling applications,
for instance in clustering and community detection Abbe (2017).

Bipartite Stochastic Block Model. To define the bipartite SBM, consider the
following random process. We have two sets of $n$ vertices, and each set is
further decomposed into $r$ blocks of size $s$, where $r\cdot s=n$. Each block
in the first part corresponds to one block of the second part. There is an
edge between each pair of vertices in two corresponding blocks independently
with probability $q$, and between every other pair of vertices with
probability $p$. We let $\alpha=qs$ denote the expected number of edges that
one node has to its corresponding block, a.k.a. _internal edges_. We let
$\beta=p(n-s)$ denote the expected number of edges that one node has to
vertices other than its corresponding block, a.k.a. _external edges_. We refer
to this as the stochastic block model with parameters $r,s,\alpha,\beta$.

The result that we provide in this section is of particular interest when the
blocks are not very sparse, i.e., $\alpha\in\omega(\frac{\log n}{\log 1/q})$
and $\alpha\in\Omega(\beta+s)$.

The next theorem upper bounds the number of edges in a (non-smooth)
$k$-anonymous subgraph of a graph generated by the stochastic block model by
$O(n\frac{\log n}{\log 1/q})$. Therefore, since $\alpha\in\omega(\frac{\log
n}{\log 1/q})$, the fraction of remaining edges tends to zero. The proof of
this theorem is presented in Appendix B.4 .

######  Theorem 4.4.

Let $G$ be a graph generated by the stochastic block model with parameters
$r,s,\alpha,\beta$. Let $k\geq\frac{2\log n}{\log 1/q}$. With probability
$99\%$, any $k$-anonymous subgraph of $G$ contains at most $\frac{2\log
n+10}{\log 1/q}n\in\tilde{O}(n)$ edges.

This allows us to show a gap with smooth-$k$-anonymization. In fact, a natural
solution that puts the vertices of each block in a cluster leads to a solution
for smooth-$k$-anonymity that in expectation keeps $\alpha n$ edges, adds
$(s-\alpha)n$ edges, and removes $\beta n$ edges. Since
$\alpha\in\Omega(\beta+s)$, the number of remaining edges $\alpha n$ is not
less than a constant factor of the changed edges. This result concerns the
optimum solution, but in the next section we provide an algorithm for
computing smooth-$k$-anonymization of a graph.

##  5 Algorithms and Analysis

In this section we develop algorithms that find a smooth-$k$-anonymization of
$G$. We say an algorithm $alg$ is $\alpha$-approximation if
$J(E,E_{alg})/J(E,E_{\textrm{Opt}})\geq\alpha$, where $E_{alg}$ is the output
of $alg$, $E_{\textrm{Opt}}$ is the optimal solution, and $J(\cdot,\cdot)$ is
the Jaccard similarity function. Our main contribution is captured by the
following theorem.

######  Theorem 5.1.

Assume $J(E,E_{\textrm{Opt}})\geq 0.75$. There exists an algorithm that finds
a constant approximate smooth-$k$-anonymization of $G$ in polynomial time.

At a high level, our algorithm will decompose users into clusters, each of
size at least $k$. Then in each cluster $c$, for each item $f$, if the
majority of the vertices in $c$ have an edge to $f$, we add edges to $f$ from
all nodes in $c$; otherwise we remove edges to $f$ from all nodes in $c$.

###  5.1 Preliminaries

Let us start with some preliminary notions and lemmas. We will abuse notation
slightly, and for a user $u$ and item $f$, say $u\in f$ if there is a $(u,f)$
edge in the graph.

Note that we can represent each user $u$ with a point in a $m$ dimensional
space. For an item $f_{i}$, we set the $i$-th dimension of $u$’s
representation to $1$ if $u\in f_{i}$ and to $0$ otherwise. In this space we
define the distance of two points, $u$ and $v$ to be the number of positions
where $u$ and $v$ differ (i.e. their Hamming distance).

Let $\Delta_{u}^{\textrm{Alg}}$ be the number of positions that the algorithm
Alg changes in the binary vector corresponding to the user $u$. Intuitively,
$\sum_{u}\Delta_{u}^{\textrm{Opt}}$ should be related to
$J(E,E_{\textrm{Opt}})$. The following lemma formalizes this intuition.

######  Lemma 5.2.

Assume $J(E,E_{\textrm{Opt}})\geq 1-\phi$. We have
$\sum_{u}\Delta_{u}^{\textrm{Opt}}\leq\frac{2\phi}{1-\phi}|E|$.

All proofs from this section are in Appendix C .

To complement Lemma 5.2, the following lemma lower bounds
$J(E,E_{\textrm{Alg}})$ given an upper bound on
$\sum_{u}\Delta_{u}^{\textrm{Alg}}$.

######  Lemma 5.3.

Assume $\sum_{u}\Delta_{u}^{\textrm{Alg}}\leq\phi^{\prime}|E|$. We have
$J(E,E_{\textrm{Alg}})\geq 1-\frac{\phi^{\prime}}{2}$.

###  5.2 Initial algorithm

We now provide an approximation algorithm using a reduction to _lower-bounded
$r$-median_111We use $r$-median instead of $k$-median to avoid the confusion
with the parameter $k$ in $k$-anonymity. We will use $r$ as the upper bound on
the number of clusters and $k$ as the lower bound for the size of the
clusters.. In the next subsection we improve it using a slightly more
complicated algorithm.

In the lower-bounded $r$-median problem we are asked to select at most $r$
centers from $n$ points and assign each point to one center such that (i) the
number of points assigned to each center is at least $k$, (ii) the total
distance of the points from their assigned centers is minimized. We refer to
each set of the points that are assigned to the same center as a cluster. In
this paper we let $r=n/k$, which means that the algorithm may use as many
centers as it needs, however, it must assign at least $k$ points to each
center222This means there are at most $n/k$ centers.. Here we use a $82.6$
approximation algorithm for lower-bounded $r$-median Ahmadian and Swamy
(2012), which is the best known result to the best of our knowledge. We refer
to this algorithm as $\textrm{Alg}_{1}$.

  1. 1.

Embed each user in $\mathbb{R}^{m}$ as described at the beginning of this
section.

  2. 2.

Approximately solve the lower-bounded $r$-median on the points (for
$r=\nicefrac{{n}}{{k}}$).

  3. 3.

For each cluster $c$, for each item $f$, if most vertices in $c$ have an edge
to $f$, add all edges from nodes in $c$ to $f$, otherwise remove all edges
from nodes in $c$ to $f$.

Note that by definition of lower-bounded $r$-median, each cluster contains at
least $k$ points. Moreover, the data that we output for users that belong to
the same cluster are the same. Hence, the output satisfies the anonymity part
of the smooth-$k$-anonymity condition. Moreover, the output satisfies the
majority part of the smooth-$k$-anonymity assumptions. Next we bound
$J(E,E_{\textrm{Alg}_{1}})$ assuming $J(E,E_{\textrm{Opt}})\geq 1-\phi$.

For analysis sake, we introduce the _relaxed lower-bounded $r$-median_ problem
in which we are allowed to select any possible discrete point in the space as
a center (as opposed to being restricted to select centers only from the
points that appear in the input). Note that, if we take a solution to relaxed
lower-bounded $r$-median and move each center to its closest point (that
appears in the input), by triangle inequality the cost of the solution
increases by at most a factor $2$. Therefore the cost of lower-bounded
$r$-median is at most twice that of relaxed lower-bounded $r$-median.

By Lemma 5.2 we have
$\sum_{u}\Delta_{u}^{\textrm{Opt}}\leq\frac{2\phi}{1-\phi}|E|$. We now prove
there exists a solution to relaxed lower-bounded $r$-median with cost at most
$\frac{2\phi}{1-\phi}|E|$. Take an optimal anonymous solution and consider the
equivalence classes of nodes with the same neighborhood. This induces a
clustering of the nodes with clusters of size at least $k$. Now, observe that
the total number of entries changed is equal to the sum of distances from the
output neighborhood (of each class) and the original nodes. So this shows that
there exists a clustering with sizes at least $k$ with total cost
$\sum_{u}\Delta_{u}^{\textrm{Opt}}$.

Therefore, there exists a solution to lower-bounded $r$-median with cost at
most $\frac{4\phi}{1-\phi}|E|$. Note that we are using an $82.6$-approximation
algorithm to find lower-bounded $r$-median. Hence, the total cost of our
solution is at most $\frac{330.4\phi}{1-\phi}|E|$. The last line of the
algorithm does not increase the total cost (since it selects the best center
for each cluster). Hence we have
$\sum_{u}\Delta_{u}^{\textrm{Alg}_{1}}\leq\frac{330.4\phi}{1-\phi}|E|$. By
applying this to Lemma 5.3 we have $J(E,E_{\textrm{Alg}_{1}})\geq
1-\frac{165.2\phi}{1-\phi}$. This is a positive constant for any $\phi\leq
0.006$. This implies the following theorem.

######  Theorem 5.4.

Assume $J(E,E_{\textrm{Opt}})\geq 0.994$. There exists an algorithm that finds
a constant approximation smooth-$k$-anonymization of $G$ in polynomial time.

Of course, having $J(E,E_{\textrm{Opt}})\geq 0.994$ is a very strong
assumption. Next we substantially relax this requirement.

###  5.3 Improved algorithm

To prove a better algorithm we will use the $1.488$ approximation algorithm
for the metric facility location problem Li (2013) as a subroutine. In the
metric facility location problem we are given a set of points and a set of
facilities in a metric space, with an opening cost for each facility. The
objective is to select a set of facilities and assign each point to a facility
such that the total cost of the selected facilities plus the total distance of
the points from their assigned facilities is minimized. Again here, we refer
to the set of points assigned to each facility as a cluster.

Below is our algorithm $\textrm{Alg}_{2}$. This algorithm depends on a
parameter $\alpha$ that we set later.

  1. 1.

Embed each user in $\mathbb{R}^{m}$ as before.

  2. 2.

For each user $u_{i}$ define a facility with the same coordinates and opening
cost $\frac{2\alpha}{1-\alpha}\sum_{u^{\prime}\in
U^{k}_{i}}\textrm{Dist}(u^{\prime},u_{i})$, where $U^{k}_{i}$ is the set of
$k$ closest points to $i$.

  3. 3.

Approximately solve the facility location instance.

  4. 4.

Iteratively, remove each cluster with fewer than $\alpha k$ points and assign
its points to their second closest facility.

  5. 5.

Arbitrarily merge clusters with size less than $k$ to reach size $k$, but do
not let the clusters grow larger than $2k$. 333If needed, break a large
cluster into some clusters of size at least $\alpha k$, so that the total size
of small clusters is more than $k$. This modification does not change the
proof.

  6. 6.

For each cluster $c$, for each item $f$, if most vertices in $c$ have an edge
to $f$, add all edges from nodes in $c$ to $f$, otherwise remove all edges
from nodes in $c$ to $f$.

######  Theorem 5.5.

Assume $J(E,E_{\textrm{Opt}})\geq 0.75$. Algorithm $\textrm{Alg}_{2}$ run with
an $\alpha\in O(1)$ finds a constant approximation to smooth-$k$-anonymization
of $E$ in polynomial time.

The proof of the theorem is in Appendix 5.5 .

(a) adult

(b) user-list

(c) $\epsilon$-edge DP

Figure 3: Mean Jaccard similarity for the various datasets and algorithms.

.

##  6 Experimental results

We give a brief overview of the empirical performance of our algorithms. We
give the full details of the setup as well as additional empirical results in
Appendix D . We will release an open-source version of our code by the camera-
ready deadline.

Datasets We used representative examples of sparse binary matrices (and
bipartite graphs) of different origins and structural properties. The scales
of the datasets are up to $>1B$ rows, $>100k$ columns, $>10B$ entries (for our
largest dataset) and the densities of the matrices range from $10^{-5}$ to
$0.1$. We used one synthetic dataset, four publicly-available real-world
datasets as well as one large-scale proprietary dataset from a major internet
company. These are as follows: stochastic is generated from the stochastic
block model described in Section 4.2;
adult444https://archive.ics.uci.edu/ml/datasets/adult and
playstore555https://www.kaggle.com/lava18/google-play-store-apps consist of
sparse binary matrices; dblp Yang and Leskovec (2015), stanford Leskovec et
al. (2009) consists of adjacency matrices of sparse bipartite graphs and,
user-lists is a proprietary dataset from a major internet company containing
user-interest relationships.

Metrics We measure utility using the Jaccard similarity between the set of the
edges as defined in the paper as well as the number of suppressed entries and
created entries.

Experimental infrastructure Our algorithm is implemented as a single-threaded
C++ problem and is run on standard commodity hardware, with the exception of
runs on the large-scale user-list dataset. For this dataset, we evaluated a
simple heuristic to parallelize our algorithm. (See Appendix D for more
details.)

Baselines and Algorithms As baselines we use the Mondrian anonymization
algorithm LeFevre et al. (2006)
implementation666https://github.com/qiyuangong/Mondrian which enforces
k-anonymity by suppression, as well as the randomized response algorithm of
Section 4 which enforces $\epsilon$ edge- or node-differential privacy. We
also compare our algorithm for smooth k-anonymization with an additional
baseline non-smooth (which uses a simple heuristic to obtain (standard)
k-anonymity by suppression using the clusters obtained by our algorithm). Our
algorithm is always run with $\alpha=1/2$, which in practice gives good
results for all datasets (we observe that values of $\alpha$ in $[1/8,1/2]$
have similar results).

dataset | algorithm | Jaccard | Supp. | Created
---|---|---|---|---
adult | mondrian | 59.9% | 40.1% | 0.0%
| non-smooth | 64.8% | 35.2% | 0.0%
| smooth | 85.0% | 8.9% | 7.2%
playstore | mondrian | 51.2% | 48.8% | 0.0%
| non-smooth | 39.2% | 60.8% | 0.0%
| smooth | 66.1% | 26.2% | 11.6%
user_lists | non-smooth | 67.3% | 32.7% | 0.0%
| smooth | 71.0% | 27.7% | 1.9%
Table 1: Average results for $k=8$ for various algorithms and dataset. Jac.,
S.E. and C.E. stand for, respectively, Jaccard similarity and fraction of
suppressed entries and newly created entries (both normalized by the entries
in the input dataset).

Jaccard similarity vs $k$ First, we evaluate the quality of our algorithm for
smooth $k$-anonymity for different $k$ values and we compare it with that of
the (non-smooth) k-anonymity solution and mondrian. In Figures 3(a) and 3(b)
we show a sample of plots of the mean Jaccard similarity for a given setting
of the $k$ parameter for smooth k-anonymity (solid line), non-smooth anonymity
(dashed line) and mondrian (dotted). We were not able to run the mondrian
algorithm on the larger datasets because, contrary to our algorithm, it scales
with the size of the full $n\times m$ matrix size ($m$ number of columns) and
it does not exploit the sparsity of the matrix. As expected, the Jaccard
similarity decreases with increasing $k$, but at every $k$ level smooth
k-anonymity allows to obtain significantly better results than all baselines
(in some cases even twice better). We report more detailed results in Table 1
for $k=8$. Notice that our smooth algorithm allows significantly higher
jaccard similarity (and lower suppressed entries) for a small increase in
created entries. For instance, in adult, the number of suppressed entries is
decreased by $\sim 26\%$ with just a $\sim 7\%$ increase in added entries.

Differential privacy We now evaluate the Jaccard similarity obtained by the
$\epsilon$-differentially private method. We report the results in Figure
3(c). Here we report results for the lower protection level of $\epsilon$-edge
differential privacy, as $\epsilon$-node differential privacy protection
generates results close to random outputs. As expected (see Section 4) the
sparser the dataset the worse the performance of differential privacy at
parity of $\epsilon$. Notice how to get Jaccard similarity above $0.5$ in
stanford or dblp, $\epsilon$ must be $10$ which is too large to provide strong
guarantees. We can use these results to compare $k$-anonymity and
$\epsilon$-differential from their a standpoint. We observe that depending on
the dataset an anonymity of $k=16$ might require an $\epsilon$ as large as
$11$ to obtain the same utility.

Learning from anonymous data Finally, we report results on using the
anonymized datasets in a downstream machine learning task. We use the
anonymized version of the adult dataset to learn a classifier for the standard
classification task of predicting whether an adult’s income is $\geq\$50k$ per
year. The results are reported in Figure 4. Notice our algorithm performs
better (or on par) with the best baseline (mondrian). We observe (see Appendix
D ) that smooth performs significantly better than the $\epsilon$-node
differentially private algorithm with $\epsilon=10$ even for $k=200$,
mirroring the degradation seen in the Jaccard similarity metric.

Figure 4: Accuracy in learning task in anonymous data . We also include a
baseline of using only the majority label as well as training a model without
anonymity and a model that uses node differential privacy with $\epsilon=10$

##  7 Conclusion

We presented a new notion of anonymity which relaxes standard $k$-anonymity
and allows us to obtain better guarantees and improved results in downstream
machine learning tasks. Our algorithms reduce the anonymization problem to
clustering with lower bounds and require non-trivial analysis to prove
approximation guarantees. Many interesting questions remain, including
strengthening our bounds for smooth $k$-anonymity and better understanding the
interplay between the various notions of privacy.

## References

  * Abbe [2017] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  _The Journal of Machine Learning Research_ , 18(1):6446–6531, 2017.
  * Aggarwal et al. [2005] Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu.  Approximation algorithms for k-anonymity.  _Journal of Privacy Technology (JOPT)_ , 2005.
  * Ahmadian and Swamy [2012] Sara Ahmadian and Chaitanya Swamy.  Improved approximation guarantees for lower-bounded facility location.  In _International Workshop on Approximation and Online Algorithms_ , pages 257–271. Springer, 2012.
  * Albert and Barabási [2002] Réka Albert and Albert-László Barabási.  Statistical mechanics of complex networks.  _Reviews of modern physics_ , 74(1):47, 2002.
  * Backstrom et al. [2012] Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna.  Four degrees of separation.  In _Proceedings of the 4th Annual ACM Web Science Conference_ , pages 33–42, 2012.
  * Bassily et al. [2013] Raef Bassily, Adam Groce, Jonathan Katz, and Adam D. Smith.  Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy.  In _54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA_ , pages 439–448, 2013.
  * Byun et al. [2007] Ji-Won Byun, Ashish Kamra, Elisa Bertino, and Ninghui Li.  Efficient k-anonymization using clustering techniques.  In _International Conference on Database Systems for Advanced Applications_ , pages 188–200. Springer, 2007.
  * Chaudhuri et al. [2011] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate.  Differentially private empirical risk minimization.  _J. Mach. Learn. Res._ , 2011.
  * Cheng et al. [2010] James Cheng, Ada Wai-Chee Fu, and Jia Liu.  K-isomorphism: privacy preserving network publication against structural attacks.  In _SIGMOD_ , pages 459–470, 2010.
  * Chierichetti et al. [2009] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan.  On compressing social networks.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 219–228, 2009.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Dwork and Smith [2010] Cynthia Dwork and Adam D. Smith.  Differential privacy for statistics: What we know and what we want to learn.  _J. Priv. Confidentiality_ , 1(2), 2010.
  * Eliáš et al. [2020] Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee.  Differentially private release of synthetic graphs.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 560–578. SIAM, 2020.
  * Fotakis [2011] Dimitris Fotakis.  Online and incremental algorithms for facility location.  _ACM SIGACT News_ , 42(1):97–131, 2011.
  * Friedman et al. [1977] Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel.  An algorithm for finding best matches in logarithmic expected time.  _ACM Transactions on Mathematical Software (TOMS)_ , 3(3):209–226, 1977.
  * Guha et al. [2000] Sudipto Guha, Adam Meyerson, and Kamesh Munagala.  Hierarchical placement and network design problems.  In _Proceedings 41st Annual Symposium on Foundations of Computer Science_ , pages 603–612. IEEE, 2000.
  * Karget and Minkoff [2000] DR Karget and Maria Minkoff.  Building steiner trees with incomplete global knowledge.  In _Proceedings 41st Annual Symposium on Foundations of Computer Science_ , pages 613–623. IEEE, 2000.
  * Kasiviswanathan et al. [2011] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  What can we learn privately?  _SIAM J. Comput._ , 40(3):793–826, 2011.
  * Kasiviswanathan et al. [2013] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  Analyzing graphs with node differential privacy.  In _Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings_ , pages 457–476, 2013.
  * Kenig and Tassa [2012] Batya Kenig and Tamir Tassa.  A practical approximation algorithm for optimal k-anonymity.  _Data Mining and Knowledge Discovery_ , 25(1):134–168, 2012.
  * LeFevre et al. [2006] Kristen LeFevre, David J DeWitt, and Raghu Ramakrishnan.  Mondrian multidimensional k-anonymity.  In _22nd International conference on data engineering (ICDE’06)_ , pages 25–25. IEEE, 2006.
  * Leskovec et al. [2007] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  _ACM transactions on Knowledge Discovery from Data (TKDD)_ , 1(1):2–es, 2007.
  * Leskovec et al. [2009] Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney.  Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters.  _Internet Mathematics_ , 6(1):29–123, 2009.
  * Li et al. [2007] Ninghui Li, Tiancheng Li, and Suresh Venkatasubramanian.  t-closeness: Privacy beyond k-anonymity and l-diversity.  In _2007 IEEE 23rd International Conference on Data Engineering_ , pages 106–115. IEEE, 2007.
  * Li et al. [2011] Ninghui Li, Wahbeh H Qardaji, and Dong Su.  Provably private data anonymization: Or, k-anonymity meets differential privacy.  _CoRR, abs/1101.2604_ , 49:55, 2011.
  * Li [2013] Shi Li.  A 1.488 approximation algorithm for the uncapacitated facility location problem.  _Information and Computation_ , 222:45–58, 2013.
  * Machanavajjhala et al. [2007] Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramaniam.  l-diversity: Privacy beyond k-anonymity.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 1(1):3–es, 2007.
  * Meyerson [2001] Adam Meyerson.  Online facility location.  In _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_ , pages 426–431. IEEE, 2001.
  * Meyerson and Williams [2004] Adam Meyerson and Ryan Williams.  On the complexity of optimal k-anonymity.  In _SIGMOD_ , pages 223–228, 2004.
  * Motwani and Nabar [2008] Rajeev Motwani and Shubha U Nabar.  Anonymizing unstructured data.  _arXiv preprint arXiv:0810.5582_ , 2008.
  * Narayanan and Shmatikov [2008] Arvind Narayanan and Vitaly Shmatikov.  Robust de-anonymization of large sparse datasets.  In _S &P_, pages 111–125, 2008.
  * Nguyen et al. [2016] Hiep H. Nguyen, Abdessamad Imine, and Michaël Rusinowitch.  Network structure release under differential privacy.  _Transactions on Data Privacy_ , 9(3):215–241, 2016.
  * Nissim et al. [2007] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  Smooth sensitivity and sampling in private data analysis.  In _Proceedings of the 39th Annual ACM Symposium on Theory of Computing_ , pages 75–84, 2007.
  * Park and Shim [2010] Hyoungmin Park and Kyuseok Shim.  Approximate algorithms with generalizing attribute values for k-anonymity.  _Information Systems_ , 35(8):933–955, 2010.
  * Ranjit et al. [2008] Ganta Srivatsava Ranjit, Kasiviswanathan Shiva Prasad, and Smith Adam.  Composition attacks and auxiliary information in data privacy.  In _KDD_ , KDD ’08. ACM, 2008.
  * Svitkina [2010] Zoya Svitkina.  Lower-bounded facility location.  _ACM Transactions on Algorithms (TALG)_ , 6(4):69, 2010.
  * Sweeney [2002] Latanya Sweeney.  k-anonymity: A model for protecting privacy.  _International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems_ , 10(05):557–570, 2002.
  * Wang et al. [2014] Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji.  Hashing for similarity search: A survey.  _arXiv preprint arXiv:1408.2927_ , 2014.
  * Wang et al. [2010] Shyue-Liang Wang, Yu-Chuan Tsai, Hung-Yu Kao, and Tzung-Pei Hong.  Anonymizing set-valued social data.  In _2010 IEEE/ACM Int’l Conference on Green Computing and Communications & Int’l Conference on Cyber, Physical and Social Computing_, pages 809–812. IEEE, 2010.
  * Yang and Leskovec [2015] Jaewon Yang and Jure Leskovec.  Defining and evaluating network communities based on ground-truth.  _Knowledge and Information Systems_ , 2015.
  * Zheng et al. [2018] Wantong Zheng, Zhongyue Wang, Tongtong Lv, Yong Ma, and Chunfu Jia.  K-anonymity algorithm based on improved clustering.  In _International Conference on Algorithms and Architectures for Parallel Processing_ , pages 462–476. Springer, 2018.

##  Appendix A Technical lemma

######  Lemma A.1.

Let $a,b,x>0$ be such that $x<\frac{b-a}{2}$ then

$\frac{a-x}{b-x}<\frac{a}{b}+2x.$ (1)

###### Proof.

From the condition on $x$ it follows that $b-x>0$. Therefore rearranging terms
in (1) yields the equivalent inequality:

$ab-bx<ab-ax+2bx-2x^{2}.$

This inequality holds if and only if $x<\frac{b-a}{2}.$ ∎

##  Appendix B Omitted proofs from Section 4

###  B.1 Randomized response is $\epsilon$-differentially private

Consider the following procedure. For each element, with probability
$1-\frac{2}{e^{\epsilon}+1}$ we report the true value, otherwise with
probability $\frac{1}{e^{\epsilon}+1}$ we report $0$ and with probability
$\frac{1}{e^{\epsilon}+1}$ we report $1$. We refer to this procedure as
$\epsilon$-DP. Next theorem shows that this procedure is
$\epsilon$-differentially private.

######  Theorem B.1.

$\epsilon$-DP preserves $\epsilon$ edge differential privacy.

###### Proof.

Let $G$ and $G^{\prime}$ be two arbitrary graphs that only differ in one edge
$e$, and let $G_{\epsilon}$ and $G^{\prime}_{\epsilon}$ be the outcomes of
$\epsilon$-DP on $G$ and $G^{\prime}$ respectively. Let $S$ be a collection of
graphs, and let $H$ be an arbitrary graph in $S$.First we consider the case
that $e\in G$ and $e\in H$. Then, we consider the case that $e\notin G$ and
$e\in H$. The same argument holds for the other two possibilities.

Let $P^{-e}(G_{\epsilon},H)$ be the probability that
$G_{\epsilon}-\\{e\\}=H-\\{e\\}$, i.e., ignoring edge $e$ all of their other
edges match. Similarly, let $P^{-e}(G^{\prime}_{\epsilon},H)$ be the
probability that $G^{\prime}_{\epsilon}-\\{e\\}=H-\\{e\\}$. Note that $G$ and
$G^{\prime}$ only defer on edge $e$. Hence, we have
$P^{-e}(G_{\epsilon},H)=P^{-e}(G^{\prime}_{\epsilon},H)$. We have

$\displaystyle\textbf{Pr}(G_{\epsilon}\in S)$ $\displaystyle=\sum_{H\in
S}P(G_{\epsilon}=H)$ $\displaystyle=\sum_{H\in
S}P^{-e}(G_{\epsilon},H)\textbf{Pr}(e\in G_{\epsilon})$
$\displaystyle=\sum_{H\in
S}P^{-e}(G_{\epsilon},H)\big{(}1-\frac{1}{e^{\epsilon}+1}\big{)}$
$\displaystyle=\big{(}\frac{e^{\epsilon}}{e^{\epsilon}+1}\big{)}\sum_{H\in
S}P^{-e}(G_{\epsilon},H).$

Similarly, we have

$\displaystyle\textbf{Pr}(G^{\prime}_{\epsilon}\in S)$
$\displaystyle=\sum_{H\in S}P(G^{\prime}_{\epsilon}=H)$
$\displaystyle=\sum_{H\in S}P^{-e}(G^{\prime}_{\epsilon},H)\textbf{Pr}(e\in
G^{\prime}_{\epsilon})$ $\displaystyle=\sum_{H\in
S}P^{-e}(G^{\prime}_{\epsilon},H)\big{(}\frac{1}{e^{\epsilon}+1}\big{)}$
$\displaystyle=\big{(}\frac{1}{e^{\epsilon}+1}\big{)}\sum_{H\in
S}P^{-e}(G^{\prime}_{\epsilon},H)$
$\displaystyle=\big{(}\frac{1}{e^{\epsilon}+1}\big{)}\sum_{H\in
S}P^{-e}(G_{\epsilon},H).$

Hence, we have $\textbf{Pr}(G_{\epsilon}\in
S)=e^{\epsilon}\textbf{Pr}(G^{\prime}_{\epsilon}\in S)$ as desired.

Now we consider the case that $e\notin G$ and $e\in H$. Similar argument to
the previous case implies $\textbf{Pr}(G_{\epsilon}\in
S)=\big{(}\frac{1}{e^{\epsilon}+1}\big{)}\sum_{H\in S}P^{-e}(G_{\epsilon},H)$
and $\textbf{Pr}(G^{\prime}_{\epsilon}\in
S)=\big{(}\frac{e^{\epsilon}}{e^{\epsilon}+1}\big{)}\sum_{H\in
S}P^{-e}(G_{\epsilon},H)$. This implies that
$e^{\epsilon}\textbf{Pr}(G_{\epsilon}\in
S)=\textbf{Pr}(G^{\prime}_{\epsilon}\in S)$. For $\epsilon\geq 1$ we have
$e^{\epsilon}\geq 1$. Hence we have $\textbf{Pr}(G_{\epsilon}\in S)\leq
e^{\epsilon}\textbf{Pr}(G^{\prime}_{\epsilon}\in S)$ as desired. ∎

###  B.2 Bound on utility of the randomized response method

######  Theorem B.2 (Restatement of Theorem 4.1).

Let $G=(U\cup F,E)\in\mathbb{G}$ be a graph, $\delta>0$. Let $\mathcal{M}$ be
a mechanism that generates a graph according to Algorithm 1 with
$p=\frac{2}{1+e^{\epsilon}}$. Let $Q=|U||F|$ and
$C(\delta)=\frac{\log(2/\delta)}{2}$. If
$\frac{p}{4}\geq\sqrt{\frac{C(\delta)}{Q}}$, then with probability at least
$1-\delta$:

$J(\mathcal{M}(G),G)\leq\frac{1-\frac{1}{e^{\epsilon}+1}}{1+\frac{1}{e^{\epsilon}+1}\frac{1-\lambda}{\lambda}}+2\sqrt{\frac{C(\delta)}{Q}},$

where $\lambda:=\lambda(G)$.

###### Proof.

Let $E^{\prime}$ denote the edge set of the output graph. By definition of the
mechanism, each edge on $E$ is preserved with probability
$1-p+\frac{1}{2}p=1-\frac{p}{2}$. Thus, we have $|E\cap
E^{\prime}|=\sum_{i=1}^{|E|}Y_{i}$ where $Y_{i}$ is distributed
Bin($1-\frac{p}{2}$). By Hoeffding’s inequality we know with probability at
least $1-\frac{\delta}{2}$:

$\displaystyle|E\cap E^{\prime}|$
$\displaystyle\leq\left(1-\frac{p}{2}\right)|E|+\sqrt{|E|\frac{\log(2/\delta)}{2}}$
$\displaystyle=\left(1-\frac{p}{2}\right)\lambda Q+\sqrt{\lambda QC(\delta)}$

Similarly an edge not in $E$ is added to $E^{\prime}$ with probability
$\frac{p}{2}$. Thus we have $|E\cup E^{\prime}|=\sum_{j=1}^{Q-|E|}Z_{j}$ where
$Z_{j}\sim\textrm{Bin}\left(\frac{p}{2}\right)$. Thus, by Hoeffding’s
inequality we have that with probability at least $1-\frac{\delta}{2}$

$\displaystyle|E\cup E^{\prime}|$
$\displaystyle\geq|E|+\left(\frac{p}{2}\right)(Q-|E|)-\sqrt{(Q-|E|)\frac{\log(2/\delta)}{2}}$
$\displaystyle=\lambda
Q+\left(\frac{p}{2}\right)Q(1-\lambda)-\sqrt{Q(1-\lambda)C(\delta)}$

By the union bound, and rearranging terms we thus have that with probability
at least $1-\delta$

$\displaystyle J(\mathcal{M}(G),G)$
$\displaystyle\leq\frac{(1-\frac{p}{2})\lambda+\sqrt{\lambda\frac{C(\delta)}{Q}}}{\lambda+\frac{p}{2}(1-\lambda)-\sqrt{(1-\lambda)\frac{C(\delta)}{Q}}}$
$\displaystyle=\frac{(1-\frac{p}{2})\lambda+\sqrt{\frac{C(\delta)}{Q}}}{\lambda+\frac{p}{2}(1-\lambda)-\sqrt{\frac{C(\delta)}{Q}}}$
$\displaystyle\leq\frac{(1-\frac{p}{2})\lambda}{\lambda+\frac{p}{2}(1-\lambda)}+2\sqrt{\frac{C(\delta)}{Q}},$

where we have used Lemma A.1 in the Appendix for the last inequality. The
results follow by dividing the numerator and denominator by $\lambda$ and
using the definition of $p$. ∎

###  B.3 Hardness of differential privacy

######  Theorem B.3 (Restatement of Theorem 4.3).

Let $\mathcal{M}$ be an arbitrary mechanism that satisfies $\epsilon$-edge
differential privacy. Let $\alpha$ be a parameter such that for any input
graph $G=(U\cup F,E)$, we have $\alpha\leq E[J(\mathcal{M}(G),G)]$. We have

$\epsilon\in\Omega\big{(}\log(\alpha^{2}nm)\big{)}.$

###### Proof.

To prove this first we define a policy $\overline{\mathcal{M}}(G)$ based on
$\mathcal{M}(G)$, such that $\overline{\mathcal{M}}(G)$ is

  * •

an $\epsilon$-differentially private mechanism,

  * •

$E[J(G,\overline{\mathcal{M}}(G))]\geq\frac{\alpha}{2}$, when $|G|\geq
l=\lfloor(nm)^{0.9}\rfloor$, and

  * •

$|\overline{\mathcal{M}}(G)|\leq\frac{2(l+1)}{\alpha}$.

The third property bounds the range of $|\overline{\mathcal{M}}(G)|$ and
allows us to analyze $\overline{\mathcal{M}}(G)$ and bound $\epsilon$. We
define policy $\overline{\mathcal{M}}(G)$ based on $\mathcal{M}(G)$ as
follows:

  * •

If $|\mathcal{M}(G)|>\frac{2(l+1)}{\alpha}$ then $\overline{\mathcal{M}}(G)$
is set to empty graph,

  * •

otherwise $\overline{\mathcal{M}}(G)=\mathcal{M}(G)$.

Note that $\overline{\mathcal{M}}(G)$ can be exactly calculated given
$\mathcal{M}(G)$, hence $\overline{\mathcal{M}}(G)$ is an
$\epsilon$-differentially private policy as well. Moreover, note that when
$|\mathcal{M}(G)|>\frac{2(l+1)}{\alpha}$ we have

$\displaystyle
J(G,\mathcal{M}(G))=\frac{|G\cap\mathcal{M}(G)|}{|G\cup\mathcal{M}(G)|}\leq\frac{|G\cap\mathcal{M}(G)|}{|\mathcal{M}(G)|}<\frac{\alpha}{2}\frac{|G|}{l+1}.$
(2)

Hence, for a graph $G$ with $|G|\leq l+1$ we have

$\displaystyle E[J(G,\overline{\mathcal{M}}(G))]=$ $\displaystyle
E[J(G,{\mathcal{M}}(G))]-E[J(G,{\mathcal{M}}(G))-J(G,\overline{\mathcal{M}}(G))]\geq$
$\displaystyle\alpha-E[J(G,{\mathcal{M}}(G))-J(G,\overline{\mathcal{M}}(G))]\geq\;\;\;\;\text{\it(By
def. )}$
$\displaystyle\alpha-E[\max(0,\frac{\alpha}{2}\frac{|G|}{l+1})]\geq\;\;\;\text{
\it(By Ineq.~{}\ref{eq:hardness:eq1})}$
$\displaystyle\frac{\alpha}{2}.\;\;\;\text{\it(By $|G|\leq l+1$)}$

Consider the following two equivalent random processes to construct random
graphs $G=(U\cup F,E)$ and $G^{\prime}=(U\cup F,E^{\prime})$.

  * •

Select $l$ pairs of nodes from $U\times F$ uniformly at random without
replacement. Add an edge between each selected pair in both $D$ and
$D\textquoteright$. Select one other pair of nodes from $U\times F$ uniformly
at random without replacement, denote it as $(u,f)$, and add an edge between
$u$ and $f$ in $D^{\prime}$.

  * •

Select $l+1$ pairs of nodes from $U\times F$ uniformly at random without
replacement. Add an edge between each selected pair in both $D$ and
$D\textquoteright$. Select one of the edges in $D$ uniformly at random, denote
it as $(u,f)$, and remove it from $D$.

Note that, $G$ is a graph chosen uniformly at random from all graphs on
$U\times F$ with $l$ edges, and $G^{\prime}$ is a graph chosen uniformly at
random from all graphs on $U\times F$ with $l+1$ edges. Moreover, $(u,f)$ is
both an edge selected uniformly at random from the edges inside $G^{\prime}$
and it is an edge selected uniformly at random from the edges that are not in
$G$.

Recall that, by definition, we have

$\displaystyle\frac{\alpha}{2}$ $\displaystyle\leq
E\big{[}J(\overline{\mathcal{M}}(G^{\prime}),G^{\prime})\big{]}=E\Big{[}\frac{|\overline{\mathcal{M}}(G^{\prime})\cap
G^{\prime}|}{|\overline{\mathcal{M}}(G^{\prime})\cup G^{\prime}|}\Big{]}$
$\displaystyle\leq E\Big{[}\frac{|\overline{\mathcal{M}}(G^{\prime})\cap
G^{\prime}|}{|G^{\prime}|}\Big{]}=\frac{E\big{[}|\overline{\mathcal{M}}(G^{\prime})\cap
G^{\prime}|\big{]}}{|G^{\prime}|}.$

Note that, if we select one of the edges of $G^{\prime}$ uniformly at random,
it exists in $\overline{\mathcal{M}}(G^{\prime})$ with probability at least
$\frac{E\big{[}|\overline{\mathcal{M}}(G^{\prime})\cap
G^{\prime}|\big{]}}{|G^{\prime}|}\geq\frac{\alpha}{2}$. Hence, we have
$(u,f)\in\overline{\mathcal{M}}(G^{\prime})$ with probability at least
$\frac{\alpha}{2}$. Let $S$ be the set of all possible outputs of
$\overline{\mathcal{M}}(G^{\prime})$ where the
$(u,f)\in\overline{\mathcal{M}}(G^{\prime})$. By the definition of
differential privacy we have

$\displaystyle\textbf{Pr}\Big{(}\overline{\mathcal{M}}(G^{\prime})\in
S\Big{)}\leq e^{\epsilon}\textbf{Pr}\Big{(}\overline{\mathcal{M}}(G)\in
S\Big{)},$

Which means

$\displaystyle\textbf{Pr}\Big{(}\overline{\mathcal{M}}(G)\in S\Big{)}\geq
e^{-\epsilon}\textbf{Pr}\Big{(}\overline{\mathcal{M}}(G^{\prime})\in
S\Big{)}\geq\frac{\alpha e^{-\epsilon}}{2}.$

This means that $(u,f)\in\overline{\mathcal{M}}(G)$ with probability at least
$\frac{\alpha e^{-\epsilon}}{2}$. Recall that, by definition $(u,f)$ is an
edge chosen uniformly at random from the edges that do not exist in $G$.
Hence, if we select one of the edges that do not exist in $G$, it exists in
$\overline{\mathcal{M}}(G)$ with probability at least $\frac{\alpha
e^{-\epsilon}}{2}$.

On the other hand, similar to $G^{\prime}$, if we select one of the edges of
$G$ uniformly at random, it exists in $\overline{\mathcal{M}}(G)$ with
probability at least $\frac{\alpha}{2}$. Hence, we have

$E[|\overline{\mathcal{M}}(G)|]\geq(nm-l)\frac{\alpha}{2}e^{-\epsilon}+l\frac{\alpha}{2}\geq\frac{nm\alpha
e^{-\epsilon}}{2}.$

Recall that by construction we have
$|\overline{\mathcal{M}}(G)|\leq\frac{2(l+1)}{\alpha}$. This together with the
above inequality gives us $\frac{nm\alpha
e^{-\epsilon}}{2}\leq\frac{2(l+1)}{\alpha}$. This implies
$\epsilon\geq\log\frac{\alpha^{2}nm}{4(l+1)}\in\Omega\big{(}\log(\alpha^{2}nm)\big{)}$,
as claimed. ∎

###  B.4 Utility of k-anonymity by suppression in the stochastic block model

######  Theorem B.4 (Restatement of Theorem 4.4).

Let $G$ be a graph generated by the stochastic block model with parameters
$r,s,\alpha,\beta$. Let $k\geq\frac{2\log n}{\log 1/q}$. With probability
$99\%$, any $k$-anonymous subgraph of $G$ contains at most $\frac{2\log
n+10}{\log 1/q}n\in\tilde{O}(n)$ edges.

###### Proof.

Let $t=\frac{2\log n+10}{\log\frac{1}{q}}$. Fix a subset of size $k$ of
vertices in the first part and a subset of size $t$ in the second part. Recall
that the probability that we have an edge between a pair of vertices is either
$p$ or $q$, where $p\leq q$, and each edge exists independently. Hence, the
probability that all of the edges between a certain set of vertices of size
$k$ and a certain set of vertices of size $t$ exist is at most $q^{kt}$. On
the other hand there are ${k\choose n}\cdot{t\choose n}$ such a pair of sets.
Therefore, by union bound, the probability that there exists a set of vertices
of size $k$ and a set of vertices of size $t$ in $G$ that forms a complete
bipartite graph is at most

$\displaystyle q^{kt}\cdot{k\choose n}\cdot{t\choose n}$ $\displaystyle\leq
q^{kt}n^{k}n^{t}$ $\displaystyle=\exp\big{(}kt\log q+k\log n+t\log n\big{)}$
$\displaystyle=\exp\big{(}-kt\log\frac{1}{q}+k\log n+t\log n\big{)}$
$\displaystyle=\exp\big{(}(k\log n-k\frac{t}{2}\log\frac{1}{q})$
$\displaystyle+(t\log n-\frac{k}{2}t\log\frac{1}{q})\big{)}$
$\displaystyle\leq\exp\big{(}(k\log n-k\frac{t}{2}\log\frac{1}{q})\big{)}$
$\displaystyle=\exp(5k)$ $\displaystyle\leq 0.01.$

Where the inequalities follow by the bounds on $k$ and $t$. This implies that
with probability $99\%$ there is no vertex with degree more than $t$ in a
$k$-anonymous subgraph of $G$. Hence the total number of edges in such a
subgraph is at most $tn=\frac{2\log n+10}{\log\frac{1}{q}}n\in\tilde{O}(n)$. ∎

##  Appendix C Omitted proofs from Section 5

###  C.1 Lemma 5.2

######  Lemma C.1 (Restatement of Lemma 5.2).

Assume $J(E,E_{\textrm{Opt}})\geq 1-\phi$. We have
$\sum_{u}\Delta_{u}^{\textrm{Opt}}\leq\frac{2\phi}{1-\phi}|E|$.

###### Proof.

Since $J(E,E_{\textrm{Opt}})\geq 1-\phi$, we have $\frac{|E\cap
E_{\textrm{Opt}}|}{|E\cup E_{\textrm{Opt}}|}\geq 1-\phi$. Thus $\frac{|E\oplus
E_{\textrm{Opt}}|}{|E\cup E_{\textrm{Opt}}|}\leq\phi$, which gives us
$|E\oplus E_{\textrm{Opt}}|\leq\phi|E\cup E_{\textrm{Opt}}|$. On the other
hand $\frac{|E\cap E_{\textrm{Opt}}|}{|E\cup E_{\textrm{Opt}}|}\geq 1-\phi$
implies that $|E\cup E_{\textrm{Opt}}|\leq\frac{1}{1-\phi}|E\cap
E_{\textrm{Opt}}|\leq\frac{1}{1-\phi}|E|$. Therefore we have

$\displaystyle\sum_{u}\Delta_{u}^{\textrm{Opt}}=2|E\oplus
E_{\textrm{Opt}}|\leq 2\phi|E\cup
E_{\textrm{Opt}}|\leq\frac{2\phi}{1-\phi}|E|.$

∎

###  C.2 Lemma 5.3

######  Lemma C.2 (Restatement of Lemma 5.3).

Assume $\sum_{u}\Delta_{u}^{\textrm{Alg}}\leq\phi^{\prime}|E|$. We have
$J(E,E_{\textrm{Alg}})\geq 1-\frac{\phi^{\prime}}{2}$.

###### Proof.

Note that $\sum_{u}\Delta_{u}^{\textrm{Alg}}\leq\phi^{\prime}|E|$ means
$2|E\oplus E_{\textrm{Opt}}|\leq\phi^{\prime}|E|$. Hence we have

$\displaystyle 2\big{(}|E\cup E_{\textrm{Alg}}|-|E\cap
E_{\textrm{Alg}}|\big{)}\leq\phi^{\prime}|E|\leq\phi^{\prime}|E\cup
E_{\textrm{Alg}}|.$

By some rearrangement we have $\frac{|E\cap E_{\textrm{Alg}}|}{|E\cup
E_{\textrm{Alg}}|}\geq 1-\frac{\phi^{\prime}}{2}$, which means
$J(E,E_{\textrm{Alg}})\geq 1-\frac{\phi^{\prime}}{2}$ as desired. ∎

###  C.3 Proof of the main theorem

######  Theorem C.3 (Restatement of Theorem 5.5).

Assume $J(E,E_{\textrm{Opt}})\geq 0.75$. There exists an algorithm that finds
a constant approximation to smooth-$k$-anonymization of $E$ in polynomial
time.

###### Proof.

Svitkina Svitkina [2010] showed that Lines 2 to 3 gives solution in which (i)
the size of each cluster is at least $\alpha k$, and (ii) the cost of the
solution is at most $1.488\cdot\frac{1+\alpha}{1-\alpha}$ times that of lower-
bounded $r$-median. Similar to our previous algorithm, since the size of each
cluster is at least $k$, the last line of the algorithm guarantees
smooth-$k$-anonymity. Next we bound $J(E,E_{\textrm{Alg}_{2}})$ assuming
$J(E,E_{\textrm{Opt}})\leq 1-\phi$. We refer to the first four lines of
algorithm $\textrm{Alg}_{2}$ as $\textrm{Alg}^{\prime}_{2}$. Similar to the
previous subsection we know that there exists a solution to lower-bounded
$r$-median with cost at most $\frac{4\phi}{1-\phi}|E|$. Therefore the cost of
the solution to the facility location problem is at most

$5.952\cdot\frac{1+\alpha}{1-\alpha}\cdot\frac{\phi}{1-\phi}|E|.$

Again similar to the previous subsection and by applying Lemma 5.3 we have

$J(E,E_{\textrm{Alg}^{\prime}_{2}})\geq
1-2.976\cdot\frac{1+\alpha}{1-\alpha}\cdot\frac{\phi}{1-\phi}.$

Later we show that Line 3 decreases the Jaccard similarity by at most a factor
$\frac{\alpha^{2}}{8}$. Hence we have

$J(E,E_{\textrm{Alg}_{2}})\geq\frac{\alpha^{2}}{8}\Big{(}1-2.976\cdot\frac{1+\alpha}{1-\alpha}\cdot\frac{\phi}{1-\phi}\Big{)},$

which is a positive constant for $\phi\leq 0.25$ and $\alpha=0.004$. This
implies Theorem 5.5.

New we show that Line 3 decreases the Jaccard similarity by a factor of at
least $\frac{\alpha^{2}}{8}$. To prove this, we use the probabilistic method.
For each cluster we show a random point such that if we move the points in
each cluster to its corresponding random point, the expected Jaccard
similarity is at least $\frac{\alpha^{2}}{8}$ times that of the initial
Jaccard similarity. This implies that there exists a fixed (i.e.,
deterministic) set of points such that if we move the points in each cluster
to its corresponding fixed point, the expected Jaccard similarity is at least
$\frac{\alpha^{2}}{8}$ times that of the initial Jaccard similarity. Note
that, for each cluster, we are selecting the optimum center, and hence this
statement holds for our selected centers as well.

Let $E_{\text{init}}$ be the edge set corresponding to the clustering prior to
Line 3. For each merged cluster we select the center of one of its initial
clusters uniformly at random. Note that each merged cluster contains at most
$2/\alpha$ initial clusters. we select the center of each initial cluster with
probability at least $\alpha/2$. This means that each edge that exists in
$E\cap E_{\text{init}}$ exists after merging the clusters with probability at
least $\alpha/2$. Hence, the expected number edges that exists after merging
is at least $\frac{\alpha}{2}|E\cap E_{\text{init}}|$.

Moreover, the number of nodes in each initial cluster is at most $\frac{\alpha
k}{2k}$ fraction of that of the merged cluster. Hence, the total number of
edges increases by a factor of at most $2/\alpha$ after merging and moving the
point to the random centers. Hence, the expected Jaccard similarity after the
merge is at least

$\displaystyle\frac{\frac{\alpha}{2}|E\cap
E_{\text{init}}|}{\frac{2}{\alpha}|E_{\text{init}}|+|E|}$
$\displaystyle\geq\frac{\frac{\alpha}{2}|E\cap
E_{\text{init}}|}{2\frac{2}{\alpha}|E\cup
E_{\text{init}}|}=\frac{\alpha^{2}}{8}\frac{|E\cap E_{\text{init}}|}{|E\cup
E_{\text{init}}|},$

as claimed. This completes the proof of Theorem 5.5. ∎

##  Appendix D Additional material from the experimental section

#### Description of the datasets

We now report a more detailed description of the datasets used. Some key
properties of the datasets are shown in Table 2.

Table 2: Datasets used in the analysis Name | Rows | Columns | Entries | Density
---|---|---|---|---
stochastic | $1024$ | $1024$ | $\sim 62{,}000$ | $\sim 0.06$
adult | $32{,}561$ | $102$ | $260{,}488$ | $0.078$
playstore | $8{,}672$ | $521$ | $86{,}720$ | $0.019$
dblp | $317{,}080$ | $317{,}080$ | $2{,}099{,}732$ | $2.09\times 10^{-5}$
stanford | $281{,}731$ | $261{,}588$ | $2{,}312{,}497$ | $3.14\times 10^{-5}$
user-lists | $>1B$ | $>100K$ | $>10B$ | $<10^{-5}$

stochastic is generated from the stochastic block model described in Section
4.2 with $n=1024$ rows and columns, and parameters $s=64$, $q=0.8$, $p=0.01$.
adult is a dataset from UCI 777https://archive.ics.uci.edu/ml/datasets/adult
from the US census used in many anonymization and differential privacy papers
LeFevre et al. [2006]. We use all categorical features represented as a binary
vector. playstore888https://www.kaggle.com/lava18/google-play-store-apps
consists of a bipartite graph representing features of user’s devices in
Google Playstore. The items $F$ represent different features that the device
has. dblp Yang and Leskovec [2015] consists of a co-authorship graph. In graph
adjacency form, rows and columns represent authors in computer science and an
entry $(i,j)$ is 1 iff $i$ and $j$ co-authored a paper. stanford Leskovec et
al. [2009] consists of a directed web graph, where rows and columns represent
web pages crawled from the Stanford website. An entry $(i,j)$ is $1$ iff page
$i$ has a hyperlink to page $j$. user-lists is a proprietary dataset from a
major internet company containing user-interest relationships. Each row
represents a user, and the columns represent the inclusion in a given
marketing interest list.

#### Metrics

Our utility goal is to preserve as accurately as possible the input, to do so
we use the Jaccard similarity between the set of the edges as utility metric
as defined in the paper. To measure the distortion incurred by the data we
also use other standard anonymity quality metrics, including the number of
suppressed entries and created entries. We note that for binary data other
metrics such as the normalized certainty penalty LeFevre et al. [2006] used
for hierarchical features are not relevant.

#### Experimental infrastructure

We implemented our algorithm using C++. For all execution of an experiment
(except for the large-scale user-list dataset) we use a single-thread program
run on standard commodity hardware. All experiments terminated within $3$
hours. We repeat each run of an algorithm with a given setting $10$ times and
report mean and deviation metrics. For our user-list dataset with more than a
billion rows, we evaluated a simple heuristic to parallelize the computation
of our algorithm. We split the dataset in chunks of order of $10^{5}$ rows by
using a Locality Sentitive Hashing technique (LSH) Wang et al. [2014]. More
precisely, for each row we compute $8$ independent min hash LSHs (over the set
of columns with $1$) and sort the rows of the dataset by the lexicographical
order of their min hashes. This is similar to the shingle sorting technique
Chierichetti et al. [2009]. We then obtain the chunks by approximately
dividing this sequence of elements in consecutive intervals of size $10^{5}$.
Then we ran our algorithm independently on each chunk of the dataset and
combined the solution. Our results (reported in Fig 3(b)) show that this
simple heuristic is quite effective.

#### Baselines

We compare our algorithm with the well-known mondrian anonymization algorithm
LeFevre et al. [2006], using an open source
implementation999https://github.com/qiyuangong/Mondrian which enforces
k-anonymity by suppression. The algorithm doesn’t have parameters to tune
(expect $k$).

Our algorithm has theoretical guarantees for smooth k-anonymization, but it
can be easily used as an heuristic for (standard) k-anonymity by suppression
(in the last step, the clusters are simply anonymized by computing the
intersection of all binary vectors), so we report results for non-smooth
k-anonymity using our algorithm as an additional baseline.

#### Implementation details

For efficiency we made small changes to the implementation of the algorithm in
Section 5.3 that we now summarize. In step (2) we slightly modify the formula
for obtaining the best empirical results. Similarly to the bicriteria
algorithm of Svitkina [2010], we add a parameter $\beta>1$, set
$\alpha=1/\beta$, and define for a point $u_{i}$ the cost of the facility as
$\frac{2\alpha}{1-\alpha}\sum_{u^{\prime}\in U^{\beta
k}_{i}}\textrm{Dist}(u^{\prime},u_{i})$, where $U^{\beta k}_{i}$ is the set of
$\beta k$ closest point to $i$. In our experiments, $\beta=2$ (i.e.
$\alpha=1/2$) was the best performing setting and we report experiments with
that value only (results with $2\leq\beta\leq 8$ are very similar). In step 3,
we solve the facility location problem efficiently by running the well-known
Meyerson’s algorithm Meyerson [2001] 10 different times on a random ordering
of the data points and selecting the best solution (in this setting the
algorithm is known to be a constant factor approximation Fotakis [2011] in
expectation). Finally, in steps 4 and 5, we replace the procedure described in
the paper, with a simpler one where we simply close facilities that have fewer
than $k$ clients in arbitrary order and reassign all clients to the nearest
open one until all clusters are large enough.

|  | Jac. | S.E. | C.E.
---|---|---|---|---
dataset | algorithm |  |  |
stochastic | mondrian | 2.2% | 97.8% | 0.0%
| non-smooth | 16.4% | 83.6% | 0.0%
| smooth | 68.1% | 17.7% | 21.0%
adult | mondrian | 59.9% | 40.1% | 0.0%
| non-smooth | 64.8% | 35.2% | 0.0%
| smooth | 85.0% | 8.9% | 7.2%
playstore | mondrian | 51.2% | 48.8% | 0.0%
| non-smooth | 39.2% | 60.8% | 0.0%
| smooth | 66.1% | 26.2% | 11.6%
dblp | non-smooth | 4.3% | 95.7% | 0.0%
| smooth | 7.4% | 92.5% | 1.4%
stanford | non-smooth | 48.0% | 52.0% | 0.0%
| smooth | 52.6% | 46.1% | 2.4%
user_lists | non-smooth | 67.3% | 32.7% | 0.0%
| smooth | 71.0% | 27.7% | 1.9%
Table 3: Extended version of Table 1. Average results for $k=8$ for various
algorithms and dataset. Jac., S.E. and C.E. stand for, respectively, Jaccard
similarity and fraction of suppressed entries and newly created entries (both
normalized by the entries in the input dataset).

(a) stochastic

(b) playstore

(c) dblp

(d) stanford

Figure 5: Mean Jaccard similarity vs k for additional datasets.

.

#### Jaccard similarity vs $k$

First, we evaluate the quality of our algorithm for smooth $k$-anonymity for
different $k$ values and we compare it with that of the (non-smooth)
k-anonymity solution and mondrian. In Figures 5(a), 5(b), 5(c), 5(d) as well
as Figures 3(a) and 3(b) we plot the mean Jaccard similarity for a given
setting of the $k$ parameter for our datasets for both smooth k-anonymity
(solid line), non-smooth anonymity (dashed line) and mondrian (dotted). We
were not able to run the mondrian algorithm on the larger datasets (dblp,
stanford, user-list) as this algorithm (contrary to ours) scales with the size
of the full $n\times m$ matrix where $m$ is the number of columns of the
dataset (while our algorithm can exploit the sparsity of the matrix).

From the pictures, it is possible to observe that, as expected, the Jaccard
similarity decreases with increasing $k$, but at every $k$ level smooth
k-anonymity allows to obtain significantly better results than all baselines.
For instance, for playstore we observe $2\times$ higher Jaccard similarity for
$k=32$ than with the best baseline. Among the baselines, interestingly we see
that non-smooth anonymity despite using our algorithm which is not optimized
for anonymity by suppression can perform better than mondrian which is
optimize for that task, in particular for lower k values. For large k values
in Figure 3(a) mondrian performs better but still is outperformed by smooth
anonymity.

The level of Jaccard similarity at a given $k$ is, as expected, dependent on
the structure of the graph. We observe for instance higher similarity at large
$k$ values for stochastic, adult, playstore dataset than dblp. This can be
easily explained by the nature of the datasets: for adult, stochastic,
playstore, the rows represent comparably dense features; while for dblp each
row represent a quite sparse and somewhat unique feature set (i.e., the co-
authors of a researcher). Interestingly, the algorithm performs much better on
the stanford dataset than the dblp one, this can be explained with previous
observations on social networks showing higher entropy than web graphs
Chierichetti et al. [2009]. Notice also how our heuristic algorithm for the
large-scale dataset obtains performances (Figure 3(b)) comparable to the best
datasets.

We observe that the results are very concentrated, in fact, the maximum
standard deviation observed for any $k$ value in $[2,64]$ for our smooth (non-
smooth) k-anonymity algorithm is $0.7\%,1.3\%$, $0.5\%$, $1.3\%$ ($1.8\%$,
$2.2\%$, $0.2\%$, $0.8\%$) for adult, playstore, dblp, stanford, respectively.

#### Trade-off between suppressed entries and created entries

We report an extended version of Table 1 in Table 3.

Figure 6: $k$ anonymity parameter vs $\epsilon$-edge DP parameter at same
level of mean Jaccard Similarity for the various datasets

.

#### Additional results for differential privacy

All results in our experiments with differential privacy in Figure 3(c) are
very concentrated around the mean with maximum standard deviation for any
$\epsilon$ of $1.02\%$, $0.09\%$, $0.15\%$, $0.05\%$, $0.04\%$ for stochastic,
adult, playstore, dblp and stanford, respectively.

#### Comparison between k-anonymity and differential privacy

We can use the results of the previous evaluation to compare the two
approaches. Notice that $k$-anonymity and $\epsilon$-differential privacy
provide mathematically incomparable privacy guarantees; but we can compare the
utility of both for different settings of their parameters $k$ or $\epsilon$.

This is what we do in Figure 6 where we report for each dataset and value of
$k$ for smooth $k$-anonymity and $\epsilon$ parameter than will result in the
same average Jaccard similarity for edge differential privacy protection.
Notice how, depending on the dataset, an anonymity level of $k=16$ might
require an $\epsilon$ as large as $11$ to obtain the same utility even for the
lower level of guarantee of edge differential privacy. For the denser datasets
like adult and playstore, values of anonymity between $k=4$ and $k=64$
correspond to the performance of $\sim 4\leq\epsilon\leq\sim 5$.

(a) DP Figure 7: Accuracy in learning task in anonymous data .

#### Learning from anonymous data

Finally, we report results on using the anonymized datasets in a downstream
machine learning task. For the adult dataset we train a neural net classifier
for the standard classification task for this dataset of predicting whether
the income of the entry point is $>=\$50k$ per year. For all methods, we only
anonymize the features not the labels and we train the model on the anonymized
features in output from the algorithms and report the prediction on the
original test dataset. We use a 1-layer, 10-hidden unit network with RELU
activation nodes.

The results are reported in Figure 4 for the anonymization methods and in
Figure 7(a) for the $\epsilon$-node differentially private method. The shades
represent the $95\%$ confidence interval. Notice that our algorithm reports
results better (or on par) with the best baseline (mondrian) and significantly
better than the $\epsilon$-node differentially private algorithm with
$\epsilon=10$ even for $k=200$. We also observe that our smooth algorithm has
lower variance in the output than the mondrian one. This confirms that our
algorithm outperforms all baselines also in producing outputs useful for
machine learning analysis.