This post is a Chinese introduction to frequent subgraph mining (English here).
在这篇博文中，我将介绍一种有趣的数据挖掘算法，叫频繁子图挖掘，它主要用来在图中挖掘有用模式。这一算法非常重要，因为数据在很多领域自然地以图来表示(比如社交网络、化学分子、国家路网)。因此，通过分析图形数据来发现有趣、意外、有用的模式是有必要的，它们可以用来帮助理解数据或者做决策。
什么是图？一点理论…
在讨论图分析之前，我们先介绍几个定义。图是一组有一些标签的顶点和边。用一个例子来说明一下。参考下图：
这个图包含四个顶点（描绘成黄色的圆圈）。这些顶点都有“10”、“11”等标签。这些标签提供了有关顶点的信息。例如，把这张图想象成一个化学分子。标签10和11可以分别代表氢和氧这两种化学元素。标签不需要是唯一的。换句话说，同一个标签可以用来描述同一个图中的几个顶点。例如，如果上图表示化学分子，则标签”10″和”11″可分别用于代表氧和氢的所有顶点。
除了顶点，图中也包含边。边是顶点之间的连线，这里用粗黑线表示。边也有一些标签。在本例中，使用了四个标签，即”20″、”21″、”22″和”23″。这些标签代表了顶点之间不同类型的关系。边的标签不唯一。
图的类型：连通图和非连通图
现实生活中可以找到许多不同类型的图。图分为连通图或非连通图。让我们用一个例子来解释一下。参考以下两个图：
左边的图称为连通图，因为沿着边可以从任何顶点到其他顶点。例如，想象一下顶点代表着城市，边是城市之间的道路。这是一个可以沿着道路从一个城市到任何其他城市的连通图。如果图没有连通，则称它是一个非连通图。例如，右边的图是断开的，因为不能沿着边从其他顶点到达顶点A。在下面的文章中，我们将使用术语“图”来表示连通图。因此，我们下面讨论的所有图都是连通图。
图的类型：有向图和无向图
区分有向图和无向图也是很有用的。在无向图中，边是双向的，而在有向图中，边可以是单向的也可以是双向的。让我们用一个例子来说明一下。
左边是无向图，而右边是有向图。在现实生活中有向图的例子有哪些呢？例如，考虑一个图, 它的顶点表示位置，边为道路。有些道路可以双向行驶，而有些道路只能单向行驶（城市中的“单行道”）。
一些数据挖掘算法被设计成只处理无向图、有向图或两者都支持。
分析图
我们已经介绍了一些关于图的理论，那么我们可以做什么样的数据挖掘任务来分析图？这个问题有很多答案。答案取决于我们的目标是什么，也取决于我们正在分析的图的类型（有向图/无向图、连通图/非连通图、单个图或多个图）。
在这篇博文中，我将阐述一个被广泛研究的挖掘任务，称为频繁子图挖掘。子图挖掘的目的是在一组图（图形数据库）中发现令人感兴趣的子图。但我们如何判断一个子图是否令人感兴趣呢？这取决于应用场景。兴趣度可以用各种方式来定义。传统上，如果一个子图在一组图中出现多次，它就被认为是令人感兴趣的。换句话说，我们希望发现多个图共有的子图。例如，找出几种化学分子共有的化学元素, 这种类型的联系是很有用的。
在一组图中查找频繁子图的做法称为频繁子图挖掘。作为输入者，用户必须提供：
▪图数据库(一组图)
▪一个称为最小支持阈值的参数(minsup)。
然后，频繁子图挖掘算法将枚举输出所有的频繁子图。频繁子图是至少在图数据库中出现minsup次的子图。下面，让我们看一下包含以下三个图的图数据库：
现在，假设我们要发现至少出现在三个图中的所有子图。因此，我们将把最小参数设置为3。通过应用频繁子图挖掘算法，我们将得到至少出现在三个图中的所有子图的集合：
参考一下第三个子图（“频繁子图3”）。这个子图是频繁的，有3个支持度（频度），因为它出现在三个输入图中。这些出现以红色标出，如下：
现在一个重要的问题是如何设置minsup参数？在实际应用中，一般是通过试错法来确定参数。如果此参数设置得太高，则会找到很少的子图，而如果设置得太低，则会根据输入数据库找到数百万的子图。
现在，在实践中，哪些工具或算法可以用来查找频繁的子图？有各种频繁子图挖掘算法。其中最著名的是GASTON, FSG和GSPAN。
在单个图中挖掘频繁子图
除了发现几个图共有的子图外，频繁子图挖掘的问题也有一些变体，它包括在单个图中查找所有频繁子图而不是在图数据库中查找。方法几乎是一样的。目的也是发现频繁出现或令人感兴趣的子图。唯一的区别是支持度（频度）是如何计算的。对于这个变化，子图的支持度是它在单个输入图中出现的次数。例如，参考以下输入图：
这个图包含七个顶点和六个边。如果我们通过将minsup参数设置为2，在这个单图上执行频繁子图挖掘，可以发现以下五个频繁的子图：
这些子图是频繁的，因为它们在输入图中至少出现过两次。例如，参考“频繁子图5”。这个子图有2个支持，因为它在输入图中有两次出现。这两种情况分别用红色和蓝色突出显示在下面。
在图数据库中发现模式的算法通常可以用来发现单个图中的模式。
结论
在这篇博文中，我们介绍了频繁子图挖掘的问题，包括发现在一组图中频繁出现的子图。这个数据挖掘问题已经被研究了15年之多，并提出了许多算法。有些算法是精确算法（会找到正确答案），而有些则是近似算法（不保证找到正确答案，但可能更快）。
一些算法也被设计来处理有向图或无向图，或者在单个图或图数据库中挖掘子图，或者同时做这两种。此外，子图挖掘问题还有其他几种变体，如在图中发现频繁路径，或在图中发现频繁树。
此外，在一般数据挖掘中，还研究了与图有关的许多其他问题，如优化问题、社交网络中的社群检测、关系分类等。
对比其它类型的数据, 一般来说，与图有关的问题是相当复杂的。子图挖掘困难的原因之一是算法通常需要检查“子图同构”，即比较子图以确定它们是否等价。尽管如此，我认为这些问题是相当有趣的，因为有一些研究上的挑战。
希望你喜欢这篇博文。如果对这个话题感兴趣，我将来可能会在图挖掘上再写一篇博文。
—
Philippe Fournier-Viger是计算机科学教授，也是提供了200多种数据挖掘算法的开源数据挖掘软件SPMF的创始人，。
