面向大规模图数据的参数化模式挖掘技术及应用

Parameterized pattern mining techniques and applications for large⁃scale graph data

摘要

大规模图上的频繁模式挖掘（Frequent Pattern Mining，FPM）因其在社交分析等各类应用中的广泛应用，受到高度关注.受模式语义的约束，传统的FPM技术难以满足多样化的数据分析需求，基于此，提出有参模式（Parameterized Patterns，p⁃模式）及其挖掘技术.通过在模式中引入参数来拓展匹配语义，实现图中复杂关系的有效捕获；设计并实现了高效的挖掘算法（PMiner），用于从大图中发现频繁p⁃模式；提出基于p⁃模式的图关联规则（Graph Association Rule，GAR），并设计GAR挖掘算法GARGen，以发现图中节点间的潜在关联.在真实图数据上的实验不仅验证了上述算法的运行效率，还揭示了p⁃模式与传统模式的差异以及定义在p⁃模式上的GAR在链接预测等任务上的有效性.

Abstract

Frequent Pattern Mining (FPM) on large⁃scale graphs has garnered significant attention due to its broad applications in areas such as social network analysis. However，constrained by traditional pattern semantics，conventional FPM techniques struggle to meet the diverse demands of data analysis. To address this challenge，this paper introduces Parameterized Patterns (p⁃patterns) and their mining framework. By incorporating parameters into patterns，the matching semantics are extended，enabling the effective capture of complex relationships within graphs. An efficient mining algorithm，PMiner，is designed and implemented to discover frequent p⁃patterns from large graphs. Furthermore，this paper proposes Graph Association Rules (GAR) based on p⁃patterns and designs the GARGen algorithm to uncover latent associations between nodes. Experiments on real⁃world graph datasets not only validate the computational efficiency of the proposed algorithms but also highlight the distinctions between p⁃patterns and traditional patterns，as well as the effectiveness of GAR in tasks such as link prediction.

Graphical abstract

关键词

有参模式 / 频繁模式挖掘 / 关联规则挖掘 / 图关联规则

Key words

parameterized pattern / frequent pattern mining / association rules mining / graph association rules

频繁模式挖掘（Frequent Pattern Mining，FPM）在图数据分析等领域发挥着至关重要的作用.一般地，FPM的目标是识别数据集中出现频率超过给定阈值的子图模式.根据应用背景，FPM的研究可分为两个主要分支：基于图数据库的频繁模式挖掘和基于单个大图的频繁模式挖掘.近年来，基于单个大图的频繁模式挖掘因其在社交网络分析^［1］和关联规则挖掘^［2］等领域的深度应用而获得了更多的关注.

传统FPM算法聚焦于发现具有确定标签的子图模式，然而，这些方法往往忽略了模式中的潜在变量或参数化需求.在现实场景中，一是图数据往往蕴含不确定信息，如节点的语义模糊、属性缺失等；二是缺乏参数的模式，其结构匹配语义严格有余，灵活不足，难以捕获图中潜在的复杂频繁结构.因此，有必要在模式中引入变量节点，通过参数化机制拓展匹配语义，进而更有效地捕捉图中深层次的节点间关联.图1展示了有参模式的有效性.

例1

图1a展示了社交网络Google+的部分视图，其中每个节点代表一个用户，具有唯一的标识符和特定的职位（例如数据库管理员（DBA）、程序员（PRG）、业务分析师（BA）、软件测试员（ST）和项目经理（PM）），连接节点的边表示用户之间的友谊关系.图1b展示了传统频繁模式挖掘算法在图G上发现的一些频繁模式，支持度阈值设为3.图1c展示了PMiner在图G上挖掘的一些频繁p⁃模式（支持度阈值同样设为3），其中参数代表职位未知的用户，参数之间的关系通过布尔表达式进行约束（U_x.Attribute=U_y.Attribute）.这些p⁃模式可以反映社交网络中实体之间的规律^［2］.例如，如图1d所示，如果用户U_x和用户U_y是朋友，U_x和U_y都在微软工作，U_y之前的专业是计算机科学，那么U_x的专业也可能是计算机科学.

显然，与传统模式相比，有参模式（简称p⁃模式）的语义更丰富，能表达更复杂的拓扑关系，捕获具有特定意义的频繁结构.研究表明，p⁃模式在众多领域具有重要的应用价值，尤其是在知识补全和社交推荐中.p⁃模式的引入为大图分析，如关系推断提供了新的方法.然而，从大规模图数据中挖掘p⁃模式并非易事，需要算法层面的创新.本文的主要贡献如下.

（1）对传统模式进行语义扩展，提出了有参模式，用以捕捉节点间的复杂关系.

（2）设计了面向单一大图的p⁃模式挖掘算法PMiner.

（3）依托p⁃模式，拓展图关联规则语义，设计规则生成算法GARGen，实现图中节点关系的预测.

（4）在真实图数据上的实验结果表明PMiner在时间和空间开销方面表现出色.p⁃模式蕴含的特殊语义，使PMiner的挖掘结果排除了大量结构简单、使用价值低的单边模式.此外，GARGen能够捕获特殊语义的图关联规则，这类规则可以有效预测图中的缺失关系，平均准确率为63.27%，显著优于现有的链接预测方法.

1 相关工作

1.1 频繁模式及其变体的挖掘

近年来，单一大图上的FPM引起了广泛关注，催生出众多先进的挖掘算法.值得注意的是，Elseidy et al^［3］将FPM重新定义为约束满足问题，设计了GraMi算法，特别地，该算法利用具有反单调性的最小图像作为支持度度量来评估模式的频率.由于GraMi专为单一大图上的挖掘任务设计，因而面临计算资源消耗大的问题.为了提高挖掘效率，ScaleMine^［4］采用了两阶段挖掘方法，首先通过近似处理快速识别频繁模式，随后通过并行挖掘对剩余模式进行挖掘，高效地解决FPM问题.为了进一步提升FPM的挖掘效率，引入并行处理技术，如GraphINC^［5］，TopKWY^［6］和Peregrine^［7］等算法通过与分布式系统结合显著提高了挖掘效率.然而，分布式系统自身也带来了复杂和高成本的问题.为此，Yuan et al^［8］的T⁃FSM算法通过加载任务驱动的执行引擎以及多种优化技术的结合，不仅实现了较低的运行时间和内存消耗，也实现了高效的负载平衡.汤小春等^［9］提出基于数据流的FPM算法，通过“微批”模式和优化的正规编码计算提高了并行性，且能够处理大规模图数据，然而，大量的子图实例的存储给内存管理带来了挑战.针对此问题，Cheng et al^［10］的可扩展频繁模式挖掘算法通过引入数据间的关联性及内存管理优化策略，有效解决了大数据探索中的可扩展性问题，使算法能在内存有限的情况下高效运行.为了适应不同的应用场景对算法进行扩展，挖掘目标也从通用模式转变成特定模式.例如郭方方等^［11］针对动态污点分析中存在的效率低下的问题，设计了SPIN⁃MGM算法来挖掘最大频繁子图，将生成树与最大频繁子图挖掘结合，显著提升了识别效率.随着图数据规模的不断增长，传统的挖掘算法已经难以满足需求.为了应对多重图上的挖掘挑战，Ingalalli et al^［12］提出了MuGram算法，不仅能在多重图上发现频繁多重图模式，也能满足普通图上的挖掘需求.针对加权图上的挖掘问题，Islam et al^［13］的WFSM⁃MaxPWS框架引入了MaxPWS剪枝技术，实现了在动、静态权重图中加权频繁子图的高效挖掘.Min et al^［14］提出一个新的频繁模式发现算法，将字母表分为强、中、弱三个组件来识别一种新型的模式，即tri⁃模式.Wu et al^［15］提出基于序列模式的高平均效用不重叠序列模式（HANP），实验证明，和现有的频繁序列模式相比，HANP具有更高的挖掘价值.这些特定模式大大增强了频繁模式挖掘的语义丰富性，能够更好地捕捉数据中的潜在关系.截至目前，尚未发现可直接用于挖掘p⁃模式的算法，但前述的频繁模式挖掘算法为研究p⁃模式挖掘问题提供了宝贵的启示和思路.

1.2 关联规则挖掘及应用

关联规则挖掘旨在识别数据集中项集间的关联关系，定义了面向交易数据的关联规则，其中，最具代表性的关联规则挖掘算法是Apriori算法^［10］.随着图数据的广泛使用，面向图数据的关联分析受到越来越多的关注.在早期的社交网络关联分析中^［16］，主要是基于社交图中提取的属性元组来挖掘传统规则和霍恩规则，没有充分考虑规则的结构特性.Fan et al^［2］将关联规则从项集拓展到图模式，引入了特殊类型的图关联规则（Graph Pattern Association Rule，GPAR）用于开展社交媒体营销等，而GPAR中的后继被定义为包含单边的特殊模式图.在此基础上，Wang et al^［16］进一步提出代表性的GPAR，形式化了GPAR挖掘问题并将其分为两个子问题，即频繁模式挖掘和规则生成，高效地解决了关联规则挖掘中的挑战.此外，Liu et al^［17］拓展了传统GPAR的语义，提出GROs （Graph Rule with Oracles），通过引入内部计算与外部知识集成机制以及基于枢轴双模拟的匹配方式，解决了传统图规则在表达能力与计算效率上的瓶颈.受益于GPAR挖掘问题的有效突破，大图上的链接预测问题也得到了有效解决.链接预测旨在推断网络结构中节点间存在关联的可能性，在社交推荐等场景中至关重要，传统方法大多通过节点特征相似性度量来实现^［18］.近年来提出了一系列链接预测技术，其中，Benhidour et al^［19］提出面向有向网络的链接预测法，包括相似度⁃流行度算法、路径探索算法以及混合算法，填补了有向网络上链接预测问题的研究空白.然而，这类算法依然面临计算复杂度高的挑战.此外，焦鹏飞等^［18］提出一种基于多视图对比学习的动态网络链接预测方法，实现了动态网络的表示学习和链接预测.

本文通过引入p⁃模式扩展了传统模式的语义，并进一步将p⁃模式融入图关联规则（Graph Association Rule，GAR），丰富了GAR的表达能力，强化了其在链接预测上的作用.

2 基本定义

定义1 图 ^［3］ 图可以定义为G=\left(V,E,L\right),

其中，（1）V是节点的集合；（2）E\subseteq V\times V是边的集合；（3）每个节点v\in V对应一个元组L\left(v\right)=\left(A_{\mathrm{1}}=a_{\mathrm{1}},A_{\mathrm{2}}=a_{\mathrm{2}},\cdots ,A_n=a_n\right),其中，A_i=a_i

\left(i\in \left[\mathrm{1},n\right]\right)表示节点v在属性A_i上的值，记作v.A_i=a_i.

给定图G\mathrm{\text{'}}=\left(V\mathrm{\text{'}},E\mathrm{\text{'}},L\mathrm{\text{'}}\right),如果V\mathrm{\text{'}}\subseteq V，E\mathrm{\text{'}}\subseteq E，并且对于任何节点v\in V\mathrm{\text{'}}，有L\mathrm{\text{'}}\left(v\right)=L\left(v\right)，则称G\mathrm{\text{'}}是G的子图.

定义2 模式^［20］ 模式可以定义为Q=\left(V_p,E_p,f_v\right)，其中，V_p和E_p分别是节点和边的集合，而f_v是定义在V_p上的函数.对于任何节点u\in V_p，它的标签f_v\left(u\right)是原子公式的合取，每个公式的形式为\mathrm{“}A=a\mathrm{”}，其中，A表示节点u的属性，a是A的值.通常，f_v\left(u\right)指节点u的查询条件.

定义3 图模式匹配^［21］ 对于图G=\left(V,E,L\right)和模式Q=\left(V_p,E_p,f_v\right),如果图G中的节点v满足模式Q中节点u的搜索条件，即对于f_v\left(u\right)中的每个原子公式\mathrm{“}A=a\mathrm{”}，在L\left(v\right)中存在一个属性A，使得v.A=a，那么称v匹配u，记作v\sim u.模式Q在图G中的匹配是由一个双射函数h:V_s\Rightarrow V_p形成的子图G_s=\left(V_s,E_s,L_s\right),满足以下条件：

（1）\forall v\in V_s，v\sim h\left(v\right)；

（2）\forall \left(v_i,v_j\right)\in E_s，\left(h\left(v_i\right),h\left(v_j\right)\right)\in E_p.

定义4 支持度^［3］ 模式Q在图G中的支持度，记作Sup\left(Q,G\right),表示Q在G中出现的频率.基于图像的最小支持度MNI是一种广泛使用的支持度指标，具有反单调特性，如下所示：

Sup\left(Q,G\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\left.\left|img\left(u\right)\right|\right|u\in V_p\right\}(1)

其中，img\left(u\right)表示模式Q中节点u在图G上的匹配去重后的节点集合.本文使用MNI作为支持度指标.

定义5 有参模式（简称“p⁃模式”）p⁃模式可以定义为Q\left[X\right]=\left(V_p,E_p,f_v,f_x\right),其中，

（1）V_p，E_p和f_v分别表示节点集、边集以及节点标签映射函数（同定义2）；

（2）X=\left\{U_x,U_y,\cdots \right\}为一个包含不同变量的集合，其基数被限制为\left|X\right|\in \left\{\mathrm{1,2}\right\},且允许通配符“_”作为特殊变量出现；

（3）f_x是从V_p到X的双射函数，它为V_p中的节点指定一个唯一的变量.

对于节点u\in V_p，

（1）若f_x\left(u\right)\notin X，则节点u的查询条件由f_v\left(u\right)指定；

（2）若f_x\left(u\right)\in X且\left|X\right|=\mathrm{1}，则节点u的查询条件由f_x\left(u\right)指定，且f_v\left(u\right)=\mathrm{“}\_\mathrm{”}；

（3）当f_x\left(u\right)\in X时，存在u的邻接节点u\text{'}使得u.A=u^{\text{'}}.A，其中，邻接节点u^{\text{'}}既可能是变量节点也可能是常规节点，A是u，u^{\text{'}}的共同属性.

例2

对于模式Q_{\mathrm{11}}（见图1c），其节点集V_p=

\left\{v_{\mathrm{1}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{5}},v_{\mathrm{6}},v_{\mathrm{8}},\dots \right\},边集E_p=\left\{\left(v_{\mathrm{1}},v_{\mathrm{3}}\right),\right.

\left.\left(v_{\mathrm{3}},v_{\mathrm{4}}\right),\left(v_{\mathrm{5}},v_{\mathrm{6}}\right),\dots \right\}.变量集合X=\left\{U_x,U_y\right\},满足\left|X\right|\in \left\{\mathrm{1,2}\right\}且U_x.university=U_y.university.标签映射函数f_v将V_p中的节点映射到模式中常规节点，如f_v\left(v_{\mathrm{4}}\right)=PM；变量映射函数f_x将V_p中的节点映射到模式中变量节点，如f_x\left(v_{\mathrm{1}}\right)=U_x，f_x\left(v_{\mathrm{3}}\right)=U_y.

与定义3类似，p⁃模式在图G中的匹配是由一个双射函数h\text{'}:V_s\Rightarrow V_p形成的子图G_s=\left(V_s,E_s,L_s\right),满足以下条件：

（1）\forall v\in V_s，若f_x\left(h\text{'}\left(v\right)\right)\in X，则存在一个节点v\text{'}\left(\left(v,v\text{'}\right)\in E_s\right)使得h^{\text{'}}\left(v\right).A=h\text{'}\left(v\text{'}\right).A;

（2）\forall v\in V_s，若f_x\left(h\text{'}\left(v\right)\right)\notin X,v\sim h\text{'}\left(v\right);

（3）\forall \left(v_i,v_j\right)\in E_s，\left(h\text{'}\left(v_i\right),h\text{'}\left(v_j\right)\right)\in E_p;

（4）\forall v\in V_s，若f_v\left(h\text{'}\left(v\right)\right)=\mathrm{“}\_\mathrm{”}则f_v\left(h^{\text{'}}\left(v\right)\right)=L\left(v\right)，即通配符可以匹配任意标签，p⁃模式的支持度定义与定义4一致.

变量的引入丰富了p⁃模式的语义表达能力，使其能够捕获传统模式（参见定义2，又称“无参模式”）难以捕获的特殊结构，同时也带来因结果集过于庞大而导致的可用性低的新问题.

从实际应用出发，本文对p⁃模式进行了约束，即：

（1）p⁃模式Q\left[X\right]仅包含不超过两个变量节点；

（2）p⁃模式中变量节点u与其邻居节点u\text{'}通过布尔表达式u.A=u^{\text{'}}.A形成Q\left[X\right]的变量约束，该约束在Q\left[X\right]后续的扩展过程中将始终存在，即使变量节点被实例化.

例3

如图1a所示，对于图G的子图G_{\mathrm{1}}=\left\{\left(v_{\mathrm{1}},v_{\mathrm{3}}\right),\left(v_{\mathrm{3}},v_{\mathrm{4}}\right)\right\}，不难发现v_{\mathrm{1}}.university=v_{\mathrm{3}}.university，v_{\mathrm{1}}映射到U_x，v_{\mathrm{3}}映射到U_y，v_{\mathrm{4}}映射到\mathrm{P}\mathrm{M}，因此G_{\mathrm{1}}构成Q_{\mathrm{11}}在G中的一个有效匹配.此外，模式Q_{\mathrm{11}}在G中的支持度Sup\left(Q_{\mathrm{11}},G\right)=\mathrm{4}，因为，

Img\left(U_x\right)=\left\{v_{\mathrm{1}},v_{\mathrm{5}},v_{\mathrm{10}},v_{\mathrm{11}}\right\}

Img\left(U_y\right)=\left\{v_{\mathrm{3}},v_{\mathrm{6}},v_{\mathrm{7}},v_{\mathrm{13}},v_{\mathrm{14}}\right\}

Img\left(PM\right)=\left\{v_{\mathrm{4}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{15}}\right\}

故，

定义6 模式域^［20］ 给定一个图G和一个节点集合为V_p的模式Q，Q的定义域记为D\left(Q,G\right).将Q在G中的所有匹配M\left(Q,G\right)组织为一个表格，该表格的列标题和主体分别对应模式节点u_i（其中u_i是V_p的元素）及其对应的映射Img\left(u_i\right).D\left(Q,G\right)的第j个域被表示为D_j\left(Q,G\right)，对应表格的第j列.

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

定义8 图关联规则 图关联规则（Graph Association Rule，GAR）定义为R=Q_l\to Q_r，其中，Q_l和Q_r分别是R的先导和后继，且满足以下条件：（1）Q_l和Q_r都包含至少一条边；（2）Q_l和Q_r都是连通的；（3）Q_l和Q_r之间没有共享的边.

规则R表明，在图G中，如果存在一个同构映射h_l，可以将模式Q_l映射到子图G_{\mathrm{1}}，那么很可能存在另一个同构映射h_r，可以将模式Q_r映射到子图G_{\mathrm{2}}.注意，Q_l和Q_r中所有公共节点u（u属于V_l和V_r的交集，其中，V_l和V_r分别为Q_l和Q_r的节点集）必须映射到图G中的同一个节点v.最后，将Q_l与Q_r的边集合扩展形成一个新模式Q_R.

通过规则R，可以开展好友推荐等任务.例如在图1a中，节点v_{\mathrm{3}}被推荐给v_{\mathrm{2}}，节点v_{\mathrm{9}}被推荐给v_{\mathrm{5}}.除了社交推荐，图关联规则还能广泛应用于链路预测^［22］、事件检测^［23］和主题检索^［23］等各种场景.

传统关联规则挖掘通过支持度实现搜索空间的剪枝.沿用定义4对模式支持度的定义，图关联规则R的支持度定义为：

Sup\left(R,G\right)=Sup\left(Q_R,G\right)(2)

即将R视为模式Q_R并计算Q_R的支持度.

为了确定在Q_l成立的情况下Q_r成立的可能性，本文采用传统的置信度指标并定义图关联规则R在图G中的置信度（conf）为模式Q_R在G中的支持度与模式Q_l在G中的支持度之比，如下所示：

conf\left(R,G\right)=\frac{Sup\left(Q_R,G\right)}{Sup\left(Q_l,G\right)}(3)

例4

如图2所示，图关联规则R可以表示为Q_l\to Q_r，其中，Q_l和Q_r分别是先导和后继.使用Q_r的边集扩展Q_l，R可以表示为模式图Q_R.

进一步，Q_l在图G中有四个匹配，因为\mathrm{m}\mathrm{i}\mathrm{n}\left(Img\left(u\right)\right)=\mathrm{3}，其支持度为Sup\left(Q_l,G\right)=\mathrm{3}.模式图Q_R在图G中仅有一个匹配，其支持度为Sup\left(Q_R,G\right)=\mathrm{1}.

因此，R的置信度为conf\left(R,G\right)=\frac{\mathrm{1}}{\mathrm{3}}.

3 p⁃模式挖掘算法

PMiner接受图G和支持度阈值\theta作为输入，返回频繁p⁃模式集合S_t.详细流程如算法1所示.

算法1 PMiner

输入：图G，阈值θ

输出：频繁p⁃模式集合S_t

Step 1.initialize S_{\mathrm{t}}=\mathrm{\varnothing },T as an empty tree，S^{[\mathrm{1}]}

Step 2.initialize fsip， remove Q\left[X\right] from fsip if ；update S_{\mathrm{t}}； update T

Step 3.T=FwExtension\left(G,T,S^{[\mathrm{1}]},\theta \right)

Step 4.T=BwExtension\left(G,T,S^{[\mathrm{1}]},\theta \right)

Step 5.update S_t with T

Step 6.return S_t

Step 7.function FwExtension\left(G,T,S^{[\mathrm{1}]},\theta \right)

Step 8. initialize flag=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e},l_{\mathrm{f}}=\mathrm{\varnothing }

Step 9. while flag\ne \mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e} do

Step 10.l_{\mathrm{f}}=PatTreeGen\left(G,T,S^{[\mathrm{1}]}\right)

Step 11. for each unseen pattern Q_{\mathrm{c}} in l_{\mathrm{f}} do

Step 12. if Sup\left(Q_c,G\right)\ge \theta then

Step 13. update T with Q_{\mathrm{c}}

Step 14. end for

Step 15. if T is not updated then

Step 16.flag=\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}

Step 17. end while

Step 18.return T

Step 19. function BwExtension\left(G,T,S^{[\mathrm{1}]},\theta \right)

Step 20. initialize h as the height of T；

Step 21. for each pattern Q at level h do

Step 22.l_{\mathrm{b}}=BackExt\left(G,Q,S^{[\mathrm{1}]}\right);

Step 23. for each unseen pattern Q_{\mathrm{c}} in l_{\mathrm{b}} do

Step 24. if Sup\left(Q_c,G\right)\ge \theta then

Step 25. update T with Q_{\mathrm{c}}

Step 26. end for

Step 27. update h

Step 28. end for

Step 29.return T

PMiner首先初始化三个参数：一个集合S_t用于记录频繁p⁃模式，一棵模式树T用于将频繁p⁃模式根据生成关系进行组织，一个集合S^{[\mathrm{1}]}用于存储所有支持度不低于阈值\theta的单边无参模式（第1行），该集合将作为后续辅助模式扩展的核心结构.随后，PMiner在图G中挖掘所有的单边p⁃模式，即仅包含一条边的p⁃模式，如图1c中的Q_{\mathrm{1}},Q_{\mathrm{2}}，并将其存储在fsip中.接着，PMiner移除所有支持度低于阈值\theta的p⁃模式.最终，这些频繁的单边p⁃模式被更新到T和S_t中，为后续扩展奠定基础（第2行）.初始化完成后，PMiner通过FwExtension进行p⁃模式的前向扩展（第7~18行）以及通过BwExtension进行p⁃模式的后向扩展（第19~29行）.最后，PMiner通过模式树T更新集合S_t，并返回更新后的S_t作为最终结果.

3.1　 FwExtension函数

该函数接受图G、p⁃模式树T、单边无参模式集合S^{\left[\mathrm{1}\right]}以及支持度阈值\theta作为输入，返回经前向扩展形成的树结构的p⁃模式集合，这些p⁃模式以层次化的形式被组织在树T上.

首先，它初始化一个布尔变量flag，用于控制while循环的执行；它还创建集合l_f用于记录每一层扩展中生成的候选p⁃模式（第8行）.接下来，FwExtension反复生成候选模式并验证它们的支持度.在每次迭代中，FwExtension调用PatTreeGen （见算法2）生成一组候选模式（第10行）.实际上，对于不同类型的待扩展模式，PatTreeGen采用与之相对应的扩展策略，以确保扩展过程的完整性，具体的扩展策略参见算法2.对于l_f中的每个未生成过的候选模式Q_c，FwExtension会验证其支持度.如果Q_c的支持度超过阈值\theta，则将Q_c更新到模式树T中（第11~14行）.若处理完所有候选模式后，模式树T未被更新，FwExtension将把循环控制变量flag设置为\mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}，以终止循环，返回模式树T（第15~18行）.

3.2　 PatTreeGen函数

PatTreeGen函数利用单边无参模式集合S^{\left[\mathrm{1}\right]}对模式树T进行逐层扩展并返回一个候选模式集合，伪代码如算法2所示.

算法2PatTreeGen

输入：图G，模式树T，单边模式集合S^{[\mathrm{1}]}

输出：候选模式集合L

Step 1.initialize L=\mathrm{\varnothing },L_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}=\mathrm{\varnothing },L_{\mathrm{c}}=\mathrm{\varnothing }

Step 2.L_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}=T.getLeaf\left(\right)

Step 3.for each pattern Q in L_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}} do

Step 4.L_{\mathrm{c}}=PatGen\left(Q,S^{[\mathrm{1}]}\right)

Step 5. if Q.VertexNum=\mathrm{2} then

Step 6.L_{\mathrm{c}}=L_{\mathrm{c}}\bigcup PatInst\left(Q,S^{[\mathrm{1}]}\right)

Step 7. if Q.ParameterNum=\mathrm{1} then

Step 8.L_{\mathrm{c}}=L_{\mathrm{c}}\bigcup ParGen\left(Q,S^{[\mathrm{1}]}\right)

Step 9. for each candidate patternQ_{{\mathrm{L}}_{\mathrm{c}}} in L_{\mathrm{c}} do

Step 10.

D\left(Q_{L_c},G\right)=UpdateDomain\left(Q_{L_c},S^{[\mathrm{1}]},G\right)

Step 11. end for

Step 12. update L with L_{\mathrm{c}}

Step 13.end for

Step 14.return L

Step 15. function UpdateDomain\left(Q_{L_c},S^{[\mathrm{1}]},G\right)

Step 16.Q_{\mathrm{p}}=getParent\left(Q_{L_c},T\right)

Step 17. initialize D\left(Q_{L_c},G\right) with D\left(Q_p,G\right)

Step 18. for each D_{\mathrm{j}}\left(Q_{L_c},G\right) in D\left(Q_{L_c},G\right) do

Step 19. for each invalid node v in D_{\mathrm{j}}\left(Q_{L_c},G\right) do

Step 20. identify a match G_{\mathrm{s}} including v

Step 21. if G_{\mathrm{s}} is not found then

Step 22. remove v from D_{\mathrm{j}}\left(Q_{L_c},G\right)

Step 23. end for

Step 24. end for

Step 25.return D\left(Q_{L_c},G\right)

算法2首先初始化三个集合：集合L用于存储所有候选模式，集合L_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}用于记录叶子模式（即树T中叶子层的模式），集合L_c用于维护L_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}中的每个模式经前向扩展所生成的候选模式（第1行）.接下来，PatTreeGen调用getLeaf函数（未展示）来获取模式树T的所有叶节点（第2行）.基于这些叶节点，算法执行前向扩展（首轮扩展中叶节点对应着最简单的频繁单边p⁃模式）.

PatTreeGen针对不同的待扩展模式采用不同的扩展策略：

（1）对于每个模式Q，PatTreeGen调用PatGen执行前向扩展，通过S^{\left[\mathrm{1}\right]}中记录的单边无参模式，引入一条从Q中的现有节点到新引入的节点的新边来扩大Q（第4行）.

（2）如果模式Q为单边p⁃模式（即首次扩展阶段），PatTreeGen调用PatInst对Q进行实例化扩展，在扩展过程中实例化一个参数，从而生成单参p⁃模式，即仅包含一个参数的p⁃模式（第5~6行）.

（3）如果模式Q为单参p⁃模式，PatTreeGen调用ParGen函数进行参数扩展，引入一个新的参数节点并与原模式连接（新引入的参数节点与扩展点之间需满足属性约束），生成包含两个参数的新模式（第7~8行）.之后，PatTreeGen调用UpdateDomain函数更新所有由Q扩展出的候选模式的模式域（第9~11行）.

处理完L_c中的所有候选模式后，PatTreeGen将L_c更新到L中（第12行）.在L_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}中的模式扩展完成后，PatTreeGen将候选模式集合L返回给FwExtension（第14行）.

例5

待扩展模式为模式Q_{\mathrm{1}}:U_x-U_y

\left(U_x.university=U_y.university\right)（见图1c）时，PatTreeGen的扩展流程如下：

（1）调用PatGen对Q_{\mathrm{1}}进行前向扩展，生成一系列p⁃模式（例如U_x-U_y-PM,U_x-U_y-DBA等）并将其放入候选模式集合L_c中.

（2）调用PatInst对Q_{\mathrm{1}}进行实例化扩展，生成一系列单参p⁃模式，例如U_x-PRG-PM（注意节点U_x与实例化节点间仍满足属性约束，即U_x.\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{y}=PRG.\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{y}），之后将其加入到L_c中.

（3）由于Q_{\mathrm{1}}已包含两个参数，算法不再调用ParGen进行参数扩展（若待扩展模式为U_x-PRG-PM时，便可通过参数扩展产生形如U_x-PRG-PM-U_z的新模式，其中，U_z为新引入的参数节点且PM与U_z之间需满足属性约束）.

所有候选模式存入L_c后，再依次执行更新模式域、支持度检测.

3.3　 UpdateDomain函数

首先，UpdateDomain函数调用getParent函数在p⁃模式树T中查找Q_{L_c}的父模式Q_p（第16行）.接着，该函数初始化D\left(Q_{L_c},G\right)（第17行），具体地，首先将D\left(Q_{L_c},G\right)设置为D\left(Q_p,G\right)，然后向D\left(Q_{L_c},G\right)中扩展一个空列，存储上一轮前向扩展中新引入节点v\text{'}的匹配点集，并用S^{\left[\mathrm{1}\right]}中单边模式\left(v,v\text{'}\right)的匹配情况填充该列，列中的节点是可能与新节点匹配的节点.之后，UpdateDomain函数逐列检查D\left(Q_{L_c},G\right)中节点的有效性（第18~24行）.在每次迭代中，函数选择一个尚未标记为有效的节点v，并尝试在G中找到一个匹配G_s，使v属于G_s并与第j列对应的模式节点u_j相匹配（第19~20行）.值得一提的是，G_s的识别是通过引导搜索完成的.在验证节点v的有效性时，算法实际上是在检查v是否能够与其他列中的节点组合成模式Q_{L_c}在G中的完整匹配.在此过程中，算法引入了一些剪枝策略：如果验证发现v可以与来自其他列的节点匹配，则这些节点可以直接在各自的列中标记为有效，从而避免对这些节点的重复验证.如果无法找到匹配G_s，UpdateDomain函数将从D_j\left(Q_{L_c},G\right)中移除v（第21~22行）.最后，当D\left(Q_{L_c},G\right)的所有列都处理完毕后，UpdateDomain将更新后的模式域返回给PatTreeGen （第25行）.

例6

以Q_{\mathrm{11}}（图1c）为例，

D\left(Q_{\mathrm{11}},G\right)=\left[U_x:\left[v_{\mathrm{1}},v_{\mathrm{5}},v_{\mathrm{10}},v_{\mathrm{11}}\right],U_y:\left[v_{\mathrm{3}},v_{\mathrm{6}},v_{\mathrm{7}},v_{\mathrm{13}},v_{\mathrm{14}}\right],PM:\left[v_{\mathrm{4}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{15}}\right]\right]

对于模式Q_{\mathrm{0}}:PM-BA，

D\left(Q_{\mathrm{0}},G\right)=\left[PM:\left[v_{\mathrm{4}},v_{\mathrm{8}},v_{\mathrm{9}},v_{\mathrm{15}}\right],BA:\left[v_{\mathrm{2}},v_{\mathrm{11}},v_{\mathrm{16}}\right]\right]

当通过单边模式Q_{\mathrm{0}}对Q_{\mathrm{11}}执行前向扩展时，可得新模式Q_{\mathrm{111}}:U_x-U_y-PM-BA.在模式域更新过程中，首先将D\left(Q_{\mathrm{111}},G\right)初始化为D\left(Q_{\mathrm{11}},G\right)，并新增一列（初始为空）对应新引入节点BA，随后利用PM-BA模式域中BA节点的匹配\left[v_{\mathrm{2}},v_{\mathrm{11}},v_{\mathrm{16}}\right]填充该新列.接着逐列验证各节点的有效性：以第一列中的节点v_{\mathrm{1}}为例，已知图G中存在子图G_s=\left\{\left(v_{\mathrm{1}},v_{\mathrm{3}}\right),\left(v_{\mathrm{3}},v_{\mathrm{4}}\right),\left(v_{\mathrm{4}},v_{\mathrm{2}}\right)\right\}与模式Q_{\mathrm{111}}匹配，则将v_{\mathrm{1}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{2}}分别在其对应列中标记为有效.后续的检查将跳过已标记为有效的节点，从而避免重复验证.

3.4　 BwExtension函数

经过前向扩展构建模式树T后，PMiner调用BwExtension函数挖掘非树模式.具体地，BwExtension首先初始化一个整数h（初始为p⁃模式树T的高度），用以跟踪当前的扩展层次（第20行）.之后，遍历当前层的所有模式，并使用BackExt函数（未展示）逐一扩展这些模式.每次扩展过程中生成的候选模式存储在l_b中（第22行）.BackExt的工作原理与PatTreeGen类似，不同之处在于BackExt通过引入新的边来扩展模式，不会引入新的节点.随后，所有满足支持度阈值的模式会被更新到p⁃模式树T中（第23~26行）.处理完当前层的所有模式后，h值减1，进入下一次迭代（第27行）.最后，BwExtension返回p⁃模式树T，其中包含了所有频繁p⁃模式.

例7

图3展示了频繁单边p⁃模式Q_{\mathrm{1}}:U_x-U_y的完整扩展过程.首先，PMiner利用FwExtension对Q_{\mathrm{1}} （Level 1）进行前向扩展，生成一系列的候选模式.经过支持度检测后，得到频繁p⁃模式Q_{\mathrm{11}}，Q_{\mathrm{12}}和Q_{\mathrm{13}} （level 2），其中，Q_{\mathrm{13}}是经实例化扩展（PatInst）得到的单参p⁃模式.随后，前向扩展过程继续进行.Q_{\mathrm{11}}进一步扩展为Q_{\mathrm{111}}和Q_{\mathrm{112}} （level 3）以及Q_{\mathrm{1121}} （level 4）.类似地，Q_{\mathrm{12}}被扩展为Q_{\mathrm{121}}和Q_{\mathrm{1211}}，而Q_{\mathrm{13}}被扩展为Q_{\mathrm{131}}和Q_{\mathrm{1311}}.当第四层模式生成的候选模式不再满足阈值要求，无法更新模式树时，前向扩展终止.随后，PMiner利用BwExtension逐层识别非树模式，并将其更新至T.例如模式Q_{\mathrm{11}}，Q_{\mathrm{111}}和Q_{\mathrm{112}}分别生成Q_{\mathrm{11}-\mathrm{1}}，Q_{\mathrm{111}-\mathrm{1}}和Q_{\mathrm{112}-\mathrm{1}}.

4 图关联规则生成算法

规则生成算法GARGen基于频繁模式树框架构建，能够生成高度关联的图模式规则.GARGen接受图G，模式树T，置信度阈值\eta作为输入，返回一个GARs集合S.在树T中，节点v\left(v\in V_T\right)唯一地索引一个频繁p⁃模式，该模式记为Q\left(v\right).算法伪代码如算法3所示.

算法3 GARGen

输入：图G，p⁃模式树T=\left(V_T,E_T\right),置信度阈值η

输出：GARs集合S

Step 1.initialize a set S=\mathrm{\varnothing },a queue q=\mathrm{\varnothing }

Step 2.for each node v in T do

Step 3.q=\mathrm{\varnothing },push v in q

Step 4. While q\ne \mathrm{\varnothing } do

Step 5.v\text{'}=q.pop\left(\right)

Step 6. for each \left(v\text{'}\text{'},v\text{'}\in E_{\mathrm{T}}\right) do

Step 7. push v\text{'}\text{'} in q， generate Q_{\mathrm{r}}

Step 8. if Q_{\mathrm{r}} is connected and \frac{Sup\left(Q\left(v\right),G\right)}{Sup\left(Q\left(v″\right),G\right)}\ge \eta

Step 9.S=S\bigcup \left\{\left(Q\left(v″\right)\to Q_r\right)\right\}

Step 10.return S

GARGen首先初始化一个空集合S和一个空队列q（第1行）.随后，GARGen从树中每一个节点v开始，通过反向广度优先搜索遍历T并生成GAR（第2~9行）.具体地，对于遍历过程遇到的每一个祖先节点v\text{'}\text{'}，通过从模式Q\left(v\right)排除与Q\left(v″\right)对应的边来生成新模式Q_r，若Q_r连通，且\frac{Sup\left(Q\left(v\right),G\right)}{Sup\left(Q\left(v″\right),G\right)}\ge \eta成立，则生成一个新的GAR

\left(Q\left(v″\right)\to Q_r\right)并将其加入集合S.处理完T的所有节点后，返回集合S.

共进行\left|V_T\right|次反向广度优先搜索，每次反向广度优先搜索最多需要O\left(\left|V_T\right|+\left|E_T\right|\right)的时间，则算法的时间复杂度为O\left(\left|V_T\right|\left(\left|V_T\right|+\left|E_T\right|\right)\right).

例8

回顾例7.在频繁p⁃模式树T构建完成后，GARGen遍历模式树中的节点以生成GAR.以\eta =\mathrm{0.5}为例，假设遍历从对应模式Q_{\mathrm{111}\mathrm{⁃}\mathrm{1}}的节点开始，其边集为：

\left\{\left(U_x,U_y\right),\left(U_y,PM\right),\left(PM,BA\right),\left(U_x,PM\right)\right\}

且Sup\left(Q_{\mathrm{111}\mathrm{⁃}\mathrm{1}},G\right)=\mathrm{3}.随后，可以从模式Q_{\mathrm{111}\mathrm{⁃}\mathrm{1}}索引到其父模式Q_{\mathrm{111}}，其边集为：

\left\{\left(U_x,U_y\right),\left(U_y,PM\right),\left(PM,BA\right)\right\}

且Sup\left(Q_{\mathrm{111}\mathrm{⁃}\mathrm{1}},G\right)=\mathrm{3}.然后，生成一个先导为Q_l=\left\{\left(U_x,U_y\right),\left(U_y,PM\right),\left(PM,BA\right)\right\},后继为Q_r=\left(U_x,PM\right)的GAR，并验证该GAR的置信度为1.因此这是一个有效的GAR.

5 实验结果与分析

使用真实图数据开展实验并与基准算法进行比较以评估PMiner的性能，主要包括两个方面：（1） PMiner在模式挖掘效率上的表现；（2） p⁃模式在规则生成中的有效性.实验环境为一台配备2.4 GHz CPU，16 GB RAM的Windows 11主机，所有代码均由Java编写.

5.1　实验设置

5.1.1　实验数据

实验共使用六个真实数据集：（1）谷歌用户共享圈网络图Google+^［24］；（2）Twitter网站社交网络图^［25］；（3）Pokec在线社交网络图^［26］；（4）Facebook社交网络^［27］；（5）YouTube共享网络^［27］；（6）照片分享网络Flickr^［27］.相关统计信息如表1所示.

5.1.2　基线算法

（1）T⁃FSM^［9］：一个面向单一大图的频繁模式挖掘的并行系统，采用基于任务的执行引擎，确保高并发、有限的内存消耗和高效的负载均衡.

（2）ScaleMine^［4］：一个面向单一大图的频繁子图挖掘的并行系统，其工作分两个阶段.第一阶段，快速识别高概率的频繁子图；第二阶段，使用近似结果计算精确解.

（3）GraMi^［3］：一个面向单一大图的频繁子图挖掘框架，通过仅搜索满足阈值的最小实例集，避免了传统方法的高成本.

（4）RuleGen^［21］：一个面向单一大图的图模式关联规则挖掘算法，通过频繁模式并行挖掘（无参模式）显著提升运算效率.

（5）Jaccard^［28］和SimRank^［29］：两种方法都基于节点相似性进行链路预测，但使用了不同的相似性度量.具体地，给定两个节点v_{\mathrm{1}}和v_{\mathrm{2}}，Jaccard通过式（4）来定义节点相似性：

Si{m}_j\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)=\frac{N\left(v_{\mathrm{1}}\right)\bigcap N\left(v_{\mathrm{2}}\right)}{N\left(v_{\mathrm{1}}\right)\bigcup N\left(v_{\mathrm{2}}\right)}（4）

其中，N\left(v\right)表示节点v的邻居集合.SimRank通过式（5）来定义v_{\mathrm{1}}和v_{\mathrm{2}}的相似性：

\begin{array}{l}Si{m}_s\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)=\\ C·\frac{\sum v_{\mathrm{1}}^{\mathrm{\text{'}}}\in N\left(v_{\mathrm{1}}\right)\sum v_{\mathrm{2}}^{\mathrm{\text{'}}}\in N\left(v_{\mathrm{2}}\right)Si{m}_s\left(v_{\mathrm{1}}^{\mathrm{\text{'}}},v_{\mathrm{2}}^{\mathrm{\text{'}}}\right)}{k_{v_{\mathrm{1}}}·k_{v_{\mathrm{2}}}}\end{array}（5）

其中，C\in [\mathrm{0,1}]为衰减因子，k_v为节点v的度数.

5.2　实验结果

在相同条件下评估PMiner与T⁃FSM，ScaleMine和GraMi的时间和空间性能.由于PMiner与传统FPM算法在挖掘目标上存在差异，进一步对比了挖掘结果，并评估了PMiner所挖掘的p⁃模式在链接预测方面的表现.

5.2.1　PMiner的时间与内存开销

测试所有挖掘算法在六个真实数据集上的时间和空间开销，如图4和图5所示.在Google+，Twitter，Pokec，Facebook，YouTube和Flickr数据集上变化支持度阈值\theta，具体为\left\{\mathrm{0.17}\mathrm{K},\mathrm{0.2}\mathrm{K},\mathrm{0.01}\mathrm{K}\right\}\left\{\mathrm{0.56}\mathrm{K},\right.

\left.\mathrm{0.62}\mathrm{K},\mathrm{0.02}\mathrm{K}\right\}\left\{\mathrm{20}\mathrm{K},\mathrm{23}\mathrm{K},\mathrm{1}\mathrm{K}\right\}\left\{\mathrm{0.5}\mathrm{K},\mathrm{0.8}\mathrm{K},\mathrm{0.1}\mathrm{K}\right\}\left\{\mathrm{1.3}\mathrm{K},\left.\mathrm{1.6}\mathrm{K},\mathrm{0.1}\mathrm{K}\right\}\mathrm{和}\left\{\mathrm{1.1}\mathrm{K},\mathrm{1.4}\mathrm{K},\mathrm{0.1}\mathrm{K}\right\},\right.其中，阈值设置由三元组\left\{\mathrm{最小}\mathrm{值},\mathrm{最大}\mathrm{值},\mathrm{增量}\right\}表示.实验结果表明了以下结论.

（1）随着支持度阈值\theta的增大，所有算法的时间和空间开销都会减小，这是因为候选模式的大幅减少显著降低了子图同构检测和支持度计算的开销.

（2）时间性能，PMiner在Twitter，YouTube和Flickr数据集上表现突出，在Pokec和Facebook数据集上表现适中.尽管PMiner因引入参数需要验证的候选模式数量通常超过传统算法，但其时间性能仍然保持在可接受的水平.

（3）空间性能，PMiner在Google+和Facebook数据集上表现较好，但在其他数据集上的表现不如传统算法.同样是因为PMiner需要处理更多的候选模式，此外PMiner还需考虑节点属性，导致空间开销增加.尽管如此，算法的整体性能仍然保持在合理范围内.

5.2.2　PMiner挖掘模式数量

由于PMiner与传统算法在挖掘目标上的差异，本文在评估了时间和空间开销之后，进一步分析在\theta相同时各算法生成的模式结果集，结果如表2所示.在六个数据集上分别将支持度阈值\theta设置为\left(\mathrm{170,200}\right)

\left(\mathrm{560,620}\right)\left(\mathrm{20000,23000}\right)\left(\mathrm{500,800}\right)\left(\mathrm{1300,1600}\right)\left(\mathrm{1100,1400}\right)进行测试，得出以下结果.

（1）T⁃FSM和GraMi挖掘的模式数量相同，因为两者都是精确挖掘算法，而ScaleMine在第一阶段采用近似解法，导致其在部分数据集上挖掘的模式数量低于其他两个算法.

（2）在大多数数据集中，PMiner识别出的p⁃模式数量高于传统算法挖掘出的无参模式数量，但两者的差异不显著.这是因为本文提出的布尔表达式\left(U_x.Attribute=U_y.Attribute\right)对参数的有效约束，有效避免了引入参数后可能出现的模式数量爆炸问题.此外，Pokec数据集的稀疏结构也导致被发现的p⁃模式较少.

（3）在YouTube数据集上，PMiner挖掘出的p⁃模式明显少于传统算法.进一步分析传统算法的挖掘结果，发现其中90%的模式为单边模式，而且在其他数据集的挖掘结果中至少包含50%的单边模式.相比之下，PMiner采用了新颖的扩展策略，其结果中单边模式的比例不到10%.

总体上，PMiner在时间和空间效率上的表现令人满意，并且有效解决了传统算法结果中单边模式冗余的问题.在\theta相同时，PMiner能够挖掘出更多结构多样的模式.

5.2.3　预测准确率

为了研究p⁃模式在链接预测中的性能，采用GARGen算法基于p⁃模式生成图关联规则（GAR）.将GARGen与RuleGen，Jaccard和SimRank算法进行比较，以评估它们的预测准确率.具体设置如下.GARGen与RuleGen的预测准确率通过交叉验证^［29］进行评估：给定图G，将其分为两个片段F_{\mathrm{1}}和F_{\mathrm{2}}，从F_{\mathrm{1}}中挖掘并选择前k\left(k=\mathrm{10,20,30,40,50}\right)个GAR，在F_{\mathrm{2}}上评估预测准确率.准确率的定义为：

Acc\left(R\right)=\frac{Sup\left(Q_R,F_{\mathrm{2}}\right)}{Sup\left(Q_l,F_{\mathrm{2}}\right)}（6）

此过程需要使用度量指标来评估GAR的“质量”以对其进行排序.因此，选取Gain^［30］和Inte⁃rest^［31］两个经典度量指标来衡量GAR的有趣性.

Jaccard和SimRank的评估使用四重交叉验证.具体操作如下.

（1）从Google+，Twitter，Pokec，Facebook，YouTube和Flickr中分别提取\left(\mathrm{5000,32329}\right)

\left(\mathrm{5000,22508}\right)\left(\mathrm{5000,21301}\right)\left(\mathrm{5000,20974}\right)\left(\mathrm{5000},\right.\left.\mathrm{21125}\right)\mathrm{和}\left(\mathrm{5000,21853}\right)的子图G_F（由于SimRank无法在整个图上运行，因此提取子图进行实验）.

（2）对于每个G_F，边集被随机分为四个部分，其中一部分作为测试集，其余三部分用于构建训练图.交叉验证过程重复四次，每个子集仅使用一次作为测试集.

（3）对于每个训练图，运行Jaccard和SimRank算法，基于相似度生成一个节点对的排名列表.选择前L个节点对作为预测边，预测准确率定义为：

Acc=\frac{L_r}{L}（7）

其中，L_r为正确预测的边数.

（4）SimRank的参数C设置为0.8，迭代次数设置为5.Gain参数\theta设置为0.4.

表3展示了GAR的预测准确率，并与RuleGen，Jaccard和SimRank进行比较.由表可以得出以下结论.

（1）使用Gain和Interest度量选择前10个GAR进行链接预测时，GARGen在六个真实图上的平均预测准确率分别为65.7%和68.3%.当设置k=\mathrm{50}时，平均预测准确率降至59.7%和56.6%.随着k的增大，准确率Acc\left(R\right)呈下降趋势.因为在k较小时，所选的GAR通常具有较高的“有趣性”，随着k的增加，更多低“有趣性”模式被包含进来，导致预测准确率的降低.

（2）在选用Gain度量和Interest度量时，GARGen的平均预测准确率分别为64.4%和62.13%，相较于基线算法RuleGen（49.7%和50.27%）平均提升幅度达13.3%.GARGen在链接预测任务上性能明显优于RuleGen，这归因于p⁃模式和无参模式相比，具备更强的表达能力，能够捕捉实体间更加复杂的关系.

（3）在预测准确率方面，GARGen算法明显优于Jaccard和\mathrm{S}\mathrm{i}\mathrm{m}\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}\left(L=\mathrm{200}\right).以Pokec数据集为例，当使用Interest度量并且设置k=\mathrm{50}时，GARGen的预测准确率分别为Jaccard和SimRank的360%和645%.

如图6所示，在Google+数据集中选择一些具有代表性的GAR进行案例分析，从图中可以得出以下结论.

（1）R_{\mathrm{1}}表示如果未知用户U_x与用户U_{\mathrm{1}}是朋友且两者都居住在芝加哥，那么U_{\mathrm{1}}的另一个朋友U_{\mathrm{2}}很可能与U_x是朋友.

（2）R_{\mathrm{2}}表示如果未知用户U_x与用户U_{\mathrm{1}}是朋友且两者都毕业于斯坦福大学，那么U_{\mathrm{1}}的另一个朋友U_{\mathrm{2}}也可能毕业于斯坦福大学.

（3）R_{\mathrm{3}}表示如果未知用户U_x与用户U_{\mathrm{1}}是朋友且两者都毕业于耶鲁大学，且U_{\mathrm{1}}与U_{\mathrm{2}}是朋友，那么U_{\mathrm{2}}也有可能是另一位毕业于耶鲁大学的用户U_y的朋友.

这些规则表明，可以利用GAR进行用户属性预测和朋友推荐.

6 结论

本文提出了有参模式，和传统模式相比，它提供了更加丰富的语义表达能力.还设计了高效的挖掘算法PMiner来发现有参模式.该算法采用基于树的分层扩展策略，确保算法具备提前终止的优良性质.此外，基于p⁃模式扩展图关联规则（GAR），实现了缺失结构的预测.实验结果验证了以上算法性能和有效性的优越性，为大规模图数据分析提供了一种有效工具.

未来将进一步探讨挖掘技术，如设计更加有效的剪枝方法以降低运算开支.此外，模式重要性的度量问题也是一个值得深入研究的方向.

参考文献

[1] Daud N N， Ab Hamid S H， Saadoon M，et al. Applications of link prediction in social networks：A review. Journal of Network and Computer Applications，2020，166：102716.

[2] Fan W F， Wang X， Wu Y H，et al. Association rules with graph patterns. Proceedings of the VLDB Endowment，2015，8(12)：1502-1513.

[3] Elseidy M， Abdelhamid E， Skiadopoulos S，et al. GraMi：Frequent subgraph and pattern mining in a single large graph. Proceedings of the VLDB Endowment，2014，7(7)：517-528.

[4] Abdelhamid E， Abdelaziz I， Kalnis P，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.

[5] Hussein R， Lerner A， Ryser A，et al. GraphINC：Graph pattern mining at network speed. Proceedings of the ACM on Management of Data，2023，1(2)：1-28.

[6] Jyoti， Kailasam S， Buzmakov A. A scalable，distributed framework for significant subgroup discovery. Knowledge⁃Based Systems，2024，284：111335.

[7] Jamshidi K， Mahadasa R， Vora K. Peregrine：A pattern⁃aware graph mining system∥Proceedings of the 15th European Conference on Computer Systems. Heraklion，Greece：Association for Computing Machinery，2020：1-16.

[8] Yuan L H， Yan D， Qu W W，et al. T⁃FSM：A task⁃based system for massively parallel frequent subgraph pattern mining from a big graph. Proceedings of the ACM on Management of Data，2023，1(1)：1-26.

[9] 汤小春，樊雪枫，周佳文，等. 基于数据流的大图中频繁模式挖掘算法研究. 计算机学报，2020，43(7)：1293-1311.

[10] Cheng W S， Lin Y T， Huang P Y，et al. A fast and highly scalable frequent pattern mining algorithm. Future Generation Computer Systems，2024，160：854-868.

[11] 郭方方，王欣悦，王慧强，等. 基于最大频繁子图挖掘的动态污点分析方法. 计算机研究与发展，2020，57(3)：631-638.

[12] Ingalalli V， Ienco D， Poncelet P. Mining frequent subgraphs in multigraphs. Information Sciences，2018，451/452：50-66.

[13] Islam M A， Ahmed C F， Alam M T，et al. Graph⁃based substructure pattern mining with edge⁃weight. Applied Intelligence，2024，54(5)：3756-3785.

[14] Min F， Zhang Z H， Zhai W J，et al. Frequent pattern discovery with tri⁃partition alphabets. Information Sciences，2020，507：715-732.

[15] Wu Y X， Geng M， Li Y，et al. HANP⁃Miner：High average utility nonoverlapping sequential pattern mining. Knowledge⁃Based Systems，2021，229：107361.

[16] Wang X， Xu Y， Zhan H Y. Extending association rules with graph patterns. Expert Systems with Applications，2020，141：112897.

[17] Liu X L， Dong B W， Fu W Z，et al. Extending graph rules with oracles. Proceedings of the VLDB Endowment，2024，17(7)：1775-1787.

[18] 焦鹏飞，吴子安，刘欢，等. 基于多视图对比学习的动态图链接预测方法. 南京大学学报(自然科学)，2024，60(3)：383-395.

[19] Benhidour H， Almeshkhas L， Kerrache S. Link prediction in directed complex networks：Combining similarity⁃popularity and path patterns mining. Applied Intelligence，2024，54(17)：8634-8665.

[20] Wang X， Lan Z， He Y A，et al. A cost⁃effective approach for mining near⁃optimal top⁃k patterns. Expert Systems with Applications，2022，202：117262.

[21] Lin P， Song Q， Shen J L，et al. Discovering graph patterns for fact checking in knowledge graphs∥Database Systems for Advanced Applications. Cham：Springer，2018：783-801.

[22] Diaz⁃Garcia J A， Ruiz M D， Martin⁃Bautista M J. A survey on the use of association rules mining techniques in textual social media. Artificial Intelligence Review，2023，56(2)：1175-1200.

[23] Gong N Z， Xu W C， Huang L，et al. Evolution of social⁃attribute networks：Measurements，modeling，and implications using Google+∥Proceedings of the 2012 Internet Measurement Conference.New York，NY，USA：Association for Computing Machinery，2012：131-144.

[24] Leskovec J， Mcauley J. Learning to discover social circles in ego networks. Advances in Neural Information Processing Systems，2012，1：539-547.

[25] Takac L， Zabovsky M. Data analysis in public social networks∥International Scientific Conference and International Workshop Present Day Trends of Innovations 2012. Łomża：[ s.n]，2012：1-6.

[26] Rossi R A， Ahmed N K. The network data repository with interactive graph analytics and visualization∥Proceedings of the AAAI Conference on Artificial Intelligence. Austin，TX，USA：AAAI Press，2015：4292-4293.

[27] Lü L Y， Zhou T. Link prediction in complex networks：a survey. Physica A：Statistical Mechanics and its Applications，2011，390(6)：1150-1170.

[28] Jeh G， Widom J. SimRank：A measure of structural⁃context similarity∥Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，2002：538-543.

[29] Galárraga L A， Teflioudi C， Hose K，et al. AMIE：Association rule mining under incomplete evidence in ontological knowledge bases∥Proceedings of the 22nd International Conference on World Wide Web. New York，NY，USA：Association for Computing Machinery，2013：413-422.

[30] Bayardo R J， Agrawal R. Mining the most interesting rules∥Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，1999：145-154.

[31] Brin S， Motwani R， Silverstein C. Beyond market baskets：Generalizing association rules to correlations∥Proceedings of the 1997 ACM SIGMOD International Conference on Management of data. New York，NY，USA：Association for Computing Machinery，1997：265-276.

基金资助

国家自然科学基金(62172102)

四川省科技创新人才基金(2022JDRC0009)