圖機(jī)器學(xué)習(xí)入門：基本概念介紹

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

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

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

什么是圖？如何定義它？

圖就是一組相互連接的對(duì)象。

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

有向與無(wú)向

圖可以是無(wú)向圖或有向圖：

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

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

圖的基本性質(zhì)

對(duì)于一個(gè)節(jié)點(diǎn)，我們可以將節(jié)點(diǎn)度(k)定義為與節(jié)點(diǎn)相鄰的邊，對(duì)于一個(gè)圖，我們可以計(jì)算無(wú)向圖的平均度k：

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

我們可以計(jì)算平均度為：

這里的

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

對(duì)于一個(gè)節(jié)點(diǎn) i 計(jì)算一個(gè)節(jié)點(diǎn)的邊(或它的度)，沿著行或列求和：

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

因?yàn)樵跓o(wú)向圖中，你要計(jì)算兩次邊(由于鄰接矩陣是對(duì)稱的，要計(jì)算兩次相同的邊)，所以除以2

對(duì)于有向圖，可以表示兩個(gè)不同的鄰接矩陣，一個(gè)表示入度，一個(gè)表示出度

對(duì)于一個(gè)節(jié)點(diǎn)，總邊數(shù)是入度和出度之和：

我們計(jì)算一個(gè)節(jié)點(diǎn)的入度和出度以及總邊數(shù)：

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

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

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

理論上來(lái)說(shuō)在社交網(wǎng)絡(luò)中，每個(gè)人都可以連接到每個(gè)人，但這并沒(méi)有發(fā)生。所以最終得到一個(gè) 70 億行和 70 億列的鄰接矩陣，其中大多數(shù)條目為零(因?yàn)榉浅Ｏ∈?。為什么要說(shuō)這個(gè)呢？因?yàn)椴皇撬械?a target="_blank">算法都能很好地處理稀疏矩陣。

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

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

加權(quán)圖

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

自循環(huán)

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

你也可以有一個(gè)多圖，一個(gè)對(duì)節(jié)點(diǎn)有多條邊

多重圖

含有平行邊的圖稱為多重圖，或者說(shuō)一個(gè)對(duì)節(jié)點(diǎn)有多條邊

上面就是一些常見(jiàn)的圖和表示方式，我們來(lái)做一個(gè)匯總

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

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

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

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

雙部圖

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

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

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

如果需要，我們也可以構(gòu)建一個(gè)三部圖?？偟膩?lái)說(shuō)，你可以擁有超過(guò)三種類型的節(jié)點(diǎn)，通常我們講的是 k-部圖。這種類型的圖擴(kuò)展了我們對(duì)雙部圖的看法。

異構(gòu)圖

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

平面圖

如果一幅圖可以繪制成沒(méi)有任何邊相交的形式（對(duì)于圖來(lái)說(shuō)，如果可以以這種方式繪制，它被稱為平面表示），則可以將其視為平面圖。即使繪制時(shí)邊相交，圖也可以是平面的。看這個(gè)例子，這幅圖可以重新繪制成平面表示。

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

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

線路 (walk) 是節(jié)點(diǎn)的交替序列（u-v 的線路是從 u 開(kāi)始并在 v 結(jié)束的節(jié)點(diǎn)序列）。路徑（path）是序列中節(jié)點(diǎn)各不相同的線路（u-x-v 是一條路徑，但 u-x-u-x-v 是線路但不是路徑）。循環(huán)圖是路徑開(kāi)始和結(jié)束于同一節(jié)點(diǎn)的圖，因?yàn)椴煌乃惴ǘ加醒h(huán)問(wèn)題(所以有時(shí)需要通過(guò)切斷一些連接將循環(huán)圖轉(zhuǎn)換為非循環(huán)圖)。我們可以將前饋神經(jīng)網(wǎng)絡(luò)定義為有向無(wú)環(huán)圖（DAG），因?yàn)镈AG 總是有一個(gè)結(jié)束點(diǎn)（也稱為葉子節(jié)點(diǎn)）。

總結(jié)

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

作者：Salvatore Raieli

來(lái)源：DeepHub IMBA