标记图中任意时间Top-k树模式检索

首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂489Any-k：标记图中任意时间Top-k树模式检索杨晓峰东北大学马萨诸塞州波士顿xiaofeng@ccs.neu.edu帕特里克·K Nicholson诺基亚贝尔实验室爱尔兰都柏林pat. nokia-bell-labs.com摘要Deepak Ajwani诺基亚贝尔实验室爱尔兰都柏林deepak. nokia-bell-labs.comMirekRiedewaldNortheastern UniversityBoston，MAmirek@ccs.neu.edu东北大学波士顿，MAwolfgang@ccs.neu.eduAlessandra Sala诺基亚贝尔实验室爱尔兰alessandra. nokia-bell-labs.com在推荐系统、社交网络分析、语义搜索和分布式根本原因分析等不同领域中的许多问题都可以建模为标记图（也称为“异构信息网络”或HIN）上的模式搜索。 给定一个大型图和一个具有节点和边标签约束的查询模式，一个基本的挑战是根据边和节点权重的排名函数找到前k个匹配。 对于用户来说，很难选择k值。因此，我们提出了一个新的概念，任何k排名算法：对于给定的时间预算，尽可能多的返回排名靠前的结果。然后，如果有额外的时间，也可以快速生成下一个排名较低的结果。 它可以随时停止，但可能必须继续，直到返回所有结果。 本文主要研究任意标号图上的无圈模式。 我们感兴趣的实用算法，有效地利用（1）异构网络的属性，特别是标签的选择性约束，和（2），用户的10只探索排名靠前的结果的一小部分。我们的解决方案，KARPET，仔细集成积极修剪，利用非循环性质的查询，和增量引导搜索。它使我们能够证明强大的非平凡的时间和空间的保证，这通常被认为是非常困难的这种类型的图搜索问题。通过实验研究，我们表明，KAR-PET实现的运行时间为毫秒级的大型网络上的树模式与数百万的节点和边缘。ACM参考格式：放大图片作者：杨晓锋，Deepak Ajwani，Wolfgang Gatterbauer，PatrickK.Nicholson，Mirek Riedewald，and Alessandra Sala. 2018年。Any-k：Anytime Top-k Tree Pattern Retrieval in Labeled Graphs. 在WWW 2018：2018年网络会议，2018年4月23日至27日，里昂，法国。ACM，New York，NY，USA，10页。https：//doi.org/10.1145/3178876.31861151引言异构信息网络（HIN）[16]，即具有节点和/或边标签的图最近由于其对许多复杂的现实世界关系建模的能力而吸引了很多本文在知识共享署名4.0国际（CC BY 4.0）许可下发布。作者保留在其个人和公司网站上以适当的归属方式传播作品的权利WWW 2018，2018年4月23日©2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.3186115图1：照片共享网络上的示例查询：为给定的三个指定类型的节点（photo1，user1，user2）找到最重要的从而实现丰富的查询。标签通常用于表示节点的类型及其关系：示例1.1（照片共享网络）。考虑具有三个顶点类型标签的照片共享社交网络：用户、照片和组。用户会连接到他们上传的照片，而照片在发布到组中时会连接到组。最后，用户可以通过加入群组来连接到群组。 为了保持活跃的社区并提醒用户可能感兴趣的照片，社交网络可能会运行图1所示类型的查询：给定照片1和两个用户，用户1和用户2，找到替代组（组2的匹配节点）来发布照片，以便在不直接向用户2发送垃圾邮件的情况下到达用户2。 这是通过识别属于两个组的用户（用户3）来实现的，该用户可以在另一组中发布照片。可能有数百个匹配的三元组（group1，user3，group2），如果没有提前给出user2，则会有更多。在这些情况下，目标通常不是找到所有结果，而是只找到最重要的结果。可以基于节点和边权重来确定重要性，表示距离（或相似性）的权重。那么查询应该返回最轻（或最重）的模式实例.例如，群组的权重可以基于其成员的数量、用户关于她/他有多活跃的权重、以及链接在其建立时的时间戳上的权重（以优先考虑长期关系或更近期的照片帖子）、或其端点的PageRank的总和。这些类型的丰富查询语义也出现在其他上下文中，例如，分布式系统中的根本原因分析OpenStack的Vitrage服务[4]使用路径和树模式来指定规则，以便自动推断所引发警报的根本原因Group1group2照片1user2user1user3首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂490虚拟机和硬件。 大型OpenStack部署-涉及数千台主机和数万台虚拟机和硬件组件-需要模式匹配算法来近实时地推断此类模式的根本原因。我们专注于非循环模式查询一般标记图的有效解决方案。为此，我们提出了任何-k算法的概念，一种新的变体的前k算法。top-k算法利用关于给定k的知识来比“全枚举”算法（其首先产生所有结果，然后按权重对它们进行排名）更快地产生top-k最轻模式在实践中，用户很难预先知道k的值（“我什么时候看够了？”）。 任意k算法通过不需要k的预设值来解决这个问题。相反，任意k算法(1) 尽可能快地返回排名靠前的结果(2) 然后返回排名第二的结果，接着返回排名第三的结果，依此类推，(3) 直到用户满意并终止该过程。换句话说，可以随时然后应该返回尽可能多的顶级结果我们感兴趣的查询对应于子图同构，这是已知的是很难在一般情况下。特别地，齐次图上的子图同构在查询的大小上已经是NP-完全的（即使对于路径情况，因为哈密顿路径是特殊情况）。 标号图包含未标号图作为一种特殊情况。 另一方面，标签通过利用存在的异质性在实践中提供更多的机会来实现更好的性能。 注意，同构困难的关键原因在于“非重复约束”，即，同一个图节点在一个答案中不能出现一次以上。如果没有这个约束，模式搜索将对应于更容易的子图同态问题，可以在PTIME中解决。我们的方法是基于三个关键的见解：（1）对节点或边标签的约束可以显着减少匹配结果的数量;（2）互斥的类型标签“缩小差距”之间的基数同构子图的集合和同态子图的集合（包括所有同构的）。这是因为不同类型的查询模式节点不能映射到同一个图节点，即使算法只搜索同态。在示例照片共享网络中，用户和照片不能代替组节点。在极端情况下，如果查询模式中的所有节点具有不同的类型，则子图同态的任何解也满足同构。这提出了一种方法，积极修剪的同态的情况下，然后过滤器的基础上节点重复的结果模式;（3）在许多现实世界的情况下，输出大小是小的相对于组合大小的模式搜索空间。因此，基于输出大小的算法复杂度界限承诺提供实际有意义的性能保证。解决方案概述 我们的方法将三个概念上独立的步骤组合成两阶段算法。1) 可能的同态模式的搜索空间被修剪到原始图的可证明的最小表示。我们使用来自著名的Yannakakis算法[39]的见解来评估非循环合取查询的答案，以在查询树中仅一次自下而上和随后的自上而下扫描中创建此表示。2) 我们设计了一个新的任意k算法枚举同态树模式。它使用动态编程来执行自下而上的成本计算，然后执行自上而下的引导搜索。3) 最后的修剪步骤移除不满足同构要求的我们展示了如何将前两个步骤组合成一个自下而上和一个自上而下的阶段。然后，我们将第三步整合到组合的自上而下阶段。我们的实验表明，即使在具有数百万个节点和数千万条边的图上，我们也可以在几毫秒内返回排名靠前的结果，而其他方法则需要更长的时间。 我们的实现可以从[2]下载。主要贡献。 我们设计了KARPET（Kernelization 1和R apid Pruning-based E exploration for T ree patterns），一种新颖且高性能的任意k算法，可以快速识别大型图中排名靠前的树模式，然后在给定额外时间时返回下一个排名较低的模式。1) KARPET被设计为一个随时排名算法，enumulates同态子树的总边权重的顺序与强有力的理论保证：我们表明，我们的最坏情况下的时间复杂度返回所有同态结果是相同的充分枚举。此外，KARPET为返回排名靠前的同态结果的时间以及返回同态结果与下一个同态结果之间的时间提供了强上限保证。 对于同态和同构之间具有“小间隙”的情况，即，当“足够多的”同态模式也是同构模式时，这些保证延续到子图同构。2) 我们提出了快速，有效的本地修剪操作，利用标记图的异质性，证明他们也保证强大的全球修剪性能。直观地说，对于子图同态，我们证明了基于1-节点邻域的廉价修剪有效地去除了不属于任何结果模式的所有候选节点。3) 在对比大量的理论工作的子图同构算法，我们的算法是输出敏感的-其最坏情况下的复杂性取决于输出的大小，这是较小的图和查询是更异构的，而不是指数的查询模式的大小4) 我们展示了如何加快搜索排名靠前的同构的答案，推动修剪非重复节点的增量结果枚举算法。2问题的定义和难度我们的目标是找到一个标记图G的最轻的子图，同构于一个给定的树模式Q。 不是在长时间等待之后一次返回所有结果，我们开始设计一种随时算法，其尽可能快地返回排名最高的匹配，然后随着时间的推移递增地返回剩余的结果。定义2.1（任意-k算法）。 任意k算法是前k算法的变体，其中k在算法开始时是未知的。该算法可以随时中断，返回前k个结果，其中k尽可能大。1核化是一种预处理技术，它将原始输入替换为（通常）称为“内核”的较小表示，以降低计算成本。我们的方法列举了一个较小的修剪候选图的解决方案首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂491Q V，E）VEQQQQ（Q）QQ）QN（v，）vG“”定义为∑′w（u，v）。（u，v）∈Ew∶E→R。E∧φ（u）=}。信息（网络G=其中v∈V中的每个n都有一个标号约束ψ∶V→L。我们一起QQ===（）∈ı（）V，E，φ，w） V Eφv∈V∈L N（v，）（）下（）下（（−）⋃ ︀ (⋃︀⋃ ︀ ))>（⋃ ︀(⋃︀⋃︀))表1：本文中使用的符号符号定义（group1，user1）（user3，group1）（d1，c1）（d2，c2）21（d，c）42d1d2user31（用户3，组2）（d1，e1）（d 2，e 1）2（d，e）2G（V， E）具有节点集V和边集E的标号图23个2二个（c1，a）14 1L节点标签的集合φ（）将节点映射到标签的函数（c2，a）（c3，a）2（组1，照片1）c1c2c3Group1一二一1个e1group21e2（组2，用户2）w（）将边映射到权重的函数二一一（c）1具有节点集和边集的树模式ψı（（）Requiredlasforagraphnodematchtoaquireynode1（c2，b）（c3，b）a b f用户1照片1用户2（e2，f）中的叶节点（或终端）集合中的选择的根节点泛邻居集合在with labelλ（）将查询节点VQ映射到图节点V的函数我们将模式的权重定义为边权重的和这也支持基于分配给边缘的概率搜索找到最有可能联系的模式图2：用于匹配图1中的示例查询的候选实例。边集合基于查询模式中的相邻节点的对应对来命名。定义2.4（同态匹配或结果模式）。查询Q的同态结果模式（或同态匹配）是图（VV，EE）使得存在函数λ∶VQ→V，其中等价于最大化边的对数之和（1）u′∈VQ∶ψ（u）=φ（λ（u））;（2）概率对于我们的问题与一个固定的查询模式，最轻和最重的模式搜索可以很容易地转换成对方。它也是简单的修改我们的方法，以支持定义为最小或最大的边缘权重的模式权重接下来我们给出正式的定义。表1总结了重要∠（u，v）∈EQ∶（λ（u），λ（v））∈E. 结果模式的权重为定义2.5（匹配或结果模式）。查询Q的（同构）结果模式（或匹配）是同态结果模式记法定义2.2（HIN，标记图）。 加权异构（V′V，E′E），其双线性映射函数λ∶VQ-1：→1V′.(HIN)是一个有标号的无向图其中是顶点集，是边集，是节点标号函数φ∶V→L，w是边权函数在许多HIN中，节点至少有两种不同的标签：唯一的节点ID和类型（或类）。 在照片共享网络的例子中（见例1.1），标签函数为每个节点分配了“用户”或“照片”等类型。我们的方法可以很容易地扩展到每个节点包括多个标签，以及（多）边标签，节点权重，和有向边。为了简化说明，我们省略了这些直截了当的概括。给定一个顶点和标签，我们用标签来表示v的所有邻居的集合，即，N（v，）{u∶（v，u）∈定义2.3（树模式或查询Q）。 给定一个有标号的图G V，E，φ，w，树模式是根树Q VQ，EQ，φ在Q VQ表示树的根，并且Q表示其叶（或终端，即终端）的集合。度1的节点标记约束可以对特定节点或节点类型的选择进行例如，在照片共享网络场景中，将用户1的Φ设置为特定用户节点的ID将用户1的候选集合限制为仅这一个图节点。类似地，将Φ设置为对类型“组”进行编码的标签将强制仅考虑表示组的图形节点，而不考虑用户或照片。注意，Q是根节点并不是一个限制：树中的任何节点都可以被选为根节点。我们只是利用树模式是根的这一事实，以便更容易地描述我们的算法。上述定义清楚地表明，同构匹配的集合是同态匹配的子集;并且可以通过移除其中多个查询节点被映射到相同图节点的所有那些同态匹配来获得在下面的讨论中，我们还将参考用于计算的中间结果的部分模式（或部分匹配）这些是不完整的实例，其中一些查询节点通过λ映射到NIL。部分匹配的直接后继者是其中NIL目标中的恰好一个被图节点替换的直接后继者，从而通过一个附加节点来增长模式。 后继者是指直接后继者的传递闭包中的任何部分或完全匹配。为了快速访问Nv，，我们依赖于GraphEdge，这是一个为G离线构建的两级哈希索引。它将给定的节点ID v映射到另一个哈希表，该哈希表进而将给定的标签映射到具有标签的v的邻居的集合N v，。 如果没有指定标签，则返回v的二级哈希表中的所有节点和对应的边权重。 该索引可以在时间上与图形大小成线性关系地从头开始批量创建，并且在时间上与更改的大小成线性关系地更新。硬度通常，即使子图同构的判定版本，即，确定给定查询图是否同构于G的子图的方法是NP-完全的。当子图是非循环连接的（即， 树），决策问题的最佳最坏情况时间界限是Koutis和Williams [24]的参数化算法，该算法需要O 2 VQpolyV时间。他们的算法也有匹配的条件下界[25]：对于任何常数ε 0，达到O21 εVQpolyV时间的界将证伪一个长期存在的猜想。请注意，由于决策问题很难，这里讨论的任意k问题至少也很难。首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂492CandEdge∶（u，u）（cc′′（）下u∈ı（Q）Q N（v，）：（↦⌋︀⌋︀′（）= （）∶（）（）下--（′）i′（u，u′）′（c，c）∶′（）（它是边（d，c）（=4）的宽度加上e22的和’’（）下（d、c）2二个（）（）∈（））（）u′u Q c′∈′（u）=′（′）w←（′′w（c，c）+（c）′′i c∈C+=对于节点u和其子节点u之间的每个查询边9：CandEdge（u，u散列索引. 插入cc14：CCandEdge（u，u′）.得到（c）在实践中，我们经常知道特定的节点实例，例如对于照片共享网络示例中的用户1，并且可以戏剧性地其将节点候选者C映射到最小子树权重的列表，对于C的每个孩子Ren具有一个权重。（2）CandEdge（′u，u）返回这些节点。尽管如此，如图2所示，不能从节点a的直接邻域判断边a、cl是否将属于排名靠前的结果或任何结果。更糟糕的是，甚至a的3跳邻域也无法回答这个问题。 因此，模式搜索算法可能遭受昂贵的回溯或在没有广泛的图遍历的情况下无法确定何时已经找到前k个最低权重模式。据我们所知，KARPET是第一个用于图查询模式的排名检索的算法3ANY-K算法接下来，我们提出子图同态的方法;这是子图同构的放松，因为我们不要求从查询节点到树模式节点的映射λ是双射的（换句话说，节点可以在结果模式中重复第5节扩展了同构的方法。KARPET由两个阶段组成：1）从叶子到Q的根的自底向上扫描，以及2）从根到叶子的自顶向下深度优先 第一阶段修剪一些虚假候选，并创建具有“最小子树权重”的“候选图”（下面讨论）。第二阶段修剪剩余的虚假候选者，并执行由子树权重引导的搜索。这里，术语伪候选是指输入图的未出现在任何查询结果中的节点或边。3.1自下而上阶段算法1自底向上的子树权重计算输入：查询，节点邻域索引输出：CandNodeu c u′wmin1：//对于查询树中的每个叶子节点，找到具有所需标签的图节点，将它们添加到候选项中，并将它们的权重设置为02：为做3：cV. φcψuCandNodeu. 插入c无04：//以任何自下而上的顺序遍历剩余的查询节点其将u的候选节点c映射到u的所有相邻候选节点c。我们用图3a、3b和3c说明算法1。它首先将每个查询叶节点u的候选节点插入到对应的候选CandNode u中，将它们的权重设置为零（第2行）。请注意，叶子没有子级，因此表达式中的值为NIL。在图3a中，每个叶存在单个候选者，但实际上，取决于节点约束，对于每个查询叶，它可以是V的更大子集。然后，对于每个查询节点u，算法（i）找到可能的候选节点，（ii）修剪它们，以及（iii）计算最小子树权重更详细地：（）对于通向子的每个查询边，它首先找到所有候选边，存储映射CandEdgeu，u，c，c（第8行）。（ii）然后，该算法仅保持每个查询节点的候选者列表，这些候选者可从查询节点的所有叶中的候选者实例到达（行11）：在图3c中，查询节点组1的候选者列表是cl、c2、c3。请注意，从叶子无法到达的虚假候选，例如，组2中的e1甚至不被访问（与图2比较）。类似地，虽然user3中的d1可以从左侧到达，但它不能从右侧子树到达，因此也被自动修剪。（iii）然后，算法为每个可达节点找到沿着每个查询边u的最小权重，u从c开始（第16行）。例如，在图3c中，用于c2的左权重5被计算为用于跟随的权重的最小值，其是作为边d2、c2（= 2）的权重加上c2（= 2+1）的权重的和的5，或者用于跟随的d2、c3、c4（ = 2+1 ）的权 重的和的5。C3的权（= 2+1）。请注意，我们在这里使用WeI ghtc作为节点c处权重之和的缩写形式，它是从CandNode获得的。这两个新创建的索引加快了在自顶向下遍历期间查找查询模式的子树3.2自上而下阶段我们的算法的第二部分执行自上而下的搜索，在根节点开始，并进行向下的叶子。这是必不可少的两个原因：首先，预先计算的子树权重提供信息，以引导搜索到最轻的模式，然后再探索较重的。第二，自顶向下遍历隐式地修剪子图的所有剩余伪候选5、对于我们TRAversA lVQdo6：//（i）找到与所有子节点u中的候选相邻的候选边7：对于in的子节点，并且候选CandNodedo8：对 于 相 邻 的 b 或 c∈N′ （ c′ ， ψ（u））do′同态，我们将在第4节中证明。再次，修剪实际上通过不到达那些候选而隐式地发生。 为了看到后者，考虑图3c中的组1候选项cl。它是假的，但不能通过自下而上的扫描来删除。然而将10：//（ii）仅保留具有到u的每个子节点的边的候选11：Cu u的子节点CandEdgeu，u. 键12：//（iii）找到子节点13：对于c′∈=C且u的所有子元素renui都是由算法1记录在CandNode中。算法2示出了用于自顶向下引导搜索的伪代码最初，查询根r中的所有候选者c被插入到优先级队列pq中（第3行），其中它们的优先级被设置为15：min We ight16：CandNode（u）. 插入（c（uiwi））自底向上阶段以任何自底向上的顺序遍历查询树，并构造由两个索引结构组成的候选人在图3c中，存在权重为5 3 8的单个候选d2然后，该算法反复弹出顶部元素从pq和扩展的部分模式使用前序遍历。函数NextPreorder返回边，作为父节点和子节点对，接下来将沿着该边扩展部分模式（第12行）。每个扩展的部分匹配的优先级值为通过从以下开始探索G来大大减少模式搜索空间：在自顶向下遍历期间永远不会被访问，因为d1永远不会′′首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂4935：pq. 插入（右（c），Z）（）←3：forc∈CandNode（（Q））do←（）←（）w（c′，c′（）下一页（）下一页（）下一页（）（）-2 + 2+（0+0）。然后将此模式扩展到（d，c，a，b），22（）（）c（d，c）3 2三个（d、c）2三个c（d，c）3 2二个（）下一页直接继承者（c，c，. . . ，c，c）具有相同的优先级w。j12j+1（（）∶（假设Alg。 2弹出的部分图案P =（d，c）（d，c）2二二三user3user3（一）（b）第（1）款（c）图3：最小子树权重计算：（a）在遍历所有叶子之后，（b）在遍历中间层之后，（c）在完成根之后节点候选上方的数字指示存储在CandNode中的最小子树权重;边缘上的数字指示存储在CandEdge中的边缘权重。算法2优先搜索（未示出前元件优化）输入：树模式Q、CandNode、CandEdge输出：Q的所有匹配，按照权重的递增顺序逐个进行1：//用查询根节点的所有候选项初始化pq2：pqPrI orI tyQueU e4：仅由一个节点的Z 部分树c6：//展开pq直到返回所有结果7：当pq.Size> 0时8：oldkey，Zpq. Pop-MI nI m um9：如果Z是完全匹配，则10：返回Z11：其他12：（u，u′）←NextPreorder（Q，Z）▷扩展模式的边4算法分析本节中的所有结果都是针对该问题的放松版本，基于子图同态而不是同构。我们将在第5节讨论如何将它们推广到同构的情况。由于空间限制，证明被省略，但可以在扩展版本中找到[38]。4.1候选图的极小性我们表明，在自顶向下搜索（Alg。2），则将永远不会访问虚假的候选节点如果不存在任何同态结果模式，其中c与q匹配，则查询节点q的候选节点c是 确保没有虚假节点的访问是至关重要的证明强上限的算法成本。定理4.1.如果查询节点节点候选c∈CandNode（q13：forc∈CandNode（u）do（′）Get（）q∈V由Alg访问2，则存在同态结果14：对于由CandEdgeu返回的c ′′，u。cdoQ15：Z = Z。追加（c′）其中λ（q）= c.16：newkey←oldke y）−+CandNode（u））。得到（c，u）+4.2每次弹出，一个结果输入顺序17：pq.PU sh（newkey，Z）WeI ght（c′接下来，我们展示了一个强大的结果，这对建立免疫系统至关重要定义为图案的边权重的和未探索子树的权重在示例中，部分匹配d2，c2被插入到pq中，优先级为8 = 2（边权重）+（2+1）（c2的权重）+3（d2的右子树的权重）。类似地，部分匹配d2，c3以优先级4+（2+1）+3 = 10插入。请注意，这些值是在遍历期间递增计算的（第16行）。考虑将d2展开为d2，c3。d2的优先级为8，新扩展的子树的权重为5，该子树的根位于group1。检索后根据CandEdge，优先级计算为8（旧）-5（新扩展的子树）+4（边的权重）+3（边的优先级）。）= 10（Alg.2）的情况。 然后接下来弹出，并扩展为部分匹配d2，c2，a，优先级为8 = 8d2，c2，a，b，e2，最后是d2，c2，a，b，e2，f--所有这些都具有相同的优先级8。后者作为最小权重解输出 只有这样，具有较高优先级值10的部分匹配d2、c3才被类似地扩展。 每个扩展操作需要从优先级队列中取出操作，访问潜在的边缘一次。重要的算法特性：在自顶向下引导搜索期间，对于每个查询结果，存在至多一个推送和至多一个优先级队列pq上的弹出操作。为此，我们需要以下引理。Lemm A4.2. 部分模式P的优先级值总是小于或等于其所有后继模式的优先级。LemmA 4.3.c1，c2，. . . ，cj），外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂494（d、c）2二个（（d，c）∶8，（d，c）∶10）。n个p-op- deliv（d，c）∶ 8，其中h为2二、二 三二二d（d，c）2 2三个（）∶（）下一页（d，c，a，b，e，f）222（）∶consecutivehomomorphicmatches，is（+r）。HereH=（）’’（）下′′时间复杂度为O（r）。HH⋃︀E⋃︀Q（）⋃︀ ⋃︀（+）（）（+）最终匹配Z-丢弃Z如果真的发生的话此修改具有d2的权重）= 8。它与d2的初始优先级相同，因为edge是确定最小左子树权重5 in的那个对于，由于边d2、c3的权重较高，优先级为10。推送这两个模式后，pq包含被扩展为d2，c2，a8，随后在该模式上重复pop和push操作，每次获得相同的优先级8，直到权重8的顶部结果完 成 。 只有到那时，d2，c3，10的扩建工程才会开始.前端元件优化。基于推论4.4，我们接下来引入对Alg的重要优化二、因为推论保证了部分模式的直接继承者之一算法2. 第4.2节的结果导致强保证。Alg.的空间复杂度 2等于优先级队列的最大大小。推论4.7直接意味着：定理4.8. Alg的空间成本2的上界为rH，rH是子图同态的总结果大小。从用户定理4.9. Alg. 2返回排名最高的同态匹配，以及返回任何两个之间的时间输出度日志outDegree≤rH是相邻点的最大基数pop before将具有最小优先级值，我们避免CandEdge中的n个候选者c：（u，u）（c{（c，w（c，c））}′′推-弹出循环，并保持直接扩展它，只推其他直接继承者。 更准确地说，假设算法刚刚弹出部分匹配Pc1，c2，. . . ，c，i。当将此模式再扩展一个节点时，它将保留在内存对于任何查询图边u，u和候选人C。这些强有力的结果表明，KARPET可以有效地利用选择性标签的限制。例如，如果G中有一千第一直接后继者P=（c1，c2，. . . ，ci，ci+1）遇到这个Alg2永远不会存储超过一千个部分匹配也具有优先级值W，将所有其它直接后继推到PQ。这样，算法仍然对最小优先级元素起作用，但避免了它的push-pop循环。 这个看似次要的优化具有强烈的含义，如以下定理中形式化的。定理4.6. 使用前端元素优化，对于任何k，来自pq的第k个弹出操作产生第k个最轻的同态结果模式，可能需要附加的推送操作，但是不再弹出操作，直到返回该结果模式。CorollA ry 4.7. 无论检索到多少结果，Alg. 2在pq上总共执行的推送操作不超过rH次。 这里rH表示G中同态子树的个数。这直接从定理4.6和下面的观察得出。假设算法继续运行，直到找到所有查询结果此时，它已经从pq中删除了所有部分匹配，队列为空。定理4.6意味着检索所有结果恰好需要r个Hpop操作。如果推送操作的总数超过此值，则队列不会为空。(And显然，任何对阿尔格的处决2在返回所有结果之前停止，则只执行了一部分推送操作在内存中，并将执行最多一千（廉价）计算步骤，以提供下一个结果给用户-无论多大或连接给定的图！接下来，我们证明KARPET的任意时间属性，即， 它可以快速提供排名靠前的结果，然后根据请求提供下一个结果，不会因为产生所有同态匹配而导致性能损失：定理4.10. 产生所有同态结果模式的下限是Ω（rH）;排序它们的成本是O（rH log rH）。Alg. 2具有5同态TO同构KARPET如第3节中介绍的那样返回同态匹配。为了获得期望的同构匹配，函数λ映射查询节点到树模式节点必须是双射的。 为了保证这一点，只需过 滤 出 不 同 查 询 节点 映射到同 一图形 节点的所 有结果 。KARPET可以通过检查Alg中的第15行来执行早期修剪，而不是对最终结果进行过滤。2如果新添加的节点c已经出现在par中4.3算法成本为了避免符号混乱，我们将查询模式的大小视为一个小常量，并在大多数公式中省略它（注意，图案大小等于EQ中的边缘的数量，例如， 5在照片共享网络的例子中。通过包含作为变量来扩展公式是直接的。算法1. 理论最坏情况成本为O E，即，图大小线性：对于每个查询模式边，在最坏情况下访问所有图边。用于构造CandEdge和CandNode的时间增加了所处理的每条边的恒定开销在实践中，由于标签约束，只有E的一小部分将被访问。特别地，通过使用Alg.1，匹配类型（标签）的所有邻居在这些邻居的数量上在时间上线性地被访问空间成本的上限由CandNode和CandEdge的组合大小限定，即，不能超过输入图形大小的EQ以下是第4.3节中成本分析结果的含义。 由于先前被推送到优先级队列pq的一些项现在将被提前丢弃，所以KARPET的空间消耗以及计算成本低于用于找到所有子图同态结果的空间消耗以及计算成本。然而，由定理4.8和4.10建立的最坏情况复杂度保持不变。并且对结果之间的时间的保证（定理4.9）较弱：在最坏的情况下，例如，当只有第一个和最后一个同态匹配表示同构结果时，则连续结果之间的时间从O outDegree log rH增长到O rH log rH。幸运的是，正如我们的实验所表明的，异质性确实导致同态和同构之间的小差距，即，真实世界的性能更接近于O outDegree logrH。6实验我们的实验评估运行时间，内存消耗，和大小的搜索空间探索KARPET对几个查询在返回所有结果之前执行首页>外文书>人文>心理励志> Social Network Analysis andGraph Algorithms for the WebWWW 2018，2018年4月23日至27日，法国里昂495=V ELYelp企业用户提示模板1模板2模板3模板4模板5图4：数据集统计模板和四个数据集对两个基线算法。为了允许可重复的结果，我们的代码可以从我们的项目页面下载[2]。基线算法。 我们选择了两个基线，使我们能够评估我们的两个关键步骤（修剪搜索空间，引导搜索）的性能KARPET的相对贡献。DBLP安然Flickr论文会议关键词作者地址电子邮件主题人用户合影Unguided首先从候选图中计算所有结果，然后才对它们进行排名。由于它使用我们修剪的搜索空间，但不包括任何查询结果的优先级，它作为一个基线，以评估我们的指导搜索阶段的贡献。主干是为了评估我们的积极的基于树的修剪策略的效果。它扩展了用于HIN上的路径查询的最新top-k算法[27]。首先，它识别树模式Q中的最长终端到终端路径R（称为Q的“主干”）。然后，它逐个增量地检索G中最轻的骨干实例。请注意，这样的实例是一个部分匹配，其中较小的未映射子树“悬挂”在主干路径上。因此，我们可以对每个这样的子模式执行Unguided，从而产生一个分治算法。 由于每个子模式是独立的，我们提取每个子模式的最轻的实例，并将这些解决方案与骨干实例合并。这涉及检查重复节点出现以强制同构。 然后探索下一个较重的子树匹配等。给定预定义的k值，算法可以在每次发现新的完全匹配时修剪剩余骨干实例的集合在我们所有的实验中，我们将k的最终值提供给Backbone，以探索该算法可能实现的最佳性能（如果它能够从一开始就猜测正确的k值）。数据集。我们使用四个著名的异构数据集：Flickr[3]，DBLP[27]，Enron[27]和Yelp[1]。图4给出了它们的属性的概述。请注意，Enron、DBLP和Flickr的图表比Yelp更密集。 为了创建单独的边的权重，我们使用边的年龄，该年龄基于边创建时间和查询时间之间的差异具有指数衰减。查询模板。我们创建了图中列出的五个不同的模式模板。五、对于每种模式，我们选择了300种不同的实际节点到查询叶子的分配，这使得我们每个叶子有300个查询模板，用于所有数据集的总共6，000个查询实例性能指标。我们在1和结果总数之间改变k，并在三个性能指标上比较算法。1）运行时间：我们测量从将数据集加载到内存到返回第k个结果之间的时间，报告每个模板的平均值2）内存消耗：我们报告节点的最大数量（即， 由它们包含的匹配节点的数量加权的部分匹配）。3）搜索空间的大小：我们报告在执行过程中存储的部分匹配的总数（由它们包含的匹配节点的数量图5：用于为每个数据集生成查询的模板。形状表示节点类型;青色节点是终端。350300250200150100500电话：+86-0510 - 8888888传真：+86-0510 - 8888888K图6：Enron数据集上模板1实例的同构和同态匹配数实验装置。 实验在Intel Xeon CPU E5-2440 1.90GHz上运行，具有运行Linux的200 GB内存。 我们用g++4.8（优化标志O2）编译了源代码。6.1讨论和亮点为了证明我们的“通过同态解决同构”方法的合理性这产生所有同态匹配，然后我们可以离线确定有多少也是同构情况的结果。在图6中，随着k的增加，我们绘制了这两个数字。它显示了使用来自模板1的查询从Enron数据集获得的代表性结果。线之间的小间隙证实了绝大多数同态匹配也是同构结果模式。图7显示了比较KARPET和Unguided的代表性结果不受k的选择的影响。可以清楚地看到我们的任意k算法如何连续地按顺序返回排名靠前的结果，并且连续输出之间的延迟非常低当Unguided最终返回第一个匹配时，KARPET已经交付了超过85%的所有匹配。最后，KARPET用了4.98秒来输出所有匹配。相比之下，Unguided的批量计算花费了4.31秒，这表明支持anytime属性的开销很小，仅为0.67