Research On Graph Kernels And Their Application In Pattern Recognition

The discipline of pattern recognition is usually divided into the statistical and thestructural approach. In statistical pattern recognition, the object is generallyrepresented by feature vector, so we can use the mature algorithms in the vector space.The disadvantage of statistical pattern recognition is that it is difficult to representcomplex relationships that might exist among different parts of a pattern. In structuralpattern recognition, object of study is generally represented by graph, and then thesimilarity of objects has been transformed to the similarity of graph. However, thecomputational complexity of graph matching algorithm is high and there is nosystematic computing method. Therefore, researchers have tried to unify statisticalpattern recognition and structural pattern recognition since the birth of structuralpattern recognition.In recent years, kernel methods have solid theoretical foundation and have beensuccessfully applied to many practical problems. Kernel methods have become aresearch hotspot. Kernel method applies not only to feature vector representation ofthe pattern but also to the structural data. Consequently, graph kernel has become anew research hotspot. Graph kernel can be thought of as a dot product in some featurespace. Consequently, algorithms in vector space are also fit for graph.Diffusion Kernels, Convolution Kernels and Walk Kernels have been proposed inthe literatures. But there are still many issues that need further research, the paperresearches on graph kernels and their application in pattern recognition.The following innovative works have been completed:(1) The spanning tree kernel and its derived kernels have been constructed, andalso a comparison of these kernels has been made. The constructed spanning treekernel is expressive, positive definite, computable graph kernel, and it is applicableto most graphs. Their compution time complexity is lower than the random walkkernel. In the face recognition, the recognition accuracy rate of these kernels ishigher than the walk kernel.(2)The cycle kernel, based on spanning tree, and its derived kernel have beenconstructed by two methods, and a comprison of these kernels has been made. Thetime complexity of the cycle kernel based on spanning tree is lower than the existingcycle kernel. They are computable and overcome the lack of random walk kernel, inwhich the vertices and edges can be repeated. In the face recognition, the recognition accuracy rate of these kernels is also higher than the walk kernel.(3)The diconnected components kernel has been constructed. It is applicable todirected graph, undirected graph, connected graph, non-connected graph, plan graph,non-plan graph, labeled graph and non-labeled graph. When the diconnectedcomponents kernel is applied to face recognition, the average recognition accuracyrate reaches to96%.(4)Finally, the face recognition method based on synthesis kernel has beenproposed, and the face recognition accuracy rate of synthesis kernel is higher than thesingle kernel. Here the paper extractes the region and LBP features of face images,and improves the histogram intersection kernel, and the face recognition accuracy rategets a lot improvement. On this basis, the combination of histogram intersectionkernel and graph kernel furtherly improves the face recognition accuracy rate.Finally, a summary of this article has been made and the direction of the furtherresearch has been described.