圖神經網路(GNN)-6.圖卷機神經網路理論推導

作者：由 Junlu Ding 發表于書法時間：2021-12-04

知識點準備

圖卷機神經網路（GCN）理論推導主要使用到了線性代數、譜圖理論、傅立葉變換、切比雪夫多項式，譜圖理論（

Spectral Graph Theory

）可以看作是專門研究圖鄰接矩陣性質的方法論，其是線性代數的一個子分支，由於譜圖理論的內容過多，這裡只簡單介紹在推導GCN時使用到的知識點。另外，關於傅立葉變換（

Fourier Transform

）不在這裡進行介紹，關於傅立葉變換的核心理念在之後的章節單獨說明。

1、特徵向量（eigenvector）、特徵值（eigenvalue）

$A\tilde{x} = \lambda\tilde{x}$

若矩陣A滿足上面的等式，則

$\tilde{x}$

為矩陣A特徵向量，

$\lambda$

為矩陣A特徵值

2、實對稱矩陣（symmetric matrix）

實對稱矩陣A具有 n 個特徵值和 n 個特徵向量，且 n 個特徵向量相互正交，且具有如下性質

$A=U \Lambda U^{T}$

$I= UU^{T}$

其中

表示 n 個相互正交的特徵向量，

$\Lambda$

表示對角線元素為 n 個特徵值，其它元素都為0的的矩陣

3、半正定矩陣（positive semi-definite matrix）

所有特徵值都大於等於0的矩陣

4、矩陣二次型（quadratic form）

$\tilde{x}^{T}A\tilde{x}$

如上表達式叫做向量

$\tilde{x}$

相對於矩陣

的二次型

5、瑞利商（rayleigh quotient）

$\frac{\tilde{x}^{T}A\tilde{x}}{\tilde{x}^{T}\tilde{x}}$

如上表達式叫做向量

$\tilde{x}$

相對於矩陣

的rayleigh quotient，當向量

$\tilde{x}$

為矩陣

的特徵向量時，rayleigh quotient結果為向量

$\tilde{x}$

相對應的特徵值

6、拉普拉斯矩陣（laplacianmatrix）

$L_{sym} = D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$

矩陣

為拉普拉斯矩陣，其中D為圖的度矩陣，即對角線元素為各個節點的度，其餘元素都為0，矩陣

為圖的鄰接矩陣，

$L_{sym}$

為拉普拉斯矩陣實對稱陣，矩陣

和

$L_{sym}$

即是實對稱矩陣也是半正定矩陣，且

$L_{sym}$

的特徵值取值範圍是［0，2］，關於此結論的證明這裡不在介紹（利用了二次型和rayleigh quotient進行證明），。

7、切比雪夫多項式（chebyshev polynomials）

$T_{0}(x) = 1$

，

$T_{1}(x) = x$

，

$T_{n+1}=2xT_{n} - T_{n-1}(x)$

圖卷機與傅立葉變換的關係

說到卷機操作首先會想到image convolution即影象卷機操作，其主要用於提取image中各種不同層次的特徵，如下所示。

卷機操作每次會都會指定一個卷機核，然後按照不同步伐大小在image進行滑動計算，每一次的滑動計算不需要整個image的畫素都參與計算，而是選擇與卷機核當前位置重合的區域性畫素進行計算，即相當於每次對不同的區域性畫素進行一個類聚合操作。而當我們在graph上同樣想執行卷機操作的時候是比較困難的，因為graph的拓撲結構不像image的拓撲結構那麼規整，所有沒辦法給出一個大小合適的卷機核。這個時候為了讓圖能夠實現與image類似的卷機操作，需要藉助傅立葉變換原理，傅立葉變換的大致思想是將複雜問題對映到不同的域中從而使得問題在不同域中變得相對簡單，最典型的例子就是聲波去噪，一個複雜的聲波其實是有多個不同頻率的正弦波疊加而成，透過不同的域變化使得複雜聲波能夠分解成不同頻率的正弦波，然後根據頻率將噪音的正弦波去掉，最後透過逆變化將去掉噪音之後的正弦波進行合併即可實現聲波去噪。如下所示。