图网络略述

其实开始冲图神经网络也已经有一段时间了，从半年前阅览《Relational inductive biases, deep learning, and graph networks》一文，对图网络有了一定的了解，到现在已经过去半年了。然而这半年中我一直在摸鱼，就算偶尔复习图神经网络的方法，也一直在复习相同的工作。先前有幸受实验室隔座的熊弟邀请参与一个研究，基于图网络和特征提取分离的类增量学习。但比较尴尬的是，我除了自诩知晓图网络以外，对实际的操作与应用一无所知。遂写下这篇文章，来昭示自己正式开始图网络的学习，并且尝试记录和融汇已知的知识点，不在浪费时间于重复的工作上，于是开始吧。

INTRO

首先，图网络是为什么产生的呢，通常，我们简略的称之为，方便表达结构化的知识，处理结构化的数据。这里的结构其实跟数据库及数据结构中描述的结构是相似的，即一种信息之间关联的结构，以及知识之间关联的结构。图拥有这样的特点，能通过节点来对实体进行描述，并用边描述实体之间的关系，与此同时还有着隐含信息的储存和全局信息的存在，于是构成了一个新颖且复杂的神经网络结构。

在周志华的机器学习一书半监督学习章节中，有对基本的图学习策略进行基本的描述，详见我为了应付课程考试整理的图半监督学习。其基本思路是这样的，通过”样本距离度量“刻画获取样本之间的联系，将样本嵌入到“图”，即样本即其关系的集合中。后通过图将半监督学习中有标记样本的标签对未标记样本进行传递，从而获取未标记样本的属性，进行学习。

如此，便定下来图网络的基本思路，即通过信息在图上的传递，迭代学习知识。有了这样的基础，我们便可以开始对图网络进行讨论了。

接下来，我们从最基础的部分来讲讲，信息是如何在图上进行传播的。

消息传递

那么，消息是什么呢？在大多数时候，我们将消息理解为节点（但其实在特定场合，边或者全局信息都是可以或者需要考虑的），即“实体”包含的，要传递的信息。对于一个结构相对复杂的节点而言，假设其拥有n个属性，我们便用一个n维的向量（或是其他什么） $\bold x$ 表示节点中储存的信息。然后，节点上的信息要怎么传递呢？

答案必然是通过节点之间的连接。

在离散数学中，我们使用邻接矩阵来刻画图上所有节点之间的联系，即Adjacency Matrix，记作 $\bold A$ 。在不考虑边权重的情况下，我们将存在节点 $x_i,x_j$ 之间的联系表示为 $A_{ij}=1$ ，在存在权重的情况下，我们将 $A_{ij}$ 的值记作两节点之间边的权重。值得注意的是， $\bold A$ 对角线上的值，即节点之间自连接的系数，在不做考虑自连接时都被记作0。

另外，我们特殊定义节点的度为该点所有连接权重之和，即 $D_i=\sum\limits_{j=0}^{n}A_{ij}$ ，使用对角矩阵 $\bold D=diag(D_1，D_2,\cdots,D_n)$ 进行统一描述。

如此，我们便通过了两个矩阵刻画了一张图上所有节点之间的传递关系。为了方便计算，以及因为种种特性，一张图最终的传递特性，被描述成了拉普拉斯矩阵 $\bold{L=D-A}$

我们通过拉普拉斯矩阵 $\bold L$ 来考虑图上的消息传递特性。

同时，我们可以理解为，拉普拉斯矩阵描述了图的结构。

归一化拉普拉斯矩阵

为了方便拉普拉斯矩阵在机器学习等众多需要迭代求解问题中的实际使用，我们要求对拉普拉斯矩阵进行归一化操作，从而避免在多次传递后导致的梯度爆炸和梯度消失。我们需要令其对角线上元素统一等于1。

我们已知的是，主对角线上的元素只会同 $\bold D$ 矩阵有关，因此，我们引入了 $\bold D^{-\frac{1}{2}}$ 作为归一化算子，令归一化拉普拉斯矩阵为

$\bold L^{sym} = \bold D^{-\frac{1}{2}}\bold L\bold D^{-\frac{1}{2}}=\bold I-\bold D^{-\frac{1}{2}}\bold A\bold D^{-\frac{1}{2}}$

$L_{ij}^{sym}=\begin{cases} 1&i=j\and deg(v_i)\neq0 \\-\frac{1}{\sqrt{deg(v_i)deg(v_j)}}&i\neq j\and v_i \ \text{adj}\ v_j \\0&else. \end{cases}$

现在，我们可以尝试用 $\bold L$ 对图进行表示了。

另外还有个随机游走归一化拉普拉斯矩阵 $\bold L^{sym} = \bold D^{-1}\bold L=\bold I-\bold D^{-1}\bold A$ ，不过我还不熟，暂时不管了

图的频域表示

其实挺意外的，早在去年的这个时候，我也考虑过这个问题。对图像的矩阵进行奇异值分解，通过切除部分奇异值，我们可以对图像中的低频和高频信息进行定量的剪切，使得减少储存信息的同时不丢失大部分画质。这样的特性是不是同信号的频域分析，即傅里叶变换有着相似之处。当时的我寻遍了全网，并没有得到甚么结果。而如今，我在做图的谱分析。

为了直观地对描述信号传播的图进行直观的“卷积滤波（需要注意的是，这里的卷积就不是图像意义上的卷积了，而是信号意义的卷积。但是在实际运用中图的卷积表示的也是信号在相邻图节点上的传播，这又与图像的卷积有着异曲同工之妙，那么新的问题来了，信号卷积和图像卷积是否也存在着甚么物理层面上的联系？）”我们通过特征分解，获取图的“频谱”，从这边开始，便是Spectral Graph Convolution的思想了。

我们将L矩阵进行特征分解，有

$\bold L = \bold{U\Lambda U}^\top$ ,其中特征值描述的是图像的频谱强度，而特征向量描述了分解的基底，即频率，对应频谱分析中的 $e^{-j\omega t}$ 。

于是，我们考虑滤波和滤波器，我们设计 $g_\theta=diag(\mathbf\theta)$ ，有滤波器改变了基底上信号的强度，即有 $g_\theta(\Lambda)$ 为特征值的函数。我们有 $g_\theta$ 在图 $\bold L$ 上对输入信号 $x$ 的卷积等于 $g_\theta、x$ 在频域相乘：

$g_\theta\star x=\bold U g_\theta\bold U^\top \bold x$

如此，我们完成了在图神经网络上进行分析的基础。

但是在实际问题下，这样的图是极难计算的，当我们的节点规模较大时，对N²规模的图进行矩阵分解，并且进行多次矩阵乘法需要消耗极大的资源，这使得图网络很难运行。因此纵使图网络有着其特殊的性质，其热度一直不是很高。

ChebNet

ChebNet的引入是当今神经网络大热门的开端，也是图卷积网络的基础。其思路为，使用切比雪夫多项式对卷积过程K阶拟合(参考)

ChebNet假设 $g_\theta$ 对 $\Lambda$ 的滤波结果是原始特征值多项式函数，而网络的目的是抛弃原本通过矩阵相乘来对卷积结果进行求解，而通过参数学习来对结果进行表示，给出下式

$\displaystyle g_\theta(\Lambda)=\sum_{k=0}^K\beta_kT_k(\hat\Lambda)=\left( \begin{matrix} \sum_{k=1}^{K}\beta_kT_k(\hat \lambda_1)& & \\ & ...& \\ & & \sum_{k=1}^{K}\beta_kT_k(\hat \lambda_n)\end{matrix} \right)$

其中有切比雪夫多项式在矩阵上的表示，具体数学背景可以详细查看

$T_0(L) = I\\ T_1(L)=L\\ T_{n+1}(L)=2LT_n(L) - T_{n-1}(L)$

有 $\beta_k$ 为网络的待学习参数

我们将原式 $g_\theta\star x=\bold U g_\theta\bold U^\top \bold x$ 表示为拟合形式 $\bold U \sum_{k=0}^K\beta_kT_k(\hat\Lambda)\bold U^\top \bold x$ ，并对其中无关输入信号 $\bold x$ 的部分进行改写

$\begin{array}\\&\bold U\sum_{k=0}^{K}\beta_kT_k(\bold {\hat \Lambda}) \bold U^\top\\ =&\sum_{k=0}^{K}\bold U\beta_k(\sum_{c=0}^k\alpha_{kc} \bold {\hat \Lambda}^k) \bold U^\top\\ =&\sum_{k=0}^{K}\beta_k(\sum_{c=0}^k\alpha_{kc} (\bold U\bold {\hat \Lambda} \bold U^\top)^k )\\ =&\sum_{k=0}^{K}\beta_kT_k(\bold U\bold {\hat \Lambda} \bold U^\top)\\=&\sum_{k=0}^{K}\beta_kT_k(\bold{\hat L})\end{array}$