图索引之gIndex

gIndex出自<Graph Indexing: A Frequent Structure-based Approach>这篇论文,论文的内容在<Managing and Mining Graph Data>这本书的第5章图索引部分也有提及。这篇论文的作者之一Jiawei Han是机器学习的大佬。

背景

这篇论文中描述的问题,类似于:在一个包含了各种化合物的数据库中,搜索一种结构式,返回所有包含这种结构式的化合物。

如上图所示,Sample Database中包含了3种化合物,Sample Qeury2,3-二甲基丁烷,需要找出包含了Sample Query的化合物。我们把上图中的(a), (b), (c)称之为Graph Item, 简称为GI,避免和其它概念混淆。这个场景和我们一般的图场景有几点不太相同:

  • 图是由多个孤立的GI组成的
  • 每个GI有id
  • 查询结果是GI维度的

在这篇论文之前的图索引的研究,索引项都是Path维度的。但是在上面示例的查询中,Sample Query能够被拆解为的Path有4种:c, c-c, c-c-c, c-c-c-c。这些Path在数据库中的每个GI都是存在的,没有剪枝的作用。所以作者提出了:

Can we use graph structure instead of path as the basic index feature?

使用图结构而不是Path来作为索引项。

方案逻辑

整个论文中比较基础、关键的点是下面3个:Frequent Subgraphs、Discriminative Fragment和Graph Sequentialization。其它的比如查询、gIndex Tree的构建、Verification、针对修改进行索引的更新,这些都比较trivial,比较容易理解,不再赘述。

Frequent Subgraphs

在作者抛出准备使用图结构作为索引项的方案之后,首先的一个问题是,一个图里面Subgraph可是比Path要多很多的,如果所有的Subgraph都来做索引项,索引数据会太大。所以作者提出Frequent Subgraphs,顾名思义是把那些在很多GI中都存在的Subgraph拿出来做索引,这样就可以减少索引数据。

Q:那么这时候可能有同学有疑问,那只有某一个GI中出现的Subgraph,如果要查询它,就需要遍历整个数据库么?

A:这里涉及到两个问题:1. 查询时,Query Graph是可能会被拆分成非常小的单元,比如说一条点、一条边组成的Subgraph,这些小的Subgraph是期望能在索引当中命中的;2. 对于一个点或者一个边这种最小的Subgraph,即使只在一个GI中出现,也需要把它索引起来。

下面先看一下Frequent Subgraphs形式化的定义。首先是support这个概念:

Given a graph database D, |Dg| is the number of graphs in D where g is a subgraph.|Dg| is called (absolute) support, denoted by support(g).

对于每一个子图g,在图中包含它的GI的个数就称为它的support。一个子图是否是frequent,取决于我们定义的minSup。刚才讲了:

对于一个点或者一个边这种最小的Subgraph,即使只在一个GI中出现,也需要把它索引起来

要达成这个目的,需要把minSup设置为1;如果对于所有subgraph都设置同样的minSup,那就失去了frequent的意义了。所以作者就提出了Size-increasing Support。简而言之,对于size越大的子图,minSup越大,也意味着成为frequent的门槛越高。

后面的描述中,Frequent Subgraphs统称为Frequent Fragment

Discriminative Fragment

作者抛出了下一个问题:

Do we need to index every frequent fragment?

一个简单的例子,如果说两个fragment:f1, f2 的support是一样的,而且f1是f2的子图,那我们只需要索引f1。比如在上面的示例数据库中,c, c-c, c-c-c, c-c-c-c这4种图结构的support都是3,所以我们只需要保留c,其它的都是Redundant Fragment。Redundant和Discriminative是两个对立的概念,区分它们的关键在于discriminative ratio

假设我们挑三拣四之后,最后形成了一个feature set: F,在这个F里面包含了又frequent,又discriminative的fragment。这个discriminative ratio简单来说就是,对于某一个需要新加入到的fragment f,把它所有的已经在F里面的子图拿出来,找出包含他们的GI,取交集,记为A;找出包含f的GI,取交集,记为B。那么A/B就是discriminative ratio了。

对于上面这3个fragment:fragment a,它的子图在示例数据库中的3个GI当中都存在,它本身在GI b, GI c中存在,所以discriminative ratio是3/2=1.5;fragment c,它的子图在示例数据库中的GI b, GI c中存在,它本身在GI c中存在,所以discriminative ratio是2/1=2。

Graph Sequentialization

这部分内容源自于Jiawei Han的另一篇论文:。解决的问题是,如何利用已经获取到的feature set: F。需要把选择出来的feature用序列化的方式表示出来,以便于查询的时候使用。

An efficient solution is to translate a graph into a sequence, called canonical label. If two fragments are the same, they must share the same canonical label.

Path的表示是比较简单的,Subgraph的表示就稍显复杂一点,文中使用的是gSpan中提到的DFS coding的方式。

上图中我们需要表示Subgraph (a)。DFS coding简而言之是:

  • 用DFS的方式遍历Subgraph,以DFS中访问到点的顺序给每一个点进行编号。按照固定的规则,对访问到的边进行排序,生成DFS codes。
  • 由于使用DFS方式遍历Subgraph可能产生多种结果,比如上图中的(b), (c), (d),但是我们需要一组唯一的DFS codes来表示Subgraph,怎么办呢?对上述的DFS codes按照字母序进行排序,最终得到minimum DFS codes。在上图中,minimum DFS codes是(d)对应的DFS codes。

总结

这篇论文中的背景比较特殊,和我们一般的图场景不太相同,索引的方式并不能直接使用。但是作者提到的graph mining technique,对于探索基于path/subgraph等graph structure的索引还是有所广益的。