作者：京东科技 李杰
联邦学习和GNN都是以后AI畛域的钻研热点。联邦学习的多个参与方能够在不泄露原始数据的状况下，平安合规地联结训练业务模型，目前已在诸多畛域获得了较好的后果。GNN在应答非欧数据结构时通常有较好的体现，因为它不仅思考节点自身的特色还思考节点之间的链接关系及强度，在诸如：异样个体辨认、链接预测、分子性质预测、天文拓扑图预测交通拥堵等畛域均有不俗体现。
那么GNN与联邦学习的强强组合又会擦出怎么的火花？
通常一个好的GNN算法须要丰盛的节点特色与残缺的连贯信息，但事实场景中数据孤岛问题比较突出，单个数据领有方往往只有无限的数据、特色、边信息，但咱们借助联邦学习技术就能够充分利用各方数据安全合规地训练有强劲体现的GNN模型。
读罢此文，您将取得如下知识点：
•GNN经典算法原理及计算模型
•联邦学习定义与分类
•联邦GNN的两种分类办法及细节
•基于横向联邦的FedGNN模型（微软亚研，2021）、基于纵向联邦的VFGNN模型（浙大+蚂蚁，2022）
一、GNN原理
1.1 图场景及数据表示
能用图刻画的场景很多，比方：社交网络、生物分子、电商网络、常识图谱等。
[]()
图最根底且通用的分类是将其分为：同构图（一种节点+一种边）与异构图（节点类型+边类型>2），相应的示意图如下。
[]()
一般来说，原始的图数据由两局部组成：节点数据（节点类型+节点ID+节点特色）、边数据（边类型+终点+起点）。原始数据通过解析解决后载入图存储模块，图存储的根本模式为邻接矩阵（COO），但个别出于存储与计算开销思考采纳稠密存储示意（CSC/CSR）。
1.2 GNN工作分类
[]()
GNN工作个别分为如下四类：
•节点/边分类：异样用户辨认。
•链接预测：user-item购物偏向、常识图谱补全。
•全图分类：生物分子性质预测。
•其余：图聚类、图生成。
1.3 GNN算法原理
咱们以GraphSAGE为例解说GNN的计算原理[1]，大抵蕴含三个过程：采样、聚合、拟合指标。GraphSAGE示意图如下：
[]()
GraphSAGE算法的伪代码如下：
[]()
上面咱们给合实例与公式具体阐明其计算过程，下图先给出采样过程与消息传递过程的框架原理。
[]()
下图给出了具体的消息传递执行过程。
[]()
二、联邦学习
之前机器学习模型训练的经典架构是：数据中心从各客户端或机构收集原始数据后，在数据中心对收集的整体数据进行模型训练。近年来随着数据隐衷爱护法规的颁布和数据安全意识的晋升，机构间替换明文数据就不可行了。如何综合多个用户或机构间数据来训练模型？联邦学习技术应运而生。联邦学习个别分为如下两大类[2]：
•联邦学习（横向）：两个机构领有较多雷同特色，然而重合样本ID很少。比方：北京医院和上海医院的病人数据。
•联邦学习（纵向）：两个机构领有较多雷同样本ID，然而机构间重合特色较少。比方：北京银行和北京保险公司的客户数据。
2.1 横向联邦学习
[]()
如上图所示，右边红虚线框内是数据表示，即重合样本较少，但特色雷同。左边是经典的横向FedAvg算法，每个客户端领有同样的模型构造，初始权重由server下发至客户端，待各客户端更新本地模型后，再将梯度/权重发送至server进行聚合，最初将聚合后果下发给各客户端以更新本地模型。
2.2 纵向联邦学习
[]()
如上图所示，右边红虚线框内代表数据表示，即两方领有较多雷同样本ID，然而重合特色较少。左边是经典的两方纵向DNN模型训练架构[3]，其中A方bottom层后果要发送至B方，而B方领有label，用来计算loss及梯度，具体过程参考[4]。
三、联邦GNN
3.1 联邦GNN分类
3.1.1 图对象+数据划分
依据图数据在客户端的散布规定，具体以图对象（图、子图、节点）与数据划分（横向、纵向）角度来看，能够将联邦GNN分为四类[5]：
1）inter-graph FL
[]()
在此分类中，客户端的每条样本是图数据，最终的全局模型解决图级别的工作。此架构广泛应用在生物工程畛域，通常用图来示意分子结构，其中节点示意原子，边示意原子间的化学键。在药物个性钻研方面能够利用此技术，每个制药厂k都保护了本人的分子-属性数据集
[]()
，但都不想分享给竞争对手。借助inter-graph FL技术，多家药厂就能够单干钻研药物性质。在此例中，全局模型为：
[]()
2）horizontal intra-graph FL
[]()
上图中全副客户端领有的数据形成残缺的图，其中虚线示意本应存在但理论不存在的边。此类架构中，每个客户端对应的子图领有雷同的特色空间和标签空间但领有不同的ID。在此设置下，全局GNN模型个别解决节点类工作和边工作：
[]()
[]()
3）vertical intra-graph FL
[]()
此类架构中，客户端共享雷同的ID空间，但不共享特色和标签空间。上图中的垂直虚线代表领有雷同ID的节点。在此架构中全局模型不惟一，这取决于多少客户端领有标签，同时也意味着此架构可进行multi-task learning。此架构次要用来以隐衷爱护的形式聚合各客户端雷同节点的特色，共享雷同节点的标签。如果不思考数据对齐和数据共享问题，则相应的指标函数定义为：
[]()
此架构个别利用在机构间单干，如反洗钱。犯罪分子采纳跨多个机构的简单策略进行洗钱流动，这时可利用此架构，通过机构间单干辨认出洗钱行为。
4）graph-structured FL
[]()
此架构用来示意客户端之间的拓扑关系，一个客户端相当于图中一个节点。此架构会基于客户端拓扑聚合本地模型，全局模型能够解决联邦学习畛域的各种工作和指标函数。全局GNN模型旨在通过客户端之间的拓扑关系开掘背地的隐含信息。此架构的经典利用是联邦交通流量预测，城市中的监控设施散布在不同的中央，GNN用来形容设施间的空间依赖关系。以上图为例全局GNN模型的聚合逻辑如下：
[]()
本节总结
[]()
3.1.2 二维分类法
依据参考文献[6]，咱们能够从2个维度对FedGNNs进行分类。第一个维度为主维度，聚焦于联邦学习与GNN如何联合；第二个维度为辅助维度，聚焦于联邦学习的聚合逻辑，用来解决不同level的图数据异构性。其分类汇总图大抵如下：
[]()
1）GNN-assisted FL
借助结构化的客户端来晋升联邦学习训练成果，用虚线来示意客户端之间的网络拓扑关系。此架构个别分为两种模式：
•中心化架构：领有客户端间的全局网络拓扑。可训练GNN模型晋升联邦聚合成果，也可帮忙客户端更新本地模型。
•非中心化架构：客户端间的全局网络拓扑必须提前给定，这样领有子图的客户端就能够找到它在图中的街坊。
2）FL-assisted GNN
借助扩散的图数据孤岛来晋升GNN模型成果，具体通过联邦学习把图数据孤岛组织起来训练一个全局GNN模型。依据客户端是否有雷同节点，此架构可分为如下两类：
•horizontal FedGNN：各客户端领有的重叠节点不多，有可能会失落跨客户端的链接，通常须要较简单的解决办法。
•vertical FedGNN：各客户端领有雷同的节点汇合，但持有的特色不雷同。依据特色的分区形式不同，相应的解决办法也随之变动。
3）Auxiliary taxonomy
辅助分类聚焦于解决联邦学习客户端之间的异构性问题。具体能够分为三类：
•客户端领有雷同ID：可将节点特色或两头表征上传至联邦服务器进行联邦聚合。罕用于vertical FedGNN和有局部反复节点的程度FedGNN。
•客户端领有不同节点但雷同网络结构：联邦聚合对象次要是模型权重和梯度。罕用于GNN-assisted FL和无反复节点的horizontal FedGNN。
•客户端领有不同网络结构：先把本地模型做成图，而后将GNN作用于图之上。联邦聚合对象是GNN权重和梯度，罕用于centralized FedGNN。
3.2 FedGNN
3.2.1 问题定义
[]()
3.2.2 FedGNN原理与架构
[]()
如上图，FedGNN[7]由一个核心服务器和大量客户端组成。客户端基于其用户交互物品与街坊客户端在本地保护了一个子图。客户端基于本地子图学习user/item embedding，以及GNN模型，而后将梯度上传给核心服务器。核心服务器用来协调客户端，具体是在训练过程中聚合从多个客户端收集的梯度（基于FedAvg算法），并将聚合后的梯度回传给客户端。如下咱们将顺次介绍一些技术细节。
[]()
FedGNN的残缺算法流程见下述Algorithm1，其中有两个隐衷爱护模块：其一是隐衷爱护模型更新（Algorithm1的9-11行），用来爱护梯度信息；其二是隐衷爱护user-item图裁减模块（Algorithm1中第15行），用来对user和item的高阶交互进行建模。
[]()
3.2.3 隐衷爱护模型更新
embedding梯度和模型梯度（GNN+rating predictor）间接传输会泄露隐衷，因而须要对此进行平安防护。因为每个客户端保护了全量item的embedding表，通过同态加密爱护梯度就不太事实（大量的存储和通信开销），文献[7]提出两个机制来爱护模型更新过程中的隐衷爱护。
1）伪交互物品采样
随机采样M个用户并未交互过的物品，依据交互物品embedding梯度散布随机生成伪交互物品embedding梯度。于是第i个用户的模型和embedding梯度批改为
[]()
2）采纳LDP（本地差分隐衷）护本地梯度
首先通过梯度的无穷范数和阈值 对梯度进行截断，而后基于LDP思维采纳0均值拉普拉斯噪声对前述梯度进行扰动，从而实现对用户隐衷的爱护。相应的公式表白为：
g i=clip(g i,)+Laplace(0,)。受爱护的梯度再上传到核心服务器进行聚合。
3.2.4 隐衷爱护图裁减
客户端本地user-item图以隐衷保护方式找到街坊客户端，以达到对本地图本身的裁减。在中心化存储的GNN场景中，user与item的高阶交互可通过全局user-item图不便获取。但非中心化场景中，在恪守隐衷爱护的前提下要想求得user-item高阶交互不是易事。文章提出通过寻找客户端的匿名街坊以晋升user和item的表征学习，同时用户隐衷不泄露，具体过程如下：
[]()
首先，核心服务器生成公钥并分发给各客户端。客户端收到公钥后，利用同态加密技术对交互物品ID进行加密解决。前述加密ID和用户embedding被上传至第三方服务器（不须要可信），通过PSI技术找到有雷同交互物品的用户，而后为每个用户提供匿名街坊embedding。最初，咱们把用户的街坊用户节点连接起来，这样就以隐衷爱护的形式增加了user-item的高阶交互信息，丰盛了客户端的本地user-item子图。
3.3 VFGNN
3.3.1 数据假如
训练一个好的GNN模型通常须要丰盛的节点特色和残缺的连贯信息。然而节点特色和连贯信息通常由多个数据方领有，也就是所谓的数据孤岛问题。下图咱们给出图数据纵向划分的例子[8]，其中三方各自领有节点不同的特色，各方领有不同类型的边。
[]()
3.3.2 算法架构及流程
安全性假如：数据领有方A,B,C和服务器S都是半诚恳的，并且假设服务器S和任一数据领有方不会合谋。这个平安假如合乎大多数已有工作，并且和事实场景比拟符合。
[]()
上图即为VFGNN的架构图，它的计算分为两大部分：
•隐衷数据相干计算：个别在数据领有方本地进行。在GNN场景中，隐衷数据有：节点特色、label、边信息。
•非隐衷数据相干计算：个别将计算权委托给半诚恳server，次要是出于计算效率的思考。
思考到数据隐衷性的问题，上述计算图分为如下三个计算子图，且各自承当的工作如下：
•CG1：隐衷特色和边相干计算。 先利用节点隐衷特色生成initial node embedding，这个过程是多方协同工作的。接着通过采样找到节点的多跳街坊，再利用聚合函数生成local node embedding。
•CG2：非隐衷数据相干计算。 出于效率思考，作者把非隐衷数据相干计算委托给半诚恳服务器。此服务器把从各方收集的local node embedding通过不同的COMBINE策略解决生成global node embedding。接着能够进行若干明文类的操作，比方max-pooling、activation（这些计算在密文状态下不敌对）。进行一系列明文解决后，咱们失去最初一个隐层输入ZL，而后把它发送给领有label的数据方计算预测值。
•CG3：隐衷标签相干计算。 以节点分类工作为例 ，当收到ZL后能够疾速计算出预测值，具体通过softmax函数进行解决。
3.3.3 重要组件
Generating Initial Node Embedding
[]()
如果各方独立生成initial node embedding（上图a），则遵循如下计算公式：
[]()
如果各方协同生成initial node emb，则可按上图b中利用MPC技术进行解决。
Generating Local Node Embedding
基于前述生成的initial node embedding，及节点的多跳街坊节点，利用聚合函数能够生成local node embedding。街坊节点的聚合操作必须在本地进行而不须要多方协同，目标是爱护隐衷的边信息。一个节点的街坊节点聚合操作和惯例GNN一样，以GraphSAGE为例节点的聚合操作是通过采样和聚合特色造成了local node embedding，具体公式如下：
[]()
GraphSAGE中，罕用的聚合函数有：Mean、LSTM、Pooling。接着数据领有方把local node embedding发送给半诚恳服务器，以进行COMBINE操作及后续的非隐衷数据计算逻辑。
Generating Global Node Embedding
对各方传来的local node embedding执行combine操作能够生成global node embedding。combine策略个别是可训练且高表白容量，文章给出了三种策略：
1）Concat
[]()
2）Mean
[]()
3）Regression
[]()
3.3.4 隐衷爱护DP
如果在前向过程中把local node embedding间接传给半诚恳服务器，或在反向流传过程中间接传递梯度信息很可能造成信息泄露。本文提出了两种基于DP的办法用来爱护信息公布过程，算法流程如下：
[]()
3.3.5 VFGNN前向算法
以GraphSAGE解决节点分类工作为例，VFGNN算法的前向过程形容如下：
[]()
3.4 其余算法及我的项目
最近四年呈现的联邦GNN算法[9]：
[]()
开源我的项目有：FedGraphNN[10]。
参考资料
1.Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[J]. Advances in neural information processing systems, 2017, 30.
2.Yang Q, Liu Y, Chen T, et al. Federated machine learning: Concept and applications[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2019, 10(2): 1-19.
- https://fate.readthedocs.io/e...
4.Zhang Y, Zhu H. Additively homomorphical encryption based deep neural network for asymmetrically collaborative machine learning[J]. arXiv preprint arXiv:2007.06849, 2020.
5.Zhang H, Shen T, Wu F, et al. Federated graph learning--a position paper[J]. arXiv preprint arXiv:2105.11099, 2021.
6.Liu R, Yu H. Federated graph neural networks: Overview, techniques and challenges[J]. arXiv preprint arXiv:2202.07256, 2022.
7.Wu C, Wu F, Cao Y, et al. Fedgnn: Federated graph neural network for privacy-preserving recommendation[J]. arXiv preprint arXiv:2102.04925, 2021.
8.Chen C, Zhou J, Zheng L, et al. Vertically federated graph neural network for privacy-preserving node classification[J]. arXiv preprint arXiv:2005.11903, 2020.
9.《图联邦学习停顿与利用》 史春奇
- https://github.com/FedML-AI/F...