十四、GraphWave

1. 图中不同位置的顶点在其局部网络拓扑中可能具有相似的角色，识别这些角色可以提供对网络结构的关键洞察insight ，并用于各种机器学习任务，包括作为机器学习问题的输入、识别系统中的关键节点（如社交网络中的关键影响者 influencers、传染病扩散图中的关键枢纽hub ）。

   直观的讲，具有相似结构角色的顶点在网络中起到相似的功能。如：公司社交网络中的管理者角色，或者细胞分子网络中的酶的角色。但是顶点的这种结构相似性和传统的顶点相似性概念有很大的不同。传统概念中，认为网络位置相近的顶点是相似的。

   如下图所示，尽管顶点 和 在图中相距甚远，它们具有相似的结构角色。

   

2. 在图上定义顶点的结构角色对应于局部网络邻域的不同拓扑，如链式结构中的顶点、星型结构中的中心、两个簇中间的bridge 等等。但是这些结构角色必须预定义，这需要领域内的专业知识，以及需要人工来对图的结构进行观察inspection 。

   一种更强大的识别结构相似性的方法是：通过无监督学习对每个顶点 学习一个结构embedding 向量 。对于任意 ，如果 则顶点 被定义为 相似的。

   因此这种方法必须引入适当的embedding 方法以及一个合适的距离函数dist() 。

   虽然目前已经有几种方法用于学习图中顶点结构 embedding，但是这些方法对于拓扑中的小扰动极为敏感，并且对所学到的 embedding 的性质缺乏数学上的解释。 并且这些方法依赖于人工手动构建拓扑结构特征，使用non-scalable 的启发式方法，甚至有的方法仅返回单个相似性得分而不是一个结构 embedding 。

   论文《Learning Structural Node Embeddings via DiffusionWavelets》 提出了 GraphWave 方法来解决图的结构学习问题。

   GraphWave 方法采用来自于图信号处理的技术，基于以顶点为中心的谱图小波扩散 spectral graph wavelet diffusion 来学习每个顶点的结构embedding 。直观的看，每个顶点在图上传播一个能量单位，并根据网络的response 来表征其邻域拓扑结构。我们正式证明了该小波系数与图的拓扑特性直接相关，因此这些系数包含了发现顶点相似性的所有信息，从而无需人工构造特征。

3. 根据设计，小波wavelet 是作用在图的局部区域的。因此如果两个顶点相距较远，则它们之间的小波是无法进行比较的。这时需要为每对顶点指定一个一对一的映射，从而使得一对顶点之间的小波可以进行直接比较，如计算相关系数或者计算 距离。

   这种顶点对之间的一一映射计算量太大，因此是难以实现的。所以这些小波方法从未被用于学习结构embedding 。

   为了克服这一调整，GraphWave 提出将小波视为图上概率分布的新颖方法。这样结构信息体现在diffusion 是如何在网络中扩散spread ，而不是扩散到何处。

   我们使用这些小波分布函数的经验特征函数empirical characteristic function 来 embed 这些小波分布，这样可以捕获给定分布的所有矩（包括高阶矩）。

4. 我们从数学上证明了 GraphWave 可以发现结构相似的顶点，并且能够抵抗局部网络结构的微小扰动。

   另外，GraphWave 的计算复杂度是 ，这使得它可以应用到大型（稀疏）网络。

   通过将 GraphWave 和其它几个 state-of-the-art 基准方法在真实数据集和合成数据集上进行比较，GraphWave 取得了最高 137% 的改进。

5. 目前挖掘顶点结构相似性的方法依赖于顶点的人工特征构造，这些方法需要在预先给出每个顶点的局部拓扑属性，如顶点的degree、它参数的三角形数量、k-clique 的数量、PageRank 得分。

   这种方法的一个典型示例是 RolX ，它是一种基于矩阵分解的方法。另一种方法是 struc2vec ，它使用启发式方法基于网络拓扑度量来构建 multi-layer 图，并在multi-layer 图上随机游走从而捕获结构信息。

   与这些方法相比，GraphWave 不依赖于启发式算法，也不需要显式的人工特征工程或者人工参数调整。另外，struc2vec,神经网络指纹, Semi-Supervised GCN 等方法是嵌入整个图，而我们的方法仅仅embed 单个顶点。

6. graph diffusion kernel 图扩散核最近用于各种图的建模任务，GraphWave 是第一个应用图扩散核来确定顶点结构角色的论文。核方法已经被证明可以有效捕获几何属性，并成功应用于各种图像处理任务。但是我们这里的图是高度不规则的（与图像的欧式图相反），因此传统的小波方法不适用。

   GraphWave 这里使用小波来表征扩散的形状而不是扩散的位置，这一关键洞察使得我们能够发现结构embedding 。

14.1 模型

1. 给定无向图 ，其中 为顶点集合， 为边集合。令邻接矩阵为 ，它是二元的或者带权重的。定义度矩阵 ，其中 。

   顶点的结构embedding 问题为：对于每个顶点 ，我们希望在一个连续的多维空间种学得一个 embedding 来表示它的结构角色structural role 。

2. 令 为未归一化的拉普拉斯矩阵，令 为 的特征向量eigenvector 组成的特征矩阵，则有：

   

   其中 ， 为 的特征值eigenvalue 。

   令 为一个scaling 参数为 的滤波器核 filter kernel，这里我们采用热核heat kernel ，但是我们的结论适用于任何类型的 scaling wavelet 。另外，这里我们假设 是给定的，后续会讨论如何选择一个合适的 值。

   图信号处理graph signal processing 将与 相关的谱图小波spectral graph wavelet 定义为：以顶点 为中心的狄拉克信号的频域响应。因此谱图小波 定义为：

   

   其中 是顶点 的 one-hot 向量：顶点 对应的位置为1，其它位置为0 。因此顶点 的第 个小波系数为 ，它是矩阵 的第 行第 列。

   可以看到在谱图小波，核 调试modulate 了特征谱，使得响应信号位于空域的局部区域以及频域的局部区域。

3. 如果我们将拉普拉斯矩阵和信号系统中的时域-频域进行类比，则发现：较小特征值对应的特征向量携带变化缓慢的信息，从而鼓励邻居顶点共享相似的信息；较大特征值对应的特征向量携带迅速变化的信息，从而使得邻域顶点之间区别较大。

   因此低通滤波器核low-pass filter kernel 可以看作是一种调制算子modulation operator ，它降低了较高的特征值并在图中平滑了信号的变化。

14.1.1 算法

1. 我们首先描述 GraphWave 算法，然后对其进行分析。对于每个顶点 ，GraphWave 返回表示其结构embedding 的一个 2d 维度向量 ，使得局部网络结构相似的顶点拥有相似的 embedding 。

2. GraphWave 算法：

   • 输入：

     • 图
     • scale 参数
     • 个均匀分布的采样点 ，它们代表分布的矩的阶数

   • 输出：顶点的结构embedding 向量

   • 算法步骤：

     • 计算拉普拉斯矩阵 ，并进行特征分解：

     • 计算图谱小波

     • 对 ，计算 为 的 column-wise 逐列均值。对于顶点 ，将 的实部和虚部分配给 ，其中 为 的第 个元素。

       每个顶点拼接 个实部虚部，则得到一个 2d 维的向量。

3. 算法中，我们首先应用谱图小波来获取每个顶点的 diffusion 模型，然后收集到矩阵 中，其中第 列的列向量是以顶点 为中心的 heat kernel 产生的谱图小波。

   • 现有的工作主要研究将小波系数视为scaling 参数 的函数，而这里我们将小波系数视为局部网络结构的函数：小波系数随着顶点 的局部网络结构的变化而变化。特别的，每个小波系数都有深刻的物理意义： 表示顶点 从顶点 接收到的能量的大小。

   • 我们将小波系数视为概率分布，并通过经验特征函数来刻画该分布。我们将证明：具有相似网络邻域结构的顶点 和 将具有相似的谱图小波系数分布 和 。

   • 概率分布 的特征函数定义为：

     

     它完全刻画了分布 ，因为它捕获了关于分布 的所有矩的信息。将它进行泰勒展开得到：

     

     给定顶点 和 scale s ， 的经验特征函数定义为：

     

     理论上我们需要计算足够多的点来描述 ，但是这里我们采样了 个均匀间隔的点，即 。最终得到：

     

   • 注意到我们在经验特征函数 上均匀采样了 个点，这创建了一个大小为 的 embedding，因此embedding 的维度和图的大小无关。

4. GraphWave 的输出为图中每个顶点的结构嵌入。我们可以将结构嵌入之间的距离定义为 距离，即顶点 和 之间的结构距离定义为：

   

   根据特征函数的定义，这相当于在小波系数分布上比较不同阶次的矩。

5. scaling 参数 确定每个顶点 周围的网络邻域的半径。较小的 会使用较小半径的邻域来确定顶点的结构嵌入；较大的 会使得扩散过程在网络上传播得更远，从而导致使用较大半径得邻域来确定顶点的结构嵌入。

   GraphWave 还可以采用 的不同取值来集成多尺度结构embedding ，这是通过串联 个不同的 embedding 来实现的，每个embedding 都和一个scale 相关，其中 。我们接下来提供一个理论上的方法来找到合适的 。

   在多尺度版本的 GraphWave 中，最终顶点 聚合的结构embedding 为：

   

6. 我们使用切比雪夫多项式来计算 ，拉普拉斯算子的每个幂具有 的计算成本，从而产生 的整体计算复杂度，其中 表示切比雪夫多项式逼近的阶数。

   因此 GraphWave 的整体计算复杂度是 的线性的，这使得 GraphWave 可以扩展到大型稀疏网络。

14.1.2 理论分析

1. 我们首先通过理论分析表明：谱图小波系数表征了局部网络领域的拓扑结构。然后我们理论上证明：结构等价/相似的顶点具有几乎相等/近似的embedding 。我们从数学上证明了 GraphWave 的理论正确性。

2. 我们首先建立顶点 的谱图小波和顶点 的局部网络结构之间的关系。

   由于图拉普拉斯算子的谱是离散的，并且位于区间 之间，根据 Stone-Weierstrass 定理可知：核 在区间 上可以通过一个多项式来逼近。记这个多项式为 ，则这个多项式逼近是紧的 tight，其误差是一致有界的 uniformaly bounded 。即：

   

   其中 为多项式逼近的阶数， 为多项式系数， 为残差。

   我们可以将顶点 的谱图小波以多项式逼近的形式重写为：

   

   由于 是单位正交矩阵， 是一致有界的，因此我们可以通过Cauchy-Schwartz 不等式将等式右侧的第二项进行不等式变换 ：

   

   其中等式左边为 的第 个元素， （因为 为单位正交矩阵）， 以及：

   

   因此 可以由一个 阶多项式逼近，该多项式捕获了有关顶点 的 阶邻域信息。这表明谱图小波主要受到顶点的局部拓扑结构影响，因此小波包含了生成顶点结构embedding 所必须的信息。

3. 然后我们证明局部邻域结构相同的顶点具有相似的 embedding 。

   假设顶点 和 的 阶邻域相同，其中 是一个小于图的直径的整数。这意味着顶点 和 在结构上是等价的。

   我们首先将 根据泰勒在零点展开到 阶：

   

   然后对于每个特征值 ，我们使用Taylor-Lagrange 等式来确保存在 ，使得：

   

   如果我们选择 使得满足：

   

   则可以保证绝对残差 对于任意 成立。这里 是一个参数，可以根据结构等效的顶点的embedding 期望的接近程度来指定，因此也称作 。另外 越小则可以选择 更小，使得上界越紧。

   由于顶点 和 的邻域是相同的，因此存在一个one-to-one 映射 ，它将 的 阶邻域 映射到 的 阶邻域 ，使得 。通过随机映射剩余的顶点（ 的 阶邻域以外的顶点），我们将 作用到整个图 上。

   利用图拉普拉斯矩阵的 阶多项式近似，我们有：

   

   • 考虑第二行的第一项。由于顶点 和 的 阶邻域是等价的，则有：

     

     因此这一项可以约掉。

   • 考虑第二行的第二项、第三项。使用前面的残差分析可以得到它们都有一个一致的上界 ，因此有：

     

     即： 中的每个小波系数和它对应的 中的小波系数的距离不超过 。

     考虑到我们使用经验特征函数来描述分布，因此这种分布的相似性就转换为embedding 的相似性。因此如果选择合适的 scale ，则结构上等效的顶点具有 相似的embedding 。

4. 接着我们证明局部邻域结构相似的顶点具有相似的 embedding 。

   设顶点 的 阶领域为 ， 为顶点 的一个扰动的 阶邻域，这是通过对顶点 的原始 阶邻域重新调整边来得到。

   假设扰动后的图拉普拉斯矩阵为 ，接下来我们证明：如果顶点邻域的扰动很小，则顶点的小波系数的变化也很小。

   假设扰动很小，即： 。我们使用核 的 阶泰勒在零点展开来表示扰动图的小波系数：

   

   我们使用 Weyl 定理将图结构中的扰动与图拉普拉斯算子的特征值变化联系起来。特别地，图的小扰动导致特征值的小扰动。即，对于每个 ， 和原始的 接近：

   

   其中 表示 的一个无穷小量， 为一个常数。

   综合所有因素，则有：

   

   因此在GraphWave 中，结构相似的顶点具有相似的 embedding 。

14.1.3 scale 参数

1. 我们开发了一个自动的方法来为heat kernel 中的 scale 参数 找到合适的取值范围，该方法将在 GraphWave 的多尺度版本中使用。我们通过分析heat diffusion 小波的方差来指定 和 来作为区间边界。

   直观来看，较小的 值使得热传播的时间较短，从而使得热扩散的小波分布没有意义，因为此时只有很少的几个小波系数是非零，绝大多数小波系数都是零。较大的 值使得热传播的时间较长，热扩散的小波分布也没有意义，因为此时网络收敛到所有顶点都处于能量为 的同温状态。

   这里我们证明两个命题，从而为热扩散小波分布的方差和收敛速度提供洞察insight。然后我们使用这些结论来选择 和 。

2. 命题一：热扩散小波 中非对角线的系数的方差与以下指标成正比：

   

   其中 随着 的增加单调递减。这是因为 ，它随着 的增加单调递减。

   证明：令小波 的非对角线系数均值为 。考虑到 为一个概率分布，因此有 。

   根据方差的定义有：

   

3. 命题一证明了小波系数的方差是 的函数，因此为了最大化方差我们必须分析 。为了确保小波系数的分布具有足够大的容量（即分布的多样性足够大），我们需要最大化方差。

   因此我们选择区间 来使得 足够大，从而使得diffusion 既有足够长的时间来扩散、又不至于太长以至于到达网络的收敛状态（所有顶点的温度都相同）。

4. 命题二：热扩散小波系数 的收敛上下界为：

   

   证明：对于非负的 有：

   

   注：这里的证明存疑，但是原始论文并未给出解释。

   对应的有：

   

   因此有：

   

   对于任意的 ，我们采用数学归纳法可以证明有：

   

   由于 是 的连续递增函数，因此我们选择大于等于零且满足条件的 进行向下、向上取整。

5. 选择 ：我们选择 使得小波系数被局限在局部邻域上。因此我们限定：

   

   其中 。这确保了 最多下降到初始值 的 。理论上如果 足够大则所有顶点温度相同，则 。

   根据命题二有：

   

   令 ，其中 ，则有： 。即 。

   • 参数越接近1 ，则传播时间越短， 越小。
   • 参数越接近0，则传播时间越长，则 越大。

   现在考虑 。当大部分特征值趋近于 时， 逼近于 ；当大部分特征值趋近于 时， 逼近于 。为找到这两种收敛情况之间的中间状态，我们将 设置为 和 的几何平均值。与算术平均值相反，几何平均值在区间 上保持相等的权重，即 的 的变化和 的 的变化效果相同。因此我们选择 为：

   

6. 选择 ：我们选择 使得每个小波都有足够长的时间来扩散，即限定：

   

   其中 。同样的分析我们有：

   

   其中：

   • 参数越接近1 ，则传播时间越短， 越小。
   • 参数越接近0，则传播时间越长，则 越大。
7. 为覆盖适当的 scale 区间，论文建议设置 以及 。

14.2 实验

1. GraphWave 的 embedding 独立于下游任务，因此我们在不同任务中对其进行评估。

   我们将 GraphWave 和两个结构嵌入的基准方法 struc2vec、RolX 进行评估。struc2vec 通过在 multi-layer 图上的一系列随机游走来发现不同尺度的结构嵌入。RolX 通过基于顶点特征的矩阵（如degree、三角形数量）的非负矩阵分解的方法来描述每个顶点的角色。

   我们还将GraphWave 和其它最新的无监督顶点表示学习方法node2vec、Deepwalk 方法进行比较，以强调结构embedding 方法与这类方法的差异。

2. 对于所有的基准模型，我们使用这些模型的默认参数。对于 GraphWave 模型，我们使用多尺度版本，并设置 ，以及使用 内均匀间隔的采样点 。

14.2.1 杠铃图

1. 杠铃图由两个长链组成的稠密团构成，该图包含 8 个不同类别的结构等效顶点，如图A 的颜色所示。

   我们通过PCA 可视化了不同模型学到的embedding ，相同的 embedding 具有相同的投影，这使得图 B~D 上的点发生重叠。

   • 从图D 可以看出， GraphWave 可以正确学习结构等效顶点的embedding，这为我们的理论提供了支撑（相同颜色的顶点几何完全重叠）。

     相反，struc2vec 和 RolX 都无法准确的识别结构等效性（相同颜色的顶点并未重叠）。

   • 所有方法都能识别稠密团的顶点（紫色）的结构，但是只有GraphWave 能够准确识别链上顶点的结构角色。

   

14.2.2 结构等效图

1. 我们在合成的图上评估这些方法。我们开发了一个程序来生成合成图，这些合成图可以植入结构等价的子图，并且给出每个顶点角色的真实标签。我们的目的是通过这些真实的角色标签来评估这些方法的性能。

   我们的合成图由不同类型的基础形状给出，这些形状类型包括 house,fan,star。我们一共评估四种网络结构配置：

   • 在 house 配置中，我们选择将4 个 house 放置在一个长度为 30 的圆环上。
   • 在 varied 配置中，我们对每个类型的形状选择8 个，并随机放置在一个长度为 40 的圆环上，从而生成具有更丰富、更复杂结构角色的合成图。
   • 在 noise 配置中，我们随机删减边来增加扰动（最多 10% ），从而评估house perturbed, varied perturbed 的鲁棒性。

   我们对这四种网络结构 house, varied, house perturbed, varied perturbed 分别构造一个图，然后在这些构造的图上运行不同方法来得到顶点 embedding 。

2. 我们通过两种策略来评估每个embedding 算法的性能：

   • 无监督评估策略：我们评估每种embedding 方法将具有相同结构角色的顶点嵌入到一起的能力。我们使用 agglomerative 聚类算法（采用 single linkage ）来对每种方法学到的 embedding 进行聚类，然后通过以下指标来评估聚类质量：

     • 同质性 homogeneity：给定聚类结果的条件下，真实结构角色的条件熵。它评估聚类结果和真实结果的差异。

     • 完整性 completeness：在所有真实结构角色相等的顶点中，有多少个被分配到同一个聚类。即评估聚类结果的准确性。

     • 轮廓系数 silhouette score ：它衡量样本聚类的合理性。

       对于样本 ，假设它到同簇类其它样本的平均距离为 ，则 越小说明该样本越应该被聚到本簇，因此定义 为簇内不相似度。

       假设它到其它簇 的平均距离为 ，则定义簇间不相似度为 。

       定义轮廓系数为：

       

       当 越接近 1 ，则说明样本 聚类合理；当 越接近 -1 ，则说明样本 聚类不合理。

   • 监督评估策略：我们将学到的顶点 embedding 作为特征来执行顶点分类，类别为顶点的真实结构角色。

     我们使用kNN 模型，对所有样本进行10 折交叉验证。对于测试集的每个顶点，我们根据它在训练集中最近邻的 4 个顶点来预测该顶点的结构角色，其中”近邻” 是通过 embedding 空间的距离来衡量。

     最终我们给出分类的准确率和 F1 得分作为评估指标。

   所有两种策略的每个实验都重复执行25 次，并报告评估指标的均值。

3. 模型embedding 的效果比较如下图所示。

   • 所有实验中，node2vec、DeepWalk 的效果都很差。这是因为这两个方法的重点都是学习顶点的邻近关系，而不是顶点的结构相似性。
   • GraphWave 的效果始终优于 struc2vec 。
   • 虽然 RolX 在部分实验中效果强于 GraphWave，但是 GraphWave 整体效果较好。
   • 轮廓系数silhouette score 表明：GraphWave 发现的簇往往更聚集并且簇之间的间隔更好。

   

4. 我们将GraphWave 学到的 embedding 进行可视化，这提供了一种观察顶点之间结构角色差异的方法。

   如图 A 表示一个带 house 的环，图B 是它的 GraphWave 学到的 embedding 的 2 维PCA 投影。这证明了 GraphWave 可以准确区分不同结构角色的顶点。

   图 C 给出了特征函数 ，不同颜色对应不同结构角色的顶点。其物理意义为：

   • 位于图图外围的顶点难以在图上扩散信号，因此派生出的小波具有很少的非零系数。因此这类顶点的特征函数是一个较小的环状曲线。
   • 位于图核心上的顶点趋向于将信号扩散得更远，因此这类顶点的特征函数是一个较大的环状曲线。

   

14.2.3 跨图的泛化

1. 我们分析embedding 如何识别位于不同图上的顶点的结构相似性，这是为了评估embedding 能否识别跨图的结构相似性。

2. 我们通过以下过程来生成 200 个具有真实顶点结构角色标签的图。

   • 首先以 0.5 的概率来选择环形图或者链式图，从而确定了图的骨架。
   • 然后通过均匀随机选择环的大小或者链的长度来决定骨架的大小。
   • 最后随机选择一定数量的小图挂载到骨架上，这些小图以 0.5 的概率从 5 个顶点的 house 或者 5 个顶点的chain 中选取。

   为了在噪音环境中评估embedding 方法，我们还在顶点之间随机添加10 个随机边，然后训练每个顶点的 embedding 。接着用学到的 embedding 来预测每个顶点的真实结构角色。

3. 为了评估每个方法在跨图上的泛化能力，我们使用10 折交叉验证，并且对于测试集中的顶点我们选择训练集中和它最近邻（通过embedding 来计算距离）的4 个邻居顶点来预测该测试顶点的标签。注意：所选择的4 个邻居顶点可能位于不同的图上。

   最后我们评估预测的准确率和 F1 得分，评估结果如下。结果表明：

   • GraphWave 方法均优于所有其它方法，这表明了 GraphWave 具有学习结构特征的能力，这种结构特征对于不同的图都有重要意义。
   • 基于结构相似性的 embedding 方法要优于基于邻近关系的embedding 方法。

   

14.2.4 可扩展性和鲁棒性

1. 为评估GraphWave 的可扩展性我们逐渐扩大了合成图的顶点数量，我们给出了这些合成图上运行GraphWave 的时间和顶点数量的关系，如下图所示。

   • GraphWave 得训练时间是边数量得线性函数，因此它是一种快速算法。

   • GraphWave 的潜在瓶颈是通过经验特征函数将小波系数的分布转换成 embedding 向量。

     这里利用了小波系数的稀疏性。小波系数通常是稀疏的，因为GraphWave 通过合理的选择 scale 参数 使得小波不会被传播得太远。这总稀疏性可以降低embedding 过程得计算量，因为这里是一组稀疏矩阵相乘，并且逐元素函数应用到非零元素上。

   • struc2vec 无法应用到大图上，对于仅包含 100 个顶点的图，它都需要高达260 秒来学习顶点的 embedding 。

   • RolX 可以扩展到类似大小的图上。

   

2. 接下来我们评估GraphWave 对噪音的鲁棒性。我们将噪音采取与 varied perturbed 相同的方式注入到图中，噪音水平由随机扰动的边占原始边的百分比给出。

   对于每个图，我们首先使用 GraphWave 学习顶点embedding，然后使用 affinity propagation 聚类算法对embedding 进行聚类。最后我们根据顶点的真实结构角色来评估聚类质量。

   除了同质性、完整性指标之外，我们还报告检测到的聚类的数量，从而衡量 GraphWave 发现的角色的丰富程度，我们随机运行10 次并报告平均结果。

   结果如下图所示。结果表明：即使存在强烈的噪音，GraphWave 的性能也是逐渐平滑地降低。

   

14.2.5 真实数据集

1. 我们考虑对安然公司员工之间的电子邮件通信网络进行学习，由于公司存在组织架构，因此我们预期结构GraphWave 能够学到这种工作职位上的结构等效性。

   该网络中每个顶点对应于安然的员工，边对应于员工之间的email 通信。员工的角色有七种，包括CEO、总裁 president、经理 manager 等。这些角色给出了网络顶点的真实标签。

   我们用不同模型学习每个顶点的 embedding，然后计算每两类员工之间的平均 L2 距离，结果如下所示。

   • GraphWave 捕获到了安然公司的复杂组织结构。如 CEO 和总裁在结构上与其它角色的距离都很远。
   • struc2vec 的结果不太成功，每个类别之间的距离几乎均匀分布。

   

   

2. 接下来我们分析一系列航空公司网络。我们考虑刘家在欧洲机场之间运营的航空公司：四家商业航空公司、两家货运航空公司。每家航空公司对应一个Graph，其中顶点表示机场/目的地、边表示机场之间的直飞航班。

   这里一共有 45 个机场，我们对其标记为枢纽机场hub airport、区域枢纽、商业枢纽、重点城市等几个类别，这些类别作为顶点的真实结构角色。

   对每个Graph我们学习图中每个机场的 embedding，然后将来自不同Graph 的同一个机场的 embedding 进行拼接，然后使用 t-SNE 可视化。我们还将拼接后的 embedding 作为 agglomerative 聚类的输入，然后评估同质性、完整性、轮廓系数。

   结果如下所示：

   • struc2vec 学习的 embedding 捕获了不同的航空公司，可以看到各航空公司的顶点几乎各自聚在一起。

     这表明struc2vec 无法在不同的航空公司网络之间泛化，因此无法识别那些结构等效、但是不属于同一个航空公司的机场。

   • RolX 学到的 embedding 的 t-SNE 投影几乎没有任何明显的模式。

   • GraphWave 可以学到顶点的结构等效性，即使这些顶点位于不同的图上。这表明 GraphWave 能够学到针对真实世界网络有意义的结构嵌入。

   • 从上表可以看到，GraphWave 在聚类的所有三个指标上都优于其它方法。