A survey on Network Embedding

 

In this survey, we focus on categorizingand then reviewing the current development on network embedding methods, andpoint out its future research directions.

 

第一部分： the motivation of network embedding

          Classical graph embedding algorithms, relationship with networkembedding.

第二部分，重点：Overview of a large number ofnetwork embedding methods.包括带有边缘信息和高层信息保护的网络嵌入方法。

 

Introduction：

怎么简明表示网络数据，便于更深层次分析，比如模式识别、分析和预测，在时空上可操作。传统的表示网络方法是一个图G=(V, E)  但大型网络中此表示方法在网络处理和分析中不适用，存在挑战。如：高的计算复杂度（两点间的距离的计算）、低并行化（紧耦合，分割图但依赖于图的拓扑结构）、不适用于机器学习

 用边来表示两者之间的关系，是最大的瓶颈。

       Relationshipamong the nodes: 边或者更高层次的拓扑结构。

Node classification  node clustering network visualization  link prediction

去除噪声和冗余，内在结构被保护，计算复杂度降低，可并行化。

1.     传统网络可被重建 2.适用于网络inference。例如链接预测，识别关键节点，节点标签。

Section2 NE方法分类 总结    section3 传统图嵌入方法和现在的网络嵌入方法的区别  Section4 5 6 各自分析NE方法。 Sec 7 一些评估场景和资源 Section8 研究方向

 

Section2方法分类

根据被保护的信息：

（1）     网络结构和属性保护的network embedding

（2）     Side information 的 network embedding

（3）     Advanced information preservingnetwork embedding

(1)   Structure and propertypreserving network embedding

比如识别关键节点，预测链接，则在只考虑拓扑结构的embedding中会存在很多问题。很多人尝试保留结构信息，如邻居的信息，高等级的邻近度、社区等等。网络属性：link formation。

（2）节点内容或者标签。节点和边的属性，以及节点的属性等。有利于network node的聚类。主要的挑战是：怎么整合和平衡网络的拓扑结构和边缘信息到networkembedding中。

（3）希望得到的embedding通用。需要监督信息。特定目标场景的表示学习框架，可以用在Network embedding中。（NLP、CV）

 

Commonly used models: matrix factorization \ random walk \deepneural networks and their variations.

（1）矩阵分解：N维的矩阵，将其降维。矩阵分解方法，与学习低秩空间的原矩阵相同的目标，可以很自然地应用于解决这个问题。SVD分解

（2）random walk：保护neighborhood structure , local structure,将节点视为word, 随机路径视为sentence,节点邻居视为共现率。 DeepWalk.

(3)深度神经网络：本质是学习一个映射函数。矩阵分解是线性函数。使用神经神经网络刻画一个非线性函数。SDNE,, SDAE   SiNE。 End to end solutions,比如针对cascade predictionand  network alignment.

 

Section3Network embedding V S Graph Embedding

传统的图嵌入方法，综述：Fu and Ma 2012 

图嵌入：

Graph Embedding 方法降维技术。流型学习。

考虑不同的重构方法，这方面有很多paper。

 

Network embedding 和graphembedding 有本质的不同：

Network embedding: 重建原始网络+网络推断。

而graph embedding主要目标是网络的重建。

因此，graph embedding 可以视为一种特殊的Network embedding，只考虑重建网络的network embedding.而现在的研究更注重网络的inference，也是本paper接下来的重点。

Network 一般来源于自然，其结点邻近度量一般不是很直接的，依赖于不同的分析或应用场景。

 

Section4 structure and Property preserving network embedding

结构保护可以分为很多种，包括：neighborhood structure \high-order node proximity \ network communities

 

(1)  Neighborhood structure and high-order

DeepWalk : 保护了邻居节点结构。设想Node出现在短的随机游走路径中的分布，类似于自然语言中词语的分布。则利用了skip-gram model来采纳到deepwalk中去学习节点。

Node2vec: 没考虑各个链接模式，Node2vec定义了网络的邻居，设计了second order random walk策略来采样邻居点，然后再深度和广度上采样。Node2vec将在同一community中的节点、或者有相似角色的node表示成相似的embedding ，

Line: 可以保护firstorder和second order。两种都是很重要的度量。Firstorder度量成联合概率分布（公式6）second order度量成基于内容的条件概率（公式7）。

 

(2)Networkcommunities 提出了一种模块化的非负矩阵分解模型(MNMF)，保护first-order and second-order proximities of nodes, and themesoscopic community structure。用了NMF模型保护微观结构，假设如果一个节点的表示与一个社区的表示相似，那么该节点在这个社区中可能具有很高的倾向

SDNE:深层模型。解决高非线性、结构保护和稀疏性问题。，SDNE使用具有多个非线性层的深度自动编码器来保护节点的邻居结构。

Cao：由PageRank模型驱动，结合加权转移概率矩阵，可以主动构造节点的表示。捕获权重图结构和节点的非线性表示结构。https://zhuanlan.zhihu.com/p/35070284

Chen：GEM-D[h(_); g(_); d(_; _)]  h()是邻近度函数，g()是非线性函数 d()是度量h和g的区别。

总结：保护一个node的局部信息，邻近结构、高阶近距离以及社区结构，

 

Property preserving network embedding

 

关注network transitivity 和 structural balance property

Ou(2015)保护非传递属性（A和B有关系，B和C有关系但是A和C没有关系）利用投影矩阵，抽取M哈希表，得到 最终相似度可以通过其聚合得到。如果两个节点语义相似，那么至少有一个 较大。

      HOPE（2016）保护有向网络的非对称传递性。（A->B  B->C 则有 A->C （而不是C->A））,总结了四种度量方法，将原始SVD转变为通用的SVD问题，时间复杂度降低，具有伸缩性。

       SiNE不仅考虑了边的正例，还考虑了负例。结构平衡理论表明用户应该能够让他们的朋友比他们的敌人更亲密。三元组（） 且  则ij相似度大于ik相似度。设计了一种深度学习模型，该模型由两个具有非线性函数的深层网络组成，如下图

总结：保留高级特性，但是获得高级特性的策略不同。有一些方法通过一个节点到邻居的生成机制来保护高层结构，或者通过高级邻近度。还有拓扑结构。网络的信息和网络的演化，

 

 

 

Section5  利用sideinformation做network embedding

Sideinformation 是另一个很重要的信息，分为两类：node content&节点和边的类型。

（1）     Node content

节点伴随有很多content,如label属性或者语义描述。问题在于怎么结合content和网络的拓扑结构。

MMDW(2016)结合了节点的标签信息，基于deepwalk的矩阵分解，采用支持向量机来优化分类边界，从而学习到节点的更具有辨识度的表示。

       文档网络嵌入的生成模型（2014），文档中的单词和文档之间的联系。Le and Lauw 2014。每个节点有个低维有序的表示ui，也学习在topic space（基于Relation Topic Model）的表示。每个topic有个单词分布。将每个主题z与同一个低维向量空间中的表示“z”相关联，然后具有以下函数

。

TADW：证明deepWalk等价于 矩阵分解，加入文本信息T, 但计算代价高，节点属性文本无序，失去语义信息。Sun et al. (Sun et al. 2016) 将context视为一种特殊的Node,得到一个更大的network，然后有mode-node 和 node-content 的链接,利用负采样和逻辑函数，学习Node在联合目标函数中的表示，从而同时保留Node-content和网络结构。

       Pan et al. (Pan et al. 2016)网络结构+节点属性+节点标签。1…N个node，每个node（i）对应有一个word集合{wi} 和标签集合{Ci}. 可能有|L|种标签。最大化：

第一项类似于deepwalk第二项node-context 第三项label-node.

       LANE 网络结构+label+属性。LANE采用了余弦相似度来构造节点属性、网络结构和标签的对应关联矩阵。再基于Laplacian矩阵，三种表示，三种关系。

 

       总结：都想融入Node content和 network topology,都基于Node content可以提供额外约束条件来更好地表示节点。

（2）     节点和边的类型（异构信息网络的嵌入）

异构网络有很多不同类型的节点和边。问题在于怎么统一易购网络的节点和边，然后再用低维向量表示出来。

  Yannet al. (Jacob, Denoyer, and Gallinari 2014)在同一个向量空间中学习节点的表示，然后进行推理（包括所有异构类型的节点）。推理时，Ui 是 ti类型，则用 预测节点i的标签。误差函数： 

 I 和 j 如果 的w很大，则ij应该很近。因此就可以把异构node映射到一个latent space。优化目标是上两个公式的结合。SGD优化。

Chang et al. (Chang et al. 2015)目标是Learn representation 且可以保护异构信息网络的特性。Node(A，B两类) 则边有 A-A A-B B-B三类。通过CNN和全连接，其表示可以被映射到common space，不同类型的数据可以直接measured,而不管其类型。

Huang and Mamoulis（2017）meta path相似度来保护异构信息网络。Meta path是一个类型序列。他们开发了一种快速的dynamic programming方法来计算被截断的元路径，它的时间复杂度与网络的大小是线性的。他们采用了类似的策略(Line ,Tang et al. 2015)，以保持低维空间的邻近度。

Xu et al. (Xu et al. 2017) coupled 异构网络：包含两个不同但有关联的同构网络，对每个同构网络采用Line中的

来度量。然后用一个嵌入矩阵度量不同网络中Node的邻近度。

      

总结：保护side information信息，不同的是怎样将side information 和网络结构额融合来表示Node。

 

Section 6 保护高级信息

       考虑additional advanced information，解决特性的分析任务。

（1）Information diffusion

       信息扩散在很多网络中存在；以前都在原始网络中做研究，现在：

Simon et al. (Bourigault et al. 2014)的社会网络嵌入算法来预测information diffusion。将传播过程映射到热传播过程，学习节点的表示，使得扩散核可以解释训练集， Li et al. (Li et al. 2017)提出end-to-end的深度学习模型来解决级联预测问题，

（2）异常检测：主要是结构的异常，比如异常节点连接到各种不同有影响力的社区。

 如图中的红色节点。

 

节点i嵌入ui中的k-th元素uki表示节点i和社区k之间的相关性，则最小化：

由于学习的向量捕获了节点和社区之间的相关性，他们提出了一种新的基于向量的度量来表示节点的异常。度量值越大，节点作为异常节点的倾向越高。

（3）网络对齐

network alignment旨在建立两个网络节点之间的对应关系。Man et al. 2016提出了network embedding 算法来预测anchor links across social networks.这些链接是不同network之间的桥梁。

       思想：扩展原始的Gs网络。思想是通过有Link的用户节点，如果在一个网络中有边，则将对应的网络中加入边，这样就可以在原始网络中加入边，

损失函数：

同时优化以上两个式子。

              总结：

       先进的信息保护网络嵌入通常由两部分组成。一是保留网络结构，以学习节点的表示。另一种是建立节点表示和目标任务之间的连接。前者类似于结构和属性保护网络嵌入，后者通常需要考虑特定任务的领域知识（network applications）。

 

Section 7实验

数据集、benchmarks、分析

一、数据集

最常用的四种真实网络：社交网络、引文网络、语言网络、生物网络。

 

社会网络：

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.

引文网络：

DBLP: http://arnetminer.org/citation

Cora:科学出版物之间的引用关系。除了链接信息之外，每个发布还与一个词向量关联，表示词典中相应单词的缺失/存在。https://linqs.soe.ucsc.edu/node/236.

Citeseer:与cora类似https://linqs.soe.ucsc.edu/node/236

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

语言网络：

Wikipedia词共现网络：http://www.mattmahoney.net/dc/textdata.

生物网络：

PPI:酵母中蛋白质之间成对的物理相互作用http://konect.uni-koblenz.de/networks/maayan-vidal

二、节点分类

 是网络应用的主要任务之一。从本质上讲，基于网络嵌入的节点分类可以分为三个步骤。

（1）首先，应用网络嵌入算法将网络嵌入到低维空间中。

（2）然后，使用已知标签的节点作为训练集。

（3）最后，一个分类器，如Liblinear (Fan et al. 2008)，从训练集中学习。使用经过训练的分类器，我们可以推断出其他节点的标签。

 

评估度量： 可在四种数据集上测试。

网络嵌入算法在各种网络中得到了广泛的应用，并在节点分类上得到了很好的证明。

 

三、链接预测

       度量：precision@K 和 平均精度MAP

Index(x)是排序后第j个节点的index 。即以i为中心，有链接的Index<K的节点个数除以K.

链接预测分类常用的网络：引用网络、社会网络、生物网络。

网络嵌入能够捕获固有的网络结构，因此很自然地适合于链接预测应用。各种网络的广泛实验表明，网络嵌入可以有效地解决链路预测问题。

 

四、节点聚类

       节点聚类是将网络中的节点划分成簇，使同一簇内的节点比不同集群中的节点更相似。聚类分析的度量标准：

精度(AC)和归一化互信息(NMI), AC是用来测量得到的正确标签的百分比

  相同则0不同则1， 置换映射函数，将每个集群标签从数据映射到相应的标签

算法聚类结果和真实聚类，MI是互信息度量https://www.cnblogs.com/gatherstars/p/6004075.html

基于网络嵌入的节点聚类在不同类型的网络上进行了测试。网络嵌入已经成为解决节点聚类问题的有效方法。

 

五、网络可视化

       二维空间中生成有意义的布局。通过可视化工具如t-SNE (Maaten和Hinton 2008)，通过学习节点的低维度表示，用户可以很容易地看到一个复杂网络的大图

 

Section 8 结论和将来的工作

结构和属性保护网络的嵌入是基础。基于结构和属性保护网络嵌入，可以应用现成的机器学习方法。如果有一些侧面信息可用，它可以被整合到网络嵌入中。此外，特定应用程序的领域知识作为高级信息。

其他的方向：

More Structures and Properties：

虽然有各种方法来保护结构和属性，例如一阶和高阶的邻近度度量, communities，非对称的传递性与结构平衡，由于现实世界网络的复杂性，在现有的网络嵌入方法中仍然存在一些未被充分考虑的特殊结构。

（1）      如何合并network motifs (Benson, Gleich，和Leskovec 2016)  ---高阶结构

（2）      如何将，节点的more complexlocal structures作为嵌入的条件

（3）      当前网络嵌入的假设通常基于成对的结构，即如果两个节点有一个链接，那么它们的表示是相似的。这样的话可以在一部分场景应用良好，比如链接预测；但是中心的节点很难编码，因为它一般都有很复杂的结构。

（4）      超边。一些真实网络中，一条边可能不单单只连接两个节点，因此节点中会隐藏更多的信息，有更多的特征。这种边的网络嵌入在真实网络中也是很重要的。

（5）      幂律分布特性表明，网络中的大多数节点与少量的边相关联。因此，对于信息有限的节点（是大多数），很难找到有效的表示方法。这一特性如何影响网络嵌入的性能，如何提高少数节点的嵌入程度，在很大程度上仍未受到影响。

The Effect of Side Information

 

Section5 讨论的算法可以在嵌入时保留side信息

(1)   所有现有的方法都假设网络结构和side信息之间存在一致性，至少是不矛盾的，但是这个假设真实网络中还是个保留的问题，（在哪适用，在哪不适用，在某个网络甚至某个应用中该怎么取舍）。如果Side information 和结构信息相关性很低，可能会导致网络映射成向量的性能变低，也可能正好因为网络结构与侧向信息互补，而提高性能。这些都可能是将来去发现规律，深入研究的地方。

（2）在异构信息网络中，元路径被广泛应用在测量两个对象的相关性中。元路径就是两个节点之间，路径的一个类型序列。元结构就可以提供了一个高阶结构约束。元结构本质上是两节点间节点和边组成的一个有向无环图。（图中的最短路径）这为改进异构信息网络嵌入提供了一个巨大的潜在方向。

 

More Advanced Information and Tasks

一般而言，大多数网络嵌入算法是为通用的目的而设计的，如链接预测、节点分类。这些网络主要是general的，可能不针对一个特定的应用场景。另一个重要的研究方向是探索为更具体的应用设计网络嵌入的可能性，例如是否可以将网络嵌入用在社交网络中检测谣言这种特定的场合中 (Seo、Mohapatra和Abdelzaher 2012;Zhang et al. 2015年)使用网络嵌入来推断社会关系(Tang, Lou，和Kleinberg 2012)吗?每个现实世界的应用都有其自身的特点，将其独特的领域知识融入到网络嵌入中是一个关键。如何将特定的领域知识建模为能够以有效方式集成到网络嵌入的高级信息。

 

Dynamic Network Embedding

       前面所说的都是静态的网络。许多网络都随着时间的推移而不断发展，（Facebook的链接总会随着时间而变化，增加、删除边和节点）。如果有变化就重新学习网络中节点的表示，这样是非常耗时的，也不是一个切实可行的方法，因此现在的网络嵌入不能直接应用于大规模的动态变化的网络中，新的网络嵌入算法应该是能够解决网络的动态演化，这个问题也是一个亟待解决的问题。

More embedding spaces

         现有的网络嵌入方法将网络嵌入到欧氏空间中。最近的一些研究(Krioukov et al. 2010)假设网络的底层结构是在双曲线空间中。在这种假设下，更加突出非均匀度分布和强聚类，因为它们很明显反应在双曲几何的负曲率和度量性质上的。探索其他嵌入空间是另一个有趣的研究方向。