近年來基于圖的機器學習有了很大的發(fā)展?；趫D的方法在數(shù)據(jù)科學中的許多常見問題中都有應用，例如鏈接預測、社群發(fā)現(xiàn)、節(jié)點分類等。根據(jù)如何組織問題和所擁有的數(shù)據(jù)，有許多解決問題的方法。本文將提供一個基于圖的嵌入算法的高層次的概述。最后還將介紹如何用Python庫(如node2vec)來在圖上生成各種嵌入。

基于圖的機器學習

人工智能有各種分支，從推薦系統(tǒng)、時間序列、自然語言處理、計算機視覺、圖機器學習等。有多種方法可以通過基于圖的機器學習來解決常見問題。包括社群發(fā)現(xiàn)、鏈接預測、節(jié)點分類等。

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

機器學習模型的目標是訓練機器在數(shù)據(jù)集中大規(guī)模學習和模式識別。在處理圖時這一點會被放大，因為圖提供不同而復雜的結構，這是其他形式的數(shù)據(jù)(如文本、音頻或圖像)所不具備的?；趫D的機器學習可以檢測并解釋重復出現(xiàn)的潛在模式[2]。

我們可能對確定與社交網絡上的用戶相關的人口統(tǒng)計信息感興趣。人口統(tǒng)計數(shù)據(jù)包括年齡、性別、種族等。像Facebook或Twitter這樣的公司的社交媒體網絡范圍從數(shù)百萬-數(shù)十億的用戶和數(shù)萬億的邊?？隙〞袔讉€與該網絡中用戶的人口統(tǒng)計信息相關的模式，這些模式不容易通過人類或算法檢測到，但模型應該能夠學習它們。類似地，我們可能想推薦一對用戶成為朋友，而他們目前還不是朋友。這就為鏈接預測(基于圖的機器學習的另一個應用)提供了素材。

什么是圖嵌入？

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

有多種方法可以從圖中生成表示結構信息的特征。最常見和最直接的方法是從圖中提取統(tǒng)計數(shù)據(jù)。這可以包括識別度分布、page rank、centrality metrics、jaccard 分數(shù)等。然后通過內核函數(shù)將所需屬性合并到模型中，但是核函數(shù)的問題是生成結果的相關時間復雜度很高。

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

圖嵌入的類型

對圖的分析可以分解為 3 個粒度級別。節(jié)點級別、邊緣級別和圖級別（整個圖）。每個級別由生成嵌入向量的不同過程組成，所選過程應取決于正在處理的問題和數(shù)據(jù)。下面介紹的每個粒度級別的嵌入都有附圖來直觀地彼此不同。

節(jié)點嵌入

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

邊嵌入

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

圖嵌入

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

Python實現(xiàn)

使用python代碼實現(xiàn)我們需要以下的這些庫

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包，也類似

節(jié)點嵌入

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 生成的節(jié)點嵌入可視，有許多計算節(jié)點嵌入的方法，如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）

總結

嵌入是一個將離散圖映射到向量表示的函數(shù)。從圖數(shù)據(jù)中可以生成多種形式的嵌入，節(jié)點嵌入、邊嵌入和圖嵌入。所有三種類型的嵌入都提供了一種向量表示，將圖的初始結構和特征映射到X維的數(shù)值。