Question

1. 在几乎所有网络中，节点往往具有一种或多种功能，这些功能极大地决定了节点在系统中的作用。例如，社交网络 social network 中的个体具有社会角色 social role 或社会地位 social position ，而 protein-protein interaction(PPI) network 中的蛋白质发挥特定功能。直观而言，这些网络中的不同节点可能执行类似的功能，例如公司的社交网络中的实习生、细胞的 PPI 网络中的催化剂。因此，节点通常可以根据它们在网络中的功能划分为等价的类别 equivalent class 。

   尽管此类功能的识别通常利用节点的属性和边的属性，但是当节点功能仅由网络结构定义时，会出现更具挑战性和更有趣的场景。在这种情况下，甚至节点的 label 都不重要，而只需要节点与其它节点（或者边）的关系。事实上，自 1970 年代以来，数学社会学家mathematical sociologist 一直在研究这个问题，定义和计算社交网络中个体的结构身份 structural identity。除了社会学之外另一个例子是，识别网页在 web-graph 中的结构身份（如 hub 、authority ），正如 Kleinberg 的著名著作《Authoritative sources in a hyperlinked environment》所定义的那样。

   结构身份是一种对称性概念，其中节点是基于网络结构来识别的。这个概念与网络中节点所扮演的功能或角色密切相关。确定节点结构身份的最常见实用方法是基于距离或者递归。

   • 在基于距离的方法中，我们利用节点邻域的距离函数从而测量所有节点 pair 对之间的距离，然后执行聚类clustering或匹配matching 从而将节点放入等价的类别。
   • 在基于递归的方法中，我们构造一个关于相邻节点的递归，然后迭代展开 iteratively unfold 直到收敛，节点上的最终值final value 用于确定等价的类别。

   虽然这些方法有优点和缺点，但论文 《struc2vec: Learning Node Representations from Structural Identity》 提供了一种替代方法，一种基于无监督 representation learning 的方法用于识别节点的结构身份。

   最近在学习网络中节点的潜在 representation 方面的努力在执行分类和预测任务方面非常成功。具体而言，这些努力使用广义的节点邻域作为上下文 context （例如，随机游走的 $ w $ 步、或者具有共同邻居的节点集合），从而对节点进行编码。简而言之，具有相似邻域的节点应该具有相似的潜在 representation 。但是，邻域是由网络中的一些邻近性概念 notion of proximity 定义的局部概念 local concept 。因此，如果两个节点的邻域表现出结构相似但是相距很远，那么这两个节点将不会具有相似的潜在 representation 。下图说明了这个问题，其中节点 $ u $ 和 $ v $ 扮演相似的角色（即，具有相似的局部结构 local structure），但是这两个节点在网络中相距很远。由于它们的邻域没有交集，因此最新的方法无法捕获它们的结构相似性 structural similarity 。

   

   值得注意的是，为什么最近学习 node representation 的方法，如 DeepWalk 和 node2vec 在分类任务中成功，但是在结构等价性任务 structural equivalence task 中往往失败。关键是在大多数真实网络中，许多节点特征都表现出强烈的同质性，例如具有相同政治倾向 political inclination 的两个博客存在连接的可能性相比随机的两个博客要大得多。具有给定特征的节点，其邻居更有可能具有相同的特征。因此，在网络和潜在 representation 中，“靠近” （close）的两个节点将倾向于有相似的 representation。同样地，“远离”（far）的两个节点将倾向于有不同的 representation，而与节点的局部结构无关。因此，潜在 representation 将无法正确地捕获结构等价性 structural equivalence。然而，如果分类任务更多地依赖于结构身份的特征而不是同质性的特征，那么捕获结构等价性的方法将超越最近的这些方法。

   论文 《struc2vec: Learning Node Representations from Structural Identity》 的主要贡献是一个灵活的、称作 struc2vec 的框架，用于学习节点结构身份的潜在representation 。该框架是基于潜在 representation 来研究结构身份的强大工具。 struc2vec 的关键思想是：

   • 独立于节点属性、边属性、以及节点和边在网络中的位置来评估节点之间的结构相似性 structural similarity 。因此，具有相似局部结构的两个节点被认为是相似的，而无关于节点在网络中的位置和节点的 label。并且该方法也不需要网络是连通的，可以在不同的连通分量connected component 中识别结构相似的节点。
   • 建立一个层级 hierarchy 来衡量结构相似性，从而允许更严格的结构相似性的的概念。具体而言，在 hierarchy 的底部，节点之间的结构相似性仅取决于它们的 degree；而在 hierarchy 的顶部，节点之间的结构相似性取决于整个网络（从节点的角度来看）。
   • 为节点生成随机上下文。该上下文是结构相似的节点序列，通过遍历一个多层图 multilayer graph （而不是原始网络）的加权随机游走而观察到的。因此，经常出现在相似上下文中的两个节点可能具有相似的结构。语言模型利用了这种上下文来学习节点的潜在 representation。

   论文实现了一个 struc2vec 实例，并通过对 toy 网络和真实网络的实验展示了 struc2vec 的潜力，并将 struc2vec 的性能与 DeepWalk、node2vec 、RolX 等方法进行比较。DeepWalk 和 node2vec 是用于学习节点潜在 representation 的两种 state-of-the-art 技术，RolX 是一种识别节点角色的最新方法。

   论文的实验结果表明：

   • DeepWalk 和 node2vec 未能捕获到结构身份的概念，而 struc2vec 在这项任务上表现出色，即使原始网络受到很强的随机噪声（随机地移除边）的影响。
   • struc2vec 在那些节点标签更多地依赖于结构身份的分类任务中表现出色，例如航空交通网络air-traffic network。

2. 相关工作：在过去的几十年中，在空间（例如欧式空间）中嵌入网络节点受到了不同社区的广泛关注。embedding 技术有助于帮助机器学习应用程序利用网络数据，因为 node embedding 可以直接用于分类和聚类等任务。

   在自然语言处理中，为稀疏数据生成稠密的 embedding 具有悠久的历史。最近，人们提出 SkipGram 作为一种有效的技术来学习文本数据的 embedding 。学到的语言模型将语义相似的单词在 embedding 空间中彼此靠近。

   DeepWalk 首先提出从 network 中学习语言模型。它使用随机游走从网络中生成节点序列，然后将节点序列视为句子sentence 并应用 SkipGram。直观而言，网络中靠近的节点往往具有相似的上下文，因此具有彼此靠近的 embedding 。node2vec 后来扩展了这一思想，并提出有偏 biased 的二阶随机游走模型，从而在生成节点上下文时提供了更大的灵活性。具体而言，node2vec 通过设计边权重（边权重会导致有偏的随机游走）从而尝试同时捕获节点同质性 vertex homophily 和结构等价性 structural equivalence 。然而，这里存在一个基本限制：如果节点的距离（hop 数）大于 SkipGram 窗口，那么结构相似的节点将永远不会共享相同的上下文。

   struc2vec 也是基于 DeepWalk 框架的，只是 struc2vec 生成随机游走序列的方式不同。

   subgraph2vec 是最近提出的另一种学习有根子图 rooted subgraph 的 embedding 的方法。与以前的技术不同，它不使用随机游走来生成上下文。相反，节点的上下文仅由其邻居定义。此外，subgraph2vec 通过将具有相同局部结构local structure 的节点嵌入到空间中的同一个点来捕获结构等价性。尽管如此，结构等价性的概念是非常严格的，因为它被定义为由 Weisfeiler-Lehman 同构测试规定的二元属性 binary property （0/1 代表是否某个子结构）。因此，结构上非常相似（但是未通过 Weisfeiler-Lehman 同构测试）并且具有非重叠邻居 non-overlapping neighbor 的两个节点在空间上可能不会靠近。

   与 subgraph2vec 类似，最近人们在学习网络节点更丰富的 representation 方面做出了相当大的努力。然而，构建显式捕获结构身份的 representation 是一个相对正交的问题，尚未受到太多关注。这是 struc2vec 的重点。

   最近一种仅使用网络结构来显式识别节点角色的方法是 RolX。这种无监督方法的思想为：

   • 枚举节点的各种结构特征。
   • 为这个联合特征空间找到更合适的基向量。
   • 为每个节点分配一个已识别角色（即基向量）的分布。

   这允许每个节点跨多个角色从而得到混合成员关系 mixed membership 。在未显式考虑节点相似性或节点上下文的情况下，RolX 很可能会遗漏结构上等价的节点 pair 对。

13.1 模型

1. 考虑捕获网络中节点结构身份的 representation learning 问题。一个成功的方法应该有两个预期的属性：

   • 节点的潜在 representation 之间的距离应该与其结构相似性structural similarity 强相关。因此，具有相同结构身份的两个节点应该具有相同的潜在 representation，而具有不同结构身份的节点应该相距很远。
   • 节点的潜在 representation 不应该依赖于任何节点属性或边属性，包括节点 label。因此，结构相似的节点应该具有靠近的潜在 representation ，独立于其邻域中节点属性和边属性。节点的结构身份必须独立于节点在网络中的 “位置”。

   鉴于这两个属性，我们提出了 struc2vec框架。这是一个用于学习节点潜在 representation 的通用框架，由四个部分组成：

   • 结构相似性度量：基于不同的邻域大小，为图中每对节点 pair 对之间定义结构相似性。这在节点之间的结构相似性度量中引入了 hierarchy ，为评估 hierarchy 中每个 level 的结构相似性提供了更多信息。

     每个邻域大小定义了一组节点 pair 相似性。

• 加权 multilayer graph ：构造一个加权的multilayer graph，其中每个 layer都包含原始图的所有节点，并且每个 layer 对应于hierarchy 中的某个 level （对应于不同的邻域大小）。此外，layer 内每个节点 pair 对之间边的权重与结构相似性成反比。

  • 上下文生成：使用 multilayer graph为每个节点生成上下文。具体而言，使用 multilayer graph 上的有偏随机游走来生成节点序列。这些序列可能包含结构上更相似的节点。
  • 学习embedding：采用一种技术（如 SkipGram ）从节点序列给出的上下文中学习潜在 representation 。

  注意，struc2vec 非常灵活，它不要求任何特定的结构相似性度量或者representational learning 框架。

  struc2vec 的核心思想是构建任意一对顶点之间的结构相似性。这个结构相似性有多个 level，由 1 阶到 k 阶邻域来决定。而邻域之间的结构相似性根据邻域节点 degree 序列的相似性来计算。

13.1.1 结构相似性

1. struc2vec 的第一步是在不使用任何节点属性或边属性的情况下确定两个节点之间的结构相似性。此外，这种相似性度量应该是层次的 hierarchical ，即随着邻域大小不断增加而捕获更精细的结构相似性概念。直观而言，具有相同degree 的两个节点在结构上相似。但是如果它们的邻居也具有相同的 degree，则这两个节点在结构上会更相似。

2. 设 $ \mathcal G=(\mathcal V,\mathcal E) $ 为一个无向无权图， $ \mathcal V $ 为节点集合， $ \mathcal E $ 为边集合， $ n=|\mathcal V| $ 为所有节点数量。设 $ k^* $ 为图的直径（节点 pair 对之间距离的最大值）。

   定义 $ \mathcal R_k(u) $ 为图中与节点 $ u $ 距离为 $ k $ 的节点的集合， $ k\ge 0 $ 。根据该定义， $ \mathcal R_1(u) $ 表示 $ u $ 的直接邻居节点的集合， $ \mathcal R_k(u),k\gt 1 $ 表示和 $ u $ 距离为 $ k $ 的环 ring 上的节点集合。定义 $ \mathbf S(\mathcal R) $ 为节点集合 $ \mathcal R\sub \mathcal V $ 的有序degree 序列 ordered degree sequence 。

   通过比较节点 $ u $ 和 $ v $ 的距离为 $ k $ （一个环 ring 上的节点）的有序degree 序列，我们可以得到节点 $ u $ 和 $ v $ 的相似性。根据不同的距离 $ k $ ，我们可以得到一个 hierarchy 相似性。具体而言，定义 $ f_k(u,v) $ 为节点 $ u $ 和 $ v $ 的 $ k $ 阶结构距离（考虑节点 $ u $ 和 $ v $ 的 k-hop 邻域，即距离小于或等于 $ k $ 的所有节点它们之间的边），我们递归定义为：

   $ f_k(u,v) = f_{k-1}(u,v) + g(\mathbf S(\mathcal R_k(u)),\mathbf S(\mathcal R_k(v)))\\ k\ge 0, |\mathcal R_k(u)|\gt 0,|\mathcal R_k(v)|\gt 0 $

   其中 $ g(\mathbf D_1,\mathbf D_2) \ge 0 $ 衡量了两个有序 degree 序列 $ \mathbf D_1,\mathbf D_2 $ 的距离，且 $ f_{-1}(\cdot,\cdot) = 0 $ 。

   $ f_k(u,v) $ 的物理意义为：节点 $ u,v $ 的 $ k $ 阶结构距离等于它们的 $ k-1 $ 阶结构距离加上它们的第 $ k $ 阶环之间的距离。

   根据定义有：

   • $ f_k(u,v) $ 是随着 $ k $ 递增，并且只有当 $ u,v $ 各自都存在距离等于 $ k $ 的邻域节点时才有定义。
   • $ f_k(u,v) $ 将比较节点 $ u $ 和 $ v $ 各自距离为 $ 1,2,\cdots,k $ 的环的有序 degree 序列。
   • 如果 $ u $ 和 $ v $ 的 $ k $ 阶邻域是 isomorphic 同构的，则有 $ f_k(u,v) = 0 $ 。

3. 最后一步是确定某个函数来比较两个 degree 序列，即函数 $ g(\cdot,\cdot) $ 。考虑到两个有序 degree 序列 $ \mathbf S(\mathcal R_k(u)) $ 和 $ \mathbf S(\mathcal R_k(v)) $ 可能具有不同的长度（因为对于不同节点，其 $ k $ 阶环的size 不同），且它们的元素是位于 $ [0,n - 1] $ 之间的任意整数（可能有重复的整数），则如何选择合适的距离函数是一个问题。

   我们采用 Dynamic Time Warping: DTW 算法来衡量两个有序 degree 序列的距离，该算法可以有效地处理不同长度的序列并宽松地 loosely 比较序列模式 sequence pattern 。

   非正式地，DTW 算法寻找两个序列 $ \mathbf A $ 和 $ \mathbf B $ 之间的最佳对齐 alignment。给定序列元素的距离函数 $ d(a,b) $ ，DTW 的目标是匹配每个元素 $ a\in \mathbf A $ 到 $ b\in \mathbf B $ ，使得被匹配的元素之间的距离之和最小。由于序列 $ \mathbf A $ 和 $ \mathbf B $ 的元素是节点的 degree，因此我们采用以下距离函数：

   $ d(a,b) = \frac{\max(a,b)}{\min(a,b)} -1 $

   注意：

   • 当 $ a=b $ 时， $ d(a,b) = 0 $ 。因此，两个相同的有序 degree 序列将具有零距离。
   • 采用这种距离，degree 1 和 degree 2 之间的距离，相比 degree 101 和 degree 102 之间的距离，二者差异悬殊。这恰好是度量节点 degree 之间距离所需的属性。

   最后，虽然我们使用 DTW 来评估两个有序 degree 序列之间的相似性，但是我们的框架可以采用任何其它函数。

4. DTW 算法：假设 $ \mathbf A=\{a_1,a_2,\cdots,a_n\},\mathbf B=\{b_1,b_2,\cdots,b_m\} $ ，则 DTW 算法需要寻找一条从 $ (a_1,b_1) $ 出发、到达 $ (a_n,b_m) $ 的最短路径。假设路径长度为 $ K $ ，第 $ k $ 个节点为 $ p_k=(a_{i_k},b_{j_k}) $ ，则路径需要满足条件：

   • 边界条件： $ (i_1,j_1) = (1,1), (i_{K},j_{K}) = (n,m) $
   • 连续性性：对于下一个节点 $ p_{k+1} $ ，它必须满足 $ i_{k+1} - i_k \le 1, j_{k+1}-i_k\le1 $ 。即数据对齐时不会出现遗漏。
   • 单调性：对于下一个节点 $ p_{k+1} $ ，它必须满足 $ i_{k+1}\ge i_k, j_{k+1}\ge j_k $ 。即数据对齐时都是按顺序依次进行的。
   • 路径最短： $ \min\sum_{k=1}^K d(p_k) $ ，其中 $ d(\cdot) $ 为单次对齐的距离。

   如下图所示，根据边界条件，该路径需要从左下角移动到右上角；根据单调性和连续性，每一步只能选择右方、上方、右上方三个方向移动一个单位。该问题可以通过动态规划来求解。

   

13.1.2 构建 context graph

1. 我们构建了一个 multilayer 加权图来编码节点之间的结构相似性。定义 $ \mathcal M $ 为一个multilayer 图，其中 layer $ k $ （ $ k=0,\cdots,k^* $ ）根据节点的 $ k $ 阶结构相似性来定义。

   layer $ k $ 是一个包含节点集合 $ \mathcal V $ 的带权无向完全图 complete graph （完全图表示任意一对节点之间存在边），即包含 $ C_{n}^2 $ 条边。每条边的权重由节点之间的 $ k $ 阶结构相似性来决定：

   $ w_k(u,v) = \exp\left(-f_k(u,v)\right)\quad k=0,\cdots,k^* $
   • 仅当 $ f_k(u,v) $ 有定义时，layer $ k $ 中节点 $ u,v $ 之间的边才有定义。
   • layer $ k $ 中边的权重与结构距离（即 $ k $ 阶结构相似性）成反比。
   • layer $ k $ 中边的权重小于等于1 ，当且仅当 $ f_k=0 $ 时权重等于 1 。
   • 和节点 $ u $ 结构相似的节点将在 $ \mathcal M $ 的各层中都具有更大的权重。

   由于 $ f_k(u,v) $ 是随着 $ k $ 的增加单调增加的，因此同一对节点 $ u,v $ 从multilayer 图的底层到高层，边的权重是逐渐降低的。

2. 对于multilayer 图的不同层之间，我们使用有向边进行连接。每个节点可以连接上面一层、下面一层对应的节点。假设节点 $ u $ 在 layer $ k $ 记作 $ u^{(k)} $ ，则 $ u^{(k)} $ 可以通过有向边分别连接到 $ u^{(k-1)},u^{(k+1)} $ 。

   对于跨 layer 的边，我们定义其边的权重为：

   $ w\left(u^{(k)},u^{(k+1)}\right)= \log(\Gamma_k(u) +e)\quad k=0,\cdots,k^*-1\\ w\left({u^{(k)},u^{(k-1)} }\right)=1\quad k=1,\cdots,k^* $

   其中 $ \Gamma_k(u^{(k)}) $ 为 layer $ k $ 中， $ u $ 的所有边中权重大于该层平均边的权重的数量。即：

   $ \bar w_k = \frac{1}{C_{n}^2}\sum_{(u,v)\in C_{n}^2} w_k(u,v),\quad \Gamma_k(u) = \sum_{v\in \mathcal V}\mathbb I(w_k(u,v) \gt \bar w_k) $

   因此 $ \Gamma_k(u) $ 衡量了在layer $ k $ ，顶点 $ u $ 和其它顶点的相似性（超出平均水平的、相似的节点数量）。这里采用对数函数，因为节点 $ u $ 超过层内平均权重的边的数量取值范围较大，通过对数可以压缩取值区间。

   • 如果 $ u $ 在当前层拥有很多结构相似的节点，则应该切换到更高层进行比较，从而得到更精细的上下文。

     根据定义有 $ w\left(u^{(k)},u^{(k+1)}\right) \ge w\left({u^{(k)},u^{(k-1)} }\right) $ ，因此每个每个节点连接更高层的权重不小于连接更低层的权重。

   • 通过向上移动一层，相似节点的数量只会减少。

     因为同一对节点 $ u,v $ 从multilayer 图的底层到高层，结构相似性是逐渐降低的。

3. $ \mathcal M $ 具有 $ k^* $ 层，每一层有 $ n $ 个节点，层内有 $ C_{n}^2 $ 条边，层之间有 $ n $ 条边。因此multilayer 图有 $ k^* C_{n}^2 + 2n(k^*-1) $ 条边。接下来我们会讨论如何优化从而降低生成 $ \mathcal M $ 的计算复杂度，以及存储 $ \mathcal M $ 的空间复杂度。

13.1.3 生成节点上下文

1. 我们通过 multilayer 图 $ \mathcal M $ 来生成每个节点 $ u\in \mathcal V $ 的结构上下文。注意： $ \mathcal M $ 仅仅使用节点的结构信息，而没有采用任何额外信息（如节点属性或节点 label）来计算节点之间的结构相似性。

   和之前的工作一样，我们也采用随机游走来生成给定节点的上下文。具体而言，我们考虑有偏的随机游走：根据 $ \mathcal M $ 中边的权重来在 $ \mathcal M $ 中随机游走。假设当前 layer 位于第 $ k $ 层：

   • 首先以概率 $ q\gt 0 $ 来决定：是在当前 layer 内游走还是需要切换 layer 游走。即以概率 $ q $ 来留在当前layer，以概率 $ 1-q $ 来跨层。

     $ q $ 为一个超参数。

   • layer 内游走：当随机游走保留在当前 layer 时，随机游走从节点 $ u $ 转移到节点 $ v $ 的概率为：

     $ p_k(u,v) = \frac{w_k(u,v)}{\sum_{v^\prime\in \mathcal V,v^\prime\ne u}w_k(u,v^\prime)} $

     其中分母是归一化系数。

   因此随机游走更倾向于游走到与当前节点结构更相似的节点，避免游走到与当前节点结构相似性很小的节点。最终节点 $ u $ 的上下文中包含的更可能是和 $ u $ 结构相似的节点，与它们在原始网络 $ G $ 中的 label 和位置无关。

   • 层间游走：如果需要切换 layer ，则是移动到更上一层、还是移动到更下一层，这由层之间的有向边的权重来决定：

     $ p_k\left(u^{(k)},u^{(k+1)}\right) = \frac{w\left(u^{(k)},u^{(k+1)}\right)}{w\left(u^{(k)},u^{(k+1)}\right) + w\left(u^{(k)},u^{(k-1)}\right)}\\ p_k\left(u^{(k)},u^{(k-1)}\right) = 1- p_k\left(u^{(k)},u^{(k+1)}\right) $

     跨层概率正比于层之间的有向边的权重。

2. 最后，对于每个节点 $ u\in V $ ，我们从第 $ 0 $ 层开始进行随机游走。每个节点生成以它为起点的 $ r $ 条随机游走序列，每条随机游走序列的长度为 $ l $ 。

3. 我们通过 SkipGram 来从随机游走序列中训练节点 embedding ，训练的目标是：给定序列中的节点，最大化其上下文的概率。其中上下文由中心窗口的宽度 $ w $ 来给定。

   • 为了降低计算复杂度，我们采用 Hierarchical Softmax 技巧。
   • 这里也可以不使用 SkipGram ，而采用任何其它的文本 embedding 技术。

13.1.4 优化

1. 为了构建 $ \mathcal M $ ，我们需要计算每一层每对节点之间的距离 $ f_k(u,v) $ ，而 $ f_k(u,v) $ 需要基于 DTW 算法在两个有序 degree 序列上计算。经典的 DTW 算法的计算复杂度为 $ O(l^2) $ ，其快速实现的计算复杂度为 $ O(l) $ ，其中 $ l $ 为最长序列的长度。

   令 $ d_\max $ 为网络中的最大 degree，则对于任意节点 $ u $ 和 layer $ k $ ， degree 序列的长度满足 $ |\mathbf S(\mathcal R_k(u)|\lt \min(d_\max^k,n) $ ，其中 $ d_\max^k $ 表示 $ d_\max $ 的 $ k $ 次幂，它随着 $ k $ 的增加而很快接近 $ n $ 。由于每一层有 $ C_{n}^2 $ 对节点，因此计算第 $ k $ 层所有距离的计算复杂度为 $ O(n^2\times \min(d_\max^k,n)) $ 。最终构建 $ \mathcal M $ 的计算复杂度为 $ O(k\times n^3) $ 。接下来我们介绍一系列优化来显著减少计算复杂度和空间复杂度。

2. 优化一：降低有序 degree 序列的长度。

   为了降低对比长序列距离的代价，我们对有序degree 序列进行压缩：对序列中出现的每个 degree，我们保存它出现的次数。压缩后的有序 degree 序列由该 degree，以及它出现的次数构成的元组来组成。由于网络中很多节点往往具有相同的 degree，因此压缩后的有序 degree 序列要比原始序列小一个量级。

   注意：压缩后的有序 degree 序列也是根据 degree 进行排序。

   令 $ \mathbf A^\prime,\mathbf B^\prime $ 为压缩后的有序 degree 序列，它们的元素都是元组的形式。则我们在DTW 中的距离函数 $ d(\cdot,\cdot) $ 修改为：

   $ d((a_0,a_1),(b_0,b_1)) = \left(\frac{\max(a_0,b_0)}{\min(a_0,b_0)}-1\right)\max(a_1,b_1) $

   其中 $ (a_0,a_1)\in \mathbf A^\prime, (b_0,b_1)\in \mathbf B^\prime $ ， $ a_0,b_0 $ 都是 degree， $ a_1,b_1 $ 都是degree 对应出现的次数。

   注意：使用压缩的 degree 序列会使得具有相同 degree 的原始序列片段之间的比较。原始的 DTW 算法是比较每个 degree，而不是比较每个 degree 片段，因此上式是原始 DTW 的近似。由于 DTW 现在在 $ \mathbf A^\prime,\mathbf B^\prime $ 上计算，而它们要比 $ \mathbf A,\mathbf B $ 短得多，因此可以显著加速 DTW 的计算速度。

3. 优化二：降低成对节点相似性计算的数量。

   在第 $ k $ 层，显然没有必要计算每对节点的相似性。考虑degree 相差很大的一对节点（如degree=2 和 degree=20 ），即使在 $ k=0 $ 层它们的结构距离也很大。由于节点之间的结构距离随着 $ k $ 的增大而增大，因此当 $ k\gt 0 $ 时它们的结构距离更大。因此这样的一对节点在 $ \mathcal M $ 中的边的权重很小，则随机游走序列不太可能经过这种权重的边，因此在 $ \mathcal M $ 中移除这类边不会显著改变模型。

   我们将每一层需要计算结构相似性的节点数量限制为：每个节点最多与 $ O(\log n) $ 个节点计算相似性。令节点 $ u $ 需要计算相似性的邻居节点集合为 $ \mathcal J_u $ ，则 $ \mathcal J_u $ 需要包含那些在结构上和 $ u $ 最相似的节点，并且应用到所有 layer 。

   我们选取和 $ u $ 的 degree 最相似的节点作为 $ J_u $ ：

   • 首先对全网所有节点的有序 degree 序列进行二分查找，查找当前节点 $ u $ 的 degree。
   • 然后沿着每个搜索方向（左侧、右侧）获取连续的 $ \log n $ 个节点。

   计算 $ \mathcal J_u $ 的计算复杂度为 $ O(n\log n) $ ，因为我们需要对全网节点根据 degree 进行排序。现在 $ \mathcal M $ 每一层包含 $ O(n\times \log n) $ 条边 ，而不是 $ O(n^2) $ 条边。

4. 优化三：降低层的数量。

   $ \mathcal M $ 中的层的数量由网络直径 $ k^* $ 来决定。然而，对于许多网络，直径可能远远大于平均距离。此外，实际上当 $ k $ 的值足够大时，评估两个节点之间的结构相似性就没有任何意义。因为当 $ k $ 接近 $ k^* $ 时， $ \mathbf S(\mathcal R_k(u)) $ 和 $ \mathbf S(\mathcal R_k(v)) $ 这两个序列都非常短，这使得 $ f_k(u,v) $ 和 $ f_{k-1}(u,v) $ 几乎相等。

   当 $ k $ 较大时，和目标节点 $ u $ 或 $ v $ 距离刚好为 $ k $ 的环非常稀疏。

   因此我们可以将 $ \mathcal M $ 的层的数量限制为一个固定的常数 $ k^\prime \lt k^* $ ，从而仅仅采用最重要的一些层来评估结构相似性。这显著减少了构建 $ \mathcal M $ 的计算需求和内存需求。

5. 尽管上述优化的组合会影响节点的结构embedding，但是我们实验证明：这些优化的影响是微不足道的，甚至是有益的。因此降低模型计算量和内存需求的好处远远超出了它们的不足。最后，我们还提供了 struc2vec 的源代码：https://github.com/leoribeiro/struc2vec。

13.2 实验

13.2.1 杠铃图

1. 我们定义 $ B(h,k) $ 为 (h,k)-barbell 图：

   • 杠铃图包含两个完全图 $ \mathcal K_1 $ 和 $ \mathcal K_2 $ ，每个完全图包含 $ h $ 个节点。
   • 杠铃图包含一个长度为 $ k $ 的路径 $ \mathbf P $ ，其节点记作 $ \{p_1,\cdots,p_k\} $ ，该路径连接两个完全图。
   • 两个节点 $ b_1\in \mathcal V(\mathcal K_1) $ 和 $ b_2\in \mathcal V(\mathcal K_2) $ 作为 bridge ，我们连接 $ b_1 $ 到 $ p_1 $ 、 $ b_2 $ 到 $ p_k $ 。

   杠铃图中包含大量结构身份相同的顶点。

   • 定义 $ \mathcal C_1=\mathcal V(\mathcal K_1)- \{b_1\}, \mathcal C_2=\mathcal V(\mathcal K_2)-\{b_2\} $ ，则所有的节点 $ v\in \{\mathcal C_1\cup \mathcal C_2\} $ 为结构等价的。
   • $ \{p_i,p_{k-i}\},1\le i\le k-1 $ 顶点对之间也是结构等价的。
   • $ \{b_1,b_2\} $ 这对bridge 也是结构等价的。

   下图给出了 $ B(10,10) $ 杠铃图，其中结构等价的顶点以相同的颜色表示。

   

2. 我们期望 struc2vec 能够学习捕获上述结构等价的节点 representation 。结构等价的每个节点都应该具有相似的潜在 representation。此外，学到的 representation 还应该捕获结构层次 structural hierarchy：虽然节点 $ p_1 $ 和节点 $ p_2,b_1 $ 不等价，但是我们可以清楚地看到，从结构的角度来看，节点 $ p_1 $ 和 $ p_2 $ 更相似（它们的 degree 更接近）。

   我们使用 DeepWalk,node2vec,struc2vec 等模型学习杠铃图中节点的 embedding 。这些模型都采用相同的参数：每个节点开始的随机游走序列数量 20、每条游走序列长度 80、SkipGram 窗口大小为5 。对于 node2vec 有 $ p=1,q=2 $ 。

   下图给出了各模型针对 $ B(10,10) $ 杠铃图学到的 embedding 。

   • DeepWalk 无法捕获结构等价性。这是符合预期的，因为 DeepWalk 并不是为结构等价性而设计的。

   • node2vec 也无法捕获结构等价性。实际上它主要学习图距离 graph distance，将图中距离相近的节点放到 embedding 空间中相近的位置。node2vec 的另一个限制是：SkipGram 的窗口大小使得 $ \mathcal K_1 $ 和 $ \mathcal K_2 $ 中的节点不可能出现在相同的上下文中。

     DeepWalk 也存在这样的问题。

• struc2vec 能够学到正确分离的等效类别 embedding ，从而将结构等价的节点放在embedding 空间中相近的位置。例如， $ p_1 $ 和 $ p_{10} $ 靠近 $ \mathcal K_1 $ 和 $ \mathcal K_2 $ 中节点的 representation，因为它们是 bridge 。

  我们提出的三个优化并未对 embedding 的质量产生任何重大影响。实际上“优化一”的 embedding 中，结构等价的节点甚至更加靠近。

  • 图b 给出了 RolX 的结果。模型一共确定了六个角色（从左到右依次编号为 0 ~ 5 ），其中一些角色精确地捕获了结构等价性（角色 1 和 3）。然而，结构上等价的节点（在 $ \mathcal K_1 $ 和 $ \mathcal K_2 $ 中）被放置在三个不同的角色（角色 0,2,5）中，而角色 4 包含路径中的所有剩余节点。因此，尽管 RolX 在为节点分配角色时确实捕获了一些结构等价性的概念，但 struct2vec 更好地识别和分离了结构等价性。

  

13.2.2 Karate 网络

1. Zachary's Karate Club 是一个由34 个节点、78 条边组成的网络，其中每个节点代表俱乐部成员、边表示两个成员是否在俱乐部以外产生互动，因此边通常被解释为成员之间的好友关系。

   我们的网络由该网络的两个拷贝 $ \mathcal G_1,\mathcal G_2 $ 组成，其中 $ u\in \mathcal V(\mathcal G_1) $ 都有一个镜像节点 $ v\in \mathcal V(\mathcal G_2) $ 。我们还通过在镜像节点对 (1,37) 之间添加一条边来连通 $ \mathcal G_1,\mathcal G_2 $ 。尽管 struc2vec 可以建模分离的连通分量，但是 DeepWalk 和 node2vec 无法训练。为了与DeepWalk/node2vec 基准方法进行公平的比较，我们添加了这条边。下面给出了镜像网络，其中结构身份相等的节点采用相同的颜色表示。

   

2. 我们使用 DeepWalk,node2vec,struc2vec 等模型学习镜像图中节点的 embedding 。这些模型都采用相同的参数：每个节点开始的随机游走序列数量 5、每条游走序列长度 15、SkipGram 窗口大小为3 。对于 node2vec 有 $ p=1,q=2 $ 。

   • DeepWalk 和 node2vec 学习的 embedding 可视化结果如下图所示。可以看到，它们都未能在潜在空间中对结构等效的节点进行分组。

   • struc2vec 再次正确地学到能够捕获节点结构身份的特征。镜像节点pair 对在embedding 空间中距离很近，并且节点以一个复杂的结构层级structural hierarchy 聚合在一起。

     例如，节点1 和 34 （及其对应的镜像节点 37 和 42）在网络中具有类似领导者 leader 的角色，struc2vec 成功捕获了它们的结构相似性，即使它们之间不存在边。

     潜在空间中的另一个簇由节点 2/3/4/33 以及它们的镜像节点组成。这些节点在网络中也具有特定的结构身份：它们具有很高的 degree，并且至少连接到一个 leader 。最后，节点 26 和 25 具有非常接近的 representation，这与它们的结构角色一致：二者都具有低 degree，并且距离 leader 34 有 2跳。

     struc2vec 还捕获了 non-trivial 的结构等价性。注意，节点 7 和 50 （粉红色和黄色）映射到潜在空间中靠近的点。令人惊讶的是，这两个节点在结构上是等价的：图中存在一个自同构automorphism将一个节点映射到另一个节点。一旦我们注意到节点 6 和 7 在结构上也是等效的，并且节点 50 是节点 6 的镜像版本（因此在结构上也是等价的），就可以更容易地看到这一点。

   • RolX 一共识别出28 个角色。注意：节点1 和 34 被分配到不同角色中，节点1 和 37 也被分配到不同角色中，而 34 的镜像节点（节点42）被放置在与节点 34 相同的角色中。

     34 对镜像节点pair 对中仅有 7 对被正确分配角色。然而，还发现了一些其它结构相似性。例如，节点 6 和 7 是结构等价的，并且被分配了相同的角色。同样地，RolX 似乎捕获到了节点之间结构相似性的一些概念，但是 struc2vec 可以用潜在 representation 更好地识别和分离结构等价性。

   

   

   

   

3. 我们测量了每个节点和它的镜像节点之间的representation 距离、每个节点和子图内其它节点的representation 距离，下图给出 node2vec 和 struc2vec 学到的embedding 的这两种距离分布。横轴为距离，纵轴为超过该距离的节点对的占比。

   • 对于 node2vec，这两个分布几乎相同。这表明node2vec 并未明显的区分镜像节点pair 对和非镜像节点pair 对，因此 node2vec 无法很好识别结构等价性。

   • 对于 struc2vec，这两个分布表现出明显的差异。94% 的镜像pair 对之间的距离小于 0.25 ，而68% 的非镜像 pair 对之间的距离大于 0.25 。

     此外，非镜像pair 对的平均距离是镜像 pair 对平均距离的 5.6 倍，而node2vec 这一比例几乎为 1 。

   

4. 为了更好地刻画结构距离和 struc2vec 学到的潜在 representation 距离的关系，我们评估所有节点对之间的距离（通过 $ f_k(u,v) $ 来衡量），以及它们在 embedding 空间中的距离（通过欧式距离来衡量）的相关性。我们分别计算 Spearman 相关系数和 Pearson 相关系数，结果如下图所示。

   这两个系数表明：对于每一层这两个距离都存在很强的相关性。这表明 struc2vec 确实在潜在空间中捕获了结构相似性。

   

13.2.3 鲁棒性

1. 为了说明struc2vec 对噪音的健壮性，我们从网络中随机删除边从而直接修改其网络结构。给定图 $ \mathcal G=(\mathcal V,\mathcal E) $ ，我们以概率 $ s $ 随机采样图 $ \mathcal G $ 中的边从而生成新的图 $ \mathcal G_1 $ ，这相当于图 $ \mathcal G $ 的边以概率 $ 1-s $ 被删除。我们使用 $ \mathcal G $ 再次重复该过程从而生成另一个新的图 $ \mathcal G_2 $ 。因此， $ \mathcal G_1 $ 和 $ \mathcal G_2 $ 通过 $ \mathcal G $ 在结构上相关，而 $ s $ 控制结构相关性的程度。注意，当 $ s=1 $ 时， $ \mathcal G_1 $ 和 $ \mathcal G_2 $ 是同构的；当 $ s=0 $ 时，所有的结构身份都丢失了。

   我们从 Facebook 网络中随机采样，该网络包含 224 个节点、3192 条边，节点 degree 最大为 99 最小为 1 。我们采用不同的 $ s $ 来生成两个新的图 $ \mathcal G_1 $ 和 $ \mathcal G_2 $ ，我们重新标记 $ \mathcal G_2 $ 中的节点从而避免 $ \mathcal G_1 $ 和 $ \mathcal G_2 $ 中存在相同编号的节点。我们将 $ \mathcal G_1 $ 和 $ \mathcal G_2 $ 的并集视为我们框架的输入网络。注意，合并后的图至少有两个连通分量（分别对应于 $ \mathcal G_1 $ 和 $ \mathcal G_2 $ ），并且 $ \mathcal G_1 $ 中的每个节点在 $ \mathcal G_2 $ 中都有对应的镜像。

   下图给出了不同的 $ s $ 值，struc2vec 学到的所有节点 pair 对之间 embedding 的距离分布。其中 x 标记的是镜像节点 pair 对之间的距离，+ 标记的是所有节点 pair 对之间的距离。

   • 当 $ s=1 $ 时，两个距离分布明显不同。所有节点pair 对之间的平均距离要比镜像节点 pair 对之间的平均距离大 21 倍。

   • 当 $ s=0.9 $ 时，两个距离分布仍然非常不同。进一步减小 $ s $ 不会显著影响所有节点 pair 对的距离分布，但是会缓缓改变镜像节点pair 对的距离分布。

   • 即使在 $ s=0.3 $ 时，这意味着原始边同时出现在 $ \mathcal G_1 $ 和 $ \mathcal G_2 $ 中的概率为 0.09，struc2vec 仍然会将镜像节点pair 对进行很好的区分。

     这表明即使在存在结构噪音（通过随机移除边）的情况下，struc2vec 在识别结构身份方面仍然具有很好的鲁棒性。

   

   

13.2.4 分类任务

1. 网络节点潜在 representation 的一个常见应用是分类。当节点 label与其结构身份相关时，可以利用 struc2vec 来完成节点分类任务。为了说明这种潜力，我们考虑一个空中交通网络。空中交通网络是一个无权无向图，每个节点表示机场，每条边表示机场之间是否存在商业航班。我们根据机场的活跃水平来分配label，其中活跃水平根据航班流量或者人流量为衡量。

2. 数据集：

   • 巴西空中交通网络Brazilian air-traffic network ：包含 2016年1月到2016年12月从国家民航局 ANAC 收集的数据。该网络有131个顶点、1038条边，网络直径为5。机场活跃度是通过对应年份的着陆总数与起飞总数来衡量的。
   • 美国空中交通网络American air-traffic network ：包含 2016年 1 月到 2016 年 10 月从美国运输统计局收集的数据。该网络有 1190 个顶点、13599 条边，网络直径为 8 。机场活跃度是通过对应年份的人流量来衡量的。
   • 欧洲空中交通网络European air-traffic network ：包含 2016 年 1 月到 2016 年 11 月从欧盟统计局收集的数据。该网络包含 399 个顶点、5995 条边，网络直径为 5 。机场活跃度是通过对应年份的着陆总数与起飞总数来衡量的。

   对于每个机场，我们将其活跃度的标签分为四类：对每个数据集我们对活跃度的分布进行取四分位数从而分成四组，然后每一组分配一个类别标签。因此每个类别的样本数量（机场数量）都相同。另外机场类别更多地与机场角色密切相关。

3. 我们使用 struc2vec 和 node2vec 来学习每个网络的顶点 embedding ，其中我们通过 grid search 来为每个模型选择最佳的超参数。注意，该步骤不使用任何节点标签信息。

   然后我们将学到的embedding 视为特征来训练一个带 L2 正则化的 one-vs-rest 逻辑回归分类器。我们还考虑直接将顶点的 degree 作为特征来训练一个逻辑回归分类器，从而比较使用原生特征和embedding 特征的区别。因为节点的 degree 捕获了一个非常基础basic 的结构身份概念。

   由于每个类别的规模相同，因此我们这里使用测试准确率来评估模型性能。我们将分类模型的数据随机拆分为80% 的训练集和 20% 的测试集，然后重复实验10 次并报告平均准确率。

   结论：

   • struc2vec 模型学到的 embedding 明显优于其它方法，并且其优化几乎没有产生影响。对于巴西网络，struc2vec 相比 node2vec，其分类准确率提高了 50% 。
   • 有趣的是，在巴西网络中，node2vec 模型学到的 embedding 的平均性能甚至略低于直接使用节点 degree，这表明在这个分类任务中，节点的结构身份起到了重要作用。

   

13.2.5 可扩展性

2. 为了说明 struc2vec 的可扩展性，我们将采用优化一、优化二的 struc2vec 应用于 Erd¨os-R´enyi 随机图。我们对每个节点采样10 个随机游走序列，每个序列长度为 80，SkipGram 窗口为 10， embedding 维度为 128 。为加快训练速度，我们使用带负采样的 SkipGram 。

   为评估运行时间，我们在顶点数量从100 到 100万 、平均degree 为 10 的图上训练 struc2vec。每个实验我们独立训练10 次并报告平均执行时间。其中 training time 表示训练 SkipGram 需要的额外时间。

   下图给出了log-log 尺度的训练时间，这表明 struc2vec 是超线性的，但是接近 $ n^{1.5} $ （虚线）。因此尽管struc2vec 在最坏情况下在时间和空间上都是不利的，但是实际上它仍然可以扩展到非常大的网络。

   $ O(\sqrt n\times n) $ 的时间复杂度对于千万级甚至亿级的大型图而言仍然是难以接受的，其计算复杂度是线性复杂度的成千上万倍。