A Survey of Network Embedding

A survey on Network Embedding

---

In this survey, we focus on the categorizing process of and then review the current development in network embedding methods, highlighting its future research directions.

第一部分： the motivation of network embedding

Traditional graph embedding algorithms are often employed to explore the connection between graph structures and network embeddings.

第二部分重点：概述大量网络嵌入方法包括具备对边信息和高阶信息进行保护功能的网络嵌入方法

Introduction：

如何简洁明了地表示网络数据以便使其便于更深入的分析？例如模式识别分析和预测等任务在时空上都可操作。传统的方法是使用一个图G=(V, E)，然而在大型网络中这种方法在网络处理和分析中面临着诸多挑战。例如在计算复杂度方面存在较高的计算开销（如两点之间的距离计算）在并行化方面由于其紧密耦合以及对图结构的高度依赖性而导致难以实现高效的并行化；此外在机器学习任务中由于其与现有算法之间的不适配性而无法直接应用

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

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

Categorization of nodes, grouping of nodes, visualization of networks, and edge forecasting are fundamental aspects in graph analysis.

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

传统网络具有重构能力，并在多种场景中得到应用；具体而言，在网络inference方面可实现以下功能：包括链接预测、识别关键节点以及节点标签的分析等任务。

第2节 NE方法分类 第3节对比当前网络嵌入与传统图嵌入的不同 第4至第6节分别分析NE相关技术 第7节评估框架及其实现细节 第8节研究前沿及未来发展方向

Section2方法分类

**

**

根据被保护的信息：

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

（2） Side information 的 network embedding

（3） Advanced information preservingnetwork embedding

(1) Structure and propertypreserving network embedding

例如，在识别关键节点和预测连接的情况下，在仅基于拓扑结构进行嵌入表示时会遇到诸多挑战。许多研究者致力于保持或恢复这些结构性特征。如邻居信息、高阶邻接关系以及等其他相关属性。将重点聚焦于网络生成机制：link formation。

（2）节点信息或者标识符。包括节点和边的属性、以及节点自身的属性等特征项。这些因素有助于将network node进行有效的聚类分析。一个主要的技术难点在于如何将网络的拓扑结构与边界的 rich information 融合并平衡到network embedding模型中。

（3）期望该种方法能实现对嵌入空间的通用性设计，并基于有监督学习的方法构建特定任务模型。针对特定目标场景的任务模型设计能够有效提升性能表现，并且该方法适用于网络嵌入模型中进行优化。（NLP、CV）

常见的模型：矩阵分解、随机游走及其变化形式和它们的变体。

（1）该技术将任意维度的矩阵映射到低维空间，并旨在逼近原始高维数据低秩结构的目标。该方法能够有效地解决相关问题，并与基于学习低秩空间的传统方法具有相同的优化目标。SVD分解

（2）random walk：保持邻域结构、局部结构，并将每个节点编码为单词、随机路径序列作为句子、以及节点邻居的共现关系作为共同出现的概率。DeepWalk.

(3)深度神经网络：其核心在于建立映射关系。矩阵分解属于线性模型范畴。通过深度神经网络能够有效建模非线性关系。其中SDNE代表深度自注意力网络（SDA），SiNE代表符号嵌入（SiNE）。端到端解决方案如针对Cascade预测以及网络对齐问题的处理方法

Section3Network embedding V S Graph Embedding

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

图嵌入：

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

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

Network embedding 和graphembedding 有本质的不同：

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

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

因此，在本论文中, graph embeddings可以被视为一种特殊的network embeddings, 其核心在于仅专注于构建能够恢复网络结构的network embeddings. 然而, 当前的研究则更加关注于通过分析网络inference来推断其潜在特征. 本论文随后的重点也将围绕这一技术展开分析.

Networks通常源于自然环境，在节点间邻近程度的衡量往往并非直观。这一特征在不同分析场景或应用条件下有所体现。

Section4 structure and Property preserving network embedding

结构保护包含多种不同的类别，在网络中主要涉及以下几个方面：局部邻域结构、高阶节点近邻关系以及网络社群。

(1) Neighborhood structure and high-order

DeepWalk : 保留了邻接关系结构。假设Node在较短的随机游走序列中的出现频率与自然语言处理中的词频分布类似，则采用了 skip-gram 模型来进行节点学习。

Node2vec: 未考虑到多种连接模式，Node2vec明确了网络中节点之间的邻居关系，并采用了基于二阶随机游走策略来进行邻居采样，在深度优先和广度优先的方式下进行采样。该方法能够将同一社区内的节点或具有相似角色的节点映射为具有相似嵌入特征。

能够保护firstorder和second order两种指标。两者都是重要的衡量标准。其中，firstorder指标代表联合概率分布（公式6），而second order指标则代表基于内容的条件概率（公式7）。

(2)Networkcommunities** 开发了一种模块化设计的非负矩阵分解模型(MNMF)，以维持网络中节点的一阶和二阶近邻关系的同时识别出跨尺度社区架构。通过基于NMF的方法来保持微观结构特征，并假设如果一个节点的表征与其所属社区的表征高度相似，则该节点在该社区中可能表现出较高的归属倾向

SDNE:深度学习模型。它能够克服高非线性和稀疏性的挑战以及保证数据完整性。，该方法通过多层感知机架构和深度自动编码器技术实现网络拓扑特征的有效捕捉与表示。

Cao：基于PageRank模型构建，并融合加权转移概率矩阵以生成节点的表征；能够提取权重图结构及其非线性表征。

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）通过保护有向网络的transitive orientation来实现非对称传递性的维持。（若存在路径A→B及B→C，则必然推导出A→C而非相反方向C→A）该研究系统地整合了四种评估指标，并成功将原始奇异值分解（SVD）建模为一种通用的SVD问题，在保持计算效率的同时显著提升了模型的扩展能力。

SiNE同时兼顾连接关系的正例与负例。
结构平衡理论揭示了用户如何让朋友之间的关系比敌人的关系更加亲密。
三元组中的ij相似度大于ik相似度。
构建了一个深度学习模型：该模型由两个具有非线性函数的深层网络构成。

总结中指出保留高级特性的同时也强调了其局限性。然而实现这一目标的策略存在差异，在现有研究中一些方法主要依赖于节点与邻居之间的动态机制来维持上层架构，并非完全独立；同时还需要考虑拓扑结构的影响。此外还需要关注网络信息特征与演化过程同样重要的问题，在实际应用中这些特征如何随时间演变直接影响着整体行为模式

Section5 利用sideinformation做network embedding

Sideinformation 属于另一类关键的信息。它被划分为两个主要类别：一类是节点内容（Node Content），另一类涉及边的类型（Edge Type）。

（1） Node content

节点与其相关联的信息通常包括标签属性以及语义描述等细节。核心挑战在于如何将这些信息与网络的拓扑结构进行有效整合。

MMDW(2016) 首先融合了节点标签信息，并通过 deepwalk 算法进行矩阵分解；随后利用支持向量机模型优化分类边界；最终使得节点表示更具识别能力。

该生成模型（2014年提出）主要关注文档网络中单词与文档之间的联系。研究团队为Le和Lauw于2014年提出了这一方法。每个节点均具有一维有序向量表示ui，并在topic space上基于Relation Topic Model进行学习。同时，在topic space上基于Relation Topic Model进行学习。将每个主题z与同一低维向量空间内的对应向量“z”建立关联后，则遵循如下函数

。

TADW： 证明deepWalk等价于

基于矩阵分解的方法引入文本信息T的同时,该过程带来了较高的计算开销且难以维持节点属性的有序性

研究者们指出,Sun et al.(2016)将context被建模为一种特殊的Node,并在此基础上构建了一个规模更大的网络模型

通过负采样策略与逻辑门电路进行优化后,该方法能够实现对Node及其携带的信息特征进行高效的学习与表征

具体而言,Sun et al.(2016)在联合目标函数中引入了mode-node与node-content之间的关联关系

这种设计不仅能够有效保留原始节点内容特征的信息量,还能够较好地平衡网络结构信息与内容信息之间的关系

**Pan et al. (Pan et al. 2016)**提出的网络架构结合了节点特征与节点标记。编号从1到N的各个node中，每个node i拥有一个词袋模型中的词集\{\bm{w}\}以及标记集\{\bm{l}\}。其中标记总数为L种，在最大化目标函数：W = \{\bm{w}_1, \bm{w}_2, ..., \bm{w}_N\}与C = \{\bm{l}_1, \bm{l}_2, ..., \bm{l}_N\}的基础上实现某种优化目标。

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

LANE 网络架构融合了标签与属性特征。通过余弦相似度计算构建了节点特征、整体架构和分类标志的对应关联矩阵。并结合拉普拉斯矩阵，在三个维度的表征下揭示三者间的相互关联。

综上所述，在许多研究中希望将Node content与network topology相结合，并基于Node content提供了额外约束条件以更准确地描述节点

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

异构网络中存在丰富的多样化节点类型以及边的不同类别。主要问题是如何实现对易购网络中的节点与边进行统一规范，并进一步通过低维向量来进行有效表示。

Yannet al. (Jacob等人于2014年)提出了一种方法，在同一向量空间中学习各节点的表示参数，并在此框架下展开相关推理工作（涵盖不同类型的节点）。当处理Ui属于ti类型时，则通过预测节点i的标签来完成任务。其中损失函数用于衡量预测与真实标签之间的差异。

当i和j之间的w值很大时，i和j应该非常接近。进而就可以将这些异构节点被嵌入到一个潜在的空间中去。目标函数旨在整合前两个公式的内容。为了实现这一目标，我们采用随机梯度下降方法进行优化。

Chang et al. (2015)旨在学习代表性的特征并同时保护异构信息网络的独特属性。节点被划分为两类（A类和B类），边则分为三种类型：A-A型、A-B型和B-B型。研究者利用卷积神经网络（CNN）以及全连接层将节点表示嵌入到公共空间中，并且能够直接比较不同数据的特征而不受类型影响。

Huang and Mamoulis (2017) proposed the use of metapath similarity measures to protect against attacks on heterogeneous information networks. A metapath represents a sequence of node types. They developed an efficient dynamic programming approach to compute truncated metapaths, whose time complexity scales linearly with the size of the network. They drew inspiration from a similar strategy employed by Line and Tang et al. (2015) to maintain proximity in low-dimensional spaces.

Xu et al. (Xu et al., 2017) integrated complementary heterogeneous networks: by constructing two distinct yet interconnected homogeneous networks, they utilized Line-based methods to address the challenges inherent in each network.

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

综上所述，在本研究中我们重点讨论了如何有效保护side information数据这一关键点。其主要区别在于如何将side information与网络结构融合地表示Node节点

Section 6 保护高级信息

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

（1）Information diffusion

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

Simon et al. (Bourigault et al. 2014)提出的node embedding算法被用于forecast information diffusion. By mapping the propagation process onto a heat propagation model, the algorithm learns node representations, thereby enabling the diffusion kernel to explain the training data. Li et al. (Li et al. 2017) introduced a fully connected deep learning model to address cascading prediction challenges.

（2）异常识别：主要关注于网络结构上的不寻常现象。例如，在社交网络中一个高影响力节点与其他重要群体建立了复杂联系。

如图中的红色节点。

节点i在嵌入空间ui中的第k个元素uki反映节点i与社区k之间的关联程度，则最小化：

由于向量成功反映了节点与社区之间的关联性，在此基础上研究团队开发出了一种新的基于向量的方法来量化异常节点的存在概率。当度量值增大时，在该条件下出现异常的可能性也越显著

（3）网络对齐

该网络对齐方法的目标是创建两个网络节点之间的对应关系。Man等人于2016年开发了一种网络嵌入算法用于预测社交网络间的锚定链接。这些连接在不同网络之间起到桥梁作用。

核心思想在于对原始Gs网络进行扩展。具体而言，在任何基于具有Link关系的用户节点的情况下，在对应的网络中添加相应的边。

损失函数：

同时优化以上两个式子。

总结：

先进信息保护网络的嵌入方案一般由两部分构成其中一部分旨在保留网络的拓扑结构以便于学习节点特征另一部分则致力于构建节点特征与其具体任务之间的关联前者类似于基于结构和属性的信息保护网络嵌入方案而后者则需结合特定任务领域的专业知识来实现相关应用

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：科学出版物间的引用关系也十分丰富。除了链接信息以外, 每个发表对象还与其对应一个词向量相关联, 用于指示该词典中相应单词是否存在

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.

生物网络：

Protein-Protein Interaction (PPI): The physical interactions between protein complexes in yeast cells, as documented in the Maayan-Vidal network dataset available at http://konect.uni-koblenz.de/networks/maayan-vidal

二、节点分类

在网络应用中扮演着核心任务的一部分。从基础层面上来说，基于网络嵌入的节点分类包括三步内容。

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

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

（3）最终步骤中，在研究中采用 Liblinear (Fan et al. 2008) 这一方法，在这一过程中通过训练数据集进行学习。通过已训练完成的分类器, 我们能够推断出剩余节点对应的标签.

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

网络嵌入技术展现出显著的应用潜力，并成功应用于各类网络环境，在节点分类任务中表现出色。

三、链接预测

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

Index(x)表示在排序后的第j个位置上的节点索引值。其值等于围绕中心点i的所有与之相连的节点中满足索引小于K的数量除以K。

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

通过捕捉固有网络架构特征的机制，网络嵌入技术能够精准反映实际连接模式。基于这一优势，在多种真实世界网络上的大量实证研究显示，在链接推断任务中表现出色。此外，在多种真实世界网络上的大量实证研究显示，在链路预测任务中展现出显著的优势

四、节点聚类

节点聚类旨在将网络中的各个节点分组为簇，并使同一簇内部的所有节点与不同簇之间的所有节点具有更高的相似度。
在聚类分析中通常采用的标准包括衡量各簇内部紧密程度和区分度的指标。

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

相同则0不同则1，

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

该算法体系的聚类效果与实际类别之间的关系由互信息度量来评估https://www.cnblogs.com/gatherstars/p/6004075.html

基于网络嵌入技术的节点聚类算法在多种类型的实际网络中进行了实验验证。该方法已被广泛认为是解决节点聚类问题的有效手段。

五、网络可视化

在二维空间中实现有意义的布局分布。借助可视化工具如t-SNE（Maaten和Hinton, 2008），基于对节点低维表示的学习过程能够帮助用户直观地观察到一个复杂网络的整体架构。

Section 8 结论和将来的工作

结构与属性保护网络的嵌入构成了基础。
可利用结构与属性保护网络的嵌入来采用现有的机器学习技术。
若存在额外的信息源，则这些信息可整合为网络嵌入的一部分。
此外，在特定应用场景中所积累的专业知识也可被视为更高层次的信息。

结构与属性保护网络的嵌入构成了基础。
可利用结构与属性保护网络的嵌入来采用现有的机器学习技术。
若存在额外的信息源，则这些信息可整合为网络嵌入的一部分。
此外，在特定应用场景中所积累的专业知识也可被视为更高层次的信息。

其他的方向：

More Structures and Properties：

尽管存在多种方法用于保护节点间的结构关系及属性特征（如一阶邻域相似性和高阶相似性指标、社区发现算法以及基于非对称传递性的网络分析框架），但鉴于现实世界的复杂性，在现有网络嵌入技术中仍未能充分捕捉到某些特殊的结构性特征。

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

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

（3）现有网络嵌入假设通常基于配对的网络结构，在这种设定下如果两个节点之间存在连接，则它们的表示向量具有较高的相似度。这种方法在某些应用领域表现良好，例如链接预测问题；然而中心节点难以有效编码其复杂结构信息。

超边。在许多实际网络中（如社交网络或信息网），一条边可能不仅仅仅限于连接两个节点。这使得节点之间不仅存在简单的关联关系，并且能够隐藏更多额外的信息并具有更多的属性。这些多端点连接的网络嵌入同样具有重要意义。

（5）遵循幂律分布规律的网络中发现，在多数情况下这些具有数据不足特征的关键节点难以获得有效的表征方式。尽管这一特性不仅对网络嵌入性能的影响、还有提升少数关键节点表征能力的问题尚未得到充分解决。

The Effect of Side Information

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

现有方法普遍假设网络架构与side信息之间具有一致性，并且至少不自相矛盾。然而这一假设计实应用中仍是一个待探讨的问题——例如，在某个领域或应用中该如何权衡取舍？当Side information与架构信息的相关性较低时（即两者相互独立），可能会导致基于向量表示的网络性能下降；但也有可能因架构与side信息相互补充而提升性能水平。这些可能成为未来研究的重要方向。

（2）在异构信息网络框架下，元路径得到了广泛应用，在评估两个实体之间的关联程度方面发挥着重要作用。元路径即为一种类型序列，在此过程中能够描述连接关系的本质特征。通过构建一个更高层次的结构性限制模型，在这种模型指导下进行分析能够更好地理解数据内在规律。（图中的最短路径）这一概念不仅简化了复杂关系建模的过程，并且为改进异构信息网络嵌入研究提供了重要方向。

More Advanced Information and Tasks

通常情况下而言, 大多数用于处理图数据的传统图神经网络架构主要关注于通用任务的设计, 如链接预测和节点分类等场景。然而, 这些架构往往并不具备对特定应用场景的高度定制化能力。另一个值得探讨的研究方向是如何将更加针对性的设计引入到图神经网络架构中, 比如在社交分析任务中能否利用图神经网络来进行谣言检测 (Seo、Mohapatra和Abdelzaher 2012;Zhang et al. 2015年) 或者利用图神经网络来推断社会关系 (Tang, Lou和Kleinberg 2012) 呢?每个现实世界的应用场景都有其独特的特点, 将这些领域的专业知识成功融入到图神经网络架构中是一个关键步骤。如何将这种专业知识建模为能够有效整合到现有框架中的高级信息将是实现这一目标的关键所在。

Dynamic Network Embedding

传统的网络分析主要关注的是静态结构，在这种情况下很难捕捉到实时变化的特点。然而，在实际应用中（例如，在Facebook等社交平台中），连接信息会随着时间不断更新）。当网络结构发生变化时（即边和节点的数量发生增减），传统的嵌入方法难以适应这种变化。因此，在处理大规模动态网络时直接应用现有的网络嵌入方法是不可行的。为了应对动态网络的变化需求（即如何在不完全重新计算嵌入的情况下捕捉到实时变化），研究者们提出了多种新的算法思路。

More embedding spaces

现有网络嵌入方法倾向于将网络嵌入到欧几里得空间中。近期研究(Krioukov et al., 2010)假定网络的基础架构位于双曲空间中。在此框架下，则会更加凸显非均匀度分布与强聚类特征；这是因为这些特征明显体现在双曲几何中的负曲率及度量特性上。探索其他可能的嵌入空间则构成了另一个值得深入探讨的方向。