0. 前言

機器學習是人工智能的一個重要分支，它致力于讓系統能夠從數據中自主學習并持續優化。這項技術在諸多應用領域取得了顯著成果，特別是在那些難以通過明確定義規則來解決具體任務的場景中表現尤為突出。例如，我們可以訓練算法執行垃圾郵件識別、多語言文本翻譯和圖像目標識別等任務。
近年來，將機器學習應用于圖數據的研究日益受到關注。相較于傳統機器學習方法，圖機器學習的主要優勢在于能夠自動學習更優的數據表征、提升預測準確度、發現潛在模式，以及更深入地理解復雜動態關系。本節首先回顧機器學習基本概念。然后重點介紹圖機器學習 (Graph Machine Learning) 中的表示學習，最后通過實踐案例理解這些理論概念。

1. 圖機器學習

作為人工智能 (Artificial Intelligence, AI) 的重要分支，機器學習 (Machine Learning, ML) 近年來備受關注。這類計算機算法能夠通過經驗自主學習和提升能力，而無需顯式編程。這種方法的靈感來源于自然界的學習過程——就像運動員學習新動作時，會通過模仿教練、不斷試錯來逐步掌握技能。
機器學習的本質是一個優化問題。目標是尋找在特定任務上表現最優的數學模型。性能可以通過特定的性能指標(或損失函數)來衡量。在常見的學習任務中，算法利用大量數據迭代做出預測，在每次迭代中，根據損失函數進行評估，由此產生的誤差用來更新模型參數，逐步提升性能，這一過程通常稱為訓練。
更正式地講，考慮一個特定的任務 T 和一個性能指標 P，P 能夠量化算法在任務 T 上的表現。根據 Mitchell 的定義，當算法在任務 T 上的性能指標 P 隨著經驗 E 提升時，即稱為學習。

1.1 機器學習基本原理

機器學習算法主要分為三類：監督學習、無監督學習和半監督學習。這些學習范式取決于數據的提供方式和評估方法。
監督學習 (supervised learning) 是在我們知道問題答案的情況下使用的學習范式。在這種情況下，數據集由樣本對 $<x,y>$ 組成，其中 $x$ 是輸入(例如圖像或語音信號)，$y$ 是相應的期望輸出(例如，圖像類別或語音文本)。輸入變量也稱為特征，而輸出通常被稱為標簽、目標。在監督學習中，性能通常通過距離函數來評估。這個函數衡量預測和期望輸出之間的差異。根據標簽的類型，監督學習可以進一步分為以下幾類：

• 分類：標簽是離散的，表示輸入屬于哪個“類別”，如圖像識別、垃圾郵件檢測
• 回歸：目標是連續的，例如溫度預測、商品價格預測

無監督學習與監督學習的不同之處在于問題的答案是未知的。在這種情況下，沒有標簽，數據集只有輸入 $<x>$ ，核心目標是發現數據內在結構和模式，如聚類分析、高維數據降維。
在半監督學習中，算法使用有標簽和無標簽數據的組合進行訓練。通常，為了引導發現無標簽輸入數據中存在的結構，會使用少量的有標簽數據。
這里還需要特別介紹強化學習 (Reinforcement Learning)。這種學習方式通過"獎懲機制"來訓練模型做出一系列決策：人工智能算法會面臨游戲般的場景，根據采取的行動獲得懲罰或獎勵，其核心目標是通過學習找到最大化獎勵、最小化懲罰的最優策略。
在機器學習中，僅僅最小化訓練數據的誤差是遠遠不夠的。真正的關鍵在于"學習"能力——算法必須對未見過的數據保持同樣的性能水平。評估算法泛化能力的常規做法是將數據集劃分為兩部分：訓練集和測試集。模型在訓練集上訓練，計算損失函數并用于更新參數。訓練后，模型在測試集上進行評估。此外，數據充足時，測試集可以進一步分為驗證集和測試集，驗證集通常用于評估模型在訓練過程中的表現。
訓練機器學習算法時，可能會出現以下三種典型情況：

• 欠擬合 (Underfitting)：模型在訓練集上的表現較差，意味著模型沒有足夠的能力來處理任務。
• 過擬合 (Overfitting)：模型在訓練集上的表現很好，但在測試數據上表現欠佳，在這種情況下，模型僅僅記住了訓練數據，而沒有真正理解它們之間的關系
• 理想狀態：模型能夠在訓練和測試數據上都達到最優的性能水平。

過擬合和欠擬合可以通過下圖中的風險曲線理解，從圖中可以看到，隨著模型復雜性的變化(即擬合的參數數量)，訓練集和測試集上的性能變化情況：

過擬合問題是機器學習實踐中的主要挑戰之一，其產生原因主要包括：

• 數據層面：數據集定義不當或樣本代表性不足。在這種情況下，增加更多的數據有助于減輕問題
• 模型層面：模型復雜度超出任務需求。在這種情況下，可以在損失函數中添加正則化項以約束模型復雜度

機器學習已在許多領域取得顯著成果，成為計算機視覺、模式識別、自然語言處理等領域中最廣泛應用和有效的方法之一。

1.2 圖機器學習的獨特優勢

傳統機器學習算法包括：回歸算法(線性/邏輯回歸)、基于實例的算法( K 近鄰/支持向量機)、決策樹算法、貝葉斯算法(樸素貝葉斯)、聚類算法( K 均值)和人工神經網絡等。
本質上，這些算法成功的核心是，機器學習可以自動處理那些人類容易完成，但傳統計算機算法難以描述的任務，并且在某些情況下，它們已經展示了比人類更好的能力。這在處理圖數據時尤為突出，與圖像或音頻信號相比，圖結構更加復雜。通過使用圖機器學習，可以創建算法來自動檢測和解釋重復出現的潛在模式。
因此，圖結構數據的表示學習已引發廣泛關注，典型應用包括：生物交互圖中蛋白質功能判定、合作網絡演化預測和社交網絡用戶產品推薦等。
由于圖結構的特性，圖可以在不同的粒度級別上進行分析：節點級、邊級和圖級(整個圖)，如下所示。每個層級對應不同的問題類型，需采用特定算法解決：

以下是不同粒度層面的圖機器學習問題示例及解決方案：

• 節點級別：給定圖 $G=(V,E)$，將每個頂點 $v\in V$ 分類到正確的類別。在這種設置下，數據集包括圖 $G$ 和節點-標簽對 $<v_i,y_i>$ 集合，其中 $v_i$ 是圖 $G$ 的一個節點，$y_i$ 是該節點所屬的類別。典型任務包括社交網絡用戶分類、蛋白質功能預測等
• 邊級別：給定圖 $G=(V,E)$，將每條邊 $e\in E$ 分類到正確的類別。在這種設置下，數據集包括圖 $G$ 和邊-標簽對 $<e_i,y_i>$ 集合，其中 $e_i$ 是圖 $G$ 的一條邊，$y_i$ 是該邊所屬的類別。典型任務為鏈接預測，即預測圖中兩個現有節點之間是否存在鏈接
• 圖級別：給定一個包含 $m$ 個不同圖的數據集，將每個圖分類到正確類別。在這種設置下，數據集包括圖-標簽對 $<G_i,y_i>$ 集合，其中 $G_i$ 是一個圖，$y_i$ 是該圖所屬的類別。典型應用包括分子屬性預測、社交網絡類型識別等

本節我們系統闡述了機器學習的基礎概念，并著重介紹了圖數據處理中常見的機器學習問題類型。基于這些理論基礎，接下來將深入探討圖機器學習中更為復雜的核心概念。

2. 廣義圖嵌入問題

在傳統機器學習應用中，處理輸入數據的常見方法是通過特征工程從一組特征中構建出一個緊湊且有意義的表示，為數據集中每個實例提供一個合適的表示。
經過特征工程處理后的數據集將作為機器學習算法的輸入。雖然這種方法在多數情況下表現良好，但在處理圖數據時可能并非最優解。由于圖數據具有明確的結構特性，要找到能夠整合所有有用信息的合適表示并非易事。
創建能夠表示圖結構信息的特征的最直接的方法是提取某些統計數據。例如，可以通過圖的度分布、效率來表示圖。更復雜的過程包括應用特定的核函數或設計專用特征以整合所需特性。然而，這些方法通常耗時且可能無法完整保留圖的關鍵信息。
過去十年間，研究者們提出了多種新方法來創建緊湊而有意義的圖表示。這些方法的核心理念是：通過學習算法將原始圖數據映射到一個新的空間，使得新空間中的幾何關系能夠反映原始圖的結構特性。我們通常稱這個過程為表示學習或網絡嵌入。
表示學習 (representation learning，也稱網絡嵌入)是指學習一個從離散圖到連續域的映射函數 $f:G\to R^d$ 的任務。函數 $f$ 能夠生成低維向量表示，同時保留圖 $G$ 的局部和全局特性。
學習得到映射函數 $f$ 后，可以將其應用于圖中，生成的映射結果可作為機器學習算法的特征集，這一過程的如下所示。

映射函數 $f$ 不僅可以用于學習整個圖的向量表示，還能專門針對節點和邊進行表示學習。正如前文所述，圖機器學習問題可以在不同粒度層級上進行分析，因此研究人員開發了不同的嵌入算法來學習特定的映射函數：

• 節點嵌入 (Node Embedding)：映射函數 $f:V\to R^d$，生成的向量空間能反映原始圖中節點的結構關系
• 邊嵌入 (Edge Embedding)：映射函數 $f:E\to R^d$，生成的向量空間能反映原始圖中邊的結構關系

這些映射函數構建的向量空間具有以下關鍵特性：

• 原始空間中相似的圖結構/節點/邊，在新空間中也保持相似性
• 相似結構的歐氏距離較小，不相似結構的歐氏距離較大

下面我們通過一個實際案例來直觀理解嵌入空間的特性，以及如何在新空間中體現相似性關系。以下代碼展示了 Node2Vec (將圖 G 中的每個節點映射為一個向量)算法的應用示例：

from node2vec import Node2VecG = nx.barbell_graph(m1=7, m2=4)
draw_graph(G, nx.spring_layout(G))node2vec = Node2Vec(G, dimensions=2)
model = node2vec.fit(window=10)
import matplotlib.pyplot as pltfig, ax = plt.subplots(figsize=(10,10))for x in G.nodes():v = model.wv.get_vector(str(x))ax.scatter(v[0],v[1], s=1000)ax.annotate(str(x), (v[0],v[1]), fontsize=12)

在前述代碼中，完成了以下操作：

1. 生成了一個杠鈴圖 (barbell graph)
2. 然后使用 Node2Vec 嵌入算法，將圖中的每個節點映射為一個二維向量
3. 最后，繪制生成的二維向量表示，每個向量表示原始圖中的一個節點，向量空間中的位置反映節點間的結構關系

結果如下所示：

從圖中可以看出，具有相似結構的節點在嵌入空間中彼此靠近，而與具有不相似結構的節點距離較遠。還可以觀察到 Node2Vec 在區分能有效區分組1和組3的節點。由于該算法使用每個節點的鄰域信息來生成表示，因此能清晰區分不同群組。
我們再以 Edge2Vec 算法為例，對同一個圖 G 的邊進行向量化表示：

from node2vec.edges import HadamardEmbedder
edges_embs = HadamardEmbedder(keyed_vectors=model.wv)
import matplotlib.pyplot as pltfig, ax = plt.subplots(figsize=(10,10))for x in G.edges():v = edges_embs[(str(x[0]), str(x[1]))]ax.scatter(v[0],v[1], s=1000)ax.annotate(str(x), (v[0],v[1]), fontsize=16)

在前述代碼中，完成了以下操作：

1. 生成了一個杠鈴圖 (barbell graph)
2. 將 HadamardEmbedder 嵌入算法應用于 Node2Vec 算法的結果 (keyed_vectors=model.wv)，將圖中的每條邊映射為二維向量
3. 最后，繪制由嵌入算法生成的二維向量，每個向量對應原始圖中的一條邊

結果如下所示：

在上圖中展示了邊嵌入算法的處理結果。從圖中可以看到，算法能準確識別結構相似的邊，屬于組 1、組 2 和組 3 的邊分別聚集在三個明確區域，特殊邊 (6,7) 和 (10,11) (分別屬于組 5 和組 4 )也形成了獨立的聚類群組。
接下來，展示圖向量 (Graph2Vec) 算法的應用，該算法可將整個圖結構映射為單個向量，使用 Graph2Vec 算法生成一組圖的嵌入表示：

import random
import matplotlib.pyplot as plt
from karateclub import Graph2Vecn_graphs = 20def generate_radom():n = random.randint(6, 20)k = random.randint(5, n)p = random.uniform(0, 1)return nx.watts_strogatz_graph(n,k,p), [n,k,p]Gs = [generate_radom() for x in range(n_graphs)]model = Graph2Vec(dimensions=2, wl_iterations=10)
model.fit([x[0] for x in Gs])
embeddings = model.get_embedding()fig, ax = plt.subplots(figsize=(10,10))for i,vec in enumerate(embeddings):ax.scatter(vec[0],vec[1], s=1000)ax.annotate(str(i), (vec[0],vec[1]), fontsize=40)

在前述代碼中，完成了以下操作：

1. 使用隨機參數生成 20 個 Watts-Strogatz 圖
2. 然后執行圖嵌入算法，生成每個圖的二維向量表示
3. 最后，將生成的向量繪制在二維空間中

結果如下所示：

從上圖可以看出，歐幾里得距離較大的圖具有不同的結構，如圖 12 和圖 8，前者是使用 nx.watts_strogatz_graph(20,20,0.2857) 參數生成的，后者是使用 nx.watts_strogatz_graph(13,6,0.8621) 參數生成的。相比之下，歐幾里得距離較小的圖它們具有相似的結構，如圖 15 和圖 4，圖 15 是使用 nx.watts_strogatz_graph(9,9,0.5091) 命令生成的，而圖4是使用 nx.watts_strogatz_graph(10,5,0.5659) 生成的。
研究人員已經提出了大量的嵌入方法，這些方法通常分為兩大類：轉導性 (Transductive) 和歸納性 (Inductive)，根據函數在添加新樣本時的更新過程進行分類。如果提供了新節點，轉導性方法會更新模型(例如重新訓練)以推斷節點的信息，而在歸納性方法中，模型應能夠推廣到訓練期間未觀察到的新節點、邊或圖。

3. 圖嵌入算法分類

為生成圖表示的緊湊空間，研究人員提出了多種方法。近年來，研究人員和機器學習實踐者趨向于采用統一術語來描述這類算法。
每個圖、節點或邊的嵌入方法都可以通過兩個基本組件來描述，分別是編碼器 (Encoder, ENC) 和解碼器 (Decoder, DEC)。編碼器將輸入映射到嵌入空間，而解碼器則從學習到的嵌入中解碼圖的結構信息，如下圖所示。

該框架基于一個直觀理念：若編碼后的嵌入能使解碼器還原全部必要信息，則說明該嵌入包含了原始圖的壓縮表示，可用于下游機器學習任務。
在基于圖的表示學習機器學習算法中，解碼器通常被設計為將節點嵌入對映射為一個實數值，該數值代表原始圖中節點之間的鄰近度(距離)。舉例來說，可以這樣實現解碼器：給定兩個節點的嵌入表示 $Z_i=ENC(V_i)$ 和 $Z_j=ENC(V_j)$，當且僅當輸入圖中存在連接這兩個節點 $Z_i$ 和 $Z_j$ 的邊時，$DEC(Z_i,Z_j)$ =1。實際應用中，我們可以采用更有效的鄰近度函數來度量節點間的相似性。
基于上圖所示框架，我們將現在把各種嵌入算法分為四大類。我們將嵌入算法劃分為四大類別，并通過偽代碼示例輔助理解。在偽代碼形式中，約定 G 代表 networkx 圖對象，graphs_list 表示圖列表，model 為嵌入算法實例：

• 淺層嵌入方法：這類方法只能學習并返回對已學數據的嵌入值。Node2Vec、Edge2Vec 和 Graph2Vec 就是淺層嵌入方法的例子。它們只能返回在擬合過程中學習到的數據的向量表示，無法為未見過的數據獲得嵌入向量。使用這類方法的典型方式如下：

  model.fit(graphs_list)
  embedding = model.get_embedding()[i]
  

  在代碼中，一個通用的淺層嵌入方法對圖列表進行訓練。模型訓練完成后，只能獲取屬于 graphs_list 的第 i 個圖的嵌入向量。
• 圖自編碼方法：這類方法不僅學習如何將輸入圖映射為向量，學習得到一個更一般的映射函數，能夠為未見過的實例生成嵌入向量。使用這類方法的典型方式如下：

  model.fit(graphs_list)
  embedding = model.get_embedding(G)
  

  模型在 graphs_list 上訓練。模型在輸入訓練集上訓練完成后，就可以用它生成一個新的、未見過的圖 G 的嵌入向量。
• 鄰域聚合方法：這類算法可用于提取圖級的嵌入，其中節點用某些屬性標記。此外，和圖自編碼方法一樣，這類算法能夠學習一個通用的映射函數 $f(G)$，也能為未見過的實例生成嵌入向量。這類算法的一個優點是，構建的嵌入空間同時考慮圖的內部結構和節點的節點外部屬性(如語義特征)。例如，使用此方法，我們可以構建一個嵌入空間，能夠同時識別具有相似結構但節點屬性不同的圖。
• 圖形正則化方法：這類方法與前述各類方法略有不同。其特點在于不需要以圖結構作為輸入數據，而是通過挖掘特征間的"交互關系"來實現正則化學習。具體而言，可通過計算特征相似度來構建關系圖，其核心假設是圖中相鄰節點應具有相同標簽。因此，損失函數的設計會強制標簽預測結果與圖結構保持一致，例如約束相鄰節點在 L2 范數距離下的嵌入向量保持相似。正因如此，編碼器僅需使用節點特征 $X$ 作為輸入。這類算法通過學習映射函數 $f(X)$，將特定特征集 ($X$) 轉化為嵌入向量。與圖自編碼和鄰域聚合方法類似，該算法也能將習得的函數應用于未見過的特征數據。

對于淺層嵌入方法和鄰域聚合方法類算法，均可定義無監督和有監督版本。圖自編碼類算法適用于無監督任務，而圖正則化類算法則用于半監督/監督場景。無監督算法僅利用輸入數據集本身的信息(如節點、邊或圖結構)進行嵌入學習；有監督算法則借助外部信息指導嵌入過程，這類信息通常以標簽形式存在(例如為每個圖結構 $G_i$ 分配類別標簽 $y_i$ 的配對數據 $<G_i,y_i>$）。
有監督學習過程比無監督更為復雜，因為模型需要尋找最優的向量表示以實現最佳的標簽分配。以圖像分類的卷積神經網絡為例：在訓練過程中，神經網絡通過適配多個卷積濾波器來將圖像歸類到正確類別，這些濾波器的目標是找到輸入數據的緊湊表示以最大化預測性能。同樣的原理適用于有監督圖嵌入算法，其目標是尋找最優的圖表示形式，從而在類別分配任務中實現最佳性能。
從數學角度而言，這些模型都通過特定的損失函數進行訓練。該函數可統一表述為兩個組成部分：

• 第一部分監督項：用于監督學習場景，最小化預測結果與真實標簽之間的差異
• 第二部分重構項：評估原始輸入圖與"編碼+解碼"后重構圖之間的相似度(即結構重構誤差)

其數學形式可定義為：
$$L=\alpha L_{sup}(y,\hat{y})+L_{rec}(G,\hat{G})$$
其中 $\alpha L_{sup}(y,\hat{y})$ 表示監督學習中的損失函數，通過優化模型使每個樣本的真實類別 $y$ 與預測類別 $\hat{y}$ 之間的誤差最小化。$L_{rec}(G,\hat{G})$ 則表征輸入圖 $G$ 與編碼解碼后重構圖 $\hat{G}$ 之間的結構誤差。在無監督場景中，由于缺乏目標變量，系數 $\alpha$ 取值為 0。
需要特別強調的是，這類算法在圖結構機器學習問題中扮演著雙重角色：既可作為被動預處理工具，將圖數據轉換為適合傳統機器學習算法或可視化任務的特征向量；也可作為主動學習組件，在模型訓練過程中直接尋找特定問題的緊湊且具有語義的解決方案。

小結

在本節中，我們回顧了機器學習的基礎概念，并探討了其在圖數據中的應用。我們系統梳理了圖機器學習的基本術語，重點闡釋了圖表示學習的內涵。通過建立圖嵌入學習算法的分類框架，厘清了各類技術方案的差異化特征。