几种图匹配的核方法研究

张燕

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

如果[vi≠vi i≠j?i，j∈1，...，k]，[w]就是一个路径。或者，游走经常就看作是路径，路径于是命为简单的、唯一的或无环的路径，这有可能会引起困惑。为了澄清余下本文的不同，我们定义路径是没有节点重复的游走。环就是[v1=vk]的游走，简单环除了[v1]不含有任何重复节点。

汉密尔顿路径是通过图中每个节点一次，且恰好一次的路径。欧拉路径是通过图中每条边，且恰好一次的路径。

2.2 随机游走核

随机游走核建立于计算两个输入图匹配游走数基础的想法上。[G?rter]及其他人[9]定义了一个讲究的方法通过两个输入图[G1=V1，E1]和[G2=V2，E2]的直积图[G×]来决定所有的匹配游走对：

尽管有清晰的定义，这些随机游走核仍具有难点。直积图可能包含[V1×V2]个节点。即使它的邻接矩阵是稀疏的，但它可能通过矩阵的力量变为满的。处理这样大的满阵会引起庞大的运算时间和内存需求。

除了运算量问题，输入图中小的相同子结构可能会引起高相似度。由于游走允许节点的重复，这些图核会引起“动摇”问题，也就是通过重复访问节点的相同环，游走可以人工产生高相似值。因此动摇限制了随机游走图核的表达性。

分析现在的随机游走核，很明显测量部分相似性方法会引起大的积图。围绕[G?rter]等人的原始随机游走核，已经丢失了寻找部分相似性的能力，减少了图核的表达性。两个方法都有动摇问题。

2.3 标签富集及核的重定义

进行的步骤改进了基于游走图核的表达性和有效性。另外，每个图增加的标签可以减少两图匹配节点数。这个测量减少了计算它们核值得工作，这是因为要考虑的游走对数减少了。

基于游走图核为了避免动摇进行了重定义，这样游走不包含两节点构成的子环。然而当节点富集在试验评价上对分类精度有了积极影响时，同时也阻止两节点环有更大的改进。

3 最短路径图核

确定所有路径是NP-难问题，同时找到路径的特殊子集也不必要。确定图的最长路径又是NP-难，这是因为它考虑决定图是否包含哈密尔顿路径。然而计算图的最短路径在多项式时间内可以解决。迪杰斯特拉[4]（从源节点出发的最短路径）和弗洛伊德-沃尔什[6]（所有节点对）这些杰出算法考虑分别在[Om+n*log n] [7]和[On3]时间内确定最短距离。

3.1 弗洛伊德-转换

我们最短路径核必要的第一步就是讲原始图转换为最短路径图。最短路径图[S]包含输入图[I]的相同节点集。和输入图不同，通过[I]中游走连接的[S]中所有节点间存在边。[S]中[vi]和[vj]间每条边通过这两个节点的最短距离来标签。

任何解决所有最短路径对问题的算法可以用来确定[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 最短路径核

为了评价我们最短路径图核的实际性能，我们选择从蛋白质中选择分类任务。540个蛋白质，每90个一类，应该分为6个不同功能类，这些功能类在10倍的交叉检验，单独地基于蛋白质结构信息。

我们随机抽取90个蛋白质，将这些蛋白质结构转化为图模型。每个节点都和它空间中三个最近邻连通。简单说，二级结构元素间距离就用它们空间中心的距离计算。边用它们在埃代表的距离进行标签。节点用代表它们的类型、片层和氨基酸中的长度进行标签。

我们在蛋白质模型图上运行游走核和最短路径核，因为计算游走核步子会到无穷大，这就导致内存问题，我们粗略估计它步数达到k，设定长步到0的核值。我们在4到6的范围内运行k的测试。

[核类型＼&精确度＼&标准偏差＼&最短路径＼&93.33＼&3.22＼&长度4的游走＼&89.63＼&2.30＼&长度5的游走＼&88.89＼&1.99＼&长度6的游走＼&88.15＼&1.67＼&]

最短路径核以至少93.33%的精确度胜过所有游走核，540个蛋白质上最坏的最短路径核精度等级明显高于用长度为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/PKDD03）， 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.