圖嵌入概述：節點、邊和圖嵌入方法及Python實現

近年來基於圖的機器學習有了很大的發展。基於圖的方法在資料科學中的許多常見問題中都有應用，例如連結預測、社群發現、節點分類等。根據如何組織問題和所擁有的數據，有許多解決問題的方法。本文將提供一個基於圖的嵌入演算法的高層次的概述。最後也將介紹如何用Python庫(如node2vec)來在圖上產生各種嵌入。

#基於圖的機器學習

人工智慧有各種分支，從推薦系統、時間序列、自然語言處理、電腦視覺、圖機器學習等。有多種方法可以透過基於圖的機器學習來解決常見問題。包括社群發現、連結預測、節點分類等。

與圖機器學習的一個主要問題是找到一種表示（或編碼）圖結構的方法，以便機器學習模型可以輕鬆地利用它[1]。一般情況下機器學習中解決這個問題需要透過與模型相關聯的結構化表格資料來學習某種表示，這在以前是透過統計測量或核函數來進行的。近年來趨勢已經轉向對圖進行編碼以產生嵌入向量來訓練機器學習模型。

機器學習模型的目標是訓練機器在資料集中大規模學習和模式識別。在處理圖時這一點會被放大，因為圖提供不同而複雜的結構，這是其他形式的資料(如文字、音訊或圖像)所不具備的。基於圖的機器學習可以偵測並解釋重複出現的潛在模式[2]。

我們可能對確定與社交網路上的使用者相關的人口統計資訊感興趣。人口統計資料包括年齡、性別、種族等。像Facebook或Twitter這樣的公司的社交媒體網絡範圍從數百萬-數十億的用戶和數萬億的邊。肯定會有幾個與該網路中使用者的人口統計資訊相關的模式，這些模式不容易透過人類或演算法檢測到，但模型應該能夠學習它們。類似地，我們可能想推薦一對用戶成為朋友，而他們目前還不是朋友。這就為連結預測(基於圖的機器學習的另一個應用)提供了素材。

什麼是圖嵌入？

特徵工程是指處理輸入資料形成一組特徵的常用方法，這些特徵提供了原始資料集的緊湊且有意義的表示。特徵工程階段的結果將作為機器學習模型的輸入。這是在表格結構化資料集的處理時必備的過程，但在處理圖資料時卻是一種難以執行的方法，因為需要找到一種方法來產生與所有圖資料相關聯的合適表示。

有多種方法可以從圖中產生表示結構資訊的特徵。最常見且最直接的方法是從圖中提取統計資料。這可以包括識別度分佈、page rank、centrality metrics、jaccard 分數等。然後透過內核函數將所需屬性合併到模型中，但是核函數的問題是產生結果的相關時間複雜度很高。

最近的研究趨勢已經轉向尋找有意義的圖表示，對圖生成嵌入表示。這些嵌入學習了保持網路原始結構的圖表示。我們可以將其視為旨在將離散圖轉換為連續域的映射函數。一旦學習了函數，就可以將其應用於圖，並且生成的映射可以用作機器學習演算法的特徵集 。

圖嵌入的類型

對圖的分析可以分解為 3 個粒度等級。節點層級、邊緣層級和圖層級（整個圖）。每個層級由產生嵌入向量的不同流程組成，所選過程應取決於正在處理的問題和資料。下面介紹的每個粒度等級的嵌入都有附圖來直觀地彼此不同。

節點嵌入

在節點級別，產生與圖中的每個節點關聯的嵌入向量。這個嵌入向量可以容納圖的表示和結構。本質上說彼此接近的節點也應該有彼此接近的向量。這是流行的節點嵌入模型(如Node2Vec)的基本原則之一。

邊嵌入

在邊緣層中，產生一個與圖中的每條邊相關的嵌入向量。鏈路預測問題是使用邊嵌入的一個常見應用。連結預測是指預測一對節點之間是否有一條邊連接的可能性。這些嵌入可以學習圖提供的邊屬性。例如在一個社交網路圖中，可以有一個多邊圖，其中節點可以根據年齡範圍、性別等用邊連接。表示該邊的相關向量可以學習這些邊屬性。

圖嵌入

圖層級的嵌入並不常見，它們包括產生一個表示每個圖的嵌入向量。例如一個有多個子圖的大圖，每個對應的子圖都有一個表示圖結構的嵌入向量。分類問題是圖嵌入可能有用的常見應用。這些類型的問題將包括將圖表分類到特定類別。

Python實作

使用python程式碼實作我們需要以下的這些函式庫

Pythnotallow=3.9
 networkx>=2.5
 pandas>=1.2.4
 numpy>=1.20.1
 node2vec>=0.4.4
 karateclub>=1.3.3
 matplotlib>=3.3.4

如果您沒有安裝node2vec包，請參考它的文件。安裝karateclub包，也類似

節點嵌入

import random
 import networkx as nx
 import matplotlib.pyplot as plt
 
 from node2vec import Node2Vec
 from node2vec.edges import HadamardEmbedder
 from karateclub import Graph2Vec
 
 plt.style.use("seaborn")
 
 # generate barbell network
 G = nx.barbell_graph(
m1 = 13,
m2 = 7
 )
 
 # node embeddings
 def run_n2v(G, dimensions=64, walk_length=80, num_walks=10, p=1, q=1, window=10):
"""
Given a graph G, this method will run the Node2Vec algorithm trained with the
appropriate parameters passed in.
 
Args:
G (Graph) : The network you want to run node2vec on
 
Returns:
This method will return a model
 
Example:
G = np.barbell_graph(m1=5, m2=3)
mdl = run_n2v(G)
"""
 
mdl = Node2Vec(
G,
dimensions=dimensions,
walk_length=walk_length,
num_walks=num_walks,
p=p,
q=q
)
mdl = mdl.fit(window=window)
return mdl
 
 mdl = run_n2v(G)
 
 # visualize node embeddings
 x_coord = [mdl.wv.get_vector(str(x))[0] for x in G.nodes()]
 y_coord = [mdl.wv.get_vector(str(x))[1] for x in G.nodes()]
 
 plt.clf()
 plt.scatter(x_coord, y_coord)
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Node2Vec Algorithm on Barbell Network")
 plt.show()

#上圖是由barbell graph 產生的節點嵌入可視，有許多計算節點嵌入的方法，如node2vec、deep walk、random walks等。這裡使用node2vec。

邊嵌入

edges_embs = HadamardEmbedder(
keyed_vectors=mdl.wv
 )
 
 # visualize embeddings
 coordinates = [
edges_embs[(str(x[0]), str(x[1]))] for x in G.edges()
 ]
 
 plt.clf()
 plt.scatter(coordinates[0], coordinates[1])
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Edge Embeddings on Barbell Network")
 plt.show()

#透過barbell graph查看邊嵌入的視覺化，Hammard Embedder的原始碼可以在這裡找到（https ://github.com/eliorc/node2vec/blob/master/node2vec/edges.py#L91）。

圖嵌入

n_graphs = 10
 Graphs = [
nx.fast_gnp_random_graph(
n = random.randint(5,15),
p = random.uniform(0,1)
) for x in range(n_graphs)
 ]
 
 g_mdl = Graph2Vec(dimensions=2)
 g_mdl.fit(Graphs)
 g_emb = g_mdl.get_embedding()
 
 x_coord = [vec[0] for vec in g_emb]
 y_coord = [vec[1] for vec in g_emb]
 
 plt.clf()
 plt.scatter(x_coord, y_coord)
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Graph Embeddings on Randomly Generated Networks")
 plt.show()

#這是一個由隨機產生的圖的圖嵌入可視化，graph2vec演算法的源代碼可以在這裡找到。 （https://karateclub.readthedocs.io/en/latest/_modules/karateclub/graph_embedding/graph2vec.html）

總結

#嵌入是一個將離散圖對應到向量表示的函數。從圖資料中可以產生多種形式的嵌入，節點嵌入、邊嵌入和圖嵌入。所有三種類型的嵌入都提供了一種向量表示，將圖的初始結構和特徵映射到X維的數值。

以上是圖嵌入概述：節點、邊和圖嵌入方法及Python實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！