Question

1. network embedding （也称作 graph embedding ）使用稠密向量来表达节点，并且已被很好地研究了多年。最近，受循环神经网络 RNN 的启发，人们基于图上的随机游走和随机梯度下降优化从而对 network embedding 进行了重新研究和开发，并可以应用于非常大的图。节点的 embedding 向量可用于编码网络的一些拓扑结构，然后可以作为下游模型的特征。network embedding 已被证明有助于网络分析任务，包括链接预测、节点分类、社区检测。

   有些网络呈现多重性multiplexity 的特点，尤其是对于社交网络。在社交网络分析中，多重性是指两个人之间的多方面关系。如果我们把这个思想推广到各种网络，多重网络 multiplex network 是指网络中包含多种类型的关系，其中每一种关系都可以构成网络的一个子网（也称作一层 layer 或子图）。以社交网络为例。在 Facebook 等社交网络中，用户之间存在不同类型的交互，如好友关系、转发文章关系、聊天关系、转账关系。每种关系都将在所有用户之间创建一个子网。如果我们将所有关系视为一个统一的整体，那么我们将得到一个巨大的多重网络。虽然网络的每个子网仅能代表用户之间的一种交互，但是为了更好地理解多重网络整体，最好把来自这些子网的不同类型的信息集成在一起，而不牺牲各种类型信息的特有属性。

   考虑到网络可能很大的事实，在论文《Scalable Multiplex Network Embedding》中，作者提出了一种可扩展的多重网络embedding 模型，从而有效地将多类型关系multi-type relation 的信息存储和学习到统一的 embedding 空间中。

   • 对于每个节点，论文提出一个高维的 common embedding 向量，该向量在多重网络的所有子网中共享。论文通过 common embedding 向量在网络的不同子网之间建立桥梁。
   • 对于每个节点，为了在不同子网上以较低内存需求的方式学习各子网的独有属性，论文还为每种类型的关系提出了一个低维的 additional embedding 。

   论文的贡献仅仅是这一个点，总体而言没有什么大的创新点，不够深入，一篇“水文”。

   为了将这些不同维度（有高维的、有低维的）的 embedding 对齐，论文为网络的每个子网引入了一个全局变换矩阵global transformation matrix 。遵从 DeepWalk，论文使用随机梯度下降来优化所提出的模型。由于全局变换矩阵的更新次数要比节点向量的更新次数多得多，因此论文添加了一个额外的正则化项来约束全局变换矩阵的范数。

   总而言之，本文贡献如下：

   • 论文正式定义了多重网络 embedding 问题，以及处理网络的多重属性 multiplexity property 。
   • 论文提出了一种可扩展的多重网络 embedding 模型，该模型将来自多类型关系multi-type relation 的信息表达到统一的 embedding 空间中。
   • 论文在链接预测、节点分类这两个网络分析任务上评估了所提出的 embedding 算法。和当前的 state-of-the-art 模型相比，所提出的模型实现了更好或相当的性能，并且内存占用更少。

2. 相关工作：

   • 多重网络分析：传统上，在社会科学中，多重性multiplexity 被用于描述用户之间社交关系的多个方面。多重性的思想可以推广到各种网络。在数据挖掘社区中，人们有时也使用 “多关系网络” multi-relational network 这个术语来表达社交网络中的多类型关系multi-type relation ，并验证在社交网络中考虑多类型关系可以帮助进行社区挖掘或链接预测等数据挖掘任务。此外，在生物信息学社区中，人们已经表明通过集成多个网络，可以改善 node representation 从而帮助基因功能分析。

     如今，多重网络上的图挖掘方法主要针对特定任务。对于链接预测，可以将传统方法应用于多重网络，而无需考虑边的类型信息。对于社区检测，《A degree centrality in multi-layered social network》 提出了跨子网的中心度centrality 度量从而捕获多重网络中节点的中心度。除此之外，人们还提出了多子网局部聚类系数 multilayered local clustering coefficient: MLCC 和跨子网聚类系数 cross-layer clustering coefficient: CLCC 来描述多重网络中节点的聚类系数。

     在本文中，我们从 network embedding 的角度提出了多重网络分析的通用解决方案。

   • network embedding：network embedding（也称作graph embedding）已被很好地研究了很多年。network embedding 也与流形学习manifold learning 有关，而流形学习通常应用于高维数据的降维。network embedding 侧重于为真实网络生成节点的向量representation ，从而促进对网络的进一步分析。传统的 network embedding 方法通常涉及耗时的计算，例如用于分析图的谱属性 spectral property 的特征值分解 eigenvalue decomposition 。然而，由于真实世界的网络规模可能很大，这类方法算法复杂度太高从而不可行。

     最近，受到循环神经网络 RNN 发展的启发，尤其是高效的 word embedding 方法，人们已经提出了许多 network embedding 方法来处理大型社交网络。例如，DeepWalk 提出在网络上执行随机游走从而生成节点序列，然后对这些序列执行 SkipGram 算法从而生成节点 embedding。在 DeepWalk 之上，Node2Vec 增加了两个超参数来控制随机游走过程从而实现有偏biased 的随机游走。其它的一些 embedding 模型专注于网络中特定类型的结构。例如，LINE 尝试使用 embedding 来逼近网络的一阶邻近性和二阶邻近性。

     上述所有模型都已被证明对单一网络single network 的分析有用，但它们都没有考虑多重性。最近，《Principled multilayer network embedding》 提出了三种方法来从多重网络中学习一个整体 embedding 。与该方法不同，我们提出一个高维的 common embedding、以及每种类型的关系一个低维的 additional embedding 。最近的一项工作 《Multi-layered network embedding》 本质上是一个异质的信息网络，因为在该论文中，不同的子网有不同类型的节点。

27.1 模型

1. 给定多重网络 multiplex network$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G=(\mathcal V, \mathcal E) $ ，其中$\mathcal{V}=\{v_1,v_2,\cdots ,v_n\}$$ \mathcal V=\{v_1,v_2,\cdots,v_n\} $ 。假设网络有$M$$ M $ 种不同的关系类型，对应的边集合为${\mathcal{E}}_1,{\mathcal{E}}_2,\cdots ,{\mathcal{E}}_M$$ \mathcal E_1,\mathcal E_2,\cdots,\mathcal E_M $ ，其中${\mathcal{E}}_m\subset \mathcal{E},\bigcup _{m=1}^M{\mathcal{E}}_m=\mathcal{E}$$ \mathcal E_m\sub \mathcal E,\quad \bigcup_{m=1}^M \mathcal E_m = \mathcal E $ 。定义类型为$m$$ m $ 的子网为${\mathcal{G}}_m(\mathcal{V},{\mathcal{E}}_m)$$ \mathcal G_m(\mathcal V,\mathcal E_m) $ 。

   对于每个节点$v_i\in \mathcal{V}$$ v_i\in \mathcal V $ ，我们有一个 common embedding 向量${\overrightarrow{\mathbf{b}}}_i\in {\mathbb{R}}^d$$ \mathbf{\vec b}_i\in \mathbb R^d $ ，它在所有关系类型之间共享。我们使用 common embedding 向量作为跨不同关系类型传输信息的桥梁。

   为捕获不同关系类型的特点，对于每个节点我们在每个子网${\mathcal{G}}_m$$ \mathcal G_m $ 上还有一个 additional embedding 向量${\overrightarrow{\mathbf{u}}}_i^{(m)}\in {\mathbb{R}}^s$$ \mathbf{\vec u}_i^{(m)} \in \mathbb R^s $ 。为了防止模型整体太大，我们选择$s\ll d\ll n$$ s\ll d\ll n $ 。

   为了将 additional embedding 空间映射到 common embedding 空间，我们引入变换矩阵${\mathbf{X}}^{(m)}\in {\mathbb{R}}^{s\times d}$$ \mathbf X^{(m)}\in \mathbb R^{s\times d} $ 。最终我们定义节点$v_i$$ v_i $ 在子网${\mathcal{G}}_m$$ \mathcal G_m $ 下的 embedding 向量为：

   $${\overrightarrow{\mathbf{v}}}_i^{(m)}={\overrightarrow{\mathbf{b}}}_i+w^{(m)}\times {\mathbf{X}}^{(m{)}^{\mathrm{\top }}}{\overrightarrow{\mathbf{u}}}_i^{(m)}$$

   其中$w^{(m)}$$ w^{(m)} $ 为超参数，表示关系类型$m$$ m $ 的全局重要性。

   这里变换矩阵是节点无关的，它在所有节点$\mathcal{V}$$ \mathcal V $ 上共享。 超参数$w^{(m)}$$ w^{(m)} $ 也可以通过模型从数据中学到。

2. 对于多重网络$\mathcal{G}$$ \mathcal G $ 中的关系类型$m$$ m $ ，我们对${\mathcal{G}}_m$$ \mathcal G_m $ 进行随机游走从而生成节点序列，然后对这些节点序列执行 SkipGram 算法学习 node embedding 。

   对于${\mathcal{G}}_m$$ \mathcal G_m $ 中的随机游走序列，假设节点$v_i$$ v_i $ 在大小为$c$$ c $ 的上下文窗口中的邻居节点集合为${\mathcal{N}}_{v_i}^{(m)}$$ \mathcal N^{(m)}_{v_i} $ ，则SkipGram 的目标函数为：

   $$-\log P^{(m)}({\mathcal{N}}_{v_i}^{(m)}\mid v_i)=-\log \prod _{v_j\in {\mathcal{N}}_{v_i}^{(m)}}\log p^{(m)}(v_j\mid v_i)$$

   我们定义$p^{(m)}(\cdot \mid \cdot )$$ p^{(m)}(\cdot\mid \cdot) $ 为：

   $$p^{(m)}(v_j\mid v_i)=\frac{\exp ({\overrightarrow{\mathbf{c}}}_j\cdot {\overrightarrow{\mathbf{v}}}_i^{(m)})}{\sum _{j^{\prime }\in \mathcal{G}}\exp ({\overrightarrow{\mathbf{c}}}_{j^{\prime }}\cdot {\overrightarrow{\mathbf{v}}}_i^{(m)})}$$

   其中：

   • ${\overrightarrow{\mathbf{v}}}_i^{(m)}$$ \mathbf{\vec v}_i^{(m)} $ 为节点$v_i$$ v_i $ 在${\mathcal{G}}_m$$ \mathcal G_m $ 下的 embedding 。

   • ${\overrightarrow{\mathbf{c}}}_j\in {\mathbb{R}}^d$$ \mathbf{\vec c}_j\in \mathbb R^d $ 为节点$v_j$$ v_j $ 的 context embedding，它在所有子网中共享。

     不仅 common embedding 向量${\overrightarrow{\mathbf{b}}}_i$$ \mathbf{\vec b}_i $ 是跨不同关系类型传输信息的桥梁，context embedding${\overrightarrow{\mathbf{c}}}_j$$ \mathbf{\vec c}_j $ 也是跨不同关系类型传输信息的桥梁，因为它们都是跨子网共享的。

     此外，假设两个节点在不同子网中共享相同的邻域节点，那么这两个节点之间是相似的，即使它们位于不同的子网。这确保了相似性的跨子网的一致性。

   为加速训练，我们采用负采样技术：

   $$\mathcal{L}=-\log \sigma ({\overrightarrow{\mathbf{c}}}_j\cdot {\overrightarrow{\mathbf{v}}}_i^{(m)})-\sum _{k=1}^K{\mathbb{E}}_{j^{\prime }\sim Q_n^{(m)}(v)}\log \sigma (-{\overrightarrow{\mathbf{c}}}_{j^{\prime }}\cdot {\overrightarrow{\mathbf{v}}}_i^{(m)})$$

   其中：$K$$ K $ 为负采样比例，$Q_n^{(m)}(v)$$ Q_n^{(m)}(v) $ 为子网${\mathcal{G}}_m$$ \mathcal G_m $ 的负采样分布，$\sigma (\cdot )$$ \sigma(\cdot) $ 为 logistic 函数。

   我们根据随机梯度下降SGD 来优化该目标函数。我们初始化所有的${\overrightarrow{\mathbf{b}}}_i,{\overrightarrow{\mathbf{u}}}_i^{(m)}$$ \mathbf{\vec b}_i,\mathbf{\vec u}_i^{(m)} $ 为零向量，${\mathbf{X}}^{(m)}$$ \mathbf X^{(m)} $ 为零矩阵，但是我们随机初始化上下文向量${\overrightarrow{\mathbf{c}}}_j$$ \mathbf{\vec c}_j $ 。

   由于子网${\mathcal{G}}_m$$ \mathcal G_m $ 中，每一个节点都会更新参数${\mathbf{X}}^{(m)}$$ \mathbf X^{(m)} $ ，因此${\mathbf{X}}^{(m)}$$ \mathbf X^{(m)} $ 被更新的次数非常多。为防止${\mathbf{X}}^{(m)}$$ \mathbf X^{(m)} $ 的范数太大，我们添加约束：$\Vert {\mathbf{X}}^{(m)}\Vert \le r$$ \left\|\mathbf X^{(m)} \right\| \le r $ ，其中$r$$ r $ 为超参数。

3. MNE 算法：

   • 输入：

     • 多重网络$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G=(\mathcal V,\mathcal E) $ ，其中包含$M$$ M $ 种不同的关系类型${\mathcal{E}}_1,{\mathcal{E}}_2,\cdots ,{\mathcal{E}}_M$$ \mathcal E_1,\mathcal E_2,\cdots,\mathcal E_M $
     • common embedding 维度$d$$ d $
     • additional embedding 维度$s$$ s $
     • 学习率$\eta$$ \eta $
     • 随机游走序列长度$l$$ l $
     • 从每个顶点开始的随机游走序列数量$n_{walk}$$ n_{walk} $
     • 上下文窗口大小$c$$ c $
     • 负采样比例$K$$ K $
     • 转换矩阵的正则化参数$r$$ r $
     • 关系类型的全局重要性${\left\{w^{(m)}\right\}}_{m=1}^M$$ \left\{w^{(m)}\right\}_{m=1}^M $

   • 输出：每个节点$v_i$$ v_i $ 在每个子网${\mathcal{G}}_m$$ \mathcal G_m $ 下的 embedding${\left\{{\overrightarrow{\mathbf{v}}}_i^{(m)}\right\}}_{i=1,\cdots ,n}^{m=1,\cdots ,M}$$ \left\{\mathbf{\vec v}_i^{(m)} \right\}_{i=1,\cdots,n}^{m=1,\cdots,M} $

   • 算法步骤：

     • 初始化${\overrightarrow{\mathbf{b}}}_i,{\overrightarrow{\mathbf{u}}}_i^{(m)},{\mathbf{X}}^{(m)}$$ \mathbf{\vec b}_i,\mathbf{\vec u}_i^{(m)},\mathbf X^{(m)} $ 为零，随机初始化${\overrightarrow{\mathbf{c}}}_j$$ \mathbf{\vec c}_j $ 。

     • 对每子网${\mathcal{G}}_m$$ \mathcal G_m $ 进行迭代：

       生成随机游走序列集合$\{{\text{Path}}_1^{(m)},{\text{Path}}_2^{(m)},\cdots ,\}$$ \left\{\text{Path}_1^{(m)},\text{Path}_2^{(m)},\cdots,\right\} $ 。其中对于每条随机游走序列${\text{Path}}^{(m)}$$ \text{Path}^{(m)} $ ：

       对于每个节点$v_i\in {\text{Path}}^{(m)}$$ v_i\in \text{Path}^{(m)} $ ：

       • 对于节点$v_i$$ v_i $ 上下文窗口内的每个上下文$v_j$$ v_j $ ：

         • 随机采样$K$$ K $ 个负样本。

         • 计算${\overrightarrow{\mathbf{v}}}_i^{(m)}={\overrightarrow{\mathbf{b}}}_i+w^{(m)}\times {\mathbf{X}}^{(m{)}^{\mathrm{\top }}}{\overrightarrow{\mathbf{u}}}_i^{(m)}$$ \mathbf{\vec v}_i^{(m)} = \mathbf{\vec b}_i + w^{(m)}\times \mathbf X^{(m)^\top} \mathbf{\vec u}_i^{(m)} $ 。

         • 对正样本$v_j$$ v_j $ 和$K$$ K $ 个负样本，通过梯度更新参数${\overrightarrow{\mathbf{b}}}_i,\{{\overrightarrow{\mathbf{c}}}_k{\}}_{k=1}^K,{\overrightarrow{\mathbf{u}}}_i^{(m)},{\mathbf{X}}^{(m)}$$ \mathbf{\vec b}_i, \{\mathbf{\vec c}_k\}_{k=1}^K, \mathbf{\vec u}_i^{(m)},\mathbf X^{(m)} $ 。

         • 如果$\Vert {\mathbf{X}}^{(m)}\Vert >r$$ \left\|\mathbf X^{(m)}\right\|\gt r $ ，则进行截断：

           $${\mathbf{X}}^{(m)}\leftarrow \frac{r}{\Vert {\mathbf{X}}^{(m)}\Vert }{\mathbf{X}}^{(m)}$$

     • 最终输出每个节点$v_i$$ v_i $ 在每子网${\mathcal{G}}_m$$ \mathcal G_m $ 下的 embedding${\left\{{\overrightarrow{\mathbf{v}}}_i^{(m)}\right\}}_{i=1,\cdots ,n}^{m=1,\cdots ,M}$$ \left\{\mathbf{\vec v}_i^{(m)} \right\}_{i=1,\cdots,n}^{m=1,\cdots,M} $ 。

4. 我们的算法基于随机游走策略。假设有$M$$ M $ 种关系类型$n$$ n $ 个节点，则我们的时间复杂度为$O(M\times n)$$ O(M\times n) $ ，空间复杂度为$O((d+s\times M)\times n)$$ O((d+s\times M)\times n) $ 。

27.2 实验

1. 数据集：

   我们选择了Manlio De Domenico 项目公开的四个多重网络，选择标准是：节点数量不能太少，且边不能太稀疏。这意味着每种关系类型的每个节点至少具有一条边。

   • Vickers：对澳大利亚维多利亚州一所学校初一年级29 名学生问卷调查得到的数据。问卷调查分三个问题，每个问题创建了网络中的一种关系。
   • CKM：由伊利诺伊州、布卢明顿市、昆西市、加勒斯堡市四个镇的医师收集的数据。医师们提出了三个问题，每个问题都创建了网络中的一种关系。
   • LAZEGA：多重社交网络，包含企业中的三种关系（工友co-work 、好友、咨询 advice ）。
   • C.ELEGANS：神经元多重网络，神经元不同的突触连接创建了网络中的不同关系。连接类型包括： ElectrJ、MonoSyn、PolySyn 。

   另外，由于上述多重网络的规模相对较小，为了测试我们模型的可扩展性和效果，我们还选择了两个真实的大型社交网络。

   • Twitter：包含一周内关于“希格斯玻色子发现”的所有推文。我们选择最大的两种关系（跟帖following 和转发 retweet ）来构建多重网络。

   • Private：一个在线社交网络。在该网络中，用户可以建立好友关系并将自己的文章发送给好友。我们随机选择 40000 名用户，这些用户都有毕业大学的信息，然后我们记录了这些用户一个月内所有文章的转发活动。

     我们在文章内容上应用了主题模型topic model，然后将文章根据主题来分类。最终我们得到了 16 个主题，每个主题都创建了多重关系网络中的一种关系。如果再加上好友关系，则一共有 17 种关系。

   

2. baseline 方法：

   • DeepWalk：通过随机游走策略构建节点序列，然后在节点序列上应用 SkipGram 算法来生成 node embedding 。
   • LINE：保持图的一阶邻近度和二阶邻近度从而得到 node embedding 。
   • Node2vec：基于有偏的随机游走得到节点序列，然后在节点序列上应用 SkipGram 算法来生成 node embedding 。
   • PMNE：提出三种不同的模型将多重网络聚合，并为每个节点点生成一个 overall embedding。这三种模型分别为 PMNE(n)、PMNE(r)、PMNE(c) 。

   除了 embedding based 之外，我们还比较了 structure based 方法，包括：

   • Common neighbor:CN：每对节点pair 对，它们的公共邻居节点越多，则存在链接的可能性越大。
   • Jaccard Coefficient:JC：每对节点pair 对，使用它们的邻居总数对公共邻居数量进行归一化。
   • Adamic/Adar:AA：类似于 JC，但是 AA 给那些邻居更少的节点更大的权重。

3. 评估指标：

   • 对于链接预测任务，我们使用 ROC-AUC 作为评估指标。
   • 对于节点分类任务，我们对学到的 embedding 采用$L_2$$ L_2 $ 正则化的逻辑回归分类器训练并分类，并评估分类的准确率 accuracy 。

4. 参数配置：

   • 所有 embedding 方法的 embedding 维度为 200 。

     由于 LINE 有一阶embedding 和二阶 embedding，因此它们的维度都是 100，最终拼接后的维度是 200 。

   • 对于所有基于随机游走的方法，我们将上下文窗口设为 10，负采样比例为 5 。

   • 对于 node2vec，我们根据实验使用最佳超参数，即$p=2,q=0.5$$ p=2,q=0.5 $ 。

   • 对于 PMNE 模型，我们使用原始论文给出的超参数。

   • 对于 MNE，我们将additional embedding 的维度设为$s=10$$ s=10 $ 。

5. 链接预测任务：对每对节点我们计算其 embedding 的余弦相似度，相似度越大则它们之间越可能存在链接。

   • 对于简单网络模型（如 DeepWalk,LINE,Node2Vec），我们将为每个子网训练一个单独的 embedding，并使用该 embedding 来预估对应关系上的链接。这意味着这些embedding 没有来自网络其它类型的信息。
   • 对于多重网络模型，我们得到的 node embedding 可以融合网络其它类型的信息。

   我们在网络的每个子网上计算 AUC，并取所有子网的 AUC 均值作为最终结果。我们使用五折交叉验证，并报告了结果的均值和标准差。

   注意：Twitter 和 Private 数据集中，following 关系和 friendship 关系是其它关系类型的基础。如，我们只能将文章发送给好友。因此在选择子网负边时，我们需要确保选择的是满足基础关系（如 following/friendship 关系）的负边。并且我们不会评估基础网络（即 following/friendship 网络）。

   结论：

   • 对于几乎所有网络，联合考虑网络的不同关系类型都是有帮助的。这与我们假设一致，即来自任何单个子网的信息不足，并且不同子网的信息可以互补。
   • baseline 方法的性能因为不同网络拓扑结构差异很大。如 LAZEGA 或 C.ELEGANS 这样的稠密网络，传统简单方法的性能就足够好，有时甚至比 embedding 方法还要好。但是当网络相对稀疏时，embedding based 方法更好。
   • 我们的方法和 PMNE 区别在于：PMNE 为一个节点生成一个 overall embedding，而我们的方法生成一组 embedding 用于捕获每种关系类型的不同信息。实验结果表明，这些信息可能非常重要。

   总而言之，我们的方法稳定地超越了其它所有 baseline，或达到 baseline 相当的性能。我们的理解是：模型的 common embedding 会合并来自不同关系类型的信息，而additional embedding 会保留每种关系类型特有的信息。

   

6. 参数敏感性：我们的方法有三个超参数：低维 additional embedding 的维度$s$$ s $ 、低维addtional embedding 的权重${\left\{w^{(m)}\right\}}_{m=1}^M$$ \left\{w^{(m)}\right\}_{m=1}^M $ 、变换矩阵范数上限$r$$ r $ 。为清楚地了解这些超参数的影响，我们使用不同的配置重复进行连接预测实验。对于四个小数据集，我们取其评估结果的均值来查看变化的趋势。

   • 如图 (a) 所示，当增加$s$$ s $ 时模型性能得到改善（固定$w^{(m)}=1,r=1000$$ w^{(m)}=1, r= 1000 $ ）。当$s=10$$ s=10 $ 时模型性能最高。这证明在 common embedding 的帮助下，我们可以使用非常低的维度（约为 common embedding 维度的十分之一）来表达多重网络的每种关系类型。
   • 如图 (b) 所示，当增加$w^{(m)}$$ w^{(m)} $ 时模型性能将会提高（固定$s=10,r=1000$$ s=10,r=1000 $ ）。但是达到 1.0 之后性能略有下降。
   • 如图 (c) 所示，如果将$r$$ r $ 设置得太小，则可能会限制模型的学习过程（固定$s=10,w^{(m)}=1$$ s=10, w^{(m)}=1 $ ）。当$r>10$$ r\gt 10 $ 时模型性能将趋于稳定。

   

7. 节点分类：我们进行节点分类任务来评估embedding 质量。CKM 社交网络是唯一提供分类标签的多重网络，因此我们将其作为实验数据集，label 为 researcher 的原始公司。考虑数据集的大小，我们使用两折交叉验证。

   对于 DeepWalk/LINE/Node2Vec，由于它们是为简单网络设计的，因此我们为每个子图单独训练一个 embedding，然后取所有子图的embedding 均值作为最终 embedding。对于我们的方法，我们将所有类型的权重$w^{(m)}$$ w^{(m)} $ 设置为 1.0 ，然后所有子图 embedding 取平均作为最终 embedding 。

   如下图所示，我们的方法在所有 embedding 方法中性能最好。可以看到即使是最简单的embedding 取平均，我们的模型也可以得到高质量的 overall embedding 。

   数据集太小太简单，结论没有多大的说服力。

   

8. 可扩展性：最后我们研究模型的可扩展性。由于现实世界的社交网络可能非常庞大，因此如果我们学习所有子图的 embedding，这些模型的训练和存储可能是一个巨大挑战。因此，我们提出了小维度的 addtional embedding 和变换矩阵的结构，试图在不牺牲整体性能的条件下减小整体模型的大小。

   如下所示，我们的方法使用的内存几乎和网络大小成线性关系。

   • 与 Node2Vec 和 LINE 相比，我们的模型在不牺牲性能的情况下仅使用十分之一的内存空间。DeepWalk/Line 的空间复杂度为$O(d\times M\times n)$$ O(d\times M\times n) $ ，而我们的空间复杂度为$O((d+s\times M)\times n)$$ O((d+s\times M)\times n) $ 。由于$s\ll d$$ s\ll d $ ，因此我们模型的空间复杂度要小得多。
   • 对于 PMNE，由于它们将多重网络合并到单个网络中，因此它们的模型最小。但是它们的模型也丢失了各种类型关系特有的信息，这些信息在之前的实验中被证明很重要。