AGCN

接下来的几篇文章将会就对GCN从不同方面考虑进行优化进行介绍。首先介绍AGCN即Adaptive Graph Convolutional Neural Networks，该方法通过改变拉普拉斯矩阵优化GCN性能。

符号

$\mathcal{G}=(V,E)$， $L=I-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$，$L=U\mathrm{\Lambda }{U}^T$，Fourier transform:$\mathcal{F}=U^{T}x$

问题与解决思路

先前研究表明，$g_{\theta }=\sum _k^{K-1}{\theta }_k{\mathrm{\Lambda }}^k$，这是$K-$局部化的，并且${\theta }^k$控制了距离中心点远近与其重要性之间的联系。

WARNING

在上式表示中，默认距离是影响重要性衡量指标${\theta }^k$的唯一因素，使得重要性一圈一圈散布开来，这限制了卷积核的灵活性。同时，这假定了两个顶点相似性本质由选择的度量和特征域决定的。但数据本身是非欧式空间的，这表明以距离作为一种衡量或许并不是最优选择，连接节点间的相似性恐怕低于未连接节点(例如分子间化学键)。

解决
参数化$L$，将$L$中包含的图连通性、点度等拓扑信息转化为与特征值$X$，拉普兰拉丝矩阵有关的可学习参数。

$$g_{\theta }(\mathrm{\Lambda })=\sum _{k=0}^{K-1}(F(L,X,\mathrm{\Gamma }){)}^k$$

其中，$X$为特征，$L$为归一化拉普拉斯矩阵，$\mathrm{\Gamma }$为可学习参数。我们定义了新的SGC-LL层

$$y=U{g}_{\theta }(\mathrm{\Lambda })U^{T}X=U\sum _{k=0}^{K-1}(F(L,X,\mathrm{\Gamma }){)}^k{U}^{T}X$$

在对其进行设计时，由于欧式距离不再作为衡量相似性的最佳标准，我们利用广义马氏距离$D(x_i,x_j)=\sqrt{(x_i-x_j{)}^{T}M(x_i-x_j)}$，这里$M=w_d{w}_d^T$为一个半正定矩阵，其中$w_d$为我们设计的可学习参数向量。使用广义马氏距离下的高斯核$G_{x_i{x}_j}=\exp \frac{-D(x_i,x_j)}{2{\sigma }^2}$，其中${\sigma }^2$为距离方差。对$G$执行归一化操作，记结果为$\tilde{A}$。
由于在实际操作中，没有先验知识使我们能够合理的初始化$M$(由于一般情况下不同的领域需要不同$M_0$)，这会导致收敛时间长等一系列问题。在实践中，假设最优图$\hat{L}$与原始的拉普拉斯矩阵$L$相差不大，通过该假设

$$\hat{L}=L+L_{res}$$

我们只需要对$L_{r}es$进行学习即可，这里$L_{r}es=I-{\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$。 为了增加模型的表达能力，在卷积曾添加了线性变换层和偏置，即最终模型下

$$\begin{gathered} H^{(l+1)}=U{g}_{\theta }(\mathrm{\Lambda })U^T{H}^{(l)}XW+b \\ \hat{L}=L+\alpha L_{res} \end{gathered}$$

其中$W,b,M,\alpha为可学习的参数。

WARNING

因为$U$为一个稠密矩阵，对其运算增加算法复杂度。

解决
利用Chebychev expansion

说明

文中设计的SGC-LL层参数为$O(d_{i-1}\times d_i)$与$N$无关，可以接受。