GCN相关算法

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^2e^{-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的权重计算通常使用中心节点vu的属性相似度表示,并使用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项。

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

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343

推荐阅读更多精彩内容