# Secure Aggregation Meets Sparsification in Decentralized Learning

Sayan Biswas
EPFL  Anne-Marie Kermarrec
EPFL  Rafael Pires
EPFL  Rishi Sharma
EPFL  Milos Vujasinovic
EPFL

###### Abstract

DL faces increased vulnerability to privacy breaches due to sophisticated
attacks on machine learning (ML) models. Secure aggregation is a
computationally efficient cryptographic technique that enables multiple
parties to compute an aggregate of their private data while keeping their
individual inputs concealed from each other and from any central aggregator.
To enhance communication efficiency in DL, sparsification techniques are used,
selectively sharing only the most crucial parameters or gradients in a model,
thereby maintaining efficiency without notably compromising accuracy. However,
applying secure aggregation to sparsified models in decentralized learning
(DL) is challenging due to the transmission of disjoint parameter sets by
distinct nodes, which can prevent masks from canceling out effectively. This
paper introduces Communication-efficient secure aggregation (CESAR), a novel
secure aggregation protocol for DL designed to be compatible with existing
sparsification mechanisms. CESAR provably defends against honest-but-curious
adversaries and can be formally adapted to counteract collusion between them.
We provide a foundational understanding of the interaction between the
sparsification carried out by the nodes and the proportion of the parameters
shared under CESAR in both colluding and non-colluding environments, offering
analytical insight into the working and applicability of the protocol.
Experiments on a network with 48 nodes in a 3-regular topology show that with
random subsampling, CESAR is always within 0.5% accuracy of decentralized
parallel stochastic gradient descent (D-PSGD), while adding only 11% of data
overhead. Moreover, it surpasses the accuracy on TopK by up to 0.3% on
independent and identically distributed (IID) data.

##  1 Introduction

Large and high-quality datasets play a major role in unlocking the full
potential of ML models [35, 20, 52]. Collaborative learning, by pooling
datasets from multiple sources, enables the creation of more robust and
diverse ML models. However, the direct sharing of data for ML training poses
significant privacy and security challenges, especially in domains where data
is sensitive or regulated, such as under the general data protection
regulation (GDPR) [13] and the health insurance portability and accountability
act (HIPAA) [43].

To address these challenges, FL [30] and DL [25] have been developed to enable
the training of ML models without direct data sharing. In these paradigms,
data remains distributed across nodes (user devices or servers), and learning
is achieved through the exchange of model parameters or updates, rather than
raw data. This approach enhances privacy, as data does not leave its original
location, and scales efficiently to large numbers of participants.

While federated learning (FL) has been utilized in various domains including
text prediction [47, 34, 6] and healthcare [21, 19, 28], DL offers a distinct
advantage in scenarios where a centralized coordinating server is infeasible
or undesirable. DL, by decentralizing the learning process, further empowers
data privacy and local control, making it particularly attractive for
applications that require distributed decision-making and autonomy over data.

Despite these advantages, DL faces its own set of significant challenges,
particularly in terms of communication efficiency and privacy preservation.
The transmission of model parameters, especially in deep learning networks,
can lead to substantial communication overhead. To mitigate this,
sparsification techniques are employed. The TopK [3] method, for instance,
focuses on transmitting only the top $k$ parameters with the highest
gradients, while random subsampling [22, 42] involves randomly selecting a
subset of parameters for transmission. Additionally, techniques like Jwins
[10] use wavelet transforms to rank the parameters without significant loss of
information. These approaches aim to reduce the volume of data transmitted,
concentrating on the most impactful parameters or gradients to preserve the
model’s accuracy.

However, the application of secure aggregation protocols to sparsified models
in DL introduces unique challenges. These protocols employ coordinated random
masks added to the parameters by each participant. When aggregated, these
masks are designed to cancel out, thereby revealing only the aggregate result
and not the individual data contributions, effectively preserving the privacy
of each participant. Nevertheless, when sparsification is employed, the
transmission of disjoint sets of parameters by different nodes can disrupt the
effective cancellation of these cryptographic masks in secure aggregation.
This disruption leads to inaccurate results due to residual noise not being
fully negated.

Moreover, another critical aspect in the interplay of sparsification and
secure aggregation in DL is the alignment of parameter indices. Sparsification
techniques such as TopK and random subsampling, by their nature, select
different sets of parameters across nodes. When these nodes engage in secure
aggregation, a crucial requirement is the matching of indices to ensure that
masks cancel out properly. However, this necessity often leads to a further
reduction in the number of parameters being aggregated, as any non-matching
indices must be discarded to avoid non-canceled noise. This additional layer
of parameter reduction can potentially impact the convergence of the model, as
important parameters might be excluded from the aggregation process.
Understanding and addressing this intersection challenge is key to optimizing
the balance between privacy preservation, efficient communication and model
accuracy in DL.

To address these challenges, this paper introduces CESAR, a novel protocol
designed for decentralized learning. CESAR is uniquely engineered to be
compatible with various forms of sparsification. The protocol is robust
against honest-but-curious adversaries and can be adapted to resist collusion
attacks by introducing a trade-off in communication efficiency. Our
comprehensive experiments conducted on several $k$-regular graph topologies
demonstrate that CESAR, when employed with random subsampling, matches the
performance of D-PSGD with only a modest increase in data overhead. Moreover,
CESAR shows superior accuracy compared to TopK sparsification methods,
affirming its effectiveness in striking a balance between communication
efficiency, privacy preservation, and model accuracy in decentralized learning
environments.

In this paper, we make the following contributions:

  * •

We introduce CESAR, the first protocol for secure aggregation in decentralized
learning using sparsification techniques.

  * •

We formally show that our protocol is secure against honest-but-curious users
and provide a theoretical analysis that enables CESAR to be provably resilient
against colluding nodes.

  * •

We theoretically derive the anticipated quantity of shared parameters between
nodes within CESAR in the presence of colluding adversaries in the network.
This allows us to parameterize the utility of CESAR and offers analytical
insights into the workings and applicability of the protocol.

  * •

We evaluated the performance and communication costs of our protocol across
three distinct datasets within two different application domains. Our results
demonstrate that CESAR can replace D-PSGD without the need for altering
hyperparameters, while still preserving comparable levels of performance.
Furthermore, an extensive analysis on CIFAR-10 showed CESAR can surpass the
accuracy of D-PSGD, while sharing as little as 7% additional data using random
subsampling, and 12% using TopK sparsification.

The remaining of this paper is organized as follows. Section 2 briefly
introduces the concept of DL, Sparsification and Secure Aggregation. CESAR is
described in Section 3, along with the corresponding analysis. We empirically
evaluate CESAR in Section 4 under several aspects. Related work is surveyed in
Section 5 before a brief discussion (Section 6) and the conclusion in Section
7.

##  2 Preliminaries

###  2.1 Decentralized Learning

Decentralized learning is a form of machine learning involving a set of nodes
$\mathcal{N}$ organized in a network topology $G$. Each node, labeled as
$N_{i}\in\mathcal{N}$, has its local dataset $D_{i}$ characterized by its
distribution $\varphi_{i}$. During training, these local datasets remain
private and are not shared among nodes. If local label distributions are
homogeneous across nodes, we call these datasets IID, and non-IID otherwise.

The collective objective of the training is to find a set of optimal
parameters $\theta^{*}$ that minimizes a loss function $\mathcal{L}$ across
the aggregated dataset of all nodes, represented as
$D=\bigcup_{N_{j}\in\mathcal{N}}D_{j}$:

$\theta^{*}=\operatorname*{arg\,min}_{\theta}\mathcal{L}(D;\theta)$

The training happens over multiple rounds, each comprised of three steps:
training, sharing, and aggregation. Initially, each node performs one or
several iterations of an optimization algorithm, typically stochastic gradient
descent (SGD), on mini-batches of their local dataset. After this, they share
their updated parameters either to all neighbors in the network topology, as
in D-PSGD [26], or to a selected subset of neighbors, as in random model walk
(RMW) [31]. Finally, upon receiving parameters from their neighbors, each node
computes an average of these parameters together with its own model. This
newly computed averaged parameter set then becomes the starting point for the
next round of training. The process is iterated until convergence.

###  2.2 Sparsification

Machine learning models are often large and become even more so, which incurs
significant costs when transferring them over a network. Sparsification is a
technique for lossy model compression. This technique assumes that even a
subset of the parameters of a model carries important information about the
model. Therefore, it involves transmitting a selected subset of indices,
rather than the entire model.

Two popular sparsification approaches are random subsampling [22, 42] and TopK
[3]. Both take as input the percentage of indices to be selected, denoted as
$\alpha$, and a model of size $k$. Random subsampling samples each index with
a probability of $\alpha$, ultimately expecting to select $\alpha k$ indices.
The indices selected in TopK, on the other hand, depend on their magnitude:
they are first sorted by weight and the top $\alpha k$ with highest values are
chosen. While TopK preserves crucial features by prioritizing significant
parameters, it risks overfitting as some parameters are never shared. Random
subsampling, in turn, does not induce overfitting but may lead to loss of
important information and hence lead to lower accuracy.

###  2.3 Secure Aggregation

Secure aggregation [4] is a form of multiparty computation, , a technique
allowing multiple parties to jointly compute a function over their inputs
while keeping those inputs private. It is performed by a set of $p\geq 3$
nodes $\mathcal{N}=\\{N_{1},N_{2},\ldots,N_{p}\\}$. Every node $N_{i}$ has a
private value $x_{i}$ that it wants to keep private and yet use it to
calculate the value of a function
$f(x_{1},x_{2},\dots,x_{p})=\sum_{i=1}^{p}x_{i}=:\hat{x}$ together with other
nodes from $\mathcal{N}$. At the end of the protocol, every value $x_{i}$ must
remain private, while the aggregated value $\hat{x}$ is public.

Pairwise masking [1, 4] is a prominent way of performing secure aggregation.
This approach assumes an imposed ordering of nodes:
$N_{1}<N_{2}<\ldots<N_{p}$. Under this assumption every pair of nodes $N_{i}$,
$N_{j}$ (where $N_{i}<N_{j}$) collaboratively generates a private random mask
$M_{i,j}$. The masking process involves $N_{i}$ adding $M_{i,j}$ to its value,
and $N_{j}$ subtracting the same mask from its value. The masks applied in
this fashion sum up to 0, guaranteeing that the sum of masked values is equal
to the sum of original values. Applying this technique across all node pairs,
each node $N_{i}$ computes a masked value
$x^{{}^{\prime}}_{i}=x_{i}-\sum_{j=1}^{i-1}M_{j,i}+\sum_{j=i+1}^{p}M_{i,j}$.
The resulting masked value, $x^{{}^{\prime}}_{i}$, can be safely shared
publicly, as it reveals no information about the original value $x_{i}$.

##  3 CESAR: Secure aggregation for sparsified decentralized learning

###  3.1 System model

We consider a set of $n$ nodes, denoted as
$\mathcal{N}=\\{N_{1},\dots,N_{n}\\}$, interconnected in a communication graph
$G(\mathcal{N},E)$. We consider all communication channels to be bidirectional
(, TCP connections over the Internet) and assume there exists an underlying
mechanism used for generating another graph called _aggregation graph_. This
aggregation graph is a spanning subgraph of the original communication graph
(, an overlay network). For clarity, all subsequent mentions of a graph in
this paper will specifically refer to the aggregation graph.

The protocol requires each node to communicate not only with its immediate
neighbors but also with the neighbors of these neighbors. Consequently, we
assume that each node must possess knowledge of both these types of nodes
within the graph. We denote immediate neighbors of $N\in\mathcal{N}$ as
$\operatorname{View}(N)=\\{M:M\in\mathcal{N}\wedge\\{N,M\\}\in E\\}$ and
second degree neighbors as
$\text{View}_{2}(N)=(\cup_{M\in\text{View}(N)}\text{View}(M))\setminus\\{N\\}$.
For $N_{\ell},N_{i}\in\mathcal{N}$, if $\\{N_{\ell},N_{i}\\}\in E$, let
$\operatorname{Comm}(N_{\ell},N_{i})=\operatorname{View}(N_{\ell})\setminus\\{N_{i}\\}$
denote the set of all nodes in the network that $N_{i}$ communicates with to
find out the intersection of the sampled parameters, agree upon the mask to be
applied to them, and, in turn, share these masked parameters to $N_{\ell}$. In
this context, we refer to $N_{\ell}$ as the _receiving node_ of $N_{i}$’s
masked model parameters. We assume that each communication channel is secure
and encrypted, and subsequently that it cannot be eavesdropped. However, there
are no definitive guarantees of direct communication channels for nodes that
are two hops away (distance 2) in the aggregation graph. Therefore, when
second degree neighbors attempt to communicate and lack a direct channel in
the communication graph, the common neighbor must relay their messages. This
process effectively doubles the total number of messages sent in such
scenarios. Nevertheless, in real-life systems, the communication graph is
almost always near-fully connected, which typically circumvents this issue.
For simplicity, the rest of this paper assumes that the communication graph is
fully connected.

All nodes train models with a shared architecture, each having $d$ parameters
and being characterized by identical numbers of layers and corresponding
layers of same shape. Parameters are enumerated using indices, or parameter
position used interchangeably, $\mathcal{I}=\\{1,\ldots,d\\}$. Parameters held
by $N_{i}$ are denoted as $v_{i}\in\mathbb{R}^{d}$ where $v_{i}^{(p)}$ denotes
the value of the parameter at index $p$ and node $N_{i}$. The set of indices
selected for sharing by $N_{i}$ in DL is denoted as
$I_{i}\subseteq\mathcal{I}$

###  3.2 Threat model

In the scope of this work, we primarily focus on the threat posed by honest-
but-curious adversaries. Accordingly, all nodes in our threat model adhere to
the protocol and do not collude with each other. However, they attempt to
infer as much information as possible from the data accessible to them through
the protocol.

Section 3.4.2 steps out of this threat model looking into possible presence of
colluding adversaries in the system and proposes ways to adjust the protocol
in order to combat them.

###  3.3 Algorithm

In this subsection we introduce the protocol, CESAR. The pseudo-code of the
protocol is shown in Algorithm 1 and the overview of execution in Figure 1.
The algorithm is broken into subcomponents for readability and ease of
understanding.

Input: Accepts list of indices selected in sparsification
$I_{i}\subseteq\mathcal{I}=\\{1,2,3,\ldots,d\\}$, all current local parameters
of $v_{i}\in\mathbb{R}^{d}$, and aggregation graph $G(\mathcal{N},E)$ in which
aggregation takes place

Output: The aggregated model $v_{i}^{\prime}\in\mathbb{R}^{d}$ of the
neighborhood of the node

1

2

3$M^{\prime}_{i},I_{i\cap}\leftarrow$ prestep(_$N_{i}$ , $I_{i}$_)

4 send_masked_models(_$N_{i}$ , $v_{i}$, $M^{\prime}_{i}$, $I_{i\cap}$_)

5 return aggregate_received_models(_$N_{i}$ , $v_{i}$_)

Algorithm 1 CESAR running in parallel on every Node $N_{i}$

1

2

3Function  _prestep(_$N_{i}$ , $I_{i}$_)_

4 for  _$N_{j}\in\operatorname{View}_{2}(N_{i})$_ do

5 Generate pseudo-random number $seed_{ij}$

6 Send $(I_{i},seed_{ij})$ to node $N_{j}$

7

8 for  _$N_{j}\in\operatorname{View}_{2}(N_{i})$_ do

9 $(I_{j},seed_{ji})\leftarrow$ Receive from node $N_{j}$

10 $I_{i\cap j}\leftarrow I_{i}\cap I_{j}$

11 $M_{ij}\leftarrow$ Random mask over $I_{i\cap j}$ with seed $seed_{ij}$

12 $M_{ji}\leftarrow$ Random mask over $I_{i\cap j}$ with seed $seed_{ji}$

13 $M^{\prime}_{ij}\leftarrow M_{ij}-M_{ji}$

14 $M^{\prime}_{i}\leftarrow\cup_{N_{j}\in\mathcal{N}}M^{\prime}_{ij}$

15 $I_{i\cap}\leftarrow\cup_{N_{j}\in\mathcal{N}}I_{i\cap j}$

16 return $M^{\prime}_{i},I_{i\cap}$

17

Algorithm 2 CESAR-prestep

1

2

3Function  _send_masked_models(_$N_{i}$ , $v_{i}$, $M^{\prime}_{i}$,
$I_{i\cap}$_)_

4 for  _$N_{k}\in\operatorname{View}(N_{i})$_ do

5 $v_{k\mathrel{\leftarrow\\!\\!|}i}\leftarrow v_{i}$

6 $C\leftarrow$ Zero vector of size $d$

7 for  _$N_{j}\in\operatorname{View}(N_{k})\setminus\\{N_{i}\\}$_ do

8 $v_{k\mathrel{\leftarrow\\!\\!|}i}[I_{i\cap j}]\leftarrow
v_{k\mathrel{\leftarrow\\!\\!|}i}[I_{i\cap j}]+M^{\prime}_{ij}$

9 $C[I_{i\cap j}]\leftarrow C[I_{i\cap j}]+1$

10

11 $I^{\prime}_{ik}\leftarrow p\in\mathcal{I}:C[p]\geq 1$

12 $w_{k\mathrel{\leftarrow\\!\\!|}i}\leftarrow
v_{k\mathrel{\leftarrow\\!\\!|}i}[I^{\prime}_{ik}]$

13 Send $(I^{\prime}_{ik},w_{k\mathrel{\leftarrow\\!\\!|}i})$ to node $N_{k}$

14

Algorithm 3 CESAR-masking the model and sending it to the neighbors

1

2

3Function  _aggregate_received_models(_$N_{i}$ , $v_{i}$_)_

4 $v_{i}^{\prime}\leftarrow v_{i}$

5 $c\leftarrow 1$

6 for  _$N_{k}\in\operatorname{View}(N_{i})$_ do

7 $(I^{\prime}_{ki},w_{k\mathrel{\leftarrow\\!\\!|}i})\leftarrow$ Receive from
node $N_{k}$

8 $v_{k}^{\prime}\leftarrow v_{i}$

9 $v_{k}^{\prime}[I^{\prime}_{ki}]\leftarrow
w_{k\mathrel{\leftarrow\\!\\!|}i}$

10 $v_{i}^{\prime}\leftarrow v_{i}^{\prime}+v_{k}^{\prime}$

11 $c\leftarrow c+1$

12

13 $v_{i}^{\prime}\leftarrow\frac{v_{i}^{\prime}}{c}$

14 return $v_{i}^{\prime}$

15

Algorithm 4 CESAR-Aggregating received models Figure 1: Overview of CESAR
model masking on $N_{1}$. (1) Nodes $N_{1}$, $N_{2}$ and $N_{3}$ independently
sparsify their local models; (2) $N_{1}$ masks the common indices of its model
with those of neighbors that are 2 hops away (, $N_{2}$ and $N_{3}$) and that
share a common neighbor ($N_{r}$); (3) Indices that were kept unmasked are
discarded; (4) $N_{1}$ sends the resulting masked model to $N_{r}$.

The inputs of the protocol are current model parameters, the set of indices
selected by the sparsification algorithm and the network graph. This protocol
builds upon D-PSGD using pairwise additive masking to implement secure
aggregation. Pairwise masking is the standard way of doing secure aggregation
within FL [4].

In D-PSGD, models are broadcast to all adjacent nodes. A notable challenge
emerges when considering a node, let us call it $N_{1}$, transmitting its
model to neighboring nodes $N_{n_{1}},N_{n_{2}},\dots,N_{n_{k}}$. Each of
these neighbors, $N_{n_{i}}$, also receives models from their respective
neighbors. In an arbitrary network graph, it is not guaranteed that the nodes
$N_{n_{1}},N_{n_{2}},\dots,N_{n_{k}}$ share any common neighbors besides
$N_{1}$. Consequently, if $N_{1}$ wishes to send the same masked model to all
its neighbors, it would require at least one unique counterpart node with
exactly the same set of neighbors with whom it could agree on a pairwise mask.
This condition is rarely met in most arbitrary graphs, leading us to adopt an
alternative method.

In our protocol rather than sending a model masked with the same mask to all
neighbors, a node transmits the same model, each time masked differently, to
each neighbor. Specifically, a node coordinates with every neighbor of the
intended recipient to establish a unique pairwise mask. When broadcasting a
model, the node applies all the masks it has agreed upon with the neighbors of
the recipient.

This approach is effective as long as the recipient has at least two neighbors
and receives all the masked models from them. It ensures that every parameter
received is masked at least once and that for each mask used to obfuscate a
parameter, its counterpart (the opposite mask) is present among the other
received masked models. Otherwise, if there is a node $N_{\text{single}}$ with
only a single neighbor, the given neighbor won’t have another node to mask
their parameters with and hence, following Algorithm 1, won’t send any
parameters to $N_{\text{single}}$ making the given edge redundant.

Upon receiving all the masked models, the recipient aggregates them with their
own model and computes the average. This process results in a new model that
aligns with the result that would be achieved in D-PSGD on the same graph.

The protocol contributes further by integrating sparsification. Sparsification
occurs independently among nodes, and there are no mechanisms to ensure that
two nodes creating a mask will choose the same set of indices. Consequently,
any indices that lie in the symmetric difference of the two nodes’ selected
indices will lack their corresponding mask, preventing the mask from being
canceled out. To address this, the protocol applies a pairwise mask solely to
the subset of indices that both parties have selected during sparsification,
namely, the intersection of their selected indices. It is important to note
that, unlike previously, the number of masks applied to each index of the same
node may vary. Additionally, some indices might be selected only by one node
and remain unmasked, as they do not form part of any intersection. The
protocol therefore counts the number of masks applied to each index,
discarding any indices that have no masks applied before sending the masked
model. As a result, every transmitted index is masked, and its corresponding
opposite mask is included among the other masked models received by the
neighboring node. The act of dropping some extra parameters may impact
convergence, which we analyse/evaluate in Section 4.6.2.

The protocol is performed in two distinct communication steps. In the first
step, denoted as _prestep_ , each node coordinates with the neighbors of its
neighbors. During this coordination, nodes exchange partial seeds for the
pairwise masks and share the set of indices selected in their sparsification
process. A node then computes the intersection of its own indices with those
received and applies a pairwise mask to this intersection. This pairwise mask
is derived by subtracting the sender’s generated mask (from their partial
seed) from the mask generated by the recipient’s own partial seed. Notably,
each node produces a distinct partial seed for every other node it interacts
with during this phase in each round. In the subsequent step, for each
neighbor, a node starts with the unmasked model and applies all pairwise masks
agreed upon with the neighbor’s neighbors. It then removes any unmasked
indices before transmitting the masked sparse model. Finally, upon receiving
these masked models, the recipient node averages them with its model,
resulting in a new model ready for training in the next round.

###  3.4 Theoretical analysis

####  3.4.1 Privacy guarantees

A parameter is considered private if its exact value cannot be inferred by any
other node in the network. A node is considered private if all its parameters
are private.

######  Theorem 1.

CESAR ensures that no honest-but-curious adversary can infer the exact value
of any parameter received by its neighbors.

###### Proof.

Without the loss of generality, let us fix a node $N\in\mathcal{N}$ and
consider an arbitrary parameter $p\in I$. During the protocol, node $N$ only
receives masked models from its neighbors. If $N$ did not receive the
parameter $p$ from any neighbor, it trivially does not learn anything about
$p$.

If $N$ received the parameter $p$ from the neighbor $N_{a_{0}}$, it means that
$N_{a_{0}}$ must have applied at least one mask to parameter $p$. Under CESAR,
if $N_{a_{0}}$ has applied at least one mask, there must be a non-empty
exhaustive set of the neighbors $\\{N_{a_{1}},\dots,N_{a_{l}}\\}$ that share
pairwise masks with $N_{a_{0}}$ for $p$. Hence, each node of the set
$\mathcal{A}=\\{N_{a_{0}},N_{a_{1}},\dots,N_{a_{l}}\\}~{}(|\mathcal{A}|\geq
2)$ must have intended to share $p$. Furthermore, by the algorithm, every pair
$\\{i,j\\}$ of nodes in $\mathcal{A}$ must have agreed on a random pairwise
mask $M^{{}^{\prime}(p)}_{ij}=-M^{{}^{\prime}(p)}_{ji}$ for $p$. For example,
if $v_{N_{\ell}}^{(p)}$ is a parameter value $p$ at $N_{\ell}$ before the
protocol and $w_{N_{\ell}}^{(p)}$ is the value received by $N$ from
$N_{\ell}\in\mathcal{A}$ for parameter $p$, we know that

$w_{N_{\ell}}^{(p)}=v_{N_{\ell}}^{(p)}+\sum_{N_{o}\in\mathcal{A}\setminus\\{N_{\ell}\\}}M^{{}^{\prime}(p)}_{N_{\ell}N_{o}}.$

Because masks are chosen independently from each other, and their values are
private to the pair that generated them, the only way for node $N$ to infer
$v_{N_{\ell}}^{(p)}$ from $w_{N_{\ell}}^{(p)}$ is to cancel all masks in
$w_{N_{\ell}}^{(p)}$. In order to do this $N$ must add to $w_{N_{\ell}}^{(p)}$
all values for $p$ received from other nodes that share a pairwise mask with
$N_{\ell}$ in equal proportion. Therefore, the most node $N$ can infer from
the information available to it is the sum of values

$\sum_{N_{\ell}\in\mathcal{A}}w_{N_{\ell}}^{(p)}=\sum_{N_{\ell}\in\mathcal{A}}v_{N_{\ell}}^{(p)}.$

From just the sum no specific contributions can be inferred. ∎

####  3.4.2 Collusion

Environments that involve colluding nodes pose significant challenges.
Nevertheless, CESAR can be made resilient against such collusion through
simple modifications to Algorithm 1. We suggest that an effective method to
counter collusion is to adjust the minimum number of masks applied to an index
before its transmission. This change involves implementing a configurable
parameter specified by the user of the system, denoted as $s$, at Algorithm 3
in the algorithm. The modification is represented as
$I^{\prime}_{ik}\leftarrow p\in\mathcal{I}:C[p]\geq s$ (i.e. the parameter at
position $p$ has to have at least $s$ masks applied in order to be sent,
otherwise it is discarded). We call this parameter $s$ as the _masking
requirement_. This modification, however, raises concerns about the potential
for some masks to be discarded while their corresponding opposite masks are
not. Lemma 3 demonstrates that all neighbors of a node, which have selected
the parameter at a predetermined position for transmission to the given node,
have an identical number of masks applied to the parameter. Moreover,
according to the algorithm, every pair of these neighbors agreed on a pairwise
mask. Consequently, provided that 2 is satisfied, it is guaranteed that all
such neighbors will either transmit the parameter, thereby cancelling out the
masks through aggregation, or conversely, all will discard the parameter and
none will transmit it. In other words, we can ensure that all masks cancel
out, provided the masking requirement is uniformly applied across the network.
In the subsequent analysis, we adhere to the following assumption.

######  Assumption 2.

All non-colluding nodes must have the same masking requirement when sending
their masked models to a fixed neighbor in CESAR.

Let us consider an environment where the graph has $n_{t}$ trusted nodes who
honestly comply with the protocol and $k$ colluding adversarial nodes who
share all the information they have with each other and aim to violate the
privacy of the trusted nodes. Let $\mathcal{N}_{T}$ and $\mathcal{N}_{A}$,
respectively, denote the sets of the trusted and the colluding adversarial
nodes in the graph such that $\mathcal{N}=\mathcal{N}_{T}\cup\mathcal{N}_{A}$
and $\mathcal{N}_{T}\cap\mathcal{N}_{A}=\phi$. In this setting, investigation
of the privacy guarantees stays relevant only for the trusted nodes.

######  Lemma 3.

For a fixed index $p$ the number of masks every node sending their masked
models to the same neighbor $N_{j}$ is either $0$ or if not zero the exact
same value among all such nodes.

###### Proof.

The set of indices selected by node $N\in\mathcal{N}$ in sparsification is
denoted as $I_{N}\subseteq\mathcal{I}$. We look at the index $p$ and node
$N_{j}$ that receives the masked models. Furthermore we define a set of
neighbors of $N_{j}$ who have selected $p$ in sparsification as
$Sel(N_{j},p)=\\{N\in\text{View}(N_{j}):p\in I_{N}\\}$.

For every neighbor $N_{i}\in\text{View}(N_{j})$ there are two cases to
consider for index $p$:

Case 1. $p\notin I_{N_{i}}$: If $N_{i}$ does not select $p$ for sharing, by
the algorithm there trivially will not be any masks agreed between $N_{i}$ and
another neighbor of $N_{j}$, making the number of mask in this case $0$.

Case 2. $p\in I_{N_{i}}$: If $N_{i}$ selects $p$ for sharing the total number
of masks $N_{i}$ will agree upon with other neighbors of $N_{j}$ on $p$ is
$\text{MaskCount}(N_{i},N_{j},p)=|\\{N\in\text{View}(N_{j})\setminus\\{N_{i}\\}:p\in
I_{N_{i}\cap N}\\}|$. Considering the precondition of the case, expression
$p\in I_{N_{i}\cap N}$ can be transformed into $p\in I_{N}$ making
$\text{MaskCount}(N_{i},N_{j},p)=|\\{N\in\text{View}(N_{j})\setminus\\{N_{i}\\}:p\in
I_{N}\\}|$. Because $p\in I_{N_{i}}$ then $N_{i}\in Sel(N_{j},p)$, so the
previous expression can also be written as
$\text{MaskCount}(N_{i},N_{j},p)=|Sel(N_{j},p)\setminus\\{N_{i}\\}|=|Sel(N_{j},p)|-1$.
Repeating the same for all neighbors of $N_{j}$ we obtain the exact same
value, hence proving the statement of the lemma. ∎

######  Lemma 4.

If the masking requirement of the nodes is $k$, without worsening the privacy
of the trusted nodes, any graph under CESAR, where $|\mathcal{N}_{A}|\leq k$,
can be transformed into a graph where:

  1. i.

$|\mathcal{N}_{A}|=k$

  2. ii.

All trusted nodes have a degree of at least 1

  3. iii.

the nodes in $\mathcal{N}_{A}$ form a clique

  4. iv.

$\\{N_{i},N_{j}\\}\notin E$ for any $N_{i},N_{j}\in\mathcal{N}_{T}$

###### Proof.

$i.$ If there are $s<k$ adversarial nodes in the graph, adding an adversarial
node with degree $0$ will not change the number of masks that the trusted
nodes applied to their model parameters.

$ii.$ If there is a trusted node with degree $0$, it does not contribute to
the working of the protocol or the number of masks that the other trusted
nodes decide to apply. Therefore, we may remove them from the graph without
compromising the privacy of any of the nodes.

$iii.$ If there is any $N_{0}\in\mathcal{N}_{A}$ without having an adversary
as its neighbor, for every $N\in\mathcal{N}_{A}$, adding $\\{N_{0},N\\}$ to
$E$ increments the number of masks added to the parameters of any trusted node
connected to $N_{0}$ or $N$ by on (which will possibly be shared between $N$
and $N^{\prime}$). However, more importantly, this does not reduce any masks
already applied to the parameters of the trusted nodes, implying their privacy
remains at least as it was when $\\{N_{0},N\\}$ was not in $E$.

$iv.$ Let $\\{N_{i},N_{j}\\}\in E$ for some $N_{i},N_{j}\in\mathcal{N}_{T}$.
Deleting this edge between $N_{i}$ and $N_{j}$ will not affect the masks that
any trusted node applies to the parameters that they share with the
adversarial nodes. We note, however, that deleting the edge between $N_{i}$
and $N_{j}$ will reduce the number of masks applied to the parameters that any
other trusted node $N_{\ell}$ shares with $N_{i}$ or $N_{j}$. But, as $N_{i}$
or $N_{j}$ are not involved in any collusion (, have no information about the
masks used by any other node), as long as the parameters they receive from
$N_{\ell}$ have at least one mask applied to them, the privacy of $N_{\ell}$
will be upheld.

∎

######  Theorem 5.

If $k$ is the masking requirement of every trusted node in the network, the
true values of their model parameters will remain obfuscated from every node
in the network when there are $k$ colluding adversarial nodes.

###### Proof.

By Lemma Lemma 4, it is sufficient to consider the case where we the trusted
nodes have edges only with the adversarial nodes. Setting the number of
adversarial nodes as $k$, as they collude in nature, we assume that they form
a $k$ clique in the network. Letting $n_{t}$ be the number of trusted nodes
present in the network, we proceed to show the result by inducting over
$n_{t}$.

When $n_{t}=1$, denoting $N$ to be the only trusted node, as it is connected
to an adversarial node $A$, $|\operatorname{Comm}(A,N)|=k-1$. Therefore, $N$
can have at most $k-1$ masks applied to any of its parameters (which are
decided by the protocol communicating with the members of
$\operatorname{Comm}(A,N)$). As the masking requirement is set to $k$, $N$
will never end up sharing updates from any of its parameters with $A$,
implying that its true value will never be revealed.

Let the result hold for some $n_{t}=\lambda-1\geq 2$ and a new trusted node in
the network. Let the trusted nodes be $N_{1},\ldots N_{\lambda}$. Due to Lemma
4, we may ignore any edge between the trusted nodes and only consider the case
where they have adversarial neighbors. Let $N_{i}$ have an edge with
adversarial node $A_{i}$ for every $i\in\\{1,\ldots,\lambda\\}$.

Case 1. $A_{\lambda}\neq A_{i}$ for every $i\in\\{1,\ldots,\lambda-1\\}$: This
essentially implies that $N_{\lambda}$ can have at most $k-1$ masks applied
its values at any index and, therefore, will not share its model updates with
the adversarial nodes and it will remain private.

Case 2. $A_{\lambda}=A_{i}$ for some $i\in\\{1,\ldots,\lambda-1\\}$: If
$|\operatorname{Comm}(A_{\lambda},N_{\lambda})|<k-1$, the maximum number of
masks that $N_{\lambda}$ can apply to the value of its model update at any
parameter will be less than its masking requirement of $k$ and, hence, will
not share its model updates with the adversarial nodes and it will remain
private. Otherwise, $N_{\lambda}$ and $N_{i}$ communicate and privately agree
to mask their corresponding model updates at the indices in $I_{\lambda\cap
i}$ with $M_{\lambda j}$ and $M_{j\lambda}(=-M_{\lambda j})$, respectively.
Thus, $\left\\{v^{(p)}_{\lambda}\colon p\in I_{\lambda\cap i}\right\\}$ will
have at least one secure mask $M_{\lambda}$ applied to it for every $p\in
I_{\lambda\cap i}$ which will not be available to the colluding adversarial
nodes. Thus, the true values $\\{v^{(p)}_{\lambda}\\}$ will remain hidden from
$A_{\lambda}$ (and, correspondingly, from every other adversarial node) due to
the privately chosen mask between $N_{\lambda}$ and $N_{i}$. ∎

Recalling that CESAR discards unmasked indices therefore reducing the
percentage of model parameters intended for sharing in sparsification,
understanding how this percentage varies based on system parameters, masking
requirements, and training configuration is vital to evaluate the practical
application of CESAR.

Given the difficulty of exhaustively modeling every sparsification approach,
our focus is on a simplified yet realistic scenario. Here, each index is
equally likely to be selected for sparsification, and the selection is
mutually independent between nodes. While this assumption does not hold for
many sparsification methods, it perfectly characterizes random subsampling. We
assume that every node chooses $\alpha$ fraction of their indices for
sparsification. Since all nodes select the same proportion of parameters and
the overall model sizes are identical, the probability $\pi_{i}^{(p)}$ for any
node $i$ to select a given index $p$ is $\alpha$. Hence, we enable ourselves
to derive the expected number of model parameters shared by each node in the
network under CESAR capturing an environment when we have $k$ colluding nodes.

######  Theorem 6.

Under CESAR with random subsampling, if the nodes have a masking requirement
of $s$, setting $\beta(\alpha,\delta,s)$ to be the expected proportion of
parameters shared by one node (sender) to another (receiver) in one round, we
have:

$\displaystyle\beta\left(\alpha,\delta,s\right)=\sum_{i=s}^{\delta-1}\binom{\delta-1}{i}\alpha^{i+1}(1-\alpha)^{\delta-1-i}$

where $\alpha$ is the probability of independently sampling any parameter by
any node and
$\delta=\left\lvert\operatorname{View}(\text{Receiver})\right\rvert$.

###### Proof.

Postponed to Section B.1. ∎

######  Corollary 7.

In the absence of any colluding nodes, CESAR with random subsampling ensures
that the expected proportion of parameters shared by any node (sender) to
another (receiver) in one round is given by:

$\displaystyle\beta\left(\alpha,,\delta,1\right)=\alpha\left(1-(1-\alpha)^{\delta-1}\right)$
(1)

where $\alpha$ is the probability of (independently) sampling any parameter by
any node and $\delta=\left\lvert\operatorname{View}(\text{Receiver
Node})\right\rvert$.

###### Proof.

In the absence of collusion, the masking requirement of all the nodes is $1$.
Thus, putting $s=1$ in Theorem 6, we obtain:

$\displaystyle\beta\left(\alpha,\delta,1\right)$
$\displaystyle=\alpha\sum_{i=1}^{\delta-1}\binom{\delta-1}{i}\alpha^{i}(1-\alpha)^{\delta-1-i}$
$\displaystyle=\alpha\left(1-(1-\alpha)^{\delta-1}\right)$

∎

Figure 2: Variation of the fraction of parameters shared in CESAR with the
$\operatorname{deg}$ denoting the degree of the receiving node and $\alpha$
being the fraction of model parameters selected in sparsification by each node
for masking requirement $s=1$ (, in the absence of any colluding adversarial
nodes). Vertical lines and solid curves correspond to scenarios assessed in
our empirical evaluation in Section 4.

Figure 2 illustrates how $\beta$ varies with different values of $\alpha$ and
degree, based on Equation 1. It is observed that for a sufficiently high
degree, the percentage of shared parameters $(\beta)$ converges towards the
percentage of parameters selected in sparsification $(\alpha)$. This
convergence occurs more rapidly for higher values of $\alpha$. Additionally,
the relative percentage of discarded parameters appears to be larger for
smaller values of $\alpha$ at for the same degree.

####  3.4.3 Communication overhead

In this analysis, the model size is denoted by $d$, the fraction of indices
selected in sparsification by $\alpha$, and the maximum degree of any node in
the graph by $\delta_{\text{max}}$.

The communication overhead incurred by CESAR occurs primarily in the prestep
stage. During this phase, each node dispatches a single message to the
neighbors of its neighbors. The number of these message transmissions is
bounded by $O(\delta_{\text{max}}^{2})$.

Each of these messages comprises a partial seed, which has a size of $O(1)$,
and a set of indices selected during sparsification, the size of which is
$O(\alpha d)$.

Consequently, the total communication overhead for the prestep in CESAR
amounts to $O(\alpha d\delta_{\text{max}}^{2})$.

##  4 Evaluation

In this section, we evaluate the performance of CESAR against a well-regarded
baseline, for a variety of graph topologies and different fractions of the
model selected in sparsification over three datasets.

###  4.1 Implementation

The code is implemented in Python 3.6, using _decentralizepy_ library [9],
which is built on top of PyTorch for machine learning.

###  4.2 Setup

We conducted our experiments on three machines. Each machine is equipped with
32-core Intel(R) Xeon(R) CPU E5-2630 v3 CPU clocked at 2.40GHz and runs Ubuntu
20.04.4 LTS with the 5.4.0-122-generic kernel. Unless otherwise specified all
experiments are carried out on a 48-node network, with each machine simulating
16 nodes. The nodes are organized in a randomly generated $k$-regular graph in
all experiments, every node has $k$ neighbors where the value of $k$ is
specified for each experiment. The size of the network in the experiments
stays fixed. We show in Section 3.4.3 that the overhead of the protocol
depends only on the degree of nodes rather than the total number of nodes in
the network.

Every experiment is run 5 times for different seeds and the results are
averaged over them. Masking requirement of CESAR in all experiments is $s=1$.

###  4.3 Dataset and hyperparameters

The experiments are conducted on CIFAR-10 [24], CelebA [5] and MovieLens [16].
CIFAR-10 and CelebA are image classification tasks, while MovieLens is a
recommendation task.

We partition training dataset among nodes such that no two nodes get the same
sample. The whole test set is utilized for performance evaluation at every
test step.

Training data is partitioned in one of two ways: IID and non-IID. IID
distribution is applied only on CIFAR-10 and CelebA by shuffling the datasets
and splitting them into chunks of equal size that are given to each node. The
same approach is applied to MovieLens, however it is non-IID by the nature of
data. In the case of non-IID, we perform it only on CIFAR-10: the dataset is
sorted by the label and split into $2n$ equally sized chunks, where $n$ is the
total number of nodes, and each node is given $2$ chunks. This limits the
total number of classes a node can receive in non-IID partitioning to 4.

The training is performed using SGD optimizer without momentum. The values of
hyperparameters are tuned by running a grid search on D-PSGD with full-
sharing. Every communication round marks one full execution of CESAR. Test
metrics are evaluated at the end of each epoch. The values of hyperparameters
together with the size of data and models used for training are shown in Table
1. They stay the same for all experiments performed on a given dataset.

Table 1: Training hyperparameters, dataset properties and models trained on them | Dataset
---|---
Hyperparameter | CIFAR-10 | CelebA | MovieLens
Learning rate | 0.01 | 0.001 | 0.05
Batch size | $\mathrm{8}$ | $\mathrm{8}$ | $\mathrm{6}\mathrm{4}$
Communication rounds per epoch | $\mathrm{2}\mathrm{1}$ | $\mathrm{1}\mathrm{0}$ | $\mathrm{2}\mathrm{2}$
SGD steps per communication rounds | $\mathrm{6}$ | $\mathrm{1}\mathrm{0}$ | $\mathrm{1}$
Dataset property |  |  |
Number of training samples | $\mathrm{5}\mathrm{0}\mathrm{0}\mathrm{0}\mathrm{0}$ | $\mathrm{6}\mathrm{3}\mathrm{7}\mathrm{4}\mathrm{1}$ | $\mathrm{7}\mathrm{0}\mathrm{0}\mathrm{0}\mathrm{0}$
Dataset type | Image classification | Image classification | Recommendation
Model | 4 Conv2D Layers | GN-LeNet [18] | Matrix Factorization [23]
Number of model parameters | $\mathrm{8}\mathrm{9}\mathrm{8}\mathrm{3}\mathrm{4}$ | $\mathrm{3}\mathrm{0}\mathrm{2}\mathrm{4}\mathrm{2}$ | $\mathrm{2}\mathrm{0}\mathrm{6}\mathrm{6}\mathrm{8}\mathrm{0}$

###  4.4 Metrics

The performance of CESAR is evaluated using several key metrics. The utility
of trained models is measured using test loss and top-1 accuracy on the test
set, except for the MovieLens dataset, on which we measure only test loss.
Besides utility, we also measure the total amount of data transferred between
nodes during training process. This data is partitioned in 3 classes depending
on what data is transferred:

  * •

CESAR-specific prestep overhead, which we call _protocol_ overhead.

  * •

Masked _model parameters_.

  * •

Additional _metadata_ associated with the masked model parameters (, indices).

We compute and record these metrics at the conclusion of each training epoch.
For a comprehensive view, each metric is averaged across all nodes and runs,
ensuring a robust evaluation of the performance of CESAR.

###  4.5 Baselines

CESAR is compared against D-PSGD with Metropolis-Hastings weights [46] over
random subsampling and TopK sparsification for different fractions of selected
indices. We limit the usage of TopK on IID data as previous work has shown
that it performs poorly in non-IID settings [10].

In all experiments, we use mathematical modelling from Corollary 7 to ensure
that the fraction of parameters shared with neighbors in CESAR roughly matches
30 and 50% mark. The actual values we use are shown in Table 2. Furthermore,
to ensure that both algorithms share the exact same fraction of parameters we
first run CESAR and measure mean fraction of shared weights across all nodes
and runs and use the obtained value as the fraction of parameters shared in
D-PSGD with the same settings.

Table 2: Fraction of parameters required to be selected in sparsification ($\alpha$) based on the degree of the receiving node and the fraction of parameters intended to be sent to it ($\beta$) according to Equation 1 $\beta$ |  $\alpha$ [Degree=3] |  $\alpha$ [Degree=6]
---|---|---
30% | 43.83% | 34.22%
50% | 59.70% | 51.39%

Because CESAR works on the basis of obfuscating parameters using masks, we
cannot compress the masked parameters. To keep the evaluation consistent, the
same is done for D-PSGD. On the other hand, Elias gamma compression [11] is
used for compressing indices in both algorithms.

###  4.6 Performance

In this section, we evaluate CESAR on several metrics against the baseline.
First, in Section 4.6.1 we look into the performance of CESAR on several
datasets. In Section 4.6.2, we zoom into one of these datasets and do more
exhaustive analysis of the performance. Section 4.6.3 looks how CESAR scales
with the size and topology of the network. Finally, Section 4.6.4 provides
insights of the security of CESAR in a setting with colluding adversaries.

####  4.6.1 Evaluation Across Multiple Datasets

In this section, we examine the performance and data usage of CESAR in
comparison to D-PSGD across CIFAR-10, CelebA, and MovieLens datasets, with 30%
of parameters shared in a 6-regular graph and using the same set of
hyperparameters.

Figure 3 presents the results of both algorithms using random subsampling, as
well as TopK. All datasets included in Figure 3b follow IID distribution, and
hence the figure excludes MovieLens. In Figure 3a, CIFAR-10 and MovieLens
follow non-IID, while CelebA follows IID distribution.

Upon visual inspection, it is evident that CESAR retains performance levels
that match D-PSGD while transferring up to 35% more data on TopK, and
significantly less on random subsampling. This indicates that in particular
settings, CESAR can be applied in place of D-PSGD without needing to alter
hyperparameters.

Figure 3: Comparison of performance and communication cost of CESAR against
D-PSGD with matching configuration over multiple datasets. CESAR is
overlapping D-PSGD in the performance plots

We also observe that additional data is distributed differently between random
subsampling and TopK. The additional data of protocol (prestep) is negligible
in random subsampling, while metadata used to transfer information about model
indices increases. In contrast, metadata in TopK does not change, while most
of the data overhead comes from protocol (prestep).

On the implementation level, random subsampling does not need to exchange
indices in the prestep, comparably when sending models in D-PSGD. Instead, it
can send only a seed used for generating a mask for selecting indices to send
to their second-degree neighbors. This results in a negligible overhead since
each message is of constant small size. However, when performing an
intersection of these masks, the final result must be represented as a set of
indices, hence increasing the metadata required for transferring masked model.
This increase is dependent on the size of their immediate, rather than second
degree neighborhood.

On the other hand, indices selected by TopK and other non-trivial approaches
must be transmitted as full sets, thereby incurring a higher communication
overhead for each message sent in the prestep. This set has to be sent to each
second degree neighbor, and their number scales with the square of the node
degree in the network.

####  4.6.2 In-Depth Analysis on CIFAR-10

In this section we take a deeper look in the performance of CESAR over various
settings on the CIFAR-10 dataset. For IID data, we use TopK sparsification,
and for non-IID, random subsampling. Measurements are taken for 3 and
6-regular graphs at 30% and 50% of parameters intended for sharing.

The results are shown in Figure 4 and Table 3. They provide several takeaways.
Firstly, the proportion of shared weights using random subsampling is
practically the same as our theorethical model predicts. In contrast, TopK
differs. Yet, it is relatively close to the expected values.

The accuracy of CESAR is comparable to that of D-PSGD. When evaluating on non-
IID distribution using random subsampling, we observe a decrease in accuracy:
a reduction of up to 0.46% on 3-regular graphs, and 0.18% on 6-regular graphs.
We suspect this is due to loss of precision in numerical converison. In order
to mask the parameters, we first convert their values from real numbers to
integers, retaining only the first six decimal places to fit them into a data
type of equivalent size. This process results in slight information loss,
which impacts accuracy.

Conversely, CESAR outperforms D-PSGD on IID distribution using the TopK:
showing an improvement of up to 0.3% on 3-regular graphs, and 0.03% on
6-regular graphs. This demonstrates that, under certain conditions, the unique
properties of CESAR can enhance learning performance without increasing the
fraction of shared parameters. A notable feature of CESAR that may explain
this behavior is that every parameter is received from at least two neighbors,
which may hypothetically improve generalization of the trained model.

Finally, CESAR induces some data overhead in comparison to D-PSGD, ranging
between 12% and 35% for TopK, and between 7% and 11% for random subsampling.
Furthermore, the behavior of this overhead varies with the degree of the
graph. In random subsampling, it remains relatively constant and does not
increase with the degree. In contrast, with TopK we observe a significant
increase as we move from degree 3 to 6. Section 4.6.3 looks deeper into this
behavior.

Figure 4: The accuracy comparison of CESAR against D-PSGD over various
configurations, data distributions and network degrees Table 3: The
performance of CESAR against D-PSGD over regular graphs of various degrees and
fractions of model shared

IIDNIIDIIDIID IIDNIIDIIDIID IIDNIIDIIDIID IIDNIIDIIDIID IIDNIIDIIDIID
IIDNIIDIIDIID IIDNIIDIIDIID IIDNIIDIIDIID NIIDNIIDNIIDIID NIIDNIIDNIIDIID
NIIDNIIDNIIDIID NIIDNIIDNIIDIID NIIDNIIDNIIDIID NIIDNIIDNIIDIID
NIIDNIIDNIIDIID NIIDNIIDNIIDIID TopKTopKTopKrand TopKTopKTopKrand
TopKTopKTopKrand TopKTopKTopKrand TopKTopKTopKrand TopKTopKTopKrand
TopKTopKTopKrand TopKTopKTopKrand randTopKrandrand randTopKrandrand
randTopKrandrand randTopKrandrand randTopKrandrand randTopKrandrand
randTopKrandrand randTopKrandrand  Data distribution Sparsification Degree
Propotion of shared weights [$\%$] Algorithm Maximum achieved accuracy [$\%$]
Total data transferred [$\mathrm{G}\mathrm{B}$] $3$ $31.02$ $71.88$ $5.22$
$71.58$ $4.41$ $50.48$ $72.50$ $7.90$ $72.29$ $7.03$ $6$ $30.13$ $72.42$
$11.56$ $72.40$ $8.58$ $49.67$ $73.12$ $17.28$ $73.09$ $13.83$ $3$ $30.00$
$48.64$ $4.34$ $49.06$ $3.92$ $50.00$ $52.54$ $7.01$ $53.00$ $6.53$ $6$
$30.00$ $50.24$ $8.69$ $50.38$ $7.85$ $50.00$ $55.44$ $14.04$ $55.62$ $13.07$

####  4.6.3 Scalability: Effects of Network Size and Topology

In this section, we examine how the communication overhead of CESAR scales in
practice. As observed in Section 4.6.1 and Section 4.6.2, the overhead with
random subsampling remains constant regardless of the network topology. In
contrast, it increases when TopK is applied.

Section 3.4.3 derives that the communication overhead of the prestep in CESAR
is $(\alpha d\delta_{\text{max}}^{2})$, as a node sends their indices to each
second degree neighbor, and their number typically scales with the square of
the degree in the network. To verify this, we ran CESAR with TopK on a 96-node
$k$-regular network with $k$ values of 3, 6, 9, and 12. In each run, 40% of
parameters were selected for sparsification, and we recorded only the overhead
caused by the protocol (prestep).

The results for the given degrees are shown in Figure 5. They indicate that
the overhead scales linearly, contrary to the quadratic scaling we expected.
However, Table 4 reveals that the overhead of the prestep actually scales with
the size of the second degree neighborhood. Because the network size is
limited, it is common for two nodes to share a neighbor, hence reducing the
size of the second degree neighborhood compared to a theoretical model where
the network size is infinite and nodes sharing a neighbor are uncommon. This
also implies that the total overhead of the prestep is limited by the size of
the network to $(\alpha d|\mathcal{N}|)$. This underscores the importance of
the ability of CESAR to reuse masks that two nodes agreed upon when sharing
their masked models with multiple common neighbors.

Table 4: Amount of data transferred per node in CESAR prestep during training for different graph degrees and their relation to the size of second degree neighborhood Degree |  CESAR overhead [$\mathrm{G}\mathrm{B}$] |  Average $2^{nd}$ degree neighborhood size |  CESAR overhead per $2^{nd}$ degree neighbor [$\mathrm{G}\mathrm{B}$]
---|---|---|---
$3$ |  $0.63$ |  $5.93$ |  $0.1064$
$6$ |  $2.77$ |  $26.87$ |  $0.1031$
$9$ |  $5.49$ |  $53.48$ |  $0.1027$
$12$ |  $7.77$ |  $75.16$ |  $0.1034$

Figure 5: Amount of data transferred per node in CESAR prestep during training
for different graph degrees

####  4.6.4 Configuring for Minimized Collusion Risks

Section 3.4.2 shows formal privacy guarantees in systems where the number of
adversaries is known. However, this is often not the case, and the number of
adversaries has to be estimated. Therefore, we look at how the privacy risk
changes as we increase the masking requirement ($s$) in CESAR for a 25-regular
graph with 100 nodes in settings with different number of adversaries.

This is performed by running a Monte Carlo simulation $250\,000$ times for
each masking requirement. Each simulation involves generating a random
25-regular graph and assigning each node to be either adversarial or honest.
All adversarial nodes are assumed to collude with each other. Over the
simulation, we measure the probability that any honest node in the network is
at risk of adversaries. A node is considered to be at risk if any of their
parameters can be inferred by the adversaries. This can only happen when the
node is connected to an adversary who has at least $s$ adversarial neighbors.

The simulation results are shown in Figure 6. The results reveal that even for
masking requirement lower than the total number of adversaries, yet
sufficiently high, the risk can be practically nonexistent to any node in the
network. For instance, for the setting with 15 adversaries we do not come
across any graphs under risk for masking requirement $\geq 13$ in any of our
simulations. Furthermore, with masking requirement $9$ the risk is $1.45\%$ in
this setting.

Figure 6: Estimated attack risk to any honest node in randomly generated 100
node graph with 25-regular topology

##  5 Related work

##### Privacy attacks.

We are seeing continuous work on privacy attacks against ML models in
distributed machine learning. Gradient inversion [14, 51], membership
inference [40], and attribute inference attacks [50] are commonly employed to
extract information about the training set from the exchanged models. Both
gradient inversion and membership inference have been also shown to be
effective against D-PSGD [32]. While sparsification has been suggested as a
defense against privacy attacks [45, 38, 51], Yue [49] present a gradient
inversion attack on gradients sparsified with TopK. These attacks, however,
are not well understood under the presence of secure aggregation. Furthermore,
the masks in CESAR can be considered as perturbations of model parameters in
noise-based defenses against privacy attacks in ML [44, 48, 8]. Since privacy
attacks to averaged models would succeed in CESAR in the same way they would
in any other secure aggregation scheme, we consider them orthogonal to this
work.

##### Secure aggregation.

Secure aggregation works on the principle of obfuscating local models and
making only the aggregated model public, hence making attacks harder to
perform. It has been a prominent approach for keeping models secure in FL
setting. The majority of work in this field is based on ideas proposed by [4]:
pairwise additive masking, node-specific masks and the use of Shamir [37]
secret sharing for recovery when nodes fail. In comparison, work on secure
aggregation in DL setting is limited [15], and often involves additional
servers [17]. Additionally, integrating data reduction techniques within
secure aggregation presents significant challenges, particularly in
environments where data usage is limited. In comparison to existing secure
aggregations in DL, our solution is the first that includes sparsification in
its core structure while avoiding use of additional servers.

##### Secure aggregation with sparsification.

Reduction of model size is a prominent research topic, ranging from
compression [7, 33], sparsification [39, 41, 27] and quantization [36, 2], as
well as other techniques [10, 22]. However, there is limited research done in
incorporating these approaches into secure aggregation. Most of this research
has been limited to FL. SparseSecAgg [12] pioneers the integration of
sparsification with secure aggregation. Their method integrates a
sparsification mechanism directly into the aggregation protocol, albeit with
limitations in compatibility with other sparsification techniques. Lu [29]
advance this field further, incorporating TopK sparsification as a part of
their protocol. This work also raises the concern of information leakage
caused by sharing the set of indices selected in sparsification with other
nodes, and proposes adding additional randomly selected indices to reduce the
risk. Their approach shows resemblance to ours, even though in FL setting, as
it focuses on masking union of indices selected by different nodes, rather
than their intersection like we do. Nevertheless, considering both are
designed for FL they rely on the presence of a central node and hence they
cannot be trivially adapted to DL setting.

##  6 Discussion

##### Limited selection of sparsification approaches.

While the paper focuses on random subsampling and TopK for sparsification,
other approaches can also be used in their place interchageably. However,
certain sparsifications rely on storing additional information and carrying
them from one round to another, often for the purpose of error compensation.
They are often designed with an assumption that their result is sent without
changes to all neighbours in the same form, but CESAR takes the result of
sparsification and sends a different subsets of it to each neighbor. Thefore,
branching the state for each neighbor without an obvious way to merge them
into one state usable for the next round of sparsification. Hence, CESAR does
not support sparsifications that rely on carrying information of their choices
from previous rounds in order to perform parameter selection in the current
round.

##### Disconnecting nodes.

While CESAR shows good performance, it does not support nodes dropping out. in
FL literature Shamir’s secret sharing [37] is often used to remove secrets of
disconnected nodes. However, in comparison, in DL the size of individual
aggregation is determined by the degree of a node, which is often relatively
small. Therefore, we assume that dropping out of nodes in this setting may be
relatively infrequent, but also too expensive to recover from in same way done
in FL. We hypothesize that starting the protocol from the beginning may be a
cheaper way to recover when dropouts occur. Furthermore, as pairwise masks
remain private there would be no need to rerun the prestep of the protocol,
and instead use the data received in the initial attempt. However, these
claims are out of the scope of this paper and they need extensive testing.

##  7 Conclusion

This paper presented CESAR, a novel secure aggregation protocol tailored for
DL training. CESAR addresses the unique challenges posed by integrating secure
aggregation with various sparsification techniques, a crucial concern in
decentralized learning for preserving privacy and enhancing communication
efficiency. Our protocol effectively balances the trade-offs between privacy
preservation, communication overhead, and model accuracy.

The experimental results demonstrate that CESAR, when combined with random
subsampling, matches the performance of D-PSGD while only adding a modest
increase in data overhead. Additionally, CESAR outperforms TopK sparsification
methods in accuracy, underscoring its effectiveness in maintaining model
quality. These achievements are significant in the context of decentralized
learning, where efficient communication and robust privacy are crucial.

Furthermore, the adaptability of CESAR to different forms of sparsification
and its robustness against honest-but-curious adversaries, with potential
adaptations for collusion resistance, mark it as a versatile and secure
solution for DL scenarios.

Future work could explore further optimization of CESAR for different network
topologies and more complex models, as well as its combination with other
sparsification techniques. The integration of CESAR in real-world applications
promises to significantly contribute to the advancement of secure, efficient,
and privacy-preserving decentralized machine learning systems.

## References

  * [1] Gergely Ács and Claude Castelluccia.  I have a dream!(differentially private smart metering).  In International Workshop on Information Hiding, pages 118–132. Springer, 2011.
  * [2] Dan Alistarh, Demjan Grubic, Jerry Z. Li, Ryota Tomioka, and Milan Vojnovic.  QSGD: Communication-efficient SGD via gradient quantization and encoding.  In NIPS, 2017.
  * [3] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli.  The convergence of sparsified gradient methods.  In NeurIPS, 2018.
  * [4] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth.  Practical secure aggregation for privacy-preserving machine learning.  In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175–1191, 2017.
  * [5] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar.  Leaf: A benchmark for federated settings, 2019.
  * [6] Mingqing Chen, Rajiv Mathews, Tom Ouyang, and Françoise Beaufays.  Federated learning of out-of-vocabulary words.  arXiv preprint arXiv:1903.10635, 2019.
  * [7] Yann Collet.  LZ4, 2022.
  * [8] Edwige Cyffers, Mathieu Even, Aurélien Bellet, and Laurent Massoulié.  Muffliato: Peer-to-peer privacy amplification for decentralized optimization and averaging.  In Advances in Neural Information Processing Systems (NeurIPS ’22), 2022.
  * [9] Akash Dhasade, Anne-Marie Kermarrec, Rafael Pires, Rishi Sharma, and Milos Vujasinovic.  Decentralized learning made easy with decentralizepy.  In Proceedings of the 3rd Workshop on Machine Learning and Systems, pages 34–41, 2023.
  * [10] Akash Dhasade, Anne-Marie Kermarrec, Rafael Pires, Rishi Sharma, Milos Vujasinovic, and Jeffrey Wigger.  Get more for less in decentralized learning systems.  In 2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS ’23), pages 463–474, 2023.
  * [11] Peter Elias.  Universal codeword sets and representations of the integers.  IEEE transactions on information theory, 21(2):194–203, 1975.
  * [12] Irem Ergun, Hasin Us Sami, and Basak Guler.  Sparsified secure aggregation for privacy-preserving federated learning.  arXiv preprint arXiv:2112.12872, 2021.
  * [13] European Commission.  Fundamental texts on european private law, 2016.
  * [14] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller.  Inverting gradients - how easy is it to break privacy in federated learning?  In Advances in Neural Information Processing Systems (NeurIPS ’20), volume 33, pages 16937–16947, 2020.
  * [15] Nirupam Gupta, Jonathan Katz, and Nikhil Chopra.  Privacy in distributed average consensus**this work was supported by the naval air warfare center aircraft division - pax river, md under contract n00421132m022.  IFAC-PapersOnLine, 50(1):9515–9520, 2017.  20th IFAC World Congress.
  * [16] F. Maxwell Harper and Joseph A. Konstan.  The movielens datasets: History and context.  ACM Trans. Interact. Intell. Syst., 5(4), dec 2015.
  * [17] Lie He, An Bian, and Martin Jaggi.  Cola: Decentralized linear learning.  Advances in Neural Information Processing Systems, 31, 2018.
  * [18] Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip B. Gibbons.  The non-IID data quagmire of decentralized machine learning.  In ICML, 2020.
  * [19] Li Huang, Yifeng Yin, Zeng Fu, Shifa Zhang, Hao Deng, and Dianbo Liu.  LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data, 2020.
  * [20] Abhinav Jain, Hima Patel, Lokesh Nagalapatti, Nitin Gupta, Sameep Mehta, Shanmukha Guttula, Shashank Mujumdar, Shazia Afzal, Ruhi Sharma Mittal, and Vitobha Munigala.  Overview and importance of data quality for machine learning tasks.  In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 3561–3562, 2020.
  * [21] Daniel Jarrett, Eleanor Stride, Katherine Vallis, and Mark J. Gooding.  Applications and limitations of machine learning in radiation oncology.  92(1100):20190001, 2019.
  * [22] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi.  Decentralized stochastic optimization and gossip algorithms with compressed communication.  In ICML, 2019.
  * [23] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  Computer, 42(8):30–37, aug 2009.
  * [24] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  The cifar-10 dataset.  55(5), 2014.
  * [25] Anusha Lalitha, Shubhanshu Shekhar, Tara Javidi, and Farinaz Koushanfar.  Fully decentralized federated learning.  In Third workshop on bayesian deep learning (NeurIPS), volume 2, 2018.
  * [26] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  In NIPS, 2017.
  * [27] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally.  Deep gradient compression: Reducing the communication bandwidth for distributed training.  In ICLR, 2018.
  * [28] Dianbo Liu, Dmitriy Dligach, and Timothy Miller.  Two-stage federated phenotyping and patient representation learning.  In Proceedings of the 18th BioNLP Workshop and Shared Task, pages 283–291. Association for Computational Linguistics, 2019.
  * [29] Shiwei Lu, Ruihu Li, Wenbin Liu, Chaofeng Guan, and Xiaopeng Yang.  Top-k sparsification with secure aggregation for privacy-preserving federated learning.  Computers & Security, 124:102993, 2023.
  * [30] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [31] Róbert Ormándi, István Hegedűs, and Márk Jelasity.  Gossip learning with linear models on fully distributed data.  Concurrency and Computation: Practice and Experience, 25(4), 2013.
  * [32] Dario Pasquini, Mathilde Raynal, and Carmela Troncoso.  On the (in) security of peer-to-peer decentralized machine learning.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 418–436, 2023.
  * [33] Igor Pavlov.  LZMA SDK, 2022.
  * [34] Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays.  Federated learning for emoji prediction in a mobile keyboard, 2019.
  * [35] Christopher A Ramezan, Timothy A Warner, Aaron E Maxwell, and Bradley S Price.  Effects of training set size on supervised machine-learning land-cover classification of large-area high-resolution remotely sensed data.  Remote Sensing, 13(3):368, 2021.
  * [36] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and application to data-parallel distributed training of speech DNNs.  In Interspeech 2014, September 2014.
  * [37] Adi Shamir.  How to share a secret.  Communications of the ACM, 22(11):612–613, 1979.
  * [38] Reza Shokri and Vitaly Shmatikov.  Privacy-preserving deep learning.  In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310–1321, 2015.
  * [39] Reza Shokri and Vitaly Shmatikov.  Privacy-preserving deep learning.  In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 909–910, 2015.
  * [40] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 3–18, 2017.
  * [41] Nikko Strom.  Scalable distributed DNN training using commodity GPU cloud computing.  In 16th Annual Conference of the International Speech Communication Association, 2015.
  * [42] Zhenheng Tang, Shaohuai Shi, and Xiaowen Chu.  Communication-efficient decentralized learning with sparsification and adaptive peer selection.  In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), 2020.
  * [43] United States Congress.  Health insurance portability and accountability act of 1996, 1996.
  * [44] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Hang Su, Bo Zhang, and H Vincent Poor.  User-level privacy-preserving federated learning: Analysis and performance optimization.  IEEE Transactions on Mobile Computing, 21(9):3388–3401, 2021.
  * [45] Wenqi Wei, Ling Liu, Margaret Loper, Ka-Ho Chow, Mehmet Emre Gursoy, Stacey Truex, and Yanzhao Wu.  A framework for evaluating client privacy leakages in federated learning.  In Computer Security–ESORICS 2020: 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14–18, 2020, Proceedings, Part I 25, pages 545–566. Springer, 2020.
  * [46] Lin Xiao and Stephen Boyd.  Fast linear iterations for distributed averaging.  Systems & Control Letters, 53(1):65–78, 2004.
  * [47] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays.  Applied federated learning: Improving google keyboard query suggestions, 2018.
  * [48] Da Yu, Huishuai Zhang, Wei Chen, and Tie-Yan Liu.  Do not let privacy overbill utility: Gradient embedding perturbation for private learning.  arXiv preprint arXiv:2102.12677, 2021.
  * [49] Kai Yue, Richeng Jin, Chau-Wai Wong, Dror Baron, and Huaiyu Dai.  Gradient obfuscation gives a false sense of security in federated learning.  In 32nd USENIX Security Symposium (USENIX Security 23), pages 6381–6398, 2023.
  * [50] Benjamin Zi Hao Zhao, Aviral Agrawal, Catisha Coburn, Hassan Jameel Asghar, Raghav Bhaskar, Mohamed Ali Kaafar, Darren Webb, and Peter Dickinson.  On the (in) feasibility of attribute inference attacks on machine learning models.  In 2021 IEEE European Symposium on Security and Privacy (EuroS&P), pages 232–251. IEEE, 2021.
  * [51] Ligeng Zhu, Zhijian Liu, and Song Han.  Deep leakage from gradients.  Advances in neural information processing systems (NeurIPS ’19), 32, 2019.
  * [52] Xiangxin Zhu, Carl Vondrick, Charless C. Fowlkes, and Deva Ramanan.  Do we need more training data?  119(1):76–92, 2016.

##  Appendix A Scalability

In this section, we examine how the communication cost of CESAR scales with an
increasing number of nodes in the network. Measurements were conducted for
networks comprising 48, 96, 192, and 288 nodes. Each experiment was performed
within a 5-regular network using the CIFAR-10 dataset. The dataset was divided
into 288 equally-sized segments, corresponding to the maximum node count, with
each node receiving one segment. In cases where the number of segments
surpassed the number of nodes, the excess segments remained unassigned and
were not utilized in the training process.

Figure 7: Amount of data transferred per node during training for different number of nodes Table 5: Amount of data transferred per node during training using CESAR for a fixed setup in networks of different sizes Number of nodes |  | Parameter data
---
[$\mathrm{G}\mathrm{B}$]
| CESAR overhead
---
[$\mathrm{G}\mathrm{B}$]
$48$ | $9.07$ | $2.25$
$96$ | $9.07$ | $2.39$
$192$ | $9.06$ | $2.48$
$288$ | $9.05$ | $2.49$

Figure 7 illustrates that the communication overhead of CESAR remains
practically independent of the number of nodes in the network. However, a more
detailed examination in Table 5 reveals a marginally higher CESAR overhead for
larger networks. This phenomenon can be attributed to the experimental setup.
As discussed in Section 3.4.3, the number of messages sent during the prestep
phase of CESAR is proportional to the number of second degree neighbors. With
fewer nodes in the network, while maintaining a fixed topology, it is more
likely for two neighbors to share a common neighbor. This overlap effectively
reduces the average second degree neighborhood size, thereby lowering the
overhead in the prestep.

##  Appendix B Postponed Proofs

###  B.1 Proof of Theorem 6

###### Proof.

Random subsampling ensures that the sparsification selects indices with
uniform probability $\alpha$ and we assume that the sparsification carried out
by each node is independent.

Without the loss of generality, let us consider the nodes
$N,N^{\prime}\in\mathcal{N}$ where $N$ is the sender and $N^{\prime}$ is the
receiver (i.e., $\\{N,N^{\prime}\\}\in E$). With the masking requirement of
$s$, we note that $N$ shares a parameter with $N^{\prime}$ iff it has been
sampled by at least $s$ other neighbors of $N^{\prime}$. Therefore, the
probability $\hat{\pi}^{(p)}_{N\rightarrow N^{\prime}}$ of $N$ sharing a
parameter $p\in I$ with $N^{\prime}$ in one round of CESAR is given by:

$\displaystyle\hat{\pi}^{(p)}_{N\rightarrow N^{\prime}}$
$\displaystyle=\pi_{i}^{(p)}\left(1-\prod_{j\in\operatorname{View}_{2}(N)}\left(1-\pi_{j}^{(p)}\right)\right)$
$\displaystyle=\alpha\sum_{i=s}^{\delta-1}\binom{\delta-1}{i}\alpha^{i}(1-\alpha)^{\delta-1-i}$
$\displaystyle=\sum_{i=s}^{\delta-1}\binom{\delta-1}{i}\alpha^{i+1}(1-\alpha)^{\delta-1-i}$

Hence, let $X_{N\rightarrow N^{\prime}}$ be the random variable denoting the
number of parameters that $N$ shares with $N^{\prime}$ in one round with a
masking requirement of $s$, and for every $p\in I$, let $X_{N\rightarrow
N^{\prime}}(p)=\mathbb{I}_{\\{N\text{ shares }p\text{ with }N^{\prime}\\}}$ be
the random variable denoting whether or not $N$ shares the parameter $p$ with
$N^{\prime}$. Therefore, noting that $X_{N\rightarrow N^{\prime}}=\sum_{p\in
I}X_{N\rightarrow N^{\prime}}(p)$, we have:

$\displaystyle\mathbb{E}\left[X_{N\rightarrow N^{\prime}}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{p\in I}X_{N\rightarrow
N^{\prime}}(p)\right]$ $\displaystyle=\sum_{p\in
I}\mathbb{E}\left[X_{N\rightarrow N^{\prime}}(p)\right]$
$\displaystyle=\sum_{p\in I}\mathbb{P}\left[\\{N\text{ shares }p\text{ with
}N^{\prime}\\}\right]$ $\displaystyle=d\hat{\pi}^{(p)}_{N\rightarrow
N^{\prime}}$

Thus, the expected fraction of the model parameters that $N$ shares with
$N^{\prime}$ is given by:

$\displaystyle\beta\left(\alpha,\delta,s\right)$
$\displaystyle=\mathbb{E}\left[\frac{X_{N\rightarrow N^{\prime}}}{d}\right]$
$\displaystyle=\frac{\mathbb{E}\left[X_{N\rightarrow N^{\prime}}\right]}{d}$
$\displaystyle=\hat{\pi}^{(p)}_{N\rightarrow N^{\prime}}$
$\displaystyle=\sum_{i=s}^{\delta-1}\binom{\delta-1}{i}\alpha^{i+1}(1-\alpha)^{\delta-1-i}$

∎

  *[ML]: machine learning
  *[DL]: decentralized learning
  *[CESAR]: Communication-efficient secure aggregation
  *[D-PSGD]: decentralized parallel stochastic gradient descent
  *[IID]: independent and identically distributed
  *[GDPR]: general data protection regulation
  *[HIPAA]: health insurance portability and accountability act
  *[FL]: federated learning
  *[SGD]: stochastic gradient descent
  *[RMW]: random model walk


# 3D View Prediction Models of the Dorsal Visual Stream

Gabriel H. Sarch<EMAIL_ADDRESS>
Neuroscience Institute, Carnegie Mellon University, Pittsburgh, PA, USA.
Hsiao-Yu Fish Tung<EMAIL_ADDRESS>
Department of Brain and Cognitive Sciences, Massachusetts Institute of
Technology, Cambridge, MA, USA. Aria Y. Wang<EMAIL_ADDRESS>
Neuroscience Institute, Carnegie Mellon University, Pittsburgh, PA, USA. Jacob
S. Prince<EMAIL_ADDRESS>
Department of Psychology, Harvard University, Cambridge, MA, USA. Michael J.
Tarr<EMAIL_ADDRESS>
Department of Psychology & Neuroscience Institute, Carnegie Mellon University,
Pittsburgh, PA, USA

## Abstract

Deep neural network representations align well with brain activity in the
ventral visual stream. However, the primate visual system has a distinct
dorsal processing stream with different functional properties. To test if a
model trained to perceive 3D scene geometry aligns better with neural
responses in dorsal visual areas, we trained a self-supervised geometry-aware
recurrent neural network (GRNN) to predict novel camera views using a 3D
feature memory. We compared GRNN to self-supervised baseline models that have
been shown to align well with ventral regions using the large-scale fMRI
Natural Scenes Dataset (NSD). We found that while the baseline models
accounted better for ventral brain regions, GRNN accounted for a greater
proportion of variance in dorsal brain regions. Our findings demonstrate the
potential for using task-relevant models to probe representational differences
across visual streams.

> Keywords: Visual Streams. DNN. Self-Supervision. fMRI.

The visual cortex has been traditionally organized into two processing streams
Ungerleider (1982), the ventral and dorsal111Following finzi2022deep, we refer
to the dorsal stream as the parietal stream to avoid confusion with the
lateral stream. (parietal) pathways, with a third lateral pathway being
proposed recently Weiner Grill-Spector (2013); Wurm Caramazza (2022); Pitcher
Ungerleider (2021). Deep neural networks (DNNs) trained for object recognition
have been found to be highly predictive of the ventral visual stream
processing Yamins . (2014). However, it remains unclear whether DNNs for
recognition are well suited for predicting non-ventral visual processing, in
the lateral or parietal visual streams.

DNNs optimized for egomotion estimation or action recognition may better
predict neural responses in the parietal and lateral visual streams Mineault .
(2021); Güçlü van Gerven (2017). However, DNNs trained for action recognition
do not appear to differentiate themselves from DNNs trained for object
recognition in terms of predicting activity across the visual streams Finzi .
(2022). Recent experimental work has demonstrated evidence that the parietal
stream plays a major role in global shape perception during object
recognition, while the ventral stream may be more involved in local shape and
texture encoding Ayzenberg Behrmann (2022). Additionally, a well-established
function of the parietal pathway is depth and 3-D shape perception Welchman
(2016), and it has been suggested that representations in these areas may
arise from self-supervised predictive coding Jehee . (2006); Raman Sarkar
(2016); Bakhtiari . (2021).

Figure 1: A. ROI definitions on a flat map of the fsaverage cortex. B. GRNN
training procedure. C. Difference (subtraction) between GRNN and DINO noise-
corrected $R^{2}$’s for each voxel for example S1. We observe higher $R^{2}$
for GRNN (darker blue) in high-level parietal regions, and conversely higher
$R^{2}$ for DINO (darker red) in high-level ventral regions.

What kinds of neural networks might best account for neural processing in the
parietal visual stream? We propose that the “GRNN” model from tung2019learning
is a promising “proxy model” Leeds . (2013) for investigating computational
constraints within the parietal pathway. GRNN learns spatially-aware 3D
representations of visual inputs and is trained in a self-supervised manner to
predict the complete 3D feature representation of a scene from one camera
viewpoint, given input from another camera viewpoint. The model can “fill in”
and predict features in the 3D feature map to represent the complete 3D
geometry and shape of a scene from a partial 2.5D view. In this sense, the
task solved by the GRNN model aligns well with several of the commonly
proposed functional characteristics of the parietal stream.

We examined GRNN’s ability to predict neural responses as measured by fMRI in
response to viewing complex, natural scenes Allen . (2022). As baseline
models, we used self-supervised DNNs that were trained to maximize agreement
between different augmentations of 2D images, which have previously been shown
to be highly predictive of ventral visual stream Caron . (2021); Chen .
(2020). Consistent with our proposal, we found that the GRNN model was
typically a better predictor of high-level parietal visual areas, while the
self-supervised 2D models were typically better predictors of high-level
ventral visual areas. These results demonstrate the potential for using task-
relevant models aligned with hypotheses regarding brain function as a means
for probing representational differences across visual streams.

## Methods

fMRI dataset. NSD contains measurements of 7T fMRI responses (1.8 mm, 1.6 s)
from 8 participants who each viewed 9,000–10,000 distinct color natural scenes
(22,000–30,000 trials). Participants fixated centrally and performed a long-
term continuous image recognition task. The noise ceiling (NC) was estimated
in each voxel as described in Allen2022. We only include voxels with NC $\geq$
10% variance and report noise-ceiling normalized prediction accuracy.
Regions of Interest (ROIs). We used NSD’s ”streams” anatomical atlas to define
seven ROIs that cover the parietal, lateral, and ventral visual streams (Fig.
1A; also see finzi2022deep). We also looked at sub-regions within each stream
using glasser2016multi and wang2015probabilistic atlases. We also examined
three scene ROIs (RSC, OPA, and PPA) obtained by thresholding the category
functional localizer.
GRNN training and inference. We used the fang2020move dataset of RGB-D images
($n=28345$) of indoor Straub . (2019) and outdoor Dosovitskiy . (2017) scenes
for our GRNN training. The self-supervised training procedure from
harley2019learning was used, which utilizes a view-contrastive loss in feature
space. This involves back-projecting an RGB image into a 3D voxel grid,
deriving a 3D feature map, and pulling corresponding features together from
egomotion-stabilized 3D feature maps (Fig. 1B). To extract GRNN
representations for NSD images, we used a fixed camera field of view and
estimated depth maps using MiDaS Ranftl . (2020).
Comparison models. We compared GRNN to two self-supervised DNNs that have
shown exceptional performance in object recognition and ventral stream
predictivity, even rivaling supervised models Zhuang . (2021). These models,
DINO Caron . (2021) (ViT-small backbone) and SimCLR SimCLR Chen . (2020)
(ResNet-50 backbone), have different self-supervised learning objectives and
neural architectures. We trained all models on the same dataset of indoor and
outdoor scenes to ensure a fair comparison with GRNN.
Fitting to brain data. We evaluated the performance of each model on a held-
out test set using an 85:15 validation split for each subject separately. To
reduce dimensionality, we used PCA to project the features into a lower
dimensional subspace and retained the first 1000 components
(schrimpf2018brain). We fit the features of each layer to each brain voxel
using ridge regression, and determined each voxel’s regularization parameter
through 7-fold cross-validation. We assessed model performance on the test
data using Pearson’s correlation and coefficient of determination ($R^{2}$),
and reported the best fitting layer for each subject in each ROI.

Figure 2: A. noise-corrected $R^{2}$ of model fit for each ROI. Each dot
represents a subject. Bars and error bars are mean and standard deviation
across subjects (N=8), respectively. B. Same as A but for subregion ROIs.

## Results

We evaluated the performance of three models for predicting voxel responses to
natural images. A representative subject (Fig. 1C) indicates that GRNN
outperforms DINO in high-level parietal regions, while DINO performs better in
high-level ventral regions. Prediction accuracy ($R^{2}$) within each stream
across all subjects reveals that GRNN predicts high-level parietal regions
better than DINO and SimCLR (GRNN$>$DINO mid-parietal $p=0.016$, high-parietal
$p=0.038$; GRNN $>$ SimCLR, high-parietal $p=0.005$). DINO also performs
better than GRNN in high-level ventral regions (paired $t$-test; $p=0.0052$).
There was no significant difference between GRNN and SimCLR in high-level
ventral (paired $t$-test; $p=0.98$) and no significant difference between
models in the mid- and high-level lateral ROIs. Paired $t$-tests on sub-ROIs
within each stream revealed that GRNN predicts voxel responses with higher
accuracy than DINO in V3AB ($p=0.021$), as well as early IPS regions and SPL
compared to DINO (GRNN$>$DINO, IPS0; $p=0.017$, IPS1; $p=0.035$, IPS2;
$p=0.039$, SPL; $0.0078$) and SimCLR (GRNN$>$SimCLR, IPS0; $p=0.018$, IPS1;
$p=0.010$, IPS2; $p=0.013$, SPL; $0.015$). No difference between models was
found in higher-order IPS (GRNN$>$DINO, IPS3; $p=0.22$, IPS4; $p=0.35$, IPS5;
$p=0.058$). In high-level ventral regions DINO had significantly higher
predictivity than GRNN in 4/6 regions examined (DINO$>$GRNN, PHC; $0.023$,
PHA; $0.0019$, VMV; $0.047$, VVC; $p=0.00066$). In scene ROIs DINO
significantly outperformed GRNN in two scene regions located more ventrally
(DINO$>$GRNN, PPA; $p=0.0034$, RSC; $0.00091$), whereas GRNN performed better
in predicting voxel responses in OPA, which is located more dorsally
(GRNN$>$DINO $p=0.011$; GRNN$>$SimCLR $p=0.037$). These results indicate that
a self-supervised model trained for 3D view prediction performs better than
models trained to capture augmentation-invariant 2D image statistics in
predicting voxel responses in parietal areas. The opposite trend was found in
ventral regions, particularly with DINO outperforming GRNN.

## Discussion

Our research indicates that a 3D view prediction model is better suited for
predicting voxel responses in the parietal visual stream compared to 2D
augmentation-invariant self-supervised models in a large-scale fMRI dataset of
humans viewing natural images. However, more research is necessary to better
understand the observed differences and to explore the impact of training and
fMRI datasets on model alignment.

## Acknowledgments

This material is based upon work supported by National Science Foundation
grants GRF DGE1745016 & DGE2140739 (GS), a DARPA Young Investigator Award, a
NSF CAREER award, an AFOSR Young Investigator Award, and DARPA Machine Common
Sense. Any opinions, findings and conclusions or recommendations expressed in
this material are those of the authors and do not necessarily reflect the
views of the United States Army, the National Science Foundation, or the
United States Air Force.

## References

  * Allen . (2022) Allen2022Allen, EJ., St-Yves, G., Wu, Y., Breedlove, JL., Prince, JS., Dowdle, LT.Kay, K.  2022\.  A massive 7T fMRI dataset to bridge cognitive neuroscience and artificial intelligence A massive 7T fMRI dataset to bridge cognitive neuroscience and artificial intelligence.  Nature Neuroscience251116–126.  10.1038/s41593-021-00962-x
  * Ayzenberg Behrmann (2022) ayzenberg2022dorsalAyzenberg, V. Behrmann, M.  2022\.  The dorsal visual pathway represents object-centered spatial relations for object recognition The dorsal visual pathway represents object-centered spatial relations for object recognition.  Journal of Neuroscience42234693–4710.
  * Bakhtiari . (2021) bakhtiari2021functionalBakhtiari, S., Mineault, P., Lillicrap, T., Pack, C. Richards, B.  2021\.  The functional specialization of visual cortex emerges from training parallel pathways with self-supervised predictive learning The functional specialization of visual cortex emerges from training parallel pathways with self-supervised predictive learning.  Advances in Neural Information Processing Systems3425164–25178.
  * Caron . (2021) caron2021emergingCaron, M., Touvron, H., Misra, I., Jégou, H., Mairal, J., Bojanowski, P. Joulin, A.  2021\.  Emerging properties in self-supervised vision transformers Emerging properties in self-supervised vision transformers.  Proceedings of the IEEE/CVF international conference on computer vision Proceedings of the ieee/cvf international conference on computer vision ( 9650–9660).
  * Chen . (2020) chen2020simpleChen, T., Kornblith, S., Norouzi, M. Hinton, G.  2020\.  A simple framework for contrastive learning of visual representations A simple framework for contrastive learning of visual representations.  International conference on machine learning International conference on machine learning ( 1597–1607).
  * Dosovitskiy . (2017) Dosovitskiy17Dosovitskiy, A., Ros, G., Codevilla, F., Lopez, A. Koltun, V.  2017\.  CARLA: An Open Urban Driving Simulator CARLA: An open urban driving simulator.  Proceedings of the 1st Annual Conference on Robot Learning Proceedings of the 1st annual conference on robot learning ( 1–16).
  * Fang . (2020) fang2020moveFang, Z., Jain, A., Sarch, G., Harley, AW. Fragkiadaki, K.  2020\.  Move to see better: Self-improving embodied object detection Move to see better: Self-improving embodied object detection.  arXiv preprint arXiv:2012.00057.
  * Finzi . (2022) finzi2022deepFinzi, D., Yamins, DL., Kay, K. Grill-Spector, K.  2022\.  Do deep convolutional neural networks accurately model representations beyond the ventral stream? Do deep convolutional neural networks accurately model representations beyond the ventral stream?  2022 Conference on Cognitive Computational Neuroscience. 2022 conference on cognitive computational neuroscience.
  * Glasser . (2016) glasser2016multiGlasser, MF., Coalson, TS., Robinson, EC., Hacker, CD., Harwell, J., Yacoub, E.others  2016\.  A multi-modal parcellation of human cerebral cortex A multi-modal parcellation of human cerebral cortex.  Nature5367615171–178.
  * Güçlü van Gerven (2017) gucclu2017increasinglyGüçlü, U. van Gerven, MA.  2017\.  Increasingly complex representations of natural movies across the dorsal stream are shared between subjects Increasingly complex representations of natural movies across the dorsal stream are shared between subjects.  NeuroImage145329–336.
  * Harley . (2019) harley2019learningHarley, AW., Lakshmikanth, SK., Li, F., Zhou, X., Tung, HYF. Fragkiadaki, K.  2019\.  Learning from unlabelled videos using contrastive predictive neural 3d mapping Learning from unlabelled videos using contrastive predictive neural 3d mapping.  arXiv preprint arXiv:1906.03764.
  * Jehee . (2006) jehee2006learningJehee, JF., Rothkopf, C., Beck, JM. Ballard, DH.  2006\.  Learning receptive fields using predictive feedback Learning receptive fields using predictive feedback.  Journal of Physiology-Paris1001-3125–132.
  * Leeds . (2013) Leeds2013Leeds, DD., Seibert, DA., Pyles, JA. Tarr, MJ.  2013\.  Comparing visual representations across human fMRI and computational vision. Comparing visual representations across human fMRI and computational vision.  J Vis131325.  10.1167/13.13.25
  * Mineault . (2021) mineault2021yourMineault, P., Bakhtiari, S., Richards, B. Pack, C.  2021\.  Your head is there to move you around: Goal-driven models of the primate dorsal pathway Your head is there to move you around: Goal-driven models of the primate dorsal pathway.  Advances in Neural Information Processing Systems3428757–28771.
  * Pitcher Ungerleider (2021) pitcher2021evidencePitcher, D. Ungerleider, LG.  2021\.  Evidence for a third visual pathway specialized for social perception Evidence for a third visual pathway specialized for social perception.  Trends in Cognitive Sciences252100–110.
  * Raman Sarkar (2016) raman2016predictiveRaman, R. Sarkar, S.  2016\.  Predictive coding: a possible explanation of filling-in at the blind spot Predictive coding: a possible explanation of filling-in at the blind spot.  PloS one113e0151194.
  * Ranftl . (2020) ranftl2020towardsRanftl, R., Lasinger, K., Hafner, D., Schindler, K. Koltun, V.  2020\.  Towards robust monocular depth estimation: Mixing datasets for zero-shot cross-dataset transfer Towards robust monocular depth estimation: Mixing datasets for zero-shot cross-dataset transfer.  IEEE transactions on pattern analysis and machine intelligence4431623–1637.
  * Schrimpf . (2018) schrimpf2018brainSchrimpf, M., Kubilius, J., Hong, H., Majaj, NJ., Rajalingham, R., Issa, EB.others  2018\.  Brain-score: Which artificial neural network for object recognition is most brain-like? Brain-score: Which artificial neural network for object recognition is most brain-like?  BioRxiv407007.
  * Straub . (2019) replica19arxivStraub, J., Whelan, T., Ma, L., Chen, Y., Wijmans, E., Green, S.Newcombe, R.  2019\.  The Replica Dataset: A Digital Replica of Indoor Spaces The Replica dataset: A digital replica of indoor spaces.  arXiv preprint arXiv:1906.05797.
  * Tung . (2019) tung2019learningTung, HYF., Cheng, R. Fragkiadaki, K.  2019\.  Learning spatial common sense with geometry-aware recurrent networks Learning spatial common sense with geometry-aware recurrent networks.  Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Proceedings of the ieee/cvf conference on computer vision and pattern recognition ( 2595–2603).
  * Ungerleider (1982) ungerleider1982twoUngerleider, LG.  1982\.  Two cortical visual systems Two cortical visual systems.  Analysis of visual behavior549–586.
  * Wang . (2015) wang2015probabilisticWang, L., Mruczek, RE., Arcaro, MJ. Kastner, S.  2015\.  Probabilistic maps of visual topography in human cortex Probabilistic maps of visual topography in human cortex.  Cerebral cortex25103911–3931.
  * Weiner Grill-Spector (2013) weiner2013neuralWeiner, KS. Grill-Spector, K.  2013\.  Neural representations of faces and limbs neighbor in human high-level visual cortex: evidence for a new organization principle Neural representations of faces and limbs neighbor in human high-level visual cortex: evidence for a new organization principle.  Psychological research7774–97.
  * Welchman (2016) welchman2016humanWelchman, AE.  2016\.  The human brain in depth: how we see in 3D The human brain in depth: how we see in 3d.  Annual review of vision science2345–376.
  * Wurm Caramazza (2022) wurm2022twoWurm, MF. Caramazza, A.  2022\.  Two ‘what’pathways for action and object recognition Two ‘what’pathways for action and object recognition.  Trends in cognitive sciences262103–116.
  * Yamins . (2014) Yamins2014Yamins, DLK., Hong, H., Cadieu, CF., Solomon, EA., Seibert, D. DiCarlo, JJ.  2014\.  Performance-optimized hierarchical models predict neural responses in higher visual cortex. Performance-optimized hierarchical models predict neural responses in higher visual cortex.  Proc Natl Acad Sci USA111238619–8624.  10.1073/pnas.1403112111
  * Zhuang . (2021) zhuang2021unsupervisedZhuang, C., Yan, S., Nayebi, A., Schrimpf, M., Frank, MC., DiCarlo, JJ. Yamins, DL.  2021\.  Unsupervised neural network models of the ventral visual stream Unsupervised neural network models of the ventral visual stream.  Proceedings of the National Academy of Sciences1183e2014196118.