语义用户搜索中的子图增强路径嵌入

16130用于异构社交网络上的子图增强路径嵌入的语义用户搜索0浙江大学中国刘泽民0Vincent W. Zheng �0新加坡高级数字科学中心0浙江大学中国周昭0阿里巴巴集团中国杨红霞0伊利诺伊大学香槟分校美国Kevin Chen-Chuan Chang0浙江大学城市学院中国吴明辉0浙江大学中国景颖0摘要0语义用户搜索是异构社交网络上的一个重要任务。其核心问题是根据某种语义用户关系来衡量网络中两个用户对象之间的接近程度。最先进的解决方案通常采用基于路径的方法，该方法使用连接查询用户和目标用户的对象序列来衡量它们之间的接近程度。尽管这些方法取得了成功，但我们断言路径作为一种低阶结构不足以捕捉两个用户之间的丰富语义。因此，在本文中，我们引入了一种新的概念，即子图增强路径，用于语义用户搜索。具体而言，我们考虑从查询用户到目标用户中采样一组对象路径；然后在每个对象路径中，我们用它们共享的子图实例替换相邻用户之间的线性对象序列。这种子图增强路径既能利用路径的距离感知性，又能利用子图的高阶结构。由于建模这种子图增强路径并不容易，我们开发了一种子图增强路径嵌入（SPE）框架来完成任务。我们在三个真实世界的公共数据集中评估了我们的解决方案在六种语义用户关系上的性能，并表明它优于基线方法。0CCS概念0• 计算方法学  →  统计关系学习；0关键词0异构网络；子图增强路径嵌入0ACM参考格式：Zemin Liu，Vincent W. Zheng，Zhou Zhao，HongxiaYang，Kevin Chen-Chuan Chang，Minghui Wu和JingYing。2018年。子图增强路径0� 通讯作者。0本文发表在Creative Commons Attribution 4.0 International（CC BY4.0）许可下。作者保留在其个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据Creative Commons CC BY 4.0许可发布。ACMISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31860730Alice（用户）0Bob（用户）0Chris（用户）0Donna（用户）0UCLA（学院）0（位置）0（雇主）0Emily（用户）0Frances（用户）0Facebook（雇主）0（雇主）0（学院）0Glen（用户）0图1：在具有不同对象的丰富用户交互的异构社交网络上的语义用户搜索。0用于异构社交网络上的语义用户搜索的嵌入。在The 2018 Web Conference (WWW2018)的论文集中。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318607301 引言0异构社交网络现在很普遍[37]。因为社交网络是以人为中心的，所以观察到用户与许多其他类型的对象进行交互是很常见的。例如，如图1所示，在社交网络上，用户与其他用户以及学院、位置和雇主进行交互。这些不同类型的交互暗示了用户-用户关系的不同语义。例如，Alice和Bob都在UCLA上学，因此他们是同学；而Chris和Donna都在Facebook工作，因此他们是同事。因此，这给了我们一个独特的机会来进行语义用户搜索。一般来说，语义用户搜索是一个任务，给定一个查询用户（例如Alice）在异构社交网络上和一个语义关系（例如同学），我们希望找到与查询用户满足该关系的其他用户（例如Bob）。这种语义用户搜索非常有用[19,22]。例如，我们可以在Facebook和LinkedIn等社交网络上使用它来找到同事、同学和家人，或者在DBLP等学术网络上找到导师和学生。传统上，路径为基础的方法被用于解决语义用户搜索。这是因为在语义用户搜索中，目标用户通常不会立即链接到查询用户。一个合理的选择是考虑从查询用户到目标用户的路径，并查看它们是否与所需的语义关系匹配。例如，Meta-PathProximity（MPP）[30]首先依赖于领域0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, Francem1 m2 m3 m4 m5 m1 : 1 m2 : 1 m3 : 1 m1 : 1 m5 : 2 m1 : 1 m4 : 1 m2 : 1 m5 : 1 m2 : 1 m5 : 1 m1 : 1 m3 : 1 … 16140Alice（用户）0Bob（用户）0Chris（用户）0Donna（用户）0UCLA（大学）0Facebook（雇主）0（a）连接用户Alice和用户Donna的示例对象路径。0用户0用户0m1:1m2:1m3:10Alice（用户）0Bob（用户）0Chris（用户）0Donna（用户）0用户0颜色 用户0用户 用户 雇员0用户 用户 位置0用户 用户 大学0m1:1m5:20m1:1m4:10（b）用子图增强每对相邻用户。0m1:1m2:1m3:10m1:1m5:20m1:1m4:10（c）子图增强路径。0Prox.0得分0排名0损失0SPE0（d）SPE的训练框架。0图2：将路径的距离感知和子图的高阶结构结合起来进行语义用户搜索。0专家可以指定几个指示所需语义关系的路径模式（即元路径），然后枚举查询用户和目标用户之间的元路径实例的数量。路径排序算法（PRA）[18]首先枚举有界长度（关系）路径模式；然后递归地为每个路径模式定义一个分数；最后，对于目标节点，其与查询节点的接近度被计算为其相应路径实例的线性组合。最近，深度学习开始利用学习表示查询节点和目标节点之间的路径，然后将其用于接近度估计。例如，ProxEmbed[20]首先从查询节点到目标节点采样多个路径，然后使用递归神经网络将每个路径嵌入为一个向量；最后，它聚合多个路径嵌入向量以进行接近度估计。尽管这种基于路径的方法取得了成功，但我们断言路径作为低阶结构不足以捕捉两个用户之间丰富的语义。考虑图2(a)中连接查询用户Alice和目标用户Donna的对象路径。实际上，Alice和Bob不仅在同一所大学UCLA就读，而且住在同一个城市L.A.。这样的信息在路径中丢失了，但是某些更高阶的子图结构可能能够捕捉到这些信息。我们受到了在组织复杂网络方面的最新工作的启发。假设我们已经有了一些离线挖掘的子图模式，如图2(b)中的用户-用户（m1）、用户-大学-用户（m2）、用户-大学和位置-用户（m3）等。然后，我们可以用m1、m2和m3的更丰富的子图实例替换Alice和Bob之间的线性对象序列。通过这种方式，我们对Alice和Bob之间的语义关系有了更完整的了解。我们设想，一旦我们更好地理解路径中每两个相邻用户之间的语义关系，我们就能更好地估计查询用户和目标用户之间的接近度。注意，我们只关注增强相邻用户对象。避免增强任意两个相邻对象而不考虑它们的类型有两个原因。首先，在语义用户搜索中，我们希望直接建模用户之间的语义关系。其次，通过限制增强相邻用户对象，我们可以减少噪声的影响。0通过涉及两个用户的子图模式，我们可以显著减少子图模式的数量，从而大大提高离线子图索引的效率，正如[11]所建议的那样。在本文中，我们引入了一种新的概念，即用于语义用户搜索的子图增强路径。具体而言，我们考虑从查询用户到目标用户采样一组对象路径；然后在每个对象路径中，我们用它们之间的共享子图实例替换其每两个相邻用户之间的线性对象序列。这样的子图增强路径预期能够利用路径的距离感知（即能够建模查询用户和目标用户之间的多跳连接）和子图的高阶结构（即能够使用比线性序列更复杂的结构）。给定这些子图增强路径作为新的输入，我们的目标是将它们嵌入到低维向量中，然后对它们进行聚合以进行接近度估计。在这项工作中，我们假设子图模式和子图实例作为输入已经给定。在实践中，这样的假设是合理的，因为频繁子图是有用的，并且通常作为基本图索引进行离线挖掘，以支持许多有用的应用程序[10]。例如，频繁子图用于阿里巴巴的欺诈检测[1]和Twitter的用户/内容推荐[13]。还存在有效的算法来挖掘频繁子图模式和匹配子图实例[9,31]。然而，嵌入子图增强路径（或简称为s-path）并不是一件简单的事情。一种直接的方法是应用ProxEmbed[20]。对于每个s-path，我们将其每个节点表示为一个键值对（定义3.5），其中键是结束用户对，值表示这两个用户之间共享的每个子图实例的数量。然后，我们应用递归神经网络对s-path中的每个节点进行编码，最后将所有节点的输出向量汇集为一个向量。对于多个s-path，我们使用距离折扣池化来减弱那些较长的路径。然而，这种直接的方法忽视了两个挑战。首先，子图具有结构和噪声。为了表示s-path中的节点，我们必须考虑每个子图的结构，以及并非所有子图对于特定的语义用户关系都是有用的（例如，m5对于schoolmates关系的指示性小于m2）。其次，s-path本身和其中的噪声。在每个s-path中，其节点对于语义关系并不都是同样有用；例如，如果Alice和Donna真的是schoolmates，那么s-path中的节点（Alice，Bob），它暗示了一个schoolmates关系，比同一s-path中的其他节点更重要。同样，并非所有的s-path都是同样有用的；例如，在图1中从Alice - Emily - Frances -Donna构建的s-path对于schoolmates关系的指示性小于图2(c)中的s-path，因为它对于该关系没有明确的信号。为了对语义用户搜索建模s-path，我们开发了一种新颖的子图增强路径嵌入（SPE）框架。在SPE中，我们首先使用子图之间的结构相似性矩阵来表示s-path中的对象，然后基于该矩阵学习每个子图的嵌入向量以保留结构相似性。然后，我们引入注意机制[40]来自动加权聚合中的子图以表示每个s-path的节点。为了处理s-path中的噪声，我们还引入了注意机制来自动加权01 https://www.alibabacloud.com/forum/read-4920Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France16150每个s-path中的每个节点和两个用户之间的每个s-path。总之，我们在子图、s-path的节点和s-path上有一个三层注意力架构。最后，我们将所有的s-path一起嵌入到一个向量中，基于此计算接近度得分，从而计算模型训练的排序损失。我们总结我们的贡献如下。0•我们引入了一个新的子图增强路径的概念，首次系统地结合了路径的距离意识和子图的高阶结构来解决语义用户搜索问题。0• 我们开发了一个新颖的SPE框架，用于嵌入这些子图增强路径以进行用户接近度估计。0•我们在三个公共数据集中评估SPE在六种语义用户关系上，并展示其优于现有的基线方法。02 相关工作0早期的图形语义搜索工作，如个性化PageRank [17]和SimRank[16]，通常将同质网络视为输入，并且它们不区分语义类别。最近的工作开始考虑异构网络中丰富的网络结构。例如，监督随机游走（SRW）[1]试图偏置网络上的随机游走，以确保网络上的排序结果与基本事实一致。MPP [30]和PRA[18]尝试使用一些监督（即元路径模式或基本事实标签）来匹配查询节点和目标节点之间的路径，以查看某种语义关系是否成立。元图相似度（MGP）[11]考虑的是比元路径更一般的子图模式。它首先将一些频繁的子图模式识别为元图，然后利用监督来自动学习哪个元图对所需的语义关系具有指示性，最后计算两个用户之间的指示性元图数量来衡量它们的接近程度。由于子图的高阶结构，MGP改进了基于路径的方法，如SRW和MPP。但是MGP缺乏距离意识;即，如果查询用户和目标用户之间是多跳的，并且它们之间没有共享的元图，则它们的接近程度变为（接近）零。MPP和MGP都可以看作是利用显式图形特征进行接近度估计。随着神经网络的发展，一些最近的研究开始考虑学习接近度估计的“隐式”图形特征。例如，在图嵌入中，DeepWalk [27]，LINE [32]，node2vec[12]等都尝试为图中的每个节点学习一个嵌入向量，可以保留图的结构。特别是，metapath2vec[8]通过使用元路径来指导随机游走以获得更好的节点嵌入。Struc2vec[28]利用两个节点的附加结构等价性进行节点嵌入。最近有一份关于图嵌入的综述[5]。利用这种节点级嵌入进行语义搜索的一种可能方法是聚合两个节点的嵌入向量（例如，首先应用Hadamard乘积，然后将其与参数向量相乘）以估计它们的接近程度。然而，这种方法被认为是“间接的”，如ProxEmbed[20]所建议的，因为它不直接编码两个可能相距较远的节点之间的网络结构。相反，ProxEmbed通过一组连接它们的路径来表示两个对象之间的网络结构，并将这些路径直接编码为接近度嵌入向量。0然而，由于ProxEmbed将对象路径作为输入，它无法利用现有的子图的高阶结构。类似地，尽管D2AGE[21]成功地将多个对象路径建模为一个有向无环图进行接近度嵌入，但它也无法利用离线挖掘的子图。在图嵌入的领域中，存在一些相关但不同的概念。首先，一些最近的工作在图嵌入中利用了“高阶接近度”的概念[6，38]。他们使用高阶可达性构建图的邻接矩阵，然后在该邻接矩阵上运行节点嵌入。与我们的方法有两个主要区别：1）他们不利用子图模式的高阶结构；2）他们考虑的是节点嵌入而不是路径嵌入。其次，一些其他工作通过图卷积[14，24]对高阶结构进行建模。这些方法可以捕捉局部图模式，但如何将路径的距离意识纳入语义用户搜索任务尚不清楚。此外，它们无法利用现有的子图模式。第三，图核方法[7]，特别是Weisfeiler-Lehman图核[29，41]，尝试衡量两个（小）图的相似性。它们通常利用一些预定义的子图结构，如边，子树和最短路径。但是，它们衡量图之间的相似性的目标与我们衡量节点之间的接近程度的目标非常不同。此外，如何将它们的方法与路径距离意识相结合以适应我们的任务尚不清楚。最后，在知识库领域，最近的工作，如TransE [4]，TransH [39]和TransNet[34]，极大地推动了知识嵌入的研究。然而，由于问题设置的不同，这些方法不直接适用于我们的任务。它们通常要求边具有明确的描述，并旨在生成节点/边嵌入而不是路径嵌入。此外，如何将这些方法扩展到子图的高阶结构和路径的距离意识以适应我们的任务尚不清楚。03 问题建模0首先介绍术语和符号（见表1）。0定义3.1. 异构网络是G = (V, E, C,τ)，其中V是一组对象，E是V中对象之间的边集，C = {c1,...,cK}是一组不同的对象类型，τ: V → C是一个对象类型映射函数。0例如，在图1中，我们有C = {user, college, location,employer}。对于Alice的对象，τ(Alice) = user。0定义3.2. 子图模式是m = (Cm,Em)，其中Cm是一组对象类型，Em是Cm中对象类型之间的边集。0例如，图2(b)列出了五个子图模式m1,...,m5。我们将G上的可能子图模式的集合表示为M。如第1节所讨论的，我们将M视为从G中离线挖掘出的频繁子图模式，并作为输入直接可用。请注意，与G中的C不同，Cm中的对象类型可能是非不同的。例如，对于图2(b)中的子图模式m1，Cm1 = {user, user}。0定义3.3. 对象子图д = (Vд, Eд)是m = (Cm,Em)的子图实例，如果存在一个从д的节点集到m的双射ϕ: Vд →Cm，使得0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, FranceTrack: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16160表1：本文中使用的符号0符号说明G, V, E, C网络G，对象V，边E，对象类型C0M 从G中频繁挖掘出的子图模式集合0I G上M的子图实例集合0D 训练元组集合0P G上采样的对象路径集合0ˆP 从P构建的子图增强路径集合0r 子图增强节点0x 子图的嵌入向量0z 子图增强路径的嵌入向量0f 两个用户之间的接近度嵌入向量0π 接近度分数0S 子图模式的结构相似性矩阵0γ, ℓ 每个对象的路径数γ，步长ℓ0d, d' 嵌入维度0ζ 用户的平均子图实例数量0• �v ∈ Vд，我们有τ(v) = ϕ(v)；• �v, u ∈ Vд，我们有(v,u) ∈ Eд iff (ϕ(v), ϕ(u)) ∈ Em。0例如，Alice - UCLA -Bob是图2(b)中m2的一个实例。我们将G上M的可能子图实例的集合表示为I。对于每个m ∈ M，可能存在多个G上的子图实例。0定义3.4. G上的对象路径是一个对象序列v1 → v2 → ... →vt，其中每个vi ∈ V，t是路径长度。0例如，图2(a)中的序列是一个对象路径。0定义3.5.子图增强节点（或简称为“s-node”）r对于两个用户对象u，v ∈V是一个键值对，其键为(u, v)，值为一组元组{m1: e1,..., ml:el}。对于每个mi ∈ M，ei是u和v之间mi的实例数量。0例如，在图2(b)中，Alice和Bob的s-node定义为r.key = (Alice,Bob)，r.value = {m1:1, m2:1,m3:1}。我们跳过r.value中实例数量为零的子图。如第1节所讨论的，我们选择仅增强两个用户对象及其共享的子图，以便专注于用户-用户的语义关系并提高子图索引效率。我们将将增强任意两个对象而不考虑它们的类型进行语义搜索作为未来的工作。0定义3.6. 子图增强路径（或简称为“s-path”）是一个s-node序列r1 → r2 → ... → rt。0例如，图2(c)中的序列是一个s-path。0问题的输入和输出。对于我们模型的输入，我们有一个异构网络G，一组现成的频繁子图模式M及其在G上的子图实例I，最后还有一组训练元组D = {(qi, vi, ui): i =1,...,n}，其中对于每个查询用户对象qi，用户vi比用户ui更接近qi。此外，我们还离线从G中采样一些对象路径作为输入。我们采用类似DeepWalk[27]的路径采样方法。具体来说，从G中的每个对象开始，我们随机采样γ个长度为ℓ的对象路径。结果，我们得到一组对象路径，表示为P。这些对象路径被索引以支持高效的训练和测试。对于每个查询对象q ∈ {q1,...,qn}和相应的目标对象v ∈ {v1,...,vn,u1,...,un}，我们提取0从P中提取多个子路径。我们将从q开始并以v结束的所有子路径记为P(q, v)，从v到q的子路径记为P(v,q)。对于从q到v的每个对象路径，我们使用子图模式M及其子图实例I构建一个子图增强路径。我们将在第4节介绍s-path构建的细节。对于我们模型的输出，我们为q和v之间的每个s-path生成一个子图增强路径嵌入向量z(q, v) ∈ Rd，其中d >0是嵌入维度。由于q和v之间存在多个s-path，我们将合理地将多个z(q, v)聚合成一个接近嵌入向量f(q, v) ∈Rd。在这项工作中，我们考虑对称和非对称关系，对于对称关系f(q,v) = f(v, q)，对于非对称关系f(q, v) ≠ f(v,q)。我们将在第5节中讨论如何通过一些分层神经网络模型计算z(q,v)和f(q, v)。最后，我们使用f(q,v)来估计q和v之间的接近度得分，如下所示：0π(q, v) = θTf(q, v)，(1)0其中θ ∈Rd是一个参数向量。我们的模型有两种类型的参数：1）用于获取z(q, v)和f(q,v)的分层神经网络参数；2）接近度估计参数θ。在训练中，我们的目标是学习这些模型参数，使得对于每个(qi, vi, ui) ∈ D，都满足π(qi,vi) ≥ π(qi,ui)。我们将在第6节介绍训练算法的细节。请注意，在离线训练中，我们只需要为那些(i = 1,...,n)的(qi, vi)和(qi,ui)计算子图增强路径嵌入，而不是对G中所有可能的对象对进行计算。在在线测试中，给定G中的一个随机查询用户q，我们将从P中快速提取从q到每个可能的目标用户v的一组样本对象路径。然后我们使用M构造s-paths，并应用我们的模型计算π(q, v)以进行排名。04 S-PATH构建0我们介绍如何根据以下内容为查询用户q和目标用户v构建子图增强路径：1）从q到v在G上已采样的一组对象路径；2）一组现成的频繁子图模式M及其在G上的子图实例I。0运行示例：以图2(b)为例。对于Alice - UCLA - Bob - Chris -Facebook -Donna的对象路径，我们首先通过折叠路径中的非用户对象提取每对相邻用户。结果，我们得到(Alice, Bob)，(Bob, Chris)和(Chris,Donna)。对于每对相邻用户，我们尝试获取每个用户涉及的子图实例。在图2(b)中，我们列出了五种可能的子图模式m1，...，m5；由于空间限制，我们跳过了它们在图1中的异构网络上的子图实例的列表。以(Alice,Bob)为例。对于Alice，她涉及了四个关于m1，m2和m3的子图实例。具体来说，对于m1，Alice在图1中有两个子图实例：Alice -Bob和Alice -Emily。对于m2，Alice在图1中有一个子图实例：Alice - UCLA -Bob。对于m3，Alice在图1中有一个子图实例：Alice - UCLA &L.A. - Bob。为了用子图替换线性对象路径Alice - UCLA -Bob，我们希望找到Alice和Bob共享的所有子图实例。找到这样的共享子图实例的一种简单方法是扫描Alice的所有子图实例，看它们是否包含Bob。正如我们所看到的，Alice和Bob共享m1的一个实例，m2的一个实例和m3的一个实例。然后我们构造一个子图增强节点(s-node) r1，其中r1.key ← (Alice, Bob)Algorithm 1 SPathConstructRequire: a set of object paths P, a query user q, a target user v, aset of subgraph patterns M and its instances I.Ensure: a set of subgraph-augmented paths p’s for (q,v).1: Q(q,v) ← GetSubpaths(P,q,v);2: for each object path oi ∈ Q(q,v) do3:pi ← ∅;4:{(u,u′)} ← GetNeighborUserPairs(o);5:for each (u,u’) do6:Iu,u′ ← GetSharedSubgraphInstance(I,u,u′);7:r.key ← (u,u′);8:r.value ← CountSubgraphInstance(Iu,u′,M);9:pi.append(r);10: return {pi }.and r1.value ← [m1 : 1,m2 : 1,m3 : 1]. Similarly, we can constructan s-node r2 for (Bob, Chris) and an s-node r3 for (Chris, Donna).In the end, we obtain an subgraph-augmented path (s-path) ofp : r1 → r2 → r3.We abstract the above running example, and summarize the s-path construction algorithm in Alg. 1. In line 1, we first extractall the object subpaths from q to v from P. Here we overload thefunction “GetSubpaths” to get different subpaths for symmetricand asymmetric semantic relations. In line 4, for each resultingobject path, we get all the neighboring user pairs. In line 6, foreach pair of neighboring users, we identify their shared subgraphinstances from the pre-indexed subgraph instance set I. After that,we construct an s-node in lines 7 and 8, and further append it tothe previous s-node sequence to form an s-path in line 9.Complexity analysis: as each object path’s length is boundedby ℓ, getting the neighboring user pairs in line 4 takes O(ℓ). Thestraightforward approach to get shared subgraph instances betweentwo users has to scan through all the subgraph instances of oneuser. Denote the average number of subgraph instance for a user onG as ζ . Because in practice the subgraph patterns have limited sizes(e.g., less than six in our experiments), the above straightforwardapproach to run line 6 takes O(ζ ). This complexity can be furtherreduced; as suggested by [11], if in the subgraph indexing stageonly those subgraph patterns that involved at least two users wereconsidered, then both the number of subgraph patterns and thenumber of subgraph instances can be significantly reduced. By asophisticated indexing of which subgraph instance matching whichtwo users, we may reduce line 6’s complexity to a constant. In all,constructing an s-path from an object path takes O(ℓ + ζ ).5S-PATH EMBEDDINGWe first introduce how to embed each subgraph-augmented pathto a vector z(q,v), and later aggregate multiple such vectors intoa single one f(q,v). We design a hierarchical neural network forsubgraph-augmented path embedding (SPE) as shown in Fig. 3. Asmotivated in Sect. 1, we will take multiple factors into the design.First of all, we embed each subgraph with structural information.Then, we aggregate the subgraph embedding in each subgraph-augmented node (s-node) with attention to obtain an s-node em-bedding. To model the sequential information of each s-path, we… S-node embedding Subgraph embedding αiηxiy jLSTM … S-path embedding … zkf (q,a)Proximity embedding π(q,a)Proximity score θʹα jʹη… ʹʹαkʹʹηf (q,b)π(q,b)… ℓ(π(q,a),π(q,b))xisi′sih j16170堆叠自编码器0子图0结构相似性0图3：子图增强路径嵌入。0我们还采用了递归神经网络架构来学习s-path的嵌入。最后，我们使用注意机制汇总所有s-path的嵌入，以获得(q,v)的整体邻近嵌入向量。接下来，我们在图3中介绍嵌入的每个步骤。0子图嵌入。为了考虑子图结构，我们受到结构深度网络嵌入[38]的启发，考虑从子图结构相似性矩阵中嵌入子图。一般来说，如果两个子图共享一些相同的结构，则它们是相似的。因此，我们采用了广泛使用的最大公共子图（MCS）方法[35]来衡量两个子图之间的相似性。给定两个子图 m i 和 m j，我们将 m �表示为它们的MCS。然后，两个子图之间的结构相似性定义为0S ( m i , m j ) = 0( | C m i | + | E m i | ) × ( | C m j | + | E m j0如果 m � 更大，则 S ( m i , m j )更大。我们使用堆叠自编码器[2]来学习每个子图 m i 的嵌入 x i ∈ Rd。记 s i = [S ( m i , m 1 )，...，S ( m i , m | M | )]T。为简单起见，我们使用一个三层自编码器来说明如何从其 s i 构建x i。特别地，我们将子图 m i 的子图嵌入向量 x i 定义为0x i = σ(W ( a ) s i + b ( a ))，(3)0其中 W ( a ) ∈ R d × | M | 和 b ( a ) ∈ R d 是参数；σ ( ∙ )是一个sigmoid函数。我们通过以下方式从 x i 重构 s i：0ˆ s i = σ(W ( b ) x i + b ( b ))，(4)0其中 W ( b ) ∈ R | M | × d 和 b ( b ) ∈ R | M |也是参数。最后，我们最小化重构误差：� | M | i = 1 ∥ ˆ s i − s i ∥2。 (5)0虽然以后优化 x i与邻近嵌入一起是可能的，但在本文中，我们选择从 S 中分别优化 xi，以保持模型简单。0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, Francehj = g( )j⊙ tanh(g( )j),(13)={W (i) ∈ Rd′×d,U (i) ∈ Rd′×d′,b(i) ∈ Rd′,W (f ) ∈ Rd′×d,U (f ) ∈Rd′×d′,b(f ) ∈ Rd′,W (c) ∈ Rd′×d,U (c) ∈ Rd′×d′,b(c) ∈ Rd′,W (o) ∈Rd′×d,U (o) ∈ Rd′×d′,b(o) ∈ Rd′}.To differentiate the contributions of s-nodes, we also computethe attention score α ′j for each s-node rj asα ′j =exp(β′j )�tk=1 exp(β′k ) ,(14)β′j = η′ σ (Q′hj + b′),(15)zk =tj=1 α ′jhj.(16)Θα ′′k =β=f(q,v) =pkˆ (q,v) α ′′k zk .(19)6END-TO-END TRAININGℓ(π (qi,vi ),π (qi,ui )) =logσλ(π (qi,vi )π (qi,ui )),(20)16180S-Node嵌入。一般来说，一个subgraph-augmentednode（s-node）中涉及多个子图。为了区分它们的贡献，我们引入了一个注意机制，自动学习s-node嵌入中每个子图的权重。对于一个s-node r j。value = { m 1 : e 1，...，m l : e l }，我们计算 r j中每个子图 m i 的注意分数 α i 为0α i = 0� l j = 1 exp ( β j )，(6)0β i = e i [ η ∙ σ ( Q x i + b ) ]，(7)0其中 η ∈ R d'，Q ∈ R d' × d和 b ∈ R d' 是参数。因此，我们计算r j 的 s-node 嵌入为0y j = � l i = 1 α i x i. (8)0S-Path嵌入。一旦在s-path p k中获得了s-node嵌入：r 1 → ... → rt，我们通过LSTM（长短期记忆）[15]来学习s-path嵌入。形式上，对于每个输入的s-node嵌入 y j，我们通过计算一系列向量 h j ∈ Rd' 来输出，其中0输入门 g ( i ) j，遗忘门 g ( f ) j，0记忆细胞状态 g ( c ) j 和输出门 g ( o ) j：0g ( i ) j = σ(W ( i ) y j + U ( i ) h j − 1 + b ( i ))，(9)0g ( f ) j = σ(W ( f ) y j + U ( f ) h j − 1 + b ( f0g ( c ) j = g ( i ) j ⊙ ˜ g ( c ) j + g ( f ) j ⊙ g ( c ) j0g ( o ) j = σ(W ( o ) y j + U ( o ) h j − 1 + b ( o))，(12)0其中˜ g(c)t,j = tanh(W(c)yj + U(c)hj−1 + b(c))，⊙是元素乘积。我们将LSTM参数集合表示为Θ(lstm) = {W(i)∈Rd'×d,U(i)∈Rd'×d', b(i)∈Rd', W(f)∈Rd'×d, U(f)∈Rd'×d', b(f)∈Rd', W(c)∈Rd'×d, U(c)∈Rd'×d', b(c)∈Rd', W(o)∈Rd'×d,U(o)∈Rd'×d', b(o)∈Rd'}。为了区分s节点的贡献，我们还计算每个s节点rj的注意力分数α'j，如下所示：0其中η'∈Rd'，Q'∈Rd'×d'，b'∈Rd'是参数。因此，我们计算p k的s路径嵌入为：0接近度嵌入。一旦获得了q和v之间每个s路径的s路径嵌入，我们可以计算它们的接近度嵌入。为了统一表示，我们引入ˆP(q,v)作为q和v之间的s路径集合。对于非对称关系，我们将ˆP(q,v)定义为从q