I am currently trying to perform clustering on a collection C of undirected and unlabeled graphs. I decided to use to a kernel on graphs to obtain the kernel matrix of C. Then I can derive the similarity matrix of C, by first computing the distance matrix, and then applying
similarity = np.exp(-beta * distance / distance.std())to get the similarity matrix of C. I can then use several clustering algorithms to do the job, like spectral clustering for instance.
Kernels on graphs seem to be a relatively recent subject of study, so I'm having some troubles to find documentation that can clearly explain me what is going on with some kernels. I decided to use the shortest-path kernel (Karsten M. Borgwardt and Hans-Peter Kriegel) since it seems to be the easiest to compute in a reasonable amount of time. I tried the random walk kernel, it not only suffers from tottering, but it also takes close to an infinite amount of time to compute the kernel matrix.
The shortest path kernel between G and G' is defined on their shortest path graphs like so :
k_sp(G,G′) = sum(sum(k_walk(e,e′))) (e and e' being the edges of the shortest path graphs)
k_walk is a positive definite kernel for comparing two edge walks of length 1, defined like so, in the paper :
k_walk(e, e′) = k_node(u, u′) · k_edge(e, e′) · k_node(v, v′)
Can someone explain me how you define a kernel on nodes, and on edges ?
They say that they used Gaussian kernel and Intersection kernel. I just wonder how you could apply such kernels on nodes and edges.
If you have any other advices for my problem, feel free to educate me.
Things are more clear now with Tom's answer. Nevertheless, I still having issues with the shortest path kernel with unlabeled data.
Essentially the problem is that every code I run into that is supposed to compute the shortest path kernel for unlabeled data does the following :
- 1) For a graph G compute a vector A(G) which i-th element is : the number of shortest path of length i.
- 2) kernel for graphs G and G' is given by inner product of the corresponding vectors calculated in 1) : k(G,G') = < A(G),A(G') >.
1st question : How can i relate this to the paper ? I just can't make the connection, sorry.
However this way of calculating the kernel seems much more easy to understand : one can easily show that the kernel is indeed a kernel since it's an inner product, and one can easily understand how this kernel measures similarity between two graphs (the inner product will be higher if the two graphs have a lot of shortest path of some lengths in common).
2nd question : Wouldn't it be a good idea to normalize the A(G) vector by multiplying it by the inverse of the count of shortest path in graph G ?
I didn't saw anything like that on the codes I ran into, even though it seems like a good idea. Otherwise some 'fake' similarities can show up because of size problems. Correct me if I'm wrong.
I feel like there are really no precise methodology with kernels, and that people use them carelessly. It also feels like there is a huge gap between theory and practice : in theory kernels are well defined, associated to an Hilbert space and a map, in which the data is very well distributed. In practice it's just people playing around with functions and trying to get the best results, then calling kernels great. I'm well aware that there's a gap between theory and practice in machine learning, but it feels huge here.