# Membership Inference Attack on Graph Neural Networks

Iyiola E. Olatunji
L3S Research Center,
Hannover, Germany.
<EMAIL_ADDRESS>Wolfgang Nejdl
L3S Research Center,
Hannover, Germany.
<EMAIL_ADDRESS>Megha Khosla
L3S Research Center,
Hannover, Germany.
<EMAIL_ADDRESS>
###### Abstract

Graph Neural Networks (GNNs), which generalize traditional deep neural
networks on graph data, have achieved state-of-the-art performance on several
graph analytical tasks. We focus on how trained GNN models could leak
information about the _member_ nodes that they were trained on. We introduce
two realistic settings for performing a membership inference (MI) attack on
GNNs. While choosing the simplest possible attack model that utilizes the
posteriors of the trained model (black-box access), we thoroughly analyze the
properties of GNNs and the datasets which dictate the differences in their
robustness towards MI attack. While in traditional machine learning models,
overfitting is considered the main cause of such leakage, we show that in GNNs
the additional structural information is the major contributing factor. We
support our findings by extensive experiments on four representative GNN
models. To prevent MI attacks on GNN, we propose two effective defenses that
significantly decreases the attacker’s inference by up to 60% without
degradation to the target model’s performance. Our code is available at
https://github.com/iyempissy/rebMIGraph.

##  I Introduction

Graph neural networks (GNNs) have gained substantial attention from academia
and industry in the past few years with high-impact applications ranging from
the analysis of social networks, recommender systems to biological networks.
One of the most popular tasks is that of _node classification_ in which the
goal is to predict the unknown node labels. These models differ from the
traditional machine learning (ML) models, in that they use additional
relational information among the node instances to make predictions. In fact,
the graph convolution-based model [7] which is the most popular class of GNNs
embeds graph structure into the model itself by computing representation of a
node via recursive aggregation and transformation of feature representations
of its neighbors. We take the first step in exposing the vulnerability of such
models to _membership inference_ (MI) attacks. In particular, we ask _whether
the trained GNN model can be used to identify the input instances (nodes) that
it was trained on._

To motivate the importance of the problem for graphs, suppose a researcher has
a list of patients infected with COVID19. The researcher is interested in
understanding the various factors contributing to the infection. To account
for the factors such as their social activity, she might want to utilize
knowledge of friendship/social connection known among the patients. She then
trains a GNN model on the graph induced on the nodes of interest and uses the
trained node representations as additional input for her disease analysis
models. A successful MI attack on the trained model would reveal the list of
infected persons even though the model might have not used any disease-related
sensitive information.

The goal of MI attack [14, 12] is to distinguish between the _target_ model’s
behavior for the inputs it encountered during training from the ones which it
did not. The inputs to the attack model are the class probabilities
(posteriors) or the confidence values output by the target model for the
corresponding data point. Thus, the attacker or adversary only requires
_black-box_ access to the model where she can query the model on her desired
data record and obtain the model predictions (output class probabilities).

While membership inference has been well studied in the context of traditional
ML models [14, 13] like convolution neural networks (CNNs) and multilayer
perceptron (MLP), GNNs has so far escaped attention. Much of the success of MI
attacks in traditional ML models has been attributed to the model’s tendency
to overfit or memorize the dataset [20]. Overfitting leads to the assignment
of high confidence scores to data records seen during training as compared to
new data it encountered during testing, making it possible to distinguish
between the instance types from the prediction scores. We ask _if overfitting
in GNNs is also the main contributing factor for successful membership
inference._ We discover that even if a GNN model generalizes well to unseen
data, it can still be highly prone to MI risks. The _encoding of the graph
structure into the model_ is what makes a GNN powerful but it is exactly this
property that makes it much more vulnerable to privacy attacks. Therefore,
unlike other models, reducing overfitting might not alone lead to higher
robustness against privacy risks.

While we showed that all GNN models are vulnerable to MI attack, we observed
differences in attack success rate. We explain these differences in terms of
differing dataset and model properties using insights from our large scale
experimental analysis. We further develop defense mechanisms based on _output
perturbation_ and _query neighborhood perturbation_ strategies. Our empirical
results show that our defenses can effectively defend against MI attacks on
GNNs by reducing the attacker’s inference by over 60% with negligible loss in
the target model’s inference.

To summarize, our key contributions are as follows.

  1. 1.

We introduce two realistic settings for carrying out MI attack on GNNs.

  2. 2.

We perform an extensive experimental study to expose the risks of privacy
leakage in GNN models. We further attribute the differences between the
model’s robustness towards MI attack to the dataset properties and the model
architecture.

  3. 3.

Contrary to popular belief, we show that for GNNs, lack of overfitting does
not guarantee robustness towards privacy attacks.

  4. 4.

We propose two defense mechanisms (based on output and query neighborhood
perturbation) against MI attacks in GNNs that significantly degrade attack
performance without compromising the target model’s utility.

##  II Background and Related Works

###  II-A Graph Neural Networks

Graph Neural Networks popularized by graph convolutional networks (GCNs) and
their variants, generalize the convolution operation for irregular graph data.
These methods encode graph structure directly into the model. In particular,
the node representation is computed by recursive aggregation and
transformation of feature representations of its neighbors.

Let $\boldsymbol{x}_{i}^{(\ell)}$ denote the feature representation of node
$i$ at layer $\ell$ and ${\mathcal{N}}_{i}$ denotes the set of its 1-hop
neighbors. Formally, the $\ell$-th layer of a general graph convolutional
operation can then be described as

$\displaystyle\boldsymbol{z}_{i}^{(\ell)}=$
$\displaystyle\operatorname{AGGREGATION}^{(\ell)}\left(\left\\{\boldsymbol{x}_{i}^{(\ell-1)},\left\\{\boldsymbol{x}_{j}^{(\ell-1)}\mid
j\in{\mathcal{N}}_{i}\right\\}\right\\}\right)$ (1)
$\displaystyle\boldsymbol{x}_{i}^{(\ell)}=$
$\displaystyle\operatorname{TRANSFORMATION}^{(\ell)}\left(\boldsymbol{z}_{i}^{(\ell)}\right)$
(2)

Finally, a softmax layer is applied to the node representations at the last
layer (say $L$) for the final prediction of node classes,

$\displaystyle\boldsymbol{y}_{i}\leftarrow\operatorname{softmax}(\boldsymbol{z}_{i}^{(L)}\mathbf{W}),$
(3)

where $\boldsymbol{y}_{i}\in\mathbb{R}^{c}$, $c$ is the number of classes and
$\mathbf{W}$ is a learnable weight matrix. Each element
$\boldsymbol{y}_{i}(j)$ corresponds to the (predicted) probability (or
posterior) that node $i$ is assigned to class $j$.

We focus on four representative models of this family which differ either on
one of the above two steps of aggregation and transformation. In the
following, we briefly describe these models and their differences.

Graph Convolutional Network (Gcn) [7]. Let $d_{i}$ denote the degree of node
$i$. The aggregation operation in Gcn is then given as

$\boldsymbol{z}_{i}^{(\ell)}\leftarrow\sum_{j\in\mathcal{N}(i)\cup
i}\frac{1}{\sqrt{d_{i}d_{j}}}\boldsymbol{x}_{j}^{(\ell-1)}.$ (4)

Gcn performs a non-linear transformation over the aggregated features to
compute the representation at layer $\ell$.

$\boldsymbol{x}_{i}^{(\ell)}\leftarrow\operatorname{ReLU}\left(\boldsymbol{z}_{j}^{(\ell-1)}\mathbf{W}^{(\ell)}\right).$
(5)

Simplifying Graph Convolutional Networks (Sgc) [18]. The authors in [18] argue
that the non-linear activation function in Gcn is not critical for the node
classification task and completely skips the non-linear transformation step.
In particular, in an $L$ layer Sgc model, $L$ aggregation steps are applied as
given by (4) followed by final prediction (as in (3)).

Graph Attention Networks (Gat) [16]. Gat modifies the aggregation operation in
(4) by introducing attention weights over the edges. In particular, the $p$-th
attention operation results in the following aggregation operation, where

$\boldsymbol{z}_{i}^{(\ell,p)}\leftarrow\sum_{j\in\mathcal{N}_{i}\cup
i}\alpha_{ij}^{p}\boldsymbol{x}_{j}^{(\ell-1)},$ (6)

where $\alpha_{ij}^{p}$ are normalized attention coefficients computed by the
p-th attention mechanism. In the transformation step, the $P$ intermediate
representations corresponding to $P$ attention mechanisms are concatenated
after a non-linear transformation as in (5) to obtain the representation at
layer $\ell$.

$\boldsymbol{x}_{i}^{(\ell)}=||_{p=1}^{P}\operatorname{ReLU}\left(\boldsymbol{z}_{i}^{(\ell,p)}\mathbf{W}^{(p\ell)}\right),$
(7)

where $||$ denotes concatenation operator and $\mathbf{W}^{(p\ell)}$ is the
corresponding weight matrix at layer $\ell$. For more details of the attention
computations, we refer the reader to [16].

GraphSage (Sage) [3]. GraphSage generalizes the graph convolutional framework
by proposing several aggregation operations. To achieve scalability, rather
than using the complete 1-hop neighborhood of the node, it samples a fixed
number of neighbors randomly at each layer for each node. Let
$\mathcal{\tilde{N}}(i)$ denote the set of sampled neighbors for node $i$. The
aggregation (we use mean aggregation in this work) operation as applied in
Sage is given as follows.

$\boldsymbol{z}_{i}^{(\ell)}\leftarrow\operatorname{CONCAT}\left(\boldsymbol{x}_{i}^{(\ell-1)},\frac{1}{|\mathcal{\tilde{N}}(i)|}\sum_{j\in\mathcal{\tilde{N}}(i)}\boldsymbol{x}_{j}^{(\ell-1)}\right).$
(8)

The transformation operation stays the same as in (5).

Our approach is the first work to compare different graph convolution-based
models with respect to their vulnerability to MI attack. More precisely, we
ask _if the differences in the aggregation and transformation operations of
the graph convolution-based models lead to differences in privacy risks._

###  II-B Privacy attacks on Machine Learning

Several attacks on machine learning models have been proposed including
membership inference attack [14, 1, 19, 9, 13] where the adversary aims to
infer whether a data sample was part of the data used in training a model or
not. In the attribute inference attack, the attacker’s goal is to reconstruct
the missing attributes given partial information about the data record and
access to the machine learning model [21, 19, 5]. In model inversion attack
[2, 8, 10], the model’s output is used to extract features that characterize
one of the model’s classes. The goal of model extraction and stealing attack
is to steal model parameters and hyperparameters to duplicate or mimic the
functionality of the target model [15, 17]. However, little attention has been
paid to the privacy risks of GNNs. Recently, privacy preserving learning
algorithms for GNN models have been proposed [11, 22]. However. their proposed
solutions are not directly applicable in overcoming the risk incurred by MI
attacks. After our work, a recent paper on node-level membership inference
attack for GNN was proposed [4]. Their work is different from our work in that
we focus on analyzing the properties of GNNs and dataset properties that
determines the differences in their robustness. Moreover, as indicated by the
authors, their proposed defenses limits the target model’s utility whereas our
proposed defenses does not affect model’s utility.

##  III Our Approach

###  III-A Problem Description

####  III-A1 Notations

Let $G=(V,E)$ represents the graph dataset with $|V|$ nodes and $|E|$ edges.
Let the nodes be labeled. We denote by _target graph_ ,
$\mathcal{G}_{t}=(V_{t},E_{t})$, the induced graph on the set of sensitive or
the member nodes $V_{t}$ which is used to train the _target model_ ,
$\mathcal{M}$.

######  Problem Statement.

Let a GNN model $\mathcal{M}$ be trained using the graph
$G_{t}=(V_{t},E_{t})$. Given a node $v$ and its $L$-hop neighborhood,
determine if $v\in V_{t}$. Note that even if $v$ was in the training set, the
$L$-hop neighborhood known to the adversary might not be the same as the one
used to train the model $\mathcal{M}$.

####  III-A2 Our Proposed Settings

We propose two realistic settings for carrying out MI attack on GNNs: (i) in
the first setting which we call the TSTF (train on subgraph, test on full)
setting, in which the whole graph $G$ is available to the adversary but she is
not aware of the subgraph $\mathcal{G}_{t}$ used for training the target
model. This implies that the attacker has access to the links (if any) between
the member nodes and non-member nodes (ii) in our second setting TSTS (train
on subgraph, test on subgraph) setting, the target graph $G_{t}$ is an
isolated component of $G$, i.e., the member and non-member nodes are not
connected. The adversary has access to $G$ but does not know which of its
component is used for training the target model.

Figure 1:  Attack methodology for membership inference on GNN models. The
training nodes and neighbor information used for training the shadow GNN model
are labeled as Member. We also query the shadow model with nodes from a test
graph and labeled the predictions as non-Member. These predictions are used to
train the attack model. The attacker then queries his trained attack model
with posteriors obtained from the target model (target predictions) to infer
membership.

###  III-B Attack Methodology

We model the problem of membership inference as a binary classification task
where the goal is to determine if a given node $v\in V_{t}$. We denote our
attack model by $\mathcal{A}$.

We organize the adversary’s methodology (also shown in Figure 1) into three
phases, shadow model training, attack model training, and membership
inference.

####  III-B1 Shadow model training

To train the shadow model, we assume that the adversary has access to the
graph with vertex set $V_{s}$ that comes from the same underlying distribution
as $V_{t}$ (the assumption which we also relax in Section V-D4). Then the
adversary trains the shadow model using the shadow model’s training split,
$V^{Train}_{s}\subset V_{s}$. To replicate the behavior of the target model,
we use the output class probabilities of the target model (when
$V^{Train}_{s}$ is used as input) as the ground truth for training the shadow
model. This would result in querying the target model for each vertex in
$V^{Train}_{s}$. We later relax the number of queries required to $0$ by
directly training the shadow model on the original ground truth labels of
$V^{Train}_{s}$. We observe there is no significant change in attack success
rate (c.f. Section V-D1). We also find that we do not need to know the exact
target model. In fact, we show that using Gcn as the shadow model,
irrespective of the actual target model already results in good attack
performance (c.f. Section V-D3).

####  III-B2 Attack model training

To construct the attack model, we use the trained shadow model to perform
predictions over all nodes in $V^{Train}_{s}$ and $V^{Out}_{s}=V_{s}\setminus
V^{Train}_{s}$ and obtain the corresponding output class posterior
probabilities. For each node, we take the posteriors as input feature vectors
for the attack model and assigns a label 1 if the node is in $V^{Train}_{s}$
and 0 if the node is from $V^{Out}_{s}$. These assigned labels serve as ground
truth data for the attack model. All the generated feature vectors and labels
are used in training the attack model.

####  III-B3 Membership inference

To perform the inference attack on whether a given node $v\in V_{t}$, the
adversary queries the target model with $v$ and its known neighborhood to
obtain the posteriors. Note that even if $v$ was part of training data, the
adversary would not always have access to the exact neighborhood structure
that was used for training. Then she inputs the posteriors into the attack
model $\mathcal{A}$ to obtain the membership prediction.

##  IV Experiments

We compare four popular GNN models: (i) graph convolution network (Gcn)[7],
(ii) graph attention network (Gat) [16] (iii) simplified graph convolution
(Sgc) [18] and (iv) GraphSage ( Sage) [3] as explained in Section II-A. We ran
all experiments for 10 random data splits (i.e., the target graphs, shadow
graphs as well as test graphs were generated 10 times) and report the average
performance along with the standard deviation.

###  IV-A Dataset and Settings

To conduct our experiments, we used 5 different datasets commonly used as a
benchmark dataset for evaluating GNN performance. The properties of the
datasets are shown in Table I.

TABLE I:  Dataset Statistics. $|V|$ and $|E|$ denote the number of vertices and edges in the corresponding graph dataset. $|V_{t}|$ denotes the number of vertices in the target/shadow (train) graph. $deg$ is the average degree of $|V_{t}|$ calculated for the training graph of target model. The average degree for trainset for shadow model $|V_{s}|$ is approximately the same as for the target model. | Cora | CiteSeer | PubMed | Flickr | Reddit
---|---|---|---|---|---
$|V|$ | 2708 | 3312 | 19,717 | 89,250 | 232,965
$|E|$ | 5429 | 4715 | 44,338 | 449,878 | 57,307,946
# features | 1433 | 3703 | 500 | 500 | 602
# classes | 7 | 6 | 3 | 7 | 41
$|V_{t}|$ | 630 | 600 | 4500 | 10,500 | 20,500
$deg_{TSTS}$ | 1.111 | 0.41 | 1.102 | 1.638 | 70.383
$deg_{TSTF}$ | 3.898 | 2.736 | 4.496 | 10.081 | 491.987

###  IV-B Model Architecture and Training

We used a 2-layer Gcn, Gat, Sgc, and Sage architecture for our target models
and shadow models. The attack model is a 3-layer MLP model. All target and
shadow models are trained such that they achieve comparable performance as
reported by the authors in the literature. We vary the learning rates between
0.001 and 0.0001 depending on the model and dataset.

Evaluation Metrics. We report AUROC scores, Precision, and Recall for the
attack model as done in [14, 13]. For the target GNN models, we report train
and test accuracy. Due to space constraints we show in the main paper
summarized results using mostly the AUROC metric. The detailed results are
shown on our GitHub page 111https://github.com/iyempissy/rebMIGraph.

###  IV-C Research Questions

Here, we summarize the main research questions that we investigate in this
work.

######  RQ 1.

How do different GNN models compare with respect to privacy leakage of
training data? What factors lead to differences in vulnerability of GNN models
towards MI attack? (c.f. Sections V-A and V-B)

######  RQ 2.

How does overfitting influence the performance of MI attacks in GNNs? (c.f.
Section V-C)

######  RQ 3.

How does the number of queries for shadow model training, absence of knowledge
of similar data distribution, target model architecture and hyperparameter
settings affect the attack performance? (c.f. Section V-D)

######  RQ 4.

How could we defend against the blackbox MI attack without compromising the
model performance? (c.f. Section VI)

##  V Analysing the MI Attack on GNNs

###  V-A Overall Attack Performance

In this section, we answer the first part of RQ 1.

(a) TSTF Setting

(b) TSTS Setting

Figure 2: Mean AUROC scores of attack model against different GNN models. All
target models except Sage encountered memory issues for the Reddit in TSTF
setting. Therefore, we only provide results for Reddit in the TSTS setting.

##### TSTF Setting

The AUROC scores for the attack model on all datasets except Reddit are shown
in Figure 2(a). For the models Gcn and Sgc, the attack model obtains similar
scores. Note that the difference between Sgc and Gcn is that Sgc does not use
a non-linear transformation after the feature aggregation step. The feature
aggregation scheme employed in both models is exactly the same.

Gat is the most robust towards the attack. Gat also differs from the models in
that it uses a weighted aggregation mechanism. Sage employs a mean aggregation
over the neighborhood’s features. Unlike the other models, for the aggregation
step, it samples a fixed number of neighbors rather than using the complete
neighborhood. Though it shows similar results for 3 citation networks, the
attack is less successful for the larger graph Flickr (when compared to Gcn
and Gat). We attribute the reason for such an observation to the induced noise
in the neighborhood structures because of the random sampling of neighbors.
Obviously, the effect is more prominent in denser graphs like Flickr as
compared to Cora where the average degree is less than 2.

##### TSTS Setting

Unlike in the TSTF setting, the train and test sets in this setting are
disconnected. This implies that any node $v\in V_{t}$ and its exact
neighborhood used during training is known to the adversary. We also see a
huge reduction in test set performance implying that the model is not
generalizing well to the test set. Intuitively, it would be much easier to
attack in this setting.

The AUROC scores for the corresponding attack are shown in Figure 2(b).
Precision and recall of the attack model along with the train-test set
performance of the target model are provided in Table VI on Github (1). We
observe that for Cora and CiteSeer the attack has a similar success rate as in
TSTF setting, for Flickr on the other hand, the attack performance degrades.
For the larger dataset Reddit, the attack is successful for Gcn and Sgc models
with a mean precision of 0.81 and 0.74 respectively. Gat and Sage shows more
robustness with AUROC scores close to 0.5 (implying that the attack model
cannot distinguish between member and non-member nodes better than a random
guess) for datasets: PubMed, Flickr, Reddit.

###  V-B Effect of Model and Dataset Properties

To answer the second part of RQ 1, we analyse the differences in the
aggregation operation of models and three dataset properties to explain the
differences in attack performance.

####  V-B1 Which model is more robust towards MI attack and Why?

To summarize the above results, we found Gat to be most robust towards
membership inference attacks. The reason can be attributed to the learnable
attention weights for different edges. The above fact implies that instead of
the original graph model, a distorted one dictated by supervised signals of
class labels is embedded in the model. This is in contrast with Sgc and Gcn
where the actual graph is embedded with equal edge weights. Also, in Sage,
which uses neighborhood sampling before the aggregation operation, does not
use the complete information of the graph during training. The effect is more
prominent in denser graphs in which only a small fraction of the neighborhood
is used during a training epoch.

Another interesting observation is the attack behavior changes with datasets.
While Gat is overall less vulnerable than other models, the percentage drop in
attack performance (as compared to, for example, Gcn) for Flickr (32%) is much
larger than for Cora (9%).

####  V-B2 How do dataset properties affect attack performance?

To investigate the differences in the behavior of the attack model on
different datasets we consider three properties of the datasets (i) _average
degree_ which influences the graph structure and the effect of aggregation
function of the GNN (ii) the _number of input features_ that influence the
number of model parameters and (iii) the _number of classes_ that decides the
input dimension/features for the attack model.

First, note that for very low average degree graphs the effect of aggregation
operation is highly decreased as there would be very few or no neighbors to
aggregate over. From Table I, we observe that CiteSeer has the lowest average
degree (both in the TSTF and TSTS settings) leading to similar attack
vulnerability of all GNN models. Reddit, on the other hand, with the highest
average degree exhibits a high vulnerability to the attack when Gcn and Sgc
are the target models whereas fpr Gat and Sage attack performance drastically
reduces owing to reasons discussed in the last section. Similar observations
can be made for Flickr which has the second-highest average degree.
Differences in attack performance for Flickr are smaller as compared to
Reddit. This is expected as Reddit has an average degree which is around 50
times the average degree of Flickr for TSTF setting and around 70 times for
TSTS setting.

Second, for the three datasets Cora, CiteSeer, and PubMed, which exhibit
similar average degrees, attack performance is highest for CiteSeer followed
by Cora. The trend stays the same for different target models. The same
pattern is also observed in the number of input features. While CiteSeer has
the highest number of features, PubMed has the least. Note that the number of
input features leads to an increase in the number of parameters (the number of
parameters corresponding to the first hidden layer will be $p\times h$ where
$p$ is the number of input features and $h$ the hidden layer dimension). The
higher number of parameters, in turn, leads to better memorization by models,
which explains the above-observed trend in low average degree datasets.

Third, we recall that the output posterior vector is the input feature vector
for the attack model. As the dimension of the posterior vector is equal to the
number of classes, more information is revealed for datasets with larger
number of classes. The low attack performance on PubMed can be therefore
additionally attributed to its lowest number of classes.

####  V-B3 Effect of Neighborhood Sampling in Sage

We attribute the differences in Sage’s robustness towards attacks on different
datasets to its neighborhood sampling strategy. Recall that rather than using
complete neighborhood in the aggregation step, Sage samples a fixed number of
neighbors at each layer. SAGE also utilizes a mini-batching technique that
contains nodes on which representation needs to be generated and their sampled
neighbors. To showcase the effect of the neighborhood sampling, we varied the
number of neighbors sampled at different layers of the network and the batch
size.

We used [25,10] and [5,5] as sampled neighborhood sizes in layers 1 and 2. As
shown in Figure 3(a), the attack AUROC decreases as the number of sampled
nodes decreases. This is because the model uses the noisy neighborhood
information and it is not able to fully encode the graph structure in the
model, this, in turn, makes the posteriors of neighboring nodes less
correlated. Similar results are obtained for a larger dataset, Flickr (shown
in Figure 3(b)).

(a) Cora

(b) Flickr

Figure 3:  Effect of training batch size and sampled neighbors on attack
performance for Sage model on (a) Cora and (b) Flickr dataset.

####  V-B4 Effect of Instance Connectivity

Here, we present a qualitative analysis of the differences in the robustness
of different models to MI attack using Flickr as an example dataset in the
TSTF setting. Recall that given the predicted posteriors as input, the attack
model labels the node instance as a member (label 1) or non-member (label 0)
node. To understand the pattern of label assignments by the attack model we
need the following definition.

###### Definition 1 (Homophily).

For any node $u$ which is either a member or non-member, we define its
homophily as the fraction of its one-hop neighbors which has the same
membership label as $u$. The neighborhood of any node is computed using the
graph available to the adversary. We call homophily with respect to ground
truth as the true homophily and with respect to the attack model predictions
as the predicted homophily.

Therefore, true homophily of $1$ means $u$, and all its neighbors in the graph
used by the adversary have the same membership label. Similarly, predicted
homophily of $1$ implies that $u$ and its neighbors were assigned the same
membership label by the attack model. In Figure 4, we visualize the
differences in attack behavior for different models on the Flickr dataset by
plotting the joint distribution of true and predicted homophily of the
correctly (orange contour lines) and incorrectly (blue contour lines)
predicted nodes. We chose Flickr here because the attack performance varies
the most with respect to different target models as also discussed in the last
sections.

Figure 4: Joint density plot of true and predicted homophily (refer to
Definition 1) on Flickr dataset.

We observe more dense regions in the upper half of the plots for all the
models. Noting the fact that these highly concentrated regions correspond to
high predicted homophily, we conclude that the attack model’s predictions on a
node are highly correlated with its predictions on its neighbors. As the
attack model is agnostic to the graph structure, this further implies that the
posterior of neighboring nodes are also correlated, which the attack model can
exploit.

The differences in the behavior of different models are also well illustrated.
Note that the higher the density of orange regions on diagonals (see for Gcn
and Sgc), the more accurate the attack model will be. In contrast to Gcn, the
attack model is confused for Gat and assigned the wrong label to corresponding
nodes and their neighbors (see blue regions corresponding to high predicted
homophily). For Sage, even though there are more orange regions, these do not
lie over the diagonal. This means that the attack model, even if it predicts
the right membership label for a member node, it also predicts the same
membership label for its non-member neighbors. Hence, including them
incorrectly in the member set. To summarize, for Gat the attack results in
more false negatives whereas for Sage there are more false positives. Both
scenarios render the attack less useful to the adversary.

###  V-C Effect of Model Overfitting

To investigate the effect of overfitting (RQ 2), we train the models such that
they achieve zero training loss or high generalization error. The train and
test accuracy as well as the attack precision and recall are shown in Table
II.

TABLE II:  Performance of GNN models and the attack model on Flickr dataset in case of overfitting. |  Target Model |  | Attack Model
---|---|---|---
| Train | Test |  | Precision | Recall
Gcn | $0.70\pm 0.01$ | $0.13\pm 0.01$ |  | $0.63\pm 0.01$ | $0.70\pm 0.04$
Gat | $0.61\pm 0.07$ | $0.50\pm 0.21$ |  | $0.75\pm 0.05$ | $0.69\pm 0.03$
Sgc | $0.75\pm 0.02$ | $0.20\pm 0.03$ |  | $0.62\pm 0.04$ | $0.59\pm 0.09$
Sage | $0.90\pm 0.03$ | $0.24\pm 0.03$ |  | $0.57\pm 0.08$ | $0.50\pm 0.01$

(a) Influence of overfitting on the attack on Flickr. N= Normal and O=Overfit.
"Normal" refers to the case when all models were trained for a fixed number of
epochs.

(b) % of nodes for which the maximum posterior is greater than 0.8 for
overfitted GNN models. The statistics are shown for one random data split.

Figure 5: Effect of overfitting. In figure (a) we observe a surprising effect
that attack is less successful for overfitted models. The reason behind such
an effect is explained in (b) which illustrates that the overfitted model also
makes extremely confident albeit incorrect predictions on the test (unseen)
set.

Figure 5(a) shows the comparison between a "normal" model and the overfitted
model. The attack precision and recall of the overfitted model consistently
decreases across all models except for GAT. This implies that overfitting
alone might not always be a contributing factor to membership inference attack
and that overfitted model may not always encode the information needed to
launch an MI attack.

To understand the reasons behind the above observations, we investigate the
posterior distribution of member and non-member nodes. In Figure 5(b), we show
the distribution of the maximum posterior (i.e., the posterior probability
corresponding to the predicted class) of overfitted models on the members and
non-members. We observe that in the case of overfitting, the GNN model not
only makes highly confident predictions for the member nodes but also for the
non-members. Most of the nodes whether member or non-member obtain the maximum
class probability (or posterior) greater than $0.8$ for models Gcn and Sgc.
For Gat and Sage, the attack model obtains higher precision given that a
relatively less number of non-member nodes obtain a high maximum posterior.
Moreover, from the test set performance in Table II, we observe that Sage
generalizes better than Gat which also reflects in lower attack precision in
Sage.

###  V-D Sensitivity Analysis of Attack

We answer RQ3 by performing the sensitivity analysis of the attack with
respect to the number of queries (Section V-D1), different sizes of hidden
layers (Section V-D2) and relaxation of model architecture and data
distribution assumptions (Section V-D3 and V-D4).

####  V-D1 Attack with reduced number of queries

We relax the number of queries required to imitate a target model to $0$ by
assuming that the adversary has access to the dataset from a similar
distribution as the dataset used for the target model. To construct such
datasets we randomly sampled disjoint sets of nodes from the full graph for
the target as well as the shadow model. We then construct the corresponding
induced graphs on the node sets to train the shadow and target models. Note
that the shadow model data, in this case, will not be exactly from the same
distribution as the target graph since our construction would not exactly
preserve the structural characteristics of these graphs e.g. degree
distribution. The data used in training the shadow model is in fact, similar
but not from the same distribution as the target model. We found that training
the shadow model using ground truth labels performs similarly to querying the
target model in the order of $\pm 0.02$ standard deviation.

####  V-D2 Attack performance without knowledge of exact hyperparameters

In this section, we relax the assumption that the attacker knows the exact
hyperparameters used in the target model by varying the number of hidden
neurons of the shadow model. We experiment with three values
$\\{256,128,64\\}$.

The corresponding mean AUROC scores are plotted in Figure 7 on Github (1) due
to space constraint. A general trend is that the larger the hidden layer size,
the better the attack performance. This is expected as an increase in the size
of the hidden layer increases the model parameters/capacity to store more
specific details about the training set. Therefore, though we observe some
reduction in attack performance for PubMed when using 128 or 64 as hidden
layer size, an attacker can just choose the hyperparameter which gives the
best train set performance on its shadow dataset.

####  V-D3 Attack without the knowledge of target model’s architecture

We further relax the assumption that the attacker knows the architecture of
the target model. Specifically, we used Sgc as the shadow model and other GNN
models as the target model. As the Sgc model is obtained from the Gcn model by
removing the non-linear activation function from Gcn, we aim to quantify how
this difference affects the attack performance. Therefore, we also used Gcn as
a shadow model. The mean AUROC scores corresponding to attacks for different
datasets are presented in Figure 8 in our Github page (1).

In both TSTF and TSTS, on the CiteSeer and Cora dataset, the performance of
using different shadow models is equivalent to using the same model as the
target model except for Sage where a significant drop in performance is
observed. However, Gcn performs significantly better than Sgc when used as the
shadow model by the attacker. On the PubMed dataset, an interesting
observation, particularly for Gat is that when Sgc is used for the shadow
model, the attack precision and recall increases more than when Gat (target
model) is used as the shadow model. On the Flickr and Reddit datasets, using
Gcn as the shadow model performs comparably to an adversary knowing the
architecture of the target model in both TSTS and TSTF settings. However,
using Sgc as a shadow model significantly led to reduced attack precision in
the TSTF setting. Better attack precision is achieved when Gcn is used as the
shadow model and Sage is used as the target model on large networks like
Reddit. Therefore, we conclude that using GCN as the shadow model is
sufficient to launch a successful attack and that the removed non-linear
activation function of Sgc makes it a less attractive option to use as a
"universal" shadow model.

####  V-D4 Attack using different data distribution (Data transferring attack)

We relax the assumption that the attacker trains her shadow model based on
data coming from similar distribution as that used by the target model.
Specifically, we used Cora as the data for training the target model and
CiteSeer as the data used by the attacker for training her shadow model. In
here, the goal of the attack model is to understand membership status based on
the posterior distribution. To cater for the discrepancies in the length of
the posterior vectors of these two datasets, we select the top $n$ coordinates
of the posterior vector and arrange them in ascending order.

As shown in Table III, we observe that relaxing the knowledge of the dataset
distribution does not affect the attack precision. Surprisingly, some gains
are observed on GCN and GAT. However, the recall drops by $13\%$ on GCN,
$16\%$ on GAT and SGC while the recall on SAGE remains the same. This implies
that the assumption of the attacker drawing the shadow dataset from the same
distribution as the target model can be relaxed with minimal loss in attack
performance.

TABLE III: Attack precision and recall when Cora is used as the target and CiteSeer as the shadow dataset. The % change with respect to original performance is shown in the brackets. | Gcn | Gat | Sgc | Sage
---|---|---|---|---
Precision | 0.766 (+1%) | 0.723 (+8%) | 0.780 (-2%) | 0.798 (-2%)
Recall | 0.653 (-13%) | 0.552 (-16%) | 0.663 (-16%) | 0.792 (0%)

##  VI Defense mechanisms

To defend against the current black box attack based on posteriors (RQ 4), we
note that the defense mechanism should possess the following properties.
_First,_ given access to only posteriors, the defense should lend
indistinguishability among member and non-member nodes without compromising
task performance and target model’s utility. _Second,_ the defense should be
oblivious to the attacker. The second property is important for output
perturbation-based defense mechanisms such that the added noise cannot be
inferred from the released information.

Based on the insights gained from our experimental analysis of attack
performance for different GNN models and datasets we propose two defense
mechanisms : (i) _query neighborhood sampling defense_ (NsD) and (ii)
_Laplacian binned posterior perturbation_ (LbP) which we describe in the
following sections.

##### Laplacian binned posterior perturbation (LbP) defense

Here, we propose an output perturbation method by adding noise to the
posterior before it is released to the user. A simple strategy would be to add
Laplacian noise of an appropriate scale directly to each element of the
posterior. We refer to this strategy as VanPd. Note that the noise level
increases with the number of classes which can have an adverse effect on model
performance.

To reduce the amount of noise needed to distort the posteriors, we propose a
binned posterior perturbation defense. We first randomly shuffle the
posteriors and then assign each posterior to a partition/bin. The total number
of bins, $\psi$, is predefined and depends on the number of classes. For each
bin, we sample noise at scale $\beta$ from the Laplace distribution (LbP). The
sampled noise is added to each element of the bin. After the completion of the
noise addition operation to each bin, we restore the initial positions of the
noisy posterior y* before binning. Then we release y*.

We observe in our experiments that it leads to a drop in attack performance
without substantially compromising model performance on the node
classification task. We set the reference values for $\beta$ as {5, 2, 0.8,
0.5, 0.3, 0.1}. The higher the value of $\beta$, the higher the added noise.
We set $\psi$ as {2, 3, 4} where for example, $\psi=2$ implies that the
posterior vector is divided into $2$ groups and the same noise added to all
members of the same group.

##### Query neighborhood sampling defense (NsD)

Exploiting the observation that a node and its neighbors are classified alike
by the attack model (homophily property), we propose a query neighborhood
sampling (NsD) defense mechanism to distort the similarity pattern between the
posterior of the node and that of its neighbors. Specifically, when a target
model is queried with the node and its $L$-hop neighborhood, the defender
removes all its first-hop neighbors except $k$ randomly chosen neighbors (Note
that no change is made to the trained model.). The neighborhood of the $k$
sampled neighbors stays intact and is not changed. By doing so, NsD limits the
amount of information used to query the target model. We set the reference
values for $k$ as follows {0, 1, 2, 3} which implies sampling no neighbors,
$1,2,\text{ or }3$ neighbors respectively.

###  VI-A Evaluating Defenses

We measure the effectiveness of a defense by the drop in attack performance
after the defense mechanism is applied. To further incorporate the two desired
properties of the defense into our evaluation we employ the following utility
measures [6].

#####  Label loss ($\mathcal{L}$)

The label loss measures the fraction of nodes in the evaluation dataset whose
label predictions are altered by the defense. For a given query $i$, if the
highest coordinate of the true posterior and that of the perturbed or
distorted posterior is the same, then the $\mathcal{L}_{i}$ is $0$, otherwise,
it is $1$. The total label loss is quantified as:
$\mathcal{L}=\nicefrac{{\sum\limits_{i=1}^{|Q|}\mathcal{L}_{i}}}{{|Q|}},$
where $|Q|$ is the number of user queries. A $\mathcal{L}$ close to $0$ is
desirable whereas $\mathcal{L}$ close to $1$ indicates that the defense
mechanism is relatively bad since it alters the label prediction which
directly affects the test accuracy of the target model.

#####  Confidence score distortion ($\mathcal{C}$)

For a given query $i$, we measure the confidence score distortion,
$\mathcal{C}_{i}$ by the distance between the true posterior and the distorted
posterior due to the defense mechanism. We use Jensen Shannon Distance (JSD)
as the distance metric. JSD extends Kullback–Leibler divergence (relative
entropy) to compute symmetrical score or similarity between two probability
distributions. The total confidence score distortion is given as:
$\mathcal{C}=\nicefrac{{\sum\limits_{i=1}^{|Q|}\mathcal{C}_{i}}}{{|Q|}}$ where
$\mathcal{C}_{i}=JSD(\textbf{y},\textbf{y*})$ for a given query $i\in Q$.
Ideally, $0$ indicates that both the perturbed posteriors and the true
posteriors are the same and $1$ indicates that they are highly dissimilar.

Setup. We compare the drop in attack precision with respect to label loss
($\mathcal{L}$) and confidence distortion ($\mathcal{C}$). For each defense
and a given value of each parameter ($\beta,\psi\text{ or }k$), we plot the
pairs $\\{\mathbb{P},\mathcal{L}\\}\text{ and }\\{\mathbb{P},\mathcal{C}\\}$
where $\mathbb{P}$ is the attack precision. We use the attacker’s AUROC as a
representative metric but observe a similar trend on the other attack
inference performance metrics (precision and recall). We performed our
experiments on Gcn since it is the most vulnerable GNN model across all
datasets as observed in Section V-A and V-D3.

###  VI-B Results

TABLE IV: Attack precision, recall and AUROC (lower the better) corresponding to different label loss $\mathcal{L}$. – indicates that the defense mechanism does not incur the corresponding label loss.  |  | VanPd | LbP | NsD
---|---|---|---|---
| $\mathcal{L}$ | Prec | Rec | AUC | Prec | Rec | AUC | Prec | Rec | AUC
Cora | 0 | 0.814 | 0.811 | 0.813 | 0.777 | 0.772 | 0.750 | 0.800 | 0.699 | 0.700
0.1 | 0.782 | 0.778 | 0.800 | 0.721 | 0.717 | 0.705 | 0.774 | 0.686 | 0.691
0.3 | 0.678 | 0.673 | 0.658 | 0.616 | 0.608 | 0.631 | – | – | –
CiteSeer | 0 | 0.880 | 0.887 | 0.880 | 0.87 | 0.859 | 0.846 | 0.810 | 0.791 | 0.795
0.1 | 0.846 | 0.830 | 0.852 | 0.691 | 0.683 | 0.700 | 0.778 | 0.766 | 0.758
0.3 | 0.747 | 0.731 | 0.735 | 0.620 | 0.606 | 0.617 | – | – | –
PubMed | 0 | 0.642 | 0.633 | 0.681 | 0.592 | 0.58 | 0.66 | 0.533 | 0.521 | 0.568
0.1 | 0.564 | 0.548 | 0.653 | 0.570 | 0.554 | 0.556 | 0.519 | 0.509 | 0.537
0.3 | 0.523 | 0.508 | 0.600 | 0.347 | 0.503 | 0.542 | – | – | –
Flickr | 0 | 0.810 | 0.775 | 0.820 | 0.568 | 0.665 | 0.745 | 0.302 | 0.500 | 0.500
0.1 | 0.685 | 0.541 | 0.785 | 0.541 | 0.514 | 0.680 | – | – | –
0.3 | 0.571 | 0.505 | 0.655 | 0.484 | 0.645 | 0.649 | – | – | –
Reddit | 0 | 0.747 | 0.825 | 0.830 | 0.730 | 0.801 | 0.814 | 0.176 | 0.500 | 0.500
0.1 | 0.574 | 0.533 | 0.655 | 0.521 | 0.524 | 0.620 | – | – | –
0.3 | 0.527 | 0.518 | 0.632 | 0.227 | 0.384 | 0.500 | – | – | –

In Figure 6, we plot the attack AUROC (after the defense is applied) together
with label loss and confidence distortion. In the following, we analyze the
results for different datasets when the three different defense mechanisms
were applied. Table IV further provides the attack precision, recall and AUROC
scores (after defense mechanism has been applied) and the corresponding label
loss. All results corresponds to attacks in TSTF setting except for Reddit in
the TSTS setting.

#####  Cora

Recall that Cora is a sparse graph (with average degree 3.89 in TSTF setting)
with $7$ classes. Because of high sparsity, we do not benefit much by NsD
defense which perturbs the input neighborhood of query node. Nevertheless, it
achieves a drop of $15\%$ in attack’s performance with a negligible label loss
and confidence distortion (see Figure 6(a)). LbP and VanPd which directly
perturbs the posteriors, achieves larger drops in attack performance though at
the expense of higher label loss and confidence distortion. Nevertheless, for
the same label loss, LbP achieves a better drop in attack performance. For
instance, LbP achieves a maximum drop of $24\%$ at label loss of $0.3$ whereas
for VanPd, the drop in attack precision is only $17\%$ at the same label loss.
At $0.1$ label loss, LbP achieves a $12\%$ (thrice the percentage drop in
attacker’s inference than VanPd and NsD at $0.1$ label loss).

#####  CiteSeer

For the CiteSeer dataset (Figure 6(b)), the drop in attacker’s inference for
LbP at label loss of $0.3$ and $0.1$ is 30% and 22% respectively which is two
times (16%) and four times (5%) better than VanPd at the same label loss. At
$0.1$ label loss, NsD achieves $12\%$ drop in attacker’s performance. However,
at a $0$ label loss, NsD still achieves $9\%$ drop in attacker’s performance
while VanPd and LbP only have $1\%$ and $2\%$ drops respectively.

#####  PubMed

On the PubMed dataset, we observe a further reduction in the attacker’s
inference with VanPd achieving $25\%$ and LbP achieving $50\%$ at label loss
of $0.3$. NsD does not incur any label loss above $0.1$. Hence, at a lower
label loss of $0.1$, VanPd and LbP perform similarly. One possible explanation
is that PubMed only has three classes. Therefore, the maximum number of bins
is restricted to $2$ which does not lead to any specific advantage for LbP as
compared to VanPd. On the contrary, NsD performs well with a $26\%$ and $24\%$
drop in attacker’s inference at a label loss of $0.1$ and $0$ respectively
making the attacker’s performance largely incorrectly classifies member nodes
as non-members. (Figure 6(c)).

#####  Flickr

As in the previous analysis on other datasets, LbP outperforms VanPd by about
over $15\%$ at label loss of $0.3$. It is notable that NsD that samples the
neighborhood of the query performs significantly better than LbP with a drop
in inference performance of $65\%$ at a perfect label loss of $0$. This
significant drop explains the intriguing observation that the predictions of a
node follow that of its neighbors (Section V-B4). Therefore, when the
neighbors of a node are distorted by the query sampling mechanism, the
posterior is equally affected, causing the attack model to misclassify member
and non-member nodes.

#####  Reddit

Similar to Flickr, at label loss $0$, we observe an $80\%$ drop for NsD,
$17\%$ for LbP, and $15\%$ drop for VanPd. We note that a similar drop in
attacker’s inference that LbP will achieve at $0.3$ label loss, NsD will
achieve the same drop at a perfect $0$ label loss (observed at $k=2$). The
observations also follow that of Flickr because of the high node degree of the
Reddit dataset.

Summary. We observe that VanPd leads to a degradation in the test performance
of the target model as well as the attack performance. Although this
significantly defends against MI attack, it is at the expense of the test
accuracy of the target model. Binning as in LbP provides a viable strategy to
reduce the amount of added noise without compromising defense. We observe that
our LbP defense is well suited for graphs with a low degree. For LbP, setting
$\psi=2$ led to a good balance between privacy and limiting label loss. We
remark that both LbP and VanPd are evaluated on the same noise scale.

On all datasets, NsD achieves the lowest label loss. We attribute the
observation of different defenses to the degree of each graph. Specifically,
Cora, CiteSeer, and PubMed have low degrees, therefore, the NsD does not
significantly reduce the attacker’s inference. However, on large datasets such
as Flickr and Reddit which have higher degrees, the attacker’s inference
reduces to a random guess (with AUC score of 0.5) with a perfect $0$-label
loss. With respect to the choice of $k$, we observed that the smaller the
value of $k$, the better the defense. For the current datasets, we observed
that for $k>3$, there was not much degradation in attack performance.

Comparison based on confidence score distortion.
The lower the $\mathcal{C}$, the more difficult it is for an attacker to
detect whether the model has undergone any defense. Moreover, a lower
confidence distortion is required for applications where the target’s model
output posterior is used rather than just the predicted class. As shown in
Figure 6, VanPd leads to very high confidence distortion as compared to other
defenses. For instance, VanPd, LbP, and NsD achieves $0.70$, $0.40$ and $0.10$
confidence score distortion respectively on Cora dataset corresponding to the
reduction in attack precision by $15\%$, $15\%$ and $12\%$. On the larger
dataset Reddit, VanPd, LbP, and NsD achieves $0.82$, $0.60$ and $0.05$
confidence score distortion corresponding to $30\%$, $30\%$ and $63\%$
reduction in attack precision. Our result shows that NsD achieves the lowest
confidence score distortion leading to an oblivious defense and the
preservation of target model’s utility.

(a) Cora

(b) CiteSeer

(c) PubMed

(d) Flickr

(e) Reddit

Figure 6:  Comparison of defense mechanisms using label loss ($\mathcal{L}$)
and confidence score distortion ($\mathcal{C}$) metric. The red dashed line
corresponds to the attack AUROC when no defense mechanism was applied. We
observe a similar trend for Precision and Recall. Table IV shows the
performance on all metric at specific $\mathcal{L}$.

##  VII Conclusion

We compare the vulnerability of GNN models to membership inference attacks. We
further show that the observed differences in vulnerability is caused by
differences in various model and dataset properties. We show that the simplest
binary classifier-based attack model already suffices to launch an attack on
GNN models even if they generalize well. We carried out experiments on five
popular datasets in two realistic settings. To prevent MI attacks on GNN, we
propose two effective defenses based on output perturbation and query
neighborhood sampling that significantly decrease the attacker’s inference
without substantially compromising the target model’s performance.

Acknowledgements. This work is in part funded by the Lower Saxony Ministry of
Science and Culture under grant number ZN3491 within the Lower Saxony "Vorab"
of the Volkswagen Foundation and supported by the Center for Digital
Innovations (ZDIN), and the Federal Ministry of Education and Research (BMBF)
under LeibnizKILabor (grant number 01DD20003).

## References

  * [1] N. Carlini, C. Liu, Ú. Erlingsson, J. Kos, and D. Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In 28th $\\{$USENIX$\\}$ Security Symposium, 2019.
  * [2] M. Fredrikson, S. Jha, and T. Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1322–1333, 2015.
  * [3] W. L. Hamilton, R. Ying, and J. Leskovec.  Inductive representation learning on large graphs.  In NIPS, 2017.
  * [4] X. He, R. Wen, Y. Wu, M. Backes, Y. Shen, and Y. Zhang.  Node-level membership inference attacks against graph neural networks.  arXiv preprint arXiv:2102.05429, 2021.
  * [5] B. Jayaraman and D. Evans.  Evaluating differentially private machine learning in practice.  In 28th $\\{$USENIX$\\}$ Security Symposium, 2019.
  * [6] J. Jia, A. Salem, M. Backes, Y. Zhang, and N. Z. Gong.  Memguard: Defending against black-box membership inference attacks via adversarial examples.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019.
  * [7] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * [8] L. Melis, C. Song, E. De Cristofaro, and V. Shmatikov.  Exploiting unintended feature leakage in collaborative learning.  In 2019 IEEE Symposium on Security and Privacy (SP), 2019.
  * [9] M. Nasr, R. Shokri, and A. Houmansadr.  Machine learning with membership privacy using adversarial regularization.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018.
  * [10] N. Papernot, P. McDaniel, A. Sinha, and M. Wellman.  Towards the science of security and privacy in machine learning.  arXiv preprint arXiv:1611.03814, 2016.
  * [11] S. Sajadmanesh and D. Gatica-Perez.  When differential privacy meets graph neural networks.  arXiv preprint arXiv:2006.05535, 2020.
  * [12] A. Salem, A. Bhattacharya, M. Backes, M. Fritz, and Y. Zhang.  Updates-leak: Data set inference and reconstruction attacks in online learning.  In USENIX, pages 1291–1308, 2020.
  * [13] A. Salem, Y. Zhang, M. Humbert, P. Berrang, M. Fritz, and M. Backes.  Ml-leaks: Model and data independent membership inference attacks and defenses on machine learning models.  arXiv preprint arXiv:1806.01246, 2018.
  * [14] R. Shokri, S. Marco, S. Congzheng, and S. Vitaly.  Membership inference attacks against machine learning models.  In IEEE Symposium on Security and Privacy (SP), 2017.
  * [15] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart.  Stealing machine learning models via prediction apis.  USENIX Association, 2016.
  * [16] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph Attention Networks.  ICLR, 2018.
  * [17] B. Wang and N. Z. Gong.  Stealing hyperparameters in machine learning.  In 2018 IEEE Symposium on Security and Privacy (SP), 2018.
  * [18] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger.  Simplifying graph convolutional networks.  In Proceedings of the 36th International Conference on Machine Learning, pages 6861–6871. PMLR, 2019.
  * [19] S. Yeom, I. Giacomelli, M. Fredrikson, and S. Jha.  Privacy risk in machine learning: Analyzing the connection to overfitting.  In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), 2018.
  * [20] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  arXiv preprint arXiv:1611.03530, 2016.
  * [21] B. Z. H. Zhao, H. J. Asghar, R. Bhaskar, and M. A. Kaafar.  On inferring training data attributes in machine learning models.  arXiv preprint arXiv:1908.10558, 2019.
  * [22] J. Zhou, C. Chen, L. Zheng, X. Zheng, B. Wu, Z. Liu, and L. Wang.  Privacy-preserving graph neural network for node classification.  arXiv:2005.11903, 2020.


# When lattice cubes meet affine subspaces:
a short note

Nguyễn Lê Thành Dũng
LIPN, CNRS & Université Paris 13
<EMAIL_ADDRESS>
In this note, we give simple proofs of what seem to be folklore results:

######  Theorem 1.

Let $S\subseteq\mathbb{R}^{d}$ ($d\in\mathbb{N}$) be an affine subspace and
$n\in\mathbb{N}$. The intersection of $S$ with the $d$-dimensional lattice
cube of side length $n$ – that is, $S\cap\\{0,\ldots,n-1\\}^{d}$ – has
cardinality at most $n^{\dim S}$.

######  Corollary 2.

The minimum number of $k$-dimensional affine subspaces of $\mathbb{R}^{d}$
necessary to cover the lattice cube $\\{0,\ldots,n-1\\}^{d}$ is $n^{d-k}$.

The proof of Theorem 1 is essentially an undergraduate-level linear algebra
exercise. That said, it is not immediately obvious.

## Context

The analogous question to Corollary 2 for _linear_ subspaces (a.k.a. vector
subspaces) is raised as an open problem in the book [BMP05] (to be precise,
Problem 6 in Section 10.2). At the time of writing, the state of the art on
this problem is the recent paper [BCV19].

Although both [BMP05, BCV19] contain many references to papers on related
problems, we have not managed to find a proof for the affine case in the
literature. Presumably it has been deemed too trivial by the authors of
[BMP05] to deserve inclusion, since they merely write “Covering by linear
subspaces instead of affine ones is more difficult”. We suspect that a proof
might have been written in [Tal97], but that paper does not seem to be
accessible on the Internet.

The motivation for writing this note arose because of some recent research by
N. K. Blanchard and S. Kachanovich [BK19] making use of (a weaker bound than)
Theorem 1.

## Proofs

_Notations:_ We write $(e_{1},\ldots,e_{d})$ for the canonical basis of
$\mathbb{R}^{d}$. We denote the lattice cube by
$C(n,d)=\\{0,\ldots,n-1\\}^{d}$.

###### Proof of Corollary 2 from Theorem 1.

Let $S_{1},\ldots,S_{m}$ be $k$-dimensional affine subspaces covering
$C(n,d)$. The theorem gives us $\mathrm{Card}(S_{i}\cap C(n,d))\leq n^{k}$. By
summing over $i=1,\ldots,m$, we get $n^{d}=\mathrm{Card}(C(n,d))\leq mn^{k}$,
hence $n^{d-k}\leq m$. Conversely, the bound can be reached by the naive
covering which uses the subspaces
$(\mathbb{R}e_{1}\oplus\ldots\oplus\mathbb{R}e_{k})+a_{k+1}e_{k+1}+\ldots+a_{d}e_{d}$
for each of the $n^{d-k}$ choices
$(a_{k+1},\ldots,a_{d})\in\\{0,\ldots,n-1\\}^{d-k}$. ∎

###### Proof of Theorem 1.

Let $k=\dim S$ ($0\leq k\leq d$). Let $D$ be the _direction_ of $S$ (i.e. the
unique linear subspace of $\mathbb{R}^{d}$ that can be obtained by translating
$S$). Let us choose any linear map $p:\mathbb{R}^{d}\to E$ (for some vector
space $E$) such that $\mathrm{Ker}(p)=D$, e.g. the projection onto the
orthogonal complement of $D$.

Since the image of a spanning set by a linear map spans its range, the set
$\\{p(e_{1}),\ldots,p(e_{d})\\}$ spans $\mathrm{Im}(p)$. Therefore, it can be
reduced to a basis of $\mathrm{Im}(p)$, which we may take without loss of
generality to be $p(e_{1}),\ldots,p(e_{d-k})$ (the number of vectors in this
basis is indeed $\dim(\mathrm{Im}(p))=\dim(\mathbb{R}^{d})-\dim(D)=d-k$ by the
rank-nullity theorem).

Now, this means that $p$ induces a linear isomorphism from
$\mathbb{R}e_{1}\oplus\ldots\oplus\mathbb{R}e_{d-k}$ to $\mathrm{Im}(p)$,
since it maps a basis of the former to a basis of the latter. In particular,
$p$ is injective when restricted to
$B=\\{x_{1}e_{1}+\ldots+x_{d-k}e_{d-k}|x_{i}\in\\{0,\ldots,n-1\\}\\}=C(n,d)\cap(\mathbb{R}e_{1}\oplus\ldots\oplus\mathbb{R}e_{d-k})$.

Let $v\in\mathbb{R}^{d}$. By linearity, $p$ is also injective on any $B+v$.
This entails that $\mathrm{Card}((B+v)\cap S)=\mathrm{Card}(p((B+v)\cap
S))\leq\mathrm{Card}(p(S))$. And since $D=\mathrm{Ker}(p)$, $p(D)=\\{0\\}$ so
$p(S)$ is a singleton (again by linearity, since $S=D+u$ for any $u\in S$).
Putting this together, $(B+v)\cap S$ is either empty or a singleton.

To conclude, observe that $C(n,d)$ is the union of
$B+a_{1}e_{d-k+1}+\ldots+a_{k}e_{d}$ for $a_{i}\in\\{0,\ldots,n-1\\}$. Since
the intersection of each of these $n^{k}$ sets with $S$ has at most one point,
we obtain the desired bound. ∎

## References

  * [BCV19] Martin Balko, Josef Cibulka, and Pavel Valtr.  Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences.  Discrete & Computational Geometry, 61(2):325–354, 2019.
  * [BK19] Nikola K. Blanchard and Siargey Kachanovich.  Counting authorised paths in constrained control-flow graphs.  In 5th Bordeaux Graph Workshop, 2019.
  * [BMP05] Peter Brass, William O. J. Moser, and János Pach.  Research Problems in Discrete Geometry.  Springer, 2005.
  * [Tal97] I. Talata.  Covering the lattice points of a convex body with affine subspaces.  Bolyai Soc. Math. Stud., 6:429–440, 1997.


# Towards End-to-End Private Automatic Speaker Recognition

###### Abstract

The development of privacy-preserving automatic speaker verification systems
has been the focus of a number of studies with the intent of allowing users to
authenticate themselves without risking the privacy of their voice. However,
current privacy-preserving methods assume that the template voice
representations (or speaker embeddings) used for authentication are extracted
locally by the user. This poses two important issues: first, knowledge of the
speaker embedding extraction model may create security and robustness
liabilities for the authentication system, as this knowledge might help
attackers in crafting adversarial examples able to mislead the system; second,
from the point of view of a service provider the speaker embedding extraction
model is arguably one of the most valuable components in the system and, as
such, disclosing it would be highly undesirable. In this work, we show how
speaker embeddings can be extracted while keeping both the speaker’s voice and
the service provider’s model private, using Secure Multiparty Computation.
Further, we show that it is possible to obtain reasonable trade-offs between
security and computational cost. This work is complementary to those showing
how authentication may be performed privately, and thus can be considered as
another step towards fully private automatic speaker recognition.

Index Terms: privacy, speaker recognition, secure multiparty computation

##  1 Introduction

Recent years have seen an increase in the number of online services and
applications that use speech as a means for authentication and interaction.
Among other speech technologies, voice-based authentication systems – or
Automatic Speaker Verification (ASV) systems – are becoming more and more a
part of our everyday lives. The uniqueness and ubiquitous nature of speech
make its use a straightforward manner to protect and grant access to both
local and remote systems. However, in the remote case, ASV systems raise
multiple privacy concerns. This comes from the fact that speech and the
information it carries are extremely sensitive in nature: from speech one can
extract information as diverse as the speaker’s age, gender, emotional or
personality traits, health state, among many others [1, 2]. As such, by
sending their voice – or a template thereof – to a remove server, users are
risking their privacy. These concerns are reflected in recent regulations, as
shown, for instance, by the definition of personal data provided by the
European Union’s General Data Protection Regulation (GDPR) [3], wherein speech
data and the information extracted from it are considered as Personally
Identifiable Information, i.e., information that, on its own, allows
determining the identity of an individual, and that, as such, is protected
under the GDPR [4].

Due to the above, the problem of protecting privacy in the setting of ASV has
been a precursor for much of the research done for speech privacy. One of the
first strides in this direction is the cryptographic-based work of Pathak et
al. [5], who adapted a Gaussian Mixture Model (GMM) to work with Homomorphic
Encryption (HE) in order to perform speaker verification. Similarly, Portêlo
et al. [6] implemented a privacy-preserving GMM-based speaker verification
using Garbled Circuits. More recently, Nautsch et al. and Treiber et al.
applied Homomorphic Encryption [7] and Secure Multiparty Computation [8, 9] to
the same problem. Differently, Pathak et al. [10], Portêlo et al. [11] and
Jiménez et al. [12] have explored the applicability of distance-preserving
hashing techniques to privacy-preserving ASV, while Mtibaa et al. have studied
cancelable biometric schemes for ASV [13, 14].

However, the above-mentioned works focus mainly on the security of the speaker
templates or on how the verification step itself can be performed privately,
sharing the assumption that the client locally extracts voice templates. In
contrast, we argue that this is extremely undesirable for service providers.
Specifically, we argue that the model used to extract voice templates, or
speaker embeddings, is one of the, if not the most valuable component in the
speaker verification pipeline. This stems from the fact that speaker embedding
extractors require large amounts of data and high levels of expertise to be
developed. As such, by sharing this model, ASV service providers would
relinquish control over their intellectual property, and consequently, lose
the value it holds. Further, as noted by Das et al. [15] and Villalba et al.
[16], having knowledge of the speaker embedding extractor model may allow
attackers to craft adversarial examples that mislead the ASV system, raising
security and robustness concerns. For this reason, in this work we show how
speaker embeddings can be extracted privately using Secure Multiparty
Computation. Specifically, we focus on the private extraction of x-vector
speaker embeddings [17]. This not only allows the protection of the speaker’s
voice, as it is never shared with the ASV provider, but also the protection of
the speaker embedding extraction model. Moreover, even though we only consider
the private extraction of x-vectors, our implementation can be directly
combined with some of the above-mentioned works for private speaker
verification [2, 9], in order to produce a fully end-to-end private speaker
verification system that protects both the speaker’s voice and the vendor’s
model.

The remainder of this paper is organised as follows: in Section 2 we provide
the necessary background on Secure Multiparty Computation (SMC); Section 3
specifies the setting and threat models assumed for our task; in Section 4 we
describe the experimental setup, while in Section 5 we present and discuss the
results obtained. Finally, Section 6 presents our conclusions and topics for
future work.

##  2 Secure Multiparty Computation

Secure Multiparty Computation (SMC) is an umbrella term for protocols designed
to allow several parties to jointly and securely compute functions over their
data, while keeping all inputs private. SMC protocols are usually built over
some form of Secret Sharing (e.g. Shamir’s Secret Sharing [18], GMW [19], BGW
[20]), or Garbled Circuits (e.g., Yao’s GCs [21], BMR [22]), and are often
combined with cryptographic primitives like public-key encryption, symmetric
encryption, Homomorphic Encryption (HE) or Oblivious Transfers (OTs) to
perform specific functionalities, each lending different levels of security,
computational and communication costs [23]. Our approach for the private
extraction of x-vectors relies on two forms of secret sharing briefly
described below.

###  2.1 Secret Sharing

Secret sharing is a basic primitive for SMC protocols. It allows parties to
represent and share their data with other parties in such a way that each of
the parties participating in the computation will only have access to a
random-looking share (here denoted as $\langle{\cdot}\rangle$) of the original
value. Considering an additive secret sharing scheme in the $n$-party case, a
value $x$ secret shared among several parties by a dealer, is defined as:

$x=\langle{x}\rangle_{1}+\langle{x}\rangle_{2}+...+\langle{x}\rangle_{n},$ (1)

where $\langle{x}\rangle_{1}$, …, $\langle{x}\rangle_{n}$ represent random-
looking shares of $x$ held by each party, generated as
$\langle{x}\rangle_{n}=x-\sum_{i=1}^{n-1}s_{i}$, where each $s_{i}$ is chosen
uniformly at random. When a value is represented in this way, a single party
is not able to reconstruct the secret without the remaining parties. Further,
this representation allows for parties to interactively compute any operation
over their secret data. For instance, due to the associative property of
addition, adding two shared values simply amounts to each party adding the
shares they hold that correspond to the two values, without requiring any
communication with the other parties.

On the other hand, in the case of multiplications, additive secret sharing
schemes require additional pre-computed random shared values called
Multiplication Triples (MTs) (or Beaver Triples [24]). These values are shares
of the form $\langle{a}\rangle$, $\langle{b}\rangle$ and $\langle{c}\rangle$,
where $\langle{c}\rangle~{}=~{}\langle{a}\rangle\times\langle{b}\rangle$. To
perform a multiplication between shared values $x$ and $y$, each party sets
its shares to
$\langle{e}\rangle_{i}=\langle{x}\rangle_{i}-\langle{a}\rangle_{i}$ and
$\langle{f}\rangle_{i}=\langle{y}\rangle_{i}-\langle{b}\rangle_{i}$ and
exchanges the results with the other parties, so that each party holds $e$ and
$f$. The resulting share is given by [25]:

$\langle{z}\rangle_{i}=i\cdot e\cdot
f+f\cdot\langle{a}\rangle_{i}+e\cdot\langle{b}\rangle_{i}+\langle{c}\rangle_{i}$
(2)

It can then be shown that by adding the $z_{i}$ we obtain $x\times y$.

The above works for any number of parties greater than or equal to two.
However, for a number of parties strictly larger than two, it is possible to
instantiate more efficient schemes. Replicated Secret Sharing (RSS) schemes
[26] are such an example. While in additive secret sharing, each party holds a
single share per value in the computation, with RSS each party holds a set of
shares per value. Considering for instance the three party case and a shared
value $y=\sum_{i=1}^{3}\langle{y}\rangle_{i}$, party $p_{1}$ will hold shares
$\langle{y}\rangle_{1},\langle{y}\rangle_{2}$, party $p_{2}$ will hold shares
$\langle{y}\rangle_{2},\langle{y}\rangle_{3}$ and party $p_{3}$ will hold
shares $\langle{y}\rangle_{3},\langle{y}\rangle_{1}$. In this case, addition
will work as before, and each party can simply perform the operation locally.
Multiplication, on the other hand, may work differently. A possible
implementation of the multiplication operation would be for each party to
locally multiply the shares it holds for each of the secret shared values. In
this way, party $p_{1}$ will obtain
$z_{1}=\langle{x}\rangle_{1}\langle{y}\rangle_{1}+\langle{x}\rangle_{1}\langle{y}\rangle_{2}+\langle{x}\rangle_{2}\langle{y}\rangle_{1}$;
party $p_{2}$,
$z_{2}=\langle{x}\rangle_{2}\langle{y}\rangle_{2}+\langle{x}\rangle_{2}\langle{y}\rangle_{3}+\langle{x}\rangle_{3}\langle{y}\rangle_{2}$
and party $p_{3}$,
$z_{3}=\langle{x}\rangle_{3}\langle{y}\rangle_{3}+\langle{x}\rangle_{3}\langle{y}\rangle_{1}+\langle{x}\rangle_{1}\langle{y}\rangle_{3}$.
As above, it can be shown that adding the resulting shares will yield the
correct result. Still, at the end of the computation, each party only holds a
single share of the value, and a re-sharing protocol is required, so that each
party holds the same set of shares as before [27].

The above-mentioned schemes are described with regard to arithmetic
operations, but also hold for binary computations, with minor modifications
[19]. This is important, as performing operations in each of these domains may
prove to be more efficient for different operations, or may even allow
performing different functionalities. Depending on the SMC protocol, the
conversion between domains may take different forms. In some protocols, it is
possible to convert between domains locally, with minimal interaction between
parties [28, 29]. However, other protocols may need to use pre-computed values
that are shared in both domains such as daBits [30] or edaBits [31].

The generation of Multiplication Triples, daBits, edaBits, as well as other
auxiliary secret shares – called correlated randomness – requires the
participation and interaction of all the parties involved in the computation.
However, since the generation of these auxiliary shares is not dependent on
input data, this step can be moved to what is called an offline, or pre-
processing phase. This phase can be performed at any time before the online
data-dependent phase. Many protocols are hence designed to have the most
expensive operations within the offline phase, making the online phase much
more efficient.

###  2.2 Fixed-point numbers

An important detail of SMC protocols is the fact that secret shared values are
integers, whereas for most real-world applications, values are floating-point
numbers. While floating-point representations exist within SMC, fixed-point
representations are much more efficient. In this work, we adopt the fixed-
point representation of [29], where a value $x$ is represented as $x=y\cdot
2^{f}$, where $y$ is an integer, and $f$ is the fixed precision. While this
approximation does not affect additions, for multiplications, one needs to
first multiply the two integers, and then truncate by $f$. This can be
implemented as a binary left shift operation [32], or via probabilistic
truncation [33, 34, 31].

###  2.3 Security

The shared nature of SMC protocols demands making threat assumptions about the
participating parties. The threat model of an SMC protocol is extremely
important as it significantly affects its security, computational and
communication performance, and thus, its range of applications.

The most common security (or threat) models include the semi-honest adversary
model (also called honest-but-curious adversary or passive security) and the
malicious adversary model (or active security). The honest-but-curious model
is the simplest model possible. In this model, the adversaries are assumed to
follow the established protocol, but are also assumed to pry into and record
the data that is visible to them. In this way, no party will be able to obtain
information other than that which it is allowed to, resulting in very
efficient implementations. On the other hand, the malicious model assumes that
adversaries will attempt to thwart the protocol, demanding additional proof
that each party is behaving correctly. This can be done in different ways,
depending on the protocol and phase of the computation, through Zero Knowledge
(ZK) proofs, cut-and-choose methods, Message Authentication Codes (MACs),
among others [35, 36, 29]. Although more secure, this model significantly
increases the protocol’s computational cost.

Besides the behaviour of individual parties, one can also define the security
of the protocol in terms of whether a majority of the parties will behave
correctly or not – honest majority vs dishonest majority, and whether a subset
of parties might collaborate – or collude – to obtain more information than
they are allowed to. If a majority of parties are assumed to be honest,
protocols that take into account malicious behaviour can be made much more
efficient [37, 28]. On the other hand, the highest possible level of security
is achieved by assuming malicious adversaries in a dishonest majority.
However, this comes at very high computational and communication costs [35,
36].

##  3 Privacy-preserving speaker embedding extraction

We consider two parties to be involved in the extraction of speaker embeddings
in the context of ASV: the client, who wants to be able to access a given
system and the ASV Vendor, who provides the authentication system as a
service. If we were considering a full ASV system, we would also need to
consider the ASV Controller, the party who holds the set of speaker templates
who are allowed to access the system. However, since in this work we only
focus on the extraction of speaker embeddings, we will not take this party
into account. Nonetheless, in some cases the vendor and controller may be same
party.

Figure 1: Privacy-preserving extraction of speaker embeddings.

###  3.1 Threat models

Our goal is to have the vendor and client collaborate to privately extract a
speaker embedding from a speech sample belonging to the client, using an
extraction model belonging to the vendor. We consider that both the client and
vendor are interested in protecting the privacy of their own data – the client
for the sensitive nature of their speech data, and the vendor due to the value
and security of its model. To this end, we consider four scenarios.

In the first scenario, the vendor and client are the only parties involved in
the private extraction of the speaker embedding, and are both assumed to be
semi-honest. This is the weakest security model, as either the vendor or the
client might thwart the protocol to obtain information about the other’s data.

In the second scenario, we consider adding a trusted non-colluding SMC server
to the computation. In a real world setting, this party would correspond to a
company providing servers for SMC. Since such a company would need to rely on
its reputation for its business, we argue that it would always follow
protocol, and would never collude with any other party involved in the
computation [38]. By adding this trusted non-colluding server, and since the
client and vendor have no incentive to collude – the SMC server does not have
data to be stolen – this allows us to instantiate the honest majority 3-party
RSS SMC protocol of Araki et al. [26]. As discussed in Section 2.1, RSS
schemes are much more efficient than additive secret sharing protocols while
keeping the same level of security [26].

For our third scenario, we consider adding a second trusted non-colluding SMC
server. This allows us to instantiate a 4-party honest-majority RSS SMC
protocol. Specifically, we can instantiate the 4-party protocol of Dalskov et
al. [28], which is secure against one malicious party. In this way, if either
the client or the vendor behave maliciously, the protocol will abort. Since
the client and the vendor will not collude, and the SMC servers are assumed to
be trusted, this setting will be more secure than the previous. However, in
this case the non-collusion assumption of the SMC server is much stronger.

In our fourth scenario we return to the 2-party setting, and assume that
either the vendor or the client might behave maliciously. This is the setting
with the highest level of security, however, it will also incur the highest
computational and communication costs. A diagram of the aforementioned
computational settings can be found in Figure 1.

###  3.2 Privacy-preserving x-vector extraction using SMC

Originally proposed by Snyder et al. [17], the x-vector architecture is a
neural network trained to discriminate between a large number of speakers.
Within this context, x-vectors correspond to latent representations extracted
from an intermediate layer of the network. This network is composed of three
main blocks: the first block is a set of time-delay (TDNN) layers that operate
at the frame level with a small temporal context. These layers work as 1D
dilated convolutions, with a kernel size corresponding to the temporal
context, which alternate with ReLU non-linearities; the second block, a
statistical pooling layer, aggregates the information across the time
dimension and outputs the per-feature mean and standard deviation for the
entire speech segment; the third block is a set of fully connected layers,
from which x-vector embeddings are extracted after the network is trained for
speaker classification.

To implement this extractor with SMC, we need to take into account the type of
operations required by each layer in the network. 1D dilated convolutional
layers are linear transformations and can be implemented using either the
basic arithmetic operations of the SMC protocol, or with specific protocols
for inner product computations [29]. ReLU activations require the computation
of a comparison, which can be done through the secure comparison protocol of
[33]. The Statistical Pooling layer involves computing the mean and standard
deviation of the input. To compute the standard deviation, we will need to
compute a square-root, which can be done through the protocol of [39].

All the protocols mentioned above work for the fixed-point number
representation of Section 2.2, making them directly compatible with the
weights and inputs of neural networks, after these have also been converted to
a fixed-point representation.

##  4 Experimental Setup

Table 1: Results obtained for each protocol in terms of computational
performance and communication cost.

Protocol |  Security Model | Time (s) | Communication (MB)
---|---|---|---
Pre-processing | Online | Total | Pre-processing | Online | Total
2-party Semi${}_{2^{k}}$ [36] | DM/SH |  8,423.00. $\pm$ 165.36∗ |  18.92 $\pm$ 0.22 |  8,441.93 $\pm$ 165.36 |  1,662,300.60∗ | 12,919.40 | 1,675,220.00
3-party RSS [26] | HM/SH |  0.18 $\pm$ 0.20∗ |  10.68 $\pm$ 0.15 |  10.85 $\pm$ 0.14 |  15.04∗ | 118.02 | 133.06
4-party RSS [28] | HM/Mal |  1.21 $\pm$ 0.29∗ |  16.76 $\pm$ 0.21 |  17.97 $\pm$ 0.21 |  27.14∗ | 333.16 | 360.30
2-party SPDZ${}_{2^{k}}$ [36] | DM/Mal |  147,799.68 $\pm$ 1,016.82∗ |  126.32 $\pm$ 1.16 |  147,926.00 $\pm$ 1,016.82 |  21,870,489.60∗ | 27,810.40 | 21,898,300.00

###  4.1 Corpora

The Voxceleb corpus was used to train the x-vector extractor and the
Probabilistic Linear Discriminant Analysis (PLDA) model described below. This
corpus includes recordings of 7,363 speakers of multiple ethnicities, accents,
occupations and age groups. It is composed of short clips taken from
interviews uploaded to YouTube [40, 41]. The corpus is composed of two parts,
VoxCeleb 1 and 2, both subdivided into dev and test.

###  4.2 Speaker embeddings

For our experiments we used the pre-trained x-vector model made available by
SpeechBrain [42]. This model follows the architecture of [17]. A description
of the layers used for extraction can be found in Table 2. The model was
trained using the dev partitions of Voxceleb 1 and 2. As a baseline reference
for computational cost, extracting a single x-vector from a 3-second long
speech sample with this model, using a CPU, takes $\sim$0.03s.

Table 2: x-vector extractor architecture.

# | Layer | Input | Output | Kernel | Dilation
---|---|---|---|---|---
1 | TDNN 1 | 24 | 512 | 5 | 1
2 | TDNN 2 | 512 | 512 | 3 | 2
3 | TDNN 3 | 512 | 512 | 3 | 3
4 | TDNN 4 | 512 | 512 | 1 | 1
5 | TDNN 5 | 512 | 1500 | 1 | 1
6 | Statistics Pooling | 1500 | 3000 | - | -
7 | Linear | 3000 | 512 | - | -

A Probabilistic Linear Discriminant Analysis (PLDA) model was used to score
pairs of x-vectors when performing verification [43]. The full pipeline
achieves 3.2% Equal Error Rate (EER) on the Voxceleb 1 test set (Cleaned) [41,
42].

###  4.3 Privacy-preserving implementation

The network described in the previous subsection was implemented using the MP-
SPDZ library [29]. We tested our implementation using four different protocols
with different levels of security, as detailed in Section 3.1. Specifically,
we tested our implementation over the following protocols: the 2-party semi-
honest (SH) version of the SPDZ${}_{2^{k}}$ scheme for dishonest majority
(DM), denoted as Semi${}_{2^{k}}$ [36]; the 3-party RSS scheme described in
[26], which provides semi-honest security, in the honest majority (HM)
setting; the 4-party RSS scheme of [28], which provides malicious (Mal)
security in the honest majority setting against one corrupted party; and the
2-party malicious version of the SPDZ${}_{2^{k}}$ scheme [36].

For 3 and 4-party RSS and for the semi-honest version of SPDZ${}_{2^{k}}$, we
used local share conversions [28] to improve efficiency. For 3 and 4-party
RSS, we also used probabilistic truncation as proposed by [34, 28], instead of
regular truncation, to further improve efficiency. Our experiments assume the
default security parameters for each protocol, namely 40-bit security for 3
and 4-party RSS, and Semi${}_{2^{k}}$, and 64-bit security for
SPDZ${}_{2^{k}}$. We used the library’s fixed-point number representation
adopting the default configuration of 16 bits for the decimal part, and 15
bits for the fractional part. All tested protocols perform computations modulo
$2^{k}$, where $k=64$. Experiments were performed on a machine with 24
Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz processors and 250GB of RAM.

##  5 Results

Table 1 includes the results obtained for our experiments in terms of
computational performance and communication cost. All results correspond to
the extraction of a single x-vector using a 3-second long speech sample.
Online results for all protocols, and for full results for 3 and 4-party RSS,
were obtained by averaging over 100 runs. Full results for Semi2k and SPDZ2k
were computed over 10 runs, due to their high computational cost. Values
denoted with ∗ were estimated by computing the difference between the full
protocol and the online phase.

Our results show that RSS schemes significantly outperform the semi-honest and
malicious versions of SPDZ${}_{2^{k}}$, both in terms of computational and
communication performance. Further, since for the semi-honest version of
SPDZ${}_{2^{k}}$, pre-processing takes $>$2h and $>$1TB of data, and since the
pre-processing for the malicious version takes $>$41h and $>$20TB of data, it
is clear that the private extraction of x-vectors with these protocols,
particularly for a high level of security, is currently infeasible.
Contrarily, the results for the RSS schemes can be deemed feasible,
particularly when considering the fact that no modifications were made to
reduce the size of the x-vector extraction network. When comparing the 3 and 4
party RSS protocols, while the 3-party semi-honest version is more efficient
in terms of computational cost and communication, we argue that the added
security of the 4-party RSS protocol is a reasonable trade-off for the
$\sim$7s and $\sim$230MB difference in the total computational and
communication costs. Still, we need to consider that to implement the 4-party
RSS protocol we need strong assumptions about the honest behaviour of the SMC
servers.

Finally, our experiments showed that the SMC implementation yielded negligible
degradation, with the average Mean Squared Error distance between 100
x-vectors extracted with the original and SMC implementations being just $\sim
1\%$ of the total magnitude of the vector.

##  6 Conclusions

In this work we have shown that it is possible to extract x-vector speaker
embeddings at a reasonable level of security and computational and
communication costs, while protecting the privacy of both the client’s data
and the ASV Vendor’s model, using SMC, particularly when deploying on 3 and
4-party RSS protocols. This problem had been unexplored so far, as other
privacy-preserving works for ASV assumed that speaker embeddings to be
extracted by the client. This makes this work complementary to others in the
literature and another step towards fully private ASV pipelines.

As future work, we consider that it would be important to explore ways to
reduce the size of the x-vector extraction network, to improve efficiency.
Moreover, it would be interesting to also consider protocols following the
covert security model, wherein adversaries may have a malicious behaviour, but
where there is a probability that in doing so, they may be discovered.

## References

  * [1] R. Singh, _Profiling humans from their voice_. Springer, 2019, ISBN: 978-981-13-8403-5.
  * [2] A. Nautsch, A. Jiménez, A. Treiber, J. Kolberg, C. Jasserand _et al._ , “Preserving privacy in speaker and speech characterisation,” _Computer Speech & Language_, vol. 58, pp. 441–480, 2019.
  * [3] European Parliament and Council, “Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 - General Data Protection Regulation.” 2016.
  * [4] A. Nautsch, C. Jasserand, E. Kindt, M. Todisco, I. Trancoso, and N. Evans, “The GDPR & Speech data: Reflections of legal and technology communities, first steps towards a common understanding,” _arXiv preprint_ , vol. 1907.03458, 2019.
  * [5] M. A. Pathak and B. Raj, “Privacy-Preserving Speaker Verification and Identification Using Gaussian Mixture Models,” _IEEE TASLP_ , vol. 21, no. 2, pp. 397–406, 2013.
  * [6] J. Portêlo, B. Raj, A. Abad, and I. Trancoso, “Privacy-preserving speaker verification using garbled gmms,” in _22nd (EUSIPCO)_. IEEE, 2014, pp. 2070–2074.
  * [7] A. Nautsch, S. Isadskiy, J. Kolberg, M. Gomez-Barrero, and C. Busch, “Homomorphic Encryption for Speaker Recognition: Protection of Biometric Templates and Vendor Model Parameters ,” in _Proc. Odyssey_ , 2018, pp. 16–23.
  * [8] A. Nautsch, J. Patino, A. Treiber _et al._ , “Privacy-Preserving Speaker Recognition with Cohort Score Normalisation,” in _Proc. Interspeech 2019_ , 2019, pp. 2868–2872.
  * [9] A. Treiber, A. Nautsch, J. Kolberg, T. Schneider, and C. Busch, “Privacy-preserving PLDA speaker verification using outsourced secure computation,” _Speech Communication_ , vol. 114, pp. 60–71, 2019.
  * [10] M. A. Pathak and B. Raj, “Privacy-preserving speaker verification as password matching,” in _ICASSP_ , 2012, pp. 1849–1852.
  * [11] J. Portêlo, A. Abad, B. Raj, and I. Trancoso, “Secure Binary Embeddings of Front-end Factor Analysis for Privacy Preserving Speaker Verification,” in _Interspeech_ , 2013, pp. 2494–2498.
  * [12] A. Jiménez, B. Raj, J. Portêlo, and I. Trancoso, “Secure Modular Hashing,” in _WIFS_. IEEE, 2015, pp. 1–6.
  * [13] A. Mtibaa, D. Petrovska-Delacretaz, and A. B. Hamida, “Cancelable speaker verification system based on binary gaussian mixtures,” in _4th ATSIP_ , 2018, pp. 1–6.
  * [14] A. Mtibaa, D. Petrovska-Delacrétaz, J. Boudy, and A. B. Hamida, “Privacy-preserving speaker verification system based on binary i-vectors,” _IET Biometrics_ , vol. 10, no. 3, pp. 233–245, 2021.
  * [15] R. K. Das, X. Tian, T. Kinnunen, and H. Li, “The Attacker’s Perspective on Automatic Speaker Verification: An Overview,” in _Proc. Interspeech 2020_ , 2020, pp. 4213–4217.
  * [16] J. Villalba, Y. Zhang, and N. Dehak, “x-Vectors Meet Adversarial Attacks: Benchmarking Adversarial Robustness in Speaker Verification,” in _Proc. Interspeech 2020_ , 2020, pp. 4233–4237.
  * [17] D. Snyder, D. Garcia-Romero, G. Sell, D. Povey, and S. Khudanpur, “X-vectors: Robust DNN embeddings for speaker recognition,” in _Proc. ICASSP_ , Calgary, AB, Canada, April 2018.
  * [18] A. Shamir, “How to share a secret,” _Communications of the ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [19] O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game,” in _Proc. 19th STOC_. ACM, 1987, pp. 218–229.
  * [20] M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” in _Proc. 20th STOC_. ACM, 1988, pp. 1–10.
  * [21] A. C. Yao, “How to generate and exchange secrets,” in _27th SFCS_ , 1986, pp. 162–167.
  * [22] D. Beaver, S. Micali, and P. Rogaway, “The round complexity of secure protocols,” in _Proc. 22nd STOC_ , 1990, pp. 503–513.
  * [23] Y. Lindell, “Secure multiparty computation (MPC).” _IACR Cryptology ePrint Archive_ , vol. 2020, p. 300, 2020.
  * [24] D. Beaver, “Efficient multiparty protocols using circuit randomization,” in _CRYPTO_. Springer, 1991, pp. 420–432.
  * [25] D. Demmler, T. Schneider, and M. Zohner, “ABY - a framework for efficient mixed-protocol secure two-party computation,” in _NDSS_ , 2015.
  * [26] T. Araki, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara, “High-throughput semi-honest secure three-party computation with an honest majority,” in _SIGSAC_. ACM, 2016, p. 805–817.
  * [27] S. Wagh, S. Tople, F. Benhamouda, E. Kushilevitz, P. Mittal, and T. Rabin, “Falcon: Honest-majority maliciously secure framework for private deep learning,” _Proceedings on Privacy Enhancing Technologies_ , vol. 1, pp. 188–208, 2021.
  * [28] A. Dalskov, D. Escudero, and M. Keller, “Fantastic four: Honest-majority four-party secure computation with malicious security,” in _30th USENIX Security Symposium_ , 2021.
  * [29] M. Keller, “Mp-spdz: A versatile framework for multi-party computation,” _Cryptology ePrint Archive_ , vol. Report 2020/521, 2020.
  * [30] D. Rotaru and T. Wood, “Marbled circuits: Mixing arithmetic and boolean circuits with active security,” in _International Conference on Cryptology in India_. Springer, 2019, pp. 227–249.
  * [31] D. Escudero, S. Ghosh, M. Keller, R. Rachuri, and P. Scholl, “Improved primitives for mpc over mixed arithmetic-binary circuits,” in _Annual International Cryptology Conference_. Springer, 2020, pp. 823–852.
  * [32] O. Catrina and S. d. Hoogh, “Improved primitives for secure multiparty integer computation,” in _International Conference on Security and Cryptography for Networks_. Springer, 2010, pp. 182–199.
  * [33] O. Catrina and A. Saxena, “Secure computation with fixed-point numbers,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2010, pp. 35–50.
  * [34] A. Dalskov, D. Escudero, and M. Keller, “Secure evaluation of quantized neural networks,” _Proceedings on Privacy Enhancing Technologies_ , vol. 4, pp. 355–375, 2020.
  * [35] I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart, “Practical covertly secure mpc for dishonest majority–or: breaking the spdz limits,” in _European Symposium on Research in Computer Security_. Springer, 2013, pp. 1–18.
  * [36] R. Cramer, I. Damgård, D. Escudero, P. Scholl, and C. Xing, “Spd $\mathbb{Z}_{2^{k}}$: efficient mpc mod $2^{k}$ for dishonest majority,” in _Annual International Cryptology Conference_. Springer, 2018, pp. 769–798.
  * [37] J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein, “High-throughput secure three-party computation for malicious adversaries and an honest majority,” in _EUROCRYPT_. Springer, 2017, pp. 225–255.
  * [38] D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A framework for fast privacy-preserving computations,” in _European Symposium on Research in Computer Security_. Springer, 2008, pp. 192–206.
  * [39] A. Aly and N. P. Smart, “Benchmarking privacy preserving scientific operations,” in _International Conference on Applied Cryptography and Network Security_. Springer, 2019, pp. 509–529.
  * [40] A. Nagrani, J. S. Chung, and A. Zisserman, “Voxceleb: A large-scale speaker identification dataset,” _Interspeech 2017_ , Aug 2017.
  * [41] J. S. Chung, A. Nagrani, and A. Zisserman, “Voxceleb2: Deep speaker recognition,” _Interspeech 2018_ , Sep 2018.
  * [42] M. Ravanelli, T. Parcollet, P. Plantinga, A. Rouhe, S. Cornell _et al._ , “SpeechBrain: A general-purpose speech toolkit,” 2021, arXiv:2106.04624.
  * [43] P. Kenny, T. Stafylakis, P. Ouellet, M. J. Alam, and P. Dumouchel, “PLDA for speaker verification with utterances of arbitrary duration,” in _ICASSP_. IEEE, 2013, pp. 7649–7653.