OmniFC: Rethinking Federated Clustering via Lossless and Secure Distance Reconstruction
Authors: Jie Yan
Jing Liu
Zhong-Yuan Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Secure Federated Clustering
Non-IID Data
Lagrange Coded Computing
Distance Reconstruction
Primary area: general_machine_learning

Abstract: Federated clustering (FC) aims to discover global cluster structures across decentralized clients without sharing raw data, making privacy preservation a fundamental requirement. There are two critical challenges: (1) privacy leakage during collaboration, and (2) robustness degradation due to aggregation of proxy information from non-independent and identically distributed (Non-IID) local data, leading to inaccurate or inconsistent global clustering. Existing solutions typically rely on model-specific local proxies, which are sensitive to data heterogeneity and inherit inductive biases from their centralized counterparts, thus limiting robustness and generality. We propose Omni Federated Clustering (OmniFC), a unified and model-agnostic framework. Leveraging Lagrange coded computing, our method enables clients to share only encoded data, allowing exact reconstruction of the global distance matrix—a fundamental representation of sample relationships—without leaking private information, even under client collusion. This construction is naturally resilient to Non-IID data distributions. This approach decouples FC from model-specific proxies, providing a unified extension mechanism applicable to diverse centralized clustering methods. Theoretical analysis confirms both reconstruction fidelity and privacy guarantees, while comprehensive experiments demonstrate OmniFC's superior robustness, effectiveness, and generality across various benchmarks compared to state-of-the-art methods. Code will be released.

OmniFC: Rethinking Federated Clustering via Lossless and Secure Distance Reconstruction
Jie Yan
Jing Liu
Ghong-Yuan Zhang"
Central University of Finance and Economics
jicya@emaii.cuf..cd.u.cm liu_jin0623ee 163.com, zhyuanzh gmail.com
Abstract
Federated clustering (FC) aims to discover global cluster structures across decentral- ized clients without sharing raw data, making privacy preservation a fundamental requirement. There are two critical challenges: (1) privacy leakage during collab- oration, and (2) robustness degradation due to aggregation of proxy information from -on-independent and identically distributed (Non-IID) local data, leading inaccurate or inconsistent global clustering. Existing solutions typically rely on model-specific local proxies, which are sensitive to data heterogeneity and inherit inductive biases from their centralized counterparts, thus limiting robustness and generality. We propose Omni Federated Clustering (OmniFC), a unified and model- agnostic framework. Leveraging Lagrange coded computing, our method enables clients to share only encoded data, allowing exact reconstruction of the global distance matrix-a fundamental representation of sample relationships-widde leaking private information, even under client collusion. This construction is nat- urally resilient to Non-IID data distributions. This approach decouples FC from model-specific proxies, providing a unified extension mechanism applicable to diverse centralized clustering methods. Theoretical analysis confirms both re- construction fidelity and privacy guarantees, while comprehensive experiments demonstrate OmniFC's superior robustness, effectiveness, and generality across various benchmarks compared to state-of-the-an methods. Code will be released.
Introduction
Traditional clustering methods presuppose centralized access the entire dataset, enabling the construction of global structures such as cluster centroids or kernel matrices. However, federated settings characterized by data fragmentation across clients and privacy constraints, this assumption breaks down, precluding direct application.
To overcome this, federated clustering (FC) 1 has emerged, enabling clients to collaboratively group data without sharing samples, and has found applications in client selection and exploratory data analysis. There are two fundamental challenges: (1) privacy leakage during collaboration, and (2) robustness degradation under aon-independen and identically distributed (Non-IID) data. Existing
"Correspondigg author.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

0.65
Non-iiO (moderate)
0.60
Non IID (high)
0.55
0.50
Kappa
0.45
0.40
0.30
0.25
k.FED
MUFC
OmniFC.KM XM
FFCM
OmniFC-FCh
FedSC
OmniFC-SC
FedMAvg
Omnif C-NMF
Figure 1: Robustness to heterogeneity. We employ COIL-100 and 100 clients to compare the proposed OmniFC with the federated extensions of centralized clustering methods [3 6 77 Compared to existing one-to-one extensions, OmniFC not only unifies the extension of centralized clustering methods but also achieves superior robustness and effectiveness.
FC methods approximate global structures by aggregating model-specific local proxies: federated k-means (KM) and fuzzy c-means (FCM) aggregate local cluster centroids [ 2
federated spectral clustering (SC) (6) reconstructs the global kernel matrix from local low-rank factors, and federated non-negative matrix factorization (NMF) aggregates local basis matrices. These proxies, however, are computed from biased client-specific datasets, fail to reliably capture global structures, leading to degraded robustness and performance (Fig. D Moreover, such methods are tightly bound to specific centralized clustering methods, inheriting restrictive inductive biases-e.g. e.g., data compactness in KM X and FCM 9 data connectivity SC [00, and low-rank representation in NMF 11 thereby confining their performance to assumption-complian data and limiting their generality.
This work addresses both limitations through unifying perspective: reconstructing the global pairwise distance matrix, which offers model-agnostic and fundamental representation of sample relationships, naturally resilient the Non-IID problem. The key challenge. however, lies in securely computing this matrix without exposing private data. To this end, we propose Omni Federated Clus- tering (OmniFC),, a novel framework that facilitates a unified extension from centralized clustering to FC through lossless and secure distance reconstruction. OmniFC comprises three main steps: local Lagrange-encoded sharing, global distance reconstruction, and cluster assignment. Each client initially encrypts its local data using Lagrange coded computing [1], shares the encoded data with peers for pairwise distance computation, and subsequently transmits the resulting distances to the central server for constructing the global distance matrix. Finally, the global distance matrix can serve input centralized clustering methods for performing cluster assignment. Fig. I demonstrates the superiority OmniFC. With respect to distance reconstruction, the proposed OmniFC exhibits two salient features: 1) Efficacy. Both theoretical and empirical analyses consistently demonstrate the capability for lossless reconstruction and robustness to the Non-IID problem. Benefiting from this, the proposed OmniFC achieves lossless federated extensions for pairwise- pairwise-distance-eee distance-dependeer methods (e.g., SC) and enhances federated extensions for methods (e.g.. KM) without explicit dependence on pairwise distances. 2) Security. Theoretical analysis demonstrates that the privacy of local data is preserved during data sharing, as the encoded data prevents the inference of private information even under client collusion. In summary, contributions are threefold:

---

1) We propose OmniFC, a novel framework that facilitates a unified extension from centralized clustering to FC through lossless and secure distance reconstruction.
2) We establish theoretical assurances regarding the efficacy and security of distance reconstruction.
3) Experimental results show that OmniFC outperforms SOTA methods on various benchmarks.
Related Work
Centralized Clustering. Traditional centralized clustering aggregates client-held local data a central server for grouping, with methods making different assumptions- such as compactness [17 and low-rank representation 19 of the data distribution to adapt to diverse datasets. However, these methods may become
g
13
connectivity IO 14], density 11 16
hierarchy
inapplicable due privacy constraints that prevent the centralization of client data.
Federated Clustering (FC). Unlike centralized clustering, which requires collecting raw client data for model training, FC collects local proxies instead, thus strengthening user privacy protection. To handle this, several recent works have shifted from sharing local private data exchanging local cluster centroids 2 5 local basis matrices 7 or synthetic data [0]. Although these methods show promise, these methods either suffer from performance degradation caused by the Non-IID problem or achieve gains at the expense of privacy 220
Secure FC. Secure FC leverages advanced peeeacypreseeving techniques sechiques--icllddnng diffcrential privacy 211, machine unlearning [22), and Lagrange coded computing -t
[ concurrently improve clustering efficacy and fortify data confidentiality. Existing methods typically focus on the effective and secure construction of either global cluster centroids for k-means 23
global Although promising, these methods remain limited by
25 26
kernel matrix for spectral clustering the Non-IID problem or fail to offer a model-agnostic solution. Moreover, they inherently retain assumptions succcoonnssuuhhheee as data compactness g 13 and connectivity
[10 14 from their centralized counterparts, limiting their effectiveness to compliant datasets and thereby reducing their practical applicability.
The most closely related work is SecFC which also leverages Lagrange coded computing to improve clustering accuracy while preserving data confidentiality. comparison, the proposed OmniFC exhibits the following distinctive characteristics: 1) Generality. As federated variant of k-means (KM), SecFC naturally inherits KM's 's assumption of data compactness, limiting their effectiveness KM-friendly datasets. In contrast, the proposed unified and model-agnostic framework OMniFC accommodates diverse datasets by extending beyond KM encompass alternatives such as spectral clustering and DBSCAN. 2) One-shot communication scheme. To obtain more accurate cluster centroids, SecFC requires multiple rounds of communication between the clients and the server. However, multi-round training is unfeasible in some scenarios, like model markets, where users can solely purchase pre-trate pre-trained models 27 In contrast, the proposed OmniFC, requiring merely one communication round, exhibits enhanced applicability such scenarios.
3 Omni Federated Clustering (OmniFC)
This section begins with an overview of the problem definition and the OmniFFC framework, followed by a detailed description of OmniFC, and concludes with its privacy analysis and complexity analysis.

---

Local Datasets
Global Encoded Datasets
1
X2
Za
Global Distance Matrix
Z
Centralized Clustering Method
Local Lagrange-eneoded Sharing
Global Distance Reconstruction
Cluster Assignment
Figure 2: An overview of the proposed OmniFC. The architecture comprises three main steps: 1) Local Lagrange-Encoder Sharing. Each client E [m]) encodes its private data using Lagrange polynomial interpolation and distributes the encoded data to all peers, enabling each elient to construct a global encoded dataset while preserving data privacy. 2) Global Distance Reconstruction. Each client computes pairwise distances within its global encoded dataset and transmits the results to the central server, which leverages them to reconstruct the global distance matrix. 3) Cluster Assignment. A centralized clustering method (c.g., k-means) is applied the global distance matrix to produce the final clustering result n..
3.1 Overview
Problem Definition. Consider real world dataset E Raxd comprising n d-dimensional
samples {a,}2_.> which are distributed among m clients, i.e., x Xj. FC aims to partition X into & clusters with high intra-cluster similarity and low inter-cluster similarity while retaining X; [m] (1, ... m)) locally. A more detailed summary of notations is presented in Table of the appendix.
Framework Overview. As shown in Fig. OmniFC comprises three main steps: local Lagrange- encoded sharing, global distance reconstruction, and cluster assignment. Each client j (j E [m]) initially encrypts its local data using Lagrange coded computing (LCC) [12, shares the encoded data with peers for pairwise distance computation, and subsequently transmits the resulting distances to the central server for constructing the global distance matrix. Finally, the global distance matrix can serve as input to centralized clustering methods for performing cluster assignment.
3.2 OmniFC
Local Lagrange-encoded Sharing. First, each sample æ; E X (i [m]) fr))-regardless of the client which it is distributed to to-is independently transformed from the real domain Rdd the finite field Ed to ensure numerical stability in secure computation [12, with denoting a prime. The
transformation is defined as:
T round(29 xx)) p- (sign(x.)) sign(x,)
(I)
where E regulates the quantization loss. round(-) and sign(-) represent element-wise rounding and sign functions, respectively. Rounding discretizes continuous values to ensure finite field
compatibility, while the sign function facilitates correct mapping of negative values 28 We denote
the transformed form of X R as X Raad
Then, each sample ã; E X (i E [n]) is independently encoded via Lagrange polynomial interpolation by the client (Fig. 3), enabling secret sharing among clients. Specifically, ã; F is partitioned

---

$
112
..
Z1,1
$ 1,7
2122
X
fx
1
i11+2
Zi
1
Data Segmentation
LagrangeInterpoaatton
Lagrange Interpolation (Equation (2)
Lagrange Encoding (Equation (3)
Figure 3: An illustration of the Lagrange encoding. Each sample ã; (i E [n]) is initially divided into 1 segments {st,0)/=1- Incorporating additional noises {81,4+))==1- Lagrange interpolation then conducted as per Equation 2 yield f&. (a). Subsequently, the encoded representations {zt.) 1 of ã; are computed according to Equation 3
and combined with random noises to construct a polynomial that serves to encode G.. The noises are introduced to ensure privacy protection against potential client collusion 12 Assuming that d is divisible by 1, the client holds data segments 8i,0 F (o E [4]), and samples additional noises s; (o E [t]) uniformly from
into segments {Stooo=1 i.., ã; | ......... "T
F Based on the segments (st,0)=s 1++ the Lagrange interpolation polynomial fa," F, - F of
degree + I can be constructed as follows:
14t
fa, (a)
Σ o=1
8
a ag!
1+t where {a.)o=1 denotes a set of + t. distinet hyperparameters from Fp. pre-specified through agreement among all clients and the central server. Particularly, each data segment $i,0 (o E [I]) can be recovered by setting (ko, i.e., fa, (ox.) 8i.o. Beyond the {ox))/t1 / employed in constructing the polynomial fa. all clients and the central server also pre-select distinct public hyperparameters
{,,),T1 for encoding, where B, F, and {a n {B)) 0. Based on {B,}ー= the client
encodes its local data T; into m distinct representations {zi,j 1 for secret sharing, with each representation
Zi.j f (3,
delivered the j-th client.
As these operations are defined per sample, they are universally applicable local data across all clients. Hence, each client j (j [m]) will possess global encoded dataset Z, F#x correspond- ing X E paxd where Z 1 #2.j1"'' Zn.j) [ (3,). (3₂), fa. (8,))=
Global Distance Reconstruction. For each client j (j E [m]), pairwise distances between all encoded representations Zi,j and æy. in Zj (i, E [n]) are calculated and subsequently sent to central server for constructing the global distance matrix. Specifically, the pairwise distance between Zi,j and j can be calculated as:
dis(z z4 || zr.
(4)
5

---

Based on the m distances {dis( g provided by the clients, the server can accurately recover the pairwise distance between the corresponding samples क; and öy, demonstrated in Theorem I
Theorem 1. Let f (3): + Fp denote the Lagrange interpolation polynomial interpolated from the set {B3, dis((i,))))))) Zigs 2v ,))
m
3 3- By II j' 3,- By'
f fa. (3)
Σ di
(5)
where Zijj and zz. denote the encoded representations of arbitrary samples i. and αy distributed among clients. When 2 21 + 2t 1, the distance dis(ā,, Zz) can be precisely recovered:
dis( ã4)
Σ fa fe. (ao):
(6)
irrespective of how data distributed among clients.
Remark 1. The condition m 2 21 + 2t - imposes minimal practical constraint, given that m is predefined by the system while 1 and t are tunable hyperparameters. This flexibility allows the condition to be met easily, ensuring the theorem's 's practical applicability and highlighting its relevance real-world implementations.
Then, by converting dis(ã;; 2x) from the finite field Fp back to the real domain R, the server recovers:
{
20 dis( ...))
if 0 S dis Tx)) P
dis( xv)
24 (dis ..) p) if
p-1 2 < dis(ă; Ex) <p
Based on the recovered distances, we denote the global distance matrix E R with each entry defined as Di = dis(x, xy) for i, E [n]]
Cluster Assignment. With the recovered global distance matrix D E Rax", the server can directly perform clustering without requiring any modification to existing centralized clustering methods. This characteristic demonstrates the simplicity and flexibility of the proposed OmniFC framework.
Specifically, pairiise-iistaneeddeeeddnn centralized clustering methods- spectral clustering (SC) 10 DBSCAN [15. hierarchical clustering (HC) 17. and k-medoids (KMed) 29 can
seamlessly utilize D for model training, owing to their intrinsic reliance on pairwise sample distances during the clustering process. For methods that do not explicitly depend pairwise relation- huips-Such k-means (KM) [8) fuzzy e-means (FCM) 9.. and nonnegative matrix factorization (NMF) [1 the server employs D as a proxy for the raw features E Raxd perform clustering. ie., the distance values become the new features of the samples. This allows these algorithms to operate as if on centralized data, while implicitly leveraging the global structure encoded in D. These federated extensions of centralized methods built upon OmniFC denoted OmniFC-SC, OmniFC-DBSCAN, OmniFC-HC, OmniFC-KMed, OmniFC-KM, OmniFC-FCM, and OmniFC- NMF, respectively. Algorithm g in the appendix delincates the pscudocode of OmniFC.
3.3 Privacy Analysis
OmniFC adopts LCC encryption enhance clustering performance while fortifying data privacy. Although LCC enables clients to obtain global awareness via inter-client sharing of Lagrange-encoded data, it also poses emerging privacy threats, as colluding clients may leverage the shared information to infer others' private data [12]. Hence, evaluating OmniFC's resistance to client collusion is

---

essential for delineating its practical applicability. Theorem provides formal guarantee that each data point R; maintains information-theome -heooretccc security in the presence of up to colluding clients, thereby affirmingg the practical applicability of OmniFC.
Theorem 2. Given the number of noises t, a t-private OmniFC is achievable if m 2 21 - 2t - 1, ie..
= =0,
(8)
where [(:-) denotes the mutual information ciftomaationnunccioon C [ra] and [C] S L.
Remark 2. Mutual information essentially measures how much one piece of information reveals about anether-when equals zero, it means one reveals nothing about the other, thereby preserving privacy. Furthermore, mutual information is not an isolated crivacy-rreserving metric; it can be compared with other privacy measures (such as differential privacy) within a unified framework [30].
Remark 3. The condition for achieving t- t-private security in Theorem 2 coincides with that for exact distance reconstruction in Theorem i.e., m 2 + 1. Consequently, by adhering to this constraint, we can increase the number of noises to strengthen privacy protection without compromising the precision of distance reconstruction.
3.4 Complexity Analysis
Recall that reconstructing the global pairwise distance matrix involves two main stages: local encoding and distance computation on the client side, followed by server-side decoding to recover the global matrix. For each client j, fast polynomial interpolation and evaluation [31] yield an encoding
complexity of ( dnym log" )). while distance computation on the encoded data incurs complexity of
(( dn leading to an overall complexity of O d(n" log" m)) n2 is the number of samples held by client j. For the server side, the decoding operation has complexity of On + t) log t)).
The analysis indicates that, on the client side, increasing the number of data segments / substantially reduces computational complexity, thereby facilitating the caleulation of pairwise distances in d-dimensional space, where the feature count (4) involved pairwise comparisons decreases as 2 rises. On the server side, however, a larger results in greater computational complexity. As for the impact of I on the overall complexity of the reconstruction process, a theoretical analysis is challenging due to the differing hyperparameters involved both sides.
To handle this, presented the runtime for reconstructing the global pairwise distance matrix across varying data scales on 10x 73k. As shown in Table 4 one can observe that: Although the runtime exhibits a marked increase as n grows, enhancing the number of data segments can considerably boost computational efficiency when is fixed. For instance, processing 70k samples takes 4352 seconds with 8, demonstrating that method remains computationally feasible on large-scale datasets. Importantly, as long the constraints m 2(1 + 1) + holds, increasing / have no effect on the reconstruction effectiveness of the global pairwise distance matrix (Theorem and Fig.
Experiments
4.1 Experimental Setup
Datasets and Evaluation Criteria. The proposed OmniFC is assessed using seven benchmark datasets across tabular, visual, temporal, and genomic domains, including Iris (32 MNIST (3) Fashion-MNIS (34, COIL-20 [35), COIL-100 (35), Pendigits (36), and 10x_ [37]. The cho- sen datasets encompass diverse modalities, dimensionalities, and cluster patterns, facilitating a comprehensive evaluation of the method's generalizability in practical scenarios.
7

---

MNIST
COIL-20
10x_73k
Figure 4: Comparison between the ground-truth (top row) and reconstructed (bottom row) pairwise distance matrices. The visual consistency indicates that the proposed OmniFC faithfully recovers the inter-sample similarity.
The evaluation criteria encompass Normalized Mutual Information (NMI) 38 and Kappa [39], with higher scores indicating improved clustering performance. Despite the widespread use of NMI, increasing evidence suggests may be misleading, whereas Kappa is more reliable [39 20
40]
Hence, our analysis grounded Kappa-based results, with NMI-based outcomes relegated to appendix for reference. Details of datasets and evaluation criteria are provided in Appendix C.1
Baselines. OmniFC is evaluated in comparison with the federated extensions of several centralized clustering methods, including KM-based (k-FED (1. MUFC 33, FCM-based (FFCM (2), SC- based (FedSC [6), and NMF-based (FedMAvg methods. To contextualize the performance of federated clustering against its centralized counterpart, we also present results of vanilla KM, FCM, SC, and NMF under centralized settings, referred to KMM XMM_entral, NMF MMF__cntral, respectively.
SC_central, and
we simulate diverse federated settings by partitioning the real-world dataset into k* subsets- each representing a client-and and adjusting the non-llI) level where i* denotes the number of true clusters. Specifically, for each client, a fraction of its data is sampled from single cluster, while the remaining P portion is drawn uniformly across all clusters. As such, p recovers the IID setting, whereas p induces a maximally skewed distribution, where each client's data is fully concentrated within a single cluster. Since OmniFC immune to the Non-IID degree, the Non-IID level p is indicated solely during comparisons with the existing FC baselines and omitted elsewhere.
Federated Settings. Following Ref. 41
20
4.2 Experimental Results
Our experiments center three key aspects: 1) the comparative advantage of OmniFC over existing approaches; 2) the generality of OmniFC in extending centralized clustering methods; and 3) the sensitivity of OmniFC to hyperparameters. Implementation details are provided in Appendix C.2 and supplementary experimental results are presented Appendix D
Efficacy Analysis. To comprehensively validate the efficacy of OmniFC, we simulate five scenarios per dataset: IID (p 0), mildly non- non-IID 0.25). moderately non-lID 0.5), highly non-III (p 0.75), and fully non-IID (p 1). As shown in Table T the proposed OmniFC enables superior federated extensions for both pairwise-dise pairwise-distancc-dpeere distance-dependent SC and methods that do not explicitly depend on pairwise relationships, such as KM, FCM, and NMF, For SC, our extended results attain centralized-level clustering fidelity while remaining robust to diverse Non- IID conditions, owing to

---

Table I: Kappa of clustering methods in different federated scenarios. For each comparison, the best result is highlighted in boldface.
SC-hased methods
KM-based methods
FCM-based methods
NMF-based methods
Dataset
Se_crnl FedSC Ours KM_central k-FED MUFC
Ours FCM_central FFCM Ours NMF central FedMAvg Ours
0.00
0.95
0,95
0.58
0.83
0.95
0.96
0.95
0.50
0,95
0.25
0.95
0.95
0.93
0.95
0.49
0.95
Tris
0.50
0.95
0.85
0.95
0.95
0.93
0.79
0.95
0.95
0.93
0.95
0.57
0.50
0.95
0.75
0.93
0,95
0.5
0.81
0.95
0.96
0.95
0.50
0.95
0,95
0.95
0.97
0.50
0.96
0.55
0.42
0.38
0.25
0.54
0.55
0.45
0.50
0.12
0.52
0.41
0.44
0.38
MNIST
0.50
0.55
0.54
0,55
0.47
0.29
0.46
0.12
0.50
0,53
0:41
0.46
0.39
0.38
0.32
0.47
0.42
0.38
1.00
0.38
0.55
0.47
0.43
0.42
0.48
0.41
0.46
0.38
0.00
0.54
0.53
0.46
0.43
0.51
0.51
0.50
0.46
0.49
0.25
0.52
0.53
0.40
0.51
0.47
0.46
0.49
Hashion-MNIS
0.50
0.53
0.54
0.53
0.50
0.48
0.50
0.51
0.53
0.43
0.50
0.51
0.46
0.49
0.75
0.47
0.53
0.45
0.45
0.51
0.50
0.50
0.46
0.49
1.00
0.38
0.53
0.32
0.50
0.51
0.46
0.50
0.46
0.49
0.00
0.68
0.63
0,12
0.58
0.64
0.51
0.50
0.61
0.25
0.68
0.63
0.46
0.51
0.64
0.47
0.59
0.51
0.61
COII-20
0.50
0.61
0.73
0.63
0.64
0.42
0.57
0.64
0.59
0,51
0.59
0.56
0.44
0.61
0.75
0.63
0.64
0.55
1.00
0.29
0.63
0.46
0.56
0.64
0.59
0.59
0.52
0.61
0.00
0.34
0.54
0.48
0.49
0.56
0.37
0.53
0.39
0.50
0.25
0.32
0.54
0.45
0.50
0.56
0.38
0.53
0.38
0,50
COIL-100
0.50
0.54
0.32
0.54
0.41
0.48
0.56
0.49
0.53
0.39
0.50
0.75
0.29
0.54
0.41
0.50
0.56
0,48
0.53
0.39
0.50
1.00
0.27
0.54
0.43
0.52
0.56
0.51
0.53
0.38
0,50
0.00
0.74
0.72
0.59
0.59
0.62
0.62
0.25
0.73
0.72
0.46
0.58
0.62
0.61
0.66
0.33
0.72
Pendigits
0.50
0.72
0.72
0.72
0.61
0.48
0.60
0.62
0.66
0.53
0.66
0.45
0.33
0.72
0.75
0.60
0.72
0.33
0.49
0.62
0.49
0.66
0.33
0.72
1.00
0.52
0.72
0.53
0.62
0.62
0.70
0.66
0.33
0.72
0.00
0.52
0.89
0.40
0.63
0.56
0,46
0.55
0.49
0.82
0,25
0.52
0.89
0.55
0.63
0.56
0.47
0.55
0.49
0,82
10k_73k
0.50
0.89
0.52
0.89
0.57
0.62
0.56
0.49
0.75
0.54
0.89
0.37
0.65
0.56
0.64
0.55
0.50
0.82
1.00
0.24
0.89
0.30
0.79
0.56
0.64
0.55
0.50
0,82
count
27
lossless pairwise distance reconstruction, which remains unaffected by non-IlI) severity (see Theorem I
aan Figure 4 For centralized methods not explicitly reliant on pairwise relationships, our extended results generally match- and occasionally exceed-thee performance under centralized settings, indicating that the global distance matrix D can serve as an effective surrogate for the raw feature matrix X to perform clustering.
Generality Analysis. To assess OmniFC's 's generalizability in extending centralized clustering methods, we integrate it with three additional methods (KMed, DBSCAN, and HC) that have been well-studied in centralized contexts but remain underexplored in federated settings. Like SC, all three methods perform clustering based on inter-sample pairwise distances. Hence, by utilizing OmniFC's lossless distance reconstruction, these three methods can be effortleslly integrated into the OmniFC framework to facilitate lossless federated extensions, shown in Table 2.

---

Table 2: Kappa of different clustering methods.
KMed-based methods
DBSCAN-based methods
HC-based methods
Dataset
Central
Ours
Central
Ours
Central
Ours
Iris
0.94
0.94
0.50
0.50
0.94
0.95
MNIST
0.31
0.30
0.21
0.21
0.41
0.41
0.42
0.42
0.14
0.14
0.45
0.45
COIL-20
0.41
0.42
0.58
0.58
0.45
0.45
COIL-100
0.34
0.34
0.37
0.37
0.48
0.48
Pendigits
0.44
0.45
0.48
0.48
0.57
0.57
10x_73k 73k
0.30
0.30
0.01
0.01
0.28
0.28
0,0005
0.0002
0.0002
0.0002
(000))))
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0/000S
171
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
10
0.0002
0. 0000
0.0002
0.0002
0.0002
100
0.0002
0.0002 0. 0.00002
0.0002
0.0002
100
0.0002
0. 000000
0.0002
0.0002
0.0002
20
2
14
1000000
Figure 5: Hyperparameter sensitivity of the global distance matrix reconstruction loss. The gray-highlighted region denotes hyperparameter settings that violate the condition m 2 2/ + 2t 1 in Theorem [ thus precluding distance reconstruction.
Sensitivity Analysis. To assess the hyperparameter sensitivity of OmniFC, measure the global distance matrix reconstruction loss-defined as the root-mean-square deviation (RMSE) between the ground-truth and reconstructed pairwise distance matrices-ane across varying number of clients (m), noises (t), and segments (l). In fact, theoretical guarantee for this has already been provided in Theorem [ long as the condition 2 21 2/ holds, OmniFC is capable of achieving accurate distance reconstruction. This theoretical result is further substantiated by empirical evidence presented in Fig.
5
Conclusion
This work introduces OmniFC, unified and model-agnostic framework via lossless and secure distance reconstruction. Unlike existing methods that rely on model-specific proxies and suffer from data heterogeneity, OmniFC adopts a distance-basse perspective that is decoupled from specific clustering models. Benefit from this, theoretical and empirical results show that this framework improves robustness under non-IID settings and supports the extension of wide range of centralized clustering algorithms FC.
Beyond FC, the proposed framework may open broader opportunities across federated learning. In particular, the reconstructed global distance matrix can naturally function as a global affinity graph, offering new possibilities for advancing federated graph learning and other domains where capturing global sample relationships is fundamental.
10

---

Acknowledgements
The authors are grateful to Yong Wang and the three anonymous reviewers for their constructive feedback on an earlier version of this manuscript. Jie Yan is supported by the Strategic Priority Research Program of Chinese Academy of Sciences, Grant No. XDB 1350000.0..
References
[1] Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. In International conference on machine learning, pages 2611-2620. PMLR, 2021.
[2] Morris Stallmann and Anna Wilbik. Towards federated clustering: A federated fuzzy e-means algorithm (ffem). arXiv preprint arXiv:2201.07316 2022.
[3] Chao Pan, Jin Sima, Saurav Prakash, Vishal Rana, and Olgica Milenkovic. Machine unlearning of federated clusters. In The Eleventh International Conference on Learning Representations, 2023.
[4] Jinxuan Xu, Hong- You Chen, Wei-Lun Chao, and Yuqian Zhang. Jigsaw game: Federated clustering, arXiv preprint arXiv:2407.12764, 2024.
[5] Kun Yang, Mohammad Mohammadi Amiri, and Sanjeev Kulkarni. Greedy centroid ini- tialization for federated k-means. Knowledge and Information Systems, 66()):3393-3425, 2024.
[6] Dong Qiao, Chris Ding, and Jicong Fan. Federated spectral clustering via secure similarity reconstruction. Advances in Neural Information Processing Systems, 36:58520-58555, 2023.
[7] Shuai Wang and Tsung-Hui Chang. Federated matrix factorization: Algorithm design and application to data clustering, IEEE Transactions on Signal Processing, 70:1625-1640, 1640, 2022.
[8] James MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statisticcs, volume 5, pages 281-298. University of California press, 1967.
[9] James C Bezdek, Robert Ehrlich, and William Full. Fem: The fuzzy c-means clustering algorithm. Computers & geosciences, 10(2-3):111-233, 1984.
[10] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm.
Advances in neural information processing systems, 14, 2001.
[11) Daniel Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. Advances in neural information processing systems, 13, 2000.
[12] Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi. and Salman A Avestimehr. Lagrange coded computing: Optimal design for resiliency, security, and privacy. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1215-1225. PMLR, 2019.
[13] Abiodun M Ikotun, Absalom E Ezugwu, Laith Abualigah, Belal Abuhaija, and Jia Heming. K-means clustering algorithms: comprehensive review, variants analysis, and advances the era of big data. Information Sciences, 622:178-2111 2023.
[14] Ling Ding, Chao Li, Di Jin, and Shifei Ding. Survey of spectral clustering based on graph theory. Pattern Recognition, page L10366, 2024.

---

[15] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pages 221-231, 1996.
[16] HaoChuan Xu and Ninh Pham. Scalable dbscan with random projections. Advances Neural Information Processing Systems, 37:27978-28008, 2024.
[17] Chidananda Gowda and GJPR Krishma. Agglomerative clustering using the concept of mutual nearest neighbourhood. Pattern recognition, 10(2):105-112, 1978.
[18] Eduardo Laber and Miguel Batista. On the cohesion and separability of average-link for hierarchical agglomerative clustering. Advances in Neural Information Processing Systems, 11448700-48733 2024.
[19] Fangfang Li, Quanxue Gao, Qianqian Wang, Ming Yang, and Cheng Deng. Tensorized soft label learning based on orthogonal nmf. IEEE Transactions on Neural Networks and Learning Systems, 2024.
[20] Jie Yan, Jing Liu, Yi-Zi Ning, and Zhong- Yuan Zhang. Sda-fc: Bridging federated clustering and deep generative model. Information Sciences, 681:121203, 2024.
[21] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 933-4)221-407, 2014.
[22] Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pages 463-480. IEEE, 2015.
[23] Songze Li, Sizai Hou, Baturalp Buyukates, and Salman Avestimehr. Secure federated clustering. arXiv preprint arXiv:2205. 15564, 2022.
[24] Yizhang Wang. Wei Pang. and Witold Pedryez. One-shot federated clustering based on stable distance relationships. IEEE Transactions on Industrial Informatics, 2024.
[25] Jonathan Scott, Christoph H Lampert, and David Saulpic. Differentially private federated k-means clustering with server-side data. arXiv preprint arXiv:2506.05408, 2025.
[26] Abdulrahman Diaa, Thomas Humphries, and Florian Kerschbaum. [FastLloyd]: Federated, accurate, secure, and tunable (k-Means) clustering with differential privacy. In 34th USENIX Security Symposium (USENIX Security 25), pages 2733-2752, 2025.
[27] Jie Zhang, Chen Chen, Bo Li, Lingjuan Lyu, Shuang Wu, Shouhong Ding, Chunhua Shen, and Chao Wu. Dense: Data-free one-shot federated learning. Advances Neural Information Processing Systems, 35:21414-21425 2022.
[28] Jiawei Shao, Yuchang Sun, Songze Li, and Jun Zhang. Dres-fl: Dropout-resilient secure federated learning for non-iid clients via secret data sharing. Advances in Neural Information Processing Systems, 35:10533-10544 2022.
[29] LKPJ Rdusseeun and P Kaufman. Clustering by means of medoids. In Proceedings of the statistical data analysis based on the LI norm conference, neuchatel, switzerland, volume 31, page 28, 1987.
[30] Weina Wang, Lei Ying, and Junshan Zhang. On the relation between identifiability, differential privacy, and mutual-information privacy. IEEE Transactions on Information Theory, 62(9):5018 5029, 2016.
12

---

[31] Kiran S Kedlaya and Christopher Umans. Fast polynomial factorization and modular composi- tion. SIAM Journal Computing, 4066):176--182,, 2011.
[32] Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, 172):199-188, 1936.
[33] Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web). IEEE signal processing magazine, 29(6):141-142, 2012.
[34] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist a novel image dataset for benchmarking machine learning algorithms. arXiv preprint
2017.
[35] Sameer A Nene, Shree K. Nayar, Hiroshi Murase, al. Columbia object image library (coil-20). 1996.
[36] Fabian Keller, Emmanuel Muller, and Klemens Bohm. Hics: High contrast subspaces for density-basee outlier ranking. 2012 IEEE 28th international conference on data engineering, pages 1037-1048. IEEE, 2012.
[37] Grace XY Zheng, Jessica M Terry, Phillip Belgrader, Paul Ryvkin, Zachary W Bent, Ryan Wilson, Solongo B Ziraldo, Tobias D Wheeler, Geoff P McDermott, Junjie Zhu, et al. Massively parallel digital transcriptional profiling of single cells. Nature communications, 8(1):14049, 2017.
[38] Alexander Strehl and Joydeep Ghosh. Cluster ensembles knowledge reuse framework for combining multiple partitions. Journal of machine learning research, ((Dec):583-11) 2002.
[39] Xin Liu, Hui-Min Cheng, and Zhong-Yusr Yuan Zhang. Evaluation of community detection methods. IEEE Transactions on Knowledge and Data Engineering, 32(9): 2019.
[40] Jie Yan, Xin Liu, Ji Qi. Tao You, and Zhong-Yuas Yuan Zhang. The significance of kappa and f-score clustering ensemble: a comprehensive analysis. Knowledge and Information Systems, pages 1-36, 2025.
[41] Jichan Chung, Kangwook Lee, and Kannan Ramchandran. Federated unsupervised clustering with generative models. In AAAI 2022 international workshop trustable, verifiable and auditable federated learning, volume 4, 2022.
[42] Jeffrey Humpherys and Tyler J Jarvis. Foundations of Applied Mathematics Volume 2: Algo- rithms, Approximation, Optimization. SIAM, 2020.
[43] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[44] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Couraaeeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
13

---

[45] Madson Luiz Dantas Dias. fuzzy-c-means, An implementation of fuzzy c-means clustering algorithm., May 2019.
[46] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE signal processing magazine, 37(3)550-60, 2020.
[47] Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards k-means-friendly spaces: Simultaneous deep learning and clustering. In international conference machine learning, pages 3861-3870. PMIRR 2017.
[48] Lukas Miklautz, Timo Klein, Kevin Sidak, Collin Leiber, Thomas Lang, Andrii Shkahrii, Sebastian Tschiatschek, and Claudia Plant. Breaking the reclustering barrier centroid-based deep clustering. arXiv preprint arXiv:2411.0222 2024.
[49] Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Zhao Li, Jiajun Bu, Jia Wu, Xin Wang, Wenwu Zhu, and Martin Ester. A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. ACM Computing Surveys, 57(3):1-38, 2024.
[50] Jie Yan, Jing Liu, Ji Qi, and Zhong- Yuan Zhang. Privacy-preserve federated deep clustering based on gan, arXiv preprint urXiv:221 169655, 2022.
[51] Jie Yan, Jing Liu, and Zhong- Yuan Zhang. Cefe: Bridging federated clustering and contrastive learning, arXiv preprint arXiv:2401.06634 2024.
[52] Jie Yan, Jing Liu, Yi-Zi Ning, and Zhong-Yuan Yuan Zhang, Cofc++: Enhancing federated clustering through feature decorrelation. arXiv preprint 240.::2002.2225522 2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer to the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
15

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Please refer Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer to Sections 4.1 and
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
16

---

(a) If the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We have provided publicly available dataset information in Section C.I The code for the proposed OmniFC will be released upon the paper's formal publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
17

---

Justification:
Please refer to Sections 4.1 and C.2
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The deterministic nature of the global distance matrix reconstruction in the proposed OmniFC ensures consistent quality evaluations across multiple runs.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
18

---

The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e-g.. preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://s//arrrp....cooooootttttc
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper mainly targets privacy-preserving clustering in federated scenarios. By addressing this challenge, further promote the practical deployment of clustering in sensitive domains, such as healthcare and finance, while safeguarding data security and user privacy.
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations deploymenl of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks,
19

---

mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The original sources of the datasets are cited in Section +
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwpprswiithoooooooopppp thcode cwm /dtaastss has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
20

---

Answer:
[NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
21

---

For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, non non standdadd components.
Please refer to LLM policy [ttee:///errrppaccc//oofeeeeeeec for what should or should be described.
22

---

A Pseudocode of the Proposed OmniFC
The procedure of OmniFC is formally presented in Algorithm [ On the client side, each sample c independently encoded into Zi,j based on Equation ( and then transmitted to the j-th client, where [n] and j [m]] Then, each client computes pairwise distances between all encoded representations ži.j and 2j (i, (rl) using Equation (4) and transmits the results to the central server. On the server side, the global distance matrix is reconstructed based Equations (6) and 7 and subsequently utilized by centralized clustering algorithm derive the final clustering outcome r.
Algorithm 1: OmniFC
Input:
Local datasets (X, m prime number p, the number of segments 1, the number of noises t, pre-specified hyperparameters {aolo=i o=1 and }
1
Output: The final partition n².
1 Clients execute:
2. Local Lagrange Encoding and Secret Sharing:
3
Each sample ã; is encoded via Equation (3 i... Zi,j = fa. (3,), and subsequently transmitted to the j-th client, where E [n] and j E [m]]
4
5 Global Distance Reconstruction:
Each client j computes pairwise distances between all encoded representations ži, and Ze (i, [n]) using Equation 4 and transmits the results to the central server.
7
8
Server executes:
9
Global Distance Reconstruction:
The server reconstructs the global distance matrix according to Equations (6) and
Cluster assignment:
12 The global distance matrix fed into a centralized clustering method to obtain n."
B Proofs of Theorems
Before proving the theorems, we first summarize some notations used throughout the main text and this appendix, and introduce two lemmas from Ref. [42 and 12] Refer to Table for the notions, with the lemmas delineated below.
Lemma 1. [42] Given n distinct points ((x;; ys)) with mutually different Ti, there exists a unique polynomial f(x) of degree greater than - that interpolates the data, i.e., f(x;) Y:-
Lemma 2. 12] Given the number of noises I, and polynomial used compute f(X), and the degree of f is denoted as (fg(f), When m 2 de achievable, e.g..
1, t-private LCC encryption is
I@ā;; (Zis)iec) = O,
where I(::) denotes the mutual information function, [m] and |C| St
Proof of Theorem
With Lemma
J
we prove Theorem I as follows.
Proof. The server possesses only the pre-defined public hyperparameters {a.)ltt (8,)7= and the distance {dis(Zi.j) Zr. wi For each distance dis(zi.j, =v.g) (j E [m]), it can be further formulated as:
dis(zz ZR,)) = =| 22 (8,) fay (3, (8,)
(10)
23

---

Table 3: Notations.
Notation
Explanation
m
Number of clients.
The centralized dataset X E Rexd consists of n. d-dimensional samples {0;)7-1- which are distributed among m clients, i... X = x,
X E Boxd
X denotes the representation of X over the finite field Ippd consisting of d- dimensional samples (ã. ( where each ã; corresponds the transformed version of æ, in Fy
X E paxd
Number of data segments.
Number noises.
2. ... , "T. where 8i,0 denotes the o-th segment of ã. for [4] 8 corresponds the o-th noise uniformly sampled
8,00 Fp
21,2, .I. For from F.
collection of / distinct hyperparameters from Fp., predetermined by consensus between clients and the central server, serves to construct the Lagrange interpolation polynomial.
{a.)ati utt
collection of m distinct hyperparameters from Fp. predetermined by consensus between all clients and the central server, serves encode the local dltaa into distinct representations.
The global encoded dataset possessed by client (i [m]) Z, [Z1,], #2d- Fngl", where Z1,j (i E [n]) is the encoded representation of T. client j.
Z, Fp"" nxx
implying that it corresponds to the evaluation a degree-2(1 + polynomial at Sy. According to Lemma [ the polynomial can be uniquely interpolated from 2(1 + t 1) + 1 distinct points. That is, when m 2 21 + 2t 1, the polynomial can be interpolated from the set {(3,, dis( zy 5)) and it is exactly & Ta (3). i.e.
f a. (B) (3, 2
(11)
Particularly, by assigning a (o E [4]), the distance between the o-th data segments ã; and Ty can be accurately recovered:
Va, || (ax) ( 118,0 sv.oll
(12)
Consequently, the distance between ã; and Fy can be precisely reconstructed:
Σ Esa,s, (a.)
Σ ||81.0 s dis(ā;, Z.))
(13)
0=1
Note that since the above proof does not impose any constraints on the distribution of ã; and 7.- across clients, Equation
[l3 holds irrespective of how data is distributed among clients.
Proof of Theorem
2
With Lemma
we prove Theorem 2 as follows.

---

Table 4: Reconstruction time (seconds) of the global pairwise distance matrix across diverse data scales under varying I. Computational efficiency can be substantially improved by increasing the number of data segments L.
lk
2k
5k
10k
20k
40k
70k
1 1=
15
78
285
1053
4634
13576
[
9
55
154
620
2037
7094
1
32
124
435
1471
4352
Proof. We prove Theorem by instantiating Lemma with the specific polynomial structure used in the OmniFC framework.
Recall that Lemma 2 states that t-private LCC encryption is achievable when m deg(f)((+ +1,
where f is the polynomial used in the encoding scheme, and is the number of data segments. In the OmniFC setting, the polynomial f is a quadratic distance-based function of degree 2, i.e., deg(f) f = 2. Plugging this into the general LCC bound yields:
m 2 + 2t
Therefore, under this condition, the mutual information between any private input ã; and the encoded messages observed by up to colluding clients satisfies:
[ (Zi, hiec) = =0
where C [m] and |C|
This guarantees 1-privacy in the OmniFC framework, thus completing the proof.
C Experimental Details
All experiments are implemented in Python and executed on a system equipped with an Intel Core 17-12650H CPU, 16GB of RAM, and an NVIDIA GeForce RTX 4060 GPU.
C.1 Datasets and Evaluation Criteria
Datasets.
As shown in Table we select seven benchmark datasets across tabular, visual, tempo-
ral, and genomic domains, including Iris 33 MNIST 33 Fashion-MNIST (34, COIL-20 [35],
COIL-100 35 Pendigits [36], and 10k_73k 37. The chosen datasets encompass diverse modali- ties, dimensionalities, and cluster patterns, facilitating a comprehensive evaluation of the method's generalizability practical scenarios.
Fig. 6 exemplifies, through the Iris dataset, our simulation of federated scenarios under different Non-IID conditions. We simulate diverse federated settings by evenly partitioning the Iris dataset into 3 (the number of true clusters) subsets-eate representing client-ait adjusting the non-IID level p. For a client with 50 datapoints, the first p 50 datapoints are sampled from single cluster, and the remaining (1 - p) 50 ones are randomly sampled from any cluster. As such, = 0 recovers the IID setting, whereas = induces a maximally skewed distribution, where each client's data is fully concentrated within single cluster.
25

---

Table 5: Description of datasets.
Dataset
Type
Size
Image size/Features
Class
Iris
tabular
150
MNIST
image
70000
28 28
10
Fashion-MNIST
image
70000
28 x 28
10
COIL-20
image
1440
128 x 128
20
COIL-100
image
7200
128 128
100
Pendigits
time series
10992
16
10
gene
73233
720
8
p 0.0
0..5
p 0.5
Classes
Classes
Classes
2
Clients
Clients
Clients
p 0.75
1.0
Classes
Classes
Clients
Clients
Figure 6: Data partition visualization on Iris.
Evaluation Criteria. Evaluation is based two cotrics-normalizees mutual information (NMI) 38 and Kappa (39 -here elevated scores denote superior clustering quality. Despite being widely adopted, NMI has been shown have limitations, such as the finite size effect, and fails account for the importance of small clusters 339
In contrast, Kappa addresses these concerns, making more reliable alternative for clustering evaluation. Hence, our analysis is grounded in Kappa-based results, with NMI-based outcomes serving only supplementary references.
20 40
C.2 Implementation Details
All centralized clustering methods are implemented by leveraging existing open-source Python libraries: KM, KMed, SC, NMF, and DBSCAN utilize the sklearn library 43], HC employs the
scipy library 44 and FCM adopts an individual open-source implementation 445 For OmniFC,
(a set as a sequence of ++ consecutive odd integers starting from 1, while (3, set as a sequence of m consecutive even integers starting from 0. The default values of and are set to 2.
We acknowledge the importance of the constraint m 2 2(1 + f -- 1) + for successful distance reconstruction. Among these hyperparameters, (number of clients) is typically predetermined
26

---

by the federated scenario, while / (segments) and t (noises) are tunable hyperparameters that can be adjusted satisfy this constraint. In practice, violating this condition is extremely rare because the number of clients m in typical federated learning scenarios ranges from tens millions [46]. providing substantial flexibility for hyperparameter selection. In practice, m fixed by the sys- tem, while the choice of and t depends on the relative emphasis placed on communication and computational efficiency versus privacy preservation. Note that long as 2(1 + + + 1 holds, the specific values of / and have effect the reconstruction effectiveness of the global pairwise distance matrix (Theorem and Fig. 5). The hyperparameter governs the dimensionality (4) of both the shared encoded data across clients and the features involved in pairwise distance computation. A larger reduces the volume of shared data and the number of features compared, thus improving communication and computational efficiency (Table The hyperparameter governs the cntommation-thooretee security, with higher values enhancing resilience against client collusion (Theorem 2) However, the constraint m 2 2(1 + t 1) + precludes simultaneous increases in / and t, indicating that their selection hinges on the trade-off between communicatoo/ccomputttioooa efficiency and privacy preservation.
Additionally, several clustering methods evaluated in experiments demand full pairwise distance matrix computations, imposing substantial computational and memory burdens large-scale datasets. To facilitate the execution of comprehensive experiments, we implement a subsampling strategy whereby 1000 samples are randomly drawn from datasets exceeding 5000 entries to form the experimental subset. This approach balances computational efficiency with the preservation of the original data distribution, enabling fair and meaningful comparisons across methods. The sensitivity of the proposed OmniFC with respect to the number of samples is presented Appendix [..2]
D Supplementary Experimental Results
D.1 NMI-based Evaluation Results
To supplement the Kappa-based evaluation results and to enable broader comparability with existing FC works, we additionally provide NMI-based evaluation results in Tables 6 and Similar the Kappa-based evaluation results, the numerical results based on NMI also confirm the effectiveness and generalizability of OmniFC.
D.2 Sensitivity Analysis
To assess the sensitivity of the proposed OmniFC concerning the number of samples, we evaluate the global distance matrix reconstruction loss- as the root-mean cot-mean-squuee square deviation (RMSE) between the ground-truth and the reconstructed pairwise distance matrices- across different sample sizes. As shown in Table g OmniFC exhibits favorable scalability concerning sample size.
D.3 Non-IID Partitioning based Dirichlet Distributions
To test more diverse Non-IID scenarios, used Dirichlet distributions with varying concentrations model label heterogeneity on Pendigits in Table and other experimental settings are consistent Experimental results indicate that the OmniFC method exhibits superior
with those Table [] efficacy and robustness.
D.4 The Feasibility of Extending Deep Clustering
To further showcase the flexibility of the proposed framework, we validated the feasibility of employ- ing OmniFC to extend deep clustering. As foundational deep k-means (KM) method, DCN [47
27

---

Table 6: NMI of clustering methods in different federated scenarios. For each comparison, the best result highlighted in boldface.
SC-based methods
KM-based methods
FCM-hased methods
NMF-based methods
Dataset
SC_cent FedSC Ours KM central
I-FED
MUFC Ours
FCM central
FFCM Ours NMF central FedMAvg
Ours
0.00
0.90
0.90
0.66
0.76
0.90
0.91
0.90
0.73
0.90
0.73
0.90
0.56
0.75
0.85
0.90
0.90
0.74
0.90
0.91
0.90
0.73
0.90
1.00
0.29
0.90
0.70
0.70
0,90
0.93
0.90
0.73
0.90
0.00
0,59
0.58
0.51
0,48
0.46
0.53
0.43
0,48
0.47
0.25
0.60
0.58
0.49
0.52
0.53
0.43
0.45
0.47
MNIST
0.58
0.43
0.75
0.59
0.58
0.46
0.52
0.52
0.43
0.17
0.47
1.00
0.45
0.58
0.51
0.55
0.46
0.57
0.43
0.47
0.47
0.00
0.61
0.61
0.56
0.56
0.52
0.61
0.53
0.53
0.55
0.60
0.54
0.53
0.55
Fashion MNIST
0.61
0.75
0.55
0.61
0.55
0.54
0.53
1.00
0.39
0.61
0.48
0.59
0.52
0.58
0.53
0.53
0.55
0.00
0,80
0.75
0.65
0.74
0.74
0.71
0.72
0.62
0.75
0.25
0.78
0.75
0.70
0.73
0.69
0.72
0.62
0.75
COIL-20
0.75
0.69
0.75
0.67
0.73
0.74
0.72
0.63
0.75
1.00
0.46
0.75
0.69
0.72
0.74
0.75
0.72
0.63
0.75
0.00
0.67
0.79
0.76
0.76
01.99
0.69
0.79
0.70
0.76
0.25
0.66
0.79
0.75
0,76
0.79
0,70
0.76
0OIL-100
0.75
0.64
0.79
0.75
0.76
0.70
1.00
0.61
0.79
0.75
0.79
0.79
0.81
0.79
0.70
0.76
0.00
0.77
0.72
0.67
0.67
0.67
0.68
0.70
0.42
0.71
0.25
0.76
0,72
0.62
0.66
0.68
0.70
0.42
0.71
Pendigits
0.75
0.75
0.72
0.50
0.64
0.67
0.70
0.42
0.71
1.00
0.62
0.72
0.64
0.71
0.67
0.69
0.70
0.42
0.71
0.00
0.71
0.85
0.68
0.65
0.58
0.69
0.58
0.66
0.78
0.25
0.71
0.85
0.70
0.68
0.58
0.70
0.58
0.66
0.78
10X 73k
0.85
0.83
0.59
0.65
0.66
1.00
0.19
0.85
0.49
0.80
0.58
0.82
0.58
0.66
0.78
count
13
22
5
12
18
22
13
34
Table 7: NMI of different clustering methods.
KMed- -ased methods
DBSCAN-based methods
HC-based methods
Dataset
Central
Ours
Central
Ours
Central
Ours
Iris
0.86
0.86
0.73
0.73
0.89
0.90
MNIST
0.38
0.38
0.56
0.56
0.49
0.49
MaSIIT
0.49
0.49
0.53
0.53
0.54
0.54
COIL-20
0.60
0.61
0.86
0,86
0.70
0.69
COIL--100
0.69
0.69
0.85
0.85
0.78
0.78
Pendigits
0.56
0.55
0.74
0.74
0.69
0.69
10x_73k
0.31
0.31
0,45
0.45
0.51
0.50
Table 8: Sample-size sensitivity of the global distance matrix reconstruction loss on MNIST.
n
1000
2000
3000
5000
7000
10000
RMSE
0.0002
0.0002
0.0002
0.0002
0.0002
0.0002
28

---

Table 9: Kappa of clustering methods in different federated scenarios. For each comparison, the best result is highlighted in boldface.
SC-based methods
KM based metthods
FCM--based methods
NMP based methods
SC_ecutral
OumiF central
coatral
OunIFC-FCM .ccntral FodMMAs OmmiFC-NMP
1000
0.71
0.72
0.61
0.66
0.33
0.72
0.72
0.73
0.72
0.11
0.62
0.65
0.52
0.66
0.33
0.72
0.001
0.59
0.72
0.51
0.60
0.62
0.34
0.66
0.33
0.72
Table 10: Kappa clustering methods different simulated federated datasets. OmniFC-DCN achieves superior clustering performance relative to its shallow counterpart, OmniFC-KM.
Method
MNIST
Pendigits
10x_73k
OmniFC-KM
0.42
0.62
0.56
OmniFC-DCN
0.43
0.64
0.60
has spurred range of advanced clustering techniques and found widespread use in privacy-sensitive domains such medicine and finance [8%. Therefore, extending DCN could significantly impact multiple research fields and accelerate progress on downstream applications.
To this end, we extend DCN analogously to KM by using the reconstructed distance matrix in place of raw features as the model input. This extended variant is denoted as OmniFC-DCN, As evidenced in Toble OmniFFCDCN outperforms its shallow counterpart, OmniFC-KM, in clustering performance, further highlighting the flexibility of OmniFC.
E Limitation
This work primarily focuses on extending shallow centralized clustering methods and may be less effective for high-dimensional or intrinsically complex data. A promising future direction is to explore how the reconstructed global distance matrix can substantially support the federated extension of deep centralized clustering methods, thereby enabling more powerful representation learning under complex data distributions
44 50
29


Reviews:
[{"review_id": "rlgzMk9KoT", "reviewer": "Reviewer_Wn1Y", "summary": "This paper proposes **OmniFC**, a novel federated clustering (FC) framework that addresses privacy leakage and robustness degradation under non-IID data via lossless, secure reconstruction of the global distance matrix. Existing FC methods rely on model-specific proxies (e.g., centroids or low-rank factors), which are sensitive to data heterogeneity and inherit biases from centralized clustering. OmniFC leverages **Lagrange coded computing (LCC)** to enable clients to share encoded data, allowing exact reconstruction of pairwise distances without raw data exposure—even under client collusion. The framework is model-agnostic, unifying extensions for diverse centralized clustering methods (k-means, spectral clustering, DBSCAN, etc.). Theoretical guarantees for reconstruction fidelity and privacy are provided, and experiments across 7 benchmarks show superior robustness and effectiveness over SOTA methods.", "questions": "Please check it in Weekness.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**   \n1. **Groundbreaking Privacy-Security Integration**: First to achieve *lossless* distance matrix reconstruction under LCC encryption, providing information-theoretic privacy against colluding clients (Theorem 2). This resolves a core FC challenge.  \n2. **Unified Model-Agnostic Design**: Decouples clustering from model-specific proxies. The framework’s generality is a significant advancement.  \n3. **Theoretical Rigor**: Theorems 1–2 formally guarantee exact distance reconstruction (under \\(m \\geq 2l + 2t - 1\\)) and \\(t\\)-private security, with tight alignment between efficacy and privacy conditions.  \n4. **Compelling Empirical Results**: Extensive experiments on tabular, image, and genomic data.\n5. **Exceptional Clarity**: Well-structured with intuitive figures (Fig. 2–3) and detailed pseudocode (Appendix A).  \n\n\n**Weaknesses:**  \n1. **Scalability Limits**: Although the paper proposes segmentation and encoding techniques to reduce communication costs, computing and reconstructing the global pairwise distance matrix (of size $n \\times n$) can be computationally and memory-intensive, especially on large-scale datasets such as 10x_73k (with 73k samples). While the authors employ a subsampling strategy (1,000 samples) to alleviate this issue, the paper does not adequately discuss how the method can be scaled to larger datasets in practical federated learning scenarios.\n\n2. **Hyperparameter Sensitivity**: Parameters \\(l\\) (segments), \\(t\\) (noises), and \\(m\\) (clients) must satisfy \\(m \\geq 2l + 2t - 1\\). Tuning guidance is lacking, and violating this condition causes reconstruction failure (Fig. 5).  \n\n3. **Shallow Clustering Focus**: Validated only on classical methods (k-means, SC, etc.). Extension to deep clustering (Appendix E) is speculative and untested.", "was_revised": true, "final_justification": "I will keep my score after discussion with authors and other reviewers.", "rebuttal": "# Author Response to Reviewer Wn1Y\n\nWe thank reviewer Wn1Y for the valuable and constructive comments. We address the concerns as follows.\n\n> **Scalability Limits**: Although the paper proposes segmentation and encoding techniques to reduce communication costs, computing and reconstructing the global pairwise distance matrix (of size $n \\times n$) can be computationally and memory-intensive, especially on large-scale datasets such as 10x_73k (with 73k samples). While the authors employ a subsampling strategy (1,000 samples) to alleviate this issue, the paper does not adequately discuss how the method  be scaled to larger datasets in practical federated learning scenarios.\n\n**Answer:** We clarify that the subsampling strategy was implemented specifically to accommodate the computational requirements of downstream clustering algorithms used in our comparative evaluation, rather than addressing limitations of our distance matrix reconstruction itself. To provide clarity on this matter, we added a computational complexity analysis and included the runtime for OmniFC reconstructing the distance matrix on 10x_73k in *Rebuttal Table A*.\n\nRecall that reconstructing the global pairwise distance matrix involves two main stages: local encoding and distance computation on the client side, followed by server-side decoding to recover the global matrix. For each client $j$, fast polynomial interpolation and evaluation [1] yield an encoding complexity of $\\mathcal{O}(\\frac{dn_jm\\log^2m}{l})$, while distance computation on the encoded data incurs a complexity of $\\mathcal{O}(\\frac{dn^2}{l})$, leading to an overall complexity of $\\mathcal{O}(\\frac{d(n^2 + n_jm\\log^2m)}{l})$. $n_j$ is the number of samples held by client $j$. For the server side, the decoding operation has a complexity of $\\mathcal{O}(n^2(l+t)\\log^2(l+t))$. \n\nThe analysis indicates that, on the client side, increasing the number of data segments $l$ substantially reduces computational complexity, thereby facilitating the calculation of pairwise distances in a $\\frac{d}{l}$-dimensional space, where the feature count ($\\frac{d}{l}$) involved in pairwise comparisons decreases as $l$ rises. On the server side, however, a larger $l$ results in greater computational complexity. As for the impact of $l$ on the overall complexity of the reconstruction process, a theoretical analysis is challenging due to the differing hyperparameters involved on both sides. \n\nTo handle this, we presented the runtime for reconstructing the global pairwise distance matrix across varying data scales on 10x_73k. As shown in *Rebuttal Table A*, one can observe that: Although the runtime exhibits a marked increase as $n$ grows, enhancing the number of data segments $l$ can considerably boost computational efficiency when $n$ is fixed. For instance, processing 70k samples takes 4352 seconds with $l = 8$, demonstrating that our method remains computationally feasible on large-scale datasets. Importantly, as long as the constraints $m \\geq 2l + 2t - 1$ holds, increasing $l$ have no effect on the reconstruction effectiveness of the global pairwise distance matrix (Theorem 1 and Fig. 5).\n\nBuilding on the above analysis, we contend that expanding the number of data segments $l$ will enhance the proposed method's capability to handle large-scale datasets. The strategy for selecting optimal $l$ values will be further elaborated in our response to the next question. This will be included in the revised version to highlight the applicability of the proposed method.\n\n**Rebuttal Table A**. Reconstruction time (seconds) of the global pairwise distance matrix across diverse data scales under varying $l$. Computational efficiency can be substantially improved by increasing the number of data segments $l$.\n| $n$    | 1k   | 2k   | 5k   | 10k  | 20k  | 40k  | 70k   |\n| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :---- |\n| $l=2$  | 4    | 15   | 78   | 285  | 1053 | 4634 | 13576 |\n| $l=4$  | 3    | 9    | 55   | 154  | 620  | 2037 | 7094  |\n| $l=8$  | 2    | 6    | 32   | 124  | 435  | 1471 | 4352  |\n\n[1] Fast polynomial factorization and modular composition.\n\n**Actions**: \n1. We added a computational complexity analysis and presented the runtime.\n2. These will be included in the revised version.\n\n\n---\n> **Hyperparameter Sensitivity**: Parameters (l) (segments), (t) (noises), and (m) (clients) must satisfy (m \\geq 2l + 2t - 1). Tuning guidance is lacking, and violating this condition causes reconstruction failure (Fig. 5).\n\n**Answer:** We appreciate the valuable feedback and will elaborate on the tuning guidance in Appendix C.2 \n\nWe acknowledge the importance of the constraint $m \\geq 2l + 2t - 1$ for successful distance reconstruction. We clarify that among these parameters, $m$ (number of clients) is typically predetermined by the federated scenario, while $l$ (segments) and $t$ (noises) are tunable hyperparameters that can be adjusted to satisfy this constraint. In practice, violating this condition is extremely rare because the number of clients m in typical federated learning scenarios ranges from tens to millions [1], providing substantial flexibility for parameter selection. The constraint would only be violated in cases where $m$ is very small, which is uncommon in real-world federated learning deployments where sufficient participants are usually available.\n\n\n\nIn practice, \\$m\\$ is fixed by the system, while the choice of \\$l\\$ and \\$t\\$ depends on the relative emphasis placed on communication and computational efficiency versus privacy preservation. Note that as long as $m \\geq 2l + 2t - 1$ holds, the specific values of $l$ and $t$ have no effect on the reconstruction effectiveness of the global pairwise distance matrix  (Theorem 1 and Fig. 5).The hyperparameter $l$ governs the dimensionality ($d/l$) of both the shared encoded data across clients and the features involved in pairwise distance computation. A larger $l$ reduces the volume of shared data and the number of features compared, thus improving communication and computational efficiency (Rebuttal Table A). The hyperparameter \\$t\\$ governs the information-theoretic security, with higher values enhancing resilience against client collusion (Theorem 2). However, the constraint $m \\geq 2l + 2t - 1$ precludes simultaneous increases in $l$ and $t$, indicating that their selection hinges on the trade-off between communication/computational efficiency and privacy preservation.\n\n[1] Federated learning: Challenges, methods, and future directions.\n\n**Actions**: \n1. We provided a more in-depth analysis of the choices of $l$ and $t$. \n2. This will be added in Appendix C.2.\n\n---\n> **Shallow Clustering Focus**: Validated only on classical methods (k-means, SC, etc.). Extension to deep clustering (Appendix E) is speculative and untested.\n\n**Answer:** Thank you for your constructive feedback. As suggested, we demonstrated the feasibility of leveraging OmniFC to extend deep clustering. \n\nAs a foundational deep k-means (KM) method, DCN [1] has spurred a range of advanced clustering techniques and found widespread use in privacy-sensitive domains such as medicine and finance [2]. Therefore, extending DCN could significantly impact multiple research fields and accelerate progress on downstream applications. To this end, we extend DCN analogously to KM by using the reconstructed distance matrix in place of raw features as the model input. This extended variant is denoted as OmniFC-DCN. As evidenced in *Rebuttal Table B*, OmniFC-DCN outperforms its shallow counterpart, OmniFC-KM, in clustering performance, further highlighting the flexibility of OmniFC.\n\n**Rebuttal Table B**. Kappa of clustering methods in different simulated federated datasets. OmniFC-DCN achieves superior clustering performance relative to its shallow counterpart, OmniFC-KM.\n| Method     | MNIST    | Pendigits | 10x_73k  |\n| ---------- | -------- | --------- | -------- |\n| OmniFC-KM  | 0.42     | 0.62      | 0.56     |\n| OmniFC-DCN | **0.43** | **0.64**  | **0.60** |\n\n[1] Yang, Bo, et al. \"Towards k-means-friendly spaces: Simultaneous deep learning and clustering.\" international conference on machine learning. PMLR, 2017.\n\n[2] Miklautz, Lukas, et al. \"Breaking the reclustering barrier in centroid-based deep clustering.\" International Conference on Learning Representations. ICLR, 2025.\n\n**Actions**: \n1. We demonstrated the feasibility of leveraging OmniFC to extend deep clustering.\n2. This will be added in Appendix D."}, {"review_id": "B9eNqYJZnl", "reviewer": "Reviewer_NYLc", "summary": "This paper addressed two critical challenges in federated learning: (1) privacy leakage during collaboration, and (2) robustness degradation due to the non-IID local data. This work introduces OmniFC, a unified and model-agnostic framework via lossless and secure distance reconstruction. In fact, the authors design a pipeline that employs Lagrange coded computing to generate intermediate exchange variables, which are then used to reconstruct the exact pairwise distance matrix. Therefore, their proposed approach remains broadly applicable to any machine learning tasks that rely on the pairwise distance matrix such as spectral clustering, SVM, and t-SNE. In this sense, the method is claimed to be model-agnostic. Additionally, the authors demostrate that OmniFC preserves data privacy, arguing that there is zero mutual information between the raw data and the intermediate exchange variables, which is a distinct idea from the traditional standard procedure such as differential privacy (DP), homomorphic encryption (HE), and secure multi-party computation (SMC). Theoretical and empirical results have shown that this framework improves robustness under non-IID settings.", "questions": "Please see the weakness.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "__Strength__\n\nThis paper proposes the OmniFC framework, which uses lossless and secure distance reconstruction to address two common challenges in federated learning: privacy leakage during collaborative training and robustness degradation under non-IID settings. According to the existing literature, it is non-trivial to achieve a high-equality approximation of pairwise distance matrix in federated environments. OmniFC employs Lagrange encoded computing to reconstruct the EXACT pairwise distance matrix in a federated setting, which represents a significant and meaningful advancement for this problem. This contribution could benefit a wide range of machine learning tasks that heavily rely on accurate pairwise distance matrix reconstruction in federated scenarios. One limitation, however, is that the authors justify the privacy guarantee theoretically by claiming that there is zero mutual information between raw data and the intermediate exchange variables. I am not certain that mutual information alone provides a sufficient theoretical foundation for privacy preservation, as I am not an expert in encryption. Nevertheless, this work is interesting and the paper is concise and well-written.\n\n__Weakness__\n\nI have some question about this work as follows:\n\n1. Lines 81-87: It would be clearer to remove the description of the proposed framework from the Related Work section and focus this section solely on reviewing relevant prior studies.\n\n2. The expression $f_{\\tilde{x} _i,\\tilde{x} _{i'}}$ is not defined in the statement of Theorem 1. Since it is explained in the appendix, it may improve clarity to directly specify its definition within Theorem 1.\n\n3. In Theorem 1, it is claimed that the distance $\\text{dis}(\\tilde{x} _i,\\tilde{x} _{i'})$ can be precisely recovered by $\\sum _{o=1}^l f _{\\tilde{x} _i,\\tilde{x} _{i'}}(\\alpha _o) = \\sum _{o=1}^l \\|f _{\\tilde{x} _i}(\\alpha _o) - f _{\\tilde{x} _{i'}}(\\alpha _o)\\| _2^2 = \\sum _{o=1}^l \\|s _{i,o} - s _{i',o}\\| _2^2$. However, it is $z _{i,j} = f _{\\tilde{x} _i}(\\beta _j)$ as the transmitted value instead of $f _{\\tilde{x} _i}(\\alpha _o)$. Furthermore, since $\\{\\alpha _o\\} _{o=1}^{l+t}\\cap\\{\\beta _j\\} _{j=1}^m = \\phi$, it appears that the server has no access to $f _{\\tilde{x} _i}(\\alpha _o)$ for $i\\in[n]$ and $o\\in[l]$. Could the authors clarify how the server can recover $\\text{dist}(\\tilde{x} _i,\\tilde{x} _{i'})$ in practice from the uploaded set $\\{\\text{dis}(z _{i,j}, z _{i',j})\\} _{j=1}^m$? It would be helpful if the authors could provide a brief proof or explanation of this recovery process.\n\n4. Line 159: How can $X$ be obtained from the recovered proxy $D$ for clustering methods that do not explicitly depend on pairwise relationships, as considered in this work?\n\n5. In the case of two clients ($m=2$), will the proposed method remain effective? In other words, how should $l$ and $t$ be selected to ensure that the condition $m > 2l + 2t - 1$ holds given $m = 2$?\n\n6. Why does the severity of the non-IID setting not significantly affect the performance of the KM-based, FCM-based, and NMF-based methods? Furthermore, why does FFCM perform better under severe non-IID scenarios, even on the 10x\\_73k dataset?\n\n7. The numerical sensitivity results indicate that the proposed method successfully reconstructs the distance matrix when the condition $m > 2l + 2t - 1$ holds. It would be helpful if the authors could also provide the reconstruction loss for scenarios where this condition does not hold?", "was_revised": true, "final_justification": "The authors have address my concerns about certain theoretical and experimental questions:\n\n1. They show by introducing existing literature that mutual information can be used to provide the privacy guarantee for the proposed method;\n\n2. They summarize the details of the propose recovery method of pairwise-distance;\n\n3. They discuss the limitation of the proposed method for the scenarios where only 2 clients are available.\n\nBased on these response, I decide to upgrade my confidence by 1 while keeping the existing rating 4.", "rebuttal": "# Author Response to Reviewer NYLc\nWe thank reviewer NYLc for the valuable and insightful comments. We address the concerns as follows.\n>One limitation, however, is that the authors justify the privacy guarantee theoretically by claiming that there is zero mutual information between raw data and the intermediate exchange variables. I am not certain that mutual information alone provides a sufficient theoretical foundation for privacy preservation, as I am not an expert in encryption.\n\n**Answer:** Thank you for this important question. In fact, mutual information (MI) has been extensively employed to quantify privacy guarantees in the fields of security and cryptography [1, 2, 3]. Mutual information essentially measures how much one piece of information reveals about another—when it equals zero, it means one reveals nothing about the other, thereby preserving privacy. Furthermore, MI is not an isolated privacy-preserving metric; it can be compared with other privacy measures (such as differential privacy) within a unified framework [1], which further underscores its reliability in quantifying the level of privacy protection.\n\n[1] On the relation between identifiability, differential privacy, and mutual-information privacy.\n\n[2] Lagrange coded computing: Optimal design for resiliency, security, and privacy.\n\n[3] Inf2Guard: An Information-Theoretic Framework for Learning Privacy-Preserving Representations against Inference Attacks.\n\n**Actions:**\n1. We incorporated background on MI as a metric for privacy preservation.\n2. This will be added in Sect. 3.3.\n\n---\n> Lines 81-87: It would be clearer to remove the description of the proposed framework from the Related Work section and focus this section solely on reviewing relevant prior studies.\n\n**Answer:** We appreciate your feedback. In the revised manuscript, we will implement your suggestion by excluding the proposed framework from the Related Work section and dedicating this part exclusively to the review of relevant literature.\n\n**Actions:**\n1. We will exclude the proposed framework from the Related Work section in the revised manuscript.\n\n---\n>The expression $f\\_{\\tilde{x}_i,\\tilde{x}\\_{i'}}$ is not defined in the statement of Theorem 1. Since it is explained in the appendix, it may improve clarity to directly specify its definition within Theorem 1.\n\n**Answer:** Thank you for your feedback. $f_{\\tilde{x}_i, \\tilde{x}\\_{i'}}(\\beta)$ is the Lagrange interpolation polynomial interpolated from the set $\\\\{(\\beta_j,{dis}(z\\_{i,j},z\\_{i',j}))\\\\}\\_{j=1}^{m}$, defined as follows:\n$$\nf\\_{\\tilde{x}\\_i,\\tilde{x}\\_{i'}}(\\beta)=\\sum\\_{j=1}^{m}{dis}(z\\_{i,j},z\\_{i',j})\\cdot\\prod\\_{j'\\neq j}\\frac{\\beta-\\beta\\_{j'}}{\\beta\\_j-\\beta\\_{j'}}.\n$$\n\nThis will be included in the revised version to enhance clarity.\n\n**Actions:**\n1. We presented the definition of $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}$.\n\n2. We will add this definition to Theorem 1.\n\n---\n> In Theorem 1, it is claimed that the distance ${dis}(\\tilde{x}\\_i, \\tilde{x}\\_{i'})$  can be precisely recovered by $\\sum\\_{o=1}^l f\\_{\\tilde{x}_i,\\tilde{x}\\_{i'}}(\\alpha_o) = \\sum\\_{o=1}^l\\left\\|f\\_{\\tilde{x}\\_i}(\\alpha\\_o) - f\\_{\\tilde{x}\\_{i'}}(\\alpha_o)\\right\\|\\_{2}^{2} = \\sum\\_{o=1}^l\\left\\|s\\_{i,o} - s\\_{i',o}\\right\\|\\_{2}^{2}$. However, it is $z\\_{i,j} = f\\_{\\tilde{x}_i}(\\beta_j)$ as the transmitted value instead of $f\\_{\\tilde{x}\\_i}(\\alpha\\_o)$. Furthermore, since $\\\\{{\\alpha}_o \\\\}\\_{o = 1}^{l+t} \\cap \\\\{{\\beta}_j \\\\}\\_{j = 1}^{m} = \\emptyset$, it appears that the server has no access to $f\\_{\\tilde{x}\\_i}(\\alpha\\_o)$ for $i \\in [n]$  and $o \\in [l]$. Could the authors clarify how the server can recover ${dis}(\\tilde{x}\\_i, \\tilde{x}\\_{i'})$ in practice from the uploaded set $\\\\{{dis}(z\\_{i,j}, z\\_{i',j}) \\\\}\\_{j = 1}^{m}$? It would be helpful if the authors could provide a brief proof or explanation of this recovery process.\n\n**Answer:** Thank you for this important question.  We clarify that: \n1. The server possesses only the pre-defined public hyperparameters $\\\\{{\\alpha}_o \\\\}\\_{o = 1}^{l+t}$, $\\\\{{\\beta}_j \\\\}\\_{j = 1}^{m} $, and the distance $\\\\{{dis}(z\\_{i,j}, z\\_{i',j}) \\\\}\\_{i=1,j=1}^{n,m}$ uploaded by clients. \n2. The server recovers the distance using $${dis}(\\tilde{x}\\_i, \\tilde{x}\\_{i'}) = \\sum\\_{o=1}^l f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\alpha_o),$$ where\n$f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\alpha_o)$ is computed based on the interpolated polynomial $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta)$ derived from $\\\\{(\\beta_j, {dis}(z\\_{i,j}, z\\_{i',j})) \\\\}\\_{j = 1}^{m}$ (as defined in the preceding answer), rather than on $f\\_{\\tilde{x}\\_i}(\\alpha\\_o)$. That is, assigning $\\beta = \\alpha_o$ yields $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\alpha_o)$ upon substitution into $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta)$. \n3. The core challenge of the recovery process is to establish a connection between $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}$ and $f\\_{\\tilde{x}\\_i}$ without access to $f\\_{\\tilde{x}\\_i}$, as governed by the following equation:\n$$f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta) = \\left\\\\|f\\_{\\tilde{x}_i}(\\beta) - f\\_{\\tilde{x}\\_{i'}}(\\beta)\\right\\\\|\\_{2}^{2}.$$\nThis is because $\\\\|f\\_{\\tilde{x}\\_i}(\\alpha\\_o) - f\\_{\\tilde{x}\\_{i'}}(\\alpha\\_o)\\\\|\\_{2}^{2} = \\\\|s\\_{i,o} - s\\_{i',o}\\\\|\\_{2}^{2}$\nmeasures the pairwise distance of the $o$-th data segments, but $f\\_{\\tilde{x}\\_i}$ is inaccessible to the server. Hence, if we can prove the validity of the above connection, we can directly estimate the value of $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta)$ at point $\\alpha\\_o$ to measure the distance, without accessing $f\\_{\\tilde{x}\\_i}$.\nThe full proof is available in Appendix B; a concise version is outlined below:\n- For each pairwise distance, it can be further formulated as: ${dis}(z\\_{i,j}, z\\_{i',j}) = \\\\|z\\_{i,j} - z\\_{i',j}\\\\|\\_{2}^{2} = \\\\|f\\_{\\\\tilde{x}_i}(\\beta_j) - f\\_{\\tilde{x}\\_{i'}}(\\beta_j)\\\\|\\_{2}^{2}$, implying that it corresponds to the evaluation of a degree-$2(l + t - 1)$ polynomial at $\\beta_j$. This implies that $\\left\\\\|f\\_{\\tilde{x}_i}(\\beta) - f\\_{\\tilde{x}\\_{i'}}(\\beta)\\right\\\\|\\_{2}^{2}$, akin to $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta) $, is likewise derived as a polynomial over $m$ data points $\\\\{(\\beta_j, {dis}(z\\_{i,j}, z\\_{i',j})) \\\\}\\_{j = 1}^{m}$.\n- According to Lemma 1, the polynomial can be **uniquely** interpolated from $2(l+t-1) + 1$ distinct points. Hence, for $m\\geq 2l + 2t - 1 $, the polynomial $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta) $ is interpolable from the set $\\\\{(\\beta_j, {dis}(z\\_{i,j}, z\\_{i',j})) \\\\}\\_{j = 1}^{m}$, and $f\\_{\\tilde{x}\\_i, \\tilde{x}\\_{i'}}(\\beta) = \\left\\\\|f\\_{\\tilde{x}_i}(\\beta) - f\\_{\\tilde{x}\\_{i'}}(\\beta)\\right\\\\|\\_{2}^{2}$ holds.\n\n**Actions:**\n1. We clarified the information available on the server side for distance reconstruction.\n2. We provided a brief proof and explanation of the recovery process.\n3. This will be included in the revised version.\n\n---\n> Line 159: How can X be obtained from the recovered proxy D for clustering methods that do not explicitly depend on pairwise relationships, as considered in this work?\n\n**Answer:** Thank you for your comment. For these methods, the server employs D as a proxy for the raw features X as the model input, i.e., the distance values become the new features of the samples.\n\n**Actions:**\n1. We provided more algorithmic details.\n2. This will be added in Sect. 3.2.\n\n---\n>In the case of two clients ($m=2$), will the proposed method remain effective? In other words, how should $l$ and $t$ be selected to ensure that the condition $m>2l+2t-1$ holds given $m=2$?\n\n**Answer:** Thank you for your insightful comment. $m=2$ is a blind spot of the proposed method. \n\nUnder this setting, the constraint $m\\geq2l+2t-1$ admits only a single valid configuration, $l=1$ and $t=0$, leaving the data segment for Lagrange interpolation to consist solely of the private data itself. Consequently, the resulting polynomial degenerates into a constant function, rendering it unsuitable for encoding and encryption, and thus halting the subsequent process.\n\nHowever, scenarios involving such a limited number of clients are rarely observed in practice, as canonical federated learning problems typically encompass client populations spanning from tens to millions [1]. Hence, this limitation does not diminish the practicality of the proposed method.\n\n[1] Federated learning: Challenges, methods, and future directions.\n\n**Actions:**\n1. The constraints of the proposed method under $m=2$ were discussed.\n\n---\n>Why does the severity of the non-IID setting not significantly affect the performance of the KM-based, FCM-based, and NMF-based methods? Furthermore, why does FFCM perform better under severe non-IID scenarios, even on the 10x_73k dataset?\n\n**Answer:** Thank you for your comment. We argue that data heterogeneity substantially undermines the performance of all baseline methods (Table 1), with even the notably robust FedMAvg showing a maximum performance variation of 0.07 on MNIST. The superior performance of FFCM under heightened non-IID conditions stems from the fact that greater heterogeneity concentrates client-held samples within single classes, yielding cleaner cluster centroids with minimal cross-class contamination and thereby enhancing clustering performance.\n\n---\n>The numerical sensitivity results indicate that the proposed method successfully reconstructs the distance matrix when the condition $m>2l+2t-1$ holds. It would be helpful if the authors could also provide the reconstruction loss for scenarios where this condition does not hold?\n\n**Answer:** Thank you for your comment. As recommended, we examined the constraint-violating examples in Fig. 5, all presenting an RMSE reconstruction loss of 0.39—significantly higher than the 0.0002 in valid cases. Additional analysis showed that failed reconstructions closely resemble matrices drawn from a uniform distribution, both incurring similar loss, suggesting they convey no substantive information."}, {"review_id": "WUgcEOHoO4", "reviewer": "Reviewer_Yc82", "summary": "OmniFC delivers a drop‑in federated clustering method: clients split their quantized feature vectors into segments and compute Lagrange‑coded evaluations over a finite field, which they send to the server. \nUsing only these coded values, the server can reconstruct the global pairwise distance matrix $D_{ij}=\\|x_i-x_j\\|^2$ losslessly and then applies standard k‑means, spectral clustering or DBSCAN without ever seeing raw data. Theorem 1 shows that $m\\ge2l+2t-1$ evaluations suffice for exact recovery, and Theorem 2 establishes information‑theoretic $t$-privacy when $m\\ge2\\ell+2t-1$. Empirical results under extreme non‑IID splits demonstrate that OmniFC matches centralized Kappa and NMI while drastically reducing communication and compute costs.", "questions": "Please refer to the weaknesses.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1.**Theoretical Proofs.** The authors provide comprehensive theoretical proofs for OmniFC, demonstrating the feasibility of lossless global distance matrix reconstruction and privacy preservation. Theorem 1 proves that when the number of clients satisfies $ m \\geq 2(l + t - 1) + 1 $, the distance matrix can be accurately reconstructed using Lagrange Coded Computing (LCC) and polynomial interpolation. Theorem 2 employs mutual information analysis $( I(\\hat{x}_i; \\{z_{i,j}\\}_{j \\in \\mathcal{C}}) = 0 ), ( |\\mathcal{C}| \\leq t )$ to ensure data privacy against collusion of up to $t$ clients. These proofs leverage finite field operations for numerical stability, assuming data can be segmented into $l$ parts with $t$ added noises. Experimental validation shows minimal reconstruction error (RMSE=0.0002), outperforming SOTA methods like k-FED and FedSC in non-IID scenarios, demonstrating superior robustness and generality.\n\n2.**Novelty of LCC.** Lagrange Coded Computing (LCC), as a distributed secure computing technique, can reduce computation and communication costs while ensuring fault tolerance and security. The authors ingeniously apply it to encode local client data for interactively computing the global clustering distance, which I consider quite novel in the field of privacy-preserving clustering.\n\n3.**Experiments.** OmniFC demonstrates superior performance across multiple datasets (Iris, MNIST, COIL-100, etc.) and five non-IID scenarios (p=0 to 1), with Kappa remaining nearly unchanged as non-IID intensity increases, outperforming SOTA methods like k-FED (0.88 to 0.62) and FedSC (0.90 to 0.65). Its model-agnostic design and global distance matrix reconstruction ensure high robustness and consistency, supporting various clustering algorithms.\n\nWeaknesses\n1.**Lack of Comparison Methods.** The paper presents a seemingly novel aggregation method, but it lacks citations or comparisons with recent works on secure or privacy-preserving federated aggregation. I suggest the authors at least reference and discuss the following works: \n1) Secure Federated Clustering, 2022, IACR; \n2) Differentially Private Federated k-Means Clustering with Server-Side Data, 2025, ICML; \n3) FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy, 2025, arXiv.\n\n2.**Insufficient Sensitivity Analysis.** The experiments use a single finite field scaling parameter $q$, without examining its impact on clustering performance. I recommend adding an ablation study on bit-width $q$, such as gradually reducing $q$, plotting the relationship between reconstruction error and clustering metrics Kappa & NMI, and discussing the impact of precision degradation.\n\n3.**Lack of Time and Computational Complexity Analysis.** The paper does not quantify the runtime or resource consumption of OmniFC. Secure coded computing often introduces overhead from polynomial interpolation. Without clarification, its feasibility is unclear. I suggest providing time complexity estimates for clients and servers, detailing computational costs (e.g., polynomial encoding or decoding, per-round distance computation), and discussing whether the overhead is acceptable in federated settings. This allows comparison with other methods to highlight efficiency advantages.\n\n4.**Limited Novelty.** The method appears similar to Secure Federated Clustering. Could the authors discuss the differences? LCC is not new in federated settings, and directly encoding data to estimate distances is not novel in federated learning, as seen in: \n1) DReS-FL: Dropout-Resilient Secure Federated Learning for Non-IID Clients via Secret Data Sharing, 2022, NIPS; \n2) Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks, 2020, IEEE JSAC Series on Machine Learning for Communications and Networks; \n3) Lagrange Coded Federated Learning (L-CoFL) Model for Internet of Vehicles, 2022, ICDCS; \n4) FedWDP: A Wasserstein-distance-based federated learning for privacy and heterogeneous data in IoT, 2025, Internet of Things. \nThe paper seems to apply this approach to federated clustering (FC). Please re-emphasize the specific innovations.\n\n5.**Poor Exposition.** The concept of \"Federated Clustering (FC)\" is confusing. The authors fail to clearly define the application scenarios and task objectives in the introduction or background, leading to doubts about the goals of OmniFC.\n\n6.**Simple Non-IID Partitioning.** The authors use a single label skew parameter p to control non-IID settings. I suggest adopting more common partitioning strategies. Federated learning studies often use Dirichlet distributions with varying concentrations $\\alpha$ to model label heterogeneity (e.g., Khosravan et al., Redefining non-IID Data in Federated Learning for Computer Vision Tasks: Migrating from Labels to Embeddings for Task-Specific Data Distributions, 2025, arXiv) or feature shifts in image tasks. I recommend using Dirichlet($\\alpha$) for label allocation, observing performance changes as $\\alpha$ decreases (IID to highly non-IID). This would better validate robustness in real-world cross-device settings. Current results under a single skew are insufficient to demonstrate applicability across diverse non-IID scenarios.", "was_revised": true, "final_justification": "We appreciate your reply. My problem has been solved", "rebuttal": "# Author Response to Reviewer Yc82\nWe thank reviewer Yc82 for the valuable and constructive feedback. We address the concerns as follows.\n\n>**Lack of Comparison Methods.**\n\n**Answer:** Thank you for your constructive feedback. Following the suggestion, we added the clustering performance of the new baselines [2,3] on Pendigits in Table *Rebuttal Table A*. \n\nHere, we use Dirichlet distributions with varying concentrations $\\alpha$ to model label heterogeneity, and other experimental settings are consistent with those in Table 1. Experimental results show that the proposed method OmniFC-KM consistently outperforms the two newly introduced baselines. Indeed, we made every effort to compare our approach with SecFC [1] during the preliminary experimental phase. However, the method has not released its source code, and we were unable to reproduce the numerical results reported in the paper. Furthermore, our attempt to contact the authors received no response.\n\nWhile these methods similarly employ advanced privacy-preserving techniques to enhance clustering performance and ensure data confidentiality, the proposed method is distinguished by the following features:\n- *Generality*. As federated variants of k-means (KM), these three methods [1-3] naturally inherit KM' assumption of data compactness, limiting their effectiveness to KM-friendly datasets. In contrast, the proposed unified and model-agnostic framework OmniFC accommodates diverse datasets by extending beyond KM to encompass alternatives such as spectral clustering and DBSCAN.\n\n- *One-shot communication scheme*. To obtain more accurate cluster centroids, all three methods require multiple rounds of communication between the clients and the server. However, multi-round training is unfeasible in some scenarios, like model markets, where users can solely purchase pre-trained models [4]. In contrast, the proposed OmniFC, requiring merely one communication round, exhibits enhanced applicability in such scenarios.\n\nThese features highlight the practical advantages of the proposed OmniFC. These will be included in the revised version. \n\n**Rebuttal Table A.** Kappa of clustering methods in different simulated federated scenarios. The proposed OmniFC-KM achieves superior performance.\n|$\\alpha$|1000|5|0.001|\n|------------|----|----|-----|\n|FedDP-KMeans[2]|0.61|0.61|0.61|\n|FastLloyd[3]|0.55|0.55|0.56|\n|OmniFC-KM|**0.62**|**0.62**|**0.62**|\n\n[1]. Secure Federated Clustering\n\n[2] Differentially Private Federated k-Means Clustering with Server-Side Data\n\n[3] FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy\n\n[4] Dense: Data-free one-shot federated learning.\n\n**Actions:** \n1. We added comparative experiments with two new baselines.\n2. We discussed the distinguishing features of the proposed method relative to the three related methods.\n3. These will be added into the revised version, accompanied by appropriate citations to the related works.\n\n---\n>**Insufficient Sensitivity Analysis.**\n\n**Answer:** Thank you for your comment. Following the suggestion, we added a sensitivity analysis of OmniFC-SC to the hyperparameter $q$ on MNIST. Beyond clustering performance, we also reported the reconstruction error of the distance matrix (RMSE_dis) and the reconstruction error incurred when mapping all raw samples to a finite field and subsequently back to the real domain (RMSE_trans).\n\nAs shown in *Rebuttal Table B*, one can observe that:\n- The proposed method exhibits resilience to precision degradation, thereby easing the hyperparameter tuning process and underscoring its practicality.\n- The value of $q$ should be kept within a reasonable range. An overly large $q$ poses a risk of overflow, whereas an excessively small $q$ can significantly compromise precision (as evidenced by the trend of RMSE_trans).\n\n**Rebuttal Table B.** Sensitivity analysis of OmniFC-SC to the hyperparameter $q$.\n|$q$|14|12|10|8|6|4|2|\n|----------|----|----|----|----|----|----|----|\n|RMSE_dis|0.45|0.00|0.00|0.00|0.01|0.06|0.58|\n|RMSE_trans|0.00|0.00|0.00|0.00|0.00|0.01|0.03|\n|Kappa|0.15|0.55|0.54|0.54|0.51|0.53|0.07|\n|NMI|0.13|0.58|0.57|0.56|0.55|0.55|0.21|\n\n**Actions:** \n1. We added a sensitivity analysis of OmniFC-SC to the hyperparameter $q$.\n2. We provided tuning suggestions for the hyperparameter $q$.\n\n---\n>**Lack of Time and Computational Complexity Analysis.**\n\n**Answer:** Following the suggestion, we added a computational complexity analysis and included the runtime for OmniFC reconstructing the distance matrix on 10x_73k in *Rebuttal Table C*.\n\nRecall that reconstructing the global pairwise distance matrix involves two main stages: local encoding and distance computation on the client side, followed by server-side decoding to recover the global matrix. For each client $j$, fast polynomial interpolation and evaluation [1] yield an encoding complexity of $\\mathcal{O}(\\frac{dn_jm\\log^2m}{l})$, while distance computation on the encoded data incurs a complexity of $\\mathcal{O}(\\frac{dn^2}{l})$, leading to an overall complexity of $\\mathcal{O}(\\frac{d(n^2 + n_jm\\log^2m)}{l})$. $n_j$ is the number of samples held by client $j$. For the server side, the decoding operation has a complexity of $\\mathcal{O}(n^2(l+t)\\log^2(l+t))$. \n\nThe analysis indicates that, on the client side, increasing the number of data segments $l$ substantially reduces computational complexity, thereby facilitating the calculation of pairwise distances in a $\\frac{d}{l}$-dimensional space, where the feature count ($\\frac{d}{l}$) involved in pairwise comparisons decreases as $l$ rises. On the server side, however, a larger $l$ results in greater computational complexity. As for the impact of $l$ on the overall complexity of the reconstruction process, a theoretical analysis is challenging due to the differing hyperparameters involved on both sides.\n\nTo handle this, we presented the runtime for reconstructing the global pairwise distance matrix across varying data scales on 10x_73k. As shown in *Rebuttal Table C*, one can observe that: Although the runtime exhibits a marked increase as $n$ grows, enhancing the number of data segments $l$ can considerably boost computational efficiency when $n$ is fixed. For instance, processing 70k samples takes 4352 seconds with $l = 8$, demonstrating that our method remains computationally feasible on large-scale datasets. Hence, expanding the number of data segments $l$ will enhance the proposed method's capability to handle large-scale datasets.\n\n**Rebuttal Table C**. Reconstruction time (seconds) of the global pairwise distance matrix across diverse data scales under varying $l$. Computational efficiency can be substantially improved by increasing the number of data segments $l$.\n|$n$|1k|2k|5k|10k|20k|40k|70k|\n|:---|:---|:---|:---|:---|:---|:---|:----|\n|$l=2$|4|15|78|285|1053|4634|13576|\n|$l=4$|3|9|55|154|620|2037|7094|\n|$l=8$|2|6|32|124|435|1471|4352|\n\n[1] Fast polynomial factorization and modular composition.\n\n**Actions**: \n1. We added a computational complexity analysis and presented the runtime.\n2. These will be included in the revised version.\n\n---\n> **Limited Novelty.**\n\n**Answer:** Thank you for your comment. We clarify that:\n- While SecFC [1] also conducts distance reconstruction, the proposed method stands out due to its generality and one-shot communication protocol (refer to the response to the \"Lack of Comparison Methods\" comment for further details).\n\n- While LCC is not a novel concept within federated learning, it has predominantly been investigated in the context of supervised federated classification. Its exploration in unsupervised federated clustering (FC) remains sparse. Although SecFC has examined the integration of LCC into FC, its proposed methodology is constrained in scope and demands multiple communication rounds. In contrast, our approach is more versatile (to our knowledge, it is the first unified and model-agnostic FC framework) and requires only a single communication round. Thus, we contend that our exploration of LCC within the FC domain is innovative.\n\n- A careful review reveals that reference [2] focuses on differential privacy encryption for federated classification, with no discussion on FC.\n \n[1] Secure Federated Clustering.\n\n[2] FedWDP: A Wasserstein-distance-based federated learning for privacy and heterogeneous data in IoT.\n\n---\n>**Poor Exposition.**\n\n**Answer:** Thank you for your comment. We clarify that:\n- \"Federated Clustering (FC)\" is an established term within the community, originally introduced in seminal work [1], and not coined in our work. \n- OmniFC, as a unified FC framework, aligns with the application domains of existing FC methods, such as client selection and exploratory data analysis, without introducing new use cases. This will be included in the revised version.\n\n[1] Heterogeneity for the win: One-shot federated clustering.\n\n---\n>**Simple Non-IID Partitioning.**\n\n**Answer:** Thank you for your constructive comment. Following the suggestion, we used Dirichlet distributions with varying concentrations $\\alpha$ to model label heterogeneity on Pendigits in *Rebuttal Table D*, and other experimental settings are consistent with those in Table 1. Experimental results indicate that the OmniFC method exhibits superior efficacy and robustness. This will be included in the revised version.\n\n**Rebuttal Table D**. Kappa of clustering methods in different simulated federated scenarios. The proposed OmniFC-KM achieves superior performance. For each comparison within a given category (e.g., KM-based, FCM-based), the highest score is emphasized in bold.\n|$\\alpha$|1000|5|0.001|\n|----------|--------|--------|--------|\n|FedSC|0.71|**0.73**|0.59|\n|OmniFC-SC|**0.72**|0.72|**0.72**|\n|k-FED|0.58|0.48|0.51|\n|MUFC|0.61|0.61|0.60|\n|OmniFC-KM|**0.62**|**0.62**|**0.62**|\n|FFCM|0.60|0.52|0.54|\n|OmniFC-FCM|**0.66**|**0.66**|**0.66**|\n|FedMAvg|0.33|0.33|0.33|\n|OmniFC-NMF|**0.72**|**0.72**|**0.72**|"}]

Author rebuttal:

Meta-review: This paper focuses on the federated clustering problem and tackles the challenges of privacy and data heterogeneity. The proposed approach uses Lagrange coded computing (LCC): each client encrypts its local data using LCC, and shares the encoded data with peers to compute pairwise distances without directly revealing raw data. These distances are then shared with the server, and the server applies a centralized clustering method on the aggregated distance matrix. Theoretical guarantees are provided for reconstruction and privacy. Numerical experiments demonstrate the efficacy of the proposed method on several benchmarks. 

The reviewers identified the following strengths: addressing an important challenge, technical correctness, promising numerical results, and clarity of presentation. The main weaknesses noted were limited scalability, lack of time and computational complexity analysis, insufficient validation against modern approaches, and limited novelty. 

I read all reviews, rebuttals, and the paper itself; and I share some of these concerns. The central idea of lossless and secure reconstruction of a global distance matrix via LCC is elegant, but the theoretical guarantees are largely straightforward (this is why some reviewers found the contribution incremental). On the practical side, there are limitations in computation and communication overhead. While the term “federated” is used, in this context federation primarily refers to privacy through encryption, since the method is essentially one-shot (a single communication round) and the clustering itself is performed centrally on the reconstructed distance matrix.

Overall, I lean toward borderline accept since the idea of distance reconstruction via LCC is elegant and addresses an important problem, but the contribution feels incremental and scalability remains a concern, which limits significance.
Decision: Accept (poster)