# Measuring Lower Bounds of Local Differential Privacy via Adversary
Instantiations in Federated Learning

Marin Matsumoto
Ochanomizu University
<EMAIL_ADDRESS>
&Tsubasa Takahashi
LINE Corporation
<EMAIL_ADDRESS>
&Seng Pei Liew
LINE Corporation
<EMAIL_ADDRESS>
&Masato Oguchi
Ochanomizu University
<EMAIL_ADDRESS>

###### Abstract

Local differential privacy (LDP) gives a strong privacy guarantee to be used
in a distributed setting like federated learning (FL). LDP mechanisms in FL
protect a client’s gradient by randomizing it on the client; however, how can
we interpret the privacy level given by the randomization? Moreover, what
types of attacks can we mitigate in practice? To answer these questions, we
introduce an empirical privacy test by measuring the lower bounds of LDP. The
privacy test estimates how an adversary predicts if a reported randomized
gradient was crafted from a raw gradient $g_{1}$ or $g_{2}$. We then
instantiate six adversaries in FL under LDP to measure empirical LDP at
various attack surfaces, including a worst-case attack that reaches the
theoretical upper bound of LDP. The empirical privacy test with the adversary
instantiations enables us to interpret LDP more intuitively and discuss
relaxation of the privacy parameter until a particular instantiated attack
surfaces. We also demonstrate numerical observations of the measured privacy
in these adversarial settings, and the worst-case attack is not realistic in
FL. In the end, we also discuss the possible relaxation of privacy levels in
FL under LDP.

##  1 Introduction

Federated learning (FL) is a machine learning technique in which clients never
share the raw data but the gradient with the server. Exposing only the
gradient would seem to protect the client’s privacy; however, several
studies[14, 43] have shown that the gradient can recover the original image.
One way of privacy protection is applying local differential privacy (LDP)
[11, 23]. LDP has been a widely accepted privacy standard that makes it hard
to distinguish randomized responses crafted from any inputs to the extent that
the privacy parameter $\varepsilon$ quantifies it. Recent studies have been
seeking a practical LDP mechanisms in FL [3, 30, 15].

To seek practice of LDP in FL, we need to understand the criteria for setting
the privacy parameter $\varepsilon$. We have a study about statistical
interpretation [18, 27], but the interpretations are still complicated and not
enough for practitioners yet. To give more intuitive interpretations that
enable us to assess guaranteed privacy, we have the following two issues; 1)
how can we interpret the privacy level given by LDP mechanisms? 2) what types
of attacks can we mitigate in practice? To answer these questions, we first
introduce a privacy measurement test based on statistical discrimination
between randomized responses under various adversaries. Based on the privacy
measurement test, we tackle instantiations of adversaries in FL using locally
differentially private stochastic gradient descent (LDP-SGD) [8, 10]. As for
the adversary instantiations, we consider various capabilities for crafting
raw gradients (i.e., what types of information the adversary is allowed to
access).

Figure 1(a) shows our empirical privacy measurement that is inspired by the
hypothesis tests for measuring the lower bound of central DP (CDP) [36, 19].
The privacy test estimates how an adversary predicts if a reported randomized
gradient was crafted from a raw gradient $g_{1}$ or $g_{2}$. To realize such
distinguishing game, we introduce crafter and distinguisher. Crafter
(maliciously) generates $g_{1}$ and $g_{2}$, then submits a randomized
gradient of either one. Distinguisher attempts to discriminate the source of
the randomized gradient. The empirical LDP is estimated over sufficient number
of games.

As for the adversary instantiations, the main challenge is to actualize robust
adversary attacks against the noise to achieve $\varepsilon$-LDP since the LDP
mechanisms tend to inject exetemely larger noise than those of CDP. In
addition, we also need to consider collusions between the server and the
client. This paper tackles these challenges to realize the way to measure the
lower bounds of LDP in FL, and demonstrates the measured $\varepsilon$ ranging
from the benign to the worst-case in Figure 1(b).

As a result of our solutions, this paper shows the following four facts: (a)
adversaries who directly manipulate raw gradients (i.e., white-box
distinguisher) can reach the theoretical upper bounds given by the privacy
parameter $\varepsilon$, (b) even in white-box scenarios, the crafters with
accessing only the input data and parameters but not the raw gradient have
limited capability, (c) the distinguishers with referring only to the updated
model but not any randomized gradient (i.e., black-box distinguisher) have
limited capability, (d) collusion with the server, like malicious pre-
training, increases the adversary’s capability. See the details in section 4.

Contributions. We here summarize our contributions as following three claims:

  1. 1.

We establish the empirical privacy measurement test of LDP in distributed
learning environments.

  2. 2.

We introduce six types of adversary instantiations that helps practitioners
interpret the privacy parameter $\varepsilon$. We also seek the worst-case
attack in FL using LDP-SGD.

  3. 3.

We demonstrate the empirical privacy levels (i.e., lower bounds of LDP) at
various attack surfaces defined by the instantiated adversaries.

This study enables us to discuss appropriate privacy levels and their
relaxations between the (unrealistic) worst-case scenario and the other weak
adversaries. At the end, we also discuss the feasibility of the relaxation
with introducing a trusted entity like secure aggregator.

(a) Our privacy measuring test in federated learning.

(b) Measured privacy.

Figure 1: Our (a) privacy test demonstrates (b) empirical LDP against six
instantiated adversaries. The test consists of crafter, which generates
(malicious) inputs, and distinguisher, which infers the input. The measured
privacy is close to the theoretical bound given by $\varepsilon$ when the
adversary directly manipulates raw gradients (i.e., white-box distinguisher),
resulting in far from the bound otherwise.

Related work. [29, 20, 19, 36] instantiated adversaries in machine learning
under CDP. Liu et al.[29] proposed an interpretation of the CDP by means of a
hypothesis test. An adversary predicts whether the input data is $D$ or
$D^{\prime}$ from the output. They quantified the success of the hypothesis
test using precision-recall-relation. Jagielski et al. [19] were the first to
attempt an empirical privacy measure using a hypothesis test. They analyzed
the privacy level of training models privacy-protected with DP-SGD [1, 2, 40]
against membership inference [42] and two poisoning attacks [17, 19]. Nasr et
al. [36] showed that theoretical and empirical $\varepsilon$ are tight when a
contaminated database is used for training in DP-SGD. As mentioned above, we
follow the abstract framework proposed in [36] but address further challenging
issues to realize how to measure the lower bounds of LDP in FL. ML Privacy
Meter [34] verifies whether a mechanism guarantees privacy, while our study
shows how a mechanism that already guarantees $\varepsilon$-LDP can withstand
attacks.

##  2 Preliminaries

This section introduces essential knowledge for understanding our proposal. We
first describe local differential privacy. Then, we introduce LDP-SGD, a local
privacy mechanism in distributed learning.

###  2.1 Local Differential Privacy

######  Definition 1 ($\varepsilon$-Local Differential Privacy).

A randomized algorithm $\mathcal{M}$ satisfies $\varepsilon$-local
differential privacy, if and only if for any pair of inputs $x,x^{\prime}\in
D$ and for any possible output $S\in Range(\mathcal{M})$:

$\text{Pr}[\mathcal{M}(x)\in S]\leq
e^{\varepsilon}\cdot\text{Pr}[\mathcal{M}(x^{\prime})\in S].$ (1)

Intuitively, we only obtain the indistinguishable information from
$\mathcal{M}$ even when the inputs differ.

Algorithm 1 LDP-SGD; client-side $\mathcal{A}_{\text{client}}$ [10]

0: Local privacy parameter: $\varepsilon$, current model:
$\theta_{t}\in\mathbb{R}^{d}$, $\ell_{2}$-clipping norm: $L$

1: Compute clipped gradient
$x\leftarrow\nabla\ell(\theta_{t};d)\cdot\min\left\\{1,\dfrac{L}{||\nabla\ell(\theta_{t};d)||_{2}}\right\\}$

2: $z\leftarrow\begin{cases}L\cdot\frac{x}{||x||_{2}}&\textrm{w.p.
}\frac{1}{2}+\frac{||x||_{2}}{2L}\\\
-L\cdot\frac{x}{||x||_{2}}&\textrm{otherwise.}\end{cases}$

3: Sample $v\sim_{u}S^{d}$, the unit sphere in $d$ dims
$\hat{z}\leftarrow\begin{cases}\text{sgn}(\langle z,v\rangle)\cdot
v&\textrm{w.p. }\frac{e^{\varepsilon}}{1+e^{\varepsilon}}\\\
-\text{sgn}(\langle z,v\rangle)\cdot v&\textrm{otherwise.}\end{cases}$

4: return $\hat{z}$

Algorithm 2 LDP-SGD; server-side $\mathcal{A}_{\text{server}}$ [10]

0: Local privacy budget: $\varepsilon$, number of epochs: $T$, parameter set:
$C$

1: $\theta_{0}\leftarrow\\{0\\}^{d}$

2: for $t\in[T]$ do

3: Send $\theta_{t}$ to all clients

4:
$g_{t}\leftarrow\frac{L\sqrt{\pi}}{2}\cdot\frac{\Gamma(\frac{d-1}{2}+1)}{\Gamma(\frac{d}{2}+1)}\cdot\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\left(\frac{1}{n}{\sum_{i\in[n]}\hat{z}_{i}}\right)$

5: Update: ${\theta_{t+1}\leftarrow\prod_{C}(\theta_{t}-\eta_{t}\cdot
g_{t})}$,where $\prod_{C}(\cdot)$ is the $\ell_{2}$-projection onto set $C$,
and
$\eta_{t}=\frac{||C||_{2}\sqrt{n}}{L\sqrt{d}}\cdot\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}$

6: end for

7: return $\theta_{priv}\leftarrow\theta_{T}$

###  2.2 Federated Learning using LDP-SGD

Federated learning (FL) [32, 22] is a decentralized machine learning
technique. The major difference between traditional machine learning and FL is
that client does not share her data with servers or other clients. However, in
FL, it is pointed out that the images used in training the model can be
restored from their gradients released by clients [14, 43]. One way to prevent
the restoration is to randomize gradients for satisfying LDP.

As shown in Figure. 1(a), FL assumed in this paper consists of an untrusted
model trainer (server) and clients that own sensitive data. First, the client
creates the gradient with the parameters distributed by the model trainer. The
client then randomizes the gradient under LDP and sends it to the model
trainer. The model trainer updates the parameters with the gradient collected
from the client. We randomize the gradient using LDP-SGD (locally
differentially private stochastic gradient descent) [8, 10] as described in
Algorithm 1 and 2. The client side algorithm (Algorithm 1) performs two
gradient randomizations at line 2 and 3. We refer to the line 2 as gradient
norm projection and the line 3 as random gradient sampling. We instantiate the
adversary based on the following two facts:

  * •

Gradient norm projection (line 2): the smaller the norm of the gradient before
randomization, the more likely the sign of the gradient is reversed.

  * •

Random gradient sampling (line 3): the gradient close to the gradient before
randomization is likely to be generated when the privacy parameter
$\varepsilon$ is set large.

##  3 Measuring Lower Bounds of LDP

This section describes how to measure the empirical privacy level of FL under
LDP.

###  3.1 Lower Bounding $\varepsilon$ of LDP as Hypothsis Testing

Given a output $y$ of a randomized mechanism $\mathcal{M}$, consider the
following hypothesis testing experiment. We choose a null hypothesis as input
$x$ and alternative hypothesis as $x^{\prime}$:

$H_{0}$: $y$ came from a input $x$

$H_{1}$: $y$ came from a input $x^{\prime}$

For a choice of a rejection region $S$, the false positive rate(FP), when the
null hypothesis is true but rejected, is defined as Pr[$\mathcal{M}(x)\in S$].
The false negative rate(FN), when the null hypothesis is false but retained,
is defined as Pr[$\mathcal{M}(x^{\prime})\in\bar{S}$] where $\bar{S}$ is the
complement of $S$. Mechanism $\mathcal{M}$ satisfying $\varepsilon$-LDP is
equivalent to satisfying the following conditions[21].

######  Theorem 1 (Empirical $\varepsilon$-Local Differential Privacy).

For any $\varepsilon\in\mathbb{R}^{+}$, a randomized mechanism $\mathcal{M}$
is $\varepsilon$-differentially private if and only if the following
conditions are satisfied for all pairs of input values $x$ and $x^{\prime}$,
and all rejection region $S\subseteq Range(\mathcal{M})$:

$\begin{split}\text{Pr}[\mathcal{M}(x)\in
S]+e^{\varepsilon}\cdot\text{Pr}[\mathcal{M}(x^{\prime})\in\bar{S}]&\geq
1,and\\\ e^{\varepsilon}\cdot\text{Pr}[\mathcal{M}(x)\in
S]+\text{Pr}[\mathcal{M}(x^{\prime})\in\bar{S}]&\geq 1.\end{split}$ (2)

Therefore, we can determine the empirical $\varepsilon$-local differential
privacy as

$\varepsilon_{\text{empirical}}=\max\left({\log\dfrac{1-\text{FP}}{\text{FN}},\log\dfrac{1-{\text{FN}}}{\text{FP}}}\right)$
(3)

For example, in 100 trials, suppose the false-positive rate, when the actual
input was $x$ but the distinguisher guesses $x^{\prime}$, was 0.1, and the
false-negative rate, when the actual input was $x^{\prime}$ but the
distinguisher guesses $x$, was 0.2. Substitute in FP and FN in Equation 3 to
obtain $\varepsilon_{\text{empirical}}\fallingdotseq 2.0$.

###  3.2 Instantiating the LDP Adversary in FL

To perform the privacy test based on the above hypothesis testing, we define
the following entities:

  * •

Crafter produces two gradients, $g_{1}$ and $g_{2}$, with the global model
$\theta_{t}$, corresponding to a malicious client in FL. This entity honestly
randomizes one of gradients by Algorithm 1 and makes it $\tilde{g}$.
$\tilde{g}$ is sent to the model trainer and distinguisher.

  * •

Model trainer uses the $\tilde{g}$ received from the crafter to update the
global model $\theta_{t}$ to $\theta_{t+1}$ by Algorithm 2. This entity
corresponds to a untrusted server in FL.

  * •

Distinguisher predicts whether the randomized gradient was $g_{1}$ or $g_{2}$.
This entity has the data $x_{1}$, $x_{2}$ that the crafter used to generate
the gradient.

We divide the distinguisher into two classes, black-box distinguisher and
white-box distinguisher. For each distinguisher, we propose two different
privacy measurement tests, namely, black-box LDP test (Algorithm 3) and white-
box LDP test (Algorithm 4).

Algorithm 3 Black-box LDP Test in FL

0: Privacy parameter: $\varepsilon$, $\\#$trials: $K$

1: for $k\in[K]$ do

2: Model trainer sends $\theta_{t}$ to crafter.

3: Crafter

4: $\\{g_{1},g_{2}\\}\leftarrow\text{Craft}(x_{1},x_{2},\theta_{t})$

5: Randomly choose $g$ from $\\{g_{1},g_{2}\\}$.

6: $\tilde{g}\leftarrow\mathcal{A}_{\text{client}}(g)$.

7: Submit $\tilde{g}$ to model trainer.

8: Share $x_{1}$, $x_{2}$, $\theta_{t}$ w/ distinguisher

9: Model Trainer

10: $\theta_{t+1}\leftarrow\mathcal{A}_{\text{server}}(\theta_{t})$

11: Submit $\theta_{t+1}$ to distinguisher

12: Distinguisher

13:
$\text{guess}\leftarrow\mathcal{D}_{\text{black}}(\theta_{t+1},\theta_{t},x_{1},x_{2})$

14: end for

15: Compute $\varepsilon_{\text{empirical}}$ as (3)

Algorithm 4 White-box LDP Test in FL

0: Privacy parameter: $\varepsilon$, $\\#$trials: $K$

1: for $k\in[K]$ do

2: Model trainer sends $\theta_{t}$ to crafter.

3: Crafter

4: $\\{g_{1},g_{2}\\}\leftarrow\text{Craft}(x_{1},x_{2},\theta_{t})$

5: Randomly choose $g$ from $\\{g_{1},g_{2}\\}$

6: $\tilde{g}\leftarrow\mathcal{A}_{\text{client}}(g)$.

7: Submit $\tilde{g}$ to distinguisher.

8: Share $g_{1}$, $g_{2}$ w/ distinguisher.

9: Distinguisher

10: $\text{guess}\leftarrow\mathcal{D}_{\text{white}}(\tilde{g},g_{1},g_{2})$

11: end for

12: Compute $\varepsilon_{\text{empirical}}$ as (3)

###  3.3 Dinstinguisher Algorithms

#### Black-box Distinguisher.

Let black-box distinguisher $\mathcal{D}_{\text{black}}$ be the distinguisher
that cannot access the randomized gradient, but can access the global
parameters $\theta_{t+1}$ updated with using it. That is, the black-box
disntinguisher only observes the updates after each step of federated
learning, but not see any details of inner process of the federated learning.
For simplicity’s sake, we only consider the global model is updated using a
single randomized gradient. The black-box distinguisher predicts the
randomized gradient by computing the loss of $x_{1}$ (and $x_{2}$), then
compare the differences before and after the model update. By default, the
distinguisher $\mathcal{D}_{\text{black}}$ employs the following inference
against two choices:

$guess=\begin{cases}{g_{1}}&f(x_{1};\theta_{t+1})\leq f(x_{1};\theta_{t})\\\
{g_{2}}&otherwise\end{cases}.$ (4)

This is based on that $g_{2}$ aims to degrade the model. However, the
inference does not work well for all crafters. In section 3.4, we mention
about the replacement for the inequality.

#### White-box Distinguisher.

White-box distinguisher $\mathcal{D}_{\text{white}}$ directly accesses a
single randomized gradient $\tilde{g}$. In addition, the white-box
distinguisher can generate two raw gradients $g_{1}$ and $g_{2}$ as well as
the client, then computes the similarity between $\tilde{g}$ and the raw
gradients to estimate the origin of the $\tilde{g}$. Here, we employ the
cosine similarity between $\tilde{g}$ and $\\{g_{1},g_{2}\\}$. The
discrimination by the white-box distinguisher is defined as follows:

$guess=\begin{cases}{g_{1}}&cos(\tilde{g},g_{1})\geq cos(\tilde{g},g_{2})\\\
{g_{2}}&otherwise\end{cases}.$ (5)

###  3.4 Crafter Algorithms

We propose several types of adversaries depending on the access level. We
introduce six types of crafter algorithms Craft($\cdot$) in Algorithm 3 and 4.
One crafter algorithm assumes collusion with the model trainer. The adversary
setting proposed in this paper is summarized in Table 1.

Table 1: Adversary settings. The lower the row, the stronger (i.e. more unrealistic) the adversary. Adversary | Malicious Access | Distinguisher
---|---|---
Crafter | Model trainer | Black-box | White-box
Benign | Benign. | Benign. |  Eq. (6) |  Eq. (5)
Input perturbation | Images. | Benign. |  Eq. (4) |  Eq. (5)
Parameter retrogression | Parameters. | Benign. |  Eq. (4) |  Eq. (5)
Gradient flip | Gradients. | Benign. |  Eq. (4) |  Eq. (5)
Collusion | Gradients | Parameters. |  Eq. (4) |  Eq. (5)
Dummy gradient | Gradients. | Benign. |  Eq. (7) |  Eq. (5)

Benign setting. As the most realistic setting, suppose all entities are
benign. In the benign setting, the crafter uses the global model $\theta_{t}$
distributed by the model trainer to generate gradients $g_{1}$ and $g_{2}$
from the images $x_{1}$ and $x_{2}$. Thus, the two gradients are also crafted
without malicious behaviors as:

$\displaystyle g_{1}=\nabla f(x_{1},\theta_{t});$ $\displaystyle g_{2}=\nabla
f(x_{2},\theta_{t})$

In this scenario, the black-box distinguisher considers the reported
randomized gradient as $g_{1}$ if

$\delta(x_{1})\geq\delta(x_{2})\ \text{where}\
\delta(x)=|f(x;\theta_{t+1})-f(x;\theta_{t})|.$ (6)

otherwise $g_{2}$.

Input perturbation. This scenario assumes that the crafter produces malicious
input data via perturbations. The crafter adds perturbation to the data
$x_{1}$ to make it easier to distinguish the gradient. Although many studies
have proposed perturbation algorithms [38, 33, 39, 6, 13], we adopted the FGSM
(Fast Gradient Sign Method) [16], a well-known method for adversarial
perturbations. For an input image, FGSM uses the gradients of the loss with
respect to the input image to create a new image that maximizes the loss. Let
$x_{2}$ be an adversary pertubed image crafted as $x_{2}=x_{1}+\alpha\
\text{sgn}(\nabla_{x_{1}}f(x_{1};\theta_{t}))$ 111We set $\alpha=1$..

Parameter retrogression. Let us assume that the crafter has maliciously
manipulated the parameters [35]. Generating a gradient from manipulated
parameters results in a significant difference in norm compared to generating
it from benign parameters. This setup suggests the ease of distinguishing
between two gradients with very different norms. Let $\theta_{t}^{\prime}$ be
the parameter updated in the direction of increasing $x_{1}$ loss as
$\theta_{t}^{\prime}=\theta_{t}+\alpha\ \nabla f(x_{1};\theta_{t})$. Generate
gradients $g_{1}$ from the benign parameter $\theta_{t}$ and $g_{2}$ from the
retrograded parameter $\theta_{t}^{\prime}$.

$\displaystyle g_{1}=\nabla f(x_{1},\theta_{t});$ $\displaystyle g_{2}=\nabla
f(x_{1},\theta_{t}^{\prime})$

Gradient flip. In this setting, the crafter processes the raw gradient. The
simplest method of processing a gradient to increase its discriminability is
to flip the gradient sign [35]. As described in Section 2.2, in the random
gradient sampling of LDP-SGD, when $\varepsilon$ is set large, the sign of the
gradient is unlikely to change, so we argue that such processing is effective.
The crafter uses the global model $\theta_{t}$ distributed by the model
trainer to generate gradients $g_{1}$ from the image $x_{1}$. Let $g_{2}$ be a
gradient with the sign of $g_{1}$ flipped.

$\displaystyle g_{1}=\nabla f(x_{1},\theta_{t});$ $\displaystyle g_{2}=-g_{1}$

Collusion. We here consider distributing a malicious model from the server to
the clients. As explained in Section 2.2, in the gradient norm projection of
LDP-SGD, the smaller the norm of the raw gradient, the easier it is for the
sign to be flipped. Taking advantage of this property, we consider a setting
where the crafter and the model trainer collude to make generating a gradient
with a small norm challenging. With this setting, the model trainer
intentionally creates a global model with a massive loss and distributes it to
the crafter. The crafter flips a gradient in the same way as the gradient
flipping. Thus the gradient $g_{2}$ is generated as $g_{2}=-g_{1}$. As a
realization of this adversary, we introduce the following procedure. First the
model trainer generates a malicious global model $\tilde{\theta}_{t}$ from
only images with the same label and distribute it to the crafter. Second, the
crafter utilizes the malicious model $\tilde{\theta}_{t}$ to generate
gradients $g_{1}$ from the image $x_{1}$. The label of $x_{1}$ is different
from the label of the images used to generate the malicious model.

$\displaystyle g_{1}=\nabla f(x_{1},\tilde{\theta}_{t});$
$\displaystyle\textrm{where }\tilde{\theta}_{t}\textrm{ is a malicious
model.}$

As well as the gradient flip, the adversary craft $g_{2}$ by flipping $g_{1}$.

Dummy gradient. Here, we consider that the crafter produces a dummy gradient.
LDP-SGD includes the gradient norm projection, which causes errors due to
randomly flipping gradients. The intuition here is to craft a dummy gradient
that never cause such errors. The simplest way to do this is to generate a
gradient with a large norm, regardless of the image or model the crafter has.
To craft the dummy gradient, we simply fill a constant $\lambda$ into all the
elements of the gradient as:

$\displaystyle g_{1}=(\lambda,\lambda,\dots,\lambda);$

The norm of $g_{1}$ must be greater than or equal to the clipping threshold
$L$ to avoid the gradient norm projection. Therefore, let $\lambda$ be
$L/\sqrt{d}$ and $d$ be the dimension of the gradient. For another choice of
the gradient, we also employ the gradient flipping to maximize the difference
against the dummy gradient. Thus the gradient $g_{2}$ is generated as
$g_{2}=-g_{1}$ as well. In this scenario, the black-box distinguisher
considers the reported randomized gradient as $g_{1}$ if

$\sum_{i\in[d]}\text{sgn}(\theta^{i}_{t+1}-\theta^{i}_{t})\geq 0,$ (7)

otherwise $g_{2}$. This is due to that the crafter produces the dummy gradient
$g_{1}$ by filling the positive constant. The combination of crafting the
dummy gradient and flipping it is a worst-case attack for the LDP adversary.
We give a proof below.

###  3.5 Analysis of the Worst-case Attack

In the above adversary instatiations with the crafter and the distinguisher,
we can find a worst-case attack in FL using LDP-SGD. About the worst-case, we
meet the following proposition.

######  Proposition 1.

The white-box distinguisher with the crafter producing a raw gradient whose
$\ell_{2}$-norm is larger than or equal to $L$ is a worst-case attack reaching
the theoretical upper bound given by $\varepsilon$.

###### Proof.

Recall that in LDP-SGD, the direction is reversed depending on the gradient
norm and $\varepsilon$. First, since the sign is easily flipped when the norm
of the gradient is small in the gradient norm projection, the norm of the
gradient must be greater than or equal to $L$. Hereafter, we assume that $g$
is a gradient with norm $L$. Let $g_{\text{flip}}$ be the flipped gradient of
$g$, $\tilde{g}$ and $\tilde{g}_{\text{flip}}$ be the outputs of the random
gradient sampling, respectively. With probability of
$\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$, the following equation holds on
line 3.

$\displaystyle g\cdot\tilde{g}\geq 0$ $\displaystyle\quad
g_{\text{flip}}\cdot\tilde{g}_{\text{flip}}\geq 0$

Let $\tilde{g}_{\text{target}}$ be the gradient randomized of either $g$ or
$g_{\text{flip}}$ with probability of $50\%$. Let us predict what
$g_{\text{target}}$ be. The case can be divided by the cosine similarity
between $\tilde{g}_{\text{target}}$ and $g$ as follows:

$\displaystyle cos(\tilde{g}_{\text{target}},g)\geq 0$
$\displaystyle\Rightarrow$
$\displaystyle\begin{cases}g_{\text{target}}\textrm{ was }g\textrm{ and
}g\textrm{ rotation was within 90 degrees.}&\textrm{ w.p.
}\frac{1}{2}\cdot\frac{e^{\varepsilon}}{1+e^{\varepsilon}}\\\
g_{\text{target}}\textrm{ was }g_{\text{flip}}\textrm{ and
}g_{\text{flip}}\textrm{ rotation was over 90 degrees.\;\;}&\textrm{ w.p.
}\frac{1}{2}\cdot\frac{1}{1+e^{\varepsilon}}\end{cases}$ $\displaystyle
cos(\tilde{g}_{\text{target}},g)\leq 0$ $\displaystyle\Rightarrow$
$\displaystyle\begin{cases}g_{\text{target}}\textrm{ was }g\textrm{ and
}g\textrm{ rotation was over 90 degrees.}&\textrm{w.p.
}\frac{1}{2}\cdot\frac{1}{1+e^{\varepsilon}}\\\ g_{\text{target}}\textrm{ was
}g_{\text{flip}}\textrm{ and }g_{\text{flip}}\textrm{ rotation was within 90
degrees.}&\textrm{w.p.
}\frac{1}{2}\cdot\frac{e^{\varepsilon}}{1+e^{\varepsilon}}\end{cases}$

White-box distinguisher predicts $g$ for the original data of
$\tilde{g}_{\text{target}}$ when the cosine similarity between $g$ and
$\tilde{g}_{\text{target}}$ is positive, then the prediction is correct with
probability $\frac{1}{2}\cdot\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$.
Likewise, white-box distinguisher predicts $g_{\text{flip}}$ for the original
data of $\tilde{g}_{\text{target}}$ when the cosine similarity between $g$ and
$\tilde{g}_{\text{target}}$ is negative, then the prediction is correct with
probability $\frac{1}{2}\cdot\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$.
Therefore, white-box distinguisher can distinguish $g$ and $g_{\text{flip}}$
with probability $\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$. ∎

##  4 Numerical Observations

Here, we address an experimental study to observe numerical results of our LDP
tests in FL.

###  4.1 Experimental Setup

For each adversary instantiations listed in Table 1, we run ten measurements
and average over these measurement results. Each measurement consists of
$K$=10,000 trials by each distinguisher.

Hyper-parameters. We have implemented our algorithms in Pytorch. For each
dataset, we used cross-entropy as loss function. We used three layers
convolutional neural network for all datasets. To train the models, we use
LDP-SGD [10] with clipping norm size $L$=1. Guaranteed privacy level
$\varepsilon$ is set to 0.5, 1.0, 2.0 and 4.0.

Datasets. We perform experimental evaluations on four datasets, namely MNIST
[26], CIFAR-10 [25], Fashion-MNIST [41] and SVHN [37]. Detail results of
CIFAR-10, Fashion-MNIST and SVHN are in Appendix.

(a) Benign setting

(b) Image perturbation

(c) Parameter retrogression

(d) Gradient flip

(e) Collusion

(f) Dummy gradient

Figure 2: The empirical privacy in federated learning. (MNIST)

###  4.2 Observations of Empirical LDP

Figure 2 shows the measured $\varepsilon$ ($\varepsilon_{\text{empirical}}$)
by our LDP test varying the privacy parameter $\varepsilon$.

Benign. In this most realistic setting, even if we set $\varepsilon=4$, the
empirical privacy strength is $0.94$, and the gap between the theoretical and
the empirical is large. (Figure 2(a)) $\varepsilon_{\text{empirical}}=0.94$ is
equivalent to about $68.1\%$ in terms of the identifiable probability. White-
box distinguisher has a higher $\varepsilon_{\text{empirical}}$ than black-box
distinguisher. Therefore it is easier to determine the randomized gradient
$\tilde{g}$ itself than the parameter $\theta_{t+1}$ updated with the
randomized gradient $\tilde{g}$.

Input perturbation. From Figure 2(b), the probability of discrimination does
not increase even if the gradient of the perturbed image is randomized. The
gap between empirical and theoretical privacy strength in this setting is more
expansive than in the benign setting. Therefore, even if the image changes
slightly due to perturbation, the gradient will not be easy to distinguish.

Parameter retrogression. In this setup, we use a nonmalicious gradient $g_{1}$
and a $g_{2}$ generated from parameters that have been processed to increase
loss. Since the norm of $g_{2}$ is larger than the norm of $g_{1}$, we assume
that discrimination would be easier if it were not randomized. However, Figure
2(c) shows that the gradient norm has a negligible effect on the
discrimination probability. This result is that in LDP-SGD, gradient clipping
keeps large normed gradients below a threshold.

Gradient flip. The measured $\varepsilon$ is shown in Figure 2(d).
Discriminability was improved compared to the benign setting when the crafter
flipped the gradient sign. In particular, when $\varepsilon=4$,
$\varepsilon_{\text{empirical}}$ shows 3.99, almost a theoretical value in
white-box distinguisher. As shown in the worst-case proof, LDP-SGD keeps the
direction roughly proportional to the guaranteed $\varepsilon$, so $g_{1}$ and
$g_{2}$, which reverses the sign of $g_{1}$, are easy to distinguish.

Collusion. The experimental results in Figure 2(e) show that the collusion
between the crafter and the model trainer narrows the gap between theoretical
privacy and empirical privacy compared to the gradient flipping. In white-box
distinguisher of this setting, the empirical $\varepsilon$ reached the
theoretical value at all the setting values $\varepsilon=0.5,1,2,4$.
$\varepsilon_{\text{empirical}}=4.07$ has the same meaning as successful
discrimination with a probability of about $98.2\%$. In the black-box setting,
this collusion increased the empirical LDP against the weaker settings
described in the above paragraphs.

Dummy gradient. From Figure 2(f), as with the collusion, this setting
increases the probability of gradient discrimination. Figure 4 shows the
effect of the norm on the discrimination probability: even with a dummy
gradient, if the norm is smaller than the clipping size $L$, the gap between
the theoretical and measured $\varepsilon$ becomes larger. Daring to generate
the dummy gradients with large norm is not common in FL. However, it is clear
that maximizing the norm of the gradient and sign flipping is the strongest
attack.

Summary of Results. Figure 1(b), 4(a), and 4(b) summarizes the results for
each dataset. Over the four datasets, adversaries who directly manipulate raw
gradients can reach the theoretical upper bounds given by the privacy
parameter $\varepsilon$. Even in white-box scenarios, adversaries who only
access the input data and parameters but not the raw gradient have limited
capability. Moreover, adversaries who only refer to the updated model but not
any randomized gradient (i.e., black-box scenarios) have the limited
capability, collusion with the server employing the malicious model, increases
the adversary’s capability in the black-box setting.

Figure 3: Effect of gradient norm.

(a) Black-box

(b) White-box

Figure 4: Summary of results in four datasets.

###  4.3 Discussion towards Relaxations of Privacy Parameters

The white-box test resulted in tightly close to the theoretical bound defined
by the privacy parameters $\varepsilon$. While the black-box test demonstrated
stronger privacy levels that were far from the bound. To prevent the white-box
attacks, we can install a secure aggregator based on such as multi-party
computations and trusted execution environments (TEEs) [31, 7]. Using such
secure aggregators for updating the global model, the process from reporting
gradients to updating the global model is fully encrypted. The experimental
results above do not allow any relaxation only with local randomizers, but
with shuffler [4, 9, 12, 28] or aggregator implemented by such secure
computations [5, 24], relaxation of $\varepsilon$ can be reasonable in the
view of empirical privacy risks. Even when the shuffler is untrusted and the
gradient is randomized with a relaxed privacy parameter (like
$\varepsilon=8$), the empirical privacy risk against the shuffler might not be
significant (like $\varepsilon_{\text{empirical}}=1$). Another possible way is
to prohibit gradient poisoning. As shown in the experiments, without directly
manipulating gradients, the empirical privacy is significantly far from the
given privacy bound. If the range of possible input training data is limited,
we can introduce out-of-distribution detectors before randomizing raw
gradients. In other words, by adding some restrictions to the crafter, the
model trainer, and the distinguisher, it may also be possible to relax
$\varepsilon$.

##  5 Conclusion

We introduced the empirical privacy test by measuring the lower bounds of LDP.
We then instantiated six adversaries in FL under LDP to measure empirical LDP
at various attack surfaces, including the worst-case attack that reached the
theoretical upper bound of LDP. We also demonstrated numerical observations of
the measured privacy in these adversarial settings. In the end, we discussed
the possible relaxation of privacy parameter $\varepsilon$ with using a
trusted entity.

## References

  * Abadi et al. [2016] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pages 308–318, 2016.
  * Bassily et al. [2014] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pages 464–473. IEEE, 2014.
  * Bhowmick et al. [2018] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers.  Protection against reconstruction and its applications in private federated learning.  _arXiv preprint arXiv:1812.00984_ , 2018.
  * Bittau et al. [2017] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld.  Prochlo: Strong privacy for analytics in the crowd.  In _Proceedings of the 26th Symposium on Operating Systems Principles_ , pages 441–459, 2017.
  * Bonawitz et al. [2017] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth.  Practical secure aggregation for privacy-preserving machine learning.  In _proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , pages 1175–1191, 2017.
  * Carlini and Wagner [2017] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In _Proceedings of the 10th ACM workshop on artificial intelligence and security_ , pages 3–14, 2017.
  * Costan and Devadas [2016] Victor Costan and Srinivas Devadas.  Intel sgx explained.  _Cryptology ePrint Archive_ , 2016.
  * Duchi et al. [2018] John C Duchi, Michael I Jordan, and Martin J Wainwright.  Minimax optimal procedures for locally private estimation.  _Journal of the American Statistical Association_ , 113(521):182–201, 2018.
  * Erlingsson et al. [2019] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2468–2479. SIAM, 2019.
  * Erlingsson et al. [2020] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta.  Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.  _arXiv preprint arXiv:2001.03618_ , 2020.
  * Evfimievski et al. [2003] Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant.  Limiting privacy breaches in privacy preserving data mining.  In _Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 211–222, 2003.
  * Feldman et al. [2022] Vitaly Feldman, Audra McMillan, and Kunal Talwar.  Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 954–964. IEEE, 2022.
  * Ford et al. [2019] Nic Ford, Justin Gilmer, Nicolas Carlini, and Dogus Cubuk.  Adversarial examples are a natural consequence of test error in noise.  _arXiv preprint arXiv:1901.10513_ , 2019.
  * Geiping et al. [2020] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller.  Inverting gradients-how easy is it to break privacy in federated learning?  _Advances in Neural Information Processing Systems_ , 33:16937–16947, 2020.
  * Girgis et al. [2021] Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh.  Shuffled model of differential privacy in federated learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2521–2529. PMLR, 2021.
  * Goodfellow et al. [2014] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Gu et al. [2017] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  _arXiv preprint arXiv:1708.06733_ , 2017.
  * Hoshino [2020] Nobuaki Hoshino.  A firm foundation for statistical disclosure control.  _Japanese Journal of Statistics and Data Science_ , 3, 08 2020.  doi: 10.1007/s42081-020-00086-9.
  * Jagielski et al. [2020] Matthew Jagielski, Jonathan Ullman, and Alina Oprea.  Auditing differentially private machine learning: How private is private sgd?  _Advances in Neural Information Processing Systems_ , 33:22205–22216, 2020.
  * Jayaraman and Evans [2019] Bargav Jayaraman and David Evans.  Evaluating differentially private machine learning in practice.  In _28th USENIX Security Symposium (USENIX Security 19)_ , pages 1895–1912. USENIX Association, 2019.
  * Kairouz et al. [2015] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  In _International conference on machine learning_ , pages 1376–1385. PMLR, 2015.
  * Kairouz et al. [2021] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Kasiviswanathan et al. [2011] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  _SIAM Journal on Computing_ , 40(3):793–826, 2011\.
  * Kato et al. [2022] Fumiyuki Kato, Yang Cao, and Masatoshi Yoshikawa.  Olive: Oblivious and differentially private federated learning on trusted execution environment.  _arXiv preprint arXiv:2202.07165_ , 2022.
  * [25] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-10 (canadian institute for advanced research).  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * LeCun and Cortes [2010] Yann LeCun and Corinna Cortes.  MNIST handwritten digit database.  2010\.  URL http://yann.lecun.com/exdb/mnist/.
  * Lee and Clifton [2011] Jaewoo Lee and Chris Clifton.  How much is enough? choosing $\varepsilon$ for differential privacy.  In _International Conference on Information Security_ , pages 325–340. Springer, 2011.
  * Liew et al. [2022] Seng Pei Liew, Tsubasa Takahashi, Shun Takagi, Fumiyuki Kato, Yang Cao, and Masatoshi Yoshikawa.  Network shuffling: Privacy amplification via random walks.  _arXiv preprint arXiv:2204.03919_ , 2022.
  * Liu et al. [2019] Changchang Liu, Xi He, Thee Chanyaswad, Shiqiang Wang, and Prateek Mittal.  Investigating statistical privacy frameworks from the perspective of hypothesis testing.  _Proceedings on Privacy Enhancing Technologies_ , 2019:233–254, 07 2019.  doi: 10.2478/popets-2019-0045.
  * Liu et al. [2020] Ruixuan Liu, Yang Cao, Masatoshi Yoshikawa, and Hong Chen.  Fedsel: Federated sgd under local differential privacy with top-k dimension selection.  In _International Conference on Database Systems for Advanced Applications_ , pages 485–501. Springer, 2020.
  * McKeen et al. [2013] Frank McKeen, Ilya Alexandrovich, Alex Berenzon, Carlos V Rozas, Hisham Shafi, Vedvyas Shanbhogue, and Uday R Savagaonkar.  Innovative instructions and software model for isolated execution.  _Hasp@ isca_ , 10(1), 2013.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Moosavi-Dezfooli et al. [2016] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  Deepfool: a simple and accurate method to fool deep neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2574–2582, 2016.
  * Murakonda and Shokri [2020] Sasi Kumar Murakonda and Reza Shokri.  Ml privacy meter: Aiding regulatory compliance by quantifying the privacy risks of machine learning.  _arXiv preprint arXiv:2007.09339_ , 2020.
  * Nasr et al. [2019] Milad Nasr, Reza Shokri, and Amir Houmansadr.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In _2019 IEEE symposium on security and privacy (SP)_ , pages 739–753. IEEE, 2019.
  * Nasr et al. [2021] Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin.  Adversary instantiation: Lower bounds for differentially private machine learning.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , pages 866–882. IEEE, 2021.
  * Netzer et al. [2011] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  2011\.  URL http://ufldl.stanford.edu/housenumbers.
  * Papernot et al. [2016] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami.  The limitations of deep learning in adversarial settings.  In _2016 IEEE European symposium on security and privacy (EuroS &P)_, pages 372–387. IEEE, 2016.
  * Papernot et al. [2017] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami.  Practical black-box attacks against machine learning.  In _Proceedings of the 2017 ACM on Asia conference on computer and communications security_ , pages 506–519, 2017.
  * Song et al. [2013] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate.  Stochastic gradient descent with differentially private updates.  In _2013 IEEE Global Conference on Signal and Information Processing_ , pages 245–248. IEEE, 2013.
  * Xiao et al. [2017] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ , 2017.  URL https://github.com/zalandoresearch/fashion-mnist.
  * Yeom et al. [2018] Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha.  Privacy risk in machine learning: Analyzing the connection to overfitting.  In _2018 IEEE 31st computer security foundations symposium (CSF)_ , pages 268–282. IEEE, 2018.
  * Yin et al. [2021] Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M Alvarez, Jan Kautz, and Pavlo Molchanov.  See through gradients: Image batch recovery via gradinversion.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 16337–16346, 2021.

##  Appendix A Experimental Details

This appendix provides details of the setup and additional experimental
results.

###  A.1 Experimental Setup

Datasets. We run experiments on four datasets:

  * •

MNIST: We use the MNIST image dataset, which consists of 28$\times$28
handwritten grayscale digit images, and the task is to recognize the 10 class
digits.

  * •

CIFAR-10: We use CIFAR10, a standard benchmark dataset consisting of
32$\times$32 RGB images. The learning task is to classify the images into ten
classes of different objects.

  * •

Fashion-MNIST: Each example of Fashion-MNIST is a 28$\times$28 grayscale image
associated with a label from 10 classes.

  * •

SVHN: This dataset is obtained from house numbers in Google Street View
images. SVHN consists of 32$\times$32 RGB images, and the task is to recognize
the 10 class digits.

Neural Network Architecture. The neural network we use in the experiments is
as in Table 3.

Table 2: Neural network architecture in measurements. Layer | Parameters
---|---
Convolution | 16 filters of 8$\times$8, strides 2
Max-Pooling | 2$\times$2 window, strides 2
Convolution | 32 filters of 4$\times$4, strides 2
Max-Pooling | 2$\times$2 window, strides 2
Linear | 32 units
Softmax | 10 units

Table 3: The black-box test for multiple clients in the benign crafter. (MNIST) Number of clients | Measured $\varepsilon$
---|---
1 | 0.12
2 | 0.07
4 | 0.06
10 | 0.06

###  A.2 Additional Observations

Dataset Perspectives. Figure 5, 6 and 7 show that the empirical privacy in
federated learning in CIFAR-10, Fashion-MNIST, and SVHN datasets. The
observation of $\varepsilon_{\text{empirical}}$ using four datasets shows that
$\varepsilon_{\text{empirical}}$ is data-independent and has a similar trend.
As in Section 4.2, the white-box LDP test is more potent than the black-box
LDP test. Furthermore, the craft of dummy gradients is closest to the
theoretical $\varepsilon$.

White-box test showed higher $\varepsilon_{\text{empirical}}$ than black-box
test. This is a natural result in black-box scenarios since the model trainer
aggregate gradients such as averaging, learning rate multiplication, and
$\ell_{2}$-projection. The more clients used to update parameters in FL, the
more pronounced this trend becomes. Table 3 shows that the black-box test for
multiple clients becomes more difficult as the number of clients increases.

Input perturbation and parameter retrogression were not successful. As
mentioned in Section 2.2, LDP-SGD includes the clipping gradient and the
random gradient sampling. The clipping gradient ignores large differences
between the norms of $g_{1}$ and $g_{2}$. Furthermore, the random gradient
sampling rotates the gradient by at most 90 degrees, so any slight difference
in the direction of $g_{1}$ and $g_{2}$ is ignored.

(a) Benign setting

(b) Image perturbation

(c) Parameter retrogression

(d) Gradient flip

(e) Collusion

(f) Dummy gradient

Figure 5: The empirical privacy in federated learning. (CIFAR-10)

(a) Benign setting

(b) Image perturbation

(c) Parameter retrogression

(d) Gradient flip

(e) Collusion

(f) Dummy gradient

Figure 6: The empirical privacy in federated learning. (Fashion-MNIST)

(a) Benign setting

(b) Image perturbation

(c) Parameter retrogression

(d) Gradient flip

(e) Collusion

(f) Dummy gradient

Figure 7: The empirical privacy in federated learning. (SVHN)


# Infomap Bioregions 2 - Exploring the interplay between biogeography and
evolution

Daniel Edler  Corresponding author<EMAIL_ADDRESS>Integrated Science
Lab, Department of Physics, Umeå University, Umeå, Sweden Gothenburg Global
Biodiversity Centre, University of Gothenburg, Gothenburg, Sweden Department
of Biological and Environmental Sciences, University of Gothenburg,
Gothenburg, Sweden Anton Holmgren  Integrated Science Lab, Department of
Physics, Umeå University, Umeå, Sweden Alexis Rojas  Integrated Science Lab,
Department of Physics, Umeå University, Umeå, Sweden Department of Computer
Science, University of Helsinki, Finland Joaquín Calatayud  Department of
Biology, Geology, Physics and Inorganic Chemistry, King Juan Carlos
University, Madrid, Spain Martin Rosvall  Integrated Science Lab, Department
of Physics, Umeå University, Umeå, Sweden Alexandre Antonelli  Gothenburg
Global Biodiversity Centre, University of Gothenburg, Gothenburg, Sweden
Department of Biological and Environmental Sciences, University of Gothenburg,
Gothenburg, Sweden Department of Biology, University of Oxford, Oxford, United
Kingdom Royal Botanical Gardens Kew, Richmond, Surrey, United Kingdom

###### Abstract

Identifying and understanding the large-scale biodiversity patterns in time
and space is vital for conservation and addressing fundamental ecological and
evolutionary questions. Network-based methods have proven useful for
simplifying and highlighting important structures in species distribution
data. However, current network-based biogeography approaches cannot exploit
the evolutionary information available in phylogenetic data. We introduce a
method for incorporating evolutionary relationships into species occurrence
networks to produce more biologically informative and robust bioregions. To
keep the bipartite network structure where bioregions are grid cells
indirectly connected through shared species, we incorporate the phylogenetic
tree by connecting ancestral nodes to the grid cells where their descendant
species occur. To incorporate the whole tree without destroying the spatial
signal of narrowly distributed species or ancestral nodes, we weigh tree nodes
by the geographic information they provide. For a more detailed analysis, we
enable integration of the evolutionary relationships at a specific time in the
tree. By sweeping through the phylogenetic tree in time, our method
interpolates between finding bioregions based only on distributional data and
finding spatially segregated clades, uncovering evolutionarily distinct
bioregions at different time slices. We also introduce a way to segregate the
connections between evolutionary branches at a selected time to enable
exploration of overlapping evolutionarily distinct regions. We have
implemented these methods in Infomap Bioregions, an interactive web
application that makes it easy to explore the possibly hierarchical and fuzzy
patterns of biodiversity on different scales in time and space.

##  1 Introduction

Biogeographical regions, bioregions for short, disclose the organization of
life. They reveal how species are spatially grouped at large spatial scales
and are important units for understanding historical biogeography, ecology,
and evolution. They also identify units of biodiversity with potentially high
conservation value [22].

There are two main data-driven approaches to identifying bioregions from
spatial species occurrence data: similarity-based[14, 13] and network-based
[21, 6]. Similarity-based approaches group grid cells with similar sets of
species. Some generalizations include phylogenetic similarity between species
[3, 17, 16]. However, while similarity-based methods are simple to interpret,
they require all grid cells to be similar in a bioregion. Therefore, they
cannot capture regions with a spatial gradient of species – where each pair of
neighboring grid cells have a large overlap of species but two grid cells
further apart have low overlap – often with arbitrary boundaries somewhere
along the gradient [21]. They also require choosing key parameters that can
strongly influence the results, such as similarity measures, thresholds, and
tie-breaking [1]. Therefore, researchers have looked for other approaches to
find robust and biologically realistic bioregions.

Network-based methods uncover bioregions from species distribution data by
first binning all species into spatial grid cells, typically one-by-one
degree, which is approximately 100-by-100 km at the Equator, or finer scales
when there is sufficient data. Then, grid cells and species are represented as
a bipartite network, with links between species and grid cell nodes specifying
occurrences. A link signifies that a species has been recorded in the cell,
typically by a collected and geo-referenced specimen in a natural history
collection or based on verified observations. In most cases, such a network
will have a modular structure: nodes with a relatively high density of links
among themselves form communities, identified with community-detection
algorithms. In species occurrence networks, communities correspond to areas
with more shared species within than between them. Each community contains
grid cells and species, and the grid cells assigned to the same community form
a bioregion. One can project the bipartite network to a unipartite network
consisting of only grid cells by replacing links to the same species with a
direct link between grid cells. Such a projection can also provide
interpretable communities but seem to distort information in the underlying
data [20].

Network-based methods overcome the similarity-based gradient problem[21]. They
recognize that occupancy histories of species exhibit varying shapes[11] and
thus, individual species have a different contribution to the overall
biogeographic structure. However, current network approaches still ignore the
evolutionary relations between species by treating two species within the same
genus and two from different families, regardless of their unique evolutionary
histories. This has potential consequences for the network-delineated
biogeographic structure. For example, common differences in taxonomic
classification based on different views or methods to determine which groups
of organisms should be considered the same or different species (the so-called
lumper-splitter problem) can harm the result [8], and sparse occurrence data
may lead to fragmented maps. By discarding vital biodiversity knowledge on
evolutionary relationships and relying on fluid species boundaries, we limit
bioregions’ value for understanding large-scale biodiversity patterns and
conservation planning.

To overcome these limitations, we introduce a method for incorporating
evolutionary relationships into species occurrence networks to produce more
biologically realistic, data-rich, and robust bioregions. We find that
integrating information about the phylogenetic tree uncovers evolutionarily
more distinct and robust bioregions.

##  2 Material and Methods

To delineate bioregions from species occurrence data, we represent the data as
a network with links between species and the grid cells where they occur.
Using a network community detection algorithm, we partition the network into
optimal modules (Fig. 1(a)). Bioregions are defined as grid cells belonging to
the same module. As the network contains two types of nodes and links always
connect species to grid cells, never species to species or grid cells to grid
cells, the network is bipartite. The bipartite structure is essential for
modules to be interpreted as areas with more shared species within than
between them. Here we extend this method to detect bioregions not only based
on shared species but also shared ancestry.

The evolutionary relations between species are represented with a fully
dichotomous, ultrametric tree structure derived from a phylogenetic inference.
Branch lengths are normally provided as absolute time resulting from a
divergence time analysis but could be relative to the total tree height.

We introduce a way to integrate the full phylogenetic tree and two
complementing ways of including the tree at a specific time for further
analysis.

### Integrating the whole phylogenetic tree

To form bioregions connected not only by shared species but by shared
evolutionary histories, we connect each ancestral node in the phylogenetic
tree to the grid cells where its descendant species occur. As ancestral nodes
further back in time connect to more and more grid cells, they will quickly
make the network too dense to find any modules. To solve this, we down-weight
links from ancestral nodes based on how much spatial information they give
(Fig. 1(b)). If tree node $i$ is connected to $k_{i}$ grid cells out of $K$
total grid cells, we weigh the links from tree node $i$ to all connected grid
cells by

$w_{i}=1-\frac{\log k_{i}}{\log K}.$

This gives zero weight to ancestral nodes that exist in all grid cells and
weight $1$ to all that exists in a single grid cell. As we do not weigh
species by abundances in each grid cell, the $\log k_{i}$ can be interpreted
as the entropy or uncertainty in knowing from which grid cell a selected
species occurrence comes, with $\log K$ being the max uncertainty used for
normalization.

### Integrating ancestral nodes for mapping the evolution of bioregions

((a))

((b))

((c))

((d))

Figure 1: Community detection in bipartite occurrence networks including
evolutionary relationships. To find biogeographical regions that capture the
spatial structuring of species, we apply community detection on the bipartite
network composed of species linked to grid cells where they occur. Grid cells
are indirectly connected through shared species (a). The two bottom grid cells
end up in different bioregions because of no shared species. By connecting
each ancestral node in a phylogenetic tree to the grid cells where its
descendant species occur, weighted by their spatial information, we can form
bioregions connected not only by shared species but by shared evolutionary
history (b). We can indirectly connect grid cells by their shared ancestry at
a selected time (c)-(d) for a more detailed analysis. With a recent time, we
can use it to solve fragmented bioregions due to sparse data and make it
robust against shifting taxonomic resolutions due to the so-called lumper-
splitter problem. We uncover unique bioregions by sweeping the selected
integration point back in time.

To explore the effect of integrating species relationships in more detail to
uncover evolutionarily unique bioregions, we introduce a way to integrate the
tree at a selected point in time (Fig. 1c-d). To keep a constant weight from
the tree as we explore different selected times of integration, we do not
weigh links from ancestral nodes by their geographic information but instead
by a selected relative tree strength compared to the species nodes of the
network without any tree data. The aim is to sweep through the selected time
of integration from recent to old while keeping a selected fixed balance
between the strength of the ancestral nodes and the strength of the species
nodes. As older ancestral nodes are more well-connected, the links from
ancestral nodes will be down-weighted to keep a fixed total weight. However,
any specific time point usually cuts the tree’s branches instead of landing at
specific ancestral nodes. Below we describe how to solve this by splitting the
link weights between the parent and child nodes of each cut branch such that
the relative strength between them matches their relative distance to the
selected time, with the strength of a node being the sum of link weights
connected to that node.

As a parent node may be connected to more grid cells than the child node, we
cannot directly split the weights using the relative time between them. When a
branch from parent to child is cut at a relative time $t$ going from $0$ at
the parent to $1$ at the child, we weigh the links linearly with $t$. If the
number of links of the parent and child node is $k_{p}$ and $k_{c}$, the
strength of the parent and child nodes are $s_{p}=k_{p}(1-t)$ and
$s_{c}=k_{c}t$ respectively. With the relative degree $k_{p/c}=k_{p}/k_{c}$,
the relative strength of the parent node at $t$ is

$s_{p/c}(t)=\frac{k_{p}(1-t)}{k_{c}t}=k_{p/c}\frac{(1-t)}{t}.$

To interpolate linearly between parent and child strength, we can use an
adjusted time $t^{\prime}$ to cancel the bias $k_{p/c}$

$t^{\prime}=\frac{tk_{p/c}}{1+t(k_{p/c}-1)}$

such that

$k_{p/c}\frac{(1-t^{\prime})}{t^{\prime}}=\frac{(1-t)}{t}.$

After weighting the links for parent and child nodes with $1-t^{\prime}$ and
$t^{\prime}$, the total strength of all included tree nodes is $s_{t}$. With
the total strength from the species nodes without the tree $s_{s}$, we rescale
all links from the tree nodes with a factor $w_{t}$. This gives the total
strength $s^{\prime}_{t}=w_{t}s_{t}$ such that the relative strength of the
tree is the specified value $s_{t/s}=s^{\prime}_{t}/(s^{\prime}_{t}+s_{s})$.
Solving for $w_{t}$ gives

$w_{t}=\frac{s_{t/s}s_{s}}{s_{t}(1-s_{t/s})}.$

While this approach uncovers evolutionarily largely unique bioregions, such as
islands or mountain ranges, the typical spatial overlap between evolutionary
branches amplifies the problem in current network-based methods to handle
evolutionary transition zones with overlapping ecosystems. As grid cells are
forced to be part of only a single bioregion, grid cells in a transition zone
are either grouped to their bioregion, arbitrarily assigned to one of the
neighboring regions, or collapsed with the neighboring regions into one
bioregion, leading to underfitting. As we extend the integration time, we
include ancestral nodes with increasing spatial overlap. This tends to
collapse modular structures. To overcome this, we need a way to find
overlapping bioregions.

### Segregating evolutionary history for mapping overlapping evolutionarily
distinct bioregions

By integrating tree nodes further and further back in time, we retain
evolutionarily unique bioregions and map selected divergence events. However,
evolutionary branches often overlap spatially, so ancestral nodes increase the
indirect links between bioregions, eventually collapsing them into large
regions (Fig. 1(d)).

Using the map equation framework for network community detection [5], we can
find overlapping evolutionary distinct bioregions using higher-order networks
[4]. The map equation is based on a dynamic approach to community detection,
where modules capture the flow patterns on top of a network – modeled by the
relative abundance of stationary visit rates of a random walk. The random
walker moves between nodes, at each step moving to a random neighboring node
proportional to the weight of that link. As the probability distribution for
the next node only depends on the current node, this is a memoryless first-
order Markov process. Higher-order Markov processes depend on one or more
previous nodes in the sequence. A higher-order model in the map equation
framework is represented by a first-order random walk on state nodes, where
each state node belongs to one physical node. A state node represents the
memory of previous steps. A physical node can overlap modules by partitioning
the state nodes into different modules.

((a))

((b))

Figure 2: Mapping overlapping evolutionary distinct bioregions. We use a
higher-order network with state nodes within grid cells to segregate
connections to species within the same evolutionary branch up to a selected
time. State nodes represent evolutionary memory: when we follow a link from a
species or ancestral node to a grid cell, it forces us to go back to a random
species or ancestral node with shared memory. On a state-node level, this
gives evolutionarily distinct bioregions. On a physical grid-cell level, this
enables the bioregions to overlap in space. By combining it with integrating
the tree at a selected time, we can explore evolutionarily unique regions with
higher resolution, as spatially overlapping branches may be kept segregated.

To distinguish the geographic patterns from distinct branches when connecting
species to grid cells, we employ a second-order model on the grid cells to
remember which evolutionary branch at a selected time each species belongs. We
represent this evolutionary memory with state nodes within grid cells, one
state node for the parent and one for the child node of the branch cut by the
selected segregating time (Fig. 2). Each link is then divided into two links
connecting grid cells to species and ancestral nodes, with link weights
distributed relative to the time at the cut between parent and child nodes.
When ancestral nodes are included, the links are aggregated from their
descendant species on the memory nodes. If the ancestral nodes are closer in
time to the species nodes than the segregating time, all network flows are
completely segregated within the respective evolutionary branch at the cut. By
increasing the integration time so that ancestral nodes further away than the
segregation time are included, they bridge segregated branches that descend
from them and possibly connect nodes from them into the same module. By
detecting communities in the state network, each grid cell’s state nodes will
belong to a module corresponding to an evolutionarily distinct bioregion. Each
grid cell may have multiple state nodes, so each can belong to multiple
overlapping bioregions.

### Nested bioregions and transition zones

A biogeographical transition zone is defined as a geographical area of
overlap, with a gradient of replacement and partial segregation between biotic
components (sets of taxa that share a similar geographical distribution as a
product of a common history)[9]. Many factors, such as mountain ranges,
watersheds, climate, macroevolutionary and paleogeographic processes, flora,
and fauna, shape bioregional boundaries [2, 10, 16]. Some boundaries may be
sharp, while others may be fuzzy [17, 16]. To highlight transition zones, we
use a network metric called the participation coefficient that defines the
degree to which a node is connected to other modules [1]. We adopt the measure
by coloring grid cells with an opacity equal to the fraction of connected
species belonging to the same module, weighted by the link weights to the
species. To further enhance the richness of the bioregional maps, we mix the
color of each grid cell with the color of the second most connected bioregion,
interpolated according to their relative weight.

However, wide-spread species can obscure and collapse modular patterns and
transition zones defined by range-restricted species [15]. As narrowly
distributed species are important for unveiling biogeographic patterns and
evolutionary processes [19], and usually also considered of higher
conservation value [7], we down-weight widespread species as described above
for integrating the whole phylogenetic tree. This gives a less dense species
occurrence network, making hierarchical structures easier to detect.

### Global mammal occurrence data

To evaluate the method, we applied the same point occurrence dataset with
globally distributed terrestrial mammals and the corresponding phylogenetic
tree we used in [6]. It consists of 1.5M point occurrences that we bin with an
adaptive resolution to grid cells from 4 degrees to 1, subdivided on capacity
100 with a minimum of 10 records per cell. As a bipartite network without
incorporating the phylogenetic tree, it has $10\,191$ nodes consisting of
$4\,972$ species connected to $5\,219$ grid cells with $210\,892$ links
weighted by range size. The species occurrences are not uniformly distributed
but concentrated in Europe, sub-Saharan Africa, the Americas, and Australasia,
with Russia being the most sparse region (Fig. 3).

Figure 3: Mammal occurrences. It consists of 1.5M point occurrences of
$4\,972$ species binned with an adaptive resolution to $5\,219$ grid cells
with sides 1-4 degrees.

##  3 Results

To test our method, we load the mammal dataset described above into Infomap
Bioregions 2, with the default settings for adaptive resolution between 1 and
4 degrees. As a baseline, we run Infomap with 20 trials without including the
phylogenetic tree. The resulting bioregions are organized into three levels,
with the top level containing tree modules. North America, Europe, Africa,
North Asia, and Australia are grouped, while South America and South Asia are
separated at this level (Fig. 4(a)). In the second level, at higher
resolution, we see how Europe, Africa, North America, and Australia are
divided. We also see how Asia and the North and South Americas are divided
into more biogeographical units. Sub-Saharan Africa is kept in a single
module, but Madagascar is distinctly separated (Fig. 4(b)). Australia and
Africa are divided into finer bioregions at the finest level with clear
transition zones (Fig. 4(c)).

When we integrate the whole phylogenetic tree of mammals, the network becomes
denser, and we find bioregions in a single level. By connecting grid cells not
only based on shared species but also shared ancestry from the whole tree, the
bioregions capture broad phylogenetically more distinct areas (Fig. 5). We use
an Alluvial diagram to compare the map without a tree (left) with the map
based on the tree (right). In the left part, colors show bioregions on level
1, and larger and smaller vertical gaps show bioregions on levels 2 and 3,
respectively. With the phylogenetic tree integrated, the map is largely
contained within the top-level bioregions without a tree, where
phylogenetically distinct bioregions from level 2, such as Madagascar and New
Guinea, are kept separate while other bioregions are merged. Interestingly,
bioregions produced when integrating phylogenetic information are more
congruent with those proposed by Wallace and later refinements also using
phylogenetic information [12], supporting the validity of our approach.

While integrating the whole phylogeny produce highly phylogenetically distinct
bioregions, it may also blur the signal of to some extent recent event on the
spatial organization of lineages. Around 110Ma the Earth experienced a global
plate reorganization event with break-ups leading to the current configuration
of continents [18]. Hence, it could be expected that important
reconfigurations of biodiversity took place after this event, shaping the
current distribution of lineages and leaving detectable signals on bioregions.
To explore this idea, we segregate the network between species and grid cells
at 110Ma, which creates bioregions formed only by the shared species within
the evolutionary branches up to that point. This creates evolutionary distinct
bioregions that may also overlap in space. The overlap is highlighted with a
lower opacity and mixed colors. The resultant bioregions are similar to those
detected when using the whole phylogeny, though in the finest of four levels
there are more detailed bioregions such as those dividing Africa (Fig. 6). At
this hierarchical level, bioregions are relatively distinct except for
Australia, which contains many overlapping bioregions and suggests that the
phylogenetic signal behind this bioregion predates the age of segregation used
(i.e. the ancestors of the Australian species diversified earlier than
110Ma.). Overall, these results show how this segregation approach can help to
better understand the origin of bioregions.

((a)) Level 1

((b)) Level 2

((c)) Level 3

Figure 4: Three levels of nested mammalian bioregions detected with Infomap
Bioregions 2. Map based on 1.5M point occurrences binned with an adaptive
resolution to grid cells from 4 degrees to 1. Opacity shows the degree of
species overlap, which highlights transition zones

((a))

((b))

Figure 5: Comparing bioregions with and without integrating the phylogenetic
tree. a) Alluvial diagram comparing the bioregions from Fig. 4, colored by the
top level bioregions with larger and smaller gaps showing levels 2 and 3,
respectively, with the bioregions obtained with the tree. b) One level of
bioregions detected when integrating the whole phylogenetic tree, which tends
to merge areas where species are phylogenetically close. Figure 6: Overlapping
bioregions. By segregating the network between species and grid cells at time
110Ma, using higher-order networks, we can detect evolutionarily distinct
bioregions and see where they overlap, such as in Australia, based on the
opacity and mixed colors. Showing the bottom level of four from a hierarchical
result of nested bioregions.

##  4 Conclusion

We have introduced a method to incorporate phylogenetic information into
network-based bioregionalization to produce more biologically informative and
robust bioregions. The method indirectly connects grid cells through not only
shared species but also shared ancestry. It reduces biases caused by
disagreements in species delimitation and also alleviates the risk of
overfitting on sparse data where different but closely related species may end
up in disconnected bioregions spanning a single or few cells.

We now weigh links between species and grid cells by the species’ geographic
distribution which reduces the sensitivity on widespread species to overshadow
spatial signals from other species and collapse modular patterns. Doing the
same for ancestral nodes enables the integration of the whole phylogenetic
tree. This highlights bioregions shaped by range-restricted species or clades,
essential for conservation purposes and a better understanding of evolutionary
processes shaping bioregional patterns. This generally also gives deeper
hierarchies of nested bioregions which we now make possible to explore.
Coloring the grid cells by the degree to which they connect to other
bioregions highlights transition zones, fuzzy boundaries and the robustness of
the solution on grid cell level.

For a more detailed analysis, we present two complementary methods to
delineate evolutionary distinct bioregions by extracting information from a
phylogenetic tree at selected times into the network. The first method has an
integrating effect, connecting phylogenetic nodes at a selected time to grid
cells where their descendant species occur. This procedure indirectly connects
grid cells with species sharing common ancestors within the selected period.
By sweeping through the phylogenetic tree in time, our method interpolates
between finding bioregions based only on distributional data and finding
spatially segregated clades, uncovering evolutionarily distinct bioregions at
different time slices. The second method has a segregating effect,
constraining network paths within branches cut at a selected point in time.
With the segregating method, we can interpolate between finding evolutionary
isolated clades and the spatial extent of clades, relaxing the non-overlapping
constraint for bioregions.

We have implemented these methods in Infomap Bioregions version 2, an
interactive web application that makes it easy to explore the relationship
between species’ spatial and phylogenetic patterns and identify evolutionarily
distinct overlapping bioregions. With these new techniques, we can create
richer bioregional maps and uncover biogeographical and evolutionary patterns
not previously visible.

##  5 Funding

D.E. and M.R. were supported by the Swedish Research Council (2016-00796).
A.H. was supported by the Swedish Foundation for Strategic Research, Grant No.
SB16-0089. A.R. was partially supported by the Kone Foundation funded project
Comparing evolutionary processes in nature and society (project number
202007064). J.C. was supported by the Ministry of Science and Innovation
through the UNIPER project (PID2020-114851GA-I00). A.A. acknowledges financial
support from the Swedish Research Council (2019-05191), the Swedish Foundation
for Strategic Environmental Research MISTRA (Project BioPath), and the Royal
Botanic Gardens, Kew.

##  6 Author contributions

A.A. conceived the study. D.E. designed the methods. D.E. and A.H. implemented
the interactive web application and performed the experiments with feedback
from all authors. All authors wrote, edited, and accepted the manuscript in
its final form.

##  7 Competing interests

The authors declare that they have no competing interests.

## References

  * [1] Nathaniel J. Bloomfield, Nunzio Knerr and Francisco Encinas-Viso  “A comparison of network and clustering methods to detect biogeographical regions”  In _Ecography_ 41.1, 2018, pp. 1–10  DOI: 10.1111/ecog.02596
  * [2] Joaquín Calatayud et al.  “Pleistocene climate change and the formation of regional species pools”  In _Proceedings of the Royal Society B: Biological Sciences_ 286.1905, 2019, pp. 20190291  DOI: 10.1098/rspb.2019.0291
  * [3] Leandro D.. Duarte, Vanderlei J. Debastiani, André V.. Freitas and Valério D. Pillar  “Dissecting phylogenetic fuzzy weighting: theory and application in metacommunity phylogenetics”  In _Methods in Ecology and Evolution_ 7.8, 2016, pp. 937–946  DOI: 10.1111/2041-210X.12547
  * [4] Daniel Edler, Ludvig Bohlin and Martin Rosvall  “Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap”  In _Algorithms_ 10.4, 2017, pp. 112  DOI: 10.3390/a10040112
  * [5] Daniel Edler, Anton Holmgren and Martin Rosvall  “The MapEquation software package”, 2022
  * [6] Daniel Edler et al.  “Infomap Bioregions: Interactive Mapping of Biogeographical Regions from Species Distributions”  In _Systematic Biology_ 66.2, 2017, pp. 197–204  DOI: 10.1093/sysbio/syw087
  * [7] Harith Farooq et al.  “WEGE: A new metric for ranking locations for biodiversity conservation”  In _Diversity and Distributions_ 26.11, 2020, pp. 1456–1466  DOI: 10.1111/ddi.13148
  * [8] Søren Faurby, Wolf L. Eiserhardt and Jens-Christian Svenning  “Strong effects of variation in taxonomic opinion on diversification analyses”  In _Methods in Ecology and Evolution_ 7.1, 2016, pp. 4–13  DOI: 10.1111/2041-210X.12449
  * [9] Ignacio Ferro and Juan J. Morrone  “Biogeographical transition zones: a search for conceptual synthesis”  In _Biological Journal of the Linnean Society_ 113.1, 2014, pp. 1–12  DOI: 10.1111/bij.12333
  * [10] Gentile Francesco Ficetola, Florent Mazel and Wilfried Thuiller  “Global determinants of zoogeographical boundaries”  In _Nature Ecology & Evolution_ 1.4, 2017, pp. 1–7  DOI: 10.1038/s41559-017-0089
  * [11] Michael Foote et al.  “Rise and Fall of Species Occupancy in Cenozoic Fossil Mollusks”  In _Science_ 318.5853, 2007, pp. 1131–1134  DOI: 10.1126/science.1146303
  * [12] Ben G. Holt et al.  “An Update of Wallace’s Zoogeographic Regions of the World”  In _Science_ 339.6115, 2013, pp. 74–78  DOI: 10.1126/science.1228282
  * [13] Holger Kreft and Walter Jetz  “A framework for delineating biogeographical regions based on species distributions”  In _Journal of Biogeography_ 37.11, 2010, pp. 2029–2053  DOI: 10.1111/j.1365-2699.2010.02375.x
  * [14] Shawn W. Laffan, Eugene Lubarsky and Dan F. Rosauer  “Biodiverse, a tool for the spatial analysis of biological and related diversity”  In _Ecography_ 33.4, 2010, pp. 643–647  DOI: 10.1111/j.1600-0587.2010.06237.x
  * [15] Shawn W. Laffan et al.  “Range-weighted metrics of species and phylogenetic turnover can better resolve biogeographic transition zones”  In _Methods in Ecology and Evolution_ 7.5, 2016, pp. 580–588  DOI: 10.1111/2041-210X.12513
  * [16] Yunpeng Liu et al.  “An updated floristic map of the world”  In _Nature Communications_ 14.1, 2023, pp. 2990  DOI: 10.1038/s41467-023-38375-y
  * [17] Renan Maestri and Leandro Duarte  “Evoregions: Mapping shifts in phylogenetic turnover across biogeographic regions”  In _Methods in Ecology and Evolution_ 11.12, 2020, pp. 1652–1662  DOI: 10.1111/2041-210X.13492
  * [18] Hugo K.. Olierook et al.  “Timing and causes of the mid-Cretaceous global plate reorganization event”  In _Earth and Planetary Science Letters_ 534, 2020, pp. 116071  DOI: 10.1016/j.epsl.2020.116071
  * [19] Ignacio Quintero and Walter Jetz  “Global elevational diversity and diversification of birds”  In _Nature_ 555.7695, 2018, pp. 246–250  DOI: 10.1038/nature25794
  * [20] Alexis Rojas et al.  “A multiscale view of the Phanerozoic fossil record reveals the three major biotic transitions”  In _Communications Biology_ 4.1, 2021, pp. 1–8  DOI: 10.1038/s42003-021-01805-y
  * [21] Daril A. Vilhena and Alexandre Antonelli  “A network approach for identifying and delimiting biogeographical regions”  In _Nature Communications_ 6.1, 2015, pp. 6848  DOI: 10.1038/ncomms7848
  * [22] Carly Vynne et al.  “An ecoregion-based approach to restoring the world’s intact large mammal assemblages”  In _Ecography_ n/a DOI: 10.1111/ecog.06098

## Supplementary Information

((a))

((b)) 220 Ma

((c)) 200 Ma

((d)) 170 Ma

((e)) 150 Ma

((f)) 130 Ma

((g)) 110 Ma

((h)) 87 Ma

((i)) 65 Ma

((j)) 44 Ma

((k)) 22 Ma

((l)) 0 Ma

Figure S1: Evolutionarily unique mammalian bioregions. We integrate the
ancestral nodes at a selected time with equal strength as the species and
sweep through the time from recent to 220Ma. As we go back in time, grid cells
are connected by shared species at that time. If the species in two bioregions
to a large degree share a common ancestor within the selected time, two
bioregions are likely merged at that point. More and more regions get merged,
leaving evolutionarily unique areas left such as Madagascar.