1. 摘要

因为图数据库的复杂模式和不同的信息描写叙述方式，对于非专业用户来说查询复杂的图数据库是异常困难的。

一个好的图查询引擎应该支持多种转化——同义词、缩略词、简写以及本体等等，而且应该可以对搜索结果进行一个非常好地排序。

基于此问题本文提出了一种新型的查询框架来方便用户查询，解放了为构造查询图而抓耳挠腮的用户群。

2. 应用背景

2.1 应用

图数据库也是一种流行的数据存储方式。如知识图、信息网络以及社交网络等应用的数据都存储在图数据库中。由于图数据的无模式或者模式太复杂以及信息的多种描写叙述方式使得基于图数据的查询变得很困难。对于一般用户来说更是望之却步。

图2-1 a为图数据库中的一部分，若查询大约30岁而且跟“Universityof California Berkley”以及“Mission:Impssible”相关的演员。易得图2-1中绿色与黄色部分均为比較好的结果。图2-1 b为一个可以表达查询语义的查询，可是现有的图数据库查询仅仅能查询到绿色的部分或者一个都查不到。

原因在于结点的信息都不匹配。而原有查询又不支持语义转换或者仅仅支持一种转化。

图2-1 图数据库G

该文解决的问题能够描写叙述为：给定一个查询Q以及数据库G，找出图数据库中全部由Q经转换函数能够转化的图。

2.2 抽象定义

给定一个查询Q、一个图数据库G以及一系列转化函数L，求跟Q匹配的最好的k个子图。当中转化函数L包含表2-1中全部的转化。

表2-1 本文支持的转化函数

注：本文的方法能够轻松地增加其他转化函数来满足不同的需求

3 已有方法

Spark查询仅仅需用户输入keyword就可以，而无需输入复杂的图结点关系就能得到查询结果。但其仅仅能提取字符串相似匹配，通过改动能够使其支持其他转换。

NeMa支持图结构和字符串相似度匹配（Jaccard）。

4 本文的方法

4.1 离线操作

4.1.1 度量函数

下述公式中v表示结点，e表示边，φ(·)表示匹配，比如φ(v)表示图数据库G中与查询图v中匹配的结点。若v能够经过第i个转换函数变为φ(v)，则f_i(v,φ(v)) = 1。反之φ(v) = 0。

结点匹配代价：

边匹配代价：

图匹配函数：

且易得图匹配函数P的值越小，与Q匹配的图φ(Q)的质量越高，即查询结果应该为P值最小的k个子图。

4.1.2 參数确定

令W={α₁, α₂, … ; β₁, β₂…}，则

当中T表示训练集。

4.1.3 冷启动

令启动的目的在于怎样生成好的查询训练集，从而能够得到好的匹配函数的參数。冷启动步骤：

(1) 从图数据库中随机选择一些子图作为查询模板Q’；

(2) 将查询模板中的一些结点和边用转换函数进行转化得到查询Q。

(3) 提取和Q精确匹配的子图Q^e；

(4) (Q, Q’)与(Q, Q^e)组成训练集。

4.2 在线查询

一般的图查询均属于NP-hard问题，其能够归约为子图同构问题，从而证明该问题是NP-hard的。

因此本文设计了两个启示式用于求解该问题。

4.2.1 启示式1

将图匹配的代价累加到一个结点上，则每一个结点的匹配得分能够代表包含该节点在内的图匹配代价。

每一个结点计算公式：

当中m_ji^(t)(u_i)表示第t次迭代u_j结点对节点u_i匹配贡献的得分。

该公式的直观理解參考图4-1。当中a、b中左边均表示数据库，右边表示查询图。

图4-1 启示式1的直观意义

4.2.2 启示式2

利用启示式1进行计算时须要计算大量的结点。由结点匹配代价计算公式可得。对于随意的查询结点v经过同样的转换函数匹配代价同样。基于此将经过同一个结点转换的结点浓缩为一个结点计算，则能够有效降低结点得分的计算个数。由浓缩结点组成的图成为概要图。若查询图中两个结点之间存在边，则连接概要图中相应的结点，而与图数据库无关。当中，边的匹配代价为图数据库中全部这类边的匹配代价的上界。

基于这样的发现问题的求解步骤为：

(1) 构造概要图；

(2) 在概要图上利用启示式1计算；

(3) 利用概要图中计算出的结果求原图中与之相应子图的得分。

循环运行直到找到k个结果。

以上为我对论文Schemaless and Structureless Graph Querying-vldb2014的个人理解。当然当中仅仅介绍了论文中的主要内容。具体的解说请查看论文解说的ppt，地址http://download.csdn.net/detail/woniu317/7391539。