search
github编辑

04-图信号处理与图卷积神经网络

图在生活无处不在，在各个方面体现着，比如社交网络，蛋白质结构等。现在开始学习图卷积神经网络。

hashtag
什么是Convolution？

Convolution的数学定义是：

(f∗g)(t)=∫Rf(x)g(t−x)dx(f*g)(t) = \int_R f(x)g(t-x)dx

一般称$g$为作用在$f$上的$filter$或$kernel$。

一维的卷积示意图如下：

img

常见的$CNN$二维卷积示意图如下：

img

这是一个简单的$3\times 3$卷积层，每个新特征的学习是这样的：对其领域（$3\times 3$局部空间）的特征进行变换（$w_ix_i$），然后求和（$\sum\limits_{i}w_ix_i$）。

在抽象的graph里面卷积该怎么表示？

img

比如这个社交网络抽象出来的graph里面，有的社交vip会关联上万的节点，这些节点没有空间上的位置关系，也就没办法通过上面给出的传统卷积公式进行计算。

hashtag
Fourier变换

为了解决graph上卷积计算的问题，引入Fourier变换。

  • 傅里叶级数表达式

设一个周期等于$T$，现定义区间为$[-\frac{T}{2},\frac{T}{2}]$的周期函数$f(x)$，傅里叶级数近似的表达式如下：

f(x)=C+∑n=1∞(ancos⁡(2πnTx)+bnsin⁡(2πnT)x)，其中C=a02f(x) = C + \sum\limits_{n=1}^{\infty}(a_n\cos(\frac{2\pi n}{T}x)+b_n\sin{(\frac{2\pi n}{T})}x)，其中C=\frac{a_0}{2}

利用偶函数$\times $奇函数$=$奇函数的性质可以得到如下：

an=∫−T2T2f(x)cos⁡(2πnTx)dx∫−T2T2cos⁡2(2πnTx)dx=T2∫−T2T2f(x)cos⁡(2πnTx)dxbn=∫−T2T2f(x)sin⁡(2πnTx)dx∫−T2T2sin⁡2(2πnTx)dx=T2∫−T2T2f(x)sin⁡(2πnTx)dx\begin{align} a_n &= \frac{\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cos{(\frac{2\pi n}{T}x)dx}}{\int_{-\frac{T}{2}}^{\frac{T}{2}}\cos^2{(\frac{2\pi n}{T}x)dx}} \\ &=\frac{T}{2}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\cos{(\frac{2\pi n}{T}x)dx} \\ b_n &= \frac{\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\sin{(\frac{2\pi n}{T}x)dx}}{\int_{-\frac{T}{2}}^{\frac{T}{2}}\sin^2{(\frac{2\pi n}{T}x)dx}} \\ &=\frac{T}{2}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(x)\sin{(\frac{2\pi n}{T}x)dx} \\ \end{align}

由欧拉公式$e^{ix}=\cos x + i\sin x$，可知：

cos⁡x=eix+e−ix2，sin⁡x=eix−e−ix2i=−i⋅eix−e−ix2\cos x = \frac{e^{ix}+e^{-ix}}{2}，\sin x = \frac{e^{ix}-e^{-ix}}{2i}=-i\cdot \frac{e^{ix}-e^{-ix}}{2}

将如上公式的$\cos ({\frac{2\pi n}{T}x})$和$\sin (\frac{2\pi n}{T}x)$的线性组合式改写如下：

abcos⁡(2πnTx)+bnsin⁡(2πnTx)=an(ei2πnTx+e−i2πnTx2)+bn(ei2πnTx−e−i2πnTx2i)=an−ibn2ei2πnTx+(an+ibn2e−i2πnTx)=cnei2πnTx+c−ne−i2πnTx\begin{align} a_b\cos (\frac{2\pi n}{T}x)+b_n\sin (\frac{2\pi n}{T}x) &= a_n(\frac{e^{i\frac{2\pi n}{T}x}+e^{-i\frac{2\pi n}{T}x}}{2}) +b_n(\frac{e^{i\frac{2\pi n}{T}x}-e^{-i\frac{2\pi n}{T}x}}{2i}) \\ &= \frac{a_n-ib_n}{2}e^{i\frac{2\pi n}{T}x}+(\frac{a_n+ib_n}{2}e^{-i\frac{2\pi n}{T}x})\\ &= c_ne^{i\frac{2\pi n}{T}x}+c_{-n}e^{-i\frac{2\pi n}{T}x} \end{align}

其中$c_n = \frac{a_n-ib_n}{2}$，且由$a_n$为偶函数，$b_n$为奇函数，可得$c_{-n}=\frac{a_{-n}-ib_{-n}}{2}=\frac{a_n+ib_n}{2}$。

当$n=0$时，有$c_0=\frac{a_0}{2}$，代回$f(x)$中，有，

f(x)=∑n=−∞∞cn⋅ei2πnTxf(x) = \sum\limits_{n=-\infty}^{\infty}c_n\cdot e^{i\frac{2\pi n }{T}x}

其中，$c_n$为基的坐标，$e^{i\frac{2\pi n}{T}x}$为正交基。

将$a_n$，$b_n$结果带入$c_n$可知：

cn=1T∫−T/2T/2f(x)(cos⁡(2πnTx)−isin⁡(2πnTx))dx=1T∫−T/2T/2f(x)e−i2πnTxdxc_n = \frac{1}{T}\int_{-T/2}^{T/2}f(x)(\cos{(\frac{2\pi n}{T}x)}-i\sin(\frac{2\pi n}{T}x))dx = \frac{1}{T}\int_{-T/2}^{T/2}f(x)e^{-i\frac{2\pi n}{T}x}dx

现在公式用频率$\Delta w=\frac{2\pi}{T}$替换，再令$\omega_n=\Delta \omega n$，有：

f(x)=∑n=−∞∞1T∫−T/2T/2f(x)e−i2πnTxdx⋅ei2πnTx=∑n=−∞∞Δω2π∫−T/2T/2f(x)e−iωnxdx⋅e−iωnxf(x) = \sum\limits_{n=-\infty}^{\infty}\frac{1}{T}\int_{-T/2}^{T/2}f(x)e^{-i\frac{2\pi n}{T}x}dx\cdot e^{i\frac{2\pi n }{T}x} = \sum\limits_{n=-\infty}^{\infty}\frac{\Delta \omega}{2\pi}\int_{-T/2}^{T/2}f(x)e^{-i\omega_n x}dx \cdot e^{-i\omega_nx}

令$T\rightarrow \infty$，有$\Delta \omega\rightarrow 0$，并设$F(\omega)=\mathop{\lim}{T\rightarrow \infty}\int{-T/2}^{T/2}f(x)e^{-i\omega x}dx$，有：

f(x)=∑n=0∞Δω2πF(ωn)⋅e−iωnx=12πF(ωn)∑n=0∞F(ωn)⋅e−iωnxΔω=12π∫−∞+∞F(ω)e−iωxdω\begin{align} f(x)&=\sum\limits_{n=0}^{\infty}\frac{\Delta \omega}{2\pi}F(\omega_n)\cdot e^{-i\omega_nx}\\ &=\frac{1}{2\pi}F(\omega_n)\sum\limits_{n=0}^{\infty} F(\omega_n)\cdot e^{-i\omega_nx} \Delta \omega\\ &=\frac{1}{2\pi}\int_{-\infty}^{+\infty}F(\omega)e^{-i\omega x}d\omega \end{align}

可推得如下：

F(ω)=∫−∞+∞f(x)e−iωxdx=∫Rf(x)e−2πixξdx，其中ξ为任意实数\begin{align} F(\omega)&=\int_{-\infty}^{+\infty}f(x)e^{-i\omega x}dx = \int_R f(x)e^{-2\pi ix\xi}dx，其中\xi为任意实数 \end{align}

  • 卷积公式

根据卷积定理，卷积公式可以写成：

f∗g=F−1{F{f}⋅F{g}}f*g=\mathcal{F}^{-1}\{\mathcal{F}\{f\}\cdot\mathcal{F}\{g\}\}

证明：

$Fourier$变换的定义：$\mathcal{F}{f}(v) = \int_R f(x)e^{-2\pi ix\cdot v}dx$，$Inverse\ Fourier$变换则是：$\mathcal{F}^{-1}{f}(x) = \int_Rf(v)e^{2\pi ix\cdot v}dv$，

定义$h$是$f$和$g$的卷积，有$h(z) = \int_Rf(x)g(z-x)dx$，于是

F{f∗g}(v)=F{h}(v)=∫Rh(z)e−2πiz⋅vdz=∫R∫Rf(x)g(z−x)e−2πiz⋅vdxdz=∫Rf(x)dx∫Rg(z−x)e−2πiz⋅vdz\begin{align} \mathcal{F}\{f*g\}(v)&=\mathcal{F}\{h\}(v)\\&=\int_Rh(z)e^{-2\pi iz\cdot v}dz\\&=\int_R\int_Rf(x)g(z-x)e^{-2\pi iz\cdot v}dxdz\\&=\int_Rf(x)dx\int_Rg(z-x)e^{-2\pi iz\cdot v}dz \end{align}

带入$y=z-x；dy=dz$，有：

F{f∗g}(v)=∫Rf(x)(∫Rg(y)e−2πi(y+x)⋅vdy)dx=∫Rf(x)e−2πix⋅v(∫Rg(y)e−2πiy⋅vdy)dx=∫Rf(x)e−2πix⋅vdx∫Rg(y)e−2πiy⋅vdy=F{f}(v)⋅F{g}(v)\begin{align} \mathcal{F}\{f*g\}(v) &= \int_Rf(x)(\int_Rg(y)e^{-2\pi i(y+x)\cdot v}dy)dx \\ &= \int_Rf(x)e^{-2\pi ix\cdot v}(\int_Rg(y)e^{-2\pi iy\cdot v}dy)dx \\ &= \int_Rf(x)e^{-2\pi ix\cdot v}dx\int_Rg(y)e^{-2\pi iy\cdot v}dy \\ &=\mathcal{F}\{f\}(v)\cdot \mathcal{F}\{g\}(v) \end{align}

同时对等式两边同时乘以$\mathcal{F}^{-1}$，得到：

f∗g=F−1{F{f}⋅F{g}}f*g = \mathcal{F}^{-1}\{\mathcal{F}\{f\}\cdot \mathcal{F}\{g\}\}

这样只需要定义graph上的Fourier变换，就可以定义出graph上的convolution变换。

img

Fourier变换的定义：

F(f)=∫Rf(x)e−2πixξdx，其中ξ为任意实数F(f)=\int_R f(x)e^{-2\pi ix\xi}dx，其中\xi为任意实数

hashtag
Laplacian算子

一阶导数定义：

f′(x)=limh→0f(x+h)−f(x)hf^{'}(x) = \mathop{lim}_{h\rightarrow0} \frac{f(x+h)-f(x)}{h}

laplacian算子简单来说二阶导数：

Δf(x)=f′′(x)=limh→0f(x+h)−2f(x)+f(x−h)h2\Delta f(x)= f^{''}(x) = \mathop{lim}_{h\rightarrow0} \frac{f(x+h)-2f(x)+f(x-h)}{h^2}

那么在graph上，定义一阶导数为：

f∗g′(x)=f(x)−f(y)f^{'}_{*g}(x)=f(x)-f(y)

其中，$y$是$x$的邻居节点，那么对应的Laplacian算子可以定义为：

Δ∗gf′(x)=∑y∼x[f(x)−f(y)]\Delta_{*g}f'(x)=\sum\limits_{y\sim x}[f(x)-f(y)]

定义$D$为$N\times N$的度矩阵为：

D(i,j)={diif  i=j0otherwiseD(i,j) = \left\{\begin{matrix} d_i&if\ \ {i=j} \\ 0&otherwise \end{matrix} \right.

定义$A$为$N\times N$邻接矩阵为：

A(i,j)={1if  xi∼xj0otherwiseA(i,j) = \left\{\begin{matrix} 1&if\ \ x_i\sim x_j \\ 0&otherwise \end{matrix} \right.

$Laplacian$算子定义为：

L=D−AL = D - A

标准化后得到：

L=IN−D−12AD12L = I_N - D^{-\frac{1}{2}}AD^{\frac{1}{2}}

定义$Laplacian$算子的目的是为了找到$Fourier$变换的基比如传统$Fourier$变换的基$e^{2\pi ix\cdot \xi}$就是$Laplacian$算法的一组特征向量：

Δe2πix⋅ξ=λe2πix⋅ξ，其中λ为一个常数\Delta e^{2\pi ix\cdot \xi} = \lambda e^{2\pi ix\cdot \xi}，其中\lambda为一个常数

那么图上的$Fourier$基就是$L$矩阵的$n$个特征向量$U=[u_1,\cdots,u_n]$， $L$可以分解为：

L=UΛUTL = U\Lambda U^T

其中，$\Lambda$为特征值矩阵。

有，

XTLX=XTVΣVTX=(VTX)TΣ(VTX)X^TLX = X^TV\Sigma V^TX = (V^TX)^T\Sigma(V^TX)

记，$\bar X = V^TX$，有$X^TLX=\bar X^T \Sigma \bar X$。

至于为什么要做特征分解，因为在$Graph$中，我们没必要每次都去更新全局，而是可以只关注一阶或二阶。拉普拉斯矩阵的特征分解可以达到目的。

传统$Fourier$变换
$Graph\ Fourier$变换

$Fourier$变换基

$e^{-2\pi ix\cdot \xi}$

$U^T$

逆$Fourier$变换基

$e^{2\pi ix\cdot \xi}$

$U$

维度

$\infty$

点的个数$n$

那么$Graph\ Fourier$变换定义为：

GF{f}(λl)=∑i=1nf(i)ul∗(i)\mathcal{GF}\{f\}(\lambda_l) = \sum\limits_{i=1}^nf(i)u_l^*(i)

其中$f(i)$可以看做是作用第$i$个点上的$signal$，用向量$x=(f(1),\cdots,f(n)) \in \mathbb{R}^n$来表示；$u_l^$是$u_l$的对偶向量，$u_l^$是矩阵$U^T$的第$l$行，$u_l$是矩阵$U$的第$l$行。

用矩阵形式来表示$Graph\ Fourier$变换：

GF{x}=UTx\mathcal{GF}\{x\} = U^Tx

类似的$Inverse\ Graph\ Fourier$变换定义为：

IGF{f^}(i)=∑l=0n−1f^(λl)ul(i)\mathcal{IGF}\{\hat f\}(i) = \sum\limits_{l=0}^{n-1}\hat f(\lambda_l)u_l(i)

其矩阵形式为：

IGF{x}=Ux\mathcal{IGF}\{x\} = Ux

hashtag
推导Graph Convolution

由卷积公式：

f∗g=F−1{F{f}⋅F{g}}，GF{x}=UTx，IGF{x}=Uxf*g = \mathcal{F}^{-1}\mathcal{\{F\{f\}\cdot F\{g\}\}}，\mathcal{GF}\{x\} = U^Tx，\mathcal{IGF}\{x\} = Ux

可知，图的卷积公式可以表示为：

g∗x=U(UTg⋅UTx)g*x = U(U^Tg\cdot U^Tx)

作为图卷积的$filter$函数$g$ ，我们希望具有很好的局部性。就像$CNN$模型里的$filter$一样，只影响到一个像素附近的像素。那么我们可以把$g$定义成一个$laplacian$矩阵的函数$g(L)$。

img

作用一次$laplacian$矩阵相当于在图上传播了一次邻居节点。进一步我们可以把$U^Tg$看做是$g_{\theta}(\Lambda)$一个$laplacian$特征值的函数，参数为$\theta$。

改写上面的图卷积公式，可以得到如下：

gθ∗x=UgθUTx=Ugθ′(Λ)UTxg_{\theta}*x = U_{g_{\theta}}U^Tx = U_{g_{\theta^{'}}}(\Lambda)U^Tx

由于复杂度太高，通过切比雪夫多项式$T_k(x)$展开到第$K$阶：

gθ′(Λ)≈∑k=0Kθk′Tk(L~)g_{\theta^{'}}(\Lambda) \approx \sum\limits_{k=0}^K\theta^{'}_kT_k( \widetilde{L})

其中$ \widetilde{L}=\frac{2}{\lambda_{max}}L-I_N$，可以通过$U\Lambda^kU^T=(U\Lambda^kU^T)^k=L^k$进行验证。

泰勒公式$e^L = 1 + L + \frac{x^2}{2!}+\cdots+\frac{x^k}{k!}$

设$K=1$，卷积公式可以简化为：

gθ′∗x≈θ(IN+L)x=θ(IN+D−12AD−12)xg_{\theta^{'}}*x \approx \theta(I_N+L)x = \theta(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x

令$\widetilde A = A+I_N$，$\widetilde D_{ii} = \sum\limits_j\widetilde{A}_{ij}$，有

gθ′∗x=θ(D~−12A~D~−12)xg_{\theta^{'}}*x = \theta(\widetilde D^{-\frac{1}{2}}\widetilde A\widetilde D^{-\frac{1}{2}})x

hashtag
学习新特征

在深度学习中最重要的学习特征：随着网络层数的增加，特征越来越抽象，然后用于最终的任务。对于图任务来说，这点同样适用，我们希望深度模型从图的最初始特征$X$出发学习到更抽象的特征，比如学习到了某个节点的高级特征，这个特征根据图结构融合了图中其他节点的特征，这样就可以用这个特征用于节点分类或者属性预测。

对于GCN模型，目标是学习作为输入的图上的特征的函数，该函数作为输入：

  • 每个节点$i$的特征描述$x_i$：归纳为$N\times D$特征矩阵$X$（$N$：节点数，$D$：输入特征数）

  • 矩阵形式的图形结构的代表性描述：通常以邻接矩阵的形式进行表示

    并生成节点级输出$Z$（$N\times F$特征矩阵，其中$F$是每个输出特征的数量节点）。图级输出可以引入某种形式的池化操作来建模，然后可以将每个神经网络层写为非线性函数：

    H(l+1)=f(H(l),A)\textbf{H}^{(\textbf{l}+1)} = f(\textbf{H}^{(\textbf{l})},\textbf{A})

    其中，$H^{(0)} = X$，$H^{(L)} = Z$，$L$表示层数，然后特定模型仅在如何选择和参数化$f(\cdot,\cdot)$方面有所不同。

hashtag
一个简单的例子

例如，考虑以下非常简单的分层传播规则形式：

f(H(l),A)=σ(AH(L)W(l))f(H^{(l)},A) = \sigma(AH^{(L)}W^{(l)})

其中，$W^{(l)}$表示第$l$个神经网络层的权重矩阵，而$\sigma(\cdot)$是类似于$ReLU$的非线性激活函数（一个很强大的激活函数）。

可以将上述学习分成三个部分：

  • 变换（transform）：对当前的节点特征进行变换学习，这里就是乘法规则（$Wx$）；

  • 聚合（aggregate）：聚合领域节点的特征，得到该节点的新特征，这里是简单的加法规则；

  • 激活（activate）：采用激活函数，增加非线性。

但是该模型有两个局限性：

  • 与$A$的乘法意味着，对于每个节点，将所有邻近节点的所有特征向量相加，但不包括节点本身(除非图中存在自循环)。可以通过在图中执行自我循环来“修复”这个问题:只需将单位矩阵添加到$A$中，即$\hat A = A+I$。

  • $A$通常没有被规范化，因此是与$A$的矩阵乘法完全改变特征向量的尺度(可以通过观察$A$的特征值来理解)，对$A$进行归一化，使所有行和为1，即$D^{-1}A$，其中$D$是对角节点度矩阵，就可以解决这个问题。现在与$D^{-1}A$相乘就相当于取邻近节点特征的平均值。

当使用对称归一化时，有$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$，可以得到如下：

H(l+1)=f(H(l),A)=σ(D^−12A^D^−12H(L)W(l))H^{(l+1)} = f(H^{(l)},A) = \sigma(\hat D^{-\frac{1}{2}}\hat A\hat D^{-\frac{1}{2}}H^{(L)}W^{(l)})

其中，$\hat A = A+I$，$I$是单位矩阵，$D$是$A$的对角节点矩阵。

实际例子，详细查阅$T Kipf$关于GCN的第三部分

定义了图卷积，我们只需要将图卷积层堆积起来就构成了图卷积网络GCN：

image-20210227141717329

hashtag
Weisfeiler-Lehman算法与GCN

可以将$gcn$模型解释为图形上著名的Weisfeiler-Lehman算法的广义，一维WL算法的工作原理如下：

对于所有节点$v_i \in \mathcal{G}$：

  • 获取相邻节点${v_j}$的特征${h_{vj}}$

  • 更新节点特征$h_{vi}\leftarrow hash(\sum\limits_jh_{vj})$，其中$hash(\cdot)$是一个内射哈希函数

回到图卷积逐层传播规则：

hvi(l+1)=σ(∑j1cijhvj(l)W(l))h_{vi}^{(l+1)} = \sigma(\sum\limits_j\frac{1}{c_{ij}}h_{vj}^{(l)}W^{(l)})

其中$j$为$v_i$的第$j$个相邻节点的索引，$c_{ij}$是边$(v_i,v_j)$的归一化常数，这个源于使用$GCN$模型的对成归一化邻接矩阵$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$。

现在看到该传播规则可以解释为$WL$带有$W$的变体，如果现在选择合适的非线性度并初始化随机权重矩阵以使其正交，此更新规则实际上变得更稳定，得到了有意义的平滑嵌入，在这里可以将距离解释为局部图结构的（不）相似性。

hashtag
图神经网络

其实图神经网路（GNN，Graph Neural Network）是一个庞大的家族，如果按照$f$分类，其可以分成以下类型：

img

GCN是一个低通滤波器

hashtag
实现

加载数据

对图卷积层的进行实现

对于GCN，只需要将图卷积层堆积起来就可以，实现一个两层的GCN：

定义一个计算准确率的函数：

然后配置相关的参数变量

之后导入数据

定义模型和优化器

对数据进行迁移内存

进行训练数据

然后，对测试集进行训练

原学习地址链接：图卷积网络(GCN)新手村完全指南arrow-up-right

T Kipf的文章：GRAPH CONVOLUTIONAL NETWORKSarrow-up-right

T Kipf的论文：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKSarrow-up-right

T Kipf的图卷积神经网络代码实现：pygcnarrow-up-right

hashtag
图论相关

图论arrow-up-right

hashtag
图数据相关任务

1. 节点层面（Node Level）的任务

节点层面的任务主要包括分类任务和回归任务。这类任务虽然是对节点层面的性质进 行预测，但是显然不应该将模型建立在一个个单独的节点上，节点的关系也需要考虑。节 点层面的任务有很多，包括学术上使用较多的对论文引用网络中的论文节点进行分类，工 业界在线社交网络中用户标签的分类、恶意账户检测等。

2. 边层面（Link Level）的任务

边层面的任务主要包括边的分类和预测任务。边的分类是指对边的某种性质进行预 测；边预测是指给定的两个节点之间是否会构成边。常见的应用场景比如在社交网络中， 将用户作为节点，用户之间的关注关系建模为边，通过边预测实现社交用户的推荐。目前，边层面的任务主要集中在推荐业务中。

3. 图层面（Graph Level）的任务

图层面的任务不依赖于某个节点或者某条边的属性，而是从图的整体结构出发，实现 分类、表示和生成等任务。目前，图层面的任务主要应用在自然科学研究领域，比如对药 物分子的分类、酶的分类等。

上一页03-卷积神经网络下一页05-GNN的变体与框架-

最后更新于

这有帮助吗？