文章简介：

1. 文章标题：An Efficient Probabilistic Approach for Graph Similarity Search
2. 作者单位：
   香港科技大学计算机科学与工程系 李子健/建勋/联想
   美国肯特州立大学计算机科学系 陈磊
3. 文章来源：2018 ICDE
4. 文章链接1
   文章链接2

正文梳理

1.所需要的预备知识

1. 在计算概率时，需要计算${\Lambda }_2$，其中需要用到高斯混合模型的知识。在模型中，许多参数从这个采样的数据对和模型的直观图推断出来。具体如图所示：
   
     文章采用了一种概率建模的方法，将GBDs（图分支距离）的形成过程，建模成随机图编辑过程。使用概率的方法，将GBDs和GED之间建立了联系。在建模之前一些重要的概念：

$B_{GBD}$是什么？

  $B_{GBD}$是一个集合，包含了图中以点位中心的边构成的集合。上图是俩个图$G_1,G_2$的俩个$GBD$，可以发现通过比较，其中的元素有交集。因此，根据定理4，可以知道俩个图分支距离之间的编辑距离：
G B D ( G 1 , G 2 ) = m a x { ∣ B G 1 ∣ , ∣ B G 2 ∣ } − ∣ ∣ B G 1 ∩ B G 2 ∣ ∣ = m a x { ∣ V 1 ∣ , ∣ V 2 ∣ } − ∣ ∣ B G 1 ∩ B G 2 ∣ ∣ GBD(G_{1},G_{2})\\=max\{|B_{G_{1}}|,|B_{G_{2}}|\}-||B_{G_{1}}\cap B_{G_{2}}||\\=max\{|V_{_{1}}|,|V_{_{2}}|\} -||B_{G_{1}}\cap B_{G_{2}}|| GBD(G1​,G2​)=max{∣BG1​​∣,∣BG2​​∣}−∣∣BG1​​∩BG2​​∣∣=max{∣V1​​∣,∣V2​​∣}−∣∣BG1​​∩BG2​​∣∣
文章的俩个重要定理，阐述了如何利用拓展图（又叫做虚图，相对于比较的图而言。需要插入虚拟顶点和虚拟便，使得俩个图如果再转换为另外一个图时 ，仅仅需要重新标记标签的操作）进行编辑操作：

定理：

2. 核心算法

${\Lambda }_1的计算$

${\Lambda }_2的计算$

通过推断得出每个GBD下的概率值：

${\Lambda }_2的计算$

通过贝叶斯模型中吉布斯的非信息依赖，推断数据集中每个数据图在不同的编辑阈值下对应的概率（注意坐标轴的表示）

  上面介绍了文章的核心算法：输入为查询图、查询数据库、相似度阈值（给定的图编辑距离）、概率阈值（和最后计算的概率作比较）；输出为结果集。算法运行的步骤为计算公式中和GBDs相关的各种先验分布，计算查询图的GBDs，之后通过公式进行比较，满足结果加入结果集。下面通过举例说明算法的运算过程：

举例

  文章举例主要问题是计算${\Lambda }_2和{\Lambda }_3$没有详细展示，这也是这个概率计算的核心部分，涉及到了很多概率方面的知识。比如采样、推断等等。

实验

数据集

四个真实数据集：

1. AIDS
2. Fingerprint
3. GREC from the IAM Graph Databases
4. AIDS Antiviral Screen Data(AASD)
   俩个合成数据集：
   syn-1 syn-2

比较方法

LSAP 2009 [11],
Greedy-Sort-GED 2015 [12]
and GraphSeriation 2005 [13]

评估角度，实验角度

1. 高效性
   评估在不同的编辑阈值$\gamma$、不同的顶点个数n下算法的有效性
2. 有效性
   通过精度、召回率、F1-score比较三种算法和自己的优化算法
3. 优化算法的比较

文献综述

精确的GED计算精确的GED计算的最新方法是A * 算法[5]及其变体[6]，其时间成本相对于图形大小[4]呈指数增长。为了解决这个NP硬度问题，大多数图相似性搜索方法都是基于过滤验证框架[4] [18] [19] [15]，该框架首先从图数据库中过滤掉不想要的图，然后仅验证剩余的候选图。常见的过滤方法是使用两个图的子结构之间的距离作为其GED的下限，包括基于树的[18]，基于路径的[33]，基于分支的[15]和基于分区的[34] ]方法。在本文中，我们采用分支结构[15]建立模型。但是，请定义分支之间的距离，因为分支距离的原始定义[15]需要O（n3）时间进行计算，而我们仅需要O（nd）时间。另外，最近的一篇论文35基于他们提出的基于分区的过滤方法，提出了一种多层索引方法来加速过滤过程

参考文献

1.参考文献【4】“Comparing stars: on approximating graph edit distance,”
Z. Zeng, A. K. Tung, J. Wang, J. Feng, and L. Zhou, Proceedings of the VLDBEndowment, vol. 2, no. 1, pp. 25–36,
2009.
主要贡献：在本文中，我们引入了三种新颖的方法来计算多项式时间内两个图形之间的编辑距离的上下限。应用这些方法，引入了两种算法AppFull以及AppSub来对图形数据库执行不同类型的图形搜索。

1. 我们正式证明了图编辑距离计算的问题是NP-Hard。
2. •我们引入了星图表示的概念，并提出了三种新颖的方法来获取多项式时间内两张图之间编辑距离的上下限。
3. •基于这些有效计算 在边界范围内，我们分别开发了两种算法AppFullandAppSub，分别用于执行近似全图搜索和近似子图搜索。
4. •进行了全面的实验研究，以评估我们算法的可扩展性和有效性

2 【参考文献28】 “Iam graph database repository for graph basedpattern recognition and machine learning,”
K. Riesen and H. Bunke,Structural, Syntactic, andStatistical Pattern Recognition, pp. 287–297
2008

摘要：近年来，基于图的表示的使用在模式识别和机器学习中获得了普及。 实际上，通过图形进行对象表示比特征向量具有许多优势。 因此，文献中已经提出了多种用于基于图的机器学习的算法。 然而，与对基于图形的表示形式的兴趣相反，可以观察到缺乏用于基准测试的标准化图形数据集。通常的做法是研究人员使用他们自己的数据集，并且这种行为妨碍了对所提出方法的客观评估。 为了使基于图的机器学习中的不同方法更好地可比，本文旨在介绍图数据集和相应基准的存储库，涵盖不同应用的广泛领域。
文章计算先验分布时需要的数据集，包括数据集MUTAG的介绍
3 外国图相似度论文（类似博士论文）
Similarity Search in Large-ScaleGraph Databases
Zhao, P.
Handbook of Big Data Technologies, 507–529.
2017
摘要：图无处不在，并且在现实世界的网络应用程序中建模和表示复杂结构中起着至关重要的作用。给定图包含大量图形的数据库，对结构相似的图形进行快速灵活的搜索是至关重要的。在本文中，我们调查了最近的图相似度搜索技术，并特别关注根据图形编辑距离（GED）指标进行工作。最先进的方法基于GED的相似性搜索通常采用修剪和验证框架。他们首先利用了一些易于计算的图形下界编辑距离，并使用新颖的图形索引结构来有效评估图数据库中的图与查询图之间的下界。这条路，可以识别和过滤违反GED下界约束的图从图形数据库中进一步调查。然后，仅对通过GED下限评估的图形执行昂贵的GED验证。我们检查现有的GED下界，图形索引结构和相似性搜索详细算法，并从多个方面比较不同的相似度搜索方法，包括索引构建成本，相似度搜索性能和在实际图形数据库中的适用性。最后，我们设想并讨论了相似性搜索和高性能查询的未来研究方向在大型图形数据库中进行处理。
总结：在本章中，我们研究了在图编辑距离（GED）约束下的相似性搜索问题，并研究了用于解决现实世界中大型图数据库中的相似性搜索问题的最新图形索引方法
3 参考文献【29】吉布斯分布
4参考文献【25】高斯混合模型“Estimating the components of a mixture of normal distri-butions,” N. E. Day,
Biometrika, vol. 56, no. 3, pp. 463–474,
1969.
5 文献【11】approximate graph edit distance computationby means of bipartite graph matching,
K. Riesen and H. Bunke,
Image and Vision computing,vol. 27, no. 7, pp. 950–959, 2009.
摘要：精确的图形编辑距离仅适用于较小尺寸的图形。在本文中，我们介绍了一种新颖的算法，该算法使我们能够以相当快的方式近似或次优地计算编辑距离。所提出的算法在优化过程中仅考虑局部边缘结构，而不考虑全局边缘结构。在不同数据集上的实验中，我们证明了我们的方法在两个参考系统上的显着提速。此外，有经验地证明，对于各种模式识别应用，次优距离的精度仍然足够准确。
总结：在本文中，我们提出了一种次优的图形编辑距离计算方法，该方法基于Munkres算法来解决分配问题。分配问题在于找到两组元素之间的分配，从而使成本函数最小化。在当前的论文中，我们展示了如何将图编辑距离问题转化为分配问题。我们提出的解决方案允许节点，边的插入，删除和替换，但是以相对独立的方式考虑这些编辑操作。因此，尽管Munkres算法返回分配问题的最优解，但我们提出的解决方案仅产生了图编辑距离问题的次优或近似解。但是，时间复杂度在两个基础图的节点数中仅是三次。
参考文献【12】
“Approximate graph edit distancein quadratic time,”
K. Riesen, M. Ferrer, and H. Bunke, IEEE/ACM transactions on computational biologyand bioinformatics, 2015
摘要：最近，本文的作者介绍了一种用于图编辑距离问题的通用逼近框架。该特定算法的基本思想是首先计算独立局部图结构的最佳分配（包括节点和边的替换，删除和插入）。相对于两个图的所涉及节点，此最佳分配是完整且一致的，因此可以用于在O（n3）时间内针对原始图编辑距离问题立即得出可允许的（尚未达到最佳）解决方案。但是，对于大型图形或图形集，立方时间复杂度可能仍然过高。因此，我们建议使用二次时间而不是三次时间的次优算法来解决基本分配问题。特别是，在图编辑距离近似的背景下，本文介绍了五种不同的贪婪分配算法。在实验评估中，我们表明这些方法具有进一步加速图形编辑距离计算的巨大潜力，而近似距离仍足以基于图形的模式分类准确。

参考文献【13】
“Graph edit distance from spectralseriation,
A. Robles-Kelly and E. R. Hancock,
IEEE transactions on pattern analysis and machine intelli-gence, vol. 27, no. 3, pp. 365–378,
2005
摘要：本文涉及计算图形编辑距离。可用于计算图形编辑距离的现有方法的批评之一是它们缺乏字符串编辑距离计算的某些形式和严谨性。因此，我们的目标是将图形转换为字符串序列，以便可以使用字符串匹配技术。为此，我们使用图谱序列化方法将邻接矩阵转换为字符串或序列顺序。我们展示了如何使用图邻接矩阵的前导特征向量建立串行排序。我们将图匹配的问题视为图对的序列化序列的最大后验概率（MAP）比对。这种处理导致了这样一种表达，其中编辑成本是后验序列比对概率的负对数。我们通过查找字符串编辑操作的顺序来计算编辑距离，这可以最大程度地减少遍历编辑格的路径的开销。编辑成本取决于邻接矩阵的前导特征向量的分量以及所匹配图的边缘密度。我们演示了在许多图聚类问题上编辑距离的实用性
总结：
本文报道的工作提供了光谱图理论和结构模式识别的综合思想。我们使用基于邻接矩阵前导特征向量的图谱系列化方法将图转换为字符串。我们通过最小化编辑距离来匹配结果字符串表示形式。使用简单的编辑转换概率模型计算所需的编辑成本，该模型旨在保留对应关系的边沿顺序。最小成本编辑序列可以用来在研究的图中定位节点之间的对应关系。我们还演示了编辑距离可用于将图聚类为有意义的类。本文描述的工作可以通过多种方式扩展。首先，尽管我们专注于未加权图，但有趣的是扩展到加权图。其次，还有其他方法可以计算最小成本编辑序列，这些方法可以同时提高方法的效率和准确性。在这种情况下，一个有趣的探索方法是字符串内核
参考文献【15】“Graph similarity search with edit distance constraint in large graph databases,”
W. Zheng, L. Zou, X. Lian, D. Wang, and D. Zhao,
in CIKM
’13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management,
2013.
摘要：由于图数据库的许多实际应用，检索与查询图q大致匹配而不是精确子图匹配的图g（在图数据库D中）变得越来越重要。 在本文中，我们研究图相似度搜索的问题，该问题在最小编辑距离的约束下检索与给定查询图相似的图。 具体来说，我们得出一个基于分支的下界，可以大大减少图相似搜索的搜索空间。 我们还提出了树索引结构，即b树，以促进有效的修剪和有效的查询处理。 大量实验证实，在修剪能力和查询响应时间方面，我们提出的方法要比现有方法好几个数量级。
总结：
考虑到现有方法的局限性，我们提出了一种基于编辑距离的相似度图相似度搜索问题的新方法。 首先提出了基于分支结构的有效下界。 为了方便查询处理，我们精心设计了树索引，即b-tree。 在真实和合成数据集上进行的大量实验证实，我们提出的方法明显优于现有方法。

文章总结

1.解决的问题

  图相似度搜索经常采用计算图编辑距离($GED$)的方法，但是精确计算$GED$被证明为$NP-hard$问题。并且，在许多情形下，相比于查询的相应时间，并不需要计算精确的$GED$。因此，文章为了解决这一问题，引出了图分支距离的定义。并且把分支距离的建立（GBD）和图编辑距离之GED间通过概率建模。如果查询图和数据库图之间不满足概率关系，则是查询结果。

2.使用的方法

  和GED相似，定义了一种新的度量标准GBD。我们将GBD作为图编辑操作的结果，来建立GED和GBD之间的关系，并通过概率方法对该过程进行建模。
  模型如下：输入为查询图、编辑距离阈值、概率阈值、图数据库，输出为结果集。在算法处理过程中，有离线阶段和在线阶段。俩个阶段都计算概率值——采用高斯分布模型和吉布斯采样，在给定的数据集上推断出GED和GBD先验分布的值。经过公式计算，如果不满足最后的不等式关系，则结果集中不包含这个图。整个方法通过定义GBD来估计GED，属于不精确分析GED，这也是一种“基于分支结构方法”【15】的思想。

3.文章的不足

1. 在离线计算先验分布时，需要进行预先从数据集中采样，采耳通过直观绘制先验分布的直方图，推断出$Pr[GBD=\phi ]$的值。采样的结果要取数据库D中的N对图，这种采样方法是不精准的，最后推断出来的先验分布也是不科学的。在采样的时候，从多种维度考虑，使得采样的结果更加精准。