一种有效的解图匹配问题的核方法研究 2(2)

由于映射 的选取，如 (G)的分量可以是两图中某一公共子路径的条数等，核k :G × G→R可以看成是两个图G1和G2间的相似性度量。

核方法作为一种非线性方法可以解决这些问题。这将使得原来用于向量表示的标准算法也适合图，它可以把统计模式识别和结构模式识别有机地结合起来。

3 图核

一般常见的图核可分为三大类：基于路径的核方法如随机游走核、最短路径核；基于有限规模子图的核方法；基于树模式的核方法如树模式图核、快速子树核、Weisfeiler-Lehman图核等。本节重点深入研究快速子树核和Weisfeiler-Lehman图核及其在解决图匹配问题时的算法复杂程度。

定义3.1（快速子树核））图G和图G’之间快速子树核

(h)kramon(G,G') kh(v,v')

v vv' v'

通过分析比较，两图之间的快速子树核的计算复杂度是O(n

对的比较和在O(4d2h4d)，其中包括n2个节点)范围之内，邻居节点的所有匹配次数。重复h次，其中h是一个多分类因子而不是指数。以k1为起是点，经过kh-1到kh递归地计算子树核。

定义3. 2（Weisfeiler-Lehman图核）图G和图G’之间的WL图核定义为 (h)kWL(G,G') (si(v),si(v'))|f(si(v)) f(si(v')),i{0,...,h},v V,v V'

其中Si（v）为节点v在第i次迭代中的多分类标签集，f是一个映射标签压缩函数，对于所有的i j，集合 f(si(v))|v V V' 和集合f(sj(v))|v V V'是不相交的。S0（v）是在标签图v和非标签图中的初始标签并且f(s0(v)) s0(v)。

4 实验论证

4.1数据准备

实验数据集主要包括MUTAG， NCI1，NCI109，ENZYMES，D&D。其中MUTAG是一个根据是否对革兰氏阴性菌鼠伤寒沙门氏菌有突变作用的含有188个突变芳香和杂环硝基化合物。NCI1和NCI109分别代表两组平衡的化学混合物数据集，它们来自于非小细胞肺癌细胞和卵巢癌细胞系。ENZYMES 是一个具有三层结构的蛋白质数据集，它包含从酶蛋白质数据库中获取的600个蛋白质酶。这种情况下的主要任务是正确给每个蛋白质添加一个6层结