最小权重有向频繁子图挖掘

任 威

（铁道部经济规划研究院 经济管理咨询部，北京 100038）

面对海量的图数据时，挖掘满足最小支持度的频繁子图是人们感兴趣的。当前图挖掘的热点在于有向图，即在大量的有向频繁图中挖掘出一种性质更优的图。本文介绍一类特殊的频繁子图—最小权重有向频繁子图，它满足最小支持度阈值，并且所包含的边和顶点的权重之和在所有同构子图中是最小的，本文提出的挖掘方法用于处理此类频繁子图，在厂区铁路运输分析研究中有实际应用。根据厂区铁路分布规模小、运输密度高的特点，用加权有向图表示某厂区铁路线路网结构，不同标记顶点表示不同类型的车间，不同标记的有向边表示不同的厂区铁路线，顶点和边的权重表示对应的运输成本，权重越小成本越小。权重之和最小的子图是运输成本最小的厂区铁路网结构，是在海量路网结构中要寻找的目标。

关于挖掘频繁子图的算法可以分为两部分：（1）宽度优先算法（BFS）,采用apriori性质枚举出现的子图以保证满足最小支持度，有代表性的是AGM[1]和FSG[2]两种算法，分别针对顶点和边进行扩展，但会产生大量复制图，效率不高。（2）深度优先算法（DFS），包括gSpan，FFSM和GraphGen等，通过扩展频繁边来逐步得到频繁子图。Han和Yan提出的gSpan[3]对标记图进行挖掘，但无法避免子图同构测试，FFSM算法[4]巧妙地将子图扩展问题转化为矩阵操作，降低了算法复杂度。GraphGen算法[5]运用图论理论，将子图扩展转化为子树扩展，进一步提高了算法效率。

以上是无向图的挖掘，Li Yuhua等人提出的mSpan[6]针对有向图进行挖掘，收效良好。Masaki Shinoda等人提出的GWF-mine算法[7]考虑了权重因素，将其作为挖掘条件。

针对厂区铁路运输线路结构的研究，挖掘的是既带有方向标识，也带有权重的图数据。本文提出的算法针对此特殊图数据集进行挖掘，达到了预期目的，在第1种算法基础上，提出了第2种改进算法。

1 基本概念

定义1（子图）：设G=(V, E)是一个图，设V'⊆V和E'⊆E，若对E'中任意一条边eij={vi, vj}，都有vi∈N'和vj∈N'，则称G'=(V', E')是G的一个子图。

定义2（子图同构）：设图G=(V, E)和G'=(V', E')，若存在一一映射g:vi→v'i，且e={vi,vj}是 G的一条边，且仅当e'=(g(vi),g(v'i))是G'一条边，则G与G'同构。

定义3（图规模）：有向图中节点与两个节点之间单个或成对有向边（计数为1）的数量和。

2 最小权重有向频繁子图挖掘算法

本文提出两种算法，第1种算法WDSpan先挖掘出频繁子图，再考虑权重，采用邻接矩阵比较法筛选最小权重频繁子图。第2种算法MWD以加入权重的支持度阈值作为挖掘和剪枝的条件，通过同构测试和平均权重的比较更新，既保证了结果的正确性和完整性，又减少了存储空间，起到了改进效果。

图1 权重有向例图

2.1 WDSpan

采用gSpan算法框架，定义最右顶点，最右路径，前向边和后向边，前向扩展和后向扩展以及最右扩展[5]，核心是深度优先方法，搜索最小DFS编码，称为基本下标，记为dfs(s)。

对图1进行DFS标记，顶点间存在单向和双向边，对不同的边给予不同的标记，以0代表双向边，1代表与前向边有相同方向的边，_1代表与后向边有相同方向的边。

图2是权重有向图的3种不同的DFS标记，加粗表示前向边，其余为后向边。顶点采用字母（数字）表示方法，字母表示顶点类别，括号中的数字表示顶点访问顺序，边上的字母表示有向边类别（双向边中两条有向边的类型相同），数字表示有向边的方向。以（C）为例，μ1是起始顶点，μs是最右顶点，最右路径为 μ1— μ2—μ4—μ5。

图2 3种不同的DFS标记

对每个DFS标记，定义边序组织有向边，边序是在给出顶点访问顺序的基础上，所有后向边出现在该顶点前向边之前，若此顶点没有前向边，则把它的后向边放在上一个访问节点前向边之后。基于边序可将加下标的有向图转换为边的序列。

定义4（DFS编码序）：若存在某个图数据的两种不同DFS编码，γ1={e11e12…e1n}和γ2={e21e22…e2m}，其中eij表示图γi遍历的第j条边，γ1和γ2的线性序由下例条件决定：

（1）γ1=γ2，当且仅当 m=n，且 e1i=e2i，其中1≤ i≤ n。

或者：n

（3）γ2≺ γ1其他情况

序列排序规则为：令边序≺ T占据第1优先级，边的起始顶点标记占据第2优先级，方向标示（1 ≺ 0≺ _1 ）占据第3优先级，边的标记占据第四优先级，边的终止顶点标记在最末级。上面 3种 DFS编码的第 1条边 (μ1μ2A 1 a A)、(μ1μ2A _1 a A)和(μ1μ2A _1 c C)中，≺ T无差别，起始顶点μj无差别，方向标示1≺ _1，所以得到γ1≺ γ2≺ γ3，γ1就是要找的基本下标。与图2对应的不同的DFS编码如表1所示。

表1 3种不同的DFS编码

使用标准邻接矩阵把权重有向图的权重表示为方阵中的元素，主对角线上的元素表示有向图节点权重，其余各点表示特定两节点间有向边的权重。图1记录为下面的邻接方阵。

对任意顶点，如果点权重与和它有关联的边权重太大，表示运输成本过大，要将其剪枝。假设权重关联最大阈值不能超过20，顶点i的相关权重计算公式为：(ai1+ai2+…ain)+(a1i+a2i+ani)_aii，上例中，5个顶点权重分别为16、12、19、15、15，小于最大权重阈值。为了简便，判断一个图是否可以剪枝，先求出邻接矩阵的1_范数和∞_范数并相加，若小于规定的顶点权重关联最大阈值，则必然满足条件；否则计算每个顶点的权重关联值来逐一比较。

可比较的邻接矩阵一定有相同结构，只需把非零处的权重相加求和再比较大小即可，不用遍历整个矩阵。

2.1.1 算法描述（gSpan）

输入：权重有向图数据集WDGD，最小支持度阈值min_sup，DFS编码 S。

输出：频繁子图集合S。

（1）put S、T←φ'S，为频繁子图集合。T为使s最右扩展一次后的结果集；

（2）if s≠dfs(s) then ；

（3）return；

（4）put S←s；

（5）遍历WDGD一次，找出所有可使S最右扩展的边e，put T←s+e；

（6）用DFS词典序对T排序；

（7）for each T中的频繁s+e，do；

（8）对s+e重复s的扩展过程。

2.1.2 算法描述（WDSpan）

输入：频繁子图集合S，单独顶点的权重关联最大阈值t。

输出：最小权重频繁子图集合C 。

（1）计算S中每个子图s的1-范数和 ∞-范数，相加求和，if 和小于t，则放在C1中；

（2）记和大于t的子图s= {v1, v2, …, vn}；

（3）For i=1, 2, …, n

计算每个顶点的关联权重w1, w2, …, wn若他们都小于t，则放在C1中；

（4）对同构的矩阵，找到权重和最小的，记为 s1，put C ← s1。

2.2 算法MWD

WDSpan中，第1步是挖掘，第2步根据权重来剪枝和筛选，得到最小权重频繁子图，但会出现很多权重很大的频繁子图作为中间结果再剪枝，使算法复杂度偏高。对此缺陷，本文根据权重图特点，把图数据的权重和支持度阈值相结合作为剪枝标准，以图1为例来说明新的剪枝计算方法。

定义5（平均权重）：一个权重有向图，图规模为n，则它的平均权重为每个点和成对或单向有向边权重之和除以n，即(vi+eij)/n，其中vi(i∈1, 2, …, m)表示m个顶点的权重，eij(i, j∈1, 2, …,m)且i< j表示单独或成对有向边的权重，eij= (vi·aij+vj·aij)/(vi+vj) 。

计算得：图1的规模为11，平均权重约为2.84。

定义6（平均权重支持度阈值—MWeight）：一个图数据的平均权重和它出现在图数据库中支持度计数的乘积。

平均权重支持度阈值是一个对图数据剪枝的标准，给定子图的支持度计数和平均权重支持度阈值，采用以下两个条件进行剪枝。

（1）sup(G)

（2）MWeight(G)≥MWeight(G3)所有的平均值， G3表示已挖掘出的两个顶点和有向边组成的规模为3的子图，是有实际意义的最小子结构。

第（2）条表示若某个子图的MWeight不比规模为3的“小”子图的平均值小，则再对它进行扩展也不能得到感兴趣的子图（反单调性）。

首先，计算得到所有G3的平均权重支持度阈值的平均值。采用深度优先策略，获得1—权重频繁子图并按权重由小到大排序，从最小点进行扩展，按照由小到大顺序依次将频繁有向边连接到顶点上，形成2—权重频繁子图。按照权重排序把频繁顶点连接到频繁有向边上，可以形成G3，计算所有G3的平均权重支持度阈值再求平均值，就可以得到剪枝条件（2）。如此再挖掘G4、G5直到Gn，总是把频繁顶点连接到原图上，满足最小支持度阈值，再计算平均权重支持度阈值，进而剪枝。

子图扩展总是将权重最小的有向边和顶点连接到原子图中，但它可能并不出现在图数据库中，需进行子图同构测试。比较从不同权重扩展的生成子图的平均权重，寻找生成的最小权重子图作为下次扩展的首选，如图3所示。

图3 （a）最小权重子图

图3 （b）最小权重子图

图3（a）权重为2.58，图3（b）权重为2.28，挖掘时先得到上面的生成子图，但要将图3（b）作为下一步扩展的首选子图。

2.2.1 算法描述（MWD）

输入：权重有向图数据集WDGD，最小支持度阈值min_sup

输出：最小权重有向频繁子图集合C

（1）找到所有1—频繁子图，按照权重由小到大进行排序(顶点和有向边分别排序)， put G1←所有1—频繁子图。G1={v1, v2, …, vm; e1, e2, …,en}；

（2）put Gk→φ(k=3, 4, …, l)， l 是 WDGD中最大图规模；

（3）put Hk→φ(k=3, 4, …, l) ；

（4）找到所有3—频繁子图，对不同构的子图，找到有最小平均权重的那些子图，记为min_g3，同理，其他K—频繁子图不同构的最小平均权重子图记为min_gk-1；

（5）Put G3← min_g3；

（6）for k=4, 5, …, l for每个vi和ejdo ；

join min_gk-1+ ej，+ min_gk-1+ vi；

（7）if MWeight(min_gk-1+ ej)≥ MWE（所有3—频繁子图权重和的平均值）剪枝；

（8）if MWeight(min_gk-1+ vi)≥MWeight（所有3—频繁子图权重和的平均值）剪枝；

（9）find min_gk-1+ ej以及min_gk-1+ vi中平均权重最小的子图，put them→Gkput others →Hk；

3 实验结果与分析

性能测评实验的平台是Pentium IV 2 GHz CPU，2 GB内存，硬盘为300 G，操作系统Windows server 2008，实验用MATLAB环境编写。实验所用的数据来自人工模拟合成的关于厂区铁路结构数据集。表2列出了数据模拟使用到的参数和含义。

表2 实验数据参数及意义

采用的有向图数据集表示为D10KT30-L50I10E50F20，实验对两种算法在挖掘的完整性和运行效率上进行了比较分析。

图4（a）、（b）分别给出在不同的支持度阈值下，两种算法发现频繁子图的数目和最小权重频繁子图的数目。增大，两种算法的运行时间逐渐接近。

图4 （a）WDSpan的子图数目对比

图4 （b）MWD的子图数目对比

图4 （c）运行时间对比

4 结束语

本文针对权重有向图数据集，提出两种挖掘最小权重频繁子图的算法。采用电脑人工合成数据集进行性能分析实验，表明两种算法都可以保证挖掘结果的正确性和连通完整性。得到最小权重有向频繁子图，是运输成本最小且有一定出现比例的厂区铁路线结构模型。分析原因，改变设计，可以降低厂区铁路运输成本。

进一步分析发现，MWD的性能要优于WDSpan，表现为更少的运行时间和更小的存储空间。但是MWD算法也有不足，如不可避免子图同构测试，每一次扩展都要和其他扩展结果通过比较平均权重找到最小权重频繁子图。

横坐标表示递增的最小支持度阈值，表示挖掘到的频繁子图数目呈递减趋势。随着最小支持度阈值的增大，原来频繁的子图有可能变为不频繁被剪枝，造成频繁子图数目减少。

对比（a）和（b）两幅图，WDSpan产生频繁子图的数目远多于MWD产生的数目，而它们产生的最小权重频繁子图数目却差不多，说明两种算法挖掘结果是相当的，但后者产生更少的中间产物，需要较少的存储空间，算法性能更好。

图4（c）给出了在不同的支持度阈值下，WDSpan和MWD的运行时间对比。支持度较小时，两种算法运行时间相差很大，随着支持度的

[1]Inokuchi A, Washio T, Okada T. An apriori-based algorithm for mining frequent substructures from graph data[C]. Proc.of the PKDD 2000. LNAI 1910, 2000：13-23.

[2]Michihiro Kuramochi, George Karypis. An Efficient Algori

thm for Discovering Frequent Subgraphs[J]. IEEE TRAN

SACTIONS ON KNOWLEDGE AND DATA ENGINEE

RING, VOL. 16, NO. 9, SEPTEMBER 2004.

[3]Yan Y, Han J. gSpan: Graph-Based substructure pattern mining[C]. Proc. of the 2002 Int’l Conf. on Data Mining (ICDM 2002).Maebashi, 2002.

[4]Han J, Wang W, Prins J. Efficient mining of frequent subgraphs in the presence of isomorphism[C]. Proc. of the IEEE Int’l Conf.on Data Mining (ICDM 2003). 2003.

[5]LI XT , LI JZ .An efficient frequent subgraph mining algorithm[J]. Journal of Software, Vol.18, No.10, October 2007.

[6]LI Yuhua. A Directed Labeled Graph Frequent Pattern Mining Algorithm based on Minimum Code[C]. Third International Conference on Multimedia and Ubiquitous Engineering.2009.

[7]Masaki Shinoda, Tomonobu Ozaki.Weighted Frequent Subgraph Mining inWeighted Graph Databases[C]. 2009 IEEE International Conference on Data Mining Workshops.