圖神經(jīng)網(wǎng)絡(luò)（GNN）是機(jī)器學(xué)習(xí)中最熱門的領(lǐng)域之一，在過(guò)去短短數(shù)月內(nèi)就有多篇優(yōu)秀的綜述論文。但數(shù)據(jù)科學(xué)家 Matt Ranger 對(duì) GNN 卻并不感冒。他認(rèn)為這方面的研究會(huì)取得進(jìn)展，但其他研究方向或許更重要。

機(jī)器之心對(duì)這篇博客進(jìn)行了編譯整理，以下是博客內(nèi)容。

模型的關(guān)鍵是壓縮

圖經(jīng)常被認(rèn)為是一種「非歐幾里得」數(shù)據(jù)類型，但實(shí)際上并不是。正則圖（regular graph）只是研究鄰接矩陣的另一種方式：

如上圖所示，充滿實(shí)數(shù)的矩陣卻被稱為「非歐幾里得」，這很奇怪。

其實(shí)這是出于實(shí)際原因。大多數(shù)圖都相當(dāng)稀疏，因此矩陣中會(huì)包含很多 0。從這個(gè)角度看，非零數(shù)值非常重要，這讓問(wèn)題接近于（計(jì)算上很難的）離散數(shù)學(xué)，而不是（容易的）連續(xù)、梯度友好的數(shù)學(xué)。

有了全矩陣，情況會(huì)變得容易

如果不考慮物理領(lǐng)域的內(nèi)容，并假設(shè)存在全鄰接矩陣，那么很多問(wèn)題就會(huì)迎刃而解。

首先，網(wǎng)絡(luò)節(jié)點(diǎn)嵌入不再是問(wèn)題。一個(gè)節(jié)點(diǎn)就是矩陣中的一行，因此它本身已經(jīng)是數(shù)字向量。

其次，所有網(wǎng)絡(luò)預(yù)測(cè)問(wèn)題也都被解決。一個(gè)足夠強(qiáng)大且經(jīng)過(guò)良好調(diào)整的模型將只提取網(wǎng)絡(luò)與附加到節(jié)點(diǎn)上的目標(biāo)變量之間的全部信息。

NLP 也只是一種花哨的矩陣壓縮

讓我們把目光從圖轉(zhuǎn)移到自然語(yǔ)言處理（NLP）領(lǐng)域。大多數(shù) NLP 問(wèn)題都可以看成圖問(wèn)題，所以這并不是題外話。

首先，像 Word2Vec、GloVe 這類經(jīng)典詞嵌入模型只進(jìn)行了矩陣分解。

GloVe 算法基于詞袋（bag of words）矩陣的一種變體運(yùn)行。它會(huì)遍歷句子，并創(chuàng)建一個(gè)（隱式）共現(xiàn)圖，圖的節(jié)點(diǎn)是詞，邊的權(quán)重取決于這些單詞在句子中一同出現(xiàn)的頻率。之后，Glove 對(duì)共現(xiàn)圖的矩陣表示進(jìn)行矩陣分解，Word2Vec 在數(shù)學(xué)方面是等效的。

語(yǔ)言模型也只是矩陣壓縮

NLP 中許多 SOTA 方法都離不開(kāi)語(yǔ)言模型。以 BERT 為例，BERT 基于語(yǔ)境來(lái)預(yù)測(cè)單詞：

這就使我們正在分解的矩陣從詞對(duì)共現(xiàn)發(fā)展為基于句子語(yǔ)境的共現(xiàn)：

我們正在培養(yǎng)待分解的「理想矩陣」。正如 Hanh & Futrell 所說(shuō)：

人類語(yǔ)言和語(yǔ)言建模具有無(wú)限的統(tǒng)計(jì)復(fù)雜度，但可以在較低層次上得到很好地近似。這一觀察結(jié)果有兩層含義：

我們可以使用相對(duì)較小的模型獲得不錯(cuò)的結(jié)果；擴(kuò)大模型具備很大潛力。

語(yǔ)言模型解決了很大的問(wèn)題空間，以至于從柯氏復(fù)雜性（Kolmogorov Complexity）角度來(lái)看，它們可能近似壓縮了整個(gè)語(yǔ)言。龐大的語(yǔ)言模型可能記住了很多信息，而不是壓縮信息。

我們能像語(yǔ)言模型一樣對(duì)任意圖執(zhí)行上采樣嗎？

實(shí)際上，我們已經(jīng)在做了。

我們將圖的「一階」嵌入稱為通過(guò)直接分解圖的鄰接矩陣或拉普拉斯矩陣（Laplacian matrix）來(lái)運(yùn)行的方法。只要使用拉普拉斯特征映射（Laplacian Eigenmap）或采用拉普拉斯的主要組成部分進(jìn)行圖嵌入，那它就是一階方法。類似地，GloVe 是詞共現(xiàn)圖上的一階方法。我最喜歡的圖一階方法之一是 ProNE，它和大多數(shù)方法一樣有效，但速度快了一個(gè)數(shù)量級(jí)。

高階方法嵌入了原始矩陣和鄰居的鄰居連接（第二階）以及更深的 k 步連接。GraRep 表明，通過(guò)擴(kuò)展圖矩陣可以基于一階方法生成高階表示。

高階方法是在圖上執(zhí)行的上采樣?；诖笮袜徲虿蓸拥?GNN 和 node2vec 等隨機(jī)游走方法執(zhí)行的是高階嵌入。

性能增益在哪兒？

過(guò)去 5 年中，大多數(shù) GNN 論文的實(shí)驗(yàn)數(shù)據(jù)對(duì)從業(yè)者選擇要使用的模型都是無(wú)用的。

正如論文《Open Graph Benchmark： Datasets for Machine Learning on Graphs》中所寫(xiě)的那樣，許多 GNN 論文基于一些節(jié)點(diǎn)數(shù)為 2000-20，000 的小型圖數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)（如 Cora、CiteSeer、PubMed）。這些數(shù)據(jù)集無(wú)法真正地區(qū)分不同 GNN 方法之間的區(qū)別。

近期的一些研究開(kāi)始直接解決這一問(wèn)題，但是為什么研究者這么長(zhǎng)時(shí)間一直在小型、無(wú)用的數(shù)據(jù)集上做實(shí)驗(yàn)?zāi)?？這個(gè)問(wèn)題值得討論。

性能和任務(wù)有關(guān)

一個(gè)令人震驚的事實(shí)是，盡管語(yǔ)言模型在大量 NLP 任務(wù)中達(dá)到最優(yōu)性能，但如果你只是把句子嵌入用于下游模型，那么從語(yǔ)言模型嵌入中獲得的性能增益并不比累加 Word2Vec 詞嵌入這類簡(jiǎn)單方法要多。

類似地，我發(fā)現(xiàn)對(duì)于很多圖而言，簡(jiǎn)單的一階方法在圖聚類和節(jié)點(diǎn)標(biāo)簽預(yù)測(cè)任務(wù)中的性能和高階嵌入方法差不多。事實(shí)上，高階方法還消耗了大量算力，造成了浪費(fèi)。

此類一階方法包括 ProNE 和 GGVec（一階）。

高階方法通常在鏈接預(yù)測(cè)任務(wù)上有更好的表現(xiàn)。

有趣的是，鏈接預(yù)測(cè)任務(wù)中的性能差距對(duì)于人工創(chuàng)建的圖而言是不存在的。這表明，高階方法的確能夠?qū)W習(xí)到現(xiàn)實(shí)圖的某種內(nèi)在結(jié)構(gòu)。

就可視化而言，一階方法表現(xiàn)更好。高階方法的可視化圖可能會(huì)出現(xiàn)偽影，例如 Node2Vec 可視化會(huì)有長(zhǎng)絲狀的結(jié)構(gòu)，它們來(lái)自較長(zhǎng)單鏈隨機(jī)游走的嵌入。高階方法和一階方法的可視化對(duì)比情況參見(jiàn)下圖：

最后，有時(shí)候簡(jiǎn)單的方法能夠打敗高階方法。問(wèn)題在于我們不知道什么時(shí)候一類方法優(yōu)于另一類方法，當(dāng)然也不知道其原因。

不同類型的圖在被不同方法表示時(shí)反應(yīng)有好有壞，這背后當(dāng)然是有原因的。但這目前仍是個(gè)開(kāi)放性問(wèn)題。

這其中的一大因素是研究空間充斥了無(wú)用的新算法。原因如下：

學(xué)術(shù)動(dòng)機(jī)阻礙進(jìn)步

憤世嫉俗者認(rèn)為機(jī)器學(xué)習(xí)論文是通過(guò)以下方式炮制的：

使用已有的算法；

添加新的層 / 超參數(shù)，用數(shù)學(xué)形式描述其重要性；

對(duì)超參數(shù)執(zhí)行網(wǎng)格搜索，直到該新方法打敗被模仿的那個(gè)基線方法；

絕不對(duì)在「實(shí)驗(yàn)結(jié)果」部分中進(jìn)行對(duì)比的方法執(zhí)行網(wǎng)格搜索；

給新方法起個(gè)不錯(cuò)的縮寫(xiě)名稱，不公布 Python 2 代碼。

我不是唯一一個(gè)對(duì)當(dāng)前可復(fù)現(xiàn)研究持此觀點(diǎn)的人。至少近兩年情況好了一點(diǎn)。

所有進(jìn)展都關(guān)乎實(shí)際問(wèn)題

早在四十多年前，我們就已經(jīng)知道如何訓(xùn)練神經(jīng)網(wǎng)絡(luò)了，但直到 2012 年 AlexNet 出現(xiàn)，神經(jīng)網(wǎng)絡(luò)才出現(xiàn)爆炸式發(fā)展。原因在于實(shí)現(xiàn)和硬件都發(fā)展到了一個(gè)節(jié)點(diǎn)，足以使深度學(xué)習(xí)應(yīng)用于實(shí)際問(wèn)題。

類似地，至少 20 年前，我們就已經(jīng)知道如何將詞共現(xiàn)矩陣轉(zhuǎn)換為詞嵌入。但詞嵌入技術(shù)直到 2013 年 Word2Vec 問(wèn)世才出現(xiàn)爆發(fā)式發(fā)展。其突破點(diǎn)在于基于 minibatch 的方法允許在商用硬件上訓(xùn)練 Wikipedia 規(guī)模的嵌入模型。

如果只花費(fèi)數(shù)天或數(shù)周時(shí)間在小規(guī)模數(shù)據(jù)上訓(xùn)練模型，那么這個(gè)領(lǐng)域的方法很難取得進(jìn)步。研究者會(huì)失去探索新方法的動(dòng)力。如果你想取得進(jìn)展，你必須嘗試在商用硬件上以合理時(shí)間運(yùn)行模型。谷歌的初始搜索算法最開(kāi)始也是在商用硬件上運(yùn)行的。

效率更重要

深度學(xué)習(xí)研究的爆發(fā)式發(fā)展離不開(kāi)效率的提升，以及更好的軟件庫(kù)和硬件支持。

模型架構(gòu)沒(méi)那么重要

今年更加重要的一篇論文是 OpenAI 的《Scaling Laws for Neural Language Models》。這篇文章指出，模型中的原始參數(shù)數(shù)量是對(duì)整體性能最具預(yù)測(cè)性的特征。最初的 BERT 論文也指出了這一點(diǎn)，并推動(dòng)了 2020 年大規(guī)模語(yǔ)言模型的迅速增加。

這一現(xiàn)實(shí)呼應(yīng)了 Rich Sutton 在《苦澀的教訓(xùn) （https://mp.weixin.qq.com/s/B6rnFLxYe2xe5C5f2fDnmw）》一文中提出的觀點(diǎn)：

利用算力的一般方法最終是最有效的方法。

Transformer 可能也在替代卷積，正如知名 YouTube 博主 Yannic Kilcher 所說(shuō)，Transformer 正在毀掉一切。它們可以和圖網(wǎng)絡(luò)結(jié)合，這也是最近幾年出現(xiàn)的方法之一，而且在基準(zhǔn)測(cè)試中表現(xiàn)出色。

研究者似乎在架構(gòu)方面投入了太多精力，但架構(gòu)并沒(méi)有那么重要，因?yàn)槟憧梢酝ㄟ^(guò)堆疊更多層來(lái)近似任何東西。

效率的勝利是偉大的，而神經(jīng)網(wǎng)絡(luò)架構(gòu)只是實(shí)現(xiàn)這一目標(biāo)的方式之一。在架構(gòu)方面投入過(guò)多的精力，只會(huì)使我們錯(cuò)過(guò)其他方面的巨大收益。

當(dāng)前的圖數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)太差勁了

NetworkX 是一個(gè)糟糕的庫(kù)。我是說(shuō)，如果你正在處理一些微小的圖，該庫(kù)表現(xiàn)還 OK。但如果處理大規(guī)模的圖任務(wù)，這個(gè)庫(kù)會(huì)令你抓狂且迫使你重寫(xiě)所有的東西。

這時(shí)，多數(shù)處理大規(guī)模圖任務(wù)的用戶不得不手動(dòng)滾動(dòng)一些數(shù)據(jù)結(jié)構(gòu)。這很難，因?yàn)槟愕挠?jì)算機(jī)內(nèi)存是由 1 和 0 組成的一維數(shù)組，并且圖沒(méi)有明顯的一維映射。

這種情況在我們更新圖（如添加 / 移除節(jié)點(diǎn) / 邊緣）時(shí)會(huì)變得更加困難。以下提供了幾個(gè)替代選擇：

分離的指針網(wǎng)絡(luò)

NetworkX 就是最好的示例。每個(gè)節(jié)點(diǎn)對(duì)象都包含指向其他節(jié)點(diǎn)的指針列表（節(jié)點(diǎn)邊緣），其布局就像鏈表一樣。

鏈表完全違背了現(xiàn)代計(jì)算機(jī)的設(shè)計(jì)方式。它從內(nèi)存中讀取數(shù)據(jù)非常慢，但在內(nèi)存中的運(yùn)行速度卻很快（快了兩個(gè)數(shù)量級(jí)）。在這種布局中，無(wú)論何時(shí)做任何事情，你都需要往返 RAM。這在設(shè)計(jì)上就很慢，你可以使用 Ruby、C 或者匯編語(yǔ)言編寫(xiě)，但還是很慢，這是因?yàn)橛布系膬?nèi)存讀取速度就很慢。

這種布局的主要優(yōu)勢(shì)在于其添加了新節(jié)點(diǎn) O（1）。所以如果你在維護(hù)一個(gè)龐大的圖，并且添加和移除節(jié)點(diǎn)的頻率與從圖中讀取數(shù)據(jù)的頻率相同，則這種布局挺適合的。

另外一個(gè)優(yōu)勢(shì)是這種布局可以「擴(kuò)展」。這是因?yàn)樗袛?shù)據(jù)彼此之間可解耦，所以你可以將這種數(shù)據(jù)結(jié)構(gòu)放置在集群上。但實(shí)際上，你正在為自身問(wèn)題創(chuàng)造一個(gè)復(fù)雜的解決方案。

稀疏鄰接矩陣

稀疏鄰接矩陣非常適合只讀（read-only）圖。我在自己的 nodevectors 庫(kù)中將它作為后端使用，很多其他的庫(kù)編寫(xiě)者使用 Scipy CSR Matrix。

最流行的布局是 CSR 格式，你可以使用 3 個(gè)數(shù)組來(lái)保存圖，分別用于邊緣終點(diǎn)、邊緣權(quán)重和「索引指針」，該指針說(shuō)明邊緣來(lái)自哪個(gè)節(jié)點(diǎn)。

此外，得益于 CSR 的 3 數(shù)組布局，它可以在單個(gè)計(jì)算機(jī)上進(jìn)行擴(kuò)展：CSR 矩陣可以放置在磁盤(pán)上，而不用放在內(nèi)存中。你只需要對(duì) 3 個(gè)數(shù)組執(zhí)行內(nèi)存映射，并在磁盤(pán)上使用它們。

隨著現(xiàn)代 NVMe 驅(qū)動(dòng)器的出現(xiàn)，隨機(jī)搜索速度不再那么慢了，要比擴(kuò)展基于鏈表的圖時(shí)進(jìn)行分布式網(wǎng)絡(luò)調(diào)用快得多。但這種表征存在的問(wèn)題是：添加一個(gè)節(jié)點(diǎn)或邊緣意味著重建整個(gè)數(shù)據(jù)結(jié)構(gòu)。

Edgelist 表征

這種表征具有 3 個(gè)數(shù)組：分別用于邊緣源、邊緣終點(diǎn)和邊緣權(quán)重。DGL 包在其內(nèi)部使用的正是這種表征。其簡(jiǎn)單、緊湊的布局非常適合分析使用。

與 CSR 圖相比，該表征的問(wèn)題在于某些尋軌操作（seek operation）速度較慢。假設(shè)你要找出節(jié)點(diǎn)＃4243 的所有邊緣，則如果不維護(hù)索引指針數(shù)組，就無(wú)法跳轉(zhuǎn)到那里。

因此，你可以保持 sorted order 和二分搜索 （O（log2n）） 或 unsorted order 和線性搜索 （O（n））。

這種數(shù)據(jù)結(jié)構(gòu)也可以在內(nèi)存映射的磁盤(pán)陣列上使用，并且在 unsorted 版本上節(jié)點(diǎn)添加速度很快（在 sorted 版本上運(yùn)行緩慢）。

全局方法是條死胡同

一次性處理整個(gè)圖的方法無(wú)法利用算力，因?yàn)樗鼈冞_(dá)到一定規(guī)模就會(huì)把 RAM 耗盡。

因此，任何想要成為新標(biāo)準(zhǔn)的方法都要能對(duì)圖的各個(gè)部分進(jìn)行逐個(gè)更新。

基于采樣的方法

未來(lái)，采樣效率將變得更加重要。

Edgewise 局部方法。我所知道的能做到這一點(diǎn)的算法只有 GloVe 和 GGVec，它們通過(guò)一個(gè)邊列表，并在每一步上更新嵌入權(quán)重。這種方法的問(wèn)題在于，它們很難應(yīng)用于更加高階的方法。但其優(yōu)點(diǎn)也很明顯：很容易進(jìn)行擴(kuò)展，即使是在一臺(tái)計(jì)算機(jī)上也不例外。此外，逐漸增加新的節(jié)點(diǎn)也很簡(jiǎn)單，只需要獲取現(xiàn)有的嵌入，添加一個(gè)新節(jié)點(diǎn)，然后在數(shù)據(jù)上執(zhí)行一個(gè)新的 epoch。

隨機(jī)游走采樣。采用這一方法的包括 deepwalk 及相關(guān)的后續(xù)工作，通常用于嵌入而不是 GNN 方法。這在計(jì)算上可能非常昂貴，添加新節(jié)點(diǎn)也很困難。但它是可以擴(kuò)展的，Instagram 就用它來(lái)為自己的推薦系統(tǒng)提供信息。

鄰接采樣。這是目前 GNN 中最普遍的一種采樣方法，低階、高階都適用（取決于 neighborhood 的大?。?。它的可擴(kuò)展性也很好，盡管很難高效執(zhí)行。Pinterest 的推薦算法用的就是這種方法。

結(jié)論

這里有幾個(gè)有趣的問(wèn)題：

圖類型和圖方法之間是什么關(guān)系？

統(tǒng)一的基準(zhǔn)測(cè)試，如 OGB。

我們把隨機(jī)的模型扔給隨機(jī)的基準(zhǔn)，卻不知道為什么或者什么時(shí)候它們表現(xiàn)得更好。

更基礎(chǔ)的研究。我很好奇：其他表示類型（如 Poincarre 嵌入）能否有效地編碼定向關(guān)系？

另一方面，我們不應(yīng)該再專注于添加新的層，并在相同的小型數(shù)據(jù)集上進(jìn)行測(cè)試。沒(méi)人在乎這個(gè)。

原文標(biāo)題：有人說(shuō)別太把圖神經(jīng)網(wǎng)絡(luò)當(dāng)回事兒

文章出處：【微信公眾號(hào)：人工智能與大數(shù)據(jù)技術(shù)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq