圖機(jī)器學(xué)習(xí)無處不在，用 Transformer 可緩解 GNN 限制

本文作者：我在思考中

2023-01-12 12:00

導(dǎo)語：從前神經(jīng)方法到圖神經(jīng)網(wǎng)絡(luò)是當(dāng)前常用的圖上學(xué)習(xí)方法。

作者 | Clémentine Fourrier

編譯 | 黃楠

編輯 | 陳彩嫻

在我們今天的生活中，圖的示例包括社交網(wǎng)絡(luò)、例如Twitter、Mastodon、以及任何鏈接論文和作者的引文網(wǎng)絡(luò)，分子，知識(shí)圖、例如 UML 圖、百科全書以及有超鏈接的網(wǎng)站，表示為句法樹的句子以及任何的 3D 網(wǎng)格等，可以說圖已經(jīng)無處不在。

近日，Hugging Face 研究科學(xué)家 Clémentine Fourrier 在文章《Introduction to Graph Machine Learning》就介紹了今天這種無處不在的圖機(jī)器學(xué)習(xí)。什么是圖形？為什么要使用圖？如何最好地表示圖？人們?nèi)绾卧趫D上學(xué)習(xí)？Clémentine Fourrier 指出，圖是對(duì)由關(guān)系鏈接項(xiàng)目的描述，其中，從前神經(jīng)方法到圖神經(jīng)網(wǎng)絡(luò)仍然是目前人們常用的圖上學(xué)習(xí)方法。

此外，有研究人員近期也開始考慮將 Transformers 應(yīng)用于圖中，Transformer 具有良好的可擴(kuò)展性，可緩解 GNN 存在的部分限制，前景十分可觀。

圖是對(duì)關(guān)系鏈接項(xiàng)目的描述

從本質(zhì)上來看，圖是對(duì)由關(guān)系鏈接項(xiàng)目的描述。圖（或網(wǎng)絡(luò)）的項(xiàng)目稱為節(jié)點(diǎn)（或頂點(diǎn)），由邊（或鏈接）來進(jìn)行連接。例如在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)是用戶，邊是用戶彼此間的連接；在分子中，節(jié)點(diǎn)是原子，邊緣是它們的分子鍵。

一個(gè)有類型節(jié)點(diǎn)或類型邊的圖被稱為異質(zhì)圖，舉個(gè)例子，在引文網(wǎng)絡(luò)的項(xiàng)目可以是論文或作者，有類型節(jié)點(diǎn)，而 XML 圖中的關(guān)系有類型邊；它不能僅僅通過其拓?fù)浣Y(jié)構(gòu)來表示，還需要額外的信息
圖也可以是有向的（例如追隨者網(wǎng)絡(luò)，A 跟隨 B 并不意味著 B 跟隨 A）或無向的（例如分子、原子之間的關(guān)系是雙向的）。邊可以連接不同的節(jié)點(diǎn)或一個(gè)節(jié)點(diǎn)與自身（自邊），但并非所有節(jié)點(diǎn)都需要連接

可以看到，使用數(shù)據(jù)必須首先考慮其最佳表示，包括同質(zhì)/異質(zhì)、有向/無向等。

在圖層面，主要任務(wù)包括以下：

圖形生成，用于藥物發(fā)現(xiàn)以生成新的合理分子
圖演化，即給定一個(gè)圖來預(yù)測它將如何隨時(shí)間演化，在物理學(xué)中可用于預(yù)測系統(tǒng)的演化
圖級(jí)預(yù)測，來自圖的分類或回歸任務(wù)，例如預(yù)測分子的毒性

節(jié)點(diǎn)層通常是對(duì)節(jié)點(diǎn)屬性的預(yù)測，例如 Alphafold 使用節(jié)點(diǎn)屬性預(yù)測來預(yù)測給定分子整體圖的原子 3D 坐標(biāo)，從而預(yù)測分子如何在 3D 空間中折疊，這是一個(gè)困難的生物化學(xué)問題。

邊緣的預(yù)測包括邊緣屬性預(yù)測和缺失邊緣預(yù)測。邊緣屬性預(yù)測有助于對(duì)藥物副作用的預(yù)測，給定一對(duì)藥物的不良副作用；缺失邊預(yù)測在推薦系統(tǒng)中則是用于預(yù)測圖中的兩個(gè)節(jié)點(diǎn)是否相關(guān)。

在子圖級(jí)別中，可進(jìn)行社區(qū)檢測或子圖屬性預(yù)測。社交網(wǎng)絡(luò)可通過社區(qū)檢測來確定人們的聯(lián)系方式。子圖屬性預(yù)測多應(yīng)用在行程系統(tǒng)中，例如谷歌地圖，可用于預(yù)測預(yù)計(jì)到達(dá)時(shí)間。

當(dāng)要進(jìn)行預(yù)測特定圖的演變時(shí)，轉(zhuǎn)換設(shè)置工作中的所有內(nèi)容，包括訓(xùn)練、驗(yàn)證和測試等，都可在同一個(gè)圖上完成。但從單個(gè)圖創(chuàng)建訓(xùn)練、評(píng)估或是測試的數(shù)據(jù)集并非易事，很多工作會(huì)使用不同的圖（單獨(dú)的訓(xùn)練/評(píng)估/測試拆分）完成，這被稱為歸納設(shè)置。

表示圖處理和操作的常見方法有兩種，一種是作為其所有邊的集合（可能由其所有節(jié)點(diǎn)的集合補(bǔ)充），或是作為其所有節(jié)點(diǎn)之間的鄰接矩陣。其中，鄰接矩陣是一個(gè)方陣（節(jié)點(diǎn)大小×節(jié)點(diǎn)大小），指示哪些節(jié)點(diǎn)直接連接到其他節(jié)點(diǎn)。要注意的是，由于大多數(shù)圖并不是密集連接的，因此具有稀疏的鄰接矩陣會(huì)使計(jì)算更加困難。

圖與 ML 中使用的典型對(duì)象非常不同，由于其拓?fù)浣Y(jié)構(gòu)比“序列”（如文本和音頻）或“有序網(wǎng)格”（如圖像和視頻）更復(fù)雜：即便可以將其表示為列表或矩陣，但這種表示不可以被視為是有序?qū)ο?。也即是說，如果打亂一個(gè)句子中的單詞，就可以創(chuàng)造一個(gè)新句子，如果將一個(gè)圖像打亂并重新排列它的列，就能創(chuàng)建了一個(gè)新圖像。

圖機(jī)器學(xué)習(xí)無處不在，用 Transformer 可緩解 GNN 限制

圖注：Hugging Face 標(biāo)志和被打亂的 Hugging Face 標(biāo)志，是完全不同的新形象

但圖的情況并非如此：如果我們洗掉圖的邊緣列表或鄰接矩陣的列，它仍然是同一個(gè)圖。

圖注：左邊是一個(gè)小圖，黃色表示節(jié)點(diǎn)，橙色表示邊；中心圖片上的鄰接矩陣，列和行按節(jié)點(diǎn)字母順序排列：節(jié)點(diǎn) A 的行（第一行）可以看到其連接到 E 和 C；右邊圖片打亂鄰接矩陣（列不再按字母順序排序），其仍為圖形的有效表示，即 A 仍連接到 E 和 C

通過 ML 的圖形表示

使用機(jī)器學(xué)習(xí)處理圖的常規(guī)過程，是首先為項(xiàng)目生成有意義的表示，其中，節(jié)點(diǎn)、邊或完整圖取決于具體任務(wù)需求，為目標(biāo)任務(wù)訓(xùn)練預(yù)測器。與其他模式一樣，可以通過限制對(duì)象的數(shù)學(xué)表示，以便在數(shù)學(xué)上與相似對(duì)象接近。但在此之中，相似性在圖 ML 中很難嚴(yán)格定義：例如，當(dāng)兩個(gè)節(jié)點(diǎn)具有相同的標(biāo)簽或相同的鄰居時(shí)，它們是否更相似？

如下面所示，本篇文章重點(diǎn)關(guān)注的是生成節(jié)點(diǎn)表示，一旦有了節(jié)點(diǎn)級(jí)的表示，就有可能獲得邊或圖級(jí)的信息。對(duì)邊級(jí)信息，可以將節(jié)點(diǎn)對(duì)的連接起來，或者做點(diǎn)乘；在圖級(jí)信息中，可以對(duì)所有節(jié)點(diǎn)級(jí)表示的串聯(lián)張量進(jìn)行全局池化，包括平均、求和等。但是，它仍然會(huì)使整個(gè)圖的信息變得平滑和丟失——遞歸的分層集合可能更有意義，或者增加一個(gè)虛擬節(jié)點(diǎn)，與圖中的所有其他節(jié)點(diǎn)相連，并將其表示作為整個(gè)圖的表示。

前神經(jīng)方法

簡單地使用工程特性

在神經(jīng)網(wǎng)絡(luò)之前，圖形及其感興趣的項(xiàng)目可以通過特定任務(wù)的方式表示為特征的組合。在今天，這些特征仍用于數(shù)據(jù)增強(qiáng)和半監(jiān)督學(xué)習(xí)，盡管存在更復(fù)雜的特征生成方法，但根據(jù)任務(wù)找到如何最好地將這些特征提供給到網(wǎng)絡(luò)至關(guān)重要。

節(jié)點(diǎn)級(jí)特征可以提供關(guān)于重要性的信息以及基于結(jié)構(gòu)的信息，并對(duì)其進(jìn)行組合。

節(jié)點(diǎn)中心性可用于衡量圖中節(jié)點(diǎn)的重要性，通過對(duì)每個(gè)節(jié)點(diǎn)鄰居中心性求和直到收斂來遞歸計(jì)算，或是通過節(jié)點(diǎn)間的最短距離度量來遞歸計(jì)算，節(jié)點(diǎn)度是其擁有的直接鄰居的數(shù)量；聚類系數(shù)衡量節(jié)點(diǎn)鄰居的連接程度；Graphlets 度向量計(jì)算則可計(jì)算有多少不同的 graphlets 以給定節(jié)點(diǎn)為根，其中，graphlets 可使用給定數(shù)量的連接節(jié)點(diǎn)來創(chuàng)建的所有迷你圖。

圖注：2 到 5 節(jié)點(diǎn)小圖

邊級(jí)特征用關(guān)于節(jié)點(diǎn)連通性的更詳細(xì)信息補(bǔ)充表示，其中就包括了兩個(gè)節(jié)點(diǎn)之間的最短距離、它們的共同相鄰點(diǎn)以及 Katz 指數(shù)（指兩個(gè)節(jié)點(diǎn)之間可能走過的一定長度的路徑的數(shù)量——其可以直接從鄰接矩陣中計(jì)算出來）。

圖級(jí)特征包含關(guān)于圖相似性和特殊性的高級(jí)信息，其中，小圖計(jì)數(shù)，盡管計(jì)算成本很高，但提供了關(guān)于子圖形狀的信息。核心方法通過不同的 "節(jié)點(diǎn)袋 "方法（類似于詞袋）來衡量圖之間的相似性。

基于行走的方法

基于行走的方法使用隨機(jī)行走中從節(jié)點(diǎn) i 訪問節(jié)點(diǎn) j 的概率來定義相似性度量，這些方法結(jié)合了局部和全局信息。例如，此前 Node2Vec 模擬圖形節(jié)點(diǎn)之間的隨機(jī)游走，使用 skip-gram 處理這些游走，就像我們處理句子中的單詞一樣，以計(jì)算嵌入。

這些方法還可用于加速 PageRank 方法的計(jì)算，該方法給每個(gè)節(jié)點(diǎn)分配一個(gè)重要性分?jǐn)?shù)，基于它與其他節(jié)點(diǎn)的連接，例如通過隨機(jī)行走來評(píng)估其訪問頻率。但上述方法也存在一定的局限性，它們不能獲得新節(jié)點(diǎn)的嵌入，不能很好地捕捉節(jié)點(diǎn)之間的結(jié)構(gòu)相似性，不能使用添加的特征。

圖神經(jīng)網(wǎng)絡(luò)如何處理圖？

神經(jīng)網(wǎng)絡(luò)可以泛化到看不見的數(shù)據(jù)?？紤]到此前提到的表示約束，一個(gè)好的神經(jīng)網(wǎng)絡(luò)應(yīng)該如何處理圖？

下面展示了兩種方法：

是置換不變的：

方程：f（P（G））=f（G）f（P（G））=f（G），其中 f 是網(wǎng)絡(luò)，P 是置換函數(shù)，G 是圖
解釋：經(jīng)過網(wǎng)絡(luò)后，圖的表示及其排列應(yīng)該相同

是置換等變的

方程：P（f（G））=f（P（G））P（f（G））=f（P（G）），其中 f 是網(wǎng)絡(luò)，P 是置換函數(shù)，G 是圖
解釋：在將節(jié)點(diǎn)傳遞到網(wǎng)絡(luò)之前置換節(jié)點(diǎn)應(yīng)該等同于置換它們的表示

典型的神經(jīng)網(wǎng)絡(luò)不是排列不變的，例如 RNN 或 CNN，因此一種新的架構(gòu)——圖神經(jīng)網(wǎng)絡(luò)被引入（最初是作為一種基于狀態(tài)的機(jī)器）。

一個(gè) GNN 是由連續(xù)的層組成的。GNN 層將節(jié)點(diǎn)表示為其鄰居的表示和來自上一層（消息傳遞）的自身組合，通常還會(huì)加上激活以添加一些非線性。而與其他模型相比，CNN 可看作是具有固定鄰居大小（通過滑動(dòng)窗口）和排序（非排列等變）的 GNN；而沒有位置嵌入的 Transformer 可以看作是全連接輸入圖上的 GNN。

聚合和消息傳遞

聚合來自節(jié)點(diǎn)鄰居的信息有很多方法，例如求和、平均，此前已有的類似聚類方法包括：

Graph Convolutional Networks，對(duì)節(jié)點(diǎn)鄰居的歸一化表示進(jìn)行平均；
Graph Attention Networks，學(xué)習(xí)根據(jù)它們的重要性來權(quán)衡不同鄰居（如Transformer）；
GraphSAGE，在使用最大集合在幾個(gè)步驟中聚合信息之前，在不同的躍點(diǎn)對(duì)鄰居進(jìn)行采樣；
Graph Isomorphism Networks，通過將 MLP 應(yīng)用于節(jié)點(diǎn)鄰居表示的總和來聚合表示。

選擇一個(gè)聚合：一些聚合技術(shù)（特別是平均/最大集合）在創(chuàng)建精細(xì)表示以區(qū)分類似節(jié)點(diǎn)的不同節(jié)點(diǎn)鄰居表示時(shí)，會(huì)遇到失敗的情況；例如，通過均值集合，一個(gè)有4個(gè)節(jié)點(diǎn)鄰居表示為1、1、-1、-1，平均為0，與一個(gè)只有3個(gè)節(jié)點(diǎn)表示為-1、0、1的鄰居是沒有區(qū)別的。

GNN 形狀和過度平滑問題

在每個(gè)新層，節(jié)點(diǎn)表示包括越來越多的節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)通過第一層，是其直接鄰居的聚合。通過第二層，它仍然是其直接鄰居的聚合，但此刻其表示還包括了它們自己的鄰居（來自第一層）。在 n 層之后，所有節(jié)點(diǎn)的表示成為其距離為 n 的所有鄰居的集合，因此，如果其直徑小于n，則為全圖的聚合。

如果網(wǎng)絡(luò)層數(shù)太多，則存在每個(gè)節(jié)點(diǎn)成為完整圖的聚合的風(fēng)險(xiǎn)（并且節(jié)點(diǎn)表示對(duì)所有節(jié)點(diǎn)收斂到相同的表示），這被稱為過度平滑問題，可通過以下方式來解決：

將 GNN 縮放到足夠小的層數(shù)，從而不會(huì)將每個(gè)節(jié)點(diǎn)近似為整個(gè)網(wǎng)絡(luò)（通過首先分析圖的直徑和形狀）
增加層的復(fù)雜性
添加非消息傳遞層來處理消息（例如簡單的 MLP）
添加跳過連接

過度平滑問題是圖 ML 中的一個(gè)重要研究領(lǐng)域，由于它會(huì)阻止 GNN 擴(kuò)大規(guī)模，就像 Transformers 在其他模型中被證明的那樣。

圖 Transformers

沒有位置編碼層的 Transformer 是置換不變的，并且 Transformer 還具有良好的可擴(kuò)展性，因此研究人員在近期開始考慮將 Transformers 應(yīng)用于圖中。大多數(shù)方法的重點(diǎn)是通過尋找最佳特征和最佳方式來表示圖形，并改變注意力以適應(yīng)這種新數(shù)據(jù)。

下面展示了一些方法，這些方法在斯坦福大學(xué)的 Open Graph Benchmark 上取得最先進(jìn)或接近的結(jié)果：

Graph Transformer for Graph-to-Sequence Learning，引入一個(gè)圖 Transformer，它將節(jié)點(diǎn)表示為它們的嵌入和位置嵌入的串聯(lián)，節(jié)點(diǎn)關(guān)系表示二者間的最短路徑，并將兩者組合成一個(gè)關(guān)系——增強(qiáng)自我關(guān)注。
Rethinking Graph Transformers with Spectral Attention，引入了 Spectral Attention Networks （SAN），這些將節(jié)點(diǎn)特征與學(xué)習(xí)的位置編碼（從拉普拉斯特征向量/值計(jì)算）結(jié)合起來，用作注意力中的鍵和查詢，注意力值是邊緣特征。
GRPE: Relative Positional Encoding for Graph Transformer，介紹了圖相對(duì)位置編碼Transformer，其通過將圖級(jí)位置編碼與節(jié)點(diǎn)信息、邊級(jí)位置編碼與節(jié)點(diǎn)信息相結(jié)合，并將兩者結(jié)合在注意力中來表示圖。
Global Self-Attention as a Replacement for Graph Convolution ，引入了 Edge Augmented Transformer，該體系結(jié)構(gòu)分別嵌入節(jié)點(diǎn)和邊緣，并將它們聚合在經(jīng)過修改的注意力中。
Do Transformers Really Perform Badly for Graph Representation，介紹了微軟的 Graphormer，它在 OGB 上問世時(shí)獲得了第一名。該架構(gòu)使用節(jié)點(diǎn)特征作為注意力中的查詢/鍵/值，并在注意力機(jī)制中將它們的表示與中心性、空間和邊緣編碼相結(jié)合。

近期有研究“Pure Transformers are Powerful Graph Learners”在方法中引入了 TokenGT，將輸入圖表示為一系列節(jié)點(diǎn)和邊嵌入，也即是使用正交節(jié)點(diǎn)標(biāo)識(shí)符和可訓(xùn)練類型標(biāo)識(shí)符進(jìn)行增強(qiáng)，沒有位置嵌入，并將此序列作為輸入提供給 Transformers，此方法非常簡單，同時(shí)也非常有效。

論文地址：https://arxiv.org/pdf/2207.02505.pdf

此外，在研究“Recipe for a General, Powerful, Scalable Graph Transformer”中，跟其他方法不同的是，它引入的不是模型而是框架，稱為 GraphGPS，可允許將消息傳遞網(wǎng)絡(luò)與線性（遠(yuǎn)程）Transformer 結(jié)合起來，輕松創(chuàng)建混合網(wǎng)絡(luò)。該框架還包含幾個(gè)用于計(jì)算位置和結(jié)構(gòu)編碼（節(jié)點(diǎn)、圖形、邊緣級(jí)別）、特征增強(qiáng)、隨機(jī)游走等的工具。