1.1 什么是圖(graph)？

在圖論的上下文中，圖是一種結構化數據類型，具有節點(nodes)（保存信息的實體）和邊緣(edges)（連接節點的連接，也可以保存信息）。

圖是一種數據結構的方式，但它本身可以是一個數據點。圖是一種非歐幾里得數據類型，這意味著它們存在于三維空間，不像其他數據類型，比如圖像、文本和音頻。

圖可以具有某些屬性，這些屬性限制了可以對其執行的可能操作和分析。這些屬性可以被定義。

1.2 圖的定義

首先，讓我們介紹一些定義。

在計算機科學中，我們經常談論一種稱為圖的數據結構：

圖的邊緣和/或節點上可以有標簽，讓我們給它一些邊緣和節點的標簽。

標簽也可以被視為權重，但這取決于圖的設計者。

標簽不必是數字，它們可以是文本的。

標簽不必是唯一的；給多個節點相同的標簽是完全可能的，有時也是有用的。例如，氫分子就是一個例子：

注意混合了數值和文本數據類型

圖可以具有特征（也稱為屬性）。

要小心不要混淆特征和標簽。一個簡單的思考方式是使用名稱、角色和人的類比：

一個節點就是一個人，一個節點的標簽就是一個人的名字，而節點的特征就是這個人的特點。

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

請注意，有向圖也可以具有無向邊

圖中的一個節點甚至可以有指向自身的邊緣。這被稱為自環(self-loop)。

圖可以是：

異構的(Heterogeneous) — 由不同類型的節點組成
同構的(Homogeneous) — 由相同類型的節點組成

并且可以是：

靜態的(Static) — 節點和邊不變，沒有添加或刪除
動態的(Dynamic) — 節點和邊發生變化，添加、刪除、移動等

粗略地說，圖可以模糊地描述為：

密集的(Dense) — 由許多節點和邊組成
稀疏的(Sparse) — 由較少的節點和邊組成

通過將它們轉化為平面形式，可以使圖看起來更整潔，這基本上意味著重新排列節點，使邊不相交。

當我們探索目前在各種GNN架構中使用的許多不同方法時，這些概念和術語將會派上用場。其中一些基本方法在以下方面進行了描述：

1.3 圖分析

有各種不同的圖結構可供ML模型學習（Wheel，Cycle，Star，Grid，Lollipop，Dense，Sparse等）。

你可以遍歷一個圖：

Jon在4個時間步驟內從Bob到Bic；他最好希望不下雪！

在這種情況下，我們正在遍歷一個無向圖。顯然，如果圖是有向的，那么只需按照邊的方向前進。有幾種不同類型的遍歷，所以要注意措辭。以下是一些最常見的圖遍歷術語及其含義：

行走（Walk）：圖的遍歷 —— 閉合行走是指目標節點與源節點相同
小徑（Trail）：沒有重復邊的行走 —— 電路（Circuit）是閉合小徑
路徑（Path）：沒有重復節點的行走 —— 循環（Cycle）是閉合路徑

在遍歷的概念基礎上，人們還可以在圖上發送消息。

Sam？更像是S-p-am（垃圾郵件）...

所有的Sam的鄰居都給他發送了一條消息，其中t代表時間步驟。Sam可以選擇打開他的郵箱并更新自己的信息。在具有注意機制的模型中，信息在網絡中傳播的概念非常重要。在圖中，消息傳遞是我們泛化卷積的一種方式。稍后會詳細討論。

1.4 E-圖 — 計算機上的圖

通過學習所有這些，你現在對圖理論有了基本的理解！任何對GNNs重要的其他概念將會隨著它們的出現而進行解釋，但與此同時，還有一個關于圖的最后一個主題我們需要涵蓋。我們必須學會如何在計算中表達圖。

有幾種方法可以將圖轉化為計算機可以處理的格式；它們都是不同類型的矩陣。

關聯矩陣Incidence Matrix（I）：

關聯矩陣通常在研究論文中用大寫字母I表示，由1、0和-1組成，關聯矩陣可以按照以下簡單的模式制作：

從圖到關聯矩陣

（帶權重的）鄰接矩陣Adjacency Matrix（A）：

圖的鄰接矩陣由1和0組成，除非它是加權或帶標簽的。在任何情況下，A都可以按照以下規則構建：

無向圖的鄰接矩陣因此在其對角線上是對稱的，從左上角對象到右下角：

有向圖的鄰接矩陣只覆蓋對角線線的一側，因為有向圖的邊只朝一個方向。

鄰接矩陣可以是“帶權重的”，這基本上意味著每條邊都有與之關聯的值，所以不是1，而是將值放在相應的矩陣坐標中。這些權重可以代表任何你想要的東西。例如，在分子的情況下，它們可以表示兩個節點（原子）之間的鍵的類型。在LinkedIn這樣的社交網絡中，它們可以表示兩個節點（人）之間的1st、2nd或3rd級連接。

邊的權重概念是使GNNs如此強大的一個屬性；它們允許我們考慮結構性（依賴性）和獨立性信息。對于實際應用，這意味著我們可以考慮外部和內部信息。

度矩陣（D）：

圖的度矩陣可以通過之前介紹的度概念來找到。D本質上是一個對角矩陣，其中對角線的每個值都是其對應節點的度數。