Question

1. 随着大数据的兴起（尤其是社交网络），图挖掘已经成为分析对象之间的多样化关系、理解底层图的复杂结构的必要条件。分析如此复杂的系统对于了解社交网络的形成方式、或者预测未来的网络行为至关重要。

   然而，图挖掘对网络的拓扑结构topological structure 非常敏感。例如，在社交网络分析中，图挖掘可以利用拓扑信息来识别网络中的社区，但是无法确定拓扑是否包含噪声（或其它错误）。避免这种情况的一种方法是使用多层网络multilayer network 。多层网络是描述节点之间多种关系的一组网络，其中每个网络（一个网络代表一层 ）代表一种特定类型的关系。

   多层网络也就是多视图网络。

   以 AUCS 数据集为例。多个层代表大学院系 61 名员工之间的五种不同关系类型：共同工作、共进午餐、facebook好友、共度闲暇时光、共著学术论文。下图显示了这些不同层之间的距离（根据论文 《Structural reducibility of multilayer networks》 的方法），其中层之间的距离是包含双方的最小子树的根节点的 distance value 。从下图中，我们观察到一些关键的交互：例如，我们观察到 “共同工作”、“共进午餐” 密切相关，因为它们具有较小的 layer distance ；而 “共度闲暇时光” 和 “facebook好友” 也是密切相关的。一般而言，我们认为，多层网络通过考虑多种关系类型从而固有地反映了节点之间的基本交互 essential interaction ，并且对任何单个关系类型中的噪音都具有鲁棒性。

   

   如今，多层网络上的图挖掘方法通常集中在不同的网络粒度，具体取决于任务。例如：

   • 在节点粒度/边粒度上，《Multiplex networks and interest group influence reputation: An exponential random graph model》 和 《Conditions for viral influence spreading through multiplex correlated social networks》 专注于开发合适的中心性 centrality 指标，例如多层网络的 cross-layer degree 中心性。

     《Individual neighbourhood exploration in complex multi-layered social network》 和 《A method for group extraction in complex social networks》 提出了多层局部聚类系数 multilayered local clustering coefficient: MLCC 和跨层聚类系数 cross-layer clustering coefficient: CLCC 来描述多层网络中节点的聚类系数。

   • 相比之下，cluster 级别通常用于社区检测，而 layer 级别通常用于分析不同层类型之间的交互。

   在论文 《Principled Multilayer Network Embedding》中，作者尝试通过结合所有粒度级别的分析，提出三种新颖的、多层网络的图挖掘方法。作者通过将多层网络的节点嵌入到向量空间来实现这一点。这个向量空间可以被解释为多层网络的隐式度量空间metric space ，它自然地定义了节点之间的相似性概念，并捕获了原始多层网络的多个方面，最终促进了基于向量的 representation 来解决一系列任务。

   在标准的网络分析中，人们已经开发了许多这样的 network embedding 方法，如 DeepWalk, LINE, node2vec。这些方法都基于在输入图上生成随机游走的样本，随机游走的方式因方法而异。然而，这些方法是建立在单个图之上的，据作者所知，多层网络的 graph embedding 方法尚未得到严格的探索。因此，作者提出了一个通用的多层网络 embedding 框架，该框架适用于为单层网络开发的任何 graph embedding 方法。具体而言，作者介绍了将 graph embedding 扩展到多层网络的三种方法，即：网络聚合Network Aggregation、结果聚合Results Aggregation、网络协同Network Co-analysis 。

   • 网络聚合：该方法的假设是来自不同层的所有边都是等价的。基于该假设，该方法将所有网络聚合为单个网络（如果不允许节点之间存在多条边，则聚合后为加权网络），然后应用现有的 graph embedding 算法来分析合并的图。注意，这个合并的图不再区分关系类型。
   • 结果聚合：该方法的假设是不同的层有完全不同的边，这意味着即使两个节点在不同的层中都有边，那么这些边是完全不同的、无法合并的。基于这个假设，该方法将 graph embedding 方法分别应用于每一层，然后将向量空间合并在一起从而定义多层网络的向量空间。
   • 网络协同：与前两种方法仅考虑 inter-layer 边（network aggregation）或 intra-layer 边（results aggregation ）不同，该方法利用不同层之间的交互来允许层之间的遍历，并保留每个层的结构。具体而言，论文引入了一种能够跨层遍历的、新的随机游走方法，从而编码节点和层之间的重要交互。

   多层网络中的随机游走方法是单层 embedding 方法的通用扩展。例如，node2vec 和 DeepWalk 都是state-of-the-art 的单层 graph embedding 方法。就像 node2vec 为 DeepWalk 添加了控制随机游走的同质性homophily 和结构等价性structural equivalence 的能力，论文使得随机游走能够遍历多个层。具体而言，论文添加$r\in [0,1]$$ r\in [0,1] $ 参数来控制随机游走的下一步将在多层网络中跨层遍历的概率。

   论文没多大价值，典型的 ”水“ 文。

2. 相关工作：这里我们回顾了标准的 network embedding 的相关工作，即为单层网络提出的 embedding 方法。

   随着无监督 feature learning 技术的发展，深度学习方法通过神经语言模型在自然语言处理任务中被证明是成功的。这些模型通过将 word 嵌入为向量来捕获人类语言的语义结构semantic structure 和语法结构 syntactic structure ，甚至是捕获逻辑类比logical analogy 。由于图可以被解释为一种语言（通过将随机游走视为等价的 sentence ），DeepWalk 将此类方法引入网络分析，从而允许将网络节点投影到向量空间中。为了解决这类方法在应用于现实世界信息网络（通常包含数百万个节点）时的可扩展性问题，人们开发了 LINE 。LINE 将 DeepWalk 的均匀随机游走扩展为一阶加权随机游走或二阶加权随机游走，从而可以在几个小时内将具有数百万节点、数十亿条边的网络投影到向量空间中。

   但是，这两种方法都有局限性。由于 DeepWalk 使用均匀随机游走进行搜索，因此它无法控制所探索的邻域。相比之下，LINE 提出了一种广度优先策略来采样节点，并在一阶邻域和二阶邻域上独立地优化似然性 likelihood ，但是它无法灵活地探索更深的节点。为了解决这两个限制，node2vec 提供了一种灵活的、可控的策略，通过参数$p$$ p $ 和$q$$ q $ 来探索网络邻域。从实践的角度来看，node2vec 具有可扩展性，并且对扰动具有鲁棒性。

   当然，这些方法都无法处理多层网络的 layer 之间的随机游走。因此，我们的网络协同方法是已有工作在随机游走能力方面的自然扩展。

22.1 模型

1. 给定多层网络$G=(V,L,A)$$ G=(V,L,A) $ ，其中$V$$ V $ 为顶点集合，$L$$ L $ 为layer 集合，$A$$ A $ 为边的集合。

   其中$A\subseteq \{(x,y,l)\mid x,y\in V,l\in L\}$$ A\sube \{(x,y,l)\mid x,y\in V,l\in L\} $ 。如果顶点$(x,y)$$ (x,y) $ 在layer$l$$ l $ 存在边，则记作$a_{x,y}^l=1$$ a_{x,y}^l = 1 $ 。

   多层网络嵌入任务是学习一个映射函数$f:V\to {\mathbb{R}}^d$$ f:V\rightarrow \mathbb R^d $ ，该函数将多层网络的顶点映射到低维向量空间，并在低维空间中保留顶点的结构信息。其中$d$$ d $ 为低维向量空间的维度。

   我们提出了多层网络嵌入的三种架构如下图所示：

   这篇论文是典型的 ”水”文，每什么价值。

   

22.1.1 网络聚合

1. 网络聚合network aggregation 方法将多层网络的多个layer 合并成单层网络，然后将常规的 node2vec 应用于合并后的单层网络。该方法的关键在于网络聚合函数：$g:G(V,L,A)\to G^{\prime }(V,E)$$ g: G(V,L,A) \rightarrow G^\prime(V,E) $ 。该函数将多层网络聚合成单层网络，其中$G^{\prime }$$ G^\prime $ 为一个单层网络，它和$G$$ G $ 共享所有的节点、但是聚合了$G$$ G $ 中所有层的边：

   $$E=\{(i,j)\mid \sum _{l\in L}{a}_{i,j}^l\ge 1\}$$

   注意：这种方式将所有的层组合在一起，从而失去了每一层的细节信息，并且在学习映射$f$$ f $ 时也无法利用层之间的交互信息。

2. 多层网络嵌入之网络聚合算法：

   • 输入：

     • 多层网络$G(V,L,A)$$ G(V,L,A) $
     • node2vec 的超参数

   • 输出：顶点的 embedding

   • 算法步骤：

     • 初始化$G^{\prime }=(V,E=\mathrm{\Phi })$$ G^\prime = (V,E=\Phi) $

     • 网络聚合：

       • 遍历每一对节点$(i,j)\in V$$ (i,j)\in V $ ：

         遍历每一层$l\in L$$ l\in L $ ，如果$a_{i,j}^l=1$$ a_{i,j}^l = 1 $ ，则添加边到$E$$ E $ 中：$E=E\cup (i,j)$$ E=E\cup (i,j) $

     • 在$G^{\prime }$$ G^\prime $ 上执行 node2vec 并返回每个节点的 embedding

22.1.2 结果聚合

1. 结果聚合results aggregation方法将多层网络中的每一层视为一个独立的网络$G_l=(V,E_l)$$ G_l=(V,E_l) $ ，其中$G_l$$ G_l $ 和$G$$ G $ 共享所有节点，但是$E_l$$ E_l $ 仅包含$G$$ G $ 中第$l$$ l $ 层的边：

   $$E_l=\{(i,j)\mid a_{i,j}^l=1\}$$

   我们独立地学习每个网络$G_l$$ G_l $ 中的节点 embedding，然后将节点在所有层的 embedding 拼接起来作为该节点的最终embedding 。这种方法可以保持每一层的网络结构，但是无法利用层之间的交互信息。

2. 多层网络嵌入之结果聚合算法：

   • 输入：

     • 多层网络$G(V,L,A)$$ G(V,L,A) $
     • node2vec 的超参数

   • 输出：节点的 embedding

   • 算法步骤：

     • 遍历每一层$l\in L$$ l\in L $ ：

       • 初始化$G_l=(V,E_l=\mathrm{\Phi })$$ G_l = (V,E_l=\Phi) $
       • 遍历$(i,j)\in V$$ (i,j)\in V $ ，如果$a_{i,j}^l=1$$ a_{i,j}^l=1 $ 则添加边到$E_l$$ E_l $ 中：$E_l=E_l\cup (i,j)$$ E_l=E_l\cup (i,j) $
       • 在$G_l$$ G_l $ 上执行 node2vec 得到顶点在第$l$$ l $ 层的 embedding

     • 拼接节点在所有层的 embedding，得到节点的最终 embedding

22.1.3 网络协同

1. 为了克服网络聚合、结果聚合都无法利用层间交互的缺陷，我们采用网络协同layer co-analysis 来构建顶点embedding，该方法可以识别各层之间的交互，并保留各层的结构。

2. 考虑下图所示的多层网络随机游走，其中黑色点线代表每层顶点之间的对应关系，黑色粗线代表网络中的边。

   • 如果在图 (a) 中使用结果聚合，则节点 A 到节点 C 没有路径，因为结果聚合无法在层之间遍历。因此该方法无法学到节点 A 和 C 的关联。
   • 如果在图 (b) 中使用网络聚合，则会忽略节点$A^{\prime }$$ A^\prime $ 和$B^{\prime }$$ B^\prime $ 之间的多条边（由红色粗线表示）。

   这使得我们我们寻求一种方法，该方法可以遍历从 A 到C 的跨层路径（图 (a) 的红色虚线表示），并可以保留多条边隐含的信息。

   

3. node2vec 在 DeepWalk 基础上引入了参数$p$$ p $ 和$q$$ q $ 来控制随机游走的局部 bias 和全局 bias，我们在 node2vec 基础上再引入参数$r$$ r $ 来控制多层网络中的跨层遍历。

   令$i_{|L|}$$ i_{|L|} $ 为节点$i$$ i $ 在多层网络中存在链接的层的数量（去重），即：

   $$i_{|L|}=\sum _{l=1}^{|L|}I(\sum _{(i,j,l)\in E}{a}_{i,j}^l\ge 1)$$

   其中$I(\cdot )$$ I(\cdot) $ 为示性函数。

   我们引入参数为$p,q,r$$ p,q,r $ 的二阶随机游走。假设第$t_{i-1}$$ t_{i-1} $ 步随机游走在第$l$$ l $ 层、从节点$z$$ z $ 游走到节点$x$$ x $ 。现在位于第$l$$ l $ 层的节点$x$$ x $ 需要决定下一步的顶点$y$$ y $ ：

   • 如果当前节点$x$$ x $ 仅在层$l$$ l $ 上存在边（即$x_{|L|}=1$$ x_{|L|} = 1 $ ），则我们使用 node2vec 在层$l$$ l $ 内的随机游走：

     $$p(t_i=(x,y,l)\mid t_{i-1}=(z,x,l))\propto a_{p,q}(z,y,l)$$

     其中$a_{p,q}(z,y,l)$$ a_{p,q}(z,y,l) $ 是 node2vec 针对多层网络的修改：

     $$\begin{array}{c}{a}_{p,q}(z,y,l)=\{\begin{array}{ll}\frac{1}{p},& d_{z,y}^l=0\\ 1,& d_{z,y}^l=1\\ \frac{1}{q},& d_{z,y}^l=2\end{array}\end{array}$$

     其中$d_{z,y}^l$$ d_{z,y}^l $ 表示在层$l$$ l $ 中节点$z$$ z $ 和$y$$ y $ 的最短路径（以节点数量来衡量）。注意：$y$$ y $ 有可能和$z$$ z $ 是相同的顶节。

   • 如果当前节点$x$$ x $ 在多个层上都存在边，则随机游走序列留在当前$l$$ l $ 层的概率为$r$$ r $ 、游走到第$l^{\prime }$$ l^\prime $ 层的概率为$(1-r)$$ (1-r) $ ：

     $$\begin{array}{c}p(t_i=(x,y,l^{\prime })\mid t_{i-1}=(z,x,l))\propto \{\begin{array}{ll}{a}_{p,q}(z,y,l^{\prime })\times r,& l^{\prime }=l\\ \frac{a_{p,q}(z,y,l^{\prime })}{x_{|L|}-1}\times (1-r),& \text{else}\end{array}\end{array}$$

   本文仅考虑二元边，也可以通过将遍历边的概率乘以归一化的边权重从而推广到加权的多层网络。

   另外，我们将在未来探索如何通过分析多层网络的层距离来自动学习$r$$ r $ ，当前我们仅将其视为一个超参数。

4. 多层网络嵌入之网络协同算法：

   • 输入：

     • 多层网络$G(V,L,A)$$ G(V,L,A) $
     • 随机游走序列数量$N$$ N $
     • 每条游走序列长度$M$$ M $
     • 超参数$p,q,r$$ p,q,r $

   • 输出：节点的 embedding

   • 算法步骤：

     • 初始化游走路径集合$\mathcal{W}=\varphi$$ \mathcal W = \phi $

     • 迭代直到生成$N$$ N $ 条随机游走序列。对第$n$$ n $ 条随机游走序列：

       • 随机选择一条边作为序列的起始边：$(i,j,l)\leftarrow (i_0,j_0,l_0)$$ (i,j,l)\leftarrow (i_0,j_0,l_0) $ ，其中$j$$ j $ 为当前节点、$l$$ l $ 为当前层、$i$$ i $ 为序列中的前一个节点

       • 迭代直到第$n$$ n $ 条随机游走序列的长度为$M$$ M $ ：

         • 以概率$r$$ r $ 选择留在当前层、或者均匀随机地选择其它层作为 next_layer
         • 以概率$\text{Error: '\_' allowed only in math mode}$$ a_{p,q}(j,i^\prime,\text{next_layer}) $ 选择next_layer 中的下一个节点
         • $\text{Error: '\_' allowed only in math mode}$$ l\leftarrow \text{next_layer}, j\leftarrow i^\prime, i\leftarrow j $

     • 对随机游走路径集合$\mathcal{W}$$ \mathcal W $ 执行node2vecSGD（基于 node2vec 对数似然目标函数的随机梯度下降）。

5. 超参数$r$$ r $ 衡量了是留在同一层重要、还是跨层交互重要。

   • 当$r\to 0$$ r\rightarrow 0 $ 时随机游走总是跨层，因此算法认为跨层交互重要。
   • 当$r\to 1$$ r\rightarrow 1 $ 时随机游走总数留在同一层（也就是初始化的层），因此算法认为留在同一层重要。

22.2 实验

1. 数据集：

   • AUCS 数据集：数据集为一个多层网络，代表大学部门的 61 位员工之间的五种不同关系：coworking, having lunch together, facebook friendship, onine friendship(having fun together), coauthorship 。

   • Terrorist 数据集：数据集为一个多层网络，代表恐怖分子之间的不同关系：communication, financial, operation, trust。

   • Student 数据集：数据集为一个多层网络，代表 Ben-Gurion University 中 185 名学生之间的不同关系： Computer Network（学生在同一台机器上完成论文）、Partner’s Networt（学生共同完成论文）、Time Network（学生在同一时间提交论文）。

   • Vickers Chan 数据集VC：数据集为一个多层网络，代表七年级学生社交的不同互动关系：你在班上和谁打交道、谁是你班上最好的朋友、你最想和谁一起玩。

   • Leskovec-Ng collaboration 数据集LN：数据集为一个多层网络，代表从 1995 到 2014 不同年代 Jure Leskovec 和 Andrew Ng 的共同著作网络。我们将 coauthorship 网络按照 5 年一个layer，最终得到四层网络。在每层网络中，如果和这两个作者任意一个至少由一篇共同著作，则存在一条边。

     根据协作的频次，每位学者被标记为 Leskovec 的协作者、或者 Ng 的协作者。

   

2. 我们在这些多层网络数据集上执行链接预测任务，从而比较不同方法在链接预测任务上的性能。

   我们将边$E$$ E $ 划分为训练集$E^T$$ E^T $ 和测试集$E^P$$ E^P $ ，其中$E=E^T\cup E^P$$ E=E^T\cup E^P $ 且$E^T\cap E^P=\mathrm{\Phi }$$ E^T\cap E^P = \Phi $ 。这里我们选择 10% 的边作为测试集。

   我们使用我们的embedding 方法在训练集$E^T$$ E^T $ 上训练得到顶点 embedding，然后计算$E^P$$ E^P $ 中节点对的距离，并将这些距离升序排列。我们将排序的顶点对中的前 10% 预测为存在边，并将预测结果和$E^P$$ E^P $ 中的真实结果进行比较。评估指标为准确率和$F_1$$ F_1 $ 得分：

   • 准确率 acc 为$acc=\frac{C}{|E^P|}$$ acc = \frac{C}{|E^P|} $ ，其中$C$$ C $ 表示$E^P$$ E^P $ 中预测正确的边的数量。

     这个指标其实是召回率指标，而不是准确率。

   • F1 得分为$F_1=\frac{1}{|L|}\sum _{l=1}^L{F}_1^l$$ F_1 = \frac{1}{|L|}\sum_{l=1}^L F_1^l $ ，其中$F_1^l$$ F_1^l $ 为第$l$$ l $ 层链接预估的 precision 和 recall 的调和均值。

     这个指标预估每个层的边。

   我们的方法中，超参数设置为：$p=q=r=0.5$$ p=q=r=0.5 $ 、每个顶点开始的随机游走序列数量为 10、每条随机游走序列的长度为 80 。

3. baseline 模型：我们在融合的网络中引入两个著名的链接预测算法：

   • Common Neighbor Similarity：${\text{CN}}_{x,y}=|\mathrm{\Gamma }(x)\cap \mathrm{\Gamma }(y)|$$ \text{CN}_{x,y} = |\Gamma(x) \cap \Gamma(y)| $ 。其中$\mathrm{\Gamma }(x)$$ \Gamma(x) $ 表示融合图中顶点$x$$ x $ 的邻居集合。
   • Jaccard Similarity：${\text{Jaccard}}_{x,y}=\frac{|\mathrm{\Gamma }(x)\cap \mathrm{\Gamma }(y)|}{|\mathrm{\Gamma }(x)\cup \mathrm{\Gamma }(y)|}$$ \text{Jaccard}_{x,y} = \frac{|\Gamma(x)\cap \Gamma(y)|}{|\Gamma(x)\cup \Gamma(y )|} $ 。

   这两种方法也是选择相似度最大的 top 10% 来预测存在边。

   baseline 没有 graph embedding 方法，垃圾。数据集太拉胯。

4. 不同方法在不同数据集上的评估结果如下表所示。可以看到，除了 LN 数据集以外，我们的方法可以实现更高的准确率和 F1 得分。

   

5. 不同数据集中各层之间的距离如下所示：

   

   

6. 我们使用下图来给出三个多层网络每一层和相应的融合层的结构。由于 VC 数据集和 LN 数据集带有标签信息，因此我们使用不同的形状和颜色来展示不同标签的顶点。

   • 在 Terrorists 数据集中，多层网络显式了恐怖分子如何协作。显然，不同层之间的作用影响很大。这意味着如果我们需要预测两个顶点之间的链接，则需要考虑这两个顶点在不同层之间的交互。以图 (a) 为例，尽管 financial 层的顶点很少，但是四层之间的交互作用很强，而网络协同可以通过不同层的随机游走来恢复必要的信息。

     对于 AUCS/Students 数据集，也是类似的结果。

   • 在VC 数据集中，不同question 代表不同的关系，因此不同层之间的作用影响较弱。比如，“你在班上和谁打交道” （Q1 ）并不意味着你和她/他就是好朋友关系 （Q2 ）。由于第一个问题过于笼统，导致产生大量的噪音，因此无法指示这些顶点之间的真实关系。

     如果我们将这些层合并，或者更多地关注层交互上，那么网络聚合和网络协同都无法揭示真实的信息，反而会引入更多噪音。

   • 在 LN 数据集中，不同时间区间的layer 没有任何交互。如，第一层没有蓝色顶点、第二层和第三层中两个簇自行扩展。这表明以下事实：层之间的交互作用并不是对应层中形成拓扑结构的关键。而且，各层之间的间隔为 5 年，因此层内的噪音使得我们的方法效果较差。

     相反，原始 Jaccard 方法最好，因为它仅关心两个顶点的平均共享邻居数量，这种方法受噪音影响最小。