美文网首页
GCN相关算法

GCN相关算法

作者: 热爱生活的大川 | 来源:发表于2021-12-02 16:46 被阅读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，训练时只使用样本点局部的特征与结构即可，通过采样限制数据结构不均衡。基本步骤如下：

  1. 采样：均等采样，指定采样邻居数量
  2. 聚合：效果最好的是均值聚合器，即对邻居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)\}))
  3. 更新参数

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
有种赢者通吃的感觉，幸福的家庭都是一样的，不幸的家庭却各有各的不幸。

相关文章

网友评论

      本文标题：GCN相关算法

      本文链接：https://www.haomeiwen.com/subject/lyzyxrtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|GCN相关算法|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！