图卷积网络 GCN Graph Convolutional Network(谱域GCN)的理解和详细推导-持续更新

2020年07月25日 阅读数:754
这篇文章主要向大家介绍图卷积网络 GCN Graph Convolutional Network(谱域GCN)的理解和详细推导-持续更新,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

文章目录

1. 为何会出现图卷积神经网络?

普通卷积神经网络研究的对象是具有Euclidean domains的数据,Euclidean domains data数据最显著的特征是他们具备规则的空间结构,如图片是规则的正方形,语音是规则的一维序列等,这些特征均可以用一维或二维的矩阵来表示,卷积神经网络处理起来比较高效。html

CNN的【平移不变性】在【非矩阵结构】数据上不适用node

  • 平移不变性(translation invariance):比较好理解,在用基础的分类结构好比ResNet、Inception给一只猫分类时,不管猫怎么扭曲、平移,最终识别出来的都是猫,输入怎么变形输出都不变这就是平移不变性,网络的层次越深这个特性会越明显。
  • 平移可变性(translation variance):针对目标检测的,好比一只猫从图片左侧移到了右侧,检测出的猫的坐标会发生变化就称为平移可变性。当卷积网络变深后最后一层卷积输出的feature map变小,物体在输入上的小偏移,通过N多层pooling后在最后的小feature map上会感知不到,这就是为何R-FCN原文会说网络变深平移可变性变差。

离散卷积本质就是一种加权求和。CNN中的卷积就是一种离散卷积,本质上就是利用一个共享参数的过滤器(kernel),经过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取,固然加权系数就是卷积核的权重系数(W)git

那么卷积核的系数如何肯定的呢?是随机化初值而后根据偏差函数经过反向传播梯度降低进行迭代优化。这是一个关键点,卷积核的参数经过优化求出才能实现特征提取的做用,GCN的理论很大一部分工做就是为了引入能够优化的卷积参数github

生活中不少数据不具有规则的空间结构,称为Non Euclidean data,如,推荐系统、电子交易、分子结构等抽象出来的图谱。这些图谱中的每一个节点链接不尽相同,有的节点有三个链接,有的节点只有一个链接,是不规则的结构。对于这些不规则的数据对象,普通卷积网络的效果不尽人意。CNN卷积操做配合pooling等在结构规则的图像等数据上效果显著,可是若是做者考虑非欧氏空间好比图(即graph,流形也是典型的非欧结构,这里做者只考虑图),就难以选取固定的卷积核来适应整个图的不规则性,如邻居节点数量的不肯定和节点顺序的不肯定。web

例如,社交网络很是适合用图数据来表达,如社交网络中节点以及节点与节点之间的关系,用户A(有ID信息等)、用户B、帖子都是节点,用户与用户之间的关系是关注,用户与帖子之间的关系多是发布或者转发。经过这样一个图谱,能够分析用户对什么人、什么事感兴趣,进一步实现推荐机制。算法

总结一下,图数据中的空间特征具备如下特色:
1) 节点特征:每一个节点有本身的特征;(体如今点上)
2) 结构特征:图数据中的每一个节点具备结构特征,即节点与节点存在必定的联系。(体如今边上)
总地来讲,图数据既要考虑节点信息,也要考虑结构信息,图卷积神经网络就能够自动化地既学习节点特征,又能学习节点与节点之间的关联信息网络

综上所述,GCN是要为除CV、NLP以外的任务提供一种处理、研究的模型。
图卷积的核心思想是利用『边的信息』对『节点信息』进行『聚合』从而生成新的『节点表示』。app

2. 图卷积网络的两种理解方式

GCN的本质目的就是用来提取拓扑图的空间特征。 而图卷积神经网络主要有两类,一类是基于空间域或顶点域vertex domain(spatial domain)的,另外一类则是基于频域或谱域spectral domain的。通俗点解释,空域能够类比到直接在图片的像素点上进行卷积,而频域能够类比到对图片进行傅里叶变换后,再进行卷积。框架

所谓的两类其实就是从两个不一样的角度理解,关于从空间角度的理解能够看本文的从空间角度理解GCNdom

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

认真读到这里,脑海中应该会浮现出一系列问题:
Q1 什么是Spectral graph theory?
Spectral graph theory请参考维基百科的介绍,简单的归纳就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质

Q2 GCN为何要利用Spectral graph theory?
这是论文(Semi-Supervised Classification with Graph Convolutional Networks)中的重点和难点,要理解这个问题须要大量的数学定义及推导

过程:
(1)定义graph上的Fourier Transformation傅里叶变换(利用Spectral graph theory,借助图的拉普拉斯矩阵的特征值和特征向量研究图的性质)
(2)定义graph上的convolution卷积

下面将介绍关于频谱域的图卷积网络的推导相关的内容。

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 A L=D-A
L中的元素给定为:
L i , j = { d i a g ( v i ) i = j 1 i j   a n d   v i   i s   a d j a c e n t   t o   v j 0 o t h e r w i s e L_{i,j}=\begin{cases} diag(v_i) & i=j\\ -1 & i \neq j \ and \ v_i \ is\ adjacent \ to \ v_j\\ 0 & otherwise \end{cases}
其中diag(vi) 表示顶点 i 的度。

对称归一化的拉普拉斯矩阵(Symmetric normalized Laplacian)

L s y s = D 1 / 2 L D 1 / 2 = I D 1 / 2 A D 1 / 2 L^{sys}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}
矩阵元素定义为:

L i , j s y s = { 1 i = j   a n d   d i a g ( v i )     0 1 d i a g ( v i ) d i a g ( v j ) i j   a n d   v i   i s   a d j a c e n t   t o   v j 0 o t h e r w i s e L^{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}

不少GCN的论文中应用的是这种拉普拉斯矩阵

随机游走归一化拉普拉斯矩阵(Random walk normalized Laplacian)

L r w = D 1 L = I D 1 A L^{rw}=D^{-1}L=I-D^{-1}A
矩阵元素定义为:

L i , j r w = { 1 i = j   a n d   d i a g ( v i )     0 1 d i a g ( v i ) i j   a n d   v i   i s   a d j a c e n t   t o   v j 0 o t h e r w i s e L^{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}

泛化的拉普拉斯 (Generalized Laplacian)

泛化的拉普拉斯(用得少)定义为:

{ Q i , j < 0 i     j   a n d   d i a g ( v i )     0 Q i , j = 0 i j   a n d   v i   i s   a d j a c e n t   t o   v j a n y n u m b e r o t h e r w i s e \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}

一个拉普拉斯矩阵的计算例子(依据于上图):

A = { 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 } D = { 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 } , L = D A = { 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 } 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\}

D 1 / 2 = { 1 2 0 0 0 0 0 0 1 3 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 3 0 0 0 0 0 0 1 3 0 0 0 0 0 0 1 } , L s y s = D 1 / 2 L D 1 / 2 = I D 1 / 2 A D 1 / 2 = { 1 1 6 0 1 6 0 0 1 6 1 1 6 0 1 9 0 0 1 6 1 1 6 0 0 1 6 0 1 6 1 1 9 1 3 0 1 9 0 1 9 1 0 0 0 0 1 3 0 1 } 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\}
能够看出,标准归一化的拉普拉斯矩阵仍是对称的,而且符合前面的公式定义。

Graph Convolution与Diffusion类似之处,固然从Random walk normalized Laplacian就能看出了二者确有类似之处(其实二者只差一个类似矩阵的变换,可参考Diffusion-Convolutional Neural Networks)
其实维基本科对Laplacian matrix的定义上写得很清楚,国内的一些介绍中只有第一种定义。这让我在最初看文献的过程当中感到一些的困惑,特地写下来,帮助你们避免再遇到相似的问题。

3.2 无向图的拉普拉斯矩阵有什么性质

(1)拉普拉斯矩阵是半正定矩阵。(最小特征值大于等于0)
(2)特征值中0出现的次数就是图连通区域的个数
(3)最小特征值是0,由于拉普拉斯矩阵(普通形式: L = D A L=D-A )每一行的和均为0,而且最小特征值对应的特征向量是每一个值全为1的向量
(4)最小非零特征值是图的代数连通度。

拉普拉斯矩阵的半正定性证实,以下:
要证实拉普拉斯矩阵是半正定的,只须要证实其二次型 f T L f 0 f^TLf \geq0
证实:
f T L f = f T D f f T A f = f T d i a g ( d ) f f T A f = i = 1 m d i f i 2 j = 1 m [ i = 1 m f j a i j ] f j = i = 1 m d i f i 2 i , j = 1 m f i f j a i j = 1 2 [ i = 1 m d i f i 2 2 i , j = 1 m f i f j a i j + j = 1 m d j f j 2 ] = 1 2 i , j = 1 m a i j ( f i f j ) 2 \begin{aligned} f^TLf & =f^TDf-f^TAf \\ & = f^T*diag(d)*f-f^TAf \\ & =\sum_{i=1}^m d_i f_i^2-\sum_{j=1}^m[\sum_{i=1}^m f_j*a_{ij}]f_j \\ & =\sum_{i=1}^m d_i f_i^2-\sum_{i,j=1}^m f_i*f_j*a_{ij} \\ & =\frac{1}{2} [ \sum_{i=1}^md_if_i^2-2\sum_{i,j=1}^m f_i f_j a_{ij}+\sum_{j=1}^m d_j f_j^2 ] \\ & = \frac{1}{2}\sum_{i,j=1}^m a_{ij}(f_i-f_j)^2 \\ \end{aligned}

因此,对于任意一个属于实向量 f R m f \in \mathbb{R}^m (f为m∗1的实数列向量 ),都有此公式成立:

f T L f = 1 2 i , j = 1 m a i j ( f i f j ) 2 f^TLf = \frac{1}{2}\sum_{i,j=1}^m a_{ij}(f_i-f_j)^2

3.3 为何GCN要用拉普拉斯矩阵?

  • 拉普拉斯矩阵是对称矩阵,能够进行特征分解(谱分解)
  • 因为卷积在傅里叶域的计算相对简单,为了在graph上作傅里叶变换,须要找到graph的连续的正交基对应于傅里叶变换的基,所以要使用拉普拉斯矩阵的特征向量。

3.4. 拉普拉斯矩阵的谱分解(特征分解)

GCN的核心基于拉普拉斯矩阵的谱分解,文献中对于这部份内容没有讲解太多,初学者可能会遇到很多误区,因此先了解一下特征分解。

特征分解(Eigendecomposition),又称谱分解(Spectral decomposition)是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有对可对角化矩阵或有n个线性无关的特征向量的矩阵才能够施以特征分解。

不是全部的矩阵均可以特征分解,其充要条件为n阶方阵存在n个线性无关的特征向量

可是拉普拉斯矩阵是半正定矩阵(半正定矩阵自己就是对称矩阵),有以下三个性质:

  • 对称矩阵必定n个线性无关的特征向量
  • 半正定矩阵的特征值必定非负
  • 对阵矩阵的不一样特征值对应的特征向量相互正交,这些正交的特征向量构成的矩阵为正交矩阵。

由上拉普拉斯矩阵对称知必定能够谱分解,且分解后有特殊的形式。

对于拉普拉斯矩阵其谱分解为:

L = U Λ U 1 = U [ λ 1 λ n ] U 1 L=U \Lambda U^{-1}=U \left[ \begin{matrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \\ \end{matrix} \right] U^{-1}
其中 U = ( u 1 , u 2 , , u n ) U=(\vec{u_1},\vec{u_2},\cdots,\vec{u_n}) ,是列向量为单位特征向量的矩阵,也就说 $ \vec{u_l} $是列向量,Λ是n个特征值构成的对角阵。

因为 U 是正交矩阵,即 U U T = E UU^{T}=E ,因此特征分解又能够写成:
L = U Λ U 1 = U Λ U T L=U \Lambda U^{-1}=U \Lambda U^{T}
注意,特征分解最右边的是特征矩阵的逆,只是拉普拉斯矩阵是对称矩阵才能够写成特征矩阵的转置。

3.5 拉普拉斯算子

定义:拉普拉斯算子是n维欧几里德空间中的一个二阶微分算子,定义为梯度( f \nabla f )的散度( f \nabla \cdot f ,即 f f \nabla f \cdot f )。所以若是f是二阶可微的实函数,则f的拉普拉斯算子∆定义为:

f = 2 f = f ∆f=\nabla^2 f=\nabla \cdot \nabla f
f的拉普拉斯算子也是笛卡尔坐标系xi中的全部非混合二阶偏导数:

f = i = 1 n 2 f x i 2 ∆f=\sum_{i=1}^n \frac{\partial^2f}{\partial x_i^2}
函数f的拉普拉斯算子也是该函数的海塞矩阵(是一个多元函数的二阶偏导数构成的方阵)的迹:
f = t r ( H ( f ) ) ∆f=tr(H(f))

拉普拉斯算子(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 ( τ ) 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\tau

4.2 离散形式的一维卷积

对于定义在整数 Z \mathbb{Z} 上的函数f,g,卷积定义为

( f g ) ( t ) = τ = f ( τ ) g ( t τ ) (f*g)(t)={\sum}_{\tau=-\infty}^{\infty}f(\tau)g(t-\tau)

4.3 实例:掷骰子问题

光看数学定义可能会以为很是抽象,下面举一个掷骰子的问题,该实例参考了知乎问题"如何通俗易懂地解释卷积"的回答。

想象如今有两个骰子,两个骰子分别是f跟g,f(1)表示骰子f向上一面为数字1的几率。同时抛掷这两个骰子1次,它们正面朝上数字和为4的几率是多少呢?相信读者很快就能想出它包含了三种状况,分别是:

  • f向上为1,g向上为3;
  • f向上为2,g向上为2;
  • f向上为3,g向上为1;

最后这三种状况出现的几率和即问题的答案,若是写成公式,就是 τ = 1 3 f ( τ ) g ( 4 τ ) \sum_{\tau=1}^{3}f(\tau)g(4-\tau) 。能够形象地绘制成下图:

若是稍微扩展一点,好比说认为 f(0) 或者 g(0)等是能够取到的,只是它们的值为0而已。那么该公式能够写成 τ = f ( τ ) g ( 4 τ ) \sum_{\tau=-\infty}^{\infty}f(\tau)g(4-\tau) 。仔细观察,这其实就是卷积(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)]

这么一看,是否是就对卷积的名字理解更深入了呢? 所谓卷积,其实就是把一个函数卷(翻)过来,而后与另外一个函数求内积。

对应到不一样方面,卷积能够有不一样的解释:g 既能够看做咱们在深度学习里常说的核(Kernel),也能够对应到信号处理中的滤波器(Filter)。而 f 能够是咱们所说的机器学习中的特征(Feature),也能够是信号处理中的信号(Signal)。f和g的卷积 (f∗g)就能够看做是对f的加权求和。下面两个动图就分别对应信号处理与深度学习中卷积操做的过程。

5. 傅里叶变换

5.1 连续形式的傅立叶变换

关于傅立叶变换相关的详细而有趣的内容,能够看这几篇文章:

下面是一个大体流程:
任意函数能够分解为奇偶函数之和:
f ( x ) = f ( x ) + f ( x ) 2 + f ( x ) f ( x ) 2 = f e v e n + f o d d f(x)=\frac{f(x)+f(-x)}{2} + \frac{f(x)-f(-x)}{2}=f_{even}+f_{odd}

任意一个周期函数能够由若干个正交函数(由 s i n , c o s sin, cos 构成)的线性组合构成,写出傅里叶级数的形式以下:
f ( x ) = a 0 + n = 1 ( a n c o s ( 2 π n T x ) + b n s i n ( 2 π n T x ) ) , a 0 R \displaystyle f(x)=a_0+\sum _{{n=1}}^{\infty}\left(a_{n}cos({\frac{2\pi n}{T}x})+b_{n}sin({\frac{2\pi n}{T}x})\right),a_0\in\mathbb{R}
利用欧拉公式 e i x = cos x + i sin x e^{ix}=\cos x+i \sin x (这里的指复数中的i), cos x , sin x \cos x, \sin x 可表示成

cos x = e i x + e i x 2 , sin x = e i x e i x 2 i \cos x=\frac{e^{ix} +e^{-ix}}{2} ,\sin x=\frac{e^{ix} -e^{-ix}}{2i}

在时间t轴上,把 e i t e^{it} 向量的虚部(也就是纵坐标)记录下来,获得的就是 s i n ( t ) sin(t)

在时间t轴上,把 e i 2 t e^{i2t} 向量的虚部记录下来,获得的就是 s i n ( 2 t ) sin(2t)

若是在时间t轴上,把 e i t e^{it} 的实部(横坐标)记录下来,获得的就是 c o s ( t ) cos(t) 的曲线:

更通常的,具备两种看待 s i n , c o s sin, cos 的角度:

e i ω t       { s i n ( ω t ) c o s ( ω t ) e^{i\omega t}\iff \begin{cases}sin(\omega t)\\cos(\omega t)\end{cases}

这两种角度,一个能够观察到旋转的频率,因此称为频域;一个能够看到流逝的时间,因此称为时域:

因此,任意周期函数能够以 e i ω t e^{i\omega t} 为基函数用傅里叶级数的指数形式表示。即,对于一个周期函数 f ( x ) f(x) 以傅里叶级数的指数形式表示为:
f ( x ) = n = c n 基的坐标 e i 2 π n x T 正交基 f(x)=\sum ^{\infty }_{n=-\infty }\underbrace{c_{n}}_{\text{基的坐标}} \cdot \underbrace{e^{i\tfrac{2\pi nx}{T}}}_{\text{正交基}}
可是对于非周期函数,并不能用傅里叶级数的形式表示。可是仍是用某个周期函数 f T ( x ) f_T(x) T T \rightarrow \infty 来逼近,即 lim T f T ( x ) = f ( x ) \lim_{T \rightarrow \infty} f_T(x)=f(x) ,用积分的形式能够表示为:

f ( x ) = [ + f ( x ) e i ω x d x ]   e i ω x d ω = F ( ω )   e i ω x d ω 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\omega
其中, F ( ω ) F( \omega ) 就是 f ( x ) f(x) 的连续形式的傅里叶变换
F ( ω ) = F [ f ( x ) ] = + f ( x ) e i ω x d x F( \omega ) =\mathcal{F}[f(x)]=\int ^{+\infty }_{-\infty } f(x)e^{-i\omega x} dx
能够看出, f ( x ) f(x) F ( ω ) F(\omega) 能够经过指定的积分运算相互表达。

固然,也能够利用欧拉公式经过cos和sin函数表示为 F ( u ) F(u)

F ( u ) = + f ( x ) [ c o s ( 2 π x u ) i s i n ( 2 π x u ) ] d x F(u)=\int_{-\infty}^{+\infty}f(x)\left[cos(2\pi xu)-i sin(2\pi xu)\right]dx

因此,对函数 f ( x ) f(x) 的傅里叶变换 F \mathcal{F} 和傅里叶的逆变换 F 1 \mathcal{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(\omega) 叫作 f ( x ) f(x) 象函数或傅里叶变换,即经过傅里叶变换后关于频率的函数,函数图像就是频谱图, ω \omega 就是f对应在频域中的频率
  • f ( x ) f(x) 叫作 F ( ω ) F(\omega) 的原象函数

其实能够发现这个对信号 f ( x ) f(x) 的傅立叶变换 F ( ω ) F(\omega) 形式上是 f ( x ) f(x) 与基函数 e i ω x e^{-i\omega x} 的积分,本质上将函数 f ( x ) f(x) 映射到了以 e i ω x e^{-i\omega x} 为基向量的空间中

5.2 频域(frequency domain)和时域(time domain)的理解

时域:真实量到的信号的时间轴,表明真实世界。

频域:为了作信号分析用的一种数学手段。

要理解时域和频域只须要看下面两张动图就能够了:

上图来自于维基百科,图中红色部分就是原函数f(x)在时域里面的曲线图,此函数通过傅里叶变换后能够分解成不少如右图中的曲线。在左图中的的蓝色线就是对应的频域中的频谱图。

频谱图里的竖线分别表明了不一样频率的正弦波函数,也就是以前的基,而高度则表明在这个频率上的振幅,也就是这个基上的坐标份量。

不少在时域看似不可能作到的数学操做,在频域相反很容易。这就是须要傅里叶变换的地方。尤为是从某条曲线中去除一些特定的频率成分,这在工程上称为滤波,是信号处理最重要的概念之一,只有在频域才能轻松的作到。

看一个傅里叶变换去噪的例子:
在傅里叶变换前,图像上有一些规律的条纹,直接在原图上去掉条纹有点困难,但咱们能够将图片经过傅里叶变换变到频谱图中,频谱图中那些规律的点就是原图中的背景条纹。

只要在频谱图中擦除这些点,就能够将背景条纹去掉,获得下图右侧的结果。

5.3 周期性离散傅里叶变换(Discrete Fourier Transform, DFT)

傅里叶变换有连续时间非周期傅里叶变换,连续时间周期性傅里叶变换,离散时间非周期傅里叶变换和离散时间周期性傅里叶变换,鉴于计算机主要处理离散周期性信号,本文主要介绍周期性离散时间傅里叶变换(DFT)。信号 x n x_n 的傅里叶变换 X k X_k

X k = n = 0 N 1 x n e i 2 π N k n X_k=\sum_{n=0}^{N-1}x_n e^{-i \frac{2\pi}{N}kn}
信号 x n x_n 用其傅里叶变换 X k X_k 表示为:
x n = n = 0 N 1 X k e i 2 π N k n x_n=\sum_{n=0}^{N-1}X_k e^{i \frac{2\pi}{N}kn}
其中

  • N表示傅里叶变换的点数
  • k表示傅里叶变换的第k个频谱

6. Graph上的傅里叶变换及卷积

把传统的傅里叶变换以及卷积迁移到Graph上来,核心工做其实就是把拉普拉斯算子的特征函数 e i ω t e^{-i\omega t} 变为Graph对应的拉普拉斯矩阵的特征向量。

傅立叶变换与拉普拉斯矩阵的关系:传统傅立叶变换的基,就是拉普拉斯矩阵的一组特征向量。

6.1 图上的傅里叶变换

前面讲到能够用一组正交函数cos和sin(或 e i ω t e^{-i\omega t} )表示任意函数,且傅里叶变换是连续形式的,在处理Graph时,用到的是傅里叶变换的离散形式。因为拉普拉斯矩阵进行谱分解之后,能够获得n个线性无关的特征向量,构成空间中的一组正交基,所以归一化拉普拉斯矩阵算子的特征向量构成了图傅里叶变换的基。图傅里叶变换将输入图的信号投影到了正交空间,至关于把图上定义的任意向量,表示成了拉普拉斯矩阵特征向量的线性组合。

离散积分就是一种内积形式,由此能够定义Graph上的傅里叶变换(实数域):
F ( λ l ) = f ^ ( λ l ) = i = 1 N f ( i ) u l ( i ) F(\lambda_l)=\hat{f}(\lambda_l)=\sum_{i=1}^{N}{f(i) u_l(i)}

  • f f 是Graph上的N维向量,能够表示某个点的特征向量, f ( i ) f(i) 表示第 i i 个特征
  • u l ( i ) u_l(i) 表示第 l l 个特征向量的第 i i 个份量
  • f f 的Graph 傅里叶变换就是与 λ l \lambda_l 对应的特征向量 u l u_l 进行内积运算
  • λ \lambda 就对应于 ω \omega (具体解释见第7部分)
  • f ^ \hat{f} 表示 f f 的傅里叶变换

6.2 图的傅立叶变换——图的傅立叶变换的矩阵形式

利用矩阵乘法将Graph上的傅里叶变换推广到矩阵形式:
( f ^ ( λ 1 ) f ^ ( λ 2 ) f ^ ( λ N ) ) = (   u 1 ( 1 ) u 1 ( 2 ) u 1 ( N ) u 2 ( 1 ) u 2 ( 2 ) u 2 ( N ) u N ( 1 ) u N ( 2 ) u N ( 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}\ u_1(1) &u_1(2)& \dots &u_1(N) \\u_2(1) &u_2(2)& \dots &u_2(N)\\ \vdots &\vdots &\ddots & \vdots\\ u_N(1) &u_N(2)& \dots &u_N(N) \end{matrix}\right)\left(\begin{matrix}f(1)\\ f(2) \\ \vdots \\f(N) \end{matrix}\right)
f f 在Graph上傅里叶变换的矩阵形式为:

f ^ = U T f ( a ) \hat{f}=U^Tf \qquad(a)

6.3 图的傅立叶逆变换——图的傅立叶逆变换的矩阵形式

相似地,传统的傅里叶变换是对频率 ω \omega 求积分:

F 1 [ F ( ω ) ] = 1 2 Π F ( ω ) e i ω t d ω \mathcal{F}^{-1}[F(\omega)]=\frac{1}{2\Pi}\int_{}^{}F(\omega)e^{i\omega t} d\omega

迁移到Graph上变为对特征值 λ l \lambda_l 求和:

f ( i ) = l = 1 N f ^ ( λ l ) u l ( i ) f(i)=\sum_{l=1}^{N}{\hat{f}(\lambda_l) u_l(i)}

利用矩阵乘法将Graph上的傅里叶逆变换推广到矩阵形式:

( f ( 1 ) f ( 2 ) f ( N ) ) = (   u 1 ( 1 ) u 2 ( 1 ) u N ( 1 ) u 1 ( 2 ) u 1 ( 2 ) u N ( 2 ) u 1 ( N ) u 2 ( N ) u N ( 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 在Graph上傅里叶逆变换的矩阵形式为:

f = U f ^ ( b ) f=U\hat{f} \qquad(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 g ) G = U ( ( U T g ) ( U T f ) ) (f*g)_G=U((U^T g)\cdot(U^Tf))
从上面能够看出,对卷积核 g g f f 进行傅里叶变换的结果 U T g , U T f U^T g,U^T f 都是一个列向量:

( 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)

因此,不少论文中的Graph卷积公式也写做:
( f g ) G = U ( ( U T g ) ( U T f ) ) (f*g)_G=U((U^Tg)\odot(U^Tf))
\odot 表示hadamard product(哈达马积),对于两个向量,就是进行内积运算;对于维度相同的两个矩阵,就是对应元素的乘积运算。

若是把 U T g U^Tg 总体看做可学习的卷积核,这里咱们把它写做 g θ g_\theta 。最终图上的卷积公式便是:

( f g ) G = U g θ U T f (f*g)_G = Ug_{\theta}U^Tf
有的地方,还把 g θ = U T g g_\theta=U^Tg 也成对角矩阵的形式,即定义一个滤波 g θ = d i a g ( U T g ) g_\theta=diag(U^T g) ,则:

f g θ = U g θ U T f = U ( g ^ ( λ 1 ) g ^ ( λ n ) ) U T f f*g_\theta=Ug_{\theta}U^Tf= U\left(\begin{matrix}\hat g(\lambda_1) & \\&\ddots \\ &&\hat g(\lambda_n) \end{matrix}\right) U^Tf

接下来第8节要介绍的图上频域卷积的工做,都是在 g θ g_\theta 的基础上作文章。

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 = U f ^ ( b ) f=U\hat{f} \qquad(b) 也能看出,graph傅里叶变换把graph上定义的任意向量f,表示成了拉普拉斯矩阵特征向量的线性组合,即:

f = f ^ ( 1 ) u 1 + f ^ ( 2 ) u 2 + + f ^ ( n ) u n f=\hat{f}(1)u_1+\hat{f}(2)u_2+\cdots +\hat{f}(n)u_n

那么:为何graph上任意的向量f均可以表示成这样的线性组合?

缘由在于 ( u 1 , u 2 , , u n ) (\vec{u_1},\vec{u_2},\cdots,\vec{u_n}) 是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 = 0 \lambda_1=0 ,由于 n 维的全1向量对应的特征值为0(由 L 的定义就能够得出):

L ( 1 1 1 ) = 0 L \left(\begin{matrix}1\\ 1 \\ \vdots \\1 \end{matrix}\right)=0

从特征方程的数学理解来看:

L u = λ u Lu=\lambda u

在由Graph肯定的 n 维空间中,越小的特征值 λ l \lambda_l 代表:拉普拉斯矩阵 L 其所对应的基 u l u_l 上的份量、“信息”越少,那么固然就是能够忽略的低频部分了。

其实图像压缩就是这个原理,把像素矩阵特征分解后,把小的特征值(低频部分)所有变成0,PCA降维也是一样的,把协方差矩阵特征分解后,按从大到小取出前K个特征值对应的特征向量做为新的“坐标轴”。

Graph Convolution的理论告一段落了,下面开始Graph Convolution Network

8. 深度学习中GCN的演变

Deep learning 中的Graph Convolution直接看上去会和第6节推导出的图卷积公式有很大的不一样,可是万变不离其宗,都是根据下式来推导的:
g θ x = U g θ U T x = U ( g ^ ( λ 1 ) g ^ ( λ n ) ) U T x g_\theta * x = Ug_\theta U^Tx =U\left(\begin{matrix}\hat g(\lambda_1) & \\&\ddots \\ &&\hat g(\lambda_n) \end{matrix}\right) U^T x

Deep learning 中的Convolution就是要设计含有trainable共享参数的kernel

上式计算量很大,由于特征向量矩阵U 的复杂度 O ( N 2 ) O(N^2) 。此外,对于大型图来讲,L特征值分解的计算量也很大

基于上面最原始的卷积公式,深度学习中的GCN主要是从下面几篇文章演变而来的(引用次数都很高),后面一一进行简单介绍:

  • 【1】Bruna, Joan, et al. “Spectral networks and locally connected networks on graphs.” 源于ICLR 2014(被引740次)
  • 【2】Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. “Convolutional neural networks on graphs with fast localized spectral filtering.” 源于NIPS 2016(被引997次)
  • 【3】Hammond, David K., Pierre Vandergheynst, and Rémi Gribonval. “Wavelets on graphs via spectral graph theory.” Applied and Computational Harmonic Analysis 30.2 (2011)(被引874次)
  • 【4】Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” 源于ICML 2017 (被引1537次)

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_\theta 看做是一个可学习参数的集合: g θ = Θ i , j k g_\theta=\Theta_{i,j}^k 。而且假设图信号是多维的,图卷积层顶定义为:

X : , j k + 1 = σ ( i = 1 f k 1 U Θ i , j k U T X : , i k ) ( j = 1 , 2 , , f k ) 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 k R N × f k 1 X^k\in \mathbb{R}^{N\times f_{k-1}} 是输入图信号,对应图上就是点的输入特征
  • N N 是节点数量
  • f k 1 f_{k-1} 是输入通道的数量
  • f k f_{k} 是输出通道的数量
  • Θ i , j k \Theta_{i,j}^k 是一个可学习参数的对角矩阵,就跟三层神经网络中的weight同样是任意的参数,经过初始化赋值而后利用偏差反向传播进行调整
  • σ ( ) \sigma(\cdot) 是激活函数

第一代的参数方法存在着一些弊端,主要在于:
(1)计算复杂:若是一个样本一个图,那么每一个样本都须要进行图的拉普拉斯矩阵的特征分解求U矩阵计算复杂;每一次前向传播,都要计算 U , d i a g ( θ l ) U,diag(\theta_l ) U T U^T 三者的乘积,特别是对于大规模的graph,计算的代价较高,须要 O ( n 2 ) \mathcal{O}(n^2) 的计算复杂度
(2)是非局部性链接的
(3)卷积核须要N个参数,当图中的节点N很大时是不可取的

因为以上的缺点第二代的卷积核设计应运而生。

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 θ ( Λ ) i = 0 K 1 θ i T k ( Λ ~ ) g_θ=g_θ(Λ) \approx \sum^{K-1}_{i=0} \theta_i T_k(\tilde Λ)
其实,就是利用Chebyshev多项式拟合卷积核的方法,来下降计算复杂度。

推导过程以下:
考虑信号 x R N x∈\mathbb{R}^N (x就是graph上对应于每一个顶点的feathure vector,即由数据集提取特征构成的向量,而不是和线性代数中常说的特征向量,注意区别)与以参数为 θ R N θ \in \mathbb{R}^N 的滤波器 g θ = d i a g ( θ ) g_θ=diag(θ) 在傅里叶域的谱卷积。

g θ x = U g θ U T x ( 3 ) g_\theta * x = Ug_\theta U^Tx \qquad (3)
其中

  • U 是对称归一化的拉普拉斯(normalized graph Laplacian)算子 L = I N D 1 / 2 A D 1 / 2 = U Λ U T L=I_N−D^{−1/2}AD^{−1/2}=UΛU^T 的特征向量矩阵,Λ是由L的特征值构成的对角矩阵。

L = D 1 2 ( D A ) D 1 2 = D 1 2 D D 1 2 D 1 2 A D 1 2 = I N D 1 2 A D 1 2 \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}
因为normalized graph Laplacian矩阵L是实对称矩阵, 所以其特征向量矩阵U是正交矩阵,即 U U T = I N UU^T=I_N

  • U T x U^Tx 是x的傅里叶变换。
  • g θ g_θ 是由参数θ构成的对角矩阵diag(θ)。因为参数θ的肯定与L的特征值有关,做者认为 g θ g_θ 是特征值 Λ的一个函数,即令

g θ = g θ ( Λ ) g_θ=g_θ(Λ)

式3的计算量很大,由于特征向量矩阵U 的复杂度 O ( N 2 ) O(N^2) 。此外,对于大型图来讲,L特征值分解的计算量也很大
为了解决这个问题,Hammond et al.(2011) :Wavelets on graphs via spectral graph theory指出 g θ ( Λ ) g_θ(Λ) 能够很好的经过Chebyshev多项式 T k ( x ) T_k(x) 的Kth-阶截断展开来拟合,并对Λ进行scale使其元素位于[−1,1]

g θ ( Λ ) k = 0 K θ k T K ( Λ ~ ) ( 4 ) g_{\theta}(Λ) \approx \sum^{K}_{k=0} \theta_kT_K(\tilde Λ) \qquad (4)
其中

  • Λ ~ = 2 Λ / λ m a x I N \tilde Λ = 2Λ / λ_{max}− I_N (为缩放后的特征向量矩阵,缩放后范围是[−1,1],单位矩阵的特征值是n重1),缩放的目的是为了知足Chebyshev多项式 T k ( x ) T_k(x) K t h K^{th} 阶截断展开的条件:自变量范围须要在[−1,1]之间
  • λ m a x λ_{max} 是L 的最大特征值,也叫谱半径
  • θ R K θ∈\mathbb{R}^K 是切比雪夫系数的向量
  • Chebyshev多项式递归定义为 T k ( x ) = 2 x T k 1 ( x ) T k 2 ( x ) T_k(x) = 2xT_{k−1}(x) − T_{k−2}(x) , 其中 T 0 ( x ) = 1 T 1 ( x ) = x T_0(x)=1, T_1(x)=x

回到对信号x与滤波器 g θ g_{θ} 的卷积的定义,如今有:

g θ x = k = 0 K θ k T K ( L ~ ) x ( 5 ) g_{\theta} * x = \sum^{K}_{k=0} \theta_kT_K(\tilde L)x \qquad (5)
其中

  • L ~ = 2 L / λ m a x I N = U Λ ~ U T \tilde L= 2L / λ_{max}− I_N=U \tilde \Lambda U^T
  • 易证 ( U Λ U T ) k = U Λ k U T (UΛU^T)^k=UΛ^kU^T

如今,相比于第一种Spectral CNN:

  • 此表达式如今是K-localized,具备局部链接性,由于它是拉普拉斯算子中的Kth-阶多项式,即它仅取决于离中央节点(Kth阶邻域)最大K步的节点
  • T K ( L ~ ) x T_K(\tilde L)x 的复杂度是O(|E|),即与边数E呈线性关系,整个运算的复杂度是 O ( K E ) O(K|E|) 。当graph是稀疏图的时候,计算加速尤其明显,这个时候复杂度远低于 O ( n 2 ) O(n^2)

公式4到公式5的补充证实以下:
(1)先用数学概括法证实

U T k ( Λ ~ ) U T = T k ( U Λ ~ U T ) U T_k (\tilde{\Lambda}) U^T = T_k (U \tilde{\Lambda} U^T)
数学概括法思路:当n=1时显然成立,假设n=k时成立,只需证n=k+1时成立

证实:
根据切比雪夫多项式的定义, 已知
U T 0 ( Λ ~ ) U T = U U T = 1 = T 0 ( U Λ ~ U T ) U T 1 ( Λ ~ ) U T = U Λ ~ U T = T 1 ( U Λ ~ U T ) \begin{aligned} &U T_0(\tilde{\Lambda}) U^T = UU^T =1 = T_0(U \tilde{\Lambda} U^T) \\ &U T_1(\tilde{\Lambda}) U^T = U\tilde{\Lambda}U^T = T_1(U \tilde{\Lambda} U^T) \end{aligned}
假设对于任意k>1, 知足
U T k 2 ( Λ ~ ) U T = T k 2 ( U Λ ~ U T ) U T_{k-2} (\tilde{\Lambda}) U^T= T_{k-2} (U \tilde{\Lambda} U^T)

U T k 1 ( Λ ~ ) U T = T k 1 ( U Λ ~ U T ) U T_{k-1} (\tilde{\Lambda}) U^T= T_{k-1} (U \tilde{\Lambda} U^T)

U T k ( Λ ~ ) U T = 2 U Λ ~ T k 1 ( Λ ~ ) U T U T k 2 ( Λ ~ ) U T = 2 ( U Λ ~ U T ) [ U T k 1 ( Λ ~ ) U T ] U T k 2 ( Λ ~ ) U T = 2 ( U Λ ~ U T ) T k 1 ( U Λ ~ U T ) T k 2 ( U Λ ~ U T ) = T k ( U Λ ~ U T ) \begin{aligned} U T_k (\tilde{\Lambda}) U^T &= 2U \tilde{\Lambda} T_{k-1}(\tilde{\Lambda})U^T - U T_{k-2}(\tilde{\Lambda}) U^T \\ &= 2 (U \tilde{\Lambda} U^T) \left[U T_{k-1}(\tilde{\Lambda})U^T \right] - U T_{k-2}(\tilde{\Lambda}) U^T \\ &= 2 (U \tilde{\Lambda} U^T) T_{k-1} (U \tilde{\Lambda} U^T) - T_{k-2} (U \tilde{\Lambda} U^T) \\ &= T_k (U \tilde{\Lambda} U^T) \end{aligned}
所以,根据数学概括法, 证毕。

(2)已知

L ~ = U Λ ~ U T \tilde L= U \tilde{\Lambda} U^T

(3)将(1)、(2)两式带入卷积公式:

g θ x = U g θ U T x = U g θ ( Λ ) U T x = U ( k = 0 K θ k T K ( Λ ~ ) ) U T x = ( k = 0 K θ k T K ( U Λ ~ U T ) ) x = k = 0 K θ k T K ( 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}


8.3 CayleyNet

CayleyNet进一步应用了参数有理复合函数的Cayley多项式来捕获窄的频带。CayleyNet的谱图卷积定义为

x g θ = c 0 x + 2 Re { j = 1 r c j ( h L i I ) j ( h L + i I ) j x } \mathbf{x} *g_\theta=c_{0} \mathbf{x}+2 \operatorname{Re}\left\{\sum_{j=1}^{r} c_{j}(h \mathbf{L}-i \mathbf{I})^{j}(h \mathbf{L}+i \mathbf{I})^{-j} \mathbf{x}\right\}
其中

  • R e ( ) Re(\cdot) 为复数的实部
  • c 0 c_0 为实数
  • c j c_j 为复数
  • i i 为虚数
  • $h4`为控制Cayley滤波器频谱的参数

CayleyNet在保留空间局部性的同时,说明ChebNet能够看做是CayleyNet的一个特例。

8.4 一阶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的开山之做,后面不少变种都是基于这篇文章的。

该篇论文贡献有两点:

  • 做者对于直接操做于图结构数据的网络模型根据频谱图卷积(Hammond等人于2011年提出的Wavelets on graphs via spectral graph theory)使用一阶近似简化计算的方法,提出了一种简单有效的层式传播方法。
  • 做者验证了图结构神经网络模型可用于快速可扩展式的处理图数据中节点半监督分类问题,做者经过在一些公有数据集上验证了本身的方法的效率和准确率可以媲美现有的顶级半监督方法。

下面介绍ChebNet的一阶近似方法:
Kipf等人引入了一种一阶近似ChebNet。假设 K = 1 , λ m a x = 2 K=1,\lambda_{max}=2 ,则ChebNet卷积公式简化近似为:

x g θ = θ 0 x θ 1 D 1 / 2 A D 1 / 2 x x*g_\theta = \theta_0x - \theta_1 D^{− 1 /2} AD^{− 1 /2}x
为了抑制参数数量防止过拟合,1stChebNet假设 θ = θ 0 = θ 1 \theta=\theta_0=-\theta_1 ,图卷积的定义就近似为(这是简单的一阶模型):

g θ x = θ ( I N + D 1 / 2 A D 1 / 2 ) x g_θ * x = θ (I_N + D^{− 1 /2} AD^{− 1 /2} ) x
其中

  • I N + D 1 / 2 A D 1 / 2 I_N+D^{−1/2}AD^{−1/2} 是有范围[0,2]的特征值。所以,若是在深度神经网络模型中使用该算子,则反复应用该算子会致使数值不稳定(发散)和梯度爆炸/消失

为了解决该问题, 引入了一个renormalization trick:
I N + D 1 / 2 A D 1 / 2 A ~ = A + I N D ~ 1 / 2 A ~ D ~ 1 / 2 I_N+D^{−1/2}AD^{−1/2} \stackrel{\tilde A=A+I_N}{\longrightarrow} \tilde D^{−1/2} \tilde A \tilde D^{−1/2}
其中

  • A ~ = A + I N , D ~ i i = j A ~ i j \tilde A=A+I_N,\tilde D_{ii}=∑_j \tilde A_{ij} ,即图中加上自环

再加上一个激活函数,最后就能够获得了论文中的快速卷积公式:
H ( l + 1 ) = f ( H l , A ) = σ ( D ~ 1 / 2 A ~ D ~ 1 / 2 H ( 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)} )

  • W W 就是参数 θ \theta 参数矩阵

推广:特征映射公式
能够将这个定义推广到具备C个输入通道(即每一个节点的C维特征向量)的信号 X R N × C X∈\mathbb{R}^{N×C} 和 F 个滤波器或特征映射以下:

Z = D ~ 1 / 2 A ~ D ~ 1 / 2 X Θ Z = \tilde D^{− 1 /2} \tilde A \tilde D^{− 1/ 2} XΘ
其中

  • Θ R C × F Θ∈\mathbb{R}^{C×F} 是一个滤波器参数矩阵,其实就是参数矩阵W
  • Z R N × F Z∈\mathbb{R}^{N×F}