GNN與聯(lián)邦學(xué)習(xí)的強(qiáng)強(qiáng)組合又會(huì)擦出怎樣的火花？

聯(lián)邦學(xué)習(xí)和 GNN 都是當(dāng)前 AI 領(lǐng)域的研究熱點(diǎn)。聯(lián)邦學(xué)習(xí)的多個(gè)參與方可以在不泄露原始數(shù)據(jù)的情況下，安全合規(guī)地聯(lián)合訓(xùn)練業(yè)務(wù)模型，目前已在諸多領(lǐng)域取得了較好的結(jié)果。GNN 在應(yīng)對(duì)非歐數(shù)據(jù)結(jié)構(gòu)時(shí)通常有較好的表現(xiàn)，因?yàn)樗粌H考慮節(jié)點(diǎn)本身的特征還考慮節(jié)點(diǎn)之間的鏈接關(guān)系及強(qiáng)度，在諸如：異常個(gè)體識(shí)別、鏈接預(yù)測(cè)、分子性質(zhì)預(yù)測(cè)、地理拓?fù)鋱D預(yù)測(cè)交通擁堵等領(lǐng)域均有不俗表現(xiàn)。

那么 GNN 與聯(lián)邦學(xué)習(xí)的強(qiáng)強(qiáng)組合又會(huì)擦出怎樣的火花？ 通常一個(gè)好的 GNN 算法需要豐富的節(jié)點(diǎn)特征與完整的連接信息，但現(xiàn)實(shí)場(chǎng)景中數(shù)據(jù)孤島問(wèn)題比較突出，單個(gè)數(shù)據(jù)擁有方往往只有有限的數(shù)據(jù)、特征、邊信息，但我們借助聯(lián)邦學(xué)習(xí)技術(shù)就可以充分利用各方數(shù)據(jù)安全合規(guī)地訓(xùn)練有強(qiáng)勁表現(xiàn)的 GNN 模型。

一、GNN 原理

1.1 圖場(chǎng)景及數(shù)據(jù)表示

能用圖刻畫(huà)的場(chǎng)景很多，比如：社交網(wǎng)絡(luò)、生物分子、電商網(wǎng)絡(luò)、知識(shí)圖譜等。



圖最基礎(chǔ)且通用的分類是將其分為：同構(gòu)圖（一種節(jié)點(diǎn) + 一種邊）與異構(gòu)圖（節(jié)點(diǎn)類型 + 邊類型 > 2），相應(yīng)的示意圖如下。



一般來(lái)說(shuō)，原始的圖數(shù)據(jù)由兩部分組成：節(jié)點(diǎn)數(shù)據(jù)（節(jié)點(diǎn)類型 + 節(jié)點(diǎn) ID + 節(jié)點(diǎn)特征）、邊數(shù)據(jù)（邊類型 + 起點(diǎn) + 終點(diǎn)）。原始數(shù)據(jù)經(jīng)過(guò)解析處理后載入圖存儲(chǔ)模塊，圖存儲(chǔ)的基本形式為鄰接矩陣（COO），但一般出于存儲(chǔ)與計(jì)算開(kāi)銷考慮采用稀疏存儲(chǔ)表示（CSC/CSR）。

1.2 GNN 任務(wù)分類

GNN 任務(wù)一般分為如下四類：

?節(jié)點(diǎn) / 邊分類：異常用戶識(shí)別。

?鏈接預(yù)測(cè)：user-item 購(gòu)物傾向、知識(shí)圖譜補(bǔ)全。

?全圖分類：生物分子性質(zhì)預(yù)測(cè)。

?其他：圖聚類、圖生成。

1.3 GNN 算法原理

我們以 GraphSAGE 為例講解 GNN 的計(jì)算原理 [1]，大致包含三個(gè)過(guò)程：采樣、聚合、擬合目標(biāo)。GraphSAGE 示意圖如下：



GraphSAGE 算法的偽代碼如下：



下面我們給合實(shí)例與公式詳細(xì)說(shuō)明其計(jì)算過(guò)程，下圖先給出采樣過(guò)程與消息傳遞過(guò)程的框架原理。



下圖給出了具體的消息傳遞執(zhí)行過(guò)程。

二、聯(lián)邦學(xué)習(xí)

之前機(jī)器學(xué)習(xí)模型訓(xùn)練的經(jīng)典架構(gòu)是：數(shù)據(jù)中心從各客戶端或機(jī)構(gòu)收集原始數(shù)據(jù)后，在數(shù)據(jù)中心對(duì)收集的全體數(shù)據(jù)進(jìn)行模型訓(xùn)練。近年來(lái)隨著數(shù)據(jù)隱私保護(hù)法規(guī)的頒布和數(shù)據(jù)安全意識(shí)的提升，機(jī)構(gòu)間交換明文數(shù)據(jù)就不可行了。如何綜合多個(gè)用戶或機(jī)構(gòu)間數(shù)據(jù)來(lái)訓(xùn)練模型？聯(lián)邦學(xué)習(xí)技術(shù)應(yīng)運(yùn)而生。聯(lián)邦學(xué)習(xí)一般分為如下兩大類 [2]：

?聯(lián)邦學(xué)習(xí)（橫向）：兩個(gè)機(jī)構(gòu)擁有較多相同特征，但是重合樣本 ID 很少。比如：北京醫(yī)院和上海醫(yī)院的病人數(shù)據(jù)。

?聯(lián)邦學(xué)習(xí)（縱向）：兩個(gè)機(jī)構(gòu)擁有較多相同樣本 ID，但是機(jī)構(gòu)間重合特征較少。比如：北京銀行和北京保險(xiǎn)公司的客戶數(shù)據(jù)。

2.1 橫向聯(lián)邦學(xué)習(xí)

如上圖所示，左邊紅虛線框內(nèi)是數(shù)據(jù)表示，即重合樣本較少，但特征相同。右邊是經(jīng)典的橫向 FedAvg 算法，每個(gè)客戶端擁有同樣的模型結(jié)構(gòu)，初始權(quán)重由 server 下發(fā)至客戶端，待各客戶端更新本地模型后，再將梯度 / 權(quán)重發(fā)送至 server 進(jìn)行聚合，最后將聚合結(jié)果下發(fā)給各客戶端以更新本地模型。

2.2 縱向聯(lián)邦學(xué)習(xí)

如上圖所示，左邊紅虛線框內(nèi)代表數(shù)據(jù)表示，即兩方擁有較多相同樣本 ID，但是重合特征較少。右邊是經(jīng)典的兩方縱向 DNN 模型訓(xùn)練架構(gòu) [3]，其中 A 方 bottom 層結(jié)果要發(fā)送至 B 方，而 B 方擁有 label，用來(lái)計(jì)算 loss 及梯度，詳細(xì)過(guò)程參考 [4]。

三、聯(lián)邦 GNN

3.1 聯(lián)邦 GNN 分類

3.1.1 圖對(duì)象 + 數(shù)據(jù)劃分

根據(jù)圖數(shù)據(jù)在客戶端的分布規(guī)則，具體以圖對(duì)象（圖、子圖、節(jié)點(diǎn)）與數(shù)據(jù)劃分（橫向、縱向）角度來(lái)看，可以將聯(lián)邦 GNN 分為四類 [5]： 1）inter-graph FL



在此分類中，客戶端的每條樣本是圖數(shù)據(jù)，最終的全局模型處理圖級(jí)別的任務(wù)。此架構(gòu)廣泛應(yīng)用在生物工程領(lǐng)域，通常用圖來(lái)表示分子結(jié)構(gòu)，其中節(jié)點(diǎn)表示原子，邊表示原子間的化學(xué)鍵。在藥物特性研究方面可以應(yīng)用此技術(shù)，每個(gè)制藥廠 k 都維護(hù)了自己的分子 - 屬性數(shù)據(jù)集 ，但都不想分享給競(jìng)爭(zhēng)對(duì)手。借助 inter-graph FL 技術(shù)，多家藥廠就可以合作研究藥物性質(zhì)。在此例中，全局模型為： 2）horizontal intra-graph FL



上圖中全部客戶端擁有的數(shù)據(jù)構(gòu)成完整的圖，其中虛線表示本應(yīng)存在但實(shí)際不存在的邊。此類架構(gòu)中，每個(gè)客戶端對(duì)應(yīng)的子圖擁有相同的特征空間和標(biāo)簽空間但擁有不同的 ID。在此設(shè)置下，全局 GNN 模型一般處理節(jié)點(diǎn)類任務(wù)和邊任務(wù)：



3）vertical intra-graph FL



此類架構(gòu)中，客戶端共享相同的 ID 空間，但不共享特征和標(biāo)簽空間。上圖中的垂直虛線代表?yè)碛邢嗤?ID 的節(jié)點(diǎn)。在此架構(gòu)中全局模型不唯一，這取決于多少客戶端擁有標(biāo)簽，同時(shí)也意味著此架構(gòu)可進(jìn)行 multi-task learning。此架構(gòu)主要用來(lái)以隱私保護(hù)的方式聚合各客戶端相同節(jié)點(diǎn)的特征，共享相同節(jié)點(diǎn)的標(biāo)簽。如果不考慮數(shù)據(jù)對(duì)齊和數(shù)據(jù)共享問(wèn)題，則相應(yīng)的目標(biāo)函數(shù)定義為：



此架構(gòu)一般應(yīng)用在機(jī)構(gòu)間合作，如反洗錢(qián)。犯罪分子采用跨多個(gè)機(jī)構(gòu)的復(fù)雜策略進(jìn)行洗錢(qián)活動(dòng)，這時(shí)可應(yīng)用此架構(gòu)，通過(guò)機(jī)構(gòu)間合作識(shí)別出洗錢(qián)行為。

4）graph-structured FL



此架構(gòu)用來(lái)表示客戶端之間的拓?fù)潢P(guān)系，一個(gè)客戶端相當(dāng)于圖中一個(gè)節(jié)點(diǎn)。此架構(gòu)會(huì)基于客戶端拓?fù)渚酆媳镜啬Ｐ?，全局模型可以處理?lián)邦學(xué)習(xí)領(lǐng)域的各種任務(wù)和目標(biāo)函數(shù)。

全局 GNN 模型旨在通過(guò)客戶端之間的拓?fù)潢P(guān)系挖掘背后的隱含信息。此架構(gòu)的經(jīng)典應(yīng)用是聯(lián)邦交通流量預(yù)測(cè)，城市中的監(jiān)控設(shè)備分布在不同的地方，GNN 用來(lái)描述設(shè)備間的空間依賴關(guān)系。

以上圖為例全局 GNN 模型的聚合邏輯如下：



本節(jié)總結(jié)

3.1.2 二維分類法

根據(jù)參考文獻(xiàn) [6]，我們可以從 2 個(gè)維度對(duì) FedGNNs 進(jìn)行分類。第一個(gè)維度為主維度，聚焦于聯(lián)邦學(xué)習(xí)與 GNN 如何結(jié)合；第二個(gè)維度為輔助維度，聚焦于聯(lián)邦學(xué)習(xí)的聚合邏輯，用來(lái)解決不同 level 的圖數(shù)據(jù)異構(gòu)性。其分類匯總圖大致如下：



1）GNN-assisted FL

借助結(jié)構(gòu)化的客戶端來(lái)提升聯(lián)邦學(xué)習(xí)訓(xùn)練效果，用虛線來(lái)表示客戶端之間的網(wǎng)絡(luò)拓?fù)潢P(guān)系。此架構(gòu)一般分為兩種形式：

?中心化架構(gòu)：擁有客戶端間的全局網(wǎng)絡(luò)拓?fù)??？捎?xùn)練 GNN 模型提升聯(lián)邦聚合效果，也可幫助客戶端更新本地模型。

?非中心化架構(gòu)：客戶端間的全局網(wǎng)絡(luò)拓?fù)浔仨毺崆敖o定，這樣擁有子圖的客戶端就可以找到它在圖中的鄰居。

2）FL-assisted GNN

借助分散的圖數(shù)據(jù)孤島來(lái)提升 GNN 模型效果，具體通過(guò)聯(lián)邦學(xué)習(xí)把圖數(shù)據(jù)孤島組織起來(lái)訓(xùn)練一個(gè)全局 GNN 模型。根據(jù)客戶端是否有相同節(jié)點(diǎn)，此架構(gòu)可分為如下兩類：

?horizontal FedGNN：各客戶端擁有的重疊節(jié)點(diǎn)不多，有可能會(huì)丟失跨客戶端的鏈接，通常需要較復(fù)雜的處理方法。

?vertical FedGNN：各客戶端擁有相同的節(jié)點(diǎn)集合，但持有的特征不相同。根據(jù)特征的分區(qū)方式不同，相應(yīng)的處理方法也隨之變化。

3）Auxiliary taxonomy 輔助分類聚焦于解決聯(lián)邦學(xué)習(xí)客戶端之間的異構(gòu)性問(wèn)題。具體可以分為三類：

?客戶端擁有相同 ID：可將節(jié)點(diǎn)特征或中間表征上傳至聯(lián)邦服務(wù)器進(jìn)行聯(lián)邦聚合。常用于 vertical FedGNN 和有部分重復(fù)節(jié)點(diǎn)的水平 FedGNN。

?客戶端擁有不同節(jié)點(diǎn)但相同網(wǎng)絡(luò)結(jié)構(gòu)：聯(lián)邦聚合對(duì)象主要是模型權(quán)重和梯度。常用于 GNN-assisted FL 和無(wú)重復(fù)節(jié)點(diǎn)的 horizontal FedGNN。

?客戶端擁有不同網(wǎng)絡(luò)結(jié)構(gòu)：先把本地模型做成圖，然后將 GNN 作用于圖之上。聯(lián)邦聚合對(duì)象是 GNN 權(quán)重和梯度，常用于 centralized FedGNN。

3.2 FedGNN

3.2.1 問(wèn)題定義

3.2.2 FedGNN 原理與架構(gòu)

如上圖，F(xiàn)edGNN [7] 由一個(gè)中心服務(wù)器和大量客戶端組成?？蛻舳嘶谄溆脩艚换ノ锲放c鄰居客戶端在本地維護(hù)了一個(gè)子圖?？蛻舳嘶诒镜刈訄D學(xué)習(xí) user/item embedding，以及 GNN 模型，然后將梯度上傳給中心服務(wù)器。中心服務(wù)器用來(lái)協(xié)調(diào)客戶端，具體是在訓(xùn)練過(guò)程中聚合從多個(gè)客戶端收集的梯度（基于 FedAvg 算法），并將聚合后的梯度回傳給客戶端。如下我們將依次介紹一些技術(shù)細(xì)節(jié)。



FedGNN 的完整算法流程見(jiàn)下述 Algorithm1，其中有兩個(gè)隱私保護(hù)模塊：其一是隱私保護(hù)模型更新（Algorithm1 的 9-11 行），用來(lái)保護(hù)梯度信息；其二是隱私保護(hù) user-item 圖擴(kuò)充模塊（Algorithm1 中第 15 行），用來(lái)對(duì) user 和 item 的高階交互進(jìn)行建模。

3.2.3 隱私保護(hù)模型更新

embedding 梯度和模型梯度（GNN+rating predictor）直接傳輸會(huì)泄露隱私，因此需要對(duì)此進(jìn)行安全防護(hù)。因?yàn)槊總€(gè)客戶端維護(hù)了全量 item 的 embedding 表，通過(guò)同態(tài)加密保護(hù)梯度就不太現(xiàn)實(shí)（大量的存儲(chǔ)和通信開(kāi)銷），文獻(xiàn) [7] 提出兩個(gè)機(jī)制來(lái)保護(hù)模型更新過(guò)程中的隱私保護(hù)。

1）偽交互物品采樣 隨機(jī)采樣 M 個(gè)用戶并未交互過(guò)的物品，根據(jù)交互物品 embedding 梯度分布隨機(jī)生成偽交互物品 embedding 梯度。于是第 i 個(gè)用戶的模型和 embedding 梯度修改為

2）采用 LDP（本地差分隱私）護(hù)本地梯度 首先通過(guò)梯度的無(wú)窮范數(shù)和閾值?δ對(duì)梯度進(jìn)行截?cái)啵缓蠡?LDP 思想采用 0 均值拉普拉斯噪聲對(duì)前述梯度進(jìn)行擾動(dòng)，從而實(shí)現(xiàn)對(duì)用戶隱私的保護(hù)。相應(yīng)的公式表達(dá)為：

gi=clip(g_i_,δ)+Laplace(0,λ)。受保護(hù)的梯度再上傳到中心服務(wù)器進(jìn)行聚合。

3.2.4 隱私保護(hù)圖擴(kuò)充

客戶端本地 user-item 圖以隱私保護(hù)方式找到鄰居客戶端，以達(dá)到對(duì)本地圖自身的擴(kuò)充。在中心化存儲(chǔ)的 GNN 場(chǎng)景中，user 與 item 的高階交互可通過(guò)全局 user-item 圖方便獲取。但非中心化場(chǎng)景中，在遵守隱私保護(hù)的前提下要想求得 user-item 高階交互不是易事。文章提出通過(guò)尋找客戶端的匿名鄰居以提升 user 和 item 的表征學(xué)習(xí)，同時(shí)用戶隱私不泄露，詳細(xì)過(guò)程如下：



首先，中心服務(wù)器生成公鑰并分發(fā)給各客戶端?？蛻舳耸盏焦€后，利用同態(tài)加密技術(shù)對(duì)交互物品 ID 進(jìn)行加密處理。前述加密 ID 和用戶 embedding 被上傳至第三方服務(wù)器（不需要可信），通過(guò) PSI 技術(shù)找到有相同交互物品的用戶，然后為每個(gè)用戶提供匿名鄰居 embedding。最后，我們把用戶的鄰居用戶節(jié)點(diǎn)連接起來(lái)，這樣就以隱私保護(hù)的方式添加了 user-item 的高階交互信息，豐富了客戶端的本地 user-item 子圖。

3.3 VFGNN

3.3.1 數(shù)據(jù)假設(shè)

訓(xùn)練一個(gè)好的 GNN 模型通常需要豐富的節(jié)點(diǎn)特征和完整的連接信息。但是節(jié)點(diǎn)特征和連接信息通常由多個(gè)數(shù)據(jù)方擁有，也就是所謂的數(shù)據(jù)孤島問(wèn)題。下圖我們給出圖數(shù)據(jù)縱向劃分的例子 [8]，其中三方各自擁有節(jié)點(diǎn)不同的特征，各方擁有不同類型的邊。

3.3.2 算法架構(gòu)及流程

安全性假設(shè)：數(shù)據(jù)擁有方 A,B,C 和服務(wù)器 S 都是半誠(chéng)實(shí)的，并且假定服務(wù)器 S 和任一數(shù)據(jù)擁有方不會(huì)合謀。這個(gè)安全假設(shè)符合大多數(shù)已有工作，并且和現(xiàn)實(shí)場(chǎng)景比較契合。



上圖即為 VFGNN 的架構(gòu)圖，它的計(jì)算分為兩大部分：

?隱私數(shù)據(jù)相關(guān)計(jì)算：一般在數(shù)據(jù)擁有方本地進(jìn)行。在 GNN 場(chǎng)景中，隱私數(shù)據(jù)有：節(jié)點(diǎn)特征、label、邊信息。

?非隱私數(shù)據(jù)相關(guān)計(jì)算：一般將計(jì)算權(quán)委托給半誠(chéng)實(shí) server，主要是出于計(jì)算效率的考慮。

考慮到數(shù)據(jù)隱私性的問(wèn)題，上述計(jì)算圖分為如下三個(gè)計(jì)算子圖，且各自承擔(dān)的工作如下：

?CG1：隱私特征和邊相關(guān)計(jì)算。先利用節(jié)點(diǎn)隱私特征生成 initial node embedding，這個(gè)過(guò)程是多方協(xié)同工作的。接著通過(guò)采樣找到節(jié)點(diǎn)的多跳鄰居，再應(yīng)用聚合函數(shù)生成 local node embedding。

?CG2：非隱私數(shù)據(jù)相關(guān)計(jì)算。出于效率考慮，作者把非隱私數(shù)據(jù)相關(guān)計(jì)算委托給半誠(chéng)實(shí)服務(wù)器。此服務(wù)器把從各方收集的 local node embedding 通過(guò)不同的 COMBINE 策略處理生成 global node embedding。接著可以進(jìn)行若干明文類的操作，比如 max-pooling、activation（這些計(jì)算在密文狀態(tài)下不友好）。進(jìn)行一系列明文處理后，我們得到最后一個(gè)隱層輸出_ZL_?，然后把它發(fā)送給擁有 label 的數(shù)據(jù)方計(jì)算預(yù)測(cè)值。

?CG3：隱私標(biāo)簽相關(guān)計(jì)算。以節(jié)點(diǎn)分類任務(wù)為例 ，當(dāng)收到_ZL_?后可以快速計(jì)算出預(yù)測(cè)值，具體通過(guò) softmax 函數(shù)進(jìn)行處理。

3.3.3 重要組件

Generating Initial Node Embedding



如果各方獨(dú)立生成 initial node embedding（上圖 a），則遵循如下計(jì)算公式：



如果各方協(xié)同生成 initial node emb，則可按上圖 b 中應(yīng)用 MPC 技術(shù)進(jìn)行處理。 Generating Local Node Embedding 基于前述生成的 initial node embedding，及節(jié)點(diǎn)的多跳鄰居節(jié)點(diǎn)，應(yīng)用聚合函數(shù)可以生成 local node embedding。鄰居節(jié)點(diǎn)的聚合操作必須在本地進(jìn)行而不需要多方協(xié)同，目的是保護(hù)隱私的邊信息。一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)聚合操作和常規(guī) GNN 一樣，以 GraphSAGE 為例節(jié)點(diǎn)的聚合操作是通過(guò)采樣和聚合特征形成了 local node embedding，具體公式如下：



GraphSAGE 中，常用的聚合函數(shù)有：Mean、LSTM、Pooling。接著數(shù)據(jù)擁有方把 local node embedding 發(fā)送給半誠(chéng)實(shí)服務(wù)器，以進(jìn)行 COMBINE 操作及后續(xù)的非隱私數(shù)據(jù)計(jì)算邏輯。 Generating Global Node Embedding 對(duì)各方傳來(lái)的 local node embedding 執(zhí)行 combine 操作可以生成 global node embedding。combine 策略一般是可訓(xùn)練且高表達(dá)容量，文章給出了三種策略：

1）Concat



2）Mean



3）Regression

3.3.4 隱私保護(hù) DP

如果在前向過(guò)程中把 local node embedding 直接傳給半誠(chéng)實(shí)服務(wù)器，或在反向傳播過(guò)程中直接傳遞梯度信息很可能造成信息泄露。本文提出了兩種基于 DP 的方法用來(lái)保護(hù)信息發(fā)布過(guò)程，算法流程如下：

3.3.5 VFGNN 前向算法

以 GraphSAGE 處理節(jié)點(diǎn)分類任務(wù)為例，VFGNN 算法的前向過(guò)程描述如下：

3.4 其他算法及項(xiàng)目

最近四年出現(xiàn)的聯(lián)邦 GNN 算法 [9]：



開(kāi)源項(xiàng)目有：FedGraphNN [10]。

審核編輯：劉清