# Cross-client Label Propagation for Transductive and
Semi-Supervised Federated Learning

Jonathan Scott<EMAIL_ADDRESS>
ISTA (Institute of Science and Technology Austria), Klosterneuburg, Austria
Michelle Yeo<EMAIL_ADDRESS>
ISTA (Institute of Science and Technology Austria), Klosterneuburg, Austria
Christoph H. Lampert<EMAIL_ADDRESS>
ISTA (Institute of Science and Technology Austria), Klosterneuburg, Austria

###### Abstract

We present _Cross-Client Label Propagation (XCLP)_ , a new method for
transductive and semi-supervised federated learning. XCLP estimates a data
graph jointly from the data of multiple clients and computes labels for the
unlabeled data by propagating label information across the graph. To avoid
clients having to share their data with anyone, XCLP employs two
cryptographically secure protocols: _secure Hamming distance computation_ and
_secure summation_. We demonstrate two distinct applications of XCLP within
federated learning. In the first, we use it in a one-shot way to predict
labels for unseen test points. In the second, we use it to repeatedly pseudo-
label unlabeled training data in a federated semi-supervised setting.
Experiments on both real federated and standard benchmark datasets show that
in both applications XCLP achieves higher classification accuracy than
alternative approaches.

##  1 Introduction

Federated Learning (FL) (McMahan et al., 2017) is a machine learning paradigm
in which multiple clients, each owning their own data, cooperate to jointly
solve a learning task. The process is typically coordinated by a central
server. The defining restriction of FL is that client data must remain on
device and cannot be shared with either the server or other clients. In
practice this is usually not due to the server being viewed as a hostile party
but rather to comply with external privacy and legal constraints that require
client data to remain stored on-device. To date, the vast majority of research
within FL has been focused on the supervised setting, in which client data is
fully labeled and the goal is to train a predictive model. In this setting a
well-defined template has emerged: first proposed as _federated averaging_
(McMahan et al., 2017), this consists of alternating between local model
training at the clients and model aggregation at the server.

However, in many real-world settings fully labeled data may not be available.
For instance, in _cross-device_ FL, smartphone users are not likely to be
interested in annotating more than a handful of the photos on their devices
(Song et al., 2022). Similarly, in a _cross-silo_ setting the labeling of
medical imaging data may be both costly and time consuming (Dehaene et al.,
2020). As such, in recent years there has been growing interest in developing
algorithms that can learn from partly labeled or fully unlabeled data in a
federated setting (Kairouz et al., 2021). For such algorithms it can be
beneficial, or even essential, to go beyond the standard federated framework
of model-centric learning and develop techniques that directly leverage client
data interactions. Examples include federated clustering (Dennis et al., 2021)
and dimensionality reduction (Grammenos et al., 2020), where clients compute
statistics based on their data and the server computes with aggregates of
these statistics.

Contribution In this work we propose _Cross-Client Label Propagation (XCLP)_
which follows a data-centric approach. XCLP allows multiple clients, each with
labeled and unlabeled data, to cooperatively compute labels for their
unlabeled data. This is done using a transductive approach, where the goal is
label inference restricted to some predefined set of unlabeled examples. In
particular this approach does not require a model to be trained in order to
infer labels. Specifically, XCLP takes a graph-based approach to directly
assign labels to the unlabeled data. It builds a joint data graph of a group
of clients and propagates the clients’ label information along the edges.
Naively, this approach would require the clients to centrally share their
data. That, however, would violate the constraints of federated learning.

XCLP allows for multiple clients to jointly infer labels from a cross-client
data graph _without_ them having to share their data. To achieve this XCLP
exploits the modular and distributed nature of the problem. It uses locality-
sensitive hashing and secure Hamming distance computation to efficiently
estimate the cross-client data graph. It then distributes the label
propagation computation across clients and aggregates the results using a
customized variant of secure summation. The key benefits of this approach are:

  * •

XCLP enables the data of multiple clients to be leveraged when estimating the
graph and propagating labels. This is beneficial as the prediction quality of
label propagation increases substantially when more data is used.

  * •

XCLP preserves privacy in the sense that it does not require clients to share
their data with anyone else. Instead clients only have to share approximate
data point similarities with the server.

  * •

XCLP is communication efficient as it does not require training a model over
multiple communication rounds but requires only a single round of
communication.

As a technique to transfer label information from labeled to unlabeled points,
XCLP is versatile enough to be used in a variety of contexts. We illustrate
this by providing two applications within federated learning. In the first we
employ XCLP purely for making predictions at inference time. We demonstrate
empirically on a real-world, highly heterogeneous, federated medical image
dataset that XCLP is able to assign high quality labels to unlabeled data.
When all clients are partly labeled we observe XCLP to outperform purely local
label propagation, which illustrates the benefits of leveraging more data.
XCLP also obtains strong results when using fully labeled clients to infer
labels on different, fully unlabeled clients, even when these clients have
very different data distributions. In both these scenarios we find that
running XCLP on features obtained from models trained using
_FederatedAveraging_ gives significantly better accuracy than purely using the
model predictions.

In the second application we tackle the problem of federated semi-supervised
learning. In this scenario clients possess only partly labeled data and the
goal is to train a classifier by leveraging both labeled and unlabeled client
data. In this setting we employ XCLP in the training process by integrating it
into a standard federated learning pipeline. Specifically, during each round
of _FederatedAveraging_ we use XCLP to assign pseudo-labels and weights to the
unlabeled data of the current batch of clients. These are then used to train
with a weighted supervised loss function. Our experiments show that this
pseudo-labelling approach outperforms all existing methods for federated semi-
supervised learning, as well as a range of natural baselines in the standard
federated CIFAR-10 benchmark. Going beyond prior work, we also evaluate on
more challenging datasets, namely CIFAR-100 and Mini-ImageNet, where we also
observe substantial improvements in accuracy.

##  2 Related Work

Federated Learning Federated learning (FL) (McMahan et al., 2017) was
originally proposed for learning on private fully labeled data split across
multiple clients. For a survey on developments in the field see (Kairouz et
al., 2021). A number of recent works propose federated learning in the absence
of fully labeled data. Methods for cluster analysis and dimensionality
reduction have been proposed (Dennis et al., 2021; Grammenos et al., 2020), in
which the server acts on aggregates of the client data, as opposed to client
models. Other works have focused on a model based approach to federated semi-
supervised learning (SSL). Jeong et al. (2021) propose inter-client
consistency and parameter decomposition to separately learn from labeled and
unlabeled data. Long et al. (2020) apply consistency locally through client
based teacher models. Liang et al. (2022) combine local semi-supervised
training with an enhanced aggregation scheme which re-weights client models
based on their distance from the mean model. Zhang et al. (2021b) and Diao et
al. (2022) focus on a setting in which the server has access to labeled data.
In this setting Zhang et al. (2021b) combine local consistency with grouping
of client updates to reduce gradient diversity while Diao et al. (2022)
combine consistency, through strong data augmentation, with pseudo-labeling
unlabeled client data. Our approach to federated SSL is to iteratively apply
XCLP to pseudo-label unlabeled client data. This approach differs from prior
work by making use of data interactions between multiple clients to propagate
label information over a cross client data graph. Related to this idea is the
notion of federated learning on graphs (Zhang et al., 2021a; Xie et al., 2021;
Wang et al., 2020). However, these works are primarily interested in learning
from data that is already a graph. In contrast XCLP estimates a graph based on
similarities between data points, in order to spread label information over
the edges.

Label Propagation Label Propagation (Zhu & Ghahramani, 2002; Zhou et al.,
2004) was originally proposed as a tool for transductive learning with partly
labeled data. Over time it has proven to be a versatile tool for a wide range
of problems. Several works have applied LP to the problem of domain
adaptation. Liu et al. (2019) apply LP over a learned graph for few shot
learning. Cai et al. (2021) develop a framework for domain adaptation by
combining LP with a teacher trained on the source. Khamis & Lampert (2014) use
LP as a prediction-time regularizer for collective classification tasks. In
the context of deep semi-supervised learning Iscen et al. (2019) make use of
LP as a means of obtaining pseudo-labels for unlabeled data which are then
used in supervised training. Several works apply LP to problems with graphical
data. Huang et al. (2021) observe that combining linear or shallow models with
LP can lead to performance that is on par with or better than complex and
computationally expensive GNNs. Wang & Leskovec (2022) apply LP as a
regularizer for graph convolutional neural networks when learning edge weights
and quantify the theoretical connection between them in terms of smoothing.

Input: set of participating clients $P$, client data $(V^{(j)},Y^{(j)})_{j\in
P}$

// data stored on-device at clients

1

2 Setup: clients exchange private and public keys, agree on random seed $s$

3 for  _client $j\in P$ in parallel_ do

$\Pi\in\mathbb{R}^{L\times
d}\quad\text{with}\quad\Pi_{ij}\stackrel{{\scriptstyle{i.i.d}.\hbox{}}}{{\sim}}\mathcal{N}_{\text{seed}=s}(0,1)$

// same $\Pi$ for each client

$B^{(j)}\leftarrow\operatorname{sign}(\Pi\,(V^{(j)})^{\top})$

// LSH projection

4

$H\leftarrow\texttt{SecureHamming}((B^{(j)})_{j\in P})$

// server gets Hamming matrix

$A\leftarrow\cos(\frac{\pi}{L}H)$

// estimate cosine similarity matrix

$B\leftarrow\text{sparsify}(A)$

// keep $k$ largest entries per row, set others to $0$

$W=B+B^{\top}$

// symmetrize

$\mathcal{W}\leftarrow D^{-\frac{1}{2}}WD^{-\frac{1}{2}}\text{ for
}D=\operatorname{diag}(d_{1},\dots,d_{n})\text{ with }d_{i}=\sum_{j}W_{ij}$

// normalize

$S\leftarrow(\text{Id}_{n\times n}-\alpha\mathcal{W})^{-1}$

// influence matrix

5 for  _client $j\in P$ in parallel_ do

$S_{L}^{(j)}\leftarrow\text{labeled-cols}_{j}(S)$

// client gets columns corresponding to labeled data

$\bar{Z}^{(j)}\leftarrow S_{L}^{(j)}Y_{L}^{(j)}$

// compute local contribution to overall label propagation

$Z^{(j)}\leftarrow\texttt{SecureRowSums}\big{(}(\bar{Z}^{(k)})_{k\in
P}\big{)}_{j}$

// client gets its part of aggregated contributions

$\hat{y}^{(j)}\leftarrow\big{(}\operatorname*{arg\,max}_{c=1,\dots,C}Z^{(j)}_{i,c}\big{)}_{i=1,\dots,n^{(j)}}$

// predict labels

$\omega^{(j)}\leftarrow\Big{(}1-\texttt{entropy}\big{(}\frac{(Z^{(j)}_{i,c})_{c=1,\dots,C}}{\sum_{c=1}^{C}Z^{(j)}_{i,c}}\big{)}/\log
C\Big{)}_{i=1,\dots,n^{(j)}}$

// predicted label confidences

6

Output: predicted labels and confidences $(\hat{y}^{(j)},\omega^{(j)})_{j\in
P}$

// available only to respective clients

7

Algorithm 1 Cross-ClientLabelPropagation

##  3 Method

In this section we begin by introducing the problem setting. In Section 3.1 we
present our method XCLP, in Section 3.2 we describe the cryptographic
protocols we make use of and in Section 3.3 we provide an analysis of XCLP.

Let $P$ be a set of client devices for which labels should be propagated. Note
that we place no restrictions on $P$. It could be all clients in a federated
learning scenario, a randomly chosen subset, or a strategically chosen subset,
e.g. based on client similarity, diversity or data set sizes.

Each client $j\in P$ possesses a set of $n^{(j)}$ $d$-dimensional data
vectors, of which $l^{(j)}$ are labeled, i.e. $V^{(j)}=(v^{(j)}_{1},\dots
v^{(j)}_{l^{(j)}},v^{(j)}_{l^{(j)}+1},\dots
v^{(j)}_{n^{(j)}})^{\top}\in\mathbb{R}^{n^{(j)}\times d}$, with partial labels
$\\{y^{(j)}_{1},\dots,y^{(j)}_{l^{(j)}}\\}$ from $C$ classes, which we encode
in zero-or-one-hot matrix form: $Y^{(j)}\in\\{0,1\\}^{n^{(j)}\times C}$ with
$Y^{(j)}_{ic}=\mathbbm{1}\\{y^{(j)}_{i}\\!\\!=c\\}$ for $1\leq i\leq l^{(j)}$
and $Y^{(j)}_{ic}=0$ otherwise. Note that this setup includes the possibility
for a client to have only labeled data, $n^{(j)}=l^{(j)}$ or only unlabeled
data, $l^{(j)}=0$. We denote the total amount of data by $n\coloneqq\sum_{j\in
P}n^{(j)}$. Our goal is to assign labels to the unlabeled data points, i.e.,
_transductive learning_ (Vapnik, 1982). The process is coordinated by a
central server, which we assume to be _non-hostile_. That means, we trust the
server to operate on non-revealing aggregate data and to return correct
results of computations.111In particular we exclude _malicious_ servers in the
cryptographic sense that would, e.g., be allowed to employ attacks such as
model poisoning or generating fake clients in order to break the protocol. At
the same time, we treat clients and server as _curious_ , i.e., we want to
prevent that at any point in the process any client’s data is revealed to the
server, or to any other client.

Our main contribution in this work is, _Cross-Client Label Propagation (XCLP)_
, an algorithm for assigning labels to the unlabeled data points. XCLP works
by propagating label information across a neighborhood graph that is built
jointly from the data of all participating clients without revealing their
data. Before explaining the individual steps in detail, we provide a high
level overview of the method.

XCLP consists of three phases: 1) the clients jointly compute similarity
values between all of their data points and transfer them to the server, 2)
the server uses these similarities to construct a neighborhood graph and
infers an influence matrix from this, which it distributes back to the
clients, 3) the clients locally compute how their data influences others,
aggregate this information, and infer labels for their data.

The key challenge is how to do these steps without the clients having to share
their data and labels with each other or with the server. XCLP manages this by
formulating the problem in a way that allows us to use only light-weight
cryptographic protocols for the steps of computing similarities and
aggregating label information.

###  3.1 Cross-Client Label Propagation (XCLP)

Algorithm 1 shows pseudocode for XCLP. To reflect the distributed nature of
XCLP we mark the execution type of each step: _client steps (CS)_ are steps
that clients do locally using only their own data, _server steps (SS_) are
steps that the server executes on aggregated data, _cross steps (XS)_ are
steps that require cross-client or client-server interactions.

As a setup step (line 1) the clients use a secure key exchange procedure to
agree on a shared random seed that remains unknown to the server. This is a
common step in FL when cryptographic methods, such as _secure model
aggregation_ , are employed, see Bonawitz et al. (2017).

Phase 1. The clients use the agreed-on random seed to generate a common matrix
$\Pi\in\mathbb{R}^{L\times d}$ with unit Gaussian random entries (line 1).
Each client, $j$, then multiplies its data matrix $V^{(j)}$ by $\Pi$ and takes
the component-wise sign of the result, thereby obtaining a matrix of $n^{(j)}$
$L$-dimensional binary vectors, $B^{(j)}$ (line 1). In combination, both steps
constitute a local _locality-sensitive hashing (LSH)_ (Indyk & Motwani, 1998)
step for each client. A crucial property of this encoding is that the (cosine)
similarity between any two data vectors, $v,v^{\prime}$, can be recovered from
their binary encodings $b,b^{\prime}$:
$\operatorname{sim}(v,v^{\prime}):=\frac{\langle
v,v^{\prime}\rangle}{\|v\|\|v^{\prime}\|}\approx\cos(\pi h(b,b^{\prime})/L),$
where $h(b,b^{\prime})=\sum_{l=1}^{L}b_{l}\oplus b^{\prime}_{l}$ is the
Hamming distance (number of bits that differ) between binary vectors and
$\oplus$ is the XOR-operation. Since all clients use identical random
projections, this identity holds even for data points located on different
clients. See Section B.2 for details on LSH.

In line 1 the necessary Hamming distance computations take place using a
cryptographic subroutine that we detail in Section 3.2. Note that
cryptographic protocols operate most efficiently on binary vectors, and
Hamming distance is particularly simple to compute. In fact, this is the
reason why we transform the data using LSH in the first place. Ultimately,
from this step the server obtains the matrix of all pairwise Hamming
distances, $H\in\mathbb{Z}^{n\times n}$, but no other information about the
data.

Phase 2. Having obtained $H$ the server executes a number of steps by itself.
First, it converts $H$ to a (cosine) similarity matrix
$A\in\mathbb{R}^{n\times n}$ (line 1). It sparsifies each row of $A$ by
keeping the $k$ largest values and setting the others to $0$ (line 1). From
the resulting matrix, $B$, it constructs a weighted adjacency matrix of the
data graph, $\mathcal{W}$ by symmetrization (line 1) and normalization (line
1).

If not for the aspect of data privacy, we could now achieve our goal of
propagating label information along the graph edges from labeled to unlabeled
points in the following way: form the concatenation of all partial label
matrices, $Y=(Y^{(j)})_{j\in P}\in\\{0,1\\}^{n\times C}$, and compute
$Z=SY\in\mathbb{R}^{n\times C}$, where
$S=(\operatorname{Id}-\alpha\mathcal{W})^{-1}$ is the _influence matrix_ , and
$\alpha\in(0,1)$ is a hyperparameter. See Section B.1 for an explanation how
this step corresponds to the propagation of labels over the graph.

XCLP is able to perform the computation of the _unnormalized class scores_ ,
$Z$, without having to form $Y$, thereby preserving the privacy of the labels.
Instead, it computes only the influence matrix, $S$, centrally on the server
(line 1), while the multiplication with the labels will be performed in a
distributed way across the clients.

Phase 3. Observe that the computation of $Z$ can also be written as
$Z=\sum_{j\in P}S^{(j)}Y^{(j)}$, where $S^{(j)}\in\mathbb{R}^{n\times
n^{(j)}}$ is the sub-matrix of $S$ consisting of only the columns that
correspond to the data of client $j$. We can refine this further, note that
all rows of $Y^{(j)}$ that correspond to the unlabeled data of client $j$ are
identically $0$ by construction and hence do not contribute to the
multiplication. Therefore, writing $Y_{L}^{(j)}\in\mathbb{R}^{l^{(j)}\times
C}$ for the rows of $Y^{(j)}$ that correspond to labeled points and
$S_{L}^{(j)}\in\mathbb{R}^{n\times l^{(j)}}$ for the corresponding columns of
$S^{(j)}$, it also holds that $Z=\sum_{j\in P}S_{L}^{(j)}Y_{L}^{(j)}$.

Using this observation, Algorithm 1 continues by each client $j$ receiving
$S_{L}^{(j)}$ from the server (line 1). It then locally computes
$\bar{Z}^{(j)}=S_{L}^{(j)}Y_{L}^{(j)}\in\mathbb{R}^{n\times C}$ (line 1),
which reflects the influence of $j$’s labels on all other data points.

By now, the clients have essentially computed $Z$, but the result is
additively split between them: $Z=\sum_{j\in P}\bar{Z}^{(j)}$. To compute the
sum while preserving data privacy, XCLP uses a secure summation routine (line
1), as commonly used in FL for model averaging (Bonawitz et al., 2017).
However, to increase its efficiency we tailor it to the task, see Section 3.2
for details. As a result, each client $j$ receives only those rows of $Z$ that
correspond to its own data, $Z^{(j)}\in\mathbb{R}^{n^{(j)}\times C}$ (line 1).
From these, it computes labels and confidence values for its data (lines 1-1).

###  3.2 Cryptographic Subroutines

In this section we describe the proposed cryptographic protocols for _secure
summation_ and _secure Hamming distance computation_ that allow clients to run
XCLP without having to share their data.

SecureRowSums We propose a variation of the _secure summation_ that is
commonly used in FL (Bonawitz et al., 2017). For simplicity we describe the
case where all values belong to $\mathbb{Z}_{l}$ for some $l\in\mathbb{N}$,
though extensions to fixed-point or floating-point arithmetic also exist
(Catrina & Saxena, 2010; Aliasgari et al., 2013).

Given a set of clients $P$, each with some matrix
$Z^{(j)}\in\mathbb{Z}_{l}^{n\times c}$, ordinary SecureSum computes
$\sum_{j\in P}Z^{(j)}$ at the server in such a way that the server learns only
the sum but nothing about the $Z^{(j)}$ matrices. The main idea is as follows:
using agreed upon random seeds clients jointly create random matrices
$M^{(j)}\in\mathbb{Z}_{l}^{n\times c}$ with the property that $\sum_{j\in
P}M^{(j)}=0$. Each client $j$ then obfuscates its data by computing
$\tilde{Z}^{(j)}\coloneqq Z^{(j)}+M^{(j)}$ and sends this to the server. From
the perspective of the server each $\tilde{Z}^{(j)}$ is indistinguishable from
uniformly random noise. However, when all parts are summed, the obfuscations
cancel out and what remains is the desired answer: $\sum_{j\in
P}\tilde{Z}^{(j)}=\sum_{j\in P}Z^{(j)}$. For technical details see Bonawitz et
al. (2017).

For XCLP, we propose a modification of the above construction. Suppose we have
a partition of the rows, $(R_{j})_{j\in P}$, where each $R_{j}\subset[n]$.
Each client $j$ knows its own $R_{j}$ and the server knows all $R_{j}$.
SecureRowSums’s task is to compute $Z\coloneqq\sum_{j\in P}Z^{(j)}$ in a
distributed form in which each client $j\in P$ learns only the rows of $Z$
indexed by $R_{j}$, denoted $Z[R_{j}]$, and the server learns nothing.

For this, let $M^{(j)}$ and $\tilde{Z}^{(j)}$ be defined as above. In
addition, let $\hat{Z}^{(j)}$ be equal to the obfuscated $\tilde{Z}^{(j)}$,
except that the rows indexed by $R_{j}$ are completely set to 0. Each client
now instead sends $\hat{Z}^{(j)}$ to the server, which computes
$\hat{Z}\coloneqq\sum_{j\in P}\hat{Z}^{(j)}$. The server then redistributes
$\hat{Z}$ among the clients, i.e. each client $j$ receives $\hat{Z}[R_{j}]$.
Note that $\hat{Z}[R_{j}]=\sum_{k\in
P\setminus\\{j\\}}\tilde{Z}^{(k)}[R_{j}]=Z[R_{j}]-\tilde{Z}^{(j)}[R_{j}]$.
Consequently, each client obtains the part of $Z$ corresponding to its own
data by computing $Z[R_{j}]=\hat{Z}[R_{j}]+\tilde{Z}^{(j)}[R_{j}]$. By
construction the shared quantities leak nothing to the server. Specifically
$\hat{Z}^{(j)}$ is random noise with rows $R_{j}$ set to 0 and $\hat{Z}$ is
random noise since each block $\hat{Z}[R_{j}]$ remains obfuscated due to
client $j$ not sending $M^{(j)}[R_{j}]$.

SecureHamming Several cryptographic protocols for computing the Hamming
distances between binary vectors exist. Here we propose two variants that are
tailored to the setting of XCLP: one is based on the SHADE protocol (Bringer
et al., 2013), which is easy to implement as it only requires only an
_oblivious transfer (OT)_ (Naor & Pinkas, 2001) routine as cryptographic
primitive. The other is based on _partially homomorphic encryption (PHE)_ and
comes with lower communication cost.

_OT-based secure Hamming distance:_ Let $b=(b_{1},\dots,b_{L})$ and
$b^{\prime}=(b^{\prime}_{1},\dots,b^{\prime}_{L})$ be the bit vectors, for
which the Hamming distance should be computed, where $b$ is stored on a client
$j$ and $b^{\prime}$ on a client $k$.

1) client $j$ creates $L$ random numbers $r_{1},\dots,r_{L}$ uniformly in the
range $[0,L-1]$. For each $l=1,\dots,L$, it then offers two values to be
transferred to client $k$: $z^{0}_{l}=r_{l}+b_{l}$ or
$z^{1}_{l}=r_{l}+\bar{b}_{l}$, for $\bar{b}_{l}=1-b_{l}$ (here and in the
following all calculations are performed in $\mathbb{Z}_{L}$, i.e. in the
integers _modulo_ $L$).

2) Client $k$ initiates an OT operation with input $b^{\prime}_{l}$ and result
$t_{l}$. That means, if $b^{\prime}_{l}=0$ it will receive $t_{l}=z^{0}_{l}$
and if $b^{\prime}_{l}=1$ it will receive $t_{l}=z^{1}_{l}$, but client $i$
will obtain no information which of the two cases occurred. Note that in both
cases, it holds that $t_{l}=r_{l}+b_{l}\oplus b^{\prime}_{l}$. However, client
$k$ gains no information about the value of $b_{l}$ from this, because of the
uniformly random shift $r_{l}$ that is unknown to it.

3) Clients $j$ and $k$ now compute $R=\sum_{l=1}^{L}r_{l}$ and
$T=\sum_{l=1}^{L}t_{l}$, respectively, and send these values to the server.

4) From $R$ and $T$, the server can infer the Hamming distance between $b$ and
$b^{\prime}$ as $T-R=\sum_{l=1}^{L}b_{l}\oplus
b^{\prime}_{l}=h(b,b^{\prime})$.

Performing these steps for all pairs of data points, the server obtains the
Hamming matrix, $H\in{\mathbb{N}}^{n\times n}$, but no other information about
the data. The clients obtain no information about each others’ data at all
during the computation.

_PHE-based secure Hamming distance:_ Homomorphic encryption is a framework
that allows computing functions on encrypted arguments (Acar et al., 2018).
The outcome is an encryption of the value that would have been the result of
evaluating the target function on the plaintext arguments, but the
computational devices gain no information about the actual plaintext. _Fully
homomorphic encryption(FHE)_ , which allows arbitrary functions to be computed
this way, is not efficient enough for practical usage so far (Jiang & Ju,
2022). However, efficient implementation exist for the setting where
cyphertexts only have to be added or subtracted, for example _Paillier_ ’s
(Paillier, 1999). We exploit this paradigm of _partially homomorphic
encryption (PHE)_ to compute the Hamming distances of a binary vector from
clients $j$ with all binary vectors from a client $k$ in the following way:

1) Client $j$ encrypts its own data vector $b^{(j)}\in\\{0,1\\}^{L}$, using
its own public key and transfers the resulting vector
$\boxed{y}:=\text{enc}(b^{(j)})$ (boxes indicate encrypted quantities) to
client $k$. Because the data is encrypted, client $k$ can extract no
information about client $j$’s data from this.

2) For any of its own data vectors $b^{(k)}\in\\{0,1\\}^{L}$, client $k$
creates a uniformly random value $r\in[0,L-1]$. It then computes the following
function in a homomorphic way with encrypted input $y=\boxed{y}$ and plaintext
input $x=b^{(k)}$:

$f(y;x)=r+\sum_{l:x_{l}=1}y_{l}-\sum_{l:x_{l}=0}y_{l}$

Because of the identity
$h(x,y)=\sum_{l}[x_{l}y_{l}+\bar{x}_{l}\bar{y}_{l}]=\sum_{l:x_{l}=1}y_{l}+\sum_{l:x_{l}=0}\bar{y}_{l}=\sum_{l:x_{l}=1}y_{l}-\sum_{l:x_{l}=0}y_{l}+n-\sum_{l}x_{l}$,
the result, $\boxed{T}=f(\boxed{y};x)$, is the value
$T=h(b^{(j)},b^{(k)})+r-n+\sum_{l}b_{l}$ in encrypted form.

4) Client $j$ send the value $R=r-n+\sum_{l}b_{l}$ to the server, and the
value $\boxed{T}$ to client $j$. Client $j$ decrypts $\boxed{T}$ using its own
secret key and sends the resulting value $T$ to the server. It gains no
information about client $k$’s data or the Hamming distance, because the added
randomness gives $T$ a uniformly random distribution.

5) The server recovers $H(b^{(j)},b^{(k)})=T-R$ without gaining any other
information about the clients’ data.

Note that for computing single Hamming distances, this protocol has no
advantage over the OT-based variant. However, for computing all pairwise
Hamming distances between the data of two clients, the PHE-based protocol
saves a factor $n^{(k)}$ in communication cost, because $\boxed{y}$ has to be
transferred only once and can then be used repeatedly by client $k$ to compute
the distances to all of its vectors.

###  3.3 Analysis

In this section, we analyze the _efficacy_ , _privacy_ , _efficiency_ and
_robustness_ of Alg. 1.

Efficacy Alg. 1 performs label propagation along the data graph, as the
classical LP algorithm (Zhu, 2005) does when data is centralized. The
similarity measure used is cosine similarity estimated via the Hamming
distance of the LSH binary vectors. How close this is to the actual cosine
similarity is determined by $L$, the LSH vector length. In practice, we
observe no difference in behavior between them already for reasonably small
values, e.g. $L=4096$.

Privacy  The main insight is that Alg. 1 adheres to the federated learning
principle that clients do not have to share their data or labels with any
other party. This is ensured by the fact that all _cross-steps_ are computed
using cryptographically secure methods. There are two potential places where
clients share some information relating to their data. The first is the matrix
of Hamming distances $H$ that is sent to the server, and from which the server
can approximately recover the matrix of cosine similarities $W$. While
certainly influenced by the client data, we consider $W$ (and therefore $H$) a
rather benign object for a non-hostile server to have access to because cosine
similarity depends only on angles, hence any rescaling and rotation of the
client input vectors would result in the same $W$ matrix. A second source of
information sharing is during phase $3$ where each client receives the columns
of $S$ that correspond to their data. Such columns reflect how their labeled
data can influence all other data points according to the data graph as
estimated from the participating clients’ vectors. However, we stress that
this influence is unnormalized and hence the influence relative to other
clients cannot be known.

Communication Efficiency XCLP incurs communication costs at two steps of Alg.
1. With the OT-based protocol for computing the $n^{(j)}\times n^{(k)}$
Hamming matrix between two clients $j$ and $k$, client $j$ sends
$n^{(j)}n^{(k)}L$ integer values in $\mathbb{Z}_{L}$ to client $k$. With the
enhanced PHE-based protocol, this amount is reduced to sending $n^{(j)}L$
encrypted values from $j$ to $k$ and $n^{(j)}n^{(k)}$ in the opposite
direction. Each of the two clients sends $n^{(j)}n^{(k)}$ integer values in
$\mathbb{Z}_{L}$ to the server. To propagate the labels via the distributed
matrix multiplication, each client $j$ first receives from the server a matrix
of size $n\times l^{(j)}$. It transmits a matrix of size $n\times C$ to the
server, and receives a matrix of size $n^{(j)}\times C$ back from it. In
particular, XCLP requires only a constant number of communication steps, which
is in contrast to other methods that train iteratively.

Robustness In _cross-device_ FL clients may be unreliable and prone to
disconnecting spontaneously. Therefore, it is important that FL algorithms can
still execute even in the event of intermediate client dropouts. This is
indeed the case for Alg. 1: a client dropping out before the SecureHamming
step (line 1), is equivalent to it not having been in $P$ in the first place.
Since the Hamming computation is executed pairwise, a client dropping out
during this step has no effect on the computation of other clients. The result
will be missing entries in the matrix, $H$, which the server can remove,
thereby leading to the same outcome as if the client had dropped out earlier.
If clients drop out after $H$ has been computed, but before the SecureRowSums
step (line 1), they will have contributed to the estimate of the data graph,
but they will not contribute label information to the propagation step. This
has the same effect as if the client only had unlabeled data. If clients drop
out within SecureRowSums, after the obfuscation matrices have been agreed on
but before the server has computed $\hat{Z}$, then the secure summation could
not be completed. To recover, the server can simply restart the SecureRowSums
step without the dropped client. Any later dropout will only result in that
client not receiving labels for its data, but it will not affect the results
for the other clients.

Table 1: XCLP for prediction (Fed-ISIC2019 dataset): Classification accuracy [in %] with two different preprocessing functions (pretrained and finetuned) and training sets of different size (average and standard deviation across three runs).  | pretrained | finetuned
---|---|---
training set size | _per-client LP_ | _XCLP_ | _FedAvg_ | _per-client LP_ | _XCLP_
$n=954$ | $30.70\pm 1.25$ | $\bf 34.00\pm 1.12$ | $43.78\pm 0.88$ | $45.35\pm 1.25$ | $\bf 47.48\pm 1.12$
$n=1882$ | $31.40\pm 1.18$ | $\bf 34.61\pm 0.93$ | $46.83\pm 0.75$ | $48.10\pm 1.18$ | $\bf 52.34\pm 0.93$
$n=3744$ | $37.41\pm 0.20$ | $\bf 38.49\pm 0.88$ | $52.87\pm 0.14$ | $56.98\pm 0.20$ | $\bf 59.49\pm 0.88$
$n=18597$ | $\bf 55.10\pm 0.51$ | $53.38\pm 0.67$ | $63.78\pm 0.20$ | $73.30\pm 0.51$ | $\bf 74.22\pm 0.67$
Table 2: XCLP for prediction (Fed-ISIC2019 dataset): Classification accuracy [in %] for leave-one-client-out experiments (average and standard deviation across three runs). left-out client | FedAvg | XCLP
---|---|---
Client 1 | $35.15\pm 0.96$ | $\bf 38.89\pm 1.34$
Client 2 | $\bf 68.75\pm 0.72$ | $67.05\pm 0.54$
Client 3 | $51.94\pm 2.52$ | $\bf 62.02\pm 1.13$
Client 4 | $42.72\pm 0.79$ | $\bf 54.84\pm 0.78$
Client 5 | $41.53\pm 1.60$ | $\bf 52.28\pm 0.58$
Client 6 | $46.92\pm 3.69$ | $\bf 61.27\pm 3.19$
Table 3: XCLP for prediction (Fed-ISIC2019 dataset): Classification accuracy [in %] when different fractions, $\alpha$, of training data are labeled. FedAvg and _XCLP (labeled)_ use only the labeled part of the training set, _XCLP (labeled+unlabeled)_ uses also the unlabeled part. | _FedAvg_ | _XCLP (labeled)_ | _XCLP (labeled+unlabeled)_
---|---|---|---
$\alpha=0.05$ | $43.78\pm 0.88$ | $47.48\pm 1.12$ | $\bf 49.50\pm 1.42$
$\alpha=0.1$ | $46.83\pm 0.75$ | $52.34\pm 0.93$ | $\bf 53.78\pm 0.90$
$\alpha=0.2$ | $52.87\pm 0.14$ | $59.49\pm 0.88$ | $\bf 61.09\pm 0.66$
$\alpha=1.0$ | $63.78\pm 0.20$ | $\bf 74.22\pm 0.67$ | $\bf 74.22\pm 0.67$

##  4 Experiments

In the following section we report experimental results for XCLP. We present
two applications in the context of federated learning. In Section 4.1 we
illustrate how XCLP can be used in a one-shot way to infer labels at
prediction time. In Section 4.2 we show how XCLP can be used for federated
semi-supervised learning by integrating it into a federated averaging training
loop. As our emphasis here is on accuracy, not real-world efficiency, we use a
simulated setting of federated learning, rather than physically distributing
the clients across multiple devices. Therefore, we also use plaintext
placeholders for the cryptographic steps that have identical output. Source
code for our experiments will be made publicly available.

###  4.1 XCLP for prediction

The most straightforward application of XCLP is as a method to predict labels
for new data at inference time. For this setting suppose a set of clients,
$P$, possess training data $X^{(j)}\in\mathcal{X}^{n^{(j)}}$ from some input
space $\mathcal{X}$, and a (potentially partial) label matrix
$Y^{(j)}\in\\{0,1\\}^{n^{(j)}\times C}$. The goal is to infer labels for new
batches of data, $X^{(j)}_{\text{new}}$. Note that the above setting is
general enough to encompass a number of settings, including clients with fully
labeled or fully unlabeled training data. Also included is the possibility
that a client $j$ has no training data to contribute, $X^{(j)}=\emptyset$, but
has a batch of new data to be labeled, $X^{(j)}_{\text{new}}\neq\emptyset$.

By $h:\mathcal{X}\rightarrow\mathbb{R}^{d}$ we denote a preprocessing
function, such as a feature extractor. Each client applies $h$ to all their
data points, train and new, to obtain their input vectors to the XCLP routine,
$V^{(j)}\coloneqq h\big{(}X^{(j)}\cup X^{(j)}_{\text{new}}\big{)}$. Running
Alg. 1 on $(V^{(j)},Y^{(j)})_{j\in P}$, each client obtains $\hat{Y}^{(j)}$,
which are label assignments for all of their data points, in particular
including $X^{(j)}_{\text{new}}$ as desired.

Experimental Setup We use the Fed-ISIC2019 dataset (Ogier du Terrail et al.,
2022), a real-world benchmark for federated classification of medical images.
It consists of a total of 23247 images across 6 clients. The dataset is highly
heterogeneous in terms of the amount of data per client, the classes present
at each client as well as visual content of the images. As baseline
classifier, we follow (Ogier du Terrail et al., 2022) and use an EfficientNet
(Tan & Le, 2019), pretrained on ImageNet, which we finetune using federated
averaging. As preprocessing functions, $h$, we use the feature extraction
layers of the network either at the point of initialization (pretrained) or
after the finetuning. Section A.1 gives full details of the experimental
setup.

Results Table 1 reports results for the setting in which all clients
contribute fully-labeled training data and have new data that should be
classified. The left columns (“pretrained") illustrate the one-shot setting:
no network training is required, only features are extracted once using a
pretrained network, and XCLP is run once to infer labels. XCLP performs better
than per-client label propagation here, except for the largest dataset size,
indicating that in the limited data regime, it is indeed beneficial to build
the data graph jointly from all data rather than separately on each clients.
The other three columns (“finetuned") illustrate that with a better –task-
adapted– feature representation, XCLP still outperforms per-client LP, and
also achieves better accuracy than predicting labels using only the network.

Table 2 reports results for a more challenging setting. We adopt a leave-one-
client-out setup in which one client does not contribute labeled training but
instead its data is meant to be classified. Given the heterogeneity of the
clients, this means the classifiers have to overcome a substantial
distribution shift. XCLP achieves better results than a network trained by
federated averaging in all but one case, where in several cases the advantage
is quite substantial. Note that per-client LP is not applicable here, as the
new data is all located on a client that does not have labeled training data.

Finally, we also conduct on ablation study on the effect of unlabeled training
data on XCLP, that is when $Y^{(j)}$ is a (strictly) partial label matrix. In
this case the unlabeled training data does not contribute label information
towards inference on $X^{(j)}_{\text{new}}$, but does contribute to a more
densely sampled graph. Table 3 shows the results: the _FedAvg_ column is
identical to the one in Table 1, because the federated averaging training does
not benefit from the additionally available unlabeled training data.
Similarly, the result for _XCLP_ with only labeled data are the same as for
XCLP in Table 1. However, allowing XCLP to exploit the additional unlabeled
data, however, indeed improves the accuracy further. This results once again
shows the benefits of exploiting unlabeled data, especially when the amount of
label data is small.

Input: partially labeled training data $(X^{(j)},Y^{(j)})_{j=1}^{m}$

1 $\theta=(\phi,\psi)\leftarrow\texttt{InitializeModelParameters}$

2 for  _round $t\in[1,\dots T]$_ do

3 $P\leftarrow\text{server randomly selects }\tau m\text{ clients}$

4 Server broadcasts $\theta$ to each client in $P$

5 for  _client $j\in P$ in parallel_ do

6 $V^{(j)}\leftarrow f_{\phi}(X^{(j)})$

7 $\hat{y}^{(j)},\omega^{(j)}\leftarrow\texttt{XCLP}(V^{(j)},Y^{(j)},P,\text{
Server})$

8
$\theta^{(j)}\leftarrow\texttt{ClientUpdate}(X^{(j)},\hat{y}^{(j)},\omega^{(j)};\theta)$

9 Client $j$ sends $\theta^{(j)}$ to the server

10

11 $\theta\leftarrow\texttt{ServerUpdate}\big{(}(\theta^{(j)})_{j\in
P})\big{)}$

Output: model parameters $\theta$

Algorithm 2 FedAvg+XCLP

###  4.2 XCLP for federated semi-supervised learning

We now describe how XCLP can be applied iteratively during a training loop in
the context of federated semi-supervised learning. _FedAvg+XCLP_ , shown in
pseudocode in Algorithm 2, follows a general FL template of alternating local
and global model updates. As such, it is compatible with most existing FL
optimization schemes, such as _FedAvg_ (McMahan et al., 2017), _FedProx_ (Li
et al., 2020), or _SCAFFOLD_ (Karimireddy et al., 2020). The choice of scheme
determines the exact form of the ClientUpdate and ServerUpdate routines.

The first step (line 2) is to initialize the model parameters,
$\theta=(\phi,\psi)$, where $f_{\phi}:\mathcal{X}\to\mathbb{R}^{d}$ is the
feature extraction part of a neural network and
$f_{\psi}:\mathbb{R}^{d}\to\mathbb{R}^{C}$ is the classifier head. The
initialization could be random, using weights of a pretrained network, by an
unsupervised technique, such as contrastive learning, or by a supervised step,
such as federated training on only the labeled examples.

We then iterate the main training loop over $T$ rounds. To start each round
the server samples some fraction $\tau$ of the $m$ total clients. These
clients receive the current model parameters from the server (line 2) and
embed their labeled and unlabeled data with the feature extractor, $f_{\phi}$
(line 2). Clients and server then collaboratively run XCLP on these feature
vectors (line 2). As output of this step each client updates the pseudo-labels
and confidence values for their unlabeled data, which they then use for local
supervised training (line 2). Lastly, clients send the updated local models to
the server (line 2) which aggregates them (line 2).

The motivation for this approach comes from the insight gained in Section 4.1,
that XCLP assigns high quality labels when run on features obtained from a
trained network. Crucially, pseudo-labels assigned by XCLP are always
recomputed when a client is sampled. Thus as the network features improve so
too does the quality of the pseudo-labeling.

Experimental Setup We evaluate the accuracy of FedAvg+XCLP against other
methods for federated SSL as well as report on ablation studies. We adopt a
standard federated averaging scheme, in which ClientUpdate consists of running
$5$ epochs of SGD with confidence-weighted cross-entropy loss on the local
device and ServerUpdate simply averages the local client models.

We use three standard datasets: CIFAR-10 (Krizhevsky, 2009), which has 10
classes and is used in several previous federated SSL works (Jeong et al.,
2021; Long et al., 2020; Albaseer et al., 2020), as well as the more difficult
CIFAR-100 (Krizhevsky, 2009) and Mini-ImageNet (Vinyals et al., 2016) which
have 100 classes. To the best of our knowledge ours is the first work in this
federated SSL setting to evaluate on these more challenging datasets. The
datasets are split in different ways (different number of clients, different
amounts of labeled data, i.i.d. vs non-i.i.d.) to simulate a diverse range of
federated settings.

Table 4: XCLP for federated SSL: classification accuracy [in %] on federated
CIFAR-10. $m$ is the number of clients, $m_{L}$ the number of clients with
labeled data, $n_{L}$ is the total number of labels across all clients. i.i.d.
and non-i.i.d. refer to how the data is split among the clients. For details,
see the main text and Section A.2.  CIFAR-10, i.i.d. ($m=100$)
---
| $m_{L}=100$ | $m_{L}=50$
Method | $n_{L}=1000$ | $n_{L}=5000$ | $n_{L}=1000$ | $n_{L}=5000$
FedAvg (labeled only) | $55.46\pm 0.43$ | $76.13\pm 0.46$ | $56.97\pm 0.59$ | $80.36\pm 0.07$
FedAvg+perclientLP | $61.75\pm 2.22$ | $85.11\pm 0.73$ | $65.29\pm 2.50$ | $84.41\pm 0.25$
FedAvg+network | $60.12\pm 0.15$ | $79.45\pm 0.31$ | $59.14\pm 0.35$ | $81.04\pm 0.20$
FedMatch | $50.93\pm 0.56$ | $72.22\pm 0.14$ | $57.10\pm 0.46$ | $77.80\pm 0.32$
FedSiam | $67.02\pm 0.98$ | $82.06\pm 0.56$ | $62.98\pm 1.61$ | $78.45\pm 0.34$
FedSem+ | $59.98\pm 0.49$ | $79.49\pm 0.15$ | $59.67\pm 0.47$ | $80.94\pm 0.25$
FedAvg+XCLP (ours) | $\bf 70.91\pm 0.71$ | $\bf 86.65\pm 0.16$ | $\bf 70.81\pm 1.65$ | $\bf 86.29\pm 0.34$
CIFAR-10, non-i.i.d. ($m=100$)
| $m_{L}=100$ | $m_{L}=50$
Method | $n_{L}=1000$ | $n_{L}=5000$ | $n_{L}=1000$ | $n_{L}=5000$
FedAvg (labeled only) | $50.94\pm 0.14$ | $75.34\pm 1.38$ | $53.26\pm 0.69$ | $79.65\pm 0.12$
FedAvg+perclientLP | $50.94\pm 0.14$ | $76.61\pm 1.50$ | $53.26\pm 0.69$ | $79.65\pm 0.12$
FedAvg+network | $60.60\pm 0.60$ | $80.07\pm 0.53$ | $59.82\pm 1.05$ | $81.14\pm 0.23$
FedMatch | $50.71\pm 1.57$ | $71.99\pm 0.70$ | $48.24\pm 0.86$ | $66.37\pm 0.41$
FedSiam | $67.85\pm 0.26$ | $82.23\pm 0.46$ | $62.29\pm 1.84$ | $78.84\pm 0.72$
FedSem+ | $60.93\pm 0.97$ | $79.70\pm 0.78$ | $59.74\pm 0.74$ | $81.30\pm 0.09$
FedAvg+XCLP (ours) | $\bf 73.76\pm 0.71$ | $\bf 85.53\pm 0.56$ | $\bf 70.01\pm 1.29$ | $\bf 85.42\pm 0.43$
Table 5: XCLP for federated SSL: classification accuracy [in %] on federated CIFAR-100 and Mini-ImageNet. $m$ is the number of clients, $m_{L}$ the number of clients with labeled data, $n_{L}$ is the total number of labels across all clients. | CIFAR-100, i.i.d. | Mini-ImageNet, i.i.d.
---|---|---
| $m=m_{L}=50$ | $m=m_{L}=100$ | $m=m_{L}=50$ | $m=m_{L}=100$
Method | $n_{L}=5000$ | $n_{L}=10000$ | $n_{L}=5000$ | $n_{L}=10000$
FedAvg (labeled only) | $43.80\pm 0.19$ | $53.91\pm 0.25$ | $23.39\pm 0.52$ | $31.72\pm 0.54$
FedAvg+network | $43.80\pm 0.19$ | $54.19\pm 0.21$ | $23.98\pm 0.36$ | $31.86\pm 0.57$
FedAvg+perclientLP | $43.82\pm 0.59$ | $54.38\pm 0.36$ | $25.53\pm 0.22$ | $33.09\pm 0.62$
FedAvg+XCLP (ours) | $\bf 50.19\pm 0.60$ | $\bf 57.00\pm 0.08$ | $\bf 26.93\pm 0.41$ | $\bf 35.78\pm 0.56$

We compare FedAvg+XCLP to a broad range of other methods. To enable a fair
comparison of results, all methods use the same network architecture, and
hyper-parameters are chosen individually to maximize each method’s
performance. From the existing federated SSL literature, we report results for
_FedMatch_ (Jeong et al., 2021), _FedSiam_ (Long et al., 2020) and _FedSem+_ ,
which follows (Albaseer et al., 2020) but additionally uses confidence-based
sample weights, as we found these to consistently improve its accuracy.
Additional baselines are two methods that follow the same structure as
Algorithm 2 but use alternative ways to obtain pseudo-labels: from per-client
label propagation (FedAvg+perclientLP) or from the network’s classifier
predictions (FedAvg+network). Finally, we also report results for training in
a supervised manner on only the available labeled examples, _FedAvg (labeled
only)_. Note that we do not include comparisons to Zhang et al. (2021b) and
Diao et al. (2022) as these methods address a different federated SSL scenario
in which the server has access to labeled data while the clients have no
labels.

Results We report the results of our experiments in Tables 4 and 5 as the
average accuracy and standard deviation over three random splits of the data
for each setting. Table 4 provides a comparison of XCLP to other approaches
and baselines in the standard setting of CIFAR-10 with 100 clients, which has
been used in prior work. In each case, we report results when 1,000 or 5,000
of the data points are labeled. Either all or half of the clients have labels,
with classes distributed either i.i.d. or non-i.i.d. across clients. Table 5
reports on the harder situation with many more classes, which prior work has
not attempted. Across the board, XCLP achieves the best results among all
methods. The effect is strongest in settings where clients have only a limited
amount of labeled data. Of the other methods, none has a consistent advantage
over the others.

##  5 Conclusions

In this work we introduced XCLP, a method for transductively predicting labels
for unlabeled data points in a federated setting, where the data is
distributed across multiple clients. It makes use of cryptographic routines to
preserve data privacy when estimating a joint neighborhood graph over the data
and propagates label information across this graph by distributing the
computation among the clients.

We presented two applications of XCLP, inferring labels for new (test) data,
and training on partly labeled data in a federated semi-supervised setting. In
our experiments XCLP led to substantial improvements in classification
accuracy in both applications, especially in the most challenging (but often
realistic) setting when the amount of labeled data per client is limited.

## References

  * Acar et al. (2018) Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti.  A survey on homomorphic encryption schemes: Theory and implementation.  _ACM Computing Surveys_ , 51(4), 2018.
  * Albaseer et al. (2020) Abdullatif Albaseer, Bekir Sait Ciftler, Mohamed M. Abdallah, and Ala I. Al-Fuqaha.  Exploiting unlabeled data in smart cities using federated edge learning.  In _International Wireless Communications and Mobile Computing Conference (IWCMC)_ , 2020.  URL https://doi.org/10.1109/IWCMC48107.2020.9148475.
  * Aliasgari et al. (2013) Mehrdad Aliasgari, Marina Blanton, Yihua Zhang, and Aaron Steele.  Secure computation on floating point numbers.  In _Network and Distributed System Security Symposium (NDSS)_ , 2013\.  URL https://www.ndss-symposium.org/ndss2013/secure-computation-floating-point-numbers.
  * Bonawitz et al. (2017) Kallista A. 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 _ACM Conference on Computer and Communications Security (SIGSAC)_ , 2017.  URL https://doi.org/10.1145/3133956.3133982.
  * Bringer et al. (2013) Julien Bringer, Hervé Chabanne, and Alain Patey.  SHADE: Secure HAmming DistancE computation from oblivious transfer.  In _International Conference on Financial Cryptography and Data Security (FC)_ , 2013.  URL https://link.springer.com/chapter/10.1007/978-3-642-41320-9_11.
  * Cai et al. (2021) Tianle Cai, Ruiqi Gao, Jason Lee, and Qi Lei.  A theory of label propagation for subpopulation shift.  In _International Conference on Machine Learing (ICML)_ , 2021.  URL https://proceedings.mlr.press/v139/cai21b.html.
  * Catrina & Saxena (2010) Octavian Catrina and Amitabh Saxena.  Secure computation with fixed-point numbers.  In _Financial Cryptography and Data Security (FCDS)_ , 2010.
  * Dehaene et al. (2020) Olivier Dehaene, Axel Camara, Olivier Moindrot, Axel de Lavergne, and Pierre Courtiol.  Self-supervision closes the gap between weak and strong supervision in histology.  _CoRR_ , abs/2012.03583, 2020.  URL https://arxiv.org/abs/2012.03583.
  * Dennis et al. (2021) Don Kurian Dennis, Tian Li, and Virginia Smith.  Heterogeneity for the win: One-shot federated clustering.  In _International Conference on Machine Learing (ICML)_ , 2021.  URL http://proceedings.mlr.press/v139/dennis21a.html.
  * Diao et al. (2022) Enmao Diao, Jie Ding, and Vahid Tarokh.  SemiFL: Communication efficient semi-supervised federated learning with unlabeled clients.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2022.  URL https://arxiv.org/abs/2106.01432.
  * Grammenos et al. (2020) Andreas Grammenos, Rodrigo Mendoza-Smith, Jon Crowcroft, and Cecilia Mascolo.  Federated principal component analysis.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2020.  URL https://proceedings.neurips.cc/paper/2020/hash/47a658229eb2368a99f1d032c8848542-Abstract.html.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.  URL https://openaccess.thecvf.com/content_cvpr_2016/html/He_Deep_Residual_Learning_CVPR_2016_paper.html.
  * Huang et al. (2021) Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson.  Combining label propagation and simple models out-performs graph neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2021.  URL https://openreview.net/forum?id=8E1-f3VhX1o.
  * Indyk & Motwani (1998) Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: towards removing the curse of dimensionality.  In _Symposium on Theory of Computing (STOC)_ , 1998.  URL https://dl.acm.org/doi/abs/10.1145/276698.276876.
  * Iscen et al. (2019) Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum.  Label propagation for deep semi-supervised learning.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.  URL http://openaccess.thecvf.com/content_CVPR_2019/html/Iscen_Label_Propagation_for_Deep_Semi-Supervised_Learning_CVPR_2019_paper.html.
  * Jeong et al. (2021) Wonyong Jeong, Jaehong Yoon, Eunho Yang, and Sung Ju Hwang.  Federated semi-supervised learning with inter-client consistency & disjoint learning.  In _International Conference on Learning Representations (ICLR)_ , 2021.  URL https://openreview.net/forum?id=ce6CFXBh30h.
  * Jiang & Ju (2022) Lei Jiang and Lei Ju.  Fhebench: Benchmarking fully homomorphic encryption schemes, 2022.
  * Kairouz et al. (2021) Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D’Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao.  Advances and open problems in federated learning.  _Foundations and Trends in Machine Learning_ , 2021.  URL https://doi.org/10.1561/2200000083.
  * Karimireddy et al. (2020) Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh.  SCAFFOLD: stochastic controlled averaging for federated learning.  In _International Conference on Machine Learing (ICML)_ , 2020.  URL http://proceedings.mlr.press/v119/karimireddy20a.html.
  * Khamis & Lampert (2014) Sameh Khamis and Christoph Lampert.  Coconut: Co-classification with output space regularization.  In _British Machine Vision Conference (BMVC)_ , 2014.  URL http://www.bmva.org/bmvc/2014/papers/paper044/index.html.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.  URL https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf.
  * Li et al. (2020) Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization in heterogeneous networks.  In _Machine Learning and Systems (MLSys)_ , 2020.  URL https://proceedings.mlsys.org/book/316.pdf.
  * Liang et al. (2022) Xiaoxiao Liang, Yiqun Lin, Huazhu Fu, Lei Zhu, and Xiaomeng Li.  Rscfed: Random sampling consensus federated semi-supervised learning.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.  URL https://doi.org/10.1109/CVPR52688.2022.00991.
  * Liu et al. (2019) Yanbin Liu, Juho Lee, Minseop Park, Saehoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang.  Learning to propagate labels: Transductive propagation network for few-shot learning.  In _International Conference on Learning Representations (ICLR)_ , 2019.  URL https://openreview.net/forum?id=SyVuRiC5K7.
  * Long et al. (2020) Zewei Long, Liwei Che, Yaqing Wang, Muchao Ye, Junyu Luo, Jinze Wu, Houping Xiao, and Fenglong Ma.  FedSiam: Towards adaptive federated semi-supervised learning.  arXiv:2012.03292, 2020.  URL https://arxiv.org/abs/2012.03292.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2017.  URL http://proceedings.mlr.press/v54/mcmahan17a.html.
  * Naor & Pinkas (2001) Moni Naor and Benny Pinkas.  Efficient oblivious transfer protocols.  In _Symposium on Discrete Algorithms (SODA)_ , 2001.
  * Ogier du Terrail et al. (2022) Jean Ogier du Terrail, Samy-Safwan Ayed, Edwige Cyffers, Felix Grimberg, Chaoyang He, Regis Loeb, Paul Mangold, Tanguy Marchand, Othmane Marfoq, Erum Mushtaq, Boris Muzellec, Constantin Philippenko, Santiago Silva, Maria Teleńczuk, Shadi Albarqouni, Salman Avestimehr, Aurélien Bellet, Aymeric Dieuleveut, Martin Jaggi, Sai Praneeth Karimireddy, Marco Lorenzi, Giovanni Neglia, Marc Tommasi, and Mathieu Andreux.  FLamby: Datasets and benchmarks for cross-silo federated learning in realistic healthcare settings, 2022.  URL https://openreview.net/forum?id=GgM5DiAb6A2.
  * Paillier (1999) Pascal Paillier.  Public-key cryptosystems based on composite degree residuosity classes.  In _International Conference on the Theory and Application of Cryptographic Techniques (EuroCrypt)_ , 1999.  URL https://link.springer.com/content/pdf/10.1007/3-540-48910-X_16.pdf.
  * Song et al. (2022) Congzheng Song, Filip Granqvist, and Kunal Talwar.  FLAIR: federated learning annotated image repository.  _CoRR_ , abs/2207.08869, 2022.  doi: 10.48550/arXiv.2207.08869.  URL https://doi.org/10.48550/arXiv.2207.08869.
  * Tan & Le (2019) Mingxing Tan and Quoc Le.  EfficientNet: Rethinking model scaling for convolutional neural networks.  In _International Conference on Machine Learing (ICML)_ , 2019.  URL https://proceedings.mlr.press/v97/tan19a.html.
  * Tarvainen & Valpola (2017) Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/68053af2923e00204c3ca7c6a3150cf7-Abstract.html.
  * Vapnik (1982) Vladimir Vapnik.  _Estimation of Dependences Based on Empirical Data_.  Springer, 1982.  URL https://link.springer.com/book/10.1007/0-387-34239-7.
  * Vinyals et al. (2016) Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.  Matching networks for one shot learning.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2016.  URL https://proceedings.neurips.cc/paper/2016/hash/90e1357833654983612fb05e3ec9148c-Abstract.html.
  * Wang et al. (2020) Binghui Wang, Ang Li, Hai Li, and Yiran Chen.  Graphfl: A federated learning framework for semi-supervised node classification on graphs.  _CoRR_ , abs/2012.04187, 2020.  URL https://arxiv.org/abs/2012.04187.
  * Wang & Leskovec (2022) Hongwei Wang and Jure Leskovec.  Combining graph convolutional neural networks and label propagation.  _ACM Trans. Inf. Syst._ , 40(4):73:1–73:27, 2022.  doi: 10.1145/3490478.  URL https://doi.org/10.1145/3490478.
  * Xie et al. (2021) Han Xie, Jing Ma, Li Xiong, and Carl Yang.  Federated graph classification over non-iid graphs.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 18839–18852, 2021.  URL https://proceedings.neurips.cc/paper/2021/hash/9c6947bd95ae487c81d4e19d3ed8cd6f-Abstract.html.
  * Zhang et al. (2021a) Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu-Ming Yiu.  Subgraph federated learning with missing neighbor generation.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 6671–6682, 2021a.  URL https://proceedings.neurips.cc/paper/2021/hash/34adeb8e3242824038aa65460a47c29e-Abstract.html.
  * Zhang et al. (2021b) Zhengming Zhang, Yaoqing Yang, Zhewei Yao, Yujun Yan, Joseph E. Gonzalez, Kannan Ramchandran, and Michael W. Mahoney.  Improving semi-supervised federated learning by reducing the gradient diversity of models.  In _International Conference on Big Data (Big Data)_ , 2021b.  URL https://doi.org/10.1109/BigData52589.2021.9671693.
  * Zhou et al. (2004) Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf.  Learning with local and global consistency.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2004.  URL https://proceedings.neurips.cc/paper/2003/file/87682805257e619d49b8e0dfdc14affa-Paper.pdf.
  * Zhu (2005) Xiaojin Zhu.  _Semi-supervised learning with graphs_.  PhD thesis, Carnegie Mellon University, 2005.  URL https://pages.cs.wisc.edu/~jerryzhu/pub/thesis.pdf.
  * Zhu & Ghahramani (2002) Xiaojin Zhu and Zoubin Ghahramani.  Learning from labeled and unlabeled data with label propagation.  Technical Report CMU-CALD-02-107, School of Computer Science, Carnegie Mellon University, 2002.  URL https://mlg.eng.cam.ac.uk/zoubin/papers/CMU-CALD-02-107.pdf.

##  Appendix A Experimental Details

###  A.1 XCLP for Prediction

Dataset We use the Fed-ISIC2019 (Ogier du Terrail et al., 2022) dataset which
contains over 20, 000 images of skin lesions. The task is to predict melanoma
(cancer) types. There are 6 clients, naturally defined by hospital and scanner
used. As a result the data of each client is highly heterogeneous in terms of
the amount of data per client (12413, 3954, 3363, 2259, 819, 439 examples for
each client respectively), the classes present at each client as well as
visual content of the images. Due to the class imbalance in the dataset the
evaluation metric used is balanced accuracy.

Network Following Ogier du Terrail et al. (2022) we use an EfficientNet (Tan &
Le, 2019) pretrained on ImageNet, which we denote by $f$. We initialize a new
final linear layer and fine-tune the whole network using federated averaging
as described in Ogier du Terrail et al. (2022).

Hyper-parameters We set all hyper-parameters for FederatedAveraging to the
values specified in Ogier du Terrail et al. (2022) except we increase the
number of training rounds to $T=40$ as we found that the accuracy to improve
with further training. Parameters for XCLP (LSH dimension, $k$-NN parameter)
are chosen using cross-validation. We use $L=1024$ and $k=3$. We fix the
parameter $\alpha=0.99$.

###  A.2 XCLP for federated semi-supervised learning

Datasets We evaluate XCLP on three standard datasets for multi-class
classification: CIFAR-10 (Krizhevsky, 2009), which has 10 classes and is used
in previous federated SSL works, as well as the more difficult CIFAR-100
(Krizhevsky, 2009) and Mini-ImageNet (Vinyals et al., 2016) which both have
100 classes. To the best of our knowledge ours is the first work in this
federated SSL setting to evaluate on these more challenging datasets. All
three datasets consist of $60{,}000$ images which we split into training sets
of size $n\coloneqq 50{,}000$ and test sets of size $10{,}000$. From the
training set, $n_{L}$ examples are labeled and the remaining $n-n_{L}$ are
unlabeled. For CIFAR-10 we evaluate with $n_{L}=1{,}000\text{ and }5{,}000$.
For CIFAR-100 and Mini-ImageNet we take $n_{L}=5{,}000$ and $10{,}000$.

Federated Setup We simulate a FL scenario by splitting the training data
(labeled and unlabeled) between $m$ clients. $m_{L}$ of these have partly
labeled data, while the others have only unlabeled data. Each client is
assigned a total of $n/m$ data points of which $n_{L}/m_{L}$ are labeled if
the client is one of the $m_{L}$ which possess labels. We simulate statistical
heterogeneity among the clients by controlling the number of classes each
client has access to. In the i.i.d. setting all clients have uniform class
distributions and receive an equal number of labels of each class. In the
non-i.i.d. setting we assign a class distribution to each client and clients
receive labels according to their own distribution.

Networks Following prior work, we use 13-layer CNNs (Tarvainen & Valpola,
2017) for CIFAR-10 and 100 and a ResNet-18 (He et al., 2016) for Mini-
ImageNet. Feature extractors are all layers except the last fully connected
one, thus embeddings have dimension 128 and 512, respectively.

Hyper-parameters We choose hyper-parameters for all methods based on training
progress (LSH dimension, $k$-NN parameter) or accuracy on a held-out
validation set consisting of 10% of the training data (batch size, learning
rate).

Federated learning parameters We set the number of clients to $m=100$, except
for our experiments on CIFAR-100 and Mini-ImageNet with $n_{L}=5000$. In these
cases we set $m=50$ as it is not possible to create an i.i.d. split of the
data over 100 clients since the number of classes (C=100) is too large. For
CIFAR-10 we set the number of clients which possess labels to $m_{L}=100$ and
$m_{L}=50$. On CIFAR-100 and Mini-ImageNet we set $m_{L}=m$.

The ClientUpdate step corresponds to $E$ epochs of stochastic gradient descent
(SGD) of a loss function. We set the number local epochs to $E=5$ and the loss
function is (per sample weighted) cross-entropy loss. The ServerUpdate step
corresponds to averaging the model updates:

$\texttt{ServerUpdate}(\theta^{(j)}\text{ for }j\in P)=\frac{1}{|P|}\sum_{j\in
P}\theta^{(j)}.$

The number of training rounds is set to $T=1500$ and the number of clients
sampled by the server per training round is set to $5$, so $\tau=0.05$ when
$m=100$ and $\tau=0.1$ when $m=50$. Note that when $m_{L}<m$ we ensure that
the server samples $\tau m_{L}$ clients from the labeled portion (and
$\tau(m-m_{L})$ from the unlabeled) to ensure that there are some labels
present in the graph.

Network training parameters  We use standard data augmentation following
Tarvainen & Valpola (2017). On CIFAR-10 and CIFAR-100 this is performed by 4×4
random translations followed by a random horizontal flip. On Mini-ImageNet,
each image is randomly rotated by 10 degrees before a random horizontal flip.
We use weight decay for all network parameters which is set to $2\times
10^{-4}$. When carrying out SGD in the ClientUpdate we use batches of data
$B=B_{L}\cup B_{U}$ where $B_{L}$ is a batch of labeled data and $B_{U}$ is a
batch of pseudo-labeled (previously unlabeled) data. We set $|B_{L}|$
according to how many labeled samples the client has available,
$|B_{L}|=\min(50,\\#labels)$. We set $|B_{U}|=|B_{L}|$. Learning rate for SGD
is set according to this batch size. On CIFAR-10, for $|B_{L}|<50$ we set the
learning rate to $0.1$ and for $|B_{L}|=50$ we set the learning rate to $0.3$.
On CIFAR-100 and Mini-ImageNet we always have $|B_{L}|=50$ and we set the
learning rates to $0.5$ and $1.0$ respectively. We decay the learning rate
using cosine annealing so that the learning rate would be 0 after 2000 rounds.

XCLP parameters  We set the LSH dimension to $L=4096$ as this gave near exact
approximation of the cosine similarities while still being computationally
fast (less than 1 second per round). We set the sparsification parameter to
$k=10$, so that each point is connected to its 10 most similar neighbors in
the graph, and the label propagation parameter to $\alpha=0.99$.

##  Appendix B Additional Background

###  B.1 Propagating values along a data graph

For a graph with $n$ vertices and adjacency matrix
$\mathcal{W}\in\mathbb{R}^{n\times n}$ of edge weights, a vector of values,
$y\in\mathbb{R}^{n}$, can be propagated to neighboring vertices by forming
$z=\mathcal{W}y$. By repeatedly multiplying with $\mathcal{W}$ values can be
propagated all along the graph structure (Zhu, 2005).

In the context of propagating labels, one wants not only to propagate the
labels to unlabeled points, but also to prevent the information at labeled
points to be forgotten. For that, one can uses an extended update rule

$z_{t+1}=\alpha\mathcal{W}z_{t}+y$ (1)

where $\alpha\in(0,1)$ is a trade-off hyperparameter. For
$\|\mathcal{W}\|<1/\alpha$, this process has the closed form expression

$z_{\infty}=(\operatorname{Id}-\alpha\mathcal{W})^{-1}y,$ (2)

as its ($t\to\infty$)-limit. This can be seen from the fact that Equation 1 is
a contraction with $z_{\infty}$ as fixed point.

In Section 3.1 we make use of this fact together with the observation that
Equation 2 can readily be applied to vectors-valued data with a matrix $Y$ in
place of $y$. However, the propagation step will not preserve normalization,
e.g. of the $L^{1}$-norm. When such a property is required, e.g. for the
calculation of entropy-based confidence, normalization has to be performed
explicitly post-hoc.

###  B.2 Computing similarity from hashed data

Locality-sensitive hashing (LSH) (Indyk & Motwani, 1998) is a procedure for
hashing real-valued vectors into binary vectors while preserving their
pairwise similarity. Let $v\in\mathbb{R}^{d}$ be a vector. To encode $v$ into
a binary vector $b$ of length $L$, LSH randomly samples $L$ hyperplanes in
$\mathbb{R}^{d}$. For each hyperplane it checks whether $v$ lies above or
below it and sets the $i$th bit in $b$ as $1$ or $0$ accordingly. Formally,
$b_{i}=\mathbbm{1}_{\langle v,u_{i}\rangle\geq 0}$, where
$u_{i}\in\mathbb{R}^{d}$ is the normal vector of the $i$th hyperplane. A key
property of LSH is that it approximately preserves cosine-similarity.
Concretely, for vectors $v_{1},v_{2}$ with LSH encodings $b_{1},b_{2}$
(compute with the same projections), one has

$\frac{\langle v_{1},v_{2}\rangle}{\|v_{1}\|\|v_{2}\|}\approx\cos(\pi
h(b_{1},b_{2})/L)$ (3)

where $h$ is the Hamming distance (number of bits that differ) between two
binary vectors. The reason is that the probability of $b_{1}$ and $b_{2}$
differing at any bit $i$ is the probability that the $i$-th sampled hyperplane
lies between $v_{1}$ and $v_{2}$, which is equal to
$\measuredangle(v_{1},v_{2})/\pi$. By the law of large numbers, the more
hyperplanes one samples, the better the approximation quality.