圖形資料分析在現今技術領域應用廣泛，從社交網路到生物資訊，都需要有效的方法來理解圖形結構。特徵萃取是其中的關鍵步驟，它將複雜的圖形資訊轉換為機器學習模型可理解的數值特徵。本文介紹了 Graphlets 和圖形演算法等方法，並探討了圖嵌入技術的應用，如何將圖形結構表示為低維向量，以便於後續分析和預測。程式碼範例則展示瞭如何使用 Python 和 NetworkX 函式庫計算 Graphlets、中心性指標以及執行隨機遊走，有助於讀者理解並應用這些技術。
圖形特徵萃取：Graphlets 與圖形演算法的應用
在圖形資料分析中，特徵萃取是一項至關重要的任務。適當的特徵可以幫助我們理解節點之間的關係、預測未來的連線，並對複雜的圖形結構進行深入分析。本章將探討兩種主要的特徵萃取方法：Graphlets 和圖形演算法。
Graphlets：系統化的子圖形模式
Graphlets 是系統化定義的小型子圖形模式，用於描述節點周圍的區域性結構。這些模式包括所有可能的組態，直到最大節點數量。圖 10-3 列出了所有 72 種不超過五個節點的 Graphlets。值得注意的是，圖中顯示了兩種型別的識別碼：形狀 ID（G0、G1、G2 等）和 Graphlet ID（1、2、3 等）。
計算每個節點周圍的 Graphlet 模式出現次數，可以提供一個標準化的特徵向量，用於比較任何兩個節點在任何圖形中的相似性。這種通用的簽名方法使得我們能夠根據節點的鄰域結構對實體進行聚類別和分類別，應用於諸如預測國家的全球貿易動態或動態社交網路中的連結預測等領域。
Graphlets 的關鍵規則
Graphlets 是由特定節點集合在圖形中誘匯出的子圖。誘導意味著它們包含基礎圖形在選定節點集合中的所有邊。這條規則確保每個特定的節點集合最多匹配一個 Graphlet 模式。
例如，考慮圖 10-2 中的 Fiona、George、Howard 和 Ivy 四個人。他們匹配的形狀是 G7，因為這四個人形成了一個帶有交叉連線的矩形。他們不匹配形狀 G5（正方形），因為 George 和 Ivy 之間存在交叉連線。進一步觀察 G7 形狀的兩個 Graphlets：Graphlet 12 和 Graphlet 13。由於 George 和 Ivy 位於交叉連線的末端，因此 Graphlet 13 是他們的其中一個 Graphlet。
Graphlets 的優缺點
Graphlets 的優勢在於它們的全面性和系統性。檢查所有不超過五個節點的 Graphlets，等同於考慮源節點的四跳鄰域的所有細節。這種方法可以自動執行，無需花費時間和金錢設計自定義的特徵萃取。
然而，Graphlets 的缺點是它們可能需要大量的計算工作。在某些情況下，專注於更具領域依賴性的特徵可能更為高效。
import networkx as nx
def count_graphlets(G, node, max_size=5):
"""
計算指定節點周圍的 Graphlets。
引數：
G (nx.Graph)：輸入圖形
node：目標節點
max_size (int)：Graphlets 的最大節點數量
傳回：
dict：Graphlets 的計數結果
"""
graphlets_count = {}
for size in range(1, max_size + 1):
for subgraph in nx.enumerate_all_cliques(G.subgraph(nx.ego_graph(G, node, radius=size-1))):
if len(subgraph) == size:
subgraph_G = G.subgraph(subgraph)
# 計算 Graphlet ID
graphlet_id = get_graphlet_id(subgraph_G)
graphlets_count[graphlet_id] = graphlets_count.get(graphlet_id, 0) + 1
return graphlets_count
def get_graphlet_id(G):
"""
計算給定子圖形的 Graphlet ID。
引數：
G (nx.Graph)：子圖形
傳回：
int：Graphlet ID
"""
# 實作 Graphlet ID 的計算邏輯
# 這裡需要根據具體的 Graphlet 定義進行實作
pass
內容解密：
count_graphlets函式用於計算指定節點周圍的 Graphlets。它遍歷從 1 到max_size的所有可能的子圖形大小，並使用nx.enumerate_all_cliques函式列舉所有完全子圖。- 對於每個子圖形，函式計算其 Graphlet ID 並更新計數結果。
get_graphlet_id函式負責計算給定子圖形的 Graphlet ID。具體實作需要根據 Graphlet 的定義進行。
圖形演算法：另一種特徵萃取方法
除了 Graphlets 之外，圖形演算法也可以用於萃取領域無關的特徵。特別是中心性和排名演算法，它們系統地檢視節點周圍的所有資訊並產生分數。
中心性指標
中心性指標用於衡量節點在圖形中的重要性。常見的中心性指標包括 PageRank、接近中心性等。
import networkx as nx
def calculate_centrality(G):
"""
計算圖形中節點的中心性指標。
引數：
G (nx.Graph)：輸入圖形
傳回：
dict：節點的中心性指標
"""
# 計算 PageRank
pagerank = nx.pagerank(G)
# 計算接近中心性
closeness_centrality = nx.closeness_centrality(G)
return pagerank, closeness_centrality
# 建立範例圖形
G = nx.Graph()
G.add_edges_from([('Alex', 'Bob'), ('Alex', 'Charlie'), ('Bob', 'David'), ('Charlie', 'David')])
# 計算中心性指標
pagerank, closeness_centrality = calculate_centrality(G)
print("PageRank:", pagerank)
print("Closeness Centrality:", closeness_centrality)
內容解密：
calculate_centrality函式計算圖形中節點的 PageRank 和接近中心性。- 使用
nx.pagerank函式計算 PageRank，該指標衡量節點的重要性。 - 使用
nx.closeness_centrality函式計算接近中心性，該指標衡量節點到其他節點的平均距離。 - 函式傳回兩個字典，分別包含節點的 PageRank 和接近中心性。
圖形特徵提取在機器學習中的應用
在機器學習領域，圖形資料的特徵提取是一項至關重要的任務。圖形資料通常用於表示複雜的關係和結構，如社交網路、金融交易網路、生物網路等。有效的特徵提取可以幫助機器學習模型更好地理解和預測圖形資料中的模式和行為。
網域獨立特徵提取
網域獨立特徵提取是一種通用方法，不依賴於特定網域知識或圖形結構。這種方法的優點在於其通用性：可以預先設計和最佳化通用特徵提取工具，並立即應用於任何圖形資料。然而，其無導向的方法可能使其成為一種不夠精確的工具。
網域獨立特徵提取有兩個主要缺點。由於它不關注所考慮的邊緣和頂點型別，因此可能會將具有相同形狀但具有完全不同含義的例項分組在一起。第二個缺點是，它可能會浪費資源計算和記錄不重要或無邏輯意義的特徵。根據您的使用案例，您可能希望關注更具選擇性的網域相關特徵。
網域獨立特徵提取的缺點
- 缺乏針對性：無法區分不同型別頂點和邊緣，可能導致無關特徵被納入。
- 資源浪費：計算和儲存無關緊要的特徵，浪費計算資源。
網域相關特徵提取
結合網域知識可以使特徵提取更聰明、更高效。在提取網域相關特徵時，首先要關注圖形中的頂點型別和邊緣型別。檢檢視形架構的顯示有助於理解資料的分層結構，例如 City-(IN)-State-(IN)-Country 或 Day-(IN)-Month-(IN)-Year。這種結構在南韓COVID-19接觸者追蹤資料的圖形模型中得到了體現，如圖10-7所示。
graph LR
A[City] -->|IN|> B[State]
B -->|IN|> C[Country]
D[Day] -->|IN|> E[Month]
E -->|IN|> F[Year]
G[Patient] -->|INFECTED_BY|> H[Patient]
圖表翻譯： 此圖表展示了一個簡單的圖形結構，闡述了城市、國家和日期之間的關係。其中，城市隸屬於某個州，而州又隸屬於某個國家。同樣地，日期是某個月的某一天，而月份又是某年的某個月。
網域相關特徵提取的優勢
- 精確性：透過關注特定型別的頂點和邊緣，可以提取更具相關性的特徵。
- 效率：避免計算無關特徵，節省資源。
實際應用案例
在COVID-19接觸者追蹤圖中，重要的事實包括感染狀態（InfectionCase）、患者（Patient）、地點（City和TravelEvent）以及時間（Day）。連線這些實體的路徑非常重要。可能的特徵包括“Patient P在2020年3月的旅行次數”或“與Patient P在同一城市的感染者數量”。
def count_travel_events(patient_id, month, year):
# 假設有一個函式用於檢索患者的旅行事件
travel_events = retrieve_travel_events(patient_id, month, year)
return len(travel_events)
def count_infected_patients_in_same_city(patient_id, city, month, year):
# 假設有一個函式用於檢索同一城市的感染者
infected_patients = retrieve_infected_patients(city, month, year)
return len([p for p in infected_patients if p != patient_id])
內容解密：
count_travel_events函式計算特定患者在特定月份和年份的旅行次數。count_infected_patients_in_same_city函式統計與特定患者在同一城市的感染者數量。- 這些函式透過檢索相關資料函式庫或圖形資料來提供有用的特徵，供機器學習模型使用。
網域相關特徵在真實場景中的應用
在實際應用中，網域相關特徵被用於檢測金融詐欺，例如：
- 貸款申請人和已知詐欺者之間的最短路徑數量。
- 貸款申請人的郵寄地址、電子郵件地址或電話號碼被不同名稱的申請者使用的次數。
- 某張信用卡在過去10分鐘內進行的收費次數。
def count_shortest_paths(applicant_id, known_fraudster_id, max_path_length):
# 假設有一個函式用於計算兩個節點之間的最短路徑
paths = compute_shortest_paths(applicant_id, known_fraudster_id, max_path_length)
return len(paths)
def count_address_reuse(applicant_id, address_type):
# 假設有一個函式用於檢索地址重用的次數
reuse_count = retrieve_address_reuse_count(applicant_id, address_type)
return reuse_count
def count_recent_transactions(card_id, time_window):
# 假設有一個函式用於檢索最近的交易次數
transactions = retrieve_recent_transactions(card_id, time_window)
return len(transactions)
內容解密：
count_shortest_paths函式計算貸款申請人和已知詐欺者之間的最短路徑數量。count_address_reuse函式統計地址被重用的次數。count_recent_transactions函式統計信用卡在特定時間視窗內的交易次數。- 這些特徵對於檢測金融詐欺行為至關重要。
圖嵌入：開啟新視野
我們討論的最後一種特徵提取方法是圖嵌入（Graph Embedding），這是近年來研究和討論的熱門話題。有些專家可能會覺得，將圖嵌入歸類別為特徵提取的一種方式有些不尋常。難道圖嵌入不是一種降維方法嗎？難道它不是表示學習（Representation Learning）嗎？難道它本身不是一種機器學習方法嗎？所有這些都是正確的。讓我們首先定義什麼是圖嵌入。
圖嵌入的定義
嵌入（Embedding）是指在特定系統中表示拓撲物件（Topological Object），並保留（或近似保留）我們關心的屬性。最後一部分，即保留我們關心的屬性，是我們使用嵌入的核心原因。一個精心選擇的嵌入使我們能夠更方便地看到我們想要看到的東西。
以下是幾個例子，幫助說明嵌入的含義：
- 地球是一個球體，但我們將世界地圖印在平面紙上。地球在紙上的表示就是一種嵌入。有幾種不同的標準表示或嵌入方式，如圖10-8所示。
- 在2010年代末之前，當有人說「圖嵌入」時，他們可能指的是類別似於地球的例子。要表示圖中所有的連線而不讓邊緣相交，通常需要三個或更多維度。每當你在平面上看到一個圖時，它就是一種嵌入，如圖10-9所示。此外，除非你的資料指定了頂點的位置，否則即使是3D表示也是一種嵌入，因為它是一種關於頂點放置的特定選擇。從理論上講，實際上需要多達n-1個維度來表示具有n個頂點的圖。
- 在自然語言處理（NLP）中，詞嵌入（Word Embedding）是指給定單詞的一系列分數（即特徵向量），如圖10-10所示。單個分數沒有自然的解釋，但機器學習程式設定分數，使得在訓練檔案中傾向於出現在彼此附近的單詞具有相似的嵌入。例如，「機器」和「學習」可能具有相似的嵌入。詞嵌入對人類使用並不方便，但對於需要計算理解單詞相似性和分組的電腦程式非常方便。
圖嵌入的新意義
近年來，圖嵌入有了新的含義，類別似於詞嵌入。我們計算一個或多個特徵向量來近似圖的鄰域結構。事實上，當人們說「圖嵌入」時，他們通常指的是頂點嵌入（Vertex Embedding）：為圖中的每個頂點計算一個特徵向量。頂點的嵌入告訴我們它如何與其他頂點連線。然後，我們可以使用頂點嵌入的集合來近似圖，不再需要考慮邊緣。還有一些方法將整個圖總結為一個嵌入。這對於比較一個圖與另一個圖非常有用。在本文中，我們將重點關注頂點嵌入。
圖10-11顯示了一個圖（a）和其頂點嵌入的一部分（b）。每個頂點的嵌入（一系列32個數字）描述了其鄰域的結構，而沒有直接提及任何鄰居。
圖嵌入的分類別
讓我們回到圖嵌入的分類別問題。圖嵌入給我們提供了一組特徵向量。對於具有一百萬個頂點的圖，典型的嵌入向量將是幾百個元素長，遠遠少於一百萬維的上界。因此，圖嵌入代表了一種降維方法。如果我們使用圖嵌入來取得特徵向量，它們也是一種特徵提取方法。正如我們將看到的，生成嵌入的方法論符合機器學習的資格，因此它們也是表示學習。
import networkx as nx
import numpy as np
# 建立一個簡單的圖
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
# 使用networkx的spring_layout計算頂點的嵌入
pos = nx.spring_layout(G)
# 列印頂點的嵌入
for node, embedding in pos.items():
print(f"頂點 {node} 的嵌入：{embedding}")
內容解密：
上述程式碼展示瞭如何使用NetworkX函式庫建立一個簡單的圖，並使用spring_layout函式計算頂點的嵌入。spring_layout是一種根據力導向的佈局演算法，它根據頂點之間的連線關係計算頂點的位置。這個位置可以被視為頂點的一種嵌入表示。程式碼中，我們首先建立了一個具有5個頂點和5條邊的圖，然後計算並列印了每個頂點的嵌入。
隨機遊走嵌入
圖嵌入最著名的其中一種方法是使用隨機遊走（Random Walk）來取得每個頂點v周圍鄰域的統計樣本。隨機遊走是圖G中的一系列連線的跳躍。遊走從某個頂點v開始，然後隨機選擇v的鄰居並移動到那裡。它重複這個選擇隨機鄰居的過程，直到被告知停止。在無偏見的遊走中，選擇任何輸出邊緣的機率是相等的。
隨機遊走非常好，因為它們很容易執行，並且有效地收集了大量資訊。我們之前研究的所有特徵提取方法都需要遵循關於如何遍歷圖的嚴格規則；圖元（Graphlets）由於其非常精確的定義和彼此之間的區別而特別苛刻。隨機遊走則無拘無束，只需隨意進行。
對於圖10-12中的示例圖，假設我們從頂點A開始隨機遊走。有三分之一的機率會前往頂點B、C或D。如果從頂點E開始遊走，則有100%的機率下一步會前往頂點B。隨機遊走規則有多種變體，包括停留在原地、復原上一步、跳回起點或跳到隨機頂點的可能性。
import random
def random_walk(G, start_node, walk_length):
walk = [start_node]
for _ in range(walk_length - 1):
current_node = walk[-1]
neighbors = list(G.neighbors(current_node))
if neighbors:
next_node = random.choice(neighbors)
walk.append(next_node)
else:
break
return walk
# 在之前建立的圖G上進行隨機遊走
start_node = 1
walk_length = 3
walk = random_walk(G, start_node, walk_length)
print(f"從頂點 {start_node} 開始的隨機遊走：{walk}")
內容解密：
上述程式碼實作了一個簡單的隨機遊走演算法。random_walk函式接受一個圖G、一個起始頂點和遊走長度作為輸入，並傳回一個代表隨機遊走路徑的頂點序列。程式碼中，我們首先定義了random_walk函式，然後在之前建立的圖G上進行了隨機遊走，最後列印了遊走路徑。隨機遊走從指定的起始頂點開始，每一步都隨機選擇當前頂點的鄰居作為下一步，直到達到指定的遊走長度。
