论文标题：FEDGS: Federated Graph-based Sampling with Arbitrary Client Availability
论文地址：https://arxiv.org/abs/2211.13975
论文代码：https://github.com/WwZzz/FedGS
论文作者：王铮（厦门大学）, 范晓亮（通讯作者，厦门大学）, Jianzhong Qi（University of Melbourne）, 金海炳（厦门大学）, 杨佩蓁（厦门大学）, 沈思淇（厦门大学）, 王程（厦门大学）
本文介绍的是厦门大学空间感知与计算ASC实验室（asc.xmu.edu.cn）近期被 AAAI-23 会议接收的一篇论文工作：「FEDGS: Federated Graph-based Sampling with Arbitrary Client Availability」。AAAI Conference on Artificial Intelligence系列会议是人工智能领域最重要的国际会议之一，是CCF A类推荐会议，每年举办一届。AAAI-23将于2023年2月7～14日在美国华盛顿特区举行。本次AAAI-23共有8777篇投稿，录用1721篇，录用率约为19.6%。
本文针对联邦学习中用户普遍存在的间歇可用性造成的系统异质性难题，设计了一个满足任意用户可用性约束的联邦图采样优化方法（简称FedGS），以同时保障模型更新的稳定性及缓解模型训练过程的长期偏差，并从理论上证明了该方法能够逼近对用户全采样时的模型更新量。
一、研究背景和挑战
为了减少通信开销，联邦学习系统在训练时通常会对用户进行采样。然而，忽视了用户是否处于活跃状态的采样策略将无限延长系统等待时间。例如，现有工作大多仅采样部分活跃用户来保证即时（不稳定）的用户可用性。如图1所示，在t-1轮时，由于用户A和B不可用，服务器将不会采样它们。然而，在任意用户可用性（对任意用户是否可用不做假设）的约束下，如何使模型快速稳定地收敛，并缓解用户可用性的异构带来的长期偏差，面临两个亟待解决的研究挑战：
挑战1: 如何保障全局模型的稳定更新。在联邦训练的每一轮中，由于联邦学习“数据可用不可见”的假设，导致服务器无法观测到用户之间的数据异质性。因此，传统的采样策略所采样的用户数据分布往往难以代表全局数据分布，最终导致模型更新的不稳定，并增大了模型收敛所需的通信轮数。如图1所示，Fair-Selection策略旨在保证每个用户的最少采样次数，故能够缓解长期偏差。然而，该策略仅考虑用户采样次数的平衡，而忽视了t+1轮中用户B和C的红色类型数据。
挑战2: 如何缓解模型的长期训练偏差。在联邦学习的训练过程中，模型更新的方向往往被那些长期活跃用户的数据分布主导，这将不可避免地损害联邦系统的数据特异性。现有采样策略仅考虑了保障模型更新的稳定性，而忽略了服务器对高可用性用户的固有采样偏好所导致的长期训练偏差。如图1所示，MDSample策略旨在优先采样本地数据量大的用户以加快和稳定收敛，而Variance-Reduce策略则仅考虑减小梯度估计的方差以保障全局模型稳定更新。然而，上述两种策略均未考虑用户是否可用的差异性，从而导致了全局模型被可用性更高的用户带偏了（例如，用户A因不可用而在前两轮均未被采样；然而，t+1轮时用户A已经可用了，它仍然不被FL系统采样，故极有可能造成了训练偏差）。
图1 ：联邦采样策略示意图
因此，针对不稳定的全局模型更新和有偏差的联邦训练过程，本文提出了一种满足任意用户可用性约束的基于图的联邦采样优化方法（简称FedGS）。首先，使用数据分布依赖图（Data-Distribution-Dependency Graph，简称3DG）对用户数据相关性进行建模，以保证采样用户数据分布的多样性；其次，最小化用户采样次数的方差，以缓解联邦训练过程中的长期偏差；最后，在7种用户可用性模式和Synthetic(0.5, 0.5)、CIFAR10、FashionMNIST三个数据集上开展大量实验验证。结果表明，本文提出的FedGS 方法在实现公平的用户采样方案和提高任意用户可用性下的模型性能方面均具有显著优势。本文的研究成果，有效揭示了联邦学习用户采样过程的复杂动态机制，即用户普遍存在的间歇可用性将导致模型更新不稳定和联邦训练过程的长期偏差。
二、问题形式化
定义1:采样无偏性。当用户数量庞大时，由于通信开销的限制，需要随机采样用户子集来获得所有用户模型更新的估计。此时，收敛的保证需要满足以下无偏条件：
其中，是t+1时刻的全局模型，
表示用户K在t+1时刻的本地模型，
表示用户K的本地数据集大小，
表示总的数据大小。
定义2: 估计方差。Fraboni等人和Balakrishnan等人为了更快和更稳定的训练，提出减小估计方差：
其中，表示全局模型在第t轮的梯度。
定义3: 采样次数方差。表示第t轮可用的用户集合，那么采样用户集合
需要满足
且
，其中M是服务器容量决定的最大采样数量。
表示N个用户在t轮后的采样次数，其中
。定义用户采样次数的方差：
问题定义：只对采样次数进行平衡可能会引入模型更新的方差导致收敛变慢。为了实现稳定的训练，本文将低模型更新方差作为一项约束来求最小化采样次数方差：
其中，是一个超参数，允许在稳定模型更新和平衡用户采样这两个目标之间进行权衡。当
时，最优的策略会选择当前采样次数最少的可用用户；
很小则将采样策略限制为模型更新方差足够小的用户。
三、FedGS算法框架
图2 ：两种数据分布的例子：(a) 容易聚类；(b) 难以聚类
数据分布依赖图（Data-Distribution-Dependency Graph，简称3DG）。为了优化上述问题，本文将模型更新的方差约束转化为可解约束来提升采样用户数据分布的多样性。对用户数据分布建模，现有的方法大多采用聚类，如图2(a)所示，它们在用户数据分布容易聚类时效果良好。然而，当数据分布如图2(b)所示难以聚类时，聚类的方法就难以捕捉用户之间的复杂数据相关性。为了更好地描述用户之间的数据分布，本文提出了数据分布依赖图（3DG）。如图3所示，在CIFAR-10数据集上使用3DG对20个用户的数据分布建模，其中每个用户只含有两类标签的数据。基于3DG，对图上的用户进行采样，通过保持采样节点之间较大的平均最短路径来提高模型更新的稳定性。直观来说，3DG通过鼓励采样节点尽可能地扩散来保持采样节点数据分布的多样性，从而为整个模型更新产生良好稳定的近似值。
在FL中建立数据分布依赖图。为了计算用户数据分布的距离，本文假设存在一个特征向量可以很好地表示用户
的数据分布。本文提出了两种建立3DG的方法：
1）基于Secure Scalar Product Protocols（SSPP）的用户标签向量法。首先，使用用户数据的标签向量作为用户的特征向量：；其次，使用相似度函数
计算每个用户两两之间的相似度获得相似度矩阵：
；最后，将相似度矩阵V转换为邻接矩阵R：
其中，是一个阈值用来控制邻接矩阵的稀疏性，
用来控制边权的多样性，大的会导致边权差异小。为了防止特征向量泄露用户隐私，在计算用户相似度时使用基于SSPP的方法，详情见论文。
2）基于模型参数的函数相似法。首先，给所有本地模型分配一批随机高斯噪声：，其中μ和
分别是服务器拥有的小型数据集的均值和协方差；其次，用这个批数据在每个用户模型第
层上的嵌入
计算相似性：
FedGS算法。首先，给定一个3DG，使用Floyd–Warshall算法计算所有用户两两之间的最短路径距离矩阵。其次，令
表示用户
在第t轮被采样，
则表示未被采样，那么第t轮的采样结果可以表示为：
，那么被采样用户之间的平均最短路径距离可以表示为：
。因此，本文将第3节问题定义中所述的模型更新方差约束项替换为
，并且将这一项作为正则项添加到优化目标中。最后，将第3节中的优化目标重新定义为一个基于
的最大化问题：
其中，表示用户
在第t轮是可用的。注意到对于第t轮不可用的用户，
且
。因此，上式可以被简化为：
聚合权重。本文对采样用户的本地数据量大小进行归一化作为模型聚合的权重：
四、实验与验证
数据集：本文使用了3个常用的联邦数据集：Synthetic (0.5, 0.5)、CIFAR10和FashionMNIST。对于Synthetic数据集，本文参考了MLSys-2020的Li et al.论文，构造了30个用户的不平衡且non-i.i.d.的数据集；对于CIFAR10数据集，本文参考了arXiv上Hsu et al.论文，根据标签分布将数据集不均衡地分配给100个用户；对于FashionMNIST，本文将数据集均衡地分给100个用户，且每个用户仅持有两类标签数据。
模型：对于Synthetic 数据集，本文使用逻辑回归模型；对于CIFAR10和FashionMNIST，本文使用CNN模型。
评价指标：使用测试集上的最优损失来衡量算法的性能，使用用户被采样次数来衡量采样的公平性。
用户可用性：本文总结了现有的用户可用性模式。表1提出了一套包含7种用户可用性模式的评估体系。对于任何一种模式，本文设置了一个参数来控制整体不可用的程度，越大，则用户可用的概率更小。更多细节请见论文。
更多数据集描述、baseline介绍和各种参数设置等细节信息，请见论文Appendix。
表 1：7种用户可用性模式
实验结果1. 性能比较
表 2：三个数据集上不同用户可用性模式下，各方法的最优测试集损失结果
如表2所示，本文提出的FedGS 在七种用户可用性模式下均取得最优（LN、SLN、LDF、YMF、YC）或接近最优（IDL和MDF）的效果。对于IDL模式，相比于UniformSample和MDSample，FedGS依然具备竞争力；对于MDF模式，尽管Power-of-Choice取得了最优效果，但是它的性能在不同的模式下是极其不稳定的。同时，使用相比于
在大多数模式下都带来了显著性能提升，这证明了FedGS减小模型更新方差的方法是有益于联邦训练的。表2结果的细节分析请见论文。
实验结果2. 用户采样公平性
图 4：FashionMNIST-YMF-0.9和Cifar10-LN-0.5上的最终用户采样次数
图 5：FashionMNIST-YMF-0.9和Cifar10-LN-0.5上的测试损失曲线
如图4所示，FedGS 在FashionMNIST-YMF-0.9和Cifar10-LN-0.5上的最终用户采样次数更均衡，显著提高了用户采样的公平性。如图5所示，FedGS使联邦训练过程更加稳定，并且在用户不完全可用的情况下获得了更优结果。
实验结果3. 基于模型参数的函数相似性建立3DG的有效性
表 3：基于模型参数的函数相似性和余弦相似性建立3DG的有效性对比
为了验证本文基于模型参数的函数相似性（functional similarity）重建理想情形的图的方法的有效性，通过预测理想情形的图中的边计算得到F1值来衡量重建的质量，将余弦相似性（cosine similarity）作为比较方法。结果如表3所示，基于模型参数的函数相似性在两个数据集上都获得了更高的F1值，证明了FedGS方法有效地重建了理想情形的图结构。详细的参数设置和实现细节请见论文。
五、理论证明
本文证明了在适当条件下，FedGS通过鼓励所采样的用户在3DG上的平均最短路径足够远，能够更好地近似全采样用户时的模型更新，从而从理论角度揭示了FedGS的内在机制。为了达到这个目的，本文首先假设数据集中只存在有限种类型的数据（对于MNIST数据集，仅存在10类标签的数据），以及3DG是一个完全图。其次，本文计算所采样用户的数据类型分布在数据类型超球面上所能够覆盖的区域，并分析全采样模型更新落在该区域的概率P。最后，我们揭示了较大的平均最短路径将鼓励概率P具有更大的值，从而说明FedGS能够更好地近似全采样用户时的模型更新量。具体证明细节请参见论文附录。
六、总结与展望
本文在七种任意用户可用性模式下，同时解决了模型更新不稳定和联邦训练长期偏差的问题，实现了更快、更稳定的联邦训练。本文提出了一种满足任意用户可用性约束的基于图的联邦采样优化方法（简称FedGS）。该方法首先使用数据分布依赖图（3DG）对用户的数据相关性进行建模，并基于数据分布依赖图对用户采样，使模型更新更加稳定。其次，为了缓解长期偏差，在远距离3DG约束下，最小化了用户被采样次数的方差。本文在7个用户可用性模式下对3个真实数据集的实验结果验证了FedGS对任意用户可用性模式的有效性。同时，我们从理论上证明了FedGS能够逼近对用户全采样时的模型更新量。未来，我们拟进一步研究如何在各种机器学习任务中更好地定义和构建3DG。本文的研究成果，有效揭示了联邦学习用户采样过程的复杂动态机制，即用户普遍存在的间歇可用性将导致全局模型更新发散和联邦训练过程的长期偏差。
论文链接：https://arxiv.org/abs/2211.13975
论文代码：https://github.com/WwZzz/FedGS
联系作者：范晓亮（通讯作者，fanxiaoliang@xmu.edu.cn）、王铮（zwang@stu.xmu.edu.cn）
*** 欢迎关注本研究小组动态：https://fanxlxmu.github.io ***