本文種展示的特征傳播是一種用于處理圖機器學習應用程序中缺失的特征的有效且可擴展的方法。它很簡單，但效果出奇地好。

圖神經(jīng)網(wǎng)絡 (GNN) 模型通常假設每個節(jié)點都有一個完整的特征向量。以一個 2 層 GCN 模型 [1] 為例，它具有以下形式：

Z = A σ(AXW?) W?

該模型的兩個輸入是編碼圖結構(歸一化的)鄰接矩陣 A 和作為行的節(jié)點特征的特征矩陣 X，輸出為節(jié)點嵌入 Z。GCN 的每一層執(zhí)行節(jié)點特征變換(參數(shù)化可學習矩陣 W? 和 W?)，然后將轉換后的特征向量傳播到相鄰節(jié)點。這里面一個重要的概念是：GCN 假設 X 中的所有條目都被觀察到。

但是在現(xiàn)實世界的場景中，經(jīng)常會看到一些節(jié)點特征可能會缺失。例如，年齡、性別等人口統(tǒng)計信息可能僅對一小部分社交網(wǎng)絡用戶可用，而內(nèi)容特征通常僅對最活躍的用戶呈現(xiàn)。例如在推薦系統(tǒng)中并非所有產(chǎn)品都有與之相關的完整描述，這使得情況變得更加嚴重，隨著人們對數(shù)字隱私的認識不斷提高，越來越多的數(shù)據(jù)只有在用戶明確同意的情況下才能獲得。

根據(jù)上面的描述，特征矩陣都有缺失值的，大多數(shù)現(xiàn)有的 GNN 模型都不能直接應用。最近的幾項工作派生了能夠處理缺失特征的 GNN 模型(例如 [2-3])，但是這些模型在缺失特征率很高(>90%)的情況下受到影響，并且不能擴展到具有超過幾百萬條邊的圖.

在 Maria Gorinova、Ben Chamberlain (Twitter)、Henry Kenlay 和 Xiaowen Dong (Oxford) 合著的一篇新論文 [4] 中，提出了特征傳播 (FP) [4] 作為一種簡單但高效且令人驚訝的有效解決方案。 簡而言之，F(xiàn)P 通過在圖上傳播已知特征來重構缺失的特征。 然后可以將重建的特征輸入任何 GNN 以解決下游任務，例如節(jié)點分類或鏈接預測。

特征傳播框架。 輸入是缺少節(jié)點特征的圖(左)。 在初始步驟中，特征傳播通過迭代地擴散圖中的已知特征來重構缺失的特征(中)。 隨后，圖和重建的節(jié)點特征被輸入到下游 GNN 模型中，然后產(chǎn)生預測(右)。

傳播步驟非常簡單：首先，未知特征用任意值初始化[5]。 通過應用(歸一化的)鄰接矩陣來傳播特征，然后將已知特征重置為其真實值。 我們重復這兩個操作，直到特征向量收斂[6]。

特征傳播是一種簡單且令人驚訝的強大方法，用于在缺少特征的圖上進行學習。 特征的每個坐標都被單獨處理(x 表示 X 的一列)。

FP 可以從數(shù)據(jù)同質性(“平滑性”)的假設中推導出來，即鄰居往往具有相似的特征向量。 同質性的水平可以使用Dirichlet energy來量化，這是一種測量節(jié)點特征與其鄰居平均值之間的平方差的二次形式。 Dirichlet energy[7] 的梯度流是圖熱擴散方程，以已知特征作為邊界條件。 FP 是使用具有單位步長的顯式前向 Euler 方案作為該擴散方程的離散化獲得的 [8]。

動畫展示了隨著特征傳播的更多迭代應用而標量節(jié)點特征的演變示例。 未知特征被初始化為零，但很快收斂到使給定圖上的Dirichlet energy最小化的值。

特征傳播與標簽傳播(LP)[9]相似。 關鍵區(qū)別在于 LP 是一種與特征無關的方法，它通過在圖中傳播已知標簽來直接預測每個節(jié)點的類，而FP 用于首先重建缺失的節(jié)點特征，然后將其饋送到下游 GNN。 這使得 FP 能夠利用觀察到的特征，并在所有基準測試中都優(yōu)于 LP。 在實踐中經(jīng)常發(fā)生帶標簽的節(jié)點集和具有特征的節(jié)點集不一定完全重疊，因此這兩種方法并不總是可以直接比較。

論文中使用七個標準節(jié)點分類基準對 FP 進行了廣泛的實驗驗證，其中隨機刪除了可變部分的節(jié)點特征(獨立于每個通道)。 FP 后跟一個 2 層 GCN 在重建特征上的表現(xiàn)明顯優(yōu)于簡單的基線以及最新的最先進的方法 [2-3]。

FP 在特征缺失率高 (>90%) 的情況下尤為突出，而所有其他方法往往會受到影響。 例如，即使丟失了 99% 的特征，與所有特征都存在的相同模型相比，F(xiàn)P 平均僅損失約 4% 的相對準確度。

Cora 數(shù)據(jù)集上不同特征缺失率的節(jié)點分類準確度(從 0% 是大多數(shù) GNN 的標準狀態(tài)到 99% 的極端情況)。

FP 的另一個關鍵特點是它的可擴展性： 其他方法無法擴展到具有幾百萬條邊的圖之外，但 FP 可以擴展到十億條邊的圖。 作者用了不到一小時的時間在內(nèi)部 Twitter 圖表上運行它，使用單臺機器大約有 10 億個節(jié)點和 100 億條邊。

FP+GCN 和最新最先進的方法 GCNMF 和 PaGNN [2-3] 的運行時間(以秒為單位)。 FP+GCN 比其他兩種方法快 3 倍。 GCNMF 在 OGBN-Arxiv 上出現(xiàn)內(nèi)存不足 (OOM)，而 GCNMF 和 PaGNN 在 OGBN-Products(約 123M 邊)上出現(xiàn) OOM，其中 FP 的重建部分(無需訓練下游模型)僅需約 10 秒。

FP 的當前限制之一是它在heterophilic graphs上效果不佳，即鄰居具有不同特征的圖。 這并不奇怪，因為 FP 源自同質假設(通過擴散方程最小化 Dirichlet energy)。 FP 假設不同的特征通道是不相關的，這在現(xiàn)實生活中很少見。 但是可以通過替代更復雜的擴散機制，同時滿足這兩個限制。

當 99% 的特征缺失時，具有各種同質性水平的合成圖上的節(jié)點分類準確度(0 是極度異質性，1 是極度同質性)。 雖然在高度同質性設置中 FP 的表現(xiàn)幾乎與具有完整特征的情況一樣好，但在低同質性設置中，兩者之間的差距很大，并且 FP 的性能惡化到一個簡單的基線，其中缺失的特征被替換為 零。

盡管在實際應用中無處不在，但在缺少節(jié)點特征的圖上學習是一個幾乎未被探索的研究領域。 特征傳播模型是提高在缺少節(jié)點特征的圖上學習能力的重要一步，它還提出了關于在這種情況下學習的理論能力的深刻問題。 FP 的簡單性和可擴展性，以及與更復雜的方法相比的驚人的好結果，即使在極端缺失的特征狀態(tài)下，也使其成為大規(guī)模工業(yè)應用的良好候選者。