GCN相关算法

2021-12-02 本文已影响0人热爱生活的大川

1. GCN

1.1 Laplace算子

Laplace算子 $\nabla^2$ 特征函数 $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$ 特征函数为 $e^{-jwt}$ 。

于是变换 $\nabla^2$ 在 $e^{-jwt}$ 张成的特征空间中的变换是简单的拉伸变换。

将函数 $f(t)$ 看做无穷维的向量，则映射到该特征空间的过程就是Fourier变换 $F(w) = \int_Rf(t)e^{-jwt}dt$ 。

因为 $e^{-jwt}$ 对 $w$ 的正交性，不同 $F(w)$ 将 $f(t)$ 投影到不同的基上，从而得到每个 $w$ 对应的投影值。

1.1.2 卷积公式

因为先推了逆变换， $e^{jwt}$ 的组合，所以正变换加了个负号。

时移性质：时移-相移，频率成分不变、大小不变，但是相位移动。
$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算子的特征空间中有卷积公式成立。这里主要用到指数函数 $f(a)f(b)=f(a+b)$ 的性质。

事实上，只要特征函数具有正交和指数形式，卷积公式就可以成立。于是想到构造一个二阶微分算子，把卷积推广到图上。

1.2 矩阵Laplace推广

Laplace算子是一个二阶梯度，本质上是计算变化率的变化率，而对应到图上的物理意义可以是热量变化的平滑程度。

热量变化应该与热量差正相关，如一维情况
$\frac{\partial \phi}{\partial t} = k[(\phi_{i+1}-\phi_i) - (\phi_i-\phi_{i-1})] = k \nabla^2 \phi$
多维情况同理。下面推广到图上。对于节点 $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$ 进行特征分解：
$L = U \begin{pmatrix} \lambda_1 & & &\\ & \lambda_2 & &\\ & & \cdots &\\ & & & \lambda_n \end{pmatrix} U^T$
其中 $U$ 的每一行为一个 $\lambda$ 对应的特征向量。

仿照傅里叶变换，有
$\hat{f}(\lambda_l) = \langle u_l, f \rangle = \sum_i^n f(i)\overline{u_l(i)} \\ F(f) = U^Tf$
其中 $f(i)$ 为节点 $i$ 对应的Embedding值。

于是整个卷积过程，可以描述为：
$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$ 为各个节点的Embeding。

1.3 卷积核

1.3.1 朴素法

直接将 $\hat{g}(\lambda_i)$ 看作参数进行训练，即变换后的卷积核为：
$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}$
参数过多，计算量过大。

1.3.2 多项式近似法

$\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)$
减少了参数，引入了局部性，不需要分解。但求解 $L^j$ 仍然需要 $O(n^3)$ 复杂度。

1.3.3 Chebyshev多项式近似卷积核

Chebyshev多项式就是余弦倍角展开公式，形式如下：
$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递推的方式实现高阶效果，计算 $T_i(\tilde\Lambda)$ 的复杂度为 $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$
进一步，限制 $\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}$ 的乘积会导致方差偏移，数值不稳定，故需要重新进行正则化：
$\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)$
其中节点特征是 $C$ 维的，即 $X \in R^{N \times C}$ ； $\Theta \in R^{C \times F}$ 是 $F$ 维滤波器， $Y \in R^{N \times F}$ 为卷积结果。

理论十分复杂，但形式却十分简单。

GraphSAGE

GCN是transductive，训练时需要把全图结构和特征都读入，无法大规模训练。

GraphSAGE是inductive，训练时只使用样本点局部的特征与结构即可，通过采样限制数据结构不均衡。基本步骤如下：

采样：均等采样，指定采样邻居数量
聚合：效果最好的是均值聚合器，即对邻居embedding取均值，GCN其实是求和
$h_v^k \leftarrow \sigma(W \cdot aggregate(\{h_v^{k-1}\}U\{h_u^{k-1},\forall{u}\in \mathcal{N}(v)\}))$
更新参数

GraphSAGE和GCN其实都是复杂网络中的一个层。设计复杂网络时，要考虑Loss函数。对于有监督可以直接用交叉熵。对于无监督，假设相邻节点embedding尽量相同，则Loss函数为
$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$ 为负采样分布， $Q$ 是负样本个数， $h$ 是相应节点的embedding。

GraphSage步骤.jpg

GAT

相比graphSAGE，增加了注意力机制，即按照一定权重聚合邻居传来的embedding。

邻居节点 $u$ 的权重计算通常使用中心节点 $v$ 和 $u$ 的属性相似度表示，并使用softmax进行归一化。如使用余弦相似度：
$\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实际使用
$\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]))}$
是一个非对称的注意力系数，就像条件概率一样。使用参数 $a$ 自动学习一个相似度函数。这里增加激活函数是为了避免softmax函数约去 $Wx_0$ 项。

这种计算相似度的加法模式，本质上两节点的计算是分离的。每一层的参数 $a$ 和 $W$ 是相同的，于是每个节点有一个特定的能量值，如果这个值很高，就跟其他所有节点都比较相似，具体相似程度要加上其他节点的这个值。
$\vec{a}(\vec{x}||\vec{y})=\vec{a_1}\vec{x}+\vec{a_2}\vec{y} = V_x + V_y$
有种赢者通吃的感觉，幸福的家庭都是一样的，不幸的家庭却各有各的不幸。