1. GCN
1.1 Laplace算子
Laplace算子特征函数 -> Fourier变换 -> 卷积
Laplace矩阵L的特征向量 -> Fourier变换 -> 卷积
1.1.1 Laplace算子的特征空间
由变换的广义特征方程解得Laplace算子特征函数为。
于是变换在张成的特征空间中的变换是简单的拉伸变换。
将函数看做无穷维的向量,则映射到该特征空间的过程就是Fourier变换。
因为对的正交性,不同将投影到不同的基上,从而得到每个对应的投影值。
1.1.2 卷积公式
因为先推了逆变换,的组合,所以正变换加了个负号。
时移性质:时移-相移,频率成分不变、大小不变,但是相位移动。
卷积公式:
于是Laplace算子的特征空间中有卷积公式成立。这里主要用到指数函数的性质。
事实上,只要特征函数具有正交和指数形式,卷积公式就可以成立。于是想到构造一个二阶微分算子,把卷积推广到图上。
1.2 矩阵Laplace推广
Laplace算子是一个二阶梯度,本质上是计算变化率的变化率,而对应到图上的物理意义可以是热量变化的平滑程度。
热量变化应该与热量差正相关,如一维情况
多维情况同理。下面推广到图上。对于节点,有
其中是对角线为度的矩阵。定义为Laplace矩阵。
于是对进行特征分解:
其中的每一行为一个对应的特征向量。
仿照傅里叶变换,有
其中为节点对应的Embedding值。
于是整个卷积过程,可以描述为:
其中为卷积核,为各个节点的Embeding。
1.3 卷积核
1.3.1 朴素法
直接将看作参数进行训练,即变换后的卷积核为:
参数过多,计算量过大。
1.3.2 多项式近似法
从而有
减少了参数,引入了局部性,不需要分解。但求解仍然需要复杂度。
1.3.3 Chebyshev多项式近似卷积核
Chebyshev多项式就是余弦倍角展开公式,形式如下:
则,变换后的卷积核为:
可以用归纳法证明:
于是,Cheby递推的方式实现高阶效果,计算的复杂度为。
1.3.4 GCN
对Cheby核做限制:,则
进一步,限制,可得
因多层的乘积会导致方差偏移,数值不稳定,故需要重新进行正则化:
于是,最终的GCN卷积层为:
其中节点特征是维的,即;是维滤波器,为卷积结果。
理论十分复杂,但形式却十分简单。
GraphSAGE
GCN是transductive,训练时需要把全图结构和特征都读入,无法大规模训练。
GraphSAGE是inductive,训练时只使用样本点局部的特征与结构即可,通过采样限制数据结构不均衡。基本步骤如下:
- 采样:均等采样,指定采样邻居数量
- 聚合:效果最好的是均值聚合器,即对邻居embedding取均值,GCN其实是求和
- 更新参数
GraphSAGE和GCN其实都是复杂网络中的一个层。设计复杂网络时,要考虑Loss函数。对于有监督可以直接用交叉熵。对于无监督,假设相邻节点embedding尽量相同,则Loss函数为
其中为负采样分布,是负样本个数,是相应节点的embedding。
GAT
相比graphSAGE,增加了注意力机制,即按照一定权重聚合邻居传来的embedding。
邻居节点的权重计算通常使用中心节点和的属性相似度表示,并使用softmax进行归一化。如使用余弦相似度:
其中类似于一种bias。
而GAT实际使用
是一个非对称的注意力系数,就像条件概率一样。使用参数自动学习一个相似度函数。这里增加激活函数是为了避免softmax函数约去项。
这种计算相似度的加法模式,本质上两节点的计算是分离的。每一层的参数和是相同的,于是每个节点有一个特定的能量值,如果这个值很高,就跟其他所有节点都比较相似,具体相似程度要加上其他节点的这个值。
有种赢者通吃的感觉,幸福的家庭都是一样的,不幸的家庭却各有各的不幸。