GNN

图深度学习笔记

1. 图信号处理民科

1.1 一维时序信号处理

1.1.1. 信号的分解与合成

一维时序信号即一个以时间为自变量的函数 $f(t):\mathbb{R}\to\mathbb{R}$​​，我们可以将信号分解为“若干个信号”的叠加. 经典的信号分析理论中, 此处的“若干个信号”通常被取做正弦波。简单来说，希望有一组基函数 $\mu_k(t)$​​, 对于任意一个$f(t)$​​​​ 都能进行拆解：

$$f(t)=\sum_{k=1}^{K}\alpha_k\mu_k(t)$$

注意此处的 $\mu_k(t)$ 是事先指定的。并且希望有一个简单的算法将 $\alpha_k$ 计算出来。类比与线性空间的情形，如果这些基函数 $\mu_k(t)$ 是单位正交的，那么系数$\alpha\_k=\langle f(t),\mu_k(t)\rangle$。假定选用的基函数为正弦波时，每个基函数还对应着一个频率 $\lambda_k$，上述分解中的系数 $\alpha_k$ 可以看作是该函数在 $\lambda_k$ ​频率下的幅值。

1.1.2. 一阶导数与二阶导数

对于一个连续可微函数 $f(t):\mathbb{R}\to\mathbb{R}$​，其一阶导数的定义为：

$$f'(t)=\lim_{h\to0^+}\frac{f(t+h)-f(t)}{h}=\lim_{h\to0^+}\frac{f(t)-f(t-h)}{h}$$

而二阶导数的定义为：

$$\Delta f(t)=f''(t)=\lim_{h\to0^+}{\frac{f'(t+h)-f'(t)}{h}}=\lim_{h\to0^+}{\frac{[f(t+h)-f(t)]-[f(t)-f(t-h)]}{h^2}}$$

我们将 $f$ 的定义域限制在整点上, 那么自然地定义：

$$\Delta f(n)=[f(n+1)-f(n)]+[f(n-1)-f(n)]$$

1.2. 图信号处理

为了将一维时序信号的某些概念引入到图上来，可以将一维信号看作是链状的图。在此之前，先约定图有关的记号：图 $G=(V, E)$​，$V$ ​为顶点集，用序号 $1,\ldots,N$ ​标识，$E$ ​为边集，邻接矩阵为 $A\in\mathbb{R}^{N\times N}$​，假定它是带权或是不带权的无向图，它的度矩阵为 $D$​。

1.2.1 图上的信号的分解与合成

首先，怎么定义图上的信号呢？注意到一维离散信号是定义在整数值上的函数，这些整数点相当于是节点，因此推广到图上自然是：定义在节点上的函数 $f:{1,\ldots,N}\to\mathbb{R}$​，或直接将其记为 $f\in\mathbb{R}^N$​​​。同样地，我们需要对图上的信号进行分解与合成。即：

$$f=\sum_{k=1}^{N}{\alpha_k\mu_k}$$

其中 $\mu_k\in\mathbb{R}^N$​，并且是单位正交的。这里，需要注意两点：

• 求和项数为 $N$​，这是为了保证每个图信号都能被分解
• 对于不同的图，$\mu_k$ 是不一样的，但 $\mu_k$ 是由 $G$ 所决定的。在一维信号处理中，$\mu_k$ 是固定的，因为其图结构为链状，是统一的。

由于 ${\mu_k}_{k=1}^N$ ​的单位正交性质，所以系数是可以用 $\alpha_k=\langle f,\mu_k\rangle$​ 直接得到。剩下的问题是 $\mu_k$ ​的频率是什么，以及不同的图怎么计算出这些 $\mu_k$​。下面先直接给出上述问题的答案：定义图的拉普拉斯矩阵$L=D-A$​, 对$L$​做特征值分解$L=U\Lambda U^T$​, 其中$U$​为正交矩阵, $\Lambda$​为对角矩阵, 且依据特征值降序排列. 那么, $U$​的列向量集合${u_k}{k=1}^N$​即为上述的${\mu_k}{k=1}^{N}$​, 而$\mu_k$​对应的频率为$\Lambda$​的第$k$​个对角元素$\lambda_k$​. 因此分解系数$\alpha=U^Tf$​. 以下是对上述答案的解释, 至于这个做法是怎么来的, 留待后续理解.

1.2.1.1. 拉普拉斯矩阵

对于特征值分解:

$$L=U\Lambda U^T=\sum_{k=1}^{N}{\lambda_k u_k u_k^T}$$

拉普拉斯矩阵具有几个性质:

• 半正定性: $f^TLf=\frac{1}{2}\sum_{i,j}{w_{ij}(f_i-f_j)^2}\ge0$, 并且$\mathbf{1}\in\mathbb{R}^N$为对应于特征值为$0$的一个特征向量.

• 定义两种归一化拉普拉斯矩阵

  $$L_{sym}=D^{-1/2}LD^{-1/2},\quad L_{rw}=D^{-1}L$$

  其中$L_{sym}$的特征值介于$[0,2]$.

注意$f^TLf$被定义为信号$f$在图$G$上的平滑程度, 此定义在无权图上易于理解, 如果连着边的节点的信号值相近, 则平滑程度较好, $f^TLf$接近于$0$, 也代表着其频率较低.

1.2.1.2 图的基与频率

由于$f^T\Lambda f$可以视为信号的频率, 那么对于上述的基$U$, 它们的频率是什么呢?

$$u_k^TLu_k=\lambda_k$$

因此$\lambda_k$的确可以被解释为$u_k$的频率. 而对于一般的信号$f=\sum_{k=1}^N\alpha_k u_k$,

$$f^TLf=\sum_{i=1}^N\alpha_i^2\lambda_i$$

频率其实也代表着"能量", 频率越高, 能量越高. 因此, 平滑程度, 频率, 能量三种说法有着一定的联系.

2. 谱图卷积

谱图卷积的思路是将空间卷积转换为频谱的乘积, 有了上述基础, 对于一个信号$f$, 首先将其转换为频域信号$U^Tf$, 假设滤波在频域的系数为$\gamma$. 那么两者在空域的卷积结果为: $Udiag(\gamma)U^Tf$. 注意此处$\gamma$为要学习的参数, 参数量为$N$. 另外, 我们可以不直接学习$N$个参数, 而是定义一个函数$g_\theta:\mathbb{R}\to\mathbb{R}$, 其中$\theta$为参数, 而上述$\gamma_i=g_\theta(\lambda_i)$. 这样, 卷积的结果可以写做:

$$Ug_\theta(\Lambda)U^Tf=g_\theta(L)f$$

注意此处用到的是矩阵函数的定义, 并且$g_\theta$不必是多项式函数.

接下来, 类比图像中的卷积, 在空域上看, 卷积核是局部的, 但在频域上看, 这种局部的卷积核在频域上的支撑是"全局的", 图像卷积网络中的参数在空域上是局部的, 但它在频域上会是全局的, 以一维卷积为例, 假设卷积核为:

$$F(e^{\omega i})=\sum_k{f(k)e^{k\omega i}}$$

一本关于信号处理的书: http://www.dspguide.com/pdfbook.htm

(深入浅出图神经网络代码)https://github.com/FighterLYL/GraphNeuralNetwork

GRL book

chapter 2

传统提取特征的方法

2.1 图的统计特征与Kernel方法（用于节点以及图分类）

节点特征：度数，中心性，节点在motif中出现的次数

图特征：节点特征的统计特征例如直方图等，计算K次WL后得到节点特征后再聚合，计算图中graphlet（各类子图）出现的次数，随机k步游走得到的节点序列上的标签信息。

2.2 邻居/域重叠度检测（用于关系预测）

两节点相似度（局部）：重叠邻居数等

两节点相似度（全局）：两节点路径权重和（长度越长的路径所占的权重越小），使用类似于PageRank的思路得到 $P(u\to v)$​ 表示平稳状态下随机游走的概率，从而使用 $P(u\to v)+P(v\to u)$ ​计算$u$​与$v$​​的相似度。

2.3 图拉普拉斯矩阵与谱方法

$L=D-A,L_{sym}=D^{-1/2}LD^{-1/2},L_{RW}=D^{-1}L$

chapter 3 简单图（单关系类型单节点类型）的节点浅层表示学习

浅层Node Embedding，使用Encoder-Decoder-Similarity function-Loss function的范式，有些方法有基于矩阵分解的闭解式，有些没有。另外，similarity function有些直接定义成了邻接矩阵，有些是邻接矩阵的多项式，有些使用随机采样（随机游走）的方式估算相似度矩阵。具体的方法（按相似度矩阵的定义分类）有：

基于矩阵分解的

• Laplacian eigenmaps

• Graph Factorization

• GrapRep

• HOPE

基于随机游走的

• DeepWalk

• node2vec

• LINE

随机游走的策略可以定制化，理论证明DeepWalk方法的解以及node2vec方法的解与基于矩阵分解的方法存在接近性（即DeepWalk与node2vec的解可以用拉普拉斯矩阵的特征分解来表达）

浅层Encode：将节点编号，直接用编号映射为一个向量。这种编码器称为浅层的编码器。缺点主要有：1）参数量过大，与节点规模成正比，不能共参数；2）浅；3）图的节点增加的时候，新节点没有嵌入方法

chapter 4 多关系图的节点浅层表示

同样使用Encoder-Decoder-Similarity function-Loss function的范式，其中相似度函数一般直接定义为邻接矩阵（因为多关系情形下多跳路径不好妥善地定义），Loss function在实现上一般用负采样的方式进行，一般使用带有负采样项的交叉熵或负采样形式的Hinge loss。因此变化主要体现在Decoder上。具体的方法为

• TransE

• TransX

• RESCAL

• DistMult

• ComplEx

• RotatE