圖形機器學習簡介
圖形機器學習（GraphML）使得能夠分析以關係連結的項目所構成的資料結構，並在圖形、節點、邊緣與子圖層級上進行預測。此領域對於從藥物發現與分子毒性預測到社群網路社群偵測以及行程系統中的交通估算等各種應用皆至關重要。
基本圖形概念
圖形由 節點（或頂點）與 邊緣（或連結）組成。根據資料的性質，圖形可依多種特徵進行分類：
- 同質 vs. 異質：同質圖形僅包含單一類型的節點與邊緣。異質圖形則具有類型化的節點或邊緣（例如同時包含作者與論文的引用網路），其表示需要除拓撲之外的額外資訊。
- 有向 vs. 無向：有向圖形（例如追隨者網路）具有具體方向的邊緣，而無向圖形（例如分子）則為雙向關係。
- 表示方式：圖形通常以邊緣集合或 鄰接矩陣 來表示，鄰接矩陣是一個方陣，值為 1 表示兩個節點之間有連結。
關鍵在於，圖形不同於序列（文字/音訊）或格狀（影像），因為它們不是有序的物件。隨機排列邊緣列表或鄰接矩陣的欄位不會改變底層圖形，這種特性稱為排列不變性。
圖形學習任務
圖形上的機器學習可應用於四個主要的粒度層級：
- 圖形層級：包括圖形生成（例如用於藥物發現）、圖形演化預測（例如在物理領域）以及圖形層級的預測（例如預測分子毒性）。
- 節點層級：聚焦於節點屬性預測，例如 AlphaFold 利用節點屬性預測分子中原子的三維座標。
- 邊緣層級：涉及邊緣屬性預測（例如藥物副作用預測）或缺失邊緣預測（例如推薦系統）。
- 子圖層級：聚焦於社群網路的社群偵測，或在如 Google 地圖等系統中對子圖屬性進行預測以估計到達時間。
這些任務可在 傳導式 設定（在單一圖形上進行訓練與測試）或 歸納式 設定（使用不同的圖形作為訓練、驗證與測試）中執行。
圖形表示的演變
神經網路前的方法
在神經網路出現之前，圖形表示依賴於人工設計的特徵：
- 節點層級特徵：中心性（重要性）、度數（鄰居數量）與聚類係數（鄰居連結性）。
- 邊緣層級特徵：節點之間的最短距離、共同鄰居，以及 Katz 指數（在一定長度內的走訪次數）。
- 圖形層級特徵：整體圖形子結構計數以及透過「節點袋」方法衡量相似性的核方法。
基於走訪的方法，如 Node2Vec，使用隨機走訪定義相似度指標，並透過 skip-gram 模型計算嵌入。然而，這些方法無法為新節點產生嵌入，且無法捕捉細緻的結構相似性或利用額外的節點特徵。
圖形神經網路（GNN）
為了對未見資料進行泛化，GNN 被設計為 排列不變（輸出不受節點排序影響）與 排列等變（節點排列會導致其表示相應排列）。
GNN 層透過 訊息傳遞 與 聚合 來運作：節點的表示會透過聚合其鄰居以及自身在前一層的表示來更新。
值得注意的 GNN 架構包括：
- 圖形卷積網路（GCNs）：對鄰居的正規化表示取平均。
- 圖形注意力網路（GATs）：使用注意力機制根據重要性加權鄰居。
- GraphSAGE：在不同跳躍層級抽樣鄰居，並使用最大池化聚合資訊。
- 圖形同構網路（GINs）：對鄰居表示的總和套用 MLP。
過度平滑問題
隨著 GNN 增加層數，每個節點的表示會聚合更廣範圍的資訊。若層數超過圖形的直徑，節點表示可能會收斂至相同的值，這種現象稱為 過度平滑。可透過限制層深、提升層複雜度、加入非訊息傳遞層（如 MLP）或實作跳躍連接來緩解此問題。
圖形 Transformer
由於 Transformer 天生具備排列不變性且具可擴展性，正被改編用於圖形，以克服 GNN 如過度平滑與對密集圖形的擴展限制等問題。主要發展包括：
- Graphormer：在注意力機制中將節點特徵作為 query/key/value，並結合中心性、空間與邊緣編碼。
- TokenGT：將圖形表示為節點與邊緣嵌入的序列，並加入識別子，省去位置嵌入的需求。
- GraphGPS：一個結合訊息傳遞網路與線性長距離 Transformer 的框架，打造混合式網路。
- 光譜注意力網路（SANs）：將節點特徵與從拉普拉斯特徵向量/特徵值衍生的學習位置編碼結合。
其他值得注意的方法包括用於圖形到序列學習的 Graph Encoder 與 GRPE（圖形相對位置編碼）Transformer。