圖形嵌入技術能將圖形資料轉化為低維向量，方便機器學習模型處理。DeepWalk 作為一種根據隨機遊走的圖形嵌入演算法，借鑑了自然語言處理的詞嵌入技術。它透過在圖形上進行多次隨機遊走，收集頂點鄰域資訊，再利用 Skip-Gram 模型將遊走序列類別比成句子，頂點類別比成單詞，訓練出每個頂點的向量表示。這些向量有效捕捉了圖形結構的特性，能應用於節點分類別、鏈路預測等下游任務。相較於 DeepWalk，Node2Vec 引入引數控制遊走方向，更靈活地探索圖形結構。而圖神經網路則直接在圖形上進行運算，例如 GCN 利用圖卷積操作聚合鄰居資訊，學習更具表達力的節點表示。
圖形嵌入技術：DeepWalk演算法解析
在圖形機器學習領域，圖形嵌入（Graph Embedding）是一種重要的技術，能夠將複雜的圖形結構轉化為低維度的向量表示，從而便於後續的機器學習任務。DeepWalk是一種根據隨機遊走（Random Walk）的圖形嵌入演算法，它借鑑了自然語言處理中的詞嵌入（Word Embedding）技術，尤其是word2vec演算法。本文將詳細介紹DeepWalk演算法的原理、實作過程及其應用。
隨機遊走與鄰域資訊收集
在圖形結構中，隨機遊走是一種從某個頂點出發，根據鄰接頂點的機率隨機選擇下一步的路徑。透過多次隨機遊走，可以收集到頂點的鄰域資訊。DeepWalk正是利用了這一特性，透過隨機遊走來收集圖形中頂點的鄰域結構資訊。
import random
def random_walk(graph, start_vertex, walk_length):
walk = [start_vertex]
for _ in range(walk_length - 1):
current_vertex = walk[-1]
neighbors = graph[current_vertex]
next_vertex = random.choice(neighbors)
walk.append(next_vertex)
return walk
# #### 內容解密：
# 這段程式碼定義了一個簡單的隨機遊走函式，引數包括圖形結構、起始頂點和遊走長度。
# 函式首先初始化一個包含起始頂點的遊走路徑，然後根據當前頂點的鄰接頂點隨機選擇下一步。
# 遊走過程重複直到達到指定的遊走長度，最終傳回完整的遊走路徑。
graph = {
'A': ['B', 'D'],
'B': ['A', 'C', 'E'],
'C': ['B', 'F'],
'D': ['A', 'E', 'G'],
'E': ['B', 'D', 'F', 'H'],
'F': ['C', 'E', 'I'],
'G': ['D', 'H'],
'H': ['E', 'G', 'I'],
'I': ['F', 'H']
}
walk = random_walk(graph, 'A', 5)
print(walk)
# #### 內容解密：
# 在這個範例中，我們定義了一個簡單的圖形結構，並從頂點'A'開始進行長度為5的隨機遊走。
# 程式碼輸出隨機遊走的路徑，例如['A', 'B', 'C', 'F', 'I']。
DeepWalk演算法流程
DeepWalk演算法的核心步驟包括：
- 隨機遊走：對圖形中的每個頂點進行多次隨機遊走，生成多條遊走路徑。
- Skip-Gram模型：將遊走路徑視為句子，頂點視為單詞，使用Skip-Gram模型訓練頂點的向量表示。
- 神經網路訓練：使用一個簡單的神經網路來訓練頂點的嵌入向量，輸入層和輸出層的維度等於頂點數量，隱藏層的維度等於嵌入向量的維度。
import numpy as np
class DeepWalk:
def __init__(self, graph, walk_length, num_walks, dimensions):
self.graph = graph
self.walk_length = walk_length
self.num_walks = num_walks
self.dimensions = dimensions
self.walks = self.generate_walks()
self.embeddings = self.train_embeddings()
def generate_walks(self):
walks = []
for vertex in self.graph:
for _ in range(self.num_walks):
walk = random_walk(self.graph, vertex, self.walk_length)
walks.append(walk)
return walks
def train_embeddings(self):
# 簡化的訓練過程，實際上需要使用word2vec或類別似的函式庫
embeddings = np.random.rand(len(self.graph), self.dimensions)
# 這裡省略了實際的訓練過程
return embeddings
# #### 內容解密：
# DeepWalk類別封裝了圖形嵌入的整個流程，包括生成隨機遊走路徑和訓練嵌入向量。
# generate_walks方法為每個頂點生成多條隨機遊走路徑，train_embeddings方法則簡化了嵌入向量的訓練過程。
# 在實際應用中，通常會使用成熟的函式庫（如Gensim）來訓練word2vec模型。
Skip-Gram模型與神經網路
DeepWalk使用Skip-Gram模型來訓練頂點的向量表示。Skip-Gram模型的目標是根據輸入頂點預測其鄰近頂點。透過訓練神經網路，DeepWalk能夠學習到頂點的低維度向量表示，這些向量捕捉了頂點在圖形中的結構資訊。
graph LR
A[輸入層] --> B[隱藏層]
B --> C[輸出層]
D[隨機遊走路徑] --> A
C --> E[Skip-Gram向量]
# **圖表翻譯：**
# 這張圖展示了DeepWalk演算法中使用的神經網路結構。
# 輸入層接受頂點的one-hot編碼，隱藏層學習頂點的嵌入向量，輸出層預測鄰近頂點。
# 隨機遊走路徑用於生成訓練資料，Skip-Gram向量則是最終輸出的頂點嵌入表示。
應用與解釋
DeepWalk生成的頂點嵌入向量可以用於各種圖形機器學習任務，例如節點分類別、連結預測和社群檢測。這些向量捕捉了頂點在圖形中的結構資訊和鄰域關係，為後續的機器學習模型提供了有力的特徵表示。
from sklearn.cluster import KMeans
# 假設embeddings是DeepWalk生成的頂點嵌入向量
embeddings = np.random.rand(100, 64) # 示例資料
kmeans = KMeans(n_clusters=5)
clusters = kmeans.fit_predict(embeddings)
print(clusters)
# #### 內容解密：
# 這段程式碼使用KMeans聚類別演算法對DeepWalk生成的頂點嵌入向量進行聚類別。
# 聚類別結果可以用於社群檢測，將結構相似的頂點分組到同一類別中。
圖神經網路（Graph Neural Networks）與圖嵌入技術（Graph Embedding Techniques）
在機器學習領域，圖（Graph）是一種強大的資料結構，能夠描述複雜的關係和實體之間的互動。圖神經網路（GNNs）與圖嵌入技術（Graph Embedding Techniques）是近年來備受矚目的研究領域，它們為圖資料的處理和分析提供了新的思路和方法。
圖嵌入技術（Graph Embedding Techniques）
圖嵌入技術旨在將圖中的節點（Vertices）或邊（Edges）轉換為低維度的向量表示（Vector Representations），使得這些向量能夠保留原始圖結構中的重要資訊。這種技術在許多應用中都非常有用，例如節點分類別（Node Classification）、鏈路預測（Link Prediction）等。
DeepWalk
DeepWalk是一種根據隨機遊走（Random Walk）的圖嵌入技術。它透過在圖中進行隨機遊走來生成節點序列，然後使用Word2Vec等技術來學習節點的向量表示。DeepWalk的核心思想是：如果兩個節點具有相似的鄰居節點，那麼它們的向量表示應該相似。
Node2Vec
Node2Vec是DeepWalk的擴充套件，它引入了兩個可調引數（Return Parameter p 和 In-Out Parameter q）來控制隨機遊走的方向和範圍。這些引數允許使用者根據具體需求調整遊走策略，以更好地捕捉圖中的結構資訊。
- 當
p值較小時，更傾向於傳回上一步的節點，實作類別似於廣度優先搜尋（Breadth-First Search）的效果。 - 當
q值較小時，更傾向於探索更遠的節點，實作類別似於深度優先搜尋（Depth-First Search）的效果。
透過調整 p 和 q 的值，Node2Vec能夠在不同場景下提供更靈活的圖嵌入表示。
import networkx as nx
import node2vec
# 建立一個簡單的圖
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)])
# 設定Node2Vec引數
n2v = node2vec.Graph(G, is_directed=False, p=1, q=1)
# 進行隨機遊走並生成節點嵌入
n2v.preprocess_transition_probs()
walks = n2v.simulate_walks(num_walks=10, walk_length=10)
# 列印隨機遊走結果
for walk in walks:
print(walk)
內容解密：
在上述程式碼中，我們首先建立了一個簡單的無向圖 G。然後，我們使用Node2Vec來對圖進行處理，設定了傳回引數 p 和 in-out 引數 q 均為1，表示進行無偏隨機遊走。接著，我們進行了10次長度為10的隨機遊走，並列印出遊走結果。
圖神經網路（Graph Neural Networks, GNNs）
圖神經網路是傳統神經網路在圖資料上的擴充套件，它能夠直接在圖結構上進行學習。GNNs的核心思想是透過聚合鄰居節點的資訊來更新當前節點的表示，從而捕捉圖中的結構資訊。
圖卷積網路（Graph Convolutional Networks, GCNs）
圖卷積網路是一種特殊的GNN，它透過卷積操作來聚合鄰居節點的資訊。GCNs在許多圖相關任務中表現出了優異的效能，例如節點分類別和圖分類別等。
GCNs的基本公式如下：
[ H^{(l+1)} = \sigma \left( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)} \right) ]
其中，( H^{(l)} ) 是第 ( l ) 層的節點表示，( \tilde{A} ) 是圖的鄰接矩陣加上單位矩陣，( \tilde{D} ) 是 ( \tilde{A} ) 的度矩陣，( W^{(l)} ) 是第 ( l ) 層的權重矩陣，( \sigma ) 是啟用函式。
import torch
import torch.nn as nn
import torch_geometric.nn as pyg_nn
class GCN(nn.Module):
def __init__(self, input_dim, hidden_dim, output_dim):
super(GCN, self).__init__()
self.conv1 = pyg_nn.GCNConv(input_dim, hidden_dim)
self.conv2 = pyg_nn.GCNConv(hidden_dim, output_dim)
def forward(self, data):
x, edge_index = data.x, data.edge_index
x = self.conv1(x, edge_index)
x = torch.relu(x)
x = self.conv2(x, edge_index)
return x
# 假設我們有一個圖資料物件 `data`
model = GCN(input_dim=10, hidden_dim=16, output_dim=7)
output = model(data)
print(output)
內容解密：
在上述程式碼中，我們定義了一個簡單的GCN模型，包含兩個圖卷積層。輸入資料 data 包含了節點特徵 x 和邊索引 edge_index。我們首先透過第一個卷積層，將節點特徵維度從 input_dim 轉換為 hidden_dim，然後應用ReLU啟用函式。接著，透過第二個卷積層，將維度進一步轉換為 output_dim，最終輸出節點的表示。
圖表翻譯：
此圖示展示了Node2Vec中隨機遊走的過程，透過調整引數 p 和 q 來控制遊走的方向和範圍。
graph LR
A[起始節點] -->|p=1, q=1|> B[鄰居節點1]
A --> C[鄰居節點2]
A --> D[鄰居節點3]
C -->|p<1|> A[傳回上一節點]
C -->|q<1|> E[更遠的節點1]
C --> F[更遠的節點2]
C --> G[更遠的節點3]
圖表翻譯：
此圖表展示了Node2Vec的隨機遊走過程。當 p 值較小時，更傾向於傳回上一步的節點；當 q 值較小時，更傾向於探索更遠的節點。透過調整這兩個引數，可以靈活地控制遊走策略，以更好地捕捉圖中的結構資訊。
