详解GCN原理-公式推导

GNN survey

convolution

如何graph domain 上做convolution 是最近最热门的研究方向。

总的来说有两种卷积的方法： Spectral and non-spectral (spatial)

spectral Network

通过对图的拉普拉斯矩阵做特征分解，将它定义在 傅里叶 domain上。

在深入解释之前，先看一些有关图的定义，以下都是针对无向图所做的说明

对于图$G$,可以用它其中的节点$V$ 和 边$E$来对他进行定义。

矩阵$A$是图的邻接矩阵，反应了节点之间有无连接。

$D$代表了图的度矩阵，表示了每个节点有多少个度，即有多少条边和它相连接，$D$为对角矩阵

$f$代表了一中映射，可以节点转换为信号。

当给了一张图：

• 我们有了它的邻接矩阵$A$和度矩阵$D$

• 计算拉普拉斯矩阵，其实很简单就是$D-A$:

• 然后对$L$做spectral decomposition ，又称特征分解。因为$L$是对称矩阵，所以可以得到以下的分解形式：
  L = U Λ U T L=U\Lambda\ U^T L=UΛ UT
  其中$\Lambda$是特征值的对角矩阵，$U$是一个由特征向量组成的向量。

  Λ = d i a g ( λ 0 , . . . , λ n − 1 ) , U = [ μ 0 , . . , μ n − 1 ] , 正 交 的 \Lambda=diag(\lambda_0,...,\lambda_{n-1}), U=[\mu_0,..,\mu_{n-1}],正交的 Λ=diag(λ0​,...,λn−1​),U=[μ0​,..,μn−1​],正交的。

• 假设 f = [ 4 , 2 , 4 , − 3 ] T f=[4,2,4,-3]^T f=[4,2,4,−3]T,我们来研究$Lf$代表了什么意思：
  $$Lf=(D-A)f=Df-Af$$
  

我们只关注于第一个结点 v 0 v_0 v0​，根据上图我们可以看到，结果 $a$就是结点 v 0 v_0 v0​和它的两个邻居结点 v 1 , v 2 v_1,v_2 v1​,v2​信号的差值。

• 那么就有下式的成立：

如果 f T L f f^TLf fTLf表示相邻结点之间能量的话，那么如果信号的频率越高，则相邻的两个信号之间的差值就越大，能量也就会越大。

• 而特征值$\lambda$,就是一种频率的反映

• Vertex domain 转换成 spectral domain

  给定一个图的结点的signal $x$,则经过傅里叶转换到频域上的 x ^ = U T x \hat x=U^Tx x^=UTx

其实就是乘上不同频率 $\lambda$上的特征值，得到这个信号在不同频率上的大小是多少：

• 怎么转换回去呢？spectral domain 转换成 Vertex domain

  就是将每一个频率下对应的信号，和对应特征向量中的值相乘：

右边一列是在不同特征值下的特征向量的分布情况，下面的那一行不同频率下的值。

现在我们知道了 vertex和spectral domain 互相转换的方法

**如果我们在spectral 转换成 vertex的时候，改变转换时乘上的参数，改成一个 g θ ( Λ ) g_\theta(\Lambda) gθ​(Λ) 一个关于$\theta 的函数$ ** 。

然后我们希望通过这个 g θ g_\theta gθ​转换成我们想要的label，那么这个过程就是可以通过神经网络进行训练的。

• 现在我们明确了我们想找的filter g θ ( Λ ) g_\theta(\Lambda) gθ​(Λ),使得：
  y ^ = g θ ( Λ ) x ^ \hat y=g_\theta(\Lambda) \hat x y^​=gθ​(Λ)x^

  ⇒ g θ ( Λ ) U T x \Rightarrow g_\theta(\Lambda) U^Tx ⇒gθ​(Λ)UTx

  两边同时成一个 U
  U y ^ = U g θ ( Λ ) U T X U\hat y=U g_\theta(\Lambda)U^TX Uy^​=Ugθ​(Λ)UTX
  合并一下：
  y = U y ^ = U g θ ( Λ ) U T X = g θ ( U Λ U T ) X = g θ ( L ) x y=U\hat y=U g_\theta(\Lambda)U^TX=g_\theta(U\Lambda U^T)X=g_\theta(L)x y=Uy^​=Ugθ​(Λ)UTX=gθ​(UΛUT)X=gθ​(L)x

• 上述的 g θ ( . ) g_\theta(.) gθ​(.)可以是任意的一个函数，比如:

根据泰勒展开式会有上述的形式，但是这样会出现一个问题1，就是学习的复杂度太高了：$O(n)$

还有另外一个问题2：

当 g θ = L 2 g_\theta=L^2 gθ​=L2的时候：

L 2 L^2 L2代表着与结点距离为2的邻居结点的信息， L n L^n Ln则代表着距离为n。如果当n越来越大，那么图中的每一个结点会和其他的所有结点相关，这个就违反了局部性 localized。

使用ChebNet去解决上述的两种问题

我们使用 一个可以被循环计算的多项式函数来拟合L

综上，GCN的最终形态会被写成：

参考
视频:https://www.youtube.com/watch?v=M9ht8vsVEw8&t=1913s
PPT:http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML2020/GNN.pdf

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！