The Study of Several Kernel Methods on Graph Matching
Yan Zhang · Computer Knowledge and Technology · 2013
Data mining algorithms are facing the challenge to deal with an increasing number of complex objects.For graph data,random walk kernels are powerful methods for error-tolerant graph matching.Because of their local definition,however,the ap plicability of random walk kernels strongly depends on the characteristics of the underlying graph representation.Additionally,a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs.Graph kernels based on walks,subtrees and cycles in graphs have been proposed so far.As a general problem,these kernels are either computa tionally expensive or limited in their expressiveness.We try to overcome this problem by defining expressive graph kernels which are based on paths.As the computation of all paths and longest paths in a graph is NP-hard,we propose graph kernels based on shortest paths.These kernels are computable in polynomial time,retain expressivity and are still positive definite.