# Secure Metric Learning via Differential Pairwise Privacy

Jing Li, Yuangang Pan, Yulei Sui, and Ivor W. Tsang J. Li, Y. Pan, Y, Sui, and
I. W. Tsang are with the Centre for Artificial Intelligence (CAI), University
of Technology Sydney, Australia.

###### Abstract

Distance Metric Learning (Dml) has drawn much attention over the last two
decades. A number of previous works have shown that it performs well in
measuring the similarities of individuals given a set of correctly labeled
pairwise data by domain experts. These important and precisely-labeled
pairwise data are often highly sensitive in real world (e.g., patients
similarity). This paper studies, for the first time, how pairwise information
can be leaked to attackers during distance metric learning, and develops
differential pairwise privacy (Dpp), generalizing the definition of standard
differential privacy, for secure metric learning.

Unlike traditional differential privacy which only applies to independent
samples, thus cannot be used for pairwise data, Dpp successfully deals with
this problem by reformulating _the worst case_. Specifically, given the
pairwise data, we reveal all the involved correlations among pairs in the
constructed undirected graph. Dpp is then formalized that defines what kind of
Dml algorithm is private to preserve pairwise data. After that, a case study
employing the contrastive loss is exhibited to clarify the details of
implementing a Dpp-Dml algorithm. Particularly, the sensitivity reduction
technique is proposed to enhance the utility of the output distance metric.
Experiments both on a toy dataset and benchmarks demonstrate that the proposed
scheme achieves pairwise data privacy without compromising the output
performance much (Accuracy declines less than 0.01 throughout all benchmark
datasets when the privacy budget is set at 4).

###### Index Terms:

Pairwise data, differential privacy, metric learning, graph, gradient
perturbation.

##  I Introduction

The distance/similarity between two samples (e.g., euclidean distance) is the
base of many applications [1], such as clustering, classification, information
retrieval, etc. Distance Metric Learning (Dml) is a fundamental tool that
learns a distance metric over the data to support these applications. It
expects that in the projected space the similar samples would be better
grouped; while the dissimilar ones would be appropriately separated. Such a
principle is properly spoken of in [2] and much subsequent research [3, 4, 5,
6, 7, 8, 9, 10] has followed this criterion.

Figure 1: Leakage of pairwise relationship. An attacker with all the prior
knowledge of the dataset except the target relationship between Bob and Lam,
is able to infer their real relationship by matching the conjecture and query
results.  Figure 2: Preserving privacy of pairwise relationship. Suppose the
relationship between Alice and Bob is the target. The attacker may have the
prior knowledge that excludes edges with question mark. This provides one of
the worst cases, where the relationship of Alice and Bob cannot be inferred
from prior knowledge. Dpp ensures that the prior knowledge of the attacker for
the worst case has the hardly indistinguishable output with the original
dataset. Particularly, the obtained metric $M_{0}$ is expected to group
training data as $M_{1}$ does.

The training data fed to Dml model is often pairwise labelled111This setting
is called weakly supervised Dml in some literature but is overwhelming in
metric learning community. which naturally encodes some secrets when the data
is collected from humans. A popular application of learning distance metric
would be healthcare data [11, 12, 13]. A pairwise relationship in this
application might be, for example, two patients have the same/different
disease(s). However, the relationships in the training data can be leaked to
attackers through a deterministic and resilient Dml model. We give a white-box
attack example to explain a scenario that a traditional Dml model may
unfortunately leak the pairwise relationship to external attackers.

_A privacy leakage scenario._ Assume that we have a set of pairwise medical
records as the training data, a Dml model is trained over the entire pairwise
data and returns a static metric $M_{*}$ (e.g., oracle). Suppose that a
powerful attacker understands the Dml model and has some prior knowledge,
i.e., knowing partial pairwise data of the entire training set (e.g. $K-1$,
where $K$ is the total number of pairs). The attacker would like to exploit a
particular relationship (e.g., Bob and Lam) which the attacker does not know.
First, she/he combines the prior knowledge by checking two possible
conjectures: (1) Bob and Lam have the same disease, and (2) Bob and Lam have
different diseases. Then, the attacker feeds them to the Dml model separately
and obtains corresponding conjecture results $M_{1}$ and $M_{2}$. Lastly,
she/he matches the two results with the oracle $M_{*}$. The matched conjecture
will expose the correct pairwise relationship between Bob and Lam, leaking the
private relationship to the attacker. Fig. 1 depicts this process.

_Differential privacy._

Figure 3:  Knowledge diagram. The prior knowledge is supposed to be smaller
than the whole data deducting the target pair because of the data correlation.
For a given target pair there always exists a corresponding defensive boundary
which restricts the volume of prior knowledge in practice.

Differential Privacy (DP) [14] has become a popular and widely accepted
privacy framework in recent years. It is initially used in data mining and
data release research community and recently moved to the machine learning
community[15]. It aims to ensure that the participation of an individual
sample never changes the probability of any possible outcome by much. This
goal is usually achieved by adding perturbation during modeling. As a result,
the model is able to protect against the powerful attackers who have access to
the whole dataset except the targeted sample. This conclusion is derived from
the DP’s assumption that all the samples are independent, so that DP can
defend the worst case scenario, i.e., except the target sample, all the
remaining data ($K$-1 samples) are the prior knowledge of an attacker.
Unfortunately, this assumption is broken in pairwise data, even if we treat a
pair of data as a single sample. For example, the disease relation between
Alice and Bob in Fig. 2 can be inferred by Jim since Jim has the same disease
as both Alice and Bob. Therefore, attackers does not need $K$-1 samples to get
the same prior knowledge as the worst case. In the pairwise data setting, the
worst case assumption ($K$-1 samples in an attacker’s prior knowledge) in DP
is not valid anymore. The DP assumption, which can be seen as a defensive
boundary for securing pairwise privacy, needs to be redefined to understand
the defence capability of DP for pairwise data. This thought is depicted as
Fig. 3, where the defensive boundary would be shrunk to the target pair’s
boundary if data are independent.

_Our solution._ This paper studies, for the first time, how pairwise
information can be leaked to attackers under distance metric learning
scenario. By understanding the limitation of DP’s assumption on prior
knowledge when preserving the privacy of pairwise data, we reformulate the
worst case assumption of DP for pairwise data by introducing an extended
privacy definition, namely Differential Pairwise Privacy (Dpp). A Dml
algorithm satisfying Dpp can be described as Fig. 2, where the input pairwise
data altogether can be viewed as a graph. Compared to the traditional Dml
algorithm, the novelty of the proposed Dml lies in the introduced randomness
which is used to compensate for the difference (i.e., a number of edges in the
graph) between the original dataset and the prior knowledge of the attacker.
Therefore, the randomized Dml is able to output hardly distinguishable
distance metric no matter which one is the input dataset, the original dataset
or the possible prior knowledge of the attacker for the worst case.
Consequently, no more useful information would be obtained for the attacker by
querying the randomized Dml.

_Contributions._ The key contributions of our work are as followings:

  1. 1.

This paper presents Dpp, a new privacy preserving technique for pairwise data
to secure distance metric learning. From the view of problem optimization,
this work is shown as an important member in Empirical Risk Minimization (ERM)
family.

  2. 2.

We analyze the gradient sensitivity via exploring the distribution of pairs
within a minibatch during the optimization. It helps to enhance the utility of
the released distance metric by reducing the amount of injected noise.

  3. 3.

We exploit the connection of Dpp with the existing privacy research, and
verify the efficacy of the proposed scheme by numerous experiments.

The rest of this paper proceeds as follows. We present the related work in
Section II and introduce the preliminaries in Section III. Then we state the
secure metric learning problem in Section IV, and formally define Dpp in
Section V. In SectionVI, we implement a Dml algorithm based on the contrastive
loss, where we further propose a utility improvement method. The experiments
in Section VII are used to verify the efficacy of the proposed scheme. Some
interesting questions are discussed in VIII. Finally, Section IX concludes
this paper.

##  II Related Works

We present the related works from two aspects, the possible strategies for the
privacy of pairwise data, and current privacy implementation methods.

###  II-A Privacy Strategies

Before diving into any specific privacy definitions, one may ask why not
directly hiding individual identity, because it would immediately remove the
privacy issues. Actually, this so-called anonymization trick has been argued
as unsafe and inadequate in many previous works, such as [16] and [17]. The
deficiency of anonymization is being vulnerable to the auxiliary information.
For example, the information extracted from a social medium without name
annotation is still possibly recognized from some other social media data with
name annotation by comparison.

A feasible choice to preserve pairwise data is to leverage Local Differential
Privacy (LDP). For example, one can adopt the coin flipping style approach
[18] to probabilistically change the relationship of any pair. In this case,
any subsequently surmised relationship for a data pair can be possibly denied,
such as [19, 20, 21]. If the privacy for individual feature is needed, one can
resort to the input perturbation like [22]. Unfortunately, LDP suffers the
performance degeneration [21] because it fails to takes the subsequent
application into consideration.

The closely related work is about studying the privacy of correlated data. One
pioneer work by Kifer et al. [23] pointed out the correlated records
definitely degrade the privacy level if not specially treated. They then
proposed a customizable privacy framework Pufferfish [24] that requires the
whole algorithm should change an attacker’s prior distribution as less as
possible. Following this framework, Song et al. [25] proposed a so-called
Wasserstein mechanism. Recent graph based privacy research [26, 27, 28, 29]
construct the relations among individuals but mainly focus on the graphical
statistics. Some other works [30, 31, 32] in the data release community [33,
34, 35] also noticed the detriment that data correlation brings in and
formalized diverse DP variants. However, we emphasize that their claimed data
correlation is virtually different from pairwise data. For instance, [25]
included the time series data while [30] took the records distance into
consideration. This means correlation in existing research is actually
individual to individual. Instead, the correlation of pairwise data is caused
by one individual’s participation in multiple pairs. Therefore, their schemes
cannot be freely extended to our problem.

###  II-B Privacy Implementation Methods

Given a specific privacy definition, current research suggests implementing
privacy by following three ways. (1) Output perturbation. This method adds
noise to the output of the algorithm, which can be easily understood when the
algorithm is as simple as a database operator, like averaging the salary of
the employees in a company [36]. For some machine learning models like
classification or regression, [37, 38] give the possible solutions. (2)
Objective perturbation. By adding an extra perturbed term in the objective,
[39, 37, 40, 41] show this strategy can works with a guarantee to the better
model utility. The perturbed term is usually not general for the other
objectives and needs some special considerations for different models. (3)
Gradient perturbation. This line of work manage to perturb the gradient during
the optimization, which has been widely used in [42, 43, 44, 45, 38, 46]. This
approach can be applied to most machine learning models including deep neural
networks. We present the recipe of DP in machine learning via gradient
perturbation. It mainly consists of 4 components.

  1. 1.

Privacy principle satisfying some requirements.

  2. 2.

Loss function designed for the specific problem.

  3. 3.

Upper bound for the gradient sensitivity.

  4. 4.

Noise injection during optimization.

##  III Preliminaries

Notation: A pairwise datum is a tuple $z_{ij}=(\Delta x_{ij},y_{ij})$, where
$\Delta x_{ij}=x_{i}-x_{j}\,(i\neq j,\Delta x_{ij}\in\mathbb{R}^{d})$ is the
feature difference between the individual $i$ and $j$, and pairwise label
$y_{ij}$ is a binary variable to encodes their relationship. Plus, $x_{i}$
could also be any representation learned by deep embedding. Omitting the
subscript of $z_{ij}$ whenever it clearly indicates a single pair, we have
$Z=\\{z^{1},z^{2},...,z^{K}\\}$ is a dataset of $K$ pairwise data which are
the input of a Dml algorithm. For a vector $v$, we use $||v||$, $||v||_{2}$ to
denote its $\ell_{1}$-norm and $\ell_{2}$-norm, respectively. In a graph, we
use $\langle,\rangle$ to denote a pair of nodes and use $(,)$ to denote an
edge or a path.

######  Definition 1.

(Edge-disjoint $s$-$t$ paths) Given an undirected graph and two nodes in it,
source $s$ and destination $t$, two paths from $s$ to $t$ are said edge-
disjoint if they do not share any edge.

######  Definition 2.

(Lipschitz function over model parameter $\theta$) A loss function
$f:\mathcal{C}\times\mathcal{Z}\rightarrow\mathbb{R}$
($\mathcal{C},\mathcal{Z}$ is parameter space and input space separately.) is
$h$-Lipschitz (under $\ell_{1}$\- norm) over $\theta$, if for any
$z\in\mathcal{Z}$ and $\theta_{1},\theta_{2}\in\mathcal{C}$, we have
$|f(\theta_{1},z)-f(\theta_{2},z)|\leq h||\theta_{1}-\theta_{2}||$.

######  Definition 3.

($\epsilon$-Differential Privacy [14]) A randomized algorithm $\mathcal{A}$ is
said to guarantee $\epsilon$-differentially private if for all datasets
$\mathcal{Z}$ and $\mathcal{Z}^{\prime}$ satisfying
$\mathcal{D}(\mathcal{Z},\mathcal{Z}^{\prime})=1$ ($\mathcal{Z}^{\prime}$ is
called the neighboring dataset of $\mathcal{Z}$, and $\mathcal{D}(,)$ means
the number of records two datasets differ.) and for any possible algorithm
output $o$ the following holds:

$Pr[\mathcal{A}(\mathcal{Z})=o]\leq e^{\epsilon}\cdot
Pr[\mathcal{A}(\mathcal{Z}^{\prime})=o],$ (1)

where $Pr[\cdot]$ is w.r.t. the randomness in $\mathcal{A}$, and the non-
negtive parameter $\epsilon$ is known as privacy budget.

Sensitivity based methods for $\epsilon$-DP leverage the Laplace Mechanism
[36] which has the following definitions.

######  Definition 4.

($\ell_{1}$-sensitivity) The $\ell_{1}$-sensitivity of a function
$g:\mathcal{Z}\rightarrow\mathbb{R}^{d}$ is:

$\Delta
g=\max_{\mathcal{D}(\mathcal{Z},\mathcal{Z}^{\prime})=1}\|g(\mathcal{\mathcal{Z}})-g(\mathcal{Z}^{\prime})\|.$
(2)

######  Definition 5.

(Laplace Mechanism) Given a function $g:\mathcal{Z}\rightarrow\mathbb{R}^{d}$,
the Laplace Mechanism $\mathcal{M}_{Lap}$ is defined as:

$\mathcal{M}_{Lap}(\mathcal{Z},g,\epsilon)=g(\mathcal{Z})+Y,$ (3)

where $Y$ is drawn from Laplace distribution $Lap(0,b)$ with $b=\frac{\Delta
g}{\epsilon}$. Laplace Mechanism preserves $\epsilon$-differentially private.

######  Remark.

Definition 3 can be relaxed to the _approximate_ DP according to [36] if
Definitions 2-5 are properly modified. The proposed Dpp can be also relaxed
with the same style. We leave these analyses to Appendix C for a supplemental
discussion.

Distance Metric Learning. Dml aims to learn a representative distance between
$i$ and $j$ defined by $\mathcal{D}_{M}(i,j)=\sqrt{\Delta x_{ij}^{T}M\Delta
x_{ij}}$, where $M\in\mathbb{R}^{d\times d}$ is the distance metric, a.k.a., a
symmetric positive semidefinite matrix. The original form of $M$ refers to the
case where $i$ and $j$ are drawn from the same distribution with covariance
matrix $\Sigma$, with $M=\Sigma^{-1}$. According to the literature [5, 6, 7,
8, 9, 10, 47], this metric can be better learned once the pairwise labels are
provided. Practically, pairwise label is often denoted as a binary variable
$y_{ij}\in\\{0,1\\}$ to indicate category. For instance, if two samples $i$
and $j$ are from the same class, then $y_{ij}=0$, and if they are from
different classes, $y_{ij}=1$. Let $M=W^{T}W$, where the transformation matrix
$W\in\mathbb{R}^{d^{\prime}\times d}$ ($1\leq d^{\prime}\leq d$) is free of
any constraint. As a result, $W$ can be optimized by minimizing the projected
distance between similar samples while maximizing the distance between
dissimilar ones.

##  IV Problem Understanding

###  IV-A Insights

Since the pairwise data encodes the interpersonal relationship, preserving the
privacy of involved pairwise relationship is the core problem in this work.
The algorithm designer is thought as the trusted party, and thus the whole
dataset can be directly fed into the algorithm, i.e., Dml. The user is
returned an available distance metric after they submit a query to the system
(Dml algorithm). To prevent any potential attacks in this setting, the
algorithm designer is responsible to develop a Dml algorithm which guarantees
the privacy of every pairwise relationship.

Practically, we are playing the role of the algorithm designer. Inspired by
[24], we adopt the following principle to preserve pairwise relationship. If
an attacker fails to infer the target relationship through her/his prior
knowledge, she/he cannot obtain more information by querying the Dml algorithm
either. Based on this principle, we have three key insights.

  1. 1.

Defending against the attacks that need query. If a targeted sample can be
inferred through its relations with other samples in the prior knowledge of
the attacker, privacy preserving techniques, e.g., DP, would never be possible
to defend the attacks. Therefore, as the algorithm designer, we are supposed
to recognize and formulate the maximum prior knowledge of an attacker, and
prevent them knowing more about data during their interactions with the Dml
algorithm. In contrast, the users who can already infer the target
relationship through their prior knowledge is outside of our scope, because
they do not need to query a Dml algorithm output.

  2. 2.

Preserving both feature difference and pairwise label. We are motivated by
preserving the privacy of pairwise relationship, i.e., $y_{ij}$, the last
element of the tuple $z_{ij}$, similar to _Attribute DP_ introduced in [23].
Unfortunately, it is actually not adequate to solely preserve $y_{ij}$.
Recalling the goal of Dml, the distance change between two individuals
reflects their relationship. For instance, two samples close to each other but
far away in the projected space are likely labeled as dissimilar, i.e.,
$||\Delta x_{ij}||$ is small while $\mathcal{D}_{M}(i,j)$ is large. As our
task is to return an available distance metric, we have to hide the
information of $\Delta x_{ij}$ to avert this kind of leakage. Therefore, we
conclude that to achieve the privacy of any pairwise relationship between $i$
and $j$, the privacy concern for $\Delta x_{ij}$ and $y_{ij}$ are both needed.
Please note it is not equal to preserving a single tuple $z_{ij}$, and see
Section V-A for more details.

  3. 3.

Enhancing the utility by introducing randomness as less as possible. Existing
works [37, 39, 40, 42, 43, 44, 38, 46, 41] applying DP in machine learning
algorithms have shown introducing randomness to the machine learning model is
provable to preserve the data privacy (Refer to the recipe in Section III).
Compared to DP in which randomness is only used to compensate the change of
any single sample, the privacy cost for pairwise data is apparently higher
because there are more than one pair’s change needs compensating. As a result,
the utility of output distance metric is decreased. This problem is alleviated
by using a sensitivity reduction technique (See section VI-B) which reduces
the amount of injected noise.

###  IV-B Clarification

Figure 4: Comparison between the samples fed to classification or regression
models and pairwise data fed to Dml algorithms. Left: Any two samples composed
of the feature $x_{i}$ ($x_{j}$) and its label $l_{i}$ ($l_{j}$) are
independent in existing ERM-based works. Right: Pairwise data are correlated
with each other because an individual may participate in multiple pairs.

We clarify two peculiar properties of Dml in this part.

_Transitive vs intransitive relationship._ Pairwise labels have different
semantics in different context, and we notice that they are not consistent
when considering their correlations. Summarily, there are mainly two types of
pairwise relationship; one is transitive and the other is intransitive.
Transitive relationship is like having the same disease or working in the same
company, and intransitive relationship is like being friends or hanging out
together. In the main body of this paper, we focus on the transitive
relationship and attribute intransitive relationship as its special case. It
is reasonable because transitive relationship requires more privacy concern
for the transitivity risks. Please note the naive edge differential privacy
(edge DP) [27, 28] is not applicable even for the intransitive relationship.
We leave the analysis of intransitive relationship to Appendix B.

_Dml vs classification/regression._ A formulated Dml loss function can be seen
as an instance of ERM-based [48] model. From this view, the transitivity
property of pairwise data makes Dml distinct from existing privacy works for
classification and regression [37, 42, 45, 46]. Fig. 4 exhibits their
comparison over input data. Concretely, any two data points fed to existing
ERM-based models are usually independent with each other, which naturally
matches the DP definition. For pairwise data, the dependence happens due to
the correlation both on feature differences and pairwise labels indicated as
edge on the right of Fig. 4. Please note although two types of correlation are
caused by the same reason, they are virtually not the identical problem. The
specific details are discussed in Section V.

##  V Differential Pairwise Privacy from Graph Perspective

Denoting each individual as a node and every pairwise data $z_{ij}$ as an
edge, we arrive at an _undirected_ graph $G=(V,E)$. Please note the node set
$V$ only keeps the identity of individuals while the edge set contains all the
information used for Dml training, i.e., $E=\\{z_{ij}=(\Delta
x_{ij},y_{ij})|(i,j\in V^{2}\wedge i\neq j\\}$. Thus, we can see that all the
privacy burden is on edges. Based on this graph, Differential Pairwise Privacy
(Dpp) is presented in this section. We will show this definition is a
nontrivial extension of DP (a.k.a. edge DP in the context of graph data) over
the pairwise data.

###  V-A Privacy Concern on Edge

Let $\langle s,t\rangle$ denote the target pair whose pairwise relationship is
the interest of the attacker. According to the statement in Section IV-A,
given the original graph $G$, we need to formulate the prior knowledge
$G^{\prime}$ of the attacker.

_Pairwise relationship correlation._ For binary category case, we summarize
there are three basic relationship inference patterns222The number of
inference patterns are actually determined by the category number, but even so
we can still come to the consistent conclusion if similar pairs are dominant
in the correlations.. Let $\sim,\nsim$ denote that two individuals are from
identical and different categories respectively, and $C$ is the category
number. We have

  * •

$s\sim i,\>i\sim t\Rightarrow s\sim t$

  * •

$s\sim i,\>i\nsim t\Rightarrow s\nsim t$

  * •

$s\nsim i,\>i\nsim t\Rightarrow s\sim t$ (iff $C=2$)

Thus, we conclude that where there is a path between two nodes there might be
a possible inference exposing their relationship. That is to say, for a target
pair $\langle s,t\rangle$, all the paths between $s$ and $t$ provide useful
inferences. According to Menger’s Theorem [49], the least cost of preventing
these inferences is properly breaking down $|\mathcal{P}_{st}|$ edges, where
$\mathcal{P}_{st}$ is the set of all edge-disjoint $s$-$t$ paths. We use an
example shown as Fig. 5 to clarify this thought. Fig. 5 (i@) shows the derived
graph $G$ formed by the given pairs. Inspecting the nodes $s$ and $t$, we find
there are totally three paths from $s$ to $t$, i.e., $(s,t)$, $(s,c,e,t)$, and
$(s,c,u,t$). We select two of them as edge-disjoint paths which are marked as
red and green line respectively in the Fig. 5 (ii@). Obviously, an instant way
to prevent the inference is to break the key edges, i.e., $(s,c)$ and $(s,t)$,
shown as the dashed edges in the Fig. 5 (iii@).

_Feature difference correlation._

Figure 5: Construction of neighboring graph w.r.t. the pair $\langle
s,t\rangle$. (i@) The graph encoding all the pairwise data. (ii@) Disjoint-
edge identification. (iii@) Two key edges $(s,c)$ and $(s,t)$ determining the
relationship inference. (iv@) Edge $(b,s)$ exposing the feature of the
individual $s$.

According to linear algebra, when an individual is included in a circle, its
feature can be calculated since the degree of freedom equals to the number of
constraints (i.e., edges). As shown in Fig. 5 (iv@), the feature of $s$ is
exposed once the information of edges $(s,a)$, $(a,b)$ and $(b,s)$ is known.
As hiding the feature of either $s$ or $t$ is adequate to privatize $\Delta
x_{st}$, one of the possible options is to delete the edge $(b,s)$ in this
example. It is observed that breaking down the edge-disjoint paths sometimes
help decrease the cycles used for feature inference, e.g., $s$ is also in the
cycle $(s,c,e,t,s)$. Thus, the edges determining $\Delta x_{st}$ inference are
only searched in the subgraph $G-\mathcal{P}_{st}$, i.e., removing all edges
belonging to $\mathcal{P}_{st}$ from $G$. Let $c_{s}$, $c_{t}$ denote the
number of edges that isolate the nodes $s$ and $t$ from the possible cycles
over $G-\mathcal{P}_{st}$, respectively. The minimum number of edges we should
delete is $\min\\{c_{s},c_{t}\\}$.

Summarily, it is concluded that the attacker who targets the relationship
between $s$ and $t$ should at least miss
$|\mathcal{P}_{st}|+\min(c_{s},c_{t})$ edges in $G$. This quantitative measure
actually generalizes the attacker’s prior knowledge but makes it easy to do
formulation. As any pair is the potential target pair, the attacker’s prior
knowledge $G^{\prime}$ should satisfy

$\mathcal{D}(G,G^{\prime})\geq\kappa,$ (4)

where $\mathcal{D}(,)$ means the number of edges two graph differs, and the
introduced variable $\kappa$ is calculated by

$\kappa=\max_{\forall s,t\in V,s\neq
t}{\\{|\mathcal{P}_{st}|+\min(c_{s},c_{t})\\}}.$ (5)

Particularly, we name $G^{\prime}$ as $\kappa$-neighboring graph of $G$ if the
equality exactly holds in Eq. (4).

###  V-B Differential Pairwise Privacy

Given a graph $G$, we name the attacker as $\kappa$-_Att_ if her/his prior
knowledge is exactly $\kappa$-neighboring graph of $G$. An attacker with fewer
edges prior, i.e., $\mathcal{D}(G,G^{\prime})>\kappa$, is unable to know more
than $\kappa$-_Att_ , while an attacker knowing more edges, i.e.,
$\mathcal{D}(G,G^{\prime})<\kappa$, is likely to have known the target pair
without any need of querying the Dml algorithm. Thus, $\kappa$-_Att_ defines
the worst case for pairwise data.

From Eq. (5), $\kappa$ is only determined by the given dataset. Although
searching the exact value of $\kappa$ is not an interactive component of the
Dml algorithm, it is very challenging to compute in reality. To overcome this
dilemma we propose an alternative approach to effectively calculate the value
of $\kappa$. The details are left to Appendix A for the interested readers.

Suppose $\kappa$ is known, based on the above analyses, we now give the
definition of differential pairwise privacy.

######  Definition 6.

($\epsilon$-Differential Pairwise Privacy (Dpp)). A randomized Dml algorithm
$\mathcal{A}_{DML}$ is said to guarantee $\epsilon$-differentially pairwise
privacy if for all datasets $G,G^{\prime}$ satisfying
$\mathcal{D}(G,G^{\prime})=\kappa$ and for any possible output $o_{M}$ the
following holds:

$Pr[\mathcal{A}_{DML}(G)=o_{M}]\leq e^{\epsilon}\cdot
Pr[\mathcal{A}_{DML}(G^{\prime})=o_{M}].$ (6)

Dpp takes good advantages of DP for pairwise data. More importantly, we
present its two valuable peculiarities.

  * •

Bearing individual participation. Our definition potentially allows attacker
to have prior knowledge about the participation of the target individuals. We
de facto privatize the participation of their pairwise relationship, i.e., the
connected edge. This is consistent with common sense. For instance, if an
attacker wants to know whether Alice and Bob have the same disease, he/she
must know they are contained in the target dataset.

  * •

Defending implicit attacks. No assumption is made to the given pairwise
labeled dataset. In practice, the data are often collected and labelled by
some domain experts who may be agnostic to the involved privacy issues. As
algorithm designers are the trusted party, it is their responsibility to
consider the possible pairwise data leakage risks. We have shown the proposed
Dpp is a feasible definition to deal with the risks.

##  VI Dpp-Dml Algorithm Design

According to the recipe of DP in Section III, since a new privacy definition
for pairwise data is built up, we now apply it to a specific Dml algorithm. In
this section, we make contrastive loss [50, 6, 10] a case study to present the
details about how to design a Dml algorithm that exactly satisfies Definition
6. Then we further improve the utility of the Dml algorithm while keeping its
intact privacy by proposing the sensitivity reduction approach.

###  VI-A Case Study with Contrastive Loss

Contrastive loss is a classic Dml model which measures pairwise data in a
projected space for better fitting the pairwise labels. For simplicity,
$z_{ij}=(\Delta x_{ij},y_{ij})$ is denoted by $z=(\Delta x,y)$, and the loss
function is written as

${L(W,z)=}\frac{1}{2}(1-y)D_{W}^{2}+\frac{1}{2}y\\{\max(0,m-D_{W})\\}^{2},$
(7)

where $W$ is the transformation matrix, $D_{W}=\|W\Delta x\|_{2}$ is the
distance of data point $i,j$ in the projected space, and $m>0$ is a margin
threshold used for avoiding collapsed solutions.

We follow the gradient perturbation approach applied in [42, 43, 45] to
implement the privacy of Dml algorithm. The consideration behind this approach
is that gradient computation is the unique component of Dml algorithm that
interacts with the input data.

As each row of $W$ is independent, the gradient w.r.t
$W_{r}(r=1,2,...,d^{\prime})$ is

$\displaystyle g_{r}(z)=\begin{cases}W_{r}\Delta x\Delta x^{T}&y=0\\\
\frac{D_{W}-m}{D_{W}}W_{r}\Delta x\Delta x^{T}&y=1,D_{W}<m\\\
\mathbf{0}&y=1,D_{W}\geq m\end{cases}.$ (8)

Before further computing the gradient sensitivity, we need the following
lemma.

######  Lemma 1.

Given a pair $(\Delta x,y)$, the gradient function $\|g_{r}(\cdot)\|$ is
infinite if only if $y=0$ and $\|W_{r}\|$ is unbounded.

###### Proof.

If $y=0$ and $\|W_{r}\|\rightarrow\infty$, clearly $\|g_{r}(\cdot)\|$ will be
infinite.

If $y=1$ and $D_{W}\geq m$, $\|g_{r}(\cdot)\|=0$.

If $y=1$ and $D_{W}<m$, we have

$\left.\begin{aligned} \|g_{r}(\cdot)\|&=|1-\frac{m}{\|W\Delta
x\|_{2}}|\cdot\|W_{r}\Delta x\Delta x^{T}\|\\\ &\overset{\leavevmode\hbox
to11.06pt{\vbox to11.06pt{\pgfpicture\makeatletter\hbox{\hskip
5.52959pt\lower-5.52959pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.32959pt}{0.0pt}\pgfsys@curveto{5.32959pt}{2.94348pt}{2.94348pt}{5.32959pt}{0.0pt}{5.32959pt}\pgfsys@curveto{-2.94348pt}{5.32959pt}{-5.32959pt}{2.94348pt}{-5.32959pt}{0.0pt}\pgfsys@curveto{-5.32959pt}{-2.94348pt}{-2.94348pt}{-5.32959pt}{0.0pt}{-5.32959pt}\pgfsys@curveto{2.94348pt}{-5.32959pt}{5.32959pt}{-2.94348pt}{5.32959pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}{\leq}\frac{m\|W_{r}\Delta
x\Delta x^{T}\|}{\frac{1}{\sqrt{d^{\prime}}}\|W\Delta x\|}-\|W_{r}\Delta
x\Delta x^{T}\|\\\ &\overset{\leavevmode\hbox to11.06pt{\vbox
to11.06pt{\pgfpicture\makeatletter\hbox{\hskip 5.52959pt\lower-5.52959pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.32959pt}{0.0pt}\pgfsys@curveto{5.32959pt}{2.94348pt}{2.94348pt}{5.32959pt}{0.0pt}{5.32959pt}\pgfsys@curveto{-2.94348pt}{5.32959pt}{-5.32959pt}{2.94348pt}{-5.32959pt}{0.0pt}\pgfsys@curveto{-5.32959pt}{-2.94348pt}{-2.94348pt}{-5.32959pt}{0.0pt}{-5.32959pt}\pgfsys@curveto{2.94348pt}{-5.32959pt}{5.32959pt}{-2.94348pt}{5.32959pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}{\leq}\frac{m\sqrt{d^{\prime}}|W_{r}\Delta
x|\cdot\|\Delta x^{T}\|}{\|W\Delta x\|}\\\ &\overset{\leavevmode\hbox
to11.06pt{\vbox to11.06pt{\pgfpicture\makeatletter\hbox{\hskip
5.52959pt\lower-5.52959pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.32959pt}{0.0pt}\pgfsys@curveto{5.32959pt}{2.94348pt}{2.94348pt}{5.32959pt}{0.0pt}{5.32959pt}\pgfsys@curveto{-2.94348pt}{5.32959pt}{-5.32959pt}{2.94348pt}{-5.32959pt}{0.0pt}\pgfsys@curveto{-5.32959pt}{-2.94348pt}{-2.94348pt}{-5.32959pt}{0.0pt}{-5.32959pt}\pgfsys@curveto{2.94348pt}{-5.32959pt}{5.32959pt}{-2.94348pt}{5.32959pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>(9)

where 1 follows the fact that for any vector $u\in\mathbb{R}^{d^{\prime}}$
$\|u\|_{1}\leq\sqrt{d^{\prime}}\|u\|_{2}$. 2 utilizes the facts that every
induced norm is submultiplicative, i.e., $\|W_{r}\Delta x\Delta
x^{T}\|\leq\|W_{r}\Delta x\|\cdot||\Delta x^{T}||$, and second term is non-
negative. 3 follows the fact $\|W_{r}\Delta x\|\leq\|W\Delta x\|$ and triangle
inequality, i.e., $\|\Delta x\|\leq\|x_{i}-x_{j}\|\leq 2\|x_{j}\|\leq 2$ where
$x_{i}$ is $\ell_{1}$ normalized.

Summarizing above results, we complete the proof. ∎

From Lemma 1 we can see $g_{r}(\cdot)$ is bounded if $\|W_{r}\|$ is smaller
than a const. A tender option is to impose some restriction on $W$. For
example, Jin et al. [51] employed a regularizer to measure the complexity of
$W$. Yet, it fails to bound the gradient during the entire optimization. As a
result, the sensitivity of gradient $g_{r}(\cdot)$ will be infinite according
to Definition 4. Chaudhuri et al. [37] averted this difficulty by constraining
the objective to be $h$-Lipschitz, which is simply achieved by the gradient
clipping technique [45]. We follow their schemes and formulate a new theorem.

######  Theorem 1.

If the objective function in Eq. (7) is $h$-Lipschitz w.r.t. $W_{r}$, the
$\ell_{1}$ gradient sensitivity $\Delta g_{r}$ on a minibatch $\mathcal{B}$ is
at most $\frac{2\kappa h}{|\mathcal{B}|}$, where $\kappa$ is specified by Eq.
(4).

Theorem 1 is a direct extension to the Corollary 8 of [37].

######  Remark.

With this gradient sensitivity, we can subsequently make Dml algorithm satisfy
Definition 6 by adding the noise sampled from the distribution
$Lap(0,\frac{2\kappa h}{|\mathcal{B}|\epsilon})$ to the iterative batch
gradient. Particularly, according to [42], the whole Dml algorithm will
satisfy $\epsilon$ pure Dpp if every batch is disjoint.

###  VI-B Improvement by Sensitivity Reduction

Figure 6: Gradient sensitivity reduction w.r.t. minibatch data. Left:
Individuals are $\ell_{1}$ normalized. The cyan line segment denotes the
factor $2h$ specified by Theorem 1. $p_{max}$ is the one of all batch members
whose gradient value is the largest, $q$ denotes the possible counterpart of
$p_{max}$ in the neighboring batch that satisfies Eq. (12). The orange line
segment connecting $p_{max}$ and $q$ is likely shorter than the cyan one.
Right: Individuals are $\ell_{2}$ normalized, and representation are
consistent with the left. This subfigure is also specified by Corollary 1 in
Appendix C.

The amount of injected noise to gradient is determined by the gradient
sensitivity. To improve the utility of optimization algorithm, an instant
option is to reduce the gradient sensitivity value. Keeping this thought in
mind we propose a gradient sensitivity reduction approach by exploring the
distribution of pairs within a minibatch during the optimization.

Since we locally add noise to every batch gradient, it does not cost much to
adjust the sensitivity in a minibatch. Specifically, the sensitivity based
method aims to find the maximum difference between the given batch and its any
possible neighbor over the gradient value. If $\kappa=1$, our goal is
equivalent to find out which pair is the most sensitive among a group of batch
members. We present an example in a two-dimensional space shown as Fig. 6,
where $p_{max}$ denotes the pair (regardless of its label dimension) who has
the maximum gradient value. Without loss of generality, we suppose the larger
distance between two pairs, the more different their gradients will be. Thus,
Theorem 1 actually employs the biggest sensitivity value represented by cyan
segment. In the presented case, $p_{max}$ is the most sensitive pair because
it has the largest possible distance to the $\ell_{1}$ norm boundary compared
to other pairs. Pair $q$ represents the farthest pair possibly occurring in
the neighboring batch. That means the sensitivity value is determined by the
distance of $p_{max}$ and $q$. Inspired by this observation, we propose
gradient sensitivity reduction approach. In the followings, instead of tuple
$z$ we abuse $p$ as a pair within a batch for the input of gradient function.

Algorithm 1 Dpp-Dml Algorithm

Input: Dataset $Z$ containing $K$ tuples

Parameter: Reduced dimension $d^{\prime}$, margin threshold $m$, Lipschitz
constant $h$, the distance $\kappa$, batch size $|\mathcal{B}|$, privacy
budget $\epsilon$, epoch number $T_{\max}$

Output: Distance metric $M$

1: Initialize transformation matrix $W$ randomly, step size $\eta=1$, counter
$\tau=0$, batch index $it_{bat}=\frac{K}{|\mathcal{B}|}$, privacy budget for
an epoch $\epsilon\prime=\frac{\epsilon}{T_{\max}}$

2: for $T=1,2,...,T_{\max}$ do

3: for $it=1,2...,it_{bat}$ do

4: $\tau\leftarrow\tau+1$

5: $\eta\leftarrow\frac{\eta}{\sqrt{\tau}}$

6: for $r=1,2,...,d^{\prime}$ do

7: Compute gradient $g_{r}(\cdot)$ w.r.t each $p_{j}\in\mathcal{B}_{it}$ by
Eq. (8) and then do gradient clipping
$\overline{g}_{r}(p_{j})=g_{r}(p_{j})/\max(1,\frac{\|g_{r}(p_{j})\|}{h})$

8: Compute
$g_{r}^{\prime}=\max(\overline{g}_{r}(p_{1}),\overline{g}_{r}(p_{2}),...,\overline{g}_{r}(p_{|\mathcal{B}|}))$

9: Compute
$g_{r}^{\prime\prime}=\min\\{h,\max(4||W_{r}||,2m\sqrt{d^{\prime}})\\}$

10: Add noise
$g_{r}^{*}=\frac{1}{|\mathcal{B}|}\sum_{j}\overline{g}_{r}(p_{j})+Lap(\frac{\kappa\Delta
g_{r}}{\epsilon^{\prime}})$, where $\Delta
g_{r}=\frac{g_{r}^{\prime}+g_{r}^{\prime\prime}}{|\mathcal{B}|}$

11: $W_{r}\leftarrow W_{r}-\eta g_{r}^{*}$

12: end for

13: end for

14: end for

15: $M=W^{T}*W$

(a) Original

(b) Dpp

(c) Dpp-S

(d) NonPriv

Figure 7: Dml projects original data into a new space. (a) A synthetic dataset
containing 200 data points drawn from two aligned strips. (b)-(d) Data
distribution after applying the metric learned by contrastive loss with Dpp,
Dpp-S (with sensitivity reduction), and NonPriv concern, respectively.

######  Theorem 2.

If the objective function in Eq. (7) is $h$-Lipschitz w.r.t. $W_{r}$, the
$\ell_{1}$ gradient sensitivity $\Delta g_{r}$ on any batch $\mathcal{B}$ is
at most $\frac{\kappa(g_{r}^{\prime}+g_{r}^{\prime\prime})}{|\mathcal{B}|}$,
where $\kappa$ is specified by Eq. (4), the batch gradient peak
$g_{r}^{\prime}=\max(||g_{r}(p_{1})||,...,||g_{r}(p_{|\mathcal{B}|})||)$, and
its possible counterpart
$g_{r}^{\prime\prime}=\min\\{h,\max(4||W_{r}||,2m\sqrt{d^{\prime}})\\}$.

###### Proof.

The worst case is that two neighbouring are exactly different by the
constraint ${\|\mathcal{B}-\mathcal{B}^{\prime}\|=\kappa}$. Since the pair
satisfying $y=1$ and $D_{W}\geq m$ has no contribution to the batch gradient,
$\ell_{1}$ sensitivity of $g_{r}(\cdot)$ can be written as

$\left.\begin{aligned} \Delta
g_{r}&=\max||\frac{1}{|\mathcal{B}|}(g_{r}(\mathcal{B})-g_{r}(\mathcal{B}^{\prime}))||\\\
&\leq\max_{j}\frac{\kappa}{|\mathcal{B}|}||(g_{r}(p_{j})-g_{r}({p_{j}}^{\prime}))||\;(j=1,2,...,|\mathcal{B}|)\\\
&\leq\frac{\kappa}{|\mathcal{B}|}(||(g_{r}(p_{max})||+||g_{r}(q))||).\end{aligned}\right.$
(10)

Let
$g_{r}^{\prime}\coloneqq\max(||g_{r}(p_{1})||,...,||g_{r}(p_{|\mathcal{B}|})||)$,
and we have

$||g_{r}(p_{max})||=g_{r}^{\prime}\leq h.$ (11)

Meanwhile, according to the proof of Lemma 1 we have
$||\frac{D_{W}-m}{D_{W}}W_{r}\Delta x\Delta x^{T}||\leq 2m\sqrt{d^{\prime}}$.
As $||W_{r}\Delta x\Delta x^{T}||\leq 4||W_{r}||$, the following inequality
must always hold

$||g_{r}(q)||\leq\min\\{h,\max(4||W_{r}||,2m\sqrt{d^{\prime}})\\}\coloneqq
g_{r}^{\prime\prime}.$ (12)

Therefore, we arrive at

$\Delta
g_{r}\leq\frac{\kappa(g_{r}^{\prime}+g_{r}^{\prime\prime})}{|\mathcal{B}|},$
(13)

which completes the proof. ∎

######  Remark.

Clearly we have $g_{r}^{\prime}=h$ if full batch gradient descent is applied.
Otherwise, the proposed approach takes advantage of the difference between
$g_{r}^{\prime}$ and $h$. Please note a minibatch is usually collected from a
component of $G$ ($G$ could be _disconnected_) according to [8, 9], instead of
globally sampling over the entire dataset $D$. Thus, $g_{r}^{\prime}$ is
diverse across different batches. It is noted that sensitivity reduction trick
also benefits from the difference between $g_{r}^{\prime\prime}$ and $h$. The
reason is that the gradient function of contrastive loss is piecewise
different. We attribute this point to the property of Dml loss function.

Combining with the steps of optimizing the contrastive loss, we summarize the
entire process into Algorithm 1 which naturally satisfies Definition 6. For
Laplacian mechanism, it is known that $Var(||g_{r}||)\propto(\frac{\Delta
g_{r}}{\epsilon^{\prime}})^{2}$, where $\epsilon^{\prime}$ is the fixed
privacy budget for each minibatch. This means the smaller sensitivity
factually implies the better utility of gradient. From the composition theory
[52], the privacy budget for an epoch is still $\epsilon^{\prime}$.
Particularly, once $T_{max}$ epochs are needed for better convergence, then
the accumulated privacy budget should be $\epsilon=\epsilon^{\prime}T_{\max}$.

##  VII Experiment

This section contains four parts. In the first part, the efficacy of the
proposed method is validated on a synthetic dataset. In the second part, based
on the same privacy mechanism, i.e., Laplace mechanism, we further compare
with other two methods on four real-world benchmarks. Their performance is
evaluated by classification accuracy on the test set. By replacing the based
privacy mechanisms we demonstrate the effectiveness of sensitivity reduction
in the third part. In the last part, we investigate the effects of different
parameters. Through all the experiments, the $\ell_{1}$-norm of every sample
is preprocessed smaller than 1 before used to compute the feature difference.
To guarantee the convergence, all the stochastic algorithms follow the step
size update rule in Algorithm 1, which typically enforces the conditions
$\sum_{\tau}\eta(\tau)=\infty$ and $\sum_{\tau}\eta^{2}(\tau)\leq\infty$.

###  VII-A Toy Example

We use the synthetic dataset introduced in [53] as a toy example for Dml
training. As shown in Fig. 7(a), raw data are composed of two classes, each of
which is single-Gaussian distributed and contains 100 points. By trickily
selecting 50 intra-class pairs within each class and 50 inter-class pairs, we
obtain an undirected acylic graph. In this experiment, contrastive loss is
optimized with NonPriv, Dpp, and Dpp-S (Dpp with sensitivity reduction)
concern separately. To verify their capacities, in this toy example, we
suppose the original data is accessible.

During the optimization, we empirically set $\epsilon=2$, $m=1$, $h=0.5$,
$|\mathcal{B}|=30$, and $T_{\max}=10$. Fig. 7(b)-7(d) show the transformed
data using the distance metrics learned by three privacy schemes,
respectively. For the convenient comparison, the transformed data are
exhibited in the same range map, $[0.08,0.32]$ horizontally, and $[0.19,0.45]$
vertically. Apparently, each of them now has the clearer structure than
original data. It is noticed that optimization with Dpp-S is very close to
NonPriv result. That means the sensitivity reduction technique improves
fidelity of output distance metric.

(a) Convergence comparison

(b) Sensitivity comparison

Figure 8: (a) The objective values of Eq. (7) versus iteration number with
NonPriv, Dpp and Dpp-S, respectively. (b) The sensitivity value $\frac{2\kappa
h}{|\mathcal{B}|}$ specified by Theorem 1 and reduced sensitivity specified by
Theorem 2 (exhibited by each dimension) versus iteration number.

(a) Adult

(b) Bank

(c) IPUMS-BR

(d) IPUMS-US

Figure 9: Classification accuracy of compared methods versus privacy budget
$\epsilon$ over four real-world datasets.

To better understand the above observations, we present the convergence curves
of each solution shown as Fig. 8(a). It is seen that NonPriv converge steadily
among three methods as its every iterative step is assigned with a clean
gradient. Compared to Dpp that uses the vanilla gradient sensitivity, the
objective value of Dpp-S decreases faster and has slighter fluctuation.
Particularly, Dpp seems to need more rounds to converge to a steady point. It
is consistent with our expectation because more noises are injected in this
privacy scheme. In addition, we notice that NonPriv objective value is not
strictly lower than Dpp-S. The reason is that the perturbation to the gradient
sometimes provides diverse exploration directions. However, the optimization
cannot benefit from random perturbations in a long period. Moreover, we
investigate the sensitivity value of each row of the transformation matrix
$W$, shown as Fig. 8(b). During a quantity of iterations, the sensitivity
value after reduction is dramatically lower than the standard one referred in
Lemma 1. We demonstrate the sensitivity reduction mitigates the utility
degeneration caused by a huge amount of redundant noise.

###  VII-B Comparison on Real-world Datasets

Four datasets about humans are employed here following the setting of recent
work [54]: (i) Adult [55] is extracted from the 1994 Census database which
contains the instances of personal income information. (ii) Bank [55] is
related with direct marketing campaigns of a Portuguese banking institution.
(iii) IPUMS-BR and (iv) IPUMS-US datasets are also about Census data collected
from IPUMS-International [56]. For imbalanced dataset (Adult and Bank), we
simply downsample the majority class during training. Table I briefly
summarizes the statistics of these datasets.

Table I: Statistics of datasets Dataset | Records (n) | Dime. | Pos./Neg. Pairs
---|---|---|---
Adult | 48,842 | 124 | 18,700/18,700
Bank | 45,211 | 33 | 8,464/8,464
IPUMS-BR | 38,000 | 53 | 30,016/30,016
IPUMS-US | 40,000 | 58 | 31,104/31,104

Since there is not any direct solution applying to the proposed secure metric
learning problem, we borrow the idea of _Node DP_ [57] and ERM-based input
perturbation (denoted by InputPer for short) [22] thought as two competing
methods. The former defends against the attacker who is unknown as many as the
maximum node degree edges, which is shown as the worst case of Dpp according
to the analysis in Appendix A. The latter assumes that data collector is also
not reliable that guarantees a stronger privacy. The advantage of InputPer for
pairwise data preserving is that no special consideration is needed for the
pair correlations, because any inference is now unreliable. Throughout all the
involved randomized algorithm, Laplace mechanism is used to extract noise. In
particular, for InputPer method, the laplacian noise is added to every
dimension over feature, while the label is randomly flipping by Warner’s model
[18]. To prevent $\kappa$ being too large, we empirically label the pairwise
data with the fixed density of constructed graph, i.e., $\frac{|E|}{|V|}=2$.
Batch size and Lipschiz const are set as $|\mathcal{B}|=50$ and $h=0.5$
respectively. For different datasets, the margin $m$ is preset as the average
distance of dissimilar pairs, i.e., $m=\frac{1}{K_{N}}\sum||\Delta x||$, where
$K_{N}$ is the number of dissimilar pairs. The output distance metric is then
evaluated by classification accuracy. Specifically, the distance metric $M$ is
firstly decomposed into transformation matrix $W$, and $W$ projects original
data into a new space. Then a $k$NN classifier ($k=5$) is trained on the
samples that are only employed in training pairs, and all the remaining
samples are regarded as the test set. Last but not least, every method is
repeated for 20 times and the average classification accuracy is eventually
reported.

Fig. 9 shows the classification results comparison versus different privacy
budgets. At the first glance, the classification accuracy of every randomized
method rises steadily with the increment of privacy budget. It is apparent
because less noise is injected to the gradient and the precision of distance
metric is improved with the same iterative steps. As Node DP injects more
noise than the proposed Dpp during each iteration, we find that its accuracy
is always lower than Dpp. Furthermore, Dpp with sensitivity reduction, i.e.
Dpp-S, effectively enhances the accuracy, especially on Adult and IPUMS-US
datasets. We observe that in most cases, InputPer shows the worst performance,
because InputPer is agnostic to the downstreaming application. Interestingly,
it outperforms other competitors on IPUMS-US dataset when $\epsilon$ is not
large. A reasonable explanation is that the dataset distance $\kappa$ or
maximum node degree is sometimes large (determined by randomly labelled
pairwise data) in other three methods, which results in a great amount
injected noise in optimization, while InputPer is not influenced by these
factors.

###  VII-C Privacy Mechanisms Comparison

(a) Adult

(b) Bank

Figure 10: Different $\epsilon$-DP mechanisms comparison in implementing Dpp
through their objective values.

Besides Laplace mechanism (and its sensitivity reduction version), we employ
two more $\epsilon$-DP mechanisms as the alternatives during implementing Dpp.
Soria-Comas and Domingo-Ferr [58] proposed a staircase-like mechanism which is
a variant of Laplace mechanism. Duchi et al. [59] proposed a method to perturb
multidimensional numeric tuples. For convenience, these four mechanisms are
orderly denoted by Lap, Lap-S, SCDF, and Duchi separately. We compare them by
replacing the gradient perturbation component and record their objective
values after an epoch optimization. Obviously, the smaller objective values
indicates better convergence. For simplicity we only do this group of
experiments on Adult and Bank datasets. The involved parameters setting
follows Section VII-B.

Fig. 10 presents the objective values of Eq. (7) when different privacy
mechanisms are employed. On both two datasets, we observe that SCDF converges
faster than Lap. This is because SCDF benefits from an adjustable parameter
controlling staircase width in Laplace mechanism. Staircase width is a
function of both sensitivity and privacy budget. Thus, it has the potential to
add less noise than Lap that enhances the utility. In addition, with the use
of reduced sensitivity trick, we find that Lap-S converges fastest in all
mechanism members. Duchi performs worst in this experiment compared with other
sensitivity based mechanisms. Specifically, all the mechanisms are extracting
unbiased noise, but the variance of Duchi for one-dimension data is
$(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}$ while the variance is
$\frac{4h^{2}}{|\mathcal{B}|^{2}{\epsilon}^{2}}$ for Lap. If we take $h=0.5$,
$|\mathcal{B}|=50$ and $\epsilon=1$, Duchi’s variance is around 10,000 times
larger than Lap’s!

###  VII-D Effects of Parameters

(a) Lipschitz constant

(b) Batch size

(c) Margin threshold

(d) Dimension reduction

Figure 11: Effects of several key parameters on Bank dataset.

We simply demonstrate the effects of involved parameters Lipschitz constant
$h$, batch size $|\mathcal{B}|$, margin threshold $m$, and reduced dimension
$d^{\prime}$ on Bank dataset.

To properly clip the gradient in each step, we need a good Lipschitz constant
$h$, because either a smaller or larger $h$ would cause the slower convergence
of optimization. On the one hand, if $h$ is too small, then most of gradients
will be clipped, and thus the objective converges slowly. On the other hand,
if $h$ is too large, the sensitivity value will be large according to Theorem
2, and consequently the amount of noise is increased in each step
optimization. In this experiment, let $\epsilon=4$ and $T_{\max}=3$, we
investigate the objective curves under different values of $h$. The
experimental results are shown as Fig. 11(a). We can observe the objective
converges faster when $h=0.5$. Particularly, when $h=2$, the objective value
initially increases within the a few of steps and then decreases steadily. It
is because the step size is large at the beginning of the optimization, which
amplifies the imprecise gradient caused by a relatively large $h$.

Similar to Lipschitz constant $h$, according to Theorems 1 and 2, the batch
size is also related to the convergence rate of the algorithm. We do grid
search for $|\mathcal{B}|$ and all of them are conducted for same epochs,
i.e., $T_{\max}=3$. The results are shown as Fig. 11(b). When the batch size
is larger, the total optimized steps are smaller, and vice versa. As
$|\mathcal{B}|=50$ reaches the lowest objective value within the limited
epochs, we empirically accept it as the default setting in other experiments.

The margin threshold $m$ is a hyperparameter for contrastive loss. Instead of
manually fixing it, we connect it with the average distance of dissimilar
pairs, i.e., $m=\frac{\rho}{K_{N}}\sum||\Delta x||$, where $\rho$ serves as a
ratio factor. In this experiment, we tune $m$ by changing the value of $\rho$
for NonPriv. Since the objective value is a function of $m$, we search $\rho$
by evaluating the corresponding testing accuracy. Fig. 11(c) shows the
accuracy comparison. Although $\rho=2$ obtains the best performance, the
accuracy of $\rho=1$ is only slightly lower than the best result. Thus, we
simply use the naive average distance in all of other experiments.

A distance metric can be decomposed into transformation matrix, which projects
the original data into different dimensional space, a.k.a. dimension
reduction. Fig. 11(d) presents the testing accuracy result versus different
reduced dimensions. The highest accuracy is obtained when $d^{\prime}=16$, and
the projection without dimension reduction ($d^{\prime}=32$) is close to the
best performance. Interestingly, it is observed that with the decrease of
dimension, the variance of testing accuracy increases significantly. We
conclude most of features are contributive in this dataset and each category
data are likely discriminative when more dimensions are kept.

##  VIII Discussion

Although we have made contrastive loss a case study in this paper, it is
believed that the proposed Dpp serves as a generalized privacy definition for
metric learning, such as triplet loss based works [5, 60], $(C+1)$-tuplet loss
[61], and $C$-pair loss objective [9]. However, we point out the work like [2]
cannot be privatized during the optimization because it employs an iterative
projection strategy (to positive/negative pairwise labeling set) that will
explicitly expose the pairwise information. More importantly, if the learning
model is neural network based, we can follow the recipe provided by [45] to
simply replace the corresponding gradient sensitivity over a _lot_ instead of
a batch.

Apart from Dml, there are many other machine learning algorithms that use
pairwise data during training. Similar to Dml, constrained clustering methods
have the better clustering performance if a small number of pairwise labeled
data is offered. The pairwise data provide _cannot-link_ or _must-link_ side
information which is useful to adjust the clustering structure. Thus the
proposed Dpp applies to this case. In crowd-sourcing community, workers are
allowed to pairwise label their preferences. Suppose privacy concern for
workers’ preference is desired, we can also define the pairwise privacy for
this kind of application.

##  IX Conclusion

This is a pilot work aiming to preserve the privacy of pairwise data for
distance metric learning. From the view of empirical risk minimization, this
work, the first of its kind in machine learning community, targets the input
data that are correlated. In the paper we first study how the pairwise data
could be leaked during training a distance metric learning model, then and we
propose a new privacy definition to this problem. The key idea of our method
is utilizing the graph property to real the involved correlations, which helps
to construct the prior knowledge of the real-world attacker. We claim this
work is different from previous privacy on graphs. Particularly, we clarify
the connections between the proposed privacy and two classical privacy
definitions over graph, edge differential privacy and node differential
privacy. Some interesting conclusions have been presented in the paper.

There are two interesting open problems that need further exploration. One is
how to design a general privacy implementation method that is not limited to
the exact optimization strategy. The other problem is how to use some database
statistics rather than pairwise data to do distance metric learning, because
it is expected have the higher utility.

##  Appendix A An efficient approach for deriving the $\kappa$ in Eq. (5)

According to Fig. 5 (iv@), we find that the privacy for pairwise relationship
and feature difference can be both eventually attributed to the 1-hop
neighbors of the target node, i.e. $s$ or $t$. Inspired by this observation,
we present the following proposition.

######  Proposition 1.

For a target pair $(s,t)$, concerning the correlation both on pairwise
relationship and feature difference, we have

$|\mathcal{P}_{st}|+\min\\{c_{s},c_{t}\\}\leq De(s)-Co_{+}(\bar{s}),$ (14)

where $De(s)$ means the degree of $s$ and $Co_{+}(\bar{s})$ represents the
increased number of components by removing $s$ from $G$. Particularly, the
equality holds if and only if $c_{s}=c_{t}$.

###### Proof.

If all the 1-hop neighbors of $s$ are connected to $t$, there must exist a
node $t^{\prime}\in V$ that causes $De(s)$ edge-disjoint $s$-$t^{\prime}$
paths, i.e. $|\mathcal{P}_{st}|\leq|\mathcal{P}_{st^{\prime}}|=De(s)$.
Otherwise, $|\mathcal{P}_{st}|<De(s)$ always holds. As a result, there are at
most $De(s)-|\mathcal{P}_{st}|$ edges that can provide feature inference of
$s$. From the graph theory, the increased number of components
$Co_{+}(\bar{s})$ should satisfy the equality
$Co_{+}(\bar{s})=De(s)-|\mathcal{P}_{st}|-c_{s}$. Due to the fact that
$\min{(c_{s},c_{t})}\leq c_{s}$, we arrive at Eq. (14).∎

For all the possible pair, we have

$\kappa^{\prime}=\max_{\forall s\in V}\\{De(s)-Co_{+}(\bar{s})\\},$ (15)

where $\kappa^{\prime}$ is a upper bound of $\kappa$ in Eq. (5). As the
component number of a graph can be efficiently calculated, the whole time
complexity for searching $\kappa^{\prime}$ is $\mathcal{O}(|V|(|V|+|E|))$.
Furthermore, one can greedily search two connected nodes having the maximum
sum for the right part of Eq. (14) to force $\kappa^{\prime}=\kappa$.

More importantly, from Proposition 1, we instantly conclude that Dpp is upper
bounded by the known _Node DP_ [27]. Deleting a node in graph equals to
removing all the edges associated with this node. Thus, we have
$\kappa=\max_{\forall s\in V}{De(s)}$ from the view of Node DP. We conclude
that the proposed Dpp is superior to Node DP. Particularly, if the derived
graph is a tree with large degree node, $\kappa$ is 1 for Dpp while $\kappa$
is the maximum node degree for Node DP.

##  Appendix B Dpp for Intransitive Relationship Case

The intransitive relationship is a relaxed version of transitive relationship.
For the pairwise data with intransitive relationship, we only need to consider
the correlation on feature difference. For a target pair $\langle s,t\rangle$,
if $s$ and $t$ are mutually 1-hop neighbors, then there should be
$1+\min(c_{s},c_{t})$ edges that need to concern for the worst case, where
$c_{s}$ and $c_{t}$ is searched on the subgraph $G-\langle s,t\rangle$.
Otherwise, only the number of $\min(c_{s},c_{t})$ edges need concerning, where
$c_{s}$ and $c_{t}$ are searched over the entire graph. It is noted that the
former case equals to the transitive relationship when
$\mathcal{P}_{st}=\\{(s,t)\\}$. For the latter case, similar to Proposition 1
we have

$\min(c_{s},c_{t})\leq De(s)-Co_{+}(\bar{s})-1.$ (16)

This inequality follows the fact that $c_{s}=De(s)-Co_{+}(\bar{s})-1$. One can
define $\kappa$-neighboring graph of $G$ now by assigning the greater value of
two cases to $\kappa$. Since the value of $\kappa$ is determined by the given
pairwise data, edge DP cannot handle this case.

##  Appendix C Sensitivity Shrinking For Approximate Dpp

We first prepare the basic ingredients for approximate Dpp. Suppose the
individual features are $\ell_{2}$ normalized, i.e. $||x_{i}||_{2}\leq 1$. We
modify the $\ell_{1}$-norm in Definitions 2 and 4 into $\ell_{2}$-norm and
draw noise $Y$ from Gaussian distribution $\mathcal{N}(0,\sigma^{2}I_{d})$
with $\sigma\geq\frac{\sqrt{2\ln(1.25/\delta)}\Delta g}{\epsilon}$, which
naturally updates Definition 3 to be the approximate DP.

From the gradient function in Eq. (8), if $y=1,D_{W}<m$ we have

$||g_{r}(\cdot)||_{2}=|1-\frac{m}{||W\Delta x||_{2}}|\cdot||W_{r}\Delta
x\Delta x^{T}||_{2}\leq 2m.$ (17)

Consequently, we have the following Corollary to calculate the sensitivity for
the approximate Dpp by extending Theorem 2 (also refer to the right of Fig.
6).

######  Corollary 1.

If the objective function in Eq. (7) is $h$-Lipschitz ($\ell_{2}$ norm) w.r.t
$W_{r}$, the $\ell_{2}$ gradient sensitivity $\Delta g_{r}$ on any batch
$\mathcal{B}$ is at most
$\frac{\kappa(g_{r}^{\prime}+g_{r}^{\prime\prime})}{|\mathcal{B}|}$, where the
batch gradient peak
$g_{r}^{\prime}=\max(||g_{r}(p_{1})||_{2},...,||g_{r}(p_{|\mathcal{B}|})||_{2})$,
and its possible counterpart
$g_{r}^{\prime\prime}=\min\\{h,\max(4||W_{r}||_{2},2m)\\}$.

The benefit of concerning approximate Dpp is that the total privacy cost can
be reduced by slightly increasing the failure of probability of $\delta$.
Since the proposed Dpp definition is consistent with DP over structure, the
advanced composition theory in [36] is naturally inherited in our work.
Furthermore, we refer interested readers to [62] for a comparison of more DP
variants which provide improved composition theories.

## References

  * [1] A. Bellet, A. Habrard, and M. Sebban, “A survey on metric learning for feature vectors and structured data,” _arXiv preprint arXiv:1306.6709_ , 2013.
  * [2] E. P. Xing, M. I. Jordan, S. J. Russell, and A. Y. Ng, “Distance metric learning with application to clustering with side-information,” in _Advances in neural information processing systems_ , 2003, pp. 521–528.
  * [3] I. W. Tsang and J. Kwok, “Distance metric learning with kernels,” in _International Conference on Artificial Neural Networks_ , 2003, pp. 126–129.
  * [4] J. Kwok and I. W. Tsang, “Learning with idealized kernels,” in _International Conference on Machine Learning_ , 2003, pp. 400–407.
  * [5] K. Q. Weinberger and L. K. Saul, “Distance metric learning for large margin nearest neighbor classification,” _Journal of Machine Learning Research_ , vol. 10, no. Feb, pp. 207–244, 2009.
  * [6] M. Guillaumin, J. Verbeek, and C. Schmid, “Is that you? metric learning approaches for face identification,” in _2009 IEEE 12th international conference on computer vision_. IEEE, pp. 498–505.
  * [7] Y. Ying and P. Li, “Distance metric learning with eigenvalue optimization,” _Journal of Machine Learning Research_ , vol. 13, no. Jan, pp. 1–26, 2012\.
  * [8] J. Hu, J. Lu, and Y.-P. Tan, “Discriminative deep metric learning for face verification in the wild,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2014, pp. 1875–1882.
  * [9] K. Sohn, “Improved deep metric learning with multi-class n-pair loss objective,” in _Advances in Neural Information Processing Systems_ , 2016, pp. 1857–1865.
  * [10] P. Xie, H. Zhang, Y. Zhu, and E. P. Xing, “Nonoverlap-promoting variable selection,” in _International Conference on Machine Learning_ , 2018, pp. 5409–5418.
  * [11] F. Wang, J. Sun, and S. Ebadollahi, “Integrating distance metrics learned from multiple experts and its application in patient similarity assessment,” in _Proceedings of the 2011 SIAM International Conference on Data Mining_. SIAM, 2011, pp. 59–70.
  * [12] M. Huai, C. Miao, Q. Suo, Y. Li, J. Gao, and A. Zhang, “Uncorrelated patient similarity learning,” in _Proceedings of the 2018 SIAM International Conference on Data Mining_. SIAM, 2018, pp. 270–278.
  * [13] Q. Suo, W. Zhong, F. Ma, Y. Yuan, J. Gao, and A. Zhang, “Metric learning on healthcare data with incomplete modalities,” in _Proceedings of the 28th International Joint Conference on Artificial Intelligence_. AAAI Press, 2019, pp. 3534–3540.
  * [14] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of cryptography conference_. Springer, 2006, pp. 265–284.
  * [15] Z. Ji, Z. C. Lipton, and C. Elkan, “Differential privacy and machine learning: a survey and review,” _arXiv preprint arXiv:1412.7584_ , 2014.
  * [16] A. Narayanan and V. Shmatikov, “Robust de-anonymization of large datasets (how to break anonymity of the netflix prize dataset),” _University of Texas at Austin_ , 2008.
  * [17] L. Sweeney, “Matching known patients to health records in washington state data,” 2013.
  * [18] S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” _Journal of the American Statistical Association_ , vol. 60, no. 309, pp. 63–69, 1965.
  * [19] M. Hay, L. Elagina, and G. Miklau, “Differentially private rank aggregation,” in _Proceedings of the 2017 SIAM International Conference on Data Mining_. SIAM, 2017, pp. 669–677.
  * [20] J. Joy and M. Gerla, “Differential privacy by sampling,” _arXiv preprint arXiv:1708.01884_ , 2017.
  * [21] H. Sun, B. Dong, H. W. Wang, T. Yu, and Z. Qin, “Truth inference on sparse crowdsourcing data with local differential privacy,” in _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 2018, pp. 488–497.
  * [22] K. Fukuchi, Q. K. Tran, and J. Sakuma, “Differentially private empirical risk minimization with input perturbation,” in _International Conference on Discovery Science_. Springer, 2017, pp. 82–90.
  * [23] D. Kifer and A. Machanavajjhala, “No free lunch in data privacy,” in _Proceedings of the 2011 ACM SIGMOD International Conference on Management of data_. ACM, 2011, pp. 193–204.
  * [24] ——, “A rigorous and customizable framework for privacy,” in _Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems_. ACM, 2012, pp. 77–88.
  * [25] S. Song, Y. Wang, and K. Chaudhuri, “Pufferfish privacy mechanisms for correlated data,” in _Proceedings of the 2017 ACM International Conference on Management of Data_. ACM, 2017, pp. 1291–1306.
  * [26] V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, “Private analysis of graph structure,” _Proceedings of the VLDB Endowment_ , vol. 4, no. 11, pp. 1146–1157, 2011.
  * [27] M. Hay, C. Li, G. Miklau, and D. Jensen, “Accurate estimation of the degree distribution of private networks,” in _Data Mining, 2009. ICDM’09. Ninth IEEE International Conference on_. IEEE, 2009, pp. 169–178.
  * [28] V. Rastogi, M. Hay, G. Miklau, and D. Suciu, “Relationship privacy: output perturbation for queries with joins,” in _Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 2009, pp. 107–116.
  * [29] J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao, “Private release of graph statistics using ladder functions,” in _Proceedings of the 2015 ACM SIGMOD international conference on management of data_ , 2015, pp. 731–745.
  * [30] T. Zhu, P. Xiong, G. Li, and W. Zhou, “Correlated differential privacy: Hiding information in non-iid data set,” _IEEE Transactions on Information Forensics and Security_ , vol. 10, no. 2, pp. 229–242, 2014.
  * [31] C. Liu, S. Chakraborty, and P. Mittal, “Dependence makes you vulnberable: Differential privacy under dependent tuples.” in _NDSS_ , vol. 16, 2016, pp. 21–24.
  * [32] J. Zhao, J. Zhang, and H. V. Poor, “Dependent differential privacy for correlated data,” in _2017 IEEE Globecom Workshops (GC Wkshps)_. IEEE, 2017, pp. 1–7.
  * [33] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” in _Proceedings of the thirty-ninth annual ACM symposium on Theory of computing_. ACM, 2007, pp. 75–84.
  * [34] K. Lee, H. Kim, K. Lee, C. Suh, and K. Ramchandran, “Synthesizing differentially private datasets using random mixing,” in _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2019, pp. 542–546.
  * [35] Y. Zhao, G. Yang, X. Fang, and B. Ge, “Preventing privacy disclosure from hostility attack base on associated attributes,” in _International Conference on Applications and Techniques in Cyber Security and Intelligence_. Springer, 2019, pp. 1315–1325.
  * [36] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [37] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization,” _Journal of Machine Learning Research_ , vol. 12, no. Mar, pp. 1069–1109, 2011.
  * [38] J. Zhang, K. Zheng, W. Mou, and L. Wang, “Efficient private erm for smooth objectives,” _arXiv preprint arXiv:1703.09947_ , 2017.
  * [39] K. Chaudhuri and C. Monteleoni, “Privacy-preserving logistic regression,” in _Advances in neural information processing systems_ , 2009, pp. 289–296.
  * [40] D. Kifer, A. Smith, and A. Thakurta, “Private convex empirical risk minimization and high-dimensional regression,” in _Conference on Learning Theory_ , 2012, pp. 25–1.
  * [41] K. Talwar, A. Thakurta, and L. Zhang, “Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry,” _arXiv preprint arXiv:1411.5417_ , 2014.
  * [42] S. Song, K. Chaudhuri, and A. D. Sarwate, “Stochastic gradient descent with differentially private updates,” in _2013 IEEE Global Conference on Signal and Information Processing_. IEEE, 2013, pp. 245–248.
  * [43] R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_. IEEE, 2014, pp. 464–473.
  * [44] K. Talwar, A. G. Thakurta, and L. Zhang, “Nearly optimal private lasso,” in _Advances in Neural Information Processing Systems_ , 2015, pp. 3025–3033.
  * [45] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2016, pp. 308–318.
  * [46] D. Wang, M. Ye, and J. Xu, “Differentially private empirical risk minimization revisited: Faster and more general,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 2722–2731.
  * [47] W. Li, J. Huo, Y. Shi, Y. Gao, L. Wang, and J. Luo, “Online deep metric learning,” _arXiv preprint arXiv:1805.05510_ , 2018.
  * [48] V. Vapnik, “Principles of risk minimization for learning theory,” in _Advances in neural information processing systems_ , 1992, pp. 831–838.
  * [49] F. Göring, “Short proof of menger’s theorem,” _Discrete Mathematics_ , vol. 219, no. 1-3, pp. 295–296, 2000.
  * [50] S. Chopra, R. Hadsell, and Y. LeCun, “Learning a similarity metric discriminatively, with application to face verification,” in _Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on_ , vol. 1. IEEE, 2005, pp. 539–546.
  * [51] R. Jin, S. Wang, and Y. Zhou, “Regularized distance metric learning: Theory and algorithm,” in _Advances in neural information processing systems_ , 2009, pp. 862–870.
  * [52] F. D. McSherry, “Privacy integrated queries: an extensible platform for privacy-preserving data analysis,” in _Proceedings of the 2009 ACM SIGMOD International Conference on Management of data_. ACM, 2009, pp. 19–30.
  * [53] B. Nguyen, C. Morell, and B. De Baets, “Supervised distance metric learning through maximization of the jeffrey divergence,” _Pattern Recognition_ , vol. 64, pp. 215–225, 2017.
  * [54] J. Lee and D. Kifer, “Concentrated differentially private gradient descent with adaptive per-iteration privacy budget,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM, 2018, pp. 1656–1665.
  * [55] D. Dua and E. Karra Taniskidou, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * [56] S. Ruggles, K. Genadek, R. Goeken, J. Grover, and M. Sobek, “Integrated public use microdata series, minnesota population center.” [Online]. Available: http://international.ipums.org
  * [57] S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith, “Analyzing graphs with node differential privacy,” in _Theory of Cryptography Conference_. Springer, 2013, pp. 457–476.
  * [58] J. Soria-Comas and J. Domingo-Ferrer, “Optimal data-independent noise for differential privacy,” _Information Sciences_ , vol. 250, pp. 200–214, 2013\.
  * [59] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Minimax optimal procedures for locally private estimation,” _Journal of the American Statistical Association_ , vol. 113, no. 521, pp. 182–201, 2018.
  * [60] G. Chechik, V. Sharma, U. Shalit, and S. Bengio, “Large scale online learning of image similarity through ranking,” _Journal of Machine Learning Research_ , vol. 11, no. Mar, pp. 1109–1135, 2010.
  * [61] H. Oh Song, Y. Xiang, S. Jegelka, and S. Savarese, “Deep metric learning via lifted structured feature embedding,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 4004–4012.
  * [62] B. Jayaraman and D. Evans, “Evaluating differentially private machine learning in practice.”