网络表征学习简介 - 好文

    中国计算机学会通讯（CCF）3月份发布了一个关于网络表征学习的专题，对于想了解这方面知识的朋友来说真是雪中送炭啊，感谢大牛们的好文章，下面就来简单谈一谈关于“网络表征学习（Network
Representation Learning
NRL）”的那些事儿...（PS：上一篇文章中我把这个翻译为“网络表示学习”，虽然这两个意思接近，但是还是以文章里面翻译的“网络表征学习”为准吧！）

1.背景

为什么要提出这个概念？

    在《网络表征学习前沿与实践》这篇文章中，作者进行了详细地解释。简单来说就是，当今的数据规模随时间以指数级增长，由于数据之间错综复杂的关联，关联大数据的算力需求与算力供给之间的不平衡，使得关联大数据的处理面临着严峻的挑战。

如何表示这些数据？

“网络”因其强大且灵活的表征能力，成为关联大数据最自然和直接的表达方式。通常，将一个网络表示为由一个点集和边集
共同组成的。通常，信息网络构成的图模型可以由邻接矩阵来表示，因此，早期的处理图结构的工作大部分采用高维稀疏向量的形式，再用矩阵分析的方法。然而，由于现实中网络的稀疏性以及其不断增长的规模，又对此类方法提出了严峻的挑战

  传统基于网络拓扑的表征方式存在哪些问题？

首先，由于拓扑结构通常导致许多网络的分析与处理算法需要许多迭代和组合计算步骤，因而不可避免地产生高复杂度运算的问题。

其次，由于拓扑关系表示节点之间有着强耦合关系，这导致了计算复杂度高、缺乏有效的并行方案，形成了大规模网络难以处理和分析的困境。

第三，目前机器学习尤其是深度学习已经在许多领域显示出强大的数据处理能力，但是它们针对的数据表征通常为一个向量空间中的独立性数据，而非彼此关联的非独立性网络数据，这会导致很多有效解决方案无法直接应用到网络数据上，而必须重新设计基于网络拓扑的模型。

由此可见，传统的基于网络拓扑的表征方式已经成为限制大规模网络处理和分析的瓶颈，所以需要探索更为高效地表征方法。

“点集”和“边集”是否为网络的唯一表征方式？

抛开现象看本质，让我们思考一下网络的形成过程，以社交网络为例，两个人形成一条边，往往是因为两个人之间存在某种相近性，如两个人有共同兴趣，或两个人是同学或同事等等。即存在着另外一个表达“相近性”的隐含向量空间驱动着网络的形成和演化，但这个隐空间不能被人们观测到。所以，如何将观测到的网络拓扑空间“嵌入”到隐含向量空间，这个问题被称之为“网络表征学习（Network
Representation Learning）”或者“网络嵌入（Network Embedding）”

2.概念

网络表征学习旨在将网络中的节点表示成低维、实值、稠密的向量形式，使得得到的向量形式可以在向量空间中具有表示以及推理的能力，从而可以更加灵活地应用于不同的数据挖掘任务中，举例来说，节点的表示可以作为特征，送到类似支持向量机的分类器中。同时，节点表示也可以转化成空间坐标，用于可视化任务。下图是传统的基于网络拓扑的网络分析与基于网络表征学习的网络分析的对比图，基于网络表征的网络分析摆脱了邻接矩阵中边的约束，使得每个节点成为低维空间中的独立数据，进而基于这种向量表达解决后续的应用问题。

3.目标

为了让网络表征更好地支持下游的网络分析任务，网络表征学习通常有两个基本目标。

    一是在低维空间中学习到的表征可以重构出原有网络结构。（如果两个节点有边连接，则它们在低维空间中的距离接近，否则，它们的距离就较远）

二是学习到的表征可以有效地支持网络推断。（若只满足第一个目标，可能会因为过拟合而对未知边的推断起到负面作用）

4.方法

网络表征学习方法主要分为三种：基于矩阵分解的方法、基于随机游走的方法、基于深度神经网络的方法

（1）基于矩阵分解的方法

矩阵分解本身是一种最为有效的表征学习模型，通过对邻接矩阵进行分解，得到每个节点的表征。比如奇异值分解（SVD）以及非负矩阵分解都有着广泛的应用。
Yang <http://www.thunlp.org/~lzy/publications/ijcai2017_fastnrl.pdf>
等人在其后续工作中将基于矩阵分解或者可以转化为矩阵分解的方法总结成同一个算法框架 : 第一步构建节点间的关系矩阵 ,
第二步对该矩阵进行矩阵分解操作得到网络表示。

优点：考虑全局结构性

缺点：过高的时间和空间消耗

（2）基于随机游走的方法

基于随机游走的模型主要是由自然语言处理（Natural Language
Process）中的word2vec启发而来，将节点对应为NLP中的单词，将随机游走得到的序列对应为NLP中的句子。2014年Bryan Perozzi
<https://classes.cs.uoregon.edu/17S/cis607bddl/papers/Perozzi.pdf>
等人开创新的提出了DeepWalk方法，通过随机游走的方式定义节点的上下文结构，即节点的邻居关系，进而通过skip-gram模型来学习网络节点表征。

从基于随机游走的方法思路来看，这些算法本质上是通过保留网络的局部结构性来估计节点的表示，使用随机游走序列而不是邻接矩阵的优势有两点 : 首先 ,
随机游走序列只依赖于局部信息 , 所以可以适用于分布式和在线系统 , 而使用邻接矩阵就必须把所有信息存储于内存中处理 , 面临着较高的计算时间和空间消耗 .
第二 , 对随机游走序列进行建模可以降低建模 0-1 二值邻接矩阵的方差和不确定性。

优点：高效性和鲁棒性、没有特征工程 <https://blog.csdn.net/joycewyj/article/details/51647036>

缺点：只考虑局部结构性、很难找到最佳的采样策略

（3）基于深度神经网络的方法

深度神经网络模型的有效性已经在计算机视觉以及语音处理领域得到广泛验证，它可以得到一个有效的非线性函数学习模型，非常适合用来拟合高度非线性的结构。HNE通过CNN和MLP分别对文本和图像数据进行特征抽取，然后通过转移矩阵将不同类型的数据投影到同一个空间。

优点：相对于浅层模型，深度模型可以更好地对非线性关系进行建模，能够抽取节点所蕴含的复杂语义信息。

缺点：模型难以诠释，特征向量对人而言并不直观

5.总结

以上只是简单总结了一下网络表征学习的相关概念、分类等，具体的方法还有很多，大家可以在北京邮电大学石川老师的主页中找相关的论文研读，包括分类、聚类、嵌入、信息融合、推荐等具体的应用，
http://www.shichuan.org/ShiChuan_ch.html
<http://www.shichuan.org/ShiChuan_ch.html>

本篇博文大部分总结自CCF第3期，网络表征学习专题，我会把相关的文章上传到资源中（资源链接
<https://download.csdn.net/download/swy520/10355726>
），感兴趣的朋友可以下载。如果这篇文章对你有帮助的话，不妨点赞支持一下，给我点儿继续更新的动力~哈哈

热门工具换一换