# 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