网络表征学习的必要性

真实世界中的复杂系统通常都可以构建为网络形式，比如社交网络、生物网络等。为了更好地支持基于网络数据的应用，如何有效地表示网络是关键步骤。而随着网络数据规模的快速增大，传统的基于网络拓扑的表征方式显露出愈加明显的缺陷。

首先，由于拓扑结构通常导致许多网络的分析与处理算法需要许多迭代和组合计算步骤，因而不可避免地产生高复杂度运算的问题。比如，为了评估网络中一个节点的重要性，我们不得不首先评估其邻居节点的重要性，以此类推，直到评估完所有节点的重要性。这种高复杂度的处理过程极大阻碍了相应算法在大规模网络上的应用。

其次，由于拓扑关系表示节点之间有着强耦合关系，使得并行和分布式运算很难被直接应用到网络数据。由于节点之间边的存在，如果简单地将不同节点分配到不同的服务器上运算，则服务器之间需要频繁地通信，因此严重影响加速比。

第三，目前机器学习尤其是深度学习已经在许多领域显示出强大的数据处理能力，对许多问题都已给出了有效的解决方案。但是它们针对的数据表征通常为一个向量空间中的独立性数据，而非彼此关联的非独立性网络数据，这会导致很多有效解决方案无法直接应用到网络数据上，而必须重新设计基于网络拓扑的模型。由此可见，传统的基于网络拓扑的表征方式已经成为限制大规模网络处理和分析的瓶颈。近年来，不少研究者开始关注网络表征学习领域^[1]，研究如何为网络中的节点学习一个低维空间中的有效向量表征，从而更好地支持后续的网络应用。图1展示了基于网络表征学习的网络分析摆脱了邻接矩阵中边的约束，使得每个节点成为低维空间中的独立数据，进而基于这种向量表达解决后续的应用问题。

网络表征学习已经在多种网络处理和分析任务上验证了其有效性，比如节点分类^[1]、链路预测^[2]以及网络可视化^[3]。网络表征学习需要在低维空间中学习节点的稠密且连续的表征，使得观测的网络结构中的噪音或者冗余信息可以被去除，同时本质的结构信息得以保持。相比于传统的节点表征方法，这种节点表征的优势是显而易见的。比如节点已经不再有耦合关系，使一些主流的并行计算方案应用在大规模网络上变得可行。同样，网络表征学习也为利用机器学习工具处理网络数据提供了新的机遇，许多现有的机器学习方法可以直接引入过来解决网络问题。

为了让网络表征更好地支持下游的网络分析任务，网络表征学习通常有两个基本目标。一是在低维空间中学习到的表征可以重构出原有网络结构，这就要求，如果两个节点有边连接，则它们在低维空间中的距离接近，否则，它们的距离就较远。第二个目标是学习到的表征可以有效地支持网络推断。只实现第一个目标在实际中并不足以支持网络推断任务。以链路预测为例，如果只考虑第一个目标，一些学习算法会倾向于完美拟合邻接矩阵中所有的0和1，而这种处理方式容易受到过拟合的影响，对未知边的推断会起到负面作用。

从图嵌入到网络表征学习

图嵌入算法的目的与网络表征学习有相似的地方。图嵌入也是根据一个图，学习图中节点的低维表征，代表性的算法有Isomap^[4], LLE^[5]和LE^[6]。这些传统图嵌入算法的基本思路是基于某种规则，比如KNN方法，从图像或文本数据集中构建一个相似度矩阵，利用降维方法学习得到每个数据的表征，该表征可以保持这种构建的图的结构。所以本质上图嵌入算法重点关注网络表征学习的第一个目标，即保持图的结构。传统图嵌入方法所针对的数据实际上是图像或文本等非结构化数据，所要达到的目的是学习图像或文本的表征。他们所采用的图通过计算数据之间的相似度得到，而并非是真实世界中的网络，这种相似度一旦通过计算得到，就认为表示了数据之间的准确关系。可真实世界中网络之间的边，通常只表示节点之间存在着关系，节点之间具体的相似度还需要根据具体任务去计算，这也是为何在网络表征学习中，为了更好地支持网络推断，除了现有观测到的网络边之外，我们还需要进一步考虑网络的高阶结构、网络的性质等。

网络表征学习的必要性

真实世界中的复杂系统通常都可以构建为网络形式，比如社交网络、生物网络等。为了更好地支持基于网络数据的应用，如何有效地表示网络是关键步骤。而随着网络数据规模的快速增大，传统的基于网络拓扑的表征方式显露出愈加明显的缺陷。

首先，由于拓扑结构通常导致许多网络的分析与处理算法需要许多迭代和组合计算步骤，因而不可避免地产生高复杂度运算的问题。比如，为了评估网络中一个节点的重要性，我们不得不首先评估其邻居节点的重要性，以此类推，直到评估完所有节点的重要性。这种高复杂度的处理过程极大阻碍了相应算法在大规模网络上的应用。

其次，由于拓扑关系表示节点之间有着强耦合关系，使得并行和分布式运算很难被直接应用到网络数据。由于节点之间边的存在，如果简单地将不同节点分配到不同的服务器上运算，则服务器之间需要频繁地通信，因此严重影响加速比。

第三，目前机器学习尤其是深度学习已经在许多领域显示出强大的数据处理能力，对许多问题都已给出了有效的解决方案。但是它们针对的数据表征通常为一个向量空间中的独立性数据，而非彼此关联的非独立性网络数据，这会导致很多有效解决方案无法直接应用到网络数据上，而必须重新设计基于网络拓扑的模型。由此可见，传统的基于网络拓扑的表征方式已经成为限制大规模网络处理和分析的瓶颈。近年来，不少研究者开始关注网络表征学习领域^[1]，研究如何为网络中的节点学习一个低维空间中的有效向量表征，从而更好地支持后续的网络应用。图1展示了基于网络表征学习的网络分析摆脱了邻接矩阵中边的约束，使得每个节点成为低维空间中的独立数据，进而基于这种向量表达解决后续的应用问题。

网络表征学习已经在多种网络处理和分析任务上验证了其有效性，比如节点分类^[1]、链路预测^[2]以及网络可视化^[3]。网络表征学习需要在低维空间中学习节点的稠密且连续的表征，使得观测的网络结构中的噪音或者冗余信息可以被去除，同时本质的结构信息得以保持。相比于传统的节点表征方法，这种节点表征的优势是显而易见的。比如节点已经不再有耦合关系，使一些主流的并行计算方案应用在大规模网络上变得可行。同样，网络表征学习也为利用机器学习工具处理网络数据提供了新的机遇，许多现有的机器学习方法可以直接引入过来解决网络问题。

图1 传统基于网络拓扑的网络分析和基于网络表征学习的网络分析的对比

为了让网络表征更好地支持下游的网络分析任务，网络表征学习通常有两个基本目标。一是在低维空间中学习到的表征可以重构出原有网络结构，这就要求，如果两个节点有边连接，则它们在低维空间中的距离接近，否则，它们的距离就较远。第二个目标是学习到的表征可以有效地支持网络推断。只实现第一个目标在实际中并不足以支持网络推断任务。以链路预测为例，如果只考虑第一个目标，一些学习算法会倾向于完美拟合邻接矩阵中所有的0和1，而这种处理方式容易受到过拟合的影响，对未知边的推断会起到负面作用。

从图嵌入到网络表征学习

图嵌入算法的目的与网络表征学习有相似的地方。图嵌入也是根据一个图，学习图中节点的低维表征，代表性的算法有Isomap^[4], LLE^[5]和LE^[6]。这些传统图嵌入算法的基本思路是基于某种规则，比如KNN方法，从图像或文本数据集中构建一个相似度矩阵，利用降维方法学习得到每个数据的表征，该表征可以保持这种构建的图的结构。所以本质上图嵌入算法重点关注网络表征学习的第一个目标，即保持图的结构。传统图嵌入方法所针对的数据实际上是图像或文本等非结构化数据，所要达到的目的是学习图像或文本的表征。他们所采用的图通过计算数据之间的相似度得到，而并非是真实世界中的网络，这种相似度一旦通过计算得到，就认为表示了数据之间的准确关系。可真实世界中网络之间的边，通常只表示节点之间存在着关系，节点之间具体的相似度还需要根据具体任务去计算，这也是为何在网络表征学习中，为了更好地支持网络推断，除了现有观测到的网络边之外，我们还需要进一步考虑网络的高阶结构、网络的性质等。

网络表征学习方法

迄今为止，有许多网络表征学习方法被提出来，都是基于其在学习过程中所考虑的不同场景。这些方法大致可以分为三类：第一类是结构与性质保持的网络表征学习方法，第二类是融合伴随信息的网络表征学习方法，第三类是融合高级信息的网络表征学习方法。结构与性质保持的网络表征学习方法是最基本的一类。此类方法重点考虑网络的拓扑结构与性质，而第二类和第三类中的信息则是网络表征学习最为本质和基础的信息。融合伴随信息的网络表征学习方法考虑了真实网络中节点或者边所具有的属性、内容、标签等信息，为表征学习提供了拓扑以外的语义信息等。如果说前两类方法针对的是常见的网络分析任务，融合高级信息的网络表征学习方法则是针对专有任务而设计的，需要根据具体任务场景，引入特定的先验信息以保证在具体任务上可以发挥更好效果的一种方法。

结构与性质保持的网络表征学习

网络的结构和性质是网络中最基本的两种信息，因此在低维空间中保持结构和性质是网络表征学习最根本的要求。保持网络的结构不仅仅指保持观测到的网络拓扑结构，更重要的是保持网络的高阶结构。所观测到的网络拓扑通常是一阶结构，高阶结构则包括二阶结构等。二阶结构考虑了两个节点的邻居关系得到的相似度^[3,7]，如图2所示。真实网络往往具有稀疏性，这也就意味着两个节点之间虽然没有边，但并不表示他们没有关系，而这种潜在的关系可通过两个节点的邻居节点所反应出来，普遍认为两个节点所共有的邻居节点越多，则他们之间的相似度越大。因此二阶结构的引入是对一阶结构的有效补充，对于链路预测等任务有着积极的作用。以此类推，更具有一般性的，还可以结合节点的K步关系得到K阶结构来表征节点相似度^[8]。除此以外，节点的高阶结构还包括节点上下文结构^[1,9]。这种结构通常由随机游走得到，通过在该点随机游走得到一个节点序列，而处在该序列中的节点则被认为是这个节点的上下文，如图3所示。不同的随机游走可以产生不同的序列，也反应了网络的不同结构信息^[9]，如图4所示。基于不同的随机游走策略，所得到的结构既可以反应同质性，也可以反应节点的结构等同性。网络中还普遍存在着社区结构，它与前面高阶结构不同，反应的是一个社区内节点的相似性。因此，也有了方法融合这种结构，使得同一社区内的节点有相似的表征，进而增强了表征的判别性^[10]。

图2 节点的一阶结构和二阶结构。节点5和6的二阶 结构可以通过邻居节点1,2,3,4反应，节点6和7的直接连接可认为是一阶结构

图3　DeepWalk中基于随机游走的节点上下文结构

图4 不同随机游走策略所反应出的不同结构信息， 上图反应了网络的同质性，下图反应了节点的结构等同性

真实网络中所具备的性质也能为网络表征学习提供必需的指导。比如，在有向网络中的非对称传递性表明里的三个节点A, B, C。如果A→B, B→C，则A有更大的可能性会指向C；相反，C指向A的可能性很小。如图5所示。这种非对称传递性质在有向网络中非常普遍，它对于有向网络的链路预测有着极为重要的指导意义。而传统的低维空间由于具有对称性，给保持这种非对称相似性带来了极大挑战^[2]。同样的，符号网络具备的结构平衡性质，也为衡量符号网络中三个节点的关系提供了丰富信息^[11]。

图5　有向网络中的非对称传递性

本质上大多数结构和性质保持的网络表征学习都是为了显式或隐式地引入更多更高阶的相似度信息，区别则是考虑了不同的高阶相似度以及用不同的方式引入高阶相似度。这也证明了在网络表征学习中，节点的高阶相似度有着极其重要的意义。由于结构是网络最显著的信息，所以许多工作都是围绕这一点开展的。性质保持的网络表征学习则是相对较新的研究课题，但已经显示出它对于学习一个好的节点表征有着重要的影响。

融合伴随信息的网络表征学习

真实网络中除了网络的拓扑结构之外，还有着丰富的伴随信息。伴随信息通常指节点的标签、内容、类型等信息。节点的标签通常可以引入判别性信息，因此，有网络表征学习通过结合支持向量机的模型来融合标签信息^[12]。节点的内容可以指代文本网络中的文本信息，也可以指代社交网络中用户的属性信息，并包含了丰富的语义信息。这些节点还产生了通过基于矩阵分解的方法融合节点内容的网络表征学习模型^[13]。类型信息通常与异构信息网络表征学习息息相关。与传统的同构信息网络不同，异构信息网络中的节点和边都有多种类型，因此需要考虑不同类型的节点以及同样类型的节点之间的相互关系^[14]。

融合伴随信息在某种程度上为节点之间的关系提供了一种额外的相似度信息辅助，不同之处是融合伴随信息与拓扑结构的方式不同。许多融合伴随信息的网络表征学习都可以由结构保持的网络表征学习模型扩展而来。

融合高级信息的网络表征学习

前面两种类型的网络表征学习可以认为是一种通用的网络嵌入方法，因为他们的设计与下游的任务无关，他们所得到的表征可以支持大多数的网络分析任务。然而真实世界的应用是多种多样的，许多专有的网络分析任务需要设计专门的网络表征学习模型。这种网络表征学习模型针对的是特定任务，因此，为了更好地支持这项任务，这类模型需要引入关于该任务相应的高级信息。比如在基于网络表征学习的信息扩展任务中，我们不仅要考虑网络的拓扑结构，还要与热扩散过程相结合^[15]。在网络对齐任务中，不仅要考虑两个网络内部之间的结构，同时还要引入两个网络之间的锚边的映射，以此来构建两种表征空间的关系^[16]。在网络异常点检测中，我们需要首先定义何为异常点，进而根据这个信息设计合适的节点表征及异常点度量方法^[17]。

由此可见，高级信息保持的网络表征学习通常包括两个部分，一部分是使得节点表征保持原有网络结构信息，另一部分是构建起节点表征和目标任务之间的联系。第一部分与结构和性质保持的网络表征学习非常相似，而第二部分则需要考虑领域知识。这一类模型拓展了网络表征学习的应用领域，使得现实世界中更多基于网络表征学习的应用变得可行。

常用的网络表征学习模型

尽管在不同场景下提出了不同的网络表征学习方法，但通常来说，网络表征学习模型包括三种：
(1)基于矩阵分解的模型；(2)基于随机游走的模型；
(3)基于深度神经网络的模型。矩阵分解本身是一种最为有效的表征学习模型，已经被广泛应用在各个场景，比如维度约减。我们可以对网络的邻接矩阵进行矩阵分解，由此得到每个节点的表征。在这类模型中，奇异值分解(SVD)^[2]以及非负矩阵分解^[10]都有着广泛的使用。基于随机游走的模型则主要是由自然语言处理中的Word2vec^[18]启发而来，通过随机游走的方式可以定义节点的上下文节点结构，进而通过保持这种结构来学习节点表征。深度神经网络模型的有效性已经在计算机视觉以及语音处理领域得到广泛验证，它可以得到一个有效的非线性函数学习模型，非常适合用来拟合网络高度非线性的结构^[3]。

展望

在实际中，结构和性质保持的网络表征学习是一个基石，如果一种方法不能很好地保持这种基本要素，则意味着在嵌入空间中本质信息的丢失将会严重影响后续的网络分析任务。在结构和性质保持的网络表征学习的基础上，融合伴随信息和融合高级信息会进一步提高表征学习的有效性。近年来虽提出了大量的网络表征学习方法，但依然有一些值得未来进一步探索的重要问题。

1. 保持更多的结构和性质。结构和性质对于网络表征学习的重要性已经被广泛验证，因此考虑更多的结构和性质是必要的，比如网络中常见的motif结构，或者超网络中的超边结构等。

2. 进一步深入探索伴随信息的影响。随着社交媒体的蓬勃发展，伴随信息已经变得非常重要且广泛。然而在融合伴随信息的时候，需要考虑以下几个问题：所有的伴随信息是否对网络表征学习都有着积极的作用？伴随信息往往是由用户产生的，里面包含的噪音如何削减？伴随信息和网络拓扑究竟是一种什么样的关系，需要挖掘二者之间的一致性还是互补性？

3. 结合更多的高级信息和任务。网络的实际应用以及潜在应用远远超过了我们目前所研究的任务。网络表征学习已经在一些任务上显示出了卓越的性能，因此未来可以结合更多的任务继续拓展网络表征学习的应用范畴。比如网络上的谣言检测、Social tie的推测等，是否可沿着网络表征学习的思路进一步得到优化？

未来，网络表征学习依然是网络分析任务中的重要一环，继续探索与研究网络表征学习对支撑实际网络应用起着至关重要的作用。  

参考文献

[1] Perozzi B, Al-Rfou R and Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014:701-710.

[2] Ou M, Cui P, Pei J and et al. Asymmetric transitivity preserving graph embedding[C]// Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2016: 672-681.

[3] Wang D, Cui P and Zhu W. Structural deep network embedding[C]// Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.ACM, 2016:1225-1234.

[4] Tenenbaum J. B, De Silva V and Langford, J. C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500):2319-2323.

[5] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science. 2000, 290(5500):2323-2326.

[6] Belkin M, and Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering[C]// Advances in neural information processing systems, 2002:585-591.

[7] Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web, 2015: 1067-1077. ACM.

[8] Cao S, Lu W, and Xu Q. Grarep: Learning graph representations with global structural information[C]// Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, 2015: 891-900.

[9] Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]// Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016:1225-1234..

[10] Wang X, Cui P, Wang J, et al. AAAI 2017b. Community preserving network embedding.

[11] Wang S, Tang J, Aggarwal C, et al. Signed Network Embedding in Social Media[C]// Proceedings of the 2017 SIAM International Conference on Data Mining. 2017: 327-335.

[12] Tu, C.; Zhang, W.; Liu, Z.; and Sun, M. 2016. Maxmargin deepwalk: discriminative learning of network representation. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016), 3889-3895.

[13] Yang, C.; Liu, Z.; Zhao, D.; Sun, M.; and Chang, E. Y. 2015. Network representation learning with rich text information. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 2111-2117.

[14] Chang, S.; Han, W.; Tang, J.; Qi, G.-J.; Aggarwal, C. C.; and Huang, T. S. 2015. Heterogeneous network embedding via deep architectures. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 119-128. ACM.

[15] Bourigault, S.; Lagnier, C.; Lamprier, S.; Denoyer, L.; and Gallinari, P. 2014. Learning social network embeddings for predicting information diffusion. In Proceedings of the 7th ACM international conference on Web search and data mining, 393–402. ACM.

[16] Man, T.; Shen, H.; Liu, S.; Jin, X.; and Cheng, X. 2016. Predict anchor links across social networks via an embedding approach. IJCAI.

[17] Hu, R.; Aggarwal, C. C.; Ma, S.; and Huai, J. 2016. An embedding approach to anomaly detection. In Data Engineering (ICDE), 2016 IEEE 32nd International Conference

on, 385–396. IEEE.

[18] Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G. S.; and Dean, J. 2013b. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, 3111–3119.