【论文阅读总结】FedGraph: Federated Graph Learning With Intelligent Sampling

针对问题：

        分布式大规模图数据嵌入：1) GCN训练涉及到客户端之间的特征共享，导致隐私泄露的风险。2）大规模数据图带来的高训练开销。

现有的图采样方法及弊端：

        1、逐节点相邻采样（a）：为每个节点迭代采样固定数量的邻居（Graphsage、VR-GCN、Cluster-GCN）。弊端：层数增加，采样节点的数量可能呈指数级增加。且它在一些节点上导致了嵌入计算的冗余（采样得到的节点可能是其他节点的共享邻居）。

        2、分层重要性采样（b）：基于节点度计算的采样概率，为每个GCN层独立地采样固定数量节点（FastGCN）。弊端：由于不同层的节点是独立采样的，一些采样的节点可能与前一层中的节点没有连接，会降低训练性能。

假设性原则：

         每个客户端都知道由其他客户端维护的相邻节点的存在，但不能直接访问它的特征向量。

解决方案：

1、提出了一个联邦图学习系统FedGraph

参数服务器：

        1）基于DDPG的采样算法：为所有客户端生成采样策略。

        2）模型聚合器：收集客户端训练的局部特征权重，并聚合成新的全局特征权重。

        3）通信模块：参数服务器和客户端之间的消息交换。

 客户端：

        1）GCN训练模块：训练局部特征权重。客户端在处理第一个GCN层时，仅聚合客户端内部邻居的嵌入（等式2）；从第二层开始，客户端能够聚合内部邻居和外部邻居（等式3）。这样可以防止本地起源特征的泄露，同时实现信息共享。

         2）GCN构建模块：从随机选择一组带有标签的节点（迷你批次）开始。对于小批量中的每个节点，迭代地聚合最多 L-1跳之外的邻居的采样子集的嵌入。

算法第一行：对k_i标记的节点进行采样作为小批量，它们组成最后的L层。算法第二行开始，在反方向迭代地构建其他GCN层。对于第(L+1)层中的每个节点v，根据概率随机选择其邻居的子集N进入第L层。算法第五行，更新了采样后的相邻关系矩阵，用于特征聚合。

3）通信模块：参数服务器和客户端之间的消息交换。

2、设计了一个基于DDPG的采样算法为所有客户端生成采样策略（子图的节点选择）

状态空间：st={Wt,W1t,W2t,…,WCt} 。Wt：全局特征权重。WCt：客户端C的局部特征权重。使用PCA降维至20维。

动作空间：at={P1t,P2t,…,PCt}。PCt：客户端C的采样概率。

奖励：。δ[t]：本地训练时间。λ[t]：当前精度。Λ：目标精度。

基于DDPG的采样算法：

 参考文献：Chen F, Li P, Miyazaki T, et al. Fedgraph: Federated graph learning with intelligent sampling[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 33(8): 1775-1786.