Cross-client Label Propagation for Transductive and Semi-Supervised Federated Learning
Authors: Jonathan Scott
Michelle Yeo
Christoph H Lampert
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (10/2023)
Cross-client Label Propagation for Transductive and Semi-Supervised Federated Learning
Jonathan Scott
Smmathnn.coot@@ist.cm
ISTA (Institute of Science and Technology Austria), Klosterneuburg, Austria
Michelle Yeo
michelle. yeoteelle.yesssst..o.. ac.at
ISTA (Institute of Science and Technology Austria), Klosterneuburg, Austria
Christoph H. Lampert
chl@ist. ac.at
ISTA (Institute of Science and Technology Austria), Klosterneuburg, Austria
Reviewed on OpenReview: https: opw.reveew........emeee net/ formm? id=
9d gY04GX8R5k
Abstract
We present Cross-Clien Label Propagation (XCLP), a new method for transductive and semi-supervised federated learning. XCLP estimates 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 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 to repeatedly pscudo-label unlabeled training data in a foderated 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) McMMahan et al. 2017 is machine learning paradigm in which multiple clients, each owning thoir own data, cooperate to jointly solve a lcarning task. The process is typically coordinated by a central server. The defining restriction of FL that client data must remain on device and cannot. be shared with either the server or other clients. In practice this usually not due the server being viewed 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 the supervised setting, in which client data is fully labeled and the goal is to train 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 handful of the photos on their devices (Song et al. 2022 Similarly, in 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 Iearn from partly labcled or fully unlabcled data in a foderated setting (Kairouz el 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.) (021]) and dimensionality
reduction [Grammenos al. (022)), where clients compute statistics based on their data and the server computes with aggregates of these statistics.

---

Published in Transactions on Machine Learning Research (10/2023)
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 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. We refer to this privacy guarantee, in which a client's 's data never leaves their own device, as data confidentiality. 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 summaation 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 achieves data confidentiality, since 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 technique to transfer label information from labeled to unlabeled points, XCLP is versatile enough to be used in a variely 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 features obtained from models trained using Federaled Averuging 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 into standard federated learning pipeline. Specifically, during each round of FederaledAAveraiing 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 da datasets, namely CIFAR-100 and Mini-Imagethe where we also observe substantial improvements in accuracy.
2 Related Work
Federated Learning Federated learning (FL) [McMahan et al. 2017] was originally proposed for Icarning 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 al. 2020), in which the server acts on aggregates of the client data, as opposed client models. Other works have focused model based approach to federated semi-supervised learning (SST.). Jeong
2

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 1: Croos=CCleentlabeePPogggge
Input: set of participating clients P. client data (VL), (EP // data stored on-device at clients
1-XS: Setup: clients exchange private and public keys, agree on random seed
2-CS: for client j E P in parallel do
3-CS: IT Rexd with 1lg
ii.d ~
Na (0,
1/ same II for each clienl
4-CS:
B6) sIl (V
// LSH projection // server gets Humming matrix // estimate cosine similarity matrix 11 keep & largest entries per row, set others to O
5-XS: H SecureHamming ng (ogggg(((B))))) )EEP)
6-SS: A < cos( E H)
7-SS: B + sparsify(A)
8-SS: W- B+ B
// symmebrize // normalize 1/ influence matrix
9-58: W + --&WD for D = diag(d),..... da) with d, = Ej Wis
10-SS: 5 (Iduxa aW)-
11-CS: for client j E in parallel do
12-CS:
slD + labeled-colsy(S)
// client gets columns corresponding to labeled data // compute local contribution to overall label propagation // client gets its part of aggregated contributions // predict labels
Z s(
C3-CS:
14-XS:
2 + SecureRowSums )(())))))))))
15-CS:
g0) ( (arg max, e= 1 1,0 i=1,..,,)0
w8) <- (1 entropy(
(Z ) log Co ;=1.....()))
16-CS:
// predicted label confidences
Σ.-1 2551
Output: predicted labels and confidences (g1)) w
// available only to respective clients
it al. 2022 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. (002) combine local semi-supervised training with an enhanced aggregation scheme which re-weights client models based on their distance from the mean model. Zhang al.) (2021b) and Diao et al. (022) focus 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 wet 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 al., 2021at Xie et al. 2021 Wang et al. 2020). However, these works are primarily interested in learning from data that is already graph. In contrast XCLP estimates graph based similarities between data points, in order to spread label information over the edges.
Label Propagation (Zhu & Ghahramani proposed as a tool for transductive learning with partly labeled data. Over time has proven to be a versatile tool for a wide range of problems. Several works have applied I.P to the problem of domain adaptation. Liu et al. (2019) apply LP over a learned graph for few shot learning. Cai al. (2021) develop framework for domain adaptation by combining LP with teacher trained on the source. Khamis & Lampert (2014) use
Label Propagation
2002 Zhou et al. 2004 was originally
LP prediction-tiin time regularizer for collective classification tasks. In the context of deep semi-supervised learning Iscen et al. (2019) make use of LP as means of obtaining pscudo-labels for unlabeled data which are Uhen used in supervised training. Several works apply LP to problers with graphical data. |Huang el 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 & Leskoved (2022) apply I.P as a regularizer for graph convolutional neural networks when learning edge weights and quantify the theoretical connection between them in terms of smoothing.
3

---

Published in Transactions on Machine Learning Research (10/2023)
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 federated learning scenario, a randomly chosen subset, or strategically chosen subset, e.g. based on client similarity, diversity or data set sizes.
Each client j E P possesses a set of n0) d-dimensional data vectors, of which 260 are labeled, i.c. VG) = ())
()) (f) (.....))))) (8)
(of) "...... .....
....../)) "0s +11))11--- "Mn)" T Rno0)d, with partial labels {vl ..... M1cs from C classes, which we encode
in zero-or-one-hol matrix form: Y E (0,1)" 1p with rid = 1 (v) ==(==)) c} for 1 S (60 and y- otherwise. Note that this setup includes the possibility for client to have only labeled data, n(t) (0) or only unlabeled data, (0) = O. We denote the total amount of data by = Ejep Ejepn()) n(), Our goal is to assign labels to the unlabeled data points, i.e., bransduclive learning (Vapuik 1982. The process is coordinated by 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 At the same time, we treat clients and server as curious, ie., 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- Label Propagation (XCLP), an algorithm for assigning labels to the unlabeled data points. XCLP works by propagating label information across 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 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 distributes back to the clients, 3) the clients locally compute how their data influences others, aggregate this information, and infer labels for their daia.
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 way that allows us to use only light- oryptographic protocols for the steps of computing similarities and aggregating label information.
3.1 Cross-Client Label Propagation (XCLP)
Algorithm 1 shows psoudocode for XCLP To refiect the distributed nature of XCLP we mark the exccution type of each step: client sleps (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. (017).
The clients use the agreed-on random seed to generate common matrix II E R-xd with unit Gaussian random entries (line 3). Each client, j, then multiplies its data matrix V(t) by IT and takes the component-wis sign of the result, thereby obtaining a matrix of nl() L-dimensional binary vectors, BQ) (line
Phase 1.
4.. In combination, both steps constitute a local meality-sensiiive 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, U, v', can be recovered from their binary encodings b, b: sim(v, o') | [[ co,(Th((,
(v.0')
where b(b,b)) = Et by @ b/ is the Hamming distance (number of bits that differ) between binary vectors
In particular we exclude malicious servers the cryptographic sense that would, e.g., be allowed to employ attacks such as model poisoning or generating fake clients in order break the protocol.
4

---

Published in Transactions on Machine Learning Research (10/2023)
and @ is the XOR-operation. Since all clients use identical random projections, this identity holds even for data points located on different. clients. See Appendix C.2 for details on LSH.
In line 5 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 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 Znx", but other information about the data.
Phase 2. Having obtained H the server executes number of steps by itself. First, it converts H to a (cosine) similarity matrix A E RRxx (line G). It sparsifies each row of A by keeping the k largest values and setting the others to (line 7 From the resulting matrix, B, it constructs a weighted adjacency matrix of the data graph, W by symmetrization (line S and normalization (line 9
If not for the aspect of data confidentiality, 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 (
10,1)* and compute Z = SY E R2*c, where S = (Id -aW)- is the influence matriz, and a E (0, 1) is a hyperparameter. See Appendix C.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 confidentiality of the labels. Instead, it computes only the influence matrix, S, centrally on the server (line I0 while the multiplication with the labels will be performed in a distributed way across the clients.
Phase Observe that the computation of Z can also be written as Z= EjEE S())y(5), where SG) g 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 that correspond to the unlabeled data of client are identically 0 by construction and hence do not contribute to the multiplication. Therefore, writing Y E ( xCxxxx for the rows of (u) that correspond to labeled points and sli) (=x( for the corresponding columns of $6), it also holds that Z = Ejer 5(0
Using this observation, A Algorithm continues by each client j receiving s from the server (line 12 It then locally computes Z s R (line 13,, 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 ΣjEp ZÚ), To compute the sum while preserving data confidentiality, XCLP uses a secure summation routine (line 14h, as commonly used in FI 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, 2 E g xC (line 13 From these, it computes labels and confidence values for its data (lines 16
3.2 Cryptographic Subroutines
In this section we describe the proposed cryptographic protocols for secure summation and secure Hamming dislance compulation that allow clients to run XCLP without having to share their data.
SecureRowSums We propose a variation of the secure summation that commonly used in FL (Bonawitz ct al. 2017]. For simplicity we describe the case where all values belong Z, for some 1 E N, though extensions to fixed-point or floating-por arithmetic also exist. (Catrina & Saxenal 2010 Aliasgari al., 2013
Given a set of clients P, cach with some matrix 2 E xn ordinary SecureSum computes ΣjEp Z at the server in such a way that the server learns only the sum but nothing about the z matrices. The main idea as follows: using agreed upon random seeds clients jointly create random matrices M() E xaxe with the property that EgerMU MD) 0. Each client j then obfuscates its data by computing Z0) = 2 M()
5

---

Published in Transactions on Machine Learning Research (10/2023)
and sends this to the server. From the perspective of the server each Z is indistinguishable from uniformly random noise. However, when all parts are summed, the obfuscations cancel out and what remains is the desired answer: ΣjEP 26) = -jep Z6), For technical details see Bonawitz et al. (2117).
For XCLP, we propose a modification of the above construction. Suppose we have a partition of the rows, (Ry)jer, where each R3 C [n] Each client j knows its own R3 and the server knows all Ry. SecureRouSums's 's task is to compute Z = Σ jEp z(6) in a distributed form in which each client j E P learns only the rows of Z indexed by Rj, denoted Z Ry], and the server learns nothing.
For this, let M and 2 be defined as above. In addition, lct 2 be oqual to the obfuscated 200, except that the rows indexed by R2 are completely set to O. Each client now instead sends 20s to the server, which computes - = DjEP 200, The server then redistributes 2 among the clients, i.e. each client j receives [[ Note that 2[R,] = EkEPrC) [(,] Z[R,] - [R)] Consequently, each client obtains the part of Z corresponding to its own data by computing [[R²]= = [R,] + [R)) By construction the shared quantities leak nothing to the server. Specifically 2 is random noise with rows R set to 0 and 2 is random noisc since each block [Ry remains obfuscated due to client j not sending [R)].
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 it only requires only an oblivious transfer (OT) (Naor & Pinkas 2001) routine as cryptographic primitive. The other is based on partially homomorphic encryplion (PHE) and comes with lower communication cost.
OT-based secure Hamming distance: Let b b= (bi,...,bb) br) and 6' = (6%,...,,%)) the Hamming distance should be computed, where b is stored on a client j and &' on a client k.
(22) be the bit vectors, for which
1) client j creates I. random numbers r',-..,P'. uniformly in the range [0, I. 1]. For each l= 1,..., L, it then offers two values to be transferred to client kn of = ri + by or o = ri + b,, for b = - by (here and in the following all calculations are performed in Σg, i.c. in the integers modulo L).
2) Client & initiates an OT operation with input B/ and result 4. That means, if b/1 =0 it will receive fa = =f and if 1/ = it will receive 4 = =/, but client will obtain no information which of the two cases occurred. Note that in both cases, it holds that t; = rι + by + B/. However, client & gains no information about the value of by from this, because of the uniformly random shift ri that unknown to it.
3) Clients and k now compute R = Et= ri and T = -Eh 4,, respectively, and send these values to the server.
4) From R and T, the server can infer the Hamming distance between b and 0' as T- by h0 h(b, D').
Performing these steps for all pairs of data points, the server obtains the Hamming matrix, H E Noxn, but no other information about the data. The clients obtain no information about each others' data at all during the computation.
PHE-based secure Hamminng distance: Homomorphic eneryption is 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 binary vector from clients j with all binary vectors from client k in the following way:
1) Client j encrypts its own data vector b6) E 14, using its own public key and transfers the resulting vector y := enc(b()) (boxes indicate encrypted quantities) to client k. Because the data is encrypted, client l can extract no information about client j's data from this.
6

---

Published in Transactions on Machine Learning Research (10/2023)
2) For any of its own data vectors b(h) E {0, 10, client & creates uniformly random value r E [0, 1]. It then computes the following function in homomorphic way with encrypted input y = y and plaintext input z = b(()
fly:z) =r
Σ y1
Σ
y1
1:21=1
Because of the identity h(z,y) = E, (mi + Dmuill Σ 11iz==1 81 +
Σ 0 31 - Eia== 31 Eizz= 31 +n Σ, 27
the result, T [( y (x), is the value T = h(b(),, BB(K) + n Σ by in encrypled form.
4) Client send the value R=r- n E by to the server, and the value T to client j. Client j decrypts 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 ((0))= T - RR 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--baed protocol saves a factor (k) in communication cost, because 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 robusiness of Algorithm 1
Efficacy Algorithm D 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, c.g. L = 4096.
Privacy The main insight is that Algorithm D Tacheres to the federated learning principle that clients do not have to share their data or labels with any other party. This 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) 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 imput vectors would result in the same W matrix. A second source of information sharing is during phase where cach 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.
Computational Complexity The computational cost. of XCLP is determined by factors: the cryptographic subroutines and the numeric operation. The contribution of the former depends heavily on the underlying implementation and available hardware support, so we do not discuss it here. The cost of the numeric operations can be derived in explicit form. Assume that the number of clients per batch is p. Each client has n data points total, out of which m are labeled (for simplicíty, we assume n and m to be identical across clients here). Let the feature dimensionality be d and the number of classes C. Then, to run XCLP with L-dimensional bit vectors, each client computes O(dnL). Then, the clients jointly compute all p²n² /2 pairwise Hamming distances, which requires n()²?n²) operations and has overall complexity O(Lp??) if run in parallel by the clients. The server inverts the matrix at cost OGr²n²). Then, each client multiplies an pm x m sized part of the resulting matrix with their m x C label matrix, which costs OCpmm) per client, and also has overall complexity O(Cpmm) if run on the clients in parallel. Overall, the most costly step is the matrix inversion, but that is done on the server, which we assume to have much higher compute capabilities. Assuming L > C and np d, the clients costs are dominated by the O(Tp??) term.
L binary data matrix, which has complexity
7

---

Published in Transactions on Machine Learning Research (10/2023)
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
linetuned per-elient LP
training set size
per-client LP
XCLP
FedAug
XCLP
954
30.70 + 1.25
34.00 + 1.12
43.78 + 0.88
45.35 + 1.25
47.48 1.12
n 1882
31.40 + 1.18
34.61 + 0.98
46.83 + 0.75
48.10 + 1.18
52.34 + 0.93
3744
37.41 + 0.20
38.49 + 0.88
52.87 + 0.14
56.98 + 0.20
59.49 = 0.88
π = 18597
55.10 = 0.51
53.38 + 0.67
63.78 0.20
73.30 + 0.51
74.22 = 0.67
For comparison, to run per-client LP, each client has to compute n²/2 d-dimensional inner products, invert the resulting n X n matrix, and multiply a sub-matrix of size m X n it with a label matrix of size m x C. The complexity per client is Odd'" +n + Cmn), which is also the total complexity, if all clients can operate in parallel. In practice, any computation. Consequently, with typical trade-off of, e.g. L 8d, XCLP requires 8p times more numeric operations than local LP. Note, however, that one has good control over the total cost, as L and p (and potentially d) are design choices.
expect d > n C, so the dominant term is (ddn)). The server does not contribute
On an absolute scale, all of these values are rather small. For example, with p = 10, d d= 512, and L = 4096, the number of numeric operations a client has to perform per datapoint is in the order of 10". In many settings, this can be expected to be less than the the operations needed to compute the datapoints feature representation in the first place, e.g. when using (even small) neural network for that purpose.
Communication Efficiency XCLP incurs communication costs at two steps of Algorithm I With the OT-based protocol for computing the n1() x (k) Hamming matrix between two clients j and k, client j sends (() L integer values in Z, to client k. With the enhanced PHE-based protocol, this amount is reduced to sending n()) encrypled values from j to k and () in the opposile direction. Each of the two clients sends ()) integer values in Σn to the server. To propagate the labels via the distributed matrix multiplication, cach client j first receives from the server matrix of size
16). It transmits a matrix of size n x C to the server, and receives matrix of size n()) x C' back from it. In particular, XCLP requires only constant number of communication steps, which is in contrast to other mot 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 indeed the case for Algorithm [ a client dropping out before the SecureHamming ng step (line 5. is equivalent to not having been in P in the first place. Since the Hamming computation 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 carlier. If clients drop out after H has been computed, but before the SecureRowSums step (line 14), 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 the client only had unlabeled data. If clients drop out within SecureRowSums, after the obfuscation matrices have been agreod on but before the server has computed 2, 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.
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 on accuracy, not real-world efficiency, we use a simulated setting of federated learning, rather than physically distributing the clients
8

---

Published in Transactions on Machine Learning Research (10/2023)
Table 2: XCLP for prediction (Fed-ISIC2019 dataset):
client-out Classification accuracy [in %] for leave-one- leave-one-clint-oott experiments (average and standard deviation across three runs).
left-oul chient
FedAvg
XCLP
Client 35.15 + 0.96
38.89 1.34
Client 68.75 0.72
67.05 0.54
Client
51.94 +: 2.52
62.02
1.13
Client 4
42.72 + 0.79
54.84 0.78
Client 11.53 1.60
52.28 0.58
Client 46.92 = 3.69
61.27 3.19
Table 3: XCLP for prediction IFed-191 dataset): Classification accuracy [in %] when different fractions, of training data are labeled. FedAvg and XCLP (labeled) use only the labeled part of the training set, XCLP - uses also the unlabeled part.
FedAug
XCLP (labeled)
XCLP (labeled uulabeled)
0.05
43.78 1 0.88
47.48 1.12
49.50
1.42
a 0.1
46.83 + 0.75
52.34 + 0.93
53.78
0.90
a 0.2
52.87 0.14
59.49 0.88
61.09
0.66
1.0
$..78
74.22 + 0.67
74.22 0.67
across multiple devices. Therefore, we also use plaintext placeholders for the cryptographic steps that have identical output. Source code for our experiments can be found at http://ggihuubbooooonnnaooooe//
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 set of clients, P. possess training data X() x from some input space X, and a (potentially partial) label matrix yú) E (0, (0,1)x09xC The goal to infer labels for new batches of data, x-i) 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 has training data to contribute, X 0, but has batch of new data to be labeled, X 0.
By h X + Rdd we denote a preprocessing function, such as feature extractor. Each client applics h to all their data points, train and new, to obtaín their input vectors to the XCLP routine, V h h(x() ()) U x1i ). Running Algorithm on (VG), Y()))ep each client obtains y which are label assignments for all of their data points, in particular including x(1) as desired.
Experimental Setup We use the Fed-ISIC2019 dataset (Ogier du Terrail et al. 2022 real-world benchmark for federated classification of medical images. Tt 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 TmageNNtt, which we finetune using federated averaging. As preprocessing functions, h, we use the fcature extraction layers of the network either at the point of initialization (pretrained) or after the finetuning. Appendix A.1 gives full details of the experimental setup.
Results Table I 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 rum once 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.
9

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 2: FedAvg+XCIP
Input: partially labeled training data (X()), y()) 1 (δ, ( < ImiiiaaizzMNddePaaaaaeees.
2 for round & E (......) 7] do
3 P server randomly selects Tm clients
4 Server broadcasts 0 to each client in P
5
for client j E in parallel do
vG + (x)(())
g0),w()) + XCLP(V)), y P. Server) 86) + ClientUpdate( g0), w())
Client j sends (6)) to the server
10
0 ServerUpdate ((ol)) (EP))
Output: model parameters 0
with a better adas--daapted- 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 more challenging setting. We adopt leave-one-clientouu 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 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 when yo) is a (strictly) partial label matrix. In this case the unlabeled training data does not contribute label information lowards inference on x(i) but does contribule to a more densely sampled graph. Table 3 shows the results: the FedAvg column identical to the one in Table [ 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 [ 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.
4.2 XCLP for federated supe-supe learning
We now describe how XCLP can be applied iteratively during a training loop in the context of federated semi-supervised learning. FedAug+XCLPP shown in pseudocode in Algorithm follows general FL template of alternating local and global model updates. As such, it is compatible with most existing FL optimization schemes, such as FedAng (MeMahan 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 1 is to initialize the model parameters, = ( ()) where fa : X - Rd is the feature extraction part of neural network and fo : Rdd + RC 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 only the labeled examples.
We then itcrate the main training loop over T rounds. To start each round the server samples some fraction T of the m total clients. These clients receive the current model parameters from the server (line 4 and embed their labeled and unlabeled data with the feature extractor, fo. (line 6. Clients and server then collaboratively run XCLP on these feature vectors (line 7 As output of this stop each client updates the pscudo-labels and confidence values for their unlabeled data, which they then use for local supervised training (line D Lastly, clients send the updated local models to the server (line 9 which aggregates them (line 10
10

---

Published in Transactions on Machine Learning Research (10/2023)
Table 4: XCLP for federated SSL: classification accuracy [in %] on federated CIFAR-10. m is the number of clients, my, the number of clients with labeled data, n,, is the total number of labels across all clients. i.i.d.
and non-iid, refer how the data split among the clients. For details, see the main text and Appendix A.2
CIFAR-10, 1.i.d. (m 100)
my
100
50
Method
7L = 1000
VLL = 5000
TLL = 1000
74 5000
FedAvg (labeled only)
55.46 + 0.43
76.13 = 0.46
56.97 + 0.59
80.36
0.07
tedeAv---erllientt
61.75 2.22
85.11 + 0.73
65.29 + 2.50
84.41 + 0.25
Fed FedMatch
60.12
79.45 + 0.31
59.14 0.35
81.04 + 0.20
50.93 = 0.56
72.22 = 0.14
57.10 0.46
77.80 = 0.32
FedSiam
67.02 0.98
82.06 = 0.56
62.98 + 1.61
78.45 = 0.34
FedSem-
59.98 + 0.49
79.49 + 0.15
59.67 1 0.47
80.94 1 0.25
FedAvg+ 4CCP XCLP (ours)
70.91 1 0.71
$6.65 1 0.16
70.81 1 1.65
86.29 1 0.34
CIFAR-10, non-i.i.d. (m 100)
100
ML
50
Method
n1 1000
nL 5000
nz
1000
72 5000
FedAvg (labeled only)
50.94 + 0.14
75.34 = 1.38
53.26 + 0.69
79.65 = 0.12
FedAvg pereliettL
50.94 0.14
76.61 + 1.50
53.26 1 0.69
79.65 + 0.12
Fed -
60.60 + 0.60
80.07 + 0.53
59.82 + 1.05
81.14 + 0.23
MedMatch
50.71 + 1.57
71.99 + 0.70
48.24 + 0.86
66.37 + 0.41
FedSiam
67.85 0.26
82.23 = 0.46
62.29 1.84
78.84 0.72
FedSem+
60.93 + 0.97
79.70 = 0.78
59.74 + 0.74
81.30 = 0.09
FedAvg+XCLP (ours)
0.77
85.53 + 0.56
70.01 1.29
85.42 0.43
Table 5: XCLP for federated SSL: classification accuracy [in %] federated CIFAR-100 and Mini-ImageNees m is the number of clients, my the number of clients with labeled data, nr is the total number of labels across all clients.
DIFAR-100. i.i.d.
Mini- Wini--maaeNNe, i.i.d.
m my 50
m = my 100
m my 50
m my 100
Method
n1 3000
nt 10000
nL 5000
n1 10000
FedAvg (labeled only)
43.80 1 0.19
53.91 1 0.25
23.39 1 0.52
31.72 1 0.54
FedAvg+
43.80 1 0.19
54.19 1 0.21
23.98 0.36
31.86 1 0.57
43.82 1 0.59
54.38 1 0.36
25.53 + 0.22
33.09 + 0.62
Avg (ours)
50.19 + 0.60
57.00 + 0.08
26.93 + 0.41
35.78 + 0.56
The motivation for this approach comes from the insight gained in Section 4.1 that XCLP assigns high quality labels when run on leatures obtained from a trained network. Crucially, pseudd-labels assigned by XCLP are always recomputed when 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 rumning 5 epochs of SGD with confidence-weiilhted cross-entropy loss on the local device and ServerUpdate simply averages the local client models.
We use three standard datascts: CIFAR-10 (Krizhevsky 2009), which has 10 classes and is used in several previous federated SSL works (Jeong et al. 2021 Long el al.) |2200] Albaseer et. al. 2020), as well the more difficult CIFAR-100 ( (Krizhevsky) 2009) and Mini- Net (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.idd vs non-i.i.d.) to simulate a diverse range of federated settings.
We compare ModAAv+XCLLA to a broad range of other methods. To enable a fair comparison of results, all methods use the same network architecture, and parameersss are chosen individually to maximize each method's performance. From the existing federated SSL literature, report results for FedMatch
11

---

Published in Transactions on Machine Learning Research (10/2023)
(Jeong et al. )021), FedSiam (Long et al. 2020 and FedSem+, which follows (Albaseer et al. 2020 but additionally uses confidence-baset 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 FeedAvg-terccientt1 or from the network's classifier predictions neewook) Finally, we also report results for training a supervised manner on only the available labeled examples, FedAug (labeled only). Note that we do not include comparisons to Zhang et al. (2021b) and Diao et al. (0022) 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 provides a comparison of XCLP to other approaches and baselines in the standard setting of CIFAR-10 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-ii.d. across clients. Table 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, while of the other methods, none has consistent advantage over the others. In addition to these general observations the results offer a number of more specific insights.
4
Firstly, in nearly all cases semi-supervised methods outperformed the labeled only FedAvg baseline. This is to be expected given the additional (unlabeled) data available to the SSL methods. A notable exception to this, however, is FedAvg + perclientLP in the non-i.id. scenario. In this case in three of the four cases perclient-LP actually degraded the performance of the initial supervised model, which caused automatic model selection to deactivate it. A likely reason for this poor performance is the presence of classes in the client test data which do not appear in the labeled portion of the clients training data. In this situation Perclient-LP is not able to predict for these classes on the test data. In contrast XCLP is unlikely to be affected by this issuc, as more clients are pooled together and hence more classes are present in the labeled training data. This is reflected in the strong performance of FedAvg + XCLP in the non-i.i.d. setting.
Secondly, we observe that the biggest gains from incorporating XCLP occur in the regime where little labeled data is available. In particular see that with ample labeled data available per client, in the i.i.d. settings, perclientLP performs not so much worse than XCLP. This is to be expected as when each client already has ample labels available then the potential gain of collaboration with other clients is of course lower.
5 Conclusions and Limitations
In this work we introduced XCLP, 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 confidentiality when estimating 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 limited.
XCLP ensures that client's data remains anonymous, in the sense that it is not directly exposed to shared with any other party, notion of privacy we referred to data confidentiality. This is achieved through the guarantecs provided by the cyryptographic subroutines. While data confidentiality is fundamental building block of private machine learning paradigms, such as federated learning, on its own it does not guarantee that nothing can be learned about the clients or their data. Indeed it is common practice in private machine learning to combine data confidentiality with other notions of privacy, such as differential privacy, order to obtain stronger privacy guarantocs. Extending XCLP to integrate such notions of privacy an interesting direction for future work.
12

---

Published in Transactions on Machine Learning Research (10/2023)
References
Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. A survey on homomorphic encryption schemes: Theory and implementation. ACM Computing Surveys, 54), 2018.
Abdullatif Albascer, Bekir Sait Ciftler, Mohamed M. Abdallah, and Ala. I. Al-Fuqaha. Exploiting unlabeled data in smart cities using federated edge learning. In International Wireless Communicatiins and Mobile Computing Conference (IWCMC), 2020. URL https:///oi.ooo wtt..///....///////.//////
Mehrdad Aliasgari, Marina Blanton, Yihua Zhang, and Aaron Stecle. Secure computation on floating point numbers. In Network and Distribuled System Securily Symposium (NDSS), 2013. URL https:
wwww.ndss-syy htt.u//..rgg///////////eee.o wwtpa///ecceeeeeeee owtpa///sosuuueettttttttoooooooa Ploaaiing-ooiig numbers
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
10. 100.111//11399563333999999 attps://doi... /ttp://...orr1111114444333/33333
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 http://iiinnss.inngge.e htt.:a/....piiggg....om/caprtrrr www.coo.ccccccecc
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://procceddingg mml. p.rrprrss/
#139/cai21b.htn
Sebastian Caldas, Peter Wu, Tian Li, Jakub Koncčný, H. Brendan McMahan, Virginia Smith, and Amect
Talwalkar. LEAF: A benchmark for federated settings. CoRR, abs/1811201197,, 2018. URL http:
wwwxiv.org/abb/1122 01097
Octavian Catrina and Amitabh Saxena. Secure computation with fixed-point numbers. In Financial Cryptography and Data Security (FCDS), 2010.
Olivier Dehaene, Axel Camara, Olivier Moindrot, Axel de Lavergne, and Pierre Courtiol. Sele-superiision closes the gap between weak and strong supervision in histology. CoRR, abs/2012.03583, 2020. URL
https://arxiv. http://axxiv..r//bbaaaaa 20120022220 03583
Don Kurian Demnis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. In International Conference on Machine Learing (ICML), 2021. URL httpp://proceedinngs. press/
www.:ang..m...........m.......ee mlr. mlw.:ress///e
#139/dennis2l..be html
Enmao Diao, Jie Ding, and Vahid Tarokh. SemiFL: Communication efficient semi-supervised foderated learning with unlabeled clients. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
URL attpp::/aarxiv.orr//bb/////
01432
Andreas Grammenos, Rodrigo Mendoza-Smith, Jon Crowcroft, and Cecilia Mascolo. Federated principal component analysis. In Conference on Neural Information Processing Systems (NewrIPS), 2020. URL https
hhtppcac...a.r..ooooo/////////aa htwp://tss2-aatttatttaa.ca html
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
In Conference on Compuler Vision and Pallern Recognition (CVPR), 2016. URL htttpa://openacces:
cacpctt__vrr__000 thecvf. wwwp:/nteennccr_22111////1
Seaeee_Dee_RReeidueeee Residual Learning_ cwtperiinnn_______ee_ee CCWP__211__PPPPPPPee_ httl
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 httpss://ppenrevior http://ee.ppppoooooe..eee///eeer
Piotr Indyk and Rajeev Motwani. Approximate ncarest neighbors: towards removing the curse of dimen- sionality. In Symposium on Theory of Computing (STOC), 1998. URL lttps::////// //al. acm. org/ddi/abs///
1145/276698 276876
13

---

Published in Transactions on Machine Learning Research (10/2023)
Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi-supervised learning. In Conference on Computer Vision and Pattern Recognilion (CVPR),
2019. URL http://openaaceess. thecvf. wwtpvvf.ccm/coooo www./oootenttteeeeeoo CVPR_ 2019/htmm//scenn Lttp__aaeeeeaaee_aee
for Der__Dep__aa Stre--emmmnSppprrvseeeeeeee
CVPP__CCP_______ 2019_papes hhmml
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 (TCLR), 2021. URL. https:///penrreviet .ett/Eoruumidd-eecrr...
Lei Jiang and Lei Ju. Fhebench: Benchmarking fully homomorphic encryption schemes, 2022.
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ý, Alcksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Ongü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, Pranccth Vepakomma, Jianyu Wang, Li Xiong, Zhong 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::/ddi.org// /t0p::///ooooor///0...6//0000000
15611/2000000000883
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 Inter- national Conference on Machine Learing (ICML), 2020. URL http://proceedding. mlr ptt.s.//ree//v1//////
karimireddy20a.hr html
Sameh Khamis and Christoph Lampert. Coconut: Co-classification with output space regularization. In British Machine Vision Conference (BMVC), 2014. URL. http://www. bmva wtw.aaa.rrg//mmm//////////prrrre
paper044/index. html
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. URL htttps://ww.... cs. toronto.... www.oto..ooouooeooooo httt:////t/////eeereeeeeeeeeeeee
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Machine Learning and Systems (ML.Sys), 2020. URL https
//proceedings. mlsys. wtggbook//1....pooooooog pdf
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 Patlern Recognition (CVPR),
2022. URL https://doli org/ 10. (0009//VR52288.... 2022. 00991
Yanbin Liu, Juho Lee, Minseop Park, Sachoon 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:://penrrevie net//torumIld-SyyuR...C.
Zewei Long, Liwci 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: //tp::////vvvvve http///awww....a//////////
hrrg/abs/20122 2011203222202222222
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 Artificial
Intelligence and Statistics (AISTATS), 2017. URL http::/proceeedings .ml.
htmll
Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In Symposium on Discrete Algorithms (SODA), 2001.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Jean Ogier du Terrail, Samy-Safwan Ayed, Edwige Cyffers, Felix Grimberg, Chaoyang He, Regis Loeb, Paul Mangold, Tanguy Marchand, Othmane Marfoq, Frum Mushtag, Boris Muzellee, Constantin Philippenko, Santiago Silva, Maria Telezzuk, Shadi Albarqouni, Salman Avestimehr, Aurélien Bellet, Aymeric Dieuleveut, Martin Jaggi, Sai Pranecth Karimireddy, Marco Lorenzi, Giovanni Neglia, Mare Tommasi, and Mathicu Andreux. FLamby: Datasels and benchmarks for cross-silo federated learning in realistic healthcare settings, 2022. URL attps://openreevev net/ http://w...eetorurmmmoooooooooa.
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. Tn International Conference on the Theory and Application of Cryptographic Techniques (EuroCrypt), 1999. URL https: //link. springer com/ wwwttooettttttnnteeeooooe 1000///0000003-----4901-1--1-111 16,4_666111 1df pdf
Congzheng Song, Filip Granqvist, and Kunal Talwar. FLAIR: federated learning annotated image repository.
CoRR, abs abs/ .08699,88,,.888 2022. doi: 10.48850/arxivv22277. .08869.. URL
2207.08869
Mingxing Tan and Quoe Le. EfficientNet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learing (ICMT., 2019. URL https::/procceednngs http:///rooenng............ mlr. press/
v97/tan19a.1 html
Antti Tarvainen and Harri Valpola. Mcan teachers are better role models: Weight-averaged con- sistency targets improve semi-supervised deep learning results. In Conference on Newral Informa- lãon Processing Systems (NewrIPS), 2017. URL htttps:/proceeeing...t (60G022250206GGGTGGG1110T7------
html
Vladimir Vapnik. Estimation of Dependences Based on Empirical Data. Springer, 1982. URL https
//link.sprinng www/booo///ooooooooooooooooooo hwtp:///ooooo/001000000008-33330
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In Conference on Newral Information Processing Systems (NeurIPS), 2016. URL https
wwwpbeedding..nuuiiss..omm httpa///ia.aa//////////////////0 htmml
Binghui Wang, Ang Li, Hai Li, and Yiran Chen. Graphfl: A federated learning framowork for semi--uueeeeii node classification on graphs. CoRR,, abs/2012.04187, 2020. URL http:://aarxi..orr///////2222/.2
Hongwei Wang and Jure Leskovee. Combining graph convolutional neural networks and label propaggtio...... ACM Trans. Inf- Syst., 40(4):73:1-7333 -7::27, 2022. doi: 10.1145/3490478. URL http:pss///ii..or///0....4
3490478
Han Xie, Jing Ma, Ti Xiong, and Carl Yang. Federated graph classification over non-iid graphs. Tn Conference on Neural Information Processing Systems (NewrIPS), pp. 18839 18852, 2021. URL https;
-at.eeeddddc------aaattte html
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu-Ming Yiu. Subgraph federated learn- ing with missing neighbor generation. In Conference on Neural Information Processing Sys- tems (NeurIPS), pp. 6671 6682, 2021a. URI. G4cd66664444447354666060aac wwwp://cttebbstttt.tota Abstract.
Zhengming Zhang, Yaoqing Yang, Zhewei Yao, Yujun Yan, Josoph F. Gonzalez, Kannan Ramchandran, and Michael W. Mahoney. Improving semi-supervised federated learning by reducing the gradient diversity of models. In Internalional Conference on Big Data (Big Data), 2021b. URL BigData52589 2022..22666 96671693
Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Conference on Neural Information Pro- cessing Systems (NeurIPS), 2004. URL https://proceedings.. http://wwwggg....oorr....cp/pppa pdd..
Xiaojin Zhu. Semi-supervised learning with graphs. PhD thesis, Carnegie Mellon University, 2005. URL
https://pages.. wws.w haaaaa.eeeer.eeerrrr////////// tut.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CATDD-02-177,, School of Computer Science, Carnegie Mellon University, 2002. URL
https://mlg. eew.ii..enng.egoo cam ac.
www.:ew................a.a.aaa http:://ww/////////////////////a 100 pdf
16

---

Published in Transactions on Machine Learning Research (10/2023)
A Experimental Details
A.1 XCLP for Prediction
Dataset We use the Fed-ISIC2019 (Ogier du Terrail ct al., 2022) dataset which contains over 20, 000 images of skin lesions. The lask 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 respoctively), 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 new final linear layer and fine-tune the whole network using federated averaging as described in Ogier du Terrail et al. 2022).
for FederateddAvraginng 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 (ISH dimension, k-NN paramcter) are chosen using cross-validation. We use L = 1024 and k == 3. We fix the parameter 0.99.
Hyper-parameters We set all
A.2 XCLP for federated semi- supervisd learning
Datasets We evaluate XCLP on three standard dalasets for multi-class classification: CIFAR-10 (Krizhevsyy 2009), which has 10 classes and is used in previous federated SSL works, as well the more difficult CIFAR-100 (Krizhevsky) 2009) and Mini-ImageNeet (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 == 50,000 and test sets of size 10,000. From the training set, ng examples are labeled and the remaining n n, are unlabeled. For CIFAR-10 we evaluate with nt, 1,000 and 5,000. For CIFAR-100 and Mini- ImtteemteeNett we take ng = 5,000 and 10,000.
Federated Sctup We simulate FL scenario by splitting the training data (labeled and unlabeled) between m clients. m. 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 nt/my are labeled if the client is one of the my which possess labels. We simulate statistical heterogencity among the clients by controlling the number 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 class distribution to each client and clients receive labels according their own distribution.
Following prior work, we use 13-layer CNNs (Trvvainen & Valpola 2017 for CIFAR-10 and 100 and 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.
Networks
We choose dimension, A-NN parameter) or accuracy on a held-out validation set consisting of 10% of the training data (batch size, learning rate).
Hyper-parameters
for all methods based on training progress (LSH
Federated learning parameters We set the number of clients to 100, except for our experiments CIFAR-100 and Mini-ImageNet with nı 5000. In these cases we set m 50 as it is not possible to create an i..dd 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. = 100 and my = 50. On CIFAR-100 and Mini-ImageNNt we set my = m.
The Cli ClientUpdate step corresponds to E epochs of stochastic gradient descent (SGD) of a loss function. We set the number local epochs to E and the loss function is (per sample weighted) cross-entropy loss. The
17

---

Published in Transactions on Machine Learning Research (10/2023)
ServerUpdate step corresponds to averaging the model updates:
ServerUpdate(f0)) for j E P)
Σ JEP
80)
P
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 T = 0.05 when m = 100 and == 0.1 when m = 50. Note that when my m we ensure that the server samples mm,, clients from the labeled portion (and T(m mr.) 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 4CE4 random translations followed by a random horizontal flip. On Mini-Imagell Imagee,,,,,eet, 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 x 10-4, When carrying out SGD in the ClientUpdate we use batches of data B = B2 U Bu where B, is a batch of labeled data and By is a batch of pseudo-labeled (previously unlabeled) data. We set [B,| according to how many labeled samples the client. has available, [Bll = min((5, #labels). We set |Bo| = [Br]- Learning rate for SGD is set according to this batch size. On CIFAR-10, for [Brl| 50 we set the learning rate to 0.1 and for Br, 50 we set the learning rate to 0.3. On CIFAR-100 and Mini- Imageem we always have [Br| 50 and we set the learning rates 0.5 and 1.0 respectively. We docay the learning rate using cosine anncaling 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 similaritics 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 most similar neighbors in the graph, and the label propagation parameter to = 0.99.
B Additional Experiments
B.1 XCLP for Prediction
We include extra experiments to test the performance of XCLP for prediction on an additional dataset. We follow the notation and setup detailed in Section
Dataset We use the FEMNIST Caldas et al. 2018 dataset. FEMNIST a federated dataset for handwritten character recognition, which has 62 classes (digits and lower/uppen case letters). It. has 817,851 samples and we keep the natural partition into 3597 clients based on the writer that wrote cach character. The clients are non-i.idd, as they heterogeneous in the amount of data they possess, the classes they have, well as the data distributions themselves.
We consider a setting where each client possesses partly labeled training data and wishes to infer labels for their own unlabeled new data. We looks at a range of different labeling scenarios based on what fraction, a, of each client's training data is labeled. Furthermore, due to the large number of clients and datapoints in FEMNIST we reduce communication overhead by partitioning the clients into large groups (we 50 groups, each with approximately 700 clients) and run XCLP separately on each groups of clients. Per-client LP remains described in
Experimental Setup
We investigate two different choices for the preprocessing function h. For the first we simply use the identity (i.e. no embedding) and run both per-client LP and XCLP directly on the raw data. For the second we use a linear embodding that we trained over the client data. Specifically, following the low training overhead approach of [.1] we train a two layer linear MLP using Federated Averaging and use the first layer linear embedding as our preprocessing function.
Results Table 6 reports the results obtained when different fractions a of each client's training data are labeled. The left. columns ("identity") give results for the one-shot setting, where no training is required,
18

---

Published in Transactions on Machine Learning Research (10/2023)
Table 6: XCLP for prediction (FEMNIST dataset); Classification accuracy [in %] with two different preprocessing functions (identity and linear embedding) and different fractions of labeled data available (average and standard deviation across three runs).
identity
linear per-client LP
Fraction of labeled data
per-client LP
XCLP
FedAvg
XCLP
Q = 0.1
33.74 + 0.20
49.29 + 0.16
53.09 + 0.19
37.27 0.12
52.39 + 0.30
a = 0.2
44.79 + 0.03
53.93
0.04
57.54 + 0.46
50.89 + 0.11
58.57 0.13
0.5
50.99 = 0.06
59.37 = 0.13
61.07 = 0.49
59.20 0.19
63.46 + 0.11
a = 1.0
51.91 = 0.07
62.35 + 0.07
62.90 = 0.31
59.42 0.11
66.18 + 0.20
and LP is run directly on the client features. The right columns ("linear") illustrate that by embedding the features using a simple linear layer we are able to improve the performance XCLP. In all cases XCLP substantially outperforms per-client LP. The difference is even more noticeable than in 4.1 presumably due to the smaller amount of data present each client.
C Additional Background
C.1 Propagating values along data graph
For graph with vertices and adjacency matrix W E R=* of edge weights, vector of values, R", can be propagated to neighboring vertices by forming = Wy. By repeatedly multiplying with 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 be forgotten. For that, one can uses an extended update rule
2+1 aW2, +
(1)
where a E 10 is a trade-off hyperparameter. For || < 1/a, this process has the closed form expression
Z00 (Id (ld-aW)-'y y.
(2)
as its (t + limit. This can be seen from the fact that Equation is a contraction with &oo as fixed point. In Section 3.1 we make use of this fact together with the observation that Equation 2 can readily be applied vectors-valued data with a matrix Y in place of y. However, the propagation step will preserve normalization, e.g. of the L' norm. When such a property is required, e.g. for the calculation of entropy-based confidence, normalization has to be performed explicitly post-hoc.
C.2 Computing similarity from hashed data
locality-sensitivg hashing (LSH) (Indyk & Motwani 1998 is procedure for hashing real-valued vectors into binary vectors while prescrving their pairwise similarity. Let E Rd be a vector. To encode v into a binary vector b of length L, LSH randomly samples L hyperplanes in Rd. For each hyperplane it checks whether v lies above or below it and sets the ith bit as or accordingly. Formally, b, = (m,a))00 where E Rdd is the normal vector of the ith hyperplane. A key property of LSH is that it approximately preserves cosine-similarity. Concretely, for vectors vi, 02 with LSH encodings b,, b2 (compute with the same projections), one has
(U) ~ cos(TT((bi,b)) b2)/L)
| |o2||
where is the Hamming distance (number of bits that differ) between two binary vectors. The reason is that the probability of b, and by differing at any bit the probability that the i-th sampled hyperplane lies between i1 and 22, which equal to <(v,, 22)/T. By the law of large numbers, the more hyperplanes one samples, the better the approximation quality.
19


Reviews:
[{"review_id": "4c0OF9dYKZ", "reviewer": "Reviewer_2fsr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The problem statement is very nice and clean. It also has some applications in practice.\n- The setting is interesting and one expects it in practice. Also, the prediction accuracy of unlabeled increases as we have access to more data. This is something expected and the paper passes this test.\n- There is enough empirical evidence to support the main claims of the paper.\n\nWeakness:\n- I do not understand any novelty in the paper. The cryptographic techniques used in this paper are pretty basic and the variation of secure sum in itself is not necessarily that exciting to me. \n- The work is more aligned with empirical evaluation. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies a specific problem in the domain of semi-supervised federated learning. They call it {\\em cross-client label propogation} (XCLP). The technique allows them to generate a data graph in a decentralized manner using data from the client at the node of this network. The client contains both labeled and unlabeled data. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I can see that it would be difficult to give a theoretical guarantee for general graphs, but can the authors give some guarantee for special classes? I would suggest the following graphs as the starting point:\n1. Line graph (or ring graph). Perhaps the most basic one. \n2. Any d-regular graph.\n3. Small cluster graph with each cluster highly connected. Most general graphs can be decomposed in the form of such clusters with very few edges between the nodes in two different clusters. It is known as sparse-dense decomposition (SDD).\n4. Graph with high conductance. I would expect there would be some relationship between their algorithm and the expansion of the graph. \n\nI do not see many other applications of the subroutines that the author proposed. This definitely can be my lack of understanding. Can the authors provide more motivation where these subroutines can be used? Currently, these subroutines seem more like a heuristic that can be used only to solve this problem. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jtmUhwyMul", "reviewer": "Reviewer_8NrT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The major contribution of work is quite significant to the federated community and semi-supervised learning community. Because it proposes a novel distributed label propagation paradigm under the federated learning context. It will be beneficial to researchers from both communities.\n\n2. The proposed method is well-motivated with clear logics. The main challenge of extending label propagation algorithm is how to construct a similarity graph without any data leakage and how to do label inference without privacy concerns. The proposed method solves them nicely with strong motivations and reasonable techniques. For the graph construction, we do not compute the cos similarity directly on the data features from each client but on top the  Hamming matrix of LSH projection. Similarly, we do not do label inference directly on the whole similarity matrix in the server, but only distributes the corresponding sub-matrix to each client.\n\n3. The writing is clear and easy to understand in general with necessary annotations.\n\n\nWeaknesses:\n1. The work is not quite theoretically sound. The reviewer does like the proposed method a lot, but it would be more interesting if the authors can provide some theoretical analysis of the proposed method. In fact, there are several potential aspects of doing so. For example, when compared to the classic centralized way of graph construction, how different would be the graph generated by the proposed method in terms of some distance metric? Are there any rigorous privacy guarantee about the two proposed secure protocols and will the performance of the label propagation be degraded compared to the naive version without privacy considerations?\n\n2. Some more recent federated semi-supervised learning models should be added in Section 4.2. The current baselines are a bit of dated. In fact there are several new baselines[1][2] related to federated semi-supervised learning.\n\n[1] SemiFL: Semi-Supervised Federated Learning for Unlabeled Clients with Alternate Training. In NeurIPS 2022.\n\n[2] Towards Unbiased Training in Federated Open-world Semi-supervised Learning. In ICML 2023.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new method for transductive and semi-supervised federated learning called Cross-Client Label Propagation (XCLP). XCLP estimates a data graph from multiple clients' data and computes labels for unlabeled data by propagating label information across the graph. To maintain privacy, XCLP uses two cryptographically secure protocols: secure Hamming distance computation and secure summation.\n\nThe paper makes several contributions to the field of federated learning:\n1. A new federated version of label propagation algorithm is proposed. XCLP allows for multiple clients to jointly infer labels from a cross-client data graph without them having to share their data.\n2. Two new cryptographically secure protocols are used in XCLP: secure Hamming distance computation and secure summation. These protocols are used to maintain privacy in XCLP, as they avoid clients having to share their data with anyone.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The reviewer does like this work and enjoy reading the paper even though there are some potential improvements about it. The proposed adjustments are listed as follows. The reviewer knows these changes may need much work and some suggestions are beyond the scope of this paper. So it is ok if the authors find it too hard to make these changes. The reviewer recommends for the acceptance of this paper based on its current status, but these changes could make this work even better. **All the following changes are not critical but could strengthen the work.** More details can be found in Strengths And Weaknesses section.\n\n1. More theoretical analysis on the proposed method on its accuracy guarantee compared to the original naive version. \n2. More recent baselines comparison for the federated semi-supervised learning case setting.", "broader_impact_concerns": "The reviewer does not find any concerns related to the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VW2Dm3UP2H", "reviewer": "Reviewer_Dy9w", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n+ Very interesting approach for the computation of the joint graph for propagating the information of the labels. Section 3 is well structured and explained and includes the analysis of different properties of the algorithm, such as efficacy, privacy, efficiency and robustness. \n+ Interesting use of the two secure protocols for keeping the privacy of the clients’ data for propagating the labels.  \n+ Experimental evaluation seems convincing and the uses cases illustrate well the capabilities of XCLP and its benefits compared to other state-of-the-art methods, including cases like semi-supervised learning and label inference in one-shot (although there are some improvements that can be addressed in the experiments).\n\nWeaknesses: \n- In the experiments, for label inference (Section 4.1), only one dataset is considered in the experiments (Fed-ISIC 2019). Although the analysis of this dataset is complete and includes the ablation study in Table 3, it would be necessary to confirm the results with at least another dataset. \n- The discussion of the results on semi-supervised learning in Section 4.2 is too brief and shallow (just one small paragraph).    \n- The computational complexity of the method is not analyzed in the experiments. For example, it would be interesting to compare the computational cost of per-client LP and XCLP in Section 4.1. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel method for transductive and semi-supervised federated learning to estimate the labels of unlabeled data points across all clients without sharing the data. For this, the proposed method, Cross Client Label Propagation (XCLP), estimates a data graph jointly from the clients’ data and computes the labels by propagating label information across the graph. Additionally, XCLP uses two cryptographically secure protocols: secure Hamming distance and secure summation. \nThe authors show the benefits of their proposed approach in different federated learning scenarios, including one-shot label prediction and semi-supervised learning. On one side, the results show that the computation of the graph using multiple clients produces significant improvements with respect to strategies based on the propagation of labels individually for each client. In semi-supervised federated learning, XCLP outperforms other state-of-the-art methods. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "+ Evaluation of XCLP for label inference in at least another dataset. \n+ Extend the discussion and analysis of the results in Section 4.2. \n+ Empirical analysis of the computational complexity (XCLP vs per-client LP). \n", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an interesting application of cryptographic primitives to a federated learning problem.
As noted by some reviewers, the techniques are somewhat straightforward, and might not be broadly applicable to other tasks.
The proposes approach is also limited to cryptographic data confidentiality, and doesn't provide stronger notions of privacy such as differential privacy.
Nevertheless the reviewers agreed this is an interesting direction worth accepting.
Decision: Accept (poster)