- 背景简述
随着社交媒体的飞速发展，在线社交网络成为了人们赖以生存的第二世界。在类似 Facebook 和新浪微博等社交网络的快速发展下， 很多研究者着力于在网络数据上设计快速有效的算法。 在有关网络的研究中, 一个重要的问题就是如何合适的表示网络信息。 传统的网络表示一般使用高维的稀疏向量，但是高维稀疏的表示也成为了人们使用统计学习方法时的局限所在，因为高维的向量将会花费更多的运行时间和计算空间。
网络嵌入（Network Embedding）旨在将网络中的节点表示成低维、实值、稠密的向量形式，使得得到的向量形式可以在向量空间中具有表示以及推理的能力，同时可轻松方便的作为机器学习模型的输入，进而可将得到的向量表示运用到社交网络中常见的应用中，如可视化任务、节点分类任务、链接预测以及社区发现等任务，还可以作为社交边信息应用到推荐系统等其他常见任务中。
- 离散网络嵌入模型简介
离散网络嵌入模型（DNE）分为两个部分，包括离散的网络表示和离散的多分类分类器。因为数据已经被二值化，所以整个的分类在汉明空间进行[1]。
DNE目标是将欧氏空间中的高维数据，通过一定步骤的运算、分解，映射到低维的二值空间中，假设输入数据S=[s1...sn]是一个n维的向量，其中sn是一个n维的样本对象，则要得到的是S的低维二值表示B=[b1...bn],bn是m维的对象，bi={0,1}；以及离散多分类(c个)分类器W=[w1...wc]，总体思路为，将得到的bn与每一个小分类器w进行内积运算，取内积最大的一类作为样本的最终分类。
因为DNE在进行各种运算和存储的过程中采用二值存储，原本需要几个字节才能存储的数据只需要几个bit就能存储，二值也大大减小了计算的难度，所以在保证一定准确率的情况下，DNE可以很好的提高计算和存储效率。
3.相关研究
网络嵌入的目标是将图表示转换成连续的特征值，其中每个节点对应于一个低维向量。关键思想是使原本空间中相关的节点在向量空间中彼此接近，以保持原本网络的结构关系。新的表示方法问世之后，使用基于新表示法的机器学习算法可以很容易地执行网络分析任务，其中比较出名的算法包括graph clustering[2]、link prediction[3]以及personalized recommendation[4]，这些算法在网络分析任务中非常有效，因此网络嵌入在近几年吸引了很多人的关注和研究。
网络嵌入可以大致分为三类：（1）基于随机游走的算法，（2）基于矩阵分解的算法，（3）基于深度学习的算法。基于随机游走的算法是在网络上产生大量的截断的随机路径，并保持路径中节点原本的邻域关系。Perozzi等人借用了NLP问题中的单词表示思想，提出DeepWalk框架[5]，这是第一个以在线方式嵌入网络的算法框架。 Node2Vec[6]进一步利用了偏置的随机游走来捕获所有网络节点的全局结构信息。其他基于随机游走的算法或者学习非对称性的近邻，或者通过在网络中捕获大量的信息源来进行网络嵌入的学习。
基于矩阵分解算法的目标是将矩阵分解为低维潜在的因子，这些因子可以视为原网络节点的新表示，它们在不同的目标函数中各不相同。有一些早期的方法，比如说模块化最大化和特征分解，它们的目的是学习指示函数，而还有一些算法例如TADW[7]，是利用两次过渡概率矩阵来归纳矩阵的因式分解。最近，一些算法研究人员已经证明，包括LINE[8]、PTE[9]、Deep Walk和Node2Vec在内的这些算法，本质上其实就是基于矩阵分解的算法[10]。而基于深度学习的算法，开发人员已经提出了许多的算法，但是与一般的算法不同，它们主要是用来研究非线性的节点表示[11][12]。
