七、WALKLETS

1. 社交网络本质都是分层的，每个人（顶点）都属于多个社区，这些社区范围从小型社区（如家庭、朋友）、中型社区（如学校、企业）到大型社区（如民族、国家），代表了不同尺度 scale 的关系。

   随着关系尺度的变化，网络的拓扑结构也发生变化。如下图所示：

   • 当考虑家庭、朋友关系这一尺度时只有黄色部分构成一个社区。
   • 当考虑学校、企业关系这一尺度时只有蓝色部分（包括黄色部分）构成一个社区。
   • 当考虑民族、国家关系这一尺度时所有顶点都构成一个社区。

   在这个过程中尺度扮演者关键的角色，它决定了社区的规模以及顶点归属到哪些社区。

   

2. 在网络representation 学习的任务中，大多数方法都是一刀切：每个顶点得到一个融合了所有尺度的representation ，无法明确的捕获网络内结点之间的多尺度关系，因此无法区分网络在各个尺度上的差异。

   GraRep 方法显式的建模多尺度关系，但是计算复杂度太高从而无法扩展到真实世界的大型网络。

   论文 《Don’t Walk, Skip! Online Learning of Multi-scale Network Embeddings》 提出了 WALKLETS 模型，该模型是一种在线的图reprensentation 学习方法，可以捕获网络顶点之间的多尺度关系，并且可扩展性强，支持扩展到百万顶点的大型网络。

   WALKLETS 将每个顶点映射到低维reprensentation 向量，该向量捕获了顶点所属社区的潜在层次结构。在预测时可以用单个尺度 representationi 或者组合多个尺度 representation 来提供顶点更全面的社区关系。

   下图来自于 Cora 引用网络的一个子网络的二维可视化，中心的红色顶点表示源点，顶点颜色代表该顶点和源点的距离：距离越近颜色越红，距离越远颜色越蓝。

   • 左图给出了细粒度 representation 相似度的结果。在这一尺度下，只有源点的直系邻居才是相似的。
   • 右图给出了粗粒度 representation 相似度的结果。在这一尺度下，源点附近的很多顶点都是相似的。

   

3. 我们受到一个事实的启发：通过一个结点可能同时隶属于不同层次的圈子，如家庭、学校、公司等等。针对这些不同的社区进行建模和预测不仅对于了解网络结构至关重要，而且还具有重要的商业价值，如更有效的广告定向。

7.1 模型

1. 给定图 ，其中：

   • 为图的顶点集合， 表示图的一个顶点。
   • 为图的边集合， 表示顶点 之间的边，其权重为 。权重衡量了边的重要性。

   定义邻接矩阵 为：

   

   这里假设所有的权重都是正的。

   定义度矩阵degree matrix 为一个对角矩阵：

   

   假设顶点 转移到顶点 的概率正比于 ，则定义转移概率矩阵 probability transition matrix： 。其中 定义了从顶点 经过一步转移到顶点 的概率，因此也称为一阶转移概率矩阵。

   多尺度 representation 学习任务需要学习 个 representation ，其中 捕获了网络在尺度 的视图 view 。从直观上看，每个 representation 都编码了视角网络在不同视图下的相似性，对应于不同尺度下的潜在社区成员关系。

2. DeepWalk 采用截断的随机游走序列来对共现顶点pair 对建模，其目标是估计顶点 和它邻居结点共同出现的可能性。根据论文 《NeuralWord Embedding as Implicit Matrix Factorization》 ， 它等价于矩阵分解。即：基于层次Softmax 的 DeepWalk 模型的优化目标对应于矩阵 的分解，其中：

   

   其中：

   • 是一个one-hot 向量，其第 个元素为1 其余元素为零。
   • 表示向量的第 个元素。

   由于 的不同幂次 代表了不同的尺度，可以看到 DeepWalk 已经隐式的建模了从尺度1 到尺度 K 的多尺度依赖关系，这表明DeepWalk 学到的表达能够捕获社交网络中的短距离依赖性和长距离依赖性。尽管如此，DeepWalk 捕获的多尺度representation 仍然有以下缺陷：

   • 无法保证representation 的多尺度：DeepWalk 不保证能够捕获多尺度的表达，因为 DeepWalk 的目标函数并没有明确的保留多个尺度。

     考虑一条长度为 的随机游走序列，从该序列获得的一阶关系顶点对有 个，从该序列获得的 阶关系顶点对有 对。因此DeepWalk 获得的 阶关系顶点对数量是一阶关系顶点对数量的 ，这使得DeepWalk 学到的表达倾向于捕获小尺度关系。

     如果下游任务需要网络的大尺度特征（如社交网络的用户年龄预测），这种小尺度倾向性是一个致命弱点。

   • 仅保留全局representation：DeepWalk 得到的是一个覆盖网络所有尺度的全局表达，因此无法访问不同尺度的表达。

     一个理想的representation 形式是：依次给出从小尺度到大尺度等各个不同尺度下的表达。这样下游的不同任务可以各自选择对自己最有利的尺度对应的表达来完成任务。

3. WALKLETS 扩展自DeepWalk ，但是显式的对多尺度依赖性进行建模。

   WALKLETS 也是基于截断的随机游走序列对网络进行建模，但是它对采样过程进行修改：在随机游走序列上跳过 个顶点来显式构建 阶关系。

   如下图所示：

   • 左图为DeepWalk 的采样过程：给定一条截断的随机游走序列，我们将所有的 阶关系顶点pair 对加入语料库来训练。

   • 右图为 WALKLETS 的采样过程：给定一条截断的随机游走序列，我们采样了 个语料库：

     • 语料库：所有一阶关系顶点pair 对加入该语料库。
     • 语料库：所有二阶关系（跳过一个顶点）顶点pair 对加入该语料库。
     • …
     • 语料库：所有 阶关系（跳过 个顶点）顶点pair 对加入该语料库。

     不同的语料库独立训练，分别得到不同尺度下的顶点表达。

     本质上第 个语料库的优化目标对应于矩阵 的矩阵分解。

   

4. WALKLETS 除了采样策略与DeepWalk 不同之外，优化方式、搜索策略都与 DeepWalk 相同。

   • WALKLETS 和 DeepWalk 都使用随机梯度下降 SGD 来优化目标函数。

   • WALKLETS 和 DeepWalk 通常应用于无权图，但是可以通过将梯度乘以边的权重从而扩展到加权图。也可以通过边采样 技术从而扩展到加权图。

   • WALKLETS 和 DeepWalk 都使用深度优先搜索策略。相比于宽度优先搜索，深度优先搜索可以编码更长距离的信息，从而能够学得更高阶的representation 。

     • 也可以引入node2vec 的有偏随机游走策略来扩展WALKLETS 。
     • 也可以直接计算 从而根据 阶转移概率矩阵来采样生成 阶顶点pair 对。但是这种方式只适合小型网络，因为大型网络计算 的算法复杂度太高。

7.2 实验

7.2.1 可视化

1. 数据集为 Cora 数据集，该数据集包含来自七个类别的 2708 篇机器学习论文。

   • 论文之间的链接代表引用关系，共有 5429个链接。

   • 从标题、摘要中生成短文本作为文档，并经过停用词处理、低频词处理（过滤文档词频低于 10个的单词），并将每个单词转化为 one-hot 向量。

     最终每篇文档映射为一个 1433 维的binary 向量，每一位为0/1 表示对应的单词是否存在。

2. 我们首先以顶点 作为源点，观察其它所有顶点和源点以representation 的 cosin 相似度作为距离的分布。

   可以看到：随着尺度的扩大（从 到 ），一个社区逐渐形成。这说明更大尺度的representation 可以更好的捕获网络的底层结构特征，从而有助于解决下游任务。

   

3. 我们在原始图（经过 t-SNE 二维可视化）中展示所有顶点到源点的距离热力图，距离越近颜色越红、距离越远颜色越蓝。

   这也显式了随着尺度的扩大，模型捕捉到一个较大社区的过程。

   

7.2.2 多标签分类

1. 数据集：

   • BlogCatalog：该数据集包含 BlogCatalog 网站上博客作者之间的社交关系，标签代表通过元数据推断出来的博客兴趣。网络包含 10312 个顶点、333983 条边、39 种不同标签。
   • DBLP Network：该数据集包含学者之间的论文合作关系。每个顶点代表一个作者，边代表一个作者对另一位作者的引用次数。网络包含 29199 个顶点、133664 条边、4 种不同标签。
   • Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。网络包含 80513 个顶点、58999882 条边、195 种不同标签。
   • YouTube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。网络包含 1138499 个顶点、2990443 条边、47 种不同标签。

2. 基准模型：

   • DeepWalk ：使用截断的随机游走序列来学习顶点的表达，学到的representation 捕获了多个尺度的社区成员关系的线性组合。

   • LINE：类似于 DeepWalk，但是这里我们仅仅考虑一阶邻近度，即只考虑 。

   • GraRep：通过显式的计算 并执行 SVD 分解来产生多个不同尺度的representation 。

     本质上该方法和 WALKLET 是类似的，但是它不是在线学习方法，且无法扩展到大规模网络。

3. 网络参数：

   • 我们使用随机梯度下降法求解最优化目标，并且使用 的 正则化，默认的初始化学习率为 0.025 。

   • 每个顶点的游走序列数量为 1000，每个序列的长度为 11，维度 为 128 。

   • 对于 WALKLETS 我们分别考虑尺度为 1,2,3 的 representation。

     同时我们也会考虑多个尺度表达的融合，此时我们分别将每个尺度的表达向量拼接起来，然后使用 PCA 降到 128 维。通过这种方式我们和其它方法进行可解释的比较。

4. 我们随机抽取 比例的标记样本作为训练集，剩下的顶点作为测试集，采用基于 one vs rest 的逻辑回归来执行多标签分类任务。

   每种情况随机重复执行十次，取平均的 MICRO-F1 作为评估指标。这里不报告准确率以及 MACRO-F1 得分，因为这些指标的趋势都相同。实验结果如下：

   • BlogCatalog 网络：使用 的 WALKLETS 超越了所有其它模型。

     

   • DBLP 网络：使用 的 WALKLETS 超越了除 GraRep 之外的所有其它模型。

     

   • Flickr网络：使用 的 WALKLETS 超越了所有其它模型。

     GraRep 无法处理该数据集，因为内存不足。

     

   • Youtube网络： 联合使用 的 WALKLETS 超越了所有其它模型。

     GraRep 无法处理该数据集，因为内存不足。

     

5. 这些实验表明：没有哪个固定尺度的表达能够胜任所有任务，因此我们需要针对不同任务选取最合适的尺度表达。

   作者推测这些分类任务表现出层次结构，而 WALKLETS 学到的不同尺度的表达可以充分利用网络的层次结构来匹配对应的任务。

6. 我们继续考察 WALKLETS 通过采样来逼近 的有效性。

   给定图 ，我们首先显式的计算 阶转移矩阵 ，然后通过WALKLETS 的随机游走过程来预估 ，并计算这两个矩阵的差异：

   

   我们在 DBLP,BlogCatalog 数据集上进行评估，游走参数如前所述。我们分别给出平均误差和标准差。

   可以看到在各种尺度下，误差的均值和标准差都很低，这表明通过随机游走序列能够得到转移矩阵的一个良好近似。并且通过增加随机游走序列的数量，这种误差会进一步降低。