面向大图的Top⁃Rank⁃K频繁模式挖掘算法

图1 社交网络示例图和在不同支持度阈值设定下的频繁模式

Fig.1 A social network graph and frequent patterns under different support threshold settings

上述例子表明：（1）支持度阈值设置过大会导致返回的模式数量过少，且模式中单边模式的占比过大，实际应用价值偏低；（2）一个过小的支持度阈值会返回过多的模式，使用户难以找到满意的模式，还会增加算法的搜索空间和计算开销，严重的甚至可能导致程序因内存溢出而崩溃.

此外，现有的Top⁃Rank⁃K频繁模式挖掘算法（如NTK^［6］和iNTK^［7］）主要应用于事务型数据库的频繁项集挖掘.随着图数据对描述关系的优势日渐显现，频繁模式挖掘的研究逐渐扩展到包含图结构数据的领域，已提出多种针对Top⁃K频繁模式挖掘的算法（如PBSM^［8］，Resling^［9］和Dminer^［10］），但它们都需要预先设定一个初始支持度阈值，并且仅用模式自身的支持度来衡量模式的价值，导致挖掘结果偏向小而频繁的模式.

以上观察激发了本文对单一大图上的Top⁃Rank⁃K频繁模式挖掘问题的探究，即在无初始支持度阈值的情况下高效地挖掘排名前 $k$ 的频繁模式.为此，本文需要解决以下两个关键问题.

（1）设计一个兴趣度指标来对模式进行排名，该指标在理想状态下能同时考虑模式的支持度和模式的大小.

（2）设计一种有效的算法，在没有初始支持度阈值输入时也能高效地进行频繁模式挖掘.

本文的具体贡献如下.

（1）提出一种基于模式大小和模式支持度的模式兴趣度度量指标.

（2）提出一种无须设置初始支持度阈值的Top⁃Rank⁃K模式挖掘算法ItrMiner，只须输入图 $G$ 和一个整数 $k$ 就能返回兴趣度排名在前 $k$ 名的模式.对无初始支持度阈值可能导致的大量低兴趣度模式问题，ItrMiner采用兴趣度优先的树模式识别策略和一种新颖的模式扩展约束条件，有效减少了低兴趣度候选模式的生成，显著提升了挖掘效率.

（3）在真实图和人工合成图数据集上进行了广泛的实验研究，验证了ItrMiner的性能.首先，ItrMiner模式的扩展约束有效性较高，和无扩展约束优化的ItrMiner_nopt相比，效率提升最高可达9.5倍；其次，与Grami算法进行了对比，验证了ItrMiner的有效性和可行性，为传统频繁模式挖掘提供了一种有价值的替代方案；另外，ItrMiner的执行效率和可扩展性表现良好，尤其在稠密的数据集上，其时间开销仅为基线算法Top⁃K Graph Miner （TKG）的13.2%.

1 相关工作

Top⁃Rank⁃K频繁模式挖掘最早由Deng and Fang^［11］提出，以模式的支持度作为排名的参考，用于在事务型数据库中寻找排名前 $k$ 的频繁项集.还有大量集中在频繁项集上的Top⁃Rank⁃K模式挖掘研究，主要分两个方向扩展：第一种是算法性能优化，如NTK^［6］，iNTK^［7］和TK⁃FIN算法^［12］等；第二种是横向功能上的扩展，例如从不确定数据中挖掘Top⁃Rank⁃K模式的UFAE算法^［13］和用于挖掘带权重的频繁项集等的TFWIN+算法^［14］.

图数据在描述数据关系方面的卓越表现日益凸显，频繁模式挖掘的研究方向逐渐从传统的事务型数据库扩展到包含图结构数据的领域，单一大图数据的频繁模式挖掘问题受到了众多学者的关注.其中，Sigram^［15］和Grami^［16］是两种代表性算法.Sigram采用支持度大于指定阈值的顶点来扩展模式并生成候选模式，通过搜索候选模式的匹配来计算其支持度，然而，采用存储模式匹配来计算支持度的方式会消耗大量内存.为了解决这一问题，Elseidy et al^［16］提出Grami算法，将子图同构查找问题转换为约束满足问题CSP （Constraint Satisfaction Problem），通过MNI （Minimum Image）支持度规则，找到足够的证据来证明该模式是频繁的部分匹配.

随着图结构数据规模的增大，为了提高在单图上进行频繁模式挖掘的效率，Arabesque^［17］，Fractal^［18］和ScaleMine^［19］等分布式挖掘算法被提出.其中，Arabesque采用BFS （Breadth First Search）策略来识别频繁模式，导致每个工作站点需要生成并存储大量的中间状态，内存开销较大.为了解决该问题，Fractal采用DFS （Depth First Search）以及模式重复生成策略，有效降低了内存消耗，并且使用局部感知的任务窃取策略来实现动态负载均衡.另一个分布式系统ScaleMine将模式挖掘分成近似挖掘和精确挖掘两个阶段工作，通过近似挖掘的结果来指导精确挖掘阶段的负载分配，实现更好的负载平衡，提升了算法的执行效率.和上述分布式算法相比，G⁃Miner^［20］采用一种细粒度的图划分方法来保证分割子图的局部性，并通过任务窃取策略来实现负载均衡.该方法不再需要每个工作站点都加载完整的输入图，可以有效地处理数据规模超过单机内存的超大单图.此外，与G⁃Miner采用的图划分方法不同，李玲等^［21］提出一种基于垂直分解框架的分布式框架，并设计了Desu⁃FSM算法，旨在挖掘大规模图中的封闭子图.

实际应用中用户通常只关注最感兴趣的前 $k$ 个模式，因此，Top⁃K模式挖掘的重要性逐渐显现.例如，为了降低枚举成本，Chen et al^［8］引入基于等价顶点的图压缩技术对数据进行预处理来挖掘前 $k$ 个最频繁的子图.为了满足用户对不同兴趣度指标的需求，Natarajan and Ranu^［9］开发了一个名为Resling的通用框架，通过基于随机游走的算法对模式进行多样性排名来挖掘前 $k$ 个最具代表性的频繁模式.与Resling类似，Wang et al^［10］重新定义模式的多样性，设计了一种多样性挖掘前 $k$ 个频繁模式的Dminer算法.为了进一步提高算法的执行效率，AprTopK^［22］采用逐层扩展策略，近似挖掘满足支持度阈值的前 $k$ 个最大频繁模式.

对于频繁模式挖掘，还有部分工作专注于避免支持度阈值设置的困扰，提出了无须设置初始支持度阈值的算法.其中，TGP^［23］采用名为Lexicographical Pattern Net的结构来存储所有子图的DFS代码，并利用该结构来挖掘前 $k$ 个最频繁的封闭子图，但由于TGP需要显示生成所有模式，执行效率不高.为了解决这一问题，Saha and Al Hasan^［24］提出一种基于MCMC （Markov Chain Monte Carlo）抽样的方法FS³来挖掘概率意义上的前 $k$ 个最频繁的子图.FS³通过采样再挖掘的方式，有效地提升了算法的运行效率，但无法准确发现所有的模式.因此，Fournier⁃Viger et al^［25］提出一种采用动态规划策略实现快速提升支持度阈值的精确挖掘算法TKG.此外，FastPat^［26］引入元索引的概念，通过预先指定核心模式，在知识图谱中挖掘出前 $k$ 个支持度最大的频繁模式.

虽然现有方法可以识别满足支持度阈值的全部或前 $k$ 个频繁模式以及通过一些约束条件在不设定支持度阈值的情况下识别前 $k$ 个最频繁的模式，但它们都没能有效解决在不设置支持度阈值的情况下综合考虑模式的大小和支持度以挖掘用户更满意的模式的问题.本文提出基于图数据的新型频繁模式挖掘方法，实现了在无支持度阈值的情况下准确地挖掘兴趣度排名在前 $k$ 的频繁模式.该方法引入一项结合模式大小和支持度的“兴趣度”函数来评估模式的价值，改进了仅使用支持度度量模式的传统方法.此外，为了提高挖掘效率，还设计了一项有效的剪枝过滤技术.

2 基本概念

本文研究的数据集包含带标签的图，每个点都有一个标签来描述其属性.首先回顾图、模式和模式匹配的概念，再对频繁模式挖掘进行形式化描述.

2.1　图、模式与模式匹配

定义1

图和子图给定三元组标签图 $G = (V, E, L)$ ，其中， $V$ 是顶点集合； $E \subseteq V \times V$ 是边集合； $V$ 中每个节点 $v$ 携带 $L (v)$ ，表示其标签或内容.

图 $G$ 的子图 $G_{s}$ 表示为 $G_{s} = (V_{s}, E_{s}, L_{s})$ 的三元组，其中， $V_{s} \subseteq V, E_{s} \subseteq E$ ，针对每个节点 $v \in V_{s}$ ，都有 $L_{s} (v) = L (v)$ ，称图 $G_{s}$ 为图 $G$ 的一个子图.

定义2

模式和子模式给定一个模式 $Q = (V_{p}, E_{p}, f_{v})$ ，其中， $V_{p}$ 和 $E_{p}$ 分别是节点和边的集合；针对每一个 $u \in V_{p}$ ， $f_{v} (u)$ 被定义为 $' A = a'$ 形式的原子公式的连结， $A$ 表示节点 $u$ 的一个属性， $a$ 是属性 $A$ 对应的值.通过一次模式扩展，可以得到模式 $Q^{'} = (V_{p}^{'}, E_{p}^{'}, f_{v}^{'})$ ，其中， $Q^{'} \supseteq Q$ . $Q^{'}$ 比模式 $Q$ 多一条边和一个顶点（也可能只多一条边）.同时，模式 $Q$ 称为父模式，模式 $Q^{'}$ 称为子模式.

定义3

模式匹配给定图 $G = (V, E, L)$ 和模式 $Q = (V_{p}, E_{p}, f_{v})$ ，如果 $G$ 中节点 $v$ 满足 $Q$ 中节点 $u$ 的查询条件，即对于每一个 $f_{v} (u)$ 中的原子公式 $A = a$ ，在 $L (v)$ 中都有对应的属性 $A$ ，使得 $v . A = a$ ，则称 $v$ 是 $u$ 的匹配，并用 $v ~ u$ 表示两者间的匹配关系.

图 $G$ 中模式 $Q$ 的匹配是一个从 $Q$ 到 $G$ 的同构映射 $f$ ，使得：

（1）对于每个节点 $u \in V_{p}$ ， $f_{v} (u) ~ L (f (u))$ ；

（2）对于每个模式边 $(u, u^{'}) \in E_{p}$ 当且仅当 $(f (u), f (u^{'})) \in E$ .

这样，当模式 $Q$ 与 $G$ 的子图 $G_{s} = (V_{s}, E_{s}, L_{s})$ 存在同构映射关系 $f$ 时， $G_{s}$ 为 $Q$ 在 $G$ 中的一个匹配.

模式 $Q$ 在 $G$ 中的匹配通常不止一个，本文使用 $M (Q, G)$ 表示模式 $Q$ 在图 $G$ 中的所有匹配.

例2

图2a的图 $G_{a}$ 中存在一个具有点集 $\{B A,$

图2

图2 样本图、模式、模式定义域及其模式匹配

Fig2 A sample of graph，patterns，domains and their matches

$P M, D B A, S T\}$ 的模式 $Q$ ，能找到八个匹配，分别为 $G_{s ⁃ 1}$ 到 $G_{s ⁃ 8}$ （图2c）.每个匹配的顶点与模式 $Q$ 的点相互对应.例如 $G_{s ⁃ 1}$ 中的点集 $\{v_{2}, v_{5}, v_{9}, v_{12}\}$ 分别对应 $Q$ 的点集 $\{B A, P M, D B A, S T\}$ .

定义4

前向扩展和后向扩展给定模式 $Q$ ，可以通过从其节点 $u$ 对 $Q$ 进行深度优先搜索来构建其DFS树 $T_{q}$ ，称 $T_{q}$ 中的边为前向边，称 $Q$ 中的其余边为后向边.因此，前向扩展通过引入一条从 $Q$ 中的现有顶点到新引入的顶点的新边来扩大 $Q$ ，扩展出来的模式形如树状结构，被称为树模式.后向扩展从 $Q$ 的两个现有顶点引入新边，扩展出来的模式，其结构中包含回边，不再是树状结构，被称为非树模式.

例3

如图2b所示， $θ = 15$ 时存在三个模式 $Q_{1}, Q_{2}$ 和 $Q_{7}$ . $Q_{2}$ 可以通过前向扩展从具有边集 $\{(D B A, P R G)\}$ 的模式 $Q_{1}$ 生成，该过程增加了一个顶点ST和一条边 $(P R G, S T)$ ； $Q_{2}$ 还可以通过后向扩展，在不增加节点的情况下，增加一条新边 $(D A B, S T)$ ，生成新的模式 $Q_{7}$ .

定义5

模式大小给定模式 $Q = (V_{p}, E_{p}, f_{v})$ ，其模式大小定义为 $|Q| = |E_{p}|$ ，其中， $|E_{p}|$ 为模式的边数.

不少工作中，模式的大小被定义为点集与边集大小的和，而本文对此进行调整，主要因为模式无论通过前向还是后向扩展，其边数都会增加1，而点数在后向扩展时保持不变，故采用边集的数量来描述模式大小的增长会更平滑.因此，本文将模式大小 $|Q|$ 定义为 $|Q| = |E_{p}|$ .

2.2　频繁模式挖掘

定义6

支持度给定模式 $Q$ 和图 $G$ ，支持度表示模式 $Q$ 在图 $G$ 中对应匹配出现的频率，记为 $S u p (Q, G)$ .

基于图像的最小支持度^［27］是一个广泛使用的度量标准，它保证了模式扩展的反单调性.本文用其来计算模式的支持度，其定义如下所示：

S u p (Q, G) = m i n \{|P (u)|, u \in V_{p}\}

(1)

其中， $P (u)$ 表示模式中顶点 $u$ 在图 $G$ 上的匹配去重后的节点集合.

例4

如图2b所示，模式 $Q$ 在图 $G$ 上的匹配去重之后得到的结果为：

P (B A) = \{v_{2}, v_{3}\}

P (P M) = \{v_{5}, v_{6}, v_{7}\}

P (S T) = \{v_{12}, v_{13}, v_{14}\}

P (D B A) = \{v_{9}, v_{10}\}

所以， $S u p (Q, G_{a}) = 2$ .

定义7

反单调性给定图 $G$ 的任意两个模式 $Q, Q^{'}$ ，如果 $Q^{'}$ 是 $Q$ 的子模式，则一定存在 $S u p (Q, G) \geq S u p (Q^{'}, G)$ ，即子模式频繁，父模式也一定频繁，称模式具有反单调性.

定义8

域给定图 $G$ 和具有节点集 $V_{p}$ 的模式 $Q$ ， $Q$ 的域 $(D o m a i n)$ 用 $D (Q, G)$ 表示.模式 $Q$ 的域将 $Q$ 在 $G$ 中的所有匹配 $M (Q, G)$ 重新组织为一个表，表的列头和列体分别对应模式节点 $u_{i} (u_{i} \in V_{p})$ 和它的映射 $P (u_{i})$ .

例5

如图2c所示，模式 $Q$ 在图 $G_{a}$ 中的所有匹配 $M (Q, G_{a})$ 包括 $G_{s ⁃ 1}$ 到 $G_{s ⁃ 8}$ ，共计八个匹配，而 $Q$ 的域 $D (Q, G_{a})$ （图2b）是一个比 $M (Q, G_{a})$ 更紧凑的数据结构.

定义9

频繁模式挖掘给定图 $G$ 和支持度阈值 $θ$ ，频繁模式挖掘旨在从图 $G$ 中发现一个频繁模式集合 $𝕊$ ， $𝕊$ 中的任意模式 $Q$ 的支持度满足 $S u p (Q, G) \geq θ$ .

表1给出了本文中重要的符号及其含义.

表1 本文使用的符号

Table 1 Summary of notation

符号	含义
$G = (V, E, L)$	一个原始数据图
$Q = (V_{p}, E_{p}, f_{v})$	一个模式
$G_{s} \subseteq G$	$G_{s}$ 是 $G$ 的子图
$Q \subseteq Q^{'}$	$Q^{'}$ 是 $Q$ 的子模式
$M (Q, G)$	$Q$ 在 $G$ 中的匹配集
$\|Q\|$	模式 $Q$ 的大小
$S u p (Q, G)$	$Q$ 在 $G$ 中的支持度
$D (Q, G)$	$Q$ 在 $G$ 中的域
$I t r (Q)$	模式 $Q$ 的兴趣度

3 Top⁃Rank⁃K模式挖掘算法

3.1　问题描述

下面给出Top⁃Rank⁃K模式挖掘问题的形式化描述.

输入：单个大图 $G$ 和一个整数 $k$ .

输出：一个从 $G$ 中发现的频繁模式集合 $𝕊_{k}$ ，该集合中的任意模式 $Q$ 的rank，即 $R (Q)$ 满足 $R (Q) \leq k$ .

这里， $R (Q)$ 是模式 $Q$ 的兴趣度排名，具体定义如下所示：

R (Q) = |\{i t r \in I & i t r \geq I t r (Q)\}|

(2)

其中， $I$ 是一个由所有模式的不同兴趣度组成的集合.模式 $Q$ 的 $R (Q)$ 被定义为兴趣度大于等于 $I t r (Q)$ 的不同兴趣度的数量.特别地，当两个模式的兴趣度相同时，它们的rank相同.模式 $Q$ 的兴趣度的定义如下所示：

I t r (Q) = \frac{1}{1 + α^{- (|Q|)}} \times S u p (Q, G)

(3)

其中， $S u p (Q, G)$ 为模式 $Q$ 的支持度， $\frac{1}{1 + α^{- (|Q|)}}$ 是一个由系数 $α (α > 1)$ 和模式大小 $|Q|$ 共同决定的衰减系数.

直观上，Top⁃Rank⁃K模式挖掘任务旨在从图 $G$ 中找到所有rank不大于 $k$ 的模式.

在设计模式兴趣度时，从应用出发，考虑两个因素：（1）模式的支持度越大，兴趣度越高；（2）模式的规模越大，兴趣度越高.然而，随着模式规模的增长，支持度必然会单调递减.对此，基于削减小模式支持度收益的思想，本文设计了如式（3）所示的兴趣度度量函数，在考虑模式大小的同时，尽可能降低不具备反单调性的影响，使基于传统支持度剪枝的效果可以有效地保留.

本文中参数 $α$ 的值预设为2.0.计算可得 $α = 2.0$ ，模式大小为1时（单边模式）， $I t r (Q) \approx S u p (Q, G) \times 0.67$ ；模式大小趋近无穷大时， $I t r (Q) \approx S u p (Q, G)$ .因此，本文选择 $α = 2.0$ ，在平衡模式大小和支持度两方面具有一定优势，可以弱化小模式支持度过大以及大模式支持度偏低带来的影响，这个选择既符合实际需求，又易于计算.后文的实验部分将更深入地讨论参数 $α$ 对算法性能的影响.

例6

图1b中的两个模式 $Q_{7}$ 和 $Q_{100}$ 在图 $G$ 中（图1a）的支持度分别为15和5.通过式（3）计算可得 $I t r (Q_{7}) = 13.35, I t r (Q_{100}) = 4.95$ .由于 $I t r (Q_{7}) > I t r (Q_{100})$ ，因此，对于用户， $Q_{7}$ 被认为是更有价值和更有趣的模式.

命题1

Top⁃Rank⁃K模式挖掘是NP⁃hard问题.

证明

子图同构（Subgraph Isomorphism，SISO）可以检测图 $G$ 中是否存在子图与 $G_{s}$ 同构.该问题被嵌入Top⁃Rank⁃K模式挖掘问题，则Top⁃Rank⁃K模式挖掘问题至少与SISO问题具有相同的难度，由于SISO是一个NP⁃hard问题^［28］，因此Top⁃Rank⁃K模式挖掘问题也是NP⁃hard问题.

由于算法无须输入支持度阈值，故其无法直接用支持度阈值进行搜索空间的剪枝.另一方面，直接对整个搜索空间进行穷举显然不可取.为了纠正这一点，算法采用兴趣度优先的树模式识别方法并结合严格的模式扩展约束来降低不必要的搜索开销，具体将在下文中详细介绍.

3.2　整体框架

如算法1中的伪代码所示，ItrMiner以图 $G$ 和整数 $k$ 为输入，返回一组rank不大于 $k$ 的模式作为输出.挖掘过程中ItrMiner执行三项主要任务：初始化（第1~4行）、兴趣度引导的树模式识别（第5~15行）和非树模式挖掘（第16和17行）.所有模式都被组织在一个动态维护的有向树 $T$ （称为编码树）中， $T$ 的增长遵循自上而下的方式，从“种子”模式开始（单边模式）.

算法1 ItrMiner

输入：图 $G$ ，整数 $k$ ；

输出：兴趣度排名在前 $k$ 的模式集合 $𝕊_{k}$ .

1.initialize $𝕊_{c} : = \emptyset$ ， $𝕊_{k} : = \emptyset$ ， $L : = \emptyset$ ；

2.initialize $T$ as an empty tree；

3.initialize $s E d g e s$ ， $m i n I t r = 1$ ；

4.update T， $𝕊_{c}$ ， $𝕊_{k}$ with $s E d g e s$ ；

5.while $𝕊_{c} \neq \emptyset$ do

6. $Q : = 𝕊_{c} . p o p ()$ ；

7. if $S u p (Q, G) < m i n I t r$ then

8. break；

9. $L : = F w T r e e G e n (Q, s E d g e s, G)$ ；

10. for each pattern $Q_{e}$ in $L$ do

11. if $Q_{e}$ is not expanded & $I t r (Q_{e}) \geq m i n I t r$ then

12. insert $Q_{e}$ into $𝕊_{k}$ and $𝕊_{c}$ ；

13. update $T$ with $𝕊_{c}$ ；

14. If $|𝕊_{k}| \geq k$ then

15. update $m i n I t r$ ；

16. $S_{k} : = B a c k S e a r c h (T, 𝕊_{k}, G, m i n I t r)$ ；

17.Return $𝕊_{k}$ .

3.3　初始化

算法1一共初始化了 $𝕊_{c}, 𝕊_{k}, L, T$ ，

$s E d g e s 和 m i n I t r$ 六个参数.首先，在第1行，初始化两个空的优先队列 $𝕊_{c} 和 𝕊_{k}$ 以及用来存储中间过程生成的候选模式的空集合L；在第2行，创建一个空的编码树T；在第3行，初始化图 $G$ 中的所有单边 $s E d g e s$ ，并将最小兴趣度 $m i n I t r$ 设定为1. $𝕊_{c}$ 存储待扩展的候选模式并以支持度作为比较条件，模式支持度越高，排名越靠前. $𝕊_{k}$ 存放迭代的Top⁃Rank⁃K模式，算法结束时最终返回的结果为 $𝕊_{k}$ 中的模式，并以模式的兴趣度为比较条件，兴趣度越低，排名越靠前.值得注意的是， $𝕊_{k}$ 的大小由不同兴趣度的个数决定且最大值为 $k$ ，当 $𝕊_{k}$ 超过 $k$ 时，移除队首元素（最小值）.然后，在第4行，ItrMiner进行单边初始化，计算每个单边模式（即“种子”模式）的支持度和兴趣度，按它们各自的大小依次加入 $𝕊_{c}$ 和 $𝕊_{k}$ ，并添加对应种子模式的节点到编码树 $T$ .注意，在这个过程中，若 $𝕊_{k}$ 的大小达到 $k$ ，则用 $𝕊_{k}$ 中最小的兴趣度更新 $m i n I t r$ .

例7图1a所示的社交网络上图 $G$ 上，ItrMiner

首先识别出八个“种子”模式 $Q_{1} ~ Q_{8}$ （如图3所示），它们的兴趣度如表2所示.根据它们各自的兴趣度将其分别插入 $𝕊_{c}$ 和 $𝕊_{k} (k = 4)$ .由于 $k = 4$ ， $Q_{5}$ 和 $Q_{8}$ 的rank排名分别为5和6，因此不插入 $𝕊_{k}$ .模式 $Q_{2}, Q_{3}$ 和 $Q_{7}$ 的兴趣度最低，为6.70，放置于 $𝕊_{k}$ 的队首；模式 $Q_{6}$ 的兴趣度最高，为13.40，放置于 $𝕊_{k}$ 的队尾. $𝕊_{c}$ 中 $Q_{6}$ 的支持度最高，为20，放置于队首； $Q_{2}$ 的支持度最低，为10，放置于队尾.值得注意的是， $Q_{5}$ 和 $Q_{8}$ 的支持度小于 $𝕊_{k}$ 当前的最小兴趣度6.70，因此不插入 $𝕊_{c}$ ，因为后续无论怎么扩展，它们的模式的兴趣度都不会大于6.70.

图3

图3 编码树生成和队列更新

Fig.3 Coding tree generation and queue update

表2 种子模式的支持度，兴趣度和rank排名

Table 2 Support，interestingness and ranking of seed patterns

模式	支持度	兴趣度	rank排名
$Q_{6}$	20	13.40	1
$Q_{1}$	16	10.72	2
$Q_{4}$	15	10.05	3
$Q_{3}$	10	6.70	4
$Q_{7}$	10	6.70	4
$Q_{2}$	10	6.70	4
$Q_{5}$	5	3.35	5
$Q_{8}$	1	0.67	6

3.4　兴趣度优先的树模式识别

在这一阶段，ItrMiner以兴趣度为优先级，通过函数FwTreeGen扩展当前支持度最高的模式，以尽快提升最小兴趣度minItr并剪掉低兴趣度的模式.具体地，当 $𝕊_{c} \neq \emptyset$ 时，算法1第6行不断地从 $𝕊_{c}$ 中弹出顶部元素（当前支持度最大的模式） $Q$ ，并执行以下操作：（1）算法1第7行和第8行，验证 $Q$ 的支持度，如果 $S u p (Q, G) < m i n I t r$ ，则结束while循环，因为后续的模式无论怎么扩展，其兴趣度都小于minItr；（2）算法1第9行调用函数FwTreeGen对模式 $Q$ 进行前向扩展，生成一组候选模式 $L$ ，在这个过程中，每个新模式的域会基于模式 $Q$ 的域进行更新；（3）对于 $L$ 中的每个候选模式 $Q_{e}$ ，算法1第10~13行检查 $Q_{e}$ 是否出现过，如果它是一个新模式并满足 $I t r (Q) \geq m i n I t r$ ，则将 $Q_{e}$ 添加到 $𝕊_{k}$ 和 $𝕊_{c}$ ，并通过 $𝕊_{c}$ 来更新 $T$ .此外，算法1第14~15行对 $𝕊_{k}$ 的大小进行验证，如果 $𝕊_{k} \geq k$ ，则更新minItr.

例8

如图3所示，将八个种子模式 $Q_{1} ~ Q_{8}$ 存储进编码树，然后ItrMiner以兴趣度优先的树模式识别方式逐一调用函数FwTreeGen前向扩展编码树 $T$ 上的模式来不断地生成候选模式.例如，模式 $Q_{6}$ 的支持度最高，先从 $𝕊_{c}$ 出队，由于扩展约束的限制， $Q_{6}$ 不能扩展（详见4.6）.接着， $Q_{1}$ 出队，通过前向扩展得到模式 $Q_{11}$ ，然后计算 $Q_{11}$ 的支持度和兴趣度，将其分别插入 $𝕊_{k} (k = 4)$ 和 $𝕊_{c}$ .由图可见，经过步骤①， $𝕊_{k} (k = 4)$ 的兴趣度集合由 $(13.40,10.72,10.05,6.70)$ 更新为 $(13.40,$

$12.80, 10.72,10.05)$ ，删除了6.70，增添了 $Q_{11}$ 的兴趣度12.80.对于 $𝕊_{c}$ ， $Q_{6} 和 Q_{1}$ 出队，新模式 $Q_{11}$ 加入队列并按照其支持度大小放置在相应的位置.值得注意的是， $Q_{2}, Q_{3}$ 和 $Q_{7}$ 的支持度（10）小于当前 $𝕊_{k} (k = 4)$ 的最小兴趣度10.05，因此更新 $𝕊_{c}$ ，将它们删除.

3.5　非树模式挖掘

非树模式挖掘，即后向扩展，是在当前模式的基础上继续增添新的边.算法2展示了后向扩展的具体细节.

算法2 BackSearch

输入： $T$ ， $𝕊_{k}$ ， $G$ ， $m i n I t r$ ；

输出： $𝕊_{k}$ .

1.initialize $L : = \emptyset$ ；

2.initialize $h = 1$ ；

3.while $(h \leq t h e h e i g h t o f T)$ do

4. for each pattern $Q_{h i}$ at level $h$ of $T$ do

5. if $S u p (Q_{h i}, G) < m i n I t r$ then

6. break；

7. $L : = B w T r e e G e n (Q_{h i}, G)$ ；

8. for each pattern $Q_{e}$ in $L$ do

9. if $Q_{e}$ is not expanded & $I t r (Q_{e}) \geq m i n I t r$ then

10. insert $Q_{e}$ into $S_{k}$ ；

11. if $|𝕊_{k}| \geq k$ then

12. update minItr；

13. h++；

14.return $𝕊_{k}$ .

编码树 $T$ 构建完成后，ItrMiner调用函数BackSearch来挖掘非树模式.具体地，BackSearch首先初始化一个整型参数 $h = 1$ ，然后迭代地生成非树模式，模式生成过程遵循自顶向下的方式，从位于 $T$ 顶层的编码树开始.每一轮迭代中，算法2第4~7行，BackSearch在 $T$ 的 $h$ 层优先选择支持度最大的模式 $Q_{h i}$ ，并利用BwTreeGen生成一组候选模式 $L$ .这个过程中会优先比较 $S u p (Q_{h i}, G)$ 与minItr的大小，如果 $S u p (Q_{h i}, G) <$

$m i n I t r$ ，则终止当层循环.值得注意的是，BwTreeGen的工作原理类似FwTreeGen，但仅通过后向扩展方式来扩展 $Q_{h i}$ .算法2第9~12行对 $L$ 中的每个候选模式 $Q_{e}$ 进行验证，如果是未被扩展出的模式并且其兴趣度大于等于minItr，则将 $Q_{e}$ 加入 $𝕊_{k}$ 并更新minItr.

例9

当树模式识别完成之后，BackSearch调用函数BwTreeGen后向扩展编码树 $T$ 上的模式来不断地生成候选模式，从而实现非树模式的挖掘.具体地，由于编码树的顶层节点都是单边模式，不能进行后向扩展，故BackSearch直接从第二层开始遍历.如图3所示， $Q_{11}, Q_{41}$ 和 $Q_{42}$ 都是第二层模式， $Q_{11}$ 的支持度最高，因此首先扩展 $Q_{11}$ ，通过函数BwTreeGen扩展得出环形模式 $Q_{11 ⁃ 1}$ ，BackSearch计算其支持度和兴趣度，将其分别插入 $𝕊_{k} (k = 4)$ 和 $𝕊_{c}$ ，再继续扩展 $Q_{41}$ 和 $Q_{42}$ .由于其扩展结果与 $Q_{11 ⁃ 1}$ 相同，因此当前 $𝕊_{k}$ 存放的即为最终结果，BackSearch将其返回.

3.6　模式扩展约束规则

为了解决传统的使用频繁单边进行扩展的方法在Top⁃Rank⁃K模式挖掘中产生大量低兴趣度模式的问题，提出模式扩展约束规则，要求每个模式都有一个扩展约束支持度 $Q . c s t$ ，并在单边 $e$ 对模式进行扩展时需要满足 $Q . c s t \leq s u p (Q_{e}, G)$ ，即单边对应的模式支持度大于等于被扩展模式的约束支持度.值得注意的是，“种子”模式的扩展约束支持度为其支持度本身，而子模式继承了父模式的扩展约束支持度.

命题2

有约束的模式扩展不会错过任何一个模式的生成.

证明

给定图 $G$ 的所有单边模式 $e_{1}, e_{2}, \dots, e_{n}$ ，其中， $s u p (e_{1}, G) \geq s u p (e_{2}, G) \geq \dots \geq s u p (e_{n}, G)$ .给定任意模式 $Q = (V, E (e_{i}, e_{j}, \dots, e_{k}), f), i < j < k$ .由于模式扩展的约束，模式 $Q$ 无法由单边模式 $e_{i}, e_{j}$ 扩展而得，但其总能被扩展约束的最小的 $e_{k}$ 扩展出来.因此，有约束的模式扩展不会错过任何一个模式的生成.

例10

如图3所示， $𝕊_{c}$ 队首元素 $Q_{6}$ 出队，通过模式扩展约束规则可知 $Q_{6} . c s t = 20$ .由于没有其余单边模式的支持度大于等于20，因此 $Q_{6}$ 无法进行扩展.紧接着 $Q_{1}$ 出队，因为 $Q_{1} . c s t < s u p (Q_{6}, G)$ ，所以 $Q_{1}$ 通过 $Q_{6}$ 扩展生成模式 $Q_{11}$ .图4所示为无约束的模式扩展编码树.与有约束的模式扩展相比，在结果相同的情况下，无约束的模式扩展产生了25个冗余模式.最后经过检验，这些模式均被证实为不频繁（其模式兴趣度小于当前 $𝕊_{k}$ 的最小兴趣度）.

图4

图4 未带约束的模式扩展编码树

Fig.4 Pattern expansion coding tree without constraints

上述例子表明，在结果相同的情况下，采用带有约束的模式扩展策略，搜索空间会更小，算法的执行效率更高.下文将详细探讨这种优化对算法性能的影响.

4 实验

为了全面评估ItrMiner算法的性能进行了实验研究，并与基线算法进行比较.实验涵盖了真实图数据和合成图数据，考察算法的运行时间、内存消耗和可扩展性.每个实验重复五次，并对结果进行平均处理.

测试环境为一台配备2.5 GHz 48核CPU和192 GB RAM的服务器，操作系统为CentOS Linux release 7.8，实验代码均用java编写.

4.1　实验数据

使用如表3所示的六个真实数据集.

表 3 实验使用的数据集

Table 3 Datasets used in experiments

数据集	点集大小	边集大小	平均度数
Amazon	410236	3356824	16.36
MiCo	100000	1080298	21.61
YouTube	154817	1055572	13.63
Twitter	81306	1768149	43.49
CiteSeer	3312	4591	2.77
PDB	20226	83356	8.24

（1） Amazon^［29］是产品联合采购网络，包含0.41×10⁶个点和3.35×10⁶条边.当两个商品a和b被客户同时购买的频次达到一定数量时，就会形成边 $(a, b)$ .

（2） MiCo^［16］是由微软合作作者信息构建的网络，包含0.1×10⁶个点和1.08×10⁶条边.每个节点代表作者，每条边代表两位作者之间的合作关系.

（3） YouTube^［30］是由来自YouTube平台的视频及其相关视频构建的网络，包含0.15×10⁶个点和1.05×10⁶条边.每个节点代表一个用户或频道，每条边代表两个节点之间的关系.

（4） Twitter^［31］是来自Twitter平台的社交网络，包含八万多个点和1.76×10⁶条边.每个节点代表一个Twitter用户，每条边代表两个用户的关注.由于原始图数据没有标签，因此随机地对节点添加标签，标签分布服从高斯分布.

（5） CiteSeer^［16］是计算科学领域的引文网络，包含三千个点和四千条边.每个节点代表一篇学术论文，每条边代表两篇论文之间的引用关系.

（6） PDB^［32］是来自PDB的一个蛋白质结构网络，包含两万多个点和八万多条边.每个节点代表一个原子，每条边表示分子之间的化学键.

4.2　实验设置

使用4.1的六种真实图数据集和通过图生成器生成的10种不同大小规模的人工合成图数据集.

使用Java实现ItrMiner和以下算法.

（1） TKG.通过实现TKG算法^［25］并对其加入支持单个大图中的支持度和兴趣度的计算，使其能在单个大图中挖掘Top⁃Rank⁃K频繁模式.

（2） Grami.是一种改良版的Grami算法^［16］，在Grami的基础上引入本文提出的兴趣度计算来挖掘Top⁃Rank⁃K频繁模式.具体地，首先挖掘得到所有的频繁模式，随后计算其兴趣度，经排序后返回前 $k$ 名的所有模式.值得一提的是：①由于Grami依赖支持度阈值进行剪枝，因此，算法利用启发式方法来估算支持度阈值；②Grami在挖掘过程中仅对候选模式进行支持度的判别，即是否达到支持度阈值，没有精确计算对模式的支持度，故本文采用模式支持度下界，即将支持度阈值作为模式的支持度来进行兴趣度值的计算.

（3） ItrMiner_nopt.是ItrMiner无模式扩展约束的版本，与ItrMiner相比，ItrMiner_nopt除了在模式扩展中没有实现扩展约束以外，其余基本一致.

4.3　实验结果

4.3.1　实验一： $k$ 对算法的影响

首先，固定系数 $α = 2.0$ ，在六个真实数据集上，以50为增量， $k$ 从100增加到300.图5展示了六个真实数据集上所有算法的执行时间.

图5

图5 在六个数据集上k对各算法执行时间的的影响

Fig.5 The execution time of each algorithm with different k on six datasets

（1）随着 $k$ 的增加，所有算法的执行时间均变长，因为需要验证的候选模式以及匹配增加了.需要注意的是，CiteSeer的执行时间基本不变，这是因为预设的 $k$ 已经大于需要验证的所有候选模式的兴趣度的数量.

（2）与TKG和ItrMiner_nopt相比，ItrMiner的效率更高，在六个真实数据集上，ItrMiner平均花费的时间分别为TKG的51.9%，39.2%，43.9%，18.7%，76.5%和94.4%.同时，ItrMiner的模式扩展约束对提升执行效率有显著作用，在六个真实数据集上，加入模式扩展约束后，ItrMiner平均花费的时间是ItrMiner_nopt的45.4%，32.3%，40.4%，14.1%，74.7%和78.0%.此外，ItrMiner在稠密的数据集上的表现尤为出色.以Twitter数据集为例，当 $k = 250$ 时，ItrMiner和ItrMiner_nopt相比，最高效率可提升9.5倍.同时，和TKG相比，ItrMiner仅需花费其13.2%的时间.

图6展示了各算法在六个真实数据集上的内存消耗.由图可见，随着 $k$ 的增大，ItrMiner，ItrMiner_nopt和TKG的内存消耗也相应增加，这是因为k越大，算法的搜索空间也越大.进一步观察发现，初始 $k = 100$ 时，ItrMiner，ItrMiner_nopt和TKG的内存消耗都略高，这是因为它们没有设置初始支持度阈值，算法开始的搜索空间较大.然而，在实际应用中，内存是一个重要的限制因素，这方面ItrMiner表现最佳，它在大多数数据集上的内存消耗最小.相比之下，ItrMiner_nopt和TKG的内存消耗略高，但总体上它们的内存成本仍然是可以接受的，并且没有一个算法在内存方面显著劣于其他算法.

图6

图6 在六个数据集上k对各算法内存消耗的的影响

Fig.5 The memory consumption of each algorithm with different k on six datasets

4.3.2　实验二：ItrMiner与Grami的比较

比较ItrMiner与Grami的性能，以评估使用ItrMiner进行前 $k$ 频繁模式挖掘是否达到或超过传统设定支持度阈值的频繁模式挖掘算法的性能.

需要注意，与ItrMiner在挖掘过程中动态维护兴趣度排名在前 $k$ 的模式方式不同，Grami的运行流程主要分三部分：（1）输入支持度阈值；（2）挖掘满足支持度阈值的模式；（3）从模式中选取兴趣度排名在前 $k$ 的所有模式.为了保证结果的一致性，将不同 $k$ 的ItrMiner运行得到的模式集合中的最小支持度作为Grami的支持度阈值输入.

固定系数 $α = 2.0$ ，在六个真实数据集上，以50为增量，k从100增加到300.表4和表5分别展示了Grami和ItrMiner在六个真实数据集上的实验结果，表中黑体字表示结果最优.

表4 Grami和ItrMiner算法在六个数据集上的执行时间 (s)

Table 4 Execution time (unit：s) of Grami and ItrMiner on six datasets

算法	Amazon		MiCo		YouTube		Twitter		CiteSeer		PDB
算法	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$
Grami	55.41	217.08	15.69	59.37	27.93	123.1	13.23	79.78	0.92	0.94	3.78	58.61
ItrMiner	36.02	74.19	17.38	59.95	12.67	32.12	15.64	173.4	0.47	0.42	3.28	41.79

表5 Grami和ItrMiner算法在六个数据集上的内存消耗 (GB)

Table 5 Memory consumption (unit：GB) of Grami and ItrMiner on six datasets

算法	Amazon		MiCo		YouTube		Twitter		CiteSeer		PDB
算法	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$
Grami	3.81	6.80	1.96	3.46	1.67	3.83	1.81	2.78	0.21	0.21	0.74	1.58
ItrMiner	3.30	4.97	1.73	3.02	1.48	3.16	2.03	3.26	0.18	0.18	1.13	1.98

由表4可知，在六个真实数据集上，ItrMiner的执行时间比Grami更短，尤其在YouTube数据集上， $k = 300$ 时Grami的执行时间接近ItrMiner的四倍.进一步观察，随着k的增大，ItrMiner的优势更明显.例如，在Amazon数据集上， $k = 100$ 时Grami的执行时间约为ItrMiner的1.5倍，而 $k = 300$ 时，这个比例扩大到3倍，因为较大的 $k$ 会导致发现更多的模式，降低模式集合中的最小支持度，这会增大Grami的搜索空间.而ItrMiner采用基于兴趣度优先的树模式识别方法，并受到模式扩展约束规则的限制，避免了大量冗余模式的生成，提升了运行效率.然而，在MiCo和Twitter数据集上，发现ItrMiner的执行时间比Grami更长.分析发现，ItrMiner以动态的方式将潜在的高兴趣度模式扩展出来，在扩展过程中ItrMiner始终维护前k名的模式，并利用它们产生大量的候选模式，这一过程在特定的数据集上可能会消耗过长的时间.相反，Grami在开始时就已指定最小支持度阈值，避免生成冗余的低支持度模式.综上，Top⁃Rank⁃K频繁模式挖掘可以在无须设定支持度阈值的情况下更加高效地进行运算.

由表5可知，除了PDB和Twitter数据集外，ItrMiner在其余数据集上的内存消耗比Grami更低.这是因为ItrMiner采用模式扩展约束策略，可以避免生成大量的冗余模式和实例检验，有效地减小了算法的搜索空间.但在PDB和Twitter数据集上，ItrMiner消耗的内存高于Grami，因为ItrMiner需要同时维护两个队列 $𝕊_{k}$ 和 $𝕊_{c}$ ， $𝕊_{k}$ 用于动态存储当前兴趣度排名在前 $k$ 的模式， $𝕊_{c}$ 用于存储需要通过动态搜索扩展的模式.

实际应用中，用户通常难以确定适当的支持度阈值（参考例1）.为此，本文在不同数据集上，对支持度阈值进行调整，并计算k不同时的挖掘任务耗时.表6展示了运行结果，表中黑体字表示性能最优.由表可见，ItrMiner在所有数据集上的执行时间均比Grami更短，并且，随着 $k$ 的增加，两者之间的差距越大，表明支持度阈值的设定直接影响算法的执行效率.因此，在实际应用中，进行Top⁃Rank⁃K挖掘更加便捷.

表6 Grami和ItrMiner算法在六个数据集上的执行时间 (s)

Table 6 Execution time (unit：s) of Grami and ItrMiner on six datasets

算法	Amazon		MiCo		YouTube		Twitter		CiteSeer		PDB
	阈值降低50		阈值降低50		阈值降低50		阈值降低150		阈值不变		阈值降低20
	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$	$k = 100$	$k = 300$
Grami	61.90	244.8	23.72	101.1	31.93	160.6	20.23	266.7	0.92	0.94	5.78	110.6
ItrMiner	36.02	74.19	17.38	59.95	12.67	32.12	15.64	173.4	0.47	0.42	3.28	41.79

在不同数据集上比较这两种算法的性能表现，验证了ItrMiner的可行性和实用性，为实际应用中的用户提供更多选择和灵活性，更高效地进行模式挖掘分析.因此，可以将ItrMiner视为传统频繁模式挖掘的一种有价值的替代方案.

4.3.3　实验三：算法的可扩展性

首先，固定系数 $α = 2.0, k = 600$ ，将图 $G = (V, E, L)$ 的规模从 $(0.1 M, 1 M)$ 增长至 $(1 M, 10 M)$ ，其中顶点的增量为0.1 M，边的增量为1 M，比较ItrMiner，ItrMiner_nopt和TKG的性能，实验结果如图7所示.由图可见：（1）如前预期，随着图规模的增大，所有算法的执行时间和内存消耗也增加，但由于具体图结构的不同，可能会出现局部下降；（2）与ItrMiner_nopt和TKG相比，ItrMiner在不同规模的数据集上表现出更短的执行时间和更低的内存消耗.此外，ItrMiner的执行时间对图规模的敏感度更低，即当图的规模从 $(0.1 M, 1 M)$ 增长至 $(1 M, 10 M)$ ，ItrMiner，ItrMiner_nopt和TKG的执行时间分别增加了478，885和705 s.因此，ItrMiner表现了更好的可扩展性.

图7

图7 算法的可扩展性

Fig.6 Scalability of the algorithms

4.3.4　实验四： $α$ 对算法的影响

首先，固定 $k = 200$ ，在六个真实数据集上， $α$ 以0.2的步长从1.6增长至2.6，测试其对ItrMiner的影响，实验结果如图8所示.

图8

图8 六个数据集上 $α$ 对ItrMiner算法的影响

Fig.8 Impact of $α$ of ItrMiner on six datasets

由图可见：（1）随着 $α$ 的增大，ItrMiner的执行时间和内存消耗呈下降趋势，因为 $α$ 越大，兴趣度在支持度上的收益越大，算法会偏向于挖掘支持度更高的模式，从而更快地提高全局的支持度，加快搜索速度；（2）虽然不明显，但是 $α$ 的增大会使Top⁃Rank⁃K模式的最大模式呈下降趋势.原因同前，基于模式反单调性的特性，子模式的支持度必定不大于父模式，越小的模式支持度一般越高.为了获取更高质量的模式，需要在模式大小和支持度之间寻找平衡，选择合适的 $α$ .

5 结论

针对频繁模式挖掘支持度阈值难以设定的问题，本文研究了Top⁃Rank⁃K的频繁模式挖掘问题.首先设计了一项同时考虑模式大小和模式支持度的兴趣度指标，并基于该指标提出一种无须设置初始支持度阈值，直接挖掘排名前 $k$ 的Top⁃Rank⁃K频繁模式挖掘算法ItrMiner.针对没有初始支持度阈值作为输入、算法剪枝困难的问题，ItrMiner采用兴趣度优先的树模式识别来快速提升支持度阈值.同时，本文还提出一种新颖的模式扩展约束策略来有效地减少不必要模式的生成，缩短算法的执行时间，降低算法的内存消耗.使用真实图和人工合成图数据集来验证ItrMiner的性能，结果表明，与无扩展约束ItrMiner_nopt和基线算法TKG相比，ItrMiner的执行时间更短，内存消耗更低，在稠密数据集上的优势更显著.另外，通过与带有支持度阈值的Grami算法的比较，验证了ItrMiner的可行性和实用性.在人工合成数据集上的实验也证明ItrMiner具有更好的扩展性.综上，本文提出的ItrMiner算法，耗时更短，内存消耗更低，还能高效地挖掘兴趣度排名在前 $k$ 的频繁模式.

未来将致力于解决更大规模图数据的频繁模式挖掘问题，并尝试通过并行计算的方法进一步提高ItrMiner算法的执行效率.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Daud

N N

， Ab Hamid

S H

， Saadoon

，et al.

Applications of link prediction in social networks：A review

Journal of Network and Computer Applications，2020，166：102716.

[2]

Sabe

V T

， Ntombela

， Jhamba

L A

，et al.

Current trends in computer aided drug design and a highlight of drugs discovered via computational techniques：A review

European Journal of Medicinal Chemistry，2021，224：113705.

[3]

Xue

， Klabjan

， Luo

Predicting ICU readmission using grouped physiological and medication trends

Artificial Intelligence in Medicine，2019，95：27-37.

[4]

Yang

， Hou

B N

， Cai

Z P

，et al.

6Graph：A graph⁃theoretic approach to address pattern mining for Internet⁃wide IPv6 scanning

Computer Networks，2022，203：108666.

[5]

Huan

， Wang

， Prins

，et al.

SPIN：Mining maximal frequent subgraphs from graph databases

∥Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle，WA，USA：ACM，2004：581-586.

[6]

Deng

Z H

Fast mining Top⁃Rank⁃K frequent patterns by using node⁃lists

Expert Systems with Applications，2014，41(4)：1763-1768.

[7]

Huynh⁃Thi⁃Le

， Le

， Vo

，et al.

An efficient and effective algorithm for mining Top⁃Rank⁃K frequent patterns

Expert Systems with Applications，2015，42(1)：156-164.

[8]

Chen

， Liu

， Chen

Z Y

，et al.

PBSM：An efficient top⁃k subgraph matching algorithm

International Journal of Pattern Recognition and Artificial Intelligence，2018，32(6)：1850020.

[9]

Natarajan

， Ranu

A scalable and generic framework to mine top⁃k representative subgraph patterns

∥2016 IEEE 16th International Conference on Data Mining. Barcelona，Spain：IEEE，2016：370-379.

[10]

Wang

， Tang

， Liu

，et al.

Diversified pattern mining on large graphs

∥The 32^nd International Conference on Database and Expert Systems Applications. Springer Berlin Heidelberg，2021：171-184.

[11]

Deng

Z H

， Fang

G D

Mining Top⁃Rank⁃K frequent patterns

∥2007 International Conference on Machine Learning and Cybernetics. Hong Kong，China：IEEE，2007：851-856.

[12]

Abdelaal

A A

， Abed

， Al⁃Shayeji

，et al.

Customized frequent patterns mining algorithms for enhanced Top⁃Rank⁃K frequent pattern mining

Expert Systems with Applications，2021，169：114530.

[13]

Goyal

， Jain

S K

An efficient algorithm for mining Top⁃Rank⁃K frequent patterns from uncertain databases

∥2016 2nd International Conference on Applied and Theoretical Computing and Communication Technology. Bangalore，India：IEEE，2016：324-328.

[14]

Nguyen

， Le

， Vo

，et al.

A new approach for mining Top⁃Rank⁃K erasable itemsets

∥The 6^th Asian Conference on Intelligent Information and Database Systems. Springer Berlin Heidelberg，2014：73-82.

[15]

Kuramochi

， Karypis

Finding frequent patterns in a large sparse graph

Data Mining and Knowledge Discovery，2005，11(3)：243-271.

[16]

Elseidy

， Abdelhamid

， Skiadopoulos

，et al.

GraMi：Frequent subgraph and pattern mining in a single large graph

Proceedings of the VLDB Endowment，2014，7(7)：517-528.

[本文引用: 5]

[17]

Teixeira

C H C

， Fonseca

A J

， Serafini

，et al.

Arabesque：A system for distributed graph mining

∥Proceedings of the 25^th Symposium on Operating Systems Principles. Monterey，CA，USA：ACM，2015：425-440.

[18]

Dias

， Teixeira

C H C

， Guedes

，et al.

Fractal：A general⁃purpose graph pattern mining system

∥Proceedings of 2019 International Conference on Management of Data. Amsterdam，Netherlands：ACM，2019：1357-1374.

[19]

Abdelhamid

， Abdelaziz

， Kalnis

，et al.

Scalemine：Scalable parallel frequent subgraph mining in a single large graph

∥Proceedings of the International Conference for High Performance Computing，Networking，Storage and Analysis. Salt Lake City，UT，USA：IEEE，2016：716-727.

[20]

Chen

H Z

， Liu

， Zhao

Y J

，et al.

G⁃miner：An efficient task⁃oriented graph mining system

∥Proceedings of the 13th EuroSys Conference. Porto，Portugal：ACM，2018：32.

[21]

李玲，印莹，赵宇海，等.

基于解耦概要图的大规模图数据高效分布式挖掘算法

计算机学报，2020，43(7)：1183-1198.

， Yin

， Zhao

Y H

，et al.

An efficient distributed algorithm for large⁃scale graph data mining based on decoupled summary subgraph

Chinese Journal of Computers，2020，43(7)：1183-1198.

[22]

Wang

， Lan

， He

Y A

，et al.

A cost⁃effective approach for mining near⁃optimal top⁃k patterns

Expert Systems with Applications，2022，202：117262.

[23]

Y H

， Lin

， Li

R X

，et al.

TGP：Mining top⁃k frequent closed graph pattern without minimum support

∥The 6^th International Conference on Advanced Data Mining and Applications. Springer Berlin Heidelberg，2010：537-548.

[24]

Saha

T K

， Al Hasan

FS³：A sampling based method for top‐k frequent subgraph mining

Statistical Analysis and Data Mining：The ASA Data Science Journal，2015，8(4)：245-261.

[25]

Fournier⁃Viger

， Cheng

， Lin

J C W

，et al.

Tkg：Efficient mining of top⁃k frequent subgraphs

∥The 7^th International Conference on Big Data Analytics. Springer Berlin Heidelberg，2019：209-226.

[26]

Zeng

， Leong

H U

， Yan

，et al.

Fast core⁃based top⁃k frequent pattern discovery in knowledge graphs

∥2021 IEEE 37th International Conference on Data Engineering. Chania，Greece：IEEE，2021：936-947.

[27]

Bringmann

， Nijssen

What is frequent in a single graph?

∥The 12^th Pacific⁃Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg，2008：858-863.

[28]

Cordella

L P

， Foggia

， Sansone

，et al.

A (sub) graph isomorphism algorithm for matching large graphs

IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(10)：1367-1372.

[29]

Leskovec

， Adamic

L A

， Huberman

B A

The dynamics of viral marketing

ACM Transactions on the Web，2007，1(1)：5.

[30]

Cheng

， Dale

， Liu

J C

Statistics and social network of YouTube videos

∥2008 16^th Interntional Workshop on Quality of Service. Enschede，Netherlands：IEEE，2008：229-238.

[31]

Mcauley

， Leskovec

Learning to discover social circles in ego networks

∥Proceedings of the 25th International Conference on Neural Information Processing Systems. Lake Tahoe，NV，USA：Curran Associates Inc.，2012：539-547.

[32]

Talukder

， Zaki

M J

A distributed approach for graph mining in massive networks

Data Mining and Knowledge Discovery，2016，30(5)：1024-1052.