圖機器學習(GML)&圖神經網絡(GNN)原理和代碼實作(前置學習系列二）

項目連結：https://aistudio.baidu.com/aistudio/projectdetail/4990947?contributionType=1

歡迎fork歡迎三連！文章篇幅有限，部分程式出圖不一一展示，詳情進入項目連結即可

圖機器學習(GML)&圖神經網絡(GNN)原理和代碼實作（PGL）[前置學習系列二]

上一個項目對圖相關基礎知識進行了詳細講述，下面進圖GML

networkx ：NetworkX 是一個 Python 包，用于建立、操作和研究複雜網絡的結構、動力學和功能

https://networkx.org/documentation/stable/reference/algorithms/index.html

import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt
from sklearn.metrics import accuracy_score
from sklearn.metrics import roc_curve
from sklearn.metrics import roc_auc_score

1. 圖機器學習GML

圖學習的主要任務

圖學習中包含三種主要的任務：

連結預測（Link prediction）
節點标記預測（Node labeling）
圖嵌入（Graph Embedding）

1.1連結預測（Link prediction）

在連結預測中，給定圖G，我們的目标是預測新邊。例如，當圖未被完全觀察時，或者當新客戶加入平台（例如，新的LinkedIn使用者）時，預測未來關系或缺失邊是很有用的。

詳細闡述一下就是：

GNN連結預測任務，即預測圖中兩個節點之間的邊是否存在。在Social Recommendation，Knowledge Graph Completion等應用中都需要進行連結預測。模型實作上是将連結預測任務看成一個二分類任務：

将圖中存在的邊作為正樣本；
負采樣一些圖中不存在的邊作為負樣本；
将正樣例和負樣例合并劃分為訓練集和測試集；
可以采用二分類模型的評估名額來評估模型的效果，

例如：AUC值在一些場景下例如大規模推薦系統或資訊檢索，模型需要評估top-k預測結果的準确性，是以對于連結預測任務還需要一些其他的評估名額來衡量模型最終效果：

MR（MeanRank）
MRR（Mean Reciprocal Rank）
Hit@n

MR, MRR, Hit@n名額含義：假設整個圖譜中共n個實體，評估前先進行如下操作：

（1）将一個正确的三元組（h,r,t）中的頭實體h或者尾實體t，依次替換成整個圖譜中的其他所有實體，這樣會産生n個三元組；

（2）對（1）中産生的n個三元組分别計算其能量值，例如在TransE中計算h+r-t的值，這樣n個三元組分别對應自己的能量值；

（3）對上述n個三元組按照能量值進行升序排序，記錄每個三元組排序後的序号；

（4）對所有正确的三元組都進行上述三步操作MR名額：将整個圖譜中每個正确三元組的能量值排序後的序号取平均得到的值；

MRR名額：将整個圖譜每個正确三元組的能量排序後的序号倒數取平均得到的值；
Hit@n名額：整個圖譜正确三元組的能量排序後序号小于n的三元組所占的比例。是以對于連結預測任務來說，MR名額越小，模型效果越好；
MRR和Hit@n名額越大，模型效果越好。接下來本文将在Cora引文資料集上，預測兩篇論文之間是否存在引用關系或被引用關系

新LinkedIn使用者的連結預測隻是給出它可能認識的人的建議。

在鍊路預測中，我們隻是嘗試在節點對之間建立相似性度量，并連結最相似的節點。現在的問題是識别和計算正确的相似性分數！

為了說明圖中不同鍊路的相似性差異，讓我們通過下面這個圖來解釋：

設$N(i)$是節點$i$的一組鄰居。在上圖中，節點$i$和$j$的鄰居可以表示為：

$i$的鄰居：

1.1.1 相似度分數

我們可以根據它們的鄰居為這兩個節點建立幾個相似度分數。

公共鄰居：$S(i,j) = \mid N(i) \cap N(j) \mid$，即公共鄰居的數量。在此示例中，分數将為2，因為它們僅共享2個公共鄰居。

Jaccard系數：$S(i,j) = \frac { \mid N(i) \cap N(j) \mid } { \mid N(i) \cup N(j) \mid }$,标準化的共同鄰居版本。

交集是共同的鄰居，并集是：

是以，Jaccard系數由粉紅色與黃色的比率計算出：

值是$\frac {1} {6}$。

Adamic-Adar指數：$S(i,j) = \sum_{k \in N(i)\cap N(j) } \frac {1} {\log \mid N(k) \mid}$。對于節點i和j的每個公共鄰居（common neighbor），我們将1除以該節點的鄰居總數。這個概念是，當預測兩個節點之間的連接配接時，與少量節點之間共享的元素相比，具有非常大的鄰域的公共元素不太重要。
優先依附(Preferential attachment)： $S(i,j) = \mid N(i) \mid * \mid N(j) \mid$
當社群資訊可用時，我們也可以在社群資訊中使用它們。

1.1.2 性能名額(Performance metrics)

我們如何進行連結預測的評估？我們必須隐藏節點對的子集，并根據上面定義的規則預測它們的連結。這相當于監督學習中的train/test的劃分。

然後，我們評估密集圖的正确預測的比例，或者使用稀疏圖的标準曲線下的面積(AUC)。

參考連結：模型評估名額AUC和ROC：https://cloud.tencent.com/developer/article/1508882

1.1.3 代碼實踐

這裡繼續用空手道俱樂部圖來舉例：

使用在前兩篇文中提及到的Karate圖，并使用python來進行實作

n=34
m = 78
G_karate = nx.karate_club_graph()

pos = nx.spring_layout(G_karate)
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)
# 我們首先把有關圖的資訊列印出來：
n = G_karate.number_of_nodes()
m = G_karate.number_of_edges()
print("Number of nodes : %d" % n)
print("Number of edges : %d" % m)
print("Number of connected components : %d" % nx.number_connected_components(G_karate))
plt.figure(figsize=(12,8))
nx.draw(G_karate, pos=pos)
plt.gca().collections[0].set_edgecolor("#000000")

# 現在，讓删除一些連接配接，例如25％的邊：
# Take a random sample of edges
edge_subset = random.sample(G_karate.edges(), int(0.25 * G_karate.number_of_edges()))

# remove some edges
G_karate_train = G_karate.copy()
G_karate_train.remove_edges_from(edge_subset)

# 繪制部分觀察到的圖，可以對比上圖發現，去掉了一些邊
plt.figure(figsize=(12,8))
nx.draw(G_karate_train, pos=pos)


# 可以列印我們删除的邊數和剩餘邊數：
edge_subset_size = len(list(edge_subset))
print("Deleted : ", str(edge_subset_size))
print("Remaining : ", str((m - edge_subset_size)))

# Jaccard Coefficient
# 可以先使用Jaccard系數進行預測：
pred_jaccard = list(nx.jaccard_coefficient(G_karate_train))
score_jaccard, label_jaccard = zip(*[(s, (u,v) in edge_subset) for (u,v,s) in pred_jaccard])
# 列印前10組結果
print(pred_jaccard[0:10])
# 預測結果如下，其中第一個是節點，第二個是節點，最後一個是Jaccard分數（用來表示兩個節點之間邊預測的機率）

# Compute the ROC AUC Score
# 其中，FPR是False Positive Rate， TPR是True Positive Rate
fpr_jaccard, tpr_jaccard, _ = roc_curve(label_jaccard, score_jaccard)
auc_jaccard = roc_auc_score(label_jaccard, score_jaccard)
print(auc_jaccard)

# Adamic-Adar
# 現在計算Adamic-Adar指數和對應的ROC-AUC分數
# Prediction using Adamic Adar 
pred_adamic = list(nx.adamic_adar_index(G_karate_train))
score_adamic, label_adamic = zip(*[(s, (u,v) in edge_subset) for (u,v,s) in pred_adamic])
print(pred_adamic[0:10])
# Compute the ROC AUC Score
fpr_adamic, tpr_adamic, _ = roc_curve(label_adamic, score_adamic)
auc_adamic = roc_auc_score(label_adamic, score_adamic)
print(auc_adamic)

# Compute the Preferential Attachment
# 同樣，可以計算Preferential Attachment得分和對應的ROC-AUC分數

pred_pref = list(nx.preferential_attachment(G_karate_train))
score_pref, label_pref = zip(*[(s, (u,v) in edge_subset) for (u,v,s) in pred_pref])
print(pred_pref[0:10])
fpr_pref, tpr_pref, _ = roc_curve(label_pref, score_pref)
auc_pref = roc_auc_score(label_pref, score_pref)
print(auc_pref)

plt.figure(figsize=(12, 8))
plt.plot(fpr_jaccard, tpr_jaccard, label='Jaccard Coefficient - AUC %.2f' % auc_jaccard, linewidth=4)
plt.plot(fpr_adamic, tpr_adamic, label='Adamic-Adar - AUC %.2f' % auc_adamic, linewidth=4)
plt.plot(fpr_pref, tpr_pref, label='Preferential Attachment - AUC %.2f' % auc_pref, linewidth=4)
plt.plot([0, 1], [0, 1], 'k--')
plt.xlim([0.0, 1.0])
plt.ylim([0.0, 1.0])
plt.xlabel('False positive rate')
plt.ylabel('True positive rate')
plt.title("ROC AUC Curve")
plt.legend(loc='lower right')
plt.show()

1.2 節點标記預測（Node labeling）

給定一個未标記某些節點的圖，我們希望對這些節點的标簽進行預測。這在某種意義上是一種半監督的學習問題。

處理這些問題的一種常見方法是假設圖上有一定的平滑度。平滑度假設指出通過資料上的高密度區域的路徑連接配接的點可能具有相似的标簽。這是标簽傳播算法背後的主要假設。

标簽傳播算法（Label Propagation Algorithm,LPA）是一種快速算法，僅使用網絡結構作為指導來發現圖中的社群，而無需任何預定義的目标函數或關于社群的先驗資訊。

單個标簽在密集連接配接的節點組中迅速占據主導地位，但是在穿過稀疏連接配接區域時會遇到問題。

半監督标簽傳播算法是如何工作？

首先，我們有一些資料：$x_1, ..., x_l, x_{l+1}, ..., x_n \in R^p$,，以及前$l$個點的标簽：$y_1, ..., y_l \in 1...C$.

我們定義初始标簽矩陣$Y \in R^{n \times C}$，如果$x_i$具有标簽$y_i=j$則$Y_{ij} = 1$，否則為0。

該算法将生成預測矩陣$F \in R^{n \times C}$，我們将在下面詳述。然後，我們通過查找最可能的标簽來預測節點的标簽：

$\hat{Y_i} = argmax_j F_{i,j}$

預測矩陣$F$是什麼？

預測矩陣是矩陣$F^{\star}$，其最小化平滑度和準确度。是以，我們的結果在平滑性和準确性之間進行權衡。

問題的描述非常複雜，是以我将不會詳細介紹。但是，解決方案是：

$F^{\star} = ( (1-\alpha)I + L_{sym})^{-1} Y$

其中：

參數$\alpha = \frac {1} {1+\mu}$
$Y$是給定的标簽
$L_{sym}$是圖的歸一化拉普拉斯矩陣（Laplacian matrix）

如果您想進一步了解這個主題，請關注圖函數的平滑度和流形正則化的概念。斯坦福有一套很好的标簽圖可以下載下傳：https://snap.stanford.edu/data/

Networkx直接實作标簽傳播：https://networkx.github.io/documentation/latest/reference/algorithms/generated/networkx.algorithms.community.label_propagation.label_propagation_communities.html

接下來我們用python來實作節點标簽的預測。

為了給我們使用到的标簽添加更多的特征，我們需要使用來自Facebook的真實資料。你可以再這裡下載下傳，然後放到facebook路徑下。

Facebook 資料已認證将每個使用者的 Facebook 内部 id 替換為新值來匿名化。此外，雖然已經提供了來自該資料集的特征向量，但對這些特征的解釋卻很模糊。例如，如果原始資料集可能包含特征“political=Democratic Party”，則新資料将僅包含“political=anonymized feature 1”。是以，使用匿名資料可以确定兩個使用者是否具有相同的政治派别，但不能确定他們各自的政治派别代表什麼。

我已經把資料集放在目錄裡了，就不需要下載下傳了

1.2.1 代碼實作标簽擴散

n = G_fb.number_of_nodes()
m = G_fb.number_of_edges()

print("Number of nodes: %d" % n)
print("Number of edges: %d" % m)
print("Number of connected components: %d" % nx.number_connected_components(G_fb))

# 我們把圖資料顯示出來：
mapping=dict(zip(G_fb.nodes(), range(n)))
nx.relabel_nodes(G_fb, mapping, copy=False)
pos = nx.spring_layout(G_fb)

plt.figure(figsize=(12,8))
nx.draw(G_fb, node_size=200, pos=pos)
plt.gca().collections[0].set_edgecolor("#000000")

with open('facebook/3980.featnames') as f:
    for i, l in enumerate(f):
        pass

n_feat = i+1

features = np.zeros((n, n_feat))
f = open('facebook/3980.feat', 'r')

for line in f:
    if line.split()[0] in mapping:
        node_id = mapping[line.split()[0]]
        features[node_id, :] = list(map(int, line.split()[1:]))

features = 2*features-1
feat_id = 6  #特征選擇id，自行設定
labels = features[:, feat_id]

plt.figure(figsize=(12,8))
nx.draw(G_fb, cmap = plt.get_cmap('bwr'), nodelist=range(n), node_color = labels, node_size=200, pos=pos)
plt.gca().collections[0].set_edgecolor("#000000")
plt.show()
# 這個所選擇的特征，在圖中相對平滑，是以擁有較好的學習傳播性能。
# 為了闡述節點标簽預測是如何進行的，我們首先要删掉一些節點的标簽，作為要預測的對象。這裡我們隻保留了30%的節點标簽：
random.seed(5)
proportion_nodes = 0.3
labeled_nodes = random.sample(G_fb.nodes(), int(proportion_nodes * G_fb.number_of_nodes()))

known_labels = np.zeros(n)
known_labels[labeled_nodes] = labels[labeled_nodes]

plt.figure(figsize=(12,8))
nx.draw(G_fb, cmap = plt.get_cmap('bwr'), nodelist=range(n), node_color = known_labels, node_size=200, pos=pos)
plt.gca().collections[0].set_edgecolor("#000000") # set node border color to black
plt.show()

1.3 圖嵌入（Graph Embedding）

嵌入的學習方式與 word2vec 的 skip-gram 嵌入的學習方式相同，使用的是 skip-gram 模型。問題是，我們如何為 Node2Vec 生成輸入語料庫？資料要複雜得多，即（非）定向、（非）權重、（a）循環……

為了生成語料庫，我們使用随機遊走采樣政策：

在處理NLP或計算機視覺問題時，我們習慣在深度神經網絡中對圖像或文本進行嵌入(embedding)。到目前為止，我們所看到的圖的一個局限性是沒有向量特征。但是，我們可以學習圖的嵌入！圖有不同幾個級别的嵌入：

對圖的元件進行嵌入（節點，邊，特征…）(Node2Vec) node2vec是一個用于圖表示學習的算法架構。給定任何圖，它可以學習節點的連續特征表示，然後可以用于各種下遊機器學習任務。

對圖的子圖或整個圖進行嵌入(Graph2Vec) Learning Distributed Representations of Graphs

學習圖的分布式表示

最近關于圖結構化資料的表示學習的工作主要集中在學習圖子結構（例如節點和子圖）的分布式表示。然而，許多圖分析任務（例如圖分類和聚類）需要将整個圖表示為固定長度的特征向量。雖然上述方法自然不具備學習這種表示的能力，但圖核心仍然是獲得它們的最有效方法。然而，這些圖核心使用手工制作的特征（例如，最短路徑、graphlet 等），是以受到泛化性差等問題的阻礙。為了解決這個限制，在這項工作中，我們提出了一個名為 graph2vec 的神經嵌入架構來學習任意大小圖的資料驅動的分布式表示。圖2vec' s 嵌入是以無監督的方式學習的，并且與任務無關。是以，它們可以用于任何下遊任務，例如圖分類、聚類甚至播種監督表示學習方法。我們在幾個基準和大型現實世界資料集上的實驗表明，graph2vec 在分類和聚類精度方面比子結構表示學習方法有顯着提高，并且可以與最先進的圖核心競争。

1.3.1. 節點嵌入(Node Embedding)

我們首先關注的是圖元件的嵌入。有幾種方法可以對節點或邊進行嵌入。例如，DeepWalk【http://www.perozzi.net/projects/deepwalk/ 】使用短随機遊走來學習圖中邊的表示。我們将讨論Node2Vec，這篇論文由2016年斯坦福大學的Aditya Grover和Jure Leskovec發表。

作者說：“node2vec是一個用于圖表示學習的算法架構。給定任何圖，它可以學習節點的連續特征表示，然後可以用于各種下遊機器學習任務。“

該模型通過使用随機遊走，優化鄰域保持目标來學習節點的低維表示。

Node2Vec的代碼可以在GitHub上找到：

https://github.com/eliorc/node2vec

部分程式出圖不一一展示，詳情進入項目連結即可

2.圖神經網絡GNN

2.1GNN引言

圖神經網絡（Graph Neural Networks，GNN）綜述連結：https://zhuanlan.zhihu.com/p/75307407?from_voters_page=true 譯文

https://arxiv.org/pdf/1901.00596.pdf 原始文章最新版本V4版本

近年來，深度學習徹底改變了許多機器學習任務，從圖像分類和視訊處理到語音識别和自然語言了解。這些任務中的資料通常在歐幾裡得空間中表示。然而，越來越多的應用程式将資料從非歐幾裡德域生成并表示為具有複雜關系和對象之間互相依賴關系的圖。圖資料的複雜性對現有的機器學習算法提出了重大挑戰。最近，出現了許多關于擴充圖資料深度學習方法的研究。在本次調查中，我們全面概述了資料挖掘和機器學習領域中的圖神經網絡 (GNN)。我們提出了一種新的分類法，将最先進的圖神經網絡分為四類，即循環圖神經網絡、卷積圖神經網絡、圖自動編碼器和時空圖神經網絡。我們進一步讨論了圖神經網絡在各個領域的應用，并總結了圖神經網絡的開源代碼、基準資料集和模型評估。最後，我們在這個快速發展的領域提出了潛在的研究方向

神經網絡最近的成功推動了模式識别和資料挖掘的研究。許多機器學習任務，如對象檢測 [1]、[2]、機器翻譯 [3]、[4] 和語音識别 [5]，曾經嚴重依賴手工特征工程來提取資訊特征集，最近已經由各種端到端深度學習範例徹底改變，例如卷積神經網絡 (CNN) [6]、遞歸神經網絡 (RNN) [7] 和自動編碼器 [8]。深度學習在許多領域的成功部分歸功于快速發展的計算資源（例如 GPU）、大訓練資料的可用性以及深度學習從歐幾裡得資料（例如圖像、文本、和視訊）。以圖像資料為例，我們可以将圖像表示為歐幾裡得空間中的規則網格。卷積神經網絡 (CNN) 能夠利用圖像資料的移位不變性、局部連通性群組合性 [9]。是以，CNN 可以提取與整個資料集共享的局部有意義的特征，用于各種圖像分析。

雖然深度學習有效地捕獲了歐幾裡得資料的隐藏模式，但越來越多的應用程式将資料以圖形的形式表示。例如，在電子商務中，基于圖的學習系統可以利用使用者和産品之間的互動來做出高度準确的推薦。在化學中，分子被模組化為圖形，并且需要确定它們的生物活性以進行藥物發現。在引文網絡中，論文通過引文互相連結，并且需要将它們分類到不同的組中。圖資料的複雜性對現有的機器學習算法提出了重大挑戰。由于圖可能是不規則的，圖可能具有可變大小的無序節點，并且來自圖中的節點可能具有不同數量的鄰居，導緻一些重要的操作（例如卷積）在圖像域中很容易計算，但是難以應用于圖域。此外，現有機器學習算法的一個核心假設是執行個體互相獨立。這個假設不再适用于圖資料，因為每個執行個體（節點）通過各種類型的連結（例如引用、友誼和互動）與其他執行個體相關聯。

最近，人們對擴充圖形資料的深度學習方法越來越感興趣。受來自深度學習的 CNN、RNN 和自動編碼器的推動，在過去幾年中，重要操作的新泛化和定義迅速發展，以處理圖資料的複雜性。例如，可以從 2D 卷積推廣圖卷積。如圖 1 所示，可以将圖像視為圖形的特殊情況，其中像素由相鄰像素連接配接。與 2D 卷積類似，可以通過取節點鄰域資訊的權重平均值來執行圖卷積。

二維卷積類似于圖，圖像中的每個像素都被視為一個節點，其中鄰居由過濾器大小确定。 2D 卷積取紅色節點及其鄰居像素值的權重平均值。節點的鄰居是有序的并且具有固定的大小。

圖卷積。為了得到紅色節點的隐藏表示，圖卷積運算的一個簡單解決方案是取紅色節點及其鄰居節點特征的平均值。與圖像資料不同，節點的鄰居是無序且大小可變的。

發展：

圖神經網絡 (GNN) Sperduti 等人的簡史。 (1997) [13] 首次将神經網絡應用于有向無環圖，這激發了對 GNN 的早期研究。圖神經網絡的概念最初是在 Gori 等人中概述的。 (2005) [14] 并在 Scarselli 等人中進一步闡述。 (2009) [15] 和 Gallicchio 等人。 (2010) [16]。這些早期研究屬于循環圖神經網絡（RecGNNs）的範疇。他們通過以疊代方式傳播鄰居資訊來學習目标節點的表示，直到達到一個穩定的固定點。這個過程在計算上是昂貴的，并且最近已經越來越多地努力克服這些挑戰[17]，[18]。

受 CNN 在計算機視覺領域的成功的鼓舞，大量重新定義圖資料卷積概念的方法被并行開發。這些方法屬于卷積圖神經網絡 (ConvGNN) 的範疇。 ConvGNN 分為兩個主流，基于光譜的方法和基于空間的方法。 Bruna 等人提出了第一個關于基于光譜的 ConvGNN 的傑出研究。（2013）[19]，它開發了一種基于譜圖理論的圖卷積。從那時起，基于譜的 ConvGNN [20]、[21]、[22]、[23] 的改進、擴充和近似值不斷增加。基于空間的 ConvGNN 的研究比基于光譜的 ConvGNN 早得多。 2009 年，Micheli 等人。 [24] 首先通過架構複合非遞歸層解決了圖互相依賴問題，同時繼承了 RecGNN 的消息傳遞思想。然而，這項工作的重要性被忽視了。直到最近，出現了許多基于空間的 ConvGNN（例如，[25]、[26]、[27]）。代表性 RecGNNs 和 ConvGNNs 的時間線如表 II 的第一列所示。除了 RecGNNs 和 ConvGNNs，在過去幾年中還開發了許多替代 GNN，包括圖自動編碼器 (GAE) 和時空圖神經網絡 (STGNN)。這些學習架構可以建立在 RecGNN、ConvGNN 或其他用于圖模組化的神經架構上。

綜述總結如下：

新分類我們提出了一種新的圖神經網絡分類。圖神經網絡分為四組：循環圖神經網絡、卷積圖神經網絡、圖自動編碼器和時空圖神經網絡。
綜合回顧我們提供了最全面的圖資料現代深度學習技術概覽。對于每種類型的圖神經網絡，我們都提供了代表性模型的較長的描述，進行了必要的比較，并總結了相應的算法。
豐富的資源我們收集了豐富的圖神經網絡資源，包括最先進的模型、基準資料集、開源代碼和實際應用。本調查可用作了解、使用和開發适用于各種現實生活應用的不同深度學習方法的實踐指南。
未來方向我們讨論了圖神經網絡的理論方面，分析了現有方法的局限性，并在模型深度、可擴充性權衡、異質性和動态性方面提出了四個可能的未來研究方向。

2.2 神經網絡類型

在本節中，我們介紹了圖神經網絡 (GNN) 的分類，如表 II 所示。我們将圖神經網絡 (GNN) 分為循環圖神經網絡 (RecGNN)、卷積圖神經網絡 (ConvGNN)、圖自動編碼器 (GAE) 和時空圖神經網絡 (STGNN)。圖 2 給出了各種模型架構的示例。下面，我們對每個類别進行簡要介紹。

2.2.1循環圖神經網絡（RecGNNs，Recurrent graph neural networks ）

循環圖神經網絡（RecGNNs）大多是圖神經網絡的先驅作品。 RecGNN 旨在學習具有循環神經架構的節點表示。他們假設圖中的一個節點不斷地與其鄰居交換資訊/消息，直到達到穩定的平衡。 RecGNN 在概念上很重要，并啟發了後來對卷積圖神經網絡的研究。特别是，基于空間的卷積圖神經網絡繼承了消息傳遞的思想。

2.2.2 卷積圖神經網絡 (ConvGNNs，Convolutional graph neural networks)

卷積圖神經網絡 (ConvGNNs) 将卷積操作從網格資料推廣到圖資料。主要思想是通過聚合它自己的特征 xv 和鄰居的特征 xu 來生成節點 v 的表示，其中 u ∈ N(v)。與 RecGNN 不同，ConvGNN 堆疊多個圖卷積層以提取進階節點表示。 ConvGNN 在建構許多其他複雜的 GNN 模型中發揮着核心作用。圖 2a 顯示了用于節點分類的 ConvGNN。圖 2b 展示了用于圖分類的 ConvGNN。

2.2.3圖自動編碼器 (GAE，Graph autoencoders (GAEs))

是無監督學習架構，它将節點/圖編碼到潛在向量空間并從編碼資訊中重建圖資料。 GAE 用于學習網絡嵌入和圖形生成分布。對于網絡嵌入，GAE 通過重構圖結構資訊（例如圖鄰接矩陣）來學習潛在節點表示。對于圖的生成，一些方法逐漸生成圖的節點和邊，而另一些方法一次全部輸出圖。圖 2c 展示了一個用于網絡嵌入的 GAE。

2.2.4 時空圖神經網絡 (STGNN，Spatial-temporal graph neural networks)

旨在從時空圖中學習隐藏模式，這在各種應用中變得越來越重要，例如交通速度預測 [72]、駕駛員機動預期 [73] 和人類動作識别 [ 75]。 STGNN 的關鍵思想是同時考慮空間依賴和時間依賴。許多目前的方法內建了圖卷積來捕獲空間依賴性，并使用 RNN 或 CNN 對時間依賴性進行模組化。圖 2d 說明了用于時空圖預測的 STGNN。

具體公式推到見論文！

2.3圖神經網絡的應用

GNN 在不同的任務和領域中有許多應用。盡管每個類别的 GNN 都可以直接處理一般任務，包括節點分類、圖分類、網絡嵌入、圖生成和時空圖預測，但其他與圖相關的一般任務，如節點聚類 [134]、連結預測 [135 ]，圖分割[136]也可以通過GNN來解決。我們詳細介紹了基于以下研究領域的一些應用。

計算機視覺（Computer vision）

計算機視覺 GNN 在計算機視覺中的應用包括場景圖生成、點雲分類和動作識别。識别對象之間的語義關系有助于了解視覺場景背後的含義。

場景圖生成模型旨在将圖像解析為由對象及其語義關系組成的語義圖 [137]、[138]、[139]。另一個應用程式通過在給定場景圖的情況下生成逼真的圖像來反轉該過程 [140]。由于自然語言可以被解析為每個單詞代表一個對象的語義圖，是以它是一種很有前途的解決方案，可以在給定文本描述的情況下合成圖像。

分類和分割點雲使 LiDAR 裝置能夠“看到”周圍環境。點雲是由 LiDAR 掃描記錄的一組 3D 點。 [141]、[142]、[143] 将點雲轉換為 k-最近鄰圖或超點圖，并使用 ConvGNN 探索拓撲結構。

識别視訊中包含的人類行為有助于從機器方面更好地了解視訊内容。一些解決方案檢測視訊剪輯中人體關節的位置。由骨骼連接配接起來的人體關節自然形成了一個圖形。給定人類關節位置的時間序列，[73]、[75] 應用 STGNN 來學習人類動作模式。

此外，GNN 在計算機視覺中的适用方向數量仍在增長。它包括人-物互動[144]、小樣本圖像分類[145]、[146]、[147]、語義分割[148]、[149]、視覺推理[150]和問答[151]。

自然語言處理（Natural language processing ）

自然語言處理 GNN 在自然語言進行中的一個常見應用是文本分類。 GNN 利用文檔或單詞的互相關系來推斷文檔标簽 [22]、[42]、[43]。

盡管自然語言資料表現出順序，但它們也可能包含内部圖結構，例如句法依賴樹。句法依賴樹定義了句子中單詞之間的句法關系。 Marcheggiani 等人。 [152] 提出了在 CNN/RNN 句子編碼器之上運作的句法 GCN。 Syntactic GCN 基于句子的句法依賴樹聚合隐藏的單詞表示。巴斯廷斯等人。 [153] 将句法 GCN 應用于神經機器翻譯任務。 Marcheggiani 等人。[154] 進一步采用與 Bastings 等人相同的模型。
[153]處理句子的語義依賴圖。

圖到序列學習學習在給定抽象詞的語義圖（稱為抽象意義表示）的情況下生成具有相同含義的句子。宋等人。 [155] 提出了一種圖 LSTM 來編碼圖級語義資訊。貝克等人。 [156] 将 GGNN [17] 應用于圖到序列學習和神經機器翻譯。逆向任務是序列到圖的學習。給定句子生成語義或知識圖在知識發現中非常有用

交通 Traffic

準确預測交通網絡中的交通速度、交通量或道路密度對于智能交通系統至關重要。 [48]、[72]、[74] 使用 STGNN 解決交通預測問題。 他們将交通網絡視為一個時空圖，其中節點是安裝在道路上的傳感器，邊緣由節點對之間的距離測量，每個節點将視窗内的平均交通速度作為動态輸入特征。 另一個工業級應用是計程車需求預測。 鑒于曆史計程車需求、位置資訊、天氣資料和事件特征，Yao 等人。 [159] 結合 LSTM、CNN 和由 LINE [160] 訓練的網絡嵌入，形成每個位置的聯合表示，以預測時間間隔内某個位置所需的計程車數量。

化學 Chemistry

在化學領域，研究人員應用 GNN 來研究分子/化合物的圖形結構。 在分子/化合物圖中，原子被視為節點，化學鍵被視為邊緣。 節點分類、圖分類和圖生成是針對分子/化合物圖的三個主要任務，以學習分子指紋 [85]、[86]、預測分子特性 [27]、推斷蛋白質界面 [164] 和 合成化合物

其他

GNN 的應用不僅限于上述領域和任務。 已經探索将 GNN 應用于各種問題，例如程式驗證 [17]、程式推理 [166]、社會影響預測 [167]、對抗性預防 [168]、電子健康記錄模組化 [169]、[170] ]、大腦網絡[171]、事件檢測[172]群組合優化[173]。

2.4未來方向

盡管 GNN 已經證明了它們在學習圖資料方面的能力，但由于圖的複雜性，挑戰仍然存在。

模型深度 Model depth

深度學習的成功在于深度神經架構 [174]。然而，李等人。表明随着圖卷積層數的增加，ConvGNN 的性能急劇下降 [53]。随着圖卷積将相鄰節點的表示推得更近，理論上，在無限數量的圖卷積層中，所有節點的表示将收斂到一個點 [53]。這就提出了一個問題，即深入研究是否仍然是學習圖資料的好政策。

可擴充性權衡 Scalability trade-off

GNN 的可擴充性是以破壞圖完整性為代價的。無論是使用采樣還是聚類，模型都會丢失部分圖資訊。通過采樣，節點可能會錯過其有影響力的鄰居。通過聚類，圖可能被剝奪了獨特的結構模式。如何權衡算法的可擴充性和圖的完整性可能是未來的研究方向。

異質性Heterogenity

目前的大多數 GNN 都假設圖是同質的。目前的 GNN 很難直接應用于異構圖，異構圖可能包含不同類型的節點和邊，或者不同形式的節點和邊輸入，例如圖像和文本。是以，應該開發新的方法來處理異構圖。

動态Dynamicity

圖本質上是動态的，節點或邊可能出現或消失，節點/邊輸入可能會随時間變化。需要新的圖卷積來适應圖的動态性。雖然圖的動态性可以通過 STGNN 部分解決，但很少有人考慮在動态空間關系的情況下如何執行圖卷積。

總結

因為之前一直在研究知識提取相關算法，後續為了建構小型領域知識圖譜，會用到知識融合、知識推理等技術，現在開始學習研究圖計算相關。

現在已經覆寫了圖的介紹，圖的主要類型，不同的圖算法，在Python中使用Networkx來實作它們，以及用于節點标記，連結預測和圖嵌入的圖學習技術，最後講了GNN應用。

本項目參考了：maelfabien大神、以及自尊心3 在部落格 or github上的貢獻

歡迎大家fork，後續将開始圖計算相關項目以及部分知識提取技術深化！

項目參考連結：

第一章節：

https://maelfabien.github.io/machinelearning/graph_4/#ii-node-labeling

https://blog.csdn.net/xjxgyc/article/details/100175930

https://maelfabien.github.io/machinelearning/graph_5/#node-embedding