什么是网络表征学习：

针对网络结构，用向量的数据形式表示网络结构、节点属性的机器学习方法就是网络表征学习。

目前的社交网络分析中，常用图的邻接矩阵表示节点间的连接关系，将边的信息表示为N*N的矩阵，邻接矩阵的列向量有时也会作为图节点的表示向量。但是这种表现形式会出现两种问题：第一，在图结构中，任意两个节点不一定是相连的，通常一个节点仅有很少的邻居，因此邻接矩阵是稀疏矩阵，倘若节点数目很多，如用户百万级的社交网络，那么用邻接矩阵表示图结构会很复杂。第二，邻接矩阵仅反映了边的信息，没有加入节点的属性，如社交网络中热的性别，年龄，兴趣等。基于这两个问题，网络表征学习的目的就是：第一，我们要学习一种低维度的向量表示网络节点，将节点映射到相应的向量空间，这种网络表征学习就是关于图结构的网络表征学习，也称网络嵌入；第二，我们的表示不仅仅可以表征网络结构，同时也可以表征节点本身自带的属性，这种表征学习，就是伴随节点属性的网络表征学习。通常第二种表征学习方法都是从第一种方法中推广而来。

第一种：关于图结构的网络表征（网络嵌入Graph Embedding/Network Embedding）

定义：将网络的节点和向量之间建立一个一一对应的关系，并且保留网络的一些拓扑性质。中心思想就是找到一种映射函数，该函数将网络中的每个节点转换为低维度的潜在表示。 在 Network embedding space中，节点之间的关系由点之间的距离来表示，结构上的特点由向量来表示。

学习 关于图结构的网络表征学习重点关注的是网络的拓扑结构与性质，是网络表征学习中最基本的一类方法，其目的在于如何得到节点在低维空间中的向量表示，使得向量之间的关系可以保持图结构中节点之间的结构关系。同时，我们需要确定向量之间距离的一种度量方式，用来表征对应节点之间的相似性。

节点之间的结构关系就是边的连接，比如直接邻居节点，就应该比二阶邻居（邻居的邻居）或高阶邻居（邻居的邻居的…）与原本节点的关系更紧密，因为直接邻居与原节点有边的直接连接。这种紧密关系应该可以用向量的距离来表示，余弦距离，欧氏距离等可以用来表示节点之间的相似性。节点之间的性质关系，则对应在边的性质。首先是边的权重，如果两个向量距离较小，那么在原图中对应两个节点之间边的权重越小（也可能越大，权重表示距离则权重越小；权重表示相似度则权重越大）。其次是边的方向，在无向图中边仅代表连接，但对于有向图，边的指向将影响节点之间的连接方式。

网络表示方法的演变：                                                                                                                                              1.传统的基于图的表示，通常用符号表示图结构，G=（V,E），每一个节点用不同的符号表示，用邻接矩阵构成的二位数据表示和存储节点之间的连接关系，有连接即为1，无连接即为0。这种方法在节点分布为长尾分布，即大多数边具有较少的连接关系的情况下，会形成非常稀疏的连接矩阵，不利于存储和计算。                                        2。网络表示学习（Network representation,或称为嵌入法Graph Embedding method）:用低纬度，稠密，实值的向量表示网络中的节点（含有语义关系，利于计算和存储，不用再手动提取特征（自适应性），且可以将异质信息投影到一个低维空间中方便进行下游计算）。 两者的差别在于1是把问题做为预处理环节，2是把问题作为机器学习本身(data-driven approach)，因为是通过数据本身优化学习到的mapping(作为参数或者模型)，使得该mapping反映更多得原始图信息。 

优势：                                                                                                                                                                         - 给网络中的每一个节点一个具体的数学向量，并且此向量能够保留节点的连接属性                                                - 降低维度                                                                                                                                                                   - 可为机器学习和统计模型提供特征（网络的结构只适用于某些统计和机器学习模型，而对于向量，我们有很多的方法和模型去处理它）

可以解决的问题：                                                                                                                                                    - (a) node classification 节点分类    (b) link prediction 预测链接  (c) clustering 聚类     (d) visualization 可视化

方法分类：

根据Embedding中保留的信息类型来划分Embedding methods。我们能够将Embedding methods分为三类：

1.network structure and properties preserving network embedding（保留网络结构和特性）                                 很多网络分析是可以在原始网络结构上进行的，但是会引起很多的问题，因此我们不禁会去考虑，是否可以只根据网络拓扑信息 来做Embedding，这样很多的分析任务就可以有效地在低维空间去进行。                                    结构信息包括邻近结构，高阶临近节点，社区结构。                                                                                               结构特性（Network Properties）包括网络传递性（network transitivity），结构平衡特性（structural balance property）.

2.network embedding with side information                                                                                                             除了网络拓扑，一些类型的网络有很丰富的Side information，比如节点内容和标签

3.advanced information preserving network embedding

以上两种方法大部分都是在无监督的情况下进行学习的，但是在这里，我们在目标场景应用应用监督学习或者半监督学习。

总的来说，Network structures和properties是基本考虑因素，Side info 和 Advanced info能够使得Embedding在真实场景上表现地更好

常用模型

不同图嵌入算法之间的区别在于，它们如何定义要保留的图属性。 不同的算法对节点（边、子结构、整图）的相似性，以及如何在嵌入空间中保留它们，有不同的见解。 

1.Matrix Factorization：基于矩阵分解的图嵌入，以矩阵的形式表示图特性（例如，节点成对相似性）并对该矩阵进行分解来获得节点嵌入。 图嵌入的开创性研究通常以这种方式解决图嵌入问题。 在大多数情况下，输入是由非关系高维数据特征构成的图。输出是一组节点嵌入。 因此，图嵌入的问题可以被视为保持结构的降维问题，其假定输入数据位于低维流形中。 有两种类型的基于矩阵分解的图嵌入。 一种是分解图的拉普拉斯特征映射 ，另一种是直接分解节点邻近矩阵 。

基于拉普拉斯特征图的图嵌入，w为相似度度量方式

基于节点邻近度矩阵分解的图嵌入算法(活跃于2010-2017)

2.Deep Learning：

(1)Deep learning with random walk paths

DeepWalk[1]：DeepWalk 通过将节点视为单词并生成短随机游走作为句子来弥补网络嵌入和单词嵌入之间的差距。然后，可以将诸如 Skip-gram 之类的神经语言模型应用于这些随机游走以获得网络嵌入。   DeepWalk 采用神经语言模型（SkipGram）进行图嵌入。 SkipGram旨在最大化窗口内出现的单词之间的共现概率  。 DeepWalk首先使用截断的随机游走，从输入图中采样一组路径（即，均匀地采样最后访问节点的邻居，直到达到最大长度）。 从图中采样的每个路径相当于来自语料库的句子，其中节点相当于单词。 然后将SkipGram应用于路径，最大化节点邻域的观测概率，以自身嵌入为条件。 以这种方式，邻域相似（二阶邻近度较大）的节点的嵌入相似。DeepWalk的目标函数如下：   

 DeepWalk 的优点可以概括为：首先其可以按需生成随机游走。由于 Skip-gram 模型也针对每个样本进行了优化，因此随机游走和 Skip-gram 的组合使 DeepWalk 成为在线算法。其次，DeepWalk 是可扩展的，生成随机游走和优化 Skip-gram 模型的过程都是高效且平凡的并行化。最重要的是，DeepWalk 引入了深度学习图形的范例。

带有随机游走路径的基于深度学习的图嵌入（2015-2017）

 如表中所示，大多数研究遵循DeepWalk的想法，但改变随机游戏的采样方法或要保留的邻近度的设定。

LINE[2]    Node2vec[3]    Walklets[4]:

(2).Deep Learning without random walk

GE基于非随机游走DL方法（2014-2017）

GraphAttention[6] SDNE[7] DNGR[8] GCN

3.GE Based on Optimization                                                                                                                                   总体四项： 基于节点嵌入建立的边应尽可能与输入图中的边相似。通过最大化边重建概率，或最小化边重建损失，来直接优化基于边重建的目标函数。 后者进一步分为基于距离的损失和基于边距的排名损失。 接下来，我们逐一介绍这三种类型。

（1）最大化边的重建概率                                                                                                                                         良好的节点嵌入应该能够重新建立原始输入图中的边。 这可以通过使用节点嵌入最大化所有观察到的边（即，节点成对接近）的生成概率来实现。生成概率可以由一节邻近度和二阶临近度衡量。

（2）最小化基于距离的损失                                                                                                                                    可以基于节点嵌入来计算节点邻近度，或者可以基于观察到的边凭经验计算节点邻近度。 最小化两种类型的邻近度之间的差异，保持了相应的邻近度。基于节点嵌入计算的节点邻近度，应尽可能接近基于观察到的边计算的节点邻近度。

基于边重建的嵌入方法（2016-2017）

4.GE based on Graph Kernel                                                                                                                                 图核是 R-convolution 核的一个实例，它是定义离散复合对象上的核的通用方法，通过递归地将结构化对象分解为“原子”子结构，并比较它们的所有对。 图核将每个图示为向量，并且使用两个向量的内积来比较两个图。 图核中通常定义了三种类型的“原子”子结构。包括 Graphlet，Subtree Patterns，Random Walks.                            Graphlet：原图被分解为一组大小为k的非同构子图graphlet{}，图G浅入为d维向量，其中第i维表示为子图出现的频率。Random walk：图被分解为随机游走或路径，并表示为随机游走的出现次数，或其中的路径。以路径为例，假设图被分解成 d个最短路径。将第i个路径表示为三元组 ，其中和是起始节点和结束节点的标签，是路径的长度。 然后图表示为d维向量 ，其中第i个维度是图中第i个三元组的频率。                                                                                                                                                                          图核专为整图嵌入而设计，因为它捕获整个图的全局属性。 输入图的类型通常是同构图或带有辅助信息的图。

三种类别的方法记录

1.Structure and Property Preserving Network Embedding

Deep Walk(Skip Gram)

Node2Vec

LINE

Modularized Nonnegative Matrix Factorization

SDNE

HOPE

2.network embedding with side information/Attributed Network Embeddings(考虑节点属性)                        TADW [9]研究节点与文本特征相关联的情况。TADW 的作者首先证明了 DeepWalk 实质上是将转移概率矩阵 M 分解为两个低维矩阵。受此结果的启发，TADW 包含文本特征矩阵 T 通过将 M 分解为 W，H 和 T 的乘积，进入矩阵分解过程。最后，将 W 和 H×T 连接起来作为节点的潜在表示。

CENE [10]是一种网络嵌入方法，它共同模拟节点中的网络结构和文本内容。CENE 将文本内容视为特殊类型的节点，并利用节点-节点链接和节点内容链接进行节点嵌入。 优化目标是共同最小化两种类型链路的损失。

HSCA [11]是一种归因图的网络嵌入方法，它同时模拟同音，网络拓扑结构和节点特征。

Maxmargin DeepWalk（MMDW）[12]是一种半监督方法，它学习部分标记网络中的节点表示。MMDW 由两部分组成：第一部分是基于矩阵分解的节点嵌入模型，第二部分是将学习的表示作为特征来训练标记节点上的最大边缘 SVM 分类器。通过引入偏置梯度，可以联合更新两个部分中的参数。

RTM

CNN Model and FC layers

3.advanced information preserving network embedding

Random Walk + GRU(Gated Recurrent Unit, actually a kind of RNN)

4.Heterogeneous Network Embeddings（异构网络）                                                                                           异构网络具有多类节点或边缘。为了模拟不同类型的节点和边缘，大多数异构网络嵌入方法通过联合最小化每种模态的损失来学习节点嵌入。这些方法要么直接在相同的潜在空间中学习所有节点嵌入，要么事先为每个模态构建嵌入，然后将它们映射到相同的潜在空间。

Chang[13]提出了异构网络的深度嵌入框架。他们的模型首先为每种模态（如图像，文本）构建一个特征表示，然后将不同模态的嵌入映射到同一个嵌入空间。优化目标是最大化链接节点的嵌入之间的相似性，同时最小化未链接节点的嵌入。注意，边可以在相同模态内的两个节点之间以及来自不同模态的节点之间。

Zhao [14]是另一种用于在异构网络中构造节点表示的框架。具体来说，他们认为维基百科网络有三种类型的节点：实体，单词和类别。建立相同和不同类型节点之间的共现矩阵，并且使用坐标矩阵分解从所有矩阵联合学习实体，词和类别的表示。

Li [15]提出了一种神经网络模型，用于学习异构社交网络中的用户表示。他们的方法联合模拟用户生成的文本，用户网络和用户与用户属性之间的多方面关系。

HEBE [16]是一种嵌入大规模异构事件网络的算法，其中事件被定义为网络中一组节点（可能是不同类型）之间的交互。虽然先前的工作将事件分解为事件中涉及的每对节点之间的成对交互，但 HEBE 将整个事件视为超边界并同时保留所有参与节点之间的接近度。

具体而言，对于超边缘中的每个节点，HEBE 将其视为目标节点，并将超边界中的其余节点视为上下文节点。因此，基础优化目标是在给定所有上下文节点的情况下预测目标节点。

EOE [17]是用于耦合异构网络的网络嵌入方法，其中两个同构网络与网络间边缘连接。EOE 学习两个网络的潜在节点表示，并利用和谐嵌入矩阵将不同网络的表示转换为相同的空间。

Metapath2vec [18]是 DeepWalk 的扩展，适用于异构网络。为了构建随机漫游，Metapath2vec 使用基于元路径的漫游来捕获不同类型节点之间的关系。对于来自随机游走序列的学习表示，他们提出异构 Skip-gram，其在模型优化期间考虑节点类型信息。

五 数据集

Social Network

BLOGCATALOG http://socialcomputing.asu.edu/datasets/BlogCatalog3

FLICKR http://socialcomputing.asu.edu/datasets/Flickr

YOUTUBE http://socialcomputing.asu.edu/datasets/YouTube2

Twitter http://socialcomputing.asu.edu/datasets/Twitter

Citation Networks

DBLP http://arnetminer.org/citation

Cora https://linqs.soe.ucsc.edu/node/236

Citeseer https://linqs.soe.ucsc.edu/node/236

ArXiv http://snap.stanford.edu/data/ca-AstroPh.html

Language Networks

Wikipedia http://www.mattmahoney.net/dc/textdata

Biological Networks

PPI http://konect.uni-koblenz.de/networks/maayan-vidal

参考文献：                                                                                                                                                                [1] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations.In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014.

[2] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Largescale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pages 1067–1077. ACM, 2015.

[3] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 855–864. ACM, 2016.

[4] Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. Don’t walk, skip! online learning of multi-scale network embeddings. In 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE/ACM, 2017.

[5] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 891–900. ACM, 2015.

[6] Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alex Alemi. Watch your step: Learning graph embeddings through attention. arXiv preprint arXiv:1710.09599, 2017.

[7] Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1225–1234. ACM, 2016.

[8] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1145–1152. AAAI Press, 2016.

 [9] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. Network representation learning with rich text information. In IJCAI, pages 2111–2117, 2015.

[10] Xiaofei Sun, Jiang Guo, Xiao Ding, and Ting Liu. A general framework for content-enhanced network representation learning. arXiv preprint arXiv:1610.02906, 2016.

[11] Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Homophily, structure, and content augmented network representation learning. In Data Mining (ICDM), 2016 IEEE 16th International Conference on, pages 609–618. IEEE, 2016.

[12] Cunchao Tu, Weicheng Zhang, Zhiyuan Liu, and Maosong Sun. Max-margin deepwalk: discriminative learning of network representation. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016), pages 3889–3895, 2016.

[13] Shiyu Chang, Wei Han, Jiliang Tang, Guo-Jun Qi, Charu C Aggarwal, and Thomas S Huang. Heterogeneous network embedding via deep architectures. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 119–128. ACM, 2015.

[14] Yu Zhao, Zhiyuan Liu, and Maosong Sun. Representation learning for measuring entity relatedness with rich information. In IJCAI, pages 1412–1418, 2015.

[15] Jiwei Li, Alan Ritter, and Dan Jurafsky. Learning multi-faceted representations of individuals from heterogeneous evidence using neural networks. arXiv preprint arXiv:1510.05198, 2015.

[16] Huan Gui, Jialu Liu, Fangbo Tao, Meng Jiang, Brandon Norick, and Jiawei Han. Large-scale embedding learning in heterogeneous event data. 2016.

[17] Linchuan Xu, Xiaokai Wei, Jiannong Cao, and Philip S Yu. Embedding of embedding (eoe): Joint embedding for coupled heterogeneous networks. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 741–749. ACM, 2017.

[18] Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 135–144. ACM, 2017.

参考链接：

https://blog.csdn.net/ZhichaoDuan/article/details/79570051

https://blog.csdn.net/lkxhit/article/details/81391728

http://www.sohu.com/a/247059535_500659