几种图匹配的核方法研究

摘要：数据挖掘算法现面临挑战，这个挑战就是要处理日益增长的复杂对象。对于图数据，随机游走核是有力的容错图匹配方法。由于随机游走核的局部定义，它的适用性取决于潜在图表示的特性。另外通过定义图实例的核函数，数据挖掘算法的整个工具变得可用。迄今为止，已经提出了基于图的游走、子树和循环的图核。一般问题在于，这些核要么运算量大要么受限于他们的表达性。我们试着通过定义基于路径有表达性的图核克服这个问题。由于计算图的所有路径和最长路径是np-难，我们建议基于最短路径图核。这些核在多项式时间内就可以计算，保持表现力并且仍然是正定的。

关键词：np-难；图核；核方法；随机游走核；最短路径核；正定

中图分类号：tp391.4 文献标识码：a 文章编号：1009-3044（2013）07-1622-04 1 概述

核方法是统计学习理论[18]的流行方法，它在数据挖掘上有多种应用。核可以完成比如分类这样的任务，这些任务以非线性假设和很种不同数据类型的支撑向量机、回归[5]、聚类[1]和主成分分析[19]来完成。

核方法的早期研究几乎都只处理基于向量描述的输入数据。haussler[10]第一个定义了在结构对象上用原则性方法设计核，也

就是所谓的r-卷积核。卷积核的基本想法是定义复合对象子结构正定核并使用在卷积下正定函数是关闭的属性来组合这些核，成为一个复合对象自身的核函数。因此，卷积核推断出复杂对象相似性来源于他们部件的相似性。将一个串拆分成两个子串，例如，可以认为是一个串的分解。对于串匹配，很多核函数提出来，大部分核函数属于卷积核类。基本理念是将串映射到用串索引坐标的特征空间。

近年来，结构对象、图[14]中节点和图的核都已经定义了，结构对象比如字符串、树、传感器、动力系统。一般说来，图核是基于经由核的图子结构的比较。为了这个目的已经考虑游走[13]、子树[17]和循环模式[11]。然而，这些子结构的核要么运算量大，有时甚至是np-难，要么局限于它们的表现力。

现存核方法的不足是因为图核设计时的竞争需求：第一，核应该是图相似性的优良准则；第二，它的运算应可能在多项式时间内；第三，核必须是正定的；第四，理想情况下它不仅仅只对图的一小部分子集适用，对所有图都应适用。现存图核对这四个目的至少有一个达不到。这篇文章我们介绍了一类图核，它是基于图最短路径来评价相似性，它在多项式时间内也可以计算出，是正定的并且适用于广泛的图。 2 现有图核

在我们回顾现存图核之前，为了方便论证，我们先规定图论中的基本定义。

2.1 初级图论

图[g]由节点（或定点）集[v]和边[e]组成。在本文中，[n]表示图的节点数，[m]表示图的边数。

属性图是节点和/或边带有标签的图；标签指的是属性。在例子中，属性由形如（属性-名称，值）的对构成。[g]的邻接矩阵[a]定义如下：

这里[vi]和[vj]是[g]的节点。图上长度为[k-1]的步子[w]是节点[v1，v2，...，vk]的一个序列，[vi-1，vi∈e ]，[ 1任何解决所有最短路径对问题的算法可以用来确定[s]中所有最短距离的边标签。我们建议用弗洛伊德的算法。这个算法运行时间为[on3]，它也适用于有负边权值的图，但是多数不包含负的权值环。此外，执行起来也很简单。下面将提到经弗洛伊德算法将图[i]转换到[s]的过程，称为弗洛伊德转换。 3.2 最短路径核

继我们输入图的弗洛伊德转换，我们现在可以定义一个最短路径核。

定义1（最短路径图核）[g1]和[g2]是两个图，经弗洛伊德转换为[s1]和[s1]。接着定义最短路径图核[s1=v1，e1]和[s2=v2，e2]为

下面我们证明最短路径核的有效性。 引理1最短路径图核是正定的。

弗洛伊德-沃尔什（n节点的图g和邻接矩阵a）

证明：最短路径核是运行在弗洛伊德转换图的简单游走核， 弗洛伊德转换图只考虑了长度为1的游走。首先，我们选择一个节点的正定核和边的正定核。接着我们定义长度为1的游走对[k1walk]，顺着游走碰到的节点和边的核结果。作为一个节点和边核的张量结果，[k1walk]是正定的。接着我们0-扩展[k1walk]到游走的整个节点对，将长度[≠]1的所有游走核值设为0。这个0-扩展维持正定性。最短路径核的正定性直接就像卷积核[10]一样，从它的定义证明正定的。

运行时间复杂度 最短路径核避免了动摇，但是如何与已知的随机游走核（测量部分相似性）进行运行时间复杂度的比较仍旧是个有趣的问题。

不失其广义，我们假设要处理两个各有[n]个节点和[m]条边的图。为了计算游走核，我们首先要确定直积图，直积图的节点数明显上限到[n2]。我们接着要转化这个直积图的邻接矩阵；[x?x]矩阵的逆的标准算法要求[ox3]时间。我们的例子中[x≤n2]，随机游走图核整个的运行时间复杂度为[on6]。

使用弗洛伊德沃尔什算法时最短路径核要求进行在[on3]内能完成的弗洛伊德转换。如果原始图是连通的，转换图的边数是[n2]。双方转换图所有边的成对比较是确定核值所必需的。我们要考虑[n2*n2]边对，结果就是整个运行时间是[on4]。

有利于游走核，如果两个因素图所有节点贴有同样地标签，直积图的节点数仅仅是[n2]可能会有争论。这对基于整个相似性的随机

游走是成立的，但是基于部分相似性的随机游走总会引起有[n2]节点的积图。因此，只有测量整个相似性并创建[n43]节点积图的随机游走核有相同运行时间复杂度。 4 实验结果 4.1 随机游走核

在本节，我们提供一个评估，它用传统随机游走核进行评估图相似性。

实验数据库由线图组成，代表线图有大写字母。为了获得字母噪音样本集，我们重复应用失真到干净的字母原型。接着失真的线图通过代表节点和边的线终点转变为图。节点用相应终点的二维坐标标签。按照这个程序，我们每150就构造一个训练集和验证集，还有一个750的测试集。数据库由15类字母[（a，e，f，h，i，k，l，m，n，t，v，w，x，y，z）]组成。如图1和2所示。 4.2 最短路径核

为了评价我们最短路径图核的实际性能，我们选择从蛋白质中选择分类任务。0个蛋白质，每90个一类，应该分为6个不同功能类，这些功能类在10倍的交叉检验，单独地基于蛋白质结构信息。 我们随机抽取90个蛋白质，将这些蛋白质结构转化为图模型。每个节点都和它空间中三个最近邻连通。简单说，二级结构元素间距离就用它们空间中心的距离计算。边用它们在埃代表的距离进行标签。节点用代表它们的类型、片层和氨基酸中的长度进行标签。 我们在蛋白质模型图上运行游走核和最短路径核，因为计算游走

核步子会到无穷大，这就导致内存问题，我们粗略估计它步数达到k，设定长步到0的核值。我们在4到6的范围内运行k的测试。 [核类型＼&精确度＼&标准偏差＼&最短路径＼&93.33＼&3.22＼&长度4的游走＼&.63＼&2.30＼&长度5的游走＼&88.＼&1.99＼&长度6的游走＼&88.15＼&1.67＼&]

最短路径核以至少93.33%的精确度胜过所有游走核，0个蛋白质上最坏的最短路径核精度等级明显高于用长度为4的最好游走核。结果，考虑最短路径而不是游走会明显增加分类的精度。 5 结束语

我们定义了基于最短路径的图核，它在多项式内可以计算，是正定的并且保有表达性，同时避免了“动摇”现象。在分类蛋白质图模型到功能类的实验中，它们明显胜过随机游走核。在往后的学习中，我们要考虑到图论和核方法之间的联系。 参考文献：

[1] a. ben-hur，d. horn，h. siegelmann，v. vapnik.a support vector method for hierarchical clustering[m]//t. k. leen，t. g. dietterich，v. tresp.editors， advances in neural information processing systems 13.mit press，2001：367-373.. [2] h. berman，j. westbrook，z. feng，g. gilliland，t. bhat，h. weissig，i. shindyalov，p. bourne. the protein data bank[j].nucleic acids research，2000（28）：235-242. [3] k. m. borgwardt，c. s. ong，s. schoenauer，s.

vishwanathan，a. smola，h.-p.kriegel. protein function prediction via graph kernel. bioinformatics，2005. in press. [4] e. w. dijkstra.a note on two problems in connection with graphs[j].numerische mathematics， 1959（1）：269-271. [5] h. drucker，c. j. c. burges，l. kaufman，a. smola，v. vapnik. support vector regression machines[m]//m.c.mozer，m.i.jordan，t. petsche，editors.advances in neural information processing systems 9，cambridge，ma，1997：155-161. [6] r. floyd.algorithm 97， shortest path. comm. acm， 5：345， 1962. （下转第1629页） （上接第1625页）

[7] m. l. fredman，r. e. tarjan.fibonacci heaps and their uses in improved network optimization algorithms[j].jacm，1987，34（3）：596–615.

[8] t. g¨artner.exponential and geometric kernels for graphs.in nips*02 workshop on unreal data， volume principles of modeling nonvectorial data，2002.

[9] t. g¨artner， p. flach， and s. wrobel. on graph kernels： hardness results and efficient alternatives[m]//b. sch¨olkopf and m.warmuth， editors， sixteenth annual conference on computational learning theory and seventh

kernel workshop， colt.springer，2003.

[10] d. haussler.convolutional kernels on discrete structures.technical report ucsc-crl-99 - 10， computer science department， uc santa cruz，1999.

[11] t. horvath， t. g¨artner， and s. wrobel. cyclic pattern kernels for predictive graph mining. in proceedings of the international conference on knowledge discovery and data mining， 2004.

[12] d. jungnickel. graphen， netzwerke und algorithmen. biwiss.- verlag， mannheim， germany， 1994.

[13] h. kashima， k. tsuda， and a. inokuchi. marginalized kernels between labeled graphs[c].in proceedings of the 20th international conference on machine learning （icml），washington， dc， united states，2003.

[14] r. s. kondor，j. lafferty.diffusion kernels on graphs and other discrete structures[c].in proceedings of the icml，2002.

[15] i. schomburg，a. chang，c. ebeling，m. gremse， c. heldt， g. huhn， and d. schomburg. brenda， the enzyme database： updates and major new developments. nucleic acids res， 32 database issue：d431–d433，jan 2004.

[16] p. maha，n. ueda， t.akutsu， j.-l. perret， and j.-p.

vert. extensions of marginalized graph kernels.in

proceedings of the twenty-first international conference on machine learning， 2004.

[17] j. ramon and t. g¨artner. expressivity versus efficiency of graph kernels. technical report， first international workshop on mining graphs， trees and sequences （held with ecml/pkdd’03）， 2003.

[18] b. sch¨olkopf and a. j. smola.learning with kernels[m].mit press，2002.

[19] b. sch¨olkopf， a. j. smola， and k.-r. m¨uller. kernel principal component analysis. in b. sch¨olkopf， c. j. c. burges， and a. j. smola， editors， advances in kernel methods-support vector learning， mit press，cambridge， ma，1999：327-352.