圖機器學(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ò)，分子，知識圖、例如 UML 圖、百科全書以及有超鏈接的網(wǎng)站，表示為句法樹的句子以及任何的 3D 網(wǎng)格等，可以說圖已經(jīng)無處不在。

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

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

圖是對關(guān)系鏈接項目的描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過 ML 的圖形表示

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

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

前神經(jīng)方法

簡單地使用工程特性

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

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

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

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

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

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

基于行走的方法

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

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

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

神經(jīng)網(wǎng)絡(luò)可以泛化到看不見的數(shù)據(jù)。考慮到此前提到的表示約束，一個好的神經(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é)點傳遞到網(wǎng)絡(luò)之前置換節(jié)點應(yīng)該等同于置換它們的表示

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

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

聚合和消息傳遞

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

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

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

GNN 形狀和過度平滑問題

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

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

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

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

圖 Transformers

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

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

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

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

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

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