0. 鏈接預測

鏈接預測 (link prediction)，也稱為圖補全，是處理圖時常見的問題。具體而言，給定一個部分觀測的圖(即某些節點對之間是否存在邊無法確定)，我們的目標是預測未知狀態節點對之間是否存在邊，如下圖所示。

設圖 $G=(V,E)$ 的節點集為 $V$，邊集為 $E=E_o\cup E_u$。其中，邊集 $E_o$ 表示已知邊(觀測到的鏈接)，而邊集 $E_u$ 表示未知邊(待預測的鏈接)。鏈接預測的目標是利用 $V$ 和 $E_o$ 的信息來估計 $E_u$。該問題在時序圖數據中同樣常見。在此設定下，假設 $G_t$ 是在時間點 $t$ 觀測到的圖，我們的目標是預測該圖在時間點 $t+1$ 的邊。
鏈接預測問題在各領域均有廣泛應用：在社交網絡中用于推薦好友關系，在電子商務平臺中用于推薦商品；在生物信息學中則用于分析蛋白質相互作用。接下來，我們將介紹解決鏈接預測問題的兩類方法——即基于相似性的方法和基于嵌入的方法。

1. 基于相似性的方法

本節介紹若干解決標簽預測問題的簡單算法，其核心思想是通過計算圖中節點對的相似度函數來預測連接概率：若節點相似度高，則它們有較高的概率通過一條邊連接。這些算法可分為兩類：基于索引的方法和基于社區的方法。前者通過簡單計算節點鄰居關系指標得出結果，后者則使用關于節點所屬社區的信息進行計算。接下來，以 networkx 庫(具體模塊為 networkx.algorithms.link_prediction )的標準實現為例進行演示。

1.1 基于指標的方法

本節介紹 networkx 中計算未連接節點間邊概率的算法，這些算法均通過分析兩節點鄰居關系來構建簡單指標。

資源分配指數 (resource allocation index)
該方法通過以下公式計算所有節點對的資源分配指數，進而估計節點 $v$ 與 $u$ 之間存在連接的概率：：
$$r(u,v)=\sum _{w\in N(u)\cap N(v)}\frac{1}{|N(w)|}$$
在以上公式中，函數 $N(v)$ 用于計算節點 $v$ 的鄰居集合，$w$ 代表同時是 $u$ 和 $v$ 鄰居的節點。我們可以使用 networkx 計算該指數：

import networkx as nx
edges = [[1,3],[2,3],[2,4],[4,5],[5,6],[5,7]]
G = nx.from_edgelist(edges)
preds = nx.resource_allocation_index(G,[(1,2),(2,5),(3,4)])

resource_allocation_index 函數的第一個參數是輸入圖，第二個參數是待計算的潛在邊列表。代碼運行結果如下所示：

[(1, 2, 0.5), (2, 5, 0.5), (3, 4, 0.5)]

輸出結果是一個包含 (1,2)、(2,5)、(3,4) 等節點對的列表及其對應的資源分配指數值。根據輸出可知，這些節點對之間存在連接邊的概率均為 0.5。

Jaccard 系數
該算法基于 Jaccard 系數計算節點 $u$ 和 $v$ 之間的連接概率：
$$J(u,v)=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|}$$
其中 $N(v)$ 表示節點 $v$ 的鄰居集合。在 networkx 中可通過以下代碼實現：

import networkx as nx
edges = [[1,3],[2,3],[2,4],[4,5],[5,6],[5,7]]
G = nx.from_edgelist(edges)
preds = nx.resource_allocation_index(G,[(1,2),(2,5),(3,4)])

代碼運行結果如下所示：

[(1, 2, 0.5), (2, 5, 0.25), (3, 4, 0.3333333333333333)]

根據輸出結果，節點 (1,2) 之間存在邊的概率為 0.5，節點 (2,5) 之間為 0.25，節點 (3,4) 之間為 0.333。
除此之外，networkx 庫還提供了許多其他基于相似度得分的節點連接概率計算方法，例如 nx.adamic_adar_index 和 nx.preferential_attachment，分別基于 Adamic/Adar 指數和偏好連接指數計算。這些函數的參數格式與前述方法一致，均需輸入圖結構和待計算的節點對列表。

1.2 基于社區的方法

與基于指標的方法類似，本類算法同樣通過計算指數來評估未連接節點的連接概率。二者的核心區別在于：基于社區的方法在生成指數前，需先計算節點所屬社區信息，同時基于社區的算法邏輯融合了社區拓撲特征。接下來，我們將介紹一些常見的基于社區的方法。

社區公共鄰居 (community common neighbor)
為了估算兩個節點連接的概率，該算法計算公共鄰居的數量，并將屬于同一社區的公共鄰居數量加到該值中。對于兩個節點 $u$ 和 $v$，社區公共鄰居值的計算方式如下：
$$c(u,v)=|N(u)\cup N(v)|+\sum _{w\in N(u)\cap N(v)}f(w)$$
其中，$N(v)$ 表示節點 $v$ 的鄰居集合，當節點 $w$ 與 $u$ 屬于同一社區時 $f(w)=1$，否則為 $0$。在 networkx 中通過以下代碼計算：

import networkx as nx
edges = [[1,3],[2,3],[2,4],[4,5],[5,6],[5,7]]
G = nx.from_edgelist(edges)
G.nodes[1]["community"] = 0
G.nodes[2]["community"] = 0
G.nodes[3]["community"] = 0
G.nodes[4]["community"] = 1
G.nodes[5]["community"] = 1
G.nodes[6]["community"] = 1
G.nodes[7]["community"] = 1
preds = nx.cn_soundarajan_hopcroft(G,[(1,2),(2,5),(3,4)])

從上述代碼中可以看到，我們需要為圖中的每個節點分配社區屬性 (community property)。該屬性用于在計算前文定義的 $f(v)$ 函數時，識別屬于同一社區的節點，社區屬性值也可以通過特定算法自動計算獲得。cn_soundarajan_hopcroft 函數接受輸入圖和我們希望計算得分的節點對。代碼執行結果如下所示：

[(1, 2, 2), (2, 5, 1), (3, 4, 1)]

與前述其它函數的主要區別在于指標值的范圍。可以看到，該函數的輸出值并不限定在 (0,1) 區間內。

社區資源分配 (community resource allocation)
與社區共同鄰居算法類似，社區資源分配算法將從節點鄰居處獲得的信息與節點所屬社區特征合并：
$$c(u,v)=\sum _{w\in N(u)\cap N(v)}\frac{f(w)}{|N(w)|}$$
其中，$N(v)$ 表示節點 $v$ 的鄰居集合，當節點 $w$ 與 $u$、$v$ 屬于同一社區時 $f(w)=1$，否則為 $0$。在 networkx 中的實現代碼如下：

import networkx as nx
edges = [[1,3],[2,3],[2,4],[4,5],[5,6],[5,7]]
G = nx.from_edgelist(edges)
G.nodes[1]["community"] = 0
G.nodes[2]["community"] = 0
G.nodes[3]["community"] = 0
G.nodes[4]["community"] = 1
G.nodes[5]["community"] = 1
G.nodes[6]["community"] = 1
G.nodes[7]["community"] = 1
preds = nx. ra_index_soundarajan_hopcroft(G,[(1,2),(2,5),(3,4)])

從以上代碼中可以看到，我們需要為圖中的每個節點分配社區屬性。該屬性在計算前文定義的函數時，用于識別屬于同一社區的節點，這些社區值也可以通過特定的算法自動計算獲得。ra_index_soundarajan_hopcroft 函數接受輸入圖和我們希望計算得分的節點對。代碼執行結果如下所示：

[(1, 2, 0.5), (2, 5, 0), (3, 4, 0)]

從輸出結果可以明顯看出社區屬性對指數計算的影響：同屬一個社區的節點 1 和 2 獲得了較高的指數值 0.5，相反，分屬不同社區的節點對 (2,5) 和 (3,4) 則得分為 0。
networkx 還提供了另外兩種結合社區信息的連接概率計算方法：nx.within_inter_cluster (基于集群內外連接分析)和 nx.common_neighbor_centrality (基于共同鄰居中心性)。
在下一節中，我們將介紹如何結合機器學習和邊嵌入 (edge embedding) 來預測未知邊。

2. 基于嵌入的方法

在本節中，我們將介紹一種更先進的鏈路預測方法。該方法的核心理念是將鏈路預測問題轉化為監督式分類任務。具體而言，對于給定圖數據，每對節點均通過特征向量 ($x$) 表示，并分配類別標簽 ($y$)。形式化定義為：設圖 $G=(V,E)$，對于任意節點對 $i,j$，構建如下公式：
$$\begin{gathered} x=[f_{0,0},...,f_{i,j},...,f_{n,n}] \\ y=[y_{0,0},...,y_{i,j},...,y_{n,n}] \end{gathered}$$
其中，$f_{i,j}\in x$ 表示節點對 $i,j$ 的特征向量，$y_{i,j}\in y$ 為其對應標簽。$y_{i,j}$ 的取值規則為：若圖 $G$ 中存在連接節點 $i,j$ 的邊，則 $y_{i,j}=1$；否則 $y_{i,j}=0$。通過特征向量和標簽數據，我們可以訓練機器學習算法來預測特定節點對是否可能構成圖中的合理邊。
雖然節點對的標簽向量構建相對簡單，但特征空間的構建則更具挑戰性。為生成每對節點的特征向量，我們將采用嵌入技術(如 node2vec 和 edge2vec)。這些嵌入算法能顯著簡化特征空間的生成過程。整個流程可概括為兩個核心步驟：

1. 使用 node2vec 算法計算圖 $G$ 中每個節點的嵌入向量
2. 對圖中所有可能的節點對，使用 edge2vec 算法計算其嵌入表示

隨后，我們可以將生成的嵌入特征向量輸入通用機器學習算法來解決分類問題。為便于理解，我們通過代碼示例演示完整流程(從圖構建到鏈路預測)，數據集采用論文引用網絡數據集 Cora。

(1) 首先，基于該數據集構建 networkx 圖結構：

import networkx as nx
import pandas as pd
from torch_geometric.utils import from_networkxedgelist = pd.read_csv("cora.cites", sep='\t', header=None, names=["target", "source"])
G = nx.from_pandas_edgelist(edgelist)
# 將圖轉換為PyG格式
pyg_data = from_networkx(G)
draw_graph(G, nx.spring_layout(G))

(2) 接下來，基于圖 G 創建訓練集和測試集。具體而言，數據集不僅需要包含圖 G 中真實邊的子集，還需包含不構成真實邊的節點對。真實邊對應的節點對將作為正樣本(類別標簽 1)，而非真實邊的節點對作為負樣本(類別標簽 0)：

from sklearn.model_selection import train_test_split
import numpy as npedges = list(G.edges())
non_edges = list(nx.non_edges(G))train_edges, test_edges = train_test_split(edges, test_size=0.1, random_state=42)
train_non_edges, test_non_edges = train_test_split(non_edges, test_size=0.1)# Rebuild train graph without test edges
graph_train = nx.Graph()
graph_train.add_nodes_from(G.nodes())
graph_train.add_edges_from(train_edges)

(3) 對于每個實例，需要生成它們的特征向量。在本節中，使用 node2vec 庫來生成節點嵌入：

from node2vec import Node2Vec
from node2vec.edges import HadamardEmbeddernode2vec = Node2Vec(graph_train)
model = node2vec.fit()
edges_embs = HadamardEmbedder(keyed_vectors=model.wv)# Create training data
samples_train = train_edges + train_non_edges
labels_train = [1]*len(train_edges) + [0]*len(train_non_edges)
train_embeddings = [edges_embs[str(x[0]), str(x[1])] for x in samples_train]# Create testing data
samples_test = test_edges + test_non_edges
labels_test = [1]*len(test_edges) + [0]*len(test_non_edges)
test_embeddings = [edges_embs[str(x[0]), str(x[1])] for x in samples_test]

(4) 使用 train_embeddings 特征空間和 train_labels 標簽分配，最終訓練機器學習算法來解決標簽預測問題：

from sklearn.ensemble import RandomForestClassifier
from sklearn import metrics# Train classifier
rf = RandomForestClassifier(n_estimators=200)
rf.fit(train_embeddings, labels_train)# Predict and evaluate
y_pred = rf.predict(test_embeddings)print('Precision:', metrics.precision_score(labels_test, y_pred))
print('Recall:', metrics.recall_score(labels_test, y_pred))
print('F1-Score:', metrics.f1_score(labels_test, y_pred))

在本節中，使用了一個簡單的 RandomForestClassifier 類，我們可以將訓練好的模型應用到 test_embeddings 特征空間中，以量化分類的質量：

print('Precision:', metrics.precision_score(labels_test, y_pred))
print('Recall:', metrics.recall_score(labels_test, y_pred))
print('F1-Score:', metrics.f1_score(labels_test, y_pred))

結果輸出如下：

Precision:：0.8557114228456913
Recall：0.8102466793168881
F1-Score：0.8323586744639375

上述方法只是一個通用的框架，流程中的每個部分——例如訓練/測試拆分、節點/邊嵌入和機器學習算法——都可以根據具體問題進行修改。該方法在處理時序圖的鏈接預測時尤為有效，此時在時間點 $t$ 獲取的邊信息可用于訓練模型，進而預測時間點 $t+1$ 可能出現的邊。
本節我們系統闡述了鏈接預測問題，通過多種示例詳細介紹了鏈接預測的不同解決方案，展示了從基于簡單指標的技術到基于嵌入的復雜技術的多元解決路徑。