1. 为什么会出现图卷积神经网络?普通卷积神经网络研究的对象是具备Euclidean domains的数据,Euclidean domains data数据最显著的特征是他们具有规则的空间结构,如图片是规则的正方形,语音是规则的一维序列等,这些特征都可以用一维或二维的矩阵来表示,卷积神经网络处理起来比较高效。 CNN的【平移不变性】在【非矩阵结构】数据上不适用
离散卷积本质就是一种加权求和。CNN中的卷积就是一种离散卷积,本质上就是利用一个共享参数的过滤器(kernel),通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取,当然加权系数就是卷积核的权重系数(W)。 那么卷积核的系数如何确定的呢?是随机化初值,然后根据误差函数通过反向传播梯度下降进行迭代优化。这是一个关键点,卷积核的参数通过优化求出才能实现特征提取的作用,GCN的理论很大一部分工作就是为了引入可以优化的卷积参数。 生活中很多数据不具备规则的空间结构,称为Non Euclidean data,如,推荐系统、电子交易、分子结构等抽象出来的图谱。这些图谱中的每个节点连接不尽相同,有的节点有三个连接,有的节点只有一个连接,是不规则的结构。对于这些不规则的数据对象,普通卷积网络的效果不尽人意。CNN卷积操作配合pooling等在结构规则的图像等数据上效果显著,但是如果作者考虑非欧氏空间比如图(即graph,流形也是典型的非欧结构,这里作者只考虑图),就难以选取固定的卷积核来适应整个图的不规则性,如邻居节点数量的不确定和节点顺序的不确定。 例如,社交网络非常适合用图数据来表达,如社交网络中节点以及节点与节点之间的关系,用户A(有ID信息等)、用户B、帖子都是节点,用户与用户之间的关系是关注,用户与帖子之间的关系可能是发布或者转发。通过这样一个图谱,可以分析用户对什么人、什么事感兴趣,进一步实现推荐机制。 总结一下,图数据中的空间特征具有以下特点: 综上所述,GCN是要为除CV、NLP之外的任务提供一种处理、研究的模型。 2. 图卷积网络的两种理解方式GCN的本质目的就是用来提取拓扑图的空间特征。 而图卷积神经网络主要有两类,一类是基于空间域或顶点域vertex domain(spatial domain)的,另一类则是基于频域或谱域spectral domain的。通俗点解释,空域可以类比到直接在图片的像素点上进行卷积,而频域可以类比到对图片进行傅里叶变换后,再进行卷积。 所谓的两类其实就是从两个不同的角度理解,关于从空间角度的理解可以看本文的从空间角度理解GCN 2.1 vertex domain(spatial domain):顶点域(空间域)基于空域卷积的方法直接将卷积操作定义在每个结点的连接关系上,它跟传统的卷积神经网络中的卷积更相似一些。在这个类别中比较有代表性的方法有 Message Passing Neural Networks(MPNN)[1], GraphSage[2], Diffusion Convolution Neural Networks(DCNN)[3], PATCHY-SAN[4]等。 2.2 spectral domain:频域方法(谱方法)这就是谱域图卷积网络的理论基础了。这种思路就是希望借助图谱的理论来实现拓扑图上的卷积操作。从整个研究的时间进程来看:首先研究GSP(graph signal processing)的学者定义了graph上的Fourier Transformation,进而定义了graph上的convolution,最后与深度学习结合提出了Graph Convolutional Network。 基于频域卷积的方法则从图信号处理起家,包括 Spectral CNN[5], Cheybyshev Spectral CNN(ChebNet)[6], 和 First order of ChebNet(1stChebNet)[7] 等 论文Semi-Supervised Classification with Graph Convolutional Networks就是一阶邻居的ChebNet 认真读到这里,脑海中应该会浮现出一系列问题: Q2 GCN为什么要利用Spectral graph theory? 过程: 下面将介绍关于频谱域的图卷积网络的推导相关的内容。 3. 什么是拉普拉斯矩阵?拉普拉斯矩阵(Laplacian matrix) 也叫做导纳矩阵、基尔霍夫矩阵或离散拉普拉斯算子,主要应用在图论中,作为一个图的矩阵表示。对于图 G=(V,E),其Laplacian 矩阵的定义为 L=D-A,其中 L 是Laplacian 矩阵, D=diag(d)是顶点的度矩阵(对角矩阵),d=rowSum(A),对角线上元素依次为各个顶点的度, A 是图的邻接矩阵。 Graph Fourier Transformation及Graph Convolution的定义都用到图的拉普拉斯矩阵。 频域卷积的前提条件是图必须是无向图,只考虑无向图,那么L就是对称矩阵。 3.1 常用的几种拉普拉斯矩阵普通形式的拉普拉斯矩阵L=D−AL=D-AL=D−A 对称归一化的拉普拉斯矩阵(Symmetric normalized Laplacian)Lsys=D−1/2LD−1/2=I−D−1/2AD−1/2L^{sys}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}Lsys=D−1/2LD−1/2=I−D−1/2AD−1/2 Lsysi,j=⎧⎩⎨⎪⎪⎪⎪⎪⎪1−1diag(vi)diag(vj)√0i=j and diag(vi) ≠ 0i≠j and vi is adjacent to vjotherwiseL^{sys}_{i,j}=\begin{cases}1 & i=j \ and \ diag(v_i) \ \neq \ 0\\-\frac{1}{\sqrt{diag(v_i)diag(v_j)}} & i \neq j \ and \ v_i \ is\ adjacent \ to \ v_j\\0 & otherwise\end{cases}Li,jsys=⎩⎪⎪⎨⎪⎪⎧1−diag(vi)diag(vj)10i=j and diag(vi) = 0i=j and vi is adjacent to vjotherwise 很多GCN的论文中应用的是这种拉普拉斯矩阵 随机游走归一化拉普拉斯矩阵(Random walk normalized Laplacian)Lrw=D−1L=I−D−1AL^{rw}=D^{-1}L=I-D^{-1}ALrw=D−1L=I−D−1A Lrwi,j=⎧⎩⎨⎪⎪⎪⎪1−1diag(vi)0i=j and diag(vi) ≠ 0i≠j and vi is adjacent to vjotherwiseL^{rw}_{i,j}=\begin{cases}1 & i=j \ and \ diag(v_i) \ \neq \ 0\\-\frac{1}{diag(v_i)} & i \neq j \ and \ v_i \ is\ adjacent \ to \ v_j\\0 & otherwise\end{cases}Li,jrw=⎩⎪⎨⎪⎧1−diag(vi)10i=j and diag(vi) = 0i=j and vi is adjacent to vjotherwise 泛化的拉普拉斯 (Generalized Laplacian)泛化的拉普拉斯(用得少)定义为: ⎧⎩⎨⎪⎪Qi,j<0Qi,j=0anynumberi ≠ j and diag(vi) ≠ 0i≠j and vi is adjacent to vjotherwise\begin{cases}Q_{i,j}<0 & i \ \neq \ j \ and \ diag(v_i) \ \neq \ 0\\Q_{i,j}=0 & i \neq j \ and \ v_i \ is\ adjacent \ to \ v_j\\any number & otherwise\end{cases}⎩⎪⎨⎪⎧Qi,j<0Qi,j=0anynumberi = j and diag(vi) = 0i=j and vi is adjacent to vjotherwise 一个拉普拉斯矩阵的计算例子(依据于上图): A=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪010010101010010100001011110100000100⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪,D=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪200000030000002000000300000030000001⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪,L=D−A=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪2−100−10−13−10−100−12−10000−13−1−1−1−10−130000−101⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪A=\left\{\begin{matrix}0 & 1 & 0 & 0 & 1 & 0\\1 & 0 & 1 & 0 & 1 & 0\\0 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1 & 1\\1 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 0 & 0\end{matrix}\right\},D=\left\{\begin{matrix}2 & 0 & 0 & 0 & 0 & 0\\0 & 3 & 0 & 0 & 0 & 0\\0 & 0 & 2 & 0 & 0 & 0\\0 & 0 & 0 & 3 & 0 & 0\\0 & 0 & 0 & 0 & 3 & 0\\0 & 0 & 0 & 0 & 0 & 1\end{matrix}\right\},L=D-A=\left\{\begin{matrix}2 & -1 & 0 & 0 & -1 & 0\\-1 & 3 & -1 & 0 & -1 & 0\\0 & -1 & 2 & -1 & 0 & 0\\0 & 0 & -1 & 3 & -1 & -1\\-1 & -1 & 0 & -1 & 3 & 0\\0 & 0 & 0 & -1 & 0 & 1\end{matrix}\right\}A=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧010010101010010100001011110100000100⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫,D=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧200000030000002000000300000030000001⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫,L=D−A=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧2−100−10−13−10−100−12−10000−13−1−1−1−10−130000−101⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫ D−1/2=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪12√00000013√00000012√00000013√00000013√0000001⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪,Lsys=D−1/2LD−1/2=I−D−1/2AD−1/2=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪1−16√0−16√00−16√1−16√0−19√00−16√1−16√00−16√0−16√1−19√−13√0−19√0−19√10000−13√01⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪D^{-1/2}=\left\{\begin{matrix}\frac{1}{\sqrt{2}} & 0 & 0 & 0 & 0 & 0\\0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0 & 0\\0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & 0\\0 & 0 & 0 & \frac{1}{\sqrt{3}} & 0 & 0\\0 & 0 & 0 & 0 & \frac{1}{\sqrt{3}} & 0\\0 & 0 & 0 & 0 & 0 & 1\end{matrix}\right\},L^{sys}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}=\left\{\begin{matrix}1 & -\frac{1}{\sqrt{6}} & 0 & -\frac{1}{\sqrt{6}} & 0 & 0\\-\frac{1}{\sqrt{6}} & 1 & -\frac{1}{\sqrt{6}} & 0 & -\frac{1}{\sqrt{9}} & 0\\0 & -\frac{1}{\sqrt{6}} & 1 & -\frac{1}{\sqrt{6}} & 0 & 0\\-\frac{1}{\sqrt{6}} & 0 & -\frac{1}{\sqrt{6}} & 1 & -\frac{1}{\sqrt{9}} & -\frac{1}{\sqrt{3}}\\0 & -\frac{1}{\sqrt{9}} & 0 & -\frac{1}{\sqrt{9}} & 1 & 0\\0 & 0 & 0 & -\frac{1}{\sqrt{3}} & 0 & 1\end{matrix}\right\}D−1/2=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧21000000310000002100000031000000310000001⎭⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎫,Lsys=D−1/2LD−1/2=I−D−1/2AD−1/2=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧1−610−6100−611−610−9100−611−6100−610−611−91−310−910−9110000−3101⎭⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎫ Graph Convolution与Diffusion相似之处,当然从Random walk normalized Laplacian就能看出了两者确有相似之处(其实两者只差一个相似矩阵的变换,可参考Diffusion-Convolutional Neural Networks) 3.2 无向图的拉普拉斯矩阵有什么性质(1)拉普拉斯矩阵是半正定矩阵。(最小特征值大于等于0) 拉普拉斯矩阵的半正定性证明,如下: 所以,对于任意一个属于实向量f∈Rmf \in \mathbb{R}^mf∈Rm(f为m∗1的实数列向量 ),都有此公式成立: fTLf=12∑mi,j=1aij(fi−fj)2f^TLf = \frac{1}{2}\sum_{i,j=1}^m a_{ij}(f_i-f_j)^2fTLf=21i,j=1∑maij(fi−fj)2 3.3 为什么GCN要用拉普拉斯矩阵?
3.4. 拉普拉斯矩阵的谱分解(特征分解)GCN的核心基于拉普拉斯矩阵的谱分解,文献中对于这部分内容没有讲解太多,初学者可能会遇到不少误区,所以先了解一下特征分解。 特征分解(Eigendecomposition),又称谱分解(Spectral decomposition)是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有对可对角化矩阵或有n个线性无关的特征向量的矩阵才可以施以特征分解。 不是所有的矩阵都可以特征分解,其充要条件为n阶方阵存在n个线性无关的特征向量。 但是拉普拉斯矩阵是半正定矩阵(半正定矩阵本身就是对称矩阵),有如下三个性质:
由上拉普拉斯矩阵对称知一定可以谱分解,且分解后有特殊的形式。 对于拉普拉斯矩阵其谱分解为: L=UΛU−1=U⎡⎣⎢λ1⋱λn⎤⎦⎥U−1L=U \Lambda U^{-1}=U\left[ \begin{matrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \\ \end{matrix} \right] U^{-1}L=UΛU−1=U⎣⎡λ1⋱λn⎦⎤U−1 由于 U 是正交矩阵,即UUT=EUU^{T}=EUUT=E,所以特征分解又可以写成: 3.5 拉普拉斯算子定义:拉普拉斯算子是n维欧几里德空间中的一个二阶微分算子,定义为梯度(∇f\nabla f∇f)的散度(∇⋅f\nabla \cdot f∇⋅f,即∇f⋅f\nabla f \cdot f∇f⋅f)。因此如果f是二阶可微的实函数,则f的拉普拉斯算子∆定义为: Δf=∇2f=∇⋅∇f∆f=\nabla^2 f=\nabla \cdot \nabla f∆f=∇2f=∇⋅∇f Δf=∑ni=1∂2f∂x2i∆f=\sum_{i=1}^n \frac{\partial^2f}{\partial x_i^2}∆f=i=1∑n∂xi2∂2f 拉普拉斯算子(Laplacian operator) 的物理意义是空间二阶导,准确定义是:标量梯度场中的散度,一般可用于描述物理量的流入流出。比如说在二维空间中的温度传播规律,一般可以用拉普拉斯算子来描述。 拉普拉斯矩阵也叫做离散的拉普拉斯算子。 4. 如何通俗易懂地理解卷积?4.1 连续形式的一维卷积在泛函分析中,卷积是通过两个函数f(x)和g(x)生成第三个函数的一种算子,它代表的意义是:两个函数中的一个(取g(x),可以任意取)函数,把g(x)经过翻转平移,然后与f(x)的相乘,得到的一个新的函数,对这个函数积分,也就是对这个新的函数求它所围成的曲边梯形的面积。 设f(t),g(t)是两个可积函数,f(t)与g(t)的卷积记为f(t)∗g(t)f(t)*g(t)f(t)∗g(t),它是其中一个函数翻转并平移后与另一个函数乘积的积分,是一个自变量是平移量的函数。也就是: f(t)∗g(t)=∫+∞−∞f(τ)g(t−τ)dτ=∫+∞−∞f(t−τ)g(τ)dτf(t)*g(t)= \int_{-\infty}^{+\infty}f(\tau)g(t-\tau)d\tau= \int_{-\infty}^{+\infty}f(t-\tau)g(\tau)d\tauf(t)∗g(t)=∫−∞+∞f(τ)g(t−τ)dτ=∫−∞+∞f(t−τ)g(τ)dτ 4.2 离散形式的一维卷积对于定义在整数Z\mathbb{Z}Z上的函数f,g,卷积定义为 (f∗g)(t)=∑∞τ=−∞f(τ)g(t−τ)(f*g)(t)={\sum}_{\tau=-\infty}^{\infty}f(\tau)g(t-\tau)(f∗g)(t)=∑τ=−∞∞f(τ)g(t−τ) 4.3 实例:掷骰子问题光看数学定义可能会觉得非常抽象,下面举一个掷骰子的问题,该实例参考了知乎问题"如何通俗易懂地解释卷积"的回答。 想象现在有两个骰子,两个骰子分别是f跟g,f(1)表示骰子f向上一面为数字1的概率。同时抛掷这两个骰子1次,它们正面朝上数字和为4的概率是多少呢?相信读者很快就能想出它包含了三种情况,分别是:
最后这三种情况出现的概率和即问题的答案,如果写成公式,就是∑3τ=1f(τ)g(4−τ)\sum_{\tau=1}^{3}f(\tau)g(4-\tau)∑τ=13f(τ)g(4−τ)。可以形象地绘制成下图: 如果稍微扩展一点,比如说认为 f(0) 或者 g(0)等是可以取到的,只是它们的值为0而已。那么该公式可以写成∑∞τ=−∞f(τ)g(4−τ)\sum_{\tau=-\infty}^{\infty}f(\tau)g(4-\tau)∑τ=−∞∞f(τ)g(4−τ)。仔细观察,这其实就是卷积(f∗g)(4)。如果将它写成内积的形式,卷积其实就是 [f(−∞),⋯,f(1),⋯,f(∞)]⋅[g(∞),⋯,g(3),⋯,g(−∞)][f(-\infty),\cdots,f(1),\cdots,f(\infty)] \cdot [g(\infty),\cdots,g(3),\cdots,g(-\infty)][f(−∞),⋯,f(1),⋯,f(∞)]⋅[g(∞),⋯,g(3),⋯,g(−∞)] 这么一看,是不是就对卷积的名字理解更深刻了呢? 所谓卷积,其实就是把一个函数卷(翻)过来,然后与另一个函数求内积。 对应到不同方面,卷积可以有不同的解释:g 既可以看作我们在深度学习里常说的核(Kernel),也可以对应到信号处理中的滤波器(Filter)。而 f 可以是我们所说的机器学习中的特征(Feature),也可以是信号处理中的信号(Signal)。f和g的卷积 (f∗g)就可以看作是对f的加权求和。下面两个动图就分别对应信号处理与深度学习中卷积操作的过程。 5. 傅里叶变换5.1 连续形式的傅立叶变换关于傅立叶变换相关的详细而有趣的内容,可以看这几篇文章:
下面是一个大致流程: 任意一个周期函数可以由若干个正交函数(由sin,cossin, cossin,cos 构成)的线性组合构成,写出傅里叶级数的形式如下: cosx=eix+e−ix2,sinx=eix−e−ix2i\cos x=\frac{e^{ix} +e^{-ix}}{2} ,\sin x=\frac{e^{ix} -e^{-ix}}{2i}cosx=2eix+e−ix,sinx=2ieix−e−ix 在时间t轴上,把eite^{it}eit向量的虚部(也就是纵坐标)记录下来,得到的就是sin(t)sin(t)sin(t): 在时间t轴上,把ei2te^{i2t}ei2t向量的虚部记录下来,得到的就是sin(2t)sin(2t)sin(2t): 如果在时间t轴上,把eite^{it}eit的实部(横坐标)记录下来,得到的就是cos(t)cos(t)cos(t)的曲线: 更一般的,具有两种看待sin,cossin, cossin,cos的角度: eiωt⟺{sin(ωt)cos(ωt)e^{i\omega t}\iff \begin{cases}sin(\omega t)\\cos(\omega t)\end{cases}eiωt⟺{sin(ωt)cos(ωt) 这两种角度,一个可以观察到旋转的频率,所以称为频域;一个可以看到流逝的时间,所以称为时域: 所以,任意周期函数可以以eiωte^{i\omega t}eiωt为基函数用傅里叶级数的指数形式表示。即,对于一个周期函数f(x)f(x)f(x)以傅里叶级数的指数形式表示为: f(x)=∫∞−∞[∫+∞−∞f(x)e−iωxdx] eiωxdω=∫∞−∞F(ω) eiωxdωf(x) = \int_{-\infty}^\infty [\int ^{+\infty }_{-\infty } f(x)e^{-i\omega x} dx]\ e^{i\omega x}\,d\omega=\int_{-\infty}^\infty F(\omega)\ e^{i\omega x}\,d\omegaf(x)=∫−∞∞[∫−∞+∞f(x)e−iωxdx] eiωxdω=∫−∞∞F(ω) eiωxdω 当然,也可以利用欧拉公式通过cos和sin函数表示为F(u)F(u)F(u): F(u)=∫+∞−∞f(x)[cos(2πxu)−isin(2πxu)]dxF(u)=\int_{-\infty}^{+\infty}f(x)\left[cos(2\pi xu)-i sin(2\pi xu)\right]dxF(u)=∫−∞+∞f(x)[cos(2πxu)−isin(2πxu)]dx 所以,对函数f(x)f(x)f(x)的傅里叶变换F\mathcal{F}F和傅里叶的逆变换F−1\mathcal{F}^{-1}F−1记作: F(ω)=F[f(x)],f(x)=F−1[F(ω)]F( \omega )=\mathcal{F}[f(x)],f(x)=\mathcal{F}^{-1}[F(\omega)] \\F(ω)=F[f(x)],f(x)=F−1[F(ω)]
其实可以发现这个对信号f(x)f(x)f(x)的傅立叶变换F(ω)F(\omega)F(ω)形式上是f(x)f(x)f(x)与基函数e−iωxe^{-i\omega x}e−iωx的积分,本质上将函数f(x)f(x)f(x)映射到了以e−iωxe^{-i\omega x}e−iωx为基向量的空间中。 5.2 频域(frequency domain)和时域(time domain)的理解时域:真实量到的信号的时间轴,代表真实世界。 频域:为了做信号分析用的一种数学手段。 要理解时域和频域只需要看下面两张动图就可以了: 上图来自于维基百科,图中红色部分就是原函数f(x)在时域里面的曲线图,此函数经过傅里叶变换后可以分解成很多如右图中的曲线。在左图中的的蓝色线就是对应的频域中的频谱图。 频谱图里的竖线分别代表了不同频率的正弦波函数,也就是之前的基,而高度则代表在这个频率上的振幅,也就是这个基上的坐标分量。 很多在时域看似不可能做到的数学操作,在频域相反很容易。这就是需要傅里叶变换的地方。尤其是从某条曲线中去除一些特定的频率成分,这在工程上称为滤波,是信号处理最重要的概念之一,只有在频域才能轻松的做到。 看一个傅里叶变换去噪的例子: 只要在频谱图中擦除这些点,就可以将背景条纹去掉,得到下图右侧的结果。 5.3 周期性离散傅里叶变换(Discrete Fourier Transform, DFT)傅里叶变换有连续时间非周期傅里叶变换,连续时间周期性傅里叶变换,离散时间非周期傅里叶变换和离散时间周期性傅里叶变换,鉴于计算机主要处理离散周期性信号,本文主要介绍周期性离散时间傅里叶变换(DFT)。信号xnx_nxn的傅里叶变换XkX_kXk为 Xk=∑N−1n=0xne−i2πNknX_k=\sum_{n=0}^{N-1}x_n e^{-i \frac{2\pi}{N}kn}Xk=n=0∑N−1xne−iN2πkn
6. Graph上的傅里叶变换及卷积把传统的傅里叶变换以及卷积迁移到Graph上来,核心工作其实就是把拉普拉斯算子的特征函数e−iωte^{-i\omega t}e−iωt 变为Graph对应的拉普拉斯矩阵的特征向量。 傅立叶变换与拉普拉斯矩阵的关系:传统傅立叶变换的基,就是拉普拉斯矩阵的一组特征向量。 6.1 图上的傅里叶变换前面讲到可以用一组正交函数cos和sin(或e−iωte^{-i\omega t}e−iωt )表示任意函数,且傅里叶变换是连续形式的,在处理Graph时,用到的是傅里叶变换的离散形式。由于拉普拉斯矩阵进行谱分解以后,可以得到n个线性无关的特征向量,构成空间中的一组正交基,因此归一化拉普拉斯矩阵算子的特征向量构成了图傅里叶变换的基。图傅里叶变换将输入图的信号投影到了正交空间,相当于把图上定义的任意向量,表示成了拉普拉斯矩阵特征向量的线性组合。 离散积分就是一种内积形式,由此可以定义Graph上的傅里叶变换(实数域):
6.2 图的傅立叶变换——图的傅立叶变换的矩阵形式利用矩阵乘法将Graph上的傅里叶变换推广到矩阵形式: fˆ=UTf(a)\hat{f}=U^Tf \qquad(a)f^=UTf(a) 6.3 图的傅立叶逆变换——图的傅立叶逆变换的矩阵形式类似地,传统的傅里叶变换是对频率ω\omegaω 求积分: F−1[F(ω)]=12Π∫F(ω)eiωtdω\mathcal{F}^{-1}[F(\omega)]=\frac{1}{2\Pi}\int_{}^{}F(\omega)e^{i\omega t} d\omegaF−1[F(ω)]=2Π1∫F(ω)eiωtdω 迁移到Graph上变为对特征值λl\lambda_lλl求和: f(i)=∑Nl=1fˆ(λl)ul(i)f(i)=\sum_{l=1}^{N}{\hat{f}(\lambda_l) u_l(i)}f(i)=l=1∑Nf^(λl)ul(i) 利用矩阵乘法将Graph上的傅里叶逆变换推广到矩阵形式: ⎛⎝⎜⎜⎜⎜f(1)f(2)⋮f(N)⎞⎠⎟⎟⎟⎟=⎛⎝⎜⎜⎜⎜ u1(1)u1(2)⋮u1(N)u2(1)u1(2)⋮u2(N)……⋱…uN(1)uN(2)⋮uN(N)⎞⎠⎟⎟⎟⎟⎛⎝⎜⎜⎜⎜⎜fˆ(λ1)fˆ(λ2)⋮fˆ(λN)⎞⎠⎟⎟⎟⎟⎟\left(\begin{matrix}f(1)\\ f(2) \\ \vdots \\f(N) \end{matrix}\right)= \left(\begin{matrix}\ u_1(1) &u_2(1)& \dots &u_N(1) \\u_1(2) &u_1(2)& \dots &u_N(2)\\ \vdots &\vdots &\ddots & \vdots\\ u_1(N) &u_2(N)& \dots &u_N(N) \end{matrix}\right) \left(\begin{matrix} \hat{f}(\lambda_1)\\ \hat{f}(\lambda_2) \\ \vdots \\\hat{f}(\lambda_N) \end{matrix}\right)⎝⎜⎜⎜⎛f(1)f(2)⋮f(N)⎠⎟⎟⎟⎞=⎝⎜⎜⎜⎛ u1(1)u1(2)⋮u1(N)u2(1)u1(2)⋮u2(N)……⋱…uN(1)uN(2)⋮uN(N)⎠⎟⎟⎟⎞⎝⎜⎜⎜⎛f^(λ1)f^(λ2)⋮f^(λN)⎠⎟⎟⎟⎞ 即 f 在Graph上傅里叶逆变换的矩阵形式为: f=Ufˆ(b)f=U\hat{f} \qquad(b)f=Uf^(b) 6.4 图上的傅里叶变换推广到图卷积在上面的基础上,利用卷积定理类比来将卷积运算,推广到Graph上。 卷积定理:函数卷积的傅里叶变换是函数傅立叶变换的乘积,即对于函数f与g两者的卷积是其函数傅立叶变换乘积的逆变换(中间的桥梁就是傅立叶变换与反傅立叶变换,证明见:https://zhuanlan.zhihu.com/p/54505069): f∗g=F−1{F(f)⋅F(g)}=F−1{fˆ⋅gˆ}f * g=\mathcal{F}^{-1}{\{\mathcal{F}(f) \cdot \mathcal{F}(g) \}}=\mathcal{F}^{-1}\{ \hat{f} \cdot \hat{g}\}f∗g=F−1{F(f)⋅F(g)}=F−1{f^⋅g^} ⎛⎝⎜⎜⎜⎜⎜fˆ(λ1)fˆ(λ2)⋮fˆ(λN)⎞⎠⎟⎟⎟⎟⎟,⎛⎝⎜⎜⎜⎜f(1)f(2)⋮f(N)⎞⎠⎟⎟⎟⎟\left(\begin{matrix} \hat{f}(\lambda_1)\\ \hat{f}(\lambda_2) \\ \vdots \\\hat{f}(\lambda_N) \end{matrix}\right),\left(\begin{matrix}f(1)\\ f(2) \\ \vdots \\f(N) \end{matrix}\right)⎝⎜⎜⎜⎛f^(λ1)f^(λ2)⋮f^(λN)⎠⎟⎟⎟⎞,⎝⎜⎜⎜⎛f(1)f(2)⋮f(N)⎠⎟⎟⎟⎞ 所以,很多论文中的Graph卷积公式也写作: 如果把UTgU^TgUTg整体看作可学习的卷积核,这里我们把它写作gθg_\thetagθ。最终图上的卷积公式即是: (f∗g)G=UgθUTf(f*g)_G = Ug_{\theta}U^Tf(f∗g)G=UgθUTf f∗gθ=UgθUTf=U⎛⎝⎜gˆ(λ1)⋱gˆ(λn)⎞⎠⎟UTff*g_\theta=Ug_{\theta}U^Tf= U\left(\begin{matrix}\hat g(\lambda_1) & \\&\ddots \\ &&\hat g(\lambda_n) \end{matrix}\right) U^Tff∗gθ=UgθUTf=U⎝⎛g^(λ1)⋱g^(λn)⎠⎞UTf 接下来第8节要介绍的图上频域卷积的工作,都是在gθg_\thetagθ的基础上做文章。 7. 为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基?特征值表示频率?在Chebyshev论文(M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,”in Advances in Neural Information Processing Systems, 2016)中就有说明,图上进行傅里叶变换时,拉普拉斯矩阵是对称矩阵,所有有n个线性无关的特征向量,因此可以构成傅里叶变换的一组基,而其对应的特征值就是傅里叶变换的频率。 7.1 为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基?傅里叶变换一个本质理解就是:把任意一个函数表示成了若干个正交函数(由sin,cos 构成)的线性组合。 通过即 f 在Graph上傅里叶逆变换的矩阵形式: f=Ufˆ(b)f=U\hat{f} \qquad(b)f=Uf^(b)也能看出,graph傅里叶变换把graph上定义的任意向量f,表示成了拉普拉斯矩阵特征向量的线性组合,即: f=fˆ(1)u1+fˆ(2)u2+⋯+fˆ(n)unf=\hat{f}(1)u_1+\hat{f}(2)u_2+\cdots +\hat{f}(n)u_nf=f^(1)u1+f^(2)u2+⋯+f^(n)un 那么:为什么graph上任意的向量f都可以表示成这样的线性组合? 原因在于(u1⃗ ,u2⃗ ,⋯,un⃗ )(\vec{u_1},\vec{u_2},\cdots,\vec{u_n})(u1,u2,⋯,un)是graph上 n维空间中的 n 个线性无关的正交向量(拉普拉斯矩阵是对称矩阵,必定可以进行特征分解,有n个线性无关的特征向量),由线性代数的知识可以知道:n 维空间中n 个线性无关的向量可以构成空间的一组基,而且拉普拉斯矩阵的特征向量还是一组正交基。 7.2 怎么理解拉普拉斯矩阵的特征值表示频率?在graph空间上无法可视化展示“频率”这个概念,那么从特征方程上来抽象理解。 将拉普拉斯矩阵 L 的 n 个非负实特征值,从小到大排列为λ1≤λ2≤⋯≤λn\lambda_1 \le \lambda_2 \le \cdots \le \lambda_nλ1≤λ2≤⋯≤λn,而且最小的特征值λ1=0\lambda_1=0λ1=0,因为 n 维的全1向量对应的特征值为0(由 L 的定义就可以得出): L⎛⎝⎜⎜⎜11⋮1⎞⎠⎟⎟⎟=0L \left(\begin{matrix}1\\ 1 \\ \vdots \\1 \end{matrix}\right)=0L⎝⎜⎜⎜⎛11⋮1⎠⎟⎟⎟⎞=0 从特征方程的数学理解来看: Lu=λuLu=\lambda uLu=λu 在由Graph确定的 n 维空间中,越小的特征值 λl\lambda_lλl表明:拉普拉斯矩阵 L 其所对应的基ulu_lul上的分量、“信息”越少,那么当然就是可以忽略的低频部分了。 其实图像压缩就是这个原理,把像素矩阵特征分解后,把小的特征值(低频部分)全部变成0,PCA降维也是同样的,把协方差矩阵特征分解后,按从大到小取出前K个特征值对应的特征向量作为新的“坐标轴”。 Graph Convolution的理论告一段落了,下面开始Graph Convolution Network 8. 深度学习中GCN的演变Deep learning 中的Graph Convolution直接看上去会和第6节推导出的图卷积公式有很大的不同,但是万变不离其宗,都是根据下式来推导的: Deep learning 中的Convolution就是要设计含有trainable共享参数的kernel。 上式计算量很大,因为特征向量矩阵U 的复杂度是O(N2)O(N^2)O(N2)。此外,对于大型图来说,L特征值分解的计算量也很大。 基于上面最原始的卷积公式,深度学习中的GCN主要是从下面几篇文章演变而来的(引用次数都很高),后面一一进行简单介绍:
8.1 Spectral CNN谱CNN源于论文(J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” in Proceedings of International Conference on Learning Representations, 2014),Bruna等人,第一次提出谱卷积神经网络。他们简单地把gθg_\thetagθ 看作是一个可学习参数的集合:gθ=Θki,jg_\theta=\Theta_{i,j}^kgθ=Θi,jk。并且假设图信号是多维的,图卷积层顶定义为: Xk+1:,j=σ(∑fk−1i=1UΘki,jUTXk:,i)(j=1,2,⋯,fk)X_{:,j}^{k+1} = \sigma(\sum_{i=1}^{f_{k-1}}U\Theta_{i,j}^kU^TX_{:,i}^{k})\quad \quad \quad (j=1,2,\cdots,f_k)X:,jk+1=σ(i=1∑fk−1UΘi,jkUTX:,ik)(j=1,2,⋯,fk)
第一代的参数方法存在着一些弊端,主要在于: 由于以上的缺点第二代的卷积核设计应运而生。 8.2 Chebyshev谱CNN(ChebNet)Chebyshev谱CNN源于论文(M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,”in Advances in Neural Information Processing Systems, 2016)。Defferrard等人提出ChebNet,定义特征向量对角矩阵的切比雪夫多项式为滤波器,也就是 gθ=gθ(Λ)≈∑K−1i=0θiTk(Λ˜)g_θ=g_θ(Λ) \approx \sum^{K-1}_{i=0} \theta_i T_k(\tilde Λ)gθ=gθ(Λ)≈i=0∑K−1θiTk(Λ~) 推导过程如下: gθ∗x=UgθUTx(3)g_\theta * x = Ug_\theta U^Tx \qquad (3)gθ∗x=UgθUTx(3)
L=D−12(D−A)D−12=D−12DD−12−D−12AD−12=IN−D−12AD−12\begin{aligned}L &= D^{-\frac{1}{2}}(D - A)D^{-\frac{1}{2}} \\&= D^{-\frac{1}{2}} D D^{-\frac{1}{2}} -D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \\&= I_N - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\end{aligned} L=D−21(D−A)D−21=D−21DD−21−D−21AD−21=IN−D−21AD−21
gθ=gθ(Λ)g_θ=g_θ(Λ)gθ=gθ(Λ) 式3的计算量很大,因为特征向量矩阵U 的复杂度是O(N2)O(N^2)O(N2)。此外,对于大型图来说,L特征值分解的计算量也很大。 gθ(Λ)≈∑Kk=0θkTK(Λ˜)(4)g_{\theta}(Λ) \approx \sum^{K}_{k=0} \theta_kT_K(\tilde Λ) \qquad (4)gθ(Λ)≈k=0∑KθkTK(Λ~)(4)
回到对信号x与滤波器gθg_{θ}gθ的卷积的定义,现在有: gθ∗x=∑Kk=0θkTK(L˜)x(5)g_{\theta} * x = \sum^{K}_{k=0} \theta_kT_K(\tilde L)x \qquad (5)gθ∗x=k=0∑KθkTK(L~)x(5)
现在,相比于第一种Spectral CNN:
公式4到公式5的补充证明如下: UTk(Λ˜)UT=Tk(UΛ˜UT)U T_k (\tilde{\Lambda}) U^T = T_k (U \tilde{\Lambda} U^T)UTk(Λ~)UT=Tk(UΛ~UT) 证明: UTk−1(Λ˜)UT=Tk−1(UΛ˜UT)U T_{k-1} (\tilde{\Lambda}) U^T= T_{k-1} (U \tilde{\Lambda} U^T)UTk−1(Λ~)UT=Tk−1(UΛ~UT) UTk(Λ˜)UT=2UΛ˜Tk−1(Λ˜)UT−UTk−1(Λ˜)UT=2(UΛ˜UT)[UTk−1(Λ˜)UT]−UTk−1(Λ˜)UT=2(UΛ˜UT)Tk−1(UΛ˜UT)−Tk−1(UΛ˜UT)=Tk(UΛ˜UT)\begin{aligned}U T_k (\tilde{\Lambda}) U^T &= 2U \tilde{\Lambda} T_{k-1}(\tilde{\Lambda})U^T - U T_{k-1}(\tilde{\Lambda}) U^T \\&= 2 (U \tilde{\Lambda} U^T) \left[U T_{k-1}(\tilde{\Lambda})U^T \right] - U T_{k-1}(\tilde{\Lambda}) U^T \\&= 2 (U \tilde{\Lambda} U^T) T_{k-1} (U \tilde{\Lambda} U^T) - T_{k-1} (U \tilde{\Lambda} U^T) \\&= T_k (U \tilde{\Lambda} U^T)\end{aligned}UTk(Λ~)UT=2UΛ~Tk−1(Λ~)UT−UTk−1(Λ~)UT=2(UΛ~UT)[UTk−1(Λ~)UT]−UTk−1(Λ~)UT=2(UΛ~UT)Tk−1(UΛ~UT)−Tk−1(UΛ~UT)=Tk(UΛ~UT) (2)已知 L˜=UΛ˜UT\tilde L= U \tilde{\Lambda} U^TL~=UΛ~UT (3)将(1)、(2)两式带入卷积公式: gθ∗x=UgθUTx=Ugθ(Λ)UTx=U(∑k=0KθkTK(Λ˜))UTx=(∑k=0KθkTK(UΛ˜UT))x=∑k=0KθkTK(L˜)x(5)\begin{aligned}g_\theta * x & = Ug_\theta U^Tx \\& = U g_{\theta}(Λ) U^Tx \\& =U (\sum^{K}_{k=0} \theta_kT_K(\tilde Λ)) U^Tx \\& = (\sum^{K}_{k=0} \theta_kT_K(U\tilde Λ U^T)) x \\& = \sum^{K}_{k=0} \theta_k T_K(\tilde L) x \qquad (5)\end{aligned}gθ∗x=UgθUTx=Ugθ(Λ)UTx=U(k=0∑KθkTK(Λ~))UTx=(k=0∑KθkTK(UΛ~UT))x=k=0∑KθkTK(L~)x(5) 8.3 一阶ChebNet(1stChebNet)-GCN一阶ChebNet源于论文(T. N. Kipf and M.Welling, “Semi-supervised classification with graph convolutional networks,” in Proceedings of the International Conference on Learning Representations, 2017)。这篇论文基于前面的工作,正式成为GCN的开山之作,后面很多变种都是基于这篇文章的。 该篇论文贡献有两点:
下面介绍ChebNet的一阶近似方法: x∗gθ=θ0x−θ1D−1/2AD−1/2xx*g_\theta = \theta_0x - \theta_1 D^{− 1 /2} AD^{− 1 /2}xx∗gθ=θ0x−θ1D−1/2AD−1/2x gθ∗x=θ(IN+D−1/2AD−1/2)xg_θ * x = θ (I_N + D^{− 1 /2} AD^{− 1 /2} ) xgθ∗x=θ(IN+D−1/2AD−1/2)x
为了解决该问题, 引入了一个renormalization trick(归一化技巧):
再加上一个激活函数,最后就可以得到了论文中的快速卷积公式:
推广:特征映射公式 Z=D˜−1/2A˜D˜−1/2XΘZ = \tilde D^{− 1 /2} \tilde A \tilde D^{− 1/ 2} XΘZ=D~−1/2A~D~−1/2XΘ
这个滤波操作复杂度是 O(∣E∣FC)O(|E|FC)O(∣E∣FC)(其中E为边数,C为特征向量维度,F为卷积核数量),并且A˜X\tilde AXA~X `可以有效地实现为密集矩阵和稀疏矩阵的乘积。(在源代码中使用了稀疏矩阵和稠密矩阵乘法) 带一阶滤波器的多层图卷积网络(GCN)的结构图如下图所示。 Input:Feature matrix X∈RN×DX \in \mathbb{R}^{N \times D}X∈RN×D,preprocessed adjacency matrix A˜\tilde AA~ 在看了上面的公式以及论文中的训练方法之后,并没有觉得GCN有多么特别,无非就是一个设计巧妙的公式,也许不用这么复杂的公式,多加一点训练数据或者把模型做深,也可能达到媲美的效果呢。 最后论文的附录里提到“even an untrained GCN model with random weights can serve as a powerful feature extractor for nodes in a graph”,可见即使不训练,完全使用随机初始化的参数W,GCN提取出来的特征就已经十分优秀了!这跟CNN不训练是完全不一样的,CNN不训练是根本得不到什么有效特征的。 然后作者做了一个实验,使用一个俱乐部会员的关系网络,使用随机初始化的GCN进行特征提取,得到各个node的embedding,然后可视化: 可以发现,在原数据中同类别的node,经过GCN的提取出的embedding,已经在空间上自动聚类了。 而这种聚类结果,可以和DeepWalk、node2vec这种经过复杂训练得到的node embedding的效果媲美了。 作者接着给每一类的node,提供仅仅一个标注样本,然后去训练,得到的可视化效果如下: GCN的一些特点1)、权值共享,参数共享,从AXWAXWAXW可以看出每一个节点的参数矩阵都是W,权值共享; 关于1stChebNet CGN的更多细节,可以参考博客: GCN的一些改进的变种1stChebNet的主要缺点是在批训练时,随着1stChebNet层数的增加,计算消耗成指数增加。最后一层的每一个节点都必须递归的在以前层中扩展他的邻居节点。 9. GCN代码分析和数据集Cora、Pubmed、Citeseer格式数据集格式见下一篇:GCN使用的数据集Cora、Citeseer、Pubmed、Tox21格式 代码分析见下一篇:图卷积网络GCN代码分析(Tensorflow版) 10. 从空间角度理解GCN前面介绍了GCN谱方法的推导以及背后的思路等,这是一种比较严谨和理论的方法。但是,其实可以发现,在傅立叶域上定义出来的GCN操作,其实也可以在空间域上进行理解,其就是所谓的消息传递机制,或者说每次从邻居中聚集信息然后对中心节点进行更新。 如下图所示,红色节点S1的邻居正是蓝色节点B1,B2,B3,这些邻居节点根据一定的规则将信息,也就是特征,汇总到红色节点上。 通常来说,会加入一个线性变换矩阵W,以作为汇聚节点特征的特征维度转换(或者说是映射),于是有 ∑u∈N(v)H(l)(u))W(l)\sum_{u \in \mathcal{N}(v)} H^{(l)}(u)) W^{(l)}u∈N(v)∑H(l)(u))W(l) σ(∑u∈N(v)H(l)(u))W(l))\sigma(\sum_{u \in \mathcal{N}(v)} H^{(l)}(u)) W^{(l)})σ(u∈N(v)∑H(l)(u))W(l)) H(l+1)=(H(l),A)=σ(AH(l)W(l))H ^{(l+1)}=(H^{(l)},A)=σ(A H^{(l)}W^{(l)})H(l+1)=(H(l),A)=σ(AH(l)W(l)) A˜=A+IN\tilde A=A+I_NA~=A+IN D˜ii=∑jA˜ij\tilde D_{ii}=∑_j \tilde A_{ij}D~ii=j∑A~ij A˜=D˜−1A˜\tilde A=\tilde D^{-1} \tilde AA~=D~−1A~ 这样就行归一化以后,对邻居的聚合就不是求和了而是求平均值。 还是考虑此图 A=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪010010101010010100001011110100000100⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪,D=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪200000030000002000000300000030000001⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪A=\left\{\begin{matrix}0 & 1 & 0 & 0 & 1 & 0\\1 & 0 & 1 & 0 & 1 & 0\\0 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1 & 1\\1 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 0 & 0\end{matrix}\right\},D=\left\{\begin{matrix}2 & 0 & 0 & 0 & 0 & 0\\0 & 3 & 0 & 0 & 0 & 0\\0 & 0 & 2 & 0 & 0 & 0\\0 & 0 & 0 & 3 & 0 & 0\\0 & 0 & 0 & 0 & 3 & 0\\0 & 0 & 0 & 0 & 0 & 1\end{matrix}\right\}A=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧010010101010010100001011110100000100⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫,D=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧200000030000002000000300000030000001⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫ A˜=A+IN=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪110010111010011100001111110110000101⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪,D˜=∑jA˜ij=D+IN=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪300000040000003000000400000040000002⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪\tilde A=A+I_N=\left\{\begin{matrix}1 & 1 & 0 & 0 & 1 & 0\\1 & 1 & 1 & 0 & 1 & 0\\0 & 1 & 1 & 1 & 0 & 0\\0 & 0 & 1 & 1 & 1 & 1\\1 & 1 & 0 & 1 & 1 & 0\\0 & 0 & 0 & 1 & 0 & 1\end{matrix}\right\},\tilde D=∑_j \tilde A_{ij}=D+I_N=\left\{\begin{matrix}3 & 0 & 0 & 0 & 0 & 0\\0 & 4 & 0 & 0 & 0 & 0\\0 & 0 & 3 & 0 & 0 & 0\\0 & 0 & 0 & 4 & 0 & 0\\0 & 0 & 0 & 0 & 4 & 0\\0 & 0 & 0 & 0 & 0 & 2\end{matrix}\right\}A~=A+IN=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧110010111010011100001111110110000101⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫,D~=j∑A~ij=D+IN=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧300000040000003000000400000040000002⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫ D˜−1A˜=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪1/30000001/40000001/30000001/40000001/40000001/2⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⋅⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪110010111010011100001111110110000101⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪1/31/4001/401/31/41/301/4001/41/31/400001/31/41/41/21/31/401/41/400001/401/2⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪\tilde D^{-1} \tilde A=\left\{\begin{matrix}1/3 & 0 & 0 & 0 & 0 & 0\\0 & 1/4 & 0 & 0 & 0 & 0\\0 & 0 & 1/3 & 0 & 0 & 0\\0 & 0 & 0 & 1/4 & 0 & 0\\0 & 0 & 0 & 0 & 1/4 & 0\\0 & 0 & 0 & 0 & 0 & 1/2\end{matrix}\right\}\cdot\left\{\begin{matrix}1 & 1 & 0 & 0 & 1 & 0\\1 & 1 & 1 & 0 & 1 & 0\\0 & 1 & 1 & 1 & 0 & 0\\0 & 0 & 1 & 1 & 1 & 1\\1 & 1 & 0 & 1 & 1 & 0\\0 & 0 & 0 & 1 & 0 & 1\end{matrix}\right\}=\left\{\begin{matrix}1/3 & 1/3 & 0 & 0 & 1/3 & 0\\1/4 & 1/4 & 1/4 & 0 & 1/4 & 0\\0 & 1/3 & 1/3 & 1/3 & 0 & 0\\0 & 0 & 1/4 & 1/4 & 1/4 & 1/4\\1/4 & 1/4 & 0 & 1/4 & 1/4 & 0\\0 & 0 & 0 & 1/2 & 0 & 1/2\end{matrix}\right\}D~−1A~=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧1/30000001/40000001/30000001/40000001/40000001/2⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫⋅⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧110010111010011100001111110110000101⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧1/31/4001/401/31/41/301/4001/41/31/400001/31/41/41/21/31/401/41/400001/401/2⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫ A˜=D˜−1/2A˜D−1/2\tilde A=\tilde D^{− 1 /2} \tilde A D^{− 1 /2}A~=D~−1/2A~D−1/2 D˜−1/2=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪13√00000014√00000013√00000014√00000014√00000012√⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪\tilde D^{-1/2}=\left\{\begin{matrix}\frac{1}{\sqrt{3}} & 0 & 0 & 0 & 0 & 0\\0 & \frac{1}{\sqrt{4}} & 0 & 0 & 0 & 0\\0 & 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0\\0 & 0 & 0 & \frac{1}{\sqrt{4}} & 0 & 0\\0 & 0 & 0 & 0 & \frac{1}{\sqrt{4}} & 0\\0 & 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}}\end{matrix}\right\}D~−1/2=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧310000004100000031000000410000004100000021⎭⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎫ A˜=D˜−1/2A˜D−1/2=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪13√00000014√00000013√00000014√00000014√00000012√⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⋅⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪110010111010011100001111110110000101⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⋅⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪13√00000014√00000013√00000014√00000014√00000012√⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪19√112√00112√0112√116√112√0116√00112√19√112√0000112√116√116√18√112√116√0116√116√000018√014√⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪\tilde A=\tilde D^{− 1 /2} \tilde A D^{− 1 /2}=\left\{\begin{matrix}\frac{1}{\sqrt{3}} & 0 & 0 & 0 & 0 & 0\\0 & \frac{1}{\sqrt{4}} & 0 & 0 & 0 & 0\\0 & 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0\\0 & 0 & 0 & \frac{1}{\sqrt{4}} & 0 & 0\\0 & 0 & 0 & 0 & \frac{1}{\sqrt{4}} & 0\\0 & 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}}\end{matrix}\right\}\cdot\left\{\begin{matrix}1 & 1 & 0 & 0 & 1 & 0\\1 & 1 & 1 & 0 & 1 & 0\\0 & 1 & 1 & 1 & 0 & 0\\0 & 0 & 1 & 1 & 1 & 1\\1 & 1 & 0 & 1 & 1 & 0\\0 & 0 & 0 & 1 & 0 & 1\end{matrix}\right\}\cdot\left\{\begin{matrix}\frac{1}{\sqrt{3}} & 0 & 0 & 0 & 0 & 0\\0 & \frac{1}{\sqrt{4}} & 0 & 0 & 0 & 0\\0 & 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0\\0 & 0 & 0 & \frac{1}{\sqrt{4}} & 0 & 0\\0 & 0 & 0 & 0 & \frac{1}{\sqrt{4}} & 0\\0 & 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}}\end{matrix}\right\}=\\\left\{\begin{matrix}\frac{1}{\sqrt{9}} & \frac{1}{\sqrt{12}} & 0 & 0 & \frac{1}{\sqrt{12}} & 0\\\frac{1}{\sqrt{12}} & \frac{1}{\sqrt{16}} & \frac{1}{\sqrt{12}} & 0 & \frac{1}{\sqrt{16}} & 0\\0 & \frac{1}{\sqrt{12}} & \frac{1}{\sqrt{9}} & \frac{1}{\sqrt{12}} & 0 & 0\\0 & 0 & \frac{1}{\sqrt{12}} & \frac{1}{\sqrt{16}} & \frac{1}{\sqrt{16}} & \frac{1}{\sqrt{8}}\\\frac{1}{\sqrt{12}} & \frac{1}{\sqrt{16}} & 0 & \frac{1}{\sqrt{16}} & \frac{1}{\sqrt{16}} & 0\\0 & 0 & 0 & \frac{1}{\sqrt{8}} & 0 & \frac{1}{\sqrt{4}}\end{matrix}\right\}A~=D~−1/2A~D−1/2=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧310000004100000031000000410000004100000021⎭⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎫⋅⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧110010111010011100001111110110000101⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫⋅⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧310000004100000031000000410000004100000021⎭⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎫=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧91121001210121161121016100121911210000121161161811211610161161000081041⎭⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎫ 对拉普拉斯矩阵进行对称标准化,有: Lsym:=D−1/2LD−1/2=D−1/2(D−A)D−1/2=In−D−1/2AD−1/2L^{sym} := D^{− 1 /2} L D^{− 1 /2} =D^{− 1 /2} (D-A) D^{− 1 /2} =I_n - D^{− 1 /2} A D^{− 1 /2}Lsym:=D−1/2LD−1/2=D−1/2(D−A)D−1/2=In−D−1/2AD−1/2 H(l+1)=f(Hl,A)=σ(D˜−1/2A˜D˜−1/2H(l)W(l))H ^{(l+1)} =f(H^l,A)=\sigma (\tilde D^{-1/2} \tilde A \tilde D^{ − 1/2} H^{(l)}W^{(l)} )H(l+1)=f(Hl,A)=σ(D~−1/2A~D~−1/2H(l)W(l)) 这就是GCN用谱方法推导出来的公式,这样就可以从空间结构的角度理解一阶ChebNet(GCN)了。 虽然从空间的角度理解似乎更简单,但是,知其然,还要知其所以然嘛。了解了GCN的谱方法的推导相信可以更深刻的理解GCN,也有利于做一些其他的研究。 11. GCN处理不同类型的图关于带权图问题GCN论文里的针对的是无权的无向图,并且采用的是平均聚合的方法,邻居之间没有权重。但是,现实生活中更多的是带权图。比如,我们都认识马化腾,但是张志东与马化腾的亲密度要比我们和马化腾的亲密度高得多。因此,可以预测张志东的工资比我们更接近马化腾。 不过GCN还是可以直接处理带权图,原来的邻居矩阵取值只能是0和1,现在可以取更多的权值。 关于有向图问题前面的都是针对于无向图的问题,所有拉普拉斯矩阵是对称矩阵,但是在有向图中,就不能定义拉普拉斯矩阵了。目前的两种解决思路: (b)如果只是为了应用,有其他形式的GCN或者GAT可以处理有向图 值得说明的是:GAT作者写道“It is worth noting that, as Kipf & Welling (2017) and Atwood & Towsley (2016), our work can also be reformulated as a particular instance of MoNet (Monti et al., 2016). ” 也就是说本质上这些模型都可以认为是在重新定义了图的邻接关系后,再进行基本的卷积运算。 节点没有特征的图对于很多网络,可能没有节点的特征,这个时候也是可以使用GCN的,如论文中作者对那个俱乐部网络,采用的方法就是用单位矩阵 I替换特征矩阵X。 12. 问题讨论下面将总结一些常见的问题和回答,欢迎大佬们一起讨论 Q1:GCN中邻接矩阵为什么要归一化?A1:归一化解决了平均的问题。举个例子,如果把『我』看成当前节点,『我的朋友』看做『我』的相邻节点,要估算『我的工资』该怎么做呢?对邻居节点的工资进行加权后是求和,不能估算『我的工资』,求和的方式可能出现一个低端交际花员工的工资比一个朋友较少的大佬的工资更高。因此,进行归一化(D−1AD^{-1}AD−1A)取平均值,就可以更合理的估算『我的工资』。 Q2:GCN中邻接矩阵为什么要对称归一化,从前面计算的例子对称化后如何看出来归一化的特点?Q3:GCN中参数矩阵W的维度如何确定?由下列公式可知 Q4:为什么GCN里使用NELL数据集相比于其他三个的分类准确率这么低?Q5:目前GCN的分类准确率仅为80%左右,如何提高GCN在Citeseer、Cora、Pubmed、Nell上的分类准确率?最后,欢迎加微信进群交流,只为一起学习,不含任何商业推广。 资料下载多篇图卷积相关ppt下载 参考本文结合了知乎,博客,论文,百度百科,维基百科等多方面的参考重新做了一个整理,感谢在这之前一些大佬做出的总结,一些重要的参考如下: |
|