Axton

计算机研究与发展'15 大规模图数据匹配技术综述

· Axton

图作为一种广泛应用的数据结构，非常适合刻画这种具有内在关联性的数据，许多领域的问题都可以通过图的相关理论和技术解决，例如社交网络与Web网络分析、推荐系统、社会安全分析、生物数据分析等。

图模式匹配技术(graph pattern matching)作为实现图数据上高效查询的重要手段，广泛应用于上述各领域的实际问题中。

面对海量关联数据带来的新挑战，各大公司纷纷提出了图数据处理的并行计算模型和系统，包括谷歌公司的大规模图数据处理系统Pregel1、微软研究院的大规模分布式图数据查询(querying large distributed graphs)系统2以及CMU Select实验室研发的GraphLab系统3，这些系统采用分布式计算等技术支持大规模图数据上的高效匹配、查询等算法。

对千万级甚至更大规模的图数据进行高效、准确的匹配查询仍然面临一些问题：

  • 匹配问题复杂
    • 子图同构(subgraph isomorphism)问题属于NP-Complete问题4
    • 措施
      • 设计更高效的搜索算法
      • 采用近似算法
  • 数据规模巨大
    • 采用数据挖掘等技术提取图中的路径、树、子图作为索引特征
  • 数据更新频繁
    • 引入增量处理技术

在所有图匹配问题中，子图同构(subgraph isomorphism)是需要解决的基本问题。

1.图匹配问题

基本的图匹配问题与定义

定义三元组\((V,E,L)\)表示一个图，其中\(V\)表示图中节点的集合，$E$表示图中边的集合，对于任意一条边\(e\in E\)，由节点\((v_i,v_j)\)构成，其中\(v_i,v_j\in V\)。图中的边喝节点可以带有属性信息，\(L\)表示属性 映射函数，将节点或边映射到一个或一组属性上。

一个数据图与模式图的精确匹配问题称为子图同构，需要在数据图中搜索出与模式图在结构和节点与边属性上完全匹配的子图。

精确图匹配问题需要在数据图中找到所有满足上述条件的子图作为模式图的匹配结果。

扩展的图匹配问题

结构匹配和语义匹配

图匹配问题按图数据是否在节点和边上包含语义信息分为语义匹配和结构匹配。

图匹配的许多前期研究基于严格的图结构相似性，即保证所匹配的节点周围具有相同的连通结构，这种匹配问题称为结构匹配，主要应用于化学物质相似结构的检测。

结构匹配的代表性算法包括1976年最早提出的Ullmann算法5以及近年来在该算法基础上改进的VF26，QuickSI7，GraphQL8，Spath9等算法。

在匹配这类图数据时，需要同时保证匹配结果在结构和语义信息上与模式图一致，这种匹配问题称为语义匹配。如典型的GraphGrep10算法。

精确匹配和近似匹配

图匹配问题按匹配结果是否要求与模式图完全一致分为精确匹配和近似匹配。

精确匹配指匹配的结果和模式图的结构及属性完全一致，这种匹配方式主要应用于对匹配结果的准确率要求较高的领域，包括生物数据分析、社会安全分析等，前面介绍的结构匹配算法和语义匹配算法都属于典型的精确匹配技术。

近似匹配是一种可以容忍结果中存在一定噪声和错误的匹配算法，代表性的近似匹配算法包括SUBDUE11，LAW12等，主要通过定义编辑距离、最大公共子图(minium common subgraph)、最小公共超图(minimum common supergraph)等方法衡量两个图的相似程度。

静态图匹配和动态图匹配

图匹配问题按数据图是否更新分为动态图匹配和静态图匹配。

静态图匹配要求所有的数据图不随着时间推移而变化，GIndex13是最有代表性的静态图匹配算法，后续还有FG-Index14，Tree+delta15等算法。

动态图匹配能够在图数据更新时满足实时匹配的性能需求。主要采用增量处理技术，仅对更新的数据图进行分析，代表性工作包括文献161718。

最优算法和近似算法

图匹配算法按是否能获得准确结果分为最优算法和近似算法

最优算法保证匹配结果完全精确，例如精确匹配问题的最优算法可以保证计算结果与模式图完全同构，近似匹配问题的最优算法获得与模式图最近似的一系列匹配结果。

近似算法不同于近似匹配，近似算法通常基于概率统计等数学模型，非常适合动态图匹配等对算法实时性要求较高且只需满足一定准确率的匹配问题。

2.精确图匹配技术

  • Exact Graph Pattern Matching
    • Non-index-based Matching
      • Ullmann(1976)
      • VF2(2001)
      • GraphQL(2008)
      • GADDI(2009)
      • Spath(2010)
    • Index-based Matching
      • Non-mining-based Matching
        • GraphGrep(2002)
        • CTree(2006)
        • GCoding(2008)
      • Mining-based Matching
        • GIndex(2004)
        • FG-Index(2007)
        • Tree-Delta(2007)

无索引的匹配技术

精确图匹配是一种NP完全问题，算法设计时利用图中的结构和语义信息可以有效提高图匹配的性能。

无索引的匹配技术主要采用搜索策略，适合小规模数据图的精确匹配。

Ullmann算法是已知最早的无索引匹配方法，采用深度优先搜索策略，在数据图\(G\)中枚举出与模式图\(P\)中节点一一匹配的子图。

Ullmann算法和VF2算法(适合语义匹配)仅利用了待匹配节点与邻接节点的结构和语义约束缩小匹配范围，适合小规模的图匹配问题

GraphQL，GADDI，Spath等算法从不同角度加强了对备选节点的约束条件，从而有效减少了搜索过程中的回溯次数。

基于索引的匹配技术

基于索引的匹配技术通过预先选择数据图中有效的特征建立倒排索引，使得模式匹配时可以根据索引快速缩小搜索空间，再对小规模的备选图进行精确匹配，达到加速匹配的目的。适合大规模图匹配问题。

基于索引的图匹配技术的基本思想主要包括以下两个方面

  • 索引建立。匹配前首先提取数据图中的特征，根据特征建立数据图的倒排索引
  • 模式匹配。在建立索引后，已知待匹配的模式图P，匹配过程包括两部分
    • 筛选备选图
    • 精确匹配

非数据挖掘的索引技术

非数据挖掘的索引算法在建立索引的过程中利用路径、节点信息或节点周围结构作为索引特征，不需要对数据图进行数据挖掘等复杂操作。

非数据挖掘的索引技术的主要优势在于采用简单的路径、树以及其他简单的结构对图数据中每个节点进行编码描述，从而快速建立索引。当图数据动态变化时能够高效地对索引进行调整，非常适合动态图数据对匹配的实时性需求。

基于数据挖掘的索引技术

针对非数据挖掘的索引技术忽略了图数据结构信息的问题，典型的改进方法是采用图的子图结构代替以节点为中心的路径、树以及其他简单结构作为索引特征。然而子图结构的数量会远远超过简单结构的数量，导致索引规模呈指数增长，无法应用于实际大规模的图匹配问题。因此，需要在所有子图结构中挖掘具有较强辨别力的子图作为特征，从而缩小索引规模。

通过数据挖掘技术可以选择具有较强辨别力的索引特征，在很大程度上降低了索引规模，但随着待处理数据规模的不断增长，所生成的大规模索引将无法直接存储在内存中，需要使用外存储器来存储。

3.图数据模式匹配算法和性能评价

具有代表性的数据集

评测数据集包括两类：数据图数据集和模式图数据集

真实数据图数据集

  • AIDS Antiviral 数据集
  • NASA 数据集
  • Yeast 数据集
  • Human 数据集

合成数据图数据集

GraphGen19是其中一种应用广泛的生成工具可用于生成一系列有标签、连通的无向图。

文献20提出了一种图数据生成方法，该方法首先随机生成S个种子图，种子图的大小服从均值为T的泊松分布。

精确图匹配算法的性能比较

无索引的图匹配算法性能比较

评价无索引的匹配技术一般包括3个标准：数据库构建时间、存储空间和平均匹配时间。

  • 数据库构建时间包括读取数据的I/O时间、提取特征等总时间；
  • 存储空间为在内存中建立完成的数据库大小；
  • 平均匹配时间为所有模式图匹配时间的平均值，当数据集中包含多个数据图时，每个模式图的匹配时间为匹配完数据集中所有数据图的累计时间。

基于索引的图匹配算法性能比较

对于基于索引的匹配算法，评价建立索引过程的指标一般包括索引规模和建立时间，评价匹配过程的指标通常包括备选图规模和总匹配时间。

备选图规模表示通过索引过滤后需要进行精确匹配的备选图数目，匹配时间Ｔ可表示为\(T=T_{filter}+|C_q|\times T_{iso}\)，其中，\(T_{filter}\)表示通过索引选择备选图阶段所需时间，\(|C_q|\)表示筛选得到的备选图数目，\(T_{iso}\)是对每个备选图采用子图同构算法进行精确匹配的平均时间。

通常精确匹配采用的子图同构算法是NP问题，不同算法的匹配时间\(T_{iso}\)差别较小。\(|C_q|\)是影响整体匹配性能的关键因素，有效且高效的索引可以快速筛选备选图，尽量降低备选图规模。但是如果所建立的索引规模过大，无法完全载入内存，由于对硬盘的访问速度比内存的访问速度慢4~6个数量级，\(T_{filter}\)也将成为整个算法的性能瓶颈。

4.图匹配技术的应用现状和未来发展

  1. 社会关系查询
    • 社会关系查询是图数据匹配技术最主要和最广泛的应用之一。
    • 社会关系可以表示为图的形式（例如学术关系图、亲属关系图、社交网络图等），其中图的节点是人，节点上带有人物的姓名、年龄、职业等属性；节点间的边表示人与人之间的各种社会关系，边上的属性值表示具体的相互关系。
  2. 社会安全分析
    • 鉴于犯罪行为和暴恐事件给国家和社会带来严重危害，分析犯罪规律并及早预防显得尤为重要。
    • 近年来，基于图数据匹配技术的犯罪规律和异常行为分析成为情报信息挖掘的重要研究方法．通过对网络行为（例如即时通信、邮件、社交网络等）和现实活动信息（例如乘坐交通工具、住宿、购物等）的获取及融合，建立以人物为节点、以活动关系为边的行为关系图．异常行为可定义为模式图的形式，通过图模式匹配技术在大规模关系图中进行搜索和定位，发现和预测特定的犯罪团伙和行为。
  3. 推荐系统
    • 图数据匹配技术也是视频推荐、音乐推荐 、专家推荐等应用领域的重要方法之一。
  4. 网络攻击检测
    • 随着互联网的迅速发展，网络安全问题也备受关注，典型的网络安全系统通常采用模式串匹配技术进行入侵检测和反病毒、反垃圾邮件检测，基于图模式匹配的检测技术成为新的发展方向。
  5. 生物数据分析
    • 大规模的生物数据可以表示为图的形式，图匹配技术对复杂生物数据的分析和研究发挥着重要作用。

图匹配技术面临着新的挑战和机遇：

  1. 大规模图数据的存储空间将越来越大，严重影响传统的基于内存的图数据匹配技术的性能。
    • 解决该问题可以从两个角度考虑：
      • 从数据的角度来看，一方面可以采用分布式系统，另一方面，对原始图数据进行压缩表示。
      • 从匹配算法的角度来看，如何设计更加精简的多级索引匹配算法也将是未来的研究热点之一。
  2. 图数据更新更加频繁，传统的静态图匹配算法难以直接、高效地应用于动态图数据，需要研究高效的动态图匹配算法。
  3. 真实数据往往存在数据丢失和不确定性等问题，影响图数据匹配的准确度。

  1. Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik et al. Pregel: a system for large-scale graph processing. SIGMOD Conference 2010: 135-146 ↩︎

  2. Mohamed Sarwat, Sameh Elnikety, Yuxiong He et al. Horton: Online Query Execution Engine for Large Distributed Graphs. ICDE 2012: 1289-1292 ↩︎

  3. Yucheng Low, Joseph Gonzalez, Aapo Kyrola et al. GraphLab: A New Framework For Parallel Machine Learning. UAI 2010: 340-349 ↩︎

  4. M. R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 ↩︎

  5. Julian R. Ullmann. An Algorithm for Subgraph Isomorphism. J. ACM 23(1): 31-42 (1976) ↩︎

  6. Luigi P. Cordella, Pasquale Foggia, Carlo Sansone et al. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10): 1367-1372 (2004) ↩︎

  7. Dennis E. Shasha, Jason Tsong-Li Wang et al. Algorithmics and Applications of Tree and Graph Searching. PODS 2002: 39-52 ↩︎

  8. Huahai He, Ambuj K. Singh Graphs-at-a-time: query language and access methods for graph databases. SIGMOD Conference 2008: 405-418 ↩︎

  9. Peixiang Zhao, Jiawei Han. On Graph Query Optimization in Large Networks. Proc. VLDB Endow. 3(1): 340-351 (2010) ↩︎

  10. Dennis E. Shasha, Jason Tsong-Li Wang, Rosalba Giugno. Algorithmics and Applications of Tree and Graph Searching. PODS 2002: 39-52 ↩︎

  11. Diane J. Cook, Lawrence B. Holder. Substructure Discovery Using Minimum Description Length and Background Knowledge. J. Artif. Intell. Res. 1: 231-255 (1994) ↩︎

  12. Michael Wolverton, Pauline Berry, Ian W. Harrison et al. LAW: A Workbench for Approximate Pattern Matching in Relational Data. IAAI 2003: 143-150 ↩︎

  13. Xifeng Yan, Philip S. Yu, Jiawei Han. Graph Indexing: A Frequent Structure-based Approach. SIGMOD Conference 2004: 335-346 ↩︎

  14. James Cheng, Yiping Ke, Wilfred Ng. Fg-index: towards verification-free query processing on graph databases. SIGMOD Conference 2007: 857-872 ↩︎

  15. Peixiang Zhao, Jeffrey Xu Yu, Philip S. Yu. Graph Indexing: Tree + Delta >= Graph. VLDB 2007: 938-949 ↩︎

  16. Sutanay Choudhury, Lawrence B. Holder, George Chin Jr. et al. StreamWorks: a system for dynamic graph search. SIGMOD Conference 2013: 1101-1104 ↩︎

  17. Lei Chen, Changliang Wang. Continuous Subgraph Pattern Search over Certain and Uncertain Graph Streams. IEEE Trans. Knowl. Data Eng. 22(8): 1093-1109 (2010) ↩︎

  18. Sutanay Choudhury, Lawrence B. Holder, John Feo et al. Fast search for dynamic multi-relational graphs. DyNetMM@SIGMOD 2013: 1-8 ↩︎

  19. GraphGen is a synthetic graph data generator. https://cse.hkust.edu.hk/graphgen/ ↩︎

  20. Michihiro Kuramochi, George Karypis. Frequent Subgraph Discovery. ICDM 2001: 313-320 ↩︎