模式感知的SchemaWalk：一种用于异构图嵌入的随机游动方法

1157→→SchemaWalk：异构图嵌入的模式感知随机游动艾哈迈德·E. Samyaesy@kth.se瑞典斯德哥尔摩皇家理工学院泽卡利亚斯凯法托zekarias@kth.se瑞典斯德哥尔摩皇家理工学院摘要异构信息网络（HIN）嵌入已经成为一种流行的方法来学习语义丰富的异构网络的表示。大多数HIN嵌入方法利用元路径来保留高阶结构，然而，它们的性能取决于（生成/手动定义的）元路径的质量及其对特定标签集的适用性而其他方法调整随机游走以利用或跳过某些异质结构（例如，节点类型），在这样做时，经调整的随机游走器可以随意地省略其它节点/边类型。我们的关键见解是，在没有领域知识的情况下，随机游走器不应该对异质结构（即，边缘类型）。因此，为了获得一种灵活通用的方法，我们利用网络模式作为HIN的唯一蓝图，并提出了SchemaWalk，一种随机行走，以均匀地采样网络模式中的所有边缘类型。此外，我们确定的饥饿现象，诱导随机游走在HIN下或过采样某些边缘类型。因此，我们设计SchemaWalkHO来跳过局部不足的连通性，以保持均匀的采样分布。最后，我们对四个真实世界的HIN进行了节点分类实验，并提供了深入的定性分析。结果突出了我们的方法的鲁棒性，无论图形结构与最先进的基线相比CCS概念• 知识表示与推理;无监督学习;信息系统;社会网络;关键词异构信息网络;表示学习;随机游走;网络嵌入本作品采用知识共享署名国际协议（Creative Commons AttributionInternational）授权4.0许可证。WWW©2022版权归所有者/作者所有。ACM ISBN978-1-4503-9130-6/22/04。https://doi.org/10.1145/3487553.3524728洛多维科·贾雷塔vico@kth.se瑞典斯德哥尔摩皇家理工学院萨尔乌纳斯·吉尔·齐尧斯卡斯sarunasg@kth.se瑞典斯德哥尔摩皇家理工学院ACM参考格式：Ahm edE. 作者：Samy，L od ovicoGia retta，ZekariasT. Kefato，andŠaru<$nasGi rdzi-jauskas. 2022年SchemaWalk：用于异质图嵌入的模式感知随机游动在网络会议2022（WWW '22同伴）的同伴程序，2022年4月25日至29日，虚拟活动，里昂，法国。 ACM ， 美国纽约州纽 约 市 ， 10 页 。https://doi.org/10.1145/3487553.35247281引言今天的大部分 它是以网络的形式构建的--从社交网络到基因组和蛋白质网络。网络嵌入已经成为一种无处不在的方法，用于将节点投影到密集空间中，以捕获网络的底层结构[5]。 嵌入可以在自动化预测和下游任务中有用，例如节点分类和个性化推荐。随机游走被广泛采用来探索网络中邻近的节点[5，17，21]。为了学习节点嵌入，SkipGram模型[12]通常被训练为在随机游走的滑动上下文窗口内推断同现节点。有偏随机游走也被提出来探索复杂的现象，如社区和角色等价[4]。这些方法可以在同构网络上学习有用的表示然而，它们不太适合异构网络，例如图1（a）中的网络，其中预期有多个节点和边缘类型，因为它们不注意这些异构结构。对于异构信息网络（HIN），一种广泛的嵌入方法是通过元路径引导随机游走[2，18];元路径是具有可识别语义含义的关系的复合集合。例如，在图1（b）中，A-P-A元路径表示两个作者之间的合作，而A-P-V-P-A连接了在同一地点发表并可能共享研究兴趣的两个作者。 选择最佳的Meta路径在时间和质量方面仍然是一个公开的挑战。元路径的选择通常需要领域知识，并且可以是特定于任务的[9]。 一些现有的方法承诺自动提取所有短于固定长度的元路径的策略[3，18]。然而，元路径的数量可以随着它们的长度或节点类型的数量的增加而呈指数增长。在任何一种情况下，结果都可以在很大程度上取决于所选择的长度[8]或预定义元路径的质量或者，已经提出了不同的调整随机游走策略来对所有节点类型进行平等采样[9]。但我们注意到，在这样做的时候，WWW萨米，吉亚雷塔，凯法托，吉吉亚乌斯卡斯1158AR→≪|R||R|：d→ R ARTG（AR）（）下一页−=D.LL+LL+（）lL +（）（）T（）G0， 否则。Al，Al+1LL+1随机游走可能忽略一些关键的语义结构，诸如图1（b）中的协作交互A-P-A。此外，因为它们的采样面向节点类型，所以在某些场景中，随机遍历器可以选择不对特定节点类型进行采样-意外地丢弃其他节点和边缘类型邻居。我们观察到，HIN嵌入方法与有效地捕获高阶语义（例如，元路径）。我们的核心观点是，在没有关于边和节点类型的重要性的知识的情况下，随机行走器在探索异质结构时不应该持有因此，我们选择网络模式作为HIN的元模板[24]。如图1（c）所示，HIN的网络模式是具有所有节点和边类型的最小元图为此，我们首先提出了SchemaWalk，一个灵活的HIN随机游走我们的想法是调整随机游走，以减轻探索网络模式时的偏差。准确地说，我们的目标是边缘类型之间的均匀采样分布。 为了实现所需的分布，步行者做出下一个应该采样的边缘类型的概率选择。通过调整指数衰减函数，我们可以控制在探索网络模式时实现的一致性程度;因此，SchemaWalk可以被概念化为探索HIN的一般方法。其次，我们确定了饥饿现象，这可能会影响异构网络上的随机游走。当某些边类型在图中不常见或不均匀分布时，可能会发生饥饿。因此，SchemaWalk和类似的方法可能会在每个局部上下文中对它们进行欠采样或过采样，从而可能导致学习效果不佳的表示。因此，我们提出了SchemaWalkHO，其中随机步行者可以跳过直接邻居，以达到欠采样的边缘类型。我们的主要贡献突出如下：我们提出了SchemaWalk，一个灵活的概念随机行走的HIN。SchemaWalk是一种基于网络模式的原理性通用嵌入算法，图1：学术异构信息网络（HIN）。类型映射E：哪里 和 分别是节点类型集和边类型集，G是HIN，当 +> 2.否则，它被称为同构信息网络。在2.2上完成。网络架构。给定HING=V，E，网络模式是一个图 = 、 图G的所有节点类型和边类型分别作为图G的节点和边。在2.3上完成 异构网络嵌入。 给定HIN G =（V，E，A，R），对于每个节点v ∈ V，目标是学习d维连续嵌入fVR，其中d表示网络中节点v的结构和语义。3异构网络嵌入方案3.1使用SchemaWalk进行受路径排序算法（PRA）[11]的启发，我们定义了以下转移概率：交互，并减轻选择元路径的困境• 我们强调了基于节点类型的采样的缺点，PAl，AL+11Al，Al+1MAl，AL+1、（1）建议边缘类型为基础的采样作为一个灵活的，更其中M是边类型R=（A，A）的邻接矩阵我们确定了饥饿问题，并提出SchemaWalkHO来缓解它。 通过跳得比紧邻的更远，SchemaWalkHO可以跳过局部缺乏连接的模式，并保留所需的采样分布。我们在几个真实世界的数据集上评估了所提出的多标签分类方法，并进一步提供了详细的定性分析。结果显示了SchemaWalk的健壮性，它实现了最佳到第二佳的性能，而不管在类型A1的节点和类型A1 +1的节点之间。 DA1，A1 +1是定义为de<$A，A1vi=jMA，A1vi，vj的阶矩阵.因此，PA，A1 vi，vj是访问类型A1的节点vi的随机游走器接下来将选择类型A1 +1的节点vj的概率。为了指导基于SchemaWalk的随机游走的行为，我们首先定义选择下一条边类型的概率（i+1）.Pr（i+1）=R |（v）zi+1（R），R=（n（vi），A），A∈NTG（vi）图结构，与基线形成对比i0，否则，（二更）2问题定义在这里，我们提供了关键概念来制定异构网络嵌入问题，与以前的研究一致[19]。在2.1上完成 异构信息网络（HIN）。是一个图G =（V，E），其中V和E分别是顶点集和边集。给定一个节点类型映射A：V→：A，其中Nvi是节点vi的相邻节点类型，A是下一个节点的类型在选择下一个边类型为R之后，下一个节点按概率选择如下。Pr（vi+1=vj|vi，n（i+1）=R）n.PAl，Al+1（vi，vj），n（vi，vj）=R（三）···探索异构网络的细粒度方法SchemaWalk：异构图嵌入的模式感知随机游动WWW1159−−∈[]（）下一页（）下一页图2：学术图上的SchemaWalk示例α设置为0。1 .一、步行者在节点P2处并且将要从{PP，PA，PV，PT}中选择下一个边类型。灰色节点是下一个过渡的候选节点，具体取决于所选的边类型。下一个节点vj可以从节点vi中选择，其中转移概率定义为等式1，仅当它们通过边类型R连接时。zi是在步骤i处的边类型上的归一化“访问”概率向量。αlRi图3：惩罚节点类型与边缘类型“B-D”被过度采样时的边缘类型其中多个语义上不同的边类型连接同一对节点类型。其次，它更好地处理过采样场景。 图3显示了突出后一个差异的网络模式的理论示例，其中假设边缘类型B D是过采样的。特别地，我们可以在图3（a）中观察到惩罚节点D的基于节点类型的方法，潜在地导致其他节点和边类型（诸如节点类型E和边类型C D）的欠采样。然而，这可以通过惩罚单个边缘类型来避免;如图3（b）所示，其中周围的边缘和节点类型仍然可达，从而降低了欠采样的风险。另一方面，JUST[9]遵循基于节点类型的采样的相当严格的方法具体来说，随机游走器对于最小数目的相同节点类型具有zi（R）R`αlR`i.（四）选择不同的下一个节点类型后的步骤例如，回文元路径（如图1中的A-P-A）不能被采样。因此，JUST可能会错过关键的语义结构。其中lRi是到步骤i为止的边类型R的访问次数，α0， 1。上面的等式定义了SchemaWalk的基本原则，其中遍历器动态地确定要访问的下一个边类型和节点 主要动机是不对异质结构（即，网络模式中的边类型为了实现这一点，SchemaWalk的目标是在边缘类型上实现全局均匀采样分布。详细地说，walker的行为由指数衰减函数αl定义;边类型被访问的次数越多，其采样权重就变得越低。DBLP图上的walker示例如图2所示。此外，α的值决定了当行走展开时随时间衰减的速率。调整α，控制局部上下文窗口内边缘类型之间的均匀性水平;非常小的α导致边缘类型的接近均匀的局部分布当α接近1时，允许个别局部上下文偏斜，但是边缘类型的全局采样保持一致。最后，当一种类型的节点比其他类型的节点多得多时（例如，作者»场地），SchemaWalk可能无法将它们全部作为上下文进行采样。这是SchemaWalk的一个设计属性;与场地相比，作者的数量很大，对所有作者进行采样不应该提供更重要的上下文信息。3.2基于节点与边缘类型的采样模式Walk不同于基于调整后的随机游走的其他HIN嵌入方法，例如JUST[9]或HeteSpaceyWalk[6]，因为它们在节点类型上寻求均匀的采样分布我们认为，均匀采样的边缘类型提供了一个更灵活的探索策略。首先，它可以推广到图3.3不幸的是，在某些类型的数据集上，SchemaWalk可能会遇到饥饿问题。例如，在学术图表中，在图4中，P-V边缘非常罕见，因此随机步行者可能执行大量步骤而没有任何机会访问它们中的任何一P-P边也是如此，它们相对频繁，但主要集中在整个图的一个小子集 在这种情况下，基于Eq. 4，被访问的边类型的权重zR呈指数下降，而缺少的边类型的权重zR长时间不改变。由于这种不平衡，当随机游走器最终遇到代表性不足的边缘类型时，它具有压倒性的机会仅访问该边缘类型几个连续跳，直到ZR分数在某种程度上平衡。因此，它周围的其他边缘类型被忽略，导致倾斜的边缘访问分布和潜在的较差的节点表示。为 了 克 服 上 述 限 制 ， 我 们 提 出 了 SchemaWalkHO ，SchemaWalk的一个变体，它在高阶图上执行随机行走，其中所有合适的边类型都存在于每个节点（例如，在图4的示例中，所有论文都与至少一个地点和至少一个作者相关联）。特别是，我们考虑建立一个加权的，完全连接的图形从原来的稀疏，二进制邻接矩阵的可能性，使用技术，分配更高的权重直接neigh-bours和更接近的节点。 这克服了原始图中边缘的缺乏，同时仍然确保大多数随机行走transi- tions保持局部性。存在几种公知的技术，可以用来构建一个加权的，完全连接的图，WWW萨米，吉亚雷塔，凯法托，吉吉亚乌斯卡斯1160.P∈[].||()J我v exp（v→i.v→k）K图4：在（1）P-P边，这是相对频繁的，但主要集中在一个小的子图和（2）P-V边，这是非常稀缺和稀疏的学术图诱导饥饿的例子属性，例如个性化PageRank（PPR）得分[16]或Katz相似性[14]。在这项工作中，我们采用了后者。从实际的角度来看，我们取代稀疏二进制邻接矩阵M在方程。1与稠密权重矩阵表1：实验异构网络的统计数据。数据集边类型和边数 U-U U-C C-T C-P-（29771个节点） 5695259042590425904-DBLP P-P P-A P-V P-T-（15649节点）698413589 4258 26532-ACM A-P P-S-（11246节点） 13407 4019-Movie M-A M-C M-D A-AM-M（20784节点） 23223 4001 563043395 61944实验4.1实验装置数据集。我们在四个现实生活中的异构网络上进行评估：重量（单位：千克）HM=我βiMi（五）[23]，[24]，[25]，[26]，[27]，[29]，数据集的统计数据详见表1。• Foursquare[23]是一个基于用户M聚合了每个节点对之间长度达到H的所有可能路径，其中每条路径的影响根据超参数β按比例减小ex0，1。为了确保M是稠密的，假设原始图是连通的，我们将H设置为原始图的直径。当处理大型图时，密集邻接应用程序无法扩展到该大型图时，可以在计算期间或计算之后稀疏化M，同时仍然保留每个节点可以访问所有相关边缘类型的关键属性。3.4基于随机游走的嵌入为了从随机游走中构建节点嵌入，我们采用SkipGram模型[12]。具体而言，该模型学习最大化在生成的随机游走语料库中出现在相同上下文中的节点的联合概率。 目标函数是最小化以下各项：纽约市该图有四种类型的节点：2,449个用户（U），25,904个签到（C），1,250个兴趣点（P）和168个时间戳（T）。边缘类型为U-U、U-C、C-T、C-P。每个兴趣点（P）基于其类别被分配标签，例如“条”。DBLP是一个学术网络，拥有5237篇论文（P），5915位作者（A），18个地点（V）和4479个主题（T）。 边缘类型为P-P、P-A、P-V、P-T。 作者根据他们的研究兴趣被标记为以下四个领域之一：“数据挖掘”，“信息检索”，“数据库”和“机器学习”。ACM [24]是另一个学术网络，由4019篇论文（P），7167位作者（A）和60个主题（S）组成。边缘类型为A-P、P-S。每篇论文都有三个研究类别之一：“数据库”，“无线通信”和“数据挖掘”。电影是一个电影图[8]，由[9]增强。 我们用6517部电影（M），10350，ar<$min−。 ..log（Pr（vj|vi，θ）），（6）演员（A），作曲家（C）1335，导演（D）2582起源-θw∈Pvi∈wvj ∈Cvi，w，k最终边缘类型为M-A、M-C、M-D。[9]用边类型M-M和A-A扩充图，分别表示两部电影其中w是随机游走，Cvi，w，k是距离游走w中的节点vi不超过k步的上下文节点的集合。通常，联合概率是softmax函数：Pr（v|v，θ）=.exp（v→i.v→j），（7）是由同一个制片人制作的，两个演员在Twitter上互相关注表1显示了边缘类型之间的巨大不平衡通过进一步的研究，我们发现A-A型的增广边在网络中是最多的考虑到节点的数量通常很大，我们用负采样近似softmax函数，类似于[13]。因此，方程中的对数概率6可以用公式表示如下：对SchemaWalk提出了挑战，如第3.2节所述每一部电影都有多个标签，包括基线。为了评估嵌入log（Pr（vj|vi，θ））=日志σ（v→i.v→j）+|Neд|1ENP（v）[日志σ（−v→i.v→N）]。（八）我们的方法与国家的最先进的随机游走方法的同质和异质图，如下所示：• DeepWalk[17]学习节点的潜在表示，Ne <$是负样本数，P v是抽样分布。上面的等式定义了SkipGram如何基于随机游走学习HIN中的节点表示。运行一组均匀随机游走来探索图，并通过SkipGram [12]模型学习嵌入 DeepWalk最初是为同构图设计的。···作为一个非常小的和密集的区域，包括约18%的节点的A型这种缺乏连通性的模式可以SchemaWalk：异构图嵌入的模式感知随机游动WWW1161−[客户端]∈[]图5：节点分类结果与训练百分比。请注意，每个数据集的y轴比例并不相同（例如，DBLP的比例高于Foursquare）。Metapath2Vec[2]是一种异构图嵌入方法，它将随机游走绑定为 遵 循 一 组 手 动 定 义 的 元 路 径 。 类 似 地 ， 嵌 入 是 通 过SkipGram 学 习 的 。 元 路 径 U-C-P-C-U 、 P-C-T-C-P（Foursquare）、A-M-D-M-A和A-M-C-M-A（Movie）的选择类似于[9]。对于DBLP，元路径是P-A-P和A-P-V-P-A，如[8]中所示最后，P-A-P 和P-S-P被选为ACM的元路径，如下[24]。JUST[9]是一种异构图嵌入方法，它将随机游走偏向于选择同质边缘（例如DBLP中的P-P）或异构边缘（例如，A-P）。其次，当选择异质边时，它们均匀地采样节点类型。SkipGram用于学习节点表示。在[10]中引入了双向随机游走，以克服传统随机游走的固有偏见，导致低度节点主要出现在游走的最开始，其中只有较小的上下文窗口可用。通过从每个节点开始两个独立的随机游走并将它们连接为一个，起始节点也可以享受完整的上下文窗口，从而更好地嵌入。虽然[10]将这些遍历与SkipGram的异构变体相结合，但我们使用原始的SkipGram算法对其进行评估。请注意，还有其他异构图嵌入方法可以用不同的学习组件（如HIN2Vec [3]）取代SkipGram ，或者提出它的异构变体，如Metapath2Vec++[2]和MARU [10]。然而，我们致力于这项工作的分析不同的随机游走作为一种抽样技术，图6：归一化节点分类结果w.r.t. SchemaWalk。相信其中最具表现力的可以与不同的学习方法相结合。因此，与上述涉及更复杂的学习组件的方法进行比较不在本工作的范围内。实施细节。 对于SchemaWalk，我们使用Movie数据集上的节点分类来调整de cay超参数α，并在α 0上进行搜索。1，0。9和0的步骤。1.因此，对于所有数据集，α固定为0.8对于我们的方法和基线，我们采用与DeepWalk [ 17 ]相同的具体来说，我们设置行走长度l=40，行走次数λ=80，窗口大小w=5，维度大小d=128。对于双向行走，我们将λ视为行走对的数量，l视为行走对的组合长度，以便在所有方法中保留相同数量的训练数据 我们报告了10个随机数据分割的平均结果。对于每个分割，使用5倍交叉验证调整超参数，并在20%保留测试集上进行评估。代码和数据集可以在GitHub 1上找到。4.2节点分类任务该任务是多标签节点分类，其中每个节点与标签集合L中的一个或多个标签相关联。为了评估结果嵌入的质量，我们训练了一个具有相同评分函数的one-vs-all logistic回归[17]。 对于训练，10个训练数据分割/集，每个分割为8个不同的百分比0。1，0。8，用于显示每个模型的学习行为和鲁棒性 为了评估，剩下的20%的数据作为测试集。选择Micro-F1和Macro-F1作为多标签分类的评价指标。图5显示了五种随机游走技术在四种异构网络上的性能 结果显示，随机游走的性能通常是可比较的，SchemaWalk在数据集上获得了最好到第二好的结果。首先，我们观察到DeepWalk和Bidirectional Walks在Movie和ACM上的表现具有竞争力。这表明了同质结构（即，而不管节点和边 的类 型 ）与 正确地分 类 节 点 更相关。 虽 然 异 构 知 识 在Foursquare 和 DBLP 中 似 乎 更 重 要 ， 但 SchemaWalk 和Metapath2Vec产生了明显更好的性能。因此，我们得出结论，对于结构的均匀勘探已经足够的情况，诸如DeepWalk之类的方法1https://github.com/AhmedESamy/SchemaWalk···WWW萨米，吉亚雷塔，凯法托，吉吉亚乌斯卡斯1162图7：生成的随机游走上的边类型分布的圆环图。表现良好。随着异构知识变得势在必行，异构网络嵌入方法可能是必不可少的。其次，SchemaWalk在DBLP上呈现的结果比异构网络嵌入基线更好-在其他数据集上也表现得始终如一特别是，在图5中值得注意的是，SchemaWalk在DBLP上达到了10%的训练数据的高准确性分数，并且在训练百分比中保持了最高的Micro-F1和Macro-F1分数。此外，如图6所示，SchemaWalk在所有数据集上都一直很高。例如，Metapath2Vec在Foursquare上取得了最好的结果，但在Movie上最差。这是因为Metapath2Vec的性能取决于所选元路径的质量及其对特定标签集的适用性。同样，DeepWalk在Movie上实现了最好的性能，但在DBLP上最差。相反，与同构和异构网络嵌入基线相比，SchemaWalk在所有图结构上都表现出稳定的性能。最后，SchemaWalk在所有实验中都优于JUST这种观察验证了直觉，即基于边缘类型的采样是一种更灵活，更有前途的嵌入方法，用于无元路径的异构网络嵌入。4.3图式漫游的定性分析在本节中，我们将对SchemaWalk与DeepWalk进行定性分析和比较 我们通过以下可视化来实现这一点。边类型上的抽样分布 图7显示了DeepWalk和SchemaWalk生成的随机游走中边类型的分布。基于DBLP和Movie数据集，将边缘类型分布可视化为甜甜圈图。检查基于DBLP的图表，可以注意到每种步行类型之间的主要差异由于SchemaWalk旨在探索网络模式，因此该图表显示了近乎均匀的分布图8：DBLP上SkipGram的上下文窗口中目标和上下文节点类型之间的相关性的热图。在边缘类型上;除了在DBLP图中稍微缺失的边缘类型“Paper-Paper”然而，在DeepWalk的情况下，边缘类型的分布是偏斜的DeepWalk将采样偏向于图中的高度节点（或频繁的边缘类型）例如，类型为“Venue”的节点及其相关联的边类型“Paper-Venue”的频率要低得多，因此DeepWalk对它们的采样较少。至于Movie数据集，该图存在结构性问题，例如缺少边缘类型（例如，电影-电影）或边缘类型的高度偏斜分布（例如，演员-演员）。因此，在Movie图上进行采样对于SchemaWalk实现均匀分布特别具有挑战性。例如，对于边类型“Actor-Actor”，饥饿现象是清楚的;虽然DeepWalk给出了“Actor-Actor”作为最频繁边类型的最高概率，但SchemaWalk努力对边类型进行适当采样。这是由“演员-演员”的高度不平衡分布造成的，只有18%的演员。因此，与DeepWalk相比，SchemaWalk对这种边缘类型的采样最少节 点 类 型 之 间 的 相 关 性 为 了 进 一 步 理 解 DeepWalk 和SchemaWalk之间的差异（作为同构与异构网络采样方法），我们在Skip Gram的上下文窗口中绘制了节点类型的同现热图。图8显示了DBLP上两种方法的热图。查看该图，两种方法都显示了所有节点类型与节点类型P（“Paper”）的高度相关性，其中P作为上下文节点出现。如果节点类型P是DBLP网络模式中的中心节点，那么这是一种预期行为（图1（b））。然而，当将节点类型P视为目标节点时，我们可以看到差异. SchemaWalk显示了目标节点类型P和其他边缘类型之间的相同相关性，这突出了P所涉及的边缘类型的均匀分布属性。相比之下，DeepWalk显示出较高的方差，并且P-A和P-T优于P-V。DeepWalk的属性有利于高频，这是合理的。SchemaWalk：异构图嵌入的模式感知随机游动WWW1163∈∈[]表2：SchemaWalkHO VS. 架构漫游图9：不同α下SchemaWalk的分类结果。此外，观察两个图表中节点类型V和T是上下文节点的列（图8），我们可以看到，使用DeepWalk，节点类型V被选为上下文节点的机会很低，而节点类型A和T被选为上下文节点的机会很高。然而，在SchemaWalk的情况下，这三种节点类型有非常相似的选择机会。这些观察结果巩固了我们的直觉和动机;SchemaWalk旨在探索网络模式，而DeepWalk则针对图的同构结构，通常有利于高度节点（或频繁的边类型）。4.4衰减参数α图9显示了参数α对DBLP和Movie网络上生成的节点嵌入质量的影响随着随机游走的展开，α的值控制着每种边缘类型的采样概率的衰减率。特别地，更高的衰减速率导致每个单个上下文窗口内的边缘类型的更均匀的采样，因为不鼓励以快速序列多次采样相同的边缘类型。 当α接近1时，这种局部偏斜是允许的，而等式3保证了全局抽样分布仍然是均匀的。 在实验期间，通过以0.1的步长在α [0.1，0.9]上搜索，在Movie数据集上调整衰减参数α。在图9中，我们报告了节点分类任务的测试结果研究结果表明，当α=0时，DBLP算法的性能达到最佳. 4，然后随着值接近1而下降在Movie上，性能相当稳定，当α> 0时略有改善。6. 除了Movie数据集，我们在实验中观察到α 0. 四，零。6通常给出最好的结果，假设其他超参数设置为默认值。这表明在SkipGram的上下文窗口当某些节点在其直接邻域内缺少某些边类型时，减小α的值仍然有助于补偿然而，Movie数据集的分析是不同的;降低α似乎会恶化3.3节中描述的饥饿问题。 由于边缘类型A-A和M-M严重缺失，SchemaWalk的补偿需求随着α的减小而呈指数级增加，因此导致对缺失的边缘类型进行过采样。值得注意的是，无论α的值如何，性能增益仍然不显著;这是因为Movie上的节点分类似乎从以均匀方式探索图中受益更多，如前所述。对于评价，所有数据集的α均设定为0.84.5SchemaWalkHO的性能表2比较了SchemaWalkHO与SchemaWalk在DBLP和Movie数据集上的节点分类任务中的性能。值得注意的是，在高阶图而不是原始图上行走会对性能产生负面影响，在某些情况下会产生显着影响。此外，当超参数β被降低时，使高阶图在结构上更接近原始图，分类性能将回升到原始SchemaWalk的水平。SchemaWalkHO的理论优势是它能够保持边缘类型的均匀采样分布，即使其中一些在原始图中呈现偏斜分布。然而，这些结果表明，这种优势被有害的副作用所抵消。一个副作用可能是在大小为k的SkipGram窗口内出现距离目标节点超过k跳的节点-因此稀释了邻近度的概念，这是使用SkipGram进行节点嵌入的关键当β值较低时，这种现象在具有均匀分布的边类型的图上应该很少发生。实际上，当β = 0时。01时，DBLP的性能回升到接近最佳的分数。另一方面，当节点缺少网络模式中的某些边类型时，尽管β值很小，但这种现象仍然持续，因为SchemaWalkHO试图克服这种边类型缺陷并避免饥饿。Movie数据集中的M-M和A-A边就是这种情况。 结果显示，即使β较低，该数据集的性能差距也较大。这表明，基于结构模式（例如我们实现中的连接路径数量）的“完成”缺陷邻域可能代表了对潜在现象的不良近似，至少在Movie数据集上是如此。 某些边缘类型的缺乏实际上可能不是由数据集的不完整性引起的，而是本身可能是输入信号的一部分，提供关于图中某些节点的作用的有价值的信息。因此，重要的是，未来的工作，研究如何捕捉这些差异和不足的连接，同时仍然保留优势，在某些情况下提供的边缘类型的统一采样。4.6SkipGram在异构图嵌入中的局限性这项工作的主要重点是提出和比较新的随机行走技术，而不是替代学习组件SkipGram。尽管如此，我们还是提供了与HIN2Vec [3]的比较，这是本研究的一部分。如表3所示，HIN2Vec [3]在几乎所有数据集上都表现出比SchemaWalkHIN2VecDBLP微观宏观电影微观宏观SchemaWalkHO（β= 0. 第一章84.584.535.528.4SchemaWalkHO（β= 0.01）的87.587.451.848.4WWW萨米，吉亚雷塔，凯法托，吉吉亚乌斯卡斯1164表3：SchemaWalk与HIN2Vec架构漫游（SkipGram）HIN2VecDBLP微宏观0.8760.8750.8760.876ACM微宏观0.8330.8270.9030.901电影微宏观0.5210.4890.540.51不使用与SchemaWalk和DeepWalk相同的SkipGram模型[17]。相反，它提出了一种不同的学习模型，通过元路径显式地表示异构知识，并通过预测任何两对输入节点的正确元路径/关系来学习。因此，该模型具有更大的学习能力，可以直接访问异构知识，而SkipGram不知道目标-上下文对的节点类型和连接它们的边类型。 我们还观察到，HIN2Vec在探索图时不会对随机游走施加强假设。因此，我们认为，他们的性能优势很大程度上来自学习组件。其他最 先进 的 方 法也 观 察 到了 同 样 的情 况。 例 如 ， 尽管Metapath 2 Vec [2]采用元路径引导的随机游走，但只有当作者将它们与Skip-Gram的异构变体结合时才能实现相当大的改进。类似地，尽管MARU [10]提出了一种双向随机行走来全面探索图，但只有在与异构SkipGram相结合时才能观察到其优势。查看最后的观察结果以及图6和表3，我们由此得出结论，对网络结构的充分理解/采样与HIN中复杂知识的显式学习/建模相结合是强烈推荐的异构网络嵌入的研究方向。5相关工作异构网络中学习表示的研究一直在蓬勃发展。许多嵌入方法将任务作为随机优化问题来处理[2，3，5，15]。例如，一些早期的工作试图预测异构图中两种类型节点之间的二元关系[1，20]。transE [1]学习实体和关系向量，其中关系向量基于它们的同现在实体类型之间转换，从而开始了知识图的研究趋势[15]。 而PTE [20]通过基于边类型提取二分网络，将LINE [21]扩展到异构网络。为了学习节点嵌入，它们然后捕获一跳邻域。然而，在以二元关系为目标时，这些方法忽略了节点之间关系的复杂语义。最近，几种方法明确地利用异构结构，即。使用元路径的节点类型[3，6，8]。Metapath2vec [2]扩展了DeepWalk[17] 通 过 限 制 随 机 游 走 以 遵 循 预 定 义 的 元 路 径 集 合 而HeteSpaceyWalk [6]提出了一种空间随机游动来近似基于元路径的随机游动的平稳分布。这些方法的性能，虽然通常令人满意，然而取决于所选择的元路径的质量，所选择的元路径通常由DO主要专家手工制作HIN2Vec [3]和HINE [8]等方法通过在特定标准（如最大长度）下定义元路径来避免后一个问题。更长的长度导致指数计算增加[3]，而长度的选择仍然可能影响最终性能[8]。 为了避免完全使用元路径，JUST [9]对随机游走进行了偏置，以便所有节点类型都以公平的平均分布进行选择。然而，他们的随机游走的概念是相当激进的;例如，回文语义序列，如作者-论文-作者是不可能采样的。因此，JUST可能会忽略关键的异质结构。更类似于我们，HeteSpaceyWalk [6]利用网络模式来指导他们的空间随机行走。然而，他们的目标是在保持均匀分布 和 有 利 于 以 前 采 样的节点类型之间取得平衡。很明显，SchemaWalk平衡了网络模式中的边类型选择，并灵活地补偿了所选边类型下的缺失边。最后，还有其他方法，如HeGAN [7]，它将对抗学习应用于HIN嵌入，Metapath2Vec++[2]，MARU [10]和HIN2Vec [3]。这些方法涉及学习部分。然而，这项工作进一步推进了采样过程，即随机游走，并通过SkipGram模型进行学习[12]。6结论在本文中，我们提出了SchemaWalk，一个灵活的随机游走异构网络嵌入。我们的工作的核心见解是，在不了解异构图中每个节点和边类型的重要性的情况下，随机游走器应该以公平采样为目标，而不对节点/边类型进行假设。此外，我们认为，基于边缘类型的探索可以更灵活和粒度，而不是基于节点类型的采样，这可能会错过异构网络中的重要语义。因此，我们利用网络模式，实现均匀的抽样分布的边缘类型。最后，我们发现了异构网络中的饥饿现象，并提出了SchemaWalkHO来解决这个问题。对多标签节点分类的评估证明了SchemaWalk在实际异构网络中的鲁棒性能，同时也暗示了SkipGram不适合嵌入异构网络。此外，我们提供了详细的定性分析SchemaWalk与DeepWalk。最后的见解和结论可以总结如下：（1）异构网络呈现丰富的结构，同质嵌入方法可能不足以捕获;（2）与基于节点类型的替代方案相比，边缘类型的无偏探索可以提供更细粒度和通用的异构网络嵌入方法;（3）SkipGram的同质性质使其不太适合异构网络嵌入。致谢该项目已获得欧盟rais-itn.eu。SchemaWalk：异构图嵌入的模式感知随机游动WWW1165引用[1] 安托万·博德斯，尼古拉斯·卡尼尔，阿尔贝托·加西亚·杜兰，杰森·韦斯顿，和奥克萨纳·亚赫年科。2013年。 为多关系数据建模转换嵌入。神经信息处理系统的进展26（2013）。[2] Yuxiao Dong ， Nitesh V Chawla ， and Ananthram Swami.2017 年 。metapath2vec：面向异构网络的可扩展表示学习 第23届ACM SIGKDD知识发现和数据挖掘国际会议论文集。135-144。[3] Tao-yang Fu，Wang-Chien Lee，and Zhen Lei. 2017. Hin2vec：探索异构信息网络中的元路径，用于表示学习。在2017年ACM信息与知识管理会议上。1797-1806.[4] Aditya Grover和Jure Leskovec2016年。node2vec：可扩展的网络特征学习。第22届ACM SIGKDD知识发现和数据挖掘国际会议论文集。855-864[5] William L Hamilton，Rex Ying和Jure Leskovec。2017.图上的表示学习：方法与应用。arXiv预印本arXiv：1709.05584（2017）。[6] Yu He，Yangqiu Song，Jianxin Li，Cheng Ji，Jian Peng，Hao Peng.2019年。 Hetes-paceywalk：一种用于异构信息网络嵌入的异构空间随机行走。 第28届ACM信息与知识管理国际会议论文集。639-648[7] 胡彬彬，袁方，石传。2019年。 异质信息网络上的对抗学习。第25届ACMSIGKDD知识发现&数据挖掘国际会议论文集。120比129[8] Zhipeng Huang和Nikos Mamoulis。2017年。基于Meta路径邻近的异构信息网络嵌入arXiv预印本arXiv：1701.05291（2017）。[9] Rana Hussein，Dingqi Yang，and