有向图，无向图，有权图，无权图，无符号图
transition matrix P = D − 1 A P = D^{-1}A P=D−1A, 从概念上可以看出是 P i , j P_{i,j} Pi,j一个从i节点出发，到达j节点随机游动的概率
节点 v i v_i vi的k邻居：是从节点 v i v_i vik步可到达的节点组成的集合。
图表示符号表
图滤波器的频率响应矩阵
图滤波器的频率响应函数
利用拉普拉斯矩阵对图滤波器H进行泰勒展开
哈达玛积：矩阵对应位置相乘
在第2节中，我们将介绍本文中使用的符号并提供初步准备 3-7节，分别介绍Graph RNNs, GCNs, GAEs，Graph RL，graph adversarial methods 第8节，总结
Graph RNNs模型实例
Node-level RNNs，又称作(graph neural networks,GNNs) 递归状态更新：
其中 F F F是需要学习的参数方程 输出方程：
graph-level RNNs
[23]的作者建议添加一个具有惟一属性的特殊节点来表示整个Graph。
学习模型参数的方法：(半监督学习)
使用Jacobi方法迭代求解(1)得到稳定点，使用Almeida-Pineda算法进行一步梯度下降来最小化目标函数 重复迭代上述过程直到收敛 GNN存在的问题 根据巴拿赫不动点定理，我们要求得到的稳定点有且仅有一个，因此，对状态更新函数F的要求是收缩映射，但是这样的话，会限制模型表达能力。迭代得到稳定点计算开销很大针对上述的问题，提出解决方案：(改进思路：利用局部邻域计算稳定节点状态和优化模型参数之间交替进行) [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） 图卷积，图上节点信号 u 1 , u 2 ∈ R N \bold{u}_1,\bold{u}_2 \in R^N u1,u2∈RN 其中Q是图拉普拉斯矩阵L的特征分解得到的特征向量组成的矩阵 （2） 图滤波公式 （3） 多层图卷积操作 u j l + 1 = ρ ( ∑ i = 1 f l Q Θ i , j l Q T u i l ) j = 1 , … , 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} ujl+1=ρ(i=1∑flQΘi,jlQTuil)j=1,…,fl+1 其中
空间卷积：考虑节点邻域来进行卷积 也可以结合两者进行 u j l + 1 = ρ ( ∑ i = 1 f l Q Θ i , j l Q T u i l ) j = 1 , … , 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} ujl+1=ρ(i=1∑flQΘi,jlQTuil)j=1,…,fl+1
多层图卷积操作 u j l + 1 = ρ ( ∑ i = 1 f l Q Θ i , j l Q T u i l ) j = 1 , … , 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} ujl+1=ρ(i=1∑flQΘi,jlQTuil)j=1,…,fl+1 其中 l l l表示第 l l l层GCN， Θ = Θ ( Λ ) ∈ R N × N \Theta=\Theta(\Lambda) \in \mathbb{R}^{N \times N} Θ=Θ(Λ)∈RN×N是可学习滤波器参数，通过使用节点特性 F V F^V FV作为输入层，叠加多个GCN层,整体架构类似于CNN。理论分析表明，这种图形卷积运算的定义可以模拟CNNs的某些几何性质。
但是上述的卷积操作 Θ \Theta Θ 的大小和节点数相关，Bruna[40]提出改进: diag ( Θ i , j l ) = K α l , i , j \operatorname{diag}\left(\boldsymbol{\Theta}_{i, j}^{l}\right)=\mathcal{K} \alpha_{l, i, j} diag(Θi,jl)=Kαl,i,j 其中 K \mathcal{K} K是固定插值核， α l , i , j \alpha_{l, i, j} αl,i,j是可学习的插值系数，[41]中将这种改进推广到图不是给定的，而是使用监督或非监督方法[41]从原始特征构造而成。
依旧存在的问题：
需要计算拉普拉斯矩阵的全部特征向量，此外前向和后向传播的时间复杂度为 O ( N 2 ) O\left(N^{2}\right) O(N2)，因此这种方法不能扩展到大规模的图上，滤波器依赖于图的特征基，所以参数不能在不同大小和结构的图之间共享。为了解决上述提到的两个问题，两条线路+统一框架‘
解决效率问题-线路1
ChebNet：Θ ( Λ ) = ∑ k = 0 K θ k Λ k \boldsymbol{\Theta}(\boldsymbol{\Lambda})=\sum_{k=0}^{K} \theta_{k} \boldsymbol{\Lambda}^{k} Θ(Λ)=k=0∑KθkΛk
其中可学习的参数为 θ k \theta_{k} θk,K是多项式阶数
为了解决拉普拉斯矩阵特征分解问题使用Chebyshev expansion，切比雪夫多项式阶数，参见ChebNet文献
Kipf和Welling[43]进一步，仅使用一阶邻域简化了滤波，增加一个self-connection,并且堆叠的一阶近邻的效果能够实现和ChebNet相同的模型容量，但是更好的结果。
ChebNet的一个重大突破就是：它们将频谱图的卷积与空间结构联系起来，它们表明了当频谱卷积函数是多项式或一阶时，频谱图的卷积等价于空间卷积
GNN可以看作是大量具有相同层的GCN去达到一个稳定的状态，GCN有不同数量的层，并且每一层包含了不同的参数。
使用谱方法解决效率问题：CayleyNet，采用Cayley polynomials定义图卷积： Θ ( Λ ) = θ 0 + 2 Re { ∑ k = 1 K θ k ( θ h Λ − i I ) k ( θ h Λ + i I ) k } \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\} Θ(Λ)=θ0+2Re{k=1∑Kθk(θhΛ−iI)k(θhΛ+iI)k} 这个优点就是：能够探测重要的窄带信息从而得到更好的结果。
GWNN：图小波神经网络，用图波小波变换代替频谱滤波器中的傅里叶变换: u 1 ∗ G u 2 = ψ ( ( ψ − 1 u 1 ) ⊙ ( ψ − 1 u 2 ) ) \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) u1∗Gu2=ψ((ψ−1u1)⊙(ψ−1u2)) 使用快速逼近（fast approximating algorithms）计算 ψ \psi ψ和 ψ − 1 \psi^{-1} ψ−1,计算复杂度为
O ( K M ) O(K M) O(KM)
将图卷积推广到任意大小的多个图
Neural FPs [46]使用一阶邻域，空间方法 h i l + 1 = σ ( ∑ j ∈ N ^ ( i ) h j l Θ l ) \mathbf{h}_{i}^{l+1}=\sigma\left(\sum_{j \in \hat{\mathcal{N}}(i)} \mathbf{h}_{j}^{l} \Theta^{l}\right) hil+1=σ⎝⎛j∈N^(i)∑hjlΘl⎠⎞ 改进：
其中参数 Θ \Theta Θ可以在不同的图之间共享，并且和图的大小没有关系
具有不同度的节点学习不同的参数 Θ \Theta Θ,这种方法在小图上表现好，但是没有办法扩展到更大的图上。
PATCHY -SAN
想法：
使用一个graph labeling procedure(比如Weisfeiler-Lehman kernel)来确定一个节点的顺序，然后使用预先定义的顺序将一个节点的邻居们排列成一行使用节点的k个邻居定义receptive field，接着采用一个1-D的CNN做卷积想法存在的问题：
卷积依赖图标记的过程，这个是未经学习的预处理步骤(LGCN提出采用字典顺序进行排序，SortPooling采用对所有节点进行排序)，我们可以从事的方向是：改进节点的排序方式，然后发论文。DCNN
想法：
将图卷积的特征基替换为扩散基，通过节点间的扩散转移概率来确定节点的邻居。 H l + 1 = ρ ( P K H l Θ l ) \mathbf{H}^{l+1}=\rho\left(\mathbf{P}^{K} \mathbf{H}^{l} \Theta^{l}\right) Hl+1=ρ(PKHlΘl)存在的问题：
计算 P K P^K PK时间复杂度为 O ( N 2 K ) O\left(N^{2} K\right) O(N2K)，因此这种方法只适合小规模图。DGCN
想法：
在对偶图卷积网络中共同采用扩散和邻接基的方法，使用两种卷积，适用于单图问题。统一的框架
MPNNs：
想法：
使用消息传递函数在空间域进行图形卷积操作的统一框架m i l + 1 = ∑ j ∈ N ( i ) F l ( h i l , h j l , F i , j E ) h i l + 1 = G l ( h i l , m i l + 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} mil+1=∑j∈N(i)Fl(hil,hjl,Fi,jE)hil+1=Gl(hil,mil+1) F l \mathcal{F}^l Fl是消息函数， G l \mathcal{G}^{l} Gl是顶点更新函数。
增加一个与所有节点连接的“主”节点以加速长距离的消息传递，并将隐藏的表示分割成不同的“塔”以提高泛化能力优点：
一种特殊的MPNNs变体可以在预测分子性质方面取得最先进的性能。GraphSAGE
想法：
使用多个聚合函数 m i l + 1 = AGGREGATE l ( { h j l , ∀ j ∈ N ( i ) } ) h i l + 1 = ρ ( Θ l [ h i l , m i l + 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} mil+1= AGGREGATE l({hjl,∀j∈N(i)})hil+1=ρ(Θl[hil,mil+1]) 其中 AGGREGATE ( ⋅ ) \text { AGGREGATE }(\cdot) AGGREGATE (⋅)表示聚合函数。
文中提出的三种聚合函数：
the element-wise meanLSTMmax-pooling文中使用的LSTM需要确定邻居的次序，采用随机排序的方法，我们可以采用更好的方法。
Mixture model network (MoNet)
想法：Aggregating,相当于将邻居的信息集合的一起
使用template matching将用于流型的CNN和GCNs进行匹配GNs
想法：GNs引入了边缘表示和整个图的表示，涵盖框架更加一般。
将节点、边和图的表示全部学习了，同时采取Aggregation策略，以及消息传递机制。 m i l = G E → V ( { e i j l , ∀ j ∈ N ( i ) } ) , m V l = G V → G ( { h i l , ∀ v i ∈ V } ) m E l = G E → G ( { e i j l , ∀ ( v i , v j ) ∈ E } ) , h i l + 1 = F V ( m i l , h i l , z l ) e i j l + 1 = F E ( e i j l , h i l , h j l , z l ) , z l + 1 = F G ( m E l , m V l , z l ) \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} mil=GE→V({eijl,∀j∈N(i)}),mVl=GV→G({hil,∀vi∈V})mEl=GE→G({eijl,∀(vi,vj)∈E}),hil+1=FV(mil,hil,zl)eijl+1=FE(eijl,hil,hjl,zl),zl+1=FG(mEl,mVl,zl)总结
主流的卷积操作框架论文MPNNs（21）,GraphSAGE （22）,GNs（27）
使用图形卷积操作，可以学习有用的节点特征来解决许多基于节点的任务。但是，为了处理基于图像的任务，需要聚合节点信息以形成图形级表示。在文献中，这样的过程通常称为读出操作。
这个问题是图的同构问题，最著名的算法是quasipolynomial。
统计学(一阶矩统计 first-moment statistics)
求和，求平均，取max-poolingfuzzy histograms进行节点的表示使用FC(fully connected)layer作为最后一层，对节点表示的特征进行加权求和再做非线性，但是无法保证order invarianceHierarchical Clustering（层次聚类）
density-based agglomerative clusteringmulti-resolution spectral clusteringanother greedy hierarchical clustering algorithmmerge two nodes at a time,along with a fast pooling method to rearrange the nodes into a balanced binary treeadopted another hierarchical clustering method by performing eigendecomposition这些方法都无法实现端到端学习，然后就有了能够训练的聚类方法。
DiffPool，将层次聚类做成可微分那样，看看人家这脑子Imposing Orders and others
最佳的节点顺序依然是正在研究中的课题，可以往下做。GNN中增加一个连接到所有节点的特殊节点，GNs中接收所有节点和边的消息学习整个图的表示set2set，还满足读出操作order invariant的要求，使用LSTM和注意力机制。能用的都用上，试试效果graph attention network (GAT)
想法：
更换卷积方式，采用学习方式
将 h i l + 1 = ρ ( ∑ j ∈ N ~ ( i ) 1 D ~ ( i , i ) D ~ ( j , j ) h j l Θ l ) \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) hil+1=ρ(∑j∈N~(i)D~(i,i)D~(j,j) 1hjlΘl)换成 h i l + 1 = ρ ( ∑ j ∈ N ^ ( i ) α i j l h j l Θ l ) \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) hil+1=ρ(∑j∈N^(i)αijlhjlΘl),注意力系数通过学习得到
作者使用multi-head attentions 去连接得到的结果
GaAN 在GAT基础上更进一步，对于不同的head学习不同的weights。
HAN使用了两种注意力机制
node-level attentionsemantic-level attention问题的由来：
GCNs最suitable的深度很有限，2-3层：原因在于：
深层GCNs训练本身的难度过渡平滑问题，导致所有深层的节点具有相同的表示(注:在Graph Neural Networks: A Review of Methods and Applications中也提到平滑问题)Kipf and Welling [43]借鉴ResNet增加残差连接
将 H l + 1 = ρ ( D ~ − 1 2 A ~ D ~ − 1 2 H l Θ l ) \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) Hl+1=ρ(D~−21A~D~−21HlΘl)换成 H l + 1 = ρ ( D ~ − 1 2 A ~ D ~ − 1 2 H l Θ l ) + H l \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} Hl+1=ρ(D~−21A~D~−21HlΘl)+Hl去学习残差，这样能加深网络Column network (CLN)也是残差连接的思路
公式使用 h i l + 1 = α i l ⊙ h ~ i l + 1 + ( 1 − α i l ) ⊙ h i l \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} hil+1=αil⊙h il+1+(1−αil)⊙hil,其中 α i l \boldsymbol{\alpha}_{i}^{l} αil是权重集，和GGS-NNs很像，
PPNP 定义图卷积,将所有参数放在一个地方 H l + 1 = ( 1 − α ) D ~ − 1 2 A ~ D ~ − 1 2 H l + α H 0 \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} Hl+1=(1−α)D~−21A~D~−21Hl+αH0
Jumping knowledge networks (JK-Nets)
采用的最后一层集合多层特征，使用GraphSGATE中提到的Aggregation函数 h i final = AGGREGATE ( h i 0 , h i 1 , … , h i L ) \mathbf{h}_{i}^{\text {final }}=\operatorname{AGGREGATE}\left(\mathbf{h}_{i}^{0}, \mathbf{h}_{i}^{1}, \ldots, \mathbf{h}_{i}^{L}\right) hifinal =AGGREGATE(hi0,hi1,…,hiL)
边缘特征也用上，废物利用，物尽其用
思路：
针对不同的边缘类型训练不同的参数，然后聚合结果
对应网络
Neural FPs不同度的节点训练不同参数，接着对结果进行求和。CLN在异质图中针对不同的边缘类型训练不同的参数，并对结果进行平均。ECCRelational GCNs (R-GCNs) 借鉴知识图DCNN将边转换成节点处理
LGCN 构造line graph去包含边特征，并且在原始图和line graph上采用了两个GCNs
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：
GraphSAGE在训练过程中均匀地为每个节点==采样固定数量的邻居==，PinSage在图上使用随机漫步(random walk)来采样邻居,StochasticGCN采用the historical activations of the last batches as a control variate来减小采样方差。layer-wise samplings
FastGCN将节点解释为i.i.d样本
Adapt：下层的抽样节点以其上层为条件;
在一种图上训练，在未见过的节点上test。这一目标的实现是通过学习给定特征上的映射函数来实现的，这个映射函数不依赖图的基，并且可以在节点和图之间进行迁移，可以参考GraphSAGE，GAT，GaAN以及FastGCN中验证inductive setting部分。不过当前的研究停留在 graphs with explicit features
out-of-sample problem
Li et al. [70]，using a special form of Laplacian smoothing，同时还提出了GCNs联合训练(co-training)和自我训练(self-training)的方法。
Wu et al. [71] ，从信号处理角度分析，将图卷积看作是一个固定的低通滤波器，去除掉所有的非线性，提出了一个简化的图卷积架构(SGC)： H L = ( D ~ − 1 2 A ~ D ~ − 1 2 ) L F V Θ \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} HL=(D~−21A~D~−21)LFVΘ 不过，没有非线性，不具有非线性流型的学习能力，Maehara [72]又提出了GFNN模型，在上述的卷积之后增加一层MLP来补救这个问题。
SAE(sparse autoencoder) min Θ L 2 = ∑ i = 1 N ∥ P ( i , : ) − P ^ ( i , : ) ∥ 2 P ^ ( i , : ) = G ( h i ) , h i = F ( P ( i , : ) ) \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} ΘminL2P^(i,:)=i=1∑N∥P(i,:)−P^(i,:)∥2=G(hi),hi=F(P(i,:)) h i \mathbf{h}_{i} hi是获取的低维表示，然后施加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 Θ L 2 + α ∑ i , j = 1 N A ( i , j ) ∥ h i − h j ∥ 2 \min _{\Theta} \mathcal{L}_{2}+\alpha \sum_{i, j=1}^{N} \mathbf{A}(i, j)\left\|\mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2} ΘminL2+αi,j=1∑NA(i,j)∥hi−hj∥2 同时，=对L2重构损失进行重写。
DNGR提出使用PPMI（positive pointwise mutual information）矩阵替换SAE中的P矩阵(transition matrix)，不过时间复杂度 O ( N 2 ) O\left(N^{2}\right) O(N2)，不适合大规模的图。
GC-MC 使用GCN作为编码器,使用简单的双线性函数作为解码器
DRNE
利用LSTM直接聚合邻域信息重构低维节点向量损失函数 L = ∑ i = 1 N ∥ h i − LSTM ( { h j ∣ j ∈ N ( i ) } ) ∥ \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\| L=∑i=1N∥hi−LSTM({hj∣j∈N(i)})∥基于节点的度对邻居节点进行排序对于具有很大度的节点来说，采用邻域采样技术防止overlong memory，比PageRank好。Graph2Gauss (G2G)
用高斯分布去获取节点的不确定信息，将节点特征映射到高斯分布的均值和方差上
没有显式定义解码函数，而是通过在学习模型时增加约束 K L ( h j ∥ h i ) < K L ( h j ′ ∥ h i ) ∀ i , ∀ j , ∀ j ′ s.t. d ( i , j ) < d ( i , j ′ ) , \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} KL(hj∥hi)<KL(hj′∥hi)∀i,∀j,∀j′ s.t. d(i,j)<d(i,j′),
