谱域图卷积

实现思路

通过 f 1 ( t ) ☆ f 2 ( t ) = F − 1 [ F 1 ( w ) ⋅ F 2 ( w ) ] f_1(t)☆f_2(t) = F^{-1}[F_1(w) \cdot F_2(w)] f1(t)f2(t)=F1[F1(w)F2(w)]
其中 f 1 ( t ) f_1(t) f1(t)表示空域输入的信号, f 2 ( t ) f_2(t) f2(t)表示空域的卷积核, F 1 ( w ) F_1(w) F1(w)表示频域输入信号, F 2 ( w ) F_2(w) F2(w)表示频域卷积核, F − 1 F^{-1} F1表示傅里叶反变换。
即先将空域信息转换到谱域,然后相乘后,利用傅里叶反变换转回到空域。


如上图, L L L拉普拉斯矩阵,可以进行分解为特征向量和特征值表示。进行图卷积时,首先 x x x通过 U T U^T UT进行傅里叶变换转换到谱域,然后通过 g θ ( ⋅ ) g_\theta(\cdot) gθ()进行类似卷积操作,然后通过 U U U转换回空域获得结果。

经典谱域图卷积

  1. SCNN
    使用可学习的对角矩阵来代替谱域的卷积核。
    表达式: x ⋆ G g θ = U F U T x x \star_{G} g_{\theta}=U F U^{T} x xGgθ=UFUTx F F F为对角矩阵
  2. ChebNet
    采用切比雪夫多项式代替谱域的卷积核。
    表达式: x ⋆ G g θ = U g θ U T x = ∑ k = 0 K β k T k ( L ^ ) x x \star_{G} g_{\theta}=U g_{\theta} U^{T} x=\sum_{k=0}^{K} \beta_{k} T_{k}(\hat{L}) x xGgθ=UgθUTx=k=0KβkTk(L^)x
    β k \beta_{k} βk为可学习参数。 T k ( L ^ ) T_{k}(\hat {L}) Tk(L^)为拉普拉斯矩阵的切比雪夫表达式。
  3. GCN
    ChebNet的精简版,只考虑1阶的切比雪夫多项式,每个卷积核只有一个参数。
    表达式: x ⋆ G g θ = θ ( D ~ − 1 / 2 W ~ D ~ − 1 / 2 ) x x \star_{G} g_{\theta}=\theta\left(\tilde{D}^{-1 / 2} \tilde{W} \tilde{D}^{-1 / 2}\right) x xGgθ=θ(D~1/2W~D~1/2)x

谱域图卷积的缺陷

1.不适合有向图,但是现实生活大部分并非无向图,即 W i j ≠ W j i W_{ij}≠W_{ji} Wij=Wji,且若当图傅里叶无法使用,空域信息无法变为谱域信息,则图卷积也无法进行。
2.由于拉普拉斯的特征矩阵 U U U的不可变性,导致训练时,图的结构也不可以变化(边的权重,增删节点),但是现实生活中,往往图(社交网络数据)无时无刻不在变化。
3.以上的图谱网络卷积,SCNN计算量大,耗时;ChebNet和GCN虽然不需要图谱分解,但是用于学习的参数太简单,降低了模型的复杂度的同时也降低了性能。

谱域和空域图卷积比较

谱域图卷积
有图谱理论和卷积定理,将数据从空域转到谱域在操作,基础理论坚实。
空域图卷积
不依靠图谱理论,直接在空间定义卷积操作。直观却缺少理论依据。

空域图卷积

各类网络都有链接具体说明:

1.GNN
GNN的做法是将一个图结构的数据强行变化为一个类似规则的数据,从而实现1维的卷积。

2.GraphSAGE
通过采样和信息聚合来完成卷积操作,并且和GNN观点不同的是,聚合函数与输入的顺序无关,即邻域的结点无序。

3.GAT
GAT认为卷积可定义为利用注意力机制(attention)对邻域节点的有区别的聚合。

4.PGC
PGC认为卷积可以当做是特定的取样函数(sample function)与特定的权重函数(weight function)相乘后求和。

对比

GNN,GraphSAGE和GAT都不要求固定的图结构,即训练集和测试集的图结构可以不同。
PGC泛化能力较以上三种更强,虽然实验运用在固定的骨架图数据上,但是应当也是不需要固定图结构的。

空域卷积的特点

1.绕开了 图谱理论,无需将信号在空域和谱域之间转换;

2.直接在空域上定义卷积操作,更加直观;

3.没有图谱理论的束缚,定义更加灵活,方法更加多样;

4.和谱域图卷积相比,缺少数学理论支撑。