GCN相關(guān)算法

1. GCN

1.1 Laplace算子

Laplace算子\nabla^2特征函數(shù)e^{-jwt} -> Fourier變換F(w) = \int_Rf(t)e^{-jwt}dt -> 卷積f*g=\mathcal{F}^{-1}(\mathcal{F}(f)\mathcal{F}(g) )

Laplace矩陣L的特征向量 -> Fourier變換 -> 卷積

1.1.1 Laplace算子的特征空間

由變換A的廣義特征方程Ax=\lambda x解得Laplace算子\nabla^2特征函數(shù)為e^{-jwt}。

于是變換\nabla^2在e^{-jwt}張成的特征空間中的變換是簡單的拉伸變換。

將函數(shù)f(t)看做無窮維的向量，則映射到該特征空間的過程就是Fourier變換F(w) = \int_Rf(t)e^{-jwt}dt。

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=e%5E%7B-jwt%7D" alt="e^{-jwt}" mathimg="1">對w的正交性，不同F(w)將f(t)投影到不同的基上，從而得到每個(gè)w對應(yīng)的投影值。

1.1.2 卷積公式

因?yàn)橄韧屏四孀儞Q，e^{jwt}的組合，所以正變換加了個(gè)負(fù)號。

時(shí)移性質(zhì)：時(shí)移-相移，頻率成分不變、大小不變，但是相位移動。
F(f(t-t_0)) = \int_Rf(t-t_0)e^{-jwt}dt = \int_Rf(x)e^{-jw(x+t_0)}dx = F(w)e^{-jwt_0}
卷積公式：
\begin{aligned} F(f_1(\tau)*f_2(\tau)) &= \int_R \left[\int_Rf_1(\tau)f_2(t-\tau)d\tau \right] e^{-jwt}dt \\ &= \int_R f_1(\tau) \left[\int_Rf_2(t-\tau)e^{-jwt}dt \right] d\tau \\ &= \int_R f_1(\tau) F(f_2(t))e^{-jw\tau} d\tau \\ &= F(f_1)F(f_2) \end{aligned}

于是Laplace算子的特征空間中有卷積公式成立。這里主要用到指數(shù)函數(shù)f(a)f(b)=f(a+b)的性質(zhì)。

事實(shí)上，只要特征函數(shù)具有正交和指數(shù)形式，卷積公式就可以成立。于是想到構(gòu)造一個(gè)二階微分算子，把卷積推廣到圖上。

1.2 矩陣Laplace推廣

Laplace算子是一個(gè)二階梯度，本質(zhì)上是計(jì)算變化率的變化率，而對應(yīng)到圖上的物理意義可以是熱量變化的平滑程度。

熱量變化應(yīng)該與熱量差正相關(guān)，如一維情況
\frac{\partial \phi}{\partial t} = k[(\phi_{i+1}-\phi_i) - (\phi_i-\phi_{i-1})] = k \nabla^2 \phi
多維情況同理。下面推廣到圖上。對于節(jié)點(diǎn)i，有
\begin{aligned} \frac{\partial \phi_i}{\partial t} &= -k\sum_{j} A_{ij}(\phi_i-\phi_j) \\ &= -k\cdot deg(i)\phi_i + k\sum_j A_{ij}\phi_j \\ \frac{\partial \phi}{\partial t} &= -kD\phi+kA\phi = -k(D-A)\phi \\ &= -kL\phi \end{aligned}
其中D是對角線為度的矩陣。定義L=D-A為Laplace矩陣。

于是對L進(jìn)行特征分解：
L = U \begin{pmatrix} \lambda_1 & & &\\ & \lambda_2 & &\\ & & \cdots &\\ & & & \lambda_n \end{pmatrix} U^T
其中U的每一行為一個(gè)\lambda對應(yīng)的特征向量。

仿照傅里葉變換，有
\hat{f}(\lambda_l) = \langle u_l, f \rangle = \sum_i^n f(i)\overline{u_l(i)} \\ F(f) = U^Tf
其中f(i)為節(jié)點(diǎn)i對應(yīng)的Embedding值。

于是整個(gè)卷積過程，可以描述為：
g*f = U(U^Tg\odot U^Tf) \\ g*f = U \begin{pmatrix} \hat{g}(\lambda_1) & & \\ & \cdots & \\ & & \hat{g}(\lambda_n) \end{pmatrix} U^Tf
其中g為卷積核，f為各個(gè)節(jié)點(diǎn)的Embeding。

1.3 卷積核

1.3.1 樸素法

直接將\hat{g}(\lambda_i)看作參數(shù)進(jìn)行訓(xùn)練，即變換后的卷積核為：
g_\theta(\Lambda) =\begin{pmatrix} \hat{g}(\lambda_1) & & \\ & \cdots & \\ & & \hat{g}(\lambda_n) \end{pmatrix} = \begin{pmatrix} \theta_1 & & \\ & \cdots & \\ & & \theta_n \end{pmatrix}
參數(shù)過多，計(jì)算量過大。

1.3.2 多項(xiàng)式近似法

\hat{g}(\lambda_i) = \sum_j^Ka_j\lambda_i^j
從而有
g_\theta(\Lambda) =\begin{pmatrix} \hat{g}(\lambda_1) & & \\ & \cdots & \\ & & \hat{g}(\lambda_n) \end{pmatrix} = \sum_j^K a_j \Lambda^j
y_{out} = \sigma(Ug_\theta(\Lambda)U^Tx) = \sigma(\sum_j^K a_j U\Lambda^jU^Tx)= \sigma(\sum_j^Ka_jL^jx)
減少了參數(shù)，引入了局部性，不需要分解。但求解L^j仍然需要O(n^3)復(fù)雜度。

1.3.3 Chebyshev多項(xiàng)式近似卷積核

Chebyshev多項(xiàng)式就是余弦倍角展開公式，形式如下：
T_n(\cos(\theta)) = \cos(n\theta) \\ T_n(x) = cos(n \arccos(x)) \quad x \in [-1,1] \\ \begin{cases} T_0(x) = 1 \\ T_1(x) = x \\ T_k = 2T_{k-1} - T_{k-2} \end{cases}
則，變換后的卷積核為：
g_\theta(\Lambda) = \sum_i^K \theta_iT_i(\tilde\Lambda) \\ \tilde\Lambda = \frac{2\Lambda}{\lambda_{\max}}-I

可以用歸納法證明：
y_{out} = \sigma(Ug_\theta(\Lambda)U^Tx) = \sigma(\sum_j^K \theta_j U T_j(\tilde \Lambda) U^T) = \sigma(\sum_j^K \theta_jT_j(\tilde L)x)

于是，Cheby遞推的方式實(shí)現(xiàn)高階效果，計(jì)算T_i(\tilde\Lambda)的復(fù)雜度為O(n^2)。

1.3.4 GCN

對Cheby核做限制：K=1, \lambda_{\max}=2，則
Ug_\theta(\Lambda)U^Tx = \sum_{i=0}^1\theta_iT_i(\tilde\Lambda)x = \theta_0x-\theta_1(L-I)x
進(jìn)一步，限制\theta = \theta_0=-\theta_1，可得
Ug_\theta(\Lambda)U^Tx = \theta Lx = \theta (I+D^{-1/2}AD^{-1/2})x
因多層I+D^{-1/2}AD^{-1/2}的乘積會導(dǎo)致方差偏移，數(shù)值不穩(wěn)定，故需要重新進(jìn)行正則化：
\tilde A = A+I \\ \tilde D_{ii} = \sum_j A_{ij} \\ I+D^{-1/2}AD^{-1/2} \to \tilde D^{-1/2}\tilde A \tilde D^{-1/2}
于是，最終的GCN卷積層為：
Y = \sigma(\tilde D^{-1/2}\tilde A \tilde D^{-1/2} X\Theta)
其中節(jié)點(diǎn)特征是C維的，即X \in R^{N \times C}；\Theta \in R^{C \times F}是F維濾波器，Y \in R^{N \times F}為卷積結(jié)果。

理論十分復(fù)雜，但形式卻十分簡單。

GraphSAGE

GCN是transductive，訓(xùn)練時(shí)需要把全圖結(jié)構(gòu)和特征都讀入，無法大規(guī)模訓(xùn)練。

GraphSAGE是inductive，訓(xùn)練時(shí)只使用樣本點(diǎn)局部的特征與結(jié)構(gòu)即可，通過采樣限制數(shù)據(jù)結(jié)構(gòu)不均衡?；静襟E如下：

  1. 采樣：均等采樣，指定采樣鄰居數(shù)量
  2. 聚合：效果最好的是均值聚合器，即對鄰居embedding取均值，GCN其實(shí)是求和
    h_v^k \leftarrow \sigma(W \cdot aggregate(\{h_v^{k-1}\}U\{h_u^{k-1},\forall{u}\in \mathcal{N}(v)\}))
  3. 更新參數(shù)

GraphSAGE和GCN其實(shí)都是復(fù)雜網(wǎng)絡(luò)中的一個(gè)層。設(shè)計(jì)復(fù)雜網(wǎng)絡(luò)時(shí)，要考慮Loss函數(shù)。對于有監(jiān)督可以直接用交叉熵。對于無監(jiān)督，假設(shè)相鄰節(jié)點(diǎn)embedding盡量相同，則Loss函數(shù)為
L_\mathcal{G} = -\ln(\sigma(h_u^Th_v))-Q\mathbb{E}_{v_n \sim P_n(v)}\ln(\sigma(-h_u^Th_{v_n}))
其中P_n為負(fù)采樣分布，Q是負(fù)樣本個(gè)數(shù)，h是相應(yīng)節(jié)點(diǎn)的embedding。

GraphSage步驟.jpg

GAT

相比graphSAGE，增加了注意力機(jī)制，即按照一定權(quán)重聚合鄰居傳來的embedding。

鄰居節(jié)點(diǎn)u的權(quán)重計(jì)算通常使用中心節(jié)點(diǎn)v和u的屬性相似度表示，并使用softmax進(jìn)行歸一化。如使用余弦相似度：
\alpha_{0,j} = \frac{\exp(\beta\cos(Wx_0,Wx_j))}{\sum_{k\in \mathcal{N}(v_0)}\exp(\beta\cos(Wx_0,Wx_k)) }
其中\beta類似于一種bias。

而GAT實(shí)際使用
\alpha_{0,j} = \frac{\exp(LeakyReLU(a[Wx_0||Wx_j]))}{\sum_{k\in \mathcal{N}(v_0)}\exp(LeakyReLU(a[Wx_0||Wx_k]))}
是一個(gè)非對稱的注意力系數(shù)，就像條件概率一樣。使用參數(shù)a自動學(xué)習(xí)一個(gè)相似度函數(shù)。這里增加激活函數(shù)是為了避免softmax函數(shù)約去Wx_0項(xiàng)。

這種計(jì)算相似度的加法模式，本質(zhì)上兩節(jié)點(diǎn)的計(jì)算是分離的。每一層的參數(shù)a和W是相同的，于是每個(gè)節(jié)點(diǎn)有一個(gè)特定的能量值，如果這個(gè)值很高，就跟其他所有節(jié)點(diǎn)都比較相似，具體相似程度要加上其他節(jié)點(diǎn)的這個(gè)值。
\vec{a}(\vec{x}||\vec{y})=\vec{a_1}\vec{x}+\vec{a_2}\vec{y} = V_x + V_y
有種贏者通吃的感覺，幸福的家庭都是一樣的，不幸的家庭卻各有各的不幸。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容