我的GitHub博客：咖啡成瘾患者

网络的邻接矩阵表示
网络的分布式表示
网络表示学习的经典工作
- Deepwalk
- LINE
- node2vec
网络表示学习的相关论文

最近看了paperweekly的两次关于网络表示学习的直播，涂存超博士与杨成博士讲解了网络表示学习的相关知识。本文将网络表示学习中的一些基本知识，结合自己的一些粗浅的理解，整理记录下来。

网络的邻接矩阵表示

用邻接矩阵是最直观的对网络数据的表示方法。在一个N个节点网络中，一个节点可以用N维向量来表示。

对一个N个节点的网络，用N*N的矩阵来表示一个网络，两个节点之间有边，则在对应的位置标记1（或者边的权值）。

下图所示为一个简单无向图的邻接矩阵表示，其中矩阵是沿对角对称的。

若图为一个无向图，邻接矩阵不一定沿对角对称。

邻接矩阵表示一个图，可以将矩阵的每一行，看做一个节点对应的向量，这种表示方法与文本表示中词的One-Hot表示方法。这种表示方法能够完整地表示图数据，准确地表示网络中的链接关系，但是弊端也很明显，对于一个N个节点的网络，表达这个网络需要N*N的矩阵，并且矩阵过于稀疏，不利于存储大规模网络。

网络的分布式表示

分布式表示（Distributed Representation)最早是由Hinton在1986年提出的一种词向量的表示方法，其核心思想是将词向量映射到一个K维的向量空间中，这样每个词可以用K维向量来表示。大名鼎鼎的Word2vec就是一种对词的分布式表示方案。

同理，将这个概念应用于网络数据中，即网络的分布式表示，网络中的每个节点对应文本中的每个单词，其表示过程就是将每个节点映射到一个K维的向量空间（通常情况下，K远小于网络中节点个数），用K维向量来表示每个节点。事实上，我们可以将这个过程理解为对网络结点的向量表示进行降维的过程，对于一个N个节点的网络，邻接矩阵表示法用N维向量来表示一个节点。但通过这样的降维过程，仅使用K维向量就可以表示一个节点，并且节点向量还能包含一定的“语义”信息，例如连接紧密的结点向量的距离也很相近。这样就将一个高纬向量表示为低维稠密的实值向量。

通常情况下，我们通过对每个节点的向量进行一定的限定，从而给定一个优化方向进行优化，得到一个最优化的结果，即为节点的表示向量。优化目标的设计，往往希望能够尽可能多的将网络信息通过向量表示出来，并使得到的向量具有一定的计算能力。在这个目标的前提下，在优化的过程中，往往会将网络的结构、节点的信息、边的信息等“嵌入”到节点向量中，因此，我们也常常将网络的表示学习过程叫做网络嵌入（Network Embedding)。通过设计特定的优化目标，我们可以将节点的不同信息嵌入到向量中，将节点映射到不同的低维向量空间。

下图所示的是Deepwalk1论文中所展示的节点向量，左图为原始网络，右图为将其映射到二维向量空间后的散点图，我们可以从图中看到，原始图中联系紧密的结点在映射到二维向量空间后距离较近，相同颜色的结点在原始图中联系紧密，在二维向量空间中分布较为密集。

网络表示学习的经典工作

Deepwalk

Deepwalk2是2014年发表在KDD上的一篇论文，这篇文章受到了word2vec3的启发，文章的思路就是对网络应用了word2vec的SkipGram模型。SkipGram模型原本是针对文本的，或者说是针对有序序列的，所以文章先应用随机游走得到一系列的网络中有序的节点序列，这些节点序列类似于文本中的句子，将这些“句子”跑SkipGram模型，从而得到“句子”每个“单词”的向量表示。过程如下图所示：

Deepwalk的随机游走过程事实上是对网络进行采样的过程，将网络中的节点通过随机游走的方式表示出来，两个节点联系越紧密，在一个随机游走过程中共现的可能性越大，反之若两个节点根本不连通，则一个随机游走过程是不可能将两个节点共现。因此deepwalk能很好的将网络的连接情况进行表达，且实验证明在网络规模较大时具有很高的效率。

LINE

LINE4是2015年提出的一中网络表示学习方法，该方法提出了一阶相似度与二阶邻近度的概念，基于这两个邻近度，提出了优化函数，得到的最优化结果即为每个节点的向量表示。

该方法的优化过程可以理解为基于两个假设：

直接相连的节点表示尽可能相近（一阶邻近度），如图中6,7。文中两个节点的联合概率表示其一阶邻近度：

$p_1(v_i,v_j)=\frac{1}{1+exp(-{\vec{u}}_i^T \cdot \vec{u}_j)}$
两个节点公共的邻居节点越多，两个节点的表示越相近（二阶邻近度），如图中5,6。文中用两个节点的条件概率表示其二阶邻近度：

$p_1(v_j|v_i)=\frac{exp({\vec{u}}_j^{'T} \cdot \vec{u}_i)}{\sum_{k=1}^{|V|}exp({\vec{u}}_k^{'T} \cdot \vec{u}_i)}$

node2vec

node2vec5是2016年提出的一种方法，该方法在deepwalk的基础上进行了优化。deepwalk中的随机游走过程，实际是就是一种简单的深搜过程，每次随机随出一个与当前节点直接相连的节点作为后继节点，这种方法虽然能够保证采样到网络中的全局信息，但是对于该节点为中心的局部信息往往不能很好的进行采样。node2vec改进了这个随机游走的过程，它将广度优先搜索与深度优先搜索相结合。

node2vec的随机游走是一个参数控制的随机游走，不同于deepwalk的随机游走，当前节点到后继节点的概率并不是完全相等的。例如下图所示的情况，v为随机游走的当前节点，它的前驱节点为t，那么下一步需要判断v相连的下一个节点，以便进行进一步的游走，这时与其相连的节点的类型有三种：一种是t，v的前驱节点；第二种是 $x_1$ ，不仅与v相连，还与其前驱节点相连；第三种是 $x_2$ 、 $x_3$ ，不是v的前驱同时也不与其前驱相连。

如果节点向第一种节点游走，则返回前驱节点；向第二种节点游走，则为广搜的过程；向第三种节点游走则为深搜的过程。为了控制广搜与深搜，因此设计了参数 $p$ 和 $q$ ，通过这两个参数计算出偏移 $a$ ，则真正的游走概率为原始概率的基础上乘上 $a$ 得到。通过调整这两个参数，可以控制广搜和深搜的程度。所以deepwalk中的随机游走过程，就是一个 $p=1$ 、 $q=1$ 的node2vec。

网络表示学习的相关论文

涂存超博士在github上整理了一些相关论文，我就直接拿来主义了，链到涂存超博士的github上。

Must-read papers on network representation learning (NRL)/network embedding (NE)

Perozzi B, Al-Rfou R, 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. ↩
Perozzi B, Al-Rfou R, 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. ↩
Mikolov T, Sutskever I, Chen K, et al. Distributed representations of words and phrases and their compositionality[C]//Advances in neural information processing systems. 2013: 3111-3119. ↩
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. International World Wide Web Conferences Steering Committee, 2015: 1067-1077. ↩
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: 855-864. ↩