OmniFC: Rethinking Federated Clustering via Lossless and Secure Distance Reconstruction¶

会议: NeurIPS 2025
arXiv: 2505.13071
代码: 待发布
领域: AI Safety / 联邦学习
关键词: 联邦聚类, Lagrange编码计算, 距离矩阵重建, 无损聚合, 安全计算

一句话总结¶

提出 OmniFC，一个模型无关的联邦聚类框架：通过 Lagrange 编码计算在有限域上精确重建全局成对距离矩阵，任意集中式聚类方法（K-Means/谱聚类/DBSCAN/层次聚类等）可直接在其上运行，仅需一轮通信，天然抵抗 Non-IID，在 7 个数据集上全面超越 k-FED/MUFC/FedSC 等专用方法。

研究背景与动机¶

领域现状：联邦聚类（FC）让分布式客户端不共享原始数据即可发现全局聚类结构。现有方法为特定聚类算法设计专用的代理聚合方案——联邦 K-Means 聚合质心、联邦谱聚类聚合核矩阵低秩因子、联邦 NMF 聚合基矩阵。
现有痛点：（a）代理聚合从有偏的客户端数据计算，在 Non-IID 设置下不可避免地引入信息损失，导致聚类性能显著退化——如 k-FED 在 COIL-100 上 p=1.0 时 Kappa 仅 0.43；（b）每种方法只能适配一种聚类算法，继承了其归纳偏置（如 KM 的紧凑性假设、SC 的连通性假设），无法适配任意聚类方法。
核心矛盾：现有 FC 方法是"一对一"扩展（centralized → federated），每额外支持一种聚类算法就需要重新设计一套聚合方案，根本不可扩展。
本文要解决什么？ 构建一个统一的模型无关框架，使任意集中式聚类方法都能直接用于联邦设置，同时保证隐私和抗 Non-IID 鲁棒性。
切入角度：关键洞察——聚类本质上只需要样本间的成对距离矩阵 \(D \in \mathbb{R}^{n \times n}\)。若能在不泄露原始数据的前提下精确重建全局距离矩阵，任何集中式聚类算法都可直接在 \(D\) 上运行。
核心idea一句话：用 Lagrange 编码计算实现全局成对距离矩阵的无损安全重建，将 FC 从"为每种算法定制聚合"解耦为"重建一次距离矩阵，适配所有算法"。

方法详解¶

整体框架¶

OmniFC 包含三个步骤：（1）Local Lagrange-Encoded Sharing：每个客户端用 Lagrange 多项式编码本地数据并分发给所有对等端；（2）Global Distance Reconstruction：每个客户端在编码数据上计算成对距离并发送给服务器，服务器通过 Lagrange 插值精确重建全局距离矩阵；（3）Cluster Assignment：在重建的距离矩阵上直接运行任意集中式聚类算法。仅需一轮通信。

关键设计¶

Lagrange 编码分享：
做什么：将每个样本 \(\tilde{x}_i\) 从实数域转换到有限域 \(\mathbb{F}_p^d\)，分成 \(l\) 段后加 \(t\) 个随机噪声，构造 \(l+t-1\) 次 Lagrange 插值多项式 \(f_{\tilde{x}_i}(\alpha)\)，在 \(m\) 个预约公共点 \(\{\beta_j\}\) 处求值得到编码表示 \(z_{i,j}\) 分发给第 \(j\) 个客户端
核心思路：每个客户端 \(j\) 最终持有所有 \(n\) 个样本在 \(\beta_j\) 处的编码表示 \(Z_j \in \mathbb{F}_p^{n \times d/l}\)——这是一个"全局编码数据集"，但任何单个客户端或 \(\leq t\) 个串通客户端都无法从中恢复原始数据（信息论安全）
设计动机：\(t\) 个噪声段确保 \(t\)-private 安全性。量化参数 \(q\) 控制实数→有限域的精度损失
全局距离重建：
做什么：每个客户端在其编码数据集上计算所有样本对的 L2 距离平方 \(dis(z_{i,j}, z_{i',j}) = \|z_{i,j} - z_{i',j}\|_2^2\)，发送给服务器
核心思路：由 Theorem 1 保证——当 \(m \geq 2l + 2t - 1\) 时，服务器可从 \(m\) 个客户端的编码距离通过 Lagrange 插值精确恢复真实距离 \(dis(\tilde{x}_i, \tilde{x}_{i'}) = \sum_{o=1}^l f_{\tilde{x}_i, \tilde{x}_{i'}}(\alpha_o)\)，与数据分布方式无关（天然抗 Non-IID）
设计动机：距离矩阵是"足够抽象"的全局结构——它完全由样本间关系决定，不受各客户端数据分布偏移影响
聚类分配：
做什么：在重建的全局距离矩阵 \(D\) 上直接运行任意聚类算法
对于距离依赖算法（SC、DBSCAN、HC、K-Medoids）：直接用 \(D\)，实现无损联邦扩展
对于非距离依赖算法（KM、FCM、NMF）：用 \(D\) 的行向量作为样本特征的代理，仍能有效聚类
设计动机：一次重建，多种算法受益——OmniFC-SC、OmniFC-KM、OmniFC-DBSCAN、OmniFC-HC 等 7 种变体

理论保证¶

Theorem 1（无损重建）：当 \(m \geq 2l + 2t - 1\) 时，距离可被精确恢复，与数据分布方式无关
Theorem 2（隐私安全）：在相同条件下，\(I(\tilde{x}_i; \{z_{i,j}\}_{j \in C}) = 0\)（\(|C| \leq t\)），即任意 \(\leq t\) 个串通客户端的互信息为零——信息论意义上的安全

实验关键数据¶

主实验（Table 1, Kappa↑）¶

数据集	FedSC	OmniFC-SC	k-FED	MUFC	OmniFC-KM	FFCM	OmniFC-FCM
Iris (p=0)	0.95	0.95	0.38	0.83	0.95	0.96	0.95
Iris (p=1)	0.31	0.95	0.71	0.77	0.95	0.97	0.95
COIL-100 (p=0)	0.34	0.54	0.48	0.49	0.56	0.37	0.53
COIL-100 (p=1)	0.27	0.54	0.43	0.52	0.56	0.51	0.53
10x_73k (p=0)	0.52	0.89	0.40	0.63	0.56	0.46	0.55
10x_73k (p=1)	0.24	0.89	0.30	0.79	0.56	0.64	0.55

跨 7 数据集 × 5 Non-IID 水平 × 4 算法族的胜出次数：OmniFC-SC 27/35, OmniFC-KM 24/35, OmniFC-NMF 30/35。

消融实验（Table 2, 通用性验证）¶

数据集	KMed_central	OmniFC-KMed	DBSCAN_central	OmniFC-DBSCAN	HC_central	OmniFC-HC
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
COIL-20	0.41	0.42	0.58	0.58	0.45	0.45
Pendigits	0.44	0.45	0.48	0.48	0.57	0.57

对于距离依赖算法（KMed/DBSCAN/HC），OmniFC 实现了与集中式完全一致的 Kappa——真正的无损联邦扩展。

关键发现¶

OmniFC 对 Non-IID 完全免疫：当 \(p\) 从 0→1 变化时，FedSC 在 10x_73k 上 Kappa 从 0.52 暴跌至 0.24，而 OmniFC-SC 始终保持 0.89——因为距离重建不受数据分布影响
模型无关性得到验证：7 种聚类算法（KM/SC/FCM/NMF/DBSCAN/HC/KMed）均可无缝接入 OmniFC，无需任何算法特定修改
距离矩阵可作为有效特征代理：对于不直接依赖距离的 KM/FCM/NMF，用距离矩阵行向量替代原始特征后，性能通常匹配甚至偶尔超越集中式
超参敏感性：只要 \(m \geq 2l + 2t - 1\)，RMSE 为零（理论精确）；增大 \(l\) 可显著降低客户端计算开销（70K 样本 l=8 时仅 4352s）
隐私-精度不矛盾：增加噪声 \(t\) 提升隐私保护级别，但只要 \(m\) 满足约束，不影响重建精度

亮点与洞察¶

"重建距离矩阵而非代理聚合"是一个优雅的抽象提升：将联邦聚类从"为每种算法定制一套聚合方案"转变为"一次重建全局距离矩阵"。这个思路可以推广——任何依赖成对关系的联邦任务（如联邦图学习）都可能受益
Lagrange 编码计算的双重功能：同一套编码方案同时实现了无损重建和信息论安全，且两者的约束条件完全一致（\(m \geq 2l + 2t - 1\)），不存在精度-隐私 trade-off
one-shot 通信：与 SecFC 需要多轮通信不同，OmniFC 仅需一轮——在模型市场等场景下更实用

局限性 / 可改进方向¶

\(O(n^2)\) 距离矩阵的可扩展性：10x_73k（70K 样本）需要 4352s 且矩阵大小 \(70K \times 70K\)，更大规模数据集不现实。可以考虑近似距离重建或分层聚类策略
有限域量化损失：实数→有限域映射通过 \(q\) 控制精度，对高维高精度场景可能不够
客户端数约束 \(m \geq 2l + 2t - 1\)：当 \(l\) 和 \(t\) 较大时需要足够多客户端，不完全适用于少客户端场景
MNIST/Fashion-MNIST 上提升有限：OmniFC-SC 在 MNIST 上仅 0.55，未显著超越 FedSC 的 0.53-0.58——说明对高维图像数据的距离矩阵可能不是最优特征表示

评分¶

新颖性: ⭐⭐⭐⭐⭐ "重建距离矩阵"的统一抽象 + 无损+安全的理论保证，思路优雅
实验充分度: ⭐⭐⭐⭐ 7 数据集 × 5 Non-IID 水平 × 7 聚类算法，覆盖全面；但缺乏大规模数据实验
写作质量: ⭐⭐⭐⭐ 理论推导清晰，定理和证明完整
价值: ⭐⭐⭐⭐ 联邦聚类的新范式，距离矩阵思路可推广到联邦图学习