Embeddings主要思路分类：

NLP类方法使用LSTM等对时序数据做表示
Graph Embedding 对图做嵌入（引入图的原因之一是：用图可以表示复杂关系的长时间时间序列）
类似CNN的方法也可以看为Embedding
对比学习，学到更好的表示 or Embedding

知乎LINKS

Embedding的原因 https://zhuanlan.zhihu.com/p/164502624
Embedding的简单发展史（主要为Word2vec -> Item2Vec）https://zhuanlan.zhihu.com/p/164502624
万物皆可Embedding https://zhuanlan.zhihu.com/p/109935332
Embedding在深度学习中的3大方向 https://zhuanlan.zhihu.com/p/67218758

Video：

Pre-trained Models for Natural Language Processing: A Survey LINK
自然语言处理中的表示学习 LINK

Resource List：

Papers:

A Tutorial on Network Embeddings 2018 Finished
Tutorial on NLP-Inspired Network Embedding 2019 Finished
DeepWalk INCLUDE
LINE INCLUDE
Node2Vec INCLUDE
GraphAttention INCLUDE
SDNE
HOPE
Learning edge representations via low-rank asymmetric projections 2017
Deep graph kernels 2015

Videos:

Pre-trained Models for Natural Language Processing: A Survey LINK
自然语言处理中的表示学习 LINK Finished

Specturm Methods:

https://www.cnblogs.com/pinard/p/6221564.html

A Tutorial on Network Embeddings

Author: Haochen Chen er al LINK

Journal: Social and Information Networks 2018

Goal of Network Embeddings：

Network embedding methods aim at learning low-dimensional latent representation of nodes in a network.

而获得的embeddings应该有如下的性质：

适应性（Adaptability）- 现实的网络在不断发展；新的应用算法不应该要求不断地重复学习过程。
可扩展性（Scalability）- 真实网络本质上通常很大，因此网络嵌入算法应该能够在短时间内处理大规模网络。
社区感知（Community aware）- 潜在表示之间的距离应表示用于评估网络的相应成员之间的相似性的度量。这就要求同质网络能够泛化。
低维（Low dimensional）- 当标记数据稀缺时，低维模型更好地推广并加速收敛和推理。
连续的（Continuous）

从传统ML降维的角度看Graph Embedding

这其中使用了例如：PCA和MDS等方法，这类方法都可以看为使用一个n by k矩阵来代表原始数据的n by m矩阵，其中k<m。之后又提出了一些新的降维方法比如：IsoMap，LLE等方法。总体来讲这类方法在小的网络上显示了不错的性能，但由于其复杂度往往随矩阵规模而指数增长，导致这种方法无法应用于大型的图。

另外一类就是图的谱方法了（如LE: Laplacian eigenmaps），基本上来讲使用拉普拉斯矩阵or标准化的拉普拉斯矩阵的特征值和特征向量的信息来对于每个节点进行聚类和划分以实现嵌入的效果。这类方法的主要问题是：对矩阵的特征值分解是与矩阵规模呈指数形式的，所以在large network中也较难应用，且这类基于spectrum的方法的性能往往逊色于基于neural network的方法。

The Age of Deep Learning

DeepWalk在图上使用表示学习（或深度学习）的方法，是一个非常经典的方法。DeepWalk 通过将节点视为单词并生成短随机游走（random walk）作为句子来弥补网络嵌入和单词嵌入之间的差距。然后，可以使用 Skip-gram 等，应用于这些随机游走以获得网络嵌入。

优点：

Online algorithm
Scalable

也引出了一种在图上使用Deep Learning的paradigm

Unsupervised Network Embeddings

最经典的还是DeepWalk，其有如下两个地方可以改进：

Source of Context Node（如何产生序列）
Embedding Learning Methods(deepwalk中使用skip-gram，当然也可以使用其他学习序列表示的方法)

针对于Deep Walk的可改良点，有这些改进的方法。

其中比较出名的有的：LINE，Node2Vec，GraphAttention等。后面的SDNE和DNGR则引入了deep learning中较深的encoder类方法。

值得注意的是，这些方法主要是用于undirected graph中的。

Directed Graph Embedding

基本上全部的基于无向图的方法都可以很自然的推广到无向图中。

其中常见和经典的方法为：HOPE

Edge Embedding

这类embedding可以用于link prediction等task中。

Signed Graph Embeddings

Signed Graph指：边的权值只为-1or1，主要方法报过：SiNE和SNE。

Subgraph Embeddings

经典方法为Deep Kernel也是这类方法的常见范式。

Meta-strategies for Improving Network Embeddings

主要方法HARP。HARP is a general meta-strategy to improve all of the state-of-the-art neural algorithms for embedding graphs, including DeepWalk, LINE, and Node2vec.

Attributed Network Embeddings

前面的讨论针对的主要是没有attribute的图，而对于有attribute的图，其attribute一般是附加在节点上的，一般主要研究两类attribute

high-level features such as text or images
node labels

针对第一点（high-level features）：常见方法包括：TADW，CENE

针对第二点（node labels 常见于引用网络和社交网络）：GENE

当然在许多真正的网络中，并不是所有节点都是有label的，所以也有一些Semi-supervised的方法设计出来。例如：Planetoid，Max-margin Deep Walk,

Heterogeneous Network Embeddings

Heterogeneous Network/Graph 异质图，即have multiple classes of nodes or edges。大部分异构网络嵌入方法通过联合最小化每种modality的损失来学习节点嵌入。这些方法要么直接在相同的潜在空间中学习所有节点嵌入，要么事先为每个模态构建嵌入，然后将它们映射到相同的潜在空间。

总结

此paper主要是总结了一下目前常见的和经典的一些图嵌入的方法（连介绍都算不上），也对于在不同应用场景上的方法做了一个分类，很适合在之后想在某个场景使用图嵌入方法时来进行查阅。这部分note也主要是这个目的。作者也简单总结了未来图嵌入可能的发展方向，不过本文是2018年的，之后会跟进一些2018年之后更新的方法。

Tutorial on NLP-Inspired Network Embedding

主要介绍使用word embedding的方法到graph embedding中。主要包括以下几个经典的方法：

DeepWalk: Online Learning of Social Representations 2014
LINE: Large-scale Information Network Embedding 2015
node2vec: Scalable Feature Learning for Networks 2016
struct2vec: Learning Node Representations from Structural Identity 2017
metapath2vec: Scalable representation learning for heterogeneous networks 2017

LINE和node2vec是对于deepwalk的改进，公认后者更加稳定一些。

word2vec（skip-gram）

word2vec基于的假设是：the principle of co-occurrence: the assumption that words with related semantic meanings appear close to each other in texts.

word2vec模型示意图，一种无监督方法。需要一个大小为2*k的slide window来生成输入序列。给定一个词w，其上下文词$c\in C(w)$由该slide window获得，我们优化的目标是：

即给定当前词，令上下文词出现的概率最大，找到合适的参数θ。

对于整个预料库，我们有：

计算这个概率一般使用softmax，即：

$V_c, V_w$为生成的embedding。由于在计算分母部分时，也非常的耗费计算时间，所以经常使用negative sampling（本质是预测总体类别的一个子集）或hierarchy softmax（本质是把 N 分类问题变成 log(N)次二分类）来取一个approximate。整体模型如下图所示：

Deep Walk

一个比较简答扩展，将word2vec可以应用于网络之中！对应关系如下图所示，具体细节可以见cs224w slides or 原始paper

The assumption is that sampling from multiple random walks captures the structure of the graph.

缺点：

生成序列使用的random walk是unbiased的，其与DFS比较相似。

LINE

LINE的目标就是优化random walk的unbiased特性，solve this issue by preserving first-order and second-order node proximities（保留一阶和二阶节点的亲近性）。其没有使用random walk，而是使用1-hop和2-hop的节点来构造供给NLP word embedding的sequence序列。

first-order proximity：节点的一阶proximity被定义为：其链接边的权值。

其数学定义为：v是其生产的embedding

其理想情况应该与基于节点权值定义的一阶相似度比较接近。即与下式接近。其中W为正则化因子。

embedding的优化目标就是尽可能缩小二者分布的“距离”，即最小化二者的KL散度。

second-order proximity：节点的二阶proximity被定义为：the common neighborhood of two nodes

其二阶相似度的优化目标为：

其中P2为：

下面是对于一阶和二阶相似度的一个直观解释。如上图所示，可见节点6与7有很高的一阶相似度（相连的边的权值大），所以他们在embedding space应该比较接近。

节点5与节点6虽然没有直接连接，但二者有高度相似的邻居节点，所以二者的二阶相似度很高，他们在embedding space中也应该比较接近。

在LINE中，the embedding for the first-order and second-order proximities (i.e. maximizing for O1 and O2) is done separately。最终从这两个模型得到的embedding在concatenate成为最终的embedding。

总结：

不同于DeepWalk的DFS，LINE更倾向于BFS；而且其最大的特点是可以利用在带权图中，利用了权重的信息。

node2vec

使用biasing the random walks。本质上就是改变了random walk生成序列的方式。作者因为了两个因子，来控制random walk是倾向于DFS还是BFS。在实现时要记录是从哪一个节点来的。

文中还提出了基于node2vec如何表示边的信息。

struct2vec

Focuses on the role of nodes in a network. Struc2vec is a framework for representations based on structural similarity.

GOAL: The goal of struc2vec is to preserve the identity of the nodes’ structure when projecting them into Euclidean space.

这与node2vec 和 deepwalk 很不一样，这俩是捕获neighbor的信息，而许多节点在struct很相似，但在图上的距离却很远。

为了计算这个表示，struct2vec构建了一个特殊的graph：the context graph 其代表了structural similarities between nodes.有了context graph之后，只需在该图上使用deep walk or node2vec即可。

设原始的图的diameter（直径为K），则the context graph M is a multi-layer graph with K + 1 layers. Each layer includes all the nodes in G.在每一个layer中，带权的权值表示了两个节点的结构相似度。

Step 1: Computing Structural Similarity

第一步主要是寻找节点之间的structural Similarity。For each node v, we look at the $N_k(u)$, which is the set of nodes which are k-distant from node u. 对于每一组$N_k(u)$看成一个ring，我们找他们的ordered degree squence，即把每个节点的度组成序列（按照降序）。k最大为K（图的diameter(直径)）。measure两个节点的structural Similarity就是使用每个节点计算的ordered degree squence。用于这个ordered degree squence显然未必是等长度的，所以作者使用了Dynamic Time Warping (DTW)，一种match element between 2 squence with different length.

下图即为整体的Structural Similarity的计算公式，可以看到时递归计算的。DS()即为ordered degree squence，g()即为前面提到的DTW，用于计算两个长度不一样序列的距离。

Step 2: Constructing the Context Graph

The context graph M is a multilayer graph with K layers. Each layer is a complete graph consisting of all the nodes u ∈ V in the original graph G. 所以图G中的每个节点可以用M中K+1层(k=0, … , K)个对应的节点来表示。

下图就是一个根据左边G建立的M。一共包含3层。

在每一层都是一个全连接的无向带权图，其权重的计算公式为：

式中的f就是上文计算不同长度序列的函数。直观的来讲，两个节点的的structural similarity越相似，即该计算的距离越小，这两个节点的间的权值就越大。

从图中也可以看出，不同layer间的同一个节点间也存在着双向的带权边，权值的计算方式如下：

其中$\Gamma_k(u)$为连接u的边中权重大于该层平均权重的数量。直观的来讲：$\Gamma_k(u)$就是有多少节点是与节点u相似的。

Step 3: Generate Context

现在我们已经建立了Context Graph，下一步就是与Deep Walk非常相似了。不过在这里显然一个节点可以往上面的层走，也可以向下面的层走，也可以在同层间游动。其中：留在本层继续游走的概率为q，自然跳层的概率就是1-q，该q为一个超参数。

切换layer的概率为1-q，向上和向下移动的概率为：

停留在当前layer的概率为q，移动的概率也根据边的权值决定。其中$Z_k(u)$为一个归一化因子。直观的来讲，结构越相似的节点越容易出现在一次random walk之中。

Step 4: Learn Representations

最后就是使用生成的序列来进行word2vec即可（skip-gram + negative sampling）

metapath2vec

主要针对heterogeneous networks（异质图）。在异质图中，节点可以属于不同的类别。这个与之前random walk类方法使用的同质图非常不同，作者主要使用random walks will be biased by using meta-paths。一个mate-path是一个predefined composite relation between nodes. 本质就是random walk只能发生在定义好的meta-path上，the random walks must follow the semantics dictated by the various prescribed meta-paths。