聯邦學習和 GNN 都是當前 AI 領域的研究熱點。聯邦學習的多個參與方可以在不泄露原始數據的情況下，安全合規地聯合訓練業務模型，目前已在諸多領域取得了較好的結果。GNN 在應對非歐數據結構時通常有較好的表現，因為它不僅考慮節點本身的特征還考慮節點之間的鏈接關系及強度，在諸如：異常個體識別、鏈接預測、分子性質預測、地理拓撲圖預測交通擁堵等領域均有不俗表現。

那么 GNN 與聯邦學習的強強組合又會擦出怎樣的火花？ 通常一個好的 GNN 算法需要豐富的節點特征與完整的連接信息，但現實場景中數據孤島問題比較突出，單個數據擁有方往往只有有限的數據、特征、邊信息，但我們借助聯邦學習技術就可以充分利用各方數據安全合規地訓練有強勁表現的 GNN 模型。

一、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 均值拉普拉斯噪聲對前述梯度進行擾動，從而實現對用戶隱私的保護。相應的公式表達為：

gi=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]。

審核編輯：劉清