作者：京东科技 李杰

联邦学习和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.

3.fate.readthedocs.io/en/develop/…

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.《图联邦学习发展与使用》 史春奇

10.github.com/FedML-AI/Fe…