連結預測（Link Prediction）是什麼？

一種圖學習任務，目標是預測圖中兩個節點之間是否存在或將存在邊的連結。

核心概念

連結預測透過學習節點的低維表示，然後基於節點對的表示相似度預測邊的存在。核心假設是相似的節點表示更容易之間有邊。這個假設在大多數真實圖上成立，因為相同類型或相近的實體傾向相連。

連結預測與節點分類的重要區別是，連結預測是邊級任務（預測邊），而節點分類是節點級任務。這使得連結預測對圖拓撲變化更敏感，更能反映模型對圖結構的學習。

運作原理

• 節點嵌入學習：使用 GNN（GCN、GAT 等）對圖進行前向傳播，得到每個節點的最終表示向量 z_u 和 z_v。

• 邊評分函數：定義邊評分函數，衡量節點對 (u, v) 間的邊概率。常用的評分函數包括：

• 內積：score(u, v) = z_u^T z_v

• 餘弦相似度：score(u, v) = (z_u · z_v) / (||z_u|| · ||z_v||)

• 多層感知器：score(u, v) = MLP([z_u; z_v])

• 距離：score(u, v) = -||z_u - z_v||_2

• 二元分類：將評分透過 sigmoid 函數轉換為 0-1 之間的概率，表示存在邊的機率。

• 訓練：在已知邊（正例）和不存在邊的節點對（負例）上計算二元交叉熵損失。負採樣策略（如隨機採樣、難負採樣）對訓練效果影響重大。

• 推理：在測試時，對所有未見過的節點對計算評分，排序後預測最高分的節點對存在邊。

實際應用

• 社交網路推薦：Facebook、LinkedIn 等使用連結預測推薦好友。根據現有好友關係和使用者特徵，預測兩個陌生人成為朋友的概率。

• 知識圖譜補全：知識圖譜中存在大量缺失關係。使用連結預測補全知識圖譜，如預測未知的人物關係、地點屬性等。Google 知識圖譜利用此技術。

• 推薦系統：在使用者-物品二部圖上進行連結預測，等同於預測使用者會購買或點擊哪些物品。Amazon、Netflix 等應用此技術。

• 蛋白質相互作用預測：在蛋白質互作網路中預測兩個蛋白質是否相互作用。這對藥物發現和生物學研究至關重要。

• 交通流量預測：在交通網路上預測未來道路間的連接強度（流量），用於交通規劃和智慧出行。

• 詐欺檢測：在金融交易網路上，預測異常交易對（可能為欺詐）。

常見誤區

• 誤區一：連結預測只需比較節點表示的相似度。即使節點表示學得很好，邊評分函數的設計也很重要。簡單的內積可能不足以捕捉複雜的關係。多層感知器等更複雜的評分函數通常更有效。

• 誤區二：負採樣越多越好。適量的負採樣有助於訓練，但過多負採樣會導致類別不均衡，損害模型性能。常見做法是負採樣數與正例相等或稍多（1:1 到 1:10）。

• 誤區三：連結預測精度在大型圖上總是很高。在大規模、稀疏、特徵豐富的圖上，連結預測往往困難。可能需要特殊的採樣策略、負採樣技巧或模型改進。

• 誤區四：邊評分函數無關緊要。實驗表明，選擇不同的評分函數（如內積 vs. MLP）會導致性能差異 5-10%。對應用應根據圖性質和邊的語義選擇適當的評分函數。

與相關技術的比較

• 節點分類：節點分類預測節點的離散標籤，連結預測預測邊的存在（二元分類）。節點分類利用節點特徵和結構，連結預測重點在於學習兩個節點間的相似度。

• 圖匹配：圖匹配尋找兩個圖之間的結構相似性。連結預測在單一圖內預測缺失邊。兩者都涉及圖結構，但問題定義和方法不同。

• 推薦系統：推薦系統通常是連結預測在二部圖上的應用。推薦系統額外考慮時間動態、隱含反饋等因素。

• 隨機遊走/Node2Vec：這些無監督方法學習節點嵌入而不依賴邊標籤，可用於連結預測。但無監督嵌入通常劣於有監督的 GNN 方法。