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+∑u∈N(v)h(k−1)uWk,k−1)h(k)v=f⎛⎝xvWk+∑u∈N(v)h(k−1)uWk,k−1⎞⎠其中,xvxv为节点vv的原始特征。
readout:将每一层的hidden state求均值,然后加权求和作为整个图的表征
DCNN(Diffusion-Convolution Neural Network. 2016)
DCNN将迭代看成是图上的扩散过程,每一层相当于在上一层的基础上再进行一跳。
aggregation:
其中,MEAN(d(v,.)=k)MEAN(d(v,.)=k)表示与点vv距离为kk的节点的原始特征(xx)的均值,这里注意不是用k−1k−1层的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)=(1√deg(x),1√deg(y))Tu(x,y)=(1√deg(x),1√deg(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按如下公示计算
spectrum domain
结论:
信号在时域上的卷积等价于其在频域上的乘法
所以,这种方法的思想是将图信号上的卷积操作转换到频域上的乘法操作,最后再逆转回去
谱图理论(vertex domain -> spectral domain)
给定包含NN个节点的图,定义A,DA,D分别为图的邻接矩阵和度矩阵。
定义图上的拉普拉斯矩阵:L=D−AL=D−A,对称,半正定。有如下特性
- 对称矩阵一定N个线性无关的特征向量
- 半正定矩阵的特征值一定非负
- 对阵矩阵的特征向量相互正交
对这个矩阵做SVD分解得到L=UΛUTL=UΛUT(这里UT=U−1UT=U−1且UUT=EUUT=E),其中Λ=diag(λ0,…,λN−1)Λ=diag(λ0,…,λN−1),U=[u0,…,uN−1]U=[u0,…,uN−1]为包含正交向量(列向量)的特征矩阵。λ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,不希望这么大
- 局部视野特性:我们不希望当前节点能看到所有节点,所以函数不能分解成无限多项(因为矩阵LL的NN次方表示当前节点可以看到任何连通节点的信息)
ChebNet
gθ(L)=K∑k=0θkLkgθ(L)=K∑k=0θkLk优点:
- 参数规模:O(K)
- 局部视野特性:K-localized
缺陷: - 复杂度问题:矩阵乘法复杂度为O(N^2),K次方下计算量大
根据Chebyshev多项式,满足
T0(ˆΛ)=I,I is identity matrixT1(ˆΛ)=ˆΛTk(ˆΛ)=2xTk−1(ˆΛ)−Tk−2(ˆΛ)T0(^Λ)=I,I is identity matrixT1(^Λ)=^ΛTk(^Λ)=2xTk−1(^Λ)−Tk−2(^Λ)其中ˆΛ=2Λλmax−I,ˆλ∈[−1,1]^Λ=2Λλmax−I,^λ∈[−1,1]。这个公式可以利用推倒结构,以
y=K∑k=0θ′kTk(ˆL)xy=K∑k=0θ′kTk(^L)x(1)代替原来的计算方式,降低计算复杂度。
每组θθ等价于一个filter,可以有多个filter,当作多个特征提取工具。
GCN是在公示1的基础上再做简化
- 令K=1,即只考虑两项
- ˆL≈L−I^L≈L−I,如果LL是normalized laplacian,有λmax≈2λmax≈2,又ˆL=2Lλmax−I^L=2Lλmax−I
- 根据Symmetric normalized Laplacian定义有L=I−D−12AD−12L=I−D−12AD−12
- 再次简化模型,令:θ=θ′0=−θ′1θ=θ′0=−θ′1
- y=θ(I+D−12AD−12)xy=θ(I+D−12AD−12)x
- 再次trick,I+D−12AD−12→ˆD−12ˆAˆD−12I+D−12AD−12→^D−12^A^D−12
- ˆA=A+I^A=A+I
- ˆDii=∑jˆAij^Dii=∑j^Aij,参考原paper
- H(l+1)=σ(ˆD−12ˆAˆD−12H(l)W(l))H(l+1)=σ(^D−12^A^D−12H(l)W(l)),这里WW对应θθ
上面重写一下(邻域要包含自己):
hv=f(1|N(v)|∑u∈N(v)Wxu+b)hv=f⎛⎝1|N(v)|∑u∈N(v)Wxu+b⎞⎠[1]. https://www.bilibili.com/video/BV1G54y1971S?p=2
[2]. SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS