GNN

图深度学习笔记

1. 图信号处理民科

1.1 一维时序信号处理

1.1.1. 信号的分解与合成

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

f(t)=∑k=1Kαkμk(t)f(t)=\sum_{k=1}^{K}\alpha_k\mu_k(t)

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

1.1.2. 一阶导数与二阶导数

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

f′(t)=lim⁡h→0+f(t+h)−f(t)h=lim⁡h→0+f(t)−f(t−h)hf'(t)=\lim_{h\to0^+}\frac{f(t+h)-f(t)}{h}=\lim_{h\to0^+}\frac{f(t)-f(t-h)}{h}

而二阶导数的定义为：

Δf(t)=f′′(t)=lim⁡h→0+f′(t+h)−f′(t)h=lim⁡h→0+[f(t+h)−f(t)]−[f(t)−f(t−h)]h2\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}}

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

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

1.2. 图信号处理

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

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

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

f=∑k=1Nαkμkf=\sum_{k=1}^{N}{\alpha_k\mu_k}

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

  • 求和项数为 NN​，这是为了保证每个图信号都能被分解

  • 对于不同的图，μk\mu_k 是不一样的，但 μk\mu_k 是由 GG 所决定的。在一维信号处理中，μk\mu_k 是固定的，因为其图结构为链状，是统一的。

由于 μkk=1N{\mu_k}_{k=1}^N ​的单位正交性质，所以系数是可以用 αk=⟨f,μk⟩\alpha_k=\langle f,\mu_k\rangle​ 直接得到。剩下的问题是 μk\mu_k ​的频率是什么，以及不同的图怎么计算出这些 μ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ΛUT=∑k=1NλkukukTL=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$的一个特征向量.

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

    Lsym=D−1/2LD−1/2,Lrw=D−1LL_{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$, 它们的频率是什么呢?

ukTLuk=λku_k^TLu_k=\lambda_k

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

fTLf=∑i=1Nαi2λif^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θ(Λ)UTf=gθ(L)fUg_\theta(\Lambda)U^Tf=g_\theta(L)f

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

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

F(eωi)=∑kf(k)ekωiF(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→v)P(u\to v)​ 表示平稳状态下随机游走的概率，从而使用 P(u→v)+P(v→u)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

PreviousAudioNextCUDA

Last updated