What is the definition of a kernel on vertices or edges?

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.

EDIT :

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.

What I think is happening is that these nodes or edges are also labeled. In the paper you mentioned they apply it to some biologicial data. From the paper: Edges are labeled by the distance they represent in angstroms. Node bear labels representing their type, namely helix, sheet or loop, and their length in amino acids.''. So the edges have a (one dimensional) feature vector, that is the length, and nodes have a type.

I was reading the paper you mentioned, but I find on page 6 that they use a delta kernel and a brownian bridge kernel for the nodes and edges. So what are they doing? When they compute the kernel between two nodes (delta kernel), they check if they have the same structure. If so, $k = 1$, otherwise $k = 0$. Now to compare edges they have this formula:

$$k(x,x') = max(0, c − |length(x) − length(x')|)$$

So I guess they put in the length of the first edge in $length(x)$ and the length of the second edge in $length(x')$.

In general, I guess you can have a graph where feature vectors are associated to edges and nodes. For example, let's say you want to classify the map of a city: is it a city in the US or somewhere else? The input is a graph: each building is a node, and the node has a featurevector associated to it, for example: (height, width, length, cost, built year, ...). If this vector is numeric, we can define a kernel between two nodes for example by using the Gaussian kernel, or any other 'regular' kernel you like. Let's say the featurevector is given by $x$ and $x'$, the Gaussian kernel is defined as: $$K(x,x') = \exp(||x-x'||^2/2\sigma^2)$$ where $\sigma$ is a parameter that determines the length scale.

The same goes for the edges. In this example the edges are roads, the feature vector of an edge could be: (built year, average # of traffic weekly, road quality, number of roadsigns, length). As long as this featurevector is numerical, again you can just take a regular kernel to compare them.

The intersection kernel is used typically for images. Compute the histogram of an image. Then the kernel between two images with two histograms $a_i$ and $b_i$ is given by:

$$K(a,b) = \sum_i min(a_i,b_i)$$

You seem to have unlabeled and undirected graphs. Thus you cannot really make meaningful kernels between your nodes and edges (unless your edges are labeled / weighted / have a length). I would try setting the kernel values of the edges and nodes all to 1, and see if then the shortest path kernel still gives you something sensible.