圖機器學習入門

在這篇博文中，我們將介紹圖機器學習的基礎知識。

我們首先研究什麼是圖，它們為什麼被使用，以及如何最好地表示它們。然後，我們簡要介紹人們如何在圖上學習，從前神經網路方法（同時探索圖特徵）到通常所說的圖神經網路。最後，我們窺探一下圖 Transformer 的世界。

圖

什麼是圖？

從本質上講，圖是對透過關係連線的專案的描述。

圖的例子包括社交網路（Twitter、Mastodon、任何連線論文和作者的引文網路）、分子、知識圖譜（如 UML 圖、百科全書以及任何頁面之間有超連結的網站）、以句法樹表示的句子、任何 3D 網格等等！因此，說圖無處不在並非誇張。

圖（或網路）中的專案稱為其 *節點* (或頂點)，它們的連線稱為其 *邊* (或連結)。例如，在社交網路中，節點是使用者，邊是他們之間的連線；在分子中，節點是原子，邊是它們的分子鍵。

• 具有型別化節點或型別化邊的圖稱為 **異構圖** (heterogeneous) (例如：引文網路中的專案可以是論文或作者，因此具有型別化的節點；而 XML 圖中的關係是型別化的，因此具有型別化的邊)。它不能僅透過其拓撲結構來表示，還需要額外的資訊。本文側重於同構圖。
• 圖也可以是 **有向的** (directed) (比如關注者網路，A 關注 B 並不意味著 B 關注 A) 或 **無向的** (undirected) (比如分子，原子之間的關係是雙向的)。邊可以連線不同的節點或一個節點自身 (自環)，但並非所有節點都需要連線。

如果你想使用你的資料，你必須首先考慮其最佳的特徵描述 (同構/異構，有向/無向，等等)。

圖有什麼用？

讓我們來看一些可以在圖上執行的任務。

在 **圖級別**，主要任務是

• 圖生成，用於藥物發現以生成新的可能分子，
• 圖演化 (給定一個圖，預測其隨時間的演變)，用於物理學中預測系統的演變，
• 圖級別預測 (從圖進行的分類或迴歸任務)，例如預測分子的毒性。

在 **節點級別**，通常是節點屬性預測。例如，Alphafold 使用節點屬性預測來預測給定分子整體圖的原子三維座標，從而預測分子如何在三維空間中摺疊，這是一個困難的生物化學問題。

在 **邊級別**，可以是邊屬性預測或缺失邊預測。邊屬性預測有助於藥物副作用預測，即在給定一對藥物的情況下預測不良副作用。缺失邊預測用於推薦系統中，以預測圖中兩個節點是否相關。

也可以在 **子圖級別** 進行社群檢測或子圖屬性預測。社交網路使用社群檢測來確定人們是如何連線的。子圖屬性預測可以在行程規劃系統 (如 Google Maps) 中找到，用於預測預計到達時間。

處理這些任務可以有兩種方式。

當你想預測特定圖的演變時，你工作在 **直推式** (transductive) 設定中，其中所有操作 (訓練、驗證和測試) 都在同一個圖上完成。*如果這是你的設定，請小心！從單個圖建立訓練/評估/測試資料集並非易事。* 然而，很多工作是使用不同的圖 (獨立的訓練/評估/測試集) 完成的，這被稱為 **歸納式** (inductive) 設定。

我們如何表示圖？

表示一個圖以進行處理和操作的常見方法有

• 表示為其所有邊的集合 (可能輔以其所有節點的集合)
• 或者表示為其所有節點之間的鄰接矩陣。鄰接矩陣是一個方陣 (大小為節點數 * 節點數)，它指示哪些節點直接連線到其他節點 (如果 (n_i) 和 (n_j) 連線，則 (A_{ij} = 1)，否則為 0)。*注意：大多數圖都不是密集連線的，因此具有稀疏鄰接矩陣，這可能使計算更加困難。*

然而，儘管這些表示方法看起來很熟悉，但不要被迷惑！

圖與機器學習中使用的典型物件非常不同，因為它們的拓撲結構比單純的“序列”(如文字和音訊) 或“有序網格”(如影像和影片) 更復雜：即使它們可以表示為列表或矩陣，它們的表示也不應被視為有序物件！

但這是什麼意思呢？如果你有一個句子並打亂其單詞，你會創造一個新句子。如果你有一張圖片並重新排列其列，你會創造一張新圖片。

對於圖來說，情況並非如此：如果你打亂其邊列表或其鄰接矩陣的列，它仍然是同一個圖。(我們稍後會更正式地解釋這一點，請查詢置換不變性)。

透過機器學習進行圖表示

使用機器學習處理圖的通常過程是，首先為你的感興趣專案 (節點、邊或整個圖，取決於你的任務) 生成一個有意義的表示，然後用這些表示來訓練一個針對你目標任務的預測器。我們希望 (像在其他模態中一樣) 約束物件的數學表示，使相似的物件在數學上是接近的。然而，這種相似性在圖機器學習中很難嚴格定義：例如，兩個節點在具有相同標籤或相同鄰居時更相似？

注意：*在接下來的部分中，我們將專注於生成節點表示。一旦你有了節點級別的表示，就可以獲得邊或圖級別的資訊。對於邊級別的資訊，你可以連線節點對的表示或進行點積。對於圖級別的資訊，可以對所有節點級別表示的連線張量進行全域性池化 (平均、求和等)。但這會平滑並丟失圖上的資訊——遞迴的層次化池化可能更有意義，或者新增一個連線到圖中所有其他節點的虛擬節點，並使用其表示作為整個圖的表示。*

前神經網路方法

簡單使用工程特徵

在神經網路出現之前，圖及其感興趣的專案可以以任務特定的方式表示為特徵的組合。現在，這些特徵仍然用於資料增強和半監督學習，儘管存在更復雜的特徵生成方法；根據你的任務，找到如何最好地將它們提供給你的網路可能至關重要。

**節點級別** 特徵可以提供關於重要性 (這個節點對圖有多重要？) 和/或基於結構 (節點周圍的圖的形狀是什麼？) 的資訊，並且可以組合使用。

節點的 **中心性** (centrality) 衡量節點在圖中的重要性。它可以透過遞迴地對每個節點的鄰居的中心性求和直到收斂，或者例如透過節點之間的最短距離度量來計算。節點的 **度** (degree) 是它直接鄰居的數量。**聚類係數** (clustering coefficient) 衡量節點鄰居之間的連線程度。**小圖度向量** (Graphlets degree vectors) 計算以給定節點為根的不同小圖的數量，其中小圖是你可以用給定數量的連線節點建立的所有迷你圖 (用三個連線的節點，你可以有一條帶兩條邊的線，或者一個帶三條邊的三角形)。

**邊級別** 特徵用關於節點連線性的更詳細資訊來補充表示，包括兩個節點之間的 **最短距離**、它們的 **共同鄰居** 以及它們的 **Katz 指數** (這是兩個節點之間長度不超過某個值的可能遊走次數 - 它可以直接從鄰接矩陣計算)。

**圖級別特徵** 包含關於圖相似性和特殊性的高階資訊。總的 **小圖計數** (graphlet counts)，雖然計算成本高，但提供了關於子圖形狀的資訊。**核方法** (Kernel methods) 透過不同的“節點袋”方法 (類似於詞袋) 來衡量圖之間的相似性。

基於遊走的方法

**基於遊走的方法** 使用在隨機遊走中從節點 i 訪問節點 j 的機率來定義相似性度量；這些方法結合了局部和全域性資訊。**Node2Vec**，例如，模擬圖節點之間的隨機遊走，然後用 skip-gram 處理這些遊走，很像我們處理句子中的詞語，來計算嵌入。這些方法也可以用來加速**頁面排名方法**的計算，該方法為每個節點分配一個重要性分數 (例如，基於其與其他節點的連線性，評估為隨機遊走訪問的頻率)。

然而，這些方法有其侷限性：它們無法為新節點獲得嵌入，無法精細地捕捉節點之間的結構相似性，也無法使用附加特徵。

圖神經網路

神經網路可以泛化到未見過的資料。考慮到我們之前提到的表示約束，一個好的用於處理圖的神經網路應該是什麼樣的？

它應該

• 是置換不變的
  • 方程： $f(P(G))=f(G)$ 其中 f 是網路，P 是置換函式，G 是圖
  • 解釋：一個圖及其置換的表示在經過網路後應該是相同的
• 是置換等變的
  • 方程： $P(f(G))=f(P(G))$ 其中 f 是網路，P 是置換函式，G 是圖
  • 解釋：在將節點傳遞給網路之前對其進行置換，應等同於對其表示進行置換

典型的神經網路，如 RNN 或 CNN，不是置換不變的。因此，一種新的架構，即圖神經網路 (GNN)，被引入 (最初是作為一種基於狀態的機器)。

GNN 由連續的層組成。一個 GNN 層將一個節點表示為其鄰居和自身在前一層表示的組合 (**聚合**)，加上通常的啟用函式以增加非線性 (**訊息傳遞**)。

**與其他模型的比較**：一個 CNN 可以被看作是一個具有固定鄰居大小 (透過滑動視窗) 和順序 (它不是置換等變的) 的 GNN。一個沒有位置嵌入的 Transformer 可以被看作是一個在全連線輸入圖上的 GNN。

聚合與訊息傳遞

有很多方法可以聚合來自鄰居節點的訊息，例如求和、求平均。一些遵循這一思想的著名工作包括：

• 圖卷積網路 (Graph Convolutional Networks) 對節點的鄰居的歸一化表示進行平均 (大多數 GNN 實際上是 GCN)；
• 圖注意力網路 (Graph Attention Networks) 學習根據不同鄰居的重要性來加權它們 (類似於 transformer)；
• GraphSAGE 在聚合資訊之前，在不同的跳數上取樣鄰居，然後透過最大池化分多步聚合它們的資訊。
• 圖同構網路 (Graph Isomorphism Networks) 透過對鄰居節點表示的和應用一個 MLP 來聚合表示。

**選擇聚合方式**：某些聚合技術 (特別是均值/最大池化) 在為具有不同相似節點鄰域的節點建立精細區分的表示時可能會遇到失敗案例 (例如：透過均值池化，一個有 4 個節點的鄰域，表示為 1,1,-1,-1，平均為 0，與一個只有 3 個節點表示為 -1, 0, 1 的鄰域沒有區別)。

GNN 的形狀和過平滑問題

在每個新層中，節點表示包含越來越多的節點。

一個節點，透過第一層，是其直接鄰居的聚合。透過第二層，它仍然是其直接鄰居的聚合，但這次，它們的表示包括了它們自己的鄰居 (來自第一層)。經過 n 層後，所有節點的表示變成了它們距離 n 的所有鄰居的聚合，因此，如果圖的直徑小於 n，則變成了整個圖的聚合！

如果你的網路層數太多，就有可能每個節點都成為整個圖的聚合 (並且所有節點的表示都收斂到同一個值)。這被稱為 **過平滑問題** (oversmoothing problem)

這可以透過以下方式解決：

• 調整 GNN 的層數，使其足夠小，以避免將每個節點近似為整個網路 (透過首先分析圖的直徑和形狀)
• 增加層的複雜性
• 新增非訊息傳遞層來處理訊息 (例如簡單的 MLP)
• 新增跳躍連線 (skip-connections)。

過平滑問題是圖機器學習中的一個重要研究領域，因為它阻止了 GNN 像 Transformer 在其他模態中那樣進行擴充套件。

圖 Transformer

一個沒有位置編碼層的 Transformer 是置換不變的，而且 Transformer 以其良好的擴充套件性而聞名，因此最近人們開始研究將 Transformer 應用於圖 (綜述)。大多數方法都專注於透過尋找最佳特徵和表示位置資訊的最佳方式來表示圖，並改變注意力機制以適應這種新資料。

以下是一些有趣的方法，它們在撰寫本文時在最難的可用基準之一——斯坦福開放圖基準上取得了 SOTA 或接近 SOTA 的結果：

• 用於圖到序列學習的圖 Transformer (Cai 和 Lam, 2020) 引入了一個圖編碼器，它將節點表示為它們的嵌入和位置嵌入的拼接，節點關係表示為它們之間的最短路徑，並在關係增強的自注意力中將兩者結合起來。
• 用譜注意力重新思考圖 Transformer (Kreuzer 等人, 2021) 引入了譜注意力網路 (SANs)。這些網路將節點特徵與學習到的位置編碼 (從拉普拉斯特徵向量/值計算) 相結合，用作注意力中的鍵和查詢，注意力值則是邊特徵。
• GRPE：圖 Transformer 的相對位置編碼 (Park 等人, 2021) 引入了圖相對位置編碼 Transformer。它透過將圖級別的位置編碼與節點資訊相結合，將邊級別的位置編碼與節點資訊相結合，並在注意力中將兩者結合來表示圖。
• 全域性自注意力作為圖卷積的替代 (Hussain 等人, 2021) 引入了邊增強 Transformer。這種架構分別嵌入節點和邊，並在修改後的注意力中將它們聚合起來。
• Transformer 在圖表示上真的表現不佳嗎 (Ying 等人, 2021) 介紹了微軟的 **Graphormer**，它在釋出時在 OGB 上獲得了第一名。這種架構在注意力中使用節點特徵作為查詢/鍵/值，並在注意力機制中將它們的表示與中心性、空間和邊編碼的組合相加。

最新的方法是 純 Transformer 是強大的圖學習器 (Kim 等人, 2022)，它引入了 **TokenGT**。這種方法將輸入圖表示為節點和邊嵌入的序列 (增加了正交節點識別符號和可訓練型別識別符號)，沒有位置嵌入，並將此序列作為輸入提供給 Transformer。它非常簡單，但很巧妙！

有點不同的是，通用、強大、可擴充套件的圖 Transformer 的配方 (Rampášek 等人, 2022) 介紹的不是一個模型，而是一個框架，名為 **GraphGPS**。它允許將訊息傳遞網路與線性 (長程) transformer 相結合，以輕鬆建立混合網路。該框架還包含多種工具來計算位置和結構編碼 (節點、圖、邊級別)、特徵增強、隨機遊走等。

將 transformer 用於圖仍然是一個處於起步階段的領域，但它看起來很有前途，因為它可能緩解 GNN 的一些侷限性，例如擴充套件到更大/更密集的圖，或在不過平滑的情況下增加模型大小。

更多資源

如果你想深入研究，可以看看這些課程：

• 學術形式
  • 斯坦福的圖機器學習
  • 麥吉爾大學的圖表示學習
• 影片形式
  • 幾何深度學習課程
• 書籍
  • 《圖表示學習》，Hamilton
• 綜述
  • 圖神經網路學習指南
• 研究方向
  • 2023 年的圖機器學習 總結了 2023 年圖機器學習可能有趣的方向。

處理圖的好庫有 PyGeometric 或 深度相簿 (用於圖機器學習) 和 NetworkX (用於更通用的圖操作)。

如果你需要高質量的基準，可以檢視：

• OGB，開放圖基準：參考的圖基準資料集，適用於不同任務和資料規模。
• GNN 基準測試：用於對圖機器學習網路及其表達能力進行基準測試的庫和資料集。相關論文特別研究了哪些資料集從統計角度來看是相關的，它們允許評估哪些圖屬性，以及哪些資料集不應再用作基準。
• 長程圖基準：最近 (2022年11月) 的基準，著眼於長程圖資訊
• 圖表示學習中基準的分類法：發表在 2022 年圖學習會議上的論文，分析並分類了現有的基準資料集

更多資料集，請參閱：

• 帶程式碼論文的圖任務排行榜：公共資料集和基準的排行榜 - 小心，這個排行榜上的並非所有基準都仍然相關
• TU 資料集：公開可用資料集的彙編，現在按類別和特徵排序。這些資料集中的大多數也可以用 PyG 載入，並且其中一些已被移植到 Datasets
• SNAP 資料集：斯坦福大型網路資料集集合:
• MoleculeNet 資料集
• 關係資料集倉庫

外部圖片來源

縮圖中的表情符號來自 Openmoji (CC-BY-SA 4.0)，小圖 (Graphlets) 的圖來自 *使用小圖度分佈進行生物網路比較* (Pržulj, 2007)。