《图神经网络导论》基础阅读笔记

引论

Graph neural network（GNN）图神经网络

Convolutional neural network （CNN）卷积神经网络 ：关键特点【局部连接、共享权重（开销更低）、多层结构（实现层次化模式）】

数学和图论基础

线性代数

基本概念

范数：衡量向量的长度

一范数-曼哈顿范数、二范数-欧式范数

$$\begin{array}{l} \|x\|_{p}: = \sqrt[p]{\left|x_{1}\right|^{p}+\cdots+\left|x_{n}\right|^{p}}, p \geq 1 \\ \|x\|_{1} = \left|x_{1}\right|+\cdots+\left|x_{n}\right| \\ \|x\|_{2} = \sqrt{\left|x_{1}\right|^{2}+\cdots+\left|x_{n}\right|^{2}} = \sqrt{x^{H} x} \\ \|x\|_{\infty} = \max _{1 \leq i \leq n}\left|x_{i}\right| \end{array}$$

阿达马积：

对于矩阵$A\,\epsilon\, \mathbb{R}^{m\times n}$和$B\,\epsilon\, \mathbb{R}^{m\times n}$，阿达马积$C\,\epsilon\, \mathbb{R}^{m\times n}$为：

$$C\,\epsilon\, \mathbb{R}^{m\times n} = A_{ij}B_{ij}$$

矩阵维度不一致

$$\begin{aligned} x \cdot y &=\left[\begin{array}{lll} x_{1} & \cdots & x_{n} \end{array}\right]\left[\begin{array}{lll} y_{1} & \cdots & y_{n} \end{array}\right] \\ &=\left[\begin{array}{llll} x_{1} y_{1} & \cdots & x_{n} y_{n} \end{array}\right] \\ x \cdot y &=\left[\begin{array}{llll} x_{1} & \cdots & x_{n} \end{array}\right]\left[\begin{array}{c} y_{1} \\ \cdots \\ y_{m} \end{array}\right] \\ &=\left[\begin{array}{llll} x_{1} y_{1} & \cdots & x_{n} y_{1} \\ \cdots & \cdots & \cdots \\ x_{1} y_{m} & \cdots & x_{n} y_{m} \end{array}\right] \\ x \cdot y &=\left[\begin{array}{llll} x_{11} & \cdots & x_{1 n} \\ \cdots & \cdots & \cdots \\ x_{m 1} & \cdots & x_{m n} \end{array}\right]\left[\begin{array}{ccc} y_{11} & \cdots & y_{1 n} \\ \cdots & \cdots & \cdots \\ y_{m 1} & \cdots & x_{n} \end{array}\right] \\ &=\left[\begin{array}{cccc} x_{11} y_{11} & \cdots & x_{1 n} y_{1 n} \\ \cdots & & \cdots & \cdots \\ x_{m 1} y_{m 1} & \cdots & x_{m n} y_{n n} \end{array}\right] \end{aligned}$$

参考博客：https://blog.csdn.net/rosefun96/article/details/104002386

特征分解

$$A\left[\begin{array}{llll} v_{1} & v_{2} & \cdots & v_{n} \end{array}\right]=\left[\begin{array}{llll} v_{1} & v_{2} & \cdots & v_{n} \end{array}\right]\left[\begin{array}{llll} \lambda_{1} & & & \\ & \lambda_{2} & & \\ & & \ddots & \\ & & & \lambda_{n} \end{array}\right]$$

$$A = \sum_{i=1}^{n}\lambda _{ i}v_{i}v_{i}^{T}$$

特征分解只能用于特定的矩阵

奇异值分解

概率论

基本概念和公式

条件概率

贝叶斯公式

链式法则（多变量条件概率）

期望：对于某个函数在一个特定概率分布$P(x)$下的平均值

$$\mathbb{E} \left [ f(x) \right ] =\sum_{x}^{} P(x)f(x)$$

衡量$f(x)$在期望周围散布情况：方差

$$Var(f(x)) = \mathbb{E} \left [ f(x)^{2} \right ]-\mathbb{E} \left [ f(x)^{2} \right ]^{2}$$

方差开根号称为“标准差”

协方差：描述两个变量共同变化的关联程度

$$Var(f(x)) = \mathbb{E} \left [ (f(x)-\mathbb{E} \left [ f(x) \right ])(g(y)-\mathbb{E} \left [ g(y) \right ]) \right ]$$

概率分布

正态分布：

$$f(x)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{(x-\mu)^{2}}{2 \sigma^{2}}\right)$$

二项分布：

$$P\{X=k\}=\left(\begin{array}{l} k \\ n \end{array}\right) p^{k}(1-p)^{n-k}$$

拉普拉斯分布：

$$f(x)=\frac{1}{2b} \exp \left(-\frac{|x-\mu|}{b}\right)$$

图论

$$G=(V,E)$$

邻接矩阵

$$A_{i j}=\left\{\begin{array}{ll} 1 & \left(\left(v_{i}, v_{j}\right) \in E \text { and } i \neq j\right) \\ 0 & (\text { otherwise }) \end{array}\right.$$

度矩阵

$$D_{ii}=d(v_{i})$$

拉普拉斯矩阵

$$L=D - A$$

$$L_{i j}=\left\{\begin{array}{ll} d\left(v_{i}\right) & (\mathrm{i}=\mathrm{j}) \\ -1 & \left(\left(v_{i}, v_{j}\right) \in E \text { and } i \neq j\right) \\ 0 & (\text { otherwise }) \end{array}\right.$$

对称归一化拉普拉斯矩阵

$$L^{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\\ =I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$$

矩阵元素：

$$L_{i j}^{\mathrm{sym}}=\left\{\begin{array}{ll} 1 & \left(i=j \text { 且 } d\left(v_{i}\right) \neq 0\right) \\ -\frac{1}{\sqrt{d\left(v_{i}\right) d\left(v_{j}\right)}} & \left(\left(v_{i}, v_{j}\right) \in E \text { and } i \neq j\right) \\ 0 & (\text { otherwise }) \end{array}\right.$$

随机游走归一化拉普拉斯矩阵

$$L^{rw}=D^{-1}L=I-D^{-1}A$$

矩阵元素：

$$L_{i j}^{\mathrm{TW}}=\left\{\begin{array}{ll} 1 & \left(i=j \text { and } d\left(v_{i}\right) \neq 0\right) \\ -\frac{1}{d\left(v_{i}\right)} & \left(\left(v_{i}, v_{j}\right) \in E \text { and } i \neq j\right) \\ 0 & (\text { otherwise }) \end{array}\right.$$

关联矩阵：$M \in \mathbb{R}^{m\times n}$

对于有向图

$$M_{i j}=\left\{\begin{array}{cl} 1 & \left(\exists k \text { s.t } e_{j}=\left(v_{i}, v_{k}\right)\right) \\ -1 & \left(\exists k \text { s.t } e_{j}=\left(v_{k}, v_{i}\right)\right) \\ 0 & (\text { otherwise }) \end{array}\right.$$

无向图

$$M_{i j}=\left\{\begin{array}{ll} 1 & \left(\exists k \text { s.t } e_{j}=\left(v_{i}, v_{k}\right)\right) \\ 0 & (\text { otherwise }) \end{array}\right.$$