Graph Convolutional Networks

GCN是GNN中比较常用的一种网络结构,其主要思想是将卷积操作迁移到图结构上以提取图的结构特征。

研究GCN的原因如下:

  • 图是一种定义拓扑关系的广义结构,可以表达丰富的结构特征
  • CNN的方法不能对图做卷积,图中每个顶点的相邻顶点数目都可能不同,无法用一个同样尺寸的卷积核来进行卷积运算

网络结构

图上的卷积操作大体上有如下两种思路

spatial domain

这里是将卷积做了一个概念上的泛化。这里有两个概念

  • aggregation:用邻居的特征更新当前节点下一层的hidden state
  • readout
    • 单个节点的表征
    • 聚合所有节点的特征,得到整个图的表征

根据aggregation和readout的不同,就有不同的算法

NN4G(Neural Networks for Graph. 2009)

aggregation:节点vv的第kk隐层节点值为

h(k)v=f(xvWk+uN(v)h(k1)uWk,k1)h(k)v=fxvWk+uN(v)h(k1)uWk,k1

其中,xvxv为节点vv的原始特征。

readout:将每一层的hidden state求均值,然后加权求和作为整个图的表征

DCNN(Diffusion-Convolution Neural Network. 2016)

DCNN将迭代看成是图上的扩散过程,每一层相当于在上一层的基础上再进行一跳。
aggregation:

h(k)v=f(Wk,vMEAN(d(v,.)=k))h(k)v=f(Wk,vMEAN(d(v,.)=k))

其中,MEAN(d(v,.)=k)MEAN(d(v,.)=k)表示与点vv距离为kk的节点的原始特征xx)的均值,这里注意不是用k1k1层的hidden state,而是原始特征。

readout:将每一层的hidden state拼成矩阵,所有的矩阵就是图的表征;单个节点对应的所有hidden state拼一起就是单个节点的表征

DGC(Diffusion Graph Convolution)

整体上与DCNN类似,唯一不同的是在readout阶段,表征不再用各个hidden state拼接的结果,而是用相加的结果

MoNet(Mixture Model Network. 2017)

aggregation:

  • 考虑了邻居的权重,不再使用邻居的简单相加,而是使用加权求和
  • 节点x,yx,y的边权重定义为:u(x,y)=(1deg(x),1deg(y))Tu(x,y)=(1deg(x),1deg(y))T,其中deg()deg()表示节点的度函数

readout:-

GAT(Graph Attention Network. 2017)

MoNet将权重写死了,GAT通过attention机制计算出邻居节点的权重。这是较为常用的一种方法

GIN(Graph Isomorphism Network. How Powerful are Graph Neural Networks?. 2019)

主要思想如下

  • aggregation的时候不要使用mean或者max pooling操作,而是使用sum。因为max、mean操作会丢失掉一些图的结构信息,比如3个2和4个2的均值、最大值都是2,但是和不一样
  • aggregation按如下公示计算
h(k)v=MLP(k)((1+ϵ(k))h(k1)v+uNvh(k1)u)h(k)v=MLP(k)((1+ϵ(k))h(k1)v+uNvh(k1)u)
spectrum domain

结论:

信号在时域上的卷积等价于其在频域上的乘法

所以,这种方法的思想是将图信号上的卷积操作转换到频域上的乘法操作,最后再逆转回去

谱图理论(vertex domain -> spectral domain)

给定包含NN个节点的图,定义A,DA,D分别为图的邻接矩阵和度矩阵。
定义图上的拉普拉斯矩阵:L=DAL=DA,对称,半正定。有如下特性

  • 对称矩阵一定N个线性无关的特征向量
  • 半正定矩阵的特征值一定非负
  • 对阵矩阵的特征向量相互正交

对这个矩阵做SVD分解得到L=UΛUTL=UΛUT(这里UT=U1UT=U1UUT=EUUT=E),其中Λ=diag(λ0,,λN1)Λ=diag(λ0,,λN1)U=[u0,,uN1]U=[u0,,uN1]为包含正交向量(列向量)的特征矩阵。λlλl可以看成频率概念,而ulul则是对应的基(basis)。[这里频率概念的解释可以参考文献1中的视频解释]

图傅立叶变换:给定信号xx,经过图傅立叶变换后得到(这里其实和PCA很像了)

ˆx=UTx^x=UTx

其中UU是上述的特征矩阵。图傅立叶逆变换则如下:

x=Uˆxx=U^x

有了经过图傅立叶变换的信号ˆx^x后,我们可以在频域上对信号做一个变换(滤波),简单的做法是做对应位相乘,引入参数θθ。为了表述统一,令gθ(Λ)gθ(Λ)为对角矩阵的对角θθ(参数写成ΛΛ只是为了和频率对上)。所以有

ˆy=gθ(Λ)ˆx=gθ(Λ)UTx^y=gθ(Λ)^x=gθ(Λ)UTx

再将频域信号转换到时域(或者说vertex domain),有

y=Uˆy=Ugθ(Λ)UTx=gθ(UΛUT)x=gθ(L)xy=U^y=Ugθ(Λ)UTx=gθ(UΛUT)x=gθ(L)x

所以,要学gθ()gθ()函数。这个函数的选取需要考虑两个方面

  • 参数规模:上述推导的参数规模是NN,不希望这么大
  • 局部视野特性:我们不希望当前节点能看到所有节点,所以函数不能分解成无限多项(因为矩阵LLNN次方表示当前节点可以看到任何连通节点的信息)

ChebNet

gθ(L)=Kk=0θkLkgθ(L)=Kk=0θkLk

优点:

  • 参数规模:O(K)
  • 局部视野特性:K-localized
    缺陷:
  • 复杂度问题:矩阵乘法复杂度为O(N^2),K次方下计算量大

根据Chebyshev多项式,满足

T0(ˆΛ)=I,I is identity matrixT1(ˆΛ)=ˆΛTk(ˆΛ)=2xTk1(ˆΛ)Tk2(ˆΛ)T0(^Λ)=I,I is identity matrixT1(^Λ)=^ΛTk(^Λ)=2xTk1(^Λ)Tk2(^Λ)

其中ˆΛ=2ΛλmaxI,ˆλ[1,1]^Λ=2ΛλmaxI,^λ[1,1]。这个公式可以利用推倒结构,以

y=Kk=0θkTk(ˆL)xy=Kk=0θkTk(^L)x(1)

代替原来的计算方式,降低计算复杂度。
每组θθ等价于一个filter,可以有多个filter,当作多个特征提取工具。


GCN是在公示1的基础上再做简化

  • 令K=1,即只考虑两项
  • ˆLLI^LLI,如果LL是normalized laplacian,有λmax2λmax2,又ˆL=2LλmaxI^L=2LλmaxI
  • 根据Symmetric normalized Laplacian定义有L=ID12AD12L=ID12AD12
  • 再次简化模型,令:θ=θ0=θ1θ=θ0=θ1
    • y=θ(I+D12AD12)xy=θ(I+D12AD12)x
  • 再次trick,I+D12AD12ˆD12ˆAˆD12I+D12AD12^D12^A^D12
    • ˆA=A+I^A=A+I
    • ˆDii=jˆAij^Dii=j^Aij,参考原paper
    • H(l+1)=σ(ˆD12ˆAˆD12H(l)W(l))H(l+1)=σ(^D12^A^D12H(l)W(l)),这里WW对应θθ

上面重写一下(邻域要包含自己):

hv=f(1|N(v)|uN(v)Wxu+b)hv=f1|N(v)|uN(v)Wxu+b

[1]. https://www.bilibili.com/video/BV1G54y1971S?p=2

[2]. SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

分享到