Question

1. 社交网络本质上是分层hierarchical 的。例如，在人类社交网络中，每个人都是若干个社区 community 的成员，这些社区从小型（例如家庭、朋友）到中型（例如学校、企业）到大型（例如民族、国家）。随着这些关系的尺度 scale 发生变化，关系的拓扑结构也会发生变化。例如，考虑社交网络上某个大学的一名大学生（如下图所示）：

   • Friends 尺寸：他可能与朋友或直系亲属非常紧密地联系在一起，并与这些人（朋友或直系亲属）形成紧密的图结构。
   • Classmates 尺寸：然而，他与同一座大学内的其它学生的关系更加松散。事实上，他与大多数学生没有直接的社交关系。
   • Society 尺度：最后，他与本国其他人的联系相对较少，但是由于共同的文化，他仍将与本国其他人共享很多属性。

   尺度在预测任务中也起着重要作用，因为这些任务也从与特定的用户属性相关（如用户的电影兴趣）到与用户所属社区的、更通用的属性相关（如用户所属的学校）。

   在搜广推领域，尺度在刻画 user/item 特征上也是很重要的。

   

   大多数关于 network representation learning 的先前工作都使用 “一刀切” 的方法来处理这个问题，其中每个用户都使用单个 network representation 来进行预测，因此无法显式捕获节点在网络中具有的多尺度关 系multiscale relationship。在论文 《Don’t Walk, Skip! Online Learning of Multi-scale Network Embeddings》 的作者看来，最好有一组 representation 从而捕获用户的、所有尺度的社区成员关系。

   在论文 《Don’t Walk, Skip! Online Learning of Multi-scale Network Embeddings》 中，作者研究了大型图中 node embedding 问题，其中该 embedding 捕获了节点所属的所有社区的潜在层次结构 latent hierarchy 。这些潜在的 multiscale representation 对于社交网络中的预测任务很有用。在预测时，可以利用（单独的、或者组合的）representation 来提供更全面的、用户的隶属关系affiliation 。下面的左图和右图说明了不同尺度上 representation 相似性之间的差异。中心的红色顶点表示源点，顶点颜色代表该顶点和源点的距离：距离越近颜色越红，距离越远颜色越蓝。

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

   

   最近，人们对社交网络 representation learning 的兴趣激增，主要是基于神经矩阵分解 neural matrix factorization 。这些方法在半监督网络分类问题上展示了强大的任务性能。尽管它们在任务中的表现很强，但是作者发现这些方法还有很多不足之处。

   • 首先，最初的工作只是间接地解决了在多个尺度上学习 representation 的问题，或者作为学习过程的产物（《Deepwalk: Online learning of social representations》）、或者通过不同目标函数的不直观的组合（《Line: Largescale information network embedding》）。

     最近，《GraRep: Learning graph representations with global structural information》 提出了一种学习多尺度 representation 的方法，但是它的计算复杂度使得它对于大多数真实世界的图而言都难以处理。

   • 其次，这些方法中的大多数都依赖于network representation learning 的“一刀切”方法，它掩盖了图的每个单独尺度上存在的细微差别的信息。

   论文 《Don’t Walk, Skip! Online Learning of Multi-scale Network Embeddings》 提出了一种用于学习网络中顶点的、多尺度multiscale 的 representation 的新方法：WALKLETS 。这是一种用于学习社交 representation 的在线算法，它的 representation 以一种可推导derivable 的方式显式编码多尺度的顶点关系。与现有工作不同，WALKLETS 的维度具有意义，允许进行信息网络分类 informed network classification 以及被捕获关系的可视化。该方法本身是可扩展的，并且可以在具有数百万个顶点的图上运行。

   WALKLETS 通过在图的顶点上对短的随机游走short random walk 进行子采样subsampling 来生成这些多尺度关系multiscale relationship 。通过在每个随机游走中跳过某些 step ，论文的方法生成了一个由顶点pair 组成的语料库，其中这些顶点pair 可以通过固定长度的路径到达。然后可以使用该语料库来学习一系列潜在 representation，每个潜在 representation 都从邻接矩阵中捕获更高阶的关系。

   具体而言，论文的贡献如下：

   • 多尺度 representation learning：论文提出了一种 graph embedding 方法，它显式地捕获了多尺度关系 multiple scale relationship 。
   • 评估：论文在多个社交网络（如 BlogCatalog, DBLP, Flickr, YouTube, Arxiv ）上广泛评估WALKLETS 的 representation 在多标签分类任务上的表现。在 Micro-F1 指标上，WALKLETS 比 DeepWalk 等几个具有挑战性的 baseline 要高出多达 5% 。
   • 可视化和分析：WALKLETS 保留了潜在 representation 的多个尺度，作者用它来分析大型图中存在的多尺度效应 multiscale effect 。

   最后，WALKLETS 是一种在线算法，可以轻松扩展到具有数百万个顶点和边的 graph 。

2. 相关工作：相关工作分为三类：无监督 feature learning、多尺度 graph clustering、graph kernel 。

   • 无监督 feature learning：最近提出的社交 representation learning（DeepWalk, LINE, node2vec, Graph Likelihood ）使用 Word2Vec 提出的神经网络损失来学习 representation 从而编码顶点相似性 vertex similarity 。与我们的工作不同，这些方法没有显式保留网络中发生的多尺度效应。

     与我们最接近的相关工作 GraRep 是通过随机游走转移矩阵 random walk transition matrix 上的 SVD 来显式建模网络中的多尺度效应。我们的工作使用采样 sampling 和在线学习来操作更大规模的语料库。此外，我们的工作保留了多个尺度的 representation，这可以提供更好的任务性能的 modeling insight 。

     人们还提出了分布式 representation 来对不同领域的结构关系进行建模，如计算机视觉、语音识别、自然语言处理。

   • 多尺度社区检测：人们已经提出了很多用于检测图中多尺度离散社区的技术。一般而言，与我们的方法不同，这些方法试图返回一个描述图中社交层级结构的硬聚类 hard clustering 。

   • Graph Kernel：Graph Kernel 是一种方法，它使用关系数据作为分类程序的一部分，但是通常速度很慢。最近的工作已经应用神经网络来学习 graph kernel 的子图相似性subgraph similarity 。

7.1 模型

7.1.1 基础知识

1. 基本概念：定义网络 $ G=(V,E) $ ，其中 $ V=\{v_i\} $ 为网络的成员集合， $ E $ 表示成员之间的链接集合，其中 $ E\sube (V\times V) $ 。我们将 $ G $ 的邻接矩阵称作 $ \mathbf A\in \mathbb R^{|V|\times |V|} $ ，当且仅当存在边 $ (v_i,v_j)\in E $ 时，元素 $ A_{i,j} $ 是非零的。给定具有邻接矩阵 $ \mathbf A $ 的图 $ G $ ，我们将其在尺度 $ k $ 处的视图 view 定义为由 $ \mathbf A^k $ 定义的图。

   我们将 representation 定义为映射 $ \Phi: V\rightarrow \mathbb R^{|V|\times d} $ ，它将每个顶点 $ v\in V $ 映射到低维空间 $ \mathbb R^{d} $ 中的 $ d $ 维向量。在实践中，我们以参数矩阵 $ \mathbf X\in \mathbb R^{|V|\times d} $ 来表示映射 $ \Phi(\cdot) $ ，该矩阵通常从数据中估计。

   最后，令 $ G_L = (G,\mathbf X,\mathbf Y) $ 表示部分标记partially labeled 的社交网络，其中特征为 $ \mathbf X\in \mathbb R^{|V|\times d} $ ，标记为 $ \mathbf Y\in \mathbb R^{|V|\times |\mathcal Y|} $ ， $ d $ 为特征空间的维度， $ \mathcal Y $ 为标签集合。

2. 多尺度 Representation Learning：给定网络 $ G=(V,E) $ ，多尺度学习的目标是学习一组 $ k $ 个逐渐粗化 coarser 的社交 representation $ \mathbf X_1,\mathbf X_2,\cdots,\mathbf X_k $ ，其中 $ \mathbf X_k\in \mathbb R^{|V|\times d} $ 捕获了 $ G $ 在尺度 $ k $ 处的视图 view 。

   直观而言，每个 representation 都编码了不同视图的社交相似性 social similarity，对应于不同尺度的潜在社区的成员关系 membership 。

3. 预测性学习任务predictive learning task：给定一个 representation 或一组 representation $ \mathbf X $ ，任务的目标是学习将 $ \mathbf X $ 映射到标签集合label set $ \mathcal Y $ 的假设 hypothesis $ H(\cdot) $ 。这将允许泛化generalization ，即推断 $ G $ 中无标签顶点的标签。

4. Representation Learning：representation learning 的目标是学习一个映射函数 $ \Phi: V\rightarrow \mathbb R^{|V|\times d} $ ，它将图中每个顶点 $ v\in V $ 映射到相关的潜在社交 representation 。在实践中，我们用自由参数 free parameter 的矩阵 $ \mathbf X\in \mathbb R^{|V|\times d} $ 来表示映射 $ \Phi(\cdot) $ 。

   DeepWalk 引入了一个概念：将顶点建模为截断随机游走truncated random walk 中节点共现node co-occurrence 的函数。这些截断随机游走序列捕获了图中每个每个顶点周围的扩散过程 diffusion process，并对局部社区结构local community structure 进行了编码。因此，DeepWalk 的目标是估计顶点 $ v_i $ 与其局部邻域 local neighborhood 共现co-occurring 的可能性：

   $ \text{Pr}\left(v_i\mid \left(\Phi(v_1),\Phi(v_2),\cdots,\Phi(v_{i-1})\right)\right)=\text{Pr}\left(v_i\mid \left(\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_{i-1}\right)\right) $

   其中 $ \mathbf{\vec x} = \Phi(v) $ 为顶点 $ v $ 的 representation 。

   然而，随着随机游走序列长度的增加，计算这个条件概率变得不可行。为解决这个问题，人们提出通过忽略相邻顶点的顺序来放松relax 这个问题：不是使用上下文context 来预测目标顶点，而是使用目标顶点来预测其局部结构。就 vertex representation 建模而言，这得到了最优化问题：

   $ \min_{\mathbf X} = -\log \text{Pr}\left(\{v_{i-w},\cdots,v_{i+w}\}-\{v_i\}\mid \mathbf{\vec x}_i\right) $

   有趣的是，这个优化目标直接等价于学习邻接矩阵 $ \mathbf A $ 的低秩近似 low-rank approximation 。

5. 神经矩阵分解 Neural Matrix Factorization：一种常用的方法建模节点 $ v_i $ 和 $ v_j $ 共现的概率是，使用 softmax 将 pairwise similarity 映射到概率空间，即：

   $ \text{Pr}(v_j\mid v_i) = \frac{\exp\left(\mathbf{\vec x}_i\cdot \mathbf{\vec c}_j\right)}{\sum_{j^\prime\in V}\exp\left(\mathbf{\vec x}_i\cdot \mathbf{\vec c}_{j^\prime}\right)} $

   其中： $ \mathbf{\vec x}_i $ 为节点 $ v_i $ 的 input representation， $ \mathbf{\vec c}_j $ 为节点 $ v_j $ 的 output representation 。

   不幸的是，上式分母的计算量很大。为此，人们提出了噪声对比估计 noise-contrastive estimation: NCE 作为上式的松弛 relaxation 。NCE 将节点共现 pair $ (v_i,v_j) $ 的概率建模为：

   $ \text{Pr}((v_i,v_j)) = \sigma\left(\mathbf{\vec x}_i\cdot \mathbf{\vec c}_j\right) = \frac{1}{1 + \exp\left(-\mathbf{\vec x}_i\cdot \mathbf{\vec c}_j\right)} $

   可以看出，这两个概率模型都对应于隐式分解邻接矩阵的某种变换transformation。

   为了启发我们的方法，我们简要讨论一些矩阵，先前关于学习社交 representation 的工作就是隐式分解了这些矩阵。具体而言，我们讨论了我们最接近的相关工作 DeepWalk。如 《GraRep: Learning graph representations with global structural information》、《Comprehend deepwalk as matrix factorization》 所述，描述由 DeepWalk 执行的隐式矩阵分解的闭式解是可能的。他们推导出了一个带 Hierarchical Softmax 的 DeepWalk （DeepWalk with Hierarchical Softmax: DWHS） 公式，表明 DeepWalk 正在分解一个矩阵 $ \mathbf M $ ，该矩阵包含高达 $ t $ 阶的随机游走转移矩阵 random walk transition matrix 。换句话讲，元素 $ M_{i,j} $ 是从节点 $ v_i $ 到节点 $ v_j $ 的、长度不超过 $ t $ 的路径的数量的期望。

   注：这意味着邻接矩阵 $ \mathbf A $ 为 0-1 矩阵，即图 $ G $ 为无权图。

   $ M_{i,j} = \log \frac{\#(v_i,v_j)}{\#(v_i)} = \log \frac{\left[\mathbf{\vec e}_i \left(\mathbf A + \mathbf A^2 + \cdots+\mathbf A^t\right)\right]_j}{t} $

   其中：

   • $ \#(v_i,v_j) $ 是计数函数，它统计随机游走中 $ (v_i,v_j) $ 的共现次数； $ \#(v_i) $ 统计随机游走中 $ v_i $ 的出现次数。
   • $ \mathbf{\vec e}_i\in \mathbb R^{|V|} $ 为一个one-hot 的行向量，它的第 $ i $ 个元素为 1 、其它元素都为 0 。
   • $ []_j $ 表示选择向量的第 $ j $ 个元素。

7.1.2 多尺度神经矩阵分解

1. 这里我们介绍用于创建多尺度 network representation 的算法。我们首先描述我们用于捕获不同尺度的 representation 的模型。我们接着讨论一些重点，如搜索策略和优化optimization。最后，我们对一个小型的、真实世界的引文网络进行了案例研究，说明了通过我们方法捕获不同尺度的 network representation 。

2. 这里我们在Neural Matrix Factorization 的基础上，正式扩展了先前在社交 representation learning 中的方法，从而显式地建模现实世界网络中表现出的多尺度效应。

   如等式 $ M_{i,j} = \log \frac{\left[\mathbf{\vec e}_i \left(\mathbf A + \mathbf A^2 + \cdots+\mathbf A^k\right)\right]_j}{k} $ 所示，DeepWalk 隐式分解一个矩阵，该矩阵的元素包含 $ \mathbf A,\mathbf A^2, \cdots,\mathbf A^k $ ，其中 $ k $ 为随机游走的窗口大小。 $ \mathbf A $ 的每个幂次 $ \mathbf A^k $ 都代表不同尺度的网络结构。回想一下， $ A_{i,j}^k $ 表示节点 $ v_i $ 和 $ v_j $ 之间的、路径长度为 $ k $ 的路径数量。

   有趣的是，DeepWalk 已经隐式地对多尺度的依赖关系进行了建模。这表明学到的 representation 能够捕获社交网络中节点之间的短距离依赖关系和长距离依赖关系。尽管 DeepWalk 的表达能力足以捕获这些 representation，但是它的多尺度属性有局限性：

   • 不保证多尺度：多尺度 representation 不一定被 DeepWalk 捕获，因为多尺度没有被目标函数显式地保留。事实上，由于 DeepWalk 来自 $ \mathbf A $ 的条目 entry 总是比来自 $ \mathbf A^k $ （ $ k\gt 1 $ ）的条目更多，因此它倾向于保持最小尺度（即 $ \mathbf A $ 的最低幂次）的 representation 。为看清这一点，注意观察给定任何长度为 $ L $ 的随机游走序列，来自 $ \mathbf A $ 的条目数量最多为 $ L-1 $ ，而来自 $ \mathbf A^k $ 的条目最多为 $ (L-1)/k $ 。

     当大尺度（即高阶幂次）是网络上机器学习任务的适当 representation 时，这种小尺度bias 是一个根本性的弱点。例如，当对大尺度的图结构相关的特征进行分类时（例如，社交网络上的语言检测），与保留单个 edge 的、更细粒度的 representation 相比，更粗粒度的 representation 可以提供更好的性能。

   • 仅全局 representation：DeepWalk 学习了一种全局 representation，它融合了所有可能尺度的网络关系。因此，不同尺度的 representation 是不可能独立地访问的。这是不可取的，因为每个单独的学习任务都需要从全局 representation 中解码相关尺度的相似度信息similarity information 。实际上，社交关系的理想 representation 将跨越多个尺度，每个尺度依次捕获更大范围的潜在社区成员关系community membership 。然后，每个学习任务都能够利用最佳 level 的社交关系来完成该任务。正如我们将在实验部分中展示的那样，可以通过不同尺度的社交 representation 来最大化每个学习任务的性能。

     比如线性组合或者非线性组合多个尺度的 representation，从而最优化目标任务的性能。

3. 多尺度随机游走 WALKLETS：基于迄今为止讨论的观察结果，我们提出扩展 DeepWalk 引入的模型从而显式地建模多尺度依赖关系 multiscale dependency 。我们的方法通过分解邻接矩阵 $ \mathbf A $ 的幂来操作，使用最近提出的算法来学习 representation。

   与 DeepWalk 类似，我们通过从每个节点开始的一系列截断的随机游走 truncated random walk 从而对网络进行建模。正如 DeepWalk 中所讨论的，这些截断的随机游走中两个顶点的共现可以建模网络中的扩散速度diffusion rate 。然而，我们对采样程序进行了更关键的修改。具体而言，我们选择跳过随机游走中的一些节点。通过这种方式，我们形成了一组关系 relationship，这些关系是从 $ \mathbf A $ 的连续的、更高的幂次中采样到的。我们用 $ \text{WALKLETS}(\mathbf A^1,\cdots,\mathbf A^k) $ 来表示从邻接矩阵的幂次 $ \mathbf A^1,\cdots,\mathbf A^k $ 导出的 WALKLETS 。

   $ \mathbf A $ 的每个不同幂次都构成了一个语料库，这一系列 $ k $ 个语料库分别对网络中的特定距离依赖性specific distance dependency 进行建模。采样过程如下图所示，其中不同颜色代表不同的 $ k $ 值采样的edge （意味着原始图中距离为 $ k $ 的路径）。

   

   在根据尺度采样的关系进行分区之后，我们对观察样本顶点 $ v_i $ 和顶点 $ v_j $ 之间的概率进行建模。这意味着以下目标函数可以学习每个节点 $ v_i\in V $ 的 representation：

   $ \mathcal J = -\sum_{(v_i,v_j)\in \mathcal C_k} \log \text{Pr}(v_j\mid v_i) $

   其中 $ \mathcal C_k $ 为尺度 $ k $ 生成的随机游走 pair 构成的语料库。

   $ \mathcal J $ 寻求最大化 $ v_i $ 和上下文节点 $ v_j $ 共现的对数似然。这个目标通常称作 SkipGram，在 《Efficient estimation of word representations in vector space》 中首次被提出从而用于语言建模，并在 DeepWalk 中首次扩展到network representation learning 。

   • 损失函数优化：我们使用具有随机梯度下降的标准反向传播算法优化上述损失函数。除非另有说明，我们使用默认的学习率 0.025、默认的 embedding size $ d=128 $ 。

     这可以很容易地扩展到加权图（通过调整与权重成比例的梯度），边采样技术（在 LINE 中被提出）也可以适用于我们的方法。

   • 隐式矩阵分解的视角：通过以这种方式采样，我们可以表明我们学习了不同尺度的 representation。在 skipped random walk 上使用 DeepWalk，其中 skip factor 设置为 $ k $ （我们对彼此距离为 $ k $ 的节点进行采样），我们隐式地考虑了从 $ \mathbf A^k $ 派生的矩阵。

     WALKLETS 必须预先计算每个顶点 $ v $ 的、距离为 $ k $ 的顶点集合。论文的方法是：在常规的随机游走过程中，连续跳过 $ k $ 个随机游走。另一种简单的方法是计算 $ \mathbf A^k $ ，但是计算复杂度太高。

     观察到在 skip factor 为 $ k $ 的 skipped random walk 中，每个连续的 node pair $ v_i $ 和 $ v_{i+1} $ 都可以通过长度刚好为 $ k $ 的路径到达，因此它代表从 $ \mathbf A^k $ 采样的边。当我们为 DeepWalk 提供的随机游走中，当前后节点之间的距离为 $ k $ 时，在 $ M_{i,j} = \log \frac{\left[\mathbf{\vec e}_i \left(\mathbf A + \mathbf A^2 + \cdots+\mathbf A^k\right)\right]_j}{k} $ 中仅有 $ \mathbf A^k $ 对应的项存在。因此，我们隐式地分解从 $ \mathbf A^k $ 派生的矩阵。

   • 搜索策略：DeepWalk、LINE、node2vec 分别提出不同的搜索策略，从而根据图中的边生成不同的社交关系。广度优先策略从源节点依次扩展并检查其所有邻居，这对于局部邻居而言效果很好，但是随着更高 level 的扩展（即邻居的邻居）而面临状态空间爆炸state space explosion 。深度优先策略使用随机游走，它编码更远距离的信息，可能更适合学习更高阶的 network representation 。

     我们的方法通过随机游走采样random walk sampling 来观察多尺度关系，我们认为这将更具有可扩展性。值得一提的是，由于 node2vec 引入了一种有偏的随机游走方案，可以视为是对 DeepWalk 的扩展，我们的 skipping 算法也可以应用于 node2vec 生成的随机游走。

     另一种搜索策略（可能适用于较小的图）是直接计算 $ \mathbf A^k $ （即任何一对节点之间的路径距离为 $ k $ ），并使用它来采样节点 pair 。

4. 案例研究 Cora：为了说明 network representation 在多尺度上的影响，我们可视化了一个小的引用网络 Cora，它有 2708 个节点、5429 条边。下图展示了从特定节点（ $ v_{35} $ ） 到每个其它节点的社交 representation 的距离的直方图。当我们依次检查更深层的社交 representation 时，我们看到随着尺度的加大，越来越多的节点（如箭头标识）靠近 $ v_{35} $ 。这些节点是 $ v_{35} $ 所属的、更大的论文社区的一部分，具体而言是遗传算法领域。如果我们在 Cora 中进行分类任务，网络结构的这种清晰可分离clear separation 可以导致更容易的泛化。

   

   下图也说明了这种现象，该图展示了覆盖在原始网络结构上的、到节点 $ v_{35} $ （如箭头标识）距离的热力图（经过 t-SNE 二维可视化）。距离越近颜色越红、距离越远颜色越蓝。注意不同尺度的网络 representation 的距离如何编码连续的、更大社区的成员关系。

   

7.2 实验

1. 这里我们将我们的方法应用于几个在线社交网络，从而实验性地分析我们的方法。具体而言，我们的实验有两个主要目标：首先，我们试图描述不同现实世界社交网络中表现出的各种多尺度效应。其次，我们评估了我们的方法在捕获底层网络结构方面的效果。

2. 数据集：

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

3. 由于我们的方法以无监督的方式学习社交网络中节点的潜在 representation，因此这些 representation 通常应该作为各种学习任务的有用特征。因此，我们在社交网络的多标签分类multi-label classification 任务上评估我们的方法。这项任务的动机是：观察到网络中的节点隶属于多个社区成员。例如，社交网络中的人是多个圈子（家庭、学校、公司、共同爱好）的成员。对这些不同的社区成员进行建模和预测，不仅对于理解现实世界的网络至关重要，而且还有几个重要的商业应用（例如更有效的广告 targeting ）。

4. baseline 方法：我们考虑三个最近提出的、代表 state-of-the-art 的社交 representation learning 模型。

   • DeepWalk：该方法使用截断的随机游走序列来学习顶点的representation ，学到的representation 捕获了多尺度社区成员关系的线性组合。
   • LINE：类似于 DeepWalk，该方法使用 SkipGram 目标函数学习节点 representation。但是这里我们仅仅 LINE 1st 方法，它只考虑 $ \mathbf A^1 $ 。
   • GraRep：该方法通过显式的计算 $ \mathbf A^1,\cdots,\mathbf A^k $ 并执行 SVD 分解来产生多尺度的representation 。本质上该方法和 WALKLET 是类似的，但是它不是在线学习方法，且无法扩展到大型网络。

5. 任务配置：我们使用 DeepWalk 中描述的相同实验程序来评估我们的方法。我们随机抽取标记节点的 $ T_f $ 比例，并将它们作为训练数据，剩余部分作为测试数据。这个过程重复 10 次，然后报告平均 MICRO-F1 得分。我们不包括其它评估指标（如准确率和 MACRO-F1 ）的结果，因为这些指标都遵循相同的趋势。这使得我们能够轻松地将我们的方法和其它相关 baseline 进行比较。

   在所有情况下，我们都会学习一个逻辑回归分类模型（基于 one vs rest 策略）。我们使用 $ C=1 $ 的默认 L2 正则化系数，并使用由 Liblinear 实现的优化算法。

   • 对于 WALKLETS ，我们仅使用尺度为 {1, 2, 3} 的随机游走生成的 representation。

   • 在所有情况下，每个节点开始的随机游走数量为 1000，每条随机游走序列的长度为 11 。在所有情况下， embedding size 为 $ d=128 $ 。这些设置也用于 baseline 。

   • 在多尺度 representation 的情况下，我们拼接所有多个尺度的特征并使用 PCA 将它们投影到 128 维。

     PCA 本质上是线性映射，因此这里是将多尺度 representation 进行线性组合。

   通过这些方法，我们可以控制训练数据大小的差异、以及超参数的差异，这些超参数控制了 representation 的容量 capacity 。这允许我们与其它方法和 baseline 进行可解释的比较。

6. 实验结果：下表显示了我们算法的性能相对于其它两种 baseline （即 DeepWalk 和 LINE ）的增益。我们没有比较 GraRep，因为它不是在线算法，也无法扩展到大型图（如 Flickr 和 Youtube ）。

   • BlogCatalog：下表显示了 BlogCatalog 上多标签分类的结果。我们观察到使用 $ \mathbf A^2 $ 特征的 WALKLETS 在 Micro-F1 上优于所有 baseline。当标记数据稀疏时（仅 10% 的节点被标记），Micro-F1 的差异在 0.001 水平上具有统计意义（比 DeepWalk 提升 8.9%，比 LINE 提升 58.4%）。我们在 10 次不同运行上使用 paired t-test 来得到统计显著性 statistical significance 。

     

   • DBLP：DBLP 的实验结果如下表所示。我们注意到，与 DeepWalk 和 LINE 相比， $ \mathbf A^3 $ 的 representation 在 Micro-F1 上提供了统计上的显著提升。在标记节点为 1% 的情况下，WALKLETS （ $ \mathbf A^3 $ ） 相对于 DeepWalk 和 LINE 的增益分别为 10.1% 和 34.3%。这些更粗的 representation 为作者发表的主题领域提供了更好的编码。

     然而，我们注意到，在这项任务中 WALKLETS 未能超越 GraRep 学到的多尺度 representation 。我们将此归因于 DBLP 表现良好的事实。

     • 首先，它表现出高度同质化的行为，因为 co-authorship 保证了相似的属性（两位作者之间的共同出版物必须在同一个研究领域）。
     • 其次，图中的 co-authorship 边表明高度相似性（更难创建虚假的边）。

     当这些条件成立时，GraRep 对随机游走转移矩阵的直接计算可以产生很高的性能增益。然而，我们注意到 GraRep 的技术需要处理一个稠密矩阵，这本质上是不可扩展 unscalable 的。

     

   • Flickr：下表显示了 Flickr 数据集的结果。在这个数据集上，我们看到 $ \mathbf A^2 $ 派生的特征在 Micro-F1 指标上提供了最佳性能，显著优于所有 baseline。具体而言，我们观察到，当只有 1% 数据被标记为训练数据时，WALKLETS 在 Micro-F1 分数上比 DeepWalk 高 4.1%、比 LINE 高 29.6% 。

     我们注意到，最具竞争力的 baseline GraRep 由于内存不足而无法在该数据集（仅 80513 个顶点）上运行。相反，我们的方法可以轻易地处理如此大型的网络，同时产生有竞争力的结果。

     

   • YouTube：YouTube 的结果如下表所示。再一次地，我们的方法优于所有 baseline 方法。有趣的是，组合的 representation $ \text{WALKLETS}(\mathbf A^2, \mathbf A^3) $ 提供了最佳性能，在 p=0.05 水平上显著优于 DeepWalk 和 LINE。

     YouTube 包含更多的顶点，因此 GraRep 再次耗尽内存也就不足为奇了。我们注意到 WALKLETS 的在线设置允许学习具有数百万个顶点的图的 representation 。

     

7. 分类任务中的多尺度效应：前面的实验结果表明，没有哪个单一尺度的 representation 在所有任务上都取得最佳性能。我们可以显式地提供各尺度的 representation ，从而解决其它 baseline 方法未能在多个尺度上显式编码信息的共同限制。

   在 Micro-F1 指标上， $ \mathbf A^2 $ 的特征在两个图（BlogCatalog, Flickr ）上的所有训练数据变体（包括不同训练集比例）中表现最好。这表明长度为 2 的路径是合适的社交依赖性，从而建模共享的用户兴趣。在 $ \mathbf A^2 $ 中捕获的 neighbor-of-neighbor 信息对于处理缺失信息missing information 的网络而言特别有用。发生这种情况的一个重要 case 是冷启动问题，其中一个节点刚刚加入网络并且还没有机会进行所有的连接。

   有趣的是，从 $ \mathbf A^3 $ 和 $ (\mathbf A^2, \mathbf A^3) $ 派生的 representation 分别在 DBLP 和 YouTube 上提供了最佳的任务性能。在这些图上，分类性能随着representation 尺度的增加而单调增加。我们可以推测：这些图中的分类任务确实表现出层次结构 hierarchical structure ，并且通过我们的方法创建的 、distinct 的高阶 representation 允许利用图的层次结构和任务标签之间的相关性。

   我们在此强调：WALKLETS 显式地对社交网络中存在的多尺度效应进行建模，从而能够全面分析哪些尺度能够对给定学习任务提供最多的信息。而这是其它的一些方法无法实现的，例如 DeepWalk 和 LINE 使用全局的 representation。

   GraRep 也能够分析各个尺度，但是它无法扩展到大型图。

8. 可扩展性：WALKLETS 是一种在线算法，它对从图中以不同依赖性水平 dependency level 采样的顶点进行操作。这种在线方法使用采样 sampling 来逼近高阶的转移矩阵 ransition matrix ，这允许扩展到具有数百万个顶点的大型图。这和最接近的相关方法 GraRep 形成鲜明对比， GraRep 需要操作稠密矩阵（如果图是连通的并且 edge 分布遵从幂律分布，那么随着 $ k $ 的增加， $ \mathbf A^k $ 会迅速失去稀疏性）。GraRep 需要计算转移矩阵的连续幂，并且进一步需要显式计算 SVD，这些都无法扩展到大型网络。

9. 采样分析：这里我们通过将我们的方法和 GraRep 进行的显式和精确计算进行比较，从而分析我们提出的随机游走采样程序的有效性。给定一个图 $ G $ ，我们使用 GraRep 显式计算它分解的矩阵 $ \mathbf M_{\text{GR}} $ 。然后，我们使用 WALKLETS 用到的随机游走来估计 WALKLETS 要分解的矩阵 $ \mathbf M_\text{W} $ 。我们通过 $ \text{Err} = \text{abs}(\mathbf M_{\text{GR}} - \mathbf M_{\text{W}}) $ 来估计我们的近似值和精确值之间的接近程度。随机游走的超参数如前所述。

   我们在 DBLP 和 BlogCatlog 数据集上评估了 Err 的平均误差，结果表明：两个图上的多尺度随机游走足以逼近显式计算的转移矩阵。我们观察到我们的近似值在各个尺度上的平均误差和标准差都很低，这表明我们的方法捕获了随机游走转移矩阵的合理近似值。增加 sample size （通过增加更多的随机游走）将导致越来越好的近似值。