跳转至

17 挖掘图数据

“在信息传递中，结构比内容更重要。” - Abbie Hoffman

17.1 介绍

图形在生物信息学，化学，半结构化和生物学数据等广泛的应用领域中无处不在。 图的许多重要属性可能与它们在这些域中的结构有关。 因此，图挖掘算法可以用于分析图的各种领域特定属性。 在实际应用中遇到的大多数图都是以下两种类型之一：

1.在诸如化学和生物数据的应用中，可以使用许多小图的数据库。 每个节点都与一个标签相关联，该标签可能对节点可能是唯一的，也可能不是唯一的，具体取决于特定于应用的场景。

2.在Web和社交网络等应用程序中，可以使用单个大图。 例如，Web可以被看作是一个非常大的图，其中节点对应于网页（由它们的URL标记），并且边对应于节点之间的超链接。

这两种数据的应用程序的性质非常不同。 Web和社交网络应用程序将在18章和19章中解决。 因此，本章将着重于第一种情景，其中有许多小图可用。 图形数据库可以正式定义如下。

定义 17.1.1（图数据库） 图数据库D是n个不同的无向图的集合，G_{1}=(N_{1},A_{1})\cdots G_{n}=(N_{n},A_{n})，像这样第i个图中的节点集合由N_{i}表示，并且第i个图中的边集合由A_{i}表示。每个节点p\in N_{i}与由l(p)表示的标签相关联。

图17.1 一种化合物（对乙酰氨基酚）及其相关的图示

与节点相关的标签可以在单个图中重复。 例如，当每个图G_{i}对应于化合物时，节点的标签是表示化学元素的符号。 由于同一元素的多个原子的存在，这样的图形将包含标签重复。 单个图形中标签的重复导致图匹配和距离计算中的许多挑战。 图形数据在许多实际应用中遇到。 图数据挖掘的关键应用的一些例子如下：

  • 化学和生物学数据可以表示为其中每个节点对应于原子并且一对原子之间的键由边表示的图形。 边缘可以加权以反映粘合强度。 图17.1举例说明了化合物及其相应的图。 图17.1a显示了化学对乙酰氨基酚，一种众所周知的镇痛药的图解。 图17.1b中给出了相应的图形表示以及节点标签和边权重。 在许多图挖掘应用中，单位边权重被假定简化。
  • XML数据可以表示为属性图。 结构化记录的不同属性之间的关系可以表示为边。
  • 几乎任何数据都可以通过实体 - 关系图来表达。这提供了以实体 - 关系图的形式表示时挖掘常规数据库记录的不同方式。

图形数据非常强大，因为它们可以模拟对象之间的任意关系。 图表示中的灵活性以更大的计算复杂性为代价：

  1. 图表缺少多维或甚至上下文（例如时间序列）数据的“平滑”结构。后者用传统模型进行分析要容易得多。
  2. 节点之间的标签重复导致图之间计算相似性的同构问题。这个问题是NP难的。这导致相似度计算和图匹配中的计算挑战。

第二个问题非常重要，因为匹配和距离计算都是图挖掘应用程序中的基本子问题。例如，在一个频繁的子图挖掘应用中，一个重要的子问题就是子图匹配。

本章安排如下。第17.2节解决了图中匹配和距离计算的问题。用于距离计算的图形转换方法在 17.3节中讨论。本节的一个重要部分是预处理方法，例如拓扑描述符和核方法，这些方法通常用于距离计算。第17.4节解决了图中模式挖掘的问题。关于图的聚类问题在17.5中得到了解决。图表分类在17.6节中解决。17.7节提供了一个总结。

17.2 图的匹配和距离计算

匹配和距离计算的问题在图形领域密切相关。 据说当两个图的节点之间建立一对一的对应关系时，两个图匹配，使得它们的标签匹配，并且相应节点之间的边存在匹配。 这样的一对图之间的距离为零。 因此，一对图之间的距离计算问题至少和图匹配一样困难。 匹配图也被认为是同构的。 应该指出的是，术语“匹配”在图形挖掘的两个不同的上下文中使用，有时可能会造成混淆。 例如，使用边将单个图中的节点配对也称为匹配。 在本章中，除非另有说明，否则我们的重点不在于节点匹配问题，而在于成对图匹配问题。 这个问题也被称为图同构。

**定义17.2.1（图匹配和重构）**两个图G_{1}=(N_{1},A_{1})和G_{2}=(N_{2},A_{2})是同构的当且仅当在N1和N2的节点之间可以找到满足以下属性的一一对应关系：

  1. 对于每一对对应的节点i∈N_1和j\in N_2，它们的标签是相同的。

​ l(i)=l(j)

  1. 令[i_1，i_2]为G_1中的节点对，[j_1，j_2]为G_2中的对应节点对。 那么当且仅当边（j_1，j_2）存在于G2中时，边（i_1，i_2）存在于G1中。

图匹配中的计算挑战是由于节点标签中的重复引起的。 例如，考虑两个甲烷分子，如图17.2所示。 虽然两个分子中的独特碳原子可以完全匹配，但是氢原子可以在其中匹配4！ = 24种不同的方式。 图17.2a和17.2b中示出了两种可能的匹配。 一般来说，每个图中标签重复的级别越高，可能匹配的数量就越大。 一对图之间可能匹配的数量随着匹配图的大小呈指数增长。 对于每个包含n个节点的一对图，可能匹配的数目可以与n！一样大。 这使得在计算上匹配一对图的问题非常昂贵。‘

**引理17.2.1 ** 确定一对图之间是否存在匹配的问题是NP难的。

图17.2：在一对表示甲烷的图间两种匹配方式

书目注释包含了NP难证明的过程。 当图表非常大时，精确匹配通常不存在。 但是，可能存在近似匹配。 近似程度用距离函数进行量化。 因此，图之间的距离函数计算是一个比图匹配更为普遍的问题，并且至少是困难的。 这个问题将在下一节详细讨论。

另一个相关的问题是子图匹配。 与精确图匹配的问题不同，在这种情况下，查询图需要与数据图明确区分。

**定义17.2.2(节点导出子图)**图G =（N，A）的节点导出的子图是满足以下性质的图G_ s =（N_s，A_s）：

  1. N_s\subseteqq N
  2. A_s=A\cap(N_s\times N_s)

换句话说，在子图G_s中，包含子集N_s中的节点之间的原始图G中的所有边。

子图同构可以用节点导出的子图来定义。 查询图G_q是数据图G的子图同构，当它是G的节点导出子图的精确同构时。

**定义17.2.3（子图匹配和同构）**当且仅当下列条件满足时，查询图G_q=(N_q,A_q)是数据图G =（N，A）的子图同构：

  1. N_q中的每个节点应该与N中具有相同标签的唯一节点相匹配，但N中的每个节点可能不一定匹配。 对于每个节点i∈N_q，必须存在唯一的匹配节点j∈N，使得它们的标签是相同的。

​ l(i)=l(j)

  1. 令[i1，i2]成为G_q中的一个节点对，根据上面讨论的匹配，令[j1，j2]成为G中相应的节点对。 那么，当且仅当边（j1，j2）存在于G中时，边（i1，i2）存在于G_q中。
    图17.3：一对图之间的两个可能的子图同构

本节中的子图同构的定义假定数据图的节点导出子图的所有边都存在于查询图中。 在一些应用中，比如频繁的子图挖掘，使用了一个更一般的定义，其中节点导出子图的边的任何子集也被认为是子图同构。 在本节中对更一般的情况可以通过对算法进行微小更改来处理。 请注意，上述定义允许子图G_q（或G）断开。 但是，对于实际应用，通常只关心连通的子图同构。 图17.3说明了一对节点之间两种可能的子图匹配的例子。 该图还表明，一个图形是另一个图形的子图有两种不同的方式。 精确匹配的问题是子图匹配的特例。 因此，子图匹配问题也是NP难的。

引理17.2.2 子图匹配的问题是NP难的。

子图匹配通常用作应用程序中的子例程，如频繁模式挖掘。 虽然子图匹配问题是精确匹配的推广，但问题可以进一步推广到在一对图之间寻找最大公共子图（MCG）的问题。 这是因为两个图之间的MCG最多等于两个图中较小的一个，当它是较大图的子图时。 一对图之间的MCG或最大公共同构定义如下。

**定义17.2.4（最大公共子图）**一对图G_1 =（N_1，A_1）和G_2 =（N_2，A_2）之间的MCG是一个图G_0 =（N_0，A_0），它是G_1和 G_2的子图同构，并且节点集合N_0的大小尽可能大。

因为MCG问题是图同构问题的泛化，所以它也是NP难题。 在本节中，将介绍用于发现子图同构和最大公共子图的算法。 随后，将讨论这些算法与图之间距离计算的关系。 可以设计子图同构算法来确定查询图和数据图之间的所有子图同构，或者可以设计快速算法以确定是否存在至少一个同构。

17.2.1乌尔曼的子图同构算法

Ullman算法设计用于确定查询图和数据图之间的所有可能的子图同构。它也可以用于通过使用提前终止标准来确定查询图是否是数据图的子图同构的决策问题。有趣的是，后来的大多数图匹配算法都是Ullman算法的改进。因此，本节将首先提供一个非常简单的没有任何改动的算法。随后，这个基本算法的不同变化和改进将在一个单独的小节中讨论。尽管子图同构的定义允许查询和数据图断开，但在查询和数据图连通的情况下集中查询和数据图常常是实用和计算可行的。通常，对算法的小改动可以适应这两种情况（请参见练习14）。

假定查询图由G_q =（N_q，A_q）表示，数据图由G =（N，A）表示。 Ullman算法的第一步是匹配两个图中所有可能的节点对，以便该对中的每个节点具有与另一个节点相同的标签。对于每个这样的匹配对，该算法使用递归搜索过程一次将其扩展为一个节点。每次递归调用将G_q和G中的匹配子图展开一个节点。因此，递归调用的参数之一是节点对的当前匹配集合M。 M中的每个元素都是G_q和G之间的一对匹配节点。因此，当两个图之间的m个节点的子图已经匹配时，集合M包含m个匹配的节点对，如下所示：

​ M={(i^q_1,i_1),(i^q_2,i_2),...(i^q_m,i_m)}

这里，假定节点i^q_r属于查询图G_q，并且节点i_r属于数据图G。匹配设置参数M的值被初始化为在顶层递归调用处的空集。 M中匹配节点的数量恰好等于递归调用的深度。当子图不能进一步匹配或G_q完全匹配时，递归回溯。在后一种情况下，报告匹配集合M，并且递归回溯到下一个更高级别以发现其他匹配。在没必要确定一对图之间的所有可能匹配的情况下，此时也可以终止算法。然而，这个特别的展示假定所有可能的匹配都需要确定。

图17.4说明了Ullman算法的简化版本。该算法被构造为递归方法，其探索两个图之间所有可能匹配的空间。该算法的输入是查询图G_q和数据图G。该递归调用的附加参数M是包含当前匹配节点对的集合。虽然分析师在顶层调用时M组为空，但在递归的较低层次上情况并非如此。 M的基数恰好等于递归的深度。这是因为在每次递归调用中将一个匹配的节点对添加到M中。严格地说，递归调用在必须遵守对应于M的匹配的约束下返回所有的子图同构。

递归过程的第一步是检查M的大小是否等于查询图G_q中的节点数。如果确实如此，则该算法将M报告为成功的子图匹配，并且将递归回溯到下一个更高级别以探索其他匹配。否则，该算法尝试确定进一步匹配的节点对以添加到M.这是候选生成步骤。在这个步骤中，G_q和G之间的所有可能的标签匹配节点对（它们不在M中）用于构造候选匹配集C。

图17.4：Ullman算法的基本模板

由于候选匹配扩展的数量可能很大，因此通常希望通过使用数据图和查询图的特定属性来试探性地修剪它们。这种启发式的一些例子将在稍后介绍。在生成修剪后的集合C之后，逐个选择节点对（i_q，i）∈C，并且检查它们是否可以被添加到M以创建两个图形之间的有效（部分）匹配。对于M∪{（i_q，i）}是一个有效的部分匹配，如果i_q∈N_q入射到G_q中任何已经匹配的节点j_q上，那么i也必须入射到G中j_q的匹配对应j上，反之亦然。如果存在有效的部分匹配，则使用部分匹配M∪{（i_q，i）}递归地调用该过程。在用相应的递归调用遍历所有这些候选扩展之后，该算法回溯到递归的下一个更高级别。

不难看出该过程在其输入大小方面具有指数复杂性，并且对查询图大小特别敏感。这种高度复杂性是因为递归的深度可以是查询图形大小的顺序，并且每个级别的递归分支的数量等于匹配节点对的数量。显然，除非通过更有效的候选生成和修剪来谨慎控制候选扩展的数量，否则这种方法将非常缓慢。

17.2.1.1算法的变化和改进

虽然基本的匹配算法最初是由Ullman提出的，但该模板已被不同的匹配算法广泛使用。 不同的算法在候选匹配对的大小如何受到严格修剪的限制方面各不相同。 仔细选择候选集的使用对算法的效率有显着的影响。 大多数修剪方法依赖于许多自然约束，这些约束在子图同构关系中总是由两个图满足的。 一些常见的修剪规则如下：

  1. Ullman算法：该算法使用简单的修剪规则。如果i的度小于i_q，则所有节点对（i_q，i）在修剪步骤中从C中删除。这是因为查询子图中每个匹配节点的度数不得大于数据图中匹配对象的度数。

  2. VF2算法：在VF2算法中，如果i_q没有连接到G_q中已经匹配的节点（即包含在M中的G_q的节点），那么这些候选（i_q，i）被修剪。随后，修剪步骤还移除其中未连接到数据图G中的匹配节点的那些节点对（i_q，i）。这些修剪规则假定查询和数据图连接。该算法还比较了连接到M中节点但未包含在M中的i和i_q中每个节点的邻居节点的数量。数据图中此类节点的数量必须不小于节点中这些节点的数量查询图。最后，比较i和i_q中每个与M中没有直接连接到节点的邻居节点的数量。数据图中这些节点的数量必须不小于查询图中此类节点的数量。

  3. 排序优化：修剪步骤的有效性对节点被添加到匹配集合M的顺序非常敏感。一般而言，查询图形中具有较少标签的节点首先选择应该在探索不同候选对C。不同图之间可以用较少的方式匹配较稀疏的标签。对较少标签的早期探索导致在递归的早期阶段探索更相关的部分匹配M.这也有助于修剪的有效性。VF2和QuickSI的增强版本结合了节点排序和上述节点修剪步骤。

有关这些算法的详细信息，请参阅书目注释。本节中子图同构的定义假定数据图的节点导出子图的所有边都出现在查询图中。在一些应用中，比如频繁的子图挖掘，使用了一个更一般的定义，其中节点导出子图的边的任何子集也被认为是子图同构。更一般的情况可以通过对基本算法的微小改变来解决，在该算法中，生成候选项和验证它们的标准都被适当放宽。

17.2.2最大公共子图（MCG）问题

MCG问题是子图同构问题的泛化。两个图之间的MCG最多等于两者中较小的一个，当一个是另一个的子图时。子图同构算法的基本原理可以很容易地扩展到MCG同构问题。以下将讨论Ullman算法扩展到MCG问题。这些方法之间的主要差异是根据修剪标准以及最大公共子图在子图的搜索空间被探索算法过程中不断追踪的实际情况。

MCG算法的递归探索过程与子图同构算法的递归探索过程相同。该算法如图17.5所示。两个输入图分别用G1和G2表示。如在子图匹配的情况下，递归探索中的当前匹配由集合M表示。对于每个匹配节点对（i_1，i_2）∈M，假定i_1是从G1绘制的，并且i_2是从G2绘制。算法的另一个输入参数是当前最佳（最大）匹配的节点对M_{best}集合。在分析师对递归算法进行的初始调用中，M和Mbest都被初始化为null。严格地说，每个递归调用都在约束条件下确定最佳匹配，即M中的对必须匹配。这是在顶层递归调用时将此参数设置为null的原因。但是，在较低级别的调用中，M的值不为空。

​图17.5：最大公共子图（MCG）算法

与子图同构算法的情况一样，递归地探索候选匹配节点对。在MCG算法中使用候选扩展和修剪的相同步骤，就像子图同构问题的情况一样。然而，基于子图假设的子图同构算法中使用的一些修剪步骤不能再使用。例如，在MCG算法中，匹配的节点对（i_1，i_2）不再需要满足约束条件，即一个图中节点的度数大于或小于其他节点中匹配节点的度数。由于最大公共子图问题中修剪更有限，它将探索更大的搜索空间。这在直觉上是合理的，因为最大公共子图问题比子图同构更普遍。然而，仍然可以使用一些优化，例如仅扩展到连接节点以及排序优化（例如较早处理罕见标签）。

迄今为止发现的最大的共同子图在M_{best}中被追踪。在过程结束时，算法返回迄今为止找到的最大匹配子图。修改此算法以确定所有可能的MCG也相对容易。主要差异在于所有当前的MCG都可以动态跟踪，而不是跟踪单个MCG。

17.2.3 距离计算的图匹配方法

图匹配方法与图之间的距离计算密切相关。 这是因为共享大型子图的图对可能更相似。 计算图形之间距离的第二种方法是使用编辑距离。 图中的编辑距离类似于字符串中编辑距离的概念。 这两个方法将在本节中讨论。

17.2.3.1基于MCG的距离

当两个图共用一个大的子图时，它表示相似性。 有几种将MCG大小转换为距离值的方法。 其中一些距离定义也被证明可以作为衡量标准，因为它们是非负的，对称的，并且满足三角不等式。 令图G_1和G_2的MCG由|MCS（G_1，G_2）|的大小表示为MCS（G_1，G_2）。 将图G_1和G_2的大小表示为| G_1 | 和| G_2 |。 各种距离度量被定义为这些量的函数。

  1. 非归一化非匹配度量：两个图之间的非归一化非匹配距离度量U（G1，G2）定义如下：U（G1，G2）= | G1 | + | G2 | -2 \cdot | MCS（G1 ，G2）| \tag{17.1}

这等于两个图之间的不匹配节点的数量，因为它减去了匹配节点的数量| MCS（G1，G2）|来自每个| G1 |和| G2 |，然后添加它们。这个度量是未规范化的，因为距离的值取决于底层图的原始大小。这是不可取的，因为比较不同大小的图形对之间的距离更加困难。如果集合中的不同图形大小大致相似，则此度量更有效。

  1. 联合归一化距离：距离度量值位于（0,1）的范围内，并且也显示为度量标准。联合归一化测度UDist（G1，G2）定义如下：UDist（G1，G2）= 1- \frac {| MCS（G1，G2）| }{| G1 | + | G2 | - | MCS（G1，G2）|}\tag{17.2}

这个度量被称为联合归一化距离，因为分母包含两个图的并集中的节点数。理解这种度量的一种不同方式是，它将两个图之间的非匹配节点U（G1，G2）的数量（非规范化度量）与两个图的并集中的节点数进行归一化。

​ UDist（G1，G2）=\frac{G1和G2之间不匹配的节点}{G1和G2的联合大小}

此度量的一个优点是，它直观地易于解释。两个完美匹配的图将彼此的距离为0，两个完全不匹配的图的距离为1。

  1. 最大归一化距离：此距离度量也位于范围（0,1）内。两个图G1和G2之间的最大规范化距离MDist（G1，G2）定义如下：MDist（G1，G2）= 1- \frac{| MCS（G1，G2）| }{\max \{| G1 |，| G2 | \} }\tag{17.3}

联合归一化距离的主要不同点是分母用两个图的最大尺寸归一化。这个距离度量是一个度量，因为它满足三角不等式。该措施也相对容易解释。两个完美匹配的图将相互之间的距离为0，两个完全不匹配的图将具有1的距离。这些距离度量可以有效地仅针对小图进行计算。对于较大的图，由于需要确定两个图之间的最大公共子图，所以评估这些度量在计算上变得太昂贵。

17.2.3.2 图编辑距离

图17.6：图G1和G2之间两种可能的编辑路径示例

图形编辑距离类似于字符串编辑距离，在第3章讨论。主要不同之处在于，编辑操作是针对图域特定的。编辑距离可以应用于节点，边或标签。在图的内容中，可容许的操作包括：（a）插入节点，（b）删除节点，（c）节点的标签替换，（d）边的插入，以及（e）删除边。请注意，删除节点包括自动删除其所有入射边。每个编辑操作都有与其相关的编辑成本，这是以特定于应用程序的方式定义的。事实上，学习编辑成本的问题本身就是一个具有挑战性的问题。例如，学习编辑成本的一种方法是使用第三章中讨论的监督距离函数学习方法。书目注释包含了一些这些算法的说明。

图17.6给出了图G1和G2之间两条可能编辑路径的例子。请注意，这两条路径将具有不同的成本，具体取决于组成操作的成本。例如，如果标签替换的成本与边插入和删除的成本相比非常高，则使用图17.6中的第二条（较低）路径可能更有效。对于大而复杂的图对，可能存在指数数量的可能编辑路径。两个图形之间的编辑距离Edit（G1，G2）等于通过一系列编辑操作将图形G1转换为G2的最小成本。

**定义17.2.5（图形编辑距离）**图形编辑距离Edit（G1，G2）是将图形G1应用于编辑操作以将其转换为图形G2的最小代价。

根据不同操作的成本，编辑距离不一定是对称的。换句话说，编辑（G1，G2）可以与编辑（G2，G1）不同。有趣的是，编辑距离与确定MCG的问题密切相关。事实上，对于一些特殊的成本选择，编辑距离可以表示为等同于基于最大公共子图的距离度量。这意味着图的编辑距离计算也是NP难的。编辑距离可以看作是一个容错图同构的成本，其中“错误”是根据编辑操作的成本进行量化的。正如在第三章中，字符串和序列的编辑距离计算可以使用动态规划多项式求解。图的情况更加困难，因为它属于NP难问题的类别。

编辑距离计算和MCG问题之间的密切关系反映在相应算法的相似结构中。就最大公共子图问题而言，可以使用递归树搜索过程来计算编辑距离。下面将介绍计算编辑距离的基本步骤。书目注释包含了对这一过程的增强和改进。

编辑距离的一个有趣特性是它可以通过仅探索那些编辑序列结束时执行任何和所有节点插入操作（连同它们的入射边缘插入）的编辑序列来计算。因此，编辑距离算法维持一系列编辑E，这些编辑E是要应用于图G1的操作，以将其转换为图G2中的子图同构G1'。通过简单地将G2的不匹配节点添加到G1'和相应的入射边作为最后一步，可以创建G2。因此，序列E的最初部分没有最后一步，根本不包含任何节点插入。换句话说，序列E的最初部分可以包含节点删除，节点标签替换，边添加和边删除。这种编辑序列的例子如下：

E = Delete(i1), Insert(i2,i5), Label-Substitute(i4,A⇒ C), Delete(i2,i6)

该编辑序列显示删除节点，然后添加新边（i2，i5）。节点i4的标签被从A替换为C。然后，边（i2，i6）被删除。编辑序列E从G1到G2的子图同构G1'的总成本等于E中所有操作的编辑成本的总和，以及需要在G1'上执行的节点插入和事件边缘插入的成本来创建最终图G2。

在所有其他边缘操作，节点删除和将G1变换为G2的子图同构的标签替换之后，执行插入节点及其入射边，有可能实现最优的编辑路径序列。这个属性的证明来自以下事实：只要插入的节点不与任何其他编辑操作（节点或边删除或标签替换）相关联，就可以对任何最佳编辑序列进行重新排序以将节点（及其相关边）的插入推到末尾。也很容易证明，删除新添加的节点或边的任何编辑路径都不是最理想的。此外，插入节点不需要在最佳路径中被标签替换，因为在节点插入时可以设置正确的标签。

在图17.7中给出了全部的递归处理过程。算法的输入分别是源图G1和目标图G2。另外，当前编辑序列E被检查以进一步扩展，并且到目前为止发现的最好（最低成本）编辑序列E_{best}是该算法的输入参数之一。这些输入参数对于在递归调用之间传递数据很有用。 E的值在顶级调用中被初始化为null。在算法开始时，E的值为null，但在每次递归调用中都会附加新的编辑。用这个扩展序列作为输入参数执行进一步的递归调用。顶层调用中参数E_{best}的值被设置为一个简单的编辑操作序列，其中删除G1的所有节点，然后添加G2的所有节点和边。

递归算法首先发现E的序列，将图G1转换为子图同构G1'。在这个阶段之后，节点/边插入的平凡序列将G1'到G2转变，这些将放在E的最后。在递归调用中的返回条件之前，这点在图17.7显示。由于这个最终的填充步骤，这些不重要的编辑的成本总是包含在编辑序列E的成本中，其由Cost（E）表示。

图17.7 图编辑距离算法

该算法的整体结构与图17.5的MCG算法相似。在每次递归调用中，首先确定G1是否是G2的子图同构。如果是这样，算法立即返回当前的一组编辑E，在并入可将G1转换为G2的平凡节点或边缘插入之后。如果G1不是G2的子图同构，则该算法继续扩展部分编辑路径E。确定一组候选编辑C，其在应用于G1时可以减小到G2的距离。实际上，这些候选编辑C是启发式确定的，因为知道编辑对距离的精确影响的问题几乎与计算编辑距离一样困难。选择候选编辑的最简单方法是考虑除节点插入之外的所有可能的单位编辑。这些候选编辑可能是节点删除，标签替换和边操作（插入和删除）。对于具有n个节点的图，基于节点的候选操作的总数是O（n），并且基于边的候选操作的数量是O（n^2）。如果可以立即确定这些编辑永远不会成为最佳编辑路径的一部分，则可以启发式地修剪这些候选编辑中的很多。事实上，一些修剪步骤对于确保算法的有限终止至关重要。一些关键的修剪步骤如下：

  1. 如果当前部分编辑路径E中已经存在同一对节点之间的边缘删除操作，则不能将边插入附加到当前部分编辑序列E。类似地，先前插入的边缘不能被删除。 最佳编辑路径永远不会包含具有零网效的编辑对。 这个修剪步骤对于确保有限终止是必要的。
  2. 如果该节点的标签替换存在于当前的部分编辑路径E中，则该节点的标签不能被替换。对于同一节点的重复标签替换显然是不理想的。
  3. 只有在两个具有相同标签的节点之间的G2中存在至少一条边时，边才可以插入到G1中的一对节点之间。
  4. 如果加入E，立刻就会增加E的成本，超出Ebest的成本，这样的候选编辑不用考虑。
  5. 在候选编辑之间进行优先排序时，还可以进行许多其他排序优化。 例如，所有节点删除都可以在所有标签替换之前执行。 可以看出，最佳编辑顺序总是可以这样安排。 类似地，可以首先考虑将标签的整体分布更接近目标图形的标签替换。 一般来说，可以将一个“好功能”与另一个“好功能”联系起来，当它被包含在E中时，它会自然而然地发现寻找好的编辑路径的可能性。 尽早找到好的编辑路径将根据上述标准（4）确保更好的修剪性能。

各种递归搜索算法的主要区别在于使用不同的启发式算法进行候选排序和修剪。读者可以参考本章末尾的参考书目，了解其中一些方法。在修剪后的候选编辑被确定之后，这些编辑中的每一个被应用于G1以创建G1'。该程序被递归地称为对（G 1，G 2），并且按照序列E'来返回。这个过程返回具有E '前置码的最佳编辑序列E_{current}。如果E_{current}成本低于E_{best}（包括用于完全匹配的简单后处理插入编辑），则E_{best}会更新为E_{current}。在程序结束时，返回E_{best}。

该过程被保证终止，因为修剪步骤在E中避免了节点标签替换和边删除中的重复。此外，编辑后的图中节点的数量是单调不增加的，因为更多的编辑被附加到E。这是因为除递归结束之外，E不包含节点插入。对于具有n个节点的图，最多可以执行2个非重复边添加和删除以及可以执行的O（n）个节点删除和标签替换。因此，递归的有限深度O（n^2）也等于E的最大长度。这种方法在最坏的情况下具有指数复杂性。编辑距离通常是昂贵的计算，除非底层图很小。

17.3 基于变换的距离计算

上一节的距离度量的主要问题是面对较大的图在计算上不实用。 许多基于启发式和基于核的方法被用来将图转换成距离计算更有效的空间。 有趣的是，其中一些方法在质量上更加有效，因为它们有能力专注于图的相关部分。

17.3.1 基于频繁子结构的转换和距离计算

这种方法可以帮助我们了解图的频繁图编码特性。 许多应用都是如此。 例如，化合物中苯环（见图17.1）的存在通常会导致特定的性质。 因此，一个图的性质通常可以通过其中存在特定的结构族来描述。 这种直觉表明，语义描述图的一种有意义的方式是根据其频繁子结构形成。 因此，使用了一种转换方法，其中从每个图形创建一个类似文本的向量空间表示。 步骤如下：

  1. 应用17.4章中的频繁的子图挖掘方法发现底层图中的频繁子图模式。这得到图所表示的“词典”。不幸的是，这个词典的规模相当大，许多子图可能是多余的，因为它们彼此相似。
  2. 从第一步中找到的子图中选择子图的子集，以减少频繁子图模式之间的重叠。不同的算法在这一步可能会有所不同，通过使用极少的最大子图，或者使得图的集合之间有足够的不重叠。为每个最终选择的频繁子图Si创建一个新的特征fi。设d是频繁子图（特征）的总数。这是词汇大小，其中将构建类似文本的表示。
  3. 对于每个图Gi，根据特征f1 \cdots fd创建一个向量空间表示。每个图都包含与其包含的子图相对应的特征。每个特征的频率是图Gi中相应子图的出现次数。也可以仅考虑子图的存在或不存在来使用二进制表示而不是频率表示。 tf-idf规范化可以用于向量空间表示，正如13章中所述。

转换完成后，可以使用任何文本相似度函数来计算图形对象之间的距离。使用这种方法的一个优点是，它可以与传统的文本索引（如倒排索引）配对，以进行有效的检索。书目注释包含了一些这些方法的说明。

这种更广泛的方法也可以用于特征转换。因此，使用这种方法可以将任何来自文本的数据挖掘算法应用于图。稍后将讨论如何通过图形挖掘算法（如聚类）以更直接的方式使用此转换方法。这种方法的主要缺点是子图同构是频繁子结构发现的中间步骤。因此，该方法在最坏的情况下具有指数复杂性。尽管如此，许多快速近似常常用来提供更有效的结果，而不会导致精度的显着损失。

17.3.2 拓扑描述符

拓扑描述符通过使用重要结构特征的量化度量作为维度将结构图转换为多维数据。转换完成后，可以在转换的表示上使用多维数据挖掘算法。这种方法可以在基于图形的应用中使用各种各样的多维数据挖掘算法。该方法的缺点是结构信息丢失。尽管如此，拓扑描述符已被证明在化学领域保留了图的重要性质，因此使用相当频繁。一般来说，拓扑描述符在图挖掘中的效用是高度特定领域的。应该指出，拓扑描述符与前一节中的频繁子图方法有许多概念上的相似之处。主要差异在于仔细选择的拓扑参数用于定义新的特征空间而不是频繁的子图。

大多数拓扑描述符都是图形专用的，而少数则是节点专用的。特定节点描述符的矢量有时候描述了几何图形。节点描述符也可以用来丰富节点的标签。拓扑描述符的一些常见示例如下所示：

  1. 摩根指数：这是一个节点特定的指数，它等于节点的第k阶度数。 换句话说，描述符等于在距离k内从节点可到达的节点的数量。 这是描述节点的少数几个描述符之一，而不是完整的图。 通过使用Morgan指数在不同节点上的频率直方图，也可以将节点特定的描述符转换为特定于图形的描述符。

  2. 维纳指数：维纳指数等于所有节点对之间的成对最短路径距离之和。 因此需要计算不同对节点之间的全对最短路径距离。

​ W(G)=\sum_{i,j\in G}d(i,j) \tag{17.4}

维纳指数已知与化合物的化学性质的关系。这个指数的出现是因为它被认为与烷烃分子的沸点密切相关[511]。后来，这种关系也显示了一些分子家族的其他性质，如它们的密度，表面张力，粘度和范德华表面积。随后，该指数也被用于超出化学领域的应用。

  1. Hosoya索引：Hosoya索引等于图中有效的成对节点匹配数。请注意，单词“匹配”在同一个图中是指代节点 - 节点匹配，而不是图形匹配。匹配不需要是最大匹配，甚至空匹配也算作其中一种可能性。 Hosoya指数的确定是＃P完全的，因为图中可能存在指数数量的匹配，特别是密集时。例如，如图17.8所示，只有四个节点的完整图（集团）的Hosoya索引是10。Hosoya索引也被称为Z索引。

    图17.8：四节点图的Hosoya索引

  2. 埃斯特拉达指数：该指数在测量蛋白质折叠程度的化学应用中特别有用。如果λ1...λn是图G的邻接矩阵的特征值，则埃斯特拉达指数E（G）定义如下：

​ E(G)=\sum_{i=1}^n e^{\lambda_i} \tag{17.5}

  1. 电路等级：电路等级C（G）等于为了消除所有的圈而需要从图中移除的最小边数。 对于具有m个边，n个节点和k个连通分量的图，该数等于（m-n + k）。 电路级别也被称为圈数。 圈数提供了对图的连接级别的深入了解。

  2. 兰德指数：兰德指数等于连接贡献的成对总和。 如果νi是顶点i的度数，那么Randic指数R（G）定义如下:

R(G)=\sum_{i,j\in G} \frac {1}{\sqrt {v_i \cdot v_j}} \tag{17.6}

​

兰德指数也被称为分子连接性指数。 该指数通常用于较大的有机化合物的背景下，以评估其连接性。 Randic指数可以与电路级别C（G）组合以产生Balaban指数B（G）：

B(G)=\frac {m\cdot R(G)}{C(G)+1} \tag{17.7}

这里，m是网络中的边数。 由于这些指数能够捕获化学化合物的不同性质，因此大多数这些指标在化学领域中的使用相当频繁。

17.3.3 基于核的转换和计算

基于核的方法可用于比基于MCG或基于编辑的方法更快的相似度计算。 而且，这些相似度计算方法可以直接用于支持向量机（SVM）分类器。 这是核方法在图分类中非常流行的原因之一。

几个核经常在图示的情况下使用。以下讨论更常见的问题。 一对图G i和G j之间的核相似度K（G i，G j）是两个图假设变换到一个新空间后的点积，由函数Φ（·）定义。

K（Gi，G j）=Φ（Gi）·Φ（Gj）\tag{17.8}

实际上，Φ（·）的值没有直接定义。 相反，它是根据核函数K（·，·）间接定义的。 有多种方式可以定义内核相似性。

17.3.3.1 随机游走内核

在随机游走内核中，这个想法是比较两幅图中随机游走引起的标签序列。 直观地说，如果在节点对之间随机游走所创建的许多标签序列也相似，那么两张图是相似的。 主要的计算挑战是节点对之间存在可能的随机游走的指数数量。 因此，第一步是定义一对节点序列s1（来自G1）和s2（来自G2）之间的原始核函数k（s1，s2）。 最简单的内核是定义核：k（s1，s2）= I（s1 = s2）\tag{17.9}

图17.9：生成图的例子

这里，I（·）是定义函数，当两个序列相同时取其值为1，否则为0。 然后，将整个核心相似度K（G1，G2）定义为所有可能步行中所有基本序列核的概率的总和：

K(G1,G2)=\sum_{s1,s2}p(s1|G1)·p(s2|G2)·k(s1,s2) \tag{17.10}

这里，p（si | Gi）是图Gi中随机游走序列si的概率。请注意，当两张图使用相同的标签序列时，此内核相似性值会更高。一个关键的挑战是计算这些概率，因为具有特定长度的指数数量的步行，并且步行的长度可以是范围（1，∞）中的任何值。6

随机游动内核使用G1和G2之间的产品图GX。通过在图G1和G2中分别定义每对标签匹配顶点u1和u2之间的顶点[u1，u2]来构建乘积图。在产品图GX中的一对顶点[u1，u2]和[v1，v2]之间添加一条边，当且仅在各个图G1和G2的相应节点之间存在一条边时。换句话说，边（u1，v1）必须存在于G1中，并且边缘（u2，v2）必须存在于G2中。图17.9举例说明了产品图。请注意，产品图中的每一步都对应于两个图G1和G2中的一对标签匹配顶点序列。那么，如果A是产品图的二元邻接矩阵，那么A^k的条目提供不同顶点对之间长度为k的散步数。因此，步行的总加权数可以计算如下:

K(G1,G2)=\sum_{i,j}\sum_ {k=1}^{\infty} λ^k[A^k]_{ij} = \bar{e}^T(I −λA)^{−1}\bar{e} \tag{17.11}

这里，\bar e是的| GX |维列向量，λ∈（0,1）是折扣因子。 折扣因子λ应该总是小于A的最大特征值的倒数，以确保无限求和的收敛。 随机游走内核的另一个变体如下：

K(G1,G2)=\sum_{i,j}\sum_ {k=1}^{\infty}\frac{λ^k}{k!}[A^k]_{ij} = \bar{e}^Texp(\lambda A)\bar{e} \tag{17.12}

当一个集合中的图形大小变化很大时，方程应该用| G1 |·| G2 |进一步归一化17.11和17.12。或者，在随机游走内核的一些概率版本中，向量\bar e^T和\bar e被产品图中各个节点上的随机游走的开始和停止概率所替代。这种计算相当昂贵，可能需要多达O（n^6）时间。

17.3.3.2 最短路径内核

在最短路径内核中，在节点对[i1，j1]∈G1和[i2，j2]∈G2上定义一个基本核ks（i1，j1，i2，i2）。有几种确定核函数ks（i1，i2，j1，j2）的方法。定义内核值的简单方法是当距离d（i1，i2）= d（j1，j2）时将其设置为1，否则为0。那么，整个核心相似度等于所有基本核心在不同四元组节点上的总和：

K（G1，G2）=\sum_ {i1，i2，j1，j2} ks（i1，i2，j1，j2）\tag{17.13}

通过在每个图上应用所有对最短路径算法来计算最短路径核。可以看出，内核计算的复杂度是O（n^4）。虽然这仍然相当昂贵，但对于小图，如化合物，这可能是实用的。

17.4 图中的频繁子结构挖掘

频繁的子图挖掘是图挖掘算法的基本组成部分。许多聚类，分类和相似性搜索技术使用频繁的子结构挖掘作为中间步骤。这是因为频繁的子结构在许多应用程序域中编码图的重要属性。例如，考虑图17.10所示的一系列酚酸。这些代表了一系列具有类似化学性质的有机化合物。这个家族的许多复杂变异可作为植物信号分子和防御物质。酚酸的性质是存在两个频繁的亚结构的直接结果，分别对应于羧基和酚基。这些组也在图17.10中进行了说明。这种子结构性质的相关性不限于化学领域。这就是频繁子结构经常用于许多图挖掘应用程序的中间阶段（如聚类和分类）的原因。

​图17.10：酚酸数据库中频繁子结构的例子

频繁子图的定义与关联模式挖掘的情况相同，除了子图关系用于计算支持而不是子集关系。许多著名的频繁子结构挖掘算法都是基于4章讨论的枚举树原理。 这些方法中最简单的方法是基于Apriori算法。该算法在第四章的图4.2中详细讨论。 Apriori算法使用连接从大小为k的频繁模式创建大小（k + 1）的候选模式。但是，由于图形结构数据的复杂性较高，因此一对图形之间的连接可能不会产生独特的解决方案。例如，候选频繁模式可以由节点扩展或边扩展生成。因此，这两个变量之间的主要区别是k的大小如何分布并连接在一起以创建大小为（k + 1）的候选结构。子图的“大小”可以指其中的节点数量，或者它的边缘取决于是否使用节点扩展或边缘扩展。因此，下面将以一般的方式描述基于Apriori的算法，而不具体讨论节点扩展或边缘扩展。随后，将讨论启用这两个特定变体所需的精确变化。

频繁子图挖掘的整体算法如图17.11所示。该算法的输入是图数据库G = {G1 ... Gn}和最小支持值minsup。基本的算法结构类似于Apriori算法，在第四章的图4.2中进行了讨论。使用逐级算法，其中通过使用来自大小为k的频繁子图Fk的集合的图对上的连接来生成大小为（k + 1）的候选子图C_{k + 1}。如前所述，取决于所使用的特定算法，子图的大小可以指它的节点或边。这两个图需要在大小为（k-1）的子图中进行匹配，以便成功执行连接。由此产生的候选子图的大小（k + 1）。因此，连接处理的重要步骤之一就是确定两个图共享一个大小为（k-1）的子图。在章节17.2中讨论的匹配算法 可用于此目的。在某些应用中，节点标签不同且同构不是问题，这一步可以非常有效地执行。另一方面，对于具有许多重复节点标签的大图，由于同构性，此步骤较慢。

在找到匹配图对之后，对它们执行连接以生成大小为（k + 1）的候选项C_{k + 1}。稍后将描述用于执行联接的方法中的不同的基于节点和基于边缘的变化。此外，使用Apriori修剪技巧。在C_{k + 1}中的候选是这样的，他们的任何k-子图不存在于Fk被修剪。对于每个剩余的候选子图，相对于图数据库G计算支持。子节同构算法在章节中讨论。需要使用17.2来计算支持。所有符合最低支持要求的C_{k + 1}候选均保留在F_{k + 1}中。迭代地重复该过程直至生成空集合F_{k + 1}。此时，算法终止，并报告∪_{i = 1}^kFi中的频繁子图集合。接下来，将描述定义图的大小k的两个不同的方法，分别对应于基于节点和边的联接。

图17.11：基本频繁子图发现算法与Apriori算法有关。 鼓励读者将此伪码与第四章的图4.2中描述的Apriori算法进行比较。

图17.12：使用两个图的基于节点的连接生成的候选

17.4.1基于节点的连接增长

在基于节点的连接中，Fk中频繁子图的大小指的是其中节点k的数量。F1中的单例图包含单个节点。这些是存在于图形数据库G中的至少minsup的图中的节点标签。对于要连接的Fk的两个图，在这两个图之间必须存在具有（k-1）个节点的匹配子图。这个匹配子图也被称为核心。当具有（k-1）个公共节点的双子图被连接以创建具有（k + 1）个节点的候选时，存在模糊性，关于两个不匹配节点之间是否存在边。因此，有两个可能的图形生成，这取决于是否存在两个不同的星系之间的不同点。图17.12给出了产生候选子图的两种可能性的例子。虽然本章不假定边标签与图形相关联，但当标签与边关联时，可能的连接数量会更大。这是因为每个可能的边缘标签必须与新创建的边缘相关联。这将导致更多的候选。此外，如果两个频繁子图之间存在大小（k-1）的同构匹配，则可能需要为每个这样的映射生成候选项（请参见练习8）。因此，为了生成候选，需要在一对图之间发现所有可能的（k-1）共同子图。因此，候选模式数量的爆炸在频繁发现子图的情况下通常比频繁模式发现更显着。

17.4.2基于边的连接增长

在基于边的联接中，Fk中频繁子图的大小指的是其中的边k的数量。 F1中的单例图包含单个边。这些对应于存在于数据库G中的至少minsup的图中的特定节点标签之间的边缘。为了使来自Fk的两个图连接，需要在两个图中存在具有（k-1）个边的匹配子图。得到的候选将包含完全（k + 1）个边。有趣的是，候选节点的数量可能不一定大于加入的各个子图中的节点数量。在图17.13中，说明了使用基于边的连接构建的两个可能候选。请注意，其中一个生成的候选项与原始对图具有相同的节点数。就像基于节点的连接一样，需要考虑候选生成过程中的同构。基于边的连接增长往往会产生更少的候选，因此通常更有效率。书目注释包含指向这些方法的更多细节的说明。

图17.13：使用两个图的基于边的连接生成的候选

17.4.3频繁模式挖掘到图模式挖掘

上述方法和Apriori之间的相似性是相当惊人的。 基于联合的增长策略也可以概括为枚举树状策略。 然而，类似的候选树可以用两种不同的方式生成，分别对应于基于节点和边缘的扩展。 此外，由于同构性，树木生长更为复杂。图Apriori使用了所有类似Apriori方法的广度第一候选树生成方法。 也可以使用其他策略，例如深度第一种方法来扩大候选树。 正如在第四章，几乎所有的频繁模式挖掘算法，包括Apriori和FP-growth，都应该被看作枚举树方法。 因此，这些算法的更广泛的原则也可以推广到图中候选树的增长。 书目注释包含了这些方法的说明。

17.5 图聚类

图聚类问题将由G1 ... Gn表示的n个图的数据库分成组。 图聚类方法或者是基于距离的，或者是基于频繁子结构的。 对于较小的图，基于距离的方法更有效，其中距离可以被鲁棒地和有效地计算。 频繁子结构的方法适用于更大的图，其中距离计算在质量和计算上变得不切实际。

17.5.1基于距离的方法

距离函数的设计对于几乎每一种复杂的数据类型都是特别重要的，因为它们适用于聚类方法，例如k-medoids和光谱方法，它们仅依赖于距离函数的设计。 几乎所有在13-16章中讨论的复杂数据类型使用这种通用方法进行聚类。 这就是距离函数设计通常是每个数据领域需要解决的最基本问题的原因。 本章第17.2和17.3节讨论了图中距离计算的方法。 在设计了距离函数之后，可以使用以下两种方法：

  1. 在第六章的6.3.4节中介绍的k-medoids方法使用了一种基于代表性的方法，其中数据对象距其最近代表的距离用于执行聚类。 使用一组k代表，并通过使用适当设计的距离函数将数据对象分配给其最近的代表。 k代表的集合通过使用爬坡方法逐步优化，其中代表与其他数据对象迭代交换以改善聚类目标函数值。 读者可以参考第六章了解k-medoids算法的细节。 该算法的一个关键特性是在距离函数被定义后，计算不依赖于数据类型的性质。
  2. 第二种常用的方法是光谱方法。在这种情况下，单个图形对象被用来构建一个单一的大型邻域图。后一个图是一个更高层的相似度图，其中每个节点对应于来自原始数据库的（较小的）图对象之一，并且边的权重等于两个对象之间的相似度。正如在第六章的6.7节所示，通过使用内核转换，可以将距离转换为相似度值。每个节点都连接到其具有无向边的k个最近的邻居。因此，聚类图对象的问题被转化为在单个大图中聚集节点的问题。这个问题在第六章的6.7节中简要地讨论过并在第19章的19.3节中详细说明。任何网络聚类或社区检测算法都可以用来对节点进行聚类，尽管频谱方法的使用相当普遍。

节点集群确定后，它们将映射回图形对象的集群。由于两个原因，当单个图形对象很大时，上述方法效果不佳。计算大型图形对象之间的距离通常在计算上很昂贵。图距离函数（如基于匹配的方法）具有随图对象大小呈指数增长的复杂度。这种方法的有效性也随着图形大小的增加而急剧下降。这是因为这些图表只能在频繁重复的某些部分相似。图表中罕见的部分对于特定的图形来说可能是唯一的。事实上，许多小的子结构可能会在两个图表中重复出现。因此，基于匹配的距离函数可能无法正确比较不同图形的关键特征。一种可能性是使用基于子结构的距离函数，正如在17.3.1章节中讨论的那样。 更直接的方法是使用频繁的基于子结构的方法。

17.5.2 基于频繁子结构的方法

这些方法从数据中提取频繁的子图并在输入图中使用它们的成员来确定聚类。基本前提是频繁的子图表示聚类成员资格，因为它们倾向于定义特定于应用程序的属性。例如，在有机化学应用中，苯环（如图17.1a的子图所示）是经常发生的子结构，表明该化合物具有特定的化学性质。在XML应用程序中，频繁的子结构对应于实体之间的重要结构关系。因此，图中这些子结构的成员资格高度表明了相似性和群集成员资格。有趣的是，频繁模式挖掘算法也用于多维聚类。一个例子是CLIQUE算法（参见第7章第7.4.1节）。在下面的章节中，将描述图形聚类的两种不同方法。第一种是可用于将文本聚类方法应用于图域的通用转换方法。第二种是将图簇与其频繁子结构关联的更直接的迭代方法。

17.5.2.1泛型转换方法

这种方法将图数据库转换为类似文本的域，以便可以利用各种文本聚类算法。广义的方法可以描述如下：

1.应用17.4节中的频繁的子图挖掘方法，以发现底层图中的频繁子图模式。选择一个子图子集以减少不同子图之间的重叠。不同的算法可能在这个步骤中通过使用偶然最大的子图而变化，或者说图的子集足够不相互重叠。为每个发现的频繁子图Si创建一个新的特征fi。设d是频繁子图（特征）的总数。这是“词汇”的大小，其中将构建类似文本的表示。

2.对于每个图Gi，根据特征f1 ... fd创建一个向量空间表示。每个图都包含与其包含的子图相对应的特征。每个特征的频率是图Gi中相应子图的出现次数。也可以通过仅考虑子图的存在或不存在而不是存在频率则使用二进制表示。使用tf-idf对矢量空间表示法进行归一化，如第13章所述。

3.使用第13章中13.3节中讨论的任何文本聚类算法，以发现新创建的文本对象的集群。将文本聚类映射到图形对象聚类。

这种使用基于文本的方法的更广泛的方法经常用于许多上下文数据类型。例如，在第15章15.3.3中讨论了序列聚类几乎完全类似的方法。这是因为大多数数据类型都可以定义频繁模式挖掘方法的修改版本。应该指出的是，虽然这里讨论了基于子结构的转换，但也可以使用本章前面讨论的许多基于内核的转换和拓扑描述符。例如，核心k均值算法可以与本章讨论的图形核心结合使用。

17.5.2.2 XProj：使用频繁子图发现进行直接聚类

XProj算法的名称源自它最初为XML图提出的方法，并且子结构可以被视为图的PROJection。尽管如此，这种方法并不是专门针对XML结构的，它可以应用于任何其他图形领域，例如化合物。 XProj算法使用子结构发现过程作为重要的子例程，并且根据数据域的不同，不同的应用可能会使用不同的子结构发现方法。因此，下面将提供用于图聚类的XProj算法的通用描述，尽管子结构发现过程可以以特定于应用的方式实现。由于该算法使用频繁的子结构进行聚类处理，因此算法的额外输入是最小支持minsup。该算法的另一个输入是开采频繁子结构的大小l。频繁子结构的大小是固定的，以确保鲁棒的计算相似性。这些是用户定义的参数，可以调整以获得最有效的结果。

算法可以被看作是一种类似于k-medoids的代表性方法，除了每个代表是一组频繁的子结构。这些代表了每个群体的局部子结构。使用这些次级子结构代替原始图表是至关重要的。这是因为当图的大小较大时，无法在图对之间有效地计算距离。另一方面，频繁子结构的成员提供了一种更直观的计算相似度的方法。应该指出的是，与变换方法不同，频繁子结构对于每个群集是局部的，因此被更好地优化。与通用转换方法相比，这是该方法的主要优点。

图17.14：基于频繁子图的聚类算法（高级描述）

共有k个这样的重复子结构集F 1 ... F k，并且图数据库被划分为围绕这些本地化代表的k个组。该算法用数据库G的随机分区初始化为k个集群。这些k个簇由C1 ... Ck表示。这些群集Ci中的每一个的频繁子结构Fi可以使用任何频繁的子结构发现算法来确定。随后，基于Gj与每个代表性集合Fi的相似度，将Gj∈G中的每个图表分配给代表集合Fi中的一个。相似度计算的细节将在后面讨论。迭代地重复该过程，以便从簇Ci生成代表集Fi，并且从频繁集Fi生成簇Ci。重复该过程，直到每个图Gj与其分配的代表性集合Fi的平均相似度的变化不大于用户定义的阈值。此时，算法被假定已经收敛，并且终止。整个算法如图17.14所示。

仍然要描述如何计算图Gj和代表性集合Fi之间的相似性。 Gj和Fi之间的相似性通过使用覆盖准则来计算。 Gj和Fi之间的相似度等于Fi中频繁子结构的一部分，它们是Gj的一个子图。

一个主要的计算挑战是确定Fi中的频繁子结构可能太昂贵。此外，Fi中可能存在大量频繁的子结构，这些子结构彼此高度重叠。为了解决这些问题，XProj算法提出了许多优化。第一个优化是频繁子结构不需要精确确定。设计了一种频繁子结构挖掘的近似算法。第二个优化是只有长度为l的非重叠子结构的一个子集被包括在集合Fi中。这些优化的细节可以在参考书目中讨论的说明中找到。

17.6 图分类

假定一组n个图G 1 ... G n是可用的，但是这些图的仅仅一部分被标记。 其中，第一个n_t≤n图被标记，其余（n-n_t）图未标记。 标签从\{1 ... k\}绘制。 希望使用训练图上的标签来推断未标记图的标签。

17.6.1 基于距离的方法

当基础图的大小很小时，基于距离的方法是最适合的，并且可以高效地计算距离。最近邻方法和集体分类方法是通常用于分类的两种基于距离的方法。后一种方法是转导式半监督方法，其中训练和测试实例需要同时用于分类过程。这些方法在下面详细描述：

  1. 最近邻居方法：对于每个测试例子，确定k个最近邻居。来自这些最近邻居的主要标签被报告为相关标签。多维数据的最近邻居方法在第十章的10.8节。该方法的唯一修改是使用不同的距离函数，适用于图形数据类型。
  2. 基于图的方法：这是一个半监督的方法，在11章的11.6.3节中讨论。在基于图的方法中，从训练和测试图对象构造更高级的邻域图。重要的是不要混淆邻域图的概念和原始图对象的概念。原始图形对象对应于邻居图。每个节点基于距离值连接到k个最近邻居对象。这导致包含标记节点和未标记节点的图形。这是集体分类问题，各部分的描述见19章的19.4节。集体分类算法可用于推导邻域图中节点的标签。这些派生标签然后可以映射回未标记的图形对象。

当基础图形对象很小时，基于距离的方法通常是有效的。对于较大的图形对象，距离的计算变得太昂贵。此外，当两个图中存在多个共同子结构时，从精度角度来看，距离计算不再有效。

17.6.2 基于频繁子结构的方法

基于模式的方法从数据中提取频繁的子图，并在不同的图中使用它们的成员资格，以建立分类模型。 就像聚类一样，主要假设是图的频繁发生的部分可能与图的特定于应用的特性有关。 例如，图17.10中的酚酸的特征在于对应于羧基和酚基的两个常见亚结构。 这些子结构因此表征了一个家族或一类化合物的重要特性。 这在化学领域以外的许多不同应用中通常都是如此。 正如在第十章中的10.4节，频繁模式通常用于基于规则的分类，即使在“多边形”多维域。 就像聚类一样，可以使用通用转换方法或更直接的基于规则的方法。

17.6.2.1 通用转换方法

这种方法通常与前面关于聚类的章节中讨论的转换方法差不多。 但是，监督的影响有一些差异。 广义的方法可以描述如下：

  1. 应用频繁的17.4中的子图挖掘方法，发现底层图中的频繁子图模式。选择一个子图子集以减少不同子图之间的重叠。例如，可以使用使冗余最小化并使特征的相关性最大化的特征选择算法。这些特征选择算法在第十章的10.2节中提到。使d作为频繁子图（特征）的总数。这是“词汇”的大小，其中将构建类似文本的表示。
  2. 对于每个图Gi，根据找到的d个特征创建一个向量空间表示。每个图都包含与其包含的子图相对应的特征。每个特征的频率等于图Gi中对应子图的出现次数。也可以仅考虑子图的存在或不存在而不是存在频率来使用二进制表示。使用tf-idf对矢量空间表示法进行归一化，如第13章所述。
  3. 选择第十三章13.5节讨论的任何文本分类算法建立一个分类模型。使用模型来分类测试实例。

这种方法提供了灵活的框架。在进行了转换之后，可以使用各种各样的算法。它还允许使用不同类型的监督特征选择方法，以确保最有区别的结构用于分类。

17.6.2.2 XRules：基于规则的方法

XRules方法是在XML数据的上下文中提出的，但它可以在任何图形数据库的上下文中使用。 这是一种基于规则的方法，将频繁的子结构与不同类别联系起来。 训练阶段包含三个步骤：

  1. 在第一阶段，确定具有充分支持和置信度的频繁子结构。 每条规则的形式如下：

​ Fg ⇒ c

符号Fg表示频繁的子结构，并且c是类别标签。 许多其他措施可以用来量化规则的强度，而不是置信度。 例子包括似然比或罕见类情景中的成本加权置信度。 Fg⇒c的似然比是包含c的例子中Fg的分数支持率与不包含c的例子中Fg的部分支持率的比率。 似然比大于1表示该规则很可能属于特定的类。 衡量类特定相关性的这些不同方式的通用术语是规则强度。

  1. 在第二阶段，规则被排序和修剪。这些规则是通过减小强度来排序的。统计阈值和最小强度可用于调整低强度规则。这产生了用于分类的有序规则的紧凑集合R.

  2. 在最后阶段，设置一个默认类，它可以用来对R中没有任何规则覆盖的测试实例进行分类。默认类被设置为未被规则集R覆盖的训练实例集的主导类。如果规则的左侧是图的子结构，则图由规则覆盖。在所有训练实例都被规则集R覆盖的情况下，则在整个训练数据中默认的类被设置为占优势的类。在类别与成本相关的情况下，成本敏感的权重用于确定大多数类别。

训练模型构建完成后，可用于如下分类。对于给定的测试图G，由G确定的规则被确定。如果没有规则文件，则会报告默认类。令Rc（G）为由G规定的规则集。注意，这些不同的规则可能不会产生相同的G预测。因此，不同规则的冲突预测需要有意义地结合。用于组合预测的不同标准如下：

  1. 平均强度：确定预测每个类别的规则的平均强度。报告平均最高强度的类别。
  2. 最佳规则：最高规则是根据前面讨论的优先顺序确定的。这个规则的类标签被报告。
  3. Top-k平均强度：这可以被认为是前两种方法的组合。每个类的top-k规则的平均强度用于确定预测标签。

XRules过程使用频繁子结构发现的有效过程以及规则量化的许多其他变体。请参阅书目注释。

17.6.3内核支持向量机

核支持向量机可以利用训练和测试内核之间的内核相似性构造分类器。如在第10章的第9.6.4节中讨论的，只要基于内核的相似性K（Gi，G j ）之间的任何一对图形对象可用。 因此，该方法对所使用的特定数据类型是不可知的。 不同种类的图形内核在17.3.3中讨论。 任何这些内核都可以与SVM方法结合使用。 参考第10章的第10.6.4节获得有关内核如何与SVM分类器结合使用的细节。

17.7 总结

本章研究挖掘图形数据集的问题。图形数据是一个具有挑战性的分析领域，因为当底层标签中存在重复时，难以匹配两个图形。这被称为图同构。图匹配的大多数方法在最坏的情况下需要指数时间。一对图之间的MCG可以用来定义图之间的距离度量。编辑距离度量还使用与MCG算法密切相关的算法。由于图中匹配算法的复杂性，一种不同的方法是将图数据库转换为更简单的文本表示法，就其定义的距离函数而言。一类重要的图距离函数是核函数。它们可以用于聚类和分类。

频繁的子结构发现算法是一个重要的构建块，因为它可以用于其他图挖掘问题，如聚类和分类。类Apriori算法使用节点增长策略或边缘增长策略来生成候选和相应的频繁子结构。图数据的大多数聚类和分类算法都是基于距离或基于频繁的子结构。基于距离的方法包括聚类的k-medoids和谱方法。对于分类，基于距离的方法包括k-最近邻方法或基于图的半监督方法。基于核的SVM也可以被认为是专门的基于距离的方法，其中SVM与数据对象之间的相似性结合使用。

频繁的基于子结构的方法经常用于图聚类和分类。通用方法是将图转换为与文本数据类似的新特征表示。任何文本聚类或分类算法都可以应用于这种表示。另一种方法是直接挖掘频繁的子结构，并将它们用作代表性的集群集合或者区分规则的前提。 XProj和XRules算法基于这个原则。

17.8 书目注释

图表匹配的问题在[26]的调查中得到解决。图[164]中提出了Ullman图匹配算法。其他两种众所周知的图匹配方法是VF2 [162]和QuickSI [163]。其他近似匹配方法在[313,314,521]中讨论。图形匹配问题的NP-硬度的证明可以在[221,164]中找到。 [120]研究了使用MCG定义距离函数。 [119]中详细研究了图编辑距离和最大公共子图问题之间的关系。本章讨论的图编辑距离算法简化了[384]中提出的算法。 [409]中讨论了许多用于计算图编辑距离的快速算法。在[408]中研究了学习编辑成本的问题。 Bunke在[26]中的调查也讨论了计算图编辑成本的方法。关于在药物设计中使用拓扑描述符的描述可以在[236]中找到。随机游走内核在[225,298]中讨论，最短路径内核在[103]中讨论。 [225]中的工作也提供了关于图内核的一般性讨论。文献[42]的工作表明频繁的基于子结构的相似性计算可以在数据挖掘应用中提供稳健的结果。

频数子图挖掘的节点增长策略是由一个Motoda的Inokuchi，Washio提出的[282]。边缘增长策略由Kuramochi和Karypis提出[331]。 gSpan算法由Yan和Han [519]提出并使用深度第一种方法来构建图模式的候选树。在[276]中讨论了使用垂直表示进行图形模式挖掘的方法。 [536]讨论了在森林中开采频繁树木的问题。关于图聚类和分类的调查可以在[26]中找到。 XProj算法在[42]中讨论，XRules算法在[540]中讨论。基于核SVM的分类方法在Tsuda [26]的图分类章节中讨论。

17.9 习题

1.考虑包含偶数2·n个节点的派系的两个图。让每个图中的正好一半的节点属于标签A和B.这两个图之间的同构匹配的总数是多少？

2.考虑两个包含2·n个节点和n个不同标签的图，每个标签出现两次。两张图之间同构匹配的最大次数是多少？

3.实现不带修剪优化的子图同构的基本算法。通过尝试匹配包含不同数量节点的随机生成图对来测试它。运行时间如何随图形的大小而变化？

4.计算图17.1对乙酰氨基酚图的每个节点的1阶和2阶摩根指数。摩根指数如何随标签（对应于化学元素）而变化？

5.编写一个计算机程序来计算本章讨论的图的每个拓扑描述符。

6.编写一个计算机程序来执行基于节点的候选增长，以便进行频繁的子图发现。如果需要，请参考书目注释，以便描述算法的特定细节。

7.编写一个计算机程序来执行频繁子图发现的基于边缘的候选增长。请参考文献的书目注释，以描述该算法的具体细节。

8.显示可以在下面两个图之间执行的不同基于节点的连接，同时考虑同构。

9.显示可以在练习8的两个图形之间执行的基于边缘的不同连接，同时考虑同构。

10.使用一对图确定可以使用基于节点的连接增长生成的候选的最大数目，同时考虑同构。假设这些图的匹配核心是一个大小为k的循环。连接部分的核心条件是什么导致了这种情况？

11.讨论基于节点的增长和基于边缘的增长策略如何转化为类似于频繁模式挖掘中枚举树的候选树结构。

12.如本章所讨论的那样，实现一个计算机程序来为图形数据库构建一个类似文本的表示。使用您选择的任何特征选择方法来最小化冗余。用这种表示法实现k-means聚类算法。

13.对分类问题重复练习12。使用第10章讨论过的朴素贝叶斯分类器作为最后的分类步骤，并从同一章节中选择适当选择的监督特征选择方法。

14.对于查询图断开连接的情况，子图同构算法会有哪些变化？