圖機器學習無處不在，用 Transformer 可緩解 GNN 限制

本文作者：我在思考中

2023-01-12 12:00

導語：從前神經方法到圖神經網絡是當前常用的圖上學習方法。

作者 | Clémentine Fourrier

編譯 | 黃楠

編輯 | 陳彩嫻

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

近日，Hugging Face 研究科學家 Clémentine Fourrier 在文章《Introduction to Graph Machine Learning》就介紹了今天這種無處不在的圖機器學習。什么是圖形？為什么要使用圖？如何最好地表示圖？人們如何在圖上學習？Clémentine Fourrier 指出，圖是對由關系鏈接項目的描述，其中，從前神經方法到圖神經網絡仍然是目前人們常用的圖上學習方法。

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

圖是對關系鏈接項目的描述

從本質上來看，圖是對由關系鏈接項目的描述。圖（或網絡）的項目稱為節點（或頂點），由邊（或鏈接）來進行連接。例如在社交網絡中，節點是用戶，邊是用戶彼此間的連接；在分子中，節點是原子，邊緣是它們的分子鍵。

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

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

在圖層面，主要任務包括以下：

圖形生成，用于藥物發現以生成新的合理分子
圖演化，即給定一個圖來預測它將如何隨時間演化，在物理學中可用于預測系統的演化
圖級預測，來自圖的分類或回歸任務，例如預測分子的毒性

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

邊緣的預測包括邊緣屬性預測和缺失邊緣預測。邊緣屬性預測有助于對藥物副作用的預測，給定一對藥物的不良副作用；缺失邊預測在推薦系統中則是用于預測圖中的兩個節點是否相關。

在子圖級別中，可進行社區檢測或子圖屬性預測。社交網絡可通過社區檢測來確定人們的聯系方式。子圖屬性預測多應用在行程系統中，例如谷歌地圖，可用于預測預計到達時間。

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

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

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

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

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

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

通過 ML 的圖形表示

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

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

前神經方法

簡單地使用工程特性

在神經網絡之前，圖形及其感興趣的項目可以通過特定任務的方式表示為特征的組合。在今天，這些特征仍用于數據增強和半監督學習，盡管存在更復雜的特征生成方法，但根據任務找到如何最好地將這些特征提供給到網絡至關重要。

節點級特征可以提供關于重要性的信息以及基于結構的信息，并對其進行組合。

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

圖注：2 到 5 節點小圖

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

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

基于行走的方法

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

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

圖神經網絡如何處理圖？

神經網絡可以泛化到看不見的數據?？紤]到此前提到的表示約束，一個好的神經網絡應該如何處理圖？

下面展示了兩種方法：

是置換不變的：

方程：f（P（G））=f（G）f（P（G））=f（G），其中 f 是網絡，P 是置換函數，G 是圖
解釋：經過網絡后，圖的表示及其排列應該相同

是置換等變的

方程：P（f（G））=f（P（G））P（f（G））=f（P（G）），其中 f 是網絡，P 是置換函數，G 是圖
解釋：在將節點傳遞到網絡之前置換節點應該等同于置換它們的表示

典型的神經網絡不是排列不變的，例如 RNN 或 CNN，因此一種新的架構——圖神經網絡被引入（最初是作為一種基于狀態的機器）。

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

聚合和消息傳遞

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

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

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

GNN 形狀和過度平滑問題

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

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

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

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

圖 Transformers

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

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

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

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

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

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