圖機器學(xué)習(xí)（Graph Machine Learning，簡稱Graph ML）是機器學(xué)習(xí)的一個分支，專注于利用圖形結(jié)構(gòu)的數(shù)據(jù)。在圖形結(jié)構(gòu)中，數(shù)據(jù)以圖的形式表示，其中的節(jié)點（或頂點）表示實體，邊（或鏈接）表示實體之間的關(guān)系。

本篇文章將從基礎(chǔ)開始介紹什么是圖，我們?nèi)绾蚊枋龊捅硎舅鼈?，以及它們的屬性是什么?/p>

圖論是在18世紀(jì)由歐拉引入的，用來解決著名的柯尼斯堡大橋問題：是否有可能只穿過七座橋中的每座橋一次。

什么是圖？如何定義它？

圖就是一組相互連接的對象。

一個圖有一組結(jié)點N和邊E, n是頂點的數(shù)目，m是邊的數(shù)目。連接的兩個節(jié)點被定義為相鄰(節(jié)點1相鄰或鄰接4)。當(dāng)我們稱網(wǎng)絡(luò)的大小N時，通常指的是節(jié)點的數(shù)量(鏈路或邊的數(shù)量通常稱為L)。

有向與無向

圖可以是無向圖或有向圖：

無向圖：邊是無向的，關(guān)系是對稱的。畫邊的順序并不重要。

有向圖：邊是有向的(也稱為有向圖)，頂點之間的邊可以有方向，可以用箭頭表示(也稱為弧線)。

圖的基本性質(zhì)

對于一個節(jié)點，我們可以將節(jié)點度(k)定義為與節(jié)點相鄰的邊，對于一個圖，我們可以計算無向圖的平均度k：

在有向網(wǎng)絡(luò)中，定義了一個節(jié)點的入度(指指向該節(jié)點的邊)和出度(指離開該節(jié)點的邊)，節(jié)點的總度是兩者的和。我們稱source節(jié)點為沒有入度的節(jié)點，稱sink節(jié)點為沒有出度的節(jié)點。

我們可以計算平均度為：

這里的

鄰接矩陣是表示圖的另一種方式，其中行和列表示圖節(jié)點，交集表示一個節(jié)點的兩個節(jié)點之間是否存在鏈接。鄰接矩陣的大小是n x n(頂點數(shù))。如果Aij是節(jié)點i和j之間的鏈接，則Aij為1，否則為0，對于無向圖，矩陣是對稱的?？梢钥吹皆诰仃嚨膶蔷€上沒有1意味著沒有自環(huán)(節(jié)點與自身相連)

對于一個節(jié)點 i 計算一個節(jié)點的邊(或它的度)，沿著行或列求和：

無向圖中的總邊數(shù)是每個節(jié)點的度之和(也可以是鄰接矩陣中的值之和)：

因為在無向圖中，你要計算兩次邊(由于鄰接矩陣是對稱的，要計算兩次相同的邊)，所以除以2

對于有向圖，可以表示兩個不同的鄰接矩陣，一個表示入度，一個表示出度

對于一個節(jié)點，總邊數(shù)是入度和出度之和：

我們計算一個節(jié)點的入度和出度以及總邊數(shù)：

由于線性代數(shù)和圖論之間存在聯(lián)系，所以可以對鄰接矩陣應(yīng)用不同的操作。如果轉(zhuǎn)置一個無向圖的鄰接矩陣，圖是沒有改變的因為是對稱的，但如果轉(zhuǎn)置一個有向圖的鄰接矩陣，邊則進行了方向的轉(zhuǎn)換。

這些矩陣非常是稀疏的，因為理論上一個節(jié)點是可以連接到所有其他節(jié)點，但這在現(xiàn)實生活中基本上不會發(fā)生。當(dāng)所有節(jié)點都與其他節(jié)點相連時，我們稱之為完全圖。完全圖通常用于理解圖論中的一些復(fù)雜問題(連通性例子等)。

圖的最大密度是一個完全圖中可能關(guān)系的總數(shù)。實際密度是測量無向非完全圖的密度：

理論上來說在社交網(wǎng)絡(luò)中，每個人都可以連接到每個人，但這并沒有發(fā)生。所以最終得到一個 70 億行和 70 億列的鄰接矩陣，其中大多數(shù)條目為零(因為非常稀疏)。為什么要說這個呢？因為不是所有的算法都能很好地處理稀疏矩陣。

除了鄰接矩陣，我們還可以將圖表示為一個邊的列表：

但是這種方法對于機器學(xué)習(xí)分析是有問題的，所以就出現(xiàn)了一種常用的方法：鄰接表，因為鄰接表對大型和稀疏的節(jié)點很有用，它允許快速檢索節(jié)點的鄰居。

加權(quán)圖

圖邊還可以增加權(quán)值，邊并不都是相同的，比如在交通圖中，為了選擇兩個節(jié)點之間的最佳路徑，我們將考慮表示時間或交通的權(quán)重。

自循環(huán)

圖的節(jié)點是可以連接到自己的，所以必須在計算總邊數(shù)時添加自循環(huán)

你也可以有一個多圖，一個對節(jié)點有多條邊

多重圖

含有平行邊的圖稱為多重圖，或者說一個對節(jié)點有多條邊

上面就是一些常見的圖和表示方式，我們來做一個匯總

圖的另一個重要參數(shù)是連接性(連通性)。每個節(jié)點都能被所有其他節(jié)點到達嗎？連通圖是指所有頂點都可以通過一條路徑連接起來的圖。不連通圖是指有兩個或多個連通分量的圖

最大的隔離的節(jié)點子集被稱為“孤島”（island）。知道圖是連通的還是不連通的是很重要的，有些算法很難處理不連通的圖。

這可以在鄰接矩陣中顯示，其中不同的組件被寫成對角線塊(非零元素被限制在平方矩陣中)。我們稱連接兩個“孤島”的鏈接“橋”（bridge）

如果圖很小，這種視覺檢查很容易，但對于一個大圖，檢查連通性是非常有挑戰(zhàn)的。

雙部圖

我們上面所看到的圖稱為單部圖，其中只有一種類型的節(jié)點和一種類型的關(guān)系

雙部圖是一種將節(jié)點劃分為兩個不相交集合（通常稱為 U 和 V）的圖。這些集合是獨立的，U 集合中的每個節(jié)點都與 V 集合中的某個節(jié)點相連（每個鏈接只能連接一個集合中的節(jié)點到另一個集合中的節(jié)點）。因此，雙部圖是一種不存在 U-U 連接和 V-V 連接的圖。有許多這樣的例子：作者到論文（作者位于 U 集合，并且他們與他們撰寫的論文即 V 集合相連）、演員（U）和他們參演的電影（V）、用戶和產(chǎn)品、食譜和配料等。另一個例子是疾病網(wǎng)絡(luò)，其中包括一組疾病和一組基因，只有包含已知會導(dǎo)致或影響該疾病的突變的基因才與該疾病相連。另一個例子是匹配，雙部圖可用于約會應(yīng)用程序。對于一個有兩組節(jié)點的雙部圖（U 有 m 個節(jié)點，V 有 n 個節(jié)點），可能的邊的總數(shù)是 m*n，節(jié)點的總數(shù)是 m + n。

雙部圖可以折疊成兩個單獨的網(wǎng)絡(luò)，U 的投影和 V 的投影。在 U 的投影中，如果兩個節(jié)點連接到同一個 V 節(jié)點，則它們相連（V 投影的原理相同）。

如果需要，我們也可以構(gòu)建一個三部圖?？偟膩碚f，你可以擁有超過三種類型的節(jié)點，通常我們講的是 k-部圖。這種類型的圖擴展了我們對雙部圖的看法。

異構(gòu)圖

異構(gòu)圖（也稱異質(zhì)圖）是一種具有不同類型的節(jié)點和邊的圖。

平面圖

如果一幅圖可以繪制成沒有任何邊相交的形式（對于圖來說，如果可以以這種方式繪制，它被稱為平面表示），則可以將其視為平面圖。即使繪制時邊相交，圖也可以是平面的?？催@個例子，這幅圖可以重新繪制成平面表示。

為什么知道我們是否可以有平面表示很有用？最常用的一個例子是繪制電路版，要保證電路不會相交。

循環(huán)圖與非循環(huán)圖

線路 (walk) 是節(jié)點的交替序列（u-v 的線路是從 u 開始并在 v 結(jié)束的節(jié)點序列）。路徑（path）是序列中節(jié)點各不相同的線路（u-x-v 是一條路徑，但 u-x-u-x-v 是線路但不是路徑）。循環(huán)圖是路徑開始和結(jié)束于同一節(jié)點的圖，因為不同的算法都有循環(huán)問題(所以有時需要通過切斷一些連接將循環(huán)圖轉(zhuǎn)換為非循環(huán)圖)。我們可以將前饋神經(jīng)網(wǎng)絡(luò)定義為有向無環(huán)圖（DAG），因為DAG 總是有一個結(jié)束點（也稱為葉子節(jié)點）。

總結(jié)

在本文中，我們介紹了什么是圖及其主要屬性，盡管圖看起來很簡單，但可以實現(xiàn)無限的變化。圖是節(jié)點和邊的集合;它沒有順序，沒有開始也沒有結(jié)束。我們可以通過它們定義不同類型的概念和數(shù)據(jù)。圖還可以簡潔地描述數(shù)據(jù)的許多屬性，并為我們提供關(guān)于不同主題之間關(guān)系的信息。例如，我們可以為節(jié)點和邊分配權(quán)重和屬性。在以后的文章中，我們將討論如何在這些網(wǎng)絡(luò)中使用算法(以及如何表示它們)。

作者：Salvatore Raieli

來源：DeepHub IMBA