Deep Learning on Graphs: A Survey论文笔记

问题

图卷积

图信号有数学表示公式吗？使用图拉普拉斯矩阵表示
图信号变换到频域的过程是怎么实现的？
图上面为什么用红色和绿色表示不同的方向？长度又是如何确定的？竖线长度表示节点信号值的大小

突然好像看看图卷积的底层推导公式啊！！！！！

The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

术语表示

the element-wise multiplication 点乘 $X_1 \cdot X_2$

词汇说明

有向图，无向图，有权图，无权图，无符号图
transition matrix $P = D^{-1}A$ , 从概念上可以看出是 $P_{i,j}$ 一个从i节点出发，到达j节点随机游动的概率
节点 $v_i$ 的k邻居：是从节点 $v_i$ k步可到达的节点组成的集合。
图表示符号表
图滤波器的频率响应矩阵
图滤波器的频率响应函数
利用拉普拉斯矩阵对图滤波器H进行泰勒展开
哈达玛积：矩阵对应位置相乘

摘要信息

在图上使用深度学习的方法分类：
依据：模型结构和训练策略
分类：
1. graph recurrent neural networks, 图递归神经网络
2. graph convolutional networks, 图卷积神经网络
3. graph autoencoders, 图自编码器
4. graph reinforcement learning, and 图强化学习
5. graph adversarial methods.图对抗方法
  对于5种类别的描述：
  
  Graph RNNs通过在节点级或图级建模状态来捕获图的递归和序列模式。GCNs在不规则图结构上定义卷积和读出操作，以捕获常见的局部和全局结构模式。GAEs采用低秩图结构，并采用无监督的方法进行节点表示学习。Graph RL定义了基于图形的动作和奖励，以获得对图形任务的反馈，同时遵循约束条件。图对抗方法采用对抗训练技术去增强图模型泛化能力，并通过对抗攻击测试其鲁棒性
相关的总结工作：
- Bronstein等人[7]在流形上总结了一些早期的GCN方法和CNNs，并通过几何深度学习对其进行了全面的研究
- Battaglia等人[9]总结了如何使用一个称为图网络的统一框架来使用GNNs和GCNs进行关系推理
- Zhang等人[11]总结了一些GCNs
- Sun等人[12]简要回顾了图的对敌攻击

文章框架

在第2节中，我们将介绍本文中使用的符号并提供初步准备
3-7节，分别介绍Graph RNNs, GCNs, GAEs，Graph RL，graph adversarial methods
第8节，总结

主要内容

传统深度学习方法应用到Graph领域的几个挑战：
1. Irregular structures of graphs，非欧式结构数据，这个问题通常被成称为几何深度学习问题。
2. Heterogeneity and diversity of graphs. 图的多样性，对于不同的问题需要建立不同的图模型进行研究。
3. Large-scale graphs，如何建立与图大小呈线性时间复杂度模型
4. Incorporating interdisciplinary knowledge.利用领域知识解决问题可能使得模型设计复杂化
基于图的学习任务分类：
1. Node-focused tasks : node classification,link prediction, and node recommendation
2. Graph-focused tasks: graph classification, estimating various graph properties, and generating graphs(图的分类，估计各种图的属性，生成图)

GRAPH RECURRENT NEURAL NETWORKS
- Graph RNNs分类：
1. node-level RNNs 模式是位于节点级并由节点状态建模
2. graph-level RNNs 位于图级并由公共图状态建模
- Graph RNNs模型实例
- Node-level RNNs，又称作(graph neural networks,GNNs)
  递归状态更新：
  
  其中 $F$ 是需要学习的参数方程
  输出方程：
- graph-level RNNs
  
  [23]的作者建议添加一个具有惟一属性的特殊节点来表示整个Graph。
- 学习模型参数的方法：(半监督学习)
1. 使用Jacobi方法迭代求解(1)得到稳定点，
2. 使用Almeida-Pineda算法进行一步梯度下降来最小化目标函数
  重复迭代上述过程直到收敛
- GNN存在的问题
1. 根据巴拿赫不动点定理，我们要求得到的稳定点有且仅有一个，因此，对状态更新函数F的要求是收缩映射，但是这样的话，会限制模型表达能力。
2. 迭代得到稳定点计算开销很大
- 针对上述的问题，提出解决方案：(改进思路：利用局部邻域计算稳定节点状态和优化模型参数之间交替进行)
  [24]使用gated graph sequence neural networks，GGS-NNs，将迭代公式使用GRU改写，实现了收缩映射条件的消除，同时可以使用现代优化算法。
  新的状态更新方程为：
  
  同时采用序列到序列的方法，网络能够产生多个输出，从而可以用于解决序列问题。
  [25]SSE采用stochastic fixed-point gradient descent来加速训练过程。
- graph-level RNNs 目的是：生成图
  在图级神经网络中，不是对每个节点应用一个神经网络来学习节点的状态，而是对整个图应用单个神经网络来编码图的状态
  * 对应模型论文：
  1. [26]使用Graph RNNs应用到图生成问题中，采用两种RNN，一种是生成新节点，另一种是自回归生成新添加节点的边。优点是能够有效的从输入图中学习
  2. [27]DGNN使用具有时间感知能力的LSTM[39]来学习节点表示,当生成新的边时，DGNN使用LSTM更新两个交互节点及其近邻的表示，其优势在于：the time-aware LSTM could model the establishing orders and time intervals of edge formations well，反证就是能够扩展应用范围。
  3. 思路：和其他的架构结合：比如GCN或者GAE。应用这些的优势是什么？不知道啊！
  为了解决图的稀疏性问题，方法1：RMGCNN[28]对GCNs的结果应用LSTM逐步重构图，如图2所示。通过使用LSTM，来自图中不同部分的信息可以在很长的范围内扩散，而不需要那么多的GCN层。方法2：Dynamic GCN[29]应用LSTM在动态网络中收集不同时间片的GCNs结果，获取空间和时间图形信息。

GRAPH CONVOLUTIONAL NETWORKS
通过设计好的卷积和读出函数
主要的GCN以及对应的主要特征
图卷积操作

频谱卷积：使用图傅里叶变换或其扩展将节点的表示变换到谱域上
（1）图卷积，图上节点信号 $\bold{u}_1,\bold{u}_2 \in R^N$
其中Q是图拉普拉斯矩阵L的特征分解得到的特征向量组成的矩阵
（2）图滤波公式

（3）多层图卷积操作
$\mathbf{u}_{j}^{l+1}=\rho\left(\sum_{i=1}^{f_{l}} \mathbf{Q} \Theta_{i, j}^{l} \mathbf{Q}^{T} \mathbf{u}_{i}^{l}\right) j=1, \ldots, f_{l+1}$
其中
空间卷积：考虑节点邻域来进行卷积
也可以结合两者进行
$\mathbf{u}_{j}^{l+1}=\rho\left(\sum_{i=1}^{f_{l}} \mathbf{Q} \Theta_{i, j}^{l} \mathbf{Q}^{T} \mathbf{u}_{i}^{l}\right) j=1, \ldots, f_{l+1}$
多层图卷积操作
$\mathbf{u}_{j}^{l+1}=\rho\left(\sum_{i=1}^{f_{l}} \mathbf{Q} \Theta_{i, j}^{l} \mathbf{Q}^{T} \mathbf{u}_{i}^{l}\right) j=1, \ldots, f_{l+1}$
其中 $l$ 表示第 $l$ 层GCN， $\Theta=\Theta(\Lambda) \in \mathbb{R}^{N \times N}$ 是可学习滤波器参数，通过使用节点特性 $F^V$ 作为输入层，叠加多个GCN层,整体架构类似于CNN。理论分析表明，这种图形卷积运算的定义可以模拟CNNs的某些几何性质。

但是上述的卷积操作 $\Theta$ 的大小和节点数相关，Bruna[40]提出改进:
$\operatorname{diag}\left(\boldsymbol{\Theta}_{i, j}^{l}\right)=\mathcal{K} \alpha_{l, i, j}$
其中 $\mathcal{K}$ 是固定插值核， $\alpha_{l, i, j}$ 是可学习的插值系数，[41]中将这种改进推广到图不是给定的，而是使用监督或非监督方法[41]从原始特征构造而成。

依旧存在的问题：

需要计算拉普拉斯矩阵的全部特征向量，此外前向和后向传播的时间复杂度为 $O\left(N^{2}\right)$ ，因此这种方法不能扩展到大规模的图上，
滤波器依赖于图的特征基，所以参数不能在不同大小和结构的图之间共享。

为了解决上述提到的两个问题，两条线路+统一框架‘

解决效率问题-线路1

ChebNet：

$\boldsymbol{\Theta}(\boldsymbol{\Lambda})=\sum_{k=0}^{K} \theta_{k} \boldsymbol{\Lambda}^{k}$

其中可学习的参数为 $\theta_{k}$ ,K是多项式阶数

为了解决拉普拉斯矩阵特征分解问题使用Chebyshev expansion，切比雪夫多项式阶数，参见ChebNet文献
Kipf和Welling[43]进一步，仅使用一阶邻域简化了滤波，增加一个self-connection,并且堆叠的一阶近邻的效果能够实现和ChebNet相同的模型容量，但是更好的结果。
ChebNet的一个重大突破就是：它们将频谱图的卷积与空间结构联系起来，它们表明了当频谱卷积函数是多项式或一阶时，频谱图的卷积等价于空间卷积
GNN可以看作是大量具有相同层的GCN去达到一个稳定的状态，GCN有不同数量的层，并且每一层包含了不同的参数。
使用谱方法解决效率问题：CayleyNet，采用Cayley polynomials定义图卷积：
$\boldsymbol{\Theta}(\boldsymbol{\Lambda})=\theta_{0}+2 \operatorname{Re}\left\{\sum_{k=1}^{K} \theta_{k}\left(\theta_{h} \boldsymbol{\Lambda}-i \mathbf{I}\right)^{k}\left(\theta_{h} \boldsymbol{\Lambda}+i \mathbf{I}\right)^{k}\right\}$
这个优点就是：能够探测重要的窄带信息从而得到更好的结果。
GWNN：图小波神经网络，用图波小波变换代替频谱滤波器中的傅里叶变换:
$\mathbf{u}_{1} *_{G} \mathbf{u}_{2}=\psi\left(\left(\psi^{-1} \mathbf{u}_{1}\right) \odot\left(\psi^{-1} \mathbf{u}_{2}\right)\right)$
使用快速逼近（fast approximating algorithms）计算 $\psi$ 和 $\psi^{-1}$ ,计算复杂度为

$O(K M)$

将图卷积推广到任意大小的多个图

Neural FPs [46]使用一阶邻域，空间方法
$\mathbf{h}_{i}^{l+1}=\sigma\left(\sum_{j \in \hat{\mathcal{N}}(i)} \mathbf{h}_{j}^{l} \Theta^{l}\right)$
改进：
1. 其中参数 $\Theta$ 可以在不同的图之间共享，并且和图的大小没有关系
2. 具有不同度的节点学习不同的参数 $\Theta$ ,这种方法在小图上表现好，但是没有办法扩展到更大的图上。
PATCHY -SAN

想法：
1. 使用一个graph labeling procedure(比如Weisfeiler-Lehman kernel)来确定一个节点的顺序，然后使用预先定义的顺序将一个节点的邻居们排列成一行
2. 使用节点的k个邻居定义receptive field，接着采用一个1-D的CNN做卷积
想法存在的问题：
1. 卷积依赖图标记的过程，这个是未经学习的预处理步骤(LGCN提出采用字典顺序进行排序，SortPooling采用对所有节点进行排序)，
2. 我们可以从事的方向是：改进节点的排序方式，然后发论文。
DCNN

想法：
1. 将图卷积的特征基替换为扩散基，通过节点间的扩散转移概率来确定节点的邻居。
  $\mathbf{H}^{l+1}=\rho\left(\mathbf{P}^{K} \mathbf{H}^{l} \Theta^{l}\right)$
存在的问题：
1. 计算 $P^K$ 时间复杂度为 $O\left(N^{2} K\right)$ ，因此这种方法只适合小规模图。
DGCN

想法：
1. 在对偶图卷积网络中共同采用扩散和邻接基的方法，使用两种卷积，适用于单图问题。

统一的框架

MPNNs：

想法：
1. 使用消息传递函数在空间域进行图形卷积操作的统一框架
$\begin{array}{c} \mathbf{m}_{i}^{l+1}=\sum_{j \in \mathcal{N}(i)} \mathcal{F}^{l}\left(\mathbf{h}_{i}^{l}, \mathbf{h}_{j}^{l}, \mathbf{F}_{i, j}^{E}\right) \\ \mathbf{h}_{i}^{l+1}=\mathcal{G}^{l}\left(\mathbf{h}_{i}^{l}, \mathbf{m}_{i}^{l+1}\right) \end{array}$
$\mathcal{F}^l$ 是消息函数， $\mathcal{G}^{l}$ 是顶点更新函数。
1. 增加一个与所有节点连接的“主”节点以加速长距离的消息传递，并将隐藏的表示分割成不同的“塔”以提高泛化能力
优点：
1. 一种特殊的MPNNs变体可以在预测分子性质方面取得最先进的性能。
GraphSAGE

想法：
1. 使用多个聚合函数
  $\begin{aligned} \mathbf{m}_{i}^{l+1} &=\text { AGGREGATE }^{l}\left(\left\{\mathbf{h}_{j}^{l}, \forall j \in \mathcal{N}(i)\right\}\right) \\ & \mathbf{h}_{i}^{l+1}=\rho\left(\boldsymbol{\Theta}^{l}\left[\mathbf{h}_{i}^{l}, \mathbf{m}_{i}^{l+1}\right]\right) \end{aligned}$
  其中 $\text { AGGREGATE }(\cdot)$ 表示聚合函数。
  
  文中提出的三种聚合函数：
  - the element-wise mean
  - LSTM
  - max-pooling
  文中使用的LSTM需要确定邻居的次序，采用随机排序的方法，我们可以采用更好的方法。
Mixture model network (MoNet)

想法：Aggregating,相当于将邻居的信息集合的一起
1. 使用template matching将用于流型的CNN和GCNs进行匹配
GNs

想法：GNs引入了边缘表示和整个图的表示，涵盖框架更加一般。
1. 将节点、边和图的表示全部学习了，同时采取Aggregation策略，以及消息传递机制。
  $\begin{array}{c} \mathbf{m}_{i}^{l}=\mathcal{G}^{E \rightarrow V}\left(\left\{\mathbf{e}_{i j}^{l}, \forall j \in \mathcal{N}(i)\right\}\right), \mathbf{m}_{V}^{l}=\mathcal{G}^{V \rightarrow G}\left(\left\{\mathbf{h}_{i}^{l}, \forall v_{i} \in V\right\}\right) \\ \mathbf{m}_{E}^{l}=\mathcal{G}^{E \rightarrow G}\left(\left\{\mathbf{e}_{i j}^{l}, \forall\left(v_{i}, v_{j}\right) \in E\right\}\right), \mathbf{h}_{i}^{l+1}=\mathcal{F}^{V}\left(\mathbf{m}_{i}^{l}, \mathbf{h}_{i}^{l}, \mathbf{z}^{l}\right) \\ \mathbf{e}_{i j}^{l+1}=\mathcal{F}^{E}\left(\mathbf{e}_{i j}^{l}, \mathbf{h}_{i}^{l}, \mathbf{h}_{j}^{l}, \mathbf{z}^{l}\right), \mathbf{z}^{l+1}=\mathcal{F}^{G}\left(\mathbf{m}_{E}^{l}, \mathbf{m}_{V}^{l}, \mathbf{z}^{l}\right) \end{array}$

总结

主流的卷积操作框架论文MPNNs（21）,GraphSAGE （22）,GNs（27）

读出操作

什么是读出操作(readout operation)

使用图形卷积操作，可以学习有用的节点特征来解决许多基于节点的任务。但是，为了处理基于图像的任务，需要聚合节点信息以形成图形级表示。在文献中，这样的过程通常称为读出操作。

读出操作要求的顺序不变性(Order Invariance)

这个问题是图的同构问题，最著名的算法是quasipolynomial。

读出操作的方法

统计学(一阶矩统计 first-moment statistics)
1. 求和，求平均，取max-pooling
2. fuzzy histograms进行节点的表示
3. 使用FC(fully connected)layer作为最后一层，对节点表示的特征进行加权求和再做非线性，但是无法保证order invariance
Hierarchical Clustering（层次聚类）
1. density-based agglomerative clustering
2. multi-resolution spectral clustering
3. another greedy hierarchical clustering algorithm
4. merge two nodes at a time,along with a fast pooling method to rearrange the nodes into a balanced binary tree
5. adopted another hierarchical clustering method by performing eigendecomposition
这些方法都无法实现端到端学习，然后就有了能够训练的聚类方法。
1. DiffPool，将层次聚类做成可微分那样，看看人家这脑子
Imposing Orders and others
1. 最佳的节点顺序依然是正在研究中的课题，可以往下做。
2. GNN中增加一个连接到所有节点的特殊节点，GNs中接收所有节点和边的消息学习整个图的表示
3. set2set，还满足读出操作order invariant的要求，使用LSTM和注意力机制。能用的都用上，试试效果

总结

最简单：统计学基本操作
层次聚类+可训练的层次聚类(可以继续尝试)
GNN增加伪节点，或者使用强制次序

GCNs改进和讨论

注意力机制

graph attention network (GAT)

想法：
1. 更换卷积方式，采用学习方式
  
  将 $\mathbf{h}_{i}^{l+1}=\rho\left(\sum_{j \in \tilde{\mathcal{N}}(i)} \frac{1}{\sqrt{\tilde{\mathbf{D}}(i, i) \tilde{\mathbf{D}}(j, j)}} \mathbf{h}_{j}^{l} \Theta^{l}\right)$ 换成 $\mathbf{h}_{i}^{l+1}=\rho\left(\sum_{j \in \hat{\mathcal{N}}(i)} \alpha_{i j}^{l} \mathbf{h}_{j}^{l} \Theta^{l}\right)$ ,注意力系数通过学习得到
2. 作者使用multi-head attentions 去连接得到的结果
GaAN 在GAT基础上更进一步，对于不同的head学习不同的weights。
HAN使用了两种注意力机制
1. node-level attention
2. semantic-level attention

残差和跳跃连接

问题的由来：

GCNs最suitable的深度很有限，2-3层：原因在于：
1. 深层GCNs训练本身的难度
2. 过渡平滑问题，导致所有深层的节点具有相同的表示(注:在Graph Neural Networks: A Review of Methods and Applications中也提到平滑问题)
Kipf and Welling [43]借鉴ResNet增加残差连接
1. 将 $\mathbf{H}^{l+1}=\rho\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{l} \Theta^{l}\right)$ 换成 $\mathbf{H}^{l+1}=\rho\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{l} \Theta^{l}\right)+\mathbf{H}^{l}$ 去学习残差，这样能加深网络
Column network (CLN)也是残差连接的思路

公式使用 $\mathbf{h}_{i}^{l+1}=\boldsymbol{\alpha}_{i}^{l} \odot \widetilde{\mathbf{h}}_{i}^{l+1}+\left(1-\boldsymbol{\alpha}_{i}^{l}\right) \odot \mathbf{h}_{i}^{l}$ ,其中 $\boldsymbol{\alpha}_{i}^{l}$ 是权重集，和GGS-NNs很像，
PPNP 定义图卷积,将所有参数放在一个地方
$\mathbf{H}^{l+1}=(1-\alpha) \tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{l}+\alpha \mathbf{H}^{0}$
Jumping knowledge networks (JK-Nets)

采用的最后一层集合多层特征，使用GraphSGATE中提到的Aggregation函数
$\mathbf{h}_{i}^{\text {final }}=\operatorname{AGGREGATE}\left(\mathbf{h}_{i}^{0}, \mathbf{h}_{i}^{1}, \ldots, \mathbf{h}_{i}^{L}\right)$

边缘特征

边缘特征也用上，废物利用，物尽其用

离散边缘特征

思路：
1. 针对不同的边缘类型训练不同的参数，然后聚合结果
  
  对应网络
  1. Neural FPs不同度的节点训练不同参数，接着对结果进行求和。
  2. CLN在异质图中针对不同的边缘类型训练不同的参数，并对结果进行平均。
  3. ECC
  4. Relational GCNs (R-GCNs) 借鉴知识图
2. DCNN将边转换成节点处理
3. LGCN 构造line graph去包含边特征，并且在原始图和line graph上采用了两个GCNs
4. Kearnes et al. [55] 提出weave module，我觉得有点像GNs那种思路，在weave module中节点和边使用四种函数交换信息node-to-node (NN), node-to-edge (NE), edge-to-edge (EE) and edge-to-node (EN)，weave module是GNs的一种特例。

采样方法

问题的引入

在训练大规模图的GCNs时，一个关键的瓶颈是效率，由于许多真实图遵循power-law分布(即少数节点具有非常大的度)，其邻居的数量可以极其迅速地扩展。

抽样方法

neighborhood samplings：
1. GraphSAGE在训练过程中均匀地为每个节点==采样固定数量的邻居==，
2. PinSage在图上使用随机漫步(random walk)来采样邻居,
3. StochasticGCN采用the historical activations of the last batches as a control variate来减小采样方差。
layer-wise samplings
1. FastGCN将节点解释为i.i.d样本
2. Adapt：下层的抽样节点以其上层为条件;

Inductive Setting

什么是inductive setting？

在一种图上训练，在未见过的节点上test。这一目标的实现是通过学习给定特征上的映射函数来实现的，这个映射函数不依赖图的基，并且可以在节点和图之间进行迁移，可以参考GraphSAGE，GAT，GaAN以及FastGCN中验证inductive setting部分。不过当前的研究停留在 graphs with explicit features

可以研究的方向

out-of-sample problem

Theoretical Analysis,理解为什么GCNs有效

node-focused tasks

Li et al. [70]，using a special form of Laplacian smoothing，同时还提出了GCNs联合训练(co-training)和自我训练(self-training)的方法。
Wu et al. [71] ，从信号处理角度分析，将图卷积看作是一个固定的低通滤波器，去除掉所有的非线性，提出了一个简化的图卷积架构(SGC)：
$\mathbf{H}^{L}=\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}}\right)^{L} \mathbf{F}_{V} \boldsymbol{\Theta}$
不过，没有非线性，不具有非线性流型的学习能力，Maehara [72]又提出了GFNN模型，在上述的卷积之后增加一层MLP来补救这个问题。

graph-focused tasks

考察GCNs和graph Kernels之间的关系,比如 Weisfeiler-Lehman (WL)
kernel(Kipf and Welling [43] ，SortPooling [49])

general analysis

Scarselli et al.使用不同**函数GCN的VC维和RNNs具有相同的scale。
Chen et al. [65] 做了线性GCNs的优化设计，并说明了在特定的简化下，局部极小值非常接近全局最小值。
Verma and Zhang [94]分析GCNs算法的稳定性和泛化边界，并说明了图卷积滤波器的最大绝对值和图的大小没有关系的话，那么单层GCNs满足一致稳定。

Graph Autoencoders

Details

AE自编码器用于学习图节点的表示，将节点映射到R上。
隐含假设：图具有固有的，潜在的非线性低秩结构

Papers

AE(Autoencoders)

Deep Learning on Graphs: A Survey论文笔记

SAE(sparse autoencoder)
$\begin{aligned} \min _{\boldsymbol{\Theta}} \mathcal{L}_{2} &=\sum_{i=1}^{N}\|\mathbf{P}(i,:)-\hat{\mathbf{P}}(i,:)\|_{2} \\ \hat{\mathbf{P}}(i,:) &=\mathcal{G}\left(\mathbf{h}_{i}\right), \mathbf{h}_{i}=\mathcal{F}(\mathbf{P}(i,:)) \end{aligned}$
$\mathbf{h}_{i}$ 是获取的低维表示，然后施加k-means进行节点的聚类任务，比不用深度学习的方法要好，但是SAE是建立在incorrect theoretical analysis上的
Structure deep network embedding (SDNE)

理论基础：two nodes share similar latten representations if they have
similar neighborhoods, which is a well-studied concept in network
science known as collaborative filtering or triangle closure(协同滤波或者三角闭包)

根据上述的先验知识修改目标函数为：
$\min _{\Theta} \mathcal{L}_{2}+\alpha \sum_{i, j=1}^{N} \mathbf{A}(i, j)\left\|\mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2}$
同时，=对L2重构损失进行重写。
DNGR提出使用PPMI（positive pointwise mutual information）矩阵替换SAE中的P矩阵(transition matrix)，不过时间复杂度 $O\left(N^{2}\right)$ ，不适合大规模的图。
GC-MC 使用GCN作为编码器,使用简单的双线性函数作为解码器
DRNE
1. 利用LSTM直接聚合邻域信息重构低维节点向量
2. 损失函数 $\mathcal{L}=\sum_{i=1}^{N}\left\|\mathbf{h}_{i}-\operatorname{LSTM}\left(\left\{\mathbf{h}_{j} \mid j \in \mathcal{N}(i)\right\}\right)\right\|$
3. 基于节点的度对邻居节点进行排序
4. 对于具有很大度的节点来说，采用邻域采样技术防止overlong memory，比PageRank好。
Graph2Gauss (G2G)
1. 用高斯分布去获取节点的不确定信息，将节点特征映射到高斯分布的均值和方差上
2. 没有显式定义解码函数，而是通过在学习模型时增加约束
  $\begin{array}{c} \mathrm{KL}\left(\mathbf{h}_{j} \| \mathbf{h}_{i}\right)<\mathrm{KL}\left(\mathbf{h}_{j^{\prime}} \| \mathbf{h}_{i}\right) \\ \forall i, \forall j, \forall j^{\prime} \text { s.t. } d(i, j)<d\left(i, j^{\prime}\right), \end{array}$

VAE(Variational Autoencoders)

总结与感悟

希望找到，这些图神经网络的共性，得到一个通用的框架(注：展望未来，GNNs的基本思想有深刻的启发:正如后面将展示的，许多先进的GCNs实际上有类似于Eq.(1)的公式，遵循相同的框架，在相邻的节点邻里之间交换信息。实际上，GNNs和GCNs可以统一成一些通用框架，一个GNN相当于一个GCN，它使用相同的层来达到稳定状态。)

参考书阅读

图信号处理和图卷积神经网络

从3种视角理解矩阵乘法：内积视角，行视角和列视角，主要思想就是：将矩阵看成是元素来理解，非常简单
图的表示：需要表示节点特征和图的结构。利用图信号(是 $V \rightarrow R$ 映射，将图信号节点feature使用 $R^N$ 向量表示）表示节点的特征，使用图拉普拉斯矩阵来表示图的拓扑结构
- 图信号的总变差为 $TV(x)=x^TLx$
- 称拉普拉斯矩阵的特征向量为傅里叶基，利用图信号和第k个傅里叶基的内积可以得到在该基上的傅里叶系数
- 图位移算子
- 重归一化形式的拉普拉斯矩阵，在论文中semi-supervised classifacation with graph convolutional networks中证明可以有效防止多层网络优化时，出现的梯度消失和梯度爆炸问题。
- 图卷积层(GCN Layer)：增加参数化权重矩阵对输入的图信号进行仿射变换，得到：

Deep Learning on Graphs: A Survey论文笔记