本文提出了一种图关联规则GAR，GARs包含了GFD。之前的GFD是用于捕捉图中属性的缺失，而GAR不仅用于捕捉属性的缺失还可以通过GAR中的规则对图上的边进行增加或删除，实现边的预测（关联推断），在现实生活中可以实现实体关系之间的预测，增加了机器学习的分类器，这些规则插入现有的ML分类器，提高了关联推断的准确性。通过GARs可以联想到很多应用，比如说经典的购物推荐这种推荐系统，当路人A购买了一样东西之后，之前购买过这样东西的路人B还购买过什么东西，就可以推荐给路人A。
本文提出一种图关联规则GARs，用来表示图中实体之间的规律。一个GAR是图模式和依赖的组合，它将机器学习分类器作为连接预测的谓词。
GARs能够帮助我们捕捉无模式图中的不完整信息，预测社交图中的链接，识别数字营销中的潜在用户，扩展图函数依赖来捕捉缺失的链接和不一致。
本文用chase的方式形式化了与GARs的关联演绎，并且证明了它的Church-Rosser性质。展示了GARs的可满足性、蕴含性、关联演绎问题分别是coNP-complete、NP-complete、NP-complete，尽管GARs的表达能力有所提高，但仍保持了与其GFD对应物相同的复杂性界限。GAR的增量扣除问题是DP-complete的，而GFDs的是coNP-complete
本文提供了关联演绎和增量演绎的并行算法。使用真实的和合成的图，实验性地验证了并行算法的有效性、可扩展性和效率。
本文已经提出了GAR，通过统一基于规则和基于ML的方法，在一个统一的框架中捕捉缺失的链接/属性和语义不一致。我们开发了以图形为中心的算法，用于并行推导和增量推导关联。实验研究已经证实了这些方法在现实生活中是有希望的。
考虑一下真实生活中的例子：
Marketing：与电视广告等传统营销策略不同，电子商务营销通过对购买和用户行为的关联分析来推广产品，这些分析通常用图形来表示。事实证明，这一点很重要:“购物者点击推荐的访问量仅占访问量的7%，但却带动了惊人的24%的订单和26%的收入”，此外，关联在推荐系统中发挥着至关重要的作用。例如，图1的图G1描绘了电子商务推荐网络，营销的一个规则是这样的:(a)如果购物者Ada跟随一家优衣库，点击其销售的产品长袖连帽衫W，(b)优衣库也销售牛仔布迷你裙，在一些套餐交易中与长袖连帽衫W相结合，(c)如果连帽衫W和迷你裙这两种产品的档次在女性购物活动中相关联，那么Ada也可能对牛仔布迷你裙感兴趣；但是链接不在G1。
Link prediction：关联规则帮助我们预测社交网络中的链接。访问同一个地方的人，有共同的朋友和相似的兴趣倾向于发展友谊。例如，图1中的图G2取自社交网络Gowalla。它建议如下:如果(a)两个人鲍勃和乔有一个共同的朋友苏，(b)他们都喜欢参观咖啡馆豆，(c)如果鲍勃和乔与苏有相同的兴趣，那么鲍勃和乔很可能成为朋友；鲍勃和乔之间的联系在G2中不存在。
Incomplete information：与关系表不同，现实生活图通常没有图模式。因此，更常见的是从图中找到缺失的信息。如图1的G3所示，在电子商务平台采用的知识图中，存在没有品牌或材料的服装项目(例如，冬装)。要使它们成为完整的项目，需要添加缺失的数据。
Catching both absent links and semantic errors：[25，21]已经研究了图的函数依赖关系，称为GFDs。像关系函数依赖一样，GFDs是捕捉语义不一致的通用逻辑语句。然而，GFDs没有抓住缺失的环节，这些环节具有存在语义。一方面，当链接丢失时，GFDs可能无法发现语义错误。考虑取自DBPedia的图表G4，其中英语和法语章节返回法国的不同人口。人们可以用一个GFD来捕捉这种不一致:如果两个记录x和x'指的是同一个国家，那么它们必须有相同的人口。然而，如果缺少x和x'之间的等价链接，那么这个GFD就不能捕捉到错误。另一方面，由于这种不一致，传统的逻辑规则不能连接图1的G5中的国家记录。在无模式图中，问题的规模要大得多。
Incorporating machine learning：关联演绎既需要基于逻辑的方法，也需要基于ML的方法。一方面，我们可以使用ML分类器来预测上述x和x'之间的联系。另一方面，我们可以使用逻辑来解释ML预测，并帮助提高其准确性。例如，如果一个ML分类器“预测”电影《出租车》获得金熊奖和金狮奖(见图1的G6)，那么我们可以得出结论，这个预测是错误的，因为这两个电影节要求它们的参与者是“初次上映”，没有一部电影同时获得这两个奖项。这个例子引起了几个问题。应该用什么规则去捕捉联想？能否同时捕捉缺失链接和语义不一致？有没有可能扩展现有的图形依赖(例如GFDs)来满足需求，同时在表达能力和复杂性之间取得平衡？更好的是，我们能把ML分类器合并到规则中，这样我们就可以统一应用基于规则和基于ML的方法了吗？把这些放在一起，最重要的是，我们能实际使用规则来推断大规模图形中的关联吗？
Rules：GARs用前提条件扩展了图模式关联规则(GPARs)，用有限的存在语义扩展了GFDs。GARs可以将用于链接预测的基于嵌入的机器学习分类器作为谓词，从而通过统一基于规则和基于机器学习的方法来提供捕捉图中缺失链接和语义错误的统一框架。此外，GARs可以将用于链接预测的基于嵌入的机器学习分类器作为谓词，从而通过统一基于规则和基于机器学习的方法来提供捕捉图中缺失链接和语义错误的统一框架。
Deducing associations：本文研究从现实生活中的图表推导出关联。本文通过用GARs扩展chase来形式化问题，以统一应用规则和基于嵌入的ML分类器。本文证明了推论具有Church-Rosser性质，即无论GARs以何种顺序应用，chase都收敛于相同的答案，即使图形可能变异。
Complexity：本文研究了图关联的基本问题，包括(1)判断一组GAR之间是否不冲突的可满足性；(b)蕴涵确定一个GAR是否由给定的一组GAR所必需，以减少冗余的GAR；(c)关联推断，以推断在现实生活中的图中缺少的链接和属性；以及(d)增量推断以推断关联的更改，以响应对图的更新。本文发现，尽管GARs增加了GFDs的表达能力，但可满足性、蕴含性和关联推理问题的复杂性与GFDs相同。除非P = NP，否则GARs的增量推导问题比GFDs (DP-complete vs. cop -complete)略难一些。也就是说，GARs确实在复杂性和表现力之间取得了平衡。
A parallel solution：为了将关联分析应用于实际，我们采用GRAPE的不动点计算模型并行化关联推理过程。本文证明了并行化能保证收敛于所推导出的同一组关联。此外，本文提供了一个并行增量算法来响应更新。现实生活中的图经常发生变化，当图发生变化时，从头开始重新推导关联的代价很高。我们增量地计算关联的更改，尽量减少不必要的重新计算。
Experimental study ：使用现实生活和合成图，本文经验地验证了本文的(增量)演绎方法的有效性、可扩展性和效率。本文发现如下。(1)通过统一基于规则和基于ml的方法，GARs能够有效地进行关联推理。本文的方法F-measure值高于88.3%，准确率分别比现有的ML和规则方法高21.3%和28.2%。(2)并行演绎方法高效、可扩展性强;用12个处理器对13亿节点和边的图进行演绎，比现有的演绎方法快18.1倍。(3)增量演绎比批量演绎的表现更好，即使更新的∆G高达G的25%，即 当|∆G| = 10%|G|时，快4.3倍。
本文主要研究关联的(增量)演绎。除了直接应用外，同样的技术也适用于图形数据清理[22]、欺诈检测[46]和注释分析[30]。例如，把这个和[22]放在一起，我们可以开发一个统一的过程来确定地修复缺失的环节和不一致之处。
本文结果的证明可以在[19]中找到。
相关的工作。本文将相关工作分类如下：
关联规则和图依赖关系：关联规则旨在捕获事务数据中的项关系，并在关系数据集上被证明是有效的。类似的规则也被应用到图上，通过提取关系来分析社交网络。GPARs直接在图上定义关联规则，用于图数据分析和知识图搜索。
与基于规则的解决方案不同，机器学习将图关联分析形式化为链接预测问题。基于统计学习，链接预测模型学习每个实体和关系[34]的向量嵌入。他们通过加法函数[10]、基于产品的函数[53,61]或深度神经网络[47]预测嵌入的链接。虽然这些模型表现出了竞争性的表现，但它们的预测误差是无法解释的。
图函数依赖关系最近被提出用于RDF[8,32,17]和属性图[25,21,20]。这些依赖关系被表达为通用逻辑句，用于捕获图中的语义不一致。也有人研究图上的元生成依赖关系(TGDs[4])[13, 14]，这是用普遍和存在逻辑量词定义的。
这项工作的新奇之处包括以下几点。
（1）这是第一次将ML分类器整合到逻辑规则中进行关联推理。一方面，这些规则插入现有的ML分类器，提高了关联推理的准确性。另一方面，它们可以解释ML分类器在逻辑上预测的链接。
（2）本文提出了一个第一个框架来捕获语义不一致和缺失关联在同一过程中。事实上，不一致也可以建模为错误的关联(第4节)，并且应该在一个统一的关联框架中处理。这就是为什么我们选择扩展GFDs[25,21]来捕获缺失的链接和属性，而不是从头开始定义一类新规则。
（3）GARs在表达性和复杂性之间取得了平衡，对GPAR和GFDs进行了必要但最少的扩展。众所周知，当通用逻辑规则和存在规则放在一起时，它们的静态分析往往是不可确定的，例如，TGDs (cf.[4])的隐含问题，以及将功能依赖关系和包含依赖关系放在一起[12]。GARs用有限存在语义学丰富了通用语义学，而它们的可满足性和蕴涵性问题在coNP和NP中分别是可决定的，与通用语义学相同。
尽管GARs的复杂度边界与GFD的复杂度边界相似，但证明却截然不同
（4）GARs使用先决条件扩展了GPARs[23]。这项工作提供了第一个使用chase的关联演绎公式，以及关于图关联规则推理的第一个基本结果，这在[23,24]中没有研究过。
并行推理。基于以下原则，已经开发了几种并行算法用于图模式匹配和GFD检查:(1)工作单元分布;(2)数据复制;(3)模式分解和多路连接;(4)通过获取数据并验证边来扩展模式匹配。
这项工作采用了一种不同的方法。(a)我们首先开发了两种序列算法来进行关联的演绎和增量演绎。在此基础上并行化了GRAPE的不动点模型，并保证了[26]的收敛性。这与先前的GFDs算法不同[25,22,20]。(b)我们同时处理一组GARs，而不是单一的图案。此外，强制gar会使图的拓扑结构发生突变。相比之下，先前的算法假设静态图;他们不为协会扣除工作。(三)我们提出一项策略，以减少不同类型的更新在递增扣减方面的冗余相互影响。(d)据我们所知，增量式演绎算法还产生了第一个增量式图修复算法。
假设三个可数无限的符号集，分别表示为Γ, Υ和U，分别表示为标签、属性和常数。
有向图G = (V,E,L,FA)，其中V是有限的节点集合；E是(v, ι, v')中v到v'的边的集合, ι ∈ Γ，v和v'是V中的节点；L是节点和边的标签，L(v)∈Γ;，L(e)∈Γ;；FA是一个等式元组
图形模式
，其中VQ是模式节点的集合；EQ是模式边的集合；LQ是模式节点和模式边的标签；
是变量的列表；µ一个将映射到VQ的双射函数；
例2：图1给出了六种模式。例如，图案Q1显示商店w销售z1和z2类的产品y1和y2, y1和y2在特价中链接，z1和z2在订单活动中相关，客户x跟随商店w并点击产品z1。图1中的模式Q2-Q6可以类似地解释。
模式匹配：采用下面的同态语义。图G中的模式
的匹配是h从Q到G的映射使得(a)对每个节点u∈VQ，LQ(u) = L(h(u))，(b)对每条Q中的边e = (u, ι, u')，e'= (h(u), ι, h(u'))是G中的一条边。表示匹配向量
是所有x∈
的匹配h(x)组成的
模式
有字段：（1）属性字段x.A ；（2）边字段ι(x, y)，其中ι是Γ中的一个标签； （3）ML字段 M(x, y, ι)，是一个ML分类器，当且仅当他预测边(x, ι, y)存在时，返回true；（4）变量字段x.A = y.B； （5）常量字段x.A = c，其中c ∈ U
GARs图关联规则φ定义为：
，其中是一个图模式，X和Y是的字段的连接。称和X → Y为φ的模式和依赖。常量和变量字段x.A = c和x.A = y.B指定属性的值关联，属性x.A和边ι(x, y)强制了属性和边的存在，即分别是属性和边关联。此外，可以“插入”现有的训练良好的ML分类器M用于链接预测，并将其视为一个布尔谓词，即，如果M预测从x到y存在标记为ι 的链接就返回true，否则返回false。我们很快就会看到，它允许我们在逻辑规则中使用基于嵌入的ML分类器，并在逻辑中解释这些分类器。
例3：我们可以使用下面的GARs来推断示例1中描述的关联，使用图1中的模式Q1 - Q6。
(1) φ1= 
，其中Y1由like(x, y2)这样的边组成（如图中的红线）。他表示如果产品y1和y2在商店x售卖了并且被连接在一个成套服务中，它们对应的类别在购买活动中是相关的，并且如果客户x点击y1，跟随店铺w，那么x也是产品y2的潜在客户。
(2)φ2=
，其中X2是x.interest = x'.interest∧x''.interest = x'.interest，interest是人的一种实体属性并且Y2是friend(x, x'').它指出，如果x'是x和x''的朋友，x、x'和x''都访问同一个咖啡馆y(在Q2中指明)，如果三个人有共同的兴趣(在X2中)，那么x和x''有可能成为朋友。
(3)φ3=
，其中Y3定义为x.brand∧x.material。强制每个服装实体都带有品牌和材质属性。
(4)φ4=
，其中Y4是x.population = x'.population，population是国家实体的一种属性。它说关于同一个国家的记录应该有相同的人口。它是一个GFD来捕捉不一致。
(5)φ5=
，X5是x.name = x'.name∧M(x, x',equivalent)且Y5是equivalent(x, x')。它指出，如果两个国家x和x'有相同的名字，并且ML分类器(链接预测器)M预测它们相等，那么应该添加链接(x,equivalent, x')。它利用现有的ML分类器来捕获关联。
(6))φ6=
，其中X6是M(z, y',receive)∧y.name=“Golden Bear”∧y'.name= “Golden Lion”。这里的false是一个布尔常量，表示为y.name=c和y.name=d，用于不同的常量c和d。凭直觉，它说一部电影不可能同时获得金熊奖和金狮奖。这表明如果M(z, y',receive)返回true，那么分类器M需要进一步训练。
通过以上的例子可以看出，GAR跟GFDs是包含关系，即GFD包含于GAR，GAR的依赖中包含有属性的等式、析取合取表达式、边字段等，而GFDs只包含了属性的等式，如x.name=y.name
语义：为了解释GAR φ=，我们使用以下符号：用
表示图G中Q的匹配，l表示
的字段。将 h(µ(x))写作h(x),其中µ是Q中从
到Q中节点的映射。
（a）当l是x.A时，属性A存在于节点h(x)
（b）当l 是边ι(x, y)时，存在一条标记为ι的边从 h(x)到h(y)
（c）当l是M(x, y, ι)时，这个ML分类器M预测边(h(x), ι, h(y))
（d）当l 是x.A=y.B时，属性A和属性B分别存在于节点h(x)和h(y)，并且h(x).A = h(y).B
（e）当l 是x.A=c时，属性A存在于h(x)，并且h(x).A = c，我们说 满足字段l用|=l 表示。如果满足X中所有字段，则|=X，如果X是空，则|=X。如果|=X蕴含|=Y则写作|=X→Y。如果对于G上Q的匹配有|=X→Y，则图G满足GAR φ。如果对于所有φ ∈ Σ有G |= φ，则称图G满足一个GARs集合Σ，表示为 G |= Σ。可以看出上面的5个条件中(b)和(c)两个条件时新增加的，这俩条件时GFDs所没有的。
例4：图1中图G2和GAR φ2=其中X2是x.interest = x'.interest ∧ x''.interest = x'.interest ，Y2是friend(x, x'')。因为存在匹配h1:x →“Bob”, x'→“Sue”, x''→ “Joe”, y→“Beans”使得|= X2，但是G2不存在边(“Bob”, friend,“Joe”) ，则G2|≠ φ2。因此
|≠ X2→ Y2，即见证G2|≠ φ2，相似的对于其他的 i ∈ [1,6]有
特例：单独挑出GARs的三个特例。
（1）GFDs和图实体依赖(GEDs)[25,21]是仅用常量和变量字段定义的GARs，假设节点id是一个特殊属性。也就是说，GARs使用属性和边的存在语义扩展了GFDs和GEDs，并允许ML分类器作为谓词。例如，例3中的φ4是GFD，但其中的其他GARs不能表示为GFD或GEDs。GARs可以捕获丢失的链接和语义错误，而GFDs和GEDs只检测不一致性。
（2）GPARs是GARs 
(∅ → ι(x, y))，其中X→Y不指定先决条件X，并且Y是单个边字段ι(x, y)
（3）GARs统一了逻辑和ML方法。一方面(M(x, y, ι) → ι(x, y))插入ML链接预测器M(x, y, ι)，即例3中的GAR φ5。另一方面GARs (ψ → M(x, y, ι)) 帮助我们解释为什么M(x, y, ι) 用条件ψ预测为真。例如，从电影和奖项的文本描述中提取属性，φ6中的ML分类器M可以被解释为类似
(z.name = y'.movie_name ∧ z.director =y'.movie_director → M(z, y',receive))的规则
GARs中的ML分类器
GARs支持基于嵌入的ML分类器用于链接预测。分别用
和
表示实体集合和关系集合，这些ML分类器将图中的每个链接视为一个三元组(h、r、t)，其中h∈是head，r∈是relation，t∈指的是三元组的tail。给定正/负的三元组作为训练数据，分类器应用张量因子分解来学习实体和关系的向量表示。学习过程中，正三元组通过预定义的相似函数引导分类器嵌入相似的向量，而负三元组则强制嵌入不同的向量。这里考虑所有类型的实体和相关信息(所有相关属性和边)。
训练完成后，这样一个ML分类器M的行为就像一个布尔函数。给定两个实体h', t'和一个关系r', M(h', r', t')返回一个布尔值。即M将h'、t'、r'映射到预计算向量
、
、
作为其嵌入。然后，它将这些向量提供给相似性函数，并返回true (false)如果分数高于(低于)阈值。这种ML链接预测器的假设是，所有的实体和关系都已经被训练数据覆盖，并且被M学习;因此M可以找到h'、t'和r'的嵌入，并预测h'是否通过r'边与t'相连。这就是最先进的基于嵌入式的SimpIE[34]和complex[53]的工作原理。
该研究的中心问题之一是推导关联性。有两种类型的关联:(a)实体之间的关联(边字段)和属性到实体的关联(属性字段);(b)值与属性的关联(变量和常量字段)。
我们通过用GARs追踪图来建模关联推理。下面我们首先将chase从关系扩展到图(第4.1节)，然后证明它的Church-Rosser性质(第4.2节)。基于这些，我们将在下一节中制定关联演绎问题。
有图G = (V, E, L, FA)和一个GARs集合Σ
Chase graphs：chase graph Gc是
，其中V和L来自图G，Ec= E ∪ ∆Ec，且
= FA∪∆，∆Ec包括chase过程中由ML字段和边字段添加的边，而∆FAc包括由属性、常量和变量字段添加的属性。
Chasing 定义G在Gc处的σ追逐步骤为
，其中φ=是Σ中的一个GAR，是Gc中Q的一个匹配使得（a）|=X；（b）如果|= l 还不成立，
通过强制一个字段l∈Y拓展Gc。的定义如下：
如果l是x.A，若A
则通过添加属性A等于特殊字符“#”到∆
(h(x))拓展Gc，若A已经在中，属性A的值保持不变。
如果l是ι(x, y)，则用边 (h(x), ι, h(y))拓展Gc
如果l是M(x, y, ι)，则通过添加边 (h(x), ι, h(y))拓展Gc。作为副产品，它建议设置M(x, y,ι)为真，即，它向ML预测器M提供反馈。
如果l是x.A = y.B，则通过（a）若属性不存在，添加属性A到∆(h(x))，添加属性B到∆(h(y)) （b）让 h(x).A = h(y).B
如果l是x.A=c，若A则通过添加属性A到∆(h(x))并且让h(x).A = c.
Consistency：chase过程中可能会出现冲突。
如果它强制字段 l，使得(a) l 是x.A = y.B，但h(x).A = c和h(y).B = d是在Gc中，c≠d，或(B) l是x. a = c, h(x).A=d时在Gc中，c≠d，那么它是无效的。否则该步骤是有效的。如果a或b发生，我们说
是不一致的。
Chasing sequences. 以
=G开始，∆和∆Ec均是∅。G被Σ的chase序列ρ为
其中对所有i∈[0,k−1]，Σ中存在一个GAR φ = 
(X →Y)且
中图模式Q的匹配h使得
是有效的chase步。
如果不存在GAR φ∈ Σ且
中φ的模式Q的匹配h使得chase 步是有效的且能够被扩招，则序列终止。更具体地说，chase的终止条件为以下两条:
（a）不能被扩展且
是一致的(i∈[0, k])，如果这样，则chase 序列是有效的且结果是
（b）在某些步i ，是不一致的，如果这样则chase 序列是无效的，结果被定义为⊥
先前关于chase图的工作主要改变属性值。相比之下，当chase GARs时，Gc的拓扑结构可能通过增加新的边和属性被改变。因此，当Gc扩展到
时，我们必须检查GARs中图形模式的新的可能匹配。
例5：考虑图1所示的图G2。假设Σ仅由例3中的一个GAR φ2=
，X2是x.interest =x'.interest ∧ x''.interest = x'.interest,Y2是friend(x, x'')。从
= G2，我们有以下追赶步骤:
（1）
，其中匹配h1是例4中的，即h1:x→“Bob”, x'→“Sue”, x''7→ “Joe”, y→“Beans”，因为Bob和Sue的interest相同，且Sue和Joe的interest相同，则Bob和Joe是朋友，所以
是通过添加边(“Bob”, friend, “Joe”)扩展
，
（2）
，其中h2的定义如下：x →“Bob”，x'→“Joe”，x''→“Eva”，y →“Beans”，同（1），有
通过使用φ2添加边(“Bob”, friend, “Eva”)扩展。注意只有在步骤(1)中添加了边(“Bob”, friend, “Joe”)之后，匹配h2才存在变化后的chase 图中
主要关心的是是否chase总是以相同的结果结束。如果对于所有的图G和所有的GARs集合Σ，所有使用Σ进行chase得到的G的序列都最终得到相同的结果（不管Σ的哪个GARs或者哪个GARs使用的顺序），则我们说这个GARs的chase是Church-Rosser。
定理1:用GARs进行chase有Church-Rosser性质
通过定理1，我们把Σ chase G的结果定义为Σ chase G的任意终端序列的结果，用Chase(G，σ)表示。如果序列有效，Chase(G，σ)有Gc的形式。我们把在G中但不在G中的边和属性称为由σ推导出的G的关联。直觉上，它们缺少链接和属性。我们用dedu ced(G，σ)表示所有这类推导出的关联的集合。如第3节所示，我们可以使用推导出的关联来重新训练M，提高其准确性并解释其预测。
通过定理1，我们把Σ chase G的结果定义为Σ追G的任意终端序列的结果，用Chase(G，Σ)表示。如果序列有效，Chase(G，Σ)有Gc的形式。我们把在Gc中但不在G中的边和属性称为由Σ推导出的G的关联。直觉上，它们缺少链接和属性。我们用deduced(G，Σ)来表示所有这些推导出的关联的集合。如第3节所示，我们可以使用推导出的关联来重新训练M，提高其准确性并解释其预测。我们称在Gc中但不在G中的属性和边为使用Σ推导的G的关联。我们使用deduced(G,Σ)来表示所有的推导关联的集合
接下来我们解决可满足性、蕴涵、关联推理和增量推理问题。我们的主要结论是，对于GARs而言，这些问题要么保持与GFDs相同的复杂性，要么比GFDs稍微困难一些，尽管GARs的表达能力有所提高。然而，证明是相当不同的，例如，处理由ML分类器引入的意外冲突。
满足性：输入：一个GARs集合Σ ； 问题：是否存在一个图G使得G |= Σ且对于每个GAR
(X → Y ) ∈ Σ，Q是否有一个G中的匹配？
直觉上，这是为了确保Σ是合理的，并且所有GARs可以同时应用而没有冲突。对GFDs来说，可满足性问题是coNP-complete的。我们接下来表明，这个问题对GARs来说并不难。
定理2：可满足性问题是coNP-complete的。
蕴含问题：如果所有的图G存在若G|=Σ，则G|=φ，则称为一个GARs集合Σ蕴含一个GAR φ表示为Σ|=φ，也就是说φ是Σ的逻辑结果，因此是多余的。
蕴含问题是：输入：一个GARs集合Σ和GAR φ； 问题：Σ|=φ ？
研究这个问题是为了消除多余的规则，从而加快推导过程。使用GARs进行chase不产生新的节点，且新增加的内容仅限于GARs中指定的内容，所以最终得到的是一个有限的图。
定理3:蕴涵问题是NP-complete的。
推导(Deduction)：为了简化讨论，我们着重于推导缺失的属性和缺失的链接，尽管本文开发的技术可以很容易地用于推导所有关联，包括与属性相关的值。也就是说，GARs可以推导出缺失的链接/属性，并在同一个框架中纠正不一致。
有图G = (V, E, L, FA)，对于节点v ∈ V和属性A ∈ Υ，如果A不存在与G中，称v.A为G中节点v的候选属性；对于节点v1,v2∈ V和标签ι ∈ Γ，如果边 (v1, ι, v2)不在G中，称之为G的候选边。又称属性v.A和边(v1, ι, v2)为G中候选联系，表示为α
关联演绎问题陈述如下：输入图G，GARs Σ,和一个候选联系α； 问题：是否α是G中通过Σ 推出的联系？ 即是否α ∈ deduced(G,Σ)？
这个问题是为了解决计算dedced(G，Σ)的复杂性，dedced(G，Σ)是图G中缺失的所有链接和属性的集合，由GARs的集合Σ来推导。
定理4：GARs的关联演绎问题是NP-complete的。
增量推导(Incremental deduction)：我们考虑图G的批量更新∆G，它是单元更新的序列：
1、边插入(insert e)，可能带有一个新的节点。 2、边删除(delete e)，以及0层的节点
这些可以模拟例如边缘标签的修改。使用G ⊕ ∆G表示图G通过∆G更新，使用deduced∆(G,∆G,Σ) 表示关联的deduced(G,Σ)集合响应更新∆G的变化集合，即关联在deduced(G,Σ)中，但不在deduced(G ⊕ ∆G,Σ)中，反之亦然。
增量推导问题陈述如下：输入：图G，GARs的集合Σ，∆G到G的批量更新，G或G ⊕∆G的候选关联α； 问题：是否α ∈ deduced∆(G,∆G,Σ) ？
根据定理4，从头开始计算deduced(G ⊕ ∆G,Σ)的成本很高。因此我们通过最大限度地重复使用deduced(G,Σ)逐渐地计算deduced(G,Σ)的改变，使得deduced(G ⊕ ∆G,Σ) = deduced(G,Σ) ⊕ deduced(G,∆G,Σ)，当∆G很小时，
通常也是如此，这样计算成本更低。
定理5：增量演绎问题对于GARs来说是DP-complete，当图G或更新∆G到G的大小不变时，它仍然是DP-hard。
需要一个master P0和n个workers P1 - Pn，GRAPE将图G分为n个片段（F1-Fn），每个worker Pi维护自己的片段Fi。
GRAPE模型有一个PIE程序，这个程序由PEval，IncEval，Assemble三个顺序算法组成。
PEval是给定一个询问Q和一个图G，计算G中Q的回答Q(G)
IncEval是给定Q,G,Q(G)并更新M到G，计算Q(G)的改变∆O使得Q(G ⊕ M) = Q(G) ⊕ ∆O
Assemble通过PEval和IncEval收集每个worker在本地计算的部分答案，并将它们组合成一个完整的答案；
（1）部分估计PEval。在第一个超步，PEval的每个worker Pi在每个Fi上局部并行地计算Q(Fi)，之后每个worker生成一个由更新参数
组成的消息并且将它发送到master P0。
（2）增量计算IncEval。在接下来的超步，Q(Fi)的部分回答由IncEval迭代更新。（a）master P0将
应用于来自上一个超级步骤的消息Mi，从而解决冲突。然后聚合值被路由到相关的worker。（b）收到消息Mi后，工作Pi通过将Mi视为更新，每个worker Pi并行递增地计算Q(Fi⊕ Mi)。在每个超级步骤结束时，worker Pi向P0发送一条消息，该消息包括对Fi的更新参数的更改，就像在PEval中一样。
（3）终止。该过程继续进行，直到它到达一个固定点，即不再有更新参数的改变。然后调用Assemble将所有部分答案组合成Q(G)。
PIE程序保证在单调条件下收敛于正确答案，只要顺序PEval，IncEval和Assemble是正确的
接下来提供一个PIE程序，用PDeduce表示。
challenges：如第4节所示，推导关联的主要任务是计算同态映射。大多数子图匹配方法对图进行预处理以建立静态索引，并通过访问索引中的候选项来枚举匹配。然而，由于以下原因，这些在我们的环境中不起作用。(1)在追踪过程中，图形会发生变异，并在运行时引入新的匹配，这与静态图形和索引相反。(2)现有方法通常以单个图形模式作为输入，并找到其匹配。相比之下，chase处理一组GAR，PDeduce必须决定使用哪些GAR以及GAR的应用顺序。(3)即使对于GAR中的单个模式，PDeduce也只需要识别缺少关联的匹配子集，而不是所有匹配
有鉴于此，我们建议(1)以增量方式仅计算来自活跃的GAR的模式的匹配；(2)使用动态匹配顺序和动态维护的简单索引；以及(3)采用关联引导策略来删减匹配。这些有助于我们避免检查对deduced(G,Σ)没有贡献的无用匹配。为了简化讨论，我们假设图是通过边割分割的，并且所有的模式都是连通的。
1、PEval：PDeduce的PEval如上图，它以一组GARs和图G的一个片断Fi作为输入，推导出一组与Fi和Σ有关的关联Q(Fi)。它为Fi中的每个节点v使用两个状态变量v.link和v.attr，分别记录v的相邻边和属性值。它还使用了一个“全局”状态变量Fi.H来存储Σ中模式的部分匹配，这些模式涉及驻留在其他workers处的节点，其中部分匹配仅映射模式节点的子集。Fi的更新参数包括(a) Fi.H将部分匹配传递给其他workers，以及(b) 边界节点v的v.link和v.attr用来协调值，其中边界节点是那些在跨越不同片段的边上的节点的
跳内的节点。
PEval算法迭代应用Σ中的活跃GARs，由片段Fi中的活跃节点引导(第2-10行)。如果一个GAR（节点）可以在当前迭代中推导新的关联的chase步骤中执行（包含到一个映射中），那么它就是活跃的。活跃的GAR和节点被分别收集在集合ψ和
中，这些GAR和节点最初分别是Σ和Vi中(第1行)。对于每个活跃的GAR，它首先在某些条件下提取一组部分匹配集合T(第5行)，然后通过过程ExpandAssoc完成它们并推导出关联Ac(第6行)。在每次迭代结束时，它用本次迭代中累积的新关联更新Fi(第8行)，并为下一次迭代调整ψ和(第9行)。 迭代继续进行，直到不能推导出新的关联(第10行)。过程中推导出的关联存储在Q(Fi)中。
PEval采用了以下新技术。
Indices索引：我们维护(a)Σ中出现的每个模式节点标签ι(通配符除外)上的索引，以获取Fi中标签有ι的节点；(b)三元组<v, ι, η>上的索引，用于获取与标记为ι的节点v相关的边，并链接到标记为η的节点。当新推导出的边被添加到片段Fi时，三元组上的索引被动态更新。即维护Σ中节点的标签和边的标签，但是因为边是会增加的，所以这个边的索引也是会变的。
Match extraction匹配提取：对于活跃的GAR
，PEval将文字X和Y中的模式节点
映射到Fi中的节点，以提取部分匹配
(第5行)，这样
可以（不可以）满足X（Y） 。这是根据模式匹配的局部性，通过使用模式节点标签上的索引并选择活跃节点CV的|Q|跳内的节点来实现的。可以验证只有这种形式的部分匹配能够促成新的关联。
Match completion. 过程ExpandAssoc按照动态候选大小顺序(第6行)，通过将剩余的
迭代映射到Fi中的节点来完成部分匹配。也就是说，每次它映射一个模式节点u，该模式节点u连接到一个匹配的模式节点，并且当前具有最小数量的候选。使用相关三元组上的索引来检查候选项，并且每个扩展的部分匹配不应该满足X → Y。一旦部分扩展到完全匹配
且包含CV的活跃节点，则直接推导出相关关联，并在Y中的模式节点已经映射到中时修剪的所有后续扩展(即关联引导修剪)。ExpandAssoc还返回一组部分匹配集合Hp，这些匹配涉及边界节点，因此需要在其他工作机上扩展。状态变量Fi.h用部分匹配Hp扩展(第7行)。
Match extraction与Match completion的区别是：前者是完成X中所有字段的部分匹配，但是只能满足X，不能满足Y，而后者是完成GAR中除了X和Y中所有字段的部分匹配也不能满足X → Y
Active GARs and nodes.
每次迭代后，我们用新推导出的关联
中涉及的节点修正CV，并通过下一次迭代的过程SuccGAR导出活跃GAR(第9行)。扩展将节点归纳到其标签的模板，SuccGAR挑选前提条件(或模式边)与中的关联具有相同的模板的活跃GAR。例如，如果一个GAR在其X中有一个文字X.A = y.B，并且有一个新的关联V.A = 1与L(v) = LQ(x)，那么它就变得活跃。
2、IncEval
如下图所示，PDeduce的IncEval也逐步推导出新的关联。在worker Pi，它由消息Mi触发，该消息Mi包括片段Fi中边界节点的状态变量的所有变化，以及将在Fi进一步扩展的一组部分匹配。与最初使Fi中的GAR集合σ和Vi节点集合活跃的PEval不同，IncEval根据消息Mi中传递的变化和部分匹配来确定最初的活动节点和GAR(第1-2行)。
它将接收到的更改直接视为∆Fc，并用∆Fc更新片段Fi(第3行)。此后，IncEval迭代地应用活跃的GARs来推断与Fi(第4行)相关的新关联，沿着与PEval中相同的路线，即上图的第2-10行。不同的是它还考虑了Mi中的部分匹配，像提取部分匹配一样展开。IncEval将迭代累积的推断关联存储为部分结果Q(Fi⊕Mi).在初始化结束时，Fi中边界节点的状态变量的变化被发送到P0。主P0然后聚合更改并发送消息，就像在PEval中一样。
3、Assemble
当不能推导出更多的关联时，assemble从所有worker Pi中获得部分结果Q(Fi⊕Mi)的联合，即从所有片段中推导出的关联。虽然PEval和IncEval在多个workers上同时计算关联，但这种并行关联推导方法的正确性是有保证的。
命题6: PIE程序PDeduce正确计算出Σ并行追G推导出的结果(G，Σ)。
例6：图3所示的片段图G（不包括虚线边缘），其中v1-v8表示人，u1-u2是类，u3-u5是产品，w1表示商店，w2-w3表示风格，边b1-b10分别是related_to, type, deal,sell, friend, follow, click, accept, fashion,like. 考虑一组GARs集合Σ包含φ1= 和φ7=
，其中Y1由like(x, y2)这样的边组成，Q7如上图所示。给定图G和Σ，φ1中Q1的匹配
在第一次迭代中由PEval在worker P1提取，其中x→v1，w→w1，y1→u4，y2→u3，z1→u2和z2→u1。由于已经是一个完全匹配，并且
，所以它在P1增加了关系(v1,like,u3)，通过关联引导修剪，丢弃与x→v1和y2→u3的其他部分匹配。因为Q7具有与新推导的关联共享相同模板的模式边(x'，like，y),所以φ7在第二次迭代中被视为活跃GAR。PEval接下来提取Q7的部分匹配
，将x'映射到活跃节点v1，y到u3。当通过程序ExpandAssoc完成时，因为z只有一个候选项w2，而x有四个(v2、v3、v5和v7)，所以Q7的z映射在x之前。事实上，只有Q7的单个完全匹配最终从扩展，并产生一个新的association(v5,like,u3)。PEval还在worker P1的第一次迭代中发现了Q7的部分匹配
。它将x映射到v8，x'映射到v4，y映射到u5。
由于涉及驻留在worker P2的v8和u5(交叉边缘由两个worker维护)，的部分匹配将被发送到P2进一步完成。在PEval结束时，主P0从所有片段中收集边界节点v的状态变量。它应用聚合函数faggr(未显示)来协调v.link和v.attr，并将聚合和部分匹配作为消息路由到相关worker。如果任何节点的属性v.attr中出现冲突，P0立即终止与⊥.的过程。
IncEval通过将Q7的唯一剩余模式节点z映射到w3来完成它。然后，他产生一个缺失的link(v8,like,u5)，推断为一个新的关联。这是worker P2的局部边并且他将被用于更新P2的片段和索引
此算法就是先寻找满足X但是不满足Y的部分匹配，再找到满足GAR但是不满足X→Y的部分匹配，如果需要两个worker来确定这个匹配，则worker1将相关的信息发送给worker2，由worker完成匹配并最终生成新的association，如果单个worker就能完成匹配，则由单个worker生成association。
本文提出了GAR，通过统一基于规则和基于ML的方法，在一个统一的框架中捕捉缺失的链接/属性和语义不一致。通过建立GARs的上下界解决了经典的三个问题，所有的都是匹配的。开发了以图形为中心的算法，用于并行推导和增量推导关联。实验研究已经证实了这些方法在现实生活中是有希望的。未来工作的一个主题是通过将GARs视为软规则来探索GARs的应用。另一个主题是为GAr寻找非嵌入的ML分类器。第三个主题是开发发现GAR的并行算法。
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
