# 《深入淺出圖神經網路:GNN原理》閱讀筆記
###### tags: `GNN`
## Chapter 4. 表示學習
---
- 傳統機器學習需要花費很多心力在做數據處理及轉換已得到好的特徵，演算法才能執行的更好
- 表示學習要做的就是從資料判別特徵
1. 如何比較兩個表示
2. 如何挖掘表示
3. 如何定義尋找的目標
- 大概可以理解成是你要如何用data的方式表示出一個物件

#### 離散與分布式表示
- **One-Hot encoding:**
有n個物件就需要n維的向量，透過在某個維度為1而其他全0的方式去做encoding

缺點:
假定所有維度相互獨立，但實際上不是，這樣會導致丟失了許多語意
另外期也會是一個稀疏矩陣，直接使用會不太好用

- **分布式:**
就像是顏色用(256,256,256)這樣，透過低維稠密的向量來做表示
同時也能解決one-hot的兩個缺點

#### 端對端學習(end-to-end)
- 由輸入端到輸出端用一個神經網路相連
- 機器學習: 特徵工程 -> 分類器 -> output
- 深度學習: input(e.g image)-> neural net work -> output
像深度學習這種方式就可以稱做是端對端可以理解成是**同時優化和進行表示學習和任務學習**
- 遷移學習(transfer learning):
用別人預訓練號好的model來應用自己的任務，需要進行一些參數的微調

### 4.2 AutoEncoder
- encoder + decoder, 將input mapping 到一個feature space，再還原回來
- 想法也是某個權重乘上input+bias並套用activation後會得到一組特徵向量h，若是把特徵向量h再乘上decoder的權重、加上bias和套用activation之後，會得到input'，拿來跟原始input做比對(loss function)
- 如果autoencoder出來的特徵維度小於原始input，會類似於PCA的效果，稱作欠完備自編碼器
- Encoder為從舊特徵提取出新特徵映射到latent space
- 用神經網路作為編碼與解碼器

#### Regulation Autoencoder
- 如果維度可以大於原始input，即稱做過完備自編碼器，但有可能導致學不到有用特徵，所以加入一些正則化的約束。

##### 1. 去躁自編碼器 Denoising autoencoder
在input加上噪音，decoder需要重新建構出沒有噪音的input，讓encoder能夠學會提取出有用的資訊。
加躁的一種做法是將部分x換成是0

##### 2. 稀疏自編碼器 Sparse autoencoder
限制神經元的活躍度，使大多數都處在不活躍的階段
活躍度的定義是他在所有樣本上取值的平均值，，限制其等於某一個超參數(通常接近於0)，對於該值偏離較大的神經元做penalty
用**相對熵**來做loss function

傳統的autoencoder必須要有連續的latent space，不然再生成採樣的時候可能會採到空白的地方導致生不出東西

autoencoder以盡可能少的損失為目標來做訓練，但他不會去管latent space的組織架構如何生成。因此，如果沒有仔細定義其架構，訓練後的網路很容易會過擬合。

#### Variational autoencoder
本質是一種generator，想要從樣本找到分布P(x)，藉此可以sample出更多樣本
比較好的說法是會想要讓生成的latent feature服從某一分布(通常是高斯分布)

實際做法是先生出mean跟sd兩種向量，並用normal distribution生出第三個向量，把sd的向量取exp再和sample出來的向量相乘後再與mean的向量相加，即可得到latent variable
好處是可以藉由參數的調整控制想生成的圖片

整體流程可以想成:
input -> latent distribution -> sample from it -> reconstruct input

會對latent space的distribution加入正則項，防止latent space裡的編碼相互偏離

refer to [變分自編碼器](https://zhuanlan.zhihu.com/p/144649293)

#### Word2vec
- 將詞embedding到一個vector space，用低維度來表示每個詞，使得語意相關的詞距離會更近

##### Skip-gram
- 給定中心詞，預測上下文
- 由上下文跟中心詞構成的單詞稱為正樣本，而非上下文跟中心詞構成的單詞稱作是負樣本
- 要正確的根據中心詞預測上下文就是去最大化正樣本的頻率，最小化負樣本，這就是他的目標函數，也可以理解成是要增大中心詞與上下文詞的內積

- 構建正負樣本並最大化正樣本的相似度、最小化負樣本的方式是表示學習中建構損失函數的一種常見方式，稱為**對比損失(Contrastive loss)**

## Chapter 5. 圖信號處理與圖卷積網路
---
- 圖卷積的本質是信號處理
- 圖本身具有三種特徵: 節點屬性和標籤、節點間的關係、邊上權重
### 5.2 圖信號與拉普拉斯矩陣
- 圖信號指的是每一個節點上對應的信號強度，同時也具有拓樸關係。定義上來看是vertex set映射到實數域當中，代表節點上的信號強度
- 映射出來的矩陣用X表示，其屬性為 $X∈R^{n*f}$ ，代表有n個節點，每個節點有f個通道數
- 拉普拉斯矩陣式用來研究圖結構的核心對象，定義為**L=D-A**，D是對角矩陣，其數值為該點的degree，A為鄰接矩陣，意即**拉普拉斯矩陣為degree矩陣減去鄰接矩陣**。所以L在對角線上會是該點的degree，然後-1代表該點有邊存在，0則是都沒有
如此定義出來的拉普拉斯矩陣為**實對稱半正定矩陣**，因此可以做eigen decomposition，寫成以下形式

- Symmetric normalized laplacian:
正則化的拉普拉斯矩陣，定義為$D^{-1/2}LD^{-1/2}$，在這種情況下i=j的地方為1(主對角線為1)，有邊的地方會是-1/(兩頂點degree相乘再開根號)，都沒有的依然為0
- 拉普拉斯算子，可以用來描述中心節點與鄰節點間的信號差異
- [拉普拉斯矩陣介紹](https://zhuanlan.zhihu.com/p/85287578)
- Total Variance
刻劃的是圖的平滑度，total variance越小，圖信號就越平滑

### 5.3 圖傅立葉轉換
將圖信號從空域(spatial domain)轉到頻域(frequency domain)

#### 以訊號波來理解空/頻域的話:
時域為訊號隨時間的變化，而頻域則是只個別的頻率波(以最大的振福來標示)

- 傅立葉轉換在函數上的意義為函數的內積，將函數投影到某個頻率所在的頻域中

- 圖傅立葉變換，稱特徵向量為傅立葉基，算出的結果是傅立業係數，本質上是圖信號在傅立葉基上的投影，衡量了圖信號與傅立葉基之間的相似度

- 把拉普拉斯矩陣的特徵值看成了頻率，將圖信號投影到了對應的特徵向量(傅立葉基)，而結果會是傅立葉係數。這個轉換的過程就叫做圖傅立葉轉換(看參考資料)

#### 圖濾波
仿照信號卷積的模式定義圖的卷積，由傅立葉基乘上對應頻率的響應函數以及圖信號在該頻率上的投影強度，接著求和

定義圖濾波器為，a.k.a. H的頻率響應矩陣，實際上是作用在拉普拉斯矩陣特徵值上的函數，利用一的是頻率響應函數來在調整不同頻率(特徵值)上分量的強度

- Graph Shift Operator(圖位移運算子)

### 圖卷積
卷積操作在泛函中代表的是兩個函數互相運算產生第三個函數，將其離散化並套用在歐式空間的話，則可以是CNN那種用卷積核對某一區塊運算的方式
但圖的結構不規則，屬於非歐式空間，不能直接用

#### 頻譜(spectral)
為了改善上述問題，有人提出用拉普拉斯矩陣特徵值作為基底，將其投影到頻域上做卷積
- 當兩組圖信號x1、x2要做卷積時，原始定義為兩組圖信號各自做圖傅立葉轉換後做element-wise相乘，再將這個結果做逆圖傅立葉轉換
- 經過一些推導可以在這個運算寫成某個濾波器乘上x2的形式，等於是對x2做圖濾波操作，所以圖卷積在此可以等價於圖濾波
- 又前面說過H可以分解出頻率響應矩陣，所以想要做的事情就是把這個矩陣參數化拿來學習


因此可以設計出上述的卷積層，theta是一個learnable的參數及圖濾波器
- 第一個等號(有diag的那個)代表的是頻域視角，$U^TX$是做一次傅立葉轉換，用diag調整分量大小，再用U去做逆傅立葉轉換
- 而第二個等號則是空域的視角，直接對圖信號矩陣X乘上一個learnable的graph shift operator

但這個做法需要eigen decomposition和傅立葉轉換，計算量很大。而且在節點很大的時候參數量同時也會很大，因為大部分有用的資訊都在低頻區域，所以等同於多訓練了很多不必要的參數
#### 多項式近似圖卷積
為了改善上述問題，將卷積操作改為某個節點K階子圖所有節點的信號加權總和
(證明看reference)
大意上是用拉普拉斯矩陣的多項式函數去逼近任意的濾波器

#### 切比雪夫多項式
用這個多項式去處理卷積操作，將特徵值縮放範圍限制在[-1,1]當中，可以避免信號在經過幾次迭代後被指數放大
- [-1,1] 的緣故可以看中間的那個式子，減號左邊經過縮放範圍落在[0,1]，而減去單位矩陣後就是[-1,1]了
總之好像是可以寫成這個樣子(詳細參考reference)
讓濾波操作的時間複雜度變成O(K|E|)，a.k.a.線性時間

- 好像可以延伸去ChebNet (?)

#### 重歸一化(Renormalization)

### Reference
[圖卷積網路原理](https://zhuanlan.zhihu.com/p/290755442)
[傅立葉變換](https://zhuanlan.zhihu.com/p/292935670)
[圖濾波器](https://zhuanlan.zhihu.com/p/297613044)

### 圖卷積的實現
#### 通式
#### Method 1
，其中$W^l$是第L層的權重矩陣，H為特徵矩陣，這個算式等價於在把某節點的鄰居相加之後再乘上權重參數，然套用非線性函數
但問題是這樣**沒有考慮到節點自身的影響**，**鄰接矩陣沒有經過Normalization，可能也會導致讓鄰居較多的節點有較大的影響力**
#### Method 2
第二種方式的改進方式是用拉普拉矩陣取代原本的鄰接矩陣，好處就是能把自身的degree一起考慮進去
#### Method 3
第三種方式類似於第二種，但使用的拉普拉斯矩陣為Symmetric normalized Laplacian，除了引入自身degree之外更是，把鄰接矩陣給normalize了
(對矩陣normalize的意思有點像是對每個節點去除以他的degree)

雖然方法都是case by case，但主流還是以method 3為優先嘗試
- Forward from [知乎: 圖卷積](https://zhuanlan.zhihu.com/p/89503068)

## Chapter 6. GCN的性質
---
- 本質上都是聚合節點鄰居的訊息
- 可以將圖像視為一種結構化的graph，一個filter遮到的地方等價於自己的鄰居;而GCN則是在處理非結構化的圖數據
- GCN處理卷積的方式是將一個節點和周圍的其他幾個鄰節點聚合起來形成新一階的單一節點
- GCN中的卷積核同樣也是共用的

### 6.2 端對端學習 in GCN
- 圖的訊息包含屬性訊息和結構訊息。屬性訊息就是object本身的固有性質，結構訊息則是object之間的交互影響
- 以$L_{sym}XW$來說，XW是在做屬性訊息的映射變換，學習特徵之間的交互模式。$L_{sym}(XW)$的過程則是聚合鄰居節點的過程
- Weisfeiler-Lehman Algorithm: 跌代聚合鄰節點
- GCN類似於一種帶有參數，支持自動微分的Weisfeiler-Lehman Algorithm，透過堆疊卷積層，能夠不斷交替屬性訊息跟結構訊息的編碼學習，因為這兩種不同訊息彼此間有互補關係，這樣同時學習會更好的影響最終結果

### 6.3 低通濾波器
從$L_{sym}$跟XW的相乘就能起到和低通濾波器相同的效果
意即GCN相當於對輸入信號做一個低通濾波的操作=>讓信號更加平滑
牽扯到拉普拉斯矩陣跟頻率響應函數
再研究看看

### 6.4 GCN的過平滑(over-smooth)
就圖信號來看，矩陣乘法到最後會讓信號處處相等
而從空域角度來看，隨著層數越多，每一層單一節點聚合的鄰節點就越多，到最後就包含每個節點因而失去了結構性

- 可以通過跳躍式連結改善這個問題，或者是改善濾波器的值

## Chapter 7. GNN的變體與框架
---
### 7.1 GraphSAGE
#### 採樣
- 透過採樣鄰節點將其改造成以節點為中心的小批量訓練方式，在原始的GCN模型中無法達成小批量更新
- 採樣是以隨機採樣的方式去控制節點的規模
- 現實中的圖數據通常都會存在幾個degree很大的超級節點，對於遍歷節點來說會有很大的cost
- 具體作法是設置一個超參數 **${S_k}$**，代表在第K層的鄰居採樣率，即每個節點採樣的一階鄰居總數不超過 ${S_k}$

#### 聚合
- 無論節點的鄰居數量怎麼變化，進行聚合操作後輸出的維度必須是一致的
- 由於圖數據本身就是一種無序的資料結構，所以不管鄰居節點怎麼排，最後輸出的結果必須要是一樣的
- 符合上述要求的運算子有: 平均/求和、池化(pooling)
- Flow:

- GraphSAGE的特徵學習過程只和其K階鄰居有關，不需要用到拉普拉斯矩陣
- 這樣的學習方法稱作**歸納學習(Inductive Learning)**，可以對訓練階段見不到的數據直接預測而不用重新訓練，對於新出現的節點數據只需要重新遍歷得到K階子圖就可以代入模型進行預測。
簡單來說歸納學習就是測試集沒有包含在訓練集當中
- 反之為**轉導(Tranductive Learning)**，指的是所有數據都在訓練階段都能取得，學習過程是建立在這個固定的數據上，一旦數據發生變化，就必須重新訓練模型
意思就是他測試的數據被包含在訓練集當中，但是是unlabel的

### 7.2 GAT(Graph Attention Network)
- 通過注意力機制來對鄰節點聚合

#### 注意力機制
以人類來比擬就是我們會關注重點部位而不是全局，以達到更快且更準確地辨別
=> 注意力的核心機制在於對給定訊息的權重分配

實際的定義為: **Attention(Query,source)= Σ similarity(Query,$Key_i$) * value**
大致上就是對所有value的訊息加權求和，權重為query跟similarity的相似度，最直接的方法就是取內積

#### 圖注意層(Graph Attention Layer)
- Query: 中心節點的特徵向量；Source: 鄰居節點的特徵向量
Attention value: 中心節點聚合過後新的特徵向量
- 這一層的計算為計算兩節點的相似度並取leaky relu之後，用softmax做normalization之後可得注意力的加權，再和原始的特徵向量做加權求和就能得到新一層的output

#### Multi-Head Attention
- 對上面的計算調用K組相互獨立的注意力機制，再將輸出結果拼接在一起
- 比起GCN多了一個自適應的邊權重係數(邊上的權重係數)，在GCN時這個部分是拉普拉斯矩陣，而這裡則是可以自適應學習的矩陣

### 7.3 RGCN
考慮的是異構圖，處理鄰居的時候會考量不同關係將鄰居分類，套用不同的權重之後分群進行聚合，最後在合起來一起看

#### Basic Decomposition
- 若為每種關係都設一種權重，那常見跟不常見的關係要學習的參數數量差距很大，會造成過擬合的風險，於是對權重提出基分解
- 會需要一個分解係數和一個超參數控制基的數量，可以將權重矩陣寫成一個線性組合

### GNN的通用框架
指的是對各種框架一般化的總結

#### 1. Message Passing Neural Network (消息傳播網路)
- 節點的表示向量都是通過消息函數和更新函數進行k輪消息傳播機制的跌代後產生的
- 利用消息函數做聚合，再用更新函數對節點特徵進行更新

#### 2. Non-Local Neural Network (非局部神經網路)
- 對注意力機制的一般化總結，將任意位置的輸出響應計算為所有位置特徵的加權和
- 操作為計算任意兩位置節點的相關係數乘上轉換過的輸入並進行加總後，歸一化即可得到新的輸出
- 相關係數的計算可以用**內積、全連接、高斯函數**等

#### 3. Graph Network (圖網路)
- 由點更新邊，邊聚合更新點，點聚合與邊聚合再更新圖
- 每個元素在更新時還需要考慮自身上一輪的狀態

## Chapter 8. 圖分類
---
- 因為graph不規則的結構，要直接實作像是CNN那種是有些困難的

### 8.1 基於全局池化的圖分類
- Readout: 對經過K次迭代的所有節點做一次性的聚合操作，從而輸出圖的全局表示
- 本質上是將輸入數據當作是一種平整且規則的數據

### 8.2 基於層次化池化的圖分類
#### 1. 基於圖塌縮(graph coarsening)
將子圖視為一個超級節點，形成一個塌縮的圖
##### 圖塌縮
$Γ^j$表示子圖中的節點列表
- 定義簇分配矩陣: $S∈R^{N*K}$，$S_{ij} = 1$ iff $v_i∈Γ^j$
考慮$S^TAS$的計算，得到的結果代表的是超級節點之間的連接強度，令其為$A_{coar}$，則$A_{ij}$表示第i個簇跟第j個簇之間的連接強度

- 定義採樣算子$C∈R^{N*N_k}$，$C^{k}_{ij} = 1$ iff $Γ_{k}^j = v_i$，可以用這個算式算出子圖的鄰接矩陣(看書上推導)
##### DiffPool
先用一個GNN對每個節點做特徵學習，再用另一個GNN學習屬於各個簇的機率分布
總之是可以不斷堆疊GCN層跟diffpool層，實現一種可微分(可導)、層式化池化的學習機制，並逐漸獲得圖的全局表示
- 節點以機率的形式被分配到不同的簇
##### Eigen Pooling
同樣基於圖塌縮，但沒有在圖分類模型中引入可學習的參數，所以用的是傳統像是k-means之類的方法直接分配到一個簇
在劃分完之後，eigen pooling採取的方式用子圖的信號在該子圖上的圖傅立葉變換來表示結構訊息和屬性訊息的整合輸出

主要優勢在於保持了超級節點之間的稀疏性，增加計算效率，同時在進行卷積操作時也能兼顧子圖內的結構和屬性訊息

#### 2. 基於TopK的池化機制
每個節點會學習出一個分數，最後要丟掉分數比較低的點，篩選出更重要的訊息
會設置一個表示池化率的超參數k，接著學習一個表示節點重要度的值並排序，採樣成原始的K倍(k在0,1之間)
#### 3. 基於邊收縮(edge contraction)的池化機制
將邊移除掉，邊連接的兩點合併在一起並保留連接關係
對於該如何選擇每個節點該歸屬的邊，這裡設計了一種評分方式，可以給每條邊一個分數
優點是節點的融合保留了圖原始的結構訊息以及圖連接的稀疏性，降低空間複雜度

## Chapter 9. 基於GNN的圖表示學習
### 9.1 圖表示學習
首先要提到Graph embedding，屬於表示學習的一個範疇:
- 主要目標是將圖數據轉為低維稠密的向量表示，同時確保圖數據的性質在向量空間中也能被對應
- 將圖數據表示呈線性空間中的向量有助於提高計算的效率

傳統表示圖的方法是利用矩陣分解，將節點轉到低維空間中同時保留結構性，但時空間複雜度都很高
另一種方式是用像是隨機遊走的方式，將結點跟邊以詞語的形式表達出來，雖然計算方便且有現成模型的成功範例，但無法妥善利用圖本身的結構訊息

### 9.2 以GNN為圖表示學習
- 融合圖的屬性訊息、能遷入到任一支持端對端學習的系統、支持歸納學習、能適應大規模圖
除了原本的監督式學習之外，GNN與相應對的損失函數結合之後就能實現無監督式學習

#### 基於重構損失的GNN
定義一個圖自編碼器(Graph Autoencoder)，類似原本的自編碼器，還要再加上約束項防止過擬合
有另一個想法是變分圖自編碼器(Variational Graph Autoencoder)，包含了推斷模型、生成模型、損失函數

#### 基於對比損失的GNN
設置一個評分函數，提高真實(正)樣本的評分並降低假(負)樣本的評分
以詞向量的概念為基礎，可以分成幾個case:
##### 1. 鄰居作為上下文
透過像是隨機遊走的方式把跟中心節點一起出現在固定視窗的節點視為鄰居，把不符合關係的視為是負樣本
強調的是節點之間的共現關係，反映的是節點間的距離遠近，缺乏對節點結構相似性的捕捉，但通常節點局部結構的相似性會是圖分類的一個關鍵因素
##### 2. 子圖視為上下文
總之就是用子圖取代節點的感覺
對於一個中心節點，會先用GNN在其K階子圖上提取表示向量，而上下文則用處在r1-hop和r2-hop之間的節點定義，同樣也用GNN提取每個的表示向量
##### 3. 全圖做為上下文
- Deep Graph Infomax

為了得到圖的全局表示，用讀出機制對局部節點的訊息作聚合

## Chapter.10 GNN的應用
---
GNN有三個優勢:
1. 具有強大的數據擬合能力，常常被利用去擬合研究對象的一些理化性質，從而指導或加速相應的科研與研發工作
2. 具有強大的推理能力，能夠對表徵語意關係的的網路做整體的建模，學到更加複雜與豐富的語意訊息。譬如說有些問題中不直接包含答案內容，需要透過學習系統經過推理將問題中的事實關係映射到答案實體上
3. 與知識圖譜結合，將先驗知識以端對端的形式高效的嵌入到學習系統當中
### 10.2 應用
#### 3D視覺
基於深度學習在2D視覺上的成功，想要將其延伸至3D視覺上
- 點雲數據(Point Cloud):
由一組點組成，除了三維座標之外還可以記錄很多東西，像是點的顏色或強度等資料
- 理解方式: 分類(給定點，算出是哪一類)、語意分割(把一個物件分割成小部分的感覺)、場景分析(在一個大場景之內分類出不同物件)

因為不具有結構性所以卷積網路無法順利地套用，如果像是**將點雲強制轉成和圖像類似的三維規則結構**或是**轉為多視覺圖(multi-view Images)進行圖像處理後再投影回原始的點雲數據**，但缺點在於會造成信息的丟失或數據的冗餘
透過GNN的技術解決這個問題。如何定義鄰接關係是這個技術的其中一個關鍵，確認之後緊接著就是實現積於鄰接邊的圖卷積
- refer to: PointNet++、Edge-Conv、PCNN

#### 基於社交網路的推薦系統
- refer to: DGRec model
用戶受到的影響因素很多，甚至整體都是動態變化的
以上面提到的model為例，需要四個部分:
1. RNN(循環神經網路): 用來建模用戶的動態興趣偏好
2. 興趣是由長期跟短期的偏好組成，長期是反映用戶穩定的興趣偏好，可以用embedding的方式做；短期的話則是近期的興趣飄移，可以用RNN建模近期消費的項目序列
3. GAT(圖注意網路): 用來建模用戶跟朋友興趣間的交互關係，甚至可以用到雙圖注意力網路把物品間的相互關係也考慮進來
4. 下一步的行為由動態興趣偏好和社交網路影響綜合決定

#### 視覺推理
用GNN融合空間訊息和語義訊息 => 局部推理 + 全局推理

### 10.3 展望
1. 適應複雜多變的圖數據
2. 在更多推理任務上的研究改進
3. 對超大規模圖建模的支持