本文主要介紹圖機器學習的基礎知識。

我們首先學習什么是圖、為什么使用圖以及如何最佳地表示圖。然后，我們簡要介紹大家如何在圖數據上學習，從神經網絡以前的方法 (同時我們會探索圖特征) 到現在廣為人知的圖神經網絡 (Graph Neural Network，GNN) ，最后，我們將一窺圖數據上的 Transformers 世界。

什么是圖？

本質上來講，圖描述了由關系互相鏈接起來的實體。

現實中有很多圖的例子，包括社交網絡 (如推特，長毛象，以及任何鏈接論文和作者的引用網絡) 、分子、知識圖譜 (如 UML 圖，百科全書，以及那些頁面之間有超鏈接的網站) 、被表示成句法樹的句子、3D 網格等等。因此，可以毫不夸張地講，圖無處不在。

圖 (或網絡) 中的實體稱為 節點 (或頂點) ，它們之間的連接稱為 邊 (或鏈接) 。舉個例子，在社交網絡中，節點是用戶，而邊是他 (她) 們之間的連接關系；在分子中，節點是原子，而邊是它們之間的分子鍵。

可以存在不止一種類型的節點或邊的圖稱為 異構圖 (heterogeneous graph) (例子：引用網絡的節點有論文和作者兩種類型，含有多種關系類型的 XML 圖的邊是多類型的) 。異構圖不能僅由其拓撲結構來表征，它需要額外的信息。本文主要討論同構圖 (homogeneous graph) 。

圖還可以是 有向 (directed) 的 (如一個關注網絡中，A 關注了 B，但 B 可以不關注 A) 或者是 無向 (undirected) 的 (如一個分子中，原子間的關系是雙向的) 。邊可以連接不同的節點，也可以自己連接自己 (自連邊，self-edges) ，但不是所有的節點都必須有連接。

如果你想使用自己的數據，首先你必須考慮如何最佳地刻畫它 (同構 / 異構，有向 / 無向等) 。

圖有什么用途？

我們一起看看在圖上我們可以做哪些任務吧。

在 圖層面，主要的任務有：

圖生成: 可在藥物發現任務中用于生成新的可能的藥物分子，

圖演化 (給定一個圖，預測它會如何隨時間演化) : 可在物理學中用于預測系統的演化，

圖層面預測 (基于圖的分類或回歸任務) : 如預測分子毒性。

在 節點層面，通常用于預測節點屬性。舉個例子，Alphafold 使用節點屬性預測方法，在給定分子總體圖的條件下預測原子的 3D 坐標，并由此預測分子在 3D 空間中如何折疊，這是個比較難的生物化學問題。

在 邊層面，我們可以做邊屬性預測或缺失邊預測。邊屬性預測可用于在給定藥物對 (pair) 的條件下預測藥物的不良副作用。缺失邊預測被用于在推薦系統中預測圖中的兩個節點是否相關。

另一種可能的工作是在 子圖層面 的，可用于社區檢測或子圖屬性預測。社交網絡用社區檢測確定人們之間如何連接。我們可以在行程系統 (如 Google Maps) 中發現子圖屬性預測的身影，它被用于預測到達時間。

完成這些任務有兩種方式。

當你想要預測特定圖的演化時，你工作在 直推 (transductive) 模式，直推模式中所有的訓練、驗證和推理都是基于同一張圖。如果這是你的設置，要多加小心！在同一張圖上創建訓練 / 評估 / 測試集可不容易。 然而，很多任務其實是工作在不同的圖上的 (不同的訓練 / 評估 / 測試集劃分) ，我們稱之為 歸納 (inductive) 模式。

如何表示圖？

常用的表示圖以用于后續處理和操作的方法有 2 種：

表示成所有邊的集合 (很有可能也會加上所有節點的集合用以補充) 。

或表示成所有節點間的鄰接矩陣。鄰接矩陣是一個 大小的方陣，它指明圖上哪些節點間是直接相連的 (若 和 相連則 ，否則為 0) 。

?

注意：多數圖的邊連接并不稠密，因此它們的鄰接矩陣是稀疏的，這個會讓計算變得困難。

雖然這些表示看上去很熟悉，但可別被騙了！

圖與機器學習中使用的典型對象大不相同，因為它們的拓撲結構比序列 (如文本或音頻) 或有序網格 (如圖像和視頻) 復雜得多：即使它們可以被表示成鏈表或者矩陣，但它們并不能被當作有序對象來處理。

這究竟意味著什么呢？如果你有一個句子，你交換了這個句子的詞序，你就創造了一個新句子。如果你有一張圖像，然后你重排了這個圖像的列，你就創造了一張新圖像。

左圖是 Hugging Face 的標志。右圖是一個重排后的 Hugging Face 標志，已經是一張不同的新圖像了。

但圖并不會如此。如果你重排了圖的邊列表或者鄰接矩陣的列，圖還是同一個圖 (一個更正式的叫法是置換不變性 (permutation invariance) ) 。

左圖，一個小型圖 (黃色是節點，橙色是邊) 。中圖，該圖的鄰接矩陣，行與列的節點按字母排序：可以看到第一行的節點 A，與 E 和 C 相連。右圖，重排后的鄰接矩陣 (列不再按字母序排了)，但這還是該圖的有效表示：A 節點仍然與 E 和 C 相連。

基于機器學習的圖表示

使用機器學習處理圖的一般流程是：首先為你感興趣的對象 (根據你的任務，可以是節點、邊或是全圖) 生成一個有意義的表示，然后使用它們訓練一個目標任務的預測器。與其他模態數據一樣，我們想要對這些對象的數學表示施加一些約束，使得相似的對象在數學上是相近的。然而，這種相似性在圖機器學習上很難嚴格定義，舉個例子，具有相同標簽的兩個節點和具有相同鄰居的兩個節點哪兩個更相似？

?

注意：在隨后的部分，我們將聚焦于如何生成節點的表示。一旦你有了節點層面的表示，就有可能獲得邊或圖層面的信息。你可以通過把邊所連接的兩個節點的表示串聯起來或者做一個點積來得到邊層面的信息。至于圖層面的信息，可以通過對圖上所有節點的表示串聯起來的張量做一個全局池化 (平均，求和等) 來獲得。當然，這么做會平滑掉或丟失掉整圖上的一些信息，使用迭代的分層池化可能更合理，或者增加一個連接到圖上所有其他節點的虛擬節點，然后使用它的表示作為整圖的表示。

神經網絡以前的方法

只使用手工設計特征

在神經網絡出現之前，圖以及圖中的感興趣項可以被表示成特征的組合，這些特征組合是針對特定任務的。盡管現在存在 更復雜的特征生成方法，這些特征仍然被用于數據增強和 半監督學習。這時，你主要的工作是根據目標任務，找到最佳的用于后續網絡訓練的特征。

節點層面特征 可以提供關于其重要性 (該節點對于圖有多重要？) 以及 / 或結構性 (節點周圍的圖的形狀如何？) 信息，兩者可以結合。

節點 中心性 (centrality) 度量圖中節點的重要性。它可以遞歸計算，即不斷對每個節點的鄰節點的中心性求和直到收斂，也可以通過計算節點間的最短距離來獲得，等等。節點的 度 (degree) 度量節點的直接鄰居的數量。聚類系數 (clustering coefficient) 度量一個節點的鄰節點之間相互連接的程度。

圖元度向量 (Graphlets degree vectors，GDV) 計算給定根節點的不同圖元的數目，這里圖元是指給定數目的連通節點可創建的所有迷你圖 (如：3 個連通節點可以生成一個有兩條邊的線，或者一個 3 條邊的三角形) 。

2 個節點到 5 個節點的圖元 (Pr?ulj, 2007)

邊層面特征帶來了關于節點間連通性的更多細節信息，有效地補充了圖的表示，有：兩節點間的 最短距離 (shortest distance)，它們的公共鄰居 (common neighbours)，以及它們的 卡茲指數 (Katz index) (表示兩節點間從所有長度小于某個值的路徑的數目，它可以由鄰接矩陣直接算得) 。

圖層面特征 包含了關于圖相似性和規格的高層信息。總 圖元數 盡管計算上很昂貴，但提供了關于子圖形狀的信息。核方法 通過不同的節點袋 (bag of nodes) (類似于詞袋 (bag of words) ) 方法度量圖之間的相似性。

基于游走的方法

基于游走的方法 使用在隨機游走時從節點j訪問節點i的可能性來定義相似矩陣；這些方法結合了局部和全局的信息。舉個例子，Node2Vec模擬圖中節點間的隨機游走，把這些游走路徑建模成跳字 (skip-gram) ，這與我們處理句子中的詞很相似，然后計算嵌入。基于隨機游走的方法也可被用于加速 Page Rank 方法，幫助計算每個節點的重要性得分 (舉個例子：如果重要性得分是基于每個節點與其他節點的連通度的話，我們可以用隨機游走訪問到每個節點的頻率來模擬這個連通度) 。

然而，這些方法也有限制：它們不能得到新的節點的嵌入向量，不能很好地捕獲節點間的結構相似性，也使用不了新加入的特征。

圖神經網絡

神經網絡可泛化至未見數據。我們在上文已經提到了一些圖表示的約束，那么一個好的神經網絡應該有哪些特性呢？

它應該：

滿足置換不變性：

等式：，這里 f 是神經網絡，P 是置換函數，G 是圖。

解釋：置換后的圖和原圖經過同樣的神經網絡后，其表示應該是相同的。

滿足置換等價性

公式：，同樣 f 是神經網絡，P 是置換函數，G 是圖。

解釋：先置換圖再傳給神經網絡和對神經網絡的輸出圖表示進行置換是等價的。

典型的神經網絡，如循環神經網絡 (RNN) 或卷積神經網絡 (CNN) 并不是置換不變的。因此，圖神經網絡 (Graph Neural Network, GNN) 作為新的架構被引入來解決這一問題 (最初是作為狀態機使用) 。

一個 GNN 由連續的層組成。一個 GNN 層通過 消息傳遞 (message passing) 過程把一個節點表示成其鄰節點及其自身表示的組合 (聚合 (aggregation)) ，然后通常我們還會使用一個激活函數去增加一些非線性。

與其他模型相比：CNN 可以看作一個鄰域 (即滑動窗口) 大小和順序固定的 GNN，也就是說 CNN 不是置換等價的。一個沒有位置嵌入 (positional embedding) 的 Transformer 模型可以被看作一個工作在全連接的輸入圖上的 GNN。

聚合與消息傳遞

多種方式可用于聚合鄰節點的消息，舉例來講，有求和，取平均等。一些值得關注的工作有：

圖卷積網絡 對目標節點的所有鄰節點的歸一化表示取平均來做聚合 (大多數 GNN 其實是 GCN) ；

圖注意力網絡 會學習如何根據鄰節點的重要性不同來加權聚合鄰節點 (與 transformer 模型想法相似) ；

GraphSAGE 先在不同的跳數上進行鄰節點采樣，然后基于采樣的子圖分多步用最大池化 (max pooling) 方法聚合信息；

圖同構網絡 先計算對鄰節點的表示求和，然后再送入一個 MLP 來計算最終的聚合信息。

選擇聚合方法：一些聚合技術 (尤其是均值池化和最大池化) 在遇到在鄰節點上僅有些微差別的相似節點的情況下可能會失敗 (舉個例子：采用均值池化，一個節點有 4 個鄰節點，分別表示為 1，1，-1，-1，取均值后變成 0；而另一個節點有 3 個鄰節點，分別表示為 - 1，0，1，取均值后也是 0。兩者就無法區分了。) 。

GNN 的形狀和過平滑問題

每加一個新層，節點表示中就會包含越來越多的節點信息。

一個節點，在第一層，只會聚合它的直接鄰節點的信息。到第二層，它們仍然只聚合直接鄰節點信息，但這次，他們的直接鄰節點的表示已經包含了它們各自的鄰節點信息 (從第一層獲得) 。經過 n 層后，所有節點的表示變成了它們距離為 n 的所有鄰節點的聚合。如果全圖的直徑小于 n 的話，就是聚合了全圖的信息！

如果你的網絡層數過多，就有每個節點都聚合了全圖所有節點信息的風險 (并且所有節點的表示都收斂至相同的值) ，這被稱為過平滑問題 (the oversmoothing problem)。

這可以通過如下方式來解決：

在設計 GNN 的層數時，要首先分析圖的直徑和形狀，層數不能過大，以確保每個節點不聚合全圖的信息

增加層的復雜性

增加非消息傳遞層來處理消息 (如簡單的 MLP 層)

增加跳躍連接 (skip-connections)

過平滑問題是圖機器學習的重要研究領域，因為它阻止了 GNN 的變大，而在其他模態數據上 Transformers 之類的模型已經證明了把模型變大是有很好的效果的。

圖 Transformers

沒有位置嵌入 (positional encoding) 層的 Transformer 模型是置換不變的，再加上 Transformer 模型已被證明擴展性很好，因此最近大家開始看如何改造 Transformer 使之適應圖數據 (綜述) 。多數方法聚焦于如何最佳表示圖，如找到最好的特征、最好的表示位置信息的方法以及如何改變注意力以適應這一新的數據。

這里我們收集了一些有意思的工作，截至本文寫作時為止，這些工作在現有的最難的測試基準之一 斯坦福開放圖測試基準 (Open Graph Benchmark, OGB) 上取得了最高水平或接近最高水平的結果：

Graph Transformer for Graph-to-Sequence Learning (Cai and Lam, 2020) 介紹了一個圖編碼器，它把節點表示為它本身的嵌入和位置嵌入的級聯，節點間關系表示為它們間的最短路徑，然后用一個關系增強的自注意力機制把兩者結合起來。

Rethinking Graph Transformers with Spectral Attention (Kreuzer et al, 2021) 介紹了譜注意力網絡 (Spectral Attention Networks, SANs) 。它把節點特征和學習到的位置編碼 (從拉普拉斯特征值和特征向量中計算得到) 結合起來，把這些作為注意力的鍵 (keys) 和查詢 (queries) ，然后把邊特征作為注意力的值 (values) 。

GRPE: Relative Positional Encoding for Graph Transformer (Park et al, 2021) 介紹了圖相對位置編碼 Transformer。它先在圖層面的位置編碼中結合節點信息，在邊層面的位置編碼中也結合節點信息，然后在注意力機制中進一步把兩者結合起來。

Global Self-Attention as a Replacement for Graph Convolution (Hussain et al, 2021) 介紹了邊增強 Transformer。該架構分別對節點和邊進行嵌入，并通過一個修改過的注意力機制聚合它們。

Do Transformers Really Perform Badly for Graph Representation (Ying et al, 2021) 介紹了微軟的 Graphormer, 該模型在面世時贏得了 OGB 第一名。這個架構使用節點特征作為注意力的查詢 / 鍵 / 值 (Q/K/V) ，然后在注意力機制中把這些表示與中心性，空間和邊編碼信息通過求和的方式結合起來。

最新的工作是 Pure Transformers are Powerful Graph Learners (Kim et al, 2022)，它引入了 TokenGT。這一方法把輸入圖表示為一個節點和邊嵌入的序列 (并用正交節點標識 (orthonormal node identifiers) 和可訓練的類型標識 (type identifiers) 增強它) ，而不使用位置嵌入，最后把這個序列輸入給 Tranformer 模型。超級簡單，但很聰明！

稍有不同的是，Recipe for a General, Powerful, Scalable Graph Transformer (Rampá?ek et al, 2022) 引入的不是某個模型，而是一個框架，稱為 GraphGPS。它允許把消息傳遞網絡和線性 (長程的) transformer 模型結合起來輕松地創建一個混合網絡。這個框架還包含了不少工具，用于計算位置編碼和結構編碼 (節點、圖、邊層面的) 、特征增強、隨機游走等等。

在圖數據上使用 transformer 模型還是一個非常初生的領域，但是它看上去很有前途，因為它可以減輕 GNN 的一些限制，如擴展到更大 / 更稠密的圖，抑或是增加模型尺寸而不必擔心過平滑問題。

不錯的處理圖數據的庫有 PyGeometric (用于圖機器學習) 以及 NetworkX (用于更通用的圖操作)。

如果你需要質量好的測試基準，你可以試試看：

OGB, 開放圖測試基準 (the Open Graph Benchmark) ：一個可用于不同的任務和數據規模的參考圖測試基準數據集。

Benchmarking GNNs: 用于測試圖機器學習網絡和他們的表現力的庫以及數據集。相關論文特地從統計角度研究了哪些數據集是相關的，它們可被用于評估圖的哪些特性，以及哪些圖不應該再被用作測試基準。

長程圖測試基準 (Long Range Graph Benchmark): 最新的 (2022 年 10 月份) 測試基準，主要關注長程的圖信息。

Taxonomy of Benchmarks in Graph Representation Learning: 發表于 2022 年 Learning on Graphs 會議，分析并對現有的測試基準數據集進行了排序。

如果想要更多的數據集，可以看看:

Paper with code 圖任務排行榜:公開數據集和測試基準的排行榜，請注意，不是所有本排行榜上的測試基準都仍然適宜。

TU 數據集: 公開可用的數據集的合輯，現在以類別和特征排序。大多數數據集可以用 PyG 加載，而且其中一些已經被集成進 PyG 的 Datsets。

審核編輯：劉清