論文：https://arxiv.org/pdf/2101.08543.pdf

代碼：https：//github.com/nd7141/bgnn

無論是分子設(shè)計(jì)、計(jì)算機(jī)視覺，還是組合優(yōu)化和推薦系統(tǒng)等，圖神經(jīng)網(wǎng)絡(luò)( GNNs，Graph Neural Networks )都在學(xué)習(xí)圖結(jié)構(gòu)化數(shù)據(jù)方面取得了巨大的成功。

這種成功的主要驅(qū)動(dòng)力之一在于 GNN 能夠有效地將原始輸入數(shù)據(jù)編碼成表達(dá)性表示，以便在新的數(shù)據(jù)集和任務(wù)上實(shí)現(xiàn)高質(zhì)量的結(jié)果。

近期，關(guān)于 GNN 的研究主要集中在具有稀疏數(shù)據(jù)的 GNNs 上。這些數(shù)據(jù)代表同構(gòu)節(jié)點(diǎn)嵌入（例如，獨(dú)熱編碼圖統(tǒng)計(jì)）或詞袋表示（bag-of-words representations）。然而，圖（graph）中的表數(shù)據(jù)（Tabular Data）節(jié)點(diǎn)之間，包含有詳細(xì)的信息和大量的語義表示。

以社交網(wǎng)絡(luò)為例，每個(gè)人都有社會(huì)人口統(tǒng)計(jì)學(xué)特征（如年齡、性別和畢業(yè)日期等）。顯然，這些特征在數(shù)據(jù)類型、規(guī)模和缺失值上存在很大差異。對(duì)于帶有表格數(shù)據(jù)的圖，GNNs 仍未邁出進(jìn)一步探索的腳步。另一方面，梯度提升決策樹（GBDT, Gradient Boosted Decision Trees）在具有此類異構(gòu)數(shù)據(jù)的應(yīng)用程序中占據(jù)著主導(dǎo)地位。

而在 ICLR 2021 文章?Boost Then Convolve: Gradient Boosting Meets Graph Neural Networks?中，作者 Sergei Ivanov 、 Liudmila Prokhorenkova 提出了一種新穎的架構(gòu)，可以聯(lián)合訓(xùn)練 GBDT 和 GNN 以獲得兩者的優(yōu)點(diǎn)：GBDT 模型處理異構(gòu)特征，而 GNN 負(fù)責(zé)圖結(jié)構(gòu)。

各自長(zhǎng)短

首先，簡(jiǎn)單介紹下 GBDTs 在表格數(shù)據(jù)上為何會(huì)如此成功。這主要得益于其以下特性：

（1）它可以有效地學(xué)習(xí)在表格數(shù)據(jù)中常見的具有類超平面邊界的決策空間；

（2）它非常適合處理高基數(shù)的變量以及值缺失且比例不同的特征;

??(3）通過事后分析階段為決策樹或集成提供定性解釋；

（4）在實(shí)際應(yīng)用中，即便是在處理大量數(shù)據(jù)時(shí)也會(huì)快速收斂。

相比之下，GNNs 的關(guān)鍵特征則為，同時(shí)考慮節(jié)點(diǎn)的鄰域信息和節(jié)點(diǎn)特征來進(jìn)行預(yù)測(cè)，這區(qū)別于 GBDTs 需要額外的預(yù)處理分析來為算法提供圖摘要（graph summary）。

而且理論上已經(jīng)證明，消息傳遞 GNNs 可以在圖靈機(jī)可計(jì)算的圖輸入上計(jì)算任何函數(shù)，即，GNNs 是已知的唯一在圖上具有通用性的學(xué)習(xí)體系結(jié)構(gòu)。

除此之外，與基于樹的方法相比，基于梯度的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)具有更大的優(yōu)勢(shì)：

（1）強(qiáng)加于 GNNs 的關(guān)系歸納偏置（relational inductive bias）減少了對(duì)捕獲網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的特性進(jìn)行手動(dòng)工程的需要。

（2）訓(xùn)練神經(jīng)網(wǎng)絡(luò)的端到端性質(zhì)允許在依賴于應(yīng)用程序的解決方案中將 GNNs 進(jìn)行多分段或多組件集成。

（3）圖網(wǎng)絡(luò)的預(yù)訓(xùn)練表示豐富了許多重要任務(wù)的遷移學(xué)習(xí)，如無監(jiān)督領(lǐng)域適應(yīng)（UDA, unsupervised domain adaptation）、自監(jiān)督學(xué)習(xí)（self-supervised learning）和主動(dòng)學(xué)習(xí)機(jī)制（active learning）。

圖神經(jīng)網(wǎng)絡(luò)已在各種圖表示學(xué)習(xí)任務(wù)中取得了成功。面對(duì)異構(gòu)表格數(shù)據(jù)時(shí)，GBDTs 通常優(yōu)于其他機(jī)器學(xué)習(xí)方法。但是，對(duì)于具有表格節(jié)點(diǎn)特征的圖，究竟該選擇哪種方法？先前的 GNNs 模型主要集中在具有同構(gòu)稀疏特征的網(wǎng)絡(luò)上，而在異構(gòu)環(huán)境中則表現(xiàn)次優(yōu)。

毫無疑問，GBDTs 和 GNNs 方法都在各自的領(lǐng)域有著核心的競(jìng)爭(zhēng)力。

因此，論文作者們不禁猜想：是否能充分使用這兩者間的潛力？

之前曾出現(xiàn)嘗試結(jié)合梯度增強(qiáng)和神經(jīng)網(wǎng)絡(luò)的方法，但鑒于計(jì)算成本高，沒有將圖結(jié)構(gòu)數(shù)據(jù)考慮在內(nèi)，以及缺乏 GNNs 體系架構(gòu)中強(qiáng)加的關(guān)系歸納偏置等多方面因素，并未取得預(yù)期效果。而據(jù)了解，本文所介紹的任務(wù)，是首次系統(tǒng)地使用 GBDTs 模型進(jìn)行圖結(jié)構(gòu)數(shù)據(jù)探索的工作。

如何結(jié)合雙方優(yōu)勢(shì)？

在這項(xiàng)工作中，研究團(tuán)隊(duì)提出了一種新穎的體系結(jié)構(gòu) BGNN（Boost-GNN）—— 將 GBDTs 對(duì)表格節(jié)點(diǎn)特征的學(xué)習(xí)與 GNNs 相結(jié)合，聯(lián)合訓(xùn)練 GBDTs 和 GNNs 以有效獲得兩者的最佳效果，即 GBDTs 模型處理異構(gòu)特征，而 GNNs 用于解釋圖結(jié)構(gòu)，兩者結(jié)合以優(yōu)化預(yù)測(cè)結(jié)果。

這使得研究團(tuán)隊(duì)提出的模型受益于端到端優(yōu)化，允許新的樹適應(yīng) GNNs 的梯度更新。通過與前沿的 GBDTs 和 GNNs 模型進(jìn)行廣泛的實(shí)驗(yàn)比較，團(tuán)隊(duì)充分證實(shí)了具有表格特征的各種圖的性能均得到了顯著提高。

具體而言，設(shè)置 G=(V, E) 為具有特征和目標(biāo)標(biāo)簽的節(jié)點(diǎn)的圖。在節(jié)點(diǎn)預(yù)測(cè)任務(wù) (分類或回歸) 中，可以借助已知的目標(biāo)標(biāo)簽預(yù)測(cè)未知。???????????????????????????????在整個(gè)文本中，用小寫變量??（??）或??表示單個(gè)節(jié)點(diǎn)的特征，而??則為所有特征的矩陣表示。單個(gè)目標(biāo)標(biāo)簽用??表示，而??和??分別代表所有的和僅為訓(xùn)練標(biāo)簽的向量。

圖神經(jīng)網(wǎng)絡(luò) (GNNs) 利用網(wǎng)絡(luò)的連通性和節(jié)點(diǎn)特征來學(xué)習(xí)所有節(jié)點(diǎn)??的潛在表示。很多流行的 GNNs 都采用鄰域聚合方法，也稱為消息傳遞機(jī)制，通過應(yīng)用其鄰居表示的非線性聚合函數(shù)以更新節(jié)點(diǎn)??的表示。類似于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)，GNNs 由多層組成，每個(gè)層代表一個(gè)非線性消息傳遞函數(shù)：

??

其中，??表示第??層上節(jié)點(diǎn)??的表示，??和??是聚合來自節(jié)點(diǎn)本地鄰域表示的函數(shù)。通過最小化經(jīng)驗(yàn)損失函數(shù)，采用梯度下降法來優(yōu)化 GNN 模型的參數(shù)。

而梯度提升決策樹 (GBDTs) 則是一種迭代的決策樹算法，由多棵決策樹組成，所有樹的結(jié)論累加起來作為最終答案。此算法是在非圖形表格數(shù)據(jù)上定義的廣泛應(yīng)用的算法，尤其適用于包含異構(gòu)特性和噪聲數(shù)據(jù)的任務(wù)。

梯度提升的核心思想是通過迭代添加弱模型 (往往選擇決策樹) 來構(gòu)建強(qiáng)模型。形式上，在梯度提升算法的每次迭代??中，模型 f (x) 都以累加的方式進(jìn)行更新：

?ε（）?

其中，??是前一次迭代中構(gòu)建的模型，??是從某些函數(shù)族中選擇的弱學(xué)習(xí)者，?ε?表示的是學(xué)習(xí)率。選擇??來近似損失函數(shù) L w.r.t 的負(fù)梯度。

弱學(xué)習(xí)者的集合通常由淺層的決策樹構(gòu)成。決策樹是通過將特征空間遞歸劃分成稱為葉子的不相交區(qū)域來建立的。

當(dāng) GBDT 遇到 GNN

梯度提升方法在表格數(shù)據(jù)學(xué)習(xí)中效果顯著；然而，將 GBDT 應(yīng)用于圖結(jié)構(gòu)數(shù)據(jù)存在以下挑戰(zhàn):

（1）如何將節(jié)點(diǎn)特征之外的關(guān)系信號(hào)傳播到本來固有的表格模型；（2）如何以端到端的方式將其與 GNNs 一起訓(xùn)練。

的確，GBDT 和 GNNs 的優(yōu)化遵循著不同的方法：GNNs 的參數(shù)主要通過梯度下降進(jìn)行優(yōu)化，而 GBDT 是迭代構(gòu)造的。

此時(shí)，應(yīng)該采用什么解決方案？

一種簡(jiǎn)單的方法是僅在節(jié)點(diǎn)特征上訓(xùn)練 GBDT 模型，然后將獲得的 GBDT 預(yù)測(cè)結(jié)果與原始輸入一起作為 GNNs 的新節(jié)點(diǎn)特征。在這種情況下，將通過圖神經(jīng)網(wǎng)絡(luò)進(jìn)一步完善 GBDT 對(duì)圖不敏感的預(yù)測(cè)問題。作者將這種方法稱之為 Res-GNN，顯然，此方法已經(jīng)可以提高 GNNs 在某些任務(wù)上的性能。但是，在這種情況下，GBDT 模型完全忽略了圖結(jié)構(gòu)，可能會(huì)遺漏圖的描述性特征，導(dǎo)致為 GNNs 提供的輸入數(shù)據(jù)在準(zhǔn)確性上存在偏差。

圖 1

相反地，研究團(tuán)隊(duì)建議對(duì) GBDT 和 GNNs 進(jìn)行端到端的訓(xùn)練，簡(jiǎn)稱為 BGNN。與先前類似的是，首先應(yīng)用 GBDT，然后采用 GNNs。但考慮到最終預(yù)測(cè)的質(zhì)量，團(tuán)隊(duì)成員對(duì)兩者進(jìn)行了優(yōu)化。BGNN 的訓(xùn)練如圖 1 所示。因?yàn)榻⒑玫臎Q策樹結(jié)構(gòu)離散而無法進(jìn)行適當(dāng)調(diào)整，因此團(tuán)隊(duì)成員通過添加新的樹來迭代更新 GBDT 模型，使其近似于 GNNs 的損失函數(shù)。

算法 1

在算法 1 中，團(tuán)隊(duì)展示了結(jié)合 GBDT 和 GNNs 的 BGNN 模型的訓(xùn)練，以解決任何節(jié)點(diǎn)級(jí)預(yù)測(cè)問題，如半監(jiān)督節(jié)點(diǎn)回歸或分類。在首次迭代中，研究團(tuán)隊(duì)通過最小化在訓(xùn)練節(jié)點(diǎn)上的平均損失函數(shù)?（（），）?，來建立帶有 k 棵決策樹的 GBDT 模型。借助所有預(yù)測(cè)?（）?，將節(jié)點(diǎn)特征更新為??，然后傳遞給 GNNs。

整體來看，BGNN 模型的主體架構(gòu)只由兩個(gè)連續(xù)的塊 (GBDT 和 GNNs) 組成，并且執(zhí)行的是端到端的訓(xùn)練，因此可以從兩個(gè)角度來闡述兩者間的關(guān)系：GBDT 是 GNNs 的嵌入層，或者 GNNs 是 GBDT 的參數(shù)損失函數(shù)。

更具體地，在第一種情況下，GBDT 將原始輸入特征??轉(zhuǎn)換為新的節(jié)點(diǎn)特征??，然后將其傳遞給 GNNs。而第二種情況下，可以將 BGNN 視為標(biāo)準(zhǔn)的梯度提升訓(xùn)練，其中 GNNs 則充當(dāng)依賴于圖拓?fù)涞膹?fù)雜損失函數(shù)。

實(shí)驗(yàn)及結(jié)果分析

團(tuán)隊(duì)成員對(duì) BGNN 和 Res-GNN 進(jìn)行了比較評(píng)估，對(duì)比了各種強(qiáng)基線和先前關(guān)于異構(gòu)節(jié)點(diǎn)預(yù)測(cè)問題的方法，從而在所有方面均實(shí)現(xiàn)了顯著的性能提升。為了確保實(shí)驗(yàn)的公平性，在訓(xùn)練每個(gè)模型時(shí)，保證驗(yàn)證集上的超參達(dá)到收斂狀態(tài)，并根據(jù)三次超參設(shè)置的運(yùn)行結(jié)果，取均值。在這部分中，主要概述了三方面的內(nèi)容：實(shí)驗(yàn)設(shè)置，異構(gòu)節(jié)點(diǎn)回歸問題的結(jié)果以及提取的特征表示。

表 1

針對(duì)于異構(gòu)節(jié)點(diǎn)的回歸問題，研究團(tuán)隊(duì)使用了五個(gè)具有不同屬性的真實(shí)世界的節(jié)點(diǎn)回歸數(shù)據(jù)集，具體統(tǒng)計(jì)情況如表 1 所示。其中，四個(gè)數(shù)據(jù)集（House、County、VK、Avazu）是異構(gòu)的，也就是說輸入要素之間彼此獨(dú)立，很可能具有不同的類型、規(guī)模和含義。而剩下的 Wiki 數(shù)據(jù)集是同構(gòu)數(shù)據(jù)集，節(jié)點(diǎn)之間是相互依存的，并且對(duì)應(yīng)于維基百科的詞袋表示。

表 2

表 2 則給出了各模型間對(duì)節(jié)點(diǎn)回歸的比較評(píng)估結(jié)果。從表中的報(bào)告數(shù)據(jù)可以明確的得出，團(tuán)隊(duì)提出的 BGNN 模型相比于基線有了顯著的提升。特別是，在異構(gòu)的情況下，BGNN 分別使 House、County、VK、Avazu 數(shù)據(jù)集的錯(cuò)誤率減少了 8%、14%、4% 和 4%。使用預(yù)訓(xùn)練的 CatBoost 模型作為 GNNs 輸入的 Res-GNN 模型也降低了均方根誤差值（RMSE, Root Mean Squared Error），但不如端到端模型 BGNN 降低得多。在同構(gòu)數(shù)據(jù)集 Wiki 中，相比于 CatBoost 模型以及隨后的 Res-GNN 和 BGNN 模型，GNN 模型的表現(xiàn)更好一些。

直觀地說，在特征同構(gòu)的情況下，神經(jīng)網(wǎng)絡(luò)方法就足以獲得最佳結(jié)果。這也潛在表明，BGNN 可以獲得更好的定性結(jié)果，其端到端的訓(xùn)練方式在表格數(shù)據(jù)圖的節(jié)點(diǎn)預(yù)測(cè)任務(wù)中占據(jù)明顯的優(yōu)勢(shì)。除此之外，端到端的組合方法 FCNN-GNN 比單純使用 GNNs 所獲得的性能更好。但是，與融合 GBDT 優(yōu)勢(shì)的 BGNN 模型相比，其改進(jìn)幅度仍然偏小。

需要注意的是，CatBoost、LightGBM 和 FCNN 可以單獨(dú)發(fā)揮作用，但它們的性能在所有數(shù)據(jù)集上的顯示并不穩(wěn)定。總體而言，這些對(duì)照實(shí)驗(yàn)有力的證明了 BGNN 模型相對(duì)于其他強(qiáng)模型的優(yōu)越性。

對(duì)于節(jié)點(diǎn)分類而言，研究團(tuán)隊(duì)使用了五個(gè)具有不同屬性的數(shù)據(jù)集。由于缺乏具有異構(gòu)節(jié)點(diǎn)特征的公開數(shù)據(jù)集，團(tuán)隊(duì)通過將目標(biāo)標(biāo)簽轉(zhuǎn)換為若干離散類，采用回歸任務(wù)中的數(shù)據(jù)集 House 類和 VK 類。另外，還引入了兩個(gè)來自異構(gòu)信息網(wǎng)絡(luò)（HIN, Heterogeneous Information Networks）的稀疏節(jié)點(diǎn)分類數(shù)據(jù)集 SLAP 和 DBLP，其中節(jié)點(diǎn)包含有幾種不同的類型。為了完整起見，在實(shí)驗(yàn)過程中，團(tuán)隊(duì)還加入了一個(gè)同構(gòu)數(shù)據(jù)集 OGB-ArXiv。

團(tuán)隊(duì)成員留意到，該數(shù)據(jù)集中的節(jié)點(diǎn)特征對(duì)應(yīng)于 128 維的特征向量，該向量是通過平均標(biāo)題和摘要中的詞嵌入得到的。由此可見，該數(shù)據(jù)集的特征并非異構(gòu)，因此推斷，與神經(jīng)網(wǎng)絡(luò)方法相比，GBDT 并不會(huì)很高。

表 3

從表 3 中可以看出，BGNN 方法在具有表格特征的數(shù)據(jù)集（House 類和 VK 類）上的結(jié)果存在顯著優(yōu)勢(shì)。例如，對(duì)于 VK 類數(shù)據(jù)集，BGNN 在精確度上實(shí)現(xiàn)了 18% 以上的增加量。這表明，GBDT 和 GNNs 的聯(lián)合學(xué)習(xí)表示形式在具有異構(gòu)特征數(shù)據(jù)的節(jié)點(diǎn)分類設(shè)置時(shí)同樣有用。

其他的兩個(gè)數(shù)據(jù)集 Slap 和 DBLP 具有稀疏的詞袋特征，這對(duì) GNNs 模型來說是個(gè)十足的挑戰(zhàn)。在這兩個(gè)數(shù)據(jù)集中，GBDT 作為最強(qiáng)的基線。而且，由于 FCNN 優(yōu)于 GNN，團(tuán)隊(duì)初步猜測(cè)，圖結(jié)構(gòu)可能無濟(jì)于事，也就是說在最終呈現(xiàn)的實(shí)驗(yàn)結(jié)果中，BGNN 不應(yīng)該優(yōu)于 GBDT。

當(dāng)然，事實(shí)確實(shí)如此：BGNN 的最終精確度略低于 GBDT。

在同構(gòu)數(shù)據(jù)集 OGB-ArXiv 中，FCNN-GNN 和 GNN 模型性能最高，其次是 Res-GNN 和 BGNN 模型。簡(jiǎn)而言之，GBDT 無法對(duì)同構(gòu)輸入特征進(jìn)行良好的預(yù)測(cè)，因此降低了 GNN 的判別能力。在數(shù)據(jù)集具有稀疏性和同構(gòu)特征的兩種情況下，均表明 BGNN 的性能與 GNN 相當(dāng)或更高。但是，由于數(shù)據(jù)中缺乏異構(gòu)結(jié)構(gòu)可能使得 GBDT 和 GNNs 的聯(lián)合訓(xùn)練存在冗余現(xiàn)象。

考慮到 BGNN 模型在各種數(shù)據(jù)集上的性能明顯優(yōu)于強(qiáng)基線，因此團(tuán)隊(duì)又做了補(bǔ)充實(shí)驗(yàn)，測(cè)試了使用不同 GNNs 模型時(shí)對(duì)改進(jìn)的影響。為了解開疑惑，團(tuán)隊(duì)比較了四種 GNNs 模型，分別是 GAT、GCN、AGNN 和 APPNP 模型。做法是先將這些模型分別替換為 Res-GNN 和 BGNN 模型，然后測(cè)量相對(duì)于原始 GNNs 性能的變化情況。實(shí)驗(yàn)結(jié)果如圖 2 所示，其縱坐標(biāo)表示每種 GNN 模型架構(gòu)的 Rse-GNN 和 BGNN 之間的 RMSE 差距。通過實(shí)驗(yàn)結(jié)果，證明了所有經(jīng)過測(cè)試的 GNNs 架構(gòu)都能從本文團(tuán)隊(duì)所出的方法中受益匪淺。以 House 數(shù)據(jù)集為例，對(duì)于 GAT、GCN、AGNN 和 APPNP 四個(gè)模型，均方差分別減少了 9%、18%、19% 和 17%。

此外，還可以清晰的看到，BGNN 的端到端訓(xùn)練（紅色方格）比 Res-GNN 模型中 CatBoost 和 GNN 的簡(jiǎn)單組合（黃色斜紋）帶來的改進(jìn)更大。這再次有力的證實(shí)了團(tuán)隊(duì)所提出方法的有效性。

先前的實(shí)驗(yàn)在模型性能方面給出了證明，那么在時(shí)間效率方面如何呢？

為了回答這個(gè)問題，團(tuán)隊(duì)成員分別測(cè)量了每個(gè)模型自開始訓(xùn)練到收斂的準(zhǔn)確時(shí)間，具體結(jié)果呈現(xiàn)在表 4 中。很明顯，大多數(shù)情況下，BGNN 和 Rse-GNN 的運(yùn)行速度都要比 GNNs 快。這也就說明，BGNN 和 Rse-GNN 模型比 GNN 更加有效，在提高性能的基礎(chǔ)上并不會(huì)增加時(shí)間成本。例如，對(duì)于 VK 數(shù)據(jù)集，BGNN 和 Rse-GNN 的運(yùn)行速度分別比 GNN 快 3 倍和 2 倍。

最后做下總結(jié)，本文提到的新穎方法 BGNN，是一種端到端的方法，可以與任何消息傳遞神經(jīng)網(wǎng)絡(luò)和梯度增強(qiáng)方法結(jié)合使用。它首先利用 GBDT 構(gòu)建異構(gòu)數(shù)據(jù)常見的超平面決策邊界，然后借助 GNNs 使用關(guān)系信息來提升預(yù)測(cè)。最終通過大量的實(shí)驗(yàn)證明，BGNN 在預(yù)測(cè)精度和訓(xùn)練時(shí)間方面均優(yōu)于現(xiàn)有的方法。作者提示，可以將此方法擴(kuò)展到圖級(jí)別的預(yù)測(cè)任務(wù)上，如圖分類或子圖檢測(cè)等有前景的方向上。

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊(cè)深度學(xué)習(xí)筆記專輯《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)專輯 本站qq群704220115，加入微信群請(qǐng)掃碼： 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【论文解读】ICLR 2021丨当梯度提升遇到图神经网络，“鱼和熊掌”皆可兼得的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。