cs224w课程学习笔记-第8课

前言

根据上一节课我们知道目前最强的GIN在表征带环或对称图形时,无法完美区分出来不同的图形.本节课基于这个局限提出了引入图的结构信息,其代表方法是通过谱分解得到图的全局结构,说明GIN的局限的原因,并可以通过矩阵得到结构信息特征;此外根据上一节课我们知道当计算图一致时,表征结果一致,但当两个不同的节点虽然其计算图一样,但是其位置不同,我们希望得到不同的表征,这种情况我们就需要引入位置信息,虽然直接为节点分配一个ID 可行,但是在各方面性能比较下不佳,因此课中提出了通过锚点集得到位置信息(该处理接近原始距离信息),这样的位置信息是数值型的,更能有效的应用到模型里.该原理获取位置信息的常见方法有随机游走,注意力机制,图自编吗器等方法.

一、图结构信息引入

1、谱分解

首先介绍谱分解就是一个矩阵可以分解为特征值对角矩阵与正交特征向量矩阵相乘.

然后思考第一个问题为什么谱分解可以得到图的信息?
我们在第一节课里就知道图除了可以表示为G(V,E)的形式,还可以表示为相邻矩阵形式.根据图论可以知道图的结构可以通过与其相关的矩阵来表示。常用的矩阵包括:

• 邻接矩阵（Adjacency Matrix, A）： 如果图有 n 个顶点，邻接矩阵是一个 n×n 的矩阵，其中 $A_{ij}=1$ 如果顶点 i 和顶点 j 相连，否则$A_{ij}=0$ （无向图）。
• 拉普拉斯矩阵（Laplacian Matrix, L）： 定义为 L=D−A，其中 D 是度矩阵（对角矩阵，表示每个顶点的度数），A 是邻接矩阵。
  这些矩阵的特征值（Eigenvalues）和特征向量（Eigenvectors) 信息捕捉了图的许多结构性和代数性质。

思考第二个问题谱分解为什么可以反映带环(圈)与对称的结构?
在图中，圈可以看作是闭合路径（即，从某个顶点出发沿着边经过若干其他顶点最终回到起点的路径），其与图的代数结构有深刻联系。

• 基于特征值和迹（Trace）的圈计数:假设 A 是图的邻接矩阵。如果我们对 $A^k$的迹（trace，即矩阵对角线元素的和）进行计算，可以捕获所有长度为 k 的闭合路径的数量。这是因为矩阵的乘法将路径的信息编码在了结果矩阵的轨迹中。$tr(A^k)$可以表达为特征值的幂次和：
  $$tr(A^k)=\sum _{i=1}^n{\lambda }_i^k$$
• 此外圈的数目和组合信息也可以部分映射到图的拉普拉斯矩阵的行列式和特征值的性质

对称结构可以很明显的从邻接矩阵直接得到

思考第三个问题GIN的限制如何用谱分解理解?
前面两个问题可以知道谱分解有全面的图结构信息,那么GIN的局限是因为其没有包含谱分解里的结构信息吗?还是说是别的原因造成的?(如果是别的原因那么引入图结构信息也没用) 证明了这个问题,我们才能知道引入图结构是否能真正的打破GIN的局限性.
回忆一下GIN的函数,可以将其mlp单层展开,即参数矩阵W,然后将领域加和写为邻接矩阵乘的形式,自传递与邻域传递合并到一起,就成功改写为矩阵形式了.

接下来我们对邻接矩阵进行矩阵分解,写成特征值与特征向量相乘的方式,如下图所示,就可以发现当前的输出取决于特征值与特征向量跟上一层输出的的点积.设想第一层就无法分辨对称类信息的话,那么后续也就无法分辨了.

我们看第一层情况,其计算如下图所示,第一层的点积是特征向量与一个全1向量相乘,这里就会有问题,对于一个对称图，它的对称性质通常让某些特征向量表现为“对称模式”,会导致它们的元素的加和（与1内积）为零,换句话说该特征向量与全1向量正交。如此一来在第一层时对称的节点其特征值虽然不同,但是计算后均为0了.

以下面的图为例,其不同节点的特征值不一致,但是特征向量与全1向量点积后为0了,从而掩盖了特征值不同的信息,导致不同节点区分不了.

2、结构信息应用

上面已经证明了GIN网络确实在最初就缺失了对称或带环的信息,因此我们要补充结构信息,来缓解GIN网络的缺陷,那么有哪些方式去提取结构信息?

1. 直接对每个节点赋予ID号,然后使用onehot 作为特征引入模型中(也可以随机采样几维数据作为该节点的ID特征)
2. 计算每个节点参与的环数,如下图所示,节点的计算图里,记录每层根节点出现次数,这样可以区分出图中的三角环与四角环
3. 提取结构类特征,如相邻矩阵对角线的乘方(前面提到其揭示环的信息),聚类系数,中心性,pagerank等

哪个方式在应用中最合适呢?

1. 表示能力上:上述方法相比于普通数值特征均可有较强能力
2. 推断学习能力上:onehot方式无法适用新节点,其它信息均适用
3. 计算量上:onehot 较高,结构数值信息取决于具体的方法,数值类特征较低
4. 应用场景上:仅onehot方式有限制,适用于小图与无新节点的场景上

二、图位置信息引入

前面举的结构信息例子部分信息无法区分即对称又带环的场景,如果是下图这样,上述举例的环计算信息就无法识别了;因此我们从位置信息看如何区分出这种带环但是对称的情况

我们看的A,B两个节点,其计算图长得一样,但是他们的位置是不同的,比如我们以最右下角的节点为锚点,A到它的距离是2,而B到它的距离是1,这个信息就可以表明其位置不一样啦.这样想,如果有一组锚点是不是可以充分表示两个节点的距离关系,其已经有相关定理证明了这一结论,该定理叫布尔增益定理(Bourgain Theorem) 该定理说明，即使原始度量空间没有类似欧几里得空间的性质，也可以将其嵌入到一个维度为 $d=O(lo{g}^{2}n)$的欧几里得空间中（其中 n 是节点的数量），同时近似保留节点间的距离关系。

这样随机采样$lo{g}^{2}n$锚点,得到每个节点的位置信息嵌入,如下图例子所示.

在实际应用中,每一次训练都会对锚点进行重采样,这样新的锚点集也能够被学习到,同时在测试新的图,又会采样新的锚点集,从而保证了模型的推理性.

需要注意的是采样是随机采样的,这样会让每一次训练的位置向量内位置发生变化,因此要保持置换不变性才行.目前该类信息通过随机游走、图卷积网络、注意力机制和图自编码器等经典方法，可以保证随机采样过程中位置发生变化而输出相对不变性。未来，基于对比学习、Transformer、多模态融合和生成模型的位置信息提取方法将成为研究热点