女神图开篇（Monica Bellucci）

GNN基础，写得很简略，主要做自己备忘。

零基础入门GNN，既是教程，也是总结

一、图表示学习

核心问题

图表示学习的目标：学习一个将图节点映射到embedding空间的映射函数（encoder)，使得在原始空间相似的点在特征空间也相似(similarity)。

两个关键问题：如何定义相似性？如何找到映射函数
最简单的encode方法：每个节点分配一个embedding向量，方法包括 deepwalk，Node2Vec
关键不同在于：如何定义节点相似性？怎样判定两个节点的相似性，例如可以看他们两点是否直接连接，是否是邻居，是否有相似的结构，或者其它

三大基本步骤如下：

经典模型

1.deepwalk

论文: 《DeepWalk: Online Learning of Social Representations，KDD' 14》
核心思想：图顶点随机游走生成序列，当成句子，用skip-gram做Word embedding 得到最后顶点嵌入表示。（算法流程如下

其它要点：

截断随机游走(truncated random walk)，实际上就是长度固定的随机游走。
随机游走好处：可以并行减少采样时间（大图）；适应局部变化

这篇论文算是network embedding的开山之作，它将NLP中词向量的思想借鉴过来做网络的节点表示，提供了一种新的思路，后面会有好几篇论文使用的也是这种思路，都是利用随机游走的特征构建概率模型，用词向量中Negative Sampling的思想解决相应问题。

2.Line

论文：《LINE: Large-scale Information Network Embedding》（msra 15
动机：当前研究着重于关注节点之间的一阶相似性，及两点之间是否直接相连，而忽略了其二阶相似性(即拥有许多共同的邻节点)。因此LINE模型就是为了在信息网络嵌入至低维空间时保留其一阶相似以及二阶相似。

核心步骤：

先定义一阶相似性。网络中的一阶相似性是两个顶点之间的局部点对的邻近度
再定义二阶相似性

损失函数：让原始空间的分布和嵌入空间的分布 KL散度最小。

3.Node2Vec

论文：《node2vec: Scalable Feature Learning for Networks KDD16》Jure
动机：deepwalk的随机游走方式太简单，有改进空间
创新点：提出用bfs和dfs的方法进行随机游走。BFS倾向于在初始节点的周围游走，可以反映出一个节点的邻居的微观特性；而DFS一般会跑的离初始节点越来越远，可以反映出一个节点邻居的宏观特性。

本文引入了两个参数用来控制随机游走产生的方式。根据p、q和之前的公式计算一个节点到它的邻居的转移概率。当p=1，q=1时，游走方式就等同于DeepWalk中的随机游走。 （见原始论文
本文其实思想跟DeepWalk是一样的，不过改进了DeepWalk中随机游走的生成方式，使得生成的随机游走可以反映深度优先和广度优先两种采样的特性，从而提高网络嵌入的效果。

二、GCN （spectral domain）

背景

动机：CV中的CNN可以提取图片空间信息，主要是因为卷积可以聚合像素邻居信息，现在想借用卷积的方法来提取图结构的拓扑信息。
问题：图数据复杂，图节点邻居不一样，怎样聚合邻居信息。
分类：Graph Convolutional Network（GCN）其实分为两大类。一种是基于谱域（spectral domain）分解方法；一种是直接加权聚合邻居信息（spatial domain）

基本原理

基于谱域（spectral domain）分解方法的GCN借用了传统的谱图方法。重点在于理解拉普拉斯矩阵和傅里叶变换的含义。

拉普拉斯矩阵

核心是图的拉普拉斯矩阵 $L=D-A$ ，其中D是图的度矩阵，A是图的邻接矩阵。拉普拉斯矩阵还有其它的归一化表示形式。如下图

可以看到拉普拉斯矩阵可以聚合邻居节点的信息。

傅里叶变换

Fourier Transform（FT变换）的作用。例如声音处理，男女混合原始声音进行FT变换到频域，去掉低频部分（男音多在低频区），将剩下的高频部分逆变换回去，就得到了女生的声音。
启示：有时候直接对信号处理很难，可以将信号FT变换变换到频域，在频域做处理，再逆变换回去。图结构可以当成图信号，GCN就是用的这种思路。
FT变换是怎么做的（如下图

图（无向图）的拉普拉斯矩阵 $L=D-A$ 是对称的，可以分解为 $L=U\Lambda U^T$ , 且有 $UU^T=I$ , $I$ 是单位矩阵。 $U=(\psi_1,\psi_2,\cdots,\psi_n)$ , $\psi_i$ 是矩阵的特征向量（线代知识）。 $U=(\psi_1,\psi_2,\cdots,\psi_n)$ 可以构成（类似）傅里叶变换的基矢

$Lx=U[\ \Lambda \ (U^T x)]$ , 理解这个公式就理解了GCN的一大半。

$x$ 是输入矩阵（节点features构成的矩阵），即图信号
$U^Tx$ 是对图信号做 FT变换，信号变换到了频域
$\Lambda \ (U^T x)$ 是对频域信号 $(U^T x)$ 做处理，这里 $\Lambda=(\lambda_1,\lambda_2,\cdots,\lambda_n)$ , $\lambda_i$ 是拉普拉斯矩阵的特征值，这里可以看作是倍数放大了频域信号
$U[\ \Lambda \ (U^T x)]$ 是对处理后的频域信号 $\Lambda \ (U^T x)$ 做 FT逆变换，又回到了原空间

$L^ix=U[\ \Lambda ^i \ (U^T x)]$ , $Lx$ 是聚合一阶邻居， $L^Nx$ 聚合 1到N阶邻居。

GCN演化

可参考

GCN三篇奠基性论文：

1.Spectral Networks and Locally Connected Networks on Graph（NIPS2014)
2.Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (NIPS 2016)
3.Semi-supervised classification with graph convolutional networks (ICLR 2017)

这个部分公式好多，懒得打了，看原来做的ppt图吧

这个写得不错

借鉴上面的思路，这里把之前的倍数变换换成了一个函数来做变换。

这里选取切比雪夫多项式做函数变换，且选取了一阶。论文说减少计算量效果好

进一步简化参数

最后的形式

可以上GCN公式了 ? H^{l+1} = \sigma(\tilde D ^{\frac{1}{2}} \tilde A \tilde D ^{\frac{1}{2}} H^{l}W ) ? 说明： $H_{l}$ 是第 L 层的节点embedding表示， W是训练参数

三、 GCN （spatial domain

经典模型

1.GraphSage

论文：《Inductive Representation Learning on Large Graphs》

参考

动机：大多数graph embedding框架是transductive(直推式的), 只能对一个固定的图生成embedding。这种transductive的方法不能对图中没有的新节点生成embedding。相对的，GraphSAGE是一个inductive（归纳式）框架，能够高效地利用节点的属性信息对新节点生成embedding。
统计机器学习可以分成两种: transductive learning, inductive learning. transductive learning: 在训练过程中，已知testing data（unlabelled data）是transductive learing inductive learning: 在训练过程中，并不知道testing data ，训练好模型后去解决未知的testing data 是inductive learing GNN中经典的DeepWalk, 上面GCN方法都是transductive learning。我们平时所说的learning一般指的是inductive learning。参考知乎
核心思想：通过学习一个对邻居顶点进行聚合表示的函数来产生目标顶点的embedding向量。

三个步骤：参考

对邻居节点采样
聚合邻居信息
得到图中各顶点的向量表示供下游任务使用

采样方法：出于对计算效率的考虑，对每个顶点采样一定数量的邻居顶点作为待聚合信息的顶点。设采样数量为k，若顶点邻居数少于k,则采用有放回的抽样方法，直到采样出k个顶点。若顶点邻居数大于k，则采用无放回的抽样。
聚合函数的选取：由于在图中顶点的邻居是天然无序的，所以我们希望构造出的聚合函数是对称的（即改变输入的顺序，函数的输出结果不变），同时具有较高的表达能力。论文实验了mean ，pool， lstm 三种聚合函数

参数学习: 论文有务监督学习和监督学习两种形式

无监督学习：基于图的损失函数希望临近的顶点具有相似的向量表示，同时让分离的顶点的表示尽可能区分。（选取一定的负采样

监督学习：监督学习形式根据任务的不同直接设置目标函数即可，如最常用的节点分类任务使用交叉熵损失函数。

2.GAT

论文：《Graph Attention Networks 》（ICLR 2018)
核心思想：聚合邻居节点用attention的方法，衡量不同节点features的权重。

参考1 参考2

核心在下面公式 ? e_{ij}=attention(Wh_i || W h_j) \qquad (1) \ \alpha_{ij} = softmax(LeaklyRelu(e_{ij})) \qquad (2) \ ? $h_i$ 是节点 i的表示， $w^{l}$ 是要学习的权重矩阵。节点 $j$ 是节点 $i$ 的邻居节点，两者做concatenate。然后对其做self-attention ，

具体见参考，思想其实挺简单的，懒得打公式了。