Spanning-tree kernels on graphs
Pattern recognition algorithms are facing the challenge to deal with an increasing number of complex objects. For graph data, a whole toolbox of pattern recognition algorithms becomes available by defining a kernel function on instances of graphs. Graph similarity is the central problem for all learning tasks such as clustering and classification on graphs. Graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. As a general problem, these kernels are either computationally expensive or limited in their expressiveness. We try to overcome this problem by defining expressive graph kernels which are based on spanning-tree. Minimum spanning tree, maximum spanning-tree kernels and mix spanningtree kernel are computable in polynomial time, retain expressivity and are still positive definite. In experiments on classification of graph models of face images, our spanning-tree kernels show significantly higher classification accuracy than walk-based kernels.
face recognition MST Maxmum spanning-tree graph kernel support vector machines
Jiang Qiang-rong Gao Yuan
College of Computer Science and Technology, BJUT Beijing, China
国际会议
长沙
英文
2676-2680
2010-03-13（万方平台首次上网日期，不代表论文的发表时间）