# Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-
Connected Networks

Rajarshi Saha, Mohamed Seif, Michal Yemini, Andrea J. Goldsmith, H. Vincent
Poor R. Saha<EMAIL_ADDRESS>(corresponding author) is with the
Department of Electrical Engineering, Stanford University, Stanford, CA, USA
94305. (Email: rajsaha@stanford.edu). M. Seif (mseif@princeton.edu), A. J.
Goldsmith (goldsmith@princeton.edu), and H. V. Poor<EMAIL_ADDRESS>are
with the Department of Electrical and Computer Engineering, Princeton
University, Princeton, NJ, USA 08540. M. Yemini<EMAIL_ADDRESS>is
with the Department of Engineering, Bar-Ilan University, Ramat-Gan, Israel
5290002. This work was supported by the AFOSR award #002484665, a Huawei
Intelligent Spectrum grant, and NSF grants CCF-1908308 & CNS-2128448. A
preliminary version of this paper was presented at the 2023 IEEE International
Symposium on Information Theory, [1]. This work presents a detailed analysis
of the algorithm and simulations, along with the derivations of central
privacy guarantees, while allowing for heterogeneity in peer-to-peer privacy
noise perturbations.

###### Abstract

We consider the problem of privately estimating the mean of vectors
distributed across different nodes of an unreliable wireless network, where
communications between nodes can fail intermittently. We adopt a semi-
decentralized setup, wherein to mitigate the impact of intermittently
connected links, nodes can collaborate with their neighbors to compute a local
consensus, which they relay to a central server. In such a setting, the
communications between any pair of nodes must ensure that the privacy of the
nodes is rigorously maintained to prevent unauthorized information leakage. We
study the tradeoff between collaborative relaying and privacy leakage due to
the data sharing among nodes and, subsequently, propose PriCER: Private
Collaborative Estimation via Relaying – a differentially private collaborative
algorithm for mean estimation to optimize this tradeoff. The privacy
guarantees of PriCER arise $\rm\bf(i)$ implicitly, by exploiting the inherent
stochasticity of the flaky network connections, and $\rm\bf(ii)$ explicitly,
by adding Gaussian perturbations to the estimates exchanged by the nodes.
Local and central privacy guarantees are provided against eavesdroppers who
can observe different signals, such as the communications amongst nodes during
local consensus and (possibly multiple) transmissions from the relays to the
central server. We substantiate our theoretical findings with numerical
simulations. Our implementation is available at
https://github.com/rajarshisaha95/private-collaborative-relaying.

###### Index Terms:

Distributed mean estimation, Differential privacy, Intermittent network
connectivity, Collaborative Relaying

##  I Introduction

Distributed Mean Estimation (DME) is a fundamental statistical problem that
arises in several applications, such as model aggregation in federated
learning (FL) [2], distributed K-means clustering [3], and distributed power
iteration [4]. DME presents several practical challenges, which prior studies
[5, 6, 7, 8, 9] have considered, including the problem of straggler nodes,
where distributed nodes cannot send their data to the aggregator, or parameter
server (PS). In practical systems, typically, there are two types of
stragglers: $\rm(i)$ computation stragglers, which cannot finish their local
computation within a deadline, and $\rm(ii)$ communication stragglers, in
which nodes cannot transmit their updates due to communication blockage [10,
11, 12, 13, 14, 15]. For instance, nodes may become communication stragglers
when their wireless communication channel to the PS is temporarily blocked.
Unlike computation stragglers, the problem of communication stragglers can be
mitigated by relaying the updates/data via neighboring nodes that have better
connectivity to the PS.

The problem of intermittent node participation, primarily in the context of
Federated Learning, has been studied in prior works such as [16, 17, 18, 19,
20, 21, 22]. The collaborative relaying approach for mitigating node
intermittency was proposed in [23, 24, 25], where it was shown that in the
presence of communication stragglers, collaborative relaying can improve the
accuracy of mean estimation and also enhance the convergence rate of FL
algorithms. While these works show the benefit of relaying, they do not secure
the client data against the potential breach of privacy due to the additional
exchange of information across the nodes. To mitigate the privacy leakage in
DME via collaborative relaying, we must define the notions of peer-to-peer
privacy, and central privacy at the relay. Within the context of distributed
learning, local differential privacy (LDP) [26] has been adopted as a standard
notion of privacy, in which a node perturbs and discloses a sanitized version
of its data to an untrusted server. LDP ensures that the statistics of the
node’s output observed by eavesdroppers are indistinguishable regardless of
the realization of any input data. In this paper, we focus on the node-level
LDP where neighboring nodes, as well as any eavesdropper that can observe the
local node-node transmissions during collaborations, cannot infer the
realization of a node’s data.

There has been extensive research into the design of distributed learning
algorithms that are both communication efficient and private (see [27] for a
comprehensive survey and references therein). It is worth noting that LDP
requires a significant amount of perturbation noise to ensure reasonable
privacy guarantees. Nonetheless, the amount of perturbation noise can be
significantly reduced by considering the intermittent connectivity of nodes in
the learning process [28]. The intermittent connectivity in DME amplifies the
privacy guarantees in the sense that it provides an increased level of
anonymity due to partial communication with the server. Various random node
participation schemes such as Poisson sampling [29], importance sampling [30,
31], and sampling with/without replacement [28], have been proposed to further
improve the utility-privacy tradeoff in distributed learning. In addition,
[32] investigated the privacy amplification in federated learning via random
check-ins and showed that the privacy leakage scales as $O(1/\sqrt{n})$, where
$n$ is the number of nodes. Random node participation reduces the amount of
noise required to achieve the same levels of privacy that are achieved without
sampling.

Existing works in the privacy literature, such as [26, 27, 28, 29, 32, 33, 34,
35, 36, 37], do not consider intermittent connectivity along with
collaborative relaying, where nodes share their local updates to mitigate the
randomness in network connectivity [24, 25, 23]. In this work, we propose
PriCER (Private Collaborative Estimation via Relaying) for DME under an
intermittent connectivity assumption, and study its tradeoff between
collaborative relaying and privacy leakage due to data sharing among nodes.
PriCER is a two-stage algorithm, in which nodes improve their connectivity to
the PS by sharing their weighted and privatized data with neighbors. For a
given network topology, PriCER finds the best collaboration scheme by solving
a joint weight and privacy-noise variance optimization problem, subject to a
set of peer-to-peer privacy constraints. Privacy constraints, which are a
function of how much nodes trust each other, manifest as cone constraints, and
we iteratively obtain a close-to-optimal solution using projected gradient
descent. Moreover, for a symmetric network topology, we derive the optimal
solution in closed form.

In a distinct line of work, over-the-air computation (OAC) strategies have
been proposed, which exploit the signal superposition property of non-
orthogonal links between nodes and the PS, for mean estimation [38, 39, 40].
OAC aggregation schemes provide a certain degree of anonymity to the
participating nodes, consequently enhancing their privacy [41, 42]. PriCER is
compatible with OAC aggregation schemes and so, we also study the privacy
leakage from PriCER at any aggregating node acting as a relay. Subsequently,
we provide the privacy guarantees for protecting the anonymity and local data
of any node which collaborates with the relay.

###  I-A Main Contributions

Our main contributions can be summarized as follows:

  * •

We generalize the collaborative relaying approach proposed in [23, 24, 25] to
jointly consider the implications of privacy leakage due to collaboration. In
our proposed framework, nodes improve their connectivity to the PS by
exchanging scaled and perturbed versions of their local private data with
their neighbors, while taking into account the trustworthiness of their
neighbors.

  * •

We introduce the individualized notion of local peer-to-peer privacy
constraints as a measure to quantify the trustworthiness between any pair of
nodes.

  * •

Our algorithm optimizes private collaborative relaying so as to minimize the
MSE and to control the bias accumulated at the PS with a bias-regularization
term.

  * •

We study the central privacy leakage at the relays and the PS due to the
redundancy introduced from collaboration. Specifically, we consider the
privacy guarantees for preserving the anonymity as well as the local data of
any node participating in the collaboration process. We study our framework in
detail for the special case of an Erdös-Rényi network topology.

  * •

We validate our framework via numerical simulations and demonstrate its
efficacy in overcoming intermittent network connectivity in the presence of
privacy constraints for mean estimation and $\rm K$-means clustering tasks.

###  I-B Paper Organization

The remainder of the paper is as follows. In §II, we introduce our system
model and proposed algorithm, followed by mean-squared error (MSE) and privacy
analyses in §III and §IV, respectively. We propose our privacy-constrained
joint weight and variance optimization in §V. Finally, we demonstrate the
efficacy of PriCER via numerical simulations for different datasets and
network topologies in §VI, and conclude in §VII. Detailed derivations are
provided in the appendices.

##  II System model for private collaboration

Consider a distributed system with $n$ nodes, where node $i$ has an
observation vector $\mathbf{x}_{i}\in\mathbb{R}^{d}$,
$\lVert\mathbf{x}_{i}\rVert\leq{\rm R}$ for some known ${\rm R}>0$. The nodes
communicate with a PS and with each other over intermittent links with the
goal of estimating the mean,
$\overline{\mathbf{x}}\triangleq\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}$ at
the PS as shown in Fig. 1, so as to minimize the MSE, given by ${\cal
E}\triangleq\mathbb{E}\lVert\widehat{\overline{\mathbf{x}}}-\overline{\mathbf{x}}\rVert^{2}$.

Figure 1: Intermittently connected network. Dotted lines indicate intermittent
node-PS and node-node connections. Communication between any two nodes must
satisfy DP constraints.

###  II-A Communication model

We consider a setup where communication links are either unavailable or
available perfectly, i.e., they do not suffer from any channel imperfections.
Such links are modeled using $0/1$ Bernoulli random variables. As shown in
Fig. 1, node $i$ can communicate with the PS with probability $p_{i}$, with
the link modeled using a Bernoulli random variable $\tau_{i}\sim{\rm
Ber}(p_{i})$. $\tau_{i}=0$ implies a communication blockage between node $i$
and the PS, whereas $\tau_{i}=1$ implies the presence of a communication
opportunity. Similarly, node $i$ can communicate with another node $j$ with
probability $p_{ij}$, i.e., $\tau_{ij}\sim{\rm Ber}(p_{ij})$. The links
between different node pairs are assumed to be statistically independent,
i.e., $\tau_{i}\perp\tau_{j}$ for $i\neq j$, $\tau_{ij}\perp\tau_{ml}$ for
$(i,j)\neq(m,l)$, $(j,i)\neq(m,l)$, and $\tau_{ij}\perp\tau_{l}$ for $i,j,l$.
The correlation of channels between a pair of nodes $i,j$ is denoted by
$\mathrm{E}_{\\{i,j\\}}\equiv\mathbb{E}[\tau_{ij}\tau_{ji}]$. We assume that
$\mathrm{E}_{\\{i,j\\}}\geq p_{ij}p_{ji}$, i.e.,
$\mathbb{P}(\tau_{ij}=1|\tau_{ji}=1)\geq\mathbb{P}(\tau_{ij}=1)$. Furthermore,
$p_{ii}=1\;\forall\;i\in[n]$, and if node $i$ can never transmit to $j$, we
have $p_{ij}=0$. We denote $\mathbf{p}\equiv(p_{1},\ldots,p_{n})$ and
$\mathbf{P}\equiv(p_{ij})_{i,j\in[n]}\in[0,1]^{n\times n}$.

###  II-B Privacy model

The nodes are assumed to be honest but curious. They are honest because they
faithfully perform their role in the system, i.e., compute the aggregate of
the received signals. However, they are curious as they might be interested in
learning sensitive information about other nodes. Each node uses an
independent local additive noise mechanism to ensure the privacy of its
transmissions to neighboring nodes. Since there are several transmissions
across nodes, and between nodes and the PS, there can be different sources of
privacy leakage depending on what the eavesdropper (which can be a node or an
external agent) has access to. We consider local privacy constraints, wherein
node $i$ trusts another node $j$ to a certain extent, and hence, randomizes
its own data accordingly when sharing with node $j$ using a synthetic Gaussian
noise to respect the privacy constraint of the link $i\to j$. In addition to
this, we also consider central privacy at each node when it acts as a relay
and does local aggregation in Alg. 1, as well as the central privacy at the PS
(Alg. 2). A brief refresher on differential privacy and Gaussian mechanism is
presented in App. G. We formally analyze the privacy guarantees in §IV.

###  II-C Private collaborative relaying for mean estimation

We now introduce PriCER, which is a two-stage semi-decentralized algorithm for
estimating the mean. In the first stage, each node $j$ sends a scaled and
privacy noise-added version of its data to a neighboring node $i$ over the
intermittent link $\tau_{ji}$. The transmitted signal from node $j\to i$ is

$\widetilde{\mathbf{x}}_{ji}=\tau_{ji}(\alpha_{ji}\mathbf{x}_{j}+\mathbf{n}_{ji}).$
(1)

Here, $\alpha_{ji}\geq 0$ is the weight used by node $j$ while transmitting to
node $i$, and $\mathbf{n}_{ji}\sim{\cal
N}(\mathbf{0},\sigma_{ji}^{2}\mathbf{I}_{d})$ is the multivariate Gaussian
noise added by node $j$. We denote the weight matrix by
$\mathbf{A}\equiv(\alpha_{ij})_{i,j\in[n]}$, and the noise variance matrix by
$\boldsymbol{\Sigma}=(\sigma_{ij})_{i,j\in[n]}$. Consequently, node $i$
computes the local aggregate of all received signals as

$\widetilde{\mathbf{x}}_{i}=\sum_{j\in[n]}\tau_{ji}(\alpha_{ji}\mathbf{x}_{j}+\mathbf{n}_{ji}).$
(2)

By observing $\widetilde{\mathbf{x}}_{ji}$ or $\widetilde{\mathbf{x}}_{i}$, an
eavesdropper (possibly including node $i$) should not be able to distinguish
between the events when node $j$ contains the data $\mathbf{x}_{j}$ versus
when it contains some other data $\mathbf{x}_{j}^{\prime}$. In addition to
this, by observing $\widetilde{\mathbf{x}}_{i}$, an eavesdropper should also
not be able to tell when node $j$ participated in the aggregation at node $i$
or not. We assume that the privacy noise added by different nodes are
uncorrelated, i.e., $\mathbb{E}[\mathbf{n}_{il}^{\top}\mathbf{n}_{jm}]=0$ for
all $i,j,l,m$ as long as $i,j,l,m$ are not all equal. In the second stage,
each node $i$ transmits $\widetilde{\mathbf{x}}_{i}$ to the PS over the
intermittent link $\tau_{i}$, and the PS computes the global estimate. The
Pseudocode for PriCER is given in Algs. 1 and 2.

Algorithm 1 PriCER-Stage 1: Local aggregation

Input: Non-negative weight matrix $\mathbf{A}$

Output: $\widetilde{\mathbf{x}}_{i}$ for all $i\in[n]$

for $i=1$ to $n$ do

Locally generate $\mathbf{x}_{i}$

Transmit
$\widetilde{\mathbf{x}}_{ij}=\alpha_{ij}\mathbf{x}_{i}+\mathbf{n}_{ij}$ to
nodes $j\neq i$

Receive
$\widetilde{\mathbf{x}}_{ji}=\tau_{ji}(\alpha_{ji}\mathbf{x}_{j}+\mathbf{n}_{ji})$
from $j\neq i$

Set $\widetilde{\mathbf{x}}_{ii}=\alpha_{ii}\mathbf{x}_{i}+\mathbf{n}_{ii}$

Locally aggregate:
$\widetilde{\mathbf{x}}_{i}=\sum_{j\in[n]}\widetilde{\mathbf{x}}_{ji}$

Transmit $\widetilde{\mathbf{x}}_{i}$ to the PS

end for

Algorithm 2 PriCER-Stage 2: Global aggregation

Input: $\tau_{i}\widetilde{\mathbf{x}}_{i}$ for all $i\in[n]$

Output: Estimate of the mean at the PS: $\widehat{\overline{\mathbf{x}}}$

for $i=1$ to $n$ do

Receive $\tau_{i}\widetilde{\mathbf{x}}_{i}$

end for

Aggregate the received signals:
$\widehat{\overline{\mathbf{x}}}=\frac{1}{n}\sum_{i\in[n]}\tau_{i}\widetilde{\mathbf{x}}_{i}$

##  III Estimation error analysis

The goal of PriCER is to obtain an estimate of $\overline{\mathbf{x}}$ at the
PS. Since each node sends its data to all other neighboring nodes, the PS
receives multiple copies of the same data, which can introduce some bias. Let
us denote $S_{i}\triangleq\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}$, i.e., after
relaying from all the nodes, the PS receives an expected contribution of node
$i$ as $S_{i}\mathbf{x}_{i}$, implying an expected bias of
$(S_{i}-1)\mathbf{x}_{i}$. Let us also define the Euclidean ball,
$\mathbb{B}_{d}(\mathrm{R})=\\{\mathbf{x}\in\mathbb{R}^{d}\;\left\lVert\mathbf{x}\right\rVert\leq\mathrm{R}\\}$.
The following result upper bounds the MSE of PriCER.

######  Theorem III.1.

Suppose for some $\mathrm{R}>0$, $\mathbf{x}_{i}\in\mathbb{B}_{d}(\mathrm{R})$
for all $i\in[n]$. Given $\mathbf{p},\mathbf{P}$, $\mathbf{A}$, and
$\boldsymbol{\Sigma}$, the MSE of PriCER is upper bounded as:

$\sup_{\\{\mathbf{x}_{i}\in\mathbb{B}_{d}(\mathrm{R})\\}}\mathbb{E}\lVert\widehat{\overline{\mathbf{x}}}-\mathbf{x}\rVert^{2}\leq\sigma_{\rm
tiv}^{2}(\mathbf{p},\mathbf{P},\mathbf{A})+\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma}),$ (3)

where the expectation is over the stochasticity of intermittent connections
and the randomness due to privacy noise. Here, $\sigma_{\rm
tiv}^{2}(\mathbf{p},\mathbf{P},\mathbf{A})$ is the topology-induced variance
introduced by the stochasticity due to intermittent topology given by

$\displaystyle\sigma_{\rm
tiv}^{2}(\mathbf{p},\mathbf{P},\mathbf{A})\triangleq\frac{{\rm
R}^{2}}{n^{2}}\left[\sum_{i,j\in[n]}p_{j}p_{ij}\left(1-p_{ij}\right)\alpha_{ij}^{2}\right.$
$\displaystyle\hskip
85.35826pt+\left.\sum_{i,j,l\in[n]}p_{j}(1-p_{j})p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\right.$
$\displaystyle\left.+\sum_{i,j\in[n]}p_{i}p_{j}(\mathrm{E}_{\\{i,j\\}}-p_{ij}p_{ji})\alpha_{ij}\alpha_{ji}+\left(\sum_{i\in[n]}(S_{i}-1)\right)^{2}\right],$
(4)

and $\sigma_{\rm pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma})$ is the
privacy-induced variance given by

$\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma})\triangleq\frac{d}{n^{2}}\sum_{i,j\in[n]}p_{j}p_{ij}\sigma_{ij}^{2}.$
(5)

Thm. III.1 is derived in App. A. From (3), we see that $\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma})$ is the price of privacy.
For a non-private setting, i.e., $\sigma_{ij}=0\;\forall\;i,j$, the privacy
induced variance $\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma})=0$, and Thm. III.1
simplifies to [23, Thm. 3.2]. In the following section, we present privacy
guarantees leading to a choice of weight matrix $\mathbf{A}$ for the optimal
utility (MSE) – privacy tradeoff for PriCER.

##  IV Privacy analysis

In Fig. 1, there are several transmissions across nodes, and between nodes and
the PS. Consequently, there can be different sources of privacy leakage
depending on what the eavesdropper can access. The privacy guarantees of
PriCER result from two effects: $\rm(i)$ the local noise added at each node,
and $\rm(ii)$ the intermittent nature of the connections. We consider
guarantees for protecting the local data of each node, and also for protecting
the identity of a particular node in the local aggregation steps. We formalize
these guarantees below.

###  IV-A Local privacy guarantee for node-node communications

We first consider the case in which an eavesdropper can observe the
transmission from node $i$ to node $j$ during the local-aggregation step of
PriCER. Let us denote the dataset of node $i$ as ${\cal D}_{i}$. For DME,
${\cal D}_{i}$ is a singleton set and by observing the transmission from node
$i$ to node $j$, the eavesdropper (which can possibly include node $j$ itself)
should not be able to differentiate between the events $\mathbf{x}_{i}\in{\cal
D}_{i}$ and $\mathbf{x}_{i}^{\prime}\in{\cal D}_{i}$, where
$\mathbf{x}_{i}^{\prime}\neq\mathbf{x}_{i}$, formalized in (7). The following
result, which is proved in App. H, states our local privacy guarantee.

######  Theorem IV.1.

Given $\mathbf{n}_{ij}\sim{\cal N}(\mathbf{0},\sigma_{ij}^{2}\mathbf{I}_{d})$,
$\mathbf{x}_{i},\mathbf{x}_{i}^{\prime}\in\mathbb{B}_{d}(\mathrm{R})$, and any
$\delta_{ij}\in(0,1]$, for $(\epsilon_{ij},p_{ij}\delta_{ij})$ that satisfy

$\epsilon_{ij}=\begin{cases}\left[2\log\left(\frac{1.25}{\delta_{ij}}\right)\right]^{\frac{1}{2}}\frac{2\alpha_{ij}{\rm
R}}{\sigma_{ij}}\;\;\;\text{ if }\;p_{ij}>0,\;\;\text{ and, }\\\ \hskip
42.67912pt0\;\;\hskip 46.94704pt\text{ if }\;p_{ij}=0,\end{cases}$ (6)

the transmitted signal from node $i$ to node $j$, i.e.,
$\widetilde{\mathbf{x}}_{ij}=\tau_{ij}(\alpha_{ij}\mathbf{x}_{i}+\mathbf{n}_{ij})$
is $(\epsilon_{ij},p_{ij}\delta_{ij})$-differentially private. In other words,
for any measurable set ${\cal S}$, $\widetilde{\mathbf{x}}_{ij}$ satisfies

$\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal S}\mid\mathbf{x}_{i}\in{\cal
D}_{i}\right)\leq
e^{\epsilon_{ij}}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i}\right)+p_{ij}\delta_{ij}.$ (7)

Here, $\epsilon_{ij}$ is a measure of how much node $i$ trusts node $j$; a
smaller value implying less trust, and hence requirement of a stricter privacy
guarantee.

$\displaystyle
r=\frac{{\max_{k\in[n]\setminus\\{j\\}}\sigma_{kj}^{2}}/{3}+\sqrt{{\max_{k\in[n]\setminus\\{j\\}}\sigma_{kj}^{2}}/{9}+4(\sum_{k\in[n]\setminus\\{j\\}}p_{kj}(1-p_{kj})\sigma_{kj}^{4})/\log(2/\delta^{\prime})}}{2/\log(2/\delta^{\prime})}$
(8)

###  IV-B Central privacy guarantees at a relay

After each node $j$ receives signals from its neighbors, it locally aggregates
them, which is analytically captured as,
$\underline{\widetilde{\mathbf{x}}}_{j}=\sum_{k\in[n]\setminus\\{j\\}}\tau_{kj}(\alpha_{kj}\mathbf{x}_{k}+\mathbf{n}_{kj})$.
It then acts as a relay to transmit
$\widetilde{\mathbf{x}}_{j}=\underline{\widetilde{\mathbf{x}}}_{j}+\widetilde{\mathbf{x}}_{jj}$
to the PS. Here, node $j$ sets
$\widetilde{\mathbf{x}}_{jj}\triangleq\alpha_{jj}\mathbf{x}_{j}+\mathbf{n}_{jj}$
as in Alg. 1. We consider the central privacy leakage of relay $j$ when an
eavesdropper (possibly node $j$ itself) can observe
$\underline{\widetilde{\mathbf{x}}}_{j}$. Privacy guarantees are a consequence
of $\rm(i)$ the random participation of nodes while computing
$\underline{\widetilde{\mathbf{x}}}_{j}$ at relay $j$, and $\rm(ii)$ the
aggregated noise in $\underline{\widetilde{\mathbf{x}}}_{j}$ as a consequence
of local Gaussian perturbations added by the participating nodes.

Let ${\cal R}_{j}\triangleq\\{k\neq j\mid\tau_{kj}=1\\}\subseteq[n]$ denote
the random set of nodes participating at relay $k$. Note that the effective
noise variance at relay $j$, denoted as
$\zeta_{j}\triangleq\sum_{k\in[n]\setminus\\{j\\}}\tau_{kj}\sigma_{kj}^{2}=\sum_{k\in{\cal
R}_{j}}\sigma_{kj}^{2}$, is a function of ${\cal R}_{j}$, excluding relay $j$.
To account for this stochasticity, we condition on the event when the
deviation of this aggregated noise $\zeta_{j}$ from its mean, i.e.,
$\overline{\zeta}_{j}=\sum_{k\in[n]\setminus\\{j\\}}p_{kj}\sigma_{kj}^{2}$, is
small. Our central privacy guarantees are formally stated in Thms. IV.2 and
IV.3

Privacy guarantee for protecting the identity of any node: For any node $j$
acting as a relay, only a random subset of its neighbors participate in
computing $\underline{\widetilde{\mathbf{x}}}_{j}$. We are interested in
protecting the identity of participating nodes. Specifically, by observing
$\underline{\widetilde{\mathbf{x}}}_{j}$, an eavesdropper (possibly including
node $j$) should not be able to confidently infer whether a particular node
$i$ communicated with node $j$. Suppose the local aggregation at node $j$
takes place blindly, i.e., it honestly aggregates all the signals it receives
anonymously. This would happen, for example, in over-the-air schemes, wherein
different nodes simultaneously send their data to an aggregating node over a
shared non-orthogonal wireless medium. In this setting, aggregation at the PS
happens because the wireless channel combines all signals “over-the-air”. In
such a situation, the aggregating node $j$ is assumed to be honest-but-
curious, and it should not be able to infer the identity of a specific
participating node.

Let $\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\triangleq\sum_{k\in{\cal
R}_{j}\setminus\\{i\\}}\left(\alpha_{kj}\mathbf{x}_{k}+\mathbf{n}_{kj}\right)$
be the aggregate at the $j^{\rm th}$ node when the contribution of node $i$ is
removed, in case it participated. Thm. IV.2, which is proved in App. B,
formally states this guarantee wherein by observing
$\underline{\widetilde{\mathbf{x}}}_{j}$, an eavesdropper would not be able to
distinguish between the presence or absence of a specific node $i$ amongst the
set of nodes that participate in the local aggregation at node $j$.

######  Theorem IV.2.

[Protecting node identity] Given privacy noises $\mathbf{n}_{kj}\sim{\cal
N}(\mathbf{0},\sigma_{kj}^{2}\mathbf{I}_{d})$,
$\zeta_{j}=\sum_{k\in[n]\setminus\\{j\\}}\tau_{kj}\sigma_{kj}^{2}$ with
$\tau_{kj}\sim{\rm Ber}(p_{jk})$,
$\overline{\zeta}_{j}=\sum_{k\in[n]\setminus\\{j\\}}p_{kj}\sigma_{kj}^{2}$,
$r>0$, and $\delta^{\prime}\in(0,1)$ such that
$\Pr(|\zeta_{j}-\overline{\zeta}_{j}|\geq r)\leq\delta^{\prime}$, for pairs
$(\epsilon_{ij}^{(p)},p_{ij}(\delta_{j}^{(p)}+\delta^{\prime}))$ satisfying

$\epsilon_{ij}^{(p)}=\begin{cases}{\left[2\log\left(\frac{1.25}{\delta_{j}^{(p)}}\right)\right]^{\frac{1}{2}}\frac{\alpha_{ij}{\rm
R}}{\sqrt{\overline{\zeta}_{j}-r}}}\;\;\;\text{ if }\;p_{ij}>0,\;\;\text{ and,
}\\\ \hskip 54.06023pt0\;\;\hskip 45.5244pt\text{ if
}\;\;p_{ij}=0,\end{cases}$ (9)

the aggregated signal at node $j$, i.e.,
$\underline{\widetilde{\mathbf{x}}}_{j}=\sum_{k\in{\cal
R}_{j}}(\alpha_{kj}\mathbf{x}_{k}+\mathbf{n}_{kj})$ is
$(\epsilon_{ij}^{(p)},p_{ij}(\delta_{j}^{(p)}+\delta^{\prime}))$
differentially private with respect to protecting the identity of any
participating node $i$. In other words, for any measurable set ${\cal S}$,

$\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\right)\leq
e^{\epsilon_{ij}^{(p)}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\right)+p_{ij}(\delta_{j}^{(p)}+\delta^{\prime}).$ (10)

Privacy guarantee for protecting the local data of any node: We also consider
the privacy guarantee for protecting the local data of any node $i$ when the
eavesdropper can observe $\underline{\widetilde{\mathbf{x}}}_{j}$. This
privacy guarantee for protecting the local data of node $i$ implies that if
$\mathbf{x}_{i}=\mathbf{u}$ is perturbed to be
$\mathbf{x}_{i}=\mathbf{u}^{\prime}$, the signal aggregated at node $j$ to the
PS, i.e., $\underline{\widetilde{\mathbf{x}}}_{j}$, should not change
significantly. The following result (derived in App. C) formalizes this.

######  Theorem IV.3.

[Protecting local data at nodes] Given privacy noises
$\mathbf{n}_{kj}\sim{\cal N}(\mathbf{0},\sigma_{kj}^{2}\mathbf{I}_{d})$,
$\zeta_{j}=\sum_{k\in{\cal R}_{j}}\sigma_{kj}^{2}$,
$\overline{\zeta}_{j}=\sum_{k\in[n]\setminus\\{j\\}}p_{kj}\sigma_{kj}^{2}$,
$r>0$, and $\delta^{\prime}\in(0,1)$ such that
$\Pr(|\zeta_{j}-\overline{\zeta}_{j}|\geq r)\leq\delta^{\prime}$, for
$(\epsilon_{ij}^{(d)},p_{ij}(\delta_{j}^{(d)}+\delta^{\prime}))$ satisfying

$\epsilon_{ij}^{(d)}=\begin{cases}2\cdot{\left[2\log\left(\frac{1.25}{\delta_{j}^{(d)}}\right)\right]^{\frac{1}{2}}\frac{\alpha_{ij}{\rm
R}}{\sqrt{\overline{\zeta}_{j}-r}}}\;\;\;\text{ if }\;p_{ij}>0,\;\;\text{ and,
}\\\ \hskip 55.48286pt0\;\;\hskip 52.63759pt\;\text{ if
}\;\;p_{ij}=0,\end{cases}$ (11)

the aggregate at node $j$, i.e.,
$\underline{\widetilde{\mathbf{x}}}_{j}=\sum_{k\in{\cal
R}_{j}}(\alpha_{kj}\mathbf{x}_{k}+\mathbf{n}_{kj})$ is
$(\epsilon_{ij}^{(d)},p_{ij}(\delta_{j}^{(d)}+\delta^{\prime}))$
differentially private with respect to protecting the local data of any node
$i$. In other words, for any
$\mathbf{u},\mathbf{u}^{\prime}\in\mathbb{B}_{d}(\mathrm{R})$ and measurable
set ${\cal S}$, we have

$\displaystyle\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}\right)$ $\displaystyle\leq
e^{\epsilon^{(d)}_{ij}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime}\right)$
$\displaystyle\qquad\qquad+p_{ij}(\delta_{j}^{(d)}+\delta^{\prime}).$ (12)

In both Thms. IV.3 and IV.2, we can obtain the parameters
$(r,\delta^{\prime})$ using Bernstein’s inequality for
$\zeta_{j}=\sum_{k\in{\cal R}_{j}}\sigma_{kj}^{2}$. The following corollary,
derived in App. G-A, gives the smallest value for $r$ that satisfies
$\Pr(|\zeta_{j}-\overline{\zeta}_{j}|\geq r)\leq\delta^{\prime}$. 111One also
can use Hoeffding’s inequality for bounding this probability. The main
drawback of this technique is that it does not capture the connectivity
probabilities $p_{ij}$’s. Moreover, it can be readily verified that
Bernstein’s inequality is tighter, specially when $p_{ij}\ll 1$.

######  Corollary IV.4.

[Bernstein parameter] For a given $\delta^{\prime}\in(0,1]$, choosing $r$ as
in (8) ensures ${\Pr(|\zeta_{j}-\overline{\zeta}_{j}|\geq
r)\leq\delta^{\prime}}$.

###  IV-C Central privacy at parameter server

We now consider the central privacy guarantees at the PS which can observe the
outputs of multiple nodes acting as relays. Since the PS receives multiple
copies of the data of any specific client $i$ (upto scaling and additive
noise) from multiple node relays, the privacy guarantee at the PS can be
obtained using composition theorem [43]. Let
$\mathbf{y}_{j}=\tau_{j}\widetilde{\mathbf{x}}_{j}$, where $\tau_{j}\sim{\rm
Ber}(p_{j})$, denote the signal received by the PS from the $j^{\rm th}$
relay. We consider protecting the identity and the local data of a particular
node $i$. In Thm. IV.5 below (proved in App. D), we formalize this guarantee
by considering that the PS can observe outputs from each of the node relays,
i.e., $\\{\mathbf{y}_{j}\\}_{j\in[n]}$.

######  Theorem IV.5.

[Central privacy at PS] For all ${j\in[n]}$, consider we have privacy noises
${\left\\{\mathbf{n}_{kj}\sim{\cal
N}(\mathbf{0},\sigma_{kj}^{2}\mathbf{I}_{d})\right\\}_{k\in[n]}}$,
${\zeta_{j}=\sum_{k\in{\cal R}_{j}}\sigma_{kj}^{2}}$,
$\overline{\zeta}_{j}=\sum_{k\in[n]\setminus\\{j\\}}p_{kj}\sigma_{kj}^{2}$,
$r_{j}>0$, and $\delta_{j}^{\prime}\in(0,1)$ such that
$\Pr(|\zeta_{j}-\overline{\zeta}_{j}|\geq r_{j})\leq\delta_{j}^{\prime}$.
Furthermore, let $\mathbf{y}_{j}=\tau_{j}\widetilde{\mathbf{x}}_{j}$, where
$\tau_{j}\sim{\rm Ber}(p_{j})$, and
$\mathbf{y}_{j}^{(-i)}=\tau_{j}\widetilde{\mathbf{x}}_{j}^{(-i)}$, where
$\widetilde{\mathbf{x}}_{j}^{(-i)}=\sum_{k\in{\cal
R}_{j}\cup\\{j\\}\setminus\\{i\\}}\left(\alpha_{kj}\mathbf{x}_{k}+\mathbf{n}_{kj}\right)$.
Suppose the PS observes $(\mathbf{y}_{1},\ldots,\mathbf{y}_{n})$ from all the
nodes acting as relays. Then, for a specific node $i$, for any measurable set
${\cal S}^{n}\subseteq\mathbb{R}^{dn}$,

$\Pr(\\{\mathbf{y}_{j}\\}_{j\in[n]}\in{\cal S}^{n})\leq
e^{\widetilde{\epsilon}_{p}}\Pr(\\{\mathbf{y}_{j}^{(-i)}\\}_{j\in[n]}\in{\cal
S}^{n})+\widetilde{\delta}_{p},$ (13)

where,

${\widetilde{\epsilon}_{p}=\sum_{\begin{subarray}{c}j\in[n],\\\
p_{ij}>0\end{subarray}}\widetilde{\epsilon}_{ij}^{(p)}},\quad{\widetilde{\delta}_{p}=\delta\sum_{j\in[n]}p_{j}},\quad{\delta\in\left(0,{\rm
min}_{\begin{subarray}{c}j\in[n],\\\
p_{ij}>0\end{subarray}}\\{p_{ij}\\}\right]},$
$\text{and,}\quad{\widetilde{\epsilon}_{ij}^{(p)}={\left[2\log\left(\frac{1.25\;p_{ij}}{\delta-
p_{ij}\delta_{j}^{\prime}}\right)\right]^{\frac{1}{2}}\frac{\alpha_{ij}{\rm
R}}{\sqrt{\overline{\zeta}_{j}+\sigma_{jj}^{2}-r_{j}}}}}.$

Moreover, for any
$\mathbf{u},\mathbf{u}^{\prime}\in\mathbb{B}_{d}(\mathrm{R})$,

$\displaystyle\Pr(\\{\mathbf{y}_{j}\\}_{j\in[n]}\in{\cal
S}^{n}\mid\mathbf{x}_{i}=\mathbf{u})$ $\displaystyle\qquad\leq
e^{\widetilde{\epsilon}_{d}}\Pr(\\{\mathbf{y}_{j}\\}_{j\in[n]}\in{\cal
S}^{n}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime})+\widetilde{\delta}_{d},$ (14)

where,

$\widetilde{\epsilon}_{d}=\sum_{\begin{subarray}{c}j\in[n]\\\
p_{ij}>0\end{subarray}}\widetilde{\epsilon}_{ij}^{(d)},\quad\widetilde{\delta}_{d}=\delta\sum_{j\in[n]}p_{j},\quad\delta\in\left(0,{\rm
min}_{\begin{subarray}{c}j\in[n]\\\
p_{ij}>0\end{subarray}}\\{p_{ij}\\}\right],$
$\text{and,}\quad\widetilde{\epsilon}_{ij}^{(d)}={\left[2\log\left(\frac{1.25\;p_{ij}}{\delta-
p_{ij}\delta_{j}^{\prime}}\right)\right]^{\frac{1}{2}}\frac{2\alpha_{ij}{\rm
R}}{\sqrt{\overline{\zeta}_{j}+\sigma_{jj}^{2}-r_{j}}}}.$

Here, for any $\delta_{j}$, the parameter $r_{j}$ can be found using Corollary
IV.4. Note that compared to $\epsilon_{ij}^{(p)}$ and $\epsilon_{ij}^{(d)}$,
the expressions for $\widetilde{\epsilon}_{ij}^{(p)}$ and
$\widetilde{\epsilon}_{ij}^{(d)}$ have an additional $\sigma_{jj}^{2}$ in the
denominator. This is a consequence of the fact that after aggregating
$\underline{\widetilde{\mathbf{x}}}_{j}$ from its neighbors, node $j$ adds
privacy noise to its own data before transmitting to the PS.

##  V Privacy-constrained weight and variance optimization

When deriving the utility-privacy tradeoff, our objective is to minimize the
MSE at the PS subject to desired privacy guarantees, namely
$(\underline{\epsilon}_{ij},\underline{\delta}_{ij}p_{ij})$ node-node local
differential privacy. Here,
$\underline{\epsilon}_{ij},\underline{\delta}_{ij}$ are pre-specified
parameters that quantify the extent to which node $i$ trusts the link $i\to j$
against an eavesdropper. While finding the optimal collaboration scheme, it is
important to consider the fact that due to relaying, a specific node $i$’s
data is received via multiple nodes at the PS. More precisely, the expected
bias in the contribution of $\mathbf{x}_{i}$ to the estimated mean
($\widehat{\overline{\mathbf{x}}}$) is given by $(S_{i}-1)\mathbf{x}_{i}$, and
the cumulative bias from all the nodes is
$\beta(\mathbf{p},\mathbf{P},\mathbf{A})=\sum_{i\in[n]}\left\lvert
S_{i}-1\right\rvert$. Consequently, we aim to solve the following bias-
regularized MSE minimization problem:

$\displaystyle\min_{\mathbf{A},\boldsymbol{\Sigma}}\;\sigma_{\rm
tiv}^{2}(\mathbf{p},\mathbf{P},\mathbf{A})+\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma})+\lambda\beta(\mathbf{p},\mathbf{P},\mathbf{A})$
$\displaystyle\text{ s.t.
}\left[2\log\left(\frac{1.25}{\underline{\delta}_{ij}}\right)\right]^{\frac{1}{2}}\frac{2\alpha_{ij}{\rm
R}}{\sigma_{ij}}\leq\underline{\epsilon}_{ij},\;\alpha_{ij}\geq
0,\;\sigma_{ij}\geq 0.$ (15)

Here, the constraints require that the collaboration weights and privacy noise
be non-negative, and ensure that the peer-to-peer privacy constraints are
respected. Since the privacy constraints are cone constraints (denoted as
${\cal K}$ in Fig. 6), and are separable with respect to the optimization
variables $(\alpha_{ij},\sigma_{ij})$, we apply projected gradient descent to
solve (V). Furthermore, $\lambda$ controls the strength of the regularization
and we study its impact in §VI. Instead of $\ell_{1}$, we can also choose an
$\ell_{2}$-regularization term to control the bias, i.e.,
$\beta(\mathbf{p},\mathbf{P},\mathbf{A})=\sum_{i\in[n]}\left(S_{i}-1\right)^{2}$
(ref. to §V-B).

###  V-A Projected gradient descent for MSE minimization

Let us denote
$\beta_{ij}\triangleq\frac{2\mathrm{R}}{\underline{\epsilon}_{ij}}\left[2\log\left(\frac{1.25}{\underline{\delta}_{ij}}\right)\right]^{\frac{1}{2}}$.
For each $i,j\in[n]$, we start with a feasible iterate
$\left(\alpha_{ij}^{(0)},\sigma_{ij}^{(0)}\right)$ that satisfies
$\alpha_{ij}^{(0)}\geq 0$, $\sigma_{ij}^{(0)}\geq\beta_{ij}\alpha_{ij}^{(0)}$,
and take gradient steps followed by projections onto the cone, which can be
computed in closed form. The Pseudocode for the weight and noise variance
optimization algorithm is provided in Alg. 3, and the projection expressions
are derived in App. E. From [44], we know that the iterates of projected
gradient descent for a Lipschitz objective converges to an
$\varepsilon$-stationary point within
$\mathrm{O}\left(\varepsilon^{-2}\right)$ iterations.222We choose projected
gradient descent for its simplicity and ease of implementation. Other
algorithms can also be used to solve (V). In §V-B below, we show that for a
simple network topology, the solution of (V) can be obtained in closed form.

Algorithm 3 PriCER: Weight and noise variance optimization with projected
gradient descent

Input: Feasible initial $\mathbf{A}^{(0)}$ and $\boldsymbol{\Sigma}^{(0)}$.

Maximal number of iterations: $T$

Output: Weight matrix $\mathbf{A}_{*}=\mathbf{A}^{(T)}$ and noise variances
$\boldsymbol{\Sigma}_{*}=\boldsymbol{\Sigma}^{(T)}$ that minimizes (V).

for $t=1$ to $T$ for all $i,j\in[n]$ do

Take gradient descent steps:
$\displaystyle\widetilde{\alpha}_{ij}\leftarrow\alpha_{ij}^{(t-1)}-\eta_{\alpha}\left(\frac{\partial{\cal
E}}{\partial\alpha_{ij}}\right)_{\mathbf{A}^{(t-1)}}$ and,
$\displaystyle\widetilde{\sigma}_{ij}\leftarrow\sigma_{ij}^{(t-1)}-\eta_{\sigma}\left(\frac{\partial{\cal
E}}{\partial\sigma_{ij}}\right)_{\boldsymbol{\Sigma}^{(t-1)}}$

Project onto cone constraints:
$\displaystyle\left(\alpha_{ij}^{(t)},\sigma_{ij}^{(t)}\right)$
$\displaystyle=$ $\displaystyle\begin{cases}\hskip
28.45274pt\left(0,\widetilde{\sigma}_{ij}\right)\quad\text{ if
}\;\widetilde{\sigma}_{ij}\geq 0\text{ and }\widetilde{\alpha}_{ij}<0,\\\
\left(\left(\frac{\widetilde{\alpha}_{ij}+\beta_{ij}\widetilde{\sigma}_{ij}}{1+\beta_{ij}^{2}}\right)_{+},\left(\frac{\beta_{ij}(\widetilde{\alpha}_{ij}+\beta_{ij}\widetilde{\sigma}_{ij})}{1+\beta_{ij}^{2}}\right)_{+}\right)\\\
\qquad\text{ if }\widetilde{\sigma}_{ij}<0\text{ or
}\left\\{\widetilde{\sigma}_{ij}\geq 0\text{ and
}\widetilde{\sigma}_{ij}<\beta_{ij}\widetilde{\alpha}_{ij}\right\\},\\\ \hskip
28.45274pt\left(\widetilde{\alpha}_{ij},\widetilde{\sigma}_{ij}\right)\quad\text{
otherwise}.\end{cases}$

end for

###  V-B Optimal collaboration over an Erdös-Rényi Topology

$\displaystyle\alpha_{*}(\lambda)$
$\displaystyle=q\left(\frac{\mathrm{R}^{2}}{\lambda
n^{2}}\left(1-p+\frac{d\xi^{2}}{\epsilon^{2}}\right)\left(\frac{\mathrm{R}^{2}}{\lambda
n^{2}}(1+(m-1)q)+q\right)+mpq\left(\frac{\mathrm{R}^{2}}{\lambda
mn}(1+(m-1)q)+q\right)\right)^{-1}\left(\frac{\mathrm{R}^{2}}{\lambda
n}+1\right),$ $\displaystyle\gamma_{*}(\lambda)$
$\displaystyle=\left(\frac{\mathrm{R}^{2}}{n^{2}}\left(1+(m-1)q\right)+\lambda
q\right)^{-1}\left(\frac{\mathrm{R}^{2}}{n^{2}}\left(n-(1+(m-1)q)(n-m)p\alpha_{*}(\lambda)\right)+\lambda\right)\quad\text{and,}\quad\sigma_{*}(\lambda)=\xi\mathrm{R}\frac{\alpha_{*}(\lambda)}{\epsilon}.$
(16)

Consider a setup of $n$ nodes that can collaborate with each other over an
Erdös-Rényi graph, i.e., $p_{ij}=p$ for $i\neq j$ and $p_{ii}=1$ for all
$i,j\in[n]$. Furthermore, suppose only a subset of these nodes, denoted by
${\cal M}\subseteq[n]$ with cardinality $|{\cal M}|=m$, can communicate with
the PS reliably, i.e., $p_{i}=q$ if $i\in{\cal M}$, and $p_{i}=0$ otherwise.
Moreover, $(\epsilon_{ij},\delta_{ij})=(\epsilon,\delta)$ for all
$i\in\overline{{\cal M}},j\in{\cal M}$, where $\overline{{\cal
M}}=[n]\setminus{\cal M}$.

From symmetry, for some $\alpha,\gamma>0$, we have $\alpha_{ii}=\gamma$ for
$i\in[n]$, $\alpha_{ij}=\alpha$ for $j\in{\cal M},i\in\overline{{\cal
M}}\setminus\\{j\\}$, and $\alpha_{ij}=0$. Furthermore, $\sigma_{ii}=0$ as
each node trusts itself, and $\sigma_{ij}=\sigma$ whenever $j\neq i$ and
$\alpha_{ij}>0$. We consider
$\beta(\mathbf{p},\mathbf{P},\mathbf{A})=\sum_{i\in[n]}\left(S_{i}-1\right)^{2}$
for analytical tractability. We show in App. F that the solution of (V) is
given by (V-B) below. When $\lambda\to\infty$, we get $\alpha_{*}=(mpq)^{-1}$
and $\gamma_{*}=q^{-1}$. With these weights,

$\displaystyle{\rm
MSE}_{*}=\mathrm{R}^{2}\left[\frac{(n-m)}{n^{2}pq}\left(\frac{1-p}{m}+\frac{\xi^{2}d}{\epsilon^{2}}\right)+\frac{1-q}{mq}\right].$
(17)

In order to compare with a setup with no collaboration, consider $p_{i}=q$ for
$i\in{\cal M}$, and $p_{i}=q^{\prime}$ for $i\in\overline{{\cal M}}$, where
$q^{\prime}\to 0$. In the absence of collaboration, in order to maintain an
unbiased estimate the PS, node $i$ should transmit $p_{i}^{-1}\mathbf{x}_{i}$
to the PS. In this case, there are no peer-to-peer privacy concerns. However,
the MSE, which is given by

$\displaystyle\frac{1}{n^{2}}\mathbb{E}\left\lVert\sum_{i\in[n]}\left(\tau_{i}\frac{\mathbf{x}_{i}}{p_{i}}-\mathbf{x}_{i}\right)\right\rVert^{2}=\frac{\mathrm{R}^{2}}{n^{2}}\left(\frac{m}{q}+\frac{n-m}{q^{\prime}}-n\right),$

increases to $\infty$ as $q^{\prime}\to 0$. On the other hand, (17) shows that
the MSE with collaboration is finite.

Central privacy guarantees for PriCER of Erdös-Rényi topology: In App. F, we
show that when $m<n$ and $p>\frac{7}{8}$, the privacy leakage at the relay for
preserving anonymity of the identity of a participating node, as defined in
Thm. IV.2 scales as
$\epsilon_{ij}^{(p)}=\mathrm{O}\left(\frac{1}{m\sqrt{n-m}}\right)$. Moreover,
from Thm. IV.3, since $\epsilon_{ij}^{(d)}=2\epsilon_{ij}^{(p)}$, the same
scaling also holds for privacy leakage for protecting the local data.

##  VI Numerical simulations

Convergence of Alg. 3: The objective function of (V) is, in general, non-
convex. In Fig. 5, we see that projected gradient descent with constant
learning rate $\eta_{\alpha}=\eta_{\sigma}=0.01$, converges in the cases
shown. This value of learning rate has been chosen after tuning it over the
set $[0.001,0.01,0.1]$. To obtain these plots, $n=10$ nodes are considered
with connectivities to the PS given by
$\mathbf{p}=[0.1,0.1,0.8,0.1,0.1,0.9,0.1,0.1,0.9,0.1]$. Note that some of
these probabilities are good, some mediocre, and some quite low. All plots are
averaged over $4$ independent random initializations for gradient descent.
Furthermore, the nodes are connected to each other according to an Erdős-Rényi
topology, where for all $i,j\in[n]$, the edge between nodes $i$ and $j$ is
present with probability $p_{ij}=p_{c}=0.9$. Nodes only trust their immediate
$1$-hop neighbors, and privacy parameters are chosen accordingly as follows:
For every $i\in[n]$, $\underline{\epsilon}_{ij}=\varepsilon_{ngbr}=10^{3}$ if
$j=i$, $j=(i+1)\;{\rm mod}\;n$, or $j=(i-1)\;{\rm mod}\;n$, and
$\underline{\epsilon}_{ij}=\varepsilon_{other}=1$ otherwise.
$\delta_{ij}=10^{-3}$ for all $i,j\in[n]$. The ensures that there is
effectively no privacy constraint for nodes communicating with their
neighbors.

As expected, with higher values of the bias regularization parameter
$\lambda$, the optimal MSE value at convergence increases. This leads to a
bias-MSE tradeoff between the optimized MSE, i.e., $\sigma_{\rm
tiv}^{2}(\mathbf{p},\mathbf{P},\mathbf{A}_{*})+\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma}_{*})$, and the total bias at
the PS, i.e., $\beta(\mathbf{p},\mathbf{P},\mathbf{A}_{*})$, where
$\mathbf{A}_{*}$ and $\boldsymbol{\Sigma}_{*}$ denote the optimized weights
and privacy noise variance at convergence. We study this tradeoff in Table I,
which shows the total bias and the optimized MSE, respectively. We sweep both
the bias regularization parameter $\lambda$ and the node-node connectivity
probability $(p_{c})$ for the Erdős-Rényi topology.

Figure 2: Variation of MSE with number of trustworthy neighbors

Figure 3: Variation of PIV with number of trustworthy neighbors

Figure 4: Topology for $\rm K$-means clustering. $p_{i}$ and $p_{ij}$ are
determined according to [45].

Figure 5: Projected gradient descent with $2$ trustworthy neighbors TABLE I:
Bias - MSE tradeoff Total bias $\beta(\mathbf{p},\mathbf{P},\mathbf{A}_{*})$
---
$p_{c}$ $\downarrow$ $\lambda$ $\rightarrow$ | $0$ | $0.1$ | $0.5$
$0.1$ | $12.799$ | $0.4125$ | $\bf 0.0025$
$0.5$ | $12.122$ | $0.0082$ | $\bf 0.0020$
MSE $\sigma^{2}_{\rm
tiv}(\mathbf{p},\mathbf{P},\mathbf{A}_{*})+\sigma^{2}_{\rm
pr}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma}_{*})$
$p_{c}$ $\downarrow$ $\lambda$ $\rightarrow$ | $0$ | $0.1$ | $0.5$
$0.1$ | $\bf 0.0449$ | $0.3422$ | $0.4039$
$0.5$ | $\bf 0.0448$ | $0.1493$ | $0.1538$

Variation with number of trustworthy neighbors: Next, we study how increased
collaboration can help in reducing the MSE. In Fig. 4, we consider a topology
in which $n=10$ nodes are arranged as a ring (as before), and each node trusts
$k$-hop neighbors, where we vary $k$ along the X-axis. Furthermore, we
consider that only one node has good connectivity to the PS, i.e., $p_{i}=0.9$
if $i=0$, otherwise $p_{i}=0.1$. This setup ensures that collaboration is
critical to ensure a small MSE. We set
$\underline{\epsilon}_{ij}=\varepsilon_{other}$ whenever a node does not trust
another node As expected, the MSE decreases as collaboration amongst
trustworthy neighbors (i.e., $k$) increases. As opposed to the settings in
prior works [24, 23, 25], here, the collaboration is not limited by a lack of
communication opportunity between the nodes, but rather, their unwillingness
to communicate with other (untrustworthy) nodes. Consequently, even when node-
node connectivity is good, i.e., $p_{c}=0.9$, the optimized collaboration
weight $\alpha_{ij}^{*}$ is small when node $i$ does not trust node $j$.
Moreover, while the above-mentioned works show that collaboration amongst
nodes helps in reducing the topology induced variance due to poor connectivity
within the network, we show that increased collaboration also helps in
reducing the privacy induced variance. This is shown in Fig. 4, where a higher
value of $k$ implies that a node does not need to perturb its data too much
while sharing it with its neighbors it trusts, resulting in a smaller PIV.

Distributed $\rm K$-means clustering: We also evaluate our algorithm on the
task of clustering a dataset distributed across $n$ nodes into $\rm K$
clusters. Each cluster is represented by its centroid and any datapoint is
clustered to its nearest centroid. In distributed $\rm K$-means clustering,
each node first computes $\rm K$ local centroids. On each node, this is done
by initializing the centroids according to the $\rm K$-means++ algorithm [46],
clustering the local datapoints to their nearest centroid, recomputing the
cluster means, and repeating this process. Once the local centroids have been
computed on each node, they are transmitted to the central PS over
intermittently failing communication links. The PS computes the average of
these local centroids to obtain the global centroids, broadcasts them to each
of the nodes. Each node then uses these centroids as their new initialization
and repeats the local clustering process. This process is repeated over
multiple iterations. We choose relative inertia as the evaluation metric for
the clustering performance. Inertia is defined as the sum of squared distances
of each datapoint $\mathbf{x}_{i}$ from its closest cluster $c(x_{i})$.
Relative inertia is defined as the ratio of the inertia of our distributed
$\rm K$-means algorithm and the inertia of the centralized variant, wherein
the entire dataset is assumed to be present on a single node. Mathematically,
$\text{Inertia (relative)}\triangleq\text{Inertia (distributed)}/\text{Inertia
(centralized)}$ where,

$\text{Inertia}\triangleq\sum_{i\;\in\;\text{dataset}}\left(x_{i}-c(\mathbf{x}_{i})\right)^{2}$
(18)

We consider clustering two datasets: (i) Raw CIFAR-10 images [47], and
$\rm(ii)$ Fashion-MNIST [48] image embeddings extracted using pre-trained
MobileNet-V3 [49]. We consider $n=10$ nodes, $\rm K=10$ clusters, $10$
communication rounds with the PS and $5$ local iterations in each round, over
three setups: $\rm(i)$ sole good node (i.e., as before, only one node has
$p_{i}=0.9$ and all other node have $p_{i}=0.1$) and no collaboration,
$\rm(ii)$ sole good node with $6$ trustworthy neighbors which enables
collaboration via PriCER with parameters
$(p_{ij}=0.9,\epsilon_{ij}=0.01,\delta=10^{-3})$, $\rm(iii)$ a scattered
topology as shown in Fig. 4, where nodes do not collaborate with each other,
and $\rm(iv)$ the same scattered topology with PriCER collaboration with
parameters $(\epsilon_{ij}=0.01,\delta=10^{-3})$. The connectivity
probabilities between nodes or between the node and the PS is a function of
distance ($\rm\delta$), given by
$p=\min\left(1,\mathrm{e}^{-\delta/30+5.2}\right)$. This expression is used to
model the outage probability of mmWave communication links [45, Eq. 8a], and
our scattered topology is visualized in Fig. 4. We assume that two nodes $i$
and $j$ trust each other if $p_{ij}>0.5$, i.e., they have a relatively high
probability of connectivity. From Tab. II, we can see that the relative
inertia for clustering is smaller when the nodes collaborate with each other.

TABLE II: Relative inertia of $\rm K$-means clustering for different datasets over “sole good node” and “scattered” network topologies. Smaller values indicate better performance Setup $\downarrow$ Dataset $\rightarrow$ |  CIFAR-10 (raw images) |  FMNIST (MobileNet-V3)
---|---|---
Sole good node (no colab) |  $2.101\pm 0.007$ |  $6.226\pm 3.054$
Sole good node (PriCER) |  $\mathbf{1.689\pm 0.030}$ |  $\mathbf{4.168\pm 2.474}$
Scattered (no colab) |  $4.454\pm 0.758$ |  $6.593\pm 0.626$
Scattered (PriCER) |  $\mathbf{1.262\pm 0.019}$ |  $\mathbf{1.315\pm 0.085}$

##  VII Conclusions

We have considered the problem of mean estimation over intermittently
connected networks with collaborative relaying subject to differential privacy
constraints. The nodes participating in the collaboration do not trust each
other completely and, in order to ensure privacy, they scale and perturb their
local data when sharing with others. We have shown that local and central
privacy can be guaranteed by leveraging the different sources of stochasticity
in our setup, namely, the Gaussian perturbations added by a node before
collaborating, as well as the intermittent nature of the node-node and node-PS
connectivities. As the MSE of the mean estimated at the PS was comprised of
the topology induced variance and the privacy induced variance, we have
proposed a two-stage consensus algorithm (PriCER) that jointly optimizes the
scaling weights and perturbation noise variance so as to minimize the MSE
while respecting the peer-to-peer privacy constraints. This joint optimization
also introduces a tradeoff between the MSE and the bias of the estimated mean,
and we traverse this tradeoff curve by tuning the bias regularization
hyperparameter. We have performed numerical simulations and shown how PriCER
can do collaborative, yet private, mean estimation over intermittently
connected networks, and that it outperforms non-collaborative strategies.

## References

  * [1] R. Saha, M. Seif, M. Yemini, A. J. Goldsmith, and H. V. Poor, “Collaborative mean estimation over intermittently connected networks with peer-to-peer privacy,” in _Proceedings of the 2023 IEEE International Symposium on Information Theory_ , 2023, pp. 174–179.
  * [2] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_. PMLR, 2017, pp. 1273–1282.
  * [3] M.-F. F. Balcan, S. Ehrlich, and Y. Liang, “Distributed $k$-means and $k$-median clustering on general topologies,” _Advances in Neural Information Processing Systems_ , vol. 26, p. 1995–2003, 2013.
  * [4] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan, “Distributed mean estimation with limited communication,” in _Proceedings of the International Conference on Machine Learning_. PMLR, 2017, pp. 3329–3337.
  * [5] S. Kar and J. M. F. Moura, “Distributed consensus algorithms in sensor networks with imperfect communication: Link failures and channel noise,” _IEEE Transactions on Signal Processing_ , vol. 57, no. 1, pp. 355–369, 2009.
  * [6] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” in _Proceedings of the International Conference on Machine Learning_. PMLR, 2017, pp. 3368–3376.
  * [7] S. Kar and J. M. F. Moura, “Sensor networks with random links: Topology design for distributed consensus,” _IEEE Transactions on Signal Processing_ , vol. 56, no. 7, pp. 3315–3326, 2008.
  * [8] S. Kar, J. M. F. Moura, and K. Ramanan, “Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication,” _IEEE Transactions on Information Theory_ , vol. 58, no. 6, pp. 3575–3605, 2012.
  * [9] D. Jhunjhunwala, A. Mallick, A. Gadhikar, S. Kadhe, and G. Joshi, “Leveraging spatial and temporal correlations in sparsified mean estimation,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 14 280–14 292, 2021.
  * [10] M. Gapeyenko, A. Samuylov, M. Gerasimenko, D. Moltchanov, S. Singh, M. R. Akdeniz, E. Aryafar, N. Himayat, S. Andreev, and Y. Koucheryavy, “On the temporal effects of mobile blockers in urban millimeter-wave cellular scenarios,” _IEEE Transactions on Vehicular Technology_ , vol. 66, no. 11, pp. 10 124–10 138, Nov 2017.
  * [11] Y. Yan and Y. Mostofi, “Co-optimization of communication and motion planning of a robotic operation under resource constraints and in fading environments,” _IEEE Transactions on Wireless Communications_ , vol. 12, no. 4, pp. 1562–1572, April 2013.
  * [12] M. M. Zavlanos, M. B. Egerstedt, and G. J. Pappas, “Graph-theoretic connectivity control of mobile robot networks,” _Proceedings of the IEEE_ , vol. 99, no. 9, pp. 1525–1540, Sep. 2011.
  * [13] N. Michael, M. M. Zavlanos, V. Kumar, and G. J. Pappas, “Maintaining connectivity in mobile robot networks,” in _Experimental Robotics_ , 2009, pp. 117–126.
  * [14] M. Yemini, S. Gil, and A. J. Goldsmith, “Exploiting local and cloud sensor fusion in intermittently connected sensor networks,” in _Proceedings of the 2020 IEEE Global Communications Conference_ , December 2020.
  * [15] M. Yemini, S. Gil, and A. J. Goldsmith, “Cloud-cluster architecture for detection in intermittently connected sensor networks,” _IEEE Transactions on Wireless Communications_ , vol. 22, no. 2, pp. 903–919, 2023.
  * [16] X. Gu, K. Huang, J. Zhang, and L. Huang, “Fast federated learning in the presence of arbitrary device unavailability,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [17] Y. Yan, C. Niu, Y. Ding, Z. Zheng, F. Wu, G. Chen, S. Tang, and Z. Wu, “Distributed non-convex optimization with sublinear speedup under intermittent client availability,” _ArXiv_ , vol. abs/2002.07399, 2020.
  * [18] S. Wang and M. Ji, “A unified analysis of federated learning with arbitrary client participation,” in _Advances in Neural Information Processing Systems_ , vol. 35, 2022, pp. 19 124–19 137.
  * [19] Y. Ruan, X. Zhang, S.-C. Liang, and C. Joe-Wong, “Towards flexible device participation in federated learning,” in _Proceedings of the 24th International Conference on Artificial Intelligence and Statistics_ , vol. 130, 2021, pp. 3403–3411.
  * [20] H. Yang, X. Zhang, P. Khanduri, and J. Liu, “Anarchic federated learning,” in _Proceedings of the 39th International Conference on Machine Learning_ , vol. 162, 2022, pp. 25 331–25 363.
  * [21] Y. Sun, Y. Mao, and J. Zhang, “Mimic: Combating client dropouts in federated learning by mimicking central updates,” _IEEE Transactions on Mobile Computing_ , p. 1–13, 2024.
  * [22] S. Wang and M. Ji, “A lightweight method for tackling unknown participation statistics in federated averaging,” in _Proceedings of the 12th International Conference on Learning Representations_ , 2024.
  * [23] R. Saha, M. Yemini, E. Ozfatura, D. Gunduz, and A. Goldsmith, “Colrel: Collaborative relaying for federated learning over intermittently connected networks,” in _Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022)_ , 2022. [Online]. Available: https://openreview.net/forum?id=8b0RHdh2Xd0
  * [24] M. Yemini, R. Saha, E. Ozfatura, D. Gündüz, and A. J. Goldsmith, “Semi-decentralized federated learning with collaborative relaying,” in _Proceedings of the 2022 IEEE International Symposium on Information Theory_ , 2022, pp. 1471–1476.
  * [25] M. Yemini, R. Saha, E. Ozfatura, D. Gündüz, and A. J. Goldsmith, “Robust semi-decentralized federated learning via collaborative relaying,” _IEEE Transactions on Wireless Communications (to appear)_ , 2023.
  * [26] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [27] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021.
  * [28] B. Balle, G. Barthe, and M. Gaboardi, “Privacy amplification by subsampling: Tight analyses via couplings and divergences,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [29] Y. Zhu and Y.-X. Wang, “Poisson subsampled Rényi differential privacy,” in _Proceedings of the International Conference on Machine Learning (ICML)_. PMLR, 2019, pp. 7634–7642.
  * [30] B. Luo, W. Xiao, S. Wang, J. Huang, and L. Tassiulas, “Tackling system and statistical heterogeneity for federated learning with adaptive client sampling,” in _Proceedings of the 2022 IEEE International Conference on Computer Communications_ , 2022, pp. 1739–1748.
  * [31] E. Rizk, S. Vlaski, and A. H. Sayed, “Federated learning under importance sampling,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 5381–5396, 2022.
  * [32] B. Balle, P. Kairouz, B. McMahan, O. Thakkar, and A. Guha Thakurta, “Privacy amplification via random check-ins,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 4623–4634, 2020.
  * [33] H. Asi, V. Feldman, and K. Talwar, “Optimal algorithms for mean estimation under local differential privacy,” in _Proceedings of the 39th International Conference on Machine Learning_ , vol. 162, 2022, pp. 1046–1056.
  * [34] R. Cummings, V. Feldman, A. McMillan, and K. Talwar, “Mean estimation with user-level privacy under data heterogeneity,” in _Advances in Neural Information Processing Systems_ , vol. 35, 2022, pp. 29 139–29 151.
  * [35] B. Isik, W.-N. Chen, A. Ozgur, T. Weissman, and A. No, “Exact optimality of communication-privacy-utility tradeoffs in distributed mean estimation,” in _Proceedings of the 37th Conference on Neural Information Processing Systems_ , 2023.
  * [36] M. Gaboardi, R. Rogers, and O. Sheffet, “Locally private mean estimation: $z$-test and tight confidence intervals,” in _Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics_ , vol. 89, 2019, pp. 2545–2554.
  * [37] Q. Xue, Y. Zhu, and J. Wang, “Mean estimation over numeric data with personalized local differential privacy,” _Frontiers of Computer Science_ , vol. 16, 2021.
  * [38] M. M. Amiri and D. Gündüz, “Federated learning over wireless fading channels,” _IEEE Trans. Wireless Comms._ , vol. 19, no. 5, pp. 3546–3557, 2020.
  * [39] E. Ozfatura, S. Rini, and D. Gündüz, “Decentralized SGD with over-the-air computation,” in _IEEE Glob. Commun. Conf_ , 2020.
  * [40] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning (extended version),” arxiv:1812.11494, 2019.
  * [41] B. Hasircioglu and D. Gunduz, “Private wireless federated learning with anonymous over-the-air computation,” arxiv:2011.08579, 2021.
  * [42] M. Seif, W.-T. Chang, and R. Tandon, “Privacy amplification for federated learning via user sampling and wireless aggregation,” arxiv:2103.01953, 2021. [Online]. Available: https://ieeexplore.ieee.org/document/9518031
  * [43] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” in _International conference on machine learning_. PMLR, 2015, pp. 1376–1385.
  * [44] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University press, 2004.
  * [45] M. R. Akdeniz, Y. Liu, M. K. Samimi, S. Sun, S. Rangan, T. S. Rappaport, and E. Erkip, “Millimeter wave channel modeling and cellular capacity evaluation,” _IEEE Journal on Selected Areas in Communications_ , vol. 32, no. 6, pp. 1164–1179, 2014.
  * [46] D. Arthur and S. Vassilvitskii, “K-Means++: The Advantages of Careful Seeding,” vol. 8, 01 2007, pp. 1027–1035.
  * [47] A. Krizhevsky, V. Nair, and G. Hinton, “CIFAR-10 (Canadian Institute For Advanced Research).” [Online]. Available: http://www.cs.toronto.edu/~kriz/cifar.html
  * [48] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms,” 2017.
  * [49] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “MobileNets: Efficient convolutional neural networks for mobile vision applications,” 2017.
  * [50] M. Mitzenmacher and E. Upfal, _Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis_. Cambridge University press, 2017.

##  Appendix A Estimation error analysis of PriCER:
Proof of Thm. III.1

Note that the global estimate at the PS is

$\widehat{\overline{\mathbf{x}}}=\frac{1}{n}\sum_{i\in[n]}\tau_{i}\sum_{j\in[n]}\tau_{ji}(\alpha_{ji}\mathbf{x}_{j}+\mathbf{n}_{ji}).$
(19)

Consequently, the MSE can be written as

$\displaystyle\mathbb{E}\left\lVert\frac{1}{n}\sum_{i\in[n]}\tau_{i}\sum_{j\in[n]}\tau_{ji}(\alpha_{ji}\mathbf{x}_{j}+\mathbf{n}_{ji})-\frac{1}{n}\sum_{i\in[n]}\mathbf{x}_{i}\right\rVert_{2}^{2}$
$\displaystyle=\underbrace{\mathbb{E}\left\lVert\frac{1}{n}\sum_{i\in[n]}\tau_{i}\sum_{j\in[n]}\tau_{ji}\alpha_{ji}\mathbf{x}_{j}-\frac{1}{n}\sum_{i\in[n]}\mathbf{x}_{i}\right\rVert_{2}^{2}}_{\text{\rm
Topology Induced Variance (TIV)}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\underbrace{\mathbb{E}\left\lVert\frac{1}{n}\sum_{i\in[n]}\tau_{i}\sum_{j\in[n]}\tau_{ji}\mathbf{n}_{ji}\right\rVert_{2}^{2}}_{\text{\rm
Privacy Induced Variance (PIV)}},$ (20)

where the expectation is taken over the random connectivity and the local
perturbation mechanism, and the equality follows because for any $j\in[n]$,
the cross term is
$\mathbb{E}\left[\sum_{i\in[n]}\tau_{j}\tau_{ij}\alpha_{ij}\mathbf{x}_{j}^{\top}\mathbb{E}[\mathbf{n}_{ij}]\right]=0$.

The first term TIV in (A) is solely affected by the intermittent connectivity
of nodes. The technique to upper bound it is similar to what is done in [23,
Thm. 3.2], except for the fact that we do not consider the unbiasedness
constraint present in [23]. We allow for biased estimates at the PS and
additional bias terms appear in the upper bound for TIV. Nevertheless, the
proof is presented here for the sake of completeness. Recall our notation
$S_{i}=\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}$. The TIV is then

$\displaystyle\mathbb{E}\left\lVert\frac{1}{n}\sum_{i\in[n]}\tau_{i}\sum_{j\in[n]}\alpha_{ji}\tau_{ji}\mathbf{x}_{j}-\frac{1}{n}\sum_{i\in[n]}\mathbf{x}_{i}\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum_{i\in[n]}\mathbb{E}\left[\left(\sum_{j\in[n]}\tau_{j}\tau_{ij}\alpha_{ij}-1\right)^{2}\right]\left\lVert\mathbf{x}_{i}\right\rVert^{2}$
$\displaystyle+$ $\displaystyle\frac{1}{n^{2}}\sum_{\stackrel{{\scriptstyle
i,l\in[n]:}}{{i\neq
l}}}\mathbb{E}\left[\left(\sum_{j\in[n]}\tau_{j}\tau_{ij}\alpha_{ij}-1\right)\right.$
$\displaystyle\qquad\qquad\qquad\left.\left(\sum_{m\in[n]}\tau_{m}\tau_{lm}\alpha_{lm}-1\right)\right]\mathbf{x}_{i}^{\top}\mathbf{x}_{l}.$
(21)

In the first term of (A), the coefficient of $\lVert\mathbf{x}_{i}\rVert^{2}$
inside the $\sum_{i\in[n]}$ can be simplified as

$\displaystyle\mathbb{E}\left[\left(\sum_{j\in[n]}\tau_{j}\tau_{ij}\alpha_{ij}-1\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\sum_{j\in[n]}\mathbb{E}\left[\tau_{j}^{2}\tau_{ij}^{2}\alpha_{ij}^{2}\right]+\sum_{\begin{subarray}{c}j_{1},j_{2}\in[n]:\\\
j_{1}\neq
j_{2}\end{subarray}}\mathbb{E}\left[\tau_{j_{1}}\tau_{j_{2}}\tau_{ij_{1}}\tau_{ij_{2}}\alpha_{ij_{1}}\alpha_{ij_{2}}\right]$
$\displaystyle\qquad\qquad\qquad\qquad-2\sum_{j\in[n]}\mathbb{E}\left[\tau_{j}\tau_{ij}\alpha_{ij}\right]+1$
$\displaystyle=\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}^{2}+\sum_{\begin{subarray}{c}j_{1},j_{2}\in[n]:\\\
j_{1}\neq
j_{2}\end{subarray}}p_{j_{1}}p_{j_{2}}p_{ij_{1}}p_{ij_{2}}\alpha_{ij_{1}}\alpha_{ij_{2}}$
$\displaystyle\qquad\qquad\qquad\qquad-2\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}+1$
$\displaystyle=\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}^{2}+\left(\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}\right)^{2}-\sum_{j\in[n]}p_{j}^{2}p_{ij}^{2}\alpha_{ij}^{2}$
$\displaystyle\qquad\qquad\qquad\qquad-2\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}+1$
$\displaystyle=\sum_{j\in[n]}p_{j}p_{ij}\left(1-p_{j}p_{ij}\right)\alpha_{ij}^{2}+S_{i}(S_{i}-2)+1$
$\displaystyle=\sum_{j\in[n]}p_{j}p_{ij}\left(1-p_{j}p_{ij}\right)\alpha_{ij}^{2}+(S_{i}-1)^{2}.$
(22)

In the second term of (A), the coefficient of
$\mathbf{x}_{i}^{\top}\mathbf{x}_{l}$ inside the
$\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq l\end{subarray}}$ can be
simplified as

$\displaystyle\sum_{j\in[n]}p_{j}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}+p_{i}p_{l}\mathrm{E}_{\\{i,l\\}}\alpha_{il}\alpha_{li}+\sum_{\begin{subarray}{c}m\in[n]:\\\
m\neq l,i\end{subarray}}p_{l}p_{m}p_{il}p_{lm}\alpha_{il}\alpha_{lm}$
$\displaystyle\hskip 56.9055pt+\sum_{\begin{subarray}{c}j\in[n]:\\\ j\neq
l\end{subarray}}\sum_{\begin{subarray}{c}m\in[n]:\\\ m\neq
j\end{subarray}}p_{j}p_{m}p_{ij}p_{lm}\alpha_{ij}\alpha_{lm}-S_{i}-S_{l}+1$
$\displaystyle=\sum_{j\in[n]}p_{j}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}+p_{i}p_{l}\mathrm{E}_{\\{i,l\\}}\alpha_{il}\alpha_{li}$
$\displaystyle\hskip 22.76228pt-
S_{i}-S_{l}+1+p_{l}p_{il}\alpha_{il}(S_{l}-p_{l}p_{ll}\alpha_{ll}-p_{i}p_{li}\alpha_{li})$
$\displaystyle\hskip
22.76228pt+S_{l}(S_{i}-p_{l}p_{il}\alpha_{il})-\sum_{j\in[n]}p_{j}^{2}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}+p_{l}^{2}p_{il}p_{ll}\alpha_{il}\alpha_{ll}$
$\displaystyle=\sum_{j\in[n]}p_{j}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}+p_{i}p_{l}\mathrm{E}_{\\{i,l\\}}\alpha_{il}\alpha_{li}-S_{i}-S_{l}+1$
$\displaystyle\hskip 28.45274pt-
p_{i}p_{l}p_{il}p_{li}\alpha_{il}\alpha_{li}+S_{i}S_{l}-\sum_{j\in[n]}p_{j}^{2}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}.$
(23)

Hence, the second term of (A) is given by

$\displaystyle\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq
l\end{subarray}}\left[\sum_{j\in[n]}p_{j}(1-p_{j})p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\right.$
$\displaystyle\left.+p_{i}p_{l}(\mathrm{E}_{\\{i,l\\}}-p_{il}p_{li})\alpha_{il}\alpha_{li}+S_{i}S_{l}-S_{i}-S_{l}+1\right.\Biggr{]}\mathbf{x}_{i}^{\top}\mathbf{x}_{l}.$
(24)

Subsequently, (A) simplifies to

$\displaystyle\frac{1}{n^{2}}\sum_{i,j\in[n]}p_{j}p_{ij}\left(1-p_{ij}\right)\alpha_{ij}^{2}\lVert\mathbf{x}_{i}\rVert^{2}+\frac{1}{n^{2}}\sum_{i\in[n]}(S_{i}-1)^{2}\lVert\mathbf{x}_{i}\rVert^{2}$
$\displaystyle\hskip
56.9055pt+\frac{1}{n^{2}}\sum_{i,j,l\in[n]}p_{j}(1-p_{j})p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\mathbf{x}_{i}^{\top}\mathbf{x}_{l}$
$\displaystyle\hskip
56.9055pt+\frac{1}{n^{2}}\sum_{i,l\in[n]}p_{i}p_{l}(\mathrm{E}_{\\{i,l\\}}-p_{il}p_{li})\alpha_{il}\alpha_{li}\mathbf{x}_{i}^{\top}\mathbf{x}_{l}$
$\displaystyle\hskip
56.9055pt+\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq
l\end{subarray}}(S_{i}-1)(S_{l}-1)\mathbf{x}_{i}^{\top}\mathbf{x}_{l}.$ (25)

Here, the $i\neq l$ under the fourth summation vanishes because
$\mathrm{E}_{\\{i,i\\}}-p_{ii}p_{ii}=1-1\cdot 1=0$. The above expression can
be simplified as

$\displaystyle\frac{1}{n^{2}}\sum_{i,j\in[n]}p_{j}p_{ij}\left(1-p_{ij}\right)\alpha_{ij}^{2}\lVert\mathbf{x}_{i}\rVert^{2}$
$\displaystyle\hskip
28.45274pt+\frac{1}{n^{2}}\sum_{i,j,l\in[n]}p_{j}(1-p_{j})p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\mathbf{x}_{i}^{\top}\mathbf{x}_{l}$
$\displaystyle\hskip
28.45274pt+\frac{1}{n^{2}}\sum_{i,j\in[n]}p_{i}p_{l}(\mathrm{E}_{\\{i,l\\}}-p_{il}p_{li})\alpha_{il}\alpha_{li}\mathbf{x}_{i}^{\top}\mathbf{x}_{l}$
$\displaystyle\hskip
28.45274pt+\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\end{subarray}}(S_{i}-1)(S_{l}-1)\mathbf{x}_{i}^{\top}\mathbf{x}_{j}.$
(26)

Recalling that ${\left\lVert\mathbf{x}_{i}\right\rVert\leq{\rm R}}$ for all
$i\in[n]$, and using Cauchy-Schwarz inequality, we have
$\lvert\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\rvert\leq\left\lVert\mathbf{x}_{i}\right\rVert\left\lVert\mathbf{x}_{j}\right\rVert\leq{\rm
R}^{2}$. This yields an upper bound to the TIV given by

$\displaystyle\sigma_{\rm
tiv}^{2}(\mathbf{p},\mathbf{P},\mathbf{A})=\frac{{\rm
R}^{2}}{n^{2}}\left[\sum_{i,j\in[n]}p_{j}p_{ij}\left(1-p_{ij}\right)\alpha_{ij}^{2}\right.$
$\displaystyle\hskip
42.67912pt\left.+\sum_{i,j,l\in[n]}p_{j}(1-p_{j})p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\right.$
$\displaystyle\hskip
14.22636pt\left.+\sum_{i,j\in[n]}p_{i}p_{l}(\mathrm{E}_{\\{i,l\\}}-p_{il}p_{li})\alpha_{il}\alpha_{li}+\sum_{\begin{subarray}{c}i,l\in[n]\end{subarray}}(S_{i}-1)(S_{l}-1)\right].$

Note that the last term can be simplified as

$\displaystyle\sum_{i\in[n]}(S_{i}-1)\sum_{l\in[n]}(S_{l}-1)=\left[\sum_{i\in[n]}(S_{i}-1)\right]^{2}.$
(27)

So, we obtain the expression for TIV as in (III.1).

The last term is the bias in the global estimate at the PS. For the unbiased
case, we choose $\\{\alpha_{ij}\\}$ such that $S_{i}=1$ for all $i$.
Consequently, the last term will disappear and we get the same upper bound for
TIV as [23, 1].

The expression for PIV is upper bounded similar to [1] but we present it here
for completeness. To simplify the PIV, which depends on the privacy noise
variance, we push $\tau_{j}$ inside $\sum_{i\in[n]}$ and interchange
$i,j\in[n]$ to get

$\displaystyle\frac{1}{n^{2}}\mathbb{E}\left\lVert\sum_{i,j\in[n]}\tau_{j}\tau_{ij}\mathbf{n}_{ij}\right\rVert_{2}^{2}=\frac{1}{n^{2}}\sum_{i\in[n]}\mathbb{E}\left[\left\lVert\sum_{j\in[n]}\tau_{j}\tau_{ij}\mathbf{n}_{ij}\right\rVert_{2}^{2}\right]$
$\displaystyle\hskip
42.67912pt+\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq
l\end{subarray}}\mathbb{E}\left[\left(\sum_{j\in[n]}\tau_{j}\tau_{ij}\mathbf{n}_{ij}\right)^{\top}\left(\sum_{m\in[n]}\tau_{m}\tau_{lm}\mathbf{n}_{lm}\right)\right].$
(28)

Expanding the first term of (A) yields

$\displaystyle\underbrace{\frac{1}{n^{2}}\sum_{i,j\in[n]}p_{j}p_{ij}\sigma_{ij}^{2}d}_{:=\sigma_{\rm
pr}^{2}(\mathbf{p},\mathbf{P},\boldsymbol{\Sigma})}+\underbrace{\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,j,k\in[n]\\\
j\neq
k\end{subarray}}p_{j}p_{k}p_{ij}p_{ik}\mathbb{E}[\mathbf{n}_{ij}^{\top}\mathbf{n}_{ik}]}_{=0},$
(29)

where the second term is zero due to our assumption of uncorrelated privacy
noise, i.e., $\mathbb{E}[\mathbf{n}_{ij}^{\top}\mathbf{n}_{ik}]=0$. For the
same reason, expanding the second term of (A) yields

$\displaystyle\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq
l\end{subarray}}\mathbb{E}\left[\sum_{j,m\in[n]}\tau_{j}\tau_{ij}\tau_{m}\tau_{lm}\mathbf{n}_{ij}^{\top}\mathbf{n}_{lm}\right]$
$\displaystyle\hskip
28.45274pt=\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq
l\end{subarray}}\sum_{\begin{subarray}{c}j,m\in[n],\\\ j\neq l,m\neq
i\end{subarray}}p_{j}p_{ij}p_{m}p_{lm}\underbrace{\mathbb{E}\left[\mathbf{n}_{ij}^{\top}\mathbf{n}_{lm}\right]}_{=0}$
$\displaystyle\hskip
42.67912pt+\frac{1}{n^{2}}\sum_{\begin{subarray}{c}i,l\in[n]\\\ i\neq
l\end{subarray}}p_{l}p_{i}E_{\\{i,l\\}}\underbrace{\mathbb{E}\left[\mathbf{n}_{ij}^{\top}\mathbf{n}_{ji}\right]}_{=0}=0.$
(30)

This completes the proof.

##  Appendix B Privacy for protecting node identity at relay: Proof of Thm.
IV.2

Note that when $i\notin{\cal R}_{j}$, we have
$\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}=\underline{\widetilde{\mathbf{x}}}_{j}$.
Consequently,

$\displaystyle\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal
S}\right)$
$\displaystyle=p_{ij}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal
S}\mid i\in{\cal R}_{j}\right)$
$\displaystyle\qquad+(1-p_{ij})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid i\notin{\cal R}_{j}\right).$ (31)

Let us denote the aggregated noise at node $j$ by $\mathbf{n}_{j}$, where
${\mathbf{n}_{j}\sim{\cal N}(\mathbf{0},\zeta_{j}^{2}\mathbf{I}_{d})}$. The
effective noise variance ${\zeta_{j}=\sum_{k\in{\cal R}_{j}}\sigma_{kj}^{2}}$
is a random variable, with mean
${\overline{\zeta}_{j}=\sum_{k\in[n]\setminus\\{j\\}}p_{kj}\sigma_{kj}^{2}}$.
Consider ${\cal
E}\triangleq\left\\{\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\leq
r\right\\}$, where $r$ is such that $\Pr({\cal E}^{C})\leq\delta^{\prime}$ for
some $\delta^{\prime}\in(0,1)$. Then,

$\displaystyle\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal
S}\mid i\in{\cal R}_{j}\right)$ $\displaystyle=\Pr({\cal
E}^{C})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\mid
i\in{\cal R}_{j},{\cal E}^{C}\right)$ $\displaystyle\quad\;\;+\Pr({\cal
E})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\mid
i\in{\cal R}_{j},{\cal E}\right)$ $\displaystyle\leq\delta^{\prime}+\Pr({\cal
E})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\mid
i\in{\cal R}_{j},{\cal E}\right).$ (32)

Furthermore, ${\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal
S}\mid i\in{\cal R}_{j},{\cal E}\right)}$ can be written as

$\displaystyle\sum_{\begin{subarray}{c}{\cal A}\subseteq[n]\setminus\\{j\\}\\\
i\in{\cal A},\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\leq
r\end{subarray}}\Pr\left(\widetilde{\mathbf{x}}_{j}^{(-i)}\in{\cal S}\mid{\cal
R}_{j}={\cal A}\right)\Pr\left({\cal R}_{j}={\cal A}\right).$ (33)

This allows us to analyze the privacy guarantee when the set of successfully
transmitting nodes is fixed as ${\cal A}$. For any
$\mathbf{z}\in\mathbb{R}^{d}$, the privacy loss can be upper bounded as
follows:

$\displaystyle\log\left(\frac{\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}=\mathbf{z}\mid{\cal
R}_{j}={\cal
A}\right)}{\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}=\mathbf{z}\mid{\cal
R}_{j}={\cal A}\right)}\right)$
$\displaystyle=\log\left(\frac{\exp\left(-\frac{\left\lVert\mathbf{z}-\sum_{k\in{\cal
A}\setminus\\{i\\}}\alpha_{kj}\mathbf{x}_{k}\right\rVert_{2}^{2}}{2\sum_{k\in{\cal
A}\setminus\\{i\\}}\sigma_{kj}^{2}}\right)}{\exp\left(-\frac{\left\lVert\mathbf{z}-\sum_{k\in{\cal
A}}\alpha_{kj}\mathbf{x}_{k}\right\rVert_{2}^{2}}{2\sum_{k\in{\cal
A}}\sigma_{kj}^{2}}\right)}\right)$
$\displaystyle\leq-\frac{1}{2\zeta_{j}}\left(\left\lVert\mathbf{z}-\sum_{k\in{\cal
A}\setminus\\{i\\}}\alpha_{kj}\mathbf{x}_{k}\right\rVert_{2}^{2}-\left\lVert\mathbf{z}-\sum_{k\in{\cal
A}}\alpha_{kj}\mathbf{x}_{k}\right\rVert_{2}^{2}\right)$ (34)

This upper bound is identical to the privacy loss of a Gaussian mechanism [26]
with variance $\sum_{k\in{\cal A}}\sigma_{kj}^{2}$, with $\ell_{2}$
sensitivity given by

$\displaystyle\sup_{{\cal A}:i\in{\cal A}}\left\lVert\sum_{k\in{\cal
A}}\alpha_{kj}\mathbf{x}_{k}-\sum_{k\in{\cal
A}\setminus\\{i\\}}\alpha_{kj}\mathbf{x}_{k}\right\rVert_{2}=\lVert\alpha_{ij}\mathbf{x}_{i}\rVert_{2}\leq\alpha_{ij}\mathrm{R},$
(35)

where the last inequality follows since $\alpha_{ij}\geq 0$. Consequently,
from the guarantee of a Gaussian mechanism,

$\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\mid{\cal
R}_{j}={\cal A}\right)\leq e^{\epsilon^{(p)}_{j\mid{\cal
A}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal S}\mid{\cal
R}_{j}={\cal A}\right)+\delta_{j}^{(p)},$ (36)

where,

$\epsilon^{(p)}_{j\mid{\cal
A}}\triangleq\left[2\log\left(\frac{1.25}{\delta_{j}^{(p)}}\right)\right]^{\frac{1}{2}}\frac{\alpha_{ij}\mathrm{R}}{\sqrt{\zeta_{j}}}.$
(37)

Let us denote
$c=\left[2\log\left(\frac{1.25}{\delta_{j}^{(p)}}\right)\right]^{\frac{1}{2}}\alpha_{ij}\mathrm{R}$.
From (33), $\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal
S}\mid i\in{\cal R}_{j},{\cal E}\right)$ can be upper bounded by

$\displaystyle\sum_{\begin{subarray}{c}{\cal A}\subseteq[n]\setminus\\{j\\}\\\
i\in{\cal A},\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\leq
r\end{subarray}}\Pr\left({\cal R}_{j}={\cal
A}\right)\left[e^{\frac{c}{\sqrt{\zeta_{j}}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid{\cal R}_{j}={\cal A}\right)+\delta_{j}^{(p)}\right]$ $\displaystyle\leq
e^{c\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\sum_{\begin{subarray}{c}{\cal
A}\subseteq[n]\setminus\\{j\\}\\\ i\in{\cal
A},\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\leq
r\end{subarray}}\Pr\left({\cal R}_{j}={\cal
A}\right)\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal S}\mid{\cal
R}_{j}={\cal A}\right)+\delta_{j}^{(p)}.$ (38)

The second inequality follows because $\zeta_{j}\geq\overline{\zeta}_{j}-r$,
and ${\sum_{{\cal A}\subseteq[n]\setminus\\{j\\}:i\in{\cal
A},\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\leq r}\Pr({\cal
R}_{j}={\cal A})\leq 1}$. Using (B), we can upper bound
$\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\mid
i\in{\cal R}_{j}\right)$ by

$\displaystyle\delta^{\prime}+e^{c\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid i\in{\cal R}_{j}\right)+\delta_{j}^{(p)}.$ (39)

Also, the second term of (B) can be upper bounded by

$\displaystyle\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal S}\mid
i\notin{\cal R}_{j}\right)\leq
e^{c\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid i\notin{\cal R}_{j}\right).$ (40)

From (39) and (40), we upper bound
$\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}^{(-i)}\in{\cal S}\right)$ by

$\displaystyle
e^{c\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\left(p_{ij}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid i\in{\cal R}_{j}\right)\right.$
$\displaystyle\qquad\left.+(1-p_{ij})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid i\notin{\cal
R}_{j}\right)\right)+p_{ij}\left(\delta^{\prime}+\delta_{j}^{(p)}\right)$
$\displaystyle\leq
e^{c\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\right)+p_{ij}\left(\delta^{\prime}+\delta_{j}^{(p)}\right).$ (41)

This completes the proof.

##  Appendix C Privacy for protecting local data at a relay: Proof of Thm.
IV.3

The proof of Thm. IV.3 is quite similar to that of Thm IV.2, and we skip the
details. Similar to (B), since $\underline{\widetilde{\mathbf{x}}}_{j}$
remains unchanged on perturbing $\mathbf{x}_{i}$ if $i\notin{\cal R}_{j}$, for
any $\mathbf{u}\in\mathbb{R}^{d}$,

$\displaystyle\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}\right)=p_{ij}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u},i\in{\cal R}_{j}\right)$
$\displaystyle\qquad\qquad\qquad\;\;+(1-p_{ij})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime},i\notin{\cal R}_{j}\right).$ (42)

Conditioning on ${\cal
E}\triangleq\left\\{\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\leq
r\right\\}$ as in (B),
$\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u},i\in{\cal R}_{j}\right)$ can be upper bounded
by

$\displaystyle\delta^{\prime}+\Pr({\cal
E})\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime},i\in{\cal R}_{j},{\cal E}\right).$
(43)

Moreover, similar to (36), for a fixed set of participating nodes ${\cal A}$,
we also upper bound $\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u},{\cal R}_{j}={\cal A}\right)$ by

$e^{\epsilon_{j\mid{\cal
A}}^{(d)}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime},{\cal R}_{j}={\cal
A}\right)+\delta_{j}^{(d)}.$ (44)

Note that the $\ell_{2}$ sensitivity is now given by

$\left\lVert\sum_{\begin{subarray}{c}k\in{\cal A}\\\ k\neq
i\end{subarray}}\alpha_{kj}\mathbf{x}_{k}+\alpha_{ij}\mathbf{u}-\sum_{\begin{subarray}{c}k\in{\cal
A}\\\ k\neq
i\end{subarray}}\alpha_{kj}\mathbf{x}_{k}-\alpha_{ij}\mathbf{u}_{i}^{\prime}\right\rVert_{2}\leq
2\alpha_{ij}{\rm R}.$

Here, we use
$\lVert\mathbf{u}-\mathbf{u}^{\prime}\rVert_{2}\leq\lVert\mathbf{u}\rVert+\lVert\mathbf{u}^{\prime}\rVert_{2}\leq
2\mathrm{R}$. A tighter inequality can be used if we know an upper bound on
the perturbation magnitude, i.e.,
$\lVert\mathbf{u}-\mathbf{u}^{\prime}\rVert_{2}$. As in (37), we get,

$\displaystyle\epsilon^{(d)}_{j\mid{\cal
A}}\triangleq\left[2\log\left(\frac{1.25}{\delta_{j}^{(d)}}\right)\right]^{\frac{1}{2}}\frac{2\alpha_{ij}\mathrm{R}}{\sqrt{\zeta_{j}}}.$
(45)

Similar to (39), denoting
$c=\left[2\log\left(\frac{1.25}{\delta_{j}^{(d)}}\right)\right]^{\frac{1}{2}}2\alpha_{ij}\mathrm{R}$,
we upper bound $\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u},i\in{\cal R}_{j}\right)$ by

$\delta^{\prime}+e^{\widetilde{c}\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime},i\in{\cal
R}_{j}\right)+\delta_{j}^{(d)}.$ (46)

Finally, similar to (B), we complete the proof by upper bounding
$\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}\right)$ by

$e^{\widetilde{c}\left(\overline{\zeta}_{j}-r\right)^{-\frac{1}{2}}}\Pr\left(\underline{\widetilde{\mathbf{x}}}_{j}\in{\cal
S}\mid\mathbf{x}_{i}=\mathbf{u}^{\prime}\right)+p_{ij}\left(\delta^{\prime}+\delta_{j}^{(d)}\right).$
(47)

##  Appendix D Privacy when the PS can observe outputs of multiple relays:
Proof of Thm. IV.5

In Thm. IV.2, let us denote $\delta^{\prime}$ by $\delta_{j}^{\prime}$ such
that $\Pr\left(\left\lvert\zeta_{j}-\overline{\zeta}_{j}\right\rvert\geq
r_{j}\right)\leq\delta_{j}^{\prime}$. When $p_{ij}>0$, for any
$\delta\in(0,p_{ij}]$, let us set
$\delta_{j}^{(p)}=\frac{\delta}{p_{ij}}-\delta_{j}^{\prime}$. Then, for
$\delta\in(0,p_{ij}]$, (10) is

$\displaystyle\Pr\left(\widetilde{\mathbf{x}}_{j}^{(-i)}\in{\cal
S}\right)\leq\widetilde{\epsilon}_{ij}^{(p)}\Pr\left(\widetilde{\mathbf{x}}_{j}\in{\cal
S}\right)+\delta,\quad\text{where}$
$\displaystyle\widetilde{\epsilon}_{ij}^{(p)}=\exp{\left(\left[2\log\left(\frac{1.25\;p_{ij}}{\delta-
p_{ij}\delta_{j}^{\prime}}\right)\right]^{\frac{1}{2}}\frac{\alpha_{ij}\mathrm{R}}{\sqrt{\overline{\zeta}_{j}+\sigma_{jj}^{2}-r_{j}}}\right)}.$
(48)

Here, $\sigma_{jj}^{2}$ appears in the denominator of
$\widetilde{\epsilon}_{ij}^{(p)}$ because we consider the signal transmitted
by node $j$ to the PS, i.e., $\widetilde{\mathbf{x}}_{j}$, instead of the
signal aggregated at node $j$, i.e., $\underline{\widetilde{\mathbf{x}}}_{j}$.
Since node $j$ adds $\mathbf{n}_{jj}\sim{\cal
N}(\mathbf{0},\sigma_{jj}\mathbf{I}_{d})$ to privatize its own data before
sending to the PS, this contributes to the effective privacy noise variance in
$\widetilde{\mathbf{x}}_{j}$.

Let us consider the privacy guarantee when the eavesdropper (possibly PS) can
observe $\mathbf{y}_{j}=\tau_{j}\widetilde{\mathbf{x}}_{j}$. Denote
$\mathbf{y}_{j}^{(-i)}=\tau_{j}\widetilde{\mathbf{x}}_{j}^{(-i)}$. Then, for
any measurable set ${\cal S}$, $\Pr(\mathbf{y}_{j}^{(-i)}\in{\cal S})$ is
given by

$\displaystyle p_{j}\Pr\left(\mathbf{y}_{j}^{(-i)}\in{\cal
S}\mid\tau_{j}=1\right)+(1-p_{j})\Pr\left(\mathbf{y}_{j}^{(-i)}\in{\cal
S}\mid\tau_{j}=0\right)$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}p_{j}\left(\widetilde{\epsilon}_{ij}^{(p)}\Pr\left(\mathbf{y}_{j}\in{\cal
S}\mid\tau_{j}=1\right)+\delta\right)$
$\displaystyle\qquad\qquad\qquad\qquad+(1-p_{j})\widetilde{\epsilon}_{ij}^{(p)}\Pr\left(\mathbf{y}_{j}\in{\cal
S}\mid\tau_{j}=0\right)$
$\displaystyle=\widetilde{\epsilon}_{ij}^{(p)}\Pr\left(\mathbf{y}_{j}\in{\cal
S}\right)+p_{j}\delta,$ (49)

where $\delta\in(0,p_{ij}]$, and $\rm(i)$ follows from (D).

Note that when the PS observes the outputs of two relays, namely nodes $j$ and
$\ell$, both $\mathbf{y}_{j}$ and $\mathbf{y}_{\ell}$ contain some component
of $\mathbf{x}_{i}$ due to the redundancy introduced as a consequence of
collaboration. The accumulated noise in $\mathbf{y}_{j}$ comes from the
following sources of stochasticity: $\rm(i)$ the local privacy noise added by
node $i$ for transmission to node $j$, i.e., $\mathbf{n}_{ij}$, $\rm(ii)$ the
intermittent nature of the link $i\to j$, i.e., $\tau_{ij}$, and $\rm(iii)$
the intermittent nature of the link from node $j$ to the PS, i.e., $\tau_{j}$.
To consider the privacy leakage about the participation of node $i$, note that
the corresponding quantities for node $\ell$, i.e., $\mathbf{n}_{i\ell}$,
$\tau_{i\ell}$, and $\tau_{\ell}$ are independent of those for node $j$. An
application of the standard composition theorem G.3 tells us that if the PS
observes the tuple $(\mathbf{y}_{j},\mathbf{y}_{\ell})$, the resulting
mechanism is
$(\widetilde{\epsilon}_{ij}^{(p)}+\widetilde{\epsilon}_{i\ell}^{(p)},\delta(p_{j}+p_{\ell}))$
differentially private, where $\delta\in(0,{\rm min}\\{p_{ij},p_{i\ell}\\}]$.

With a similar argument, we can conclude that if the PS observes the outputs
of multiple relays, i.e., $\\{\mathbf{y}_{j}\\}_{j\in[n]}$, the resulting
mechanism is $\left(\sum_{\begin{subarray}{c}j\in[n]\\\
p_{ij}>0\end{subarray}}\widetilde{\epsilon}_{ij}^{(p)},\delta\left(\sum_{j\in[n]}p_{j}\right)\right)$
differentially private with respect to protecting the identity of node $i$,
where $\delta\in(0,{\rm min}_{\begin{subarray}{c}j\in[n]\\\
p_{ij}>0\end{subarray}}\\{p_{ij}\\}]$. Here, we consider only the nodes $j$
such that $p_{ij}>0$, because when $p_{ij}=0$, the corresponding mechanism are
$(0,0)$-differentially private, since there is no transmission. This gives us
(13).

Proceeding in a similar fashion, we can obtain the privacy leakage for
protecting the local data of a node, i.e., (IV.5).

##  Appendix E Weight and noise variance optimization using projected gradient
descent

Recall our notation
$\rho_{ij}=\frac{2\mathrm{R}}{\underline{\epsilon}_{ij}}\left[2\log\left(\frac{1.25}{\underline{\delta}_{ij}}\right)\right]^{\frac{1}{2}}$.
Referring to Fig. 6, let us consider a point ${\rm P}\equiv(\alpha,\sigma)$
and suppose its projection onto the cone ${\cal K}$ is denoted by
${\rm\widehat{P}}\equiv(\alpha_{{\cal K}},\sigma_{{\cal K}})$. Any point ${\rm
P}$ can lie in one of the following three regions:

Figure 6: Projecting onto cone ${\cal K}$ for finding $\alpha_{ij}$ and
$\sigma_{ij}$.

Case $\mathbf{1}$: $\alpha\geq 0$ and $\sigma\geq\rho_{ij}\alpha$. In this
case, $(\alpha,\sigma)\in{\cal K}$, and so, $(\alpha_{{\cal K}},\sigma_{{\cal
K}})=(\alpha,\sigma)$.

Case $\mathbf{2}$: $\sigma\geq 0$ and $\alpha<0$. The projection
${\rm\widehat{P}}\equiv(\alpha_{\cal K},\sigma_{\cal K})$ is

$\alpha_{{\cal K}}=0\;\text{ and }\;\sigma_{{\cal K}}=\sigma.$ (50)

Case $\mathbf{3}$:  $\sigma<0$ or $\\{\sigma\geq 0\;\text{ and
}\;\sigma\leq\rho_{ij}\alpha\\}$. Let $(x,y)$ be the projection of the point
on the line $\sigma=\rho_{ij}\alpha$. Then, $(x,y)$ must satisfy
$y=\rho_{ij}x$ and $(\alpha-x)+\rho_{ij}(\sigma-y)=0$, i.e.,

$x=\frac{\alpha+\rho_{ij}\sigma}{1+\rho_{ij}^{2}},\text{ and
}\;y=\frac{\rho_{ij}(\alpha+\rho_{ij}\sigma)}{1+\rho_{ij}^{2}}.$ (51)

Now, if $x<0$, then the projection onto ${\cal K}$ will be $(\alpha_{{\cal
K}},\sigma_{{\cal K}})=(0,0)$; otherwise leave them as it is. This can be
concisely expressed as

$\alpha_{\cal
K}=\left(\frac{\alpha+\rho_{ij}\sigma}{1+\rho_{ij}^{2}}\right)_{+}\;\text{ and
}\;\sigma_{\cal
K}=\left(\frac{\rho_{ij}(\alpha+\rho_{ij}\sigma)}{1+\rho_{ij}^{2}}\right)_{+}.$
(52)

Here, $\left(\cdot\right)_{+}={\rm max}\\{\cdot,0\\}$ . For each
${i,j\in[n]}$, we start with a feasible iterate
$\left(\alpha_{ij}^{(0)},\sigma_{ij}^{(0)}\right)$ that satisfies
${\alpha_{ij}^{(0)}\geq 0}$,
${\sigma_{ij}^{(0)}\geq\rho_{ij}\alpha_{ij}^{(0)}}$, and take projected
gradient descent steps.

##  Appendix F Collaboration over Erdös-Rényi network topologies

Optimal collaboration weights: For the setup described in §V-B, the first term
of the TIV (III.1) is

$\displaystyle\frac{\mathrm{R}^{2}}{n^{2}}\sum_{i,j}p_{j}p_{ij}(1-p_{ij})\alpha_{ij}^{2}=\frac{\mathrm{R}^{2}}{n^{2}}\sum_{j\in{\cal
M}}q\sum_{i}p_{ij}(1-p_{ij})\alpha_{ij}^{2}$ $\displaystyle=$
$\displaystyle\frac{\mathrm{R}^{2}q}{n^{2}}\sum_{j\in{\cal
M}}\left[p_{jj}(1-p_{jj})\alpha_{jj}^{2}+\sum_{i\in{\cal
M}\setminus\\{j\\}}p_{ij}(1-p_{ij})\alpha_{ij}^{2}\right.$
$\displaystyle\quad\left.+\sum_{i\in\overline{{\cal
M}}}p_{ij}(1-p_{ij})\alpha_{ij}^{2}\right]=\frac{\mathrm{R}^{2}}{n^{2}}m(n-m)qp(1-p)\alpha^{2}.$
(53)

The second term of (III.1),
${\frac{\mathrm{R}^{2}}{n^{2}}\sum_{i,j,l}p_{j}(1-p_{j})p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}}$,
is

$\displaystyle\frac{\mathrm{R}^{2}}{n^{2}}q(1-q)\sum_{j\in{\cal
M}}\sum_{i,l}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}$
$\displaystyle=\frac{\mathrm{R}^{2}}{n^{2}}q(1-q)\sum_{j\in{\cal
M}}\left[\sum_{i}p_{ij}^{2}\alpha_{ij}^{2}+\sum_{i,l:i\neq
l}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\right]$
$\displaystyle=\frac{\mathrm{R}^{2}}{n^{2}}q(1-q)\sum_{j\in{\cal
M}}\left[\sum_{j\in{\cal
M}\setminus\\{i\\}}p_{ij}^{2}\alpha_{ij}^{2}+p_{ii}^{2}\alpha_{ii}^{2}+\sum_{j\in\overline{{\cal
M}}}p_{ij}^{2}\alpha_{ij}^{2}\right.$
$\displaystyle+\left.\sum_{l\in\overline{{\cal
M}}}p_{jj}p_{lj}\alpha_{jj}\alpha_{lj}+\sum_{i\in\overline{{\cal
M}}}p_{ij}p_{jj}\alpha_{ij}\alpha_{jj}+\sum_{i,l\in\overline{{\cal M}}:i\neq
l}p_{ij}p_{lj}\alpha_{ij}\alpha_{lj}\right]$
$\displaystyle=\frac{\mathrm{R}^{2}}{n^{2}}q(1-q)\sum_{j\in{\cal
M}}\left[\gamma^{2}+(n-m)p^{2}\alpha^{2}+2(n-m)p\gamma\alpha\right.$
$\displaystyle\left.\qquad\qquad\qquad\qquad+(n-m)(n-m-1)p^{2}\alpha^{2}\right]$
$\displaystyle=\frac{\mathrm{R}^{2}}{n^{2}}mq(1-q)\left(\gamma+(n-m)p\alpha\right)^{2}.$
(54)

The third term of (III.1),
${\frac{\mathrm{R}^{2}}{n^{2}}\sum_{i,j}p_{i}p_{j}(\mathrm{E}_{ij}-p_{ij}p_{ji})\alpha_{ij}\alpha_{ji}}$,
is

$\displaystyle\frac{\mathrm{R}^{2}}{n^{2}}\sum_{i\in{\cal
M}}p_{i}^{2}(\mathrm{E}_{ii}-p_{ii}^{2})\alpha_{ii}^{2}=0.$ (55)

This follows as $\alpha_{ij}=0$ whenever $i,j\in{\cal M}$, $i\neq j$, and
because $\mathrm{E}_{ii}=p_{ii}=1$.

The fourth term of (III.1),
${\frac{\mathrm{R}^{2}}{n^{2}}\left(\sum_{i,j}p_{j}p_{ij}\alpha_{ij}-n\right)^{2}}$,
is

$\displaystyle\frac{\mathrm{R}^{2}}{n^{2}}\left(\sum_{j\in{\cal
M}}p_{j}\left(p_{jj}\alpha_{jj}+\sum_{i\in\overline{{\cal
M}}}p_{ij}\alpha_{ij}\right)\right)^{2}$
$\displaystyle\qquad\qquad=\frac{\mathrm{R}^{2}}{n^{2}}\left[mq\left(\gamma+(n-m)p\alpha\right)-n\right]^{2}.$
(56)

The PIV given by (5) simplifies to

$\displaystyle\frac{d}{n^{2}}\sum_{j\in{\cal M}}p_{j}\sum_{i\in\overline{{\cal
M}}}p_{ij}\sigma_{ij}^{2}=\frac{d}{n^{2}}qpm(n-m)\sigma^{2}.$ (57)

With $\ell_{2}$ regularization for bias, we have

$\displaystyle\beta(\alpha,\gamma)$
$\displaystyle=\sum_{i\in[n]}\left(\sum_{j\in[n]}p_{j}p_{ij}\alpha_{ij}-1\right)^{2}$
$\displaystyle=m\left(q\gamma-1\right)^{2}+(n-m)\left(mqp\alpha-1\right)^{2}.$
(58)

So, the optimization problem (V) is given by

$\displaystyle\mathop{\rm arg\hskip
2.84526ptmin}_{\alpha,\gamma,\sigma}\sigma_{\rm
tiv}^{2}(\alpha,\gamma)+\sigma_{\rm
piv}^{2}(\sigma)+\lambda\beta(\alpha,\gamma)$ $\displaystyle\quad\text{subject
to}\quad\xi\mathrm{R}\frac{\alpha}{\sigma}\leq\epsilon,\alpha\geq 0,\sigma\geq
0.$ (59)

Here,

$\displaystyle\sigma_{\rm
tiv}^{2}(\alpha,\gamma)=\frac{\mathrm{R}^{2}}{n^{2}}m(n-m)qp(1-p)\alpha^{2}$
$\displaystyle\qquad\qquad\qquad+\frac{\mathrm{R}^{2}}{n^{2}}mq(1-q)\left(\gamma+(n-m)p\alpha\right)^{2}$
$\displaystyle\qquad\qquad\qquad+\frac{\mathrm{R}^{2}}{n^{2}}\left[mq\left(\gamma+(n-m)p\alpha\right)-n\right]^{2},$
$\displaystyle\sigma_{\rm pr}^{2}(\sigma)=\frac{d}{n^{2}}qpm(n-m)\sigma^{2},$
$\displaystyle\beta(\alpha,\gamma)=m\left(q\gamma-1\right)^{2}+(n-m)\left(mqp\alpha-1\right)^{2},$
and
$\displaystyle\xi=2\left[2\log\left(\frac{1.25}{\delta}\right)\right]^{\frac{1}{2}}.$
(60)

For $(\alpha,\gamma,\sigma)$ that satisfy
$\sigma\geq\xi\mathrm{R}\frac{\alpha}{\epsilon}$, $\alpha\geq 0$, $\sigma\geq
0$, we have

$\displaystyle{\rm min}_{\alpha,\gamma,\sigma}\;\sigma_{\rm
tiv}^{2}(\alpha,\gamma)+\sigma_{\rm
pr}^{2}(\sigma)+\lambda\beta(\alpha,\gamma)$ $\displaystyle\geq\;\;$
$\displaystyle{\rm min}_{\alpha,\gamma}\;\sigma_{\rm
tiv}^{2}(\alpha,\gamma)+\frac{d}{n^{2}}qpm(n-m)\left(\xi\mathrm{R}\frac{\alpha}{\epsilon}\right)^{2}+\lambda\beta(\alpha,\gamma),$

and the inequality is tight for $\sigma=\xi\mathrm{R}\frac{\alpha}{\epsilon}$.
Since the RHS is a smooth and convex function of $\alpha$ and $\gamma$, we can
find the optimal values by finding the stationary points. Differentiating with
respect to $\alpha$ and $\gamma$, and some algebra yields the optimal
collaboration weights given in (V-B).

Central privacy guarantee: From Thm. IV.2, ${p_{ij}=p>0}$,
${\epsilon_{ij}^{(p)}=\left[2\log\left(\frac{1.25}{\delta_{j}^{(p)}}\right)\right]^{\frac{1}{2}}\frac{\alpha_{ij}{\rm
R}}{\sqrt{\overline{\zeta}_{j}-r}}}$, where ${j\in{\cal M}}$ acts as a relay,
and ${i\in\overline{{\cal M}}}$ is a node with no direct connectivity to the
PS. Fix ${\delta_{ij}^{(p)}=\delta}$ to be the same $\delta$ as the peer-to-
peer privacy constraint. Then,
${\epsilon_{ij}^{(p)}=\frac{\xi\mathrm{R}}{2mpq}\frac{1}{\sqrt{\overline{\zeta}_{j}-r}}}$,
where

${\overline{\zeta}_{j}=\sum_{k\in\overline{{\cal
M}}}p_{kj}\sigma_{kj}^{2}=(n-m)p\sigma_{*}^{2}},$

and,

$r=\left(\frac{\sigma_{*}^{2}}{6}+\frac{1}{2}\left(\frac{\sigma_{*}^{2}}{9}+\frac{4(n-m)p(1-p)\sigma_{*}^{4}}{\log(2/\delta^{\prime})}\right)^{\frac{1}{2}}\right)\log\left(\frac{2}{\delta^{\prime}}\right).$

Choose $\delta^{\prime}$ such that
$12(n-m)p(1-p)\sigma_{*}^{2}=\log\left(2/\delta^{\prime}\right)$. Since
$\delta^{\prime}\in(0,1)$, and $\sigma_{*}=\frac{\xi\mathrm{R}}{mpq\epsilon}$,
when $n>m$, the above choice is valid if

$\displaystyle\sigma_{*}\geq\left(\frac{\log
2}{12(n-m)p(1-p)}\right)^{\frac{1}{2}}$
$\displaystyle\qquad\qquad\qquad\quad\text{or,
}\quad\epsilon\leq\frac{\xi\mathrm{R}}{mq}\left(\left(\frac{1-p}{p}\right)\frac{12(n-m)}{\log
2}\right)^{\frac{1}{2}}.$ (61)

With the above constraint on $\epsilon$ and this choice of $\delta^{\prime}$,
we get

$\overline{\zeta}_{j}-r=(n-m)p\sigma_{*}^{2}\left(1-2\sigma_{*}(\sigma_{*}+2)(1-p)\right).$
(62)

Since $(\overline{\zeta}_{j}-r)>0$, when $p>\frac{7}{8}$, it suffices to
ensure

$\displaystyle\sigma_{*}(\sigma_{*}+2)\leq(\sigma_{*}+2)^{2}\leq\frac{1}{2(1-p)}\quad\text{or,
}\quad\sigma_{*}\leq\frac{1}{\sqrt{2(1-p)}}-2$
$\displaystyle\qquad\qquad\qquad\qquad\quad\text{or,
}\quad\epsilon\geq\frac{\xi\mathrm{R}}{mpq}\left(\sqrt{\frac{1}{2(1-p)}}-2\right).$
(63)

So, the privacy leakage is

$\displaystyle\epsilon_{ij}^{(p)}$
$\displaystyle=\frac{\xi\mathrm{R}}{2mpq}\left((n-m)p\sigma_{*}^{2}\left(1-2\sigma_{*}(\sigma_{*}+2)(1-p)\right)\right)^{-\frac{1}{2}}$
$\displaystyle\sim{\cal O}\left(\frac{1}{m\sqrt{n-m}}\right).$ (64)

##  Appendix G Preliminaries

######  Definition G.1.

($(\epsilon_{i},\delta_{i})$-Local Differential Privacy (LDP)) Let
$\mathcal{D}_{i}$ be a set of all possible data points at node $i$. For node
$i$, a randomized mechanism
$\mathcal{M}_{i}:\mathcal{D}_{i}\rightarrow\mathbb{R}^{d}$ is
$(\epsilon_{i},\delta_{i})$ locally differentially private (LDP) if for any
$x,x^{\prime}\in\mathcal{D}_{i}$, and any measurable subset
$\mathcal{S}\subseteq\text{Range}(\mathcal{M}_{i})$, we have

$\displaystyle\operatorname{Pr}(\mathcal{M}_{i}(x)\in\mathcal{S})\leq
e^{\epsilon_{i}}\operatorname{Pr}(\mathcal{M}_{i}(x^{\prime})\in\mathcal{S})+\delta_{i}.$
(65)

The setting when $\delta_{i}=0$ is referred as pure $\epsilon_{i}$-LDP. In
this work, we analyze the privacy level achieved by the PriCER algorithm,
which exploits the intermittent connectivity and adds synthetic noise
perturbations to privatize its local data. We focus on analyzing the privacy
leakage under an additive noise mechanism that is drawn from the Gaussian
distribution. This well-known perturbation technique is known as the Gaussian
mechanism, and it provides rigorous privacy guarantees, defined next.

######  Definition G.2.

(Gaussian Mechanism [26]) Suppose a node wants to release a function $f(X)$ of
an input $X$ subject to $(\epsilon,\delta)$-LDP. The Gaussian release
mechanism is defined as

$\displaystyle\mathcal{M}(X)\triangleq
f(X)+\mathcal{N}(0,\sigma^{2}\mathbf{I}).$ (66)

If the $\ell_{2}$-sensitivity of the function is bounded by $\Delta_{f}$,
i.e., $\|f(x)-f(x^{\prime})\|_{2}\leq\Delta_{f}$, $\forall x,x^{\prime}$, then
for any $\delta\in(0,1]$, the Gaussian mechanism satisfies
$(\epsilon,\delta)$-LDP, where

$\displaystyle\epsilon=\frac{\Delta_{f}}{\sigma}\sqrt{2\log\frac{1.25}{\delta}}.$
(67)

######  Definition G.3.

(Basic Composition Thm. of DP [26]) If a randomized mechanism
$\mathcal{M}_{i}$ satisfies $(\epsilon_{i},\delta_{i})$-LDP for
$i=1,2,\cdots,n$, then for any $\delta_{i}\in(0,1]$, their composition
$\mathcal{M}$ defined by
$\mathcal{M}\triangleq(\mathcal{M}_{1},\mathcal{M}_{2},\cdots,\mathcal{M}_{K})$
satisfies $(\sum_{i=1}^{n}\epsilon_{i},\sum_{i=1}^{n}\delta_{i})$-LDP.

###  G-A Bernstein’s inequality

######  Lemma G.4.

(Bernstein’s Inequality [50]) Let $\\{X_{k}\\}_{k=1}^{n}$ be a collection of
zero-mean independent random variables, where each $X_{k}$ is bounded by $M$,
almost surely. Then, for any $r\geq 0$, we have

$\displaystyle\operatorname{Pr}\bigg{(}\sum_{i=1}^{n}X_{k}>r\bigg{)}\leq\exp\left[-\frac{r^{2}}{\sum_{k=1}^{n}E(X_{k}^{2})+\frac{Mr}{3}}\right].$
(68)

Choice of the parameter $r$ for the result in Cor. IV.4: Consider the random
variables to be ${X_{k}=\left(\tau_{kj}-p_{kj}\right)\sigma_{kj}^{2}}$. Then,
$\mathbb{E}[X_{k}]=0$, $M=\max_{k\in[n]}\sigma_{kj}^{2}$, and
${\mathbb{E}[X_{k}^{2}]=p_{kj}(1-p_{kj})\sigma_{kj}^{4}}$. An application of
Bernstein inequality gives

$\displaystyle\Pr(\lvert\zeta_{j}-\overline{\zeta}_{j}\rvert\geq
r)=\Pr\left(\left\lvert\sum_{k\in[n]\setminus\\{j\\}}(\tau_{kj}-p_{kj})\sigma_{kj}^{2}\right\rvert\geq
r\right)$ $\displaystyle\leq
2\exp\left[-\frac{r^{2}}{\sum_{k\in[n]\setminus\\{j\\}}p_{kj}(1-p_{kj})\sigma_{kj}^{4}+\frac{r\max_{k\in[n]\setminus\\{j\\}}\sigma_{kj}^{2}}{3}}\right].$

For any $\delta^{\prime}\in(0,1]$, this is a quadratic in $r$ and the right
hand side expression can be tightened by choosing $r$ to be

$\displaystyle r$
$\displaystyle=\frac{\log(2/\delta^{\prime})}{2}\left({\max_{k\in[n]\setminus\\{j\\}}\sigma_{kj}^{2}}/{3}\right.$
$\displaystyle\left.+\sqrt{{\max_{k\in[n]\setminus\\{j\\}}\sigma_{kj}^{2}}/{9}+\frac{4}{\log(2/\delta^{\prime})}\left(\sum_{k\in[n]\setminus\\{j\\}}p_{kj}(1-p_{kj})\sigma_{kj}^{4}\right)}\right).$
(69)

##  Appendix H Local privacy guarantee for node-node communications: Proof of
Thm. IV.1

We begin by considering the cases of successful transmission, i.e.,
$\tau_{ij}=1$ and unsuccessful transmission, i.e., $\tau_{ij}=0$ separately.
When $\tau_{ij}=0$, we have perfect privacy, i.e.,

$\displaystyle\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}\in{\cal D}_{i},\tau_{ij}=0\right)$
$\displaystyle=\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i},\tau_{ij}=0\right),$ (70)

since there is no transmission from node $i$, i.e.,
$\widetilde{\mathbf{x}}_{ij}=\mathbf{0}$ irrespective of whether
$\mathbf{x}_{i}\in{\cal D}_{i}$ or $\mathbf{x}_{i}^{\prime}\in{\cal D}_{i}$.
When ${\tau_{ij}=1}$, node $j$ receives
${\widetilde{\mathbf{x}}_{ij}=\alpha_{ij}\mathbf{x}_{i}+\mathbf{n}_{ij}}$. In
this case, the $\ell_{2}$-sensitivity is

$\sup_{\begin{subarray}{c}\mathbf{x}_{i},\mathbf{x}_{i}^{\prime}\text{ s.t.
}\\\ \lVert\mathbf{x}_{i}\rVert\leq{\rm
R},\lVert\mathbf{x}_{i}^{\prime}\rVert\leq{\rm
R}\end{subarray}}\lVert\alpha_{ij}\mathbf{x}_{i}-\alpha_{ij}\mathbf{x}_{i}^{\prime}\rVert\leq
2\alpha_{ij}{\rm R}.$ (71)

Using (71) above, and from the guarantees of the Gaussian mechanism [26], when
$\tau_{ij}=1$, we have for any $\delta_{ij}\in(0,1)$, the transmission from
node $i$ to node $j$ is $(\epsilon_{ij},\delta_{ij})$ \- differentially
private, i.e.,

$\displaystyle\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}\in{\cal D}_{i},\tau_{ij}=1\right)$
$\displaystyle\qquad\qquad\qquad\leq
e^{\epsilon_{ij}}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i},\tau_{ij}=1\right)+\delta_{ij},$
(72)

where

$\epsilon_{ij}=\left[2\log\left(\frac{1.25}{\delta_{ij}}\right)\right]^{\frac{1}{2}}\frac{2\alpha_{ij}{\rm
R}}{\sigma_{ij}}.$

Combining (70) and (H), we have

$\displaystyle\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}\in{\cal D}_{i}\right)$
$\displaystyle=p_{ij}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}\in{\cal D}_{i},\tau_{ij}=1\right)$
$\displaystyle\qquad\qquad+(1-p_{ij})\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}\in{\cal D}_{i},\tau_{ij}=0\right)$ $\displaystyle\leq
p_{ij}\left(e^{\epsilon_{ij}}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i},\tau_{ij}=1\right)+\delta\right)$
$\displaystyle\qquad\qquad+(1-p_{ij})\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i},\tau_{ij}=0\right)$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}p_{ij}e^{\epsilon_{ij}}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i},\tau_{ij}=1\right)$
$\displaystyle\qquad+(1-p_{ij})e^{\epsilon_{ij}}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal
D}_{i},\tau_{ij}=0\right)+p_{ij}\delta_{ij}$
$\displaystyle=e^{\epsilon_{ij}}\Pr\left(\widetilde{\mathbf{x}}_{ij}\in{\cal
S}\mid\mathbf{x}_{i}^{\prime}\in{\cal D}_{i}\right)+p_{ij}\delta_{ij}.$ (73)

Here, $\rm(i)$ holds true since ${e^{\epsilon_{ij}}\geq 1}$. Furthermore, note
that when ${p_{ij}=0}$, node $i$ can never transmit to node $j$ and as a
consequence, we can choose ${\alpha_{ij}=0}$. This completes the proof.